// Copyright 2025 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

///|
/// 23 tree construction insertion modes (WHATWG 13.2.6)
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
}

///|
/// Entry in the stack of open elements
struct StackEntry {
  node_id : Int
  tag_name : String
  ns : Namespace
}

///|
/// Marker or Element entry in the active formatting elements list
enum FormattingEntry {
  Marker
  Element(
    node_id~ : Int,
    tag_name~ : String,
    attributes~ : Array[(String, String)]
  )
}

///|
/// The HTML tree builder (WHATWG 13.2.6)
pub struct TreeBuilder {
  tokenizer : Tokenizer
  document : Document
  // Stack of open elements (WHATWG 13.2.4.2)
  open_elements : Array[StackEntry]
  // Active formatting elements (WHATWG 13.2.4.3)
  active_formatting : Array[FormattingEntry]
  // Current insertion mode
  mut mode : InsertionMode
  // Original insertion mode (for "text" and "in table text" modes)
  mut original_mode : InsertionMode
  // Template insertion modes stack
  template_modes : Array[InsertionMode]
  // Head element pointer
  mut head_element : Int
  // Form element pointer
  mut form_element : Int
  // Scripting flag (for noscript handling)
  scripting : Bool
  // Frameset-ok flag
  mut frameset_ok : Bool
  // Foster parenting mode
  mut foster_parenting : Bool
  // Pending table character tokens
  pending_table_chars : Array[Char]
  // Skip newline flag after 
, , <listing>
  mut skip_next_newline : Bool
  // Parsing errors
  errors : Array[ParseError]
}

///|
/// Create a new tree builder for parsing HTML
pub fn TreeBuilder::new(html : String) -> TreeBuilder {
  TreeBuilder::new_with_options(html, scripting=false)
}

///|
/// Create a new tree builder with options
pub fn TreeBuilder::new_with_options(
  html : String,
  scripting~ : Bool,
) -> TreeBuilder {
  let document = Document::new()
  document.scripting_enabled = scripting
  {
    tokenizer: Tokenizer::new(html),
    document,
    open_elements: [],
    active_formatting: [],
    mode: Initial,
    original_mode: Initial,
    template_modes: [],
    head_element: NO_NODE,
    form_element: NO_NODE,
    scripting,
    frameset_ok: true,
    foster_parenting: false,
    pending_table_chars: [],
    skip_next_newline: false,
    errors: [],
  }
}

///|
/// Parse the document and return it
pub fn TreeBuilder::parse(self : TreeBuilder) -> Document {
  // Main parsing loop
  while true {
    // Update tokenizer's foreign content flag based on current node
    self.tokenizer.in_foreign_content = self.is_in_foreign_content()
    let mut token = self.tokenizer.next_token()
    // Skip leading newline after pre/listing/textarea
    if self.skip_next_newline {
      self.skip_next_newline = false
      match token {
        Character('\n') => continue
        _ => ()
      }
    }
    // Process token, reprocessing if needed
    while true {
      let reprocess = self.process_token(token)
      if !reprocess {
        break
      }
      // Reprocess same token in new mode
    }
    // Handle EOF
    match token {
      EOF => break
      _ => ()
    }
  }
  // Collect tokenizer errors
  for err in self.tokenizer.errors {
    self.errors.push(err)
  }
  self.finalize_select_selectedcontent()
  self.document
}

///|
fn TreeBuilder::finalize_select_selectedcontent(self : TreeBuilder) -> Unit {
  let mut stack : Array[Int] = [0]
  while stack.length() > 0 {
    let id = stack.remove(stack.length() - 1)
    match self.document.get_node(id) {
      Some(DocumentNode(children~)) =>
        for i = children.length() - 1; i >= 0; i = i - 1 {
          stack.push(children[i])
        }
      Some(DocumentFragmentNode(children~)) =>
        for i = children.length() - 1; i >= 0; i = i - 1 {
          stack.push(children[i])
        }
      Some(ElementNode(elem)) => {
        if elem.ns == HTML && elem.tag_name == "select" {
          self.populate_selectedcontent_for_select(id)
        }
        let children = elem.children.copy()
        for i = children.length() - 1; i >= 0; i = i - 1 {
          stack.push(children[i])
        }
        if elem.tag_name == "template" && elem.template_content != NO_NODE {
          stack.push(elem.template_content)
        }
      }
      _ => ()
    }
  }
}

///|
fn TreeBuilder::populate_selectedcontent_for_select(
  self : TreeBuilder,
  select_id : Int,
) -> Unit {
  let mut options : Array[Int] = []
  let mut selected_option : Int = NO_NODE
  let mut placeholders : Array[Int] = []
  let mut stack : Array[(Int, Bool)] = []
  let root_children = self.document.get_children(select_id)
  for i = root_children.length() - 1; i >= 0; i = i - 1 {
    stack.push((root_children[i], false))
  }
  while stack.length() > 0 {
    let (id, in_button) = stack.remove(stack.length() - 1)
    match self.document.get_node(id) {
      Some(DocumentFragmentNode(children~)) =>
        for i = children.length() - 1; i >= 0; i = i - 1 {
          stack.push((children[i], in_button))
        }
      Some(ElementNode(elem)) => {
        if elem.ns != HTML {
          continue
        }
        if elem.tag_name == "select" {
          continue
        }
        let in_button2 = in_button || elem.tag_name == "button"
        if elem.tag_name == "option" {
          options.push(id)
          if selected_option == NO_NODE &&
            self.document.has_attribute(id, "selected") {
            selected_option = id
          }
        }
        if elem.tag_name == "selectedcontent" && in_button2 {
          placeholders.push(id)
        }
        let children = elem.children.copy()
        for i = children.length() - 1; i >= 0; i = i - 1 {
          stack.push((children[i], in_button2))
        }
        if elem.tag_name == "template" && elem.template_content != NO_NODE {
          stack.push((elem.template_content, in_button2))
        }
      }
      _ => ()
    }
  }
  if placeholders.length() == 0 {
    return
  }
  let effective_option = if selected_option != NO_NODE {
    selected_option
  } else if options.length() > 0 {
    options[0]
  } else {
    return
  }
  let option_children = self.document.get_children(effective_option)
  for placeholder_id in placeholders {
    self.clear_children(placeholder_id)
    for child_id in option_children {
      self.clone_node_into(child_id, placeholder_id)
    }
  }
}

