Separating transitions from descriptors.

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 762 matching lines @@
   V(ExternalDoubleArray)                       \
   V(ExternalPixelArray)                        \
   V(ByteArray)                                 \
   V(FreeSpace)                                 \
   V(JSReceiver)                                \
   V(JSObject)                                  \
   V(JSContextExtensionObject)                  \
   V(JSModule)                                  \
   V(Map)                                       \
   V(DescriptorArray)                           \
+  V(TransitionArray)                           \
   V(DeoptimizationInputData)                   \
   V(DeoptimizationOutputData)                  \
   V(TypeFeedbackCells)                         \
   V(FixedArray)                                \
   V(FixedDoubleArray)                          \
   V(Context)                                   \
   V(GlobalContext)                             \
   V(ModuleContext)                             \
   V(ScopeInfo)                                 \
   V(JSFunction)                                \
@@ skipping 1098 matching lines @@
   // (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);
 
   // Add a property to a fast-case object using a map transition to
   // new_map.
   MUST_USE_RESULT MaybeObject* AddFastPropertyUsingMap(Map* new_map,
                                                        String* name,
-                                                       Object* value);
+                                                       Object* value,
+                                                       int field_index);
 
   // Add a constant function property to a fast-case object.
   // This leaves a CONSTANT_TRANSITION in the old map, and
   // if it is called on a second object with this map, a
   // normal property is added instead, with a map transition.
   // This avoids the creation of many maps with the same constant
   // function, all orphaned.
   MUST_USE_RESULT MaybeObject* AddConstantFunctionProperty(
       String* name,
       JSFunction* function,
@@ skipping 137 matching lines @@
 #ifdef OBJECT_PRINT
   inline void PrintProperties() {
     PrintProperties(stdout);
   }
   void PrintProperties(FILE* out);
 
   inline void PrintElements() {
     PrintElements(stdout);
   }
   void PrintElements(FILE* out);
+  inline void PrintTransitions() {
+    PrintTransitions(stdout);
+  }
+  void PrintTransitions(FILE* out);
 #endif
 
   void PrintElementsTransition(
       FILE* file, ElementsKind from_kind, FixedArrayBase* from_elements,
       ElementsKind to_kind, FixedArrayBase* to_elements);
 
 #ifdef DEBUG
   // Structure for collecting spill information about JSObjects.
   class SpillInformation {
    public:
@@ skipping 133 matching lines @@
       uint32_t index,
       Object* getter,
       Object* setter,
       PropertyAttributes attributes);
   MUST_USE_RESULT MaybeObject* CreateAccessorPairFor(String* name);
   MUST_USE_RESULT MaybeObject* DefinePropertyAccessor(
       String* name,
       Object* getter,
       Object* setter,
       PropertyAttributes attributes);
-  void LookupInDescriptor(String* name, LookupResult* result);
 
   // Returns the hidden properties backing store object, currently
   // a StringDictionary, stored on this object.
   // If no hidden properties object has been put on this object,
   // return undefined, unless create_if_absent is true, in which case
   // a new dictionary is created, added to this object, and returned.
   MUST_USE_RESULT MaybeObject* GetHiddenPropertiesDictionary(
       bool create_if_absent);
   // Updates the existing hidden properties dictionary.
   MUST_USE_RESULT MaybeObject* SetHiddenPropertiesDictionary(
@@ skipping 14 matching lines @@
   inline static FixedArrayBase* cast(Object* object);
 
   // Layout description.
   // Length is smi tagged when it is stored.
   static const int kLengthOffset = HeapObject::kHeaderSize;
   static const int kHeaderSize = kLengthOffset + kPointerSize;
 };
 
 
 class FixedDoubleArray;
+class IncrementalMarking;
+
 
 // FixedArray describes fixed-sized arrays with element type Object*.
 class FixedArray: public FixedArrayBase {
  public:
   // Setter and getter for elements.
   inline Object* get(int index);
   // Setter that uses write barrier.
   inline void set(int index, Object* value);
   inline bool is_the_hole(int index);
 
@@ skipping 75 matching lines @@
   // object, the prefix of this array is sorted.
   void SortPairs(FixedArray* numbers, uint32_t len);
 
   class BodyDescriptor : public FlexibleBodyDescriptor<kHeaderSize> {
    public:
     static inline int SizeOf(Map* map, HeapObject* object) {
       return SizeFor(reinterpret_cast<FixedArray*>(object)->length());
     }
   };
 
+  // WhitenessWitness is used to prove that a descriptor array is white
+  // (unmarked), so incremental write barriers can be skipped because the
+  // marking invariant cannot be broken and slots pointing into evacuation
+  // candidates will be discovered when the object is scanned. A witness is
+  // always stack-allocated right after creating an array. By allocating a
+  // witness, incremental marking is globally disabled. The witness is then
+  // passed along wherever needed to statically prove that the array is known to
+  // be white.
+  class WhitenessWitness {
+   public:
+    inline explicit WhitenessWitness(FixedArray* array);
+    inline ~WhitenessWitness();
+
+   private:
+    IncrementalMarking* marking_;
+  };
+
  protected:
   // Set operation on FixedArray without using write barriers. Can
   // only be used for storing old space objects or smis.
   static inline void NoWriteBarrierSet(FixedArray* array,
                                        int index,
                                        Object* value);
 
   // Set operation on FixedArray without incremental write barrier. Can
   // only be used if the object is guaranteed to be white (whiteness witness
   // is present).
@@ skipping 54 matching lines @@
 
 #ifdef DEBUG
   void FixedDoubleArrayVerify();
 #endif
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(FixedDoubleArray);
 };
 
 
-class IncrementalMarking;
-
-
 // DescriptorArrays are fixed arrays used to hold instance descriptors.
 // The format of the these objects is:
 // TODO(1399): It should be possible to make room for bit_field3 in the map
 //             without overloading the instance descriptors field in the map
 //             (and storing it in the DescriptorArray when the map has one).
 //   [0]: storage for bit_field3 for Map owning this object (Smi)
 //   [1]: point to a fixed array with (value, detail) pairs.
 //   [2]: next enumeration index (Smi), or pointer to small fixed array:
 //          [0]: next enumeration index (Smi)
 //          [1]: pointer to fixed array with enum cache
 //   [3]: first key
 //   [length() - 1]: last key
 //
 class DescriptorArray: public FixedArray {
  public:
   // Returns true for both shared empty_descriptor_array and for smis, which the
   // map uses to encode additional bit fields when the descriptor array is not
   // yet used.
   inline bool IsEmpty();
   inline bool MayContainTransitions();
+  inline bool HasTransitionArray();
 
-  DECL_ACCESSORS(elements_transition_map, Map)
-  inline void ClearElementsTransition();
+  DECL_ACCESSORS(transitions, TransitionArray)
+  inline void ClearTransitions();
 
   // Returns the number of descriptors in the array.
   int number_of_descriptors() {
-    ASSERT(length() >= kFirstIndex || IsEmpty());
+    ASSERT(MayContainTransitions() || IsEmpty());
     int len = length();
     return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kDescriptorSize;
   }
 
+  inline int number_of_entries() { return number_of_descriptors(); }
+
   int NextEnumerationIndex() {
     if (IsEmpty()) return PropertyDetails::kInitialIndex;
     Object* obj = get(kEnumerationIndexIndex);
     if (obj->IsSmi()) {
       return Smi::cast(obj)->value();
     } else {
       Object* index = FixedArray::cast(obj)->get(kEnumCacheBridgeEnumIndex);
       return Smi::cast(index)->value();
     }
   }
@@ skipping 14 matching lines @@
     return bridge->get(kEnumCacheBridgeCacheIndex);
   }
 
   Object** GetEnumCacheSlot() {
     ASSERT(HasEnumCache());
     return HeapObject::RawField(reinterpret_cast<HeapObject*>(this),
                                 kEnumerationIndexOffset);
   }
 
   Object** GetTransitionsSlot() {
-    ASSERT(elements_transition_map() != NULL);
     return HeapObject::RawField(reinterpret_cast<HeapObject*>(this),
                                 kTransitionsOffset);
   }
 
   // TODO(1399): It should be possible to make room for bit_field3 in the map
   //             without overloading the instance descriptors field in the map
   //             (and storing it in the DescriptorArray when the map has one).
   inline int bit_field3_storage();
   inline void set_bit_field3_storage(int value);
 
   // Initialize or change the enum cache,
   // using the supplied storage for the small "bridge".
   void SetEnumCache(FixedArray* bridge_storage,
                     FixedArray* new_cache,
                     Object* new_index_cache);
 
   // Accessors for fetching instance descriptor at descriptor number.
   inline String* GetKey(int descriptor_number);
   inline Object** GetKeySlot(int descriptor_number);
-  inline void SetKeyUnchecked(Heap* heap, int descriptor_number, String* value);
   inline Object* GetValue(int descriptor_number);
   inline Object** GetValueSlot(int descriptor_number);
-  inline void SetNullValueUnchecked(Heap* heap, int descriptor_number);
-  inline void SetValueUnchecked(Heap* heap,
-                                int descriptor_number,
-                                Object* value);
   inline PropertyDetails GetDetails(int descriptor_number);
-  inline void SetDetailsUnchecked(int descriptor_number, Smi* value);
   inline PropertyType GetType(int descriptor_number);
   inline int GetFieldIndex(int descriptor_number);
   inline JSFunction* GetConstantFunction(int descriptor_number);
   inline Object* GetCallbacksObject(int descriptor_number);
   inline AccessorDescriptor* GetCallbacks(int descriptor_number);
-  inline bool IsProperty(int descriptor_number);
-  inline bool IsTransitionOnly(int descriptor_number);
-
-  // WhitenessWitness is used to prove that a specific descriptor array is white
-  // (unmarked), so incremental write barriers can be skipped because the
-  // marking invariant cannot be broken and slots pointing into evacuation
-  // candidates will be discovered when the object is scanned. A witness is
-  // always stack-allocated right after creating a descriptor array. By
-  // allocating a witness, incremental marking is globally disabled. The witness
-  // is then passed along wherever needed to statically prove that the
-  // descriptor array is known to be white.
-  class WhitenessWitness {
-   public:
-    inline explicit WhitenessWitness(DescriptorArray* array);
-    inline ~WhitenessWitness();
-
-   private:
-    IncrementalMarking* marking_;
-  };
 
   // Accessor for complete descriptor.
   inline void Get(int descriptor_number, Descriptor* desc);
   inline void Set(int descriptor_number,
                   Descriptor* desc,
                   const WhitenessWitness&);
 
   // Transfer a complete descriptor from the src descriptor array to the dst
   // one, dropping map transitions in CALLBACKS.
   static void CopyFrom(Handle<DescriptorArray> dst,
                        int dst_index,
                        Handle<DescriptorArray> src,
                        int src_index,
                        const WhitenessWitness& witness);
 
   // Transfer a complete descriptor from the src descriptor array to this
   // descriptor array, dropping map transitions in CALLBACKS.
   MUST_USE_RESULT MaybeObject* CopyFrom(int dst_index,
                                         DescriptorArray* src,
                                         int src_index,
                                         const WhitenessWitness&);
 
   // Copy the descriptor array, insert a new descriptor and optionally
   // remove map transitions.  If the descriptor is already present, it is
   // replaced.  If a replaced descriptor is a real property (not a transition
   // or null), its enumeration index is kept as is.
   // If adding a real property, map transitions must be removed.  If adding
   // a transition, they must not be removed.  All null descriptors are removed.
-  MUST_USE_RESULT MaybeObject* CopyInsert(Descriptor* descriptor,
-                                          TransitionFlag transition_flag);
+  MUST_USE_RESULT MaybeObject* CopyInsert(Descriptor* descriptor);
 
   // Indicates whether the search function should expect a sorted or an unsorted
   // descriptor array as input.
   enum SharedMode {
     MAY_BE_SHARED,
     CANNOT_BE_SHARED
   };
 
   // Return a copy of the array with all transitions and null descriptors
   // removed. Return a Failure object in case of an allocation failure.
-  MUST_USE_RESULT MaybeObject* RemoveTransitions(SharedMode shared_mode);
+  MUST_USE_RESULT MaybeObject* Copy(SharedMode shared_mode);
 
   // Sort the instance descriptors by the hash codes of their keys.
   // Does not check for duplicates.
   void SortUnchecked(const WhitenessWitness&);
 
   // Sort the instance descriptors by the hash codes of their keys.
   // Checks the result for duplicates.
   void Sort(const WhitenessWitness&);
 
   // Search the instance descriptors for given name.
   INLINE(int Search(String* name));
 
   // As the above, but uses DescriptorLookupCache and updates it when
   // necessary.
   INLINE(int SearchWithCache(String* name));
 
   // Tells whether the name is present int the array.
   bool Contains(String* name) { return kNotFound != Search(name); }
 
-  // Perform a binary search in the instance descriptors represented
-  // by this fixed array.  low and high are descriptor indices.  If there
-  // are three instance descriptors in this array it should be called
-  // with low=0 and high=2.
-  int BinarySearch(String* name, int low, int high);
-
-  // Perform a linear search in the instance descriptors represented
-  // by this fixed array.  len is the number of descriptor indices that are
-  // valid.
-  int LinearSearch(SearchMode mode, String* name, int len);
-
   // Allocates a DescriptorArray, but returns the singleton
   // empty descriptor array object if number_of_descriptors is 0.
   MUST_USE_RESULT static MaybeObject* Allocate(int number_of_descriptors,
                                                SharedMode shared_mode);
 
   // Casting.
   static inline DescriptorArray* cast(Object* obj);
 
   // Constant for denoting key was not found.
   static const int kNotFound = -1;
 
   static const int kBitField3StorageIndex = 0;
   static const int kEnumerationIndexIndex = 1;
   static const int kTransitionsIndex = 2;
   static const int kFirstIndex = 3;
 
   // The length of the "bridge" to the enum cache.
   static const int kEnumCacheBridgeLength = 3;
   static const int kEnumCacheBridgeEnumIndex = 0;
   static const int kEnumCacheBridgeCacheIndex = 1;
   static const int kEnumCacheBridgeIndicesCacheIndex = 2;
 
   // Layout description.
   static const int kBitField3StorageOffset = FixedArray::kHeaderSize;
-  static const int kEnumerationIndexOffset =
-      kBitField3StorageOffset + kPointerSize;
+  static const int kEnumerationIndexOffset = kBitField3StorageOffset +
+                                             kPointerSize;
   static const int kTransitionsOffset = kEnumerationIndexOffset + kPointerSize;
   static const int kFirstOffset = kTransitionsOffset + kPointerSize;
 
   // Layout description for the bridge array.
   static const int kEnumCacheBridgeEnumOffset = FixedArray::kHeaderSize;
   static const int kEnumCacheBridgeCacheOffset =
     kEnumCacheBridgeEnumOffset + kPointerSize;
 
   // Layout of descriptor.
   static const int kDescriptorKey = 0;
@@ skipping 55 matching lines @@
   static int ToValueIndex(int descriptor_number) {
     return kFirstIndex +
            (descriptor_number * kDescriptorSize) +
            kDescriptorValue;
   }
 
   // Swap operation on FixedArray without using write barriers.
   static inline void NoIncrementalWriteBarrierSwap(
       FixedArray* array, int first, int second);
 
-  // Swap descriptor first and second.
+  // Swap first and second descriptor.
   inline void NoIncrementalWriteBarrierSwapDescriptors(
       int first, int second);
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(DescriptorArray);
 };
 
 
