Sharing of descriptor arrays.

src/objects.cc

 // 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 1525 matching lines @@
   }
   return true;
 }
 
 
 MaybeObject* JSObject::AddFastProperty(String* name,
                                        Object* value,
                                        PropertyAttributes attributes,
                                        StoreFromKeyed store_mode) {
   ASSERT(!IsJSGlobalProxy());
-  ASSERT(map()->instance_descriptors()->Search(name) ==
-         DescriptorArray::kNotFound);
+  ASSERT(DescriptorArray::kNotFound ==
+         map()->instance_descriptors()->Search(
+             name, map()->NumberOfOwnDescriptors()));
 
   // Normalize the object if the name is an actual string (not the
   // hidden symbols) and is not a real identifier.
   // Normalize the object if it will have too many fast properties.
   Isolate* isolate = GetHeap()->isolate();
   StringInputBuffer buffer(name);
   if ((!IsIdentifier(isolate->unicode_cache(), &buffer)
        && name != isolate->heap()->hidden_symbol()) ||
       (map()->unused_property_fields() == 0 &&
        TooManyFastProperties(properties()->length(), store_mode))) {
@@ skipping 591 matching lines @@
 }
 
 
 void Map::CopyAppendCallbackDescriptors(Handle<Map> map,
                                         Handle<Object> descriptors) {
   Isolate* isolate = map->GetIsolate();
   Handle<DescriptorArray> array(map->instance_descriptors());
   v8::NeanderArray callbacks(descriptors);
   int nof_callbacks = callbacks.length();
   int descriptor_count = array->number_of_descriptors();
+  ASSERT(descriptor_count == map->NumberOfOwnDescriptors());
 
   // Ensure the keys are symbols before writing them into the instance
   // descriptor. Since it may cause a GC, it has to be done before we
   // temporarily put the heap in an invalid state while appending descriptors.
   for (int i = 0; i < nof_callbacks; ++i) {
     Handle<AccessorInfo> entry(AccessorInfo::cast(callbacks.get(i)));
     Handle<String> key =
         isolate->factory()->SymbolFromString(
             Handle<String>(String::cast(entry->name())));
     entry->set_name(*key);
   }
 
   Handle<DescriptorArray> result =
       isolate->factory()->NewDescriptorArray(descriptor_count + nof_callbacks);
 
   // Ensure that marking will not progress and change color of objects.
   DescriptorArray::WhitenessWitness witness(*result);
 
   // Copy the descriptors from the array.
-  if (0 < descriptor_count) {
-    for (int i = 0; i < descriptor_count; i++) {
-      result->CopyFrom(i, *array, i, witness);
-    }
+  for (int i = 0; i < descriptor_count; i++) {
+    result->CopyFrom(i, *array, i, witness);
   }
 
   // After this point the GC is not allowed to run anymore until the map is in a
   // consistent state again, i.e., all the descriptors are appended and the
   // descriptor array is trimmed to the right size.
   Map::SetDescriptors(map, result);
 
   // Fill in new callback descriptors.  Process the callbacks from
   // back to front so that the last callback with a given name takes
   // precedence over previously added callbacks with that name.
+  int nof = descriptor_count;
   for (int i = nof_callbacks - 1; i >= 0; i--) {
     AccessorInfo* entry = AccessorInfo::cast(callbacks.get(i));
     String* key = String::cast(entry->name());
     // Check if a descriptor with this name already exists before writing.
-    if (LinearSearch(*result, key, map->NumberOfOwnDescriptors()) ==
-        DescriptorArray::kNotFound) {
+    if (result->Search(key, nof) == DescriptorArray::kNotFound) {
       CallbacksDescriptor desc(key, entry, entry->property_attributes());
       map->AppendDescriptor(&desc, witness);
+      nof += 1;
     }
   }
 
-  int new_number_of_descriptors = map->NumberOfOwnDescriptors();
+  ASSERT(nof == map->NumberOfOwnDescriptors());
+
   // Reinstall the original descriptor array if no new elements were added.
-  if (new_number_of_descriptors == descriptor_count) {
+  if (nof == descriptor_count) {
     Map::SetDescriptors(map, array);
     return;
   }
 
   // If duplicates were detected, trim the descriptor array to the right size.
-  int new_array_size = DescriptorArray::LengthFor(new_number_of_descriptors);
+  int new_array_size = DescriptorArray::LengthFor(nof);
   if (new_array_size < result->length()) {
     RightTrimFixedArray<FROM_MUTATOR>(
         isolate->heap(), *result, result->length() - new_array_size);
   }
 }
 
 
 static bool ContainsMap(MapHandleList* maps, Handle<Map> map) {
   ASSERT(!map.is_null());
   for (int i = 0; i < maps->length(); ++i) {
@@ skipping 1046 matching lines @@
   if (!HasFastProperties()) return this;
 
   // The global object is always normalized.
   ASSERT(!IsGlobalObject());
   // JSGlobalProxy must never be normalized
   ASSERT(!IsJSGlobalProxy());
 
   Map* map_of_this = map();
 
   // Allocate new content.
-  int property_count = map_of_this->NumberOfDescribedProperties();
+  int real_size = map_of_this->NumberOfOwnDescriptors();
+  int property_count =
+      map_of_this->NumberOfDescribedProperties(OWN_DESCRIPTORS);
   if (expected_additional_properties > 0) {
     property_count += expected_additional_properties;
   } else {
     property_count += 2;  // Make space for two more properties.
   }
   StringDictionary* dictionary;
-  { MaybeObject* maybe_dictionary = StringDictionary::Allocate(property_count);
-    if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
-  }
+  MaybeObject* maybe_dictionary = StringDictionary::Allocate(property_count);
+  if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
 
   DescriptorArray* descs = map_of_this->instance_descriptors();
-  for (int i = 0; i < descs->number_of_descriptors(); i++) {
+  for (int i = 0; i < real_size; i++) {
     PropertyDetails details = descs->GetDetails(i);
     switch (details.type()) {
       case CONSTANT_FUNCTION: {
         PropertyDetails d = PropertyDetails(details.attributes(),
                                             NORMAL,
                                             details.descriptor_index());
         Object* value = descs->GetConstantFunction(i);
         MaybeObject* maybe_dictionary =
             dictionary->Add(descs->GetKey(i), value, d);
         if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
@@ skipping 24 matching lines @@
       case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
         break;
     }
   }
 
   Heap* current_heap = GetHeap();
 
   // Copy the next enumeration index from instance descriptor.
-  int index = map_of_this->instance_descriptors()->NextEnumerationIndex();
-  dictionary->SetNextEnumerationIndex(index);
+  dictionary->SetNextEnumerationIndex(real_size + 1);
 
   Map* new_map;
   MaybeObject* maybe_map =
       current_heap->isolate()->context()->native_context()->
       normalized_map_cache()->Get(this, mode);
   if (!maybe_map->To(&new_map)) return maybe_map;
   ASSERT(new_map->is_dictionary_map());
 
   // We have now successfully allocated all the necessary objects.
   // Changes can now be made with the guarantee that all of them take effect.
@@ skipping 325 matching lines @@
   ASSERT(!IsJSGlobalProxy());
   Object* inline_value;
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if (descriptors->number_of_descriptors() > 0) {
       int sorted_index = descriptors->GetSortedKeyIndex(0);
-      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol()) {
+      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol() &&
+          sorted_index < map()->NumberOfOwnDescriptors()) {
         ASSERT(descriptors->GetType(sorted_index) == FIELD);
-        inline_value = this->FastPropertyAt(
-            descriptors->GetFieldIndex(sorted_index));
+        inline_value =
+            this->FastPropertyAt(descriptors->GetFieldIndex(sorted_index));
       } else {
         inline_value = GetHeap()->undefined_value();
       }
     } else {
       inline_value = GetHeap()->undefined_value();
     }
   } else {
     PropertyAttributes attributes;
     // You can't install a getter on a property indexed by the hidden symbol,
     // so we can be sure that GetLocalPropertyPostInterceptor returns a real
@@ skipping 44 matching lines @@
   // for hidden properties yet.
   ASSERT(HasHiddenProperties() != value->IsSmi());
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if (descriptors->number_of_descriptors() > 0) {
       int sorted_index = descriptors->GetSortedKeyIndex(0);
-      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol()) {
+      if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol() &&
+          sorted_index < map()->NumberOfOwnDescriptors()) {
         ASSERT(descriptors->GetType(sorted_index) == FIELD);
         this->FastPropertyAtPut(descriptors->GetFieldIndex(sorted_index),
                                 value);
         return this;
       }
     }
   }
   MaybeObject* store_result =
       SetPropertyPostInterceptor(GetHeap()->hidden_symbol(),
                                  value,
@@ skipping 417 matching lines @@
 }
 
 
 void Map::SetDescriptors(Handle<Map> map,
                          Handle<DescriptorArray> descriptors) {
   Isolate* isolate = map->GetIsolate();
   CALL_HEAP_FUNCTION_VOID(isolate, map->SetDescriptors(*descriptors));
 }
 
 
-int Map::NumberOfDescribedProperties(PropertyAttributes filter) {
+int Map::NumberOfDescribedProperties(DescriptorFlag which,
+                                     PropertyAttributes filter) {
   int result = 0;
   DescriptorArray* descs = instance_descriptors();
-  for (int i = 0; i < descs->number_of_descriptors(); i++) {
-    PropertyDetails details = descs->GetDetails(i);
-    if ((details.attributes() & filter) == 0) {
-      result++;
-    }
+  int limit = which == ALL_DESCRIPTORS
+      ? descs->number_of_descriptors()
+      : NumberOfOwnDescriptors();
+  for (int i = 0; i < limit; i++) {
+    if ((descs->GetDetails(i).attributes() & filter) == 0) result++;
   }
   return result;
 }
 
 
 int Map::PropertyIndexFor(String* name) {
   DescriptorArray* descs = instance_descriptors();
-  for (int i = 0; i < descs->number_of_descriptors(); i++) {
+  int limit = NumberOfOwnDescriptors();
+  for (int i = 0; i < limit; i++) {
     if (name->Equals(descs->GetKey(i))) return descs->GetFieldIndex(i);
   }
   return -1;
 }
 
 
 int Map::NextFreePropertyIndex() {
   int max_index = -1;
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
   DescriptorArray* descs = instance_descriptors();
-  for (int i = 0; i < descs->number_of_descriptors(); i++) {
+  for (int i = 0; i < number_of_own_descriptors; i++) {
     if (descs->GetType(i) == FIELD) {
       int current_index = descs->GetFieldIndex(i);
       if (current_index > max_index) max_index = current_index;
     }
   }
   return max_index + 1;
 }
 
 
 AccessorDescriptor* Map::FindAccessor(String* name) {
   DescriptorArray* descs = instance_descriptors();
-  for (int i = 0; i < descs->number_of_descriptors(); i++) {
-    if (name->Equals(descs->GetKey(i)) && descs->GetType(i) == CALLBACKS) {
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
+  for (int i = 0; i < number_of_own_descriptors; i++) {
+    if (descs->GetType(i) == CALLBACKS && name->Equals(descs->GetKey(i))) {
       return descs->GetCallbacks(i);
     }
   }
   return NULL;
 }
 
 
 void JSReceiver::LocalLookup(String* name, LookupResult* result) {
   ASSERT(name->IsString());
 
@@ skipping 403 matching lines @@
     } else {
       return GetHeap()->null_value();
     }
 
     int descriptor_number = result.GetDescriptorIndex();
 
     map()->LookupTransition(this, name, &result);
 
     if (result.IsFound()) {
       Map* target = result.GetTransitionTarget();
-      ASSERT(target->instance_descriptors()->number_of_descriptors() ==
-             map()->instance_descriptors()->number_of_descriptors());
-      ASSERT(target->instance_descriptors()->GetKey(descriptor_number) == name);
+      ASSERT(target->NumberOfOwnDescriptors() ==
+             map()->NumberOfOwnDescriptors());
+      // This works since descriptors are sorted in order of addition.
+      ASSERT(map()->instance_descriptors()->GetKey(descriptor_number) == name);
       return TryAccessorTransition(
           this, target, descriptor_number, component, accessor, attributes);
     }
   } else {
     // If not, lookup a transition.
     map()->LookupTransition(this, name, &result);
 
     // If there is a transition, try to follow it.
     if (result.IsFound()) {
       Map* target = result.GetTransitionTarget();
@@ skipping 162 matching lines @@
         }
       }
     }
   }
   return heap->undefined_value();
 }
 
 
 Object* JSObject::SlowReverseLookup(Object* value) {
   if (HasFastProperties()) {
+    int number_of_own_descriptors = map()->NumberOfOwnDescriptors();
     DescriptorArray* descs = map()->instance_descriptors();
-    for (int i = 0; i < descs->number_of_descriptors(); i++) {
+    for (int i = 0; i < number_of_own_descriptors; i++) {
       if (descs->GetType(i) == FIELD) {
         if (FastPropertyAt(descs->GetFieldIndex(i)) == value) {
           return descs->GetKey(i);
         }
       } else if (descs->GetType(i) == CONSTANT_FUNCTION) {
         if (descs->GetConstantFunction(i) == value) {
           return descs->GetKey(i);
         }
       }
     }
     return GetHeap()->undefined_value();
   } else {
     return property_dictionary()->SlowReverseLookup(value);
   }
 }
 
 
 MaybeObject* Map::RawCopy(int instance_size) {
   Map* result;
   MaybeObject* maybe_result =
       GetHeap()->AllocateMap(instance_type(), instance_size);
   if (!maybe_result->To(&result)) return maybe_result;
 
   result->set_prototype(prototype());
   result->set_constructor(constructor());
   result->set_bit_field(bit_field());
   result->set_bit_field2(bit_field2());
   result->set_bit_field3(bit_field3());
-  result->SetNumberOfOwnDescriptors(0);
-  result->SetEnumLength(kInvalidEnumCache);
+  int new_bit_field3 = bit_field3();
+  new_bit_field3 = OwnsDescriptors::update(new_bit_field3, true);
+  new_bit_field3 = NumberOfOwnDescriptorsBits::update(new_bit_field3, 0);
+  new_bit_field3 = EnumLengthBits::update(new_bit_field3, kInvalidEnumCache);
+  result->set_bit_field3(new_bit_field3);
   return result;
 }
 
 
 MaybeObject* Map::CopyNormalized(PropertyNormalizationMode mode,
                                  NormalizedMapSharingMode sharing) {
   int new_instance_size = instance_size();
   if (mode == CLEAR_INOBJECT_PROPERTIES) {
     new_instance_size -= inobject_properties() * kPointerSize;
   }
@@ skipping 29 matching lines @@
   result->set_inobject_properties(inobject_properties());
   result->set_unused_property_fields(unused_property_fields());
 
   result->set_pre_allocated_property_fields(pre_allocated_property_fields());
   result->set_is_shared(false);
   result->ClearCodeCache(GetHeap());
   return result;
 }
 
 
+MaybeObject* Map::ShareDescriptor(Descriptor* descriptor) {
+  Map* result;
+  MaybeObject* maybe_result = CopyDropDescriptors();
+  if (!maybe_result->To(&result)) return maybe_result;
+
+  String* name = descriptor->GetKey();
+
+  TransitionArray* transitions;
+  MaybeObject* maybe_transitions = AddTransition(name, result);
+  if (!maybe_transitions->To(&transitions)) return maybe_transitions;
+
+  DescriptorArray* descriptors = instance_descriptors();
+  int old_size = descriptors->number_of_descriptors();
+
+  DescriptorArray* new_descriptors;
+  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1);
+  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
+  FixedArray::WhitenessWitness witness(new_descriptors);
+
+  for (int i = 0; i < old_size; ++i) {
+    new_descriptors->CopyFrom(i, descriptors, i, witness);
+  }
+  new_descriptors->Append(descriptor, witness, old_size);
+
+  // If the source descriptors had an enum cache we copy it. This ensures that
+  // the maps to which we push the new descriptor array back can rely on a
+  // cache always being available once it is set. If the map has more
+  // enumerated descriptors than available in the original cache, the cache
+  // will be lazily replaced by the extended cache when needed.
+  if (descriptors->HasEnumCache()) {
+    new_descriptors->CopyEnumCacheFrom(descriptors);
+  }
+
+  transitions->set_descriptors(new_descriptors);
+  set_transitions(transitions);
+  result->SetBackPointer(this);
+  SetOwnsDescriptors(false);
+
+  result->SetNumberOfOwnDescriptors(new_descriptors->number_of_descriptors());
+
+  return result;
+}
+
+
 MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors,
                                          String* name,
                                          TransitionFlag flag) {
+  ASSERT(descriptors->IsSortedNoDuplicates());
+
   Map* result;
   MaybeObject* maybe_result = CopyDropDescriptors();
   if (!maybe_result->To(&result)) return maybe_result;
 
-  if (descriptors->number_of_descriptors() != 0) {
+  // Unless we are creating a map with no descriptors and no back pointer, we
+  // insert the descriptor array locally.
+  if (!descriptors->IsEmpty()) {
     MaybeObject* maybe_failure = result->SetDescriptors(descriptors);
     if (maybe_failure->IsFailure()) return maybe_failure;
     result->SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
   }
 
   if (flag == INSERT_TRANSITION && CanHaveMoreTransitions()) {
     TransitionArray* transitions;
     MaybeObject* maybe_transitions = AddTransition(name, result);
     if (!maybe_transitions->To(&transitions)) return maybe_transitions;
 
+    if (descriptors->IsEmpty()) {
+      if (OwnsDescriptors()) {
+        // If the copied map has no added fields, and the parent map owns its
+        // descriptors, those descriptors have to be empty. In that case,
+        // transfer ownership of the descriptors to the new child.
+        ASSERT(instance_descriptors()->IsEmpty());
+        SetOwnsDescriptors(false);
+      } else {
+        // If the parent did not own its own descriptors, it may share a larger
+        // descriptors array already. In that case, force a split by setting
+        // the descriptor array of the new map to the empty descriptor array.
+        MaybeObject* maybe_failure =
+            result->SetDescriptors(GetHeap()->empty_descriptor_array());
+        if (maybe_failure->IsFailure()) return maybe_failure;
+      }
+    }
+
     set_transitions(transitions);
     result->SetBackPointer(this);
   }
 
   return result;
 }
 
 
 MaybeObject* Map::CopyAsElementsKind(ElementsKind kind, TransitionFlag flag) {
-  // Create a new free-floating map only if we are not allowed to store it.
-  Map* new_map = NULL;
-  MaybeObject* maybe_new_map = Copy();
-  if (!maybe_new_map->To(&new_map)) return maybe_new_map;
-  new_map->set_elements_kind(kind);
-
   if (flag == INSERT_TRANSITION) {
     ASSERT(!HasElementsTransition() ||
         ((elements_transition_map()->elements_kind() == DICTIONARY_ELEMENTS ||
           IsExternalArrayElementsKind(
               elements_transition_map()->elements_kind())) &&
          (kind == DICTIONARY_ELEMENTS ||
           IsExternalArrayElementsKind(kind))));
     ASSERT(!IsFastElementsKind(kind) ||
            IsMoreGeneralElementsKindTransition(elements_kind(), kind));
     ASSERT(kind != elements_kind());
+  }
+
+  if (flag == INSERT_TRANSITION && OwnsDescriptors()) {
+    // In case the map owned its own descriptors, share the descriptors and
+    // transfer ownership to the new map.
+    Map* new_map;
+    MaybeObject* maybe_new_map = CopyDropDescriptors();
+    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
 
     MaybeObject* added_elements = set_elements_transition_map(new_map);
     if (added_elements->IsFailure()) return added_elements;
 
+    new_map->set_elements_kind(kind);
+    new_map->SetBackPointer(this);
+    new_map->SetNumberOfOwnDescriptors(NumberOfOwnDescriptors());
+    SetOwnsDescriptors(false);
+    return new_map;
+  }
+
+  // In case the map did not own its own descriptors, a split is forced by
+  // copying the map; creating a new descriptor array cell.
+  // Create a new free-floating map only if we are not allowed to store it.
+  Map* new_map;
+  MaybeObject* maybe_new_map = Copy();
+  if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+  ASSERT(new_map->NumberOfOwnDescriptors() == NumberOfOwnDescriptors());
+  new_map->set_elements_kind(kind);
+
+  if (flag == INSERT_TRANSITION) {
+    // Map::Copy does not store the descriptor array in case it is empty, since
+    // it does not insert a back pointer; implicitly indicating that its
+    // descriptor array is empty. Since in this case we do want to insert a back
+    // pointer, we have to manually set the empty descriptor array to force a
+    // split.
+    if (!new_map->StoresOwnDescriptors()) {
+      ASSERT(new_map->NumberOfOwnDescriptors() == 0);
+      MaybeObject* maybe_failure =
+          new_map->SetDescriptors(GetHeap()->empty_descriptor_array());
+      if (maybe_failure->IsFailure()) return maybe_failure;
+    }
+    MaybeObject* added_elements = set_elements_transition_map(new_map);
+    if (added_elements->IsFailure()) return added_elements;
+
     new_map->SetBackPointer(this);
   }
 
   return new_map;
 }
 
 
 MaybeObject* Map::CopyWithPreallocatedFieldDescriptors() {
   if (pre_allocated_property_fields() == 0) return CopyDropDescriptors();
 
   // If the map has pre-allocated properties always start out with a descriptor
   // array describing these properties.
   ASSERT(constructor()->IsJSFunction());
   JSFunction* ctor = JSFunction::cast(constructor());
   Map* map = ctor->initial_map();
   DescriptorArray* descriptors = map->instance_descriptors();
 
-  return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION);
+  int number_of_own_descriptors = map->NumberOfOwnDescriptors();
+  DescriptorArray* new_descriptors;
+  MaybeObject* maybe_descriptors =
+      descriptors->CopyUpTo(number_of_own_descriptors);
+  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
+
+  return CopyReplaceDescriptors(new_descriptors, NULL, OMIT_TRANSITION);
 }
 
 
 MaybeObject* Map::Copy() {
   DescriptorArray* descriptors = instance_descriptors();
-  return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION);
+  DescriptorArray* new_descriptors;
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
+  MaybeObject* maybe_descriptors =
+      descriptors->CopyUpTo(number_of_own_descriptors);
+  if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
+
+  return CopyReplaceDescriptors(new_descriptors, NULL, OMIT_TRANSITION);
 }
 
 
 MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor,
                                     TransitionFlag flag) {
   DescriptorArray* descriptors = instance_descriptors();
+  // name->PrintLn();

[Jakob Kummerow, 2012/09/11 14:24:25]

leftover?

[Toon Verwaest, 2012/09/11 14:49:23]

Done.

 
   // Ensure the key is a symbol.
   MaybeObject* maybe_failure = descriptor->KeyToSymbol();
   if (maybe_failure->IsFailure()) return maybe_failure;
 
-  String* key = descriptor->GetKey();
-  ASSERT(descriptors->Search(key) == DescriptorArray::kNotFound);
+  int old_size = NumberOfOwnDescriptors();
+  int new_size = old_size + 1;
+  descriptor->SetEnumerationIndex(new_size);
 
-  int old_size = descriptors->number_of_descriptors();
-  int new_size = old_size + 1;
+  if (flag == INSERT_TRANSITION &&
+      OwnsDescriptors() &&
+      CanHaveMoreTransitions()) {
+    return ShareDescriptor(descriptor);
+  }
 
   DescriptorArray* new_descriptors;
-  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(new_size);
+  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1);
   if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
 
   FixedArray::WhitenessWitness witness(new_descriptors);
 
   // Copy the descriptors, inserting a descriptor.
   for (int i = 0; i < old_size; ++i) {
     new_descriptors->CopyFrom(i, descriptors, i, witness);
   }
 
-  new_descriptors->Append(descriptor, witness, old_size);
+  new_descriptors->Set(old_size, descriptor, witness);
+  new_descriptors->Sort();
 
-  SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
-
-  return CopyReplaceDescriptors(new_descriptors, key, flag);
+  return CopyReplaceDescriptors(new_descriptors, descriptor->GetKey(), flag);
 }
 
 
 MaybeObject* Map::CopyInsertDescriptor(Descriptor* descriptor,
                                        TransitionFlag flag) {
   DescriptorArray* old_descriptors = instance_descriptors();
 
   // Ensure the key is a symbol.
   MaybeObject* maybe_result = descriptor->KeyToSymbol();
   if (maybe_result->IsFailure()) return maybe_result;
 
   // We replace the key if it is already present.
-  int index = old_descriptors->SearchWithCache(descriptor->GetKey());
+  int index = old_descriptors->SearchWithCache(descriptor->GetKey(), this);
   if (index != DescriptorArray::kNotFound) {
     return CopyReplaceDescriptor(descriptor, index, flag);
   }
   return CopyAddDescriptor(descriptor, flag);
 }
 
 
+MaybeObject* DescriptorArray::CopyUpTo(int enumeration_index) {
+  if (enumeration_index == 0) return GetHeap()->empty_descriptor_array();
+  // if (enumeration_index == number_of_descriptors()) return this;

[Jakob Kummerow, 2012/09/11 14:24:25]

// ?

[Toon Verwaest, 2012/09/11 14:49:23]

This is leftover code. Removed.

It would have been nice to actually share descriptor arrays if no descriptors
were added yet. This would introduce sharing without transferring ownership,
which is not possible given that descriptor arrays aren't fully immutable: they
potentially get reduced in ClearNonLiveTransitions.

This is problematic if the new map is not linked in the transitions of the old
map. They might have been removed when we changed the nature of a transition
from accessor to property, or not have been inserted in the first place.

+
+  int size = enumeration_index;
+
+  DescriptorArray* descriptors;
+  MaybeObject* maybe_descriptors = Allocate(size);
+  if (!maybe_descriptors->To(&descriptors)) return maybe_descriptors;
+  DescriptorArray::WhitenessWitness witness(descriptors);
+
+  for (int i = 0; i < size; ++i) {
+    descriptors->CopyFrom(i, this, i, witness);
+  }
+
+  if (number_of_descriptors() != enumeration_index) descriptors->Sort();
+
+  return descriptors;
+}
+
+
 MaybeObject* Map::CopyReplaceDescriptor(Descriptor* descriptor,
                                         int insertion_index,
                                         TransitionFlag flag) {
-  DescriptorArray* descriptors = instance_descriptors();
-  int size = descriptors->number_of_descriptors();
-  ASSERT(0 <= insertion_index && insertion_index < size);
-
   // Ensure the key is a symbol.
   MaybeObject* maybe_failure = descriptor->KeyToSymbol();
   if (maybe_failure->IsFailure()) return maybe_failure;
 
+  DescriptorArray* descriptors = instance_descriptors();
+
   String* key = descriptor->GetKey();
   ASSERT(key == descriptors->GetKey(insertion_index));
 
+  int new_size = NumberOfOwnDescriptors();
+  ASSERT(0 <= insertion_index && insertion_index < new_size);
+
+  PropertyDetails details = descriptors->GetDetails(insertion_index);
+  ASSERT_LE(details.descriptor_index(), new_size);
+  descriptor->SetEnumerationIndex(details.descriptor_index());
+
   DescriptorArray* new_descriptors;
-  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(size);
+  MaybeObject* maybe_descriptors = DescriptorArray::Allocate(new_size);
   if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
+  DescriptorArray::WhitenessWitness witness(new_descriptors);
 
-  FixedArray::WhitenessWitness witness(new_descriptors);
-
-  // Copy the descriptors, replacing a descriptor.
-  for (int index = 0; index < size; ++index) {
-    if (index == insertion_index) continue;
-    new_descriptors->CopyFrom(index, descriptors, index, witness);
+  for (int i = 0; i < new_size; ++i) {
+    if (i == insertion_index) {
+      new_descriptors->Set(i, descriptor, witness);
+    } else {
+      new_descriptors->CopyFrom(i, descriptors, i, witness);
+    }
   }
 
-  PropertyDetails original_details = descriptors->GetDetails(insertion_index);
-  descriptor->SetEnumerationIndex(original_details.descriptor_index());
-  descriptor->SetSortedKey(original_details.pointer());
-
-  new_descriptors->Set(insertion_index, descriptor, witness);
-
-  SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
+  // Resort if descriptors were removed.

[Jakob Kummerow, 2012/09/11 14:24:25]

nit: s/Resort/Re-sort/

[Toon Verwaest, 2012/09/11 14:49:23]

Done.

+  if (new_size != descriptors->length()) new_descriptors->Sort();
 
   return CopyReplaceDescriptors(new_descriptors, key, flag);
 }
 
 
 void Map::UpdateCodeCache(Handle<Map> map,
                           Handle<String> name,
                           Handle<Code> code) {
   Isolate* isolate = map->GetIsolate();
   CALL_HEAP_FUNCTION_VOID(isolate,
@@ skipping 777 matching lines @@
   return result;
 }
 
 
 void DescriptorArray::SetEnumCache(FixedArray* bridge_storage,
                                    FixedArray* new_cache,
                                    Object* new_index_cache) {
   ASSERT(bridge_storage->length() >= kEnumCacheBridgeLength);
   ASSERT(new_index_cache->IsSmi() || new_index_cache->IsFixedArray());
   if (HasEnumCache()) {
+    ASSERT(new_cache->length() > FixedArray::cast(GetEnumCache())->length());
     FixedArray::cast(get(kEnumCacheIndex))->
       set(kEnumCacheBridgeCacheIndex, new_cache);
     FixedArray::cast(get(kEnumCacheIndex))->
       set(kEnumCacheBridgeIndicesCacheIndex, new_index_cache);
   } else {
-    if (IsEmpty()) return;  // Do nothing for empty descriptor array.
+    ASSERT(!IsEmpty());  // Do nothing for empty descriptor array.

[Jakob Kummerow, 2012/09/11 14:24:25]

outdated comment (just remove it)

[Toon Verwaest, 2012/09/11 14:49:23]

Done.

     FixedArray::cast(bridge_storage)->
       set(kEnumCacheBridgeCacheIndex, new_cache);
     FixedArray::cast(bridge_storage)->
       set(kEnumCacheBridgeIndicesCacheIndex, new_index_cache);
     set(kEnumCacheIndex, bridge_storage);
   }
 }
 
 
 void DescriptorArray::CopyFrom(int dst_index,
@@ skipping 55 matching lines @@
         if (right_child_hash > child_hash) {
           child_index++;
           child_hash = right_child_hash;
         }
       }
       if (child_hash <= parent_hash) break;
       SwapSortedKeys(parent_index, child_index);
       parent_index = child_index;
     }
   }
+  ASSERT(IsSortedNoDuplicates());
 }
 
 
 MaybeObject* AccessorPair::Copy() {
   Heap* heap = GetHeap();
   AccessorPair* copy;
   MaybeObject* maybe_copy = heap->AllocateAccessorPair();
   if (!maybe_copy->To(&copy)) return maybe_copy;
 
   copy->set_getter(getter());
@@ skipping 1227 matching lines @@
 void String::PrintOn(FILE* file) {
   int length = this->length();
   for (int i = 0; i < length; i++) {
     fprintf(file, "%c", Get(i));
   }
 }
 
 
 // Clear a possible back pointer in case the transition leads to a dead map.
 // Return true in case a back pointer has been cleared and false otherwise.
-static bool ClearBackPointer(Heap* heap, Object* target) {
-  ASSERT(target->IsMap());
-  Map* map = Map::cast(target);
-  if (Marking::MarkBitFrom(map).Get()) return false;
-  map->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER);
+static bool ClearBackPointer(Heap* heap, Map* target) {
+  if (Marking::MarkBitFrom(target).Get()) return false;
+  target->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER);
   return true;
 }
 
 
 // TODO(mstarzinger): This method should be moved into MarkCompactCollector,
 // because it cannot be called from outside the GC and we already have methods
 // depending on the transitions layout in the GC anyways.
 void Map::ClearNonLiveTransitions(Heap* heap) {
   // If there are no transitions to be cleared, return.
   // TODO(verwaest) Should be an assert, otherwise back pointers are not
   // properly cleared.
   if (!HasTransitionArray()) return;
 
   TransitionArray* t = transitions();
   MarkCompactCollector* collector = heap->mark_compact_collector();
 
   int transition_index = 0;
 
+  DescriptorArray* descriptors = t->descriptors();
+  bool descriptors_owner_died = false;
+
   // Compact all live descriptors to the left.
   for (int i = 0; i < t->number_of_transitions(); ++i) {
-    if (!ClearBackPointer(heap, t->GetTarget(i))) {
+    Map* target = t->GetTarget(i);
+    if (ClearBackPointer(heap, target)) {
+      if (target->instance_descriptors() == descriptors) {
+        descriptors_owner_died = true;
+      }
+    } else {
       if (i != transition_index) {
         String* key = t->GetKey(i);
         t->SetKey(transition_index, key);
         Object** key_slot = t->GetKeySlot(transition_index);
         collector->RecordSlot(key_slot, key_slot, key);
         // Target slots do not need to be recorded since maps are not compacted.
         t->SetTarget(transition_index, t->GetTarget(i));
       }
       transition_index++;
     }
   }
 
   if (t->HasElementsTransition() &&
       ClearBackPointer(heap, t->elements_transition())) {
+    if (t->elements_transition()->instance_descriptors() == descriptors) {
+      descriptors_owner_died = true;
+    }
     t->ClearElementsTransition();
   } else {
     // If there are no transitions to be cleared, return.
     // TODO(verwaest) Should be an assert, otherwise back pointers are not
     // properly cleared.
     if (transition_index == t->number_of_transitions()) return;
   }
 
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
+
+  if (descriptors_owner_died) {
+    if (number_of_own_descriptors > 0) {
+      int live_enum = NumberOfDescribedProperties(OWN_DESCRIPTORS, DONT_ENUM);
+      int number_of_descriptors = descriptors->number_of_descriptors();
+      int to_trim = number_of_descriptors - number_of_own_descriptors;
+      if (to_trim > 0) {
+        RightTrimFixedArray<FROM_GC>(
+            heap, descriptors, to_trim * DescriptorArray::kDescriptorSize);
+        if (descriptors->HasEnumCache()) {
+          FixedArray* enum_cache =
+              FixedArray::cast(descriptors->GetEnumCache());
+          to_trim = enum_cache->length() - live_enum;
+          if (to_trim > 0) {
+            RightTrimFixedArray<FROM_GC>(
+                heap, FixedArray::cast(descriptors->GetEnumCache()), to_trim);
+          }
+        }
+        descriptors->Sort();
+      }
+      ASSERT(descriptors->number_of_descriptors() == number_of_own_descriptors);
+    } else {
+      t->set_descriptors(heap->empty_descriptor_array());
+    }
+    SetOwnsDescriptors(true);
+  }
+
   // If the final transition array does not contain any live transitions, remove
   // the transition array from the map.
   if (transition_index == 0 &&
       !t->HasElementsTransition() &&
       !t->HasPrototypeTransitions() &&
-      t->descriptors()->IsEmpty()) {
+      number_of_own_descriptors == 0) {
     return ClearTransitions(heap);
   }
 
   int trim = t->number_of_transitions() - transition_index;
   if (trim > 0) {
     RightTrimFixedArray<FROM_GC>(
         heap, t, trim * TransitionArray::kTransitionSize);
   }
 }
 
@@ skipping 3100 matching lines @@
   }
 
   LookupResult result(isolate);
   LocalLookupRealNamedProperty(key, &result);
   return result.IsPropertyCallbacks();
 }
 
 
 int JSObject::NumberOfLocalProperties(PropertyAttributes filter) {
   return HasFastProperties() ?
-      map()->NumberOfDescribedProperties(filter) :
+      map()->NumberOfDescribedProperties(OWN_DESCRIPTORS, filter) :
       property_dictionary()->NumberOfElementsFilterAttributes(filter);
 }
 
 
 void FixedArray::SwapPairs(FixedArray* numbers, int i, int j) {
   Object* temp = get(i);
   set(i, get(j));
   set(j, temp);
   if (this != numbers) {
     temp = numbers->get(i);
@@ skipping 103 matching lines @@
   }
 }
 
 
 // Fill in the names of local properties into the supplied storage. The main
 // purpose of this function is to provide reflection information for the object
 // mirrors.
 void JSObject::GetLocalPropertyNames(FixedArray* storage, int index) {
   ASSERT(storage->length() >= (NumberOfLocalProperties() - index));
   if (HasFastProperties()) {
+    int real_size = map()->NumberOfOwnDescriptors();
     DescriptorArray* descs = map()->instance_descriptors();
-    ASSERT(storage->length() >= index + descs->number_of_descriptors());
-    for (int i = 0; i < descs->number_of_descriptors(); i++) {
+    ASSERT(storage->length() >= index + real_size);
+    for (int i = 0; i < real_size; i++) {
       storage->set(index + i, descs->GetKey(i));
     }
   } else {
     property_dictionary()->CopyKeysTo(storage,
                                       index,
                                       StringDictionary::UNSORTED);
   }
 }
 
 
@@ skipping 1682 matching lines @@
   { MaybeObject* maybe_obj = heap->AllocateFixedArray(length);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   FixedArray* enumeration_order = FixedArray::cast(obj);
 
   // Fill the enumeration order array with property details.
   int capacity = HashTable<Shape, Key>::Capacity();
   int pos = 0;
   for (int i = 0; i < capacity; i++) {
     if (Dictionary<Shape, Key>::IsKey(Dictionary<Shape, Key>::KeyAt(i))) {
-      enumeration_order->set(
-          pos++, Smi::FromInt(DetailsAt(i).dictionary_index()));
+      int index = DetailsAt(i).dictionary_index();
+      enumeration_order->set(pos++, Smi::FromInt(index));
     }
   }
 
   // Sort the arrays wrt. enumeration order.
   iteration_order->SortPairs(enumeration_order, enumeration_order->length());
 
   // Overwrite the enumeration_order with the enumeration indices.
   for (int i = 0; i < length; i++) {
     int index = Smi::cast(iteration_order->get(i))->value();
     int enum_index = PropertyDetails::kInitialIndex + i;
@@ skipping 108 matching lines @@
                                               uint32_t hash) {
   // Compute the key object.
   Object* k;
   { MaybeObject* maybe_k = Shape::AsObject(key);
     if (!maybe_k->ToObject(&k)) return maybe_k;
   }
 
   uint32_t entry = Dictionary<Shape, Key>::FindInsertionEntry(hash);
   // Insert element at empty or deleted entry
   if (!details.IsDeleted() &&
-      details.dictionary_index() == 0 && Shape::kIsEnumerable) {
+      details.dictionary_index() == 0 &&
+      Shape::kIsEnumerable) {
     // Assign an enumeration index to the property and update
     // SetNextEnumerationIndex.
     int index = NextEnumerationIndex();
     details = PropertyDetails(details.attributes(), details.type(), index);
     SetNextEnumerationIndex(index + 1);
   }
   SetEntry(entry, k, value, details);
   ASSERT((Dictionary<Shape, Key>::KeyAt(entry)->IsNumber()
           || Dictionary<Shape, Key>::KeyAt(entry)->IsString()));
   HashTable<Shape, Key>::ElementAdded();
@@ skipping 873 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal