// 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.
 */
class MinifyNamer extends Namer {
  MinifyNamer(Compiler compiler) : super(compiler) {
    reserveBackendNames();
    fieldRegistry = new _FieldNamingRegistry(this);
  }

  String get isolateName => 'I';
  String get isolatePropertiesName => 'p';
  bool get shouldMinify => true;

  final String getterPrefix = 'g';
  final String setterPrefix = 's';
  final String callPrefix = ''; // this will create function names $<n>

  final ALPHABET_CHARACTERS = 52;  // a-zA-Z.
  final ALPHANUMERIC_CHARACTERS = 62;  // a-zA-Z0-9.

  _FieldNamingRegistry fieldRegistry;

  // You can pass an invalid identifier to this and unlike its non-minifying
  // counterpart it will never return the proposedName as the new fresh name.
  String getFreshName(String proposedName,
                      Set<String> usedNames,
                      Map<String, String> suggestedNames,
                      {bool ensureSafe: true}) {
    var freshName;
    var suggestion = suggestedNames[proposedName];
    if (suggestion != null && !usedNames.contains(suggestion)) {
      freshName = suggestion;
    } else {
      freshName = _getUnusedName(proposedName, usedNames,
          suggestedNames.values);
    }
    usedNames.add(freshName);
    return freshName;
  }

  String getClosureVariableName(String name, int id) {
    if (id < ALPHABET_CHARACTERS) {
      return new String.fromCharCodes([_letterNumber(id)]);
    }
    return "${getMappedInstanceName('closure')}_$id";
  }

  // From issue 7554.  These should not be used on objects (as instance
  // variables) because they clash with names from the DOM. However, it is
  // OK to use them as fields, as we only access fields directly if we know
  // the receiver type.
  static const _reservedNativeProperties = const <String>[
      'Q', 'a', 'b', 'c', 'd', 'e', 'f', 'r', 'x', 'y', 'z',
      // 2-letter:
      'ch', 'cx', 'cy', 'db', 'dx', 'dy', 'fr', 'fx', 'fy', 'go', 'id', 'k1',
      'k2', 'k3', 'k4', 'r1', 'r2', 'rx', 'ry', 'x1', 'x2', 'y1', 'y2',
      // 3-letter:
      'add', 'all', 'alt', 'arc', 'CCW', 'cmp', 'dir', 'end', 'get', 'in1',
      'in2', 'INT', 'key', 'log', 'low', 'm11', 'm12', 'm13', 'm14', 'm21',
      'm22', 'm23', 'm24', 'm31', 'm32', 'm33', 'm34', 'm41', 'm42', 'm43',
      'm44', 'max', 'min', 'now', 'ONE', 'put', 'red', 'rel', 'rev', 'RGB',
      'sdp', 'set', 'src', 'tag', 'top', 'uid', 'uri', 'url', 'URL',
      // 4-letter:
      'abbr', 'atob', 'Attr', 'axes', 'axis', 'back', 'BACK', 'beta', 'bias',
      'Blob', 'blue', 'blur', 'BLUR', 'body', 'BOOL', 'BOTH', 'btoa', 'BYTE',
      'cite', 'clip', 'code', 'cols', 'cues', 'data', 'DECR', 'DONE', 'face',
      'file', 'File', 'fill', 'find', 'font', 'form', 'gain', 'hash', 'head',
      'high', 'hint', 'host', 'href', 'HRTF', 'IDLE', 'INCR', 'info', 'INIT',
      'isId', 'item', 'KEEP', 'kind', 'knee', 'lang', 'left', 'LESS', 'line',
      'link', 'list', 'load', 'loop', 'mode', 'name', 'Node', 'None', 'NONE',
      'only', 'open', 'OPEN', 'ping', 'play', 'port', 'rect', 'Rect', 'refX',
      'refY', 'RGBA', 'root', 'rows', 'save', 'seed', 'seek', 'self', 'send',
      'show', 'SINE', 'size', 'span', 'stat', 'step', 'stop', 'tags', 'text',
      'Text', 'time', 'type', 'view', 'warn', 'wrap', 'ZERO'];

