Expand description
Flat-array structural index for XML documents.
Instead of building a DOM tree with heap-allocated nodes and pointer-chasing,
this module represents XML structure as parallel arrays (struct-of-arrays layout).
Each tag gets an entry in tag_starts, tag_ends, tag_types, tag_names,
depths, and parents — all indexed by the same tag position.
Memory overhead is ~16 bytes per tag vs ~35 bytes per node in a typical DOM.
Parent-child and sibling relationships are stored in CSR (Compressed Sparse Row)
format, built lazily on first XPath evaluation. Tag names are interned to u16
IDs with an inverted posting index for O(1) name-to-tags lookup.
The index supports all 13 XPath 1.0 axes via array operations:
- O(1) ancestor/descendant checks using pre/post-order numbering
- O(1) child enumeration via CSR offsets
- O(1) tag name matching via interned name IDs