LCOV - code coverage report
Current view: top level - src - transitions.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 263 288 91.3 %
Date: 2019-01-20 Functions: 31 33 93.9 %

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

Generated by: LCOV version 1.10