Repository navigation
Commit d555e61
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
File tree
- benchmark/dom
- lib/jsdom
- living
- css
- custom-elements
- domparsing
- events
- helpers
- nodes
- range
- selection
- traversal
- test
- api
- fixtures
- web-platform-tests
- to-upstream/dom
- nodes
- ranges
Some content is hidden
Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
15 | 15 | | |
16 | 16 | | |
17 | 17 | | |
| 18 | + | |
18 | 19 | | |
19 | 20 | | |
20 | 21 | | |
| |||
79 | 80 | | |
80 | 81 | | |
81 | 82 | | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
82 | 107 | | |
83 | 108 | | |
84 | 109 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
35 | 35 | | |
36 | 36 | | |
37 | 37 | | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
38 | 53 | | |
39 | 54 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
118 | 118 | | |
119 | 119 | | |
120 | 120 | | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
121 | 171 | | |
122 | 172 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1 | 1 | | |
2 | 2 | | |
3 | 3 | | |
4 | | - | |
5 | 4 | | |
6 | 5 | | |
7 | 6 | | |
| |||
27 | 26 | | |
28 | 27 | | |
29 | 28 | | |
30 | | - | |
| 29 | + | |
31 | 30 | | |
32 | 31 | | |
33 | 32 | | |
| |||
0 commit comments