script/dom/node/
iterators.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
5use js::context::NoGC;
6
7use super::FlatTreeParent;
8use crate::dom::Node;
9use crate::dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
10use crate::dom::bindings::inheritance::Castable;
11use crate::dom::bindings::root::{DomRoot, UnrootedDom};
12use crate::dom::element::Element;
13use crate::dom::shadowroot::shadowroot::ShadowRoot;
14
15/// Whether a tree traversal should pass shadow tree boundaries.
16#[derive(Clone, Copy, PartialEq)]
17pub(crate) enum ShadowIncluding {
18    No,
19    Yes,
20}
21
22pub(crate) struct FollowingNodeIterator {
23    current: Option<DomRoot<Node>>,
24    root: DomRoot<Node>,
25    shadow_including: ShadowIncluding,
26}
27
28impl FollowingNodeIterator {
29    pub(crate) fn new(
30        current: Option<DomRoot<Node>>,
31        root: DomRoot<Node>,
32        shadow_including: ShadowIncluding,
33    ) -> Self {
34        FollowingNodeIterator {
35            current,
36            root,
37            shadow_including,
38        }
39    }
40}
41
42impl FollowingNodeIterator {
43    /// Skips iterating the children of the current node
44    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
45        let current = self.current.take()?;
46        self.next_skipping_children_impl(current)
47    }
48
49    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
50        if self.root == current {
51            self.current = None;
52            return None;
53        }
54
55        if let Some(next_sibling) = current.GetNextSibling() {
56            self.current = Some(next_sibling);
57            return current.GetNextSibling();
58        }
59
60        for ancestor in current.inclusive_ancestors(self.shadow_including) {
61            if self.root == ancestor {
62                break;
63            }
64            if let Some(next_sibling) = ancestor.GetNextSibling() {
65                self.current = Some(next_sibling);
66                return ancestor.GetNextSibling();
67            }
68        }
69        self.current = None;
70        None
71    }
72}
73
74impl Iterator for FollowingNodeIterator {
75    type Item = DomRoot<Node>;
76
77    /// <https://dom.spec.whatwg.org/#concept-tree-following>
78    fn next(&mut self) -> Option<DomRoot<Node>> {
79        let current = self.current.take()?;
80
81        if let Some(first_child) = current.GetFirstChild() {
82            self.current = Some(first_child);
83            return current.GetFirstChild();
84        }
85
86        self.next_skipping_children_impl(current)
87    }
88}
89
90pub(crate) struct UnrootedFollowingNodeIterator<'b> {
91    current: Option<UnrootedDom<'b, Node>>,
92    root: UnrootedDom<'b, Node>,
93    shadow_including: ShadowIncluding,
94    no_gc: &'b NoGC,
95}
96
97impl<'b> UnrootedFollowingNodeIterator<'b> {
98    pub(crate) fn new(
99        current: Option<UnrootedDom<'b, Node>>,
100        root: UnrootedDom<'b, Node>,
101        shadow_including: ShadowIncluding,
102        no_gc: &'b NoGC,
103    ) -> Self {
104        UnrootedFollowingNodeIterator {
105            current,
106            root,
107            shadow_including,
108            no_gc,
109        }
110    }
111}
112
113impl<'b> UnrootedFollowingNodeIterator<'b> {
114    fn next_skipping_children_impl(
115        &mut self,
116        current: UnrootedDom<'b, Node>,
117    ) -> Option<UnrootedDom<'b, Node>> {
118        if self.root == current {
119            self.current = None;
120            return None;
121        }
122
123        if let Some(next_sibling) = current.get_next_sibling_unrooted(self.no_gc) {
124            self.current = Some(next_sibling);
125            return current.get_next_sibling_unrooted(self.no_gc);
126        }
127
128        for ancestor in current.inclusive_ancestors_unrooted(self.no_gc, self.shadow_including) {
129            if self.root == ancestor {
130                break;
131            }
132            if let Some(next_sibling) = ancestor.get_next_sibling_unrooted(self.no_gc) {
133                self.current = Some(next_sibling);
134                return ancestor.get_next_sibling_unrooted(self.no_gc);
135            }
136        }
137        self.current = None;
138        None
139    }
140}
141
142impl<'b> Iterator for UnrootedFollowingNodeIterator<'b> {
143    type Item = UnrootedDom<'b, Node>;
144
145    /// <https://dom.spec.whatwg.org/#concept-tree-following>
146    fn next(&mut self) -> Option<UnrootedDom<'b, Node>> {
147        let current = self.current.take()?;
148
149        if let Some(first_child) = current.get_first_child_unrooted(self.no_gc) {
150            self.current = Some(first_child);
151            return current.get_first_child_unrooted(self.no_gc);
152        }
153
154        self.next_skipping_children_impl(current)
155    }
156}
157
158pub(crate) struct PrecedingNodeIterator {
159    current: Option<DomRoot<Node>>,
160    root: DomRoot<Node>,
161}
162
163impl PrecedingNodeIterator {
164    pub(crate) fn new(current: Option<DomRoot<Node>>, root: DomRoot<Node>) -> Self {
165        PrecedingNodeIterator { current, root }
166    }
167}
168
169impl Iterator for PrecedingNodeIterator {
170    type Item = DomRoot<Node>;
171
172    /// <https://dom.spec.whatwg.org/#concept-tree-preceding>
173    fn next(&mut self) -> Option<DomRoot<Node>> {
174        let current = self.current.take()?;
175
176        self.current = if self.root == current {
177            None
178        } else if let Some(previous_sibling) = current.GetPreviousSibling() {
179            if self.root == previous_sibling {
180                None
181            } else if let Some(last_child) = previous_sibling.descending_last_children().last() {
182                Some(last_child)
183            } else {
184                Some(previous_sibling)
185            }
186        } else {
187            current.GetParentNode()
188        };
189        self.current.clone()
190    }
191}
192
193pub(crate) struct UnrootedPrecedingNodeIterator<'b> {
194    current: Option<UnrootedDom<'b, Node>>,
195    no_gc: &'b NoGC,
196    root: UnrootedDom<'b, Node>,
197}
198
199impl<'b> UnrootedPrecedingNodeIterator<'b> {
200    pub(crate) fn new(
201        current: Option<UnrootedDom<'b, Node>>,
202        root: UnrootedDom<'b, Node>,
203        no_gc: &'b NoGC,
204    ) -> Self {
205        UnrootedPrecedingNodeIterator {
206            current,
207            no_gc,
208            root,
209        }
210    }
211}
212
213impl<'b> Iterator for UnrootedPrecedingNodeIterator<'b> {
214    type Item = UnrootedDom<'b, Node>;
215
216    /// <https://dom.spec.whatwg.org/#concept-tree-preceding>
217    fn next(&mut self) -> Option<UnrootedDom<'b, Node>> {
218        let current = self.current.take()?;
219
220        self.current = if self.root == current {
221            None
222        } else if let Some(previous_sibling) = current.get_previous_sibling_unrooted(self.no_gc) {
223            if self.root == previous_sibling {
224                None
225            } else if let Some(last_child) = previous_sibling
226                .descending_last_children_unrooted(self.no_gc)
227                .last()
228            {
229                Some(last_child)
230            } else {
231                Some(previous_sibling)
232            }
233        } else {
234            current.get_parent_node_unrooted(self.no_gc)
235        };
236
237        self.current.clone()
238    }
239}
240
241pub(crate) struct SimpleNodeIterator<I>
242where
243    I: Fn(&Node) -> Option<DomRoot<Node>>,
244{
245    current: Option<DomRoot<Node>>,
246    next_node: I,
247}
248
249impl<I> SimpleNodeIterator<I>
250where
251    I: Fn(&Node) -> Option<DomRoot<Node>>,
252{
253    pub(crate) fn new(current: Option<DomRoot<Node>>, next_node: I) -> Self {
254        SimpleNodeIterator { current, next_node }
255    }
256}
257
258impl<I> Iterator for SimpleNodeIterator<I>
259where
260    I: Fn(&Node) -> Option<DomRoot<Node>>,
261{
262    type Item = DomRoot<Node>;
263
264    fn next(&mut self) -> Option<Self::Item> {
265        let current = self.current.take();
266        self.current = current.as_ref().and_then(|c| (self.next_node)(c));
267        current
268    }
269}
270
271/// An efficient SimpleNodeIterator because it skips rooting if there are no GC pauses.
272///
273/// Use this if you have a `&JSContext` or `NoGC`.
274///
275/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
276/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
277/// while this iterator is alive.
278#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
279pub(crate) struct UnrootedSimpleNodeIterator<'b, I>
280where
281    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
282{
283    current: Option<UnrootedDom<'b, Node>>,
284    next_node: I,
285    /// This is unused and only used for lifetime guarantee of NoGC
286    no_gc: &'b NoGC,
287}
288
289impl<'b, I> UnrootedSimpleNodeIterator<'b, I>
290where
291    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
292{
293    pub(crate) fn new(
294        current: Option<UnrootedDom<'b, Node>>,
295        next_node: I,
296        no_gc: &'b NoGC,
297    ) -> Self {
298        UnrootedSimpleNodeIterator {
299            current,
300            next_node,
301            no_gc,
302        }
303    }
304}
305
306impl<'b, I> Iterator for UnrootedSimpleNodeIterator<'b, I>
307where
308    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
309{
310    type Item = UnrootedDom<'b, Node>;
311
312    fn next(&mut self) -> Option<Self::Item> {
313        let current = self.current.take();
314        self.current = current
315            .as_ref()
316            .and_then(|c| (self.next_node)(c, self.no_gc));
317        current
318    }
319}
320
321pub(crate) type UnrootedAncestorIterator<'no_gc> = UnrootedSimpleNodeIterator<
322    'no_gc,
323    fn(&Node, &'no_gc NoGC) -> Option<UnrootedDom<'no_gc, Node>>,
324>;
325
326/// A data structure that does efficient traversal of a tree used for both [`UnrootedTreeIterator`] and
327/// [`TreeIterator`].
328struct TreeIteratorInner {
329    depth: usize,
330    shadow_including: ShadowIncluding,
331}
332
333impl TreeIteratorInner {
334    fn next_skipping_children<'a>(
335        &mut self,
336        no_gc: &'a NoGC,
337        current: &Node,
338    ) -> Option<UnrootedDom<'a, Node>> {
339        for ancestor in current.inclusive_ancestors_unrooted(no_gc, self.shadow_including) {
340            if self.depth == 0 {
341                break;
342            }
343            if let Some(next_sibling) = ancestor.get_next_sibling_unrooted(no_gc) {
344                return Some(next_sibling);
345            }
346            // Shadow roots don't have sibling, so after we're done traversing one we jump to the
347            // first child of the containing shadow host.
348            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() &&
349                let Some(child) = shadow_root
350                    .host_unrooted(no_gc)
351                    .upcast::<Node>()
352                    .get_first_child_unrooted(no_gc)
353            {
354                return Some(child);
355            }
356
357            self.depth -= 1;
358        }
359        debug_assert_eq!(self.depth, 0);
360        None
361    }
362
363    /// <https://dom.spec.whatwg.org/#concept-tree-order>
364    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
365    fn next<'a>(&mut self, no_gc: &'a NoGC, current: &Node) -> Option<UnrootedDom<'a, Node>> {
366        // Handle a potential shadow root on the element
367        if self.shadow_including == ShadowIncluding::Yes &&
368            let Some(element) = current.downcast::<Element>() &&
369            let Some(shadow_root) = element.shadow_root_unrooted(no_gc)
370        {
371            self.depth += 1;
372            return Some(UnrootedDom::upcast(shadow_root));
373        }
374        if let Some(first_child) = current.get_first_child_unrooted(no_gc) {
375            self.depth += 1;
376            return Some(first_child);
377        }
378        self.next_skipping_children(no_gc, current)
379    }
380}
381
382pub(crate) struct TreeIterator {
383    current: Option<DomRoot<Node>>,
384    inner: TreeIteratorInner,
385}
386
387impl TreeIterator {
388    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding) -> TreeIterator {
389        TreeIterator {
390            current: Some(DomRoot::from_ref(root)),
391            inner: TreeIteratorInner {
392                depth: 0,
393                shadow_including,
394            },
395        }
396    }
397
398    #[expect(unsafe_code)]
399    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
400        // SAFETY: This code *only* walks the DOM tree by reading pointers. It never runs garbage
401        // collection or allocates new garbage collected objects. Normally, we would want to ensure
402        // this via the type system, but since this code is so performance sensitive, we rely on
403        // carefully implementing this here. This `NoGC` should stay local to this method and never
404        // be stored in a longer-lived data structure.
405        let no_gc = unsafe { NoGC::new() };
406        let current = self.current.take()?;
407        self.current = self
408            .inner
409            .next_skipping_children(&no_gc, &current)
410            .map(|node| node.as_rooted());
411        Some(current)
412    }
413
414    pub(crate) fn peek(&self) -> Option<&DomRoot<Node>> {
415        self.current.as_ref()
416    }
417}
418
419impl Iterator for TreeIterator {
420    type Item = DomRoot<Node>;
421
422    #[expect(unsafe_code)]
423    fn next(&mut self) -> Option<DomRoot<Node>> {
424        // SAFETY: This code *only* walks the DOM tree by reading pointers. It never runs garbage
425        // collection or allocates new garbage collected objects. Normally, we would want to ensure
426        // this via the type system, but since this code is so performance sensitive, we rely on
427        // carefully implementing this here. This `NoGC` should stay local to this method and never
428        // be stored in a longer-lived data structure.
429        let no_gc = unsafe { NoGC::new() };
430        let current = self.current.take()?;
431        self.current = self
432            .inner
433            .next(&no_gc, &current)
434            .map(|node| node.as_rooted());
435        Some(current)
436    }
437}
438
439/// An efficient TreeIterator because it skips rooting if there are no GC pauses.
440///
441/// Use this if you have a `&JSContext` or `NoGC`.
442///
443/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
444/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
445/// while this iterator is alive.
446#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
447pub(crate) struct UnrootedTreeIterator<'b> {
448    inner: TreeIteratorInner,
449    current: Option<UnrootedDom<'b, Node>>,
450    no_gc: &'b NoGC,
451}
452
453impl<'b> UnrootedTreeIterator<'b> {
454    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding, no_gc: &'b NoGC) -> Self {
455        Self {
456            inner: TreeIteratorInner {
457                depth: 0,
458                shadow_including,
459            },
460            current: Some(UnrootedDom::from_ref(root, no_gc)),
461            no_gc,
462        }
463    }
464
465    pub(crate) fn next_skipping_children(&mut self) -> Option<UnrootedDom<'b, Node>> {
466        let current = self.current.take()?;
467        self.current = self.inner.next_skipping_children(self.no_gc, &current);
468        Some(current)
469    }
470
471    pub(crate) fn peek(&self) -> Option<&UnrootedDom<'b, Node>> {
472        self.current.as_ref()
473    }
474}
475
476impl<'b> Iterator for UnrootedTreeIterator<'b> {
477    type Item = UnrootedDom<'b, Node>;
478    fn next(&mut self) -> Option<Self::Item> {
479        let current = self.current.take()?;
480        self.current = self.inner.next(self.no_gc, &current);
481        Some(current)
482    }
483}
484
485/// An `Item` in an traversal that is both pre-order and post-order. Each iteration
486/// of the traversal is either an record of entering a node or a leaving a node during
487/// the course of traversal.
488#[derive(Clone)]
489pub(crate) enum PrePostIteration<T: Clone> {
490    /// The traversal encountered this node for the first time. This happens before
491    /// traversing the node's descendants.
492    Enter(T),
493    /// The traversal is leaving this node. This happens after traversing the node's
494    /// descendants.
495    Leave(T),
496}
497
498/// A traversal of a [`Document`]'s [flat tree]. This is both a pre-order and post-order
499/// unrooted traversal. This means that an item is returned both when encountering a node
500/// for the first time and when leaving a node. In addition, no garbage collection can
501/// happen while iterating, allowing returning unrooted values for performance reasons.
502///
503/// [flat tree]: https://drafts.csswg.org/css-shadow-1/#flat-tree
504#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
505pub(crate) struct UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
506    start: UnrootedDom<'no_gc, Node>,
507    previously_returned_item: Option<PrePostIteration<UnrootedDom<'no_gc, Node>>>,
508    no_gc: &'no_gc NoGC,
509}
510
511impl<'no_gc> UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
512    pub(crate) fn new(root: &Node, no_gc: &'no_gc NoGC) -> Self {
513        Self {
514            start: UnrootedDom::from_ref(root, no_gc),
515            previously_returned_item: None,
516            no_gc,
517        }
518    }
519
520    pub(crate) fn next_skipping_subtree(
521        &mut self,
522    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
523        let next = self.find_next_skipping_subtree()?;
524        self.previously_returned_item = Some(next);
525        self.previously_returned_item.clone()
526    }
527
528    fn find_next_skipping_subtree(
529        &mut self,
530    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
531        match &self.previously_returned_item {
532            None => Some(PrePostIteration::Leave(self.start.clone())),
533            Some(PrePostIteration::Enter(previous)) => {
534                Some(PrePostIteration::Leave(previous.clone()))
535            },
536            Some(PrePostIteration::Leave(previous)) => {
537                Self::find_next_after_post(self.no_gc, previous)
538            },
539        }
540    }
541
542    fn find_next_after_post(
543        no_gc: &'no_gc NoGC,
544        previous: &UnrootedDom<'no_gc, Node>,
545    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
546        if let Some(next_sibling) = previous.next_flat_tree_sibling_unrooted(no_gc) {
547            return Some(PrePostIteration::Enter(next_sibling));
548        }
549        match previous.parent_in_flat_tree(no_gc) {
550            FlatTreeParent::Parent(parent_node) => Some(PrePostIteration::Leave(parent_node)),
551            FlatTreeParent::NotInFlatTree => None,
552            FlatTreeParent::RootNode => None,
553        }
554    }
555
556    fn find_next(&mut self) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
557        match &self.previously_returned_item {
558            None => Some(PrePostIteration::Enter(self.start.clone())),
559            Some(PrePostIteration::Enter(previous)) => {
560                if let Some(first_child) = previous.first_flat_tree_child_unrooted(self.no_gc) {
561                    return Some(PrePostIteration::Enter(first_child));
562                }
563                Some(PrePostIteration::Leave(previous.clone()))
564            },
565            Some(PrePostIteration::Leave(previous)) => {
566                Self::find_next_after_post(self.no_gc, previous)
567            },
568        }
569    }
570}
571
572impl<'no_gc> Iterator for UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
573    type Item = PrePostIteration<UnrootedDom<'no_gc, Node>>;
574
575    fn next(&mut self) -> Option<Self::Item> {
576        let next = self.find_next()?;
577        self.previously_returned_item = Some(next);
578        self.previously_returned_item.clone()
579    }
580}
script/dom/node/iterators.rs

script/dom/node/
iterators.rs
