| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 // Patch file for dart:collection classes. | |
| 6 import 'dart:_foreign_helper' show JS; | |
| 7 import 'dart:_js_helper' show | |
| 8 fillLiteralMap, InternalMap, NoInline, NoSideEffects, NoThrows, patch, | |
| 9 JsLinkedHashMap, LinkedHashMapCell, LinkedHashMapKeyIterable, | |
| 10 LinkedHashMapKeyIterator; | |
| 11 | |
| 12 const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); | |
| 13 | |
| 14 @patch | |
| 15 class HashMap<K, V> { | |
| 16 @patch | |
| 17 factory HashMap({ bool equals(K key1, K key2), | |
| 18 int hashCode(K key), | |
| 19 bool isValidKey(potentialKey) }) { | |
| 20 if (isValidKey == null) { | |
| 21 if (hashCode == null) { | |
| 22 if (equals == null) { | |
| 23 return new _HashMap<K, V>(); | |
| 24 } | |
| 25 hashCode = _defaultHashCode; | |
| 26 } else { | |
| 27 if (identical(identityHashCode, hashCode) && | |
| 28 identical(identical, equals)) { | |
| 29 return new _IdentityHashMap<K, V>(); | |
| 30 } | |
| 31 if (equals == null) { | |
| 32 equals = _defaultEquals; | |
| 33 } | |
| 34 } | |
| 35 } else { | |
| 36 if (hashCode == null) { | |
| 37 hashCode = _defaultHashCode; | |
| 38 } | |
| 39 if (equals == null) { | |
| 40 equals = _defaultEquals; | |
| 41 } | |
| 42 } | |
| 43 return new _CustomHashMap<K, V>(equals, hashCode, isValidKey); | |
| 44 } | |
| 45 | |
| 46 @patch | |
| 47 factory HashMap.identity() = _IdentityHashMap<K, V>; | |
| 48 } | |
| 49 | |
| 50 class _HashMap<K, V> implements HashMap<K, V> { | |
| 51 int _length = 0; | |
| 52 | |
| 53 // The hash map contents are divided into three parts: one part for | |
| 54 // string keys, one for numeric keys, and one for the rest. String | |
| 55 // and numeric keys map directly to their values, but the rest of | |
| 56 // the entries are stored in bucket lists of the form: | |
| 57 // | |
| 58 // [key-0, value-0, key-1, value-1, ...] | |
| 59 // | |
| 60 // where all keys in the same bucket share the same hash code. | |
| 61 var _strings; | |
| 62 var _nums; | |
| 63 var _rest; | |
| 64 | |
| 65 // When iterating over the hash map, it is very convenient to have a | |
| 66 // list of all the keys. We cache that on the instance and clear the | |
| 67 // the cache whenever the key set changes. This is also used to | |
| 68 // guard against concurrent modifications. | |
| 69 List _keys; | |
| 70 | |
| 71 _HashMap(); | |
| 72 | |
| 73 | |
| 74 int get length => _length; | |
| 75 bool get isEmpty => _length == 0; | |
| 76 bool get isNotEmpty => !isEmpty; | |
| 77 | |
| 78 Iterable<K> get keys { | |
| 79 return new HashMapKeyIterable<K>(this); | |
| 80 } | |
| 81 | |
| 82 Iterable<V> get values { | |
| 83 return new MappedIterable<K, V>(keys, (each) => this[each]); | |
| 84 } | |
| 85 | |
| 86 bool containsKey(Object key) { | |
| 87 if (_isStringKey(key)) { | |
| 88 var strings = _strings; | |
| 89 return (strings == null) ? false : _hasTableEntry(strings, key); | |
| 90 } else if (_isNumericKey(key)) { | |
| 91 var nums = _nums; | |
| 92 return (nums == null) ? false : _hasTableEntry(nums, key); | |
| 93 } else { | |
| 94 return _containsKey(key); | |
| 95 } | |
| 96 } | |
| 97 | |
| 98 bool _containsKey(Object key) { | |
| 99 var rest = _rest; | |
| 100 if (rest == null) return false; | |
| 101 var bucket = _getBucket(rest, key); | |
| 102 return _findBucketIndex(bucket, key) >= 0; | |
| 103 } | |
| 104 | |
| 105 bool containsValue(Object value) { | |
| 106 return _computeKeys().any((each) => this[each] == value); | |
| 107 } | |
| 108 | |
| 109 void addAll(Map<K, V> other) { | |
| 110 other.forEach((K key, V value) { | |
| 111 this[key] = value; | |
| 112 }); | |
| 113 } | |
| 114 | |
| 115 V operator[](Object key) { | |
| 116 if (_isStringKey(key)) { | |
| 117 var strings = _strings; | |
| 118 return (strings == null) ? null : _getTableEntry(strings, key); | |
| 119 } else if (_isNumericKey(key)) { | |
| 120 var nums = _nums; | |
| 121 return (nums == null) ? null : _getTableEntry(nums, key); | |
| 122 } else { | |
| 123 return _get(key); | |
| 124 } | |
| 125 } | |
| 126 | |
| 127 V _get(Object key) { | |
| 128 var rest = _rest; | |
| 129 if (rest == null) return null; | |
| 130 var bucket = _getBucket(rest, key); | |
| 131 int index = _findBucketIndex(bucket, key); | |
| 132 return (index < 0) ? null : JS('var', '#[#]', bucket, index + 1); | |
| 133 } | |
| 134 | |
| 135 void operator[]=(K key, V value) { | |
| 136 if (_isStringKey(key)) { | |
| 137 var strings = _strings; | |
| 138 if (strings == null) _strings = strings = _newHashTable(); | |
| 139 _addHashTableEntry(strings, key, value); | |
| 140 } else if (_isNumericKey(key)) { | |
| 141 var nums = _nums; | |
| 142 if (nums == null) _nums = nums = _newHashTable(); | |
| 143 _addHashTableEntry(nums, key, value); | |
| 144 } else { | |
| 145 _set(key, value); | |
| 146 } | |
| 147 } | |
| 148 | |
| 149 void _set(K key, V value) { | |
| 150 var rest = _rest; | |
| 151 if (rest == null) _rest = rest = _newHashTable(); | |
| 152 var hash = _computeHashCode(key); | |
| 153 var bucket = JS('var', '#[#]', rest, hash); | |
| 154 if (bucket == null) { | |
| 155 _setTableEntry(rest, hash, JS('var', '[#, #]', key, value)); | |
| 156 _length++; | |
| 157 _keys = null; | |
| 158 } else { | |
| 159 int index = _findBucketIndex(bucket, key); | |
| 160 if (index >= 0) { | |
| 161 JS('void', '#[#] = #', bucket, index + 1, value); | |
| 162 } else { | |
| 163 JS('void', '#.push(#, #)', bucket, key, value); | |
| 164 _length++; | |
| 165 _keys = null; | |
| 166 } | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 V putIfAbsent(K key, V ifAbsent()) { | |
| 171 if (containsKey(key)) return this[key]; | |
| 172 V value = ifAbsent(); | |
| 173 this[key] = value; | |
| 174 return value; | |
| 175 } | |
| 176 | |
| 177 V remove(Object key) { | |
| 178 if (_isStringKey(key)) { | |
| 179 return _removeHashTableEntry(_strings, key); | |
| 180 } else if (_isNumericKey(key)) { | |
| 181 return _removeHashTableEntry(_nums, key); | |
| 182 } else { | |
| 183 return _remove(key); | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 V _remove(Object key) { | |
| 188 var rest = _rest; | |
| 189 if (rest == null) return null; | |
| 190 var bucket = _getBucket(rest, key); | |
| 191 int index = _findBucketIndex(bucket, key); | |
| 192 if (index < 0) return null; | |
| 193 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 194 // the length reaches zero. | |
| 195 _length--; | |
| 196 _keys = null; | |
| 197 // Use splice to remove the two [key, value] elements at the | |
| 198 // index and return the value. | |
| 199 return JS('var', '#.splice(#, 2)[1]', bucket, index); | |
| 200 } | |
| 201 | |
| 202 void clear() { | |
| 203 if (_length > 0) { | |
| 204 _strings = _nums = _rest = _keys = null; | |
| 205 _length = 0; | |
| 206 } | |
| 207 } | |
| 208 | |
| 209 void forEach(void action(K key, V value)) { | |
| 210 List keys = _computeKeys(); | |
| 211 for (int i = 0, length = keys.length; i < length; i++) { | |
| 212 var key = JS('var', '#[#]', keys, i); | |
| 213 action(key, this[key]); | |
| 214 if (JS('bool', '# !== #', keys, _keys)) { | |
| 215 throw new ConcurrentModificationError(this); | |
| 216 } | |
| 217 } | |
| 218 } | |
| 219 | |
| 220 List _computeKeys() { | |
| 221 if (_keys != null) return _keys; | |
| 222 List result = new List(_length); | |
| 223 int index = 0; | |
| 224 | |
| 225 // Add all string keys to the list. | |
| 226 var strings = _strings; | |
| 227 if (strings != null) { | |
| 228 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 229 int entries = JS('int', '#.length', names); | |
| 230 for (int i = 0; i < entries; i++) { | |
| 231 String key = JS('String', '#[#]', names, i); | |
| 232 JS('void', '#[#] = #', result, index, key); | |
| 233 index++; | |
| 234 } | |
| 235 } | |
| 236 | |
| 237 // Add all numeric keys to the list. | |
| 238 var nums = _nums; | |
| 239 if (nums != null) { | |
| 240 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 241 int entries = JS('int', '#.length', names); | |
| 242 for (int i = 0; i < entries; i++) { | |
| 243 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 244 // have to convert the keys back to numbers (+). | |
| 245 num key = JS('num', '+#[#]', names, i); | |
| 246 JS('void', '#[#] = #', result, index, key); | |
| 247 index++; | |
| 248 } | |
| 249 } | |
| 250 | |
| 251 // Add all the remaining keys to the list. | |
| 252 var rest = _rest; | |
| 253 if (rest != null) { | |
| 254 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 255 int entries = JS('int', '#.length', names); | |
| 256 for (int i = 0; i < entries; i++) { | |
| 257 var key = JS('String', '#[#]', names, i); | |
| 258 var bucket = JS('var', '#[#]', rest, key); | |
| 259 int length = JS('int', '#.length', bucket); | |
| 260 for (int i = 0; i < length; i += 2) { | |
| 261 var key = JS('var', '#[#]', bucket, i); | |
| 262 JS('void', '#[#] = #', result, index, key); | |
| 263 index++; | |
| 264 } | |
| 265 } | |
| 266 } | |
| 267 assert(index == _length); | |
| 268 return _keys = result; | |
| 269 } | |
| 270 | |
| 271 void _addHashTableEntry(var table, K key, V value) { | |
| 272 if (!_hasTableEntry(table, key)) { | |
| 273 _length++; | |
| 274 _keys = null; | |
| 275 } | |
| 276 _setTableEntry(table, key, value); | |
| 277 } | |
| 278 | |
| 279 V _removeHashTableEntry(var table, Object key) { | |
| 280 if (table != null && _hasTableEntry(table, key)) { | |
| 281 V value = _getTableEntry(table, key); | |
| 282 _deleteTableEntry(table, key); | |
| 283 _length--; | |
| 284 _keys = null; | |
| 285 return value; | |
| 286 } else { | |
| 287 return null; | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 static bool _isStringKey(var key) { | |
| 292 return key is String && key != '__proto__'; | |
| 293 } | |
| 294 | |
| 295 static bool _isNumericKey(var key) { | |
| 296 // Only treat unsigned 30-bit integers as numeric keys. This way, | |
| 297 // we avoid converting them to strings when we use them as keys in | |
| 298 // the JavaScript hash table object. | |
| 299 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 300 } | |
| 301 | |
| 302 int _computeHashCode(var key) { | |
| 303 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 304 // issues with problematic keys like '__proto__'. Another option | |
| 305 // would be to throw an exception if the hash code isn't a number. | |
| 306 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 307 } | |
| 308 | |
| 309 static bool _hasTableEntry(var table, var key) { | |
| 310 var entry = JS('var', '#[#]', table, key); | |
| 311 // We take care to only store non-null entries in the table, so we | |
| 312 // can check if the table has an entry for the given key with a | |
| 313 // simple null check. | |
| 314 return entry != null; | |
| 315 } | |
| 316 | |
| 317 static _getTableEntry(var table, var key) { | |
| 318 var entry = JS('var', '#[#]', table, key); | |
| 319 // We store the table itself as the entry to signal that it really | |
| 320 // is a null value, so we have to map back to null here. | |
| 321 return JS('bool', '# === #', entry, table) ? null : entry; | |
| 322 } | |
| 323 | |
| 324 static void _setTableEntry(var table, var key, var value) { | |
| 325 // We only store non-null entries in the table, so we have to | |
| 326 // change null values to refer to the table itself. Such values | |
| 327 // will be recognized and mapped back to null on access. | |
| 328 if (value == null) { | |
| 329 // Do not update [value] with [table], otherwise our | |
| 330 // optimizations could be confused by this opaque object being | |
| 331 // now used for more things than storing and fetching from it. | |
| 332 JS('void', '#[#] = #', table, key, table); | |
| 333 } else { | |
| 334 JS('void', '#[#] = #', table, key, value); | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 static void _deleteTableEntry(var table, var key) { | |
| 339 JS('void', 'delete #[#]', table, key); | |
| 340 } | |
| 341 | |
| 342 List _getBucket(var table, var key) { | |
| 343 var hash = _computeHashCode(key); | |
| 344 return JS('var', '#[#]', table, hash); | |
| 345 } | |
| 346 | |
| 347 int _findBucketIndex(var bucket, var key) { | |
| 348 if (bucket == null) return -1; | |
| 349 int length = JS('int', '#.length', bucket); | |
| 350 for (int i = 0; i < length; i += 2) { | |
| 351 if (JS('var', '#[#]', bucket, i) == key) return i; | |
| 352 } | |
| 353 return -1; | |
| 354 } | |
| 355 | |
| 356 static _newHashTable() { | |
| 357 // Create a new JavaScript object to be used as a hash table. Use | |
| 358 // Object.create to avoid the properties on Object.prototype | |
| 359 // showing up as entries. | |
| 360 var table = JS('var', 'Object.create(null)'); | |
| 361 // Attempt to force the hash table into 'dictionary' mode by | |
| 362 // adding a property to it and deleting it again. | |
| 363 var temporaryKey = '<non-identifier-key>'; | |
| 364 _setTableEntry(table, temporaryKey, table); | |
| 365 _deleteTableEntry(table, temporaryKey); | |
| 366 return table; | |
| 367 } | |
| 368 } | |
| 369 | |
| 370 class _IdentityHashMap<K, V> extends _HashMap<K, V> { | |
| 371 int _computeHashCode(var key) { | |
| 372 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 373 // issues with problematic keys like '__proto__'. Another option | |
| 374 // would be to throw an exception if the hash code isn't a number. | |
| 375 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 376 } | |
| 377 | |
| 378 int _findBucketIndex(var bucket, var key) { | |
| 379 if (bucket == null) return -1; | |
| 380 int length = JS('int', '#.length', bucket); | |
| 381 for (int i = 0; i < length; i += 2) { | |
| 382 if (identical(JS('var', '#[#]', bucket, i), key)) return i; | |
| 383 } | |
| 384 return -1; | |
| 385 } | |
| 386 } | |
| 387 | |
| 388 class _CustomHashMap<K, V> extends _HashMap<K, V> { | |
| 389 final _Equality<K> _equals; | |
| 390 final _Hasher<K> _hashCode; | |
| 391 final _Predicate _validKey; | |
| 392 | |
| 393 _CustomHashMap(this._equals, this._hashCode, bool validKey(potentialKey)) | |
| 394 : _validKey = (validKey != null) ? validKey : ((v) => v is K); | |
| 395 | |
| 396 V operator[](Object key) { | |
| 397 if (!_validKey(key)) return null; | |
| 398 return super._get(key); | |
| 399 } | |
| 400 | |
| 401 void operator[]=(K key, V value) { | |
| 402 super._set(key, value); | |
| 403 } | |
| 404 | |
| 405 bool containsKey(Object key) { | |
| 406 if (!_validKey(key)) return false; | |
| 407 return super._containsKey(key); | |
| 408 } | |
| 409 | |
| 410 V remove(Object key) { | |
| 411 if (!_validKey(key)) return null; | |
| 412 return super._remove(key); | |
| 413 } | |
| 414 | |
| 415 int _computeHashCode(var key) { | |
| 416 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 417 // issues with problematic keys like '__proto__'. Another option | |
| 418 // would be to throw an exception if the hash code isn't a number. | |
| 419 return JS('int', '# & 0x3ffffff', _hashCode(key)); | |
| 420 } | |
| 421 | |
| 422 int _findBucketIndex(var bucket, var key) { | |
| 423 if (bucket == null) return -1; | |
| 424 int length = JS('int', '#.length', bucket); | |
| 425 for (int i = 0; i < length; i += 2) { | |
| 426 if (_equals(JS('var', '#[#]', bucket, i), key)) return i; | |
| 427 } | |
| 428 return -1; | |
| 429 } | |
| 430 | |
| 431 String toString() => Maps.mapToString(this); | |
| 432 } | |
| 433 | |
| 434 class HashMapKeyIterable<E> extends Iterable<E> | |
| 435 implements EfficientLength { | |
| 436 final _map; | |
| 437 HashMapKeyIterable(this._map); | |
| 438 | |
| 439 int get length => _map._length; | |
| 440 bool get isEmpty => _map._length == 0; | |
| 441 | |
| 442 Iterator<E> get iterator { | |
| 443 return new HashMapKeyIterator<E>(_map, _map._computeKeys()); | |
| 444 } | |
| 445 | |
| 446 bool contains(Object element) { | |
| 447 return _map.containsKey(element); | |
| 448 } | |
| 449 | |
| 450 void forEach(void f(E element)) { | |
| 451 List keys = _map._computeKeys(); | |
| 452 for (int i = 0, length = JS('int', '#.length', keys); i < length; i++) { | |
| 453 f(JS('var', '#[#]', keys, i)); | |
| 454 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 455 throw new ConcurrentModificationError(_map); | |
| 456 } | |
| 457 } | |
| 458 } | |
| 459 } | |
| 460 | |
| 461 class HashMapKeyIterator<E> implements Iterator<E> { | |
| 462 final _map; | |
| 463 final List _keys; | |
| 464 int _offset = 0; | |
| 465 E _current; | |
| 466 | |
| 467 HashMapKeyIterator(this._map, this._keys); | |
| 468 | |
| 469 E get current => _current; | |
| 470 | |
| 471 bool moveNext() { | |
| 472 var keys = _keys; | |
| 473 int offset = _offset; | |
| 474 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 475 throw new ConcurrentModificationError(_map); | |
| 476 } else if (offset >= JS('int', '#.length', keys)) { | |
| 477 _current = null; | |
| 478 return false; | |
| 479 } else { | |
| 480 _current = JS('var', '#[#]', keys, offset); | |
| 481 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 482 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 483 // get unnecessary bailout code. | |
| 484 _offset = JS('int', '#', offset + 1); | |
| 485 return true; | |
| 486 } | |
| 487 } | |
| 488 } | |
| 489 | |
| 490 @patch | |
| 491 class LinkedHashMap<K, V> { | |
| 492 @patch | |
| 493 factory LinkedHashMap({ bool equals(K key1, K key2), | |
| 494 int hashCode(K key), | |
| 495 bool isValidKey(potentialKey) }) { | |
| 496 if (isValidKey == null) { | |
| 497 if (hashCode == null) { | |
| 498 if (equals == null) { | |
| 499 return new JsLinkedHashMap<K, V>.es6(); | |
| 500 } | |
| 501 hashCode = _defaultHashCode; | |
| 502 } else { | |
| 503 if (identical(identityHashCode, hashCode) && | |
| 504 identical(identical, equals)) { | |
| 505 return new _LinkedIdentityHashMap<K, V>.es6(); | |
| 506 } | |
| 507 if (equals == null) { | |
| 508 equals = _defaultEquals; | |
| 509 } | |
| 510 } | |
| 511 } else { | |
| 512 if (hashCode == null) { | |
| 513 hashCode = _defaultHashCode; | |
| 514 } | |
| 515 if (equals == null) { | |
| 516 equals = _defaultEquals; | |
| 517 } | |
| 518 } | |
| 519 return new _LinkedCustomHashMap<K, V>(equals, hashCode, isValidKey); | |
| 520 } | |
| 521 | |
| 522 @patch | |
| 523 factory LinkedHashMap.identity() = _LinkedIdentityHashMap<K, V>.es6; | |
| 524 | |
| 525 // Private factory constructor called by generated code for map literals. | |
| 526 @NoInline() | |
| 527 factory LinkedHashMap._literal(List keyValuePairs) { | |
| 528 return fillLiteralMap(keyValuePairs, new JsLinkedHashMap<K, V>.es6()); | |
| 529 } | |
| 530 | |
| 531 // Private factory constructor called by generated code for map literals. | |
| 532 @NoThrows() @NoInline() @NoSideEffects() | |
| 533 factory LinkedHashMap._empty() { | |
| 534 return new JsLinkedHashMap<K, V>.es6(); | |
| 535 } | |
| 536 | |
| 537 // Private factory static function called by generated code for map literals. | |
| 538 // This version is for map literals without type parameters. | |
| 539 @NoInline() | |
| 540 static _makeEmpty() => new JsLinkedHashMap(); | |
| 541 | |
| 542 // Private factory static function called by generated code for map literals. | |
| 543 // This version is for map literals without type parameters. | |
| 544 @NoInline() | |
| 545 static _makeLiteral(keyValuePairs) => | |
| 546 fillLiteralMap(keyValuePairs, new JsLinkedHashMap()); | |
| 547 } | |
| 548 | |
| 549 class _LinkedIdentityHashMap<K, V> extends JsLinkedHashMap<K, V> { | |
| 550 static bool get _supportsEs6Maps { | |
| 551 return JS('returns:bool;depends:none;effects:none;throws:never;gvn:true', | |
| 552 'typeof Map != "undefined"'); | |
| 553 } | |
| 554 | |
| 555 factory _LinkedIdentityHashMap.es6() { | |
| 556 return (_USE_ES6_MAPS && _LinkedIdentityHashMap._supportsEs6Maps) | |
| 557 ? new _Es6LinkedIdentityHashMap<K, V>() | |
| 558 : new _LinkedIdentityHashMap<K, V>(); | |
| 559 } | |
| 560 | |
| 561 _LinkedIdentityHashMap(); | |
| 562 | |
| 563 int internalComputeHashCode(var key) { | |
| 564 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 565 // issues with problematic keys like '__proto__'. Another option | |
| 566 // would be to throw an exception if the hash code isn't a number. | |
| 567 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 568 } | |
| 569 | |
| 570 int internalFindBucketIndex(var bucket, var key) { | |
| 571 if (bucket == null) return -1; | |
| 572 int length = JS('int', '#.length', bucket); | |
| 573 for (int i = 0; i < length; i++) { | |
| 574 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 575 if (identical(cell.hashMapCellKey, key)) return i; | |
| 576 } | |
| 577 return -1; | |
| 578 } | |
| 579 } | |
| 580 | |
| 581 class _Es6LinkedIdentityHashMap<K, V> | |
| 582 extends _LinkedIdentityHashMap<K, V> implements InternalMap { | |
| 583 final _map; | |
| 584 int _modifications = 0; | |
| 585 | |
| 586 _Es6LinkedIdentityHashMap() : _map = JS('var', 'new Map()'); | |
| 587 | |
| 588 int get length => JS('int', '#.size', _map); | |
| 589 bool get isEmpty => length == 0; | |
| 590 bool get isNotEmpty => !isEmpty; | |
| 591 | |
| 592 Iterable<K> get keys => new _Es6MapIterable<K>(this, true); | |
| 593 | |
| 594 Iterable<V> get values => | |
| 595 new _Es6MapIterable<V>(this, false); | |
| 596 | |
| 597 bool containsKey(Object key) { | |
| 598 return JS('bool', '#.has(#)', _map, key); | |
| 599 } | |
| 600 | |
| 601 bool containsValue(Object value) { | |
| 602 return values.any((each) => each == value); | |
| 603 } | |
| 604 | |
| 605 void addAll(Map<K, V> other) { | |
| 606 other.forEach((K key, V value) { | |
| 607 this[key] = value; | |
| 608 }); | |
| 609 } | |
| 610 | |
| 611 V operator[](Object key) { | |
| 612 return JS('var', '#.get(#)', _map, key); | |
| 613 } | |
| 614 | |
| 615 void operator[]=(K key, V value) { | |
| 616 JS('var', '#.set(#, #)', _map, key, value); | |
| 617 _modified(); | |
| 618 } | |
| 619 | |
| 620 V putIfAbsent(K key, V ifAbsent()) { | |
| 621 if (containsKey(key)) return this[key]; | |
| 622 V value = ifAbsent(); | |
| 623 this[key] = value; | |
| 624 return value; | |
| 625 } | |
| 626 | |
| 627 V remove(Object key) { | |
| 628 V value = this[key]; | |
| 629 JS('bool', '#.delete(#)', _map, key); | |
| 630 _modified(); | |
| 631 return value; | |
| 632 } | |
| 633 | |
| 634 void clear() { | |
| 635 JS('void', '#.clear()', _map); | |
| 636 _modified(); | |
| 637 } | |
| 638 | |
| 639 void forEach(void action(K key, V value)) { | |
| 640 var jsEntries = JS('var', '#.entries()', _map); | |
| 641 int modifications = _modifications; | |
| 642 while (true) { | |
| 643 var next = JS('var', '#.next()', jsEntries); | |
| 644 bool done = JS('bool', '#.done', next); | |
| 645 if (done) break; | |
| 646 var entry = JS('var', '#.value', next); | |
| 647 var key = JS('var', '#[0]', entry); | |
| 648 var value = JS('var', '#[1]', entry); | |
| 649 action(key, value); | |
| 650 if (modifications != _modifications) { | |
| 651 throw new ConcurrentModificationError(this); | |
| 652 } | |
| 653 } | |
| 654 } | |
| 655 | |
| 656 void _modified() { | |
| 657 // Value cycles after 2^30 modifications so that modification counts are | |
| 658 // always unboxed (Smi) values. Modification detection will be missed if you | |
| 659 // make exactly some multiple of 2^30 modifications between advances of an | |
| 660 // iterator. | |
| 661 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 662 } | |
| 663 | |
| 664 String toString() => Maps.mapToString(this); | |
| 665 } | |
| 666 | |
| 667 class _Es6MapIterable<E> extends Iterable<E> | |
| 668 implements EfficientLength { | |
| 669 final _map; | |
| 670 final bool _isKeys; | |
| 671 | |
| 672 _Es6MapIterable(this._map, this._isKeys); | |
| 673 | |
| 674 int get length => _map.length; | |
| 675 bool get isEmpty => _map.isEmpty; | |
| 676 | |
| 677 Iterator<E> get iterator => | |
| 678 new _Es6MapIterator<E>(_map, _map._modifications, _isKeys); | |
| 679 | |
| 680 bool contains(Object element) => _map.containsKey(element); | |
| 681 | |
| 682 void forEach(void f(E element)) { | |
| 683 var jsIterator; | |
| 684 if (_isKeys) { | |
| 685 jsIterator = JS('var', '#.keys()', _map._map); | |
| 686 } else { | |
| 687 jsIterator = JS('var', '#.values()', _map._map); | |
| 688 } | |
| 689 int modifications = _map._modifications; | |
| 690 while (true) { | |
| 691 var next = JS('var', '#.next()', jsIterator); | |
| 692 bool done = JS('bool', '#.done', next); | |
| 693 if (done) break; | |
| 694 var value = JS('var', '#.value', next); | |
| 695 f(value); | |
| 696 if (modifications != _map._modifications) { | |
| 697 throw new ConcurrentModificationError(_map); | |
| 698 } | |
| 699 } | |
| 700 } | |
| 701 } | |
| 702 | |
| 703 class _Es6MapIterator<E> implements Iterator<E> { | |
| 704 final _map; | |
| 705 final int _modifications; | |
| 706 final bool _isKeys; | |
| 707 var _jsIterator; | |
| 708 var _next; | |
| 709 E _current; | |
| 710 bool _done; | |
| 711 | |
| 712 _Es6MapIterator(this._map, this._modifications, this._isKeys) { | |
| 713 if (_isKeys) { | |
| 714 _jsIterator = JS('var', '#.keys()', _map._map); | |
| 715 } else { | |
| 716 _jsIterator = JS('var', '#.values()', _map._map); | |
| 717 } | |
| 718 _done = false; | |
| 719 } | |
| 720 | |
| 721 E get current => _current; | |
| 722 | |
| 723 bool moveNext() { | |
| 724 if (_modifications != _map._modifications) { | |
| 725 throw new ConcurrentModificationError(_map); | |
| 726 } | |
| 727 if (_done) return false; | |
| 728 _next = JS('var', '#.next()', _jsIterator); | |
| 729 bool done = JS('bool', '#.done', _next); | |
| 730 if (done) { | |
| 731 _current = null; | |
| 732 _done = true; | |
| 733 return false; | |
| 734 } else { | |
| 735 _current = JS('var', '#.value', _next); | |
| 736 return true; | |
| 737 } | |
| 738 } | |
| 739 } | |
| 740 | |
| 741 // TODO(floitsch): use ES6 maps when available. | |
| 742 class _LinkedCustomHashMap<K, V> extends JsLinkedHashMap<K, V> { | |
| 743 final _Equality<K> _equals; | |
| 744 final _Hasher<K> _hashCode; | |
| 745 final _Predicate _validKey; | |
| 746 | |
| 747 _LinkedCustomHashMap(this._equals, this._hashCode, | |
| 748 bool validKey(potentialKey)) | |
| 749 : _validKey = (validKey != null) ? validKey : ((v) => v is K); | |
| 750 | |
| 751 V operator[](Object key) { | |
| 752 if (!_validKey(key)) return null; | |
| 753 return super.internalGet(key); | |
| 754 } | |
| 755 | |
| 756 void operator[]=(K key, V value) { | |
| 757 super.internalSet(key, value); | |
| 758 } | |
| 759 | |
| 760 bool containsKey(Object key) { | |
| 761 if (!_validKey(key)) return false; | |
| 762 return super.internalContainsKey(key); | |
| 763 } | |
| 764 | |
| 765 V remove(Object key) { | |
| 766 if (!_validKey(key)) return null; | |
| 767 return super.internalRemove(key); | |
| 768 } | |
| 769 | |
| 770 int internalComputeHashCode(var key) { | |
| 771 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 772 // issues with problematic keys like '__proto__'. Another option | |
| 773 // would be to throw an exception if the hash code isn't a number. | |
| 774 return JS('int', '# & 0x3ffffff', _hashCode(key)); | |
| 775 } | |
| 776 | |
| 777 int internalFindBucketIndex(var bucket, var key) { | |
| 778 if (bucket == null) return -1; | |
| 779 int length = JS('int', '#.length', bucket); | |
| 780 for (int i = 0; i < length; i++) { | |
| 781 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 782 if (_equals(cell.hashMapCellKey, key)) return i; | |
| 783 } | |
| 784 return -1; | |
| 785 } | |
| 786 } | |
| 787 | |
| 788 @patch | |
| 789 class HashSet<E> { | |
| 790 @patch | |
| 791 factory HashSet({ bool equals(E e1, E e2), | |
| 792 int hashCode(E e), | |
| 793 bool isValidKey(potentialKey) }) { | |
| 794 if (isValidKey == null) { | |
| 795 if (hashCode == null) { | |
| 796 if (equals == null) { | |
| 797 return new _HashSet<E>(); | |
| 798 } | |
| 799 hashCode = _defaultHashCode; | |
| 800 } else { | |
| 801 if (identical(identityHashCode, hashCode) && | |
| 802 identical(identical, equals)) { | |
| 803 return new _IdentityHashSet<E>(); | |
| 804 } | |
| 805 if (equals == null) { | |
| 806 equals = _defaultEquals; | |
| 807 } | |
| 808 } | |
| 809 } else { | |
| 810 if (hashCode == null) { | |
| 811 hashCode = _defaultHashCode; | |
| 812 } | |
| 813 if (equals == null) { | |
| 814 equals = _defaultEquals; | |
| 815 } | |
| 816 } | |
| 817 return new _CustomHashSet<E>(equals, hashCode, isValidKey); | |
| 818 } | |
| 819 | |
| 820 @patch | |
| 821 factory HashSet.identity() = _IdentityHashSet<E>; | |
| 822 } | |
| 823 | |
| 824 class _HashSet<E> extends _HashSetBase<E> implements HashSet<E> { | |
| 825 int _length = 0; | |
| 826 | |
| 827 // The hash set contents are divided into three parts: one part for | |
| 828 // string elements, one for numeric elements, and one for the | |
| 829 // rest. String and numeric elements map directly to a sentinel | |
| 830 // value, but the rest of the entries are stored in bucket lists of | |
| 831 // the form: | |
| 832 // | |
| 833 // [element-0, element-1, element-2, ...] | |
| 834 // | |
| 835 // where all elements in the same bucket share the same hash code. | |
| 836 var _strings; | |
| 837 var _nums; | |
| 838 var _rest; | |
| 839 | |
| 840 // When iterating over the hash set, it is very convenient to have a | |
| 841 // list of all the elements. We cache that on the instance and clear | |
| 842 // the the cache whenever the set changes. This is also used to | |
| 843 // guard against concurrent modifications. | |
| 844 List _elements; | |
| 845 | |
| 846 _HashSet(); | |
| 847 | |
| 848 Set<E> _newSet() => new _HashSet<E>(); | |
| 849 | |
| 850 // Iterable. | |
| 851 Iterator<E> get iterator { | |
| 852 return new HashSetIterator<E>(this, _computeElements()); | |
| 853 } | |
| 854 | |
| 855 int get length => _length; | |
| 856 bool get isEmpty => _length == 0; | |
| 857 bool get isNotEmpty => !isEmpty; | |
| 858 | |
| 859 bool contains(Object object) { | |
| 860 if (_isStringElement(object)) { | |
| 861 var strings = _strings; | |
| 862 return (strings == null) ? false : _hasTableEntry(strings, object); | |
| 863 } else if (_isNumericElement(object)) { | |
| 864 var nums = _nums; | |
| 865 return (nums == null) ? false : _hasTableEntry(nums, object); | |
| 866 } else { | |
| 867 return _contains(object); | |
| 868 } | |
| 869 } | |
| 870 | |
| 871 bool _contains(Object object) { | |
| 872 var rest = _rest; | |
| 873 if (rest == null) return false; | |
| 874 var bucket = _getBucket(rest, object); | |
| 875 return _findBucketIndex(bucket, object) >= 0; | |
| 876 } | |
| 877 | |
| 878 E lookup(Object object) { | |
| 879 if (_isStringElement(object) || _isNumericElement(object)) { | |
| 880 return this.contains(object) ? object : null; | |
| 881 } | |
| 882 return _lookup(object); | |
| 883 } | |
| 884 | |
| 885 E _lookup(Object object) { | |
| 886 var rest = _rest; | |
| 887 if (rest == null) return null; | |
| 888 var bucket = _getBucket(rest, object); | |
| 889 var index = _findBucketIndex(bucket, object); | |
| 890 if (index < 0) return null; | |
| 891 return bucket[index]; | |
| 892 } | |
| 893 | |
| 894 // Collection. | |
| 895 bool add(E element) { | |
| 896 if (_isStringElement(element)) { | |
| 897 var strings = _strings; | |
| 898 if (strings == null) _strings = strings = _newHashTable(); | |
| 899 return _addHashTableEntry(strings, element); | |
| 900 } else if (_isNumericElement(element)) { | |
| 901 var nums = _nums; | |
| 902 if (nums == null) _nums = nums = _newHashTable(); | |
| 903 return _addHashTableEntry(nums, element); | |
| 904 } else { | |
| 905 return _add(element); | |
| 906 } | |
| 907 } | |
| 908 | |
| 909 bool _add(E element) { | |
| 910 var rest = _rest; | |
| 911 if (rest == null) _rest = rest = _newHashTable(); | |
| 912 var hash = _computeHashCode(element); | |
| 913 var bucket = JS('var', '#[#]', rest, hash); | |
| 914 if (bucket == null) { | |
| 915 _setTableEntry(rest, hash, JS('var', '[#]', element)); | |
| 916 } else { | |
| 917 int index = _findBucketIndex(bucket, element); | |
| 918 if (index >= 0) return false; | |
| 919 JS('void', '#.push(#)', bucket, element); | |
| 920 } | |
| 921 _length++; | |
| 922 _elements = null; | |
| 923 return true; | |
| 924 } | |
| 925 | |
| 926 void addAll(Iterable<E> objects) { | |
| 927 for (E each in objects) { | |
| 928 add(each); | |
| 929 } | |
| 930 } | |
| 931 | |
| 932 bool remove(Object object) { | |
| 933 if (_isStringElement(object)) { | |
| 934 return _removeHashTableEntry(_strings, object); | |
| 935 } else if (_isNumericElement(object)) { | |
| 936 return _removeHashTableEntry(_nums, object); | |
| 937 } else { | |
| 938 return _remove(object); | |
| 939 } | |
| 940 } | |
| 941 | |
| 942 bool _remove(Object object) { | |
| 943 var rest = _rest; | |
| 944 if (rest == null) return false; | |
| 945 var bucket = _getBucket(rest, object); | |
| 946 int index = _findBucketIndex(bucket, object); | |
| 947 if (index < 0) return false; | |
| 948 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 949 // the length reaches zero. | |
| 950 _length--; | |
| 951 _elements = null; | |
| 952 // TODO(kasperl): It would probably be faster to move the | |
| 953 // element to the end and reduce the length of the bucket list. | |
| 954 JS('void', '#.splice(#, 1)', bucket, index); | |
| 955 return true; | |
| 956 } | |
| 957 | |
| 958 void clear() { | |
| 959 if (_length > 0) { | |
| 960 _strings = _nums = _rest = _elements = null; | |
| 961 _length = 0; | |
| 962 } | |
| 963 } | |
| 964 | |
| 965 List _computeElements() { | |
| 966 if (_elements != null) return _elements; | |
| 967 List result = new List(_length); | |
| 968 int index = 0; | |
| 969 | |
| 970 // Add all string elements to the list. | |
| 971 var strings = _strings; | |
| 972 if (strings != null) { | |
| 973 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 974 int entries = JS('int', '#.length', names); | |
| 975 for (int i = 0; i < entries; i++) { | |
| 976 String element = JS('String', '#[#]', names, i); | |
| 977 JS('void', '#[#] = #', result, index, element); | |
| 978 index++; | |
| 979 } | |
| 980 } | |
| 981 | |
| 982 // Add all numeric elements to the list. | |
| 983 var nums = _nums; | |
| 984 if (nums != null) { | |
| 985 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 986 int entries = JS('int', '#.length', names); | |
| 987 for (int i = 0; i < entries; i++) { | |
| 988 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 989 // have to convert the elements back to numbers (+). | |
| 990 num element = JS('num', '+#[#]', names, i); | |
| 991 JS('void', '#[#] = #', result, index, element); | |
| 992 index++; | |
| 993 } | |
| 994 } | |
| 995 | |
| 996 // Add all the remaining elements to the list. | |
| 997 var rest = _rest; | |
| 998 if (rest != null) { | |
| 999 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 1000 int entries = JS('int', '#.length', names); | |
| 1001 for (int i = 0; i < entries; i++) { | |
| 1002 var entry = JS('String', '#[#]', names, i); | |
| 1003 var bucket = JS('var', '#[#]', rest, entry); | |
| 1004 int length = JS('int', '#.length', bucket); | |
| 1005 for (int i = 0; i < length; i++) { | |
| 1006 JS('void', '#[#] = #[#]', result, index, bucket, i); | |
| 1007 index++; | |
| 1008 } | |
| 1009 } | |
| 1010 } | |
| 1011 assert(index == _length); | |
| 1012 return _elements = result; | |
| 1013 } | |
| 1014 | |
| 1015 bool _addHashTableEntry(var table, E element) { | |
| 1016 if (_hasTableEntry(table, element)) return false; | |
| 1017 _setTableEntry(table, element, 0); | |
| 1018 _length++; | |
| 1019 _elements = null; | |
| 1020 return true; | |
| 1021 } | |
| 1022 | |
| 1023 bool _removeHashTableEntry(var table, Object element) { | |
| 1024 if (table != null && _hasTableEntry(table, element)) { | |
| 1025 _deleteTableEntry(table, element); | |
| 1026 _length--; | |
| 1027 _elements = null; | |
| 1028 return true; | |
| 1029 } else { | |
| 1030 return false; | |
| 1031 } | |
| 1032 } | |
| 1033 | |
| 1034 static bool _isStringElement(var element) { | |
| 1035 return element is String && element != '__proto__'; | |
| 1036 } | |
| 1037 | |
| 1038 static bool _isNumericElement(var element) { | |
| 1039 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 1040 // way, we avoid converting them to strings when we use them as | |
| 1041 // keys in the JavaScript hash table object. | |
| 1042 return element is num && | |
| 1043 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 1044 } | |
| 1045 | |
| 1046 int _computeHashCode(var element) { | |
| 1047 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1048 // issues with problematic elements like '__proto__'. Another | |
| 1049 // option would be to throw an exception if the hash code isn't a | |
| 1050 // number. | |
| 1051 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 1052 } | |
| 1053 | |
| 1054 static bool _hasTableEntry(var table, var key) { | |
| 1055 var entry = JS('var', '#[#]', table, key); | |
| 1056 // We take care to only store non-null entries in the table, so we | |
| 1057 // can check if the table has an entry for the given key with a | |
| 1058 // simple null check. | |
| 1059 return entry != null; | |
| 1060 } | |
| 1061 | |
| 1062 static void _setTableEntry(var table, var key, var value) { | |
| 1063 assert(value != null); | |
| 1064 JS('void', '#[#] = #', table, key, value); | |
| 1065 } | |
| 1066 | |
| 1067 static void _deleteTableEntry(var table, var key) { | |
| 1068 JS('void', 'delete #[#]', table, key); | |
| 1069 } | |
| 1070 | |
| 1071 List _getBucket(var table, var element) { | |
| 1072 var hash = _computeHashCode(element); | |
| 1073 return JS('var', '#[#]', table, hash); | |
| 1074 } | |
| 1075 | |
| 1076 int _findBucketIndex(var bucket, var element) { | |
| 1077 if (bucket == null) return -1; | |
| 1078 int length = JS('int', '#.length', bucket); | |
| 1079 for (int i = 0; i < length; i++) { | |
| 1080 if (JS('var', '#[#]', bucket, i) == element) return i; | |
| 1081 } | |
| 1082 return -1; | |
| 1083 } | |
| 1084 | |
| 1085 static _newHashTable() { | |
| 1086 // Create a new JavaScript object to be used as a hash table. Use | |
| 1087 // Object.create to avoid the properties on Object.prototype | |
| 1088 // showing up as entries. | |
| 1089 var table = JS('var', 'Object.create(null)'); | |
| 1090 // Attempt to force the hash table into 'dictionary' mode by | |
| 1091 // adding a property to it and deleting it again. | |
| 1092 var temporaryKey = '<non-identifier-key>'; | |
| 1093 _setTableEntry(table, temporaryKey, table); | |
| 1094 _deleteTableEntry(table, temporaryKey); | |
| 1095 return table; | |
| 1096 } | |
| 1097 } | |
| 1098 | |
| 1099 class _IdentityHashSet<E> extends _HashSet<E> { | |
| 1100 Set<E> _newSet() => new _IdentityHashSet<E>(); | |
| 1101 | |
| 1102 int _computeHashCode(var key) { | |
| 1103 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1104 // issues with problematic keys like '__proto__'. Another option | |
| 1105 // would be to throw an exception if the hash code isn't a number. | |
| 1106 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 1107 } | |
| 1108 | |
| 1109 int _findBucketIndex(var bucket, var element) { | |
| 1110 if (bucket == null) return -1; | |
| 1111 int length = JS('int', '#.length', bucket); | |
| 1112 for (int i = 0; i < length; i++) { | |
| 1113 if (identical(JS('var', '#[#]', bucket, i), element)) return i; | |
| 1114 } | |
| 1115 return -1; | |
| 1116 } | |
| 1117 } | |
| 1118 | |
| 1119 class _CustomHashSet<E> extends _HashSet<E> { | |
| 1120 _Equality<E> _equality; | |
| 1121 _Hasher<E> _hasher; | |
| 1122 _Predicate _validKey; | |
| 1123 _CustomHashSet(this._equality, this._hasher, bool validKey(potentialKey)) | |
| 1124 : _validKey = (validKey != null) ? validKey : ((x) => x is E); | |
| 1125 | |
| 1126 Set<E> _newSet() => new _CustomHashSet<E>(_equality, _hasher, _validKey); | |
| 1127 | |
| 1128 int _findBucketIndex(var bucket, var element) { | |
| 1129 if (bucket == null) return -1; | |
| 1130 int length = JS('int', '#.length', bucket); | |
| 1131 for (int i = 0; i < length; i++) { | |
| 1132 if (_equality(JS('var', '#[#]', bucket, i), element)) return i; | |
| 1133 } | |
| 1134 return -1; | |
| 1135 } | |
| 1136 | |
| 1137 int _computeHashCode(var element) { | |
| 1138 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1139 // issues with problematic elements like '__proto__'. Another | |
| 1140 // option would be to throw an exception if the hash code isn't a | |
| 1141 // number. | |
| 1142 return JS('int', '# & 0x3ffffff', _hasher(element)); | |
| 1143 } | |
| 1144 | |
| 1145 bool add(E object) => super._add(object); | |
| 1146 | |
| 1147 bool contains(Object object) { | |
| 1148 if (!_validKey(object)) return false; | |
| 1149 return super._contains(object); | |
| 1150 } | |
| 1151 | |
| 1152 E lookup(Object object) { | |
| 1153 if (!_validKey(object)) return null; | |
| 1154 return super._lookup(object); | |
| 1155 } | |
| 1156 | |
| 1157 bool remove(Object object) { | |
| 1158 if (!_validKey(object)) return false; | |
| 1159 return super._remove(object); | |
| 1160 } | |
| 1161 } | |
| 1162 | |
| 1163 // TODO(kasperl): Share this code with HashMapKeyIterator<E>? | |
| 1164 class HashSetIterator<E> implements Iterator<E> { | |
| 1165 final _set; | |
| 1166 final List _elements; | |
| 1167 int _offset = 0; | |
| 1168 E _current; | |
| 1169 | |
| 1170 HashSetIterator(this._set, this._elements); | |
| 1171 | |
| 1172 E get current => _current; | |
| 1173 | |
| 1174 bool moveNext() { | |
| 1175 var elements = _elements; | |
| 1176 int offset = _offset; | |
| 1177 if (JS('bool', '# !== #', elements, _set._elements)) { | |
| 1178 throw new ConcurrentModificationError(_set); | |
| 1179 } else if (offset >= JS('int', '#.length', elements)) { | |
| 1180 _current = null; | |
| 1181 return false; | |
| 1182 } else { | |
| 1183 _current = JS('var', '#[#]', elements, offset); | |
| 1184 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 1185 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 1186 // get unnecessary bailout code. | |
| 1187 _offset = JS('int', '#', offset + 1); | |
| 1188 return true; | |
| 1189 } | |
| 1190 } | |
| 1191 } | |
| 1192 | |
| 1193 @patch | |
| 1194 class LinkedHashSet<E> { | |
| 1195 @patch | |
| 1196 factory LinkedHashSet({ bool equals(E e1, E e2), | |
| 1197 int hashCode(E e), | |
| 1198 bool isValidKey(potentialKey) }) { | |
| 1199 if (isValidKey == null) { | |
| 1200 if (hashCode == null) { | |
| 1201 if (equals == null) { | |
| 1202 return new _LinkedHashSet<E>(); | |
| 1203 } | |
| 1204 hashCode = _defaultHashCode; | |
| 1205 } else { | |
| 1206 if (identical(identityHashCode, hashCode) && | |
| 1207 identical(identical, equals)) { | |
| 1208 return new _LinkedIdentityHashSet<E>(); | |
| 1209 } | |
| 1210 if (equals == null) { | |
| 1211 equals = _defaultEquals; | |
| 1212 } | |
| 1213 } | |
| 1214 } else { | |
| 1215 if (hashCode == null) { | |
| 1216 hashCode = _defaultHashCode; | |
| 1217 } | |
| 1218 if (equals == null) { | |
| 1219 equals = _defaultEquals; | |
| 1220 } | |
| 1221 } | |
| 1222 return new _LinkedCustomHashSet<E>(equals, hashCode, isValidKey); | |
| 1223 } | |
| 1224 | |
| 1225 @patch | |
| 1226 factory LinkedHashSet.identity() = _LinkedIdentityHashSet<E>; | |
| 1227 } | |
| 1228 | |
| 1229 class _LinkedHashSet<E> extends _HashSetBase<E> implements LinkedHashSet<E> { | |
| 1230 int _length = 0; | |
| 1231 | |
| 1232 // The hash set contents are divided into three parts: one part for | |
| 1233 // string elements, one for numeric elements, and one for the | |
| 1234 // rest. String and numeric elements map directly to their linked | |
| 1235 // cells, but the rest of the entries are stored in bucket lists of | |
| 1236 // the form: | |
| 1237 // | |
| 1238 // [cell-0, cell-1, ...] | |
| 1239 // | |
| 1240 // where all elements in the same bucket share the same hash code. | |
| 1241 var _strings; | |
| 1242 var _nums; | |
| 1243 var _rest; | |
| 1244 | |
| 1245 // The elements are stored in cells that are linked together | |
| 1246 // to form a double linked list. | |
| 1247 LinkedHashSetCell _first; | |
| 1248 LinkedHashSetCell _last; | |
| 1249 | |
| 1250 // We track the number of modifications done to the element set to | |
| 1251 // be able to throw when the set is modified while being iterated | |
| 1252 // over. | |
| 1253 int _modifications = 0; | |
| 1254 | |
| 1255 _LinkedHashSet(); | |
| 1256 | |
| 1257 Set<E> _newSet() => new _LinkedHashSet<E>(); | |
| 1258 | |
| 1259 void _unsupported(String operation) { | |
| 1260 throw 'LinkedHashSet: unsupported $operation'; | |
| 1261 } | |
| 1262 | |
| 1263 // Iterable. | |
| 1264 Iterator<E> get iterator { | |
| 1265 return new LinkedHashSetIterator(this, _modifications); | |
| 1266 } | |
| 1267 | |
| 1268 int get length => _length; | |
| 1269 bool get isEmpty => _length == 0; | |
| 1270 bool get isNotEmpty => !isEmpty; | |
| 1271 | |
| 1272 bool contains(Object object) { | |
| 1273 if (_isStringElement(object)) { | |
| 1274 var strings = _strings; | |
| 1275 if (strings == null) return false; | |
| 1276 LinkedHashSetCell cell = _getTableEntry(strings, object); | |
| 1277 return cell != null; | |
| 1278 } else if (_isNumericElement(object)) { | |
| 1279 var nums = _nums; | |
| 1280 if (nums == null) return false; | |
| 1281 LinkedHashSetCell cell = _getTableEntry(nums, object); | |
| 1282 return cell != null; | |
| 1283 } else { | |
| 1284 return _contains(object); | |
| 1285 } | |
| 1286 } | |
| 1287 | |
| 1288 bool _contains(Object object) { | |
| 1289 var rest = _rest; | |
| 1290 if (rest == null) return false; | |
| 1291 var bucket = _getBucket(rest, object); | |
| 1292 return _findBucketIndex(bucket, object) >= 0; | |
| 1293 } | |
| 1294 | |
| 1295 E lookup(Object object) { | |
| 1296 if (_isStringElement(object) || _isNumericElement(object)) { | |
| 1297 return this.contains(object) ? object : null; | |
| 1298 } else { | |
| 1299 return _lookup(object); | |
| 1300 } | |
| 1301 } | |
| 1302 | |
| 1303 E _lookup(Object object) { | |
| 1304 var rest = _rest; | |
| 1305 if (rest == null) return null; | |
| 1306 var bucket = _getBucket(rest, object); | |
| 1307 var index = _findBucketIndex(bucket, object); | |
| 1308 if (index < 0) return null; | |
| 1309 return bucket[index]._element; | |
| 1310 } | |
| 1311 | |
| 1312 void forEach(void action(E element)) { | |
| 1313 LinkedHashSetCell cell = _first; | |
| 1314 int modifications = _modifications; | |
| 1315 while (cell != null) { | |
| 1316 action(cell._element); | |
| 1317 if (modifications != _modifications) { | |
| 1318 throw new ConcurrentModificationError(this); | |
| 1319 } | |
| 1320 cell = cell._next; | |
| 1321 } | |
| 1322 } | |
| 1323 | |
| 1324 E get first { | |
| 1325 if (_first == null) throw new StateError("No elements"); | |
| 1326 return _first._element; | |
| 1327 } | |
| 1328 | |
| 1329 E get last { | |
| 1330 if (_last == null) throw new StateError("No elements"); | |
| 1331 return _last._element; | |
| 1332 } | |
| 1333 | |
| 1334 // Collection. | |
| 1335 bool add(E element) { | |
| 1336 if (_isStringElement(element)) { | |
| 1337 var strings = _strings; | |
| 1338 if (strings == null) _strings = strings = _newHashTable(); | |
| 1339 return _addHashTableEntry(strings, element); | |
| 1340 } else if (_isNumericElement(element)) { | |
| 1341 var nums = _nums; | |
| 1342 if (nums == null) _nums = nums = _newHashTable(); | |
| 1343 return _addHashTableEntry(nums, element); | |
| 1344 } else { | |
| 1345 return _add(element); | |
| 1346 } | |
| 1347 } | |
| 1348 | |
| 1349 bool _add(E element) { | |
| 1350 var rest = _rest; | |
| 1351 if (rest == null) _rest = rest = _newHashTable(); | |
| 1352 var hash = _computeHashCode(element); | |
| 1353 var bucket = JS('var', '#[#]', rest, hash); | |
| 1354 if (bucket == null) { | |
| 1355 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1356 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 1357 } else { | |
| 1358 int index = _findBucketIndex(bucket, element); | |
| 1359 if (index >= 0) return false; | |
| 1360 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1361 JS('void', '#.push(#)', bucket, cell); | |
| 1362 } | |
| 1363 return true; | |
| 1364 } | |
| 1365 | |
| 1366 bool remove(Object object) { | |
| 1367 if (_isStringElement(object)) { | |
| 1368 return _removeHashTableEntry(_strings, object); | |
| 1369 } else if (_isNumericElement(object)) { | |
| 1370 return _removeHashTableEntry(_nums, object); | |
| 1371 } else { | |
| 1372 return _remove(object); | |
| 1373 } | |
| 1374 } | |
| 1375 | |
| 1376 bool _remove(Object object) { | |
| 1377 var rest = _rest; | |
| 1378 if (rest == null) return false; | |
| 1379 var bucket = _getBucket(rest, object); | |
| 1380 int index = _findBucketIndex(bucket, object); | |
| 1381 if (index < 0) return false; | |
| 1382 // Use splice to remove the [cell] element at the index and | |
| 1383 // unlink it. | |
| 1384 LinkedHashSetCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 1385 _unlinkCell(cell); | |
| 1386 return true; | |
| 1387 } | |
| 1388 | |
| 1389 void removeWhere(bool test(E element)) { | |
| 1390 _filterWhere(test, true); | |
| 1391 } | |
| 1392 | |
| 1393 void retainWhere(bool test(E element)) { | |
| 1394 _filterWhere(test, false); | |
| 1395 } | |
| 1396 | |
| 1397 void _filterWhere(bool test(E element), bool removeMatching) { | |
| 1398 LinkedHashSetCell cell = _first; | |
| 1399 while (cell != null) { | |
| 1400 E element = cell._element; | |
| 1401 LinkedHashSetCell next = cell._next; | |
| 1402 int modifications = _modifications; | |
| 1403 bool shouldRemove = (removeMatching == test(element)); | |
| 1404 if (modifications != _modifications) { | |
| 1405 throw new ConcurrentModificationError(this); | |
| 1406 } | |
| 1407 if (shouldRemove) remove(element); | |
| 1408 cell = next; | |
| 1409 } | |
| 1410 } | |
| 1411 | |
| 1412 void clear() { | |
| 1413 if (_length > 0) { | |
| 1414 _strings = _nums = _rest = _first = _last = null; | |
| 1415 _length = 0; | |
| 1416 _modified(); | |
| 1417 } | |
| 1418 } | |
| 1419 | |
| 1420 bool _addHashTableEntry(var table, E element) { | |
| 1421 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1422 if (cell != null) return false; | |
| 1423 _setTableEntry(table, element, _newLinkedCell(element)); | |
| 1424 return true; | |
| 1425 } | |
| 1426 | |
| 1427 bool _removeHashTableEntry(var table, Object element) { | |
| 1428 if (table == null) return false; | |
| 1429 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1430 if (cell == null) return false; | |
| 1431 _unlinkCell(cell); | |
| 1432 _deleteTableEntry(table, element); | |
| 1433 return true; | |
| 1434 } | |
| 1435 | |
| 1436 void _modified() { | |
| 1437 // Value cycles after 2^30 modifications. If you keep hold of an | |
| 1438 // iterator for that long, you might miss a modification | |
| 1439 // detection, and iteration can go sour. Don't do that. | |
| 1440 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 1441 } | |
| 1442 | |
| 1443 // Create a new cell and link it in as the last one in the list. | |
| 1444 LinkedHashSetCell _newLinkedCell(E element) { | |
| 1445 LinkedHashSetCell cell = new LinkedHashSetCell(element); | |
| 1446 if (_first == null) { | |
| 1447 _first = _last = cell; | |
| 1448 } else { | |
| 1449 LinkedHashSetCell last = _last; | |
| 1450 cell._previous = last; | |
| 1451 _last = last._next = cell; | |
| 1452 } | |
| 1453 _length++; | |
| 1454 _modified(); | |
| 1455 return cell; | |
| 1456 } | |
| 1457 | |
| 1458 // Unlink the given cell from the linked list of cells. | |
| 1459 void _unlinkCell(LinkedHashSetCell cell) { | |
| 1460 LinkedHashSetCell previous = cell._previous; | |
| 1461 LinkedHashSetCell next = cell._next; | |
| 1462 if (previous == null) { | |
| 1463 assert(cell == _first); | |
| 1464 _first = next; | |
| 1465 } else { | |
| 1466 previous._next = next; | |
| 1467 } | |
| 1468 if (next == null) { | |
| 1469 assert(cell == _last); | |
| 1470 _last = previous; | |
| 1471 } else { | |
| 1472 next._previous = previous; | |
| 1473 } | |
| 1474 _length--; | |
| 1475 _modified(); | |
| 1476 } | |
| 1477 | |
| 1478 static bool _isStringElement(var element) { | |
| 1479 return element is String && element != '__proto__'; | |
| 1480 } | |
| 1481 | |
| 1482 static bool _isNumericElement(var element) { | |
| 1483 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 1484 // way, we avoid converting them to strings when we use them as | |
| 1485 // keys in the JavaScript hash table object. | |
| 1486 return element is num && | |
| 1487 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 1488 } | |
| 1489 | |
| 1490 int _computeHashCode(var element) { | |
| 1491 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1492 // issues with problematic elements like '__proto__'. Another | |
| 1493 // option would be to throw an exception if the hash code isn't a | |
| 1494 // number. | |
| 1495 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 1496 } | |
| 1497 | |
| 1498 static _getTableEntry(var table, var key) { | |
| 1499 return JS('var', '#[#]', table, key); | |
| 1500 } | |
| 1501 | |
| 1502 static void _setTableEntry(var table, var key, var value) { | |
| 1503 assert(value != null); | |
| 1504 JS('void', '#[#] = #', table, key, value); | |
| 1505 } | |
| 1506 | |
| 1507 static void _deleteTableEntry(var table, var key) { | |
| 1508 JS('void', 'delete #[#]', table, key); | |
| 1509 } | |
| 1510 | |
| 1511 List _getBucket(var table, var element) { | |
| 1512 var hash = _computeHashCode(element); | |
| 1513 return JS('var', '#[#]', table, hash); | |
| 1514 } | |
| 1515 | |
| 1516 int _findBucketIndex(var bucket, var element) { | |
| 1517 if (bucket == null) return -1; | |
| 1518 int length = JS('int', '#.length', bucket); | |
| 1519 for (int i = 0; i < length; i++) { | |
| 1520 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1521 if (cell._element == element) return i; | |
| 1522 } | |
| 1523 return -1; | |
| 1524 } | |
| 1525 | |
| 1526 static _newHashTable() { | |
| 1527 // Create a new JavaScript object to be used as a hash table. Use | |
| 1528 // Object.create to avoid the properties on Object.prototype | |
| 1529 // showing up as entries. | |
| 1530 var table = JS('var', 'Object.create(null)'); | |
| 1531 // Attempt to force the hash table into 'dictionary' mode by | |
| 1532 // adding a property to it and deleting it again. | |
| 1533 var temporaryKey = '<non-identifier-key>'; | |
| 1534 _setTableEntry(table, temporaryKey, table); | |
| 1535 _deleteTableEntry(table, temporaryKey); | |
| 1536 return table; | |
| 1537 } | |
| 1538 } | |
| 1539 | |
| 1540 class _LinkedIdentityHashSet<E> extends _LinkedHashSet<E> { | |
| 1541 Set<E> _newSet() => new _LinkedIdentityHashSet<E>(); | |
| 1542 | |
| 1543 int _computeHashCode(var key) { | |
| 1544 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1545 // issues with problematic keys like '__proto__'. Another option | |
| 1546 // would be to throw an exception if the hash code isn't a number. | |
| 1547 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 1548 } | |
| 1549 | |
| 1550 int _findBucketIndex(var bucket, var element) { | |
| 1551 if (bucket == null) return -1; | |
| 1552 int length = JS('int', '#.length', bucket); | |
| 1553 for (int i = 0; i < length; i++) { | |
| 1554 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1555 if (identical(cell._element, element)) return i; | |
| 1556 } | |
| 1557 return -1; | |
| 1558 } | |
| 1559 } | |
| 1560 | |
| 1561 class _LinkedCustomHashSet<E> extends _LinkedHashSet<E> { | |
| 1562 _Equality<E> _equality; | |
| 1563 _Hasher<E> _hasher; | |
| 1564 _Predicate _validKey; | |
| 1565 _LinkedCustomHashSet(this._equality, this._hasher, | |
| 1566 bool validKey(potentialKey)) | |
| 1567 : _validKey = (validKey != null) ? validKey : ((x) => x is E); | |
| 1568 | |
| 1569 Set<E> _newSet() => | |
| 1570 new _LinkedCustomHashSet<E>(_equality, _hasher, _validKey); | |
| 1571 | |
| 1572 int _findBucketIndex(var bucket, var element) { | |
| 1573 if (bucket == null) return -1; | |
| 1574 int length = JS('int', '#.length', bucket); | |
| 1575 for (int i = 0; i < length; i++) { | |
| 1576 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1577 if (_equality(cell._element, element)) return i; | |
| 1578 } | |
| 1579 return -1; | |
| 1580 } | |
| 1581 | |
| 1582 int _computeHashCode(var element) { | |
| 1583 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1584 // issues with problematic elements like '__proto__'. Another | |
| 1585 // option would be to throw an exception if the hash code isn't a | |
| 1586 // number. | |
| 1587 return JS('int', '# & 0x3ffffff', _hasher(element)); | |
| 1588 } | |
| 1589 | |
| 1590 bool add(E element) => super._add(element); | |
| 1591 | |
| 1592 bool contains(Object object) { | |
| 1593 if (!_validKey(object)) return false; | |
| 1594 return super._contains(object); | |
| 1595 } | |
| 1596 | |
| 1597 E lookup(Object object) { | |
| 1598 if (!_validKey(object)) return null; | |
| 1599 return super._lookup(object); | |
| 1600 } | |
| 1601 | |
| 1602 bool remove(Object object) { | |
| 1603 if (!_validKey(object)) return false; | |
| 1604 return super._remove(object); | |
| 1605 } | |
| 1606 | |
| 1607 bool containsAll(Iterable<Object> elements) { | |
| 1608 for (Object element in elements) { | |
| 1609 if (!_validKey(element) || !this.contains(element)) return false; | |
| 1610 } | |
| 1611 return true; | |
| 1612 } | |
| 1613 | |
| 1614 void removeAll(Iterable<Object> elements) { | |
| 1615 for (Object element in elements) { | |
| 1616 if (_validKey(element)) { | |
| 1617 super._remove(element); | |
| 1618 } | |
| 1619 } | |
| 1620 } | |
| 1621 } | |
| 1622 | |
| 1623 class LinkedHashSetCell { | |
| 1624 final _element; | |
| 1625 | |
| 1626 LinkedHashSetCell _next; | |
| 1627 LinkedHashSetCell _previous; | |
| 1628 | |
| 1629 LinkedHashSetCell(this._element); | |
| 1630 } | |
| 1631 | |
| 1632 // TODO(kasperl): Share this code with LinkedHashMapKeyIterator<E>? | |
| 1633 class LinkedHashSetIterator<E> implements Iterator<E> { | |
| 1634 final _set; | |
| 1635 final int _modifications; | |
| 1636 LinkedHashSetCell _cell; | |
| 1637 E _current; | |
| 1638 | |
| 1639 LinkedHashSetIterator(this._set, this._modifications) { | |
| 1640 _cell = _set._first; | |
| 1641 } | |
| 1642 | |
| 1643 E get current => _current; | |
| 1644 | |
| 1645 bool moveNext() { | |
| 1646 if (_modifications != _set._modifications) { | |
| 1647 throw new ConcurrentModificationError(_set); | |
| 1648 } else if (_cell == null) { | |
| 1649 _current = null; | |
| 1650 return false; | |
| 1651 } else { | |
| 1652 _current = _cell._element; | |
| 1653 _cell = _cell._next; | |
| 1654 return true; | |
| 1655 } | |
| 1656 } | |
| 1657 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1212513002:
sdk files reorganization to make dart2js a proper package (Closed)
Base URL: git@github.com:dart-lang/sdk.git@master