Define the first bounded document-tree walk contract

[isomorphisms]

Why this issue exists

IB currently has a streaming information extractor in IB.Information: it tokenizes text/tag runs and recursively builds an InformationView. It does not yet have a DOM or another browser-owned node graph.

Issues #35–#37 correctly identify selector matching, style/layout traversal, and tree construction as important later workloads, but they currently jump over the missing substrate. This issue defines that substrate as a semantic acceptance contract before anyone chooses an Idriç representation or writes another implementation.

Status: issue-only design contract

Do not implement this issue in Java, inherited Idris, Idriç, C, or ARM assembly yet.

Implementation begins only after isomorphisms/idric-arm-thumb#31 says the required Idriç gates are green. Existing draft experiments may remain evidence, but they do not settle the language, ABI, node layout, or browser architecture.

Non-bridges:

• no RefC or generic boxed value/runtime;
• no Float32-buffer sentinel used as a pretend node/result ABI;
• no WebView DOM as IB's canonical tree;
• no hidden allocation, recursion, or string representation inherited merely because Idris already supplies one.

"DOM walking" here means walking a browser-owned normalized document tree. It does not require a standards-complete, permanently live web DOM when a smaller typed document IR is sufficient.

First bounded semantic fixture

Define one static, already-tokenized tree with stable node identities:

Node	Kind	Relevant data	Parent
0	document	—	none
1	html	—	0
2	body	—	1
3	nav	class primary	2
4	a	class active	3
5	text	Home	4
6	main	—	2
7	article	—	6
8	h1	—	7
9	text	Title	8
10	p	—	7
11	text	Body	10

The fixture is semantic, not a required memory layout. The first exact observations should be:

• preorder node identities: [0,1,2,3,4,5,6,7,8,9,10,11];
• direct children of node 2: [3,6];
• next sibling of node 3: node 6;
• first descendant of node 3 matching a.active: node 4;
• first descendant of node 6 matching a.active: none;
• nearest ancestor of node 5 with kind nav: node 3;
• text descendants of node 7, in document order: nodes [9,11].

Record visited-node counts for early-exit operations as well as the semantic result, so later traversal changes can be evaluated without making one traversal strategy part of the meaning.

For the first native fixture, tag and class identities are already-decoded finite values. HTML tokenization, UTF-8 decoding, CSS parsing, raw selector strings, networking, mutation/invalidation, layout, paint, and platform I/O are deliberately outside this fixture.

The words Home, Title, and Body name the logical text nodes for human review. The first native walk does not inspect their bytes and therefore need not commit to a text payload representation.

Representation questions to settle later

The contract intentionally does not yet choose:

• packed node records versus parallel arrays;
• parent/first-child/next-sibling links versus child ranges or another compact encoding;
• NodeId width;
• region ownership and lifetime;
• whether text is stored as a byte slice, source span, interned identity, or another reviewed form;
• cursor/stack representation for bounded traversal;
• whether a proof or up-front bounds check can remove checks inside the walk;
• how a mutable/live document differs from a compact prepaint document.

The first native walk should not require a general heap or source-level recursion. That is a constraint on the first acceptance program, not a premature claim that Idriç can never represent recursion or dynamic trees.

Browser connections

This one substrate should later support small, separate semantic ladders for:

• operative-content extraction now performed by collect_information;
• selector relationships in Make CSS selector matching a browser control-flow benchmark #35;
• compiled matching and computed-style association in Compile CSS matching and attach computed style records to DOM nodes #36;
• tree construction following tokenization in Make HTML/XML tokenization a renderer-native branch/scanning benchmark #37;
• heading/link/form/table discovery for prepaint;
• layout and display-list walks;
• link hit regions;
• browser-owned display-repair anchors.

Computed style must be associated with a stable node identity; this issue does not require physically embedding a style record in every node.

HTML and XML may share byte-scanning machinery, but their recovery and tree-construction semantics must not be conflated.

Connection to low-level ARM/Thumb work

Once the language gates are green, this fixture becomes a compact test of:

• direct named calls;
• fixed-width integer arguments and returns;
• indexed loads;
• bounds/extent handling;
• finite tags;
• comparisons and two-way branches;
• bounded loops;
• sibling/ancestor/descendant traversal;
• early exit;
• exact stable-ID results.

Only after the portable semantic program exists should a backend compare record layouts, branch trees, tables, packed fields, or other ARM-specific choices.

Done for the issue-only phase

• the logical tree and exact observations above are reviewed;
• the distinction between logical document tree and physical node layout remains explicit;
• Make CSS selector matching a browser control-flow benchmark #35–Make HTML/XML tokenization a renderer-native branch/scanning benchmark #37 point here rather than assuming a DOM already exists;
• Sequence IB-derived ARM/Thumb work behind native Idriç gates idric-arm-thumb#31 points here as the first bounded tree-walk target;
• no implementation is started merely to make this checklist green.