dev/core/src/com/google/gwt/dev/jjs/impl/CallGraph.java

/*
 * Copyright 2014 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */
package com.google.gwt.dev.jjs.impl;

import com.google.gwt.dev.jjs.ast.Context;
import com.google.gwt.dev.jjs.ast.JMethod;
import com.google.gwt.dev.jjs.ast.JMethodCall;
import com.google.gwt.dev.jjs.ast.JProgram;
import com.google.gwt.dev.jjs.ast.JVisitor;
import com.google.gwt.thirdparty.guava.common.collect.LinkedHashMultimap;
import com.google.gwt.thirdparty.guava.common.collect.Sets;

import java.util.Collection;
import java.util.Set;

/**
 * Call graph, which records {callee->callers} and {caller->callees} pairs.
 */
public class CallGraph {

  /**
   * Visitor used to build call graph.
   */
  private class BuildCallGraphVisitor extends JVisitor {

    // TODO(leafwang): This call graph does not take into account overloads nor calls that happen
    // in JSNI methods.

    private JMethod currentMethod;

    @Override
    public void endVisit(JMethod x, Context ctx) {
      assert (currentMethod == x);
      currentMethod = null;
    }

    @Override
    public void endVisit(JMethodCall x, Context ctx) {
      JMethod calleeMethod = x.getTarget();
      assert (currentMethod != null);
      calleeCallersPairs.put(calleeMethod, currentMethod);
      callerCalleesPairs.put(currentMethod, calleeMethod);
    }

    @Override
    public boolean visit(JMethod x, Context ctx) {
      assert (currentMethod == null);
      currentMethod = x;
      return true;
    }
  }

  private LinkedHashMultimap<JMethod, JMethod> calleeCallersPairs = LinkedHashMultimap.create();
  private LinkedHashMultimap<JMethod, JMethod> callerCalleesPairs = LinkedHashMultimap.create();

  /**
   * Add a caller method and its callee methods to the call graph.
   */
  public void addCallerMethod(JMethod callerMethod, Collection<JMethod> calleeMethods) {
    callerCalleesPairs.putAll(callerMethod, calleeMethods);
    for (JMethod calleeMethod : calleeMethods) {
      calleeCallersPairs.put(calleeMethod, callerMethod);
    }
  }

  /**
   * Build the call graph of a JProgram.
   */
  public void buildCallGraph(JProgram program) {
    resetCallGraph();
    BuildCallGraphVisitor buildCallGraphVisitor = new BuildCallGraphVisitor();
    buildCallGraphVisitor.accept(program);
  }

  /**
   * Return all the callee methods in the call graph.
   */
  public Set<JMethod> getAllCallees() {
    return calleeCallersPairs.keySet();
  }

  /**
   * Return all the callees of a set of caller methods.
   */
  public Set<JMethod> getCallees(Collection<JMethod> callerMethods) {
    assert (callerMethods != null);
    Set<JMethod> calleeMethods = Sets.newLinkedHashSet();
    for (JMethod callerMethod : callerMethods) {
      calleeMethods.addAll(callerCalleesPairs.get(callerMethod));
    }
    return calleeMethods;
  }

  /**
   * Return all the callers of a set of callee methods.
   */
  public Set<JMethod> getCallers(Collection<JMethod> calleeMethods) {
    assert (calleeMethods != null);
    Set<JMethod> callerMethods = Sets.newLinkedHashSet();
    for (JMethod calleeMethod : calleeMethods) {
      callerMethods.addAll(calleeCallersPairs.get(calleeMethod));
    }
    return callerMethods;
  }

  /**
   * Remove a callee method and all its caller methods in both
   * {@code calleeCallersPairs} and {@code callerCalleesPairs}.
   * Return its caller methods.
   */
  public Set<JMethod> removeCalleeMethod(JMethod calleeMethod) {
    Set<JMethod> callerMethods = calleeCallersPairs.removeAll(calleeMethod);
    for (JMethod callerMethod : callerMethods) {
      callerCalleesPairs.remove(callerMethod, calleeMethod);
    }
    return callerMethods;
  }

  /**
   * Remove a caller method and all its callee methods in both
   * {@code callerCalleesPairs} and {@code calleeCallersPairs}.
   * Return its callee methods.
   */
  public Set<JMethod> removeCallerMethod(JMethod callerMethod) {
    Set<JMethod> calleeMethods = callerCalleesPairs.removeAll(callerMethod);
    for (JMethod calleeMethod : calleeMethods) {
      calleeCallersPairs.remove(calleeMethod, callerMethod);
    }
    return calleeMethods;
  }

  public void resetCallGraph() {
    calleeCallersPairs.clear();
    callerCalleesPairs.clear();
  }

  /**
   * Update call graph of a JMethod. Record the deleted and added sub graph after the update in
   * {@code deletedSubCallGraph} and {@code addedSubCallGraph} respectively.
   */
  public void updateCallGraphOfMethod(JMethod method, CallGraph deletedSubCallGraph,
      CallGraph addedSubCallGraph) {
    Set<JMethod> calleeMethods = removeCallerMethod(method);
    BuildCallGraphVisitor callSiteVisitor = new BuildCallGraphVisitor();
    callSiteVisitor.accept(method);
    deletedSubCallGraph.addCallerMethod(method,
        Sets.difference(calleeMethods, callerCalleesPairs.get(method)));
    addedSubCallGraph.addCallerMethod(method,
        Sets.difference(callerCalleesPairs.get(method), calleeMethods));
  }
}