Skip to content

Commit d555e61

Browse files
scttcperdomeniccodex
authored
Replace SymbolTree with a DOM-specific tree
Replace the symbol-tree dependency with tree storage owned by NodeImpl instances. Expose traversal and tree comparisons as node methods, reduce mutation bookkeeping, and avoid repeatedly searching ancestor paths or traversing unrelated content in Range operations. Observable fixes: - Normalize only descendant Text nodes. Calling normalize() on a Text node now leaves the receiver and its siblings unchanged. Previously, an empty receiver could be removed, and a non-empty receiver could absorb adjacent siblings. - Use the UTF-16 data length of CDATASection nodes when validating and setting Range and Selection boundaries. Previously, CDATA sections were treated as having zero length because the node-length helper counted their children. - Recognize CDATASection as a Text and CharacterData subtype throughout Range operations. Cloning and extracting partial CDATA selections preserve the selected data and node type; deletion updates the data; insertion splits at the text offset; stringification includes CDATA text; surrounding accepts otherwise-valid partial CDATA boundaries; and contextual fragment creation uses the parent element as its context. Tree architecture and storage: - Store parent, sibling, child, child-count, and index-cache information in a lazily allocated Links record. Allocate records when nodes join a tree or gain children, without allocating tree storage merely to read an unattached node or attribute. - Keep link allocation, index caching, and raw link mutations in helpers/dom-tree.js, with NodeImpl as its only consumer. Keep DOM validation, adoption, live Range updates, mutation observers, slot assignment, and custom element reactions in the existing DOM mutation algorithms. - Expose underscored node methods for children, descendants, inclusive descendants, shadow-including traversal, array construction, tree position, and common-ancestor discovery. Distinguish inclusive and exclusive traversal explicitly so callers do not repeatedly filter out the root. - Preserve existing sibling indexes when appending or removing the last child. For other mutations, retain the valid cached prefix and rebuild subsequent indexes only when requested. Check cached-node identity before trusting an old index, and truncate cached references when removing or moving subtrees so retained parents do not keep removed descendants alive. - Read first- and last-child indexes directly, maintain child counts during mutations, and calculate insertion or removal indexes only when live Ranges require them. - Use Iterator subclasses for traversal and native iterator helpers for searches. Retain direct array builders for collection refreshes to avoid iterator-result allocations, and use direct sibling walks for element child/sibling getters and node equality. - Replace recursive shadow traversal generators with an explicit stack. Preserve the existing mutation semantics: capture the next light-tree node before visiting the current node, but inspect a host's shadow root after visiting the host. This preserves traversal order and avoids repeating insertion steps when synchronous callbacks insert light children during shadow traversal. - Consolidate root and containment operations on node implementations. Keep document-root caching and path compression in getRootNode(), while leaving detached roots uncached because their mutations do not invalidate descendant root caches. - Represent DOM node length with an internal _length getter overridden by CharacterDataImpl. Retain a separate _childCount getter for algorithms that explicitly count children, including selectAllChildren() on Selection instances. - Move HTMLCollection query factories into helpers/html-collections.js and keep named-window tree sorting alongside window-property handling. Remove the redundant node helper module, SymbolTree indirection, and simultaneous-iterator utility. Range and traversal algorithms: - Share common-ancestor discovery between tree-position comparisons and Range operations. Return the ancestor together with its child on each boundary path, and reuse that information for commonAncestorContainer, boundary-point comparisons, partial boundary children, and collapsed positions. Avoid repeated ancestor searches, including for branches with unequal depths. - Share boundary preparation between cloning and extraction. Identify fully contained children from the boundary paths and offsets instead of testing every child of the common ancestor. Snapshot the children and reject contained doctypes before cloning or mutation begins. - Start deletion and stringification at the boundary offsets and stop at the end boundary, skipping the contents of unrelated subtrees. Return immediately when stringifying a collapsed Range, and handle partial CharacterData boundaries separately. - When collecting nodes for deletion, skip descendants of each contained node selected for removal. This collects only the outermost contained nodes without a separate parent-containment check. Preserve collection before mutation, removal order, and live Range adjustments. - Check the two partial boundary children in surroundContents() instead of scanning the common ancestor's entire subtree. A non-Text partial child requires rejection; a Text partial child cannot contain further descendants. - Reuse bounded tree traversal in NodeIterator, including finding the next node within the iterator's root when adjusting its position before removal. Tests and benchmarks: - Add public API coverage for normalization, CDATA boundaries, subtree moves, sibling indexes, document order, nested shadow-tree adoption, Range content operations, boundary-limited traversal, mutation record ordering, and live Range updates. Cover garbage collection of previously indexed subtrees and synchronous mutation during shadow traversal. - Enable 13 existing Range WPT files covering cloning, extraction, deletion, collapse, common ancestors, boundary comparisons, point comparisons, node selection, boundary setters, character data mutations, and surrounding. Retain the Range-insertNode.html skip for the separate incorrect-exception-realm failures. - Add public API benchmarks for sibling mutations with and without live Ranges, element traversal, live collection refreshes, custom element upgrade traversal, tree comparisons, and Range operations across deep branches, unequal depths, shared ancestors, and unrelated subtrees. Keep destructive and non-destructive benchmark fixtures separate. Fixes #4291. Co-authored-by: Domenic Denicola <[email protected]> Co-authored-by: codex <[email protected]>
1 parent f28983d commit d555e61