  void reserveBackendNames() {
    for (var name in _reservedNativeProperties) {
      if (name.length < 2) {
        instanceNameMap[name] = name;
      }
      usedInstanceNames.add(name);
      // Getter and setter names are autogenerated by prepending 'g' and 's' to
      // field names.  Therefore there are some field names we don't want to
      // use.  It is implicit in the next line that the banned prefix is
      // only one character.
      if (_hasBannedPrefix(name)) usedInstanceNames.add(name.substring(1));
    }

    // These popular names are present in most programs and deserve
    // single character minified names.  We could determine the popular names
    // individually per program, but that would mean that the output of the
    // minifier was less stable from version to version of the program being
    // minified.
    _populateSuggestedNames(
        suggestedInstanceNames,
        usedInstanceNames,
        const <String>[
            r'$add', r'add$1', r'$and',
            r'$or',
            r'current', r'$shr', r'$eq', r'$ne',
            r'$index', r'$indexSet',
            r'$xor', r'clone$0',
            r'iterator', r'length',
            r'$lt', r'$gt', r'$le', r'$ge',
            r'moveNext$0', r'node', r'on', r'$negate', r'push', r'self',
            r'start', r'target', r'$shl', r'value', r'width', r'style',
            r'noSuchMethod$1', r'$mul', r'$div', r'$sub', r'$not', r'$mod',
            r'$tdiv', r'toString$0']);

    _populateSuggestedNames(
        suggestedGlobalNames,
        usedGlobalNames,
        const <String>[
            r'Object', 'wrapException', r'$eq', r'S', r'ioore',
            r'UnsupportedError$', r'length', r'$sub',
            r'$add', r'$gt', r'$ge', r'$lt', r'$le', r'add',
            r'iae',
            r'ArgumentError$', r'BoundClosure', r'Closure', r'StateError$',
            r'getInterceptor', r'max', r'$mul',
            r'Map', r'Key_Key', r'$div',
            r'List_List$from',
            r'LinkedHashMap_LinkedHashMap$_empty',
            r'LinkedHashMap_LinkedHashMap$_literal',
            r'min',
            r'RangeError$value', r'JSString', r'JSNumber',
            r'JSArray', r'createInvocationMirror', r'String',
            r'setRuntimeTypeInfo', r'createRuntimeType'
            ]);
  }

  void _populateSuggestedNames(Map<String, String> suggestionMap,
                               Set<String> used,
                               List<String> suggestions) {
    int c = $a - 1;
    String letter;
    for (String name in suggestions) {
      do {
        assert(c != $Z);
        c = (c == $z) ? $A : c + 1;
        letter = new String.fromCharCodes([c]);
      } while (used.contains(letter));
      assert(suggestionMap[name] == null);
      suggestionMap[name] = letter;
    }
  }


  // This gets a minified name based on a hash of the proposed name.  This
  // is slightly less efficient than just getting the next name in a series,
  // but it means that small changes in the input program will give smallish
  // changes in the output, which can be useful for diffing etc.
  String _getUnusedName(String proposedName, Set<String> usedNames,
                        Iterable<String> suggestions) {
    int hash = _calculateHash(proposedName);
    // Avoid very small hashes that won't try many names.
    hash = hash < 1000 ? hash * 314159 : hash;  // Yes, it's prime.

    // Try other n-character names based on the hash.  We try one to three
    // character identifiers.  For each length we try around 10 different names
    // in a predictable order determined by the proposed name.  This is in order
    // to make the renamer stable: small changes in the input should nornally
    // result in relatively small changes in the output.
    for (var n = 1; n <= 3; n++) {
      int h = hash;
      while (h > 10) {
        var codes = <int>[_letterNumber(h)];
        int h2 = h ~/ ALPHABET_CHARACTERS;
        for (var i = 1; i < n; i++) {
          codes.add(_alphaNumericNumber(h2));
          h2 ~/= ALPHANUMERIC_CHARACTERS;
        }
        final candidate = new String.fromCharCodes(codes);
        if (!usedNames.contains(candidate) &&
            !jsReserved.contains(candidate) &&
            !_hasBannedPrefix(candidate) &&
            (n != 1 || !suggestions.contains(candidate))) {
          return candidate;
        }
        // Try again with a slightly different hash.  After around 10 turns
        // around this loop h is zero and we try a longer name.
        h ~/= 7;
      }
    }
    return _badName(hash, usedNames);
  }

