/*

 * Copyright (c) 2011, 2019, 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.Edges.Type.Inputs;

import static org.graalvm.compiler.graph.Edges.Type.Successors;

import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;

import static org.graalvm.compiler.serviceprovider.GraalUnsafeAccess.getUnsafe;

import java.lang.annotation.ElementType;

import java.lang.annotation.RetentionPolicy;

import java.util.Arrays;

import java.util.Collections;

import java.util.EnumSet;

import java.util.Formattable;

import java.util.FormattableFlags;

import java.util.Formatter;

import java.util.HashMap;

import java.util.Map;

import java.util.Objects;

import java.util.function.Predicate;

import java.util.function.Supplier;

import org.graalvm.compiler.core.common.Fields;

import org.graalvm.compiler.core.common.type.AbstractPointerStamp;

import org.graalvm.compiler.core.common.type.Stamp;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.graph.Graph.NodeEventListener;

import org.graalvm.compiler.graph.Graph.Options;

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

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

import org.graalvm.compiler.graph.spi.Simplifiable;

import org.graalvm.compiler.graph.spi.SimplifierTool;

import org.graalvm.compiler.nodeinfo.InputType;

import org.graalvm.compiler.nodeinfo.NodeCycles;

import org.graalvm.compiler.nodeinfo.NodeInfo;

import org.graalvm.compiler.nodeinfo.NodeSize;

import org.graalvm.compiler.nodeinfo.Verbosity;

import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.services.Services;

import sun.misc.Unsafe;

/**

 * This class is the base class for all nodes. It represents a node that can be inserted in a

 * {@link Graph}.

 * <p>

 * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the

 * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and

 * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either

 * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node

 * this field points to.

 * <p>

 * Nodes which are be value numberable should implement the {@link ValueNumberable} interface.

 *

 * <h1>Assertions and Verification</h1>

 *

 * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and

 * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean

 * and throw a VerificationError if it has the wrong value. Both methods will always either throw an

 * exception or return true. They can thus be used within an assert statement, so that the check is

 * only performed if assertions are enabled.

 */

@NodeInfo

public abstract class Node implements Cloneable, Formattable, NodeInterface {

    private static final Unsafe UNSAFE = getUnsafe();

    public static final NodeClass<?> TYPE = null;

    public static final boolean TRACK_CREATION_POSITION = Boolean.parseBoolean(Services.getSavedProperties().get("debug.graal.TrackNodeCreationPosition"));

    static final int DELETED_ID_START = -1000000000;

    static final int INITIAL_ID = -1;

    static final int ALIVE_ID_START = 0;

    // The use of fully qualified class names here and in the rest

    // of this file works around a problem javac has resolving symbols

