/*

 * 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.core.common.Fields.translateInto;

import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;

import static org.graalvm.compiler.graph.Edges.translateInto;

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

import static org.graalvm.compiler.graph.InputEdges.translateInto;

import static org.graalvm.compiler.graph.Node.WithAllEdges;

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

import java.lang.annotation.Annotation;

import java.lang.reflect.AnnotatedElement;

import java.lang.reflect.Field;

import java.lang.reflect.Modifier;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.EnumSet;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Objects;

import java.util.concurrent.atomic.AtomicInteger;

import jdk.internal.vm.compiler.collections.EconomicMap;

import jdk.internal.vm.compiler.collections.Equivalence;

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

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

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

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.TTY;

import org.graalvm.compiler.debug.TimerKey;

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

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

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

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

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

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

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

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

import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative;

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

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 sun.misc.Unsafe;

/**

 * Metadata for every {@link Node} type. The metadata includes:

 * <ul>

 * <li>The offsets of fields annotated with {@link Input} and {@link Successor} as well as methods

 * for iterating over such fields.</li>

 * <li>The identifier for an {@link IterableNodeType} class.</li>

 * </ul>

 */

public final class NodeClass<T> extends FieldIntrospection<T> {

    private static final Unsafe UNSAFE = getUnsafe();

    // Timers for creation of a NodeClass instance

    private static final TimerKey Init_FieldScanning = DebugContext.timer("NodeClass.Init.FieldScanning");

    private static final TimerKey Init_FieldScanningInner = DebugContext.timer("NodeClass.Init.FieldScanning.Inner");

    private static final TimerKey Init_AnnotationParsing = DebugContext.timer("NodeClass.Init.AnnotationParsing");

    private static final TimerKey Init_Edges = DebugContext.timer("NodeClass.Init.Edges");

    private static final TimerKey Init_Data = DebugContext.timer("NodeClass.Init.Data");

    private static final TimerKey Init_AllowedUsages = DebugContext.timer("NodeClass.Init.AllowedUsages");

    private static final TimerKey Init_IterableIds = DebugContext.timer("NodeClass.Init.IterableIds");

    public static final long MAX_EDGES = 8;

    public static final long MAX_LIST_EDGES = 6;

    public static final long OFFSET_MASK = 0xFC;

    public static final long LIST_MASK = 0x01;

    public static final long NEXT_EDGE = 0x08;

    @SuppressWarnings("try")

    private static <T extends Annotation> T getAnnotationTimed(AnnotatedElement e, Class<T> annotationClass, DebugContext debug) {

        try (DebugCloseable s = Init_AnnotationParsing.start(debug)) {

            return e.getAnnotation(annotationClass);

        }

    }

    /**

     * Gets the {@link NodeClass} associated with a given {@link Class}.

     */

    public static <T> NodeClass<T> create(Class<T> c) {

        assert getUnchecked(c) == null;

        Class<? super T> superclass = c.getSuperclass();

        NodeClass<? super T> nodeSuperclass = null;

        if (superclass != NODE_CLASS) {

            nodeSuperclass = get(superclass);

        }

        return new NodeClass<>(c, nodeSuperclass);

    }

    @SuppressWarnings("unchecked")

    private static <T> NodeClass<T> getUnchecked(Class<T> clazz) {

        try {

            Field field = clazz.getDeclaredField("TYPE");

            field.setAccessible(true);

            return (NodeClass<T>) field.get(null);

        } catch (IllegalArgumentException | IllegalAccessException | NoSuchFieldException | SecurityException e) {

            throw new RuntimeException("Could not load Graal NodeClass TYPE field for " + clazz, e);

        }

    }

    public static <T> NodeClass<T> get(Class<T> clazz) {

        int numTries = 0;

        while (true) {

            boolean shouldBeInitializedBefore = UNSAFE.shouldBeInitialized(clazz);

            NodeClass<T> result = getUnchecked(clazz);

            if (result != null || clazz == NODE_CLASS) {

                return result;

            }

            /*

             * GR-9537: We observed a transient problem with TYPE fields being null. Retry a couple

             * of times and print something to the log so that we can gather more diagnostic

             * information without failing gates.

             */

            numTries++;

            boolean shouldBeInitializedAfter = UNSAFE.shouldBeInitialized(clazz);

            String msg = "GR-9537 Reflective field access of TYPE field returned null. This is probably a bug in HotSpot class initialization. " +

                            " clazz: " + clazz.getTypeName() + ", numTries: " + numTries +

                            ", shouldBeInitializedBefore: " + shouldBeInitializedBefore + ", shouldBeInitializedAfter: " + shouldBeInitializedAfter;

            if (numTries <= 100) {

                TTY.println(msg);

                UNSAFE.ensureClassInitialized(clazz);

            } else {

                throw GraalError.shouldNotReachHere(msg);

            }

            return result;

        }

    }

