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 crate::dom::Node;
8use crate::dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
9use crate::dom::bindings::codegen::Bindings::ShadowRootBinding::ShadowRoot_Binding::ShadowRootMethods;
10use crate::dom::bindings::inheritance::Castable;
11use crate::dom::bindings::root::{Dom, DomRoot, UnrootedDom};
12use crate::dom::element::Element;
13use crate::dom::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(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) struct TreeIterator {
322    current: Option<DomRoot<Node>>,
323    depth: usize,
324    shadow_including: ShadowIncluding,
325}
326
327impl TreeIterator {
328    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding) -> TreeIterator {
329        TreeIterator {
330            current: Some(DomRoot::from_ref(root)),
331            depth: 0,
332            shadow_including,
333        }
334    }
335
336    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
337        let current = self.current.take()?;
338
339        self.next_skipping_children_impl(current)
340    }
341
342    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
343        let iter = current.inclusive_ancestors(self.shadow_including);
344
345        for ancestor in iter {
346            if self.depth == 0 {
347                break;
348            }
349            if let Some(next_sibling) = ancestor.GetNextSibling() {
350                self.current = Some(next_sibling);
351                return Some(current);
352            }
353            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
354                // Shadow roots don't have sibling, so after we're done traversing
355                // one we jump to the first child of the host
356                if let Some(child) = shadow_root.Host().upcast::<Node>().GetFirstChild() {
357                    self.current = Some(child);
358                    return Some(current);
359                }
360            }
361            self.depth -= 1;
362        }
363        debug_assert_eq!(self.depth, 0);
364        self.current = None;
365        Some(current)
366    }
367
368    pub(crate) fn peek(&self) -> Option<&DomRoot<Node>> {
369        self.current.as_ref()
370    }
371}
372
373impl Iterator for TreeIterator {
374    type Item = DomRoot<Node>;
375
376    /// <https://dom.spec.whatwg.org/#concept-tree-order>
377    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
378    fn next(&mut self) -> Option<DomRoot<Node>> {
379        let current = self.current.take()?;
380
381        // Handle a potential shadow root on the element
382        if let Some(element) = current.downcast::<Element>() &&
383            let Some(shadow_root) = element.shadow_root() &&
384            self.shadow_including == ShadowIncluding::Yes
385        {
386            self.current = Some(DomRoot::from_ref(shadow_root.upcast::<Node>()));
387            self.depth += 1;
388            return Some(current);
389        }
390
391        if let Some(first_child) = current.GetFirstChild() {
392            self.current = Some(first_child);
393            self.depth += 1;
394            return Some(current);
395        };
396
397        self.next_skipping_children_impl(current)
398    }
399}
400
401/// An efficient TreeIterator because it skips rooting if there are no GC pauses.
402///
403/// Use this if you have a `&JSContext` or `NoGC`.
404///
405/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
406/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
407/// while this iterator is alive.
408#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
409pub(crate) struct UnrootedTreeIterator<'b> {
410    current: Option<UnrootedDom<'b, Node>>,
411    depth: usize,
412    shadow_including: ShadowIncluding,
413    /// This is unused and only used for lifetime guarantee of NoGC
414    no_gc: &'b NoGC,
415}
416
417impl<'b> UnrootedTreeIterator<'b> {
418    pub(crate) fn new(
419        root: &Node,
420        shadow_including: ShadowIncluding,
421        no_gc: &'b NoGC,
422    ) -> UnrootedTreeIterator<'b> {
423        UnrootedTreeIterator {
424            current: Some(UnrootedDom::from_dom(Dom::from_ref(root), no_gc)),
425            depth: 0,
426            shadow_including,
427            no_gc,
428        }
429    }
430
431    pub(crate) fn next_skipping_children(&mut self) -> Option<UnrootedDom<'b, Node>> {
432        let current = self.current.take()?;
433
434        let iter = current.inclusive_ancestors(self.shadow_including);
435
436        for ancestor in iter {
437            if self.depth == 0 {
438                break;
439            }
440
441            let next_sibling_option = ancestor.get_next_sibling_unrooted(self.no_gc);
442
443            if let Some(next_sibling) = next_sibling_option {
444                self.current = Some(next_sibling);
445                return Some(current);
446            }
447
448            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
449                // Shadow roots don't have sibling, so after we're done traversing
450                // one we jump to the first child of the host
451                let child_option = shadow_root
452                    .Host()
453                    .upcast::<Node>()
454                    .get_first_child_unrooted(self.no_gc);
455
456                if let Some(child) = child_option {
457                    self.current = Some(child);
458                    return Some(current);
459                }
460            }
461            self.depth -= 1;
462        }
463        debug_assert_eq!(self.depth, 0);
464        self.current = None;
465        Some(current)
466    }
467}
468
469impl<'b> Iterator for UnrootedTreeIterator<'b> {
470    type Item = UnrootedDom<'b, Node>;
471
472    /// <https://dom.spec.whatwg.org/#concept-tree-order>
473    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
474    fn next(&mut self) -> Option<UnrootedDom<'b, Node>> {
475        let current = self.current.take()?;
476
477        // Handle a potential shadow root on the element
478        if let Some(element) = current.downcast::<Element>() &&
479            let Some(shadow_root) = element.shadow_root() &&
480            self.shadow_including == ShadowIncluding::Yes
481        {
482            self.current = Some(UnrootedDom::from_dom(
483                Dom::from_ref(shadow_root.upcast::<Node>()),
484                self.no_gc,
485            ));
486            self.depth += 1;
487            return Some(current);
488        }
489
490        let first_child_option = current.get_first_child_unrooted(self.no_gc);
491        if let Some(first_child) = first_child_option {
492            self.current = Some(first_child);
493            self.depth += 1;
494            return Some(current);
495        };
496
497        // current is empty.
498        let _ = self.current.insert(current);
499        self.next_skipping_children()
500    }
501}
script/dom/node/iterators.rs

script/dom/node/
iterators.rs
