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

script/dom/html/
htmlcollection.rs
