/*
 * Copyright 2008 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.js;

import com.google.gwt.dev.common.InliningMode;
import com.google.gwt.dev.jjs.HasSourceInfo;
import com.google.gwt.dev.jjs.InternalCompilerException;
import com.google.gwt.dev.jjs.SourceInfo;
import com.google.gwt.dev.jjs.impl.OptimizerStats;
import com.google.gwt.dev.js.ast.JsArrayAccess;
import com.google.gwt.dev.js.ast.JsArrayLiteral;
import com.google.gwt.dev.js.ast.JsBinaryOperation;
import com.google.gwt.dev.js.ast.JsBinaryOperator;
import com.google.gwt.dev.js.ast.JsBlock;
import com.google.gwt.dev.js.ast.JsBooleanLiteral;
import com.google.gwt.dev.js.ast.JsCatchScope;
import com.google.gwt.dev.js.ast.JsConditional;
import com.google.gwt.dev.js.ast.JsContext;
import com.google.gwt.dev.js.ast.JsEmpty;
import com.google.gwt.dev.js.ast.JsExprStmt;
import com.google.gwt.dev.js.ast.JsExpression;
import com.google.gwt.dev.js.ast.JsFunction;
import com.google.gwt.dev.js.ast.JsInvocation;
import com.google.gwt.dev.js.ast.JsModVisitor;
import com.google.gwt.dev.js.ast.JsName;
import com.google.gwt.dev.js.ast.JsNameRef;
import com.google.gwt.dev.js.ast.JsNew;
import com.google.gwt.dev.js.ast.JsNode;
import com.google.gwt.dev.js.ast.JsNullLiteral;
import com.google.gwt.dev.js.ast.JsNumberLiteral;
import com.google.gwt.dev.js.ast.JsObjectLiteral;
import com.google.gwt.dev.js.ast.JsParameter;
import com.google.gwt.dev.js.ast.JsPostfixOperation;
import com.google.gwt.dev.js.ast.JsPrefixOperation;
import com.google.gwt.dev.js.ast.JsProgram;
import com.google.gwt.dev.js.ast.JsPropertyInitializer;
import com.google.gwt.dev.js.ast.JsRegExp;
import com.google.gwt.dev.js.ast.JsReturn;
import com.google.gwt.dev.js.ast.JsRootScope;
import com.google.gwt.dev.js.ast.JsScope;
import com.google.gwt.dev.js.ast.JsStatement;
import com.google.gwt.dev.js.ast.JsStringLiteral;
import com.google.gwt.dev.js.ast.JsThisRef;
import com.google.gwt.dev.js.ast.JsVars;
import com.google.gwt.dev.js.ast.JsVars.JsVar;
import com.google.gwt.dev.js.ast.JsVisitor;
import com.google.gwt.dev.util.collect.Stack;
import com.google.gwt.dev.util.log.speedtracer.CompilerEventType;
import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger;
import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event;
import com.google.gwt.thirdparty.guava.common.collect.HashMultiset;
import com.google.gwt.thirdparty.guava.common.collect.Lists;
import com.google.gwt.thirdparty.guava.common.collect.Maps;
import com.google.gwt.thirdparty.guava.common.collect.Multiset;
import com.google.gwt.thirdparty.guava.common.collect.Sets;

import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

/**
 * Perform inlining optimizations on the JavaScript AST.
 *
 * TODO(bobv): remove anything that's duplicating work with {@link JsStaticEval}
 * migrate other stuff to that class perhaps.
 */
public class JsInliner {
  private static final String NAME = JsInliner.class.getSimpleName();

  /**
   * Determines if the evaluation of a JsNode may be affected by side effects.
   */
  private static class AffectedBySideEffectsVisitor extends JsVisitor {
    private boolean affectedBySideEffects;
    private final JsScope safeScope;

    public AffectedBySideEffectsVisitor(JsScope safeScope) {
      this.safeScope = safeScope;
    }

    public boolean affectedBySideEffects() {
      return affectedBySideEffects;
    }

    @Override
    public void endVisit(JsArrayLiteral x, JsContext ctx) {
      affectedBySideEffects = true;
    }

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      affectedBySideEffects = true;
    }

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      /*
       * We could make this more accurate by analyzing the function that's being
       * executed, but we'll bank on subsequent passes inlining simple function
       * invocations.
       */
      affectedBySideEffects = true;
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      if (x.getQualifier() == null && x.getName() != null) {
        // Special case the undefined literal.
        if (x.getName() == JsRootScope.INSTANCE.getUndefined()) {
          return;
        }
        // Locals in a safe scope are unaffected.
        if (x.getName().getEnclosing() == safeScope) {
          return;
        }
      }

