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
14namespace v8 {
15namespace 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
35class 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  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
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  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           (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
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    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  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
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_
327