Share the JavaScript based LinkedHashMap implementation between constant maps and the LinkedHashMap…

sdk/lib/_internal/compiler/js_lib/linked_hash_map.dart

+// Copyright (c) 2014, 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.
+
+// Efficient JavaScript based implementation of a linked hash map used as a
+// backing map for constant maps and the [LinkedHashMap] patch
+
+part of _js_helper;
+
+class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap {
+  int _length = 0;
+
+  // The hash map contents are divided into three parts: one part for
+  // string keys, one for numeric keys, and one for the rest. String
+  // and numeric keys map directly to their linked cells, but the rest
+  // of the entries are stored in bucket lists of the form:
+  //
+  //    [cell-0, cell-1, ...]
+  //
+  // where all keys in the same bucket share the same hash code.
+  var _strings;
+  var _nums;
+  var _rest;
+
+  // The keys and values are stored in cells that are linked together
+  // to form a double linked list.
+  LinkedHashMapCell _first;
+  LinkedHashMapCell _last;
+
+  // We track the number of modifications done to the key set of the
+  // hash map to be able to throw when the map is modified while being
+  // iterated over.
+  int _modifications = 0;
+
+  JsLinkedHashMap();
+
+
+  int get length => _length;
+  bool get isEmpty => _length == 0;
+  bool get isNotEmpty => !isEmpty;
+
+  Iterable<K> get keys {
+    return new LinkedHashMapKeyIterable<K>(this);
+  }
+
+  Iterable<V> get values {
+    return new MappedIterable<K, V>(keys, (each) => this[each]);
+  }
+
+  bool containsKey(Object key) {
+    if (_isStringKey(key)) {
+      var strings = _strings;
+      if (strings == null) return false;
+      LinkedHashMapCell cell = _getTableEntry(strings, key);
+      return cell != null;
+    } else if (_isNumericKey(key)) {
+      var nums = _nums;
+      if (nums == null) return false;
+      LinkedHashMapCell cell = _getTableEntry(nums, key);
+      return cell != null;
+    } else {
+      return internalContainsKey(key);
+    }
+  }
+
+  bool internalContainsKey(Object key) {
+    var rest = _rest;
+    if (rest == null) return false;
+    var bucket = _getBucket(rest, key);
+    return internalFindBucketIndex(bucket, key) >= 0;
+  }
+
+  bool containsValue(Object value) {
+    return keys.any((each) => this[each] == value);
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((K key, V value) {
+      this[key] = value;
+    });
+  }
+
+  V operator[](Object key) {
+    if (_isStringKey(key)) {
+      var strings = _strings;
+      if (strings == null) return null;
+      LinkedHashMapCell cell = _getTableEntry(strings, key);
+      return (cell == null) ? null : cell.value;
+    } else if (_isNumericKey(key)) {
+      var nums = _nums;
+      if (nums == null) return null;
+      LinkedHashMapCell cell = _getTableEntry(nums, key);
+      return (cell == null) ? null : cell.value;
+    } else {
+      return internalGet(key);
+    }
+  }
+
+  V internalGet(Object key) {
+    var rest = _rest;
+    if (rest == null) return null;
+    var bucket = _getBucket(rest, key);
+    int index = internalFindBucketIndex(bucket, key);
+    if (index < 0) return null;
+    LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
+    return cell.value;
+  }
+
+  void operator[]=(K key, V value) {
+    if (_isStringKey(key)) {
+      var strings = _strings;
+      if (strings == null) _strings = strings = _newHashTable();
+      _addHashTableEntry(strings, key, value);
+    } else if (_isNumericKey(key)) {
+      var nums = _nums;
+      if (nums == null) _nums = nums = _newHashTable();
+      _addHashTableEntry(nums, key, value);
+    } else {
+      internalSet(key, value);
+    }
+  }
+
+  void internalSet(K key, V value) {
+    var rest = _rest;
+    if (rest == null) _rest = rest = _newHashTable();
+    var hash = internalComputeHashCode(key);
+    var bucket = JS('var', '#[#]', rest, hash);
+    if (bucket == null) {
+      LinkedHashMapCell cell = _newLinkedCell(key, value);
+      _setTableEntry(rest, hash, JS('var', '[#]', cell));
+    } else {
+      int index = internalFindBucketIndex(bucket, key);
+      if (index >= 0) {
+        LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
+        cell.value = value;
+      } else {
+        LinkedHashMapCell cell = _newLinkedCell(key, value);
+        JS('void', '#.push(#)', bucket, cell);
+      }
+    }
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    if (containsKey(key)) return this[key];
+    V value = ifAbsent();
+    this[key] = value;
+    return value;
+  }
+
+  V remove(Object key) {
+    if (_isStringKey(key)) {
+      return _removeHashTableEntry(_strings, key);
+    } else if (_isNumericKey(key)) {
+      return _removeHashTableEntry(_nums, key);
+    } else {
+      return internalRemove(key);
+    }
+  }
+
+  V internalRemove(Object key) {
+    var rest = _rest;
+    if (rest == null) return null;
+    var bucket = _getBucket(rest, key);
+    int index = internalFindBucketIndex(bucket, key);
+    if (index < 0) return null;
+    // Use splice to remove the [cell] element at the index and
+    // unlink the cell before returning its value.
+    LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index);
+    _unlinkCell(cell);
+    // TODO(kasperl): Consider getting rid of the bucket list when
+    // the length reaches zero.
+    return cell.value;
+  }
+
+  void clear() {
+    if (_length > 0) {
+      _strings = _nums = _rest = _first = _last = null;
+      _length = 0;
+      _modified();
+    }
+  }
+
+  void forEach(void action(K key, V value)) {
+    LinkedHashMapCell cell = _first;
+    int modifications = _modifications;
+    while (cell != null) {
+      action(cell.key, cell.value);
+      if (modifications != _modifications) {
+        throw new ConcurrentModificationError(this);
+      }
+      cell = cell._next;
+    }
+  }
+
+  void _addHashTableEntry(var table, K key, V value) {
+    LinkedHashMapCell cell = _getTableEntry(table, key);
+    if (cell == null) {
+      _setTableEntry(table, key, _newLinkedCell(key, value));
+    } else {
+      cell.value = value;
+    }
+  }
+
+  V _removeHashTableEntry(var table, Object key) {
+    if (table == null) return null;
+    LinkedHashMapCell cell = _getTableEntry(table, key);
+    if (cell == null) return null;
+    _unlinkCell(cell);
+    _deleteTableEntry(table, key);
+    return cell.value;
+  }
+
+  void _modified() {
+    // Value cycles after 2^30 modifications. If you keep hold of an
+    // iterator for that long, you might miss a modification
+    // detection, and iteration can go sour. Don't do that.
+    _modifications = (_modifications + 1) & 0x3ffffff;
+  }
+
+  // Create a new cell and link it in as the last one in the list.
+  LinkedHashMapCell _newLinkedCell(K key, V value) {
+    LinkedHashMapCell cell = new LinkedHashMapCell(key, value);
+    if (_first == null) {
+      _first = _last = cell;
+    } else {
+      LinkedHashMapCell last = _last;
+      cell._previous = last;
+      _last = last._next = cell;
+    }
+    _length++;
+    _modified();
+    return cell;
+  }
+
+  // Unlink the given cell from the linked list of cells.
+  void _unlinkCell(LinkedHashMapCell cell) {
+    LinkedHashMapCell previous = cell._previous;
+    LinkedHashMapCell next = cell._next;
+    if (previous == null) {
+      assert(cell == _first);
+      _first = next;
+    } else {
+      previous._next = next;
+    }
+    if (next == null) {
+      assert(cell == _last);
+      _last = previous;
+    } else {
+      next._previous = previous;
+    }
+    _length--;
+    _modified();
+  }
+
+  static bool _isStringKey(var key) {
+    return key is String && key != '__proto__';
+  }
+
+  static bool _isNumericKey(var key) {
+    // Only treat unsigned 30-bit integers as numeric keys. This way,
+    // we avoid converting them to strings when we use them as keys in
+    // the JavaScript hash table object.
+    return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key);
+  }
+
+  int internalComputeHashCode(var key) {
+    // We force the hash codes to be unsigned 30-bit integers to avoid
+    // issues with problematic keys like '__proto__'. Another option
+    // would be to throw an exception if the hash code isn't a number.
+    return JS('int', '# & 0x3ffffff', key.hashCode);
+  }
+
+  static _getTableEntry(var table, var key) {
+    return JS('var', '#[#]', table, key);
+  }
+
+  static void _setTableEntry(var table, var key, var value) {
+    assert(value != null);
+    JS('void', '#[#] = #', table, key, value);
+  }
+
+  static void _deleteTableEntry(var table, var key) {
+    JS('void', 'delete #[#]', table, key);
+  }
+
+  List _getBucket(var table, var key) {
+    var hash = internalComputeHashCode(key);
+    return JS('var', '#[#]', table, hash);
+  }
+
+  int internalFindBucketIndex(var bucket, var key) {
+    if (bucket == null) return -1;
+    int length = JS('int', '#.length', bucket);
+    for (int i = 0; i < length; i++) {
+      LinkedHashMapCell cell = JS('var', '#[#]', bucket, i);
+      if (cell.key == key) return i;
+    }
+    return -1;
+  }
+
+  static _newHashTable() {
+    // Create a new JavaScript object to be used as a hash table. Use
+    // Object.create to avoid the properties on Object.prototype
+    // showing up as entries.
+    var table = JS('var', 'Object.create(null)');
+    // Attempt to force the hash table into 'dictionary' mode by
+    // adding a property to it and deleting it again.
+    var temporaryKey = '<non-identifier-key>';
+    _setTableEntry(table, temporaryKey, table);
+    _deleteTableEntry(table, temporaryKey);
+    return table;
+  }
+
+  String toString() => Maps.mapToString(this);
+}
+
+class LinkedHashMapCell {
+  final key;
+  var value;
+
+  LinkedHashMapCell _next;
+  LinkedHashMapCell _previous;
+
+  LinkedHashMapCell(this.key, this.value);
+}
+
+class LinkedHashMapKeyIterable<E> extends IterableBase<E>
+                                  implements EfficientLength {
+  final _map;
+  LinkedHashMapKeyIterable(this._map);
+
+  int get length => _map._length;
+  bool get isEmpty => _map._length == 0;
+
+  Iterator<E> get iterator {
+    return new LinkedHashMapKeyIterator<E>(_map, _map._modifications);
+  }
+
+  bool contains(Object element) {
+    return _map.containsKey(element);
+  }
+
+  void forEach(void f(E element)) {
+    LinkedHashMapCell cell = _map._first;
+    int modifications = _map._modifications;
+    while (cell != null) {
+      f(cell.key);
+      if (modifications != _map._modifications) {
+        throw new ConcurrentModificationError(_map);
+      }
+      cell = cell._next;
+    }
+  }
+}
+
+class LinkedHashMapKeyIterator<E> implements Iterator<E> {
+  final _map;
+  final int _modifications;
+  LinkedHashMapCell _cell;
+  E _current;
+
+  LinkedHashMapKeyIterator(this._map, this._modifications) {
+    _cell = _map._first;
+  }
+
+  E get current => _current;
+
+  bool moveNext() {
+    if (_modifications != _map._modifications) {
+      throw new ConcurrentModificationError(_map);
+    } else if (_cell == null) {
+      _current = null;
+      return false;
+    } else {
+      _current = _cell.key;
+      _cell = _cell._next;
+      return true;
+    }
+  }
+}