Separating transitions from descriptors.

src/objects-inl.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 29 matching lines @@
 #include "contexts.h"
 #include "conversions-inl.h"
 #include "heap.h"
 #include "isolate.h"
 #include "property.h"
 #include "spaces.h"
 #include "store-buffer.h"
 #include "v8memory.h"
 #include "factory.h"
 #include "incremental-marking.h"
+#include "transitions.h"
+#include "transitions-inl.h"
 
 namespace v8 {
 namespace internal {
 
 PropertyDetails::PropertyDetails(Smi* smi) {
   value_ = smi->value();
 }
 
 
 Smi* PropertyDetails::AsSmi() {
@@ skipping 457 matching lines @@
 TYPE_CHECKER(Map, MAP_TYPE)
 TYPE_CHECKER(FixedArray, FIXED_ARRAY_TYPE)
 TYPE_CHECKER(FixedDoubleArray, FIXED_DOUBLE_ARRAY_TYPE)
 
 
 bool Object::IsDescriptorArray() {
   return IsFixedArray();
 }
 
 
+bool Object::IsTransitionArray() {
+  return IsFixedArray();
+}
+
+
 bool Object::IsDeoptimizationInputData() {
   // Must be a fixed array.
   if (!IsFixedArray()) return false;
 
   // There's no sure way to detect the difference between a fixed array and
   // a deoptimization data array.  Since this is used for asserts we can
   // check that the length is zero or else the fixed size plus a multiple of
   // the entry size.
   int length = FixedArray::cast(this)->length();
   if (length == 0) return true;
@@ skipping 1341 matching lines @@
          this == HEAP->empty_descriptor_array());
   return length() < kFirstIndex;
 }
 
 
 bool DescriptorArray::MayContainTransitions() {
   return !IsEmpty();
 }
 
 
+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));
 }
 
 
 void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array,
                                                     int first,
                                                     int second) {
   Object* tmp = array->get(first);
   NoIncrementalWriteBarrierSet(array, first, array->get(second));
   NoIncrementalWriteBarrierSet(array, second, tmp);
 }
 
 
