/*
 * Copyright 2004 The Closure Compiler Authors.
 *
 * 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.javascript.jscomp;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.base.Strings.nullToEmpty;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ListMultimap;
import com.google.javascript.jscomp.NodeTraversal.AbstractPostOrderCallback;
import com.google.javascript.jscomp.NodeTraversal.ScopedCallback;
import com.google.javascript.rhino.Node;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import javax.annotation.Nullable;

/**
 * Apache Royale copied RenameVars and modified it to handle
 * Royale modules.
 * 
 * RenameVars renames all the variables names into short names, to reduce code
 * size and also to obfuscate the code.
 *
 */
final class RenameVarsWithModuleSupport implements CompilerPass {

  /**
   * Limit on number of locals in a scope for temporary local renaming
   * when {@code preferStableNames} is true.
   */
  private static final int MAX_LOCALS_IN_SCOPE_TO_TEMP_RENAME = 1000;

  private final AbstractCompiler compiler;

  /** List of global NAME nodes */
  private final ArrayList<Node> globalNameNodes = new ArrayList<Node>();

  /** List of local NAME nodes */
  private final ArrayList<Node> localNameNodes = new ArrayList<Node>();

  /** Mapping of original names for change detection */
  private final Map<Node, String> originalNameByNode = new HashMap<Node, String>();

  /**
   * Maps a name node to its pseudo name, null if we are not generating so
   * there will be no overhead unless we are debugging.
   */
  private final Map<Node, String> pseudoNameMap;

  /** Set of extern variable names */
  private Set<String> externNames;

  /** Set of reserved variable names */
  private final Set<String> reservedNames;

  /** The renaming map */
  private final Map<String, String> renameMap = new HashMap<String, String>();

  /** The previously used rename map. */
  private final VariableMap prevUsedRenameMap;

  /** The global name prefix */
  private final String prefix;

  /** Counter for each assignment */
  private int assignmentCount = 0;

  // Logic for bleeding functions, where the name leaks into the outer
  // scope on IE but not on other browsers.
  private final Set<Var> localBleedingFunctions = new HashSet<Var>();
  private final ListMultimap<Scope, Var> localBleedingFunctionsPerScope =
      ArrayListMultimap.create();

  class Assignment {
    final boolean isLocal;
    final String oldName;
    final int orderOfOccurrence;
    String newName;
    int count; // Number of times this is referenced

    Assignment(String name) {
      this.isLocal = name.startsWith(LOCAL_VAR_PREFIX);
      this.oldName = name;
      this.newName = null;
      this.count = 0;

      // Represents the order at which a symbol appears in the source.
      this.orderOfOccurrence = assignmentCount++;
    }

    /**
     * Assigns the new name.
     */
    void setNewName(String newName) {
      checkState(this.newName == null);
      this.newName = newName;
    }
  }

  /** Maps an old name to a new name assignment */
  private final Map<String, Assignment> assignments =
      new HashMap<String, Assignment>();

  /** Whether renaming should apply to local variables only. */
  private final boolean localRenamingOnly;

  /**
   * Whether function expression names should be preserved. Typically, for
   * debugging purposes.
   *
   * @see NameAnonymousFunctions
   */
  private final boolean preserveFunctionExpressionNames;

  private final boolean shouldShadow;

  private final boolean preferStableNames;

  /** Characters that shouldn't be used in variable names. */
  private final char[] reservedCharacters;

  /** A prefix to distinguish temporary local names from global names */
  private static final String LOCAL_VAR_PREFIX = "L ";

  // Shared name generator
  private final NameGenerator nameGenerator;

  /* list of aliases from the externs */
  private List<String> externAliases;
  