      /*
       * We can make this more accurate if we had single-assignment information
       * (e.g. static final fields).
       */
      affectedBySideEffects = true;
    }

    @Override
    public void endVisit(JsObjectLiteral x, JsContext ctx) {
      affectedBySideEffects = true;
    }
  }

  /**
   * Make comma binary operations left-nested since commas are naturally
   * left-associative. We will define the comma-normal form such that a comma
   * expression should never have a comma expression as its RHS and contains no
   * side-effect-free expressions save for the outer, right-hand expression.
   * This form has a nice side-effect of minimizing the number of generated
   * parentheses.
   *
   * <pre>
   * (X, b) is unchanged
   * (X, (b, c) becomes ((X, b), c); b is guaranteed to have a side-effect
   * (X, ((b, c), d)) becomes (((X, b), c), d)
   * </pre>
   */
  private static class CommaNormalizer extends JsModVisitor {

    /**
     * Returns an expression as a JsBinaryOperation if it is a comma expression.
     */
    private static JsBinaryOperation isComma(JsExpression x) {
      if (!(x instanceof JsBinaryOperation)) {
        return null;
      }
      JsBinaryOperation op = (JsBinaryOperation) x;

      return op.getOperator().equals(JsBinaryOperator.COMMA) ? op : null;
    }

    private final List<JsName> localVariableNames;

    public CommaNormalizer(List<JsName> localVariableNames) {
      this.localVariableNames = localVariableNames;
    }

    @Override
    public void endVisit(JsBinaryOperation x, JsContext ctx) {
      if (isComma(x) == null) {
        return;
      }

      // If (X, a) and X has no side effects, replace with a
      if (!x.getArg1().hasSideEffects()) {
        ctx.replaceMe(x.getArg2());
        return;
      }

      JsBinaryOperation toUpdate = isComma(x.getArg2());
      if (toUpdate == null) {
        /*
         * We have a JsBinaryOperation that's structurally normal: (X, a). Now
         * it may be the case that the inner expression X is a comma expression
         * (Y, b). If b creates no side-effects, we can remove it, leaving (Y,
         * a) as the expression.
         */
        JsBinaryOperation inner = isComma(x.getArg1());
        if (inner != null && !inner.getArg2().hasSideEffects()) {
          x.setArg1(inner.getArg1());
          didChange = true;
        }

        /*
         * Eliminate the pattern (localVar = expr, localVar). This tends to
         * occur when a method interacted with pruned fields or had statements
         * removed.
         */
        JsName assignmentRef = null;
        JsExpression expr = null;
        JsName returnRef = null;

        if (x.getArg1() instanceof JsBinaryOperation) {
          JsBinaryOperation op = (JsBinaryOperation) x.getArg1();
          if (op.getOperator() == JsBinaryOperator.ASG
              && op.getArg1() instanceof JsNameRef) {
            JsNameRef nameRef = (JsNameRef) op.getArg1();
            if (nameRef.getQualifier() == null) {
              assignmentRef = nameRef.getName();
              expr = op.getArg2();
            }
          }
        }

        if (x.getArg2() instanceof JsNameRef) {
          JsNameRef nameRef = (JsNameRef) x.getArg2();
          if (nameRef.getQualifier() == null) {
            returnRef = nameRef.getName();
          }
        }

        if (assignmentRef != null && assignmentRef.equals(returnRef)
            && localVariableNames.contains(assignmentRef)) {
          assert expr != null;
          localVariableNames.remove(assignmentRef);
          ctx.replaceMe(expr);
        }
        return;
      }

      // Find the left-most, nested comma expression
      while (isComma(toUpdate.getArg1()) != null) {
        toUpdate = (JsBinaryOperation) toUpdate.getArg1();
      }

      /*
       * Create a new comma expression with the original LHS and the LHS of the
       * nested comma expression.
       */
      JsBinaryOperation newOp = new JsBinaryOperation(x.getSourceInfo(),
          JsBinaryOperator.COMMA);
      newOp.setArg1(x.getArg1());
      newOp.setArg2(toUpdate.getArg1());

      // Set the LHS of the nested comma expression to the new comma expression
      toUpdate.setArg1(newOp);

      // Replace the original node with its updated RHS
      ctx.replaceMe(x.getArg2());
    }
  }

  /**
   * Provides a relative metric by which the syntactic complexity of a
   * JsExpression can be gauged.
   */
  private static class ComplexityEstimator extends JsVisitor {
    public static final int AVERAGE_OBFUSCATED_IDENTIFIER_LENGTH = 2;
    /**
     * The current measure of complexity. This measures the number of
     * expressions that have been encountered by the visitor.
     */
    private int complexity = 0;

    @Override
    public void endVisit(JsArrayAccess x, JsContext ctx) {
      complexity += "[]".length();
    }

    @Override
    public void endVisit(JsArrayLiteral x, JsContext ctx) {
      complexity += x.getExpressions().size() * ",".length() + "[]".length();
    }

    @Override
    public void endVisit(JsBinaryOperation x, JsContext ctx) {
      complexity += x.getOperator().getSymbol().length();
    }

    @Override
    public void endVisit(JsBooleanLiteral x, JsContext ctx) {
      complexity++;
    }

    @Override
    public void endVisit(JsConditional x, JsContext ctx) {
      complexity += "?:".length();
    }

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      complexity += "function ".length() + x.getParameters().size() * ",".length()
          + "(){}".length();
    }

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      complexity += x.getArguments().size() * ",".length() + "()".length();
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      // Average name length in obfuscated mode.
      complexity += 2;
    }

    @Override
    public void endVisit(JsNew x, JsContext ctx) {
      complexity += "new ".length() + x.getArguments().size() * ",".length() + "()".length();
    }

    @Override
    public void endVisit(JsNullLiteral x, JsContext ctx) {
      complexity += "null".length();
    }

    @Override
    public void endVisit(JsNumberLiteral x, JsContext ctx) {
      // Duplicate constants will be interned so they are counted as an obfuscated identifier.
      complexity += AVERAGE_OBFUSCATED_IDENTIFIER_LENGTH;
    }

    @Override
    public void endVisit(JsObjectLiteral x, JsContext ctx) {
      complexity += x.getPropertyInitializers().size() * ",:".length() + "{}".length();
    }

    @Override
    public void endVisit(JsPostfixOperation x, JsContext ctx) {
      complexity += x.getOperator().getSymbol().length();
    }

    @Override
    public void endVisit(JsPrefixOperation x, JsContext ctx) {
      complexity += x.getOperator().getSymbol().length();
    }

    @Override
    public void endVisit(JsRegExp x, JsContext ctx) {
      complexity += x.getPattern().length();
    }

    @Override
    public void endVisit(JsStringLiteral x, JsContext ctx) {
      // Duplicate constants will be interned so they are counted as an obfuscated identifier.
      complexity += AVERAGE_OBFUSCATED_IDENTIFIER_LENGTH;
    }

    @Override
    public void endVisit(JsThisRef x, JsContext ctx) {
      complexity += "this".length();
    }

    public int getComplexity() {
      return complexity;
    }
  }

  /**
   * Determines that a list of names is guaranteed to be evaluated in a
   * particular order. Also ensures that all names are evaluated before any
   * invocations occur.
   */
  private static class EvaluationOrderVisitor extends JsVisitor {
    /**
     * A dummy name to represent 'this' refs.
     */
    public static final JsName THIS_NAME = new JsCatchScope(
        JsRootScope.INSTANCE, "this").getAllNames().iterator().next();

    private boolean maintainsOrder = true;
    private final List<JsName> toEvaluate;
    private final List<JsName> unevaluated;
    private final Set<JsName> paramsOrLocals = Sets.newHashSet();

    public EvaluationOrderVisitor(List<JsName> toEvaluate, JsFunction callee) {
      this.toEvaluate = toEvaluate;
      this.unevaluated = Lists.newArrayList(toEvaluate);
      // collect params and locals from callee function
      new JsVisitor() {
        @Override
        public void endVisit(JsParameter x, JsContext ctx) {
          paramsOrLocals.add(x.getName());
        }

        @Override
        public boolean visit(JsVar x, JsContext ctx) {
          // record this before visiting initializer
          paramsOrLocals.add(x.getName());
          return true;
        }
      }.accept(callee);
    }

    @Override
    public void endVisit(JsBinaryOperation x, JsContext ctx) {
      JsBinaryOperator op = x.getOperator();

      /*
       * We don't care about the left-hand expression, because it is guaranteed
       * to be evaluated.
       */
      boolean rightStrict = refersToRequiredName(x.getArg2());
      boolean conditionalEvaluation = JsBinaryOperator.AND.equals(op)
          || JsBinaryOperator.OR.equals(op);

      if (rightStrict && conditionalEvaluation) {
        maintainsOrder = false;
      }
    }

    /**
     * If the condition would cause conditional evaluation of strict parameters,
     * don't allow inlining.
     */
    @Override
    public void endVisit(JsConditional x, JsContext ctx) {
      boolean thenStrict = refersToRequiredName(x.getThenExpression());
      boolean elseStrict = refersToRequiredName(x.getElseExpression());

      if (thenStrict || elseStrict) {
        maintainsOrder = false;
      }
    }

    /**
     * The statement declares a function closure. This makes actual evaluation
     * order of the parameters difficult or impossible to determine, so we'll
     * just ignore them.
     */
    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      maintainsOrder = false;
    }

    /**
     * The innermost invocation we see must consume all presently unevaluated
     * parameters to ensure that an exception does not prevent their evaluation.
     *
     * In the case of a nested invocation, such as
     * <code>F(r1, r2, G(r3, r4), f1);</code> the evaluation order is guaranteed
     * to be maintained, provided that no required parameters occur after the
     * nested invocation.
     */
    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      if (unevaluated.size() > 0) {
        maintainsOrder = false;
      }
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      checkName(x.getName());
    }

    @Override
    public void endVisit(JsNew x, JsContext ctx) {
      /*
       * Unless all arguments have already been evaluated, assume that invoking
       * the new expression might interfere with the evaluation of the argument.
       *
       * It would be possible to allow this if the invoked function either does
       * nothing or does nothing that affects the remaining arguments. However,
       * currently there is no analysis of the invoked function.
       */
      if (unevaluated.size() > 0) {
        maintainsOrder = false;
      }
    }

    @Override
    public void endVisit(JsThisRef x, JsContext ctx) {
      checkName(THIS_NAME);
    }

    public boolean maintainsOrder() {
      return maintainsOrder && unevaluated.size() == 0;
    }

    /**
     * Check to see if the evaluation of this JsName will break program order assumptions given
     * the parameters left to be substituted.
     *
     * The cases are as follows:
     * 1) JsName is a function parameter name which has side effects or is affected by side effects
     * (hereafter called 'volatile'), so it will be in 'toEvaluate'
     * 2) JsName is a function parameter which is not volatile (not in toEvaluate)
     * 3) JsName is a reference to a global variable
     * 4) JsName is a reference to a local variable
     *
     * A reference to a global while there are still parameters left to evaluate / substitute
     * implies an order violation.
     *
     * A reference to a volatile parameter is ok if it is the next parameter in sequence to
     * be evaluated (beginning of unevaluated list). Else, it is either being evaluated out of
     * order with respect to other parameters, or it is being evaluated more than once.
     */
    private void checkName(JsName name) {
      if (!toEvaluate.contains(name)) {
        // if the name is a non-local/non-parameter (e.g. global) and there are params left to eval
        if (!paramsOrLocals.contains(name) && unevaluated.size() > 0) {
          maintainsOrder = false;
        }
        // else this may be a local, or all volatile params have already been evaluated, so it's ok.
        return;
      }

      // either this param is being evaled twice, or out of order
      if (unevaluated.size() == 0 || !unevaluated.remove(0).equals(name)) {
        maintainsOrder = false;
      }
    }

    /**
     * Determine if an expression contains a reference to a strict parameter.
     */
    private boolean refersToRequiredName(JsExpression e) {
      RefersToNameVisitor v = new RefersToNameVisitor(toEvaluate);
      v.accept(e);
      return v.refersToName();
    }
  }

  /**
   * Collect names in a inlineable expression that are local to the original
   * scope.  These names will need to be copied to the destination scope
   * once the expression is inlined.
   */
  private static class ExtrudedNamesCollector extends JsVisitor {
    private final JsScope toScope;
    private final JsScope fromScope;
    private final List<JsName> hoistedNames;

    public ExtrudedNamesCollector(JsScope toScope, JsScope fromScope) {
      this.toScope = toScope;
      this.fromScope = fromScope;
      this.hoistedNames = Lists.newArrayList();
    }

    public List<JsName> getExtrudedNames() {
      return hoistedNames;
    }

    /*
     * We need to hoist names that are only visible in fromScope, but not in
     * toScope (i.e. we don't want to hoist names that are visible to both
     * scopes, such as a global). Also, we don't want to hoist names that have a
     * staticRef, which indicates a formal parameter, or a function name.
     */
    @Override
    public boolean visit(JsNameRef nameRef, JsContext ctx) {
      JsName name = nameRef.getName();
      JsName fromScopeName = fromScope.findExistingName(name.getIdent());
      JsName toScopeName = toScope.findExistingName(name.getIdent());
      if (name.getStaticRef() == null
          && name == fromScopeName
          && name != toScopeName
          && !hoistedNames.contains(name)) {
        hoistedNames.add(name);
      }
      return true;
    }
  }

  /**
   * Collect all of the idents used in an AST node. The collector can be
   * configured to collect idents from qualified xor unqualified JsNameRefs.
   */
  private static class IdentCollector extends JsVisitor {
    private final boolean collectQualified;
    private final Set<String> idents = Sets.newHashSet();

    public IdentCollector(boolean collectQualified) {
      this.collectQualified = collectQualified;
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      boolean hasQualifier = x.getQualifier() != null;

      if ((collectQualified && !hasQualifier)
          || (!collectQualified && hasQualifier)) {
        return;
      }

      assert x.getIdent() != null;
      idents.add(x.getIdent());
    }

    public Set<String> getIdents() {
      return idents;
    }
  }

  /**
   * This class looks for function invocations that can be inlined and performs
   * the replacement by replacing the JsInvocation with a comma expression
   * consisting of the expressions evaluated by the target function. A second
   * step may convert the expressions in the comma expression back to multiple
   * statements if the context of the invocation would allow this.
   */
  private static class InliningVisitor extends JsModVisitor {
    private final Set<JsFunction> blacklist = Sets.newHashSet();
    private final Set<JsNode> whitelist;
    /**
     * This reflects the functions that are currently being inlined to prevent
     * infinite expansion.
     */
    private final Stack<JsFunction> inlining = new Stack<JsFunction>();
    /**
     * This reflects which function the visitor is currently visiting.
     */
    private final Stack<JsFunction> functionStack = new Stack<JsFunction>();
    private final InvocationCountingVisitor invocationCountingVisitor =
        new InvocationCountingVisitor();
    private final Stack<List<JsName>> newLocalVariableStack = Stack.create();

    /**
     * A map containing the next integer to try as an identifier suffix for a
     * given name in a given JsScope.
     */
    private Map<JsScope, Multiset<String>> nextSuffixForIdentifierByScope =
        Maps.newIdentityHashMap();

    /**
     * Not a stack because program fragments aren't nested.
     */
    private JsFunction programFunction;

    public InliningVisitor(JsProgram program, Set<JsNode> whitelist) {
      this.whitelist = whitelist;
      invocationCountingVisitor.accept(program);
    }

    /**
     * Add to the list of JsFunctions that should not be inlined, regardless of
     * whether or not they would normally be inlinable.
     */
    public void blacklist(Collection<JsFunction> functions) {
      blacklist.addAll(functions);
    }

    /**
     * This normalizes the comma expressions into multiple statements and
     * removes statements with no side-effects.
     */
    @Override
    public void endVisit(JsExprStmt x, JsContext ctx) {
      JsExpression e = x.getExpression();

      // We will occasionally create JsExprStmts that have no side-effects.
      if (ctx.canRemove() && !x.getExpression().hasSideEffects()) {
        ctx.removeMe();
        return;
      }

      List<JsExprStmt> statements = Lists.newArrayList();

      /*
       * Assemble the expressions back into a list of JsExprStmts. We will
       * iteratively disassemble the nested comma expressions, stopping when the
       * LHS is not a comma expression.
       */
      while (e instanceof JsBinaryOperation) {
        JsBinaryOperation op = (JsBinaryOperation) e;

        if (!op.getOperator().equals(JsBinaryOperator.COMMA)) {
          break;
        }

        /*
         * We can ignore intermediate expressions as long as they have no
         * side-effects.
         */
        if (op.getArg2().hasSideEffects()) {
          statements.add(0, op.getArg2().makeStmt());
        }

        e = op.getArg1();
      }

      /*
       * We know the return value from the original invocation was ignored, so
       * it may be possible to ignore the final expressions as long as it has no
       * side-effects.
       */
      if (e.hasSideEffects()) {
        statements.add(0, e.makeStmt());
      }

      if (statements.size() == 0) {
        // The expression contained no side effects at all.
        if (ctx.canRemove()) {
          ctx.removeMe();
        } else {
          ctx.replaceMe(new JsEmpty(x.getSourceInfo()));
        }
      } else if (x.getExpression() != statements.get(0).getExpression()) {
        // Something has changed

        if (!ctx.canInsert()) {
          /*
           * This indicates that the function was attached to a clause of a
           * control function and not into an existing block. We'll replace the
           * single JsExprStmt with a JsBlock that contains all of the
           * statements.
           */
          JsBlock b = new JsBlock(x.getSourceInfo());
          b.getStatements().addAll(statements);
          ctx.replaceMe(b);
          return;
        } else {
          // Insert the new statements into the original context
          for (JsStatement s : statements) {
            ctx.insertBefore(s);
          }
          ctx.removeMe();
        }
      }
    }

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      if (!functionStack.pop().equals(x)) {
        throw new InternalCompilerException("Unexpected function popped");
      }

      JsBlock body = x.getBody();
      List<JsName> newLocalVariables = newLocalVariableStack.pop();

      addVars(x, body, newLocalVariables);
    }

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      JsFunction callerFunction = functionStack.peek();

      /*
       * We only want to look at invocations of things that we statically know
       * to be functions. Otherwise, we can't know what statements the
       * invocation would actually invoke. The static reference would be null
       * when trying operate on references to external functions, or functions
       * as arguments to another function.
       */
      JsFunction invokedFunction = JsUtils.isFunction(x.getQualifier());
      if (invokedFunction == null) {
        return;
      }

      if (!invokedFunction.isInliningAllowed() || blacklist.contains(invokedFunction)) {
        return;
      }

      /*
       * Don't inline huge functions into huge multi-expressions. Some JS
       * engines will blow up.
       */
      if (invokedFunction.getBody().getStatements().size() > MAX_INLINE_FN_SIZE) {
        return;
      }

      /*
       * The current function has been mutated so as to be self-recursive. Ban
       * it from any future inlining to prevent infinite expansion.
       */
      if (invokedFunction == callerFunction) {
        blacklist.add(invokedFunction);
        return;
      }

      /*
       * We are already in the middle of attempting to inline a call to this
       * function. This check prevents infinite expansion across
       * mutually-recursive, inlinable functions. Any invocation skipped by this
       * logic will be re-visited in the <code>op = accept(op)</code> call in
       * the outermost JsInvocation.
       */
      if (inlining.contains(invokedFunction)) {
        return;
      }

      inlining.push(invokedFunction);
      x = tryToUnravelExplicitCall(x);
      JsExpression op = process(x, callerFunction, invokedFunction);

      if (x != op) {
        /*
         * See if any further inlining can be performed in the current context.
         * By attempting to maximize the level of inlining now, we can reduce
         * the total number of passes required to finalize the AST.
         */
        op = accept(op);
        ctx.replaceMe(op);
      }

      if (inlining.pop() != invokedFunction) {
        throw new RuntimeException("Unexpected function popped");
      }
    }

    @Override
    public void endVisit(JsProgram x, JsContext ctx) {
      if (!functionStack.pop().equals(programFunction)) {
        throw new InternalCompilerException("Unexpected function popped");
      }

      assert programFunction.getBody().getStatements().size() == 0 :
          "Should not have moved statements into program";

      List<JsName> newLocalVariables = newLocalVariableStack.pop();
      assert newLocalVariables.size() == 0 : "Should not have tried to create variables in program";
    }

    @Override
    public boolean visit(JsFunction x, JsContext ctx) {
      functionStack.push(x);
      newLocalVariableStack.push(Lists.<JsName>newArrayList());
      return whitelist.contains(x);
    }

    /**
     * Create a synthetic context to attempt to simplify statements in the
     * top-level of the program.
     */
    @Override
    public boolean visit(JsProgram x, JsContext ctx) {
      programFunction = new JsFunction(x.getSourceInfo(), x.getScope());
      programFunction.setBody(new JsBlock(x.getSourceInfo()));
      functionStack.push(programFunction);
      newLocalVariableStack.push(Lists.<JsName>newArrayList());
      return true;
    }

    private void addVars(HasSourceInfo x, JsBlock body,
        List<JsName> newLocalVariables) {
      // Nothing to do
      if (newLocalVariables.isEmpty()) {
        return;
      }

      List<JsStatement> statements = body.getStatements();

      // The body can't be empty if we have local variables to create
      assert !statements.isEmpty();

      // Find or create the JsVars as the first statement
      SourceInfo sourceInfo = x.getSourceInfo();
      JsVars vars;
      if (statements.get(0) instanceof JsVars) {
        vars = (JsVars) statements.get(0);
      } else {
        vars = new JsVars(sourceInfo);
        statements.add(0, vars);
      }

      // Add all variables
      for (JsName name : newLocalVariables) {
        vars.add(new JsVar(sourceInfo, name));
      }
    }

    private boolean isInvokedMoreThanOnce(JsFunction f) {
      return invocationCountingVisitor.invocationCount(f) > 1;
    }

    /**
     * Determine if <code>invokedFunction</code> can be inlined into
     * <code>callerFunction</code> at callsite <code>x</code>.
     *
     * @return An expression equivalent to <code>x</code>
     */
    private JsExpression process(JsInvocation x, JsFunction callerFunction,
        JsFunction invokedFunction) {
      List<JsStatement> statements;
      if (invokedFunction.getBody() != null) {
        statements = Lists.newArrayList(invokedFunction.getBody().getStatements());
      } else {
        /*
         * Will see this with certain classes whose clinits are folded into the
         * main JsProgram body.
         */
        statements = Collections.emptyList();
      }

      List<JsExpression> inlinableBodyAsExpression =
          Lists.newArrayListWithCapacity(statements.size());
      JsExpression thisExpr = ((JsNameRef) x.getQualifier()).getQualifier();
      ExtrudedNamesCollector extrudedNamesCollector =
          new ExtrudedNamesCollector(callerFunction.getScope(), invokedFunction.getScope());

      boolean sawReturnStatement = false;

      for (JsStatement statement : statements) {
        if (sawReturnStatement) {
          /*
           * We've already seen a return statement, but there are still more
           * statements. The target is unsafe to inline, so bail. Note: in most
           * cases JsStaticEval will have removed any statements following a
           * return statement.
           *
           * The reason we have to bail is that the return statement's
           * expression MUST be the last thing evaluated.
           *
           * TODO(bobv): maybe it could still be inlined with smart
           * transformation?
           */
          return x;
        }

        /*
         * Create replacement expressions to use in place of the original
         * statements. It is important that the replacement is newly-minted and
         * therefore not referenced by any other AST nodes. Consider the case of
         * a common, delegating function. If the inlinableBodyAsExpression expressions were not
         * distinct objects, it would not be possible to substitute different
         * JsNameRefs at different call sites.
         */
        JsExpression statementAsExpression = convertToExpression(statement);
        if (statementAsExpression == null) {
          return x;
        }

        sawReturnStatement |= isReturnStatement(statement);
        if (sawReturnStatement || statementAsExpression.hasSideEffects()) {
          /*
           * Visit the statement to find names that will be moved to the caller's
           * scope from the invoked function.
           */
          extrudedNamesCollector.accept(statementAsExpression);
          inlinableBodyAsExpression.add(statementAsExpression);
        }
      }

      /*
       * Get the referenced names that need to be copied to the caller's scope.
       */
      List<JsName> extrudedNames = extrudedNamesCollector.getExtrudedNames();

      if (extrudedNames.size() != 0 && callerFunction == programFunction) {
        // Don't extrude variables into the global scope.
        return x;
      }

      /*
       * If the inlined method has no return statement, synthesize an undefined
       * reference. It will be reclaimed if the method call is from a
       * JsExprStmt.
       */
      if (!sawReturnStatement) {
        inlinableBodyAsExpression.add(new JsNameRef(x.getSourceInfo(),
            JsRootScope.INSTANCE.getUndefined()));
      }

      assert (inlinableBodyAsExpression.size() > 0);

      /*
       * Build up the new comma expression from right-to-left; building the
       * rightmost comma expressions first. Bootstrapping with i.previous()
       * ensures that this logic will function correctly in the case of a single
       * expression.
       */
      SourceInfo sourceInfo = x.getSourceInfo();
      ListIterator<JsExpression> i =
          inlinableBodyAsExpression.listIterator(inlinableBodyAsExpression.size());
      JsExpression op = i.previous();
      while (i.hasPrevious()) {
        JsBinaryOperation outerOp = new JsBinaryOperation(sourceInfo, JsBinaryOperator.COMMA);
        outerOp.setArg1(i.previous());
        outerOp.setArg2(op);
        op = outerOp;
      }

      // Confirm that the expression conforms to the desired heuristics
      if (!isInlinable(callerFunction, invokedFunction, thisExpr, x.getArguments(), op)) {
        return x;
      }

      // Perform the name replacement
      NameRefReplacerVisitor nameRefReplacer = new NameRefReplacerVisitor(thisExpr,
          x.getArguments(), invokedFunction.getParameters());
      for (ListIterator<JsName> nameIterator = extrudedNames.listIterator();
          nameIterator.hasNext();) {

        JsName name = nameIterator.next();

        JsName newName = getUnusedName(
            callerFunction.getScope(),
            invokedFunction.getName() + "_" + name.getIdent(),
            name.getShortIdent());
        nameRefReplacer.setReplacementName(name, newName);
        nameIterator.set(newName);
      }
      op = nameRefReplacer.accept(op);

      // Normalize any nested comma expressions that we may have generated.
      op = (new CommaNormalizer(extrudedNames)).accept(op);

      if (callerFunction == programFunction && extrudedNames.size() > 0) {
        // Don't add additional variables to the top-level program.
        return x;
      }

      /*
       * Compare the relative complexity of the original invocation versus the
       * inlined form.
       */
      if (invokedFunction.getInliningMode() != InliningMode.FORCE_INLINE
          && isTooComplexToInline(x, op)
          && isInvokedMoreThanOnce(invokedFunction)) {
        return x;
      }

      // We've committed to the inlining, ensure the vars are created
      newLocalVariableStack.peek().addAll(extrudedNames);

      // update invocation counts according to this inlining
      invocationCountingVisitor.removeCountsFor(x);
      invocationCountingVisitor.accept(op);
      return op;
    }

    private JsName getUnusedName(JsScope scope, String baseName, String shortIdentifier) {
      /*
       * Find an unused identifier in the caller's scope. It's possible that
       * the same function has been inlined in multiple places within the
       * function so we'll use a counter for disambiguation.
       */
      String identifier;
      Multiset<String> nextSuffixForIdentifier = nextSuffixForIdentifierByScope.get(scope);
      if (nextSuffixForIdentifier == null) {
        nextSuffixForIdentifier = HashMultiset.create();
        nextSuffixForIdentifierByScope.put(scope, nextSuffixForIdentifier);
      }

      int suffix = nextSuffixForIdentifier.count(baseName);
      do {
        identifier = baseName + "_" + suffix++;
      } while (scope.findExistingName(identifier) != null);
      nextSuffixForIdentifier.setCount(baseName, suffix);

      return scope.declareName(identifier, shortIdentifier);
    }

    private boolean isTooComplexToInline(JsInvocation x, JsExpression op) {
      int originalComplexity = complexity(x);
      int inlinedComplexity = complexity(op);
      return ((double) inlinedComplexity) / (originalComplexity + INLINING_BIAS)
          > MAX_COMPLEXITY_INCREASE;
    }
  }

  /**
   * Counts the number of times a function is invoked. Functions that only have
   * a single call site in the whole program are inlined, regardless of
   * complexity.
   */
  private static class InvocationCountingVisitor extends JsVisitor {
    private boolean removingCounts = false;
    private final Multiset<JsFunction> invocationCount = HashMultiset.create();

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      checkFunctionCall(x.getQualifier());
    }

    @Override
    public void endVisit(JsNew x, JsContext ctx) {
      checkFunctionCall(x.getConstructorExpression());
    }

    public int invocationCount(JsFunction f) {
      return invocationCount.count(f);
    }

    /**
     * Like accept(), but remove counts for all invocations in expr.
     */
    public void removeCountsFor(JsExpression expr) {
      assert (!removingCounts);
      removingCounts = true;
      accept(expr);
      removingCounts = false;
    }

    private void checkFunctionCall(JsExpression qualifier) {
      JsFunction function = JsUtils.isFunction(qualifier);
      if (function == null) {
        return;
      }
      if (removingCounts) {
        invocationCount.remove(function);
      } else {
        invocationCount.add(function);
      }
    }
  }

  /**
   * Finds functions that are only invoked at a single invocation site.
   */
  private static class SingleInvocationVisitor extends JsVisitor {
    // Keep track of functions that are invoked once.
    // Invariant: singleInvokations(fn) = null => calls to fn have not been seen
    //            singleInvokations(fn) = MULTIPLE =>  multiple callsites to fn have been seen.
    //            singleInvokations(fn) = caller =>  one callsite has been seen an occurs in caller.
    private final Map<JsFunction, JsFunction> singleInvocations = Maps.newLinkedHashMap();

    // Indicates multiple invocations were found (only identity is used).
    private static final JsFunction MULTIPLE = JsFunction.createSentinel();

    private final Stack<JsFunction> functionStack = new Stack<JsFunction>();

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      if (!functionStack.pop().equals(x)) {
        throw new InternalCompilerException("Unexpected function popped");
      }
    }

    public Collection<JsNode> inliningCandidates() {
      Collection<JsNode> set = Sets.newLinkedHashSet();
      for (Map.Entry<JsFunction, JsFunction> entry : singleInvocations.entrySet()) {
        if (entry.getValue() != MULTIPLE) {
          set.add(entry.getValue());
        }
      }
      return set;
    }

    @Override
    public boolean visit(JsFunction x, JsContext ctx) {
      functionStack.push(x);
      return true;
    }

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      checkFunctionCall(x.getQualifier());
    }

    @Override
    public void endVisit(JsNew x, JsContext ctx) {
      checkFunctionCall(x.getConstructorExpression());
    }

    private void checkFunctionCall(JsExpression qualifier) {
      JsFunction function = JsUtils.isFunction(qualifier);
      if (function != null && !functionStack.isEmpty()) {
        // Keep track if function is only invoked at a single callsite.
        JsFunction recordedInvoker = singleInvocations.get(function);
        // Mark self recursive functions as if they had multiple call sites.
        if (recordedInvoker == null && functionStack.peek() != function) {
          // This is the first invocation, register it.
          singleInvocations.put(function, functionStack.peek());
        } else if (recordedInvoker != MULTIPLE) {
          singleInvocations.put(function, MULTIPLE);
        }
      }
    }
  }

  /**
   * Replace references to JsNames with the inlined JsExpression.
   */
  private static class NameRefReplacerVisitor extends JsModVisitor {
    /**
     * Set up a map to record name replacements to perform.
     */
    final Map<JsName, JsName> nameReplacements = Maps.newIdentityHashMap();

    /**
     * Set up a map of parameter names back to the expressions that will be
     * passed in from the outer call site.
     */
    final Map<JsName, JsExpression> paramsToArgsMap = Maps.newIdentityHashMap();

    /**
     * A replacement expression for this references.
     */
    private JsExpression thisExpr;

    public NameRefReplacerVisitor(JsExpression thisExpr,
        List<JsExpression> arguments, List<JsParameter> parameters) {
      this.thisExpr = thisExpr;
      if (parameters.size() != arguments.size()) {
        // This shouldn't happen if the cloned JsInvocation has been properly
        // configured
        throw new InternalCompilerException(
            "Mismatch on parameters and arguments");
      }

      for (int i = 0; i < parameters.size(); i++) {
        JsParameter p = parameters.get(i);
        JsExpression e = arguments.get(i);
        paramsToArgsMap.put(p.getName(), e);
      }
    }

    /**
     * Replace JsNameRefs that refer to parameters with the expression passed
     * into the function invocation.
     */
    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      if (x.getQualifier() != null) {
        return;
      }

      JsExpression replacement = tryGetReplacementExpression(x.getSourceInfo(),
          x.getName());

      if (replacement != null) {
        ctx.replaceMe(replacement);
      }
    }

    @Override
    public void endVisit(JsThisRef x, JsContext ctx) {
      assert thisExpr != null;
      ctx.replaceMe(thisExpr);
    }

    /**
     * Set a replacement JsName for all references to a JsName.
     *
     * @param name the name to replace
     * @param newName the new name that should be used in place of references to
     *          <code>name</code>
     * @return the previous JsName the name would have been replaced with or
     *         <code>null</code> if one was not previously set
     */
    public JsName setReplacementName(JsName name, JsName newName) {
      return nameReplacements.put(name, newName);
    }

    /**
     * Determine the replacement expression to use in place of a reference to a
     * given name. Returns <code>null</code> if no replacement has been set for
     * the name.
     */
    private JsExpression tryGetReplacementExpression(SourceInfo sourceInfo,
        JsName name) {
      if (paramsToArgsMap.containsKey(name)) {
        /*
         * TODO if we ever allow mutable JsExpression types to be considered
         * always flexible, then it would be necessary to clone the expression.
         */
        return paramsToArgsMap.get(name);
      } else if (nameReplacements.containsKey(name)) {
        return nameReplacements.get(name).makeRef(sourceInfo);
      } else {
        return null;
      }
    }
  }

  /**
   * Detects function declarations.
   */
  private static class NestedFunctionVisitor extends JsVisitor {

    private boolean containsNestedFunctions = false;

    public boolean containsNestedFunctions() {
      return containsNestedFunctions;
    }

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      containsNestedFunctions = true;
    }
  }

  /**
   * Detects uses of parameters that would produce incorrect results if inlined.
   * Generally speaking, we disallow the use of parameters as lvalues. Also
   * detects trying to inline a method which references 'this' where the call
   * site has no qualifier.
   */
  private static class ParameterUsageVisitor extends JsVisitor {
    private final boolean hasThisExpr;
    private final Set<JsName> parameterNames;
    private boolean violation = false;

    public ParameterUsageVisitor(boolean hasThisExpr, Set<JsName> parameterNames) {
      this.hasThisExpr = hasThisExpr;
      this.parameterNames = parameterNames;
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      if (ctx.isLvalue() && isParameter(x)) {
        violation = true;
      }
    }

    @Override
    public void endVisit(JsThisRef x, JsContext ctx) {
      if (!hasThisExpr) {
        violation = true;
      }
    }

    public boolean hasViolation() {
      return violation;
    }

    /**
     * Determine if a JsExpression is a JsNameRef that refers to a parameter.
     */
    private boolean isParameter(JsNameRef ref) {
      if (ref.getQualifier() != null) {
        return false;
      }

      JsName name = ref.getName();
      return parameterNames.contains(name);
    }
  }

  /**
   * Collect self-recursive functions. This visitor does not look for
   * mutually-recursive functions because inlining one of the functions into the
   * other would make the single resultant function self-recursive and not
   * eligible for inlining in a subsequent pass.
   */
  private static class RecursionCollector extends JsVisitor {
    private final Stack<JsFunction> functionStack = Stack.create();
    private final Set<JsFunction> recursive = Sets.newHashSet();

    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      if (!functionStack.pop().equals(x)) {
        throw new InternalCompilerException("Unexpected function popped");
      }
    }

    @Override
    public void endVisit(JsInvocation x, JsContext ctx) {
      /*
       * Because functions can encapsulate other functions, we look at the
       * entire stack and not just the top element. This would prevent inlining
       *
       * function a() { function b() { a(); } b(); }
       *
       * in the case that we generally allow nested functions to be inlinable.
       */
      JsFunction f = JsUtils.isFunction(x.getQualifier());
      if (functionStack.contains(f)) {
        recursive.add(f);
      }
    }

    public Set<JsFunction> getRecursive() {
      return recursive;
    }

    @Override
    public boolean visit(JsFunction x, JsContext ctx) {
      functionStack.push(x);
      return true;
    }
  }

  /**
   * Determine which functions should not be inlined because they are redefined
   * during program execution. This would violate the assumption that the
   * statements to be executed by any given function invocation are stable over
   * the lifetime of the program.
   */
  private static class RedefinedFunctionCollector extends JsVisitor {
    private final Map<JsName, JsFunction> nameMap = Maps.newIdentityHashMap();
    private final Set<JsFunction> redefined = Sets.newHashSet();

    /**
     * Look for assignments to JsNames whose static references are JsFunctions.
     */
    @Override
    public void endVisit(JsBinaryOperation x, JsContext ctx) {

      if (!x.getOperator().equals(JsBinaryOperator.ASG)) {
        return;
      }

      JsFunction f = JsUtils.isFunction(x.getArg1());
      if (f != null) {
        redefined.add(f);
      }
    }

    /**
     * Look for the case where a function is declared with the same name as an
     * existing function.
     */
    @Override
    public void endVisit(JsFunction x, JsContext ctx) {
      JsName name = x.getName();

      if (name == null) {
        // Ignore anonymous functions
        return;
      } else if (nameMap.containsKey(name)) {
        /*
         * We have to add the current function as well as the original
         * JsFunction that was declared to use that name.
         */
        redefined.add(nameMap.get(name));
        redefined.add(x);
      } else {
        nameMap.put(name, x);
      }
    }

    public Collection<JsFunction> getRedefined() {
      return redefined;
    }
  }

  /**
   * Given a collection of JsNames, determine if an AST node refers to any of
   * those names.
   */
  private static class RefersToNameVisitor extends JsVisitor {
    private final Collection<JsName> names;
    private boolean refersToName;

    public RefersToNameVisitor(Collection<JsName> names) {
      this.names = names;
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      JsName name = x.getName();

      if (name != null) {
        refersToName = refersToName || names.contains(name);
      }
    }

    public boolean refersToName() {
      return refersToName;
    }
  }

  /**
   * This ensures that changing the scope of an expression from its enclosing
   * function into the scope of the call site will not cause unqualified
   * identifiers to resolve to different values.
   */
  private static class StableNameChecker extends JsVisitor {
    private final JsScope calleeScope;
    private final JsScope callerScope;
    private final Collection<JsName> parameterNames;
    private boolean stable = true;

    public StableNameChecker(JsScope callerScope, JsScope calleeScope,
        Collection<JsName> parameterNames) {
      this.callerScope = callerScope;
      this.calleeScope = calleeScope;
      this.parameterNames = parameterNames;
    }

    @Override
    public void endVisit(JsNameRef x, JsContext ctx) {
      /*
       * We can ignore qualified reference, since their scope is always that of
       * the qualifier.
       */
      if (x.getQualifier() != null) {
        return;
      }

      /*
       * Attempt to resolve the ident in both scopes
       */
      JsName callerName = callerScope.findExistingName(x.getIdent());
      JsName calleeName = calleeScope.findExistingName(x.getIdent());

      if (callerName == null && calleeName == null) {
        // They both reference out-of-module names

      } else if (parameterNames.contains(calleeName)) {
        // A reference to a parameter, which will be replaced by an argument

      } else if (callerName != null && callerName.equals(calleeName)) {
        // The names are known to us and are the same

      } else if (calleeName != null && calleeName.getEnclosing().equals(calleeScope)) {
        // It's a local variable in the callee

      } else {
        stable = false;
      }
    }

    public boolean isStable() {
      return stable;
    }

    @Override
    public boolean visit(JsObjectLiteral x, JsContext ctx) {
      // Labels are always stable, so only check values.
      for (JsPropertyInitializer propertyInitializer : x.getPropertyInitializers()) {
        accept(propertyInitializer.getValueExpr());
      }
      return false;
    }
  }

  /**
   * The maximum number of statements a function can have to be actually considered for inlining.
   *
   * Setting gwt.jsinlinerMaxFnSize = 50 and gwt.jsinlinerRatio = 1.7 (as was originally)
   * increases compile time by 5% and decreases code size by 0.4%.
   */
  public static final int MAX_INLINE_FN_SIZE = Integer.parseInt(System.getProperty(
      "gwt.jsinlinerMaxFnSize", "23"));

  /**
   * When attempting to inline an invocation, this constant determines the
   * maximum allowable ratio of potential inlined complexity to initial
   * complexity. Increasing this number will allow larger sections of
   * code to be inlined, but at a cost of larger JS output.
   *
   * The default value for this parameter is 1.0 which means that inlining only happens if it is
   * estimated that it does not increase codesize.
   */
  private static final double MAX_COMPLEXITY_INCREASE = Double.parseDouble(System.getProperty(
      "gwt.jsinlinerRatio", "1.0"));

  /**
   * Allow for some constant increase in size to account for inlining of simple expressions.
   *
   * It is commonly desired that small code fragments (in most cases consisting of plain operations)
   * is inlined even if it slightly increases code size because by doing so it creates more
   * opportunities for the static evaluator.
   */
  private static final int INLINING_BIAS = Integer.parseInt(System.getProperty(
      "gwt.jsinlinerInliningBias", "5"));

  /**
   * Static entry point used by JavaToJavaScriptCompiler.
   */
  public static OptimizerStats exec(JsProgram program, Collection<JsNode> toInline) {
    Event optimizeJsEvent = SpeedTracerLogger.start(
        CompilerEventType.OPTIMIZE_JS, "optimizer", NAME);
    OptimizerStats stats = execImpl(program, toInline);
    optimizeJsEvent.end("didChange", "" + stats.didChange());
    return stats;
  }

  /**
   * Determine whether or not a list of AST nodes are affected by side effects.
   * The context parameter provides a scope in which local (and therefore
   * immutable) variables are defined.
   */
  private static boolean affectedBySideEffects(List<JsExpression> list,
      JsFunction context) {
    /*
     * If the caller contains no nested functions, none of its locals can
     * possibly be affected by side effects.
     */
    JsScope safeScope = null;
    if (context != null && !containsNestedFunctions(context)) {
      safeScope = context.getScope();
    }
    AffectedBySideEffectsVisitor v = new AffectedBySideEffectsVisitor(safeScope);
    v.acceptList(list);
    return v.affectedBySideEffects();
  }

  /**
   * Generate an estimated measure of the syntactic complexity of a JsNode.
   */
  private static int complexity(JsNode toEstimate) {
    ComplexityEstimator e = new ComplexityEstimator();
    e.accept(toEstimate);
    return e.getComplexity();
  }

  /**
   * Examine a JsFunction to determine if it contains nested functions.
   */
  private static boolean containsNestedFunctions(JsFunction func) {
    NestedFunctionVisitor v = new NestedFunctionVisitor();
    v.accept(func.getBody());
    return v.containsNestedFunctions();
  }

  private static OptimizerStats execImpl(JsProgram program, Collection<JsNode> toInline) {
    OptimizerStats stats = new OptimizerStats(NAME);

    // We are not covering the whole AST, hence we will try to inline functions with a single call
    // site as well as those produced by native methods and their callers.
    SingleInvocationVisitor s = new SingleInvocationVisitor();
    s.accept(program);
    Set<JsNode> candidates = Sets.newLinkedHashSet(toInline);
    candidates.addAll(s.inliningCandidates());

    RedefinedFunctionCollector d = new RedefinedFunctionCollector();
    d.accept(program);

    RecursionCollector rc = new RecursionCollector();
    for (JsNode fn : candidates) {
      rc.accept(fn);
    }

    InliningVisitor v = new InliningVisitor(program, candidates);
    v.blacklist(d.getRedefined());
    v.blacklist(rc.getRecursive());
    // Do not accept among candidates as the list might get stale and contain nodes that are not
    // reachable from the AST. Instead filter within InliningVisitor.
    v.accept(program);

    if (v.didChange()) {
      stats.recordModified();
    }
    return stats;
  }

  /**
   * Check to see if the to-be-inlined statement shares any idents with the
   * call-side arguments. Two passes are made: the first one looks for qualified
   * names; the second pass looks for unqualified names, but ignores identifiers
   * that refer to function parameters.
   */
  private static boolean hasCommonIdents(List<JsExpression> arguments,
      JsNode toInline, Collection<String> parameterIdents) {

    // This is a fire-twice loop
    boolean checkQualified = false;
    do {
      checkQualified = !checkQualified;

      // Collect the idents used in the arguments and the statement
      IdentCollector argCollector = new IdentCollector(checkQualified);
      argCollector.acceptList(arguments);
      IdentCollector statementCollector = new IdentCollector(checkQualified);
      statementCollector.accept(toInline);

      Set<String> idents = argCollector.getIdents();

      // Unqualified idents may be references to parameters, thus ignored
      if (!checkQualified) {
        idents.removeAll(parameterIdents);
      }

      // Perform the set difference
      idents.retainAll(statementCollector.getIdents());

      if (idents.size() > 0) {
        return true;
      }
    } while (checkQualified);

    return false;
  }

  /**
   * Determine whether or not a list of AST nodes have side effects.
   */
  private static boolean hasSideEffects(List<JsExpression> list) {
    for (JsExpression expr : list) {
      if (expr.hasSideEffects()) {
        return true;
      }
    }
    return false;
  }

  /**
   * Given a delegated JsStatement, construct an expression to hoist into the
   * outer caller. This does not perform any name replacement, but simply
   * constructs a mutable copy of the expression that can be manipulated
   * at-will.
   *
   * @param statement the statement from which to extract the expressions
   * @return a JsExpression representing all expressions that would have been
   *         evaluated by the statement
   */
  private static JsExpression convertToExpression(JsStatement statement) {

    JsExpression expression;
    if (statement instanceof JsExprStmt) {
      // Extract the expression
      JsExprStmt exprStmt = (JsExprStmt) statement;
      expression = exprStmt.getExpression();
    } else if (statement instanceof JsReturn) {
      // Extract the return value
      JsReturn ret = (JsReturn) statement;
      expression = ret.getExpr();
      if (expression == null) {
        expression = new JsNameRef(ret.getSourceInfo(),
            JsRootScope.INSTANCE.getUndefined());
      }
    } else if (statement instanceof JsVars) {
      // Create a comma expression for variable initializers
      JsVars vars = (JsVars) statement;

      // Rely on comma expression cleanup to remove this later.
      expression = JsNullLiteral.INSTANCE;

      for (JsVar var : vars) {
        // Extract the initialization expression
        JsExpression init = var.getInitExpr();
        if (init != null) {
          SourceInfo sourceInfo = var.getSourceInfo();
          JsBinaryOperation assignment = new JsBinaryOperation(sourceInfo,
              JsBinaryOperator.ASG);
          assignment.setArg1(var.getName().makeRef(sourceInfo));
          assignment.setArg2(init);

          // Multiple initializers go into a comma expression
          JsBinaryOperation comma = new JsBinaryOperation(sourceInfo,
              JsBinaryOperator.COMMA);
          comma.setArg1(expression);
          comma.setArg2(assignment);
          expression = comma;
        }
      }
    } else {
      return null;
    }

    assert expression != null;
    return JsSafeCloner.clone(expression);
  }

  /**
   * Determine if a statement can be inlined into a call site.
   */
  private static boolean isInlinable(JsFunction caller, JsFunction callee,
      JsExpression thisExpr, List<JsExpression> arguments, JsNode toInline) {

    /*
     * This will happen with varargs-style JavaScript functions that rely on the
     * "arguments" array. The reference to arguments would be detected in
     * BoundedScopeVisitor, but the code below assumes the same number of
     * parameters and arguments.
     */
    if (arguments.size() != callee.getParameters().size()) {
      return false;
    }

    // Build up a list of all parameter names
    Set<JsName> parameterNames = Sets.newHashSet();
    Set<String> parameterIdents = Sets.newHashSet();
    for (JsParameter param : callee.getParameters()) {
      parameterNames.add(param.getName());
      parameterIdents.add(param.getName().getIdent());
    }

    /*
     * Make sure that inlining won't change the final name of non-parameter
     * idents due to the change of scope. The most likely cause would be the use
     * of an unqualified variable reference in a JSNI block that happened to
     * conflict with a Java-derived identifier.
     */
    StableNameChecker detector = new StableNameChecker(caller.getScope(),
        callee.getScope(), parameterNames);
    detector.accept(toInline);
    if (!detector.isStable()) {
      return false;
    }

    /*
     * Ensure that the names referred to by the argument list and the statement
     * are disjoint. This prevents inlining of the following:
     *
     * static int i; public void add(int a) { i += a; }; add(i++);
     */
    if (hasCommonIdents(arguments, toInline, parameterIdents)) {
      return false;
    }

    List<JsExpression> evalArgs;
    if (thisExpr == null) {
      evalArgs = arguments;
    } else {
      evalArgs = Lists.newArrayListWithCapacity(1 + arguments.size());
      evalArgs.add(thisExpr);
      evalArgs.addAll(arguments);
    }

    /*
     * Determine if the evaluation of the invocation's arguments may create side
     * effects. This will determine how aggressively the parameters may be
     * reordered.
     */
    if (isVolatile(evalArgs, caller)) {
      /*
       * Determine the order in which the parameters must be evaluated. This
       * will vary between call sites, based on whether or not the invocation's
       * arguments can be repeated without ill effect.
       */
      List<JsName> requiredOrder = Lists.newArrayList();
      if (thisExpr != null && isVolatile(thisExpr, callee)) {
        requiredOrder.add(EvaluationOrderVisitor.THIS_NAME);
      }
      for (int i = 0; i < arguments.size(); i++) {
        JsExpression e = arguments.get(i);
        JsParameter p = callee.getParameters().get(i);

        if (isVolatile(e, callee)) {
          requiredOrder.add(p.getName());
        }
      }

      // This would indicate that isVolatile changed its output between
      // the if statement and the loop.
      assert requiredOrder.size() > 0;

      /*
       * Verify that the non-reorderable arguments are evaluated in the right
       * order.
       */
      EvaluationOrderVisitor orderVisitor = new EvaluationOrderVisitor(
          requiredOrder, callee);
      orderVisitor.accept(toInline);
      if (!orderVisitor.maintainsOrder()) {
        return false;
      }
    }

    // Check that parameters aren't used in such a way as to prohibit inlining
    ParameterUsageVisitor v = new ParameterUsageVisitor(thisExpr != null,
        parameterNames);
    v.accept(toInline);
    if (v.hasViolation()) {
      return false;
    }

    // Hooray!
    return true;
  }

  /**
   * This is used in combination with {@link #hoistedExpression(JsStatement)} to
   * indicate if a given statement would terminate the list of hoisted
   * expressions.
   */
  private static boolean isReturnStatement(JsStatement statement) {
    return statement instanceof JsReturn;
  }

  /**
   * Indicates if an expression would create side effects or possibly be
   * affected by side effects when evaluated within a particular function
   * context.
   */
  private static boolean isVolatile(JsExpression e, JsFunction context) {
    return isVolatile(Collections.singletonList(e), context);
  }

  /**
   * Indicates if a list of expressions would create side effects or possibly be
   * affected by side effects when evaluated within a particular function
   * context.
   */
  private static boolean isVolatile(List<JsExpression> list, JsFunction context) {
    return hasSideEffects(list) || affectedBySideEffects(list, context);
  }

  /**
   * Transforms any <code>foo.call(this)</code> into <code>this.foo()</code> to
   * be compatible with our inlining algorithm.
   */
  private static JsInvocation tryToUnravelExplicitCall(JsInvocation x) {
    if (!(x.getQualifier() instanceof JsNameRef)) {
      return x;
    }
    JsNameRef ref = (JsNameRef) x.getQualifier();
    if (ref.getName().isObfuscatable() || !"call".equals(ref.getIdent())) {
      return x;
    }
    List<JsExpression> oldArgs = x.getArguments();
    if (oldArgs.size() < 1) {
      return x;
    }

    JsNameRef oldTarget = (JsNameRef) ref.getQualifier();
    JsNameRef newTarget = new JsNameRef(oldTarget.getSourceInfo(),
        oldTarget.getName());
    newTarget.setQualifier(oldArgs.get(0));
    JsInvocation newCall = new JsInvocation(x.getSourceInfo(), newTarget,
        // Don't need to clone because the returned invocation is transient.
        oldArgs.subList(1, oldArgs.size()));
    return newCall;
  }

  /**
   * Utility class.
   */
  private JsInliner() {
  }
}