auto merge of #1136 : Ms2ger/servo/insertBefore, r=jdm

5 files changed, 242 insertions, 102 deletions

diff --git a/src/components/script/dom/bindings/codegen/Node.webidl b/src/components/script/dom/bindings/codegen/Node.webidl
index 5e099c217a4..5f32ff93f67 100644
--- a/src/components/script/dom/bindings/codegen/Node.webidl
+++ b/src/components/script/dom/bindings/codegen/Node.webidl
@@ -57,8 +57,8 @@ interface Node /*: EventTarget*/ {
            attribute DOMString? nodeValue;
   [SetterThrows, Pure]
            attribute DOMString? textContent;
-  /*[Throws]
-    Node insertBefore(Node node, Node? child);*/ //XXXjdm we don't deal well with Node? parameters
+  [Throws]
+  Node insertBefore(Node node, Node? child);
   [Throws]
   Node appendChild(Node node);
   [Throws]
diff --git a/src/components/script/dom/document.rs b/src/components/script/dom/document.rs
index d0a40235878..d2bee663740 100644
--- a/src/components/script/dom/document.rs
+++ b/src/components/script/dom/document.rs
@@ -315,7 +315,7 @@ impl Document {
                                 for title_child in child.children() {
                                     child.remove_child(title_child);
                                 }
-                                child.add_child(self.CreateTextNode(abstract_self, title));
+                                child.AppendChild(self.CreateTextNode(abstract_self, title));
                                 break;
                             }
                             if !has_title {
@@ -325,8 +325,8 @@ impl Document {
                                 let new_title = unsafe { 
                                     Node::as_abstract_node(self.get_cx(), new_title)
                                 };
-                                new_title.add_child(self.CreateTextNode(abstract_self, title));
-                                node.add_child(new_title);
+                                new_title.AppendChild(self.CreateTextNode(abstract_self, title));
+                                node.AppendChild(new_title);
                             }
                             break;
                         }
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index 680f6fbab19..aecb59dc25b 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -455,6 +455,34 @@ impl<'self, View> AbstractNode<View> {
     }
 }
 
