Revision: 7156
Author: [email protected]
Date: Mon Mar 14 05:32:24 2011
Log: Port revision 6934 (plus fix from 6935) and refactoring in revision
6993 to the 3.0 branch.
Review URL: http://codereview.chromium.org/6592007
http://code.google.com/p/v8/source/detail?r=7156
Modified:
/branches/3.0/src/array.js
/branches/3.0/src/handles-inl.h
/branches/3.0/src/handles.h
/branches/3.0/src/objects-inl.h
/branches/3.0/src/runtime.cc
/branches/3.0/src/version.cc
/branches/3.0/test/mjsunit/array-concat.js
=======================================
--- /branches/3.0/src/array.js Fri Feb 25 03:44:19 2011
+++ /branches/3.0/src/array.js Mon Mar 14 05:32:24 2011
@@ -426,7 +426,6 @@
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;
=======================================
--- /branches/3.0/src/handles-inl.h Wed Oct 27 02:33:13 2010
+++ /branches/3.0/src/handles-inl.h Mon Mar 14 05:32:24 2011
@@ -36,14 +36,14 @@
namespace v8 {
namespace internal {
-template<class T>
+template<typename T>
Handle<T>::Handle(T* obj) {
ASSERT(!obj->IsFailure());
location_ = HandleScope::CreateHandle(obj);
}
-template <class T>
+template <typename T>
inline T* Handle<T>::operator*() const {
ASSERT(location_ != NULL);
ASSERT(reinterpret_cast<Address>(*location_) != kHandleZapValue);
=======================================
--- /branches/3.0/src/handles.h Mon Jan 10 00:15:37 2011
+++ /branches/3.0/src/handles.h Mon Mar 14 05:32:24 2011
@@ -39,7 +39,7 @@
// Handles are only valid within a HandleScope.
// When a handle is created for an object a cell is allocated in the heap.
-template<class T>
+template<typename T>
class Handle {
public:
INLINE(explicit Handle(T** location)) { location_ = location; }
@@ -112,15 +112,7 @@
}
~HandleScope() {
- current_.next = prev_next_;
- current_.level--;
- if (current_.limit != prev_limit_) {
- current_.limit = prev_limit_;
- DeleteExtensions();
- }
-#ifdef DEBUG
- ZapRange(prev_next_, prev_limit_);
-#endif
+ CloseScope();
}
// Counts the number of allocated handles.
@@ -147,6 +139,26 @@
static Address current_next_address();
static Address current_limit_address();
static Address current_level_address();
+
+ // Closes the HandleScope (invalidating all handles
+ // created in the scope of the HandleScope) and returns
+ // a Handle backed by the parent scope holding the
+ // value of the argument handle.
+ template <typename T>
+ Handle<T> CloseAndEscape(Handle<T> handle_value) {
+ T* value = *handle_value;
+ // Throw away all handles in the current scope.
+ CloseScope();
+ // Allocate one handle in the parent scope.
+ ASSERT(current_.level > 0);
+ Handle<T> result(CreateHandle<T>(value));
+ // Reinitialize the current scope (so that it's ready
+ // to be used or closed again).
+ prev_next_ = current_.next;
+ prev_limit_ = current_.limit;
+ current_.level++;
+ return result;
+ }
private:
// Prevent heap allocation or illegal handle scopes.
@@ -155,9 +167,23 @@
void* operator new(size_t size);
void operator delete(void* size_t);
+ inline void CloseScope() {
+ current_.next = prev_next_;
+ current_.level--;
+ if (current_.limit != prev_limit_) {
+ current_.limit = prev_limit_;
+ DeleteExtensions();
+ }
+#ifdef DEBUG
+ ZapRange(prev_next_, prev_limit_);
+#endif
+ }
+
static v8::ImplementationUtilities::HandleScopeData current_;
- Object** const prev_next_;
- Object** const prev_limit_;
+ // Holds values on entry. The prev_next_ value is never NULL
+ // on_entry, but is set to NULL when this scope is closed.
+ Object** prev_next_;
+ Object** prev_limit_;
// Extend the handle scope making room for more handles.
static internal::Object** Extend();
=======================================
--- /branches/3.0/src/objects-inl.h Wed Feb 16 01:11:23 2011
+++ /branches/3.0/src/objects-inl.h Mon Mar 14 05:32:24 2011
@@ -769,6 +769,10 @@
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);
}
=======================================
--- /branches/3.0/src/runtime.cc Wed Feb 16 01:11:23 2011
+++ /branches/3.0/src/runtime.cc Mon Mar 14 05:32:24 2011
@@ -40,6 +40,7 @@
#include "debug.h"
#include "deoptimizer.h"
#include "execution.h"
+#include "global-handles.h"
#include "jsregexp.h"
#include "liveedit.h"
#include "parser.h"
@@ -7894,398 +7895,488 @@
class ArrayConcatVisitor {
public:
ArrayConcatVisitor(Handle<FixedArray> storage,
- uint32_t index_limit,
bool fast_elements) :
- storage_(storage), index_limit_(index_limit),
- index_offset_(0), fast_elements_(fast_elements) { }
+ storage_(Handle<FixedArray>::cast(GlobalHandles::Create(*storage))),
+ index_offset_(0u),
+ fast_elements_(fast_elements) { }
+
+ ~ArrayConcatVisitor() {
+ clear_storage();
+ }
void visit(uint32_t i, Handle<Object> 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<uint32_t>(storage_->length()));
- storage_->set(index, *elm);
-
+ 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(index);
+ // Fall-through to dictionary mode.
+ }
+ ASSERT(!fast_elements_);
+ Handle<NumberDictionary> dict(NumberDictionary::cast(*storage_));
+ Handle<NumberDictionary> result =
+ Factory::DictionaryAtNumberPut(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 {
- Handle<NumberDictionary> dict =
Handle<NumberDictionary>::cast(storage_);
- Handle<NumberDictionary> result =
- Factory::DictionaryAtNumberPut(dict, index, elm);
- if (!result.is_identical_to(dict))
- storage_ = result;
+ index_offset_ += delta;
}
}
- void increase_index_offset(uint32_t delta) {
- if (index_limit_ - index_offset_ < delta) {
- index_offset_ = index_limit_;
+ Handle<JSArray> ToArray() {
+ Handle<JSArray> array = Factory::NewJSArray(0);
+ Handle<Object> length =
+ Factory::NewNumber(static_cast<double>(index_offset_));
+ Handle<Map> map;
+ if (fast_elements_) {
+ map = Factory::GetFastElementsMap(Handle<Map>(array->map()));
} else {
- index_offset_ += delta;
- }
- }
-
- Handle<FixedArray> storage() { return storage_; }
+ map = Factory::GetSlowElementsMap(Handle<Map>(array->map()));
+ }
+ array->set_map(*map);
+ array->set_length(*length);
+ array->set_elements(*storage_);
+ return array;
+ }
private:
- Handle<FixedArray> 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<FixedArray> current_storage(*storage_);
+ Handle<NumberDictionary> slow_storage(
+ Factory::NewNumberDictionary(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;
+ Handle<Object> element(current_storage->get(i));
+ if (!element->IsTheHole()) {
+ Handle<NumberDictionary> new_storage =
+ Factory::DictionaryAtNumberPut(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(GlobalHandles::Create(storage));
+ }
+
+ Handle<FixedArray> storage_; // Always a global handle.
+ // 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<JSArray> array) {
+ uint32_t length = static_cast<uint32_t>(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<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 JSObject::DICTIONARY_ELEMENTS: {
+ Handle<NumberDictionary> dictionary(
+ NumberDictionary::cast(array->elements()));
+ int capacity = dictionary->Capacity();
+ for (int i = 0; i < capacity; i++) {
+ Handle<Object> 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<class ExternalArrayClass, class ElementType>
-static uint32_t IterateExternalArrayElements(Handle<JSObject> receiver,
- bool elements_are_ints,
- bool
elements_are_guaranteed_smis,
- uint32_t range,
- ArrayConcatVisitor* visitor) {
+static void IterateExternalArrayElements(Handle<JSObject> receiver,
+ bool elements_are_ints,
+ bool elements_are_guaranteed_smis,
+ ArrayConcatVisitor* visitor) {
Handle<ExternalArrayClass> array(
ExternalArrayClass::cast(receiver->elements()));
- uint32_t len = Min(static_cast<uint32_t>(array->length()), range);
-
- if (visitor != NULL) {
- if (elements_are_ints) {
- if (elements_are_guaranteed_smis) {
- for (uint32_t j = 0; j < len; j++) {
- Handle<Smi> e(Smi::FromInt(static_cast<int>(array->get(j))));
+ uint32_t len = static_cast<uint32_t>(array->length());
+
+ ASSERT(visitor != NULL);
+ if (elements_are_ints) {
+ if (elements_are_guaranteed_smis) {
+ for (uint32_t j = 0; j < len; j++) {
+ HandleScope loop_scope;
+ Handle<Smi> e(Smi::FromInt(static_cast<int>(array->get(j))));
+ visitor->visit(j, e);
+ }
+ } else {
+ for (uint32_t j = 0; j < len; j++) {
+ HandleScope loop_scope;
+ int64_t val = static_cast<int64_t>(array->get(j));
+ if (Smi::IsValid(static_cast<intptr_t>(val))) {
+ Handle<Smi> e(Smi::FromInt(static_cast<int>(val)));
visitor->visit(j, e);
- }
- } else {
- for (uint32_t j = 0; j < len; j++) {
- int64_t val = static_cast<int64_t>(array->get(j));
- if (Smi::IsValid(static_cast<intptr_t>(val))) {
- Handle<Smi> e(Smi::FromInt(static_cast<int>(val)));
- visitor->visit(j, e);
- } else {
- Handle<Object> e =
- Factory::NewNumber(static_cast<ElementType>(val));
- visitor->visit(j, e);
+ } else {
+ Handle<Object> e =
+ Factory::NewNumber(static_cast<ElementType>(val));
+ visitor->visit(j, e);
+ }
+ }
+ }
+ } else {
+ for (uint32_t j = 0; j < len; j++) {
+ HandleScope loop_scope;
+ Handle<Object> e = Factory::NewNumber(array->get(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) {
+ JSObject::ElementsKind kind = object->GetElementsKind();
+ switch (kind) {
+ case JSObject::FAST_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 JSObject::DICTIONARY_ELEMENTS: {
+ Handle<NumberDictionary>
dict(NumberDictionary::cast(object->elements()));
+ uint32_t capacity = dict->Capacity();
+ for (uint32_t j = 0; j < capacity; j++) {
+ HandleScope loop_scope;
+ Handle<Object> k(dict->KeyAt(j));
+ if (dict->IsKey(*k)) {
+ ASSERT(k->IsNumber());
+ uint32_t index = static_cast<uint32_t>(k->Number());
+ if (index < range) {
+ indices->Add(index);
}
}
}
- } else {
- for (uint32_t j = 0; j < len; j++) {
- Handle<Object> 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();
+ dense_elements_length = 0;
+ break;
+ }
+ uint32_t length = static_cast<uint32_t>(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<Object> prototype(object->GetPrototype());
+ if (prototype->IsJSObject()) {
+ // The prototype will usually have no inherited element indices,
+ // but we have to check.
+ CollectElementIndices(Handle<JSObject>::cast(prototype), range,
indices);
+ }
+}
+
/**
- * A helper function that visits elements of a JSObject. Only elements
- * whose index between 0 and range (exclusive) are visited.
+ * A helper function that visits elements of a JSArray in numerical
+ * order.
*
- * If the third parameter, visitor, is not NULL, the visitor is called
- * with parameters, 'visitor_index_offset + element index' and the element.
- *
- * 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<JSObject> receiver,
- uint32_t range,
- ArrayConcatVisitor* visitor) {
- uint32_t num_of_elements = 0;
-
+static void IterateElements(Handle<JSArray> receiver,
+ ArrayConcatVisitor* visitor) {
+ uint32_t length = static_cast<uint32_t>(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<FixedArray> elements(FixedArray::cast(receiver->elements()));
- uint32_t len = elements->length();
- if (range < len) {
- len = range;
- }
-
- for (uint32_t j = 0; j < len; j++) {
- Handle<Object> e(elements->get(j));
- if (!e->IsTheHole()) {
- num_of_elements++;
- if (visitor) {
- visitor->visit(j, e);
- }
+ int fast_length = static_cast<int>(length);
+ ASSERT(fast_length <= elements->length());
+ for (int j = 0; j < fast_length; j++) {
+ HandleScope loop_scope;
+ Handle<Object> 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<NumberDictionary> 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;
+ uint32_t index = indices[j];
+ Handle<Object> 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<PixelArray> 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<Smi> e(Smi::FromInt(pixels->get(j)));
- visitor->visit(j, e);
- }
+ for (uint32_t j = 0; j < length; j++) {
+ Handle<Smi> e(Smi::FromInt(pixels->get(j)));
+ visitor->visit(j, e);
}
break;
}
case JSObject::EXTERNAL_BYTE_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalByteArray, int8_t>(
- receiver, true, true, range, visitor);
+ IterateExternalArrayElements<ExternalByteArray, int8_t>(
+ receiver, true, true, visitor);
break;
}
case JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalUnsignedByteArray, uint8_t>(
- receiver, true, true, range, visitor);
+ IterateExternalArrayElements<ExternalUnsignedByteArray, uint8_t>(
+ receiver, true, true, visitor);
break;
}
case JSObject::EXTERNAL_SHORT_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalShortArray, int16_t>(
- receiver, true, true, range, visitor);
+ IterateExternalArrayElements<ExternalShortArray, int16_t>(
+ receiver, true, true, visitor);
break;
}
case JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalUnsignedShortArray,
uint16_t>(
- receiver, true, true, range, visitor);
+ IterateExternalArrayElements<ExternalUnsignedShortArray, uint16_t>(
+ receiver, true, true, visitor);
break;
}
case JSObject::EXTERNAL_INT_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalIntArray, int32_t>(
- receiver, true, false, range, visitor);
+ IterateExternalArrayElements<ExternalIntArray, int32_t>(
+ receiver, true, false, visitor);
break;
}
case JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalUnsignedIntArray, uint32_t>(
- receiver, true, false, range, visitor);
+ IterateExternalArrayElements<ExternalUnsignedIntArray, uint32_t>(
+ receiver, true, false, visitor);
break;
}
case JSObject::EXTERNAL_FLOAT_ELEMENTS: {
- num_of_elements =
- IterateExternalArrayElements<ExternalFloatArray, float>(
- receiver, false, false, range, visitor);
+ IterateExternalArrayElements<ExternalFloatArray, float>(
+ receiver, false, false, visitor);
break;
}
- case JSObject::DICTIONARY_ELEMENTS: {
- Handle<NumberDictionary> dict(receiver->element_dictionary());
- uint32_t capacity = dict->Capacity();
- for (uint32_t j = 0; j < capacity; j++) {
- Handle<Object> k(dict->KeyAt(j));
- if (dict->IsKey(*k)) {
- ASSERT(k->IsNumber());
- uint32_t index = static_cast<uint32_t>(k->Number());
- if (index < range) {
- num_of_elements++;
- if (visitor) {
- visitor->visit(index, Handle<Object>(dict->ValueAt(j)));
- }
- }
- }
- }
- 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<JSArray> array,
- ArrayConcatVisitor*
visitor) {
- uint32_t range = static_cast<uint32_t>(array->length()->Number());
- Handle<Object> obj = array;
-
- static const int kEstimatedPrototypes = 3;
- List< Handle<JSObject> > 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<JSObject>::cast(obj));
- obj = Handle<Object>(obj->GetPrototype());
- }
-
- uint32_t nof_elements = 0;
- for (int i = objects.length() - 1; i >= 0; i--) {
- Handle<JSObject> obj = objects[i];
- uint32_t encountered_elements =
- IterateElements(Handle<JSObject>::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<JSArray> arguments,
- ArrayConcatVisitor* visitor) {
- uint32_t visited_elements = 0;
- uint32_t num_of_args =
static_cast<uint32_t>(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<Object> obj(element);
- if (obj->IsJSArray()) {
- Handle<JSArray> array = Handle<JSArray>::cast(obj);
- uint32_t len = static_cast<uint32_t>(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<JSArray> 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<uint32_t>(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<uint32_t>(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<int>(arguments->length()->Number());
+ RUNTIME_ASSERT(arguments->HasFastElements());
+ 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.
+
+ uint32_t estimate_result_length = 0;
+ uint32_t estimate_nof_elements = 0;
+ {
+ for (int i = 0; i < argument_count; i++) {
+ HandleScope loop_scope;
+ Handle<Object> obj(elements->get(i));
+ 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());
+ 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 length and content later.
- Handle<JSArray> 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<FixedArray> storage;
if (fast_case) {
// The backing storage array must have non-existing elements to
// preserve holes across concat operations.
- storage = Factory::NewFixedArrayWithHoles(result_length);
- Handle<Map> fast_map =
- Factory::GetFastElementsMap(Handle<Map>(result->map()));
- result->set_map(*fast_map);
+ storage = 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(
Factory::NewNumberDictionary(at_least_space_for));
- Handle<Map> slow_map =
- Factory::GetSlowElementsMap(Handle<Map>(result->map()));
- result->set_map(*slow_map);
}
- Handle<Object> len =
Factory::NewNumber(static_cast<double>(result_length));
-
- ArrayConcatVisitor visitor(storage, result_length, fast_case);
-
- IterateArguments(arguments, &visitor);
-
- result->set_length(*len);
- // Please note the storage might have changed in the visitor.
- result->set_elements(*visitor.storage());
-
- return *result;
+ ArrayConcatVisitor visitor(storage, fast_case);
+
+ for (int i = 0; i < argument_count; i++) {
+ Handle<Object> obj(elements->get(i));
+ if (obj->IsJSArray()) {
+ Handle<JSArray> array = Handle<JSArray>::cast(obj);
+ IterateElements(array, &visitor);
+ } else {
+ visitor.visit(0, obj);
+ visitor.increase_index_offset(1);
+ }
+ }
+
+ return *visitor.ToArray();
}
=======================================
--- /branches/3.0/src/version.cc Wed Mar 9 05:10:51 2011
+++ /branches/3.0/src/version.cc Mon Mar 14 05:32:24 2011
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 3
#define MINOR_VERSION 0
#define BUILD_NUMBER 12
-#define PATCH_LEVEL 31
+#define PATCH_LEVEL 32
#define CANDIDATE_VERSION false
// Define SONAME to have the SCons build the put a specific SONAME into the
=======================================
--- /branches/3.0/test/mjsunit/array-concat.js Mon May 17 02:10:26 2010
+++ /branches/3.0/test/mjsunit/array-concat.js Mon Mar 14 05:32:24 2011
@@ -101,7 +101,6 @@
assertEquals("undefined", typeof(c[-1]));
assertEquals("undefined", typeof(c[0xffffffff]));
assertEquals(c.length, a.length + 1);
-
}
poses = [140, 4000000000];
@@ -193,3 +192,46 @@
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);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
