use std::collections::HashMap;
use crate::dom::{
Attr, AttrNs, Data, Document, Element, NONE, Name, NodeId, Ns, Positions, Quirks, Span,
};
use crate::tags::Tag;
use crate::tokenizer::{self, Doctype, Sink, TextMode, Tokenizer};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Mode {
Initial,
BeforeHtml,
BeforeHead,
InHead,
InHeadNoscript,
AfterHead,
InBody,
Text,
InTable,
InTableText,
InCaption,
InColumnGroup,
InTableBody,
InRow,
InCell,
InTemplate,
AfterBody,
InFrameset,
AfterFrameset,
AfterAfterBody,
AfterAfterFrameset,
}
#[derive(Clone, Copy)]
struct Start<'t> {
tag: Tag,
name: &'t str,
attrs: Option<&'t tokenizer::Tag<'t>>,
self_closing: bool,
}
impl<'t> Start<'t> {
fn bare(tag: Tag) -> Start<'static> {
Start {
tag,
name: tag.name(),
attrs: None,
self_closing: false,
}
}
fn attrs(&self) -> impl Iterator<Item = (&'t str, &'t str)> + use<'t> {
self.attrs.into_iter().flat_map(|t| t.attrs())
}
fn attr(&self, name: &str) -> Option<&'t str> {
self.attrs().find(|(n, _)| *n == name).map(|(_, v)| v)
}
}
#[derive(Clone, Copy)]
struct End<'t> {
tag: Tag,
name: &'t str,
}
#[derive(Clone, Copy)]
enum Tok<'t> {
Doctype(&'t Doctype<'t>),
Start(Start<'t>),
End(End<'t>),
Text(&'t str),
Comment(&'t str),
Pi(&'t str, &'t str),
Eof,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Open {
id: NodeId,
ns: Ns,
tag: Tag,
}
impl Open {
fn is(self, tag: Tag) -> bool {
self.ns == Ns::Html && self.tag == tag
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Scope {
Default,
ListItem,
Button,
Table,
}
const MARKER: NodeId = NONE;
struct Merged {
names: std::collections::HashSet<String>,
room: u32,
}
pub(crate) struct TreeBuilder {
pub(crate) doc: Document,
max_depth: Option<usize>,
open: Vec<Open>,
active: Vec<NodeId>,
mode: Mode,
original: Mode,
template_modes: Vec<Mode>,
head: NodeId,
form: NodeId,
frameset_ok: bool,
foster: bool,
scripting: bool,
context: Option<Open>,
pending: String,
pending_text: bool,
skip_newline: bool,
switch: Option<TextMode>,
done: bool,
eof_again: bool,
selected: HashMap<NodeId, NodeId>,
option_select: HashMap<NodeId, NodeId>,
merged: HashMap<NodeId, Merged>,
counts: [u32; 256],
foreign_boundaries: u32,
p_in_scope: Vec<bool>,
names: Box<[u32; NAME_SLOTS]>,
on_stack: Vec<bool>,
spans: bool,
at: [u32; 2],
pending_at: [u32; 2],
closing_name: String,
closing: bool,
sigs: Vec<u64>,
errors: bool,
errors_found: Vec<(&'static str, u32)>,
acknowledged: bool,
shadow_roots: bool,
shadow_templates: Vec<NodeId>,
}
const NAME_SLOTS: usize = 1024;
fn name_key(html: bool, name: &str) -> usize {
let mut h: u64 = if html {
0xcbf2_9ce4_8422_2325
} else {
0x8422_2325_cbf2_9ce4
};
for b in name.bytes() {
h ^= u64::from(b.to_ascii_lowercase());
h = h.wrapping_mul(0x0100_0000_01b3);
}
(h ^ (h >> 32)) as usize % NAME_SLOTS
}
fn is_space(c: u8) -> bool {
matches!(c, b'\t' | b'\n' | b'\x0C' | b'\r' | b' ')
}
fn is_space_char(c: char) -> bool {
matches!(c, '\t' | '\n' | '\x0C' | '\r' | ' ')
}
fn space_runs(s: &str) -> impl Iterator<Item = &str> {
s.split(|c: char| !is_space_char(c))
.filter(|r| !r.is_empty())
}
fn split_space(s: &str) -> (&str, &str) {
let n = s.bytes().take_while(|&b| is_space(b)).count();
s.split_at(n)
}
fn all_space(s: &str) -> bool {
s.bytes().all(is_space)
}
fn special(o: Open) -> bool {
use Tag::*;
match o.ns {
Ns::Html => matches!(
o.tag,
Address
| Applet
| Area
| Article
| Aside
| Base
| Basefont
| Bgsound
| Blockquote
| Body
| Br
| Button
| Caption
| Center
| Col
| Colgroup
| Dd
| Details
| Dir
| Div
| Dl
| Dt
| Embed
| Fieldset
| Figcaption
| Figure
| Footer
| Form
| Frame
| Frameset
| H1
| H2
| H3
| H4
| H5
| H6
| Head
| Header
| Hgroup
| Hr
| Html
| Iframe
| Img
| Input
| Keygen
| Li
| Link
| Listing
| Main
| Marquee
| Menu
| Meta
| Nav
| Noembed
| Noframes
| Noscript
| Object
| Ol
| P
| Param
| Plaintext
| Pre
| Script
| Search
| Section
| Select
| Source
| Style
| Summary
| Table
| Tbody
| Td
| Template
| Textarea
| Tfoot
| Th
| Thead
| Title
| Tr
| Track
| Ul
| Wbr
| Xmp
),
Ns::MathMl => matches!(o.tag, Mi | Mo | Mn | Ms | Mtext | AnnotationXml),
Ns::Svg => matches!(o.tag, ForeignObject | Desc | Title),
Ns::Xml => false,
}
}
fn scope_boundary(o: Open, scope: Scope) -> bool {
use Tag::*;
let base = || match o.ns {
Ns::Html => matches!(
o.tag,
Applet | Caption | Html | Table | Td | Th | Marquee | Object | Select | Template
),
Ns::MathMl => matches!(o.tag, Mi | Mo | Mn | Ms | Mtext | AnnotationXml),
Ns::Svg => matches!(o.tag, ForeignObject | Desc | Title),
Ns::Xml => false,
};
match scope {
Scope::Default => base(),
Scope::ListItem => base() || o.is(Ol) || o.is(Ul),
Scope::Button => base() || o.is(Button),
Scope::Table => o.is(Html) || o.is(Table) || o.is(Template),
}
}
const HEADINGS: [Tag; 6] = [Tag::H1, Tag::H2, Tag::H3, Tag::H4, Tag::H5, Tag::H6];
fn heading(tag: Tag) -> bool {
HEADINGS.contains(&tag)
}
fn implied(tag: Tag) -> bool {
use Tag::*;
matches!(
tag,
Dd | Dt | Li | Optgroup | Option | P | Rb | Rp | Rt | Rtc
)
}
fn mathml_text_integration(o: Open) -> bool {
o.ns == Ns::MathMl && matches!(o.tag, Tag::Mi | Tag::Mo | Tag::Mn | Tag::Ms | Tag::Mtext)
}
pub(crate) static SVG_TAG_NAMES: [(&str, &str); 37] = [
("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"),
];
pub(crate) fn svg_tag_name(name: &str) -> Option<u8> {
SVG_TAG_NAMES
.iter()
.position(|(lower, _)| *lower == name)
.map(|i| i as u8)
}
pub(crate) fn svg_attr_name(name: &str) -> Option<&'static str> {
Some(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",
_ => return None,
})
}
fn foreign_attr(name: &str) -> Option<(AttrNs, &'static str)> {
Some(match name {
"xlink:actuate" => (AttrNs::XLink, "actuate"),
"xlink:arcrole" => (AttrNs::XLink, "arcrole"),
"xlink:href" => (AttrNs::XLink, "href"),
"xlink:role" => (AttrNs::XLink, "role"),
"xlink:show" => (AttrNs::XLink, "show"),
"xlink:title" => (AttrNs::XLink, "title"),
"xlink:type" => (AttrNs::XLink, "type"),
"xml:lang" => (AttrNs::Xml, "lang"),
"xml:space" => (AttrNs::Xml, "space"),
"xmlns" => (AttrNs::Xmlns, "xmlns"),
"xmlns:xlink" => (AttrNs::Xmlns, "xlink"),
_ => return None,
})
}
fn quirky_public_id(public: &str) -> bool {
const STARTS: &[&str] = &[
"+//silmaril//dtd html pro v0r11 19970101//",
"-//as//dtd html 3.0 aswedit + extensions//",
"-//advasoft ltd//dtd html 3.0 aswedit + extensions//",
"-//ietf//dtd html 2.0 level 1//",
"-//ietf//dtd html 2.0 level 2//",
"-//ietf//dtd html 2.0 strict level 1//",
"-//ietf//dtd html 2.0 strict level 2//",
"-//ietf//dtd html 2.0 strict//",
"-//ietf//dtd html 2.0//",
"-//ietf//dtd html 2.1e//",
"-//ietf//dtd html 3.0//",
"-//ietf//dtd html 3.2 final//",
"-//ietf//dtd html 3.2//",
"-//ietf//dtd html 3//",
"-//ietf//dtd html level 0//",
"-//ietf//dtd html level 1//",
"-//ietf//dtd html level 2//",
"-//ietf//dtd html level 3//",
"-//ietf//dtd html strict level 0//",
"-//ietf//dtd html strict level 1//",
"-//ietf//dtd html strict level 2//",
"-//ietf//dtd html strict level 3//",
"-//ietf//dtd html strict//",
"-//ietf//dtd html//",
"-//metrius//dtd metrius presentational//",
"-//microsoft//dtd internet explorer 2.0 html strict//",
"-//microsoft//dtd internet explorer 2.0 html//",
"-//microsoft//dtd internet explorer 2.0 tables//",
"-//microsoft//dtd internet explorer 3.0 html strict//",
"-//microsoft//dtd internet explorer 3.0 html//",
"-//microsoft//dtd internet explorer 3.0 tables//",
"-//netscape comm. corp.//dtd html//",
"-//netscape comm. corp.//dtd strict html//",
"-//o'reilly and associates//dtd html 2.0//",
"-//o'reilly and associates//dtd html extended 1.0//",
"-//o'reilly and associates//dtd html extended relaxed 1.0//",
"-//sq//dtd html 2.0 hotmetal + extensions//",
"-//softquad software//dtd hotmetal pro 6.0::19990601::extensions to html 4.0//",
"-//softquad//dtd hotmetal pro 4.0::19971010::extensions to html 4.0//",
"-//spyglass//dtd html 2.0 extended//",
"-//sun microsystems corp.//dtd hotjava html//",
"-//sun microsystems corp.//dtd hotjava strict html//",
"-//w3c//dtd html 3 1995-03-24//",
"-//w3c//dtd html 3.2 draft//",
"-//w3c//dtd html 3.2 final//",
"-//w3c//dtd html 3.2//",
"-//w3c//dtd html 3.2s draft//",
"-//w3c//dtd html 4.0 frameset//",
"-//w3c//dtd html 4.0 transitional//",
"-//w3c//dtd html experimental 19960712//",
"-//w3c//dtd html experimental 970421//",
"-//w3c//dtd w3 html//",
"-//w3o//dtd w3 html 3.0//",
"-//webtechs//dtd mozilla html 2.0//",
"-//webtechs//dtd mozilla html//",
];
STARTS.iter().any(|s| starts_with_ci(public, s))
}
fn starts_with_ci(s: &str, prefix: &str) -> bool {
s.len() >= prefix.len() && s.as_bytes()[..prefix.len()].eq_ignore_ascii_case(prefix.as_bytes())
}
fn doctype_quirks(d: &Doctype<'_>) -> Quirks {
let public = d.public_id.unwrap_or("");
let system = d.system_id;
let eq = |a: &str, b: &str| a.eq_ignore_ascii_case(b);
if d.force_quirks
|| d.name != Some("html")
|| d.public_id.is_some_and(|p| {
eq(p, "-//W3O//DTD W3 HTML Strict 3.0//EN//")
|| eq(p, "-/W3C/DTD HTML 4.0 Transitional/EN")
|| eq(p, "HTML")
})
|| system.is_some_and(|s| {
eq(
s,
"http://www.ibm.com/data/dtd/v11/ibmxhtml1-transitional.dtd",
)
})
|| d.public_id.is_some_and(quirky_public_id)
|| (system.is_none()
&& (starts_with_ci(public, "-//W3C//DTD HTML 4.01 Frameset//")
|| starts_with_ci(public, "-//W3C//DTD HTML 4.01 Transitional//")))
{
Quirks::Quirks
} else if starts_with_ci(public, "-//W3C//DTD XHTML 1.0 Frameset//")
|| starts_with_ci(public, "-//W3C//DTD XHTML 1.0 Transitional//")
|| (system.is_some()
&& (starts_with_ci(public, "-//W3C//DTD HTML 4.01 Frameset//")
|| starts_with_ci(public, "-//W3C//DTD HTML 4.01 Transitional//")))
{
Quirks::Limited
} else {
Quirks::No
}
}
impl TreeBuilder {
pub(crate) fn new(capacity: usize, scripting: bool) -> TreeBuilder {
TreeBuilder {
doc: Document::new(Data::Document, capacity),
max_depth: None,
open: Vec::with_capacity(64),
active: Vec::new(),
mode: Mode::Initial,
original: Mode::Initial,
template_modes: Vec::new(),
head: NONE,
form: NONE,
frameset_ok: true,
foster: false,
scripting,
context: None,
pending: String::new(),
pending_text: false,
skip_newline: false,
switch: None,
done: false,
eof_again: false,
selected: HashMap::new(),
option_select: HashMap::new(),
merged: HashMap::new(),
counts: [0; 256],
foreign_boundaries: 0,
p_in_scope: Vec::with_capacity(64),
names: Box::new([0; NAME_SLOTS]),
on_stack: vec![false; capacity / 24 + 1024],
spans: false,
at: [0; 2],
pending_at: [0; 2],
closing_name: String::new(),
closing: false,
sigs: Vec::new(),
errors: false,
errors_found: Vec::new(),
acknowledged: false,
shadow_roots: false,
shadow_templates: Vec::new(),
}
}
#[cold]
fn err(&mut self, code: &'static str) {
if self.errors {
self.errors_found.push((code, self.at[0]));
}
}
#[cold]
fn err_in(&mut self, code: &'static str, s: &str, i: usize) {
if self.errors {
let at = self
.doc
.source_offset(s)
.map_or(self.at[0], |o| (o + i) as u32);
self.errors_found.push((code, at));
}
}
fn text_at(&self, s: &str) -> [u32; 2] {
match self.doc.source_offset(s) {
Some(o) => [o as u32, (o + s.len()) as u32],
None => self.at,
}
}
fn finish_errors(&mut self) {
if !self.errors {
return;
}
let mut found = std::mem::take(&mut self.errors_found);
found.sort_by_key(|&(_, at)| at);
let src = self.doc.src.as_bytes();
let (mut line, mut column, mut at) = (1, 1, 0);
let mut errors = Vec::with_capacity(found.len());
for (code, offset) in found {
let offset = (offset as usize).min(src.len());
let from = at;
for i in memchr::memchr_iter(b'\n', &src[from..offset]) {
line += 1;
column = 1;
at = from + i + 1;
}
column += src[at..offset]
.iter()
.filter(|&&b| (b as i8) >= -0x40)
.count();
at = offset;
let original = self
.doc
.positions
.as_deref()
.map_or(offset, |p| p.original(offset as u32));
errors.push(crate::SyntaxError {
code,
offset: original,
line,
column,
});
}
self.doc.errors = errors;
}
pub(crate) fn fragment(&mut self, ns: Ns, name: &str) -> Option<TextMode> {
let tag = Tag::from_name(&name.to_ascii_lowercase());
let context = self.create(
&Start {
tag,
name,
attrs: None,
self_closing: false,
},
ns,
);
self.context = Some(Open {
id: context,
ns,
tag,
});
let root = self.create(&Start::bare(Tag::Html), Ns::Html);
self.doc.insert(0, root, NONE);
self.push_open(Open {
id: root,
ns: Ns::Html,
tag: Tag::Html,
});
if ns == Ns::Html && tag == Tag::Template {
self.template_modes.push(Mode::InTemplate);
}
if ns == Ns::Html && tag == Tag::Form {
self.form = context;
}
self.reset_mode();
if ns != Ns::Html {
return None;
}
match tag {
Tag::Title | Tag::Textarea => Some(TextMode::Rcdata),
Tag::Style | Tag::Xmp | Tag::Iframe | Tag::Noembed | Tag::Noframes => {
Some(TextMode::Rawtext)
}
Tag::Script => Some(TextMode::ScriptData),
Tag::Noscript if self.scripting => Some(TextMode::Rawtext),
Tag::Plaintext => Some(TextMode::Plaintext),
_ => None,
}
}
pub(crate) fn finish_fragment(&mut self) {
let root = self
.doc
.first_child(0)
.expect("the fragment's html element");
self.doc.detach(root);
while let Some(child) = self.doc.first_child(root) {
self.doc.detach(child);
self.doc.insert(0, child, NONE);
}
self.doc.nodes[0].data = Data::Fragment;
}
fn current(&self) -> Open {
*self.open.last().expect("an open element")
}
fn adjusted_current(&self) -> Option<Open> {
match self.context {
Some(c) if self.open.len() == 1 => Some(c),
_ => self.open.last().copied(),
}
}
fn mark(&mut self, id: NodeId, on: bool) {
let i = id as usize;
if let Some(flag) = self.on_stack.get_mut(i) {
*flag = on;
} else {
self.on_stack.resize(i * 2 + 1024, false);
self.on_stack[i] = on;
}
}
fn count(&mut self, o: Open, by: i32) {
debug_assert_eq!(
self.open_contains(o.id),
by < 0,
"node {} {} the stack of open elements twice",
o.id,
if by < 0 { "leaves" } else { "joins" }
);
debug_assert!(
self.element_at(o.id) == Some(o),
"the stack's entry for node {} isn't its element",
o.id
);
self.mark(o.id, by > 0);
if by < 0 && self.closing {
self.closed_by_end_tag(o.id);
}
if o.ns == Ns::Html && o.tag != Tag::Other {
debug_assert!(
by > 0 || self.counts[o.tag as usize] > 0,
"{:?} counted below 0",
o.tag
);
self.counts[o.tag as usize] = self.counts[o.tag as usize].wrapping_add_signed(by);
return;
}
if scope_boundary(o, Scope::Default) {
self.foreign_boundaries = self.foreign_boundaries.wrapping_add_signed(by);
}
let Some(name) = self.doc.element(o.id).map(|e| self.doc.element_name(e)) else {
return;
};
let n = &mut self.names[name_key(o.ns == Ns::Html, name)];
debug_assert!(by > 0 || *n > 0, "{name} counted below 0");
*n = n.wrapping_add_signed(by);
}
fn open_named(&self, html: bool, name: &str) -> u32 {
self.names[name_key(html, name)]
}
fn push_open(&mut self, o: Open) {
self.count(o, 1);
self.open.push(o);
let below = self.p_in_scope.last().copied().unwrap_or(false);
self.p_in_scope
.push(o.is(Tag::P) || below && !scope_boundary(o, Scope::Button));
}
fn remove_open_at(&mut self, i: usize) -> Open {
let o = self.open.remove(i);
self.count(o, -1);
self.p_in_scope_from(i);
o
}
fn insert_open_at(&mut self, i: usize, o: Open) {
self.count(o, 1);
self.open.insert(i, o);
self.p_in_scope_from(i);
}
fn p_in_scope_from(&mut self, i: usize) {
self.p_in_scope.truncate(i);
let mut below = self.p_in_scope.last().copied().unwrap_or(false);
for &o in &self.open[i..] {
below = o.is(Tag::P) || below && !scope_boundary(o, Scope::Button);
self.p_in_scope.push(below);
}
}
fn open_count(&self, tag: Tag) -> u32 {
self.counts[tag as usize]
}
fn pop(&mut self) -> Option<Open> {
let o = self.open.pop()?;
self.p_in_scope.pop();
self.count(o, -1);
if o.is(Tag::Option) {
self.option_popped(o.id);
}
Some(o)
}
fn truncate_open(&mut self, len: usize) {
while self.open.len() > len {
self.pop();
}
}
fn template_open(&self) -> bool {
self.open_count(Tag::Template) > 0
}
fn in_template_contents(&self) -> bool {
self.template_open() || self.context.is_some_and(|c| c.is(Tag::Template))
}
fn boundaries_above_root(&self, scope: Scope) -> u32 {
use Tag::*;
let base = self.foreign_boundaries
+ [
Applet, Caption, Table, Td, Th, Marquee, Object, Select, Template,
]
.iter()
.map(|&t| self.open_count(t))
.sum::<u32>();
match scope {
Scope::Default => base,
Scope::ListItem => base + self.open_count(Ol) + self.open_count(Ul),
Scope::Button => base + self.open_count(Button),
Scope::Table => self.open_count(Table) + self.open_count(Template),
}
}
fn in_scope(&self, tag: Tag, scope: Scope) -> bool {
if tag != Tag::Other && self.open_count(tag) == 0 {
return false;
}
if matches!(tag, Tag::Body | Tag::Html) {
return self.boundaries_above_root(scope) == 0;
}
self.in_scope_walk(tag, scope)
}
fn in_scope_walk(&self, tag: Tag, scope: Scope) -> bool {
let walk = || {
for &o in self.open.iter().rev() {
if o.is(tag) {
return true;
}
if scope_boundary(o, scope) {
return false;
}
}
false
};
if tag == Tag::P && scope == Scope::Button {
let known = self.p_in_scope.last().copied().unwrap_or(false);
debug_assert_eq!(known, walk(), "p_in_scope is out of step");
return known;
}
walk()
}
fn in_scope_any(&self, tags: &[Tag], scope: Scope) -> bool {
if tags.iter().all(|&t| self.open_count(t) == 0) {
return false;
}
for &o in self.open.iter().rev() {
if o.ns == Ns::Html && tags.contains(&o.tag) {
return true;
}
if scope_boundary(o, scope) {
return false;
}
}
false
}
fn node_in_scope(&self, id: NodeId) -> bool {
for &o in self.open.iter().rev() {
if o.id == id {
return true;
}
if scope_boundary(o, Scope::Default) {
return false;
}
}
false
}
fn pop_until(&mut self, tag: Tag) {
while let Some(o) = self.pop() {
if o.is(tag) {
break;
}
}
}
fn pop_until_where(&mut self, f: impl Fn(Tag) -> bool) {
while let Some(o) = self.pop() {
if o.ns == Ns::Html && f(o.tag) {
break;
}
}
}
fn remove_open(&mut self, id: NodeId) {
if let Some(i) = self.open.iter().rposition(|o| o.id == id) {
self.remove_open_at(i);
}
}
fn generate_implied(&mut self, except: Option<Tag>) {
while let Some(&o) = self.open.last() {
if o.ns == Ns::Html && implied(o.tag) && Some(o.tag) != except {
self.pop();
} else {
break;
}
}
}
fn generate_implied_thoroughly(&mut self) {
use Tag::*;
while let Some(&o) = self.open.last() {
if o.ns == Ns::Html
&& (implied(o.tag)
|| matches!(
o.tag,
Caption | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
))
{
self.pop();
} else {
break;
}
}
}
fn close_p(&mut self) {
self.generate_implied(Some(Tag::P));
if !self.current().is(Tag::P) {
self.err("unexpected-end-tag");
}
self.pop_until(Tag::P);
}
fn close_p_in_button_scope(&mut self) {
if self.in_scope(Tag::P, Scope::Button) {
self.close_p();
}
}
fn clear_to_table_context(&mut self) {
while !matches!(self.current().tag, Tag::Table | Tag::Template | Tag::Html)
|| self.current().ns != Ns::Html
{
self.pop();
}
}
fn clear_to_table_body_context(&mut self) {
use Tag::*;
while !matches!(self.current().tag, Tbody | Tfoot | Thead | Template | Html)
|| self.current().ns != Ns::Html
{
self.pop();
}
}
fn clear_to_table_row_context(&mut self) {
while !matches!(self.current().tag, Tag::Tr | Tag::Template | Tag::Html)
|| self.current().ns != Ns::Html
{
self.pop();
}
}
fn reset_mode(&mut self) {
use Tag::*;
if self.context.is_none()
&& [
Td, Th, Tr, Tbody, Thead, Tfoot, Caption, Colgroup, Table, Template, Head,
]
.iter()
.all(|&t| self.open_count(t) == 0)
{
if self.open_count(Body) > 0 {
self.mode = Mode::InBody;
return;
}
if self.open_count(Frameset) > 0 {
self.mode = Mode::InFrameset;
return;
}
}
for i in (0..self.open.len()).rev() {
let last = i == 0;
let mut node = self.open[i];
if last && let Some(c) = self.context {
node = c;
}
if node.ns != Ns::Html {
if last {
self.mode = Mode::InBody;
return;
}
continue;
}
self.mode = match node.tag {
Td | Th if !last => Mode::InCell,
Tr => Mode::InRow,
Tbody | Thead | Tfoot => Mode::InTableBody,
Caption => Mode::InCaption,
Colgroup => Mode::InColumnGroup,
Table => Mode::InTable,
Template => *self.template_modes.last().unwrap_or(&Mode::InBody),
Head if !last => Mode::InHead,
Body => Mode::InBody,
Frameset => Mode::InFrameset,
Html => {
if self.head == NONE {
Mode::BeforeHead
} else {
Mode::AfterHead
}
}
_ if last => Mode::InBody,
_ => continue,
};
return;
}
}
#[cfg(debug_assertions)]
fn check_stack(&self, all: bool) {
let mut counts = [0u32; 256];
let mut names = vec![0u32; NAME_SLOTS];
for &o in &self.open {
assert!(
self.open_contains(o.id),
"node {} is open but not marked",
o.id
);
assert_eq!(
self.element_at(o.id),
Some(o),
"the stack's entry for {}",
o.id
);
if o.ns == Ns::Html && o.tag != Tag::Other {
counts[o.tag as usize] += 1;
} else if let Some(e) = self.doc.element(o.id) {
names[name_key(o.ns == Ns::Html, self.doc.element_name(e))] += 1;
}
}
assert!(counts == self.counts, "counts disagree with the stack");
assert!(names[..] == self.names[..], "names disagree with the stack");
let foreign = self
.open
.iter()
.filter(|&&o| o.ns != Ns::Html && scope_boundary(o, Scope::Default));
assert_eq!(
foreign.count() as u32,
self.foreign_boundaries,
"scope boundaries"
);
for scope in [Scope::Default, Scope::ListItem, Scope::Button, Scope::Table] {
for tag in [
Tag::Body,
Tag::Html,
Tag::Div,
Tag::P,
Tag::Li,
Tag::Td,
Tag::H1,
] {
if self.open_count(tag) > 0 {
assert_eq!(
self.in_scope(tag, scope),
self.in_scope_walk(tag, scope),
"{tag:?} in {scope:?} scope"
);
}
}
}
if all {
let marked = self.on_stack.iter().filter(|&&on| on).count();
assert_eq!(marked, self.open.len(), "a node is marked open but isn't");
}
let mut since_marker = std::collections::HashSet::new();
for &e in &self.active {
if e == MARKER {
since_marker.clear();
continue;
}
assert!(
self.element_at(e).is_some_and(|o| o.ns == Ns::Html),
"{e} in the list"
);
assert!(since_marker.insert(e), "node {e} in the list twice");
}
}
fn open_contains(&self, id: NodeId) -> bool {
self.on_stack.get(id as usize).copied().unwrap_or(false)
}
fn same_element(&self, a: NodeId, b: NodeId) -> bool {
let (Some(x), Some(y)) = (self.doc.element(a), self.doc.element(b)) else {
return false;
};
if x.ns != y.ns
|| x.tag != y.tag
|| !(matches!((x.name, y.name), (Name::Tag, Name::Tag))
|| self.doc.element_name(x) == self.doc.element_name(y))
|| x.attrs.end - x.attrs.start != y.attrs.end - y.attrs.start
{
return false;
}
let ys = &self.doc.attrs[y.attrs.start as usize..y.attrs.end as usize];
self.doc.attrs[x.attrs.start as usize..x.attrs.end as usize]
.iter()
.all(|a| {
ys.iter().any(|b| {
a.ns == b.ns
&& self.doc.str(a.name) == self.doc.str(b.name)
&& self.doc.str(a.value) == self.doc.str(b.value)
})
})
}
#[inline]
fn signature(&mut self, id: NodeId) -> u64 {
match self.sigs.get(id as usize) {
Some(&s) if s != 0 => s,
_ => self.work_out_signature(id),
}
}
#[inline(never)]
fn work_out_signature(&mut self, id: NodeId) -> u64 {
fn mix(h: u64, bytes: &[u8]) -> u64 {
bytes
.iter()
.fold(h, |h, &b| (h ^ b as u64).wrapping_mul(0x100000001b3))
}
const SEED: u64 = 0xcbf29ce484222325;
let e = self.doc.element(id).expect("an element");
let mut h = mix(SEED, &[e.ns as u8, e.tag as u8]);
if !matches!(e.name, Name::Tag) {
h = mix(h, self.doc.element_name(e).as_bytes());
}
let mut attrs = 0u64;
for a in &self.doc.attrs[e.attrs.start as usize..e.attrs.end as usize] {
let one = mix(SEED, self.doc.str(a.name).as_bytes());
attrs = attrs.wrapping_add(mix(mix(one, &[0]), self.doc.str(a.value).as_bytes()));
}
let h = (h ^ attrs).wrapping_mul(0x100000001b3) | 1;
self.set_signature(id, h);
h
}
fn set_signature(&mut self, id: NodeId, sig: u64) {
let i = id as usize;
if i >= self.sigs.len() {
self.sigs.resize(i * 2 + 1024, 0);
}
self.sigs[i] = sig;
}
fn push_active(&mut self, id: NodeId) {
debug_assert!(
self.element_at(id).is_some_and(|o| o.ns == Ns::Html
&& matches!(
o.tag,
Tag::A
| Tag::B
| Tag::Big
| Tag::Code
| Tag::Em
| Tag::Font
| Tag::I
| Tag::Nobr
| Tag::S
| Tag::Small
| Tag::Strike
| Tag::Strong
| Tag::Tt
| Tag::U
)),
"node {id} isn't a formatting element"
);
let sig = self.signature(id);
let (mut same, mut earliest) = (0, 0);
for i in (0..self.active.len()).rev() {
let e = self.active[i];
if e == MARKER {
break;
}
debug_assert!(
e != id,
"node {id} is in the list of formatting elements twice"
);
if self.signature(e) == sig && self.same_element(e, id) {
same += 1;
earliest = i;
}
}
if same >= 3 {
self.active.remove(earliest);
}
self.active.push(id);
}
fn clear_active_to_marker(&mut self) {
while let Some(e) = self.active.pop() {
if e == MARKER {
break;
}
}
}
fn reconstruct(&mut self) {
let Some(&last) = self.active.last() else {
return;
};
if last == MARKER || self.open_contains(last) {
return;
}
let mut i = self.active.len() - 1;
while i > 0 {
let e = self.active[i - 1];
if e == MARKER || self.open_contains(e) {
break;
}
i -= 1;
}
for j in i..self.active.len() {
debug_assert!(self.active[j] != MARKER, "a marker reopened");
let new = self.clone_element(self.active[j]);
let place = self.place(None);
self.insert_at(place, new);
let e = self.doc.element(new).unwrap();
let (ns, tag) = (e.ns, e.tag);
self.push_open(Open { id: new, ns, tag });
self.active[j] = new;
}
}
fn clone_element(&mut self, id: NodeId) -> NodeId {
let e = *self.doc.element(id).expect("an element");
let new = self.doc.add(Data::Element(Element {
contents: NONE,
..e
}));
if let Some(&sig) = self.sigs.get(id as usize)
&& sig != 0
{
self.set_signature(new, sig);
}
new
}
fn create(&mut self, s: &Start<'_>, ns: Ns) -> NodeId {
let name = match ns {
Ns::Svg => match svg_tag_name(s.name) {
Some(fixed) => Name::Svg(fixed),
None if s.tag != Tag::Other => Name::Tag,
None => Name::Span(self.doc.intern(s.name)),
},
_ if s.tag != Tag::Other => Name::Tag,
_ => Name::Span(self.doc.intern(s.name)),
};
let first = self.doc.attrs.len() as u32;
let mut html_integration = false;
for (n, v) in s.attrs() {
let (attr_ns, local) = if ns == Ns::Html {
(AttrNs::None, n)
} else if let Some((attr_ns, _)) = foreign_attr(n) {
(attr_ns, n)
} else {
(AttrNs::None, n)
};
if ns == Ns::MathMl
&& s.tag == Tag::AnnotationXml
&& n == "encoding"
&& (v.eq_ignore_ascii_case("text/html")
|| v.eq_ignore_ascii_case("application/xhtml+xml"))
{
html_integration = true;
}
let name = self.doc.intern(local);
let value = self.doc.intern(v);
self.doc.attrs.push(Attr {
ns: attr_ns,
name,
value,
});
}
let contents = if ns == Ns::Html && s.tag == Tag::Template {
self.doc.add(Data::Fragment)
} else {
NONE
};
let id = self.doc.add(Data::Element(Element {
ns,
tag: s.tag,
name,
attrs: Span {
start: first,
end: self.doc.attrs.len() as u32,
},
contents,
html_integration,
}));
if self.spans
&& let Some(tag) = s.attrs
{
self.element_written(id, tag, first as usize);
}
id
}
fn element_at(&self, id: NodeId) -> Option<Open> {
self.doc.element(id).map(|e| Open {
id,
ns: e.ns,
tag: e.tag,
})
}
fn place(&self, target: Option<NodeId>) -> (NodeId, NodeId) {
use Tag::*;
let mut target = target.unwrap_or_else(|| self.current().id);
let mut before = NONE;
let t = self.element_at(target);
if self.foster
&& t.is_some_and(|t| {
t.ns == Ns::Html && matches!(t.tag, Table | Tbody | Tfoot | Thead | Tr)
})
{
let last = self
.open
.iter()
.rposition(|o| o.is(Template) || o.is(Table));
match last {
None => return (self.open[0].id, NONE),
Some(i) if self.open[i].is(Template) => target = self.open[i].id,
Some(i) => {
let table = self.open[i].id;
match self.doc.parent(table) {
Some(parent) => {
target = parent;
before = table;
}
None => target = self.open[i - 1].id,
}
}
}
}
if let Some(e) = self.doc.element(target)
&& e.ns == Ns::Html
&& e.tag == Template
{
return (e.contents, NONE);
}
if before == NONE
&& self.max_depth.is_some_and(|max| self.open.len() > max)
&& let Some(up) = self.doc.parent(target)
{
return (up, NONE);
}
(target, before)
}
fn insert_at(&mut self, (parent, before): (NodeId, NodeId), node: NodeId) {
if parent == 0
&& matches!(self.doc.nodes[0].data, Data::Document)
&& self.doc.children(0).any(|c| self.doc.element(c).is_some())
{
return;
}
self.doc.insert(parent, node, before);
}
fn insert_element(&mut self, s: &Start<'_>, ns: Ns) -> NodeId {
let id = self.create(s, ns);
let place = self.place(None);
self.insert_at(place, id);
self.push_open(Open { id, ns, tag: s.tag });
if ns == Ns::Html {
match s.tag {
Tag::Option => self.option_inserted(id, s),
Tag::Selectedcontent => self.selectedcontent_inserted(id),
_ => {}
}
}
id
}
fn stop(&mut self) {
self.done = true;
self.truncate_open(0);
}
#[inline(never)]
fn shadow_template(&mut self, s: &Start<'_>) {
if !self.declarative_shadow_root(s) {
self.insert_html(s);
}
}
fn declarative_shadow_root(&mut self, s: &Start<'_>) -> bool {
let Some(init) = crate::shadow::declared(s.attrs()) else {
return false;
};
let Some(host) = self.adjusted_current() else {
return false;
};
if self.open.first().is_some_and(|o| o.id == host.id)
|| self.context.is_some_and(|c| c.id == host.id)
|| self.doc.shadow_root(host.id).is_some()
{
return false;
}
let Some(e) = self.doc.element(host.id) else {
return false;
};
if !crate::shadow::valid_host(e.ns, e.tag, self.doc.element_name(e)) {
return false;
}
let template = self.create(s, Ns::Html);
let root = self.doc.add_shadow_root(host.id, init);
if let Data::Element(e) = &mut self.doc.nodes[template as usize].data {
e.contents = root;
}
self.shadow_templates.push(template);
self.push_open(Open {
id: template,
ns: Ns::Html,
tag: Tag::Template,
});
true
}
fn release_shadow_roots(&mut self) {
for t in std::mem::take(&mut self.shadow_templates) {
if let Data::Element(e) = &mut self.doc.nodes[t as usize].data {
e.contents = NONE;
}
}
}
fn html_element(&self, id: NodeId, tag: Tag) -> bool {
self.doc
.element(id)
.is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
}
fn has_attr(&self, id: NodeId, name: &str) -> bool {
self.doc
.attrs(id)
.any(|(ns, n, _)| ns == AttrNs::None && n == name)
}
fn nearest_select(&self, id: NodeId) -> NodeId {
if self.open_count(Tag::Select) == 0 {
return NONE;
}
let mut optgroup = false;
let mut at = self.doc.parent(id);
while let Some(a) = at {
if let Some(e) = self.doc.element(a)
&& e.ns == Ns::Html
{
match e.tag {
Tag::Datalist | Tag::Hr | Tag::Option => return NONE,
Tag::Optgroup if optgroup => return NONE,
Tag::Optgroup => optgroup = true,
Tag::Select => return a,
_ => {}
}
}
at = self.doc.parent(a);
}
NONE
}
fn option_inserted(&mut self, option: NodeId, s: &Start<'_>) {
let select = self.nearest_select(option);
if select == NONE {
return;
}
self.option_select.insert(option, select);
if self.has_attr(select, "multiple") {
return;
}
let size_one = self
.doc
.attrs(select)
.find(|(ns, n, _)| *ns == AttrNs::None && *n == "size")
.and_then(|(_, _, v)| v.trim().parse::<u32>().ok())
.is_none_or(|n| n <= 1);
let disabled = s.attr("disabled").is_some()
|| self.doc.parent(option).is_some_and(|p| {
self.html_element(p, Tag::Optgroup) && self.has_attr(p, "disabled")
});
if s.attr("selected").is_some()
|| (!self.selected.contains_key(&select) && size_one && !disabled)
{
self.selected.insert(select, option);
}
}
fn option_popped(&mut self, option: NodeId) {
let Some(&select) = self.option_select.get(&option) else {
return;
};
if self.selected.get(&select) != Some(&option) || self.has_attr(select, "multiple") {
return;
}
for target in self.selectedcontents(select) {
self.clone_children_into(option, target);
}
}
fn selectedcontent_inserted(&mut self, id: NodeId) {
let mut select = NONE;
let mut at = self.doc.parent(id);
while let Some(a) = at {
if self.html_element(a, Tag::Select) {
if select != NONE {
return;
}
select = a;
} else if self.html_element(a, Tag::Option)
|| self.html_element(a, Tag::Selectedcontent)
{
return;
}
at = self.doc.parent(a);
}
if select == NONE || self.has_attr(select, "multiple") {
return;
}
if let Some(&option) = self.selected.get(&select) {
self.clone_children_into(option, id);
}
}
fn selectedcontents(&self, select: NodeId) -> Vec<NodeId> {
let mut found = Vec::new();
let mut stack: Vec<NodeId> = self.doc.children(select).collect();
stack.reverse();
while let Some(n) = stack.pop() {
if let Some(e) = self.doc.element(n)
&& e.ns == Ns::Html
{
match e.tag {
Tag::Selectedcontent => {
found.push(n);
continue;
}
Tag::Option | Tag::Select => continue,
_ => {}
}
}
let at = stack.len();
stack.extend(self.doc.children(n));
stack[at..].reverse();
}
found
}
fn clone_children_into(&mut self, from: NodeId, to: NodeId) {
while let Some(child) = self.doc.first_child(to) {
self.doc.detach(child);
}
let children: Vec<NodeId> = self.doc.children(from).collect();
for child in children {
let copy = self.deep_clone(child);
self.doc.insert(to, copy, NONE);
}
}
fn deep_clone(&mut self, id: NodeId) -> NodeId {
let mut root = NONE;
let mut stack = vec![(id, NONE)];
while let Some((from, parent)) = stack.pop() {
let mut data = self.doc.nodes[from as usize].data;
if let Data::Element(e) = &mut data {
e.contents = NONE;
}
let copy = self.doc.add(data);
if parent == NONE {
root = copy;
} else {
self.doc.insert(parent, copy, NONE);
}
let at = stack.len();
stack.extend(self.doc.children(from).map(|c| (c, copy)));
stack[at..].reverse();
}
root
}
fn insert_html(&mut self, s: &Start<'_>) -> NodeId {
self.insert_element(s, Ns::Html)
}
fn insert_void(&mut self, s: &Start<'_>) {
self.acknowledged = true;
self.insert_html(s);
self.pop();
}
fn insert_text(&mut self, text: &str) {
if text.is_empty() {
return;
}
let (parent, before) = self.place(None);
if parent == 0 && matches!(self.doc.nodes[0].data, Data::Document) {
return;
}
let prev = if before == NONE {
self.doc.nodes[parent as usize].last_child
} else {
self.doc.nodes[before as usize].prev
};
if prev != NONE && matches!(self.doc.nodes[prev as usize].data, Data::Text(_)) {
self.doc.append_text(prev, text);
if self.spans {
self.text_written(prev, text, true);
}
} else {
let span = self.doc.intern(text);
let id = self.doc.add(Data::Text(span));
self.doc.insert(parent, id, before);
if self.spans {
self.text_written(id, text, false);
}
}
}
fn insert_comment(&mut self, text: &str, at: Option<(NodeId, NodeId)>) {
let place = at.unwrap_or_else(|| self.place(None));
let span = self.doc.intern(text);
let id = self.doc.add(Data::Comment(span));
self.doc.insert(place.0, id, place.1);
if self.spans {
self.written(id);
}
}
fn insert_pi(&mut self, target: &str, data: &str, at: Option<(NodeId, NodeId)>) {
let place = at.unwrap_or_else(|| self.place(None));
let target = self.doc.intern(target);
let data = self.doc.intern(data);
let id = self.doc.add(Data::ProcessingInstruction { target, data });
self.doc.insert(place.0, id, place.1);
if self.spans {
self.written(id);
}
}
#[cold]
fn written(&mut self, id: NodeId) {
if let Some(p) = self.doc.positions.as_deref_mut() {
Positions::set(&mut p.nodes, id as usize, self.at);
}
}
#[cold]
fn element_written(&mut self, id: NodeId, tag: &tokenizer::Tag<'_>, first: usize) {
self.written(id);
let Some(p) = self.doc.positions.as_deref_mut() else {
return;
};
for i in 0..tag.attrs().len() {
if let Some(at) = tag.attr_span(i) {
Positions::set(&mut p.attrs, first + i, [at.start as u32, at.end as u32]);
}
}
}
#[cold]
fn closed_by_end_tag(&mut self, id: NodeId) {
if self.doc.lower_name(id) == Some(&self.closing_name) {
self.ended(id);
}
}
#[cold]
fn text_written(&mut self, id: NodeId, text: &str, more: bool) {
let at = match self.doc.source_offset(text) {
Some(o) => [o as u32, (o + text.len()) as u32],
None => self.at,
};
let Some(p) = self.doc.positions.as_deref_mut() else {
return;
};
let at = match p.nodes.get(id as usize) {
Some(&[start, end]) if more && start != u32::MAX => [start.min(at[0]), end.max(at[1])],
_ if more => return,
_ => at,
};
Positions::set(&mut p.nodes, id as usize, at);
}
#[cold]
fn ended(&mut self, id: NodeId) {
if self.spans
&& let Some(p) = self.doc.positions.as_deref_mut()
&& p.ends.get(id as usize).is_none_or(|&a| a[0] == u32::MAX)
{
Positions::set(&mut p.ends, id as usize, self.at);
}
}
fn rawtext(&mut self, s: &Start<'_>, mode: TextMode) {
self.insert_html(s);
self.switch = Some(mode);
self.original = self.mode;
self.mode = Mode::Text;
}
fn merge_attrs(&mut self, id: NodeId, s: &Start<'_>) {
let Some(e) = self.doc.element(id) else {
return;
};
let old = e.attrs;
let merged = self.merged.entry(id).or_insert_with(|| Merged {
names: self.doc.attrs(id).map(|(_, n, _)| n.to_owned()).collect(),
room: old.end,
});
let mut adds = Vec::new();
for (i, (n, v)) in s.attrs().enumerate() {
if !merged.names.contains(n) {
merged.names.insert(n.to_owned());
adds.push((i, n, v));
}
}
if adds.is_empty() {
return;
}
let len = self.doc.attrs.len() as u32;
let (have, more) = (old.end - old.start, adds.len() as u32);
let start = if old.end == len || old.end + more <= merged.room {
old.start
} else {
self.doc
.attrs
.extend_from_within(old.start as usize..old.end as usize);
let empty = Span { start: 0, end: 0 };
let spare = Attr {
ns: AttrNs::None,
name: empty,
value: empty,
};
let room = have + more;
self.doc.attrs.extend((0..room).map(|_| spare));
merged.room = len + have + room;
if self.spans
&& let Some(p) = self.doc.positions.as_deref_mut()
{
for k in 0..have as usize {
let at = p.attrs.get(old.start as usize + k).copied();
if let Some(at) = at {
Positions::set(&mut p.attrs, len as usize + k, at);
}
}
}
len
};
let mut at = start + have;
for (i, n, v) in adds {
let written = s.attrs.and_then(|t| t.attr_span(i));
let attr = Attr {
ns: AttrNs::None,
name: self.doc.intern(n),
value: self.doc.intern(v),
};
if at as usize == self.doc.attrs.len() {
self.doc.attrs.push(attr);
} else {
self.doc.attrs[at as usize] = attr;
}
if self.spans
&& let Some(p) = self.doc.positions.as_deref_mut()
&& let Some(w) = written
{
Positions::set(&mut p.attrs, at as usize, [w.start as u32, w.end as u32]);
}
at += 1;
}
if let Data::Element(e) = &mut self.doc.nodes[id as usize].data {
e.attrs = Span { start, end: at };
}
}
fn process(&mut self, t: Tok<'_>) {
if self.done {
return;
}
if self.html_rules(&t) {
self.html(t);
} else {
self.foreign(t);
}
}
fn html_rules(&self, t: &Tok<'_>) -> bool {
let Some(a) = self.adjusted_current() else {
return true;
};
if a.ns == Ns::Html {
return true;
}
let html_integration = match a.ns {
Ns::Svg => matches!(a.tag, Tag::ForeignObject | Tag::Desc | Tag::Title),
Ns::MathMl => self.doc.element(a.id).is_some_and(|e| e.html_integration),
Ns::Html | Ns::Xml => false,
};
match t {
Tok::Start(s) => {
(mathml_text_integration(a) && !matches!(s.tag, Tag::Mglyph | Tag::Malignmark))
|| (a.ns == Ns::MathMl && a.tag == Tag::AnnotationXml && s.tag == Tag::Svg)
|| html_integration
}
Tok::Text(_) => mathml_text_integration(a) || html_integration,
Tok::Eof => true,
_ => false,
}
}
fn html(&mut self, t: Tok<'_>) {
match self.mode {
Mode::Initial => self.initial(t),
Mode::BeforeHtml => self.before_html(t),
Mode::BeforeHead => self.before_head(t),
Mode::InHead => self.in_head(t),
Mode::InHeadNoscript => self.in_head_noscript(t),
Mode::AfterHead => self.after_head(t),
Mode::InBody => self.in_body(t),
Mode::Text => self.text(t),
Mode::InTable => self.in_table(t),
Mode::InTableText => self.in_table_text(t),
Mode::InCaption => self.in_caption(t),
Mode::InColumnGroup => self.in_column_group(t),
Mode::InTableBody => self.in_table_body(t),
Mode::InRow => self.in_row(t),
Mode::InCell => self.in_cell(t),
Mode::InTemplate => self.in_template(t),
Mode::AfterBody => self.after_body(t),
Mode::InFrameset => self.in_frameset(t),
Mode::AfterFrameset => self.after_frameset(t),
Mode::AfterAfterBody => self.after_after_body(t),
Mode::AfterAfterFrameset => self.after_after_frameset(t),
}
}
fn reprocess(&mut self, mode: Mode, t: Tok<'_>) {
self.mode = mode;
self.process(t);
}
fn initial(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => {
let (_, rest) = split_space(s);
if !rest.is_empty() {
self.err_in("expected-doctype-but-got-chars", rest, 0);
self.doc.quirks = Quirks::Quirks;
self.reprocess(Mode::BeforeHtml, Tok::Text(rest));
}
}
Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
Tok::Doctype(d) => {
if d.name != Some("html")
|| d.public_id.is_some()
|| d.system_id.is_some_and(|s| s != "about:legacy-compat")
{
self.err("unknown-doctype");
}
let name = self.doc.intern(d.name.unwrap_or(""));
let public_id = self.doc.intern(d.public_id.unwrap_or(""));
let system_id = self.doc.intern(d.system_id.unwrap_or(""));
let id = self.doc.add(Data::Doctype {
name,
public_id,
system_id,
});
self.doc.insert(0, id, NONE);
if self.spans {
self.written(id);
}
self.doc.quirks = doctype_quirks(d);
self.mode = Mode::BeforeHtml;
}
_ => {
self.err(match t {
Tok::Start(_) => "expected-doctype-but-got-start-tag",
Tok::End(_) => "expected-doctype-but-got-end-tag",
_ => "expected-doctype-but-got-eof",
});
self.doc.quirks = Quirks::Quirks;
self.reprocess(Mode::BeforeHtml, t);
}
}
}
fn before_html(&mut self, t: Tok<'_>) {
match t {
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
Tok::Text(s) => {
let (_, rest) = split_space(s);
if !rest.is_empty() {
self.before_html_else(Tok::Text(rest));
}
}
Tok::Start(s) if s.tag == Tag::Html => {
let id = self.create(&s, Ns::Html);
self.insert_at((0, NONE), id);
self.push_open(Open {
id,
ns: Ns::Html,
tag: Tag::Html,
});
self.mode = Mode::BeforeHead;
}
Tok::End(e) if !matches!(e.tag, Tag::Head | Tag::Body | Tag::Html | Tag::Br) => {
self.err("unexpected-end-tag-before-html");
}
_ => self.before_html_else(t),
}
}
fn before_html_else(&mut self, t: Tok<'_>) {
let id = self.create(&Start::bare(Tag::Html), Ns::Html);
self.insert_at((0, NONE), id);
self.push_open(Open {
id,
ns: Ns::Html,
tag: Tag::Html,
});
self.reprocess(Mode::BeforeHead, t);
}
fn before_head(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => {
let (_, rest) = split_space(s);
if !rest.is_empty() {
self.before_head_else(Tok::Text(rest));
}
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
Tok::Start(s) if s.tag == Tag::Head => {
self.head = self.insert_html(&s);
self.mode = Mode::InHead;
}
Tok::End(e) if !matches!(e.tag, Tag::Head | Tag::Body | Tag::Html | Tag::Br) => {
self.err("end-tag-after-implied-root");
}
_ => self.before_head_else(t),
}
}
fn before_head_else(&mut self, t: Tok<'_>) {
self.head = self.insert_html(&Start::bare(Tag::Head));
self.reprocess(Mode::InHead, t);
}
fn in_head(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s) => {
let (space, rest) = split_space(s);
self.insert_text(space);
if !rest.is_empty() {
self.in_head_else(Tok::Text(rest));
}
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) => match s.tag {
Html => self.in_body(t),
Base | Basefont | Bgsound | Link | Meta => self.insert_void(&s),
Title => self.rawtext(&s, TextMode::Rcdata),
Noscript if self.scripting => self.rawtext(&s, TextMode::Rawtext),
Noframes | Style => self.rawtext(&s, TextMode::Rawtext),
Noscript => {
self.insert_html(&s);
self.mode = Mode::InHeadNoscript;
}
Script => self.rawtext(&s, TextMode::ScriptData),
Template => {
self.active.push(MARKER);
self.frameset_ok = false;
self.mode = Mode::InTemplate;
self.template_modes.push(Mode::InTemplate);
if self.shadow_roots {
self.shadow_template(&s);
} else {
self.insert_html(&s);
}
}
Head => self.err("two-heads-are-not-better-than-one"),
_ => self.in_head_else(t),
},
Tok::End(e) => match e.tag {
Head => {
self.pop();
self.mode = Mode::AfterHead;
}
Body | Html | Br => self.in_head_else(t),
Template => {
if !self.template_open() {
self.err("unexpected-end-tag");
return;
}
self.generate_implied_thoroughly();
if !self.current().is(Template) {
self.err("end-tag-too-early");
}
self.pop_until(Template);
self.clear_active_to_marker();
self.template_modes.pop();
self.reset_mode();
}
_ => self.err("unexpected-end-tag"),
},
Tok::Eof => self.in_head_else(t),
}
}
fn in_head_else(&mut self, t: Tok<'_>) {
self.pop();
self.reprocess(Mode::AfterHead, t);
}
fn in_head_noscript(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) if s.tag == Html => self.in_body(t),
Tok::End(e) if e.tag == Noscript => {
self.pop();
self.mode = Mode::InHead;
}
Tok::Text(s) => {
let (space, rest) = split_space(s);
if !space.is_empty() {
self.in_head(Tok::Text(space));
}
if !rest.is_empty() {
self.in_head_noscript_else(Tok::Text(rest));
}
}
Tok::Comment(_) | Tok::Pi(..) => self.in_head(t),
Tok::Start(s)
if matches!(s.tag, Basefont | Bgsound | Link | Meta | Noframes | Style) =>
{
self.in_head(t)
}
Tok::End(e) if e.tag == Br => self.in_head_noscript_else(t),
Tok::Start(s) if matches!(s.tag, Head | Noscript) => self.err("unexpected-start-tag"),
Tok::End(_) => self.err("unexpected-end-tag"),
_ => self.in_head_noscript_else(t),
}
}
fn in_head_noscript_else(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => self.err_in("char-in-head-noscript", s, 0),
Tok::Eof => self.err("eof-in-head-noscript"),
_ => self.err("unexpected-inhead-noscript-tag"),
}
self.pop();
self.reprocess(Mode::InHead, t);
}
fn after_head(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s) => {
let (space, rest) = split_space(s);
self.insert_text(space);
if !rest.is_empty() {
self.after_head_else(Tok::Text(rest));
}
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) => match s.tag {
Html => self.in_body(t),
Body => {
self.insert_html(&s);
self.frameset_ok = false;
self.mode = Mode::InBody;
}
Frameset => {
self.insert_html(&s);
self.mode = Mode::InFrameset;
}
Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
| Title => {
self.err("unexpected-start-tag-out-of-my-head");
let head = self.head;
self.push_open(Open {
id: head,
ns: Ns::Html,
tag: Head,
});
self.in_head(t);
self.remove_open(head);
}
Head => self.err("unexpected-start-tag"),
_ => self.after_head_else(t),
},
Tok::End(e) => match e.tag {
Template => self.in_head(t),
Body | Html | Br => self.after_head_else(t),
_ => self.err("unexpected-end-tag"),
},
Tok::Eof => self.after_head_else(t),
}
}
fn after_head_else(&mut self, t: Tok<'_>) {
self.insert_html(&Start::bare(Tag::Body));
self.frameset_ok = true;
self.reprocess(Mode::InBody, t);
}
fn body_text(&mut self, s: &str) {
if memchr::memchr(0, s.as_bytes()).is_none() {
self.reconstruct();
self.insert_text(s);
if self.frameset_ok && !all_space(s) {
self.frameset_ok = false;
}
return;
}
if self.errors {
for i in memchr::memchr_iter(0, s.as_bytes()) {
self.err_in("invalid-codepoint-in-body", s, i);
}
}
for piece in s.split('\0').filter(|p| !p.is_empty()) {
self.body_text(piece);
}
}
fn in_body(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => self.body_text(s),
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) => self.in_body_start(s),
Tok::End(e) => self.in_body_end(e),
Tok::Eof => {
if !self.template_modes.is_empty() {
self.in_template(t);
} else {
self.check_open_at_end("expected-closing-tag-but-got-eof");
self.stop();
}
}
}
}
fn in_body_start(&mut self, s: Start<'_>) {
use Tag::*;
match s.tag {
Html => {
self.err("non-html-root");
if !self.template_open() {
let root = self.open[0].id;
self.merge_attrs(root, &s);
}
}
Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
| Title => self.in_head(Tok::Start(s)),
Body => {
self.err("unexpected-start-tag");
if self.open.len() == 1 || !self.open[1].is(Body) || self.template_open() {
return;
}
self.frameset_ok = false;
let body = self.open[1].id;
self.merge_attrs(body, &s);
}
Frameset => {
self.err("unexpected-start-tag");
if self.open.len() == 1 || !self.open[1].is(Body) || !self.frameset_ok {
return;
}
let body = self.open[1].id;
self.doc.detach(body);
self.truncate_open(1);
self.insert_html(&s);
self.mode = Mode::InFrameset;
}
Address | Article | Aside | Blockquote | Center | Details | Dialog | Dir | Div | Dl
| Fieldset | Figcaption | Figure | Footer | Header | Hgroup | Main | Menu | Nav
| Ol | P | Search | Section | Summary | Ul => {
self.close_p_in_button_scope();
self.insert_html(&s);
}
H1 | H2 | H3 | H4 | H5 | H6 => {
self.close_p_in_button_scope();
let c = self.current();
if c.ns == Ns::Html && heading(c.tag) {
self.err("unexpected-start-tag");
self.pop();
}
self.insert_html(&s);
}
Pre | Listing => {
self.close_p_in_button_scope();
self.insert_html(&s);
self.skip_newline = true;
self.frameset_ok = false;
}
Form => {
let template = self.in_template_contents();
if self.form != NONE && !template {
self.err("unexpected-start-tag");
return;
}
self.close_p_in_button_scope();
let id = self.insert_html(&s);
if !template {
self.form = id;
}
}
Li | Dd | Dt => {
self.frameset_ok = false;
for i in (0..self.open.len()).rev() {
let node = self.open[i];
let closes = match s.tag {
Li => node.is(Li),
_ => node.is(Dd) || node.is(Dt),
};
if closes {
self.generate_implied(Some(node.tag));
if !self.current().is(node.tag) {
self.err("end-tag-too-early");
}
self.pop_until(node.tag);
break;
}
if special(node) && !node.is(Address) && !node.is(Div) && !node.is(P) {
break;
}
}
self.close_p_in_button_scope();
self.insert_html(&s);
}
Plaintext => {
self.close_p_in_button_scope();
self.insert_html(&s);
self.switch = Some(TextMode::Plaintext);
}
Button => {
if self.in_scope(Button, Scope::Default) {
self.err("unexpected-start-tag-implies-end-tag");
self.generate_implied(None);
self.pop_until(Button);
}
self.reconstruct();
self.insert_html(&s);
self.frameset_ok = false;
}
A => {
let start = self
.active
.iter()
.rposition(|&e| e == MARKER)
.map_or(0, |i| i + 1);
let existing = self.active[start..].iter().rev().copied().find(|&e| {
self.doc
.element(e)
.is_some_and(|el| el.ns == Ns::Html && el.tag == A)
});
if let Some(a) = existing {
self.err("unexpected-start-tag-implies-end-tag");
if self.adoption_agency(A, "a") {
self.any_other_end(End { tag: A, name: "a" });
}
self.active.retain(|&e| e != a);
self.remove_open(a);
}
self.reconstruct();
let id = self.insert_html(&s);
self.push_active(id);
}
B | Big | Code | Em | Font | I | S | Small | Strike | Strong | Tt | U => {
self.reconstruct();
let id = self.insert_html(&s);
self.push_active(id);
}
Nobr => {
self.reconstruct();
if self.in_scope(Nobr, Scope::Default) {
self.err("unexpected-start-tag-implies-end-tag");
if self.adoption_agency(Nobr, "nobr") {
self.any_other_end(End {
tag: Nobr,
name: "nobr",
});
}
self.reconstruct();
}
let id = self.insert_html(&s);
self.push_active(id);
}
Applet | Marquee | Object => {
self.reconstruct();
self.insert_html(&s);
self.active.push(MARKER);
self.frameset_ok = false;
}
Table => {
if self.doc.quirks != Quirks::Quirks {
self.close_p_in_button_scope();
}
self.insert_html(&s);
self.frameset_ok = false;
self.mode = Mode::InTable;
}
Area | Br | Embed | Img | Keygen | Wbr => {
self.reconstruct();
self.insert_void(&s);
self.frameset_ok = false;
}
Input => {
if self.context.is_some_and(|c| c.is(Select)) {
self.err("unexpected-input-in-select");
return;
}
if self.in_scope(Select, Scope::Default) {
self.err("unexpected-input-in-select");
self.pop_until(Select);
}
self.reconstruct();
self.insert_void(&s);
if !s
.attr("type")
.is_some_and(|t| t.eq_ignore_ascii_case("hidden"))
{
self.frameset_ok = false;
}
}
Param | Source | Track => self.insert_void(&s),
Hr => {
self.close_p_in_button_scope();
if self.in_scope(Select, Scope::Default) {
self.generate_implied(None);
}
self.insert_void(&s);
self.frameset_ok = false;
}
Image => {
self.err("unexpected-start-tag-treated-as");
self.process(Tok::Start(Start {
tag: Img,
name: "img",
..s
}))
}
Textarea => {
self.insert_html(&s);
self.skip_newline = true;
self.switch = Some(TextMode::Rcdata);
self.original = self.mode;
self.frameset_ok = false;
self.mode = Mode::Text;
}
Xmp => {
self.close_p_in_button_scope();
self.reconstruct();
self.frameset_ok = false;
self.rawtext(&s, TextMode::Rawtext);
}
Iframe => {
self.frameset_ok = false;
self.rawtext(&s, TextMode::Rawtext);
}
Noembed => self.rawtext(&s, TextMode::Rawtext),
Noscript if self.scripting => self.rawtext(&s, TextMode::Rawtext),
Select => {
if self.context.is_some_and(|c| c.is(Select)) {
self.err("unexpected-select-in-select");
return;
}
if self.in_scope(Select, Scope::Default) {
self.err("unexpected-select-in-select");
self.pop_until(Select);
return;
}
self.reconstruct();
self.insert_html(&s);
self.frameset_ok = false;
}
Option => {
if self.in_scope(Select, Scope::Default) {
self.generate_implied(Some(Optgroup));
} else if self.current().is(Option) {
self.pop();
}
self.reconstruct();
self.insert_html(&s);
}
Optgroup => {
if self.in_scope(Select, Scope::Default) {
self.generate_implied(None);
} else if self.current().is(Option) {
self.pop();
}
self.reconstruct();
self.insert_html(&s);
}
Rb | Rtc => {
if self.in_scope(Ruby, Scope::Default) {
self.generate_implied(None);
if !self.current().is(Ruby) {
self.err("unexpected-start-tag");
}
}
self.insert_html(&s);
}
Rp | Rt => {
if self.in_scope(Ruby, Scope::Default) {
self.generate_implied(Some(Rtc));
if !self.current().is(Ruby) && !self.current().is(Rtc) {
self.err("unexpected-start-tag");
}
}
self.insert_html(&s);
}
Math | Svg => {
self.reconstruct();
let ns = if s.tag == Math { Ns::MathMl } else { Ns::Svg };
self.insert_element(&s, ns);
if s.self_closing {
self.acknowledged = true;
self.pop();
}
}
Caption | Col | Colgroup | Frame | Head | Tbody | Td | Tfoot | Th | Thead | Tr => {
self.err("unexpected-start-tag-ignored");
}
_ => {
self.reconstruct();
self.insert_html(&s);
}
}
}
fn in_body_end(&mut self, e: End<'_>) {
use Tag::*;
match e.tag {
Template => self.in_head(Tok::End(e)),
Body => {
if !self.in_scope(Body, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.check_open_at_end("expected-one-end-tag-but-got-another");
self.mode = Mode::AfterBody;
if let Some(body) = self.open.get(1).filter(|o| o.is(Body)) {
self.ended(body.id);
}
}
}
Html => {
if !self.in_scope(Body, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.check_open_at_end("expected-one-end-tag-but-got-another");
self.reprocess(Mode::AfterBody, Tok::End(e));
}
}
Address | Article | Aside | Blockquote | Button | Center | Details | Dialog | Dir
| Div | Dl | Fieldset | Figcaption | Figure | Footer | Header | Hgroup | Listing
| Main | Menu | Nav | Ol | Pre | Search | Section | Select | Summary | Ul => {
if !self.in_scope(e.tag, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(None);
if !self.current().is(e.tag) {
self.err("end-tag-too-early");
}
self.pop_until(e.tag);
}
}
Form => {
if !self.in_template_contents() {
let node = self.form;
self.form = NONE;
if node == NONE || !self.node_in_scope(node) {
self.err("unexpected-end-tag");
return;
}
self.generate_implied(None);
if self.current().id != node {
self.err("end-tag-too-early-ignored");
}
self.remove_open(node);
} else if !self.in_scope(Form, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(None);
if !self.current().is(Form) {
self.err("end-tag-too-early-ignored");
}
self.pop_until(Form);
}
}
P => {
if !self.in_scope(P, Scope::Button) {
self.err("unexpected-end-tag");
self.insert_html(&Start::bare(P));
}
self.close_p();
}
Li => {
if !self.in_scope(Li, Scope::ListItem) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(Some(Li));
if !self.current().is(Li) {
self.err("end-tag-too-early");
}
self.pop_until(Li);
}
}
Dd | Dt => {
if !self.in_scope(e.tag, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(Some(e.tag));
if !self.current().is(e.tag) {
self.err("end-tag-too-early");
}
self.pop_until(e.tag);
}
}
H1 | H2 | H3 | H4 | H5 | H6 => {
if !self.in_scope_any(&HEADINGS, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(None);
if !self.current().is(e.tag) {
self.err("end-tag-too-early");
}
self.pop_until_where(heading);
}
}
A | B | Big | Code | Em | Font | I | Nobr | S | Small | Strike | Strong | Tt | U => {
if self.adoption_agency(e.tag, e.name) {
self.any_other_end(e);
}
}
Applet | Marquee | Object => {
if !self.in_scope(e.tag, Scope::Default) {
self.err("unexpected-end-tag");
} else {
self.generate_implied(None);
if !self.current().is(e.tag) {
self.err("end-tag-too-early");
}
self.pop_until(e.tag);
self.clear_active_to_marker();
}
}
Br => {
self.err("unexpected-end-tag-treated-as");
self.in_body_start(Start::bare(Br));
}
_ => self.any_other_end(e),
}
}
fn check_open_at_end(&mut self, code: &'static str) {
use Tag::*;
if !self.errors {
return;
}
let may_be_open: u32 = [
Dd, Dt, Li, Optgroup, Option, P, Rb, Rp, Rt, Rtc, Tbody, Td, Tfoot, Th, Thead, Tr,
Body, Html,
]
.iter()
.map(|&t| self.open_count(t))
.sum();
let unclosed = self.open.len() as u32 > may_be_open;
if unclosed {
self.err(code);
}
}
fn names_match(&self, o: Open, e: &End<'_>) -> bool {
if o.ns != Ns::Html {
return false;
}
if e.tag != Tag::Other || o.tag != Tag::Other {
return o.tag == e.tag;
}
self.doc
.element(o.id)
.is_some_and(|el| self.doc.element_name(el) == e.name)
}
fn any_other_end(&mut self, e: End<'_>) {
let open = match e.tag {
Tag::Other => self.open_named(true, e.name),
tag => self.open_count(tag),
};
if open == 0 {
self.err("unexpected-end-tag");
return;
}
for i in (0..self.open.len()).rev() {
let node = self.open[i];
if self.names_match(node, &e) {
self.generate_implied(Some(node.tag).filter(|&t| t != Tag::Other));
if self.open.len() != i + 1 {
self.err("unexpected-end-tag");
}
self.truncate_open(i);
return;
}
if special(node) {
self.err("unexpected-end-tag");
return;
}
}
}
fn adoption_agency(&mut self, subject: Tag, _name: &str) -> bool {
let c = self.current();
if c.is(subject) && !self.active.contains(&c.id) {
self.pop();
return false;
}
let errors = self.errors;
for _ in 0..8 {
let start = self
.active
.iter()
.rposition(|&e| e == MARKER)
.map_or(0, |i| i + 1);
let Some(fe_active) = (start..self.active.len()).rev().find(|&i| {
self.doc
.element(self.active[i])
.is_some_and(|el| el.ns == Ns::Html && el.tag == subject)
}) else {
return true;
};
let fe = self.active[fe_active];
let Some(fe_open) = self.open.iter().rposition(|o| o.id == fe) else {
self.err("adoption-agency-1.2");
self.active.remove(fe_active);
return false;
};
if !self.node_in_scope(fe) {
self.err("adoption-agency-4.4");
return false;
}
if errors && self.current().id != fe {
self.err("adoption-agency-1.3");
}
let Some(fb_open) = (fe_open + 1..self.open.len()).find(|&i| special(self.open[i]))
else {
self.truncate_open(fe_open);
self.active.remove(fe_active);
return false;
};
let furthest = self.open[fb_open].id;
let common = self.open[fe_open - 1].id;
let mut bookmark = fe_active;
let mut node_index = fb_open;
let mut last = furthest;
let mut inner = 0;
let mut bookmark_moved = false;
loop {
inner += 1;
node_index -= 1;
let node = self.open[node_index];
if node.id == fe {
break;
}
let mut in_active = self.active.iter().position(|&e| e == node.id);
if inner > 3
&& let Some(i) = in_active
{
self.active.remove(i);
if i < bookmark {
bookmark -= 1;
}
in_active = None;
}
let Some(ai) = in_active else {
self.remove_open_at(node_index);
continue;
};
let new = self.clone_element(node.id);
self.active[ai] = new;
self.open[node_index] = Open { id: new, ..node };
debug_assert!(self.open_contains(node.id) && !self.open_contains(new));
self.mark(node.id, false);
self.mark(new, true);
if !bookmark_moved {
bookmark = ai + 1;
bookmark_moved = true;
}
self.doc.detach(last);
self.doc.insert(new, last, NONE);
last = new;
}
let place = self.place(Some(common));
self.doc.detach(last);
self.insert_at(place, last);
let new = self.clone_element(fe);
while let Some(child) = self.doc.first_child(furthest) {
self.doc.detach(child);
self.doc.insert(new, child, NONE);
}
self.doc.insert(furthest, new, NONE);
let fe_active = self
.active
.iter()
.position(|&e| e == fe)
.expect("still active");
self.active.remove(fe_active);
if fe_active < bookmark {
bookmark -= 1;
}
self.active.insert(bookmark.min(self.active.len()), new);
let fe_open = self
.open
.iter()
.position(|o| o.id == fe)
.expect("still open");
let fe_entry = self.remove_open_at(fe_open);
let fb = self
.open
.iter()
.position(|o| o.id == furthest)
.expect("still open");
self.insert_open_at(
fb + 1,
Open {
id: new,
..fe_entry
},
);
}
false
}
fn text(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => self.insert_text(s),
Tok::Eof => {
self.err("expected-named-closing-tag-but-got-eof");
self.pop();
let original = self.original;
self.reprocess(original, t);
}
Tok::End(_) => {
self.pop();
self.mode = self.original;
}
_ => {}
}
}
fn in_table(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s)
if matches!(
self.current().tag,
Table | Tbody | Template | Tfoot | Thead | Tr
) && self.current().ns == Ns::Html =>
{
self.pending.clear();
self.pending_text = false;
self.pending_at = self.text_at(s);
self.original = self.mode;
self.reprocess(Mode::InTableText, t);
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) => match s.tag {
Caption => {
self.clear_to_table_context();
self.active.push(MARKER);
self.insert_html(&s);
self.mode = Mode::InCaption;
}
Colgroup => {
self.clear_to_table_context();
self.insert_html(&s);
self.mode = Mode::InColumnGroup;
}
Col => {
self.clear_to_table_context();
self.insert_html(&Start::bare(Colgroup));
self.reprocess(Mode::InColumnGroup, t);
}
Tbody | Tfoot | Thead => {
self.clear_to_table_context();
self.insert_html(&s);
self.mode = Mode::InTableBody;
}
Td | Th | Tr => {
self.clear_to_table_context();
self.insert_html(&Start::bare(Tbody));
self.reprocess(Mode::InTableBody, t);
}
Table => {
self.err("unexpected-start-tag-implies-end-tag");
if self.in_scope(Table, Scope::Table) {
self.pop_until(Table);
self.reset_mode();
self.process(t);
}
}
Style | Script | Template => self.in_head(t),
Input
if s.attr("type")
.is_some_and(|v| v.eq_ignore_ascii_case("hidden")) =>
{
self.err("unexpected-hidden-input-in-table");
self.insert_void(&s);
}
Form => {
self.err("unexpected-form-in-table");
let template = self.in_template_contents();
if self.form != NONE && !template {
return;
}
let id = self.insert_html(&s);
if !template {
self.form = id;
}
self.pop();
}
_ => self.in_table_else(t),
},
Tok::End(e) => match e.tag {
Table => {
if self.in_scope(Table, Scope::Table) {
self.pop_until(Table);
self.reset_mode();
} else {
self.err("unexpected-end-tag");
}
}
Body | Caption | Col | Colgroup | Html | Tbody | Td | Tfoot | Th | Thead | Tr => {
self.err("unexpected-end-tag");
}
Template => self.in_head(t),
_ => self.in_table_else(t),
},
Tok::Eof => self.in_body(t),
Tok::Text(_) => self.in_table_else(t),
}
}
fn in_table_else(&mut self, t: Tok<'_>) {
match t {
Tok::Start(_) => self.err("foster-parenting-start-tag"),
Tok::End(_) => self.err("foster-parenting-end-tag"),
Tok::Text(s) => self.chars_dropped(s, "foster-parenting-character", false),
_ => {}
}
let foster = self.foster;
self.foster = true;
self.in_body(t);
self.foster = foster;
}
fn in_table_text(&mut self, t: Tok<'_>) {
if let Tok::Text(s) = t {
if self.errors {
for i in memchr::memchr_iter(0, s.as_bytes()) {
self.err_in("invalid-codepoint-in-table-text", s, i);
}
}
for piece in s.split('\0') {
if !all_space(piece) {
self.pending_text = true;
}
self.pending.push_str(piece);
}
self.pending_at[1] = self.text_at(s)[1];
return;
}
let at = std::mem::replace(&mut self.at, self.pending_at);
let pending = std::mem::take(&mut self.pending);
if self.pending_text {
self.chars_dropped(&pending, "foster-parenting-character", false);
let foster = self.foster;
self.foster = true;
self.body_text(&pending);
self.foster = foster;
} else {
self.insert_text(&pending);
}
self.pending = pending;
self.pending.clear();
self.at = at;
let original = self.original;
self.reprocess(original, t);
}
fn close_caption(&mut self) -> bool {
if !self.in_scope(Tag::Caption, Scope::Table) {
self.err("unexpected-end-tag");
return false;
}
self.generate_implied(None);
if !self.current().is(Tag::Caption) {
self.err("expected-one-end-tag-but-got-another");
}
self.pop_until(Tag::Caption);
self.clear_active_to_marker();
self.mode = Mode::InTable;
true
}
fn in_caption(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::End(e) if e.tag == Caption => {
self.close_caption();
}
Tok::Start(s)
if matches!(
s.tag,
Caption | Col | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
) =>
{
if self.close_caption() {
self.process(t);
}
}
Tok::End(e) if e.tag == Table => {
if self.close_caption() {
self.process(t);
}
}
Tok::End(e)
if matches!(
e.tag,
Body | Col | Colgroup | Html | Tbody | Td | Tfoot | Th | Thead | Tr
) =>
{
self.err("unexpected-end-tag");
}
_ => self.in_body(t),
}
}
fn in_column_group(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s) => {
let (space, rest) = split_space(s);
self.insert_text(space);
if !rest.is_empty() {
self.in_column_group_else(Tok::Text(rest));
}
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) if s.tag == Html => self.in_body(t),
Tok::Start(s) if s.tag == Col => self.insert_void(&s),
Tok::End(e) if e.tag == Colgroup => {
if self.current().is(Colgroup) {
self.pop();
self.mode = Mode::InTable;
} else {
self.err("unexpected-end-tag");
}
}
Tok::End(e) if e.tag == Col => self.err("no-end-tag"),
Tok::Start(s) if s.tag == Template => self.in_head(t),
Tok::End(e) if e.tag == Template => self.in_head(t),
Tok::Eof => self.in_body(t),
_ => self.in_column_group_else(t),
}
}
fn in_column_group_else(&mut self, t: Tok<'_>) {
if self.current().is(Tag::Colgroup) {
self.pop();
self.reprocess(Mode::InTable, t);
} else if let Tok::Text(s) = t {
self.chars_dropped(s, "unexpected-character-in-colgroup", true);
self.frameset_space(s);
} else {
self.err("unexpected-character-in-colgroup");
}
}
fn in_table_body(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Start(s) if s.tag == Tr => {
self.clear_to_table_body_context();
self.insert_html(&s);
self.mode = Mode::InRow;
}
Tok::Start(s) if matches!(s.tag, Th | Td) => {
self.err("unexpected-cell-in-table-body");
self.clear_to_table_body_context();
self.insert_html(&Start::bare(Tr));
self.reprocess(Mode::InRow, t);
}
Tok::End(e) if matches!(e.tag, Tbody | Tfoot | Thead) => {
if self.in_scope(e.tag, Scope::Table) {
self.clear_to_table_body_context();
self.pop();
self.mode = Mode::InTable;
} else {
self.err("unexpected-end-tag-in-table-body");
}
}
Tok::Start(s) if matches!(s.tag, Caption | Col | Colgroup | Tbody | Tfoot | Thead) => {
self.table_body_exit(t);
}
Tok::End(e) if e.tag == Table => self.table_body_exit(t),
Tok::End(e)
if matches!(e.tag, Body | Caption | Col | Colgroup | Html | Td | Th | Tr) =>
{
self.err("unexpected-end-tag-in-table-body");
}
_ => self.in_table(t),
}
}
fn table_body_exit(&mut self, t: Tok<'_>) {
use Tag::*;
if self.in_scope_any(&[Tbody, Thead, Tfoot], Scope::Table) {
self.clear_to_table_body_context();
self.pop();
self.reprocess(Mode::InTable, t);
} else {
self.err("unexpected-end-tag");
}
}
fn in_row(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Start(s) if matches!(s.tag, Th | Td) => {
self.clear_to_table_row_context();
self.insert_html(&s);
self.mode = Mode::InCell;
self.active.push(MARKER);
}
Tok::End(e) if e.tag == Tr => {
if self.in_scope(Tr, Scope::Table) {
self.clear_to_table_row_context();
self.pop();
self.mode = Mode::InTableBody;
} else {
self.err("unexpected-end-tag");
}
}
Tok::Start(s)
if matches!(s.tag, Caption | Col | Colgroup | Tbody | Tfoot | Thead | Tr) =>
{
self.row_exit(t);
}
Tok::End(e) if e.tag == Table => self.row_exit(t),
Tok::End(e) if matches!(e.tag, Tbody | Tfoot | Thead) => {
if self.in_scope(e.tag, Scope::Table) {
self.row_exit(t);
} else {
self.err("unexpected-end-tag-in-table-row");
}
}
Tok::End(e) if matches!(e.tag, Body | Caption | Col | Colgroup | Html | Td | Th) => {
self.err("unexpected-end-tag-in-table-row");
}
_ => self.in_table(t),
}
}
fn row_exit(&mut self, t: Tok<'_>) {
if self.in_scope(Tag::Tr, Scope::Table) {
self.clear_to_table_row_context();
self.pop();
self.reprocess(Mode::InTableBody, t);
} else {
self.err("unexpected-end-tag");
}
}
fn close_cell(&mut self) {
self.generate_implied(None);
let c = self.current();
if !(c.is(Tag::Td) || c.is(Tag::Th)) {
self.err("unexpected-cell-end-tag");
}
self.pop_until_where(|t| matches!(t, Tag::Td | Tag::Th));
self.clear_active_to_marker();
self.mode = Mode::InRow;
}
fn in_cell(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::End(e) if matches!(e.tag, Td | Th) => {
if self.in_scope(e.tag, Scope::Table) {
self.generate_implied(None);
if !self.current().is(e.tag) {
self.err("unexpected-cell-end-tag");
}
self.pop_until(e.tag);
self.clear_active_to_marker();
self.mode = Mode::InRow;
} else {
self.err("unexpected-end-tag");
}
}
Tok::Start(s)
if matches!(
s.tag,
Caption | Col | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
) =>
{
if self.in_scope_any(&[Td, Th], Scope::Table) {
self.close_cell();
self.process(t);
} else {
self.err("unexpected-start-tag");
}
}
Tok::End(e) if matches!(e.tag, Body | Caption | Col | Colgroup | Html) => {
self.err("unexpected-end-tag");
}
Tok::End(e) if matches!(e.tag, Table | Tbody | Tfoot | Thead | Tr) => {
if self.in_scope(e.tag, Scope::Table) {
self.close_cell();
self.process(t);
} else {
self.err("unexpected-end-tag");
}
}
_ => self.in_body(t),
}
}
fn in_template(&mut self, t: Tok<'_>) {
use Tag::*;
let switch = |me: &mut Self, mode: Mode| {
me.template_modes.pop();
me.template_modes.push(mode);
me.reprocess(mode, t);
};
match t {
Tok::Text(_) | Tok::Comment(_) | Tok::Pi(..) | Tok::Doctype(_) => self.in_body(t),
Tok::Start(s) => match s.tag {
Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
| Title => self.in_head(t),
Caption | Colgroup | Tbody | Tfoot | Thead => switch(self, Mode::InTable),
Col => switch(self, Mode::InColumnGroup),
Tr => switch(self, Mode::InTableBody),
Td | Th => switch(self, Mode::InRow),
_ => switch(self, Mode::InBody),
},
Tok::End(e) if e.tag == Template => self.in_head(t),
Tok::End(_) => self.err("unexpected-end-tag"),
Tok::Eof => {
if !self.template_open() {
self.stop();
return;
}
self.err("eof-in-template");
self.pop_until(Template);
self.clear_active_to_marker();
self.template_modes.pop();
self.reset_mode();
self.eof_again = true;
}
}
}
fn after_body(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => {
let (space, rest) = split_space(s);
if !space.is_empty() {
self.in_body(Tok::Text(space));
}
if !rest.is_empty() {
self.err_in("unexpected-char-after-body", rest, 0);
self.reprocess(Mode::InBody, Tok::Text(rest));
}
}
Tok::Comment(c) => {
let root = self.open[0].id;
self.insert_comment(c, Some((root, NONE)));
}
Tok::Pi(target, data) => {
let root = self.open[0].id;
self.insert_pi(target, data, Some((root, NONE)));
}
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
Tok::End(e) if e.tag == Tag::Html => {
if self.context.is_none() {
self.mode = Mode::AfterAfterBody;
let html = self.open[0].id;
self.ended(html);
} else {
self.err("unexpected-end-tag-after-body-innerhtml");
}
}
Tok::Eof => self.stop(),
_ => {
self.err(match t {
Tok::Start(_) => "unexpected-start-tag-after-body",
_ => "unexpected-end-tag-after-body",
});
self.reprocess(Mode::InBody, t);
}
}
}
fn chars_dropped(&mut self, s: &str, code: &'static str, but_space: bool) {
if self.errors {
for (i, c) in s.char_indices() {
if !(but_space && is_space_char(c)) {
self.err_in(code, s, i);
}
}
}
}
fn frameset_space(&mut self, s: &str) {
for space in space_runs(s) {
self.insert_text(space);
}
}
fn in_frameset(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s) => {
self.chars_dropped(s, "unexpected-char-in-frameset", true);
self.frameset_space(s);
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) => match s.tag {
Html => self.in_body(t),
Frameset => {
self.insert_html(&s);
}
Frame => self.insert_void(&s),
Noframes => self.in_head(t),
_ => self.err("unexpected-start-tag-in-frameset"),
},
Tok::End(e) if e.tag == Frameset => {
if self.open.len() == 1 {
self.err("unexpected-frameset-in-frameset-innerhtml");
return;
}
self.pop();
if self.context.is_none() && !self.current().is(Frameset) {
self.mode = Mode::AfterFrameset;
}
}
Tok::End(_) => self.err("unexpected-end-tag-in-frameset"),
Tok::Eof => {
if self.open.len() > 1 {
self.err("eof-in-frameset");
}
self.stop();
}
}
}
fn after_frameset(&mut self, t: Tok<'_>) {
match t {
Tok::Text(s) => {
self.chars_dropped(s, "unexpected-char-after-frameset", true);
self.frameset_space(s);
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
Tok::End(e) if e.tag == Tag::Html => self.mode = Mode::AfterAfterFrameset,
Tok::Start(s) if s.tag == Tag::Noframes => self.in_head(t),
Tok::Eof => self.stop(),
Tok::Start(_) => self.err("unexpected-start-tag-after-frameset"),
Tok::End(_) => self.err("unexpected-end-tag-after-frameset"),
}
}
fn after_after_body(&mut self, t: Tok<'_>) {
match t {
Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
Tok::Doctype(_) => self.in_body(t),
Tok::Text(s) => {
let (space, rest) = split_space(s);
if !space.is_empty() {
self.in_body(Tok::Text(space));
}
if !rest.is_empty() {
self.err_in("expected-eof-but-got-char", rest, 0);
self.reprocess(Mode::InBody, Tok::Text(rest));
}
}
Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
Tok::Eof => self.stop(),
_ => {
self.err(match t {
Tok::Start(_) => "expected-eof-but-got-start-tag",
_ => "expected-eof-but-got-end-tag",
});
self.reprocess(Mode::InBody, t);
}
}
}
fn after_after_frameset(&mut self, t: Tok<'_>) {
match t {
Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
Tok::Doctype(_) => self.in_body(t),
Tok::Text(s) => {
self.chars_dropped(s, "expected-eof-but-got-char", true);
for space in space_runs(s) {
self.in_body(Tok::Text(space));
}
}
Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
Tok::Start(s) if s.tag == Tag::Noframes => self.in_head(t),
Tok::Eof => self.stop(),
Tok::Start(_) => self.err("expected-eof-but-got-start-tag"),
Tok::End(_) => self.err("expected-eof-but-got-end-tag"),
}
}
fn foreign(&mut self, t: Tok<'_>) {
use Tag::*;
match t {
Tok::Text(s) => {
if s.contains('\0') {
if self.errors {
for i in memchr::memchr_iter(0, s.as_bytes()) {
self.err_in("invalid-codepoint-in-foreign-content", s, i);
}
}
self.insert_text(&s.replace('\0', "\u{FFFD}"));
} else {
self.insert_text(s);
}
if s.bytes().any(|b| !is_space(b) && b != 0) {
self.frameset_ok = false;
}
}
Tok::Comment(c) => self.insert_comment(c, None),
Tok::Pi(target, data) => self.insert_pi(target, data, None),
Tok::Doctype(_) => self.err("unexpected-doctype"),
Tok::Start(s)
if matches!(
s.tag,
B | Big
| Blockquote
| Body
| Br
| Center
| Code
| Dd
| Div
| Dl
| Dt
| Em
| Embed
| H1
| H2
| H3
| H4
| H5
| H6
| Head
| Hr
| I
| Img
| Li
| Listing
| Menu
| Meta
| Nobr
| Ol
| P
| Pre
| Ruby
| S
| Small
| Span
| Strong
| Strike
| Sub
| Sup
| Table
| Tt
| U
| Ul
| Var
) || (s.tag == Font
&& s.attrs()
.any(|(n, _)| matches!(n, "color" | "face" | "size"))) =>
{
self.err("unexpected-html-element-in-foreign-content");
self.break_out(t);
}
Tok::End(e) if matches!(e.tag, Br | P) => {
self.err("unexpected-end-tag");
self.break_out(t);
}
Tok::Start(s) => {
let ns = self.adjusted_current().map_or(Ns::Html, |a| a.ns);
self.insert_element(&s, ns);
if s.self_closing {
self.acknowledged = true;
self.pop();
}
}
Tok::End(e) => {
let c = self.current();
if e.tag == Script && c.ns == Ns::Svg && c.tag == Script {
self.pop();
return;
}
let mut i = self.open.len() - 1;
let current = self
.doc
.element(c.id)
.is_some_and(|el| self.doc.element_name(el).eq_ignore_ascii_case(e.name));
if !current {
self.err("unexpected-end-tag");
}
if !current && self.open_named(false, e.name) == 0 {
if i > 0 {
self.html(t);
}
return;
}
loop {
if i == 0 {
return;
}
let node = self.open[i];
let name = self
.doc
.element(node.id)
.map(|el| self.doc.element_name(el))
.unwrap_or("");
if name.eq_ignore_ascii_case(e.name) {
self.truncate_open(i);
return;
}
i -= 1;
if self.open[i].ns == Ns::Html {
self.html(t);
return;
}
}
}
Tok::Eof => self.html(t),
}
}
fn break_out(&mut self, t: Tok<'_>) {
loop {
let c = self.current();
let html_integration = match c.ns {
Ns::Svg => matches!(c.tag, Tag::ForeignObject | Tag::Desc | Tag::Title),
Ns::MathMl => self.doc.element(c.id).is_some_and(|e| e.html_integration),
Ns::Html | Ns::Xml => true,
};
if mathml_text_integration(c) || html_integration {
break;
}
self.pop();
}
self.html(t);
}
}
impl Sink for TreeBuilder {
fn doctype(&mut self, d: &Doctype<'_>) {
self.skip_newline = false;
self.process(Tok::Doctype(d));
}
fn start_tag(&mut self, tag: &tokenizer::Tag<'_>) -> Option<TextMode> {
self.skip_newline = false;
self.switch = None;
self.acknowledged = false;
self.process(Tok::Start(Start {
tag: Tag::from_name(tag.name),
name: tag.name,
attrs: Some(tag),
self_closing: tag.self_closing,
}));
if self.errors && tag.self_closing && !self.acknowledged {
self.err("non-void-element-with-trailing-solidus");
}
self.switch.take()
}
fn end_tag(&mut self, tag: &tokenizer::Tag<'_>) {
self.skip_newline = false;
if self.spans {
self.closing_name.clear();
self.closing_name.push_str(tag.name);
self.closing = true;
}
self.process(Tok::End(End {
tag: Tag::from_name(tag.name),
name: tag.name,
}));
self.closing = false;
}
fn comment(&mut self, text: &str) {
self.skip_newline = false;
self.process(Tok::Comment(text));
}
fn processing_instruction(&mut self, target: &str, data: &str) {
self.skip_newline = false;
self.process(Tok::Pi(target, data));
}
fn text(&mut self, text: &str) {
let mut text = text;
if std::mem::take(&mut self.skip_newline) {
text = text.strip_prefix('\n').unwrap_or(text);
}
if !text.is_empty() {
self.process(Tok::Text(text));
}
}
fn eof(&mut self) {
self.at = [self.doc.src.len() as u32; 2];
self.process(Tok::Eof);
while std::mem::take(&mut self.eof_again) {
self.process(Tok::Eof);
}
}
fn error(&mut self, code: &'static str, at: usize) {
self.errors_found.push((code, at as u32));
}
fn cdata_allowed(&self) -> bool {
self.adjusted_current().is_some_and(|a| a.ns != Ns::Html)
}
fn position(&mut self, start: usize, end: usize) {
debug_assert!(
start <= end && end <= self.doc.src.len(),
"token at {start}..{end}, outside {} bytes of source",
self.doc.src.len()
);
self.at = [start as u32, end as u32];
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct Options {
pub scripting: bool,
pub budget: Option<std::time::Duration>,
pub errors: bool,
pub spans: bool,
pub max_depth: Option<usize>,
pub declarative_shadow_roots: Option<bool>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SyntaxError {
pub code: &'static str,
pub offset: usize,
pub line: usize,
pub column: usize,
}
impl std::fmt::Display for SyntaxError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}:{}: {}", self.line, self.column, self.code)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ParseError {
TooLarge { len: usize },
Timeout {
budget: std::time::Duration,
parsed: usize,
},
}
impl std::fmt::Display for ParseError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
ParseError::TooLarge { len } => write!(
f,
"{len} bytes of HTML is over the {} byte limit",
crate::MAX_INPUT
),
ParseError::Timeout { budget, parsed } => write!(
f,
"parsing took longer than {budget:?} (gave up after {parsed} bytes)"
),
}
}
}
impl std::error::Error for ParseError {}
pub fn parse(html: &str, scripting: bool) -> Document {
parse_with(
html,
Options {
scripting,
..Options::default()
},
)
.unwrap_or_else(|e| panic!("{e}"))
}
pub fn parse_with(html: &str, options: Options) -> Result<Document, ParseError> {
run(html, options, None)
}
pub fn parse_fragment(html: &str, ns: Ns, context: &str, scripting: bool) -> Document {
parse_fragment_with(
html,
ns,
context,
Options {
scripting,
..Options::default()
},
)
.unwrap_or_else(|e| panic!("{e}"))
}
pub fn parse_fragment_with(
html: &str,
ns: Ns,
context: &str,
options: Options,
) -> Result<Document, ParseError> {
run(html, options, Some((ns, context)))
}
fn run(html: &str, options: Options, fragment: Option<(Ns, &str)>) -> Result<Document, ParseError> {
let bom = fragment.is_none() && html.starts_with('\u{FEFF}');
let len = html.len() - if bom { 3 } else { 0 };
if len > crate::MAX_INPUT {
return Err(ParseError::TooLarge { len });
}
let mut parser = Parser::start(options, fragment, html.len());
parser.push(html);
parser.finish()
}
pub struct Parser {
builder: TreeBuilder,
tokenizer: Tokenizer<'static>,
options: Options,
fragment: bool,
started: bool,
cr: bool,
len: usize,
spent: std::time::Duration,
too_large: bool,
}
impl Parser {
pub fn new(options: Options) -> Parser {
Parser::start(options, None, 0)
}
pub fn fragment(ns: Ns, context: &str, options: Options) -> Parser {
Parser::start(options, Some((ns, context)), 0)
}
fn start(options: Options, fragment: Option<(Ns, &str)>, capacity: usize) -> Parser {
let mut builder = TreeBuilder::new(capacity, options.scripting);
builder.doc.src = String::with_capacity(capacity);
builder.doc.scripting = options.scripting;
builder.max_depth = options.max_depth.map(|d| d.max(1));
builder.spans = options.spans;
builder.errors = options.errors;
builder.shadow_roots = options
.declarative_shadow_roots
.unwrap_or(fragment.is_none());
if options.spans || options.errors {
builder.doc.positions = Some(Box::default());
}
let mode = match fragment {
Some((ns, context)) => builder.fragment(ns, context),
None => None,
};
let mut tokenizer = Tokenizer::new("");
if let Some(mode) = mode {
tokenizer.set_text_mode(mode);
}
if options.errors {
tokenizer.report_errors();
}
if options.spans || options.errors {
tokenizer.keep_positions();
}
Parser {
builder,
tokenizer,
options,
fragment: fragment.is_some(),
started: false,
cr: false,
len: 0,
spent: std::time::Duration::ZERO,
too_large: false,
}
}
pub fn feed(&mut self, chunk: &str) {
if self.push(chunk) {
self.tokenize(true);
#[cfg(debug_assertions)]
self.builder.check_stack(false);
}
}
pub fn finish(mut self) -> Result<Document, ParseError> {
if self.too_large {
return Err(ParseError::TooLarge { len: self.len });
}
if !self.tokenizer.timed_out() {
if std::mem::take(&mut self.cr) {
self.builder.doc.src.push('\n');
}
self.tokenize(false);
}
if self.tokenizer.timed_out() {
return Err(ParseError::Timeout {
budget: self.options.budget.unwrap_or_default(),
parsed: self.tokenizer.position(),
});
}
#[cfg(debug_assertions)]
self.builder.check_stack(true);
if self.fragment {
self.builder.finish_fragment();
}
self.builder.release_shadow_roots();
self.builder.finish_errors();
let mut doc = self.builder.doc;
doc.src.shrink_to_fit();
Ok(doc)
}
fn push(&mut self, chunk: &str) -> bool {
let mut chunk = chunk;
if !self.started && !chunk.is_empty() {
self.started = true;
if !self.fragment
&& let Some(rest) = chunk.strip_prefix('\u{FEFF}')
{
chunk = rest;
if let Some(p) = self.builder.doc.positions.as_deref_mut() {
p.skipped = 3;
}
}
}
self.len += chunk.len();
if self.too_large || self.len > crate::MAX_INPUT {
if !self.too_large {
self.too_large = true;
self.builder.doc.src = String::new();
}
return false;
}
if self.tokenizer.timed_out() {
return false;
}
let doc = &mut self.builder.doc;
let (src, mut positions) = (&mut doc.src, doc.positions.as_deref_mut());
let mut crlf = |at: usize| {
if let Some(p) = positions.as_deref_mut() {
p.crlf.push(at as u32);
}
};
let mut rest = chunk;
if rest.is_empty() {
return true;
}
if std::mem::take(&mut self.cr) {
if let Some(after) = rest.strip_prefix('\n') {
crlf(src.len());
rest = after;
}
src.push('\n');
}
while let Some(i) = memchr::memchr(b'\r', rest.as_bytes()) {
src.push_str(&rest[..i]);
match rest.as_bytes().get(i + 1) {
None => {
self.cr = true;
return true;
}
Some(b'\n') => {
crlf(src.len());
rest = &rest[i + 2..];
}
Some(_) => rest = &rest[i + 1..],
}
src.push('\n');
}
src.push_str(rest);
true
}
fn tokenize(&mut self, partial: bool) {
let start = self.options.budget.map(|_| std::time::Instant::now());
let src: &'static str = unsafe { &*(self.builder.doc.src.as_str() as *const str) };
self.tokenizer.extend(src);
if let Some((budget, start)) = self.options.budget.zip(start) {
match budget.checked_sub(self.spent) {
Some(left) => {
if let Some(deadline) = start.checked_add(left) {
self.tokenizer.set_deadline(deadline);
}
}
None => self.tokenizer.set_deadline(start),
}
}
if partial {
self.tokenizer.run_partial(&mut self.builder);
} else {
self.tokenizer.run(&mut self.builder);
}
self.tokenizer.detach();
if let Some(start) = start {
self.spent += start.elapsed();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::time::Duration;
#[test]
fn noahs_ark_matches_attributes_in_any_order() {
let html = "<p><b a=1 c=2><b c=2 a=1><b a=1 c=2><b c=3 a=1><b c=2 a=1></p><p>x";
let doc = parse(html, false);
let out = doc.outer_html(doc.root());
let second = &out[out.rfind("<p>").unwrap()..];
assert_eq!(second.matches("<b ").count(), 4, "{out}");
assert_eq!(second.matches("c=\"3\"").count(), 1, "{out}");
}
#[test]
fn a_budget_stops_a_long_parse_and_says_how_far_it_got() {
let html = "<div><b>x</b> y</div>".repeat(200_000);
let tight = Options {
budget: Some(Duration::from_micros(50)),
..Options::default()
};
match parse_with(&html, tight) {
Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
}
let roomy = Options {
budget: Some(Duration::from_secs(60)),
..Options::default()
};
assert!(parse_with(&html, roomy).is_ok());
}
#[test]
fn a_long_run_of_references_is_one_text_node() {
let html = "<p>".to_owned() + &"&x© ".repeat(20_000) + "<b>";
let with_spans = Options {
spans: true,
errors: true,
..Options::default()
};
for doc in [parse(&html, false), parse_with(&html, with_spans).unwrap()] {
let p = (0..doc.len() as NodeId)
.find(|&n| doc.lower_name(n) == Some("p"))
.unwrap();
assert_eq!(doc.children(p).count(), 2);
assert_eq!(doc.text(p), "&x\u{a9}\u{a0}".repeat(20_000));
}
}
#[test]
fn max_depth_keeps_the_tree_shallow_and_every_element() {
fn deepest(doc: &Document, id: NodeId) -> usize {
1 + doc.children(id).map(|c| deepest(doc, c)).max().unwrap_or(0)
}
let html = "<div>".repeat(1_000) + "x" + &"</div>".repeat(1_000);
let free = parse(&html, false);
assert!(deepest(&free, free.root()) > 1_000);
let capped = parse_with(
&html,
Options {
max_depth: Some(100),
..Options::default()
},
)
.unwrap();
assert!(deepest(&capped, capped.root()) <= 102);
let divs = |doc: &Document| {
(0..doc.len() as NodeId)
.filter(|&n| doc.lower_name(n) == Some("div"))
.count()
};
assert_eq!(divs(&capped), 1_000);
assert!(capped.text(capped.root()).contains('x'));
let shallow = "<div><p>a<b>b</b></p></div>";
let same = parse_with(
shallow,
Options {
max_depth: Some(100),
..Options::default()
},
)
.unwrap();
let plain = parse(shallow, false);
assert_eq!(same.inner_html(same.root()), plain.inner_html(plain.root()));
let at = |max_depth| {
let doc = parse_with(
shallow,
Options {
max_depth: Some(max_depth),
..Options::default()
},
)
.unwrap();
doc.inner_html(doc.root())
};
assert_eq!(at(0), at(1));
assert!(at(0).contains("<div></div><p></p>a<b></b>b"), "{}", at(0));
}
#[test]
fn a_fragment_has_a_budget_and_a_size_limit_too() {
let html = "<div><b>x</b> y</div>".repeat(200_000);
let tight = Options {
budget: Some(Duration::from_micros(50)),
..Options::default()
};
match parse_fragment_with(&html, Ns::Html, "div", tight) {
Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
}
let doc = parse_fragment_with("<b>x</b>", Ns::Html, "div", Options::default()).unwrap();
assert_eq!(doc.inner_html(doc.root()), "<b>x</b>");
let huge = "x".repeat(crate::MAX_INPUT + 1);
assert_eq!(
parse_fragment_with(&huge, Ns::Html, "div", Options::default()).map(|d| d.len()),
Err(ParseError::TooLarge { len: huge.len() })
);
}
#[test]
fn a_leading_byte_order_mark_is_dropped_from_a_document() {
let page = "<!DOCTYPE html><p>x</p>";
let with = parse(&format!("\u{FEFF}{page}"), false);
let without = parse(page, false);
assert_eq!(with.quirks(), crate::Quirks::No);
assert_eq!(
with.inner_html(with.root()),
without.inner_html(without.root())
);
let twice = parse("\u{FEFF}\u{FEFF}<p>x</p>", false);
assert!(twice.inner_html(twice.root()).contains('\u{FEFF}'));
let fragment = parse_fragment("\u{FEFF}x", Ns::Html, "div", false);
assert!(fragment.inner_html(fragment.root()).contains('\u{FEFF}'));
}
#[test]
fn a_budget_too_big_for_the_clock_is_no_limit() {
let endless = Options {
budget: Some(Duration::MAX),
..Options::default()
};
assert!(parse_with("<p>x", endless).is_ok());
}
fn in_pieces(pieces: &[&str]) -> Document {
let mut parser = Parser::new(Options::default());
for piece in pieces {
parser.feed(piece);
}
parser.finish().unwrap()
}
#[test]
fn the_tree_grows_as_the_pieces_come() {
let mut parser = Parser::new(Options::default());
parser.feed("<ul><li>one<li>tw");
let early = parser.builder.doc.len();
assert_eq!(early, 9);
parser.feed("o</ul><p a=\"x");
assert_eq!(parser.builder.doc.len(), early);
parser.feed("\">three");
assert_eq!(parser.builder.doc.len(), early + 2);
let doc = parser.finish().unwrap();
assert_eq!(
doc.inner_html(doc.root()),
"<html><head></head><body><ul><li>one</li><li>two</li></ul>\
<p a=\"x\">three</p></body></html>"
);
}
#[test]
fn whitespace_after_a_dropped_character_in_a_template_column_group_stays() {
let html = "<template><col>A \n<col></template>";
let want = "<html><head><template><col> \n<col></template></head><body></body></html>";
assert_eq!(parse(html, false).inner_html(0), want);
let (a, b) = html.split_at(html.find(' ').unwrap());
assert_eq!(in_pieces(&[a, b]).inner_html(0), want);
let errors = parse_with(
html,
Options {
errors: true,
..Options::default()
},
)
.unwrap();
let dropped = errors
.errors()
.iter()
.filter(|e| e.code == "unexpected-character-in-colgroup");
assert_eq!(dropped.count(), 1);
}
#[test]
fn a_cr_at_the_end_of_a_piece_waits_for_the_next() {
let text = |doc: &Document| doc.text(doc.root());
assert_eq!(text(&in_pieces(&["a\r", "\nb"])), "a\nb");
assert_eq!(text(&in_pieces(&["a\r", "b"])), "a\nb");
assert_eq!(text(&in_pieces(&["a\r", "", "\r\nb\r"])), "a\n\nb\n");
let pre = in_pieces(&["<pre>\r", "\nx</pre>"]);
assert_eq!(text(&pre), "x");
}
#[test]
fn a_byte_order_mark_is_dropped_from_a_documents_first_piece() {
let whole = parse("<p>x", false);
let pieces = in_pieces(&["", "\u{FEFF}", "<p>x"]);
assert_eq!(pieces.inner_html(0), whole.inner_html(0));
let mut fragment = Parser::fragment(Ns::Html, "div", Options::default());
fragment.feed("\u{FEFF}x");
let fragment = fragment.finish().unwrap();
assert!(fragment.inner_html(0).contains('\u{FEFF}'));
}
#[test]
fn a_budget_and_the_size_limit_hold_for_pieces_too() {
let tight = Options {
budget: Some(Duration::from_micros(50)),
..Options::default()
};
let piece = "<div><b>x</b> y</div>".repeat(10_000);
let mut parser = Parser::new(tight);
for _ in 0..20 {
parser.feed(&piece);
}
match parser.finish() {
Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < piece.len() * 20),
other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
}
let huge = "x".repeat(crate::MAX_INPUT);
let mut parser = Parser::new(Options::default());
parser.feed(&huge);
parser.feed("xy");
assert_eq!(
parser.finish().map(|d| d.len()),
Err(ParseError::TooLarge {
len: crate::MAX_INPUT + 2
})
);
}
}
#[cfg(test)]
mod hostile {
use super::*;
use std::time::{Duration, Instant};
fn time(html: &str) -> Duration {
let start = Instant::now();
std::hint::black_box(parse(html, false));
start.elapsed()
}
fn grows_linearly(make: impl Fn(usize) -> String) {
grows_linearly_timed(make, time);
}
fn grows_linearly_timed(make: impl Fn(usize) -> String, time: fn(&str) -> Duration) {
let (small, large) = (make(5_000), make(20_000));
let rounds: Vec<_> = (0..5).map(|_| (time(&small), time(&large))).collect();
assert!(
rounds
.iter()
.any(|&(a, b)| b < a * 8 + Duration::from_millis(20)),
"{} bytes, then {} bytes, took {rounds:?}",
small.len(),
large.len()
);
}
fn time_in_pieces(html: &str) -> Duration {
let start = Instant::now();
let mut parser = Parser::new(Options::default());
for piece in html.as_bytes().chunks(64) {
parser.feed(std::str::from_utf8(piece).unwrap());
}
std::hint::black_box(parser.finish().unwrap());
start.elapsed()
}
#[test]
fn a_token_over_many_pieces_costs_linear_time() {
let long = |open: &'static str, close: &'static str, fill: &'static str| {
move |n: usize| format!("{open}{}{close}", fill.repeat(n * 10))
};
for make in [
long("<a href=\"", "\">", "x"),
long("<a href=", ">", "x"),
long("<a ", ">", "b"),
long("<", ">", "a"),
long("<!--", "-->", "x"),
long("<!DOCTYPE html PUBLIC \"", "\">", "x"),
long("<?pi ", "?>", "x"),
long("&#", ";", "1"),
long("&", ";", "a"),
long("<svg><![CDATA[", "]]>", "]"),
long("<script>", "</script>", "<"),
] {
grows_linearly_timed(make, time_in_pieces);
}
}
#[test]
fn copying_deep_option_contents_keeps_to_a_small_stack() {
let html = format!(
"<select><button><selectedcontent></selectedcontent></button><option>{}",
"<div>".repeat(20_000)
);
let parsed = std::thread::Builder::new()
.stack_size(256 * 1024)
.spawn(move || parse(&html, false).len())
.unwrap()
.join()
.unwrap();
assert!(parsed > 40_000, "both copies are there: {parsed} nodes");
}
#[test]
fn unmatched_end_tags_under_deep_nesting_cost_linear_time() {
grows_linearly(|n| format!("{}{}", "<span>".repeat(n), "</x>".repeat(n)));
grows_linearly(|n| format!("{}{}", "<span>".repeat(n), "</p>".repeat(n)));
grows_linearly(|n| format!("{}{}", "<x-a>".repeat(n), "</x-b>".repeat(n)));
}
#[test]
fn end_tags_under_deep_nesting_cost_linear_time() {
for end in ["</body>", "</html>", "</h1>", "<table>", "</body><p>"] {
grows_linearly(|n| format!("{}{}", "<div>".repeat(n), end.repeat(n)));
grows_linearly_timed(
|n| format!("{}{}", "<div>".repeat(n), end.repeat(n)),
time_with_errors,
);
}
grows_linearly(|n| format!("<applet>{}{}", "<div>".repeat(n), "</body>".repeat(n)));
grows_linearly(|n| format!("<table><td>{}{}", "<div>".repeat(n), "</td>".repeat(n)));
}
fn time_with_errors(html: &str) -> Duration {
let start = Instant::now();
let options = Options {
errors: true,
..Options::default()
};
std::hint::black_box(parse_with(html, options).unwrap());
start.elapsed()
}
#[test]
fn unmatched_end_tags_in_deep_svg_cost_linear_time() {
grows_linearly(|n| format!("<svg>{}{}", "<g>".repeat(n), "</x>".repeat(n)));
}
#[test]
fn options_under_deep_nesting_cost_linear_time() {
grows_linearly(|n| format!("{}{}", "<div>".repeat(n), "<option>".repeat(n)));
}
#[test]
fn text_split_by_merged_attributes_costs_linear_memory() {
let tail: String = (0..11_000).map(|i| format!("<body X{i}>b")).collect();
let html = format!("<body>a&{}{tail}", "x".repeat(100_000));
let doc = parse(&html, false);
assert!(doc.buf.len() + doc.extras.iter().map(|e| e.len()).sum::<usize>() < 4 * html.len());
assert!(doc.text(0).ends_with('b'));
}
fn attributes(n: usize) -> String {
(0..n).map(|i| format!(" a{i}=1")).collect()
}
#[test]
fn many_attributes_cost_linear_time() {
grows_linearly(|n| format!("<p{}>", attributes(n)));
grows_linearly(|n| format!("<p{}&>", attributes(n)));
grows_linearly(|n| format!("<svg{}>", attributes(n)));
grows_linearly(|n| format!("<body{0}><body{0}>", attributes(n / 2)));
grows_linearly(|n| {
(0..n / 4)
.map(|i| format!("<body x{i}=1><p a=1>"))
.collect()
});
let doc = parse("<body a=1><p b=2><body c=3 a=4><i d=5><body e=6>", false);
let body = (0..doc.len() as NodeId)
.find(|&n| doc.lower_name(n) == Some("body"))
.unwrap();
let attrs: Vec<_> = doc.attrs(body).map(|(_, n, v)| (n, v)).collect();
assert_eq!(attrs, [("a", "1"), ("c", "3"), ("e", "6")]);
}
#[test]
fn a_budget_holds_inside_a_tag_of_many_attributes() {
let none = Options {
budget: Some(Duration::ZERO),
..Options::default()
};
for html in [
format!("<p{}>", attributes(300_000)),
format!("<p{}&>", attributes(300_000)),
] {
match parse_with(&html, none) {
Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
}
}
}
#[test]
fn the_end_of_input_under_deep_templates_keeps_to_a_small_stack() {
for unit in [
"<template>",
"<div><template shadowrootmode=open>",
"<table><caption><template>",
"<template><tr>",
"<template><col>",
"<template><td>",
] {
let html = unit.repeat(100_000);
let sizes = std::thread::Builder::new()
.stack_size(256 * 1024)
.spawn(move || {
let doc = parse(&html, false);
let fragment = parse_fragment(&html, Ns::Html, "div", false);
let with_errors = Options {
errors: true,
max_depth: Some(512),
..Options::default()
};
let checked = parse_with(&html, with_errors).unwrap();
(doc.len(), fragment.len(), checked.errors().len())
})
.unwrap()
.join()
.unwrap();
assert!(sizes.0 > 100_000 && sizes.1 > 100_000, "{unit}: {sizes:?}");
assert!(sizes.2 >= 100_000, "{unit}: an error for each template");
}
}
}