Google Git
Sign in
android / platform / external / v8 / 2a61e75 / . / src / runtime / runtime-array.cc
blob: a017236a540643ef08e8b0f6b64c95d4dc0752b5 [file] [log] [blame]
// 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),
bit_field_(FastElementsField::encode(fast_elements) |
ExceedsLimitField::encode(false)) {}
~ArrayConcatVisitor() { clear_storage(); }
void visit(uint32_t i, Handle<Object> elm) {
if (i > JSObject::kMaxElementCount - index_offset_) {
set_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() const {
return ExceedsLimitField::decode(bit_field_);
}
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);
set_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));
}
class FastElementsField : public BitField<bool, 0, 1> {};
class ExceedsLimitField : public BitField<bool, 1, 1> {};
bool fast_elements() const { return FastElementsField::decode(bit_field_); }
void set_fast_elements(bool fast) {
bit_field_ = FastElementsField::update(bit_field_, fast);
}
void set_exceeds_array_limit(bool exceeds) {
bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
}
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_;
uint32_t bit_field_;
};
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 IterateTypedArrayElements(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);
}
}
static bool IterateElementsSlow(Isolate* isolate, Handle<JSObject> receiver,
uint32_t length, ArrayConcatVisitor* visitor) {
for (uint32_t i = 0; i < length; ++i) {
HandleScope loop_scope(isolate);
Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
if (!maybe.has_value) return false;
if (maybe.value) {
Handle<Object> element_value;
ASSIGN_RETURN_ON_EXCEPTION_VALUE(
isolate, element_value,
Runtime::GetElementOrCharAt(isolate, receiver, i), false);
visitor->visit(i, element_value);
}
}
visitor->increase_index_offset(length);
return true;
}
/**
* A helper function that visits elements of a JSObject 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<JSObject> receiver,
ArrayConcatVisitor* visitor) {
uint32_t length = 0;
if (receiver->IsJSArray()) {
Handle<JSArray> array(Handle<JSArray>::cast(receiver));
length = static_cast<uint32_t>(array->length()->Number());
} else {
Handle<Object> val;
Handle<Object> key(isolate->heap()->length_string(), isolate);
ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, val,
Runtime::GetObjectProperty(isolate, receiver, key), false);
// TODO(caitp): Support larger element indexes (up to 2^53-1).
if (!val->ToUint32(&length)) {
ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, val,
Execution::ToLength(isolate, val), false);
val->ToUint32(&length);
}
}
if (!(receiver->IsJSArray() || receiver->IsJSTypedArray())) {
// For classes which are not known to be safe to access via elements alone,
// use the slow case.
return IterateElementsSlow(isolate, receiver, length, visitor);
}
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 UINT8_CLAMPED_ELEMENTS: {
Handle<FixedUint8ClampedArray> pixels(
FixedUint8ClampedArray::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: {
IterateTypedArrayElements<ExternalInt8Array, int8_t>(
isolate, receiver, true, true, visitor);
break;
}
case INT8_ELEMENTS: {
IterateTypedArrayElements<FixedInt8Array, int8_t>(
isolate, receiver, true, true, visitor);
break;
}
case EXTERNAL_UINT8_ELEMENTS: {
IterateTypedArrayElements<ExternalUint8Array, uint8_t>(
isolate, receiver, true, true, visitor);
break;
}
case UINT8_ELEMENTS: {
IterateTypedArrayElements<FixedUint8Array, uint8_t>(
isolate, receiver, true, true, visitor);
break;
}
case EXTERNAL_INT16_ELEMENTS: {
IterateTypedArrayElements<ExternalInt16Array, int16_t>(
isolate, receiver, true, true, visitor);
break;
}
case INT16_ELEMENTS: {
IterateTypedArrayElements<FixedInt16Array, int16_t>(
isolate, receiver, true, true, visitor);
break;
}
case EXTERNAL_UINT16_ELEMENTS: {
IterateTypedArrayElements<ExternalUint16Array, uint16_t>(
isolate, receiver, true, true, visitor);
break;
}
case UINT16_ELEMENTS: {
IterateTypedArrayElements<FixedUint16Array, uint16_t>(
isolate, receiver, true, true, visitor);
break;
}
case EXTERNAL_INT32_ELEMENTS: {
IterateTypedArrayElements<ExternalInt32Array, int32_t>(
isolate, receiver, true, false, visitor);
break;
}
case INT32_ELEMENTS: {
IterateTypedArrayElements<FixedInt32Array, int32_t>(
isolate, receiver, true, false, visitor);
break;
}
case EXTERNAL_UINT32_ELEMENTS: {
IterateTypedArrayElements<ExternalUint32Array, uint32_t>(
isolate, receiver, true, false, visitor);
break;
}
case UINT32_ELEMENTS: {
IterateTypedArrayElements<FixedUint32Array, uint32_t>(
isolate, receiver, true, false, visitor);
break;
}
case EXTERNAL_FLOAT32_ELEMENTS: {
IterateTypedArrayElements<ExternalFloat32Array, float>(
isolate, receiver, false, false, visitor);
break;
}
case FLOAT32_ELEMENTS: {
IterateTypedArrayElements<FixedFloat32Array, float>(
isolate, receiver, false, false, visitor);
break;
}
case EXTERNAL_FLOAT64_ELEMENTS: {
IterateTypedArrayElements<ExternalFloat64Array, double>(
isolate, receiver, false, false, visitor);
break;
}
case FLOAT64_ELEMENTS: {
IterateTypedArrayElements<FixedFloat64Array, double>(
isolate, receiver, false, false, visitor);
break;
}
case SLOPPY_ARGUMENTS_ELEMENTS: {
ElementsAccessor* accessor = receiver->GetElementsAccessor();
for (uint32_t index = 0; index < length; index++) {
HandleScope loop_scope(isolate);
if (accessor->HasElement(receiver, receiver, index)) {
Handle<Object> element;
ASSIGN_RETURN_ON_EXCEPTION_VALUE(
isolate, element, accessor->Get(receiver, receiver, index),
false);
visitor->visit(index, element);
}
}
break;
}
}
visitor->increase_index_offset(length);
return true;
}
static bool IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
HandleScope handle_scope(isolate);
if (!obj->IsSpecObject()) return false;
if (obj->IsJSArray()) return true;
if (FLAG_harmony_arrays) {
Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
Handle<Object> value;
MaybeHandle<Object> maybeValue =
i::Runtime::GetObjectProperty(isolate, obj, key);
if (maybeValue.ToHandle(&value)) {
return value->BooleanValue();
}
}
return false;
}
/**
* 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);
bool spreadable = IsConcatSpreadable(isolate, obj);
if (isolate->has_pending_exception()) return isolate->heap()->exception();
if (spreadable) {
Handle<JSObject> object = Handle<JSObject>::cast(obj);
if (!IterateElements(isolate, object, &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