# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1409828046 -7200
# Node ID 46cefd15ba3f7c3e98d9dea970c82b4966255969
# Parent  9fe9d32e00b5153a6a605ee69a61e3e6dd0a3838
NodeRefIterator advances lazily instead of eagerly, allowing the next element to be cached in the advance operation

diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NodeRefIteratorTest.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NodeRefIteratorTest.java	Thu Sep 04 12:54:06 2014 +0200
@@ -0,0 +1,219 @@
+/*
+ * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.test;
+
+import org.junit.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodeinfo.*;
+import com.oracle.graal.nodes.*;
+
+public class NodeRefIteratorTest extends GraalCompilerTest {
+
+    @NodeInfo
+    static class TestNode extends Node {
+        @Successor Node s1;
+        @Successor Node s2;
+        @Successor NodeSuccessorList<Node> stail;
+
+        @Input NodeInputList<ValueNode> itail;
+        @Input ValueNode i1;
+        @Input ValueNode i2;
+
+        public static TestNode create() {
+            return USE_GENERATED_NODES ? new NodeRefIteratorTest_TestNodeGen() : new TestNode();
+        }
+    }
+
+    @Test
+    public void testInputs() {
+        TestNode n = TestNode.create();
+
+        ConstantNode i1 = ConstantNode.forInt(1);
+        ConstantNode i2 = ConstantNode.forDouble(1.0d);
+        ConstantNode i3 = ConstantNode.forInt(4);
+        ConstantNode i4 = ConstantNode.forInt(14);
+        n.itail = new NodeInputList<>(n, new ValueNode[]{i3, i4});
+        n.i1 = i1;
+        n.i2 = i2;
+
+        NodeClassIterable inputs = n.inputs();
+
+        NodePosIterator iterator = inputs.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 0/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 1/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 2/0");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 2/1");
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        n.i1 = i4;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        n.i2 = i1;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        n.itail.initialize(1, i4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        n.i1 = null;
+        n.i2 = i2;
+        n.itail.initialize(0, null);
+        n.itail.initialize(1, i4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.withNullIterator();
+        n.i1 = null;
+        n.i2 = null;
+        n.itail.initialize(0, i3);
+        n.itail.initialize(1, null);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void testSuccessors() {
+        TestNode n = TestNode.create();
+        EndNode s1 = EndNode.create();
+        EndNode s2 = EndNode.create();
+        EndNode s3 = EndNode.create();
+        EndNode s4 = EndNode.create();
+        n.s1 = s1;
+        n.s2 = s2;
+        n.stail = new NodeSuccessorList<>(n, new Node[]{s3, s4});
+
+        NodeClassIterable successors = n.successors();
+        NodePosIterator iterator = successors.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 0/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 1/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 2/0");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 2/1");
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        n.s1 = s4;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        n.s2 = s1;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        n.stail.initialize(1, s4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        n.s1 = null;
+        n.s2 = s2;
+        n.stail.initialize(0, null);
+        n.stail.initialize(1, s4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.withNullIterator();
+        n.s1 = null;
+        n.s2 = null;
+        n.stail.initialize(0, s3);
+        n.stail.initialize(1, null);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+    }
+}
diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -33,14 +33,16 @@
 
     public NodeAllRefsIterator(Node node, int nodeFields, int nodeListFields, boolean isInputs) {
         super(node, nodeFields, nodeListFields, isInputs);
-        forward();
     }
 
     @Override
     protected void forward() {
+        assert needsForward;
+        needsForward = false;
         if (index < nodeFields) {
             index++;
             if (index < nodeFields) {
+                nextElement = getNode(index);
                 return;
             }
         } else {
@@ -52,6 +54,7 @@
                 list = getNodeList(index - nodeFields);
             }
             if (subIndex < list.size()) {
+                nextElement = list.get(subIndex);
                 return;
             }
             subIndex = 0;
diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java	Thu Sep 04 12:54:06 2014 +0200
@@ -56,9 +56,7 @@
         if (MODIFICATION_COUNTS_ENABLED) {
             return new NodeRefWithModCountIterator(node, nodeFields, nodeListFields, isInputs);
         } else {
-            NodeRefIterator iter = new NodeRefIterator(node, nodeFields, nodeListFields, isInputs);
-            iter.forward();
-            return iter;
+            return new NodeRefIterator(node, nodeFields, nodeListFields, isInputs);
         }
     }
 
diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -67,6 +67,8 @@
      */
     protected int subIndex;
 