///|
fn TreeBuilder::clear_children(self : TreeBuilder, parent_id : Int) -> Unit {
  let children = self.document.get_children(parent_id)
  for child_id in children {
    self.document.remove_child(parent_id, child_id)
  }
}

///|
fn TreeBuilder::clone_node_into(
  self : TreeBuilder,
  src_id : Int,
  dest_parent_id : Int,
) -> Unit {
  match self.document.get_node(src_id) {
    Some(TextNode(text)) => {
      let new_id = self.document.add_node(TextNode(text))
      self.document.append_child(dest_parent_id, new_id)
    }
    Some(CommentNode(text)) => {
      let new_id = self.document.add_node(CommentNode(text))
      self.document.append_child(dest_parent_id, new_id)
    }
    Some(DocumentFragmentNode(children~)) => {
      let children = children.copy()
      for child_id in children {
        self.clone_node_into(child_id, dest_parent_id)
      }
    }
    Some(ElementNode(elem)) => {
      let mut new_elem : Element = {
        tag_name: elem.tag_name,
        ns: elem.ns,
        attributes: elem.attributes.copy(),
        children: [],
        parent: NO_NODE,
        is_html_integration_point: elem.is_html_integration_point,
        is_mathml_text_integration_point: elem.is_mathml_text_integration_point,
        template_content: NO_NODE,
      }
      if elem.tag_name == "template" && elem.template_content != NO_NODE {
        let frag_id = self.document.add_node(DocumentFragmentNode(children=[]))
        new_elem.template_content = frag_id
        let new_id = self.document.add_node(ElementNode(new_elem))
        self.document.append_child(dest_parent_id, new_id)
        let frag_children = self.document.get_children(elem.template_content)
        for child_id in frag_children {
          self.clone_node_into(child_id, frag_id)
        }
      } else {
        let new_id = self.document.add_node(ElementNode(new_elem))
        self.document.append_child(dest_parent_id, new_id)
        let children = elem.children.copy()
        for child_id in children {
          self.clone_node_into(child_id, new_id)
        }
      }
    }
    _ => ()
  }
}

///|
/// Determine the document's quirks mode based on DOCTYPE (WHATWG 13.2.6.4.1)
fn TreeBuilder::determine_quirks_mode(
  self : TreeBuilder,
  name : String?,
  public_id : String?,
  system_id : String?,
  force_quirks : Bool,
) -> QuirksMode {
  // Force quirks mode
  if force_quirks {
    return Quirks
  }
  // Name must be "html"
  if name != Some("html") {
    return Quirks
  }
  // Check public identifiers that trigger quirks mode
  match public_id {
    Some(pub_id) => {
      let pub_lower = pub_id.to_lower()
      // Exact matches that trigger quirks
      if pub_lower == "-//w3o//dtd w3 html strict 3.0//en//" ||
        pub_lower == "-/w3c/dtd html 4.0 transitional/en" ||
        pub_lower == "html" {
        return Quirks
      }
      // Prefix matches that trigger quirks
      if pub_lower.has_prefix("+//silmaril//dtd html pro v0r11 19970101//") ||
        pub_lower.has_prefix("-//as//dtd html 3.0 aswedit + extensions//") ||
        pub_lower.has_prefix(
          "-//advasoft ltd//dtd html 3.0 aswedit + extensions//",
        ) ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0 level 1//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0 level 2//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0 strict level 1//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0 strict level 2//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0 strict//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.0//") ||
        pub_lower.has_prefix("-//ietf//dtd html 2.1e//") ||
        pub_lower.has_prefix("-//ietf//dtd html 3.0//") ||
        pub_lower.has_prefix("-//ietf//dtd html 3.2 final//") ||
        pub_lower.has_prefix("-//ietf//dtd html 3.2//") ||
        pub_lower.has_prefix("-//ietf//dtd html 3//") ||
        pub_lower.has_prefix("-//ietf//dtd html level 0//") ||
        pub_lower.has_prefix("-//ietf//dtd html level 1//") ||
        pub_lower.has_prefix("-//ietf//dtd html level 2//") ||
        pub_lower.has_prefix("-//ietf//dtd html level 3//") ||
        pub_lower.has_prefix("-//ietf//dtd html strict level 0//") ||
        pub_lower.has_prefix("-//ietf//dtd html strict level 1//") ||
        pub_lower.has_prefix("-//ietf//dtd html strict level 2//") ||
        pub_lower.has_prefix("-//ietf//dtd html strict level 3//") ||
        pub_lower.has_prefix("-//ietf//dtd html strict//") ||
        pub_lower.has_prefix("-//ietf//dtd html//") ||
        pub_lower.has_prefix("-//metrius//dtd metrius presentational//") ||
        pub_lower.has_prefix(
          "-//microsoft//dtd internet explorer 2.0 html strict//",
        ) ||
        pub_lower.has_prefix("-//microsoft//dtd internet explorer 2.0 html//") ||
        pub_lower.has_prefix("-//microsoft//dtd internet explorer 2.0 tables//") ||
        pub_lower.has_prefix(
          "-//microsoft//dtd internet explorer 3.0 html strict//",
        ) ||
        pub_lower.has_prefix("-//microsoft//dtd internet explorer 3.0 html//") ||
        pub_lower.has_prefix("-//microsoft//dtd internet explorer 3.0 tables//") ||
        pub_lower.has_prefix("-//netscape comm. corp.//dtd html//") ||
        pub_lower.has_prefix("-//netscape comm. corp.//dtd strict html//") ||
        pub_lower.has_prefix("-//o'reilly and associates//dtd html 2.0//") ||
        pub_lower.has_prefix(
          "-//o'reilly and associates//dtd html extended 1.0//",
        ) ||
        pub_lower.has_prefix(
          "-//o'reilly and associates//dtd html extended relaxed 1.0//",
        ) ||
        pub_lower.has_prefix("-//sq//dtd html 2.0 hotmetal + extensions//") ||
        pub_lower.has_prefix(
          "-//softquad software//dtd hotmetal pro 6.0::19990601::extensions to html 4.0//",
        ) ||
        pub_lower.has_prefix(
          "-//softquad//dtd hotmetal pro 4.0::19971010::extensions to html 4.0//",
        ) ||
        pub_lower.has_prefix("-//spyglass//dtd html 2.0 extended//") ||
        pub_lower.has_prefix("-//sun microsystems corp.//dtd hotjava html//") ||
        pub_lower.has_prefix(
          "-//sun microsystems corp.//dtd hotjava strict html//",
        ) ||
        pub_lower.has_prefix("-//w3c//dtd html 3 1995-03-24//") ||
        pub_lower.has_prefix("-//w3c//dtd html 3.2 draft//") ||
        pub_lower.has_prefix("-//w3c//dtd html 3.2 final//") ||
        pub_lower.has_prefix("-//w3c//dtd html 3.2//") ||
        pub_lower.has_prefix("-//w3c//dtd html 3.2s draft//") ||
        pub_lower.has_prefix("-//w3c//dtd html 4.0 frameset//") ||
        pub_lower.has_prefix("-//w3c//dtd html 4.0 transitional//") ||
        pub_lower.has_prefix("-//w3c//dtd html experimental 19960712//") ||
        pub_lower.has_prefix("-//w3c//dtd html experimental 970421//") ||
        pub_lower.has_prefix("-//w3c//dtd w3 html//") ||
        pub_lower.has_prefix("-//w3o//dtd w3 html 3.0//") ||
        pub_lower.has_prefix("-//webtechs//dtd mozilla html 2.0//") ||
        pub_lower.has_prefix("-//webtechs//dtd mozilla html//") {
        return Quirks
      }
      // Quirks mode if public ID starts with these AND no system ID
      if system_id is None {
        if pub_lower.has_prefix("-//w3c//dtd html 4.01 frameset//") ||
          pub_lower.has_prefix("-//w3c//dtd html 4.01 transitional//") {
          return Quirks
        }
      }
      // Limited quirks mode checks
      if pub_lower.has_prefix("-//w3c//dtd xhtml 1.0 frameset//") ||
        pub_lower.has_prefix("-//w3c//dtd xhtml 1.0 transitional//") {
        return LimitedQuirks
      }
      // Limited quirks with system ID
      if system_id is Some(_) {
        if pub_lower.has_prefix("-//w3c//dtd html 4.01 frameset//") ||
          pub_lower.has_prefix("-//w3c//dtd html 4.01 transitional//") {
          return LimitedQuirks
        }
      }
    }
    None => ()
  }
  // Check system identifier
  match system_id {
    Some(sys_id) => {
      let sys_lower = sys_id.to_lower()
      if sys_lower ==
        "http://www.ibm.com/data/dtd/v11/ibmxhtml1-transitional.dtd" {
        return Quirks
      }
    }
    None => ()
  }
  NoQuirks
}

