Study guides · Advanced

Preserve DOM parent and child invariants in Rust

Build a consistent DOM from tokens using arena indices and an open-element stack, then test recovery policies and structural boundaries.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Goal: build a tree on an indexed arena
  2. Why links use indices rather than references
  3. Worked trace: the stack of open elements
  4. Policies for mismatches, void elements, and duplicates
  5. A small Rust check for structural consistency
  6. Compare normal, boundary, and failure cases
  7. Exercise: explain the tree together with its source
  8. Ask Logeia about this articleCheck your understanding

Goal: build a tree on an indexed arena

The tokenizer recognizes pieces of input; tree construction decides how those pieces relate. The project’s parse_html function uses an arena: nodes live in one vector, and parent and child links are indices into that vector. Before considering pointer-based alternatives, establish three properties: a node has at most one parent, a parent’s child list agrees with each child’s parent field, and the open-element stack identifies the current insertion context.

Run the same HTML through the WASM demo and inspect the tokens before the tree. Correct tokens do not guarantee a correct DOM when a node is attached to the wrong parent. Translate the familiar operation “append a child” into adding a vector entry, obtaining its index, and updating both sides of the relationship. The node numbers identify positions within one parse. They are not persistent user identifiers or suitable keys for account progress, and a later parse may assign them to different nodes.

Why links use indices rather than references

A vector can move its allocation when it grows. Retaining references to its elements while continuing to append therefore conflicts with the design and with Rust borrowing rules. Saving an index lets code obtain a fresh reference after growth. Indices still require invariants: they must be in bounds, belong to the current document, and not silently designate a different node after deletion or reuse. An integer is a representation choice, not a proof of structural correctness.

This parser appends nodes in order, attaching a new child to a parent that already exists. Avoid holding a mutable borrow of the parent across a vector push. Read the needed identifiers, append the node, then update the parent’s child list. Keep tree construction independent from JSON formatting so changing the presentation format does not alter the structural tests. A useful review question is whether the tree can be inspected without invoking any UI code; in this project, the Rust data structures are that independent boundary.

Worked trace: the stack of open elements

For <div><p>A</p><p>B</p></div>, start with document node 0. A possible append order is div 1, first p 2, text A 3, second p 4, and text B 5. An opening tag attaches an element under the stack top and then makes that element the new top. Text attaches under the current top. A matching closing tag removes an entry from the open-element stack; it does not delete the element from the DOM. Returning to div is what makes the two paragraphs siblings.

If the first closing paragraph fails to pop the stack, the second paragraph becomes a child of the first. The token count and a flattened text output of AB can remain unchanged, so neither catches the structural bug. Assert that node 4 has parent 1 and that node 1 lists children 2 and 4. Use explicitly paired tags for this exercise. Browser-standard insertion modes and omitted-tag recovery are separate concerns and cannot be inferred from this small stack algorithm.

After inputStackNew relationship
<div>[0,1]Parent of 1 is 0
<p>A[0,1,2]Parent of 3 is 2
</p>[0,1]Node 2 remains
<p>B[0,1,4]Parent of 4 is 1

Policies for mismatches, void elements, and duplicates

The implemented parse_html records a diagnostic for a mismatched closing tag and leaves the stack unchanged for that mismatch. In <div></p></div>, you can observe rejection of the paragraph closer separately from the later matching div closer. Open elements remaining at end of input are also diagnosed. Silently pretending they were all closed would hide an editing mistake. This is the teaching subset’s policy, not a claim to reproduce the recovery behavior of a complete browser HTML parser.

The project treats br, hr, img, input, meta, and link as void elements, so they do not become a new insertion parent on the stack. Duplicate attributes retain their first value. These choices produce useful boundary tests: inspect the parent of B in <div>A<br>B</div>, then use a repeated id attribute and inspect the retained value. When extending the accepted language, verify existing diagnostic positions and child order as well as the new example. Recovery is observable behavior and therefore belongs in the documented contract.

A small Rust check for structural consistency

The standalone program below checks agreement between parent links and child lists in a tiny indexed tree. The document lists node 1, and node 1 points back to document 0. Give each project test the name of an invariant rather than describing it only as an expected output string. Updating one side of a relationship while forgetting the other is a concrete bug that this check exposes directly.

Add checks that each non-document node appears in exactly one parent’s child list and that siblings preserve source order. An operation that can create cycles needs a traversal check with a visited set or an equivalent proof. In the current append-only construction, a parent exists before its new child, which offers an additional useful invariant. If you later implement moving nodes, reconsider that proof: a property established by append order may no longer hold for arbitrary mutations.

rust
// Standalone arena invariant; related to parse_html parent/children links.
struct Node { parent: Option<usize>, children: Vec<usize> }
fn main() {
    let nodes = vec![
        Node { parent: None, children: vec![1] },
        Node { parent: Some(0), children: vec![] },
    ];
    for (parent, node) in nodes.iter().enumerate() {
        for &child in &node.children {
            assert_eq!(nodes[child].parent, Some(parent));
        }
    }
}

Compare normal, boundary, and failure cases

A normal test should contain both siblings and nesting; a single paragraph barely exercises restoration of an insertion parent. Boundary cases include an empty document, void elements, whitespace-only text, Japanese text, and nesting immediately below the documented limit. Failure cases include mismatched closing names, unclosed elements, interrupted attributes, and exceeded node or depth limits. The current project documents limits of 8192 input bytes, 512 tokens, 256 nodes, and 31 nested elements.

For a rejected input, inspect several facts: a diagnostic exists, its source range is valid, any retained tree still has consistent links, and a new run contains no nodes from the previous run. A page remaining responsive is not proof that the intended limit was enforced. Vary one boundary at a time so you can identify whether tokenization or tree construction produced the stopping condition. That distinction becomes valuable when the renderer later receives the same document.

Exercise: explain the tree together with its source

After running the completed project, implement the child-attachment milestone in the exercise version and compare its tree with your hand calculation. Begin with an input producing only a few nodes, then add a sibling and a void element. Test the tree returned by parse_html itself. Reordering JSON afterward to obtain a pleasing picture does not fix a broken construction invariant, and the next stage will consume this same document.

For one diagnostic, record its source byte range, the relevant Rust branch, the stack change, and the links retained in the DOM. Use the article and source views together until you can explain why a particular child belongs under a particular parent. Keep question answers, web execution, and local implementation completion as distinct records. A saved local test log gives the layout chapter an evidence trail: when geometry later looks wrong, you can establish whether the input tree was already correct.

Parse HTML and build a DOM in Rust

Loading experiment checkpoint…

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 20

Choose a learning path