script/dom/html/
htmlcollection.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;
6use std::cmp::Ordering;
7
8use dom_struct::dom_struct;
9use html5ever::{LocalName, QualName, local_name, namespace_url, ns};
10use style::str::split_html_space_chars;
11use stylo_atoms::Atom;
12
13use crate::dom::bindings::codegen::Bindings::HTMLCollectionBinding::HTMLCollectionMethods;
14use crate::dom::bindings::domname::namespace_from_domstring;
15use crate::dom::bindings::inheritance::Castable;
16use crate::dom::bindings::reflector::{Reflector, reflect_dom_object};
17use crate::dom::bindings::root::{Dom, DomRoot, MutNullableDom};
18use crate::dom::bindings::str::DOMString;
19use crate::dom::bindings::trace::JSTraceable;
20use crate::dom::element::Element;
21use crate::dom::node::{Node, NodeTraits};
22use crate::dom::window::Window;
23use crate::script_runtime::CanGc;
24
25pub(crate) trait CollectionFilter: JSTraceable {
26    fn filter<'a>(&self, elem: &'a Element, root: &'a Node) -> bool;
27}
28
29/// An optional `u32`, using `u32::MAX` to represent None.  It would be nicer
30/// just to use `Option<u32>` for this, but that would produce word alignment
31/// issues since `Option<u32>` uses 33 bits.
32#[derive(Clone, Copy, JSTraceable, MallocSizeOf)]
33struct OptionU32 {
34    bits: u32,
35}
36
37impl OptionU32 {
38    fn to_option(self) -> Option<u32> {
39        if self.bits == u32::MAX {
40            None
41        } else {
42            Some(self.bits)
43        }
44    }
45
46    fn some(bits: u32) -> OptionU32 {
47        assert_ne!(bits, u32::MAX);
48        OptionU32 { bits }
49    }
50
51    fn none() -> OptionU32 {
52        OptionU32 { bits: u32::MAX }
53    }
54}
55
56#[dom_struct]
57pub(crate) struct HTMLCollection {
58    reflector_: Reflector,
59    root: Dom<Node>,
60    #[ignore_malloc_size_of = "Trait object (Box<dyn CollectionFilter>) cannot be sized"]
61    filter: Box<dyn CollectionFilter + 'static>,
62    // We cache the version of the root node and all its decendents,
63    // the length of the collection, and a cursor into the collection.
64    // FIXME: make the cached cursor element a weak pointer
65    cached_version: Cell<u64>,
66    cached_cursor_element: MutNullableDom<Element>,
67    cached_cursor_index: Cell<OptionU32>,
68    cached_length: Cell<OptionU32>,
69}
70
71impl HTMLCollection {
72    pub(crate) fn new_inherited(
73        root: &Node,
74        filter: Box<dyn CollectionFilter + 'static>,
75    ) -> HTMLCollection {
76        HTMLCollection {
77            reflector_: Reflector::new(),
78            root: Dom::from_ref(root),
79            filter,
80            // Default values for the cache
81            cached_version: Cell::new(root.inclusive_descendants_version()),
82            cached_cursor_element: MutNullableDom::new(None),
83            cached_cursor_index: Cell::new(OptionU32::none()),
84            cached_length: Cell::new(OptionU32::none()),
85        }
86    }
87
88    /// Returns a collection which is always empty.
89    pub(crate) fn always_empty(window: &Window, root: &Node, can_gc: CanGc) -> DomRoot<Self> {
90        #[derive(JSTraceable)]
91        struct NoFilter;
92        impl CollectionFilter for NoFilter {
93            fn filter<'a>(&self, _: &'a Element, _: &'a Node) -> bool {
94                false
95            }
96        }
97
98        Self::new(window, root, Box::new(NoFilter), can_gc)
99    }
100
101    pub(crate) fn new(
102        window: &Window,
103        root: &Node,
104        filter: Box<dyn CollectionFilter + 'static>,
105        can_gc: CanGc,
106    ) -> DomRoot<Self> {
107        reflect_dom_object(Box::new(Self::new_inherited(root, filter)), window, can_gc)
108    }
109
110    /// Create a new  [`HTMLCollection`] that just filters element using a static function.
111    pub(crate) fn new_with_filter_fn(
112        window: &Window,
113        root: &Node,
114        filter_function: fn(&Element, &Node) -> bool,
115        can_gc: CanGc,
116    ) -> DomRoot<Self> {
117        #[derive(JSTraceable, MallocSizeOf)]
118        pub(crate) struct StaticFunctionFilter(
119            // The function *must* be static so that it never holds references to DOM objects, which
120            // would cause issues with garbage collection -- since it isn't traced.
121            #[no_trace]
122            #[ignore_malloc_size_of = "Static function pointer"]
123            fn(&Element, &Node) -> bool,
124        );
125        impl CollectionFilter for StaticFunctionFilter {
126            fn filter(&self, element: &Element, root: &Node) -> bool {
127                (self.0)(element, root)
128            }
129        }
130        Self::new(
131            window,
132            root,
133            Box::new(StaticFunctionFilter(filter_function)),
134            can_gc,
135        )
136    }
137
138    pub(crate) fn create(
139        window: &Window,
140        root: &Node,
141        filter: Box<dyn CollectionFilter + 'static>,
142        can_gc: CanGc,
143    ) -> DomRoot<Self> {
144        Self::new(window, root, filter, can_gc)
145    }
146
147    fn validate_cache(&self) {
148        // Clear the cache if the root version is different from our cached version
149        let cached_version = self.cached_version.get();
150        let curr_version = self.root.inclusive_descendants_version();
151        if curr_version != cached_version {
152            // Default values for the cache
153            self.cached_version.set(curr_version);
154            self.cached_cursor_element.set(None);
155            self.cached_length.set(OptionU32::none());
156            self.cached_cursor_index.set(OptionU32::none());
157        }
158    }
159
160    fn set_cached_cursor(
161        &self,
162        index: u32,
163        element: Option<DomRoot<Element>>,
164    ) -> Option<DomRoot<Element>> {
165        if let Some(element) = element {
166            self.cached_cursor_index.set(OptionU32::some(index));
167            self.cached_cursor_element.set(Some(&element));
168            Some(element)
169        } else {
170            None
171        }
172    }
173
174    /// <https://dom.spec.whatwg.org/#concept-getelementsbytagname>
175    pub(crate) fn by_qualified_name(
176        window: &Window,
177        root: &Node,
178        qualified_name: LocalName,
179        can_gc: CanGc,
180    ) -> DomRoot<HTMLCollection> {
181        // case 1
182        if qualified_name == local_name!("*") {
183            #[derive(JSTraceable, MallocSizeOf)]
184            struct AllFilter;
185            impl CollectionFilter for AllFilter {
186                fn filter(&self, _elem: &Element, _root: &Node) -> bool {
187                    true
188                }
189            }
190            return HTMLCollection::create(window, root, Box::new(AllFilter), can_gc);
191        }
192
193        #[derive(JSTraceable, MallocSizeOf)]
194        struct HtmlDocumentFilter {
195            #[no_trace]
196            qualified_name: LocalName,
197            #[no_trace]
198            ascii_lower_qualified_name: LocalName,
199        }
200        impl CollectionFilter for HtmlDocumentFilter {
201            fn filter(&self, elem: &Element, root: &Node) -> bool {
202                if root.is_in_html_doc() && elem.namespace() == &ns!(html) {
203                    // case 2
204                    HTMLCollection::match_element(elem, &self.ascii_lower_qualified_name)
205                } else {
206                    // case 2 and 3
207                    HTMLCollection::match_element(elem, &self.qualified_name)
208                }
209            }
210        }
211
212        let filter = HtmlDocumentFilter {
213            ascii_lower_qualified_name: qualified_name.to_ascii_lowercase(),
214            qualified_name,
215        };
216        HTMLCollection::create(window, root, Box::new(filter), can_gc)
217    }
218
219    fn match_element(elem: &Element, qualified_name: &LocalName) -> bool {
220        match elem.prefix().as_ref() {
221            None => elem.local_name() == qualified_name,
222            Some(prefix) => {
223                qualified_name.starts_with(&**prefix) &&
224                    qualified_name.find(':') == Some(prefix.len()) &&
225                    qualified_name.ends_with(&**elem.local_name())
226            },
227        }
228    }
229
230    pub(crate) fn by_tag_name_ns(
231        window: &Window,
232        root: &Node,
233        tag: DOMString,
234        maybe_ns: Option<DOMString>,
235        can_gc: CanGc,
236    ) -> DomRoot<HTMLCollection> {
237        let local = LocalName::from(tag);
238        let ns = namespace_from_domstring(maybe_ns);
239        let qname = QualName::new(None, ns, local);
240        HTMLCollection::by_qual_tag_name(window, root, qname, can_gc)
241    }
242
243    pub(crate) fn by_qual_tag_name(
244        window: &Window,
245        root: &Node,
246        qname: QualName,
247        can_gc: CanGc,
248    ) -> DomRoot<HTMLCollection> {
249        #[derive(JSTraceable, MallocSizeOf)]
250        struct TagNameNSFilter {
251            #[no_trace]
252            qname: QualName,
253        }
254        impl CollectionFilter for TagNameNSFilter {
255            fn filter(&self, elem: &Element, _root: &Node) -> bool {
256                ((self.qname.ns == namespace_url!("*")) || (self.qname.ns == *elem.namespace())) &&
257                    ((self.qname.local == local_name!("*")) ||
258                        (self.qname.local == *elem.local_name()))
259            }
260        }
261        let filter = TagNameNSFilter { qname };
262        HTMLCollection::create(window, root, Box::new(filter), can_gc)
263    }
264
265    pub(crate) fn by_class_name(
266        window: &Window,
267        root: &Node,
268        classes: DOMString,
269        can_gc: CanGc,
270    ) -> DomRoot<HTMLCollection> {
271        let class_atoms = split_html_space_chars(&classes.str())
272            .map(Atom::from)
273            .collect();
274        HTMLCollection::by_atomic_class_name(window, root, class_atoms, can_gc)
275    }
276
277    pub(crate) fn by_atomic_class_name(
278        window: &Window,
279        root: &Node,
280        classes: Vec<Atom>,
281        can_gc: CanGc,
282    ) -> DomRoot<HTMLCollection> {
283        #[derive(JSTraceable, MallocSizeOf)]
284        struct ClassNameFilter {
285            #[no_trace]
286            classes: Vec<Atom>,
287        }
288        impl CollectionFilter for ClassNameFilter {
289            fn filter(&self, elem: &Element, _root: &Node) -> bool {
290                let case_sensitivity = elem
291                    .owner_document()
292                    .quirks_mode()
293                    .classes_and_ids_case_sensitivity();
294
295                self.classes
296                    .iter()
297                    .all(|class| elem.has_class(class, case_sensitivity))
298            }
299        }
300
301        if classes.is_empty() {
302            return HTMLCollection::always_empty(window, root, can_gc);
303        }
304
305        let filter = ClassNameFilter { classes };
306        HTMLCollection::create(window, root, Box::new(filter), can_gc)
307    }
308
309    pub(crate) fn children(window: &Window, root: &Node, can_gc: CanGc) -> DomRoot<HTMLCollection> {
310        HTMLCollection::new_with_filter_fn(
311            window,
312            root,
313            |element, root| root.is_parent_of(element.upcast()),
314            can_gc,
315        )
316    }
317
318    pub(crate) fn elements_iter_after<'a>(
319        &'a self,
320        after: &'a Node,
321    ) -> impl Iterator<Item = DomRoot<Element>> + 'a {
322        // Iterate forwards from a node.
323        after
324            .following_nodes(&self.root)
325            .filter_map(DomRoot::downcast)
326            .filter(move |element| self.filter.filter(element, &self.root))
327    }
328
329    pub(crate) fn elements_iter(&self) -> impl Iterator<Item = DomRoot<Element>> + '_ {
330        // Iterate forwards from the root.
331        self.elements_iter_after(&self.root)
332    }
333
334    pub(crate) fn elements_iter_before<'a>(
335        &'a self,
336        before: &'a Node,
337    ) -> impl Iterator<Item = DomRoot<Element>> + 'a {
338        // Iterate backwards from a node.
339        before
340            .preceding_nodes(&self.root)
341            .filter_map(DomRoot::downcast)
342            .filter(move |element| self.filter.filter(element, &self.root))
343    }
344
345    pub(crate) fn root_node(&self) -> DomRoot<Node> {
346        DomRoot::from_ref(&self.root)
347    }
348}
349
350impl HTMLCollectionMethods<crate::DomTypeHolder> for HTMLCollection {
351    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-length>
352    fn Length(&self) -> u32 {
353        self.validate_cache();
354
355        if let Some(cached_length) = self.cached_length.get().to_option() {
356            // Cache hit
357            cached_length
358        } else {
359            // Cache miss, calculate the length
360            let length = self.elements_iter().count() as u32;
361            self.cached_length.set(OptionU32::some(length));
362            length
363        }
364    }
365
366    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-item>
367    fn Item(&self, index: u32) -> Option<DomRoot<Element>> {
368        self.validate_cache();
369
370        if let Some(element) = self.cached_cursor_element.get() {
371            // Cache hit, the cursor element is set
372            if let Some(cached_index) = self.cached_cursor_index.get().to_option() {
373                match cached_index.cmp(&index) {
374                    Ordering::Equal => {
375                        // The cursor is the element we're looking for
376                        Some(element)
377                    },
378                    Ordering::Less => {
379                        // The cursor is before the element we're looking for
380                        // Iterate forwards, starting at the cursor.
381                        let offset = index - (cached_index + 1);
382                        let node: DomRoot<Node> = DomRoot::upcast(element);
383                        let mut iter = self.elements_iter_after(&node);
384                        self.set_cached_cursor(index, iter.nth(offset as usize))
385                    },
386                    Ordering::Greater => {
387                        // The cursor is after the element we're looking for
388                        // Iterate backwards, starting at the cursor.
389                        let offset = cached_index - (index + 1);
390                        let node: DomRoot<Node> = DomRoot::upcast(element);
391                        let mut iter = self.elements_iter_before(&node);
392                        self.set_cached_cursor(index, iter.nth(offset as usize))
393                    },
394                }
395            } else {
396                // Cache miss
397                // Iterate forwards through all the nodes
398                self.set_cached_cursor(index, self.elements_iter().nth(index as usize))
399            }
400        } else {
401            // Cache miss
402            // Iterate forwards through all the nodes
403            self.set_cached_cursor(index, self.elements_iter().nth(index as usize))
404        }
405    }
406
407    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-nameditem>
408    fn NamedItem(&self, key: DOMString) -> Option<DomRoot<Element>> {
409        // Step 1.
410        if key.is_empty() {
411            return None;
412        }
413
414        let key = Atom::from(key);
415
416        // Step 2.
417        self.elements_iter().find(|elem| {
418            elem.get_id().is_some_and(|id| id == key) ||
419                (elem.namespace() == &ns!(html) && elem.get_name().is_some_and(|id| id == key))
420        })
421    }
422
423    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-item>
424    fn IndexedGetter(&self, index: u32) -> Option<DomRoot<Element>> {
425        self.Item(index)
426    }
427
428    // check-tidy: no specs after this line
429    fn NamedGetter(&self, name: DOMString) -> Option<DomRoot<Element>> {
430        self.NamedItem(name)
431    }
432
433    /// <https://dom.spec.whatwg.org/#interface-htmlcollection>
434    fn SupportedPropertyNames(&self) -> Vec<DOMString> {
435        // Step 1
436        let mut result = vec![];
437
438        // Step 2
439        for elem in self.elements_iter() {
440            // Step 2.1
441            if let Some(id_atom) = elem.get_id() {
442                let id_str = DOMString::from(&*id_atom);
443                if !result.contains(&id_str) {
444                    result.push(id_str);
445                }
446            }
447            // Step 2.2
448            if *elem.namespace() == ns!(html) {
449                if let Some(name_atom) = elem.get_name() {
450                    let name_str = DOMString::from(&*name_atom);
451                    if !result.contains(&name_str) {
452                        result.push(name_str)
453                    }
454                }
455            }
456        }
457
458        // Step 3
459        result
460    }
461}
script/dom/html/htmlcollection.rs

script/dom/html/
htmlcollection.rs
