From 889eac7f13e0c61a32b3fc7632a4ae19749ce951 Mon Sep 17 00:00:00 2001 From: "lrn@chromium.org" Date: Mon, 27 Apr 2009 11:16:59 +0000 Subject: [PATCH] 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 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1800 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 27 +--- src/globals.h | 2 + src/objects.cc | 261 ++++++++++++++++++++++++++---------- src/objects.h | 12 +- src/runtime.cc | 14 +- src/runtime.h | 2 +- test/mjsunit/array-sort.js | 57 ++++++++ test/mjsunit/regress/regress-326.js | 40 ++++++ 8 files changed, 311 insertions(+), 104 deletions(-) create mode 100644 test/mjsunit/regress/regress-326.js diff --git a/src/array.js b/src/array.js index 0adbf9d..c01c0c8 100644 --- a/src/array.js +++ b/src/array.js @@ -709,33 +709,12 @@ function ArraySort(comparefn) { 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; } diff --git a/src/globals.h b/src/globals.h index fbbe7c9..d11ea67 100644 --- a/src/globals.h +++ b/src/globals.h @@ -86,6 +86,8 @@ const int GB = KB * KB * KB; 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 diff --git a/src/objects.cc b/src/objects.cc index 55fc971..4d01e85 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -2850,22 +2850,26 @@ static bool HasKey(FixedArray* array, Object* key) { 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 @@ Object* FixedArray::UnionOfKeys(FixedArray* other) { // 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 @@ Object* FixedArray::UnionOfKeys(FixedArray* other) { // 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 @@ bool JSObject::ShouldConvertToFastElements() { } -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()); @@ -6448,6 +6399,176 @@ template class HashTable<2, 3>; 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(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(Smi::kMaxValue)) { + return Smi::FromInt(static_cast(result)); + } + + ASSERT_NE(NULL, result_double); + result_double->set_value(static_cast(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(elements->length()); + if (limit > elements_length) { + limit = elements_length ; + } + if (limit == 0) { + return Smi::FromInt(0); + } + + HeapNumber* result_double = NULL; + if (limit > static_cast(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(Smi::kMaxValue)) { + return Smi::FromInt(static_cast(result)); + } + ASSERT_NE(NULL, result_double); + result_double->set_value(static_cast(result)); + return result_double; +} + + Object* SymbolTable::LookupString(String* string, Object** s) { SymbolKey key(string); return LookupKey(&key, s); diff --git a/src/objects.h b/src/objects.h index 8e76591..f3580f9 100644 --- a/src/objects.h +++ b/src/objects.h @@ -1178,6 +1178,14 @@ class JSObject: public HeapObject { 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 @@ class Dictionary: public DictionaryBase { void RemoveNumberEntries(uint32_t from, uint32_t to); // Sorting support - Object* RemoveHoles(); void CopyValuesTo(FixedArray* elements); // Casting. @@ -3892,9 +3899,6 @@ class JSArray: public JSObject { // 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); diff --git a/src/runtime.cc b/src/runtime.cc index a1e23b4..fd7e766 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -5244,12 +5244,16 @@ static Object* Runtime_GlobalPrint(Arguments args) { 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); } diff --git a/src/runtime.h b/src/runtime.h index b29ce70..9430073 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -205,7 +205,7 @@ namespace v8 { namespace internal { F(IgnoreAttributesAndSetProperty, -1 /* 3 or 4 */) \ \ /* Arrays */ \ - F(RemoveArrayHoles, 1) \ + F(RemoveArrayHoles, 2) \ F(GetArrayKeys, 2) \ F(MoveArrayContents, 2) \ F(EstimateNumberOfElements, 1) \ diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js index dfa4590..a3653d2 100644 --- a/test/mjsunit/array-sort.js +++ b/test/mjsunit/array-sort.js @@ -152,3 +152,60 @@ function TestArraySortingWithUnsoundComparisonFunction() { } 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); diff --git a/test/mjsunit/regress/regress-326.js b/test/mjsunit/regress/regress-326.js new file mode 100644 index 0000000..fcd102e --- /dev/null +++ b/test/mjsunit/regress/regress-326.js @@ -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."); -- 2.7.4