# HG changeset patch # User Gilles Duboscq # Date 1357833931 -3600 # Node ID c5a9bcd9493dc58917897f89427da49d8999e474 # Parent 6939a5af19d50f4a35a1a2a984cfd1bf0460d730 Support sub-types for typed node iterators Add tests diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNode.java --- a/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNode.java Thu Jan 10 12:03:14 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,37 +0,0 @@ -/* - * Copyright (c) 2011, 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.graph; - - -public class TestNode extends Node implements Node.IterableNodeType { - private String name; - - public TestNode(String name) { - this.name = name; - } - - - public String getName() { - return name; - } -} diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNodeInterface.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNodeInterface.java Thu Jan 10 17:05:31 2013 +0100 @@ -0,0 +1,28 @@ +/* + * Copyright (c) 2011, 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.graph; + + +public interface TestNodeInterface { + String getName(); +} diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest.java --- a/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest.java Thu Jan 10 12:03:14 2013 +0100 +++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest.java Thu Jan 10 17:05:31 2013 +0100 @@ -31,6 +31,16 @@ public class TypedNodeIteratorTest { + private static class TestNode extends Node implements Node.IterableNodeType, TestNodeInterface { + private final String name; + public TestNode(String name) { + this.name = name; + } + public String getName() { + return name; + } + } + @Test public void singleNodeTest() { Graph graph = new Graph(); @@ -144,9 +154,9 @@ assertEquals(3, z); } - private static String toString(Iterable nodes) { + public static String toString(Iterable nodes) { StringBuilder sb = new StringBuilder(); - for (TestNode tn : nodes) { + for (TestNodeInterface tn : nodes) { sb.append(tn.getName()); } return sb.toString(); diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest2.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest2.java Thu Jan 10 17:05:31 2013 +0100 @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2013, 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.graph; + +import static org.junit.Assert.*; + +import org.junit.*; + + +public class TypedNodeIteratorTest2 { + + private static class NodeA extends Node implements TestNodeInterface { + private final String name; + public NodeA(String name) { + this.name = name; + } + public String getName() { + return name; + } + } + + private static class NodeB extends NodeA implements Node.IterableNodeType { + public NodeB(String name) { + super(name); + } + } + + private static class NodeC extends NodeB { + public NodeC(String name) { + super(name); + } + } + + private static class NodeD extends NodeC { + public NodeD(String name) { + super(name); + } + } + + @Test + public void simpleSubclassTest() { + Graph graph = new Graph(); + graph.add(new NodeB("b")); + graph.add(new NodeD("d")); + + Assert.assertEquals("bd", TypedNodeIteratorTest.toString(graph.getNodes(NodeB.class))); + Assert.assertEquals("d", TypedNodeIteratorTest.toString(graph.getNodes(NodeD.class))); + } + + @Test + public void addingNodeDuringIterationTest() { + Graph graph = new Graph(); + graph.add(new NodeB("b1")); + NodeD d1 = graph.add(new NodeD("d1")); + StringBuilder sb = new StringBuilder(); + for (NodeB tn : graph.getNodes(NodeB.class)) { + if (tn == d1) { + graph.add(new NodeB("b2")); + } + sb.append(tn.getName()); + } + assertEquals("b1d1b2", sb.toString()); + for (NodeB tn : graph.getNodes(NodeB.class)) { + if (tn == d1) { + graph.add(new NodeB("b3")); + } + assertNotNull(tn); + } + assertEquals(4, graph.getNodes(NodeB.class).count()); + assertEquals(1, graph.getNodes(NodeD.class).count()); + } + +} diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Jan 10 12:03:14 2013 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Jan 10 17:05:31 2013 +0100 @@ -310,51 +310,99 @@ }; } - private static class TypedNodeIterator implements Iterator { - private Node current; - private final Node start; + private static class PlaceHolderNode extends Node {} + private static final PlaceHolderNode PLACE_HOLDER = new PlaceHolderNode(); + + private class TypedNodeIterator implements Iterator { + private final int[] ids; + private final Node[] current; + + private int currentIdIndex; + private boolean needsForward; + + public TypedNodeIterator(NodeClass clazz) { + ids = clazz.iterableIds(); + currentIdIndex = 0; + current = new Node[ids.length]; + Arrays.fill(current, PLACE_HOLDER); + needsForward = true; + } + + private Node findNext() { + if (needsForward) { + forward(); + } else { + Node c = current(); + Node afterDeleted = skipDeleted(c); + if (afterDeleted == null) { + needsForward = true; + } else if (c != afterDeleted) { + setCurrent(afterDeleted); + } + } + if (needsForward) { + return null; + } + return current(); + } - public TypedNodeIterator(Node start) { - if (start != null && start.isDeleted()) { - this.current = start; - } else { - this.current = null; + private Node skipDeleted(Node node) { + Node n = node; + while (n != null && n.isDeleted()) { + n = n.typeCacheNext; } - this.start = start; + return n; + } + + private void forward() { + needsForward = false; + int startIdx = currentIdIndex; + while (true) { + Node next; + if (current() == PLACE_HOLDER) { + next = getStartNode(ids[currentIdIndex]); + } else { + next = current().typeCacheNext; + } + next = skipDeleted(next); + if (next == null) { + currentIdIndex++; + if (currentIdIndex >= ids.length) { + currentIdIndex = 0; + } + if (currentIdIndex == startIdx) { + needsForward = true; + return; + } + } else { + setCurrent(next); + break; + } + } + } + + private Node current() { + return current[currentIdIndex]; + } + + private void setCurrent(Node n) { + current[currentIdIndex] = n; } @Override public boolean hasNext() { - if (current != null) { - Node next = current.typeCacheNext; - if (next != null) { - while (next.isDeleted()) { - next = next.typeCacheNext; - if (next == null) { - return false; - } - current.typeCacheNext = next; - } - return true; - } - return false; - } else { - return start != null; - } + return findNext() != null; } @Override @SuppressWarnings("unchecked") public T next() { - if (current == null) { - Node result = start; - current = result; - return (T) result; - } else { - Node result = current.typeCacheNext; - current = result; - return (T) result; + Node result = findNext(); + if (result == null) { + throw new NoSuchElementException(); } + needsForward = true; + return (T) result; } @Override @@ -369,11 +417,11 @@ * @return an {@link Iterable} providing all the matching nodes. */ public NodeIterable getNodes(final Class type) { - final Node start = getStartNode(type); + final NodeClass nodeClass = NodeClass.get(type); return new AbstractNodeIterable() { @Override public Iterator iterator() { - return new TypedNodeIterator<>(start); + return new TypedNodeIterator<>(nodeClass); } }; } @@ -387,10 +435,8 @@ return getNodes(type).iterator().hasNext(); } - private Node getStartNode(final Class type) { - int nodeClassId = NodeClass.get(type).iterableId(); - assert nodeClassId != -1 : type + " is not iterable within graphs (missing \"implements IterableNodeType\"?)"; - Node start = nodeCacheFirst.size() <= nodeClassId ? null : nodeCacheFirst.get(nodeClassId); + private Node getStartNode(int iterableId) { + Node start = nodeCacheFirst.size() <= iterableId ? null : nodeCacheFirst.get(iterableId); return start; } diff -r 6939a5af19d5 -r c5a9bcd9493d graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Jan 10 12:03:14 2013 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Jan 10 17:05:31 2013 +0100 @@ -47,8 +47,7 @@ } } - - public static final int NOT_ITERABLE = -1; + static final int NOT_ITERABLE = -1; private static final Class NODE_CLASS = Node.class; private static final Class INPUT_LIST_CLASS = NodeInputList.class; @@ -66,6 +65,7 @@ private final String shortName; private final String nameTemplate; private final int iterableId; + private int[] iterableIds; public NodeClass(Class clazz) { @@ -110,14 +110,27 @@ this.shortName = newShortName; if (Node.IterableNodeType.class.isAssignableFrom(clazz)) { this.iterableId = nextIterableId++; - // TODO (lstadler) add type hierarchy - based node iteration -// for (NodeClass nodeClass : nodeClasses.values()) { -// if (clazz.isAssignableFrom(nodeClass.clazz)) { -// throw new UnsupportedOperationException("iterable non-final Node classes not supported: " + clazz); -// } -// } + List existingClasses = new LinkedList<>(); + for (FieldIntrospection nodeClass : allClasses.values()) { + if (clazz.isAssignableFrom(nodeClass.clazz)) { + existingClasses.add((NodeClass) nodeClass); + } + if (nodeClass.clazz.isAssignableFrom(clazz) && Node.IterableNodeType.class.isAssignableFrom(nodeClass.clazz)) { + NodeClass superNodeClass = (NodeClass) nodeClass; + superNodeClass.iterableIds = Arrays.copyOf(superNodeClass.iterableIds, superNodeClass.iterableIds.length + 1); + superNodeClass.iterableIds[superNodeClass.iterableIds.length - 1] = this.iterableId; + } + } + int[] ids = new int[existingClasses.size() + 1]; + ids[0] = iterableId; + int i = 1; + for (NodeClass other : existingClasses) { + ids[i++] = other.iterableId; + } + this.iterableIds = ids; } else { this.iterableId = NOT_ITERABLE; + this.iterableIds = null; } } @@ -145,6 +158,10 @@ return shortName; } + public int[] iterableIds() { + return iterableIds; + } + public int iterableId() { return iterableId; }