From 83d1d02df7fa65e3e15ab8faddbfc12bc7b2505a Mon Sep 17 00:00:00 2001 From: "lrn@chromium.org" Date: Fri, 1 May 2009 10:06:55 +0000 Subject: [PATCH] Made sort on non-arrays also affect elements on the prototype, for JSC compatability. Made sort on non-objects with inherited elements JSC compatible. Review URL: http://codereview.chromium.org/99272 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1829 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 80 ++++++++++++++++++++++++++++ src/runtime.cc | 7 +-- test/mjsunit/array-sort.js | 129 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 213 insertions(+), 3 deletions(-) diff --git a/src/array.js b/src/array.js index c01c0c8..bee73e4 100644 --- a/src/array.js +++ b/src/array.js @@ -709,13 +709,93 @@ function ArraySort(comparefn) { QuickSort(a, high_start, to); } + // Copies elements in the range 0..length from obj's prototype chain + // to obj itself, if obj has holes. Returns one more than the maximal index + // of a prototype property. + function CopyFromPrototype(obj, length) { + var max = 0; + for (var proto = obj.__proto__; proto; proto = proto.__proto__) { + var indices = %GetArrayKeys(proto, length); + if (indices.length > 0) { + if (indices[0] == -1) { + // It's an interval. + var proto_length = indices[1]; + for (var i = 0; i < proto_length; i++) { + if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { + obj[i] = proto[i]; + if (i >= max) { max = i + 1; } + } + } + } else { + for (var i = 0; i < indices.length; i++) { + var index = indices[i]; + if (!IS_UNDEFINED(index) && + !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { + obj[index] = proto[index]; + if (index >= max) { max = index + 1; } + } + } + } + } + } + return max; + } + + // Set a value of "undefined" on all indices in the range from..to + // where a prototype of obj has an element. I.e., shadow all prototype + // elements in that range. + function ShadowPrototypeElements(obj, from, to) { + for (var proto = obj.__proto__; proto; proto = proto.__proto__) { + var indices = %GetArrayKeys(proto, to); + if (indices.length > 0) { + if (indices[0] == -1) { + // It's an interval. + var proto_length = indices[1]; + for (var i = from; i < proto_length; i++) { + if (proto.hasOwnProperty(i)) { + obj[i] = void 0; + } + } + } else { + for (var i = 0; i < indices.length; i++) { + var index = indices[i]; + if (!IS_UNDEFINED(index) && from <= index && + proto.hasOwnProperty(index)) { + obj[index] = void 0; + } + } + } + } + } + } + var length = ToUint32(this.length); if (length < 2) return this; + var is_array = IS_ARRAY(this); + var max_prototype_element; + if (!is_array) { + // For compatibility with JSC, we also sort elements inherited from + // the prototype chain on non-Array objects. + // We do this by copying them to this object and sorting only + // local elements. This is not very efficient, but sorting with + // inherited elements happens very, very rarely, if at all. + // The specification allows "implementation dependent" behavior + // if an element on the prototype chain has an element that + // might interact with sorting. + max_prototype_element = CopyFromPrototype(this, length); + } + var num_non_undefined = %RemoveArrayHoles(this, length); QuickSort(this, 0, num_non_undefined); + if (!is_array && (num_non_undefined + 1 < max_prototype_element)) { + // For compatibility with JSC, we shadow any elements in the prototype + // chain that has become exposed by sort moving a hole to its position. + ShadowPrototypeElements(this, num_non_undefined, max_prototype_element); + } + return this; } diff --git a/src/runtime.cc b/src/runtime.cc index fd7e766..29656dd 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -5289,8 +5289,7 @@ static Object* Runtime_EstimateNumberOfElements(Arguments args) { static Object* Runtime_GetArrayKeys(Arguments args) { ASSERT(args.length() == 2); HandleScope scope; - CONVERT_CHECKED(JSArray, raw_array, args[0]); - Handle array(raw_array); + CONVERT_ARG_CHECKED(JSObject, array, 0); CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]); if (array->elements()->IsDictionary()) { // Create an array and get all the keys into it, then remove all the @@ -5312,8 +5311,10 @@ static Object* Runtime_GetArrayKeys(Arguments args) { single_interval->set(0, Smi::FromInt(-1), SKIP_WRITE_BARRIER); + uint32_t actual_length = static_cast(array->elements()->length()); + uint32_t min_length = actual_length < length ? actual_length : length; Handle length_object = - Factory::NewNumber(static_cast(length)); + Factory::NewNumber(static_cast(min_length)); single_interval->set(1, *length_object); return *Factory::NewJSArrayWithElements(single_interval); } diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js index a3653d2..a4ef001 100644 --- a/test/mjsunit/array-sort.js +++ b/test/mjsunit/array-sort.js @@ -209,3 +209,132 @@ TestNonArrayLongerLength(10); TestNonArrayLongerLength(1000); TestNonArrayLongerLength(500000); TestNonArrayLongerLength(Math.pow(2,32) - 1); + + +function TestInheritedElementSort(depth) { + var length = depth * 2 + 3; + var obj = {length: length}; + obj[depth * 2 + 1] = 0; + for (var i = 0; i < depth; i++) { + var newObj = {}; + newObj.__proto__ = obj; + obj[i] = undefined; + obj[i + depth + 1] = depth - i; + obj = newObj; + } + // expected (inherited) object: [undef1,...undefdepth,hole,1,...,depth,0,hole] + + Array.prototype.sort.call(obj, function(a,b) { return (b < a) - (a < b); }); + // expected result: [0,1,...,depth,undef1,...,undefdepth,undef,hole] + var name = "SortInherit("+depth+")-"; + + assertEquals(length, obj.length, name+"length"); + for (var i = 0; i <= depth; i++) { + assertTrue(obj.hasOwnProperty(i), name + "hasvalue" + i); + assertEquals(i, obj[i], name + "value" + i); + } + for (var i = depth + 1; i <= depth * 2 + 1; i++) { + assertEquals(undefined, obj[i], name + "undefined" + i); + assertTrue(obj.hasOwnProperty(i), name + "hasundefined" + i); + } + assertTrue(!obj.hasOwnProperty(depth * 2 + 2), name + "hashole"); +} + +TestInheritedElementSort(5); +TestInheritedElementSort(15); + +function TestSparseInheritedElementSort(scale) { + var length = scale * 10; + var x = {length: length}; + var y = {}; + y.__proto__ = x; + + for (var i = 0; i < 5; i++) { + x[i * 2 * scale] = 2 * (4 - i); + y[(i * 2 + 1) * scale] = 2 * (4 - i) + 1; + } + + var name = "SparseSortInherit(" + scale + ")-"; + + Array.prototype.sort.call(y); + + assertEquals(length, y.length, name+"length"); + + for (var i = 0; i < 10; i++) { + assertTrue(y.hasOwnProperty(i), name + "hasvalue" + i); + assertEquals(i, y[i], name + "value" + i); + } + for (var i = 10; i < length; i++) { + assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i), name+"hasundef"+i); + assertEquals(undefined, y[i], name+"undefined"+i); + if (x.hasOwnProperty(i)) { + assertTrue(0 == i % (2 * scale), name+"new_x"+i); + } + } +} + +TestSparseInheritedElementSort(10); +TestSparseInheritedElementSort(100); +TestSparseInheritedElementSort(1000); +TestSparseInheritedElementSort(10000); + +function TestSpecialCasesInheritedElementSort() { + + var x = { + 1:"d1", + 2:"c1", + 3:"b1", + 4: undefined, + __proto__: { + length: 10000, + 1: "e2", + 10: "a2", + 100: "b2", + 1000: "c2", + 2000: undefined, + 8000: "d2", + 12000: "XX", + __proto__: { + 0: "e3", + 1: "d3", + 2: "c3", + 3: "b3", + 4: "f3", + 5: "a3", + 6: undefined, + } + } + }; + Array.prototype.sort.call(x); + + var name = "SpecialInherit-"; + + assertEquals(10000, x.length, name + "length"); + var sorted = ["a2", "a3", "b1", "b2", "c1", "c2", "d1", "d2", "e3", + undefined, undefined, undefined]; + for (var i = 0; i < sorted.length; i++) { + assertTrue(x[0], x.hasOwnProperty(i) + "has" + i) + assertEquals(sorted[i], x[i], name + i); + } + assertFalse(x.hasOwnProperty(sorted.length), name + "haspost"); + assertFalse(sorted.length in x, name + "haspost2"); + assertEquals(undefined, x[12000], name + "XX12000"); + + assertTrue(x.hasOwnProperty(10), name + "hasundefined10"); + assertEquals(undefined, x[10], name + "undefined10"); + assertTrue(x.hasOwnProperty(100), name + "hasundefined100"); + assertEquals(undefined, x[100], name + "undefined100"); + assertTrue(x.hasOwnProperty(1000), name + "hasundefined1000"); + assertEquals(undefined, x[1000], name + "undefined1000"); + assertTrue(x.hasOwnProperty(2000), name + "hasundefined2000"); + assertEquals(undefined, x[2000], name + "undefined2000"); + assertTrue(x.hasOwnProperty(8000), name + "hasundefined8000"); + assertEquals(undefined, x[8000], name + "undefined8000"); + + assertFalse(x.hasOwnProperty(11), name + "hasundefined11"); + assertEquals(undefined, x[11], name + "undefined11"); + + assertFalse(x.hasOwnProperty(12000), name + "has12000"); + assertEquals("XX", x[12000], name + "XX12000"); + +} \ No newline at end of file -- 2.7.4