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