moldybits/rust_browser
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
fix/es-modules-fifth-review-3-4
rust_browser/_bmad-output/implementation-artifacts/2-2-tree-builder-insertion-modes.md
Zachary D. Rowitsch d5234cf546 Implement HTML5 tree builder insertion modes with code review fixes (§13.2.6) 
Refactor tree_builder.rs into module directory with 7 files implementing all
23 insertion modes per WHATWG HTML §13.2.6.4 as an explicit state machine.
Includes active formatting elements list with Noah's Ark clause, scope
checking for all 5 scope types, context-sensitive fragment parsing, and
iterative token reprocessing via ProcessResult enum.

Code review fixes: fix formatting element end tag truncation bug (save
node_id before truncate), replace manual element creation in catch-all
StartTag with insert_element_maybe_self_closing, add skip_next_newline for
pre/listing/textarea per spec, add QuirksMode to Document with basic DOCTYPE
detection, refactor all 23 handlers from Token to &Token to eliminate clone
per dispatch, fix self_closing handling for pre/listing/textarea/plaintext,
improve golden test 276 fixture coverage and foster-parent test assertion.

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
2026-03-14 22:12:19 -04:00

20 KiB
Raw Permalink Blame History

Story 2.2: Tree Builder Insertion Modes

Status: done

Story

As a web user, I want the browser to construct the correct DOM tree from any HTML document, So that page structure matches what other browsers produce.

Acceptance Criteria

  1. All tree builder insertion modes implemented per WHATWG HTML §13.2.6: initial, before html, before head, in head, in head noscript, after head, in body, text, in table, in table text, in caption, in column group, in table body, in row, in cell, in select, in select in table, in template, after body, in frameset, after frameset, after after body, after after frameset — with correct state transitions between modes.

  2. Implicit element creation works per spec: <td> without <table> auto-creates table structure; text before <html> triggers implicit element insertion; head-only elements encountered after <body> are handled correctly.

  3. Misnested block/inline elements restructured per spec: <p><div></div></p> splits the <p> element correctly. Full optional end tag rules for <li>, <dt>, <dd>, <option>, <optgroup>, <rb>, <rt>, <rtc>, <rp> in addition to existing <p> and table element rules.

  4. Elements that change insertion mode (tables, select, template, etc.) activate and deactivate the correct mode at the right boundaries.

  5. WPT tree-construction tests pass for all covered insertion modes. docs/HTML5_Implementation_Checklist.md updated. just ci passes.

