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 
     15 // static
     16 void TransitionArray::Insert(Handle<Map> map, Handle<Name> name,
     17                              Handle<Map> target, SimpleTransitionFlag flag) {
     18   Isolate* isolate = map->GetIsolate();
     19   target->SetBackPointer(*map);
     20 
     21   // If the map doesn't have any transitions at all yet, install the new one.
     22   if (CanStoreSimpleTransition(map->raw_transitions())) {
     23     if (flag == SIMPLE_PROPERTY_TRANSITION) {
     24       Handle<WeakCell> cell = Map::WeakCellForMap(target);
     25       ReplaceTransitions(map, *cell);
     26       return;
     27     }
     28     // If the flag requires a full TransitionArray, allocate one.
     29     Handle<TransitionArray> result = Allocate(isolate, 0, 1);
     30     ReplaceTransitions(map, *result);
     31   }
     32 
     33   bool is_special_transition = flag == SPECIAL_TRANSITION;
     34   // If the map has a simple transition, check if it should be overwritten.
     35   if (IsSimpleTransition(map->raw_transitions())) {
     36     Map* old_target = GetSimpleTransition(map->raw_transitions());
     37     Name* key = GetSimpleTransitionKey(old_target);
     38     PropertyDetails old_details = GetSimpleTargetDetails(old_target);
     39     PropertyDetails new_details = is_special_transition
     40                                       ? PropertyDetails::Empty()
     41                                       : GetTargetDetails(*name, *target);
     42     if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
     43         old_details.kind() == new_details.kind() &&
     44         old_details.attributes() == new_details.attributes()) {
     45       Handle<WeakCell> cell = Map::WeakCellForMap(target);
     46       ReplaceTransitions(map, *cell);
     47       return;
     48     }
     49     // Otherwise allocate a full TransitionArray with slack for a new entry.
     50     Handle<TransitionArray> result = Allocate(isolate, 1, 1);
     51     // Re-read existing data; the allocation might have caused it to be cleared.
     52     if (IsSimpleTransition(map->raw_transitions())) {
     53       old_target = GetSimpleTransition(map->raw_transitions());
     54       result->Set(0, GetSimpleTransitionKey(old_target), old_target);
     55     } else {
     56       result->SetNumberOfTransitions(0);
     57     }
     58     ReplaceTransitions(map, *result);
     59   }
     60 
     61   // At this point, we know that the map has a full TransitionArray.
     62   DCHECK(IsFullTransitionArray(map->raw_transitions()));
     63 
     64   int number_of_transitions = 0;
     65   int new_nof = 0;
     66   int insertion_index = kNotFound;
     67   DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
     68   PropertyDetails details = is_special_transition
     69                                 ? PropertyDetails::Empty()
     70                                 : GetTargetDetails(*name, *target);
     71 
     72   {
     73     DisallowHeapAllocation no_gc;
     74     TransitionArray* array = TransitionArray::cast(map->raw_transitions());
     75     number_of_transitions = array->number_of_transitions();
     76     new_nof = number_of_transitions;
     77 
     78     int index =
     79         is_special_transition
     80             ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
     81             : array->Search(details.kind(), *name, details.attributes(),
     82                             &insertion_index);
     83     // If an existing entry was found, overwrite it and return.
     84     if (index != kNotFound) {
     85       array->SetTarget(index, *target);
     86       return;
     87     }
     88 
     89     ++new_nof;
     90     CHECK(new_nof <= kMaxNumberOfTransitions);
     91     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
     92 
     93     // If there is enough capacity, insert new entry into the existing array.
     94     if (new_nof <= Capacity(array)) {
     95       array->SetNumberOfTransitions(new_nof);
     96       for (index = number_of_transitions; index > insertion_index; --index) {
     97         array->SetKey(index, array->GetKey(index - 1));
     98         array->SetTarget(index, array->GetTarget(index - 1));
     99       }
    100       array->SetKey(index, *name);
    101       array->SetTarget(index, *target);
    102       SLOW_DCHECK(array->IsSortedNoDuplicates());
    103       return;
    104     }
    105   }
    106 
    107   // We're gonna need a bigger TransitionArray.
    108   Handle<TransitionArray> result = Allocate(
    109       map->GetIsolate(), new_nof,
    110       Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
    111 
    112   // The map's transition array may have shrunk during the allocation above as
    113   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
    114   // result copy if needed, and recompute variables.
    115   DCHECK(IsFullTransitionArray(map->raw_transitions()));
    116   DisallowHeapAllocation no_gc;
    117   TransitionArray* array = TransitionArray::cast(map->raw_transitions());
    118   if (array->number_of_transitions() != number_of_transitions) {
    119     DCHECK(array->number_of_transitions() < number_of_transitions);
    120 
    121     number_of_transitions = array->number_of_transitions();
    122     new_nof = number_of_transitions;
    123 
    124     insertion_index = kNotFound;
    125     int index =
    126         is_special_transition
    127             ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
    128             : array->Search(details.kind(), *name, details.attributes(),
    129                             &insertion_index);
    130     if (index == kNotFound) {
    131       ++new_nof;
    132     } else {
    133       insertion_index = index;
    134     }
    135     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
    136 
    137     result->Shrink(ToKeyIndex(new_nof));
    138     result->SetNumberOfTransitions(new_nof);
    139   }
    140 
    141   if (array->HasPrototypeTransitions()) {
    142     result->SetPrototypeTransitions(array->GetPrototypeTransitions());
    143   }
    144 
    145   DCHECK_NE(kNotFound, insertion_index);
    146   for (int i = 0; i < insertion_index; ++i) {
    147     result->Set(i, array->GetKey(i), array->GetTarget(i));
    148   }
    149   result->Set(insertion_index, *name, *target);
    150   for (int i = insertion_index; i < number_of_transitions; ++i) {
    151     result->Set(i + 1, array->GetKey(i), array->GetTarget(i));
    152   }
    153 
    154   SLOW_DCHECK(result->IsSortedNoDuplicates());
    155   ReplaceTransitions(map, *result);
    156 }
    157 
    158 
    159 // static
    160 Map* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name,
    161                                        PropertyAttributes attributes) {
    162   Object* raw_transitions = map->raw_transitions();
    163   if (IsSimpleTransition(raw_transitions)) {
    164     Map* target = GetSimpleTransition(raw_transitions);
    165     Name* key = GetSimpleTransitionKey(target);
    166     if (!key->Equals(name)) return NULL;
    167     PropertyDetails details = GetSimpleTargetDetails(target);
    168     if (details.attributes() != attributes) return NULL;
    169     if (details.kind() != kind) return NULL;
    170     return target;
    171   }
    172   if (IsFullTransitionArray(raw_transitions)) {
    173     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
    174     int transition = transitions->Search(kind, name, attributes);
    175     if (transition == kNotFound) return NULL;
    176     return transitions->GetTarget(transition);
    177   }
    178   return NULL;
    179 }
    180 
    181 
    182 // static
    183 Map* TransitionArray::SearchSpecial(Map* map, Symbol* name) {
    184   Object* raw_transitions = map->raw_transitions();
    185   if (IsFullTransitionArray(raw_transitions)) {
    186     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
    187     int transition = transitions->SearchSpecial(name);
    188     if (transition == kNotFound) return NULL;
    189     return transitions->GetTarget(transition);
    190   }
    191   return NULL;
    192 }
    193 
    194 
    195 // static
    196 Handle<Map> TransitionArray::FindTransitionToField(Handle<Map> map,
    197                                                    Handle<Name> name) {
    198   DisallowHeapAllocation no_gc;
    199   Map* target = SearchTransition(*map, kData, *name, NONE);
    200   if (target == NULL) return Handle<Map>::null();
    201   PropertyDetails details = target->GetLastDescriptorDetails();
    202   DCHECK_EQ(NONE, details.attributes());
    203   if (details.type() != DATA) return Handle<Map>::null();
    204   return Handle<Map>(target);
    205 }
    206 
    207 
    208 // static
    209 Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) {
    210   DisallowHeapAllocation no_gc;
    211   Object* raw_transition = map->raw_transitions();
    212   if (!IsSimpleTransition(raw_transition)) return Handle<String>::null();
    213   Map* target = GetSimpleTransition(raw_transition);
    214   PropertyDetails details = GetSimpleTargetDetails(target);
    215   if (details.type() != DATA) return Handle<String>::null();
    216   if (details.attributes() != NONE) return Handle<String>::null();
    217   Name* name = GetSimpleTransitionKey(target);
    218   if (!name->IsString()) return Handle<String>::null();
    219   return Handle<String>(String::cast(name));
    220 }
    221 
    222 
    223 // static
    224 bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) {
    225   if (map->is_dictionary_map()) return false;
    226   Object* raw_transitions = map->raw_transitions();
    227   if (IsFullTransitionArray(raw_transitions)) {
    228     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
    229     return transitions->number_of_transitions() < kMaxNumberOfTransitions;
    230   }
    231   return true;
    232 }
    233 
    234 
    235 // static
    236 bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) {
    237   const int header = kProtoTransitionHeaderSize;
    238   int number_of_transitions = NumberOfPrototypeTransitions(array);
    239   if (number_of_transitions == 0) {
    240     // Empty array cannot be compacted.
    241     return false;
    242   }
    243   int new_number_of_transitions = 0;
    244   for (int i = 0; i < number_of_transitions; i++) {
    245     Object* cell = array->get(header + i);
    246     if (!WeakCell::cast(cell)->cleared()) {
    247       if (new_number_of_transitions != i) {
    248         array->set(header + new_number_of_transitions, cell);
    249       }
    250       new_number_of_transitions++;
    251     }
    252   }
    253   // Fill slots that became free with undefined value.
    254   for (int i = new_number_of_transitions; i < number_of_transitions; i++) {
    255     array->set_undefined(header + i);
    256   }
    257   if (number_of_transitions != new_number_of_transitions) {
    258     SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
    259   }
    260   return new_number_of_transitions < number_of_transitions;
    261 }
    262 
    263 
    264 // static
    265 Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray(
    266     Handle<FixedArray> array, int new_capacity, Isolate* isolate) {
    267   // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
    268   int capacity = array->length() - kProtoTransitionHeaderSize;
    269   new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity);
    270   DCHECK_GT(new_capacity, capacity);
    271   int grow_by = new_capacity - capacity;
    272   array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED);
    273   if (capacity < 0) {
    274     // There was no prototype transitions array before, so the size
    275     // couldn't be copied. Initialize it explicitly.
    276     SetNumberOfPrototypeTransitions(*array, 0);
    277   }
    278   return array;
    279 }
    280 
    281 
    282 // static
    283 int TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) {
    284   FixedArray* transitions = GetPrototypeTransitions(map);
    285   CompactPrototypeTransitionArray(transitions);
    286   return TransitionArray::NumberOfPrototypeTransitions(transitions);
    287 }
    288 
    289 
    290 // static
    291 void TransitionArray::PutPrototypeTransition(Handle<Map> map,
    292                                              Handle<Object> prototype,
    293                                              Handle<Map> target_map) {
    294   DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
    295   // Don't cache prototype transition if this map is either shared, or a map of
    296   // a prototype.
    297   if (map->is_prototype_map()) return;
    298   if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return;
    299 
    300   const int header = kProtoTransitionHeaderSize;
    301 
    302   Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map);
    303 
    304   Handle<FixedArray> cache(GetPrototypeTransitions(*map));
    305   int capacity = cache->length() - header;
    306   int transitions = NumberOfPrototypeTransitions(*cache) + 1;
    307 
    308   if (transitions > capacity) {
    309     // Grow the array if compacting it doesn't free space.
    310     if (!CompactPrototypeTransitionArray(*cache)) {
    311       if (capacity == kMaxCachedPrototypeTransitions) return;
    312       cache = GrowPrototypeTransitionArray(cache, 2 * transitions,
    313                                            map->GetIsolate());
    314       SetPrototypeTransitions(map, cache);
    315     }
    316   }
    317 
    318   // Reload number of transitions as they might have been compacted.
    319   int last = NumberOfPrototypeTransitions(*cache);
    320   int entry = header + last;
    321 
    322   cache->set(entry, *target_cell);
    323   SetNumberOfPrototypeTransitions(*cache, last + 1);
    324 }
    325 
    326 
    327 // static
    328 Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map,
    329                                                     Handle<Object> prototype) {
    330   DisallowHeapAllocation no_gc;
    331   FixedArray* cache = GetPrototypeTransitions(*map);
    332   int number_of_transitions = NumberOfPrototypeTransitions(cache);
    333   for (int i = 0; i < number_of_transitions; i++) {
    334     WeakCell* target_cell =
    335         WeakCell::cast(cache->get(kProtoTransitionHeaderSize + i));
    336     if (!target_cell->cleared() &&
    337         Map::cast(target_cell->value())->prototype() == *prototype) {
    338       return handle(Map::cast(target_cell->value()));
    339     }
    340   }
    341   return Handle<Map>();
    342 }
    343 
    344 
    345 // static
    346 FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) {
    347   Object* raw_transitions = map->raw_transitions();
    348   Heap* heap = map->GetHeap();
    349   if (!IsFullTransitionArray(raw_transitions)) {
    350     return heap->empty_fixed_array();
    351   }
    352   TransitionArray* transitions = TransitionArray::cast(raw_transitions);
    353   if (!transitions->HasPrototypeTransitions()) {
    354     return heap->empty_fixed_array();
    355   }
    356   return transitions->GetPrototypeTransitions();
    357 }
    358 
    359 
    360 // static
    361 void TransitionArray::SetNumberOfPrototypeTransitions(
    362     FixedArray* proto_transitions, int value) {
    363   DCHECK(proto_transitions->length() != 0);
    364   proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
    365                          Smi::FromInt(value));
    366 }
    367 
    368 
    369 // static
    370 int TransitionArray::NumberOfTransitions(Object* raw_transitions) {
    371   if (CanStoreSimpleTransition(raw_transitions)) return 0;
    372   if (IsSimpleTransition(raw_transitions)) return 1;
    373   // Prototype maps don't have transitions.
    374   if (raw_transitions->IsPrototypeInfo()) return 0;
    375   DCHECK(IsFullTransitionArray(raw_transitions));
    376   return TransitionArray::cast(raw_transitions)->number_of_transitions();
    377 }
    378 
    379 
    380 // static
    381 int TransitionArray::Capacity(Object* raw_transitions) {
    382   if (!IsFullTransitionArray(raw_transitions)) return 1;
    383   TransitionArray* t = TransitionArray::cast(raw_transitions);
    384   if (t->length() <= kFirstIndex) return 0;
    385   return (t->length() - kFirstIndex) / kTransitionSize;
    386 }
    387 
    388 
    389 // Private static helper functions.
    390 
    391 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
    392                                                   int number_of_transitions,
    393                                                   int slack) {
    394   Handle<FixedArray> array = isolate->factory()->NewTransitionArray(
    395       LengthFor(number_of_transitions + slack));
    396   array->set(kNextLinkIndex, isolate->heap()->undefined_value());
    397   array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
    398   array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
    399   return Handle<TransitionArray>::cast(array);
    400 }
    401 
    402 
    403 // static
    404 void TransitionArray::ZapTransitionArray(TransitionArray* transitions) {
    405   // Do not zap the next link that is used by GC.
    406   STATIC_ASSERT(kNextLinkIndex + 1 == kPrototypeTransitionsIndex);
    407   MemsetPointer(transitions->data_start() + kPrototypeTransitionsIndex,
    408                 transitions->GetHeap()->the_hole_value(),
    409                 transitions->length() - kPrototypeTransitionsIndex);
    410   transitions->SetNumberOfTransitions(0);
    411 }
    412 
    413 
    414 void TransitionArray::ReplaceTransitions(Handle<Map> map,
    415                                          Object* new_transitions) {
    416   Object* raw_transitions = map->raw_transitions();
    417   if (IsFullTransitionArray(raw_transitions)) {
    418     TransitionArray* old_transitions = TransitionArray::cast(raw_transitions);
    419 #ifdef DEBUG
    420     CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions);
    421     DCHECK(old_transitions != new_transitions);
    422 #endif
    423     // Transition arrays are not shared. When one is replaced, it should not
    424     // keep referenced objects alive, so we zap it.
    425     // When there is another reference to the array somewhere (e.g. a handle),
    426     // not zapping turns from a waste of memory into a source of crashes.
    427     ZapTransitionArray(old_transitions);
    428   }
    429   map->set_raw_transitions(new_transitions);
    430 }
    431 
    432 
    433 void TransitionArray::SetPrototypeTransitions(
    434     Handle<Map> map, Handle<FixedArray> proto_transitions) {
    435   EnsureHasFullTransitionArray(map);
    436   TransitionArray* transitions = TransitionArray::cast(map->raw_transitions());
    437   transitions->SetPrototypeTransitions(*proto_transitions);
    438 }
    439 
    440 
    441 void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) {
    442   Object* raw_transitions = map->raw_transitions();
    443   if (IsFullTransitionArray(raw_transitions)) return;
    444   int nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
    445   Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof);
    446   DisallowHeapAllocation no_gc;
    447   // Reload pointer after the allocation that just happened.
    448   raw_transitions = map->raw_transitions();
    449   int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
    450   if (new_nof != nof) {
    451     DCHECK(new_nof == 0);
    452     result->Shrink(ToKeyIndex(0));
    453     result->SetNumberOfTransitions(0);
    454   } else if (nof == 1) {
    455     Map* target = GetSimpleTransition(raw_transitions);
    456     Name* key = GetSimpleTransitionKey(target);
    457     result->Set(0, key, target);
    458   }
    459   ReplaceTransitions(map, *result);
    460 }
    461 
    462 
    463 void TransitionArray::TraverseTransitionTreeInternal(Map* map,
    464                                                      TraverseCallback callback,
    465                                                      void* data) {
    466   Object* raw_transitions = map->raw_transitions();
    467   if (IsFullTransitionArray(raw_transitions)) {
    468     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
    469     if (transitions->HasPrototypeTransitions()) {
    470       FixedArray* proto_trans = transitions->GetPrototypeTransitions();
    471       for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) {
    472         int index = TransitionArray::kProtoTransitionHeaderSize + i;
    473         WeakCell* cell = WeakCell::cast(proto_trans->get(index));
    474         if (!cell->cleared()) {
    475           TraverseTransitionTreeInternal(Map::cast(cell->value()), callback,
    476                                          data);
    477         }
    478       }
    479     }
    480     for (int i = 0; i < transitions->number_of_transitions(); ++i) {
    481       TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
    482     }
    483   } else if (IsSimpleTransition(raw_transitions)) {
    484     TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions),
    485                                    callback, data);
    486   }
    487   callback(map, data);
    488 }
    489 
    490 
    491 #ifdef DEBUG
    492 void TransitionArray::CheckNewTransitionsAreConsistent(
    493     Handle<Map> map, TransitionArray* old_transitions, Object* transitions) {
    494   // This function only handles full transition arrays.
    495   DCHECK(IsFullTransitionArray(transitions));
    496   TransitionArray* new_transitions = TransitionArray::cast(transitions);
    497   for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
    498     Map* target = old_transitions->GetTarget(i);
    499     if (target->instance_descriptors() == map->instance_descriptors()) {
    500       Name* key = old_transitions->GetKey(i);
    501       int new_target_index;
    502       if (TransitionArray::IsSpecialTransition(key)) {
    503         new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
    504       } else {
    505         PropertyDetails details =
    506             TransitionArray::GetTargetDetails(key, target);
    507         new_target_index =
    508             new_transitions->Search(details.kind(), key, details.attributes());
    509       }
    510       DCHECK_NE(TransitionArray::kNotFound, new_target_index);
    511       DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
    512     }
    513   }
    514 }
    515 #endif
    516 
    517 
    518 // Private non-static helper functions (operating on full transition arrays).
    519 
    520 int TransitionArray::SearchDetails(int transition, PropertyKind kind,
    521                                    PropertyAttributes attributes,
    522                                    int* out_insertion_index) {
    523   int nof_transitions = number_of_transitions();
    524   DCHECK(transition < nof_transitions);
    525   Name* key = GetKey(transition);
    526   for (; transition < nof_transitions && GetKey(transition) == key;
    527        transition++) {
    528     Map* target = GetTarget(transition);
    529     PropertyDetails target_details = GetTargetDetails(key, target);
    530 
    531     int cmp = CompareDetails(kind, attributes, target_details.kind(),
    532                              target_details.attributes());
    533     if (cmp == 0) {
    534       return transition;
    535     } else if (cmp < 0) {
    536       break;
    537     }
    538   }
    539   if (out_insertion_index != NULL) *out_insertion_index = transition;
    540   return kNotFound;
    541 }
    542 
    543 
    544 int TransitionArray::Search(PropertyKind kind, Name* name,
    545                             PropertyAttributes attributes,
    546                             int* out_insertion_index) {
    547   int transition = SearchName(name, out_insertion_index);
    548   if (transition == kNotFound) {
    549     return kNotFound;
    550   }
    551   return SearchDetails(transition, kind, attributes, out_insertion_index);
    552 }
    553 }  // namespace internal
    554 }  // namespace v8
    555