// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.shaking;

import com.android.tools.r8.experimental.graphinfo.ClassGraphNode;
import com.android.tools.r8.experimental.graphinfo.FieldGraphNode;
import com.android.tools.r8.experimental.graphinfo.GraphConsumer;
import com.android.tools.r8.experimental.graphinfo.GraphEdgeInfo;
import com.android.tools.r8.experimental.graphinfo.GraphEdgeInfo.EdgeKind;
import com.android.tools.r8.experimental.graphinfo.GraphNode;
import com.android.tools.r8.experimental.graphinfo.KeepRuleGraphNode;
import com.android.tools.r8.experimental.graphinfo.MethodGraphNode;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.position.Position;
import com.android.tools.r8.position.TextPosition;
import com.android.tools.r8.position.TextRange;
import com.android.tools.r8.references.ClassReference;
import com.android.tools.r8.references.FieldReference;
import com.android.tools.r8.references.MethodReference;
import com.android.tools.r8.references.TypeReference;
import com.android.tools.r8.utils.DescriptorUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.Pair;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.StringUtils.BraceType;
import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * Implementation of the whyareyoukeeping rule using an R8 kept-graph consumer.
 *
 * <p>This class is not intended for public use and clients should define their own consumer
 * instead.
 */
public class WhyAreYouKeepingConsumer extends CollectingGraphConsumer {

  // Single-linked path description when BF searching for a path.
  private static class GraphPath {
    final GraphNode node;
    final GraphPath path;

    public GraphPath(GraphNode node, GraphPath path) {
      assert node != null;
      this.node = node;
      this.path = path;
    }
  }

  public WhyAreYouKeepingConsumer(GraphConsumer subConsumer) {
    super(subConsumer);
  }

  public ClassGraphNode getClassNode(ClassReference clazz) {
    for (GraphNode node : getTargets()) {
      if (node instanceof ClassGraphNode && ((ClassGraphNode) node).getReference() == clazz) {
        return (ClassGraphNode) node;
      }
    }
    return null;
  }

  public MethodGraphNode getMethodNode(MethodReference method) {
    for (GraphNode node : getTargets()) {
      if (node instanceof MethodGraphNode && ((MethodGraphNode) node).getReference() == method) {
        return (MethodGraphNode) node;
      }
    }
    return null;
  }

  public FieldGraphNode getFieldNode(FieldReference field) {
    for (GraphNode node : getTargets()) {
      if (node instanceof FieldGraphNode && ((FieldGraphNode) node).getReference() == field) {
        return (FieldGraphNode) node;
      }
    }
    return null;
  }

  public void printWhyAreYouKeeping(ClassReference reference, PrintStream out) {
    ClassGraphNode node = getClassNode(reference);
    printWhyAreYouKeeping(node != null ? node : new ClassGraphNode(false, reference), out);
  }

  public void printWhyAreYouKeeping(MethodReference reference, PrintStream out) {
    MethodGraphNode node = getMethodNode(reference);
    printWhyAreYouKeeping(node != null ? node : new MethodGraphNode(false, reference), out);
  }

  public void printWhyAreYouKeeping(FieldReference reference, PrintStream out) {
    FieldGraphNode node = getFieldNode(reference);
    printWhyAreYouKeeping(node != null ? node : new FieldGraphNode(false, reference), out);
  }

  public void printWhyAreYouKeeping(GraphNode node, PrintStream out) {
    Formatter formatter = new Formatter(out);
    List<Pair<GraphNode, GraphEdgeInfo>> path = findShortestPathTo(node);
    if (path == null) {
      printNothingKeeping(node, out);
      return;
    }
    formatter.startItem(getNodeString(node));
    for (int i = path.size() - 1; i >= 0; i--) {
      Pair<GraphNode, GraphEdgeInfo> edge = path.get(i);
      printEdge(edge.getFirst(), edge.getSecond(), formatter);
    }
    formatter.endItem();
  }

  private void printNothingKeeping(GraphNode node, PrintStream out) {
    out.print("Nothing is keeping ");
    out.println(getNodeString(node));
  }

  private List<Pair<GraphNode, GraphEdgeInfo>> findShortestPathTo(final GraphNode node) {
    if (node == null) {
      return null;
    }
    Map<GraphNode, GraphNode> seen = new IdentityHashMap<>();
    Deque<GraphPath> queue = new ArrayDeque<>();
    GraphPath path = null;
    GraphNode current = node;
    while (true) {
      Map<GraphNode, Set<GraphEdgeInfo>> sources = getSourcesTargeting(current);
      if (sources == null) {
        // We have reached a root or the current node is not targeted at all.
        return getCanonicalPath(path, node);
      }
      assert !sources.isEmpty();
      for (GraphNode source : sources.keySet()) {
        if (!seen.containsKey(source)) {
          seen.put(source, source);
          queue.addLast(new GraphPath(source, path));
        }
      }
      // The source set was not empty, thus we don't have a real root, but all sources are seen!
      if (queue.isEmpty()) {
        return getCanonicalPath(new GraphPath(GraphNode.cycle(), path), node);
      }
      path = queue.removeFirst();
      current = path.node;
    }
  }

