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(int number_of_transitions); 123 124 bool IsSimpleTransition() { 125 return length() == kSimpleTransitionSize && 126 get(kSimpleTransitionTarget)->IsHeapObject() && 127 // The IntrusivePrototypeTransitionIterator may have set the map of the 128 // prototype transitions array to a smi. In that case, there are 129 // prototype transitions, hence this transition array is a full 130 // transition array. 131 HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() && 132 get(kSimpleTransitionTarget)->IsMap(); 133 } 134 135 bool IsFullTransitionArray() { 136 return length() > kFirstIndex || 137 (length() == kFirstIndex && !IsSimpleTransition()); 138 } 139 140 // Casting. 141 static inline TransitionArray* cast(Object* obj); 142 143 // Constant for denoting key was not found. 144 static const int kNotFound = -1; 145 146 static const int kBackPointerStorageIndex = 0; 147 148 // Layout for full transition arrays. 149 static const int kPrototypeTransitionsIndex = 1; 150 static const int kFirstIndex = 2; 151 152 // Layout for simple transition arrays. 153 static const int kSimpleTransitionTarget = 1; 154 static const int kSimpleTransitionSize = 2; 155 static const int kSimpleTransitionIndex = 0; 156 STATIC_ASSERT(kSimpleTransitionIndex != kNotFound); 157 158 static const int kBackPointerStorageOffset = FixedArray::kHeaderSize; 159 160 // Layout for the full transition array header. 161 static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset + 162 kPointerSize; 163 164 // Layout of map transition entries in full transition arrays. 165 static const int kTransitionKey = 0; 166 static const int kTransitionTarget = 1; 167 static const int kTransitionSize = 2; 168 169 #ifdef OBJECT_PRINT 170 // Print all the transitions. 171 inline void PrintTransitions() { 172 PrintTransitions(stdout); 173 } 174 void PrintTransitions(FILE* out); 175 #endif 176 177 #ifdef DEBUG 178 bool IsSortedNoDuplicates(int valid_entries = -1); 179 bool IsConsistentWithBackPointers(Map* current_map); 180 bool IsEqualTo(TransitionArray* other); 181 #endif 182 183 // The maximum number of transitions we want in a transition array (should 184 // fit in a page). 185 static const int kMaxNumberOfTransitions = 1024 + 512; 186 187 private: 188 // Conversion from transition number to array indices. 189 static int ToKeyIndex(int transition_number) { 190 return kFirstIndex + 191 (transition_number * kTransitionSize) + 192 kTransitionKey; 193 } 194 195 static int ToTargetIndex(int transition_number) { 196 return kFirstIndex + 197 (transition_number * kTransitionSize) + 198 kTransitionTarget; 199 } 200 201 inline void NoIncrementalWriteBarrierSet(int transition_number, 202 Name* key, 203 Map* target); 204 205 DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray); 206 }; 207 208 209 } } // namespace v8::internal 210 211 #endif // V8_TRANSITIONS_H_ 212
