Avoid quadratic backtracking in vim modeline detection by Support-itecz · Pull Request #3410 · pygments/pygments · GitHub
Skip to content

Avoid quadratic backtracking in vim modeline detection - #3410

Open
Support-itecz wants to merge 1 commit into
pygments:masterfrom
Support-itecz:modeline-backtracking
Open

Support-itecz wants to merge 1 commit into
pygments:masterfrom
Support-itecz:modeline-backtracking

Conversation

@Support-itecz

Copy link
Copy Markdown

get_filetype_from_line runs modeline_re.search() on the first and last lines of the buffer, and because the pattern is a modeline start followed by .* and an ft=/syn= assignment, a line with many starts and no assignment restarts the scan at every start, which is quadratic in the line length. guess_lexer() calls this before anything else, so guessing the language of a single 96 KB line of 'vi:' takes about 51 s (48 KB: 10 s); with this change it takes 5 ms, and 1 MB takes 50 ms. The .* can skip over any later start, so only the leftmost one can decide the result: find it with the prefix alone and run the existing pattern once with match() there, which returns the same filetype as before (checked against the old regex on 300k random lines).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant