[runtime] Fancify KeyAccumulator

src/objects.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_OBJECTS_H_
 #define V8_OBJECTS_H_
 
 #include <iosfwd>
 
 #include "src/allocation.h"
@@ skipping 836 matching lines @@
 class AllocationSite;
 class AllocationSiteCreationContext;
 class AllocationSiteUsageContext;
 class Cell;
 class ConsString;
 class ElementsAccessor;
 class FixedArrayBase;
 class FunctionLiteral;
 class GlobalObject;
 class JSBuiltinsObject;
+class KeyAccumulator;
 class LayoutDescriptor;
 class LiteralsArray;
 class LookupIterator;
 class ObjectHashTable;
 class ObjectVisitor;
 class PropertyCell;
 class PropertyDescriptor;
 class SafepointEntry;
 class SharedFunctionInfo;
 class StringStream;
@@ skipping 215 matching lines @@
 
   inline ElementsKind OptimalElementsKind();
 
   inline bool FitsRepresentation(Representation representation);
 
   // Checks whether two valid primitive encodings of a property name resolve to
   // the same logical property. E.g., the smi 1, the string "1" and the double
   // 1 all refer to the same property, so this helper will return true.
   inline bool KeyEquals(Object* other);
 
+  inline bool FilterKey(PropertyAttributes filter);
+
   Handle<HeapType> OptimalType(Isolate* isolate, Representation representation);
 
   inline static Handle<Object> NewStorageFor(Isolate* isolate,
                                              Handle<Object> object,
                                              Representation representation);
 
   inline static Handle<Object> WrapForRead(Isolate* isolate,
                                            Handle<Object> object,
                                            Representation representation);
 
@@ skipping 682 matching lines @@
 // Indicator for one component of an AccessorPair.
 enum AccessorComponent {
   ACCESSOR_GETTER,
   ACCESSOR_SETTER
 };
 
 
 enum KeyFilter { SKIP_SYMBOLS, INCLUDE_SYMBOLS };
 
 
+enum GetKeysConversion { KEEP_NUMBERS, CONVERT_TO_STRING };
+
+
 enum ShouldThrow { THROW_ON_ERROR, DONT_THROW };
 
 
 // JSReceiver includes types on which properties can be defined, i.e.,
 // JSObject and JSProxy.
 class JSReceiver: public HeapObject {
  public:
   DECLARE_CAST(JSReceiver)
 
   // ES6 section 7.1.1 ToPrimitive
@@ skipping 92 matching lines @@
   // hash code if needed and none exists.
   inline static Handle<Smi> GetOrCreateIdentityHash(
       Handle<JSReceiver> object);
 
   enum KeyCollectionType { OWN_ONLY, INCLUDE_PROTOS };
 
   // Computes the enumerable keys for a JSObject. Used for implementing
   // "for (n in object) { }".
   MUST_USE_RESULT static MaybeHandle<FixedArray> GetKeys(
       Handle<JSReceiver> object, KeyCollectionType type,
-      KeyFilter filter = SKIP_SYMBOLS);
+      KeyFilter filter = SKIP_SYMBOLS,
+      GetKeysConversion getConversion = KEEP_NUMBERS);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSReceiver);
 };
 
 
 // The JSObject describes real heap allocated JavaScript objects with
 // properties.
 // Note that the map of JSObject changes during execution to enable inline
 // caching.
@@ skipping 309 matching lines @@
                           PropertyAttributes filter = NONE);
 
   // Returns the number of properties on this object filtering out properties
   // with the specified attributes (ignoring interceptors).
   int NumberOfOwnElements(PropertyAttributes filter);
   // Returns the number of enumerable elements (ignoring interceptors).
   int NumberOfEnumElements();
   // Returns the number of elements on this object filtering out elements
   // with the specified attributes (ignoring interceptors).
   int GetOwnElementKeys(FixedArray* storage, PropertyAttributes filter);
+  static void CollectOwnElementKeys(Handle<JSObject> object,
+                                    KeyAccumulator* keys,
+                                    PropertyAttributes filter);
   // Count and fill in the enumerable elements into storage.
   // (storage->length() == NumberOfEnumElements()).
   // If storage is NULL, will count the elements without adding
   // them to any storage.
   // Returns the number of enumerable elements.
   int GetEnumElementKeys(FixedArray* storage);
 
   static Handle<FixedArray> GetEnumPropertyKeys(Handle<JSObject> object,
                                                 bool cache_result);
 
