V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
transitions.h
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/objects.h"
11 #include "src/objects/descriptor-array.h"
12 #include "src/objects/map.h"
13 #include "src/objects/maybe-object.h"
14 #include "src/objects/name.h"
15 
16 // Has to be the last include (doesn't have include guards):
17 #include "src/objects/object-macros.h"
18 
19 namespace v8 {
20 namespace internal {
21 
22 // TransitionsAccessor is a helper class to encapsulate access to the various
23 // ways a Map can store transitions to other maps in its respective field at
24 // Map::kTransitionsOrPrototypeInfo.
25 // It caches state information internally, which becomes stale when a Map's
26 // transitions storage changes or when a GC cycle clears dead transitions;
27 // so while a TransitionsAccessor instance can be used for several read-only
28 // operations in a row (provided no GC happens between them), it must be
29 // discarded and recreated after "Insert" and "UpdateHandler" operations.
30 //
31 // Internal details: a Map's field either holds an in-place weak reference to a
32 // transition target, or a StoreIC handler for a transitioning store (which in
33 // turn points to its target map), or a TransitionArray for several target maps
34 // and/or handlers as well as prototype and ElementsKind transitions. Property
35 // details (and in case of inline target storage, the key) are retrieved from
36 // the target map's descriptor array. Stored transitions are weak in the GC
37 // sense: both single transitions stored inline and TransitionArray fields are
38 // cleared when the map they refer to is not otherwise reachable.
40  public:
42  : isolate_(isolate), map_(map) {
43  Initialize();
44  USE(no_gc);
45  }
47  : isolate_(isolate), map_handle_(map), map_(*map) {
48  Initialize();
49  }
50 
51  // Insert a new transition into |map|'s transition array, extending it
52  // as necessary.
53  // Requires the constructor that takes a Handle<Map> to have been used.
54  // This TransitionsAccessor instance is unusable after this operation.
55  void Insert(Handle<Name> name, Handle<Map> target, SimpleTransitionFlag flag);
56 
57  Map SearchTransition(Name name, PropertyKind kind,
58  PropertyAttributes attributes);
59 
60  Map SearchSpecial(Symbol name);
61  // Returns true for non-property transitions like elements kind, or
62  // or frozen/sealed transitions.
63  static bool IsSpecialTransition(ReadOnlyRoots roots, Name name);
64 
65  enum RequestedLocation { kAnyLocation, kFieldOnly };
66  MaybeHandle<Map> FindTransitionToDataProperty(
67  Handle<Name> name, RequestedLocation requested_location = kAnyLocation);
68 
69  MaybeHandle<Map> FindTransitionToField(Handle<Name> name) {
70  return FindTransitionToDataProperty(name, kFieldOnly);
71  }
72 
73  Handle<String> ExpectedTransitionKey();
74  Handle<Map> ExpectedTransitionTarget();
75 
76  int NumberOfTransitions();
77  // The size of transition arrays are limited so they do not end up in large
78  // object space. Otherwise ClearNonLiveReferences would leak memory while
79  // applying in-place right trimming.
80  static const int kMaxNumberOfTransitions = 1024 + 512;
81  bool CanHaveMoreTransitions();
82  inline Name GetKey(int transition_number);
83  inline Map GetTarget(int transition_number);
84  static inline PropertyDetails GetTargetDetails(Name name, Map target);
85 
86  static bool IsMatchingMap(Map target, Name name, PropertyKind kind,
87  PropertyAttributes attributes);
88 
89  // ===== ITERATION =====
90  typedef void (*TraverseCallback)(Map map, void* data);
91 
92  // Traverse the transition tree in postorder.
93  void TraverseTransitionTree(TraverseCallback callback, void* data) {
94  // Make sure that we do not allocate in the callback.
95  DisallowHeapAllocation no_allocation;
96  TraverseTransitionTreeInternal(callback, data, &no_allocation);
97  }
98 
99  // ===== PROTOTYPE TRANSITIONS =====
100  // When you set the prototype of an object using the __proto__ accessor you
101  // need a new map for the object (the prototype is stored in the map). In
102  // order not to multiply maps unnecessarily we store these as transitions in
103  // the original map. That way we can transition to the same map if the same
104  // prototype is set, rather than creating a new map every time. The
105  // transitions are in the form of a map where the keys are prototype objects
106  // and the values are the maps they transition to.
107  void PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map);
108  Handle<Map> GetPrototypeTransition(Handle<Object> prototype);
109 
110  // During the first-time Map::Update and Map::TryUpdate, the migration target
111  // map could be cached in the raw_transitions slot of the old map that is
112  // deprecated from the map transition tree. The next time old map is updated,
113  // we will check this cache slot as a shortcut to get the migration target
114  // map.
115  void SetMigrationTarget(Map migration_target);
116  Map GetMigrationTarget();
117 
118 #if DEBUG || OBJECT_PRINT
119  void PrintTransitions(std::ostream& os);
120  static void PrintOneTransition(std::ostream& os, Name key, Map target);
121  void PrintTransitionTree();
122  void PrintTransitionTree(std::ostream& os, int level,
123  DisallowHeapAllocation* no_gc);
124 #endif
125 #if DEBUG
126  void CheckNewTransitionsAreConsistent(TransitionArray* old_transitions,
127  Object* transitions);
128  bool IsConsistentWithBackPointers();
129  bool IsSortedNoDuplicates();
130 #endif
131 
132  protected:
133  // Allow tests to use inheritance to access internals.
134  enum Encoding {
135  kPrototypeInfo,
136  kUninitialized,
137  kMigrationTarget,
138  kWeakRef,
139  kFullTransitionArray,
140  };
141 
142  void Reload() {
143  DCHECK(!map_handle_.is_null());
144  map_ = *map_handle_;
145  Initialize();
146  }
147 
148  inline Encoding encoding() {
149  DCHECK(!needs_reload_);
150  return encoding_;
151  }
152 
153  private:
154  friend class MarkCompactCollector; // For HasSimpleTransitionTo.
155  friend class TransitionArray;
156 
157  static inline PropertyDetails GetSimpleTargetDetails(Map transition);
158 
159  static inline Name GetSimpleTransitionKey(Map transition);
160 
161  static inline Map GetTargetFromRaw(MaybeObject raw);
162 
163  void MarkNeedsReload() {
164 #if DEBUG
165  needs_reload_ = true;
166 #endif
167  }
168 
169  void Initialize();
170 
171  inline Map GetSimpleTransition();
172  bool HasSimpleTransitionTo(Map map);
173 
174  void ReplaceTransitions(MaybeObject new_transitions);
175 
176  inline Map GetTargetMapFromWeakRef();
177 
178  void EnsureHasFullTransitionArray();
179  void SetPrototypeTransitions(Handle<WeakFixedArray> proto_transitions);
180  WeakFixedArray* GetPrototypeTransitions();
181 
182  void TraverseTransitionTreeInternal(TraverseCallback callback, void* data,
183  DisallowHeapAllocation* no_gc);
184 
185  inline TransitionArray* transitions();
186 
187  Isolate* isolate_;
188  Handle<Map> map_handle_;
189  Map map_;
190  MaybeObject raw_transitions_;
191  Encoding encoding_;
192 #if DEBUG
193  bool needs_reload_;
194 #endif
195 
196  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionsAccessor);
197 };
198 
199 // TransitionArrays are fixed arrays used to hold map transitions for property,
200 // constant, and element changes.
201 // The TransitionArray class exposes a very low-level interface. Most clients
202 // should use TransitionsAccessors.
203 // TransitionArrays have the following format:
204 // [0] Link to next TransitionArray (for weak handling support) (strong ref)
205 // [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref)
206 // [2] Number of transitions (can be zero after trimming)
207 // [3] First transition key (strong ref)
208 // [4] First transition target (weak ref)
209 // ...
210 // [3 + number of transitions * kTransitionSize]: start of slack
212  public:
213  DECL_CAST(TransitionArray)
214 
215  inline WeakFixedArray* GetPrototypeTransitions();
216  inline bool HasPrototypeTransitions();
217 
218  // Accessors for fetching instance transition at transition number.
219  inline void SetKey(int transition_number, Name value);
220  inline Name GetKey(int transition_number);
221  inline HeapObjectSlot GetKeySlot(int transition_number);
222 
223  inline Map GetTarget(int transition_number);
224  inline void SetRawTarget(int transition_number, MaybeObject target);
225  inline MaybeObject GetRawTarget(int transition_number);
226  inline HeapObjectSlot GetTargetSlot(int transition_number);
227  inline bool GetTargetIfExists(int transition_number, Isolate* isolate,
228  Map* target);
229 
230  // Required for templatized Search interface.
231  static constexpr int kNotFound = -1;
232 
233  inline Name GetSortedKey(int transition_number);
234  int GetSortedKeyIndex(int transition_number) { return transition_number; }
235  inline int number_of_entries() const;
236 #ifdef DEBUG
237  bool IsSortedNoDuplicates(int valid_entries = -1);
238 #endif
239 
240  void Sort();
241 
242  void PrintInternal(std::ostream& os);
243 
244  DECL_PRINTER(TransitionArray)
245  DECL_VERIFIER(TransitionArray)
246 
247  // Layout for full transition arrays.
248  static const int kPrototypeTransitionsIndex = 0;
249  static const int kTransitionLengthIndex = 1;
250  static const int kFirstIndex = 2;
251 
252  // Layout of map transition entries in full transition arrays.
253  static const int kEntryKeyIndex = 0;
254  static const int kEntryTargetIndex = 1;
255  static const int kEntrySize = 2;
256 
257  // Conversion from transition number to array indices.
258  static int ToKeyIndex(int transition_number) {
259  return kFirstIndex + (transition_number * kEntrySize) + kEntryKeyIndex;
260  }
261 
262  static int ToTargetIndex(int transition_number) {
263  return kFirstIndex + (transition_number * kEntrySize) + kEntryTargetIndex;
264  }
265 
266  inline int SearchNameForTesting(Name name,
267  int* out_insertion_index = nullptr);
268 
269  private:
270  friend class Factory;
271  friend class MarkCompactCollector;
272  friend class TransitionsAccessor;
273 
274  inline void SetNumberOfTransitions(int number_of_transitions);
275 
276  inline int Capacity();
277 
278  // ===== PROTOTYPE TRANSITIONS =====
279  // Cache format:
280  // 0: finger - index of the first free cell in the cache
281  // 1 + i: target map
282  static const int kProtoTransitionHeaderSize = 1;
283  static const int kMaxCachedPrototypeTransitions = 256;
284 
285  inline void SetPrototypeTransitions(WeakFixedArray* prototype_transitions);
286 
287  static inline int NumberOfPrototypeTransitions(
288  WeakFixedArray* proto_transitions);
289  static void SetNumberOfPrototypeTransitions(WeakFixedArray* proto_transitions,
290  int value);
291 
292  static const int kProtoTransitionNumberOfEntriesOffset = 0;
293  STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
294 
295  // Returns the fixed array length required to hold number_of_transitions
296  // transitions.
297  static int LengthFor(int number_of_transitions) {
298  return ToKeyIndex(number_of_transitions);
299  }
300 
301  // Search a transition for a given kind, property name and attributes.
302  int Search(PropertyKind kind, Name name, PropertyAttributes attributes,
303  int* out_insertion_index = nullptr);
304 
305  // Search a non-property transition (like elements kind, observe or frozen
306  // transitions).
307  inline int SearchSpecial(Symbol symbol, int* out_insertion_index = nullptr);
308  // Search a first transition for a given property name.
309  inline int SearchName(Name name, int* out_insertion_index = nullptr);
310  int SearchDetails(int transition, PropertyKind kind,
311  PropertyAttributes attributes, int* out_insertion_index);
312 
313  inline int number_of_transitions() const;
314 
315  static bool CompactPrototypeTransitionArray(Isolate* isolate,
316  WeakFixedArray* array);
317 
318  static Handle<WeakFixedArray> GrowPrototypeTransitionArray(
319  Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate);
320 
321  // Compares two tuples <key, kind, attributes>, returns -1 if
322  // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
323  static inline int CompareKeys(Name key1, uint32_t hash1, PropertyKind kind1,
324  PropertyAttributes attributes1, Name key2,
325  uint32_t hash2, PropertyKind kind2,
326  PropertyAttributes attributes2);
327 
328  // Compares keys, returns -1 if key1 is "less" than key2,
329  // 0 if key1 equal to key2 and 1 otherwise.
330  static inline int CompareNames(Name key1, uint32_t hash1, Name key2,
331  uint32_t hash2);
332 
333  // Compares two details, returns -1 if details1 is "less" than details2,
334  // 0 if details1 equal to details2 and 1 otherwise.
335  static inline int CompareDetails(PropertyKind kind1,
336  PropertyAttributes attributes1,
337  PropertyKind kind2,
338  PropertyAttributes attributes2);
339 
340  inline void Set(int transition_number, Name key, MaybeObject target);
341 
342  void Zap(Isolate* isolate);
343 
344  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
345 };
346 
347 } // namespace internal
348 } // namespace v8
349 
350 #include "src/objects/object-macros-undef.h"
351 
352 #endif // V8_TRANSITIONS_H_
Definition: libplatform.h:13
Definition: v8.h:3740