+template<typename T>
+inline int LinearSearch(T* array, SearchMode mode, String* name, int len);
+
+
+template<typename T>
+inline int Search(T* array, String* name);
+
+
 // HashTable is a subclass of FixedArray that implements a hash table
 // that uses open addressing and quadratic probing.
 //
 // In order for the quadratic probing to work, elements that have not
 // yet been used and elements that have been deleted are
 // distinguished.  Probing continues when deleted elements are
 // encountered and stops when unused elements are encountered.
 //
 // - Elements with key == undefined have not been used yet.
 // - Elements with key == the_hole have been deleted.
@@ skipping 444 matching lines @@
   void CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array);
 
   // For transforming properties of a JSObject.
   MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor(
       JSObject* obj,
       int unused_property_fields);
 
   // Find entry for key, otherwise return kNotFound. Optimized version of
   // HashTable::FindEntry.
   int FindEntry(String* key);
-
-  bool ContainsTransition(int entry);
 };
 
 
 class NumberDictionaryShape : public BaseShape<uint32_t> {
  public:
   static inline bool IsMatch(uint32_t key, Object* other);
   MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key);
   static const int kEntrySize = 3;
   static const bool kIsEnumerable = false;
 };
@@ skipping 1428 matching lines @@
   // Bit field 2.
   inline byte bit_field2();
   inline void set_bit_field2(byte value);
 
   // Bit field 3.
   // TODO(1399): It should be possible to make room for bit_field3 in the map
   // without overloading the instance descriptors field (and storing it in the
   // DescriptorArray when the map has one).
   inline int bit_field3();
   inline void set_bit_field3(int value);
