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 std::marker::PhantomData;
6
7use js::context::NoGC;
8
9use crate::dom::Node;
10use crate::dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
11use crate::dom::bindings::codegen::Bindings::ShadowRootBinding::ShadowRoot_Binding::ShadowRootMethods;
12use crate::dom::bindings::inheritance::Castable;
13use crate::dom::bindings::root::{Dom, DomRoot, UnrootedDom};
14use crate::dom::element::Element;
15use crate::dom::shadowroot::ShadowRoot;
16
17/// Whether a tree traversal should pass shadow tree boundaries.
18#[derive(Clone, Copy, PartialEq)]
19pub(crate) enum ShadowIncluding {
20    No,
21    Yes,
22}
23
24pub(crate) struct FollowingNodeIterator {
25    current: Option<DomRoot<Node>>,
26    root: DomRoot<Node>,
27    shadow_including: ShadowIncluding,
28}
29
30impl FollowingNodeIterator {
31    pub(crate) fn new(
32        current: Option<DomRoot<Node>>,
33        root: DomRoot<Node>,
34        shadow_including: ShadowIncluding,
35    ) -> Self {
36        FollowingNodeIterator {
37            current,
38            root,
39            shadow_including,
40        }
41    }
42}
43
44impl FollowingNodeIterator {
45    /// Skips iterating the children of the current node
46    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
47        let current = self.current.take()?;
48        self.next_skipping_children_impl(current)
49    }
50
51    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
52        if self.root == current {
53            self.current = None;
54            return None;
55        }
56
57        if let Some(next_sibling) = current.GetNextSibling() {
58            self.current = Some(next_sibling);
59            return current.GetNextSibling();
60        }
61
62        for ancestor in current.inclusive_ancestors(self.shadow_including) {
63            if self.root == ancestor {
64                break;
65            }
66            if let Some(next_sibling) = ancestor.GetNextSibling() {
67                self.current = Some(next_sibling);
68                return ancestor.GetNextSibling();
69            }
70        }
71        self.current = None;
72        None
73    }
74}
75
76impl Iterator for FollowingNodeIterator {
77    type Item = DomRoot<Node>;
78
79    /// <https://dom.spec.whatwg.org/#concept-tree-following>
80    fn next(&mut self) -> Option<DomRoot<Node>> {
81        let current = self.current.take()?;
82
83        if let Some(first_child) = current.GetFirstChild() {
84            self.current = Some(first_child);
85            return current.GetFirstChild();
86        }
87
88        self.next_skipping_children_impl(current)
89    }
90}
91
92pub(crate) struct PrecedingNodeIterator {
93    current: Option<DomRoot<Node>>,
94    root: DomRoot<Node>,
95}
96
97impl PrecedingNodeIterator {
98    pub(crate) fn new(current: Option<DomRoot<Node>>, root: DomRoot<Node>) -> Self {
99        PrecedingNodeIterator { current, root }
100    }
101}
102
103impl Iterator for PrecedingNodeIterator {
104    type Item = DomRoot<Node>;
105
106    /// <https://dom.spec.whatwg.org/#concept-tree-preceding>
107    fn next(&mut self) -> Option<DomRoot<Node>> {
108        let current = self.current.take()?;
109
110        self.current = if self.root == current {
111            None
112        } else if let Some(previous_sibling) = current.GetPreviousSibling() {
113            if self.root == previous_sibling {
114                None
115            } else if let Some(last_child) = previous_sibling.descending_last_children().last() {
116                Some(last_child)
117            } else {
118                Some(previous_sibling)
119            }
120        } else {
121            current.GetParentNode()
122        };
123        self.current.clone()
124    }
125}
126
127pub(crate) struct SimpleNodeIterator<I>
128where
129    I: Fn(&Node) -> Option<DomRoot<Node>>,
130{
131    current: Option<DomRoot<Node>>,
132    next_node: I,
133}
134
135impl<I> SimpleNodeIterator<I>
136where
137    I: Fn(&Node) -> Option<DomRoot<Node>>,
138{
139    pub(crate) fn new(current: Option<DomRoot<Node>>, next_node: I) -> Self {
140        SimpleNodeIterator { current, next_node }
141    }
142}
143
144impl<I> Iterator for SimpleNodeIterator<I>
145where
146    I: Fn(&Node) -> Option<DomRoot<Node>>,
147{
148    type Item = DomRoot<Node>;
149
150    fn next(&mut self) -> Option<Self::Item> {
151        let current = self.current.take();
152        self.current = current.as_ref().and_then(|c| (self.next_node)(c));
153        current
154    }
155}
156
157/// An efficient SimpleNodeIterator because it skips rooting if there are no GC pauses.
158///
159/// Use this if you have a `&JSContext` or `NoGC`.
160///
161/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
162/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
163/// while this iterator is alive.
164#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
165pub(crate) struct UnrootedSimpleNodeIterator<'a, 'b, I>
166where
167    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
168{
169    current: Option<UnrootedDom<'b, Node>>,
170    next_node: I,
171    /// This is unused and only used for lifetime guarantee of NoGC
172    no_gc: &'b NoGC,
173    phantom: PhantomData<&'a Node>,
174}
175
176impl<'a, 'b, I> UnrootedSimpleNodeIterator<'a, 'b, I>
177where
178    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
179{
180    pub(crate) fn new(
181        current: Option<UnrootedDom<'b, Node>>,
182        next_node: I,
183        no_gc: &'b NoGC,
184    ) -> Self {
185        UnrootedSimpleNodeIterator {
186            current,
187            next_node,
188            no_gc,
189            phantom: PhantomData,
190        }
191    }
192}
193
194impl<'a, 'b, I> Iterator for UnrootedSimpleNodeIterator<'a, 'b, I>
195where
196    'b: 'a,
197    I: Fn(&Node, &'b NoGC) -> Option<UnrootedDom<'b, Node>>,
198{
199    type Item = UnrootedDom<'b, Node>;
200
201    fn next(&mut self) -> Option<Self::Item> {
202        let current = self.current.take();
203        self.current = current
204            .as_ref()
205            .and_then(|c| (self.next_node)(c, self.no_gc));
206        current
207    }
208}
209
210pub(crate) struct TreeIterator {
211    current: Option<DomRoot<Node>>,
212    depth: usize,
213    shadow_including: ShadowIncluding,
214}
215
216impl TreeIterator {
217    pub(crate) fn new(root: &Node, shadow_including: ShadowIncluding) -> TreeIterator {
218        TreeIterator {
219            current: Some(DomRoot::from_ref(root)),
220            depth: 0,
221            shadow_including,
222        }
223    }
224
225    pub(crate) fn next_skipping_children(&mut self) -> Option<DomRoot<Node>> {
226        let current = self.current.take()?;
227
228        self.next_skipping_children_impl(current)
229    }
230
231    fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
232        let iter = current.inclusive_ancestors(self.shadow_including);
233
234        for ancestor in iter {
235            if self.depth == 0 {
236                break;
237            }
238            if let Some(next_sibling) = ancestor.GetNextSibling() {
239                self.current = Some(next_sibling);
240                return Some(current);
241            }
242            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
243                // Shadow roots don't have sibling, so after we're done traversing
244                // one we jump to the first child of the host
245                if let Some(child) = shadow_root.Host().upcast::<Node>().GetFirstChild() {
246                    self.current = Some(child);
247                    return Some(current);
248                }
249            }
250            self.depth -= 1;
251        }
252        debug_assert_eq!(self.depth, 0);
253        self.current = None;
254        Some(current)
255    }
256
257    pub(crate) fn peek(&self) -> Option<&DomRoot<Node>> {
258        self.current.as_ref()
259    }
260}
261
262impl Iterator for TreeIterator {
263    type Item = DomRoot<Node>;
264
265    /// <https://dom.spec.whatwg.org/#concept-tree-order>
266    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
267    fn next(&mut self) -> Option<DomRoot<Node>> {
268        let current = self.current.take()?;
269
270        // Handle a potential shadow root on the element
271        if let Some(element) = current.downcast::<Element>() &&
272            let Some(shadow_root) = element.shadow_root() &&
273            self.shadow_including == ShadowIncluding::Yes
274        {
275            self.current = Some(DomRoot::from_ref(shadow_root.upcast::<Node>()));
276            self.depth += 1;
277            return Some(current);
278        }
279
280        if let Some(first_child) = current.GetFirstChild() {
281            self.current = Some(first_child);
282            self.depth += 1;
283            return Some(current);
284        };
285
286        self.next_skipping_children_impl(current)
287    }
288}
289
290/// An efficient TreeIterator because it skips rooting if there are no GC pauses.
291///
292/// Use this if you have a `&JSContext` or `NoGC`.
293///
294/// Normally we need to root every `Node` we come across as we do not know if we will have a GC pause.
295/// This does not root the required children. Taking a `&NoGC` enforces that there is no `&mut JSContext`
296/// while this iterator is alive.
297#[cfg_attr(crown, crown::unrooted_must_root_lint::allow_unrooted_interior)]
298pub(crate) struct UnrootedTreeIterator<'a, 'b> {
299    current: Option<UnrootedDom<'b, Node>>,
300    depth: usize,
301    shadow_including: ShadowIncluding,
302    /// This is unused and only used for lifetime guarantee of NoGC
303    no_gc: &'b NoGC,
304    phantom: PhantomData<&'a Node>,
305}
306
307impl<'a, 'b> UnrootedTreeIterator<'a, 'b>
308where
309    'b: 'a,
310{
311    pub(crate) fn new(
312        root: &'a Node,
313        shadow_including: ShadowIncluding,
314        no_gc: &'b NoGC,
315    ) -> UnrootedTreeIterator<'a, 'b> {
316        UnrootedTreeIterator {
317            current: Some(UnrootedDom::from_dom(Dom::from_ref(root), no_gc)),
318            depth: 0,
319            shadow_including,
320            no_gc,
321            phantom: PhantomData,
322        }
323    }
324
325    pub(crate) fn next_skipping_children(&mut self) -> Option<UnrootedDom<'b, Node>> {
326        let current = self.current.take()?;
327
328        let iter = current.inclusive_ancestors(self.shadow_including);
329
330        for ancestor in iter {
331            if self.depth == 0 {
332                break;
333            }
334
335            let next_sibling_option = ancestor.get_next_sibling_unrooted(self.no_gc);
336
337            if let Some(next_sibling) = next_sibling_option {
338                self.current = Some(next_sibling);
339                return Some(current);
340            }
341
342            if let Some(shadow_root) = ancestor.downcast::<ShadowRoot>() {
343                // Shadow roots don't have sibling, so after we're done traversing
344                // one we jump to the first child of the host
345                let child_option = shadow_root
346                    .Host()
347                    .upcast::<Node>()
348                    .get_first_child_unrooted(self.no_gc);
349
350                if let Some(child) = child_option {
351                    self.current = Some(child);
352                    return Some(current);
353                }
354            }
355            self.depth -= 1;
356        }
357        debug_assert_eq!(self.depth, 0);
358        self.current = None;
359        Some(current)
360    }
361}
362
363impl<'a, 'b> Iterator for UnrootedTreeIterator<'a, 'b>
364where
365    'b: 'a,
366{
367    type Item = UnrootedDom<'b, Node>;
368
369    /// <https://dom.spec.whatwg.org/#concept-tree-order>
370    /// <https://dom.spec.whatwg.org/#concept-shadow-including-tree-order>
371    fn next(&mut self) -> Option<UnrootedDom<'b, Node>> {
372        let current = self.current.take()?;
373
374        // Handle a potential shadow root on the element
375        if let Some(element) = current.downcast::<Element>() &&
376            let Some(shadow_root) = element.shadow_root() &&
377            self.shadow_including == ShadowIncluding::Yes
378        {
379            self.current = Some(UnrootedDom::from_dom(
380                Dom::from_ref(shadow_root.upcast::<Node>()),
381                self.no_gc,
382            ));
383            self.depth += 1;
384            return Some(current);
385        }
386
387        let first_child_option = current.get_first_child_unrooted(self.no_gc);
388        if let Some(first_child) = first_child_option {
389            self.current = Some(first_child);
390            self.depth += 1;
391            return Some(current);
392        };
393
394        // current is empty.
395        let _ = self.current.insert(current);
396        self.next_skipping_children()
397    }
398}
script/dom/node/iterators.rs

script/dom/node/
iterators.rs
