diff options
Diffstat (limited to 'components/script/dom/htmlcollection.rs')
| -rw-r--r-- | components/script/dom/htmlcollection.rs | 252 |
1 files changed, 187 insertions, 65 deletions
diff --git a/components/script/dom/htmlcollection.rs b/components/script/dom/htmlcollection.rs index 18b495a6f00..b645449dcc1 100644 --- a/components/script/dom/htmlcollection.rs +++ b/components/script/dom/htmlcollection.rs @@ -6,76 +6,169 @@ use dom::bindings::codegen::Bindings::HTMLCollectionBinding; use dom::bindings::codegen::Bindings::HTMLCollectionBinding::HTMLCollectionMethods; use dom::bindings::global::GlobalRef; use dom::bindings::inheritance::Castable; -use dom::bindings::js::{JS, Root}; +use dom::bindings::js::{JS, Root, MutNullableHeap}; use dom::bindings::reflector::{Reflector, reflect_dom_object}; use dom::bindings::trace::JSTraceable; use dom::bindings::xmlname::namespace_from_domstring; use dom::element::Element; -use dom::node::{Node, TreeIterator}; +use dom::node::{Node, FollowingNodeIterator, PrecedingNodeIterator}; use dom::window::Window; use std::ascii::AsciiExt; -use string_cache::{Atom, Namespace}; +use std::cell::Cell; +use string_cache::{Atom, Namespace, QualName}; use util::str::{DOMString, split_html_space_chars}; pub trait CollectionFilter : JSTraceable { fn filter<'a>(&self, elem: &'a Element, root: &'a Node) -> bool; } -#[derive(JSTraceable)] -#[must_root] -pub struct Collection(JS<Node>, Box<CollectionFilter + 'static>); +// An optional u32, using maxint 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, HeapSizeOf)] +struct OptionU32 { + bits: u32, +} + +impl OptionU32 { + fn to_option(self) -> Option<u32> { + if self.bits == u32::max_value() { + None + } else { + Some(self.bits) + } + } + + fn some(bits: u32) -> OptionU32 { + assert!(bits != u32::max_value()); + OptionU32 { bits: bits } + } + + fn none() -> OptionU32 { + OptionU32 { bits: u32::max_value() } + } +} #[dom_struct] pub struct HTMLCollection { reflector_: Reflector, + root: JS<Node>, #[ignore_heap_size_of = "Contains a trait object; can't measure due to #6870"] - collection: Collection, + filter: Box<CollectionFilter + 'static>, + // 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: MutNullableHeap<JS<Element>>, + cached_cursor_index: Cell<OptionU32>, + cached_length: Cell<OptionU32>, } impl HTMLCollection { #[allow(unrooted_must_root)] - fn new_inherited(collection: Collection) -> HTMLCollection { + fn new_inherited(root: &Node, filter: Box<CollectionFilter + 'static>) -> HTMLCollection { HTMLCollection { reflector_: Reflector::new(), - collection: collection, + root: JS::from_ref(root), + filter: filter, + // Default values for the cache + cached_version: Cell::new(root.get_inclusive_descendants_version()), + cached_cursor_element: MutNullableHeap::new(None), + cached_cursor_index: Cell::new(OptionU32::none()), + cached_length: Cell::new(OptionU32::none()), } } #[allow(unrooted_must_root)] - pub fn new(window: &Window, collection: Collection) -> Root<HTMLCollection> { - reflect_dom_object(box HTMLCollection::new_inherited(collection), + pub fn new(window: &Window, root: &Node, filter: Box<CollectionFilter + 'static>) -> Root<HTMLCollection> { + reflect_dom_object(box HTMLCollection::new_inherited(root, filter), GlobalRef::Window(window), HTMLCollectionBinding::Wrap) } pub fn create(window: &Window, root: &Node, filter: Box<CollectionFilter + 'static>) -> Root<HTMLCollection> { - HTMLCollection::new(window, Collection(JS::from_ref(root), filter)) + HTMLCollection::new(window, root, filter) } - fn all_elements(window: &Window, root: &Node, - namespace_filter: Option<Namespace>) -> Root<HTMLCollection> { - #[derive(JSTraceable, HeapSizeOf)] - struct AllElementFilter { - namespace_filter: Option<Namespace> + 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.get_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()); } - impl CollectionFilter for AllElementFilter { - fn filter(&self, elem: &Element, _root: &Node) -> bool { - match self.namespace_filter { - None => true, - Some(ref namespace) => *elem.namespace() == *namespace + } + + fn get_length(&self) -> u32 { + // Call validate_cache before calling this method! + 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 + } + } + + fn set_cached_cursor(&self, index: u32, element: Option<Root<Element>>) -> Option<Root<Element>> { + if let Some(element) = element { + self.cached_cursor_index.set(OptionU32::some(index)); + self.cached_cursor_element.set(Some(element.r())); + Some(element) + } else { + None + } + } + + fn get_item(&self, index: u32) -> Option<Root<Element>> { + // Call validate_cache before calling this method! + 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 + Some(element) + } else if cached_index < index { + // The cursor is before the element we're looking for + // Iterate forwards, starting at the cursor. + let offset = index - (cached_index + 1); + let node: Root<Node> = Root::upcast(element); + self.set_cached_cursor(index, self.elements_iter_after(node.r()).nth(offset as usize)) + } else { + // The cursor is after the element we're looking for + // Iterate backwards, starting at the cursor. + let offset = cached_index - (index + 1); + let node: Root<Node> = Root::upcast(element); + self.set_cached_cursor(index, self.elements_iter_before(node.r()).nth(offset as usize)) } + } else { + // Cache miss + // Iterate forwards through all the nodes + self.set_cached_cursor(index, self.elements_iter().nth(index as usize)) } + } else { + // Cache miss + // Iterate forwards through all the nodes + self.set_cached_cursor(index, self.elements_iter().nth(index as usize)) } - let filter = AllElementFilter { namespace_filter: namespace_filter }; - HTMLCollection::create(window, root, box filter) } pub fn by_tag_name(window: &Window, root: &Node, mut tag: DOMString) -> Root<HTMLCollection> { - if tag == "*" { - return HTMLCollection::all_elements(window, root, None); - } + let tag_atom = Atom::from_slice(&tag); + tag.make_ascii_lowercase(); + let ascii_lower_tag = Atom::from_slice(&tag); + HTMLCollection::by_atomic_tag_name(window, root, tag_atom, ascii_lower_tag) + } + pub fn by_atomic_tag_name(window: &Window, root: &Node, tag_atom: Atom, ascii_lower_tag: Atom) + -> Root<HTMLCollection> { #[derive(JSTraceable, HeapSizeOf)] struct TagNameFilter { tag: Atom, @@ -83,16 +176,15 @@ impl HTMLCollection { } impl CollectionFilter for TagNameFilter { fn filter(&self, elem: &Element, _root: &Node) -> bool { - if elem.html_element_in_html_document() { + if self.tag == atom!("*") { + true + } else if elem.html_element_in_html_document() { *elem.local_name() == self.ascii_lower_tag } else { *elem.local_name() == self.tag } } } - let tag_atom = Atom::from_slice(&tag); - tag.make_ascii_lowercase(); - let ascii_lower_tag = Atom::from_slice(&tag); let filter = TagNameFilter { tag: tag_atom, ascii_lower_tag: ascii_lower_tag, @@ -102,39 +194,37 @@ impl HTMLCollection { pub fn by_tag_name_ns(window: &Window, root: &Node, tag: DOMString, maybe_ns: Option<DOMString>) -> Root<HTMLCollection> { - let namespace_filter = match maybe_ns { - Some(ref namespace) if namespace == &"*" => None, - ns => Some(namespace_from_domstring(ns)), - }; + let local = Atom::from_slice(&tag); + let ns = namespace_from_domstring(maybe_ns); + let qname = QualName::new(ns, local); + HTMLCollection::by_qual_tag_name(window, root, qname) + } - if tag == "*" { - return HTMLCollection::all_elements(window, root, namespace_filter); - } + pub fn by_qual_tag_name(window: &Window, root: &Node, qname: QualName) -> Root<HTMLCollection> { #[derive(JSTraceable, HeapSizeOf)] struct TagNameNSFilter { - tag: Atom, - namespace_filter: Option<Namespace> + qname: QualName } impl CollectionFilter for TagNameNSFilter { fn filter(&self, elem: &Element, _root: &Node) -> bool { - let ns_match = match self.namespace_filter { - Some(ref namespace) => { - *elem.namespace() == *namespace - }, - None => true - }; - ns_match && *elem.local_name() == self.tag + ((self.qname.ns == Namespace(atom!("*"))) || (self.qname.ns == *elem.namespace())) + && ((self.qname.local == atom!("*")) || (self.qname.local == *elem.local_name())) } } let filter = TagNameNSFilter { - tag: Atom::from_slice(&tag), - namespace_filter: namespace_filter + qname: qname }; HTMLCollection::create(window, root, box filter) } pub fn by_class_name(window: &Window, root: &Node, classes: DOMString) -> Root<HTMLCollection> { + let class_atoms = split_html_space_chars(&classes).map(Atom::from_slice).collect(); + HTMLCollection::by_atomic_class_name(window, root, class_atoms) + } + + pub fn by_atomic_class_name(window: &Window, root: &Node, classes: Vec<Atom>) + -> Root<HTMLCollection> { #[derive(JSTraceable, HeapSizeOf)] struct ClassNameFilter { classes: Vec<Atom> @@ -145,9 +235,7 @@ impl HTMLCollection { } } let filter = ClassNameFilter { - classes: split_html_space_chars(&classes).map(|class| { - Atom::from_slice(class) - }).collect() + classes: classes }; HTMLCollection::create(window, root, box filter) } @@ -163,21 +251,34 @@ impl HTMLCollection { HTMLCollection::create(window, root, box ElementChildFilter) } - pub fn elements_iter(&self) -> HTMLCollectionElementsIter { - let ref filter = self.collection.1; - let root = Root::from_ref(&*self.collection.0); - let mut node_iter = root.traverse_preorder(); - let _ = node_iter.next(); // skip the root node + pub fn elements_iter_after(&self, after: &Node) -> HTMLCollectionElementsIter { + // Iterate forwards from a node. HTMLCollectionElementsIter { - node_iter: node_iter, - root: root, - filter: filter, + node_iter: after.following_nodes(&self.root), + root: Root::from_ref(&self.root), + filter: &self.filter, + } + } + + pub fn elements_iter(&self) -> HTMLCollectionElementsIter { + // Iterate forwards from the root. + self.elements_iter_after(&*self.root) + } + + pub fn elements_iter_before(&self, before: &Node) -> HTMLCollectionElementsRevIter { + // Iterate backwards from a node. + HTMLCollectionElementsRevIter { + node_iter: before.preceding_nodes(&self.root), + root: Root::from_ref(&self.root), + filter: &self.filter, } } + } +// TODO: Make this generic, and avoid code duplication pub struct HTMLCollectionElementsIter<'a> { - node_iter: TreeIterator, + node_iter: FollowingNodeIterator, root: Root<Node>, filter: &'a Box<CollectionFilter>, } @@ -186,24 +287,45 @@ impl<'a> Iterator for HTMLCollectionElementsIter<'a> { type Item = Root<Element>; fn next(&mut self) -> Option<Self::Item> { - let filter = self.filter; - let root = self.root.r(); + let ref filter = self.filter; + let ref root = self.root; self.node_iter.by_ref() .filter_map(Root::downcast) .filter(|element| filter.filter(&element, root)) .next() + } +} + +pub struct HTMLCollectionElementsRevIter<'a> { + node_iter: PrecedingNodeIterator, + root: Root<Node>, + filter: &'a Box<CollectionFilter>, +} + +impl<'a> Iterator for HTMLCollectionElementsRevIter<'a> { + type Item = Root<Element>; + + fn next(&mut self) -> Option<Self::Item> { + let ref filter = self.filter; + let ref root = self.root; + self.node_iter.by_ref() + .filter_map(Root::downcast) + .filter(|element| filter.filter(&element, root)) + .next() } } impl HTMLCollectionMethods for HTMLCollection { // https://dom.spec.whatwg.org/#dom-htmlcollection-length fn Length(&self) -> u32 { - self.elements_iter().count() as u32 + self.validate_cache(); + self.get_length() } // https://dom.spec.whatwg.org/#dom-htmlcollection-item fn Item(&self, index: u32) -> Option<Root<Element>> { - self.elements_iter().nth(index as usize) + self.validate_cache(); + self.get_item(index) } // https://dom.spec.whatwg.org/#dom-htmlcollection-nameditem |