Index: src/objects-inl.h |
diff --git a/src/objects-inl.h b/src/objects-inl.h |
index b33466977fa85fe60da724e23151e8d1441c61c4..360ba3f703b77226f78473b09f2d6c8f6d8391ce 100644 |
--- a/src/objects-inl.h |
+++ b/src/objects-inl.h |
@@ -47,6 +47,7 @@ |
#include "v8memory.h" |
#include "factory.h" |
#include "incremental-marking.h" |
+#include "transitions-inl.h" |
namespace v8 { |
namespace internal { |
@@ -524,6 +525,11 @@ bool Object::IsDescriptorArray() { |
} |
+bool Object::IsTransitionArray() { |
+ return IsFixedArray(); |
+} |
+ |
+ |
bool Object::IsDeoptimizationInputData() { |
// Must be a fixed array. |
if (!IsFixedArray()) return false; |
@@ -1885,13 +1891,18 @@ bool DescriptorArray::MayContainTransitions() { |
} |
+bool DescriptorArray::HasTransitionArray() { |
+ return MayContainTransitions() && !get(kTransitionsIndex)->IsSmi(); |
+} |
+ |
+ |
int DescriptorArray::bit_field3_storage() { |
Object* storage = READ_FIELD(this, kBitField3StorageOffset); |
return Smi::cast(storage)->value(); |
} |
void DescriptorArray::set_bit_field3_storage(int value) { |
- ASSERT(this->MayContainTransitions()); |
+ ASSERT(length() > kBitField3StorageIndex); |
WRITE_FIELD(this, kBitField3StorageOffset, Smi::FromInt(value)); |
} |
@@ -1905,60 +1916,104 @@ void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array, |
} |
-int DescriptorArray::Search(String* name) { |
- SLOW_ASSERT(IsSortedNoDuplicates()); |
+// Perform a binary search in a fixed array. Low and high are entry indices. If |
+// there are three entries in this array it should be called with low=0 and |
+// high=2. |
+template<typename T> |
+int BinarySearch(T* array, String* name, int low, int high) { |
+ uint32_t hash = name->Hash(); |
+ int limit = high; |
+ |
+ ASSERT(low <= high); |
+ |
+ while (low != high) { |
+ int mid = (low + high) / 2; |
+ String* mid_name = array->GetKey(mid); |
+ uint32_t mid_hash = mid_name->Hash(); |
+ |
+ if (mid_hash >= hash) { |
+ high = mid; |
+ } else { |
+ low = mid + 1; |
+ } |
+ } |
+ |
+ for (; low <= limit && array->GetKey(low)->Hash() == hash; ++low) { |
+ if (array->GetKey(low)->Equals(name)) return low; |
+ } |
+ |
+ return T::kNotFound; |
+} |
+ |
+ |
+// Perform a linear search in this fixed array. len is the number of entry |
+// indices that are valid. |
+template<typename T> |
+int LinearSearch(T* array, SearchMode mode, String* name, int len) { |
+ uint32_t hash = name->Hash(); |
+ for (int number = 0; number < len; number++) { |
+ String* entry = array->GetKey(number); |
+ uint32_t current_hash = entry->Hash(); |
+ if (mode == EXPECT_SORTED && current_hash > hash) break; |
+ if (current_hash == hash && name->Equals(entry)) return number; |
+ } |
+ return T::kNotFound; |
+} |
+ |
+ |
+template<typename T> |
+int Search(T* array, String* name) { |
+ SLOW_ASSERT(array->IsSortedNoDuplicates()); |
// Check for empty descriptor array. |
- int nof = number_of_descriptors(); |
- if (nof == 0) return kNotFound; |
+ int nof = array->number_of_entries(); |
+ if (nof == 0) return T::kNotFound; |
// Fast case: do linear search for small arrays. |
const int kMaxElementsForLinearSearch = 8; |
if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) { |
- return LinearSearch(EXPECT_SORTED, name, nof); |
+ return LinearSearch(array, EXPECT_SORTED, name, nof); |
} |
// Slow case: perform binary search. |
- return BinarySearch(name, 0, nof - 1); |
+ return BinarySearch(array, name, 0, nof - 1); |
+} |
+ |
+ |
+int DescriptorArray::Search(String* name) { |
+ return internal::Search(this, name); |
} |
int DescriptorArray::SearchWithCache(String* name) { |
- int number = GetIsolate()->descriptor_lookup_cache()->Lookup(this, name); |
+ DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); |
+ int number = cache->Lookup(this, name); |
if (number == DescriptorLookupCache::kAbsent) { |
- number = Search(name); |
- GetIsolate()->descriptor_lookup_cache()->Update(this, name, number); |
+ number = internal::Search(this, name); |
+ cache->Update(this, name, number); |
} |
return number; |
} |
-Map* DescriptorArray::elements_transition_map() { |
- if (!this->MayContainTransitions()) { |
- return NULL; |
- } |
- Object* transition_map = get(kTransitionsIndex); |
- if (transition_map == Smi::FromInt(0)) { |
- return NULL; |
- } else { |
- return Map::cast(transition_map); |
- } |
+TransitionArray* DescriptorArray::transitions() { |
+ if (!this->MayContainTransitions()) return NULL; |
+ Object* array = get(kTransitionsIndex); |
+ return TransitionArray::cast(array); |
} |
-void DescriptorArray::set_elements_transition_map( |
- Map* transition_map, WriteBarrierMode mode) { |
- ASSERT(this->length() > kTransitionsIndex); |
- Heap* heap = GetHeap(); |
- WRITE_FIELD(this, kTransitionsOffset, transition_map); |
- CONDITIONAL_WRITE_BARRIER( |
- heap, this, kTransitionsOffset, transition_map, mode); |
- ASSERT(DescriptorArray::cast(this)); |
+void DescriptorArray::ClearTransitions() { |
+ WRITE_FIELD(this, kTransitionsOffset, Smi::FromInt(0)); |
} |
-void DescriptorArray::ClearElementsTransition() { |
- WRITE_FIELD(this, kTransitionsOffset, Smi::FromInt(0)); |
+void DescriptorArray::set_transitions(TransitionArray* transitions_array, |
+ WriteBarrierMode mode) { |
+ Heap* heap = GetHeap(); |
+ WRITE_FIELD(this, kTransitionsOffset, transitions_array); |
+ CONDITIONAL_WRITE_BARRIER( |
+ heap, this, kTransitionsOffset, transitions_array, mode); |
} |
@@ -1976,17 +2031,6 @@ String* DescriptorArray::GetKey(int descriptor_number) { |
} |
-void DescriptorArray::SetKeyUnchecked(Heap* heap, |
- int descriptor_number, |
- String* key) { |
- ASSERT(descriptor_number < number_of_descriptors()); |
- set_unchecked(heap, |
- ToKeyIndex(descriptor_number), |
- key, |
- UPDATE_WRITE_BARRIER); |
-} |
- |
- |
Object** DescriptorArray::GetValueSlot(int descriptor_number) { |
ASSERT(descriptor_number < number_of_descriptors()); |
return HeapObject::RawField( |
@@ -2001,24 +2045,6 @@ Object* DescriptorArray::GetValue(int descriptor_number) { |
} |
-void DescriptorArray::SetNullValueUnchecked(Heap* heap, int descriptor_number) { |
- ASSERT(descriptor_number < number_of_descriptors()); |
- set_null_unchecked(heap, ToValueIndex(descriptor_number)); |
-} |
- |
- |
- |
-void DescriptorArray::SetValueUnchecked(Heap* heap, |
- int descriptor_number, |
- Object* value) { |
- ASSERT(descriptor_number < number_of_descriptors()); |
- set_unchecked(heap, |
- ToValueIndex(descriptor_number), |
- value, |
- UPDATE_WRITE_BARRIER); |
-} |
- |
- |
PropertyDetails DescriptorArray::GetDetails(int descriptor_number) { |
ASSERT(descriptor_number < number_of_descriptors()); |
Object* details = get(ToDetailsIndex(descriptor_number)); |
@@ -2026,12 +2052,6 @@ PropertyDetails DescriptorArray::GetDetails(int descriptor_number) { |
} |
-void DescriptorArray::SetDetailsUnchecked(int descriptor_number, Smi* value) { |
- ASSERT(descriptor_number < number_of_descriptors()); |
- set_unchecked(ToDetailsIndex(descriptor_number), value); |
-} |
- |
- |
PropertyType DescriptorArray::GetType(int descriptor_number) { |
return GetDetails(descriptor_number).type(); |
} |
@@ -2060,38 +2080,6 @@ AccessorDescriptor* DescriptorArray::GetCallbacks(int descriptor_number) { |
} |
-bool DescriptorArray::IsProperty(int descriptor_number) { |
- Entry entry(this, descriptor_number); |
- return IsPropertyDescriptor(&entry); |
-} |
- |
- |
-bool DescriptorArray::IsTransitionOnly(int descriptor_number) { |
- switch (GetType(descriptor_number)) { |
- case MAP_TRANSITION: |
- case CONSTANT_TRANSITION: |
- return true; |
- case CALLBACKS: { |
- Object* value = GetValue(descriptor_number); |
- if (!value->IsAccessorPair()) return false; |
- AccessorPair* accessors = AccessorPair::cast(value); |
- return accessors->getter()->IsMap() && accessors->setter()->IsMap(); |
- } |
- case NORMAL: |
- case FIELD: |
- case CONSTANT_FUNCTION: |
- case HANDLER: |
- case INTERCEPTOR: |
- return false; |
- case NONEXISTENT: |
- UNREACHABLE(); |
- break; |
- } |
- UNREACHABLE(); // Keep the compiler happy. |
- return false; |
-} |
- |
- |
void DescriptorArray::Get(int descriptor_number, Descriptor* desc) { |
desc->Init(GetKey(descriptor_number), |
GetValue(descriptor_number), |
@@ -2129,16 +2117,14 @@ void DescriptorArray::NoIncrementalWriteBarrierSwapDescriptors( |
} |
-DescriptorArray::WhitenessWitness::WhitenessWitness(DescriptorArray* array) |
+FixedArray::WhitenessWitness::WhitenessWitness(FixedArray* array) |
: marking_(array->GetHeap()->incremental_marking()) { |
marking_->EnterNoMarkingScope(); |
- if (array->number_of_descriptors() > 0) { |
- ASSERT(Marking::Color(array) == Marking::WHITE_OBJECT); |
- } |
+ ASSERT(Marking::Color(array) == Marking::WHITE_OBJECT); |
} |
-DescriptorArray::WhitenessWitness::~WhitenessWitness() { |
+FixedArray::WhitenessWitness::~WhitenessWitness() { |
marking_->LeaveNoMarkingScope(); |
} |
@@ -3431,12 +3417,8 @@ void Map::init_instance_descriptors() { |
void Map::clear_instance_descriptors() { |
- Object* object = READ_FIELD(this, |
- kInstanceDescriptorsOrBitField3Offset); |
+ Object* object = READ_FIELD(this, kInstanceDescriptorsOrBitField3Offset); |
if (!object->IsSmi()) { |
-#ifdef DEBUG |
- ZapInstanceDescriptors(); |
-#endif |
WRITE_FIELD( |
this, |
kInstanceDescriptorsOrBitField3Offset, |
@@ -3462,11 +3444,6 @@ void Map::set_instance_descriptors(DescriptorArray* value, |
} |
} |
ASSERT(!is_shared()); |
-#ifdef DEBUG |
- if (value != instance_descriptors()) { |
- ZapInstanceDescriptors(); |
- } |
-#endif |
WRITE_FIELD(this, kInstanceDescriptorsOrBitField3Offset, value); |
CONDITIONAL_WRITE_BARRIER( |
heap, this, kInstanceDescriptorsOrBitField3Offset, value, mode); |
@@ -3489,7 +3466,7 @@ void Map::ClearDescriptorArray() { |
#ifdef DEBUG |
Object* object = READ_FIELD(this, kInstanceDescriptorsOrBitField3Offset); |
if (!object->IsSmi()) { |
- ZapInstanceDescriptors(); |
+ ZapTransitions(); |
} |
#endif |
WRITE_FIELD(this, |
@@ -3521,13 +3498,93 @@ Object* Map::GetBackPointer() { |
} |
+bool Map::HasElementsTransition() { |
+ return HasTransitionArray() && transitions()->HasElementsTransition(); |
+} |
+ |
+ |
+bool Map::HasTransitionArray() { |
+ return instance_descriptors()->HasTransitionArray(); |
+} |
+ |
+ |
Map* Map::elements_transition_map() { |
- return instance_descriptors()->elements_transition_map(); |
+ return transitions()->elements_transition(); |
} |
-void Map::set_elements_transition_map(Map* transitioned_map) { |
- return instance_descriptors()->set_elements_transition_map(transitioned_map); |
+MaybeObject* Map::AddTransition(String* key, Object* value) { |
+ if (HasTransitionArray()) return transitions()->CopyInsert(key, value); |
+ return TransitionArray::NewWith(key, value); |
+} |
+ |
+ |
+// If the map does not have a descriptor array, install a new empty |
+// descriptor array that has room for a transition array. |
+static MaybeObject* AllowTransitions(Map* map) { |
+ if (map->instance_descriptors()->MayContainTransitions()) return map; |
+ DescriptorArray* descriptors; |
+ MaybeObject* maybe_descriptors = |
+ DescriptorArray::Allocate(0, DescriptorArray::CANNOT_BE_SHARED); |
+ if (!maybe_descriptors->To(&descriptors)) return maybe_descriptors; |
+ map->set_instance_descriptors(descriptors); |
+ return descriptors; |
+} |
+ |
+ |
+// If the descriptor does not have a transition array, install a new |
+// transition array that has room for an element transition. |
+static MaybeObject* AllowElementsTransition(Map* map) { |
+ if (map->HasTransitionArray()) return map; |
+ |
+ AllowTransitions(map); |
+ |
+ TransitionArray* transitions; |
+ MaybeObject* maybe_transitions = TransitionArray::Allocate(0); |
+ if (!maybe_transitions->To(&transitions)) return maybe_transitions; |
+ MaybeObject* added_transitions = map->set_transitions(transitions); |
+ if (added_transitions->IsFailure()) return added_transitions; |
+ return transitions; |
+} |
+ |
+ |
+MaybeObject* Map::set_elements_transition_map(Map* transitioned_map) { |
+ MaybeObject* allow_elements = AllowElementsTransition(this); |
+ if (allow_elements->IsFailure()) return allow_elements; |
+ transitions()->set_elements_transition(transitioned_map); |
+ return this; |
+} |
+ |
+ |
+TransitionArray* Map::transitions() { |
+ return instance_descriptors()->transitions(); |
+} |
+ |
+ |
+void Map::ClearTransitions() { |
+#ifdef DEBUG |
+ ZapTransitions(); |
+#endif |
+ DescriptorArray* descriptors = instance_descriptors(); |
+ if (descriptors->number_of_descriptors() == 0) { |
+ ClearDescriptorArray(); |
+ } else { |
+ descriptors->ClearTransitions(); |
+ } |
+} |
+ |
+ |
+MaybeObject* Map::set_transitions(TransitionArray* transitions_array) { |
+ MaybeObject* allow_transitions = AllowTransitions(this); |
+ if (allow_transitions->IsFailure()) return allow_transitions; |
+#ifdef DEBUG |
+ if (HasTransitionArray()) { |
+ ASSERT(transitions() != transitions_array); |
+ ZapTransitions(); |
+ } |
+#endif |
+ instance_descriptors()->set_transitions(transitions_array); |
+ return this; |
} |