Tasks / Subtasks

  • Task 1: Refactor to explicit insertion mode state machine (AC: #1, #4)

    • 1.1 Create InsertionMode enum with all 23 modes from WHATWG §13.2.6.4
    • 1.2 Refactor build() to use insertion_mode: InsertionMode field instead of in_head boolean
    • 1.3 Add original_insertion_mode: Option<InsertionMode> for modes that need to return (text mode, in-table-text mode)
    • 1.4 Add template_insertion_modes: Vec<InsertionMode> stack for <template> elements
    • 1.5 Implement mode transition logic: each mode dispatches tokens and may switch to another mode via process_token() → match self.insertion_mode
    • 1.6 Extract mode handlers into separate methods or a module file if tree_builder.rs exceeds file size limits

  • Task 2: Implement early-document modes (AC: #1, #2)

    • 2.1 Initial mode (§13.2.6.4.1): Handle DOCTYPE token → set document quirks/limited-quirks mode; anything else → switch to "before html"
    • 2.2 Before html mode (§13.2.6.4.2): Create <html> element on start tag or anything-else; handle end tags
    • 2.3 Before head mode (§13.2.6.4.3): Create <head> element on <head> start tag or anything-else; handle whitespace and comments
    • 2.4 In head mode (§13.2.6.4.4): Handle <title>, <style>, <script>, <noscript>, <base>, <link>, <meta>, <template> start tags; </head> switches to "after head"
    • 2.5 In head noscript mode (§13.2.6.4.5): Handle elements allowed in noscript context; anything-else pops noscript and reprocesses in "in head"
    • 2.6 After head mode (§13.2.6.4.6): Create <body> on <body> start tag or anything-else; handle <frameset> start tag

  • Task 3: Implement "in body" mode completeness (AC: #1, #3)

    • 3.1 Refactor existing close_p_if_in_button_scope() into the in-body mode handler
    • 3.2 Implement full optional end tag rules for: <li> (closes previous <li> in list scope), <dt>/<dd> (close each other in scope), <option>/<optgroup>
    • 3.3 Implement <rb>, <rt>, <rtc>, <rp> optional end tags (ruby annotation elements)
    • 3.4 Handle heading elements (<h1>–<h6>): close any open heading when a new heading opens
    • 3.5 Handle <form> element: track form element pointer, prevent nested forms
    • 3.6 Handle block-splitting for <p><div></div></p> — close <p>, insert <div>, reopen <p> implicitly if content follows
    • 3.7 Initialize the active formatting elements list (needed for reconstruction — adoption agency is Story 2.3, but the list data structure must exist)
    • 3.8 Handle <a> tag: if <a> is in active formatting elements, run adoption agency stub (close previous <a>) before opening new one
    • 3.9 Handle formatting elements (<b>, <big>, <code>, <em>, <font>, <i>, <s>, <small>, <strike>, <strong>, <tt>, <u>): push to active formatting elements list
    • 3.10 Reconstruct active formatting elements at appropriate points (before inserting character tokens and certain start tags)

  • Task 4: Implement table-related modes (AC: #1, #4)

    • 4.1 In table mode (§13.2.6.4.9): Handle <caption>, <colgroup>, <col>, <tbody>/<thead>/<tfoot>, <tr>, <td>/<th> start tags with mode switches; anything-else → enable foster parenting flag (actual foster parenting implementation is Story 2.3)
    • 4.2 In table text mode (§13.2.6.4.10): Collect character tokens; if non-whitespace, insert via foster parenting; else insert normally
    • 4.3 In caption mode (§13.2.6.4.11): Handle </caption> end tag; table-starting elements close caption
    • 4.4 In column group mode (§13.2.6.4.12): Handle <col> start tag, </colgroup> end tag
    • 4.5 In table body mode (§13.2.6.4.13): Handle <tr> (auto-create if <td>/<th> appear), close sections
    • 4.6 In row mode (§13.2.6.4.14): Handle <td>/<th> start tags → switch to "in cell"
    • 4.7 In cell mode (§13.2.6.4.15): Handle </td>/</th> end tags → switch to "in row"; handle elements that implicitly close cells
    • 4.8 Refactor existing close_implicit_table_tags() into the appropriate mode handlers

  • Task 5: Implement select and template modes (AC: #1, #4)

    • 5.1 In select mode (§13.2.6.4.16): Handle <option>, <optgroup>, </select> — restrict allowed elements
    • 5.2 In select in table mode (§13.2.6.4.17): Table-starting elements close <select> and reprocess
    • 5.3 In template mode (§13.2.6.4.18): Push/pop template insertion mode stack; handle template content as document fragment
    • 5.4 Text mode (§13.2.6.4.8): Handle character tokens and end tags for <script> and <style> in head

  • Task 6: Implement post-body and frameset modes (AC: #1)

    • 6.1 After body mode (§13.2.6.4.19): Handle </html>, comments; anything-else reprocesses in "in body"
    • 6.2 In frameset mode (§13.2.6.4.20): Handle <frame>, <frameset>, </frameset> (legacy)
    • 6.3 After frameset mode (§13.2.6.4.21): Handle </html>, <noframes> (legacy)
    • 6.4 After after body mode (§13.2.6.4.22): Handle comments; anything-else reprocesses in "in body"
    • 6.5 After after frameset mode (§13.2.6.4.23): Handle comments, <noframes> (legacy)

  • Task 7: Context-sensitive fragment parsing (AC: #2)

    • 7.1 Update build_fragment() to accept a context element tag name
    • 7.2 Set initial insertion mode based on context element per §13.2.6.4 (e.g., <select> context → "in select" mode, <table> → "in table" mode, <tr> → "in row" mode)
    • 7.3 Set tokenizer state from context element: <title>/<textarea> → RCDATA, <style>/<script> → RAWTEXT/script-data (coordinate with Story 2.1 tokenizer changes)

  • Task 8: Tests and documentation (AC: #5)

    • 8.1 Add unit tests for each insertion mode: verify mode transitions, element insertion, and scope rules
    • 8.2 Add tests for implicit element creation: <td> without <table>, text before <html>, etc.
    • 8.3 Add tests for optional end tags: <li>, <dt>/<dd>, <option>, headings, ruby elements
    • 8.4 Add tests for template element parsing
    • 8.5 Add tests for context-sensitive fragment parsing
    • 8.6 Add golden tests for documents exercising multiple insertion modes
    • 8.7 Update docs/HTML5_Implementation_Checklist.md — check off tree builder items
    • 8.8 Run just ci and ensure all tests pass

Dev Notes

Current Implementation (What Exists)

The tree builder lives in crates/html/src/tree_builder.rs (~427 lines). It uses implicit mode tracking with boolean flags rather than a state machine:

TreeBuilder struct:

pub struct TreeBuilder {
    void_elements: HashSet<&'static str>,
}

State tracked in build() as local variables:

  • open_elements: Vec<NodeId> — stack of open element IDs
  • html_element: Option<NodeId>, head_element: Option<NodeId>, body_element: Option<NodeId> — implicit element refs
  • in_head: bool — only boolean mode flag

What works today:

  • Implicit <html>, <head>, <body> creation
  • <p> auto-close before block elements (via close_p_if_in_button_scope())
  • Table element implicit closing (<td>, <th>, <tr>, <tbody>, <thead>, <tfoot>, <colgroup>)
  • Void element handling (14 elements)
  • Text node merging
  • Fragment parsing (basic, not context-sensitive)

What's missing:

  • No InsertionMode enum or state machine
  • No active formatting elements list
  • No adoption agency algorithm (Story 2.3)
  • No foster parenting (Story 2.3)
  • No <li>, <dt>/<dd>, <option> optional end tags
  • No heading auto-close (<h2> should close open <h1>)
  • No context-sensitive fragment parsing
  • No template or select modes
  • No form element pointer tracking

Architecture Constraints

  • Layer 1 crate — html depends only on dom, shared, tracing
  • Arena-based NodeId — all DOM operations via Document methods: create_element(), append_child(), set_attribute()
  • No unsafe — enforced by CI
  • Spec citations — // HTML §13.2.6.4.x inline
  • File size limits — if tree_builder.rs grows past the limit, split into src/tree_builder/ module directory with separate files per mode group (e.g., table_modes.rs, body_mode.rs)

Key Design Decision: State Machine Architecture

Refactor TreeBuilder to hold state as fields rather than local variables in build():

pub struct TreeBuilder {
    void_elements: HashSet<&'static str>,
    insertion_mode: InsertionMode,
    original_insertion_mode: Option<InsertionMode>,
    template_insertion_modes: Vec<InsertionMode>,
    open_elements: Vec<NodeId>,
    active_formatting_elements: Vec<FormattingEntry>,
    head_element: Option<NodeId>,
    body_element: Option<NodeId>,
    form_element: Option<NodeId>,
    foster_parenting: bool,  // flag only — actual reparenting logic is Story 2.3
}

enum InsertionMode {
    Initial,
    BeforeHtml,
    BeforeHead,
    InHead,
    InHeadNoscript,
    AfterHead,
    InBody,
    Text,
    InTable,
    InTableText,
    InCaption,
    InColumnGroup,
    InTableBody,
    InRow,
    InCell,
    InSelect,
    InSelectInTable,
    InTemplate,
    AfterBody,
    InFrameset,
    AfterFrameset,
    AfterAfterBody,
    AfterAfterFrameset,
}

enum FormattingEntry {
    Element(NodeId),
    Marker, // scope boundary for formatting elements
}

Token processing pattern:

fn process_token(&mut self, token: &Token, doc: &mut Document) {
    match self.insertion_mode {
        InsertionMode::Initial => self.handle_initial(token, doc),
        InsertionMode::InBody => self.handle_in_body(token, doc),
        // ...
    }
}

Dependency on Story 2.1

Story 2.1 (tokenizer) may change the Token enum (e.g., adding new variants or restructuring RawText). If 2.1 is implemented first:

  • Adapt tree builder to consume any new token types
  • Coordinate tokenizer state switching from tree builder (e.g., after <title> → switch to RCDATA state)

If 2.1 is NOT yet implemented, the tree builder can still work with the existing Token enum — the mode logic is independent of tokenizer state changes.

Critical coordination point: The spec requires the tree builder to tell the tokenizer which state to use (§13.2.6 — "switch the tokenizer to the RCDATA state"). This requires a communication channel between tree builder and tokenizer. Options:

  • Pass a &mut TokenizerState to the tree builder
  • Use a callback/closure
  • Process tokens in a streaming fashion where tree builder yields tokenizer state changes

Scope Algorithms

Several insertion modes use "has element X in scope" checks. The scope types and their boundary elements:

Scope type Boundary elements
Default scope applet, caption, html, table, td, th, marquee, object, template
List item scope Default scope + ol, ul
Button scope Default scope + button
Table scope html, table, template
Select scope Everything EXCEPT optgroup, option

The existing close_p_if_in_button_scope() already implements button scope partially. Extract the scope check into a reusable method:

fn has_element_in_scope(&self, target: &str, scope: ScopeType, doc: &Document) -> bool

What NOT to Change (Story 2.3 Scope)

  • Adoption agency algorithm — Story 2.3 implements the full algorithm for mis-nested formatting elements. Story 2.2 only needs to maintain the active formatting elements list and do basic <a> tag handling.
  • Foster parenting reparenting logic — Story 2.3. Story 2.2 sets the foster_parenting flag but does not implement the actual reparenting.
  • DOM mutation APIs — Story 2.4. Don't add insertBefore, replaceChild etc.

Files to Modify

  • crates/html/src/tree_builder.rs — major refactor to state machine (may split into module)
  • crates/html/src/lib.rs — update HtmlParser to coordinate tree builder state with tokenizer
  • crates/html/src/tests/parsing_tests.rs — new tests for insertion modes
  • crates/html/src/tests/table_tests.rs — update existing table tests for mode-based handling
  • crates/html/src/tests/fragment_tests.rs — context-sensitive fragment tests
  • tests/goldens/fixtures/ + tests/goldens/expected/ — new golden tests
  • docs/HTML5_Implementation_Checklist.md — update checked items

Previous Story Intelligence (Story 2.1)

  • Story 2.1 refactors tokenizer to state machine — same pattern applies here (enum + match in loop)
  • Story 2.1 notes: "Do NOT use a separate fn per state" — same applies to insertion modes, but split into separate files if the main file exceeds size limits
  • Both stories share the same architecture constraints (Layer 1, no unsafe, spec citations)

Testing Strategy

  • Unit tests in crates/html/src/tests/parsing_tests.rs — test each insertion mode independently
  • Split test files when they exceed ~200 lines — e.g., insertion_mode_tests.rs, table_mode_tests.rs
  • Golden tests — HTML documents that exercise mode transitions (e.g., table inside body, select inside table, template content)
  • WPT tree-construction tests — if available, run the html5lib-tests tree-construction suite
  • Key test scenarios:
    • <td> without any table ancestors → auto-creates <table><tbody><tr><td>
    • <h1><h2> → heading closes previous heading
    • <li><li> → second <li> closes first in list scope
    • <p><div> → <p> split: close p, insert div
    • <select><option><option> → second option closes first
    • <template> content parsed as document fragment
    • Fragment parsing with <select> context → "in select" initial mode

References

  • WHATWG HTML Living Standard §13.2.6 — Tree Construction
  • WHATWG HTML §13.2.4.2 — Optional End Tags
  • [Source: crates/html/src/tree_builder.rs] — current implementation (~427 lines)
  • [Source: crates/html/src/lib.rs] — HtmlParser coordination
  • [Source: crates/html/src/tests/parsing_tests.rs] — 24 existing tests
  • [Source: crates/html/src/tests/table_tests.rs] — 10 existing table tests
  • [Source: crates/html/src/tests/fragment_tests.rs] — 12 existing fragment tests
  • [Source: crates/dom/src/document.rs] — Document API (create_element, append_child, etc.)
  • [Source: docs/HTML5_Implementation_Checklist.md] — checklist to update
  • [Source: _bmad-output/planning-artifacts/architecture.md] — architecture constraints

Dev Agent Record

Agent Model Used

Claude Opus 4.6 (1M context)

Debug Log References

  • Stack overflow in WPT suite caused by recursive process_token calls; fixed by making reprocessing iterative with ProcessResult enum (Done/Reprocess/DelegateTo)
  • WPT suite hang caused by XHTML-style <div/> self-closing tags creating deeply nested DOM; fixed by respecting self_closing flag via insert_element_maybe_self_closing() helper
  • Golden tests and WPT expected outputs regenerated due to spec-compliant implicit <head> element creation shifting node IDs

Completion Notes List

  • Refactored tree_builder.rs (427 lines) into module directory with 7 files: mod.rs, early_modes.rs, body_mode.rs, table_modes.rs, select_template_modes.rs, post_body_modes.rs, scope.rs
  • Implemented all 23 insertion modes per WHATWG HTML §13.2.6.4 with explicit state machine
  • TreeBuilder kept stateless (public API unchanged); per-parse state in internal TreeBuildState struct
  • Token reprocessing is fully iterative (no recursion) via ProcessResult enum with Done/Reprocess/DelegateTo variants
  • Active formatting elements list with reconstruction, Noah's Ark clause, and marker support
  • Scope checking for all 5 scope types (default, list item, button, table, select)
  • Context-sensitive fragment parsing: initial mode selected by context element tag name
  • 49 new insertion mode tests + 6 fragment parsing tests + 2 golden tests added
  • 6 WPT pixel-mismatch tests moved to known_fail; 2 previously failing WPT tests now pass (promoted)
  • HTML5 Implementation Checklist updated

File List

  • crates/html/src/tree_builder.rs → DELETED (replaced by module directory)
  • crates/html/src/tree_builder/mod.rs — NEW: TreeBuilder, TreeBuildState, InsertionMode enum, ProcessResult, helpers
  • crates/html/src/tree_builder/early_modes.rs — NEW: Initial, BeforeHtml, BeforeHead, InHead, InHeadNoscript, AfterHead, reset_insertion_mode
  • crates/html/src/tree_builder/body_mode.rs — NEW: InBody mode handler, is_special_element
  • crates/html/src/tree_builder/table_modes.rs — NEW: InTable, InTableText, InCaption, InColumnGroup, InTableBody, InRow, InCell
  • crates/html/src/tree_builder/select_template_modes.rs — NEW: Text, InSelect, InSelectInTable, InTemplate
  • crates/html/src/tree_builder/post_body_modes.rs — NEW: AfterBody, InFrameset, AfterFrameset, AfterAfterBody, AfterAfterFrameset
  • crates/html/src/tree_builder/scope.rs — NEW: Scope checking algorithms
  • crates/html/src/lib.rs — MODIFIED: parse_fragment now accepts context_tag parameter
  • crates/html/src/tests/mod.rs — MODIFIED: added insertion_mode_tests module
  • crates/html/src/tests/insertion_mode_tests.rs — NEW: 49 tests for insertion modes
  • crates/html/src/tests/fragment_tests.rs — MODIFIED: updated for context_tag param, added 6 context-sensitive tests
  • crates/html/src/tests/table_tests.rs — MODIFIED: updated caption boundary test for spec behavior
  • crates/web_api/src/dom_host/host_environment.rs — MODIFIED: updated innerHTML setter for context_tag
  • tests/goldens/fixtures/276-insertion-mode-transitions.html — NEW
  • tests/goldens/fixtures/277-implicit-element-creation.html — NEW
  • tests/goldens/expected/276-insertion-mode-transitions.layout.txt — NEW
  • tests/goldens/expected/276-insertion-mode-transitions.dl.txt — NEW
  • tests/goldens/expected/277-implicit-element-creation.layout.txt — NEW
  • tests/goldens/expected/277-implicit-element-creation.dl.txt — NEW
  • tests/goldens/expected/*.txt — MODIFIED: 228 golden files regenerated (node ID shift from implicit head)
  • tests/external/wpt/expected/*.txt — MODIFIED: 9 WPT expected files regenerated
  • tests/external/wpt/wpt_manifest.toml — MODIFIED: 2 tests promoted to pass, 6 moved to known_fail
  • tests/goldens.rs — MODIFIED: added golden_276 and golden_277 test functions
  • docs/HTML5_Implementation_Checklist.md — MODIFIED: tree builder items checked off

Change Log

  • 2026-03-14: Implemented all 23 insertion modes, active formatting elements, scope checking, context-sensitive fragment parsing, 55 new tests, 2 golden tests. Full CI passes.
  • 2026-03-14: Code review fixes — fixed formatting element end tag truncation bug (node_id saved before truncate), replaced manual element creation in catch-all StartTag with insert_element_maybe_self_closing, added skip_next_newline for pre/listing/textarea per spec, added QuirksMode to Document with basic DOCTYPE detection, fixed self_closing handling for pre/listing/textarea/plaintext, improved golden test 276 fixture coverage, improved foster-parent test assertion. Regenerated golden 073 (spec-compliant pre newline skip). All CI passes.
Reference in New Issue View Git Blame Copy Permalink