Tree Traversal

A LexTree stores its nodes as contiguous 16-byte records in preorder depth-first order. That single fact gives you four traversal styles, each best at something. This page covers all of them, with the cost model so you can pick deliberately.

The essentials

const tree = parseHtml(bytes);

tree.nodeCount;        // total nodes
tree.root;             // LexNode view of the root
tree.source;           // the original Uint8Array (zero-copy)

const node = tree.root;
node.kind;             // numeric kind id — compare against HtmlKind.* etc.
node.flags;            // raw flags byte
node.hasError;         // (flags & LEX_NODE_HAS_ERROR) !== 0
node.fieldId;          // numeric field role (0 = none)
node.fieldName();      // field role name via tree metadata, or null
node.subtreeSize;      // nodes in this subtree, including itself
node.range;            // LexRange — a TUPLE: readonly [start, end]
node.text;             // UTF-8 decode of source[start..end]

range is a tuple

node.range is readonly [start, end], not an object. Destructure it:

const [start, end] = node.range;

Style 1 — index scan (visit everything, fastest)

Preorder storage means “every node” is just indices 0..nodeCount:

import { LexNode } from '@lanexio/parser-core';

for (let i = 0; i < tree.nodeCount; i++) {
  const node = new LexNode(tree, i);
  if (node.hasError) console.log('error node at index', i, node.range);
}

This is the cheapest full visit — no stack, no child lists. To skip an entire subtree, jump by its size:

for (let i = 0; i < tree.nodeCount; ) {
  const node = new LexNode(tree, i);
  if (node.kind === HtmlKind.ScriptData) {
    i += node.subtreeSize;        // O(1) skip over everything inside
    continue;
  }
  i += 1;
}

Style 2 — children iteration (structured, allocation-light)

for (const child of tree.root.children()) {
  console.log(child.kind, child.range);
}

children() walks direct children by hopping subtreeSize, so iterating k children costs O(k) regardless of how big their subtrees are. Related helpers:

Call	Cost	Notes
node.children()	O(k) total	Preferred for sequential access.
node.childCount()	O(k)	Counts by iterating.
node.child(i)	O(i) per call	An indexed for loop over child(i) is O(k²) — use children() instead.
node.nextSibling() / previousSibling()	O(1) / O(siblings)	previousSibling rescans from the parent.
node.followingSiblings()	O(remaining)	Iterator over later siblings.
node.parent()	First call O(n) per tree, then O(1)	Builds a parent side-table lazily, cached on the tree.

Style 3 — field navigation (semantic access)

Grammars tag structurally meaningful children with field roles, resolved by name through the tree’s own metadata:

// JSON: object members expose key/value roles
const member = /* a JsonKind.Member node */;
member.childByField('key');     // the key String node
member.childByField('value');   // the member's value node

// HTML: elements expose tag/attrs/body; attributes expose name/value
element.childByField('attrs');

// CSS: rules and declarations expose selector/property/value
rule.childByField('selector');

Each grammar guide documents its field table (HTML: tag/attrs/name/value/body; JSON: key/value; CSS: selector/property/value; Markdown ships MdField roles; YAML models key/value as node kinds — YamlKind.Key/YamlKind.Value — instead of fields). For hot loops, resolve once and compare ids:

const keyField = tree.fieldIdForName('key');   // number | null
for (const child of member.children()) {
  if (child.fieldId === keyField) { /* … */ }
}

Style 4 — cursor (stateful walk, byte-position lookups)

LexCursor keeps a current position and moves in O(1)-ish steps without allocating per visited node:

const cursor = tree.cursor();             // positioned at root

cursor.current;                           // LexNode at the position
cursor.gotoFirstChild();                  // boolean
cursor.gotoNextSibling();                 // boolean
cursor.gotoPreviousSibling();             // boolean
cursor.gotoParent();                      // boolean (false at root)
cursor.gotoFirstChildForRange([s, e]);    // descend toward a byte range
cursor.gotoDescendantForRange([s, e]);    // jump to deepest node containing the range

The canonical full depth-first walk:

const cursor = tree.cursor();
visit: while (true) {
  const node = cursor.current;
  // …visit node…
  if (cursor.gotoFirstChild()) continue;
  while (!cursor.gotoNextSibling()) {
    if (!cursor.gotoParent()) break visit;
  }
}

Why not `while (gotoFirstChild() || gotoNextSibling())`?

That popular-looking loop is wrong twice over: without gotoParent() it never returns to visit aunts/uncles, and with gotoParent() in the disjunction it cycles forever (parent → first child → parent…). Use the labeled pattern above — descend, else advance, else climb until a sibling exists.

Byte-position lookups

For editors and diagnostics — “what node is at offset X?”:

// Deepest node containing byte offset 42:
const node = tree.root.descendantForRange([42, 42]);

// Deepest node containing a selection [start, end):
const sel = tree.root.descendantForRange([selStart, selEnd]);

Both run in O(depth × branching) by descending through containing children. firstChildForRange is the single-step version.

Choosing a style

Task	Reach for
Visit/filter every node	Index scan
Walk a node’s direct structure	children() / field navigation
Editor cursor ↔ tree position	LexCursor + range lookups
”Find all X anywhere” with a pattern	LexQuery