Simplify and compact transitions storage

src/objects-inl.h

 // 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.
 //
 // Review notes:
 //
 // - The use of macros in these inline functions may seem superfluous
 // but it is absolutely needed to make sure gcc generates optimal
 // code. gcc is not happy when attempting to inline too deep.
 //
@@ skipping 1859 matching lines @@
   WRITE_FIELD(this, kPropertiesOffset, GetHeap()->empty_fixed_array());
 }
 
 
 void JSObject::initialize_elements() {
   FixedArrayBase* elements = map()->GetInitialElements();
   WRITE_FIELD(this, kElementsOffset, elements);
 }
 
 
-Handle<String> Map::ExpectedTransitionKey(Handle<Map> map) {
-  DisallowHeapAllocation no_gc;
-  if (!map->HasTransitionArray()) return Handle<String>::null();
-  TransitionArray* transitions = map->transitions();
-  if (!transitions->IsSimpleTransition()) return Handle<String>::null();
-  int transition = TransitionArray::kSimpleTransitionIndex;
-  PropertyDetails details = transitions->GetTargetDetails(transition);
-  Name* name = transitions->GetKey(transition);
-  if (details.type() != DATA) return Handle<String>::null();
-  if (details.attributes() != NONE) return Handle<String>::null();
-  if (!name->IsString()) return Handle<String>::null();
-  return Handle<String>(String::cast(name));
-}
-
-
-Handle<Map> Map::ExpectedTransitionTarget(Handle<Map> map) {
-  DCHECK(!ExpectedTransitionKey(map).is_null());
-  return Handle<Map>(map->transitions()->GetTarget(
-      TransitionArray::kSimpleTransitionIndex));
-}
-
-
-Handle<Map> Map::FindTransitionToField(Handle<Map> map, Handle<Name> key) {
-  DisallowHeapAllocation no_allocation;
-  if (!map->HasTransitionArray()) return Handle<Map>::null();
-  TransitionArray* transitions = map->transitions();
-  int transition = transitions->Search(kData, *key, NONE);
-  if (transition == TransitionArray::kNotFound) return Handle<Map>::null();
-  PropertyDetails details = transitions->GetTargetDetails(transition);
-  if (details.type() != DATA) return Handle<Map>::null();
-  DCHECK_EQ(NONE, details.attributes());
-  return Handle<Map>(transitions->GetTarget(transition));
-}
-
-
 ACCESSORS(Oddball, to_string, String, kToStringOffset)
 ACCESSORS(Oddball, to_number, Object, kToNumberOffset)
 
 
 byte Oddball::kind() const {
   return Smi::cast(READ_FIELD(this, kKindOffset))->value();
 }
 
 
 void Oddball::set_kind(byte value) {
@@ skipping 1105 matching lines @@
   if (has_fast_smi_or_object_elements() ||
       has_fast_double_elements()) {
     DCHECK(!GetHeap()->InNewSpace(GetHeap()->empty_fixed_array()));
     return GetHeap()->empty_fixed_array();
   } else if (has_external_array_elements()) {
     ExternalArray* empty_array = GetHeap()->EmptyExternalArrayForMap(this);
     DCHECK(!GetHeap()->InNewSpace(empty_array));
     return empty_array;
   } else if (has_fixed_typed_array_elements()) {
     FixedTypedArrayBase* empty_array =
-      GetHeap()->EmptyFixedTypedArrayForMap(this);
+        GetHeap()->EmptyFixedTypedArrayForMap(this);
     DCHECK(!GetHeap()->InNewSpace(empty_array));
     return empty_array;
   } else {
     UNREACHABLE();
   }
   return NULL;
 }
 
 
 Object** DescriptorArray::GetKeySlot(int descriptor_number) {
@@ skipping 2197 matching lines @@
 }
 
 
 void Map::set_prototype(Object* value, WriteBarrierMode mode) {
   DCHECK(value->IsNull() || value->IsJSReceiver());
   WRITE_FIELD(this, kPrototypeOffset, value);
   CONDITIONAL_WRITE_BARRIER(GetHeap(), this, kPrototypeOffset, value, mode);
 }
 
 
