script/dom/
node.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! The core DOM types. Defines the basic DOM hierarchy as well as all the HTML elements.
6
7use std::borrow::Cow;
8use std::cell::{Cell, LazyCell, UnsafeCell};
9use std::default::Default;
10use std::f64::consts::PI;
11use std::ops::Range;
12use std::slice::from_ref;
13use std::{cmp, fmt, iter};
14
15use app_units::Au;
16use base::id::{BrowsingContextId, PipelineId};
17use bitflags::bitflags;
18use devtools_traits::NodeInfo;
19use dom_struct::dom_struct;
20use embedder_traits::UntrustedNodeAddress;
21use euclid::Point2D;
22use euclid::default::{Rect, Size2D};
23use html5ever::serialize::HtmlSerializer;
24use html5ever::{Namespace, Prefix, QualName, ns, serialize as html_serialize};
25use js::jsapi::JSObject;
26use js::rust::HandleObject;
27use keyboard_types::Modifiers;
28use layout_api::{
29    BoxAreaType, GenericLayoutData, HTMLCanvasData, HTMLMediaData, LayoutElementType,
30    LayoutNodeType, QueryMsg, SVGElementData, StyleData, TrustedNodeAddress,
31};
32use libc::{self, c_void, uintptr_t};
33use malloc_size_of::{MallocSizeOf, MallocSizeOfOps};
34use net_traits::image_cache::Image;
35use pixels::ImageMetadata;
36use script_bindings::codegen::InheritTypes::DocumentFragmentTypeId;
37use script_traits::DocumentActivity;
38use selectors::matching::{
39    MatchingContext, MatchingForInvalidation, MatchingMode, NeedsSelectorFlags,
40    matches_selector_list,
41};
42use selectors::parser::SelectorList;
43use servo_arc::Arc;
44use servo_config::pref;
45use servo_url::ServoUrl;
46use smallvec::SmallVec;
47use style::attr::AttrValue;
48use style::context::QuirksMode;
49use style::dom::OpaqueNode;
50use style::properties::ComputedValues;
51use style::selector_parser::{PseudoElement, SelectorImpl, SelectorParser};
52use style::stylesheets::{Stylesheet, UrlExtraData};
53use uuid::Uuid;
54use xml5ever::{local_name, serialize as xml_serialize};
55
56use super::types::CDATASection;
57use crate::conversions::Convert;
58use crate::document_loader::DocumentLoader;
59use crate::dom::attr::Attr;
60use crate::dom::bindings::cell::{DomRefCell, Ref, RefMut};
61use crate::dom::bindings::codegen::Bindings::AttrBinding::AttrMethods;
62use crate::dom::bindings::codegen::Bindings::CSSStyleDeclarationBinding::CSSStyleDeclarationMethods;
63use crate::dom::bindings::codegen::Bindings::CharacterDataBinding::CharacterDataMethods;
64use crate::dom::bindings::codegen::Bindings::DocumentBinding::DocumentMethods;
65use crate::dom::bindings::codegen::Bindings::ElementBinding::ElementMethods;
66use crate::dom::bindings::codegen::Bindings::HTMLCollectionBinding::HTMLCollectionMethods;
67use crate::dom::bindings::codegen::Bindings::NodeBinding::{
68    GetRootNodeOptions, NodeConstants, NodeMethods,
69};
70use crate::dom::bindings::codegen::Bindings::NodeListBinding::NodeListMethods;
71use crate::dom::bindings::codegen::Bindings::ProcessingInstructionBinding::ProcessingInstructionMethods;
72use crate::dom::bindings::codegen::Bindings::ShadowRootBinding::ShadowRoot_Binding::ShadowRootMethods;
73use crate::dom::bindings::codegen::Bindings::ShadowRootBinding::{
74    ShadowRootMode, SlotAssignmentMode,
75};
76use crate::dom::bindings::codegen::Bindings::WindowBinding::WindowMethods;
77use crate::dom::bindings::codegen::UnionTypes::NodeOrString;
78use crate::dom::bindings::conversions::{self, DerivedFrom};
79use crate::dom::bindings::domname::namespace_from_domstring;
80use crate::dom::bindings::error::{Error, ErrorResult, Fallible};
81use crate::dom::bindings::inheritance::{
82    Castable, CharacterDataTypeId, ElementTypeId, EventTargetTypeId, HTMLElementTypeId, NodeTypeId,
83    SVGElementTypeId, SVGGraphicsElementTypeId, TextTypeId,
84};
85use crate::dom::bindings::reflector::{DomObject, DomObjectWrap, reflect_dom_object_with_proto};
86use crate::dom::bindings::root::{Dom, DomRoot, DomSlice, LayoutDom, MutNullableDom, ToLayout};
87use crate::dom::bindings::str::{DOMString, USVString};
88use crate::dom::characterdata::{CharacterData, LayoutCharacterDataHelpers};
89use crate::dom::cssstylesheet::CSSStyleSheet;
90use crate::dom::customelementregistry::{CallbackReaction, try_upgrade_element};
91use crate::dom::document::{Document, DocumentSource, HasBrowsingContext, IsHTMLDocument};
92use crate::dom::documentfragment::DocumentFragment;
93use crate::dom::documenttype::DocumentType;
94use crate::dom::element::{CustomElementCreationMode, Element, ElementCreator, SelectorWrapper};
95use crate::dom::event::{Event, EventBubbles, EventCancelable};
96use crate::dom::eventtarget::EventTarget;
97use crate::dom::globalscope::GlobalScope;
98use crate::dom::html::htmlcanvaselement::{HTMLCanvasElement, LayoutHTMLCanvasElementHelpers};
99use crate::dom::html::htmlcollection::HTMLCollection;
100use crate::dom::html::htmlelement::HTMLElement;
101use crate::dom::html::htmliframeelement::{HTMLIFrameElement, HTMLIFrameElementLayoutMethods};
102use crate::dom::html::htmlimageelement::{HTMLImageElement, LayoutHTMLImageElementHelpers};
103use crate::dom::html::htmlinputelement::{
104    HTMLInputElement, InputType, LayoutHTMLInputElementHelpers,
105};
106use crate::dom::html::htmllinkelement::HTMLLinkElement;
107use crate::dom::html::htmlslotelement::{HTMLSlotElement, Slottable};
108use crate::dom::html::htmlstyleelement::HTMLStyleElement;
109use crate::dom::html::htmltextareaelement::{
110    HTMLTextAreaElement, LayoutHTMLTextAreaElementHelpers,
111};
112use crate::dom::html::htmlvideoelement::{HTMLVideoElement, LayoutHTMLVideoElementHelpers};
113use crate::dom::mutationobserver::{Mutation, MutationObserver, RegisteredObserver};
114use crate::dom::nodelist::NodeList;
115use crate::dom::pointerevent::{PointerEvent, PointerId};
116use crate::dom::processinginstruction::ProcessingInstruction;
117use crate::dom::range::WeakRangeVec;
118use crate::dom::raredata::NodeRareData;
119use crate::dom::servoparser::{ServoParser, serialize_html_fragment};
120use crate::dom::shadowroot::{IsUserAgentWidget, LayoutShadowRootHelpers, ShadowRoot};
121use crate::dom::stylesheetlist::StyleSheetListOwner;
122use crate::dom::svgsvgelement::{LayoutSVGSVGElementHelpers, SVGSVGElement};
123use crate::dom::text::Text;
124use crate::dom::virtualmethods::{VirtualMethods, vtable_for};
125use crate::dom::window::Window;
126use crate::script_runtime::CanGc;
127use crate::script_thread::ScriptThread;
128
129//
130// The basic Node structure
131//
132
133/// An HTML node.
134#[dom_struct]
135pub struct Node {
136    /// The JavaScript reflector for this node.
137    eventtarget: EventTarget,
138
139    /// The parent of this node.
140    parent_node: MutNullableDom<Node>,
141
142    /// The first child of this node.
143    first_child: MutNullableDom<Node>,
144
145    /// The last child of this node.
146    last_child: MutNullableDom<Node>,
147
148    /// The next sibling of this node.
149    next_sibling: MutNullableDom<Node>,
150
151    /// The previous sibling of this node.
152    prev_sibling: MutNullableDom<Node>,
153
154    /// The document that this node belongs to.
155    owner_doc: MutNullableDom<Document>,
156
157    /// Rare node data.
158    rare_data: DomRefCell<Option<Box<NodeRareData>>>,
159
160    /// The live count of children of this node.
161    children_count: Cell<u32>,
162
163    /// A bitfield of flags for node items.
164    flags: Cell<NodeFlags>,
165
166    /// The maximum version of any inclusive descendant of this node.
167    inclusive_descendants_version: Cell<u64>,
168
169    /// Style data for this node. This is accessed and mutated by style
170    /// passes and is used to lay out this node and populate layout data.
171    #[no_trace]
172    style_data: DomRefCell<Option<Box<StyleData>>>,
173
174    /// Layout data for this node. This is populated during layout and can
175    /// be used for incremental relayout and script queries.
176    #[no_trace]
177    layout_data: DomRefCell<Option<Box<GenericLayoutData>>>,
178}
179
180impl fmt::Debug for Node {
181    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
182        if matches!(self.type_id(), NodeTypeId::Element(_)) {
183            let el = self.downcast::<Element>().unwrap();
184            el.fmt(f)
185        } else {
186            write!(f, "[Node({:?})]", self.type_id())
187        }
188    }
189}
190
191/// Flags for node items
192#[derive(Clone, Copy, JSTraceable, MallocSizeOf)]
193pub(crate) struct NodeFlags(u16);
194
195bitflags! {
196    impl NodeFlags: u16 {
197        /// Specifies whether this node is in a document.
198        ///
199        /// <https://dom.spec.whatwg.org/#in-a-document-tree>
200        const IS_IN_A_DOCUMENT_TREE = 1 << 0;
201
202        /// Specifies whether this node needs style recalc on next reflow.
203        const HAS_DIRTY_DESCENDANTS = 1 << 1;
204
205        /// Specifies whether or not there is an authentic click in progress on
206        /// this element.
207        const CLICK_IN_PROGRESS = 1 << 2;
208
209        /// Specifies whether this node is focusable and whether it is supposed
210        /// to be reachable with using sequential focus navigation."]
211        const SEQUENTIALLY_FOCUSABLE = 1 << 3;
212
213        // There are two free bits here.
214
215        /// Specifies whether the parser has set an associated form owner for
216        /// this element. Only applicable for form-associatable elements.
217        const PARSER_ASSOCIATED_FORM_OWNER = 1 << 6;
218
219        /// Whether this element has a snapshot stored due to a style or
220        /// attribute change.
221        ///
222        /// See the `style::restyle_hints` module.
223        const HAS_SNAPSHOT = 1 << 7;
224
225        /// Whether this element has already handled the stored snapshot.
226        const HANDLED_SNAPSHOT = 1 << 8;
227
228        /// Whether this node participates in a shadow tree.
229        const IS_IN_SHADOW_TREE = 1 << 9;
230
231        /// Specifies whether this node's shadow-including root is a document.
232        ///
233        /// <https://dom.spec.whatwg.org/#connected>
234        const IS_CONNECTED = 1 << 10;
235
236        /// Whether this node has a weird parser insertion mode. i.e whether setting innerHTML
237        /// needs extra work or not
238        const HAS_WEIRD_PARSER_INSERTION_MODE = 1 << 11;
239
240        /// Whether this node resides in UA shadow DOM. Element within UA Shadow DOM
241        /// will have a different style computation behavior
242        const IS_IN_UA_WIDGET = 1 << 12;
243    }
244}
245
246/// suppress observers flag
247/// <https://dom.spec.whatwg.org/#concept-node-insert>
248/// <https://dom.spec.whatwg.org/#concept-node-remove>
249#[derive(Clone, Copy, MallocSizeOf)]
250enum SuppressObserver {
251    Suppressed,
252    Unsuppressed,
253}
254
255impl Node {
256    /// Adds a new child to the end of this node's list of children.
257    ///
258    /// Fails unless `new_child` is disconnected from the tree.
259    fn add_child(&self, new_child: &Node, before: Option<&Node>, can_gc: CanGc) {
260        assert!(new_child.parent_node.get().is_none());
261        assert!(new_child.prev_sibling.get().is_none());
262        assert!(new_child.next_sibling.get().is_none());
263        match before {
264            Some(before) => {
265                assert!(before.parent_node.get().as_deref() == Some(self));
266                let prev_sibling = before.GetPreviousSibling();
267                match prev_sibling {
268                    None => {
269                        assert!(self.first_child.get().as_deref() == Some(before));
270                        self.first_child.set(Some(new_child));
271                    },
272                    Some(ref prev_sibling) => {
273                        prev_sibling.next_sibling.set(Some(new_child));
274                        new_child.prev_sibling.set(Some(prev_sibling));
275                    },
276                }
277                before.prev_sibling.set(Some(new_child));
278                new_child.next_sibling.set(Some(before));
279            },
280            None => {
281                let last_child = self.GetLastChild();
282                match last_child {
283                    None => self.first_child.set(Some(new_child)),
284                    Some(ref last_child) => {
285                        assert!(last_child.next_sibling.get().is_none());
286                        last_child.next_sibling.set(Some(new_child));
287                        new_child.prev_sibling.set(Some(last_child));
288                    },
289                }
290
291                self.last_child.set(Some(new_child));
292            },
293        }
294
295        new_child.parent_node.set(Some(self));
296        self.children_count.set(self.children_count.get() + 1);
297
298        let parent_is_in_a_document_tree = self.is_in_a_document_tree();
299        let parent_in_shadow_tree = self.is_in_a_shadow_tree();
300        let parent_is_connected = self.is_connected();
301        let parent_is_in_ua_widget = self.is_in_ua_widget();
302
303        for node in new_child.traverse_preorder(ShadowIncluding::No) {
304            if parent_in_shadow_tree {
305                if let Some(shadow_root) = self.containing_shadow_root() {
306                    node.set_containing_shadow_root(Some(&*shadow_root));
307                }
308                debug_assert!(node.containing_shadow_root().is_some());
309            }
310            node.set_flag(
311                NodeFlags::IS_IN_A_DOCUMENT_TREE,
312                parent_is_in_a_document_tree,
313            );
314            node.set_flag(NodeFlags::IS_IN_SHADOW_TREE, parent_in_shadow_tree);
315            node.set_flag(NodeFlags::IS_CONNECTED, parent_is_connected);
316            node.set_flag(NodeFlags::IS_IN_UA_WIDGET, parent_is_in_ua_widget);
317
318            // Out-of-document elements never have the descendants flag set.
319            debug_assert!(!node.get_flag(NodeFlags::HAS_DIRTY_DESCENDANTS));
320            vtable_for(&node).bind_to_tree(
321                &BindContext {
322                    tree_connected: parent_is_connected,
323                    tree_is_in_a_document_tree: parent_is_in_a_document_tree,
324                    tree_is_in_a_shadow_tree: parent_in_shadow_tree,
325                },
326                can_gc,
327            );
328        }
329    }
330
331    /// Implements the "unsafely set HTML" algorithm as specified in:
332    /// <https://html.spec.whatwg.org/multipage/#concept-unsafely-set-html>
333    pub(crate) fn unsafely_set_html(
334        target: &Node,
335        context_element: &Element,
336        html: DOMString,
337        can_gc: CanGc,
338    ) {
339        // Step 1. Let newChildren be the result of the HTML fragment parsing algorithm.
340        let new_children = ServoParser::parse_html_fragment(context_element, html, true, can_gc);
341
342        // Step 2. Let fragment be a new DocumentFragment whose node document is contextElement's node document.
343
344        let context_document = context_element.owner_document();
345        let fragment = DocumentFragment::new(&context_document, can_gc);
346
347        // Step 3. For each node in newChildren, append node to fragment.
348        for child in new_children {
349            fragment
350                .upcast::<Node>()
351                .AppendChild(&child, can_gc)
352                .unwrap();
353        }
354
355        // Step 4. Replace all with fragment within target.
356        Node::replace_all(Some(fragment.upcast()), target, can_gc);
357    }
358
359    pub(crate) fn clean_up_style_and_layout_data(&self) {
360        self.owner_doc().cancel_animations_for_node(self);
361        self.style_data.borrow_mut().take();
362        self.layout_data.borrow_mut().take();
363    }
364
365    /// Clean up flags and runs steps 11-14 of remove a node.
366    /// <https://dom.spec.whatwg.org/#concept-node-remove>
367    pub(crate) fn complete_remove_subtree(root: &Node, context: &UnbindContext, can_gc: CanGc) {
368        // Flags that reset when a node is disconnected
369        const RESET_FLAGS: NodeFlags = NodeFlags::IS_IN_A_DOCUMENT_TREE
370            .union(NodeFlags::IS_CONNECTED)
371            .union(NodeFlags::HAS_DIRTY_DESCENDANTS)
372            .union(NodeFlags::HAS_SNAPSHOT)
373            .union(NodeFlags::HANDLED_SNAPSHOT);
374
375        for node in root.traverse_preorder(ShadowIncluding::No) {
376            node.set_flag(RESET_FLAGS | NodeFlags::IS_IN_SHADOW_TREE, false);
377
378            // If the element has a shadow root attached to it then we traverse that as well,
379            // but without touching the IS_IN_SHADOW_TREE flags of the children
380            if let Some(shadow_root) = node.downcast::<Element>().and_then(Element::shadow_root) {
381                for node in shadow_root
382                    .upcast::<Node>()
383                    .traverse_preorder(ShadowIncluding::Yes)
384                {
385                    node.set_flag(RESET_FLAGS, false);
386                }
387            }
388        }
389
390        // Step 12.
391        let is_parent_connected = context.parent.is_connected();
392        let custom_element_reaction_stack = ScriptThread::custom_element_reaction_stack();
393        for node in root.traverse_preorder(ShadowIncluding::Yes) {
394            node.clean_up_style_and_layout_data();
395
396            // Step 11 & 14.1. Run the removing steps.
397            // This needs to be in its own loop, because unbind_from_tree may
398            // rely on the state of IS_IN_DOC of the context node's descendants,
399            // e.g. when removing a <form>.
400            vtable_for(&node).unbind_from_tree(context, can_gc);
401
402            // Step 12 & 14.2. Enqueue disconnected custom element reactions.
403            if is_parent_connected {
404                if let Some(element) = node.as_custom_element() {
405                    custom_element_reaction_stack.enqueue_callback_reaction(
406                        &element,
407                        CallbackReaction::Disconnected,
408                        None,
409                    );
410                }
411            }
412        }
413    }
414
415    /// Removes the given child from this node's list of children.
416    ///
417    /// Fails unless `child` is a child of this node.
418    fn remove_child(&self, child: &Node, cached_index: Option<u32>, can_gc: CanGc) {
419        assert!(child.parent_node.get().as_deref() == Some(self));
420        self.note_dirty_descendants();
421
422        let prev_sibling = child.GetPreviousSibling();
423        match prev_sibling {
424            None => {
425                self.first_child.set(child.next_sibling.get().as_deref());
426            },
427            Some(ref prev_sibling) => {
428                prev_sibling
429                    .next_sibling
430                    .set(child.next_sibling.get().as_deref());
431            },
432        }
433        let next_sibling = child.GetNextSibling();
434        match next_sibling {
435            None => {
436                self.last_child.set(child.prev_sibling.get().as_deref());
437            },
438            Some(ref next_sibling) => {
439                next_sibling
440                    .prev_sibling
441                    .set(child.prev_sibling.get().as_deref());
442            },
443        }
444
445        let context = UnbindContext::new(
446            self,
447            prev_sibling.as_deref(),
448            next_sibling.as_deref(),
449            cached_index,
450        );
451
452        child.prev_sibling.set(None);
453        child.next_sibling.set(None);
454        child.parent_node.set(None);
455        self.children_count.set(self.children_count.get() - 1);
456
457        Self::complete_remove_subtree(child, &context, can_gc);
458    }
459
460    pub(crate) fn to_untrusted_node_address(&self) -> UntrustedNodeAddress {
461        UntrustedNodeAddress(self.reflector().get_jsobject().get() as *const c_void)
462    }
463
464    pub(crate) fn to_opaque(&self) -> OpaqueNode {
465        OpaqueNode(self.reflector().get_jsobject().get() as usize)
466    }
467
468    pub(crate) fn as_custom_element(&self) -> Option<DomRoot<Element>> {
469        self.downcast::<Element>().and_then(|element| {
470            if element.is_custom() {
471                assert!(element.get_custom_element_definition().is_some());
472                Some(DomRoot::from_ref(element))
473            } else {
474                None
475            }
476        })
477    }
478
479    /// <https://html.spec.whatwg.org/multipage/#fire-a-synthetic-pointer-event>
480    pub(crate) fn fire_synthetic_pointer_event_not_trusted(&self, name: DOMString, can_gc: CanGc) {
481        // Spec says the choice of which global to create the pointer event
482        // on is not well-defined,
483        // and refers to heycam/webidl#135
484        let window = self.owner_window();
485
486        // <https://w3c.github.io/pointerevents/#the-click-auxclick-and-contextmenu-events>
487        let pointer_event = PointerEvent::new(
488            &window, // ambiguous in spec
489            name,
490            EventBubbles::Bubbles,              // Step 3: bubbles
491            EventCancelable::Cancelable,        // Step 3: cancelable
492            Some(&window),                      // Step 7: view
493            0,                                  // detail uninitialized
494            Point2D::zero(),                    // coordinates uninitialized
495            Point2D::zero(),                    // coordinates uninitialized
496            Point2D::zero(),                    // coordinates uninitialized
497            Modifiers::empty(),                 // empty modifiers
498            0,                                  // button, left mouse button
499            0,                                  // buttons
500            None,                               // related_target
501            None,                               // point_in_target
502            PointerId::NonPointerDevice as i32, // pointer_id
503            1,                                  // width
504            1,                                  // height
505            0.5,                                // pressure
506            0.0,                                // tangential_pressure
507            0,                                  // tilt_x
508            0,                                  // tilt_y
509            0,                                  // twist
510            PI / 2.0,                           // altitude_angle
511            0.0,                                // azimuth_angle
512            DOMString::from(""),                // pointer_type
513            false,                              // is_primary
514            vec![],                             // coalesced_events
515            vec![],                             // predicted_events
516            can_gc,
517        );
518
519        // Step 4. Set event's composed flag.
520        pointer_event.upcast::<Event>().set_composed(true);
521
522        // Step 5. If the not trusted flag is set, initialize event's isTrusted attribute to false.
523        pointer_event.upcast::<Event>().set_trusted(false);
524
525        // Step 6,8. TODO keyboard modifiers
526
527        pointer_event
528            .upcast::<Event>()
529            .dispatch(self.upcast::<EventTarget>(), false, can_gc);
530    }
531
532    pub(crate) fn parent_directionality(&self) -> String {
533        let mut current = self.GetParentNode();
534
535        loop {
536            match current {
537                Some(node) => {
538                    if let Some(directionality) = node
539                        .downcast::<HTMLElement>()
540                        .and_then(|html_element| html_element.directionality())
541                    {
542                        return directionality;
543                    } else {
544                        current = node.GetParentNode();
545                    }
546                },
547                None => return "ltr".to_owned(),
548            }
549        }
550    }
551}
552
553pub(crate) struct QuerySelectorIterator {
554    selectors: SelectorList<SelectorImpl>,
555    iterator: TreeIterator,
556}
557
558impl QuerySelectorIterator {
559    fn new(iter: TreeIterator, selectors: SelectorList<SelectorImpl>) -> QuerySelectorIterator {
560        QuerySelectorIterator {
561            selectors,
562            iterator: iter,
563        }
564    }
565}
566
567impl Iterator for QuerySelectorIterator {
568    type Item = DomRoot<Node>;
569
570    fn next(&mut self) -> Option<DomRoot<Node>> {
571        let selectors = &self.selectors;
572
573        self.iterator
574            .by_ref()
575            .filter_map(|node| {
576                // TODO(cgaebel): Is it worth it to build a bloom filter here
577                // (instead of passing `None`)? Probably.
578                let mut nth_index_cache = Default::default();
579                let mut ctx = MatchingContext::new(
580                    MatchingMode::Normal,
581                    None,
582                    &mut nth_index_cache,
583                    node.owner_doc().quirks_mode(),
584                    NeedsSelectorFlags::No,
585                    MatchingForInvalidation::No,
586                );
587                if let Some(element) = DomRoot::downcast(node) {
588                    if matches_selector_list(
589                        selectors,
590                        &SelectorWrapper::Borrowed(&element),
591                        &mut ctx,
592                    ) {
593                        return Some(DomRoot::upcast(element));
594                    }
595                }
596                None
597            })
598            .next()
599    }
600}
601
602impl Node {
603    fn rare_data(&self) -> Ref<'_, Option<Box<NodeRareData>>> {
604        self.rare_data.borrow()
605    }
606
607    fn ensure_rare_data(&self) -> RefMut<'_, Box<NodeRareData>> {
608        let mut rare_data = self.rare_data.borrow_mut();
609        if rare_data.is_none() {
610            *rare_data = Some(Default::default());
611        }
612        RefMut::map(rare_data, |rare_data| rare_data.as_mut().unwrap())
613    }
614
615    /// Returns true if this node is before `other` in the same connected DOM
616    /// tree.
617    pub(crate) fn is_before(&self, other: &Node) -> bool {
618        let cmp = other.CompareDocumentPosition(self);
619        if cmp & NodeConstants::DOCUMENT_POSITION_DISCONNECTED != 0 {
620            return false;
621        }
622
623        cmp & NodeConstants::DOCUMENT_POSITION_PRECEDING != 0
624    }
625
626    /// Return all registered mutation observers for this node. Lazily initialize the
627    /// raredata if it does not exist.
628    pub(crate) fn registered_mutation_observers_mut(&self) -> RefMut<'_, Vec<RegisteredObserver>> {
629        RefMut::map(self.ensure_rare_data(), |rare_data| {
630            &mut rare_data.mutation_observers
631        })
632    }
633
634    pub(crate) fn registered_mutation_observers(&self) -> Option<Ref<'_, Vec<RegisteredObserver>>> {
635        let rare_data: Ref<'_, _> = self.rare_data.borrow();
636
637        if rare_data.is_none() {
638            return None;
639        }
640        Some(Ref::map(rare_data, |rare_data| {
641            &rare_data.as_ref().unwrap().mutation_observers
642        }))
643    }
644
645    /// Add a new mutation observer for a given node.
646    pub(crate) fn add_mutation_observer(&self, observer: RegisteredObserver) {
647        self.ensure_rare_data().mutation_observers.push(observer);
648    }
649
650    /// Removes the mutation observer for a given node.
651    pub(crate) fn remove_mutation_observer(&self, observer: &MutationObserver) {
652        self.ensure_rare_data()
653            .mutation_observers
654            .retain(|reg_obs| &*reg_obs.observer != observer)
655    }
656
657    /// Dumps the subtree rooted at this node, for debugging.
658    pub(crate) fn dump(&self) {
659        self.dump_indent(0);
660    }
661
662    /// Dumps the node tree, for debugging, with indentation.
663    pub(crate) fn dump_indent(&self, indent: u32) {
664        let mut s = String::new();
665        for _ in 0..indent {
666            s.push_str("    ");
667        }
668
669        s.push_str(&self.debug_str());
670        debug!("{:?}", s);
671
672        // FIXME: this should have a pure version?
673        for kid in self.children() {
674            kid.dump_indent(indent + 1)
675        }
676    }
677
678    /// Returns a string that describes this node.
679    pub(crate) fn debug_str(&self) -> String {
680        format!("{:?}", self.type_id())
681    }
682
683    /// <https://dom.spec.whatwg.org/#in-a-document-tree>
684    pub(crate) fn is_in_a_document_tree(&self) -> bool {
685        self.flags.get().contains(NodeFlags::IS_IN_A_DOCUMENT_TREE)
686    }
687
688    /// Return true iff node's root is a shadow-root.
689    pub(crate) fn is_in_a_shadow_tree(&self) -> bool {
690        self.flags.get().contains(NodeFlags::IS_IN_SHADOW_TREE)
691    }
692
693    pub(crate) fn has_weird_parser_insertion_mode(&self) -> bool {
694        self.flags
695            .get()
696            .contains(NodeFlags::HAS_WEIRD_PARSER_INSERTION_MODE)
697    }
698
699    pub(crate) fn set_weird_parser_insertion_mode(&self) {
700        self.set_flag(NodeFlags::HAS_WEIRD_PARSER_INSERTION_MODE, true)
701    }
702
703    /// <https://dom.spec.whatwg.org/#connected>
704    pub(crate) fn is_connected(&self) -> bool {
705        self.flags.get().contains(NodeFlags::IS_CONNECTED)
706    }
707
708    pub(crate) fn set_in_ua_widget(&self, in_ua_widget: bool) {
709        self.set_flag(NodeFlags::IS_IN_UA_WIDGET, in_ua_widget)
710    }
711
712    pub(crate) fn is_in_ua_widget(&self) -> bool {
713        self.flags.get().contains(NodeFlags::IS_IN_UA_WIDGET)
714    }
715
716    /// Returns the type ID of this node.
717    pub(crate) fn type_id(&self) -> NodeTypeId {
718        match *self.eventtarget.type_id() {
719            EventTargetTypeId::Node(type_id) => type_id,
720            _ => unreachable!(),
721        }
722    }
723
724    /// <https://dom.spec.whatwg.org/#concept-node-length>
725    pub(crate) fn len(&self) -> u32 {
726        match self.type_id() {
727            NodeTypeId::DocumentType => 0,
728            NodeTypeId::CharacterData(_) => self.downcast::<CharacterData>().unwrap().Length(),
729            _ => self.children_count(),
730        }
731    }
732
733    pub(crate) fn is_empty(&self) -> bool {
734        // A node is considered empty if its length is 0.
735        self.len() == 0
736    }
737
738    /// <https://dom.spec.whatwg.org/#concept-tree-index>
739    pub(crate) fn index(&self) -> u32 {
740        self.preceding_siblings().count() as u32
741    }
742
743    /// Returns true if this node has a parent.
744    pub(crate) fn has_parent(&self) -> bool {
745        self.parent_node.get().is_some()
746    }
747
748    pub(crate) fn children_count(&self) -> u32 {
749        self.children_count.get()
750    }
751
752    pub(crate) fn ranges(&self) -> RefMut<'_, WeakRangeVec> {
753        RefMut::map(self.ensure_rare_data(), |rare_data| &mut rare_data.ranges)
754    }
755
756    pub(crate) fn ranges_is_empty(&self) -> bool {
757        self.rare_data()
758            .as_ref()
759            .is_none_or(|data| data.ranges.is_empty())
760    }
761
762    #[inline]
763    pub(crate) fn is_doctype(&self) -> bool {
764        self.type_id() == NodeTypeId::DocumentType
765    }
766
767    pub(crate) fn get_flag(&self, flag: NodeFlags) -> bool {
768        self.flags.get().contains(flag)
769    }
770
771    pub(crate) fn set_flag(&self, flag: NodeFlags, value: bool) {
772        let mut flags = self.flags.get();
773
774        if value {
775            flags.insert(flag);
776        } else {
777            flags.remove(flag);
778        }
779
780        self.flags.set(flags);
781    }
782
783    // FIXME(emilio): This and the function below should move to Element.
784    pub(crate) fn note_dirty_descendants(&self) {
785        self.owner_doc().note_node_with_dirty_descendants(self);
786    }
787
788    pub(crate) fn has_dirty_descendants(&self) -> bool {
789        self.get_flag(NodeFlags::HAS_DIRTY_DESCENDANTS)
790    }
791
792    pub(crate) fn rev_version(&self) {
793        // The new version counter is 1 plus the max of the node's current version counter,
794        // its descendants version, and the document's version. Normally, this will just be
795        // the document's version, but we do have to deal with the case where the node has moved
796        // document, so may have a higher version count than its owning document.
797        let doc: DomRoot<Node> = DomRoot::upcast(self.owner_doc());
798        let version = cmp::max(
799            self.inclusive_descendants_version(),
800            doc.inclusive_descendants_version(),
801        ) + 1;
802
803        // This `while` loop is equivalent to iterating over the non-shadow-inclusive ancestors
804        // without creating intermediate rooted DOM objects.
805        let mut node = &MutNullableDom::new(Some(self));
806        while let Some(p) = node.if_is_some(|p| {
807            p.inclusive_descendants_version.set(version);
808            &p.parent_node
809        }) {
810            node = p
811        }
812        doc.inclusive_descendants_version.set(version);
813    }
814
815    pub(crate) fn dirty(&self, damage: NodeDamage) {
816        self.rev_version();
817        if !self.is_connected() {
818            return;
819        }
820
821        match self.type_id() {
822            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::Text)) => {
823                // For content changes in text nodes, we should accurately use
824                // [`NodeDamage::ContentOrHeritage`] to mark the parent node, thereby
825                // reducing the scope of incremental box tree construction.
826                self.parent_node
827                    .get()
828                    .unwrap()
829                    .dirty(NodeDamage::ContentOrHeritage)
830            },
831            NodeTypeId::Element(_) => self.downcast::<Element>().unwrap().restyle(damage),
832            NodeTypeId::DocumentFragment(DocumentFragmentTypeId::ShadowRoot) => self
833                .downcast::<ShadowRoot>()
834                .unwrap()
835                .Host()
836                .upcast::<Element>()
837                .restyle(damage),
838            _ => {},
839        };
840    }
841
842    /// The maximum version number of this node's descendants, including itself
843    pub(crate) fn inclusive_descendants_version(&self) -> u64 {
844        self.inclusive_descendants_version.get()
845    }
846
847    /// Iterates over this node and all its descendants, in preorder.
848    pub(crate) fn traverse_preorder(&self, shadow_including: ShadowIncluding) -> TreeIterator {
849        TreeIterator::new(self, shadow_including)
850    }
851
852    pub(crate) fn inclusively_following_siblings(
853        &self,
854    ) -> impl Iterator<Item = DomRoot<Node>> + use<> {
855        SimpleNodeIterator {
856            current: Some(DomRoot::from_ref(self)),
857            next_node: |n| n.GetNextSibling(),
858        }
859    }
860
861    pub(crate) fn inclusively_preceding_siblings(
862        &self,
863    ) -> impl Iterator<Item = DomRoot<Node>> + use<> {
864        SimpleNodeIterator {
865            current: Some(DomRoot::from_ref(self)),
866            next_node: |n| n.GetPreviousSibling(),
867        }
868    }
869
870    pub(crate) fn common_ancestor(
871        &self,
872        other: &Node,
873        shadow_including: ShadowIncluding,
874    ) -> Option<DomRoot<Node>> {
875        self.inclusive_ancestors(shadow_including).find(|ancestor| {
876            other
877                .inclusive_ancestors(shadow_including)
878                .any(|node| node == *ancestor)
879        })
880    }
881
882    pub(crate) fn common_ancestor_in_flat_tree(&self, other: &Node) -> Option<DomRoot<Node>> {
883        self.inclusive_ancestors_in_flat_tree().find(|ancestor| {
884            other
885                .inclusive_ancestors_in_flat_tree()
886                .any(|node| node == *ancestor)
887        })
888    }
889
890    pub(crate) fn is_inclusive_ancestor_of(&self, child: &Node) -> bool {
891        self == child || self.is_ancestor_of(child)
892    }
893
894    pub(crate) fn is_ancestor_of(&self, child: &Node) -> bool {
895        child.ancestors().any(|ancestor| &*ancestor == self)
896    }
897
898    pub(crate) fn is_shadow_including_inclusive_ancestor_of(&self, node: &Node) -> bool {
899        node.inclusive_ancestors(ShadowIncluding::Yes)
900            .any(|ancestor| &*ancestor == self)
901    }
902
903    pub(crate) fn following_siblings(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
904        SimpleNodeIterator {
905            current: self.GetNextSibling(),
906            next_node: |n| n.GetNextSibling(),
907        }
908    }
909
910    pub(crate) fn preceding_siblings(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
911        SimpleNodeIterator {
912            current: self.GetPreviousSibling(),
913            next_node: |n| n.GetPreviousSibling(),
914        }
915    }
916
917    pub(crate) fn following_nodes(&self, root: &Node) -> FollowingNodeIterator {
918        FollowingNodeIterator {
919            current: Some(DomRoot::from_ref(self)),
920            root: DomRoot::from_ref(root),
921        }
922    }
923
924    pub(crate) fn preceding_nodes(&self, root: &Node) -> PrecedingNodeIterator {
925        PrecedingNodeIterator {
926            current: Some(DomRoot::from_ref(self)),
927            root: DomRoot::from_ref(root),
928        }
929    }
930
931    pub(crate) fn descending_last_children(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
932        SimpleNodeIterator {
933            current: self.GetLastChild(),
934            next_node: |n| n.GetLastChild(),
935        }
936    }
937
938    pub(crate) fn is_parent_of(&self, child: &Node) -> bool {
939        child
940            .parent_node
941            .get()
942            .is_some_and(|parent| &*parent == self)
943    }
944
945    pub(crate) fn to_trusted_node_address(&self) -> TrustedNodeAddress {
946        TrustedNodeAddress(self as *const Node as *const libc::c_void)
947    }
948
949    pub(crate) fn content_box(&self) -> Option<Rect<Au>> {
950        self.owner_window()
951            .box_area_query(self, BoxAreaType::Content)
952    }
953
954    pub(crate) fn border_box(&self) -> Option<Rect<Au>> {
955        self.owner_window()
956            .box_area_query(self, BoxAreaType::Border)
957    }
958
959    pub(crate) fn border_boxes(&self) -> Vec<Rect<Au>> {
960        self.owner_window()
961            .box_areas_query(self, BoxAreaType::Border)
962    }
963
964    pub(crate) fn client_rect(&self) -> Rect<i32> {
965        self.owner_window().client_rect_query(self)
966    }
967
968    /// <https://drafts.csswg.org/cssom-view/#dom-element-scrollwidth>
969    /// <https://drafts.csswg.org/cssom-view/#dom-element-scrollheight>
970    pub(crate) fn scroll_area(&self) -> Rect<i32> {
971        // "1. Let document be the element’s node document.""
972        let document = self.owner_doc();
973
974        // "2. If document is not the active document, return zero and terminate these steps.""
975        if !document.is_active() {
976            return Rect::zero();
977        }
978
979        // "3. Let viewport width/height be the width of the viewport excluding the width/height of the
980        // scroll bar, if any, or zero if there is no viewport."
981        let window = document.window();
982        let viewport = Size2D::new(window.InnerWidth(), window.InnerHeight());
983
984        let in_quirks_mode = document.quirks_mode() == QuirksMode::Quirks;
985        let is_root = self.downcast::<Element>().is_some_and(|e| e.is_root());
986        let is_body_element = self
987            .downcast::<HTMLElement>()
988            .is_some_and(|e| e.is_body_element());
989
990        // "4. If the element is the root element and document is not in quirks mode
991        // return max(viewport scrolling area width/height, viewport width/height)."
992        // "5. If the element is the body element, document is in quirks mode and the
993        // element is not potentially scrollable, return max(viewport scrolling area
994        // width, viewport width)."
995        if (is_root && !in_quirks_mode) || (is_body_element && in_quirks_mode) {
996            let viewport_scrolling_area = window.scrolling_area_query(None);
997            return Rect::new(
998                viewport_scrolling_area.origin,
999                viewport_scrolling_area.size.max(viewport),
1000            );
1001        }
1002
1003        // "6. If the element does not have any associated box return zero and terminate
1004        // these steps."
1005        // "7. Return the width of the element’s scrolling area."
1006        window.scrolling_area_query(Some(self))
1007    }
1008
1009    /// <https://dom.spec.whatwg.org/#dom-childnode-before>
1010    pub(crate) fn before(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1011        // Step 1.
1012        let parent = &self.parent_node;
1013
1014        // Step 2.
1015        let parent = match parent.get() {
1016            None => return Ok(()),
1017            Some(parent) => parent,
1018        };
1019
1020        // Step 3.
1021        let viable_previous_sibling = first_node_not_in(self.preceding_siblings(), &nodes);
1022
1023        // Step 4.
1024        let node = self
1025            .owner_doc()
1026            .node_from_nodes_and_strings(nodes, can_gc)?;
1027
1028        // Step 5.
1029        let viable_previous_sibling = match viable_previous_sibling {
1030            Some(ref viable_previous_sibling) => viable_previous_sibling.next_sibling.get(),
1031            None => parent.first_child.get(),
1032        };
1033
1034        // Step 6.
1035        Node::pre_insert(&node, &parent, viable_previous_sibling.as_deref(), can_gc)?;
1036
1037        Ok(())
1038    }
1039
1040    /// <https://dom.spec.whatwg.org/#dom-childnode-after>
1041    pub(crate) fn after(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1042        // Step 1.
1043        let parent = &self.parent_node;
1044
1045        // Step 2.
1046        let parent = match parent.get() {
1047            None => return Ok(()),
1048            Some(parent) => parent,
1049        };
1050
1051        // Step 3.
1052        let viable_next_sibling = first_node_not_in(self.following_siblings(), &nodes);
1053
1054        // Step 4.
1055        let node = self
1056            .owner_doc()
1057            .node_from_nodes_and_strings(nodes, can_gc)?;
1058
1059        // Step 5.
1060        Node::pre_insert(&node, &parent, viable_next_sibling.as_deref(), can_gc)?;
1061
1062        Ok(())
1063    }
1064
1065    /// <https://dom.spec.whatwg.org/#dom-childnode-replacewith>
1066    pub(crate) fn replace_with(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1067        // Step 1. Let parent be this’s parent.
1068        let Some(parent) = self.GetParentNode() else {
1069            // Step 2. If parent is null, then return.
1070            return Ok(());
1071        };
1072
1073        // Step 3. Let viableNextSibling be this’s first following sibling not in nodes; otherwise null.
1074        let viable_next_sibling = first_node_not_in(self.following_siblings(), &nodes);
1075
1076        // Step 4. Let node be the result of converting nodes into a node, given nodes and this’s node document.
1077        let node = self
1078            .owner_doc()
1079            .node_from_nodes_and_strings(nodes, can_gc)?;
1080
1081        if self.parent_node == Some(&*parent) {
1082            // Step 5. If this’s parent is parent, replace this with node within parent.
1083            parent.ReplaceChild(&node, self, can_gc)?;
1084        } else {
1085            // Step 6. Otherwise, pre-insert node into parent before viableNextSibling.
1086            Node::pre_insert(&node, &parent, viable_next_sibling.as_deref(), can_gc)?;
1087        }
1088        Ok(())
1089    }
1090
1091    /// <https://dom.spec.whatwg.org/#dom-parentnode-prepend>
1092    pub(crate) fn prepend(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1093        // Step 1.
1094        let doc = self.owner_doc();
1095        let node = doc.node_from_nodes_and_strings(nodes, can_gc)?;
1096        // Step 2.
1097        let first_child = self.first_child.get();
1098        Node::pre_insert(&node, self, first_child.as_deref(), can_gc).map(|_| ())
1099    }
1100
1101    /// <https://dom.spec.whatwg.org/#dom-parentnode-append>
1102    pub(crate) fn append(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1103        // Step 1.
1104        let doc = self.owner_doc();
1105        let node = doc.node_from_nodes_and_strings(nodes, can_gc)?;
1106        // Step 2.
1107        self.AppendChild(&node, can_gc).map(|_| ())
1108    }
1109
1110    /// <https://dom.spec.whatwg.org/#dom-parentnode-replacechildren>
1111    pub(crate) fn replace_children(&self, nodes: Vec<NodeOrString>, can_gc: CanGc) -> ErrorResult {
1112        // Step 1.
1113        let doc = self.owner_doc();
1114        let node = doc.node_from_nodes_and_strings(nodes, can_gc)?;
1115        // Step 2.
1116        Node::ensure_pre_insertion_validity(&node, self, None)?;
1117        // Step 3.
1118        Node::replace_all(Some(&node), self, can_gc);
1119        Ok(())
1120    }
1121
1122    /// <https://dom.spec.whatwg.org/#dom-parentnode-queryselector>
1123    pub(crate) fn query_selector(
1124        &self,
1125        selectors: DOMString,
1126    ) -> Fallible<Option<DomRoot<Element>>> {
1127        // Step 1.
1128        let doc = self.owner_doc();
1129        match SelectorParser::parse_author_origin_no_namespace(
1130            &selectors,
1131            &UrlExtraData(doc.url().get_arc()),
1132        ) {
1133            // Step 2.
1134            Err(_) => Err(Error::Syntax(None)),
1135            // Step 3.
1136            Ok(selectors) => {
1137                let mut nth_index_cache = Default::default();
1138                let mut ctx = MatchingContext::new(
1139                    MatchingMode::Normal,
1140                    None,
1141                    &mut nth_index_cache,
1142                    doc.quirks_mode(),
1143                    NeedsSelectorFlags::No,
1144                    MatchingForInvalidation::No,
1145                );
1146                let mut descendants = self.traverse_preorder(ShadowIncluding::No);
1147                // Skip the root of the tree.
1148                assert!(&*descendants.next().unwrap() == self);
1149                Ok(descendants.filter_map(DomRoot::downcast).find(|element| {
1150                    matches_selector_list(&selectors, &SelectorWrapper::Borrowed(element), &mut ctx)
1151                }))
1152            },
1153        }
1154    }
1155
1156    /// <https://dom.spec.whatwg.org/#scope-match-a-selectors-string>
1157    /// Get an iterator over all nodes which match a set of selectors
1158    /// Be careful not to do anything which may manipulate the DOM tree
1159    /// whilst iterating, otherwise the iterator may be invalidated.
1160    pub(crate) fn query_selector_iter(
1161        &self,
1162        selectors: DOMString,
1163    ) -> Fallible<QuerySelectorIterator> {
1164        // Step 1.
1165        let url = self.owner_doc().url();
1166        match SelectorParser::parse_author_origin_no_namespace(
1167            &selectors,
1168            &UrlExtraData(url.get_arc()),
1169        ) {
1170            // Step 2.
1171            Err(_) => Err(Error::Syntax(None)),
1172            // Step 3.
1173            Ok(selectors) => {
1174                let mut descendants = self.traverse_preorder(ShadowIncluding::No);
1175                // Skip the root of the tree.
1176                assert!(&*descendants.next().unwrap() == self);
1177                Ok(QuerySelectorIterator::new(descendants, selectors))
1178            },
1179        }
1180    }
1181
1182    /// <https://dom.spec.whatwg.org/#dom-parentnode-queryselectorall>
1183    #[allow(unsafe_code)]
1184    pub(crate) fn query_selector_all(&self, selectors: DOMString) -> Fallible<DomRoot<NodeList>> {
1185        let window = self.owner_window();
1186        let iter = self.query_selector_iter(selectors)?;
1187        Ok(NodeList::new_simple_list(&window, iter, CanGc::note()))
1188    }
1189
1190    pub(crate) fn ancestors(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
1191        SimpleNodeIterator {
1192            current: self.GetParentNode(),
1193            next_node: |n| n.GetParentNode(),
1194        }
1195    }
1196
1197    /// <https://dom.spec.whatwg.org/#concept-shadow-including-inclusive-ancestor>
1198    pub(crate) fn inclusive_ancestors(
1199        &self,
1200        shadow_including: ShadowIncluding,
1201    ) -> impl Iterator<Item = DomRoot<Node>> + use<> {
1202        SimpleNodeIterator {
1203            current: Some(DomRoot::from_ref(self)),
1204            next_node: move |n| {
1205                if shadow_including == ShadowIncluding::Yes {
1206                    if let Some(shadow_root) = n.downcast::<ShadowRoot>() {
1207                        return Some(DomRoot::from_ref(shadow_root.Host().upcast::<Node>()));
1208                    }
1209                }
1210                n.GetParentNode()
1211            },
1212        }
1213    }
1214
1215    pub(crate) fn owner_doc(&self) -> DomRoot<Document> {
1216        self.owner_doc.get().unwrap()
1217    }
1218
1219    pub(crate) fn set_owner_doc(&self, document: &Document) {
1220        self.owner_doc.set(Some(document));
1221    }
1222
1223    pub(crate) fn containing_shadow_root(&self) -> Option<DomRoot<ShadowRoot>> {
1224        self.rare_data()
1225            .as_ref()?
1226            .containing_shadow_root
1227            .as_ref()
1228            .map(|sr| DomRoot::from_ref(&**sr))
1229    }
1230
1231    pub(crate) fn set_containing_shadow_root(&self, shadow_root: Option<&ShadowRoot>) {
1232        self.ensure_rare_data().containing_shadow_root = shadow_root.map(Dom::from_ref);
1233    }
1234
1235    pub(crate) fn is_in_html_doc(&self) -> bool {
1236        self.owner_doc().is_html_document()
1237    }
1238
1239    pub(crate) fn is_connected_with_browsing_context(&self) -> bool {
1240        self.is_connected() && self.owner_doc().browsing_context().is_some()
1241    }
1242
1243    pub(crate) fn children(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
1244        SimpleNodeIterator {
1245            current: self.GetFirstChild(),
1246            next_node: |n| n.GetNextSibling(),
1247        }
1248    }
1249
1250    pub(crate) fn rev_children(&self) -> impl Iterator<Item = DomRoot<Node>> + use<> {
1251        SimpleNodeIterator {
1252            current: self.GetLastChild(),
1253            next_node: |n| n.GetPreviousSibling(),
1254        }
1255    }
1256
1257    pub(crate) fn child_elements(&self) -> impl Iterator<Item = DomRoot<Element>> + use<> {
1258        self.children()
1259            .filter_map(DomRoot::downcast as fn(_) -> _)
1260            .peekable()
1261    }
1262
1263    pub(crate) fn remove_self(&self, can_gc: CanGc) {
1264        if let Some(ref parent) = self.GetParentNode() {
1265            Node::remove(self, parent, SuppressObserver::Unsuppressed, can_gc);
1266        }
1267    }
1268
1269    pub(crate) fn unique_id(&self, pipeline: PipelineId) -> String {
1270        let mut rare_data = self.ensure_rare_data();
1271
1272        if rare_data.unique_id.is_none() {
1273            let node_id = UniqueId::new();
1274            ScriptThread::save_node_id(pipeline, node_id.borrow().simple().to_string());
1275            rare_data.unique_id = Some(node_id);
1276        }
1277        rare_data
1278            .unique_id
1279            .as_ref()
1280            .unwrap()
1281            .borrow()
1282            .simple()
1283            .to_string()
1284    }
1285
1286    pub(crate) fn summarize(&self, can_gc: CanGc) -> NodeInfo {
1287        let USVString(base_uri) = self.BaseURI();
1288        let node_type = self.NodeType();
1289        let pipeline = self.owner_window().pipeline_id();
1290
1291        let maybe_shadow_root = self.downcast::<ShadowRoot>();
1292        let shadow_root_mode = maybe_shadow_root
1293            .map(ShadowRoot::Mode)
1294            .map(ShadowRootMode::convert);
1295        let host = maybe_shadow_root
1296            .map(ShadowRoot::Host)
1297            .map(|host| host.upcast::<Node>().unique_id(pipeline));
1298        let is_shadow_host = self.downcast::<Element>().is_some_and(|potential_host| {
1299            let Some(root) = potential_host.shadow_root() else {
1300                return false;
1301            };
1302            !root.is_user_agent_widget() || pref!(inspector_show_servo_internal_shadow_roots)
1303        });
1304
1305        let num_children = if is_shadow_host {
1306            // Shadow roots count as children
1307            self.ChildNodes(can_gc).Length() as usize + 1
1308        } else {
1309            self.ChildNodes(can_gc).Length() as usize
1310        };
1311
1312        let window = self.owner_window();
1313        let display = self
1314            .downcast::<Element>()
1315            .map(|elem| window.GetComputedStyle(elem, None))
1316            .map(|style| style.Display().into());
1317
1318        NodeInfo {
1319            unique_id: self.unique_id(pipeline),
1320            host,
1321            base_uri,
1322            parent: self
1323                .GetParentNode()
1324                .map_or("".to_owned(), |node| node.unique_id(pipeline)),
1325            node_type,
1326            is_top_level_document: node_type == NodeConstants::DOCUMENT_NODE,
1327            node_name: String::from(self.NodeName()),
1328            node_value: self.GetNodeValue().map(|v| v.into()),
1329            num_children,
1330            attrs: self.downcast().map(Element::summarize).unwrap_or(vec![]),
1331            is_shadow_host,
1332            shadow_root_mode,
1333            display,
1334            // It is not entirely clear when this should be set to false.
1335            // Firefox considers nodes with "display: contents" to be displayed.
1336            // The doctype node is displayed despite being `display: none`.
1337            is_displayed: !self.is_display_none() || self.is::<DocumentType>(),
1338            doctype_name: self
1339                .downcast::<DocumentType>()
1340                .map(DocumentType::name)
1341                .cloned()
1342                .map(String::from),
1343            doctype_public_identifier: self
1344                .downcast::<DocumentType>()
1345                .map(DocumentType::public_id)
1346                .cloned()
1347                .map(String::from),
1348            doctype_system_identifier: self
1349                .downcast::<DocumentType>()
1350                .map(DocumentType::system_id)
1351                .cloned()
1352                .map(String::from),
1353        }
1354    }
1355
1356    /// Used by `HTMLTableSectionElement::InsertRow` and `HTMLTableRowElement::InsertCell`
1357    pub(crate) fn insert_cell_or_row<F, G, I>(
1358        &self,
1359        index: i32,
1360        get_items: F,
1361        new_child: G,
1362        can_gc: CanGc,
1363    ) -> Fallible<DomRoot<HTMLElement>>
1364    where
1365        F: Fn() -> DomRoot<HTMLCollection>,
1366        G: Fn() -> DomRoot<I>,
1367        I: DerivedFrom<Node> + DerivedFrom<HTMLElement> + DomObject,
1368    {
1369        if index < -1 {
1370            return Err(Error::IndexSize);
1371        }
1372
1373        let tr = new_child();
1374
1375        {
1376            let tr_node = tr.upcast::<Node>();
1377            if index == -1 {
1378                self.InsertBefore(tr_node, None, can_gc)?;
1379            } else {
1380                let items = get_items();
1381                let node = match items
1382                    .elements_iter()
1383                    .map(DomRoot::upcast::<Node>)
1384                    .map(Some)
1385                    .chain(iter::once(None))
1386                    .nth(index as usize)
1387                {
1388                    None => return Err(Error::IndexSize),
1389                    Some(node) => node,
1390                };
1391                self.InsertBefore(tr_node, node.as_deref(), can_gc)?;
1392            }
1393        }
1394
1395        Ok(DomRoot::upcast::<HTMLElement>(tr))
1396    }
1397
1398    /// Used by `HTMLTableSectionElement::DeleteRow` and `HTMLTableRowElement::DeleteCell`
1399    pub(crate) fn delete_cell_or_row<F, G>(
1400        &self,
1401        index: i32,
1402        get_items: F,
1403        is_delete_type: G,
1404        can_gc: CanGc,
1405    ) -> ErrorResult
1406    where
1407        F: Fn() -> DomRoot<HTMLCollection>,
1408        G: Fn(&Element) -> bool,
1409    {
1410        let element = match index {
1411            index if index < -1 => return Err(Error::IndexSize),
1412            -1 => {
1413                let last_child = self.upcast::<Node>().GetLastChild();
1414                match last_child.and_then(|node| {
1415                    node.inclusively_preceding_siblings()
1416                        .filter_map(DomRoot::downcast::<Element>)
1417                        .find(|elem| is_delete_type(elem))
1418                }) {
1419                    Some(element) => element,
1420                    None => return Ok(()),
1421                }
1422            },
1423            index => match get_items().Item(index as u32) {
1424                Some(element) => element,
1425                None => return Err(Error::IndexSize),
1426            },
1427        };
1428
1429        element.upcast::<Node>().remove_self(can_gc);
1430        Ok(())
1431    }
1432
1433    pub(crate) fn get_stylesheet(&self) -> Option<Arc<Stylesheet>> {
1434        if let Some(node) = self.downcast::<HTMLStyleElement>() {
1435            node.get_stylesheet()
1436        } else if let Some(node) = self.downcast::<HTMLLinkElement>() {
1437            node.get_stylesheet()
1438        } else {
1439            None
1440        }
1441    }
1442
1443    pub(crate) fn get_cssom_stylesheet(&self) -> Option<DomRoot<CSSStyleSheet>> {
1444        if let Some(node) = self.downcast::<HTMLStyleElement>() {
1445            node.get_cssom_stylesheet()
1446        } else if let Some(node) = self.downcast::<HTMLLinkElement>() {
1447            node.get_cssom_stylesheet(CanGc::note())
1448        } else {
1449            None
1450        }
1451    }
1452
1453    pub(crate) fn is_styled(&self) -> bool {
1454        self.style_data.borrow().is_some()
1455    }
1456
1457    pub(crate) fn is_display_none(&self) -> bool {
1458        self.style_data.borrow().as_ref().is_none_or(|data| {
1459            data.element_data
1460                .borrow()
1461                .styles
1462                .primary()
1463                .get_box()
1464                .display
1465                .is_none()
1466        })
1467    }
1468
1469    pub(crate) fn style(&self) -> Option<Arc<ComputedValues>> {
1470        self.owner_window().layout_reflow(QueryMsg::StyleQuery);
1471        self.style_data
1472            .borrow()
1473            .as_ref()
1474            .map(|data| data.element_data.borrow().styles.primary().clone())
1475    }
1476
1477    /// <https://html.spec.whatwg.org/multipage/#language>
1478    pub(crate) fn get_lang(&self) -> Option<String> {
1479        self.inclusive_ancestors(ShadowIncluding::Yes)
1480            .filter_map(|node| {
1481                node.downcast::<Element>().and_then(|el| {
1482                    el.get_attribute(&ns!(xml), &local_name!("lang"))
1483                        .or_else(|| el.get_attribute(&ns!(), &local_name!("lang")))
1484                        .map(|attr| String::from(attr.Value()))
1485                })
1486                // TODO: Check meta tags for a pragma-set default language
1487                // TODO: Check HTTP Content-Language header
1488            })
1489            .next()
1490    }
1491
1492    /// <https://dom.spec.whatwg.org/#assign-slotables-for-a-tree>
1493    pub(crate) fn assign_slottables_for_a_tree(&self) {
1494        // NOTE: This method traverses all descendants of the node and is potentially very
1495        // expensive. If the node is not a shadow root then assigning slottables to it won't
1496        // have any effect, so we take a fast path out.
1497        let Some(shadow_root) = self.downcast::<ShadowRoot>() else {
1498            return;
1499        };
1500
1501        if !shadow_root.has_slot_descendants() {
1502            return;
1503        }
1504
1505        // > To assign slottables for a tree, given a node root, run assign slottables for each slot
1506        // > slot in root’s inclusive descendants, in tree order.
1507        for node in self.traverse_preorder(ShadowIncluding::No) {
1508            if let Some(slot) = node.downcast::<HTMLSlotElement>() {
1509                slot.assign_slottables();
1510            }
1511        }
1512    }
1513
1514    pub(crate) fn assigned_slot(&self) -> Option<DomRoot<HTMLSlotElement>> {
1515        let assigned_slot = self
1516            .rare_data
1517            .borrow()
1518            .as_ref()?
1519            .slottable_data
1520            .assigned_slot
1521            .as_ref()?
1522            .as_rooted();
1523        Some(assigned_slot)
1524    }
1525
1526    pub(crate) fn set_assigned_slot(&self, assigned_slot: Option<&HTMLSlotElement>) {
1527        self.ensure_rare_data().slottable_data.assigned_slot = assigned_slot.map(Dom::from_ref);
1528    }
1529
1530    pub(crate) fn manual_slot_assignment(&self) -> Option<DomRoot<HTMLSlotElement>> {
1531        let manually_assigned_slot = self
1532            .rare_data
1533            .borrow()
1534            .as_ref()?
1535            .slottable_data
1536            .manual_slot_assignment
1537            .as_ref()?
1538            .as_rooted();
1539        Some(manually_assigned_slot)
1540    }
1541
1542    pub(crate) fn set_manual_slot_assignment(
1543        &self,
1544        manually_assigned_slot: Option<&HTMLSlotElement>,
1545    ) {
1546        self.ensure_rare_data()
1547            .slottable_data
1548            .manual_slot_assignment = manually_assigned_slot.map(Dom::from_ref);
1549    }
1550
1551    /// Gets the parent of this node from the perspective of layout and style.
1552    ///
1553    /// The returned node is the node's assigned slot, if any, or the
1554    /// shadow host if it's a shadow root. Otherwise, it is the node's
1555    /// parent.
1556    pub(crate) fn parent_in_flat_tree(&self) -> Option<DomRoot<Node>> {
1557        if let Some(assigned_slot) = self.assigned_slot() {
1558            return Some(DomRoot::upcast(assigned_slot));
1559        }
1560
1561        let parent_or_none = self.GetParentNode();
1562        if let Some(parent) = parent_or_none.as_deref() {
1563            if let Some(shadow_root) = parent.downcast::<ShadowRoot>() {
1564                return Some(DomRoot::from_ref(shadow_root.Host().upcast::<Node>()));
1565            }
1566        }
1567
1568        parent_or_none
1569    }
1570
1571    pub(crate) fn inclusive_ancestors_in_flat_tree(
1572        &self,
1573    ) -> impl Iterator<Item = DomRoot<Node>> + use<> {
1574        SimpleNodeIterator {
1575            current: Some(DomRoot::from_ref(self)),
1576            next_node: move |n| n.parent_in_flat_tree(),
1577        }
1578    }
1579
1580    /// We are marking this as an implemented pseudo element.
1581    pub(crate) fn set_implemented_pseudo_element(&self, pseudo_element: PseudoElement) {
1582        // Implemented pseudo element should exist only in the UA shadow DOM.
1583        debug_assert!(self.is_in_ua_widget());
1584        self.ensure_rare_data().implemented_pseudo_element = Some(pseudo_element);
1585    }
1586
1587    pub(crate) fn implemented_pseudo_element(&self) -> Option<PseudoElement> {
1588        self.rare_data
1589            .borrow()
1590            .as_ref()
1591            .and_then(|rare_data| rare_data.implemented_pseudo_element)
1592    }
1593}
1594
1595/// Iterate through `nodes` until we find a `Node` that is not in `not_in`
1596fn first_node_not_in<I>(mut nodes: I, not_in: &[NodeOrString]) -> Option<DomRoot<Node>>
1597where
1598    I: Iterator<Item = DomRoot<Node>>,
1599{
1600    nodes.find(|node| {
1601        not_in.iter().all(|n| match *n {
1602            NodeOrString::Node(ref n) => n != node,
1603            _ => true,
1604        })
1605    })
1606}
1607
1608/// If the given untrusted node address represents a valid DOM node in the given runtime,
1609/// returns it.
1610#[allow(unsafe_code)]
1611pub(crate) unsafe fn from_untrusted_node_address(candidate: UntrustedNodeAddress) -> DomRoot<Node> {
1612    let node = unsafe { Node::from_untrusted_node_address(candidate) };
1613    DomRoot::from_ref(node)
1614}
1615
1616#[allow(unsafe_code)]
1617pub(crate) trait LayoutNodeHelpers<'dom> {
1618    fn type_id_for_layout(self) -> NodeTypeId;
1619
1620    fn parent_node_ref(self) -> Option<LayoutDom<'dom, Node>>;
1621    fn composed_parent_node_ref(self) -> Option<LayoutDom<'dom, Node>>;
1622    fn first_child_ref(self) -> Option<LayoutDom<'dom, Node>>;
1623    fn last_child_ref(self) -> Option<LayoutDom<'dom, Node>>;
1624    fn prev_sibling_ref(self) -> Option<LayoutDom<'dom, Node>>;
1625    fn next_sibling_ref(self) -> Option<LayoutDom<'dom, Node>>;
1626
1627    fn owner_doc_for_layout(self) -> LayoutDom<'dom, Document>;
1628    fn containing_shadow_root_for_layout(self) -> Option<LayoutDom<'dom, ShadowRoot>>;
1629    fn assigned_slot_for_layout(self) -> Option<LayoutDom<'dom, HTMLSlotElement>>;
1630
1631    fn is_element_for_layout(&self) -> bool;
1632    fn is_text_node_for_layout(&self) -> bool;
1633    unsafe fn get_flag(self, flag: NodeFlags) -> bool;
1634    unsafe fn set_flag(self, flag: NodeFlags, value: bool);
1635
1636    fn style_data(self) -> Option<&'dom StyleData>;
1637    fn layout_data(self) -> Option<&'dom GenericLayoutData>;
1638
1639    /// Initialize the style data of this node.
1640    ///
1641    /// # Safety
1642    ///
1643    /// This method is unsafe because it modifies the given node during
1644    /// layout. Callers should ensure that no other layout thread is
1645    /// attempting to read or modify the opaque layout data of this node.
1646    unsafe fn initialize_style_data(self);
1647
1648    /// Initialize the opaque layout data of this node.
1649    ///
1650    /// # Safety
1651    ///
1652    /// This method is unsafe because it modifies the given node during
1653    /// layout. Callers should ensure that no other layout thread is
1654    /// attempting to read or modify the opaque layout data of this node.
1655    unsafe fn initialize_layout_data(self, data: Box<GenericLayoutData>);
1656
1657    /// Clear the style and opaque layout data of this node.
1658    ///
1659    /// # Safety
1660    ///
1661    /// This method is unsafe because it modifies the given node during
1662    /// layout. Callers should ensure that no other layout thread is
1663    /// attempting to read or modify the opaque layout data of this node.
1664    unsafe fn clear_style_and_layout_data(self);
1665
1666    /// Whether this element is a `<input>` rendered as text or a `<textarea>`.
1667    /// This is used for the rendering of text control element in the past
1668    /// where the necessities is being handled within layout. With the current
1669    /// implementation of Shadow DOM, we are able to move and expand this kind
1670    /// of behavior in the previous pipelines (i.e. DOM, style traversal).
1671    fn is_text_input(&self) -> bool;
1672
1673    /// Whether this element serve as a container of editable text for a text input
1674    /// that is implemented as an UA widget.
1675    fn is_single_line_text_inner_editor(&self) -> bool;
1676
1677    /// Whether this element serve as a container of any text inside a text input
1678    /// that is implemented as an UA widget.
1679    fn is_text_container_of_single_line_input(&self) -> bool;
1680    fn text_content(self) -> Cow<'dom, str>;
1681    fn selection(self) -> Option<Range<usize>>;
1682    fn image_url(self) -> Option<ServoUrl>;
1683    fn image_density(self) -> Option<f64>;
1684    fn image_data(self) -> Option<(Option<Image>, Option<ImageMetadata>)>;
1685    fn canvas_data(self) -> Option<HTMLCanvasData>;
1686    fn media_data(self) -> Option<HTMLMediaData>;
1687    fn svg_data(self) -> Option<SVGElementData>;
1688    fn iframe_browsing_context_id(self) -> Option<BrowsingContextId>;
1689    fn iframe_pipeline_id(self) -> Option<PipelineId>;
1690    fn opaque(self) -> OpaqueNode;
1691    fn implemented_pseudo_element(&self) -> Option<PseudoElement>;
1692    fn is_in_ua_widget(&self) -> bool;
1693}
1694
1695impl<'dom> LayoutDom<'dom, Node> {
1696    #[inline]
1697    #[allow(unsafe_code)]
1698    pub(crate) fn parent_node_ref(self) -> Option<LayoutDom<'dom, Node>> {
1699        unsafe { self.unsafe_get().parent_node.get_inner_as_layout() }
1700    }
1701}
1702
1703impl<'dom> LayoutNodeHelpers<'dom> for LayoutDom<'dom, Node> {
1704    #[inline]
1705    fn type_id_for_layout(self) -> NodeTypeId {
1706        self.unsafe_get().type_id()
1707    }
1708
1709    #[inline]
1710    fn is_element_for_layout(&self) -> bool {
1711        (*self).is::<Element>()
1712    }
1713
1714    fn is_text_node_for_layout(&self) -> bool {
1715        self.type_id_for_layout() ==
1716            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::Text))
1717    }
1718
1719    #[inline]
1720    #[allow(unsafe_code)]
1721    fn parent_node_ref(self) -> Option<LayoutDom<'dom, Node>> {
1722        unsafe { self.unsafe_get().parent_node.get_inner_as_layout() }
1723    }
1724
1725    #[inline]
1726    fn composed_parent_node_ref(self) -> Option<LayoutDom<'dom, Node>> {
1727        let parent = self.parent_node_ref();
1728        if let Some(parent) = parent {
1729            if let Some(shadow_root) = parent.downcast::<ShadowRoot>() {
1730                return Some(shadow_root.get_host_for_layout().upcast());
1731            }
1732        }
1733        parent
1734    }
1735
1736    #[inline]
1737    #[allow(unsafe_code)]
1738    fn first_child_ref(self) -> Option<LayoutDom<'dom, Node>> {
1739        unsafe { self.unsafe_get().first_child.get_inner_as_layout() }
1740    }
1741
1742    #[inline]
1743    #[allow(unsafe_code)]
1744    fn last_child_ref(self) -> Option<LayoutDom<'dom, Node>> {
1745        unsafe { self.unsafe_get().last_child.get_inner_as_layout() }
1746    }
1747
1748    #[inline]
1749    #[allow(unsafe_code)]
1750    fn prev_sibling_ref(self) -> Option<LayoutDom<'dom, Node>> {
1751        unsafe { self.unsafe_get().prev_sibling.get_inner_as_layout() }
1752    }
1753
1754    #[inline]
1755    #[allow(unsafe_code)]
1756    fn next_sibling_ref(self) -> Option<LayoutDom<'dom, Node>> {
1757        unsafe { self.unsafe_get().next_sibling.get_inner_as_layout() }
1758    }
1759
1760    #[inline]
1761    #[allow(unsafe_code)]
1762    fn owner_doc_for_layout(self) -> LayoutDom<'dom, Document> {
1763        unsafe { self.unsafe_get().owner_doc.get_inner_as_layout().unwrap() }
1764    }
1765
1766    #[inline]
1767    #[allow(unsafe_code)]
1768    fn containing_shadow_root_for_layout(self) -> Option<LayoutDom<'dom, ShadowRoot>> {
1769        unsafe {
1770            self.unsafe_get()
1771                .rare_data
1772                .borrow_for_layout()
1773                .as_ref()?
1774                .containing_shadow_root
1775                .as_ref()
1776                .map(|sr| sr.to_layout())
1777        }
1778    }
1779
1780    #[inline]
1781    #[allow(unsafe_code)]
1782    fn assigned_slot_for_layout(self) -> Option<LayoutDom<'dom, HTMLSlotElement>> {
1783        unsafe {
1784            self.unsafe_get()
1785                .rare_data
1786                .borrow_for_layout()
1787                .as_ref()?
1788                .slottable_data
1789                .assigned_slot
1790                .as_ref()
1791                .map(|assigned_slot| assigned_slot.to_layout())
1792        }
1793    }
1794
1795    // FIXME(nox): get_flag/set_flag (especially the latter) are not safe because
1796    // they mutate stuff while values of this type can be used from multiple
1797    // threads at once, this should be revisited.
1798
1799    #[inline]
1800    #[allow(unsafe_code)]
1801    unsafe fn get_flag(self, flag: NodeFlags) -> bool {
1802        (self.unsafe_get()).flags.get().contains(flag)
1803    }
1804
1805    #[inline]
1806    #[allow(unsafe_code)]
1807    unsafe fn set_flag(self, flag: NodeFlags, value: bool) {
1808        let this = self.unsafe_get();
1809        let mut flags = (this).flags.get();
1810
1811        if value {
1812            flags.insert(flag);
1813        } else {
1814            flags.remove(flag);
1815        }
1816
1817        (this).flags.set(flags);
1818    }
1819
1820    // FIXME(nox): How we handle style and layout data needs to be completely
1821    // revisited so we can do that more cleanly and safely in layout 2020.
1822    #[inline]
1823    #[allow(unsafe_code)]
1824    fn style_data(self) -> Option<&'dom StyleData> {
1825        unsafe { self.unsafe_get().style_data.borrow_for_layout().as_deref() }
1826    }
1827
1828    #[inline]
1829    #[allow(unsafe_code)]
1830    fn layout_data(self) -> Option<&'dom GenericLayoutData> {
1831        unsafe { self.unsafe_get().layout_data.borrow_for_layout().as_deref() }
1832    }
1833
1834    #[inline]
1835    #[allow(unsafe_code)]
1836    unsafe fn initialize_style_data(self) {
1837        let data = unsafe { self.unsafe_get().style_data.borrow_mut_for_layout() };
1838        debug_assert!(data.is_none());
1839        *data = Some(Box::default());
1840    }
1841
1842    #[inline]
1843    #[allow(unsafe_code)]
1844    unsafe fn initialize_layout_data(self, new_data: Box<GenericLayoutData>) {
1845        let data = unsafe { self.unsafe_get().layout_data.borrow_mut_for_layout() };
1846        debug_assert!(data.is_none());
1847        *data = Some(new_data);
1848    }
1849
1850    #[inline]
1851    #[allow(unsafe_code)]
1852    unsafe fn clear_style_and_layout_data(self) {
1853        unsafe {
1854            self.unsafe_get().style_data.borrow_mut_for_layout().take();
1855            self.unsafe_get().layout_data.borrow_mut_for_layout().take();
1856        }
1857    }
1858
1859    /// Whether this element should layout as a special case input element.
1860    // TODO(#38251): With the implementation of Shadow DOM, we could implement the construction properly
1861    //               in the DOM, instead of delegating it to layout.
1862    fn is_text_input(&self) -> bool {
1863        let type_id = self.type_id_for_layout();
1864        if type_id ==
1865            NodeTypeId::Element(ElementTypeId::HTMLElement(
1866                HTMLElementTypeId::HTMLInputElement,
1867            ))
1868        {
1869            let input = self.unsafe_get().downcast::<HTMLInputElement>().unwrap();
1870
1871            !input.is_textual_widget() && input.input_type() != InputType::Color
1872        } else {
1873            type_id ==
1874                NodeTypeId::Element(ElementTypeId::HTMLElement(
1875                    HTMLElementTypeId::HTMLTextAreaElement,
1876                ))
1877        }
1878    }
1879
1880    fn is_single_line_text_inner_editor(&self) -> bool {
1881        matches!(
1882            self.unsafe_get().implemented_pseudo_element(),
1883            Some(PseudoElement::ServoTextControlInnerEditor)
1884        )
1885    }
1886
1887    fn is_text_container_of_single_line_input(&self) -> bool {
1888        let is_single_line_text_inner_placeholder = matches!(
1889            self.unsafe_get().implemented_pseudo_element(),
1890            Some(PseudoElement::Placeholder)
1891        );
1892        // Currently `::placeholder` is only implemented for single line text input element.
1893        debug_assert!(
1894            !is_single_line_text_inner_placeholder ||
1895                self.containing_shadow_root_for_layout()
1896                    .map(|root| root.get_host_for_layout())
1897                    .map(|host| host.downcast::<HTMLInputElement>())
1898                    .is_some()
1899        );
1900
1901        self.is_single_line_text_inner_editor() || is_single_line_text_inner_placeholder
1902    }
1903
1904    fn text_content(self) -> Cow<'dom, str> {
1905        if let Some(text) = self.downcast::<Text>() {
1906            return text.upcast().data_for_layout().into();
1907        }
1908
1909        if let Some(input) = self.downcast::<HTMLInputElement>() {
1910            return input.value_for_layout();
1911        }
1912
1913        if let Some(area) = self.downcast::<HTMLTextAreaElement>() {
1914            return area.value_for_layout().into();
1915        }
1916
1917        panic!("not text!")
1918    }
1919
1920    fn selection(self) -> Option<Range<usize>> {
1921        // If this is a inner editor of an UA widget element, we should find
1922        // the selection from its shadow host.
1923        // FIXME(stevennovaryo): This should account for the multiline text input,
1924        //                       but we are yet to support that input with UA widget.
1925        if self.is_in_ua_widget() &&
1926            self.is_text_node_for_layout() &&
1927            self.parent_node_ref()
1928                .is_some_and(|parent| parent.is_single_line_text_inner_editor())
1929        {
1930            let shadow_root = self.containing_shadow_root_for_layout();
1931            if let Some(containing_shadow_host) = shadow_root.map(|root| root.get_host_for_layout())
1932            {
1933                if let Some(input) = containing_shadow_host.downcast::<HTMLInputElement>() {
1934                    return input.selection_for_layout();
1935                }
1936            }
1937        }
1938
1939        if let Some(area) = self.downcast::<HTMLTextAreaElement>() {
1940            return area.selection_for_layout();
1941        }
1942
1943        if let Some(input) = self.downcast::<HTMLInputElement>() {
1944            return input.selection_for_layout();
1945        }
1946
1947        None
1948    }
1949
1950    fn image_url(self) -> Option<ServoUrl> {
1951        self.downcast::<HTMLImageElement>()
1952            .expect("not an image!")
1953            .image_url()
1954    }
1955
1956    fn image_data(self) -> Option<(Option<Image>, Option<ImageMetadata>)> {
1957        self.downcast::<HTMLImageElement>().map(|e| e.image_data())
1958    }
1959
1960    fn image_density(self) -> Option<f64> {
1961        self.downcast::<HTMLImageElement>()
1962            .expect("not an image!")
1963            .image_density()
1964    }
1965
1966    fn canvas_data(self) -> Option<HTMLCanvasData> {
1967        self.downcast::<HTMLCanvasElement>()
1968            .map(|canvas| canvas.data())
1969    }
1970
1971    fn media_data(self) -> Option<HTMLMediaData> {
1972        self.downcast::<HTMLVideoElement>()
1973            .map(|media| media.data())
1974    }
1975
1976    fn svg_data(self) -> Option<SVGElementData> {
1977        self.downcast::<SVGSVGElement>().map(|svg| svg.data())
1978    }
1979
1980    fn iframe_browsing_context_id(self) -> Option<BrowsingContextId> {
1981        self.downcast::<HTMLIFrameElement>()
1982            .and_then(|iframe_element| iframe_element.browsing_context_id())
1983    }
1984
1985    fn iframe_pipeline_id(self) -> Option<PipelineId> {
1986        self.downcast::<HTMLIFrameElement>()
1987            .and_then(|iframe_element| iframe_element.pipeline_id())
1988    }
1989
1990    #[allow(unsafe_code)]
1991    fn opaque(self) -> OpaqueNode {
1992        unsafe { OpaqueNode(self.get_jsobject() as usize) }
1993    }
1994
1995    fn implemented_pseudo_element(&self) -> Option<PseudoElement> {
1996        self.unsafe_get().implemented_pseudo_element()
1997    }
1998
1999    fn is_in_ua_widget(&self) -> bool {
2000        self.unsafe_get().is_in_ua_widget()
2001    }
2002}
2003
2004//
2005// Iteration and traversal
2006//
2007
2008pub(crate) struct FollowingNodeIterator {
2009    current: Option<DomRoot<Node>>,
2010    root: DomRoot<Node>,
2011}
2012
2013impl FollowingNodeIterator {
2014    /// Skips iterating the children of the current node
2015    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
2016        let current = self.current.take()?;
2017        self.next_skipping_children_impl(current)
2018    }
2019
2020    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
2021        if self.root == current {
2022            self.current = None;
2023            return None;
2024        }
2025
2026        if let Some(next_sibling) = current.GetNextSibling() {
2027            self.current = Some(next_sibling);
2028            return current.GetNextSibling();
2029        }
2030
2031        for ancestor in current.inclusive_ancestors(ShadowIncluding::No) {
2032            if self.root == ancestor {
2033                break;
2034            }
2035            if let Some(next_sibling) = ancestor.GetNextSibling() {
2036                self.current = Some(next_sibling);
2037                return ancestor.GetNextSibling();
2038            }
2039        }
2040        self.current = None;
2041        None
2042    }
2043}
2044
2045impl Iterator for FollowingNodeIterator {
2046    type Item = DomRoot<Node>;
2047
2048    /// <https://dom.spec.whatwg.org/#concept-tree-following>
2049    fn next(&mut self) -> Option<DomRoot<Node>> {
2050        let current = self.current.take()?;
2051
2052        if let Some(first_child) = current.GetFirstChild() {
2053            self.current = Some(first_child);
2054            return current.GetFirstChild();
2055        }
2056
2057        self.next_skipping_children_impl(current)
2058    }
2059}
2060
2061pub(crate) struct PrecedingNodeIterator {
2062    current: Option<DomRoot<Node>>,
2063    root: DomRoot<Node>,
2064}
2065
2066impl Iterator for PrecedingNodeIterator {
2067    type Item = DomRoot<Node>;
2068
2069    /// <https://dom.spec.whatwg.org/#concept-tree-preceding>
2070    fn next(&mut self) -> Option<DomRoot<Node>> {
2071        let current = self.current.take()?;
2072
2073        self.current = if self.root == current {
2074            None
2075        } else if let Some(previous_sibling) = current.GetPreviousSibling() {
2076            if self.root == previous_sibling {
2077                None
2078            } else if let Some(last_child) = previous_sibling.descending_last_children().last() {
2079                Some(last_child)
2080            } else {
2081                Some(previous_sibling)
2082            }
2083        } else {
2084            current.GetParentNode()
2085        };
2086        self.current.clone()
2087    }
2088}
2089
2090struct SimpleNodeIterator<I>
2091where
2092    I: Fn(&Node) -> Option<DomRoot<Node>>,
2093{
2094    current: Option<DomRoot<Node>>,
2095    next_node: I,
2096}
2097
2098impl<I> Iterator for SimpleNodeIterator<I>
2099where
2100    I: Fn(&Node) -> Option<DomRoot<Node>>,
2101{
2102    type Item = DomRoot<Node>;
2103
2104    fn next(&mut self) -> Option<Self::Item> {
2105        let current = self.current.take();
2106        self.current = current.as_ref().and_then(|c| (self.next_node)(c));
2107        current
2108    }
2109}
2110
2111/// Whether a tree traversal should pass shadow tree boundaries.
2112#[derive(Clone, Copy, PartialEq)]
2113pub(crate) enum ShadowIncluding {
2114    No,
2115    Yes,
2116}
2117
2118pub(crate) struct TreeIterator {
2119    current: Option<DomRoot<Node>>,
2120    depth: usize,
2121    shadow_including: bool,
2122}
2123
2124impl TreeIterator {
2125    fn new(root: &Node, shadow_including: ShadowIncluding) -> TreeIterator {
2126        TreeIterator {
2127            current: Some(DomRoot::from_ref(root)),
2128            depth: 0,
2129            shadow_including: shadow_including == ShadowIncluding::Yes,
2130        }
2131    }
2132
2133    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
2134        let current = self.current.take()?;
2135
2136        self.next_skipping_children_impl(current)
2137    }
2138
2139    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
2140        let iter = current.inclusive_ancestors(if self.shadow_including {
2141            ShadowIncluding::Yes
2142        } else {
2143            ShadowIncluding::No
2144        });
2145
2146        for ancestor in iter {
2147            if self.depth == 0 {
2148                break;
2149            }
2150            if let Some(next_sibling) = ancestor.GetNextSibling() {
2151                self.current = Some(next_sibling);
2152                return Some(current);
2153            }
2154            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
2155                // Shadow roots don't have sibling, so after we're done traversing
2156                // one we jump to the first child of the host
2157                if let Some(child) = shadow_root.Host().upcast::<Node>().GetFirstChild() {
2158                    self.current = Some(child);
2159                    return Some(current);
2160                }
2161            }
2162            self.depth -= 1;
2163        }
2164        debug_assert_eq!(self.depth, 0);
2165        self.current = None;
2166        Some(current)
2167    }
2168
2169    pub(crate) fn peek(&self) -> Option<&DomRoot<Node>> {
2170        self.current.as_ref()
2171    }
2172}
2173
2174impl Iterator for TreeIterator {
2175    type Item = DomRoot<Node>;
2176
2177    /// <https://dom.spec.whatwg.org/#concept-tree-order>
2178    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
2179    fn next(&mut self) -> Option<DomRoot<Node>> {
2180        let current = self.current.take()?;
2181
2182        // Handle a potential shadow root on the element
2183        if let Some(element) = current.downcast::<Element>() {
2184            if let Some(shadow_root) = element.shadow_root() {
2185                if self.shadow_including {
2186                    self.current = Some(DomRoot::from_ref(shadow_root.upcast::<Node>()));
2187                    self.depth += 1;
2188                    return Some(current);
2189                }
2190            }
2191        }
2192
2193        if let Some(first_child) = current.GetFirstChild() {
2194            self.current = Some(first_child);
2195            self.depth += 1;
2196            return Some(current);
2197        };
2198
2199        self.next_skipping_children_impl(current)
2200    }
2201}
2202
2203/// Specifies whether children must be recursively cloned or not.
2204#[derive(Clone, Copy, MallocSizeOf, PartialEq)]
2205pub(crate) enum CloneChildrenFlag {
2206    CloneChildren,
2207    DoNotCloneChildren,
2208}
2209
2210fn as_uintptr<T>(t: &T) -> uintptr_t {
2211    t as *const T as uintptr_t
2212}
2213
2214impl Node {
2215    pub(crate) fn reflect_node<N>(node: Box<N>, document: &Document, can_gc: CanGc) -> DomRoot<N>
2216    where
2217        N: DerivedFrom<Node> + DomObject + DomObjectWrap<crate::DomTypeHolder>,
2218    {
2219        Self::reflect_node_with_proto(node, document, None, can_gc)
2220    }
2221
2222    pub(crate) fn reflect_node_with_proto<N>(
2223        node: Box<N>,
2224        document: &Document,
2225        proto: Option<HandleObject>,
2226        can_gc: CanGc,
2227    ) -> DomRoot<N>
2228    where
2229        N: DerivedFrom<Node> + DomObject + DomObjectWrap<crate::DomTypeHolder>,
2230    {
2231        let window = document.window();
2232        reflect_dom_object_with_proto(node, window, proto, can_gc)
2233    }
2234
2235    pub(crate) fn new_inherited(doc: &Document) -> Node {
2236        Node::new_(NodeFlags::empty(), Some(doc))
2237    }
2238
2239    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
2240    pub(crate) fn new_document_node() -> Node {
2241        Node::new_(
2242            NodeFlags::IS_IN_A_DOCUMENT_TREE | NodeFlags::IS_CONNECTED,
2243            None,
2244        )
2245    }
2246
2247    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
2248    fn new_(flags: NodeFlags, doc: Option<&Document>) -> Node {
2249        Node {
2250            eventtarget: EventTarget::new_inherited(),
2251
2252            parent_node: Default::default(),
2253            first_child: Default::default(),
2254            last_child: Default::default(),
2255            next_sibling: Default::default(),
2256            prev_sibling: Default::default(),
2257            owner_doc: MutNullableDom::new(doc),
2258            rare_data: Default::default(),
2259            children_count: Cell::new(0u32),
2260            flags: Cell::new(flags),
2261            inclusive_descendants_version: Cell::new(0),
2262            style_data: Default::default(),
2263            layout_data: Default::default(),
2264        }
2265    }
2266
2267    /// <https://dom.spec.whatwg.org/#concept-node-adopt>
2268    pub(crate) fn adopt(node: &Node, document: &Document, can_gc: CanGc) {
2269        document.add_script_and_layout_blocker();
2270
2271        // Step 1. Let oldDocument be node’s node document.
2272        let old_doc = node.owner_doc();
2273        old_doc.add_script_and_layout_blocker();
2274
2275        // Step 2. If node’s parent is non-null, then remove node.
2276        node.remove_self(can_gc);
2277
2278        // Step 3. If document is not oldDocument:
2279        if &*old_doc != document {
2280            // Step 3.1. For each inclusiveDescendant in node’s shadow-including inclusive descendants:
2281            for descendant in node.traverse_preorder(ShadowIncluding::Yes) {
2282                // Step 3.1.1 Set inclusiveDescendant’s node document to document.
2283                descendant.set_owner_doc(document);
2284
2285                // Step 3.1.2 If inclusiveDescendant is an element, then set the node document of each
2286                // attribute in inclusiveDescendant’s attribute list to document.
2287                if let Some(element) = descendant.downcast::<Element>() {
2288                    for attribute in element.attrs().iter() {
2289                        attribute.upcast::<Node>().set_owner_doc(document);
2290                    }
2291                }
2292            }
2293
2294            // Step 3.2 For each inclusiveDescendant in node’s shadow-including inclusive descendants
2295            // that is custom, enqueue a custom element callback reaction with inclusiveDescendant,
2296            // callback name "adoptedCallback", and « oldDocument, document ».
2297            let custom_element_reaction_stack = ScriptThread::custom_element_reaction_stack();
2298            for descendant in node
2299                .traverse_preorder(ShadowIncluding::Yes)
2300                .filter_map(|d| d.as_custom_element())
2301            {
2302                custom_element_reaction_stack.enqueue_callback_reaction(
2303                    &descendant,
2304                    CallbackReaction::Adopted(old_doc.clone(), DomRoot::from_ref(document)),
2305                    None,
2306                );
2307            }
2308
2309            // Step 3.3 For each inclusiveDescendant in node’s shadow-including inclusive descendants,
2310            // in shadow-including tree order, run the adopting steps with inclusiveDescendant and oldDocument.
2311            for descendant in node.traverse_preorder(ShadowIncluding::Yes) {
2312                vtable_for(&descendant).adopting_steps(&old_doc, can_gc);
2313            }
2314        }
2315
2316        old_doc.remove_script_and_layout_blocker();
2317        document.remove_script_and_layout_blocker();
2318    }
2319
2320    /// <https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity>
2321    pub(crate) fn ensure_pre_insertion_validity(
2322        node: &Node,
2323        parent: &Node,
2324        child: Option<&Node>,
2325    ) -> ErrorResult {
2326        // Step 1.
2327        match parent.type_id() {
2328            NodeTypeId::Document(_) | NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..) => {
2329            },
2330            _ => return Err(Error::HierarchyRequest),
2331        }
2332
2333        // Step 2.
2334        if node.is_inclusive_ancestor_of(parent) {
2335            return Err(Error::HierarchyRequest);
2336        }
2337
2338        // Step 3.
2339        if let Some(child) = child {
2340            if !parent.is_parent_of(child) {
2341                return Err(Error::NotFound);
2342            }
2343        }
2344
2345        // Step 4-5.
2346        match node.type_id() {
2347            NodeTypeId::CharacterData(CharacterDataTypeId::Text(_)) => {
2348                if parent.is::<Document>() {
2349                    return Err(Error::HierarchyRequest);
2350                }
2351            },
2352            NodeTypeId::DocumentType => {
2353                if !parent.is::<Document>() {
2354                    return Err(Error::HierarchyRequest);
2355                }
2356            },
2357            NodeTypeId::DocumentFragment(_) |
2358            NodeTypeId::Element(_) |
2359            NodeTypeId::CharacterData(CharacterDataTypeId::ProcessingInstruction) |
2360            NodeTypeId::CharacterData(CharacterDataTypeId::Comment) => (),
2361            NodeTypeId::Document(_) | NodeTypeId::Attr => return Err(Error::HierarchyRequest),
2362        }
2363
2364        // Step 6.
2365        if parent.is::<Document>() {
2366            match node.type_id() {
2367                // Step 6.1
2368                NodeTypeId::DocumentFragment(_) => {
2369                    // Step 6.1.1(b)
2370                    if node.children().any(|c| c.is::<Text>()) {
2371                        return Err(Error::HierarchyRequest);
2372                    }
2373                    match node.child_elements().count() {
2374                        0 => (),
2375                        // Step 6.1.2
2376                        1 => {
2377                            if parent.child_elements().next().is_some() {
2378                                return Err(Error::HierarchyRequest);
2379                            }
2380                            if let Some(child) = child {
2381                                if child
2382                                    .inclusively_following_siblings()
2383                                    .any(|child| child.is_doctype())
2384                                {
2385                                    return Err(Error::HierarchyRequest);
2386                                }
2387                            }
2388                        },
2389                        // Step 6.1.1(a)
2390                        _ => return Err(Error::HierarchyRequest),
2391                    }
2392                },
2393                // Step 6.2
2394                NodeTypeId::Element(_) => {
2395                    if parent.child_elements().next().is_some() {
2396                        return Err(Error::HierarchyRequest);
2397                    }
2398                    if let Some(child) = child {
2399                        if child
2400                            .inclusively_following_siblings()
2401                            .any(|child| child.is_doctype())
2402                        {
2403                            return Err(Error::HierarchyRequest);
2404                        }
2405                    }
2406                },
2407                // Step 6.3
2408                NodeTypeId::DocumentType => {
2409                    if parent.children().any(|c| c.is_doctype()) {
2410                        return Err(Error::HierarchyRequest);
2411                    }
2412                    match child {
2413                        Some(child) => {
2414                            if parent
2415                                .children()
2416                                .take_while(|c| &**c != child)
2417                                .any(|c| c.is::<Element>())
2418                            {
2419                                return Err(Error::HierarchyRequest);
2420                            }
2421                        },
2422                        None => {
2423                            if parent.child_elements().next().is_some() {
2424                                return Err(Error::HierarchyRequest);
2425                            }
2426                        },
2427                    }
2428                },
2429                NodeTypeId::CharacterData(_) => (),
2430                // Because Document and Attr should already throw `HierarchyRequest`
2431                // error, both of them are unreachable here.
2432                NodeTypeId::Document(_) | NodeTypeId::Attr => unreachable!(),
2433            }
2434        }
2435        Ok(())
2436    }
2437
2438    /// <https://dom.spec.whatwg.org/#concept-node-pre-insert>
2439    pub(crate) fn pre_insert(
2440        node: &Node,
2441        parent: &Node,
2442        child: Option<&Node>,
2443        can_gc: CanGc,
2444    ) -> Fallible<DomRoot<Node>> {
2445        // Step 1.
2446        Node::ensure_pre_insertion_validity(node, parent, child)?;
2447
2448        // Steps 2-3.
2449        let reference_child_root;
2450        let reference_child = match child {
2451            Some(child) if child == node => {
2452                reference_child_root = node.GetNextSibling();
2453                reference_child_root.as_deref()
2454            },
2455            _ => child,
2456        };
2457
2458        // Step 4.
2459        Node::insert(
2460            node,
2461            parent,
2462            reference_child,
2463            SuppressObserver::Unsuppressed,
2464            can_gc,
2465        );
2466
2467        // Step 5.
2468        Ok(DomRoot::from_ref(node))
2469    }
2470
2471    /// <https://dom.spec.whatwg.org/#concept-node-insert>
2472    fn insert(
2473        node: &Node,
2474        parent: &Node,
2475        child: Option<&Node>,
2476        suppress_observers: SuppressObserver,
2477        can_gc: CanGc,
2478    ) {
2479        debug_assert!(child.is_none_or(|child| Some(parent) == child.GetParentNode().as_deref()));
2480
2481        // Step 1. Let nodes be node’s children, if node is a DocumentFragment node; otherwise « node ».
2482        rooted_vec!(let mut new_nodes);
2483        let new_nodes = if let NodeTypeId::DocumentFragment(_) = node.type_id() {
2484            new_nodes.extend(node.children().map(|node| Dom::from_ref(&*node)));
2485            new_nodes.r()
2486        } else {
2487            from_ref(&node)
2488        };
2489
2490        // Step 2. Let count be nodes’s size.
2491        let count = new_nodes.len();
2492
2493        // Step 3. If count is 0, then return.
2494        if count == 0 {
2495            return;
2496        }
2497
2498        // Script and layout blockers must be added after any early return.
2499        // `node.owner_doc()` may change during the algorithm.
2500        let parent_document = parent.owner_doc();
2501        let from_document = node.owner_doc();
2502        from_document.add_script_and_layout_blocker();
2503        parent_document.add_script_and_layout_blocker();
2504
2505        // Step 4. If node is a DocumentFragment node:
2506        if let NodeTypeId::DocumentFragment(_) = node.type_id() {
2507            // Step 4.1. Remove its children with the suppress observers flag set.
2508            for kid in new_nodes {
2509                Node::remove(kid, node, SuppressObserver::Suppressed, can_gc);
2510            }
2511            vtable_for(node).children_changed(&ChildrenMutation::replace_all(new_nodes, &[]));
2512
2513            // Step 4.2. Queue a tree mutation record for node with « », nodes, null, and null.
2514            let mutation = LazyCell::new(|| Mutation::ChildList {
2515                added: None,
2516                removed: Some(new_nodes),
2517                prev: None,
2518                next: None,
2519            });
2520            MutationObserver::queue_a_mutation_record(node, mutation);
2521        }
2522
2523        // Step 5. If child is non-null:
2524        //     1. For each live range whose start node is parent and start offset is
2525        //        greater than child’s index, increase its start offset by count.
2526        //     2. For each live range whose end node is parent and end offset is
2527        //        greater than child’s index, increase its end offset by count.
2528        if let Some(child) = child {
2529            if !parent.ranges_is_empty() {
2530                parent
2531                    .ranges()
2532                    .increase_above(parent, child.index(), count.try_into().unwrap());
2533            }
2534        }
2535
2536        // Step 6. Let previousSibling be child’s previous sibling or parent’s last child if child is null.
2537        let previous_sibling = match suppress_observers {
2538            SuppressObserver::Unsuppressed => match child {
2539                Some(child) => child.GetPreviousSibling(),
2540                None => parent.GetLastChild(),
2541            },
2542            SuppressObserver::Suppressed => None,
2543        };
2544
2545        let custom_element_reaction_stack = ScriptThread::custom_element_reaction_stack();
2546        // Step 7. For each node in nodes, in tree order:
2547        for kid in new_nodes {
2548            // Step 7.1. Adopt node into parent’s node document.
2549            Node::adopt(kid, &parent.owner_document(), can_gc);
2550
2551            // Step 7.2. If child is null, then append node to parent’s children.
2552            // Step 7.3. Otherwise, insert node into parent’s children before child’s index.
2553            parent.add_child(kid, child, can_gc);
2554
2555            // Step 7.4 If parent is a shadow host whose shadow root’s slot assignment is "named"
2556            // and node is a slottable, then assign a slot for node.
2557            if let Some(shadow_root) = parent.downcast::<Element>().and_then(Element::shadow_root) {
2558                if shadow_root.SlotAssignment() == SlotAssignmentMode::Named {
2559                    let cx = GlobalScope::get_cx();
2560                    if node.is::<Element>() || node.is::<Text>() {
2561                        rooted!(in(*cx) let slottable = Slottable(Dom::from_ref(node)));
2562                        slottable.assign_a_slot();
2563                    }
2564                }
2565            }
2566
2567            // Step 7.5 If parent’s root is a shadow root, and parent is a slot whose assigned nodes
2568            // is the empty list, then run signal a slot change for parent.
2569            if parent.is_in_a_shadow_tree() {
2570                if let Some(slot_element) = parent.downcast::<HTMLSlotElement>() {
2571                    if !slot_element.has_assigned_nodes() {
2572                        slot_element.signal_a_slot_change();
2573                    }
2574                }
2575            }
2576
2577            // Step 7.6 Run assign slottables for a tree with node’s root.
2578            kid.GetRootNode(&GetRootNodeOptions::empty())
2579                .assign_slottables_for_a_tree();
2580
2581            // Step 7.7. For each shadow-including inclusive descendant inclusiveDescendant of node,
2582            // in shadow-including tree order:
2583            for descendant in kid
2584                .traverse_preorder(ShadowIncluding::Yes)
2585                .filter_map(DomRoot::downcast::<Element>)
2586            {
2587                // Step 7.7.1. Run the insertion steps with inclusiveDescendant.
2588                // This is done in `parent.add_child()`.
2589
2590                // Step 7.7.2, whatwg/dom#833
2591                // Enqueue connected reactions for custom elements or try upgrade.
2592                if descendant.is_custom() {
2593                    if descendant.is_connected() {
2594                        custom_element_reaction_stack.enqueue_callback_reaction(
2595                            &descendant,
2596                            CallbackReaction::Connected,
2597                            None,
2598                        );
2599                    }
2600                } else {
2601                    try_upgrade_element(&descendant);
2602                }
2603            }
2604        }
2605
2606        if let SuppressObserver::Unsuppressed = suppress_observers {
2607            // Step 9. Run the children changed steps for parent.
2608            // TODO(xiaochengh): If we follow the spec and move it out of the if block, some WPT fail. Investigate.
2609            vtable_for(parent).children_changed(&ChildrenMutation::insert(
2610                previous_sibling.as_deref(),
2611                new_nodes,
2612                child,
2613            ));
2614
2615            // Step 8. If suppress observers flag is unset, then queue a tree mutation record for parent
2616            // with nodes, « », previousSibling, and child.
2617            let mutation = LazyCell::new(|| Mutation::ChildList {
2618                added: Some(new_nodes),
2619                removed: None,
2620                prev: previous_sibling.as_deref(),
2621                next: child,
2622            });
2623            MutationObserver::queue_a_mutation_record(parent, mutation);
2624        }
2625
2626        // Step 10. Let staticNodeList be a list of nodes, initially « ».
2627        let mut static_node_list = vec![];
2628
2629        // Step 11. For each node of nodes, in tree order:
2630        for node in new_nodes {
2631            // Step 11.1 For each shadow-including inclusive descendant inclusiveDescendant of node,
2632            //           in shadow-including tree order, append inclusiveDescendant to staticNodeList.
2633            static_node_list.extend(node.traverse_preorder(ShadowIncluding::Yes));
2634        }
2635
2636        // We use a delayed task for this step to work around an awkward interaction between
2637        // script/layout blockers, Node::replace_all, and the children_changed vtable method.
2638        // Any node with a post connection step that triggers layout (such as iframes) needs
2639        // to be marked as dirty before doing so. This is handled by Node's children_changed
2640        // callback, but when Node::insert is called as part of Node::replace_all then the
2641        // callback is suppressed until we return to Node::replace_all. To ensure the sequence:
2642        // 1) children_changed in Node::replace_all,
2643        // 2) post_connection_steps from Node::insert,
2644        // we use a delayed task that will run as soon as Node::insert removes its
2645        // script/layout blocker.
2646        parent_document.add_delayed_task(
2647            task!(PostConnectionSteps: |static_node_list: Vec<DomRoot<Node>>| {
2648                // Step 12. For each node of staticNodeList, if node is connected, then run the
2649                //          post-connection steps with node.
2650                for node in static_node_list.iter().filter(|n| n.is_connected()) {
2651                    vtable_for(node).post_connection_steps();
2652                }
2653            }),
2654        );
2655
2656        parent_document.remove_script_and_layout_blocker();
2657        from_document.remove_script_and_layout_blocker();
2658    }
2659
2660    /// <https://dom.spec.whatwg.org/#concept-node-replace-all>
2661    pub(crate) fn replace_all(node: Option<&Node>, parent: &Node, can_gc: CanGc) {
2662        parent.owner_doc().add_script_and_layout_blocker();
2663        // Step 1.
2664        if let Some(node) = node {
2665            Node::adopt(node, &parent.owner_doc(), can_gc);
2666        }
2667        // Step 2.
2668        rooted_vec!(let removed_nodes <- parent.children().map(|c| DomRoot::as_traced(&c)));
2669        // Step 3.
2670        rooted_vec!(let mut added_nodes);
2671        let added_nodes = if let Some(node) = node.as_ref() {
2672            if let NodeTypeId::DocumentFragment(_) = node.type_id() {
2673                added_nodes.extend(node.children().map(|child| Dom::from_ref(&*child)));
2674                added_nodes.r()
2675            } else {
2676                from_ref(node)
2677            }
2678        } else {
2679            &[] as &[&Node]
2680        };
2681        // Step 4.
2682        for child in &*removed_nodes {
2683            Node::remove(child, parent, SuppressObserver::Suppressed, can_gc);
2684        }
2685        // Step 5.
2686        if let Some(node) = node {
2687            Node::insert(node, parent, None, SuppressObserver::Suppressed, can_gc);
2688        }
2689        // Step 6.
2690        vtable_for(parent).children_changed(&ChildrenMutation::replace_all(
2691            removed_nodes.r(),
2692            added_nodes,
2693        ));
2694
2695        if !removed_nodes.is_empty() || !added_nodes.is_empty() {
2696            let mutation = LazyCell::new(|| Mutation::ChildList {
2697                added: Some(added_nodes),
2698                removed: Some(removed_nodes.r()),
2699                prev: None,
2700                next: None,
2701            });
2702            MutationObserver::queue_a_mutation_record(parent, mutation);
2703        }
2704        parent.owner_doc().remove_script_and_layout_blocker();
2705    }
2706
2707    /// <https://dom.spec.whatwg.org/multipage/#string-replace-all>
2708    pub(crate) fn string_replace_all(string: DOMString, parent: &Node, can_gc: CanGc) {
2709        if string.is_empty() {
2710            Node::replace_all(None, parent, can_gc);
2711        } else {
2712            let text = Text::new(string, &parent.owner_document(), can_gc);
2713            Node::replace_all(Some(text.upcast::<Node>()), parent, can_gc);
2714        };
2715    }
2716
2717    /// <https://dom.spec.whatwg.org/#concept-node-pre-remove>
2718    fn pre_remove(child: &Node, parent: &Node, can_gc: CanGc) -> Fallible<DomRoot<Node>> {
2719        // Step 1.
2720        match child.GetParentNode() {
2721            Some(ref node) if &**node != parent => return Err(Error::NotFound),
2722            None => return Err(Error::NotFound),
2723            _ => (),
2724        }
2725
2726        // Step 2.
2727        Node::remove(child, parent, SuppressObserver::Unsuppressed, can_gc);
2728
2729        // Step 3.
2730        Ok(DomRoot::from_ref(child))
2731    }
2732
2733    /// <https://dom.spec.whatwg.org/#concept-node-remove>
2734    fn remove(node: &Node, parent: &Node, suppress_observers: SuppressObserver, can_gc: CanGc) {
2735        parent.owner_doc().add_script_and_layout_blocker();
2736
2737        // Step 1. Let parent be node’s parent.
2738        // Step 2. Assert: parent is non-null.
2739        // NOTE: We get parent as an argument instead
2740        assert!(
2741            node.GetParentNode()
2742                .is_some_and(|node_parent| &*node_parent == parent)
2743        );
2744
2745        // Step 3. Run the live range pre-remove steps.
2746        // https://dom.spec.whatwg.org/#live-range-pre-remove-steps
2747        let cached_index = {
2748            if parent.ranges_is_empty() {
2749                None
2750            } else {
2751                // Step 1. Let parent be node’s parent.
2752                // Step 2. Assert: parent is not null.
2753                // NOTE: We already have the parent.
2754
2755                // Step 3. Let index be node’s index.
2756                let index = node.index();
2757
2758                // Steps 4-5 are handled in Node::unbind_from_tree.
2759
2760                // Step 6. For each live range whose start node is parent and start offset is greater than index,
2761                // decrease its start offset by 1.
2762                // Step 7. For each live range whose end node is parent and end offset is greater than index,
2763                // decrease its end offset by 1.
2764                parent.ranges().decrease_above(parent, index, 1);
2765
2766                // Parent had ranges, we needed the index, let's keep track of
2767                // it to avoid computing it for other ranges when calling
2768                // unbind_from_tree recursively.
2769                Some(index)
2770            }
2771        };
2772
2773        // TODO: Step 4. Pre-removing steps for node iterators
2774
2775        // Step 5.
2776        let old_previous_sibling = node.GetPreviousSibling();
2777
2778        // Step 6.
2779        let old_next_sibling = node.GetNextSibling();
2780
2781        // Step 7. Remove node from its parent's children.
2782        // Step 11-14. Run removing steps and enqueue disconnected custom element reactions for the subtree.
2783        parent.remove_child(node, cached_index, can_gc);
2784
2785        // Step 8. If node is assigned, then run assign slottables for node’s assigned slot.
2786        if let Some(slot) = node.assigned_slot() {
2787            slot.assign_slottables();
2788        }
2789
2790        // Step 9. If parent’s root is a shadow root, and parent is a slot whose assigned nodes is the empty list,
2791        // then run signal a slot change for parent.
2792        if parent.is_in_a_shadow_tree() {
2793            if let Some(slot_element) = parent.downcast::<HTMLSlotElement>() {
2794                if !slot_element.has_assigned_nodes() {
2795                    slot_element.signal_a_slot_change();
2796                }
2797            }
2798        }
2799
2800        // Step 10. If node has an inclusive descendant that is a slot:
2801        let has_slot_descendant = node
2802            .traverse_preorder(ShadowIncluding::No)
2803            .any(|elem| elem.is::<HTMLSlotElement>());
2804        if has_slot_descendant {
2805            // Step 10.1 Run assign slottables for a tree with parent’s root.
2806            parent
2807                .GetRootNode(&GetRootNodeOptions::empty())
2808                .assign_slottables_for_a_tree();
2809
2810            // Step 10.2 Run assign slottables for a tree with node.
2811            node.assign_slottables_for_a_tree();
2812        }
2813
2814        // TODO: Step 15. transient registered observers
2815
2816        // Step 16.
2817        if let SuppressObserver::Unsuppressed = suppress_observers {
2818            vtable_for(parent).children_changed(&ChildrenMutation::replace(
2819                old_previous_sibling.as_deref(),
2820                &Some(node),
2821                &[],
2822                old_next_sibling.as_deref(),
2823            ));
2824
2825            let removed = [node];
2826            let mutation = LazyCell::new(|| Mutation::ChildList {
2827                added: None,
2828                removed: Some(&removed),
2829                prev: old_previous_sibling.as_deref(),
2830                next: old_next_sibling.as_deref(),
2831            });
2832            MutationObserver::queue_a_mutation_record(parent, mutation);
2833        }
2834        parent.owner_doc().remove_script_and_layout_blocker();
2835    }
2836
2837    /// Ensure that for styles, we clone the already-parsed property declaration block.
2838    /// This does two things:
2839    /// 1. it uses the same fast-path as CSSStyleDeclaration
2840    /// 2. it also avoids the CSP checks when cloning (it shouldn't run any when cloning
2841    ///    existing valid attributes)
2842    fn compute_attribute_value_with_style_fast_path(attr: &Dom<Attr>, elem: &Element) -> AttrValue {
2843        if *attr.local_name() == local_name!("style") {
2844            if let Some(ref pdb) = *elem.style_attribute().borrow() {
2845                let document = elem.owner_document();
2846                let shared_lock = document.style_shared_lock();
2847                let new_pdb = pdb.read_with(&shared_lock.read()).clone();
2848                return AttrValue::Declaration(
2849                    (**attr.value()).to_owned(),
2850                    Arc::new(shared_lock.wrap(new_pdb)),
2851                );
2852            }
2853        }
2854
2855        attr.value().clone()
2856    }
2857
2858    /// <https://dom.spec.whatwg.org/#concept-node-clone>
2859    pub(crate) fn clone(
2860        node: &Node,
2861        maybe_doc: Option<&Document>,
2862        clone_children: CloneChildrenFlag,
2863        can_gc: CanGc,
2864    ) -> DomRoot<Node> {
2865        // Step 1. If document is not given, let document be node’s node document.
2866        let document = match maybe_doc {
2867            Some(doc) => DomRoot::from_ref(doc),
2868            None => node.owner_doc(),
2869        };
2870
2871        // Step 2. / Step 3.
2872        // XXXabinader: clone() for each node as trait?
2873        let copy: DomRoot<Node> = match node.type_id() {
2874            NodeTypeId::DocumentType => {
2875                let doctype = node.downcast::<DocumentType>().unwrap();
2876                let doctype = DocumentType::new(
2877                    doctype.name().clone(),
2878                    Some(doctype.public_id().clone()),
2879                    Some(doctype.system_id().clone()),
2880                    &document,
2881                    can_gc,
2882                );
2883                DomRoot::upcast::<Node>(doctype)
2884            },
2885            NodeTypeId::Attr => {
2886                let attr = node.downcast::<Attr>().unwrap();
2887                let attr = Attr::new(
2888                    &document,
2889                    attr.local_name().clone(),
2890                    attr.value().clone(),
2891                    attr.name().clone(),
2892                    attr.namespace().clone(),
2893                    attr.prefix().cloned(),
2894                    None,
2895                    can_gc,
2896                );
2897                DomRoot::upcast::<Node>(attr)
2898            },
2899            NodeTypeId::DocumentFragment(_) => {
2900                let doc_fragment = DocumentFragment::new(&document, can_gc);
2901                DomRoot::upcast::<Node>(doc_fragment)
2902            },
2903            NodeTypeId::CharacterData(_) => {
2904                let cdata = node.downcast::<CharacterData>().unwrap();
2905                cdata.clone_with_data(cdata.Data(), &document, can_gc)
2906            },
2907            NodeTypeId::Document(_) => {
2908                let document = node.downcast::<Document>().unwrap();
2909                let is_html_doc = if document.is_html_document() {
2910                    IsHTMLDocument::HTMLDocument
2911                } else {
2912                    IsHTMLDocument::NonHTMLDocument
2913                };
2914                let window = document.window();
2915                let loader = DocumentLoader::new(&document.loader());
2916                let document = Document::new(
2917                    window,
2918                    HasBrowsingContext::No,
2919                    Some(document.url()),
2920                    // https://github.com/whatwg/dom/issues/378
2921                    document.origin().clone(),
2922                    is_html_doc,
2923                    None,
2924                    None,
2925                    DocumentActivity::Inactive,
2926                    DocumentSource::NotFromParser,
2927                    loader,
2928                    None,
2929                    document.status_code(),
2930                    Default::default(),
2931                    false,
2932                    document.allow_declarative_shadow_roots(),
2933                    Some(document.insecure_requests_policy()),
2934                    document.has_trustworthy_ancestor_or_current_origin(),
2935                    document.custom_element_reaction_stack(),
2936                    can_gc,
2937                );
2938                DomRoot::upcast::<Node>(document)
2939            },
2940            NodeTypeId::Element(..) => {
2941                let element = node.downcast::<Element>().unwrap();
2942                let name = QualName {
2943                    prefix: element.prefix().as_ref().map(|p| Prefix::from(&**p)),
2944                    ns: element.namespace().clone(),
2945                    local: element.local_name().clone(),
2946                };
2947                let element = Element::create(
2948                    name,
2949                    element.get_is(),
2950                    &document,
2951                    ElementCreator::ScriptCreated,
2952                    CustomElementCreationMode::Asynchronous,
2953                    None,
2954                    can_gc,
2955                );
2956                DomRoot::upcast::<Node>(element)
2957            },
2958        };
2959
2960        // Step 4. Set copy’s node document and document to copy, if copy is a document,
2961        // and set copy’s node document to document otherwise.
2962        let document = match copy.downcast::<Document>() {
2963            Some(doc) => DomRoot::from_ref(doc),
2964            None => DomRoot::from_ref(&*document),
2965        };
2966        assert!(copy.owner_doc() == document);
2967
2968        // TODO: The spec tells us to do this in step 3.
2969        match node.type_id() {
2970            NodeTypeId::Document(_) => {
2971                let node_doc = node.downcast::<Document>().unwrap();
2972                let copy_doc = copy.downcast::<Document>().unwrap();
2973                copy_doc.set_encoding(node_doc.encoding());
2974                copy_doc.set_quirks_mode(node_doc.quirks_mode());
2975            },
2976            NodeTypeId::Element(..) => {
2977                let node_elem = node.downcast::<Element>().unwrap();
2978                let copy_elem = copy.downcast::<Element>().unwrap();
2979
2980                for attr in node_elem.attrs().iter() {
2981                    let new_value =
2982                        Node::compute_attribute_value_with_style_fast_path(attr, node_elem);
2983                    copy_elem.push_new_attribute(
2984                        attr.local_name().clone(),
2985                        new_value,
2986                        attr.name().clone(),
2987                        attr.namespace().clone(),
2988                        attr.prefix().cloned(),
2989                        can_gc,
2990                    );
2991                }
2992            },
2993            _ => (),
2994        }
2995
2996        // Step 5: Run any cloning steps defined for node in other applicable specifications and pass copy,
2997        // node, document, and the clone children flag if set, as parameters.
2998        vtable_for(node).cloning_steps(&copy, maybe_doc, clone_children, can_gc);
2999
3000        // Step 6. If the clone children flag is set, then for each child child of node, in tree order: append the
3001        // result of cloning child with document and the clone children flag set, to copy.
3002        if clone_children == CloneChildrenFlag::CloneChildren {
3003            for child in node.children() {
3004                let child_copy = Node::clone(&child, Some(&document), clone_children, can_gc);
3005                let _inserted_node = Node::pre_insert(&child_copy, &copy, None, can_gc);
3006            }
3007        }
3008
3009        // Step 7. If node is a shadow host whose shadow root’s clonable is true:
3010        // NOTE: Only elements can be shadow hosts
3011        if matches!(node.type_id(), NodeTypeId::Element(_)) {
3012            let node_elem = node.downcast::<Element>().unwrap();
3013            let copy_elem = copy.downcast::<Element>().unwrap();
3014
3015            if let Some(shadow_root) = node_elem.shadow_root().filter(|r| r.Clonable()) {
3016                // Step 7.1 Assert: copy is not a shadow host.
3017                assert!(!copy_elem.is_shadow_host());
3018
3019                // Step 7.2 Run attach a shadow root with copy, node’s shadow root’s mode, true,
3020                // node’s shadow root’s serializable, node’s shadow root’s delegates focus,
3021                // and node’s shadow root’s slot assignment.
3022                let copy_shadow_root =
3023                    copy_elem.attach_shadow(
3024                        IsUserAgentWidget::No,
3025                        shadow_root.Mode(),
3026                        shadow_root.Clonable(),
3027                        shadow_root.Serializable(),
3028                        shadow_root.DelegatesFocus(),
3029                        shadow_root.SlotAssignment(),
3030                        can_gc
3031                    )
3032                    .expect("placement of attached shadow root must be valid, as this is a copy of an existing one");
3033
3034                // Step 7.3 Set copy’s shadow root’s declarative to node’s shadow root’s declarative.
3035                copy_shadow_root.set_declarative(shadow_root.is_declarative());
3036
3037                // Step 7.4 For each child child of node’s shadow root, in tree order: append the result of
3038                // cloning child with document and the clone children flag set, to copy’s shadow root.
3039                for child in shadow_root.upcast::<Node>().children() {
3040                    let child_copy = Node::clone(
3041                        &child,
3042                        Some(&document),
3043                        CloneChildrenFlag::CloneChildren,
3044                        can_gc,
3045                    );
3046
3047                    // TODO: Should we handle the error case here and in step 6?
3048                    let _inserted_node = Node::pre_insert(
3049                        &child_copy,
3050                        copy_shadow_root.upcast::<Node>(),
3051                        None,
3052                        can_gc,
3053                    );
3054                }
3055            }
3056        }
3057
3058        // Step 8. Return copy.
3059        copy
3060    }
3061
3062    /// <https://html.spec.whatwg.org/multipage/#child-text-content>
3063    pub(crate) fn child_text_content(&self) -> DOMString {
3064        Node::collect_text_contents(self.children())
3065    }
3066
3067    /// <https://html.spec.whatwg.org/multipage/#descendant-text-content>
3068    pub(crate) fn descendant_text_content(&self) -> DOMString {
3069        Node::collect_text_contents(self.traverse_preorder(ShadowIncluding::No))
3070    }
3071
3072    pub(crate) fn collect_text_contents<T: Iterator<Item = DomRoot<Node>>>(
3073        iterator: T,
3074    ) -> DOMString {
3075        let mut content = String::new();
3076        for node in iterator {
3077            if let Some(text) = node.downcast::<Text>() {
3078                content.push_str(&text.upcast::<CharacterData>().data());
3079            }
3080        }
3081        DOMString::from(content)
3082    }
3083
3084    /// <https://dom.spec.whatwg.org/#string-replace-all>
3085    pub(crate) fn set_text_content_for_element(&self, value: Option<DOMString>, can_gc: CanGc) {
3086        // This should only be called for elements and document fragments when setting the
3087        // text content: https://dom.spec.whatwg.org/#set-text-content
3088        assert!(matches!(
3089            self.type_id(),
3090            NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..)
3091        ));
3092        let value = value.unwrap_or_default();
3093        let node = if value.is_empty() {
3094            // Step 1. Let node be null.
3095            None
3096        } else {
3097            // Step 2. If string is not the empty string, then set node to
3098            // a new Text node whose data is string and node document is parent’s node document.
3099            Some(DomRoot::upcast(
3100                self.owner_doc().CreateTextNode(value, can_gc),
3101            ))
3102        };
3103
3104        // Step 3. Replace all with node within parent.
3105        Self::replace_all(node.as_deref(), self, can_gc);
3106    }
3107
3108    pub(crate) fn namespace_to_string(namespace: Namespace) -> Option<DOMString> {
3109        match namespace {
3110            ns!() => None,
3111            // FIXME(ajeffrey): convert directly from Namespace to DOMString
3112            _ => Some(DOMString::from(&*namespace)),
3113        }
3114    }
3115
3116    /// <https://dom.spec.whatwg.org/#locate-a-namespace>
3117    pub(crate) fn locate_namespace(node: &Node, prefix: Option<DOMString>) -> Namespace {
3118        match node.type_id() {
3119            NodeTypeId::Element(_) => node.downcast::<Element>().unwrap().locate_namespace(prefix),
3120            NodeTypeId::Attr => node
3121                .downcast::<Attr>()
3122                .unwrap()
3123                .GetOwnerElement()
3124                .as_ref()
3125                .map_or(ns!(), |elem| elem.locate_namespace(prefix)),
3126            NodeTypeId::Document(_) => node
3127                .downcast::<Document>()
3128                .unwrap()
3129                .GetDocumentElement()
3130                .as_ref()
3131                .map_or(ns!(), |elem| elem.locate_namespace(prefix)),
3132            NodeTypeId::DocumentType | NodeTypeId::DocumentFragment(_) => ns!(),
3133            _ => node
3134                .GetParentElement()
3135                .as_ref()
3136                .map_or(ns!(), |elem| elem.locate_namespace(prefix)),
3137        }
3138    }
3139
3140    /// If the given untrusted node address represents a valid DOM node in the given runtime,
3141    /// returns it.
3142    ///
3143    /// # Safety
3144    ///
3145    /// Callers should ensure they pass an UntrustedNodeAddress that points to a valid [`JSObject`]
3146    /// in memory that represents a [`Node`].
3147    #[allow(unsafe_code)]
3148    pub(crate) unsafe fn from_untrusted_node_address(
3149        candidate: UntrustedNodeAddress,
3150    ) -> &'static Self {
3151        // https://github.com/servo/servo/issues/6383
3152        let candidate = candidate.0 as usize;
3153        let object = candidate as *mut JSObject;
3154        if object.is_null() {
3155            panic!("Attempted to create a `Node` from an invalid pointer!")
3156        }
3157
3158        unsafe { &*(conversions::private_from_object(object) as *const Self) }
3159    }
3160
3161    pub(crate) fn html_serialize(
3162        &self,
3163        traversal_scope: html_serialize::TraversalScope,
3164        serialize_shadow_roots: bool,
3165        shadow_roots: Vec<DomRoot<ShadowRoot>>,
3166        can_gc: CanGc,
3167    ) -> DOMString {
3168        let mut writer = vec![];
3169        let mut serializer = HtmlSerializer::new(
3170            &mut writer,
3171            html_serialize::SerializeOpts {
3172                traversal_scope: traversal_scope.clone(),
3173                ..Default::default()
3174            },
3175        );
3176
3177        serialize_html_fragment(
3178            self,
3179            &mut serializer,
3180            traversal_scope,
3181            serialize_shadow_roots,
3182            shadow_roots,
3183            can_gc,
3184        )
3185        .expect("Serializing node failed");
3186
3187        // FIXME(ajeffrey): Directly convert UTF8 to DOMString
3188        DOMString::from(String::from_utf8(writer).unwrap())
3189    }
3190
3191    /// <https://w3c.github.io/DOM-Parsing/#dfn-xml-serialization>
3192    pub(crate) fn xml_serialize(
3193        &self,
3194        traversal_scope: xml_serialize::TraversalScope,
3195    ) -> Fallible<DOMString> {
3196        let mut writer = vec![];
3197        xml_serialize::serialize(
3198            &mut writer,
3199            &self,
3200            xml_serialize::SerializeOpts { traversal_scope },
3201        )
3202        .map_err(|error| {
3203            error!("Cannot serialize node: {error}");
3204            Error::InvalidState
3205        })?;
3206
3207        // FIXME(ajeffrey): Directly convert UTF8 to DOMString
3208        let string = DOMString::from(String::from_utf8(writer).map_err(|error| {
3209            error!("Cannot serialize node: {error}");
3210            Error::InvalidState
3211        })?);
3212
3213        Ok(string)
3214    }
3215
3216    /// <https://html.spec.whatwg.org/multipage/#fragment-serializing-algorithm-steps>
3217    pub(crate) fn fragment_serialization_algorithm(
3218        &self,
3219        require_well_formed: bool,
3220        can_gc: CanGc,
3221    ) -> Fallible<DOMString> {
3222        // Step 1. Let context document be node's node document.
3223        let context_document = self.owner_document();
3224
3225        // Step 2. If context document is an HTML document, return the result of HTML fragment serialization algorithm
3226        // with node, false, and « ».
3227        if context_document.is_html_document() {
3228            return Ok(self.html_serialize(
3229                html_serialize::TraversalScope::ChildrenOnly(None),
3230                false,
3231                vec![],
3232                can_gc,
3233            ));
3234        }
3235
3236        // Step 3. Return the XML serialization of node given require well-formed.
3237        // TODO: xml5ever doesn't seem to want require_well_formed
3238        let _ = require_well_formed;
3239        self.xml_serialize(xml_serialize::TraversalScope::ChildrenOnly(None))
3240    }
3241
3242    /// Return true if this node establishes a "scrolling box" for the purposes of `scrollIntoView`.
3243    pub(crate) fn establishes_scrolling_box(&self) -> bool {
3244        // For now, `Document` represents the viewport.
3245        //
3246        // TODO: Is this the right thing to do? Maybe `Document` should be ignored and viewport
3247        // should be represented by the root of the DOM flat tree.
3248        if self.is::<Document>() {
3249            return true;
3250        }
3251        let Some(element) = self.downcast::<Element>() else {
3252            // Shadow roots and other nodes are not scrolling boxes.
3253            return false;
3254        };
3255        // TODO: This should ask layout whether or not the element establishes a scrolling
3256        // box. This heuristic is wrong.
3257        element.style().is_some_and(|style| {
3258            let overflow_x = style.get_box().clone_overflow_x();
3259            let overflow_y = style.get_box().clone_overflow_y();
3260            overflow_x.is_scrollable() || overflow_y.is_scrollable()
3261        })
3262    }
3263}
3264
3265impl NodeMethods<crate::DomTypeHolder> for Node {
3266    /// <https://dom.spec.whatwg.org/#dom-node-nodetype>
3267    fn NodeType(&self) -> u16 {
3268        match self.type_id() {
3269            NodeTypeId::Attr => NodeConstants::ATTRIBUTE_NODE,
3270            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::Text)) => {
3271                NodeConstants::TEXT_NODE
3272            },
3273            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::CDATASection)) => {
3274                NodeConstants::CDATA_SECTION_NODE
3275            },
3276            NodeTypeId::CharacterData(CharacterDataTypeId::ProcessingInstruction) => {
3277                NodeConstants::PROCESSING_INSTRUCTION_NODE
3278            },
3279            NodeTypeId::CharacterData(CharacterDataTypeId::Comment) => NodeConstants::COMMENT_NODE,
3280            NodeTypeId::Document(_) => NodeConstants::DOCUMENT_NODE,
3281            NodeTypeId::DocumentType => NodeConstants::DOCUMENT_TYPE_NODE,
3282            NodeTypeId::DocumentFragment(_) => NodeConstants::DOCUMENT_FRAGMENT_NODE,
3283            NodeTypeId::Element(_) => NodeConstants::ELEMENT_NODE,
3284        }
3285    }
3286
3287    /// <https://dom.spec.whatwg.org/#dom-node-nodename>
3288    fn NodeName(&self) -> DOMString {
3289        match self.type_id() {
3290            NodeTypeId::Attr => self.downcast::<Attr>().unwrap().qualified_name(),
3291            NodeTypeId::Element(..) => self.downcast::<Element>().unwrap().TagName(),
3292            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::Text)) => {
3293                DOMString::from("#text")
3294            },
3295            NodeTypeId::CharacterData(CharacterDataTypeId::Text(TextTypeId::CDATASection)) => {
3296                DOMString::from("#cdata-section")
3297            },
3298            NodeTypeId::CharacterData(CharacterDataTypeId::ProcessingInstruction) => {
3299                self.downcast::<ProcessingInstruction>().unwrap().Target()
3300            },
3301            NodeTypeId::CharacterData(CharacterDataTypeId::Comment) => DOMString::from("#comment"),
3302            NodeTypeId::DocumentType => self.downcast::<DocumentType>().unwrap().name().clone(),
3303            NodeTypeId::DocumentFragment(_) => DOMString::from("#document-fragment"),
3304            NodeTypeId::Document(_) => DOMString::from("#document"),
3305        }
3306    }
3307
3308    /// <https://dom.spec.whatwg.org/#dom-node-baseuri>
3309    fn BaseURI(&self) -> USVString {
3310        USVString(String::from(self.owner_doc().base_url().as_str()))
3311    }
3312
3313    /// <https://dom.spec.whatwg.org/#dom-node-isconnected>
3314    fn IsConnected(&self) -> bool {
3315        self.is_connected()
3316    }
3317
3318    /// <https://dom.spec.whatwg.org/#dom-node-ownerdocument>
3319    fn GetOwnerDocument(&self) -> Option<DomRoot<Document>> {
3320        match self.type_id() {
3321            NodeTypeId::Document(_) => None,
3322            _ => Some(self.owner_doc()),
3323        }
3324    }
3325
3326    /// <https://dom.spec.whatwg.org/#dom-node-getrootnode>
3327    fn GetRootNode(&self, options: &GetRootNodeOptions) -> DomRoot<Node> {
3328        if !options.composed {
3329            if let Some(shadow_root) = self.containing_shadow_root() {
3330                return DomRoot::upcast(shadow_root);
3331            }
3332        }
3333
3334        if self.is_connected() {
3335            DomRoot::from_ref(self.owner_doc().upcast::<Node>())
3336        } else {
3337            self.inclusive_ancestors(ShadowIncluding::Yes)
3338                .last()
3339                .unwrap()
3340        }
3341    }
3342
3343    /// <https://dom.spec.whatwg.org/#dom-node-parentnode>
3344    fn GetParentNode(&self) -> Option<DomRoot<Node>> {
3345        self.parent_node.get()
3346    }
3347
3348    /// <https://dom.spec.whatwg.org/#dom-node-parentelement>
3349    fn GetParentElement(&self) -> Option<DomRoot<Element>> {
3350        self.GetParentNode().and_then(DomRoot::downcast)
3351    }
3352
3353    /// <https://dom.spec.whatwg.org/#dom-node-haschildnodes>
3354    fn HasChildNodes(&self) -> bool {
3355        self.first_child.get().is_some()
3356    }
3357
3358    /// <https://dom.spec.whatwg.org/#dom-node-childnodes>
3359    fn ChildNodes(&self, can_gc: CanGc) -> DomRoot<NodeList> {
3360        if let Some(list) = self.ensure_rare_data().child_list.get() {
3361            return list;
3362        }
3363
3364        let doc = self.owner_doc();
3365        let window = doc.window();
3366        let list = NodeList::new_child_list(window, self, can_gc);
3367        self.ensure_rare_data().child_list.set(Some(&list));
3368        list
3369    }
3370
3371    /// <https://dom.spec.whatwg.org/#dom-node-firstchild>
3372    fn GetFirstChild(&self) -> Option<DomRoot<Node>> {
3373        self.first_child.get()
3374    }
3375
3376    /// <https://dom.spec.whatwg.org/#dom-node-lastchild>
3377    fn GetLastChild(&self) -> Option<DomRoot<Node>> {
3378        self.last_child.get()
3379    }
3380
3381    /// <https://dom.spec.whatwg.org/#dom-node-previoussibling>
3382    fn GetPreviousSibling(&self) -> Option<DomRoot<Node>> {
3383        self.prev_sibling.get()
3384    }
3385
3386    /// <https://dom.spec.whatwg.org/#dom-node-nextsibling>
3387    fn GetNextSibling(&self) -> Option<DomRoot<Node>> {
3388        self.next_sibling.get()
3389    }
3390
3391    /// <https://dom.spec.whatwg.org/#dom-node-nodevalue>
3392    fn GetNodeValue(&self) -> Option<DOMString> {
3393        match self.type_id() {
3394            NodeTypeId::Attr => Some(self.downcast::<Attr>().unwrap().Value()),
3395            NodeTypeId::CharacterData(_) => {
3396                self.downcast::<CharacterData>().map(CharacterData::Data)
3397            },
3398            _ => None,
3399        }
3400    }
3401
3402    /// <https://dom.spec.whatwg.org/#dom-node-nodevalue>
3403    fn SetNodeValue(&self, val: Option<DOMString>, can_gc: CanGc) -> Fallible<()> {
3404        match self.type_id() {
3405            NodeTypeId::Attr => {
3406                let attr = self.downcast::<Attr>().unwrap();
3407                attr.SetValue(val.unwrap_or_default(), can_gc)?;
3408            },
3409            NodeTypeId::CharacterData(_) => {
3410                let character_data = self.downcast::<CharacterData>().unwrap();
3411                character_data.SetData(val.unwrap_or_default());
3412            },
3413            _ => {},
3414        };
3415        Ok(())
3416    }
3417
3418    /// <https://dom.spec.whatwg.org/#dom-node-textcontent>
3419    fn GetTextContent(&self) -> Option<DOMString> {
3420        match self.type_id() {
3421            NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..) => {
3422                let content =
3423                    Node::collect_text_contents(self.traverse_preorder(ShadowIncluding::No));
3424                Some(content)
3425            },
3426            NodeTypeId::Attr => Some(self.downcast::<Attr>().unwrap().Value()),
3427            NodeTypeId::CharacterData(..) => {
3428                let characterdata = self.downcast::<CharacterData>().unwrap();
3429                Some(characterdata.Data())
3430            },
3431            NodeTypeId::DocumentType | NodeTypeId::Document(_) => None,
3432        }
3433    }
3434
3435    /// <https://dom.spec.whatwg.org/#set-text-content>
3436    fn SetTextContent(&self, value: Option<DOMString>, can_gc: CanGc) -> Fallible<()> {
3437        match self.type_id() {
3438            NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..) => {
3439                self.set_text_content_for_element(value, can_gc);
3440            },
3441            NodeTypeId::Attr => {
3442                let attr = self.downcast::<Attr>().unwrap();
3443                attr.SetValue(value.unwrap_or_default(), can_gc)?;
3444            },
3445            NodeTypeId::CharacterData(..) => {
3446                let characterdata = self.downcast::<CharacterData>().unwrap();
3447                characterdata.SetData(value.unwrap_or_default());
3448            },
3449            NodeTypeId::DocumentType | NodeTypeId::Document(_) => {},
3450        };
3451        Ok(())
3452    }
3453
3454    /// <https://dom.spec.whatwg.org/#dom-node-insertbefore>
3455    fn InsertBefore(
3456        &self,
3457        node: &Node,
3458        child: Option<&Node>,
3459        can_gc: CanGc,
3460    ) -> Fallible<DomRoot<Node>> {
3461        Node::pre_insert(node, self, child, can_gc)
3462    }
3463
3464    /// <https://dom.spec.whatwg.org/#dom-node-appendchild>
3465    fn AppendChild(&self, node: &Node, can_gc: CanGc) -> Fallible<DomRoot<Node>> {
3466        Node::pre_insert(node, self, None, can_gc)
3467    }
3468
3469    /// <https://dom.spec.whatwg.org/#concept-node-replace>
3470    fn ReplaceChild(&self, node: &Node, child: &Node, can_gc: CanGc) -> Fallible<DomRoot<Node>> {
3471        // Step 1. If parent is not a Document, DocumentFragment, or Element node,
3472        // then throw a "HierarchyRequestError" DOMException.
3473        match self.type_id() {
3474            NodeTypeId::Document(_) | NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..) => {
3475            },
3476            _ => return Err(Error::HierarchyRequest),
3477        }
3478
3479        // Step 2. If node is a host-including inclusive ancestor of parent,
3480        // then throw a "HierarchyRequestError" DOMException.
3481        if node.is_inclusive_ancestor_of(self) {
3482            return Err(Error::HierarchyRequest);
3483        }
3484
3485        // Step 3. If child’s parent is not parent, then throw a "NotFoundError" DOMException.
3486        if !self.is_parent_of(child) {
3487            return Err(Error::NotFound);
3488        }
3489
3490        // Step 4. If node is not a DocumentFragment, DocumentType, Element, or CharacterData node,
3491        // then throw a "HierarchyRequestError" DOMException.
3492        // Step 5. If either node is a Text node and parent is a document,
3493        // or node is a doctype and parent is not a document, then throw a "HierarchyRequestError" DOMException.
3494        match node.type_id() {
3495            NodeTypeId::CharacterData(CharacterDataTypeId::Text(_)) if self.is::<Document>() => {
3496                return Err(Error::HierarchyRequest);
3497            },
3498            NodeTypeId::DocumentType if !self.is::<Document>() => {
3499                return Err(Error::HierarchyRequest);
3500            },
3501            NodeTypeId::Document(_) | NodeTypeId::Attr => return Err(Error::HierarchyRequest),
3502            _ => (),
3503        }
3504
3505        // Step 6. If parent is a document, and any of the statements below, switched on the interface node implements,
3506        // are true, then throw a "HierarchyRequestError" DOMException.
3507        if self.is::<Document>() {
3508            match node.type_id() {
3509                // Step 6.1
3510                NodeTypeId::DocumentFragment(_) => {
3511                    // Step 6.1.1(b)
3512                    if node.children().any(|c| c.is::<Text>()) {
3513                        return Err(Error::HierarchyRequest);
3514                    }
3515                    match node.child_elements().count() {
3516                        0 => (),
3517                        // Step 6.1.2
3518                        1 => {
3519                            if self.child_elements().any(|c| c.upcast::<Node>() != child) {
3520                                return Err(Error::HierarchyRequest);
3521                            }
3522                            if child.following_siblings().any(|child| child.is_doctype()) {
3523                                return Err(Error::HierarchyRequest);
3524                            }
3525                        },
3526                        // Step 6.1.1(a)
3527                        _ => return Err(Error::HierarchyRequest),
3528                    }
3529                },
3530                // Step 6.2
3531                NodeTypeId::Element(..) => {
3532                    if self.child_elements().any(|c| c.upcast::<Node>() != child) {
3533                        return Err(Error::HierarchyRequest);
3534                    }
3535                    if child.following_siblings().any(|child| child.is_doctype()) {
3536                        return Err(Error::HierarchyRequest);
3537                    }
3538                },
3539                // Step 6.3
3540                NodeTypeId::DocumentType => {
3541                    if self.children().any(|c| c.is_doctype() && &*c != child) {
3542                        return Err(Error::HierarchyRequest);
3543                    }
3544                    if self
3545                        .children()
3546                        .take_while(|c| &**c != child)
3547                        .any(|c| c.is::<Element>())
3548                    {
3549                        return Err(Error::HierarchyRequest);
3550                    }
3551                },
3552                NodeTypeId::CharacterData(..) => (),
3553                // Because Document and Attr should already throw `HierarchyRequest`
3554                // error, both of them are unreachable here.
3555                NodeTypeId::Document(_) => unreachable!(),
3556                NodeTypeId::Attr => unreachable!(),
3557            }
3558        }
3559
3560        // Step 7. Let referenceChild be child’s next sibling.
3561        // Step 8. If referenceChild is node, then set referenceChild to node’s next sibling.
3562        let child_next_sibling = child.GetNextSibling();
3563        let node_next_sibling = node.GetNextSibling();
3564        let reference_child = if child_next_sibling.as_deref() == Some(node) {
3565            node_next_sibling.as_deref()
3566        } else {
3567            child_next_sibling.as_deref()
3568        };
3569
3570        // Step 9. Let previousSibling be child’s previous sibling.
3571        let previous_sibling = child.GetPreviousSibling();
3572
3573        // NOTE: All existing browsers assume that adoption is performed here, which does not follow the DOM spec.
3574        // However, if we follow the spec and delay adoption to inside `Node::insert()`, then the mutation records will
3575        // be different, and we will fail WPT dom/nodes/MutationObserver-childList.html.
3576        let document = self.owner_document();
3577        Node::adopt(node, &document, can_gc);
3578
3579        // Step 10. Let removedNodes be the empty set.
3580        // Step 11. If child’s parent is non-null:
3581        //     1. Set removedNodes to « child ».
3582        //     2. Remove child with the suppress observers flag set.
3583        let removed_child = if node != child {
3584            // Step 11.
3585            Node::remove(child, self, SuppressObserver::Suppressed, can_gc);
3586            Some(child)
3587        } else {
3588            None
3589        };
3590
3591        // Step 12. Let nodes be node’s children if node is a DocumentFragment node; otherwise « node ».
3592        rooted_vec!(let mut nodes);
3593        let nodes = if node.type_id() ==
3594            NodeTypeId::DocumentFragment(DocumentFragmentTypeId::DocumentFragment) ||
3595            node.type_id() == NodeTypeId::DocumentFragment(DocumentFragmentTypeId::ShadowRoot)
3596        {
3597            nodes.extend(node.children().map(|node| Dom::from_ref(&*node)));
3598            nodes.r()
3599        } else {
3600            from_ref(&node)
3601        };
3602
3603        // Step 13. Insert node into parent before referenceChild with the suppress observers flag set.
3604        Node::insert(
3605            node,
3606            self,
3607            reference_child,
3608            SuppressObserver::Suppressed,
3609            can_gc,
3610        );
3611
3612        vtable_for(self).children_changed(&ChildrenMutation::replace(
3613            previous_sibling.as_deref(),
3614            &removed_child,
3615            nodes,
3616            reference_child,
3617        ));
3618
3619        // Step 14. Queue a tree mutation record for parent with nodes, removedNodes,
3620        // previousSibling, and referenceChild.
3621        let removed = removed_child.map(|r| [r]);
3622        let mutation = LazyCell::new(|| Mutation::ChildList {
3623            added: Some(nodes),
3624            removed: removed.as_ref().map(|r| &r[..]),
3625            prev: previous_sibling.as_deref(),
3626            next: reference_child,
3627        });
3628
3629        MutationObserver::queue_a_mutation_record(self, mutation);
3630
3631        // Step 15. Return child.
3632        Ok(DomRoot::from_ref(child))
3633    }
3634
3635    /// <https://dom.spec.whatwg.org/#dom-node-removechild>
3636    fn RemoveChild(&self, node: &Node, can_gc: CanGc) -> Fallible<DomRoot<Node>> {
3637        Node::pre_remove(node, self, can_gc)
3638    }
3639
3640    /// <https://dom.spec.whatwg.org/#dom-node-normalize>
3641    fn Normalize(&self, can_gc: CanGc) {
3642        let mut children = self.children().enumerate().peekable();
3643        while let Some((_, node)) = children.next() {
3644            if let Some(text) = node.downcast::<Text>() {
3645                if text.is::<CDATASection>() {
3646                    continue;
3647                }
3648                let cdata = text.upcast::<CharacterData>();
3649                let mut length = cdata.Length();
3650                if length == 0 {
3651                    Node::remove(&node, self, SuppressObserver::Unsuppressed, can_gc);
3652                    continue;
3653                }
3654                while children.peek().is_some_and(|(_, sibling)| {
3655                    sibling.is::<Text>() && !sibling.is::<CDATASection>()
3656                }) {
3657                    let (index, sibling) = children.next().unwrap();
3658                    sibling
3659                        .ranges()
3660                        .drain_to_preceding_text_sibling(&sibling, &node, length);
3661                    self.ranges()
3662                        .move_to_text_child_at(self, index as u32, &node, length);
3663                    let sibling_cdata = sibling.downcast::<CharacterData>().unwrap();
3664                    length += sibling_cdata.Length();
3665                    cdata.append_data(&sibling_cdata.data());
3666                    Node::remove(&sibling, self, SuppressObserver::Unsuppressed, can_gc);
3667                }
3668            } else {
3669                node.Normalize(can_gc);
3670            }
3671        }
3672    }
3673
3674    /// <https://dom.spec.whatwg.org/#dom-node-clonenode>
3675    fn CloneNode(&self, subtree: bool, can_gc: CanGc) -> Fallible<DomRoot<Node>> {
3676        // Step 1. If this is a shadow root, then throw a "NotSupportedError" DOMException.
3677        if self.is::<ShadowRoot>() {
3678            return Err(Error::NotSupported);
3679        }
3680
3681        // Step 2. Return the result of cloning a node given this with subtree set to subtree.
3682        let result = Node::clone(
3683            self,
3684            None,
3685            if subtree {
3686                CloneChildrenFlag::CloneChildren
3687            } else {
3688                CloneChildrenFlag::DoNotCloneChildren
3689            },
3690            can_gc,
3691        );
3692        Ok(result)
3693    }
3694
3695    /// <https://dom.spec.whatwg.org/#dom-node-isequalnode>
3696    fn IsEqualNode(&self, maybe_node: Option<&Node>) -> bool {
3697        fn is_equal_doctype(node: &Node, other: &Node) -> bool {
3698            let doctype = node.downcast::<DocumentType>().unwrap();
3699            let other_doctype = other.downcast::<DocumentType>().unwrap();
3700            (*doctype.name() == *other_doctype.name()) &&
3701                (*doctype.public_id() == *other_doctype.public_id()) &&
3702                (*doctype.system_id() == *other_doctype.system_id())
3703        }
3704        fn is_equal_element(node: &Node, other: &Node) -> bool {
3705            let element = node.downcast::<Element>().unwrap();
3706            let other_element = other.downcast::<Element>().unwrap();
3707            (*element.namespace() == *other_element.namespace()) &&
3708                (*element.prefix() == *other_element.prefix()) &&
3709                (*element.local_name() == *other_element.local_name()) &&
3710                (element.attrs().len() == other_element.attrs().len())
3711        }
3712        fn is_equal_processinginstruction(node: &Node, other: &Node) -> bool {
3713            let pi = node.downcast::<ProcessingInstruction>().unwrap();
3714            let other_pi = other.downcast::<ProcessingInstruction>().unwrap();
3715            (*pi.target() == *other_pi.target()) &&
3716                (*pi.upcast::<CharacterData>().data() ==
3717                    *other_pi.upcast::<CharacterData>().data())
3718        }
3719        fn is_equal_characterdata(node: &Node, other: &Node) -> bool {
3720            let characterdata = node.downcast::<CharacterData>().unwrap();
3721            let other_characterdata = other.downcast::<CharacterData>().unwrap();
3722            *characterdata.data() == *other_characterdata.data()
3723        }
3724        fn is_equal_attr(node: &Node, other: &Node) -> bool {
3725            let attr = node.downcast::<Attr>().unwrap();
3726            let other_attr = other.downcast::<Attr>().unwrap();
3727            (*attr.namespace() == *other_attr.namespace()) &&
3728                (attr.local_name() == other_attr.local_name()) &&
3729                (**attr.value() == **other_attr.value())
3730        }
3731        fn is_equal_element_attrs(node: &Node, other: &Node) -> bool {
3732            let element = node.downcast::<Element>().unwrap();
3733            let other_element = other.downcast::<Element>().unwrap();
3734            assert!(element.attrs().len() == other_element.attrs().len());
3735            element.attrs().iter().all(|attr| {
3736                other_element.attrs().iter().any(|other_attr| {
3737                    (*attr.namespace() == *other_attr.namespace()) &&
3738                        (attr.local_name() == other_attr.local_name()) &&
3739                        (**attr.value() == **other_attr.value())
3740                })
3741            })
3742        }
3743
3744        fn is_equal_node(this: &Node, node: &Node) -> bool {
3745            // Step 2.
3746            if this.NodeType() != node.NodeType() {
3747                return false;
3748            }
3749
3750            match node.type_id() {
3751                // Step 3.
3752                NodeTypeId::DocumentType if !is_equal_doctype(this, node) => return false,
3753                NodeTypeId::Element(..) if !is_equal_element(this, node) => return false,
3754                NodeTypeId::CharacterData(CharacterDataTypeId::ProcessingInstruction)
3755                    if !is_equal_processinginstruction(this, node) =>
3756                {
3757                    return false;
3758                },
3759                NodeTypeId::CharacterData(CharacterDataTypeId::Text(_)) |
3760                NodeTypeId::CharacterData(CharacterDataTypeId::Comment)
3761                    if !is_equal_characterdata(this, node) =>
3762                {
3763                    return false;
3764                },
3765                // Step 4.
3766                NodeTypeId::Element(..) if !is_equal_element_attrs(this, node) => return false,
3767                NodeTypeId::Attr if !is_equal_attr(this, node) => return false,
3768
3769                _ => (),
3770            }
3771
3772            // Step 5.
3773            if this.children_count() != node.children_count() {
3774                return false;
3775            }
3776
3777            // Step 6.
3778            this.children()
3779                .zip(node.children())
3780                .all(|(child, other_child)| is_equal_node(&child, &other_child))
3781        }
3782        match maybe_node {
3783            // Step 1.
3784            None => false,
3785            // Step 2-6.
3786            Some(node) => is_equal_node(self, node),
3787        }
3788    }
3789
3790    /// <https://dom.spec.whatwg.org/#dom-node-issamenode>
3791    fn IsSameNode(&self, other_node: Option<&Node>) -> bool {
3792        match other_node {
3793            Some(node) => self == node,
3794            None => false,
3795        }
3796    }
3797
3798    /// <https://dom.spec.whatwg.org/#dom-node-comparedocumentposition>
3799    fn CompareDocumentPosition(&self, other: &Node) -> u16 {
3800        // step 1.
3801        if self == other {
3802            return 0;
3803        }
3804
3805        // step 2
3806        let mut node1 = Some(other);
3807        let mut node2 = Some(self);
3808
3809        // step 3
3810        let mut attr1: Option<&Attr> = None;
3811        let mut attr2: Option<&Attr> = None;
3812
3813        // step 4: spec says to operate on node1 here,
3814        // node1 is definitely Some(other) going into this step
3815        // The compiler doesn't know the lifetime of attr1.GetOwnerElement
3816        // is guaranteed by the lifetime of attr1, so we hold it explicitly
3817        let attr1owner;
3818        if let Some(a) = other.downcast::<Attr>() {
3819            attr1 = Some(a);
3820            attr1owner = a.GetOwnerElement();
3821            node1 = match attr1owner {
3822                Some(ref e) => Some(e.upcast()),
3823                None => None,
3824            }
3825        }
3826
3827        // step 5.1: spec says to operate on node2 here,
3828        // node2 is definitely just Some(self) going into this step
3829        let attr2owner;
3830        if let Some(a) = self.downcast::<Attr>() {
3831            attr2 = Some(a);
3832            attr2owner = a.GetOwnerElement();
3833            node2 = match attr2owner {
3834                Some(ref e) => Some(e.upcast()),
3835                None => None,
3836            }
3837        }
3838
3839        // Step 5.2
3840        // This substep seems lacking in test coverage.
3841        // We hit this when comparing two attributes that have the
3842        // same owner element.
3843        if let Some(node2) = node2 {
3844            if Some(node2) == node1 {
3845                if let (Some(a1), Some(a2)) = (attr1, attr2) {
3846                    let attrs = node2.downcast::<Element>().unwrap().attrs();
3847                    // go through the attrs in order to see if self
3848                    // or other is first; spec is clear that we
3849                    // want value-equality, not reference-equality
3850                    for attr in attrs.iter() {
3851                        if (*attr.namespace() == *a1.namespace()) &&
3852                            (attr.local_name() == a1.local_name()) &&
3853                            (**attr.value() == **a1.value())
3854                        {
3855                            return NodeConstants::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC +
3856                                NodeConstants::DOCUMENT_POSITION_PRECEDING;
3857                        }
3858                        if (*attr.namespace() == *a2.namespace()) &&
3859                            (attr.local_name() == a2.local_name()) &&
3860                            (**attr.value() == **a2.value())
3861                        {
3862                            return NodeConstants::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC +
3863                                NodeConstants::DOCUMENT_POSITION_FOLLOWING;
3864                        }
3865                    }
3866                    // both attrs have node2 as their owner element, so
3867                    // we can't have left the loop without seeing them
3868                    unreachable!();
3869                }
3870            }
3871        }
3872
3873        // Step 6
3874        match (node1, node2) {
3875            (None, _) => {
3876                // node1 is null
3877                NodeConstants::DOCUMENT_POSITION_FOLLOWING +
3878                    NodeConstants::DOCUMENT_POSITION_DISCONNECTED +
3879                    NodeConstants::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC
3880            },
3881            (_, None) => {
3882                // node2 is null
3883                NodeConstants::DOCUMENT_POSITION_PRECEDING +
3884                    NodeConstants::DOCUMENT_POSITION_DISCONNECTED +
3885                    NodeConstants::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC
3886            },
3887            (Some(node1), Some(node2)) => {
3888                // still step 6, testing if node1 and 2 share a root
3889                let mut self_and_ancestors = node2
3890                    .inclusive_ancestors(ShadowIncluding::No)
3891                    .collect::<SmallVec<[_; 20]>>();
3892                let mut other_and_ancestors = node1
3893                    .inclusive_ancestors(ShadowIncluding::No)
3894                    .collect::<SmallVec<[_; 20]>>();
3895
3896                if self_and_ancestors.last() != other_and_ancestors.last() {
3897                    let random = as_uintptr(self_and_ancestors.last().unwrap()) <
3898                        as_uintptr(other_and_ancestors.last().unwrap());
3899                    let random = if random {
3900                        NodeConstants::DOCUMENT_POSITION_FOLLOWING
3901                    } else {
3902                        NodeConstants::DOCUMENT_POSITION_PRECEDING
3903                    };
3904
3905                    // Disconnected.
3906                    return random +
3907                        NodeConstants::DOCUMENT_POSITION_DISCONNECTED +
3908                        NodeConstants::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
3909                }
3910                // steps 7-10
3911                let mut parent = self_and_ancestors.pop().unwrap();
3912                other_and_ancestors.pop().unwrap();
3913
3914                let mut current_position =
3915                    cmp::min(self_and_ancestors.len(), other_and_ancestors.len());
3916
3917                while current_position > 0 {
3918                    current_position -= 1;
3919                    let child_1 = self_and_ancestors.pop().unwrap();
3920                    let child_2 = other_and_ancestors.pop().unwrap();
3921
3922                    if child_1 != child_2 {
3923                        let is_before = parent.children().position(|c| c == child_1).unwrap() <
3924                            parent.children().position(|c| c == child_2).unwrap();
3925                        // If I am before, `other` is following, and the other way
3926                        // around.
3927                        return if is_before {
3928                            NodeConstants::DOCUMENT_POSITION_FOLLOWING
3929                        } else {
3930                            NodeConstants::DOCUMENT_POSITION_PRECEDING
3931                        };
3932                    }
3933
3934                    parent = child_1;
3935                }
3936
3937                // We hit the end of one of the parent chains, so one node needs to be
3938                // contained in the other.
3939                //
3940                // If we're the container, return that `other` is contained by us.
3941                if self_and_ancestors.len() < other_and_ancestors.len() {
3942                    NodeConstants::DOCUMENT_POSITION_FOLLOWING +
3943                        NodeConstants::DOCUMENT_POSITION_CONTAINED_BY
3944                } else {
3945                    NodeConstants::DOCUMENT_POSITION_PRECEDING +
3946                        NodeConstants::DOCUMENT_POSITION_CONTAINS
3947                }
3948            },
3949        }
3950    }
3951
3952    /// <https://dom.spec.whatwg.org/#dom-node-contains>
3953    fn Contains(&self, maybe_other: Option<&Node>) -> bool {
3954        match maybe_other {
3955            None => false,
3956            Some(other) => self.is_inclusive_ancestor_of(other),
3957        }
3958    }
3959
3960    /// <https://dom.spec.whatwg.org/#dom-node-lookupprefix>
3961    fn LookupPrefix(&self, namespace: Option<DOMString>) -> Option<DOMString> {
3962        let namespace = namespace_from_domstring(namespace);
3963
3964        // Step 1.
3965        if namespace == ns!() {
3966            return None;
3967        }
3968
3969        // Step 2.
3970        match self.type_id() {
3971            NodeTypeId::Element(..) => self.downcast::<Element>().unwrap().lookup_prefix(namespace),
3972            NodeTypeId::Document(_) => self
3973                .downcast::<Document>()
3974                .unwrap()
3975                .GetDocumentElement()
3976                .and_then(|element| element.lookup_prefix(namespace)),
3977            NodeTypeId::DocumentType | NodeTypeId::DocumentFragment(_) => None,
3978            NodeTypeId::Attr => self
3979                .downcast::<Attr>()
3980                .unwrap()
3981                .GetOwnerElement()
3982                .and_then(|element| element.lookup_prefix(namespace)),
3983            _ => self
3984                .GetParentElement()
3985                .and_then(|element| element.lookup_prefix(namespace)),
3986        }
3987    }
3988
3989    /// <https://dom.spec.whatwg.org/#dom-node-lookupnamespaceuri>
3990    fn LookupNamespaceURI(&self, prefix: Option<DOMString>) -> Option<DOMString> {
3991        // Step 1. If prefix is the empty string, then set it to null.
3992        let prefix = prefix.filter(|prefix| !prefix.is_empty());
3993
3994        // Step 2. Return the result of running locate a namespace for this using prefix.
3995        Node::namespace_to_string(Node::locate_namespace(self, prefix))
3996    }
3997
3998    /// <https://dom.spec.whatwg.org/#dom-node-isdefaultnamespace>
3999    fn IsDefaultNamespace(&self, namespace: Option<DOMString>) -> bool {
4000        // Step 1.
4001        let namespace = namespace_from_domstring(namespace);
4002        // Steps 2 and 3.
4003        Node::locate_namespace(self, None) == namespace
4004    }
4005}
4006
4007pub(crate) trait NodeTraits {
4008    /// Get the [`Document`] that owns this node. Note that this may differ from the
4009    /// [`Document`] that the node was created in if it was adopted by a different
4010    /// [`Document`] (the owner).
4011    fn owner_document(&self) -> DomRoot<Document>;
4012    /// Get the [`Window`] of the [`Document`] that owns this node. Note that this may
4013    /// differ from the [`Document`] that the node was created in if it was adopted by a
4014    /// different [`Document`] (the owner).
4015    fn owner_window(&self) -> DomRoot<Window>;
4016    /// Get the [`GlobalScope`] of the [`Document`] that owns this node. Note that this may
4017    /// differ from the [`GlobalScope`] that the node was created in if it was adopted by a
4018    /// different [`Document`] (the owner).
4019    fn owner_global(&self) -> DomRoot<GlobalScope>;
4020    /// If this [`Node`] is contained in a [`ShadowRoot`] return it, otherwise `None`.
4021    fn containing_shadow_root(&self) -> Option<DomRoot<ShadowRoot>>;
4022    /// Get the stylesheet owner for this node: either the [`Document`] or the [`ShadowRoot`]
4023    /// of the node.
4024    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
4025    fn stylesheet_list_owner(&self) -> StyleSheetListOwner;
4026}
4027
4028impl<T: DerivedFrom<Node> + DomObject> NodeTraits for T {
4029    fn owner_document(&self) -> DomRoot<Document> {
4030        self.upcast().owner_doc()
4031    }
4032
4033    fn owner_window(&self) -> DomRoot<Window> {
4034        DomRoot::from_ref(self.owner_document().window())
4035    }
4036
4037    fn owner_global(&self) -> DomRoot<GlobalScope> {
4038        DomRoot::from_ref(self.owner_window().upcast())
4039    }
4040
4041    fn containing_shadow_root(&self) -> Option<DomRoot<ShadowRoot>> {
4042        Node::containing_shadow_root(self.upcast())
4043    }
4044
4045    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
4046    fn stylesheet_list_owner(&self) -> StyleSheetListOwner {
4047        self.containing_shadow_root()
4048            .map(|shadow_root| StyleSheetListOwner::ShadowRoot(Dom::from_ref(&*shadow_root)))
4049            .unwrap_or_else(|| {
4050                StyleSheetListOwner::Document(Dom::from_ref(&*self.owner_document()))
4051            })
4052    }
4053}
4054
4055impl VirtualMethods for Node {
4056    fn super_type(&self) -> Option<&dyn VirtualMethods> {
4057        Some(self.upcast::<EventTarget>() as &dyn VirtualMethods)
4058    }
4059
4060    fn children_changed(&self, mutation: &ChildrenMutation) {
4061        if let Some(s) = self.super_type() {
4062            s.children_changed(mutation);
4063        }
4064
4065        if let Some(data) = self.rare_data().as_ref() {
4066            if let Some(list) = data.child_list.get() {
4067                list.as_children_list().children_changed(mutation);
4068            }
4069        }
4070
4071        self.owner_doc().content_and_heritage_changed(self);
4072    }
4073
4074    // This handles the ranges mentioned in steps 2-3 when removing a node.
4075    /// <https://dom.spec.whatwg.org/#concept-node-remove>
4076    fn unbind_from_tree(&self, context: &UnbindContext, can_gc: CanGc) {
4077        self.super_type().unwrap().unbind_from_tree(context, can_gc);
4078
4079        // Ranges should only drain to the parent from inclusive non-shadow
4080        // including descendants. If we're in a shadow tree at this point then the
4081        // unbind operation happened further up in the tree and we should not
4082        // drain any ranges.
4083        if !self.is_in_a_shadow_tree() && !self.ranges_is_empty() {
4084            self.ranges().drain_to_parent(context, self);
4085        }
4086    }
4087}
4088
4089/// A summary of the changes that happened to a node.
4090#[derive(Clone, Copy, MallocSizeOf, PartialEq)]
4091pub(crate) enum NodeDamage {
4092    /// The node's `style` attribute changed.
4093    Style,
4094    /// The node's content or heritage changed, such as the addition or removal of
4095    /// children.
4096    ContentOrHeritage,
4097    /// Other parts of a node changed; attributes, text content, etc.
4098    Other,
4099}
4100
4101pub(crate) enum ChildrenMutation<'a> {
4102    Append {
4103        prev: &'a Node,
4104        added: &'a [&'a Node],
4105    },
4106    Insert {
4107        prev: &'a Node,
4108        added: &'a [&'a Node],
4109        next: &'a Node,
4110    },
4111    Prepend {
4112        added: &'a [&'a Node],
4113        next: &'a Node,
4114    },
4115    Replace {
4116        prev: Option<&'a Node>,
4117        removed: &'a Node,
4118        added: &'a [&'a Node],
4119        next: Option<&'a Node>,
4120    },
4121    ReplaceAll {
4122        removed: &'a [&'a Node],
4123        added: &'a [&'a Node],
4124    },
4125    /// Mutation for when a Text node's data is modified.
4126    /// This doesn't change the structure of the list, which is what the other
4127    /// variants' fields are stored for at the moment, so this can just have no
4128    /// fields.
4129    ChangeText,
4130}
4131
4132impl<'a> ChildrenMutation<'a> {
4133    fn insert(
4134        prev: Option<&'a Node>,
4135        added: &'a [&'a Node],
4136        next: Option<&'a Node>,
4137    ) -> ChildrenMutation<'a> {
4138        match (prev, next) {
4139            (None, None) => ChildrenMutation::ReplaceAll {
4140                removed: &[],
4141                added,
4142            },
4143            (Some(prev), None) => ChildrenMutation::Append { prev, added },
4144            (None, Some(next)) => ChildrenMutation::Prepend { added, next },
4145            (Some(prev), Some(next)) => ChildrenMutation::Insert { prev, added, next },
4146        }
4147    }
4148
4149    fn replace(
4150        prev: Option<&'a Node>,
4151        removed: &'a Option<&'a Node>,
4152        added: &'a [&'a Node],
4153        next: Option<&'a Node>,
4154    ) -> ChildrenMutation<'a> {
4155        if let Some(ref removed) = *removed {
4156            if let (None, None) = (prev, next) {
4157                ChildrenMutation::ReplaceAll {
4158                    removed: from_ref(removed),
4159                    added,
4160                }
4161            } else {
4162                ChildrenMutation::Replace {
4163                    prev,
4164                    removed,
4165                    added,
4166                    next,
4167                }
4168            }
4169        } else {
4170            ChildrenMutation::insert(prev, added, next)
4171        }
4172    }
4173
4174    fn replace_all(removed: &'a [&'a Node], added: &'a [&'a Node]) -> ChildrenMutation<'a> {
4175        ChildrenMutation::ReplaceAll { removed, added }
4176    }
4177
4178    /// Get the child that follows the added or removed children.
4179    /// Currently only used when this mutation might force us to
4180    /// restyle later children (see HAS_SLOW_SELECTOR_LATER_SIBLINGS and
4181    /// Element's implementation of VirtualMethods::children_changed).
4182    pub(crate) fn next_child(&self) -> Option<&Node> {
4183        match *self {
4184            ChildrenMutation::Append { .. } => None,
4185            ChildrenMutation::Insert { next, .. } => Some(next),
4186            ChildrenMutation::Prepend { next, .. } => Some(next),
4187            ChildrenMutation::Replace { next, .. } => next,
4188            ChildrenMutation::ReplaceAll { .. } => None,
4189            ChildrenMutation::ChangeText => None,
4190        }
4191    }
4192
4193    /// If nodes were added or removed at the start or end of a container, return any
4194    /// previously-existing child whose ":first-child" or ":last-child" status *may* have changed.
4195    ///
4196    /// NOTE: This does not check whether the inserted/removed nodes were elements, so in some
4197    /// cases it will return a false positive.  This doesn't matter for correctness, because at
4198    /// worst the returned element will be restyled unnecessarily.
4199    pub(crate) fn modified_edge_element(&self) -> Option<DomRoot<Node>> {
4200        match *self {
4201            // Add/remove at start of container: Return the first following element.
4202            ChildrenMutation::Prepend { next, .. } |
4203            ChildrenMutation::Replace {
4204                prev: None,
4205                next: Some(next),
4206                ..
4207            } => next
4208                .inclusively_following_siblings()
4209                .find(|node| node.is::<Element>()),
4210            // Add/remove at end of container: Return the last preceding element.
4211            ChildrenMutation::Append { prev, .. } |
4212            ChildrenMutation::Replace {
4213                prev: Some(prev),
4214                next: None,
4215                ..
4216            } => prev
4217                .inclusively_preceding_siblings()
4218                .find(|node| node.is::<Element>()),
4219            // Insert or replace in the middle:
4220            ChildrenMutation::Insert { prev, next, .. } |
4221            ChildrenMutation::Replace {
4222                prev: Some(prev),
4223                next: Some(next),
4224                ..
4225            } => {
4226                if prev
4227                    .inclusively_preceding_siblings()
4228                    .all(|node| !node.is::<Element>())
4229                {
4230                    // Before the first element: Return the first following element.
4231                    next.inclusively_following_siblings()
4232                        .find(|node| node.is::<Element>())
4233                } else if next
4234                    .inclusively_following_siblings()
4235                    .all(|node| !node.is::<Element>())
4236                {
4237                    // After the last element: Return the last preceding element.
4238                    prev.inclusively_preceding_siblings()
4239                        .find(|node| node.is::<Element>())
4240                } else {
4241                    None
4242                }
4243            },
4244
4245            ChildrenMutation::Replace {
4246                prev: None,
4247                next: None,
4248                ..
4249            } => unreachable!(),
4250            ChildrenMutation::ReplaceAll { .. } => None,
4251            ChildrenMutation::ChangeText => None,
4252        }
4253    }
4254}
4255
4256/// The context of the binding to tree of a node.
4257pub(crate) struct BindContext {
4258    /// Whether the tree is connected.
4259    ///
4260    /// <https://dom.spec.whatwg.org/#connected>
4261    pub(crate) tree_connected: bool,
4262
4263    /// Whether the tree's root is a document.
4264    ///
4265    /// <https://dom.spec.whatwg.org/#in-a-document-tree>
4266    pub(crate) tree_is_in_a_document_tree: bool,
4267
4268    /// Whether the tree's root is a shadow root
4269    pub(crate) tree_is_in_a_shadow_tree: bool,
4270}
4271
4272impl BindContext {
4273    /// Return true iff the tree is inside either a document- or a shadow tree.
4274    pub(crate) fn is_in_tree(&self) -> bool {
4275        self.tree_is_in_a_document_tree || self.tree_is_in_a_shadow_tree
4276    }
4277}
4278
4279/// The context of the unbinding from a tree of a node when one of its
4280/// inclusive ancestors is removed.
4281pub(crate) struct UnbindContext<'a> {
4282    /// The index of the inclusive ancestor that was removed.
4283    index: Cell<Option<u32>>,
4284    /// The parent of the inclusive ancestor that was removed.
4285    pub(crate) parent: &'a Node,
4286    /// The previous sibling of the inclusive ancestor that was removed.
4287    prev_sibling: Option<&'a Node>,
4288    /// The next sibling of the inclusive ancestor that was removed.
4289    pub(crate) next_sibling: Option<&'a Node>,
4290
4291    /// Whether the tree is connected.
4292    ///
4293    /// <https://dom.spec.whatwg.org/#connected>
4294    pub(crate) tree_connected: bool,
4295
4296    /// Whether the tree's root is a document.
4297    ///
4298    /// <https://dom.spec.whatwg.org/#in-a-document-tree>
4299    pub(crate) tree_is_in_a_document_tree: bool,
4300
4301    /// Whether the tree's root is a shadow root
4302    pub(crate) tree_is_in_a_shadow_tree: bool,
4303}
4304
4305impl<'a> UnbindContext<'a> {
4306    /// Create a new `UnbindContext` value.
4307    pub(crate) fn new(
4308        parent: &'a Node,
4309        prev_sibling: Option<&'a Node>,
4310        next_sibling: Option<&'a Node>,
4311        cached_index: Option<u32>,
4312    ) -> Self {
4313        UnbindContext {
4314            index: Cell::new(cached_index),
4315            parent,
4316            prev_sibling,
4317            next_sibling,
4318            tree_connected: parent.is_connected(),
4319            tree_is_in_a_document_tree: parent.is_in_a_document_tree(),
4320            tree_is_in_a_shadow_tree: parent.is_in_a_shadow_tree(),
4321        }
4322    }
4323
4324    /// The index of the inclusive ancestor that was removed from the tree.
4325    #[allow(unsafe_code)]
4326    pub(crate) fn index(&self) -> u32 {
4327        if let Some(index) = self.index.get() {
4328            return index;
4329        }
4330        let index = self.prev_sibling.map_or(0, |sibling| sibling.index() + 1);
4331        self.index.set(Some(index));
4332        index
4333    }
4334}
4335
4336/// A node's unique ID, for devtools.
4337pub(crate) struct UniqueId {
4338    cell: UnsafeCell<Option<Box<Uuid>>>,
4339}
4340
4341unsafe_no_jsmanaged_fields!(UniqueId);
4342
4343impl MallocSizeOf for UniqueId {
4344    #[allow(unsafe_code)]
4345    fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
4346        if let Some(uuid) = unsafe { &*self.cell.get() } {
4347            unsafe { ops.malloc_size_of(&**uuid) }
4348        } else {
4349            0
4350        }
4351    }
4352}
4353
4354impl UniqueId {
4355    /// Create a new `UniqueId` value. The underlying `Uuid` is lazily created.
4356    fn new() -> UniqueId {
4357        UniqueId {
4358            cell: UnsafeCell::new(None),
4359        }
4360    }
4361
4362    /// The Uuid of that unique ID.
4363    #[allow(unsafe_code)]
4364    fn borrow(&self) -> &Uuid {
4365        unsafe {
4366            let ptr = self.cell.get();
4367            if (*ptr).is_none() {
4368                *ptr = Some(Box::new(Uuid::new_v4()));
4369            }
4370            (*ptr).as_ref().unwrap()
4371        }
4372    }
4373}
4374
4375pub(crate) struct NodeTypeIdWrapper(pub(crate) NodeTypeId);
4376
4377impl From<NodeTypeIdWrapper> for LayoutNodeType {
4378    #[inline(always)]
4379    fn from(node_type: NodeTypeIdWrapper) -> LayoutNodeType {
4380        match node_type.0 {
4381            NodeTypeId::Element(e) => LayoutNodeType::Element(ElementTypeIdWrapper(e).into()),
4382            NodeTypeId::CharacterData(CharacterDataTypeId::Text(_)) => LayoutNodeType::Text,
4383            x => unreachable!("Layout should not traverse nodes of type {:?}", x),
4384        }
4385    }
4386}
4387
4388struct ElementTypeIdWrapper(ElementTypeId);
4389
4390impl From<ElementTypeIdWrapper> for LayoutElementType {
4391    #[inline(always)]
4392    fn from(element_type: ElementTypeIdWrapper) -> LayoutElementType {
4393        match element_type.0 {
4394            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLBodyElement) => {
4395                LayoutElementType::HTMLBodyElement
4396            },
4397            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLBRElement) => {
4398                LayoutElementType::HTMLBRElement
4399            },
4400            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLCanvasElement) => {
4401                LayoutElementType::HTMLCanvasElement
4402            },
4403            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLHtmlElement) => {
4404                LayoutElementType::HTMLHtmlElement
4405            },
4406            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLIFrameElement) => {
4407                LayoutElementType::HTMLIFrameElement
4408            },
4409            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLImageElement) => {
4410                LayoutElementType::HTMLImageElement
4411            },
4412            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLMediaElement(_)) => {
4413                LayoutElementType::HTMLMediaElement
4414            },
4415            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLInputElement) => {
4416                LayoutElementType::HTMLInputElement
4417            },
4418            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLOptGroupElement) => {
4419                LayoutElementType::HTMLOptGroupElement
4420            },
4421            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLOptionElement) => {
4422                LayoutElementType::HTMLOptionElement
4423            },
4424            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLObjectElement) => {
4425                LayoutElementType::HTMLObjectElement
4426            },
4427            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLParagraphElement) => {
4428                LayoutElementType::HTMLParagraphElement
4429            },
4430            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLPreElement) => {
4431                LayoutElementType::HTMLPreElement
4432            },
4433            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLSelectElement) => {
4434                LayoutElementType::HTMLSelectElement
4435            },
4436            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTableCellElement) => {
4437                LayoutElementType::HTMLTableCellElement
4438            },
4439            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTableColElement) => {
4440                LayoutElementType::HTMLTableColElement
4441            },
4442            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTableElement) => {
4443                LayoutElementType::HTMLTableElement
4444            },
4445            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTableRowElement) => {
4446                LayoutElementType::HTMLTableRowElement
4447            },
4448            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTableSectionElement) => {
4449                LayoutElementType::HTMLTableSectionElement
4450            },
4451            ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLTextAreaElement) => {
4452                LayoutElementType::HTMLTextAreaElement
4453            },
4454            ElementTypeId::SVGElement(SVGElementTypeId::SVGGraphicsElement(
4455                SVGGraphicsElementTypeId::SVGImageElement,
4456            )) => LayoutElementType::SVGImageElement,
4457            ElementTypeId::SVGElement(SVGElementTypeId::SVGGraphicsElement(
4458                SVGGraphicsElementTypeId::SVGSVGElement,
4459            )) => LayoutElementType::SVGSVGElement,
4460            _ => LayoutElementType::Element,
4461        }
4462    }
4463}
4464
4465/// Helper trait to insert an element into vector whose elements
4466/// are maintained in tree order
4467pub(crate) trait VecPreOrderInsertionHelper<T> {
4468    fn insert_pre_order(&mut self, elem: &T, tree_root: &Node);
4469}
4470
4471impl<T> VecPreOrderInsertionHelper<T> for Vec<Dom<T>>
4472where
4473    T: DerivedFrom<Node> + DomObject,
4474{
4475    /// This algorithm relies on the following assumptions:
4476    /// * any elements inserted in this vector share the same tree root
4477    /// * any time an element is removed from the tree root, it is also removed from this array
4478    /// * any time an element is moved within the tree, it is removed from this array and re-inserted
4479    ///
4480    /// Under these assumptions, an element's tree-order position in this array can be determined by
4481    /// performing a [preorder traversal](https://dom.spec.whatwg.org/#concept-tree-order) of the tree root's children,
4482    /// and increasing the destination index in the array every time a node in the array is encountered during
4483    /// the traversal.
4484    fn insert_pre_order(&mut self, elem: &T, tree_root: &Node) {
4485        if self.is_empty() {
4486            self.push(Dom::from_ref(elem));
4487            return;
4488        }
4489
4490        let elem_node = elem.upcast::<Node>();
4491        let mut head: usize = 0;
4492        for node in tree_root.traverse_preorder(ShadowIncluding::No) {
4493            let head_node = DomRoot::upcast::<Node>(DomRoot::from_ref(&*self[head]));
4494            if head_node == node {
4495                head += 1;
4496            }
4497            if elem_node == &*node || head == self.len() {
4498                break;
4499            }
4500        }
4501        self.insert(head, Dom::from_ref(elem));
4502    }
4503}