Optimise Node.childNodes

We use the virtual method children_changed() to propagate changes in the children
list to the NodeList tied to Node.childNodes.

3 files changed, 207 insertions, 15 deletions

diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index e8cb5641e29..09aadc71be9 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -40,7 +40,7 @@ use dom::element::{AttributeHandlers, Element, ElementCreator, ElementTypeId};
 use dom::element::ElementHelpers;
 use dom::eventtarget::{EventTarget, EventTargetTypeId};
 use dom::htmlelement::HTMLElementTypeId;
-use dom::nodelist::NodeList;
+use dom::nodelist::{NodeList, NodeListHelpers};
 use dom::processinginstruction::{ProcessingInstruction, ProcessingInstructionHelpers};
 use dom::text::Text;
 use dom::virtualmethods::{VirtualMethods, vtable_for};
@@ -2582,6 +2582,9 @@ impl<'a> VirtualMethods for &'a Node {
                 self.children_count.set(added.len() as u32);
             },
         }
+        if let Some(list) = self.child_list.get().map(|list| list.root()) {
+            list.as_children_list().children_changed(mutation);
+        }
     }
 }
 
diff --git a/components/script/dom/nodelist.rs b/components/script/dom/nodelist.rs
index 35ed6861459..0c6583a684d 100644
--- a/components/script/dom/nodelist.rs
+++ b/components/script/dom/nodelist.rs
@@ -2,19 +2,22 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
+use dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
 use dom::bindings::codegen::Bindings::NodeListBinding;
 use dom::bindings::codegen::Bindings::NodeListBinding::NodeListMethods;
 use dom::bindings::global::GlobalRef;
-use dom::bindings::js::{JS, Root};
+use dom::bindings::js::{JS, MutNullableHeap, Root};
 use dom::bindings::utils::{Reflector, reflect_dom_object};
-use dom::node::{Node, NodeHelpers};
+use dom::node::{ChildrenMutation, Node, NodeHelpers};
 use dom::window::Window;
 
+use std::cell::Cell;
+
 #[derive(JSTraceable)]
 #[must_root]
 pub enum NodeListType {
     Simple(Vec<JS<Node>>),
-    Children(JS<Node>)
+    Children(ChildrenList),
 }
 
 // https://dom.spec.whatwg.org/#interface-nodelist
@@ -45,7 +48,7 @@ impl NodeList {
     }
 
     pub fn new_child_list(window: &Window, node: &Node) -> Root<NodeList> {
-        NodeList::new(window, NodeListType::Children(JS::from_ref(node)))
+        NodeList::new(window, NodeListType::Children(ChildrenList::new(node)))
     }
 }
 
@@ -54,22 +57,17 @@ impl<'a> NodeListMethods for &'a NodeList {
     fn Length(self) -> u32 {
         match self.list_type {
             NodeListType::Simple(ref elems) => elems.len() as u32,
-            NodeListType::Children(ref node) => {
-                let node = node.root();
-                node.r().children().count() as u32
-            }
+            NodeListType::Children(ref list) => list.len(),
         }
     }
 
     // https://dom.spec.whatwg.org/#dom-nodelist-item
     fn Item(self, index: u32) -> Option<Root<Node>> {
         match self.list_type {
-            _ if index >= self.Length() => None,
-            NodeListType::Simple(ref elems) => Some(elems[index as usize].root()),
-            NodeListType::Children(ref node) => {
-                let node = node.root();
-                node.r().children().nth(index as usize)
-            }
+            NodeListType::Simple(ref elems) => {
+                elems.get(index as usize).map(|node| Root::from_rooted(*node))
+            },
+            NodeListType::Children(ref list) => list.item(index),
         }
     }
 
@@ -81,3 +79,193 @@ impl<'a> NodeListMethods for &'a NodeList {
     }
 }
 