    /**

     * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of

     * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of

     * type {@link Node} outside of their constructor should call

     * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input.

     */

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.FIELD)

    public static @interface Input {

        InputType value() default InputType.Value;

    }

    /**

     * Denotes an optional (nullable) node input. This should be applied to exactly the fields of a

     * node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of type

     * {@link Node} outside of their constructor should call {@link Node#updateUsages(Node, Node)}

     * just prior to doing the update of the input.

     */

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.FIELD)

    public static @interface OptionalInput {

        InputType value() default InputType.Value;

    }

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.FIELD)

    public static @interface Successor {

    }

    /**

     * Denotes that a parameter of an {@linkplain NodeIntrinsic intrinsic} method must be a compile

     * time constant at all call sites to the intrinsic method.

     */

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.PARAMETER)

    public static @interface ConstantNodeParameter {

    }

    /**

     * Denotes an injected parameter in a {@linkplain NodeIntrinsic node intrinsic} constructor. If

     * the constructor is called as part of node intrinsification, the node intrinsifier will inject

     * an argument for the annotated parameter. Injected parameters must precede all non-injected

     * parameters in a constructor. If the type of the annotated parameter is {@link Stamp}, the

     * {@linkplain Stamp#javaType type} of the injected stamp is the return type of the annotated

     * method (which cannot be {@code void}).

     */

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.PARAMETER)

    public static @interface InjectedNodeParameter {

    }

    /**

     * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the

     * annotated method will be processed by a generated {@code InvocationPlugin} that calls either

     * a factory method or a constructor corresponding with the annotated method.

     * <p>

     * A factory method corresponding to an annotated method is a static method named

     * {@code intrinsify} defined in the class denoted by {@link #value()}. In order, its signature

     * is as follows:

     * <ol>

     * <li>A {@code GraphBuilderContext} parameter.</li>

     * <li>A {@code ResolvedJavaMethod} parameter.</li>

     * <li>A sequence of zero or more {@linkplain InjectedNodeParameter injected} parameters.</li>

     * <li>Remaining parameters that match the declared parameters of the annotated method.</li>

     * </ol>

     * A constructor corresponding to an annotated method is defined in the class denoted by

     * {@link #value()}. In order, its signature is as follows:

     * <ol>

     * <li>A sequence of zero or more {@linkplain InjectedNodeParameter injected} parameters.</li>

     * <li>Remaining parameters that match the declared parameters of the annotated method.</li>

     * </ol>

     * There must be exactly one such factory method or constructor corresponding to a

     * {@link NodeIntrinsic} annotated method.

     */

    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)

    @java.lang.annotation.Target(ElementType.METHOD)

    public static @interface NodeIntrinsic {

        /**

         * The class declaring the factory method or {@link Node} subclass declaring the constructor

         * used to intrinsify a call to the annotated method. The default value is the class in

         * which the annotated method is declared.

         */

        Class<?> value() default NodeIntrinsic.class;

        /**

         * If {@code true}, the factory method or constructor selected by the annotation must have

         * an {@linkplain InjectedNodeParameter injected} {@link Stamp} parameter. Calling

         * {@link AbstractPointerStamp#nonNull()} on the injected stamp is guaranteed to return

         * {@code true}.

         */

        boolean injectedStampIsNonNull() default false;

        /**

         * If {@code true} then this is lowered into a node that has side effects.

         */

        boolean hasSideEffect() default false;

    }

    /**

     * Marker for a node that can be replaced by another node via global value numbering. A

     * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same

     * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node

     * can be replaced by another node of the same type that has exactly the same data values as

     * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors()

     * successors}.

     */

    public interface ValueNumberable {

    }

    /**

     * Marker interface for nodes that contains other nodes. When the inputs to this node changes,

     * users of this node should also be placed on the work list for canonicalization.

     */

    public interface IndirectCanonicalization {

    }

    private Graph graph;

    int id;

    // this next pointer is used in Graph to implement fast iteration over NodeClass types, it

    // therefore points to the next Node of the same type.

    Node typeCacheNext;

    static final int INLINE_USAGE_COUNT = 2;

    private static final Node[] NO_NODES = {};

    /**

     * Head of usage list. The elements of the usage list in order are {@link #usage0},

     * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list.

     */

    Node usage0;

    Node usage1;

    Node[] extraUsages;

    int extraUsagesCount;

    private Node predecessor;

    private NodeClass<? extends Node> nodeClass;

    public static final int NODE_LIST = -2;

    public static final int NOT_ITERABLE = -1;

    static class NodeStackTrace {

        final StackTraceElement[] stackTrace;

        NodeStackTrace() {

            this.stackTrace = new Throwable().getStackTrace();

        }

        private String getString(String label) {

            StringBuilder sb = new StringBuilder();

            if (label != null) {

                sb.append(label).append(": ");

            }

            for (StackTraceElement ste : stackTrace) {

                sb.append("at ").append(ste.toString()).append('\n');

            }

            return sb.toString();

        }

        String getStrackTraceString() {

            return getString(null);

        }

        @Override

        public String toString() {

            return getString(getClass().getSimpleName());

        }

    }

    static class NodeCreationStackTrace extends NodeStackTrace {

    }

    public static class NodeInsertionStackTrace extends NodeStackTrace {

    }

    public Node(NodeClass<? extends Node> c) {

        init(c);

    }

    final void init(NodeClass<? extends Node> c) {

        assert c.getJavaClass() == this.getClass();

        this.nodeClass = c;

        id = INITIAL_ID;

        extraUsages = NO_NODES;

        if (TRACK_CREATION_POSITION) {

            setCreationPosition(new NodeCreationStackTrace());

        }

    }

    final int id() {

        return id;

    }

    @Override

    public Node asNode() {

        return this;

    }

    /**

     * Gets the graph context of this node.

     */

    public Graph graph() {

        return graph;

    }

    /**

     * Gets the option values associated with this node's graph.

     */

    public final OptionValues getOptions() {

        return graph == null ? null : graph.getOptions();

    }

    /**

     * Gets the debug context associated with this node's graph.

     */

    public final DebugContext getDebug() {

        return graph.getDebug();

    }

    /**

     * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input

     * edges of this node.

     *

     * @return an {@link NodeIterable iterable} for all non-null input edges.

     */

    public NodeIterable<Node> inputs() {

        return nodeClass.getInputIterable(this);

    }

    /**

     * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges

     * of this node.

     *

     * @return an {@link Iterable iterable} for all non-null input edges.

     */

    public Iterable<Position> inputPositions() {

        return nodeClass.getInputEdges().getPositionsIterable(this);

    }

    public abstract static class EdgeVisitor {

        public abstract Node apply(Node source, Node target);

    }

    /**

     * Applies the given visitor to all inputs of this node.

     *

     * @param visitor the visitor to be applied to the inputs

     */

    public void applyInputs(EdgeVisitor visitor) {

        nodeClass.applyInputs(this, visitor);

    }

    /**

     * Applies the given visitor to all successors of this node.

     *

     * @param visitor the visitor to be applied to the successors

     */

    public void applySuccessors(EdgeVisitor visitor) {

        nodeClass.applySuccessors(this, visitor);

    }

    /**

     * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null successor

     * edges of this node.

     *

     * @return an {@link NodeIterable iterable} for all non-null successor edges.

     */

    public NodeIterable<Node> successors() {

        assert !this.isDeleted() : this;

        return nodeClass.getSuccessorIterable(this);

    }

    /**

     * Returns an {@link Iterable iterable} which can be used to traverse all successor edge

     * positions of this node.

     *

     * @return an {@link Iterable iterable} for all successor edge positoins.

     */

    public Iterable<Position> successorPositions() {

        return nodeClass.getSuccessorEdges().getPositionsIterable(this);

    }

    /**

     * Gets the maximum number of usages this node has had at any point in time.

     */

    public int getUsageCount() {

        if (usage0 == null) {

            return 0;

        }

        if (usage1 == null) {

            return 1;

        }

        return INLINE_USAGE_COUNT + extraUsagesCount;

    }

    /**

     * Gets the list of nodes that use this node (i.e., as an input).

     */

    public final NodeIterable<Node> usages() {

        return new NodeUsageIterable(this);

    }

    /**

     * Checks whether this node has no usages.

     */

    public final boolean hasNoUsages() {

        return this.usage0 == null;

    }

    /**

     * Checks whether this node has usages.

     */

    public final boolean hasUsages() {

        return this.usage0 != null;

    }

    /**

     * Checks whether this node has more than one usages.

     */

    public final boolean hasMoreThanOneUsage() {

        return this.usage1 != null;

    }

    /**

     * Checks whether this node has exactly one usgae.

     */

    public final boolean hasExactlyOneUsage() {

        return hasUsages() && !hasMoreThanOneUsage();

    }

    /**

     * Adds a given node to this node's {@linkplain #usages() usages}.

     *

     * @param node the node to add

     */

    void addUsage(Node node) {

        incUsageModCount();

        if (usage0 == null) {

            usage0 = node;

        } else if (usage1 == null) {

            usage1 = node;

        } else {

            int length = extraUsages.length;

            if (length == 0) {

                extraUsages = new Node[4];

            } else if (extraUsagesCount == length) {

                Node[] newExtraUsages = new Node[length * 2 + 1];

                System.arraycopy(extraUsages, 0, newExtraUsages, 0, length);

                extraUsages = newExtraUsages;

            }

            extraUsages[extraUsagesCount++] = node;

        }

    }

    private void movUsageFromEndTo(int destIndex) {

        if (destIndex >= INLINE_USAGE_COUNT) {

            movUsageFromEndToExtraUsages(destIndex - INLINE_USAGE_COUNT);

        } else if (destIndex == 1) {

            movUsageFromEndToIndexOne();

        } else {

            assert destIndex == 0;

            movUsageFromEndToIndexZero();

        }

    }

    private void movUsageFromEndToExtraUsages(int destExtraIndex) {

        this.extraUsagesCount--;

        Node n = extraUsages[extraUsagesCount];

        extraUsages[destExtraIndex] = n;

        extraUsages[extraUsagesCount] = null;

    }

    private void movUsageFromEndToIndexZero() {

        if (extraUsagesCount > 0) {

            this.extraUsagesCount--;

            usage0 = extraUsages[extraUsagesCount];

            extraUsages[extraUsagesCount] = null;

        } else if (usage1 != null) {

            usage0 = usage1;

            usage1 = null;

        } else {

            usage0 = null;

        }

    }

    private void movUsageFromEndToIndexOne() {

        if (extraUsagesCount > 0) {

            this.extraUsagesCount--;

            usage1 = extraUsages[extraUsagesCount];

            extraUsages[extraUsagesCount] = null;

        } else {

            assert usage1 != null;

            usage1 = null;

        }

    }

    /**

     * Removes a given node from this node's {@linkplain #usages() usages}.

     *

     * @param node the node to remove

     * @return whether or not {@code usage} was in the usage list

     */

    public boolean removeUsage(Node node) {

        assert node != null;

        // For large graphs, usage removal is performance critical.

        // Furthermore, it is critical that this method maintains the invariant that the usage list

        // has no null element preceding a non-null element.

        incUsageModCount();