Skip to content

Commit eab1e48

Browse files
DavidDavidDavidcursoragent
authored
fix: avoid quadratic scan for unmatched emphasis delimiters (#4103)
* fix: avoid quadratic scan for unmatched emphasis delimiters Tokenizer.emStrong and del walked every later delimiter for each unmatched opener, so parse time grew ~4x when those inputs doubled. Cache the last possible closer on maskedSrc and skip the scan when none remains after the opener. Fixes #4099 Co-authored-by: David <[email protected]> * fix: keep emphasis closer hints on the inline pass Address review on the unmatched-delimiter scan: remove the timing unit tests, cover mid-run openers in test/specs/new, name the emphasis and strikethrough closer indexes, and drop the module-level maskedSrc cache. Co-authored-by: David <[email protected]> * refactor: scan unmatched emphasis closers in internal helpers Tokenizer no longer gains public methods. The last-closer scan still runs once per inline pass and the hint stack is dropped when that pass ends, so the masked source is not retained. Co-authored-by: David <[email protected]> --------- Co-authored-by: David <[email protected]> Co-authored-by: David <[email protected]> Co-authored-by: Cursor Agent <[email protected]>
1 parent 8babc79 commit eab1e48

6 files changed

Lines changed: 182 additions & 5 deletions

File tree

‎src/Lexer.ts‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
import { _Tokenizer } from './Tokenizer.ts';
22
import { _defaults } from './defaults.ts';
33
import { other, block, inline } from './rules.ts';
4-
import { normalizeLabel } from './helpers.ts';
4+
import { beginEmStrongDelCloserScan, endEmStrongDelCloserScan, normalizeLabel } from './helpers.ts';
55
import type { Token, TokensList, Tokens } from './Tokens.ts';
66
import type { MarkedOptions } from './MarkedOptions.ts';
77

@@ -382,6 +382,18 @@ export class _Lexer<ParserOutput = string, RendererOutput = string> {
382382
? this.#maskSrc(src)
383383
: src;
384384

385+
// One scan of this maskedSrc for the last emphasis, strong, and
386+
// strikethrough closers, shared by every opener in the pass. Popped
387+
// when the pass ends so the source is not retained (#4099).
388+
beginEmStrongDelCloserScan(this.tokenizer, maskedSrc);
389+
try {
390+
return this.#tokenizeInlines(src, maskedSrc, tokens);
391+
} finally {
392+
endEmStrongDelCloserScan(this.tokenizer);
393+
}
394+
}
395+
396+
#tokenizeInlines(src: string, maskedSrc: string, tokens: Token[]): Token[] {
385397
let keepPrevChar = false;
386398
let prevChar = '';
387399
let srcLength = Infinity;

‎src/Tokenizer.ts‎

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@ import {
77
normalizeLabel,
88
decodeNumericCharacterReferences,
99
trimTrailingBlankLines,
10+
cachedLastPossibleEmStrongCloserIndex,
11+
cachedLastPossibleDelCloserIndex,
1012
} from './helpers.ts';
1113
import type { Rules } from './rules.ts';
1214
import type { _Lexer } from './Lexer.ts';
@@ -906,13 +908,18 @@ export class _Tokenizer<ParserOutput = string, RendererOutput = string> {
906908
const runLength = srcStart - runStart + lLength;
907909
const openerCanClose = !this.options.pedantic && !!runPrevChar.trim()
908910
&& (!!nextChar || (delimChar === '*' && !runPrevPunct));
911+
if (delimChar !== '*' && delimChar !== '_') return;
909912
const endReg = delimChar === '*' ? this.rules.inline.emStrongRDelimAst : this.rules.inline.emStrongRDelimUnd;
910-
endReg.lastIndex = 0;
911-
913+
const lastPossibleEmStrongCloserIndex = cachedLastPossibleEmStrongCloserIndex(this, maskedSrc, delimChar);
914+
const emStrongCloserWindowStart = maskedSrc.length - src.length + lLength;
915+
if (lastPossibleEmStrongCloserIndex < emStrongCloserWindowStart) return;
912916
// Clip maskedSrc to same section of string as src (move to lexer?)
913917
maskedSrc = maskedSrc.slice(-1 * src.length + lLength);
918+
const lastPossibleEmStrongCloserIndexInWindow = lastPossibleEmStrongCloserIndex - emStrongCloserWindowStart;
919+
endReg.lastIndex = 0;
914920

915921
while ((match = endReg.exec(maskedSrc)) !== null) {
922+
if (match.index > lastPossibleEmStrongCloserIndexInWindow) break;
916923
rDelim = match[1] || match[2] || match[3] || match[4] || match[5] || match[6];
917924

918925
if (!rDelim) continue; // skip single * in __abc*abc__
@@ -1006,12 +1013,16 @@ export class _Tokenizer<ParserOutput = string, RendererOutput = string> {
10061013
let rDelim, rLength, delimTotal = lLength;
10071014

10081015
const endReg = this.rules.inline.delRDelim;
1009-
endReg.lastIndex = 0;
1010-
1016+
const lastPossibleDelCloserIndex = cachedLastPossibleDelCloserIndex(this, maskedSrc);
1017+
const delCloserWindowStart = maskedSrc.length - src.length + lLength;
1018+
if (lastPossibleDelCloserIndex < delCloserWindowStart) return;
10111019
// Clip maskedSrc to same section of string as src
10121020
maskedSrc = maskedSrc.slice(-1 * src.length + lLength);
1021+
const lastPossibleDelCloserIndexInWindow = lastPossibleDelCloserIndex - delCloserWindowStart;
1022+
endReg.lastIndex = 0;
10131023

10141024
while ((match = endReg.exec(maskedSrc)) !== null) {
1025+
if (match.index > lastPossibleDelCloserIndexInWindow) break;
10151026
rDelim = match[1] || match[2] || match[3] || match[4] || match[5] || match[6];
10161027

10171028
if (!rDelim) continue;

‎src/helpers.ts‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,129 @@ export function findClosingBracket(str: string, b: string) {
186186
return -1;
187187
}
188188

189+
interface LastPossibleEmStrongCloserIndex {
190+
/** Last `*` run that can close emphasis or strong. `-1` if none. */
191+
'*': number;
192+
/** Last `_` run that can close emphasis or strong. `-1` if none. */
193+
_: number;
194+
}
195+
196+
/**
197+
* Closer hints for one inline `maskedSrc`. Held only while that pass runs.
198+
*/
199+
interface EmStrongDelCloserHintFrame {
200+
maskedSrc: string;
201+
lastPossibleEmStrongCloserIndex: LastPossibleEmStrongCloserIndex;
202+
/** Last `~` run that can close strikethrough. `-1` if none. */
203+
lastPossibleDelCloserIndex: number;
204+
}
205+
206+
/**
207+
* Hint stacks for inline passes currently running. Keyed by the tokenizer
208+
* instance so parses do not share frames. Nested `inlineTokens` calls push
209+
* a frame. The entry is removed when the outermost pass ends, so
210+
* `maskedSrc` is not retained once parsing returns (#4099).
211+
*/
212+
const emStrongDelCloserHintStacks = new WeakMap<object, EmStrongDelCloserHintFrame[]>();
213+
214+
/**
215+
* Last indexes of `*` / `_` runs that can close emphasis or strong, and of
216+
* a `~` run that can close strikethrough.
217+
*
218+
* A run can close only when it is not preceded by ASCII whitespace or the
219+
* start of the string. The right-delim regexes accept a closer only in
220+
* groups 1, 2, 5, and 6, and each of those requires that predecessor. When
221+
* the opener's window has no such run, the regex scan cannot succeed.
222+
* Finding one only means "keep looking": CommonMark rules 9–10 and mid-run
223+
* openers are still applied in the loop (#4099).
224+
*/
225+
function scanLastPossibleEmStrongDelClosers(src: string): EmStrongDelCloserHintFrame {
226+
const lastPossibleEmStrongCloserIndex: LastPossibleEmStrongCloserIndex = { '*': -1, _: -1 };
227+
let lastPossibleDelCloserIndex = -1;
228+
const len = src.length;
229+
for (let i = 0; i < len; i++) {
230+
const ch = src[i];
231+
if (ch !== '*' && ch !== '_' && ch !== '~') {
232+
continue;
233+
}
234+
// A leading run has no predecessor, same as one after a line break.
235+
const prev = i === 0 ? '\n' : src[i - 1];
236+
let j = i + 1;
237+
while (j < len && src[j] === ch) {
238+
j++;
239+
}
240+
if (prev !== ' ' && prev !== '\t' && prev !== '\n' && prev !== '\r' && prev !== '\f') {
241+
if (ch === '~') {
242+
lastPossibleDelCloserIndex = i;
243+
} else {
244+
lastPossibleEmStrongCloserIndex[ch] = i;
245+
}
246+
}
247+
i = j - 1;
248+
}
249+
return {
250+
maskedSrc: src,
251+
lastPossibleEmStrongCloserIndex,
252+
lastPossibleDelCloserIndex,
253+
};
254+
}
255+
256+
/**
257+
* Scan `maskedSrc` once for the last `*` / `_` run that can close emphasis
258+
* or strong and the last `~` run that can close strikethrough.
259+
* `endEmStrongDelCloserScan` drops this frame when the inline pass ends.
260+
*/
261+
export function beginEmStrongDelCloserScan(tokenizer: object, maskedSrc: string): void {
262+
const frame = scanLastPossibleEmStrongDelClosers(maskedSrc);
263+
const stack = emStrongDelCloserHintStacks.get(tokenizer);
264+
if (stack) {
265+
stack.push(frame);
266+
} else {
267+
emStrongDelCloserHintStacks.set(tokenizer, [frame]);
268+
}
269+
}
270+
271+
/**
272+
* Drop the closer-hint frame for the inline pass that just finished.
273+
* Removing the last frame drops the tokenizer's `maskedSrc` reference.
274+
*/
275+
export function endEmStrongDelCloserScan(tokenizer: object): void {
276+
const stack = emStrongDelCloserHintStacks.get(tokenizer);
277+
if (!stack) {
278+
return;
279+
}
280+
stack.pop();
281+
if (stack.length === 0) {
282+
emStrongDelCloserHintStacks.delete(tokenizer);
283+
}
284+
}
285+
286+
/**
287+
* Index in `maskedSrc` of the last `*` or `_` run that can close emphasis
288+
* or strong. Uses the active inline-pass scan when `maskedSrc` is that
289+
* pass's source; otherwise scans this string and discards the result.
290+
*/
291+
export function cachedLastPossibleEmStrongCloserIndex(tokenizer: object, maskedSrc: string, delim: '*' | '_'): number {
292+
const frame = emStrongDelCloserHintStacks.get(tokenizer)?.at(-1);
293+
if (frame && frame.maskedSrc === maskedSrc) {
294+
return frame.lastPossibleEmStrongCloserIndex[delim];
295+
}
296+
return scanLastPossibleEmStrongDelClosers(maskedSrc).lastPossibleEmStrongCloserIndex[delim];
297+
}
298+
299+
/**
300+
* Index in `maskedSrc` of the last `~` run that can close strikethrough.
301+
* Uses the active inline-pass scan when `maskedSrc` is that pass's
302+
* source; otherwise scans this string and discards the result.
303+
*/
304+
export function cachedLastPossibleDelCloserIndex(tokenizer: object, maskedSrc: string): number {
305+
const frame = emStrongDelCloserHintStacks.get(tokenizer)?.at(-1);
306+
if (frame && frame.maskedSrc === maskedSrc) {
307+
return frame.lastPossibleDelCloserIndex;
308+
}
309+
return scanLastPossibleEmStrongDelClosers(maskedSrc).lastPossibleDelCloserIndex;
310+
}
311+
189312
export function expandTabs(line: string, indent = 0) {
190313
let col = indent;
191314
let expanded = '';
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
<p>**a<em>b</em>c</p>
2+
3+
<p><em>foo**bar</em></p>
4+
5+
<p>*foo <em>bar</em></p>
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
**a*b*c
2+
3+
*foo**bar*
4+
5+
*foo *bar*
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// Unmatched left-flanking emphasis / strikethrough delimiters. Before the
2+
// last-closer early-exit, each opener walked every later delimiter
3+
// (issue #4099). These sizes exceed the spec harness 1s budget on that path.
4+
module.exports = [
5+
{
6+
markdown: ('- *').repeat(2000),
7+
html: `<ul>\n<li>${'*- '.repeat(1999)}*</li>\n</ul>\n`,
8+
},
9+
{
10+
markdown: ('+ _').repeat(2000),
11+
html: `<ul>\n<li>${'_+ '.repeat(1999)}_</li>\n</ul>\n`,
12+
},
13+
{
14+
markdown: ('*x *x ').repeat(2000),
15+
html: `<p>${'*x *x '.repeat(2000)}</p>\n`,
16+
},
17+
{
18+
markdown: ('~x ~x ').repeat(2000),
19+
html: `<p>${'~x ~x '.repeat(2000)}</p>\n`,
20+
},
21+
];

0 commit comments

Comments
 (0)