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

script/dom/node/
iterators.rs
