Home | History | Annotate | Download | only in src 
      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 
     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 
     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 
     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 
     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 
    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 
    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
    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 
    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 
    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 
    284 Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() {
    285   DCHECK(!ExpectedTransitionKey().is_null());
    286   return handle(GetTarget(0), isolate_);
    287 }
    288 
    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
    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
    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
    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 
    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 
    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 
    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
    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 
    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 
    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 
    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 
    469 void TransitionsAccessor::SetPrototypeTransitions(
    470     Handle<WeakFixedArray> proto_transitions) {
    471   EnsureHasFullTransitionArray();
    472   transitions()->SetPrototypeTransitions(*proto_transitions);
    473 }
    474 
    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 
    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
    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 
    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 
    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 
    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