// Copyright (c) 2017, 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.ir.conversion.callgraph;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.ir.conversion.callgraph.CallSiteInformation.CallGraphBasedCallSiteInformation;
import com.android.tools.r8.ir.conversion.callgraph.CycleEliminator.CycleEliminationResult;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
import com.google.common.collect.Sets;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * Call graph representation.
 *
 * <p>Each node in the graph contain the methods called and the calling methods. For virtual and
 * interface calls all potential calls from subtypes are recorded.
 *
 * <p>Only methods in the program - not library methods - are represented.
 *
 * <p>The directional edges are represented as sets of nodes in each node (called methods and
 * callees).
 *
 * <p>A call from method <code>a</code> to method <code>b</code> is only present once no matter how
 * many calls of <code>a</code> there are in <code>a</code>.
 *
 * <p>Recursive calls are not present.
 */
public class CallGraph extends CallGraphBase<Node> {

  private final CycleEliminationResult cycleEliminationResult;

  CallGraph(Map<DexMethod, Node> nodes) {
    this(nodes, null);
  }

  CallGraph(Map<DexMethod, Node> nodes, CycleEliminationResult cycleEliminationResult) {
    super(nodes);
    this.cycleEliminationResult = cycleEliminationResult;
  }

  public static CallGraphBuilder builder(AppView<AppInfoWithLiveness> appView) {
    return new CallGraphBuilder(appView);
  }

  public static CallGraph createForTesting(Collection<Node> nodes) {
    return new CallGraph(
        nodes.stream()
            .collect(
                Collectors.toMap(
                    node -> node.getProgramMethod().getReference(), Function.identity())));
  }

  public CallSiteInformation createCallSiteInformation(AppView<AppInfoWithLiveness> appView) {
    // Don't leverage single/dual call site information when we are not tree shaking.
    return appView.options().isShrinking()
        ? new CallGraphBasedCallSiteInformation(appView, this)
        : CallSiteInformation.empty();
  }

  public ProgramMethodSet extractLeaves() {
    return extractNodes(Node::isLeaf, Node::cleanCallersAndReadersForRemoval);
  }

  public ProgramMethodSet extractRoots() {
    return extractNodes(Node::isRoot, Node::cleanCalleesAndWritersForRemoval);
  }

  private ProgramMethodSet extractNodes(Predicate<Node> predicate, Consumer<Node> clean) {
    ProgramMethodSet result = ProgramMethodSet.create();
    Set<Node> removed = Sets.newIdentityHashSet();
    Iterator<Node> nodeIterator = nodes.values().iterator();
    while (nodeIterator.hasNext()) {
      Node node = nodeIterator.next();
      if (predicate.test(node)) {
        result.add(node.getProgramMethod());
        nodeIterator.remove();
        removed.add(node);
      }
    }
    removed.forEach(clean);
    assert !result.isEmpty();
    return result;
  }
}