5 #include "src/transitions.h" 7 #include "src/objects-inl.h" 8 #include "src/transitions-inl.h" 14 void 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()) {
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;
27 DCHECK(map_->is_deprecated());
28 DCHECK(heap_object->IsMap());
29 encoding_ = kMigrationTarget;
35 needs_reload_ =
false;
39 Map TransitionsAccessor::GetSimpleTransition() {
42 return Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
48 bool TransitionsAccessor::HasSimpleTransitionTo(Map map) {
51 return raw_transitions_->GetHeapObjectAssumeWeak() == map;
54 case kMigrationTarget:
55 case kFullTransitionArray:
61 void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target,
62 SimpleTransitionFlag flag) {
63 DCHECK(!map_handle_.is_null());
64 target->SetBackPointer(map_);
67 if (encoding() == kUninitialized || encoding() == kMigrationTarget) {
68 if (flag == SIMPLE_PROPERTY_TRANSITION) {
69 ReplaceTransitions(HeapObjectReference::Weak(*target));
73 Handle<TransitionArray> result =
74 isolate_->factory()->NewTransitionArray(0, 1);
75 ReplaceTransitions(MaybeObject::FromObject(*result));
79 bool is_special_transition = flag == SPECIAL_TRANSITION;
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));
95 Handle<Map> map(simple_transition, isolate_);
96 Handle<TransitionArray> result =
97 isolate_->factory()->NewTransitionArray(1, 1);
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));
110 result->SetNumberOfTransitions(0);
112 ReplaceTransitions(MaybeObject::FromObject(*result));
117 DCHECK_EQ(kFullTransitionArray, encoding());
119 int number_of_transitions = 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);
129 DisallowHeapAllocation no_gc;
130 TransitionArray* array = transitions();
131 number_of_transitions = array->number_of_transitions();
132 new_nof = number_of_transitions;
135 is_special_transition
136 ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
137 : array->Search(details.kind(), *name, details.attributes(),
140 if (index != kNotFound) {
141 array->SetRawTarget(index, HeapObjectReference::Weak(*target));
146 CHECK_LE(new_nof, kMaxNumberOfTransitions);
147 DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
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));
156 array->SetKey(index, *name);
157 array->SetRawTarget(index, HeapObjectReference::Weak(*target));
158 SLOW_DCHECK(array->IsSortedNoDuplicates());
164 Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(
166 Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
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);
177 number_of_transitions = array->number_of_transitions();
178 new_nof = number_of_transitions;
180 insertion_index = kNotFound;
182 is_special_transition
183 ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
184 : array->Search(details.kind(), *name, details.attributes(),
186 if (index == kNotFound) {
189 insertion_index = index;
191 DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
193 result->SetNumberOfTransitions(new_nof);
196 if (array->HasPrototypeTransitions()) {
197 result->SetPrototypeTransitions(array->GetPrototypeTransitions());
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));
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));
209 SLOW_DCHECK(result->IsSortedNoDuplicates());
210 ReplaceTransitions(MaybeObject::FromObject(*result));
213 Map TransitionsAccessor::SearchTransition(Name name, PropertyKind kind,
214 PropertyAttributes attributes) {
215 DCHECK(name->IsUniqueName());
216 switch (encoding()) {
219 case kMigrationTarget:
222 Map map = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
223 if (!IsMatchingMap(map, name, kind, attributes))
return Map();
226 case kFullTransitionArray: {
227 int transition = transitions()->Search(kind, name, attributes);
228 if (transition == kNotFound)
return Map();
229 return transitions()->GetTarget(transition);
235 Map TransitionsAccessor::SearchSpecial(Symbol name) {
236 if (encoding() != kFullTransitionArray)
return Map();
237 int transition = transitions()->SearchSpecial(name);
238 if (transition == kNotFound)
return Map();
239 return transitions()->GetTarget(transition);
243 bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots, Name name) {
244 if (!name->IsSymbol())
return false;
245 return name == roots.nonextensible_symbol() ||
246 name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
247 name == roots.elements_transition_symbol() ||
248 name == roots.strict_function_transition_symbol();
251 MaybeHandle<Map> TransitionsAccessor::FindTransitionToDataProperty(
252 Handle<Name> name, RequestedLocation requested_location) {
253 DCHECK(name->IsUniqueName());
254 DisallowHeapAllocation no_gc;
255 PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE;
256 Map target = SearchTransition(*name, kData, attributes);
257 if (target.is_null())
return MaybeHandle<Map>();
258 PropertyDetails details = target->GetLastDescriptorDetails();
259 DCHECK_EQ(attributes, details.attributes());
260 DCHECK_EQ(kData, details.kind());
261 if (requested_location == kFieldOnly && details.location() != kField) {
262 return MaybeHandle<Map>();
264 return Handle<Map>(target, isolate_);
267 Handle<String> TransitionsAccessor::ExpectedTransitionKey() {
268 DisallowHeapAllocation no_gc;
269 switch (encoding()) {
272 case kMigrationTarget:
273 case kFullTransitionArray:
274 return Handle<String>::null();
276 Map target = Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
277 PropertyDetails details = GetSimpleTargetDetails(target);
278 if (details.location() != kField)
return Handle<String>::null();
279 DCHECK_EQ(kData, details.kind());
280 if (details.attributes() != NONE)
return Handle<String>::null();
281 Name name = GetSimpleTransitionKey(target);
282 if (!name->IsString())
return Handle<String>::null();
283 return handle(String::cast(name), isolate_);
289 Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
290 DCHECK(!ExpectedTransitionKey().is_null());
291 return handle(GetTarget(0), isolate_);
294 bool TransitionsAccessor::CanHaveMoreTransitions() {
295 if (map_->is_dictionary_map())
return false;
296 if (encoding() == kFullTransitionArray) {
297 return transitions()->number_of_transitions() < kMaxNumberOfTransitions;
303 bool TransitionsAccessor::IsMatchingMap(Map target, Name name,
305 PropertyAttributes attributes) {
306 int descriptor = target->LastAdded();
307 DescriptorArray* descriptors = target->instance_descriptors();
308 Name key = descriptors->GetKey(descriptor);
309 if (key != name)
return false;
310 PropertyDetails details = descriptors->GetDetails(descriptor);
311 return (details.kind() == kind && details.attributes() == attributes);
315 bool TransitionArray::CompactPrototypeTransitionArray(Isolate* isolate,
316 WeakFixedArray* array) {
317 const int header = kProtoTransitionHeaderSize;
318 int number_of_transitions = NumberOfPrototypeTransitions(array);
319 if (number_of_transitions == 0) {
323 int new_number_of_transitions = 0;
324 for (
int i = 0;
i < number_of_transitions;
i++) {
325 MaybeObject target = array->Get(header +
i);
326 DCHECK(target->IsCleared() ||
327 (target->IsWeak() && target->GetHeapObject()->IsMap()));
328 if (!target->IsCleared()) {
329 if (new_number_of_transitions !=
i) {
330 array->Set(header + new_number_of_transitions, target);
332 new_number_of_transitions++;
336 MaybeObject undefined =
337 MaybeObject::FromObject(*isolate->factory()->undefined_value());
338 for (
int i = new_number_of_transitions;
i < number_of_transitions;
i++) {
339 array->Set(header +
i, undefined);
341 if (number_of_transitions != new_number_of_transitions) {
342 SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
344 return new_number_of_transitions < number_of_transitions;
349 Handle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
350 Handle<WeakFixedArray> array,
int new_capacity, Isolate* isolate) {
352 int capacity = array->length() - kProtoTransitionHeaderSize;
353 new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
354 DCHECK_GT(new_capacity, capacity);
355 int grow_by = new_capacity - capacity;
357 isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by, TENURED);
361 SetNumberOfPrototypeTransitions(*array, 0);
366 void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype,
367 Handle<Map> target_map) {
368 DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
371 if (map_->is_prototype_map())
return;
372 if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions)
return;
374 const int header = TransitionArray::kProtoTransitionHeaderSize;
376 Handle<WeakFixedArray> cache(GetPrototypeTransitions(), isolate_);
377 int capacity = cache->length() - header;
378 int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
380 if (transitions > capacity) {
382 if (!TransitionArray::CompactPrototypeTransitionArray(isolate_, *cache)) {
383 if (capacity == TransitionArray::kMaxCachedPrototypeTransitions)
return;
384 cache = TransitionArray::GrowPrototypeTransitionArray(
385 cache, 2 * transitions, isolate_);
387 SetPrototypeTransitions(cache);
392 int last = TransitionArray::NumberOfPrototypeTransitions(*cache);
393 int entry = header + last;
395 cache->Set(entry, HeapObjectReference::Weak(*target_map));
396 TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
399 Handle<Map> TransitionsAccessor::GetPrototypeTransition(
400 Handle<Object> prototype) {
401 DisallowHeapAllocation no_gc;
402 WeakFixedArray* cache = GetPrototypeTransitions();
403 int length = TransitionArray::NumberOfPrototypeTransitions(cache);
404 for (
int i = 0;
i < length;
i++) {
406 cache->Get(TransitionArray::kProtoTransitionHeaderSize +
i);
407 DCHECK(target->IsWeakOrCleared());
408 HeapObject* heap_object;
409 if (target->GetHeapObjectIfWeak(&heap_object)) {
410 Map map = Map::cast(heap_object);
411 if (map->prototype() == *prototype) {
412 return handle(map, isolate_);
416 return Handle<Map>();
419 WeakFixedArray* TransitionsAccessor::GetPrototypeTransitions() {
420 if (encoding() != kFullTransitionArray ||
421 !transitions()->HasPrototypeTransitions()) {
422 return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
424 return transitions()->GetPrototypeTransitions();
428 void TransitionArray::SetNumberOfPrototypeTransitions(
429 WeakFixedArray* proto_transitions,
int value) {
430 DCHECK_NE(proto_transitions->length(), 0);
431 proto_transitions->Set(kProtoTransitionNumberOfEntriesOffset,
432 MaybeObject::FromSmi(Smi::FromInt(value)));
435 int TransitionsAccessor::NumberOfTransitions() {
436 switch (encoding()) {
439 case kMigrationTarget:
443 case kFullTransitionArray:
444 return transitions()->number_of_transitions();
450 void TransitionsAccessor::SetMigrationTarget(Map migration_target) {
453 if (encoding() != kUninitialized)
return;
454 DCHECK(map_->is_deprecated());
455 map_->set_raw_transitions(MaybeObject::FromObject(migration_target));
459 Map TransitionsAccessor::GetMigrationTarget() {
460 if (encoding() == kMigrationTarget) {
461 return map_->raw_transitions()->cast<Map>();
466 void TransitionArray::Zap(Isolate* isolate) {
467 MemsetPointer(ObjectSlot(data_start() + kPrototypeTransitionsIndex),
468 ReadOnlyRoots(isolate).the_hole_value(),
469 length() - kPrototypeTransitionsIndex);
470 SetNumberOfTransitions(0);
473 void TransitionsAccessor::ReplaceTransitions(MaybeObject new_transitions) {
474 if (encoding() == kFullTransitionArray) {
475 TransitionArray* old_transitions = transitions();
477 CheckNewTransitionsAreConsistent(
478 old_transitions, new_transitions->GetHeapObjectAssumeStrong());
479 DCHECK(old_transitions != new_transitions->GetHeapObjectAssumeStrong());
485 old_transitions->Zap(isolate_);
487 map_->set_raw_transitions(new_transitions);
491 void TransitionsAccessor::SetPrototypeTransitions(
492 Handle<WeakFixedArray> proto_transitions) {
493 EnsureHasFullTransitionArray();
494 transitions()->SetPrototypeTransitions(*proto_transitions);
497 void TransitionsAccessor::EnsureHasFullTransitionArray() {
498 if (encoding() == kFullTransitionArray)
return;
500 (encoding() == kUninitialized || encoding() == kMigrationTarget) ? 0 : 1;
501 Handle<TransitionArray> result = isolate_->factory()->NewTransitionArray(nof);
504 if (encoding() == kUninitialized) {
506 result->SetNumberOfTransitions(0);
509 Handle<Map> target(GetSimpleTransition(), isolate_);
510 Name key = GetSimpleTransitionKey(*target);
511 result->Set(0, key, HeapObjectReference::Weak(*target));
514 ReplaceTransitions(MaybeObject::FromObject(*result));
518 void TransitionsAccessor::TraverseTransitionTreeInternal(
519 TraverseCallback callback,
void* data, DisallowHeapAllocation* no_gc) {
520 switch (encoding()) {
523 case kMigrationTarget:
527 Map::cast(raw_transitions_->GetHeapObjectAssumeWeak());
528 TransitionsAccessor(isolate_, simple_target, no_gc)
529 .TraverseTransitionTreeInternal(callback, data, no_gc);
532 case kFullTransitionArray: {
533 if (transitions()->HasPrototypeTransitions()) {
534 WeakFixedArray* proto_trans = transitions()->GetPrototypeTransitions();
535 int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans);
536 for (
int i = 0;
i < length; ++
i) {
537 int index = TransitionArray::kProtoTransitionHeaderSize +
i;
538 MaybeObject target = proto_trans->Get(index);
539 HeapObject* heap_object;
540 if (target->GetHeapObjectIfWeak(&heap_object)) {
541 TransitionsAccessor(isolate_, Map::cast(heap_object), no_gc)
542 .TraverseTransitionTreeInternal(callback, data, no_gc);
544 DCHECK(target->IsCleared());
548 for (
int i = 0;
i < transitions()->number_of_transitions(); ++
i) {
549 TransitionsAccessor(isolate_, transitions()->GetTarget(
i), no_gc)
550 .TraverseTransitionTreeInternal(callback, data, no_gc);
555 callback(map_, data);
559 void TransitionsAccessor::CheckNewTransitionsAreConsistent(
560 TransitionArray* old_transitions, Object* transitions) {
562 DCHECK_EQ(kFullTransitionArray, encoding());
563 TransitionArray* new_transitions = TransitionArray::cast(transitions);
564 for (
int i = 0;
i < old_transitions->number_of_transitions();
i++) {
565 Map target = old_transitions->GetTarget(
i);
566 if (target->instance_descriptors() == map_->instance_descriptors()) {
567 Name key = old_transitions->GetKey(
i);
568 int new_target_index;
569 if (IsSpecialTransition(ReadOnlyRoots(isolate_), key)) {
570 new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
572 PropertyDetails details = GetTargetDetails(key, target);
574 new_transitions->Search(details.kind(), key, details.attributes());
576 DCHECK_NE(TransitionArray::kNotFound, new_target_index);
577 DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
585 int TransitionArray::SearchDetails(
int transition, PropertyKind kind,
586 PropertyAttributes attributes,
587 int* out_insertion_index) {
588 int nof_transitions = number_of_transitions();
589 DCHECK(transition < nof_transitions);
590 Name key = GetKey(transition);
591 for (; transition < nof_transitions && GetKey(transition) == key;
593 Map target = GetTarget(transition);
594 PropertyDetails target_details =
595 TransitionsAccessor::GetTargetDetails(key, target);
597 int cmp = CompareDetails(kind, attributes, target_details.kind(),
598 target_details.attributes());
601 }
else if (cmp < 0) {
605 if (out_insertion_index !=
nullptr) *out_insertion_index = transition;
609 int TransitionArray::Search(PropertyKind kind, Name name,
610 PropertyAttributes attributes,
611 int* out_insertion_index) {
612 int transition = SearchName(name, out_insertion_index);
613 if (transition == kNotFound)
return kNotFound;
614 return SearchDetails(transition, kind, attributes, out_insertion_index);
617 void TransitionArray::Sort() {
618 DisallowHeapAllocation no_gc;
620 int length = number_of_transitions();
621 ReadOnlyRoots roots = GetReadOnlyRoots();
622 for (
int i = 1;
i < length;
i++) {
623 Name key = GetKey(
i);
624 MaybeObject target = GetRawTarget(
i);
625 PropertyKind kind = kData;
626 PropertyAttributes attributes = NONE;
627 if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
628 Map target_map = TransitionsAccessor::GetTargetFromRaw(target);
629 PropertyDetails details =
630 TransitionsAccessor::GetTargetDetails(key, target_map);
631 kind = details.kind();
632 attributes = details.attributes();
635 for (j =
i - 1; j >= 0; j--) {
636 Name temp_key = GetKey(j);
637 MaybeObject temp_target = GetRawTarget(j);
638 PropertyKind temp_kind = kData;
639 PropertyAttributes temp_attributes = NONE;
640 if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
641 Map temp_target_map =
642 TransitionsAccessor::GetTargetFromRaw(temp_target);
643 PropertyDetails details =
644 TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
645 temp_kind = details.kind();
646 temp_attributes = details.attributes();
649 CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes,
650 key, key->Hash(), kind, attributes);
652 SetKey(j + 1, temp_key);
653 SetRawTarget(j + 1, temp_target);
659 SetRawTarget(j + 1, target);
661 DCHECK(IsSortedNoDuplicates());