/*

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

import jdk.vm.ci.code.BytecodePosition;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

/**

 * This class contains all inlining decisions performed on a graph during the compilation.

 *

 * Each inlining decision consists of:

 *

 * <ul>

 * <li>a value indicating whether the decision was positive or negative</li>

 * <li>the call target method</li>

 * <li>the reason for the inlining decision</li>

 * <li>the name of the phase in which the inlining decision took place</li>

 * <li>the special {@link BytecodePositionWithId} value that describes the position in the bytecode

 * together with the callsite-specific unique identifier</li>

 * <li>the inlining log of the inlined graph, or {@code null} if the decision was negative</li>

 * </ul>

 *

 * A phase that does inlining should use the instance of this class contained in the

 * {@link StructuredGraph} by calling {@link #addDecision} whenever it decides to inline a method.

 * If there are invokes in the graph at the end of the respective phase, then that phase must call

 * {@link #addDecision} to log negative decisions.

 *

 * At the end of the compilation, the contents of the inlining log can be converted into a list of

 * decisions by calling {@link #formatAsList} or into an inlining tree, by calling

 * {@link #formatAsTree}.

 */

public class InliningLog {

    /**

     * A bytecode position with a unique identifier attached.

     *

     * The purpose of this class is to disambiguate callsites that are duplicated by a

     * transformation (such as loop peeling or path duplication).

     */

    public static final class BytecodePositionWithId extends BytecodePosition implements Comparable<BytecodePositionWithId> {

        private final int id;

        public BytecodePositionWithId(BytecodePositionWithId caller, ResolvedJavaMethod method, int bci, int id) {

            super(caller, method, bci);

            this.id = id;

        }

        public BytecodePositionWithId addCallerWithId(BytecodePositionWithId caller) {

            if (getCaller() == null) {

                return new BytecodePositionWithId(caller, getMethod(), getBCI(), id);

            } else {

                return new BytecodePositionWithId(getCaller().addCallerWithId(caller), getMethod(), getBCI(), id);

            }

        }

        public static BytecodePositionWithId create(FrameState state) {

            return create(state, true);

        }

        @SuppressWarnings("deprecation")

        private static BytecodePositionWithId create(FrameState state, boolean topLevel) {

            if (state == null) {

                return null;

            }

            ResolvedJavaMethod method = state.getMethod();

            int bci = topLevel ? state.bci - 3 : state.bci;

            int id = state.getId();

            return new BytecodePositionWithId(create(state.outerFrameState(), false), method, bci, id);

        }

        @Override

        public BytecodePositionWithId getCaller() {

            return (BytecodePositionWithId) super.getCaller();

        }

        public BytecodePositionWithId withoutCaller() {

            return new BytecodePositionWithId(null, getMethod(), getBCI(), id);

        }

        public long getId() {

            return id;

        }

        @Override

        public boolean equals(Object that) {

            return super.equals(that) && this.id == ((BytecodePositionWithId) that).id;

        }

        @Override

        public int hashCode() {

            return super.hashCode() ^ (id << 16);

        }

        @Override

        public int compareTo(BytecodePositionWithId that) {

            int diff = this.getBCI() - that.getBCI();

            if (diff != 0) {

                return diff;

            }

            diff = (int) (this.getId() - that.getId());

            return diff;

        }

    }

    public static final class Decision {

        private final boolean positive;

        private final String reason;

        private final String phase;

        private final ResolvedJavaMethod target;

        private final BytecodePositionWithId position;

        private final InliningLog childLog;

        private Decision(boolean positive, String reason, String phase, ResolvedJavaMethod target, BytecodePositionWithId position, InliningLog childLog) {

            assert position != null;

            this.positive = positive;

            this.reason = reason;

            this.phase = phase;

            this.target = target;

            this.position = position;

            this.childLog = childLog;

        }

        public boolean isPositive() {

            return positive;

        }

        public String getReason() {

            return reason;

        }

        public String getPhase() {

            return phase;

        }

        public BytecodePositionWithId getPosition() {

            return position;

        }

        public InliningLog getChildLog() {

            return childLog;

        }

        public ResolvedJavaMethod getTarget() {

            return target;

        }

    }

    private static class Callsite {

        public final List<String> decisions;

        public final Map<BytecodePositionWithId, Callsite> children;

