ES6: Add support for Map/Set forEach

src/objects.h

 // Copyright 2012 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 48 matching lines @@
 //     - HeapObject   (superclass for everything allocated in the heap)
 //       - JSReceiver  (suitable for property access)
 //         - JSObject
 //           - JSArray
 //           - JSArrayBuffer
 //           - JSArrayBufferView
 //             - JSTypedArray
 //             - JSDataView
 //           - JSSet
 //           - JSMap
+//           - JSSetIterator
+//           - JSMapIterator
 //           - JSWeakCollection
 //             - JSWeakMap
 //             - JSWeakSet
 //           - JSRegExp
 //           - JSFunction
 //           - JSGeneratorObject
 //           - JSModule
 //           - GlobalObject
 //             - JSGlobalObject
 //             - JSBuiltinsObject
@@ skipping 359 matching lines @@
   V(JS_GLOBAL_OBJECT_TYPE)                                                     \
   V(JS_BUILTINS_OBJECT_TYPE)                                                   \
   V(JS_GLOBAL_PROXY_TYPE)                                                      \
   V(JS_ARRAY_TYPE)                                                             \
   V(JS_ARRAY_BUFFER_TYPE)                                                      \
   V(JS_TYPED_ARRAY_TYPE)                                                       \
   V(JS_DATA_VIEW_TYPE)                                                         \
   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)                                                            \
                                                                                \
   V(JS_FUNCTION_TYPE)                                                          \
   V(JS_FUNCTION_PROXY_TYPE)                                                    \
   V(DEBUG_INFO_TYPE)                                                           \
   V(BREAK_POINT_INFO_TYPE)
 
 
@@ skipping 328 matching lines @@
   JS_MODULE_TYPE,
   JS_GLOBAL_OBJECT_TYPE,
   JS_BUILTINS_OBJECT_TYPE,
   JS_GLOBAL_PROXY_TYPE,
   JS_ARRAY_TYPE,
   JS_ARRAY_BUFFER_TYPE,
   JS_TYPED_ARRAY_TYPE,
   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,
 
   JS_REGEXP_TYPE,
 
   JS_FUNCTION_TYPE,  // LAST_JS_OBJECT_TYPE, LAST_JS_RECEIVER_TYPE
 
   // Pseudo-types
   FIRST_TYPE = 0x0,
   LAST_TYPE = JS_FUNCTION_TYPE,
@@ skipping 227 matching lines @@
   V(Boolean)                                   \
   V(JSArray)                                   \
   V(JSArrayBuffer)                             \
   V(JSArrayBufferView)                         \
   V(JSTypedArray)                              \
   V(JSDataView)                                \
   V(JSProxy)                                   \
   V(JSFunctionProxy)                           \
   V(JSSet)                                     \
   V(JSMap)                                     \
+  V(JSSetIterator)                             \
+  V(JSMapIterator)                             \
   V(JSWeakCollection)                          \
   V(JSWeakMap)                                 \
   V(JSWeakSet)                                 \
   V(JSRegExp)                                  \
   V(HashTable)                                 \
   V(Dictionary)                                \
   V(StringTable)                               \
   V(JSFunctionResultCache)                     \
   V(NormalizedMapCache)                        \
   V(CompilationCacheTable)                     \
@@ skipping 3255 matching lines @@
 // equality operator and Object::GetHash() for the hash function.
 //
 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
 // Originally attributed to Tyler Close.
 //
 // Memory layout:
 //   [0]: bucket count
 //   [1]: element count
 //   [2]: deleted element count
-//   [3..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset
+//   [3]: live iterators (doubly-linked list)
+//   [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|.
   static Handle<Derived> Allocate(
       Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED);
 
   // Returns an OrderedHashTable (possibly |table|) with enough space
   // to add at least one new element.
   static Handle<Derived> EnsureGrowable(Handle<Derived> table);
 
   // Returns an OrderedHashTable (possibly |table|) that's shrunken
   // 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);
 
   int NumberOfElements() {
     return Smi::cast(get(kNumberOfElementsIndex))->value();
   }
 
   int NumberOfDeletedElements() {
     return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
   }
 
+  int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
+
   int NumberOfBuckets() {
     return Smi::cast(get(kNumberOfBucketsIndex))->value();
   }
 
+  Object* iterators() { return get(kIteratorsIndex); }
+
+  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.
   int AddEntry(int hash);
 
   // Removes the entry, and puts the_hole in entrysize pointers
   // (leaving the hash table chain intact).
   void RemoveEntry(int entry);
 
   // Returns an index into |this| for the given entry.
   int EntryToIndex(int entry) {
     return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
   }
 
+  Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
+
   static const int kNotFound = -1;
