script/dom/html/

htmlcollection.rs

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

use std::cell::Cell;

use dom_struct::dom_struct;
use html5ever::{LocalName, QualName, local_name, namespace_url, ns};
use style::str::split_html_space_chars;
use stylo_atoms::Atom;

use crate::dom::bindings::codegen::Bindings::HTMLCollectionBinding::HTMLCollectionMethods;
use crate::dom::bindings::domname::namespace_from_domstring;
use crate::dom::bindings::inheritance::Castable;
use crate::dom::bindings::reflector::{Reflector, reflect_dom_object_with_cx};
use crate::dom::bindings::root::{Dom, DomRoot, MutNullableDom};
use crate::dom::bindings::str::DOMString;
use crate::dom::bindings::trace::JSTraceable;
use crate::dom::element::Element;
use crate::dom::node::{Node, NodeTraits};
use crate::dom::window::Window;

pub(crate) trait CollectionFilter: JSTraceable {
    fn filter<'a>(&self, elem: &'a Element, root: &'a Node) -> bool;
}

/// Alternative to [`CollectionFilter`] that provides elements directly via
/// a custom iterator, rather than filtering a tree traversal. This is more
/// efficient when the collection's elements can be enumerated directly
/// (e.g. `selectedOptions` iterating only the select's list of options).
pub(crate) trait CollectionSource: JSTraceable {
    fn iter<'a>(&'a self, root: &'a Node) -> Box<dyn Iterator<Item = DomRoot<Element>> + 'a>;
}

