Preserve order of fields when doing slow-to-fast object migration.

src/objects.cc

 // Copyright 2013 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.
 
 #include <sstream>
 
 #include "src/v8.h"
 
 #include "src/accessors.h"
 #include "src/allocation-site-scopes.h"
@@ skipping 4262 matching lines @@
   DCHECK(!object->IsGlobalObject());
   Isolate* isolate = object->GetIsolate();
   Factory* factory = isolate->factory();
   Handle<NameDictionary> dictionary(object->property_dictionary());
 
   // Make sure we preserve dictionary representation if there are too many
   // descriptors.
   int number_of_elements = dictionary->NumberOfElements();
   if (number_of_elements > kMaxNumberOfDescriptors) return;
 
+  Handle<FixedArray> iteration_order;
   if (number_of_elements != dictionary->NextEnumerationIndex()) {
-    NameDictionary::DoGenerateNewEnumerationIndices(dictionary);
+    iteration_order =
+        NameDictionary::DoGenerateNewEnumerationIndices(dictionary);
+  } else {
+    iteration_order = NameDictionary::BuildIterationIndicesArray(dictionary);
   }
 
-  int instance_descriptor_length = 0;
+  int instance_descriptor_length = iteration_order->length();
   int number_of_fields = 0;
 
   // Compute the length of the instance descriptor.
