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