Replace Linked{Identity,Custom}Hash{Map,Set} with compact implementation; remove old code and flag.

runtime/lib/compact_hash.dart

 // Copyright (c) 2015, 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.
 
 import 'dart:typed_data';
 
 // Hash table with open addressing that separates the index from keys/values.
 abstract class _HashBase {
   // Each occupied entry in _index is a fixed-size integer that encodes a pair:
   //   [ hash pattern for key | index of entry in _data ]
@@ skipping 50 matching lines @@
     data[d] = data;
   }
 
   // Concurrent modification detection relies on this checksum monotonically
   // increasing between reallocations of _data.
   int get _checkSum => _usedData + _deletedKeys;
   bool _isModifiedSince(List oldData, int oldCheckSum) =>
       !identical(_data, oldData) || (_checkSum != oldCheckSum);
 }
 
+abstract class _OperatorEqualsAndHashCode {

[Ivan Posva, 2015/03/05 20:45:34]

Why "abstract"?

+  int _hashCode(e) => e.hashCode;
+  bool _equals(e1, e2) => e1 == e2;
+}
+
+abstract class _IdenticalAndIdentityHashCode {
+  int _hashCode(e) => identityHashCode(e);
+  bool _equals(e1, e2) => identical(e1, e2);
+}
+
 // Map with iteration in insertion order (hence "Linked"). New keys are simply
 // appended to _data.
 class _CompactLinkedHashMap<K, V>
-    extends MapBase<K, V> with _HashBase
+    extends MapBase<K, V> with _HashBase, _OperatorEqualsAndHashCode
     implements HashMap<K, V>, LinkedHashMap<K, V> {

[Ivan Posva, 2015/03/05 20:45:34]

I think you can drop the "HashMap<K,V>" from the implements as this is implied
by LinkedHashMap.

 
   _CompactLinkedHashMap() {
     assert(_HashBase._UNUSED_PAIR == 0);
     _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE);
     _data = new List(_HashBase._INITIAL_INDEX_SIZE);
   }
   
   int get length => (_usedData >> 1) - _deletedKeys;
   bool get isEmpty => length == 0;
   bool get isNotEmpty => !isEmpty;
