Add a new implementation of HashMap that uses JS objects for its (multiple) hash tables.

sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart

Index: sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
diff --git a/sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart b/sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
new file mode 100644
index 0000000000000000000000000000000000000000..10a95131ae15b6596019b9511d0bb8205bdb8380
--- /dev/null
+++ b/sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart
@@ -0,0 +1,315 @@
+// Copyright (c) 2013, 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.
+
+// Patch file for dart:collection classes.
+import 'dart:_foreign_helper' show JS;
+
+patch class HashMap<K, V> {
+  // BUG(9368): We're currently unable to pass the type arguments to
+  // the construction of the JSMap instance.
+  patch factory HashMap() => new JSMap();
+}
+
+class JSMap<K, V> implements HashMap<K, V> {
+  int _length = 0;
+  var _strings, _nums, _rest;

[ahe, 2013/03/22 16:18:31]

Each of these should be on their own line, and each deserve a comment.

+  List _keys;
+
+  int get length => _length;
+  bool get isEmpty => _length == 0;
+
+  Iterable<K> get keys {
+    return new JSMapKeyIterable<K>(this);
+  }
+
+  Iterable<V> get values {
+    return keys.map((each) => this[each]);
+  }
+
+  bool containsKey(K key) {
+    if (key is String && key != '__proto__') {
+      var strings = _strings;

[ahe, 2013/03/22 16:18:31]

Would this work:

var strings = JS('JavaScriptIndexingBehavior', '#', _strings);
return (strings != null) && strings[key] != null;

+      if (strings == null) return false;
+      var probe = JS('var', '#[#]', strings, key);
+      return JS('bool', '# != null', probe);

[ahe, 2013/03/22 16:18:31]

Why not simply:

return probe != null;

+    } else if (key is num) {
+      var nums = _nums;
+      if (nums == null) return false;
+      var probe = JS('var', '#[#]', nums, key);
+      return JS('bool', '# != null', probe);
+    } else {
+      var rest = _rest;
+      if (rest == null) return false;
+      var hash = key.hashCode;
+      var bucket = JS('var', '#[#]', rest, hash);

[ahe, 2013/03/22 16:18:31]

Do you know if open addressing would be better in this case?

+      if (bucket != null) {
+        int bucketLength = JS('int', '#.length', bucket);

[ahe, 2013/03/22 16:18:31]

Could you tell compiler that bucket is a List and avoid using JS here? It should
even hoist out the length check in that case, right?

+        for (int i = 0; i < bucketLength; i += 2) {
+          if (JS('var', '#[#]', bucket, i) == key) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+  }
+
+  bool containsValue(V value) {
+    return _computeKeys().any((each) => this[each] == value);

[ahe, 2013/03/22 16:18:31]

This looks slow.  Wouldn't this always be faster:

for (var key in _computeKeys()) {
  if (this[key] == value) return true;
}
return false;

+  }
+
+  V operator[](K key) {
+    if (key is String && key != '__proto__') {
+      var strings = _strings;
+      if (strings == null) return null;
+      var probe = JS('var', '#[#]', strings, key);
+      return JS('bool', '# === #', probe, strings) ? null : probe;

[ahe, 2013/03/22 16:18:31]

You're using _strings as a sentinel object?  Comment would be nice.

+    } else if (key is num) {
+      var nums = _nums;
+      if (nums == null) return null;
+      var probe = JS('var', '#[#]', nums, key);
+      return JS('bool', '# === #', probe, nums) ? null : probe;
+    } else {
+      var rest = _rest;
+      if (rest == null) return null;
+      var hash = JS('num', 'Number(#)', key.hashCode);

[ahe, 2013/03/22 16:18:31]

Shouldn't you throw some kind of exception if hashCode isn't an int?

+      var bucket = JS('var', '#[#]', rest, hash);
+      if (bucket != null) {
+        int bucketLength = JS('int', '#.length', bucket);
+        for (int i = 0; i < bucketLength; i += 2) {
+          if (JS('var', '#[#]', bucket, i) == key) {
+            return JS('var', '#[# + 1]', bucket, i);
+          }
+        }
+      }
+      return null;
+    }
+  }
+
+  void operator[]=(K key, V value) {
+    if (key is String && key != '__proto__') {
+      var strings = _strings;
+      if (strings == null) {
+        _strings = strings = _newHashTable();
+        _length++;
+        _keys = null;

[ahe, 2013/03/22 16:18:31]

This might be more readable:

addedNewKey = true;

And then at the end of this method:

if (addedNewKey) {
  _keys = null;
}

+      } else if (JS('bool', '#[#] == null', strings, key)) {
+        _length++;
+        _keys = null;
+      }
+      if (value == null) value = strings;
+      JS('void', '#[#] = #', strings, key, value);
+    } else if (key is num) {
+      var nums = _nums;
+      if (nums == null) {
+        _nums = nums = _newHashTable();
+        _length++;
+        _keys = null;
+      } else if (JS('bool', '#[#] == null', nums, key)) {
+        _length++;
+        _keys = null;
+      }
+      if (value == null) value = nums;
+      JS('void', '#[#] = #', nums, key, value);
+    } else {
+      var rest = _rest;
+      var hash = JS('num', 'Number(#)', key.hashCode);

[ahe, 2013/03/22 16:18:31]

Exception?

+      var bucket;
+      if (rest == null) {
+        _rest = rest = _newHashTable();
+      } else {
+        bucket = JS('var', '#[#]', rest, hash);
+      }
+      if (bucket == null) {
+        JS('void', '#[#] = [#, #]', rest, hash, key, value);
+        _length++;
+        _keys = null;
+      } else {
+        int bucketLength = JS('int', '#.length', bucket);
+        for (int i = 0; i < bucketLength; i += 2) {
+          if (JS('var', '#[#]', bucket, i) == key) {
+            JS('void', '#[# + 1] = #', bucket, i, value);
+            return;
+          }
+        }
+        JS('void', '#.push(#, #)', bucket, key, value);
+        _length++;
+        _keys = null;
+      }
+    }
+  }
+
+  V remove(K key) {
+    if (key is String && key != '__proto__') {
+      var strings = _strings;
+      if (strings == null) return null;
+      var probe = JS('var', '#[#]', strings, key);
+      if (probe == null) return null;
+      JS('void', 'delete #[#]', strings, key);
+      _length--;
+      _keys = null;
+      return JS('bool', '# === #', probe, strings) ? null : probe;
+    } else if (key is num) {
+      var nums = _nums;
+      if (nums == null) return null;
+      var probe = JS('var', '#[#]', nums, key);
+      if (probe == null) return null;
+      JS('void', 'delete #[#]', nums, key);
+      _length--;
+      _keys = null;
+      return JS('bool', '# === #', probe, nums) ? null : probe;
+    } else {
+      var rest = _rest;
+      if (rest == null) return null;
+      var hash = JS('num', 'Number(#)', key.hashCode);
+      var bucket = JS('var', '#[#]', rest, hash);
+      if (bucket == null) return null;
+      int bucketLength = JS('int', '#.length', bucket);
+      for (int i = 0; i < bucketLength; i += 2) {
+        if (JS('var', '#[#]', bucket, i) == key) {
+          var value = JS('var', '#[# + 1]', bucket, i);
+          int last = bucketLength - 2;
+          if (i != last) {
+            JS('void', '#[#] = #[#]', bucket, i, bucket, last);
+            JS('void', '#[# + 1] = #[# + 1]', bucket, i, bucket, last);
+          }
+          JS('void', '#.length = #', bucket, last);
+          _length--;
+          _keys = null;
+          return value;
+        }
+      }
+      return null;
+    }
+  }
+
+  void clear() {
+    if (_length > 0) {
+      _strings = _nums = _rest = _keys = null;
+      _length = 0;
+    }
+  }
+
+  void forEach(void f(K key, V value)) {
+    List keys = _computeKeys();
+    for (int i = 0, length = keys.length; i < length; i++) {
+      var key = keys[i];
+      f(key, this[key]);
+      if (!identical(keys, _keys)) {
+        throw new ConcurrentModificationError(this);

[ahe, 2013/03/22 16:18:31]

This means there are situations where a concurrent modification occurs, but you
allow it.  For example, you may replace values for existing keys.  This is fine
by me, but rather hard to specify correctly, so I hope the specification is
clear about this.

+      }
+    }
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    if (containsKey(key)) return this[key];
+    V value = ifAbsent();
+    this[key] = value;
+    return value;
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((K key, V value) {
+      this[key] = value;
+    });
+  }
+
+  String toString() => Maps.mapToString(this);
+
+  List _computeKeys() {
+    if (_keys != null) return _keys;
+
+    List result = new List(_length);
+    int index = 0;
+    var strings = _strings;
+    if (strings != null) {
+      var names = JS('var', 'Object.getOwnPropertyNames(#)', strings);

[ahe, 2013/03/22 16:18:31]

There is a comment in the emitter about an Opera bug for this method.  Is it
safe to use now?

[ahe, 2013/03/22 16:18:31]

If the type of the JS expression is '=List' can't you just use plain Dart code
for the rest?

+      int length = JS('int', '#.length', names);
+      for (int i = 0; i < length; i++) {
+        String key = JS('String', '#[#]', names, i);
+        result[index++] = key;
+      }
+    }
+
+    var nums = _nums;
+    if (_nums != null) {
+      var names = JS('var', 'Object.getOwnPropertyNames(#)', nums);

[ahe, 2013/03/22 16:18:31]

Use =List?

+      int length = JS('int', '#.length', names);
+      for (int i = 0; i < length; i++) {
+        num key = JS('num', 'Number(#[#])', names, i);

[ahe, 2013/03/22 16:18:31]

A comment explaining why Number is necessary would be great.

+        result[index++] = key;
+      }
+    }
+
+    var rest = _rest;
+    if (rest != null) {
+      var names = JS('var', 'Object.getOwnPropertyNames(#)', rest);

[ahe, 2013/03/22 16:18:31]

Use =List?

+      int length = JS('int', '#.length', names);
+      for (int i = 0; i < length; i++) {
+        var key = JS('String', '#[#]', names, i);
+        var bucket = JS('var', '#[#]', rest, key);
+        int bucketLength = JS('int', '#.length', bucket);
+        for (int i = 0; i < bucketLength; i += 2) {
+          var key = JS('var', '#[#]', bucket, i);
+          result[index++] = key;
+        }
+      }
+    }
+    return _keys = result;
+  }
+
+  _newHashTable() {
+    var table = JS('var', 'Object.create(null)');
+    var temporaryKey = '<non-identifier-key>';
+    JS('void', '#[#] = #', table, temporaryKey, table);
+    JS('void', 'delete #[#]', table, temporaryKey);

[ahe, 2013/03/22 16:18:31]

Add a comment explaining the purpose of <non-identifier-key> and delete.  I
think it looks like black magic to people that aren't intimately familiar with
map transitions in V8.

+    return table;
+  }
+}
+
+
+class JSMapKeyIterable<E> extends Iterable<E> {
+  final JSMap _map;
+  JSMapKeyIterable(this._map);
+
+  int get length => _map._length;
+  bool get isEmpty => _map._length == 0;
+
+  Iterator<E> get iterator {
+    return new JSMapKeyIterator<E>(_map, _map._computeKeys());
+  }
+
+  void forEach(void f(E element)) {
+    List keys = _map._computeKeys();
+    for (int i = 0, length = keys.length; i < length; i++) {
+      f(keys[i]);
+      if (!identical(keys, _map._keys)) {
+        throw new ConcurrentModificationError(_map);
+      }
+    }
+  }
+}
+
+class JSMapKeyIterator<E> implements Iterator<E> {
+  final JSMap _map;
+  final List _keys;
+  int _offset = 0;
+  E _current;
+
+  JSMapKeyIterator(this._map, this._keys);
+
+  E get current => _current;
+
+  bool moveNext() {
+    if (!identical(_keys, _map._keys)) {
+      throw new ConcurrentModificationError(_map);
+    } else if (_offset >= _keys.length) {
+      _current = null;
+      return false;
+    } else {
+      _current = _keys[_offset++];
+      return true;
+    }
+  }
+}