  /*
   * nameGenerator is a shared NameGenerator that this instance can use;
   * the instance may reset or reconfigure it, so the caller should
   * not expect any state to be preserved.
   */
  RenameVarsWithModuleSupport(AbstractCompiler compiler, String prefix,
      boolean localRenamingOnly, boolean preserveFunctionExpressionNames,
      boolean generatePseudoNames, boolean shouldShadow,
      boolean preferStableNames, VariableMap prevUsedRenameMap,
      @Nullable char[] reservedCharacters,
      @Nullable Set<String> reservedNames,
      NameGenerator nameGenerator) {
    this.compiler = compiler;
    this.prefix = nullToEmpty(prefix);
    this.localRenamingOnly = localRenamingOnly;
    this.preserveFunctionExpressionNames = preserveFunctionExpressionNames;
    if (generatePseudoNames) {
      this.pseudoNameMap = new HashMap<Node, String>();
    } else {
      this.pseudoNameMap = null;
    }
    this.prevUsedRenameMap = prevUsedRenameMap;
    this.reservedCharacters = reservedCharacters;
    this.shouldShadow = shouldShadow;
    this.preferStableNames = preferStableNames;
    if (reservedNames == null) {
      this.reservedNames = new HashSet<String>();
    } else {
      this.reservedNames = new HashSet<String>(reservedNames);
    }
    this.nameGenerator = nameGenerator;
  }

  /**
   * Iterate through the nodes, collect all the NAME nodes that need to be
   * renamed, and count how many times each variable name is referenced.
   *
   * Keep track of all name references in globalNameNodes, and localNameNodes.
   *
   * To get shorter local variable renaming, we rename local variables to a
   * temporary name "LOCAL_VAR_PREFIX + index" where index is the index of the
   * variable declared in the local scope stack.
   * e.g.
   * Foo(fa, fb) {
   *   var c = function(d, e) { return fa; }
   * }
   * The indexes are: fa:0, fb:1, c:2, d:3, e:4
   *
   * In that way, local variable names are reused in each global function.
   * e.g. the final code might look like
   * function x(a,b) { ... }
   * function y(a,b,c) { ... }
   */
  class ProcessVars extends AbstractPostOrderCallback implements ScopedCallback {

    @Override
    public void enterScope(NodeTraversal t) {
      if (t.inGlobalHoistScope() || !shouldTemporarilyRenameLocalsInScope(t.getScope())) {
        return;
      }
      Scope scope = t.getScope();
      for (Var current : scope.getVarIterable()) {
        if (current.isBleedingFunction()) {
          localBleedingFunctions.add(current);
          localBleedingFunctionsPerScope.put(
              scope.getParent(), current);
        }
      }
    }

    @Override
    public void exitScope(NodeTraversal t) {}

    @Override
    public void visit(NodeTraversal t, Node n, Node parent) {
      if (!(n.isName() || n.isImportStar())) {
        return;
      }

      String name = n.getString();

      // Ignore anonymous functions and classes.
      if (name.isEmpty()) {
        return;
      }

      // "import {x as y} from 'm';"
      // Skip x because it's not a variable in this scope.
      if (parent.isImportSpec() && parent.hasTwoChildren() && parent.getFirstChild() == n) {
        return;
      }

      // Is this local or Global?
      // Bleeding functions should be treated as part of their outer
      // scope, because IE has bugs in how it handles bleeding
      // functions.
      Var var = t.getScope().getVar(name);
      boolean local =
          var != null
              && var.isLocal()
              && (var.scope.getParent().isLocal() || !var.isBleedingFunction());

      // Never rename references to the arguments array
      if (var != null && var.isArguments()) {
        reservedNames.add(name);
        return;
      }

      // Are we renaming global variables?
      if (!local && localRenamingOnly) {
        reservedNames.add(name);
        return;
      }

      // Are we renaming function expression names?
      if (preserveFunctionExpressionNames && var != null
          && NodeUtil.isFunctionExpression(var.getParentNode())) {
        reservedNames.add(name);
        return;
      }

      // Check if we can rename this.
      if (!okToRenameVar(name, local)) {
        if (local) {
          // Blindly de-uniquify for the Prototype library for
          // http://blickly.github.io/closure-compiler-issues/#103
          String newName = MakeDeclaredNamesUnique.ContextualRenameInverter.getOriginalName(name);
          if (!newName.equals(name)) {
            n.setString(newName);
          }
        }
        return;
      }

      if (pseudoNameMap != null) {
        recordPseudoName(n);
      }

      if (local && shouldTemporarilyRenameLocalsInScope(var.getScope())) {
        // Give local variables a temporary name based on the
        // variable's index in the scope to enable name reuse across
        // locals in independent scopes.
        String tempName = LOCAL_VAR_PREFIX + getLocalVarIndex(var);
        incCount(tempName);
        localNameNodes.add(n);
        // Remember the original string in a name before it's temporarily filled with an "L".
        originalNameByNode.put(n, n.getString());
        n.setString(tempName);
      } else if (var != null) { // Not an extern
        // If it's global, increment global count
        incCount(name);
        globalNameNodes.add(n);
      }
    }

