/*

 * Copyright (c) 2011, 2016, 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.core.test;

import static jdk.vm.ci.runtime.JVMCICompiler.INVOCATION_ENTRY_BCI;

import static org.graalvm.compiler.nodes.ConstantNode.getConstantNodes;

import static org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin.InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;

import static org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin.InlineInfo.DO_NOT_INLINE_WITH_EXCEPTION;

import java.lang.annotation.ElementType;

import java.lang.annotation.Retention;

import java.lang.annotation.RetentionPolicy;

import java.lang.annotation.Target;

import java.lang.reflect.Constructor;

import java.lang.reflect.Executable;

import java.lang.reflect.InvocationTargetException;

import java.lang.reflect.Method;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.EnumMap;

import java.util.HashMap;

import java.util.List;

import java.util.ListIterator;

import java.util.Map;

import java.util.Set;

import java.util.function.Supplier;

import org.graalvm.compiler.api.directives.GraalDirectives;

import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;

import org.graalvm.compiler.api.test.Graal;

import org.graalvm.compiler.code.CompilationResult;

import org.graalvm.compiler.core.CompilationPrinter;

import org.graalvm.compiler.core.GraalCompiler;

import org.graalvm.compiler.core.GraalCompiler.Request;

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

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

import org.graalvm.compiler.core.target.Backend;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.DebugDumpHandler;

import org.graalvm.compiler.debug.DebugDumpScope;

import org.graalvm.compiler.debug.DebugHandlersFactory;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.debug.TTY;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeClass;

import org.graalvm.compiler.graph.NodeMap;

import org.graalvm.compiler.java.BytecodeParser;

import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure;

import org.graalvm.compiler.java.GraphBuilderPhase;

import org.graalvm.compiler.lir.asm.CompilationResultBuilderFactory;

import org.graalvm.compiler.lir.phases.LIRSuites;

import org.graalvm.compiler.nodeinfo.NodeInfo;

import org.graalvm.compiler.nodeinfo.NodeSize;

import org.graalvm.compiler.nodeinfo.Verbosity;

import org.graalvm.compiler.nodes.BreakpointNode;

import org.graalvm.compiler.nodes.Cancellable;

import org.graalvm.compiler.nodes.ConstantNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.FrameState;

import org.graalvm.compiler.nodes.FullInfopointNode;

import org.graalvm.compiler.nodes.InvokeNode;

import org.graalvm.compiler.nodes.InvokeWithExceptionNode;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.ProxyNode;

import org.graalvm.compiler.nodes.ReturnNode;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;

import org.graalvm.compiler.nodes.StructuredGraph.Builder;

import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.cfg.Block;

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

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

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

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

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

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

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

import org.graalvm.compiler.nodes.spi.LoweringProvider;

import org.graalvm.compiler.nodes.spi.Replacements;

import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;

import org.graalvm.compiler.options.OptionValues;

import org.graalvm.compiler.phases.BasePhase;

import org.graalvm.compiler.phases.OptimisticOptimizations;

import org.graalvm.compiler.phases.Phase;

import org.graalvm.compiler.phases.PhaseSuite;

import org.graalvm.compiler.phases.common.CanonicalizerPhase;

import org.graalvm.compiler.phases.common.ConvertDeoptimizeToGuardPhase;

import org.graalvm.compiler.phases.schedule.SchedulePhase;

import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;

import org.graalvm.compiler.phases.tiers.HighTierContext;

import org.graalvm.compiler.phases.tiers.MidTierContext;

import org.graalvm.compiler.phases.tiers.Suites;

import org.graalvm.compiler.phases.tiers.TargetProvider;

import org.graalvm.compiler.phases.util.Providers;

import org.graalvm.compiler.printer.GraalDebugHandlersFactory;

import org.graalvm.compiler.runtime.RuntimeProvider;

import org.graalvm.compiler.test.AddExports;

import org.graalvm.compiler.test.GraalTest;

import org.graalvm.compiler.test.JLModule;

import org.junit.After;

import org.junit.Assert;

import org.junit.Test;

import org.junit.internal.AssumptionViolatedException;

import jdk.vm.ci.code.Architecture;

import jdk.vm.ci.code.BailoutException;

import jdk.vm.ci.code.CodeCacheProvider;

import jdk.vm.ci.code.InstalledCode;

import jdk.vm.ci.code.TargetDescription;

import jdk.vm.ci.meta.Assumptions.Assumption;

import jdk.vm.ci.meta.ConstantReflectionProvider;

import jdk.vm.ci.meta.DeoptimizationReason;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.JavaType;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.ProfilingInfo;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaType;

import jdk.vm.ci.meta.SpeculationLog;

/**

 * Base class for Graal compiler unit tests.

 * <p>

 * White box tests for Graal compiler transformations use this pattern:

 * <ol>

 * <li>Create a graph by {@linkplain #parseEager parsing} a method.</li>

 * <li>Manually modify the graph (e.g. replace a parameter node with a constant).</li>

 * <li>Apply a transformation to the graph.</li>

 * <li>Assert that the transformed graph is equal to an expected graph.</li>

 * </ol>

 * <p>

 * See {@link InvokeHintsTest} as an example of a white box test.

 * <p>

 * Black box tests use the {@link #test(String, Object...)} or

 * {@link #testN(int, String, Object...)} to execute some method in the interpreter and compare its

 * result against that produced by a Graal compiled version of the method.

 * <p>

 * These tests will be run by the {@code mx unittest} command.

 */