///|
/// Process a token in the current insertion mode
/// Returns true if the token should be reprocessed
fn TreeBuilder::process_token(self : TreeBuilder, token : Token) -> Bool {
  match token {
    ProcessingInstruction(target~, data~) => {
      self.insert_processing_instruction(target, data)
      return false
    }
    _ => ()
  }
  // Check for foreign content processing
  if self.should_process_in_foreign_content(token) {
    return self.process_in_foreign_content(token)
  }
  // Dispatch to current insertion mode
  self.process_token_in_html_mode(token)
}

///|
/// Process a token using HTML rules (skipping foreign content check)
/// Used when falling back from foreign content to HTML processing
fn TreeBuilder::process_token_in_html_mode(
  self : TreeBuilder,
  token : Token,
) -> Bool {
  match self.mode {
    Initial => self.process_initial_mode(token)
    BeforeHtml => self.process_before_html_mode(token)
    BeforeHead => self.process_before_head_mode(token)
    InHead => self.process_in_head_mode(token)
    InHeadNoscript => self.process_in_head_noscript_mode(token)
    AfterHead => self.process_after_head_mode(token)
    InBody => self.process_in_body_mode(token)
    Text => self.process_text_mode(token)
    InTable => self.process_in_table_mode(token)
    InTableText => self.process_in_table_text_mode(token)
    InCaption => self.process_in_caption_mode(token)
    InColumnGroup => self.process_in_column_group_mode(token)
    InTableBody => self.process_in_table_body_mode(token)
    InRow => self.process_in_row_mode(token)
    InCell => self.process_in_cell_mode(token)
    InSelect => self.process_in_select_mode(token)
    InSelectInTable => self.process_in_select_in_table_mode(token)
    InTemplate => self.process_in_template_mode(token)
    AfterBody => self.process_after_body_mode(token)
    InFrameset => self.process_in_frameset_mode(token)
    AfterFrameset => self.process_after_frameset_mode(token)
    AfterAfterBody => self.process_after_after_body_mode(token)
    AfterAfterFrameset => self.process_after_after_frameset_mode(token)
  }
}

///|
/// Check if the current node is in foreign content (SVG or MathML namespace)
/// Used to tell the tokenizer whether to handle CDATA sections
fn TreeBuilder::is_in_foreign_content(self : TreeBuilder) -> Bool {
  if self.open_elements.is_empty() {
    return false
  }
  let current = self.current_node()
  current.ns != HTML
}