+  inline void SetOwnBitField3(int value);
 
   // Tells whether the object in the prototype property will be used
   // for instances created from this function.  If the prototype
   // property is set to a value that is not a JSObject, the prototype
   // property will not be used to create instances of the function.
   // See ECMA-262, 13.2.2.
   inline void set_non_instance_prototype(bool value);
   inline bool has_non_instance_prototype();
 
   // Tells whether function has special prototype property. If not, prototype
@@ skipping 100 matching lines @@
   }
 
   inline bool has_slow_elements_kind() {
     return elements_kind() == DICTIONARY_ELEMENTS
         || elements_kind() == NON_STRICT_ARGUMENTS_ELEMENTS;
   }
 
   static bool IsValidElementsTransition(ElementsKind from_kind,
                                         ElementsKind to_kind);
 
+  inline bool HasTransitionArray();
+  inline bool HasElementsTransition();
   inline Map* elements_transition_map();
-  inline void set_elements_transition_map(Map* transitioned_map);
+  MUST_USE_RESULT inline MaybeObject* set_elements_transition_map(
+      Map* transitioned_map);
+  inline TransitionArray* transitions();
+  MUST_USE_RESULT inline MaybeObject* AddTransition(String* key,
+                                                    Object* value);
+  MUST_USE_RESULT inline MaybeObject* set_transitions(
+      TransitionArray* transitions);
+  inline void ClearTransitions();
 
   // Tells whether the map is attached to SharedFunctionInfo
   // (for inobject slack tracking).
   inline void set_attached_to_shared_function_info(bool value);
 
   inline bool attached_to_shared_function_info();
 
   // Tells whether the map is shared between objects that may have different
   // behavior. If true, the map should never be modified, instead a clone
   // should be created and modified.
