From 72294ca73568fa69559eed9f744605acb9b76b6f Mon Sep 17 00:00:00 2001 From: "ager@chromium.org" Date: Thu, 16 Apr 2009 11:30:55 +0000 Subject: [PATCH] Change the enumeration order for unsigned integer keys to always be numerical order independently of the representation of the object. Exchanged the order of enumeration of integer and string keys so integer keys are first instead of string keys to better match WebKit/JSC behavior. Added test cases that document our enumeration order choice. Review URL: http://codereview.chromium.org/75035 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1722 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/handles.cc | 30 +++++------ src/objects.cc | 89 +++++++++++++++---------------- src/objects.h | 14 +++-- test/cctest/test-api.cc | 67 +++++++++++++++++++---- test/mjsunit/enumeration-order.js | 60 +++++++++++++++++++-- 5 files changed, 180 insertions(+), 80 deletions(-) diff --git a/src/handles.cc b/src/handles.cc index 60d82362f..f97ccaa29 100644 --- a/src/handles.cc +++ b/src/handles.cc @@ -213,9 +213,9 @@ Handle SetProperty(Handle object, Handle IgnoreAttributesAndSetLocalProperty(Handle object, - Handle key, - Handle value, - PropertyAttributes attributes) { + Handle key, + Handle value, + PropertyAttributes attributes) { CALL_HEAP_FUNCTION(object-> IgnoreAttributesAndSetLocalProperty(*key, *value, attributes), Object); } @@ -491,17 +491,6 @@ Handle GetKeysInFixedArrayFor(Handle object) { break; } - // Compute the property keys. - content = UnionOfKeys(content, GetEnumPropertyKeys(current)); - - // Add the property keys from the interceptor. - if (current->HasNamedInterceptor()) { - v8::Handle result = - GetKeysForNamedInterceptor(object, current); - if (!result.IsEmpty()) - content = AddKeysFromJSArray(content, v8::Utils::OpenHandle(*result)); - } - // Compute the element keys. Handle element_keys = Factory::NewFixedArray(current->NumberOfEnumElements()); @@ -515,6 +504,17 @@ Handle GetKeysInFixedArrayFor(Handle object) { if (!result.IsEmpty()) content = AddKeysFromJSArray(content, v8::Utils::OpenHandle(*result)); } + + // Compute the property keys. + content = UnionOfKeys(content, GetEnumPropertyKeys(current)); + + // Add the property keys from the interceptor. + if (current->HasNamedInterceptor()) { + v8::Handle result = + GetKeysForNamedInterceptor(object, current); + if (!result.IsEmpty()) + content = AddKeysFromJSArray(content, v8::Utils::OpenHandle(*result)); + } } } return content; @@ -549,7 +549,7 @@ Handle GetEnumPropertyKeys(Handle object) { index++; } } - (*storage)->SortPairs(*sort_array); + (*storage)->SortPairs(*sort_array, sort_array->length()); Handle bridge_storage = Factory::NewFixedArray(DescriptorArray::kEnumCacheBridgeLength); DescriptorArray* desc = object->map()->instance_descriptors(); diff --git a/src/objects.cc b/src/objects.cc index 5ac0ee85b..22444b967 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -5121,7 +5121,7 @@ bool JSObject::HasElementWithInterceptor(JSObject* receiver, uint32_t index) { VMState state(EXTERNAL); result = getter(index, info); } - if (!result.IsEmpty()) return !result->IsUndefined(); + if (!result.IsEmpty()) return true; } return holder_handle->HasElementPostInterceptor(*receiver_handle, index); } @@ -5848,43 +5848,46 @@ int JSObject::NumberOfEnumProperties() { } -void FixedArray::Swap(int i, int j) { +void FixedArray::SwapPairs(FixedArray* numbers, int i, int j) { Object* temp = get(i); set(i, get(j)); set(j, temp); + if (this != numbers) { + temp = numbers->get(i); + numbers->set(i, numbers->get(j)); + numbers->set(j, temp); + } } -static void InsertionSortPairs(FixedArray* content, FixedArray* smis) { - int len = smis->length(); +static void InsertionSortPairs(FixedArray* content, + FixedArray* numbers, + int len) { for (int i = 1; i < len; i++) { int j = i; while (j > 0 && - Smi::cast(smis->get(j-1))->value() > - Smi::cast(smis->get(j))->value()) { - smis->Swap(j-1, j); - content->Swap(j-1, j); + (NumberToUint32(numbers->get(j - 1)) > + NumberToUint32(numbers->get(j)))) { + content->SwapPairs(numbers, j - 1, j); j--; } } } -void HeapSortPairs(FixedArray* content, FixedArray* smis) { +void HeapSortPairs(FixedArray* content, FixedArray* numbers, int len) { // In-place heap sort. - ASSERT(content->length() == smis->length()); - int len = smis->length(); + ASSERT(content->length() == numbers->length()); // Bottom-up max-heap construction. for (int i = 1; i < len; ++i) { int child_index = i; while (child_index > 0) { int parent_index = ((child_index + 1) >> 1) - 1; - int parent_value = Smi::cast(smis->get(parent_index))->value(); - int child_value = Smi::cast(smis->get(child_index))->value(); + uint32_t parent_value = NumberToUint32(numbers->get(parent_index)); + uint32_t child_value = NumberToUint32(numbers->get(child_index)); if (parent_value < child_value) { - content->Swap(parent_index, child_index); - smis->Swap(parent_index, child_index); + content->SwapPairs(numbers, parent_index, child_index); } else { break; } @@ -5895,25 +5898,22 @@ void HeapSortPairs(FixedArray* content, FixedArray* smis) { // Extract elements and create sorted array. for (int i = len - 1; i > 0; --i) { // Put max element at the back of the array. - content->Swap(0, i); - smis->Swap(0, i); + content->SwapPairs(numbers, 0, i); // Sift down the new top element. int parent_index = 0; while (true) { int child_index = ((parent_index + 1) << 1) - 1; if (child_index >= i) break; - uint32_t child1_value = Smi::cast(smis->get(child_index))->value(); - uint32_t child2_value = Smi::cast(smis->get(child_index + 1))->value(); - uint32_t parent_value = Smi::cast(smis->get(parent_index))->value(); + uint32_t child1_value = NumberToUint32(numbers->get(child_index)); + uint32_t child2_value = NumberToUint32(numbers->get(child_index + 1)); + uint32_t parent_value = NumberToUint32(numbers->get(parent_index)); if (child_index + 1 >= i || child1_value > child2_value) { if (parent_value > child1_value) break; - content->Swap(parent_index, child_index); - smis->Swap(parent_index, child_index); + content->SwapPairs(numbers, parent_index, child_index); parent_index = child_index; } else { if (parent_value > child2_value) break; - content->Swap(parent_index, child_index + 1); - smis->Swap(parent_index, child_index + 1); + content->SwapPairs(numbers, parent_index, child_index + 1); parent_index = child_index + 1; } } @@ -5921,43 +5921,41 @@ void HeapSortPairs(FixedArray* content, FixedArray* smis) { } -// Sort this array and the smis as pairs wrt. the (distinct) smis. -void FixedArray::SortPairs(FixedArray* smis) { - ASSERT(this->length() == smis->length()); - int len = smis->length(); +// Sort this array and the numbers as pairs wrt. the (distinct) numbers. +void FixedArray::SortPairs(FixedArray* numbers, uint32_t len) { + ASSERT(this->length() == numbers->length()); // For small arrays, simply use insertion sort. if (len <= 10) { - InsertionSortPairs(this, smis); + InsertionSortPairs(this, numbers, len); return; } // Check the range of indices. - int min_index = Smi::cast(smis->get(0))->value(); - int max_index = min_index; - int i; + uint32_t min_index = NumberToUint32(numbers->get(0)); + uint32_t max_index = min_index; + uint32_t i; for (i = 1; i < len; i++) { - if (Smi::cast(smis->get(i))->value() < min_index) { - min_index = Smi::cast(smis->get(i))->value(); - } else if (Smi::cast(smis->get(i))->value() > max_index) { - max_index = Smi::cast(smis->get(i))->value(); + if (NumberToUint32(numbers->get(i)) < min_index) { + min_index = NumberToUint32(numbers->get(i)); + } else if (NumberToUint32(numbers->get(i)) > max_index) { + max_index = NumberToUint32(numbers->get(i)); } } if (max_index - min_index + 1 == len) { // Indices form a contiguous range, unless there are duplicates. - // Do an in-place linear time sort assuming distinct smis, but + // Do an in-place linear time sort assuming distinct numbers, but // avoid hanging in case they are not. for (i = 0; i < len; i++) { - int p; - int j = 0; + uint32_t p; + uint32_t j = 0; // While the current element at i is not at its correct position p, // swap the elements at these two positions. - while ((p = Smi::cast(smis->get(i))->value() - min_index) != i && + while ((p = NumberToUint32(numbers->get(i)) - min_index) != i && j++ < len) { - this->Swap(i, p); - smis->Swap(i, p); + SwapPairs(numbers, i, p); } } } else { - HeapSortPairs(this, smis); + HeapSortPairs(this, numbers, len); return; } } @@ -6745,7 +6743,7 @@ Object* Dictionary::GenerateNewEnumerationIndices() { } // Sort the arrays wrt. enumeration order. - iteration_order->SortPairs(enumeration_order); + iteration_order->SortPairs(enumeration_order, enumeration_order->length()); // Overwrite the enumeration_order with the enumeration indices. for (int i = 0; i < length; i++) { @@ -6997,6 +6995,7 @@ void Dictionary::CopyKeysTo(FixedArray* storage, PropertyAttributes filter) { if ((attr & filter) == 0) storage->set(index++, k); } } + storage->SortPairs(storage, index); ASSERT(storage->length() >= index); } @@ -7018,7 +7017,7 @@ void Dictionary::CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array) { } } } - storage->SortPairs(sort_array); + storage->SortPairs(sort_array, sort_array->length()); ASSERT(storage->length() >= index); } diff --git a/src/objects.h b/src/objects.h index ade282be6..b12875e83 100644 --- a/src/objects.h +++ b/src/objects.h @@ -1585,11 +1585,15 @@ class FixedArray: public Array { bool IsEqualTo(FixedArray* other); #endif - // Swap two elements. - void Swap(int i, int j); - - // Sort this array and the smis as pairs wrt. the smis. - void SortPairs(FixedArray* smis); + // Swap two elements in a pair of arrays. If this array and the + // numbers array are the same object, the elements are only swapped + // once. + void SwapPairs(FixedArray* numbers, int i, int j); + + // Sort prefix of this array and the numbers array as pairs wrt. the + // numbers. If the numbers array and the this array are the same + // object, the prefix of this array is sorted. + void SortPairs(FixedArray* numbers, uint32_t len); protected: // Set operation on FixedArray without using write barriers. diff --git a/test/cctest/test-api.cc b/test/cctest/test-api.cc index 23e57d548..13185abf5 100644 --- a/test/cctest/test-api.cc +++ b/test/cctest/test-api.cc @@ -2925,7 +2925,19 @@ THREADED_TEST(Deleter) { static v8::Handle GetK(Local name, const AccessorInfo&) { ApiTestFuzzer::Fuzz(); - return v8::Undefined(); + if (name->Equals(v8_str("foo")) || + name->Equals(v8_str("bar")) || + name->Equals(v8_str("baz"))) { + return v8::Undefined(); + } + return v8::Handle(); +} + + +static v8::Handle IndexedGetK(uint32_t index, const AccessorInfo&) { + ApiTestFuzzer::Fuzz(); + if (index == 0 || index == 1) return v8::Undefined(); + return v8::Handle(); } @@ -2942,8 +2954,8 @@ static v8::Handle NamedEnum(const AccessorInfo&) { static v8::Handle IndexedEnum(const AccessorInfo&) { ApiTestFuzzer::Fuzz(); v8::Handle result = v8::Array::New(2); - result->Set(v8::Integer::New(0), v8_str("hat")); - result->Set(v8::Integer::New(1), v8_str("gyt")); + result->Set(v8::Integer::New(0), v8_str("0")); + result->Set(v8::Integer::New(1), v8_str("1")); return result; } @@ -2952,21 +2964,56 @@ THREADED_TEST(Enumerators) { v8::HandleScope scope; v8::Handle obj = ObjectTemplate::New(); obj->SetNamedPropertyHandler(GetK, NULL, NULL, NULL, NamedEnum); - obj->SetIndexedPropertyHandler(NULL, NULL, NULL, NULL, IndexedEnum); + obj->SetIndexedPropertyHandler(IndexedGetK, NULL, NULL, NULL, IndexedEnum); LocalContext context; context->Global()->Set(v8_str("k"), obj->NewInstance()); v8::Handle result = v8::Handle::Cast(CompileRun( + "k[10] = 0;" + "k.a = 0;" + "k[5] = 0;" + "k.b = 0;" + "k[4294967295] = 0;" + "k.c = 0;" + "k[4294967296] = 0;" + "k.d = 0;" + "k[140000] = 0;" + "k.e = 0;" + "k[30000000000] = 0;" + "k.f = 0;" "var result = [];" "for (var prop in k) {" " result.push(prop);" "}" "result")); - CHECK_EQ(5, result->Length()); - CHECK_EQ(v8_str("foo"), result->Get(v8::Integer::New(0))); - CHECK_EQ(v8_str("bar"), result->Get(v8::Integer::New(1))); - CHECK_EQ(v8_str("baz"), result->Get(v8::Integer::New(2))); - CHECK_EQ(v8_str("hat"), result->Get(v8::Integer::New(3))); - CHECK_EQ(v8_str("gyt"), result->Get(v8::Integer::New(4))); + // Check that we get all the property names returned including the + // ones from the enumerators in the right order: indexed properties + // in numerical order, indexed interceptor properties, named + // properties in insertion order, named interceptor properties. + // This order is not mandated by the spec, so this test is just + // documenting our behavior. + CHECK_EQ(17, result->Length()); + // Indexed properties in numerical order. + CHECK_EQ(v8_str("5"), result->Get(v8::Integer::New(0))); + CHECK_EQ(v8_str("10"), result->Get(v8::Integer::New(1))); + CHECK_EQ(v8_str("140000"), result->Get(v8::Integer::New(2))); + CHECK_EQ(v8_str("4294967295"), result->Get(v8::Integer::New(3))); + // Indexed interceptor properties in the order they are returned + // from the enumerator interceptor. + CHECK_EQ(v8_str("0"), result->Get(v8::Integer::New(4))); + CHECK_EQ(v8_str("1"), result->Get(v8::Integer::New(5))); + // Named properties in insertion order. + CHECK_EQ(v8_str("a"), result->Get(v8::Integer::New(6))); + CHECK_EQ(v8_str("b"), result->Get(v8::Integer::New(7))); + CHECK_EQ(v8_str("c"), result->Get(v8::Integer::New(8))); + CHECK_EQ(v8_str("4294967296"), result->Get(v8::Integer::New(9))); + CHECK_EQ(v8_str("d"), result->Get(v8::Integer::New(10))); + CHECK_EQ(v8_str("e"), result->Get(v8::Integer::New(11))); + CHECK_EQ(v8_str("30000000000"), result->Get(v8::Integer::New(12))); + CHECK_EQ(v8_str("f"), result->Get(v8::Integer::New(13))); + // Named interceptor properties. + CHECK_EQ(v8_str("foo"), result->Get(v8::Integer::New(14))); + CHECK_EQ(v8_str("bar"), result->Get(v8::Integer::New(15))); + CHECK_EQ(v8_str("baz"), result->Get(v8::Integer::New(16))); } diff --git a/test/mjsunit/enumeration-order.js b/test/mjsunit/enumeration-order.js index 699a636cc..a328121d7 100644 --- a/test/mjsunit/enumeration-order.js +++ b/test/mjsunit/enumeration-order.js @@ -26,17 +26,17 @@ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. function check_enumeration_order(obj) { - var value = 0; + var value = 0; for (var name in obj) assertTrue(value < obj[name]); value = obj[name]; } function make_object(size) { var a = new Object(); - + for (var i = 0; i < size; i++) a["a_" + i] = i + 1; check_enumeration_order(a); - + for (var i = 0; i < size; i +=3) delete a["a_" + i]; check_enumeration_order(a); } @@ -51,9 +51,59 @@ function make_literal_object(size) { code += "a_" + (size - 1) + " : " + size; code += " }"; eval("var a = " + code); - check_enumeration_order(a); + check_enumeration_order(a); } -// Validate the enumeration order for object literals up to 100 named properties. +// Validate the enumeration order for object literals up to 100 named +// properties. for (var j = 1; j< 100; j++) make_literal_object(j); +// We enumerate indexed properties in numerical order followed by +// named properties in insertion order, followed by indexed properties +// of the prototype object in numerical order, followed by named +// properties of the prototype object in insertion order, and so on. +// +// This enumeration order is not required by the specification, so +// this just documents our choice. +var proto2 = {}; +proto2[140000] = 0; +proto2.a = 0; +proto2[2] = 0; +proto2[3] = 0; // also on the 'proto1' object +proto2.b = 0; +proto2[4294967295] = 0; +proto2.c = 0; +proto2[4294967296] = 0; + +var proto1 = {}; +proto1[5] = 0; +proto1.d = 0; +proto1[3] = 0; +proto1.e = 0; +proto1.f = 0; // also on the 'o' object + +var o = {}; +o[-23] = 0; +o[300000000000] = 0; +o[23] = 0; +o.f = 0; +o.g = 0; +o[-4] = 0; +o[42] = 0; + +o.__proto__ = proto1; +proto1.__proto__ = proto2; + +var expected = ['23', '42', // indexed from 'o' + '-23', '300000000000', 'f', 'g', '-4', // named from 'o' + '3', '5', // indexed from 'proto1' + 'd', 'e', // named from 'proto1' + '2', '140000', '4294967295', // indexed from 'proto2' + 'a', 'b', 'c', '4294967296']; // named from 'proto2' +var actual = []; +for (var p in o) actual.push(p); +assertArrayEquals(expected, actual); + + + + -- 2.34.1