ES6: Add support for Map.prototype.forEach and Set.prototype.forEach

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index aaa03203ae444987ec954edb1d4e19012e0791c5..1fb362ad87d45b7764cd53617f0a1fa2a65d8cd6 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -1692,6 +1692,8 @@ void HeapObject::IterateBody(InstanceType type, int object_size,
     case JS_DATA_VIEW_TYPE:
     case JS_SET_TYPE:
     case JS_MAP_TYPE:
+    case JS_SET_ITERATOR_TYPE:
+    case JS_MAP_ITERATOR_TYPE:
     case JS_WEAK_MAP_TYPE:
     case JS_WEAK_SET_TYPE:
     case JS_REGEXP_TYPE:
@@ -15742,15 +15744,14 @@ void WeakHashTable::AddEntry(int entry, Object* key, Object* value) {
 }
 
 
-template<class Derived, int entrysize>
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
+template<class Derived, class Iterator, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Allocate(
     Isolate* isolate, int capacity, PretenureFlag pretenure) {
   // Capacity must be a power of two, since we depend on being able
   // to divide and multiple by 2 (kLoadFactor) to derive capacity
   // from number of buckets. If we decide to change kLoadFactor
   // to something other than 2, capacity should be stored as another
   // field of this object.
-  const int kMinCapacity = 4;
   capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity));
   if (capacity > kMaxCapacity) {
     v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true);
@@ -15767,12 +15768,13 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
   table->SetNumberOfBuckets(num_buckets);
   table->SetNumberOfElements(0);
   table->SetNumberOfDeletedElements(0);
+  table->set_iterators(isolate->heap()->undefined_value());
   return table;
 }
 
 
-template<class Derived, int entrysize>
-Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
+template<class Derived, class Iterator, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::EnsureGrowable(
     Handle<Derived> table) {
   int nof = table->NumberOfElements();
   int nod = table->NumberOfDeletedElements();
@@ -15785,8 +15787,8 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
 }
 
 
-template<class Derived, int entrysize>
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
+template<class Derived, class Iterator, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Shrink(
     Handle<Derived> table) {
   int nof = table->NumberOfElements();
   int capacity = table->Capacity();
@@ -15795,8 +15797,31 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
 }
 
 
-template<class Derived, int entrysize>
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
+template<class Derived, class Iterator, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Clear(
+    Handle<Derived> table) {
+  Handle<Derived> new_table =
+      Allocate(table->GetIsolate(),
+               kMinCapacity,
+               table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED);
+
+  new_table->set_iterators(table->iterators());
+  table->set_iterators(table->GetHeap()->undefined_value());
+
+  DisallowHeapAllocation no_allocation;
+  for (Object* object = new_table->iterators();
+       !object->IsUndefined();
+       object = Iterator::cast(object)->next_iterator()) {
+    Iterator::cast(object)->TableCleared();
+    Iterator::cast(object)->set_table(*new_table);
+  }
+
+  return new_table;
+}
+
+
+template<class Derived, class Iterator, int entrysize>
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash(
     Handle<Derived> table, int new_capacity) {
   Handle<Derived> new_table =
       Allocate(table->GetIsolate(),
@@ -15823,12 +15848,24 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
     ++new_entry;
   }
   new_table->SetNumberOfElements(nof);
+
+  new_table->set_iterators(table->iterators());
+  table->set_iterators(table->GetHeap()->undefined_value());
+
+  DisallowHeapAllocation no_allocation;
+  for (Object* object = new_table->iterators();
+       !object->IsUndefined();
+       object = Iterator::cast(object)->next_iterator()) {
+    Iterator::cast(object)->TableCompacted();
+    Iterator::cast(object)->set_table(*new_table);
+  }
+
   return new_table;
 }
 
 
-template<class Derived, int entrysize>
-int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) {
+template<class Derived, class Iterator, int entrysize>
+int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(Object* key) {
   ASSERT(!key->IsTheHole());
   Object* hash = key->GetHash();
   if (hash->IsUndefined()) return kNotFound;
@@ -15843,8 +15880,8 @@ int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) {
 }
 
 
-template<class Derived, int entrysize>
-int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) {
+template<class Derived, class Iterator, int entrysize>
+int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) {
   int entry = NumberOfElements() + NumberOfDeletedElements();
   int bucket = HashToBucket(hash);
   int index = EntryToIndex(entry);
@@ -15856,19 +15893,52 @@ int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) {
 }
 
 
