microsoft / microsoft/knack

Inefficient regex in `extract_full_summary_from_signature`

Open
#281 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
358
Forks
101
PR merge metrics
No merged PRs in 30d

Description

As pointed out by https://gist.github.com/prodigysml/d07cd482214c80bfb6d3240454d2f679, this regex (introduced by https://github.com/microsoft/knack/commit/430c39e657d8a424ef9b631782fe0e62a6bed203, #8) is inefficient:

https://github.com/microsoft/knack/blob/e0c14114aea5e4416c70a77623e403773aba73a8/knack/introspection.py#L18

It tries to match a string such as:

        :param command_loader: The command loader that commands will be registered into

As shown in https://regex101.com/, a simple :param r requires 1214 steps to fail.

image

:param r causes catastrophic backtracking:

Image

This is because \s+, .+? and \s* all match consecutive spaces, thus can trigger many backtrackings.

A better solution is to replace .+? with \w+ to match the parameter name so that backtrackings can be greatly reduced:

\s*(:param)\s+(\w+)\s*:(.*)

image

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in knack/introspection.py at the extract_full_summary_from_signature regex around line 18. Reproduce the long-space and malformed inputs shown in the issue, then verify that parameter documentation still extracts correctly while the pathological input no longer causes excessive backtracking. The proposed regex and examples define the expected behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
cli, performance
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.