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
19namespace v8 {
20namespace 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.
39class V8_EXPORT_PRIVATE TransitionsAccessor {
40 public:
41 TransitionsAccessor(Isolate* isolate, Map map, DisallowHeapAllocation* no_gc)
42 : isolate_(isolate), map_(map) {
43 Initialize();
44 USE(no_gc);
45 }
46 TransitionsAccessor(Isolate* isolate, Handle<Map> map)
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 bool HasIntegrityLevelTransitionTo(
90 Map to, Symbol* out_symbol = nullptr,
91 PropertyAttributes* out_integrity_level = nullptr);
92
93 // ===== ITERATION =====
94 typedef void (*TraverseCallback)(Map map, void* data);
95
96 // Traverse the transition tree in postorder.
97 void TraverseTransitionTree(TraverseCallback callback, void* data) {
98 // Make sure that we do not allocate in the callback.
99 DisallowHeapAllocation no_allocation;
100 TraverseTransitionTreeInternal(callback, data, &no_allocation);
101 }
102
103 // ===== PROTOTYPE TRANSITIONS =====
104 // When you set the prototype of an object using the __proto__ accessor you
105 // need a new map for the object (the prototype is stored in the map). In
106 // order not to multiply maps unnecessarily we store these as transitions in
107 // the original map. That way we can transition to the same map if the same
108 // prototype is set, rather than creating a new map every time. The
109 // transitions are in the form of a map where the keys are prototype objects
110 // and the values are the maps they transition to.
111 void PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map);
112 Handle<Map> GetPrototypeTransition(Handle<Object> prototype);
113
114 // During the first-time Map::Update and Map::TryUpdate, the migration target
115 // map could be cached in the raw_transitions slot of the old map that is
116 // deprecated from the map transition tree. The next time old map is updated,
117 // we will check this cache slot as a shortcut to get the migration target
118 // map.
119 void SetMigrationTarget(Map migration_target);
120 Map GetMigrationTarget();
121
122#if DEBUG || OBJECT_PRINT
123 void PrintTransitions(std::ostream& os);
124 static void PrintOneTransition(std::ostream& os, Name key, Map target);
125 void PrintTransitionTree();
126 void PrintTransitionTree(std::ostream& os, int level,
127 DisallowHeapAllocation* no_gc);
128#endif
129#if DEBUG
130 void CheckNewTransitionsAreConsistent(TransitionArray old_transitions,
131 Object transitions);
132 bool IsConsistentWithBackPointers();
133 bool IsSortedNoDuplicates();
134#endif
135
136 protected:
137 // Allow tests to use inheritance to access internals.
138 enum Encoding {
139 kPrototypeInfo,
140 kUninitialized,
141 kMigrationTarget,
142 kWeakRef,
143 kFullTransitionArray,
144 };
145
146 void Reload() {
147 DCHECK(!map_handle_.is_null());
148 map_ = *map_handle_;
149 Initialize();
150 }
151
152 inline Encoding encoding() {
153 DCHECK(!needs_reload_);
154 return encoding_;
155 }
156
157 private:
158 friend class MarkCompactCollector; // For HasSimpleTransitionTo.
159 friend class TransitionArray;
160
161 static inline PropertyDetails GetSimpleTargetDetails(Map transition);
162
163 static inline Name GetSimpleTransitionKey(Map transition);
164
165 static inline Map GetTargetFromRaw(MaybeObject raw);
166
167 void MarkNeedsReload() {
168#if DEBUG
169 needs_reload_ = true;
170#endif
171 }
172
173 void Initialize();
174
175 inline Map GetSimpleTransition();
176 bool HasSimpleTransitionTo(Map map);
177
178 void ReplaceTransitions(MaybeObject new_transitions);
179
180 inline Map GetTargetMapFromWeakRef();
181
182 void EnsureHasFullTransitionArray();
183 void SetPrototypeTransitions(Handle<WeakFixedArray> proto_transitions);
184 WeakFixedArray GetPrototypeTransitions();
185
186 void TraverseTransitionTreeInternal(TraverseCallback callback, void* data,
187 DisallowHeapAllocation* no_gc);
188
189 inline TransitionArray transitions();
190
191 Isolate* isolate_;
192 Handle<Map> map_handle_;
193 Map map_;
194 MaybeObject raw_transitions_;
195 Encoding encoding_;
196#if DEBUG
197 bool needs_reload_;
198#endif
199
200 DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionsAccessor);
201};
202
203// TransitionArrays are fixed arrays used to hold map transitions for property,
204// constant, and element changes.
205// The TransitionArray class exposes a very low-level interface. Most clients
206// should use TransitionsAccessors.
207// TransitionArrays have the following format:
208// [0] Link to next TransitionArray (for weak handling support) (strong ref)
209// [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref)
210// [2] Number of transitions (can be zero after trimming)
211// [3] First transition key (strong ref)
212// [4] First transition target (weak ref)
213// ...
214// [3 + number of transitions * kTransitionSize]: start of slack
215class TransitionArray : public WeakFixedArray {
216 public:
217 DECL_CAST(TransitionArray)
218
219 inline WeakFixedArray GetPrototypeTransitions();
220 inline bool HasPrototypeTransitions();
221
222 // Accessors for fetching instance transition at transition number.
223 inline void SetKey(int transition_number, Name value);
224 inline Name GetKey(int transition_number);
225 inline HeapObjectSlot GetKeySlot(int transition_number);
226
227 inline Map GetTarget(int transition_number);
228 inline void SetRawTarget(int transition_number, MaybeObject target);
229 inline MaybeObject GetRawTarget(int transition_number);
230 inline HeapObjectSlot GetTargetSlot(int transition_number);
231 inline bool GetTargetIfExists(int transition_number, Isolate* isolate,
232 Map* target);
233
234 // Required for templatized Search interface.
235 static constexpr int kNotFound = -1;
236
237 inline Name GetSortedKey(int transition_number);
238 int GetSortedKeyIndex(int transition_number) { return transition_number; }
239 inline int number_of_entries() const;
240#ifdef DEBUG
241 V8_EXPORT_PRIVATE bool IsSortedNoDuplicates(int valid_entries = -1);
242#endif
243
244 void Sort();
245
246 void PrintInternal(std::ostream& os);
247
248 DECL_PRINTER(TransitionArray)
249 DECL_VERIFIER(TransitionArray)
250
251 // Layout for full transition arrays.
252 static const int kPrototypeTransitionsIndex = 0;
253 static const int kTransitionLengthIndex = 1;
254 static const int kFirstIndex = 2;
255
256 // Layout of map transition entries in full transition arrays.
257 static const int kEntryKeyIndex = 0;
258 static const int kEntryTargetIndex = 1;
259 static const int kEntrySize = 2;
260
261 // Conversion from transition number to array indices.
262 static int ToKeyIndex(int transition_number) {
263 return kFirstIndex + (transition_number * kEntrySize) + kEntryKeyIndex;
264 }
265
266 static int ToTargetIndex(int transition_number) {
267 return kFirstIndex + (transition_number * kEntrySize) + kEntryTargetIndex;
268 }
269
270 inline int SearchNameForTesting(Name name,
271 int* out_insertion_index = nullptr);
272
273 private:
274 friend class Factory;
275 friend class MarkCompactCollector;
276 friend class TransitionsAccessor;
277
278 inline void SetNumberOfTransitions(int number_of_transitions);
279
280 inline int Capacity();
281
282 // ===== PROTOTYPE TRANSITIONS =====
283 // Cache format:
284 // 0: finger - index of the first free cell in the cache
285 // 1 + i: target map
286 static const int kProtoTransitionHeaderSize = 1;
287 static const int kMaxCachedPrototypeTransitions = 256;
288
289 inline void SetPrototypeTransitions(WeakFixedArray prototype_transitions);
290
291 static inline int NumberOfPrototypeTransitions(
292 WeakFixedArray proto_transitions);
293 static void SetNumberOfPrototypeTransitions(WeakFixedArray proto_transitions,
294 int value);
295
296 static const int kProtoTransitionNumberOfEntriesOffset = 0;
297 STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
298
299 // Returns the fixed array length required to hold number_of_transitions
300 // transitions.
301 static int LengthFor(int number_of_transitions) {
302 return ToKeyIndex(number_of_transitions);
303 }
304
305 // Search a transition for a given kind, property name and attributes.
306 int Search(PropertyKind kind, Name name, PropertyAttributes attributes,
307 int* out_insertion_index = nullptr);
308
309 Map SearchAndGetTarget(PropertyKind kind, Name name,
310 PropertyAttributes attributes);
311
312 // Search a non-property transition (like elements kind, observe or frozen
313 // transitions).
314 inline int SearchSpecial(Symbol symbol, int* out_insertion_index = nullptr);
315 // Search a first transition for a given property name.
316 inline int SearchName(Name name, int* out_insertion_index = nullptr);
317 int SearchDetails(int transition, PropertyKind kind,
318 PropertyAttributes attributes, int* out_insertion_index);
319 Map SearchDetailsAndGetTarget(int transition, PropertyKind kind,
320 PropertyAttributes attributes);
321
322 inline int number_of_transitions() const;
323
324 static bool CompactPrototypeTransitionArray(Isolate* isolate,
325 WeakFixedArray array);
326
327 static Handle<WeakFixedArray> GrowPrototypeTransitionArray(
328 Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate);
329
330 // Compares two tuples <key, kind, attributes>, returns -1 if
331 // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
332 static inline int CompareKeys(Name key1, uint32_t hash1, PropertyKind kind1,
333 PropertyAttributes attributes1, Name key2,
334 uint32_t hash2, PropertyKind kind2,
335 PropertyAttributes attributes2);
336
337 // Compares keys, returns -1 if key1 is "less" than key2,
338 // 0 if key1 equal to key2 and 1 otherwise.
339 static inline int CompareNames(Name key1, uint32_t hash1, Name key2,
340 uint32_t hash2);
341
342 // Compares two details, returns -1 if details1 is "less" than details2,
343 // 0 if details1 equal to details2 and 1 otherwise.
344 static inline int CompareDetails(PropertyKind kind1,
345 PropertyAttributes attributes1,
346 PropertyKind kind2,
347 PropertyAttributes attributes2);
348
349 inline void Set(int transition_number, Name key, MaybeObject target);
350
351 void Zap(Isolate* isolate);
352
353 OBJECT_CONSTRUCTORS(TransitionArray, WeakFixedArray);
354};
355
356} // namespace internal
357} // namespace v8
358
359#include "src/objects/object-macros-undef.h"
360
361#endif // V8_TRANSITIONS_H_
362