Caching HTMCollections.

We cache the state of any live HTMLCollection, keeping track of

a) the optional cached length of the collection, and
b) an optional cursor into the collection (a node in the collection plus its index).

The cache is invalidated based on the version number of the node.

We use these caches for speeding up random access to the collection.
When returning coll[i], we search from the cursor, if it exists,
and otherwise search from the front of the collection.
In particular, both a forward for-loop and a backward for-loop
through the collection will now have each access take O(1)
time rather than O(n) time.

This gets 1000x speed-up on the relevant Dromaeo DOM query tests.

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