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,
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.
143   void PrintTransitions(OStream& os);  // NOLINT
144 #endif
145 
146 #ifdef DEBUG
147   bool IsSortedNoDuplicates(int valid_entries = -1);
148   bool IsConsistentWithBackPointers(Map* current_map);
149   bool IsEqualTo(TransitionArray* other);
150 #endif
151 
152   // The maximum number of transitions we want in a transition array (should
153   // fit in a page).
154   static const int kMaxNumberOfTransitions = 1024 + 512;
155 
156  private:
157   // Conversion from transition number to array indices.
ToKeyIndex(int transition_number)158   static int ToKeyIndex(int transition_number) {
159     return kFirstIndex +
160            (transition_number * kTransitionSize) +
161            kTransitionKey;
162   }
163 
ToTargetIndex(int transition_number)164   static int ToTargetIndex(int transition_number) {
165     return kFirstIndex +
166            (transition_number * kTransitionSize) +
167            kTransitionTarget;
168   }
169 
170   static Handle<TransitionArray> AllocateSimple(
171       Isolate* isolate, Handle<Map> target);
172 
173   // Allocate a new transition array with a single entry.
174   static Handle<TransitionArray> NewWith(Handle<Map> map,
175                                          Handle<Name> name,
176                                          Handle<Map> target,
177                                          SimpleTransitionFlag flag);
178 
179   inline void NoIncrementalWriteBarrierSet(int transition_number,
180                                            Name* key,
181                                            Map* target);
182 
183   // Copy a single transition from the origin array.
184   inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
185                                                 int origin_transition,
186                                                 int target_transition);
187 
188   DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
189 };
190 
191 
192 } }  // namespace v8::internal
193 
194 #endif  // V8_TRANSITIONS_H_
195