    // Increment count of an assignment
    void incCount(String name) {
      Assignment s = assignments.get(name);
      if (s == null) {
        s = new Assignment(name);
        assignments.put(name, s);
      }
      s.count++;
    }
  }

  /**
   * Sorts Assignment objects by their count, breaking ties by their order of
   * occurrence in the source to ensure a deterministic total ordering.
   */
  private static final Comparator<Assignment> FREQUENCY_COMPARATOR =
      new Comparator<Assignment>() {
    @Override
    public int compare(Assignment a1, Assignment a2) {
      if (a1.count != a2.count) {
        return a2.count - a1.count;
      }
      // Break a tie using the order in which the variable first appears in
      // the source.
      return ORDER_OF_OCCURRENCE_COMPARATOR.compare(a1, a2);
    }
  };

  /**
   * Sorts Assignment objects by the order the variable name first appears in
   * the source.
   */
  private static final Comparator<Assignment> ORDER_OF_OCCURRENCE_COMPARATOR =
      new Comparator<Assignment>() {
        @Override
        public int compare(Assignment a1, Assignment a2) {
          return a1.orderOfOccurrence - a2.orderOfOccurrence;
        }
      };

  @Override
  public void process(Node externs, Node root) {
	externAliases = ProcessClosurePrimitivesWithModuleSupport.externedAliases.get(externs);
    this.externNames = NodeUtil.collectExternVariableNames(this.compiler, externs);

    originalNameByNode.clear();

    // Do variable reference counting.
    NodeTraversal.traverse(compiler, root, new ProcessVars());

    // Make sure that new names don't overlap with extern names.
    reservedNames.addAll(externNames);

    // Rename vars, sorted by frequency of occurrence to minimize code size.
    SortedSet<Assignment> varsByFrequency = new TreeSet<Assignment>(FREQUENCY_COMPARATOR);
    varsByFrequency.addAll(assignments.values());

    if (shouldShadow) {
      new ShadowVariablesWithModuleSupport(
          compiler, assignments, varsByFrequency, pseudoNameMap).process(
              externs, root);
    }

    // First try to reuse names from an earlier compilation.
    if (prevUsedRenameMap != null) {
      reusePreviouslyUsedVariableMap(varsByFrequency);
    }

    // now that previous names have been assigned, 
    // add those previous renames to reserved names
    // so those variable names don't get re-used in assignNames.
    if (prevUsedRenameMap != null) {
    	reservedNames.addAll(prevUsedRenameMap.getNewNameToOriginalNameMap().keySet());
    }
    
    // Assign names, sorted by descending frequency to minimize code size.
    assignNames(varsByFrequency);

    // Rename the globals!
    for (Node n : globalNameNodes) {
      /* A module may have a reference to a class
       * but no variable defining it since the class
       * is defined in the main loading app.  Closure 
       * expects every reference to have a var so in
       * CollapseProperties, some vars are added so that
       * they can be collapsed.  However, we don't want those
       * added vars in the output so here we move them
       * to externs (if we added them to the externs in 
       * CollapseProperties they wouldn't get renamed).
       */ 
      boolean moveToExternsAfterRename = false;
      String renamedVar = n.getString();
      if (prevUsedRenameMap != null && 
    		  externAliases.contains(renamedVar) &&
      		  n.getParent().isVar())
        moveToExternsAfterRename = true;
      setNameAndReport(n, getNewGlobalName(n));
      if (moveToExternsAfterRename) {
        Node p = n.getParent();
        p.detach();
        Node externsInput = compiler.getSynthesizedExternsInput().getAstRoot(compiler);
        externsInput.addChildToBack(p);
        compiler.reportChangeToEnclosingScope(p);
      }
    }

    // Rename the locals!
    for (Node n : localNameNodes) {
      setNameAndReport(n, getNewLocalName(n));
    }
  }