/// How a collection enumerates its elements.
#[derive(JSTraceable)]
enum CollectionKind {
    /// Filter elements from a subtree traversal of the root node.
    Filter(Box<dyn CollectionFilter + 'static>),
    /// Provide elements directly via a custom iterator.
    Source(Box<dyn CollectionSource + 'static>),
}

/// An optional `u32`, using `u32::MAX` to represent None.  It would be nicer
/// just to use `Option<u32>` for this, but that would produce word alignment
/// issues since `Option<u32>` uses 33 bits.
#[derive(Clone, Copy, JSTraceable, MallocSizeOf)]
struct OptionU32 {
    bits: u32,
}

impl OptionU32 {
    fn to_option(self) -> Option<u32> {
        if self.bits == u32::MAX {
            None
        } else {
            Some(self.bits)
        }
    }

    fn some(bits: u32) -> OptionU32 {
        assert_ne!(bits, u32::MAX);
        OptionU32 { bits }
    }

    fn none() -> OptionU32 {
        OptionU32 { bits: u32::MAX }
    }
}

#[dom_struct]
pub(crate) struct HTMLCollection {
    reflector_: Reflector,
    root: Dom<Node>,
    #[ignore_malloc_size_of = "Trait objects cannot be sized"]
    kind: CollectionKind,
    // We cache the version of the root node and all its decendents,
    // the length of the collection, and a cursor into the collection.
    // FIXME: make the cached cursor element a weak pointer
    cached_version: Cell<u64>,
    cached_cursor_element: MutNullableDom<Element>,
    cached_cursor_index: Cell<OptionU32>,
    cached_length: Cell<OptionU32>,
}

impl HTMLCollection {
    fn new_inherited_with_kind(root: &Node, kind: CollectionKind) -> HTMLCollection {
        HTMLCollection {
            reflector_: Reflector::new(),
            root: Dom::from_ref(root),
            kind,
            // Default values for the cache
            cached_version: Cell::new(root.inclusive_descendants_version()),
            cached_cursor_element: MutNullableDom::new(None),
            cached_cursor_index: Cell::new(OptionU32::none()),
            cached_length: Cell::new(OptionU32::none()),
        }
    }

    pub(crate) fn new_inherited(
        root: &Node,
        filter: Box<dyn CollectionFilter + 'static>,
    ) -> HTMLCollection {
        Self::new_inherited_with_kind(root, CollectionKind::Filter(filter))
    }

    pub(crate) fn new_inherited_with_source(
        root: &Node,
        source: Box<dyn CollectionSource + 'static>,
    ) -> HTMLCollection {
        Self::new_inherited_with_kind(root, CollectionKind::Source(source))
    }

    /// Returns a collection which is always empty.
    pub(crate) fn always_empty(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
    ) -> DomRoot<Self> {
        #[derive(JSTraceable)]
        struct NoFilter;
        impl CollectionFilter for NoFilter {
            fn filter<'a>(&self, _: &'a Element, _: &'a Node) -> bool {
                false
            }
        }

        Self::new(cx, window, root, Box::new(NoFilter))
    }

    pub(crate) fn new(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        filter: Box<dyn CollectionFilter + 'static>,
    ) -> DomRoot<Self> {
        reflect_dom_object_with_cx(Box::new(Self::new_inherited(root, filter)), window, cx)
    }

    /// Create a new  [`HTMLCollection`] that just filters element using a static function.
    pub(crate) fn new_with_filter_fn(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        filter_function: fn(&Element, &Node) -> bool,
    ) -> DomRoot<Self> {
        // The function *must* be static so that it never holds references to DOM objects, which
        // would cause issues with garbage collection -- since it isn't traced.
        #[derive(JSTraceable, MallocSizeOf)]
        pub(crate) struct StaticFunctionFilter(
            #[no_trace]
            #[ignore_malloc_size_of = "Static function pointer"]
            fn(&Element, &Node) -> bool,
        );
        impl CollectionFilter for StaticFunctionFilter {
            fn filter(&self, element: &Element, root: &Node) -> bool {
                (self.0)(element, root)
            }
        }
        Self::new(
            cx,
            window,
            root,
            Box::new(StaticFunctionFilter(filter_function)),
        )
    }

    pub(crate) fn create(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        filter: Box<dyn CollectionFilter + 'static>,
    ) -> DomRoot<Self> {
        Self::new(cx, window, root, filter)
    }

    /// Create a new [`HTMLCollection`] backed by a custom element source.
    pub(crate) fn new_with_source(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        source: Box<dyn CollectionSource + 'static>,
    ) -> DomRoot<Self> {
        reflect_dom_object_with_cx(
            Box::new(Self::new_inherited_with_source(root, source)),
            window,
            cx,
        )
    }

    fn validate_cache(&self) {
        // Clear the cache if the root version is different from our cached version
        let cached_version = self.cached_version.get();
        let curr_version = self.root.inclusive_descendants_version();
        if curr_version != cached_version {
            // Default values for the cache
            self.cached_version.set(curr_version);
            self.cached_cursor_element.set(None);
            self.cached_length.set(OptionU32::none());
            self.cached_cursor_index.set(OptionU32::none());
        }
    }

    fn set_cached_cursor(
        &self,
        index: u32,
        element: Option<DomRoot<Element>>,
    ) -> Option<DomRoot<Element>> {
        if let Some(element) = element {
            self.cached_cursor_index.set(OptionU32::some(index));
            self.cached_cursor_element.set(Some(&element));
            Some(element)
        } else {
            None
        }
    }

    /// <https://dom.spec.whatwg.org/#concept-getelementsbytagname>
    pub(crate) fn by_qualified_name(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        qualified_name: LocalName,
    ) -> DomRoot<HTMLCollection> {
        // case 1
        if qualified_name == local_name!("*") {
            #[derive(JSTraceable, MallocSizeOf)]
            struct AllFilter;
            impl CollectionFilter for AllFilter {
                fn filter(&self, _elem: &Element, _root: &Node) -> bool {
                    true
                }
            }
            return HTMLCollection::create(cx, window, root, Box::new(AllFilter));
        }

        #[derive(JSTraceable, MallocSizeOf)]
        struct HtmlDocumentFilter {
            #[no_trace]
            qualified_name: LocalName,
            #[no_trace]
            ascii_lower_qualified_name: LocalName,
        }
        impl CollectionFilter for HtmlDocumentFilter {
            fn filter(&self, elem: &Element, root: &Node) -> bool {
                if root.is_in_html_doc() && elem.namespace() == &ns!(html) {
                    // case 2
                    HTMLCollection::match_element(elem, &self.ascii_lower_qualified_name)
                } else {
                    // case 2 and 3
                    HTMLCollection::match_element(elem, &self.qualified_name)
                }
            }
        }

        let filter = HtmlDocumentFilter {
            ascii_lower_qualified_name: qualified_name.to_ascii_lowercase(),
            qualified_name,
        };
        HTMLCollection::create(cx, window, root, Box::new(filter))
    }

    fn match_element(elem: &Element, qualified_name: &LocalName) -> bool {
        match elem.prefix().as_ref() {
            None => elem.local_name() == qualified_name,
            Some(prefix) => {
                qualified_name.starts_with(&**prefix) &&
                    qualified_name.find(':') == Some(prefix.len()) &&
                    qualified_name.ends_with(&**elem.local_name())
            },
        }
    }

    pub(crate) fn by_tag_name_ns(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        tag: DOMString,
        maybe_ns: Option<DOMString>,
    ) -> DomRoot<HTMLCollection> {
        let local = LocalName::from(tag);
        let ns = namespace_from_domstring(maybe_ns);
        let qname = QualName::new(None, ns, local);
        HTMLCollection::by_qual_tag_name(cx, window, root, qname)
    }

    pub(crate) fn by_qual_tag_name(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        qname: QualName,
    ) -> DomRoot<HTMLCollection> {
        #[derive(JSTraceable, MallocSizeOf)]
        struct TagNameNSFilter {
            #[no_trace]
            qname: QualName,
        }
        impl CollectionFilter for TagNameNSFilter {
            fn filter(&self, elem: &Element, _root: &Node) -> bool {
                ((self.qname.ns == namespace_url!("*")) || (self.qname.ns == *elem.namespace())) &&
                    ((self.qname.local == local_name!("*")) ||
                        (self.qname.local == *elem.local_name()))
            }
        }
        let filter = TagNameNSFilter { qname };
        HTMLCollection::create(cx, window, root, Box::new(filter))
    }

    pub(crate) fn by_class_name(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        classes: DOMString,
    ) -> DomRoot<HTMLCollection> {
        let class_atoms = split_html_space_chars(&classes.str())
            .map(Atom::from)
            .collect();
        HTMLCollection::by_atomic_class_name(cx, window, root, class_atoms)
    }

    pub(crate) fn by_atomic_class_name(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
        classes: Vec<Atom>,
    ) -> DomRoot<HTMLCollection> {
        #[derive(JSTraceable, MallocSizeOf)]
        struct ClassNameFilter {
            #[no_trace]
            classes: Vec<Atom>,
        }
        impl CollectionFilter for ClassNameFilter {
            fn filter(&self, elem: &Element, _root: &Node) -> bool {
                let case_sensitivity = elem
                    .owner_document()
                    .quirks_mode()
                    .classes_and_ids_case_sensitivity();

                self.classes
                    .iter()
                    .all(|class| elem.has_class(class, case_sensitivity))
            }
        }

        if classes.is_empty() {
            return HTMLCollection::always_empty(cx, window, root);
        }

        let filter = ClassNameFilter { classes };
        HTMLCollection::create(cx, window, root, Box::new(filter))
    }

    pub(crate) fn children(
        cx: &mut js::context::JSContext,
        window: &Window,
        root: &Node,
    ) -> DomRoot<HTMLCollection> {
        HTMLCollection::new_with_filter_fn(cx, window, root, |element, root| {
            root.is_parent_of(element.upcast())
        })
    }

    /// Iterate forwards from a node, filtering by a [`CollectionFilter`].
    /// Only usable with filter-based collections for cursor optimization.
    fn filter_iter_after<'a>(
        &'a self,
        after: &'a Node,
        filter: &'a (dyn CollectionFilter + 'static),
    ) -> impl Iterator<Item = DomRoot<Element>> + 'a {
        after
            .following_nodes(&self.root)
            .filter_map(DomRoot::downcast)
            .filter(move |element| filter.filter(element, &self.root))
    }

    /// Iterate backwards from a node, filtering by a [`CollectionFilter`].
    /// Only usable with filter-based collections for cursor optimization.
    fn filter_iter_before<'a>(
        &'a self,
        before: &'a Node,
        filter: &'a (dyn CollectionFilter + 'static),
    ) -> impl Iterator<Item = DomRoot<Element>> + 'a {
        before
            .preceding_nodes(&self.root)
            .filter_map(DomRoot::downcast)
            .filter(move |element| filter.filter(element, &self.root))
    }

    pub(crate) fn elements_iter(&self) -> Box<dyn Iterator<Item = DomRoot<Element>> + '_> {
        match &self.kind {
            CollectionKind::Filter(filter) => {
                Box::new(self.filter_iter_after(&self.root, filter.as_ref()))
            },
            CollectionKind::Source(source) => source.iter(&self.root),
        }
    }

    pub(crate) fn root_node(&self) -> DomRoot<Node> {
        DomRoot::from_ref(&self.root)
    }
}

