From 68f1c73a0665f4fce3924ae55e31460e8d6c6967 Mon Sep 17 00:00:00 2001 From: "lrn@chromium.org" Date: Thu, 24 Feb 2011 14:00:52 +0000 Subject: [PATCH] Fix array concat to follow the specification in the presence of element getters. Also fix issue 1175 and 1177. BUG=v8:1175 Review URL: http://codereview.chromium.org/6568007 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6934 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 1 - src/handles-inl.h | 14 +- src/handles.h | 51 +++- src/objects-inl.h | 4 + src/runtime.cc | 638 ++++++++++++++++++++++++------------------- test/mjsunit/array-concat.js | 44 ++- 6 files changed, 463 insertions(+), 289 deletions(-) diff --git a/src/array.js b/src/array.js index ef82674..ead3710 100644 --- a/src/array.js +++ b/src/array.js @@ -418,7 +418,6 @@ function ArrayPush() { function ArrayConcat(arg1) { // length == 1 - // TODO: can we just use arguments? var arg_count = %_ArgumentsLength(); var arrays = new $Array(1 + arg_count); arrays[0] = this; diff --git a/src/handles-inl.h b/src/handles-inl.h index b313512..1811023 100644 --- a/src/handles-inl.h +++ b/src/handles-inl.h @@ -36,14 +36,14 @@ namespace v8 { namespace internal { -template +template Handle::Handle(T* obj) { ASSERT(!obj->IsFailure()); location_ = HandleScope::CreateHandle(obj); } -template +template inline T* Handle::operator*() const { ASSERT(location_ != NULL); ASSERT(reinterpret_cast
(*location_) != kHandleZapValue); @@ -51,6 +51,16 @@ inline T* Handle::operator*() const { } +template +HandleCell::HandleCell(T* value) + : location_(HandleScope::CreateHandle(value)) { } + + +template +HandleCell::HandleCell(Handle value) + : location_(HandleScope::CreateHandle(*value)) { } + + #ifdef DEBUG inline NoHandleAllocation::NoHandleAllocation() { v8::ImplementationUtilities::HandleScopeData* current = diff --git a/src/handles.h b/src/handles.h index d95ca91..d7bf03f 100644 --- a/src/handles.h +++ b/src/handles.h @@ -39,7 +39,7 @@ namespace internal { // Handles are only valid within a HandleScope. // When a handle is created for an object a cell is allocated in the heap. -template +template class Handle { public: INLINE(explicit Handle(T** location)) { location_ = location; } @@ -93,6 +93,55 @@ class Handle { }; +// A handle-scope based variable. The value stored in the variable can change +// over time. The value stored in the variable at any time is a root +// for garbage collection. +// The variable is backed by the current HandleScope. +template +class HandleCell { + public: + // Create a new HandleCell holding the given value. + explicit HandleCell(Handle value); + explicit HandleCell(T* value); + + // Create an alias of an existing HandleCell. + explicit HandleCell(const HandleCell& value) + : location_(value.location_) { } + + INLINE(T* operator->() const) { return operator*(); } + INLINE(T* operator*() const) { + return *location_; + } + INLINE(void operator=(T* value)) { + *location_ = value; + } + INLINE(void operator=(Handle value)) { + *location_ = *value; + } + INLINE(void operator=(const HandleCell& value)) { + *location_ = *value.location_; + } + + // Extract the value of the variable and cast it to a give type. + // This is typically used for calling methods on a more specialized type. + template + inline S* cast() { + S::cast(*location_); + return *reinterpret_cast(location_); + } + + Handle ToHandle() const { + return Handle(*location_); + } + + private: + // Prevent implicit constructor from being created. + HandleCell(); + + T** location_; +}; + + // A stack-allocated class that governs a number of local handles. // After a handle scope has been created, all local handles will be // allocated within that handle scope until either the handle scope is diff --git a/src/objects-inl.h b/src/objects-inl.h index 24887a0..f955d33 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -769,6 +769,10 @@ bool Object::HasSpecificClassOf(String* name) { MaybeObject* Object::GetElement(uint32_t index) { + // GetElement can trigger a getter which can cause allocation. + // This was not always the case. This ASSERT is here to catch + // leftover incorrect uses. + ASSERT(Heap::IsAllocationAllowed()); return GetElementWithReceiver(this, index); } diff --git a/src/runtime.cc b/src/runtime.cc index 5a443ef..d40565c 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -8028,377 +8028,448 @@ static MaybeObject* Runtime_PushIfAbsent(Arguments args) { class ArrayConcatVisitor { public: ArrayConcatVisitor(Handle storage, - uint32_t index_limit, bool fast_elements) : - storage_(storage), index_limit_(index_limit), - index_offset_(0), fast_elements_(fast_elements) { } + storage_(storage), + index_offset_(0u), + fast_elements_(fast_elements) { } void visit(uint32_t i, Handle elm) { - if (i >= index_limit_ - index_offset_) return; + if (i >= JSObject::kMaxElementCount - index_offset_) return; uint32_t index = index_offset_ + i; if (fast_elements_) { - ASSERT(index < static_cast(storage_->length())); - storage_->set(index, *elm); - - } else { - Handle dict = Handle::cast(storage_); - Handle result = - Factory::DictionaryAtNumberPut(dict, index, elm); - if (!result.is_identical_to(dict)) - storage_ = result; + if (index < static_cast(storage_->length())) { + storage_->set(index, *elm); + return; + } + // Our initial estimate of length was foiled, possibly by + // getters on the arrays increasing the length of later arrays + // during iteration. + // This shouldn't happen in anything but pathological cases. + SetDictionaryMode(index); + // Fall-through to dictionary mode. } - } + ASSERT(!fast_elements_); + Handle dict(storage_.cast()); + Handle result = + Factory::DictionaryAtNumberPut(dict, index, elm); + if (!result.is_identical_to(dict)) { + storage_ = Handle::cast(result); + } +} void increase_index_offset(uint32_t delta) { - if (index_limit_ - index_offset_ < delta) { - index_offset_ = index_limit_; + if (JSObject::kMaxElementCount - index_offset_ < delta) { + index_offset_ = JSObject::kMaxElementCount; } else { index_offset_ += delta; } } - Handle storage() { return storage_; } + Handle ToArray() { + Handle array = Factory::NewJSArray(0); + Handle length = + Factory::NewNumber(static_cast(index_offset_)); + Handle map; + if (fast_elements_) { + map = Factory::GetFastElementsMap(Handle(array->map())); + } else { + map = Factory::GetSlowElementsMap(Handle(array->map())); + } + array->set_map(*map); + array->set_length(*length); + array->set_elements(*storage_); + return array; + } private: - Handle storage_; - // Limit on the accepted indices. Elements with indices larger than the - // limit are ignored by the visitor. - uint32_t index_limit_; - // Index after last seen index. Always less than or equal to index_limit_. + // Convert storage to dictionary mode. + void SetDictionaryMode(uint32_t index) { + ASSERT(fast_elements_); + Handle current_storage(storage_.ToHandle()); + HandleCell slow_storage( + Factory::NewNumberDictionary(current_storage->length())); + uint32_t current_length = static_cast(current_storage->length()); + for (uint32_t i = 0; i < current_length; i++) { + HandleScope loop_scope; + Handle element(current_storage->get(i)); + if (!element->IsTheHole()) { + slow_storage = + Factory::DictionaryAtNumberPut(slow_storage.ToHandle(), i, element); + } + } + storage_ = slow_storage.cast(); + fast_elements_ = false; + } + + HandleCell storage_; + // Index after last seen index. Always less than or equal to + // JSObject::kMaxElementCount. uint32_t index_offset_; - const bool fast_elements_; + bool fast_elements_; }; +static uint32_t EstimateElementCount(Handle array) { + uint32_t length = static_cast(array->length()->Number()); + int element_count = 0; + switch (array->GetElementsKind()) { + case JSObject::FAST_ELEMENTS: { + // Fast elements can't have lengths that are not representable by + // a 32-bit signed integer. + ASSERT(static_cast(FixedArray::kMaxLength) >= 0); + int fast_length = static_cast(length); + Handle elements(FixedArray::cast(array->elements())); + for (int i = 0; i < fast_length; i++) { + if (!elements->get(i)->IsTheHole()) element_count++; + } + break; + } + case JSObject::DICTIONARY_ELEMENTS: { + Handle dictionary( + NumberDictionary::cast(array->elements())); + int capacity = dictionary->Capacity(); + for (int i = 0; i < capacity; i++) { + Handle key(dictionary->KeyAt(i)); + if (dictionary->IsKey(*key)) { + element_count++; + } + } + break; + } + default: + // External arrays are always dense. + return length; + } + // As an estimate, we assume that the prototype doesn't contain any + // inherited elements. + return element_count; +} + + + template -static uint32_t IterateExternalArrayElements(Handle receiver, - bool elements_are_ints, - bool elements_are_guaranteed_smis, - uint32_t range, - ArrayConcatVisitor* visitor) { +static void IterateExternalArrayElements(Handle receiver, + bool elements_are_ints, + bool elements_are_guaranteed_smis, + ArrayConcatVisitor* visitor) { Handle array( ExternalArrayClass::cast(receiver->elements())); - uint32_t len = Min(static_cast(array->length()), range); + uint32_t len = static_cast(array->length()); - if (visitor != NULL) { - if (elements_are_ints) { - if (elements_are_guaranteed_smis) { - for (uint32_t j = 0; j < len; j++) { - Handle e(Smi::FromInt(static_cast(array->get(j)))); + ASSERT(visitor != NULL); + if (elements_are_ints) { + if (elements_are_guaranteed_smis) { + for (uint32_t j = 0; j < len; j++) { + HandleScope loop_scope; + Handle e(Smi::FromInt(static_cast(array->get(j)))); + visitor->visit(j, e); + } + } else { + for (uint32_t j = 0; j < len; j++) { + HandleScope loop_scope; + int64_t val = static_cast(array->get(j)); + if (Smi::IsValid(static_cast(val))) { + Handle e(Smi::FromInt(static_cast(val))); + visitor->visit(j, e); + } else { + Handle e = + Factory::NewNumber(static_cast(val)); visitor->visit(j, e); } - } else { - for (uint32_t j = 0; j < len; j++) { - int64_t val = static_cast(array->get(j)); - if (Smi::IsValid(static_cast(val))) { - Handle e(Smi::FromInt(static_cast(val))); - visitor->visit(j, e); - } else { - Handle e = - Factory::NewNumber(static_cast(val)); - visitor->visit(j, e); + } + } + } else { + for (uint32_t j = 0; j < len; j++) { + HandleScope loop_scope; + Handle e = Factory::NewNumber(array->get(j)); + visitor->visit(j, e); + } + } +} + + +// Used for sorting indices in a List. +static int compareUInt32(const uint32_t* ap, const uint32_t* bp) { + uint32_t a = *ap; + uint32_t b = *bp; + return (a == b) ? 0 : (a < b) ? -1 : 1; +} + + +static void CollectElementIndices(Handle object, + uint32_t range, + List* indices) { + JSObject::ElementsKind kind = object->GetElementsKind(); + switch (kind) { + case JSObject::FAST_ELEMENTS: { + Handle elements(FixedArray::cast(object->elements())); + uint32_t length = static_cast(elements->length()); + if (range < length) length = range; + for (uint32_t i = 0; i < length; i++) { + if (!elements->get(i)->IsTheHole()) { + indices->Add(i); + } + } + break; + } + case JSObject::DICTIONARY_ELEMENTS: { + Handle dict(NumberDictionary::cast(object->elements())); + uint32_t capacity = dict->Capacity(); + for (uint32_t j = 0; j < capacity; j++) { + HandleScope loop_scope; + Handle k(dict->KeyAt(j)); + if (dict->IsKey(*k)) { + ASSERT(k->IsNumber()); + uint32_t index = static_cast(k->Number()); + if (index < range) { + indices->Add(index); } } } - } else { - for (uint32_t j = 0; j < len; j++) { - Handle e = Factory::NewNumber(array->get(j)); - visitor->visit(j, e); + break; + } + default: { + int dense_elements_length; + switch (kind) { + case JSObject::PIXEL_ELEMENTS: { + dense_elements_length = + PixelArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_BYTE_ELEMENTS: { + dense_elements_length = + ExternalByteArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS: { + dense_elements_length = + ExternalUnsignedByteArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_SHORT_ELEMENTS: { + dense_elements_length = + ExternalShortArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS: { + dense_elements_length = + ExternalUnsignedShortArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_INT_ELEMENTS: { + dense_elements_length = + ExternalIntArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS: { + dense_elements_length = + ExternalUnsignedIntArray::cast(object->elements())->length(); + break; + } + case JSObject::EXTERNAL_FLOAT_ELEMENTS: { + dense_elements_length = + ExternalFloatArray::cast(object->elements())->length(); + break; + } + default: + UNREACHABLE(); + break; + } + uint32_t length = static_cast(dense_elements_length); + if (range <= length) { + length = range; + // We will add all indices, so we might as well clear it first + // and avoid duplicates. + indices->Clear(); } + for (uint32_t i = 0; i < length; i++) { + indices->Add(i); + } + if (length == range) return; // All indices accounted for already. + break; } } - return len; + Handle prototype(object->GetPrototype()); + if (prototype->IsJSObject()) { + // The prototype will usually have no inherited element indices, + // but we have to check. + CollectElementIndices(Handle::cast(prototype), range, indices); + } } + /** - * A helper function that visits elements of a JSObject. Only elements - * whose index between 0 and range (exclusive) are visited. - * - * If the third parameter, visitor, is not NULL, the visitor is called - * with parameters, 'visitor_index_offset + element index' and the element. + * A helper function that visits elements of a JSArray in numerical + * order. * - * It returns the number of visisted elements. + * The visitor argument called for each existing element in the array + * with the element index and the element's value. + * Afterwards it increments the base-index of the visitor by the array + * length. */ -static uint32_t IterateElements(Handle receiver, - uint32_t range, - ArrayConcatVisitor* visitor) { - uint32_t num_of_elements = 0; - +static void IterateElements(Handle receiver, + ArrayConcatVisitor* visitor) { + uint32_t length = static_cast(receiver->length()->Number()); switch (receiver->GetElementsKind()) { case JSObject::FAST_ELEMENTS: { + // Run through the elements FixedArray and use HasElement and GetElement + // to check the prototype for missing elements. Handle elements(FixedArray::cast(receiver->elements())); - uint32_t len = elements->length(); - if (range < len) { - len = range; - } - - for (uint32_t j = 0; j < len; j++) { - Handle e(elements->get(j)); - if (!e->IsTheHole()) { - num_of_elements++; - if (visitor) { - visitor->visit(j, e); - } + int fast_length = static_cast(length); + ASSERT(fast_length <= elements->length()); + for (int j = 0; j < fast_length; j++) { + HandleScope loop_scope; + Handle element_value(elements->get(j)); + if (!element_value->IsTheHole()) { + visitor->visit(j, element_value); + } else if (receiver->HasElement(j)) { + // Call GetElement on receiver, not its prototype, or getters won't + // have the correct receiver. + element_value = GetElement(receiver, j); + visitor->visit(j, element_value); } } break; } + case JSObject::DICTIONARY_ELEMENTS: { + Handle dict(receiver->element_dictionary()); + List 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(receiver, length, &indices); + indices.Sort(&compareUInt32); + int j = 0; + int n = indices.length(); + while (j < n) { + HandleScope loop_scope; + uint32_t index = indices[j]; + Handle element = GetElement(receiver, index); + visitor->visit(index, element); + // Skip to next different index (i.e., omit duplicates). + do { + j++; + } while (j < n && indices[j] == index); + } + break; + } case JSObject::PIXEL_ELEMENTS: { Handle pixels(PixelArray::cast(receiver->elements())); - uint32_t len = pixels->length(); - if (range < len) { - len = range; - } - - for (uint32_t j = 0; j < len; j++) { - num_of_elements++; - if (visitor != NULL) { - Handle e(Smi::FromInt(pixels->get(j))); - visitor->visit(j, e); - } + for (uint32_t j = 0; j < length; j++) { + Handle e(Smi::FromInt(pixels->get(j))); + visitor->visit(j, e); } break; } case JSObject::EXTERNAL_BYTE_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, true, range, visitor); + IterateExternalArrayElements( + receiver, true, true, visitor); break; } case JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, true, range, visitor); + IterateExternalArrayElements( + receiver, true, true, visitor); break; } case JSObject::EXTERNAL_SHORT_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, true, range, visitor); + IterateExternalArrayElements( + receiver, true, true, visitor); break; } case JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, true, range, visitor); + IterateExternalArrayElements( + receiver, true, true, visitor); break; } case JSObject::EXTERNAL_INT_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, false, range, visitor); + IterateExternalArrayElements( + receiver, true, false, visitor); break; } case JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, true, false, range, visitor); + IterateExternalArrayElements( + receiver, true, false, visitor); break; } case JSObject::EXTERNAL_FLOAT_ELEMENTS: { - num_of_elements = - IterateExternalArrayElements( - receiver, false, false, range, visitor); - break; - } - case JSObject::DICTIONARY_ELEMENTS: { - Handle dict(receiver->element_dictionary()); - uint32_t capacity = dict->Capacity(); - for (uint32_t j = 0; j < capacity; j++) { - Handle k(dict->KeyAt(j)); - if (dict->IsKey(*k)) { - ASSERT(k->IsNumber()); - uint32_t index = static_cast(k->Number()); - if (index < range) { - num_of_elements++; - if (visitor) { - visitor->visit(index, Handle(dict->ValueAt(j))); - } - } - } - } + IterateExternalArrayElements( + receiver, false, false, visitor); break; } default: UNREACHABLE(); break; } - - return num_of_elements; -} - - -/** - * A helper function that visits elements of an Array object, and elements - * on its prototypes. - * - * Elements on prototypes are visited first, and only elements whose indices - * less than Array length are visited. - * - * If a ArrayConcatVisitor object is given, the visitor is called with - * parameters, element's index + visitor_index_offset and the element. - * - * The returned number of elements is an upper bound on the actual number - * of elements added. If the same element occurs in more than one object - * in the array's prototype chain, it will be counted more than once, but - * will only occur once in the result. - */ -static uint32_t IterateArrayAndPrototypeElements(Handle array, - ArrayConcatVisitor* visitor) { - uint32_t range = static_cast(array->length()->Number()); - Handle obj = array; - - static const int kEstimatedPrototypes = 3; - List< Handle > objects(kEstimatedPrototypes); - - // Visit prototype first. If an element on the prototype is shadowed by - // the inheritor using the same index, the ArrayConcatVisitor visits - // the prototype element before the shadowing element. - // The visitor can simply overwrite the old value by new value using - // the same index. This follows Array::concat semantics. - while (!obj->IsNull()) { - objects.Add(Handle::cast(obj)); - obj = Handle(obj->GetPrototype()); - } - - uint32_t nof_elements = 0; - for (int i = objects.length() - 1; i >= 0; i--) { - Handle obj = objects[i]; - uint32_t encountered_elements = - IterateElements(Handle::cast(obj), range, visitor); - - if (encountered_elements > JSObject::kMaxElementCount - nof_elements) { - nof_elements = JSObject::kMaxElementCount; - } else { - nof_elements += encountered_elements; - } - } - - return nof_elements; -} - - -/** - * A helper function of Runtime_ArrayConcat. - * - * The first argument is an Array of arrays and objects. It is the - * same as the arguments array of Array::concat JS function. - * - * If an argument is an Array object, the function visits array - * elements. If an argument is not an Array object, the function - * visits the object as if it is an one-element array. - * - * If the result array index overflows 32-bit unsigned integer, the rounded - * non-negative number is used as new length. For example, if one - * array length is 2^32 - 1, second array length is 1, the - * concatenated array length is 0. - * TODO(lrn) Change length behavior to ECMAScript 5 specification (length - * is one more than the last array index to get a value assigned). - */ -static uint32_t IterateArguments(Handle arguments, - ArrayConcatVisitor* visitor) { - uint32_t visited_elements = 0; - uint32_t num_of_args = static_cast(arguments->length()->Number()); - - for (uint32_t i = 0; i < num_of_args; i++) { - Object *element; - MaybeObject* maybe_element = arguments->GetElement(i); - // This if() is not expected to fail, but we have the check in the - // interest of hardening the runtime calls. - if (maybe_element->ToObject(&element)) { - Handle obj(element); - if (obj->IsJSArray()) { - Handle array = Handle::cast(obj); - uint32_t len = static_cast(array->length()->Number()); - uint32_t nof_elements = - IterateArrayAndPrototypeElements(array, visitor); - // Total elements of array and its prototype chain can be more than - // the array length, but ArrayConcat can only concatenate at most - // the array length number of elements. We use the length as an estimate - // for the actual number of elements added. - uint32_t added_elements = (nof_elements > len) ? len : nof_elements; - if (JSArray::kMaxElementCount - visited_elements < added_elements) { - visited_elements = JSArray::kMaxElementCount; - } else { - visited_elements += added_elements; - } - if (visitor) visitor->increase_index_offset(len); - } else { - if (visitor) { - visitor->visit(0, obj); - visitor->increase_index_offset(1); - } - if (visited_elements < JSArray::kMaxElementCount) { - visited_elements++; - } - } - } - } - return visited_elements; + visitor->increase_index_offset(length); } /** * Array::concat implementation. * See ECMAScript 262, 15.4.4.4. - * TODO(lrn): Fix non-compliance for very large concatenations and update to + * TODO(581): Fix non-compliance for very large concatenations and update to * following the ECMAScript 5 specification. */ static MaybeObject* Runtime_ArrayConcat(Arguments args) { ASSERT(args.length() == 1); HandleScope handle_scope; - CONVERT_CHECKED(JSArray, arg_arrays, args[0]); - Handle arguments(arg_arrays); - - // Pass 1: estimate the number of elements of the result - // (it could be more than real numbers if prototype has elements). - uint32_t result_length = 0; - uint32_t num_of_args = static_cast(arguments->length()->Number()); - - { AssertNoAllocation nogc; - for (uint32_t i = 0; i < num_of_args; i++) { - Object* obj; - MaybeObject* maybe_object = arguments->GetElement(i); - // This if() is not expected to fail, but we have the check in the - // interest of hardening the runtime calls. - if (maybe_object->ToObject(&obj)) { - uint32_t length_estimate; - if (obj->IsJSArray()) { - length_estimate = - static_cast(JSArray::cast(obj)->length()->Number()); - } else { - length_estimate = 1; - } - if (JSObject::kMaxElementCount - result_length < length_estimate) { - result_length = JSObject::kMaxElementCount; - break; - } - result_length += length_estimate; + CONVERT_ARG_CHECKED(JSArray, arguments, 0); + int argument_count = static_cast(arguments->length()->Number()); + RUNTIME_ASSERT(arguments->HasFastElements()); + Handle elements(FixedArray::cast(arguments->elements())); + + // Pass 1: estimate the length and number of elements of the result. + // The actual length can be larger if any of the arguments have getters + // that mutate other arguments (but will otherwise be precise). + // The number of elements is precise if there are no inherited elements. + + uint32_t estimate_result_length = 0; + uint32_t estimate_nof_elements = 0; + { + for (int i = 0; i < argument_count; i++) { + HandleScope loop_scope; + Handle obj(elements->get(i)); + uint32_t length_estimate; + uint32_t element_estimate; + if (obj->IsJSArray()) { + Handle array(Handle::cast(obj)); + length_estimate = + static_cast(array->length()->Number()); + element_estimate = + EstimateElementCount(array); + } else { + 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; + } + if (JSObject::kMaxElementCount - estimate_nof_elements < + element_estimate) { + estimate_nof_elements = JSObject::kMaxElementCount; + } else { + estimate_nof_elements += element_estimate; } } } - // Allocate an empty array, will set map, length, and content later. - Handle result = Factory::NewJSArray(0); - - uint32_t estimate_nof_elements = IterateArguments(arguments, NULL); // If estimated number of elements is more than half of length, a // fixed array (fast case) is more time and space-efficient than a // dictionary. - bool fast_case = (estimate_nof_elements * 2) >= result_length; + bool fast_case = (estimate_nof_elements * 2) >= estimate_result_length; - Handle map; Handle storage; if (fast_case) { // The backing storage array must have non-existing elements to // preserve holes across concat operations. - map = Factory::GetFastElementsMap(Handle(result->map())); - storage = Factory::NewFixedArrayWithHoles(result_length); + storage = Factory::NewFixedArrayWithHoles(estimate_result_length); } else { - map = Factory::GetSlowElementsMap(Handle(result->map())); // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate uint32_t at_least_space_for = estimate_nof_elements + (estimate_nof_elements >> 2); @@ -8406,21 +8477,20 @@ static MaybeObject* Runtime_ArrayConcat(Arguments args) { Factory::NewNumberDictionary(at_least_space_for)); } - Handle len = Factory::NewNumber(static_cast(result_length)); - - ArrayConcatVisitor visitor(storage, result_length, fast_case); - - IterateArguments(arguments, &visitor); + ArrayConcatVisitor visitor(storage, fast_case); - // Please note: - // - the storage might have been changed in the visitor; - // - the map and the storage must be set together to avoid breaking - // the invariant that the map describes the array's elements. - result->set_map(*map); - result->set_length(*len); - result->set_elements(*visitor.storage()); + for (int i = 0; i < argument_count; i++) { + Handle obj(elements->get(i)); + if (obj->IsJSArray()) { + Handle array = Handle::cast(obj); + IterateElements(array, &visitor); + } else { + visitor.visit(0, obj); + visitor.increase_index_offset(1); + } + } - return *result; + return *visitor.ToArray(); } diff --git a/test/mjsunit/array-concat.js b/test/mjsunit/array-concat.js index db89f4d..97bd85a 100644 --- a/test/mjsunit/array-concat.js +++ b/test/mjsunit/array-concat.js @@ -101,7 +101,6 @@ while (pos = poses.shift()) { assertEquals("undefined", typeof(c[-1])); assertEquals("undefined", typeof(c[0xffffffff])); assertEquals(c.length, a.length + 1); - } poses = [140, 4000000000]; @@ -193,3 +192,46 @@ for (var i = 0; i < holey.length; i++) { assertTrue(i in holey); } } + +// Polluted prototype from prior tests. +delete Array.prototype[123]; + +// Check that concat reads getters in the correct order. +var arr1 = [,2]; +var arr2 = [1,3]; +var r1 = [].concat(arr1, arr2); // [,2,1,3] +assertEquals([,2,1,3], r1); + +// Make first array change length of second array. +Object.defineProperty(arr1, 0, {get: function() { + arr2.push("X"); + return undefined; + }, configurable: true}) +var r2 = [].concat(arr1, arr2); // [undefined,2,1,3,"X"] +assertEquals([undefined,2,1,3,"X"], r2); + +// Make first array change length of second array massively. +arr2.length = 2; +Object.defineProperty(arr1, 0, {get: function() { + arr2[500000] = "X"; + return undefined; + }, configurable: true}) +var r3 = [].concat(arr1, arr2); // [undefined,2,1,3,"X"] +var expected = [undefined,2,1,3]; +expected[500000 + 2] = "X"; + +assertEquals(expected, r3); + +var arr3 = []; +var trace = []; +var expectedTrace = [] +function mkGetter(i) { return function() { trace.push(i); }; } +arr3.length = 10000; +for (var i = 0; i < 100; i++) { + Object.defineProperty(arr3, i * i, {get: mkGetter(i)}); + expectedTrace[i] = i; + expectedTrace[100 + i] = i; +} +var r4 = [0].concat(arr3, arr3); +assertEquals(1 + arr3.length * 2, r4.length); +assertEquals(expectedTrace, trace); -- 2.7.4