        public final BytecodePositionWithId position;

        Callsite(BytecodePositionWithId position) {

            this.children = new HashMap<>();

            this.position = position;

            this.decisions = new ArrayList<>();

        }

        public Callsite getOrCreateChild(BytecodePositionWithId fromRootPosition) {

            Callsite child = children.get(fromRootPosition.withoutCaller());

            if (child == null) {

                child = new Callsite(fromRootPosition);

                children.put(fromRootPosition.withoutCaller(), child);

            }

            return child;

        }

        public Callsite createCallsite(BytecodePositionWithId fromRootPosition, String decision) {

            Callsite parent = getOrCreateCallsite(fromRootPosition.getCaller());

            Callsite callsite = parent.getOrCreateChild(fromRootPosition);

            callsite.decisions.add(decision);

            return null;

        }

        private Callsite getOrCreateCallsite(BytecodePositionWithId fromRootPosition) {

            if (fromRootPosition == null) {

                return this;

            } else {

                Callsite parent = getOrCreateCallsite(fromRootPosition.getCaller());

                Callsite callsite = parent.getOrCreateChild(fromRootPosition);

                return callsite;

            }

        }

    }

    private final List<Decision> decisions;

    public InliningLog() {

        this.decisions = new ArrayList<>();

    }

    public List<Decision> getDecisions() {

        return decisions;

    }

    public void addDecision(boolean positive, String reason, String phase, ResolvedJavaMethod target, BytecodePositionWithId position,

                    InliningLog calleeLog) {

        Decision decision = new Decision(positive, reason, phase, target, position, calleeLog);

        decisions.add(decision);

    }

    public String formatAsList() {

        StringBuilder builder = new StringBuilder();

        formatAsList("", null, decisions, builder);

        return builder.toString();

    }

    private void formatAsList(String phasePrefix, BytecodePositionWithId caller, List<Decision> subDecisions, StringBuilder builder) {

        for (Decision decision : subDecisions) {

            String phaseStack = phasePrefix.equals("") ? decision.getPhase() : phasePrefix + "-" + decision.getPhase();

            String target = decision.getTarget().format("%H.%n(%p)");

            String positive = decision.isPositive() ? "inline" : "do not inline";

            BytecodePositionWithId absolutePosition = decision.getPosition().addCallerWithId(caller);

            String position = "  " + decision.getPosition().toString().replaceAll("\n", "\n  ");

            String line = String.format("<%s> %s %s: %s\n%s", phaseStack, positive, target, decision.getReason(), position);

            builder.append(line).append(System.lineSeparator());

            if (decision.getChildLog() != null) {

                formatAsList(phaseStack, absolutePosition, decision.getChildLog().getDecisions(), builder);

            }

        }

    }

    public String formatAsTree() {

        Callsite root = new Callsite(null);

        createTree("", null, root, decisions);

        StringBuilder builder = new StringBuilder();

        formatAsTree(root, "", builder);

        return builder.toString();

    }

    private void createTree(String phasePrefix, BytecodePositionWithId caller, Callsite root, List<Decision> subDecisions) {

        for (Decision decision : subDecisions) {

            String phaseStack = phasePrefix.equals("") ? decision.getPhase() : phasePrefix + "-" + decision.getPhase();

            String target = decision.getTarget().format("%H.%n(%p)");

            BytecodePositionWithId absolutePosition = decision.getPosition().addCallerWithId(caller);

            String line = String.format("<%s> %s: %s", phaseStack, target, decision.getReason());

            root.createCallsite(absolutePosition, line);

            if (decision.getChildLog() != null) {

                createTree(phaseStack, absolutePosition, root, decision.getChildLog().getDecisions());

            }

        }

    }

    private void formatAsTree(Callsite site, String indent, StringBuilder builder) {

        String position = site.position != null ? site.position.withoutCaller().toString() : "<root>";

        String decision = String.join("; ", site.decisions);

        String line = String.format("%s%s; %s", indent, position, decision);

        builder.append(line).append(System.lineSeparator());

        String childIndent = indent + "  ";

        site.children.entrySet().stream().sorted((x, y) -> x.getKey().compareTo(y.getKey())).forEach(e -> {

            formatAsTree(e.getValue(), childIndent, builder);

        });

    }

}