  private void setNameAndReport(Node n, @Nullable String newName) {
    // A null newName, indicates it should not be renamed.
    if (newName != null && !newName.equals(n.getString())) {
      n.setString(newName);

      // Only mark changes if the final name change is different than it was original before being
      // filled with the "L" temporary name.
      if (!newName.equals(originalNameByNode.get(n))) {
        compiler.reportChangeToEnclosingScope(n);
        Node parent = n.getParent();
        if (parent.isFunction() && NodeUtil.isFunctionDeclaration(parent)) {
          // If we are renaming a function declaration, make sure the containing scope
          // has the opportunity to act on the change.
          compiler.reportChangeToEnclosingScope(parent);
        }
      }
    }
  }

  @Nullable
  private String getNewGlobalName(Node n) {
    String oldName = n.getString();
    Assignment a = assignments.get(oldName);
    if (a.newName != null && !a.newName.equals(oldName)) {
      if (pseudoNameMap != null) {
        return pseudoNameMap.get(n);
      }
      return a.newName;
    } else {
      return null;
    }
  }

  @Nullable
  private String getNewLocalName(Node n) {
    String oldTempName = n.getString();
    Assignment a = assignments.get(oldTempName);
    if (!a.newName.equals(oldTempName)) {
      if (pseudoNameMap != null) {
        return pseudoNameMap.get(n);
      }
      return a.newName;
    }
    return null;
  }

  private void recordPseudoName(Node n) {
    // Variable names should be in a different name space than
    // property pseudo names.
    pseudoNameMap.put(n, '$' + n.getString() + "$$");
  }

  /**
   * Runs through the assignments and reuses as many names as possible from the previously used
   * variable map. Updates reservedNames with the set of names that were reused.
   */
  private void reusePreviouslyUsedVariableMap(SortedSet<Assignment> varsToRename) {
    // If prevUsedRenameMap had duplicate values then this pass would be
    // non-deterministic.
    // In such a case, the following will throw an IllegalArgumentException.
    checkNotNull(prevUsedRenameMap.getNewNameToOriginalNameMap());
    for (Assignment a : varsToRename) {
      String prevNewName = prevUsedRenameMap.lookupNewName(a.oldName);
      if (prevNewName == null || reservedNames.contains(prevNewName)) {
        continue;
      }

      if (a.isLocal
          || (!externNames.contains(a.oldName)
              && prevNewName.startsWith(prefix))) {
        reservedNames.add(prevNewName);
        finalizeNameAssignment(a, prevNewName);
      }
    }
  }

