Skip to content

Commit 627d9ae

Browse files
authored
fix: make walkTokens linear by appending values in place (#4121)
* fix: make walkTokens linear by appending values in place Marked.walkTokens collected callback results with `values = values.concat(...)` for every token, copying the whole array each time, so parsing with any walkTokens extension took quadratic time in document size. Append in place instead, flattening one level like concat did, so the returned values are unchanged. The combined walkTokens function built in use() gets the same change. Fixes #4120 * fix: copy walkTokens callback arrays by index like concat
1 parent 4bd2528 commit 627d9ae

2 files changed

Lines changed: 123 additions & 9 deletions

File tree

‎src/Instance.ts‎

Lines changed: 22 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,19 @@ export type MaybePromise = void | Promise<void>;
1414
type UnknownFunction = (...args: unknown[]) => unknown;
1515
type GenericRendererFunction = (...args: unknown[]) => string | false;
1616

17+
/**
18+
* Append value(s) to values in place, flattening one level like concat
19+
*/
20+
function pushValues(values: MaybePromise[], value: MaybePromise | MaybePromise[]) {
21+
if (Array.isArray(value)) {
22+
for (let i = 0; i < value.length; i++) {
23+
values.push(value[i]);
24+
}
25+
} else {
26+
values.push(value);
27+
}
28+
}
29+
1730
export class Marked<ParserOutput = string, RendererOutput = string> {
1831
defaults = _getDefaults<ParserOutput, RendererOutput>();
1932
options = this.setOptions;
@@ -49,36 +62,36 @@ export class Marked<ParserOutput = string, RendererOutput = string> {
4962
* Run callback for every token
5063
*/
5164
walkTokens(tokens: Token[] | TokensList, callback: (token: Token) => MaybePromise | MaybePromise[]) {
52-
let values: MaybePromise[] = [];
65+
const values: MaybePromise[] = [];
5366
for (const token of tokens) {
54-
values = values.concat(callback.call(this, token));
67+
pushValues(values, callback.call(this, token));
5568
switch (token.type) {
5669
case 'table': {
5770
const tableToken = token as Tokens.Table;
5871
for (const cell of tableToken.header) {
59-
values = values.concat(this.walkTokens(cell.tokens, callback));
72+
pushValues(values, this.walkTokens(cell.tokens, callback));
6073
}
6174
for (const row of tableToken.rows) {
6275
for (const cell of row) {
63-
values = values.concat(this.walkTokens(cell.tokens, callback));
76+
pushValues(values, this.walkTokens(cell.tokens, callback));
6477
}
6578
}
6679
break;
6780
}
6881
case 'list': {
6982
const listToken = token as Tokens.List;
70-
values = values.concat(this.walkTokens(listToken.items, callback));
83+
pushValues(values, this.walkTokens(listToken.items, callback));
7184
break;
7285
}
7386
default: {
7487
const genericToken = token as Tokens.Generic;
7588
if (this.defaults.extensions?.childTokens?.[genericToken.type]) {
7689
this.defaults.extensions.childTokens[genericToken.type].forEach((childTokens) => {
7790
const tokens = genericToken[childTokens].flat(Infinity) as Token[] | TokensList;
78-
values = values.concat(this.walkTokens(tokens, callback));
91+
pushValues(values, this.walkTokens(tokens, callback));
7992
});
8093
} else if (genericToken.tokens) {
81-
values = values.concat(this.walkTokens(genericToken.tokens, callback));
94+
pushValues(values, this.walkTokens(genericToken.tokens, callback));
8295
}
8396
}
8497
}
@@ -266,10 +279,10 @@ export class Marked<ParserOutput = string, RendererOutput = string> {
266279
const walkTokens = this.defaults.walkTokens;
267280
const packWalktokens = pack.walkTokens;
268281
opts.walkTokens = function(token) {
269-
let values: MaybePromise[] = [];
282+
const values: MaybePromise[] = [];
270283
values.push(packWalktokens.call(this, token));
271284
if (walkTokens) {
272-
values = values.concat(walkTokens.call(this, token));
285+
pushValues(values, walkTokens.call(this, token));
273286
}
274287
return values;
275288
};

‎test/unit/marked.test.js‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1083,6 +1083,107 @@ br
10831083
]);
10841084
});
10851085

1086+
it('should return callback values in walk order', () => {
1087+
const tokens = lexer('| a | b |\n|---|---|\n| c | d |\n\n- e\n - *f*\n', getDefaults());
1088+
const values = walkTokens(tokens, (token) => {
1089+
if (token.type === 'space') {
1090+
return undefined;
1091+
}
1092+
if (token.type === 'text' && !token.tokens) {
1093+
return [token.raw, [token.raw]];
1094+
}
1095+
return token.type;
1096+
});
1097+
1098+
assert.deepEqual(values, [
1099+
'table',
1100+
'a', ['a'],
1101+
'b', ['b'],
1102+
'c', ['c'],
1103+
'd', ['d'],
1104+
undefined,
1105+
'list',
1106+
'list_item',
1107+
'text',
1108+
'e', ['e'],
1109+
'list',
1110+
'list_item',
1111+
'text',
1112+
'em',
1113+
'f', ['f'],
1114+
]);
1115+
});
1116+
1117+
it('should return callback values from extension childTokens', () => {
1118+
marked.use({
1119+
extensions: [{
1120+
name: 'dl',
1121+
level: 'block',
1122+
childTokens: ['dt', 'dd'],
1123+
tokenizer(src) {
1124+
const match = /^:(.+) \| (.+)\n?/.exec(src);
1125+
if (match) {
1126+
return {
1127+
type: 'dl',
1128+
raw: match[0],
1129+
dt: this.lexer.inlineTokens(match[1]),
1130+
dd: [this.lexer.inlineTokens(match[2])],
1131+
};
1132+
}
1133+
},
1134+
}],
1135+
});
1136+
const tokens = marked.lexer(':term | **def**');
1137+
const values = marked.walkTokens(tokens, (token) => [token.type]);
1138+
1139+
assert.deepEqual(values, ['dl', 'text', 'strong', 'text']);
1140+
});
1141+
1142+
it('should return values from every walkTokens extension', () => {
1143+
marked.use(
1144+
{ walkTokens: () => 'one' },
1145+
{ walkTokens: () => 'two' },
1146+
{ walkTokens: () => 'three' },
1147+
);
1148+
const tokens = marked.lexer('*em*');
1149+
const values = marked.walkTokens(tokens, marked.defaults.walkTokens);
1150+
1151+
assert.deepEqual(values, [
1152+
'three', 'two', 'one', // paragraph
1153+
'three', 'two', 'one', // em
1154+
'three', 'two', 'one', // text
1155+
]);
1156+
});
1157+
1158+
it('should wait for async `walkTokens` on nested tokens', async() => {
1159+
marked.use({
1160+
async: true,
1161+
async walkTokens(token) {
1162+
if (token.type === 'text' && !token.tokens) {
1163+
await timeout();
1164+
token.text = token.text.toUpperCase();
1165+
}
1166+
},
1167+
});
1168+
const html = await marked.parse('| a | b |\n|---|---|\n| c | d |\n\n- e\n - *f*\n\n> g\n');
1169+
1170+
assert.strictEqual(html, new Marked().parse('| A | B |\n|---|---|\n| C | D |\n\n- E\n - *F*\n\n> G\n'));
1171+
});
1172+
1173+
it('should copy returned arrays by index like concat', async() => {
1174+
const tokens = marked.lexer('before');
1175+
const pending = timeout().then(() => {
1176+
tokens[0].tokens[0].text = 'after';
1177+
});
1178+
const results = [pending];
1179+
Object.defineProperty(results, Symbol.iterator, { value: function * () {} });
1180+
const values = marked.walkTokens(tokens, (token) => token.type === 'paragraph' ? results : undefined);
1181+
1182+
assert.deepEqual(values, [pending, undefined]);
1183+
await Promise.all(values);
1184+
assert.strictEqual(marked.parser(tokens), '<p>after</p>\n');
1185+
});
1186+
10861187
it('should assign marked to `this`', () => {
10871188
marked.use({
10881189
walkTokens(token) {

0 commit comments

Comments
 (0)