///|
/// Check if we should process token in foreign content
fn TreeBuilder::should_process_in_foreign_content(
  self : TreeBuilder,
  token : Token,
) -> Bool {
  // If stack is empty or current node is HTML, don't use foreign content
  if self.open_elements.is_empty() {
    return false
  }
  let current = self.current_node()
  if current.ns == HTML {
    return false
  }
  // Check for MathML text integration point
  if self.is_mathml_text_integration_point(current) {
    match token {
      StartTag(name~, ..) =>
        if name != "mglyph" && name != "malignmark" {
          return false
        }
      Character(_) => return false
      _ => ()
    }
  }
  // Check for annotation-xml with encoding
  if current.tag_name == "annotation-xml" && current.ns == MathML {
    match token {
      StartTag(name~, ..) if name == "svg" => return false
      _ => ()
    }
  }
  // Check for HTML integration point
  if self.is_html_integration_point(current) {
    match token {
      StartTag(_) => return false
      Character(_) => return false
      _ => ()
    }
  }
  // EOF always processed by current mode
  match token {
    EOF => return false
    _ => ()
  }
  true
}

///|
/// Check if element is a MathML text integration point
fn TreeBuilder::is_mathml_text_integration_point(
  self : TreeBuilder,
  entry : StackEntry,
) -> Bool {
  entry.ns == MathML &&
  (
    entry.tag_name == "mi" ||
    entry.tag_name == "mo" ||
    entry.tag_name == "mn" ||
    entry.tag_name == "ms" ||
    entry.tag_name == "mtext"
  )
}

///|
/// Check if element is an HTML integration point
fn TreeBuilder::is_html_integration_point(
  self : TreeBuilder,
  entry : StackEntry,
) -> Bool {
  // SVG foreignObject, desc, title
  if entry.ns == SVG {
    return entry.tag_name == "foreignObject" ||
      entry.tag_name == "desc" ||
      entry.tag_name == "title"
  }
  // MathML annotation-xml with text/html or application/xhtml+xml encoding
  if entry.ns == MathML && entry.tag_name == "annotation-xml" {
    match self.document.get_attribute(entry.node_id, "encoding") {
      Some(enc) => {
        let lower_enc = enc.to_lower()
        return lower_enc == "text/html" || lower_enc == "application/xhtml+xml"
      }
      None => return false
    }
  }
  false
}

// ============================================================================
// Stack of Open Elements operations (WHATWG 13.2.4.2)
// ============================================================================

///|
/// Get the current node (last element in stack)
fn TreeBuilder::current_node(self : TreeBuilder) -> StackEntry {
  self.open_elements[self.open_elements.length() - 1]
}

///|
/// Push an element onto the stack
fn TreeBuilder::push_element(
  self : TreeBuilder,
  node_id : Int,
  tag_name : String,
  ns : Namespace,
) -> Unit {
  self.open_elements.push({ node_id, tag_name, ns, })
}

///|
/// Pop the current element from the stack
fn TreeBuilder::pop_element(self : TreeBuilder) -> StackEntry {
  self.open_elements.pop().unwrap()
}

///|
/// Pop elements until we find one with the given tag name (HTML namespace)
fn TreeBuilder::pop_until(self : TreeBuilder, tag_name : String) -> Unit {
  while self.open_elements.length() > 0 {
    let entry = self.pop_element()
    // Only match HTML elements for pop_until
    if entry.tag_name == tag_name && entry.ns == HTML {
      break
    }
  }
}

///|
/// Check if an element with the given tag is in scope
fn TreeBuilder::in_scope(
  self : TreeBuilder,
  tag_name : String,
  scope_elements : Array[String],
) -> Bool {
  for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
    let entry = self.open_elements[i]
    if entry.tag_name == tag_name && entry.ns == HTML {
      return true
    }
    // HTML scope-containing elements
    if scope_elements.contains(entry.tag_name) && entry.ns == HTML {
      return false
    }
    // Specific MathML elements are scope-containing
    if entry.ns == MathML {
      if entry.tag_name == "mi" ||
        entry.tag_name == "mo" ||
        entry.tag_name == "mn" ||
        entry.tag_name == "ms" ||
        entry.tag_name == "mtext" ||
        entry.tag_name == "annotation-xml" {
        return false
      }
    }
    // Specific SVG elements are scope-containing
    if entry.ns == SVG {
      if entry.tag_name == "foreignObject" ||
        entry.tag_name == "desc" ||
        entry.tag_name == "title" {
        return false
      }
    }
  }
  false
}

///|
/// Default scope elements for "in scope" checks
fn default_scope_elements() -> Array[String] {
  [
    "applet", "caption", "html", "table", "td", "th", "marquee", "object", "template",
  ]
}

///|
/// Check if tag is in default scope
fn TreeBuilder::in_default_scope(self : TreeBuilder, tag_name : String) -> Bool {
  self.in_scope(tag_name, default_scope_elements())
}

///|
/// Button scope elements
fn button_scope_elements() -> Array[String] {
  let mut elems = default_scope_elements()
  elems.push("button")
  elems
}

///|
/// Check if tag is in button scope
fn TreeBuilder::in_button_scope(self : TreeBuilder, tag_name : String) -> Bool {
  self.in_scope(tag_name, button_scope_elements())
}

///|
/// List item scope elements
fn list_item_scope_elements() -> Array[String] {
  let mut elems = default_scope_elements()
  elems.push("ol")
  elems.push("ul")
  elems
}

///|
/// Check if tag is in list item scope
fn TreeBuilder::in_list_item_scope(
  self : TreeBuilder,
  tag_name : String,
) -> Bool {
  self.in_scope(tag_name, list_item_scope_elements())
}

///|
/// Check if tag is in table scope
/// Table scope ONLY checks for html, table, template - NOT SVG/MathML elements
fn TreeBuilder::in_table_scope(self : TreeBuilder, tag_name : String) -> Bool {
  for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
    let entry = self.open_elements[i]
    if entry.tag_name == tag_name && entry.ns == HTML {
      return true
    }
    // Only html, table, template are table scope markers (per WHATWG 13.2.4.2)
    if entry.ns == HTML {
      if entry.tag_name == "html" ||
        entry.tag_name == "table" ||
        entry.tag_name == "template" {
        return false
      }
    }
  }
  false
}

