Auto merge of #6660 - nox:children-changed, r=jdm

Introduce VirtualMethods::children_changed()

This virtual method mimics the behaviour of mutation observers and make it more viable than the older child_inserted(), which didn't cover removed nodes and was called as many times as there were inserted nodes.

A few other shortcomings where remove_child() was called directly instead of Node::remove() were also fixed while at it.

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

11 files changed, 217 insertions, 199 deletions

diff --git a/components/script/dom/bindings/trace.rs b/components/script/dom/bindings/trace.rs
index a2c82b80722..ad8da0e41b0 100644
--- a/components/script/dom/bindings/trace.rs
+++ b/components/script/dom/bindings/trace.rs
@@ -70,6 +70,7 @@ use std::collections::hash_state::HashState;
 use std::ffi::CString;
 use std::hash::{Hash, Hasher};
 use std::intrinsics::return_address;
+use std::mem;
 use std::ops::{Deref, DerefMut};
 use std::rc::Rc;
 use std::sync::Arc;
@@ -482,6 +483,13 @@ impl<T: JSTraceable + Reflectable> RootedVec<T> {
     }
 }
 
+impl<T: JSTraceable + Reflectable> RootedVec<JS<T>> {
+    /// Obtain a safe slice of references that can't outlive that RootedVec.
+    pub fn r(&self) -> &[&T] {
+        unsafe { mem::transmute(&*self.v) }
+    }
+}
+
 impl<T: JSTraceable + Reflectable> Drop for RootedVec<T> {
     fn drop(&mut self) {
         RootedTraceableSet::remove(self);
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index d074dca0d4e..0e494b79a89 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -733,15 +733,13 @@ impl<'a> DocumentHelpers<'a> for &'a Document {
         // Set hover state for any elements in the current mouse over list.
         // Check if any of them changed state to determine whether to
         // force a reflow below.
-        for target in mouse_over_targets.iter() {
-            let target = target.root();
-            let target_ref = target.r();
-            if !target_ref.get_hover_state() {
-                target_ref.set_hover_state(true);
+        for target in mouse_over_targets.r() {
+            if !target.get_hover_state() {
+                target.set_hover_state(true);
 
-                let target = EventTargetCast::from_ref(target_ref);
+                let target = EventTargetCast::from_ref(*target);
 
-                self.fire_mouse_event(point, &target, "mouseover".to_owned());
+                self.fire_mouse_event(point, target, "mouseover".to_owned());
 
             }
         }
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 0fb55d0ff82..dd6afd3061b 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -866,9 +866,9 @@ impl<'a> AttributeHandlers for &'a Element {
     fn get_attribute(self, namespace: &Namespace, local_name: &Atom) -> Option<Root<Attr>> {
         let mut attributes = RootedVec::new();
         self.get_attributes(local_name, &mut attributes);
-        attributes.iter()
-                  .map(|attr| attr.root())
-                  .find(|attr| attr.r().namespace() == namespace)
+        attributes.r().iter()
+                  .find(|attr| attr.namespace() == namespace)
+                  .map(|attr| Root::from_ref(*attr))
     }
 
     // https://dom.spec.whatwg.org/#concept-element-attributes-get-by-name
diff --git a/components/script/dom/eventdispatcher.rs b/components/script/dom/eventdispatcher.rs
index 8633f63df7c..0c6c7e14b18 100644
--- a/components/script/dom/eventdispatcher.rs
+++ b/components/script/dom/eventdispatcher.rs
@@ -41,14 +41,13 @@ pub fn dispatch_event<'a, 'b>(target: &'a EventTarget,
     //FIXME: The "callback this value" should be currentTarget
 
     /* capturing */
-    for cur_target in chain.iter().rev() {
-        let cur_target = cur_target.root();
-        let stopped = match cur_target.r().get_listeners_for(&type_, ListenerPhase::Capturing) {
+    for cur_target in chain.r().iter().rev() {
+        let stopped = match cur_target.get_listeners_for(&type_, ListenerPhase::Capturing) {
             Some(listeners) => {
-                event.set_current_target(cur_target.r());
+                event.set_current_target(cur_target);
                 for listener in listeners.iter() {
                     // Explicitly drop any exception on the floor.
-                    let _ = listener.HandleEvent_(cur_target.r(), event, Report);
+                    let _ = listener.HandleEvent_(*cur_target, event, Report);
 
                     if event.stop_immediate() {
                         break;
@@ -87,14 +86,13 @@ pub fn dispatch_event<'a, 'b>(target: &'a EventTarget,
     if event.bubbles() && !event.stop_propagation() {
         event.set_phase(EventPhase::Bubbling);
 
-        for cur_target in chain.iter() {
-            let cur_target = cur_target.root();
-            let stopped = match cur_target.r().get_listeners_for(&type_, ListenerPhase::Bubbling) {
+        for cur_target in chain.r() {
+            let stopped = match cur_target.get_listeners_for(&type_, ListenerPhase::Bubbling) {
                 Some(listeners) => {
-                    event.set_current_target(cur_target.r());
+                    event.set_current_target(cur_target);
                     for listener in listeners.iter() {
                         // Explicitly drop any exception on the floor.
-                        let _ = listener.HandleEvent_(cur_target.r(), event, Report);
+                        let _ = listener.HandleEvent_(*cur_target, event, Report);
 
                         if event.stop_immediate() {
                             break;
diff --git a/components/script/dom/htmlscriptelement.rs b/components/script/dom/htmlscriptelement.rs
index 8bdbdb8759e..3329e0f0af9 100644
--- a/components/script/dom/htmlscriptelement.rs
+++ b/components/script/dom/htmlscriptelement.rs
@@ -27,7 +27,8 @@ use dom::eventtarget::{EventTarget, EventTargetTypeId};
 use dom::event::{Event, EventBubbles, EventCancelable, EventHelpers};
 use dom::element::ElementTypeId;
 use dom::htmlelement::{HTMLElement, HTMLElementTypeId};
-use dom::node::{Node, NodeHelpers, NodeTypeId, document_from_node, window_from_node, CloneChildrenFlag};
+use dom::node::{ChildrenMutation, CloneChildrenFlag, Node, NodeHelpers};
+use dom::node::{NodeTypeId, document_from_node, window_from_node};
 use dom::servohtmlparser::ServoHTMLParserHelpers;
 use dom::virtualmethods::VirtualMethods;
 use dom::window::{WindowHelpers, ScriptHelpers};
@@ -564,9 +565,9 @@ impl<'a> VirtualMethods for &'a HTMLScriptElement {
         }
     }
 
-    fn child_inserted(&self, child: &Node) {
+    fn children_changed(&self, mutation: &ChildrenMutation) {
         if let Some(ref s) = self.super_type() {
-            s.child_inserted(child);
+            s.children_changed(mutation);
         }
         let node = NodeCast::from_ref(*self);
         if !self.parser_inserted.get() && node.is_in_doc() {
diff --git a/components/script/dom/htmlstyleelement.rs b/components/script/dom/htmlstyleelement.rs
index 7c1c06412ef..22c4c705ccb 100644
--- a/components/script/dom/htmlstyleelement.rs
+++ b/components/script/dom/htmlstyleelement.rs
@@ -11,7 +11,8 @@ use dom::document::Document;
 use dom::eventtarget::{EventTarget, EventTargetTypeId};
 use dom::element::{ElementTypeId, AttributeHandlers};
 use dom::htmlelement::{HTMLElement, HTMLElementTypeId};
-use dom::node::{Node, NodeHelpers, NodeTypeId, window_from_node};
+use dom::node::{ChildrenMutation, Node, NodeHelpers, NodeTypeId};
+use dom::node::window_from_node;
 use dom::virtualmethods::VirtualMethods;
 use dom::window::WindowHelpers;
 use layout_interface::{LayoutChan, Msg};
@@ -86,11 +87,10 @@ impl<'a> VirtualMethods for &'a HTMLStyleElement {
         Some(htmlelement as &VirtualMethods)
     }
 
-    fn child_inserted(&self, child: &Node) {
+    fn children_changed(&self, mutation: &ChildrenMutation) {
         if let Some(ref s) = self.super_type() {
-            s.child_inserted(child);
+            s.children_changed(mutation);
         }
-
         let node = NodeCast::from_ref(*self);
         if node.is_in_doc() {
             self.parse_own_css();
diff --git a/components/script/dom/htmltextareaelement.rs b/components/script/dom/htmltextareaelement.rs
index 17e646d71ed..22e843fa08f 100644
--- a/components/script/dom/htmltextareaelement.rs
+++ b/components/script/dom/htmltextareaelement.rs
@@ -11,7 +11,7 @@ use dom::bindings::codegen::Bindings::HTMLTextAreaElementBinding::HTMLTextAreaEl
 use dom::bindings::codegen::Bindings::NodeBinding::NodeMethods;
 use dom::bindings::codegen::InheritTypes::{ElementCast, EventTargetCast, HTMLElementCast, NodeCast};
 use dom::bindings::codegen::InheritTypes::{HTMLTextAreaElementDerived, HTMLFieldSetElementDerived};
-use dom::bindings::codegen::InheritTypes::{KeyboardEventCast, TextDerived};
+use dom::bindings::codegen::InheritTypes::KeyboardEventCast;
 use dom::bindings::global::GlobalRef;
 use dom::bindings::js::{LayoutJS, Root};
 use dom::bindings::refcounted::Trusted;
@@ -23,8 +23,8 @@ use dom::element::ElementTypeId;
 use dom::htmlelement::{HTMLElement, HTMLElementTypeId};
 use dom::htmlformelement::FormControl;
 use dom::keyboardevent::KeyboardEvent;
-use dom::node::{DisabledStateHelpers, Node, NodeHelpers, NodeDamage, NodeTypeId};
-use dom::node::{document_from_node, window_from_node};
+use dom::node::{ChildrenMutation, DisabledStateHelpers, Node, NodeDamage};
+use dom::node::{NodeHelpers, NodeTypeId, document_from_node, window_from_node};
 use textinput::{TextInput, Lines, KeyReaction};
 use dom::virtualmethods::VirtualMethods;
 use dom::window::WindowHelpers;
@@ -330,12 +330,11 @@ impl<'a> VirtualMethods for &'a HTMLTextAreaElement {
         }
     }
 
-    fn child_inserted(&self, child: &Node) {
-        if let Some(s) = self.super_type() {
-            s.child_inserted(child);
+    fn children_changed(&self, mutation: &ChildrenMutation) {
+        if let Some(ref s) = self.super_type() {
+            s.children_changed(mutation);
         }
-
-        if child.is_text() && !self.value_changed.get() {
+        if !self.value_changed.get() {
             self.reset();
         }
     }
diff --git a/components/script/dom/htmltitleelement.rs b/components/script/dom/htmltitleelement.rs
index a6585bd17b4..e4f51b03629 100644
--- a/components/script/dom/htmltitleelement.rs
+++ b/components/script/dom/htmltitleelement.rs
@@ -13,7 +13,7 @@ use dom::document::{Document, DocumentHelpers};
 use dom::eventtarget::{EventTarget, EventTargetTypeId};
 use dom::element::ElementTypeId;
 use dom::htmlelement::{HTMLElement, HTMLElementTypeId};
-use dom::node::{Node, NodeHelpers, NodeTypeId};
+use dom::node::{ChildrenMutation, Node, NodeHelpers, NodeTypeId};
 use dom::text::Text;
 use dom::virtualmethods::VirtualMethods;
 use util::str::DOMString;
@@ -75,15 +75,13 @@ impl<'a> VirtualMethods for &'a HTMLTitleElement {
         Some(htmlelement as &VirtualMethods)
     }
 
-    fn child_inserted(&self, child: &Node) {
+    fn children_changed(&self, mutation: &ChildrenMutation) {
         if let Some(ref s) = self.super_type() {
-            s.child_inserted(child);
+            s.children_changed(mutation);
         }
-
         let node = NodeCast::from_ref(*self);
         if node.is_in_doc() {
-            let document = node.owner_doc();
-            document.r().title_changed();
+            node.owner_doc().title_changed();
         }
     }
 
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index 0a06a5253c5..4922bb53118 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -67,6 +67,7 @@ use std::cell::{Cell, RefCell, Ref, RefMut};
 use std::default::Default;
 use std::iter::{FilterMap, Peekable};
 use std::mem;
+use std::slice::ref_slice;
 use std::sync::Arc;
 use uuid;
 use string_cache::{Atom, Namespace, QualName};
@@ -282,42 +283,11 @@ pub enum NodeTypeId {
 }
 
 trait PrivateNodeHelpers {
-    fn node_inserted(self);
-    fn node_removed(self, parent_in_doc: bool);
     fn add_child(self, new_child: &Node, before: Option<&Node>);
     fn remove_child(self, child: &Node);
 }
 
 impl<'a> PrivateNodeHelpers for &'a Node {
-    // https://dom.spec.whatwg.org/#node-is-inserted
-    fn node_inserted(self) {
-        assert!(self.parent_node.get().is_some());
-        let document = document_from_node(self);
-        let is_in_doc = self.is_in_doc();
-
-        for node in self.traverse_preorder() {
-            vtable_for(&node.r()).bind_to_tree(is_in_doc);
-        }
-
-        let parent = self.parent_node.get().map(Root::from_rooted);
-        parent.r().map(|parent| vtable_for(&parent).child_inserted(self));
-        document.r().content_and_heritage_changed(self, NodeDamage::OtherNodeDamage);
-    }
-
-    // https://dom.spec.whatwg.org/#node-is-removed
-    fn node_removed(self, parent_in_doc: bool) {
-        assert!(self.parent_node.get().is_none());
-        for node in self.traverse_preorder() {
-            node.r().set_flag(IS_IN_DOC, false);
-            vtable_for(&node.r()).unbind_from_tree(parent_in_doc);
-        }
-        self.layout_data.dispose(self);
-    }
-
-    //
-    // Pointer stitching
-    //
-
     /// Adds a new child to the end of this node's list of children.
     ///
     /// Fails unless `new_child` is disconnected from the tree.
@@ -358,6 +328,14 @@ impl<'a> PrivateNodeHelpers for &'a Node {
         }
 
         new_child.parent_node.set(Some(JS::from_ref(self)));
+
+        let parent_in_doc = self.is_in_doc();
+        for node in new_child.traverse_preorder() {
+            node.set_flag(IS_IN_DOC, parent_in_doc);
+            vtable_for(&&*node).bind_to_tree(parent_in_doc);
+        }
+        let document = new_child.owner_doc();
+        document.content_and_heritage_changed(new_child, NodeDamage::OtherNodeDamage);
     }
 
     /// Removes the given child from this node's list of children.
@@ -387,6 +365,15 @@ impl<'a> PrivateNodeHelpers for &'a Node {
         child.prev_sibling.set(None);
         child.next_sibling.set(None);
         child.parent_node.set(None);
+
+        let parent_in_doc = self.is_in_doc();
+        for node in child.traverse_preorder() {
+            node.set_flag(IS_IN_DOC, false);
+            vtable_for(&&*node).unbind_from_tree(parent_in_doc);
+        }
+        child.layout_data.dispose(child);
+        let document = child.owner_doc();
+        document.content_and_heritage_changed(child, NodeDamage::OtherNodeDamage);
     }
 }
 
@@ -971,9 +958,8 @@ impl<'a> NodeHelpers for &'a Node {
     }
 
     fn remove_self(self) {
-        match self.parent_node.get() {
-            Some(parent) => parent.root().r().remove_child(self),
-            None => ()
+        if let Some(ref parent) = self.GetParentNode() {
+            Node::remove(self, parent.r(), SuppressObserver::Unsuppressed);
         }
     }
 
@@ -1638,110 +1624,79 @@ impl Node {
               parent: &Node,
               child: Option<&Node>,
               suppress_observers: SuppressObserver) {
-        fn do_insert(node: &Node, parent: &Node, child: Option<&Node>) {
-            parent.add_child(node, child);
-            let is_in_doc = parent.is_in_doc();
-            for kid in node.traverse_preorder() {
-                let mut flags = kid.r().flags.get();
-                if is_in_doc {
-                    flags.insert(IS_IN_DOC);
-                } else {
-                    flags.remove(IS_IN_DOC);
-                }
-                kid.r().flags.set(flags);
-            }
-        }
+        debug_assert!(&*node.owner_doc() == &*parent.owner_doc());
+        debug_assert!(child.map_or(true, |child| Some(parent) == child.GetParentNode().r()));
 
-        fn fire_observer_if_necessary(node: &Node, suppress_observers: SuppressObserver) {
-            match suppress_observers {
-                SuppressObserver::Unsuppressed => node.node_inserted(),
-                SuppressObserver::Suppressed => ()
+        // Steps 1-2: ranges.
+        let mut new_nodes = RootedVec::new();
+        let new_nodes = if let NodeTypeId::DocumentFragment = node.type_id() {
+            // Step 3.
+            new_nodes.extend(node.children().map(|kid| JS::from_rooted(&kid)));
+            // Step 4: mutation observers.
+            // Step 5.
+            for kid in new_nodes.r() {
+                Node::remove(*kid, node, SuppressObserver::Suppressed);
             }
-        }
-
-        // XXX assert owner_doc
-        // Step 1-3: ranges.
-
-        match node.type_id() {
-            NodeTypeId::DocumentFragment => {
-                // Step 4.
-                // Step 5: DocumentFragment, mutation records.
-                // Step 6: DocumentFragment.
-                let kids: Vec<Root<Node>> = node.children().collect();
-                for kid in &kids {
-                    Node::remove(kid.r(), node, SuppressObserver::Suppressed);
-                }
-
-                // Step 7: mutation records.
-                // Step 8.
-                for kid in &kids {
-                    do_insert(kid.r(), parent, child);
-                }
-
-                for kid in kids {
-                    fire_observer_if_necessary(kid.r(), suppress_observers);
+            vtable_for(&node).children_changed(&ChildrenMutation::replace_all(new_nodes.r(), &[]));
+            new_nodes.r()
+        } else {
+            // Step 3.
+            ref_slice(&node)
+        };
+        // Step 6: mutation observers.
+        let previous_sibling = match suppress_observers {
+            SuppressObserver::Unsuppressed => {
+                match child {
+                    Some(child) => child.GetPreviousSibling(),
+                    None => parent.GetLastChild(),
                 }
-            }
-            _ => {
-                // Step 4.
-                // Step 5: DocumentFragment, mutation records.
-                // Step 6: DocumentFragment.
-                // Step 7: mutation records.
-                // Step 8.
-                do_insert(node, parent, child);
-                // Step 9.
-                fire_observer_if_necessary(node, suppress_observers);
-            }
+            },
+            SuppressObserver::Suppressed => None,
+        };
+        // Step 7.
+        for kid in new_nodes {
+            // Step 7.1.
+            parent.add_child(*kid, child);
+            // Step 7.2: insertion steps.
+        }
+        if let SuppressObserver::Unsuppressed = suppress_observers {
+            vtable_for(&parent).children_changed(
+                &ChildrenMutation::insert(previous_sibling.r(), new_nodes, child));
         }
     }
 
     // https://dom.spec.whatwg.org/#concept-node-replace-all
     pub fn replace_all(node: Option<&Node>, parent: &Node) {
         // Step 1.
-        match node {
-            Some(node) => {
-                let document = document_from_node(parent);
-                Node::adopt(node, document.r());
-            }
-            None => (),
+        if let Some(node) = node {
+            Node::adopt(node, &*parent.owner_doc());
         }
-
         // Step 2.
-        let mut removed_nodes: RootedVec<JS<Node>> = RootedVec::new();
-        for child in parent.children() {
-            removed_nodes.push(JS::from_rooted(&child));
-        }
-
+        let mut removed_nodes = RootedVec::new();
+        removed_nodes.extend(parent.children().map(|child| JS::from_rooted(&child)));
         // Step 3.
-        let added_nodes = match node {
-            None => vec!(),
-            Some(node) => match node.type_id() {
-                NodeTypeId::DocumentFragment => node.children().collect(),
-                _ => vec!(Root::from_ref(node)),
-            },
+        let mut added_nodes = RootedVec::new();
+        let added_nodes = if let Some(node) = node.as_ref() {
+            if let NodeTypeId::DocumentFragment = node.type_id() {
+                added_nodes.extend(node.children().map(|child| JS::from_rooted(&child)));
+                added_nodes.r()
+            } else {
+                ref_slice(node)
+            }
+        } else {
+            &[] as &[&Node]
         };
-
         // Step 4.
-        for child in parent.children() {
-            Node::remove(child.r(), parent, SuppressObserver::Suppressed);
+        for child in removed_nodes.r() {
+            Node::remove(*child, parent, SuppressObserver::Suppressed);
         }
-
         // Step 5.
-        match node {
-            Some(node) => Node::insert(node, parent, None, SuppressObserver::Suppressed),
-            None => (),
-        }
-
-        // Step 6: mutation records.
-
-        // Step 7.
-        let parent_in_doc = parent.is_in_doc();
-        for removed_node in removed_nodes.iter() {
-            removed_node.root().r().node_removed(parent_in_doc);
-        }
-        for added_node in added_nodes {
-            added_node.r().node_inserted();
+        if let Some(node) = node {
+            Node::insert(node, parent, None, SuppressObserver::Suppressed);
         }
+        // Step 6: mutation observers.
+        vtable_for(&parent).children_changed(
+            &ChildrenMutation::replace_all(removed_nodes.r(), added_nodes));
     }
 
     // https://dom.spec.whatwg.org/#concept-node-pre-remove
@@ -1761,16 +1716,22 @@ impl Node {
     }
 
     // https://dom.spec.whatwg.org/#concept-node-remove
-    fn remove(node: &Node, parent: &Node, _suppress_observers: SuppressObserver) {
+    fn remove(node: &Node, parent: &Node, suppress_observers: SuppressObserver) {
         assert!(node.GetParentNode().map_or(false, |node_parent| node_parent.r() == parent));
 
         // Step 1-5: ranges.
-        // Step 6-7: mutation observers.
-        // Step 8.
-        parent.remove_child(node);
-
+        // Step 6.
+        let old_previous_sibling = node.GetPreviousSibling();
+        // Steps 7-8: mutation observers.
         // Step 9.
-        node.node_removed(parent.is_in_doc());
+        let old_next_sibling = node.GetNextSibling();
+        parent.remove_child(node);
+        if let SuppressObserver::Unsuppressed = suppress_observers {
+            vtable_for(&parent).children_changed(
+                &ChildrenMutation::replace(old_previous_sibling.r(),
+                                           &node, &[],
+                                           old_next_sibling.r()));
+        }
     }
 
     // https://dom.spec.whatwg.org/#concept-node-clone
@@ -2275,36 +2236,31 @@ impl<'a> NodeMethods for &'a Node {
         let document = document_from_node(self);
         Node::adopt(node, document.r());
 
-        // Step 12.
-        let mut nodes: RootedVec<JS<Node>> = RootedVec::new();
-        if node.type_id() == NodeTypeId::DocumentFragment {
-            // Collect fragment children before Step 11,
-            // because Node::insert removes a DocumentFragment's children,
-            // and we need them in Step 13.
-            // Issue filed against the spec:
-            // https://www.w3.org/Bugs/Public/show_bug.cgi?id=28330
-            for child_node in node.children() {
-                nodes.push(JS::from_rooted(&child_node));
-            }
-        } else {
-            nodes.push(JS::from_ref(node));
-        }
+        // Step 10.
+        let previous_sibling = child.GetPreviousSibling();
 
-        {
-            // Step 10.
-            Node::remove(child, self, SuppressObserver::Suppressed);
+        // Step 11.
+        Node::remove(child, self, SuppressObserver::Suppressed);
 
-            // Step 11.
-            Node::insert(node, self, reference_child, SuppressObserver::Suppressed);
-        }
+        // Step 12.
+        let mut nodes = RootedVec::new();
+        let nodes = if node.type_id() == NodeTypeId::DocumentFragment {
+            nodes.extend(node.children().map(|node| JS::from_rooted(&node)));
+            nodes.r()
+        } else {
+            ref_slice(&node)
+        };
 
-        // Step 13: mutation records.
-        child.node_removed(self.is_in_doc());
-        for child_node in &*nodes {
-            child_node.root().r().node_inserted();
-        }
+        // Step 13.
+        Node::insert(node, self, reference_child, SuppressObserver::Suppressed);
 
         // Step 14.
+        vtable_for(&self).children_changed(
+            &ChildrenMutation::replace(previous_sibling.r(),
+                                       &child, nodes,
+                                       reference_child));
+
+        // Step 15.
         Ok(Root::from_ref(child))
     }
 
@@ -2322,14 +2278,14 @@ impl<'a> NodeMethods for &'a Node {
                 Some(text) => {
                     let characterdata: &CharacterData = CharacterDataCast::from_ref(text);
                     if characterdata.Length() == 0 {
-                        self.remove_child(child.r());
+                        Node::remove(&*child, self, SuppressObserver::Unsuppressed);
                     } else {
                         match prev_text {
                             Some(ref text_node) => {
                                 let prev_characterdata =
                                     CharacterDataCast::from_ref(text_node.r());
                                 prev_characterdata.append_data(&**characterdata.data());
-                                self.remove_child(child.r());
+                                Node::remove(&*child, self, SuppressObserver::Unsuppressed);
                             },
                             None => prev_text = Some(Root::from_ref(text))
                         }
@@ -2635,3 +2591,61 @@ pub enum NodeDamage {
     /// Other parts of a node changed; attributes, text content, etc.
     OtherNodeDamage,
 }
+
+pub enum ChildrenMutation<'a> {
+    Append { prev: &'a Node, added: &'a [&'a Node] },
+    Insert { prev: &'a Node, added: &'a [&'a Node], next: &'a Node },
+    Prepend { added: &'a [&'a Node], next: &'a Node },
+    Replace {
+        prev: Option<&'a Node>,
+        removed: &'a Node,
+        added: &'a [&'a Node],
+        next: Option<&'a Node>,
+    },
+    ReplaceAll { removed: &'a [&'a Node], added: &'a [&'a Node] },
+}
+
+impl<'a> ChildrenMutation<'a> {
+    fn insert(prev: Option<&'a Node>, added: &'a [&'a Node], next: Option<&'a Node>)
+              -> ChildrenMutation<'a> {
+        match (prev, next) {
+            (None, None) => {
+                ChildrenMutation::ReplaceAll { removed: &[], added: added }
+            },
+            (Some(prev), None) => {
+                ChildrenMutation::Append { prev: prev, added: added }
+            },
+            (None, Some(next)) => {
+                ChildrenMutation::Prepend { added: added, next: next }
+            },
+            (Some(prev), Some(next)) => {
+                ChildrenMutation::Insert { prev: prev, added: added, next: next }
+            },
+        }
+    }
+
+    fn replace(prev: Option<&'a Node>,
+               removed: &'a &'a Node,
+               added: &'a [&'a Node],
+               next: Option<&'a Node>)
+               -> ChildrenMutation<'a> {
+        if let (None, None) = (prev, next) {
+            ChildrenMutation::ReplaceAll {
+                removed: ref_slice(removed),
+                added: added,
+            }
+        } else {
+            ChildrenMutation::Replace {
+                prev: prev,
+                removed: *removed,
+                added: added,
+                next: next,
+            }
+        }
+    }
+
+    fn replace_all(removed: &'a [&'a Node], added: &'a [&'a Node])
+                   -> ChildrenMutation<'a> {
+        ChildrenMutation::ReplaceAll { removed: removed, added: added }
+    }
+}
diff --git a/components/script/dom/virtualmethods.rs b/components/script/dom/virtualmethods.rs
index 8bb62637ac6..88cc024acd5 100644
--- a/components/script/dom/virtualmethods.rs
+++ b/components/script/dom/virtualmethods.rs
@@ -35,7 +35,8 @@ use dom::document::Document;
 use dom::element::ElementTypeId;
 use dom::event::Event;
 use dom::htmlelement::HTMLElementTypeId;
-use dom::node::{Node, NodeHelpers, NodeTypeId, CloneChildrenFlag};
+use dom::node::{ChildrenMutation, CloneChildrenFlag, Node, NodeHelpers};
+use dom::node::NodeTypeId;
 
 use util::str::DOMString;
 
@@ -97,10 +98,10 @@ pub trait VirtualMethods {
         }
     }
 
-    /// Called on the parent when a node is added to its child list.
-    fn child_inserted(&self, child: &Node) {
+    /// Called on the parent when its children are changed.
+    fn children_changed(&self, mutation: &ChildrenMutation) {
         if let Some(ref s) = self.super_type() {
-            s.child_inserted(child);
+            s.children_changed(mutation);
         }
     }
 
diff --git a/components/script/lib.rs b/components/script/lib.rs
index 16f73c85afd..e41a033dc66 100644
--- a/components/script/lib.rs
+++ b/components/script/lib.rs
@@ -19,6 +19,7 @@
 #![feature(nonzero)]
 #![feature(owned_ascii_ext)]
 #![feature(plugin)]
+#![feature(ref_slice)]
 #![feature(rc_unique)]
 #![feature(slice_chars)]
 #![feature(str_utf16)]