Skip to content

Commit 8482c9f

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 204a98b commit 8482c9f

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
@@ -18088,15 +18088,12 @@ const buildLiteralForms = (tree, node, target, fields) => {
1808818088
};
1808918089

1809018090
/**
18091-
* The ESTree object of a node, the same object each time it is asked for.
18092-
* With `fields`, only those are built, each a whole subtree; a later call adds
18093-
* what it lacks.
18091+
* The object of a node, made with only its type and offsets the first time.
1809418092
* @param {SyntaxTree} tree the tree holding the node
1809518093
* @param {number} node the node, or `0` for none
18096-
* @param {string[]=} fields the fields to build, or every field
18097-
* @returns {import("estree").Node | null} the node's object, or null for none
18094+
* @returns {EstreeObject | null} its object, or null for none
1809818095
*/
18099-
const toEstreeObject = (tree, node, fields) => {
18096+
const estreeObjectOf = (tree, node) => {
1810018097
if (node === 0) return null;
1810118098
let object = tree._objects[node];
1810218099
if (object === undefined) {
@@ -18106,14 +18103,23 @@ const toEstreeObject = (tree, node, fields) => {
1810618103
tree._ends[node]
1810718104
);
1810818105
tree._objects[node] = object;
18109-
} else if (tree._complete[node] === 1) {
18110-
return /** @type {import("estree").Node} */ (
18111-
/** @type {unknown} */ (object)
18112-
);
1811318106
}
18107+
return object;
18108+
};
18109+
18110+
/**
18111+
* Builds a node's fields onto its object, pushing each child whose object
18112+
* still lacks fields onto `pending` rather than recursing into it.
18113+
* @param {SyntaxTree} tree the tree holding the node
18114+
* @param {number} node the node
18115+
* @param {string[] | undefined} fields the fields to build, or every field
18116+
* @param {number[]} pending the nodes left to build
18117+
* @returns {void}
18118+
*/
18119+
const buildFields = (tree, node, fields, pending) => {
1811418120
const type = tree._types[node];
1811518121
const target = /** @type {Record<string, unknown>} */ (
18116-
/** @type {unknown} */ (object)
18122+
/** @type {unknown} */ (estreeObjectOf(tree, node))
1811718123
);
1811818124
const base = tree._bases[node];
1811918125
for (const field of getTreeNodeTypes()[type].fields) {
@@ -18126,15 +18132,18 @@ const toEstreeObject = (tree, node, fields) => {
1812618132
const slot = tree._slots[base + field.slot];
1812718133
switch (field.kind) {
1812818134
case FIELD_NODE:
18129-
target[field.name] = toEstreeObject(tree, slot);
18135+
target[field.name] = estreeObjectOf(tree, slot);
18136+
if (slot !== 0 && tree._complete[slot] === 0) pending.push(slot);
1813018137
break;
1813118138
case FIELD_LIST: {
1813218139
const start = tree._listStarts[slot];
1813318140
const length = tree._listLengths[slot];
18134-
/** @type {(import("estree").Node | null)[]} */
18141+
/** @type {(EstreeObject | null)[]} */
1813518142
const items = [];
1813618143
for (let i = 0; i < length; i++) {
18137-
items.push(toEstreeObject(tree, tree._listItems[start + i]));
18144+
const item = tree._listItems[start + i];
18145+
items.push(estreeObjectOf(tree, item));
18146+
if (item !== 0 && tree._complete[item] === 0) pending.push(item);
1813818147
}
1813918148
target[field.name] = items;
1814018149
break;
@@ -18148,7 +18157,30 @@ const toEstreeObject = (tree, node, fields) => {
1814818157
}
1814918158
if (type === treeLiteralType) buildLiteralForms(tree, node, target, fields);
1815018159
if (fields === undefined) tree._complete[node] = 1;
18151-
return /** @type {import("estree").Node} */ (/** @type {unknown} */ (object));
18160+
};
18161+
18162+
/**
18163+
* The ESTree object of a node, the same object each time it is asked for.
18164+
* With `fields`, only those are built, each a whole subtree; a later call adds
18165+
* what it lacks.
18166+
* @param {SyntaxTree} tree the tree holding the node
18167+
* @param {number} node the node, or `0` for none
18168+
* @param {string[]=} fields the fields to build, or every field
18169+
* @returns {import("estree").Node | null} the node's object, or null for none
18170+
*/
18171+
const toEstreeObject = (tree, node, fields) => {
18172+
const object = /** @type {import("estree").Node | null} */ (
18173+
/** @type {unknown} */ (estreeObjectOf(tree, node))
18174+
);
18175+
if (object === null || tree._complete[node] === 1) return object;
18176+
/** @type {number[]} */
18177+
const pending = [];
18178+
buildFields(tree, node, fields, pending);
18179+
while (pending.length > 0) {
18180+
const child = /** @type {number} */ (pending.pop());
18181+
buildFields(tree, child, undefined, pending);
18182+
}
18183+
return object;
1815218184
};
1815318185

1815418186
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)