-template<class Derived, int entrysize>
-void OrderedHashTable<Derived, entrysize>::RemoveEntry(int entry) {
+template<class Derived, class Iterator, int entrysize>
+void OrderedHashTable<Derived, Iterator, entrysize>::RemoveEntry(int entry) {
   int index = EntryToIndex(entry);
   for (int i = 0; i < entrysize; ++i) {
     set_the_hole(index + i);
   }
   SetNumberOfElements(NumberOfElements() - 1);
   SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
+
+  DisallowHeapAllocation no_allocation;
+  for (Object* object = iterators();
+       !object->IsUndefined();
+       object = Iterator::cast(object)->next_iterator()) {
+    Iterator::cast(object)->EntryRemoved(entry);
+  }
+}
+
+
+template<class Derived, class Iterator, int entrysize>
+Handle<Iterator> OrderedHashTable<Derived, Iterator, entrysize>::CreateIterator(
+    Handle<Derived> table,
+    int kind) {
+  Object* undefined = table->GetHeap()->undefined_value();

[adamk, 2014/04/14 21:25:54]

Please use a Handle here (available from isolate->factory()->undefined_value()).

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+  Handle<Iterator> new_iterator = Iterator::Create(table->GetIsolate());
+  new_iterator->set_previous_iterator(undefined);
+  new_iterator->set_table(*table);
+  new_iterator->set_index(Smi::FromInt(0));
+  new_iterator->set_count(Smi::FromInt(0));
+  new_iterator->set_kind(Smi::FromInt(kind));
+
+  Object* old_iterator = table->iterators();

[adamk, 2014/04/14 21:25:54]

Style-wise I'd also handl-ify this one (in case more code gets added below that
happens to cause allocations).

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+  if (!old_iterator->IsUndefined()) {
+    Iterator::cast(old_iterator)->set_previous_iterator(*new_iterator);
+    new_iterator->set_next_iterator(old_iterator);
+  } else {
+    new_iterator->set_next_iterator(undefined);
+  }
+
+  table->set_iterators(*new_iterator);
+
+  return new_iterator;
 }
 
 
-template class OrderedHashTable<OrderedHashSet, 1>;
-template class OrderedHashTable<OrderedHashMap, 2>;
+template class OrderedHashTable<OrderedHashSet, JSSetIterator, 1>;
+template class OrderedHashTable<OrderedHashMap, JSMapIterator, 2>;
 
 
 bool OrderedHashSet::Contains(Object* key) {
@@ -15894,7 +15964,6 @@ Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table,
   int entry = table->FindEntry(*key);
   if (entry == kNotFound) return table;
   table->RemoveEntry(entry);
-  // TODO(adamk): Don't shrink if we're being iterated over
   return Shrink(table);
 }
 
@@ -15914,7 +15983,6 @@ Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
   if (value->IsTheHole()) {
     if (entry == kNotFound) return table;
     table->RemoveEntry(entry);
-    // TODO(adamk): Only shrink if not iterating
     return Shrink(table);
   }
 
@@ -15933,6 +16001,171 @@ Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
 }
 
 
