Line data Source code
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/isolate.h"
11 : #include "src/objects.h"
12 : #include "src/objects/descriptor-array.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. "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
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 : //
27 : // This class provides a static interface that operates directly on maps
28 : // and handles the distinction between simple and full transitions storage.
29 : //
30 : // The full format is:
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
35 : class TransitionArray: public FixedArray {
36 : public:
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 4563 : static MaybeHandle<Map> SearchTransition(Handle<Map> map, PropertyKind kind,
45 : Handle<Name> name,
46 : PropertyAttributes attributes) {
47 4563 : 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 28257472 : static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
60 : DCHECK(!ExpectedTransitionKey(map).is_null());
61 28257472 : 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 15958181 : static inline bool CanStoreSimpleTransition(Object* raw_transition) {
66 20260452 : return raw_transition->IsSmi() ||
67 2752233 : (raw_transition->IsWeakCell() &&
68 15958181 : WeakCell::cast(raw_transition)->cleared());
69 : }
70 98027782 : 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 142603018 : return raw_transition->IsWeakCell() &&
75 98027777 : !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 68987763 : static inline bool IsFullTransitionArray(Object* raw_transitions) {
83 68987757 : 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 4408752 : static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
112 4408752 : if (proto_transitions->length() == 0) return 0;
113 : Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
114 4204120 : 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 186071 : TraverseTransitionTreeInternal(map, callback, data);
136 : }
137 :
138 : // ===== LOW-LEVEL ACCESSORS =====
139 :
140 : // Accessors for fetching instance transition at transition number.
141 : static inline Name* GetKey(Object* raw_transitions, int transition_number);
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 :
151 : static inline Map* GetTarget(Object* raw_transitions, int transition_number);
152 : inline Map* GetTarget(int transition_number);
153 : inline void SetTarget(int transition_number, Map* target);
154 :
155 : static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
156 :
157 : // Returns the number of transitions in the array.
158 : static int NumberOfTransitions(Object* raw_transitions);
159 : // Required for templatized Search interface.
160 37408779 : inline int number_of_entries() { return number_of_transitions(); }
161 :
162 : inline void SetNumberOfTransitions(int number_of_transitions);
163 :
164 : static int Capacity(Object* raw_transitions);
165 :
166 : inline static TransitionArray* cast(Object* object);
167 :
168 : // This field should be used only by GC.
169 : inline void set_next_link(Object* next, WriteBarrierMode mode);
170 : inline Object* next_link();
171 :
172 : static const int kTransitionSize = 2;
173 : static const int kProtoTransitionHeaderSize = 1;
174 :
175 : #if defined(DEBUG) || defined(OBJECT_PRINT)
176 : // For our gdb macros, we should perhaps change these in the future.
177 : void Print();
178 :
179 : // Print all the transitions.
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();
190 : #endif
191 :
192 : #ifdef DEBUG
193 : bool IsSortedNoDuplicates(int valid_entries = -1);
194 : static bool IsSortedNoDuplicates(Map* map);
195 : static bool IsConsistentWithBackPointers(Map* map);
196 :
197 : // Returns true for a non-property transitions like elements kind, observed
198 : // or frozen transitions.
199 : static inline bool IsSpecialTransition(Name* name);
200 : #endif
201 :
202 : // Constant for denoting key was not found.
203 : static const int kNotFound = -1;
204 :
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:
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 :
224 : // Conversion from transition number to array indices.
225 : static int ToKeyIndex(int transition_number) {
226 : return kFirstIndex +
227 182312443 : (transition_number * kTransitionSize) +
228 182312443 : kTransitionKey;
229 : }
230 :
231 : static int ToTargetIndex(int transition_number) {
232 : return kFirstIndex +
233 79755160 : (transition_number * kTransitionSize) +
234 79755160 : kTransitionTarget;
235 : }
236 :
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 : }
242 :
243 : // Allocates a TransitionArray.
244 : static Handle<TransitionArray> Allocate(Isolate* isolate,
245 : int number_of_transitions,
246 : int slack = 0);
247 :
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 2868077 : return SearchName(symbol, out_insertion_index);
259 : }
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 :
265 60797490 : int number_of_transitions() {
266 60797490 : if (length() < kFirstIndex) return 0;
267 60797490 : return Smi::cast(get(kTransitionLengthIndex))->value();
268 : }
269 :
270 38578052 : static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
271 38578053 : return transition->GetLastDescriptorDetails();
272 : }
273 :
274 38790520 : static inline Name* GetSimpleTransitionKey(Map* transition) {
275 : int descriptor = transition->LastAdded();
276 38790520 : 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 :
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 :
310 : inline void Set(int transition_number, Name* key, Map* target);
311 :
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);
318 :
319 : DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
320 : };
321 :
322 :
323 : } // namespace internal
324 : } // namespace v8
325 :
326 : #endif // V8_TRANSITIONS_H_
|
