// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/objects/transitions.h"
#include <optional>
#include "src/base/small-vector.h"
#include "src/objects/objects-inl.h"
#include "src/objects/transitions-inl.h"
#include "src/utils/utils.h"
namespace v8::internal {
// static
Tagged<Map> TransitionsAccessor::GetSimpleTransition(Isolate* isolate,
DirectHandle<Map> map) {
Tagged<MaybeObject> raw_transitions = map->raw_transitions(kAcquireLoad);
switch (GetEncoding(isolate, raw_transitions)) {
case kWeakRef:
return Cast<Map>(raw_transitions.GetHeapObjectAssumeWeak());
default:
return {};
}
}
bool TransitionsAccessor::HasSimpleTransitionTo(Tagged<Map> map) {
switch (encoding()) {
case kWeakRef:
return raw_transitions_.GetHeapObjectAssumeWeak() == map;
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
case kFullTransitionArray:
return false;
}
UNREACHABLE();
}
// static
void TransitionsAccessor::InsertHelper(Isolate* isolate, DirectHandle<Map> map,
DirectHandle<Name> name,
DirectHandle<Map> target,
TransitionKindFlag flag) {
DCHECK_NE(flag, PROTOTYPE_TRANSITION);
Encoding encoding = GetEncoding(isolate, map);
DCHECK_NE(kPrototypeInfo, encoding);
ReadOnlyRoots roots(isolate);
(*target)->SetBackPointer(*map);
// If the map doesn't have any transitions at all yet, install the new one.
if (encoding == kUninitialized || encoding == kMigrationTarget) {
if (flag == SIMPLE_PROPERTY_TRANSITION) {
ReplaceTransitions(isolate, map, MakeWeak(*target));
return;
}
// If the flag requires a full TransitionArray, allocate one.
DirectHandle<TransitionArray> result =
isolate->factory()->NewTransitionArray(1, 0);
result->Set(0, *name, MakeWeak(*target));
ReplaceTransitions(isolate, map, result);
DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
return;
}
if (encoding == kWeakRef) {
Tagged<Map> simple_transition = GetSimpleTransition(isolate, map);
DCHECK(!simple_transition.is_null());
if (flag == SIMPLE_PROPERTY_TRANSITION) {
Tagged<Name> key = GetSimpleTransitionKey(simple_transition);
PropertyDetails old_details =
simple_transition->GetLastDescriptorDetails();
PropertyDetails new_details = GetTargetDetails(*name, *target);
if (key->Equals(*name) && old_details.kind() == new_details.kind() &&
old_details.attributes() == new_details.attributes()) {
ReplaceTransitions(isolate, map, MakeWeak(*target));
return;
}
}
// Otherwise allocate a full TransitionArray with slack for a new entry.
DirectHandle<TransitionArray> result =
isolate->factory()->NewTransitionArray(1, 1);
// Reload `simple_transition`. Allocations might have caused it to be
// cleared.
simple_transition = GetSimpleTransition(isolate, map);
if (simple_transition.is_null()) {
result->Set(0, *name, MakeWeak(*target));
ReplaceTransitions(isolate, map, result);
DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
return;
}
// Insert the original transition in index 0.
result->Set(0, GetSimpleTransitionKey(simple_transition),
MakeWeak(simple_transition));
// Search for the correct index to insert the new transition.
int insertion_index;
int index;
if (flag == SPECIAL_TRANSITION) {
index =
result->SearchSpecial(Cast<Symbol>(*name), false, &insertion_index);
} else {
PropertyDetails details = GetTargetDetails(*name, *target);
index = result->Search(details.kind(), *name, details.attributes(),
&insertion_index);
}
DCHECK_EQ(index, kNotFound);
USE(index);
result->SetNumberOfTransitions(2);
if (insertion_index == 0) {
// If the new transition will be inserted in index 0, move the original
// transition to index 1.
result->Set(1, GetSimpleTransitionKey(simple_transition),
MakeWeak(simple_transition));
}
result->SetKey(insertion_index, *name);
result->SetRawTarget(insertion_index, MakeWeak(*target));
SLOW_DCHECK(result->IsSortedNoDuplicates());
ReplaceTransitions(isolate, map, result);
DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, *result));
return;
}
// At this point, we know that the map has a full TransitionArray.
DCHECK_EQ(kFullTransitionArray, encoding);
int number_of_transitions = 0;
int new_nof = 0;
int insertion_index = kNotFound;
const bool is_special_transition = flag == SPECIAL_TRANSITION;
DCHECK_EQ(is_special_transition, IsSpecialTransition(roots, *name));
PropertyDetails details = is_special_transition
? PropertyDetails::Empty()
: GetTargetDetails(*name, *target);
{
DisallowGarbageCollection no_gc;
Tagged<TransitionArray> array = GetTransitionArray(isolate, map);
number_of_transitions = array->number_of_transitions();
int index =
is_special_transition
? array->SearchSpecial(Cast<Symbol>(*name), false, &insertion_index)
: array->Search(details.kind(), *name, details.attributes(),
&insertion_index);
// If an existing entry was found, overwrite it and return.
if (index != kNotFound) {
base::MutexGuard mutex_guard(isolate->full_transition_array_access());
array->SetRawTarget(index, MakeWeak(*target));
return;
}
new_nof = number_of_transitions + 1;
CHECK_LE(new_nof, kMaxNumberOfTransitions);
DCHECK_GE(insertion_index, 0);
DCHECK_LE(insertion_index, number_of_transitions);
// If there is enough capacity, insert new entry into the existing array.
if (new_nof <= array->Capacity()) {
base::MutexGuard mutex_guard(isolate->full_transition_array_access());
array->SetNumberOfTransitions(new_nof);
for (int i = number_of_transitions; i > insertion_index; --i) {
array->SetKey(i, array->GetKey(i - 1));
array->SetRawTarget(i, array->GetRawTarget(i - 1));
}
array->SetKey(insertion_index, *name);
array->SetRawTarget(insertion_index, MakeWeak(*target));
// The new size exceeds the threshold for linear search, sort the array
// for binary search later.
if (new_nof == TransitionArray::kMaxElementsForLinearSearch + 1) {
array->Sort();
}
SLOW_DCHECK(array->IsSortedNoDuplicates());
return;
}
}
// We're gonna need a bigger TransitionArray.
int slack =
Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions);
// TODO(375937549): Convert these to uint32_t.
DCHECK_GE(new_nof, 0);
DCHECK_GE(slack, 0);
DirectHandle<TransitionArray> result = isolate->factory()->NewTransitionArray(
static_cast<uint32_t>(new_nof), static_cast<uint32_t>(slack));
// The map's transition array may have shrunk during the allocation above as
// it was weakly traversed, though it is guaranteed not to disappear. Trim the
// result copy if needed, and recompute variables.
DisallowGarbageCollection no_gc;
Tagged<TransitionArray> array = GetTransitionArray(isolate, map);
if (array->number_of_transitions() != number_of_transitions) {
DCHECK_LT(array->number_of_transitions(), number_of_transitions);
int index =
is_special_transition
? array->SearchSpecial(Cast<Symbol>(*name), false, &insertion_index)
: array->Search(details.kind(), *name, details.attributes(),
&insertion_index);
CHECK_EQ(index, kNotFound);
USE(index);
DCHECK_GE(insertion_index, 0);
DCHECK_LE(insertion_index, number_of_transitions);
number_of_transitions = array->number_of_transitions();
new_nof = number_of_transitions + 1;
result->SetNumberOfTransitions(new_nof);
}
if (array->HasPrototypeTransitions()) {
result->SetPrototypeTransitions(array->GetPrototypeTransitions());
}
if (array->HasSideStepTransitions()) {
result->SetSideStepTransitions(array->GetSideStepTransitions());
}
DCHECK_NE(kNotFound, insertion_index);
for (int i = 0; i < insertion_index; ++i) {
result->Set(i, array->GetKey(i), array->GetRawTarget(i));
}
result->Set(insertion_index, *name, MakeWeak(*target));
for (int i = insertion_index; i < number_of_transitions; ++i) {
result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i));
}
// The new size exceeds the threshold for linear search, sort the array
// for binary search later.
if (new_nof == TransitionArray::kMaxElementsForLinearSearch + 1) {
result->Sort();
}
SLOW_DCHECK(result->IsSortedNoDuplicates());
ReplaceTransitions(isolate, map, result);
}
Tagged<Map> TransitionsAccessor::SearchTransition(
Tagged<Name> name, PropertyKind kind, PropertyAttributes attributes) {
DCHECK(IsUniqueName(name));
switch (encoding()) {
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
return {};
case kWeakRef: {
Tagged<Map> map = Cast<Map>(raw_transitions_.GetHeapObjectAssumeWeak());
if (!IsMatchingMap(map, name, kind, attributes)) return {};
return map;
}
case kFullTransitionArray: {
base::MutexGuardIf guard(isolate_->full_transition_array_access(),
concurrent_access_);
return transitions()->SearchAndGetTarget(kind, name, attributes);
}
}
UNREACHABLE();
}
Tagged<Map> TransitionsAccessor::SearchSpecial(Tagged<Symbol> name) {
if (encoding() != kFullTransitionArray) return {};
base::MutexGuardIf guard(isolate_->full_transition_array_access(),
concurrent_access_);
int transition = transitions()->SearchSpecial(name, concurrent_access_);
if (transition == kNotFound) return {};
return transitions()->GetTarget(transition);
}
// static
bool TransitionsAccessor::IsSpecialTransition(ReadOnlyRoots roots,
Tagged<Name> name) {
if (!IsSymbol(name)) return false;
return name == roots.nonextensible_symbol() ||
name == roots.sealed_symbol() || name == roots.frozen_symbol() ||
name == roots.elements_transition_symbol() ||
name == roots.strict_function_transition_symbol() ||
name == roots.detached_symbol();
}
MaybeHandle<Map> TransitionsAccessor::FindTransitionToField(
DirectHandle<String> name) {
DCHECK(IsInternalizedString(*name));
DisallowGarbageCollection no_gc;
Tagged<Map> target = SearchTransition(*name, PropertyKind::kData, NONE);
if (target.is_null()) return MaybeHandle<Map>();
#ifdef DEBUG
PropertyDetails details = target->GetLastDescriptorDetails();
DCHECK_EQ(NONE, details.attributes());
DCHECK_EQ(PropertyKind::kData, details.kind());
DCHECK_EQ(PropertyLocation::kField, details.location());
#endif
return Handle<Map>(target, isolate_);
}
void TransitionsAccessor::ForEachTransitionTo(
Tagged<Name> name, const ForEachTransitionCallback& callback,
DisallowGarbageCollection* no_gc) {
DCHECK(IsUniqueName(name));
switch (encoding()) {
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
return;
case kWeakRef: {
Tagged<Map> target =
Cast<Map>(raw_transitions_.GetHeapObjectAssumeWeak());
InternalIndex descriptor = target->LastAdded();
Tagged<DescriptorArray> descriptors =
target->instance_descriptors(kAcquireLoad);
Tagged<Name> key = descriptors->GetKey(descriptor);
if (key == name) {
callback(target);
}
return;
}
case kFullTransitionArray: {
base::MutexGuardIf guard(isolate_->full_transition_array_access(),
concurrent_access_);
return transitions()->ForEachTransitionTo(name, callback);
}
}
UNREACHABLE();
}
// static
bool TransitionsAccessor::CanHaveMoreTransitions(Isolate* isolate,
DirectHandle<Map> map) {
if (map->is_dictionary_map()) return false;
Tagged<MaybeObject> raw_transitions = map->raw_transitions(kAcquireLoad);
if (GetEncoding(isolate, raw_transitions) == kFullTransitionArray) {
return GetTransitionArray(isolate, raw_transitions)
->number_of_transitions() < kMaxNumberOfTransitions;
}
return true;
}
// static
bool TransitionsAccessor::IsMatchingMap(Tagged<Map> target, Tagged<Name> name,
PropertyKind kind,
PropertyAttributes attributes) {
InternalIndex descriptor = target->LastAdded();
Tagged<DescriptorArray> descriptors =
target->instance_descriptors(kAcquireLoad);
Tagged<Name> key = descriptors->GetKey(descriptor);
if (key != name) return false;
return descriptors->GetDetails(descriptor)
.HasKindAndAttributes(kind, attributes);
}
// static
bool TransitionArray::CompactPrototypeTransitionArray(
Isolate* isolate, Tagged<WeakFixedArray> array) {
const uint32_t header = kProtoTransitionHeaderSize;
const uint32_t number_of_transitions = NumberOfPrototypeTransitions(array);
if (number_of_transitions == 0) {
// Empty array cannot be compacted.
return false;
}
uint32_t new_number_of_transitions = 0;
for (uint32_t i = 0; i < number_of_transitions; i++) {
Tagged<MaybeObject> target = array->get(header + i);
DCHECK(target.IsCleared() ||
(target.IsWeak() && IsMap(target.GetHeapObject())));
if (!target.IsCleared()) {
if (new_number_of_transitions != i) {
array->set(header + new_number_of_transitions, target);
}
new_number_of_transitions++;
}
}
// Fill slots that became free with undefined value.
Tagged<MaybeObject> undefined = *isolate->factory()->undefined_value();
for (uint32_t i = new_number_of_transitions; i < number_of_transitions; i++) {
array->set(header + i, undefined);
}
if (number_of_transitions != new_number_of_transitions) {
SetNumberOfPrototypeTransitions(array, new_number_of_transitions);
}
return new_number_of_transitions < number_of_transitions;
}
// static
DirectHandle<WeakFixedArray> TransitionArray::GrowPrototypeTransitionArray(
DirectHandle<WeakFixedArray> array, uint32_t new_capacity,
Isolate* isolate) {
// Grow array by factor 2 up to MaxCachedPrototypeTransitions.
const uint32_t array_len = array->ulength().value();
const uint32_t capacity = array_len >= kProtoTransitionHeaderSize
? array_len - kProtoTransitionHeaderSize
: 0;
new_capacity = std::min({kMaxCachedPrototypeTransitions, new_capacity});
DCHECK_GT(new_capacity, capacity);
const uint32_t grow_by = new_capacity - capacity;
DirectHandle<WeakFixedArray> new_array =
isolate->factory()->CopyWeakFixedArrayAndGrow(array, grow_by);
if (capacity == 0) {
// There was no prototype transitions array before, so the size
// couldn't be copied. Initialize it explicitly.
SetNumberOfPrototypeTransitions(*new_array, 0);
}
return new_array;
}
// static
bool TransitionsAccessor::PutPrototypeTransition(Isolate* isolate,
DirectHandle<Map> map,
DirectHandle<Object> prototype,
DirectHandle<Map> target_map) {
DCHECK(IsUndefined(map->GetBackPointer()));
DCHECK_NE(map->prototype(), *prototype);
DCHECK(IsMap(Cast<HeapObject>(*prototype)->map()));
// Only the main thread should write to transition arrays.
DCHECK_EQ(ThreadId::Current(), isolate->thread_id());
// It's OK to read the transition array without holding the
// full_transition_array_access lock in read mode, since this is only called
// in the main thread, and the main thread is the only writer. In addition, we
// shouldn't GC while holding the lock, because it will cause a deadlock if a
// background thread is waiting for the shared mutex outside of a safepoint.
// Don't cache prototype transition if this map is either shared, or a map of
// a prototype.
if (map->is_prototype_map()) return false;
if (map->is_dictionary_map() || !v8_flags.cache_prototype_transitions) {
return false;
}
const uint32_t header = TransitionArray::kProtoTransitionHeaderSize;
DirectHandle<WeakFixedArray> cache(
TransitionsAccessor(isolate, *map).GetPrototypeTransitions(), isolate);
const uint32_t cache_len = cache->ulength().value();
const uint32_t capacity = cache_len >= header ? cache_len - header : 0;
const uint32_t transitions =
TransitionArray::NumberOfPrototypeTransitions(*cache) + 1;
if (transitions > capacity) {
// Grow the array if compacting it doesn't free space.
bool compacted;
{
base::MutexGuard guard(isolate->full_transition_array_access());
DisallowGarbageCollection no_gc;
compacted =
TransitionArray::CompactPrototypeTransitionArray(isolate, *cache);
}
if (!compacted) {
if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) {
return false;
}
cache = TransitionArray::GrowPrototypeTransitionArray(
cache, 2 * transitions, isolate);
SetPrototypeTransitions(isolate, map, cache);
}
}
target_map->SetBackPointer(*map);
// Reload number of transitions as they might have been compacted.
const uint32_t last = TransitionArray::NumberOfPrototypeTransitions(*cache);
const uint32_t entry = header + last;
{
base::MutexGuard guard(isolate->full_transition_array_access());
DisallowGarbageCollection no_gc;
cache->set(entry, MakeWeak(*target_map));
TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1);
}
return true;
}
std::optional<Tagged<Map>> TransitionsAccessor::GetPrototypeTransition(
Tagged<Object> prototype) {
DisallowGarbageCollection no_gc;
if (encoding() != kFullTransitionArray) return {};
base::MutexGuardIf guard(isolate_->full_transition_array_access(),
concurrent_access_);
Tagged<WeakFixedArray> cache = GetPrototypeTransitions();
const uint32_t length = TransitionArray::NumberOfPrototypeTransitions(cache);
for (uint32_t i = 0; i < length; i++) {
Tagged<MaybeObject> target =
cache->get(TransitionArray::kProtoTransitionHeaderSize + i);
DCHECK(target.IsWeakOrCleared());
Tagged<HeapObject> heap_object;
if (target.GetHeapObjectIfWeak(&heap_object)) {
Tagged<Map> target_map = Cast<Map>(heap_object);
if (target_map->prototype() == prototype) {
return target_map;
}
}
}
return {};
}
Tagged<WeakFixedArray> TransitionsAccessor::GetPrototypeTransitions() {
if (!HasPrototypeTransitions()) {
return ReadOnlyRoots(isolate_).empty_weak_fixed_array();
}
return transitions()->GetPrototypeTransitions();
}
// static
void TransitionArray::SetNumberOfPrototypeTransitions(
Tagged<WeakFixedArray> proto_transitions, uint32_t value) {
DCHECK_NE(proto_transitions->ulength().value(), 0);
proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
Smi::FromUInt(value));
}
int TransitionsAccessor::NumberOfTransitions() {
switch (encoding()) {
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
return 0;
case kWeakRef:
return 1;
case kFullTransitionArray:
return transitions()->number_of_transitions();
}
UNREACHABLE();
}
bool TransitionsAccessor::HasPrototypeTransitions() {
switch (encoding()) {
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
case kWeakRef:
return false;
case kFullTransitionArray:
return transitions()->HasPrototypeTransitions();
}
UNREACHABLE();
}
// static
void TransitionsAccessor::SetMigrationTarget(Isolate* isolate,
DirectHandle<Map> map,
Tagged<Map> migration_target) {
// We only cache the migration target for maps with empty transitions for GC's
// sake.
if (GetEncoding(isolate, map) != kUninitialized) return;
DCHECK(map->is_deprecated());
map->set_raw_transitions(migration_target, kReleaseStore);
}
Tagged<Map> TransitionsAccessor::GetMigrationTarget() {
if (encoding() == kMigrationTarget) {
return Cast<Map>(map_->raw_transitions(kAcquireLoad));
}
return {};
}
// static
void TransitionsAccessor::ReplaceTransitions(
Isolate* isolate, DirectHandle<Map> map,
Tagged<UnionOf<TransitionArray, MaybeWeak<Map>>> new_transitions) {
#if DEBUG
if (GetEncoding(isolate, map) == kFullTransitionArray) {
CheckNewTransitionsAreConsistent(
isolate, map, new_transitions.GetHeapObjectAssumeStrong());
DCHECK_NE(GetTransitionArray(isolate, map),
new_transitions.GetHeapObjectAssumeStrong());
}
#endif
map->set_raw_transitions(new_transitions, kReleaseStore);
USE(isolate);
}
// static
void TransitionsAccessor::ReplaceTransitions(
Isolate* isolate, DirectHandle<Map> map,
DirectHandle<TransitionArray> new_transitions) {
ReplaceTransitions(isolate, map, *new_transitions);
}
// static
void TransitionsAccessor::SetPrototypeTransitions(
Isolate* isolate, DirectHandle<Map> map,
DirectHandle<WeakFixedArray> proto_transitions) {
EnsureHasFullTransitionArray(isolate, map);
GetTransitionArray(isolate, map->raw_transitions(kAcquireLoad))
->SetPrototypeTransitions(*proto_transitions);
}
// static
void TransitionsAccessor::EnsureHasFullTransitionArray(Isolate* isolate,
DirectHandle<Map> map) {
Encoding encoding = GetEncoding(isolate, map->raw_transitions(kAcquireLoad));
if (encoding == kFullTransitionArray) return;
uint32_t nof =
(encoding == kUninitialized || encoding == kMigrationTarget) ? 0 : 1;
DirectHandle<TransitionArray> result =
isolate->factory()->NewTransitionArray(nof);
// Reload encoding after possible GC.
encoding = GetEncoding(isolate, map->raw_transitions(kAcquireLoad));
if (nof == 1) {
if (encoding == kUninitialized) {
// If allocation caused GC and cleared the target, trim the new array.
result->SetNumberOfTransitions(0);
} else {
// Otherwise populate the new array.
Tagged<Map> target = GetSimpleTransition(isolate, map);
Tagged<Name> key = GetSimpleTransitionKey(target);
result->Set(0, key, MakeWeak(target));
}
}
ReplaceTransitions(isolate, map, result);
}
void TransitionsAccessor::TraverseTransitionTreeInternal(
const TraverseCallback& callback, DisallowGarbageCollection* no_gc) {
// Mostly arbitrary but more than enough to run the test suite in static
// memory.
static constexpr int kStaticStackSize = 16;
base::SmallVector<Tagged<Map>, kStaticStackSize> stack;
stack.emplace_back(map_);
// Pre-order iterative depth-first-search.
while (!stack.empty()) {
Tagged<Map> current_map = stack.back();
stack.pop_back();
callback(current_map);
Tagged<MaybeObject> raw_transitions =
current_map->raw_transitions(kAcquireLoad);
Encoding encoding = GetEncoding(isolate_, raw_transitions);
switch (encoding) {
case kPrototypeInfo:
case kPrototypeSharedClosureInfo:
case kUninitialized:
case kMigrationTarget:
break;
case kWeakRef: {
stack.emplace_back(
Cast<Map>(raw_transitions.GetHeapObjectAssumeWeak()));
break;
}
case kFullTransitionArray: {
Tagged<TransitionArray> transitions =
Cast<TransitionArray>(raw_transitions.GetHeapObjectAssumeStrong());
if (transitions->HasPrototypeTransitions()) {
Tagged<WeakFixedArray> proto_trans =
transitions->GetPrototypeTransitions();
const uint32_t length =
TransitionArray::NumberOfPrototypeTransitions(proto_trans);
for (uint32_t i = 0; i < length; ++i) {
uint32_t index = TransitionArray::kProtoTransitionHeaderSize + i;
Tagged<MaybeObject> target = proto_trans->get(index);
Tagged<HeapObject> heap_object;
if (target.GetHeapObjectIfWeak(&heap_object)) {
stack.emplace_back(Cast<Map>(heap_object));
} else {
DCHECK(target.IsCleared());
}
}
}
ReadOnlyRoots roots(isolate_);
for (int i = 0; i < transitions->number_of_transitions(); ++i) {
stack.emplace_back(transitions->GetTarget(i));
}
break;
}
}
}
}
#ifdef DEBUG
// static
void TransitionsAccessor::CheckNewTransitionsAreConsistent(
Isolate* isolate, DirectHandle<Map> map, Tagged<Object> transitions) {
// This function only handles full transition arrays.
Tagged<TransitionArray> old_transitions = GetTransitionArray(isolate, map);
DCHECK_EQ(kFullTransitionArray, GetEncoding(isolate, old_transitions));
Tagged<TransitionArray> new_transitions = Cast<TransitionArray>(transitions);
ReadOnlyRoots roots(isolate);
for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
Tagged<Map> target;
if (old_transitions->GetTargetIfExists(i, isolate, &target)) {
if (target->instance_descriptors() == map->instance_descriptors()) {
Tagged<Name> key = old_transitions->GetKey(i);
int new_target_index;
if (IsSpecialTransition(roots, key)) {
new_target_index = new_transitions->SearchSpecial(Cast<Symbol>(key));
} else {
PropertyDetails details = GetTargetDetails(key, target);
new_target_index = new_transitions->Search(details.kind(), key,
details.attributes());
}
DCHECK_NE(TransitionArray::kNotFound, new_target_index);
DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
}
} else {
DCHECK(IsSpecialTransition(roots, old_transitions->GetKey(i)));
}
}
}
#endif
// Private non-static helper functions (operating on full transition arrays).
int TransitionArray::SearchDetails(int transition, PropertyKind kind,
PropertyAttributes attributes,
int* out_insertion_index) {
int nof_transitions = number_of_transitions();
DCHECK(transition < nof_transitions);
Tagged<Name> key = GetKey(transition);
for (; transition < nof_transitions && GetKey(transition) == key;
transition++) {
Tagged<Map> target = GetTarget(transition);
PropertyDetails target_details =
TransitionsAccessor::GetTargetDetails(key, target);
int cmp = CompareDetails(kind, attributes, target_details.kind(),
target_details.attributes());
if (cmp == 0) {
return transition;
} else if (cmp < 0) {
break;
}
}
if (out_insertion_index != nullptr) *out_insertion_index = transition;
return kNotFound;
}
Tagged<Map> TransitionArray::SearchDetailsAndGetTarget(
int transition, PropertyKind kind, PropertyAttributes attributes) {
int nof_transitions = number_of_transitions();
DCHECK(transition < nof_transitions);
Tagged<Name> key = GetKey(transition);
for (; transition < nof_transitions && GetKey(transition) == key;
transition++) {
Tagged<Map> target = GetTarget(transition);
PropertyDetails target_details =
TransitionsAccessor::GetTargetDetails(key, target);
int cmp = CompareDetails(kind, attributes, target_details.kind(),
target_details.attributes());
if (cmp == 0) {
return target;
} else if (cmp < 0) {
break;
}
}
return {};
}
int TransitionArray::Search(PropertyKind kind, Tagged<Name> name,
PropertyAttributes attributes,
int* out_insertion_index) {
int transition = SearchName(name, false, out_insertion_index);
if (transition == kNotFound) return kNotFound;
return SearchDetails(transition, kind, attributes, out_insertion_index);
}
Tagged<Map> TransitionArray::SearchAndGetTarget(PropertyKind kind,
Tagged<Name> name,
PropertyAttributes attributes) {
int transition = SearchName(name);
if (transition == kNotFound) {
return {};
}
return SearchDetailsAndGetTarget(transition, kind, attributes);
}
void TransitionArray::ForEachTransitionTo(
Tagged<Name> name, const ForEachTransitionCallback& callback) {
int transition = SearchName(name);
if (transition == kNotFound) return;
int nof_transitions = number_of_transitions();
DCHECK(transition < nof_transitions);
Tagged<Name> key = GetKey(transition);
for (; transition < nof_transitions && GetKey(transition) == key;
transition++) {
Tagged<Map> target = GetTarget(transition);
callback(target);
}
}
void TransitionArray::Sort(bool force) {
DisallowGarbageCollection no_gc;
// In-place insertion sort.
int length = number_of_transitions();
// After rehashing, the arrays are no longer in hash-sorted order.
// In this case, we need to force a re-sort even for small arrays,
// so that subsequent linear searches can find the correct transition
// and avoid inserting duplicates.
if (!force && length <= kMaxElementsForLinearSearch) return;
ReadOnlyRoots roots = GetReadOnlyRoots();
for (int i = 1; i < length; i++) {
Tagged<Name> key = GetKey(i);
Tagged<MaybeObject> target = GetRawTarget(i);
PropertyKind kind = PropertyKind::kData;
PropertyAttributes attributes = NONE;
if (!TransitionsAccessor::IsSpecialTransition(roots, key)) {
Tagged<Map> target_map = TransitionsAccessor::GetTargetFromRaw(target);
PropertyDetails details =
TransitionsAccessor::GetTargetDetails(key, target_map);
kind = details.kind();
attributes = details.attributes();
}
int j;
for (j = i - 1; j >= 0; j--) {
Tagged<Name> temp_key = GetKey(j);
Tagged<MaybeObject> temp_target = GetRawTarget(j);
PropertyKind temp_kind = PropertyKind::kData;
PropertyAttributes temp_attributes = NONE;
if (!TransitionsAccessor::IsSpecialTransition(roots, temp_key)) {
Tagged<Map> temp_target_map =
TransitionsAccessor::GetTargetFromRaw(temp_target);
PropertyDetails details =
TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map);
temp_kind = details.kind();
temp_attributes = details.attributes();
}
int cmp =
CompareKeys(temp_key, temp_key->hash(), temp_kind, temp_attributes,
key, key->hash(), kind, attributes);
if (cmp > 0) {
SetKey(j + 1, temp_key);
SetRawTarget(j + 1, temp_target);
} else {
break;
}
}
SetKey(j + 1, key);
SetRawTarget(j + 1, target);
}
DCHECK(IsSortedNoDuplicates());
}
bool TransitionsAccessor::HasIntegrityLevelTransitionTo(
Tagged<Map> to, Tagged<Symbol>* out_symbol,
PropertyAttributes* out_integrity_level) {
ReadOnlyRoots roots(isolate_);
if (SearchSpecial(roots.frozen_symbol()) == to) {
if (out_integrity_level) *out_integrity_level = FROZEN;
if (out_symbol) *out_symbol = roots.frozen_symbol();
} else if (SearchSpecial(roots.sealed_symbol()) == to) {
if (out_integrity_level) *out_integrity_level = SEALED;
if (out_symbol) *out_symbol = roots.sealed_symbol();
} else if (SearchSpecial(roots.nonextensible_symbol()) == to) {
if (out_integrity_level) *out_integrity_level = NONE;
if (out_symbol) *out_symbol = roots.nonextensible_symbol();
} else {
return false;
}
return true;
}
// static
void TransitionsAccessor::EnsureHasSideStepTransitions(Isolate* isolate,
DirectHandle<Map> map) {
EnsureHasFullTransitionArray(isolate, map);
Tagged<TransitionArray> transitions =
GetTransitionArray(isolate, map->raw_transitions());
if (transitions->HasSideStepTransitions()) return;
TransitionArray::CreateSideStepTransitions(
isolate, direct_handle(transitions, isolate));
}
// static
void TransitionArray::CreateSideStepTransitions(
Isolate* isolate, DirectHandle<TransitionArray> transitions) {
DCHECK(!transitions->HasSideStepTransitions()); // Callers must check first.
DirectHandle<WeakFixedArray> result = WeakFixedArray::New(
isolate, SideStepTransition::kSize, AllocationType::kYoung,
direct_handle(SideStepTransition::Empty, isolate));
transitions->SetSideStepTransitions(*result);
}
std::ostream& operator<<(std::ostream& os, SideStepTransition::Kind sidestep) {
switch (sidestep) {
case SideStepTransition::Kind::kObjectAssignValidityCell:
os << "Object.assign-validity-cell";
break;
case SideStepTransition::Kind::kObjectAssign:
os << "Object.assign-map";
break;
case SideStepTransition::Kind::kCloneObject:
os << "Clone-object-IC-map";
break;
}
return os;
}
} // namespace v8::internal