XPath sorting asserts on node-sets with nodes from different trees
Component: WebCore XPath | 5f78a99
Source/WebCore/xml/XPathNodeSet.cpp
XPath location paths and unions produce a node-set that must come back in document order. For small sets, WebKit builds an ancestor chain for each node and compares chains; above roughly 10,000 nodes it switches to a traversal sort that walks a tree from a root and emits nodes as it meets them, which only works if every node is reachable from that root. Detached attributes and disconnected subtrees have their own roots, so a union with the document can mix several trees, and a shadow tree's root is its ShadowRoot, not the document.
NodeSet::sort() now sorts each tree separately and concatenates trees in first-seen order. Since 17129@main it had assumed all nodes shared one tree, so a union such as (id("x") | .) mixing a document node with a detached attribute or disconnected node crashed or read out of bounds. Separately, large sets inside a shadow tree are now sorted from the shadow root; since 91446@main the traversal sort started at the document and never reached shadow nodes.
After (mixed trees):
NodeSet {doc node, detachedAttr, ...}
└─► allNodesAreInOneTree()? no
└─► sortEachTree()
├─ tree A (first seen) ─► sortOneTree()
├─ tree B (detached) ─► sortOneTree()
└─ concatenate in first-seen order
Shadow tree (>10000 nodes):
Before: traversalSort ─► findRootNode(first) ─► Document
After: traversalSort ─► treeRoot(first) ─► ShadowRoot
Significance
The out-of-bounds read was reachable from web JS through document.evaluate with attacker-chosen XPath and DOM. Two regressions in the same invariant over two commits suggests the tree-membership assumptions behind node-set sorting are fragile.
Audit directions
The single-tree assumption likely lives elsewhere too. Check other NodeSet consumers that may assume one tree: union, predicates, position()/last() handling, and the iterator and snapshot result types. Probe root selection for attribute nodes whose ownerElement changes or is removed during evaluation, shadow roots nested inside disconnected subtrees, slotted nodes, and mixed trees right at the 10,000-node switch between strategies. Check whether sorting can run while XPath functions or custom resolvers mutate the DOM. The test builds its union with id(), so fuzzing id() combined with document.evaluate over disconnected content is a natural starting point.