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.

3 files changed, 291 insertions, 78 deletions

diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index b39adbc53fc..0d778e700c9 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -26,7 +26,7 @@ use dom::bindings::refcounted::Trusted;
 use dom::bindings::reflector::{Reflectable, reflect_dom_object};
 use dom::bindings::trace::RootedVec;
 use dom::bindings::xmlname::XMLName::InvalidXMLName;
-use dom::bindings::xmlname::{validate_and_extract, xml_name_type};
+use dom::bindings::xmlname::{validate_and_extract, namespace_from_domstring, xml_name_type};
 use dom::comment::Comment;
 use dom::customevent::CustomEvent;
 use dom::documentfragment::DocumentFragment;
@@ -119,7 +119,6 @@ enum ParserBlockedByScript {
 pub struct Document {
     node: Node,
     window: JS<Window>,
-    idmap: DOMRefCell<HashMap<Atom, Vec<JS<Element>>>>,
     implementation: MutNullableHeap<JS<DOMImplementation>>,
     location: MutNullableHeap<JS<Location>>,
     content_type: DOMString,
@@ -128,6 +127,11 @@ pub struct Document {
     is_html_document: bool,
     url: Url,
     quirks_mode: Cell<QuirksMode>,
+    /// Caches for the getElement methods
+    id_map: DOMRefCell<HashMap<Atom, Vec<JS<Element>>>>,
+    tag_map: DOMRefCell<HashMap<Atom, JS<HTMLCollection>>>,
+    tagns_map: DOMRefCell<HashMap<QualName, JS<HTMLCollection>>>,
+    classes_map: DOMRefCell<HashMap<Vec<Atom>, JS<HTMLCollection>>>,
     images: MutNullableHeap<JS<HTMLCollection>>,
     embeds: MutNullableHeap<JS<HTMLCollection>>,
     links: MutNullableHeap<JS<HTMLCollection>>,
@@ -387,8 +391,8 @@ impl Document {
                                 to_unregister: &Element,
                                 id: Atom) {
         debug!("Removing named element from document {:p}: {:p} id={}", self, to_unregister, id);
-        let mut idmap = self.idmap.borrow_mut();
-        let is_empty = match idmap.get_mut(&id) {
+        let mut id_map = self.id_map.borrow_mut();
+        let is_empty = match id_map.get_mut(&id) {
             None => false,
             Some(elements) => {
                 let position = elements.iter()
@@ -399,7 +403,7 @@ impl Document {
             }
         };
         if is_empty {
-            idmap.remove(&id);
+            id_map.remove(&id);
         }
     }
 
@@ -411,12 +415,12 @@ impl Document {
         assert!(element.upcast::<Node>().is_in_doc());
         assert!(!id.is_empty());
 
-        let mut idmap = self.idmap.borrow_mut();
+        let mut id_map = self.id_map.borrow_mut();
 
         let root = self.GetDocumentElement().expect(
             "The element is in the document, so there must be a document element.");
 
-        match idmap.entry(id) {
+        match id_map.entry(id) {
             Vacant(entry) => {
                 entry.insert(vec![JS::from_ref(element)]);
             }
@@ -1278,7 +1282,6 @@ impl Document {
         Document {
             node: Node::new_document_node(),
             window: JS::from_ref(window),
-            idmap: DOMRefCell::new(HashMap::new()),
             implementation: Default::default(),
             location: Default::default(),
             content_type: match content_type {
@@ -1297,6 +1300,10 @@ impl Document {
             // https://dom.spec.whatwg.org/#concept-document-encoding
             encoding_name: DOMRefCell::new(DOMString("UTF-8".to_owned())),
             is_html_document: is_html_document == IsHTMLDocument::HTMLDocument,
+            id_map: DOMRefCell::new(HashMap::new()),
+            tag_map: DOMRefCell::new(HashMap::new()),
+            tagns_map: DOMRefCell::new(HashMap::new()),
+            classes_map: DOMRefCell::new(HashMap::new()),
             images: Default::default(),
             embeds: Default::default(),
             links: Default::default(),
@@ -1386,7 +1393,7 @@ impl Document {
     }
 
     pub fn get_element_by_id(&self, id: &Atom) -> Option<Root<Element>> {
-        self.idmap.borrow().get(&id).map(|ref elements| Root::from_ref(&*(*elements)[0]))
+        self.id_map.borrow().get(&id).map(|ref elements| Root::from_ref(&*(*elements)[0]))
     }
 
     pub fn record_element_state_change(&self, el: &Element, which: ElementState) {
@@ -1504,18 +1511,47 @@ impl DocumentMethods for Document {
 
     // https://dom.spec.whatwg.org/#dom-document-getelementsbytagname
     fn GetElementsByTagName(&self, tag_name: DOMString) -> Root<HTMLCollection> {
-        HTMLCollection::by_tag_name(&self.window, self.upcast(), tag_name)
+        let tag_atom = Atom::from_slice(&tag_name);
+        match self.tag_map.borrow_mut().entry(tag_atom.clone()) {
+            Occupied(entry) => Root::from_ref(entry.get()),
+            Vacant(entry) => {
+                let mut tag_copy = tag_name;
+                tag_copy.make_ascii_lowercase();
+                let ascii_lower_tag = Atom::from_slice(&tag_copy);
+                let result = HTMLCollection::by_atomic_tag_name(&self.window, self.upcast(), tag_atom, ascii_lower_tag);
+                entry.insert(JS::from_rooted(&result));
+                result
+            }
+        }
     }
 
     // https://dom.spec.whatwg.org/#dom-document-getelementsbytagnamens
     fn GetElementsByTagNameNS(&self, maybe_ns: Option<DOMString>, tag_name: DOMString)
                               -> Root<HTMLCollection> {
-        HTMLCollection::by_tag_name_ns(&self.window, self.upcast(), tag_name, maybe_ns)
+        let ns = namespace_from_domstring(maybe_ns);
+        let local = Atom::from_slice(&tag_name);
+        let qname = QualName::new(ns, local);
+        match self.tagns_map.borrow_mut().entry(qname.clone()) {
+            Occupied(entry) => Root::from_ref(entry.get()),
+            Vacant(entry) => {
+                let result = HTMLCollection::by_qual_tag_name(&self.window, self.upcast(), qname);
+                entry.insert(JS::from_rooted(&result));
+                result
+            }
+        }
     }
 
     // https://dom.spec.whatwg.org/#dom-document-getelementsbyclassname
     fn GetElementsByClassName(&self, classes: DOMString) -> Root<HTMLCollection> {
-        HTMLCollection::by_class_name(&self.window, self.upcast(), classes)
+        let class_atoms: Vec<Atom> = split_html_space_chars(&classes).map(Atom::from_slice).collect();
+        match self.classes_map.borrow_mut().entry(class_atoms.clone())  {
+            Occupied(entry) => Root::from_ref(entry.get()),
+            Vacant(entry) => {
+                let result = HTMLCollection::by_atomic_class_name(&self.window, self.upcast(), class_atoms);
+                entry.insert(JS::from_rooted(&result));
+                result
+            }
+        }
     }
 
     // https://dom.spec.whatwg.org/#dom-nonelementparentnode-getelementbyid
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
diff --git a/tests/wpt/mozilla/tests/mozilla/htmlcollection.html b/tests/wpt/mozilla/tests/mozilla/htmlcollection.html
index 440a4244a0e..57114d30a92 100644
--- a/tests/wpt/mozilla/tests/mozilla/htmlcollection.html
+++ b/tests/wpt/mozilla/tests/mozilla/htmlcollection.html
@@ -52,13 +52,68 @@
 
                 var new_live = document.createElement("div");
                 new_live.className = "live";
+                assert_equals(htmlcollection.length, 1);
+
                 document.body.appendChild(new_live);
                 assert_equals(htmlcollection.length, 2);
                 assert_equals(htmlcollection.item(1), new_live);
 
+                new_live.className = "dead";
+                assert_equals(htmlcollection.length, 1);
+
+                new_live.className = "live";
+                assert_equals(htmlcollection.length, 2);
+
                 document.body.removeChild(new_live);
                 assert_equals(htmlcollection.length, 1);
-            }, "live HTMLCollection");
+            }, "live HTMLCollection byClassName");
+
+            test(function() {
+                var element = document.createElement("div");
+                var coll = element.getElementsByTagName("div");
+                assert_equals(coll.length, 0);
+
+                element.innerHTML = '<div id="q1"><span id="q2">a</span><div id="q3">b</div><div id="q4">c</div></div>';
+                assert_equals(coll.length, 3);
+
+                var child = coll[0];
+                var grandchild = coll[1];
+                assert_equals(child.id, "q1");
+                assert_equals(grandchild.id, "q3");
+                assert_equals(grandchild.parentNode, child);
+                assert_equals(child.parentNode, element);
+
+                child.removeChild(grandchild);
+                assert_equals(coll.length, 2);
+
+                child.appendChild(grandchild);
+                assert_equals(coll.length, 3);
+            }, "live HTMLCollection byTagName");
+
+            test(function() {
+                var element = document.createElement("div");
+                var coll = element.getElementsByTagName("div");
+                assert_equals(coll.length, 0);
+
+                element.innerHTML = '<div id="n0"><div id="n1"><div id="n2"></div><div id="n3"></div></div></div>';
+                assert_equals(coll.length, 4);
+
+                assert_equals(coll[3].id, "n3");
+                assert_equals(coll[2].id, "n2");
+                assert_equals(coll[2].id, "n2");
+                assert_equals(coll[1].id, "n1");
+                assert_equals(coll[2].id, "n2");
+                assert_equals(coll[0].id, "n0");
+
+                assert_equals(coll[0].id, "n0");
+                assert_equals(coll[2].id, "n2");
+                assert_equals(coll[1].id, "n1");
+                assert_equals(coll[2].id, "n2");
+                assert_equals(coll[3].id, "n3");
+
+                assert_equals(coll.length, 4);
+
+            }, "HTMLCollection cursoring");
 
             test(function() {
                 assert_equals(document.getElementsByTagName("DIV").length, 5);