Revert of 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();
 }
 
 
-Map* Map::ElementsTransitionMap() {
-  return TransitionArray::SearchSpecial(
-      this, GetHeap()->elements_transition_symbol());
+bool Map::HasElementsTransition() {
+  return HasTransitionArray() && transitions()->HasElementsTransition();
 }
 
 
-ACCESSORS(Map, raw_transitions, Object, kTransitionsOffset)
+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);
+}
 
 
 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_