/*

 * Copyright (c) 2011, 2017, 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.nodeinfo.NodeCycles.CYCLES_IGNORED;

import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Iterator;

import java.util.function.Consumer;

import org.graalvm.compiler.debug.CounterKey;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.debug.TimerKey;

import org.graalvm.compiler.graph.Node.ValueNumberable;

import org.graalvm.compiler.graph.iterators.NodeIterable;

import org.graalvm.compiler.options.Option;

import org.graalvm.compiler.options.OptionKey;

import org.graalvm.compiler.options.OptionType;

import org.graalvm.compiler.options.OptionValues;

/**

 * This class is a graph container, it contains the set of nodes that belong to this graph.

 */

public class Graph {

    public static class Options {

        @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)//

        public static final OptionKey<Boolean> VerifyGraalGraphs = new OptionKey<>(true);

        @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)//

        public static final OptionKey<Boolean> VerifyGraalGraphEdges = new OptionKey<>(false);

        @Option(help = "Graal graph compression is performed when percent of live nodes falls below this value", type = OptionType.Debug)//

        public static final OptionKey<Integer> GraphCompressionThreshold = new OptionKey<>(70);

    }

    private enum FreezeState {

        Unfrozen,

        TemporaryFreeze,

        DeepFreeze

    }

    public final String name;

    /**

     * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.

     */

    Node[] nodes;

    /**

     * Source information to associate with newly created nodes.

     */

    NodeSourcePosition currentNodeSourcePosition;

    /**

     * Records if updating of node source information is required when performing inlining.

     */

    boolean seenNodeSourcePosition;

    /**

     * The number of valid entries in {@link #nodes}.

     */

    int nodesSize;

    /**

     * Records the modification count for nodes. This is only used in assertions.

     */

    private int[] nodeModCounts;

    /**

     * Records the modification count for nodes' usage lists. This is only used in assertions.

     */

    private int[] nodeUsageModCounts;

    // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.

    // they contain the first and last pointer to a linked list of all nodes with this type.

    private final ArrayList<Node> iterableNodesFirst;

    private final ArrayList<Node> iterableNodesLast;

    private int nodesDeletedSinceLastCompression;

    private int nodesDeletedBeforeLastCompression;

    /**

     * The number of times this graph has been compressed.

     */

    int compressions;

    NodeEventListener nodeEventListener;

    /**

     * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf}

     * nodes.

     */

    private EconomicMap<Node, Node>[] cachedLeafNodes;

    private static final Equivalence NODE_VALUE_COMPARE = new Equivalence() {

        @Override

        public boolean equals(Object a, Object b) {

            if (a == b) {

                return true;

            }

            assert a.getClass() == b.getClass();

            return ((Node) a).valueEquals((Node) b);

        }

        @Override

        public int hashCode(Object k) {

            return ((Node) k).getNodeClass().valueNumber((Node) k);

        }

    };

    /**

     * Indicates that the graph should no longer be modified. Frozen graphs can be used by multiple

     * threads so it's only safe to read them.

     */

    private FreezeState freezeState = FreezeState.Unfrozen;

    /**

     * The option values used while compiling this graph.

     */

    private final OptionValues options;

    /**

     * The {@link DebugContext} used while compiling this graph.

     */

    private DebugContext debug;

    private class NodeSourcePositionScope implements DebugCloseable {

        private final NodeSourcePosition previous;

        NodeSourcePositionScope(NodeSourcePosition sourcePosition) {

            previous = currentNodeSourcePosition;

            currentNodeSourcePosition = sourcePosition;

        }

        @Override

        public DebugContext getDebug() {

            return debug;

        }

        @Override

        public void close() {

            currentNodeSourcePosition = previous;

        }

    }

    public NodeSourcePosition currentNodeSourcePosition() {

        return currentNodeSourcePosition;

    }

    /**

     * Opens a scope in which the source information from {@code node} is copied into nodes created

     * within the scope. If {@code node} has no source information information, no scope is opened

     * and {@code null} is returned.

     *

     * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope

     *         was opened

     */

    public DebugCloseable withNodeSourcePosition(Node node) {

        return withNodeSourcePosition(node.sourcePosition);

    }

    /**

     * Opens a scope in which {@code sourcePosition} is copied into nodes created within the scope.

     * If {@code sourcePosition == null}, no scope is opened and {@code null} is returned.

     *

     * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope

     *         was opened

     */

    public DebugCloseable withNodeSourcePosition(NodeSourcePosition sourcePosition) {

        return sourcePosition != null ? new NodeSourcePositionScope(sourcePosition) : null;

    }

    /**

     * Opens a scope in which newly created nodes do not get any source information added.

     *

     * @return a {@link DebugCloseable} for managing the opened scope

     */

    public DebugCloseable withoutNodeSourcePosition() {

        return new NodeSourcePositionScope(null);

    }

    /**

     * Determines if this graph might contain nodes with source information. This is mainly useful

     * to short circuit logic for updating those positions after inlining since that requires

     * visiting every node in the graph.

     */

    public boolean mayHaveNodeSourcePosition() {

        assert seenNodeSourcePosition || verifyHasNoSourcePosition();

        return seenNodeSourcePosition;

    }

    private boolean verifyHasNoSourcePosition() {

        for (Node node : getNodes()) {

            assert node.getNodeSourcePosition() == null;

        }

        return true;

    }

    /**

     * Creates an empty Graph with no name.

     */

    public Graph(OptionValues options, DebugContext debug) {

        this(null, options, debug);

    }

    /**

     * We only want the expensive modification count tracking when assertions are enabled for the

     * {@link Graph} class.

     */

    @SuppressWarnings("all")

    public static boolean isModificationCountsEnabled() {

        boolean enabled = false;

        assert enabled = true;

        return enabled;

    }

    private static final int INITIAL_NODES_SIZE = 32;

    /**

     * Creates an empty Graph with a given name.

     *

     * @param name the name of the graph, used for debugging purposes

     */

    public Graph(String name, OptionValues options, DebugContext debug) {

        nodes = new Node[INITIAL_NODES_SIZE];

        iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());

        iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());

        this.name = name;

        this.options = options;

        assert debug != null;

        this.debug = debug;

        if (isModificationCountsEnabled()) {

            nodeModCounts = new int[INITIAL_NODES_SIZE];

            nodeUsageModCounts = new int[INITIAL_NODES_SIZE];

        }

    }

    int extractOriginalNodeId(Node node) {

        int id = node.id;

        if (id <= Node.DELETED_ID_START) {

            id = Node.DELETED_ID_START - id;

        }

        return id;

    }

    int modCount(Node node) {

        int id = extractOriginalNodeId(node);

        if (id >= 0 && id < nodeModCounts.length) {

            return nodeModCounts[id];

        }

        return 0;

    }

    void incModCount(Node node) {

        int id = extractOriginalNodeId(node);

        if (id >= 0) {

            if (id >= nodeModCounts.length) {

                nodeModCounts = Arrays.copyOf(nodeModCounts, id * 2 + 30);

            }

            nodeModCounts[id]++;

        } else {

            assert false;

        }

    }

    int usageModCount(Node node) {

        int id = extractOriginalNodeId(node);

        if (id >= 0 && id < nodeUsageModCounts.length) {

            return nodeUsageModCounts[id];

        }

        return 0;

    }

    void incUsageModCount(Node node) {

        int id = extractOriginalNodeId(node);

        if (id >= 0) {

            if (id >= nodeUsageModCounts.length) {

                nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id * 2 + 30);

            }

            nodeUsageModCounts[id]++;

        } else {

            assert false;

        }

    }

    /**

     * Creates a copy of this graph.

     *

     * @param debugForCopy the debug context for the graph copy. This must not be the debug for this

     *            graph if this graph can be accessed from multiple threads (e.g., it's in a cache

     *            accessed by multiple threads).

     */

    public final Graph copy(DebugContext debugForCopy) {

        return copy(name, null, debugForCopy);

    }

    /**

     * Creates a copy of this graph.

     *

     * @param duplicationMapCallback consumer of the duplication map created during the copying

     * @param debugForCopy the debug context for the graph copy. This must not be the debug for this

     *            graph if this graph can be accessed from multiple threads (e.g., it's in a cache

     *            accessed by multiple threads).

     */

    public final Graph copy(Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) {

        return copy(name, duplicationMapCallback, debugForCopy);

    }

    /**

     * Creates a copy of this graph.

     *

     * @param newName the name of the copy, used for debugging purposes (can be null)

     * @param debugForCopy the debug context for the graph copy. This must not be the debug for this

     *            graph if this graph can be accessed from multiple threads (e.g., it's in a cache

     *            accessed by multiple threads).

     */

    public final Graph copy(String newName, DebugContext debugForCopy) {

        return copy(newName, null, debugForCopy);

    }

    /**

     * Creates a copy of this graph.

     *

     * @param newName the name of the copy, used for debugging purposes (can be null)

     * @param duplicationMapCallback consumer of the duplication map created during the copying

     * @param debugForCopy the debug context for the graph copy. This must not be the debug for this

     *            graph if this graph can be accessed from multiple threads (e.g., it's in a cache

     *            accessed by multiple threads).

     */

    protected Graph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) {

        Graph copy = new Graph(newName, options, debugForCopy);

        UnmodifiableEconomicMap<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (EconomicMap<Node, Node>) null);

        if (duplicationMapCallback != null) {

            duplicationMapCallback.accept(duplicates);

        }

        return copy;

    }

    public final OptionValues getOptions() {

        return options;

    }

    public DebugContext getDebug() {

        return debug;

    }

    /**

     * Resets the {@link DebugContext} for this graph to a new value. This is useful when a graph is

     * "handed over" from its creating thread to another thread.

     *

     * This must only be done when the current thread is no longer using the graph. This is in

     * general impossible to test due to races and since metrics can be updated at any time. As

     * such, this method only performs a weak sanity check that at least the current debug context

     * does not have a nested scope open (the top level scope will always be open if scopes are

     * enabled).

     */

    public void resetDebug(DebugContext newDebug) {

        assert newDebug == debug || !debug.inNestedScope() : String.format("Cannot reset the debug context for %s while it has the nested scope \"%s\" open", this, debug.getCurrentScopeName());

        this.debug = newDebug;

    }

    @Override

    public String toString() {

        return name == null ? super.toString() : "Graph " + name;

    }

    /**

     * Gets the number of live nodes in this graph. That is the number of nodes which have been

     * added to the graph minus the number of deleted nodes.

     *

     * @return the number of live nodes in this graph

     */

    public int getNodeCount() {

        return nodesSize - getNodesDeletedSinceLastCompression();

    }

    /**

     * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node

     * identifiers are only stable between compressions. To ensure this constraint is observed, any

     * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.

     */

    public int getCompressions() {

        return compressions;

    }

    /**

     * Gets the number of nodes which have been deleted from this graph since it was last

     * {@linkplain #maybeCompress() compressed}.

     */

    public int getNodesDeletedSinceLastCompression() {

        return nodesDeletedSinceLastCompression;

    }

    /**

     * Gets the total number of nodes which have been deleted from this graph.

     */

    public int getTotalNodesDeleted() {

        return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;

    }

    /**

     * Adds a new node to the graph.

     *

     * @param node the node to be added

     * @return the node which was added to the graph

     */

    public <T extends Node> T add(T node) {

        if (node.getNodeClass().valueNumberable()) {

            throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique.");

        }

        return addHelper(node);

    }

    public <T extends Node> T addWithoutUnique(T node) {

        return addHelper(node);

    }

    public <T extends Node> T addOrUnique(T node) {

        if (node.getNodeClass().valueNumberable()) {

            return uniqueHelper(node);

        }

        return add(node);

    }

    public <T extends Node> T maybeAddOrUnique(T node) {

        if (node.isAlive()) {

            return node;

        }

        return addOrUnique(node);

    }

    public <T extends Node> T addOrUniqueWithInputs(T node) {

        if (node.isAlive()) {

            assert node.graph() == this;

            return node;

        } else {

            assert node.isUnregistered();

            addInputs(node);

            if (node.getNodeClass().valueNumberable()) {

                return uniqueHelper(node);

            }

            return add(node);

        }

    }

    public <T extends Node> T addWithoutUniqueWithInputs(T node) {

        addInputs(node);

        return addHelper(node);

    }

    private final class AddInputsFilter extends Node.EdgeVisitor {

        @Override

        public Node apply(Node self, Node input) {

            if (!input.isAlive()) {

                assert !input.isDeleted();

                return addOrUniqueWithInputs(input);

            } else {

                return input;

            }

        }

    }

    private AddInputsFilter addInputsFilter = new AddInputsFilter();

    private <T extends Node> void addInputs(T node) {

        node.applyInputs(addInputsFilter);

    }

    private <T extends Node> T addHelper(T node) {

        node.initialize(this);

        return node;

    }

    /**

     * The type of events sent to a {@link NodeEventListener}.

     */

    public enum NodeEvent {

        /**

         * A node's input is changed.

         */

        INPUT_CHANGED,

        /**