Reimplement Maps and Sets in JS

src/runtime/runtime-collections.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/v8.h"
 
 #include "src/arguments.h"
 #include "src/runtime/runtime-utils.h"
 
 
 namespace v8 {
 namespace internal {
 
+
+RUNTIME_FUNCTION(Runtime_StringGetRawHashField) {
+  HandleScope scope(isolate);
+  DCHECK(args.length() == 1);
+  CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
+  return *isolate->factory()->NewNumberFromUint(string->hash_field());
+}
+
+
+RUNTIME_FUNCTION(Runtime_TheHole) {
+  SealHandleScope shs(isolate);
+  DCHECK(args.length() == 0);
+  return isolate->heap()->the_hole_value();

[Michael Starzinger, 2015/03/16 22:54:13]

This will trigger debug code in CEntryStub::Generate that asserts that no
runtime function returns the hole. We probably will need to drop that check.

[adamk, 2015/03/17 09:05:31]

%FixedArrayGet() can already return the hole (which is largely why I need it
here), so indeed it seems like we'd need to drop that check.

+}
+
+
+RUNTIME_FUNCTION(Runtime_FixedArrayGet) {
+  SealHandleScope shs(isolate);
+  DCHECK(args.length() == 2);
+  CONVERT_ARG_CHECKED(FixedArray, object, 0);
+  CONVERT_SMI_ARG_CHECKED(index, 1);
+  return object->get(index);
+}
+
+
+RUNTIME_FUNCTION(Runtime_FixedArraySet) {
+  SealHandleScope shs(isolate);
+  DCHECK(args.length() == 3);
+  CONVERT_ARG_CHECKED(FixedArray, object, 0);
+  CONVERT_SMI_ARG_CHECKED(index, 1);
+  CONVERT_ARG_CHECKED(Object, value, 2);
+  object->set(index, value);
+  return isolate->heap()->undefined_value();
+}
+
+
+RUNTIME_FUNCTION(Runtime_JSCollectionGetTable) {
+  SealHandleScope shs(isolate);
+  DCHECK(args.length() == 1);
+  CONVERT_ARG_CHECKED(JSObject, object, 0);
+  RUNTIME_ASSERT(object->IsJSSet() || object->IsJSMap());
+  return static_cast<JSCollection*>(object)->table();
+}
+
+
+RUNTIME_FUNCTION(Runtime_GenericHash) {
+  HandleScope scope(isolate);
+  DCHECK(args.length() == 1);
+  CONVERT_ARG_HANDLE_CHECKED(Object, object, 0);
+  Handle<Smi> hash = Object::GetOrCreateHash(isolate, object);
+  return *hash;
+}
+
+
 RUNTIME_FUNCTION(Runtime_SetInitialize) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
   Handle<OrderedHashSet> table = isolate->factory()->NewOrderedHashSet();
   holder->set_table(*table);
   return *holder;
 }
 
 
-RUNTIME_FUNCTION(Runtime_SetAdd) {
+RUNTIME_FUNCTION(Runtime_SetGrow) {
   HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
+  DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
   Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
-  table = OrderedHashSet::Add(table, key);
+  table = OrderedHashSet::EnsureGrowable(table);
   holder->set_table(*table);
-  return *holder;
+  return isolate->heap()->undefined_value();
 }
 
 
-RUNTIME_FUNCTION(Runtime_SetHas) {
+RUNTIME_FUNCTION(Runtime_SetShrink) {
   HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
+  DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
   Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
-  return isolate->heap()->ToBoolean(table->Contains(key));
-}
-
-
-RUNTIME_FUNCTION(Runtime_SetDelete) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
-  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
-  Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
-  bool was_present = false;
-  table = OrderedHashSet::Remove(table, key, &was_present);
+  table = OrderedHashSet::Shrink(table);
   holder->set_table(*table);
-  return isolate->heap()->ToBoolean(was_present);
+  return isolate->heap()->undefined_value();
 }
 
 
 RUNTIME_FUNCTION(Runtime_SetClear) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
   Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
   table = OrderedHashSet::Clear(table);
   holder->set_table(*table);
   return isolate->heap()->undefined_value();
 }
 
 
-RUNTIME_FUNCTION(Runtime_SetGetSize) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 1);
-  CONVERT_ARG_HANDLE_CHECKED(JSSet, holder, 0);
-  Handle<OrderedHashSet> table(OrderedHashSet::cast(holder->table()));
-  return Smi::FromInt(table->NumberOfElements());
-}
-
-
 RUNTIME_FUNCTION(Runtime_SetIteratorInitialize) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 3);
   CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSSet, set, 1);
   CONVERT_SMI_ARG_CHECKED(kind, 2)
   RUNTIME_ASSERT(kind == JSSetIterator::kKindValues ||
                  kind == JSSetIterator::kKindEntries);
   Handle<OrderedHashSet> table(OrderedHashSet::cast(set->table()));
   holder->set_table(*table);
