Change the enumeration order for unsigned integer keys to always be...

src/objects.cc

 // Copyright 2006-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
@@ skipping 5119 matching lines @@
   } else if (!interceptor->getter()->IsUndefined()) {
     v8::IndexedPropertyGetter getter =
         v8::ToCData<v8::IndexedPropertyGetter>(interceptor->getter());
     LOG(ApiIndexedPropertyAccess("interceptor-indexed-has-get", this, index));
     v8::Handle<v8::Value> result;
     {
       // Leaving JavaScript.
       VMState state(EXTERNAL);
       result = getter(index, info);
     }
-    if (!result.IsEmpty()) return !result->IsUndefined();
+    if (!result.IsEmpty()) return true;

[Mads Ager (chromium), 2009/04/16 11:14:56]

I have no idea why we treated an undefined result from an indexed property
getter as not being present.  I guess layout tests might tell us.  Running them
now.

   }
   return holder_handle->HasElementPostInterceptor(*receiver_handle, index);
 }
 
 
 bool JSObject::HasLocalElement(uint32_t index) {
   // Check access rights if needed.
   if (IsAccessCheckNeeded() &&
       !Top::MayIndexedAccess(this, index, v8::ACCESS_HAS)) {
     Top::ReportFailedAccessCheck(this, v8::ACCESS_HAS);
@@ skipping 706 matching lines @@
     return property_dictionary()->NumberOfElementsFilterAttributes(filter);
   }
 }
 
 
 int JSObject::NumberOfEnumProperties() {
   return NumberOfLocalProperties(static_cast<PropertyAttributes>(DONT_ENUM));
 }
 
 
-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)) >

[Kasper Lund, 2009/04/16 11:22:04]

j-1 -> 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;
       }
       child_index = parent_index;
     }
   }
 
   // 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;
       }
     }
   }
 }
 
 
-// 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;
   }
 }
 
 
 // Fill in the names of local properties into the supplied storage. The main
 // purpose of this function is to provide reflection information for the object
 // mirrors.
 void JSObject::GetLocalPropertyNames(FixedArray* storage, int index) {
   ASSERT(storage->length() >=
@@ skipping 767 matching lines @@
   int pos = 0;
   for (int i = 0; i < capacity; i++) {
     if (IsKey(KeyAt(i))) {
       enumeration_order->set(pos++,
                              Smi::FromInt(DetailsAt(i).index()),
                              SKIP_WRITE_BARRIER);
     }
   }
 
   // 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++) {
     int index = Smi::cast(iteration_order->get(i))->value();
     int enum_index = PropertyDetails::kInitialIndex + i;
     enumeration_order->set(index,
                            Smi::FromInt(enum_index),
                            SKIP_WRITE_BARRIER);
   }
 
@@ skipping 231 matching lines @@
   ASSERT(storage->length() >= NumberOfEnumElements());
   int capacity = Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
      Object* k = KeyAt(i);
      if (IsKey(k)) {
        PropertyAttributes attr = DetailsAt(i).attributes();
        if ((attr & filter) == 0) storage->set(index++, k);
      }
   }
+  storage->SortPairs(storage, index);
   ASSERT(storage->length() >= index);
 }
 
 
 void Dictionary::CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array) {
   ASSERT(storage->length() >= NumberOfEnumElements());
   int capacity = Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
      Object* k = KeyAt(i);
      if (IsKey(k)) {
        PropertyDetails details = DetailsAt(i);
        if (!details.IsDontEnum()) {
          storage->set(index, k);
          sort_array->set(index,
                          Smi::FromInt(details.index()),
                          SKIP_WRITE_BARRIER);
          index++;
        }
      }
   }
-  storage->SortPairs(sort_array);
+  storage->SortPairs(sort_array, sort_array->length());
   ASSERT(storage->length() >= index);
 }
 
 
 void Dictionary::CopyKeysTo(FixedArray* storage) {
   ASSERT(storage->length() >= NumberOfElementsFilterAttributes(
       static_cast<PropertyAttributes>(NONE)));
   int capacity = Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
@@ skipping 370 matching lines @@
   // No break point.
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 
 
 } }  // namespace v8::internal