ES6: Add support for Map/Set forEach

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 2a54d3cb5ec18c0ee3fe0c055e0c64809c7d14a3..070a58c5dd978280e9ded63ca4e4fdcc6d0beea9 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -1675,6 +1675,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:
@@ -16320,15 +16322,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);
@@ -16345,12 +16346,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();
@@ -16363,8 +16365,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();
@@ -16373,8 +16375,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(),
@@ -16401,12 +16426,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;
@@ -16421,9 +16458,9 @@ int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) {
 }
 
 
-template<class Derived, int entrysize>
-int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) {
-  int entry = NumberOfElements() + NumberOfDeletedElements();
+template<class Derived, class Iterator, int entrysize>
+int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) {
+  int entry = UsedCapacity();
   int bucket = HashToBucket(hash);
   int index = EntryToIndex(entry);
   Object* chain_entry = get(kHashTableStartIndex + bucket);
@@ -16434,19 +16471,26 @@ 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 OrderedHashTable<OrderedHashSet, 1>;
-template class OrderedHashTable<OrderedHashMap, 2>;
+template class OrderedHashTable<OrderedHashSet, JSSetIterator, 1>;
+template class OrderedHashTable<OrderedHashMap, JSMapIterator, 2>;

[adamk, 2014/04/16 18:35:11]

Based on the Windows build error, I think you need a template instantiation
here:

template int OrderedHashTable<OrderedHashMap, JSMapIterator,
2>::FindEntry(Object* key);

[arv (Not doing code reviews), 2014/04/16 18:49:54]

Done.

 
 
 bool OrderedHashSet::Contains(Object* key) {
@@ -16472,7 +16516,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);
 }
 
@@ -16492,7 +16535,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);
   }
 
@@ -16511,6 +16553,206 @@ 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;
+
+  DisallowHeapAllocation no_allocation;
+
+  Object* undefined = GetHeap()->undefined_value();
+  TableType* table = TableType::cast(this->table());
+  Object* previous = previous_iterator();
+  Object* next = next_iterator();
+
+  if (previous == undefined) {
+    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(undefined);
+  set_next_iterator(undefined);
+  set_table(undefined);
+}
+
+
+template<class Derived, class TableType>
+void OrderedHashTableIterator<Derived, TableType>::Seek() {
+  ASSERT(!Closed());
+
+  DisallowHeapAllocation no_allocation;
+
+  int index = this->index()->value();
+
+  TableType* table = TableType::cast(this->table());
+  int used_capacity = table->UsedCapacity();
+
+  while (index < used_capacity && 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();
+
+  Handle<Object> object(iterator->table(), isolate);
+
+  if (!object->IsUndefined()) {
+    Handle<TableType> table = Handle<TableType>::cast(object);
+    int index = iterator->index()->value();
+    if (index < table->UsedCapacity()) {
+      int entry_index = table->EntryToIndex(index);
+      iterator->MoveNext();
+      Handle<Object> value = Derived::ValueForKind(iterator, entry_index);
+      return factory->NewIteratorResultObject(value, false);
+    } else {
+      iterator->Close();
+    }
+  }
+
+  return factory->NewIteratorResultObject(factory->undefined_value(), true);
+}
+
+
+template<class Derived, class TableType>
+Handle<Derived> OrderedHashTableIterator<Derived, TableType>::CreateInternal(
+    Handle<Map> map,
+    Handle<TableType> table,
+    int kind) {
+  Isolate* isolate = table->GetIsolate();
+
+  Handle<Object> undefined = isolate->factory()->undefined_value();
+
+  Handle<Derived> new_iterator = Handle<Derived>::cast(
+      isolate->factory()->NewJSObjectFromMap(map));
+  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));
+
+  Handle<Object> old_iterator(table->iterators(), isolate);
+  if (!old_iterator->IsUndefined()) {
+    Handle<Derived>::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 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>;
+template class OrderedHashTableIterator<JSMapIterator, OrderedHashMap>;

[adamk, 2014/04/16 18:35:11]

Based on the windows build errors, I think you need some more explicit template
instantiations here:

template Handle<JSObject> OrderedHashTableIterator<JSSetIterator,
OrderedHashSet>::Next(Handle<JSSetIterator> iterator);
template Handle<JSObject> OrderedHashTableIterator<JSMapIterator,
OrderedHashMap>::Next(Handle<JSMapIterator> iterator);

[arv (Not doing code reviews), 2014/04/16 18:49:54]

Done.

+
+
+Handle<JSSetIterator> JSSetIterator::Create(
+    Handle<OrderedHashSet> table, int kind) {
+  return CreateInternal(table->GetIsolate()->set_iterator_map(), table, kind);
+}
+
+
+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();
+
+  Handle<OrderedHashSet> table(
+      OrderedHashSet::cast(iterator->table()), isolate);
+  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(
+    Handle<OrderedHashMap> table,
+    int kind) {
+  return CreateInternal(table->GetIsolate()->map_iterator_map(), table, kind);
+}
+
+
+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();
+
+  Handle<OrderedHashMap> table(
+      OrderedHashMap::cast(iterator->table()), isolate);
+
+  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: {
+      Handle<Object> key(table->get(entry_index), isolate);
+      Handle<Object> value(table->get(entry_index + 1), isolate);
+      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()),