Version 0.3.7.3 Merge revisions 18567, 18573, 18574, 18588 ,18594 to trunk git-svn-id: http://dart.googlecode.com/svn/trunk@18610 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/pkg/pkg.status b/pkg/pkg.status index 9933564..cdaed72 100644 --- a/pkg/pkg.status +++ b/pkg/pkg.status
@@ -52,6 +52,9 @@ intl/test/find_default_locale_browser_test: Skip intl/test/date_time_format_http_request_test: Skip +# Fails to recognize HashMap as an instance of Map. +analyzer-experimental/test/generated/ast_test: Fail + [ $runtime == vm && $system == windows ] intl/test/find_default_locale_standalone_test: Fail # Issue 8110
diff --git a/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart b/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart index e60f8c9..9f8155d 100644 --- a/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart +++ b/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart
@@ -306,7 +306,7 @@ // TODO(sgjesse): Handle field types for classes with more than one // constructor. if (ctors.length == 2) { - optimizedFunctions.forEach((Element field, _) { + optimizedFunctions.keys.toList().forEach((Element field) { if (identical(field.enclosingElement, cls)) { scheduleRecompilation(field); } @@ -347,12 +347,12 @@ // TODO(sgjesse): Take the type of the setter into account. if (setterSelectorsUsed.contains(setter.name)) return; setterSelectorsUsed.add(setter.name); - optimizedStaticFunctions.forEach((Element field, _) { + optimizedStaticFunctions.keys.toList().forEach((Element field) { if (field.name == setter.name) { scheduleRecompilation(field); } }); - optimizedFunctions.forEach((Element field, _) { + optimizedFunctions.keys.toList().forEach((Element field) { if (field.name == setter.name) { scheduleRecompilation(field); } @@ -622,14 +622,14 @@ CodeEmitterTask emitter; /** - * The generated code as a js AST for compiled methods. + * The generated code as a js AST for compiled methods. */ Map<Element, js.Expression> get generatedCode { return compiler.enqueuer.codegen.generatedCode; } /** - * The generated code as a js AST for compiled bailout methods. + * The generated code as a js AST for compiled bailout methods. */ final Map<Element, js.Expression> generatedBailoutCode = new Map<Element, js.Expression>(); @@ -908,7 +908,7 @@ // The backend will use a literal list to initialize the entries // of the map. if (enqueuer.isResolutionQueue) { - enqueuer.registerInstantiatedClass(compiler.listClass); + enqueuer.registerInstantiatedClass(compiler.listClass); enqueuer.registerInstantiatedClass(compiler.mapLiteralClass); } }
diff --git a/sdk/lib/_internal/compiler/implementation/native_handler.dart b/sdk/lib/_internal/compiler/implementation/native_handler.dart index 894a605..adce296 100644 --- a/sdk/lib/_internal/compiler/implementation/native_handler.dart +++ b/sdk/lib/_internal/compiler/implementation/native_handler.dart
@@ -362,7 +362,7 @@ cause, [String reason]) { Iterable matches = unusedClasses.where(predicate); - matches.forEach((c) => enqueueClass(c, cause)); + matches.toList().forEach((c) => enqueueClass(c, cause)); } onFirstNativeClass() {
diff --git a/sdk/lib/_internal/compiler/implementation/source_map_builder.dart b/sdk/lib/_internal/compiler/implementation/source_map_builder.dart index a2cd6fc..80960d3 100644 --- a/sdk/lib/_internal/compiler/implementation/source_map_builder.dart +++ b/sdk/lib/_internal/compiler/implementation/source_map_builder.dart
@@ -134,7 +134,6 @@ int indexOf(List<String> list, String value, Map<String, int> map) { return map.putIfAbsent(value, () { int index = list.length; - map[value] = index; list.add(value); return index; });
diff --git a/sdk/lib/collection/collection.dart b/sdk/lib/collection/collection.dart index b1a8353..88c1ada 100644 --- a/sdk/lib/collection/collection.dart +++ b/sdk/lib/collection/collection.dart
@@ -9,8 +9,12 @@ part 'arrays.dart'; part 'collections.dart'; part 'iterator.dart'; -part 'map.dart'; part 'maps.dart'; part 'queue.dart'; -part 'set.dart'; part 'splay_tree.dart'; +part 'hash_table.dart'; +part 'hash_set.dart'; +part 'hash_map.dart'; +part 'linked_hash_table.dart'; +part 'linked_hash_set.dart'; +part 'linked_hash_map.dart';
diff --git a/sdk/lib/collection/collection_sources.gypi b/sdk/lib/collection/collection_sources.gypi index b262c10..37d67be 100644 --- a/sdk/lib/collection/collection_sources.gypi +++ b/sdk/lib/collection/collection_sources.gypi
@@ -7,11 +7,15 @@ 'sources': [ 'arrays.dart', 'collections.dart', + 'hash_map.dart', + 'hash_set.dart', + 'hash_table.dart', 'iterator.dart', - 'map.dart', + 'linked_hash_map.dart', + 'linked_hash_set.dart', + 'linked_hash_table.dart', 'maps.dart', 'queue.dart', - 'set.dart', 'splay_tree.dart', ], }
diff --git a/sdk/lib/collection/hash_map.dart b/sdk/lib/collection/hash_map.dart new file mode 100644 index 0000000..d90b4b9 --- /dev/null +++ b/sdk/lib/collection/hash_map.dart
@@ -0,0 +1,136 @@ +// 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. + +part of dart.collection; + +class _HashMapTable<K, V> extends _HashTable<K> { + static const int _INITIAL_CAPACITY = 8; + static const int _VALUE_INDEX = 1; + + _HashMapTable() : super(_INITIAL_CAPACITY); + + int get _entrySize => 2; + + V _value(int offset) => _table[offset + _VALUE_INDEX]; + void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; } + + _copyEntry(List fromTable, int fromOffset, int toOffset) { + _table[toOffset + _VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]; + } +} + +class HashMap<K, V> implements Map<K, V> { + final _HashMapTable<K, V> _hashTable; + + HashMap() : _hashTable = new _HashMapTable<K, V>() { + _hashTable._container = this; + } + + factory HashMap.from(Map<K, V> other) { + return new HashMap<K, V>()..addAll(other); + } + + bool containsKey(K key) { + return _hashTable._get(key) >= 0; + } + + bool containsValue(V value) { + List table = _hashTable._table; + int entrySize = _hashTable._entrySize; + for (int offset = 0; offset < table.length; offset += entrySize) { + if (!_hashTable._isFree(table[offset]) && + _hashTable._value(offset) == value) { + return true; + } + } + return false; + } + + void addAll(Map<K, V> other) { + other.forEach((K key, V value) { + int offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + }); + } + + V operator [](K key) { + int offset = _hashTable._get(key); + if (offset >= 0) return _hashTable._value(offset); + return null; + } + + void operator []=(K key, V value) { + int offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + } + + V putIfAbsent(K key, V ifAbsent()) { + int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key); + Object entry = _hashTable._table[offset]; + if (!_hashTable._isFree(entry)) { + return _hashTable._value(offset); + } + int modificationCount = _hashTable._modificationCount; + V value = ifAbsent(); + if (modificationCount == _hashTable._modificationCount) { + _hashTable._setKey(offset, key); + _hashTable._setValue(offset, value); + if (entry == null) { + _hashTable._entryCount++; + _hashTable._checkCapacity(); + } else { + assert(identical(entry, _TOMBSTONE)); + _hashTable._deletedCount--; + } + _hashTable._recordModification(); + } else { + // The table might have changed, so we can't trust [offset] any more. + // Do another lookup before setting the value. + offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + } + return value; + } + + V remove(K key) { + int offset = _hashTable._remove(key); + if (offset < 0) return null; + V oldValue = _hashTable._value(offset); + _hashTable._setValue(offset, null); + _hashTable._checkCapacity(); + return oldValue; + } + + void clear() { + _hashTable._clear(); + } + + void forEach(void action (K key, V value)) { + int modificationCount = _hashTable._modificationCount; + List table = _hashTable._table; + int entrySize = _hashTable._entrySize; + for (int offset = 0; offset < table.length; offset += entrySize) { + Object entry = table[offset]; + if (!_hashTable._isFree(entry)) { + K key = entry; + V value = _hashTable._value(offset); + action(key, value); + _hashTable._checkModification(modificationCount); + } + } + } + + Iterable<K> get keys => new _HashTableKeyIterable<K>(_hashTable); + Iterable<V> get values => + new _HashTableValueIterable<V>(_hashTable, _HashMapTable._VALUE_INDEX); + + int get length => _hashTable._elementCount; + + bool get isEmpty => _hashTable._elementCount == 0; + + String toString() => Maps.mapToString(this); +}
diff --git a/sdk/lib/collection/hash_set.dart b/sdk/lib/collection/hash_set.dart new file mode 100644 index 0000000..22fb38f --- /dev/null +++ b/sdk/lib/collection/hash_set.dart
@@ -0,0 +1,115 @@ +// 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. + +part of dart.collection; + +class HashSet<E> extends Collection<E> implements Set<E> { + static const int _INITIAL_CAPACITY = 8; + final _HashTable<E> _table; + + HashSet() : _table = new _HashTable(_INITIAL_CAPACITY) { + _table._container = this; + } + + factory HashSet.from(Iterable<E> iterable) { + return new HashSet<E>()..addAll(iterable); + } + + // Iterable. + Iterator<E> get iterator => new _HashTableKeyIterator<E>(_table); + + bool get isEmpty => _table._elementCount == 0; + + bool contains(Object object) => _table._get(object) >= 0; + + // Collection. + void add(E element) { + _table._put(element); + _table._checkCapacity(); + } + + void addAll(Iterable<E> objects) { + for (E object in objects) { + _table._put(object); + _table._checkCapacity(); + } + } + + bool remove(Object object) { + int offset = _table._remove(object); + _table._checkCapacity(); + return offset >= 0; + } + + void removeAll(Iterable objectsToRemove) { + for (Object object in objectsToRemove) { + _table._remove(object); + _table._checkCapacity(); + } + } + + void retainAll(Iterable objectsToRetain) { + IterableMixinWorkaround.retainAll(this, objectsToRetain); + } + + void _filterMatching(bool test(E element), bool removeMatching) { + int entrySize = _table._entrySize; + int length = _table._table.length; + for (int offset = 0; offset < length; offset += entrySize) { + Object entry = _table._table[offset]; + if (!_table._isFree(entry)) { + E key = identical(entry, _NULL) ? null : entry; + int modificationCount = _table._modificationCount; + bool shouldRemove = (removeMatching == test(key)); + _table._checkModification(modificationCount); + if (shouldRemove) { + _table._deleteEntry(offset); + } + } + } + _table._checkCapacity(); + } + + void removeMatching(bool test(E element)) { + _filterMatching(test, true); + } + + void retainMatching(bool test(E element)) { + _filterMatching(test, false); + } + + void clear() { + _table._clear(); + } + + // Set. + bool isSubsetOf(Collection<E> collection) { + Set otherSet; + if (collection is Set) { + otherSet = collection; + } else { + otherSet = collection.toSet(); + } + return otherSet.containsAll(this); + } + + bool containsAll(Collection<E> collection) { + for (E element in collection) { + if (!this.contains(element)) return false; + } + return true; + } + + Set<E> intersection(Collection<E> other) { + Set<E> result = new HashSet<E>(); + for (E element in other) { + if (this.contains(element)) { + result.add(element); + } + } + return result; + } + + String toString() => Collections.collectionToString(this); +}
diff --git a/sdk/lib/collection/hash_table.dart b/sdk/lib/collection/hash_table.dart new file mode 100644 index 0000000..7ab52cb --- /dev/null +++ b/sdk/lib/collection/hash_table.dart
@@ -0,0 +1,404 @@ +// 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. + +part of dart.collection; + +class _DeadEntry { + const _DeadEntry(); +} + +class _NullKey { + const _NullKey(); + int get hashCode => null.hashCode; +} + +const _TOMBSTONE = const _DeadEntry(); +const _NULL = const _NullKey(); + +class _HashTable<K> { + /** + * Table of entries with [_entrySize] slots per entry. + * + * Capacity in entries must be factor of two. + */ + List _table; + /** Current capacity. Always equal to [:_table.length ~/ _entrySize:]. */ + int _capacity; + /** Count of occupied entries, including deleted ones. */ + int _entryCount = 0; + /** Count of deleted entries. */ + int _deletedCount = 0; + /** Counter incremented when table is modified. */ + int _modificationCount = 0; + /** If set, used as the source object for [ConcurrentModificationError]s. */ + Object _container; + + _HashTable(int initialCapacity) : _capacity = initialCapacity { + _table = _createTable(initialCapacity); + } + + /** Reads key from table. Converts _NULL marker to null. */ + Object _key(offset) { + assert(!_isFree(_table[offset])); + Object key = _table[offset]; + if (!identical(key, _NULL)) return key; + return null; + } + + /** Writes key to table. Converts null to _NULL marker. */ + void _setKey(int offset, Object key) { + if (key == null) key = _NULL; + _table[offset] = key; + } + + int get _elementCount => _entryCount - _deletedCount; + + /** Size of each entry. */ + int get _entrySize => 1; + + void _checkModification(int expectedModificationCount) { + if (_modificationCount != expectedModificationCount) { + throw new ConcurrentModificationError(_container); + } + } + + void _recordModification() { + // 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. + _modificationCount = (_modificationCount + 1) & (0x3FFFFFFF); + } + + /** + * Create an empty table. + */ + List _createTable(int capacity) { + List table = new List.fixedLength(capacity * _entrySize); + return table; + } + + /** First table probe. */ + int _firstProbe(int hashCode, int capacity) { + return hashCode & (capacity - 1); + } + + /** Following table probes. */ + int _nextProbe(int previousIndex, int probeCount, int capacity) { + // When capacity is a power of 2, this probing algorithm (the triangular + // number sequence modulo capacity) is guaranteed to hit all indices exactly + // once before repeating. + return (previousIndex + probeCount) & (capacity - 1); + } + + /** Whether an object is a free-marker (either tombstone or free). */ + bool _isFree(Object marker) => + marker == null || identical(marker, _TOMBSTONE); + + /** + * Look up the offset for an object in the table. + * + * Finds the offset of the object in the table, if it is there, + * or the first free offset for its hashCode. + */ + int _probeForAdd(int hashCode, Object object) { + int entrySize = _entrySize; + int index = _firstProbe(hashCode, _capacity); + int firstTombstone = -1; + int probeCount = 0; + while (true) { + int offset = index * entrySize; + Object entry = _table[offset]; + if (identical(entry, _TOMBSTONE)) { + if (firstTombstone < 0) firstTombstone = offset; + } else if (entry == null) { + if (firstTombstone < 0) return offset; + return firstTombstone; + } else if (identical(_NULL, entry) ? _equals(null, object) + : _equals(entry, object)) { + return offset; + } + // The _nextProbe is designed so that it hits + // every index eventually. + index = _nextProbe(index, ++probeCount, _capacity); + } + } + + /** + * Look up the offset for an object in the table. + * + * If the object is in the table, its offset is returned. + * + * If the object is not in the table, Otherwise a negative value is returned. + */ + int _probeForLookup(int hashCode, Object object) { + int entrySize = _entrySize; + int index = _firstProbe(hashCode, _capacity); + int probeCount = 0; + while (true) { + int offset = index * entrySize; + Object entry = _table[offset]; + if (entry == null) { + return -1; + } else if (!identical(_TOMBSTONE, entry)) { + if (identical(_NULL, entry) ? _equals(null, object) + : _equals(entry, object)) { + return offset; + } + } + // The _nextProbe is designed so that it hits + // every index eventually. + index = _nextProbe(index, ++probeCount, _capacity); + } + } + + // Override the following two to change equality/hashCode computations + + /** + * Compare two object for equality. + * + * The first object is the one already in the table, + * and the second is the one being searched for. + */ + bool _equals(Object element, Object other) { + return element == other; + } + + /** + * Compute hash-code for an object. + */ + int _hashCodeOf(Object object) => object.hashCode; + + /** + * Ensure that the table isn't too full for its own good. + * + * Call this after adding an element. + */ + int _checkCapacity() { + // Compute everything in multiples of entrySize to avoid division. + int freeCount = _capacity - _entryCount; + if (freeCount * 4 < _capacity || + freeCount < _deletedCount) { + // Less than 25% free or more deleted entries than free entries. + _grow(_entryCount - _deletedCount); + } + } + + void _grow(int contentCount) { + int capacity = _capacity; + // Don't grow to less than twice the needed capacity. + int minCapacity = contentCount * 2; + while (capacity < minCapacity) { + capacity *= 2; + } + // Reset to another table and add all existing elements. + List oldTable = _table; + _table = _createTable(capacity); + _capacity = capacity; + _entryCount = 0; + _deletedCount = 0; + _addAllEntries(oldTable); + _recordModification(); + } + + /** + * Copies all non-free entries from the old table to the new empty table. + */ + void _addAllEntries(List oldTable) { + for (int i = 0; i < oldTable.length; i += _entrySize) { + Object object = oldTable[i]; + if (!_isFree(object)) { + int toOffset = _put(object); + _copyEntry(oldTable, i, toOffset); + } + } + } + + /** + * Copies everything but the key element from one entry to another. + * + * Called while growing the base array. + * + * Override this if any non-key fields need copying. + */ + void _copyEntry(List fromTable, int fromOffset, int toOffset) {} + + // The following three methods are for simple get/set/remove operations. + // They only affect the key of an entry. The remaining fields must be + // filled by the caller. + + /** + * Returns the offset of a key in [_table], or negative if it's not there. + */ + int _get(K key) { + return _probeForLookup(_hashCodeOf(key), key); + } + + /** + * Puts the key into the table and returns its offset into [_table]. + * + * If [_entrySize] is greater than 1, the caller should fill the + * remaining fields. + * + * Remember to call [_checkCapacity] after using this method. + */ + int _put(K key) { + int offset = _probeForAdd(_hashCodeOf(key), key); + Object oldEntry = _table[offset]; + if (oldEntry == null) { + _entryCount++; + } else if (identical(oldEntry, _TOMBSTONE)) { + _deletedCount--; + } else { + return offset; + } + _setKey(offset, key); + _recordModification(); + return offset; + } + + /** + * Removes a key from the table and returns its offset into [_table]. + * + * Returns null if the key was not in the table. + * If [_entrySize] is greater than 1, the caller should clean up the + * remaining fields. + */ + int _remove(K key) { + int offset = _probeForLookup(_hashCodeOf(key), key); + if (offset >= 0) { + _deleteEntry(offset); + } + return offset; + } + + /** Clears the table completely, leaving it empty. */ + void _clear() { + if (_elementCount == 0) return; + for (int i = 0; i < _table.length; i++) { + _table[i] = null; + } + _entryCount = _deletedCount = 0; + _recordModification(); + } + + /** Clears an entry in the table. */ + void _deleteEntry(int offset) { + assert(!_isFree(_table[offset])); + _setKey(offset, _TOMBSTONE); + _deletedCount++; + _recordModification(); + } +} + +/** + * Generic iterable based on a [_HashTable]. + */ +abstract class _HashTableIterable<E> extends Iterable<E> { + final _HashTable _hashTable; + _HashTableIterable(this._hashTable); + + Iterator<E> get iterator; + + /** + * Return the iterated value for a given entry. + */ + E _valueAt(int offset, Object key); + + int get length => _hashTable._elementCount; + + bool get isEmpty => _hashTable._elementCount == 0; + + void forEach(void action(E element)) { + int entrySize = _hashTable._entrySize; + List table = _hashTable._table; + int modificationCount = _hashTable._modificationCount; + for (int offset = 0; offset < table.length; offset += entrySize) { + Object entry = table[offset]; + if (!_hashTable._isFree(entry)) { + E value = _valueAt(offset, entry); + action(value); + } + _hashTable._checkModification(modificationCount); + } + } +} + +abstract class _HashTableIterator<E> implements Iterator<E> { + final _HashTable _hashTable; + final int _modificationCount; + /** Location right after last found element. */ + int _offset = 0; + E _current = null; + + _HashTableIterator(_HashTable hashTable) + : _hashTable = hashTable, + _modificationCount = hashTable._modificationCount; + + bool moveNext() { + _hashTable._checkModification(_modificationCount); + + List table = _hashTable._table; + int entrySize = _hashTable._entrySize; + + while (_offset < table.length) { + int currentOffset = _offset; + Object entry = table[currentOffset]; + _offset = currentOffset + entrySize; + if (!_hashTable._isFree(entry)) { + _current = _valueAt(currentOffset, entry); + return true; + } + } + _current = null; + return false; + } + + E get current => _current; + + E _valueAt(int offset, Object key); +} + +class _HashTableKeyIterable<K> extends _HashTableIterable<K> { + _HashTableKeyIterable(_HashTable<K> hashTable) : super(hashTable); + + Iterator<K> get iterator => new _HashTableKeyIterator<K>(_hashTable); + + K _valueAt(int offset, Object key) { + if (identical(key, _NULL)) return null; + return key; + } + + bool contains(Object value) => _hashTable._get(value) >= 0; +} + +class _HashTableKeyIterator<K> extends _HashTableIterator<K> { + _HashTableKeyIterator(_HashTable hashTable) : super(hashTable); + + K _valueAt(int offset, Object key) { + if (identical(key, _NULL)) return null; + return key; + } +} + +class _HashTableValueIterable<V> extends _HashTableIterable<V> { + final int _entryIndex; + + _HashTableValueIterable(_HashTable hashTable, this._entryIndex) + : super(hashTable); + + Iterator<V> get iterator { + return new _HashTableValueIterator<V>(_hashTable, _entryIndex); + } + + V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex]; +} + +class _HashTableValueIterator<V> extends _HashTableIterator<V> { + final int _entryIndex; + + _HashTableValueIterator(_HashTable hashTable, this._entryIndex) + : super(hashTable); + + V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex]; +}
diff --git a/sdk/lib/collection/linked_hash_map.dart b/sdk/lib/collection/linked_hash_map.dart new file mode 100644 index 0000000..4dcbc060 --- /dev/null +++ b/sdk/lib/collection/linked_hash_map.dart
@@ -0,0 +1,138 @@ +// 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. + +part of dart.collection; + +class _LinkedHashMapTable<K, V> extends _LinkedHashTable<K> { + static const int _INITIAL_CAPACITY = 8; + static const int _VALUE_INDEX = 3; + + int get _entrySize => 4; + + _LinkedHashMapTable() : super(_INITIAL_CAPACITY); + + V _value(int offset) => _table[offset + _VALUE_INDEX]; + void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; } + + _copyEntry(List oldTable, int fromOffset, int toOffset) { + _table[toOffset + _VALUE_INDEX] = oldTable[fromOffset + _VALUE_INDEX]; + } +} + +/** + * A hash-based map that iterates keys and values in key insertion order. + */ +class LinkedHashMap<K, V> implements Map<K, V> { + final _LinkedHashMapTable _hashTable; + + LinkedHashMap() : _hashTable = new _LinkedHashMapTable<K, V>() { + _hashTable._container = this; + } + + factory LinkedHashMap.from(Map<K, V> other) { + return new LinkedHashMap<K, V>()..addAll(other); + } + + bool containsKey(K key) { + return _hashTable._get(key) >= 0; + } + + bool containsValue(V value) { + int modificationCount = _hashTable._modificationCount; + for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET); + offset != _LinkedHashTable._HEAD_OFFSET; + offset = _hashTable._next(offset)) { + if (_hashTable._value(offset) == value) { + return true; + } + // The == call may modify the table. + _hashTable._checkModification(modificationCount); + } + return false; + } + + void addAll(Map<K, V> other) { + other.forEach((K key, V value) { + int offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + }); + } + + V operator [](K key) { + int offset = _hashTable._get(key); + if (offset >= 0) return _hashTable._value(offset); + return null; + } + + void operator []=(K key, V value) { + int offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + } + + V putIfAbsent(K key, V ifAbsent()) { + int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key); + Object entry = _hashTable._table[offset]; + if (!_hashTable._isFree(entry)) { + return _hashTable._value(offset); + } + int modificationCount = _hashTable._modificationCount; + V value = ifAbsent(); + if (modificationCount == _hashTable._modificationCount) { + _hashTable._setKey(offset, key); + _hashTable._setValue(offset, value); + _hashTable._linkLast(offset); + if (entry == null) { + _hashTable._entryCount++; + _hashTable._checkCapacity(); + } else { + assert(identical(entry, _TOMBSTONE)); + _hashTable._deletedCount--; + } + _hashTable._recordModification(); + } else { + // The table might have changed, so we can't trust [offset] any more. + // Do another lookup before setting the value. + offset = _hashTable._put(key); + _hashTable._setValue(offset, value); + _hashTable._checkCapacity(); + } + return value; + } + + V remove(K key) { + int offset = _hashTable._remove(key); + if (offset < 0) return null; + Object oldValue = _hashTable._value(offset); + _hashTable._setValue(offset, null); + _hashTable._checkCapacity(); + return oldValue; + } + + void clear() { + _hashTable._clear(); + } + + void forEach(void action (K key, V value)) { + int modificationCount = _hashTable._modificationCount; + for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET); + offset != _LinkedHashTable._HEAD_OFFSET; + offset = _hashTable._next(offset)) { + action(_hashTable._key(offset), _hashTable._value(offset)); + _hashTable._checkModification(modificationCount); + } + } + + Iterable<K> get keys => new _LinkedHashTableKeyIterable<K>(_hashTable); + Iterable<V> get values => + new _LinkedHashTableValueIterable<V>(_hashTable, + _LinkedHashMapTable._VALUE_INDEX); + + int get length => _hashTable._elementCount; + + bool get isEmpty => _hashTable._elementCount == 0; + + String toString() => Maps.mapToString(this); +}
diff --git a/sdk/lib/collection/linked_hash_set.dart b/sdk/lib/collection/linked_hash_set.dart new file mode 100644 index 0000000..e72493a --- /dev/null +++ b/sdk/lib/collection/linked_hash_set.dart
@@ -0,0 +1,157 @@ +// 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. + +part of dart.collection; + +class LinkedHashSet<E> extends Collection<E> implements Set<E> { + static const int _INITIAL_CAPACITY = 8; + _LinkedHashTable<E> _table; + + LinkedHashSet() : _table = new _LinkedHashTable(_INITIAL_CAPACITY) { + _table._container = this; + } + + factory LinkedHashSet.from(Iterable<E> iterable) { + return new LinkedHashSet<E>()..addAll(iterable); + } + + // Iterable. + Iterator<E> get iterator => new _LinkedHashTableKeyIterator<E>(_table); + + void forEach(void action(E element)) { + int offset = _table._next(_LinkedHashTable._HEAD_OFFSET); + int modificationCount = _table._modificationCount; + while (offset != _LinkedHashTable._HEAD_OFFSET) { + E key = _table._key(offset); + action(key); + _table._checkModification(modificationCount); + offset = _table._next(offset); + } + } + + bool get isEmpty => _table._elementCount == 0; + + bool contains(Object object) => _table._get(object) >= 0; + + E get first { + int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET); + if (firstOffset == _LinkedHashTable._HEAD_OFFSET) { + throw new StateError("No elements"); + } + return _table._key(firstOffset); + } + + E get last { + int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET); + if (lastOffset == _LinkedHashTable._HEAD_OFFSET) { + throw new StateError("No elements"); + } + return _table._key(lastOffset); + } + + E get single { + int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET); + if (firstOffset == _LinkedHashTable._HEAD_OFFSET) { + throw new StateError("No elements"); + } + int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET); + if (lastOffset != firstOffset) { + throw new StateError("Too many elements"); + } + return _table._key(firstOffset); + } + + // Collection. + void add(E element) { + _table._put(element); + _table._checkCapacity(); + } + + void addAll(Iterable<E> objects) { + for (E object in objects) { + _table._put(object); + _table._checkCapacity(); + } + } + + bool remove(Object object) { + int offset = _table._remove(object); + if (offset >= 0) { + _table._checkCapacity(); + return true; + } + return false; + } + + void removeAll(Iterable objectsToRemove) { + for (Object object in objectsToRemove) { + _table._remove(object); + _table._checkCapacity(); + } + } + + void retainAll(Iterable objectsToRemove) { + IterableMixinWorkaround.retainAll(this, objectsToRemove); + } + + void _filterMatching(bool test(E element), bool removeMatching) { + int entrySize = _table._entrySize; + int length = _table._table.length; + int offset = _table._next(_LinkedHashTable._HEAD_OFFSET); + while (offset != _LinkedHashTable._HEAD_OFFSET) { + E key = _table._key(offset); + int nextOffset = _table._next(offset); + int modificationCount = _table._modificationCount; + bool shouldRemove = (removeMatching == test(key)); + _table._checkModification(modificationCount); + if (shouldRemove) { + _table._deleteEntry(offset); + } + offset = nextOffset; + } + _table._checkCapacity(); + } + + void removeMatching(bool test(E element)) { + _filterMatching(test, true); + } + + void retainMatching(bool test(E element)) { + _filterMatching(test, false); + } + + void clear() { + _table._clear(); + } + + // Set. + bool isSubsetOf(Collection<E> collection) { + Set otherSet; + if (collection is Set) { + otherSet = collection; + } else { + otherSet = collection.toSet(); + } + return otherSet.containsAll(this); + } + + bool containsAll(Collection<E> collection) { + for (E element in collection) { + if (!this.contains(element)) return false; + } + return true; + } + + Set<E> intersection(Collection<E> other) { + Set<E> result = new LinkedHashSet<E>(); + for (E element in other) { + if (this.contains(element)) { + result.add(element); + } + } + return result; + } + + String toString() => Collections.collectionToString(this); +}
diff --git a/sdk/lib/collection/linked_hash_table.dart b/sdk/lib/collection/linked_hash_table.dart new file mode 100644 index 0000000..fbf6172 --- /dev/null +++ b/sdk/lib/collection/linked_hash_table.dart
@@ -0,0 +1,165 @@ +// 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. + +part of dart.collection; + +/** Unique marker object for the head of a linked list of entries. */ +class _LinkedHashTableHeadMarker { + const _LinkedHashTableHeadMarker(); +} + +const _LinkedHashTableHeadMarker _HEAD_MARKER = + const _LinkedHashTableHeadMarker(); + +class _LinkedHashTable<K> extends _HashTable<K> { + static const _NEXT_INDEX = 1; + static const _PREV_INDEX = 2; + static const _HEAD_OFFSET = 0; + + _LinkedHashTable(int initialCapacity) : super(initialCapacity); + + int get _entrySize => 3; + + List _createTable(int capacity) { + List result = new List.fixedLength(capacity * _entrySize); + result[_HEAD_OFFSET] = _HEAD_MARKER; + result[_HEAD_OFFSET + _NEXT_INDEX] = _HEAD_OFFSET; + result[_HEAD_OFFSET + _PREV_INDEX] = _HEAD_OFFSET; + return result; + } + + int _next(int offset) => _table[offset + _NEXT_INDEX]; + void _setNext(int offset, int to) { _table[offset + _NEXT_INDEX] = to; } + + int _prev(int offset) => _table[offset + _PREV_INDEX]; + void _setPrev(int offset, int to) { _table[offset + _PREV_INDEX] = to; } + + void _linkLast(int offset) { + // Add entry at offset at end of double-linked list. + int last = _prev(_HEAD_OFFSET); + _setNext(offset, _HEAD_OFFSET); + _setPrev(offset, last); + _setNext(last, offset); + _setPrev(_HEAD_OFFSET, offset); + } + + void _unlink(int offset) { + assert(offset != _HEAD_OFFSET); + int next = _next(offset); + int prev = _prev(offset); + _setNext(offset, null); + _setPrev(offset, null); + _setNext(prev, next); + _setPrev(next, prev); + } + + /** + * Copies all non-free entries from the old table to the new empty table. + */ + void _addAllEntries(List oldTable) { + int offset = oldTable[_HEAD_OFFSET + _NEXT_INDEX]; + while (offset != _HEAD_OFFSET) { + Object object = oldTable[offset]; + int nextOffset = oldTable[offset + _NEXT_INDEX]; + int toOffset = _put(object); + _copyEntry(oldTable, offset, toOffset); + offset = nextOffset; + } + } + + void _clear() { + if (_elementCount == 0) return; + _setNext(_HEAD_OFFSET, _HEAD_OFFSET); + _setPrev(_HEAD_OFFSET, _HEAD_OFFSET); + for (int i = _entrySize; i < _table.length; i++) { + _table[i] = null; + } + _entryCount = _deletedCount = 0; + _recordModification(); + } + + int _put(K key) { + int offset = _probeForAdd(_hashCodeOf(key), key); + Object oldEntry = _table[offset]; + if (identical(oldEntry, _TOMBSTONE)) { + _deletedCount--; + } else if (oldEntry == null) { + _entryCount++; + } else { + return offset; + } + _recordModification(); + _setKey(offset, key); + _linkLast(offset); + return offset; + } + + void _deleteEntry(int offset) { + _unlink(offset); + _setKey(offset, _TOMBSTONE); + _deletedCount++; + _recordModification(); + } +} + +class _LinkedHashTableKeyIterable<K> extends Iterable<K> { + final _LinkedHashTable<K> _table; + _LinkedHashTableKeyIterable(this._table); + Iterator<K> get iterator => new _LinkedHashTableKeyIterator<K>(_table); + + bool contains(Object value) => _table._get(value) >= 0; + + int get length => _table._elementCount; +} + +class _LinkedHashTableKeyIterator<K> extends _LinkedHashTableIterator<K> { + _LinkedHashTableKeyIterator(_LinkedHashTable<K> hashTable): super(hashTable); + + K _getCurrent(int offset) => _hashTable._key(offset); +} + +class _LinkedHashTableValueIterable<V> extends Iterable<V> { + final _LinkedHashTable _hashTable; + final int _valueIndex; + _LinkedHashTableValueIterable(this._hashTable, this._valueIndex); + Iterator<V> get iterator => + new _LinkedHashTableValueIterator<V>(_hashTable, _valueIndex); + int get length => _hashTable._elementCount; +} + +class _LinkedHashTableValueIterator<V> extends _LinkedHashTableIterator<V> { + final int _valueIndex; + + _LinkedHashTableValueIterator(_LinkedHashTable hashTable, this._valueIndex) + : super(hashTable); + + V _getCurrent(int offset) => _hashTable._table[offset + _valueIndex]; +} + +abstract class _LinkedHashTableIterator<T> implements Iterator<T> { + final _LinkedHashTable _hashTable; + final int _modificationCount; + int _offset; + T _current; + + _LinkedHashTableIterator(_LinkedHashTable table) + : _hashTable = table, + _modificationCount = table._modificationCount, + _offset = table._next(_LinkedHashTable._HEAD_OFFSET); + + bool moveNext() { + _hashTable._checkModification(_modificationCount); + if (_offset == _LinkedHashTable._HEAD_OFFSET) { + _current = null; + return false; + } + _current = _getCurrent(_offset); + _offset = _hashTable._next(_offset); + return true; + } + + T _getCurrent(int offset); + + T get current => _current; +}
diff --git a/sdk/lib/collection/map.dart b/sdk/lib/collection/map.dart deleted file mode 100644 index 1beaf2b..0000000 --- a/sdk/lib/collection/map.dart +++ /dev/null
@@ -1,474 +0,0 @@ -// 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. - -part of dart.collection; - - -/** - * Hash map version of the [Map] interface. A [HashMap] does not - * provide any guarantees on the order of keys and values in [keys] - * and [values]. - */ -abstract class HashMap<K, V> extends Map<K, V> { - /** - * Creates a map with the default implementation. - */ - factory HashMap() => new _HashMapImpl<K, V>(); - - /** - * Creates a [HashMap] that contains all key value pairs of [other]. - */ - factory HashMap.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other); -} - -/** - * Hash map version of the [Map] interface that preserves insertion - * order. - */ -abstract class LinkedHashMap<K, V> extends HashMap<K, V> { - /** - * Creates a map with the default implementation. - */ - factory LinkedHashMap() => new _LinkedHashMapImpl<K, V>(); - - /** - * Creates a [LinkedHashMap] that contains all key value pairs of [other]. - */ - factory LinkedHashMap.from(Map<K, V> other) - => new _LinkedHashMapImpl<K, V>.from(other); -} - - -// Hash map implementation with open addressing and quadratic probing. -class _HashMapImpl<K, V> implements HashMap<K, V> { - - // The [_keys] list contains the keys inserted in the map. - // The [_keys] list must be a raw list because it - // will contain both elements of type K, and the [_DELETED_KEY] of type - // [_DeletedKeySentinel]. - // The alternative of declaring the [_keys] list as of type Object - // does not work, because the HashSetIterator constructor would fail: - // HashSetIterator(HashSet<E> set) - // : _nextValidIndex = -1, - // _entries = set_._backingMap._keys { - // _advance(); - // } - // With K being type int, for example, it would fail because - // List<Object> is not assignable to type List<int> of entries. - List _keys; - - // The values inserted in the map. For a filled entry index in this - // list, there is always the corresponding key in the [keys_] list - // at the same entry index. - List<V> _values; - - // The load limit is the number of entries we allow until we double - // the size of the lists. - int _loadLimit; - - // The current number of entries in the map. Will never be greater - // than [_loadLimit]. - int _numberOfEntries; - - // The current number of deleted entries in the map. - int _numberOfDeleted; - - // The sentinel when a key is deleted from the map. - static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); - - // The initial capacity of a hash map. - static const int _INITIAL_CAPACITY = 8; // must be power of 2 - - _HashMapImpl() { - _numberOfEntries = 0; - _numberOfDeleted = 0; - _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); - _keys = new List.fixedLength(_INITIAL_CAPACITY); - _values = new List<V>.fixedLength(_INITIAL_CAPACITY); - } - - factory _HashMapImpl.from(Map<K, V> other) { - Map<K, V> result = new _HashMapImpl<K, V>(); - other.forEach((K key, V value) { result[key] = value; }); - return result; - } - - static int _computeLoadLimit(int capacity) { - return (capacity * 3) ~/ 4; - } - - static int _firstProbe(int hashCode, int length) { - return hashCode & (length - 1); - } - - static int _nextProbe(int currentProbe, int numberOfProbes, int length) { - return (currentProbe + numberOfProbes) & (length - 1); - } - - int _probeForAdding(K key) { - if (key == null) throw new ArgumentError(null); - int hash = _firstProbe(key.hashCode, _keys.length); - int numberOfProbes = 1; - int initialHash = hash; - // insertionIndex points to a slot where a key was deleted. - int insertionIndex = -1; - while (true) { - // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. - Object existingKey = _keys[hash]; - if (existingKey == null) { - // We are sure the key is not already in the set. - // If the current slot is empty and we didn't find any - // insertion slot before, return this slot. - if (insertionIndex < 0) return hash; - // If we did find an insertion slot before, return it. - return insertionIndex; - } else if (existingKey == key) { - // The key is already in the map. Return its slot. - return hash; - } else if ((insertionIndex < 0) && - (identical(existingKey, _DELETED_KEY))) { - // The slot contains a deleted element. Because previous calls to this - // method may not have had this slot deleted, we must continue iterate - // to find if there is a slot with the given key. - insertionIndex = hash; - } - - // We did not find an insertion slot. Look at the next one. - hash = _nextProbe(hash, numberOfProbes++, _keys.length); - // _ensureCapacity has guaranteed the following cannot happen. - // assert(hash != initialHash); - } - } - - int _probeForLookup(K key) { - if (key == null) throw new ArgumentError(null); - int hash = _firstProbe(key.hashCode, _keys.length); - int numberOfProbes = 1; - int initialHash = hash; - while (true) { - // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. - Object existingKey = _keys[hash]; - // If the slot does not contain anything (in particular, it does not - // contain a deleted key), we know the key is not in the map. - if (existingKey == null) return -1; - // The key is in the map, return its index. - if (existingKey == key) return hash; - // Go to the next probe. - hash = _nextProbe(hash, numberOfProbes++, _keys.length); - // _ensureCapacity has guaranteed the following cannot happen. - // assert(hash != initialHash); - } - } - - void _ensureCapacity() { - int newNumberOfEntries = _numberOfEntries + 1; - // Test if adding an element will reach the load limit. - if (newNumberOfEntries >= _loadLimit) { - _grow(_keys.length * 2); - return; - } - - // Make sure that we don't have poor performance when a map - // contains lots of deleted entries: we _grow if - // there are more deleted entried than free entries. - int capacity = _keys.length; - int numberOfFreeOrDeleted = capacity - newNumberOfEntries; - int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted; - // assert(numberOfFree > 0); - if (_numberOfDeleted > numberOfFree) { - _grow(_keys.length); - } - } - - static bool _isPowerOfTwo(int x) { - return ((x & (x - 1)) == 0); - } - - void _grow(int newCapacity) { - assert(_isPowerOfTwo(newCapacity)); - int capacity = _keys.length; - _loadLimit = _computeLoadLimit(newCapacity); - List oldKeys = _keys; - List<V> oldValues = _values; - _keys = new List.fixedLength(newCapacity); - _values = new List<V>.fixedLength(newCapacity); - for (int i = 0; i < capacity; i++) { - // [key] can be either of type [K] or [_DeletedKeySentinel]. - Object key = oldKeys[i]; - // If there is no key, we don't need to deal with the current slot. - if (key == null || identical(key, _DELETED_KEY)) { - continue; - } - V value = oldValues[i]; - // Insert the {key, value} pair in their new slot. - int newIndex = _probeForAdding(key); - _keys[newIndex] = key; - _values[newIndex] = value; - } - _numberOfDeleted = 0; - } - - void clear() { - _numberOfEntries = 0; - _numberOfDeleted = 0; - int length = _keys.length; - for (int i = 0; i < length; i++) { - _keys[i] = null; - _values[i] = null; - } - } - - void operator []=(K key, V value) { - _ensureCapacity(); - int index = _probeForAdding(key); - if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) { - _numberOfEntries++; - } - _keys[index] = key; - _values[index] = value; - } - - V operator [](K key) { - int index = _probeForLookup(key); - if (index < 0) return null; - return _values[index]; - } - - V putIfAbsent(K key, V ifAbsent()) { - int index = _probeForLookup(key); - if (index >= 0) return _values[index]; - - V value = ifAbsent(); - this[key] = value; - return value; - } - - V remove(K key) { - int index = _probeForLookup(key); - if (index >= 0) { - _numberOfEntries--; - V value = _values[index]; - _values[index] = null; - // Set the key to the sentinel to not break the probing chain. - _keys[index] = _DELETED_KEY; - _numberOfDeleted++; - return value; - } - return null; - } - - bool get isEmpty { - return _numberOfEntries == 0; - } - - int get length { - return _numberOfEntries; - } - - void forEach(void f(K key, V value)) { - Iterator<int> it = new _HashMapImplIndexIterator(this); - while (it.moveNext()) { - f(_keys[it.current], _values[it.current]); - } - } - - Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this); - - Iterable<V> get values => new _HashMapImplValueIterable<V>(this); - - bool containsKey(K key) { - return (_probeForLookup(key) != -1); - } - - bool containsValue(V value) => values.contains(value); - - String toString() { - return Maps.mapToString(this); - } -} - -class _HashMapImplKeyIterable<E> extends Iterable<E> { - final _HashMapImpl _map; - _HashMapImplKeyIterable(this._map); - - Iterator<E> get iterator => new _HashMapImplKeyIterator<E>(_map); -} - -class _HashMapImplValueIterable<E> extends Iterable<E> { - final _HashMapImpl _map; - _HashMapImplValueIterable(this._map); - - Iterator<E> get iterator => new _HashMapImplValueIterator<E>(_map); -} - -abstract class _HashMapImplIterator<E> implements Iterator<E> { - final _HashMapImpl _map; - int _index = -1; - E _current; - - _HashMapImplIterator(this._map); - - E _computeCurrentFromIndex(int index, List keys, List values); - - bool moveNext() { - int length = _map._keys.length; - int newIndex = _index + 1; - while (newIndex < length) { - var key = _map._keys[newIndex]; - if ((key != null) && (!identical(key, _HashMapImpl._DELETED_KEY))) { - _current = _computeCurrentFromIndex(newIndex, _map._keys, _map._values); - _index = newIndex; - return true; - } - newIndex++; - } - _index = length; - _current = null; - return false; - } - - E get current => _current; -} - -class _HashMapImplKeyIterator<E> extends _HashMapImplIterator<E> { - _HashMapImplKeyIterator(_HashMapImpl map) : super(map); - - E _computeCurrentFromIndex(int index, List keys, List values) { - return keys[index]; - } -} - -class _HashMapImplValueIterator<E> extends _HashMapImplIterator<E> { - _HashMapImplValueIterator(_HashMapImpl map) : super(map); - - E _computeCurrentFromIndex(int index, List keys, List values) { - return values[index]; - } -} - -class _HashMapImplIndexIterator extends _HashMapImplIterator<int> { - _HashMapImplIndexIterator(_HashMapImpl map) : super(map); - - int _computeCurrentFromIndex(int index, List keys, List values) { - return index; - } -} - -/** - * A singleton sentinel used to represent when a key is deleted from the map. - * We can't use [: const Object() :] as a sentinel because it would end up - * canonicalized and then we cannot distinguish the deleted key from the - * canonicalized [: Object() :]. - */ -class _DeletedKeySentinel { - const _DeletedKeySentinel(); -} - - -/** - * This class represents a pair of two objects, used by LinkedHashMap - * to store a {key, value} in a list. - */ -class _KeyValuePair<K, V> { - _KeyValuePair(this.key, this.value) {} - - final K key; - V value; -} - -/** - * A LinkedHashMap is a hash map that preserves the insertion order - * when iterating over the keys or the values. Updating the value of a - * key does not change the order. - */ -class _LinkedHashMapImpl<K, V> implements LinkedHashMap<K, V> { - DoubleLinkedQueue<_KeyValuePair<K, V>> _list; - HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>> _map; - - _LinkedHashMapImpl() { - _map = new HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>>(); - _list = new DoubleLinkedQueue<_KeyValuePair<K, V>>(); - } - - factory _LinkedHashMapImpl.from(Map<K, V> other) { - Map<K, V> result = new _LinkedHashMapImpl<K, V>(); - other.forEach((K key, V value) { result[key] = value; }); - return result; - } - - void operator []=(K key, V value) { - if (_map.containsKey(key)) { - _map[key].element.value = value; - } else { - _list.addLast(new _KeyValuePair<K, V>(key, value)); - _map[key] = _list.lastEntry(); - } - } - - V operator [](K key) { - DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key]; - if (entry == null) return null; - return entry.element.value; - } - - V remove(K key) { - DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key); - if (entry == null) return null; - entry.remove(); - return entry.element.value; - } - - V putIfAbsent(K key, V ifAbsent()) { - V value = this[key]; - if ((this[key] == null) && !(containsKey(key))) { - value = ifAbsent(); - this[key] = value; - } - return value; - } - - Iterable<K> get keys { - return new MappedIterable<_KeyValuePair<K, V>, K>( - _list, (_KeyValuePair<K, V> entry) => entry.key); - } - - - Iterable<V> get values { - return new MappedIterable<_KeyValuePair<K, V>, V>( - _list, (_KeyValuePair<K, V> entry) => entry.value); - } - - void forEach(void f(K key, V value)) { - _list.forEach((_KeyValuePair<K, V> entry) { - f(entry.key, entry.value); - }); - } - - bool containsKey(K key) { - return _map.containsKey(key); - } - - bool containsValue(V value) { - return _list.any((_KeyValuePair<K, V> entry) { - return (entry.value == value); - }); - } - - int get length { - return _map.length; - } - - bool get isEmpty { - return length == 0; - } - - void clear() { - _map.clear(); - _list.clear(); - } - - String toString() { - return Maps.mapToString(this); - } -}
diff --git a/sdk/lib/collection/set.dart b/sdk/lib/collection/set.dart deleted file mode 100644 index 9363676..0000000 --- a/sdk/lib/collection/set.dart +++ /dev/null
@@ -1,110 +0,0 @@ -// 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. - -part of dart.collection; - - - -class HashSet<E> extends Collection<E> implements Set<E> { - // The map backing this set. The associations in this map are all - // of the form element -> element. If a value is not in the map, - // then it is not in the set. - final _HashMapImpl<E, E> _backingMap; - - HashSet() : _backingMap = new _HashMapImpl<E, E>(); - - /** - * Creates a [Set] that contains all elements of [other]. - */ - factory HashSet.from(Iterable<E> other) { - Set<E> set = new HashSet<E>(); - for (final e in other) { - set.add(e); - } - return set; - } - - void clear() { - _backingMap.clear(); - } - - void add(E value) { - _backingMap[value] = value; - } - - bool remove(Object value) { - if (!_backingMap.containsKey(value)) return false; - _backingMap.remove(value); - return true; - } - - bool contains(E value) { - return _backingMap.containsKey(value); - } - - Set<E> intersection(Collection<E> collection) { - Set<E> result = new Set<E>(); - collection.forEach((E value) { - if (contains(value)) result.add(value); - }); - return result; - } - - bool isSubsetOf(Collection<E> other) { - return new Set<E>.from(other).containsAll(this); - } - - bool containsAll(Collection<E> collection) { - return collection.every((E value) { - return contains(value); - }); - } - - void forEach(void f(E element)) { - _backingMap.forEach((E key, E value) { - f(key); - }); - } - - bool get isEmpty { - return _backingMap.isEmpty; - } - - int get length { - return _backingMap.length; - } - - Iterator<E> get iterator => new _HashSetIterator<E>(this); - - String toString() { - return Collections.collectionToString(this); - } -} - -class _HashSetIterator<E> implements Iterator<E> { - - _HashSetIterator(HashSet<E> set) - : _keysIterator = set._backingMap._keys.iterator; - - E get current { - var result = _keysIterator.current; - if (identical(result, _HashMapImpl._DELETED_KEY)) { - // TODO(floitsch): improve the error reporting. - throw new StateError("Concurrent modification."); - } - return result; - } - - bool moveNext() { - bool result; - do { - result = _keysIterator.moveNext(); - } while (result && - (_keysIterator.current == null || - identical(_keysIterator.current, _HashMapImpl._DELETED_KEY))); - return result; - } - - Iterator _keysIterator; -}
diff --git a/sdk/lib/collection/splay_tree.dart b/sdk/lib/collection/splay_tree.dart index d9eca77..31be011 100644 --- a/sdk/lib/collection/splay_tree.dart +++ b/sdk/lib/collection/splay_tree.dart
@@ -9,12 +9,12 @@ * and right children in the tree. */ class SplayTreeNode<K, V> { - SplayTreeNode(K this.key, V this.value); - - K key; + final K key; V value; SplayTreeNode<K, V> left; SplayTreeNode<K, V> right; + + SplayTreeNode(K this.key, V this.value); } /** @@ -40,10 +40,23 @@ // Number of elements in the splay tree. int _count; - SplayTreeMap() { - _dummy = new SplayTreeNode<K, V>(null, null); + /** + * Counter incremented whenever the keys in the map changes. + * + * Used to detect concurrent modifications. + */ + int _modificationCount = 0; + /** + * Counter incremented whenever the tree structure changes. + * + * Used to detect that an in-place traversal cannot use + * cached information that relies on the tree structure. + */ + int _splayCount = 0; + + SplayTreeMap() : + _dummy = new SplayTreeNode<K, V>(null, null), _count = 0; - } /** * Perform the splay operation for the given key. Moves the node with @@ -51,9 +64,12 @@ * key, the last node on the search path is moved to the top of the * tree. This is the simplified top-down splaying algorithm from: * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. + * + * Returns the result of comparing the new root of the tree to [key]. + * Returns -1 if the table is empty. */ - void splay_(K key) { - if (isEmpty) return; + int _splay(K key) { + if (_root == null) return -1; // The right child of the dummy node will hold // the L tree of the algorithm. The left child of the dummy node @@ -62,11 +78,13 @@ SplayTreeNode<K, V> left = _dummy; SplayTreeNode<K, V> right = _dummy; SplayTreeNode<K, V> current = _root; + int comp; while (true) { - int comp = key.compareTo(current.key); - if (comp < 0) { + comp = current.key.compareTo(key); + if (comp > 0) { if (current.left == null) break; - if (key.compareTo(current.left.key) < 0) { + comp = current.left.key.compareTo(key); + if (comp > 0) { // Rotate right. SplayTreeNode<K, V> tmp = current.left; current.left = tmp.right; @@ -78,9 +96,10 @@ right.left = current; right = current; current = current.left; - } else if (comp > 0) { + } else if (comp < 0) { if (current.right == null) break; - if (key.compareTo(current.right.key) > 0) { + comp = current.right.key.compareTo(key); + if (comp < 0) { // Rotate left. SplayTreeNode<K, V> tmp = current.right; current.right = tmp.left; @@ -105,20 +124,22 @@ _dummy.right = null; _dummy.left = null; + _splayCount++; + return comp; } V operator [](K key) { - if (!isEmpty) { - splay_(key); - if (_root.key.compareTo(key) == 0) return _root.value; + if (_root != null) { + int comp = _splay(key); + if (comp == 0) return _root.value; } return null; } V remove(K key) { - if (isEmpty) return null; - splay_(key); - if (_root.key.compareTo(key) != 0) return null; + if (_root == null) return null; + int comp = _splay(key); + if (comp != 0) return null; V value = _root.value; _count--; @@ -129,31 +150,43 @@ SplayTreeNode<K, V> right = _root.right; _root = _root.left; // Splay to make sure that the new root has an empty right child. - splay_(key); + _splay(key); // Insert the original right child as the right child of the new // root. _root.right = right; } + _modificationCount++; return value; } void operator []=(K key, V value) { - if (isEmpty) { + if (_root == null) { _count++; _root = new SplayTreeNode(key, value); + _modificationCount++; return; } // Splay on the key to move the last node on the search path for // the key to the root of the tree. - splay_(key); - if (_root.key.compareTo(key) == 0) { + int comp = _splay(key); + if (comp == 0) { _root.value = value; return; } + _addNewRoot(key, value, comp); + } + + /** + * Adds a new root node with the given [key] or [value]. + * + * The [comp] value is the result of comparing the existing root's key + * with key. + */ + void _addNewRoot(K key, V value, int comp) { SplayTreeNode<K, V> node = new SplayTreeNode(key, value); // assert(_count >= 0); _count++; - if (key.compareTo(_root.key) > 0) { + if (comp < 0) { node.left = _root; node.right = _root.right; _root.right = null; @@ -163,12 +196,34 @@ _root.left = null; } _root = node; + _modificationCount++; } V putIfAbsent(K key, V ifAbsent()) { - if (containsKey(key)) return this[key]; + if (_root == null) { + V value = ifAbsent(); + if (_root != null) { + throw new ConcurrentModificationError(this); + } + _root = new SplayTreeNode(key, value); + _count++; + _modificationCount++; + return value; + } + int comp = _splay(key); + if (comp == 0) return _root.value; + int modificationCount = _modificationCount; + int splayCount = _splayCount; V value = ifAbsent(); - this[key] = value; + if (modificationCount != _modificationCount) { + throw new ConcurrentModificationError(this); + } + if (splayCount != _splayCount) { + comp = _splay(key); + // Key is still not there, otherwise _modificationCount would be changed. + assert(comp != 0); + } + _addNewRoot(key, value, comp); return value; } @@ -179,21 +234,11 @@ } void forEach(void f(K key, V value)) { - List<SplayTreeNode<K, V>> list = new List<SplayTreeNode<K, V>>(); - SplayTreeNode<K, V> current = _root; - while (current != null) { - if (current.left != null) { - list.add(current); - current = current.left; - } else { - f(current.key, current.value); - while (current.right == null) { - if (list.isEmpty) return; - current = list.removeLast(); - f(current.key, current.value); - } - current = current.right; - } + Iterator<SplayTreeNode<K, V>> nodes = + new _SplayTreeNodeIterator<K, V>(this); + while (nodes.moveNext()) { + SplayTreeNode<K, V> node = nodes.current; + f(node.key, node.value); } } @@ -207,11 +252,7 @@ } bool containsKey(K key) { - if (!isEmpty) { - splay_(key); - if (_root.key.compareTo(key) == 0) return true; - } - return false; + return _splay(key) == 0; } bool containsValue(V value) { @@ -219,22 +260,16 @@ bool visit(SplayTreeNode node) { if (node == null) return false; if (node.value == value) return true; + // TODO(lrn): Do we want to handle the case where node.value.operator== + // modifies the map? return visit(node.left) || visit(node.right); } return visit(_root); } - Collection<K> get keys { - List<K> list = new List<K>(); - forEach((K k, V v) { list.add(k); }); - return list; - } + Iterable<K> get keys => new _SplayTreeKeyIterable(this); - Collection<V> get values { - List<V> list = new List<V>(); - forEach((K k, V v) { list.add(v); }); - return list; - } + Iterable<V> get values => new _SplayTreeValueIterable(this); String toString() { return Maps.mapToString(this); @@ -251,7 +286,7 @@ } // Maybe implement a splay-method that can splay the minimum without // performing comparisons. - splay_(node.key); + _splay(node.key); return node.key; } @@ -266,7 +301,7 @@ } // Maybe implement a splay-method that can splay the maximum without // performing comparisons. - splay_(node.key); + _splay(node.key); return node.key; } @@ -275,17 +310,15 @@ * [null] if no key was not found. */ K lastKeyBefore(K key) { - splay_(key); - K visit(SplayTreeNode node, K ifEmpty) { - if (node == null) return ifEmpty; - if (node.key.compareTo(key) >= 0) { - return visit(node.left, ifEmpty); - } - if (node.key.compareTo(key) < 0) { - return visit(node.right, node.key); - } + if (_root == null) return null; + int comp = _splay(key); + if (comp < 0) return _root.key; + SplayTreeNode<K, V> node = _root.left; + if (node == null) return null; + while (node.right != null) { + node = node.right; } - return visit(_root, null); + return node.key; } /** @@ -293,16 +326,138 @@ * [null] if no key was not found. */ K firstKeyAfter(K key) { - splay_(key); - K visit(SplayTreeNode node, K ifEmpty) { - if (node == null) return ifEmpty; - if (node.key.compareTo(key) > 0) { - return visit(node.left, node.key); - } - if (node.key.compareTo(key) <= 0) { - return visit(node.right, ifEmpty); - } + if (_root == null) return null; + int comp = _splay(key); + if (comp > 0) return _root.key; + SplayTreeNode<K, V> node = _root.right; + if (node == null) return null; + while (node.left != null) { + node = node.left; } - return visit(_root, null); + return node.key; } } + +abstract class _SplayTreeIterator<T> implements Iterator<T> { + final SplayTreeMap _map; + /** + * Worklist of nodes to visit. + * + * These nodes have been passed over on the way down in a + * depth-first left-to-right traversal. Visiting each node, + * and their right subtrees will visit the remainder of + * the nodes of a full traversal. + * + * Only valid as long as the original tree map isn't reordered. + */ + final List<SplayTreeNode> _workList = <SplayTreeNode>[]; + + /** + * Original modification counter of [_map]. + * + * Incremented on [_map] when a key is added or removed. + * If it changes, iteration is aborted. + */ + final int _modificationCount; + + /** + * Count of splay operations on [_map] when [_workList] was built. + * + * If the splay count on [_map] increases, [_workList] becomes invalid. + */ + int _splayCount; + + /** Current node. */ + SplayTreeNode _currentNode; + + _SplayTreeIterator(SplayTreeMap map) + : _map = map, + _modificationCount = map._modificationCount, + _splayCount = map._splayCount { + _findLeftMostDescendent(map._root); + } + + T get current { + if (_currentNode == null) return null; + return _getValue(_currentNode); + } + + void _findLeftMostDescendent(SplayTreeNode node) { + while (node != null) { + _workList.add(node); + node = node.left; + } + } + + /** + * Called when the tree structure of the map has changed. + * + * This can be caused by a splay operation. + * If the key-set changes, iteration is aborted before getting + * here, so we know that the keys are the same as before, it's + * only the tree that has been reordered. + */ + void _rebuildWorkList(SplayTreeNode currentNode) { + assert(!_workList.isEmpty); + _workList.clear(); + if (currentNode == null) { + _findLeftMostDescendent(_map._root); + } else { + _map._splay(currentNode.key); + _findLeftMostDescendent(_map._root.right); + assert(!_workList.isEmpty); + } + } + + bool moveNext() { + if (_modificationCount != _map._modificationCount) { + throw new ConcurrentModificationError(_map); + } + // Picks the next element in the worklist as current. + // Updates the worklist with the left-most path of the current node's + // right-hand child. + // If the worklist is no longer valid (after a splay), it is rebuild + // from scratch. + if (_workList.isEmpty) { + _currentNode = null; + return false; + } + if (_map._splayCount != _splayCount) { + _rebuildWorkList(_currentNode); + } + _currentNode = _workList.removeLast(); + _findLeftMostDescendent(_currentNode.right); + return true; + } + + T _getValue(SplayTreeNode node); +} + + +class _SplayTreeKeyIterable<K, V> extends Iterable<K> { + SplayTreeMap<K, V> _map; + _SplayTreeKeyIterable(this._map); + Iterator<K> get iterator => new _SplayTreeKeyIterator<K, V>(_map); +} + +class _SplayTreeValueIterable<K, V> extends Iterable<V> { + SplayTreeMap<K, V> _map; + _SplayTreeValueIterable(this._map) ; + Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map); +} + +class _SplayTreeKeyIterator<K, V> extends _SplayTreeIterator<K> { + _SplayTreeKeyIterator(SplayTreeMap<K, V> map): super(map); + K _getValue(SplayTreeNode node) => node.key; +} + +class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { + _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); + V _getValue(SplayTreeNode node) => node.value; +} + +class _SplayTreeNodeIterator<K, V> + extends _SplayTreeIterator<SplayTreeNode<K, V>> { + _SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map); + SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node; +}
diff --git a/sdk/lib/core/map.dart b/sdk/lib/core/map.dart index 8b27b3e..de3807f 100644 --- a/sdk/lib/core/map.dart +++ b/sdk/lib/core/map.dart
@@ -47,6 +47,9 @@ * If [key] is not associated to a value, calls [ifAbsent] and * updates the map by mapping [key] to the value returned by * [ifAbsent]. Returns the value in the map. + * + * It is an error to add or remove keys from map during the call to + * [ifAbsent]. */ V putIfAbsent(K key, V ifAbsent()); @@ -65,6 +68,8 @@ /** * Applies [f] to each {key, value} pair of the map. + * + * It is an error to add or remove keys from the map during iteration. */ void forEach(void f(K key, V value));
diff --git a/sdk/lib/io/http_impl.dart b/sdk/lib/io/http_impl.dart index 224c1e7..70c6c53 100644 --- a/sdk/lib/io/http_impl.dart +++ b/sdk/lib/io/http_impl.dart
@@ -1917,14 +1917,15 @@ void shutdown({bool force: false}) { if (force) _closeQueue.shutdown(); - _openSockets.forEach((String key, Queue<_SocketConnection> connections) { + new Map.from(_openSockets).forEach( + (String key, Queue<_SocketConnection> connections) { while (!connections.isEmpty) { _SocketConnection socketConn = connections.removeFirst(); socketConn._socket.close(); } }); if (force) { - _activeSockets.forEach((_SocketConnection socketConn) { + _activeSockets.toList().forEach((_SocketConnection socketConn) { socketConn._httpClientConnection._onClientShutdown(); socketConn._close(); });
diff --git a/tests/co19/co19-dart2dart.status b/tests/co19/co19-dart2dart.status index 21a8cce..fc61890 100644 --- a/tests/co19/co19-dart2dart.status +++ b/tests/co19/co19-dart2dart.status
@@ -657,3 +657,20 @@ LibTest/core/Queue/removeLast_A02_t01: Fail # Moved collection classes from core to collection. co19 issue 371. LibTest/core/Set/Set.from_A01_t01: Fail # Moved collection classes from core to collection. co19 issue 371. Language/14_Types/4_Interface_Types_A08_t06: Fail # Moved collection classes from core to collection. co19 issue 371. + +# Doesn't expect null to be allowed in Set or Map keys (issue 377). +LibTest/core/Map/containsKey_A01_t02: Fail +LibTest/core/Map/operator_subscript_A01_t02: Fail +LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail +LibTest/core/Map/remove_A01_t02: Fail +LibTest/core/Set/add_A01_t02: Fail +LibTest/core/Set/addAll_A01_t02: Fail +LibTest/core/Set/contains_A01_t02: Fail +LibTest/core/Set/containsAll_A01_t02: Fail +LibTest/core/Set/intersection_A03_t01: Fail +LibTest/core/Set/isSubsetOf_A01_t02: Fail +LibTest/core/Set/remove_A01_t02: Fail +LibTest/core/Set/removeAll_A01_t02: Fail + +# Doesn't expect concurrent modification error (issue 376). +LibTest/core/Map/forEach_A01_t07: Fail
diff --git a/tests/co19/co19-dart2js.status b/tests/co19/co19-dart2js.status index a54182d..8da7c21 100644 --- a/tests/co19/co19-dart2js.status +++ b/tests/co19/co19-dart2js.status
@@ -787,3 +787,20 @@ Language/14_Types/5_Function_Types_A03_t06: Fail # dartbug.com/7342 Language/14_Types/5_Function_Types_A03_t10: Fail # dartbug.com/7342 Language/14_Types/5_Function_Types_A03_t11: Fail # dartbug.com/7342 + +# Doesn't expect null to be allowed in Set or Map keys (issue 377). +LibTest/core/Map/containsKey_A01_t02: Fail +LibTest/core/Map/operator_subscript_A01_t02: Fail +LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail +LibTest/core/Map/remove_A01_t02: Fail +LibTest/core/Set/add_A01_t02: Fail +LibTest/core/Set/addAll_A01_t02: Fail +LibTest/core/Set/contains_A01_t02: Fail +LibTest/core/Set/containsAll_A01_t02: Fail +LibTest/core/Set/intersection_A03_t01: Fail +LibTest/core/Set/isSubsetOf_A01_t02: Fail +LibTest/core/Set/remove_A01_t02: Fail +LibTest/core/Set/removeAll_A01_t02: Fail + +# Doesn't expect concurrent modification error (issue 376). +LibTest/core/Map/forEach_A01_t07: Fail
diff --git a/tests/co19/co19-runtime.status b/tests/co19/co19-runtime.status index 09f39d0..6a312f5 100644 --- a/tests/co19/co19-runtime.status +++ b/tests/co19/co19-runtime.status
@@ -504,6 +504,23 @@ LibTest/core/Queue/removeLast_A02_t01: Fail # Moved collection classes from core to collection. co19 issue 371. LibTest/core/Set/Set.from_A01_t01: Fail # Moved collection classes from core to collection. co19 issue 371. +# Doesn't expect null to be allowed in Set or Map keys (issue 377). +LibTest/core/Map/containsKey_A01_t02: Fail +LibTest/core/Map/operator_subscript_A01_t02: Fail +LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail +LibTest/core/Map/remove_A01_t02: Fail +LibTest/core/Set/add_A01_t02: Fail +LibTest/core/Set/addAll_A01_t02: Fail +LibTest/core/Set/contains_A01_t02: Fail +LibTest/core/Set/containsAll_A01_t02: Fail +LibTest/core/Set/intersection_A03_t01: Fail +LibTest/core/Set/isSubsetOf_A01_t02: Fail +LibTest/core/Set/remove_A01_t02: Fail +LibTest/core/Set/removeAll_A01_t02: Fail + +# Doesn't expect concurrent modification error (issue 376). +LibTest/core/Map/forEach_A01_t07: Fail + [ $compiler == none && $runtime == vm && $unchecked ] LibTest/core/Future/chain_A02_t05: Fail # Future is in async library. co19 issue 367 LibTest/core/Future/transform_A02_t04: Fail # Future is in async library. co19 issue 367
diff --git a/tests/corelib/hash_map2_test.dart b/tests/corelib/hash_map2_test.dart new file mode 100644 index 0000000..9f81c9f --- /dev/null +++ b/tests/corelib/hash_map2_test.dart
@@ -0,0 +1,289 @@ +// 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. + +// Tests of hash map behavior, with focus in iteration and concurrent +// modification errors. + +library hash_map2_test; +import 'dart:collection'; + +testMap(Map newMap(), Map newMapFrom(Map map)) { + Map gen(int from, int to) { + Map map = new LinkedHashMap(); + for (int i = from; i < to; i++) map[i] = i; + return map; + } + + bool odd(int n) => (n & 1) == 1; + bool even(int n) => (n & 1) == 0; + void addAll(Map toMap, Map fromMap) { + fromMap.forEach((k, v) { toMap[k] = v; }); + } + + { // Test growing to largish capacity. + Map map = newMap(); + + for (int i = 0; i < 256; i++) { + map[i] = i; + } + addAll(map, gen(256, 512)); + addAll(map, newMapFrom(gen(512, 1000))); + Expect.equals(1000, map.length); + + // Remove half. + for (int i = 0; i < 1000; i += 2) map.remove(i); + Expect.equals(500, map.length); + Expect.isFalse(map.keys.any(even)); + Expect.isTrue(map.keys.every(odd)); + + // Re-add all. + addAll(map, gen(0, 1000)); + Expect.equals(1000, map.length); + } + + { // Test having many deleted elements. + Map map = newMap(); + map[0] = 0; + for (int i = 0; i < 1000; i++) { + map[i + 1] = i + 1; + map.remove(i); + Expect.equals(1, map.length); + } + } + + { // Test having many elements with same hashCode + Map map = newMap(); + for (int i = 0; i < 1000; i++) { + map[new BadHashCode()] = 0; + } + Expect.equals(1000, map.length); + } + + { // Check concurrent modification + Map map = newMap()..[0] = 0..[1] = 1; + + { // Test adding before a moveNext. + Iterator iter = map.keys.iterator; + iter.moveNext(); + map[1] = 9; // Updating existing key isn't a modification. + iter.moveNext(); + map[2] = 2; + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test adding after last element. + Iterator iter = map.keys.iterator; + Expect.equals(3, map.length); + iter.moveNext(); + iter.moveNext(); + iter.moveNext(); + map[3] = 3; + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test removing during iteration. + Iterator iter = map.keys.iterator; + iter.moveNext(); + map.remove(1000); // Not a modification if it's not there. + iter.moveNext(); + int n = iter.current; + map.remove(n); + // Removing doesn't change current. + Expect.equals(n, iter.current); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test removing after last element. + Iterator iter = map.keys.iterator; + Expect.equals(3, map.length); + iter.moveNext(); + iter.moveNext(); + iter.moveNext(); + int n = iter.current; + map.remove(n); + // Removing doesn't change current. + Expect.equals(n, iter.current); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test that updating value of existing key doesn't cause concurrent + // modification error. + Iterator iter = map.keys.iterator; + Expect.equals(2, map.length); + iter.moveNext(); + int n = iter.current; + map[n] = n * 2; + iter.moveNext(); + Expect.equals(map[iter.current], iter.current); + } + + { // Test that modification during putIfAbsent is not an error. + map.putIfAbsent(4, () { + map[5] = 5; + map[4] = -1; + return 4; + }); + Expect.equals(4, map[4]); + Expect.equals(5, map[5]); + } + + { // Check adding many existing keys isn't considered modification. + Map map2 = newMap(); + for (var key in map.keys) { + map2[key] = map[key] + 1; + } + Iterator iter = map.keys.iterator; + addAll(map, map2); + // Shouldn't throw. + iter.moveNext(); + } + } + + { // Regression test for bug in putIfAbsent where adding an element + // that make the table grow, can be lost. + Map map = newMap(); + map.putIfAbsent("S", () => 0); + map.putIfAbsent("T", () => 0); + map.putIfAbsent("U", () => 0); + map.putIfAbsent("C", () => 0); + map.putIfAbsent("a", () => 0); + map.putIfAbsent("b", () => 0); + map.putIfAbsent("n", () => 0); + Expect.isTrue(map.containsKey("n")); + } + + { // Check that putIfAbsent works just as well as put. + Map map = newMap(); + for (int i = 0; i < 128; i++) { + map.putIfAbsent(i, () => i); + Expect.isTrue(map.containsKey(i)); + map.putIfAbsent(i >> 1, () => -1); // Never triggers. + } + for (int i = 0; i < 128; i++) { + Expect.equals(i, map[i]); + } + } + + { // Check that updating existing elements is not a modification. + // This must be the case even if the underlying data structure is + // nearly full. + for (int i = 1; i < 128; i++) { + // Create maps of different sizes, some of which should be + // at a limit of the underlying data structure. + Map map = newMapFrom(gen(0, i)); + + // ForEach-iteration. + map.forEach((key, v) { + Expect.equals(key, map[key]); + map[key] = key + 1; + map.remove(1000); // Removing something not there. + map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); + // Doesn't cause ConcurrentModificationError. + }); + + // for-in iteration. + for (int key in map.keys) { + Expect.equals(key + 1, map[key]); + map[key] = map[key] + 1; + map.remove(1000); // Removing something not there. + map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); + // Doesn't cause ConcurrentModificationError. + } + + // Raw iterator. + Iterator iter = map.keys.iterator; + for (int key = 0; key < i; key++) { + Expect.equals(key + 2, map[key]); + map[key] = key + 3; + map.remove(1000); // Removing something not there. + map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); + // Doesn't cause ConcurrentModificationError on the moveNext. + } + iter.moveNext(); // Should not throw. + + // Remove a lot of elements, which can cause a re-tabulation. + for (int key = 1; key < i; key++) { + Expect.equals(key + 3, map[key]); + map.remove(key); + } + iter = map.keys.iterator; + map[0] = 2; + iter.moveNext(); // Should not throw. + } + } + + + { // Check that null can be in the map. + Map map = newMap(); + map[null] = 0; + Expect.equals(1, map.length); + Expect.isTrue(map.containsKey(null)); + Expect.isNull(map.keys.first); + Expect.isNull(map.keys.last); + map[null] = 1; + Expect.equals(1, map.length); + Expect.isTrue(map.containsKey(null)); + map.remove(null); + Expect.isTrue(map.isEmpty); + Expect.isFalse(map.containsKey(null)); + + // Created using map.from. + map = newMapFrom(new Map()..[null] = 0); + Expect.equals(1, map.length); + Expect.isTrue(map.containsKey(null)); + Expect.isNull(map.keys.first); + Expect.isNull(map.keys.last); + map[null] = 1; + Expect.equals(1, map.length); + Expect.isTrue(map.containsKey(null)); + map.remove(null); + Expect.isTrue(map.isEmpty); + Expect.isFalse(map.containsKey(null)); + + Map fromMap = new Map(); + fromMap[1] = 0; + fromMap[2] = 0; + fromMap[3] = 0; + fromMap[null] = 0; + fromMap[4] = 0; + fromMap[5] = 0; + fromMap[6] = 0; + Expect.equals(7, fromMap.length); + + // map that grows with null in it. + map = newMapFrom(fromMap); + Expect.equals(7, map.length); + for (int i = 7; i < 128; i++) { + map[i] = 0; + } + Expect.equals(128, map.length); + Expect.isTrue(map.containsKey(null)); + map[null] = 1; + Expect.equals(128, map.length); + Expect.isTrue(map.containsKey(null)); + map.remove(null); + Expect.equals(127, map.length); + Expect.isFalse(map.containsKey(null)); + } +} + +void main() { + Expect.isTrue(new HashMap<int, String>() is Map<int, String>); + Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>); + Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>); + Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>); + Expect.isTrue(<String, int>{} is Map<String, int>); + Expect.isTrue(const <String, int>{} is Map<String, int>); + + testMap(() => new HashMap(), (m) => new HashMap.from(m)); + testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m)); +} + + +class BadHashCode { + static int idCounter = 0; + final int id; + BadHashCode() : id = idCounter++; + int get hashCode => 42; +}
diff --git a/tests/corelib/hash_set_test.dart b/tests/corelib/hash_set_test.dart new file mode 100644 index 0000000..68a0844 --- /dev/null +++ b/tests/corelib/hash_set_test.dart
@@ -0,0 +1,206 @@ +// 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. + +// Tests of hash set behavior, with focus in iteration and concurrent +// modification errors. + +library hash_map2_test; +import 'dart:collection'; + +testSet(Set newSet(), Set newSetFrom(Set from)) { + Set gen(int from, int to) => + new Set.from(new Iterable.generate(to - from, (n) => n + from)); + + bool odd(int n) => (n & 1) == 1; + bool even(int n) => (n & 1) == 0; + + { // Test growing to largish capacity. + Set set = newSet(); + + for (int i = 0; i < 256; i++) { + set.add(i); + } + set.addAll(gen(256, 512)); + set.addAll(newSetFrom(gen(512, 1000))); + Expect.equals(1000, set.length); + + // Remove half. + for (int i = 0; i < 1000; i += 2) set.remove(i); + Expect.equals(500, set.length); + Expect.isFalse(set.any(even)); + Expect.isTrue(set.every(odd)); + + // Re-add all. + set.addAll(gen(0, 1000)); + Expect.equals(1000, set.length); + } + + { // Test having many deleted elements. + Set set = newSet(); + set.add(0); + for (int i = 0; i < 1000; i++) { + set.add(i + 1); + set.remove(i); + Expect.equals(1, set.length); + } + } + + { // Test having many elements with same hashCode + Set set = newSet(); + for (int i = 0; i < 1000; i++) { + set.add(new BadHashCode()); + } + Expect.equals(1000, set.length); + } + + { // Check concurrent modification + Set set = newSet()..add(0)..add(1); + + { // Test adding before a moveNext. + Iterator iter = set.iterator; + iter.moveNext(); + set.add(1); // Updating existing key isn't a modification. + iter.moveNext(); + set.add(2); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test adding after last element. + Iterator iter = set.iterator; + Expect.equals(3, set.length); + iter.moveNext(); + iter.moveNext(); + iter.moveNext(); + set.add(3); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test removing during iteration. + Iterator iter = set.iterator; + iter.moveNext(); + set.remove(1000); // Not a modification if it's not there. + iter.moveNext(); + int n = iter.current; + set.remove(n); + // Removing doesn't change current. + Expect.equals(n, iter.current); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test removing after last element. + Iterator iter = set.iterator; + Expect.equals(3, set.length); + iter.moveNext(); + iter.moveNext(); + iter.moveNext(); + int n = iter.current; + set.remove(n); + // Removing doesn't change current. + Expect.equals(n, iter.current); + Expect.throws(iter.moveNext, (e) => e is Error); + } + + { // Test that updating value doesn't cause error. + Iterator iter = set.iterator; + Expect.equals(2, set.length); + iter.moveNext(); + int n = iter.current; + set.add(n); + iter.moveNext(); + Expect.isTrue(set.contains(iter.current)); + } + + { // Check adding many existing values isn't considered modification. + Set set2 = newSet(); + for (var value in set) { + set2.add(value); + } + Iterator iter = set.iterator; + set.addAll(set2); + // Shouldn't throw. + iter.moveNext(); + } + } + + { // Check that updating existing elements is not a modification. + // This must be the case even if the underlying data structure is + // nearly full. + for (int i = 1; i < 128; i++) { + // Create maps of different sizes, some of which should be + // at a limit of the underlying data structure. + Set set = newSetFrom(gen(0, i)); + Iterator iter = set.iterator; + for (int j = 0; j < i; j++) { + set.add(j); + } + iter.moveNext(); // Should not throw. + + for (int j = 1; j < i; j++) { + set.remove(j); + } + iter = set.iterator; + set.add(0); + iter.moveNext(); // Should not throw. + } + } + + { // Check that null can be in the set. + Set set = newSet(); + set.add(null); + Expect.equals(1, set.length); + Expect.isTrue(set.contains(null)); + Expect.isNull(set.first); + Expect.isNull(set.last); + set.add(null); + Expect.equals(1, set.length); + Expect.isTrue(set.contains(null)); + set.remove(null); + Expect.isTrue(set.isEmpty); + Expect.isFalse(set.contains(null)); + + // Created using Set.from. + set = newSetFrom([null]); + Expect.equals(1, set.length); + Expect.isTrue(set.contains(null)); + Expect.isNull(set.first); + Expect.isNull(set.last); + set.add(null); + Expect.equals(1, set.length); + Expect.isTrue(set.contains(null)); + set.remove(null); + Expect.isTrue(set.isEmpty); + Expect.isFalse(set.contains(null)); + + // Set that grows with null in it. + set = newSetFrom([1, 2, 3, null, 4, 5, 6]); + Expect.equals(7, set.length); + for (int i = 7; i < 128; i++) { + set.add(i); + } + Expect.equals(128, set.length); + Expect.isTrue(set.contains(null)); + set.add(null); + Expect.equals(128, set.length); + Expect.isTrue(set.contains(null)); + set.remove(null); + Expect.equals(127, set.length); + Expect.isFalse(set.contains(null)); + } +} + +void main() { + testSet(() => new HashSet(), (m) => new HashSet.from(m)); + testSet(() => new LinkedHashSet(), (m) => new LinkedHashSet.from(m)); +} + + +class BadHashCode { + static int idCounter = 0; + final int id; + BadHashCode() : id = idCounter++; + int get hashCode => 42; + // operator == is identity. + // Can't make a bad compareTo that isn't invalid. + int compareTo(BadHashCode other) => id - other.id; +}
diff --git a/tests/corelib/map_from_test.dart b/tests/corelib/map_from_test.dart index bc47e9d..b43a45d 100644 --- a/tests/corelib/map_from_test.dart +++ b/tests/corelib/map_from_test.dart
@@ -71,7 +71,7 @@ var map = const { 'b': 1, 'a': 2, 'c': 3 }; var otherMap = new LinkedHashMap.from(map); Expect.isTrue(otherMap is Map); - Expect.isTrue(otherMap is HashMap); + Expect.isTrue(otherMap is! HashMap); Expect.isTrue(otherMap is LinkedHashMap); var i = 1; for (var val in map.values) {
diff --git a/tests/standalone/standalone.status b/tests/standalone/standalone.status index 9652300..cbaa158 100644 --- a/tests/standalone/standalone.status +++ b/tests/standalone/standalone.status
@@ -45,6 +45,7 @@ [ $runtime == vm && $system == windows ] io/file_system_links_test: Skip # No links on Windows. +io/socket_stream_close_test: Fail, Pass # Issue 8556. [ $compiler == none && $runtime == drt ] io/*: Skip # Don't run tests using dart:io in the browser
diff --git a/tools/VERSION b/tools/VERSION index 57771f2..8b85f04 100644 --- a/tools/VERSION +++ b/tools/VERSION
@@ -1,4 +1,4 @@ MAJOR 0 MINOR 3 BUILD 7 -PATCH 2 +PATCH 3
diff --git a/utils/pub/pub.dart b/utils/pub/pub.dart index 569c63c..00abe4c 100644 --- a/utils/pub/pub.dart +++ b/utils/pub/pub.dart
@@ -42,7 +42,7 @@ 'uploader': new UploaderCommand(), 'version': new VersionCommand() }; - for (var command in commands.values) { + for (var command in commands.values.toList()) { for (var alias in command.aliases) { commands[alias] = command; }