  // Convert a internal path representation to the external API and compute the edge reasons.
  private List<Pair<GraphNode, GraphEdgeInfo>> getCanonicalPath(
      GraphPath path, GraphNode endTarget) {
    if (path == null) {
      // If there is no path to endTarget, treat it as not kept by returning a null path.
      return null;
    }
    List<Pair<GraphNode, GraphEdgeInfo>> canonical = new ArrayList<>();
    while (path.path != null) {
      GraphNode source = path.node;
      if (source.isCycle()) {
        canonical.add(new Pair<>(source, new GraphEdgeInfo(EdgeKind.Unknown)));
      } else {
        GraphNode target = path.path.node;
        Set<GraphEdgeInfo> infos = getSourcesTargeting(target).get(source);
        canonical.add(new Pair<>(source, getCanonicalInfo(infos)));
      }
      path = path.path;
    }
    Set<GraphEdgeInfo> infos = getSourcesTargeting(endTarget).get(path.node);
    canonical.add(new Pair<>(path.node, getCanonicalInfo(infos)));
    return canonical;
  }

  // Compute the most meaningful edge reason.
  private GraphEdgeInfo getCanonicalInfo(Set<GraphEdgeInfo> infos) {
    // TODO(b/120959039): this is pretty bad...
    for (EdgeKind kind : EdgeKind.values()) {
      for (GraphEdgeInfo info : infos) {
        if (info.edgeKind() == kind) {
          return info;
        }
      }
    }
    assert false : "Unexpected empty set of graph edge info";
    return GraphEdgeInfo.unknown();
  }

  private void printEdge(GraphNode node, GraphEdgeInfo info, Formatter formatter) {
    formatter.addReason("is " + info.getInfoPrefix() + ":");
    addNodeMessage(node, formatter);
  }

  private String getNodeString(GraphNode node) {
    if (node instanceof ClassGraphNode) {
      return DescriptorUtils.descriptorToJavaType(
          ((ClassGraphNode) node).getReference().getDescriptor());
    }
    if (node instanceof MethodGraphNode) {
      MethodReference method = ((MethodGraphNode) node).getReference();
      return (method.getReturnType() == null ? "void" : method.getReturnType().getTypeName())
          + ' '
          + method.getHolderClass().getTypeName()
          + '.'
          + method.getMethodName()
          + StringUtils.join(
              ",",
              ListUtils.map(method.getFormalTypes(), TypeReference::getTypeName),
              BraceType.PARENS);
    }
    if (node instanceof FieldGraphNode) {
      FieldReference field = ((FieldGraphNode) node).getReference();
      return field.getFieldType().getTypeName()
          + ' '
          + field.getHolderClass().getTypeName()
          + '.'
          + field.getFieldName();
    }
    if (node instanceof KeepRuleGraphNode) {
      KeepRuleGraphNode keepRuleNode = (KeepRuleGraphNode) node;
      return keepRuleNode.getOrigin() == Origin.unknown()
          ? keepRuleNode.getContent()
          : keepRuleNode.getOrigin() + ":" + shortPositionInfo(keepRuleNode.getPosition());
    }
    if (node == GraphNode.cycle()) {
      return "only cyclic dependencies remain, failed to determine a path from a keep rule";
    }
    assert false : "Unexpected graph node type: " + node;
    return Objects.toString(node);
  }

  private void addNodeMessage(GraphNode node, Formatter formatter) {
    for (String line : StringUtils.splitLines(getNodeString(node))) {
      formatter.addMessage(line);
    }
  }

  private static String shortPositionInfo(Position position) {
    if (position instanceof TextRange) {
      TextPosition start = ((TextRange) position).getStart();
      return start.getLine() + ":" + start.getColumn();
    }
    return position.getDescription();
  }

  private static class Formatter {
    private final PrintStream output;
    private int indentation = -1;

    public Formatter(PrintStream output) {
      this.output = output;
    }

    void startItem(String itemString) {
      indentation++;
      indent();
      output.println(itemString);
    }

    private void indent() {
      for (int i = 0; i < indentation; i++) {
        output.print("  ");
      }
    }

    void addReason(String thing) {
      indent();
      output.print("|- ");
      output.println(thing);
    }

    void addMessage(String thing) {
      indent();
      output.print("|  ");
      output.println(thing);
    }

    void endItem() {
      indentation--;
    }
  }
}