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