@AddExports({"java.base/jdk.internal.org.objectweb.asm", "java.base/jdk.internal.org.objectweb.asm.tree"})

public abstract class GraalCompilerTest extends GraalTest {

    /**

     * Gets the initial option values provided by the Graal runtime. These are option values

     * typically parsed from the command line.

     */

    public static OptionValues getInitialOptions() {

        return Graal.getRequiredCapability(OptionValues.class);

    }

    private static final int BAILOUT_RETRY_LIMIT = 1;

    private final Providers providers;

    private final Backend backend;

    /**

     * Representative class for the {@code java.base} module.

     */

    public static final Class<?> JAVA_BASE = Class.class;

    /**

     * Exports the package named {@code packageName} declared in {@code moduleMember}'s module to

     * this object's module. This must be called before accessing packages that are no longer public

     * as of JDK 9.

     */

    protected final void exportPackage(Class<?> moduleMember, String packageName) {

        if (!Java8OrEarlier) {

            JLModule.exportPackageTo(moduleMember, packageName, getClass());

        }

    }

    /**

     * Denotes a test method that must be inlined by the {@link BytecodeParser}.

     */

    @Target({ElementType.METHOD, ElementType.CONSTRUCTOR})

    @Retention(RetentionPolicy.RUNTIME)

    public @interface BytecodeParserForceInline {

    }

    /**

     * Denotes a test method that must never be inlined by the {@link BytecodeParser}.

     */

    @Retention(RetentionPolicy.RUNTIME)

    @Target({ElementType.METHOD, ElementType.CONSTRUCTOR})

    public @interface BytecodeParserNeverInline {

        /**

         * Specifies if the call should be implemented with {@link InvokeWithExceptionNode} instead

         * of {@link InvokeNode}.

         */

        boolean invokeWithException() default false;

    }

    /**

     * Can be overridden by unit tests to verify properties of the graph.

     *

     * @param graph the graph at the end of HighTier

     */

    protected boolean checkHighTierGraph(StructuredGraph graph) {

        return true;

    }

    /**

     * Can be overridden by unit tests to verify properties of the graph.

     *

     * @param graph the graph at the end of MidTier

     */

    protected boolean checkMidTierGraph(StructuredGraph graph) {

        return true;

    }

    /**

     * Can be overridden by unit tests to verify properties of the graph.

     *

     * @param graph the graph at the end of LowTier

     */

    protected boolean checkLowTierGraph(StructuredGraph graph) {

        return true;

    }

    protected static void breakpoint() {

    }

    @SuppressWarnings("unused")

    protected static void breakpoint(int arg0) {

    }

    protected static void shouldBeOptimizedAway() {

    }

    protected Suites createSuites(OptionValues opts) {

        Suites ret = backend.getSuites().getDefaultSuites(opts).copy();

        ListIterator<BasePhase<? super HighTierContext>> iter = ret.getHighTier().findPhase(ConvertDeoptimizeToGuardPhase.class, true);

        if (iter == null) {

            /*

             * in the economy configuration, we don't have the ConvertDeoptimizeToGuard phase, so we

             * just select the first CanonicalizerPhase in HighTier

             */

            iter = ret.getHighTier().findPhase(CanonicalizerPhase.class);

        }

        iter.add(new Phase() {

            @Override

            protected void run(StructuredGraph graph) {

                ComputeLoopFrequenciesClosure.compute(graph);

            }

            @Override

            public float codeSizeIncrease() {

                return NodeSize.IGNORE_SIZE_CONTRACT_FACTOR;

            }

            @Override

            protected CharSequence getName() {

                return "ComputeLoopFrequenciesPhase";

            }

        });

        ret.getHighTier().appendPhase(new Phase() {

            @Override

            protected void run(StructuredGraph graph) {

                assert checkHighTierGraph(graph) : "failed HighTier graph check";

            }

            @Override

            public float codeSizeIncrease() {

                return NodeSize.IGNORE_SIZE_CONTRACT_FACTOR;

            }

            @Override

            protected CharSequence getName() {

                return "CheckGraphPhase";

            }

        });

        ret.getMidTier().appendPhase(new Phase() {

            @Override

            protected void run(StructuredGraph graph) {

                assert checkMidTierGraph(graph) : "failed MidTier graph check";

            }

            @Override

            public float codeSizeIncrease() {

                return NodeSize.IGNORE_SIZE_CONTRACT_FACTOR;

            }

            @Override

            protected CharSequence getName() {

                return "CheckGraphPhase";

            }

        });

        ret.getLowTier().appendPhase(new Phase() {

            @Override

            protected void run(StructuredGraph graph) {

                assert checkLowTierGraph(graph) : "failed LowTier graph check";

            }

            @Override

            public float codeSizeIncrease() {

                return NodeSize.IGNORE_SIZE_CONTRACT_FACTOR;

            }

            @Override

            protected CharSequence getName() {

                return "CheckGraphPhase";

            }

        });

        return ret;

    }

    protected LIRSuites createLIRSuites(OptionValues opts) {

        LIRSuites ret = backend.getSuites().getDefaultLIRSuites(opts).copy();

        return ret;

    }

    public GraalCompilerTest() {

        this.backend = Graal.getRequiredCapability(RuntimeProvider.class).getHostBackend();

        this.providers = getBackend().getProviders();

    }

    /**

     * Set up a test for a non-default backend. The test should check (via {@link #getBackend()} )

     * whether the desired backend is available.

     *

     * @param arch the name of the desired backend architecture

     */

    public GraalCompilerTest(Class<? extends Architecture> arch) {

        RuntimeProvider runtime = Graal.getRequiredCapability(RuntimeProvider.class);

        Backend b = runtime.getBackend(arch);

        if (b != null) {

            this.backend = b;

        } else {

            // Fall back to the default/host backend

            this.backend = runtime.getHostBackend();

        }

        this.providers = backend.getProviders();

    }

    /**

     * Set up a test for a non-default backend.

     *

     * @param backend the desired backend

     */

    public GraalCompilerTest(Backend backend) {

        this.backend = backend;

        this.providers = backend.getProviders();

    }

    @Override

    @After

    public void afterTest() {

        if (invocationPluginExtensions != null) {

            synchronized (this) {

                if (invocationPluginExtensions != null) {

                    extendedInvocationPlugins.removeTestPlugins(invocationPluginExtensions);

                    extendedInvocationPlugins = null;

                    invocationPluginExtensions = null;

                }

            }

        }

        super.afterTest();

    }

    /**

     * Gets a {@link DebugContext} object corresponding to {@code options}, creating a new one if

     * none currently exists. Debug contexts created by this method will have their

     * {@link DebugDumpHandler}s closed in {@link #afterTest()}.

     */

    protected DebugContext getDebugContext() {

        return getDebugContext(getInitialOptions());

    }

    @Override

    protected Collection<DebugHandlersFactory> getDebugHandlersFactories() {

        return Collections.singletonList(new GraalDebugHandlersFactory(getSnippetReflection()));

    }

    protected void assertEquals(StructuredGraph expected, StructuredGraph graph) {

        assertEquals(expected, graph, false, true);

    }

    protected int countUnusedConstants(StructuredGraph graph) {

        int total = 0;

        for (ConstantNode node : getConstantNodes(graph)) {

            if (node.hasNoUsages()) {

                total++;

            }

        }

        return total;

    }

    protected int getNodeCountExcludingUnusedConstants(StructuredGraph graph) {

        return graph.getNodeCount() - countUnusedConstants(graph);

    }

