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..8d4cbc94a9dd0f0c4b6441cf620c55d7262b1efd 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,8 +15744,8 @@ 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
@@ -15767,12 +15769,13 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
   table->SetNumberOfBuckets(num_buckets);
   table->SetNumberOfElements(0);
   table->SetNumberOfDeletedElements(0);
+  table->set_iterators(table->GetHeap()->undefined_value());

[adamk, 2014/04/14 19:15:42]

Nit: s/table->GetHeap()/isolate->heap()/ (as above)

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

   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 +15788,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 +15798,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) {
+  int new_capacity = 4;

[adamk, 2014/04/14 19:15:42]

This magic number probably means kMinCapacity in Allocate() should be moved up
to be a constant on the class.

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

+  Handle<Derived> new_table =
+      Allocate(table->GetIsolate(),
+               new_capacity,
+               table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED);
+
+  for (Object* object = table->iterators();

[adamk, 2014/04/14 19:15:42]

Putting a DisallowHeapAllocation above this loop would be a good idea, since you
use a raw Object* to handle the iteration.

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

+       !object->IsUndefined();
+       object = Iterator::cast(object)->next_iterator()) {
+    Iterator::cast(object)->TableCleared();
+    Iterator::cast(object)->set_table(*new_table);
+  }
+
+  new_table->set_iterators(table->iterators());
+  table->set_iterators(table->GetHeap()->undefined_value());
+
+  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 +15849,21 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
     ++new_entry;
   }
   new_table->SetNumberOfElements(nof);
+  new_table->set_iterators(table->iterators());
+
+  for (Object* object = table->iterators();

[adamk, 2014/04/14 19:15:42]

Same as above, DisallowHeapAllocation

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

+       !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 +15878,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 +15891,49 @@ 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);
+
+  for (Object* object = iterators();

[adamk, 2014/04/14 19:15:42]

And one more DisallowHeapAllocation.

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

+       !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(int kind) {
+  Handle<Iterator> new_iterator = Iterator::Create(GetIsolate());
+  new_iterator->set_previous_iterator(GetHeap()->undefined_value());
+  new_iterator->set_table(this);

[adamk, 2014/04/14 19:15:42]

You triggered an allocation above, but are referring to a bare |this| here,
which is unsafe. CreateIterator has to be a static, and take the table it's to
operate on as a a handlified argument.

Would be nice to make this a lint error in V8...

+  new_iterator->set_index(Smi::FromInt(0));
+  new_iterator->set_count(Smi::FromInt(0));
+  new_iterator->set_kind(Smi::FromInt(kind));
+
+  Object* old_iterator = iterators();
+  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(GetHeap()->undefined_value());

[adamk, 2014/04/14 19:15:42]

Nit: whitespace off here (extra space)

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Done.

+  }
+
+  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 +15959,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 +15978,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 +15996,176 @@ 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();

[adamk, 2014/04/14 19:15:42]

I see this a lot, maybe OrderedHashTable should expose an accessor that returns
the result of this expression.

[arv (Not doing code reviews), 2014/04/14 19:51:49]

Any suggestion for a name?

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

FilledCapacity()? UsedCapacity()?

+
+  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());
+
+  int index = this->index()->value() + 1;
+  int count = this->count()->value() + 1;
+  set_index(Smi::FromInt(index));
+  set_count(Smi::FromInt(count));
+  Seek();
+
+  TableType* table = TableType::cast(this->table());
+  int element_count =
+      table->NumberOfElements() + table->NumberOfDeletedElements();
+
+  if (index >= element_count) {
+    Close();
+  }
+}
+
+
+template<class Derived, class TableType>
+Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next() {
+  Isolate* isolate = GetIsolate();
+  Factory* factory = isolate->factory();
+
+  Object* object = this->table();
+
+  if (!object->IsUndefined()) {
+    TableType* table = TableType::cast(object);
+    int index = this->index()->value();
+    if (index < table->NumberOfElements() + table->NumberOfDeletedElements()) {
+      int entry_index = table->EntryToIndex(index);
+      Handle<Object> value =
+          static_cast<Derived*>(this)->ValueForKind(entry_index);
+      MoveNext();
+      return factory->CreateIteratorResultObject(value, false);

[adamk, 2014/04/14 19:15:42]

Method should be static since it does allocation.

[adamk, 2014/04/14 19:15:42]

I notice you pass false here unconditionally, even if the table is already
Closed() at this point. Is that per spec, or is it up to the implementation?

Also makes me wonder, what if the forEach function adds an entry to the table
during its final callback? It looks like that might cause the forEach to
terminate without hitting that last entry, and yet I think the spec would say
that the newly-added entry should also be iterated over...

[arv (Not doing code reviews), 2014/04/14 19:51:49]

I think you are right. I'll review the spec and add tests.

[arv (Not doing code reviews), 2014/04/14 21:41:56]

Done.

+    }
+  }
+
+  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(int entry_index) {
+  int kind = this->kind()->value();
+  ASSERT(kind == kKindValues || kind == kKindEntries);

[adamk, 2014/04/14 19:15:42]

I suppose it's arbitrary, but I was surprised at that kKindValues here refers to
the set's keys....

[arv (Not doing code reviews), 2014/04/14 19:51:49]

This follows from the spec. Set.prototype has values but not keys. We could
internally only use keys but either way it is pretty arbitrary.

I added a comment.

+
+  Isolate* isolate = GetIsolate();
+  Factory* factory = isolate->factory();
+  OrderedHashSet* table = OrderedHashSet::cast(this->table());
+
+  Handle<Object> value = Handle<Object>(table->get(entry_index), isolate);
+
+  if (kind == kKindEntries) {
+    Handle<FixedArray> array = factory->NewFixedArray(2);

[adamk, 2014/04/14 19:15:42]

This method should be static since it does allocation.

[arv (Not doing code reviews), 2014/04/14 21:41:56]

Done.

+    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(int entry_index) {
+  int kind = this->kind()->value();
+  ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries);
+
+  Isolate* isolate = GetIsolate();
+  Factory* factory = isolate->factory();
+  OrderedHashMap* table = OrderedHashMap::cast(this->table());
+
+  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);
+      Handle<FixedArray> array = factory->NewFixedArray(2);
+      array->set(0, key);
+      array->set(1, value);
+      return factory->NewJSArrayWithElements(array);

[adamk, 2014/04/14 19:15:42]

Same as above, should be static.

[arv (Not doing code reviews), 2014/04/14 21:41:56]

Done.

+    }
+  }
+
+  UNREACHABLE();
+  return factory->undefined_value();
+}
+
+
 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
     DeclaredAccessorDescriptor* descriptor)
     : array_(descriptor->serialized_data()->GetDataStartAddress()),