64 files changed

Lines changed: 2027 additions & 911 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎benchmark/dom/custom-elements.js‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ module.exports = () => {
1515
addUIMountBenchmark(bench, definitionCount);
1616
}
1717
addCustomElementControls(bench);
18+
addUpgradeBenchmarks(bench);
1819

1920
return bench;
2021
};
@@ -79,6 +80,30 @@ function addCustomElementControls(bench) {
7980
});
8081
}
8182

83+
function addUpgradeBenchmarks(bench) {
84+
const { window } = new JSDOM();
85+
const { document } = window;
86+
87+
for (const shape of ["flat", "deep", "fields", "nested shadow"]) {
88+
const root = document.createElement("div");
89+
let parent = root;
90+
for (let i = 0; i < 200; ++i) {
91+
const child = parent.appendChild(document.createElement("div"));
92+
if (shape === "deep") {
93+
parent = child;
94+
} else if (shape === "nested shadow") {
95+
parent = child.attachShadow({ mode: "closed" });
96+
} else if (shape === "fields") {
97+
child.innerHTML = "<label><span>Name</span><input></label>";
98+
}
99+
}
100+
101+
bench.add(`upgrade(): ${shape} subtree without custom elements`, () => {
102+
window.customElements.upgrade(root);
103+
});
104+
}
105+
}
106+
82107
function createSubtree(document, localName = "div") {
83108
const parent = document.createElement("div");
84109

‎benchmark/dom/element-traversal.js‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
"use strict";
2+
const documentBench = require("../document-bench");
3+
4+
module.exports = () => {
5+
const { document, bench } = documentBench();
6+
7+
for (const shape of ["adjacent elements", "mixed nodes", "no elements"]) {
8+
const parents = [];
9+
const firstNodes = [];
10+
const lastNodes = [];
11+
for (let i = 0; i < 100; ++i) {
12+
const parent = document.createElement("div");
13+
const gap = shape === "adjacent elements" ? "" : "text<!-- comment -->".repeat(4);
14+
parent.innerHTML = shape === "no elements" ? gap : `${gap}<span></span>${gap}<span></span>${gap}`;
15+
parents.push(parent);
16+
firstNodes.push(parent.firstChild);
17+
lastNodes.push(parent.lastChild);
18+
}
19+
20+
bench.add(`firstElementChild: ${shape}`, () => {
21+
let count = 0;
22+
for (const parent of parents) {
23+
if (parent.firstElementChild !== null) {
24+
++count;
25+
}
26+
}
27+
return count;
28+
});
29+
30+
bench.add(`lastElementChild: ${shape}`, () => {
31+
let count = 0;
32+
for (const parent of parents) {
33+
if (parent.lastElementChild !== null) {
34+
++count;
35+
}
36+
}
37+
return count;
38+
});
39+
40+
bench.add(`nextElementSibling: ${shape}`, () => {
41+
let count = 0;
42+
for (const node of firstNodes) {
43+
if (node.nextElementSibling !== null) {
44+
++count;
45+
}
46+
}
47+
return count;
48+
});
49+
50+
bench.add(`previousElementSibling: ${shape}`, () => {
51+
let count = 0;
52+
for (const node of lastNodes) {
53+
if (node.previousElementSibling !== null) {
54+
++count;
55+
}
56+
}
57+
return count;
58+
});
59+
}
60+
61+
return bench;
62+
};

‎benchmark/dom/live-collections.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,5 +35,20 @@ module.exports = () => {
3535
addUpdateTask("children: read after updating list", "children", false);
3636
addUpdateTask("children: read after every mutation", "children", true);
3737

38+
for (const [name, query] of [
39+
["tag name", parent => parent.getElementsByTagName("span")],
40+
["all elements", parent => parent.getElementsByTagName("*")],
41+
["class name", parent => parent.getElementsByClassName("match")]
42+
]) {
43+
const parent = document.createElement("div");
44+
parent.innerHTML = '<span class="match"><b>text</b></span><!-- comment -->'.repeat(ITEM_COUNT);
45+
const collection = query(parent);
46+
let version = 0;
47+
bench.add(`${name}: refresh descendants after mutation`, () => {
48+
parent.setAttribute("data-version", String(++version));
49+
return collection.length;
50+
});
51+
}
52+
3853
return bench;
3954
};

‎benchmark/dom/middle-mutations.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
"use strict";
2+
3+
const documentBench = require("../document-bench");
4+
5+
module.exports = () => {
6+
const { document, bench } = documentBench();
7+
8+
for (const liveRange of [false, true]) {
9+
for (const pattern of ["fixed middle", "random reordering"]) {
10+
const parent = document.createElement("div");
11+
const children = Array.from({ length: 1000 }, () => document.createElement("span"));
12+
const extra = document.createElement("span");
13+
const range = liveRange ? document.createRange() : null;
14+
const suffix = liveRange ? "with a live Range" : "without live Ranges";
15+
16+
bench.add(`${pattern}: 200 moves among 1000 siblings, ${suffix}`, () => {
17+
for (let i = 0; i < 200; ++i) {
18+
if (pattern === "fixed middle") {
19+
parent.insertBefore(extra, children[500]);
20+
parent.removeChild(extra);
21+
} else {
22+
parent.insertBefore(children[(i * 397) % 1000], children[(i * 173 + 501) % 1000]);
23+
}
24+
}
25+
}, {
26+
beforeEach() {
27+
parent.replaceChildren(...children);
28+
if (liveRange) {
29+
range.selectNodeContents(parent);
30+
}
31+
}
32+
});
33+
}
34+
}
35+
36+
return bench;
37+
};

‎benchmark/dom/range-subtrees.js‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
"use strict";
2+
const documentBench = require("../document-bench");
3+
4+
module.exports = () => {
5+
const { document, bench } = documentBench();
6+
7+
const deletionParent = document.createElement("div");
8+
const subtree = document.createElement("section");
9+
let descendant = subtree;
10+
for (let i = 0; i < 200; ++i) {
11+
descendant = descendant.appendChild(document.createElement("div"));
12+
}
13+
const deletionRange = document.createRange();
14+
bench.add("deleteContents: fully contained deep subtree", () => deletionRange.deleteContents(), {
15+
beforeEach() {
16+
deletionParent.appendChild(subtree);
17+
deletionRange.selectNode(subtree);
18+
}
19+
});
20+
21+
for (const siblingCount of [0, 1000]) {
22+
const parent = document.createElement("div");
23+
const left = parent.appendChild(document.createTextNode("left"));
24+
const right = parent.appendChild(document.createTextNode("right"));
25+
for (let i = 0; i < siblingCount; ++i) {
26+
parent.appendChild(document.createElement("span"));
27+
}
28+
const wrapper = document.createElement("b");
29+
const range = document.createRange();
30+
bench.add(`surroundContents: adjacent text with ${siblingCount} unrelated siblings`, () => {
31+
range.surroundContents(wrapper);
32+
}, {
33+
beforeEach() {
34+
wrapper.remove();
35+
wrapper.replaceChildren();
36+
left.data = "left";
37+
right.data = "right";
38+
range.setStart(left, 2);
39+
range.setEnd(right, 3);
40+
}
41+
});
42+
}
43+
44+
for (const siblingCount of [0, 1000]) {
45+
const parent = document.createElement("div");
46+
const selected = parent.appendChild(document.createElement("b"));
47+
selected.textContent = "selected";
48+
for (let i = 0; i < siblingCount; ++i) {
49+
let node = parent.appendChild(document.createElement("section"));
50+
for (let depth = 0; depth < 20; ++depth) {
51+
node = node.appendChild(document.createElement("div"));
52+
}
53+
node.textContent = "unselected";
54+
}
55+
56+
const range = document.createRange();
57+
range.selectNode(selected);
58+
bench.add(`toString: one child with ${siblingCount} unrelated subtrees`, () => range.toString());
59+
60+
const collapsed = document.createRange();
61+
collapsed.setStart(parent, 0);
62+
collapsed.collapse(true);
63+
bench.add(`toString: collapsed with ${siblingCount} unrelated subtrees`, () => collapsed.toString());
64+
65+
const deletionTree = parent.cloneNode(true);
66+
const childToDelete = deletionTree.firstChild;
67+
const deletion = document.createRange();
68+
bench.add(`deleteContents: one child with ${siblingCount} unrelated subtrees`, () => deletion.deleteContents(), {
69+
beforeEach() {
70+
deletionTree.insertBefore(childToDelete, deletionTree.firstChild);
71+
deletion.selectNode(childToDelete);
72+
}
73+
});
74+
}
75+
76+
return bench;
77+
};

‎benchmark/dom/ranges.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -118,5 +118,55 @@ module.exports = () => {
118118
}
119119
});
120120

