Skip to main content

parsec/
tree.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! Tree construction, as section 13.2.6 of the HTML Standard describes it,
5//! with scripting off or on and no sanitizer.
6
7use std::collections::HashMap;
8
9use crate::dom::{
10    Attr, AttrNs, Data, Document, Element, NONE, Name, NodeId, Ns, Positions, Quirks, Span,
11};
12use crate::tags::Tag;
13use crate::tokenizer::{self, Doctype, Sink, TextMode, Tokenizer};
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16enum Mode {
17    Initial,
18    BeforeHtml,
19    BeforeHead,
20    InHead,
21    InHeadNoscript,
22    AfterHead,
23    InBody,
24    Text,
25    InTable,
26    InTableText,
27    InCaption,
28    InColumnGroup,
29    InTableBody,
30    InRow,
31    InCell,
32    InTemplate,
33    AfterBody,
34    InFrameset,
35    AfterFrameset,
36    AfterAfterBody,
37    AfterAfterFrameset,
38}
39
40#[derive(Clone, Copy)]
41struct Start<'t> {
42    tag: Tag,
43    name: &'t str,
44    attrs: Option<&'t tokenizer::Tag<'t>>,
45    self_closing: bool,
46}
47
48impl<'t> Start<'t> {
49    fn bare(tag: Tag) -> Start<'static> {
50        Start {
51            tag,
52            name: tag.name(),
53            attrs: None,
54            self_closing: false,
55        }
56    }
57
58    fn attrs(&self) -> impl Iterator<Item = (&'t str, &'t str)> + use<'t> {
59        self.attrs.into_iter().flat_map(|t| t.attrs())
60    }
61
62    fn attr(&self, name: &str) -> Option<&'t str> {
63        self.attrs().find(|(n, _)| *n == name).map(|(_, v)| v)
64    }
65}
66
67#[derive(Clone, Copy)]
68struct End<'t> {
69    tag: Tag,
70    name: &'t str,
71}
72
73#[derive(Clone, Copy)]
74enum Tok<'t> {
75    Doctype(&'t Doctype<'t>),
76    Start(Start<'t>),
77    End(End<'t>),
78    Text(&'t str),
79    Comment(&'t str),
80    Pi(&'t str, &'t str),
81    Eof,
82}
83
84/// An entry in the stack of open elements, with its namespace and tag
85/// beside it so scope checks don't touch the nodes.
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87struct Open {
88    id: NodeId,
89    ns: Ns,
90    tag: Tag,
91}
92
93impl Open {
94    fn is(self, tag: Tag) -> bool {
95        self.ns == Ns::Html && self.tag == tag
96    }
97}
98
99#[derive(Debug, Clone, Copy, PartialEq, Eq)]
100enum Scope {
101    Default,
102    ListItem,
103    Button,
104    Table,
105}
106
107const MARKER: NodeId = NONE;
108
109/// An element a later tag's attributes are merged into: the names it
110/// has, and where the spare slots after its attributes end.
111struct Merged {
112    names: std::collections::HashSet<String>,
113    room: u32,
114}
115
116pub(crate) struct TreeBuilder {
117    pub(crate) doc: Document,
118    /// From [`Options::max_depth`].
119    max_depth: Option<usize>,
120    open: Vec<Open>,
121    active: Vec<NodeId>,
122    mode: Mode,
123    original: Mode,
124    template_modes: Vec<Mode>,
125    head: NodeId,
126    form: NodeId,
127    frameset_ok: bool,
128    foster: bool,
129    scripting: bool,
130    context: Option<Open>,
131    pending: String,
132    pending_text: bool,
133    skip_newline: bool,
134    switch: Option<TextMode>,
135    done: bool,
136    /// Set when the end of the input closed a template and is to be read
137    /// again in the mode that leaves: the caller loops on it, so a page of
138    /// nested templates can't nest calls as deep.
139    eof_again: bool,
140    /// Each select's selected option, and each option's select, for
141    /// `<selectedcontent>`.
142    selected: HashMap<NodeId, NodeId>,
143    option_select: HashMap<NodeId, NodeId>,
144    /// The `<html>` and `<body>` a later tag of theirs has added to.
145    merged: HashMap<NodeId, Merged>,
146    /// How many HTML elements of each tag are open, so "is there a p in
147    /// button scope" is answered without walking the stack when none is.
148    counts: [u32; 256],
149    /// How many open foreign elements end the default scope (`mi`,
150    /// `foreignObject`...); `counts` has the HTML ones. With none open but
151    /// the root, `body` and `html`, at the bottom of the stack, are in
152    /// scope, and out of it otherwise.
153    foreign_boundaries: u32,
154    /// For each entry of the stack, whether a p is in button scope with
155    /// the stack cut off there. Nearly every block start tag asks, and a
156    /// p under thousands of open divs made each ask walk them all.
157    p_in_scope: Vec<bool>,
158    /// How many open elements have each name, for those `counts` doesn't
159    /// cover: HTML elements of no known tag, and foreign elements. Keyed
160    /// by [`name_key`]: two names can share a slot, which only makes a
161    /// count too high, so the walk it saves is made after all.
162    names: Box<[u32; NAME_SLOTS]>,
163    /// Whether each node is on the stack of open elements, so asking is
164    /// one lookup however deep the stack is.
165    on_stack: Vec<bool>,
166    /// Whether to record where nodes were written ([`Options::spans`]),
167    /// and where the token being handled was, from [`Sink::position`].
168    spans: bool,
169    at: [u32; 2],
170    /// Where the table text in `pending` was written.
171    pending_at: [u32; 2],
172    /// The name of the end tag being handled, while `spans` is on and
173    /// `closing` says one is: an element of that name it closes ends
174    /// there.
175    closing_name: String,
176    closing: bool,
177    /// Each element's [`signature`](Self::signature), 0 until it's
178    /// worked out.
179    sigs: Vec<u64>,
180    /// Whether to collect parse errors ([`Options::errors`]), and those
181    /// found so far, by offset into the preprocessed source.
182    errors: bool,
183    errors_found: Vec<(&'static str, u32)>,
184    /// Whether the start tag being handled may close itself, as a void
185    /// element or a foreign one can.
186    acknowledged: bool,
187    /// The document's "allow declarative shadow roots", from
188    /// [`Options::declarative_shadow_roots`].
189    shadow_roots: bool,
190    /// The templates that made shadow roots, kept off the tree, whose
191    /// contents are those roots while they're parsed.
192    shadow_templates: Vec<NodeId>,
193}
194
195/// How many counters [`TreeBuilder::names`] has.
196const NAME_SLOTS: usize = 1024;
197
198/// FNV-1a over `name` in ASCII lower case, and whether it's an HTML
199/// element's: a slot in [`TreeBuilder::names`], found without allocating.
200fn name_key(html: bool, name: &str) -> usize {
201    let mut h: u64 = if html {
202        0xcbf2_9ce4_8422_2325
203    } else {
204        0x8422_2325_cbf2_9ce4
205    };
206    for b in name.bytes() {
207        h ^= u64::from(b.to_ascii_lowercase());
208        h = h.wrapping_mul(0x0100_0000_01b3);
209    }
210    (h ^ (h >> 32)) as usize % NAME_SLOTS
211}
212
213fn is_space(c: u8) -> bool {
214    matches!(c, b'\t' | b'\n' | b'\x0C' | b'\r' | b' ')
215}
216
217/// The leading whitespace of `s`, and the rest.
218fn is_space_char(c: char) -> bool {
219    matches!(c, '\t' | '\n' | '\x0C' | '\r' | ' ')
220}
221
222/// The runs of whitespace in `s`, as slices of it.
223fn space_runs(s: &str) -> impl Iterator<Item = &str> {
224    s.split(|c: char| !is_space_char(c))
225        .filter(|r| !r.is_empty())
226}
227
228fn split_space(s: &str) -> (&str, &str) {
229    let n = s.bytes().take_while(|&b| is_space(b)).count();
230    s.split_at(n)
231}
232
233fn all_space(s: &str) -> bool {
234    s.bytes().all(is_space)
235}
236
237fn special(o: Open) -> bool {
238    use Tag::*;
239    match o.ns {
240        Ns::Html => matches!(
241            o.tag,
242            Address
243                | Applet
244                | Area
245                | Article
246                | Aside
247                | Base
248                | Basefont
249                | Bgsound
250                | Blockquote
251                | Body
252                | Br
253                | Button
254                | Caption
255                | Center
256                | Col
257                | Colgroup
258                | Dd
259                | Details
260                | Dir
261                | Div
262                | Dl
263                | Dt
264                | Embed
265                | Fieldset
266                | Figcaption
267                | Figure
268                | Footer
269                | Form
270                | Frame
271                | Frameset
272                | H1
273                | H2
274                | H3
275                | H4
276                | H5
277                | H6
278                | Head
279                | Header
280                | Hgroup
281                | Hr
282                | Html
283                | Iframe
284                | Img
285                | Input
286                | Keygen
287                | Li
288                | Link
289                | Listing
290                | Main
291                | Marquee
292                | Menu
293                | Meta
294                | Nav
295                | Noembed
296                | Noframes
297                | Noscript
298                | Object
299                | Ol
300                | P
301                | Param
302                | Plaintext
303                | Pre
304                | Script
305                | Search
306                | Section
307                | Select
308                | Source
309                | Style
310                | Summary
311                | Table
312                | Tbody
313                | Td
314                | Template
315                | Textarea
316                | Tfoot
317                | Th
318                | Thead
319                | Title
320                | Tr
321                | Track
322                | Ul
323                | Wbr
324                | Xmp
325        ),
326        Ns::MathMl => matches!(o.tag, Mi | Mo | Mn | Ms | Mtext | AnnotationXml),
327        Ns::Svg => matches!(o.tag, ForeignObject | Desc | Title),
328        // The HTML parser never makes XML elements.
329        Ns::Xml => false,
330    }
331}
332
333fn scope_boundary(o: Open, scope: Scope) -> bool {
334    use Tag::*;
335    let base = || match o.ns {
336        Ns::Html => matches!(
337            o.tag,
338            Applet | Caption | Html | Table | Td | Th | Marquee | Object | Select | Template
339        ),
340        Ns::MathMl => matches!(o.tag, Mi | Mo | Mn | Ms | Mtext | AnnotationXml),
341        Ns::Svg => matches!(o.tag, ForeignObject | Desc | Title),
342        // The HTML parser never makes XML elements.
343        Ns::Xml => false,
344    };
345    match scope {
346        Scope::Default => base(),
347        Scope::ListItem => base() || o.is(Ol) || o.is(Ul),
348        Scope::Button => base() || o.is(Button),
349        Scope::Table => o.is(Html) || o.is(Table) || o.is(Template),
350    }
351}
352
353const HEADINGS: [Tag; 6] = [Tag::H1, Tag::H2, Tag::H3, Tag::H4, Tag::H5, Tag::H6];
354
355fn heading(tag: Tag) -> bool {
356    HEADINGS.contains(&tag)
357}
358
359fn implied(tag: Tag) -> bool {
360    use Tag::*;
361    matches!(
362        tag,
363        Dd | Dt | Li | Optgroup | Option | P | Rb | Rp | Rt | Rtc
364    )
365}
366
367fn mathml_text_integration(o: Open) -> bool {
368    o.ns == Ns::MathMl && matches!(o.tag, Tag::Mi | Tag::Mo | Tag::Mn | Tag::Ms | Tag::Mtext)
369}
370
371/// SVG element names whose case the parser fixes: as tokenized, and as
372/// the element has it.
373pub(crate) static SVG_TAG_NAMES: [(&str, &str); 37] = [
374    ("altglyph", "altGlyph"),
375    ("altglyphdef", "altGlyphDef"),
376    ("altglyphitem", "altGlyphItem"),
377    ("animatecolor", "animateColor"),
378    ("animatemotion", "animateMotion"),
379    ("animatetransform", "animateTransform"),
380    ("clippath", "clipPath"),
381    ("feblend", "feBlend"),
382    ("fecolormatrix", "feColorMatrix"),
383    ("fecomponenttransfer", "feComponentTransfer"),
384    ("fecomposite", "feComposite"),
385    ("feconvolvematrix", "feConvolveMatrix"),
386    ("fediffuselighting", "feDiffuseLighting"),
387    ("fedisplacementmap", "feDisplacementMap"),
388    ("fedistantlight", "feDistantLight"),
389    ("fedropshadow", "feDropShadow"),
390    ("feflood", "feFlood"),
391    ("fefunca", "feFuncA"),
392    ("fefuncb", "feFuncB"),
393    ("fefuncg", "feFuncG"),
394    ("fefuncr", "feFuncR"),
395    ("fegaussianblur", "feGaussianBlur"),
396    ("feimage", "feImage"),
397    ("femerge", "feMerge"),
398    ("femergenode", "feMergeNode"),
399    ("femorphology", "feMorphology"),
400    ("feoffset", "feOffset"),
401    ("fepointlight", "fePointLight"),
402    ("fespecularlighting", "feSpecularLighting"),
403    ("fespotlight", "feSpotLight"),
404    ("fetile", "feTile"),
405    ("feturbulence", "feTurbulence"),
406    ("foreignobject", "foreignObject"),
407    ("glyphref", "glyphRef"),
408    ("lineargradient", "linearGradient"),
409    ("radialgradient", "radialGradient"),
410    ("textpath", "textPath"),
411];
412
413pub(crate) fn svg_tag_name(name: &str) -> Option<u8> {
414    SVG_TAG_NAMES
415        .iter()
416        .position(|(lower, _)| *lower == name)
417        .map(|i| i as u8)
418}
419
420/// SVG attribute names whose case the parser fixes.
421pub(crate) fn svg_attr_name(name: &str) -> Option<&'static str> {
422    Some(match name {
423        "attributename" => "attributeName",
424        "attributetype" => "attributeType",
425        "basefrequency" => "baseFrequency",
426        "baseprofile" => "baseProfile",
427        "calcmode" => "calcMode",
428        "clippathunits" => "clipPathUnits",
429        "diffuseconstant" => "diffuseConstant",
430        "edgemode" => "edgeMode",
431        "filterunits" => "filterUnits",
432        "glyphref" => "glyphRef",
433        "gradienttransform" => "gradientTransform",
434        "gradientunits" => "gradientUnits",
435        "kernelmatrix" => "kernelMatrix",
436        "kernelunitlength" => "kernelUnitLength",
437        "keypoints" => "keyPoints",
438        "keysplines" => "keySplines",
439        "keytimes" => "keyTimes",
440        "lengthadjust" => "lengthAdjust",
441        "limitingconeangle" => "limitingConeAngle",
442        "markerheight" => "markerHeight",
443        "markerunits" => "markerUnits",
444        "markerwidth" => "markerWidth",
445        "maskcontentunits" => "maskContentUnits",
446        "maskunits" => "maskUnits",
447        "numoctaves" => "numOctaves",
448        "pathlength" => "pathLength",
449        "patterncontentunits" => "patternContentUnits",
450        "patterntransform" => "patternTransform",
451        "patternunits" => "patternUnits",
452        "pointsatx" => "pointsAtX",
453        "pointsaty" => "pointsAtY",
454        "pointsatz" => "pointsAtZ",
455        "preservealpha" => "preserveAlpha",
456        "preserveaspectratio" => "preserveAspectRatio",
457        "primitiveunits" => "primitiveUnits",
458        "refx" => "refX",
459        "refy" => "refY",
460        "repeatcount" => "repeatCount",
461        "repeatdur" => "repeatDur",
462        "requiredextensions" => "requiredExtensions",
463        "requiredfeatures" => "requiredFeatures",
464        "specularconstant" => "specularConstant",
465        "specularexponent" => "specularExponent",
466        "spreadmethod" => "spreadMethod",
467        "startoffset" => "startOffset",
468        "stddeviation" => "stdDeviation",
469        "stitchtiles" => "stitchTiles",
470        "surfacescale" => "surfaceScale",
471        "systemlanguage" => "systemLanguage",
472        "tablevalues" => "tableValues",
473        "targetx" => "targetX",
474        "targety" => "targetY",
475        "textlength" => "textLength",
476        "viewbox" => "viewBox",
477        "viewtarget" => "viewTarget",
478        "xchannelselector" => "xChannelSelector",
479        "ychannelselector" => "yChannelSelector",
480        "zoomandpan" => "zoomAndPan",
481        _ => return None,
482    })
483}
484
485/// The spec's "adjust foreign attributes": a namespace and local name.
486fn foreign_attr(name: &str) -> Option<(AttrNs, &'static str)> {
487    Some(match name {
488        "xlink:actuate" => (AttrNs::XLink, "actuate"),
489        "xlink:arcrole" => (AttrNs::XLink, "arcrole"),
490        "xlink:href" => (AttrNs::XLink, "href"),
491        "xlink:role" => (AttrNs::XLink, "role"),
492        "xlink:show" => (AttrNs::XLink, "show"),
493        "xlink:title" => (AttrNs::XLink, "title"),
494        "xlink:type" => (AttrNs::XLink, "type"),
495        "xml:lang" => (AttrNs::Xml, "lang"),
496        "xml:space" => (AttrNs::Xml, "space"),
497        "xmlns" => (AttrNs::Xmlns, "xmlns"),
498        "xmlns:xlink" => (AttrNs::Xmlns, "xlink"),
499        _ => return None,
500    })
501}
502
503fn quirky_public_id(public: &str) -> bool {
504    const STARTS: &[&str] = &[
505        "+//silmaril//dtd html pro v0r11 19970101//",
506        "-//as//dtd html 3.0 aswedit + extensions//",
507        "-//advasoft ltd//dtd html 3.0 aswedit + extensions//",
508        "-//ietf//dtd html 2.0 level 1//",
509        "-//ietf//dtd html 2.0 level 2//",
510        "-//ietf//dtd html 2.0 strict level 1//",
511        "-//ietf//dtd html 2.0 strict level 2//",
512        "-//ietf//dtd html 2.0 strict//",
513        "-//ietf//dtd html 2.0//",
514        "-//ietf//dtd html 2.1e//",
515        "-//ietf//dtd html 3.0//",
516        "-//ietf//dtd html 3.2 final//",
517        "-//ietf//dtd html 3.2//",
518        "-//ietf//dtd html 3//",
519        "-//ietf//dtd html level 0//",
520        "-//ietf//dtd html level 1//",
521        "-//ietf//dtd html level 2//",
522        "-//ietf//dtd html level 3//",
523        "-//ietf//dtd html strict level 0//",
524        "-//ietf//dtd html strict level 1//",
525        "-//ietf//dtd html strict level 2//",
526        "-//ietf//dtd html strict level 3//",
527        "-//ietf//dtd html strict//",
528        "-//ietf//dtd html//",
529        "-//metrius//dtd metrius presentational//",
530        "-//microsoft//dtd internet explorer 2.0 html strict//",
531        "-//microsoft//dtd internet explorer 2.0 html//",
532        "-//microsoft//dtd internet explorer 2.0 tables//",
533        "-//microsoft//dtd internet explorer 3.0 html strict//",
534        "-//microsoft//dtd internet explorer 3.0 html//",
535        "-//microsoft//dtd internet explorer 3.0 tables//",
536        "-//netscape comm. corp.//dtd html//",
537        "-//netscape comm. corp.//dtd strict html//",
538        "-//o'reilly and associates//dtd html 2.0//",
539        "-//o'reilly and associates//dtd html extended 1.0//",
540        "-//o'reilly and associates//dtd html extended relaxed 1.0//",
541        "-//sq//dtd html 2.0 hotmetal + extensions//",
542        "-//softquad software//dtd hotmetal pro 6.0::19990601::extensions to html 4.0//",
543        "-//softquad//dtd hotmetal pro 4.0::19971010::extensions to html 4.0//",
544        "-//spyglass//dtd html 2.0 extended//",
545        "-//sun microsystems corp.//dtd hotjava html//",
546        "-//sun microsystems corp.//dtd hotjava strict html//",
547        "-//w3c//dtd html 3 1995-03-24//",
548        "-//w3c//dtd html 3.2 draft//",
549        "-//w3c//dtd html 3.2 final//",
550        "-//w3c//dtd html 3.2//",
551        "-//w3c//dtd html 3.2s draft//",
552        "-//w3c//dtd html 4.0 frameset//",
553        "-//w3c//dtd html 4.0 transitional//",
554        "-//w3c//dtd html experimental 19960712//",
555        "-//w3c//dtd html experimental 970421//",
556        "-//w3c//dtd w3 html//",
557        "-//w3o//dtd w3 html 3.0//",
558        "-//webtechs//dtd mozilla html 2.0//",
559        "-//webtechs//dtd mozilla html//",
560    ];
561    STARTS.iter().any(|s| starts_with_ci(public, s))
562}
563
564fn starts_with_ci(s: &str, prefix: &str) -> bool {
565    s.len() >= prefix.len() && s.as_bytes()[..prefix.len()].eq_ignore_ascii_case(prefix.as_bytes())
566}
567
568fn doctype_quirks(d: &Doctype<'_>) -> Quirks {
569    let public = d.public_id.unwrap_or("");
570    let system = d.system_id;
571    let eq = |a: &str, b: &str| a.eq_ignore_ascii_case(b);
572    if d.force_quirks
573        || d.name != Some("html")
574        || d.public_id.is_some_and(|p| {
575            eq(p, "-//W3O//DTD W3 HTML Strict 3.0//EN//")
576                || eq(p, "-/W3C/DTD HTML 4.0 Transitional/EN")
577                || eq(p, "HTML")
578        })
579        || system.is_some_and(|s| {
580            eq(
581                s,
582                "http://www.ibm.com/data/dtd/v11/ibmxhtml1-transitional.dtd",
583            )
584        })
585        || d.public_id.is_some_and(quirky_public_id)
586        || (system.is_none()
587            && (starts_with_ci(public, "-//W3C//DTD HTML 4.01 Frameset//")
588                || starts_with_ci(public, "-//W3C//DTD HTML 4.01 Transitional//")))
589    {
590        Quirks::Quirks
591    } else if starts_with_ci(public, "-//W3C//DTD XHTML 1.0 Frameset//")
592        || starts_with_ci(public, "-//W3C//DTD XHTML 1.0 Transitional//")
593        || (system.is_some()
594            && (starts_with_ci(public, "-//W3C//DTD HTML 4.01 Frameset//")
595                || starts_with_ci(public, "-//W3C//DTD HTML 4.01 Transitional//")))
596    {
597        Quirks::Limited
598    } else {
599        Quirks::No
600    }
601}
602
603impl TreeBuilder {
604    pub(crate) fn new(capacity: usize, scripting: bool) -> TreeBuilder {
605        TreeBuilder {
606            doc: Document::new(Data::Document, capacity),
607            max_depth: None,
608            open: Vec::with_capacity(64),
609            active: Vec::new(),
610            mode: Mode::Initial,
611            original: Mode::Initial,
612            template_modes: Vec::new(),
613            head: NONE,
614            form: NONE,
615            frameset_ok: true,
616            foster: false,
617            scripting,
618            context: None,
619            pending: String::new(),
620            pending_text: false,
621            skip_newline: false,
622            switch: None,
623            done: false,
624            eof_again: false,
625            selected: HashMap::new(),
626            option_select: HashMap::new(),
627            merged: HashMap::new(),
628            counts: [0; 256],
629            foreign_boundaries: 0,
630            p_in_scope: Vec::with_capacity(64),
631            names: Box::new([0; NAME_SLOTS]),
632            on_stack: vec![false; capacity / 24 + 1024],
633            spans: false,
634            at: [0; 2],
635            pending_at: [0; 2],
636            closing_name: String::new(),
637            closing: false,
638            sigs: Vec::new(),
639            errors: false,
640            errors_found: Vec::new(),
641            acknowledged: false,
642            shadow_roots: false,
643            shadow_templates: Vec::new(),
644        }
645    }
646
647    /// A tree-construction parse error in the token being handled.
648    #[cold]
649    fn err(&mut self, code: &'static str) {
650        if self.errors {
651            self.errors_found.push((code, self.at[0]));
652        }
653    }
654
655    /// A parse error at byte `i` of text `s`: there, when `s` is still a
656    /// slice of the source, so the place doesn't depend on how the text
657    /// was cut into runs; else where the token being handled was.
658    #[cold]
659    fn err_in(&mut self, code: &'static str, s: &str, i: usize) {
660        if self.errors {
661            let at = self
662                .doc
663                .source_offset(s)
664                .map_or(self.at[0], |o| (o + i) as u32);
665            self.errors_found.push((code, at));
666        }
667    }
668
669    /// Where text `s` was written: exactly, when it's a slice of the
670    /// source, even part of a run; else where the token being handled
671    /// was.
672    fn text_at(&self, s: &str) -> [u32; 2] {
673        match self.doc.source_offset(s) {
674            Some(o) => [o as u32, (o + s.len()) as u32],
675            None => self.at,
676        }
677    }
678
679    /// The errors found, in the document's list in source order, with
680    /// their offsets in the input as given and their lines and columns.
681    fn finish_errors(&mut self) {
682        if !self.errors {
683            return;
684        }
685        let mut found = std::mem::take(&mut self.errors_found);
686        // Stable, so errors at one offset stay in the order found.
687        found.sort_by_key(|&(_, at)| at);
688        let src = self.doc.src.as_bytes();
689        let (mut line, mut column, mut at) = (1, 1, 0);
690        let mut errors = Vec::with_capacity(found.len());
691        for (code, offset) in found {
692            let offset = (offset as usize).min(src.len());
693            // One pass over the source for them all.
694            let from = at;
695            for i in memchr::memchr_iter(b'\n', &src[from..offset]) {
696                line += 1;
697                column = 1;
698                at = from + i + 1;
699            }
700            column += src[at..offset]
701                .iter()
702                .filter(|&&b| (b as i8) >= -0x40)
703                .count();
704            at = offset;
705            let original = self
706                .doc
707                .positions
708                .as_deref()
709                .map_or(offset, |p| p.original(offset as u32));
710            errors.push(crate::SyntaxError {
711                code,
712                offset: original,
713                line,
714                column,
715            });
716        }
717        self.doc.errors = errors;
718    }
719
720    /// Sets up the fragment case with a context element, and returns the
721    /// mode the tokenizer starts in.
722    pub(crate) fn fragment(&mut self, ns: Ns, name: &str) -> Option<TextMode> {
723        let tag = Tag::from_name(&name.to_ascii_lowercase());
724        let context = self.create(
725            &Start {
726                tag,
727                name,
728                attrs: None,
729                self_closing: false,
730            },
731            ns,
732        );
733        self.context = Some(Open {
734            id: context,
735            ns,
736            tag,
737        });
738        let root = self.create(&Start::bare(Tag::Html), Ns::Html);
739        self.doc.insert(0, root, NONE);
740        self.push_open(Open {
741            id: root,
742            ns: Ns::Html,
743            tag: Tag::Html,
744        });
745        if ns == Ns::Html && tag == Tag::Template {
746            self.template_modes.push(Mode::InTemplate);
747        }
748        if ns == Ns::Html && tag == Tag::Form {
749            self.form = context;
750        }
751        self.reset_mode();
752        if ns != Ns::Html {
753            return None;
754        }
755        match tag {
756            Tag::Title | Tag::Textarea => Some(TextMode::Rcdata),
757            Tag::Style | Tag::Xmp | Tag::Iframe | Tag::Noembed | Tag::Noframes => {
758                Some(TextMode::Rawtext)
759            }
760            Tag::Script => Some(TextMode::ScriptData),
761            Tag::Noscript if self.scripting => Some(TextMode::Rawtext),
762            Tag::Plaintext => Some(TextMode::Plaintext),
763            _ => None,
764        }
765    }
766
767    /// After a fragment parse: the html element's children become the
768    /// document's, and the document becomes a fragment.
769    pub(crate) fn finish_fragment(&mut self) {
770        let root = self
771            .doc
772            .first_child(0)
773            .expect("the fragment's html element");
774        self.doc.detach(root);
775        while let Some(child) = self.doc.first_child(root) {
776            self.doc.detach(child);
777            self.doc.insert(0, child, NONE);
778        }
779        self.doc.nodes[0].data = Data::Fragment;
780    }
781
782    // ---- the stack and the list -------------------------------------------
783
784    fn current(&self) -> Open {
785        *self.open.last().expect("an open element")
786    }
787
788    fn adjusted_current(&self) -> Option<Open> {
789        match self.context {
790            Some(c) if self.open.len() == 1 => Some(c),
791            _ => self.open.last().copied(),
792        }
793    }
794
795    fn mark(&mut self, id: NodeId, on: bool) {
796        let i = id as usize;
797        if let Some(flag) = self.on_stack.get_mut(i) {
798            *flag = on;
799        } else {
800            self.on_stack.resize(i * 2 + 1024, false);
801            self.on_stack[i] = on;
802        }
803    }
804
805    /// Counts `o` as opened (`by` 1) or closed (`by` -1).
806    fn count(&mut self, o: Open, by: i32) {
807        debug_assert_eq!(
808            self.open_contains(o.id),
809            by < 0,
810            "node {} {} the stack of open elements twice",
811            o.id,
812            if by < 0 { "leaves" } else { "joins" }
813        );
814        debug_assert!(
815            self.element_at(o.id) == Some(o),
816            "the stack's entry for node {} isn't its element",
817            o.id
818        );
819        self.mark(o.id, by > 0);
820        if by < 0 && self.closing {
821            self.closed_by_end_tag(o.id);
822        }
823        if o.ns == Ns::Html && o.tag != Tag::Other {
824            debug_assert!(
825                by > 0 || self.counts[o.tag as usize] > 0,
826                "{:?} counted below 0",
827                o.tag
828            );
829            self.counts[o.tag as usize] = self.counts[o.tag as usize].wrapping_add_signed(by);
830            return;
831        }
832        if scope_boundary(o, Scope::Default) {
833            self.foreign_boundaries = self.foreign_boundaries.wrapping_add_signed(by);
834        }
835        let Some(name) = self.doc.element(o.id).map(|e| self.doc.element_name(e)) else {
836            return;
837        };
838        let n = &mut self.names[name_key(o.ns == Ns::Html, name)];
839        debug_assert!(by > 0 || *n > 0, "{name} counted below 0");
840        *n = n.wrapping_add_signed(by);
841    }
842
843    /// How many open elements are named `name`, HTML ones of no known tag
844    /// (`html`) or foreign ones; or more, when names share a key.
845    fn open_named(&self, html: bool, name: &str) -> u32 {
846        self.names[name_key(html, name)]
847    }
848
849    fn push_open(&mut self, o: Open) {
850        self.count(o, 1);
851        self.open.push(o);
852        let below = self.p_in_scope.last().copied().unwrap_or(false);
853        self.p_in_scope
854            .push(o.is(Tag::P) || below && !scope_boundary(o, Scope::Button));
855    }
856
857    fn remove_open_at(&mut self, i: usize) -> Open {
858        let o = self.open.remove(i);
859        self.count(o, -1);
860        self.p_in_scope_from(i);
861        o
862    }
863
864    fn insert_open_at(&mut self, i: usize, o: Open) {
865        self.count(o, 1);
866        self.open.insert(i, o);
867        self.p_in_scope_from(i);
868    }
869
870    /// `p_in_scope` again from entry `i` up, after the stack changed there.
871    fn p_in_scope_from(&mut self, i: usize) {
872        self.p_in_scope.truncate(i);
873        let mut below = self.p_in_scope.last().copied().unwrap_or(false);
874        for &o in &self.open[i..] {
875            below = o.is(Tag::P) || below && !scope_boundary(o, Scope::Button);
876            self.p_in_scope.push(below);
877        }
878    }
879
880    fn open_count(&self, tag: Tag) -> u32 {
881        self.counts[tag as usize]
882    }
883
884    fn pop(&mut self) -> Option<Open> {
885        let o = self.open.pop()?;
886        self.p_in_scope.pop();
887        self.count(o, -1);
888        if o.is(Tag::Option) {
889            self.option_popped(o.id);
890        }
891        Some(o)
892    }
893
894    fn truncate_open(&mut self, len: usize) {
895        while self.open.len() > len {
896            self.pop();
897        }
898    }
899
900    fn template_open(&self) -> bool {
901        self.open_count(Tag::Template) > 0
902    }
903
904    /// The spec's "parsing template contents", which the form element
905    /// pointer ignores.
906    fn in_template_contents(&self) -> bool {
907        self.template_open() || self.context.is_some_and(|c| c.is(Tag::Template))
908    }
909
910    /// How many open elements end `scope`, not counting the root `html`.
911    fn boundaries_above_root(&self, scope: Scope) -> u32 {
912        use Tag::*;
913        let base = self.foreign_boundaries
914            + [
915                Applet, Caption, Table, Td, Th, Marquee, Object, Select, Template,
916            ]
917            .iter()
918            .map(|&t| self.open_count(t))
919            .sum::<u32>();
920        match scope {
921            Scope::Default => base,
922            Scope::ListItem => base + self.open_count(Ol) + self.open_count(Ul),
923            Scope::Button => base + self.open_count(Button),
924            Scope::Table => self.open_count(Table) + self.open_count(Template),
925        }
926    }
927
928    fn in_scope(&self, tag: Tag, scope: Scope) -> bool {
929        if tag != Tag::Other && self.open_count(tag) == 0 {
930            return false;
931        }
932        // `body` and `html` are at the bottom of the stack, so they're in
933        // scope when nothing above the root ends it, without a walk down
934        // to them. (Other elements are found near the top, as a rule.)
935        if matches!(tag, Tag::Body | Tag::Html) {
936            return self.boundaries_above_root(scope) == 0;
937        }
938        self.in_scope_walk(tag, scope)
939    }
940
941    fn in_scope_walk(&self, tag: Tag, scope: Scope) -> bool {
942        let walk = || {
943            for &o in self.open.iter().rev() {
944                if o.is(tag) {
945                    return true;
946                }
947                if scope_boundary(o, scope) {
948                    return false;
949                }
950            }
951            false
952        };
953        if tag == Tag::P && scope == Scope::Button {
954            let known = self.p_in_scope.last().copied().unwrap_or(false);
955            debug_assert_eq!(known, walk(), "p_in_scope is out of step");
956            return known;
957        }
958        walk()
959    }
960
961    /// Whether one of `tags` is in scope, as [`Self::in_scope`] for each.
962    fn in_scope_any(&self, tags: &[Tag], scope: Scope) -> bool {
963        if tags.iter().all(|&t| self.open_count(t) == 0) {
964            return false;
965        }
966        for &o in self.open.iter().rev() {
967            if o.ns == Ns::Html && tags.contains(&o.tag) {
968                return true;
969            }
970            if scope_boundary(o, scope) {
971                return false;
972            }
973        }
974        false
975    }
976
977    fn node_in_scope(&self, id: NodeId) -> bool {
978        for &o in self.open.iter().rev() {
979            if o.id == id {
980                return true;
981            }
982            if scope_boundary(o, Scope::Default) {
983                return false;
984            }
985        }
986        false
987    }
988
989    fn pop_until(&mut self, tag: Tag) {
990        while let Some(o) = self.pop() {
991            if o.is(tag) {
992                break;
993            }
994        }
995    }
996
997    fn pop_until_where(&mut self, f: impl Fn(Tag) -> bool) {
998        while let Some(o) = self.pop() {
999            if o.ns == Ns::Html && f(o.tag) {
1000                break;
1001            }
1002        }
1003    }
1004
1005    fn remove_open(&mut self, id: NodeId) {
1006        if let Some(i) = self.open.iter().rposition(|o| o.id == id) {
1007            self.remove_open_at(i);
1008        }
1009    }
1010
1011    fn generate_implied(&mut self, except: Option<Tag>) {
1012        while let Some(&o) = self.open.last() {
1013            if o.ns == Ns::Html && implied(o.tag) && Some(o.tag) != except {
1014                self.pop();
1015            } else {
1016                break;
1017            }
1018        }
1019    }
1020
1021    fn generate_implied_thoroughly(&mut self) {
1022        use Tag::*;
1023        while let Some(&o) = self.open.last() {
1024            if o.ns == Ns::Html
1025                && (implied(o.tag)
1026                    || matches!(
1027                        o.tag,
1028                        Caption | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
1029                    ))
1030            {
1031                self.pop();
1032            } else {
1033                break;
1034            }
1035        }
1036    }
1037
1038    fn close_p(&mut self) {
1039        self.generate_implied(Some(Tag::P));
1040        if !self.current().is(Tag::P) {
1041            self.err("unexpected-end-tag");
1042        }
1043        self.pop_until(Tag::P);
1044    }
1045
1046    fn close_p_in_button_scope(&mut self) {
1047        if self.in_scope(Tag::P, Scope::Button) {
1048            self.close_p();
1049        }
1050    }
1051
1052    fn clear_to_table_context(&mut self) {
1053        while !matches!(self.current().tag, Tag::Table | Tag::Template | Tag::Html)
1054            || self.current().ns != Ns::Html
1055        {
1056            self.pop();
1057        }
1058    }
1059
1060    fn clear_to_table_body_context(&mut self) {
1061        use Tag::*;
1062        while !matches!(self.current().tag, Tbody | Tfoot | Thead | Template | Html)
1063            || self.current().ns != Ns::Html
1064        {
1065            self.pop();
1066        }
1067    }
1068
1069    fn clear_to_table_row_context(&mut self) {
1070        while !matches!(self.current().tag, Tag::Tr | Tag::Template | Tag::Html)
1071            || self.current().ns != Ns::Html
1072        {
1073            self.pop();
1074        }
1075    }
1076
1077    fn reset_mode(&mut self) {
1078        use Tag::*;
1079        // With none of the elements that decide the mode open but `body`
1080        // or `frameset`, the walk would pass everything down to that one.
1081        if self.context.is_none()
1082            && [
1083                Td, Th, Tr, Tbody, Thead, Tfoot, Caption, Colgroup, Table, Template, Head,
1084            ]
1085            .iter()
1086            .all(|&t| self.open_count(t) == 0)
1087        {
1088            if self.open_count(Body) > 0 {
1089                self.mode = Mode::InBody;
1090                return;
1091            }
1092            if self.open_count(Frameset) > 0 {
1093                self.mode = Mode::InFrameset;
1094                return;
1095            }
1096        }
1097        for i in (0..self.open.len()).rev() {
1098            let last = i == 0;
1099            let mut node = self.open[i];
1100            if last && let Some(c) = self.context {
1101                node = c;
1102            }
1103            if node.ns != Ns::Html {
1104                if last {
1105                    self.mode = Mode::InBody;
1106                    return;
1107                }
1108                continue;
1109            }
1110            self.mode = match node.tag {
1111                Td | Th if !last => Mode::InCell,
1112                Tr => Mode::InRow,
1113                Tbody | Thead | Tfoot => Mode::InTableBody,
1114                Caption => Mode::InCaption,
1115                Colgroup => Mode::InColumnGroup,
1116                Table => Mode::InTable,
1117                Template => *self.template_modes.last().unwrap_or(&Mode::InBody),
1118                Head if !last => Mode::InHead,
1119                Body => Mode::InBody,
1120                Frameset => Mode::InFrameset,
1121                Html => {
1122                    if self.head == NONE {
1123                        Mode::BeforeHead
1124                    } else {
1125                        Mode::AfterHead
1126                    }
1127                }
1128                _ if last => Mode::InBody,
1129                _ => continue,
1130            };
1131            return;
1132        }
1133    }
1134
1135    /// Checks the stack of open elements against what's kept beside it:
1136    /// `on_stack` marks exactly the elements on it, `counts` and `names`
1137    /// count them, and each entry's namespace and tag are its element's.
1138    /// Linear in the stack, and in the document when `all` asks for every
1139    /// mark to be checked, so it runs once a piece of input, not once a
1140    /// token.
1141    #[cfg(debug_assertions)]
1142    fn check_stack(&self, all: bool) {
1143        let mut counts = [0u32; 256];
1144        let mut names = vec![0u32; NAME_SLOTS];
1145        for &o in &self.open {
1146            assert!(
1147                self.open_contains(o.id),
1148                "node {} is open but not marked",
1149                o.id
1150            );
1151            assert_eq!(
1152                self.element_at(o.id),
1153                Some(o),
1154                "the stack's entry for {}",
1155                o.id
1156            );
1157            if o.ns == Ns::Html && o.tag != Tag::Other {
1158                counts[o.tag as usize] += 1;
1159            } else if let Some(e) = self.doc.element(o.id) {
1160                names[name_key(o.ns == Ns::Html, self.doc.element_name(e))] += 1;
1161            }
1162        }
1163        assert!(counts == self.counts, "counts disagree with the stack");
1164        assert!(names[..] == self.names[..], "names disagree with the stack");
1165        let foreign = self
1166            .open
1167            .iter()
1168            .filter(|&&o| o.ns != Ns::Html && scope_boundary(o, Scope::Default));
1169        assert_eq!(
1170            foreign.count() as u32,
1171            self.foreign_boundaries,
1172            "scope boundaries"
1173        );
1174        for scope in [Scope::Default, Scope::ListItem, Scope::Button, Scope::Table] {
1175            for tag in [
1176                Tag::Body,
1177                Tag::Html,
1178                Tag::Div,
1179                Tag::P,
1180                Tag::Li,
1181                Tag::Td,
1182                Tag::H1,
1183            ] {
1184                if self.open_count(tag) > 0 {
1185                    assert_eq!(
1186                        self.in_scope(tag, scope),
1187                        self.in_scope_walk(tag, scope),
1188                        "{tag:?} in {scope:?} scope"
1189                    );
1190                }
1191            }
1192        }
1193        if all {
1194            let marked = self.on_stack.iter().filter(|&&on| on).count();
1195            assert_eq!(marked, self.open.len(), "a node is marked open but isn't");
1196        }
1197        // Between the markers, HTML elements only, each once.
1198        let mut since_marker = std::collections::HashSet::new();
1199        for &e in &self.active {
1200            if e == MARKER {
1201                since_marker.clear();
1202                continue;
1203            }
1204            assert!(
1205                self.element_at(e).is_some_and(|o| o.ns == Ns::Html),
1206                "{e} in the list"
1207            );
1208            assert!(since_marker.insert(e), "node {e} in the list twice");
1209        }
1210    }
1211
1212    fn open_contains(&self, id: NodeId) -> bool {
1213        self.on_stack.get(id as usize).copied().unwrap_or(false)
1214    }
1215
1216    fn same_element(&self, a: NodeId, b: NodeId) -> bool {
1217        let (Some(x), Some(y)) = (self.doc.element(a), self.doc.element(b)) else {
1218            return false;
1219        };
1220        if x.ns != y.ns
1221            || x.tag != y.tag
1222            || !(matches!((x.name, y.name), (Name::Tag, Name::Tag))
1223                || self.doc.element_name(x) == self.doc.element_name(y))
1224            || x.attrs.end - x.attrs.start != y.attrs.end - y.attrs.start
1225        {
1226            return false;
1227        }
1228        let ys = &self.doc.attrs[y.attrs.start as usize..y.attrs.end as usize];
1229        self.doc.attrs[x.attrs.start as usize..x.attrs.end as usize]
1230            .iter()
1231            .all(|a| {
1232                ys.iter().any(|b| {
1233                    a.ns == b.ns
1234                        && self.doc.str(a.name) == self.doc.str(b.name)
1235                        && self.doc.str(a.value) == self.doc.str(b.value)
1236                })
1237            })
1238    }
1239
1240    /// A hash of what [`same_element`](Self::same_element) compares, so
1241    /// the Noah's Ark check compares one number per entry and the full
1242    /// check runs only when two agree. Cached: a long list of formatting
1243    /// elements is otherwise compared name by name and attribute by
1244    /// attribute on every push.
1245    #[inline]
1246    fn signature(&mut self, id: NodeId) -> u64 {
1247        match self.sigs.get(id as usize) {
1248            Some(&s) if s != 0 => s,
1249            _ => self.work_out_signature(id),
1250        }
1251    }
1252
1253    #[inline(never)]
1254    fn work_out_signature(&mut self, id: NodeId) -> u64 {
1255        // FNV-1a.
1256        fn mix(h: u64, bytes: &[u8]) -> u64 {
1257            bytes
1258                .iter()
1259                .fold(h, |h, &b| (h ^ b as u64).wrapping_mul(0x100000001b3))
1260        }
1261        const SEED: u64 = 0xcbf29ce484222325;
1262        let e = self.doc.element(id).expect("an element");
1263        let mut h = mix(SEED, &[e.ns as u8, e.tag as u8]);
1264        if !matches!(e.name, Name::Tag) {
1265            h = mix(h, self.doc.element_name(e).as_bytes());
1266        }
1267        // Summed, since attribute order doesn't matter to same_element.
1268        let mut attrs = 0u64;
1269        for a in &self.doc.attrs[e.attrs.start as usize..e.attrs.end as usize] {
1270            let one = mix(SEED, self.doc.str(a.name).as_bytes());
1271            attrs = attrs.wrapping_add(mix(mix(one, &[0]), self.doc.str(a.value).as_bytes()));
1272        }
1273        let h = (h ^ attrs).wrapping_mul(0x100000001b3) | 1;
1274        self.set_signature(id, h);
1275        h
1276    }
1277
1278    fn set_signature(&mut self, id: NodeId, sig: u64) {
1279        let i = id as usize;
1280        if i >= self.sigs.len() {
1281            self.sigs.resize(i * 2 + 1024, 0);
1282        }
1283        self.sigs[i] = sig;
1284    }
1285
1286    fn push_active(&mut self, id: NodeId) {
1287        debug_assert!(
1288            self.element_at(id).is_some_and(|o| o.ns == Ns::Html
1289                && matches!(
1290                    o.tag,
1291                    Tag::A
1292                        | Tag::B
1293                        | Tag::Big
1294                        | Tag::Code
1295                        | Tag::Em
1296                        | Tag::Font
1297                        | Tag::I
1298                        | Tag::Nobr
1299                        | Tag::S
1300                        | Tag::Small
1301                        | Tag::Strike
1302                        | Tag::Strong
1303                        | Tag::Tt
1304                        | Tag::U
1305                )),
1306            "node {id} isn't a formatting element"
1307        );
1308        let sig = self.signature(id);
1309        let (mut same, mut earliest) = (0, 0);
1310        for i in (0..self.active.len()).rev() {
1311            let e = self.active[i];
1312            if e == MARKER {
1313                break;
1314            }
1315            debug_assert!(
1316                e != id,
1317                "node {id} is in the list of formatting elements twice"
1318            );
1319            if self.signature(e) == sig && self.same_element(e, id) {
1320                same += 1;
1321                earliest = i;
1322            }
1323        }
1324        if same >= 3 {
1325            self.active.remove(earliest);
1326        }
1327        self.active.push(id);
1328    }
1329
1330    fn clear_active_to_marker(&mut self) {
1331        while let Some(e) = self.active.pop() {
1332            if e == MARKER {
1333                break;
1334            }
1335        }
1336    }
1337
1338    fn reconstruct(&mut self) {
1339        let Some(&last) = self.active.last() else {
1340            return;
1341        };
1342        if last == MARKER || self.open_contains(last) {
1343            return;
1344        }
1345        let mut i = self.active.len() - 1;
1346        while i > 0 {
1347            let e = self.active[i - 1];
1348            if e == MARKER || self.open_contains(e) {
1349                break;
1350            }
1351            i -= 1;
1352        }
1353        for j in i..self.active.len() {
1354            // Only elements past the last marker are reopened.
1355            debug_assert!(self.active[j] != MARKER, "a marker reopened");
1356            let new = self.clone_element(self.active[j]);
1357            let place = self.place(None);
1358            self.insert_at(place, new);
1359            let e = self.doc.element(new).unwrap();
1360            let (ns, tag) = (e.ns, e.tag);
1361            self.push_open(Open { id: new, ns, tag });
1362            self.active[j] = new;
1363        }
1364    }
1365
1366    // ---- creating and inserting -------------------------------------------
1367
1368    fn clone_element(&mut self, id: NodeId) -> NodeId {
1369        let e = *self.doc.element(id).expect("an element");
1370        let new = self.doc.add(Data::Element(Element {
1371            contents: NONE,
1372            ..e
1373        }));
1374        // Same name and attributes, so the same signature.
1375        if let Some(&sig) = self.sigs.get(id as usize)
1376            && sig != 0
1377        {
1378            self.set_signature(new, sig);
1379        }
1380        new
1381    }
1382
1383    fn create(&mut self, s: &Start<'_>, ns: Ns) -> NodeId {
1384        let name = match ns {
1385            Ns::Svg => match svg_tag_name(s.name) {
1386                Some(fixed) => Name::Svg(fixed),
1387                None if s.tag != Tag::Other => Name::Tag,
1388                None => Name::Span(self.doc.intern(s.name)),
1389            },
1390            _ if s.tag != Tag::Other => Name::Tag,
1391            _ => Name::Span(self.doc.intern(s.name)),
1392        };
1393        let first = self.doc.attrs.len() as u32;
1394        let mut html_integration = false;
1395        for (n, v) in s.attrs() {
1396            let (attr_ns, local) = if ns == Ns::Html {
1397                (AttrNs::None, n)
1398            } else if let Some((attr_ns, _)) = foreign_attr(n) {
1399                // Kept as written (`xlink:href`); attrs() gives the local
1400                // name, attrs_written() this.
1401                (attr_ns, n)
1402            } else {
1403                // Lowercase as tokenized: attrs_written() fixes SVG's and
1404                // MathML's case.
1405                (AttrNs::None, n)
1406            };
1407            if ns == Ns::MathMl
1408                && s.tag == Tag::AnnotationXml
1409                && n == "encoding"
1410                && (v.eq_ignore_ascii_case("text/html")
1411                    || v.eq_ignore_ascii_case("application/xhtml+xml"))
1412            {
1413                html_integration = true;
1414            }
1415            let name = self.doc.intern(local);
1416            let value = self.doc.intern(v);
1417            self.doc.attrs.push(Attr {
1418                ns: attr_ns,
1419                name,
1420                value,
1421            });
1422        }
1423        let contents = if ns == Ns::Html && s.tag == Tag::Template {
1424            self.doc.add(Data::Fragment)
1425        } else {
1426            NONE
1427        };
1428        let id = self.doc.add(Data::Element(Element {
1429            ns,
1430            tag: s.tag,
1431            name,
1432            attrs: Span {
1433                start: first,
1434                end: self.doc.attrs.len() as u32,
1435            },
1436            contents,
1437            html_integration,
1438        }));
1439        // Only an element made from the token itself was written there;
1440        // `Start::bare` makes the ones the parser implies.
1441        if self.spans
1442            && let Some(tag) = s.attrs
1443        {
1444            self.element_written(id, tag, first as usize);
1445        }
1446        id
1447    }
1448
1449    fn element_at(&self, id: NodeId) -> Option<Open> {
1450        self.doc.element(id).map(|e| Open {
1451            id,
1452            ns: e.ns,
1453            tag: e.tag,
1454        })
1455    }
1456
1457    /// The appropriate place for inserting a node: a parent, and the child
1458    /// to insert before ([`NONE`] for last).
1459    fn place(&self, target: Option<NodeId>) -> (NodeId, NodeId) {
1460        use Tag::*;
1461        let mut target = target.unwrap_or_else(|| self.current().id);
1462        let mut before = NONE;
1463        let t = self.element_at(target);
1464        if self.foster
1465            && t.is_some_and(|t| {
1466                t.ns == Ns::Html && matches!(t.tag, Table | Tbody | Tfoot | Thead | Tr)
1467            })
1468        {
1469            let last = self
1470                .open
1471                .iter()
1472                .rposition(|o| o.is(Template) || o.is(Table));
1473            match last {
1474                None => return (self.open[0].id, NONE),
1475                Some(i) if self.open[i].is(Template) => target = self.open[i].id,
1476                Some(i) => {
1477                    let table = self.open[i].id;
1478                    match self.doc.parent(table) {
1479                        Some(parent) => {
1480                            target = parent;
1481                            before = table;
1482                        }
1483                        None => target = self.open[i - 1].id,
1484                    }
1485                }
1486            }
1487        }
1488        if let Some(e) = self.doc.element(target)
1489            && e.ns == Ns::Html
1490            && e.tag == Template
1491        {
1492            return (e.contents, NONE);
1493        }
1494        // Past max_depth, beside the target instead of inside it, as
1495        // Chromium's construction site does. Not when fostering, which has
1496        // already picked a place outside the table, nor at the top.
1497        if before == NONE
1498            && self.max_depth.is_some_and(|max| self.open.len() > max)
1499            && let Some(up) = self.doc.parent(target)
1500        {
1501            return (up, NONE);
1502        }
1503        (target, before)
1504    }
1505
1506    fn insert_at(&mut self, (parent, before): (NodeId, NodeId), node: NodeId) {
1507        if parent == 0
1508            && matches!(self.doc.nodes[0].data, Data::Document)
1509            && self.doc.children(0).any(|c| self.doc.element(c).is_some())
1510        {
1511            return;
1512        }
1513        self.doc.insert(parent, node, before);
1514    }
1515
1516    fn insert_element(&mut self, s: &Start<'_>, ns: Ns) -> NodeId {
1517        let id = self.create(s, ns);
1518        let place = self.place(None);
1519        self.insert_at(place, id);
1520        self.push_open(Open { id, ns, tag: s.tag });
1521        if ns == Ns::Html {
1522            match s.tag {
1523                Tag::Option => self.option_inserted(id, s),
1524                Tag::Selectedcontent => self.selectedcontent_inserted(id),
1525                _ => {}
1526            }
1527        }
1528        id
1529    }
1530
1531    /// Stop parsing: every open element is popped.
1532    fn stop(&mut self) {
1533        self.done = true;
1534        self.truncate_open(0);
1535    }
1536
1537    // ---- declarative shadow roots -----------------------------------------
1538
1539    /// The "in head" steps for a `template` start tag with a valid
1540    /// `shadowrootmode`: the adjusted current node becomes a shadow host,
1541    /// and the template, put on the stack but not in the tree, has the
1542    /// new shadow root as its contents, so what follows is parsed into
1543    /// it. False when the token makes an ordinary template instead: no
1544    /// valid mode, the html element or the fragment's context as the host
1545    /// (which the result doesn't hold), a host that already has a shadow
1546    /// root, or one that can't have one.
1547    #[inline(never)]
1548    fn shadow_template(&mut self, s: &Start<'_>) {
1549        if !self.declarative_shadow_root(s) {
1550            self.insert_html(s);
1551        }
1552    }
1553
1554    fn declarative_shadow_root(&mut self, s: &Start<'_>) -> bool {
1555        let Some(init) = crate::shadow::declared(s.attrs()) else {
1556            return false;
1557        };
1558        let Some(host) = self.adjusted_current() else {
1559            return false;
1560        };
1561        if self.open.first().is_some_and(|o| o.id == host.id)
1562            || self.context.is_some_and(|c| c.id == host.id)
1563            || self.doc.shadow_root(host.id).is_some()
1564        {
1565            return false;
1566        }
1567        let Some(e) = self.doc.element(host.id) else {
1568            return false;
1569        };
1570        if !crate::shadow::valid_host(e.ns, e.tag, self.doc.element_name(e)) {
1571            return false;
1572        }
1573        let template = self.create(s, Ns::Html);
1574        let root = self.doc.add_shadow_root(host.id, init);
1575        if let Data::Element(e) = &mut self.doc.nodes[template as usize].data {
1576            e.contents = root;
1577        }
1578        self.shadow_templates.push(template);
1579        self.push_open(Open {
1580            id: template,
1581            ns: Ns::Html,
1582            tag: Tag::Template,
1583        });
1584        true
1585    }
1586
1587    /// At the end of the parse, the templates that made shadow roots let
1588    /// go of them, so nothing but the hosts lead there.
1589    fn release_shadow_roots(&mut self) {
1590        for t in std::mem::take(&mut self.shadow_templates) {
1591            if let Data::Element(e) = &mut self.doc.nodes[t as usize].data {
1592                e.contents = NONE;
1593            }
1594        }
1595    }
1596
1597    // ---- <select> and <selectedcontent> -----------------------------------
1598
1599    fn html_element(&self, id: NodeId, tag: Tag) -> bool {
1600        self.doc
1601            .element(id)
1602            .is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
1603    }
1604
1605    fn has_attr(&self, id: NodeId, name: &str) -> bool {
1606        self.doc
1607            .attrs(id)
1608            .any(|(ns, n, _)| ns == AttrNs::None && n == name)
1609    }
1610
1611    /// The spec's "nearest ancestor select" of an option.
1612    fn nearest_select(&self, id: NodeId) -> NodeId {
1613        // An option is inserted where the parser is, under open elements,
1614        // so with no select open there is none above it; and the walk
1615        // below would go all the way up to say so.
1616        if self.open_count(Tag::Select) == 0 {
1617            return NONE;
1618        }
1619        let mut optgroup = false;
1620        let mut at = self.doc.parent(id);
1621        while let Some(a) = at {
1622            if let Some(e) = self.doc.element(a)
1623                && e.ns == Ns::Html
1624            {
1625                match e.tag {
1626                    Tag::Datalist | Tag::Hr | Tag::Option => return NONE,
1627                    Tag::Optgroup if optgroup => return NONE,
1628                    Tag::Optgroup => optgroup = true,
1629                    Tag::Select => return a,
1630                    _ => {}
1631                }
1632            }
1633            at = self.doc.parent(a);
1634        }
1635        NONE
1636    }
1637
1638    /// The selectedness setting algorithm, as options arrive in tree
1639    /// order: the last with `selected` wins, else the first enabled one.
1640    // ponytail: assumes options are inserted in tree order, as parsing
1641    // does; one moved by the adoption agency or foster parenting keeps
1642    // its place in this order.
1643    fn option_inserted(&mut self, option: NodeId, s: &Start<'_>) {
1644        let select = self.nearest_select(option);
1645        if select == NONE {
1646            return;
1647        }
1648        self.option_select.insert(option, select);
1649        if self.has_attr(select, "multiple") {
1650            return;
1651        }
1652        let size_one = self
1653            .doc
1654            .attrs(select)
1655            .find(|(ns, n, _)| *ns == AttrNs::None && *n == "size")
1656            .and_then(|(_, _, v)| v.trim().parse::<u32>().ok())
1657            .is_none_or(|n| n <= 1);
1658        let disabled = s.attr("disabled").is_some()
1659            || self.doc.parent(option).is_some_and(|p| {
1660                self.html_element(p, Tag::Optgroup) && self.has_attr(p, "disabled")
1661            });
1662        if s.attr("selected").is_some()
1663            || (!self.selected.contains_key(&select) && size_one && !disabled)
1664        {
1665            self.selected.insert(select, option);
1666        }
1667    }
1668
1669    fn option_popped(&mut self, option: NodeId) {
1670        let Some(&select) = self.option_select.get(&option) else {
1671            return;
1672        };
1673        if self.selected.get(&select) != Some(&option) || self.has_attr(select, "multiple") {
1674            return;
1675        }
1676        for target in self.selectedcontents(select) {
1677            self.clone_children_into(option, target);
1678        }
1679    }
1680
1681    fn selectedcontent_inserted(&mut self, id: NodeId) {
1682        let mut select = NONE;
1683        let mut at = self.doc.parent(id);
1684        while let Some(a) = at {
1685            if self.html_element(a, Tag::Select) {
1686                if select != NONE {
1687                    return;
1688                }
1689                select = a;
1690            } else if self.html_element(a, Tag::Option)
1691                || self.html_element(a, Tag::Selectedcontent)
1692            {
1693                return;
1694            }
1695            at = self.doc.parent(a);
1696        }
1697        if select == NONE || self.has_attr(select, "multiple") {
1698            return;
1699        }
1700        if let Some(&option) = self.selected.get(&select) {
1701            self.clone_children_into(option, id);
1702        }
1703    }
1704
1705    /// The `<selectedcontent>` elements a select updates, in tree order.
1706    fn selectedcontents(&self, select: NodeId) -> Vec<NodeId> {
1707        let mut found = Vec::new();
1708        let mut stack: Vec<NodeId> = self.doc.children(select).collect();
1709        stack.reverse();
1710        while let Some(n) = stack.pop() {
1711            if let Some(e) = self.doc.element(n)
1712                && e.ns == Ns::Html
1713            {
1714                match e.tag {
1715                    Tag::Selectedcontent => {
1716                        found.push(n);
1717                        continue;
1718                    }
1719                    Tag::Option | Tag::Select => continue,
1720                    _ => {}
1721                }
1722            }
1723            let at = stack.len();
1724            stack.extend(self.doc.children(n));
1725            stack[at..].reverse();
1726        }
1727        found
1728    }
1729
1730    fn clone_children_into(&mut self, from: NodeId, to: NodeId) {
1731        while let Some(child) = self.doc.first_child(to) {
1732            self.doc.detach(child);
1733        }
1734        let children: Vec<NodeId> = self.doc.children(from).collect();
1735        for child in children {
1736            let copy = self.deep_clone(child);
1737            self.doc.insert(to, copy, NONE);
1738        }
1739    }
1740
1741    /// Copies `id` and everything under it, in tree order, with a stack
1742    /// of its own: the page decides how deep it goes, and a call per
1743    /// level overflowed the thread's stack.
1744    fn deep_clone(&mut self, id: NodeId) -> NodeId {
1745        let mut root = NONE;
1746        let mut stack = vec![(id, NONE)];
1747        while let Some((from, parent)) = stack.pop() {
1748            let mut data = self.doc.nodes[from as usize].data;
1749            if let Data::Element(e) = &mut data {
1750                e.contents = NONE;
1751            }
1752            let copy = self.doc.add(data);
1753            if parent == NONE {
1754                root = copy;
1755            } else {
1756                self.doc.insert(parent, copy, NONE);
1757            }
1758            let at = stack.len();
1759            stack.extend(self.doc.children(from).map(|c| (c, copy)));
1760            stack[at..].reverse();
1761        }
1762        root
1763    }
1764
1765    fn insert_html(&mut self, s: &Start<'_>) -> NodeId {
1766        self.insert_element(s, Ns::Html)
1767    }
1768
1769    fn insert_void(&mut self, s: &Start<'_>) {
1770        self.acknowledged = true;
1771        self.insert_html(s);
1772        self.pop();
1773    }
1774
1775    fn insert_text(&mut self, text: &str) {
1776        if text.is_empty() {
1777            return;
1778        }
1779        let (parent, before) = self.place(None);
1780        if parent == 0 && matches!(self.doc.nodes[0].data, Data::Document) {
1781            return;
1782        }
1783        let prev = if before == NONE {
1784            self.doc.nodes[parent as usize].last_child
1785        } else {
1786            self.doc.nodes[before as usize].prev
1787        };
1788        if prev != NONE && matches!(self.doc.nodes[prev as usize].data, Data::Text(_)) {
1789            self.doc.append_text(prev, text);
1790            if self.spans {
1791                self.text_written(prev, text, true);
1792            }
1793        } else {
1794            let span = self.doc.intern(text);
1795            let id = self.doc.add(Data::Text(span));
1796            self.doc.insert(parent, id, before);
1797            if self.spans {
1798                self.text_written(id, text, false);
1799            }
1800        }
1801    }
1802
1803    fn insert_comment(&mut self, text: &str, at: Option<(NodeId, NodeId)>) {
1804        let place = at.unwrap_or_else(|| self.place(None));
1805        let span = self.doc.intern(text);
1806        let id = self.doc.add(Data::Comment(span));
1807        self.doc.insert(place.0, id, place.1);
1808        if self.spans {
1809            self.written(id);
1810        }
1811    }
1812
1813    fn insert_pi(&mut self, target: &str, data: &str, at: Option<(NodeId, NodeId)>) {
1814        let place = at.unwrap_or_else(|| self.place(None));
1815        let target = self.doc.intern(target);
1816        let data = self.doc.intern(data);
1817        let id = self.doc.add(Data::ProcessingInstruction { target, data });
1818        self.doc.insert(place.0, id, place.1);
1819        if self.spans {
1820            self.written(id);
1821        }
1822    }
1823
1824    // ---- where nodes were written -----------------------------------------
1825    //
1826    // Each of these runs only with `spans` on, and none is inlined, so the
1827    // parse without them stays as small and fast as it was.
1828
1829    /// Records that `id` came from the token being handled.
1830    #[cold]
1831    fn written(&mut self, id: NodeId) {
1832        if let Some(p) = self.doc.positions.as_deref_mut() {
1833            Positions::set(&mut p.nodes, id as usize, self.at);
1834        }
1835    }
1836
1837    /// Records that element `id` was read from start tag `tag`, and so
1838    /// were its attributes, which start at `first` in the document's list.
1839    #[cold]
1840    fn element_written(&mut self, id: NodeId, tag: &tokenizer::Tag<'_>, first: usize) {
1841        self.written(id);
1842        let Some(p) = self.doc.positions.as_deref_mut() else {
1843            return;
1844        };
1845        for i in 0..tag.attrs().len() {
1846            if let Some(at) = tag.attr_span(i) {
1847                Positions::set(&mut p.attrs, first + i, [at.start as u32, at.end as u32]);
1848            }
1849        }
1850    }
1851
1852    /// An element the end tag being handled closed: that's its end tag
1853    /// when the names match.
1854    #[cold]
1855    fn closed_by_end_tag(&mut self, id: NodeId) {
1856        if self.doc.lower_name(id) == Some(&self.closing_name) {
1857            self.ended(id);
1858        }
1859    }
1860
1861    /// Records that `text` went into text node `id`, as all of it or, when
1862    /// `more`, after what it already had. Text still a slice of the source
1863    /// says exactly where it was, even when the tree builder took only
1864    /// part of a run; anything else (decoded, or table text gathered up)
1865    /// was written where the token being handled was.
1866    #[cold]
1867    fn text_written(&mut self, id: NodeId, text: &str, more: bool) {
1868        let at = match self.doc.source_offset(text) {
1869            Some(o) => [o as u32, (o + text.len()) as u32],
1870            None => self.at,
1871        };
1872        let Some(p) = self.doc.positions.as_deref_mut() else {
1873            return;
1874        };
1875        let at = match p.nodes.get(id as usize) {
1876            Some(&[start, end]) if more && start != u32::MAX => [start.min(at[0]), end.max(at[1])],
1877            // A copy made for `<selectedcontent>` stays unknown.
1878            _ if more => return,
1879            _ => at,
1880        };
1881        Positions::set(&mut p.nodes, id as usize, at);
1882    }
1883
1884    /// Records that the end tag being handled closed element `id`; the
1885    /// first one to do so is its end tag.
1886    #[cold]
1887    fn ended(&mut self, id: NodeId) {
1888        if self.spans
1889            && let Some(p) = self.doc.positions.as_deref_mut()
1890            && p.ends.get(id as usize).is_none_or(|&a| a[0] == u32::MAX)
1891        {
1892            Positions::set(&mut p.ends, id as usize, self.at);
1893        }
1894    }
1895
1896    fn rawtext(&mut self, s: &Start<'_>, mode: TextMode) {
1897        self.insert_html(s);
1898        self.switch = Some(mode);
1899        self.original = self.mode;
1900        self.mode = Mode::Text;
1901    }
1902
1903    /// Adds the token's attributes that `id` doesn't already have, as a
1904    /// second `<html>` or `<body>` does. The names it has are kept in a
1905    /// set, and its attributes move to the end of the list with room to
1906    /// grow: asking every one, or moving them all, on each merge made a
1907    /// page of many such tags cost the square of their attributes.
1908    fn merge_attrs(&mut self, id: NodeId, s: &Start<'_>) {
1909        let Some(e) = self.doc.element(id) else {
1910            return;
1911        };
1912        let old = e.attrs;
1913        let merged = self.merged.entry(id).or_insert_with(|| Merged {
1914            names: self.doc.attrs(id).map(|(_, n, _)| n.to_owned()).collect(),
1915            room: old.end,
1916        });
1917        let mut adds = Vec::new();
1918        for (i, (n, v)) in s.attrs().enumerate() {
1919            // The token has dropped its own duplicates already.
1920            if !merged.names.contains(n) {
1921                merged.names.insert(n.to_owned());
1922                adds.push((i, n, v));
1923            }
1924        }
1925        if adds.is_empty() {
1926            return;
1927        }
1928        let len = self.doc.attrs.len() as u32;
1929        let (have, more) = (old.end - old.start, adds.len() as u32);
1930        let start = if old.end == len || old.end + more <= merged.room {
1931            old.start
1932        } else {
1933            // Moved to the end, with as much room again after them.
1934            self.doc
1935                .attrs
1936                .extend_from_within(old.start as usize..old.end as usize);
1937            let empty = Span { start: 0, end: 0 };
1938            let spare = Attr {
1939                ns: AttrNs::None,
1940                name: empty,
1941                value: empty,
1942            };
1943            let room = have + more;
1944            self.doc.attrs.extend((0..room).map(|_| spare));
1945            merged.room = len + have + room;
1946            // The old ones moved; where they were written goes along.
1947            if self.spans
1948                && let Some(p) = self.doc.positions.as_deref_mut()
1949            {
1950                for k in 0..have as usize {
1951                    let at = p.attrs.get(old.start as usize + k).copied();
1952                    if let Some(at) = at {
1953                        Positions::set(&mut p.attrs, len as usize + k, at);
1954                    }
1955                }
1956            }
1957            len
1958        };
1959        let mut at = start + have;
1960        for (i, n, v) in adds {
1961            let written = s.attrs.and_then(|t| t.attr_span(i));
1962            let attr = Attr {
1963                ns: AttrNs::None,
1964                name: self.doc.intern(n),
1965                value: self.doc.intern(v),
1966            };
1967            if at as usize == self.doc.attrs.len() {
1968                self.doc.attrs.push(attr);
1969            } else {
1970                self.doc.attrs[at as usize] = attr;
1971            }
1972            if self.spans
1973                && let Some(p) = self.doc.positions.as_deref_mut()
1974                && let Some(w) = written
1975            {
1976                Positions::set(&mut p.attrs, at as usize, [w.start as u32, w.end as u32]);
1977            }
1978            at += 1;
1979        }
1980        if let Data::Element(e) = &mut self.doc.nodes[id as usize].data {
1981            e.attrs = Span { start, end: at };
1982        }
1983    }
1984
1985    // ---- the dispatcher ---------------------------------------------------
1986
1987    fn process(&mut self, t: Tok<'_>) {
1988        if self.done {
1989            return;
1990        }
1991        if self.html_rules(&t) {
1992            self.html(t);
1993        } else {
1994            self.foreign(t);
1995        }
1996    }
1997
1998    fn html_rules(&self, t: &Tok<'_>) -> bool {
1999        let Some(a) = self.adjusted_current() else {
2000            return true;
2001        };
2002        if a.ns == Ns::Html {
2003            return true;
2004        }
2005        let html_integration = match a.ns {
2006            Ns::Svg => matches!(a.tag, Tag::ForeignObject | Tag::Desc | Tag::Title),
2007            Ns::MathMl => self.doc.element(a.id).is_some_and(|e| e.html_integration),
2008            Ns::Html | Ns::Xml => false,
2009        };
2010        match t {
2011            Tok::Start(s) => {
2012                (mathml_text_integration(a) && !matches!(s.tag, Tag::Mglyph | Tag::Malignmark))
2013                    || (a.ns == Ns::MathMl && a.tag == Tag::AnnotationXml && s.tag == Tag::Svg)
2014                    || html_integration
2015            }
2016            Tok::Text(_) => mathml_text_integration(a) || html_integration,
2017            Tok::Eof => true,
2018            _ => false,
2019        }
2020    }
2021
2022    fn html(&mut self, t: Tok<'_>) {
2023        match self.mode {
2024            Mode::Initial => self.initial(t),
2025            Mode::BeforeHtml => self.before_html(t),
2026            Mode::BeforeHead => self.before_head(t),
2027            Mode::InHead => self.in_head(t),
2028            Mode::InHeadNoscript => self.in_head_noscript(t),
2029            Mode::AfterHead => self.after_head(t),
2030            Mode::InBody => self.in_body(t),
2031            Mode::Text => self.text(t),
2032            Mode::InTable => self.in_table(t),
2033            Mode::InTableText => self.in_table_text(t),
2034            Mode::InCaption => self.in_caption(t),
2035            Mode::InColumnGroup => self.in_column_group(t),
2036            Mode::InTableBody => self.in_table_body(t),
2037            Mode::InRow => self.in_row(t),
2038            Mode::InCell => self.in_cell(t),
2039            Mode::InTemplate => self.in_template(t),
2040            Mode::AfterBody => self.after_body(t),
2041            Mode::InFrameset => self.in_frameset(t),
2042            Mode::AfterFrameset => self.after_frameset(t),
2043            Mode::AfterAfterBody => self.after_after_body(t),
2044            Mode::AfterAfterFrameset => self.after_after_frameset(t),
2045        }
2046    }
2047
2048    fn reprocess(&mut self, mode: Mode, t: Tok<'_>) {
2049        self.mode = mode;
2050        self.process(t);
2051    }
2052
2053    // ---- the insertion modes ----------------------------------------------
2054
2055    fn initial(&mut self, t: Tok<'_>) {
2056        match t {
2057            Tok::Text(s) => {
2058                let (_, rest) = split_space(s);
2059                if !rest.is_empty() {
2060                    self.err_in("expected-doctype-but-got-chars", rest, 0);
2061                    self.doc.quirks = Quirks::Quirks;
2062                    self.reprocess(Mode::BeforeHtml, Tok::Text(rest));
2063                }
2064            }
2065            Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
2066            Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
2067            Tok::Doctype(d) => {
2068                if d.name != Some("html")
2069                    || d.public_id.is_some()
2070                    || d.system_id.is_some_and(|s| s != "about:legacy-compat")
2071                {
2072                    self.err("unknown-doctype");
2073                }
2074                let name = self.doc.intern(d.name.unwrap_or(""));
2075                let public_id = self.doc.intern(d.public_id.unwrap_or(""));
2076                let system_id = self.doc.intern(d.system_id.unwrap_or(""));
2077                let id = self.doc.add(Data::Doctype {
2078                    name,
2079                    public_id,
2080                    system_id,
2081                });
2082                self.doc.insert(0, id, NONE);
2083                if self.spans {
2084                    self.written(id);
2085                }
2086                self.doc.quirks = doctype_quirks(d);
2087                self.mode = Mode::BeforeHtml;
2088            }
2089            _ => {
2090                self.err(match t {
2091                    Tok::Start(_) => "expected-doctype-but-got-start-tag",
2092                    Tok::End(_) => "expected-doctype-but-got-end-tag",
2093                    _ => "expected-doctype-but-got-eof",
2094                });
2095                self.doc.quirks = Quirks::Quirks;
2096                self.reprocess(Mode::BeforeHtml, t);
2097            }
2098        }
2099    }
2100
2101    fn before_html(&mut self, t: Tok<'_>) {
2102        match t {
2103            Tok::Doctype(_) => self.err("unexpected-doctype"),
2104            Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
2105            Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
2106            Tok::Text(s) => {
2107                let (_, rest) = split_space(s);
2108                if !rest.is_empty() {
2109                    self.before_html_else(Tok::Text(rest));
2110                }
2111            }
2112            Tok::Start(s) if s.tag == Tag::Html => {
2113                let id = self.create(&s, Ns::Html);
2114                self.insert_at((0, NONE), id);
2115                self.push_open(Open {
2116                    id,
2117                    ns: Ns::Html,
2118                    tag: Tag::Html,
2119                });
2120                self.mode = Mode::BeforeHead;
2121            }
2122            Tok::End(e) if !matches!(e.tag, Tag::Head | Tag::Body | Tag::Html | Tag::Br) => {
2123                self.err("unexpected-end-tag-before-html");
2124            }
2125            _ => self.before_html_else(t),
2126        }
2127    }
2128
2129    fn before_html_else(&mut self, t: Tok<'_>) {
2130        let id = self.create(&Start::bare(Tag::Html), Ns::Html);
2131        self.insert_at((0, NONE), id);
2132        self.push_open(Open {
2133            id,
2134            ns: Ns::Html,
2135            tag: Tag::Html,
2136        });
2137        self.reprocess(Mode::BeforeHead, t);
2138    }
2139
2140    fn before_head(&mut self, t: Tok<'_>) {
2141        match t {
2142            Tok::Text(s) => {
2143                let (_, rest) = split_space(s);
2144                if !rest.is_empty() {
2145                    self.before_head_else(Tok::Text(rest));
2146                }
2147            }
2148            Tok::Comment(c) => self.insert_comment(c, None),
2149            Tok::Pi(target, data) => self.insert_pi(target, data, None),
2150            Tok::Doctype(_) => self.err("unexpected-doctype"),
2151            Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
2152            Tok::Start(s) if s.tag == Tag::Head => {
2153                self.head = self.insert_html(&s);
2154                self.mode = Mode::InHead;
2155            }
2156            Tok::End(e) if !matches!(e.tag, Tag::Head | Tag::Body | Tag::Html | Tag::Br) => {
2157                self.err("end-tag-after-implied-root");
2158            }
2159            _ => self.before_head_else(t),
2160        }
2161    }
2162
2163    fn before_head_else(&mut self, t: Tok<'_>) {
2164        self.head = self.insert_html(&Start::bare(Tag::Head));
2165        self.reprocess(Mode::InHead, t);
2166    }
2167
2168    fn in_head(&mut self, t: Tok<'_>) {
2169        use Tag::*;
2170        match t {
2171            Tok::Text(s) => {
2172                let (space, rest) = split_space(s);
2173                self.insert_text(space);
2174                if !rest.is_empty() {
2175                    self.in_head_else(Tok::Text(rest));
2176                }
2177            }
2178            Tok::Comment(c) => self.insert_comment(c, None),
2179            Tok::Pi(target, data) => self.insert_pi(target, data, None),
2180            Tok::Doctype(_) => self.err("unexpected-doctype"),
2181            Tok::Start(s) => match s.tag {
2182                Html => self.in_body(t),
2183                Base | Basefont | Bgsound | Link | Meta => self.insert_void(&s),
2184                Title => self.rawtext(&s, TextMode::Rcdata),
2185                Noscript if self.scripting => self.rawtext(&s, TextMode::Rawtext),
2186                Noframes | Style => self.rawtext(&s, TextMode::Rawtext),
2187                Noscript => {
2188                    self.insert_html(&s);
2189                    self.mode = Mode::InHeadNoscript;
2190                }
2191                Script => self.rawtext(&s, TextMode::ScriptData),
2192                Template => {
2193                    self.active.push(MARKER);
2194                    self.frameset_ok = false;
2195                    self.mode = Mode::InTemplate;
2196                    self.template_modes.push(Mode::InTemplate);
2197                    if self.shadow_roots {
2198                        self.shadow_template(&s);
2199                    } else {
2200                        self.insert_html(&s);
2201                    }
2202                }
2203                Head => self.err("two-heads-are-not-better-than-one"),
2204                _ => self.in_head_else(t),
2205            },
2206            Tok::End(e) => match e.tag {
2207                Head => {
2208                    self.pop();
2209                    self.mode = Mode::AfterHead;
2210                }
2211                Body | Html | Br => self.in_head_else(t),
2212                Template => {
2213                    if !self.template_open() {
2214                        self.err("unexpected-end-tag");
2215                        return;
2216                    }
2217                    self.generate_implied_thoroughly();
2218                    if !self.current().is(Template) {
2219                        self.err("end-tag-too-early");
2220                    }
2221                    self.pop_until(Template);
2222                    self.clear_active_to_marker();
2223                    self.template_modes.pop();
2224                    self.reset_mode();
2225                }
2226                _ => self.err("unexpected-end-tag"),
2227            },
2228            Tok::Eof => self.in_head_else(t),
2229        }
2230    }
2231
2232    fn in_head_else(&mut self, t: Tok<'_>) {
2233        self.pop();
2234        self.reprocess(Mode::AfterHead, t);
2235    }
2236
2237    fn in_head_noscript(&mut self, t: Tok<'_>) {
2238        use Tag::*;
2239        match t {
2240            Tok::Doctype(_) => self.err("unexpected-doctype"),
2241            Tok::Start(s) if s.tag == Html => self.in_body(t),
2242            Tok::End(e) if e.tag == Noscript => {
2243                self.pop();
2244                self.mode = Mode::InHead;
2245            }
2246            Tok::Text(s) => {
2247                let (space, rest) = split_space(s);
2248                if !space.is_empty() {
2249                    self.in_head(Tok::Text(space));
2250                }
2251                if !rest.is_empty() {
2252                    self.in_head_noscript_else(Tok::Text(rest));
2253                }
2254            }
2255            Tok::Comment(_) | Tok::Pi(..) => self.in_head(t),
2256            Tok::Start(s)
2257                if matches!(s.tag, Basefont | Bgsound | Link | Meta | Noframes | Style) =>
2258            {
2259                self.in_head(t)
2260            }
2261            Tok::End(e) if e.tag == Br => self.in_head_noscript_else(t),
2262            Tok::Start(s) if matches!(s.tag, Head | Noscript) => self.err("unexpected-start-tag"),
2263            Tok::End(_) => self.err("unexpected-end-tag"),
2264            _ => self.in_head_noscript_else(t),
2265        }
2266    }
2267
2268    fn in_head_noscript_else(&mut self, t: Tok<'_>) {
2269        match t {
2270            Tok::Text(s) => self.err_in("char-in-head-noscript", s, 0),
2271            Tok::Eof => self.err("eof-in-head-noscript"),
2272            _ => self.err("unexpected-inhead-noscript-tag"),
2273        }
2274        self.pop();
2275        self.reprocess(Mode::InHead, t);
2276    }
2277
2278    fn after_head(&mut self, t: Tok<'_>) {
2279        use Tag::*;
2280        match t {
2281            Tok::Text(s) => {
2282                let (space, rest) = split_space(s);
2283                self.insert_text(space);
2284                if !rest.is_empty() {
2285                    self.after_head_else(Tok::Text(rest));
2286                }
2287            }
2288            Tok::Comment(c) => self.insert_comment(c, None),
2289            Tok::Pi(target, data) => self.insert_pi(target, data, None),
2290            Tok::Doctype(_) => self.err("unexpected-doctype"),
2291            Tok::Start(s) => match s.tag {
2292                Html => self.in_body(t),
2293                Body => {
2294                    self.insert_html(&s);
2295                    self.frameset_ok = false;
2296                    self.mode = Mode::InBody;
2297                }
2298                Frameset => {
2299                    self.insert_html(&s);
2300                    self.mode = Mode::InFrameset;
2301                }
2302                Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
2303                | Title => {
2304                    self.err("unexpected-start-tag-out-of-my-head");
2305                    let head = self.head;
2306                    self.push_open(Open {
2307                        id: head,
2308                        ns: Ns::Html,
2309                        tag: Head,
2310                    });
2311                    self.in_head(t);
2312                    self.remove_open(head);
2313                }
2314                Head => self.err("unexpected-start-tag"),
2315                _ => self.after_head_else(t),
2316            },
2317            Tok::End(e) => match e.tag {
2318                Template => self.in_head(t),
2319                Body | Html | Br => self.after_head_else(t),
2320                _ => self.err("unexpected-end-tag"),
2321            },
2322            Tok::Eof => self.after_head_else(t),
2323        }
2324    }
2325
2326    fn after_head_else(&mut self, t: Tok<'_>) {
2327        self.insert_html(&Start::bare(Tag::Body));
2328        self.frameset_ok = true;
2329        self.reprocess(Mode::InBody, t);
2330    }
2331
2332    fn body_text(&mut self, s: &str) {
2333        if memchr::memchr(0, s.as_bytes()).is_none() {
2334            self.reconstruct();
2335            self.insert_text(s);
2336            if self.frameset_ok && !all_space(s) {
2337                self.frameset_ok = false;
2338            }
2339            return;
2340        }
2341        if self.errors {
2342            for i in memchr::memchr_iter(0, s.as_bytes()) {
2343                self.err_in("invalid-codepoint-in-body", s, i);
2344            }
2345        }
2346        for piece in s.split('\0').filter(|p| !p.is_empty()) {
2347            self.body_text(piece);
2348        }
2349    }
2350
2351    fn in_body(&mut self, t: Tok<'_>) {
2352        match t {
2353            Tok::Text(s) => self.body_text(s),
2354            Tok::Comment(c) => self.insert_comment(c, None),
2355            Tok::Pi(target, data) => self.insert_pi(target, data, None),
2356            Tok::Doctype(_) => self.err("unexpected-doctype"),
2357            Tok::Start(s) => self.in_body_start(s),
2358            Tok::End(e) => self.in_body_end(e),
2359            Tok::Eof => {
2360                if !self.template_modes.is_empty() {
2361                    self.in_template(t);
2362                } else {
2363                    self.check_open_at_end("expected-closing-tag-but-got-eof");
2364                    self.stop();
2365                }
2366            }
2367        }
2368    }
2369
2370    fn in_body_start(&mut self, s: Start<'_>) {
2371        use Tag::*;
2372        match s.tag {
2373            Html => {
2374                self.err("non-html-root");
2375                if !self.template_open() {
2376                    let root = self.open[0].id;
2377                    self.merge_attrs(root, &s);
2378                }
2379            }
2380            Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
2381            | Title => self.in_head(Tok::Start(s)),
2382            Body => {
2383                self.err("unexpected-start-tag");
2384                if self.open.len() == 1 || !self.open[1].is(Body) || self.template_open() {
2385                    return;
2386                }
2387                self.frameset_ok = false;
2388                let body = self.open[1].id;
2389                self.merge_attrs(body, &s);
2390            }
2391            Frameset => {
2392                self.err("unexpected-start-tag");
2393                if self.open.len() == 1 || !self.open[1].is(Body) || !self.frameset_ok {
2394                    return;
2395                }
2396                let body = self.open[1].id;
2397                self.doc.detach(body);
2398                self.truncate_open(1);
2399                self.insert_html(&s);
2400                self.mode = Mode::InFrameset;
2401            }
2402            Address | Article | Aside | Blockquote | Center | Details | Dialog | Dir | Div | Dl
2403            | Fieldset | Figcaption | Figure | Footer | Header | Hgroup | Main | Menu | Nav
2404            | Ol | P | Search | Section | Summary | Ul => {
2405                self.close_p_in_button_scope();
2406                self.insert_html(&s);
2407            }
2408            H1 | H2 | H3 | H4 | H5 | H6 => {
2409                self.close_p_in_button_scope();
2410                let c = self.current();
2411                if c.ns == Ns::Html && heading(c.tag) {
2412                    self.err("unexpected-start-tag");
2413                    self.pop();
2414                }
2415                self.insert_html(&s);
2416            }
2417            Pre | Listing => {
2418                self.close_p_in_button_scope();
2419                self.insert_html(&s);
2420                self.skip_newline = true;
2421                self.frameset_ok = false;
2422            }
2423            Form => {
2424                let template = self.in_template_contents();
2425                if self.form != NONE && !template {
2426                    self.err("unexpected-start-tag");
2427                    return;
2428                }
2429                self.close_p_in_button_scope();
2430                let id = self.insert_html(&s);
2431                if !template {
2432                    self.form = id;
2433                }
2434            }
2435            Li | Dd | Dt => {
2436                self.frameset_ok = false;
2437                for i in (0..self.open.len()).rev() {
2438                    let node = self.open[i];
2439                    let closes = match s.tag {
2440                        Li => node.is(Li),
2441                        _ => node.is(Dd) || node.is(Dt),
2442                    };
2443                    if closes {
2444                        self.generate_implied(Some(node.tag));
2445                        if !self.current().is(node.tag) {
2446                            self.err("end-tag-too-early");
2447                        }
2448                        self.pop_until(node.tag);
2449                        break;
2450                    }
2451                    if special(node) && !node.is(Address) && !node.is(Div) && !node.is(P) {
2452                        break;
2453                    }
2454                }
2455                self.close_p_in_button_scope();
2456                self.insert_html(&s);
2457            }
2458            Plaintext => {
2459                self.close_p_in_button_scope();
2460                self.insert_html(&s);
2461                self.switch = Some(TextMode::Plaintext);
2462            }
2463            Button => {
2464                if self.in_scope(Button, Scope::Default) {
2465                    self.err("unexpected-start-tag-implies-end-tag");
2466                    self.generate_implied(None);
2467                    self.pop_until(Button);
2468                }
2469                self.reconstruct();
2470                self.insert_html(&s);
2471                self.frameset_ok = false;
2472            }
2473            A => {
2474                let start = self
2475                    .active
2476                    .iter()
2477                    .rposition(|&e| e == MARKER)
2478                    .map_or(0, |i| i + 1);
2479                let existing = self.active[start..].iter().rev().copied().find(|&e| {
2480                    self.doc
2481                        .element(e)
2482                        .is_some_and(|el| el.ns == Ns::Html && el.tag == A)
2483                });
2484                if let Some(a) = existing {
2485                    self.err("unexpected-start-tag-implies-end-tag");
2486                    if self.adoption_agency(A, "a") {
2487                        self.any_other_end(End { tag: A, name: "a" });
2488                    }
2489                    self.active.retain(|&e| e != a);
2490                    self.remove_open(a);
2491                }
2492                self.reconstruct();
2493                let id = self.insert_html(&s);
2494                self.push_active(id);
2495            }
2496            B | Big | Code | Em | Font | I | S | Small | Strike | Strong | Tt | U => {
2497                self.reconstruct();
2498                let id = self.insert_html(&s);
2499                self.push_active(id);
2500            }
2501            Nobr => {
2502                self.reconstruct();
2503                if self.in_scope(Nobr, Scope::Default) {
2504                    self.err("unexpected-start-tag-implies-end-tag");
2505                    if self.adoption_agency(Nobr, "nobr") {
2506                        self.any_other_end(End {
2507                            tag: Nobr,
2508                            name: "nobr",
2509                        });
2510                    }
2511                    self.reconstruct();
2512                }
2513                let id = self.insert_html(&s);
2514                self.push_active(id);
2515            }
2516            Applet | Marquee | Object => {
2517                self.reconstruct();
2518                self.insert_html(&s);
2519                self.active.push(MARKER);
2520                self.frameset_ok = false;
2521            }
2522            Table => {
2523                if self.doc.quirks != Quirks::Quirks {
2524                    self.close_p_in_button_scope();
2525                }
2526                self.insert_html(&s);
2527                self.frameset_ok = false;
2528                self.mode = Mode::InTable;
2529            }
2530            Area | Br | Embed | Img | Keygen | Wbr => {
2531                self.reconstruct();
2532                self.insert_void(&s);
2533                self.frameset_ok = false;
2534            }
2535            Input => {
2536                if self.context.is_some_and(|c| c.is(Select)) {
2537                    self.err("unexpected-input-in-select");
2538                    return;
2539                }
2540                if self.in_scope(Select, Scope::Default) {
2541                    self.err("unexpected-input-in-select");
2542                    self.pop_until(Select);
2543                }
2544                self.reconstruct();
2545                self.insert_void(&s);
2546                if !s
2547                    .attr("type")
2548                    .is_some_and(|t| t.eq_ignore_ascii_case("hidden"))
2549                {
2550                    self.frameset_ok = false;
2551                }
2552            }
2553            Param | Source | Track => self.insert_void(&s),
2554            Hr => {
2555                self.close_p_in_button_scope();
2556                if self.in_scope(Select, Scope::Default) {
2557                    self.generate_implied(None);
2558                }
2559                self.insert_void(&s);
2560                self.frameset_ok = false;
2561            }
2562            Image => {
2563                self.err("unexpected-start-tag-treated-as");
2564                self.process(Tok::Start(Start {
2565                    tag: Img,
2566                    name: "img",
2567                    ..s
2568                }))
2569            }
2570            Textarea => {
2571                self.insert_html(&s);
2572                self.skip_newline = true;
2573                self.switch = Some(TextMode::Rcdata);
2574                self.original = self.mode;
2575                self.frameset_ok = false;
2576                self.mode = Mode::Text;
2577            }
2578            Xmp => {
2579                self.close_p_in_button_scope();
2580                self.reconstruct();
2581                self.frameset_ok = false;
2582                self.rawtext(&s, TextMode::Rawtext);
2583            }
2584            Iframe => {
2585                self.frameset_ok = false;
2586                self.rawtext(&s, TextMode::Rawtext);
2587            }
2588            Noembed => self.rawtext(&s, TextMode::Rawtext),
2589            Noscript if self.scripting => self.rawtext(&s, TextMode::Rawtext),
2590            Select => {
2591                if self.context.is_some_and(|c| c.is(Select)) {
2592                    self.err("unexpected-select-in-select");
2593                    return;
2594                }
2595                if self.in_scope(Select, Scope::Default) {
2596                    self.err("unexpected-select-in-select");
2597                    self.pop_until(Select);
2598                    return;
2599                }
2600                self.reconstruct();
2601                self.insert_html(&s);
2602                self.frameset_ok = false;
2603            }
2604            Option => {
2605                if self.in_scope(Select, Scope::Default) {
2606                    self.generate_implied(Some(Optgroup));
2607                } else if self.current().is(Option) {
2608                    self.pop();
2609                }
2610                self.reconstruct();
2611                self.insert_html(&s);
2612            }
2613            Optgroup => {
2614                if self.in_scope(Select, Scope::Default) {
2615                    self.generate_implied(None);
2616                } else if self.current().is(Option) {
2617                    self.pop();
2618                }
2619                self.reconstruct();
2620                self.insert_html(&s);
2621            }
2622            Rb | Rtc => {
2623                if self.in_scope(Ruby, Scope::Default) {
2624                    self.generate_implied(None);
2625                    if !self.current().is(Ruby) {
2626                        self.err("unexpected-start-tag");
2627                    }
2628                }
2629                self.insert_html(&s);
2630            }
2631            Rp | Rt => {
2632                if self.in_scope(Ruby, Scope::Default) {
2633                    self.generate_implied(Some(Rtc));
2634                    if !self.current().is(Ruby) && !self.current().is(Rtc) {
2635                        self.err("unexpected-start-tag");
2636                    }
2637                }
2638                self.insert_html(&s);
2639            }
2640            Math | Svg => {
2641                self.reconstruct();
2642                let ns = if s.tag == Math { Ns::MathMl } else { Ns::Svg };
2643                self.insert_element(&s, ns);
2644                if s.self_closing {
2645                    self.acknowledged = true;
2646                    self.pop();
2647                }
2648            }
2649            Caption | Col | Colgroup | Frame | Head | Tbody | Td | Tfoot | Th | Thead | Tr => {
2650                self.err("unexpected-start-tag-ignored");
2651            }
2652            _ => {
2653                self.reconstruct();
2654                self.insert_html(&s);
2655            }
2656        }
2657    }
2658
2659    fn in_body_end(&mut self, e: End<'_>) {
2660        use Tag::*;
2661        match e.tag {
2662            Template => self.in_head(Tok::End(e)),
2663            Body => {
2664                if !self.in_scope(Body, Scope::Default) {
2665                    self.err("unexpected-end-tag");
2666                } else {
2667                    self.check_open_at_end("expected-one-end-tag-but-got-another");
2668                    self.mode = Mode::AfterBody;
2669                    // It stays open, but this was its end tag.
2670                    if let Some(body) = self.open.get(1).filter(|o| o.is(Body)) {
2671                        self.ended(body.id);
2672                    }
2673                }
2674            }
2675            Html => {
2676                if !self.in_scope(Body, Scope::Default) {
2677                    self.err("unexpected-end-tag");
2678                } else {
2679                    self.check_open_at_end("expected-one-end-tag-but-got-another");
2680                    self.reprocess(Mode::AfterBody, Tok::End(e));
2681                }
2682            }
2683            Address | Article | Aside | Blockquote | Button | Center | Details | Dialog | Dir
2684            | Div | Dl | Fieldset | Figcaption | Figure | Footer | Header | Hgroup | Listing
2685            | Main | Menu | Nav | Ol | Pre | Search | Section | Select | Summary | Ul => {
2686                if !self.in_scope(e.tag, Scope::Default) {
2687                    self.err("unexpected-end-tag");
2688                } else {
2689                    self.generate_implied(None);
2690                    if !self.current().is(e.tag) {
2691                        self.err("end-tag-too-early");
2692                    }
2693                    self.pop_until(e.tag);
2694                }
2695            }
2696            Form => {
2697                if !self.in_template_contents() {
2698                    let node = self.form;
2699                    self.form = NONE;
2700                    if node == NONE || !self.node_in_scope(node) {
2701                        self.err("unexpected-end-tag");
2702                        return;
2703                    }
2704                    self.generate_implied(None);
2705                    if self.current().id != node {
2706                        self.err("end-tag-too-early-ignored");
2707                    }
2708                    self.remove_open(node);
2709                } else if !self.in_scope(Form, Scope::Default) {
2710                    self.err("unexpected-end-tag");
2711                } else {
2712                    self.generate_implied(None);
2713                    if !self.current().is(Form) {
2714                        self.err("end-tag-too-early-ignored");
2715                    }
2716                    self.pop_until(Form);
2717                }
2718            }
2719            P => {
2720                if !self.in_scope(P, Scope::Button) {
2721                    self.err("unexpected-end-tag");
2722                    self.insert_html(&Start::bare(P));
2723                }
2724                self.close_p();
2725            }
2726            Li => {
2727                if !self.in_scope(Li, Scope::ListItem) {
2728                    self.err("unexpected-end-tag");
2729                } else {
2730                    self.generate_implied(Some(Li));
2731                    if !self.current().is(Li) {
2732                        self.err("end-tag-too-early");
2733                    }
2734                    self.pop_until(Li);
2735                }
2736            }
2737            Dd | Dt => {
2738                if !self.in_scope(e.tag, Scope::Default) {
2739                    self.err("unexpected-end-tag");
2740                } else {
2741                    self.generate_implied(Some(e.tag));
2742                    if !self.current().is(e.tag) {
2743                        self.err("end-tag-too-early");
2744                    }
2745                    self.pop_until(e.tag);
2746                }
2747            }
2748            H1 | H2 | H3 | H4 | H5 | H6 => {
2749                if !self.in_scope_any(&HEADINGS, Scope::Default) {
2750                    self.err("unexpected-end-tag");
2751                } else {
2752                    self.generate_implied(None);
2753                    if !self.current().is(e.tag) {
2754                        self.err("end-tag-too-early");
2755                    }
2756                    self.pop_until_where(heading);
2757                }
2758            }
2759            A | B | Big | Code | Em | Font | I | Nobr | S | Small | Strike | Strong | Tt | U => {
2760                if self.adoption_agency(e.tag, e.name) {
2761                    self.any_other_end(e);
2762                }
2763            }
2764            Applet | Marquee | Object => {
2765                if !self.in_scope(e.tag, Scope::Default) {
2766                    self.err("unexpected-end-tag");
2767                } else {
2768                    self.generate_implied(None);
2769                    if !self.current().is(e.tag) {
2770                        self.err("end-tag-too-early");
2771                    }
2772                    self.pop_until(e.tag);
2773                    self.clear_active_to_marker();
2774                }
2775            }
2776            Br => {
2777                self.err("unexpected-end-tag-treated-as");
2778                self.in_body_start(Start::bare(Br));
2779            }
2780            _ => self.any_other_end(e),
2781        }
2782    }
2783
2784    /// The spec's check at `</body>`, `</html>` and the end of the input:
2785    /// an element still open that its end tag can't be left off.
2786    fn check_open_at_end(&mut self, code: &'static str) {
2787        use Tag::*;
2788        if !self.errors {
2789            return;
2790        }
2791        // Counted, not walked: each `</body>` under a deep stack walked it.
2792        let may_be_open: u32 = [
2793            Dd, Dt, Li, Optgroup, Option, P, Rb, Rp, Rt, Rtc, Tbody, Td, Tfoot, Th, Thead, Tr,
2794            Body, Html,
2795        ]
2796        .iter()
2797        .map(|&t| self.open_count(t))
2798        .sum();
2799        let unclosed = self.open.len() as u32 > may_be_open;
2800        if unclosed {
2801            self.err(code);
2802        }
2803    }
2804
2805    fn names_match(&self, o: Open, e: &End<'_>) -> bool {
2806        if o.ns != Ns::Html {
2807            return false;
2808        }
2809        if e.tag != Tag::Other || o.tag != Tag::Other {
2810            return o.tag == e.tag;
2811        }
2812        self.doc
2813            .element(o.id)
2814            .is_some_and(|el| self.doc.element_name(el) == e.name)
2815    }
2816
2817    fn any_other_end(&mut self, e: End<'_>) {
2818        // With no open element of that name the walk below can only end
2819        // without doing anything, after going through the whole stack.
2820        let open = match e.tag {
2821            Tag::Other => self.open_named(true, e.name),
2822            tag => self.open_count(tag),
2823        };
2824        if open == 0 {
2825            self.err("unexpected-end-tag");
2826            return;
2827        }
2828        for i in (0..self.open.len()).rev() {
2829            let node = self.open[i];
2830            if self.names_match(node, &e) {
2831                self.generate_implied(Some(node.tag).filter(|&t| t != Tag::Other));
2832                if self.open.len() != i + 1 {
2833                    self.err("unexpected-end-tag");
2834                }
2835                self.truncate_open(i);
2836                return;
2837            }
2838            if special(node) {
2839                self.err("unexpected-end-tag");
2840                return;
2841            }
2842        }
2843    }
2844
2845    /// The adoption agency algorithm. True when the end tag is to be
2846    /// handled as any other end tag instead.
2847    fn adoption_agency(&mut self, subject: Tag, _name: &str) -> bool {
2848        let c = self.current();
2849        if c.is(subject) && !self.active.contains(&c.id) {
2850            self.pop();
2851            return false;
2852        }
2853        let errors = self.errors;
2854        for _ in 0..8 {
2855            let start = self
2856                .active
2857                .iter()
2858                .rposition(|&e| e == MARKER)
2859                .map_or(0, |i| i + 1);
2860            let Some(fe_active) = (start..self.active.len()).rev().find(|&i| {
2861                self.doc
2862                    .element(self.active[i])
2863                    .is_some_and(|el| el.ns == Ns::Html && el.tag == subject)
2864            }) else {
2865                return true;
2866            };
2867            let fe = self.active[fe_active];
2868            let Some(fe_open) = self.open.iter().rposition(|o| o.id == fe) else {
2869                self.err("adoption-agency-1.2");
2870                self.active.remove(fe_active);
2871                return false;
2872            };
2873            if !self.node_in_scope(fe) {
2874                self.err("adoption-agency-4.4");
2875                return false;
2876            }
2877            if errors && self.current().id != fe {
2878                self.err("adoption-agency-1.3");
2879            }
2880            let Some(fb_open) = (fe_open + 1..self.open.len()).find(|&i| special(self.open[i]))
2881            else {
2882                self.truncate_open(fe_open);
2883                self.active.remove(fe_active);
2884                return false;
2885            };
2886            let furthest = self.open[fb_open].id;
2887            let common = self.open[fe_open - 1].id;
2888            let mut bookmark = fe_active;
2889            let mut node_index = fb_open;
2890            let mut last = furthest;
2891            let mut inner = 0;
2892            let mut bookmark_moved = false;
2893            loop {
2894                inner += 1;
2895                node_index -= 1;
2896                let node = self.open[node_index];
2897                if node.id == fe {
2898                    break;
2899                }
2900                let mut in_active = self.active.iter().position(|&e| e == node.id);
2901                if inner > 3
2902                    && let Some(i) = in_active
2903                {
2904                    self.active.remove(i);
2905                    if i < bookmark {
2906                        bookmark -= 1;
2907                    }
2908                    in_active = None;
2909                }
2910                let Some(ai) = in_active else {
2911                    self.remove_open_at(node_index);
2912                    continue;
2913                };
2914                let new = self.clone_element(node.id);
2915                self.active[ai] = new;
2916                self.open[node_index] = Open { id: new, ..node };
2917                debug_assert!(self.open_contains(node.id) && !self.open_contains(new));
2918                self.mark(node.id, false);
2919                self.mark(new, true);
2920                if !bookmark_moved {
2921                    bookmark = ai + 1;
2922                    bookmark_moved = true;
2923                }
2924                self.doc.detach(last);
2925                self.doc.insert(new, last, NONE);
2926                last = new;
2927            }
2928            let place = self.place(Some(common));
2929            self.doc.detach(last);
2930            self.insert_at(place, last);
2931            let new = self.clone_element(fe);
2932            while let Some(child) = self.doc.first_child(furthest) {
2933                self.doc.detach(child);
2934                self.doc.insert(new, child, NONE);
2935            }
2936            self.doc.insert(furthest, new, NONE);
2937            let fe_active = self
2938                .active
2939                .iter()
2940                .position(|&e| e == fe)
2941                .expect("still active");
2942            self.active.remove(fe_active);
2943            if fe_active < bookmark {
2944                bookmark -= 1;
2945            }
2946            self.active.insert(bookmark.min(self.active.len()), new);
2947            let fe_open = self
2948                .open
2949                .iter()
2950                .position(|o| o.id == fe)
2951                .expect("still open");
2952            let fe_entry = self.remove_open_at(fe_open);
2953            let fb = self
2954                .open
2955                .iter()
2956                .position(|o| o.id == furthest)
2957                .expect("still open");
2958            self.insert_open_at(
2959                fb + 1,
2960                Open {
2961                    id: new,
2962                    ..fe_entry
2963                },
2964            );
2965        }
2966        false
2967    }
2968
2969    fn text(&mut self, t: Tok<'_>) {
2970        match t {
2971            Tok::Text(s) => self.insert_text(s),
2972            Tok::Eof => {
2973                self.err("expected-named-closing-tag-but-got-eof");
2974                self.pop();
2975                let original = self.original;
2976                self.reprocess(original, t);
2977            }
2978            Tok::End(_) => {
2979                self.pop();
2980                self.mode = self.original;
2981            }
2982            _ => {}
2983        }
2984    }
2985
2986    fn in_table(&mut self, t: Tok<'_>) {
2987        use Tag::*;
2988        match t {
2989            Tok::Text(s)
2990                if matches!(
2991                    self.current().tag,
2992                    Table | Tbody | Template | Tfoot | Thead | Tr
2993                ) && self.current().ns == Ns::Html =>
2994            {
2995                self.pending.clear();
2996                self.pending_text = false;
2997                self.pending_at = self.text_at(s);
2998                self.original = self.mode;
2999                self.reprocess(Mode::InTableText, t);
3000            }
3001            Tok::Comment(c) => self.insert_comment(c, None),
3002            Tok::Pi(target, data) => self.insert_pi(target, data, None),
3003            Tok::Doctype(_) => self.err("unexpected-doctype"),
3004            Tok::Start(s) => match s.tag {
3005                Caption => {
3006                    self.clear_to_table_context();
3007                    self.active.push(MARKER);
3008                    self.insert_html(&s);
3009                    self.mode = Mode::InCaption;
3010                }
3011                Colgroup => {
3012                    self.clear_to_table_context();
3013                    self.insert_html(&s);
3014                    self.mode = Mode::InColumnGroup;
3015                }
3016                Col => {
3017                    self.clear_to_table_context();
3018                    self.insert_html(&Start::bare(Colgroup));
3019                    self.reprocess(Mode::InColumnGroup, t);
3020                }
3021                Tbody | Tfoot | Thead => {
3022                    self.clear_to_table_context();
3023                    self.insert_html(&s);
3024                    self.mode = Mode::InTableBody;
3025                }
3026                Td | Th | Tr => {
3027                    self.clear_to_table_context();
3028                    self.insert_html(&Start::bare(Tbody));
3029                    self.reprocess(Mode::InTableBody, t);
3030                }
3031                Table => {
3032                    self.err("unexpected-start-tag-implies-end-tag");
3033                    if self.in_scope(Table, Scope::Table) {
3034                        self.pop_until(Table);
3035                        self.reset_mode();
3036                        self.process(t);
3037                    }
3038                }
3039                Style | Script | Template => self.in_head(t),
3040                Input
3041                    if s.attr("type")
3042                        .is_some_and(|v| v.eq_ignore_ascii_case("hidden")) =>
3043                {
3044                    self.err("unexpected-hidden-input-in-table");
3045                    self.insert_void(&s);
3046                }
3047                Form => {
3048                    self.err("unexpected-form-in-table");
3049                    let template = self.in_template_contents();
3050                    if self.form != NONE && !template {
3051                        return;
3052                    }
3053                    let id = self.insert_html(&s);
3054                    if !template {
3055                        self.form = id;
3056                    }
3057                    self.pop();
3058                }
3059                _ => self.in_table_else(t),
3060            },
3061            Tok::End(e) => match e.tag {
3062                Table => {
3063                    if self.in_scope(Table, Scope::Table) {
3064                        self.pop_until(Table);
3065                        self.reset_mode();
3066                    } else {
3067                        self.err("unexpected-end-tag");
3068                    }
3069                }
3070                Body | Caption | Col | Colgroup | Html | Tbody | Td | Tfoot | Th | Thead | Tr => {
3071                    self.err("unexpected-end-tag");
3072                }
3073                Template => self.in_head(t),
3074                _ => self.in_table_else(t),
3075            },
3076            Tok::Eof => self.in_body(t),
3077            Tok::Text(_) => self.in_table_else(t),
3078        }
3079    }
3080
3081    fn in_table_else(&mut self, t: Tok<'_>) {
3082        match t {
3083            Tok::Start(_) => self.err("foster-parenting-start-tag"),
3084            Tok::End(_) => self.err("foster-parenting-end-tag"),
3085            // One for each character, as the spec has them one at a time.
3086            Tok::Text(s) => self.chars_dropped(s, "foster-parenting-character", false),
3087            _ => {}
3088        }
3089        let foster = self.foster;
3090        self.foster = true;
3091        self.in_body(t);
3092        self.foster = foster;
3093    }
3094
3095    fn in_table_text(&mut self, t: Tok<'_>) {
3096        if let Tok::Text(s) = t {
3097            if self.errors {
3098                for i in memchr::memchr_iter(0, s.as_bytes()) {
3099                    self.err_in("invalid-codepoint-in-table-text", s, i);
3100                }
3101            }
3102            for piece in s.split('\0') {
3103                if !all_space(piece) {
3104                    self.pending_text = true;
3105                }
3106                self.pending.push_str(piece);
3107            }
3108            self.pending_at[1] = self.text_at(s)[1];
3109            return;
3110        }
3111        // The gathered text was written where its runs were, not where
3112        // the token that ends it is.
3113        let at = std::mem::replace(&mut self.at, self.pending_at);
3114        let pending = std::mem::take(&mut self.pending);
3115        if self.pending_text {
3116            self.chars_dropped(&pending, "foster-parenting-character", false);
3117            let foster = self.foster;
3118            self.foster = true;
3119            self.body_text(&pending);
3120            self.foster = foster;
3121        } else {
3122            self.insert_text(&pending);
3123        }
3124        self.pending = pending;
3125        self.pending.clear();
3126        self.at = at;
3127        let original = self.original;
3128        self.reprocess(original, t);
3129    }
3130
3131    fn close_caption(&mut self) -> bool {
3132        if !self.in_scope(Tag::Caption, Scope::Table) {
3133            self.err("unexpected-end-tag");
3134            return false;
3135        }
3136        self.generate_implied(None);
3137        if !self.current().is(Tag::Caption) {
3138            self.err("expected-one-end-tag-but-got-another");
3139        }
3140        self.pop_until(Tag::Caption);
3141        self.clear_active_to_marker();
3142        self.mode = Mode::InTable;
3143        true
3144    }
3145
3146    fn in_caption(&mut self, t: Tok<'_>) {
3147        use Tag::*;
3148        match t {
3149            Tok::End(e) if e.tag == Caption => {
3150                self.close_caption();
3151            }
3152            Tok::Start(s)
3153                if matches!(
3154                    s.tag,
3155                    Caption | Col | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
3156                ) =>
3157            {
3158                if self.close_caption() {
3159                    self.process(t);
3160                }
3161            }
3162            Tok::End(e) if e.tag == Table => {
3163                if self.close_caption() {
3164                    self.process(t);
3165                }
3166            }
3167            Tok::End(e)
3168                if matches!(
3169                    e.tag,
3170                    Body | Col | Colgroup | Html | Tbody | Td | Tfoot | Th | Thead | Tr
3171                ) =>
3172            {
3173                self.err("unexpected-end-tag");
3174            }
3175            _ => self.in_body(t),
3176        }
3177    }
3178
3179    fn in_column_group(&mut self, t: Tok<'_>) {
3180        use Tag::*;
3181        match t {
3182            Tok::Text(s) => {
3183                let (space, rest) = split_space(s);
3184                self.insert_text(space);
3185                if !rest.is_empty() {
3186                    self.in_column_group_else(Tok::Text(rest));
3187                }
3188            }
3189            Tok::Comment(c) => self.insert_comment(c, None),
3190            Tok::Pi(target, data) => self.insert_pi(target, data, None),
3191            Tok::Doctype(_) => self.err("unexpected-doctype"),
3192            Tok::Start(s) if s.tag == Html => self.in_body(t),
3193            Tok::Start(s) if s.tag == Col => self.insert_void(&s),
3194            Tok::End(e) if e.tag == Colgroup => {
3195                if self.current().is(Colgroup) {
3196                    self.pop();
3197                    self.mode = Mode::InTable;
3198                } else {
3199                    self.err("unexpected-end-tag");
3200                }
3201            }
3202            Tok::End(e) if e.tag == Col => self.err("no-end-tag"),
3203            Tok::Start(s) if s.tag == Template => self.in_head(t),
3204            Tok::End(e) if e.tag == Template => self.in_head(t),
3205            Tok::Eof => self.in_body(t),
3206            _ => self.in_column_group_else(t),
3207        }
3208    }
3209
3210    fn in_column_group_else(&mut self, t: Tok<'_>) {
3211        if self.current().is(Tag::Colgroup) {
3212            self.pop();
3213            self.reprocess(Mode::InTable, t);
3214        } else if let Tok::Text(s) = t {
3215            // A token a character: only the others are dropped, and the
3216            // whitespace among them still goes in, however the text was
3217            // cut into runs.
3218            self.chars_dropped(s, "unexpected-character-in-colgroup", true);
3219            self.frameset_space(s);
3220        } else {
3221            self.err("unexpected-character-in-colgroup");
3222        }
3223    }
3224
3225    fn in_table_body(&mut self, t: Tok<'_>) {
3226        use Tag::*;
3227        match t {
3228            Tok::Start(s) if s.tag == Tr => {
3229                self.clear_to_table_body_context();
3230                self.insert_html(&s);
3231                self.mode = Mode::InRow;
3232            }
3233            Tok::Start(s) if matches!(s.tag, Th | Td) => {
3234                self.err("unexpected-cell-in-table-body");
3235                self.clear_to_table_body_context();
3236                self.insert_html(&Start::bare(Tr));
3237                self.reprocess(Mode::InRow, t);
3238            }
3239            Tok::End(e) if matches!(e.tag, Tbody | Tfoot | Thead) => {
3240                if self.in_scope(e.tag, Scope::Table) {
3241                    self.clear_to_table_body_context();
3242                    self.pop();
3243                    self.mode = Mode::InTable;
3244                } else {
3245                    self.err("unexpected-end-tag-in-table-body");
3246                }
3247            }
3248            Tok::Start(s) if matches!(s.tag, Caption | Col | Colgroup | Tbody | Tfoot | Thead) => {
3249                self.table_body_exit(t);
3250            }
3251            Tok::End(e) if e.tag == Table => self.table_body_exit(t),
3252            Tok::End(e)
3253                if matches!(e.tag, Body | Caption | Col | Colgroup | Html | Td | Th | Tr) =>
3254            {
3255                self.err("unexpected-end-tag-in-table-body");
3256            }
3257            _ => self.in_table(t),
3258        }
3259    }
3260
3261    fn table_body_exit(&mut self, t: Tok<'_>) {
3262        use Tag::*;
3263        if self.in_scope_any(&[Tbody, Thead, Tfoot], Scope::Table) {
3264            self.clear_to_table_body_context();
3265            self.pop();
3266            self.reprocess(Mode::InTable, t);
3267        } else {
3268            self.err("unexpected-end-tag");
3269        }
3270    }
3271
3272    fn in_row(&mut self, t: Tok<'_>) {
3273        use Tag::*;
3274        match t {
3275            Tok::Start(s) if matches!(s.tag, Th | Td) => {
3276                self.clear_to_table_row_context();
3277                self.insert_html(&s);
3278                self.mode = Mode::InCell;
3279                self.active.push(MARKER);
3280            }
3281            Tok::End(e) if e.tag == Tr => {
3282                if self.in_scope(Tr, Scope::Table) {
3283                    self.clear_to_table_row_context();
3284                    self.pop();
3285                    self.mode = Mode::InTableBody;
3286                } else {
3287                    self.err("unexpected-end-tag");
3288                }
3289            }
3290            Tok::Start(s)
3291                if matches!(s.tag, Caption | Col | Colgroup | Tbody | Tfoot | Thead | Tr) =>
3292            {
3293                self.row_exit(t);
3294            }
3295            Tok::End(e) if e.tag == Table => self.row_exit(t),
3296            Tok::End(e) if matches!(e.tag, Tbody | Tfoot | Thead) => {
3297                if self.in_scope(e.tag, Scope::Table) {
3298                    self.row_exit(t);
3299                } else {
3300                    self.err("unexpected-end-tag-in-table-row");
3301                }
3302            }
3303            Tok::End(e) if matches!(e.tag, Body | Caption | Col | Colgroup | Html | Td | Th) => {
3304                self.err("unexpected-end-tag-in-table-row");
3305            }
3306            _ => self.in_table(t),
3307        }
3308    }
3309
3310    fn row_exit(&mut self, t: Tok<'_>) {
3311        if self.in_scope(Tag::Tr, Scope::Table) {
3312            self.clear_to_table_row_context();
3313            self.pop();
3314            self.reprocess(Mode::InTableBody, t);
3315        } else {
3316            self.err("unexpected-end-tag");
3317        }
3318    }
3319
3320    fn close_cell(&mut self) {
3321        self.generate_implied(None);
3322        let c = self.current();
3323        if !(c.is(Tag::Td) || c.is(Tag::Th)) {
3324            self.err("unexpected-cell-end-tag");
3325        }
3326        self.pop_until_where(|t| matches!(t, Tag::Td | Tag::Th));
3327        self.clear_active_to_marker();
3328        self.mode = Mode::InRow;
3329    }
3330
3331    fn in_cell(&mut self, t: Tok<'_>) {
3332        use Tag::*;
3333        match t {
3334            Tok::End(e) if matches!(e.tag, Td | Th) => {
3335                if self.in_scope(e.tag, Scope::Table) {
3336                    self.generate_implied(None);
3337                    if !self.current().is(e.tag) {
3338                        self.err("unexpected-cell-end-tag");
3339                    }
3340                    self.pop_until(e.tag);
3341                    self.clear_active_to_marker();
3342                    self.mode = Mode::InRow;
3343                } else {
3344                    self.err("unexpected-end-tag");
3345                }
3346            }
3347            Tok::Start(s)
3348                if matches!(
3349                    s.tag,
3350                    Caption | Col | Colgroup | Tbody | Td | Tfoot | Th | Thead | Tr
3351                ) =>
3352            {
3353                if self.in_scope_any(&[Td, Th], Scope::Table) {
3354                    self.close_cell();
3355                    self.process(t);
3356                } else {
3357                    self.err("unexpected-start-tag");
3358                }
3359            }
3360            Tok::End(e) if matches!(e.tag, Body | Caption | Col | Colgroup | Html) => {
3361                self.err("unexpected-end-tag");
3362            }
3363            Tok::End(e) if matches!(e.tag, Table | Tbody | Tfoot | Thead | Tr) => {
3364                if self.in_scope(e.tag, Scope::Table) {
3365                    self.close_cell();
3366                    self.process(t);
3367                } else {
3368                    self.err("unexpected-end-tag");
3369                }
3370            }
3371            _ => self.in_body(t),
3372        }
3373    }
3374
3375    fn in_template(&mut self, t: Tok<'_>) {
3376        use Tag::*;
3377        let switch = |me: &mut Self, mode: Mode| {
3378            me.template_modes.pop();
3379            me.template_modes.push(mode);
3380            me.reprocess(mode, t);
3381        };
3382        match t {
3383            Tok::Text(_) | Tok::Comment(_) | Tok::Pi(..) | Tok::Doctype(_) => self.in_body(t),
3384            Tok::Start(s) => match s.tag {
3385                Base | Basefont | Bgsound | Link | Meta | Noframes | Script | Style | Template
3386                | Title => self.in_head(t),
3387                Caption | Colgroup | Tbody | Tfoot | Thead => switch(self, Mode::InTable),
3388                Col => switch(self, Mode::InColumnGroup),
3389                Tr => switch(self, Mode::InTableBody),
3390                Td | Th => switch(self, Mode::InRow),
3391                _ => switch(self, Mode::InBody),
3392            },
3393            Tok::End(e) if e.tag == Template => self.in_head(t),
3394            Tok::End(_) => self.err("unexpected-end-tag"),
3395            Tok::Eof => {
3396                if !self.template_open() {
3397                    self.stop();
3398                    return;
3399                }
3400                self.err("eof-in-template");
3401                self.pop_until(Template);
3402                self.clear_active_to_marker();
3403                self.template_modes.pop();
3404                self.reset_mode();
3405                self.eof_again = true;
3406            }
3407        }
3408    }
3409
3410    fn after_body(&mut self, t: Tok<'_>) {
3411        match t {
3412            Tok::Text(s) => {
3413                let (space, rest) = split_space(s);
3414                if !space.is_empty() {
3415                    self.in_body(Tok::Text(space));
3416                }
3417                if !rest.is_empty() {
3418                    self.err_in("unexpected-char-after-body", rest, 0);
3419                    self.reprocess(Mode::InBody, Tok::Text(rest));
3420                }
3421            }
3422            Tok::Comment(c) => {
3423                let root = self.open[0].id;
3424                self.insert_comment(c, Some((root, NONE)));
3425            }
3426            Tok::Pi(target, data) => {
3427                let root = self.open[0].id;
3428                self.insert_pi(target, data, Some((root, NONE)));
3429            }
3430            Tok::Doctype(_) => self.err("unexpected-doctype"),
3431            Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
3432            Tok::End(e) if e.tag == Tag::Html => {
3433                if self.context.is_none() {
3434                    self.mode = Mode::AfterAfterBody;
3435                    let html = self.open[0].id;
3436                    self.ended(html);
3437                } else {
3438                    self.err("unexpected-end-tag-after-body-innerhtml");
3439                }
3440            }
3441            Tok::Eof => self.stop(),
3442            _ => {
3443                self.err(match t {
3444                    Tok::Start(_) => "unexpected-start-tag-after-body",
3445                    _ => "unexpected-end-tag-after-body",
3446                });
3447                self.reprocess(Mode::InBody, t);
3448            }
3449        }
3450    }
3451
3452    /// A parse error for each character of `s`, as the spec has a token
3453    /// for each; with `but_space`, not for whitespace, which the frameset
3454    /// modes keep.
3455    fn chars_dropped(&mut self, s: &str, code: &'static str, but_space: bool) {
3456        if self.errors {
3457            for (i, c) in s.char_indices() {
3458                if !(but_space && is_space_char(c)) {
3459                    self.err_in(code, s, i);
3460                }
3461            }
3462        }
3463    }
3464
3465    /// The frameset modes keep only the whitespace: each run of it goes
3466    /// in as the slice it is, so the text node has the place it would
3467    /// whichever way the text was cut into runs.
3468    fn frameset_space(&mut self, s: &str) {
3469        for space in space_runs(s) {
3470            self.insert_text(space);
3471        }
3472    }
3473
3474    fn in_frameset(&mut self, t: Tok<'_>) {
3475        use Tag::*;
3476        match t {
3477            Tok::Text(s) => {
3478                self.chars_dropped(s, "unexpected-char-in-frameset", true);
3479                self.frameset_space(s);
3480            }
3481            Tok::Comment(c) => self.insert_comment(c, None),
3482            Tok::Pi(target, data) => self.insert_pi(target, data, None),
3483            Tok::Doctype(_) => self.err("unexpected-doctype"),
3484            Tok::Start(s) => match s.tag {
3485                Html => self.in_body(t),
3486                Frameset => {
3487                    self.insert_html(&s);
3488                }
3489                Frame => self.insert_void(&s),
3490                Noframes => self.in_head(t),
3491                _ => self.err("unexpected-start-tag-in-frameset"),
3492            },
3493            Tok::End(e) if e.tag == Frameset => {
3494                if self.open.len() == 1 {
3495                    self.err("unexpected-frameset-in-frameset-innerhtml");
3496                    return;
3497                }
3498                self.pop();
3499                if self.context.is_none() && !self.current().is(Frameset) {
3500                    self.mode = Mode::AfterFrameset;
3501                }
3502            }
3503            Tok::End(_) => self.err("unexpected-end-tag-in-frameset"),
3504            Tok::Eof => {
3505                if self.open.len() > 1 {
3506                    self.err("eof-in-frameset");
3507                }
3508                self.stop();
3509            }
3510        }
3511    }
3512
3513    fn after_frameset(&mut self, t: Tok<'_>) {
3514        match t {
3515            Tok::Text(s) => {
3516                self.chars_dropped(s, "unexpected-char-after-frameset", true);
3517                self.frameset_space(s);
3518            }
3519            Tok::Comment(c) => self.insert_comment(c, None),
3520            Tok::Pi(target, data) => self.insert_pi(target, data, None),
3521            Tok::Doctype(_) => self.err("unexpected-doctype"),
3522            Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
3523            Tok::End(e) if e.tag == Tag::Html => self.mode = Mode::AfterAfterFrameset,
3524            Tok::Start(s) if s.tag == Tag::Noframes => self.in_head(t),
3525            Tok::Eof => self.stop(),
3526            Tok::Start(_) => self.err("unexpected-start-tag-after-frameset"),
3527            Tok::End(_) => self.err("unexpected-end-tag-after-frameset"),
3528        }
3529    }
3530
3531    fn after_after_body(&mut self, t: Tok<'_>) {
3532        match t {
3533            Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
3534            Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
3535            Tok::Doctype(_) => self.in_body(t),
3536            Tok::Text(s) => {
3537                let (space, rest) = split_space(s);
3538                if !space.is_empty() {
3539                    self.in_body(Tok::Text(space));
3540                }
3541                if !rest.is_empty() {
3542                    self.err_in("expected-eof-but-got-char", rest, 0);
3543                    self.reprocess(Mode::InBody, Tok::Text(rest));
3544                }
3545            }
3546            Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
3547            Tok::Eof => self.stop(),
3548            _ => {
3549                self.err(match t {
3550                    Tok::Start(_) => "expected-eof-but-got-start-tag",
3551                    _ => "expected-eof-but-got-end-tag",
3552                });
3553                self.reprocess(Mode::InBody, t);
3554            }
3555        }
3556    }
3557
3558    fn after_after_frameset(&mut self, t: Tok<'_>) {
3559        match t {
3560            Tok::Comment(c) => self.insert_comment(c, Some((0, NONE))),
3561            Tok::Pi(target, data) => self.insert_pi(target, data, Some((0, NONE))),
3562            Tok::Doctype(_) => self.in_body(t),
3563            Tok::Text(s) => {
3564                self.chars_dropped(s, "expected-eof-but-got-char", true);
3565                for space in space_runs(s) {
3566                    self.in_body(Tok::Text(space));
3567                }
3568            }
3569            Tok::Start(s) if s.tag == Tag::Html => self.in_body(t),
3570            Tok::Start(s) if s.tag == Tag::Noframes => self.in_head(t),
3571            Tok::Eof => self.stop(),
3572            Tok::Start(_) => self.err("expected-eof-but-got-start-tag"),
3573            Tok::End(_) => self.err("expected-eof-but-got-end-tag"),
3574        }
3575    }
3576
3577    // ---- foreign content --------------------------------------------------
3578
3579    fn foreign(&mut self, t: Tok<'_>) {
3580        use Tag::*;
3581        match t {
3582            Tok::Text(s) => {
3583                if s.contains('\0') {
3584                    if self.errors {
3585                        for i in memchr::memchr_iter(0, s.as_bytes()) {
3586                            self.err_in("invalid-codepoint-in-foreign-content", s, i);
3587                        }
3588                    }
3589                    self.insert_text(&s.replace('\0', "\u{FFFD}"));
3590                } else {
3591                    self.insert_text(s);
3592                }
3593                if s.bytes().any(|b| !is_space(b) && b != 0) {
3594                    self.frameset_ok = false;
3595                }
3596            }
3597            Tok::Comment(c) => self.insert_comment(c, None),
3598            Tok::Pi(target, data) => self.insert_pi(target, data, None),
3599            Tok::Doctype(_) => self.err("unexpected-doctype"),
3600            Tok::Start(s)
3601                if matches!(
3602                    s.tag,
3603                    B | Big
3604                        | Blockquote
3605                        | Body
3606                        | Br
3607                        | Center
3608                        | Code
3609                        | Dd
3610                        | Div
3611                        | Dl
3612                        | Dt
3613                        | Em
3614                        | Embed
3615                        | H1
3616                        | H2
3617                        | H3
3618                        | H4
3619                        | H5
3620                        | H6
3621                        | Head
3622                        | Hr
3623                        | I
3624                        | Img
3625                        | Li
3626                        | Listing
3627                        | Menu
3628                        | Meta
3629                        | Nobr
3630                        | Ol
3631                        | P
3632                        | Pre
3633                        | Ruby
3634                        | S
3635                        | Small
3636                        | Span
3637                        | Strong
3638                        | Strike
3639                        | Sub
3640                        | Sup
3641                        | Table
3642                        | Tt
3643                        | U
3644                        | Ul
3645                        | Var
3646                ) || (s.tag == Font
3647                    && s.attrs()
3648                        .any(|(n, _)| matches!(n, "color" | "face" | "size"))) =>
3649            {
3650                self.err("unexpected-html-element-in-foreign-content");
3651                self.break_out(t);
3652            }
3653            Tok::End(e) if matches!(e.tag, Br | P) => {
3654                self.err("unexpected-end-tag");
3655                self.break_out(t);
3656            }
3657            Tok::Start(s) => {
3658                let ns = self.adjusted_current().map_or(Ns::Html, |a| a.ns);
3659                self.insert_element(&s, ns);
3660                if s.self_closing {
3661                    self.acknowledged = true;
3662                    self.pop();
3663                }
3664            }
3665            Tok::End(e) => {
3666                let c = self.current();
3667                if e.tag == Script && c.ns == Ns::Svg && c.tag == Script {
3668                    self.pop();
3669                    return;
3670                }
3671                let mut i = self.open.len() - 1;
3672                // Unless the current node or an open foreign element has
3673                // that name, the walk below ends at the nearest HTML
3674                // element, which then takes the token; without walking
3675                // there one element at a time.
3676                let current = self
3677                    .doc
3678                    .element(c.id)
3679                    .is_some_and(|el| self.doc.element_name(el).eq_ignore_ascii_case(e.name));
3680                if !current {
3681                    self.err("unexpected-end-tag");
3682                }
3683                if !current && self.open_named(false, e.name) == 0 {
3684                    if i > 0 {
3685                        self.html(t);
3686                    }
3687                    return;
3688                }
3689                loop {
3690                    if i == 0 {
3691                        return;
3692                    }
3693                    let node = self.open[i];
3694                    let name = self
3695                        .doc
3696                        .element(node.id)
3697                        .map(|el| self.doc.element_name(el))
3698                        .unwrap_or("");
3699                    if name.eq_ignore_ascii_case(e.name) {
3700                        self.truncate_open(i);
3701                        return;
3702                    }
3703                    i -= 1;
3704                    if self.open[i].ns == Ns::Html {
3705                        self.html(t);
3706                        return;
3707                    }
3708                }
3709            }
3710            Tok::Eof => self.html(t),
3711        }
3712    }
3713
3714    fn break_out(&mut self, t: Tok<'_>) {
3715        loop {
3716            let c = self.current();
3717            let html_integration = match c.ns {
3718                Ns::Svg => matches!(c.tag, Tag::ForeignObject | Tag::Desc | Tag::Title),
3719                Ns::MathMl => self.doc.element(c.id).is_some_and(|e| e.html_integration),
3720                Ns::Html | Ns::Xml => true,
3721            };
3722            if mathml_text_integration(c) || html_integration {
3723                break;
3724            }
3725            self.pop();
3726        }
3727        self.html(t);
3728    }
3729}
3730
3731impl Sink for TreeBuilder {
3732    fn doctype(&mut self, d: &Doctype<'_>) {
3733        self.skip_newline = false;
3734        self.process(Tok::Doctype(d));
3735    }
3736
3737    fn start_tag(&mut self, tag: &tokenizer::Tag<'_>) -> Option<TextMode> {
3738        self.skip_newline = false;
3739        self.switch = None;
3740        self.acknowledged = false;
3741        self.process(Tok::Start(Start {
3742            tag: Tag::from_name(tag.name),
3743            name: tag.name,
3744            attrs: Some(tag),
3745            self_closing: tag.self_closing,
3746        }));
3747        // Only a void element or a foreign one may close itself.
3748        if self.errors && tag.self_closing && !self.acknowledged {
3749            self.err("non-void-element-with-trailing-solidus");
3750        }
3751        self.switch.take()
3752    }
3753
3754    fn end_tag(&mut self, tag: &tokenizer::Tag<'_>) {
3755        self.skip_newline = false;
3756        if self.spans {
3757            self.closing_name.clear();
3758            self.closing_name.push_str(tag.name);
3759            self.closing = true;
3760        }
3761        self.process(Tok::End(End {
3762            tag: Tag::from_name(tag.name),
3763            name: tag.name,
3764        }));
3765        self.closing = false;
3766    }
3767
3768    fn comment(&mut self, text: &str) {
3769        self.skip_newline = false;
3770        self.process(Tok::Comment(text));
3771    }
3772
3773    fn processing_instruction(&mut self, target: &str, data: &str) {
3774        self.skip_newline = false;
3775        self.process(Tok::Pi(target, data));
3776    }
3777
3778    fn text(&mut self, text: &str) {
3779        let mut text = text;
3780        if std::mem::take(&mut self.skip_newline) {
3781            text = text.strip_prefix('\n').unwrap_or(text);
3782        }
3783        if !text.is_empty() {
3784            self.process(Tok::Text(text));
3785        }
3786    }
3787
3788    fn eof(&mut self) {
3789        // Errors at the end are at the end of the input.
3790        self.at = [self.doc.src.len() as u32; 2];
3791        self.process(Tok::Eof);
3792        while std::mem::take(&mut self.eof_again) {
3793            self.process(Tok::Eof);
3794        }
3795    }
3796
3797    fn error(&mut self, code: &'static str, at: usize) {
3798        self.errors_found.push((code, at as u32));
3799    }
3800
3801    fn cdata_allowed(&self) -> bool {
3802        self.adjusted_current().is_some_and(|a| a.ns != Ns::Html)
3803    }
3804
3805    fn position(&mut self, start: usize, end: usize) {
3806        debug_assert!(
3807            start <= end && end <= self.doc.src.len(),
3808            "token at {start}..{end}, outside {} bytes of source",
3809            self.doc.src.len()
3810        );
3811        self.at = [start as u32, end as u32];
3812    }
3813}
3814
3815/// How to parse.
3816#[derive(Debug, Clone, Copy, Default)]
3817pub struct Options {
3818    /// As a browser with JavaScript on: `<noscript>` holds raw text.
3819    pub scripting: bool,
3820    /// Give up after this long. Some inputs are slow by design (the spec
3821    /// makes deeply misnested markup cost more), so a crawler parsing
3822    /// pages it doesn't control should set one. The clock is read every
3823    /// 4,096 tokenizer steps, so a small input finishes even with
3824    /// `Duration::ZERO`: the budget bounds slow parses, not fast ones.
3825    pub budget: Option<std::time::Duration>,
3826    /// Collect the parse errors, for [`Document::errors`]. The page is
3827    /// parsed the same either way; this only keeps the errors, and takes
3828    /// the tokenizer's slower path through tags to find them all.
3829    pub errors: bool,
3830    /// Record where each node and attribute was written, for
3831    /// [`Document::span`], [`Document::end_span`],
3832    /// [`Document::attr_span`] and [`Document::line_col`]. Off, the parse
3833    /// is as fast as ever; on, it keeps a few bytes more per node.
3834    pub spans: bool,
3835    /// Keep the tree at most this deep, as Chromium does at 512: once more
3836    /// elements are open than this, a node goes beside the current one
3837    /// instead of inside it. Only the tree gets flatter; the parse goes on
3838    /// as before, and every element is still there. `None` is no limit;
3839    /// `Some(0)` is taken as `Some(1)`, as the root element holds the rest.
3840    pub max_depth: Option<usize>,
3841    /// Whether a `<template shadowrootmode>` attaches a shadow root to the
3842    /// element it's in, the document's "allow declarative shadow roots".
3843    /// `None` is the HTML Standard's default: on for a document, as a
3844    /// browser parses a page, and off for a fragment, as `innerHTML`
3845    /// parses one; `Some(true)` for a fragment is `setHTMLUnsafe`. Off, the
3846    /// template is an ordinary one. In a fragment the context element is
3847    /// never the host: it isn't in the result.
3848    pub declarative_shadow_roots: Option<bool>,
3849}
3850
3851/// A parse error the HTML Standard defines, from [`Document::errors`].
3852/// The parser recovered from it, as the spec says to; it's for a linter
3853/// or an editor to report.
3854#[derive(Debug, Clone, PartialEq, Eq)]
3855pub struct SyntaxError {
3856    /// The error's name: the HTML Standard's for those the tokenizer finds
3857    /// (`unexpected-null-character`, `eof-in-tag`), and for those of tree
3858    /// construction, which the spec leaves unnamed, the names the html5lib
3859    /// and web-platform-tests suites use (`unexpected-end-tag`,
3860    /// `expected-doctype-but-got-start-tag`).
3861    pub code: &'static str,
3862    /// A byte offset into the input as the parse was given it: where the
3863    /// tokenizer was when it found the error, or the start of the token
3864    /// that tree construction found it in.
3865    pub offset: usize,
3866    /// The offset's line and column, as [`Document::line_col`] counts
3867    /// them: from 1, in characters.
3868    pub line: usize,
3869    pub column: usize,
3870}
3871
3872impl std::fmt::Display for SyntaxError {
3873    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
3874        write!(f, "{}:{}: {}", self.line, self.column, self.code)
3875    }
3876}
3877
3878/// Why a parse returned no document.
3879#[derive(Debug, Clone, PartialEq, Eq)]
3880pub enum ParseError {
3881    /// The input is over [`crate::MAX_INPUT`] bytes.
3882    TooLarge { len: usize },
3883    /// The budget ran out after `parsed` bytes.
3884    Timeout {
3885        budget: std::time::Duration,
3886        parsed: usize,
3887    },
3888}
3889
3890impl std::fmt::Display for ParseError {
3891    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
3892        match self {
3893            ParseError::TooLarge { len } => write!(
3894                f,
3895                "{len} bytes of HTML is over the {} byte limit",
3896                crate::MAX_INPUT
3897            ),
3898            ParseError::Timeout { budget, parsed } => write!(
3899                f,
3900                "parsing took longer than {budget:?} (gave up after {parsed} bytes)"
3901            ),
3902        }
3903    }
3904}
3905
3906impl std::error::Error for ParseError {}
3907
3908/// Parses a whole document. A leading byte order mark (U+FEFF) is dropped,
3909/// as decoding the page would have.
3910///
3911/// # Panics
3912/// On input over [`crate::MAX_INPUT`] bytes; [`parse_with`] returns an
3913/// error instead.
3914pub fn parse(html: &str, scripting: bool) -> Document {
3915    parse_with(
3916        html,
3917        Options {
3918            scripting,
3919            ..Options::default()
3920        },
3921    )
3922    .unwrap_or_else(|e| panic!("{e}"))
3923}
3924
3925/// Parses a whole document, within a size limit and an optional budget.
3926pub fn parse_with(html: &str, options: Options) -> Result<Document, ParseError> {
3927    run(html, options, None)
3928}
3929
3930/// Parses `html` as the contents of an element named `context` in
3931/// namespace `ns`, as `innerHTML` does.
3932///
3933/// # Panics
3934/// As [`parse`].
3935pub fn parse_fragment(html: &str, ns: Ns, context: &str, scripting: bool) -> Document {
3936    parse_fragment_with(
3937        html,
3938        ns,
3939        context,
3940        Options {
3941            scripting,
3942            ..Options::default()
3943        },
3944    )
3945    .unwrap_or_else(|e| panic!("{e}"))
3946}
3947
3948/// Parses `html` as [`parse_fragment`] does, within a size limit and an
3949/// optional budget, as [`parse_with`] does for a whole document.
3950pub fn parse_fragment_with(
3951    html: &str,
3952    ns: Ns,
3953    context: &str,
3954    options: Options,
3955) -> Result<Document, ParseError> {
3956    run(html, options, Some((ns, context)))
3957}
3958
3959fn run(html: &str, options: Options, fragment: Option<(Ns, &str)>) -> Result<Document, ParseError> {
3960    // Too large is said before anything is made for it, as the parser
3961    // would count it: less a document's byte order mark.
3962    let bom = fragment.is_none() && html.starts_with('\u{FEFF}');
3963    let len = html.len() - if bom { 3 } else { 0 };
3964    if len > crate::MAX_INPUT {
3965        return Err(ParseError::TooLarge { len });
3966    }
3967    let mut parser = Parser::start(options, fragment, html.len());
3968    parser.push(html);
3969    parser.finish()
3970}
3971
3972/// Parses a document as it arrives, a piece at a time, into the tree
3973/// [`parse_with`] would build from the whole: the same for any way of
3974/// cutting the input up, with the same spans and errors when asked for.
3975///
3976/// Each [`Parser::feed`] tokenizes and builds as far as the input allows,
3977/// keeping only what it can't decide yet (an unfinished tag, a character
3978/// reference cut short, a CR that might be half a CRLF) for the next
3979/// piece; [`Parser::finish`] reads the end of the input and hands back the
3980/// document. The pieces are `&str`, so one can't end inside a character:
3981/// decoding bytes, and finding the encoding, comes first, and is the
3982/// encoding crate's.
3983///
3984/// ```
3985/// use parsec::{Options, Parser};
3986///
3987/// let mut parser = Parser::new(Options::default());
3988/// for piece in ["<p>He", "llo, <b>wor", "ld</b>"] {
3989///     parser.feed(piece);
3990/// }
3991/// let doc = parser.finish().unwrap();
3992/// assert_eq!(doc.text(doc.root()), "Hello, world");
3993/// ```
3994pub struct Parser {
3995    builder: TreeBuilder,
3996    /// Reads the document's source as it grows: see [`Parser::tokenize`].
3997    tokenizer: Tokenizer<'static>,
3998    options: Options,
3999    fragment: bool,
4000    /// Whether the input's first character has come, which is dropped if
4001    /// it's a byte order mark.
4002    started: bool,
4003    /// Whether the last piece ended in a CR, which waits for the next: a
4004    /// CRLF is one LF.
4005    cr: bool,
4006    /// How much input there has been, less a dropped byte order mark.
4007    len: usize,
4008    /// How much of the budget the parse has used, which counts only the
4009    /// time spent in `feed` and `finish`, not waiting for input.
4010    spent: std::time::Duration,
4011    too_large: bool,
4012}
4013
4014impl Parser {
4015    /// A parser for a whole document, as [`parse_with`] parses one.
4016    pub fn new(options: Options) -> Parser {
4017        Parser::start(options, None, 0)
4018    }
4019
4020    /// A parser for the contents of an element named `context` in
4021    /// namespace `ns`, as [`parse_fragment_with`] parses them.
4022    pub fn fragment(ns: Ns, context: &str, options: Options) -> Parser {
4023        Parser::start(options, Some((ns, context)), 0)
4024    }
4025
4026    fn start(options: Options, fragment: Option<(Ns, &str)>, capacity: usize) -> Parser {
4027        let mut builder = TreeBuilder::new(capacity, options.scripting);
4028        builder.doc.src = String::with_capacity(capacity);
4029        builder.doc.scripting = options.scripting;
4030        builder.max_depth = options.max_depth.map(|d| d.max(1));
4031        builder.spans = options.spans;
4032        builder.errors = options.errors;
4033        builder.shadow_roots = options
4034            .declarative_shadow_roots
4035            .unwrap_or(fragment.is_none());
4036        if options.spans || options.errors {
4037            builder.doc.positions = Some(Box::default());
4038        }
4039        let mode = match fragment {
4040            Some((ns, context)) => builder.fragment(ns, context),
4041            None => None,
4042        };
4043        let mut tokenizer = Tokenizer::new("");
4044        if let Some(mode) = mode {
4045            tokenizer.set_text_mode(mode);
4046        }
4047        if options.errors {
4048            tokenizer.report_errors();
4049        }
4050        if options.spans || options.errors {
4051            tokenizer.keep_positions();
4052        }
4053        Parser {
4054            builder,
4055            tokenizer,
4056            options,
4057            fragment: fragment.is_some(),
4058            started: false,
4059            cr: false,
4060            len: 0,
4061            spent: std::time::Duration::ZERO,
4062            too_large: false,
4063        }
4064    }
4065
4066    /// The next piece of the input.
4067    pub fn feed(&mut self, chunk: &str) {
4068        if self.push(chunk) {
4069            self.tokenize(true);
4070            #[cfg(debug_assertions)]
4071            self.builder.check_stack(false);
4072        }
4073    }
4074
4075    /// The end of the input: the document, or why there's none, as
4076    /// [`parse_with`] gives them. A budget counts the time spent in
4077    /// [`Parser::feed`] and here, not the time between.
4078    pub fn finish(mut self) -> Result<Document, ParseError> {
4079        if self.too_large {
4080            return Err(ParseError::TooLarge { len: self.len });
4081        }
4082        if !self.tokenizer.timed_out() {
4083            if std::mem::take(&mut self.cr) {
4084                self.builder.doc.src.push('\n');
4085            }
4086            self.tokenize(false);
4087        }
4088        if self.tokenizer.timed_out() {
4089            return Err(ParseError::Timeout {
4090                budget: self.options.budget.unwrap_or_default(),
4091                parsed: self.tokenizer.position(),
4092            });
4093        }
4094        #[cfg(debug_assertions)]
4095        self.builder.check_stack(true);
4096        if self.fragment {
4097            self.builder.finish_fragment();
4098        }
4099        self.builder.release_shadow_roots();
4100        self.builder.finish_errors();
4101        let mut doc = self.builder.doc;
4102        doc.src.shrink_to_fit();
4103        Ok(doc)
4104    }
4105
4106    /// Adds `chunk` to the document's source as the spec's input stream
4107    /// preprocessing would have it, CRLF and CR as LF, and says whether
4108    /// to go on.
4109    fn push(&mut self, chunk: &str) -> bool {
4110        let mut chunk = chunk;
4111        if !self.started && !chunk.is_empty() {
4112            self.started = true;
4113            // Decoding a document drops a byte order mark, so a string
4114            // that still starts with one gets the same tree. A fragment,
4115            // as innerHTML, keeps it.
4116            if !self.fragment
4117                && let Some(rest) = chunk.strip_prefix('\u{FEFF}')
4118            {
4119                chunk = rest;
4120                if let Some(p) = self.builder.doc.positions.as_deref_mut() {
4121                    p.skipped = 3;
4122                }
4123            }
4124        }
4125        self.len += chunk.len();
4126        if self.too_large || self.len > crate::MAX_INPUT {
4127            // Nothing more is kept, nor read.
4128            if !self.too_large {
4129                self.too_large = true;
4130                self.builder.doc.src = String::new();
4131            }
4132            return false;
4133        }
4134        if self.tokenizer.timed_out() {
4135            return false;
4136        }
4137        let doc = &mut self.builder.doc;
4138        let (src, mut positions) = (&mut doc.src, doc.positions.as_deref_mut());
4139        // Where an LF that was a CRLF lands, for mapping back.
4140        let mut crlf = |at: usize| {
4141            if let Some(p) = positions.as_deref_mut() {
4142                p.crlf.push(at as u32);
4143            }
4144        };
4145        let mut rest = chunk;
4146        if rest.is_empty() {
4147            return true;
4148        }
4149        if std::mem::take(&mut self.cr) {
4150            if let Some(after) = rest.strip_prefix('\n') {
4151                crlf(src.len());
4152                rest = after;
4153            }
4154            src.push('\n');
4155        }
4156        while let Some(i) = memchr::memchr(b'\r', rest.as_bytes()) {
4157            src.push_str(&rest[..i]);
4158            match rest.as_bytes().get(i + 1) {
4159                None => {
4160                    self.cr = true;
4161                    return true;
4162                }
4163                Some(b'\n') => {
4164                    crlf(src.len());
4165                    rest = &rest[i + 2..];
4166                }
4167                Some(_) => rest = &rest[i + 1..],
4168            }
4169            src.push('\n');
4170        }
4171        src.push_str(rest);
4172        true
4173    }
4174
4175    /// Tokenizes what the source has that the tokenizer hasn't read; the
4176    /// rest of it, at the end, when not `partial`.
4177    fn tokenize(&mut self, partial: bool) {
4178        // Only with a budget: wasm32-unknown-unknown has no clock, and
4179        // reading one there panics.
4180        let start = self.options.budget.map(|_| std::time::Instant::now());
4181        // SAFETY: the source grows only between these calls. While the
4182        // tokenizer runs, the tree builder adds to its own buffers and
4183        // never to the source, so these bytes stay where they are; and the
4184        // tokenizer lets go of the reference as soon as it's done, keeping
4185        // its place as offsets, so it never holds one to a source that has
4186        // since grown and moved. The reference never leaves the parser.
4187        let src: &'static str = unsafe { &*(self.builder.doc.src.as_str() as *const str) };
4188        self.tokenizer.extend(src);
4189        // What's left of the budget from now; one past what the clock can
4190        // count is no limit at all.
4191        if let Some((budget, start)) = self.options.budget.zip(start) {
4192            match budget.checked_sub(self.spent) {
4193                Some(left) => {
4194                    if let Some(deadline) = start.checked_add(left) {
4195                        self.tokenizer.set_deadline(deadline);
4196                    }
4197                }
4198                None => self.tokenizer.set_deadline(start),
4199            }
4200        }
4201        if partial {
4202            self.tokenizer.run_partial(&mut self.builder);
4203        } else {
4204            self.tokenizer.run(&mut self.builder);
4205        }
4206        self.tokenizer.detach();
4207        if let Some(start) = start {
4208            self.spent += start.elapsed();
4209        }
4210    }
4211}
4212
4213#[cfg(test)]
4214mod tests {
4215    use super::*;
4216    use std::time::Duration;
4217
4218    #[test]
4219    fn noahs_ark_matches_attributes_in_any_order() {
4220        // Four alike, written in two orders: the list keeps three, so the
4221        // second paragraph reopens three. The one with c=3 isn't alike.
4222        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";
4223        let doc = parse(html, false);
4224        let out = doc.outer_html(doc.root());
4225        let second = &out[out.rfind("<p>").unwrap()..];
4226        assert_eq!(second.matches("<b ").count(), 4, "{out}");
4227        assert_eq!(second.matches("c=\"3\"").count(), 1, "{out}");
4228    }
4229
4230    #[test]
4231    fn a_budget_stops_a_long_parse_and_says_how_far_it_got() {
4232        let html = "<div><b>x</b> y</div>".repeat(200_000);
4233        let tight = Options {
4234            budget: Some(Duration::from_micros(50)),
4235            ..Options::default()
4236        };
4237        match parse_with(&html, tight) {
4238            Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
4239            other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
4240        }
4241        let roomy = Options {
4242            budget: Some(Duration::from_secs(60)),
4243            ..Options::default()
4244        };
4245        assert!(parse_with(&html, roomy).is_ok());
4246    }
4247    #[test]
4248    fn a_long_run_of_references_is_one_text_node() {
4249        // Longer than the tokenizer gathers before handing a run over.
4250        let html = "<p>".to_owned() + &"&amp;x&#169;&nbsp".repeat(20_000) + "<b>";
4251        let with_spans = Options {
4252            spans: true,
4253            errors: true,
4254            ..Options::default()
4255        };
4256        for doc in [parse(&html, false), parse_with(&html, with_spans).unwrap()] {
4257            let p = (0..doc.len() as NodeId)
4258                .find(|&n| doc.lower_name(n) == Some("p"))
4259                .unwrap();
4260            assert_eq!(doc.children(p).count(), 2);
4261            assert_eq!(doc.text(p), "&x\u{a9}\u{a0}".repeat(20_000));
4262        }
4263    }
4264
4265    #[test]
4266    fn max_depth_keeps_the_tree_shallow_and_every_element() {
4267        fn deepest(doc: &Document, id: NodeId) -> usize {
4268            1 + doc.children(id).map(|c| deepest(doc, c)).max().unwrap_or(0)
4269        }
4270        let html = "<div>".repeat(1_000) + "x" + &"</div>".repeat(1_000);
4271        let free = parse(&html, false);
4272        assert!(deepest(&free, free.root()) > 1_000);
4273        let capped = parse_with(
4274            &html,
4275            Options {
4276                max_depth: Some(100),
4277                ..Options::default()
4278            },
4279        )
4280        .unwrap();
4281        assert!(deepest(&capped, capped.root()) <= 102);
4282        // Every div is still there, with the text, just flatter.
4283        let divs = |doc: &Document| {
4284            (0..doc.len() as NodeId)
4285                .filter(|&n| doc.lower_name(n) == Some("div"))
4286                .count()
4287        };
4288        assert_eq!(divs(&capped), 1_000);
4289        assert!(capped.text(capped.root()).contains('x'));
4290        // Under the limit, nothing changes.
4291        let shallow = "<div><p>a<b>b</b></p></div>";
4292        let same = parse_with(
4293            shallow,
4294            Options {
4295                max_depth: Some(100),
4296                ..Options::default()
4297            },
4298        )
4299        .unwrap();
4300        let plain = parse(shallow, false);
4301        assert_eq!(same.inner_html(same.root()), plain.inner_html(plain.root()));
4302        // A limit of none at all still keeps every element, under the root.
4303        let at = |max_depth| {
4304            let doc = parse_with(
4305                shallow,
4306                Options {
4307                    max_depth: Some(max_depth),
4308                    ..Options::default()
4309                },
4310            )
4311            .unwrap();
4312            doc.inner_html(doc.root())
4313        };
4314        assert_eq!(at(0), at(1));
4315        assert!(at(0).contains("<div></div><p></p>a<b></b>b"), "{}", at(0));
4316    }
4317
4318    #[test]
4319    fn a_fragment_has_a_budget_and_a_size_limit_too() {
4320        let html = "<div><b>x</b> y</div>".repeat(200_000);
4321        let tight = Options {
4322            budget: Some(Duration::from_micros(50)),
4323            ..Options::default()
4324        };
4325        match parse_fragment_with(&html, Ns::Html, "div", tight) {
4326            Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
4327            other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
4328        }
4329        let doc = parse_fragment_with("<b>x</b>", Ns::Html, "div", Options::default()).unwrap();
4330        assert_eq!(doc.inner_html(doc.root()), "<b>x</b>");
4331        let huge = "x".repeat(crate::MAX_INPUT + 1);
4332        assert_eq!(
4333            parse_fragment_with(&huge, Ns::Html, "div", Options::default()).map(|d| d.len()),
4334            Err(ParseError::TooLarge { len: huge.len() })
4335        );
4336    }
4337
4338    #[test]
4339    fn a_leading_byte_order_mark_is_dropped_from_a_document() {
4340        let page = "<!DOCTYPE html><p>x</p>";
4341        let with = parse(&format!("\u{FEFF}{page}"), false);
4342        let without = parse(page, false);
4343        assert_eq!(with.quirks(), crate::Quirks::No);
4344        assert_eq!(
4345            with.inner_html(with.root()),
4346            without.inner_html(without.root())
4347        );
4348        // Only the first one goes; one later on is text like any other.
4349        let twice = parse("\u{FEFF}\u{FEFF}<p>x</p>", false);
4350        assert!(twice.inner_html(twice.root()).contains('\u{FEFF}'));
4351        // innerHTML doesn't decode, so a fragment keeps it.
4352        let fragment = parse_fragment("\u{FEFF}x", Ns::Html, "div", false);
4353        assert!(fragment.inner_html(fragment.root()).contains('\u{FEFF}'));
4354    }
4355
4356    #[test]
4357    fn a_budget_too_big_for_the_clock_is_no_limit() {
4358        let endless = Options {
4359            budget: Some(Duration::MAX),
4360            ..Options::default()
4361        };
4362        assert!(parse_with("<p>x", endless).is_ok());
4363    }
4364
4365    fn in_pieces(pieces: &[&str]) -> Document {
4366        let mut parser = Parser::new(Options::default());
4367        for piece in pieces {
4368            parser.feed(piece);
4369        }
4370        parser.finish().unwrap()
4371    }
4372
4373    #[test]
4374    fn the_tree_grows_as_the_pieces_come() {
4375        let mut parser = Parser::new(Options::default());
4376        parser.feed("<ul><li>one<li>tw");
4377        let early = parser.builder.doc.len();
4378        // html, head, body, ul, li, "one", li, and the text so far.
4379        assert_eq!(early, 9);
4380        parser.feed("o</ul><p a=\"x");
4381        // The p waits for the rest of its tag.
4382        assert_eq!(parser.builder.doc.len(), early);
4383        parser.feed("\">three");
4384        assert_eq!(parser.builder.doc.len(), early + 2);
4385        let doc = parser.finish().unwrap();
4386        assert_eq!(
4387            doc.inner_html(doc.root()),
4388            "<html><head></head><body><ul><li>one</li><li>two</li></ul>\
4389             <p a=\"x\">three</p></body></html>"
4390        );
4391    }
4392
4393    /// Found by fuzzing: in a template's column group, text after a
4394    /// character that isn't whitespace was all dropped, its whitespace
4395    /// too, so where a piece ended changed the tree.
4396    #[test]
4397    fn whitespace_after_a_dropped_character_in_a_template_column_group_stays() {
4398        let html = "<template><col>A \n<col></template>";
4399        let want = "<html><head><template><col> \n<col></template></head><body></body></html>";
4400        assert_eq!(parse(html, false).inner_html(0), want);
4401        let (a, b) = html.split_at(html.find(' ').unwrap());
4402        assert_eq!(in_pieces(&[a, b]).inner_html(0), want);
4403        let errors = parse_with(
4404            html,
4405            Options {
4406                errors: true,
4407                ..Options::default()
4408            },
4409        )
4410        .unwrap();
4411        let dropped = errors
4412            .errors()
4413            .iter()
4414            .filter(|e| e.code == "unexpected-character-in-colgroup");
4415        assert_eq!(dropped.count(), 1);
4416    }
4417
4418    #[test]
4419    fn a_cr_at_the_end_of_a_piece_waits_for_the_next() {
4420        let text = |doc: &Document| doc.text(doc.root());
4421        assert_eq!(text(&in_pieces(&["a\r", "\nb"])), "a\nb");
4422        assert_eq!(text(&in_pieces(&["a\r", "b"])), "a\nb");
4423        assert_eq!(text(&in_pieces(&["a\r", "", "\r\nb\r"])), "a\n\nb\n");
4424        // A `<pre>` drops one newline after it, a CRLF as much as an LF.
4425        let pre = in_pieces(&["<pre>\r", "\nx</pre>"]);
4426        assert_eq!(text(&pre), "x");
4427    }
4428
4429    #[test]
4430    fn a_byte_order_mark_is_dropped_from_a_documents_first_piece() {
4431        let whole = parse("<p>x", false);
4432        let pieces = in_pieces(&["", "\u{FEFF}", "<p>x"]);
4433        assert_eq!(pieces.inner_html(0), whole.inner_html(0));
4434        let mut fragment = Parser::fragment(Ns::Html, "div", Options::default());
4435        fragment.feed("\u{FEFF}x");
4436        let fragment = fragment.finish().unwrap();
4437        assert!(fragment.inner_html(0).contains('\u{FEFF}'));
4438    }
4439
4440    #[test]
4441    fn a_budget_and_the_size_limit_hold_for_pieces_too() {
4442        let tight = Options {
4443            budget: Some(Duration::from_micros(50)),
4444            ..Options::default()
4445        };
4446        let piece = "<div><b>x</b> y</div>".repeat(10_000);
4447        let mut parser = Parser::new(tight);
4448        for _ in 0..20 {
4449            parser.feed(&piece);
4450        }
4451        match parser.finish() {
4452            Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < piece.len() * 20),
4453            other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
4454        }
4455        let huge = "x".repeat(crate::MAX_INPUT);
4456        let mut parser = Parser::new(Options::default());
4457        parser.feed(&huge);
4458        parser.feed("xy");
4459        assert_eq!(
4460            parser.finish().map(|d| d.len()),
4461            Err(ParseError::TooLarge {
4462                len: crate::MAX_INPUT + 2
4463            })
4464        );
4465    }
4466}
4467
4468#[cfg(test)]
4469mod hostile {
4470    use super::*;
4471    use std::time::{Duration, Instant};
4472
4473    fn time(html: &str) -> Duration {
4474        let start = Instant::now();
4475        std::hint::black_box(parse(html, false));
4476        start.elapsed()
4477    }
4478
4479    /// Fails if four times the input takes more than eight times as long:
4480    /// linear work takes four, quadratic sixteen. The two sizes are timed
4481    /// back to back, five times, and one round inside the limit passes: a
4482    /// slow spell on a loaded machine that lands on the large parses only
4483    /// can't fail it, and quadratic work fails every round.
4484    fn grows_linearly(make: impl Fn(usize) -> String) {
4485        grows_linearly_timed(make, time);
4486    }
4487
4488    fn grows_linearly_timed(make: impl Fn(usize) -> String, time: fn(&str) -> Duration) {
4489        let (small, large) = (make(5_000), make(20_000));
4490        let rounds: Vec<_> = (0..5).map(|_| (time(&small), time(&large))).collect();
4491        assert!(
4492            rounds
4493                .iter()
4494                .any(|&(a, b)| b < a * 8 + Duration::from_millis(20)),
4495            "{} bytes, then {} bytes, took {rounds:?}",
4496            small.len(),
4497            large.len()
4498        );
4499    }
4500
4501    /// Parses `html` (ASCII) fed 64 bytes at a time.
4502    fn time_in_pieces(html: &str) -> Duration {
4503        let start = Instant::now();
4504        let mut parser = Parser::new(Options::default());
4505        for piece in html.as_bytes().chunks(64) {
4506            parser.feed(std::str::from_utf8(piece).unwrap());
4507        }
4508        std::hint::black_box(parser.finish().unwrap());
4509        start.elapsed()
4510    }
4511
4512    /// A token that goes on over many pieces is read once, not again from
4513    /// its start with each piece: a long attribute value, a long name, a
4514    /// comment, a character reference that's all digits.
4515    #[test]
4516    fn a_token_over_many_pieces_costs_linear_time() {
4517        let long = |open: &'static str, close: &'static str, fill: &'static str| {
4518            move |n: usize| format!("{open}{}{close}", fill.repeat(n * 10))
4519        };
4520        for make in [
4521            long("<a href=\"", "\">", "x"),
4522            long("<a href=", ">", "x"),
4523            long("<a ", ">", "b"),
4524            long("<", ">", "a"),
4525            long("<!--", "-->", "x"),
4526            long("<!DOCTYPE html PUBLIC \"", "\">", "x"),
4527            long("<?pi ", "?>", "x"),
4528            long("&#", ";", "1"),
4529            long("&", ";", "a"),
4530            long("<svg><![CDATA[", "]]>", "]"),
4531            long("<script>", "</script>", "<"),
4532        ] {
4533            grows_linearly_timed(make, time_in_pieces);
4534        }
4535    }
4536
4537    /// A selected option's contents are copied into `<selectedcontent>`
4538    /// as it closes, and the copy recursed once per level: a hundred
4539    /// kilobytes of nesting overflowed a thread's stack.
4540    #[test]
4541    fn copying_deep_option_contents_keeps_to_a_small_stack() {
4542        let html = format!(
4543            "<select><button><selectedcontent></selectedcontent></button><option>{}",
4544            "<div>".repeat(20_000)
4545        );
4546        let parsed = std::thread::Builder::new()
4547            .stack_size(256 * 1024)
4548            .spawn(move || parse(&html, false).len())
4549            .unwrap()
4550            .join()
4551            .unwrap();
4552        assert!(parsed > 40_000, "both copies are there: {parsed} nodes");
4553    }
4554
4555    /// An end tag nothing open matches walked the whole stack of open
4556    /// elements, for each such tag.
4557    #[test]
4558    fn unmatched_end_tags_under_deep_nesting_cost_linear_time() {
4559        grows_linearly(|n| format!("{}{}", "<span>".repeat(n), "</x>".repeat(n)));
4560        grows_linearly(|n| format!("{}{}", "<span>".repeat(n), "</p>".repeat(n)));
4561        grows_linearly(|n| format!("{}{}", "<x-a>".repeat(n), "</x-b>".repeat(n)));
4562    }
4563
4564    /// `</body>` and `</html>` asked whether body was in scope by walking
4565    /// the whole stack down to it; a heading end tag looked for any open
4566    /// heading the same way; and a `<table>` in a table reset the mode by
4567    /// walking down to body.
4568    #[test]
4569    fn end_tags_under_deep_nesting_cost_linear_time() {
4570        for end in ["</body>", "</html>", "</h1>", "<table>", "</body><p>"] {
4571            grows_linearly(|n| format!("{}{}", "<div>".repeat(n), end.repeat(n)));
4572            grows_linearly_timed(
4573                |n| format!("{}{}", "<div>".repeat(n), end.repeat(n)),
4574                time_with_errors,
4575            );
4576        }
4577        // Out of scope, behind an element that ends it.
4578        grows_linearly(|n| format!("<applet>{}{}", "<div>".repeat(n), "</body>".repeat(n)));
4579        grows_linearly(|n| format!("<table><td>{}{}", "<div>".repeat(n), "</td>".repeat(n)));
4580    }
4581
4582    fn time_with_errors(html: &str) -> Duration {
4583        let start = Instant::now();
4584        let options = Options {
4585            errors: true,
4586            ..Options::default()
4587        };
4588        std::hint::black_box(parse_with(html, options).unwrap());
4589        start.elapsed()
4590    }
4591
4592    /// The same, inside SVG, where an end tag is first looked for among
4593    /// the open foreign elements.
4594    #[test]
4595    fn unmatched_end_tags_in_deep_svg_cost_linear_time() {
4596        grows_linearly(|n| format!("<svg>{}{}", "<g>".repeat(n), "</x>".repeat(n)));
4597    }
4598
4599    /// Each option looked up the tree for a select, all the way up when
4600    /// there was none.
4601    #[test]
4602    fn options_under_deep_nesting_cost_linear_time() {
4603        grows_linearly(|n| format!("{}{}", "<div>".repeat(n), "<option>".repeat(n)));
4604    }
4605
4606    /// Each `<body X>` merges an attribute (copied into the parse buffer)
4607    /// and then text goes back into the same text node, so a text node
4608    /// copied whole on every append grew the buffer quadratically: 310 KB
4609    /// reached 1 GB and panicked.
4610    #[test]
4611    fn text_split_by_merged_attributes_costs_linear_memory() {
4612        let tail: String = (0..11_000).map(|i| format!("<body X{i}>b")).collect();
4613        let html = format!("<body>a&amp;{}{tail}", "x".repeat(100_000));
4614        let doc = parse(&html, false);
4615        assert!(doc.buf.len() + doc.extras.iter().map(|e| e.len()).sum::<usize>() < 4 * html.len());
4616        assert!(doc.text(0).ends_with('b'));
4617    }
4618
4619    fn attributes(n: usize) -> String {
4620        (0..n).map(|i| format!(" a{i}=1")).collect()
4621    }
4622
4623    /// Each attribute was checked against every one before it for a
4624    /// duplicate, and each merge into `<body>` against all it had.
4625    #[test]
4626    fn many_attributes_cost_linear_time() {
4627        grows_linearly(|n| format!("<p{}>", attributes(n)));
4628        grows_linearly(|n| format!("<p{}&amp;>", attributes(n)));
4629        grows_linearly(|n| format!("<svg{}>", attributes(n)));
4630        grows_linearly(|n| format!("<body{0}><body{0}>", attributes(n / 2)));
4631        // Text between merges moved all of body's attributes to the end of
4632        // the list each time.
4633        grows_linearly(|n| {
4634            (0..n / 4)
4635                .map(|i| format!("<body x{i}=1><p a=1>"))
4636                .collect()
4637        });
4638        let doc = parse("<body a=1><p b=2><body c=3 a=4><i d=5><body e=6>", false);
4639        let body = (0..doc.len() as NodeId)
4640            .find(|&n| doc.lower_name(n) == Some("body"))
4641            .unwrap();
4642        let attrs: Vec<_> = doc.attrs(body).map(|(_, n, v)| (n, v)).collect();
4643        assert_eq!(attrs, [("a", "1"), ("c", "3"), ("e", "6")]);
4644    }
4645
4646    /// One tag of a million attributes is one step of the tokenizer,
4647    /// which read the clock only between steps.
4648    #[test]
4649    fn a_budget_holds_inside_a_tag_of_many_attributes() {
4650        let none = Options {
4651            budget: Some(Duration::ZERO),
4652            ..Options::default()
4653        };
4654        for html in [
4655            format!("<p{}>", attributes(300_000)),
4656            format!("<p{}&amp;>", attributes(300_000)),
4657        ] {
4658            match parse_with(&html, none) {
4659                Err(ParseError::Timeout { parsed, .. }) => assert!(parsed < html.len()),
4660                other => panic!("expected a timeout, got {:?}", other.map(|d| d.len())),
4661            }
4662        }
4663    }
4664
4665    /// The end of the input closed one open template and read the end
4666    /// again, a call deeper each time: 40,000 nested templates overflowed
4667    /// an 8 MB stack.
4668    #[test]
4669    fn the_end_of_input_under_deep_templates_keeps_to_a_small_stack() {
4670        for unit in [
4671            "<template>",
4672            "<div><template shadowrootmode=open>",
4673            "<table><caption><template>",
4674            "<template><tr>",
4675            "<template><col>",
4676            "<template><td>",
4677        ] {
4678            let html = unit.repeat(100_000);
4679            let sizes = std::thread::Builder::new()
4680                .stack_size(256 * 1024)
4681                .spawn(move || {
4682                    let doc = parse(&html, false);
4683                    let fragment = parse_fragment(&html, Ns::Html, "div", false);
4684                    let with_errors = Options {
4685                        errors: true,
4686                        max_depth: Some(512),
4687                        ..Options::default()
4688                    };
4689                    let checked = parse_with(&html, with_errors).unwrap();
4690                    (doc.len(), fragment.len(), checked.errors().len())
4691                })
4692                .unwrap()
4693                .join()
4694                .unwrap();
4695            assert!(sizes.0 > 100_000 && sizes.1 > 100_000, "{unit}: {sizes:?}");
4696            assert!(sizes.2 >= 100_000, "{unit}: an error for each template");
4697        }
4698    }
4699}