Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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/checks.h" |
| 9 | #include "src/elements-kind.h" |
| 10 | #include "src/heap/heap.h" |
| 11 | #include "src/isolate.h" |
| 12 | #include "src/objects.h" |
| 13 | |
| 14 | namespace v8 { |
| 15 | namespace internal { |
| 16 | |
| 17 | |
| 18 | // TransitionArrays are fixed arrays used to hold map transitions for property, |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 19 | // constant, and element changes. "Simple" transitions storing only a single |
| 20 | // property transition are stored inline (i.e. the target map is stored |
| 21 | // directly); otherwise a full transition array is used that has |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 22 | // prototype transitions and multiple property transitons. The details related |
| 23 | // to property transitions are accessed in the descriptor array of the target |
| 24 | // map. In the case of a simple transition, the key is also read from the |
| 25 | // descriptor array of the target map. |
| 26 | // |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 27 | // This class provides a static interface that operates directly on maps |
| 28 | // and handles the distinction between simple and full transitions storage. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 29 | // |
| 30 | // The full format is: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 31 | // [0] Smi(0) or fixed array of prototype transitions |
| 32 | // [1] Number of transitions |
| 33 | // [2] First transition |
| 34 | // [2 + number of transitions * kTransitionSize]: start of slack |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 35 | class TransitionArray: public FixedArray { |
| 36 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 37 | // Insert a new transition into |map|'s transition array, extending it |
| 38 | // as necessary. |
| 39 | static void Insert(Handle<Map> map, Handle<Name> name, Handle<Map> target, |
| 40 | SimpleTransitionFlag flag); |
| 41 | |
| 42 | static Map* SearchTransition(Map* map, PropertyKind kind, Name* name, |
| 43 | PropertyAttributes attributes); |
| 44 | static MaybeHandle<Map> SearchTransition(Handle<Map> map, PropertyKind kind, |
| 45 | Handle<Name> name, |
| 46 | PropertyAttributes attributes) { |
| 47 | if (Map* transition = SearchTransition(*map, kind, *name, attributes)) { |
| 48 | return handle(transition); |
| 49 | } |
| 50 | return MaybeHandle<Map>(); |
| 51 | } |
| 52 | |
| 53 | static Map* SearchSpecial(Map* map, Symbol* name); |
| 54 | |
| 55 | static Handle<Map> FindTransitionToField(Handle<Map> map, Handle<Name> name); |
| 56 | |
| 57 | static Handle<String> ExpectedTransitionKey(Handle<Map> map); |
| 58 | |
| 59 | static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) { |
| 60 | DCHECK(!ExpectedTransitionKey(map).is_null()); |
| 61 | return Handle<Map>(GetSimpleTransition(map->raw_transitions())); |
| 62 | } |
| 63 | // Returns true if |raw_transition| can be overwritten with a simple |
| 64 | // transition (because it's either uninitialized, or has been cleared). |
| 65 | static inline bool CanStoreSimpleTransition(Object* raw_transition) { |
| 66 | return raw_transition->IsSmi() || |
| 67 | (raw_transition->IsWeakCell() && |
| 68 | WeakCell::cast(raw_transition)->cleared()); |
| 69 | } |
| 70 | static inline bool IsSimpleTransition(Object* raw_transition) { |
| 71 | DCHECK(!raw_transition->IsWeakCell() || |
| 72 | WeakCell::cast(raw_transition)->cleared() || |
| 73 | WeakCell::cast(raw_transition)->value()->IsMap()); |
| 74 | return raw_transition->IsWeakCell() && |
| 75 | !WeakCell::cast(raw_transition)->cleared(); |
| 76 | } |
| 77 | static inline Map* GetSimpleTransition(Object* raw_transition) { |
| 78 | DCHECK(IsSimpleTransition(raw_transition)); |
| 79 | DCHECK(raw_transition->IsWeakCell()); |
| 80 | return Map::cast(WeakCell::cast(raw_transition)->value()); |
| 81 | } |
| 82 | static inline bool IsFullTransitionArray(Object* raw_transitions) { |
| 83 | return raw_transitions->IsTransitionArray(); |
| 84 | } |
| 85 | |
| 86 | // The size of transition arrays are limited so they do not end up in large |
| 87 | // object space. Otherwise ClearNonLiveReferences would leak memory while |
| 88 | // applying in-place right trimming. |
| 89 | static bool CanHaveMoreTransitions(Handle<Map> map); |
| 90 | |
| 91 | // ===== PROTOTYPE TRANSITIONS ===== |
| 92 | // When you set the prototype of an object using the __proto__ accessor you |
| 93 | // need a new map for the object (the prototype is stored in the map). In |
| 94 | // order not to multiply maps unnecessarily we store these as transitions in |
| 95 | // the original map. That way we can transition to the same map if the same |
| 96 | // prototype is set, rather than creating a new map every time. The |
| 97 | // transitions are in the form of a map where the keys are prototype objects |
| 98 | // and the values are the maps they transition to. |
| 99 | // Cache format: |
| 100 | // 0: finger - index of the first free cell in the cache |
| 101 | // 1 + i: target map |
| 102 | static const int kMaxCachedPrototypeTransitions = 256; |
| 103 | static void PutPrototypeTransition(Handle<Map> map, Handle<Object> prototype, |
| 104 | Handle<Map> target_map); |
| 105 | |
| 106 | static Handle<Map> GetPrototypeTransition(Handle<Map> map, |
| 107 | Handle<Object> prototype); |
| 108 | |
| 109 | static FixedArray* GetPrototypeTransitions(Map* map); |
| 110 | |
| 111 | static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) { |
| 112 | if (proto_transitions->length() == 0) return 0; |
| 113 | Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset); |
| 114 | return Smi::cast(raw)->value(); |
| 115 | } |
| 116 | static int NumberOfPrototypeTransitionsForTest(Map* map); |
| 117 | |
| 118 | static void SetNumberOfPrototypeTransitions(FixedArray* proto_transitions, |
| 119 | int value); |
| 120 | |
| 121 | inline FixedArray* GetPrototypeTransitions(); |
| 122 | inline void SetPrototypeTransitions(FixedArray* prototype_transitions); |
| 123 | inline Object** GetPrototypeTransitionsSlot(); |
| 124 | inline bool HasPrototypeTransitions(); |
| 125 | |
| 126 | // ===== ITERATION ===== |
| 127 | |
| 128 | typedef void (*TraverseCallback)(Map* map, void* data); |
| 129 | |
| 130 | // Traverse the transition tree in postorder. |
| 131 | static void TraverseTransitionTree(Map* map, TraverseCallback callback, |
| 132 | void* data) { |
| 133 | // Make sure that we do not allocate in the callback. |
| 134 | DisallowHeapAllocation no_allocation; |
| 135 | TraverseTransitionTreeInternal(map, callback, data); |
| 136 | } |
| 137 | |
| 138 | // ===== LOW-LEVEL ACCESSORS ===== |
| 139 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 140 | // Accessors for fetching instance transition at transition number. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 141 | static inline Name* GetKey(Object* raw_transitions, int transition_number); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 142 | inline Name* GetKey(int transition_number); |
| 143 | inline void SetKey(int transition_number, Name* value); |
| 144 | inline Object** GetKeySlot(int transition_number); |
| 145 | int GetSortedKeyIndex(int transition_number) { return transition_number; } |
| 146 | |
| 147 | Name* GetSortedKey(int transition_number) { |
| 148 | return GetKey(transition_number); |
| 149 | } |
| 150 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 151 | static inline Map* GetTarget(Object* raw_transitions, int transition_number); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 152 | inline Map* GetTarget(int transition_number); |
| 153 | inline void SetTarget(int transition_number, Map* target); |
| 154 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 155 | static inline PropertyDetails GetTargetDetails(Name* name, Map* target); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 156 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 157 | // Returns the number of transitions in the array. |
| 158 | static int NumberOfTransitions(Object* raw_transitions); |
| 159 | // Required for templatized Search interface. |
| 160 | inline int number_of_entries() { return number_of_transitions(); } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 161 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 162 | inline void SetNumberOfTransitions(int number_of_transitions); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 163 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 164 | static int Capacity(Object* raw_transitions); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 165 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 166 | inline static TransitionArray* cast(Object* object); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 167 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 168 | // This field should be used only by GC. |
| 169 | inline void set_next_link(Object* next, WriteBarrierMode mode); |
| 170 | inline Object* next_link(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 171 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 172 | static const int kTransitionSize = 2; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 173 | static const int kProtoTransitionHeaderSize = 1; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 174 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 175 | #if defined(DEBUG) || defined(OBJECT_PRINT) |
| 176 | // For our gdb macros, we should perhaps change these in the future. |
| 177 | void Print(); |
| 178 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 179 | // Print all the transitions. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 180 | static void PrintTransitions(std::ostream& os, Object* transitions, |
| 181 | bool print_header = true); // NOLINT |
| 182 | #endif |
| 183 | |
| 184 | #ifdef OBJECT_PRINT |
| 185 | void TransitionArrayPrint(std::ostream& os); // NOLINT |
| 186 | #endif |
| 187 | |
| 188 | #ifdef VERIFY_HEAP |
| 189 | void TransitionArrayVerify(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 190 | #endif |
| 191 | |
| 192 | #ifdef DEBUG |
| 193 | bool IsSortedNoDuplicates(int valid_entries = -1); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 194 | static bool IsSortedNoDuplicates(Map* map); |
| 195 | static bool IsConsistentWithBackPointers(Map* map); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 196 | |
| 197 | // Returns true for a non-property transitions like elements kind, observed |
| 198 | // or frozen transitions. |
| 199 | static inline bool IsSpecialTransition(Name* name); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 200 | #endif |
| 201 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 202 | // Constant for denoting key was not found. |
| 203 | static const int kNotFound = -1; |
| 204 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 205 | // The maximum number of transitions we want in a transition array (should |
| 206 | // fit in a page). |
| 207 | static const int kMaxNumberOfTransitions = 1024 + 512; |
| 208 | |
| 209 | private: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 210 | // Layout for full transition arrays. |
| 211 | static const int kNextLinkIndex = 0; |
| 212 | static const int kPrototypeTransitionsIndex = 1; |
| 213 | static const int kTransitionLengthIndex = 2; |
| 214 | static const int kFirstIndex = 3; |
| 215 | |
| 216 | // Layout of map transition entries in full transition arrays. |
| 217 | static const int kTransitionKey = 0; |
| 218 | static const int kTransitionTarget = 1; |
| 219 | STATIC_ASSERT(kTransitionSize == 2); |
| 220 | |
| 221 | static const int kProtoTransitionNumberOfEntriesOffset = 0; |
| 222 | STATIC_ASSERT(kProtoTransitionHeaderSize == 1); |
| 223 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 224 | // Conversion from transition number to array indices. |
| 225 | static int ToKeyIndex(int transition_number) { |
| 226 | return kFirstIndex + |
| 227 | (transition_number * kTransitionSize) + |
| 228 | kTransitionKey; |
| 229 | } |
| 230 | |
| 231 | static int ToTargetIndex(int transition_number) { |
| 232 | return kFirstIndex + |
| 233 | (transition_number * kTransitionSize) + |
| 234 | kTransitionTarget; |
| 235 | } |
| 236 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 237 | // Returns the fixed array length required to hold number_of_transitions |
| 238 | // transitions. |
| 239 | static int LengthFor(int number_of_transitions) { |
| 240 | return ToKeyIndex(number_of_transitions); |
| 241 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 242 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 243 | // Allocates a TransitionArray. |
| 244 | static Handle<TransitionArray> Allocate(Isolate* isolate, |
| 245 | int number_of_transitions, |
| 246 | int slack = 0); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 247 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 248 | static void EnsureHasFullTransitionArray(Handle<Map> map); |
| 249 | static void ReplaceTransitions(Handle<Map> map, Object* new_transitions); |
| 250 | |
| 251 | // Search a transition for a given kind, property name and attributes. |
| 252 | int Search(PropertyKind kind, Name* name, PropertyAttributes attributes, |
| 253 | int* out_insertion_index = NULL); |
| 254 | |
| 255 | // Search a non-property transition (like elements kind, observe or frozen |
| 256 | // transitions). |
| 257 | inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) { |
| 258 | return SearchName(symbol, out_insertion_index); |
| 259 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 260 | // Search a first transition for a given property name. |
| 261 | inline int SearchName(Name* name, int* out_insertion_index = NULL); |
| 262 | int SearchDetails(int transition, PropertyKind kind, |
| 263 | PropertyAttributes attributes, int* out_insertion_index); |
| 264 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 265 | int number_of_transitions() { |
| 266 | if (length() < kFirstIndex) return 0; |
| 267 | return Smi::cast(get(kTransitionLengthIndex))->value(); |
| 268 | } |
| 269 | |
| 270 | static inline PropertyDetails GetSimpleTargetDetails(Map* transition) { |
| 271 | return transition->GetLastDescriptorDetails(); |
| 272 | } |
| 273 | |
| 274 | static inline Name* GetSimpleTransitionKey(Map* transition) { |
| 275 | int descriptor = transition->LastAdded(); |
| 276 | return transition->instance_descriptors()->GetKey(descriptor); |
| 277 | } |
| 278 | |
| 279 | static void TraverseTransitionTreeInternal(Map* map, |
| 280 | TraverseCallback callback, |
| 281 | void* data); |
| 282 | |
| 283 | static void SetPrototypeTransitions(Handle<Map> map, |
| 284 | Handle<FixedArray> proto_transitions); |
| 285 | |
| 286 | static bool CompactPrototypeTransitionArray(FixedArray* array); |
| 287 | |
| 288 | static Handle<FixedArray> GrowPrototypeTransitionArray( |
| 289 | Handle<FixedArray> array, int new_capacity, Isolate* isolate); |
| 290 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 291 | // Compares two tuples <key, kind, attributes>, returns -1 if |
| 292 | // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise. |
| 293 | static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1, |
| 294 | PropertyAttributes attributes1, Name* key2, |
| 295 | uint32_t hash2, PropertyKind kind2, |
| 296 | PropertyAttributes attributes2); |
| 297 | |
| 298 | // Compares keys, returns -1 if key1 is "less" than key2, |
| 299 | // 0 if key1 equal to key2 and 1 otherwise. |
| 300 | static inline int CompareNames(Name* key1, uint32_t hash1, Name* key2, |
| 301 | uint32_t hash2); |
| 302 | |
| 303 | // Compares two details, returns -1 if details1 is "less" than details2, |
| 304 | // 0 if details1 equal to details2 and 1 otherwise. |
| 305 | static inline int CompareDetails(PropertyKind kind1, |
| 306 | PropertyAttributes attributes1, |
| 307 | PropertyKind kind2, |
| 308 | PropertyAttributes attributes2); |
| 309 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 310 | inline void Set(int transition_number, Name* key, Map* target); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 311 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 312 | #ifdef DEBUG |
| 313 | static void CheckNewTransitionsAreConsistent(Handle<Map> map, |
| 314 | TransitionArray* old_transitions, |
| 315 | Object* transitions); |
| 316 | #endif |
| 317 | static void ZapTransitionArray(TransitionArray* transitions); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 318 | |
| 319 | DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray); |
| 320 | }; |
| 321 | |
| 322 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 323 | } // namespace internal |
| 324 | } // namespace v8 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 325 | |
| 326 | #endif // V8_TRANSITIONS_H_ |