Mapping an ordered node-set to selections rebuilt each result as an
independent value Node through TreeNode.node, projecting that node's whole
subtree. For a result set whose nodes nest within one another (`//a` over a
deep chain, where every `a` contains all deeper ones) this materialized the
sum of their subtrees: quadratic. `//a` over an 8000-deep chain took ~19s.
The projection now threads a memo keyed by tree-node identity across one
result set. A tree node is projected once; a result that nests a
deeper one reuses its already-built value Node by reference, which the
copy-on-write Element storage (from the value-Node depth-safety work) makes
a shared, not copied, subtree. The set is built in one pass over the
distinct nodes. The same query now returns in ~0.04s and scales linearly.
The non-memoized `node` projection (serialization, value comparison) is
unchanged. Results are identical: 1787 tests pass, including the XPath and
XSLT value corpora. Closes#348.
Building a TreeNode from a value Node, projecting it back via `node`, and
releasing it each recursed one native frame per tree level, so a deeply
nested document overflowed the call stack (signal 10 around 30-60k deep,
and far shallower on a constrained stack such as a Swift Task). None of
these is fixed by the serializer, which was already iterative.
- `TreeNode(_:)` and `node`/`projectedChildren` now drive explicit
post-order work stacks (entity-reference splicing, doctype/namespace
dropping, and the root special-cases are unchanged).
- `deinit` flattens the subtree into a heap worklist before releasing, so
each node frees with empty children and the teardown stays flat. Only a
node the teardown solely owns (isKnownUniquelyReferenced) is flattened,
so a child still referenced elsewhere keeps its subtree.
- The validator walk and the XPath descendant axis were made iterative for
the same reason.
A 60000-deep tree now releases in well under 0.1s; 1778 tests pass and no
accepted output changes. Part of #341; the value Node's own recursive
release and XPath result ordering/dedup remain depth-bounded and tracked
there.
Building the mutable TreeNode tree from a parsed value Node ran append for every
child. append -> insert detaches the child from any previous parent, rejects a
self/ancestor cycle, and inserts into a children array that grows element by
element. The children the conversion passes come from element.children.map and
are freshly built and parentless, so all three guards are no-ops and the
incremental growth rebuilds an array that was already prepared.
TreeNode.init(adopting:) adopts the prepared array directly and wires each
child's parent. The tree is identical: the same children in the same order with
the same parent links. The adopting initializer is used only by the value-Node
conversion; every public factory keeps the detaching, cycle-checking append path
for externally supplied children that may already live in a tree.
Measured parse ~12% faster on the 20k-item generated corpus via a same-state
A/B (7.7x to ~6.5x slower than libxml2). Verified by TreeNodeAdoptingInitTests
(parent-wiring and post-adoption mutability), the W3C XML conformance corpora,
the Xalan XSLT gold-output corpus, the full suite, the WASM build, and an
adversarial equivalence review.
Add PureXML.Model.TreeNode, a reference-type document tree that knows its
parent and siblings. Navigation goes up and sideways (parent, nextSibling,
previousSibling, ancestors, root, elementChildren, stringValue) and editing
is in place (append, insert before/after, removeFromParent, replace, copy).
Children are held strongly and the parent weakly; attaching a node detaches
it from any prior parent and a node can never become its own ancestor.
parseTree builds one from XML; TreeNode.node converts back for serialization.
Closes#31
