[runtime] Ensure that all elements kind transitions are chained to the root map.

src/objects.cc

 // Copyright 2015 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 "src/objects.h"
 
 #include <cmath>
 #include <iomanip>
 #include <sstream>
 
@@ skipping 3198 matching lines @@
 
 int Map::NumberOfFields() {
   DescriptorArray* descriptors = instance_descriptors();
   int result = 0;
   for (int i = 0; i < NumberOfOwnDescriptors(); i++) {
     if (descriptors->GetDetails(i).location() == kField) result++;
   }
   return result;
 }
 
-
 Handle<Map> Map::CopyGeneralizeAllRepresentations(
-    Handle<Map> map, int modify_index, StoreMode store_mode, PropertyKind kind,
-    PropertyAttributes attributes, const char* reason) {
+    Handle<Map> map, ElementsKind elements_kind, int modify_index,
+    StoreMode store_mode, PropertyKind kind, PropertyAttributes attributes,
+    const char* reason) {
   Isolate* isolate = map->GetIsolate();
   Handle<DescriptorArray> old_descriptors(map->instance_descriptors(), isolate);
   int number_of_own_descriptors = map->NumberOfOwnDescriptors();
   Handle<DescriptorArray> descriptors =
       DescriptorArray::CopyUpTo(old_descriptors, number_of_own_descriptors);
 
   for (int i = 0; i < number_of_own_descriptors; i++) {
     descriptors->SetRepresentation(i, Representation::Tagged());
     if (descriptors->GetDetails(i).type() == DATA) {
       descriptors->SetValue(i, FieldType::Any());
@@ skipping 35 matching lines @@
       }
       map->PrintGeneralization(
           stdout, reason, modify_index, new_map->NumberOfOwnDescriptors(),
           new_map->NumberOfOwnDescriptors(),
           details.type() == DATA_CONSTANT && store_mode == FORCE_FIELD,
           details.representation(), Representation::Tagged(), field_type,
           MaybeHandle<Object>(), FieldType::Any(isolate),
           MaybeHandle<Object>());
     }
   }
