Skip to content

Commit c6a25bb

Browse files
spokodevclaude
andauthored
fix: avoid O(n^2) scanning in reflinkSearch (#4090)
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
1 parent a43c064 commit c6a25bb

2 files changed

Lines changed: 43 additions & 2 deletions

File tree

‎src/rules.ts‎

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -466,9 +466,32 @@ const nolink = edit(/^!?\[(ref)\](?:\[\])?/)
466466
.replace('ref', _blockLabel)
467467
.getRegex();
468468

469+
// `reflink` and `nolink` are anchored, so the tokenizer tries each of them at a
470+
// single position. `reflinkSearch` drops the anchors and runs with the global
471+
// flag, which makes every '[' in the source a start position. A label crosses a
472+
// bracket only by escaping it, and nothing caps how often it does, so a
473+
// candidate that can never match still scans to the end of the source and the
474+
// whole pass costs O(n^2).
475+
//
476+
// The labels below bound that scan. `_boundedInlineLabel` limits how many
477+
// escapes, code spans and nested brackets a link text may hold, leaving runs of
478+
// ordinary characters unbounded so link text of any length is still found.
479+
// `_boundedBlockLabel` limits the label itself to 999 items, which is every
480+
// label CommonMark allows: "A link label can have at most 999 characters
481+
// inside the square brackets."
482+
const _boundedBlockLabel = /(?!\s*\])(?:\\[\s\S]|[^\[\]\\]){1,999}/;
483+
const _boundedInlineLabel = edit(/(?:[^\[\]\\`]*(?:\[(?:brackets|\\[\s\S]|[^\[\]\\])*\]|\\[\s\S]|`+(?!`)[^`]*?`+(?!`)|``+(?=\]))){0,999}?[^\[\]\\`]*?/)
484+
.replace('brackets', _inlineLabelBrackets)
485+
.getRegex();
486+
469487
const reflinkSearch = edit('reflink|nolink(?!\\()', 'g')
470-
.replace('reflink', reflink)
471-
.replace('nolink', nolink)
488+
.replace('reflink', edit(/^!?\[(label)\]\[(ref)\]/)
489+
.replace('label', _boundedInlineLabel)
490+
.replace('ref', _boundedBlockLabel)
491+
.getRegex())
492+
.replace('nolink', edit(/^!?\[(ref)\](?:\[\])?/)
493+
.replace('ref', _boundedBlockLabel)
494+
.getRegex())
472495
.getRegex();
473496

474497
const _caseInsensitiveProtocol = /[hH][tT][tT][pP][sS]?|[fF][tT][pP]/;
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
// Regression: `reflinkSearch` is unanchored and runs with the global flag, so
2+
// every '[' in the source is a start position. A label crosses a bracket only
3+
// by escaping it, and nothing capped how often it could, so a candidate that
4+
// can never match still scanned to the end of the source. 188 KB of the first
5+
// shape took 21s to parse with default options.
6+
const escapedBracket = 18000;
7+
const escapedPair = 14000;
8+
9+
module.exports = [
10+
{
11+
markdown: '[' + '\t\\['.repeat(escapedBracket) + '[',
12+
html: `<p>[${'\t['.repeat(escapedBracket)}[</p>`,
13+
},
14+
{
15+
markdown: '[' + '\t\\[\\]'.repeat(escapedPair) + '[',
16+
html: `<p>[${'\t[]'.repeat(escapedPair)}[</p>`,
17+
},
18+
];

0 commit comments

Comments
 (0)