Author: [email protected]
Date: Mon Apr 27 04:16:59 2009
New Revision: 1800
Added:
branches/bleeding_edge/test/mjsunit/regress/regress-326.js
Modified:
branches/bleeding_edge/src/array.js
branches/bleeding_edge/src/globals.h
branches/bleeding_edge/src/objects.cc
branches/bleeding_edge/src/objects.h
branches/bleeding_edge/src/runtime.cc
branches/bleeding_edge/src/runtime.h
branches/bleeding_edge/test/mjsunit/array-sort.js
Log:
Fix Issue 326. Handle sorting of non-array objects correctly.
Change handling of sorting to be the same for all JS-arrays.
Collect undefined values as well while removing holes.
Review URL: http://codereview.chromium.org/92123
Modified: branches/bleeding_edge/src/array.js
==============================================================================
--- branches/bleeding_edge/src/array.js (original)
+++ branches/bleeding_edge/src/array.js Mon Apr 27 04:16:59 2009
@@ -709,33 +709,12 @@
QuickSort(a, high_start, to);
}
- var old_length = ToUint32(this.length);
- if (old_length < 2) return this;
-
- %RemoveArrayHoles(this);
-
var length = ToUint32(this.length);
+ if (length < 2) return this;
- // Move undefined elements to the end of the array.
- for (var i = 0; i < length; ) {
- if (IS_UNDEFINED(this[i])) {
- length--;
- this[i] = this[length];
- this[length] = void 0;
- } else {
- i++;
- }
- }
-
- QuickSort(this, 0, length);
+ var num_non_undefined = %RemoveArrayHoles(this, length);
- // We only changed the length of the this object (in
- // RemoveArrayHoles) if it was an array. We are not allowed to set
- // the length of the this object if it is not an array because this
- // might introduce a new length property.
- if (IS_ARRAY(this)) {
- this.length = old_length;
- }
+ QuickSort(this, 0, num_non_undefined);
return this;
}
Modified: branches/bleeding_edge/src/globals.h
==============================================================================
--- branches/bleeding_edge/src/globals.h (original)
+++ branches/bleeding_edge/src/globals.h Mon Apr 27 04:16:59 2009
@@ -86,6 +86,8 @@
const int kMaxInt = 0x7FFFFFFF;
const int kMinInt = -kMaxInt - 1;
+const uint32_t kMaxUInt32 = 0xFFFFFFFFu;
+
const int kCharSize = sizeof(char); // NOLINT
const int kShortSize = sizeof(short); // NOLINT
const int kIntSize = sizeof(int); // NOLINT
Modified: branches/bleeding_edge/src/objects.cc
==============================================================================
--- branches/bleeding_edge/src/objects.cc (original)
+++ branches/bleeding_edge/src/objects.cc Mon Apr 27 04:16:59 2009
@@ -2850,22 +2850,26 @@
Object* FixedArray::AddKeysFromJSArray(JSArray* array) {
- // Remove array holes from array if any.
- Object* object = array->RemoveHoles();
- if (object->IsFailure()) return object;
- JSArray* compacted_array = JSArray::cast(object);
+ if (array->HasFastElements()) {
+ return UnionOfKeys(array->elements());
+ }
+ ASSERT(!array->HasFastElements());
+ Dictionary* dict = array->element_dictionary();
+ int size = dict->NumberOfElements();
// Allocate a temporary fixed array.
- int compacted_array_length =
Smi::cast(compacted_array->length())->value();
- object = Heap::AllocateFixedArray(compacted_array_length);
+ Object* object = Heap::AllocateFixedArray(size);
if (object->IsFailure()) return object;
FixedArray* key_array = FixedArray::cast(object);
+ int capacity = dict->Capacity();
+ int pos = 0;
// Copy the elements from the JSArray to the temporary fixed array.
- for (int i = 0; i < compacted_array_length; i++) {
- key_array->set(i, compacted_array->GetElement(i));
+ for (int i = 0; i < capacity; i++) {
+ if (dict->IsKey(dict->KeyAt(i))) {
+ key_array->set(pos++, dict->ValueAt(i));
+ }
}
-
// Compute the union of this and the temporary fixed array.
return UnionOfKeys(key_array);
}
@@ -2881,9 +2885,12 @@
// Compute how many elements are not in this.
int extra = 0;
for (int y = 0; y < len1; y++) {
- if (!HasKey(this, other->get(y))) extra++;
+ Object* value = other->get(y);
+ if (!value->IsTheHole() && !HasKey(this, value)) extra++;
}
+ if (extra == 0) return this;
+
// Allocate the result
Object* obj = Heap::AllocateFixedArray(len0 + extra);
if (obj->IsFailure()) return obj;
@@ -2896,7 +2903,8 @@
// Fill in the extra keys.
int index = 0;
for (int y = 0; y < len1; y++) {
- if (!HasKey(this, other->get(y))) {
+ Object* value = other->get(y);
+ if (!value->IsTheHole() && !HasKey(this, value)) {
result->set(len0 + index, other->get(y), mode);
index++;
}
@@ -5628,75 +5636,18 @@
}
-Object* Dictionary::RemoveHoles() {
- int capacity = Capacity();
- Object* obj = Allocate(NumberOfElements());
- if (obj->IsFailure()) return obj;
- Dictionary* dict = Dictionary::cast(obj);
- uint32_t pos = 0;
- for (int i = 0; i < capacity; i++) {
- Object* k = KeyAt(i);
- if (IsKey(k)) {
- dict->AddNumberEntry(pos++, ValueAt(i), DetailsAt(i));
- }
- }
- return dict;
-}
-
-
void Dictionary::CopyValuesTo(FixedArray* elements) {
int pos = 0;
int capacity = Capacity();
+ WriteBarrierMode mode = elements->GetWriteBarrierMode();
for (int i = 0; i < capacity; i++) {
Object* k = KeyAt(i);
- if (IsKey(k)) elements->set(pos++, ValueAt(i));
+ if (IsKey(k)) elements->set(pos++, ValueAt(i), mode);
}
ASSERT(pos == elements->length());
}
-Object* JSArray::RemoveHoles() {
- if (HasFastElements()) {
- int len = Smi::cast(length())->value();
- int pos = 0;
- FixedArray* elms = FixedArray::cast(elements());
- for (int index = 0; index < len; index++) {
- Object* e = elms->get(index);
- if (!e->IsTheHole()) {
- if (index != pos) elms->set(pos, e);
- pos++;
- }
- }
- set_length(Smi::FromInt(pos), SKIP_WRITE_BARRIER);
- for (int index = pos; index < len; index++) {
- elms->set_the_hole(index);
- }
- return this;
- }
-
- // Compact the sparse array if possible.
- Dictionary* dict = element_dictionary();
- int length = dict->NumberOfElements();
-
- // Try to make this a fast array again.
- if (length <= kMaxFastElementsLength) {
- Object* obj = Heap::AllocateFixedArray(length);
- if (obj->IsFailure()) return obj;
- dict->CopyValuesTo(FixedArray::cast(obj));
- set_length(Smi::FromInt(length), SKIP_WRITE_BARRIER);
- set_elements(FixedArray::cast(obj));
- return this;
- }
-
- // Make another dictionary with smaller indices.
- Object* obj = dict->RemoveHoles();
- if (obj->IsFailure()) return obj;
- set_length(Smi::FromInt(length), SKIP_WRITE_BARRIER);
- set_elements(Dictionary::cast(obj));
- return this;
-}
-
-
InterceptorInfo* JSObject::GetNamedInterceptor() {
ASSERT(map()->has_named_interceptor());
JSFunction* constructor = JSFunction::cast(map()->constructor());
@@ -6446,6 +6397,176 @@
// Force instantiation of EvalCache's base class
template class HashTable<0, 2>;
+
+
+// Collates undefined and unexisting elements below limit from position
+// zero of the elements. The object stays in Dictionary mode.
+Object* JSObject::PrepareSlowElementsForSort(uint32_t limit) {
+ ASSERT(!HasFastElements());
+ // Must stay in dictionary mode, either because of
requires_slow_elements,
+ // or because we are not going to sort (and therefore compact) all of the
+ // elements.
+ Dictionary* dict = element_dictionary();
+ HeapNumber* result_double = NULL;
+ if (limit > static_cast<uint32_t>(Smi::kMaxValue)) {
+ // Allocate space for result before we start mutating the object.
+ Object* new_double = Heap::AllocateHeapNumber(0.0);
+ if (new_double->IsFailure()) return new_double;
+ result_double = HeapNumber::cast(new_double);
+ }
+
+ int capacity = dict->Capacity();
+ Object* obj = Dictionary::Allocate(dict->Capacity());
+ if (obj->IsFailure()) return obj;
+ Dictionary* new_dict = Dictionary::cast(obj);
+
+ AssertNoAllocation no_alloc;
+
+ // Loose all details on properties when moving them around.
+ // Elements do not have special details like properties.
+ PropertyDetails no_details = PropertyDetails(NONE, NORMAL);
+
+ uint32_t pos = 0;
+ uint32_t undefs = 0;
+ for (int i = 0; i < capacity; i++) {
+ Object* k = dict->KeyAt(i);
+ if (dict->IsKey(k)) {
+ ASSERT(k->IsNumber());
+ ASSERT(!k->IsSmi() || Smi::cast(k)->value() >= 0);
+ ASSERT(!k->IsHeapNumber() || HeapNumber::cast(k)->value() >= 0);
+ ASSERT(!k->IsHeapNumber() || HeapNumber::cast(k)->value() <=
kMaxUInt32);
+ Object* value = dict->ValueAt(i);
+ uint32_t key = NumberToUint32(k);
+ if (key < limit) {
+ if (value->IsUndefined()) {
+ undefs++;
+ } else {
+ new_dict->AddNumberEntry(pos, value, no_details);
+ pos++;
+ }
+ } else {
+ new_dict->AddNumberEntry(key, value, no_details);
+ }
+ }
+ }
+
+ uint32_t result = pos;
+ while (undefs > 0) {
+ new_dict->AddNumberEntry(pos, Heap::undefined_value(), no_details);
+ pos++;
+ undefs--;
+ }
+
+ set_elements(new_dict);
+
+ if (result <= static_cast<uint32_t>(Smi::kMaxValue)) {
+ return Smi::FromInt(static_cast<int>(result));
+ }
+
+ ASSERT_NE(NULL, result_double);
+ result_double->set_value(static_cast<double>(result));
+ return result_double;
+}
+
+
+// Collects all defined (non-hole) and non-undefined (array) elements at
+// the start of the elements array.
+// If the object is in dictionary mode, it is converted to fast elements
+// mode.
+Object* JSObject::PrepareElementsForSort(uint32_t limit) {
+ if (!HasFastElements()) {
+ // Convert to fast elements containing only the existing properties.
+ // Ordering is irrelevant, since we are going to sort anyway.
+ Dictionary* dict = element_dictionary();
+ if (IsJSArray() || dict->requires_slow_elements() ||
+ dict->max_number_key() >= limit) {
+ return PrepareSlowElementsForSort(limit);
+ }
+ // Convert to fast elements.
+
+ PretenureFlag tenure = Heap::InNewSpace(this) ? NOT_TENURED: TENURED;
+ Object* new_array =
+ Heap::AllocateFixedArray(dict->NumberOfElements(), tenure);
+ if (new_array->IsFailure()) {
+ return new_array;
+ }
+ FixedArray* fast_elements = FixedArray::cast(new_array);
+ dict->CopyValuesTo(fast_elements);
+ set_elements(fast_elements);
+ }
+ ASSERT(HasFastElements());
+
+ // Collect holes at the end, undefined before that and the rest at the
+ // start, and return the number of non-hole, non-undefined values.
+
+ FixedArray* elements = this->elements();
+ uint32_t elements_length = static_cast<uint32_t>(elements->length());
+ if (limit > elements_length) {
+ limit = elements_length ;
+ }
+ if (limit == 0) {
+ return Smi::FromInt(0);
+ }
+
+ HeapNumber* result_double = NULL;
+ if (limit > static_cast<uint32_t>(Smi::kMaxValue)) {
+ // Pessimistically allocate space for return value before
+ // we start mutating the array.
+ Object* new_double = Heap::AllocateHeapNumber(0.0);
+ if (new_double->IsFailure()) return new_double;
+ result_double = HeapNumber::cast(new_double);
+ }
+
+ AssertNoAllocation no_alloc;
+
+ // Split elements into defined, undefined and the_hole, in that order.
+ // Only count locations for undefined and the hole, and fill them
afterwards.
+ WriteBarrierMode write_barrier = elements->GetWriteBarrierMode();
+ unsigned int undefs = limit;
+ unsigned int holes = limit;
+ // Assume most arrays contain no holes and undefined values, so minimize
the
+ // number of stores of non-undefined, non-the-hole values.
+ for (unsigned int i = 0; i < undefs; i++) {
+ Object* current = elements->get(i);
+ if (current->IsTheHole()) {
+ holes--;
+ undefs--;
+ } else if (current->IsUndefined()) {
+ undefs--;
+ } else {
+ continue;
+ }
+ // Position i needs to be filled.
+ while (undefs > i) {
+ current = elements->get(undefs);
+ if (current->IsTheHole()) {
+ holes--;
+ undefs--;
+ } else if (current->IsUndefined()) {
+ undefs--;
+ } else {
+ elements->set(i, current, write_barrier);
+ break;
+ }
+ }
+ }
+ uint32_t result = undefs;
+ while (undefs < holes) {
+ elements->set_undefined(undefs);
+ undefs++;
+ }
+ while (holes < limit) {
+ elements->set_the_hole(holes);
+ holes++;
+ }
+
+ if (result <= static_cast<uint32_t>(Smi::kMaxValue)) {
+ return Smi::FromInt(static_cast<int>(result));
+ }
+ ASSERT_NE(NULL, result_double);
+ result_double->set_value(static_cast<double>(result));
+ return result_double;
+}
Object* SymbolTable::LookupString(String* string, Object** s) {
Modified: branches/bleeding_edge/src/objects.h
==============================================================================
--- branches/bleeding_edge/src/objects.h (original)
+++ branches/bleeding_edge/src/objects.h Mon Apr 27 04:16:59 2009
@@ -1178,6 +1178,14 @@
inline bool HasFastElements();
inline Dictionary* element_dictionary(); // Gets slow elements.
+ // Collects elements starting at index 0.
+ // Undefined values are placed after non-undefined values.
+ // Returns the number of non-undefined values.
+ Object* PrepareElementsForSort(uint32_t limit);
+ // As PrepareElementsForSort, but only on objects where elements is
+ // a dictionary, and it will stay a dictionary.
+ Object* PrepareSlowElementsForSort(uint32_t limit);
+
Object* SetProperty(String* key,
Object* value,
PropertyAttributes attributes);
@@ -2008,7 +2016,6 @@
void RemoveNumberEntries(uint32_t from, uint32_t to);
// Sorting support
- Object* RemoveHoles();
void CopyValuesTo(FixedArray* elements);
// Casting.
@@ -3891,9 +3898,6 @@
// Set the content of the array to the content of storage.
inline void SetContent(FixedArray* storage);
-
- // Support for sorting
- Object* RemoveHoles();
// Casting.
static inline JSArray* cast(Object* obj);
Modified: branches/bleeding_edge/src/runtime.cc
==============================================================================
--- branches/bleeding_edge/src/runtime.cc (original)
+++ branches/bleeding_edge/src/runtime.cc Mon Apr 27 04:16:59 2009
@@ -5244,12 +5244,16 @@
return string;
}
-
+// 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.
static Object* Runtime_RemoveArrayHoles(Arguments args) {
- ASSERT(args.length() == 1);
- // Ignore the case if this is not a JSArray.
- if (!args[0]->IsJSArray()) return args[0];
- return JSArray::cast(args[0])->RemoveHoles();
+ ASSERT(args.length() == 2);
+ CONVERT_CHECKED(JSObject, object, args[0]);
+ CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
+ return object->PrepareElementsForSort(limit);
}
Modified: branches/bleeding_edge/src/runtime.h
==============================================================================
--- branches/bleeding_edge/src/runtime.h (original)
+++ branches/bleeding_edge/src/runtime.h Mon Apr 27 04:16:59 2009
@@ -205,7 +205,7 @@
F(IgnoreAttributesAndSetProperty, -1 /* 3 or 4 */) \
\
/* Arrays */ \
- F(RemoveArrayHoles, 1) \
+ F(RemoveArrayHoles, 2) \
F(GetArrayKeys, 2) \
F(MoveArrayContents, 2) \
F(EstimateNumberOfElements, 1) \
Modified: branches/bleeding_edge/test/mjsunit/array-sort.js
==============================================================================
--- branches/bleeding_edge/test/mjsunit/array-sort.js (original)
+++ branches/bleeding_edge/test/mjsunit/array-sort.js Mon Apr 27 04:16:59
2009
@@ -152,3 +152,60 @@
}
TestArraySortingWithUnsoundComparisonFunction();
+
+function TestSparseNonArraySorting(length) {
+ assertTrue(length > 101);
+ var obj = {length: length};
+ obj[0] = 42;
+ obj[10] = 37;
+ obj[100] = undefined;
+ obj[length - 1] = null;
+ Array.prototype.sort.call(obj);
+ assertEquals(length, obj.length, "objsort length unaffected");
+ assertEquals(37, obj[0], "objsort smallest number");
+ assertEquals(42, obj[1], "objsort largest number");
+ assertEquals(null, obj[2], "objsort null");
+ assertEquals(undefined, obj[3], "objsort undefined");
+ assertTrue(3 in obj, "objsort undefined retained");
+ assertFalse(4 in obj, "objsort non-existing retained");
+}
+
+TestSparseNonArraySorting(5000);
+TestSparseNonArraySorting(500000);
+TestSparseNonArraySorting(Math.pow(2, 31) + 1);
+
+function TestArrayLongerLength(length) {
+ var x = new Array(4);
+ x[0] = 42;
+ x[2] = 37;
+ x.length = length;
+ Array.prototype.sort.call(x);
+ assertEquals(length, x.length, "longlength length");
+ assertEquals(37, x[0], "longlength first");
+ assertEquals(42, x[1], "longlength second");
+ assertFalse(2 in x,"longlength third");
+}
+
+TestArrayLongerLength(4);
+TestArrayLongerLength(10);
+TestArrayLongerLength(1000);
+TestArrayLongerLength(500000);
+TestArrayLongerLength(Math.pow(2,32) - 1);
+
+function TestNonArrayLongerLength(length) {
+ var x = {};
+ x[0] = 42;
+ x[2] = 37;
+ x.length = length;
+ Array.prototype.sort.call(x);
+ assertEquals(length, x.length, "longlength length");
+ assertEquals(37, x[0], "longlength first");
+ assertEquals(42, x[1], "longlength second");
+ assertFalse(2 in x,"longlength third");
+}
+
+TestNonArrayLongerLength(4);
+TestNonArrayLongerLength(10);
+TestNonArrayLongerLength(1000);
+TestNonArrayLongerLength(500000);
+TestNonArrayLongerLength(Math.pow(2,32) - 1);
Added: branches/bleeding_edge/test/mjsunit/regress/regress-326.js
==============================================================================
--- (empty file)
+++ branches/bleeding_edge/test/mjsunit/regress/regress-326.js Mon Apr 27
04:16:59 2009
@@ -0,0 +1,40 @@
+// Copyright 2009 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Should not crash or raise an exception.
+// Should sort non-array into equivalent of [37,42,undefined,,0]
+
+var nonArray = { length: 4, 0: 42, 2: 37, 3: undefined, 4: 0 };
+Array.prototype.sort.call(nonArray);
+
+assertEquals(4, nonArray.length, "preserve length");
+assertEquals(37, nonArray[0], "sort smallest first");
+assertEquals(42, nonArray[1], "sort largest last");
+assertTrue(2 in nonArray, "don't delete undefined");
+assertEquals(undefined, nonArray[2], "sort undefined after largest");
+assertFalse(3 in nonArray, "don't create non-existing");
+assertEquals(0, nonArray[4], "don't affect after length.");
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
