Match DOM4 spec with respect to DocumentFragment insertion
authoradamk@chromium.org <adamk@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 23 Mar 2012 22:51:25 +0000 (22:51 +0000)
committeradamk@chromium.org <adamk@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 23 Mar 2012 22:51:25 +0000 (22:51 +0000)
https://bugs.webkit.org/show_bug.cgi?id=82089

Reviewed by Ryosuke Niwa.

Source/WebCore:

DOM4 specifies the behavior of appendChild, insertBefore, and replaceChild
in terms of "mutation algorithms":

http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#mutation-algorithms

This change updates WebKit to match, in particular with regard to DocumentFragments.
Previously, ContainerNode would remove nodes one at a time, then add them to the new parent.
When combined with MutationObservers, this results in overly-verbose mutation records.
Now we create as few records as possible, matching the spec as well as Gecko's implementation
of MutationObservers.

Note that we still need to check validity each time through the loop,
since inserting a node may dispatch events. In a future change, I hope
to move these events so that they fire only after all nodes are inserted,
but that's too much to tackle all in one.

Tests: fast/mutation/document-fragment-insertion.html

* dom/ContainerNode.cpp:
(WebCore::collectChildrenAndRemoveFromOldParent): New helper method
combining collectTargetNodes() with the removal of the collected nodes from
their old parent, if any.
(WebCore::ContainerNode::insertBefore): Use new helper method instead
of removing nodes one at a time from the fragment.
(WebCore::ContainerNode::replaceChild): ditto. Also removed some redundant asserts
and moved the "do nothing" check out of the loop.
(WebCore::ContainerNode::appendChild): Use new helper method.

LayoutTests:

* fast/dom/Node/fragment-mutation-expected.txt:
* fast/dom/Node/fragment-mutation.html: Removed tests that no longer make sense
since the DocumentFragment has no children by the time DOMSubtreeModified is called.
* fast/mutation/document-fragment-insertion-expected.txt: Added.
* fast/mutation/document-fragment-insertion.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@111925 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/dom/Node/fragment-mutation-expected.txt
LayoutTests/fast/dom/Node/fragment-mutation.html
LayoutTests/fast/mutation/document-fragment-insertion-expected.txt [new file with mode: 0644]
LayoutTests/fast/mutation/document-fragment-insertion.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/dom/ContainerNode.cpp

index 18bdfe7412aeac4bb1a4732e0105c89a25f52a33..10246ea4ec3ce9c86ae59f59346591c87962d7b1 100644 (file)
@@ -1,3 +1,16 @@
+2012-03-23  Adam Klein  <adamk@chromium.org>
+
+        Match DOM4 spec with respect to DocumentFragment insertion
+        https://bugs.webkit.org/show_bug.cgi?id=82089
+
+        Reviewed by Ryosuke Niwa.
+
+        * fast/dom/Node/fragment-mutation-expected.txt:
+        * fast/dom/Node/fragment-mutation.html: Removed tests that no longer make sense
+        since the DocumentFragment has no children by the time DOMSubtreeModified is called.
+        * fast/mutation/document-fragment-insertion-expected.txt: Added.
+        * fast/mutation/document-fragment-insertion.html: Added.
+
 2012-03-23  Emil A Eklund  <eae@chromium.org>
 
         Unreviewed rebaseline of css3 filter test for chromium linux.
index 41e8fa4d3306f589d49e76a45e52d5cc7700fd2f..0f04e66a0e53e6f5b1901c5dcb176f67f2e4f868 100644 (file)
@@ -1,17 +1,13 @@
 This test creates a fragment containing three elements: "B", "U", and "P", attempts to appendChild this fragment and studies effects of mutation events on the fragment.
 
 Inserting an element in front of the next item in fragment should not affect the result: PASS
-Removing next item should not abort iteration: PASS
 Appending an element at the end of the fragment should not affect the result: PASS
 Continually re-appending removed element to the fragment should eventually throw NOT_FOUND_ERR: PASS
-Moving next item to become previous sibling of the re-parentee should not result in stack exhaustion: PASS
 
 This test creates a fragment containing three elements: "B", "U", and "P", attempts to insertBefore this fragment and studies effects of mutation events on the fragment.
 
 Inserting an element in front of the next item in fragment should not affect the result: PASS
-Removing next item should not abort iteration: PASS
 Appending an element at the end of the fragment should not affect the result: PASS
 Continually re-appending removed element to the fragment should eventually throw NOT_FOUND_ERR: PASS
-Moving next item to become previous sibling of the re-parentee should not result in stack exhaustion: PASS
 
 
index 037e17bf5002f84691f180760664fc41630bc3ae..f89506fdadfce2cdc45d3cf19ac9f6450c1cf0a4 100644 (file)
@@ -113,11 +113,6 @@ function runTest(methodName, method)
         frag.insertBefore(missing, frag.firstChild);
     }, expectNodes("BUP"));
 
-    testFragment(method, "Removing next item should not abort iteration", function(evt, frag)
-    {
-        frag.removeChild(frag.firstChild);
-    }, expectNodes("BUP"));
-
     var extra = document.body.appendChild(document.createElement("em"));
     testFragment(method, "Appending an element at the end of the fragment should not affect the result", function(evt, frag)
     {
@@ -128,11 +123,6 @@ function runTest(methodName, method)
     {
         stash.insertBefore(frag.lastChild, stash.firstChild);
     }, expectException(8), true);
-
-    testFragment(method, "Moving next item to become previous sibling of the re-parentee should not result in stack exhaustion", function(evt, frag, stash)
-    {
-        document.body.insertBefore(frag.firstChild, stash);
-    }, expectNodes("BUP"));
     printLog(methodName);
 }
 function runTests()
@@ -145,4 +135,4 @@ function runTests()
 </head>
 <body onload="runTests()">
 </body>
-</html>
\ No newline at end of file
+</html>
diff --git a/LayoutTests/fast/mutation/document-fragment-insertion-expected.txt b/LayoutTests/fast/mutation/document-fragment-insertion-expected.txt
new file mode 100644 (file)
index 0000000..f2f3ee3
--- /dev/null
@@ -0,0 +1,30 @@
+Inserting DocumentFragments should remove all children of the fragment before inserting the children.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+Testing appendChild
+PASS mutations.length is 2
+PASS mutations[0].addedNodes.length is 0
+PASS mutations[0].removedNodes.length is 2
+PASS mutations[1].addedNodes.length is 2
+PASS mutations[1].removedNodes.length is 0
+
+Testing insertBefore
+PASS mutations.length is 2
+PASS mutations[0].addedNodes.length is 0
+PASS mutations[0].removedNodes.length is 2
+PASS mutations[1].addedNodes.length is 2
+PASS mutations[1].removedNodes.length is 0
+
+Testing replaceChild
+PASS mutations.length is 2
+PASS mutations[0].addedNodes.length is 0
+PASS mutations[0].removedNodes.length is 2
+PASS mutations[1].addedNodes.length is 2
+PASS mutations[1].removedNodes.length is 1
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/mutation/document-fragment-insertion.html b/LayoutTests/fast/mutation/document-fragment-insertion.html
new file mode 100644 (file)
index 0000000..cac46cf
--- /dev/null
@@ -0,0 +1,77 @@
+<!DOCTYPE html>
+<script src="../js/resources/js-test-pre.js"></script>
+<script>
+description('Inserting DocumentFragments should remove all children of the fragment before inserting the children.');
+
+window.jsTestIsAsync = true;
+
+function createObservedFragment() {
+    var fragment = document.createDocumentFragment();
+    fragment.appendChild(document.createElement('b'));
+    fragment.appendChild(document.createElement('i'));
+    observer.observe(fragment, {childList: true});
+    return fragment;
+}
+
+function createObservedDiv() {
+    return div;
+}
+
+function callback(mutations) {
+    window.mutations = mutations;
+}
+var observer = new WebKitMutationObserver(callback);
+
+function testAppendChild() {
+    debug('Testing appendChild');
+    var div = document.createElement('div');
+    observer.observe(div, {childList: true});
+    div.appendChild(createObservedFragment());
+    setTimeout(function() {
+        shouldBe('mutations.length', '2');
+        shouldBe('mutations[0].addedNodes.length', '0');
+        shouldBe('mutations[0].removedNodes.length', '2');
+        shouldBe('mutations[1].addedNodes.length', '2');
+        shouldBe('mutations[1].removedNodes.length', '0');
+        debug('');
+        testInsertBefore();
+    }, 0);
+}
+
+function testInsertBefore() {
+    debug('Testing insertBefore');
+    var div = document.createElement('div');
+    div.appendChild(document.createElement('span'));
+    observer.observe(div, {childList: true});
+    div.insertBefore(createObservedFragment(), div.firstChild);
+    setTimeout(function() {
+        shouldBe('mutations.length', '2');
+        shouldBe('mutations[0].addedNodes.length', '0');
+        shouldBe('mutations[0].removedNodes.length', '2');
+        shouldBe('mutations[1].addedNodes.length', '2');
+        shouldBe('mutations[1].removedNodes.length', '0');
+        debug('');
+        testReplaceChild();
+    }, 0);
+}
+
+function testReplaceChild() {
+    debug('Testing replaceChild');
+    var div = document.createElement('div');
+    div.appendChild(document.createElement('span'));
+    observer.observe(div, {childList: true});
+    div.replaceChild(createObservedFragment(), div.firstChild);
+    setTimeout(function() {
+        shouldBe('mutations.length', '2');
+        shouldBe('mutations[0].addedNodes.length', '0');
+        shouldBe('mutations[0].removedNodes.length', '2');
+        shouldBe('mutations[1].addedNodes.length', '2');
+        shouldBe('mutations[1].removedNodes.length', '1');
+        debug('');
+        finishJSTest();
+    }, 0);
+}
+
+testAppendChild();
+</script>
+<script src="../js/resources/js-test-post.js"></script>
index abc61bffc6a505a7ec4f58b42b178a70adb9660d..53c6484c1b0e3dfb3315278a5f926ec825c46b0d 100644 (file)
@@ -1,3 +1,38 @@
+2012-03-23  Adam Klein  <adamk@chromium.org>
+
+        Match DOM4 spec with respect to DocumentFragment insertion
+        https://bugs.webkit.org/show_bug.cgi?id=82089
+
+        Reviewed by Ryosuke Niwa.
+
+        DOM4 specifies the behavior of appendChild, insertBefore, and replaceChild
+        in terms of "mutation algorithms":
+
+        http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#mutation-algorithms
+
+        This change updates WebKit to match, in particular with regard to DocumentFragments.
+        Previously, ContainerNode would remove nodes one at a time, then add them to the new parent.
+        When combined with MutationObservers, this results in overly-verbose mutation records.
+        Now we create as few records as possible, matching the spec as well as Gecko's implementation
+        of MutationObservers.
+
+        Note that we still need to check validity each time through the loop,
+        since inserting a node may dispatch events. In a future change, I hope
+        to move these events so that they fire only after all nodes are inserted,
+        but that's too much to tackle all in one.
+
+        Tests: fast/mutation/document-fragment-insertion.html
+
+        * dom/ContainerNode.cpp:
+        (WebCore::collectChildrenAndRemoveFromOldParent): New helper method
+        combining collectTargetNodes() with the removal of the collected nodes from
+        their old parent, if any.
+        (WebCore::ContainerNode::insertBefore): Use new helper method instead
+        of removing nodes one at a time from the fragment.
+        (WebCore::ContainerNode::replaceChild): ditto. Also removed some redundant asserts
+        and moved the "do nothing" check out of the loop.
+        (WebCore::ContainerNode::appendChild): Use new helper method.
+
 2012-03-23  Stephen White  <senorblanco@chromium.org>
 
         [skia] Switch to Skia's implementation of the feMorphology filter.
index d96d09810e3bbddd73951f5caa161c6a8365c178..9a437028a49e473d58c6299465015c0d91e1c93d 100644 (file)
@@ -69,6 +69,18 @@ static void collectTargetNodes(Node* node, NodeVector& nodes)
     getChildNodes(node, nodes);
 }
 