+  static const int kMinCapacity = 4;
 
  private:
   static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
 
   void SetNumberOfBuckets(int num) {
     set(kNumberOfBucketsIndex, Smi::FromInt(num));
   }
 
   void SetNumberOfElements(int num) {
     set(kNumberOfElementsIndex, Smi::FromInt(num));
   }
 
   void SetNumberOfDeletedElements(int num) {
     set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
   }
 
   int Capacity() {
     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();
   }
 
   int HashToBucket(int hash) {
     return hash & (NumberOfBuckets() - 1);
   }
 
   int HashToEntry(int hash) {
     int bucket = HashToBucket(hash);
     return Smi::cast(get(kHashTableStartIndex + bucket))->value();
   }
 
   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;
 
   static const int kLoadFactor = 2;
   static const int kMaxCapacity =
       (FixedArray::kMaxLength - kHashTableStartIndex)
       / (1 + (kEntrySize * kLoadFactor));
 };
 
 
-class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> {
+class JSSetIterator;
+
+
+class OrderedHashSet: public OrderedHashTable<
+    OrderedHashSet, JSSetIterator, 1> {
  public:
   static OrderedHashSet* cast(Object* obj) {
     ASSERT(obj->IsOrderedHashTable());
     return reinterpret_cast<OrderedHashSet*>(obj);
   }
 
   bool Contains(Object* key);
   static Handle<OrderedHashSet> Add(
       Handle<OrderedHashSet> table, Handle<Object> key);
   static Handle<OrderedHashSet> Remove(
       Handle<OrderedHashSet> table, Handle<Object> key);
 };
 
 
-class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> {
+class JSMapIterator;
+
+
+class OrderedHashMap:public OrderedHashTable<
+    OrderedHashMap, JSMapIterator, 2> {
  public:
   static OrderedHashMap* cast(Object* obj) {
     ASSERT(obj->IsOrderedHashTable());
     return reinterpret_cast<OrderedHashMap*>(obj);
   }
 
   Object* Lookup(Object* key);
   static Handle<OrderedHashMap> Put(
       Handle<OrderedHashMap> table,
       Handle<Object> key,
@@ skipping 3134 matching lines @@
   static const int kContinuationOffset = kReceiverOffset + kPointerSize;
   static const int kOperandStackOffset = kContinuationOffset + kPointerSize;
   static const int kStackHandlerIndexOffset =
       kOperandStackOffset + kPointerSize;
   static const int kSize = kStackHandlerIndexOffset + kPointerSize;
 
   // Resume mode, for use by runtime functions.
   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;
 
   static const int kResultValuePropertyOffset = JSObject::kHeaderSize;
   static const int kResultDonePropertyOffset =
       kResultValuePropertyOffset + kPointerSize;
   static const int kResultSize = kResultDonePropertyOffset + kPointerSize;
 
  private:
@@ skipping 2461 matching lines @@
   DECLARE_VERIFIER(JSMap)
 
   static const int kTableOffset = JSObject::kHeaderSize;
   static const int kSize = kTableOffset + kPointerSize;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap);
 };
 
 
+// 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)
+
+#ifdef OBJECT_PRINT
+  void OrderedHashTableIteratorPrint(FILE* out);
+#endif
+
+  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.
+  static Handle<JSObject> Next(Handle<Derived> iterator);
+
+ protected:
+  static Handle<Derived> CreateInternal(
+      Handle<Map> map, Handle<TableType> table, int kind);
+
+ 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:
+  // Creates a new iterator associated with [table].
+  // [kind] needs to be one of the OrderedHashTableIterator Kind enum values.
+  static inline Handle<JSSetIterator> Create(
+      Handle<OrderedHashSet> table, int kind);
+
+  // Dispatched behavior.
+  DECLARE_PRINTER(JSSetIterator)
+  DECLARE_VERIFIER(JSSetIterator)
+
+  // Casting.
+  static inline JSSetIterator* cast(Object* obj);
+
+  static Handle<Object> ValueForKind(
+      Handle<JSSetIterator> iterator, int entry_index);
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
+};
+
+
+class JSMapIterator: public OrderedHashTableIterator<JSMapIterator,
+                                                     OrderedHashMap> {
+ public:
+  // Creates a new iterator associated with [table].
+  // [kind] needs to be one of the OrderedHashTableIterator Kind enum values.
+  static inline Handle<JSMapIterator> Create(
+      Handle<OrderedHashMap> table, int kind);
+
+  // Dispatched behavior.
+  DECLARE_PRINTER(JSMapIterator)
+  DECLARE_VERIFIER(JSMapIterator)
+
+  // Casting.
+  static inline JSMapIterator* cast(Object* obj);
+
+  static Handle<Object> ValueForKind(
+      Handle<JSMapIterator> iterator, int entry_index);
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
+};
+
+
 // Base class for both JSWeakMap and JSWeakSet
 class JSWeakCollection: public JSObject {
  public:
   // [table]: the backing hash table mapping keys to values.
   DECL_ACCESSORS(table, Object)
 
   // [next]: linked list of encountered weak maps during GC.
   DECL_ACCESSORS(next, Object)
 
   static const int kTableOffset = JSObject::kHeaderSize;
@@ skipping 1010 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_