[builtins] Fix Array.prototype.concat bug

src/builtins.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/builtins.h"
 
 #include "src/api.h"
 #include "src/api-arguments.h"
 #include "src/api-natives.h"
 #include "src/base/once.h"
@@ skipping 205 matching lines @@
 
 
 inline bool PrototypeHasNoElements(PrototypeIterator* iter) {
   DisallowHeapAllocation no_gc;
   for (; !iter->IsAtEnd(); iter->Advance()) {
     if (iter->GetCurrent()->IsJSProxy()) return false;
     JSObject* current = iter->GetCurrent<JSObject>();
     if (current->IsAccessCheckNeeded()) return false;
     if (current->HasIndexedInterceptor()) return false;
     if (current->elements()->length() != 0) return false;
+    if (current->HasStringWrapperElements()) return false;
   }
   return true;
 }
 
-
 inline bool IsJSArrayFastElementMovingAllowed(Isolate* isolate,
                                               JSArray* receiver) {
   DisallowHeapAllocation no_gc;
   // If the array prototype chain is intact (and free of elements), and if the
   // receiver's prototype is the array prototype, then we are done.
   Object* prototype = receiver->map()->prototype();
   if (prototype->IsJSArray() &&
       isolate->is_initial_array_prototype(JSArray::cast(prototype)) &&
       isolate->IsFastArrayConstructorPrototypeChainIntact()) {
     return true;
   }
-
   // Slow case.
   PrototypeIterator iter(isolate, receiver);
   return PrototypeHasNoElements(&iter);
 }
 
+inline bool HasOnlySimpleReceiverElements(Isolate* isolate,
+                                          JSReceiver* receiver) {
+  // Check that we have no accessors on the receiver's elements.
+  JSObject* object = JSObject::cast(receiver);
+  if (object->GetElementsAccessor()->HasAccessors(object)) return false;
+  // Check that ther are not elements on the prototype.
+  DisallowHeapAllocation no_gc;
+  PrototypeIterator iter(isolate, receiver);
+  return PrototypeHasNoElements(&iter);
+}
+
+inline bool HasOnlySimpleElements(Isolate* isolate, JSReceiver* receiver) {
+  // Check that ther are not elements on the prototype.
+  DisallowHeapAllocation no_gc;
+  PrototypeIterator iter(isolate, receiver,
+                         PrototypeIterator::START_AT_RECEIVER);
+  for (; !iter.IsAtEnd(); iter.Advance()) {
+    if (iter.GetCurrent()->IsJSProxy()) return false;
+    JSObject* current = iter.GetCurrent<JSObject>();
+    if (current->IsAccessCheckNeeded()) return false;
+    if (current->HasIndexedInterceptor()) return false;
+    if (current->HasStringWrapperElements()) return false;
+    if (current->GetElementsAccessor()->HasAccessors(current)) return false;
+  }
+  return true;
+}
+
 // Returns |false| if not applicable.
 MUST_USE_RESULT
 inline bool EnsureJSArrayWithWritableFastElements(Isolate* isolate,
                                                   Handle<Object> receiver,
                                                   Arguments* args,
                                                   int first_added_arg) {
   if (!receiver->IsJSArray()) return false;
   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
   // If there may be elements accessors in the prototype chain, the fast path
   // cannot be used if there arguments to add to the array.
   if (args != nullptr && !IsJSArrayFastElementMovingAllowed(isolate, *array)) {
     return false;
   }
-  ElementsKind origin_kind = array->map()->elements_kind();
+  ElementsKind origin_kind = array->GetElementsKind();
   if (IsDictionaryElementsKind(origin_kind)) return false;
   if (array->map()->is_observed()) return false;
   if (!array->map()->is_extensible()) return false;
   if (args == nullptr) return true;
 
   // Adding elements to the array prototype would break code that makes sure
   // it has no elements. Handle that elsewhere.
   if (isolate->IsAnyInitialArrayPrototype(array)) return false;
 
   // Need to ensure that the arguments passed in args can be contained in
@@ skipping 784 matching lines @@
     Handle<Object> key = isolate->factory()->length_string();
     ASSIGN_RETURN_ON_EXCEPTION_VALUE(
         isolate, val, Runtime::GetObjectProperty(isolate, receiver, key),
         false);
     ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, val,
                                      Object::ToLength(isolate, val), false);
     // TODO(caitp): Support larger element indexes (up to 2^53-1).
     if (!val->ToUint32(&length)) {
       length = 0;
     }