+// 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(IsSortedNoDuplicates());
+
+  // Check for empty descriptor array.
+  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(array, EXPECT_SORTED, name, nof);
+  }
+
+  // Slow case: perform binary search.
+  return BinarySearch(array, name, 0, nof - 1);
+}
+
+
 int DescriptorArray::Search(String* name) {
-  SLOW_ASSERT(IsSortedNoDuplicates());
-
-  // Check for empty descriptor array.
-  int nof = number_of_descriptors();
-  if (nof == 0) return 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);
-  }
-
-  // Slow case: perform binary search.
-  return BinarySearch(name, 0, nof - 1);
+  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::ClearElementsTransition() {
+void DescriptorArray::ClearTransitions() {
   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);
+}
+
+
 Object** DescriptorArray::GetKeySlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToKeyIndex(descriptor_number)));
 }
 
 
 String* DescriptorArray::GetKey(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return String::cast(get(ToKeyIndex(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(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToValueIndex(descriptor_number)));
 }
 
 
 Object* DescriptorArray::GetValue(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return get(ToValueIndex(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));
   return PropertyDetails(Smi::cast(details));
 }
 
 
-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();
 }
 
 
 int DescriptorArray::GetFieldIndex(int descriptor_number) {
   return Descriptor::IndexFromValue(GetValue(descriptor_number));
 }
 
 
 JSFunction* DescriptorArray::GetConstantFunction(int descriptor_number) {
   return JSFunction::cast(GetValue(descriptor_number));
 }
 
 
 Object* DescriptorArray::GetCallbacksObject(int descriptor_number) {
   ASSERT(GetType(descriptor_number) == CALLBACKS);
   return GetValue(descriptor_number);
 }
 
 
 AccessorDescriptor* DescriptorArray::GetCallbacks(int descriptor_number) {
   ASSERT(GetType(descriptor_number) == CALLBACKS);
   Foreign* p = Foreign::cast(GetCallbacksObject(descriptor_number));
   return reinterpret_cast<AccessorDescriptor*>(p->foreign_address());
 }
 
 
-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),
              GetDetails(descriptor_number));
 }
 
 
 void DescriptorArray::Set(int descriptor_number,
                           Descriptor* desc,
                           const WhitenessWitness&) {
@@ skipping 1319 matching lines @@
   }
 }
 
 
 void Map::init_instance_descriptors() {
   WRITE_FIELD(this, kInstanceDescriptorsOrBitField3Offset, Smi::FromInt(0));
 }
 
 
 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,
         Smi::FromInt(DescriptorArray::cast(object)->bit_field3_storage()));
   }
 }
 
 
 void Map::set_instance_descriptors(DescriptorArray* value,
                                    WriteBarrierMode mode) {
   Object* object = READ_FIELD(this,
                               kInstanceDescriptorsOrBitField3Offset);
   Heap* heap = GetHeap();
   if (value == heap->empty_descriptor_array()) {
     clear_instance_descriptors();
     return;
   } else {
     if (object->IsSmi()) {
       value->set_bit_field3_storage(Smi::cast(object)->value());
     } else {
       value->set_bit_field3_storage(
           DescriptorArray::cast(object)->bit_field3_storage());
     }
   }
   ASSERT(!is_shared());
-#ifdef DEBUG
-  if (value != instance_descriptors()) {
-    ZapInstanceDescriptors();
-  }
-#endif
   WRITE_FIELD(this, kInstanceDescriptorsOrBitField3Offset, value);
   CONDITIONAL_WRITE_BARRIER(
       heap, this, kInstanceDescriptorsOrBitField3Offset, value, mode);
 }
 
 
 int Map::bit_field3() {
   Object* object = READ_FIELD(this,
                               kInstanceDescriptorsOrBitField3Offset);
   if (object->IsSmi()) {
     return Smi::cast(object)->value();
   } else {
     return DescriptorArray::cast(object)->bit_field3_storage();
   }
 }
 
 
 void Map::ClearDescriptorArray() {
   int bitfield3 = bit_field3();
 #ifdef DEBUG
   Object* object = READ_FIELD(this, kInstanceDescriptorsOrBitField3Offset);
   if (!object->IsSmi()) {
-    ZapInstanceDescriptors();
+    ZapTransitions();
   }
 #endif
   WRITE_FIELD(this,
               kInstanceDescriptorsOrBitField3Offset,
               Smi::FromInt(bitfield3));
 }
 
 
 void Map::set_bit_field3(int value) {
   ASSERT(Smi::IsValid(value));
@@ skipping 11 matching lines @@
 Object* Map::GetBackPointer() {
   Object* object = READ_FIELD(this, kPrototypeTransitionsOrBackPointerOffset);
   if (object->IsFixedArray()) {
     return FixedArray::cast(object)->get(kProtoTransitionBackPointerOffset);
   } else {
     return object;
   }
 }
 
 
+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 descriptor is using the empty transition array, install a new empty
+// transition array that will have place for an element transition.
+static MaybeObject* AllowElementsTransition(Map* map) {
+  if (map->HasTransitionArray()) return 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();
+}
+
+
+// If the map is using the empty descriptor array, install a new empty
+// descriptor array that will contain an element transition.
+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;
+}
+
+
+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()) {
+    if (transitions() == transitions_array) UNREACHABLE();
+    ZapTransitions();
+  }
+#endif
+  instance_descriptors()->set_transitions(transitions_array);
+  return this;
+}
+
+
 void Map::SetBackPointer(Object* value, WriteBarrierMode mode) {
   Heap* heap = GetHeap();
   ASSERT(instance_type() >= FIRST_JS_RECEIVER_TYPE);
   ASSERT((value->IsUndefined() && GetBackPointer()->IsMap()) ||
          (value->IsMap() && GetBackPointer()->IsUndefined()));
   Object* object = READ_FIELD(this, kPrototypeTransitionsOrBackPointerOffset);
   if (object->IsFixedArray()) {
     FixedArray::cast(object)->set(
         kProtoTransitionBackPointerOffset, value, mode);
   } else {
@@ skipping 1674 matching lines @@
 #undef WRITE_UINT32_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_