Auto merge of #8227 - asajeffrey:versioned_dom, r=eefriedman

Versioned dom

This PR adds versioning to the DOM. There are now node.get_version and node.get_descendent_version methods that return a counter that is bumped when the node is dirtied. This is used to implement cache invalidation for caching HTMLCollection state. Caching HTMCollections gets a 1000x speedup in the Dromaeo DOM query tests.

Addresses https://github.com/servo/servo/issues/6901, https://github.com/servo/servo/issues/3381 and https://github.com/servo/servo/issues/1916.

Replaces PR https://github.com/servo/servo/pull/6927.

<!-- Reviewable:start -->
[<img src="https://reviewable.io/review_button.png" height=40 alt="Review on Reviewable"/>](https://reviewable.io/reviews/servo/servo/8227)
<!-- Reviewable:end -->

4 files changed, 260 insertions, 79 deletions

diff --git a/components/script/dom/bindings/trace.rs b/components/script/dom/bindings/trace.rs
index 5d4e0a603f5..9b592e731f7 100644
--- a/components/script/dom/bindings/trace.rs
+++ b/components/script/dom/bindings/trace.rs
@@ -81,7 +81,7 @@ use std::rc::Rc;
 use std::sync::Arc;
 use std::sync::atomic::AtomicBool;
 use std::sync::mpsc::{Receiver, Sender};
-use string_cache::{Atom, Namespace};
+use string_cache::{Atom, Namespace, QualName};
 use style::properties::PropertyDeclarationBlock;
 use style::values::specified::Length;
 use url::Url;
@@ -257,7 +257,7 @@ no_jsmanaged_fields!(Size2D<T>);
 no_jsmanaged_fields!(Arc<T>);
 no_jsmanaged_fields!(Image, ImageCacheChan, ImageCacheTask);
 no_jsmanaged_fields!(Metadata);
-no_jsmanaged_fields!(Atom, Namespace);
+no_jsmanaged_fields!(Atom, Namespace, QualName);
 no_jsmanaged_fields!(Trusted<T: Reflectable>);
 no_jsmanaged_fields!(PropertyDeclarationBlock);
 no_jsmanaged_fields!(HashSet<T>);
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index 14c4f5da5e9..c077a4f5769 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;
@@ -124,7 +124,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,
@@ -133,6 +132,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>>,
@@ -396,8 +400,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()
@@ -408,7 +412,7 @@ impl Document {
             }
         };
         if is_empty {
-            idmap.remove(&id);
+            id_map.remove(&id);
         }
     }
 
@@ -420,12 +424,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)]);
             }
@@ -1310,7 +1314,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 {
@@ -1329,6 +1332,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(),
@@ -1445,7 +1452,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 element_state_will_change(&self, el: &Element) {
@@ -1554,18 +1561,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/components/script/dom/node.rs b/components/script/dom/node.rs
index d3eb716d05d..49bb441e21e 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -57,6 +57,7 @@ use selectors::parser::Selector;
 use selectors::parser::parse_author_origin_selector_list_from_str;
 use std::borrow::ToOwned;
 use std::cell::{Cell, Ref, RefCell, RefMut};
+use std::cmp::max;
 use std::default::Default;
 use std::iter::{self, FilterMap, Peekable};
 use std::mem;
@@ -105,6 +106,9 @@ pub struct Node {
     /// A bitfield of flags for node items.
     flags: Cell<NodeFlags>,
 
+    /// The maximum version of any inclusive descendant of this node.
+    inclusive_descendants_version: Cell<u64>,
+
     /// Layout information. Only the layout task may touch this data.
     ///
     /// Must be sent back to the layout task to be destroyed when this
@@ -489,6 +493,19 @@ impl Node {
     }
 
     pub fn dirty_impl(&self, damage: NodeDamage, force_ancestors: bool) {
+
+        // 0. Set version counter
+        // The new version counter is 1 plus the max of the node's current version counter,
+        // its descendants version, and the document's version. Normally, this will just be
+        // the document's version, but we do have to deal with the case where the node has moved
+        // document, so may have a higher version count than its owning document.
+        let doc: Root<Node> = Root::upcast(self.owner_doc());
+        let version = max(self.get_inclusive_descendants_version(), doc.get_inclusive_descendants_version()) + 1;
+        for ancestor in self.inclusive_ancestors() {
+            ancestor.inclusive_descendants_version.set(version);
+        }
+        doc.inclusive_descendants_version.set(version);
+
         // 1. Dirty self.
         match damage {
             NodeDamage::NodeStyleDamaged => {}
@@ -520,6 +537,11 @@ impl Node {
         }
     }
 
+    /// The maximum version number of this node's descendants, including itself
+    pub fn get_inclusive_descendants_version(&self) -> u64 {
+        self.inclusive_descendants_version.get()
+    }
+
     /// Iterates over this node and all its descendants, in preorder.
     pub fn traverse_preorder(&self) -> TreeIterator {
         TreeIterator::new(self)
@@ -1284,6 +1306,7 @@ impl Node {
             child_list: Default::default(),
             children_count: Cell::new(0u32),
             flags: Cell::new(flags),
+            inclusive_descendants_version: Cell::new(0),
 
             layout_data: LayoutDataRef::new(),