Revert of Simplify and compact transitions storage

src/transitions.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_TRANSITIONS_H_
 #define V8_TRANSITIONS_H_
 
 #include "src/checks.h"
 #include "src/elements-kind.h"
 #include "src/heap/heap.h"
 #include "src/isolate.h"
 #include "src/objects.h"
 
 namespace v8 {
 namespace internal {
 
 
 // TransitionArrays are fixed arrays used to hold map transitions for property,
-// constant, and element changes. "Simple" transitions storing only a single
-// property transition are stored inline (i.e. the target map is stored
-// directly); otherwise a full transition array is used that has
+// constant, and element changes. They can either be simple transition arrays
+// that store a single property transition, or a full transition array that has
 // prototype transitions and multiple property transitons. The details related
 // to property transitions are accessed in the descriptor array of the target
 // map. In the case of a simple transition, the key is also read from the
 // descriptor array of the target map.
 //
-// This class provides a static interface that operates directly on maps
-// and handles the distinction between simple and full transitions storage.
+// The simple format of the these objects is:
+// [0] Undefined or back pointer map
+// [1] Single transition
 //
 // The full format is:
-// [0] Smi(0) or fixed array of prototype transitions
-// [1] Number of transitions
-// [2] First transition
-// [2 + number of transitions * kTransitionSize]: start of slack
+// [0] Undefined or back pointer map
+// [1] Smi(0) or fixed array of prototype transitions
+// [2] Number of transitions
+// [3] First transition
+// [3 + number of transitions * kTransitionSize]: start of slack
 class TransitionArray: public FixedArray {
  public:
-  // Insert a new transition into |map|'s transition array, extending it
-  // as necessary.
-  static void Insert(Handle<Map> map, Handle<Name> name, Handle<Map> target,
-                     SimpleTransitionFlag flag);
+  // Accessors for fetching instance transition at transition number.
+  inline Name* GetKey(int transition_number);
+  inline void SetKey(int transition_number, Name* value);
+  inline Object** GetKeySlot(int transition_number);
+  int GetSortedKeyIndex(int transition_number) { return transition_number; }
 
-  static Map* SearchTransition(Map* map, PropertyKind kind, Name* name,
-                               PropertyAttributes attributes);
-
-  static Map* SearchSpecial(Map* map, Symbol* name);
-
-  static Handle<Map> FindTransitionToField(Handle<Map> map, Handle<Name> name);
-
-  static Handle<String> ExpectedTransitionKey(Handle<Map> map);
-
-  static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
-    DCHECK(!ExpectedTransitionKey(map).is_null());
-    return Handle<Map>(GetSimpleTransition(map->raw_transitions()));
-  }
-  // Returns true if |raw_transition| can be overwritten with a simple
-  // transition (because it's either uninitialized, or has been cleared).
-  static inline bool CanStoreSimpleTransition(Object* raw_transition) {
-    return raw_transition->IsSmi() ||
-           (raw_transition->IsWeakCell() &&
-            WeakCell::cast(raw_transition)->cleared());
-  }
-  static inline bool IsSimpleTransition(Object* raw_transition) {
-    DCHECK(!raw_transition->IsWeakCell() ||
-           WeakCell::cast(raw_transition)->cleared() ||
-           WeakCell::cast(raw_transition)->value()->IsMap());
-    return raw_transition->IsWeakCell() &&
-           !WeakCell::cast(raw_transition)->cleared();
-  }
-  static inline Map* GetSimpleTransition(Object* raw_transition) {
-    DCHECK(IsSimpleTransition(raw_transition));
-    return Map::cast(WeakCell::cast(raw_transition)->value());
-  }
-  static inline bool IsFullTransitionArray(Object* raw_transitions) {
-    return raw_transitions->IsTransitionArray();
+  Name* GetSortedKey(int transition_number) {
+    return GetKey(transition_number);
   }
 
-  // The size of transition arrays are limited so they do not end up in large
-  // object space. Otherwise ClearNonLiveReferences would leak memory while
-  // applying in-place right trimming.
-  static bool CanHaveMoreTransitions(Handle<Map> map);
+  inline Map* GetTarget(int transition_number);
+  inline void SetTarget(int transition_number, Map* target);
 
-  // ===== PROTOTYPE TRANSITIONS =====
-  // When you set the prototype of an object using the __proto__ accessor you
-  // need a new map for the object (the prototype is stored in the map).  In
-  // order not to multiply maps unnecessarily we store these as transitions in
-  // the original map.  That way we can transition to the same map if the same
-  // prototype is set, rather than creating a new map every time.  The
-  // transitions are in the form of a map where the keys are prototype objects
-  // and the values are the maps they transition to.
-  // Cache format:
-  //    0: finger - index of the first free cell in the cache
-  //    1 + i: target map
-  static const int kMaxCachedPrototypeTransitions = 256;
-  static Handle<Map> PutPrototypeTransition(Handle<Map> map,
-                                            Handle<Object> prototype,
-                                            Handle<Map> target_map);
+  inline PropertyDetails GetTargetDetails(int transition_number);
+  inline Object* GetTargetValue(int transition_number);
 
-  static Handle<Map> GetPrototypeTransition(Handle<Map> map,
-                                            Handle<Object> prototype);
+  inline bool HasElementsTransition();
 
-  static FixedArray* GetPrototypeTransitions(Map* map);
-
-  static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
-    if (proto_transitions->length() == 0) return 0;
-    Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
-    return Smi::cast(raw)->value();
-  }
-
-  static void SetNumberOfPrototypeTransitions(FixedArray* proto_transitions,
-                                              int value);
+  inline Object* back_pointer_storage();
+  inline void set_back_pointer_storage(
+      Object* back_pointer,
+      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
 
   inline FixedArray* GetPrototypeTransitions();
   inline void SetPrototypeTransitions(
       FixedArray* prototype_transitions,
       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
   inline Object** GetPrototypeTransitionsSlot();
   inline bool HasPrototypeTransitions();
 
-  // ===== ITERATION =====
-
-  typedef void (*TraverseCallback)(Map* map, void* data);
-
-  // Traverse the transition tree in postorder.
-  static void TraverseTransitionTree(Map* map, TraverseCallback callback,
-                                     void* data) {
-    // Make sure that we do not allocate in the callback.
-    DisallowHeapAllocation no_allocation;
-    TraverseTransitionTreeInternal(map, callback, data);
+  // Returns the number of transitions in the array.
+  int number_of_transitions() {
+    if (IsSimpleTransition()) return 1;
+    if (length() <= kFirstIndex) return 0;
+    return Smi::cast(get(kTransitionLengthIndex))->value();
   }
 
-  // ===== LOW-LEVEL ACCESSORS =====
-
-  // Accessors for fetching instance transition at transition number.
-  static inline Name* GetKey(Object* raw_transitions, int transition_number);
-  inline Name* GetKey(int transition_number);
-  inline void SetKey(int transition_number, Name* value);
-  inline Object** GetKeySlot(int transition_number);
-  int GetSortedKeyIndex(int transition_number) { return transition_number; }
-
-  Name* GetSortedKey(int transition_number) {
-    return GetKey(transition_number);
+  int number_of_transitions_storage() {
+    if (IsSimpleTransition()) return 1;
+    if (length() <= kFirstIndex) return 0;
+    return (length() - kFirstIndex) / kTransitionSize;
   }
 
-  static inline Map* GetTarget(Object* raw_transitions, int transition_number);
-  inline Map* GetTarget(int transition_number);
-  inline void SetTarget(int transition_number, Map* target);
+  int NumberOfSlackTransitions() {
+    return number_of_transitions_storage() - number_of_transitions();
+  }
+
+  inline void SetNumberOfTransitions(int number_of_transitions);
+  inline int number_of_entries() { return number_of_transitions(); }
+
+  // Creates a FullTransitionArray from a SimpleTransitionArray in
+  // containing_map.
+  static Handle<TransitionArray> ExtendToFullTransitionArray(
+      Handle<Map> containing_map);
+
+  // Return a transition array, using the array from the owning map if it
+  // already has one (copying into a larger array if necessary), otherwise
+  // creating a new one according to flag.
+  // TODO(verwaest): This should not cause an existing transition to be
+  // overwritten.
+  static Handle<TransitionArray> Insert(Handle<Map> map, Handle<Name> name,
+                                        Handle<Map> target,
+                                        SimpleTransitionFlag flag);
+  // Search a  transition for a given kind, property name and attributes.
+  int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
+             int* out_insertion_index = NULL);
+
+  // Search a non-property transition (like elements kind, observe or frozen
+  // transitions).
+  inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
+    return SearchName(symbol, out_insertion_index);
+  }
 
   static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
 
-  // Returns the number of transitions in the array.
-  static int NumberOfTransitions(Object* raw_transitions);
-  // Required for templatized Search interface.
-  inline int number_of_entries() { return number_of_transitions(); }
+  // Allocates a TransitionArray.
+  static Handle<TransitionArray> Allocate(Isolate* isolate,
+                                          int number_of_transitions,
+                                          int slack = 0);
 
-  inline void SetNumberOfTransitions(int number_of_transitions);
+  bool IsSimpleTransition() {
+    return length() == kSimpleTransitionSize &&
+        get(kSimpleTransitionTarget)->IsHeapObject() &&
+        // The IntrusivePrototypeTransitionIterator may have set the map of the
+        // prototype transitions array to a smi. In that case, there are
+        // prototype transitions, hence this transition array is a full
+        // transition array.
+        HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
+        get(kSimpleTransitionTarget)->IsMap();
+  }
 
-  static int Capacity(Object* raw_transitions);
+  bool IsFullTransitionArray() {
+    return length() > kFirstIndex ||
+        (length() == kFirstIndex && !IsSimpleTransition());
+  }
 
   // Casting.
   static inline TransitionArray* cast(Object* obj);
 
+  // Constant for denoting key was not found.
+  static const int kNotFound = -1;
+
+  static const int kBackPointerStorageIndex = 0;
+
+  // Layout for full transition arrays.
+  static const int kPrototypeTransitionsIndex = 1;
+  static const int kTransitionLengthIndex = 2;
+  static const int kFirstIndex = 3;
+
+  // Layout for simple transition arrays.
+  static const int kSimpleTransitionTarget = 1;
+  static const int kSimpleTransitionSize = 2;
+  static const int kSimpleTransitionIndex = 0;
+  STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
+
+  static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
+
+  // Layout for the full transition array header.
+  static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
+                                                 kPointerSize;
+  static const int kTransitionLengthOffset =
+      kPrototypeTransitionsOffset + kPointerSize;
+
+  // Layout of map transition entries in full transition arrays.
+  static const int kTransitionKey = 0;
+  static const int kTransitionTarget = 1;
   static const int kTransitionSize = 2;
-  static const int kProtoTransitionHeaderSize = 1;
 
 #if defined(DEBUG) || defined(OBJECT_PRINT)
   // For our gdb macros, we should perhaps change these in the future.
   void Print();
 
   // Print all the transitions.
-  static void PrintTransitions(std::ostream& os, Object* transitions,
-                               bool print_header = true);  // NOLINT
+  void PrintTransitions(std::ostream& os, bool print_header = true);  // NOLINT
 #endif
 
 #ifdef DEBUG
   bool IsSortedNoDuplicates(int valid_entries = -1);
-  static bool IsSortedNoDuplicates(Map* map);
-  static bool IsConsistentWithBackPointers(Map* map);
+  bool IsConsistentWithBackPointers(Map* current_map);
+  bool IsEqualTo(TransitionArray* other);
 
   // Returns true for a non-property transitions like elements kind, observed
   // or frozen transitions.
   static inline bool IsSpecialTransition(Name* name);
 #endif
 
-  // Constant for denoting key was not found.
-  static const int kNotFound = -1;
-
   // The maximum number of transitions we want in a transition array (should
   // fit in a page).
   static const int kMaxNumberOfTransitions = 1024 + 512;
 
+  // Returns the fixed array length required to hold number_of_transitions
+  // transitions.
+  static int LengthFor(int number_of_transitions) {
+    return ToKeyIndex(number_of_transitions);
+  }
+
  private:
-  // Layout for full transition arrays.
-  static const int kPrototypeTransitionsIndex = 0;
-  static const int kTransitionLengthIndex = 1;
-  static const int kFirstIndex = 2;
-
-  // Layout of map transition entries in full transition arrays.
-  static const int kTransitionKey = 0;
-  static const int kTransitionTarget = 1;
-  STATIC_ASSERT(kTransitionSize == 2);
-
-  static const int kProtoTransitionNumberOfEntriesOffset = 0;
-  STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
-
   // Conversion from transition number to array indices.
   static int ToKeyIndex(int transition_number) {
     return kFirstIndex +
            (transition_number * kTransitionSize) +
            kTransitionKey;
   }
 
   static int ToTargetIndex(int transition_number) {
     return kFirstIndex +
            (transition_number * kTransitionSize) +
            kTransitionTarget;
   }
 
-  // Returns the fixed array length required to hold number_of_transitions
-  // transitions.
-  static int LengthFor(int number_of_transitions) {
-    return ToKeyIndex(number_of_transitions);
-  }
+  static Handle<TransitionArray> AllocateSimple(
+      Isolate* isolate, Handle<Map> target);
 
-  // Allocates a TransitionArray.
-  static Handle<TransitionArray> Allocate(Isolate* isolate,
-                                          int number_of_transitions,
-                                          int slack = 0);
+  // Allocate a new transition array with a single entry.
+  static Handle<TransitionArray> NewWith(Handle<Map> map,
+                                         Handle<Name> name,
+                                         Handle<Map> target,
+                                         SimpleTransitionFlag flag);
 
-  static void EnsureHasFullTransitionArray(Handle<Map> map);
-  static void ReplaceTransitions(Handle<Map> map, Object* new_transitions);
-
-  // Search a  transition for a given kind, property name and attributes.
-  int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
-             int* out_insertion_index = NULL);
-
-  // Search a non-property transition (like elements kind, observe or frozen
-  // transitions).
-  inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
-    return SearchName(symbol, out_insertion_index);
-  }
   // Search a first transition for a given property name.
   inline int SearchName(Name* name, int* out_insertion_index = NULL);
   int SearchDetails(int transition, PropertyKind kind,
                     PropertyAttributes attributes, int* out_insertion_index);
 
-  int number_of_transitions() {
-    if (length() < kFirstIndex) return 0;
-    return Smi::cast(get(kTransitionLengthIndex))->value();
-  }
-
-  static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
-    return transition->GetLastDescriptorDetails();
-  }
-
-  static inline Name* GetSimpleTransitionKey(Map* transition) {
-    int descriptor = transition->LastAdded();
-    return transition->instance_descriptors()->GetKey(descriptor);
-  }
-
-  static void TraverseTransitionTreeInternal(Map* map,
-                                             TraverseCallback callback,
-                                             void* data);
-
-  static void SetPrototypeTransitions(Handle<Map> map,
-                                      Handle<FixedArray> proto_transitions);
-
   // Compares two tuples <key, kind, attributes>, returns -1 if
   // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
   static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
                                 PropertyAttributes attributes1, Name* key2,
                                 uint32_t hash2, PropertyKind kind2,
                                 PropertyAttributes attributes2);
 
   // Compares keys, returns -1 if key1 is "less" than key2,
   // 0 if key1 equal to key2 and 1 otherwise.
   static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2,
                                  uint32_t hash2);
 
   // Compares two details, returns -1 if details1 is "less" than details2,
   // 0 if details1 equal to details2 and 1 otherwise.
   static inline int CompareDetails(PropertyKind kind1,
                                    PropertyAttributes attributes1,
                                    PropertyKind kind2,
                                    PropertyAttributes attributes2);
 
   inline void NoIncrementalWriteBarrierSet(int transition_number,
                                            Name* key,
                                            Map* target);
 
   // Copy a single transition from the origin array.
   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
                                                 int origin_transition,
                                                 int target_transition);
 
-#ifdef DEBUG
-  static void CheckNewTransitionsAreConsistent(Handle<Map> map,
-                                               TransitionArray* old_transitions,
-                                               Object* transitions);
-#endif
-
   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TRANSITIONS_H_