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

src/objects.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1674 matching lines @@
     case JS_GENERATOR_OBJECT_TYPE:
     case JS_MODULE_TYPE:
     case JS_VALUE_TYPE:
     case JS_DATE_TYPE:
     case JS_ARRAY_TYPE:
     case JS_ARRAY_BUFFER_TYPE:
     case JS_TYPED_ARRAY_TYPE:
     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:
     case JS_GLOBAL_PROXY_TYPE:
     case JS_GLOBAL_OBJECT_TYPE:
     case JS_BUILTINS_OBJECT_TYPE:
     case JS_MESSAGE_OBJECT_TYPE:
       JSObject::BodyDescriptor::IterateBody(this, object_size, v);
       break;
     case JS_FUNCTION_TYPE:
@@ skipping 14030 matching lines @@
 }
 
 
 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) {
   set(EntryToIndex(entry), key);
   set(EntryToValueIndex(entry), value);
   ElementAdded();
 }
 
 
-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);
   }
   int num_buckets = capacity / kLoadFactor;
   Handle<FixedArray> backing_store = isolate->factory()->NewFixedArray(
       kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure);
   backing_store->set_map_no_write_barrier(
       isolate->heap()->ordered_hash_table_map());
   Handle<Derived> table = Handle<Derived>::cast(backing_store);
   for (int i = 0; i < num_buckets; ++i) {
     table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound));
   }
   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();
   int capacity = table->Capacity();
   if ((nof + nod) < capacity) return table;
   // Don't need to grow if we can simply clear out deleted entries instead.
   // Note that we can't compact in place, though, so we always allocate
   // a new table.
   return Rehash(table, (nod < (capacity >> 1)) ? capacity << 1 : capacity);
 }
 
 
-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();
   if (nof > (capacity >> 2)) return table;
   return Rehash(table, capacity / 2);
 }
 
 
-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(),
                new_capacity,
                table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED);
   int nof = table->NumberOfElements();
   int nod = table->NumberOfDeletedElements();
   int new_buckets = new_table->NumberOfBuckets();
   int new_entry = 0;
   for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
     Object* key = table->KeyAt(old_entry);
     if (key->IsTheHole()) continue;
     Object* hash = key->GetHash();
     int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
     Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
     new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
     int new_index = new_table->EntryToIndex(new_entry);
     int old_index = table->EntryToIndex(old_entry);
     for (int i = 0; i < entrysize; ++i) {
       Object* value = table->get(old_index + i);
       new_table->set(new_index + i, value);
     }
     new_table->set(new_index + kChainOffset, chain_entry);
     ++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;
   for (int entry = HashToEntry(Smi::cast(hash)->value());
        entry != kNotFound;
        entry = ChainAt(entry)) {
     Object* candidate = KeyAt(entry);
     if (candidate->SameValue(key))
       return entry;
   }
   return kNotFound;
 }
 
 
-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);
   Object* chain_entry = get(kHashTableStartIndex + bucket);
   set(kHashTableStartIndex + bucket, Smi::FromInt(entry));
   set(index + kChainOffset, chain_entry);
   SetNumberOfElements(NumberOfElements() + 1);
   return index;
 }
 
 
-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 OrderedHashTable<OrderedHashSet, 1>;
-template class OrderedHashTable<OrderedHashMap, 2>;
+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, JSSetIterator, 1>;
+template class OrderedHashTable<OrderedHashMap, JSMapIterator, 2>;
 
 
 bool OrderedHashSet::Contains(Object* key) {
   return FindEntry(key) != kNotFound;
 }
 
 
 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table,
                                            Handle<Object> key) {
   if (table->FindEntry(*key) != kNotFound) return table;
 
   table = EnsureGrowable(table);
 
   Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
   int index = table->AddEntry(Smi::cast(*hash)->value());
   table->set(index, *key);
   return table;
 }
 
 
 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table,
                                               Handle<Object> key) {
   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);
 }
 
 
 Object* OrderedHashMap::Lookup(Object* key) {
   int entry = FindEntry(key);
   if (entry == kNotFound) return GetHeap()->the_hole_value();
   return ValueAt(entry);
 }
 
 
 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
                                            Handle<Object> key,
                                            Handle<Object> value) {
   int entry = table->FindEntry(*key);
 
   if (value->IsTheHole()) {
     if (entry == kNotFound) return table;
     table->RemoveEntry(entry);
-    // TODO(adamk): Only shrink if not iterating
     return Shrink(table);
   }
 
   if (entry != kNotFound) {
     table->set(table->EntryToIndex(entry) + kValueOffset, *value);
     return table;
   }
 
   table = EnsureGrowable(table);
 
   Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate());
   int index = table->AddEntry(Smi::cast(*hash)->value());
   table->set(index, *key);
   table->set(index + kValueOffset, *value);
   return 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()),
       length_(descriptor->serialized_data()->length()),
       offset_(0) {
 }
 
 
 const DeclaredAccessorDescriptorData*
   DeclaredAccessorDescriptorIterator::Next() {
@@ skipping 571 matching lines @@
 #define ERROR_MESSAGES_TEXTS(C, T) T,
   static const char* error_messages_[] = {
       ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS)
   };
 #undef ERROR_MESSAGES_TEXTS
   return error_messages_[reason];
 }
 
 
 } }  // namespace v8::internal