Bug 17252 – Acid3 test removing Nodes during NodeIterator walk fails (affects Acid3 test 2)

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Eric Seidel (no email)]

Acid3 test removing Nodes during NodeIterator walk fails

Test 2: reached expectation 13 when expecting expectation 12

We'll need to reduce this further.

    function () {
      // test 2: Removing nodes during iteration
      var count = 0;
      var expect = function(n, node1, node2) {
        count += 1;
        assert(n == count, "reached expectation " + n + " when expecting expectation " + count);
        assertEquals(node1, node2, "expectation " + count + " failed");
      };
      var doc = getTestDocument();
      var t1 = doc.body.appendChild(doc.createElement('t1'));
      var t2 = doc.body.appendChild(doc.createElement('t2'));
      var t3 = doc.body.appendChild(doc.createElement('t3'));
      var t4 = doc.body.appendChild(doc.createElement('t4'));
      var callCount = 0;
      var filterFunctions = [
        function (node) { expect(1, node, doc.body); return true; }, // filter 0
        function (node) { expect(3, node, t1); return true; }, // filter 1
        function (node) { expect(5, node, t2); return true; }, // filter 2
        function (node) { expect(7, node, t3); doc.body.removeChild(t4); return true; }, // filter 3
        function (node) { expect(9, node, t4); return true; }, // filter 4
        function (node) { expect(11, node, t4); doc.body.removeChild(t4); return 2 /* REJECT */; }, // filter 5
        function (node) { expect(12, node, t3); return true; }, // filter 6
        function (node) { expect(14, node, t2); doc.body.removeChild(t2); return true; }, // filter 7
        function (node) { expect(16, node, t1); return true; }, // filter 8
      ];
      var i = doc.createNodeIterator(doc.documentElement.lastChild, 0xFFFFFFFF, function (node) { return filterFunctions[callCount++](node); }, true);
      // * B 1 2 3 4
      expect(2, i.nextNode(), doc.body); // filter 0
      // [B] * 1 2 3 4     
      expect(4, i.nextNode(), t1); // filter 1
      // B [1] * 2 3 4
      expect(6, i.nextNode(), t2); // filter 2
      // B 1 [2] * 3 4
      expect(8, i.nextNode(), t3); // filter 3
      // B 1 2 [3] *
      doc.body.appendChild(t4);
      // B 1 2 [3] * 4
      expect(10, i.nextNode(), t4); // filter 4
      // B 1 2 3 [4] *
      expect(13, i.previousNode(), t3); // filters 5, 6
        // B 1 2 3 * (4) // filter 5
        // B 1 2 [3] *   // between 5 and 6
        // B 1 2 * (3)   // filter 6
      // B 1 2 * [3]
      expect(15, i.previousNode(), t2); // filter 7
        // B 1 2 * (2) [3]
        // -- spec says "For instance, if a NodeFilter removes a node
        //    from a document, it can still accept the node, which
        //    means that the node may be returned by the NodeIterator
        //    or TreeWalker even though it is no longer in the subtree
        //    being traversed."
        // -- but it also says "If changes to the iterated list do not
        //    remove the reference node, they do not affect the state
        //    of the NodeIterator."
      // B 1 * [3]
      expect(17, i.previousNode(), t1); // filter 8
      // B [1] * 3
      return 1;
    },

[Darin Adler]

This could be a little challenging.

When I did my first NodeIterator/TreeWalker patch I attempted to fix this issue. However, it was quite tricky. The specification is unclear on what to do when nodes are removed inside the filter function.

- It specifies clearly what should happen to the current node when a node is removed.
- It specifies clearly what current node should be on return from NodeIterator functions.
- But it does not specify what the current node should be during execution of the NodeIterator functions.

In particular, if a function fails because it can't find, for example, a next sibling, currentNode is supposed to be left unchanged. This means that during the execution of the function we should not be changing currentNode from one candidate to another while calling the filter, because if the filter rejects all the nodes we'll have to change currentNode back to the original node.

All this led me to creation of a second "current node" that's just internal to NodeIterator. However, I was not able to get that model into working shape yet.

[Robert Xiao]

http://www.cafeconleche.org/books/xmljava/chapters/ch12.html says some vague stuff about "The iterator’s current position is always between two nodes (or before the first node or after the last node) but never on a node. Thus it is not invalidated by deleting the current node."

I am new to this, and I realize that this source isn't the spec. I wonder if an implementation like that can be realized?

Sorry if my query sounds dumb -- I'm just throwing out an idea, since it looks like this bug hasn't seen any activity for a while.

[Darin Adler]

Created attachment 20065 [details]
patch

[Anders Carlsson]

Comment on attachment 20065 [details]
patch


>Index: LayoutTests/traversal/resources/acid3-test-2.js
>===================================================================
>--- LayoutTests/traversal/resources/acid3-test-2.js	(revision 0)
>+++ LayoutTests/traversal/resources/acid3-test-2.js	(revision 0)
>@@ -0,0 +1,73 @@
>+description("Test of behavior NodeIterator when nodes are removed, from Acid3.");
>+
>+    var iframe = document.createElement("iframe");
>+    iframe.setAttribute("src", "about:blank");
>+    document.body.appendChild(iframe);
>+    var doc = iframe.contentDocument;
>+    for (var i = doc.documentElement.childNodes.length-1; i >= 0; i -= 1)
>+      doc.documentElement.removeChild(doc.documentElement.childNodes[i]);
>+    doc.documentElement.appendChild(doc.createElement('head'));
>+    doc.documentElement.firstChild.appendChild(doc.createElement('title'));
>+    doc.documentElement.appendChild(doc.createElement('body'));
>+

Indentation looks weird here.

r=me

[Darin Adler]

Committed revision 31303.

(Blog post coming shortly.)