compiler/graph/Edges.java

/*
 * Copyright (c) 2014, 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 org.graalvm.compiler.graph;

import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
import static org.graalvm.compiler.graph.Node.NOT_ITERABLE;
import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;

import java.util.ArrayList;
import java.util.Iterator;

import org.graalvm.compiler.core.common.Fields;
import org.graalvm.compiler.core.common.FieldsScanner;
import org.graalvm.compiler.graph.NodeClass.EdgeInfo;

/**
 * Describes {@link Node} fields representing the set of inputs for the node or the set of the
 * node's successors.
 */
public abstract class Edges extends Fields {

    /**
     * Constants denoting whether a set of edges are inputs or successors.
     */
    public enum Type {
        Inputs,
        Successors;
    }

    private final int directCount;
    private final Type type;

    public Edges(Type type, int directCount, ArrayList<? extends FieldsScanner.FieldInfo> edges) {
        super(edges);
        this.type = type;
        this.directCount = directCount;
    }

    public static void translateInto(Edges edges, ArrayList<EdgeInfo> infos) {
        for (int index = 0; index < edges.getCount(); index++) {
            infos.add(new EdgeInfo(edges.offsets[index], edges.getName(index), edges.getType(index), edges.getDeclaringClass(index)));
        }
    }

    public static Node getNodeUnsafe(Node node, long offset) {
        return (Node) UNSAFE.getObject(node, offset);
    }

    @SuppressWarnings("unchecked")
    public static NodeList<Node> getNodeListUnsafe(Node node, long offset) {
        return (NodeList<Node>) UNSAFE.getObject(node, offset);
    }

    private static void putNodeUnsafe(Node node, long offset, Node value) {
        UNSAFE.putObject(node, offset, value);
    }

    private static void putNodeListUnsafe(Node node, long offset, NodeList<?> value) {
        UNSAFE.putObject(node, offset, value);
    }

    /**
     * Get the number of direct edges represented by this object. A direct edge goes directly to
     * another {@link Node}. An indirect edge goes via a {@link NodeList}.
     */
    public int getDirectCount() {
        return directCount;
    }

    /**
     * Gets the {@link Node} at the end point of a {@linkplain #getDirectCount() direct} edge.
     *
     * @param node one end point of the edge
     * @param index the index of a non-list the edge (must be less than {@link #getDirectCount()})
     * @return the Node at the other edge of the requested edge
     */
    public static Node getNode(Node node, long[] offsets, int index) {
        return getNodeUnsafe(node, offsets[index]);
    }

    /**
     * Gets the {@link NodeList} at the end point of a {@linkplain #getDirectCount() direct} edge.
     *
     * @param node one end point of the edge
     * @param index the index of a non-list the edge (must be equal to or greater than
     *            {@link #getDirectCount()})
     * @return the {@link NodeList} at the other edge of the requested edge
     */
    public static NodeList<Node> getNodeList(Node node, long[] offsets, int index) {
        return getNodeListUnsafe(node, offsets[index]);
    }

