Reland "Limit the number of transitions allowed per hidden class."

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"
@@ skipping 12 matching lines @@
 // map. In the case of a simple transition, the key is also read from the
 // descriptor array of the target map.
 //
 // The simple format of the these objects is:
 // [0] Undefined or back pointer map
 // [1] Single transition
 //
 // The full format is:
 // [0] Undefined or back pointer map
 // [1] Smi(0) or fixed array of prototype transitions
-// [2] First transition
-// [length() - kTransitionSize] Last transition
+// [2] Number of transitions
+// [3] First transition
+// [3 + number of transitions * kTransitionSize]: start of slack
 class TransitionArray: public FixedArray {
  public:
   // 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; }
 
   Name* GetSortedKey(int transition_number) {
     return GetKey(transition_number);
@@ skipping 15 matching lines @@
   inline FixedArray* GetPrototypeTransitions();
   inline void SetPrototypeTransitions(
       FixedArray* prototype_transitions,
       WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
   inline Object** GetPrototypeTransitionsSlot();
   inline bool HasPrototypeTransitions();
 
   // Returns the number of transitions in the array.
   int number_of_transitions() {
     if (IsSimpleTransition()) return 1;
-    int len = length();
-    return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
+    if (length() <= kFirstIndex) return 0;
+    return Smi::cast(get(kTransitionLengthIndex))->value();
   }
 
+  int number_of_transitions_storage() {
+    if (IsSimpleTransition()) return 1;
+    if (length() <= kFirstIndex) return 0;
+    return (length() - kFirstIndex) / kTransitionSize;
+  }
+
+  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);
 
-  // Create a transition array, copying from the owning map if it already has
-  // one, otherwise creating a new one according to flag.
+  // 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> CopyInsert(Handle<Map> map,
-                                            Handle<Name> name,
-                                            Handle<Map> target,
-                                            SimpleTransitionFlag flag);
+  static Handle<TransitionArray> Insert(Handle<Map> map, Handle<Name> name,
+                                        Handle<Map> target,
+                                        SimpleTransitionFlag flag);
 
   // Search a transition for a given property name.
   inline int Search(Name* name);
 
   // Allocates a TransitionArray.
-  static Handle<TransitionArray> Allocate(
-      Isolate* isolate, int number_of_transitions);
+  static Handle<TransitionArray> Allocate(Isolate* isolate,
+                                          int number_of_transitions,
+                                          int slack = 0);
 
   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();
   }
 
   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 kFirstIndex = 2;
+  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;
 
 #ifdef OBJECT_PRINT
   // For our gdb macros, we should perhaps change these in the future.
   void Print();
 
   // Print all the transitions.
   void PrintTransitions(std::ostream& os, bool print_header = true);  // NOLINT
 #endif
 
 #ifdef DEBUG
   bool IsSortedNoDuplicates(int valid_entries = -1);
   bool IsConsistentWithBackPointers(Map* current_map);
   bool IsEqualTo(TransitionArray* other);
 #endif
 
   // 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:
   // 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 +
@@ skipping 19 matching lines @@
                                                 int origin_transition,
                                                 int target_transition);
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TRANSITIONS_H_