-// If the descriptor is using the empty transition array, install a new empty
-// transition array that will have place for an element transition.
-static void EnsureHasTransitionArray(Handle<Map> map) {
-  Handle<TransitionArray> transitions;
-  if (!map->HasTransitionArray()) {
-    transitions = TransitionArray::Allocate(map->GetIsolate(), 0);
-    transitions->set_back_pointer_storage(map->GetBackPointer());
-  } else if (!map->transitions()->IsFullTransitionArray()) {
-    transitions = TransitionArray::ExtendToFullTransitionArray(map);
-  } else {
-    return;
-  }
-  map->set_transitions(*transitions);
-}
-
-
 LayoutDescriptor* Map::layout_descriptor_gc_safe() {
   Object* layout_desc = READ_FIELD(this, kLayoutDecriptorOffset);
   return LayoutDescriptor::cast_gc_safe(layout_desc);
 }
 
 
 bool Map::HasFastPointerLayout() const {
   Object* layout_desc = READ_FIELD(this, kLayoutDecriptorOffset);
   return LayoutDescriptor::IsFastPointerLayout(layout_desc);
 }
@@ skipping 82 matching lines @@
 
 Object* Map::GetBackPointer() {
   Object* object = constructor_or_backpointer();
   if (object->IsMap()) {
     return object;
   }
   return GetIsolate()->heap()->undefined_value();
 }
 
 
