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

script/dom/html/
htmlcollection.rs