+static void collectChildrenAndRemoveFromOldParent(Node* node, NodeVector& nodes, ExceptionCode& ec)
+{
+    if (node->nodeType() != Node::DOCUMENT_FRAGMENT_NODE) {
+        nodes.append(node);
+        if (ContainerNode* oldParent = node->parentNode())
+            oldParent->removeChild(node, ec);
+        return;
+    }
+    getChildNodes(node, nodes);
+    toContainerNode(node)->removeChildren();
+}
+
 void ContainerNode::removeAllChildren()
 {
     removeAllChildrenInContainer<Node, ContainerNode>(this);
@@ -127,13 +139,14 @@ bool ContainerNode::insertBefore(PassRefPtr<Node> newChild, Node* refChild, Exce
         return false;
     }
 
-    NodeVector targets;
-    collectTargetNodes(newChild.get(), targets);
-    if (targets.isEmpty())
+    if (refChild->previousSibling() == newChild || refChild == newChild) // nothing to do
         return true;
 
-    // Now actually add the child(ren)
-    if (refChild->previousSibling() == newChild || refChild == newChild) // nothing to do
+    NodeVector targets;
+    collectChildrenAndRemoveFromOldParent(newChild.get(), targets, ec);
+    if (ec)
+        return false;
+    if (targets.isEmpty())
         return true;
 
 #if ENABLE(MUTATION_OBSERVERS)
@@ -145,12 +158,6 @@ bool ContainerNode::insertBefore(PassRefPtr<Node> newChild, Node* refChild, Exce
     for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
         Node* child = it->get();
 
-        // If child is already present in the tree, first remove it from the old location.
-        if (ContainerNode* oldParent = child->parentNode())
-            oldParent->removeChild(child, ec);
-        if (ec)
-            return false;
-
         // Due to arbitrary code running in response to a DOM mutation event it's
         // possible that "next" is no longer a child of "this".
         // It's also possible that "child" has been inserted elsewhere.
@@ -252,7 +259,7 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce
 
     if (oldChild == newChild) // nothing to do
         return true;
-    
+
     // Make sure replacing the old child with the new is ok
     checkReplaceChild(newChild.get(), oldChild, ec);
     if (ec)
@@ -277,23 +284,18 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce
     if (ec)
         return false;
 
+    if (next && (next->previousSibling() == newChild || next == newChild)) // nothing to do
+        return true;
+
     NodeVector targets;
-    collectTargetNodes(newChild.get(), targets);
+    collectChildrenAndRemoveFromOldParent(newChild.get(), targets, ec);
+    if (ec)
+        return false;
 
     // Add the new child(ren)
     for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
         Node* child = it->get();
 
-        // If the new child is already in the right place, we're done.
-        if (next && (next == child || next == child->previousSibling()))
-            break;
-
-        // Remove child from its old position.
-        if (ContainerNode* oldParent = child->parentNode())
-            oldParent->removeChild(child, ec);
-        if (ec)
-            return false;
-
         // Due to arbitrary code running in response to a DOM mutation event it's
         // possible that "next" is no longer a child of "this".
         // It's also possible that "child" has been inserted elsewhere.
@@ -303,9 +305,6 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce
         if (child->parentNode())
             break;
 
-        ASSERT(!child->nextSibling());
-        ASSERT(!child->previousSibling());
-
 #if ENABLE(INSPECTOR)
         InspectorInstrumentation::willInsertDOMNode(document(), child, this);
 #endif
@@ -580,7 +579,10 @@ bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, bo
         return newChild;
 
     NodeVector targets;
-    collectTargetNodes(newChild.get(), targets);
+    collectChildrenAndRemoveFromOldParent(newChild.get(), targets, ec);
+    if (ec)
+        return false;
+
     if (targets.isEmpty())
         return true;
 
@@ -592,18 +594,12 @@ bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, bo
     RefPtr<Node> prev = lastChild();
     for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
         Node* child = it->get();
-        // If child is already present in the tree, first remove it
-        if (ContainerNode* oldParent = child->parentNode()) {
-            oldParent->removeChild(child, ec);
-            if (ec)
-                return false;
-
-            // If the child has a parent again, just stop what we're doing, because
-            // that means someone is doing something with DOM mutation -- can't re-parent
-            // a child that already has a parent.
-            if (child->parentNode())
-                break;
-        }
+
+        // If the child has a parent again, just stop what we're doing, because
+        // that means someone is doing something with DOM mutation -- can't re-parent
+        // a child that already has a parent.
+        if (child->parentNode())
+            break;
 
 #if ENABLE(INSPECTOR)
         InspectorInstrumentation::willInsertDOMNode(document(), child, this);