+    // TODO(cbruni): handle other element kind as well
+    return IterateElementsSlow(isolate, receiver, length, visitor);
   }
 
-  if (!receiver->IsJSArray()) {
-    // For classes which are not known to be safe to access via elements alone,
-    // use the slow case.
+  if (!HasOnlySimpleElements(isolate, *receiver)) {

[Toon Verwaest, 2016/03/15 19:10:15]

I'd keep the IsJSArray for now to ensure that the Min below isn't necessary
(it's wrong anyway...)

     return IterateElementsSlow(isolate, receiver, length, visitor);
   }
   Handle<JSObject> array = Handle<JSObject>::cast(receiver);
 
   switch (array->GetElementsKind()) {
     case FAST_SMI_ELEMENTS:
     case FAST_ELEMENTS:
     case FAST_HOLEY_SMI_ELEMENTS:
     case FAST_HOLEY_ELEMENTS: {
       // Run through the elements FixedArray and use HasElement and GetElement
       // to check the prototype for missing elements.
       Handle<FixedArray> elements(FixedArray::cast(array->elements()));
       int fast_length = static_cast<int>(length);
-      DCHECK(fast_length <= elements->length());
+      fast_length = Min(fast_length, elements->length());
       for (int j = 0; j < fast_length; j++) {
         HandleScope loop_scope(isolate);
         Handle<Object> element_value(elements->get(j), isolate);
         if (!element_value->IsTheHole()) {
           if (!visitor->visit(j, element_value)) return false;
         } else {
           Maybe<bool> maybe = JSReceiver::HasElement(array, j);
           if (!maybe.IsJust()) return false;
           if (maybe.FromJust()) {
             // Call GetElement on array, not its prototype, or getters won't
@@ skipping 39 matching lines @@
                 isolate, element_value,
                 JSReceiver::GetElement(isolate, array, j), false);
             if (!visitor->visit(j, element_value)) return false;
           }
         }
       }
       break;
     }
 
     case DICTIONARY_ELEMENTS: {
-      // CollectElementIndices() can't be called when there's a JSProxy
-      // on the prototype chain.
-      for (PrototypeIterator iter(isolate, array); !iter.IsAtEnd();
-           iter.Advance()) {
-        if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
-          return IterateElementsSlow(isolate, array, length, visitor);
-        }
-      }
       Handle<SeededNumberDictionary> dict(array->element_dictionary());
       List<uint32_t> indices(dict->Capacity() / 2);
       // Collect all indices in the object and the prototypes less
       // than length. This might introduce duplicates in the indices list.
       CollectElementIndices(array, length, &indices);
       indices.Sort(&compareUInt32);
       int j = 0;
       int n = indices.length();
       while (j < n) {
         HandleScope loop_scope(isolate);
@@ skipping 20 matching lines @@
             false);
         if (!visitor->visit(index, element)) return false;
       }
       break;
     }
     case NO_ELEMENTS:
       break;
 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
       TYPED_ARRAYS(TYPED_ARRAY_CASE)
 #undef TYPED_ARRAY_CASE
+      return IterateElementsSlow(isolate, receiver, length, visitor);
     case FAST_STRING_WRAPPER_ELEMENTS:
     case SLOW_STRING_WRAPPER_ELEMENTS:
       // |array| is guaranteed to be an array or typed array.
       UNREACHABLE();
       break;
   }
   visitor->increase_index_offset(length);
   return true;
 }
 
@@ skipping 37 matching lines @@
   for (int i = 0; i < argument_count; i++) {
     HandleScope loop_scope(isolate);
     Handle<Object> obj((*args)[i], isolate);
     uint32_t length_estimate;
     uint32_t element_estimate;
     if (obj->IsJSArray()) {
       Handle<JSArray> array(Handle<JSArray>::cast(obj));
       length_estimate = static_cast<uint32_t>(array->length()->Number());
       if (length_estimate != 0) {
         ElementsKind array_kind =
-            GetPackedElementsKind(array->map()->elements_kind());
+            GetPackedElementsKind(array->GetElementsKind());
         kind = GetMoreGeneralElementsKind(kind, array_kind);
       }
       element_estimate = EstimateElementCount(array);
     } else {
       if (obj->IsHeapObject()) {
-        if (obj->IsNumber()) {
-          kind = GetMoreGeneralElementsKind(kind, FAST_DOUBLE_ELEMENTS);
-        } else {
-          kind = GetMoreGeneralElementsKind(kind, FAST_ELEMENTS);
-        }
+        kind = GetMoreGeneralElementsKind(
+            kind, obj->IsNumber() ? FAST_DOUBLE_ELEMENTS : FAST_ELEMENTS);
       }
       length_estimate = 1;
       element_estimate = 1;
     }
     // Avoid overflows by capping at kMaxElementCount.
     if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
       estimate_result_length = JSObject::kMaxElementCount;
     } else {
       estimate_result_length += length_estimate;
     }
