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::{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) type UnrootedAncestorIterator<'no_gc> = UnrootedSimpleNodeIterator<
323    'no_gc,
324    fn(&Node, &'no_gc NoGC) -> Option<UnrootedDom<'no_gc, Node>>,
325>;
326
327pub(crate) struct TreeIterator {
328    current: Option<DomRoot<Node>>,
329    depth: usize,
330    shadow_including: ShadowIncluding,
331}
332
333impl TreeIterator {
334    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding) -> TreeIterator {
335        TreeIterator {
336            current: Some(DomRoot::from_ref(root)),
337            depth: 0,
338            shadow_including,
339        }
340    }
341
342    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
343        let current = self.current.take()?;
344
345        self.next_skipping_children_impl(current)
346    }
347
348    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
349        let iter = current.inclusive_ancestors(self.shadow_including);
350
351        for ancestor in iter {
352            if self.depth == 0 {
353                break;
354            }
355            if let Some(next_sibling) = ancestor.GetNextSibling() {
356                self.current = Some(next_sibling);
357                return Some(current);
358            }
359            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
360                // Shadow roots don't have sibling, so after we're done traversing
361                // one we jump to the first child of the host
362                if let Some(child) = shadow_root.Host().upcast::<Node>().GetFirstChild() {
363                    self.current = Some(child);
364                    return Some(current);
365                }
366            }
367            self.depth -= 1;
368        }
369        debug_assert_eq!(self.depth, 0);
370        self.current = None;
371        Some(current)
372    }
373
374    pub(crate) fn peek(&self) -> Option<&DomRoot<Node>> {
375        self.current.as_ref()
376    }
377}
378
379impl Iterator for TreeIterator {
380    type Item = DomRoot<Node>;
381
382    /// <https://dom.spec.whatwg.org/#concept-tree-order>
383    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
384    fn next(&mut self) -> Option<DomRoot<Node>> {
385        let current = self.current.take()?;
386
387        // Handle a potential shadow root on the element
388        if let Some(element) = current.downcast::<Element>() &&
389            let Some(shadow_root) = element.shadow_root() &&
390            self.shadow_including == ShadowIncluding::Yes
391        {
392            self.current = Some(DomRoot::from_ref(shadow_root.upcast::<Node>()));
393            self.depth += 1;
394            return Some(current);
395        }
396
397        if let Some(first_child) = current.GetFirstChild() {
398            self.current = Some(first_child);
399            self.depth += 1;
400            return Some(current);
401        };
402
403        self.next_skipping_children_impl(current)
404    }
405}
406
407/// An efficient TreeIterator because it skips rooting if there are no GC pauses.
408///
409/// Use this if you have a `&JSContext` or `NoGC`.
410///
411/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
412/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
413/// while this iterator is alive.
414#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
415pub(crate) struct UnrootedTreeIterator<'b> {
416    current: Option<UnrootedDom<'b, Node>>,
417    depth: usize,
418    shadow_including: ShadowIncluding,
419    /// This is unused and only used for lifetime guarantee of NoGC
420    no_gc: &'b NoGC,
421}
422
423impl<'b> UnrootedTreeIterator<'b> {
424    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding, no_gc: &'b NoGC) -> Self {
425        Self {
426            current: Some(UnrootedDom::from_ref(root, no_gc)),
427            depth: 0,
428            shadow_including,
429            no_gc,
430        }
431    }
432
433    pub(crate) fn next_skipping_children(&mut self) -> Option<UnrootedDom<'b, Node>> {
434        let current = self.current.take()?;
435
436        let iter = current.inclusive_ancestors_unrooted(self.no_gc, self.shadow_including);
437
438        for ancestor in iter {
439            if self.depth == 0 {
440                break;
441            }
442
443            let next_sibling_option = ancestor.get_next_sibling_unrooted(self.no_gc);
444
445            if let Some(next_sibling) = next_sibling_option {
446                self.current = Some(next_sibling);
447                return Some(current);
448            }
449
450            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
451                // Shadow roots don't have sibling, so after we're done traversing
452                // one we jump to the first child of the host
453                let child_option = shadow_root
454                    .host_unrooted(self.no_gc)
455                    .upcast::<Node>()
456                    .get_first_child_unrooted(self.no_gc);
457
458                if let Some(child) = child_option {
459                    self.current = Some(child);
460                    return Some(current);
461                }
462            }
463            self.depth -= 1;
464        }
465        debug_assert_eq!(self.depth, 0);
466        self.current = None;
467        Some(current)
468    }
469}
470
471impl<'b> Iterator for UnrootedTreeIterator<'b> {
472    type Item = UnrootedDom<'b, Node>;
473
474    /// <https://dom.spec.whatwg.org/#concept-tree-order>
475    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
476    fn next(&mut self) -> Option<Self::Item> {
477        let current = self.current.take()?;
478
479        // Handle a potential shadow root on the element
480        if let Some(element) = current.downcast::<Element>() &&
481            let Some(shadow_root) = element.shadow_root_unrooted(self.no_gc) &&
482            self.shadow_including == ShadowIncluding::Yes
483        {
484            self.current = Some(UnrootedDom::upcast(shadow_root));
485            self.depth += 1;
486            return Some(current);
487        }
488
489        let first_child_option = current.get_first_child_unrooted(self.no_gc);
490        if let Some(first_child) = first_child_option {
491            self.current = Some(first_child);
492            self.depth += 1;
493            return Some(current);
494        };
495
496        // Restore `self.current` emptied by `.take()`
497        self.current = Some(current);
498        self.next_skipping_children()
499    }
500}
501
502/// An `Item` in an traversal that is both pre-order and post-order. Each iteration
503/// of the traversal is either an record of entering a node or a leaving a node during
504/// the course of traversal.
505#[derive(Clone)]
506pub(crate) enum PrePostIteration<T: Clone> {
507    /// The traversal encountered this node for the first time. This happens before
508    /// traversing the node's descendants.
509    Enter(T),
510    /// The traversal is leaving this node. This happens after traversing the node's
511    /// descendants.
512    Leave(T),
513}
514
515/// A traversal of a [`Document`]'s [flat tree]. This is both a pre-order and post-order
516/// unrooted traversal. This means that an item is returned both when encountering a node
517/// for the first time and when leaving a node. In addition, no garbage collection can
518/// happen while iterating, allowing returning unrooted values for performance reasons.
519///
520/// [flat tree]: https://drafts.csswg.org/css-shadow-1/#flat-tree
521#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
522pub(crate) struct UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
523    start: UnrootedDom<'no_gc, Node>,
524    previously_returned_item: Option<PrePostIteration<UnrootedDom<'no_gc, Node>>>,
525    no_gc: &'no_gc NoGC,
526}
527
528impl<'no_gc> UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
529    pub(crate) fn new(root: &Node, no_gc: &'no_gc NoGC) -> Self {
530        Self {
531            start: UnrootedDom::from_ref(root, no_gc),
532            previously_returned_item: None,
533            no_gc,
534        }
535    }
536
537    pub(crate) fn next_skipping_subtree(
538        &mut self,
539    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
540        let next = self.find_next_skipping_subtree()?;
541        self.previously_returned_item = Some(next);
542        self.previously_returned_item.clone()
543    }
544
545    fn find_next_skipping_subtree(
546        &mut self,
547    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
548        match &self.previously_returned_item {
549            None => Some(PrePostIteration::Leave(self.start.clone())),
550            Some(PrePostIteration::Enter(previous)) => {
551                Some(PrePostIteration::Leave(previous.clone()))
552            },
553            Some(PrePostIteration::Leave(previous)) => {
554                Self::find_next_after_post(self.no_gc, previous)
555            },
556        }
557    }
558
559    fn find_next_after_post(
560        no_gc: &'no_gc NoGC,
561        previous: &UnrootedDom<'no_gc, Node>,
562    ) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
563        if let Some(next_sibling) = previous.next_flat_tree_sibling_unrooted(no_gc) {
564            return Some(PrePostIteration::Enter(next_sibling));
565        }
566        match previous.parent_in_flat_tree(no_gc) {
567            FlatTreeParent::Parent(parent_node) => Some(PrePostIteration::Leave(parent_node)),
568            FlatTreeParent::NotInFlatTree => None,
569            FlatTreeParent::RootNode => None,
570        }
571    }
572
573    fn find_next(&mut self) -> Option<PrePostIteration<UnrootedDom<'no_gc, Node>>> {
574        match &self.previously_returned_item {
575            None => Some(PrePostIteration::Enter(self.start.clone())),
576            Some(PrePostIteration::Enter(previous)) => {
577                if let Some(first_child) = previous.first_flat_tree_child_unrooted(self.no_gc) {
578                    return Some(PrePostIteration::Enter(first_child));
579                }
580                Some(PrePostIteration::Leave(previous.clone()))
581            },
582            Some(PrePostIteration::Leave(previous)) => {
583                Self::find_next_after_post(self.no_gc, previous)
584            },
585        }
586    }
587}
588
589impl<'no_gc> Iterator for UnrootedFollowingFlatTreeNodesTraversal<'no_gc> {
590    type Item = PrePostIteration<UnrootedDom<'no_gc, Node>>;
591
592    fn next(&mut self) -> Option<Self::Item> {
593        let next = self.find_next()?;
594        self.previously_returned_item = Some(next);
595        self.previously_returned_item.clone()
596    }
597}
script/dom/node/iterators.rs

script/dom/node/
iterators.rs
