| // 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, JSExportName; |
| import 'dart:_runtime' as dart; |
| import 'dart:_interceptors' show JSArray; |
| import 'dart:_js_helper' |
| show |
| NoInline, |
| NoSideEffects, |
| NoThrows, |
| patch, |
| LinkedMap, |
| IdentityMap, |
| CustomHashMap, |
| CustomKeyHashMap, |
| DartIterator, |
| notNull, |
| putLinkedMapKey; |
| |
| @patch |
| class HashMap<K, V> { |
| @patch |
| factory HashMap( |
| {bool equals(K key1, K key2), |
| int hashCode(K key), |
| bool isValidKey(Object potentialKey)}) { |
| if (isValidKey == null) { |
| if (hashCode == null) { |
| if (equals == null) { |
| if (identical(K, String) || identical(K, int)) { |
| return IdentityMap<K, V>(); |
| } |
| return LinkedMap<K, V>(); |
| } |
| hashCode = dart.hashCode; |
| } else if (identical(identityHashCode, hashCode) && |
| identical(identical, equals)) { |
| return IdentityMap<K, V>(); |
| } |
| return CustomHashMap<K, V>(equals ?? dart.equals, hashCode); |
| } |
| return CustomKeyHashMap<K, V>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode, isValidKey); |
| } |
| |
| @patch |
| factory HashMap.identity() = IdentityMap<K, V>; |
| } |
| |
| @patch |
| class LinkedHashMap<K, V> { |
| @patch |
| factory LinkedHashMap( |
| {bool equals(K key1, K key2), |
| int hashCode(K key), |
| bool isValidKey(Object potentialKey)}) { |
| if (isValidKey == null) { |
| if (hashCode == null) { |
| if (equals == null) { |
| if (identical(K, String) || identical(K, int)) { |
| return IdentityMap<K, V>(); |
| } |
| return LinkedMap<K, V>(); |
| } |
| hashCode = dart.hashCode; |
| } else if (identical(identityHashCode, hashCode) && |
| identical(identical, equals)) { |
| return IdentityMap<K, V>(); |
| } |
| return CustomHashMap<K, V>(equals ?? dart.equals, hashCode); |
| } |
| return CustomKeyHashMap<K, V>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode, isValidKey); |
| } |
| |
| @patch |
| factory LinkedHashMap.identity() = IdentityMap<K, V>; |
| } |
| |
| @patch |
| class HashSet<E> { |
| @patch |
| factory HashSet( |
| {bool equals(E e1, E e2), |
| int hashCode(E e), |
| bool isValidKey(Object potentialKey)}) { |
| if (isValidKey == null) { |
| if (hashCode == null) { |
| if (equals == null) { |
| if (identical(E, String) || identical(E, int)) { |
| return _IdentityHashSet<E>(); |
| } |
| return _HashSet<E>(); |
| } |
| hashCode = dart.hashCode; |
| } else if (identical(identityHashCode, hashCode) && |
| identical(identical, equals)) { |
| return _IdentityHashSet<E>(); |
| } |
| return _CustomHashSet<E>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode); |
| } |
| return _CustomKeyHashSet<E>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode, isValidKey); |
| } |
| |
| @patch |
| factory HashSet.identity() = _IdentityHashSet<E>; |
| } |
| |
| @patch |
| class LinkedHashSet<E> { |
| @patch |
| factory LinkedHashSet( |
| {bool equals(E e1, E e2), |
| int hashCode(E e), |
| bool isValidKey(Object potentialKey)}) { |
| if (isValidKey == null) { |
| if (hashCode == null) { |
| if (equals == null) { |
| if (identical(E, String) || identical(E, int)) { |
| return _IdentityHashSet<E>(); |
| } |
| return _HashSet<E>(); |
| } |
| hashCode = dart.hashCode; |
| } else if (identical(identityHashCode, hashCode) && |
| identical(identical, equals)) { |
| return _IdentityHashSet<E>(); |
| } |
| return _CustomHashSet<E>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode); |
| } |
| return _CustomKeyHashSet<E>( |
| equals ?? dart.equals, hashCode ?? dart.hashCode, isValidKey); |
| } |
| |
| @patch |
| factory LinkedHashSet.identity() = _IdentityHashSet<E>; |
| } |
| |
| class _HashSet<E> extends _InternalSet<E> |
| implements HashSet<E>, LinkedHashSet<E> { |
| /// The backing store for this set. |
| /// |
| /// Keys that use identity equality are stored directly. For other types of |
| /// keys, we first look them up (by hashCode) in the [_keyMap] map, then |
| /// we lookup the key in this map. |
| @notNull |
| final _map = JS('', 'new Set()'); |
| |
| /// Items that use custom equality semantics. |
| /// |
| /// This maps from the item's hashCode to the canonical key, which is then |
| /// used to lookup the item in [_map]. Keeping the data in our primary backing |
| /// map gives us the ordering semantics requred by [LinkedHashMap], while |
| /// also providing convenient access to keys/values. |
| @notNull |
| final _keyMap = JS('', 'new Map()'); |
| |
| // 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. |
| // |
| // Value cycles after 2^30 modifications so that modification counts are |
| // always unboxed (Smi) values. Modification detection will be missed if you |
| // make exactly some multiple of 2^30 modifications between advances of an |
| // iterator. |
| @notNull |
| int _modifications = 0; |
| |
| _HashSet(); |
| |
| Set<E> _newSet() => _HashSet<E>(); |
| |
| Set<R> _newSimilarSet<R>() => _HashSet<R>(); |
| |
| bool contains(Object key) { |
| if (key == null) { |
| key = null; |
| } else if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| @notNull |
| var k = key; |
| var buckets = JS('', '#.get(# & 0x3ffffff)', _keyMap, k.hashCode); |
| if (buckets != null) { |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| k = JS('', '#[#]', buckets, i); |
| if (k == key) return true; |
| } |
| } |
| return false; |
| } |
| return JS('bool', '#.has(#)', _map, key); |
| } |
| |
| E lookup(Object key) { |
| if (key == null) return null; |
| if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| @notNull |
| var k = key; |
| var buckets = JS('', '#.get(# & 0x3ffffff)', _keyMap, k.hashCode); |
| if (buckets != null) { |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| k = JS('', '#[#]', buckets, i); |
| if (k == key) return JS('', '#', k); |
| } |
| } |
| return null; |
| } |
| return JS('', '#.has(#) ? # : null', _map, key, key); |
| } |
| |
| bool add(E key) { |
| var map = _map; |
| if (key == null) { |
| if (JS('', '#.has(null)', map)) return false; |
| key = null; |
| } else if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| var keyMap = _keyMap; |
| @notNull |
| var k = key; |
| int hash = JS('!', '# & 0x3ffffff', k.hashCode); |
| var buckets = JS('', '#.get(#)', keyMap, hash); |
| if (buckets == null) { |
| JS('', '#.set(#, [#])', keyMap, hash, key); |
| } else { |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| k = JS('', '#[#]', buckets, i); |
| if (k == key) return false; |
| } |
| JS('', '#.push(#)', buckets, key); |
| } |
| } else if (JS('', '#.has(#)', map, key)) { |
| return false; |
| } |
| JS('', '#.add(#)', map, key); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| |
| void addAll(Iterable<E> objects) { |
| var map = _map; |
| int length = JS('', '#.size', map); |
| for (E key in objects) { |
| if (key == null) { |
| key = null; // converts undefined to null, if needed. |
| } else if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| key = putLinkedMapKey(key, _keyMap); |
| } |
| JS('', '#.add(#)', map, key); |
| } |
| if (length != JS<int>('!', '#.size', map)) { |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| } |
| } |
| |
| bool remove(Object key) { |
| if (key == null) { |
| key = null; |
| } else if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| @notNull |
| var k = key; |
| int hash = JS('!', '# & 0x3ffffff', k.hashCode); |
| var buckets = JS('', '#.get(#)', _keyMap, hash); |
| if (buckets == null) return false; // not found |
| for (int i = 0, n = JS('!', '#.length', buckets);;) { |
| k = JS('', '#[#]', buckets, i); |
| if (k == key) { |
| key = k; |
| if (n == 1) { |
| JS('', '#.delete(#)', _keyMap, hash); |
| } else { |
| JS('', '#.splice(#, 1)', buckets, i); |
| } |
| break; |
| } |
| if (++i >= n) return false; // not found |
| } |
| } |
| var map = _map; |
| if (JS('bool', '#.delete(#)', map, key)) { |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| return false; |
| } |
| |
| void clear() { |
| var map = _map; |
| if (JS<int>('!', '#.size', map) > 0) { |
| JS('', '#.clear()', map); |
| JS('', '#.clear()', _keyMap); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| } |
| } |
| } |
| |
| // Used for DDC const sets. |
| class _ImmutableSet<E> extends _HashSet<E> { |
| _ImmutableSet.from(JSArray entries) { |
| var map = _map; |
| for (Object key in entries) { |
| if (key == null) { |
| key = null; // converts undefined to null, if needed. |
| } else if (JS('bool', '#[#] !== #', key, dart.extensionSymbol('_equals'), |
| dart.identityEquals)) { |
| key = putLinkedMapKey(key, _keyMap); |
| } |
| JS('', '#.add(#)', map, key); |
| } |
| } |
| |
| bool add(Object other) => throw _unsupported(); |
| void addAll(Object other) => throw _unsupported(); |
| void clear() => throw _unsupported(); |
| bool remove(Object key) => throw _unsupported(); |
| |
| static Error _unsupported() => |
| UnsupportedError("Cannot modify unmodifiable set"); |
| } |
| |
| class _IdentityHashSet<E> extends _InternalSet<E> |
| implements HashSet<E>, LinkedHashSet<E> { |
| /// The backing store for this set. |
| @notNull |
| final _map = JS('', 'new Set()'); |
| |
| @notNull |
| int _modifications = 0; |
| |
| _IdentityHashSet(); |
| |
| Set<E> _newSet() => _IdentityHashSet<E>(); |
| |
| Set<R> _newSimilarSet<R>() => _IdentityHashSet<R>(); |
| |
| bool contains(Object element) { |
| return JS('', '#.has(#)', _map, element); |
| } |
| |
| E lookup(Object element) { |
| return JS('', '#.has(#)', _map, element) ? element : null; |
| } |
| |
| bool add(E element) { |
| var map = _map; |
| if (JS('bool', '#.has(#)', map, element)) return false; |
| JS('', '#.add(#)', map, element); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| |
| void addAll(Iterable<E> objects) { |
| var map = _map; |
| int length = JS('', '#.size', map); |
| for (E key in objects) { |
| JS('', '#.add(#)', map, key); |
| } |
| if (length != JS<int>('!', '#.size', map)) { |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| } |
| } |
| |
| bool remove(Object element) { |
| if (JS('bool', '#.delete(#)', _map, element)) { |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| return false; |
| } |
| |
| void clear() { |
| var map = _map; |
| if (JS<int>('!', '#.size', map) > 0) { |
| JS('', '#.clear()', map); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| } |
| } |
| } |
| |
| class _CustomKeyHashSet<E> extends _CustomHashSet<E> { |
| _Predicate<Object> _validKey; |
| _CustomKeyHashSet(_Equality<E> equals, _Hasher<E> hashCode, this._validKey) |
| : super(equals, hashCode); |
| |
| Set<E> _newSet() => _CustomKeyHashSet<E>(_equals, _hashCode, _validKey); |
| |
| Set<R> _newSimilarSet<R>() => _HashSet<R>(); |
| |
| bool contains(Object element) { |
| // TODO(jmesserly): there is a subtle difference here compared to Dart 1. |
| // See the comment on CustomKeyHashMap.containsKey for more information. |
| // Treatment of `null` is different due to strong mode's requirement to |
| // perform an `element is E` check before calling equals/hashCode. |
| if (!_validKey(element)) return false; |
| return super.contains(element); |
| } |
| |
| E lookup(Object element) { |
| if (!_validKey(element)) return null; |
| return super.lookup(element); |
| } |
| |
| bool remove(Object element) { |
| if (!_validKey(element)) return false; |
| return super.remove(element); |
| } |
| } |
| |
| class _CustomHashSet<E> extends _InternalSet<E> |
| implements HashSet<E>, LinkedHashSet<E> { |
| _Equality<E> _equals; |
| _Hasher<E> _hashCode; |
| |
| // 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. |
| // |
| // Value cycles after 2^30 modifications so that modification counts are |
| // always unboxed (Smi) values. Modification detection will be missed if you |
| // make exactly some multiple of 2^30 modifications between advances of an |
| // iterator. |
| @notNull |
| int _modifications = 0; |
| |
| /// The backing store for this set, used to handle ordering. |
| // TODO(jmesserly): a non-linked custom hash set could skip this. |
| @notNull |
| final _map = JS('', 'new Set()'); |
| |
| /// Our map used to map keys onto the canonical key that is stored in [_map]. |
| @notNull |
| final _keyMap = JS('', 'new Map()'); |
| |
| _CustomHashSet(this._equals, this._hashCode); |
| |
| Set<E> _newSet() => _CustomHashSet<E>(_equals, _hashCode); |
| Set<R> _newSimilarSet<R>() => _HashSet<R>(); |
| |
| bool contains(Object key) { |
| if (key is E) { |
| var buckets = JS('', '#.get(# & 0x3ffffff)', _keyMap, _hashCode(key)); |
| if (buckets != null) { |
| var equals = _equals; |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| E k = JS('', '#[#]', buckets, i); |
| if (equals(k, key)) return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| E lookup(Object key) { |
| if (key is E) { |
| var buckets = JS('', '#.get(# & 0x3ffffff)', _keyMap, _hashCode(key)); |
| if (buckets != null) { |
| var equals = _equals; |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| E k = JS('', '#[#]', buckets, i); |
| if (equals(k, key)) return k; |
| } |
| } |
| } |
| return null; |
| } |
| |
| bool add(E key) { |
| var keyMap = _keyMap; |
| var hash = JS<int>('!', '# & 0x3ffffff', _hashCode(key)); |
| var buckets = JS('', '#.get(#)', keyMap, hash); |
| if (buckets == null) { |
| JS('', '#.set(#, [#])', keyMap, hash, key); |
| } else { |
| var equals = _equals; |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| E k = JS('', '#[#]', buckets, i); |
| if (equals(k, key)) return false; |
| } |
| JS('', '#.push(#)', buckets, key); |
| } |
| JS('', '#.add(#)', _map, key); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| |
| void addAll(Iterable<E> objects) { |
| // TODO(jmesserly): it'd be nice to skip the covariance check here. |
| for (E element in objects) add(element); |
| } |
| |
| bool remove(Object key) { |
| if (key is E) { |
| var hash = JS<int>('!', '# & 0x3ffffff', _hashCode(key)); |
| var keyMap = _keyMap; |
| var buckets = JS('', '#.get(#)', keyMap, hash); |
| if (buckets == null) return false; // not found |
| var equals = _equals; |
| for (int i = 0, n = JS('!', '#.length', buckets); i < n; i++) { |
| E k = JS('', '#[#]', buckets, i); |
| if (equals(k, key)) { |
| if (n == 1) { |
| JS('', '#.delete(#)', keyMap, hash); |
| } else { |
| JS('', '#.splice(#, 1)', buckets, i); |
| } |
| JS('', '#.delete(#)', _map, k); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| void clear() { |
| var map = _map; |
| if (JS<int>('!', '#.size', map) > 0) { |
| JS('', '#.clear()', map); |
| JS('', '#.clear()', _keyMap); |
| _modifications = (_modifications + 1) & 0x3ffffff; |
| } |
| } |
| } |
| |
| /// Base class for our internal [LinkedHashSet]/[HashSet] implementations. |
| /// |
| /// This implements the common functionality. |
| abstract class _InternalSet<E> extends _SetBase<E> { |
| @notNull |
| get _map; |
| |
| @notNull |
| int get _modifications; |
| |
| @notNull |
| int get length => JS<int>('!', '#.size', _map); |
| |
| @notNull |
| bool get isEmpty => JS('bool', '#.size == 0', _map); |
| |
| @notNull |
| bool get isNotEmpty => JS('bool', '#.size != 0', _map); |
| |
| Iterator<E> get iterator => DartIterator<E>(_jsIterator()); |
| |
| @JSExportName('Symbol.iterator') |
| _jsIterator() { |
| var self = this; |
| var iterator = JS('', '#.values()', self._map); |
| int modifications = self._modifications; |
| return JS( |
| '', |
| '''{ |
| next() { |
| if (# != #) { |
| throw #; |
| } |
| return #.next(); |
| } |
| }''', |
| modifications, |
| self._modifications, |
| ConcurrentModificationError(self), |
| iterator); |
| } |
| } |
| |
| @patch |
| abstract class _SplayTree<K, Node extends _SplayTreeNode<K>> { |
| @patch |
| Node _splayMin(Node node) { |
| Node current = node; |
| while (current.left != null) { |
| Node left = current.left; |
| current.left = left.right; |
| left.right = current; |
| current = left; |
| } |
| return current; |
| } |
| |
| @patch |
| Node _splayMax(Node node) { |
| Node current = node; |
| while (current.right != null) { |
| Node right = current.right; |
| current.right = right.left; |
| right.left = current; |
| current = right; |
| } |
| return current; |
| } |
| } |