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

script/dom/html/
htmlcollection.rs