  /**
   * Determines which new names to substitute for the original names.
   */
  private void assignNames(SortedSet<Assignment> varsToRename) {
    NameGenerator globalNameGenerator = null;
    NameGenerator localNameGenerator = null;

    globalNameGenerator = nameGenerator;
    nameGenerator.reset(reservedNames, prefix, reservedCharacters);

    // Local variables never need a prefix.
    // Also, we need to avoid conflicts between global and local variable
    // names; we do this by having using the same generator (not two
    // instances). The case where global variables have a prefix (and
    // therefore we use two different generators) but a local variable name
    // might nevertheless conflict with a global one is not handled.
    localNameGenerator =
        prefix.isEmpty()
        ? globalNameGenerator
        : nameGenerator.clone(reservedNames, "", reservedCharacters);

    // Generated names and the assignments for non-local vars.
    List<Assignment> pendingAssignments = new ArrayList<Assignment>();
    List<String> generatedNamesForAssignments = new ArrayList<String>();

    for (Assignment a : varsToRename) {
      if (a.newName != null) {
        continue;
      }

      if (externNames.contains(a.oldName)) {
        continue;
      }

      String newName;
      if (a.isLocal) {
        // For local variable, we make the assignment right away.
        newName = localNameGenerator.generateNextName();
        finalizeNameAssignment(a, newName);
      } else {
        // For non-local variable, delay finalizing the name assignment
        // until we know how many new names we'll have of length 2, 3, etc.
        newName = globalNameGenerator.generateNextName();
        pendingAssignments.add(a);
        generatedNamesForAssignments.add(newName);
      }
      reservedNames.add(newName);
    }

    // Now that we have a list of generated names, and a list of variable
    // Assignment objects, we assign the generated names to the vars as
    // follows:
    // 1) The most frequent vars get the shorter names.
    // 2) If N number of vars are going to be assigned names of the same
    //    length, we assign the N names based on the order at which the vars
    //    first appear in the source. This makes the output somewhat less
    //    random, because symbols declared close together are assigned names
    //    that are quite similar. With this heuristic, the output is more
    //    compressible.
    //    For instance, the output may look like:
    //    var da = "..", ea = "..";
    //    function fa() { .. } function ga() { .. }

    int numPendingAssignments = generatedNamesForAssignments.size();
    for (int i = 0; i < numPendingAssignments;) {
      SortedSet<Assignment> varsByOrderOfOccurrence =
          new TreeSet<Assignment>(ORDER_OF_OCCURRENCE_COMPARATOR);

      // Add k number of Assignment to the set, where k is the number of
      // generated names of the same length.
      int len = generatedNamesForAssignments.get(i).length();
      for (int j = i; j < numPendingAssignments
          && generatedNamesForAssignments.get(j).length() == len; j++) {
        varsByOrderOfOccurrence.add(pendingAssignments.get(j));
      }

      // Now, make the assignments
      for (Assignment a : varsByOrderOfOccurrence) {
        finalizeNameAssignment(a, generatedNamesForAssignments.get(i));
        ++i;
      }
    }
  }

  /**
   * Makes a final name assignment.
   */
  private void finalizeNameAssignment(Assignment a, String newName) {
    a.setNewName(newName);

    // Keep track of the mapping
    renameMap.put(a.oldName, newName);
  }

  /**
   * Gets the variable map.
   */
  VariableMap getVariableMap() {
    return new VariableMap(ImmutableMap.copyOf(renameMap));
  }

  /**
   * Determines whether a variable name is okay to rename.
   */
  private boolean okToRenameVar(String name, boolean isLocal) {
    return !compiler.getCodingConvention().isExported(name, isLocal);
  }

  /**
   * Returns the index within the scope stack.
   * e.g. function Foo(a) { var b; function c(d) { } }
   * a = 0, b = 1, c = 2, d = 3
   */
  private int getLocalVarIndex(Var v) {
    int num = v.index;
    Scope s = v.scope.getParent();
    if (s == null) {
      throw new IllegalArgumentException("Var is not local");
    }

    boolean isBleedingIntoScope = s.getParent() != null && localBleedingFunctions.contains(v);

    while (s.getParent() != null) {
      if (isBleedingIntoScope) {
        num += localBleedingFunctionsPerScope.get(s).indexOf(v) + 1;
        isBleedingIntoScope = false;
      } else {
        num += localBleedingFunctionsPerScope.get(s).size();
      }
      if (shouldTemporarilyRenameLocalsInScope(s)) {
        num += s.getVarCount();
      }
      s = s.getParent();
    }
    return num;
  }

  /**
   * Returns true if the local variables in a scope should be given
   * temporary names (eg, 'L 123') prior to renaming to allow reuse of
   * names across scopes.  With {@code preferStableNames}, temporary
   * renaming is disabled if the number of locals in the scope is
   * above a heuristic threshold to allow effective reuse of rename
   * maps (see {@code prevUsedRenameMap}).  In scopes with many
   * variables the temporary name given to a variable is unlikely to
   * be the same temporary name used when the rename map was created.
   */
  private boolean shouldTemporarilyRenameLocalsInScope(Scope s) {
    return (!preferStableNames || s.getVarCount() <= MAX_LOCALS_IN_SCOPE_TO_TEMP_RENAME);
  }
}