+impl AbstractNode<ScriptView> {
+    pub fn AppendChild(self, node: AbstractNode<ScriptView>) -> Fallible<AbstractNode<ScriptView>> {
+        self.node().AppendChild(self, node)
+    }
+
+    // http://dom.spec.whatwg.org/#node-is-inserted
+    fn node_inserted(self) {
+        assert!(self.parent_node().is_some());
+        let document = self.node().owner_doc();
+
+        // Register elements having "id" attribute to the owner doc.
+        document.mut_document().register_nodes_with_id(&self);
+
+        document.document().content_changed();
+    }
+
+    // http://dom.spec.whatwg.org/#node-is-removed
+    fn node_removed(self) {
+        assert!(self.parent_node().is_none());
+        let document = self.node().owner_doc();
+
+        // Unregister elements having "id".
+        document.mut_document().unregister_nodes_with_id(&self);
+
+        document.document().content_changed();
+    }
+}
+
 impl<View> Iterator<AbstractNode<View>> for AbstractNodeChildrenIterator<View> {
     fn next(&mut self) -> Option<AbstractNode<View>> {
         let node = self.current_node;
@@ -499,32 +527,6 @@ impl Node<ScriptView> {
         }
     }
 
-    pub fn add_to_doc(&mut self, abstract_self: AbstractNode<ScriptView>, doc: AbstractDocument) {
-        let old_doc = self.owner_doc();
-        self.set_owner_doc(doc);
-        let mut cur_node = self.first_child;
-        while cur_node.is_some() {
-            for node in cur_node.unwrap().traverse_preorder() {
-                node.mut_node().set_owner_doc(doc);
-            };
-            cur_node = cur_node.unwrap().next_sibling();
-        }
-
-        // Unregister elements having "id' from the old doc.
-        old_doc.mut_document().unregister_nodes_with_id(&abstract_self);
-
-        // Register elements having "id" attribute to the owner doc.
-        doc.mut_document().register_nodes_with_id(&abstract_self);
-
-        // Signal the old document that it needs to update its display
-        if old_doc != doc {
-            old_doc.document().content_changed();
-        }
-
-        // Signal the new document that it needs to update its display
-        doc.document().content_changed();
-    }
-
     pub fn new(type_id: NodeTypeId, doc: AbstractDocument) -> Node<ScriptView> {
         Node {
             reflector_: Reflector::new(),
@@ -691,6 +693,136 @@ impl Node<ScriptView> {
         }
     }
 
+    // http://dom.spec.whatwg.org/#concept-node-adopt
+    fn adopt(node: AbstractNode<ScriptView>, document: AbstractDocument) {
+        // Step 1.
+        match node.parent_node() {
+            Some(parent) => Node::remove(node, parent, false),
+            None => (),
+        }
+
+        // Step 2.
+        if node.node().owner_doc() != document {
+            for descendant in node.traverse_preorder() {
+                descendant.mut_node().set_owner_doc(document);
+            }
+        }
+
+        // Step 3.
+        // If node is an element, it is _affected by a base URL change_.
+    }
+
+    // http://dom.spec.whatwg.org/#concept-node-pre-insert
+    fn pre_insert(node: AbstractNode<ScriptView>,
+                  parent: AbstractNode<ScriptView>,
+                  child: Option<AbstractNode<ScriptView>>) -> Fallible<AbstractNode<ScriptView>> {
+        fn is_inclusive_ancestor_of(node: AbstractNode<ScriptView>,
+                                    parent: AbstractNode<ScriptView>) -> bool {
+            node == parent || parent.ancestors().any(|ancestor| ancestor == node)
+        }
+
+        // Step 1.
+        match parent.type_id() {
+            // DocumentNodeTypeId |
+            DocumentFragmentNodeTypeId |
+            ElementNodeTypeId(*) => (),
+            _ => {
+                return Err(HierarchyRequest);
+            },
+        }
+
+        // Step 2.
+        if is_inclusive_ancestor_of(node, parent) {
+            return Err(HierarchyRequest);
+        }
+
+        // Step 3.
+        match child {
+            Some(child) => {
+                if child.parent_node() != Some(parent) {
+                    return Err(NotFound);
+                }
+            },
+            None => (),
+        }
+
+        // Step 4.
+        match node.type_id() {
+            DocumentFragmentNodeTypeId |
+            DoctypeNodeTypeId |
+            ElementNodeTypeId(_) |
+            TextNodeTypeId |
+            // ProcessingInstructionNodeTypeId |
+            CommentNodeTypeId => (),
+            /*_ => { XXX #838
+                return Err(HierarchyRequest);
+            },*/
+        }
+        
+        // Step 5.
+        match node.type_id() {
+            TextNodeTypeId => {
+                if false { // XXX #838
+                    return Err(HierarchyRequest);
+                }
+            },
+            DoctypeNodeTypeId => {
+                if true { // XXX #838
+                    return Err(HierarchyRequest);
+                }
+            },
+            _ => (),
+        }
+
+        // Step 6.
+        // XXX #838
+
+        // Step 7-8.
+        let referenceChild = if child != Some(node) {
+            child
+        } else {
+            node.next_sibling()
+        };
+
+        // Step 9.
+        Node::adopt(node, parent.node().owner_doc());
+
+        // Step 10.
+        Node::insert(node, parent, referenceChild, false);
+
+        // Step 11.
+        return Ok(node)
+    }
+
+    // http://dom.spec.whatwg.org/#concept-node-insert
+    fn insert(node: AbstractNode<ScriptView>,
+              parent: AbstractNode<ScriptView>,
+              child: Option<AbstractNode<ScriptView>>,
+              suppress_observers: bool) {
+        // XXX assert owner_doc
+        // Step 1-3: ranges.
+        // Step 4.
+        let nodes = match node.type_id() {
+            DocumentFragmentNodeTypeId => node.children().collect(),
+            _ => ~[node],
+        };
+
+        // Step 5: DocumentFragment, mutation records.
+        // Step 6: DocumentFragment.
+        // Step 7: mutation records.
+        // Step 8.
+        for node in nodes.iter() {
+            parent.add_child(*node, child);
+        }
+
+        // Step 9.
+        if !suppress_observers {
+            for node in nodes.iter() {
+                node.node_inserted();
+            }
+        }
+    }
+
     // http://dom.spec.whatwg.org/#concept-node-replace-all
     pub fn replace_all(&mut self,
                        abstract_self: AbstractNode<ScriptView>,
@@ -707,6 +839,38 @@ impl Node<ScriptView> {
         }
     }
 
+    // http://dom.spec.whatwg.org/#concept-node-pre-remove
+    fn pre_remove(child: AbstractNode<ScriptView>,
+                  parent: AbstractNode<ScriptView>) -> Fallible<AbstractNode<ScriptView>> {
+        // Step 1.
+        if child.parent_node() != Some(parent) {
+            return Err(NotFound);
+        }
+
+        // Step 2.
+        Node::remove(child, parent, false);
+
+        // Step 3.
+        Ok(child)
+    }
+
+    // http://dom.spec.whatwg.org/#concept-node-remove
+    fn remove(node: AbstractNode<ScriptView>,
+              parent: AbstractNode<ScriptView>,
+              suppress_observers: bool) {
+        assert!(node.parent_node() == Some(parent));
+
+        // Step 1-5: ranges.
+        // Step 6-7: mutation observers.
+        // Step 8.
+        parent.remove_child(node);
+
+        // Step 9.
+        if !suppress_observers {
+            node.node_removed();
+        }
+    }
+
     pub fn SetTextContent(&mut self,
                           abstract_self: AbstractNode<ScriptView>,
                           value: &DOMString) -> ErrorResult {
@@ -740,8 +904,11 @@ impl Node<ScriptView> {
         Ok(())
     }
 
-    pub fn InsertBefore(&mut self, _node: AbstractNode<ScriptView>, _child: Option<AbstractNode<ScriptView>>) -> Fallible<AbstractNode<ScriptView>> {
-        fail!("stub")
+    pub fn InsertBefore(&self,
+                        node: AbstractNode<ScriptView>,
+                        child: Option<AbstractNode<ScriptView>>) -> Fallible<AbstractNode<ScriptView>> {
+        self.wait_until_safe_to_modify_dom();
+        Node::pre_insert(node, node, child)
     }
 
     fn wait_until_safe_to_modify_dom(&self) {
@@ -749,75 +916,22 @@ impl Node<ScriptView> {
         document.document().wait_until_safe_to_modify_dom();
     }
 
-    pub fn AppendChild(&mut self,
+    pub fn AppendChild(&self,
                        abstract_self: AbstractNode<ScriptView>,
                        node: AbstractNode<ScriptView>) -> Fallible<AbstractNode<ScriptView>> {
-        fn is_hierarchy_request_err(this_node: AbstractNode<ScriptView>,
-                                   new_child: AbstractNode<ScriptView>) -> bool {
-            if new_child.is_doctype() {
-                return true;
-            }
-            if !this_node.is_element() {
-                // FIXME: This should also work for Document and DocumentFragments when they inherit from node.
-                // per jgraham
-                return true;
-            }
-            if this_node == new_child {
-                return true;
-            }
-            for ancestor in this_node.ancestors() {
-                if ancestor == new_child {
-                    return true;
-                }
-            }
-            false
-        }
-
-        if is_hierarchy_request_err(abstract_self, node) {
-            return Err(HierarchyRequest);
-        }
-
-        // TODO: Should we handle WRONG_DOCUMENT_ERR here?
-
         self.wait_until_safe_to_modify_dom();
-
-        // If the node already exists it is removed from current parent node.
-        node.parent_node().map(|parent| parent.remove_child(node));
-        abstract_self.add_child(node);
-        node.mut_node().add_to_doc(node, self.owner_doc());
-        Ok(node)
+        Node::pre_insert(node, abstract_self, None)
     }
 
     pub fn ReplaceChild(&mut self, _node: AbstractNode<ScriptView>, _child: AbstractNode<ScriptView>) -> Fallible<AbstractNode<ScriptView>> {
         fail!("stub")
     }
 
-    pub fn RemoveChild(&mut self,
+    pub fn RemoveChild(&self,
                        abstract_self: AbstractNode<ScriptView>,
                        node: AbstractNode<ScriptView>) -> Fallible<AbstractNode<ScriptView>> {
-        fn is_not_found_err(this_node: AbstractNode<ScriptView>,
-                            old_child: AbstractNode<ScriptView>) -> bool {
-            match old_child.parent_node() {
-                Some(parent) if parent == this_node => false,
-                _ => true
-            }
-        }
-
-        if is_not_found_err(abstract_self, node) {
-            return Err(NotFound);
-        }
-
         self.wait_until_safe_to_modify_dom();
-
-        // Unregister elements having "id' from the owner doc.
-        // This need be called before target nodes are removed from tree.
-        self.owner_doc.mut_document().unregister_nodes_with_id(&abstract_self);
-
-        abstract_self.remove_child(node);
-        // Signal the document that it needs to update its display.
-        let document = self.owner_doc();
-        document.document().content_changed();
-        Ok(node)
+        Node::pre_remove(node, abstract_self)
     }
 
     pub fn Normalize(&mut self) {
diff --git a/src/components/script/html/hubbub_html_parser.rs b/src/components/script/html/hubbub_html_parser.rs
index cbcab035578..4ed1981b8ed 100644
--- a/src/components/script/html/hubbub_html_parser.rs
+++ b/src/components/script/html/hubbub_html_parser.rs
@@ -477,7 +477,10 @@ pub fn parse_html(cx: *JSContext,
                 debug!("append child %x %x", cast::transmute(parent), cast::transmute(child));
                 let parent: AbstractNode<ScriptView> = NodeWrapping::from_hubbub_node(parent);
                 let child: AbstractNode<ScriptView> = NodeWrapping::from_hubbub_node(child);
-                parent.add_child(child);
+                // FIXME this needs to be AppendChild.
+                //       Probably blocked on #838, so that we can remove the
+                //       double root element.
+                parent.add_child(child, None);
             }
             child
         },
diff --git a/src/components/util/tree.rs b/src/components/util/tree.rs
index 4c6cfaa4962..f2a80342655 100644
--- a/src/components/util/tree.rs
+++ b/src/components/util/tree.rs
@@ -145,24 +145,47 @@ pub trait TreeNodeRef<Node>: Clone {
     /// Adds a new child to the end of this node's list of children.
     ///
     /// Fails unless `new_child` is disconnected from the tree.
-    fn add_child(&self, new_child: Self) {
+    fn add_child(&self, new_child: Self, before: Option<Self>) {
         let this_node = self.mut_node();
         let new_child_node = new_child.mut_node();
         assert!((get!(new_child_node, parent_node)).is_none());
         assert!((get!(new_child_node, prev_sibling)).is_none());
         assert!((get!(new_child_node, next_sibling)).is_none());
-
-        match get!(this_node, last_child) {
-            None => set!(this_node, set_first_child, Some(new_child.clone())),
-            Some(last_child) => {
-                let last_child_node = last_child.mut_node();
-                assert!((get!(last_child_node, next_sibling)).is_none());
-                set!(last_child_node, set_next_sibling, Some(new_child.clone()));
-                set!(new_child_node, set_prev_sibling, Some(last_child.clone()));
-            }
+        match before {
+            Some(before) => {
+                let before_node = before.mut_node();
+                // XXX Should assert that parent is self.
+                assert!((get!(before_node, parent_node)).is_some());
+                set!(before_node, set_prev_sibling, Some(new_child.clone()));
+                set!(new_child_node, set_next_sibling, Some(before.clone()));
+                match get!(before_node, prev_sibling) {
+                    None => {
+                        // XXX Should assert that before is the first child of
+                        //     self.
+                        set!(this_node, set_first_child, Some(new_child.clone()));
+                    },
+                    Some(prev_sibling) => {
+                        let prev_sibling_node = prev_sibling.mut_node();
+                        set!(prev_sibling_node, set_next_sibling, Some(new_child.clone()));
+                        set!(new_child_node, set_prev_sibling, Some(prev_sibling.clone()));
+                    },
+                }
+            },
+            None => {
+                match get!(this_node, last_child) {
+                    None => set!(this_node, set_first_child, Some(new_child.clone())),
+                    Some(last_child) => {
+                        let last_child_node = last_child.mut_node();
+                        assert!((get!(last_child_node, next_sibling)).is_none());
+                        set!(last_child_node, set_next_sibling, Some(new_child.clone()));
+                        set!(new_child_node, set_prev_sibling, Some(last_child.clone()));
+                    }
+                }
+
+                set!(this_node, set_last_child, Some(new_child.clone()));
+            },
         }
 
-        set!(this_node, set_last_child, Some(new_child.clone()));
         set!(new_child_node, set_parent_node, Some((*self).clone()));
     }