Make Array.sort safely generic on JSObject types. Fix bug 346 http://code.go...

src/array.js

 // Copyright 2006-2008 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 751 matching lines @@
             if (!IS_UNDEFINED(index) && from <= index &&
                 proto.hasOwnProperty(index)) {
               obj[index] = void 0;
             }
           }
         }
       }
     }
   }
 
+  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;
 
   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);
+  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);
 
   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;
@@ skipping 246 matching lines @@
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1,
     ArrayReduce: 1,
     ArrayReduceRight: 1
   });
 }
 
 
 SetupArray();