dart2js: Implement frequency based naming.

pkg/compiler/lib/src/js_backend/namer.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of js_backend;
 
 /**
  * Assigns JavaScript identifiers to Dart variables, class-names and members.
  *
  * Names are generated through three stages:
@@ skipping 369 matching lines @@
   /// [_disambiguateMember], [_disambiguateInternalMember],
   /// [_disambiguateOperator], and [reservePublicMemberName].
   final Set<String> usedInstanceNames = new Set<String>();
   final Map<String, jsAst.Name> userInstanceMembers =
       new HashMap<String, jsAst.Name>();
   final Map<Element, jsAst.Name> internalInstanceMembers =
       new HashMap<Element, jsAst.Name>();
   final Map<String, jsAst.Name> userInstanceOperators =
       new HashMap<String, jsAst.Name>();
 
+  Set<String> getUsedNames(NamingScope scope) {
+    if (scope == NamingScope.global) {
+      return usedGlobalNames;
+    } else {
+      assert(scope == NamingScope.instance);
+      return usedInstanceNames;
+    }
+  }
+
   final Map<String, int> popularNameCounters = <String, int>{};
 
   final Map<LibraryElement, String> libraryLongNames =
       new HashMap<LibraryElement, String>();
 
   final Map<ConstantValue, jsAst.Name> constantNames =
       new HashMap<ConstantValue, jsAst.Name>();
   final Map<ConstantValue, String> constantLongNames =
       <ConstantValue, String>{};
   ConstantCanonicalHasher constantHasher;
 
   /// Maps private names to a library that may use that name without prefixing
   /// itself. Used for building proposed names.
   final Map<String, LibraryElement> shortPrivateNameOwners =
       <String, LibraryElement>{};
 
   /// Maps proposed names to *suggested* disambiguated names.
   ///
   /// Suggested names are hints to the [MinifyNamer], suggesting that a specific
   /// names be given to the first item with the given proposed name.
   ///
   /// This is currently used in [MinifyNamer] to assign very short minified
   /// names to things that tend to be used very often.
   final Map<String, String> suggestedGlobalNames = <String, String>{};
   final Map<String, String> suggestedInstanceNames = <String, String>{};
 
+  Map<String, String> getSuggestedNames(NamingScope scope) {
+    if (scope == NamingScope.global) {
+      return suggestedGlobalNames;
+    } else {
+      assert(scope == NamingScope.instance);
+      return suggestedInstanceNames;
+    }
+  }
+
+
   /// Used to store unique keys for library names. Keys are not used as names,
   /// nor are they visible in the output. The only serve as an internal
   /// key into maps.
   final Map<LibraryElement, String> _libraryKeys =
       new HashMap<LibraryElement, String>();
 
   Namer(Compiler compiler)
       : compiler = compiler,
         constantHasher = new ConstantCanonicalHasher(compiler),
         functionTypeNamer = new FunctionTypeNamer(compiler) {
@@ skipping 72 matching lines @@
   ///
   /// Unique within the global-member namespace.
   jsAst.Name constantName(ConstantValue constant) {
     // In the current implementation it doesn't make sense to give names to
     // function constants since the function-implementation itself serves as
     // constant and can be accessed directly.
     assert(!constant.isFunction);
     jsAst.Name result = constantNames[constant];
     if (result == null) {
       String longName = constantLongName(constant);
-      result = getFreshName(longName, usedGlobalNames, suggestedGlobalNames);
+      result = getFreshName(NamingScope.global, longName);
       constantNames[constant] = result;
     }
     return result;
   }
 
   /// Proposed name for [constant].
   String constantLongName(ConstantValue constant) {
     String longName = constantLongNames[constant];
     if (longName == null) {
       longName = new ConstantNamingVisitor(compiler, constantHasher)
@@ skipping 295 matching lines @@
     jsAst.Name disambiguatedName = _disambiguateMember(originalName);
     return deriveGetterName(disambiguatedName);
   }
 
   /// Disambiguated name for a compiler-owned global variable.
   ///
   /// The resulting name is unique within the global-member namespace.
   jsAst.Name _disambiguateInternalGlobal(String name) {
     jsAst.Name newName = internalGlobals[name];
     if (newName == null) {
-      newName = getFreshName(name, usedGlobalNames, suggestedGlobalNames);
+      newName = getFreshName(NamingScope.global, name);
       internalGlobals[name] = newName;
     }
     return newName;
   }
 
   /// Returns the property name to use for a compiler-owner global variable,
   /// i.e. one that does not correspond to any element but is used as a utility
   /// global by code generation.
   ///
   /// [name] functions as both the proposed name for the global, and as a key
@@ skipping 26 matching lines @@
   /// Returns the disambiguated name for a top-level or static element.
   ///
   /// The resulting name is unique within the global-member namespace.
   jsAst.Name _disambiguateGlobal(Element element) {
     // TODO(asgerf): We can reuse more short names if we disambiguate with
     // a separate namespace for each of the global holder objects.
     element = element.declaration;
     jsAst.Name newName = userGlobals[element];
     if (newName == null) {
       String proposedName = _proposeNameForGlobal(element);
-      newName = getFreshName(proposedName, usedGlobalNames,
-                             suggestedGlobalNames);
+      newName = getFreshName(NamingScope.global, proposedName);
       userGlobals[element] = newName;
     }
     return newName;
   }
 
   /// Returns the disambiguated name for an instance method or field
   /// with [originalName] in [library].
   ///
   /// [library] may be `null` if [originalName] is known to be public.
   ///
@@ skipping 19 matching lines @@
     // This avoids clashes since the original names cannot contain that symbol.
     String key = '$libraryKey@${originalName.text}@${suffixes.join('@')}';
     jsAst.Name newName = userInstanceMembers[key];
     if (newName == null) {
       String proposedName = privateName(originalName);
       if (!suffixes.isEmpty) {
         // In the proposed name, separate the name parts by '$', because the
         // proposed name must be a valid identifier, but not necessarily unique.
         proposedName += r'$' + suffixes.join(r'$');
       }
-      newName = getFreshName(proposedName,
-                             usedInstanceNames, suggestedInstanceNames,
+      newName = getFreshName(NamingScope.instance, proposedName,
                              sanitizeForAnnotations: true);
       userInstanceMembers[key] = newName;
     }
     return newName;
   }
 
   /// Forces the public instance member with [originalName] to have the given
   /// [disambiguatedName].
   ///
   /// The [originalName] must not have been disambiguated before, and the
@@ skipping 18 matching lines @@
   /// This is used as the property name for fields, type variables,
   /// constructor bodies, and super-accessors.
   ///
   /// The resulting name is unique within the instance-member namespace.
   jsAst.Name _disambiguateInternalMember(Element element,
                                          String proposeName()) {
     jsAst.Name newName = internalInstanceMembers[element];
     if (newName == null) {
       String name = proposeName();
       bool mayClashNative = _isUserClassExtendingNative(element.enclosingClass);
-      newName = getFreshName(name,
-                             usedInstanceNames, suggestedInstanceNames,
+      newName = getFreshName(NamingScope.instance, name,
                              sanitizeForAnnotations: true,
                              sanitizeForNatives: mayClashNative);
       internalInstanceMembers[element] = newName;
     }
     return newName;
   }
 
   /// Disambiguated name for the given operator.
   ///
   /// [operatorIdentifier] must be the operator's identifier, e.g.
   /// `$add` and not `+`.
   ///
   /// The resulting name is unique within the instance-member namespace.
   jsAst.Name _disambiguateOperator(String operatorIdentifier) {
     jsAst.Name newName = userInstanceOperators[operatorIdentifier];
     if (newName == null) {
-      newName = getFreshName(operatorIdentifier, usedInstanceNames,
-                             suggestedInstanceNames);
+      newName = getFreshName(NamingScope.instance, operatorIdentifier);
       userInstanceOperators[operatorIdentifier] = newName;
     }
     return newName;
   }
 
-  /// Returns an unused name.
-  ///
-  /// [proposedName] must be a valid JavaScript identifier.
-  ///
-  /// If [sanitizeForAnnotations] is `true`, then the result is guaranteed not
-  /// to have the form of an annotated name.
-  ///
-  /// If [sanitizeForNatives] it `true`, then the result is guaranteed not to
-  /// clash with a property name on a native object.
-  ///
-  /// Note that [MinifyNamer] overrides this method with one that produces
-  /// minified names.
-  jsAst.Name getFreshName(String proposedName,
-                          Set<String> usedNames,
-                          Map<String, String> suggestedNames,
-                          {bool sanitizeForAnnotations: false,
-                           bool sanitizeForNatives: false}) {
+  String _generateFreshStringForName(String proposedName,
+      Set<String> usedNames,
+      Map<String, String> suggestedNames,
+      {bool sanitizeForAnnotations: false,
+       bool sanitizeForNatives: false}) {
     if (sanitizeForAnnotations) {
       proposedName = _sanitizeForAnnotations(proposedName);
     }
     if (sanitizeForNatives) {
       proposedName = _sanitizeForNatives(proposedName);
     }
     proposedName = _sanitizeForKeywords(proposedName);
     String candidate;
     if (!usedNames.contains(proposedName)) {
       candidate = proposedName;
     } else {
       int counter = popularNameCounters[proposedName];
       int i = (counter == null) ? 0 : counter;
       while (usedNames.contains("$proposedName$i")) {
         i++;
       }
       popularNameCounters[proposedName] = i + 1;
       candidate = "$proposedName$i";
     }
     usedNames.add(candidate);
+    return candidate;
+  }
+
+  /// Returns an unused name.
+  ///
+  /// [proposedName] must be a valid JavaScript identifier.
+  ///
+  /// If [sanitizeForAnnotations] is `true`, then the result is guaranteed not
+  /// to have the form of an annotated name.
+  ///
+  /// If [sanitizeForNatives] it `true`, then the result is guaranteed not to
+  /// clash with a property name on a native object.
+  ///
+  /// Note that [MinifyNamer] overrides this method with one that produces
+  /// minified names.
+  jsAst.Name getFreshName(NamingScope scope,
+                          String proposedName,
+                          {bool sanitizeForAnnotations: false,
+                           bool sanitizeForNatives: false}) {
+    String candidate =
+        _generateFreshStringForName(proposedName,
+                                    getUsedNames(scope),
+                                    getSuggestedNames(scope),
+                                    sanitizeForAnnotations:
+                                        sanitizeForAnnotations,
+                                    sanitizeForNatives: sanitizeForNatives);
     return new StringBackedName(candidate);
   }
 
   /// Returns a variant of [name] that cannot clash with the annotated
   /// version of another name, that is, the resulting name can never be returned
   /// by [deriveGetterName], [deriveSetterName], [deriveCallMethodName],
   /// [operatorIs], or [substitutionName].
   ///
   /// For example, a name `get$x` would be converted to `$get$x` to ensure it
   /// cannot clash with the getter for `x`.
@@ skipping 309 matching lines @@
 
   String get functionTypeNamedParametersTag => r'named';
 
   Map<FunctionType, jsAst.Name> functionTypeNameMap =
       new HashMap<FunctionType, jsAst.Name>();
   final FunctionTypeNamer functionTypeNamer;
 
   jsAst.Name getFunctionTypeName(FunctionType functionType) {
     return functionTypeNameMap.putIfAbsent(functionType, () {
       String proposedName = functionTypeNamer.computeName(functionType);
-      return getFreshName(proposedName, usedInstanceNames,
-                          suggestedInstanceNames);
+      return getFreshName(NamingScope.instance, proposedName);
     });
   }
 
   jsAst.Name operatorIsType(DartType type) {
     if (type.isFunctionType) {
       // TODO(erikcorry): Reduce from $isx to ix when we are minifying.
       return new CompoundName([new StringBackedName(operatorIsPrefix),
                                _literalUnderscore,
                                getFunctionTypeName(type)]);
     }
@@ skipping 120 matching lines @@
   }
 
   void forgetElement(Element element) {
     jsAst.Name globalName = userGlobals[element];
     invariant(element, globalName != null, message: 'No global name.');
     usedGlobalNames.remove(globalName);
     userGlobals.remove(element);
   }
 }
 
-abstract class _NamerName extends jsAst.Name {
-  int get _kind;
-}
-
-class StringBackedName extends _NamerName {
-  final String name;
-  int get _kind => 1;
-  
-  StringBackedName(this.name);
-
-  toString() => throw new UnsupportedError("Cannot convert a name to a string");
-
-  operator==(other) {
-    if (identical(this, other)) return true;
-    return (other is StringBackedName) && other.name == name;
-  }
-
-  int get hashCode => name.hashCode;
-
-  int compareTo(_NamerName other) {
-    if (other._kind != _kind) return other._kind - _kind;
-    return name.compareTo(other.name);
-  }
-}
-
-abstract class _PrefixedName extends _NamerName {
-  final jsAst.Name prefix;
-  final jsAst.Name base;
-  int get _kind;
-
-  _PrefixedName(this.prefix, this.base);
-  
-  String get name => prefix.name + base.name;
-
-  toString() => throw new UnsupportedError("Cannot convert a name to a string");
-
-  bool operator==(other) {
-    if (identical(this, other)) return true;
-    if (other is! _PrefixedName) return false;
-    return other.base == base && other.prefix == prefix;
-  }
-
-  int get hashCode => base.hashCode * 13 + prefix.hashCode;
-
-  int compareTo(_NamerName other) {
-    if (other._kind != _kind) return other._kind - _kind;
-    _PrefixedName otherSameKind = other;
-    int result = prefix.compareTo(otherSameKind.prefix);
-    if (result == 0) {
-      result = name.compareTo(otherSameKind.name);
-    }
-    return result;
-  }
-}
-
-class GetterName extends _PrefixedName {
-  int get _kind => 2;
-
-  GetterName(jsAst.Name prefix, jsAst.Name base) : super(prefix, base);
-}
-
-class SetterName extends _PrefixedName {
-  int get _kind => 3;
-
-  SetterName(jsAst.Name prefix, jsAst.Name base) : super(prefix, base);
-}
-
-class _AsyncName extends _PrefixedName {
-  int get _kind => 4;
-
-  _AsyncName(jsAst.Name prefix, jsAst.Name base) : super(prefix, base);
-
-  @override
-  bool get allowRename => true;
-}
-
-class CompoundName extends _NamerName {
-  final List<_NamerName> _parts;
-  int get _kind => 4;
-  String _cachedName;
-  int _cachedHashCode = -1;
-
-  CompoundName(this._parts);
-
-  String get name {
-    if (_cachedName == null) {
-      _cachedName = _parts.map((jsAst.Name name) => name.name).join();
-    }
-    return _cachedName;
-  }
-
-  toString() => throw new UnsupportedError("Cannot convert a name to a string");
-
-  bool operator==(other) {
-    if (identical(this, other)) return true;
-    if (other is! CompoundName) return false;
-    if (other._parts.length != _parts.length) return false;
-    for (int i = 0; i < _parts.length; ++i) {
-      if (other._parts[i] != _parts[i]) return false;
-    }
-    return true;
-  }
-
-  int get hashCode {
-    if (_cachedHashCode < 0) {
-      _cachedHashCode = 0;
-      for (jsAst.Name name in _parts) {
-        _cachedHashCode = (_cachedHashCode * 17 + name.hashCode) & 0x7fffffff;
-      }
-    }
-    return _cachedHashCode;
-  }
-
-  int compareTo(_NamerName other) {
-    if (other._kind != _kind) return other._kind - _kind;
-    CompoundName otherSameKind = other;
-    if (otherSameKind._parts.length != _parts.length) {
-      return otherSameKind._parts.length - _parts.length;
-    }
-    int result = 0;
-    for (int pos = 0; result == 0 && pos < _parts.length; pos++) {
-      result = _parts[pos].compareTo(otherSameKind._parts[pos]);
-    }
-    return result;
-  }
-}
-
 /**
  * Generator of names for [ConstantValue] values.
  *
  * The names are stable under perturbations of the source.  The name is either a
  * short sequence of words, if this can be found from the constant, or a type
  * followed by a hash tag.
  *
  *     List_imX                // A List, with hash tag.
  *     C_Sentinel              // const Sentinel(),  "C_" added to avoid clash
  *                             //   with class name.
@@ skipping 415 matching lines @@
         if (!first) {
           sb.write('_');
         }
         sb.write('_');
         visit(parameter);
         first = true;
       }
     }
   }
 }
+
+enum NamingScope {
+  global,
+  instance
+}