html5ever/tree_builder/
mod.rs

1// Copyright 2014-2017 The html5ever Project Developers. See the
2// COPYRIGHT file at the top-level directory of this distribution.
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10//! The HTML5 tree builder.
11
12pub use crate::interface::{create_element, ElemName, ElementFlags, Tracer, TreeSink};
13pub use crate::interface::{AppendNode, AppendText, Attribute, NodeOrText};
14pub use crate::interface::{LimitedQuirks, NoQuirks, Quirks, QuirksMode};
15
16use self::types::*;
17
18use crate::tendril::StrTendril;
19use crate::{ExpandedName, LocalName, Namespace, QualName};
20
21use crate::tokenizer;
22use crate::tokenizer::states as tok_state;
23use crate::tokenizer::{Doctype, EndTag, StartTag, Tag, TokenSink, TokenSinkResult};
24
25use std::borrow::Cow::{self, Borrowed};
26use std::cell::{Cell, Ref, RefCell};
27use std::collections::VecDeque;
28use std::iter::{Enumerate, Rev};
29use std::{fmt, slice};
30
31use crate::tokenizer::states::RawKind;
32use crate::tree_builder::tag_sets::*;
33use crate::util::str::to_escaped_string;
34use log::{debug, log_enabled, warn, Level};
35use markup5ever::{expanded_name, local_name, namespace_prefix, ns};
36
37#[macro_use]
38mod tag_sets;
39
40mod data;
41mod rules;
42mod types;
43
44/// Tree builder options, with an impl for Default.
45#[derive(Copy, Clone)]
46pub struct TreeBuilderOpts {
47    /// Report all parse errors described in the spec, at some
48    /// performance penalty? Default: false
49    pub exact_errors: bool,
50
51    /// Is scripting enabled?
52    ///
53    /// This affects how `<noscript>` elements are parsed:
54    ///   - If scripting **is** enabled then the contents of a `<noscript>` element are parsed as a single text node
55    ///   - If scriping is **not** enabled then the contents of a `<noscript>` element are parsed as a normal tree of nodes
56    pub scripting_enabled: bool,
57
58    /// Is this document being parsed from the `srcdoc` attribute of an `<iframe>` element?
59    ///
60    /// This affects heuristics that infer `QuirksMode` from `<!DOCTYPE>`.
61    pub iframe_srcdoc: bool,
62
63    /// Should we drop the DOCTYPE (if any) from the tree?
64    pub drop_doctype: bool,
65
66    /// Initial TreeBuilder quirks mode. Default: NoQuirks
67    pub quirks_mode: QuirksMode,
68}
69
70impl Default for TreeBuilderOpts {
71    fn default() -> TreeBuilderOpts {
72        TreeBuilderOpts {
73            exact_errors: false,
74            scripting_enabled: true,
75            iframe_srcdoc: false,
76            drop_doctype: false,
77            quirks_mode: NoQuirks,
78        }
79    }
80}
81
82/// The HTML tree builder.
83pub struct TreeBuilder<Handle, Sink> {
84    /// Options controlling the behavior of the tree builder.
85    opts: TreeBuilderOpts,
86
87    /// Consumer of tree modifications.
88    pub sink: Sink,
89
90    /// Insertion mode.
91    mode: Cell<InsertionMode>,
92
93    /// Original insertion mode, used by Text and InTableText modes.
94    orig_mode: Cell<Option<InsertionMode>>,
95
96    /// Stack of template insertion modes.
97    template_modes: RefCell<Vec<InsertionMode>>,
98
99    /// Pending table character tokens.
100    pending_table_text: RefCell<Vec<(SplitStatus, StrTendril)>>,
101
102    /// Quirks mode as set by the parser.
103    /// FIXME: can scripts etc. change this?
104    quirks_mode: Cell<QuirksMode>,
105
106    /// The document node, which is created by the sink.
107    doc_handle: Handle,
108
109    /// Stack of open elements, most recently added at end.
110    open_elems: RefCell<Vec<Handle>>,
111
112    /// List of active formatting elements.
113    active_formatting: RefCell<Vec<FormatEntry<Handle>>>,
114
115    //§ the-element-pointers
116    /// Head element pointer.
117    head_elem: RefCell<Option<Handle>>,
118
119    /// Form element pointer.
120    form_elem: RefCell<Option<Handle>>,
121    //§ END
122    /// Frameset-ok flag.
123    frameset_ok: Cell<bool>,
124
125    /// Ignore a following U+000A LINE FEED?
126    ignore_lf: Cell<bool>,
127
128    /// Is foster parenting enabled?
129    foster_parenting: Cell<bool>,
130
131    /// The context element for the fragment parsing algorithm.
132    context_elem: RefCell<Option<Handle>>,
133
134    /// Track current line
135    current_line: Cell<u64>,
136    // WARNING: If you add new fields that contain Handles, you
137    // must add them to trace_handles() below to preserve memory
138    // safety!
139    //
140    // FIXME: Auto-generate the trace hooks like Servo does.
141}
142
143impl<Handle, Sink> TreeBuilder<Handle, Sink>
144where
145    Handle: Clone,
146    Sink: TreeSink<Handle = Handle>,
147{
148    /// Create a new tree builder which sends tree modifications to a particular `TreeSink`.
149    ///
150    /// The tree builder is also a `TokenSink`.
151    pub fn new(sink: Sink, opts: TreeBuilderOpts) -> TreeBuilder<Handle, Sink> {
152        let doc_handle = sink.get_document();
153        TreeBuilder {
154            opts,
155            sink,
156            mode: Cell::new(InsertionMode::Initial),
157            orig_mode: Cell::new(None),
158            template_modes: Default::default(),
159            pending_table_text: Default::default(),
160            quirks_mode: Cell::new(opts.quirks_mode),
161            doc_handle,
162            open_elems: Default::default(),
163            active_formatting: Default::default(),
164            head_elem: Default::default(),
165            form_elem: Default::default(),
166            frameset_ok: Cell::new(true),
167            ignore_lf: Default::default(),
168            foster_parenting: Default::default(),
169            context_elem: Default::default(),
170            current_line: Cell::new(1),
171        }
172    }
173
174    /// Create a new tree builder which sends tree modifications to a particular `TreeSink`.
175    /// This is for parsing fragments.
176    ///
177    /// The tree builder is also a `TokenSink`.
178    pub fn new_for_fragment(
179        sink: Sink,
180        context_elem: Handle,
181        form_elem: Option<Handle>,
182        opts: TreeBuilderOpts,
183    ) -> TreeBuilder<Handle, Sink> {
184        let doc_handle = sink.get_document();
185        let context_is_template =
186            sink.elem_name(&context_elem).expanded() == expanded_name!(html "template");
187        let template_modes = if context_is_template {
188            RefCell::new(vec![InsertionMode::InTemplate])
189        } else {
190            RefCell::new(vec![])
191        };
192
193        let tb = TreeBuilder {
194            opts,
195            sink,
196            mode: Cell::new(InsertionMode::Initial),
197            orig_mode: Cell::new(None),
198            template_modes,
199            pending_table_text: Default::default(),
200            quirks_mode: Cell::new(opts.quirks_mode),
201            doc_handle,
202            open_elems: Default::default(),
203            active_formatting: Default::default(),
204            head_elem: Default::default(),
205            form_elem: RefCell::new(form_elem),
206            frameset_ok: Cell::new(true),
207            ignore_lf: Default::default(),
208            foster_parenting: Default::default(),
209            context_elem: RefCell::new(Some(context_elem)),
210            current_line: Cell::new(1),
211        };
212
213        // https://html.spec.whatwg.org/multipage/#parsing-html-fragments
214        // 5. Let root be a new html element with no attributes.
215        // 6. Append the element root to the Document node created above.
216        // 7. Set up the parser's stack of open elements so that it contains just the single element root.
217        tb.create_root(vec![]);
218        // 10. Reset the parser's insertion mode appropriately.
219        let old_insertion_mode = tb.reset_insertion_mode();
220        tb.mode.set(old_insertion_mode);
221
222        tb
223    }
224
225    // https://html.spec.whatwg.org/multipage/#concept-frag-parse-context
226    // Step 4. Set the state of the HTML parser's tokenization stage as follows:
227    pub fn tokenizer_state_for_context_elem(
228        &self,
229        context_element_allows_scripting: bool,
230    ) -> tok_state::State {
231        let context_elem = self.context_elem.borrow();
232        let elem = context_elem.as_ref().expect("no context element");
233        let elem_name = self.sink.elem_name(elem);
234        let name = match elem_name.expanded() {
235            ExpandedName {
236                ns: &ns!(html),
237                local,
238            } => local,
239            _ => return tok_state::Data,
240        };
241        match *name {
242            local_name!("title") | local_name!("textarea") => tok_state::RawData(tok_state::Rcdata),
243
244            local_name!("style")
245            | local_name!("xmp")
246            | local_name!("iframe")
247            | local_name!("noembed")
248            | local_name!("noframes") => tok_state::RawData(tok_state::Rawtext),
249
250            local_name!("script") => tok_state::RawData(tok_state::ScriptData),
251
252            local_name!("noscript") => {
253                if context_element_allows_scripting {
254                    tok_state::RawData(tok_state::Rawtext)
255                } else {
256                    tok_state::Data
257                }
258            },
259
260            local_name!("plaintext") => tok_state::Plaintext,
261
262            _ => tok_state::Data,
263        }
264    }
265
266    /// Call the `Tracer`'s `trace_handle` method on every `Handle` in the tree builder's
267    /// internal state.  This is intended to support garbage-collected DOMs.
268    pub fn trace_handles(&self, tracer: &dyn Tracer<Handle = Handle>) {
269        tracer.trace_handle(&self.doc_handle);
270        for e in &*self.open_elems.borrow() {
271            tracer.trace_handle(e);
272        }
273
274        for e in &*self.active_formatting.borrow() {
275            if let FormatEntry::Element(handle, _) = e {
276                tracer.trace_handle(handle);
277            }
278        }
279
280        if let Some(head_elem) = self.head_elem.borrow().as_ref() {
281            tracer.trace_handle(head_elem);
282        }
283
284        if let Some(form_elem) = self.form_elem.borrow().as_ref() {
285            tracer.trace_handle(form_elem);
286        }
287
288        if let Some(context_elem) = self.context_elem.borrow().as_ref() {
289            tracer.trace_handle(context_elem);
290        }
291    }
292
293    #[allow(dead_code)]
294    fn dump_state(&self, label: String) {
295        println!("dump_state on {label}");
296        print!("    open_elems:");
297        for node in self.open_elems.borrow().iter() {
298            let name = self.sink.elem_name(node);
299            match *name.ns() {
300                ns!(html) => print!(" {}", name.local_name()),
301                _ => panic!(),
302            }
303        }
304        println!();
305        print!("    active_formatting:");
306        for entry in self.active_formatting.borrow().iter() {
307            match entry {
308                &FormatEntry::Marker => print!(" Marker"),
309                FormatEntry::Element(h, _) => {
310                    let name = self.sink.elem_name(h);
311                    match *name.ns() {
312                        ns!(html) => print!(" {}", name.local_name()),
313                        _ => panic!(),
314                    }
315                },
316            }
317        }
318        println!();
319    }
320
321    fn debug_step(&self, mode: InsertionMode, token: &Token) {
322        if log_enabled!(Level::Debug) {
323            debug!(
324                "processing {} in insertion mode {:?}",
325                to_escaped_string(token),
326                mode
327            );
328        }
329    }
330
331    fn process_to_completion(&self, mut token: Token) -> TokenSinkResult<Handle> {
332        // Queue of additional tokens yet to be processed.
333        // This stays empty in the common case where we don't split whitespace.
334        let mut more_tokens = VecDeque::new();
335
336        loop {
337            let should_have_acknowledged_self_closing_flag = matches!(
338                token,
339                Token::Tag(Tag {
340                    self_closing: true,
341                    kind: StartTag,
342                    ..
343                })
344            );
345            let result = if self.is_foreign(&token) {
346                self.step_foreign(token)
347            } else {
348                let mode = self.mode.get();
349                self.step(mode, token)
350            };
351            match result {
352                ProcessResult::Done => {
353                    if should_have_acknowledged_self_closing_flag {
354                        self.sink
355                            .parse_error(Borrowed("Unacknowledged self-closing tag"));
356                    }
357                    let Some(new_token) = more_tokens.pop_front() else {
358                        return tokenizer::TokenSinkResult::Continue;
359                    };
360                    token = new_token;
361                },
362                ProcessResult::DoneAckSelfClosing => {
363                    let Some(new_token) = more_tokens.pop_front() else {
364                        return tokenizer::TokenSinkResult::Continue;
365                    };
366                    token = new_token;
367                },
368                ProcessResult::Reprocess(m, t) => {
369                    self.mode.set(m);
370                    token = t;
371                },
372                ProcessResult::ReprocessForeign(t) => {
373                    token = t;
374                },
375                ProcessResult::SplitWhitespace(mut buf) => {
376                    let p = buf.pop_front_char_run(|c| c.is_ascii_whitespace());
377                    let Some((first, is_ws)) = p else {
378                        return tokenizer::TokenSinkResult::Continue;
379                    };
380                    let status = if is_ws {
381                        SplitStatus::Whitespace
382                    } else {
383                        SplitStatus::NotWhitespace
384                    };
385                    token = Token::Characters(status, first);
386
387                    if buf.len32() > 0 {
388                        more_tokens.push_back(Token::Characters(SplitStatus::NotSplit, buf));
389                    }
390                },
391                ProcessResult::Script(node) => {
392                    assert!(more_tokens.is_empty());
393                    return tokenizer::TokenSinkResult::Script(node);
394                },
395                ProcessResult::ToPlaintext => {
396                    assert!(more_tokens.is_empty());
397                    return tokenizer::TokenSinkResult::Plaintext;
398                },
399                ProcessResult::ToRawData(k) => {
400                    assert!(more_tokens.is_empty());
401                    return tokenizer::TokenSinkResult::RawData(k);
402                },
403            }
404        }
405    }
406
407    /// Are we parsing a HTML fragment?
408    pub fn is_fragment(&self) -> bool {
409        self.context_elem.borrow().is_some()
410    }
411
412    /// https://html.spec.whatwg.org/multipage/#appropriate-place-for-inserting-a-node
413    fn appropriate_place_for_insertion(
414        &self,
415        override_target: Option<Handle>,
416    ) -> InsertionPoint<Handle> {
417        use self::tag_sets::*;
418
419        declare_tag_set!(foster_target = "table" "tbody" "tfoot" "thead" "tr");
420        let target = override_target.unwrap_or_else(|| self.current_node().clone());
421        if !(self.foster_parenting.get() && self.elem_in(&target, foster_target)) {
422            if self.html_elem_named(&target, local_name!("template")) {
423                // No foster parenting (inside template).
424                let contents = self.sink.get_template_contents(&target);
425                return InsertionPoint::LastChild(contents);
426            } else {
427                // No foster parenting (the common case).
428                return InsertionPoint::LastChild(target);
429            }
430        }
431
432        // Foster parenting
433        let open_elems = self.open_elems.borrow();
434        let mut iter = open_elems.iter().rev().peekable();
435        while let Some(elem) = iter.next() {
436            if self.html_elem_named(elem, local_name!("template")) {
437                let contents = self.sink.get_template_contents(elem);
438                return InsertionPoint::LastChild(contents);
439            } else if self.html_elem_named(elem, local_name!("table")) {
440                return InsertionPoint::TableFosterParenting {
441                    element: elem.clone(),
442                    prev_element: (*iter.peek().unwrap()).clone(),
443                };
444            }
445        }
446        let html_elem = self.html_elem();
447        InsertionPoint::LastChild(html_elem.clone())
448    }
449
450    fn insert_at(&self, insertion_point: InsertionPoint<Handle>, child: NodeOrText<Handle>) {
451        match insertion_point {
452            InsertionPoint::LastChild(parent) => self.sink.append(&parent, child),
453            InsertionPoint::BeforeSibling(sibling) => {
454                self.sink.append_before_sibling(&sibling, child)
455            },
456            InsertionPoint::TableFosterParenting {
457                element,
458                prev_element,
459            } => self
460                .sink
461                .append_based_on_parent_node(&element, &prev_element, child),
462        }
463    }
464}
465
466impl<Handle, Sink> TokenSink for TreeBuilder<Handle, Sink>
467where
468    Handle: Clone,
469    Sink: TreeSink<Handle = Handle>,
470{
471    type Handle = Handle;
472
473    fn process_token(&self, token: tokenizer::Token, line_number: u64) -> TokenSinkResult<Handle> {
474        if line_number != self.current_line.get() {
475            self.sink.set_current_line(line_number);
476        }
477        let ignore_lf = self.ignore_lf.take();
478
479        // Handle `ParseError` and `DoctypeToken`; convert everything else to the local `Token` type.
480        let token = match token {
481            tokenizer::ParseError(e) => {
482                self.sink.parse_error(e);
483                return tokenizer::TokenSinkResult::Continue;
484            },
485
486            tokenizer::DoctypeToken(dt) => {
487                if self.mode.get() == InsertionMode::Initial {
488                    let (err, quirk) = data::doctype_error_and_quirks(&dt, self.opts.iframe_srcdoc);
489                    if err {
490                        self.sink.parse_error(if self.opts.exact_errors {
491                            Cow::from(format!("Bad DOCTYPE: {dt:?}"))
492                        } else {
493                            Cow::from("Bad DOCTYPE")
494                        });
495                    }
496                    let Doctype {
497                        name,
498                        public_id,
499                        system_id,
500                        force_quirks: _,
501                    } = dt;
502                    if !self.opts.drop_doctype {
503                        self.sink.append_doctype_to_document(
504                            name.unwrap_or(StrTendril::new()),
505                            public_id.unwrap_or(StrTendril::new()),
506                            system_id.unwrap_or(StrTendril::new()),
507                        );
508                    }
509                    self.set_quirks_mode(quirk);
510
511                    self.mode.set(InsertionMode::BeforeHtml);
512                    return tokenizer::TokenSinkResult::Continue;
513                } else {
514                    self.sink.parse_error(if self.opts.exact_errors {
515                        Cow::from(format!("DOCTYPE in insertion mode {:?}", self.mode.get()))
516                    } else {
517                        Cow::from("DOCTYPE in body")
518                    });
519                    return tokenizer::TokenSinkResult::Continue;
520                }
521            },
522
523            tokenizer::TagToken(x) => Token::Tag(x),
524            tokenizer::CommentToken(x) => Token::Comment(x),
525            tokenizer::NullCharacterToken => Token::NullCharacter,
526            tokenizer::EOFToken => Token::Eof,
527
528            tokenizer::CharacterTokens(mut x) => {
529                if ignore_lf && x.starts_with("\n") {
530                    x.pop_front(1);
531                }
532                if x.is_empty() {
533                    return tokenizer::TokenSinkResult::Continue;
534                }
535                Token::Characters(SplitStatus::NotSplit, x)
536            },
537        };
538
539        self.process_to_completion(token)
540    }
541
542    fn end(&self) {
543        for elem in self.open_elems.borrow_mut().drain(..).rev() {
544            self.sink.pop(&elem);
545        }
546    }
547
548    fn adjusted_current_node_present_but_not_in_html_namespace(&self) -> bool {
549        !self.open_elems.borrow().is_empty()
550            && *self.sink.elem_name(&self.adjusted_current_node()).ns() != ns!(html)
551    }
552}
553
554pub fn html_elem<Handle>(open_elems: &[Handle]) -> &Handle {
555    &open_elems[0]
556}
557
558struct ActiveFormattingView<'a, Handle: 'a> {
559    data: Ref<'a, Vec<FormatEntry<Handle>>>,
560}
561
562impl<'a, Handle: 'a> ActiveFormattingView<'a, Handle> {
563    fn iter(&'a self) -> impl Iterator<Item = (usize, &'a Handle, &'a Tag)> + 'a {
564        ActiveFormattingIter {
565            iter: self.data.iter().enumerate().rev(),
566        }
567    }
568}
569
570pub struct ActiveFormattingIter<'a, Handle: 'a> {
571    iter: Rev<Enumerate<slice::Iter<'a, FormatEntry<Handle>>>>,
572}
573
574impl<'a, Handle> Iterator for ActiveFormattingIter<'a, Handle> {
575    type Item = (usize, &'a Handle, &'a Tag);
576    fn next(&mut self) -> Option<(usize, &'a Handle, &'a Tag)> {
577        match self.iter.next() {
578            None | Some((_, &FormatEntry::Marker)) => None,
579            Some((i, FormatEntry::Element(h, t))) => Some((i, h, t)),
580        }
581    }
582}
583
584pub enum PushFlag {
585    Push,
586    NoPush,
587}
588
589enum Bookmark<Handle> {
590    Replace(Handle),
591    InsertAfter(Handle),
592}
593
594macro_rules! qualname {
595    ("", $local:tt) => {
596        QualName {
597            prefix: None,
598            ns: ns!(),
599            local: local_name!($local),
600        }
601    };
602    ($prefix: tt $ns:tt $local:tt) => {
603        QualName {
604            prefix: Some(namespace_prefix!($prefix)),
605            ns: ns!($ns),
606            local: local_name!($local),
607        }
608    };
609}
610
611#[doc(hidden)]
612impl<Handle, Sink> TreeBuilder<Handle, Sink>
613where
614    Handle: Clone,
615    Sink: TreeSink<Handle = Handle>,
616{
617    fn unexpected<T: fmt::Debug>(&self, _thing: &T) -> ProcessResult<Handle> {
618        self.sink.parse_error(if self.opts.exact_errors {
619            Cow::from(format!(
620                "Unexpected token {} in insertion mode {:?}",
621                to_escaped_string(_thing),
622                self.mode.get()
623            ))
624        } else {
625            Cow::from("Unexpected token")
626        });
627        ProcessResult::Done
628    }
629
630    fn assert_named(&self, node: &Handle, name: LocalName) {
631        assert!(self.html_elem_named(node, name));
632    }
633
634    /// Iterate over the active formatting elements (with index in the list) from the end
635    /// to the last marker, or the beginning if there are no markers.
636    fn active_formatting_end_to_marker(&self) -> ActiveFormattingView<'_, Handle> {
637        ActiveFormattingView {
638            data: self.active_formatting.borrow(),
639        }
640    }
641
642    fn position_in_active_formatting(&self, element: &Handle) -> Option<usize> {
643        self.active_formatting
644            .borrow()
645            .iter()
646            .position(|n| match n {
647                FormatEntry::Marker => false,
648                FormatEntry::Element(ref handle, _) => self.sink.same_node(handle, element),
649            })
650    }
651
652    fn set_quirks_mode(&self, mode: QuirksMode) {
653        self.quirks_mode.set(mode);
654        self.sink.set_quirks_mode(mode);
655    }
656
657    fn stop_parsing(&self) -> ProcessResult<Handle> {
658        ProcessResult::Done
659    }
660
661    //§ parsing-elements-that-contain-only-text
662    // Switch to `Text` insertion mode, save the old mode, and
663    // switch the tokenizer to a raw-data state.
664    // The latter only takes effect after the current / next
665    // `process_token` of a start tag returns!
666    fn to_raw_text_mode(&self, k: RawKind) -> ProcessResult<Handle> {
667        self.orig_mode.set(Some(self.mode.get()));
668        self.mode.set(InsertionMode::Text);
669        ProcessResult::ToRawData(k)
670    }
671
672    // The generic raw text / RCDATA parsing algorithm.
673    fn parse_raw_data(&self, tag: Tag, k: RawKind) -> ProcessResult<Handle> {
674        self.insert_element_for(tag);
675        self.to_raw_text_mode(k)
676    }
677    //§ END
678
679    fn current_node(&self) -> Ref<'_, Handle> {
680        Ref::map(self.open_elems.borrow(), |elems| {
681            elems.last().expect("no current element")
682        })
683    }
684
685    fn adjusted_current_node(&self) -> Ref<'_, Handle> {
686        if self.open_elems.borrow().len() == 1 {
687            let context_elem = self.context_elem.borrow();
688            let ctx = Ref::filter_map(context_elem, |e| e.as_ref());
689            if let Ok(ctx) = ctx {
690                return ctx;
691            }
692        }
693        self.current_node()
694    }
695
696    fn current_node_in<TagSet>(&self, set: TagSet) -> bool
697    where
698        TagSet: Fn(ExpandedName) -> bool,
699    {
700        set(self.sink.elem_name(&self.current_node()).expanded())
701    }
702
703    // Insert at the "appropriate place for inserting a node".
704    fn insert_appropriately(&self, child: NodeOrText<Handle>, override_target: Option<Handle>) {
705        let insertion_point = self.appropriate_place_for_insertion(override_target);
706        self.insert_at(insertion_point, child);
707    }
708
709    fn adoption_agency(&self, subject: LocalName) {
710        // 1.
711        if self.current_node_named(subject.clone())
712            && self
713                .position_in_active_formatting(&self.current_node())
714                .is_none()
715        {
716            self.pop();
717            return;
718        }
719
720        // 2. 3. 4.
721        for _ in 0..8 {
722            // 5.
723            // We clone the Handle and Tag so they don't cause an immutable borrow of self.
724            let maybe_fmt_entry = self
725                .active_formatting_end_to_marker()
726                .iter()
727                .find(|&(_, _, tag)| tag.name == subject)
728                .map(|(i, h, t)| (i, h.clone(), t.clone()));
729
730            let Some((fmt_elem_index, fmt_elem, fmt_elem_tag)) = maybe_fmt_entry else {
731                return self.process_end_tag_in_body(Tag {
732                    kind: EndTag,
733                    name: subject,
734                    self_closing: false,
735                    attrs: vec![],
736                });
737            };
738
739            let Some(fmt_elem_stack_index) = self
740                .open_elems
741                .borrow()
742                .iter()
743                .rposition(|n| self.sink.same_node(n, &fmt_elem))
744            else {
745                self.sink
746                    .parse_error(Borrowed("Formatting element not open"));
747                self.active_formatting.borrow_mut().remove(fmt_elem_index);
748                return;
749            };
750
751            // 7.
752            if !self.in_scope(default_scope, |n| self.sink.same_node(&n, &fmt_elem)) {
753                self.sink
754                    .parse_error(Borrowed("Formatting element not in scope"));
755                return;
756            }
757
758            // 8.
759            if !self.sink.same_node(&self.current_node(), &fmt_elem) {
760                self.sink
761                    .parse_error(Borrowed("Formatting element not current node"));
762            }
763
764            // 9.
765            let maybe_furthest_block = self
766                .open_elems
767                .borrow()
768                .iter()
769                .enumerate()
770                .skip(fmt_elem_stack_index)
771                .find(|&(_, open_element)| self.elem_in(open_element, special_tag))
772                .map(|(i, h)| (i, h.clone()));
773
774            let Some((furthest_block_index, furthest_block)) = maybe_furthest_block else {
775                // 10.
776                self.open_elems.borrow_mut().truncate(fmt_elem_stack_index);
777                self.active_formatting.borrow_mut().remove(fmt_elem_index);
778                return;
779            };
780
781            // 11.
782            let common_ancestor = self.open_elems.borrow()[fmt_elem_stack_index - 1].clone();
783
784            // 12.
785            let mut bookmark = Bookmark::Replace(fmt_elem.clone());
786
787            // 13.
788            let mut node;
789            let mut node_index = furthest_block_index;
790            let mut last_node = furthest_block.clone();
791
792            // 13.1.
793            let mut inner_counter = 0;
794            loop {
795                // 13.2.
796                inner_counter += 1;
797
798                // 13.3.
799                node_index -= 1;
800                node = self.open_elems.borrow()[node_index].clone();
801
802                // 13.4.
803                if self.sink.same_node(&node, &fmt_elem) {
804                    break;
805                }
806
807                // 13.5.
808                if inner_counter > 3 {
809                    self.position_in_active_formatting(&node)
810                        .map(|position| self.active_formatting.borrow_mut().remove(position));
811                    self.open_elems.borrow_mut().remove(node_index);
812                    continue;
813                }
814
815                let Some(node_formatting_index) = self.position_in_active_formatting(&node) else {
816                    // 13.6.
817                    self.open_elems.borrow_mut().remove(node_index);
818                    continue;
819                };
820
821                // 13.7.
822                let tag = match self.active_formatting.borrow()[node_formatting_index] {
823                    FormatEntry::Element(ref h, ref t) => {
824                        assert!(self.sink.same_node(h, &node));
825                        t.clone()
826                    },
827                    FormatEntry::Marker => panic!("Found marker during adoption agency"),
828                };
829                // FIXME: Is there a way to avoid cloning the attributes twice here (once on their
830                // own, once as part of t.clone() above)?
831                let new_element = create_element(
832                    &self.sink,
833                    QualName::new(None, ns!(html), tag.name.clone()),
834                    tag.attrs.clone(),
835                );
836                self.open_elems.borrow_mut()[node_index] = new_element.clone();
837                self.active_formatting.borrow_mut()[node_formatting_index] =
838                    FormatEntry::Element(new_element.clone(), tag);
839                node = new_element;
840
841                // 13.8.
842                if self.sink.same_node(&last_node, &furthest_block) {
843                    bookmark = Bookmark::InsertAfter(node.clone());
844                }
845
846                // 13.9.
847                self.sink.remove_from_parent(&last_node);
848                self.sink.append(&node, AppendNode(last_node.clone()));
849
850                // 13.10.
851                last_node = node.clone();
852
853                // 13.11.
854            }
855
856            // 14.
857            self.sink.remove_from_parent(&last_node);
858            self.insert_appropriately(AppendNode(last_node.clone()), Some(common_ancestor));
859
860            // 15.
861            // FIXME: Is there a way to avoid cloning the attributes twice here (once on their own,
862            // once as part of t.clone() above)?
863            let new_element = create_element(
864                &self.sink,
865                QualName::new(None, ns!(html), fmt_elem_tag.name.clone()),
866                fmt_elem_tag.attrs.clone(),
867            );
868            let new_entry = FormatEntry::Element(new_element.clone(), fmt_elem_tag);
869
870            // 16.
871            self.sink.reparent_children(&furthest_block, &new_element);
872
873            // 17.
874            self.sink
875                .append(&furthest_block, AppendNode(new_element.clone()));
876
877            // 18.
878            // FIXME: We could probably get rid of the position_in_active_formatting() calls here
879            // if we had a more clever Bookmark representation.
880            match bookmark {
881                Bookmark::Replace(to_replace) => {
882                    let index = self
883                        .position_in_active_formatting(&to_replace)
884                        .expect("bookmark not found in active formatting elements");
885                    self.active_formatting.borrow_mut()[index] = new_entry;
886                },
887                Bookmark::InsertAfter(previous) => {
888                    let index = self
889                        .position_in_active_formatting(&previous)
890                        .expect("bookmark not found in active formatting elements")
891                        + 1;
892                    self.active_formatting.borrow_mut().insert(index, new_entry);
893                    let old_index = self
894                        .position_in_active_formatting(&fmt_elem)
895                        .expect("formatting element not found in active formatting elements");
896                    self.active_formatting.borrow_mut().remove(old_index);
897                },
898            }
899
900            // 19.
901            self.remove_from_stack(&fmt_elem);
902            let new_furthest_block_index = self
903                .open_elems
904                .borrow()
905                .iter()
906                .position(|n| self.sink.same_node(n, &furthest_block))
907                .expect("furthest block missing from open element stack");
908            self.open_elems
909                .borrow_mut()
910                .insert(new_furthest_block_index + 1, new_element);
911
912            // 20.
913        }
914    }
915
916    fn push(&self, elem: &Handle) {
917        self.open_elems.borrow_mut().push(elem.clone());
918    }
919
920    fn pop(&self) -> Handle {
921        let elem = self
922            .open_elems
923            .borrow_mut()
924            .pop()
925            .expect("no current element");
926        self.sink.pop(&elem);
927        elem
928    }
929
930    fn remove_from_stack(&self, elem: &Handle) {
931        let position = self
932            .open_elems
933            .borrow()
934            .iter()
935            .rposition(|x| self.sink.same_node(elem, x));
936        if let Some(position) = position {
937            self.open_elems.borrow_mut().remove(position);
938            self.sink.pop(elem);
939        }
940    }
941
942    fn is_marker_or_open(&self, entry: &FormatEntry<Handle>) -> bool {
943        match *entry {
944            FormatEntry::Marker => true,
945            FormatEntry::Element(ref node, _) => self
946                .open_elems
947                .borrow()
948                .iter()
949                .rev()
950                .any(|n| self.sink.same_node(n, node)),
951        }
952    }
953
954    /// <https://html.spec.whatwg.org/#reconstruct-the-active-formatting-elements>
955    fn reconstruct_active_formatting_elements(&self) {
956        {
957            let active_formatting = self.active_formatting.borrow();
958
959            // Step 1. If there are no entries in the list of active formatting elements,
960            // then there is nothing to reconstruct; stop this algorithm.
961            let Some(last) = active_formatting.last() else {
962                return;
963            };
964
965            // Step 2. If the last (most recently added) entry in the list of active formatting elements is a marker,
966            // or if it is an element that is in the stack of open elements, then there is nothing to reconstruct;
967            // stop this algorithm.
968            if self.is_marker_or_open(last) {
969                return;
970            }
971        }
972
973        // Step 3. Let entry be the last (most recently added) element in the list of active formatting elements.
974        // NOTE: We track the index of the element instead
975        let mut entry_index = self.active_formatting.borrow().len() - 1;
976        loop {
977            // Step 4. Rewind: If there are no entries before entry in the list of active formatting elements,
978            // then jump to the step labeled create.
979            if entry_index == 0 {
980                break;
981            }
982
983            // Step 5. Let entry be the entry one earlier than entry in the list of active formatting elements.
984            entry_index -= 1;
985
986            // Step 6. If entry is neither a marker nor an element that is also in the stack of open elements,
987            // go to the step labeled rewind.
988            // Step 7. Advance: Let entry be the element one later than entry in the list
989            // of active formatting elements.
990            if self.is_marker_or_open(&self.active_formatting.borrow()[entry_index]) {
991                entry_index += 1;
992                break;
993            }
994        }
995
996        loop {
997            // Step 8. Create: Insert an HTML element for the token for which the element entry was created,
998            // to obtain new element.
999            let tag = match self.active_formatting.borrow()[entry_index] {
1000                FormatEntry::Element(_, ref t) => t.clone(),
1001                FormatEntry::Marker => {
1002                    panic!("Found marker during formatting element reconstruction")
1003                },
1004            };
1005
1006            // FIXME: Is there a way to avoid cloning the attributes twice here (once on their own,
1007            // once as part of t.clone() above)?
1008            let new_element = self.insert_element(
1009                PushFlag::Push,
1010                ns!(html),
1011                tag.name.clone(),
1012                tag.attrs.clone(),
1013            );
1014
1015            // Step 9. Replace the entry for entry in the list with an entry for new element.
1016            self.active_formatting.borrow_mut()[entry_index] =
1017                FormatEntry::Element(new_element, tag);
1018
1019            // Step 10. If the entry for new element in the list of active formatting elements is
1020            // not the last entry in the list, return to the step labeled advance.
1021            if entry_index == self.active_formatting.borrow().len() - 1 {
1022                break;
1023            }
1024            entry_index += 1;
1025        }
1026    }
1027
1028    /// Get the first element on the stack, which will be the <html> element.
1029    fn html_elem(&self) -> Ref<'_, Handle> {
1030        Ref::map(self.open_elems.borrow(), |elems| &elems[0])
1031    }
1032
1033    /// Get the second element on the stack, if it's a HTML body element.
1034    fn body_elem(&self) -> Option<Ref<'_, Handle>> {
1035        if self.open_elems.borrow().len() <= 1 {
1036            return None;
1037        }
1038
1039        let node = Ref::map(self.open_elems.borrow(), |elems| &elems[1]);
1040        if self.html_elem_named(&node, local_name!("body")) {
1041            Some(node)
1042        } else {
1043            None
1044        }
1045    }
1046
1047    /// Signal an error depending on the state of the stack of open elements at
1048    /// the end of the body.
1049    fn check_body_end(&self) {
1050        declare_tag_set!(body_end_ok =
1051            "dd" "dt" "li" "optgroup" "option" "p" "rp" "rt" "tbody" "td" "tfoot" "th"
1052            "thead" "tr" "body" "html");
1053
1054        for elem in self.open_elems.borrow().iter() {
1055            let error = {
1056                let elem_name = self.sink.elem_name(elem);
1057                let name = elem_name.expanded();
1058                if body_end_ok(name) {
1059                    continue;
1060                }
1061
1062                if self.opts.exact_errors {
1063                    Cow::from(format!("Unexpected open tag {name:?} at end of body"))
1064                } else {
1065                    Cow::from("Unexpected open tag at end of body")
1066                }
1067            };
1068            self.sink.parse_error(error);
1069            // FIXME: Do we keep checking after finding one bad tag?
1070            // The spec suggests not.
1071            return;
1072        }
1073    }
1074
1075    fn in_scope<TagSet, Pred>(&self, scope: TagSet, pred: Pred) -> bool
1076    where
1077        TagSet: Fn(ExpandedName) -> bool,
1078        Pred: Fn(Handle) -> bool,
1079    {
1080        for node in self.open_elems.borrow().iter().rev() {
1081            if pred(node.clone()) {
1082                return true;
1083            }
1084            if scope(self.sink.elem_name(node).expanded()) {
1085                return false;
1086            }
1087        }
1088
1089        // supposed to be impossible, because <html> is always in scope
1090
1091        false
1092    }
1093
1094    fn elem_in<TagSet>(&self, elem: &Handle, set: TagSet) -> bool
1095    where
1096        TagSet: Fn(ExpandedName) -> bool,
1097    {
1098        set(self.sink.elem_name(elem).expanded())
1099    }
1100
1101    fn html_elem_named(&self, elem: &Handle, name: LocalName) -> bool {
1102        let elem_name = self.sink.elem_name(elem);
1103        *elem_name.ns() == ns!(html) && *elem_name.local_name() == name
1104    }
1105
1106    fn in_html_elem_named(&self, name: LocalName) -> bool {
1107        self.open_elems
1108            .borrow()
1109            .iter()
1110            .any(|elem| self.html_elem_named(elem, name.clone()))
1111    }
1112
1113    fn current_node_named(&self, name: LocalName) -> bool {
1114        self.html_elem_named(&self.current_node(), name)
1115    }
1116
1117    fn in_scope_named<TagSet>(&self, scope: TagSet, name: LocalName) -> bool
1118    where
1119        TagSet: Fn(ExpandedName) -> bool,
1120    {
1121        self.in_scope(scope, |elem| self.html_elem_named(&elem, name.clone()))
1122    }
1123
1124    /// <https://html.spec.whatwg.org/#generate-implied-end-tags>
1125    fn generate_implied_end_tags<TagSet>(&self, set: TagSet)
1126    where
1127        TagSet: Fn(ExpandedName) -> bool,
1128    {
1129        loop {
1130            {
1131                let open_elems = self.open_elems.borrow();
1132                let Some(elem) = open_elems.last() else {
1133                    return;
1134                };
1135                let elem_name = self.sink.elem_name(elem);
1136                if !set(elem_name.expanded()) {
1137                    return;
1138                }
1139            }
1140            self.pop();
1141        }
1142    }
1143
1144    fn generate_implied_end_except(&self, except: LocalName) {
1145        self.generate_implied_end_tags(|p| {
1146            if *p.ns == ns!(html) && *p.local == except {
1147                false
1148            } else {
1149                cursory_implied_end(p)
1150            }
1151        });
1152    }
1153    //§ END
1154
1155    // Pop elements until the current element is in the set.
1156    fn pop_until_current<TagSet>(&self, tag_set: TagSet)
1157    where
1158        TagSet: Fn(ExpandedName) -> bool,
1159    {
1160        while !self.current_node_in(&tag_set) {
1161            self.open_elems.borrow_mut().pop();
1162        }
1163    }
1164
1165    // Pop elements until an element from the set has been popped.  Returns the
1166    // number of elements popped.
1167    fn pop_until<P>(&self, pred: P) -> usize
1168    where
1169        P: Fn(ExpandedName) -> bool,
1170    {
1171        let mut n = 0;
1172        loop {
1173            n += 1;
1174            match self.open_elems.borrow_mut().pop() {
1175                None => break,
1176                Some(elem) => {
1177                    if pred(self.sink.elem_name(&elem).expanded()) {
1178                        break;
1179                    }
1180                },
1181            }
1182        }
1183        n
1184    }
1185
1186    fn pop_until_named(&self, name: LocalName) -> usize {
1187        self.pop_until(|p| *p.ns == ns!(html) && *p.local == name)
1188    }
1189
1190    /// Pop elements until one with the specified name has been popped.
1191    /// Signal an error if it was not the first one.
1192    fn expect_to_close(&self, name: LocalName) {
1193        if self.pop_until_named(name.clone()) != 1 {
1194            self.sink.parse_error(if self.opts.exact_errors {
1195                Cow::from(format!("Unexpected open element while closing {name:?}"))
1196            } else {
1197                Cow::from("Unexpected open element")
1198            });
1199        }
1200    }
1201
1202    fn close_p_element(&self) {
1203        declare_tag_set!(implied = [cursory_implied_end] - "p");
1204        self.generate_implied_end_tags(implied);
1205        self.expect_to_close(local_name!("p"));
1206    }
1207
1208    fn close_p_element_in_button_scope(&self) {
1209        if self.in_scope_named(button_scope, local_name!("p")) {
1210            self.close_p_element();
1211        }
1212    }
1213
1214    // Check <input> tags for type=hidden
1215    fn is_type_hidden(&self, tag: &Tag) -> bool {
1216        match tag
1217            .attrs
1218            .iter()
1219            .find(|&at| at.name.expanded() == expanded_name!("", "type"))
1220        {
1221            None => false,
1222            Some(at) => at.value.eq_ignore_ascii_case("hidden"),
1223        }
1224    }
1225
1226    fn foster_parent_in_body(&self, token: Token) -> ProcessResult<Handle> {
1227        warn!("foster parenting not implemented");
1228        self.foster_parenting.set(true);
1229        let res = self.step(InsertionMode::InBody, token);
1230        // FIXME: what if res is Reprocess?
1231        self.foster_parenting.set(false);
1232        res
1233    }
1234
1235    fn process_chars_in_table(&self, token: Token) -> ProcessResult<Handle> {
1236        declare_tag_set!(table_outer = "table" "tbody" "tfoot" "thead" "tr");
1237        if self.current_node_in(table_outer) {
1238            assert!(self.pending_table_text.borrow().is_empty());
1239            self.orig_mode.set(Some(self.mode.get()));
1240            ProcessResult::Reprocess(InsertionMode::InTableText, token)
1241        } else {
1242            self.sink.parse_error(if self.opts.exact_errors {
1243                Cow::from(format!(
1244                    "Unexpected characters {} in table",
1245                    to_escaped_string(&token)
1246                ))
1247            } else {
1248                Cow::from("Unexpected characters in table")
1249            });
1250            self.foster_parent_in_body(token)
1251        }
1252    }
1253
1254    // https://html.spec.whatwg.org/multipage/#reset-the-insertion-mode-appropriately
1255    fn reset_insertion_mode(&self) -> InsertionMode {
1256        let open_elems = self.open_elems.borrow();
1257        for (i, mut node) in open_elems.iter().enumerate().rev() {
1258            let last = i == 0usize;
1259            let context_elem = self.context_elem.borrow();
1260            if let (true, Some(ctx)) = (last, context_elem.as_ref()) {
1261                node = ctx;
1262            }
1263            let elem_name = self.sink.elem_name(node);
1264            let name = match elem_name.expanded() {
1265                ExpandedName {
1266                    ns: &ns!(html),
1267                    local,
1268                } => local,
1269                _ => continue,
1270            };
1271            match *name {
1272                local_name!("select") => {
1273                    for ancestor in self.open_elems.borrow()[0..i].iter().rev() {
1274                        if self.html_elem_named(ancestor, local_name!("template")) {
1275                            return InsertionMode::InSelect;
1276                        } else if self.html_elem_named(ancestor, local_name!("table")) {
1277                            return InsertionMode::InSelectInTable;
1278                        }
1279                    }
1280                    return InsertionMode::InSelect;
1281                },
1282                local_name!("td") | local_name!("th") => {
1283                    if !last {
1284                        return InsertionMode::InCell;
1285                    }
1286                },
1287                local_name!("tr") => return InsertionMode::InRow,
1288                local_name!("tbody") | local_name!("thead") | local_name!("tfoot") => {
1289                    return InsertionMode::InTableBody;
1290                },
1291                local_name!("caption") => return InsertionMode::InCaption,
1292                local_name!("colgroup") => return InsertionMode::InColumnGroup,
1293                local_name!("table") => return InsertionMode::InTable,
1294                local_name!("template") => return *self.template_modes.borrow().last().unwrap(),
1295                local_name!("head") => {
1296                    if !last {
1297                        return InsertionMode::InHead;
1298                    }
1299                },
1300                local_name!("body") => return InsertionMode::InBody,
1301                local_name!("frameset") => return InsertionMode::InFrameset,
1302                local_name!("html") => match *self.head_elem.borrow() {
1303                    None => return InsertionMode::BeforeHead,
1304                    Some(_) => return InsertionMode::AfterHead,
1305                },
1306
1307                _ => (),
1308            }
1309        }
1310        InsertionMode::InBody
1311    }
1312
1313    fn close_the_cell(&self) {
1314        self.generate_implied_end_tags(cursory_implied_end);
1315        if self.pop_until(td_th) != 1 {
1316            self.sink
1317                .parse_error(Borrowed("expected to close <td> or <th> with cell"));
1318        }
1319        self.clear_active_formatting_to_marker();
1320    }
1321
1322    fn append_text(&self, text: StrTendril) -> ProcessResult<Handle> {
1323        self.insert_appropriately(AppendText(text), None);
1324        ProcessResult::Done
1325    }
1326
1327    fn append_comment(&self, text: StrTendril) -> ProcessResult<Handle> {
1328        let comment = self.sink.create_comment(text);
1329        self.insert_appropriately(AppendNode(comment), None);
1330        ProcessResult::Done
1331    }
1332
1333    fn append_comment_to_doc(&self, text: StrTendril) -> ProcessResult<Handle> {
1334        let comment = self.sink.create_comment(text);
1335        self.sink.append(&self.doc_handle, AppendNode(comment));
1336        ProcessResult::Done
1337    }
1338
1339    fn append_comment_to_html(&self, text: StrTendril) -> ProcessResult<Handle> {
1340        let open_elems = self.open_elems.borrow();
1341        let target = html_elem(&open_elems);
1342        let comment = self.sink.create_comment(text);
1343        self.sink.append(target, AppendNode(comment));
1344        ProcessResult::Done
1345    }
1346
1347    //§ creating-and-inserting-nodes
1348    fn create_root(&self, attrs: Vec<Attribute>) {
1349        let elem = create_element(
1350            &self.sink,
1351            QualName::new(None, ns!(html), local_name!("html")),
1352            attrs,
1353        );
1354        self.push(&elem);
1355        self.sink.append(&self.doc_handle, AppendNode(elem));
1356        // FIXME: application cache selection algorithm
1357    }
1358
1359    // https://html.spec.whatwg.org/multipage/#create-an-element-for-the-token
1360    fn insert_element(
1361        &self,
1362        push: PushFlag,
1363        ns: Namespace,
1364        name: LocalName,
1365        attrs: Vec<Attribute>,
1366    ) -> Handle {
1367        declare_tag_set!(form_associatable =
1368            "button" "fieldset" "input" "object"
1369            "output" "select" "textarea" "img");
1370
1371        declare_tag_set!(listed = [form_associatable] - "img");
1372
1373        // Step 7.
1374        let qname = QualName::new(None, ns, name);
1375        let elem = create_element(&self.sink, qname.clone(), attrs.clone());
1376
1377        let insertion_point = self.appropriate_place_for_insertion(None);
1378        let (node1, node2) = match insertion_point {
1379            InsertionPoint::LastChild(ref p) | InsertionPoint::BeforeSibling(ref p) => {
1380                (p.clone(), None)
1381            },
1382            InsertionPoint::TableFosterParenting {
1383                ref element,
1384                ref prev_element,
1385            } => (element.clone(), Some(prev_element.clone())),
1386        };
1387
1388        // Step 12.
1389        if form_associatable(qname.expanded())
1390            && self.form_elem.borrow().is_some()
1391            && !self.in_html_elem_named(local_name!("template"))
1392            && !(listed(qname.expanded())
1393                && attrs
1394                    .iter()
1395                    .any(|a| a.name.expanded() == expanded_name!("", "form")))
1396        {
1397            let form = self.form_elem.borrow().as_ref().unwrap().clone();
1398            self.sink
1399                .associate_with_form(&elem, &form, (&node1, node2.as_ref()));
1400        }
1401
1402        self.insert_at(insertion_point, AppendNode(elem.clone()));
1403
1404        match push {
1405            PushFlag::Push => self.push(&elem),
1406            PushFlag::NoPush => (),
1407        }
1408        // FIXME: Remove from the stack if we can't append?
1409        elem
1410    }
1411
1412    fn insert_element_for(&self, tag: Tag) -> Handle {
1413        self.insert_element(PushFlag::Push, ns!(html), tag.name, tag.attrs)
1414    }
1415
1416    fn insert_and_pop_element_for(&self, tag: Tag) -> Handle {
1417        self.insert_element(PushFlag::NoPush, ns!(html), tag.name, tag.attrs)
1418    }
1419
1420    fn insert_phantom(&self, name: LocalName) -> Handle {
1421        self.insert_element(PushFlag::Push, ns!(html), name, vec![])
1422    }
1423
1424    /// <https://html.spec.whatwg.org/multipage/parsing.html#insert-an-element-at-the-adjusted-insertion-location>
1425    fn insert_foreign_element(
1426        &self,
1427        tag: Tag,
1428        ns: Namespace,
1429        only_add_to_element_stack: bool,
1430    ) -> Handle {
1431        let adjusted_insertion_location = self.appropriate_place_for_insertion(None);
1432        let qname = QualName::new(None, ns, tag.name);
1433        let elem = create_element(&self.sink, qname.clone(), tag.attrs.clone());
1434
1435        if !only_add_to_element_stack {
1436            self.insert_at(adjusted_insertion_location, AppendNode(elem.clone()));
1437        }
1438
1439        self.push(&elem);
1440
1441        elem
1442    }
1443    //§ END
1444
1445    /// <https://html.spec.whatwg.org/multipage/parsing.html#parsing-main-inhead>
1446    ///
1447    /// A start tag whose tag name is "template"
1448    fn should_attach_declarative_shadow(&self, tag: &Tag) -> bool {
1449        let adjusted_insertion_location = self.appropriate_place_for_insertion(None);
1450
1451        let (intended_parent, _node2) = match adjusted_insertion_location {
1452            InsertionPoint::LastChild(ref p) | InsertionPoint::BeforeSibling(ref p) => {
1453                (p.clone(), None)
1454            },
1455            InsertionPoint::TableFosterParenting {
1456                ref element,
1457                ref prev_element,
1458            } => (element.clone(), Some(prev_element.clone())),
1459        };
1460
1461        // template start tag's shadowrootmode is not in the none state
1462        let is_shadow_root_mode = tag.attrs.iter().any(|attr| {
1463            attr.name.local == local_name!("shadowrootmode")
1464                && (attr.value.as_ref() == "open" || attr.value.as_ref() == "closed")
1465        });
1466
1467        // Check if intended_parent's document allows declarative shadow roots
1468        let allow_declarative_shadow_roots =
1469            self.sink.allow_declarative_shadow_roots(&intended_parent);
1470
1471        // the adjusted current node is not the topmost element in the stack of open elements
1472        let adjusted_current_node_not_topmost = match self.open_elems.borrow().first() {
1473            // The stack grows downwards; the topmost node on the stack is the first one added to the stack
1474            // The current node is the bottommost node in this stack of open elements.
1475            //
1476            // (1) The adjusted current node is the context element if the parser was created as part of the HTML fragment parsing algorithm
1477            // and the stack of open elements has only one element in it (fragment case);
1478            // (2) otherwise, the adjusted current node is the current node (the bottomost node)
1479            //
1480            // => adjusted current node != topmost element in the stack when the stack size > 1
1481            Some(_) => self.open_elems.borrow().len() > 1,
1482            None => true,
1483        };
1484
1485        is_shadow_root_mode && allow_declarative_shadow_roots && adjusted_current_node_not_topmost
1486    }
1487
1488    /// <https://html.spec.whatwg.org/multipage/parsing.html#parsing-main-inhead>
1489    ///
1490    /// A start tag whose tag name is "template"
1491    fn attach_declarative_shadow(
1492        &self,
1493        tag: &Tag,
1494        shadow_host: &Handle,
1495        template: &Handle,
1496    ) -> bool {
1497        self.sink
1498            .attach_declarative_shadow(shadow_host, template, &tag.attrs)
1499    }
1500
1501    fn create_formatting_element_for(&self, tag: Tag) -> Handle {
1502        // FIXME: This really wants unit tests.
1503        let mut first_match = None;
1504        let mut matches = 0usize;
1505        for (i, _, old_tag) in self.active_formatting_end_to_marker().iter() {
1506            if tag.equiv_modulo_attr_order(old_tag) {
1507                first_match = Some(i);
1508                matches += 1;
1509            }
1510        }
1511
1512        if matches >= 3 {
1513            self.active_formatting
1514                .borrow_mut()
1515                .remove(first_match.expect("matches with no index"));
1516        }
1517
1518        let elem = self.insert_element(
1519            PushFlag::Push,
1520            ns!(html),
1521            tag.name.clone(),
1522            tag.attrs.clone(),
1523        );
1524        self.active_formatting
1525            .borrow_mut()
1526            .push(FormatEntry::Element(elem.clone(), tag));
1527        elem
1528    }
1529
1530    fn clear_active_formatting_to_marker(&self) {
1531        loop {
1532            match self.active_formatting.borrow_mut().pop() {
1533                None | Some(FormatEntry::Marker) => break,
1534                _ => (),
1535            }
1536        }
1537    }
1538
1539    fn process_end_tag_in_body(&self, tag: Tag) {
1540        // Look back for a matching open element.
1541        let mut match_idx = None;
1542        for (i, elem) in self.open_elems.borrow().iter().enumerate().rev() {
1543            if self.html_elem_named(elem, tag.name.clone()) {
1544                match_idx = Some(i);
1545                break;
1546            }
1547
1548            if self.elem_in(elem, special_tag) {
1549                self.sink
1550                    .parse_error(Borrowed("Found special tag while closing generic tag"));
1551                return;
1552            }
1553        }
1554
1555        let Some(match_idx) = match_idx else {
1556            // I believe this is impossible, because the root
1557            // <html> element is in special_tag.
1558            self.unexpected(&tag);
1559            return;
1560        };
1561
1562        self.generate_implied_end_except(tag.name.clone());
1563
1564        if match_idx != self.open_elems.borrow().len() - 1 {
1565            // mis-nested tags
1566            self.unexpected(&tag);
1567        }
1568        self.open_elems.borrow_mut().truncate(match_idx);
1569    }
1570
1571    fn handle_misnested_a_tags(&self, tag: &Tag) {
1572        let Some(node) = self
1573            .active_formatting_end_to_marker()
1574            .iter()
1575            .find(|&(_, n, _)| self.html_elem_named(n, local_name!("a")))
1576            .map(|(_, n, _)| n.clone())
1577        else {
1578            return;
1579        };
1580
1581        self.unexpected(tag);
1582        self.adoption_agency(local_name!("a"));
1583        self.position_in_active_formatting(&node)
1584            .map(|index| self.active_formatting.borrow_mut().remove(index));
1585        self.remove_from_stack(&node);
1586    }
1587
1588    //§ tree-construction
1589    fn is_foreign(&self, token: &Token) -> bool {
1590        if let Token::Eof = *token {
1591            return false;
1592        }
1593
1594        if self.open_elems.borrow().is_empty() {
1595            return false;
1596        }
1597
1598        let current = self.adjusted_current_node();
1599        let elem_name = self.sink.elem_name(&current);
1600        let name = elem_name.expanded();
1601        if let ns!(html) = *name.ns {
1602            return false;
1603        }
1604
1605        if mathml_text_integration_point(name) {
1606            match *token {
1607                Token::Characters(..) | Token::NullCharacter => return false,
1608                Token::Tag(Tag {
1609                    kind: StartTag,
1610                    ref name,
1611                    ..
1612                }) if !matches!(*name, local_name!("mglyph") | local_name!("malignmark")) => {
1613                    return false;
1614                },
1615                _ => (),
1616            }
1617        }
1618
1619        if svg_html_integration_point(name) {
1620            match *token {
1621                Token::Characters(..) | Token::NullCharacter => return false,
1622                Token::Tag(Tag { kind: StartTag, .. }) => return false,
1623                _ => (),
1624            }
1625        }
1626
1627        if let expanded_name!(mathml "annotation-xml") = name {
1628            match *token {
1629                Token::Tag(Tag {
1630                    kind: StartTag,
1631                    name: local_name!("svg"),
1632                    ..
1633                }) => return false,
1634                Token::Characters(..)
1635                | Token::NullCharacter
1636                | Token::Tag(Tag { kind: StartTag, .. }) => {
1637                    return !self
1638                        .sink
1639                        .is_mathml_annotation_xml_integration_point(&self.adjusted_current_node());
1640                },
1641                _ => {},
1642            };
1643        }
1644
1645        true
1646    }
1647    //§ END
1648
1649    fn enter_foreign(&self, mut tag: Tag, ns: Namespace) -> ProcessResult<Handle> {
1650        match ns {
1651            ns!(mathml) => self.adjust_mathml_attributes(&mut tag),
1652            ns!(svg) => self.adjust_svg_attributes(&mut tag),
1653            _ => (),
1654        }
1655        self.adjust_foreign_attributes(&mut tag);
1656
1657        if tag.self_closing {
1658            self.insert_element(PushFlag::NoPush, ns, tag.name, tag.attrs);
1659            ProcessResult::DoneAckSelfClosing
1660        } else {
1661            self.insert_element(PushFlag::Push, ns, tag.name, tag.attrs);
1662            ProcessResult::Done
1663        }
1664    }
1665
1666    fn adjust_svg_tag_name(&self, tag: &mut Tag) {
1667        let Tag { ref mut name, .. } = *tag;
1668        match *name {
1669            local_name!("altglyph") => *name = local_name!("altGlyph"),
1670            local_name!("altglyphdef") => *name = local_name!("altGlyphDef"),
1671            local_name!("altglyphitem") => *name = local_name!("altGlyphItem"),
1672            local_name!("animatecolor") => *name = local_name!("animateColor"),
1673            local_name!("animatemotion") => *name = local_name!("animateMotion"),
1674            local_name!("animatetransform") => *name = local_name!("animateTransform"),
1675            local_name!("clippath") => *name = local_name!("clipPath"),
1676            local_name!("feblend") => *name = local_name!("feBlend"),
1677            local_name!("fecolormatrix") => *name = local_name!("feColorMatrix"),
1678            local_name!("fecomponenttransfer") => *name = local_name!("feComponentTransfer"),
1679            local_name!("fecomposite") => *name = local_name!("feComposite"),
1680            local_name!("feconvolvematrix") => *name = local_name!("feConvolveMatrix"),
1681            local_name!("fediffuselighting") => *name = local_name!("feDiffuseLighting"),
1682            local_name!("fedisplacementmap") => *name = local_name!("feDisplacementMap"),
1683            local_name!("fedistantlight") => *name = local_name!("feDistantLight"),
1684            local_name!("fedropshadow") => *name = local_name!("feDropShadow"),
1685            local_name!("feflood") => *name = local_name!("feFlood"),
1686            local_name!("fefunca") => *name = local_name!("feFuncA"),
1687            local_name!("fefuncb") => *name = local_name!("feFuncB"),
1688            local_name!("fefuncg") => *name = local_name!("feFuncG"),
1689            local_name!("fefuncr") => *name = local_name!("feFuncR"),
1690            local_name!("fegaussianblur") => *name = local_name!("feGaussianBlur"),
1691            local_name!("feimage") => *name = local_name!("feImage"),
1692            local_name!("femerge") => *name = local_name!("feMerge"),
1693            local_name!("femergenode") => *name = local_name!("feMergeNode"),
1694            local_name!("femorphology") => *name = local_name!("feMorphology"),
1695            local_name!("feoffset") => *name = local_name!("feOffset"),
1696            local_name!("fepointlight") => *name = local_name!("fePointLight"),
1697            local_name!("fespecularlighting") => *name = local_name!("feSpecularLighting"),
1698            local_name!("fespotlight") => *name = local_name!("feSpotLight"),
1699            local_name!("fetile") => *name = local_name!("feTile"),
1700            local_name!("feturbulence") => *name = local_name!("feTurbulence"),
1701            local_name!("foreignobject") => *name = local_name!("foreignObject"),
1702            local_name!("glyphref") => *name = local_name!("glyphRef"),
1703            local_name!("lineargradient") => *name = local_name!("linearGradient"),
1704            local_name!("radialgradient") => *name = local_name!("radialGradient"),
1705            local_name!("textpath") => *name = local_name!("textPath"),
1706            _ => (),
1707        }
1708    }
1709
1710    fn adjust_attributes<F>(&self, tag: &mut Tag, mut map: F)
1711    where
1712        F: FnMut(LocalName) -> Option<QualName>,
1713    {
1714        for &mut Attribute { ref mut name, .. } in &mut tag.attrs {
1715            if let Some(replacement) = map(name.local.clone()) {
1716                *name = replacement;
1717            }
1718        }
1719    }
1720
1721    fn adjust_svg_attributes(&self, tag: &mut Tag) {
1722        self.adjust_attributes(tag, |k| match k {
1723            local_name!("attributename") => Some(qualname!("", "attributeName")),
1724            local_name!("attributetype") => Some(qualname!("", "attributeType")),
1725            local_name!("basefrequency") => Some(qualname!("", "baseFrequency")),
1726            local_name!("baseprofile") => Some(qualname!("", "baseProfile")),
1727            local_name!("calcmode") => Some(qualname!("", "calcMode")),
1728            local_name!("clippathunits") => Some(qualname!("", "clipPathUnits")),
1729            local_name!("diffuseconstant") => Some(qualname!("", "diffuseConstant")),
1730            local_name!("edgemode") => Some(qualname!("", "edgeMode")),
1731            local_name!("filterunits") => Some(qualname!("", "filterUnits")),
1732            local_name!("glyphref") => Some(qualname!("", "glyphRef")),
1733            local_name!("gradienttransform") => Some(qualname!("", "gradientTransform")),
1734            local_name!("gradientunits") => Some(qualname!("", "gradientUnits")),
1735            local_name!("kernelmatrix") => Some(qualname!("", "kernelMatrix")),
1736            local_name!("kernelunitlength") => Some(qualname!("", "kernelUnitLength")),
1737            local_name!("keypoints") => Some(qualname!("", "keyPoints")),
1738            local_name!("keysplines") => Some(qualname!("", "keySplines")),
1739            local_name!("keytimes") => Some(qualname!("", "keyTimes")),
1740            local_name!("lengthadjust") => Some(qualname!("", "lengthAdjust")),
1741            local_name!("limitingconeangle") => Some(qualname!("", "limitingConeAngle")),
1742            local_name!("markerheight") => Some(qualname!("", "markerHeight")),
1743            local_name!("markerunits") => Some(qualname!("", "markerUnits")),
1744            local_name!("markerwidth") => Some(qualname!("", "markerWidth")),
1745            local_name!("maskcontentunits") => Some(qualname!("", "maskContentUnits")),
1746            local_name!("maskunits") => Some(qualname!("", "maskUnits")),
1747            local_name!("numoctaves") => Some(qualname!("", "numOctaves")),
1748            local_name!("pathlength") => Some(qualname!("", "pathLength")),
1749            local_name!("patterncontentunits") => Some(qualname!("", "patternContentUnits")),
1750            local_name!("patterntransform") => Some(qualname!("", "patternTransform")),
1751            local_name!("patternunits") => Some(qualname!("", "patternUnits")),
1752            local_name!("pointsatx") => Some(qualname!("", "pointsAtX")),
1753            local_name!("pointsaty") => Some(qualname!("", "pointsAtY")),
1754            local_name!("pointsatz") => Some(qualname!("", "pointsAtZ")),
1755            local_name!("preservealpha") => Some(qualname!("", "preserveAlpha")),
1756            local_name!("preserveaspectratio") => Some(qualname!("", "preserveAspectRatio")),
1757            local_name!("primitiveunits") => Some(qualname!("", "primitiveUnits")),
1758            local_name!("refx") => Some(qualname!("", "refX")),
1759            local_name!("refy") => Some(qualname!("", "refY")),
1760            local_name!("repeatcount") => Some(qualname!("", "repeatCount")),
1761            local_name!("repeatdur") => Some(qualname!("", "repeatDur")),
1762            local_name!("requiredextensions") => Some(qualname!("", "requiredExtensions")),
1763            local_name!("requiredfeatures") => Some(qualname!("", "requiredFeatures")),
1764            local_name!("specularconstant") => Some(qualname!("", "specularConstant")),
1765            local_name!("specularexponent") => Some(qualname!("", "specularExponent")),
1766            local_name!("spreadmethod") => Some(qualname!("", "spreadMethod")),
1767            local_name!("startoffset") => Some(qualname!("", "startOffset")),
1768            local_name!("stddeviation") => Some(qualname!("", "stdDeviation")),
1769            local_name!("stitchtiles") => Some(qualname!("", "stitchTiles")),
1770            local_name!("surfacescale") => Some(qualname!("", "surfaceScale")),
1771            local_name!("systemlanguage") => Some(qualname!("", "systemLanguage")),
1772            local_name!("tablevalues") => Some(qualname!("", "tableValues")),
1773            local_name!("targetx") => Some(qualname!("", "targetX")),
1774            local_name!("targety") => Some(qualname!("", "targetY")),
1775            local_name!("textlength") => Some(qualname!("", "textLength")),
1776            local_name!("viewbox") => Some(qualname!("", "viewBox")),
1777            local_name!("viewtarget") => Some(qualname!("", "viewTarget")),
1778            local_name!("xchannelselector") => Some(qualname!("", "xChannelSelector")),
1779            local_name!("ychannelselector") => Some(qualname!("", "yChannelSelector")),
1780            local_name!("zoomandpan") => Some(qualname!("", "zoomAndPan")),
1781            _ => None,
1782        });
1783    }
1784
1785    fn adjust_mathml_attributes(&self, tag: &mut Tag) {
1786        self.adjust_attributes(tag, |k| match k {
1787            local_name!("definitionurl") => Some(qualname!("", "definitionURL")),
1788            _ => None,
1789        });
1790    }
1791
1792    fn adjust_foreign_attributes(&self, tag: &mut Tag) {
1793        self.adjust_attributes(tag, |k| match k {
1794            local_name!("xlink:actuate") => Some(qualname!("xlink" xlink "actuate")),
1795            local_name!("xlink:arcrole") => Some(qualname!("xlink" xlink "arcrole")),
1796            local_name!("xlink:href") => Some(qualname!("xlink" xlink "href")),
1797            local_name!("xlink:role") => Some(qualname!("xlink" xlink "role")),
1798            local_name!("xlink:show") => Some(qualname!("xlink" xlink "show")),
1799            local_name!("xlink:title") => Some(qualname!("xlink" xlink "title")),
1800            local_name!("xlink:type") => Some(qualname!("xlink" xlink "type")),
1801            local_name!("xml:lang") => Some(qualname!("xml" xml "lang")),
1802            local_name!("xml:space") => Some(qualname!("xml" xml "space")),
1803            local_name!("xmlns") => Some(qualname!("" xmlns "xmlns")),
1804            local_name!("xmlns:xlink") => Some(qualname!("xmlns" xmlns "xlink")),
1805            _ => None,
1806        });
1807    }
1808
1809    fn foreign_start_tag(&self, mut tag: Tag) -> ProcessResult<Handle> {
1810        let current_ns = self
1811            .sink
1812            .elem_name(&self.adjusted_current_node())
1813            .ns()
1814            .clone();
1815        match current_ns {
1816            ns!(mathml) => self.adjust_mathml_attributes(&mut tag),
1817            ns!(svg) => {
1818                self.adjust_svg_tag_name(&mut tag);
1819                self.adjust_svg_attributes(&mut tag);
1820            },
1821            _ => (),
1822        }
1823        self.adjust_foreign_attributes(&mut tag);
1824        if tag.self_closing {
1825            // FIXME(#118): <script /> in SVG
1826            self.insert_element(PushFlag::NoPush, current_ns, tag.name, tag.attrs);
1827            ProcessResult::DoneAckSelfClosing
1828        } else {
1829            self.insert_element(PushFlag::Push, current_ns, tag.name, tag.attrs);
1830            ProcessResult::Done
1831        }
1832    }
1833
1834    fn unexpected_start_tag_in_foreign_content(&self, tag: Tag) -> ProcessResult<Handle> {
1835        self.unexpected(&tag);
1836        while !self.current_node_in(|n| {
1837            *n.ns == ns!(html) || mathml_text_integration_point(n) || svg_html_integration_point(n)
1838        }) {
1839            self.pop();
1840        }
1841        self.step(self.mode.get(), Token::Tag(tag))
1842    }
1843}