+    protected Node nextElement;
+    protected boolean needsForward;
     protected NodeList<? extends Node> list;
 
     /**
@@ -85,7 +87,8 @@
         this.allNodeRefFields = nodeListFields + nodeFields;
         this.nodeFields = nodeFields;
         this.isInputs = isInputs;
-        index = Node.NOT_ITERABLE;
+        this.needsForward = true;
+        index = -1;
         subIndex = 0;
     }
 
@@ -111,10 +114,12 @@
     }
 
     protected void forward() {
+        needsForward = false;
         if (index < nodeFields) {
             index++;
             while (index < nodeFields) {
-                if (getNode(index) != null) {
+                nextElement = getNode(index);
+                if (nextElement != null) {
                     return;
                 }
                 index++;
@@ -128,7 +133,8 @@
             }
             assert list == getNodeList(index - nodeFields);
             while (subIndex < list.size()) {
-                if (list.get(subIndex) != null) {
+                nextElement = list.get(subIndex);
+                if (nextElement != null) {
                     return;
                 }
                 subIndex++;
@@ -140,39 +146,39 @@
     }
 
     private Node nextElement() {
-        if (index < nodeFields) {
-            return getNode(index);
-        } else if (index < allNodeRefFields) {
-            assert getNodeList(index - nodeFields) == list;
-            return list.get(subIndex);
+        if (needsForward) {
+            forward();
+        }
+        needsForward = true;
+        if (index < allNodeRefFields) {
+            return nextElement;
         }
         throw new NoSuchElementException();
     }
 
     @Override
     public boolean hasNext() {
-        return index >= 0 && index < allNodeRefFields;
+        if (needsForward) {
+            forward();
+        }
+        return index < allNodeRefFields;
     }
 
     @Override
     public Node next() {
-        try {
-            return nextElement();
-        } finally {
-            forward();
-        }
+        return nextElement();
     }
 
     public Position nextPosition() {
-        try {
-            if (index < nodeFields) {
-                return new Position(isInputs, index, Node.NOT_ITERABLE);
-            } else {
-                return new Position(isInputs, index, subIndex);
-            }
-        } finally {
+        if (needsForward) {
             forward();
         }
+        needsForward = true;
+        if (index < nodeFields) {
+            return new Position(isInputs, index, Node.NOT_ITERABLE);
+        } else {
+            return new Position(isInputs, index, subIndex);
+        }
     }
 
     @Override
diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -40,7 +40,6 @@
         super(node, nodeFields, nodeListFields, isInputs);
         assert MODIFICATION_COUNTS_ENABLED;
         this.modCount = node.modCount();
-        forward();
     }
 
     @Override
diff -r 9fe9d32e00b5 -r 46cefd15ba3f graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java
--- a/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -524,7 +524,6 @@
 
         // Constructor
         CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
-        addParameter(ctor, getType(boolean.class), "callForward");
         CodeTreeBuilder b = ctor.createBuilder();
         b.startStatement().startSuperCall();
         b.string(genClassName, ".this");
@@ -532,9 +531,6 @@
         b.string(String.valueOf(nodeListFields.size()));
         b.string(String.valueOf(nodeRefsType == NodeRefsType.Inputs));
         b.end().end();
-        b.startIf().string("callForward").end().startBlock();
-        b.startStatement().string("forward()").end();
-        b.end();
         cls.add(ctor);
 
         // Methods overriding those in NodeRefIterator
@@ -681,23 +677,20 @@
         CodeTypeElement cls = new CodeTypeElement(modifiers(PRIVATE, FINAL), ElementKind.CLASS, packageElement, name);
         cls.setSuperClass(inputsIteratorType);
 
-        // Constructor
-        CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
-        CodeTreeBuilder b = ctor.createBuilder();
-        b.startStatement().startSuperCall();
-        b.string("true");
-        b.end().end();
-        cls.add(ctor);
-
         // forward() method
         CodeExecutableElement method = new CodeExecutableElement(modifiers(PROTECTED), getType(void.class), "forward");
-        b = method.createBuilder();
+        CodeTreeBuilder b = method.createBuilder();
         int nodeFieldsSize = nodeFields.size();
         int nodeListFieldsSize = nodeListFields.size();
         String cond = "index < " + nodeFieldsSize;
+        if (GENERATE_ASSERTIONS) {
+            b.startAssert().string("needsForward").end();
+        }
+        b.startStatement().string("needsForward = false").end();
         b.startIf().string(cond).end().startBlock();
         b.startStatement().string("index++").end();
         b.startIf().string(cond).end().startBlock();
+        b.startStatement().string("nextElement = getNode(index)").end();
         b.startStatement().string("return").end();
         b.end();
         b.end();
@@ -710,6 +703,7 @@
         b.startStatement().string("list = getNodeList(index - " + nodeFieldsSize + ")").end();
         b.end();
         b.startIf().string("subIndex < list.size()").end().startBlock();
+        b.startStatement().string("nextElement = list.get(subIndex)").end();
         b.startStatement().string("return").end();
         b.end();
         b.startStatement().string("subIndex = 0").end();
@@ -733,12 +727,8 @@
         // Constructor
         CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
         CodeTreeBuilder b = ctor.createBuilder();
-        b.startStatement().startSuperCall();
-        b.string("false");
-        b.end().end();
         b.startAssert().staticReference(getType("com.oracle.graal.graph.Graph"), "MODIFICATION_COUNTS_ENABLED").end();
         b.startStatement().string("this.modCount = modCount()").end();
-        b.startStatement().string("forward()").end();
         cls.add(ctor);
 
         // hasNext, next and nextPosition methods
@@ -773,7 +763,7 @@
         b.startStatement().string("return new " + nodeRefsType + "WithModCountIterator()").end();
         b.end();
         b.startElseBlock();
-        b.startStatement().string("return new " + nodeRefsType + "Iterator(true)").end();
+        b.startStatement().string("return new " + nodeRefsType + "Iterator()").end();
         b.end();
         cls.add(method);