+  new_map->set_elements_kind(elements_kind);
   return new_map;
 }
 
 
 void Map::DeprecateTransitionTree() {
   if (is_deprecated()) return;
   Object* transitions = raw_transitions();
   int num_transitions = TransitionArray::NumberOfTransitions(transitions);
   for (int i = 0; i < num_transitions; ++i) {
     TransitionArray::GetTarget(transitions, i)->DeprecateTransitionTree();
@@ skipping 232 matching lines @@
   DCHECK_EQ(details.location(), location);
 #endif
   if (location == kField) {
     return handle(descriptors->GetFieldType(descriptor), isolate);
   } else {
     return descriptors->GetValue(descriptor)
         ->OptimalType(isolate, representation);
   }
 }
 
-
-// Reconfigures property at |modify_index| with |new_kind|, |new_attributes|,
-// |store_mode| and/or |new_representation|/|new_field_type|.
+// Reconfigures elements kind to |new_elements_kind| and/or property at
+// |modify_index| with |new_kind|, |new_attributes|, |store_mode| and/or
+// |new_representation|/|new_field_type|.
 // If |modify_index| is negative then no properties are reconfigured but the
 // map is migrated to the up-to-date non-deprecated state.
 //
 // This method rewrites or completes the transition tree to reflect the new
 // change. To avoid high degrees over polymorphism, and to stabilize quickly,
 // on every rewrite the new type is deduced by merging the current type with
 // any potential new (partial) version of the type in the transition tree.
 // To do this, on each rewrite:
 // - Search the root of the transition tree using FindRootMap.
+// - Find/create a |root_map| with requested |new_elements_kind|.
 // - Find |target_map|, the newest matching version of this map using the
 //   virtually "enhanced" |old_map|'s descriptor array (i.e. whose entry at
 //   |modify_index| is considered to be of |new_kind| and having
 //   |new_attributes|) to walk the transition tree.
 // - Merge/generalize the "enhanced" descriptor array of the |old_map| and
 //   descriptor array of the |target_map|.
 // - Generalize the |modify_index| descriptor using |new_representation| and
 //   |new_field_type|.
 // - Walk the tree again starting from the root towards |target_map|. Stop at
 //   |split_map|, the first map who's descriptor array does not match the merged
 //   descriptor array.
 // - If |target_map| == |split_map|, |target_map| is in the expected state.
 //   Return it.
 // - Otherwise, invalidate the outdated transition target from |target_map|, and
 //   replace its transition tree with a new branch for the updated descriptors.
-Handle<Map> Map::ReconfigureProperty(Handle<Map> old_map, int modify_index,
-                                     PropertyKind new_kind,
-                                     PropertyAttributes new_attributes,
-                                     Representation new_representation,
-                                     Handle<FieldType> new_field_type,
-                                     StoreMode store_mode) {
+Handle<Map> Map::Reconfigure(Handle<Map> old_map,
+                             ElementsKind new_elements_kind, int modify_index,
+                             PropertyKind new_kind,
+                             PropertyAttributes new_attributes,
+                             Representation new_representation,
+                             Handle<FieldType> new_field_type,
+                             StoreMode store_mode) {
   DCHECK_NE(kAccessor, new_kind);  // TODO(ishell): not supported yet.
   DCHECK(store_mode != FORCE_FIELD || modify_index >= 0);
   Isolate* isolate = old_map->GetIsolate();
 
   Handle<DescriptorArray> old_descriptors(
       old_map->instance_descriptors(), isolate);
   int old_nof = old_map->NumberOfOwnDescriptors();
 
   // If it's just a representation generalization case (i.e. property kind and
   // attributes stays unchanged) it's fine to transition from None to anything
   // but double without any modification to the object, because the default
   // uninitialized value for representation None can be overwritten by both
   // smi and tagged values. Doubles, however, would require a box allocation.
   if (modify_index >= 0 && !new_representation.IsNone() &&
-      !new_representation.IsDouble()) {
+      !new_representation.IsDouble() &&
+      old_map->elements_kind() == new_elements_kind) {
     PropertyDetails old_details = old_descriptors->GetDetails(modify_index);
     Representation old_representation = old_details.representation();
 
     if (old_representation.IsNone()) {
       DCHECK_EQ(new_kind, old_details.kind());
       DCHECK_EQ(new_attributes, old_details.attributes());
       DCHECK_EQ(DATA, old_details.type());
       if (FLAG_trace_generalization) {
         old_map->PrintGeneralization(
             stdout, "uninitialized field", modify_index,
@@ skipping 12 matching lines @@
                  .Equals(new_representation));
       DCHECK(
           old_descriptors->GetFieldType(modify_index)->NowIs(new_field_type));
       return old_map;
     }
   }
 
   // Check the state of the root map.
   Handle<Map> root_map(old_map->FindRootMap(), isolate);
   if (!old_map->EquivalentToForTransition(*root_map)) {
-    return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                            new_kind, new_attributes,
-                                            "GenAll_NotEquivalent");
+    return CopyGeneralizeAllRepresentations(
+        old_map, new_elements_kind, modify_index, store_mode, new_kind,
+        new_attributes, "GenAll_NotEquivalent");
   }
 
   ElementsKind from_kind = root_map->elements_kind();
-  ElementsKind to_kind = old_map->elements_kind();
+  ElementsKind to_kind = new_elements_kind;
   // TODO(ishell): Add a test for SLOW_SLOPPY_ARGUMENTS_ELEMENTS.
   if (from_kind != to_kind && to_kind != DICTIONARY_ELEMENTS &&
+      to_kind != SLOW_STRING_WRAPPER_ELEMENTS &&
       to_kind != SLOW_SLOPPY_ARGUMENTS_ELEMENTS &&
       !(IsTransitionableFastElementsKind(from_kind) &&
         IsMoreGeneralElementsKindTransition(from_kind, to_kind))) {
-    return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                            new_kind, new_attributes,
-                                            "GenAll_InvalidElementsTransition");
+    return CopyGeneralizeAllRepresentations(
+        old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+        "GenAll_InvalidElementsTransition");
   }
   int root_nof = root_map->NumberOfOwnDescriptors();
   if (modify_index >= 0 && modify_index < root_nof) {
     PropertyDetails old_details = old_descriptors->GetDetails(modify_index);
     if (old_details.kind() != new_kind ||
         old_details.attributes() != new_attributes) {
-      return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                              new_kind, new_attributes,
-                                              "GenAll_RootModification1");
+      return CopyGeneralizeAllRepresentations(
+          old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+          "GenAll_RootModification1");
     }
     if ((old_details.type() != DATA && store_mode == FORCE_FIELD) ||
         (old_details.type() == DATA &&
          (!new_field_type->NowIs(old_descriptors->GetFieldType(modify_index)) ||
           !new_representation.fits_into(old_details.representation())))) {
-      return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                              new_kind, new_attributes,
-                                              "GenAll_RootModification2");
+      return CopyGeneralizeAllRepresentations(
+          old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+          "GenAll_RootModification2");
     }
   }
 
   // From here on, use the map with correct elements kind as root map.
   if (from_kind != to_kind) {
     root_map = Map::AsElementsKind(root_map, to_kind);
   }
 
   Handle<Map> target_map = root_map;
   for (int i = root_nof; i < old_nof; ++i) {
@@ skipping 33 matching lines @@
     Handle<DescriptorArray> tmp_descriptors = handle(
         tmp_map->instance_descriptors(), isolate);
 
     // Check if target map is incompatible.
     PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
     DCHECK_EQ(next_kind, tmp_details.kind());
     DCHECK_EQ(next_attributes, tmp_details.attributes());
     if (next_kind == kAccessor &&
         !EqualImmutableValues(old_descriptors->GetValue(i),
                               tmp_descriptors->GetValue(i))) {
-      return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                              new_kind, new_attributes,
-                                              "GenAll_Incompatible");
+      return CopyGeneralizeAllRepresentations(
+          old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+          "GenAll_Incompatible");
     }
     if (next_location == kField && tmp_details.location() == kDescriptor) break;
 
     Representation tmp_representation = tmp_details.representation();
     if (!next_representation.fits_into(tmp_representation)) break;
 
     PropertyLocation old_location = old_details.location();
     PropertyLocation tmp_location = tmp_details.location();
     if (tmp_location == kField) {
       if (next_kind == kData) {
@@ skipping 72 matching lines @@
 
     // Check if target map is compatible.
 #ifdef DEBUG
     PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
     DCHECK_EQ(next_kind, tmp_details.kind());
     DCHECK_EQ(next_attributes, tmp_details.attributes());
 #endif
     if (next_kind == kAccessor &&
         !EqualImmutableValues(old_descriptors->GetValue(i),
                               tmp_descriptors->GetValue(i))) {
-      return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                              new_kind, new_attributes,
-                                              "GenAll_Incompatible");
+      return CopyGeneralizeAllRepresentations(
+          old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+          "GenAll_Incompatible");
     }
     DCHECK(!tmp_map->is_deprecated());
     target_map = tmp_map;
   }
   target_nof = target_map->NumberOfOwnDescriptors();
   target_descriptors = handle(target_map->instance_descriptors(), isolate);
 
   // Allocate a new descriptor array large enough to hold the required
   // descriptors, with minimally the exact same size as the old descriptor
   // array.