///|
/// Select scope - everything except optgroup and option
fn TreeBuilder::in_select_scope(self : TreeBuilder, tag_name : String) -> Bool {
  for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
    let entry = self.open_elements[i]
    if entry.tag_name == tag_name && entry.ns == HTML {
      return true
    }
    if entry.tag_name != "optgroup" && entry.tag_name != "option" {
      return false
    }
  }
  false
}

///|
/// Check if the stack has an element with the given tag name
fn TreeBuilder::has_element_in_stack(
  self : TreeBuilder,
  tag_name : String,
) -> Bool {
  for entry in self.open_elements {
    if entry.tag_name == tag_name && entry.ns == HTML {
      return true
    }
  }
  false
}

///|
/// Remove an element from the stack by node id
fn TreeBuilder::remove_from_stack(self : TreeBuilder, node_id : Int) -> Unit {
  for i, entry in self.open_elements {
    if entry.node_id == node_id {
      let _ = self.open_elements.remove(i)
      break
    }
  }
}

// ============================================================================
// Element creation and insertion (WHATWG 13.2.6.1)
// ============================================================================

///|
/// Create an element for a token and insert it
fn TreeBuilder::insert_element_for_token(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
  ns : Namespace,
) -> Int {
  let attributes : Array[(String, String)] = attrs.map(fn(a) {
    (a.name, a.value)
  })
  let element = Element::new(name, ns, attributes)
  let node_id = self.document.add_node(ElementNode(element))
  // For template elements, create a DocumentFragment for content
  if ns == HTML && name == "template" {
    let fragment_id = self.document.add_node(DocumentFragmentNode(children=[]))
    // Set the template's content pointer
    match self.document.nodes[node_id] {
      ElementNode(elem) => elem.template_content = fragment_id
      _ => ()
    }
  }
  // Insert into the appropriate location
  self.insert_node(node_id)
  // Push onto stack of open elements
  self.push_element(node_id, name, ns)
  // Update document pointers
  if ns == HTML {
    match name {
      "html" => self.document.document_element = node_id
      "head" => {
        self.document.head_element = node_id
        self.head_element = node_id
      }
      "body" => self.document.body_element = node_id
      _ => ()
    }
  }
  node_id
}

///|
/// Create an element without inserting it (for adoption agency)
fn TreeBuilder::create_element_for_token(
  self : TreeBuilder,
  name : String,
  attrs : Array[(String, String)],
  ns : Namespace,
) -> Int {
  let element = Element::new(name, ns, attrs)
  self.document.add_node(ElementNode(element))
}

///|
/// Insert an HTML element
fn TreeBuilder::insert_html_element(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
) -> Int {
  self.insert_element_for_token(name, attrs, HTML)
}

///|
/// Insert a foreign element
fn TreeBuilder::insert_foreign_element(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
  ns : Namespace,
) -> Int {
  // Adjust tag name for SVG elements
  let adjusted_name = match ns {
    SVG => adjust_svg_tag_name(name)
    _ => name
  }
  // Adjust attributes based on namespace
  let adjusted_attrs = attrs.map(fn(a) {
    let adjusted_name = adjust_foreign_attribute_name(a.name, ns)
    { name: adjusted_name, value: a.value, }
  })
  self.insert_element_for_token(adjusted_name, adjusted_attrs, ns)
}

///|
/// Insert a node at the appropriate insertion location
fn TreeBuilder::insert_node(self : TreeBuilder, node_id : Int) -> Unit {
  if self.foster_parenting && self.is_foster_parenting_required() {
    self.insert_node_foster_parenting(node_id)
  } else {
    let parent_id = self.appropriate_insertion_point()
    self.document.append_child(parent_id, node_id)
  }
}

///|
/// Get the appropriate insertion point
fn TreeBuilder::appropriate_insertion_point(self : TreeBuilder) -> Int {
  if self.open_elements.is_empty() {
    // Insert into document
    0
  } else {
    // Insert into current node, or its template content if it's a template
    let current = self.current_node()
    if current.tag_name == "template" && current.ns == HTML {
      // Get the template's content fragment
      match self.document.get_node(current.node_id) {
        Some(ElementNode(elem)) if elem.template_content != NO_NODE =>
          elem.template_content
        _ => current.node_id
      }
    } else {
      current.node_id
    }
  }
}

///|
/// Check if foster parenting is required
/// Foster parenting is needed when inserting into table/tbody/tfoot/thead/tr
fn TreeBuilder::is_foster_parenting_required(self : TreeBuilder) -> Bool {
  if self.open_elements.is_empty() {
    return false
  }
  let current = self.current_node()
  // Check if current node is a table-related element that requires foster parenting
  current.tag_name == "table" ||
  current.tag_name == "tbody" ||
  current.tag_name == "tfoot" ||
  current.tag_name == "thead" ||
  current.tag_name == "tr"
}

///|
/// Insert a node using foster parenting (WHATWG 13.2.6.1)
fn TreeBuilder::insert_node_foster_parenting(
  self : TreeBuilder,
  node_id : Int,
) -> Unit {
  let (parent_id, insert_before) = self.get_foster_parent_location()
  if insert_before != NO_NODE {
    self.document.insert_before(parent_id, node_id, insert_before)
  } else {
    self.document.append_child(parent_id, node_id)
  }
}

