script/dom/
nodelist.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::cell::Cell;
6
7use dom_struct::dom_struct;
8use stylo_atoms::Atom;
9
10use crate::dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
11use crate::dom::bindings::codegen::Bindings::NodeListBinding::NodeListMethods;
12use crate::dom::bindings::reflector::{Reflector, reflect_dom_object};
13use crate::dom::bindings::root::{Dom, DomRoot, MutNullableDom};
14use crate::dom::bindings::str::DOMString;
15use crate::dom::document::Document;
16use crate::dom::html::htmlelement::HTMLElement;
17use crate::dom::html::htmlformelement::HTMLFormElement;
18use crate::dom::node::{ChildrenMutation, Node};
19use crate::dom::window::Window;
20use crate::script_runtime::CanGc;
21
22#[derive(JSTraceable, MallocSizeOf)]
23#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
24pub(crate) enum NodeListType {
25    Simple(Vec<Dom<Node>>),
26    Children(ChildrenList),
27    Labels(LabelsList),
28    Radio(RadioList),
29    ElementsByName(ElementsByNameList),
30}
31
32// https://dom.spec.whatwg.org/#interface-nodelist
33#[dom_struct]
34pub(crate) struct NodeList {
35    reflector_: Reflector,
36    list_type: NodeListType,
37}
38
39impl NodeList {
40    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
41    pub(crate) fn new_inherited(list_type: NodeListType) -> NodeList {
42        NodeList {
43            reflector_: Reflector::new(),
44            list_type,
45        }
46    }
47
48    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
49    pub(crate) fn new(
50        window: &Window,
51        list_type: NodeListType,
52        can_gc: CanGc,
53    ) -> DomRoot<NodeList> {
54        reflect_dom_object(Box::new(NodeList::new_inherited(list_type)), window, can_gc)
55    }
56
57    pub(crate) fn new_simple_list<T>(window: &Window, iter: T, can_gc: CanGc) -> DomRoot<NodeList>
58    where
59        T: Iterator<Item = DomRoot<Node>>,
60    {
61        NodeList::new(
62            window,
63            NodeListType::Simple(iter.map(|r| Dom::from_ref(&*r)).collect()),
64            can_gc,
65        )
66    }
67
68    pub(crate) fn new_simple_list_slice(
69        window: &Window,
70        slice: &[&Node],
71        can_gc: CanGc,
72    ) -> DomRoot<NodeList> {
73        NodeList::new(
74            window,
75            NodeListType::Simple(slice.iter().map(|r| Dom::from_ref(*r)).collect()),
76            can_gc,
77        )
78    }
79
80    pub(crate) fn new_child_list(window: &Window, node: &Node, can_gc: CanGc) -> DomRoot<NodeList> {
81        NodeList::new(
82            window,
83            NodeListType::Children(ChildrenList::new(node)),
84            can_gc,
85        )
86    }
87
88    pub(crate) fn new_labels_list(
89        window: &Window,
90        element: &HTMLElement,
91        can_gc: CanGc,
92    ) -> DomRoot<NodeList> {
93        NodeList::new(
94            window,
95            NodeListType::Labels(LabelsList::new(element)),
96            can_gc,
97        )
98    }
99
100    pub(crate) fn new_elements_by_name_list(
101        window: &Window,
102        document: &Document,
103        name: DOMString,
104        can_gc: CanGc,
105    ) -> DomRoot<NodeList> {
106        NodeList::new(
107            window,
108            NodeListType::ElementsByName(ElementsByNameList::new(document, name)),
109            can_gc,
110        )
111    }
112
113    pub(crate) fn empty(window: &Window, can_gc: CanGc) -> DomRoot<NodeList> {
114        NodeList::new(window, NodeListType::Simple(vec![]), can_gc)
115    }
116}
117
118impl NodeListMethods<crate::DomTypeHolder> for NodeList {
119    // https://dom.spec.whatwg.org/#dom-nodelist-length
120    fn Length(&self) -> u32 {
121        match self.list_type {
122            NodeListType::Simple(ref elems) => elems.len() as u32,
123            NodeListType::Children(ref list) => list.len(),
124            NodeListType::Labels(ref list) => list.len(),
125            NodeListType::Radio(ref list) => list.len(),
126            NodeListType::ElementsByName(ref list) => list.len(),
127        }
128    }
129
130    // https://dom.spec.whatwg.org/#dom-nodelist-item
131    fn Item(&self, index: u32) -> Option<DomRoot<Node>> {
132        match self.list_type {
133            NodeListType::Simple(ref elems) => elems
134                .get(index as usize)
135                .map(|node| DomRoot::from_ref(&**node)),
136            NodeListType::Children(ref list) => list.item(index),
137            NodeListType::Labels(ref list) => list.item(index),
138            NodeListType::Radio(ref list) => list.item(index),
139            NodeListType::ElementsByName(ref list) => list.item(index),
140        }
141    }
142
143    // https://dom.spec.whatwg.org/#dom-nodelist-item
144    fn IndexedGetter(&self, index: u32) -> Option<DomRoot<Node>> {
145        self.Item(index)
146    }
147}
148
149impl NodeList {
150    pub(crate) fn as_children_list(&self) -> &ChildrenList {
151        if let NodeListType::Children(ref list) = self.list_type {
152            list
153        } else {
154            panic!("called as_children_list() on a non-children node list")
155        }
156    }
157
158    pub(crate) fn as_radio_list(&self) -> &RadioList {
159        if let NodeListType::Radio(ref list) = self.list_type {
160            list
161        } else {
162            panic!("called as_radio_list() on a non-radio node list")
163        }
164    }
165
166    pub(crate) fn iter(&self) -> impl Iterator<Item = DomRoot<Node>> + '_ {
167        let len = self.Length();
168        // There is room for optimization here in non-simple cases,
169        // as calling Item repeatedly on a live list can involve redundant work.
170        (0..len).flat_map(move |i| self.Item(i))
171    }
172}
173
174#[derive(JSTraceable, MallocSizeOf)]
175#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
176pub(crate) struct ChildrenList {
177    node: Dom<Node>,
178    last_visited: MutNullableDom<Node>,
179    last_index: Cell<u32>,
180}
181
182impl ChildrenList {
183    pub(crate) fn new(node: &Node) -> ChildrenList {
184        let last_visited = node.GetFirstChild();
185        ChildrenList {
186            node: Dom::from_ref(node),
187            last_visited: MutNullableDom::new(last_visited.as_deref()),
188            last_index: Cell::new(0u32),
189        }
190    }
191
192    pub(crate) fn len(&self) -> u32 {
193        self.node.children_count()
194    }
195
196    pub(crate) fn item(&self, index: u32) -> Option<DomRoot<Node>> {
197        // This always start traversing the children from the closest element
198        // among parent's first and last children and the last visited one.
199        let len = self.len();
200        if index >= len {
201            return None;
202        }
203        if index == 0u32 {
204            // Item is first child if any, not worth updating last visited.
205            return self.node.GetFirstChild();
206        }
207        let last_index = self.last_index.get();
208        if index == last_index {
209            // Item is last visited child, no need to update last visited.
210            return Some(self.last_visited.get().unwrap());
211        }
212        let last_visited = if index - 1u32 == last_index {
213            // Item is last visited's next sibling.
214            self.last_visited.get().unwrap().GetNextSibling().unwrap()
215        } else if last_index > 0 && index == last_index - 1u32 {
216            // Item is last visited's previous sibling.
217            self.last_visited
218                .get()
219                .unwrap()
220                .GetPreviousSibling()
221                .unwrap()
222        } else if index > last_index {
223            if index == len - 1u32 {
224                // Item is parent's last child, not worth updating last visited.
225                return Some(self.node.GetLastChild().unwrap());
226            }
227            if index <= last_index + (len - last_index) / 2u32 {
228                // Item is closer to the last visited child and follows it.
229                self.last_visited
230                    .get()
231                    .unwrap()
232                    .inclusively_following_siblings()
233                    .nth((index - last_index) as usize)
234                    .unwrap()
235            } else {
236                // Item is closer to parent's last child and obviously
237                // precedes it.
238                self.node
239                    .GetLastChild()
240                    .unwrap()
241                    .inclusively_preceding_siblings()
242                    .nth((len - index - 1u32) as usize)
243                    .unwrap()
244            }
245        } else if index >= last_index / 2u32 {
246            // Item is closer to the last visited child and precedes it.
247            self.last_visited
248                .get()
249                .unwrap()
250                .inclusively_preceding_siblings()
251                .nth((last_index - index) as usize)
252                .unwrap()
253        } else {
254            // Item is closer to parent's first child and obviously follows it.
255            debug_assert!(index < last_index / 2u32);
256            self.node
257                .GetFirstChild()
258                .unwrap()
259                .inclusively_following_siblings()
260                .nth(index as usize)
261                .unwrap()
262        };
263        self.last_visited.set(Some(&last_visited));
264        self.last_index.set(index);
265        Some(last_visited)
266    }
267
268    pub(crate) fn children_changed(&self, mutation: &ChildrenMutation) {
269        fn prepend(list: &ChildrenList, added: &[&Node], next: &Node) {
270            let len = added.len() as u32;
271            if len == 0u32 {
272                return;
273            }
274            let index = list.last_index.get();
275            if index < len {
276                list.last_visited.set(Some(added[index as usize]));
277            } else if index / 2u32 >= len {
278                // If last index is twice as large as the number of added nodes,
279                // updating only it means that less nodes will be traversed if
280                // caller is traversing the node list linearly.
281                list.last_index.set(len + index);
282            } else {
283                // If last index is not twice as large but still larger,
284                // it's better to update it to the number of added nodes.
285                list.last_visited.set(Some(next));
286                list.last_index.set(len);
287            }
288        }
289
290        fn replace(
291            list: &ChildrenList,
292            prev: Option<&Node>,
293            removed: &Node,
294            added: &[&Node],
295            next: Option<&Node>,
296        ) {
297            let index = list.last_index.get();
298            if removed == &*list.last_visited.get().unwrap() {
299                let visited = match (prev, added, next) {
300                    (None, _, None) => {
301                        // Such cases where parent had only one child should
302                        // have been changed into ChildrenMutation::ReplaceAll
303                        // by ChildrenMutation::replace().
304                        unreachable!()
305                    },
306                    (_, added, _) if !added.is_empty() => added[0],
307                    (_, _, Some(next)) => next,
308                    (Some(prev), _, None) => {
309                        list.last_index.set(index - 1u32);
310                        prev
311                    },
312                };
313                list.last_visited.set(Some(visited));
314            } else if added.len() != 1 {
315                // The replaced child isn't the last visited one, and there are
316                // 0 or more than 1 nodes to replace it. Special care must be
317                // given to update the state of that ChildrenList.
318                match (prev, next) {
319                    (Some(_), None) => {},
320                    (None, Some(next)) => {
321                        list.last_index.set(index - 1);
322                        prepend(list, added, next);
323                    },
324                    (Some(_), Some(_)) => {
325                        list.reset();
326                    },
327                    (None, None) => unreachable!(),
328                }
329            }
330        }
331
332        match *mutation {
333            ChildrenMutation::Append { .. } => {},
334            ChildrenMutation::Insert { .. } => {
335                self.reset();
336            },
337            ChildrenMutation::Prepend { added, next } => {
338                prepend(self, added, next);
339            },
340            ChildrenMutation::Replace {
341                prev,
342                removed,
343                added,
344                next,
345            } => {
346                replace(self, prev, removed, added, next);
347            },
348            ChildrenMutation::ReplaceAll { added, .. } => {
349                let len = added.len();
350                let index = self.last_index.get();
351                if len == 0 {
352                    self.last_visited.set(None);
353                    self.last_index.set(0u32);
354                } else if index < len as u32 {
355                    self.last_visited.set(Some(added[index as usize]));
356                } else {
357                    // Setting last visited to parent's last child serves no purpose,
358                    // so the middle is arbitrarily chosen here in case the caller
359                    // wants random access.
360                    let middle = len / 2;
361                    self.last_visited.set(Some(added[middle]));
362                    self.last_index.set(middle as u32);
363                }
364            },
365            ChildrenMutation::ChangeText => {},
366        }
367    }
368
369    fn reset(&self) {
370        self.last_visited.set(self.node.GetFirstChild().as_deref());
371        self.last_index.set(0u32);
372    }
373}
374
375// Labels lists: There might be room for performance optimization
376// analogous to the ChildrenMutation case of a children list,
377// in which we can keep information from an older access live
378// if we know nothing has happened that would change it.
379// However, label relationships can happen from further away
380// in the DOM than parent-child relationships, so it's not as simple,
381// and it's possible that tracking label moves would end up no faster
382// than recalculating labels.
383#[derive(JSTraceable, MallocSizeOf)]
384#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
385pub(crate) struct LabelsList {
386    element: Dom<HTMLElement>,
387}
388
389impl LabelsList {
390    pub(crate) fn new(element: &HTMLElement) -> LabelsList {
391        LabelsList {
392            element: Dom::from_ref(element),
393        }
394    }
395
396    pub(crate) fn len(&self) -> u32 {
397        self.element.labels_count()
398    }
399
400    pub(crate) fn item(&self, index: u32) -> Option<DomRoot<Node>> {
401        self.element.label_at(index)
402    }
403}
404
405// Radio node lists: There is room for performance improvement here;
406// a form is already aware of changes to its set of controls,
407// so a radio list can cache and cache-invalidate its contents
408// just by hooking into what the form already knows without a
409// separate mutation observer. FIXME #25482
410#[derive(Clone, Copy, JSTraceable, MallocSizeOf)]
411pub(crate) enum RadioListMode {
412    ControlsExceptImageInputs,
413    Images,
414}
415
416#[derive(JSTraceable, MallocSizeOf)]
417#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
418pub(crate) struct RadioList {
419    form: Dom<HTMLFormElement>,
420    mode: RadioListMode,
421    #[no_trace]
422    name: Atom,
423}
424
425impl RadioList {
426    pub(crate) fn new(form: &HTMLFormElement, mode: RadioListMode, name: Atom) -> RadioList {
427        RadioList {
428            form: Dom::from_ref(form),
429            mode,
430            name,
431        }
432    }
433
434    pub(crate) fn len(&self) -> u32 {
435        self.form.count_for_radio_list(self.mode, &self.name)
436    }
437
438    pub(crate) fn item(&self, index: u32) -> Option<DomRoot<Node>> {
439        self.form.nth_for_radio_list(index, self.mode, &self.name)
440    }
441}
442
443#[derive(JSTraceable, MallocSizeOf)]
444#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
445pub(crate) struct ElementsByNameList {
446    document: Dom<Document>,
447    name: DOMString,
448}
449
450impl ElementsByNameList {
451    pub(crate) fn new(document: &Document, name: DOMString) -> ElementsByNameList {
452        ElementsByNameList {
453            document: Dom::from_ref(document),
454            name,
455        }
456    }
457
458    pub(crate) fn len(&self) -> u32 {
459        self.document.elements_by_name_count(&self.name)
460    }
461
462    pub(crate) fn item(&self, index: u32) -> Option<DomRoot<Node>> {
463        self.document
464            .nth_element_by_name(index, &self.name)
465            .map(|n| DomRoot::from_ref(&*n))
466    }
467}