@@ skipping 22 matching lines @@
         Handle<Object> obj((*args)[i], isolate);
         if (obj->IsSmi()) {
           double_storage->set(j, Smi::cast(*obj)->value());
           j++;
         } else if (obj->IsNumber()) {
           double_storage->set(j, obj->Number());
           j++;
         } else {
           JSArray* array = JSArray::cast(*obj);
           uint32_t length = static_cast<uint32_t>(array->length()->Number());
-          switch (array->map()->elements_kind()) {
+          switch (array->GetElementsKind()) {
             case FAST_HOLEY_DOUBLE_ELEMENTS:
             case FAST_DOUBLE_ELEMENTS: {
               // Empty array is FixedArray but not FixedDoubleArray.
               if (length == 0) break;
               FixedDoubleArray* elements =
                   FixedDoubleArray::cast(array->elements());
               for (uint32_t i = 0; i < length; i++) {
                 if (elements->is_the_hole(i)) {
                   // TODO(jkummerow/verwaest): We could be a bit more clever
                   // here: Check if there are no elements/getters on the
@@ skipping 31 matching lines @@
               DCHECK_EQ(0u, length);
               break;
             default:
               UNREACHABLE();
           }
         }
         if (failure) break;
       }
     }
     if (!failure) {
-      Handle<JSArray> array = isolate->factory()->NewJSArray(0);
-      Smi* length = Smi::FromInt(j);
-      Handle<Map> map;
-      map = JSObject::GetElementsTransitionMap(array, kind);
-      array->set_map(*map);
-      array->set_length(length);
-      array->set_elements(*storage);
-      return *array;
+      return *isolate->factory()->NewJSArrayWithElements(storage, kind, j);
     }
     // In case of failure, fall through.
   }
 
   Handle<Object> storage;
   if (fast_case) {
     // The backing storage array must have non-existing elements to preserve
     // holes across concat operations.
     storage =
         isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
@@ skipping 36 matching lines @@
 
   if (is_array_species) {
     return *visitor.ToArray();
   } else {
     return *visitor.storage_jsreceiver();
   }
 }
 
 
 MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate, Arguments* args) {
-  if (!isolate->IsFastArrayConstructorPrototypeChainIntact()) {
-    return MaybeHandle<JSArray>();
-  }
   int n_arguments = args->length();
   int result_len = 0;
   {
     DisallowHeapAllocation no_gc;
-    Object* array_proto = isolate->array_function()->prototype();
     // Iterate through all the arguments performing checks
     // and calculating total length.
     for (int i = 0; i < n_arguments; i++) {
       Object* arg = (*args)[i];
       if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
+      if (!HasOnlySimpleReceiverElements(isolate, JSObject::cast(arg))) {
+        return MaybeHandle<JSArray>();
+      }
+      // TODO(cbruni): support fast concatenation of DICTIONARY_ELEMENTS.
+      if (!JSObject::cast(arg)->HasFastElements()) {
+        return MaybeHandle<JSArray>();
+      }
       Handle<JSArray> array(JSArray::cast(arg), isolate);
-      if (!array->HasFastElements()) return MaybeHandle<JSArray>();
-      PrototypeIterator iter(isolate, *array);
-      if (iter.GetCurrent() != array_proto) return MaybeHandle<JSArray>();
       if (HasConcatSpreadableModifier(isolate, array)) {
         return MaybeHandle<JSArray>();
       }
       int len = Smi::cast(array->length())->value();
 
       // We shouldn't overflow when adding another len.
       const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
       STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
       USE(kHalfOfMaxInt);
       result_len += len;
@@ skipping 3088 matching lines @@
 BUILTIN_LIST_C(DEFINE_BUILTIN_ACCESSOR_C)
 BUILTIN_LIST_A(DEFINE_BUILTIN_ACCESSOR_A)
 BUILTIN_LIST_H(DEFINE_BUILTIN_ACCESSOR_H)
 BUILTIN_LIST_DEBUG_A(DEFINE_BUILTIN_ACCESSOR_A)
 #undef DEFINE_BUILTIN_ACCESSOR_C
 #undef DEFINE_BUILTIN_ACCESSOR_A
 
 
 }  // namespace internal
 }  // namespace v8