@@ skipping 59 matching lines @@
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair == _HashBase._DELETED_PAIR) {
         if (firstDeleted < 0){
           firstDeleted = i;
         }
       } else {
         final int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (key == _data[d]) {
+          if (_equals(key, _data[d])) {
             return d + 1;
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return firstDeleted >= 0 ? -firstDeleted : -i;
   }
   
   void operator[]=(K key, V value) {
     final int size = _index.length;
     final int sizeMask = size - 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
     if (d > 0) {
       _data[d] = value;
     } else {
       final int i = -d;
       _insert(key, value, hashPattern, i);
     }
   }
   
   V putIfAbsent(K key, V ifAbsent()) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
     if (d > 0) {
       return _data[d];
     }
     // 'ifAbsent' is allowed to modify the map.
     List oldData = _data;
     int oldCheckSum = _checkSum;
     V value = ifAbsent();
     if (_isModifiedSince(oldData, oldCheckSum)) {
       this[key] = value;
     } else {
       final int i = -d;
       _insert(key, value, hashPattern, i);
     }
     return value;
   }
   
   V remove(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair != _HashBase._DELETED_PAIR) {
         final int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (key == _data[d]) {
+          if (_equals(key, _data[d])) {
             _index[i] = _HashBase._DELETED_PAIR;
             _HashBase._setDeletedAt(_data, d);
             V value = _data[d + 1];
             _HashBase._setDeletedAt(_data, d + 1);
             ++_deletedKeys;
             return value;
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return null;
   }
   
   // If key is absent, return _data (which is never a value).
   Object _getValueOrData(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair != _HashBase._DELETED_PAIR) {
         final int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (key == _data[d]) {
+          if (_equals(key, _data[d])) {
             return _data[d + 1];
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return _data;
   }
   
   bool containsKey(Object key) => !identical(_data, _getValueOrData(key));
   
   V operator[](Object key) {
     var v = _getValueOrData(key);
     return identical(_data, v) ? null : v;
   }
   
   bool containsValue(Object value) {
     for (var v in values) {
+      // Spec. says this should always use "==", also for identity maps, etc.
       if (v == value) {
         return true;
       }
     }
     return false;
   }
 
   void forEach(void f(K key, V value)) {
     var ki = keys.iterator;
     var vi = values.iterator;
     while (ki.moveNext()) {
       vi.moveNext();
       f(ki.current, vi.current);
     }
   }
 
   Iterable<K> get keys =>
       new _CompactIterable<K>(this, _data, _usedData, -2, 2);
   Iterable<V> get values =>
       new _CompactIterable<V>(this, _data, _usedData, -1, 2);
 }
 
+class _CompactLinkedIdentityHashMap<K, V>
+    extends _CompactLinkedHashMap<K, V> with _IdenticalAndIdentityHashCode {
+}
+
+class _CompactLinkedCustomHashMap<K, V>
+    extends _CompactLinkedHashMap<K, V> {
+  final _equality;
+  final _hasher;
+  final _validKey;
+
+  // TODO(koda): Ask gbracha why I cannot have fields _equals/_hashCode.
+  int _hashCode(e) => _hasher(e);
+  bool _equals(e1, e2) => _equality(e1, e2);
+      
+  bool containsKey(Object o) => _validKey(o) ? super.containsKey(o) : false;
+  V operator[](Object o) => _validKey(o) ? super[o] : null;
+  V remove(Object o) => _validKey(o) ? super.remove(o) : null;
+
+  _CompactLinkedCustomHashMap(this._equality, this._hasher, validKey)
+      : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test;
+}
+      
 // Iterates through _data[_offset + _step], _data[_offset + 2*_step], ...
 // and checks for concurrent modification.
 class _CompactIterable<E> extends IterableBase<E> {
   final _table;
   final List _data;
   final int _len;
   final int _offset;
   final int _step;
 
   _CompactIterable(this._table, this._data, this._len,
@@ skipping 30 matching lines @@
       current = _data[_offset];
       return true;
     } else {
       current = null;
       return false;
     }
   }
 }
 
 // Set implementation, analogous to _CompactLinkedHashMap.
-class _CompactLinkedHashSet<K>
-    extends SetBase<K> with _HashBase
-    implements LinkedHashSet<K> {
+class _CompactLinkedHashSet<E>
+    extends SetBase<E> with _HashBase, _OperatorEqualsAndHashCode
+    implements LinkedHashSet<E> {
 
   _CompactLinkedHashSet() {
     assert(_HashBase._UNUSED_PAIR == 0);
     _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE);
     _data = new List(_HashBase._INITIAL_INDEX_SIZE >> 1);
   }
 
   int get length => _usedData - _deletedKeys;
 
   void _rehash() {
@@ skipping 19 matching lines @@
     if (oldData != null) {
       for (int i = 0; i < oldUsed; i += 1) {
         var key = oldData[i];
         if (!_HashBase._isDeleted(oldData, key)) {
           add(key);
         }
       }
     }
   }
 
-  bool add(K key) {
+  bool add(E key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int firstDeleted = -1;
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair == _HashBase._DELETED_PAIR) {
         if (firstDeleted < 0){
           firstDeleted = i;
         }
       } else {
         final int d = hashPattern ^ pair;
-        if (d < maxEntries && key == _data[d]) {
+        if (d < maxEntries && _equals(key, _data[d])) {
           return false;
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     if (_usedData == _data.length) {
       _rehash();
       add(key);
     } else {
       final int insertionPoint = (firstDeleted >= 0) ? firstDeleted : i;
       assert(1 <= hashPattern && hashPattern < (1 << 32));
       assert((hashPattern & _usedData) == 0);
       _index[insertionPoint] = hashPattern | _usedData;
       _data[_usedData++] = key;
     }
     return true;
   }
   
   // If key is absent, return _data (which is never a value).
   Object _getKeyOrData(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair != _HashBase._DELETED_PAIR) {
         final int d = hashPattern ^ pair;
-        if (d < maxEntries && key == _data[d]) {
+        if (d < maxEntries && _equals(key, _data[d])) {
           return _data[d];  // Note: Must return the existing key.
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return _data;    
   }
 
-  K lookup(Object key) {
+  E lookup(Object key) {
     var k = _getKeyOrData(key);
     return identical(_data, k) ? null : k;
   }
   
   bool contains(Object key) => !identical(_data, _getKeyOrData(key));
 
   bool remove(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
-    final int fullHash = key.hashCode;
+    final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair != _HashBase._DELETED_PAIR) {
         final int d = hashPattern ^ pair;
-        if (d < maxEntries && key == _data[d]) {
+        if (d < maxEntries && _equals(key, _data[d])) {
           _index[i] = _HashBase._DELETED_PAIR;
           _HashBase._setDeletedAt(_data, d);
           ++_deletedKeys;
           return true;
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return false;
   }
                                                 
-  Iterator<K> get iterator =>
-      new _CompactIterator<K>(this, _data, _usedData, -1, 1);
+  Iterator<E> get iterator =>
+      new _CompactIterator<E>(this, _data, _usedData, -1, 1);
 
-  Set<K> toSet() => new Set<K>()..addAll(this);  
+  // Returns a set of the same type, although this
+  // is not required by the spec. (For instance, always using an identity set
+  // would be technically correct, albeit surprising.)
+  Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this);
 }
+    
+class _CompactLinkedIdentityHashSet<E>
+    extends _CompactLinkedHashSet<E> with _IdenticalAndIdentityHashCode {
+  Set<E> toSet() => new _CompactLinkedIdentityHashSet<E>()..addAll(this);
+}
+    
+class _CompactLinkedCustomHashSet<E>
+    extends _CompactLinkedHashSet<E> {
+  final _equality;
+  final _hasher;
+  final _validKey;
+
+  int _hashCode(e) => _hasher(e);
+  bool _equals(e1, e2) => _equality(e1, e2);
+  
+  bool contains(Object o) => _validKey(o) ? super.contains(o) : false;
+  E lookup(Object o) => _validKey(o) ? super.lookup(o) : null;
+  bool remove(Object o) => _validKey(o) ? super.remove(o) : false;
+
+  _CompactLinkedCustomHashSet(this._equality, this._hasher, validKey)
+      : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test;
+
+  Set<E> toSet() =>
+      new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey)
+          ..addAll(this);
+}