impl HTMLCollectionMethods<crate::DomTypeHolder> for HTMLCollection {
    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-length>
    fn Length(&self) -> u32 {
        self.validate_cache();

        if let Some(cached_length) = self.cached_length.get().to_option() {
            // Cache hit
            cached_length
        } else {
            // Cache miss, calculate the length
            let length = self.elements_iter().count() as u32;
            self.cached_length.set(OptionU32::some(length));
            length
        }
    }

    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-item>
    fn Item(&self, index: u32) -> Option<DomRoot<Element>> {
        self.validate_cache();

        if let Some(element) = self.cached_cursor_element.get() {
            // Cache hit, the cursor element is set
            if let Some(cached_index) = self.cached_cursor_index.get().to_option() {
                if cached_index == index {
                    // The cursor is the element we're looking for.
                    return Some(element);
                }

                // Cursor-relative traversal is only possible for filter-based
                // collections, where elements follow tree order.
                if let CollectionKind::Filter(ref filter) = self.kind {
                    let node: DomRoot<Node> = DomRoot::upcast(element);
                    return if cached_index < index {
                        // Iterate forwards from the cursor.
                        let offset = index - (cached_index + 1);
                        self.set_cached_cursor(
                            index,
                            self.filter_iter_after(&node, filter.as_ref())
                                .nth(offset as usize),
                        )
                    } else {
                        // Iterate backwards from the cursor.
                        let offset = cached_index - (index + 1);
                        self.set_cached_cursor(
                            index,
                            self.filter_iter_before(&node, filter.as_ref())
                                .nth(offset as usize),
                        )
                    };
                }
            }
        }

        // Cache miss or source-based collection: iterate from the beginning.
        self.set_cached_cursor(index, self.elements_iter().nth(index as usize))
    }

    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-nameditem>
    fn NamedItem(&self, key: DOMString) -> Option<DomRoot<Element>> {
        // Step 1.
        if key.is_empty() {
            return None;
        }

        let key = Atom::from(key);

        // Step 2.
        self.elements_iter().find(|elem| {
            elem.get_id().is_some_and(|id| id == key) ||
                (elem.namespace() == &ns!(html) && elem.get_name().is_some_and(|id| id == key))
        })
    }

    /// <https://dom.spec.whatwg.org/#dom-htmlcollection-item>
    fn IndexedGetter(&self, index: u32) -> Option<DomRoot<Element>> {
        self.Item(index)
    }

    // check-tidy: no specs after this line
    fn NamedGetter(&self, name: DOMString) -> Option<DomRoot<Element>> {
        self.NamedItem(name)
    }

    /// <https://dom.spec.whatwg.org/#interface-htmlcollection>
    fn SupportedPropertyNames(&self) -> Vec<DOMString> {
        // Step 1
        let mut result = vec![];

        // Step 2
        for elem in self.elements_iter() {
            // Step 2.1
            if let Some(id_atom) = elem.get_id() {
                let id_str = DOMString::from(&*id_atom);
                if !result.contains(&id_str) {
                    result.push(id_str);
                }
            }
            // Step 2.2
            if *elem.namespace() == ns!(html) {
                if let Some(name_atom) = elem.get_name() {
                    let name_str = DOMString::from(&*name_atom);
                    if !result.contains(&name_str) {
                        result.push(name_str)
                    }
                }
            }
        }

        // Step 3
        result
    }
}