///|
/// Get the foster parenting insertion location (WHATWG 13.2.6.1)
/// Returns (parent_id, insert_before_id) where insert_before_id is NO_NODE for append
fn TreeBuilder::get_foster_parent_location(self : TreeBuilder) -> (Int, Int) {
  // Find last template and last table in the stack
  let mut last_template_idx = -1
  let mut last_table_idx = -1
  for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
    if self.open_elements[i].tag_name == "template" && last_template_idx == -1 {
      last_template_idx = i
    }
    if self.open_elements[i].tag_name == "table" && last_table_idx == -1 {
      last_table_idx = i
    }
  }
  // Step 3: If template exists and (no table OR template is lower than table)
  if last_template_idx != -1 &&
    (last_table_idx == -1 || last_template_idx < last_table_idx) {
    let template_id = self.open_elements[last_template_idx].node_id
    let content_id = self.document.get_template_content(template_id)
    if content_id != NO_NODE {
      // If table is inside this template, insert before the table in its parent
      if last_table_idx != -1 {
        let table_node_id = self.open_elements[last_table_idx].node_id
        let table_parent = self.document.get_parent(table_node_id)
        if table_parent != NO_NODE {
          return (table_parent, table_node_id)
        }
      }
      return (content_id, NO_NODE)
    }
  }
  // Step 4: No table found, insert into first element (html)
  if last_table_idx == -1 {
    if self.open_elements.length() > 0 {
      return (self.open_elements[0].node_id, NO_NODE)
    }
    return (0, NO_NODE)
  }
  // Step 5: If table has a parent, insert before the table
  let table_node_id = self.open_elements[last_table_idx].node_id
  let parent = self.document.get_parent(table_node_id)
  if parent != NO_NODE {
    return (parent, table_node_id)
  }
  // Step 6: Insert into element above table in stack
  if last_table_idx > 0 {
    let foster_parent = self.open_elements[last_table_idx - 1].node_id
    return (foster_parent, NO_NODE)
  }
  (0, NO_NODE)
}

///|
/// Insert a character node
fn TreeBuilder::insert_character(self : TreeBuilder, c : Char) -> Unit {
  // Determine actual insertion location (considering foster parenting)
  let (parent_id, insert_before) = if self.foster_parenting &&
    self.is_foster_parenting_required() {
    self.get_foster_parent_location()
  } else {
    (self.appropriate_insertion_point(), NO_NODE)
  }
  // Try to append to existing text node
  let children = self.document.get_children(parent_id)
  if children.length() > 0 {
    // When inserting before a node, check the previous sibling, not last child
    let check_idx = if insert_before != NO_NODE {
      // Find the index of insert_before and check the node before it
      let mut idx = -1
      for i, child in children {
        if child == insert_before {
          idx = i
          break
        }
      }
      idx - 1
    } else {
      children.length() - 1
    }
    if check_idx >= 0 {
      let prev_child = children[check_idx]
      match self.document.get_node(prev_child) {
        Some(TextNode(text)) => {
          // Replace with new text node containing old text + new char
          let new_text = text + c.to_string()
          self.document.nodes[prev_child] = TextNode(new_text)
          return
        }
        _ => ()
      }
    }
  }
  // Create new text node
  let node_id = self.document.add_node(TextNode(c.to_string()))
  if insert_before != NO_NODE {
    self.document.insert_before(parent_id, node_id, insert_before)
  } else {
    self.document.append_child(parent_id, node_id)
  }
}

///|
/// Insert a comment node
fn TreeBuilder::insert_comment(self : TreeBuilder, text : String) -> Unit {
  let node_id = self.document.add_node(CommentNode(text))
  self.insert_node(node_id)
}

///|
/// Insert a comment at document level
fn TreeBuilder::insert_comment_at_document(
  self : TreeBuilder,
  text : String,
) -> Unit {
  let node_id = self.document.add_node(CommentNode(text))
  self.document.append_child(0, node_id)
}

///|
/// Insert a processing instruction at the mode-appropriate location.
fn TreeBuilder::insert_processing_instruction(
  self : TreeBuilder,
  target : String,
  data : String,
) -> Unit {
  let node_id = self.document.add_node(
    ProcessingInstructionNode(target~, data~),
  )
  match self.mode {
    AfterBody | AfterFrameset if !self.open_elements.is_empty() =>
      self.document.append_child(self.open_elements[0].node_id, node_id)
    AfterAfterBody | AfterAfterFrameset =>
      self.document.append_child(0, node_id)
    _ => self.insert_node(node_id)
  }
}

///|
/// Insert a DOCTYPE node
fn TreeBuilder::insert_doctype(
  self : TreeBuilder,
  name : String?,
  public_id : String?,
  system_id : String?,
) -> Unit {
  let doctype_name = name.unwrap_or("")
  let pub_id = public_id.unwrap_or("")
  let sys_id = system_id.unwrap_or("")
  let node_id = self.document.add_node(
    DocumentTypeNode(name=doctype_name, public_id=pub_id, system_id=sys_id),
  )
  self.document.append_child(0, node_id)
}

// ============================================================================
// Error handling
// ============================================================================

///|
/// Emit a parse error
fn TreeBuilder::emit_error(self : TreeBuilder, code : ParseErrorCode) -> Unit {
  // Insertion modes historically used a tokenizer-only error as their generic
  // parse-error marker. Keep the call sites compact while exposing an accurate
  // tree-construction diagnostic to callers.
  let code = match code {
    UnexpectedCharacterInUnquotedAttributeValue => TreeConstruction
    _ => code
  }
  self.errors.push({ code, position: self.tokenizer.get_position(), })
}

// ============================================================================
// Generic RCDATA/RAWTEXT algorithm (WHATWG 13.2.6.2)
// ============================================================================

///|
/// Switch tokenizer to RCDATA and set up text mode parsing
fn TreeBuilder::parse_rcdata(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
) -> Unit {
  let _ = self.insert_html_element(name, attrs)
  self.tokenizer.state = RCDATA
  self.original_mode = self.mode
  self.mode = Text
}

///|
/// Switch tokenizer to RAWTEXT and set up text mode parsing
fn TreeBuilder::parse_rawtext(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
) -> Unit {
  let _ = self.insert_html_element(name, attrs)
  self.tokenizer.state = RAWTEXT
  self.original_mode = self.mode
  self.mode = Text
}

///|
/// Switch tokenizer to script data state
fn TreeBuilder::parse_script(
  self : TreeBuilder,
  name : String,
  attrs : Array[Attribute],
) -> Unit {
  let _ = self.insert_html_element(name, attrs)
  self.tokenizer.state = ScriptData
  self.original_mode = self.mode
  self.mode = Text
}