@@ skipping 45 matching lines @@
 RUNTIME_FUNCTION(Runtime_MapInitialize) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
   Handle<OrderedHashMap> table = isolate->factory()->NewOrderedHashMap();
   holder->set_table(*table);
   return *holder;
 }
 
 
-RUNTIME_FUNCTION(Runtime_MapGet) {
+RUNTIME_FUNCTION(Runtime_MapShrink) {
   HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
+  DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
   Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
-  Handle<Object> lookup(table->Lookup(key), isolate);
-  return lookup->IsTheHole() ? isolate->heap()->undefined_value() : *lookup;
+  table = OrderedHashMap::Shrink(table);
+  holder->set_table(*table);
+  return isolate->heap()->undefined_value();
 }
 
 
-RUNTIME_FUNCTION(Runtime_MapHas) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
-  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
-  Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
-  Handle<Object> lookup(table->Lookup(key), isolate);
-  return isolate->heap()->ToBoolean(!lookup->IsTheHole());
-}
-
-
-RUNTIME_FUNCTION(Runtime_MapDelete) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 2);
-  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
-  Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
-  bool was_present = false;
-  Handle<OrderedHashMap> new_table =
-      OrderedHashMap::Remove(table, key, &was_present);
-  holder->set_table(*new_table);
-  return isolate->heap()->ToBoolean(was_present);
-}
-
-
 RUNTIME_FUNCTION(Runtime_MapClear) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
   Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
   table = OrderedHashMap::Clear(table);
   holder->set_table(*table);
   return isolate->heap()->undefined_value();
 }
 
 
-RUNTIME_FUNCTION(Runtime_MapSet) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 3);
-  CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
-  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
-  CONVERT_ARG_HANDLE_CHECKED(Object, value, 2);
-  Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
-  Handle<OrderedHashMap> new_table = OrderedHashMap::Put(table, key, value);
-  holder->set_table(*new_table);
-  return *holder;
-}
-
-
-RUNTIME_FUNCTION(Runtime_MapGetSize) {
+RUNTIME_FUNCTION(Runtime_MapGrow) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0);
   Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()));
-  return Smi::FromInt(table->NumberOfElements());
+  table = OrderedHashMap::EnsureGrowable(table);
+  holder->set_table(*table);
+  return isolate->heap()->undefined_value();
 }
 
 
 RUNTIME_FUNCTION(Runtime_MapIteratorInitialize) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 3);
   CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSMap, map, 1);
   CONVERT_SMI_ARG_CHECKED(kind, 2)
   RUNTIME_ASSERT(kind == JSMapIterator::kKindKeys ||
@@ skipping 214 matching lines @@
 
 RUNTIME_FUNCTION(Runtime_ObservationWeakMapCreate) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 0);
   Handle<JSWeakMap> weakmap = isolate->factory()->NewJSWeakMap();
   Runtime::WeakCollectionInitialize(isolate, weakmap);
   return *weakmap;
 }
 }
 }  // namespace v8::internal