Skip to content

Commit c215b88

Browse files
fix(javascript): build a deep syntax tree's objects without recursing
`toEstreeObject` recursed once per nested node, so a tree deeper than the call stack threw a `RangeError`. It now builds children from a work stack. Claude-Session: https://claude.ai/code/session_01Tgxgyb4N35ndP6cC4KcrXC
1 parent 8851c88 commit c215b88

2 files changed

Lines changed: 63 additions & 15 deletions

File tree

‎lib/javascript/syntax-parser.js‎

Lines changed: 47 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -18114,15 +18114,12 @@ const buildLiteralForms = (tree, node, target, fields) => {
1811418114
};
1811518115

1811618116
/**
18117-
* The ESTree object of a node, the same object each time it is asked for.
18118-
* With `fields`, only those are built, each a whole subtree; a later call adds
18119-
* what it lacks.
18117+
* The object of a node, made with only its type and offsets the first time.
1812018118
* @param {SyntaxTree} tree the tree holding the node
1812118119
* @param {number} node the node, or `0` for none
18122-
* @param {string[]=} fields the fields to build, or every field
18123-
* @returns {import("estree").Node | null} the node's object, or null for none
18120+
* @returns {EstreeObject | null} its object, or null for none
1812418121
*/
18125-
const toEstreeObject = (tree, node, fields) => {
18122+
const estreeObjectOf = (tree, node) => {
1812618123
if (node === 0) return null;
1812718124
let object = tree._objects[node];
1812818125
if (object === undefined) {
@@ -18132,14 +18129,23 @@ const toEstreeObject = (tree, node, fields) => {
1813218129
tree._ends[node]
1813318130
);
1813418131
tree._objects[node] = object;
18135-
} else if (tree._complete[node] === 1) {
18136-
return /** @type {import("estree").Node} */ (
18137-
/** @type {unknown} */ (object)
18138-
);
1813918132
}
18133+
return object;
18134+
};
18135+
18136+
/**
18137+
* Builds a node's fields onto its object, pushing each child whose object
18138+
* still lacks fields onto `pending` rather than recursing into it.
18139+
* @param {SyntaxTree} tree the tree holding the node
18140+
* @param {number} node the node
18141+
* @param {string[] | undefined} fields the fields to build, or every field
18142+
* @param {number[]} pending the nodes left to build
18143+
* @returns {void}
18144+
*/
18145+
const buildFields = (tree, node, fields, pending) => {
1814018146
const type = tree._types[node];
1814118147
const target = /** @type {Record<string, unknown>} */ (
18142-
/** @type {unknown} */ (object)
18148+
/** @type {unknown} */ (estreeObjectOf(tree, node))
1814318149
);
1814418150
const base = tree._bases[node];
1814518151
for (const field of getTreeNodeTypes()[type].fields) {
@@ -18152,15 +18158,18 @@ const toEstreeObject = (tree, node, fields) => {
1815218158
const slot = tree._slots[base + field.slot];
1815318159
switch (field.kind) {
1815418160
case FIELD_NODE:
18155-
target[field.name] = toEstreeObject(tree, slot);
18161+
target[field.name] = estreeObjectOf(tree, slot);
18162+
if (slot !== 0 && tree._complete[slot] === 0) pending.push(slot);
1815618163
break;
1815718164
case FIELD_LIST: {
1815818165
const start = tree._listStarts[slot];
1815918166
const length = tree._listLengths[slot];
18160-
/** @type {(import("estree").Node | null)[]} */
18167+
/** @type {(EstreeObject | null)[]} */
1816118168
const items = [];
1816218169
for (let i = 0; i < length; i++) {
18163-
items.push(toEstreeObject(tree, tree._listItems[start + i]));
18170+
const item = tree._listItems[start + i];
18171+
items.push(estreeObjectOf(tree, item));
18172+
if (item !== 0 && tree._complete[item] === 0) pending.push(item);
1816418173
}
1816518174
target[field.name] = items;
1816618175
break;
@@ -18174,7 +18183,30 @@ const toEstreeObject = (tree, node, fields) => {
1817418183
}
1817518184
if (type === treeLiteralType) buildLiteralForms(tree, node, target, fields);
1817618185
if (fields === undefined) tree._complete[node] = 1;
18177-
return /** @type {import("estree").Node} */ (/** @type {unknown} */ (object));
18186+
};
18187+
18188+
/**
18189+
* The ESTree object of a node, the same object each time it is asked for.
18190+
* With `fields`, only those are built, each a whole subtree; a later call adds
18191+
* what it lacks.
18192+
* @param {SyntaxTree} tree the tree holding the node
18193+
* @param {number} node the node, or `0` for none
18194+
* @param {string[]=} fields the fields to build, or every field
18195+
* @returns {import("estree").Node | null} the node's object, or null for none
18196+
*/
18197+
const toEstreeObject = (tree, node, fields) => {
18198+
const object = /** @type {import("estree").Node | null} */ (
18199+
/** @type {unknown} */ (estreeObjectOf(tree, node))
18200+
);
18201+
if (object === null || tree._complete[node] === 1) return object;
18202+
/** @type {number[]} */
18203+
const pending = [];
18204+
buildFields(tree, node, fields, pending);
18205+
while (pending.length > 0) {
18206+
const child = /** @type {number} */ (pending.pop());
18207+
buildFields(tree, child, undefined, pending);
18208+
}
18209+
return object;
1817818210
};
1817918211

1818018212
module.exports.BIND_FUNCTION = BIND_FUNCTION;

‎test/unitCases/JavascriptSyntaxTree.unittest.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,22 @@ describe("SyntaxTree", () => {
199199
).toBe(false);
200200
});
201201

202+
it("builds a tree nested deeper than the call stack", () => {
203+
const tree = new SyntaxTree();
204+
let node = tree.add("Identifier", 0, 1);
205+
tree.set(node, "name", "a");
206+
for (let i = 0; i < 100000; i++) {
207+
const unary = tree.add("UnaryExpression", 0, 1);
208+
tree.set(unary, "operator", "!");
209+
tree.set(unary, "prefix", true);
210+
tree.set(unary, "argument", node);
211+
node = unary;
212+
}
213+
let object = /** @type {EXPECTED_ANY} */ (toEstreeObject(tree, node));
214+
while (object.type === "UnaryExpression") object = object.argument;
215+
expect(object.name).toBe("a");
216+
});
217+
202218
it("refuses an unknown type or field", () => {
203219
const tree = new SyntaxTree();
204220
expect(() => tree.add("JSXElement", 0, 1)).toThrow(/Unknown node type/);

0 commit comments

Comments
 (0)