// ============================================================================
// Implied end tags (WHATWG 13.2.6.2)
// ============================================================================

///|
/// Elements with implied end tags
fn implied_end_tag_elements() -> Array[String] {
  ["dd", "dt", "li", "optgroup", "option", "p", "rb", "rp", "rt", "rtc"]
}

///|
/// Generate implied end tags (except for given tag)
fn TreeBuilder::generate_implied_end_tags(
  self : TreeBuilder,
  except : String,
) -> Unit {
  let implied = implied_end_tag_elements()
  while self.open_elements.length() > 0 {
    let current = self.current_node()
    if current.tag_name == except {
      break
    }
    if !implied.contains(current.tag_name) || current.ns != HTML {
      break
    }
    let _ = self.pop_element()
  }
}

///|
/// Elements with implied end tags (thoroughly)
fn thorough_implied_end_tag_elements() -> Array[String] {
  [
    "caption", "colgroup", "dd", "dt", "li", "optgroup", "option", "p", "rb", "rp",
    "rt", "rtc", "tbody", "td", "tfoot", "th", "thead", "tr",
  ]
}

///|
/// Generate implied end tags thoroughly
fn TreeBuilder::generate_implied_end_tags_thoroughly(
  self : TreeBuilder,
) -> Unit {
  let implied = thorough_implied_end_tag_elements()
  while self.open_elements.length() > 0 {
    let current = self.current_node()
    if !implied.contains(current.tag_name) || current.ns != HTML {
      break
    }
    let _ = self.pop_element()
  }
}

// ============================================================================
// Reset insertion mode appropriately (WHATWG 13.2.4.1)
// ============================================================================

///|
/// Reset the insertion mode appropriately
fn TreeBuilder::reset_insertion_mode(self : TreeBuilder) -> Unit {
  for i = self.open_elements.length() - 1; i >= 0; i = i - 1 {
    let entry = self.open_elements[i]
    let is_last = i == 0
    // For fragment parsing, first node might be replaced
    match entry.tag_name {
      "select" => {
        if !is_last {
          // Walk up to find context
          for j = i - 1; j >= 0; j = j - 1 {
            let ancestor = self.open_elements[j]
            if ancestor.tag_name == "template" {
              break
            }
            if ancestor.tag_name == "table" {
              self.mode = InSelectInTable
              return
            }
          }
        }
        self.mode = InSelect
        return
      }
      "td" | "th" =>
        if !is_last {
          self.mode = InCell
          return
        }
      "tr" => {
        self.mode = InRow
        return
      }
      "tbody" | "thead" | "tfoot" => {
        self.mode = InTableBody
        return
      }
      "caption" => {
        self.mode = InCaption
        return
      }
      "colgroup" => {
        self.mode = InColumnGroup
        return
      }
      "table" => {
        self.mode = InTable
        return
      }
      "template" => {
        if self.template_modes.length() > 0 {
          self.mode = self.template_modes[self.template_modes.length() - 1]
        } else {
          self.mode = InTemplate
        }
        return
      }
      "head" =>
        if !is_last {
          self.mode = InHead
          return
        }
      "body" => {
        self.mode = InBody
        return
      }
      "frameset" => {
        self.mode = InFrameset
        return
      }
      "html" => {
        if self.head_element == NO_NODE {
          self.mode = BeforeHead
        } else {
          self.mode = AfterHead
        }
        return
      }
      _ => ()
    }
    if is_last {
      self.mode = InBody
      return
    }
  }
}

// ============================================================================
// Foreign attribute adjustment (WHATWG 13.2.6.5)
// ============================================================================

///|
/// Adjust foreign attribute names based on namespace
/// WHATWG 13.2.6.4 - only specific attributes should be adjusted
fn adjust_foreign_attribute_name(name : String, ns : Namespace) -> String {
  // Check for specific xlink: attributes (WHATWG spec list)
  match name {
    "xlink:actuate" => return "xlink actuate"
    "xlink:arcrole" => return "xlink arcrole"
    "xlink:href" => return "xlink href"
    "xlink:role" => return "xlink role"
    "xlink:show" => return "xlink show"
    "xlink:title" => return "xlink title"
    "xlink:type" => return "xlink type"
    "xml:lang" => return "xml lang"
    "xml:space" => return "xml space"
    "xmlns" => return "xmlns"
    "xmlns:xlink" => return "xmlns xlink"
    _ => ()
  }
  // Then apply namespace-specific case adjustments
  match ns {
    SVG => adjust_svg_attribute_name(name)
    MathML => adjust_mathml_attribute_name(name)
    HTML => name
  }
}

///|
/// Adjust SVG attribute names to proper case
fn adjust_svg_attribute_name(name : String) -> String {
  match name {
    "attributename" => "attributeName"
    "attributetype" => "attributeType"
    "basefrequency" => "baseFrequency"
    "baseprofile" => "baseProfile"
    "calcmode" => "calcMode"
    "clippathunits" => "clipPathUnits"
    "diffuseconstant" => "diffuseConstant"
    "edgemode" => "edgeMode"
    "filterunits" => "filterUnits"
    "glyphref" => "glyphRef"
    "gradienttransform" => "gradientTransform"
    "gradientunits" => "gradientUnits"
    "kernelmatrix" => "kernelMatrix"
    "kernelunitlength" => "kernelUnitLength"
    "keypoints" => "keyPoints"
    "keysplines" => "keySplines"
    "keytimes" => "keyTimes"
    "lengthadjust" => "lengthAdjust"
    "limitingconeangle" => "limitingConeAngle"
    "markerheight" => "markerHeight"
    "markerunits" => "markerUnits"
    "markerwidth" => "markerWidth"
    "maskcontentunits" => "maskContentUnits"
    "maskunits" => "maskUnits"
    "numoctaves" => "numOctaves"
    "pathlength" => "pathLength"
    "patterncontentunits" => "patternContentUnits"
    "patterntransform" => "patternTransform"
    "patternunits" => "patternUnits"
    "pointsatx" => "pointsAtX"
    "pointsaty" => "pointsAtY"
    "pointsatz" => "pointsAtZ"
    "preservealpha" => "preserveAlpha"
    "preserveaspectratio" => "preserveAspectRatio"
    "primitiveunits" => "primitiveUnits"
    "refx" => "refX"
    "refy" => "refY"
    "repeatcount" => "repeatCount"
    "repeatdur" => "repeatDur"
    "requiredextensions" => "requiredExtensions"
    "requiredfeatures" => "requiredFeatures"
    "specularconstant" => "specularConstant"
    "specularexponent" => "specularExponent"
    "spreadmethod" => "spreadMethod"
    "startoffset" => "startOffset"
    "stddeviation" => "stdDeviation"
    "stitchtiles" => "stitchTiles"
    "surfacescale" => "surfaceScale"
    "systemlanguage" => "systemLanguage"
    "tablevalues" => "tableValues"
    "targetx" => "targetX"
    "targety" => "targetY"
    "textlength" => "textLength"
    "viewbox" => "viewBox"
    "viewtarget" => "viewTarget"
    "xchannelselector" => "xChannelSelector"
    "ychannelselector" => "yChannelSelector"
    "zoomandpan" => "zoomAndPan"
    _ => name
  }
}