-  int capacity = dictionary->Capacity();
-  for (int i = 0; i < capacity; i++) {
-    Object* k = dictionary->KeyAt(i);
-    if (dictionary->IsKey(k)) {
-      Object* value = dictionary->ValueAt(i);
-      PropertyType type = dictionary->DetailsAt(i).type();
-      DCHECK(type != FIELD);
-      instance_descriptor_length++;
-      if (type == NORMAL && !value->IsJSFunction()) {
-        number_of_fields += 1;
-      }
+  for (int i = 0; i < instance_descriptor_length; i++) {
+    int index = Smi::cast(iteration_order->get(i))->value();
+    DCHECK(dictionary->IsKey(dictionary->KeyAt(index)));
+
+    Object* value = dictionary->ValueAt(index);
+    PropertyType type = dictionary->DetailsAt(index).type();
+    DCHECK(type != FIELD);
+    if (type == NORMAL && !value->IsJSFunction()) {
+      number_of_fields += 1;
     }
   }
 
   int inobject_props = object->map()->inobject_properties();
 
   // Allocate new map.
   Handle<Map> new_map = Map::CopyDropDescriptors(handle(object->map()));
   new_map->set_dictionary_map(false);
 
   if (instance_descriptor_length == 0) {
@@ skipping 19 matching lines @@
     number_of_allocated_fields = 0;
     unused_property_fields = inobject_props - number_of_fields;
   }
 
   // Allocate the fixed array for the fields.
   Handle<FixedArray> fields = factory->NewFixedArray(
       number_of_allocated_fields);
 
   // Fill in the instance descriptor and the fields.
   int current_offset = 0;
-  for (int i = 0; i < capacity; i++) {
-    Object* k = dictionary->KeyAt(i);
-    if (dictionary->IsKey(k)) {
-      Object* value = dictionary->ValueAt(i);
-      Handle<Name> key;
-      if (k->IsSymbol()) {
-        key = handle(Symbol::cast(k));
+  for (int i = 0; i < instance_descriptor_length; i++) {
+    int index = Smi::cast(iteration_order->get(i))->value();
+    Object* k = dictionary->KeyAt(index);
+    DCHECK(dictionary->IsKey(k));
+
+    Object* value = dictionary->ValueAt(index);
+    Handle<Name> key;
+    if (k->IsSymbol()) {
+      key = handle(Symbol::cast(k));
+    } else {
+      // Ensure the key is a unique name before writing into the
+      // instance descriptor.
+      key = factory->InternalizeString(handle(String::cast(k)));
+    }
+
+    PropertyDetails details = dictionary->DetailsAt(index);
+    int enumeration_index = details.dictionary_index();
+    PropertyType type = details.type();
+
+    if (value->IsJSFunction()) {
+      ConstantDescriptor d(key, handle(value, isolate), details.attributes());
+      descriptors->Set(enumeration_index - 1, &d);
+    } else if (type == NORMAL) {
+      if (current_offset < inobject_props) {
+        object->InObjectPropertyAtPut(current_offset, value,
+                                      UPDATE_WRITE_BARRIER);
       } else {
-        // Ensure the key is a unique name before writing into the
-        // instance descriptor.
-        key = factory->InternalizeString(handle(String::cast(k)));
+        int offset = current_offset - inobject_props;
+        fields->set(offset, value);
       }
-
-      PropertyDetails details = dictionary->DetailsAt(i);
-      int enumeration_index = details.dictionary_index();
-      PropertyType type = details.type();
-
-      if (value->IsJSFunction()) {
-        ConstantDescriptor d(key,
-                             handle(value, isolate),
-                             details.attributes());
-        descriptors->Set(enumeration_index - 1, &d);
-      } else if (type == NORMAL) {
-        if (current_offset < inobject_props) {
-          object->InObjectPropertyAtPut(current_offset,
-                                        value,
-                                        UPDATE_WRITE_BARRIER);
-        } else {
-          int offset = current_offset - inobject_props;
-          fields->set(offset, value);
-        }
-        FieldDescriptor d(key,
-                          current_offset++,
-                          details.attributes(),
-                          // TODO(verwaest): value->OptimalRepresentation();
-                          Representation::Tagged());
-        descriptors->Set(enumeration_index - 1, &d);
-      } else if (type == CALLBACKS) {
-        CallbacksDescriptor d(key,
-                              handle(value, isolate),
-                              details.attributes());
-        descriptors->Set(enumeration_index - 1, &d);
-      } else {
-        UNREACHABLE();
-      }
+      FieldDescriptor d(key, current_offset++, details.attributes(),
+                        // TODO(verwaest): value->OptimalRepresentation();
+                        Representation::Tagged());
+      descriptors->Set(enumeration_index - 1, &d);
+    } else if (type == CALLBACKS) {
+      CallbacksDescriptor d(key, handle(value, isolate), details.attributes());
+      descriptors->Set(enumeration_index - 1, &d);
+    } else {
+      UNREACHABLE();
     }
   }
   DCHECK(current_offset == number_of_fields);
 
   descriptors->Sort();
 
   DisallowHeapAllocation no_gc;
   new_map->InitializeDescriptors(*descriptors);
   new_map->set_unused_property_fields(unused_property_fields);
 
@@ skipping 9703 matching lines @@
             NameDictionary, NameDictionaryShape, Handle<Name> >::SortMode);
 
 template int
 Dictionary<NameDictionary, NameDictionaryShape, Handle<Name> >::
     NumberOfElementsFilterAttributes(PropertyAttributes);
 
 template Handle<NameDictionary>
 Dictionary<NameDictionary, NameDictionaryShape, Handle<Name> >::Add(
     Handle<NameDictionary>, Handle<Name>, Handle<Object>, PropertyDetails);
 
-template void
-Dictionary<NameDictionary, NameDictionaryShape, Handle<Name> >::
-    GenerateNewEnumerationIndices(Handle<NameDictionary>);
+template Handle<FixedArray> Dictionary<
+    NameDictionary, NameDictionaryShape,
+    Handle<Name> >::BuildIterationIndicesArray(Handle<NameDictionary>);
+
+template Handle<FixedArray> Dictionary<
+    NameDictionary, NameDictionaryShape,
+    Handle<Name> >::GenerateNewEnumerationIndices(Handle<NameDictionary>);
 
 template int
 Dictionary<SeededNumberDictionary, SeededNumberDictionaryShape, uint32_t>::
     NumberOfElementsFilterAttributes(PropertyAttributes);
 
 template Handle<SeededNumberDictionary>
 Dictionary<SeededNumberDictionary, SeededNumberDictionaryShape, uint32_t>::
     Add(Handle<SeededNumberDictionary>,
         uint32_t,
         Handle<Object>,
@@ skipping 785 matching lines @@
                                                at_least_space_for,
                                                USE_DEFAULT_MINIMUM_CAPACITY,
                                                pretenure);
 
   // Initialize the next enumeration index.
   dict->SetNextEnumerationIndex(PropertyDetails::kInitialIndex);
   return dict;
 }
 
 
-template<typename Derived, typename Shape, typename Key>
-void Dictionary<Derived, Shape, Key>::GenerateNewEnumerationIndices(
+template <typename Derived, typename Shape, typename Key>
+Handle<FixedArray> Dictionary<Derived, Shape, Key>::BuildIterationIndicesArray(
     Handle<Derived> dictionary) {
   Factory* factory = dictionary->GetIsolate()->factory();
   int length = dictionary->NumberOfElements();
 
-  // Allocate and initialize iteration order array.
   Handle<FixedArray> iteration_order = factory->NewFixedArray(length);
-  for (int i = 0; i < length; i++) {
-    iteration_order->set(i, Smi::FromInt(i));
-  }
-
-  // Allocate array with enumeration order.
   Handle<FixedArray> enumeration_order = factory->NewFixedArray(length);
 
-  // Fill the enumeration order array with property details.
+  // Fill both the iteration order array and the enumeration order array
+  // with property details.
   int capacity = dictionary->Capacity();
   int pos = 0;
   for (int i = 0; i < capacity; i++) {
     if (dictionary->IsKey(dictionary->KeyAt(i))) {
       int index = dictionary->DetailsAt(i).dictionary_index();
-      enumeration_order->set(pos++, Smi::FromInt(index));
+      iteration_order->set(pos, Smi::FromInt(i));
+      enumeration_order->set(pos, Smi::FromInt(index));
+      pos++;
     }
   }
+  DCHECK(pos == length);
 
   // Sort the arrays wrt. enumeration order.
   iteration_order->SortPairs(*enumeration_order, enumeration_order->length());
+  return iteration_order;
+}
 
-  // Overwrite the enumeration_order with the enumeration indices.
+
+template <typename Derived, typename Shape, typename Key>
+Handle<FixedArray>
+Dictionary<Derived, Shape, Key>::GenerateNewEnumerationIndices(
+    Handle<Derived> dictionary) {
+  int length = dictionary->NumberOfElements();
+
+  Handle<FixedArray> iteration_order = BuildIterationIndicesArray(dictionary);
+  DCHECK(iteration_order->length() == length);
+
+  // Iterate over the dictionary using the enumeration order and update
+  // the dictionary with new enumeration indices.
   for (int i = 0; i < length; i++) {
     int index = Smi::cast(iteration_order->get(i))->value();
+    DCHECK(dictionary->IsKey(dictionary->KeyAt(index)));
+
     int enum_index = PropertyDetails::kInitialIndex + i;
-    enumeration_order->set(index, Smi::FromInt(enum_index));
-  }
 
-  // Update the dictionary with new indices.
-  capacity = dictionary->Capacity();
-  pos = 0;
-  for (int i = 0; i < capacity; i++) {
-    if (dictionary->IsKey(dictionary->KeyAt(i))) {
-      int enum_index = Smi::cast(enumeration_order->get(pos++))->value();
-      PropertyDetails details = dictionary->DetailsAt(i);
-      PropertyDetails new_details = PropertyDetails(
-          details.attributes(), details.type(), enum_index);
-      dictionary->DetailsAtPut(i, new_details);
-    }
+    PropertyDetails details = dictionary->DetailsAt(index);
+    PropertyDetails new_details =
+        PropertyDetails(details.attributes(), details.type(), enum_index);
+    dictionary->DetailsAtPut(index, new_details);
   }
 
   // Set the next enumeration index.
   dictionary->SetNextEnumerationIndex(PropertyDetails::kInitialIndex+length);
+  return iteration_order;
 }
 
 
 template<typename Derived, typename Shape, typename Key>
 Handle<Derived> Dictionary<Derived, Shape, Key>::EnsureCapacity(
     Handle<Derived> dictionary, int n, Key key) {
   // Check whether there are enough enumeration indices to add n elements.
   if (Shape::kIsEnumerable &&
       !PropertyDetails::IsValidIndex(dictionary->NextEnumerationIndex() + n)) {
     // If not, we generate new indices for the properties.
@@ skipping 1405 matching lines @@
   Handle<DependentCode> codes =
       DependentCode::Insert(handle(cell->dependent_code(), info->isolate()),
                             DependentCode::kPropertyCellChangedGroup,
                             info->object_wrapper());
   if (*codes != cell->dependent_code()) cell->set_dependent_code(*codes);
   info->dependencies(DependentCode::kPropertyCellChangedGroup)->Add(
       cell, info->zone());
 }
 
 } }  // namespace v8::internal