121+
for (const [shape, leftDepth, rightDepth, sharedDepth, siblingCount] of [
122+
["deep branches", 200, 200, 0, 0],
123+
["unequal branch depths", 200, 10, 0, 0],
124+
["deep shared ancestor", 10, 10, 200, 0],
125+
["many unrelated siblings", 1, 1, 0, 1000]
126+
]) {
127+
for (const method of ["cloneContents", "extractContents", "deleteContents"]) {
128+
let left, right, start, end, range;
129+
130+
function descend(parent, depth) {
131+
for (let i = 0; i < depth; ++i) {
132+
parent = parent.appendChild(document.createElement("div"));
133+
}
134+
return parent;
135+
}
136+
137+
function resetBoundaries() {
138+
left.replaceChildren();
139+
right.replaceChildren();
140+
start = descend(left, leftDepth).appendChild(document.createTextNode("start"));
141+
end = descend(right, rightDepth).appendChild(document.createTextNode("end"));
142+
range.setStart(start, 2);
143+
range.setEnd(end, 1);
144+
}
145+
146+
bench.add(`${method}: ${shape}`, () => range[method](), {
147+
beforeAll() {
148+
const root = descend(document.createElement("div"), sharedDepth);
149+
for (let i = 0; i < siblingCount; ++i) {
150+
root.appendChild(document.createElement("span"));
151+
}
152+
left = root.appendChild(document.createElement("section"));
153+
right = root.appendChild(document.createElement("section"));
154+
for (let i = 0; i < siblingCount; ++i) {
155+
root.appendChild(document.createElement("span"));
156+
}
157+
range = document.createRange();
158+
resetBoundaries();
159+
},
160+
beforeEach() {
161+
// Partial boundary ancestors survive extraction and deletion. Restore only
162+
// their contents, leaving the unrelated siblings and shared ancestors intact.
163+
if (method !== "cloneContents") {
164+
resetBoundaries();
165+
}
166+
}
167+
});
168+
}
169+
}
170+
121171
return bench;
122172
};