    private static final Class<?> NODE_CLASS = Node.class;

    private static final Class<?> INPUT_LIST_CLASS = NodeInputList.class;

    private static final Class<?> SUCCESSOR_LIST_CLASS = NodeSuccessorList.class;

    private static AtomicInteger nextIterableId = new AtomicInteger();

    private static AtomicInteger nextLeafId = new AtomicInteger();

    private final InputEdges inputs;

    private final SuccessorEdges successors;

    private final NodeClass<? super T> superNodeClass;

    private final boolean canGVN;

    private final int startGVNNumber;

    private final String nameTemplate;

    private final int iterableId;

    private final EnumSet<InputType> allowedUsageTypes;

    private int[] iterableIds;

    private final long inputsIteration;

    private final long successorIteration;

    private static final CounterKey ITERABLE_NODE_TYPES = DebugContext.counter("IterableNodeTypes");

    /**

     * Determines if this node type implements {@link Canonicalizable}.

     */

    private final boolean isCanonicalizable;

    /**

     * Determines if this node type implements {@link BinaryCommutative}.

     */

    private final boolean isCommutative;

    /**

     * Determines if this node type implements {@link Simplifiable}.

     */

    private final boolean isSimplifiable;

    private final boolean isLeafNode;

    private final int leafId;

    public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass) {

        this(clazz, superNodeClass, new FieldsScanner.DefaultCalcOffset(), null, 0);

    }

    @SuppressWarnings("try")

    public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass, FieldsScanner.CalcOffset calcOffset, int[] presetIterableIds, int presetIterableId) {

        super(clazz);

        DebugContext debug = DebugContext.forCurrentThread();

        this.superNodeClass = superNodeClass;

        assert NODE_CLASS.isAssignableFrom(clazz);

        this.isCanonicalizable = Canonicalizable.class.isAssignableFrom(clazz);

        this.isCommutative = BinaryCommutative.class.isAssignableFrom(clazz);

        if (Canonicalizable.Unary.class.isAssignableFrom(clazz) || Canonicalizable.Binary.class.isAssignableFrom(clazz)) {

            assert Canonicalizable.Unary.class.isAssignableFrom(clazz) ^ Canonicalizable.Binary.class.isAssignableFrom(clazz) : clazz + " should implement either Unary or Binary, not both";

        }

        this.isSimplifiable = Simplifiable.class.isAssignableFrom(clazz);

        NodeFieldsScanner fs = new NodeFieldsScanner(calcOffset, superNodeClass, debug);

        try (DebugCloseable t = Init_FieldScanning.start(debug)) {

            fs.scan(clazz, clazz.getSuperclass(), false);

        }

        try (DebugCloseable t1 = Init_Edges.start(debug)) {

            successors = new SuccessorEdges(fs.directSuccessors, fs.successors);

            successorIteration = computeIterationMask(successors.type(), successors.getDirectCount(), successors.getOffsets());

            inputs = new InputEdges(fs.directInputs, fs.inputs);

            inputsIteration = computeIterationMask(inputs.type(), inputs.getDirectCount(), inputs.getOffsets());

        }

        try (DebugCloseable t1 = Init_Data.start(debug)) {

            data = new Fields(fs.data);

        }

        isLeafNode = inputs.getCount() + successors.getCount() == 0;

        if (isLeafNode) {

            this.leafId = nextLeafId.getAndIncrement();

        } else {

            this.leafId = -1;

        }

        canGVN = Node.ValueNumberable.class.isAssignableFrom(clazz);

        startGVNNumber = clazz.getName().hashCode();

        NodeInfo info = getAnnotationTimed(clazz, NodeInfo.class, debug);

        assert info != null : "Missing NodeInfo annotation on " + clazz;

        if (!info.nameTemplate().isEmpty()) {

            this.nameTemplate = info.nameTemplate();

        } else if (!info.shortName().isEmpty()) {

            this.nameTemplate = info.shortName();

        } else {

            this.nameTemplate = "";

        }

        try (DebugCloseable t1 = Init_AllowedUsages.start(debug)) {

            allowedUsageTypes = superNodeClass == null ? EnumSet.noneOf(InputType.class) : superNodeClass.allowedUsageTypes.clone();

            allowedUsageTypes.addAll(Arrays.asList(info.allowedUsageTypes()));

        }

        if (presetIterableIds != null) {

            this.iterableIds = presetIterableIds;

            this.iterableId = presetIterableId;

        } else if (IterableNodeType.class.isAssignableFrom(clazz)) {

            ITERABLE_NODE_TYPES.increment(debug);

            try (DebugCloseable t1 = Init_IterableIds.start(debug)) {

                this.iterableId = nextIterableId.getAndIncrement();

                NodeClass<?> snc = superNodeClass;

                while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {

                    snc.addIterableId(iterableId);

                    snc = snc.superNodeClass;

                }

                this.iterableIds = new int[]{iterableId};

            }

        } else {

            this.iterableId = Node.NOT_ITERABLE;

            this.iterableIds = null;

        }

        assert verifyIterableIds();

        try (DebugContext.Scope scope = debug.scope("NodeCosts")) {

            /*

             * Note: We do not check for the existence of the node cost annotations during

             * construction as not every node needs to have them set. However if costs are queried,

             * after the construction of the node class, they must be properly set. This is

             * important as we can not trust our cost model if there are unspecified nodes. Nodes

             * that do not need cost annotations are e.g. abstractions like FixedNode or

             * FloatingNode or ValueNode. Sub classes where costs are not specified will ask the

             * superclass for their costs during node class initialization. Therefore getters for

             * cycles and size can omit verification during creation.

             */

            NodeCycles c = info.cycles();

            if (c == NodeCycles.CYCLES_UNSET) {

                cycles = superNodeClass != null ? superNodeClass.cycles : NodeCycles.CYCLES_UNSET;

            } else {

                cycles = c;

            }

            assert cycles != null;

            NodeSize s = info.size();

            if (s == NodeSize.SIZE_UNSET) {

                size = superNodeClass != null ? superNodeClass.size : NodeSize.SIZE_UNSET;

            } else {

                size = s;

            }

            assert size != null;

            debug.log("Node cost for node of type __| %s |_, cycles:%s,size:%s", clazz, cycles, size);

        }

    }

    private final NodeCycles cycles;

    private final NodeSize size;

    public NodeCycles cycles() {

        return cycles;

    }

    public NodeSize size() {

        return size;

    }

    public static long computeIterationMask(Type type, int directCount, long[] offsets) {

        long mask = 0;

        if (offsets.length > NodeClass.MAX_EDGES) {

            throw new GraalError("Exceeded maximum of %d edges (%s)", NodeClass.MAX_EDGES, type);

        }

        if (offsets.length - directCount > NodeClass.MAX_LIST_EDGES) {

            throw new GraalError("Exceeded maximum of %d list edges (%s)", NodeClass.MAX_LIST_EDGES, type);

        }

        for (int i = offsets.length - 1; i >= 0; i--) {

            long offset = offsets[i];

            assert ((offset & 0xFF) == offset) : "field offset too large!";

            mask <<= NodeClass.NEXT_EDGE;

            mask |= offset;

            if (i >= directCount) {

                mask |= 0x3;

            }

        }

        return mask;

    }

    private synchronized void addIterableId(int newIterableId) {

        assert !containsId(newIterableId, iterableIds);

        int[] copy = Arrays.copyOf(iterableIds, iterableIds.length + 1);

        copy[iterableIds.length] = newIterableId;

        iterableIds = copy;

    }

    private boolean verifyIterableIds() {

        NodeClass<?> snc = superNodeClass;

        while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {

            assert containsId(iterableId, snc.iterableIds);

            snc = snc.superNodeClass;

        }

        return true;

    }

    private static boolean containsId(int iterableId, int[] iterableIds) {

        for (int i : iterableIds) {

            if (i == iterableId) {

                return true;

            }

        }

        return false;

    }

    private String shortName;

    public String shortName() {

        if (shortName == null) {

            NodeInfo info = getClazz().getAnnotation(NodeInfo.class);

            if (!info.shortName().isEmpty()) {

                shortName = info.shortName();

            } else {

                String localShortName = getClazz().getSimpleName();

                if (localShortName.endsWith("Node") && !localShortName.equals("StartNode") && !localShortName.equals("EndNode")) {

                    shortName = localShortName.substring(0, localShortName.length() - 4);

                } else {

                    shortName = localShortName;

                }

            }

        }

        return shortName;

    }

    @Override

    public Fields[] getAllFields() {

        return new Fields[]{data, inputs, successors};

    }

    int[] iterableIds() {

        return iterableIds;

    }

    public int iterableId() {

        return iterableId;

    }

    public boolean valueNumberable() {

        return canGVN;

    }

    /**

     * Determines if this node type implements {@link Canonicalizable}.

     */

    public boolean isCanonicalizable() {

        return isCanonicalizable;

    }

    /**

     * Determines if this node type implements {@link BinaryCommutative}.

     */

    public boolean isCommutative() {

        return isCommutative;

    }

    /**

     * Determines if this node type implements {@link Simplifiable}.

     */

    public boolean isSimplifiable() {

        return isSimplifiable;

    }

    static int allocatedNodeIterabledIds() {

        return nextIterableId.get();

    }

    public EnumSet<InputType> getAllowedUsageTypes() {

        return allowedUsageTypes;

    }

    /**

     * Describes a field representing an input or successor edge in a node.

     */

    protected static class EdgeInfo extends FieldsScanner.FieldInfo {

        public EdgeInfo(long offset, String name, Class<?> type, Class<?> declaringClass) {

            super(offset, name, type, declaringClass);

        }

        /**

         * Sorts non-list edges before list edges.

         */

        @Override

        public int compareTo(FieldsScanner.FieldInfo o) {

            if (NodeList.class.isAssignableFrom(o.type)) {

                if (!NodeList.class.isAssignableFrom(type)) {

                    return -1;

                }

            } else {

                if (NodeList.class.isAssignableFrom(type)) {

                    return 1;

                }

            }

            return super.compareTo(o);

        }

    }

    /**

     * Describes a field representing an {@linkplain Type#Inputs input} edge in a node.

     */

    protected static class InputInfo extends EdgeInfo {

        final InputType inputType;

        final boolean optional;

        public InputInfo(long offset, String name, Class<?> type, Class<?> declaringClass, InputType inputType, boolean optional) {

            super(offset, name, type, declaringClass);

            this.inputType = inputType;

            this.optional = optional;

        }

        @Override

        public String toString() {

            return super.toString() + "{inputType=" + inputType + ", optional=" + optional + "}";

        }

    }

    protected static class NodeFieldsScanner extends FieldsScanner {

        public final ArrayList<InputInfo> inputs = new ArrayList<>();

        public final ArrayList<EdgeInfo> successors = new ArrayList<>();

        int directInputs;

        int directSuccessors;

        final DebugContext debug;

        protected NodeFieldsScanner(FieldsScanner.CalcOffset calc, NodeClass<?> superNodeClass, DebugContext debug) {

            super(calc);

            this.debug = debug;

            if (superNodeClass != null) {

                translateInto(superNodeClass.inputs, inputs);

                translateInto(superNodeClass.successors, successors);

                translateInto(superNodeClass.data, data);

                directInputs = superNodeClass.inputs.getDirectCount();

                directSuccessors = superNodeClass.successors.getDirectCount();

            }

        }

        @SuppressWarnings("try")

        @Override

        protected void scanField(Field field, long offset) {

            Input inputAnnotation = getAnnotationTimed(field, Node.Input.class, debug);

            OptionalInput optionalInputAnnotation = getAnnotationTimed(field, Node.OptionalInput.class, debug);

            Successor successorAnnotation = getAnnotationTimed(field, Successor.class, debug);

            try (DebugCloseable s = Init_FieldScanningInner.start(debug)) {

                Class<?> type = field.getType();

                int modifiers = field.getModifiers();

                if (inputAnnotation != null || optionalInputAnnotation != null) {

                    assert successorAnnotation == null : "field cannot be both input and successor";

                    if (INPUT_LIST_CLASS.isAssignableFrom(type)) {

                        // NodeInputList fields should not be final since they are

                        // written (via Unsafe) in clearInputs()

                        GraalError.guarantee(!Modifier.isFinal(modifiers), "NodeInputList input field %s should not be final", field);

                        GraalError.guarantee(!Modifier.isPublic(modifiers), "NodeInputList input field %s should not be public", field);