///|
/// HTML5 Tree Construction Algorithm
/// Based on WHATWG HTML5 Parsing Specification
///|
/// Insertion mode for tree construction
pub(all) 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
}
///|
/// Formatting element marker or element
pub(all) enum FormattingElement {
Element(Element)
Marker
}
///|
/// Tree Builder state machine
pub(all) struct TreeBuilder {
tokenizer : Tokenizer
mut insertion_mode : InsertionMode
mut original_insertion_mode : InsertionMode?
open_elements : Array[Element]
active_formatting : Array[FormattingElement]
mut foster_parenting : Bool
mut frameset_ok : Bool
mut head_element : Element?
mut pending_table_chars : Array[Char]
// Stack of "template insertion modes" parallel to the open elements stack:
// one entry is pushed per open , driving reset_insertion_mode and
// EOF handling inside template content.
template_insertion_modes : Array[InsertionMode]
// Text accumulation buffer for efficient character insertion
pending_text : StringBuilder
// Queue of tokens to reprocess (avoids stack overflow from recursive process_token calls)
pending_tokens : Array[Token]
}
///|
pub fn TreeBuilder::new(tokenizer : Tokenizer) -> TreeBuilder {
{
tokenizer,
insertion_mode: InsertionMode::Initial,
original_insertion_mode: None,
open_elements: [],
active_formatting: [],
foster_parenting: false,
frameset_ok: true,
head_element: None,
pending_table_chars: [],
template_insertion_modes: [],
pending_text: StringBuilder::new(),
pending_tokens: [],
}
}
///|
/// Queue a token for reprocessing (instead of recursive process_token call)
fn TreeBuilder::reprocess_token(self : TreeBuilder, token : Token) -> Unit {
self.pending_tokens.push(token)
}
///|
/// Get current element (top of stack)
fn TreeBuilder::current_node(self : TreeBuilder) -> Element? {
if self.open_elements.is_empty() {
None
} else {
Some(self.open_elements[self.open_elements.length() - 1])
}
}
///|
/// Check if tag is in scope
fn TreeBuilder::has_element_in_scope(self : TreeBuilder, tag : String) -> Bool {
for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
let elem = self.open_elements[i]
if elem.tag == tag {
return true
}
// Scope boundary elements
if is_scope_boundary(elem.tag) {
return false
}
}
false
}
///|
/// Check if tag is in table scope
fn TreeBuilder::has_element_in_table_scope(
self : TreeBuilder,
tag : String,
) -> Bool {
for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
let elem = self.open_elements[i]
if elem.tag == tag {
return true
}
// Table scope boundary
if elem.tag == "html" || elem.tag == "table" || elem.tag == "template" {
return false
}
}
false
}
///|
/// Scope boundary elements
fn is_scope_boundary(tag : String) -> Bool {
match tag {
"applet"
| "caption"
| "html"
| "table"
| "td"
| "th"
| "marquee"
| "object"
| "template" => true
_ => false
}
}
///|
/// Create element from tag name and attributes
fn create_element(tag : String, attrs : Map[String, String]) -> Element {
let id = attrs.get("id")
let classes = match attrs.get("class") {
Some(class_str) => {
let parts : Array[String] = []
for part in class_str.split(" ") {
let s = part.to_owned().trim()
if !s.is_empty() {
parts.push(s.to_owned())
}
}
parts
}
None => []
}
let style = attrs.get("style")
{ tag, id, classes, style, attributes: attrs, children: [] }
}
///|
/// Insert element at appropriate place
fn TreeBuilder::insert_element(self : TreeBuilder, element : Element) -> Unit {
// Security: reject excessive nesting depth
if self.open_elements.length() >= max_nesting_depth {
return
}
// Flush any pending text before inserting element
self.flush_pending_text(next_tag=Some(element.tag))
if self.foster_parenting && is_table_context(self.current_node()) {
self.foster_parent_element(element)
} else {
match self.current_node() {
Some(current) => current.children.push(Node::Element(element))
None => ()
}
}
self.open_elements.push(element)
}
///|
/// Insert metadata/raw-text element into the stored element even when the
/// current insertion mode is in-body.
fn TreeBuilder::insert_into_head(
self : TreeBuilder,
element : Element,
push_to_stack : Bool,
) -> Unit {
self.flush_pending_text(next_tag=Some(element.tag))
match self.head_element {
Some(head) => head.children.push(Node::Element(element))
None =>
match self.current_node() {
Some(current) => current.children.push(Node::Element(element))
None => ()
}
}
if push_to_stack {
self.open_elements.push(element)
}
}
///|
/// Insert character at appropriate place - accumulates in pending_text buffer
fn TreeBuilder::insert_character(self : TreeBuilder, c : Char) -> Unit {
if self.foster_parenting && is_table_context(self.current_node()) {
// Flush any pending text before foster parenting
self.flush_pending_text()
self.foster_parent_character(c)
} else {
// Accumulate character in buffer
self.pending_text.write_char(c)
}
}
///|
/// Insert multiple characters at once - optimized batch insertion
fn TreeBuilder::insert_characters(self : TreeBuilder, s : String) -> Unit {
if self.foster_parenting && is_table_context(self.current_node()) {
// Flush any pending text before foster parenting
self.flush_pending_text()
// Foster parent each character
for c in s {
self.foster_parent_character(c)
}
} else {
// Accumulate all characters in buffer
self.pending_text.write_string(s)
}
}
///|
/// Flush pending text buffer to current element
fn TreeBuilder::flush_pending_text(
self : TreeBuilder,
next_tag? : String? = None,
) -> Unit {
if self.pending_text.is_empty() {
return
}
let raw_text = self.pending_text.to_string()
self.pending_text.reset()
// Decode HTML entities
let text = decode_html_entities(raw_text)
match self.current_node() {
Some(current) => {
// Try to append to last text node
let len = current.children.length()
if len > 0 {
match current.children[len - 1] {
Node::Text(existing) => {
current.children[len - 1] = Node::Text(existing + text)
return
}
_ => ()
}
}
// Skip whitespace-only text nodes between elements
// while preserving one collapsed space for later layout decisions.
if is_whitespace_only(text) {
let keep_space_only_leaf_text = next_tag is None &&
current.children.length() == 0 &&
is_plain_space_only(text)
if should_preserve_inline_inter_element_whitespace(current, next_tag) ||
keep_space_only_leaf_text {
current.children.push(Node::Text(" "))
}
return
}
current.children.push(Node::Text(text))
}
None => ()
}
}
///|
/// Keep a single collapsed whitespace when it appears between element siblings.
/// Whether it contributes to layout is decided later from computed display values.
fn should_preserve_inline_inter_element_whitespace(
current : Element,
next_tag : String?,
) -> Bool {
let prev_len = current.children.length()
if prev_len == 0 {
return false
}
let has_next_element = match next_tag {
Some(_) => true
None => false
}
if !has_next_element {
return false
}
match current.children[prev_len - 1] {
Node::Element(_) => true
Node::Text(_) => false
}
}
///|
/// Check if string contains only whitespace
fn is_whitespace_only(s : String) -> Bool {
for c in s {
if !tb_is_whitespace(c) {
return false
}
}
true
}
///|
fn is_plain_space_only(s : String) -> Bool {
if s.is_empty() {
return false
}
for c in s {
if c != ' ' {
return false
}
}
true
}
///|
/// Check if character is whitespace
fn tb_is_whitespace(c : Char) -> Bool {
c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\u000C'
}
///|
/// Check if element is table context for foster parenting
fn is_table_context(elem : Element?) -> Bool {
match elem {
Some(e) =>
match e.tag {
"table" | "tbody" | "tfoot" | "thead" | "tr" => true
_ => false
}
None => false
}
}
///|
/// Foster parent an element (insert before table)
fn TreeBuilder::foster_parent_element(
self : TreeBuilder,
element : Element,
) -> Unit {
// Find the table in the stack
let mut table_idx = -1
for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
if self.open_elements[i].tag == "table" {
table_idx = i
break
}
}
if table_idx > 0 {
// Insert before the table in its parent
let parent = self.open_elements[table_idx - 1]
// Find position of table in parent's children
let mut table_pos = -1
for i = 0; i < parent.children.length(); i = i + 1 {
match parent.children[i] {
Node::Element(e) if e.tag == "table" => {
table_pos = i
break
}
_ => ()
}
}
if table_pos >= 0 {
// Insert before table
parent.children.insert(table_pos, Node::Element(element))
} else {
// Table not found in parent, append
parent.children.push(Node::Element(element))
}
} else if table_idx == 0 {
// Table is at root, just add element before it in open_elements
// This is an edge case - shouldn't normally happen
()
}
}
///|
/// Foster parent a character
fn TreeBuilder::foster_parent_character(self : TreeBuilder, c : Char) -> Unit {
// Find the table in the stack
let mut table_idx = -1
for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
if self.open_elements[i].tag == "table" {
table_idx = i
break
}
}
if table_idx > 0 {
let parent = self.open_elements[table_idx - 1]
// Find position of table in parent's children
let mut table_pos = -1
for i = 0; i < parent.children.length(); i = i + 1 {
match parent.children[i] {
Node::Element(e) if e.tag == "table" => {
table_pos = i
break
}
_ => ()
}
}
if table_pos >= 0 {
// Check if there's a text node just before the table
if table_pos > 0 {
match parent.children[table_pos - 1] {
Node::Text(existing) => {
parent.children[table_pos - 1] = Node::Text(
existing + c.to_string(),
)
return
}
_ => ()
}
}
// Insert new text node before table
parent.children.insert(table_pos, Node::Text(c.to_string()))
} else {
// Append to parent
parent.children.push(Node::Text(c.to_string()))
}
}
}
///|
/// Pop elements until we hit a specific tag
fn TreeBuilder::pop_until(self : TreeBuilder, tag : String) -> Unit {
// Flush pending text to current element before popping
self.flush_pending_text()
while !self.open_elements.is_empty() {
let elem = self.open_elements.pop()
match elem {
Some(e) if e.tag == tag => break
_ => ()
}
}
}
///|
/// Generate implied end tags
fn TreeBuilder::generate_implied_end_tags(self : TreeBuilder) -> Unit {
while !self.open_elements.is_empty() {
match self.current_node() {
Some(e) =>
match e.tag {
"dd"
| "dt"
| "li"
| "optgroup"
| "option"
| "p"
| "rb"
| "rp"
| "rt"
| "rtc" => {
let _ = self.open_elements.pop()
}
_ => break
}
None => break
}
}
}
///|
/// Generate implied end tags except for a specific tag
fn TreeBuilder::generate_implied_end_tags_except(
self : TreeBuilder,
except : String,
) -> Unit {
while !self.open_elements.is_empty() {
match self.current_node() {
Some(e) if e.tag == except => break
Some(e) =>
match e.tag {
"dd"
| "dt"
| "li"
| "optgroup"
| "option"
| "p"
| "rb"
| "rp"
| "rt"
| "rtc" => {
let _ = self.open_elements.pop()
}
_ => break
}
None => break
}
}
}
///|
/// Check if tag is special element
fn is_special_element(tag : String) -> Bool {
match tag {
"address"
| "applet"
| "area"
| "article"
| "aside"
| "base"
| "basefont"
| "bgsound"
| "blockquote"
| "body"
| "br"
| "button"
| "caption"
| "center"
| "col"
| "colgroup"
| "dd"
| "details"
| "dir"
| "div"
| "dl"
| "dt"
| "embed"
| "fieldset"
| "figcaption"
| "figure"
| "footer"
| "form"
| "frame"
| "frameset"
| "h1"
| "h2"
| "h3"
| "h4"
| "h5"
| "h6"
| "head"
| "header"
| "hgroup"
| "hr"
| "html"
| "iframe"
| "img"
| "input"
| "keygen"
| "li"
| "link"
| "listing"
| "main"
| "marquee"
| "menu"
| "meta"
| "nav"
| "noembed"
| "noframes"
| "noscript"
| "object"
| "ol"
| "p"
| "param"
| "plaintext"
| "pre"
| "script"
| "section"
| "select"
| "source"
| "style"
| "summary"
| "table"
| "tbody"
| "td"
| "template"
| "textarea"
| "tfoot"
| "th"
| "thead"
| "title"
| "tr"
| "track"
| "ul"
| "wbr"
| "xmp" => true
_ => false
}
}
///|
/// Run the tree construction algorithm for fragment parsing
/// Starts in InBody mode with pre-created html/head/body structure
pub fn TreeBuilder::build(self : TreeBuilder) -> Element {
// Create initial document structure
let html_elem = create_element("html", {})
let head_elem = create_element("head", {})
let body_elem = create_element("body", {})
html_elem.children.push(Node::Element(head_elem))
html_elem.children.push(Node::Element(body_elem))
self.open_elements.push(html_elem)
self.open_elements.push(body_elem)
self.head_element = Some(head_elem)
self.insertion_mode = InsertionMode::InBody
// Process tokens using queue to avoid stack overflow
while true {
let token = self.tokenizer.next_token()
match token {
Token::EOF => break
_ => {
self.process_token_single(token)
// Process any requeued tokens iteratively
while !self.pending_tokens.is_empty() {
let next = self.pending_tokens.remove(0)
self.process_token_single(next)
}
}
}
}
// Flush any remaining pending text
self.flush_pending_text()
html_elem
}
///|
/// Run the tree construction algorithm for full document parsing
/// Starts in Initial mode and builds structure from tokens
pub fn TreeBuilder::build_document(self : TreeBuilder) -> Element {
self.insertion_mode = InsertionMode::Initial
// Process tokens using queue to avoid stack overflow
while true {
let token = self.tokenizer.next_token()
match token {
Token::EOF => break
_ => {
self.process_token_single(token)
// Process any requeued tokens iteratively
while !self.pending_tokens.is_empty() {
let next = self.pending_tokens.remove(0)
self.process_token_single(next)
}
}
}
}
// Flush any remaining pending text
self.flush_pending_text()
// Return html element (first in open_elements or create one)
match self.open_elements.get(0) {
Some(elem) => elem
None => {
// Fallback: create minimal structure
let html = create_element("html", {})
let body = create_element("body", {})
html.children.push(Node::Element(body))
html
}
}
}
///|
/// Process a single token (internal - handlers may requeue tokens)
fn TreeBuilder::process_token_single(self : TreeBuilder, token : Token) -> Unit {
// `` closes its (inert, scope-bounded) template subtree regardless
// of the insertion mode its content switched into (a nested