1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_TRANSITIONS_H_ 6 #define V8_TRANSITIONS_H_ 7 8 #include "src/elements-kind.h" 9 #include "src/heap.h" 10 #include "src/isolate.h" 11 #include "src/objects.h" 12 #include "src/v8checks.h" 13 14 namespace v8 { 15 namespace internal { 16 17 18 // TransitionArrays are fixed arrays used to hold map transitions for property, 19 // constant, and element changes. They can either be simple transition arrays 20 // that store a single property transition, or a full transition array that has 21 // prototype transitions and multiple property transitons. The details related 22 // to property transitions are accessed in the descriptor array of the target 23 // map. In the case of a simple transition, the key is also read from the 24 // descriptor array of the target map. 25 // 26 // The simple format of the these objects is: 27 // [0] Undefined or back pointer map 28 // [1] Single transition 29 // 30 // The full format is: 31 // [0] Undefined or back pointer map 32 // [1] Smi(0) or fixed array of prototype transitions 33 // [2] First transition 34 // [length() - kTransitionSize] Last transition 35 class TransitionArray: public FixedArray { 36 public: 37 // Accessors for fetching instance transition at transition number. 38 inline Name* GetKey(int transition_number); 39 inline void SetKey(int transition_number, Name* value); 40 inline Object** GetKeySlot(int transition_number); GetSortedKeyIndex(int transition_number)41 int GetSortedKeyIndex(int transition_number) { return transition_number; } 42 GetSortedKey(int transition_number)43 Name* GetSortedKey(int transition_number) { 44 return GetKey(transition_number); 45 } 46 47 inline Map* GetTarget(int transition_number); 48 inline void SetTarget(int transition_number, Map* target); 49 50 inline PropertyDetails GetTargetDetails(int transition_number); 51 52 inline bool HasElementsTransition(); 53 54 inline Object* back_pointer_storage(); 55 inline void set_back_pointer_storage( 56 Object* back_pointer, 57 WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 58 59 inline FixedArray* GetPrototypeTransitions(); 60 inline void SetPrototypeTransitions( 61 FixedArray* prototype_transitions, 62 WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 63 inline Object** GetPrototypeTransitionsSlot(); 64 inline bool HasPrototypeTransitions(); 65 66 // Returns the number of transitions in the array. number_of_transitions()67 int number_of_transitions() { 68 if (IsSimpleTransition()) return 1; 69 int len = length(); 70 return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize; 71 } 72 number_of_entries()73 inline int number_of_entries() { return number_of_transitions(); } 74 75 // Creates a FullTransitionArray from a SimpleTransitionArray in 76 // containing_map. 77 static Handle<TransitionArray> ExtendToFullTransitionArray( 78 Handle<Map> containing_map); 79 80 // Create a transition array, copying from the owning map if it already has 81 // one, otherwise creating a new one according to flag. 82 // TODO(verwaest): This should not cause an existing transition to be 83 // overwritten. 84 static Handle<TransitionArray> CopyInsert(Handle<Map> map, 85 Handle<Name> name, 86 Handle<Map> target, 87 SimpleTransitionFlag flag); 88 89 // Search a transition for a given property name. 90 inline int Search(Name* name); 91 92 // Allocates a TransitionArray. 93 static Handle<TransitionArray> Allocate( 94 Isolate* isolate, int number_of_transitions); 95 IsSimpleTransition()96 bool IsSimpleTransition() { 97 return length() == kSimpleTransitionSize && 98 get(kSimpleTransitionTarget)->IsHeapObject() && 99 // The IntrusivePrototypeTransitionIterator may have set the map of the 100 // prototype transitions array to a smi. In that case, there are 101 // prototype transitions, hence this transition array is a full 102 // transition array. 103 HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() && 104 get(kSimpleTransitionTarget)->IsMap(); 105 } 106 IsFullTransitionArray()107 bool IsFullTransitionArray() { 108 return length() > kFirstIndex || 109 (length() == kFirstIndex && !IsSimpleTransition()); 110 } 111 112 // Casting. 113 static inline TransitionArray* cast(Object* obj); 114 115 // Constant for denoting key was not found. 116 static const int kNotFound = -1; 117 118 static const int kBackPointerStorageIndex = 0; 119 120 // Layout for full transition arrays. 121 static const int kPrototypeTransitionsIndex = 1; 122 static const int kFirstIndex = 2; 123 124 // Layout for simple transition arrays. 125 static const int kSimpleTransitionTarget = 1; 126 static const int kSimpleTransitionSize = 2; 127 static const int kSimpleTransitionIndex = 0; 128 STATIC_ASSERT(kSimpleTransitionIndex != kNotFound); 129 130 static const int kBackPointerStorageOffset = FixedArray::kHeaderSize; 131 132 // Layout for the full transition array header. 133 static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset + 134 kPointerSize; 135 136 // Layout of map transition entries in full transition arrays. 137 static const int kTransitionKey = 0; 138 static const int kTransitionTarget = 1; 139 static const int kTransitionSize = 2; 140 141 #ifdef OBJECT_PRINT 142 // Print all the transitions. PrintTransitions()143 inline void PrintTransitions() { 144 PrintTransitions(stdout); 145 } 146 void PrintTransitions(FILE* out); 147 #endif 148 149 #ifdef DEBUG 150 bool IsSortedNoDuplicates(int valid_entries = -1); 151 bool IsConsistentWithBackPointers(Map* current_map); 152 bool IsEqualTo(TransitionArray* other); 153 #endif 154 155 // The maximum number of transitions we want in a transition array (should 156 // fit in a page). 157 static const int kMaxNumberOfTransitions = 1024 + 512; 158 159 private: 160 // Conversion from transition number to array indices. ToKeyIndex(int transition_number)161 static int ToKeyIndex(int transition_number) { 162 return kFirstIndex + 163 (transition_number * kTransitionSize) + 164 kTransitionKey; 165 } 166 ToTargetIndex(int transition_number)167 static int ToTargetIndex(int transition_number) { 168 return kFirstIndex + 169 (transition_number * kTransitionSize) + 170 kTransitionTarget; 171 } 172 173 static Handle<TransitionArray> AllocateSimple( 174 Isolate* isolate, Handle<Map> target); 175 176 // Allocate a new transition array with a single entry. 177 static Handle<TransitionArray> NewWith(Handle<Map> map, 178 Handle<Name> name, 179 Handle<Map> target, 180 SimpleTransitionFlag flag); 181 182 inline void NoIncrementalWriteBarrierSet(int transition_number, 183 Name* key, 184 Map* target); 185 186 // Copy a single transition from the origin array. 187 inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin, 188 int origin_transition, 189 int target_transition); 190 191 DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray); 192 }; 193 194 195 } } // namespace v8::internal 196 197 #endif // V8_TRANSITIONS_H_ 198