    protected void assertEquals(StructuredGraph expected, StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) {

        String expectedString = getCanonicalGraphString(expected, excludeVirtual, checkConstants);

        String actualString = getCanonicalGraphString(graph, excludeVirtual, checkConstants);

        String mismatchString = compareGraphStrings(expected, expectedString, graph, actualString);

        if (!excludeVirtual && getNodeCountExcludingUnusedConstants(expected) != getNodeCountExcludingUnusedConstants(graph)) {

            expected.getDebug().dump(DebugContext.BASIC_LEVEL, expected, "Node count not matching - expected");

            graph.getDebug().dump(DebugContext.BASIC_LEVEL, graph, "Node count not matching - actual");

            Assert.fail("Graphs do not have the same number of nodes: " + expected.getNodeCount() + " vs. " + graph.getNodeCount() + "\n" + mismatchString);

        }

        if (!expectedString.equals(actualString)) {

            expected.getDebug().dump(DebugContext.BASIC_LEVEL, expected, "mismatching graphs - expected");

            graph.getDebug().dump(DebugContext.BASIC_LEVEL, graph, "mismatching graphs - actual");

            Assert.fail(mismatchString);

        }

    }

    private static String compareGraphStrings(StructuredGraph expectedGraph, String expectedString, StructuredGraph actualGraph, String actualString) {

        if (!expectedString.equals(actualString)) {

            String[] expectedLines = expectedString.split("\n");

            String[] actualLines = actualString.split("\n");

            int diffIndex = -1;

            int limit = Math.min(actualLines.length, expectedLines.length);

            String marker = " <<<";

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

                if (!expectedLines[i].equals(actualLines[i])) {

                    diffIndex = i;

                    break;

                }

            }

            if (diffIndex == -1) {

                // Prefix is the same so add some space after the prefix

                diffIndex = limit;

                if (actualLines.length == limit) {

                    actualLines = Arrays.copyOf(actualLines, limit + 1);

                    actualLines[diffIndex] = "";

                } else {

                    assert expectedLines.length == limit;

                    expectedLines = Arrays.copyOf(expectedLines, limit + 1);

                    expectedLines[diffIndex] = "";

                }

            }

            // Place a marker next to the first line that differs

            expectedLines[diffIndex] = expectedLines[diffIndex] + marker;

            actualLines[diffIndex] = actualLines[diffIndex] + marker;

            String ediff = String.join("\n", expectedLines);

            String adiff = String.join("\n", actualLines);

            return "mismatch in graphs:\n========= expected (" + expectedGraph + ") =========\n" + ediff + "\n\n========= actual (" + actualGraph + ") =========\n" + adiff;

        } else {

            return "mismatch in graphs";

        }

    }

    protected void assertOptimizedAway(StructuredGraph g) {

        Assert.assertEquals(0, g.getNodes().filter(NotOptimizedNode.class).count());

    }

    protected void assertConstantReturn(StructuredGraph graph, int value) {

        String graphString = getCanonicalGraphString(graph, false, true);

        Assert.assertEquals("unexpected number of ReturnNodes: " + graphString, graph.getNodes(ReturnNode.TYPE).count(), 1);

        ValueNode result = graph.getNodes(ReturnNode.TYPE).first().result();

        Assert.assertTrue("unexpected ReturnNode result node: " + graphString, result.isConstant());

        Assert.assertEquals("unexpected ReturnNode result kind: " + graphString, result.asJavaConstant().getJavaKind(), JavaKind.Int);

        Assert.assertEquals("unexpected ReturnNode result: " + graphString, result.asJavaConstant().asInt(), value);

    }

    protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) {

        SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST);

        schedule.apply(graph);

        ScheduleResult scheduleResult = graph.getLastSchedule();

        NodeMap<Integer> canonicalId = graph.createNodeMap();

        int nextId = 0;

        List<String> constantsLines = new ArrayList<>();

        StringBuilder result = new StringBuilder();

        for (Block block : scheduleResult.getCFG().getBlocks()) {

            result.append("Block ").append(block).append(' ');

            if (block == scheduleResult.getCFG().getStartBlock()) {

                result.append("* ");

            }

            result.append("-> ");

            for (Block succ : block.getSuccessors()) {

                result.append(succ).append(' ');

            }

            result.append('\n');

            for (Node node : scheduleResult.getBlockToNodesMap().get(block)) {

                if (node instanceof ValueNode && node.isAlive()) {

                    if (!excludeVirtual || !(node instanceof VirtualObjectNode || node instanceof ProxyNode || node instanceof FullInfopointNode || node instanceof ParameterNode)) {

                        if (node instanceof ConstantNode) {

                            String name = checkConstants ? node.toString(Verbosity.Name) : node.getClass().getSimpleName();

                            if (excludeVirtual) {

                                constantsLines.add(name);

                            } else {

                                constantsLines.add(name + "    (" + filteredUsageCount(node) + ")");

                            }

                        } else {

                            int id;

                            if (canonicalId.get(node) != null) {

                                id = canonicalId.get(node);