@@ skipping 210 matching lines @@
       split_attributes);
   if (maybe_transition != NULL) {
     maybe_transition->DeprecateTransitionTree();
   }
 
   // If |maybe_transition| is not NULL then the transition array already
   // contains entry for given descriptor. This means that the transition
   // could be inserted regardless of whether transitions array is full or not.
   if (maybe_transition == NULL &&
       !TransitionArray::CanHaveMoreTransitions(split_map)) {
-    return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
-                                            new_kind, new_attributes,
-                                            "GenAll_CantHaveMoreTransitions");
+    return CopyGeneralizeAllRepresentations(
+        old_map, to_kind, modify_index, store_mode, new_kind, new_attributes,
+        "GenAll_CantHaveMoreTransitions");
   }
 
   old_map->NotifyLeafMapLayoutChange();
 
   if (FLAG_trace_generalization && modify_index >= 0) {
     PropertyDetails old_details = old_descriptors->GetDetails(modify_index);
     PropertyDetails new_details = new_descriptors->GetDetails(modify_index);
     MaybeHandle<FieldType> old_field_type;
     MaybeHandle<FieldType> new_field_type;
     MaybeHandle<Object> old_value;
@@ skipping 60 matching lines @@
   if (!old_map->EquivalentToForTransition(root_map)) return MaybeHandle<Map>();
 
   ElementsKind from_kind = root_map->elements_kind();
   ElementsKind to_kind = old_map->elements_kind();
   if (from_kind != to_kind) {
     // Try to follow existing elements kind transitions.
     root_map = root_map->LookupElementsTransitionMap(to_kind);
     if (root_map == NULL) return MaybeHandle<Map>();
     // From here on, use the map with correct elements kind as root map.
   }
-  int root_nof = root_map->NumberOfOwnDescriptors();
+  Map* new_map = root_map->TryReplayPropertyTransitions(*old_map);
+  if (new_map == nullptr) return MaybeHandle<Map>();
+  return handle(new_map);
+}
+
+Map* Map::TryReplayPropertyTransitions(Map* old_map) {
+  DisallowHeapAllocation no_allocation;
+  DisallowDeoptimization no_deoptimization(GetIsolate());
+
+  int root_nof = NumberOfOwnDescriptors();
 
   int old_nof = old_map->NumberOfOwnDescriptors();
   DescriptorArray* old_descriptors = old_map->instance_descriptors();
 
-  Map* new_map = root_map;
+  Map* new_map = this;
   for (int i = root_nof; i < old_nof; ++i) {
     PropertyDetails old_details = old_descriptors->GetDetails(i);
     Map* transition = TransitionArray::SearchTransition(
         new_map, old_details.kind(), old_descriptors->GetKey(i),
         old_details.attributes());
-    if (transition == NULL) return MaybeHandle<Map>();
+    if (transition == NULL) return nullptr;
     new_map = transition;
     DescriptorArray* new_descriptors = new_map->instance_descriptors();
 
     PropertyDetails new_details = new_descriptors->GetDetails(i);
     DCHECK_EQ(old_details.kind(), new_details.kind());
     DCHECK_EQ(old_details.attributes(), new_details.attributes());
     if (!old_details.representation().fits_into(new_details.representation())) {
-      return MaybeHandle<Map>();
+      return nullptr;
     }
     switch (new_details.type()) {
       case DATA: {
         FieldType* new_type = new_descriptors->GetFieldType(i);
         // Cleared field types need special treatment. They represent lost
         // knowledge, so we must first generalize the new_type to "Any".
         if (FieldTypeIsCleared(new_details.representation(), new_type)) {
-          return MaybeHandle<Map>();
+          return nullptr;
         }
         PropertyType old_property_type = old_details.type();
         if (old_property_type == DATA) {
           FieldType* old_type = old_descriptors->GetFieldType(i);
           if (FieldTypeIsCleared(old_details.representation(), old_type) ||
               !old_type->NowIs(new_type)) {
-            return MaybeHandle<Map>();
+            return nullptr;
           }
         } else {
           DCHECK(old_property_type == DATA_CONSTANT);
           Object* old_value = old_descriptors->GetValue(i);
           if (!new_type->NowContains(old_value)) {
-            return MaybeHandle<Map>();
+            return nullptr;
           }
         }
         break;
       }
       case ACCESSOR: {
 #ifdef DEBUG
         FieldType* new_type = new_descriptors->GetFieldType(i);
         DCHECK(new_type->IsAny());
 #endif
         break;
       }
 
       case DATA_CONSTANT:
       case ACCESSOR_CONSTANT: {
         Object* old_value = old_descriptors->GetValue(i);
         Object* new_value = new_descriptors->GetValue(i);
         if (old_details.location() == kField || old_value != new_value) {
-          return MaybeHandle<Map>();
+          return nullptr;
         }
         break;
       }
     }
   }
-  if (new_map->NumberOfOwnDescriptors() != old_nof) return MaybeHandle<Map>();
-  return handle(new_map);
+  if (new_map->NumberOfOwnDescriptors() != old_nof) return nullptr;
+  return new_map;
 }
 
 
 // static
 Handle<Map> Map::Update(Handle<Map> map) {
   if (!map->is_deprecated()) return map;
   return ReconfigureProperty(map, -1, kData, NONE, Representation::None(),
                              FieldType::None(map->GetIsolate()),
                              ALLOW_IN_DESCRIPTOR);
 }
