Reapply "Add custom equals and hashCode for HashMap implementation."

runtime/lib/collection_patch.dart

Index: runtime/lib/collection_patch.dart
diff --git a/runtime/lib/collection_patch.dart b/runtime/lib/collection_patch.dart
index 5bd4ab93657d4ff5f096a3ecdd303661da79e104..3b3bcc089f41ee5237c695fff916420420072575 100644
--- a/runtime/lib/collection_patch.dart
+++ b/runtime/lib/collection_patch.dart
@@ -3,23 +3,40 @@
 // BSD-style license that can be found in the LICENSE file.
 
 patch class HashMap<K, V> {
+  /* patch */ factory HashMap({ bool equals(K key1, K key2),
+                                int hashCode(K key) }) {
+    if (hashCode == null) {
+      if (equals == null) {
+        return new _HashMapImpl<K, V>();
+      }
+      if (identical(identical, equals)) {
+        return new _IdentityHashMap<K, V>();
+      }
+      hashCode = _defaultHashCode;
+    } else if (equals == null) {
+      equals = _defaultEquals;
+    }
+    return new _CustomHashMap<K, V>(equals, hashCode);
+  }
+}
+
+const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
+
+class _HashMapImpl<K, V> implements HashMap<K, V> {
   static const int _INITIAL_CAPACITY = 8;
-  static const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
 
   int _elementCount = 0;
   List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY);
   int _modificationCount = 0;
 
-  /* patch */ HashMap._internal();
-
-  /* patch */ int get length => _elementCount;
-  /* patch */ bool get isEmpty => _elementCount == 0;
-  /* patch */ bool get isNotEmpty => _elementCount != 0;
+  int get length => _elementCount;
+  bool get isEmpty => _elementCount == 0;
+  bool get isNotEmpty => _elementCount != 0;
 
-  /* patch */ Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
-  /* patch */ Iterable<V> get values => new _HashMapValueIterable<V>(this);
+  Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _HashMapValueIterable<V>(this);
 
-  /* patch */ bool containsKey(Object key) {
+  bool containsKey(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -31,7 +48,7 @@ patch class HashMap<K, V> {
     return false;
   }
 
-  /* patch */ bool containsValue(Object value) {
+  bool containsValue(Object value) {
     List buckets = _buckets;
     int length = buckets.length;
     for (int i = 0; i < length; i++) {
@@ -44,7 +61,7 @@ patch class HashMap<K, V> {
     return false;
   }
 
-  /* patch */ V operator[](Object key) {
+  V operator[](Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -58,7 +75,7 @@ patch class HashMap<K, V> {
     return null;
   }
 
-  /* patch */ void operator []=(K key, V value) {
+  void operator []=(K key, V value) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int length = buckets.length;
@@ -74,7 +91,7 @@ patch class HashMap<K, V> {
     _addEntry(buckets, index, length, key, value, hashCode);
   }
 
-  /* patch */ V putIfAbsent(K key, V ifAbsent()) {
+  V putIfAbsent(K key, V ifAbsent()) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int length = buckets.length;
@@ -96,13 +113,13 @@ patch class HashMap<K, V> {
     return value;
   }
 
-  /* patch */ void addAll(Map<K, V> other) {
+  void addAll(Map<K, V> other) {
     other.forEach((K key, V value) {
       this[key] = value;
     });
   }
 
-  /* patch */ void forEach(void action(K key, V value)) {
+  void forEach(void action(K key, V value)) {
     int stamp = _modificationCount;
     List buckets = _buckets;
     int length = buckets.length;
@@ -118,7 +135,7 @@ patch class HashMap<K, V> {
     }
   }
 
-  /* patch */ V remove(Object key) {
+  V remove(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -143,7 +160,7 @@ patch class HashMap<K, V> {
     return null;
   }
 
-  /* patch */ void clear() {
+  void clear() {
     _elementCount = 0;
     _buckets = new List(_INITIAL_CAPACITY);
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
@@ -180,8 +197,201 @@ patch class HashMap<K, V> {
     }
     _buckets = newBuckets;
   }
+
+  String toString() => Maps.mapToString(this);
 }
 
+class _CustomHashMap<K, V> extends _HashMapImpl<K, V> {
+  final _Equality<K> _equals;
+  final _Hasher<K> _hashCode;
+  _CustomHashMap(this._equals, this._hashCode);
+
+  bool containsKey(Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) return true;
+      entry = entry.next;
+    }
+    return false;
+  }
+
+  V operator[](Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        entry.value = value;
+        return;
+      }
+      entry = entry.next;
+    }
+    _addEntry(buckets, index, length, key, value, hashCode);
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    int stamp = _modificationCount;
+    V value = ifAbsent();
+    if (stamp == _modificationCount) {
+      _addEntry(buckets, index, length, key, value, hashCode);
+    } else {
+      this[key] = value;
+    }
+    return value;
+  }
+
+  V remove(Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    _HashMapEntry previous = null;
+    while (entry != null) {
+      _HashMapEntry next = entry.next;
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+
+  String toString() => Maps.mapToString(this);
+}
+
+class _IdentityHashMap<K, V> extends _HashMapImpl<K, V> {
+  bool containsKey(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && identical(entry.key, key)) return true;
+      entry = entry.next;
+    }
+    return false;
+  }
+
+  V operator[](Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && identical(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && identical(entry.key, key)) {
+        entry.value = value;
+        return;
+      }
+      entry = entry.next;
+    }
+    _addEntry(buckets, index, length, key, value, hashCode);
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && identical(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    int stamp = _modificationCount;
+    V value = ifAbsent();
+    if (stamp == _modificationCount) {
+      _addEntry(buckets, index, length, key, value, hashCode);
+    } else {
+      this[key] = value;
+    }
+    return value;
+  }
+
+  V remove(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    _HashMapEntry previous = null;
+    while (entry != null) {
+      _HashMapEntry next = entry.next;
+      if (hashCode == entry.hashCode && identical(entry.key, key)) {
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+
+  String toString() => Maps.mapToString(this);
+}
+
+
 class _HashMapEntry {
   final key;
   var value;