Reland of "TransitionArray now uses <is_data_property, name, attributes> tuple as a key, which allo…

src/transitions.cc

 // 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.
 
 #include "src/v8.h"
 
 #include "src/objects.h"
 #include "src/transitions-inl.h"
 #include "src/utils.h"
 
@@ skipping 30 matching lines @@
 }
 
 
 Handle<TransitionArray> TransitionArray::NewWith(Handle<Map> map,
                                                  Handle<Name> name,
                                                  Handle<Map> target,
                                                  SimpleTransitionFlag flag) {
   Handle<TransitionArray> result;
   Isolate* isolate = name->GetIsolate();
 
-  if (flag == SIMPLE_TRANSITION) {
+  if (flag == SIMPLE_PROPERTY_TRANSITION) {
     result = AllocateSimple(isolate, target);
   } else {
     result = Allocate(isolate, 1);
     result->NoIncrementalWriteBarrierSet(0, *name, *target);
   }
   result->set_back_pointer_storage(map->GetBackPointer());
   return result;
 }
 
 
@@ skipping 25 matching lines @@
                                                 Handle<Name> name,
                                                 Handle<Map> target,
                                                 SimpleTransitionFlag flag) {
   if (!map->HasTransitionArray()) {
     return TransitionArray::NewWith(map, name, target, flag);
   }
 
   int number_of_transitions = map->transitions()->number_of_transitions();
   int new_nof = number_of_transitions;
 
+  bool is_special_transition = flag == SPECIAL_TRANSITION;
+  DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
+  PropertyDetails details = is_special_transition
+                                ? PropertyDetails(NONE, FIELD, 0)
+                                : GetTargetDetails(*name, *target);
+
   int insertion_index = kNotFound;
-  int index = map->transitions()->Search(*name, &insertion_index);
-
+  int index =
+      is_special_transition
+          ? map->transitions()->SearchSpecial(Symbol::cast(*name),
+                                              &insertion_index)
+          : map->transitions()->Search(details.type(), *name,
+                                       details.attributes(), &insertion_index);
   if (index == kNotFound) {
     ++new_nof;
   } else {
     insertion_index = index;
   }
   DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
 
   CHECK(new_nof <= kMaxNumberOfTransitions);
 
   if (new_nof <= map->transitions()->number_of_transitions_storage()) {
     DisallowHeapAllocation no_gc;
     TransitionArray* array = map->transitions();
 
     if (index != kNotFound) {
       array->SetTarget(index, *target);
       return handle(array);
     }
 
     array->SetNumberOfTransitions(new_nof);
     for (index = number_of_transitions; index > insertion_index; --index) {
       Name* key = array->GetKey(index - 1);
-      DCHECK(key->Hash() > name->Hash());
       array->SetKey(index, key);
       array->SetTarget(index, array->GetTarget(index - 1));
     }
     array->SetKey(index, *name);
     array->SetTarget(index, *target);
+    SLOW_DCHECK(array->IsSortedNoDuplicates());
     return handle(array);
   }
 
   Handle<TransitionArray> result = Allocate(
       map->GetIsolate(), new_nof,
       Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
 
   // The map's transition array may grown smaller during the allocation above as
   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
   // result copy if needed, and recompute variables.
   DCHECK(map->HasTransitionArray());
   DisallowHeapAllocation no_gc;
   TransitionArray* array = map->transitions();
   if (array->number_of_transitions() != number_of_transitions) {
     DCHECK(array->number_of_transitions() < number_of_transitions);
 
     number_of_transitions = array->number_of_transitions();
     new_nof = number_of_transitions;
 
     insertion_index = kNotFound;
-    index = array->Search(*name, &insertion_index);
+    index = is_special_transition ? map->transitions()->SearchSpecial(
+                                        Symbol::cast(*name), &insertion_index)
+                                  : map->transitions()->Search(
+                                        details.type(), *name,
+                                        details.attributes(), &insertion_index);
     if (index == kNotFound) {
       ++new_nof;
     } else {
       insertion_index = index;
     }
     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
 
     result->Shrink(ToKeyIndex(new_nof));
     result->SetNumberOfTransitions(new_nof);
   }
 
   if (array->HasPrototypeTransitions()) {
     result->SetPrototypeTransitions(array->GetPrototypeTransitions());
   }
 
   DCHECK_NE(kNotFound, insertion_index);
   for (int i = 0; i < insertion_index; ++i) {
     result->NoIncrementalWriteBarrierCopyFrom(array, i, i);
   }
   result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
   for (int i = insertion_index; i < number_of_transitions; ++i) {
     result->NoIncrementalWriteBarrierCopyFrom(array, i, i + 1);
   }
 
   result->set_back_pointer_storage(array->back_pointer_storage());
+  SLOW_DCHECK(result->IsSortedNoDuplicates());
   return result;
 }
 
 
+int TransitionArray::SearchDetails(int transition, PropertyType type,
+                                   PropertyAttributes attributes,
+                                   int* out_insertion_index) {
+  int nof_transitions = number_of_transitions();
+  DCHECK(transition < nof_transitions);
+  Name* key = GetKey(transition);
+  bool is_data = type == FIELD || type == CONSTANT;
+  for (; transition < nof_transitions && GetKey(transition) == key;
+       transition++) {
+    Map* target = GetTarget(transition);
+    PropertyDetails target_details = GetTargetDetails(key, target);
+
+    bool target_is_data =
+        target_details.type() == FIELD || target_details.type() == CONSTANT;
+
+    int cmp = CompareDetails(is_data, attributes, target_is_data,
+                             target_details.attributes());
+    if (cmp == 0) {
+      return transition;
+    } else if (cmp < 0) {
+      break;
+    }
+  }
+  if (out_insertion_index != NULL) *out_insertion_index = transition;
+  return kNotFound;
+}
+
+
+int TransitionArray::Search(PropertyType type, Name* name,
+                            PropertyAttributes attributes,
+                            int* out_insertion_index) {
+  int transition = SearchName(name, out_insertion_index);
+  if (transition == kNotFound) {
+    return kNotFound;
+  }
+  return SearchDetails(transition, type, attributes, out_insertion_index);
+}
 } }  // namespace v8::internal