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