1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_TRANSITIONS_H_ 29 #define V8_TRANSITIONS_H_ 30 31 #include "elements-kind.h" 32 #include "heap.h" 33 #include "isolate.h" 34 #include "objects.h" 35 #include "v8checks.h" 36 37 namespace v8 { 38 namespace internal { 39 40 41 // TransitionArrays are fixed arrays used to hold map transitions for property, 42 // constant, and element changes. They can either be simple transition arrays 43 // that store a single property transition, or a full transition array that has 44 // prototype transitions and multiple property transitons. The details related 45 // to property transitions are accessed in the descriptor array of the target 46 // map. In the case of a simple transition, the key is also read from the 47 // descriptor array of the target map. 48 // 49 // The simple format of the these objects is: 50 // [0] Undefined or back pointer map 51 // [1] Single transition 52 // 53 // The full format is: 54 // [0] Undefined or back pointer map 55 // [1] Smi(0) or fixed array of prototype transitions 56 // [2] First transition 57 // [length() - kTransitionSize] Last transition 58 class TransitionArray: public FixedArray { 59 public: 60 // Accessors for fetching instance transition at transition number. 61 inline Name* GetKey(int transition_number); 62 inline void SetKey(int transition_number, Name* value); 63 inline Object** GetKeySlot(int transition_number); 64 int GetSortedKeyIndex(int transition_number) { return transition_number; } 65 66 Name* GetSortedKey(int transition_number) { 67 return GetKey(transition_number); 68 } 69 70 inline Map* GetTarget(int transition_number); 71 inline void SetTarget(int transition_number, Map* target); 72 73 inline PropertyDetails GetTargetDetails(int transition_number); 74 75 inline bool HasElementsTransition(); 76 77 inline Object* back_pointer_storage(); 78 inline void set_back_pointer_storage( 79 Object* back_pointer, 80 WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 81 82 inline FixedArray* GetPrototypeTransitions(); 83 inline void SetPrototypeTransitions( 84 FixedArray* prototype_transitions, 85 WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 86 inline Object** GetPrototypeTransitionsSlot(); 87 inline bool HasPrototypeTransitions(); 88 inline HeapObject* UncheckedPrototypeTransitions(); 89 90 // Returns the number of transitions in the array. 91 int number_of_transitions() { 92 if (IsSimpleTransition()) return 1; 93 int len = length(); 94 return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize; 95 } 96 97 inline int number_of_entries() { return number_of_transitions(); } 98 99 // Allocate a new transition array with a single entry. 100 static MUST_USE_RESULT MaybeObject* NewWith( 101 SimpleTransitionFlag flag, 102 Name* key, 103 Map* target, 104 Object* back_pointer); 105 106 MUST_USE_RESULT MaybeObject* ExtendToFullTransitionArray(); 107 108 // Copy the transition array, inserting a new transition. 109 // TODO(verwaest): This should not cause an existing transition to be 110 // overwritten. 111 MUST_USE_RESULT MaybeObject* CopyInsert(Name* name, Map* target); 112 113 // Copy a single transition from the origin array. 114 inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin, 115 int origin_transition, 116 int target_transition); 117 118 // Search a transition for a given property name. 119 inline int Search(Name* name); 120 121 // Allocates a TransitionArray. 122 MUST_USE_RESULT static MaybeObject* Allocate( 123 Isolate* isolate, int number_of_transitions); 124 125 bool IsSimpleTransition() { 126 return length() == kSimpleTransitionSize && 127 get(kSimpleTransitionTarget)->IsHeapObject() && 128 // The IntrusivePrototypeTransitionIterator may have set the map of the 129 // prototype transitions array to a smi. In that case, there are 130 // prototype transitions, hence this transition array is a full 131 // transition array. 132 HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() && 133 get(kSimpleTransitionTarget)->IsMap(); 134 } 135 136 bool IsFullTransitionArray() { 137 return length() > kFirstIndex || 138 (length() == kFirstIndex && !IsSimpleTransition()); 139 } 140 141 // Casting. 142 static inline TransitionArray* cast(Object* obj); 143 144 // Constant for denoting key was not found. 145 static const int kNotFound = -1; 146 147 static const int kBackPointerStorageIndex = 0; 148 149 // Layout for full transition arrays. 150 static const int kPrototypeTransitionsIndex = 1; 151 static const int kFirstIndex = 2; 152 153 // Layout for simple transition arrays. 154 static const int kSimpleTransitionTarget = 1; 155 static const int kSimpleTransitionSize = 2; 156 static const int kSimpleTransitionIndex = 0; 157 STATIC_ASSERT(kSimpleTransitionIndex != kNotFound); 158 159 static const int kBackPointerStorageOffset = FixedArray::kHeaderSize; 160 161 // Layout for the full transition array header. 162 static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset + 163 kPointerSize; 164 165 // Layout of map transition entries in full transition arrays. 166 static const int kTransitionKey = 0; 167 static const int kTransitionTarget = 1; 168 static const int kTransitionSize = 2; 169 170 #ifdef OBJECT_PRINT 171 // Print all the transitions. 172 inline void PrintTransitions() { 173 PrintTransitions(stdout); 174 } 175 void PrintTransitions(FILE* out); 176 #endif 177 178 #ifdef DEBUG 179 bool IsSortedNoDuplicates(int valid_entries = -1); 180 bool IsConsistentWithBackPointers(Map* current_map); 181 bool IsEqualTo(TransitionArray* other); 182 #endif 183 184 // The maximum number of transitions we want in a transition array (should 185 // fit in a page). 186 static const int kMaxNumberOfTransitions = 1024 + 512; 187 188 private: 189 // Conversion from transition number to array indices. 190 static int ToKeyIndex(int transition_number) { 191 return kFirstIndex + 192 (transition_number * kTransitionSize) + 193 kTransitionKey; 194 } 195 196 static int ToTargetIndex(int transition_number) { 197 return kFirstIndex + 198 (transition_number * kTransitionSize) + 199 kTransitionTarget; 200 } 201 202 inline void NoIncrementalWriteBarrierSet(int transition_number, 203 Name* key, 204 Map* target); 205 206 DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray); 207 }; 208 209 210 } } // namespace v8::internal 211 212 #endif // V8_TRANSITIONS_H_ 213