    /**
     * Clear edges in a given node. This is accomplished by setting {@linkplain #getDirectCount()
     * direct} edges to null and replacing the lists containing indirect edges with new lists. The
     * latter is important so that this method can be used to clear the edges of cloned nodes.
     *
     * @param node the node whose edges are to be cleared
     */
    public void clear(Node node) {
        final long[] curOffsets = this.offsets;
        final Type curType = this.type;
        int index = 0;
        int curDirectCount = getDirectCount();
        while (index < curDirectCount) {
            initializeNode(node, index++, null);
        }
        int curCount = getCount();
        while (index < curCount) {
            NodeList<Node> list = getNodeList(node, curOffsets, index);
            if (list != null) {
                int size = list.initialSize;
                NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);

                // replacing with a new list object is the expected behavior!
                initializeList(node, index, newList);
            }
            index++;
        }
    }

    /**
     * Initializes the list edges in a given node based on the size of the list edges in a prototype
     * node.
     *
     * @param node the node whose list edges are to be initialized
     * @param prototype the node whose list edge sizes are used when creating new edge lists
     */
    public void initializeLists(Node node, Node prototype) {
        int index = getDirectCount();
        final long[] curOffsets = this.offsets;
        final Edges.Type curType = this.type;
        while (index < getCount()) {
            NodeList<Node> list = getNodeList(prototype, curOffsets, index);
            if (list != null) {
                int size = list.initialSize;
                NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
                initializeList(node, index, newList);
            }
            index++;
        }
    }

    /**
     * Copies edges from {@code fromNode} to {@code toNode}. The nodes are expected to be of the
     * exact same type.
     *
     * @param fromNode the node from which the edges should be copied.
     * @param toNode the node to which the edges should be copied.
     */
    public void copy(Node fromNode, Node toNode) {
        assert fromNode != toNode;
        assert fromNode.getNodeClass().getClazz() == toNode.getNodeClass().getClazz();
        int index = 0;
        final long[] curOffsets = this.offsets;
        final Type curType = this.type;
        int curDirectCount = getDirectCount();
        while (index < curDirectCount) {
            initializeNode(toNode, index, getNode(fromNode, curOffsets, index));
            index++;
        }
        int curCount = getCount();
        while (index < curCount) {
            NodeList<Node> list = getNodeList(toNode, curOffsets, index);
            NodeList<Node> fromList = getNodeList(fromNode, curOffsets, index);
            if (list == null || list == fromList) {
                list = curType == Edges.Type.Inputs ? new NodeInputList<>(toNode, fromList) : new NodeSuccessorList<>(toNode, fromList);
                initializeList(toNode, index, list);
            } else {
                list.copy(fromList);
            }
            index++;
        }
    }

    @Override
    public void set(Object node, int index, Object value) {
        throw new IllegalArgumentException("Cannot call set on " + this);
    }

    /**
     * Sets the value of a given edge without notifying the new and old nodes on the other end of
     * the edge of the change.
     *
     * @param node the node whose edge is to be updated
     * @param index the index of the edge (between 0 and {@link #getCount()})
     * @param value the node to be written to the edge
     */
    public void initializeNode(Node node, int index, Node value) {
        verifyUpdateValid(node, index, value);
        putNodeUnsafe(node, offsets[index], value);
    }

    public void initializeList(Node node, int index, NodeList<Node> value) {
        verifyUpdateValid(node, index, value);
        putNodeListUnsafe(node, offsets[index], value);
    }

    private void verifyUpdateValid(Node node, int index, Object newValue) {
        if (newValue != null && !getType(index).isAssignableFrom(newValue.getClass())) {
            throw new IllegalArgumentException("Can not assign " + newValue.getClass() + " to " + getType(index) + " in " + node);
        }
    }

    /**
     * Sets the value of a given edge and notifies the new and old nodes on the other end of the
     * edge of the change.
     *
     * @param node the node whose edge is to be updated
     * @param index the index of the edge (between 0 and {@link #getCount()})
     * @param value the node to be written to the edge
     */
    public void setNode(Node node, int index, Node value) {
        assert index < directCount;
        Node old = getNodeUnsafe(node, offsets[index]);
        initializeNode(node, index, value);
        update(node, old, value);
    }

    public abstract void update(Node node, Node oldValue, Node newValue);

    public boolean contains(Node node, Node value) {
        final long[] curOffsets = this.offsets;
        for (int i = 0; i < directCount; i++) {
            if (getNode(node, curOffsets, i) == value) {
                return true;
            }
        }
        for (int i = directCount; i < getCount(); i++) {
            NodeList<?> curList = getNodeList(node, curOffsets, i);
            if (curList != null && curList.contains(value)) {
                return true;
            }
        }
        return false;
    }

    /**
     * An iterator that will iterate over edges.
     *
     * An iterator of this type will not return null values, unless edges are modified concurrently.
     * Concurrent modifications are detected by an assertion on a best-effort basis.
     */
    private static class EdgesIterator implements Iterator<Position> {
        protected final Node node;
        protected final Edges edges;
        protected int index;
        protected int subIndex;
        protected boolean needsForward;
        protected final int directCount;
        protected final long[] offsets;

        /**
         * Creates an iterator that will iterate over some given edges in a given node.
         */
        EdgesIterator(Node node, Edges edges) {
            this.node = node;
            this.edges = edges;
            index = NOT_ITERABLE;
            subIndex = 0;
            needsForward = true;
            this.directCount = edges.getDirectCount();
            this.offsets = edges.getOffsets();
        }

        void forward() {
            needsForward = false;
            if (index < directCount) {
                index++;
                if (index < directCount) {
                    return;
                }
            } else {
                subIndex++;
            }
            if (index < edges.getCount()) {
                forwardNodeList();
            }
        }

        private void forwardNodeList() {
            do {
                NodeList<?> list = Edges.getNodeList(node, offsets, index);
                if (list != null) {
                    if (subIndex < list.size()) {
                        return;
                    }
                }
                subIndex = 0;
                index++;
            } while (index < edges.getCount());
        }

        @Override
        public boolean hasNext() {
            if (needsForward) {
                forward();
            }
            return index < edges.getCount();
        }

        @Override
        public Position next() {
            if (needsForward) {
                forward();
            }
            needsForward = true;
            if (index < directCount) {
                return new Position(edges, index, NOT_ITERABLE);
            } else {
                return new Position(edges, index, subIndex);
            }
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    private static final class EdgesWithModCountIterator extends EdgesIterator {
        private final int modCount;

        private EdgesWithModCountIterator(Node node, Edges edges) {
            super(node, edges);
            assert isModificationCountsEnabled();
            this.modCount = node.modCount();
        }

        @Override
        public boolean hasNext() {
            try {
                return super.hasNext();
            } finally {
                assert modCount == node.modCount() : "must not be modified";
            }
        }

        @Override
        public Position next() {
            try {
                return super.next();
            } finally {
                assert modCount == node.modCount() : "must not be modified";
            }
        }
    }

    public Iterable<Position> getPositionsIterable(final Node node) {
        return new Iterable<Position>() {

            @Override
            public Iterator<Position> iterator() {
                if (isModificationCountsEnabled()) {
                    return new EdgesWithModCountIterator(node, Edges.this);
                } else {
                    return new EdgesIterator(node, Edges.this);
                }
            }
        };
    }

    public Type type() {
        return type;
    }
}