‎benchmark/dom/sibling-indexes.js‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
"use strict";
2+
const documentBench = require("../document-bench");
3+
4+
module.exports = () => {
5+
const { document, bench } = documentBench();
6+
7+
for (const liveRange of [false, true]) {
8+
const suffix = liveRange ? "with a live Range" : "without live Ranges";
9+
const removalParent = document.createElement("div");
10+
const insertionParent = document.createElement("div");
11+
const removalChildren = Array.from({ length: 1000 }, () => document.createElement("span"));
12+
const insertionChildren = Array.from({ length: 1000 }, () => document.createElement("span"));
13+
const reference = document.createElement("span");
14+
const removalRange = liveRange ? document.createRange() : null;
15+
const insertionRange = liveRange ? document.createRange() : null;
16+
17+
// Restore the trees outside the timed region. Repeated mutations at the end
18+
// invalidate sibling-index caches and expose unnecessary rescans.
19+
bench.add(`removeChild: last of 1000 siblings, ${suffix}`, () => {
20+
while (removalParent.lastChild) {
21+
removalParent.removeChild(removalParent.lastChild);
22+
}
23+
}, {
24+
beforeEach() {
25+
removalParent.replaceChildren(...removalChildren);
26+
if (liveRange) {
27+
removalRange.selectNodeContents(removalParent);
28+
}
29+
}
30+
});
31+
32+
bench.add(`insertBefore: 1000 siblings before last child, ${suffix}`, () => {
33+
for (const child of insertionChildren) {
34+
insertionParent.insertBefore(child, reference);
35+
}
36+
}, {
37+
beforeEach() {
38+
insertionParent.replaceChildren(reference);
39+
if (liveRange) {
40+
insertionRange.selectNodeContents(insertionParent);
41+
}
42+
}
43+
});
44+
}
45+
46+
return bench;
47+
};

