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 #include "src/objects/transitions.h"
6
7 #include "src/base/small-vector.h"
8 #include "src/objects/objects-inl.h"
9 #include "src/objects/transitions-inl.h"
10 #include "src/utils/utils.h"
11
12 namespace v8 {
13 namespace internal {
14
15 // static
GetSimpleTransition(Isolate * isolate,Handle<Map> map)16 Map TransitionsAccessor::GetSimpleTransition(Isolate* isolate,
17 Handle<Map> map) {
18 MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
19 switch (GetEncoding(isolate, raw_transitions)) {
20 case kWeakRef:
21 return Map::cast(raw_transitions->GetHeapObjectAssumeWeak());
22 default:
23 return Map();
24 }
25 }
26
HasSimpleTransitionTo(Map map)27 bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
28 switch (encoding()) {
29 case kWeakRef:
30 return raw_transitions_->GetHeapObjectAssumeWeak() == map;
31 case kPrototypeInfo:
32 case kUninitialized:
33 case kMigrationTarget:
34 case kFullTransitionArray:
35 return false;
36 }
37 UNREACHABLE();
38 }
39
40 // static
Insert(Isolate * isolate,Handle<Map> map,Handle<Name> name,Handle<Map> target,SimpleTransitionFlag flag)41 void TransitionsAccessor::Insert(Isolate* isolate, Handle<Map> map,
42 Handle<Name> name, Handle<Map> target,
43 SimpleTransitionFlag flag) {
44 Encoding encoding = GetEncoding(isolate, map);
45 DCHECK_NE(kPrototypeInfo, encoding);
46 target->SetBackPointer(*map);
47
48 // If the map doesn't have any transitions at all yet, install the new one.
49 if (encoding == kUninitialized || encoding == kMigrationTarget) {
50 if (flag == SIMPLE_PROPERTY_TRANSITION) {
51 ReplaceTransitions(isolate, map, HeapObjectReference::Weak(*target));
52 return;
53 }
54 // If the flag requires a full TransitionArray, allocate one.
55 Handle<TransitionArray> result =
56 isolate->factory()->NewTransitionArray(1, 0);
57 result->Set(0, *name, HeapObjectReference::Weak(*target));
58 ReplaceTransitions(isolate, map, result);
59 DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
60 return;
61 }
62
63 if (encoding == kWeakRef) {
64 Map simple_transition = GetSimpleTransition(isolate, map);
65 DCHECK(!simple_transition.is_null());
66
67 if (flag == SIMPLE_PROPERTY_TRANSITION) {
68 Name key = GetSimpleTransitionKey(simple_transition);
69 PropertyDetails old_details =
70 simple_transition.GetLastDescriptorDetails(isolate);
71 PropertyDetails new_details = GetTargetDetails(*name, *target);
72 if (key.Equals(*name) && old_details.kind() == new_details.kind() &&
73 old_details.attributes() == new_details.attributes()) {
74 ReplaceTransitions(isolate, map, HeapObjectReference::Weak(*target));
75 return;
76 }
77 }
78
79 // Otherwise allocate a full TransitionArray with slack for a new entry.
80 Handle<TransitionArray> result =
81 isolate->factory()->NewTransitionArray(1, 1);
82
83 // Reload `simple_transition`. Allocations might have caused it to be
84 // cleared.
85 simple_transition = GetSimpleTransition(isolate, map);
86 if (simple_transition.is_null()) {
87 result->Set(0, *name, HeapObjectReference::Weak(*target));
88 ReplaceTransitions(isolate, map, result);
89 DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
90 return;
91 }
92
93 // Insert the original transition in index 0.
94 result->Set(0, GetSimpleTransitionKey(simple_transition),
95 HeapObjectReference::Weak(simple_transition));
96
97 // Search for the correct index to insert the new transition.
98 int insertion_index;
99 int index;
100 if (flag == SPECIAL_TRANSITION) {
101 index =
102 result->SearchSpecial(Symbol::cast(*name), false, &insertion_index);
103 } else {
104 PropertyDetails details = GetTargetDetails(*name, *target);
105 index = result->Search(details.kind(), *name, details.attributes(),
106 &insertion_index);
107 }
108 DCHECK_EQ(index, kNotFound);
109 USE(index);
110
111 result->SetNumberOfTransitions(2);
112 if (insertion_index == 0) {
113 // If the new transition will be inserted in index 0, move the original
114 // transition to index 1.
115 result->Set(1, GetSimpleTransitionKey(simple_transition),
116 HeapObjectReference::Weak(simple_transition));
117 }
118 result->SetKey(insertion_index, *name);
119 result->SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));
120
121 SLOW_DCHECK(result->IsSortedNoDuplicates());
122 ReplaceTransitions(isolate, map, result);
123 DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
124 return;
125 }
126
127 // At this point, we know that the map has a full TransitionArray.
128 DCHECK_EQ(kFullTransitionArray, encoding);
129
130 int number_of_transitions = 0;
131 int new_nof = 0;
132 int insertion_index = kNotFound;
133 const bool is_special_transition = flag == SPECIAL_TRANSITION;
134 DCHECK_EQ(is_special_transition,
135 IsSpecialTransition(ReadOnlyRoots(isolate), *name));
136 PropertyDetails details = is_special_transition
137 ? PropertyDetails::Empty()
138 : GetTargetDetails(*name, *target);
139
140 {
141 DisallowGarbageCollection no_gc;
142 TransitionArray array = GetTransitionArray(isolate, map);
143 number_of_transitions = array.number_of_transitions();
144
145 int index =
146 is_special_transition
147 ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
148 : array.Search(details.kind(), *name, details.attributes(),
149 &insertion_index);
150 // If an existing entry was found, overwrite it and return.
151 if (index != kNotFound) {
152 base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
153 isolate->full_transition_array_access());
154 array.SetRawTarget(index, HeapObjectReference::Weak(*target));
155 return;
156 }
157
158 new_nof = number_of_transitions + 1;
159 CHECK_LE(new_nof, kMaxNumberOfTransitions);
160 DCHECK_GE(insertion_index, 0);
161 DCHECK_LE(insertion_index, number_of_transitions);
162
163 // If there is enough capacity, insert new entry into the existing array.
164 if (new_nof <= array.Capacity()) {
165 base::SharedMutexGuard<base::kExclusive> shared_mutex_guard(
166 isolate->full_transition_array_access());
167 array.SetNumberOfTransitions(new_nof);
168 for (int i = number_of_transitions; i > insertion_index; --i) {
169 array.SetKey(i, array.GetKey(i - 1));
170 array.SetRawTarget(i, array.GetRawTarget(i - 1));
171 }
172 array.SetKey(insertion_index, *name);
173 array.SetRawTarget(insertion_index, HeapObjectReference::Weak(*target));
174 SLOW_DCHECK(array.IsSortedNoDuplicates());
175 return;
176 }
177 }
178
179 // We're gonna need a bigger TransitionArray.
180 Handle<TransitionArray> result = isolate->factory()->NewTransitionArray(
181 new_nof,
182 Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
183
184 // The map's transition array may have shrunk during the allocation above as
185 // it was weakly traversed, though it is guaranteed not to disappear. Trim the
186 // result copy if needed, and recompute variables.
187 DisallowGarbageCollection no_gc;
188 TransitionArray array = GetTransitionArray(isolate, map);
189 if (array.number_of_transitions() != number_of_transitions) {
190 DCHECK_LT(array.number_of_transitions(), number_of_transitions);
191
192 int index =
193 is_special_transition
194 ? array.SearchSpecial(Symbol::cast(*name), false, &insertion_index)
195 : array.Search(details.kind(), *name, details.attributes(),
196 &insertion_index);
197 CHECK_EQ(index, kNotFound);
198 USE(index);
199 DCHECK_GE(insertion_index, 0);
200 DCHECK_LE(insertion_index, number_of_transitions);
201
202 number_of_transitions = array.number_of_transitions();
203 new_nof = number_of_transitions + 1;
204 result->SetNumberOfTransitions(new_nof);
205 }
206
207 if (array.HasPrototypeTransitions()) {
208 result->SetPrototypeTransitions(array.GetPrototypeTransitions());
209 }
210
211 DCHECK_NE(kNotFound, insertion_index);
212 for (int i = 0; i < insertion_index; ++i) {
213 result->Set(i, array.GetKey(i), array.GetRawTarget(i));
214 }
215 result->Set(insertion_index, *name, HeapObjectReference::Weak(*target));
216 for (int i = insertion_index; i < number_of_transitions; ++i) {
217 result->Set(i + 1, array.GetKey(i), array.GetRawTarget(i));
218 }
219
220 SLOW_DCHECK(result->IsSortedNoDuplicates());
221 ReplaceTransitions(isolate, map, result);
222 }
223
SearchTransition(Name name,PropertyKind kind,PropertyAttributes attributes)224 Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
225 PropertyAttributes attributes) {
226 DCHECK(name.IsUniqueName());
227 switch (encoding()) {
228 case kPrototypeInfo:
229 case kUninitialized:
230 case kMigrationTarget:
231 return Map();
232 case kWeakRef: {
233 Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
234 if (!IsMatchingMap(map, name, kind, attributes)) return Map();
235 return map;
236 }
237 case kFullTransitionArray: {
238 base::SharedMutexGuardIf<base::kShared> scope(
239 isolate_->full_transition_array_access(), concurrent_access_);
240 return transitions().SearchAndGetTarget(kind, name, attributes);
241 }
242 }
243 UNREACHABLE();
244 }
245
SearchSpecial(Symbol name)246 Map TransitionsAccessor::SearchSpecial(Symbol name) {
247 if (encoding() != kFullTransitionArray) return Map();
248 base::SharedMutexGuardIf<base::kShared> scope(
249 isolate_->full_transition_array_access(), concurrent_access_);
250 int transition = transitions().SearchSpecial(name, concurrent_access_);
251 if (transition == kNotFound) return Map();
252 return transitions().GetTarget(transition);
253 }
254
255 // static
IsSpecialTransition(ReadOnlyRoots roots,Name name)256 bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
257 if (!name.IsSymbol()) return false;
258 return name == roots.nonextensible_symbol() ||
259 name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
260 name == roots.elements_transition_symbol() ||
261 name == roots.strict_function_transition_symbol();
262 }
263
FindTransitionToDataProperty(Handle<Name> name,RequestedLocation requested_location)264 MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
265 Handle<Name> name, RequestedLocation requested_location) {
266 DCHECK(name->IsUniqueName());
267 DisallowGarbageCollection no_gc;
268 PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
269 Map target = SearchTransition(*name, PropertyKind::kData, attributes);
270 if (target.is_null()) return MaybeHandle<Map>();
271 PropertyDetails details = target.GetLastDescriptorDetails(isolate_);
272 DCHECK_EQ(attributes, details.attributes());
273 DCHECK_EQ(PropertyKind::kData, details.kind());
274 if (requested_location == kFieldOnly &&
275 details.location() != PropertyLocation::kField) {
276 return MaybeHandle<Map>();
277 }
278 return Handle<Map>(target, isolate_);
279 }
280
ForEachTransitionTo(Name name,const ForEachTransitionCallback & callback,DisallowGarbageCollection * no_gc)281 void TransitionsAccessor::ForEachTransitionTo(
282 Name name, const ForEachTransitionCallback& callback,
283 DisallowGarbageCollection* no_gc) {
284 DCHECK(name.IsUniqueName());
285 switch (encoding()) {
286 case kPrototypeInfo:
287 case kUninitialized:
288 case kMigrationTarget:
289 return;
290 case kWeakRef: {
291 Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
292 InternalIndex descriptor = target.LastAdded();
293 DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
294 Name key = descriptors.GetKey(descriptor);
295 if (key == name) {
296 callback(target);
297 }
298 return;
299 }
300 case kFullTransitionArray: {
301 base::SharedMutexGuardIf<base::kShared> scope(
302 isolate_->full_transition_array_access(), concurrent_access_);
303 return transitions().ForEachTransitionTo(name, callback);
304 }
305 }
306 UNREACHABLE();
307 }
308
309 // static
CanHaveMoreTransitions(Isolate * isolate,Handle<Map> map)310 bool TransitionsAccessor::CanHaveMoreTransitions(Isolate* isolate,
311 Handle<Map> map) {
312 if (map->is_dictionary_map()) return false;
313 MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
314 if (GetEncoding(isolate, raw_transitions) == kFullTransitionArray) {
315 return GetTransitionArray(isolate, raw_transitions)
316 .number_of_transitions() < kMaxNumberOfTransitions;
317 }
318 return true;
319 }
320
321 // static
IsMatchingMap(Map target,Name name,PropertyKind kind,PropertyAttributes attributes)322 bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
323 PropertyKind kind,
324 PropertyAttributes attributes) {
325 InternalIndex descriptor = target.LastAdded();
326 DescriptorArray descriptors = target.instance_descriptors(kRelaxedLoad);
327 Name key = descriptors.GetKey(descriptor);
328 if (key != name) return false;
329 return descriptors.GetDetails(descriptor)
330 .HasKindAndAttributes(kind, attributes);
331 }
332
333 // static
CompactPrototypeTransitionArray(Isolate * isolate,WeakFixedArray array)334 bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
335 WeakFixedArray array) {
336 const int header = kProtoTransitionHeaderSize;
337 int number_of_transitions = NumberOfPrototypeTransitions(array);
338 if (number_of_transitions == 0) {
339 // Empty array cannot be compacted.
340 return false;
341 }
342 int new_number_of_transitions = 0;
343 for (int i = 0; i < number_of_transitions; i++) {
344 MaybeObject target = array.Get(header + i);
345 DCHECK(target->IsCleared() ||
346 (target->IsWeak() && target->GetHeapObject().IsMap()));
347 if (!target->IsCleared()) {
348 if (new_number_of_transitions != i) {
349 array.Set(header + new_number_of_transitions, target);
350 }
351 new_number_of_transitions++;
352 }
353 }
354 // Fill slots that became free with undefined value.
355 MaybeObject undefined =
356 MaybeObject::FromObject(*isolate->factory()->undefined_value());
357 for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
358 array.Set(header + i, undefined);
359 }
360 if (number_of_transitions != new_number_of_transitions) {
361 SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
362 }
363 return new_number_of_transitions < number_of_transitions;
364 }
365
366 // static
GrowPrototypeTransitionArray(Handle<WeakFixedArray> array,int new_capacity,Isolate * isolate)367 Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
368 Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate) {
369 // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
370 int capacity = array->length() - kProtoTransitionHeaderSize;
371 new_capacity = std::min({kMaxCachedPrototypeTransitions, new_capacity});
372 DCHECK_GT(new_capacity, capacity);
373 int grow_by = new_capacity - capacity;
374 array = isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by);
375 if (capacity < 0) {
376 // There was no prototype transitions array before, so the size
377 // couldn't be copied. Initialize it explicitly.
378 SetNumberOfPrototypeTransitions(*array, 0);
379 }
380 return array;
381 }
382
383 // static
PutPrototypeTransition(Isolate * isolate,Handle<Map> map,Handle<Object> prototype,Handle<Map> target_map)384 void TransitionsAccessor::PutPrototypeTransition(Isolate* isolate,
385 Handle<Map> map,
386 Handle<Object> prototype,
387 Handle<Map> target_map) {
388 DCHECK(HeapObject::cast(*prototype).map().IsMap());
389 // Don't cache prototype transition if this map is either shared, or a map of
390 // a prototype.
391 if (map->is_prototype_map()) return;
392 if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
393
394 const int header = TransitionArray::kProtoTransitionHeaderSize;
395
396 Handle<WeakFixedArray> cache(GetPrototypeTransitions(isolate, map), isolate);
397 int capacity = cache->length() - header;
398 int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
399
400 base::SharedMutexGuard<base::kExclusive> scope(
401 isolate->full_transition_array_access());
402
403 if (transitions > capacity) {
404 // Grow the array if compacting it doesn't free space.
405 if (!TransitionArray::CompactPrototypeTransitionArray(isolate, *cache)) {
406 if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return;
407 cache = TransitionArray::GrowPrototypeTransitionArray(
408 cache, 2 * transitions, isolate);
409 SetPrototypeTransitions(isolate, map, cache);
410 }
411 }
412
413 // Reload number of transitions as they might have been compacted.
414 int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
415 int entry = header + last;
416
417 cache->Set(entry, HeapObjectReference::Weak(*target_map));
418 TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
419 }
420
421 // static
GetPrototypeTransition(Isolate * isolate,Handle<Map> map,Handle<Object> prototype)422 Handle<Map> TransitionsAccessor::GetPrototypeTransition(
423 Isolate* isolate, Handle<Map> map, Handle<Object> prototype) {
424 DisallowGarbageCollection no_gc;
425 WeakFixedArray cache = GetPrototypeTransitions(isolate, map);
426 int length = TransitionArray::NumberOfPrototypeTransitions(cache);
427 for (int i = 0; i < length; i++) {
428 MaybeObject target =
429 cache.Get(TransitionArray::kProtoTransitionHeaderSize + i);
430 DCHECK(target->IsWeakOrCleared());
431 HeapObject heap_object;
432 if (target->GetHeapObjectIfWeak(&heap_object)) {
433 Map target_map = Map::cast(heap_object);
434 if (target_map.prototype() == *prototype) {
435 return handle(target_map, isolate);
436 }
437 }
438 }
439 return Handle<Map>();
440 }
441
442 // static
GetPrototypeTransitions(Isolate * isolate,Handle<Map> map)443 WeakFixedArray TransitionsAccessor::GetPrototypeTransitions(Isolate* isolate,
444 Handle<Map> map) {
445 MaybeObject raw_transitions = map->raw_transitions(isolate, kAcquireLoad);
446 if (GetEncoding(isolate, raw_transitions) != kFullTransitionArray) {
447 return ReadOnlyRoots(isolate).empty_weak_fixed_array();
448 }
449 TransitionArray transition_array =
450 GetTransitionArray(isolate, raw_transitions);
451 if (!transition_array.HasPrototypeTransitions()) {
452 return ReadOnlyRoots(isolate).empty_weak_fixed_array();
453 }
454 return transition_array.GetPrototypeTransitions();
455 }
456
457 // static
SetNumberOfPrototypeTransitions(WeakFixedArray proto_transitions,int value)458 void TransitionArray::SetNumberOfPrototypeTransitions(
459 WeakFixedArray proto_transitions, int value) {
460 DCHECK_NE(proto_transitions.length(), 0);
461 proto_transitions.Set(kProtoTransitionNumberOfEntriesOffset,
462 MaybeObject::FromSmi(Smi::FromInt(value)));
463 }
464
NumberOfTransitions()465 int TransitionsAccessor::NumberOfTransitions() {
466 switch (encoding()) {
467 case kPrototypeInfo:
468 case kUninitialized:
469 case kMigrationTarget:
470 return 0;
471 case kWeakRef:
472 return 1;
473 case kFullTransitionArray:
474 return transitions().number_of_transitions();
475 }
476 UNREACHABLE();
477 }
478
479 // static
SetMigrationTarget(Isolate * isolate,Handle<Map> map,Map migration_target)480 void TransitionsAccessor::SetMigrationTarget(Isolate* isolate, Handle<Map> map,
481 Map migration_target) {
482 // We only cache the migration target for maps with empty transitions for GC's
483 // sake.
484 if (GetEncoding(isolate, map) != kUninitialized) return;
485 DCHECK(map->is_deprecated());
486 map->set_raw_transitions(MaybeObject::FromObject(migration_target),
487 kReleaseStore);
488 }
489
GetMigrationTarget()490 Map TransitionsAccessor::GetMigrationTarget() {
491 if (encoding() == kMigrationTarget) {
492 return map_.raw_transitions(kAcquireLoad)->cast<Map>();
493 }
494 return Map();
495 }
496
497 // static
ReplaceTransitions(Isolate * isolate,Handle<Map> map,MaybeObject new_transitions)498 void TransitionsAccessor::ReplaceTransitions(Isolate* isolate, Handle<Map> map,
499 MaybeObject new_transitions) {
500 #if DEBUG
501 if (GetEncoding(isolate, map) == kFullTransitionArray) {
502 CheckNewTransitionsAreConsistent(
503 isolate, map, new_transitions->GetHeapObjectAssumeStrong());
504 DCHECK_NE(GetTransitionArray(isolate, map),
505 new_transitions->GetHeapObjectAssumeStrong());
506 }
507 #endif
508 map->set_raw_transitions(new_transitions, kReleaseStore);
509 USE(isolate);
510 }
511
512 // static
ReplaceTransitions(Isolate * isolate,Handle<Map> map,Handle<TransitionArray> new_transitions)513 void TransitionsAccessor::ReplaceTransitions(
514 Isolate* isolate, Handle<Map> map,
515 Handle<TransitionArray> new_transitions) {
516 ReplaceTransitions(isolate, map, MaybeObject::FromObject(*new_transitions));
517 }
518
519 // static
SetPrototypeTransitions(Isolate * isolate,Handle<Map> map,Handle<WeakFixedArray> proto_transitions)520 void TransitionsAccessor::SetPrototypeTransitions(
521 Isolate* isolate, Handle<Map> map,
522 Handle<WeakFixedArray> proto_transitions) {
523 EnsureHasFullTransitionArray(isolate, map);
524 GetTransitionArray(isolate, map->raw_transitions(isolate, kAcquireLoad))
525 .SetPrototypeTransitions(*proto_transitions);
526 }
527
528 // static
EnsureHasFullTransitionArray(Isolate * isolate,Handle<Map> map)529 void TransitionsAccessor::EnsureHasFullTransitionArray(Isolate* isolate,
530 Handle<Map> map) {
531 Encoding encoding =
532 GetEncoding(isolate, map->raw_transitions(isolate, kAcquireLoad));
533 if (encoding == kFullTransitionArray) return;
534 int nof =
535 (encoding == kUninitialized || encoding == kMigrationTarget) ? 0 : 1;
536 Handle<TransitionArray> result = isolate->factory()->NewTransitionArray(nof);
537 // Reload encoding after possible GC.
538 encoding = GetEncoding(isolate, map->raw_transitions(isolate, kAcquireLoad));
539 if (nof == 1) {
540 if (encoding == kUninitialized) {
541 // If allocation caused GC and cleared the target, trim the new array.
542 result->SetNumberOfTransitions(0);
543 } else {
544 // Otherwise populate the new array.
545 Map target = GetSimpleTransition(isolate, map);
546 Name key = GetSimpleTransitionKey(target);
547 result->Set(0, key, HeapObjectReference::Weak(target));
548 }
549 }
550 ReplaceTransitions(isolate, map, result);
551 }
552
TraverseTransitionTreeInternal(const TraverseCallback & callback,DisallowGarbageCollection * no_gc)553 void TransitionsAccessor::TraverseTransitionTreeInternal(
554 const TraverseCallback& callback, DisallowGarbageCollection* no_gc) {
555 // Mostly arbitrary but more than enough to run the test suite in static
556 // memory.
557 static constexpr int kStaticStackSize = 16;
558 base::SmallVector<Map, kStaticStackSize> stack;
559 stack.emplace_back(map_);
560
561 // Pre-order iterative depth-first-search.
562 while (!stack.empty()) {
563 Map current_map = stack.back();
564 stack.pop_back();
565
566 callback(current_map);
567
568 MaybeObject raw_transitions =
569 current_map.raw_transitions(isolate_, kAcquireLoad);
570 Encoding encoding = GetEncoding(isolate_, raw_transitions);
571
572 switch (encoding) {
573 case kPrototypeInfo:
574 case kUninitialized:
575 case kMigrationTarget:
576 break;
577 case kWeakRef: {
578 stack.emplace_back(
579 Map::cast(raw_transitions->GetHeapObjectAssumeWeak()));
580 break;
581 }
582 case kFullTransitionArray: {
583 TransitionArray transitions =
584 TransitionArray::cast(raw_transitions->GetHeapObjectAssumeStrong());
585 if (transitions.HasPrototypeTransitions()) {
586 WeakFixedArray proto_trans = transitions.GetPrototypeTransitions();
587 int length =
588 TransitionArray::NumberOfPrototypeTransitions(proto_trans);
589 for (int i = 0; i < length; ++i) {
590 int index = TransitionArray::kProtoTransitionHeaderSize + i;
591 MaybeObject target = proto_trans.Get(index);
592 HeapObject heap_object;
593 if (target->GetHeapObjectIfWeak(&heap_object)) {
594 stack.emplace_back(Map::cast(heap_object));
595 } else {
596 DCHECK(target->IsCleared());
597 }
598 }
599 }
600 for (int i = 0; i < transitions.number_of_transitions(); ++i) {
601 stack.emplace_back(transitions.GetTarget(i));
602 }
603 break;
604 }
605 }
606 }
607 }
608
609 #ifdef DEBUG
610 // static
CheckNewTransitionsAreConsistent(Isolate * isolate,Handle<Map> map,Object transitions)611 void TransitionsAccessor::CheckNewTransitionsAreConsistent(Isolate* isolate,
612 Handle<Map> map,
613 Object transitions) {
614 // This function only handles full transition arrays.
615 TransitionArray old_transitions = GetTransitionArray(isolate, map);
616 DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, old_transitions));
617 TransitionArray new_transitions = TransitionArray::cast(transitions);
618 for (int i = 0; i < old_transitions.number_of_transitions(); i++) {
619 Map target = old_transitions.GetTarget(i);
620 if (target.instance_descriptors(isolate) ==
621 map->instance_descriptors(isolate)) {
622 Name key = old_transitions.GetKey(i);
623 int new_target_index;
624 if (IsSpecialTransition(ReadOnlyRoots(isolate), key)) {
625 new_target_index = new_transitions.SearchSpecial(Symbol::cast(key));
626 } else {
627 PropertyDetails details = GetTargetDetails(key, target);
628 new_target_index =
629 new_transitions.Search(details.kind(), key, details.attributes());
630 }
631 DCHECK_NE(TransitionArray::kNotFound, new_target_index);
632 DCHECK_EQ(target, new_transitions.GetTarget(new_target_index));
633 }
634 }
635 }
636 #endif
637
638 // Private non-static helper functions (operating on full transition arrays).
639
SearchDetails(int transition,PropertyKind kind,PropertyAttributes attributes,int * out_insertion_index)640 int TransitionArray::SearchDetails(int transition, PropertyKind kind,
641 PropertyAttributes attributes,
642 int* out_insertion_index) {
643 int nof_transitions = number_of_transitions();
644 DCHECK(transition < nof_transitions);
645 Name key = GetKey(transition);
646 for (; transition < nof_transitions && GetKey(transition) == key;
647 transition++) {
648 Map target = GetTarget(transition);
649 PropertyDetails target_details =
650 TransitionsAccessor::GetTargetDetails(key, target);
651
652 int cmp = CompareDetails(kind, attributes, target_details.kind(),
653 target_details.attributes());
654 if (cmp == 0) {
655 return transition;
656 } else if (cmp < 0) {
657 break;
658 }
659 }
660 if (out_insertion_index != nullptr) *out_insertion_index = transition;
661 return kNotFound;
662 }
663
SearchDetailsAndGetTarget(int transition,PropertyKind kind,PropertyAttributes attributes)664 Map TransitionArray::SearchDetailsAndGetTarget(int transition,
665 PropertyKind kind,
666 PropertyAttributes attributes) {
667 int nof_transitions = number_of_transitions();
668 DCHECK(transition < nof_transitions);
669 Name key = GetKey(transition);
670 for (; transition < nof_transitions && GetKey(transition) == key;
671 transition++) {
672 Map target = GetTarget(transition);
673 PropertyDetails target_details =
674 TransitionsAccessor::GetTargetDetails(key, target);
675
676 int cmp = CompareDetails(kind, attributes, target_details.kind(),
677 target_details.attributes());
678 if (cmp == 0) {
679 return target;
680 } else if (cmp < 0) {
681 break;
682 }
683 }
684 return Map();
685 }
686
Search(PropertyKind kind,Name name,PropertyAttributes attributes,int * out_insertion_index)687 int TransitionArray::Search(PropertyKind kind, Name name,
688 PropertyAttributes attributes,
689 int* out_insertion_index) {
690 int transition = SearchName(name, false, out_insertion_index);
691 if (transition == kNotFound) return kNotFound;
692 return SearchDetails(transition, kind, attributes, out_insertion_index);
693 }
694
SearchAndGetTarget(PropertyKind kind,Name name,PropertyAttributes attributes)695 Map TransitionArray::SearchAndGetTarget(PropertyKind kind, Name name,
696 PropertyAttributes attributes) {
697 int transition = SearchName(name);
698 if (transition == kNotFound) {
699 return Map();
700 }
701 return SearchDetailsAndGetTarget(transition, kind, attributes);
702 }
703
ForEachTransitionTo(Name name,const ForEachTransitionCallback & callback)704 void TransitionArray::ForEachTransitionTo(
705 Name name, const ForEachTransitionCallback& callback) {
706 int transition = SearchName(name);
707 if (transition == kNotFound) return;
708
709 int nof_transitions = number_of_transitions();
710 DCHECK(transition < nof_transitions);
711 Name key = GetKey(transition);
712 for (; transition < nof_transitions && GetKey(transition) == key;
713 transition++) {
714 Map target = GetTarget(transition);
715 callback(target);
716 }
717 }
718
Sort()719 void TransitionArray::Sort() {
720 DisallowGarbageCollection no_gc;
721 // In-place insertion sort.
722 int length = number_of_transitions();
723 ReadOnlyRoots roots = GetReadOnlyRoots();
724 for (int i = 1; i < length; i++) {
725 Name key = GetKey(i);
726 MaybeObject target = GetRawTarget(i);
727 PropertyKind kind = PropertyKind::kData;
728 PropertyAttributes attributes = NONE;
729 if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
730 Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
731 PropertyDetails details =
732 TransitionsAccessor::GetTargetDetails(key, target_map);
733 kind = details.kind();
734 attributes = details.attributes();
735 }
736 int j;
737 for (j = i - 1; j >= 0; j--) {
738 Name temp_key = GetKey(j);
739 MaybeObject temp_target = GetRawTarget(j);
740 PropertyKind temp_kind = PropertyKind::kData;
741 PropertyAttributes temp_attributes = NONE;
742 if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
743 Map temp_target_map =
744 TransitionsAccessor::GetTargetFromRaw(temp_target);
745 PropertyDetails details =
746 TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
747 temp_kind = details.kind();
748 temp_attributes = details.attributes();
749 }
750 int cmp = CompareKeys(temp_key, temp_key.hash(), temp_kind,
751 temp_attributes, key, key.hash(), kind, attributes);
752 if (cmp > 0) {
753 SetKey(j + 1, temp_key);
754 SetRawTarget(j + 1, temp_target);
755 } else {
756 break;
757 }
758 }
759 SetKey(j + 1, key);
760 SetRawTarget(j + 1, target);
761 }
762 DCHECK(IsSortedNoDuplicates());
763 }
764
HasIntegrityLevelTransitionTo(Map to,Symbol * out_symbol,PropertyAttributes * out_integrity_level)765 bool TransitionsAccessor::HasIntegrityLevelTransitionTo(
766 Map to, Symbol* out_symbol, PropertyAttributes* out_integrity_level) {
767 ReadOnlyRoots roots(isolate_);
768 if (SearchSpecial(roots.frozen_symbol()) == to) {
769 if (out_integrity_level) *out_integrity_level = FROZEN;
770 if (out_symbol) *out_symbol = roots.frozen_symbol();
771 } else if (SearchSpecial(roots.sealed_symbol()) == to) {
772 if (out_integrity_level) *out_integrity_level = SEALED;
773 if (out_symbol) *out_symbol = roots.sealed_symbol();
774 } else if (SearchSpecial(roots.nonextensible_symbol()) == to) {
775 if (out_integrity_level) *out_integrity_level = NONE;
776 if (out_symbol) *out_symbol = roots.nonextensible_symbol();
777 } else {
778 return false;
779 }
780 return true;
781 }
782
783 } // namespace internal
784 } // namespace v8
785