Repository navigation
Fix catastrophic backtracking in CommonLispLexer/EmacsLispLexer symbols - #3324
Open
kratos0718 wants to merge 1 commit into
Open
kratos0718 wants to merge 1 commit into
kratos0718 wants to merge 1 commit into
Conversation
nonmacro's "+-/" is an unescaped character-class range (it matches +,-./, not the three literal characters + - / it looks like), so "." already matched through nonmacro. constituent then added "." again via its own explicit "[#.:]", giving two ways to attribute each "." in a run to the same repeated group. A symbol rule that fails to close (the "*symbol*" special-variable rule is the easiest to trigger) forces the engine to retry every such split before giving up, which is quadratic in the run's length - a few thousand dots is already unusable. Dropped the redundant "." from constituent's own suffix instead of touching nonmacro, since some real symbols (e.g. one starting with a literal ".", already covered by tests/examplefiles/common-lisp/type.lisp) rely on nonmacro accepting it.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Reported in a comment on #3226 (the same super-linear-lexing class covered there for SPARQL/Turtle/ShExC, but a separate root cause in
lisp.py, not yet its own PR): #3226 (comment)nonmacro's+-/is an unescaped character-class range — it matches+,-./(five characters), not the three literal characters+ - /it looks like it's listing. So.already matches throughnonmacro.constituent(nonmacro + '|[#.:]') then adds.a second time via its own explicit suffix. That gives two ways to attribute each.in a run of dots to the same repeated group ((?:{constituent})*), and when the enclosing rule fails to close — the*symbol*special-variable rule (line ~463) is the easiest to trigger, since it just needs a*with no matching closing*— the engine retries every such split before giving up. Quadratic in the run's length; a few thousand dots is already unusable, and the reported repro ("*" + "." * 30) took 55s.Same bug, same fix, in
EmacsLispLexer(nonmacro/constituenta bit further down the file).Fix
Dropped the redundant
.fromconstituent's own[#.:]suffix, rather than touchingnonmacro. I initially tried removing.fromnonmacroinstead (seemed like the more obviously "unintended" side of the duplication) — that broketests/examplefiles/common-lisp/type.lisp, which has(symbol-name :#.junk): a symbol starting with a literal.needsnonmacro(which matches only the first character of a symbol) to accept..constituentcovers the repeated remainder and already includesnonmacroas one of its alternatives, so dropping the duplicate from its explicit suffix removes the ambiguity without changing what any symbol can start with or contain.Test Plan
pytest tests/ --ignore=tests/contrast(that one dir needs an unrelated optional dependency neither installed nor touched by this PR) — 5332 passed, 16 skipped, no failures, including thetype.lispexample-file test that caught my first attempt.ruff check --ignore UP031 .andregexlint --verbose pygments.lexers.lisp(CommonLispLexer OK,EmacsLispLexer OK) both clean.tests/test_lisp.py:test_symbol_redos_resistance(parametrized over both lexers): times lexing"*" + "." * 2000 + "\n", asserts under 5s. Fails on the pre-fix code well before the timeout (30 dots alone was already 55s per the issue's own measurement).test_symbol_starting_with_dot_still_lexes: regression guard for thetype.lispcase that caught my first (wrong) attempt at this fix.