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

src/objects.h

Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index 1f656bc0b50bbc0f1ad27a19e6345ced0a244515..756309756a39984446a4501eb6fd7a3b256abd7d 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -66,6 +66,8 @@
 //             - JSDataView
 //           - JSSet
 //           - JSMap
+//           - JSSetIterator
+//           - JSMapIterator
 //           - JSWeakCollection
 //             - JSWeakMap
 //             - JSWeakSet
@@ -445,6 +447,8 @@ const int kStubMinorKeyBits = kBitsPerInt - kSmiTagSize - kStubMajorKeyBits;
   V(JS_PROXY_TYPE)                                                             \
   V(JS_SET_TYPE)                                                               \
   V(JS_MAP_TYPE)                                                               \
+  V(JS_SET_ITERATOR_TYPE)                                                      \
+  V(JS_MAP_ITERATOR_TYPE)                                                      \
   V(JS_WEAK_MAP_TYPE)                                                          \
   V(JS_WEAK_SET_TYPE)                                                          \
   V(JS_REGEXP_TYPE)                                                            \
@@ -793,6 +797,8 @@ enum InstanceType {
   JS_DATA_VIEW_TYPE,
   JS_SET_TYPE,
   JS_MAP_TYPE,
+  JS_SET_ITERATOR_TYPE,
+  JS_MAP_ITERATOR_TYPE,
   JS_WEAK_MAP_TYPE,
   JS_WEAK_SET_TYPE,
 
@@ -1053,6 +1059,8 @@ class MaybeObject BASE_EMBEDDED {
   V(JSFunctionProxy)                           \
   V(JSSet)                                     \
   V(JSMap)                                     \
+  V(JSSetIterator)                             \
+  V(JSMapIterator)                             \
   V(JSWeakCollection)                          \
   V(JSWeakMap)                                 \
   V(JSWeakSet)                                 \
@@ -4268,16 +4276,17 @@ class ObjectHashTable: public HashTable<ObjectHashTableShape, Object*> {
 //   [0]: bucket count
 //   [1]: element count
 //   [2]: deleted element count
-//   [3..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset
+//   [3]: live iterators (double linked list)

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

Nit: s/double linked/doubly-linked/

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

Done.

+//   [4..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset
 //                                 into the data table (see below) where the
 //                                 first item in this bucket is stored.
-//   [3 + NumberOfBuckets()..length]: "data table", an array of length
+//   [4 + NumberOfBuckets()..length]: "data table", an array of length
 //                            Capacity() * kEntrySize, where the first entrysize
 //                            items are handled by the derived class and the
 //                            item at kChainOffset is another entry into the
 //                            data table indicating the next entry in this hash
 //                            bucket.
-template<class Derived, int entrysize>
+template<class Derived, class Iterator, int entrysize>
 class OrderedHashTable: public FixedArray {
  public:
   // Returns an OrderedHashTable with a capacity of at least |capacity|.
@@ -4292,6 +4301,10 @@ class OrderedHashTable: public FixedArray {
   // if possible.
   static Handle<Derived> Shrink(Handle<Derived> table);
 
+  // Returns a new empty OrderedHashTable and updates all the iterators to
+  // point to the new table.
+  static Handle<Derived> Clear(Handle<Derived> table);
+
   // Returns kNotFound if the key isn't present.
   int FindEntry(Object* key);
 
@@ -4307,6 +4320,16 @@ class OrderedHashTable: public FixedArray {
     return Smi::cast(get(kNumberOfBucketsIndex))->value();
   }
 
+  Handle<Iterator> CreateIterator(int kind);

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

This should at least have a comment referring to the enum it's supposed to
conform to.

Also, needs to be static.

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

This is an instance method. The iterator depends on the OrderedHashTable.

I added comment clarifying this. Maybe we should provide some other API to make
this more explicit?

+
+  Object* iterators() {
+    return get(kIteratorsIndex);

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

Nit: if you can fit these on one line, please do so.

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

Done.

+  }
+
+  void set_iterators(Object* value) {
+    set(kIteratorsIndex, value);
+  }
+
   // Returns the index into the data table where the new entry
   // should be placed. The table is assumed to have enough space
   // for a new entry.
@@ -4321,6 +4344,8 @@ class OrderedHashTable: public FixedArray {
     return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
   }
 
+  Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
+
   static const int kNotFound = -1;
 
  private:
@@ -4342,8 +4367,6 @@ class OrderedHashTable: public FixedArray {
     return NumberOfBuckets() * kLoadFactor;
   }
 
-  Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
-
   // Returns the next entry for the given entry.
   int ChainAt(int entry) {
     return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value();
@@ -4361,7 +4384,8 @@ class OrderedHashTable: public FixedArray {
   static const int kNumberOfBucketsIndex = 0;
   static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1;
   static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
-  static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1;
+  static const int kIteratorsIndex = kNumberOfDeletedElementsIndex + 1;
+  static const int kHashTableStartIndex = kIteratorsIndex + 1;
 
   static const int kEntrySize = entrysize + 1;
   static const int kChainOffset = entrysize;
@@ -4373,7 +4397,11 @@ class OrderedHashTable: public FixedArray {
 };
 
 
-class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
+class JSSetIterator;
+
+
+class OrderedHashSet: public OrderedHashTable<
+    OrderedHashSet, JSSetIterator, 1> {
  public:
   static OrderedHashSet* cast(Object* obj) {
     ASSERT(obj->IsOrderedHashTable());
@@ -4388,7 +4416,11 @@ class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
 };
 
 
-class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> {
+class JSMapIterator;
+
+
+class OrderedHashMap:public OrderedHashTable<
+    OrderedHashMap, JSMapIterator, 2> {
  public:
   static OrderedHashMap* cast(Object* obj) {
     ASSERT(obj->IsOrderedHashTable());
@@ -7528,7 +7560,7 @@ class JSGeneratorObject: public JSObject {
   enum ResumeMode { NEXT, THROW };
 
   // Yielding from a generator returns an object with the following inobject
-  // properties.  See Context::generator_result_map() for the map.
+  // properties.  See Context::iterator_result_map() for the map.
   static const int kResultValuePropertyIndex = 0;
   static const int kResultDonePropertyIndex = 1;
   static const int kResultPropertyCount = 2;
@@ -9996,6 +10028,135 @@ class JSMap: public JSObject {
 };
 
 
+// OrderedHashTableIterator is an iterator that iterates over the keys and
+// values of an OrderedHashTable.
+//
+// The hash table has a reference to the iterator and the iterators themselves
+// have references to the [next_iterator] and [previous_iterator], thus creating
+// a double linked list.
+//
+// When the hash table changes the iterators are called to update their [index]
+// and [count]. The hash table calls [EntryRemoved], [TableCompacted] as well
+// as [TableCleared].
+//
+// When an iterator is done it closes itself. It removes itself from the double
+// linked list and it sets its [table] to undefined, no longer keeping the
+// [table] alive.
+template<class Derived, class TableType>
+class OrderedHashTableIterator: public JSObject {
+ public:
+  // [table]: the backing hash table mapping keys to values.
+  DECL_ACCESSORS(table, Object)
+
+  // [index]: The index into the data table.
+  DECL_ACCESSORS(index, Smi)
+
+  // [count]: The logical index into the data table, ignoring the holes.
+  DECL_ACCESSORS(count, Smi)
+
+  // [kind]: The kind of iteration this is. One of the [Kind] enum values.
+  DECL_ACCESSORS(kind, Smi)
+
+  // [next_iterator]: Used as a double linked list for the live iterators.
+  DECL_ACCESSORS(next_iterator, Object)
+
+  // [previous_iterator]: Used as a double linked list for the live iterators.
+  DECL_ACCESSORS(previous_iterator, Object)
+
+  void OrderedHashTableIteratorPrint(FILE* out);
+
+  static const int kTableOffset = JSObject::kHeaderSize;
+  static const int kIndexOffset = kTableOffset + kPointerSize;
+  static const int kCountOffset = kIndexOffset + kPointerSize;
+  static const int kKindOffset = kCountOffset + kPointerSize;
+  static const int kNextIteratorOffset = kKindOffset + kPointerSize;
+  static const int kPreviousIteratorOffset = kNextIteratorOffset + kPointerSize;
+  static const int kSize = kPreviousIteratorOffset + kPointerSize;
+
+  enum Kind {
+    kKindKeys = 1,
+    kKindValues = 2,
+    kKindEntries = 3
+  };
+
+  // Called by the underlying [table] when an entry is removed.
+  void EntryRemoved(int index);
+
+  // Called by the underlying [table] when it is compacted/rehashed.
+  void TableCompacted() {
+    // All holes have been removed so index is now same as count.
+    set_index(count());
+  }
+
+  // Called by the underlying [table] when it is cleared.
+  void TableCleared() {
+    set_index(Smi::FromInt(0));
+    set_count(Smi::FromInt(0));
+  }
+
+  // Removes the iterator from the double linked list and removes its reference
+  // back to the [table].
+  void Close();
+
+  // Returns an iterator result object: {value: any, done: boolean} and moves
+  // the index to the next valid entry. Closes the iterator if moving past the
+  // end.
+  Handle<JSObject> Next();
+
+ private:
+  // Ensures [index] is not pointing to a hole.
+  void Seek();
+
+  // Moves [index] to next valid entry. Closes the iterator if moving past the
+  // end.
+  void MoveNext();
+
+  bool Closed() {
+    return table()->IsUndefined();
+  }
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
+};
+
+
+class JSSetIterator: public OrderedHashTableIterator<JSSetIterator,
+                                                     OrderedHashSet> {
+ public:
+  static Handle<JSSetIterator> Create(Isolate* isolate);
+
+  // Dispatched behavior.
+  DECLARE_PRINTER(JSSetIterator)
+  DECLARE_VERIFIER(JSSetIterator)
+
+  // Casting.
+  static inline JSSetIterator* cast(Object* obj);
+
+  Handle<Object> ValueForKind(int entry_index);
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
+};
+
+
+class JSMapIterator: public OrderedHashTableIterator<JSMapIterator,
+                                                     OrderedHashMap> {
+ public:
+  static Handle<JSMapIterator> Create(Isolate* isolate);
+
+  // Dispatched behavior.
+  DECLARE_PRINTER(JSMapIterator)
+  DECLARE_VERIFIER(JSMapIterator)
+
+  // Casting.
+  static inline JSMapIterator* cast(Object* obj);
+
+  Handle<Object> ValueForKind(int entry_index);
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
+};
+
+
 // Base class for both JSWeakMap and JSWeakSet
 class JSWeakCollection: public JSObject {
  public: