pub(crate) mod dispatch;
mod foreign;
mod helpers;
mod insertion_mode;
pub use insertion_mode::InsertionMode;
use std::cell::RefCell;
use std::rc::Rc;
use muskitty_dom::Node;
use crate::error::ParseError;
use muskitty_html5_tokenizer::{Token, Tokenizer};
pub const MAX_REPROCESS_COUNT: u32 = 50;
pub const MAX_ACTIVE_FORMATTING_ELEMENTS: usize = 256;
#[derive(Clone)]
pub enum ActiveFormattingEntry {
Marker,
Element(Rc<RefCell<Node>>),
}
pub struct HtmlTreeConstructor {
pub document: Rc<RefCell<Node>>,
pub open_elements: Vec<Rc<RefCell<Node>>>,
pub active_formatting_elements: Vec<ActiveFormattingEntry>,
pub insertion_mode: InsertionMode,
pub original_insertion_mode: Option<InsertionMode>,
pub head_element: Option<Rc<RefCell<Node>>>,
pub form_element: Option<Rc<RefCell<Node>>>,
pub foster_parenting: bool,
pub pending_table_text: String,
pub template_insertion_modes: Vec<InsertionMode>,
pub frameset_ok: bool,
pub scripting_flag: bool,
pub errors: Vec<ParseError>,
pub skip_next_lf: bool,
pub quirks_mode: bool,
pub max_open_elements: usize,
pub fragment_context: Option<Rc<RefCell<Node>>>,
pub skip_foreign_dispatch_once: bool,
pub fragment_root: Option<Rc<RefCell<Node>>>,
pub select_selectedness_memo: Option<SelectSelectednessMemo>,
pub select_selectedcontent_memo: Option<SelectSelectedcontentMemo>,
}
pub struct SelectSelectednessMemo {
pub select: std::rc::Weak<RefCell<Node>>,
pub has_selected: bool,
pub all_disabled: bool,
pub last_selected: std::rc::Weak<RefCell<Node>>,
}
pub struct SelectSelectedcontentMemo {
pub select: std::rc::Weak<RefCell<Node>>,
pub lookup: SelectedcontentLookup,
}
pub enum SelectedcontentLookup {
Absent,
Present(std::rc::Weak<RefCell<Node>>),
}
impl HtmlTreeConstructor {
pub fn new(document: Rc<RefCell<Node>>) -> Self {
Self {
document,
open_elements: Vec::new(),
active_formatting_elements: Vec::new(),
insertion_mode: InsertionMode::Initial,
original_insertion_mode: None,
head_element: None,
form_element: None,
foster_parenting: false,
pending_table_text: String::new(),
template_insertion_modes: Vec::new(),
frameset_ok: true,
scripting_flag: false,
errors: Vec::new(),
skip_next_lf: false,
quirks_mode: false,
max_open_elements: crate::MAX_OPEN_ELEMENTS,
fragment_context: None,
skip_foreign_dispatch_once: false,
fragment_root: None,
select_selectedness_memo: None,
select_selectedcontent_memo: None,
}
}
pub fn current_node(&self) -> Rc<RefCell<Node>> {
self.open_elements
.last()
.cloned()
.unwrap_or_else(|| self.document.clone())
}
pub fn current_node_in_foreign_content(&self) -> bool {
if self.fragment_context.is_some() && self.open_elements.len() == 1 {
if let Some(ctx) = &self.fragment_context {
let n = ctx.borrow();
return matches!(&n.kind, muskitty_dom::NodeKind::Element(e)
if e.namespace != muskitty_dom::Namespace::Html);
}
}
match self.open_elements.last() {
Some(node) => {
let n = node.borrow();
matches!(&n.kind, muskitty_dom::NodeKind::Element(e)
if e.namespace != muskitty_dom::Namespace::Html)
}
None => false,
}
}
pub fn run(&mut self, token: &Token, tokenizer: &mut dyn Tokenizer) {
if self.skip_next_lf {
self.skip_next_lf = false;
if let Token::Character('\n') = token {
return;
}
}
let mut reprocess_count = 0u32;
loop {
match dispatch::dispatch(self, token, tokenizer) {
dispatch::Step::Done => return,
dispatch::Step::Reprocess => {
reprocess_count += 1;
if reprocess_count > MAX_REPROCESS_COUNT {
self.errors.push(ParseError::ReprocessLimitExceeded {
limit: MAX_REPROCESS_COUNT,
});
return;
}
continue;
}
}
}
}
pub fn finalize(&mut self) {
while !self.open_elements.is_empty() {
helpers::pop_open_element(self);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::ParseError;
use muskitty_dom::Node;
use muskitty_html5_tokenizer::HtmlTokenizer;
#[test]
fn reprocess_limit_records_error_instead_of_panicking() {
let document = Node::new_document();
let mut constructor = HtmlTreeConstructor::new(document);
constructor.insertion_mode = InsertionMode::Text;
let mut tokenizer = HtmlTokenizer::new("");
constructor.run(&Token::EOF, &mut tokenizer);
assert!(
constructor
.errors
.iter()
.any(|e| matches!(e, ParseError::ReprocessLimitExceeded { .. })),
"expected ReprocessLimitExceeded error, got {:?}",
constructor.errors
);
}
#[test]
fn afe_list_capped_under_distinct_formatting_elements() {
let mut input = String::new();
for i in 0..600 {
input.push_str(&format!("<b a={i}>"));
}
let document = Node::new_document();
let mut constructor = HtmlTreeConstructor::new(document);
let mut tokenizer = HtmlTokenizer::new(&input);
while let Some(tok) = tokenizer.next_token() {
if matches!(tok, muskitty_html5_tokenizer::Token::EOF) {
break;
}
constructor.run(&tok, &mut tokenizer);
}
assert_eq!(
constructor.active_formatting_elements.len(),
crate::parser::MAX_ACTIVE_FORMATTING_ELEMENTS,
"AFE list must be capped at MAX_ACTIVE_FORMATTING_ELEMENTS"
);
}
#[test]
fn large_distinct_formatting_input_parses_completely() {
let mut input = String::new();
for i in 0..3_000 {
input.push_str(&format!("<b a={i}>"));
}
let doc = crate::parse(&input);
assert!(
doc.borrow().first_element_child().is_some(),
"document must still build normally"
);
}
fn collect_options(
node: &std::rc::Rc<std::cell::RefCell<Node>>,
out: &mut Vec<std::rc::Rc<std::cell::RefCell<Node>>>,
) {
let children: Vec<_> = node.borrow().child_nodes().to_vec();
for c in children {
let is_option = c
.borrow()
.kind
.as_element()
.map(|e| e.local_name == "option")
.unwrap_or(false);
if is_option {
out.push(c.clone());
}
collect_options(&c, out);
}
}
fn option_selected_states(html: &str) -> Vec<bool> {
let doc = crate::parse(html);
let mut opts = Vec::new();
collect_options(&doc, &mut opts);
opts.iter()
.map(|o| {
o.borrow()
.kind
.as_element()
.map(|e| e.selectedness)
.unwrap_or(false)
})
.collect()
}
#[test]
fn option_first_plain_becomes_selected() {
assert_eq!(
option_selected_states("<select><option>a<option>b</select>"),
vec![true, false]
);
}
#[test]
fn option_disabled_first_selects_second() {
assert_eq!(
option_selected_states("<select><option disabled>a<option>b</select>"),
vec![false, true]
);
}
#[test]
fn option_all_disabled_none_selected() {
assert_eq!(
option_selected_states("<select><option disabled>a<option disabled>b</select>"),
vec![false, false]
);
}
#[test]
fn option_selected_attr_and_last_selected_kept() {
assert_eq!(
option_selected_states("<select><option selected>a<option>b</select>"),
vec![true, false]
);
assert_eq!(
option_selected_states("<select><option selected>a<option selected>b</select>"),
vec![false, true]
);
}
#[test]
fn option_selected_after_step1_auto_select_deselects_previous() {
assert_eq!(
option_selected_states("<select><option>a<option selected>b</select>"),
vec![false, true]
);
}
#[test]
fn option_size_not_1_selected_pair_keeps_last() {
assert_eq!(
option_selected_states("<select size=2><option selected>a<option selected>b</select>"),
vec![false, true]
);
assert_eq!(
option_selected_states("<select size=2><option selected>a<option>b</select>"),
vec![true, false]
);
}
#[test]
fn option_two_selects_independent_memos() {
assert_eq!(
option_selected_states("<select><option selected>a</select><select><option>b</select>"),
vec![true, true]
);
}
#[test]
fn option_multiple_select_no_adjustment() {
assert_eq!(
option_selected_states("<select multiple><option selected>a<option>b</select>"),
vec![true, false]
);
}
#[test]
fn many_plain_options_parse_fast_via_memo() {
let mut input = String::with_capacity(65_000 * 16);
input.push_str("<select>");
for _ in 0..65_000 {
input.push_str("<option>x</option>");
}
input.push_str("</select>");
let doc = crate::parse(&input);
let mut opts = Vec::new();
collect_options(&doc, &mut opts);
assert_eq!(opts.len(), 65_000, "all options must be in the tree");
assert!(
opts[0]
.borrow()
.kind
.as_element()
.map(|e| e.selectedness)
.unwrap_or(false),
"first option must be selected (step 1)"
);
}
#[test]
fn many_selected_options_parse_fast_via_memo() {
let mut input = String::with_capacity(65_000 * 26);
input.push_str("<select>");
for _ in 0..65_000 {
input.push_str("<option selected>x</option>");
}
input.push_str("</select>");
let doc = crate::parse(&input);
let mut opts = Vec::new();
collect_options(&doc, &mut opts);
assert_eq!(opts.len(), 65_000, "all options must be in the tree");
let selected: Vec<bool> = opts
.iter()
.map(|o| {
o.borrow()
.kind
.as_element()
.map(|e| e.selectedness)
.unwrap_or(false)
})
.collect();
assert!(selected[65_000 - 1], "last option must stay selected");
assert!(
!selected[..65_000 - 1].iter().any(|&s| s),
"all earlier options must be deselected"
);
}
#[test]
fn normal_input_never_triggers_reprocess_limit() {
let document = Node::new_document();
let mut constructor = HtmlTreeConstructor::new(document);
let mut tokenizer = HtmlTokenizer::new("");
constructor.run(&Token::Character('a'), &mut tokenizer);
constructor.run(&Token::EOF, &mut tokenizer);
assert!(!constructor
.errors
.iter()
.any(|e| matches!(e, ParseError::ReprocessLimitExceeded { .. })));
}
}