• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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