-bool Map::HasElementsTransition() {
-  return HasTransitionArray() && transitions()->HasElementsTransition();
+Map* Map::ElementsTransitionMap() {
+  return TransitionArray::SearchSpecial(
+      this, GetHeap()->elements_transition_symbol());
 }
 
 
-bool Map::HasTransitionArray() const {
-  Object* object = READ_FIELD(this, kTransitionsOffset);
-  return object->IsTransitionArray();
-}
-
-
-Map* Map::elements_transition_map() {
-  int index =
-      transitions()->SearchSpecial(GetHeap()->elements_transition_symbol());
-  return transitions()->GetTarget(index);
-}
-
-
-bool Map::CanHaveMoreTransitions() {
-  if (!HasTransitionArray()) return true;
-  return transitions()->number_of_transitions() <
-         TransitionArray::kMaxNumberOfTransitions;
-}
-
-
-Map* Map::GetTransition(int transition_index) {
-  return transitions()->GetTarget(transition_index);
-}
-
-
-int Map::SearchSpecialTransition(Symbol* name) {
-  if (HasTransitionArray()) {
-    return transitions()->SearchSpecial(name);
-  }
-  return TransitionArray::kNotFound;
-}
-
-
-int Map::SearchTransition(PropertyKind kind, Name* name,
-                          PropertyAttributes attributes) {
-  if (HasTransitionArray()) {
-    return transitions()->Search(kind, name, attributes);
-  }
-  return TransitionArray::kNotFound;
-}
-
-
-FixedArray* Map::GetPrototypeTransitions() {
-  if (!HasTransitionArray()) return GetHeap()->empty_fixed_array();
-  if (!transitions()->HasPrototypeTransitions()) {
-    return GetHeap()->empty_fixed_array();
-  }
-  return transitions()->GetPrototypeTransitions();
-}
-
-
-void Map::SetPrototypeTransitions(
-    Handle<Map> map, Handle<FixedArray> proto_transitions) {
-  EnsureHasTransitionArray(map);
-  int old_number_of_transitions = map->NumberOfProtoTransitions();
-  if (Heap::ShouldZapGarbage() && map->HasPrototypeTransitions()) {
-    DCHECK(map->GetPrototypeTransitions() != *proto_transitions);
-    map->ZapPrototypeTransitions();
-  }
-  map->transitions()->SetPrototypeTransitions(*proto_transitions);
-  map->SetNumberOfProtoTransitions(old_number_of_transitions);
-}
-
-
-bool Map::HasPrototypeTransitions() {
-  return HasTransitionArray() && transitions()->HasPrototypeTransitions();
-}
-
-
-TransitionArray* Map::transitions() const {
-  DCHECK(HasTransitionArray());
-  Object* object = READ_FIELD(this, kTransitionsOffset);
-  return TransitionArray::cast(object);
-}
-
-
-void Map::set_transitions(TransitionArray* transition_array,
-                          WriteBarrierMode mode) {
-  // Transition arrays are not shared. When one is replaced, it should not
-  // keep referenced objects alive, so we zap it.
-  // When there is another reference to the array somewhere (e.g. a handle),
-  // not zapping turns from a waste of memory into a source of crashes.
-  if (HasTransitionArray()) {
-#ifdef DEBUG
-    for (int i = 0; i < transitions()->number_of_transitions(); i++) {
-      Map* target = transitions()->GetTarget(i);
-      if (target->instance_descriptors() == instance_descriptors()) {
-        Name* key = transitions()->GetKey(i);
-        int new_target_index;
-        if (TransitionArray::IsSpecialTransition(key)) {
-          new_target_index = transition_array->SearchSpecial(Symbol::cast(key));
-        } else {
-          PropertyDetails details =
-              TransitionArray::GetTargetDetails(key, target);
-          new_target_index = transition_array->Search(details.kind(), key,
-                                                      details.attributes());
-        }
-        DCHECK_NE(TransitionArray::kNotFound, new_target_index);
-        DCHECK_EQ(target, transition_array->GetTarget(new_target_index));
-      }
-    }
-#endif
-    DCHECK(transitions() != transition_array);
-    ZapTransitions();
-  }
-
-  WRITE_FIELD(this, kTransitionsOffset, transition_array);
-  CONDITIONAL_WRITE_BARRIER(GetHeap(), this, kTransitionsOffset,
-                            transition_array, mode);
-}
-
-
-void Map::init_transitions(Object* undefined) {
-  DCHECK(undefined->IsUndefined());
-  WRITE_FIELD(this, kTransitionsOffset, undefined);
-}
+ACCESSORS(Map, raw_transitions, Object, kTransitionsOffset);
 
 
 void Map::SetBackPointer(Object* value, WriteBarrierMode mode) {
   DCHECK(instance_type() >= FIRST_JS_RECEIVER_TYPE);
   DCHECK((value->IsUndefined() && GetBackPointer()->IsMap()) ||
          (value->IsMap() && GetBackPointer()->IsUndefined()));
   DCHECK(!value->IsMap() ||
          Map::cast(value)->GetConstructor() == constructor_or_backpointer());
   set_constructor_or_backpointer(value, mode);
 }
 
 
 ACCESSORS(Map, code_cache, Object, kCodeCacheOffset)
 ACCESSORS(Map, dependent_code, DependentCode, kDependentCodeOffset)
 ACCESSORS(Map, weak_cell_cache, Object, kWeakCellCacheOffset)
 ACCESSORS(Map, constructor_or_backpointer, Object,
           kConstructorOrBackPointerOffset)
 
+
 Object* Map::GetConstructor() const {
   Object* maybe_constructor = constructor_or_backpointer();
   // Follow any back pointers.
   while (maybe_constructor->IsMap()) {
     maybe_constructor =
         Map::cast(maybe_constructor)->constructor_or_backpointer();
   }
   return maybe_constructor;
 }
+
+
 void Map::SetConstructor(Object* constructor, WriteBarrierMode mode) {
   // Never overwrite a back pointer with a constructor.
   DCHECK(!constructor_or_backpointer()->IsMap());
   set_constructor_or_backpointer(constructor, mode);
 }
 
+
 ACCESSORS(JSFunction, shared, SharedFunctionInfo, kSharedFunctionInfoOffset)
 ACCESSORS(JSFunction, literals_or_bindings, FixedArray, kLiteralsOffset)
 ACCESSORS(JSFunction, next_function_link, Object, kNextFunctionLinkOffset)
 
 ACCESSORS(GlobalObject, builtins, JSBuiltinsObject, kBuiltinsOffset)
 ACCESSORS(GlobalObject, native_context, Context, kNativeContextOffset)
 ACCESSORS(GlobalObject, global_proxy, JSObject, kGlobalProxyOffset)
 
 ACCESSORS(JSGlobalProxy, native_context, Object, kNativeContextOffset)
 ACCESSORS(JSGlobalProxy, hash, Object, kHashOffset)
@@ skipping 2090 matching lines @@
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 #undef NOBARRIER_READ_BYTE_FIELD
 #undef NOBARRIER_WRITE_BYTE_FIELD
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_