‎benchmark/dom/tree-position.js‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
"use strict";
2+
3+
const documentBench = require("../document-bench");
4+
5+
module.exports = () => {
6+
const { document, bench } = documentBench();
7+
8+
function descend(parent, depth) {
9+
for (let i = 0; i < depth; ++i) {
10+
parent = parent.appendChild(document.createElement("div"));
11+
}
12+
return parent;
13+
}
14+
15+
for (const [leftDepth, rightDepth, sharedDepth] of [[1000, 1000, 0], [1000, 10, 0], [10, 10, 1000]]) {
16+
const root = document.createElement("div");
17+
const commonAncestor = descend(root, sharedDepth);
18+
const left = descend(commonAncestor, leftDepth);
19+
const right = descend(commonAncestor, rightDepth);
20+
bench.add(`compare branches: depths ${leftDepth}/${rightDepth}, shared depth ${sharedDepth}`, () => {
21+
return left.compareDocumentPosition(right);
22+
});
23+
24+
const range = document.createRange();
25+
range.setStart(left, 0);
26+
range.setEnd(right, 0);
27+
bench.add(`common ancestor: depths ${leftDepth}/${rightDepth}, shared depth ${sharedDepth}`, () => {
28+
return range.commonAncestorContainer;
29+
});
30+
}
31+
32+
return bench;
33+
};

‎lib/jsdom/living/css/StyleSheetList-impl.js‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
"use strict";
22

33
const idlUtils = require("../../../generated/idl/utils.js");
4-
const { domSymbolTree } = require("../helpers/internal-constants");
54
const { DOCUMENT_POSITION_FOLLOWING } = require("../node-document-position");
65

76
exports.implementation = class StyleSheetList {
@@ -27,7 +26,7 @@ exports.implementation = class StyleSheetList {
2726
if (!_list.includes(sheet)) {
2827
// https://drafts.csswg.org/cssom/#add-a-css-style-sheet
2928
const index = _list.findLastIndex(other => {
30-
return domSymbolTree.compareTreePosition(other.ownerNode, sheet.ownerNode) & DOCUMENT_POSITION_FOLLOWING;
29+
return other.ownerNode._compareTreePosition(sheet.ownerNode) & DOCUMENT_POSITION_FOLLOWING;
3130
});
3231
_list.splice(index + 1, 0, sheet);
3332
}

0 commit comments

Comments
 (0)