1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 (function(global, utils) { 6 "use strict"; 7 8 %CheckIsBootstrapping(); 9 10 // ------------------------------------------------------------------- 11 // Imports 12 13 var GlobalMap = global.Map; 14 var GlobalObject = global.Object; 15 var GlobalSet = global.Set; 16 var hashCodeSymbol = utils.ImportNow("hash_code_symbol"); 17 var IntRandom; 18 var MakeTypeError; 19 var MapIterator; 20 var NumberIsNaN; 21 var SetIterator; 22 var speciesSymbol = utils.ImportNow("species_symbol"); 23 var toStringTagSymbol = utils.ImportNow("to_string_tag_symbol"); 24 25 utils.Import(function(from) { 26 IntRandom = from.IntRandom; 27 MakeTypeError = from.MakeTypeError; 28 MapIterator = from.MapIterator; 29 NumberIsNaN = from.NumberIsNaN; 30 SetIterator = from.SetIterator; 31 }); 32 33 // ------------------------------------------------------------------- 34 35 function HashToEntry(table, hash, numBuckets) { 36 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); 37 return ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); 38 } 39 %SetForceInlineFlag(HashToEntry); 40 41 42 function SetFindEntry(table, numBuckets, key, hash) { 43 var entry = HashToEntry(table, hash, numBuckets); 44 if (entry === NOT_FOUND) return entry; 45 var candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets); 46 if (key === candidate) return entry; 47 var keyIsNaN = NumberIsNaN(key); 48 while (true) { 49 if (keyIsNaN && NumberIsNaN(candidate)) { 50 return entry; 51 } 52 entry = ORDERED_HASH_SET_CHAIN_AT(table, entry, numBuckets); 53 if (entry === NOT_FOUND) return entry; 54 candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets); 55 if (key === candidate) return entry; 56 } 57 return NOT_FOUND; 58 } 59 %SetForceInlineFlag(SetFindEntry); 60 61 62 function MapFindEntry(table, numBuckets, key, hash) { 63 var entry = HashToEntry(table, hash, numBuckets); 64 if (entry === NOT_FOUND) return entry; 65 var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets); 66 if (key === candidate) return entry; 67 var keyIsNaN = NumberIsNaN(key); 68 while (true) { 69 if (keyIsNaN && NumberIsNaN(candidate)) { 70 return entry; 71 } 72 entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets); 73 if (entry === NOT_FOUND) return entry; 74 candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets); 75 if (key === candidate) return entry; 76 } 77 return NOT_FOUND; 78 } 79 %SetForceInlineFlag(MapFindEntry); 80 81 82 function ComputeIntegerHash(key, seed) { 83 var hash = key; 84 hash = hash ^ seed; 85 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 86 hash = hash ^ (hash >>> 12); 87 hash = hash + (hash << 2); 88 hash = hash ^ (hash >>> 4); 89 hash = (hash * 2057) | 0; // hash = (hash + (hash << 3)) + (hash << 11); 90 hash = hash ^ (hash >>> 16); 91 return hash & 0x3fffffff; 92 } 93 %SetForceInlineFlag(ComputeIntegerHash); 94 95 function GetExistingHash(key) { 96 if (%_IsSmi(key)) { 97 return ComputeIntegerHash(key, 0); 98 } 99 if (IS_STRING(key)) { 100 var field = %_StringGetRawHashField(key); 101 if ((field & 1 /* Name::kHashNotComputedMask */) === 0) { 102 return field >>> 2 /* Name::kHashShift */; 103 } 104 } else if (IS_RECEIVER(key) && !IS_PROXY(key) && !IS_GLOBAL(key)) { 105 var hash = GET_PRIVATE(key, hashCodeSymbol); 106 return hash; 107 } 108 return %GenericHash(key); 109 } 110 %SetForceInlineFlag(GetExistingHash); 111 112 113 function GetHash(key) { 114 var hash = GetExistingHash(key); 115 if (IS_UNDEFINED(hash)) { 116 hash = IntRandom() | 0; 117 if (hash === 0) hash = 1; 118 SET_PRIVATE(key, hashCodeSymbol, hash); 119 } 120 return hash; 121 } 122 %SetForceInlineFlag(GetHash); 123 124 125 // ------------------------------------------------------------------- 126 // Harmony Set 127 128 function SetConstructor(iterable) { 129 if (IS_UNDEFINED(new.target)) { 130 throw MakeTypeError(kConstructorNotFunction, "Set"); 131 } 132 133 %_SetInitialize(this); 134 135 if (!IS_NULL_OR_UNDEFINED(iterable)) { 136 var adder = this.add; 137 if (!IS_CALLABLE(adder)) { 138 throw MakeTypeError(kPropertyNotFunction, adder, 'add', this); 139 } 140 141 for (var value of iterable) { 142 %_Call(adder, this, value); 143 } 144 } 145 } 146 147 148 function SetAdd(key) { 149 if (!IS_SET(this)) { 150 throw MakeTypeError(kIncompatibleMethodReceiver, 'Set.prototype.add', this); 151 } 152 // Normalize -0 to +0 as required by the spec. 153 // Even though we use SameValueZero as the comparison for the keys we don't 154 // want to ever store -0 as the key since the key is directly exposed when 155 // doing iteration. 156 if (key === 0) { 157 key = 0; 158 } 159 var table = %_JSCollectionGetTable(this); 160 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 161 var hash = GetHash(key); 162 if (SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND) return this; 163 164 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 165 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); 166 var capacity = numBuckets << 1; 167 if ((nof + nod) >= capacity) { 168 // Need to grow, bail out to runtime. 169 %SetGrow(this); 170 // Re-load state from the grown backing store. 171 table = %_JSCollectionGetTable(this); 172 numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 173 nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 174 nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); 175 } 176 var entry = nof + nod; 177 var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets); 178 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); 179 var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); 180 ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry); 181 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1); 182 FIXED_ARRAY_SET(table, index, key); 183 FIXED_ARRAY_SET_SMI(table, index + 1, chainEntry); 184 return this; 185 } 186 187 188 function SetHas(key) { 189 if (!IS_SET(this)) { 190 throw MakeTypeError(kIncompatibleMethodReceiver, 'Set.prototype.has', this); 191 } 192 var table = %_JSCollectionGetTable(this); 193 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 194 var hash = GetExistingHash(key); 195 if (IS_UNDEFINED(hash)) return false; 196 return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND; 197 } 198 199 200 function SetDelete(key) { 201 if (!IS_SET(this)) { 202 throw MakeTypeError(kIncompatibleMethodReceiver, 203 'Set.prototype.delete', this); 204 } 205 var table = %_JSCollectionGetTable(this); 206 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 207 var hash = GetExistingHash(key); 208 if (IS_UNDEFINED(hash)) return false; 209 var entry = SetFindEntry(table, numBuckets, key, hash); 210 if (entry === NOT_FOUND) return false; 211 212 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1; 213 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1; 214 var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets); 215 FIXED_ARRAY_SET(table, index, %_TheHole()); 216 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof); 217 ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod); 218 if (nof < (numBuckets >>> 1)) %SetShrink(this); 219 return true; 220 } 221 222 223 function SetGetSize() { 224 if (!IS_SET(this)) { 225 throw MakeTypeError(kIncompatibleMethodReceiver, 226 'Set.prototype.size', this); 227 } 228 var table = %_JSCollectionGetTable(this); 229 return ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 230 } 231 232 233 function SetClearJS() { 234 if (!IS_SET(this)) { 235 throw MakeTypeError(kIncompatibleMethodReceiver, 236 'Set.prototype.clear', this); 237 } 238 %_SetClear(this); 239 } 240 241 242 function SetForEach(f, receiver) { 243 if (!IS_SET(this)) { 244 throw MakeTypeError(kIncompatibleMethodReceiver, 245 'Set.prototype.forEach', this); 246 } 247 248 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); 249 250 var iterator = new SetIterator(this, ITERATOR_KIND_VALUES); 251 var key; 252 var value_array = [UNDEFINED]; 253 while (%SetIteratorNext(iterator, value_array)) { 254 key = value_array[0]; 255 %_Call(f, receiver, key, key, this); 256 } 257 } 258 259 260 function SetSpecies() { 261 return this; 262 } 263 264 265 // ------------------------------------------------------------------- 266 267 %SetCode(GlobalSet, SetConstructor); 268 %FunctionSetLength(GlobalSet, 0); 269 %FunctionSetPrototype(GlobalSet, new GlobalObject()); 270 %AddNamedProperty(GlobalSet.prototype, "constructor", GlobalSet, DONT_ENUM); 271 %AddNamedProperty(GlobalSet.prototype, toStringTagSymbol, "Set", 272 DONT_ENUM | READ_ONLY); 273 274 %FunctionSetLength(SetForEach, 1); 275 276 utils.InstallGetter(GlobalSet, speciesSymbol, SetSpecies); 277 278 // Set up the non-enumerable functions on the Set prototype object. 279 utils.InstallGetter(GlobalSet.prototype, "size", SetGetSize); 280 utils.InstallFunctions(GlobalSet.prototype, DONT_ENUM, [ 281 "add", SetAdd, 282 "has", SetHas, 283 "delete", SetDelete, 284 "clear", SetClearJS, 285 "forEach", SetForEach 286 ]); 287 288 289 // ------------------------------------------------------------------- 290 // Harmony Map 291 292 function MapConstructor(iterable) { 293 if (IS_UNDEFINED(new.target)) { 294 throw MakeTypeError(kConstructorNotFunction, "Map"); 295 } 296 297 %_MapInitialize(this); 298 299 if (!IS_NULL_OR_UNDEFINED(iterable)) { 300 var adder = this.set; 301 if (!IS_CALLABLE(adder)) { 302 throw MakeTypeError(kPropertyNotFunction, adder, 'set', this); 303 } 304 305 for (var nextItem of iterable) { 306 if (!IS_RECEIVER(nextItem)) { 307 throw MakeTypeError(kIteratorValueNotAnObject, nextItem); 308 } 309 %_Call(adder, this, nextItem[0], nextItem[1]); 310 } 311 } 312 } 313 314 315 function MapGet(key) { 316 if (!IS_MAP(this)) { 317 throw MakeTypeError(kIncompatibleMethodReceiver, 318 'Map.prototype.get', this); 319 } 320 var table = %_JSCollectionGetTable(this); 321 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 322 var hash = GetExistingHash(key); 323 if (IS_UNDEFINED(hash)) return UNDEFINED; 324 var entry = MapFindEntry(table, numBuckets, key, hash); 325 if (entry === NOT_FOUND) return UNDEFINED; 326 return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets); 327 } 328 329 330 function MapSet(key, value) { 331 if (!IS_MAP(this)) { 332 throw MakeTypeError(kIncompatibleMethodReceiver, 333 'Map.prototype.set', this); 334 } 335 // Normalize -0 to +0 as required by the spec. 336 // Even though we use SameValueZero as the comparison for the keys we don't 337 // want to ever store -0 as the key since the key is directly exposed when 338 // doing iteration. 339 if (key === 0) { 340 key = 0; 341 } 342 343 var table = %_JSCollectionGetTable(this); 344 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 345 var hash = GetHash(key); 346 var entry = MapFindEntry(table, numBuckets, key, hash); 347 if (entry !== NOT_FOUND) { 348 var existingIndex = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); 349 FIXED_ARRAY_SET(table, existingIndex + 1, value); 350 return this; 351 } 352 353 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 354 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); 355 var capacity = numBuckets << 1; 356 if ((nof + nod) >= capacity) { 357 // Need to grow, bail out to runtime. 358 %MapGrow(this); 359 // Re-load state from the grown backing store. 360 table = %_JSCollectionGetTable(this); 361 numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 362 nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 363 nod = ORDERED_HASH_TABLE_DELETED_COUNT(table); 364 } 365 entry = nof + nod; 366 var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); 367 var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets); 368 var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket); 369 ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry); 370 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1); 371 FIXED_ARRAY_SET(table, index, key); 372 FIXED_ARRAY_SET(table, index + 1, value); 373 FIXED_ARRAY_SET(table, index + 2, chainEntry); 374 return this; 375 } 376 377 378 function MapHas(key) { 379 if (!IS_MAP(this)) { 380 throw MakeTypeError(kIncompatibleMethodReceiver, 381 'Map.prototype.has', this); 382 } 383 var table = %_JSCollectionGetTable(this); 384 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 385 var hash = GetHash(key); 386 return MapFindEntry(table, numBuckets, key, hash) !== NOT_FOUND; 387 } 388 389 390 function MapDelete(key) { 391 if (!IS_MAP(this)) { 392 throw MakeTypeError(kIncompatibleMethodReceiver, 393 'Map.prototype.delete', this); 394 } 395 var table = %_JSCollectionGetTable(this); 396 var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 397 var hash = GetHash(key); 398 var entry = MapFindEntry(table, numBuckets, key, hash); 399 if (entry === NOT_FOUND) return false; 400 401 var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1; 402 var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1; 403 var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets); 404 FIXED_ARRAY_SET(table, index, %_TheHole()); 405 FIXED_ARRAY_SET(table, index + 1, %_TheHole()); 406 ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof); 407 ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod); 408 if (nof < (numBuckets >>> 1)) %MapShrink(this); 409 return true; 410 } 411 412 413 function MapGetSize() { 414 if (!IS_MAP(this)) { 415 throw MakeTypeError(kIncompatibleMethodReceiver, 416 'Map.prototype.size', this); 417 } 418 var table = %_JSCollectionGetTable(this); 419 return ORDERED_HASH_TABLE_ELEMENT_COUNT(table); 420 } 421 422 423 function MapClearJS() { 424 if (!IS_MAP(this)) { 425 throw MakeTypeError(kIncompatibleMethodReceiver, 426 'Map.prototype.clear', this); 427 } 428 %_MapClear(this); 429 } 430 431 432 function MapForEach(f, receiver) { 433 if (!IS_MAP(this)) { 434 throw MakeTypeError(kIncompatibleMethodReceiver, 435 'Map.prototype.forEach', this); 436 } 437 438 if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f); 439 440 var iterator = new MapIterator(this, ITERATOR_KIND_ENTRIES); 441 var value_array = [UNDEFINED, UNDEFINED]; 442 while (%MapIteratorNext(iterator, value_array)) { 443 %_Call(f, receiver, value_array[1], value_array[0], this); 444 } 445 } 446 447 448 function MapSpecies() { 449 return this; 450 } 451 452 // ------------------------------------------------------------------- 453 454 %SetCode(GlobalMap, MapConstructor); 455 %FunctionSetLength(GlobalMap, 0); 456 %FunctionSetPrototype(GlobalMap, new GlobalObject()); 457 %AddNamedProperty(GlobalMap.prototype, "constructor", GlobalMap, DONT_ENUM); 458 %AddNamedProperty( 459 GlobalMap.prototype, toStringTagSymbol, "Map", DONT_ENUM | READ_ONLY); 460 461 %FunctionSetLength(MapForEach, 1); 462 463 utils.InstallGetter(GlobalMap, speciesSymbol, MapSpecies); 464 465 // Set up the non-enumerable functions on the Map prototype object. 466 utils.InstallGetter(GlobalMap.prototype, "size", MapGetSize); 467 utils.InstallFunctions(GlobalMap.prototype, DONT_ENUM, [ 468 "get", MapGet, 469 "set", MapSet, 470 "has", MapHas, 471 "delete", MapDelete, 472 "clear", MapClearJS, 473 "forEach", MapForEach 474 ]); 475 476 // ----------------------------------------------------------------------- 477 // Exports 478 479 %InstallToContext([ 480 "map_get", MapGet, 481 "map_set", MapSet, 482 "map_has", MapHas, 483 "map_delete", MapDelete, 484 "set_add", SetAdd, 485 "set_has", SetHas, 486 "set_delete", SetDelete, 487 ]); 488 489 utils.Export(function(to) { 490 to.GetExistingHash = GetExistingHash; 491 to.GetHash = GetHash; 492 }); 493 494 }) 495