  /// Instance members starting with g and s are reserved for getters and
  /// setters.
  bool _hasBannedPrefix(String name) {
    int code = name.codeUnitAt(0);
    return code == $g || code == $s;
  }

  int _calculateHash(String name) {
    int h = 0;
    for (int i = 0; i < name.length; i++) {
      h += name.codeUnitAt(i);
      h &= 0xffffffff;
      h += h << 10;
      h &= 0xffffffff;
      h ^= h >> 6;
      h &= 0xffffffff;
    }
    return h;
  }

  /// If we can't find a hash based name in the three-letter space, then base
  /// the name on a letter and a counter.
  String _badName(int hash, Set<String> usedNames) {
    var startLetter = new String.fromCharCodes([_letterNumber(hash)]);
    var name;
    var i = 0;
    do {
      name = "$startLetter${i++}";
    } while (usedNames.contains(name));
    // We don't need to check for banned prefix because the name is in the form
    // xnnn, where nnn is a number.  There can be no getter or setter called
    // gnnn since that would imply a numeric field name.
    return name;
  }

  int _letterNumber(int x) {
    if (x >= ALPHABET_CHARACTERS) x %= ALPHABET_CHARACTERS;
    if (x < 26) return $a + x;
    return $A + x - 26;
  }

  int _alphaNumericNumber(int x) {
    if (x >= ALPHANUMERIC_CHARACTERS) x %= ALPHANUMERIC_CHARACTERS;
    if (x < 26) return $a + x;
    if (x < 52) return $A + x - 26;
    return $0 + x - 52;
  }

  String instanceFieldPropertyName(Element element) {
    if (element.hasFixedBackendName) {
      return element.fixedBackendName;
    }

    _FieldNamingScope names;
    if (element is BoxFieldElement) {
      names = new _FieldNamingScope.forBox(element.box, fieldRegistry);
    } else {
      ClassElement cls = element is ClosureFieldElement
          ? element.closureClass : element.enclosingClass;
      names = new _FieldNamingScope.forClass(cls, compiler.world,
          fieldRegistry);
    }

    // The inheritance scope based naming did not yield a name. For instance,
    // this could be because the field belongs to a mixin.
    if (!names.containsField(element)) {
      return super.instanceFieldPropertyName(element);
    }

    return names[element];
  }
}

/**
 * Encapsulates the global state of field naming.
 */
class _FieldNamingRegistry {
  final MinifyNamer namer;

  final Map<Entity, _FieldNamingScope> scopes =
      new Map<Entity, _FieldNamingScope>();

  final Map<Entity, String> globalNames = new Map<Entity, String>();

  int globalCount = 0;

  final List<String> nameStore = new List<String>();

  _FieldNamingRegistry(this.namer);

  String getName(int count) {
    if (count >= nameStore.length) {
      // The namer usually does not use certain names as they clash with
      // existing properties on JS objects (see [_reservedNativeProperties]).
      // However, some of them are really short and safe to use for fields.
      // Thus, we shortcut the namer to use those first.
      if (count < MinifyNamer._reservedNativeProperties.length &&
          MinifyNamer._reservedNativeProperties[count].length <= 2) {
        nameStore.add(MinifyNamer._reservedNativeProperties[count]);
      } else {
        nameStore.add(namer.getFreshName("field$count",
            namer.usedInstanceNames, namer.suggestedInstanceNames,
            ensureSafe: true));
      }
    }

    return nameStore[count];
  }
}

/**
 * A [_FieldNamingScope] encodes a node in the inheritance tree of the current
 * class hierarchy. The root node typically is the node corresponding to the
 * `Object` class. It is used to assign a unique name to each field of a class.
 * Unique here means unique wrt. all fields along the path back to the root.
 * This is achieved at construction time via the [_fieldNameCounter] field that counts the
 * number of fields on the path to the root node that have been encountered so
 * far.
 *
 * Obviously, this only works if no fields are added to a parent node after its
 * children have added their first field.
 */
class _FieldNamingScope {
  final _FieldNamingScope superScope;
  final Entity container;
  final Map<Element, String> names = new Maplet<Element, String>();
  final _FieldNamingRegistry registry;

  /// Naming counter used for fields of ordinary classes.
  int _fieldNameCounter;

