#[derive(Debug, PartialEq)]
pub(super) enum Node {
Text(String),
Element { tag: String, children: Vec<Self> },
}
impl Drop for Node {
fn drop(&mut self) {
let mut stack: Vec<Self> = if let Self::Element { children, .. } = self {
std::mem::take(children)
} else {
return;
};
while let Some(mut node) = stack.pop() {
if let Self::Element { children, .. } = &mut node {
stack.append(children);
}
}
}
}
fn is_void_element(tag: &str) -> bool {
matches!(
tag,
"br" | "hr"
| "img"
| "input"
| "meta"
| "link"
| "area"
| "base"
| "col"
| "embed"
| "source"
| "track"
| "wbr"
)
}
fn implicitly_closes(open_tag: &str, new_tag: &str) -> bool {
(open_tag == "p" && closes_open_paragraph(new_tag))
|| (open_tag == "head" && !is_valid_in_head(new_tag))
|| matches!(
(open_tag, new_tag),
("li", "li")
| ("dt" | "dd", "dt" | "dd")
| ("tr", "tr" | "thead" | "tbody" | "tfoot")
| ("td" | "th", "td" | "th" | "tr" | "thead" | "tbody" | "tfoot")
| ("thead" | "tbody" | "tfoot", "thead" | "tbody" | "tfoot")
)
}
fn is_valid_in_head(tag: &str) -> bool {
matches!(
tag,
"head" | "title" | "base" | "link" | "meta" | "style" | "script" | "noscript" | "template"
)
}
fn closes_open_paragraph(new_tag: &str) -> bool {
matches!(
new_tag,
"p" | "div"
| "blockquote"
| "dl"
| "dt"
| "dd"
| "hr"
| "table"
| "ul"
| "ol"
| "li"
| "section"
| "article"
| "main"
| "header"
| "footer"
| "nav"
| "aside"
| "h1"
| "h2"
| "h3"
| "h4"
| "h5"
| "h6"
)
}
fn is_raw_text_element(tag: &str) -> bool {
matches!(tag, "script" | "style" | "title" | "textarea")
}
fn oversized_raw_text_tag_name(s: &str) -> Option<&'static str> {
debug_assert!(s.starts_with('<'));
let rest = &s[1..];
for name in [
"script", "style", "title", "head", "noscript", "template", "textarea",
] {
if rest.len() < name.len()
|| !rest.as_bytes()[..name.len()].eq_ignore_ascii_case(name.as_bytes())
{
continue;
}
let is_boundary = rest[name.len()..]
.chars()
.next()
.is_none_or(|c| c == '>' || c == '/' || c.is_whitespace());
if is_boundary {
return Some(name);
}
}
None
}
fn oversized_tag_body_start(input: &str, after_name: usize, len: usize) -> usize {
find_tag_end(&input[after_name..]).map_or(len, |i| after_name + i + 1)
}
fn push_oversized_nested_tag(
stack: &mut Vec<(String, Vec<Node>, usize)>,
name: &str,
body_start: usize,
) -> usize {
let structural_idx = nearest_structural_idx(stack, name);
stack.push((name.to_owned(), Vec::new(), structural_idx));
body_start
}
fn push_oversized_raw_text_content_tag(
stack: &mut [(String, Vec<Node>, usize)],
input: &str,
body_start: usize,
name: &str,
) -> usize {
let (text, new_pos) = consume_raw_text(input, body_start, name);
let mut children = Vec::new();
if !text.is_empty() {
children.push(Node::Text(decode_entities(text)));
}
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element {
tag: name.to_owned(),
children,
});
new_pos
}
const MAX_TAG_NAME_SCAN: usize = 128;
fn push_oversized_generic_tag(
stack: &mut Vec<(String, Vec<Node>, usize)>,
input: &str,
pos: usize,
len: usize,
) -> Option<usize> {
let rest = &input[pos + 1..];
let first = rest.chars().next()?;
if !first.is_ascii_alphabetic() {
return None;
}
let name_end = bounded_prefix(rest, MAX_TAG_NAME_SCAN)
.find(|c: char| c == '>' || c == '/' || c.is_whitespace())?;
let tag = rest[..name_end].to_ascii_lowercase();
let after_name = pos + 1 + name_end;
let gt = find_tag_end(&input[after_name..]);
let body_start = gt.map_or(len, |i| after_name + i + 1);
close_implied_tags(stack, &tag);
if is_void_element(&tag) {
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element {
tag,
children: Vec::new(),
});
} else {
let structural_idx = nearest_structural_idx(stack, &tag);
stack.push((tag, Vec::new(), structural_idx));
}
Some(body_start)
}
fn consume_raw_text<'a>(input: &'a str, pos: usize, tag: &str) -> (&'a str, usize) {
let rest = &input[pos..];
for (i, _) in rest.match_indices('<') {
let Some(after_slash) = rest[i + 1..].strip_prefix('/') else {
continue;
};
if after_slash.len() < tag.len()
|| !after_slash.as_bytes()[..tag.len()].eq_ignore_ascii_case(tag.as_bytes())
{
continue;
}
let after_tag = &after_slash[tag.len()..];
let is_boundary = after_tag
.chars()
.next()
.is_none_or(|c| c == '>' || c == '/' || c.is_whitespace());
if !is_boundary {
continue;
}
let Some(gt) = raw_close_tag_end(after_tag) else {
continue;
};
let consumed = i + 2 + tag.len() + gt + 1;
return (&rest[..i], pos + consumed);
}
(rest, input.len())
}
fn raw_close_tag_end(after_tag: &str) -> Option<usize> {
let bytes = after_tag.as_bytes();
let mut i = 0;
let mut in_unquoted_value = false;
loop {
let rel = bytes
.get(i..)?
.iter()
.position(|&b| b == b'>' || b == b'<' || b == b'=' || b.is_ascii_whitespace())?;
let idx = i + rel;
match bytes[idx] {
b'>' => return Some(idx),
b'<' if !in_unquoted_value => return None,
b'=' if !in_unquoted_value => {
let (next_i, quoted) = consume_attr_value(bytes, idx)?;
in_unquoted_value = !quoted;
i = next_i;
}
b if b.is_ascii_whitespace() => {
in_unquoted_value = false;
i = idx + 1;
}
_ => {
i = idx + 1;
}
}
}
}
const MAX_CLOSE_SCAN: usize = 512;
fn handle_closing_tag(
stack: &mut Vec<(String, Vec<Node>, usize)>,
input: &str,
pos: usize,
) -> usize {
let rest = &input[pos + 2..];
let name_end = rest
.find(|c: char| c == '>' || c == '/' || c.is_whitespace())
.unwrap_or(rest.len());
let name = rest[..name_end].to_ascii_lowercase();
let tag_end = find_tag_end(bounded_prefix(rest, MAX_TAG_SCAN)).or_else(|| find_tag_end(rest));
let new_pos = pos + 2 + tag_end.map_or(rest.len(), |i| i + 1);
let matching_depth = if name.is_empty() {
None
} else {
let window_start = stack.len().saturating_sub(MAX_CLOSE_SCAN);
stack[window_start..]
.iter()
.rposition(|(tag, _, _)| *tag == name)
.map(|i| window_start + i)
};
if let Some(depth) = matching_depth {
while stack.len() > depth {
let (tag, children, _) = stack.pop().expect("depth <= stack.len()");
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element { tag, children });
}
}
new_pos
}
fn comment_end(input: &str, pos: usize, len: usize) -> usize {
let rest = &input[pos..];
[
rest.find("-->").map(|i| i + 3),
rest.find("--!>").map(|i| i + 4),
]
.into_iter()
.flatten()
.min()
.map_or(len, |i| pos + i)
}
pub(super) fn parse(input: &str) -> Vec<Node> {
let bytes = input.as_bytes();
let len = bytes.len();
let mut pos = 0usize;
let mut stack: Vec<(String, Vec<Node>, usize)> = vec![(String::new(), Vec::new(), 0)];
while pos < len {
if bytes[pos] == b'<' {
if input[pos..].starts_with("<!--") {
pos = comment_end(input, pos, len);
continue;
}
if input[pos..].starts_with("<!") || input[pos..].starts_with("<?") {
let end = input[pos..].find('>').map_or(len, |i| pos + i + 1);
pos = end;
continue;
}
if input[pos..].starts_with("</") {
pos = handle_closing_tag(&mut stack, input, pos);
continue;
}
if let Some((tag, tag_end)) = parse_open_tag(&input[pos..]) {
pos += tag_end;
close_implied_tags(&mut stack, &tag);
if is_raw_text_element(&tag) {
let (text, new_pos) = consume_raw_text(input, pos, &tag);
pos = new_pos;
let mut children = Vec::new();
if !text.is_empty() {
children.push(Node::Text(decode_entities(text)));
}
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element { tag, children });
continue;
}
if is_void_element(&tag) {
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element {
tag,
children: Vec::new(),
});
} else {
let structural_idx = nearest_structural_idx(&stack, &tag);
stack.push((tag, Vec::new(), structural_idx));
}
continue;
}
if let Some(name) = oversized_raw_text_tag_name(&input[pos..]) {
let after_name = pos + 1 + name.len();
let body_start = oversized_tag_body_start(input, after_name, len);
pos = if name == "textarea" {
push_oversized_raw_text_content_tag(&mut stack, input, body_start, name)
} else if is_raw_text_element(name) {
consume_raw_text(input, body_start, name).1
} else {
push_oversized_nested_tag(&mut stack, name, body_start)
};
continue;
}
if let Some(new_pos) = push_oversized_generic_tag(&mut stack, input, pos, len) {
pos = new_pos;
continue;
}
push_text(&mut stack, "<");
pos += 1;
continue;
}
let next_lt = input[pos..].find('<').map_or(len, |i| pos + i);
let raw = &input[pos..next_lt];
if !raw.is_empty() {
push_text(&mut stack, &decode_entities(raw));
}
pos = next_lt;
}
while stack.len() > 1 {
let (tag, children, _) = stack.pop().expect("stack.len() > 1");
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element { tag, children });
}
stack.pop().expect("root frame always present").1
}
fn is_structural_tag(tag: &str) -> bool {
is_valid_in_head(tag)
|| matches!(
tag,
"thead"
| "tbody"
| "tfoot"
| "tr"
| "td"
| "th"
| "html"
| "body"
| "p"
| "li"
| "dt"
| "dd"
| "ul"
| "ol"
| "table"
)
}
fn nearest_structural_idx(stack: &[(String, Vec<Node>, usize)], tag: &str) -> usize {
if is_structural_tag(tag) {
stack.len()
} else {
stack.last().map_or(0, |frame| frame.2)
}
}
fn close_implied_tags(stack: &mut Vec<(String, Vec<Node>, usize)>, new_tag: &str) {
loop {
if stack.len() <= 1 {
break;
}
let target = stack[stack.len() - 1].2;
if !implicitly_closes(&stack[target].0, new_tag) {
break;
}
while stack.len() > target {
let (closed_tag, children, _) = stack.pop().expect("stack.len() > target >= 1");
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element {
tag: closed_tag,
children,
});
}
}
}
fn push_text(stack: &mut Vec<(String, Vec<Node>, usize)>, text: &str) {
if text.is_empty() {
return;
}
if stack.last().is_some_and(|(tag, _, _)| tag == "head")
&& text.contains(|c: char| !c.is_whitespace())
{
let (closed_tag, children, _) = stack.pop().expect("just checked stack.last() above");
stack
.last_mut()
.expect("root frame is never popped")
.1
.push(Node::Element {
tag: closed_tag,
children,
});
}
let top = stack.last_mut().expect("root frame is never popped");
if let Some(Node::Text(prev)) = top.1.last_mut() {
prev.push_str(text);
} else {
top.1.push(Node::Text(text.to_owned()));
}
}
const MAX_TAG_SCAN: usize = 4096;
fn bounded_prefix(s: &str, max_len: usize) -> &str {
let mut end = s.len().min(max_len);
while end > 0 && !s.is_char_boundary(end) {
end -= 1;
}
&s[..end]
}
fn consume_attr_value(bytes: &[u8], eq_idx: usize) -> Option<(usize, bool)> {
let mut j = eq_idx + 1;
while j < bytes.len() && bytes[j].is_ascii_whitespace() {
j += 1;
}
match bytes.get(j) {
Some("e @ (b'"' | b'\'')) => {
let after_quote = j + 1;
let close_off = bytes.get(after_quote..)?.iter().position(|&b| b == quote)?;
Some((after_quote + close_off + 1, true))
}
_ => Some((j, false)),
}
}
fn find_tag_end(window: &str) -> Option<usize> {
let naive_gt = window.find('>')?;
if !window[..naive_gt].contains('"') && !window[..naive_gt].contains('\'') {
return Some(naive_gt);
}
let bytes = window.as_bytes();
let mut i = 0;
let mut in_unquoted_value = false;
loop {
let rel = bytes
.get(i..)?
.iter()
.position(|&b| b == b'>' || b == b'=' || b.is_ascii_whitespace())?;
let idx = i + rel;
match bytes[idx] {
b'>' => return Some(idx),
b'=' if !in_unquoted_value => {
let (next_i, quoted) = consume_attr_value(bytes, idx)?;
in_unquoted_value = !quoted;
i = next_i;
}
b if b.is_ascii_whitespace() => {
in_unquoted_value = false;
i = idx + 1;
}
_ => {
i = idx + 1;
}
}
}
}
fn parse_open_tag(s: &str) -> Option<(String, usize)> {
debug_assert!(s.starts_with('<'));
let rest = &s[1..];
let first = rest.chars().next()?;
if !first.is_ascii_alphabetic() {
return None;
}
let window = bounded_prefix(rest, MAX_TAG_SCAN);
let gt = find_tag_end(window)?;
let name_end = window[..gt]
.find(|c: char| c.is_whitespace() || c == '/')
.unwrap_or(gt);
let tag = window[..name_end].to_ascii_lowercase();
Some((tag, 1 + gt + 1))
}
fn decode_entities(raw: &str) -> String {
if !raw.contains('&') {
return raw.to_owned();
}
let mut out = String::with_capacity(raw.len());
let mut chars = raw.char_indices();
while let Some((i, ch)) = chars.next() {
if ch != '&' {
out.push(ch);
continue;
}
let rest = &raw[i..];
let window_end = rest
.char_indices()
.nth(11)
.map_or(rest.len(), |(off, _)| off);
let Some(semi) = rest[..window_end].find(';') else {
out.push('&');
continue;
};
let entity = &rest[1..semi];
let decoded = decode_one_entity(entity);
match decoded {
Some(c) => {
out.push(c);
for _ in 0..semi {
chars.next();
}
}
None => out.push('&'),
}
}
out
}
fn decode_one_entity(entity: &str) -> Option<char> {
match entity {
"amp" => Some('&'),
"lt" => Some('<'),
"gt" => Some('>'),
"quot" => Some('"'),
"apos" => Some('\''),
"nbsp" => Some('\u{00A0}'),
"mdash" => Some('—'),
"ndash" => Some('–'),
"hellip" => Some('…'),
"copy" => Some('©'),
_ => {
let dec = entity.strip_prefix('#')?;
let value = if let Some(hex) = dec.strip_prefix('x').or_else(|| dec.strip_prefix('X')) {
u32::from_str_radix(hex, 16).ok()?
} else {
dec.parse::<u32>().ok()?
};
char::from_u32(value)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn text(children: &[Node]) -> String {
children
.iter()
.map(|n| match n {
Node::Text(t) => t.clone(),
Node::Element { children, .. } => text(children),
})
.collect()
}
#[test]
fn plain_text_round_trips() {
let nodes = parse("hello world");
assert_eq!(nodes, vec![Node::Text("hello world".to_owned())]);
}
#[test]
fn nested_elements_build_a_tree() {
let nodes = parse("<p>Hello <strong>bold</strong> world</p>");
assert_eq!(nodes.len(), 1);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Hello bold world");
assert!(matches!(&children[1], Node::Element { tag, .. } if tag == "strong"));
}
#[test]
fn an_omitted_li_closing_tag_is_implied_by_the_next_li() {
let nodes = parse("<ul><li>One<li>Two</ul>");
assert_eq!(nodes.len(), 1);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling <li>s, got {children:?}"
);
for (child, expected_text) in children.iter().zip(["One", "Two"]) {
let Node::Element { tag, children } = child else {
panic!("expected an element")
};
assert_eq!(tag, "li");
assert_eq!(text(children), expected_text);
}
}
#[test]
fn an_omitted_li_closing_tag_is_implied_through_a_transparent_inline_wrapper() {
let nodes = parse("<ul><li><span>One<li>Two</ul>");
assert_eq!(nodes.len(), 1);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling <li>s, got {children:?}"
);
let Node::Element {
tag,
children: first_li,
} = &children[0]
else {
panic!("expected an element")
};
assert_eq!(tag, "li");
assert_eq!(first_li.len(), 1, "expected one <span> child");
assert!(matches!(&first_li[0], Node::Element { tag, .. } if tag == "span"));
assert_eq!(text(first_li), "One");
let Node::Element {
tag,
children: second_li,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "li");
assert_eq!(text(second_li), "Two");
}
#[test]
fn an_omitted_li_closing_tag_is_implied_through_the_remaining_transparent_wrappers() {
for wrapper in ["small", "code", "abbr", "label"] {
let html = format!("<ul><li><{wrapper}>One<li>Two</ul>");
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "wrapper {wrapper:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling <li>s for wrapper {wrapper:?}, got {children:?}"
);
let Node::Element { tag, .. } = &children[1] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "li", "wrapper {wrapper:?}");
}
}
#[test]
fn an_omitted_li_closing_tag_is_implied_through_any_unrecognized_wrapper_tag() {
for wrapper in ["mark", "time", "cite", "made-up-tag"] {
let html = format!("<ul><li><{wrapper}>One<li>Two</ul>");
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "wrapper {wrapper:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling <li>s for wrapper {wrapper:?}, got {children:?}"
);
let Node::Element { tag, .. } = &children[1] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "li", "wrapper {wrapper:?}");
}
}
#[test]
fn an_omitted_li_closing_tag_is_implied_through_an_ordinary_block_wrapper() {
for wrapper in ["div", "h2", "section", "blockquote", "header"] {
let html = format!("<ul><li><{wrapper}>One<li>Two</ul>");
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "wrapper {wrapper:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling <li>s for wrapper {wrapper:?}, got {children:?}"
);
let Node::Element {
tag,
children: first_li,
} = &children[0]
else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "li", "wrapper {wrapper:?}");
assert_eq!(
first_li.len(),
1,
"expected one wrapper child ({wrapper:?})"
);
assert!(
matches!(&first_li[0], Node::Element { tag, .. } if tag == wrapper),
"wrapper {wrapper:?}: expected the first <li> to still contain its wrapper, \
got {first_li:?}"
);
assert_eq!(text(first_li), "One", "wrapper {wrapper:?}");
let Node::Element { tag, children } = &children[1] else {
panic!("expected an element ({wrapper:?})")
};
assert_eq!(tag, "li", "wrapper {wrapper:?}");
assert_eq!(text(children), "Two", "wrapper {wrapper:?}");
}
}
#[test]
fn nested_list_scope_barrier_survives_the_ordinary_block_wrapper_fix() {
let nodes = parse("<ul><li>Parent<div><ul><li>Child</ul></div><li>Sibling</ul>");
assert_eq!(nodes.len(), 1);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two sibling top-level <li>s, got {children:?}"
);
let Node::Element {
tag,
children: first_li,
} = &children[0]
else {
panic!("expected an element")
};
assert_eq!(tag, "li");
assert_eq!(first_li.len(), 2, "expected text then <div>: {first_li:?}");
assert!(matches!(&first_li[0], Node::Text(t) if t == "Parent"));
let Node::Element {
tag,
children: div_children,
} = &first_li[1]
else {
panic!("expected the <div>")
};
assert_eq!(tag, "div");
assert_eq!(div_children.len(), 1, "expected the nested <ul>");
let Node::Element {
tag,
children: inner_ul,
} = &div_children[0]
else {
panic!("expected the nested <ul>")
};
assert_eq!(tag, "ul");
assert_eq!(inner_ul.len(), 1, "expected the inner <li>");
assert_eq!(text(inner_ul), "Child");
let Node::Element {
tag,
children: second_li,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "li");
assert_eq!(text(second_li), "Sibling");
}
#[test]
fn an_omitted_td_closing_tag_is_implied_by_the_next_td_or_tr() {
let nodes = parse("<table><tr><td>A<td>B<tr><td>C</table>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "table");
assert_eq!(
children.len(),
2,
"expected two sibling <tr>s, got {children:?}"
);
let Node::Element {
tag,
children: row1,
} = &children[0]
else {
panic!("expected an element")
};
assert_eq!(tag, "tr");
assert_eq!(row1.len(), 2, "expected two sibling <td>s, got {row1:?}");
assert_eq!(text(std::slice::from_ref(&row1[0])), "A");
assert_eq!(text(std::slice::from_ref(&row1[1])), "B");
let Node::Element {
tag,
children: row2,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "tr");
assert_eq!(row2.len(), 1);
assert_eq!(text(row2), "C");
}
#[test]
fn omitted_th_tr_and_thead_closing_tags_are_implied_by_a_following_tbody() {
let nodes = parse("<table><thead><tr><th>H<tbody><tr><td>A</table>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "table");
assert_eq!(
children.len(),
2,
"expected <thead> and <tbody> as siblings, got {children:?}"
);
let Node::Element {
tag,
children: thead_children,
} = &children[0]
else {
panic!("expected an element")
};
assert_eq!(tag, "thead");
assert_eq!(thead_children.len(), 1, "expected one <tr>");
assert_eq!(text(thead_children), "H");
let Node::Element {
tag,
children: tbody_children,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "tbody");
assert_eq!(tbody_children.len(), 1, "expected one <tr>");
assert_eq!(
text(tbody_children),
"A",
"the body row must be a sibling row, not text flattened into the header cell"
);
}
#[test]
fn an_omitted_p_closing_tag_is_implied_by_a_following_block_element() {
let nodes = parse("<p>Intro<table><tr><td>A</td><td>B</td></tr></table><p>After");
assert_eq!(
nodes.len(),
3,
"expected <p>, <table>, <p> as three siblings, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Intro");
assert!(matches!(&nodes[1], Node::Element { tag, .. } if tag == "table"));
let Node::Element { tag, children } = &nodes[2] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "After");
}
#[test]
fn an_omitted_p_closing_tag_is_implied_through_intervening_inline_formatting() {
let nodes = parse("<p><strong>Intro<table><tr><td>A</td><td>B</td></tr></table><p>After");
assert_eq!(
nodes.len(),
3,
"expected <p>, <table>, <p> as three siblings, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(
children.len(),
1,
"expected a single <strong> child, got {children:?}"
);
assert!(matches!(&children[0], Node::Element { tag, .. } if tag == "strong"));
assert_eq!(text(children), "Intro");
assert!(matches!(&nodes[1], Node::Element { tag, .. } if tag == "table"));
let Node::Element { tag, children } = &nodes[2] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "After");
}
#[test]
fn an_omitted_head_closing_tag_is_implied_by_body() {
let nodes = parse("<html><head><title>X</title><body><p>Visible</p></body></html>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "html");
assert_eq!(
children.len(),
2,
"expected <head> and <body> as siblings, got {children:?}"
);
assert!(matches!(&children[0], Node::Element { tag, .. } if tag == "head"));
let Node::Element {
tag,
children: body_children,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "body");
assert_eq!(text(body_children), "Visible");
}
#[test]
fn an_omitted_body_start_tag_also_implies_a_head_close() {
let nodes = parse("<html><head><title>X</title><p>Visible</p></html>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "html");
assert_eq!(
children.len(),
2,
"expected <head> and <p> as siblings, got {children:?}"
);
assert!(matches!(&children[0], Node::Element { tag, .. } if tag == "head"));
let Node::Element {
tag,
children: p_children,
} = &children[1]
else {
panic!("expected an element")
};
assert_eq!(tag, "p");
assert_eq!(text(p_children), "Visible");
}
#[test]
fn non_whitespace_text_also_implies_a_head_close() {
let nodes = parse("<html><head><title>X</title>Visible</html>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "html");
assert_eq!(
children.len(),
2,
"expected <head> and the bare text as siblings, got {children:?}"
);
assert!(matches!(&children[0], Node::Element { tag, .. } if tag == "head"));
assert_eq!(children[1], Node::Text("Visible".to_owned()));
}
#[test]
fn whitespace_only_text_does_not_close_an_open_head() {
let nodes =
parse("<html><head>\n <title>X</title>\n</head><body><p>Visible</p></body></html>");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "html");
let Node::Element {
tag: head_tag,
children: head_children,
} = &children[0]
else {
panic!("expected an element")
};
assert_eq!(head_tag, "head");
assert!(
head_children
.iter()
.any(|n| matches!(n, Node::Element { tag, .. } if tag == "title")),
"the <title> must still be a child of <head>, not hoisted out by whitespace"
);
}
#[test]
fn script_content_with_a_stray_angle_bracket_does_not_swallow_later_siblings() {
let nodes = parse("<script>if(a<b){}</script><p>Visible</p>");
assert_eq!(
nodes.len(),
2,
"the <p> must be a sibling of <script>, not swallowed into it"
);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn oversized_script_tag_does_not_leak_its_source_as_visible_text() {
let oversized_attr = "Q".repeat(5000);
let html = format!(
r#"<script data-x="{oversized_attr}">var secret = "should never render";</script><p>Visible</p>"#
);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"the oversized <script> must not leak any node into the tree, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "p");
let rendered = text(children);
assert_eq!(rendered, "Visible");
assert!(
!rendered.contains("secret") && !rendered.contains('Q'),
"the script's source and its oversized attribute value must never appear as \
visible text, got {rendered:?}"
);
}
#[test]
fn oversized_tag_with_a_closing_tag_look_alike_in_its_own_attribute_is_not_fooled() {
let oversized_attr = format!("</script>{}", "Q".repeat(5000));
let html = format!(r#"<script data-x="{oversized_attr}">Secret</script><p>Visible</p>"#);
let nodes = parse(&html);
let rendered = text(&nodes);
assert!(
!rendered.contains("Secret") && !rendered.contains('Q'),
"the script's source and its oversized attribute value (including the embedded \
</script>-looking substring) must never appear as visible text, got {rendered:?}"
);
assert!(
rendered.contains("Visible"),
"the following sibling <p> must still render normally, got {rendered:?}"
);
}
#[test]
fn oversized_title_tag_does_not_leak_into_the_visible_document() {
let oversized_attr = "Q".repeat(5000);
let html = format!(
r#"<head><title data-x="{oversized_attr}">Secret</title></head><p>Visible</p>"#
);
let nodes = parse(&html);
let rendered = text(&nodes);
assert!(
!rendered.contains("Secret") && !rendered.contains('Q'),
"the title's text and its oversized attribute value must never appear as visible \
text, got {rendered:?}"
);
assert!(
rendered.contains("Visible"),
"the following sibling <p> must still render normally, got {rendered:?}"
);
}
#[test]
fn oversized_noscript_and_template_tags_do_not_leak_into_the_visible_document() {
for tag in ["noscript", "template"] {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<{tag} data-x="{oversized_attr}">Secret</{tag}><p>Visible</p>"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"tag {tag:?}: expected exactly the oversized element and its sibling <p> at the \
top level (nothing escaped as an extra sibling), got {nodes:?}"
);
let Node::Element { tag: first_tag, .. } = &nodes[0] else {
panic!("tag {tag:?}: expected the first top-level node to be an element")
};
assert_eq!(first_tag, tag);
let Node::Element {
tag: second_tag,
children,
} = &nodes[1]
else {
panic!("tag {tag:?}: expected the second top-level node to be an element")
};
assert_eq!(second_tag, "p");
assert_eq!(
text(children),
"Visible",
"tag {tag:?}: the following sibling <p> must still render normally"
);
}
}
#[test]
fn oversized_head_tag_does_not_swallow_the_rest_of_the_document_at_an_implicit_close() {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<head data-x="{oversized_attr}"><body>Visible</body>"#);
let nodes = parse(&html);
let rendered = text(&nodes);
assert!(
!rendered.contains('Q'),
"the oversized attribute value must never appear as visible text, got {rendered:?}"
);
assert!(
rendered.contains("Visible"),
"the <body> content must still render even though </head> was never written, got \
{rendered:?}"
);
}
#[test]
fn oversized_template_nested_inside_itself_hides_everything_up_to_the_outer_close() {
let oversized_attr = "Q".repeat(5000);
let html = format!(
r#"<template data-x="{oversized_attr}"><template>inner</template>leak</template><p>Visible</p>"#
);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected exactly the outer template element and its sibling <p> at the top level \
(nothing escaped as an extra sibling), got {nodes:?}"
);
let Node::Element { tag: first_tag, .. } = &nodes[0] else {
panic!(
"expected the first top-level node to be the outer template element, not a \
leaked text node, got {:?}",
nodes[0]
)
};
assert_eq!(first_tag, "template");
let Node::Element {
tag: second_tag,
children,
} = &nodes[1]
else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(second_tag, "p");
assert_eq!(
text(children),
"Visible",
"the following sibling <p> must still render normally"
);
}
#[test]
fn oversized_textarea_tag_still_renders_its_content_as_raw_text() {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<textarea data-x="{oversized_attr}">a<b</textarea><p>Visible</p>"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected the textarea element and its sibling <p>, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first top-level node to be an element")
};
assert_eq!(tag, "textarea");
assert_eq!(
text(children),
"a<b",
"the oversized attribute must not leak, and the real content must survive as \
literal raw text (not tokenized as markup), got {children:?}"
);
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn oversized_ordinary_tag_is_skipped_not_rendered_as_literal_text() {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<div data-state="{oversized_attr}">Visible</div>"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"expected a single <div>, with the oversized attribute nowhere in sight, got \
{nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(
text(children),
"Visible",
"the oversized attribute value must not leak into the div's own content"
);
}
#[test]
fn oversized_ordinary_tag_self_closing_and_void_variants_still_work() {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<my-widget data-x="{oversized_attr}" />Visible"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"expected a single <my-widget>, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "my-widget");
assert_eq!(text(children), "Visible");
let html = format!(r#"<img data-x="{oversized_attr}">Visible"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected the void <img> and its sibling text, got {nodes:?}"
);
assert!(matches!(
&nodes[0],
Node::Element { tag, children } if tag == "img" && children.is_empty()
));
assert_eq!(nodes[1], Node::Text("Visible".to_owned()));
}
#[test]
fn oversized_ordinary_tag_with_a_quoted_bracket_look_alike_is_not_fooled() {
let oversized_attr = format!("{}>", "Q".repeat(5000));
let html = format!(r#"<div data-x="{oversized_attr}">Visible</div>"#);
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "Visible");
}
#[test]
fn oversized_ordinary_closing_tag_beyond_the_fast_bound_still_finds_its_real_close() {
let oversized_attr = "Q".repeat(5000);
let html = format!(r#"<div>One</div data-x="{oversized_attr}">Visible"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected the closed <div> and the genuine trailing text, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "One");
assert_eq!(nodes[1], Node::Text("Visible".to_owned()));
}
#[test]
fn oversized_ordinary_tag_far_beyond_any_fixed_bound_still_finds_its_real_close() {
let oversized_attr = "Q".repeat(300 * 1024);
let html = format!(r#"<img src="{oversized_attr}">Visible"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected the void <img> and its sibling text, with no leaked attribute-soup \
siblings in between, got a tree with {} nodes",
nodes.len()
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "img");
assert!(
children.is_empty(),
"img is a void element, got {children:?}"
);
assert_eq!(
nodes[1],
Node::Text("Visible".to_owned()),
"the oversized attribute value must not leak into visible text"
);
}
#[test]
fn long_run_of_single_quoted_oversized_divs_is_linear_not_quadratic() {
let candidate = format!("<div data-x='{}'>", "A".repeat(5000));
let html = candidate.repeat(2_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "expected one nested chain of <div>s");
assert!(
start.elapsed() < std::time::Duration::from_secs(5),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn style_content_with_a_stray_angle_bracket_does_not_swallow_later_siblings() {
let nodes = parse("<style>/* a<b */</style><p>Visible</p>");
assert_eq!(nodes.len(), 2);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "style"));
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn title_content_with_a_stray_angle_bracket_does_not_swallow_later_siblings() {
let nodes = parse("<title>a<b</title><p>Visible</p>");
assert_eq!(
nodes.len(),
2,
"the <p> must be a sibling of <title>, not swallowed into it"
);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "title"));
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn textarea_content_with_a_stray_angle_bracket_is_not_dropped() {
let nodes = parse("<textarea>a<b</textarea><p>Visible</p>");
assert_eq!(
nodes.len(),
2,
"the <p> must be a sibling of <textarea>, not swallowed into it"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first top-level node to be an element")
};
assert_eq!(tag, "textarea");
assert_eq!(
text(children),
"a<b",
"the textarea's literal content must survive, not be dropped"
);
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn textarea_content_still_decodes_entities() {
let nodes = parse("<textarea>Ben & Jerry</textarea>");
assert_eq!(nodes.len(), 1);
let Node::Element { children, .. } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(text(children), "Ben & Jerry");
}
#[test]
fn void_elements_have_no_children_and_need_no_close() {
let nodes = parse("a<br>b<hr/>c");
assert_eq!(nodes.len(), 5);
assert!(
matches!(&nodes[1], Node::Element { tag, children } if tag == "br" && children.is_empty())
);
assert!(
matches!(&nodes[3], Node::Element { tag, children } if tag == "hr" && children.is_empty())
);
}
#[test]
fn unclosed_tags_are_auto_closed_at_eof() {
let nodes = parse("<div><p>oops");
assert_eq!(nodes.len(), 1);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected div")
};
assert_eq!(tag, "div");
assert!(matches!(&children[0], Node::Element { tag, .. } if tag == "p"));
}
#[test]
fn stray_closing_tag_is_ignored() {
let nodes = parse("hello</p>world");
assert_eq!(text(&nodes), "helloworld");
}
#[test]
fn empty_closing_tag_does_not_panic() {
assert_eq!(text(&parse("hello</>world")), "helloworld");
assert_eq!(text(&parse("<div></></div>")), "");
assert_eq!(text(&parse("</>")), "");
}
#[test]
fn html_comments_are_never_rendered() {
let nodes = parse("Before<!-- hidden -->After");
assert_eq!(text(&nodes), "BeforeAfter");
}
#[test]
fn abrupt_empty_comment_closes_immediately_not_at_the_next_real_close() {
let nodes = parse("<!--><p>Visible</p>");
assert_eq!(nodes.len(), 1, "expected just the <p>, got {nodes:?}");
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "p"));
assert_eq!(text(&nodes), "Visible");
}
#[test]
fn comment_closed_with_the_browser_tolerated_bang_terminator_does_not_swallow_the_rest_of_the_document()
{
let nodes = parse("<!-- hidden --!><p>Visible</p>");
assert_eq!(nodes.len(), 1, "got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the comment to be skipped and only the <p> to remain")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn comment_closes_at_whichever_terminator_appears_first() {
let nodes = parse("<!-- a --!>b<!-- c -->d");
assert_eq!(text(&nodes), "bd");
}
#[test]
fn ordinary_closing_tag_with_a_browser_tolerated_attribute_still_matches_its_opener() {
let nodes = parse(r#"<div>One</div data-x=">secret">Two"#);
assert_eq!(
nodes.len(),
2,
"expected the closed <div> and the genuine trailing text as separate top-level \
nodes, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "div");
assert_eq!(
text(children),
"One",
"the div's own content must not include anything from its closing tag's \
attribute soup"
);
assert_eq!(
nodes[1],
Node::Text("Two".to_owned()),
"only the genuine trailing text may appear as a sibling — the quoted attribute \
value must not leak, got {nodes:?}"
);
}
#[test]
fn entities_are_decoded() {
let nodes = parse("Fish & Chips — £5 AB");
assert_eq!(text(&nodes), "Fish & Chips — £5 AB");
}
#[test]
fn long_run_of_unterminated_ampersands_is_linear_not_quadratic() {
let html = "&".repeat(200_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(
text(&nodes),
html,
"unterminated `&` passes through unchanged"
);
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"decode_entities took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_unterminated_open_tags_is_linear_not_quadratic() {
let html = "<a".repeat(100_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(
text(&nodes),
html,
"unterminated `<a` fragments pass through unchanged as literal text"
);
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse_open_tag took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_unmatched_closing_tags_is_linear_not_quadratic() {
let html = format!("{}{}", "<a>".repeat(50_000), "</x>".repeat(50_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_never_closing_wrapper_tags_is_linear_not_quadratic() {
let html = "<span>".repeat(100_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "expected one deeply nested <span> tree");
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_never_closing_phrasing_wrappers_is_linear_not_quadratic() {
let html = "<strong>".repeat(100_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "expected one deeply nested <strong> tree");
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_unterminated_raw_text_closes_is_linear_not_quadratic() {
let html = format!("<script>{}", "</script ".repeat(50_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn raw_text_closing_tag_skips_a_quoted_bracket_look_alike() {
let html = r#"<script>hidden</script data-x=">secret">Visible"#;
let nodes = parse(html);
assert_eq!(
nodes.len(),
2,
"expected the script element and the trailing text, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "script");
assert_eq!(
text(children),
"hidden",
"the script's own content must stay hidden inside it"
);
assert_eq!(
nodes[1],
Node::Text("Visible".to_owned()),
"only the genuine trailing text must appear as a sibling — the quoted attribute \
value must not leak, got {nodes:?}"
);
}
#[test]
fn raw_text_closing_tag_accepts_arbitrary_whitespace_before_the_bracket() {
let padding = " ".repeat(200);
let html = format!("<script>alert(1)</script{padding}><p>Visible</p>");
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected the script element and its sibling <p>, got {nodes:?}"
);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn raw_text_closing_tag_with_a_long_non_whitespace_attribute_is_still_recognized() {
let value = "x".repeat(100);
let html = format!(r#"<script>hidden</script data-x="{value}">Visible"#);
let nodes = parse(&html);
assert_eq!(
nodes.len(),
2,
"expected script + trailing text, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "script");
assert_eq!(text(children), "hidden");
assert_eq!(nodes[1], Node::Text("Visible".to_owned()));
}
#[test]
fn raw_text_closing_tag_recognizes_xhtml_style_self_closing_slash() {
let html = "<script>hidden</script/><p>Visible</p>";
let nodes = parse(html);
assert_eq!(nodes.len(), 2, "expected script + <p>, got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "script");
assert_eq!(text(children), "hidden");
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn long_run_of_raw_text_closes_padded_with_whitespace_is_linear_not_quadratic() {
let candidate = format!("</script{}", " ".repeat(200));
let html = format!("<script>{}", candidate.repeat(2_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_raw_text_closes_padded_with_long_attributes_is_linear_not_quadratic() {
let candidate = format!("</script data-x=\"{}", "y".repeat(300));
let html = format!("<script>{}", candidate.repeat(2_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn self_closing_syntax_on_a_raw_text_element_is_ignored_like_a_real_browser() {
let html = r#"<script src="x" />alert(1)</script><p>Visible</p>"#;
let nodes = parse(html);
assert_eq!(
nodes.len(),
2,
"expected the script element and its sibling <p>, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "script");
assert_eq!(
text(children),
"alert(1)",
"the script source must stay inside the script element as raw content"
);
let Node::Element { tag, children } = &nodes[1] else {
panic!("expected the second top-level node to be an element")
};
assert_eq!(tag, "p");
assert_eq!(text(children), "Visible");
}
#[test]
fn self_closing_syntax_on_an_ordinary_non_void_element_is_ignored_like_a_real_browser() {
let nodes = parse("<ul><li/>One<li/>Two</ul>");
assert_eq!(nodes.len(), 1, "expected a single <ul>, got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "ul");
assert_eq!(
children.len(),
2,
"expected two <li> children, got {children:?}"
);
for (child, expected) in children.iter().zip(["One", "Two"]) {
let Node::Element { tag, children } = child else {
panic!("expected an <li> element, got {child:?}")
};
assert_eq!(tag, "li");
assert_eq!(text(children), expected);
}
}
#[test]
fn attribute_value_quote_separated_from_equals_by_whitespace_is_still_recognized() {
let nodes = parse(r#"<div title = "Balance > 100">Visible</div>"#);
assert_eq!(nodes.len(), 1, "expected a single <div>, got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "Visible");
}
#[test]
fn stray_equals_and_quote_inside_an_already_started_unquoted_value_does_not_swallow_the_tag() {
let nodes = parse(r#"<div title=x=">Visible</div>"#);
assert_eq!(nodes.len(), 1, "expected a single <div>, got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "Visible");
}
#[test]
fn adjacent_quoted_attributes_with_no_separating_whitespace_are_both_recognized() {
let nodes = parse(r#"<div a="x"b=">secret">Visible</div>"#);
assert_eq!(nodes.len(), 1, "expected a single <div>, got {nodes:?}");
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "Visible");
}
#[test]
fn closing_tag_deeper_than_the_scan_window_is_ignored_not_matched() {
let html = format!("<outer>{}</outer>tail", "<a>".repeat(600));
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"the out-of-window close must not split off a sibling at the root"
);
assert_eq!(text(&nodes), "tail");
}
#[test]
fn valid_tag_with_long_attribute_list_still_parses() {
let long_class = "flex items-center justify-between px-4 py-2 bg-white \
dark:bg-gray-900 border border-gray-200 rounded-lg shadow-sm \
hover:shadow-md transition-shadow duration-200 text-sm font-medium \
text-gray-700 dark:text-gray-300 focus:outline-none focus:ring-2 \
focus:ring-offset-2 data-controller=\"dropdown\" aria-label=\"menu\"";
assert!(
long_class.len() > 256,
"test fixture must exceed the old, too-tight window"
);
let html = format!("<div class=\"{long_class}\">Hello</div>");
let nodes = parse(&html);
assert_eq!(
text(&nodes),
"Hello",
"a long but well-formed opening tag must parse, not leak as literal text"
);
}
#[test]
fn quoted_greater_than_inside_an_attribute_does_not_end_the_tag_early() {
let nodes = parse(r#"<div title="Balance > 100">Visible</div>"#);
assert_eq!(
nodes.len(),
1,
"expected a single <div> node, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(
text(children),
"Visible",
"the quoted attribute value must not leak into the rendered text"
);
}
#[test]
fn quoted_apostrophe_greater_than_inside_an_attribute_does_not_end_the_tag_early() {
let nodes = parse("<div title='Balance > 100'>Visible</div>");
assert_eq!(nodes.len(), 1);
let Node::Element { children, .. } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(text(children), "Visible");
}
#[test]
fn literal_quote_in_an_unquoted_attribute_value_does_not_swallow_the_tag() {
let nodes = parse("<div title=it's>Visible</div>");
assert_eq!(
nodes.len(),
1,
"expected a single <div> node, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(tag, "div");
assert_eq!(text(children), "Visible");
}
#[test]
fn raw_text_closing_tag_with_a_literal_angle_bracket_in_a_quoted_attribute_still_closes() {
let nodes = parse(r#"<script>hidden</script data-x="<">Visible"#);
assert_eq!(
nodes.len(),
2,
"expected script + trailing text, got {nodes:?}"
);
let Node::Element { tag, children } = &nodes[0] else {
panic!("expected the first node to be an element")
};
assert_eq!(tag, "script");
assert_eq!(text(children), "hidden");
assert_eq!(nodes[1], Node::Text("Visible".to_owned()));
}
#[test]
fn long_run_of_unterminated_quoted_attributes_is_linear_not_quadratic() {
let html = "<a title=\"x".repeat(50_000);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(
nodes,
vec![Node::Element {
tag: "a".to_owned(),
children: Vec::new(),
}],
"the whole unterminated attribute must be swallowed into one auto-closed <a>, \
not leaked as visible text"
);
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"find_tag_end's quoted-attribute path took {:?} — looks quadratic",
start.elapsed()
);
}
#[test]
fn long_run_of_stray_apostrophes_before_the_real_close_is_linear_not_quadratic() {
let html = format!("<div title={}>Visible</div>", "it's ".repeat(50_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"expected a single <div> node, got {nodes:?}"
);
let Node::Element { children, .. } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(text(children), "Visible");
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"find_tag_end took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_whitespace_separated_stray_apostrophes_is_linear_not_quadratic() {
let html = format!("<div title={}>Visible</div>", "x '".repeat(50_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(
nodes.len(),
1,
"expected a single <div> node, got {nodes:?}"
);
let Node::Element { children, .. } = &nodes[0] else {
panic!("expected an element")
};
assert_eq!(text(children), "Visible");
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"find_tag_end took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn long_run_of_raw_text_closes_with_quoted_angle_brackets_is_linear_not_quadratic() {
let candidate = "</script data-x=\"<\" ";
let html = format!("<script>{}", candidate.repeat(2_000));
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "script"));
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn find_tag_end_skips_mixed_quote_styles_and_embedded_brackets() {
let w = r#" data-x="a" data-y='b>c' data-z="Balance > 100">Visible"#;
let expected = w.find("\">Visible").unwrap() + 1;
assert_eq!(find_tag_end(w), Some(expected));
}
#[test]
fn oversized_tag_with_many_short_quote_pairs_before_its_real_close_is_linear_not_quadratic() {
let pairs = 20_000;
let html = format!(
r"<script data-x={}>Secret</script><p>Visible</p>",
r#""a""#.repeat(pairs)
);
let start = std::time::Instant::now();
let nodes = parse(&html);
assert_eq!(nodes.len(), 1, "got {nodes:?}");
assert!(matches!(&nodes[0], Node::Element { tag, .. } if tag == "p"));
assert_eq!(text(&nodes), "Visible");
assert!(
start.elapsed() < std::time::Duration::from_secs(2),
"parse took {:?} — looks quadratic again",
start.elapsed()
);
}
#[test]
fn attributes_are_ignored_but_dont_break_parsing() {
let nodes = parse(r#"<p class="total" data-x='1'>Total</p>"#);
assert_eq!(text(&nodes), "Total");
}
#[test]
fn deeply_nested_input_does_not_overflow_the_stack() {
let mut html = String::new();
for _ in 0..50_000 {
html.push_str("<div>");
}
html.push('x');
for _ in 0..50_000 {
html.push_str("</div>");
}
let nodes = parse(&html);
assert_eq!(nodes.len(), 1);
}
#[test]
fn malformed_lone_angle_bracket_is_literal_text() {
let nodes = parse("a < b");
assert_eq!(text(&nodes), "a < b");
}
}