1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/transitions.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/objects-inl.h" 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/transitions-inl.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/utils.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 15014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 16014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::Insert(Handle<Map> map, Handle<Name> name, 17014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Map> target, SimpleTransitionFlag flag) { 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Isolate* isolate = map->GetIsolate(); 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch target->SetBackPointer(*map); 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If the map doesn't have any transitions at all yet, install the new one. 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (CanStoreSimpleTransition(map->raw_transitions())) { 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (flag == SIMPLE_PROPERTY_TRANSITION) { 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<WeakCell> cell = Map::WeakCellForMap(target); 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *cell); 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return; 27014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 28014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If the flag requires a full TransitionArray, allocate one. 29014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<TransitionArray> result = Allocate(isolate, 0, 1); 30014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *result); 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 33014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_special_transition = flag == SPECIAL_TRANSITION; 34014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If the map has a simple transition, check if it should be overwritten. 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsSimpleTransition(map->raw_transitions())) { 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* old_target = GetSimpleTransition(map->raw_transitions()); 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Name* key = GetSimpleTransitionKey(old_target); 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails old_details = GetSimpleTargetDetails(old_target); 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails new_details = is_special_transition 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ? PropertyDetails::Empty() 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : GetTargetDetails(*name, *target); 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) && 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch old_details.kind() == new_details.kind() && 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch old_details.attributes() == new_details.attributes()) { 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<WeakCell> cell = Map::WeakCellForMap(target); 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *cell); 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return; 48014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 49014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Otherwise allocate a full TransitionArray with slack for a new entry. 50014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<TransitionArray> result = Allocate(isolate, 1, 1); 51014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Re-read existing data; the allocation might have caused it to be cleared. 52014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsSimpleTransition(map->raw_transitions())) { 53014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch old_target = GetSimpleTransition(map->raw_transitions()); 54014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Set(0, GetSimpleTransitionKey(old_target), old_target); 55014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else { 56014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->SetNumberOfTransitions(0); 57014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 58014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *result); 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // At this point, we know that the map has a full TransitionArray. 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsFullTransitionArray(map->raw_transitions())); 63958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int number_of_transitions = 0; 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int new_nof = 0; 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int insertion_index = kNotFound; 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK_EQ(is_special_transition, IsSpecialTransition(*name)); 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier PropertyDetails details = is_special_transition 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ? PropertyDetails::Empty() 70958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : GetTargetDetails(*name, *target); 71958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch { 73958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DisallowHeapAllocation no_gc; 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* array = TransitionArray::cast(map->raw_transitions()); 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch number_of_transitions = array->number_of_transitions(); 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_nof = number_of_transitions; 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int index = 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch is_special_transition 80014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : array->Search(details.kind(), *name, details.attributes(), 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch &insertion_index); 83014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If an existing entry was found, overwrite it and return. 84958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (index != kNotFound) { 85958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier array->SetTarget(index, *target); 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return; 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 88958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ++new_nof; 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch CHECK(new_nof <= kMaxNumberOfTransitions); 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); 92014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 93014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If there is enough capacity, insert new entry into the existing array. 94014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (new_nof <= Capacity(array)) { 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->SetNumberOfTransitions(new_nof); 96014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (index = number_of_transitions; index > insertion_index; --index) { 97014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->SetKey(index, array->GetKey(index - 1)); 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->SetTarget(index, array->GetTarget(index - 1)); 99014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->SetKey(index, *name); 101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->SetTarget(index, *target); 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SLOW_DCHECK(array->IsSortedNoDuplicates()); 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return; 104958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 105958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 106958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // We're gonna need a bigger TransitionArray. 108958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Handle<TransitionArray> result = Allocate( 109958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier map->GetIsolate(), new_nof, 110958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions)); 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // The map's transition array may have shrunk during the allocation above as 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // it was weakly traversed, though it is guaranteed not to disappear. Trim the 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // result copy if needed, and recompute variables. 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsFullTransitionArray(map->raw_transitions())); 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DisallowHeapAllocation no_gc; 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* array = TransitionArray::cast(map->raw_transitions()); 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (array->number_of_transitions() != number_of_transitions) { 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(array->number_of_transitions() < number_of_transitions); 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch number_of_transitions = array->number_of_transitions(); 122958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier new_nof = number_of_transitions; 123958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 124958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier insertion_index = kNotFound; 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int index = 126014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch is_special_transition 127014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) 128014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : array->Search(details.kind(), *name, details.attributes(), 129014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch &insertion_index); 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (index == kNotFound) { 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ++new_nof; 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } else { 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier insertion_index = index; 134958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 135958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier result->Shrink(ToKeyIndex(new_nof)); 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier result->SetNumberOfTransitions(new_nof); 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (array->HasPrototypeTransitions()) { 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->SetPrototypeTransitions(array->GetPrototypeTransitions()); 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 145958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK_NE(kNotFound, insertion_index); 146958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (int i = 0; i < insertion_index; ++i) { 147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Set(i, array->GetKey(i), array->GetTarget(i)); 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Set(insertion_index, *name, *target); 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (int i = insertion_index; i < number_of_transitions; ++i) { 151014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Set(i + 1, array->GetKey(i), array->GetTarget(i)); 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 154958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SLOW_DCHECK(result->IsSortedNoDuplicates()); 155014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *result); 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 158014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochMap* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name, 161014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyAttributes attributes) { 162109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch DCHECK(name->IsUniqueName()); 163014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 164014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsSimpleTransition(raw_transitions)) { 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* target = GetSimpleTransition(raw_transitions); 166014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Name* key = GetSimpleTransitionKey(target); 167109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch if (key != name) return nullptr; 168014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails details = GetSimpleTargetDetails(target); 169109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch if (details.attributes() != attributes) return nullptr; 170109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch if (details.kind() != kind) return nullptr; 171014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return target; 172014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) { 174014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(raw_transitions); 175014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int transition = transitions->Search(kind, name, attributes); 176109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch if (transition == kNotFound) return nullptr; 177014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return transitions->GetTarget(transition); 178014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 179014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return NULL; 180014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 181014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 182014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 183014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 184014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochMap* TransitionArray::SearchSpecial(Map* map, Symbol* name) { 185014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 186014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) { 187014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(raw_transitions); 188014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int transition = transitions->SearchSpecial(name); 189014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (transition == kNotFound) return NULL; 190014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return transitions->GetTarget(transition); 191014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 192014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return NULL; 193014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 194014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 195014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 196014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 197014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochHandle<Map> TransitionArray::FindTransitionToField(Handle<Map> map, 198014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Name> name) { 199109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch DCHECK(name->IsUniqueName()); 200014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DisallowHeapAllocation no_gc; 201014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* target = SearchTransition(*map, kData, *name, NONE); 202014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (target == NULL) return Handle<Map>::null(); 203014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails details = target->GetLastDescriptorDetails(); 204014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(NONE, details.attributes()); 20562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (details.location() != kField) return Handle<Map>::null(); 20662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch DCHECK_EQ(kData, details.kind()); 207014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Handle<Map>(target); 208014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 209014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 210014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 211014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochHandle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) { 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DisallowHeapAllocation no_gc; 214014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transition = map->raw_transitions(); 215014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!IsSimpleTransition(raw_transition)) return Handle<String>::null(); 216014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* target = GetSimpleTransition(raw_transition); 217014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails details = GetSimpleTargetDetails(target); 21862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (details.location() != kField) return Handle<String>::null(); 21962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch DCHECK_EQ(kData, details.kind()); 220014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (details.attributes() != NONE) return Handle<String>::null(); 221014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Name* name = GetSimpleTransitionKey(target); 222014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!name->IsString()) return Handle<String>::null(); 223014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Handle<String>(String::cast(name)); 224014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 225014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 227014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 228014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) { 229014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (map->is_dictionary_map()) return false; 230014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 231014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) { 232014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(raw_transitions); 233014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return transitions->number_of_transitions() < kMaxNumberOfTransitions; 234014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 235014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return true; 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 239014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 240014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) { 241014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const int header = kProtoTransitionHeaderSize; 242014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int number_of_transitions = NumberOfPrototypeTransitions(array); 243014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (number_of_transitions == 0) { 244014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Empty array cannot be compacted. 245014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return false; 246014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 247014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int new_number_of_transitions = 0; 248014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < number_of_transitions; i++) { 249014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* cell = array->get(header + i); 250014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!WeakCell::cast(cell)->cleared()) { 251014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (new_number_of_transitions != i) { 252014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->set(header + new_number_of_transitions, cell); 253014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 254014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_number_of_transitions++; 255014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 256014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 257014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Fill slots that became free with undefined value. 258014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = new_number_of_transitions; i < number_of_transitions; i++) { 259014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->set_undefined(header + i); 260014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 261014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (number_of_transitions != new_number_of_transitions) { 262014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetNumberOfPrototypeTransitions(array, new_number_of_transitions); 263014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 264014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return new_number_of_transitions < number_of_transitions; 265014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 266014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 267014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 268014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 269014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochHandle<FixedArray> TransitionArray::GrowPrototypeTransitionArray( 270014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<FixedArray> array, int new_capacity, Isolate* isolate) { 271014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Grow array by factor 2 up to MaxCachedPrototypeTransitions. 272014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int capacity = array->length() - kProtoTransitionHeaderSize; 273014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity); 274014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_GT(new_capacity, capacity); 275014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int grow_by = new_capacity - capacity; 276014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED); 277014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (capacity < 0) { 278014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // There was no prototype transitions array before, so the size 279014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // couldn't be copied. Initialize it explicitly. 280014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetNumberOfPrototypeTransitions(*array, 0); 281014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 282014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return array; 283014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 284014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 285014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 286014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 287014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochint TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) { 288014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch FixedArray* transitions = GetPrototypeTransitions(map); 289014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch CompactPrototypeTransitionArray(transitions); 290014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return TransitionArray::NumberOfPrototypeTransitions(transitions); 291014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 292014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 293014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 294014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 295014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::PutPrototypeTransition(Handle<Map> map, 296014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Object> prototype, 297014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Map> target_map) { 298014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(HeapObject::cast(*prototype)->map()->IsMap()); 299014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Don't cache prototype transition if this map is either shared, or a map of 300014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // a prototype. 301014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (map->is_prototype_map()) return; 302014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return; 303014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 304014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const int header = kProtoTransitionHeaderSize; 305014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 306014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map); 307014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 308014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<FixedArray> cache(GetPrototypeTransitions(*map)); 309014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int capacity = cache->length() - header; 310014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int transitions = NumberOfPrototypeTransitions(*cache) + 1; 311014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 312014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (transitions > capacity) { 313014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Grow the array if compacting it doesn't free space. 314014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!CompactPrototypeTransitionArray(*cache)) { 315014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (capacity == kMaxCachedPrototypeTransitions) return; 316014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch cache = GrowPrototypeTransitionArray(cache, 2 * transitions, 317014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch map->GetIsolate()); 318014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetPrototypeTransitions(map, cache); 319014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 320014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 321014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 322014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Reload number of transitions as they might have been compacted. 323014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int last = NumberOfPrototypeTransitions(*cache); 324014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int entry = header + last; 325014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 326014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch cache->set(entry, *target_cell); 327014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetNumberOfPrototypeTransitions(*cache, last + 1); 328014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 329014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 330014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 331014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 332014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochHandle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map, 333014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Object> prototype) { 334014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DisallowHeapAllocation no_gc; 335014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch FixedArray* cache = GetPrototypeTransitions(*map); 336014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int number_of_transitions = NumberOfPrototypeTransitions(cache); 337014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < number_of_transitions; i++) { 338014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch WeakCell* target_cell = 339014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch WeakCell::cast(cache->get(kProtoTransitionHeaderSize + i)); 340014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!target_cell->cleared() && 341014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map::cast(target_cell->value())->prototype() == *prototype) { 342014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return handle(Map::cast(target_cell->value())); 343014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 344014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 345014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Handle<Map>(); 346014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 347014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 348014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 349014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 350014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochFixedArray* TransitionArray::GetPrototypeTransitions(Map* map) { 351014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 352014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Heap* heap = map->GetHeap(); 353014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!IsFullTransitionArray(raw_transitions)) { 354014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return heap->empty_fixed_array(); 355014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 356014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(raw_transitions); 357014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!transitions->HasPrototypeTransitions()) { 358014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return heap->empty_fixed_array(); 359014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 360014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return transitions->GetPrototypeTransitions(); 361014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 362014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 363014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 364014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 365014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::SetNumberOfPrototypeTransitions( 366014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch FixedArray* proto_transitions, int value) { 367014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(proto_transitions->length() != 0); 368014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch proto_transitions->set(kProtoTransitionNumberOfEntriesOffset, 369014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Smi::FromInt(value)); 370014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 371014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 372014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 373014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 374014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochint TransitionArray::NumberOfTransitions(Object* raw_transitions) { 375014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (CanStoreSimpleTransition(raw_transitions)) return 0; 376014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsSimpleTransition(raw_transitions)) return 1; 377014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Prototype maps don't have transitions. 378014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (raw_transitions->IsPrototypeInfo()) return 0; 379014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsFullTransitionArray(raw_transitions)); 380014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return TransitionArray::cast(raw_transitions)->number_of_transitions(); 381014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 382014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 383014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 384014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 385014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochint TransitionArray::Capacity(Object* raw_transitions) { 386014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!IsFullTransitionArray(raw_transitions)) return 1; 387014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* t = TransitionArray::cast(raw_transitions); 388014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (t->length() <= kFirstIndex) return 0; 389014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return (t->length() - kFirstIndex) / kTransitionSize; 390014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 391014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 392014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 393014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Private static helper functions. 394014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 395014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochHandle<TransitionArray> TransitionArray::Allocate(Isolate* isolate, 396014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int number_of_transitions, 397014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int slack) { 398014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<FixedArray> array = isolate->factory()->NewTransitionArray( 399014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LengthFor(number_of_transitions + slack)); 400c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch array->set(kPrototypeTransitionsIndex, Smi::kZero); 401014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions)); 402014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Handle<TransitionArray>::cast(array); 403014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 404014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 405014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 406014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 407014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::ZapTransitionArray(TransitionArray* transitions) { 408014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Do not zap the next link that is used by GC. 409014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch STATIC_ASSERT(kNextLinkIndex + 1 == kPrototypeTransitionsIndex); 410014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MemsetPointer(transitions->data_start() + kPrototypeTransitionsIndex, 411014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch transitions->GetHeap()->the_hole_value(), 412014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch transitions->length() - kPrototypeTransitionsIndex); 413014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch transitions->SetNumberOfTransitions(0); 414014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 415014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 416014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 417014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::ReplaceTransitions(Handle<Map> map, 418014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* new_transitions) { 419014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 420014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) { 421014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* old_transitions = TransitionArray::cast(raw_transitions); 422014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#ifdef DEBUG 423014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions); 424014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(old_transitions != new_transitions); 425014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif 426014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Transition arrays are not shared. When one is replaced, it should not 427014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // keep referenced objects alive, so we zap it. 428014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // When there is another reference to the array somewhere (e.g. a handle), 429014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // not zapping turns from a waste of memory into a source of crashes. 430014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZapTransitionArray(old_transitions); 431014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 432014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch map->set_raw_transitions(new_transitions); 433014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 434014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 435014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 436014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::SetPrototypeTransitions( 437014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Map> map, Handle<FixedArray> proto_transitions) { 438014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch EnsureHasFullTransitionArray(map); 439014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(map->raw_transitions()); 440014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch transitions->SetPrototypeTransitions(*proto_transitions); 441014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 442014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 443014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 444014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) { 445014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 446014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) return; 447014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 448014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof); 449014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DisallowHeapAllocation no_gc; 450014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Reload pointer after the allocation that just happened. 451014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch raw_transitions = map->raw_transitions(); 452014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 453014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (new_nof != nof) { 454014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(new_nof == 0); 455014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Shrink(ToKeyIndex(0)); 456014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->SetNumberOfTransitions(0); 457014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else if (nof == 1) { 458014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* target = GetSimpleTransition(raw_transitions); 459014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Name* key = GetSimpleTransitionKey(target); 460014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result->Set(0, key, target); 461014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 462014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReplaceTransitions(map, *result); 463014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 464014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 465014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 466014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::TraverseTransitionTreeInternal(Map* map, 467014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TraverseCallback callback, 468014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void* data) { 469014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Object* raw_transitions = map->raw_transitions(); 470014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (IsFullTransitionArray(raw_transitions)) { 471014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* transitions = TransitionArray::cast(raw_transitions); 472014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (transitions->HasPrototypeTransitions()) { 473014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch FixedArray* proto_trans = transitions->GetPrototypeTransitions(); 474014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) { 475014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int index = TransitionArray::kProtoTransitionHeaderSize + i; 476014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch WeakCell* cell = WeakCell::cast(proto_trans->get(index)); 477014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!cell->cleared()) { 478014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TraverseTransitionTreeInternal(Map::cast(cell->value()), callback, 479014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch data); 480014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 481014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 482014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 483014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < transitions->number_of_transitions(); ++i) { 484014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data); 485014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 486014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else if (IsSimpleTransition(raw_transitions)) { 487014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions), 488014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch callback, data); 489014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 490014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch callback(map, data); 491014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 492014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 493014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 494014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#ifdef DEBUG 495014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid TransitionArray::CheckNewTransitionsAreConsistent( 496014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Handle<Map> map, TransitionArray* old_transitions, Object* transitions) { 497014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This function only handles full transition arrays. 498014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsFullTransitionArray(transitions)); 499014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray* new_transitions = TransitionArray::cast(transitions); 500014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < old_transitions->number_of_transitions(); i++) { 501014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Map* target = old_transitions->GetTarget(i); 502014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (target->instance_descriptors() == map->instance_descriptors()) { 503014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Name* key = old_transitions->GetKey(i); 504014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int new_target_index; 505014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (TransitionArray::IsSpecialTransition(key)) { 506014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_target_index = new_transitions->SearchSpecial(Symbol::cast(key)); 507014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else { 508014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropertyDetails details = 509014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TransitionArray::GetTargetDetails(key, target); 510014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_target_index = 511014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new_transitions->Search(details.kind(), key, details.attributes()); 512014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 513014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NE(TransitionArray::kNotFound, new_target_index); 514014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(target, new_transitions->GetTarget(new_target_index)); 515014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 516014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 517014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 518014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif 519014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 520014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 521014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Private non-static helper functions (operating on full transition arrays). 522014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 523958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierint TransitionArray::SearchDetails(int transition, PropertyKind kind, 524958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier PropertyAttributes attributes, 525958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int* out_insertion_index) { 526958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int nof_transitions = number_of_transitions(); 527958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK(transition < nof_transitions); 528958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Name* key = GetKey(transition); 529958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (; transition < nof_transitions && GetKey(transition) == key; 530958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier transition++) { 531958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Map* target = GetTarget(transition); 532958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier PropertyDetails target_details = GetTargetDetails(key, target); 533958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 534958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int cmp = CompareDetails(kind, attributes, target_details.kind(), 535958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier target_details.attributes()); 536958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (cmp == 0) { 537958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return transition; 538958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } else if (cmp < 0) { 539958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier break; 540958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 541958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 542958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (out_insertion_index != NULL) *out_insertion_index = transition; 543958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return kNotFound; 544958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 545958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 546958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 547958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierint TransitionArray::Search(PropertyKind kind, Name* name, 548958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier PropertyAttributes attributes, 549958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int* out_insertion_index) { 550958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int transition = SearchName(name, out_insertion_index); 551109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch if (transition == kNotFound) return kNotFound; 552958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return SearchDetails(transition, kind, attributes, out_insertion_index); 553958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 554014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 555014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 556