1/**
2 * Incremental parser for predicting closing tags in Markdown text. Works best
3 * when continuously appending text to the end of the string; this behavior
4 * specifically triggers a fast parsing path.
5 */
6export class Predict {
7 /** @internal Read-only state indicating the stable string */
8 #stable = "";
9 /** Incrementally reparses the tail. */
10 update(text: string): string {
11 if (!text.startsWith(this.#stable)) this.#stable = "";
12 let tail = text.slice(this.#stable.length);
13 let state = parseTail(tail);
14 if (state.commitIndex > 0) {
15 this.#stable += tail.slice(0, state.commitIndex);
16 tail = tail.slice(state.commitIndex);
17 state = parseTail(tail);
18 }
19 return this.#stable + renderTail(tail, state);
20 }
21}
22
23type DelimToken = "***" | "**" | "__" | "~~" | "*" | "_";
24type DelimState = { start: number; token: DelimToken };
25type LinkState =
26 | { phase: "text"; start: number }
27 | { phase: "url_wait"; start: number; textEnd: number }
28 | { phase: "url"; start: number; textEnd: number; parenDepth: number };
29type ExclusiveState =
30 | { kind: "code"; start: number; token: string }
31 | { kind: "fence"; start: number; token: string }
32 | { kind: "math"; start: number; token: "$" | "$$" };
33interface TailState {
34 commitIndex: number;
35 delims: DelimState[];
36 exclusive: ExclusiveState | null;
37 links: LinkState[];
38 pendingDelim: DelimState | null;
39 pendingHtml: number | null;
40}
41
42const NESTABLE_DELIMS = new Set<DelimToken>(["*", "**", "_", "__"]);
43
44function parseTail(tail: string): TailState {
45 const state: TailState = {
46 commitIndex: 0,
47 delims: [],
48 exclusive: null,
49 links: [],
50 pendingDelim: null,
51 pendingHtml: null,
52 };
53 for (let i = 0; i < tail.length; i++) {
54 const char = tail[i]!;
55 if (char === "\n" && tail[i - 1] === "\n") {
56 resetParagraphState(state);
57 if (!state.exclusive) state.commitIndex = i + 1;
58 continue;
59 }
60
61 const exclusiveEnd = consumeExclusive(state, tail, i);
62 if (exclusiveEnd > i) {
63 i = exclusiveEnd - 1;
64 continue;
65 }
66 if (state.exclusive) continue;
67
68 if (inLinkUrlMode(state)) {
69 updateLink(state, i, char);
70 continue;
71 }
72 const htmlEnd = consumeHtml(state, tail, i);
73 if (htmlEnd > i) {
74 i = htmlEnd - 1;
75 continue;
76 }
77 const delimEnd = consumeDelim(state, tail, i);
78 if (delimEnd > i) {
79 i = delimEnd - 1;
80 continue;
81 }
82 if (isEscapedAt(tail, i)) continue;
83 updateLink(state, i, char);
84 }
85 return state;
86}
87
88function consumeExclusive(state: TailState, tail: string, start: number) {
89 const char = tail[start];
90 if (char === "`") return consumeBackticks(state, tail, start);
91 if (char === "$") return consumeMath(state, tail, start);
92 if (char === "~") return consumeTildes(state, tail, start);
93 return start;
94}
95
96function consumeBackticks(state: TailState, tail: string, start: number) {
97 const length = runLengthAt(tail, start);
98 const token = "`".repeat(length);
99 const exclusive = state.exclusive;
100 if (exclusive?.kind === "fence") {
101 if (
102 exclusive.token[0] === "`" &&
103 isLineStart(tail, start) &&
104 !isEscapedAt(tail, start) &&
105 length >= exclusive.token.length
106 ) {
107 state.exclusive = null;
108 }
109 return start + length;
110 }
111 if (exclusive?.kind === "code") {
112 if (!isEscapedAt(tail, start) && length >= exclusive.token.length) {
113 state.exclusive = null;
114 }
115 return start + length;
116 }
117 if (exclusive) return start + length;
118 if (isEscapedAt(tail, start)) return start + length;
119 if (length >= 3 && isLineStart(tail, start)) {
120 state.exclusive = { kind: "fence", start, token };
121 return start + length;
122 }
123 state.exclusive = { kind: "code", start, token };
124 return start + length;
125}
126
127function consumeMath(state: TailState, tail: string, start: number) {
128 const length = runLengthAt(tail, start);
129 const exclusive = state.exclusive;
130 if (exclusive?.kind === "math") {
131 if (!isEscapedAt(tail, start) && length >= exclusive.token.length) {
132 state.exclusive = null;
133 }
134 return start + length;
135 }
136 if (exclusive) return start + length;
137 if (isEscapedAt(tail, start)) return start + length;
138 state.exclusive = {
139 kind: "math",
140 start,
141 token: length >= 2 ? "$$" : "$",
142 };
143 return start + length;
144}
145
146function consumeTildes(state: TailState, tail: string, start: number) {
147 const length = runLengthAt(tail, start);
148 const exclusive = state.exclusive;
149 if (exclusive?.kind === "fence" && exclusive.token[0] === "~") {
150 if (isLineStart(tail, start) && !isEscapedAt(tail, start) && length >= exclusive.token.length) {
151 state.exclusive = null;
152 }
153 return start + length;
154 }
155 if (exclusive) return start;
156 if (length < 3 || !isLineStart(tail, start) || isEscapedAt(tail, start)) return start;
157 state.exclusive = { kind: "fence", start, token: "~".repeat(length) };
158 return start + length;
159}
160
161function consumeHtml(state: TailState, tail: string, start: number) {
162 if (tail[start] !== "<" || isEscapedAt(tail, start)) return start;
163 const next = tail[start + 1];
164 if (next !== undefined && !isAsciiLetter(next)) return start;
165 state.pendingHtml = start;
166 for (let i = start + 1; i < tail.length; i++) {
167 if (tail[i] === ">" || tail[i] === "\n") {
168 state.pendingHtml = null;
169 return i + 1;
170 }
171 }
172 return tail.length;
173}
174
175function consumeDelim(state: TailState, tail: string, start: number) {
176 const token = matchDelim(tail, start);
177 if (!token) return start;
178 if (isEscapedAt(tail, start)) return start + token.length;
179 const existingIndex = state.delims.findLastIndex((delim) => delim.token === token);
180 if (existingIndex !== -1) {
181 state.delims.splice(existingIndex, 1);
182 return start + token.length;
183 }
184 if (start + token.length === tail.length) {
185 state.pendingDelim = { start, token };
186 return start + token.length;
187 }
188 if (!canOpenDelim(tail, start, token)) return start + token.length;
189 state.delims.push({ start, token });
190 return start + token.length;
191}
192
193function matchDelim(tail: string, start: number): DelimToken | undefined {
194 const char = tail[start];
195 if (char === "*") {
196 if (tail.startsWith("***", start)) return "***";
197 if (tail.startsWith("**", start)) return "**";
198 return "*";
199 }
200 if (char === "_") {
201 if (tail.startsWith("__", start)) return "__";
202 return "_";
203 }
204 if (char === "~" && tail.startsWith("~~", start)) {
205 return "~~";
206 }
207}
208
209function canOpenDelim(tail: string, start: number, token: DelimToken) {
210 const next = tail[start + token.length];
211 if (!next || /\s/.test(next)) return false;
212 const prev = tail[start - 1];
213 return !isWordChar(prev) || !isWordChar(next);
214}
215
216function updateLink(state: TailState, index: number, char: string) {
217 const top = state.links.at(-1);
218 if (char === "[") {
219 state.links.push({ phase: "text", start: index });
220 return;
221 }
222 if (char === "]" && top?.phase === "text") {
223 state.links[state.links.length - 1] = {
224 phase: "url_wait",
225 start: top.start,
226 textEnd: index,
227 };
228 return;
229 }
230 if (char === "(" && top?.phase === "url_wait") {
231 state.links[state.links.length - 1] = {
232 phase: "url",
233 start: top.start,
234 textEnd: top.textEnd,
235 parenDepth: 0,
236 };
237 return;
238 }
239 if (char === "(" && top?.phase === "url") {
240 top.parenDepth += 1;
241 return;
242 }
243 if (char === ")" && top?.phase === "url") {
244 if (top.parenDepth > 0) {
245 top.parenDepth -= 1;
246 return;
247 }
248 state.links.pop();
249 }
250}
251
252function resetParagraphState(state: TailState) {
253 state.delims.length = 0;
254 state.links.length = 0;
255 if (state.exclusive?.kind === "fence") return;
256 if (state.exclusive?.kind === "math" && state.exclusive.token === "$$") return;
257 state.exclusive = null;
258}
259
260function inLinkUrlMode(state: TailState) {
261 const phase = state.links.at(-1)?.phase;
262 return phase === "url_wait" || phase === "url";
263}
264
265function renderTail(tail: string, state: TailState) {
266 if (state.pendingHtml !== null)
267 tail = tail.slice(0, findPendingHtmlCutoff(tail, state.pendingHtml));
268 const link = state.links.at(-1);
269 if (link) {
270 return maybePredictTable(renderOpenLink(tail, link));
271 }
272 const nestedClosers = renderNestedClosers(state);
273 if (nestedClosers) {
274 return maybePredictTable(appendCloser(tail, nestedClosers));
275 }
276 const open = findLastOpen(state);
277 if (!open) {
278 return maybePredictTable(state.pendingDelim ? tail.slice(0, state.pendingDelim.start) : tail);
279 } else if (open.kind === "delim") {
280 return maybePredictTable(
281 hasContentAfter(tail, open.start, open.token.length)
282 ? appendCloserBeforeTrailingInlineWhitespace(tail, open.token)
283 : tail.slice(0, open.start),
284 );
285 } else if (!hasContentAfter(tail, open.start, open.token.length)) {
286 return maybePredictTable(open.kind === "fence" ? tail : tail.slice(0, open.start));
287 } else if (open.kind === "fence") {
288 return maybePredictTable(tail);
289 } else if (open.kind === "code") {
290 return maybePredictTable(appendCloser(tail, open.token));
291 } else if (open.token === "$$") {
292 return maybePredictTable(appendCloser(tail, (tail.endsWith("\n") ? "" : "\n") + "$$"));
293 } else if (/\s/.test(tail[tail.length - 1] ?? "")) {
294 return maybePredictTable(tail);
295 } else {
296 return maybePredictTable(appendCloser(tail, "$"));
297 }
298}
299
300function renderOpenLink(tail: string, state: LinkState) {
301 const before = tail.slice(0, state.start);
302 if (state.phase === "text") {
303 if (!hasContentAfter(tail, state.start, 1)) return before;
304 return before + tail.slice(state.start + 1);
305 }
306 const text = tail.slice(state.start + 1, state.textEnd);
307 if (state.phase === "url_wait") return before + text + tail.slice(state.textEnd + 1);
308 return before + text;
309}
310
311function renderNestedClosers(state: TailState) {
312 const closers: string[] = [];
313 if (state.exclusive) {
314 if (state.exclusive.kind !== "code") return undefined;
315 closers.push(state.exclusive.token);
316 }
317 for (let i = state.delims.length - 1; i >= 0; i--) {
318 const token = state.delims[i]!.token;
319 if (!NESTABLE_DELIMS.has(token)) return undefined;
320 closers.push(token);
321 }
322 if (closers.length < 2) return undefined;
323 return closers.join("");
324}
325
326function findPendingHtmlCutoff(tail: string, pendingStart: number) {
327 let cutoff = pendingStart;
328 let cursor = pendingStart;
329
330 while (cursor > 0) {
331 const candidateStart = tail.lastIndexOf("<", cursor - 1);
332 if (candidateStart === -1) break;
333 if (!isCompleteHtmlTag(tail, candidateStart, cursor)) break;
334 cutoff = candidateStart;
335 cursor = candidateStart;
336 }
337
338 return cutoff;
339}
340
341function isCompleteHtmlTag(tail: string, start: number, end: number) {
342 if (tail[end - 1] !== ">") return false;
343 if (isEscapedAt(tail, start)) return false;
344 const next = tail[start + 1];
345 if (next !== undefined && !isAsciiLetter(next)) return false;
346 for (let i = start + 1; i < end - 1; i++) {
347 const char = tail[i];
348 if (char === ">" || char === "\n") return false;
349 }
350 return true;
351}
352
353function maybePredictTable(text: string) {
354 const lastBlankLine = text.lastIndexOf("\n\n");
355 const blockStart = lastBlankLine === -1 ? 0 : lastBlankLine + 2;
356 const before = text.slice(0, blockStart);
357 const block = text.slice(blockStart);
358 const newline = block.indexOf("\n");
359 const header = newline === -1 ? block : block.slice(0, newline);
360 const indent = header.match(/^( *)\|/)?.[1];
361 if (indent === undefined) return text;
362 if (countPipes(header) < 2 && !hasTableHeaderContent(header, indent)) return before;
363 const fullHeader = header.trimEnd().endsWith("|")
364 ? header
365 : appendCloserBeforeTrailingInlineWhitespace(header, " |");
366 const pipeCount = countPipes(fullHeader);
367 const columns =
368 pipeCount < 2 ? 0 : fullHeader.trimEnd().endsWith("|") ? pipeCount - 1 : pipeCount;
369 if (columns === 0) return text;
370 const rest = newline === -1 ? "" : block.slice(newline + 1);
371 const fullDelimiter = renderTableDelimiter(
372 indent,
373 Array.from({ length: columns }, () => "-"),
374 );
375 if (rest.length === 0) return before + fullHeader + "\n" + fullDelimiter;
376 const delimiterEnd = rest.indexOf("\n");
377 const delimiter = delimiterEnd === -1 ? rest : rest.slice(0, delimiterEnd);
378 const afterDelimiter = delimiterEnd === -1 ? "" : rest.slice(delimiterEnd);
379 if (isCompleteTableDelimiter(delimiter, indent, columns)) return text;
380 if (delimiter.startsWith(indent + "|") && /^[ |:\-\t]*$/.test(delimiter.slice(indent.length))) {
381 const cells = parseTableDelimiterCells(delimiter, indent).map((cell) => {
382 const trimmed = cell.trim();
383 if (trimmed.length === 0) return "-";
384 let hyphenCount = 0;
385 for (let i = 0; i < trimmed.length; i++) if (trimmed.charCodeAt(i) === 0x2d) hyphenCount++;
386 return (
387 (trimmed.startsWith(":") ? ":" : "") +
388 "-".repeat(Math.max(1, hyphenCount)) +
389 (trimmed.length > 1 && trimmed.endsWith(":") ? ":" : "")
390 );
391 });
392 while (cells.length < columns) cells.push("-");
393 return before + fullHeader + "\n" + renderTableDelimiter(indent, cells) + afterDelimiter;
394 }
395 return before + fullHeader + "\n" + fullDelimiter + "\n" + rest;
396}
397
398function appendCloser(tail: string, closer: string) {
399 return tail + closer.slice(overlapLength(tail, closer));
400}
401
402function appendCloserBeforeTrailingInlineWhitespace(tail: string, closer: string) {
403 const trailingWhitespace = tail.match(/[^\S\n]+$/)?.[0];
404 if (!trailingWhitespace) return appendCloser(tail, closer);
405 const body = tail.slice(0, -trailingWhitespace.length);
406 return appendCloser(body, closer) + trailingWhitespace;
407}
408
409function overlapLength(tail: string, closer: string) {
410 for (let length = Math.min(tail.length, closer.length); length > 0; length -= 1) {
411 if (tail.endsWith(closer.slice(0, length))) return length;
412 }
413 return 0;
414}
415
416function findLastOpen(state: TailState) {
417 const delim = state.delims.at(-1);
418 if (state.exclusive && (!delim || state.exclusive.start > delim.start)) return state.exclusive;
419 if (delim) return { kind: "delim" as const, start: delim.start, token: delim.token };
420 return state.exclusive;
421}
422
423function countPipes(text: string) {
424 let count = 0;
425 for (let i = 0; i < text.length; i++) if (text.charCodeAt(i) === 0x7c) count++;
426 return count;
427}
428
429function hasTableHeaderContent(header: string, indent: string) {
430 return header.slice(indent.length + 1).trim().length > 0;
431}
432
433function renderTableDelimiter(indent: string, cells: string[]) {
434 return indent + "|" + cells.map((cell) => ` ${cell} |`).join("");
435}
436
437function parseTableDelimiterCells(line: string, indent: string) {
438 const cells = line.slice(indent.length + 1).split("|");
439 if (line.trimEnd().endsWith("|")) cells.pop();
440 return cells;
441}
442
443function isCompleteTableDelimiter(line: string, indent: string, columns: number) {
444 if (!line.startsWith(indent)) return false;
445 const trimmed = line.slice(indent.length).trim();
446 if (!trimmed.startsWith("|") || !trimmed.endsWith("|")) return false;
447 const cells = parseTableDelimiterCells(trimmed, "").map((cell) => cell.trim());
448 return cells.length === columns && cells.every((cell) => /^:?-+:?$/.test(cell));
449}
450
451function runLengthAt(text: string, start: number) {
452 let end = start + 1;
453 while (end < text.length && text[end] === text[start]) end += 1;
454 return end - start;
455}
456
457function hasContentAfter(text: string, start: number, tokenLength: number) {
458 return text.length > start + tokenLength;
459}
460
461function isLineStart(text: string, index: number) {
462 return index === 0 || text[index - 1] === "\n";
463}
464
465function isEscapedAt(text: string, index: number) {
466 let count = 0;
467 for (let i = index - 1; i >= 0; i--) {
468 if (text[i] !== "\\") break;
469 count += 1;
470 }
471 return count % 2 === 1;
472}
473
474function isWordChar(char?: string) {
475 return !!char && /[A-Za-z0-9]/.test(char);
476}
477
478function isAsciiLetter(char?: string) {
479 return !!char && /[A-Za-z]/.test(char);
480}