Author: [email protected]
Date: Wed Jun 10 04:42:22 2009
New Revision: 2133
Modified:
branches/bleeding_edge/src/array.js
branches/bleeding_edge/src/objects.cc
branches/bleeding_edge/src/objects.h
branches/bleeding_edge/test/mjsunit/array-sort.js
Log:
Make Array.sort safely generic on JSObject types. Fix bug 346
http://code.google.com/p/v8/issues/detail?id=346
Review URL: http://codereview.chromium.org/119357
Modified: branches/bleeding_edge/src/array.js
==============================================================================
--- branches/bleeding_edge/src/array.js (original)
+++ branches/bleeding_edge/src/array.js Wed Jun 10 04:42:22 2009
@@ -769,6 +769,63 @@
}
}
+ function SafeRemoveArrayHoles(obj) {
+ // Copy defined elements from the end to fill in all holes and
undefineds
+ // in the beginning of the array. Write undefineds and holes at the
end
+ // after loop is finished.
+ var first_undefined = 0;
+ var last_defined = length - 1;
+ var num_holes = 0;
+ while (first_undefined < last_defined) {
+ // Find first undefined element.
+ while (first_undefined < last_defined &&
+ !IS_UNDEFINED(obj[first_undefined])) {
+ first_undefined++;
+ }
+ // Maintain the invariant num_holes = the number of holes in the
original
+ // array with indices <= first_undefined or > last_defined.
+ if (!obj.hasOwnProperty(first_undefined)) {
+ num_holes++;
+ }
+
+ // Find last defined element.
+ while (first_undefined < last_defined &&
+ IS_UNDEFINED(obj[last_defined])) {
+ if (!obj.hasOwnProperty(last_defined)) {
+ num_holes++;
+ }
+ last_defined--;
+ }
+ if (first_undefined < last_defined) {
+ // Fill in hole or undefined.
+ obj[first_undefined] = obj[last_defined];
+ obj[last_defined] = void 0;
+ }
+ }
+ // If there were any undefineds in the entire array, first_undefined
+ // points to one past the last defined element. Make this true if
+ // there were no undefineds, as well, so that first_undefined == number
+ // of defined elements.
+ if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
+ // Fill in the undefineds and the holes. There may be a hole where
+ // an undefined should be and vice versa.
+ var i;
+ for (i = first_undefined; i < length - num_holes; i++) {
+ obj[i] = void 0;
+ }
+ for (i = length - num_holes; i < length; i++) {
+ // For compatability with Webkit, do not expose elements in the
prototype.
+ if (i in obj.__proto__) {
+ obj[i] = void 0;
+ } else {
+ delete obj[i];
+ }
+ }
+
+ // Return the number of defined elements.
+ return first_undefined;
+ }
+
var length = ToUint32(this.length);
if (length < 2) return this;
@@ -787,6 +844,12 @@
}
var num_non_undefined = %RemoveArrayHoles(this, length);
+ if (num_non_undefined == -1) {
+ // There were indexed accessors in the array. Move array holes and
+ // undefineds to the end using a Javascript function that is safe
+ // in the presence of accessors.
+ num_non_undefined = SafeRemoveArrayHoles(this);
+ }
QuickSort(this, 0, num_non_undefined);
Modified: branches/bleeding_edge/src/objects.cc
==============================================================================
--- branches/bleeding_edge/src/objects.cc (original)
+++ branches/bleeding_edge/src/objects.cc Wed Jun 10 04:42:22 2009
@@ -6436,10 +6436,6 @@
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++) {
@@ -6450,21 +6446,27 @@
ASSERT(!k->IsHeapNumber() || HeapNumber::cast(k)->value() >= 0);
ASSERT(!k->IsHeapNumber() || HeapNumber::cast(k)->value() <=
kMaxUInt32);
Object* value = dict->ValueAt(i);
+ PropertyDetails details = dict->DetailsAt(i);
+ if (details.type() == CALLBACKS) {
+ // Bail out and do the sorting of undefineds and array holes in JS.
+ return Smi::FromInt(-1);
+ }
uint32_t key = NumberToUint32(k);
if (key < limit) {
if (value->IsUndefined()) {
undefs++;
} else {
- new_dict->AddNumberEntry(pos, value, no_details);
+ new_dict->AddNumberEntry(pos, value, details);
pos++;
}
} else {
- new_dict->AddNumberEntry(key, value, no_details);
+ new_dict->AddNumberEntry(key, value, details);
}
}
}
uint32_t result = pos;
+ PropertyDetails no_details = PropertyDetails(NONE, NORMAL);
while (undefs > 0) {
new_dict->AddNumberEntry(pos, Heap::undefined_value(), no_details);
pos++;
Modified: branches/bleeding_edge/src/objects.h
==============================================================================
--- branches/bleeding_edge/src/objects.h (original)
+++ branches/bleeding_edge/src/objects.h Wed Jun 10 04:42:22 2009
@@ -2483,7 +2483,7 @@
return ((1 << kIsHiddenPrototype) & bit_field()) != 0;
}
- // Tells whether the instance has a named interceptor.
+ // Records and queries whether the instance has a named interceptor.
inline void set_has_named_interceptor() {
set_bit_field(bit_field() | (1 << kHasNamedInterceptor));
}
@@ -2492,7 +2492,7 @@
return ((1 << kHasNamedInterceptor) & bit_field()) != 0;
}
- // Tells whether the instance has a named interceptor.
+ // Records and queries whether the instance has an indexed interceptor.
inline void set_has_indexed_interceptor() {
set_bit_field(bit_field() | (1 << kHasIndexedInterceptor));
}
@@ -4021,10 +4021,9 @@
// If an accessor was found and it does not have a setter,
// the request is ignored.
//
-// To allow shadow an accessor property, the accessor can
-// have READ_ONLY property attribute so that a new value
-// is added to the local object to shadow the accessor
-// in prototypes.
+// If the accessor in the prototype has the READ_ONLY property attribute,
then
+// a new value is added to the local object when the property is set.
+// This shadows the accessor in the prototype.
class AccessorInfo: public Struct {
public:
DECL_ACCESSORS(getter, Object)
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 Wed Jun 10 04:42:22
2009
@@ -214,6 +214,30 @@
TestNonArrayLongerLength(Math.pow(2,32) - 1);
+function TestNonArrayWithAccessors() {
+ // Regression test for issue 346, more info at URL
+ // http://code.google.com/p/v8/issues/detail?id=346
+ // Reported by nth10sd, test based on this report.
+ var x = {};
+ x[0] = 42;
+ x.__defineGetter__("1", function(){return this.foo;});
+ x.__defineSetter__("1", function(val){this.foo = val;});
+ x[1] = 49
+ x[3] = 37;
+ x.length = 4;
+ Array.prototype.sort.call(x);
+ // Behavior of sort with accessors is undefined. This accessor is
+ // well-behaved (acts like a normal property), so it should work.
+ assertEquals(4, x.length, "sortaccessors length");
+ assertEquals(37, x[0], "sortaccessors first");
+ assertEquals(42, x[1], "sortaccessors second");
+ assertEquals(49, x[2], "sortaccessors third")
+ assertFalse(3 in x, "sortaccessors fourth");
+}
+
+TestNonArrayWithAccessors();
+
+
function TestInheritedElementSort(depth) {
var length = depth * 2 + 3;
var obj = {length: length};
@@ -268,7 +292,7 @@
assertEquals(i, y[i], name + "value" + i);
}
for (var i = 10; i < length; i++) {
- assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i),
+ assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i),
name + "hasundef" + i);
assertEquals(undefined, y[i], name+"undefined"+i);
if (x.hasOwnProperty(i)) {
@@ -282,7 +306,7 @@
TestSparseInheritedElementSort(1000);
function TestSpecialCasesInheritedElementSort() {
-
+
var x = {
1:"d1",
2:"c1",
@@ -309,11 +333,11 @@
}
};
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",
+ var sorted = ["a2", "a3", "b1", "b2", "c1", "c2", "d1", "d2", "e3",
undefined, undefined, undefined];
for (var i = 0; i < sorted.length; i++) {
assertTrue(x.hasOwnProperty(i), name + "has" + i)
@@ -321,7 +345,6 @@
}
assertFalse(x.hasOwnProperty(sorted.length), name + "haspost");
assertFalse(sorted.length in x, name + "haspost2");
-
assertTrue(x.hasOwnProperty(10), name + "hasundefined10");
assertEquals(undefined, x[10], name + "undefined10");
assertTrue(x.hasOwnProperty(100), name + "hasundefined100");
@@ -332,11 +355,8 @@
assertEquals(undefined, x[2000], name + "undefined2000");
assertTrue(x.hasOwnProperty(8000), name + "hasundefined8000");
assertEquals(undefined, x[8000], name + "undefined8000");
-
assertFalse(x.hasOwnProperty(12000), name + "has12000");
assertEquals("XX", x[12000], name + "XX12000");
-
}
TestSpecialCasesInheritedElementSort();
-
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