@@ skipping 8459 matching lines @@
     if (v) {
       value |= (1 << bit_position);
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 
+enum AddKeyConversion { DO_NOT_CONVERT, CONVERT_TO_ARRAY_INDEX, PROXY_MAGIC };
+
+// This is a helper class for JSReceiver::GetKeys which collects and sorts keys.
+// GetKeys needs to sort keys per prototype level, first showing the integer
+// indices from elements then the strings from the properties. However, this
+// does not apply to proxies which are in full control of how the keys are
+// sorted.
+//
+// For performance reasons the KeyAccumulator internally separates integer
+// keys in |elements_| into sorted lists per prototype level. String keys are
+// collected in |properties_|, a single OrderedHashSet. To separate the keys per
+// level later when assembling the final list, |levelLengths_| keeps track of
+// the total number of keys (integers + strings) per level.
+//
+// Only unique keys are kept by the KeyAccumulator, strings are stored in a
+// HashSet for inexpensive lookups. Integer keys are kept in sorted lists which
+// are more compact and allow for reasonably fast includes check.
 class KeyAccumulator final BASE_EMBEDDED {
  public:
-  explicit KeyAccumulator(Isolate* isolate) : isolate_(isolate), length_(0) {}
+  explicit KeyAccumulator(Isolate* isolate,
+                          KeyFilter filter = KeyFilter::SKIP_SYMBOLS)
+      : isolate_(isolate), filter_(filter), length_(0), levelLength_(0) {}
+  ~KeyAccumulator();
 
-  void AddKey(Handle<Object> key, int check_limit);
-  void AddKeys(Handle<FixedArray> array, KeyFilter filter);
-  void AddKeys(Handle<JSObject> array, KeyFilter filter);
-  void PrepareForComparisons(int count);
-  Handle<FixedArray> GetKeys();
+  bool AddKey(uint32_t key);
+  bool AddKey(Object* key, AddKeyConversion convert = DO_NOT_CONVERT);
+  bool AddKey(Handle<Object> key, AddKeyConversion convert = DO_NOT_CONVERT);
+  void AddKeys(Handle<FixedArray> array,
+               AddKeyConversion convert = DO_NOT_CONVERT);
+  void AddKeys(Handle<JSObject> array,
+               AddKeyConversion convert = DO_NOT_CONVERT);
+  void AddKeysFromProxy(Handle<JSObject> array);
+  // Jump to the next level, pushing the current |levelLength_| to
+  // |levelLengths_| and adding a new list to |elements_|.
+  void NextPrototype();
+  // Sort the integer indices in the last list in |elements_|
+  void SortCurrentElementsList();
+  Handle<FixedArray> GetKeys(GetKeysConversion convert = KEEP_NUMBERS);
 
-  int GetLength() { return length_; }
 
  private:
-  void EnsureCapacity(int capacity);
-  void Grow();
+  Isolate* isolate_;
+  KeyFilter filter_;
+  // |elements_| contains the sorted element keys (indices) per level.
+  List<List<uint32_t>*> elements_;
+  // |protoLengths_| contains the total number of keys (elements + properties)
+  // per level. Negative values mark counts for a level with keys from a proxy.
+  List<int> levelLengths_;
+  // |properties_| contains the property keys per level in insertion order.
+  Handle<OrderedHashSet> properties_;
+  // |length_| keeps track of the total number of all element and property keys.
+  int length_;
+  // |levelLength_| keeps track of the total number of keys
+  // (elements + properties) in the current level.
+  int levelLength_;
 
-  Isolate* isolate_;
-  Handle<FixedArray> keys_;
-  Handle<OrderedHashSet> set_;
-  int length_;
   DISALLOW_COPY_AND_ASSIGN(KeyAccumulator);
 };
 
 }  // NOLINT, false-positive due to second-order macros.
 }  // NOLINT, false-positive due to second-order macros.
 
 #endif  // V8_OBJECTS_H_