+pub trait NodeListHelpers<'a> {
+    fn as_children_list(self) -> &'a ChildrenList;
+}
+
+impl<'a> NodeListHelpers<'a> for &'a NodeList {
+    fn as_children_list(self) -> &'a ChildrenList {
+        if let NodeListType::Children(ref list) = self.list_type {
+            list
+        } else {
+            panic!("called as_children_list() on a simple node list")
+        }
+    }
+}
+
+#[derive(JSTraceable)]
+#[must_root]
+pub struct ChildrenList {
+    node: JS<Node>,
+    last_visited: MutNullableHeap<JS<Node>>,
+    last_index: Cell<u32>,
+}
+
+impl ChildrenList {
+    fn new(node: &Node) -> ChildrenList {
+        let last_visited = node.GetFirstChild();
+        ChildrenList {
+            node: JS::from_ref(node),
+            last_visited:
+                MutNullableHeap::new(last_visited.as_ref().map(JS::from_rooted)),
+            last_index: Cell::new(0u32),
+        }
+    }
+
+    pub fn len(&self) -> u32 {
+        self.node.root().children_count()
+    }
+
+    pub fn item(&self, index: u32) -> Option<Root<Node>> {
+        // This always start traversing the children from the closest element
+        // among parent's first and last children and the last visited one.
+        let len = self.len() as u32;
+        if index >= len {
+            return None;
+        }
+        if index == 0u32 {
+            // Item is first child if any, not worth updating last visited.
+            return self.node.root().GetFirstChild();
+        }
+        let last_index = self.last_index.get();
+        if index == last_index {
+            // Item is last visited child, no need to update last visited.
+            return Some(self.last_visited.get().unwrap().root());
+        }
+        let last_visited = if index - 1u32 == last_index {
+            // Item is last visited's next sibling.
+            self.last_visited.get().unwrap().root().GetNextSibling().unwrap()
+        } else if last_index > 0 && index == last_index - 1u32 {
+            // Item is last visited's previous sibling.
+            self.last_visited.get().unwrap().root().GetPreviousSibling().unwrap()
+        } else if index > last_index {
+            if index == len - 1u32 {
+                // Item is parent's last child, not worth updating last visited.
+                return Some(self.node.root().GetLastChild().unwrap());
+            }
+            if index <= last_index + (len - last_index) / 2u32 {
+                // Item is closer to the last visited child and follows it.
+                self.last_visited.get().unwrap().root()
+                                 .inclusively_following_siblings()
+                                 .nth((index - last_index) as usize).unwrap()
+            } else {
+                // Item is closer to parent's last child and obviously
+                // precedes it.
+                self.node.root().GetLastChild().unwrap()
+                    .inclusively_preceding_siblings()
+                    .nth((len - index - 1u32) as usize).unwrap()
+            }
+        } else if index >= last_index / 2u32 {
+            // Item is closer to the last visited child and precedes it.
+            self.last_visited.get().unwrap().root()
+                             .inclusively_preceding_siblings()
+                             .nth((last_index - index) as usize).unwrap()
+        } else {
+            // Item is closer to parent's first child and obviously follows it.
+            debug_assert!(index < last_index / 2u32);
+            self.node.root().GetFirstChild().unwrap()
+                     .inclusively_following_siblings()
+                     .nth(index as usize)
+                     .unwrap()
+        };
+        self.last_visited.set(Some(JS::from_rooted(&last_visited)));
+        self.last_index.set(index);
+        Some(last_visited)
+    }
+
+    pub fn children_changed(&self, mutation: &ChildrenMutation) {
+        fn prepend(list: &ChildrenList, added: &[&Node], next: &Node) {
+            let len = added.len() as u32;
+            if len == 0u32 {
+                return;
+            }
+            let index = list.last_index.get();
+            if index < len {
+                list.last_visited.set(Some(JS::from_ref(added[index as usize])));
+            } else if index / 2u32 >= len {
+                // If last index is twice as large as the number of added nodes,
+                // updating only it means that less nodes will be traversed if
+                // caller is traversing the node list linearly.
+                list.last_index.set(len + index);
+            } else {
+                // If last index is not twice as large but still larger,
+                // it's better to update it to the number of added nodes.
+                list.last_visited.set(Some(JS::from_ref(next)));
+                list.last_index.set(len);
+            }
+        }
+
+        fn replace(list: &ChildrenList,
+                   prev: Option<&Node>,
+                   removed: &Node,
+                   added: &[&Node],
+                   next: Option<&Node>) {
+            let index = list.last_index.get();
+            if removed == &*list.last_visited.get().unwrap().root() {
+                let visited = match (prev, added, next) {
+                    (None, _, None) => {
+                        // Such cases where parent had only one child should
+                        // have been changed into ChildrenMutation::ReplaceAll
+                        // by ChildrenMutation::replace().
+                        unreachable!()
+                    },
+                    (_, [node, ..], _) => node,
+                    (_, [], Some(next)) => next,
+                    (Some(prev), [], None) => {
+                        list.last_index.set(index - 1u32);
+                        prev
+                    },
+                };
+                list.last_visited.set(Some(JS::from_ref(visited)));
+            } else {
+                match (prev, next) {
+                    (Some(_), None) => {},
+                    (None, Some(next)) => {
+                        list.last_index.set(index - 1);
+                        prepend(list, added, next);
+                    },
+                    (Some(_), Some(_)) => {
+                        list.reset();
+                    },
+                    (None, None) => unreachable!(),
+                }
+            }
+        }
+
+        match *mutation {
+            ChildrenMutation::Append { .. } => {},
+            ChildrenMutation::Insert { .. } => {
+                self.reset();
+            },
+            ChildrenMutation::Prepend { added, next } => {
+                prepend(self, added, next);
+            },
+            ChildrenMutation::Replace { prev, removed, added, next } => {
+                replace(self, prev, removed, added, next);
+            },
+            ChildrenMutation::ReplaceAll { added, .. } => {
+                let len = added.len();
+                let index = self.last_index.get();
+                if len == 0 {
+                    self.last_visited.set(None);
+                    self.last_index.set(0u32);
+                } else if index < len as u32 {
+                    self.last_visited.set(Some(JS::from_ref(added[index as usize])));
+                } else {
+                    // Setting last visited to parent's last child serves no purpose,
+                    // so the middle is arbitrarily chosen here in case the caller
+                    // wants random access.
+                    let middle = len / 2;
+                    self.last_visited.set(Some(JS::from_ref(added[middle])));
+                    self.last_index.set(middle as u32);
+                }
+            },
+        }
+    }
+
+    fn reset(&self) {
+        self.last_visited.set(
+            self.node.root().GetFirstChild().map(|node| JS::from_rooted(&node)));
+        self.last_index.set(0u32);
+    }
+}
diff --git a/components/script/lib.rs b/components/script/lib.rs
index 640aad8e6e1..21d78eaf61f 100644
--- a/components/script/lib.rs
+++ b/components/script/lib.rs
@@ -21,6 +21,7 @@
 #![feature(plugin)]
 #![feature(ref_slice)]
 #![feature(rc_unique)]
+#![feature(slice_patterns)]
 #![feature(str_utf16)]
 #![feature(unicode)]
 #![feature(vec_push_all)]