fix: Avoid O(n^2) masked source rebuild in inline tokenizer - #4017
Conversation
|
@hong4rc is attempting to deploy a commit to the MarkedJS Team on Vercel. A member of the Team first needs to authorize it. |
|
The latest updates on your projects. Learn more about Vercel for GitHub.
|
calculuschild
left a comment
There was a problem hiding this comment.
Woo nice. Very good find!
## [18.0.7](v18.0.6...v18.0.7) (2026-07-21) ### Bug Fixes * Avoid O(n^2) backtracking in HTML block close and tilde interrupt regexes ([#4014](#4014)) ([f945fc5](f945fc5)), closes [#3991](#3991) * Avoid O(n^2) masked source rebuild in inline tokenizer ([#4017](#4017)) ([9154f8f](9154f8f)) * keep empty list after blockquote as a sibling block ([#4004](#4004)) ([3f144a0](3f144a0)) * preserve code spans adjacent to tildes ([#4012](#4012)) ([0de7188](0de7188)) * Recognize setext headings whose first line starts with # ([#4015](#4015)) ([f056437](f056437)), closes [#1](#1) * treat a line of only tabs as a blank line between paragraphs ([#4007](#4007)) ([bc2f121](bc2f121))
|
A quick note here: @UziTech, would it make sense to chain a conditional to the Pardon the post-close comment. Let me know if I should file a proper issue. |
|
@anthon I think the correct thing to do if the first parameter is not a string would be to throw an error. That seems to already happen in this case. |
|
You're right. Previously it failed silently, which I thought was elegant render-library design; no input no output. Anyway – thanks for great work! |
While looking for remaining quadratic paths after #4013/#4014, I found that the link-masking step in
Lexer.tokenizeis O(n²) on some ordinary inputs.Before em/strong processing,
tokenizemasks out reflinks, escaped characters, and other inline blocks so they don't interfere. Each of the three masks ran awhile ((match = rule.exec(maskedSrc)))loop that rebuilt the entiremaskedSrcstring on every match:For an input with k matches that's k full-length string rebuilds — O(k·n), i.e. quadratic when the matches are dense. It's easy to hit with perfectly normal markdown: a paragraph full of escaped punctuation, many inline
`code`spans, or many reference-style[ref]links. On my machine (marked.parseat HEAD):'\\.'.repeat(100000)'`x` '.repeat(60000)'[a]: x\n\n' + '[a] '.repeat(100000)The masking regexes match linearly on their own — the cost is purely the repeated
slice+concat rebuild, not the regex. This is the string-rebuild sibling of the em-mask work in #2818 (which fixed the regex side).The fix replaces each hand-rolled loop with a single-pass
String.prototype.replace, so the masked string is built once instead of k times. Every replacement is exactly the same length as what it replaces (reflink →[+a×(len−2) +], escapes →++, blockSkip → context prefix + same-length padding), so the global regex'slastIndexbookkeeping is unaffected and the output is byte-identical — the whole spec suite (CommonMark, GFM, original, redos) passes unchanged. The three inputs above drop to ~5 ms / ~40 ms / ~68 ms and scale linearly.I added
test/specs/redos/quadratic_inline_masking.cjscovering the three shapes; each exceeds the redos harness's 1-second budget onmasterand passes with this change.