+template<class Derived, class TableType>
+void OrderedHashTableIterator<Derived, TableType>::EntryRemoved(int index) {
+  int i = this->index()->value();
+  if (index < i) {
+    set_count(Smi::FromInt(count()->value() - 1));
+  }
+  if (index == i) {
+    Seek();
+  }
+}
+
+
+template<class Derived, class TableType>
+void OrderedHashTableIterator<Derived, TableType>::Close() {
+  if (Closed()) return;
+
+  TableType* table = TableType::cast(this->table());
+  Object* previous = previous_iterator();
+  Object* next = next_iterator();
+
+  if (previous->IsUndefined()) {
+    ASSERT_EQ(table->iterators(), this);
+    table->set_iterators(next);
+  } else {
+    ASSERT_EQ(Derived::cast(previous)->next_iterator(), this);
+    Derived::cast(previous)->set_next_iterator(next);
+  }
+
+  if (!next->IsUndefined()) {
+    ASSERT_EQ(Derived::cast(next)->previous_iterator(), this);
+    Derived::cast(next)->set_previous_iterator(previous);
+  }
+
+  set_previous_iterator(GetHeap()->undefined_value());
+  set_next_iterator(GetHeap()->undefined_value());
+  set_table(GetHeap()->undefined_value());
+}
+
+
+template<class Derived, class TableType>
+void OrderedHashTableIterator<Derived, TableType>::Seek() {
+  ASSERT(!Closed());
+
+  int index = this->index()->value();
+
+  TableType* table = TableType::cast(this->table());
+  int element_count =
+      table->NumberOfElements() + table->NumberOfDeletedElements();
+
+  while (index < element_count && table->KeyAt(index)->IsTheHole()) {
+    index++;
+  }
+  set_index(Smi::FromInt(index));
+}
+
+
+template<class Derived, class TableType>
+void OrderedHashTableIterator<Derived, TableType>::MoveNext() {
+  ASSERT(!Closed());
+
+  set_index(Smi::FromInt(index()->value() + 1));
+  set_count(Smi::FromInt(count()->value() + 1));
+  Seek();
+}
+
+
+template<class Derived, class TableType>
+Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
+    Handle<Derived> iterator) {
+  Isolate* isolate = iterator->GetIsolate();
+  Factory* factory = isolate->factory();
+
+  Object* object = iterator->table();

[adamk, 2014/04/14 21:25:54]

Need to use a Handle here.

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+
+  if (!object->IsUndefined()) {
+    TableType* table = TableType::cast(object);
+    int index = iterator->index()->value();
+    if (index < table->NumberOfElements() + table->NumberOfDeletedElements()) {
+      int entry_index = table->EntryToIndex(index);
+      iterator->MoveNext();
+      Handle<Object> value = Derived::ValueForKind(iterator, entry_index);
+      return factory->CreateIteratorResultObject(value, false);
+    } else {
+      iterator->Close();
+    }
+  }
+
+  return factory->CreateIteratorResultObject(factory->undefined_value(), true);
+}
+
+
+template class OrderedHashTableIterator<JSSetIterator, OrderedHashSet>;
+template class OrderedHashTableIterator<JSMapIterator, OrderedHashMap>;
+
+
+Handle<JSSetIterator> JSSetIterator::Create(Isolate* isolate) {
+  Handle<Map> map =
+      isolate->factory()->NewMap(JS_SET_ITERATOR_TYPE, JSSetIterator::kSize);
+  return
+      Handle<JSSetIterator>::cast(isolate->factory()->NewJSObjectFromMap(map));
+}
+
+
+Handle<Object> JSSetIterator::ValueForKind(
+    Handle<JSSetIterator> iterator, int entry_index) {
+  int kind = iterator->kind()->value();
+  // Set.prototype only has values and entries.
+  ASSERT(kind == kKindValues || kind == kKindEntries);
+
+  Isolate* isolate = iterator->GetIsolate();
+  Factory* factory = isolate->factory();
+  OrderedHashSet* table = OrderedHashSet::cast(iterator->table());

[adamk, 2014/04/14 21:25:54]

Needs to be a Handle too.

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+
+  Handle<Object> value = Handle<Object>(table->get(entry_index), isolate);
+
+  if (kind == kKindEntries) {
+    Handle<FixedArray> array = factory->NewFixedArray(2);
+    array->set(0, *value);
+    array->set(1, *value);
+    return factory->NewJSArrayWithElements(array);
+  }
+
+  return value;
+}
+
+
+Handle<JSMapIterator> JSMapIterator::Create(Isolate* isolate) {
+  Handle<Map> map =
+      isolate->factory()->NewMap(JS_MAP_ITERATOR_TYPE, JSMapIterator::kSize);
+  return Handle<JSMapIterator>::cast(
+      isolate->factory()->NewJSObjectFromMap(map));
+}
+
+
+Handle<Object> JSMapIterator::ValueForKind(
+    Handle<JSMapIterator> iterator, int entry_index) {
+  int kind = iterator->kind()->value();
+  ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries);
+
+  Isolate* isolate = iterator->GetIsolate();
+  Factory* factory = isolate->factory();
+  OrderedHashMap* table = OrderedHashMap::cast(iterator->table());

[adamk, 2014/04/14 21:25:54]

And this one too.

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+
+  switch (kind) {
+    case kKindKeys:
+      return Handle<Object>(table->get(entry_index), isolate);
+
+    case kKindValues:
+      return Handle<Object>(table->get(entry_index + 1), isolate);
+
+    case kKindEntries: {
+      Object* key = table->get(entry_index);
+      Object* value = table->get(entry_index + 1);

[adamk, 2014/04/14 21:25:54]

These both need to be Handles.

[arv (Not doing code reviews), 2014/04/14 22:13:27]

Done.

+      Handle<FixedArray> array = factory->NewFixedArray(2);
+      array->set(0, key);
+      array->set(1, value);
+      return factory->NewJSArrayWithElements(array);
+    }
+  }
+
+  UNREACHABLE();
+  return factory->undefined_value();
+}
+
+
 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
     DeclaredAccessorDescriptor* descriptor)
     : array_(descriptor->serialized_data()->GetDataStartAddress()),