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