@@ skipping 69 matching lines @@
   inline void SetNumberOfProtoTransitions(int value) {
     FixedArray* cache = prototype_transitions();
     ASSERT(cache->length() != 0);
     cache->set_unchecked(kProtoTransitionNumberOfEntriesOffset,
                          Smi::FromInt(value));
   }
 
   // Lookup in the map's instance descriptors and fill out the result
   // with the given holder if the name is found. The holder may be
   // NULL when this function is used from the compiler.
-  void LookupInDescriptors(JSObject* holder,
-                           String* name,
-                           LookupResult* result);
+  void LookupDescriptor(JSObject* holder,
+                        String* name,
+                        LookupResult* result);
+
+  void LookupTransition(JSObject* holder,
+                        String* name,
+                        LookupResult* result);
+
+  void LookupTransitionOrDescriptor(JSObject* holder,
+                                    String* name,
+                                    LookupResult* result);
 
   MUST_USE_RESULT MaybeObject* CopyDropDescriptors();
 
   MUST_USE_RESULT MaybeObject* CopyNormalized(PropertyNormalizationMode mode,
                                               NormalizedMapSharingMode sharing);
 
   // Returns a copy of the map, with all transitions dropped from the
   // instance descriptors.
   MUST_USE_RESULT MaybeObject* CopyDropTransitions(
       DescriptorArray::SharedMode shared_mode);
@@ skipping 63 matching lines @@
   // elements_kind that's found in |candidates|, or null handle if no match is
   // found at all.
   Handle<Map> FindTransitionedMap(MapHandleList* candidates);
   Map* FindTransitionedMap(MapList* candidates);
 
   // Zaps the contents of backing data structures in debug mode. Note that the
   // heap verifier (i.e. VerifyMarkingVisitor) relies on zapping of objects
   // holding weak references when incremental marking is used, because it also
   // iterates over objects that are otherwise unreachable.
 #ifdef DEBUG
-  void ZapInstanceDescriptors();
   void ZapPrototypeTransitions();
+  void ZapTransitions();
 #endif
 
   // Dispatched behavior.
 #ifdef OBJECT_PRINT
   inline void MapPrint() {
     MapPrint(stdout);
   }
   void MapPrint(FILE* out);
 #endif
 #ifdef DEBUG
@@ skipping 3871 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_