Skip to content

Commit 9c57ab6

Browse files
saphidcodex
andcommitted
perf(web): avoid quadratic markdown link scans
Scan link labels and reuse destination delimiter searches so unfinished streamed markdown does not repeatedly scan overlapping suffixes. Preserve existing destinations, quoted titles, and malformed-link fallback behavior. Co-Authored-By: GPT-6.1 Sol <[email protected]>
1 parent aaf83ee commit 9c57ab6

2 files changed

Lines changed: 86 additions & 4 deletions

File tree

‎packages/shared/src/markdownLinks.test.ts‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -222,6 +222,25 @@ describe("isWindowsDrivePathHref", () => {
222222
});
223223

224224
describe("extractMarkdownLinkHrefs", () => {
225+
it.each([
226+
["[".repeat(32_000), []],
227+
["[](a".repeat(16_000), []],
228+
["[](<a".repeat(16_000), []],
229+
["[x](https://e.com/".repeat(8_000), []],
230+
["[a](<foo)bar> invalid [b](ok)", ["<foo", "ok"]],
231+
["[a](foo \"mixed title') [b](< >)", ["foo"]],
232+
["[a](<one [b](two)> invalid [c](ok)", ["two", "ok"]],
233+
["```text\n" + "[unfinished item\n".repeat(8_000) + "```", []],
234+
["[[[nested](src/main.ts) [unfinished", ["src/main.ts"]],
235+
["[outer [inner] invalid [valid](src/main.ts)", ["src/main.ts"]],
236+
["[bad](missing title [valid](src/main.ts)", ["src/main.ts"]],
237+
["```text\n[link](src/main.ts)\n```", ["src/main.ts"]],
238+
["[empty]() [valid](src/main.ts 'title')", ["src/main.ts"]],
239+
['[angle](<src/My File.ts> "title")', ["src/My File.ts"]],
240+
])("extracts links from incomplete and nested text", (markdown, hrefs) => {
241+
expect(extractMarkdownLinkHrefs(markdown)).toEqual(hrefs);
242+
});
243+
225244
it("extracts angle-bracketed paths containing spaces", () => {
226245
expect(
227246
extractMarkdownLinkHrefs(

‎packages/shared/src/markdownLinks.ts‎

Lines changed: 67 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -322,13 +322,76 @@ export function extractInlineCodeSpans(text: string): string[] {
322322
return spans;
323323
}
324324

325-
const MARKDOWN_LINK_HREF_PATTERN =
326-
/\[[^\]]*]\(\s*(?:<([^>\n]+)>|([^\s)]+))(?:\s+["'][^"']*["'])?\s*\)/g;
325+
/** Reuses delimiter searches when successive candidates fall in the same run. */
326+
function markdownRunEndFinder(markdown: string, delimiter: RegExp) {
327+
let runStart = -1;
328+
let runEnd = -1;
329+
return (start: number) => {
330+
if (start >= runStart && start <= runEnd) return runEnd;
331+
delimiter.lastIndex = start;
332+
runStart = start;
333+
runEnd = delimiter.exec(markdown)?.index ?? markdown.length;
334+
return runEnd;
335+
};
336+
}
337+
338+
function markdownLinkTailScanner(markdown: string) {
339+
const whitespaceEnd = markdownRunEndFinder(markdown, /\S/g);
340+
const titleEnd = markdownRunEndFinder(markdown, /["']/g);
341+
const titleWhitespaceEnd = markdownRunEndFinder(markdown, /\S/g);
342+
return (start: number) => {
343+
const end = whitespaceEnd(start);
344+
if (markdown[end] === ")") return end + 1;
345+
if (end === start || (markdown[end] !== '"' && markdown[end] !== "'")) return null;
346+
const quoteEnd = titleEnd(end + 1);
347+
if (quoteEnd === markdown.length) return null;
348+
const close = titleWhitespaceEnd(quoteEnd + 1);
349+
return markdown[close] === ")" ? close + 1 : null;
350+
};
351+
}
352+
353+
function markdownLinkDestinationScanner(markdown: string) {
354+
const whitespaceEnd = markdownRunEndFinder(markdown, /\S/g);
355+
const angleEnd = markdownRunEndFinder(markdown, /[>\n]/g);
356+
const bareEnd = markdownRunEndFinder(markdown, /[\s)]/g);
357+
// Separate caches keep each branch's searches moving forward even when an
358+
// angle destination fails and falls back to an ordinary destination.
359+
const angleTail = markdownLinkTailScanner(markdown);
360+
const bareTail = markdownLinkTailScanner(markdown);
361+
return (start: number) => {
362+
if (markdown[start] !== "(") return null;
363+
const hrefStart = whitespaceEnd(start + 1);
364+
if (markdown[hrefStart] === "<") {
365+
const hrefEnd = angleEnd(hrefStart + 1);
366+
if (hrefEnd > hrefStart + 1 && markdown[hrefEnd] === ">") {
367+
const end = angleTail(hrefEnd + 1);
368+
if (end !== null) return { hrefStart: hrefStart + 1, hrefEnd, end };
369+
}
370+
}
371+
const hrefEnd = bareEnd(hrefStart);
372+
if (hrefEnd === hrefStart) return null;
373+
const end = bareTail(hrefEnd);
374+
return end === null ? null : { hrefStart, hrefEnd, end };
375+
};
376+
}
327377

328378
export function extractMarkdownLinkHrefs(markdown: string): string[] {
329379
const hrefs: string[] = [];
330-
for (const match of markdown.matchAll(MARKDOWN_LINK_HREF_PATTERN)) {
331-
const href = (match[1] ?? match[2])?.trim();
380+
const scanDestination = markdownLinkDestinationScanner(markdown);
381+
let cursor = 0;
382+
while (cursor < markdown.length) {
383+
const labelStart = markdown.indexOf("[", cursor);
384+
if (labelStart === -1) break;
385+
const labelEnd = markdown.indexOf("]", labelStart + 1);
386+
if (labelEnd === -1) break;
387+
388+
// Nested opening brackets share this closing bracket. On failure, skip the
389+
// whole label instead of rescanning its suffix from each opening bracket.
390+
cursor = labelEnd + 1;
391+
const destination = scanDestination(cursor);
392+
if (!destination) continue;
393+
cursor = destination.end;
394+
const href = markdown.slice(destination.hrefStart, destination.hrefEnd).trim();
332395
if (href) hrefs.push(href);
333396
}
334397
return hrefs;

0 commit comments

Comments
 (0)