  /// The number of fields along the superclass chain that use inheritance
  /// based naming, including the ones allocated for this scope.
  int get inheritanceBasedFieldNameCounter => _fieldNameCounter;

  /// The number of locally used fields. Depending on the naming source
  /// (e.g. inheritance based or globally unique for mixixns) this
  /// might be different from [inheritanceBasedFieldNameCounter].
  int get _localFieldNameCounter => _fieldNameCounter;
  void set _localFieldNameCounter(int val) { _fieldNameCounter = val; }

  factory _FieldNamingScope.forClass(ClassElement cls, ClassWorld world,
      _FieldNamingRegistry registry) {
    _FieldNamingScope result = registry.scopes[cls];
    if (result != null) return result;

    if (world.isUsedAsMixin(cls)) {
      result = new _MixinFieldNamingScope.mixin(cls, registry);
    } else {
      if (cls.superclass == null) {
        result = new _FieldNamingScope.rootScope(cls, registry);
      } else {
        _FieldNamingScope superScope = new _FieldNamingScope.forClass(
            cls.superclass, world, registry);
        if (cls.isMixinApplication) {
          result = new _MixinFieldNamingScope.mixedIn(cls, superScope,
              registry);
        } else {
          result = new _FieldNamingScope.inherit(cls, superScope, registry);
        }
      }
    }

    cls.forEachInstanceField((cls, field) => result.add(field));

    registry.scopes[cls] = result;
    return result;
  }

  factory _FieldNamingScope.forBox(Local box, _FieldNamingRegistry registry) {
    return registry.scopes.putIfAbsent(box,
        () => new _BoxFieldNamingScope(box, registry));
  }

  _FieldNamingScope.rootScope(this.container, this.registry)
    : superScope = null,
      _fieldNameCounter = 0;

  _FieldNamingScope.inherit(this.container, this.superScope, this.registry) {
    _fieldNameCounter = superScope.inheritanceBasedFieldNameCounter;
  }

  /**
   * Checks whether [name] is already used in the current scope chain.
   */
  _isNameUnused(String name) {
    return !names.values.contains(name) &&
        ((superScope == null) || superScope._isNameUnused(name));
  }

  String _nextName() => registry.getName(_localFieldNameCounter++);

  String operator[](Element field) {
    String name = names[field];
    if (name == null && superScope != null) return superScope[field];
    return name;
  }

  void add(Element field) {
    if (names.containsKey(field)) return;

    String value = _nextName();
    assert(invariant(field, _isNameUnused(value)));
    names[field] = value;
  }

  bool containsField(Element field) => names.containsKey(field);
}

/**
 * Field names for mixins have two constraints: They need to be unique in the
 * hierarchy of each application of a mixin and they need to be the same for
 * all applications of a mixin. To achieve this, we use global naming for
 * mixins from the same name pool as fields and add a `$` at the end to ensure
 * they do not collide with normal field names. The `$` sign is typically used
 * as a separator between method names and argument counts and does not appear
 * in generated names themselves.
 */
class _MixinFieldNamingScope extends _FieldNamingScope {
  int get _localFieldNameCounter => registry.globalCount;
  void set _localFieldNameCounter(int val) { registry.globalCount = val; }

  Map<Entity, String> get names => registry.globalNames;

  _MixinFieldNamingScope.mixin(ClassElement cls, _FieldNamingRegistry registry)
    : super.rootScope(cls, registry);

  _MixinFieldNamingScope.mixedIn(MixinApplicationElement container,
      _FieldNamingScope superScope, _FieldNamingRegistry registry)
    : super.inherit(container, superScope, registry);

  String _nextName() {
    var proposed = super._nextName();
    return proposed + r'$';
  }
}

/**
 * [BoxFieldElement] fields work differently in that they do not belong to an
 * actual class but an anonymous box associated to a [Local]. As there is no
 * inheritance chain, we do not need to compute fields a priori but can assign
 * names on the fly.
 */
class _BoxFieldNamingScope extends _FieldNamingScope {
  _BoxFieldNamingScope(Local box, _FieldNamingRegistry registry) :
    super.rootScope(box, registry);

  bool containsField(_) => true;

  String operator[](Element field) {
    if (!names.containsKey(field)) add(field);
    return names[field];
  }
}