/*

 * Copyright (c) 2012, 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.java;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP2;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X1;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X2;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X1;

import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X2;

import static org.graalvm.compiler.bytecode.Bytecodes.POP;

import static org.graalvm.compiler.bytecode.Bytecodes.POP2;

import static org.graalvm.compiler.bytecode.Bytecodes.SWAP;

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

import static org.graalvm.compiler.nodes.FrameState.TWO_SLOT_MARKER;

import static org.graalvm.compiler.nodes.util.GraphUtil.originalValue;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.function.Function;

import org.graalvm.compiler.bytecode.Bytecode;

import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;

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

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

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

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.java.BciBlockMapping.BciBlock;

import org.graalvm.compiler.nodeinfo.Verbosity;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.ConstantNode;

import org.graalvm.compiler.nodes.FrameState;

import org.graalvm.compiler.nodes.LoopBeginNode;

import org.graalvm.compiler.nodes.LoopExitNode;

import org.graalvm.compiler.nodes.NodeView;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.PhiNode;

import org.graalvm.compiler.nodes.ProxyNode;

import org.graalvm.compiler.nodes.StateSplit;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.ValuePhiNode;

import org.graalvm.compiler.nodes.calc.FloatingNode;

import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;

import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderTool;

import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext.SideEffectsState;

import org.graalvm.compiler.nodes.graphbuilderconf.ParameterPlugin;

import org.graalvm.compiler.nodes.java.MonitorIdNode;

import jdk.vm.ci.code.BytecodeFrame;

import jdk.vm.ci.meta.Assumptions;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.JavaType;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaType;

import jdk.vm.ci.meta.Signature;

public final class FrameStateBuilder implements SideEffectsState {

    private static final ValueNode[] EMPTY_ARRAY = new ValueNode[0];

    private static final MonitorIdNode[] EMPTY_MONITOR_ARRAY = new MonitorIdNode[0];

    private final BytecodeParser parser;

    private final GraphBuilderTool tool;

    private final Bytecode code;

    private int stackSize;

    protected final ValueNode[] locals;

    protected final ValueNode[] stack;

    private ValueNode[] lockedObjects;

    private boolean canVerifyKind;

    /**

     * @see BytecodeFrame#rethrowException

     */

    private boolean rethrowException;

    private MonitorIdNode[] monitorIds;

    private final StructuredGraph graph;

    private final boolean clearNonLiveLocals;

    private FrameState outerFrameState;

    private NodeSourcePosition outerSourcePosition;

    /**

     * The closest {@link StateSplit#hasSideEffect() side-effect} predecessors. There will be more

     * than one when the current block contains no side-effects but merging predecessor blocks do.

     */

    private List<StateSplit> sideEffects;

    /**

     * Creates a new frame state builder for the given method and the given target graph.

     *

     * @param method the method whose frame is simulated

     * @param graph the target graph of Graal nodes created by the builder

     */

    public FrameStateBuilder(GraphBuilderTool tool, ResolvedJavaMethod method, StructuredGraph graph) {

        this(tool, new ResolvedJavaMethodBytecode(method), graph, false);

    }

    /**

     * Creates a new frame state builder for the given code attribute, method and the given target

     * graph. Additionally specifies if nonLiveLocals should be retained.

     *

     * @param code the bytecode in which the frame exists

     * @param graph the target graph of Graal nodes created by the builder

     * @param shouldRetainLocalVariables specifies if nonLiveLocals should be retained in state.

     */

    public FrameStateBuilder(GraphBuilderTool tool, Bytecode code, StructuredGraph graph, boolean shouldRetainLocalVariables) {

        this.tool = tool;

        if (tool instanceof BytecodeParser) {

            this.parser = (BytecodeParser) tool;

        } else {

            this.parser = null;

        }

        this.code = code;

        this.locals = allocateArray(code.getMaxLocals());

        this.stack = allocateArray(Math.max(1, code.getMaxStackSize()));

        this.lockedObjects = allocateArray(0);

        assert graph != null;

        this.monitorIds = EMPTY_MONITOR_ARRAY;

        this.graph = graph;

        this.clearNonLiveLocals = !shouldRetainLocalVariables;

        this.canVerifyKind = true;

    }

    public void disableKindVerification() {

        canVerifyKind = false;

    }

    public void initializeFromArgumentsArray(ValueNode[] arguments) {

        int javaIndex = 0;

        int index = 0;

        if (!getMethod().isStatic()) {

            // set the receiver

            locals[javaIndex] = arguments[index];

            javaIndex = 1;

            index = 1;

        }

        Signature sig = getMethod().getSignature();

        int max = sig.getParameterCount(false);

        for (int i = 0; i < max; i++) {

            JavaKind kind = sig.getParameterKind(i);

            locals[javaIndex] = arguments[index];

            javaIndex++;

            if (kind.needsTwoSlots()) {

                locals[javaIndex] = TWO_SLOT_MARKER;

                javaIndex++;

            }

            index++;

        }

    }

    public void initializeForMethodStart(Assumptions assumptions, boolean eagerResolve, Plugins plugins) {

        int javaIndex = 0;

        int index = 0;

        ResolvedJavaMethod method = getMethod();

        ResolvedJavaType originalType = method.getDeclaringClass();

        if (!method.isStatic()) {

            // add the receiver

            FloatingNode receiver = null;

            StampPair receiverStamp = null;

            if (plugins != null) {

                receiverStamp = plugins.getOverridingStamp(tool, originalType, true);

            }

            if (receiverStamp == null) {

                receiverStamp = StampFactory.forDeclaredType(assumptions, originalType, true);

            }

            if (plugins != null) {

                for (ParameterPlugin plugin : plugins.getParameterPlugins()) {

                    receiver = plugin.interceptParameter(tool, index, receiverStamp);

                    if (receiver != null) {

                        break;

                    }

                }

            }

            if (receiver == null) {

                receiver = new ParameterNode(javaIndex, receiverStamp);

            }

            locals[javaIndex] = graph.addOrUniqueWithInputs(receiver);

            javaIndex = 1;

            index = 1;

        }

        Signature sig = method.getSignature();

        int max = sig.getParameterCount(false);

        ResolvedJavaType accessingClass = originalType;

        for (int i = 0; i < max; i++) {

            JavaType type = sig.getParameterType(i, accessingClass);

            if (eagerResolve) {

                type = type.resolve(accessingClass);

            }

            JavaKind kind = type.getJavaKind();

            StampPair stamp = null;

            if (plugins != null) {

                stamp = plugins.getOverridingStamp(tool, type, false);

            }

            if (stamp == null) {

                // GR-714: subword inputs cannot be trusted

                if (kind.getStackKind() != kind) {

                    stamp = StampPair.createSingle(StampFactory.forKind(JavaKind.Int));

                } else {

                    stamp = StampFactory.forDeclaredType(assumptions, type, false);

                }

            }

            FloatingNode param = null;

            if (plugins != null) {

                for (ParameterPlugin plugin : plugins.getParameterPlugins()) {

                    param = plugin.interceptParameter(tool, index, stamp);

                    if (param != null) {

                        break;

                    }

                }

            }

            if (param == null) {

                param = new ParameterNode(index, stamp);

            }

            locals[javaIndex] = graph.addOrUniqueWithInputs(param);

            javaIndex++;

            if (kind.needsTwoSlots()) {

                locals[javaIndex] = TWO_SLOT_MARKER;

                javaIndex++;

            }

            index++;

        }

    }

    private FrameStateBuilder(FrameStateBuilder other) {

        this.parser = other.parser;

        this.tool = other.tool;

        this.code = other.code;

        this.stackSize = other.stackSize;

        this.locals = other.locals.clone();

        this.stack = other.stack.clone();

        this.lockedObjects = other.lockedObjects.length == 0 ? other.lockedObjects : other.lockedObjects.clone();

        this.rethrowException = other.rethrowException;

        this.canVerifyKind = other.canVerifyKind;

        assert locals.length == code.getMaxLocals();

        assert stack.length == Math.max(1, code.getMaxStackSize());

        assert other.graph != null;

        graph = other.graph;

        clearNonLiveLocals = other.clearNonLiveLocals;

        monitorIds = other.monitorIds.length == 0 ? other.monitorIds : other.monitorIds.clone();

        assert lockedObjects.length == monitorIds.length;

    }

    private static ValueNode[] allocateArray(int length) {

        return length == 0 ? EMPTY_ARRAY : new ValueNode[length];

    }

    public ResolvedJavaMethod getMethod() {

        return code.getMethod();

    }

    @Override

    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("[locals: [");

        for (int i = 0; i < locals.length; i++) {

            sb.append(i == 0 ? "" : ",").append(locals[i] == null ? "_" : locals[i] == TWO_SLOT_MARKER ? "#" : locals[i].toString(Verbosity.Id));

        }

        sb.append("] stack: [");

        for (int i = 0; i < stackSize; i++) {

            sb.append(i == 0 ? "" : ",").append(stack[i] == null ? "_" : stack[i] == TWO_SLOT_MARKER ? "#" : stack[i].toString(Verbosity.Id));

        }

        sb.append("] locks: [");

        for (int i = 0; i < lockedObjects.length; i++) {

            sb.append(i == 0 ? "" : ",").append(lockedObjects[i].toString(Verbosity.Id)).append(" / ").append(monitorIds[i].toString(Verbosity.Id));

        }

        sb.append("]");

        if (rethrowException) {

            sb.append(" rethrowException");

        }

        sb.append("]");

        return sb.toString();

    }

    public FrameState create(int bci, StateSplit forStateSplit) {

        if (parser != null && parser.parsingIntrinsic()) {

            NodeSourcePosition sourcePosition = parser.getGraph().trackNodeSourcePosition() ? createBytecodePosition(bci) : null;

            return parser.intrinsicContext.createFrameState(parser.getGraph(), this, forStateSplit, sourcePosition);

        }

        // Skip intrinsic frames

        return create(bci, parser != null ? parser.getNonIntrinsicAncestor() : null, false, null, null);

    }

    /**

     * @param pushedValues if non-null, values to {@link #push(JavaKind, ValueNode)} to the stack

     *            before creating the {@link FrameState}

     */

    public FrameState create(int bci, BytecodeParser parent, boolean duringCall, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {

        if (outerFrameState == null && parent != null) {

            assert !parent.parsingIntrinsic() : "must already have the next non-intrinsic ancestor";

            outerFrameState = parent.getFrameStateBuilder().create(parent.bci(), parent.getNonIntrinsicAncestor(), true, null, null);

        }

        if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {

            FrameState newFrameState = outerFrameState.duplicateModified(outerFrameState.bci, true, false, JavaKind.Void, new JavaKind[]{JavaKind.Object}, new ValueNode[]{stack[0]});

            return newFrameState;

        }

        if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {

            throw shouldNotReachHere();

        }

        if (pushedValues != null) {

            assert pushedSlotKinds.length == pushedValues.length;

            int stackSizeToRestore = stackSize;

            for (int i = 0; i < pushedValues.length; i++) {

                push(pushedSlotKinds[i], pushedValues[i]);

            }

            FrameState res = graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));

            stackSize = stackSizeToRestore;

            return res;

        } else {

            if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI) {

                assert outerFrameState == null;

                clearLocals();

            }

            return graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));

        }

    }

    public NodeSourcePosition createBytecodePosition(int bci) {

        BytecodeParser parent = parser.getParent();

        NodeSourcePosition position = create(bci, parent);

        return position;

    }

    private NodeSourcePosition create(int bci, BytecodeParser parent) {

        if (outerSourcePosition == null && parent != null) {

            outerSourcePosition = parent.getFrameStateBuilder().createBytecodePosition(parent.bci());

        }

        if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {

            return FrameState.toSourcePosition(outerFrameState);

        }

        if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {

            throw shouldNotReachHere();

        }

        if (parser.intrinsicContext != null && (parent == null || parent.intrinsicContext != parser.intrinsicContext)) {

            // When parsing an intrinsic put in a substitution marker showing the original method as

            // the caller. This keeps the relationship between the method and the method

            // substitution clear in resulting NodeSourcePosition.

            NodeSourcePosition original = new NodeSourcePosition(outerSourcePosition, parser.intrinsicContext.getOriginalMethod(), -1);

            return NodeSourcePosition.substitution(original, code.getMethod(), bci);

        } else {

            return new NodeSourcePosition(outerSourcePosition, code.getMethod(), bci);

        }

    }

    public FrameStateBuilder copy() {

        return new FrameStateBuilder(this);

    }

    private String incompatibilityErrorMessage(String reason, FrameStateBuilder other) {

        return String.format("Frame states being merged are incompatible: %s%n This frame state: %s%nOther frame state: %s%nParser context: %s", reason, this, other, parser);

    }

    /**

     * Checks invariants that must hold when merging {@code other} into this frame state.

     *

     * @param other

     * @throws PermanentBailoutException if the frame states are incompatible with respect to their

     *             locked objects. This indicates bytecode that has unstructured or unbalanced

     *             locks.

     * @throws GraalError if the frame states are incompatible in terms of {@link #rethrowException}

     *             or stack slots

     */

    public void checkCompatibleWith(FrameStateBuilder other) {

        assert code.equals(other.code) && graph == other.graph && localsSize() == other.localsSize() : "Can only compare frame states of the same method";

        assert lockedObjects.length == monitorIds.length && other.lockedObjects.length == other.monitorIds.length : "mismatch between lockedObjects and monitorIds";

        if (rethrowException != other.rethrowException) {

            throw new GraalError(incompatibilityErrorMessage("mismatch in rethrowException flag", other));

        }

        if (stackSize() != other.stackSize()) {

            throw new GraalError(incompatibilityErrorMessage("mismatch in stack sizes", other));

        }

        for (int i = 0; i < stackSize(); i++) {

            ValueNode x = stack[i];

            ValueNode y = other.stack[i];

            assert x != null && y != null;

            if (x != y && (x == TWO_SLOT_MARKER || x.isDeleted() || y == TWO_SLOT_MARKER || y.isDeleted() || x.getStackKind() != y.getStackKind())) {

                throw new GraalError(incompatibilityErrorMessage("mismatch in stack types", other));

            }

        }

        if (lockedObjects.length != other.lockedObjects.length) {

            throw new PermanentBailoutException(incompatibilityErrorMessage("unbalanced monitors - locked objects do not match", other));

        }

        for (int i = 0; i < lockedObjects.length; i++) {

            if (originalValue(lockedObjects[i], false) != originalValue(other.lockedObjects[i], false)) {

                throw new PermanentBailoutException(incompatibilityErrorMessage("unbalanced monitors - locked objects do not match", other));

            }

            if (monitorIds[i] != other.monitorIds[i]) {

                throw new PermanentBailoutException(incompatibilityErrorMessage("unbalanced monitors - monitors do not match", other));

            }

        }

    }

    public void merge(AbstractMergeNode block, FrameStateBuilder other) {

        checkCompatibleWith(other);

        for (int i = 0; i < localsSize(); i++) {

            locals[i] = merge(locals[i], other.locals[i], block);

        }

        for (int i = 0; i < stackSize(); i++) {

            stack[i] = merge(stack[i], other.stack[i], block);

        }

        for (int i = 0; i < lockedObjects.length; i++) {

            lockedObjects[i] = merge(lockedObjects[i], other.lockedObjects[i], block);

            assert monitorIds[i] == other.monitorIds[i];

        }

        if (sideEffects == null) {

            sideEffects = other.sideEffects;

        } else {

            if (other.sideEffects != null) {

                sideEffects.addAll(other.sideEffects);

            }

        }

    }

    private ValueNode merge(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {

        if (currentValue == null || currentValue.isDeleted()) {

            return null;

        } else if (block.isPhiAtMerge(currentValue)) {

            if (otherValue == null || otherValue == TWO_SLOT_MARKER || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {

                // This phi must be dead anyway, add input of correct stack kind to keep the graph

                // invariants.

                ((PhiNode) currentValue).addInput(ConstantNode.defaultForKind(currentValue.getStackKind(), graph));

            } else {

                ((PhiNode) currentValue).addInput(otherValue);

            }

            return currentValue;

        } else if (currentValue != otherValue) {

            if (currentValue == TWO_SLOT_MARKER || otherValue == TWO_SLOT_MARKER) {

                return null;

            } else if (otherValue == null || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {

                return null;

            }

            assert !(block instanceof LoopBeginNode) : String.format("Phi functions for loop headers are create eagerly for changed locals and all stack slots: %s != %s", currentValue, otherValue);

            return createValuePhi(currentValue, otherValue, block);

        } else {

            return currentValue;

        }

    }

    private ValuePhiNode createValuePhi(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {

        ValuePhiNode phi = graph.addWithoutUnique(new ValuePhiNode(currentValue.stamp(NodeView.DEFAULT).unrestricted(), block));

        for (int i = 0; i < block.phiPredecessorCount(); i++) {

            phi.addInput(currentValue);

        }

        phi.addInput(otherValue);

        assert phi.valueCount() == block.phiPredecessorCount() + 1;

        return phi;

    }

    public void inferPhiStamps(AbstractMergeNode block) {

        for (int i = 0; i < localsSize(); i++) {

            inferPhiStamp(block, locals[i]);

        }

        for (int i = 0; i < stackSize(); i++) {

            inferPhiStamp(block, stack[i]);

        }

        for (int i = 0; i < lockedObjects.length; i++) {

            inferPhiStamp(block, lockedObjects[i]);

        }

    }

    private static void inferPhiStamp(AbstractMergeNode block, ValueNode node) {

        if (block.isPhiAtMerge(node)) {

            node.inferStamp();

        }

    }

    public void insertLoopPhis(LocalLiveness liveness, int loopId, LoopBeginNode loopBegin, boolean forcePhis, boolean stampFromValueForForcedPhis) {

        for (int i = 0; i < localsSize(); i++) {

            boolean changedInLoop = liveness.localIsChangedInLoop(loopId, i);

            if (forcePhis || changedInLoop) {

                locals[i] = createLoopPhi(loopBegin, locals[i], stampFromValueForForcedPhis && !changedInLoop);

            }

        }

        for (int i = 0; i < stackSize(); i++) {

            stack[i] = createLoopPhi(loopBegin, stack[i], false);

        }

        for (int i = 0; i < lockedObjects.length; i++) {