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

script/dom/html/
htmlcollection.rs
