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