@@ skipping 572 matching lines @@
 
 
 static bool ContainsMap(MapHandleList* maps, Map* map) {
   DCHECK_NOT_NULL(map);
   for (int i = 0; i < maps->length(); ++i) {
     if (!maps->at(i).is_null() && *maps->at(i) == map) return true;
   }
   return false;
 }
 
+Map* Map::FindElementsKindTransitionedMap(MapHandleList* candidates) {
+  DisallowHeapAllocation no_allocation;
+  DisallowDeoptimization no_deoptimization(GetIsolate());
 
-Handle<Map> Map::FindTransitionedMap(Handle<Map> map,
-                                     MapHandleList* candidates) {
-  ElementsKind kind = map->elements_kind();
+  ElementsKind kind = elements_kind();
   bool packed = IsFastPackedElementsKind(kind);
 
   Map* transition = nullptr;
   if (IsTransitionableFastElementsKind(kind)) {
-    for (Map* current = map->ElementsTransitionMap();
-         current != nullptr && current->has_fast_elements();
-         current = current->ElementsTransitionMap()) {
+    // Check the state of the root map.
+    Map* root_map = FindRootMap();
+    if (!EquivalentToForTransition(root_map)) return nullptr;
+    root_map = root_map->LookupElementsTransitionMap(kind);
+    DCHECK_NOT_NULL(root_map);
+    // Starting from the next existing elements kind transition try to
+    // replay the property transitions.
+    for (root_map = root_map->ElementsTransitionMap();
+         root_map != nullptr && root_map->has_fast_elements();
+         root_map = root_map->ElementsTransitionMap()) {
+      Map* current = root_map->TryReplayPropertyTransitions(this);
+      if (current == nullptr) continue;
+
       if (ContainsMap(candidates, current) &&
           (packed || !IsFastPackedElementsKind(current->elements_kind()))) {
         transition = current;
         packed = packed && IsFastPackedElementsKind(current->elements_kind());
       }
     }
   }
-  return transition == nullptr ? Handle<Map>() : handle(transition);
+  return transition;
 }
 
 
 static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
+  // Ensure we are requested to search elements kind transition "near the root".
+  DCHECK_EQ(map->FindRootMap()->NumberOfOwnDescriptors(),
+            map->NumberOfOwnDescriptors());
   Map* current_map = map;
 
   ElementsKind kind = map->elements_kind();
   while (kind != to_kind) {
     Map* next_map = current_map->ElementsTransitionMap();
     if (next_map == nullptr) return current_map;
     kind = next_map->elements_kind();
     current_map = next_map;
   }
 
@@ skipping 108 matching lines @@
   if (IsFastElementsKind(to_kind)) {
     allow_store_transition =
         allow_store_transition && IsTransitionableFastElementsKind(from_kind) &&
         IsMoreGeneralElementsKindTransition(from_kind, to_kind);
   }
 
   if (!allow_store_transition) {
     return Map::CopyAsElementsKind(map, to_kind, OMIT_TRANSITION);
   }
 
-  return Map::AsElementsKind(map, to_kind);
+  return Map::ReconfigureElementsKind(map, to_kind);
 }
 
 
 // static
 Handle<Map> Map::AsElementsKind(Handle<Map> map, ElementsKind kind) {
   Handle<Map> closest_map(FindClosestElementsTransition(*map, kind));
 
   if (closest_map->elements_kind() == kind) {
     return closest_map;
   }
@@ skipping 341 matching lines @@
   if (map_kind != obj_kind) {
     ElementsKind to_kind = GetMoreGeneralElementsKind(map_kind, obj_kind);
     if (IsDictionaryElementsKind(obj_kind)) {
       to_kind = obj_kind;
     }
     if (IsDictionaryElementsKind(to_kind)) {
       NormalizeElements(object);
     } else {
       TransitionElementsKind(object, to_kind);
     }
-    map = Map::AsElementsKind(map, to_kind);
+    map = Map::ReconfigureElementsKind(map, to_kind);
   }
   JSObject::MigrateToMap(object, map);
 }
 
 
 void JSObject::MigrateInstance(Handle<JSObject> object) {
   Handle<Map> original_map(object->map());
   Handle<Map> map = Map::Update(original_map);
   map->set_migration_target(true);
   MigrateToMap(object, map);
@@ skipping 3562 matching lines @@
 
   Handle<Name> name = handle(descriptors->GetKey(new_descriptor));
   ConnectTransition(parent, child, name, SIMPLE_PROPERTY_TRANSITION);
 }
 
 
 Handle<Map> Map::CopyAsElementsKind(Handle<Map> map, ElementsKind kind,
                                     TransitionFlag flag) {
   Map* maybe_elements_transition_map = NULL;
   if (flag == INSERT_TRANSITION) {
+    // Ensure we are requested to add elements kind transition "near the root".
+    DCHECK_EQ(map->FindRootMap()->NumberOfOwnDescriptors(),
+              map->NumberOfOwnDescriptors());
+
     maybe_elements_transition_map = map->ElementsTransitionMap();
     DCHECK(maybe_elements_transition_map == NULL ||
            (maybe_elements_transition_map->elements_kind() ==
                 DICTIONARY_ELEMENTS &&
             kind == DICTIONARY_ELEMENTS));
     DCHECK(!IsFastElementsKind(kind) ||
            IsMoreGeneralElementsKindTransition(map->elements_kind(), kind));
     DCHECK(kind != map->elements_kind());
   }
 
@@ skipping 284 matching lines @@
 Handle<Map> Map::ReconfigureExistingProperty(Handle<Map> map, int descriptor,
                                              PropertyKind kind,
                                              PropertyAttributes attributes) {
   // Dictionaries have to be reconfigured in-place.
   DCHECK(!map->is_dictionary_map());
 
   if (!map->GetBackPointer()->IsMap()) {
     // There is no benefit from reconstructing transition tree for maps without
     // back pointers.
     return CopyGeneralizeAllRepresentations(
-        map, descriptor, FORCE_FIELD, kind, attributes,
+        map, map->elements_kind(), descriptor, FORCE_FIELD, kind, attributes,
         "GenAll_AttributesMismatchProtoMap");
   }
 
   if (FLAG_trace_generalization) {
     map->PrintReconfiguration(stdout, descriptor, kind, attributes);
   }
 
   Isolate* isolate = map->GetIsolate();
   Handle<Map> new_map = ReconfigureProperty(
       map, descriptor, kind, attributes, Representation::None(),
@@ skipping 9290 matching lines @@
   if (cell->value() != *new_value) {
     cell->set_value(*new_value);
     Isolate* isolate = cell->GetIsolate();
     cell->dependent_code()->DeoptimizeDependentCodeGroup(
         isolate, DependentCode::kPropertyCellChangedGroup);
   }
 }
 
 }  // namespace internal
 }  // namespace v8