| // Copyright 2014 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/arguments.h" |
| #include "src/runtime/runtime-utils.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| RUNTIME_FUNCTION(Runtime_FinishArrayPrototypeSetup) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 1); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0); |
| Object* length = prototype->length(); |
| RUNTIME_ASSERT(length->IsSmi() && Smi::cast(length)->value() == 0); |
| RUNTIME_ASSERT(prototype->HasFastSmiOrObjectElements()); |
| // This is necessary to enable fast checks for absence of elements |
| // on Array.prototype and below. |
| prototype->set_elements(isolate->heap()->empty_fixed_array()); |
| return Smi::FromInt(0); |
| } |
| |
| |
| static void InstallBuiltin(Isolate* isolate, Handle<JSObject> holder, |
| const char* name, Builtins::Name builtin_name) { |
| Handle<String> key = isolate->factory()->InternalizeUtf8String(name); |
| Handle<Code> code(isolate->builtins()->builtin(builtin_name)); |
| Handle<JSFunction> optimized = |
| isolate->factory()->NewFunctionWithoutPrototype(key, code); |
| optimized->shared()->DontAdaptArguments(); |
| JSObject::AddProperty(holder, key, optimized, NONE); |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_SpecialArrayFunctions) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 0); |
| Handle<JSObject> holder = |
| isolate->factory()->NewJSObject(isolate->object_function()); |
| |
| InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop); |
| InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush); |
| InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift); |
| InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift); |
| InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice); |
| InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice); |
| InstallBuiltin(isolate, holder, "concat", Builtins::kArrayConcat); |
| |
| return *holder; |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_TransitionElementsKind) { |
| HandleScope scope(isolate); |
| RUNTIME_ASSERT(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0); |
| CONVERT_ARG_HANDLE_CHECKED(Map, map, 1); |
| JSObject::TransitionElementsKind(array, map->elements_kind()); |
| return *array; |
| } |
| |
| |
| // Push an object unto an array of objects if it is not already in the |
| // array. Returns true if the element was pushed on the stack and |
| // false otherwise. |
| RUNTIME_FUNCTION(Runtime_PushIfAbsent) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0); |
| CONVERT_ARG_HANDLE_CHECKED(JSReceiver, element, 1); |
| RUNTIME_ASSERT(array->HasFastSmiOrObjectElements()); |
| int length = Smi::cast(array->length())->value(); |
| FixedArray* elements = FixedArray::cast(array->elements()); |
| for (int i = 0; i < length; i++) { |
| if (elements->get(i) == *element) return isolate->heap()->false_value(); |
| } |
| |
| // Strict not needed. Used for cycle detection in Array join implementation. |
| RETURN_FAILURE_ON_EXCEPTION( |
| isolate, JSObject::SetFastElement(array, length, element, SLOPPY, true)); |
| return isolate->heap()->true_value(); |
| } |
| |
| |
| /** |
| * A simple visitor visits every element of Array's. |
| * The backend storage can be a fixed array for fast elements case, |
| * or a dictionary for sparse array. Since Dictionary is a subtype |
| * of FixedArray, the class can be used by both fast and slow cases. |
| * The second parameter of the constructor, fast_elements, specifies |
| * whether the storage is a FixedArray or Dictionary. |
| * |
| * An index limit is used to deal with the situation that a result array |
| * length overflows 32-bit non-negative integer. |
| */ |
| class ArrayConcatVisitor { |
| public: |
| ArrayConcatVisitor(Isolate* isolate, Handle<FixedArray> storage, |
| bool fast_elements) |
| : isolate_(isolate), |
| storage_(Handle<FixedArray>::cast( |
| isolate->global_handles()->Create(*storage))), |
| index_offset_(0u), |
| fast_elements_(fast_elements), |
| exceeds_array_limit_(false) {} |
| |
| ~ArrayConcatVisitor() { clear_storage(); } |
| |
| void visit(uint32_t i, Handle<Object> elm) { |
| if (i > JSObject::kMaxElementCount - index_offset_) { |
| exceeds_array_limit_ = true; |
| return; |
| } |
| uint32_t index = index_offset_ + i; |
| |
| if (fast_elements_) { |
| if (index < static_cast<uint32_t>(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(); |
| // Fall-through to dictionary mode. |
| } |
| DCHECK(!fast_elements_); |
| Handle<SeededNumberDictionary> dict( |
| SeededNumberDictionary::cast(*storage_)); |
| Handle<SeededNumberDictionary> result = |
| SeededNumberDictionary::AtNumberPut(dict, index, elm); |
| if (!result.is_identical_to(dict)) { |
| // Dictionary needed to grow. |
| clear_storage(); |
| set_storage(*result); |
| } |
| } |
| |
| void increase_index_offset(uint32_t delta) { |
| if (JSObject::kMaxElementCount - index_offset_ < delta) { |
| index_offset_ = JSObject::kMaxElementCount; |
| } else { |
| index_offset_ += delta; |
| } |
| // If the initial length estimate was off (see special case in visit()), |
| // but the array blowing the limit didn't contain elements beyond the |
| // provided-for index range, go to dictionary mode now. |
| if (fast_elements_ && |
| index_offset_ > |
| static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) { |
| SetDictionaryMode(); |
| } |
| } |
| |
| bool exceeds_array_limit() { return exceeds_array_limit_; } |
| |
| Handle<JSArray> ToArray() { |
| Handle<JSArray> array = isolate_->factory()->NewJSArray(0); |
| Handle<Object> length = |
| isolate_->factory()->NewNumber(static_cast<double>(index_offset_)); |
| Handle<Map> map = JSObject::GetElementsTransitionMap( |
| array, fast_elements_ ? FAST_HOLEY_ELEMENTS : DICTIONARY_ELEMENTS); |
| array->set_map(*map); |
| array->set_length(*length); |
| array->set_elements(*storage_); |
| return array; |
| } |
| |
| private: |
| // Convert storage to dictionary mode. |
| void SetDictionaryMode() { |
| DCHECK(fast_elements_); |
| Handle<FixedArray> current_storage(*storage_); |
| Handle<SeededNumberDictionary> slow_storage( |
| SeededNumberDictionary::New(isolate_, current_storage->length())); |
| uint32_t current_length = static_cast<uint32_t>(current_storage->length()); |
| for (uint32_t i = 0; i < current_length; i++) { |
| HandleScope loop_scope(isolate_); |
| Handle<Object> element(current_storage->get(i), isolate_); |
| if (!element->IsTheHole()) { |
| Handle<SeededNumberDictionary> new_storage = |
| SeededNumberDictionary::AtNumberPut(slow_storage, i, element); |
| if (!new_storage.is_identical_to(slow_storage)) { |
| slow_storage = loop_scope.CloseAndEscape(new_storage); |
| } |
| } |
| } |
| clear_storage(); |
| set_storage(*slow_storage); |
| fast_elements_ = false; |
| } |
| |
| inline void clear_storage() { |
| GlobalHandles::Destroy(Handle<Object>::cast(storage_).location()); |
| } |
| |
| inline void set_storage(FixedArray* storage) { |
| storage_ = |
| Handle<FixedArray>::cast(isolate_->global_handles()->Create(storage)); |
| } |
| |
| Isolate* isolate_; |
| Handle<FixedArray> storage_; // Always a global handle. |
| // Index after last seen index. Always less than or equal to |
| // JSObject::kMaxElementCount. |
| uint32_t index_offset_; |
| bool fast_elements_ : 1; |
| bool exceeds_array_limit_ : 1; |
| }; |
| |
| |
| static uint32_t EstimateElementCount(Handle<JSArray> array) { |
| uint32_t length = static_cast<uint32_t>(array->length()->Number()); |
| int element_count = 0; |
| switch (array->GetElementsKind()) { |
| case FAST_SMI_ELEMENTS: |
| case FAST_HOLEY_SMI_ELEMENTS: |
| case FAST_ELEMENTS: |
| case FAST_HOLEY_ELEMENTS: { |
| // Fast elements can't have lengths that are not representable by |
| // a 32-bit signed integer. |
| DCHECK(static_cast<int32_t>(FixedArray::kMaxLength) >= 0); |
| int fast_length = static_cast<int>(length); |
| Handle<FixedArray> elements(FixedArray::cast(array->elements())); |
| for (int i = 0; i < fast_length; i++) { |
| if (!elements->get(i)->IsTheHole()) element_count++; |
| } |
| break; |
| } |
| case FAST_DOUBLE_ELEMENTS: |
| case FAST_HOLEY_DOUBLE_ELEMENTS: { |
| // Fast elements can't have lengths that are not representable by |
| // a 32-bit signed integer. |
| DCHECK(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0); |
| int fast_length = static_cast<int>(length); |
| if (array->elements()->IsFixedArray()) { |
| DCHECK(FixedArray::cast(array->elements())->length() == 0); |
| break; |
| } |
| Handle<FixedDoubleArray> elements( |
| FixedDoubleArray::cast(array->elements())); |
| for (int i = 0; i < fast_length; i++) { |
| if (!elements->is_the_hole(i)) element_count++; |
| } |
| break; |
| } |
| case DICTIONARY_ELEMENTS: { |
| Handle<SeededNumberDictionary> dictionary( |
| SeededNumberDictionary::cast(array->elements())); |
| int capacity = dictionary->Capacity(); |
| for (int i = 0; i < capacity; i++) { |
| Handle<Object> key(dictionary->KeyAt(i), array->GetIsolate()); |
| if (dictionary->IsKey(*key)) { |
| element_count++; |
| } |
| } |
| break; |
| } |
| case SLOPPY_ARGUMENTS_ELEMENTS: |
| #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \ |
| case EXTERNAL_##TYPE##_ELEMENTS: \ |
| case TYPE##_ELEMENTS: |
| |
| TYPED_ARRAYS(TYPED_ARRAY_CASE) |
| #undef TYPED_ARRAY_CASE |
| // 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 <class ExternalArrayClass, class ElementType> |
| static void IterateExternalArrayElements(Isolate* isolate, |
| Handle<JSObject> receiver, |
| bool elements_are_ints, |
| bool elements_are_guaranteed_smis, |
| ArrayConcatVisitor* visitor) { |
| Handle<ExternalArrayClass> array( |
| ExternalArrayClass::cast(receiver->elements())); |
| uint32_t len = static_cast<uint32_t>(array->length()); |
| |
| DCHECK(visitor != NULL); |
| if (elements_are_ints) { |
| if (elements_are_guaranteed_smis) { |
| for (uint32_t j = 0; j < len; j++) { |
| HandleScope loop_scope(isolate); |
| Handle<Smi> e(Smi::FromInt(static_cast<int>(array->get_scalar(j))), |
| isolate); |
| visitor->visit(j, e); |
| } |
| } else { |
| for (uint32_t j = 0; j < len; j++) { |
| HandleScope loop_scope(isolate); |
| int64_t val = static_cast<int64_t>(array->get_scalar(j)); |
| if (Smi::IsValid(static_cast<intptr_t>(val))) { |
| Handle<Smi> e(Smi::FromInt(static_cast<int>(val)), isolate); |
| visitor->visit(j, e); |
| } else { |
| Handle<Object> e = |
| isolate->factory()->NewNumber(static_cast<ElementType>(val)); |
| visitor->visit(j, e); |
| } |
| } |
| } |
| } else { |
| for (uint32_t j = 0; j < len; j++) { |
| HandleScope loop_scope(isolate); |
| Handle<Object> e = isolate->factory()->NewNumber(array->get_scalar(j)); |
| visitor->visit(j, e); |
| } |
| } |
| } |
| |
| |
| // Used for sorting indices in a List<uint32_t>. |
| 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<JSObject> object, uint32_t range, |
| List<uint32_t>* indices) { |
| Isolate* isolate = object->GetIsolate(); |
| ElementsKind kind = object->GetElementsKind(); |
| switch (kind) { |
| case FAST_SMI_ELEMENTS: |
| case FAST_ELEMENTS: |
| case FAST_HOLEY_SMI_ELEMENTS: |
| case FAST_HOLEY_ELEMENTS: { |
| Handle<FixedArray> elements(FixedArray::cast(object->elements())); |
| uint32_t length = static_cast<uint32_t>(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 FAST_HOLEY_DOUBLE_ELEMENTS: |
| case FAST_DOUBLE_ELEMENTS: { |
| if (object->elements()->IsFixedArray()) { |
| DCHECK(object->elements()->length() == 0); |
| break; |
| } |
| Handle<FixedDoubleArray> elements( |
| FixedDoubleArray::cast(object->elements())); |
| uint32_t length = static_cast<uint32_t>(elements->length()); |
| if (range < length) length = range; |
| for (uint32_t i = 0; i < length; i++) { |
| if (!elements->is_the_hole(i)) { |
| indices->Add(i); |
| } |
| } |
| break; |
| } |
| case DICTIONARY_ELEMENTS: { |
| Handle<SeededNumberDictionary> dict( |
| SeededNumberDictionary::cast(object->elements())); |
| uint32_t capacity = dict->Capacity(); |
| for (uint32_t j = 0; j < capacity; j++) { |
| HandleScope loop_scope(isolate); |
| Handle<Object> k(dict->KeyAt(j), isolate); |
| if (dict->IsKey(*k)) { |
| DCHECK(k->IsNumber()); |
| uint32_t index = static_cast<uint32_t>(k->Number()); |
| if (index < range) { |
| indices->Add(index); |
| } |
| } |
| } |
| break; |
| } |
| #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \ |
| case TYPE##_ELEMENTS: \ |
| case EXTERNAL_##TYPE##_ELEMENTS: |
| |
| TYPED_ARRAYS(TYPED_ARRAY_CASE) |
| #undef TYPED_ARRAY_CASE |
| { |
| uint32_t length = static_cast<uint32_t>( |
| FixedArrayBase::cast(object->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; |
| } |
| case SLOPPY_ARGUMENTS_ELEMENTS: { |
| MaybeHandle<Object> length_obj = |
| Object::GetProperty(object, isolate->factory()->length_string()); |
| double length_num = length_obj.ToHandleChecked()->Number(); |
| uint32_t length = static_cast<uint32_t>(DoubleToInt32(length_num)); |
| ElementsAccessor* accessor = object->GetElementsAccessor(); |
| for (uint32_t i = 0; i < length; i++) { |
| if (accessor->HasElement(object, object, i)) { |
| indices->Add(i); |
| } |
| } |
| break; |
| } |
| } |
| |
| PrototypeIterator iter(isolate, object); |
| if (!iter.IsAtEnd()) { |
| // The prototype will usually have no inherited element indices, |
| // but we have to check. |
| CollectElementIndices( |
| Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter)), range, |
| indices); |
| } |
| } |
| |
| |
| /** |
| * A helper function that visits elements of a JSArray in numerical |
| * order. |
| * |
| * 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. |
| * Returns false if any access threw an exception, otherwise true. |
| */ |
| static bool IterateElements(Isolate* isolate, Handle<JSArray> receiver, |
| ArrayConcatVisitor* visitor) { |
| uint32_t length = static_cast<uint32_t>(receiver->length()->Number()); |
| switch (receiver->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(receiver->elements())); |
| int fast_length = static_cast<int>(length); |
| DCHECK(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()) { |
| visitor->visit(j, element_value); |
| } else { |
| Maybe<bool> maybe = JSReceiver::HasElement(receiver, j); |
| if (!maybe.has_value) return false; |
| if (maybe.value) { |
| // Call GetElement on receiver, not its prototype, or getters won't |
| // have the correct receiver. |
| ASSIGN_RETURN_ON_EXCEPTION_VALUE( |
| isolate, element_value, |
| Object::GetElement(isolate, receiver, j), false); |
| visitor->visit(j, element_value); |
| } |
| } |
| } |
| break; |
| } |
| case FAST_HOLEY_DOUBLE_ELEMENTS: |
| case FAST_DOUBLE_ELEMENTS: { |
| // Empty array is FixedArray but not FixedDoubleArray. |
| if (length == 0) break; |
| // Run through the elements FixedArray and use HasElement and GetElement |
| // to check the prototype for missing elements. |
| if (receiver->elements()->IsFixedArray()) { |
| DCHECK(receiver->elements()->length() == 0); |
| break; |
| } |
| Handle<FixedDoubleArray> elements( |
| FixedDoubleArray::cast(receiver->elements())); |
| int fast_length = static_cast<int>(length); |
| DCHECK(fast_length <= elements->length()); |
| for (int j = 0; j < fast_length; j++) { |
| HandleScope loop_scope(isolate); |
| if (!elements->is_the_hole(j)) { |
| double double_value = elements->get_scalar(j); |
| Handle<Object> element_value = |
| isolate->factory()->NewNumber(double_value); |
| visitor->visit(j, element_value); |
| } else { |
| Maybe<bool> maybe = JSReceiver::HasElement(receiver, j); |
| if (!maybe.has_value) return false; |
| if (maybe.value) { |
| // Call GetElement on receiver, not its prototype, or getters won't |
| // have the correct receiver. |
| Handle<Object> element_value; |
| ASSIGN_RETURN_ON_EXCEPTION_VALUE( |
| isolate, element_value, |
| Object::GetElement(isolate, receiver, j), false); |
| visitor->visit(j, element_value); |
| } |
| } |
| } |
| break; |
| } |
| case DICTIONARY_ELEMENTS: { |
| Handle<SeededNumberDictionary> dict(receiver->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(receiver, length, &indices); |
| indices.Sort(&compareUInt32); |
| int j = 0; |
| int n = indices.length(); |
| while (j < n) { |
| HandleScope loop_scope(isolate); |
| uint32_t index = indices[j]; |
| Handle<Object> element; |
| ASSIGN_RETURN_ON_EXCEPTION_VALUE( |
| isolate, element, Object::GetElement(isolate, receiver, index), |
| false); |
| visitor->visit(index, element); |
| // Skip to next different index (i.e., omit duplicates). |
| do { |
| j++; |
| } while (j < n && indices[j] == index); |
| } |
| break; |
| } |
| case EXTERNAL_UINT8_CLAMPED_ELEMENTS: { |
| Handle<ExternalUint8ClampedArray> pixels( |
| ExternalUint8ClampedArray::cast(receiver->elements())); |
| for (uint32_t j = 0; j < length; j++) { |
| Handle<Smi> e(Smi::FromInt(pixels->get_scalar(j)), isolate); |
| visitor->visit(j, e); |
| } |
| break; |
| } |
| case EXTERNAL_INT8_ELEMENTS: { |
| IterateExternalArrayElements<ExternalInt8Array, int8_t>( |
| isolate, receiver, true, true, visitor); |
| break; |
| } |
| case EXTERNAL_UINT8_ELEMENTS: { |
| IterateExternalArrayElements<ExternalUint8Array, uint8_t>( |
| isolate, receiver, true, true, visitor); |
| break; |
| } |
| case EXTERNAL_INT16_ELEMENTS: { |
| IterateExternalArrayElements<ExternalInt16Array, int16_t>( |
| isolate, receiver, true, true, visitor); |
| break; |
| } |
| case EXTERNAL_UINT16_ELEMENTS: { |
| IterateExternalArrayElements<ExternalUint16Array, uint16_t>( |
| isolate, receiver, true, true, visitor); |
| break; |
| } |
| case EXTERNAL_INT32_ELEMENTS: { |
| IterateExternalArrayElements<ExternalInt32Array, int32_t>( |
| isolate, receiver, true, false, visitor); |
| break; |
| } |
| case EXTERNAL_UINT32_ELEMENTS: { |
| IterateExternalArrayElements<ExternalUint32Array, uint32_t>( |
| isolate, receiver, true, false, visitor); |
| break; |
| } |
| case EXTERNAL_FLOAT32_ELEMENTS: { |
| IterateExternalArrayElements<ExternalFloat32Array, float>( |
| isolate, receiver, false, false, visitor); |
| break; |
| } |
| case EXTERNAL_FLOAT64_ELEMENTS: { |
| IterateExternalArrayElements<ExternalFloat64Array, double>( |
| isolate, receiver, false, false, visitor); |
| break; |
| } |
| default: |
| UNREACHABLE(); |
| break; |
| } |
| visitor->increase_index_offset(length); |
| return true; |
| } |
| |
| |
| /** |
| * Array::concat implementation. |
| * See ECMAScript 262, 15.4.4.4. |
| * TODO(581): Fix non-compliance for very large concatenations and update to |
| * following the ECMAScript 5 specification. |
| */ |
| RUNTIME_FUNCTION(Runtime_ArrayConcat) { |
| HandleScope handle_scope(isolate); |
| DCHECK(args.length() == 1); |
| |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, arguments, 0); |
| int argument_count = static_cast<int>(arguments->length()->Number()); |
| RUNTIME_ASSERT(arguments->HasFastObjectElements()); |
| Handle<FixedArray> 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. |
| |
| ElementsKind kind = FAST_SMI_ELEMENTS; |
| |
| uint32_t estimate_result_length = 0; |
| uint32_t estimate_nof_elements = 0; |
| for (int i = 0; i < argument_count; i++) { |
| HandleScope loop_scope(isolate); |
| Handle<Object> obj(elements->get(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()); |
| if (IsMoreGeneralElementsKindTransition(kind, array_kind)) { |
| kind = array_kind; |
| } |
| } |
| element_estimate = EstimateElementCount(array); |
| } else { |
| if (obj->IsHeapObject()) { |
| if (obj->IsNumber()) { |
| if (IsMoreGeneralElementsKindTransition(kind, FAST_DOUBLE_ELEMENTS)) { |
| kind = FAST_DOUBLE_ELEMENTS; |
| } |
| } else if (IsMoreGeneralElementsKindTransition(kind, FAST_ELEMENTS)) { |
| kind = 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; |
| } |
| if (JSObject::kMaxElementCount - estimate_nof_elements < element_estimate) { |
| estimate_nof_elements = JSObject::kMaxElementCount; |
| } else { |
| estimate_nof_elements += element_estimate; |
| } |
| } |
| |
| // 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) >= estimate_result_length; |
| |
| if (fast_case && kind == FAST_DOUBLE_ELEMENTS) { |
| Handle<FixedArrayBase> storage = |
| isolate->factory()->NewFixedDoubleArray(estimate_result_length); |
| int j = 0; |
| bool failure = false; |
| if (estimate_result_length > 0) { |
| Handle<FixedDoubleArray> double_storage = |
| Handle<FixedDoubleArray>::cast(storage); |
| for (int i = 0; i < argument_count; i++) { |
| Handle<Object> obj(elements->get(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()) { |
| 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 |
| // prototype chain, and if so, allow creation of a holey |
| // result array. |
| // Same thing below (holey smi case). |
| failure = true; |
| break; |
| } |
| double double_value = elements->get_scalar(i); |
| double_storage->set(j, double_value); |
| j++; |
| } |
| break; |
| } |
| case FAST_HOLEY_SMI_ELEMENTS: |
| case FAST_SMI_ELEMENTS: { |
| FixedArray* elements(FixedArray::cast(array->elements())); |
| for (uint32_t i = 0; i < length; i++) { |
| Object* element = elements->get(i); |
| if (element->IsTheHole()) { |
| failure = true; |
| break; |
| } |
| int32_t int_value = Smi::cast(element)->value(); |
| double_storage->set(j, int_value); |
| j++; |
| } |
| break; |
| } |
| case FAST_HOLEY_ELEMENTS: |
| case FAST_ELEMENTS: |
| DCHECK_EQ(0, 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; |
| } |
| // In case of failure, fall through. |
| } |
| |
| Handle<FixedArray> 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); |
| } else { |
| // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate |
| uint32_t at_least_space_for = |
| estimate_nof_elements + (estimate_nof_elements >> 2); |
| storage = Handle<FixedArray>::cast( |
| SeededNumberDictionary::New(isolate, at_least_space_for)); |
| } |
| |
| ArrayConcatVisitor visitor(isolate, storage, fast_case); |
| |
| for (int i = 0; i < argument_count; i++) { |
| Handle<Object> obj(elements->get(i), isolate); |
| if (obj->IsJSArray()) { |
| Handle<JSArray> array = Handle<JSArray>::cast(obj); |
| if (!IterateElements(isolate, array, &visitor)) { |
| return isolate->heap()->exception(); |
| } |
| } else { |
| visitor.visit(0, obj); |
| visitor.increase_index_offset(1); |
| } |
| } |
| |
| if (visitor.exceeds_array_limit()) { |
| THROW_NEW_ERROR_RETURN_FAILURE( |
| isolate, |
| NewRangeError("invalid_array_length", HandleVector<Object>(NULL, 0))); |
| } |
| return *visitor.ToArray(); |
| } |
| |
| |
| // Moves all own elements of an object, that are below a limit, to positions |
| // starting at zero. All undefined values are placed after non-undefined values, |
| // and are followed by non-existing element. Does not change the length |
| // property. |
| // Returns the number of non-undefined elements collected. |
| // Returns -1 if hole removal is not supported by this method. |
| RUNTIME_FUNCTION(Runtime_RemoveArrayHoles) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0); |
| CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]); |
| return *JSObject::PrepareElementsForSort(object, limit); |
| } |
| |
| |
| // Move contents of argument 0 (an array) to argument 1 (an array) |
| RUNTIME_FUNCTION(Runtime_MoveArrayContents) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1); |
| JSObject::ValidateElements(from); |
| JSObject::ValidateElements(to); |
| |
| Handle<FixedArrayBase> new_elements(from->elements()); |
| ElementsKind from_kind = from->GetElementsKind(); |
| Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind); |
| JSObject::SetMapAndElements(to, new_map, new_elements); |
| to->set_length(from->length()); |
| |
| JSObject::ResetElements(from); |
| from->set_length(Smi::FromInt(0)); |
| |
| JSObject::ValidateElements(to); |
| return *to; |
| } |
| |
| |
| // How many elements does this object/array have? |
| RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 1); |
| CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0); |
| Handle<FixedArrayBase> elements(array->elements(), isolate); |
| SealHandleScope shs(isolate); |
| if (elements->IsDictionary()) { |
| int result = |
| Handle<SeededNumberDictionary>::cast(elements)->NumberOfElements(); |
| return Smi::FromInt(result); |
| } else { |
| DCHECK(array->length()->IsSmi()); |
| // For packed elements, we know the exact number of elements |
| int length = elements->length(); |
| ElementsKind kind = array->GetElementsKind(); |
| if (IsFastPackedElementsKind(kind)) { |
| return Smi::FromInt(length); |
| } |
| // For holey elements, take samples from the buffer checking for holes |
| // to generate the estimate. |
| const int kNumberOfHoleCheckSamples = 97; |
| int increment = (length < kNumberOfHoleCheckSamples) |
| ? 1 |
| : static_cast<int>(length / kNumberOfHoleCheckSamples); |
| ElementsAccessor* accessor = array->GetElementsAccessor(); |
| int holes = 0; |
| for (int i = 0; i < length; i += increment) { |
| if (!accessor->HasElement(array, array, i, elements)) { |
| ++holes; |
| } |
| } |
| int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) / |
| kNumberOfHoleCheckSamples * length); |
| return Smi::FromInt(estimate); |
| } |
| } |
| |
| |
| // Returns an array that tells you where in the [0, length) interval an array |
| // might have elements. Can either return an array of keys (positive integers |
| // or undefined) or a number representing the positive length of an interval |
| // starting at index 0. |
| // Intervals can span over some keys that are not in the object. |
| RUNTIME_FUNCTION(Runtime_GetArrayKeys) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0); |
| CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]); |
| if (array->elements()->IsDictionary()) { |
| Handle<FixedArray> keys = isolate->factory()->empty_fixed_array(); |
| for (PrototypeIterator iter(isolate, array, |
| PrototypeIterator::START_AT_RECEIVER); |
| !iter.IsAtEnd(); iter.Advance()) { |
| if (PrototypeIterator::GetCurrent(iter)->IsJSProxy() || |
| JSObject::cast(*PrototypeIterator::GetCurrent(iter)) |
| ->HasIndexedInterceptor()) { |
| // Bail out if we find a proxy or interceptor, likely not worth |
| // collecting keys in that case. |
| return *isolate->factory()->NewNumberFromUint(length); |
| } |
| Handle<JSObject> current = |
| Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter)); |
| Handle<FixedArray> current_keys = |
| isolate->factory()->NewFixedArray(current->NumberOfOwnElements(NONE)); |
| current->GetOwnElementKeys(*current_keys, NONE); |
| ASSIGN_RETURN_FAILURE_ON_EXCEPTION( |
| isolate, keys, FixedArray::UnionOfKeys(keys, current_keys)); |
| } |
| // Erase any keys >= length. |
| // TODO(adamk): Remove this step when the contract of %GetArrayKeys |
| // is changed to let this happen on the JS side. |
| for (int i = 0; i < keys->length(); i++) { |
| if (NumberToUint32(keys->get(i)) >= length) keys->set_undefined(i); |
| } |
| return *isolate->factory()->NewJSArrayWithElements(keys); |
| } else { |
| RUNTIME_ASSERT(array->HasFastSmiOrObjectElements() || |
| array->HasFastDoubleElements()); |
| uint32_t actual_length = static_cast<uint32_t>(array->elements()->length()); |
| return *isolate->factory()->NewNumberFromUint(Min(actual_length, length)); |
| } |
| } |
| |
| |
| static Object* ArrayConstructorCommon(Isolate* isolate, |
| Handle<JSFunction> constructor, |
| Handle<AllocationSite> site, |
| Arguments* caller_args) { |
| Factory* factory = isolate->factory(); |
| |
| bool holey = false; |
| bool can_use_type_feedback = true; |
| if (caller_args->length() == 1) { |
| Handle<Object> argument_one = caller_args->at<Object>(0); |
| if (argument_one->IsSmi()) { |
| int value = Handle<Smi>::cast(argument_one)->value(); |
| if (value < 0 || value >= JSObject::kInitialMaxFastElementArray) { |
| // the array is a dictionary in this case. |
| can_use_type_feedback = false; |
| } else if (value != 0) { |
| holey = true; |
| } |
| } else { |
| // Non-smi length argument produces a dictionary |
| can_use_type_feedback = false; |
| } |
| } |
| |
| Handle<JSArray> array; |
| if (!site.is_null() && can_use_type_feedback) { |
| ElementsKind to_kind = site->GetElementsKind(); |
| if (holey && !IsFastHoleyElementsKind(to_kind)) { |
| to_kind = GetHoleyElementsKind(to_kind); |
| // Update the allocation site info to reflect the advice alteration. |
| site->SetElementsKind(to_kind); |
| } |
| |
| // We should allocate with an initial map that reflects the allocation site |
| // advice. Therefore we use AllocateJSObjectFromMap instead of passing |
| // the constructor. |
| Handle<Map> initial_map(constructor->initial_map(), isolate); |
| if (to_kind != initial_map->elements_kind()) { |
| initial_map = Map::AsElementsKind(initial_map, to_kind); |
| } |
| |
| // If we don't care to track arrays of to_kind ElementsKind, then |
| // don't emit a memento for them. |
| Handle<AllocationSite> allocation_site; |
| if (AllocationSite::GetMode(to_kind) == TRACK_ALLOCATION_SITE) { |
| allocation_site = site; |
| } |
| |
| array = Handle<JSArray>::cast(factory->NewJSObjectFromMap( |
| initial_map, NOT_TENURED, true, allocation_site)); |
| } else { |
| array = Handle<JSArray>::cast(factory->NewJSObject(constructor)); |
| |
| // We might need to transition to holey |
| ElementsKind kind = constructor->initial_map()->elements_kind(); |
| if (holey && !IsFastHoleyElementsKind(kind)) { |
| kind = GetHoleyElementsKind(kind); |
| JSObject::TransitionElementsKind(array, kind); |
| } |
| } |
| |
| factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS); |
| |
| ElementsKind old_kind = array->GetElementsKind(); |
| RETURN_FAILURE_ON_EXCEPTION( |
| isolate, ArrayConstructInitializeElements(array, caller_args)); |
| if (!site.is_null() && |
| (old_kind != array->GetElementsKind() || !can_use_type_feedback)) { |
| // The arguments passed in caused a transition. This kind of complexity |
| // can't be dealt with in the inlined hydrogen array constructor case. |
| // We must mark the allocationsite as un-inlinable. |
| site->SetDoNotInlineCall(); |
| } |
| return *array; |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_ArrayConstructor) { |
| HandleScope scope(isolate); |
| // If we get 2 arguments then they are the stub parameters (constructor, type |
| // info). If we get 4, then the first one is a pointer to the arguments |
| // passed by the caller, and the last one is the length of the arguments |
| // passed to the caller (redundant, but useful to check on the deoptimizer |
| // with an assert). |
| Arguments empty_args(0, NULL); |
| bool no_caller_args = args.length() == 2; |
| DCHECK(no_caller_args || args.length() == 4); |
| int parameters_start = no_caller_args ? 0 : 1; |
| Arguments* caller_args = |
| no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]); |
| CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start); |
| CONVERT_ARG_HANDLE_CHECKED(Object, type_info, parameters_start + 1); |
| #ifdef DEBUG |
| if (!no_caller_args) { |
| CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 2); |
| DCHECK(arg_count == caller_args->length()); |
| } |
| #endif |
| |
| Handle<AllocationSite> site; |
| if (!type_info.is_null() && |
| *type_info != isolate->heap()->undefined_value()) { |
| site = Handle<AllocationSite>::cast(type_info); |
| DCHECK(!site->SitePointsToLiteral()); |
| } |
| |
| return ArrayConstructorCommon(isolate, constructor, site, caller_args); |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_InternalArrayConstructor) { |
| HandleScope scope(isolate); |
| Arguments empty_args(0, NULL); |
| bool no_caller_args = args.length() == 1; |
| DCHECK(no_caller_args || args.length() == 3); |
| int parameters_start = no_caller_args ? 0 : 1; |
| Arguments* caller_args = |
| no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]); |
| CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start); |
| #ifdef DEBUG |
| if (!no_caller_args) { |
| CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 1); |
| DCHECK(arg_count == caller_args->length()); |
| } |
| #endif |
| return ArrayConstructorCommon(isolate, constructor, |
| Handle<AllocationSite>::null(), caller_args); |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_NormalizeElements) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 1); |
| CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0); |
| RUNTIME_ASSERT(!array->HasExternalArrayElements() && |
| !array->HasFixedTypedArrayElements()); |
| JSObject::NormalizeElements(array); |
| return *array; |
| } |
| |
| |
| RUNTIME_FUNCTION(Runtime_HasComplexElements) { |
| HandleScope scope(isolate); |
| DCHECK(args.length() == 1); |
| CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0); |
| for (PrototypeIterator iter(isolate, array, |
| PrototypeIterator::START_AT_RECEIVER); |
| !iter.IsAtEnd(); iter.Advance()) { |
| if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) { |
| return isolate->heap()->true_value(); |
| } |
| Handle<JSObject> current = |
| Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter)); |
| if (current->HasIndexedInterceptor()) { |
| return isolate->heap()->true_value(); |
| } |
| if (!current->HasDictionaryElements()) continue; |
| if (current->element_dictionary()->HasComplexElements()) { |
| return isolate->heap()->true_value(); |
| } |
| } |
| return isolate->heap()->false_value(); |
| } |
| |
| |
| // TODO(dcarney): remove this function when TurboFan supports it. |
| // Takes the object to be iterated over and the result of GetPropertyNamesFast |
| // Returns pair (cache_array, cache_type). |
| RUNTIME_FUNCTION_RETURN_PAIR(Runtime_ForInInit) { |
| SealHandleScope scope(isolate); |
| DCHECK(args.length() == 2); |
| // This simulates CONVERT_ARG_HANDLE_CHECKED for calls returning pairs. |
| // Not worth creating a macro atm as this function should be removed. |
| if (!args[0]->IsJSReceiver() || !args[1]->IsObject()) { |
| Object* error = isolate->ThrowIllegalOperation(); |
| return MakePair(error, isolate->heap()->undefined_value()); |
| } |
| Handle<JSReceiver> object = args.at<JSReceiver>(0); |
| Handle<Object> cache_type = args.at<Object>(1); |
| if (cache_type->IsMap()) { |
| // Enum cache case. |
| if (Map::EnumLengthBits::decode(Map::cast(*cache_type)->bit_field3()) == |
| 0) { |
| // 0 length enum. |
| // Can't handle this case in the graph builder, |
| // so transform it into the empty fixed array case. |
| return MakePair(isolate->heap()->empty_fixed_array(), Smi::FromInt(1)); |
| } |
| return MakePair(object->map()->instance_descriptors()->GetEnumCache(), |
| *cache_type); |
| } else { |
| // FixedArray case. |
| Smi* new_cache_type = Smi::FromInt(object->IsJSProxy() ? 0 : 1); |
| return MakePair(*Handle<FixedArray>::cast(cache_type), new_cache_type); |
| } |
| } |
| |
| |
| // TODO(dcarney): remove this function when TurboFan supports it. |
| RUNTIME_FUNCTION(Runtime_ForInCacheArrayLength) { |
| SealHandleScope shs(isolate); |
| DCHECK(args.length() == 2); |
| CONVERT_ARG_HANDLE_CHECKED(Object, cache_type, 0); |
| CONVERT_ARG_HANDLE_CHECKED(FixedArray, array, 1); |
| int length = 0; |
| if (cache_type->IsMap()) { |
| length = Map::cast(*cache_type)->EnumLength(); |
| } else { |
| DCHECK(cache_type->IsSmi()); |
| length = array->length(); |
| } |
| return Smi::FromInt(length); |
| } |
| |
| |
| // TODO(dcarney): remove this function when TurboFan supports it. |
| // Takes (the object to be iterated over, |
| // cache_array from ForInInit, |
| // cache_type from ForInInit, |
| // the current index) |
| // Returns pair (array[index], needs_filtering). |
| RUNTIME_FUNCTION_RETURN_PAIR(Runtime_ForInNext) { |
| SealHandleScope scope(isolate); |
| DCHECK(args.length() == 4); |
| int32_t index; |
| // This simulates CONVERT_ARG_HANDLE_CHECKED for calls returning pairs. |
| // Not worth creating a macro atm as this function should be removed. |
| if (!args[0]->IsJSReceiver() || !args[1]->IsFixedArray() || |
| !args[2]->IsObject() || !args[3]->ToInt32(&index)) { |
| Object* error = isolate->ThrowIllegalOperation(); |
| return MakePair(error, isolate->heap()->undefined_value()); |
| } |
| Handle<JSReceiver> object = args.at<JSReceiver>(0); |
| Handle<FixedArray> array = args.at<FixedArray>(1); |
| Handle<Object> cache_type = args.at<Object>(2); |
| // Figure out first if a slow check is needed for this object. |
| bool slow_check_needed = false; |
| if (cache_type->IsMap()) { |
| if (object->map() != Map::cast(*cache_type)) { |
| // Object transitioned. Need slow check. |
| slow_check_needed = true; |
| } |
| } else { |
| // No slow check needed for proxies. |
| slow_check_needed = Smi::cast(*cache_type)->value() == 1; |
| } |
| return MakePair(array->get(index), |
| isolate->heap()->ToBoolean(slow_check_needed)); |
| } |
| |
| |
| RUNTIME_FUNCTION(RuntimeReference_IsArray) { |
| SealHandleScope shs(isolate); |
| DCHECK(args.length() == 1); |
| CONVERT_ARG_CHECKED(Object, obj, 0); |
| return isolate->heap()->ToBoolean(obj->IsJSArray()); |
| } |
| |
| |
| RUNTIME_FUNCTION(RuntimeReference_HasCachedArrayIndex) { |
| SealHandleScope shs(isolate); |
| DCHECK(args.length() == 1); |
| return isolate->heap()->false_value(); |
| } |
| |
| |
| RUNTIME_FUNCTION(RuntimeReference_GetCachedArrayIndex) { |
| SealHandleScope shs(isolate); |
| DCHECK(args.length() == 1); |
| return isolate->heap()->undefined_value(); |
| } |
| |
| |
| RUNTIME_FUNCTION(RuntimeReference_FastOneByteArrayJoin) { |
| SealHandleScope shs(isolate); |
| DCHECK(args.length() == 2); |
| return isolate->heap()->undefined_value(); |
| } |
| } |
| } // namespace v8::internal |