///|
/// Adjust MathML attribute names to proper case
fn adjust_mathml_attribute_name(name : String) -> String {
  match name {
    "definitionurl" => "definitionURL"
    _ => name
  }
}

///|
/// Adjust SVG tag names to proper case
fn adjust_svg_tag_name(name : String) -> String {
  match name {
    "altglyph" => "altGlyph"
    "altglyphdef" => "altGlyphDef"
    "altglyphitem" => "altGlyphItem"
    "animatecolor" => "animateColor"
    "animatemotion" => "animateMotion"
    "animatetransform" => "animateTransform"
    "clippath" => "clipPath"
    "feblend" => "feBlend"
    "fecolormatrix" => "feColorMatrix"
    "fecomponenttransfer" => "feComponentTransfer"
    "fecomposite" => "feComposite"
    "feconvolvematrix" => "feConvolveMatrix"
    "fediffuselighting" => "feDiffuseLighting"
    "fedisplacementmap" => "feDisplacementMap"
    "fedistantlight" => "feDistantLight"
    "fedropshadow" => "feDropShadow"
    "feflood" => "feFlood"
    "fefunca" => "feFuncA"
    "fefuncb" => "feFuncB"
    "fefuncg" => "feFuncG"
    "fefuncr" => "feFuncR"
    "fegaussianblur" => "feGaussianBlur"
    "feimage" => "feImage"
    "femerge" => "feMerge"
    "femergenode" => "feMergeNode"
    "femorphology" => "feMorphology"
    "feoffset" => "feOffset"
    "fepointlight" => "fePointLight"
    "fespecularlighting" => "feSpecularLighting"
    "fespotlight" => "feSpotLight"
    "fetile" => "feTile"
    "feturbulence" => "feTurbulence"
    "foreignobject" => "foreignObject"
    "glyphref" => "glyphRef"
    "lineargradient" => "linearGradient"
    "radialgradient" => "radialGradient"
    "textpath" => "textPath"
    _ => name
  }
}

// ============================================================================
// Parse function - main entry point
// ============================================================================

///|
/// Parse an HTML string and return the document
pub fn parse(html : String) -> Document {
  let builder = TreeBuilder::new(html)
  builder.parse()
}

///|
/// Parse an HTML string with scripting enabled
pub fn parse_with_scripting(html : String) -> Document {
  let builder = TreeBuilder::new_with_options(html, scripting=true)
  builder.parse()
}

///|
/// Parse an HTML string and return the document with errors
pub fn parse_with_errors(html : String) -> (Document, Array[ParseError]) {
  let builder = TreeBuilder::new(html)
  let doc = builder.parse()
  (doc, builder.errors)
}
</code></pre>
  <script>
    let moonbitLanguageFn = hljs => {
      return {
        case_insensitive: true,
        keywords: {
          keyword: 'func fn enum struct type if else match return continue break while let var interface pub priv readonly',
          literal: 'true false',
          type: "Int Int64 Double String Bool Char Bytes Option Array Result",
          built_in: 'lsl lsr asr shl shr land lor lxor Show Debug Hash Eq Compare Some None'
        },
        contains: [
          {
            scope: "char",
            begin: "'", end: "'"
          },
          {
            scope: "string",
            begin: "\"", end: "\""
          },
          {
            scope: "number",
            begin: "\\b\\d+(\\.\\d+)?\\b"
          },
          {
            scope: "codelink",
            match: /\<a href\="(?<link>[^<>]+?)"\>(?<code>[^\/<>]+?)\<\/a\>/g
          },
          hljs.COMMENT(
            '//', // begin
            '\n', // end
          )
        ]
      }
    }

    hljs.registerLanguage('moonbit', moonbitLanguageFn);
    hljs.highlightAll();
    hljs.initLineNumbersOnLoad();

    const number = window.location.href.split('#')[1];

    function waitForLineNumbers() {
      setTimeout(function () {
        const target = document.querySelector(`.hljs-ln-line[data-line-number="${number}"]`);
        if (target == null) waitForLineNumbers();
        else target.scrollIntoView();
      }, 50);
    }

    waitForLineNumbers()

  </script>
  <style>
    .hljs-ln-numbers {
      -webkit-touch-callout: none;
      -webkit-user-select: none;
      -khtml-user-select: none;
      -moz-user-select: none;
      -ms-user-select: none;
      user-select: none;
    }

    .hljs-ln-n {
      color: #ccc;
      border-right: 1px solid #dfdddd;
      margin-right: 1em;
      text-align: center;
      vertical-align: top;
      padding-right: 0.5em;
    }

    .hljs {
      background: none;
    }

    body {
      background-color: #fafafa;
    }
  </style>
</body>

</html>