Codify the assumption that %GetArrayKeys can return only a single interval starting at zero

src/array.js

 // Copyright 2012 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 22 matching lines @@
 
 // Global list of arrays visited during toString, toLocaleString and
 // join invocations.
 var visited_arrays = new InternalArray();
 
 
 // Gets a sorted array of array keys.  Useful for operations on sparse
 // arrays.  Dupes have not been removed.
 function GetSortedArrayKeys(array, intervals) {
   var length = intervals.length;
-  var keys = [];
-  for (var k = 0; k < length; k++) {
-    var key = intervals[k];
-    if (key < 0) {
-      var j = -1 - key;
-      var limit = j + intervals[++k];
-      for (; j < limit; j++) {
-        var e = array[j];
-        if (!IS_UNDEFINED(e) || j in array) {
-          keys.push(j);
-        }
+  var keys = new InternalArray();
+  if (length == 2 && intervals[0] == -1) {

[rossberg, 2013/03/28 12:27:07]

Nit: using === might be more accurate (and marginally more efficient). Same in
other places below.

[rossberg, 2013/03/28 12:27:07]

Do you actually need to test that length is 2? An index of -1 seems unambiguous
under the new invariant.

+    // It's an interval
+    var limit = intervals[1];
+    for (var i = 0; i < limit; ++i) {
+      var e = array[i];
+      if (!IS_UNDEFINED(e) || i in array) {
+        keys.push(i);
       }
-    } else {
-      // The case where key is undefined also ends here.
+    }
+  } else {
+    for (var k = 0; k < length; ++k) {
+      var key = intervals[k];
       if (!IS_UNDEFINED(key)) {
         var e = array[key];
         if (!IS_UNDEFINED(e) || key in array) {
           keys.push(key);
         }
       }
     }
+    %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
   }
-  %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
   return keys;
 }
 
 
 function SparseJoinWithSeparator(array, len, convert, separator) {
   var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
   var totalLength = 0;
   var elements = new InternalArray(keys.length * 2);
   var previousKey = -1;
   for (var i = 0; i < keys.length; i++) {
@@ skipping 137 matching lines @@
 }
 
 
 // This function implements the optimized splice implementation that can use
 // special array operations to handle sparse arrays in a sensible fashion.
 function SmartSlice(array, start_i, del_count, len, deleted_elements) {
   // Move deleted elements to a new array (the return value from splice).
   // Intervals array can contain keys and intervals.  See comment in Concat.
   var intervals = %GetArrayKeys(array, start_i + del_count);
   var length = intervals.length;
-  for (var k = 0; k < length; k++) {
-    var key = intervals[k];
-    if (key < 0) {
-      var j = -1 - key;
-      var interval_limit = j + intervals[++k];
-      if (j < start_i) {
-        j = start_i;
+  if (length == 2 && intervals[0] == -1) {
+    var interval_limit = intervals[1];
+    for (var i = start_i; i < interval_limit; ++i) {
+      var current = array[i];
+      if (!IS_UNDEFINED(current) || i in array) {
+        deleted_elements[i - start_i] = current;
       }
-      for (; j < interval_limit; j++) {
-        // ECMA-262 15.4.4.12 line 10.  The spec could also be
-        // interpreted such that %HasLocalProperty would be the
-        // appropriate test.  We follow KJS in consulting the
-        // prototype.
-        var current = array[j];
-        if (!IS_UNDEFINED(current) || j in array) {
-          deleted_elements[j - start_i] = current;
-        }
-      }
-    } else {
+    }
+  } else {
+    for (var k = 0; k < length; ++k) {
+      var key = intervals[k];
       if (!IS_UNDEFINED(key)) {
         if (key >= start_i) {
-          // ECMA-262 15.4.4.12 line 10.  The spec could also be
-          // interpreted such that %HasLocalProperty would be the
-          // appropriate test.  We follow KJS in consulting the
-          // prototype.
           var current = array[key];
           if (!IS_UNDEFINED(current) || key in array) {
             deleted_elements[key - start_i] = current;
           }
         }
       }
     }
   }
 }
 
 
 // This function implements the optimized splice implementation that can use
 // special array operations to handle sparse arrays in a sensible fashion.
 function SmartMove(array, start_i, del_count, len, num_additional_args) {
   // Move data to new array.
   var new_array = new InternalArray(len - del_count + num_additional_args);
   var intervals = %GetArrayKeys(array, len);
   var length = intervals.length;
-  for (var k = 0; k < length; k++) {
-    var key = intervals[k];
-    if (key < 0) {
-      var j = -1 - key;
-      var interval_limit = j + intervals[++k];
-      while (j < start_i && j < interval_limit) {
-        // The spec could also be interpreted such that
-        // %HasLocalProperty would be the appropriate test.  We follow
-        // KJS in consulting the prototype.
-        var current = array[j];
-        if (!IS_UNDEFINED(current) || j in array) {
-          new_array[j] = current;
-        }
-        j++;
+  if (length == 2 && intervals[0] == -1) {
+    var interval_limit = intervals[1];
+    for (var i = 0; i < start_i && i < interval_limit; ++i) {
+      var current = array[i];
+      if (!IS_UNDEFINED(current) || i in array) {
+        new_array[i] = current;
       }
-      j = start_i + del_count;
-      while (j < interval_limit) {
-        // ECMA-262 15.4.4.12 lines 24 and 41.  The spec could also be
-        // interpreted such that %HasLocalProperty would be the
-        // appropriate test.  We follow KJS in consulting the
-        // prototype.
-        var current = array[j];
-        if (!IS_UNDEFINED(current) || j in array) {
-          new_array[j - del_count + num_additional_args] = current;
-        }
-        j++;
+    }
+    for (var i = start_i + del_count; i < interval_limit; ++i) {
+      var current = array[i];
+      if (!IS_UNDEFINED(current) || i in array) {
+        new_array[i - del_count + num_additional_args] = current;
       }
-    } else {
+    }
+  } else {
+    for (var k = 0; k < length; ++k) {
+      var key = intervals[k];
       if (!IS_UNDEFINED(key)) {
         if (key < start_i) {
-          // The spec could also be interpreted such that
-          // %HasLocalProperty would be the appropriate test.  We follow
-          // KJS in consulting the prototype.
           var current = array[key];
           if (!IS_UNDEFINED(current) || key in array) {
             new_array[key] = current;
           }
         } else if (key >= start_i + del_count) {
-          // ECMA-262 15.4.4.12 lines 24 and 41.  The spec could also
-          // be interpreted such that %HasLocalProperty would be the
-          // appropriate test.  We follow KJS in consulting the
-          // prototype.
           var current = array[key];
           if (!IS_UNDEFINED(current) || key in array) {
             new_array[key - del_count + num_additional_args] = current;
           }
         }
       }
     }
   }
   // Move contents of new_array into this array
   %MoveArrayContents(new_array, array);
@@ skipping 562 matching lines @@
     }
   };
 
   // Copy elements in the range 0..length from obj's prototype chain
   // to obj itself, if obj has holes. Return one more than the maximal index
   // of a prototype property.
   var CopyFromPrototype = function CopyFromPrototype(obj, length) {
     var max = 0;
     for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(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; }
-            }
+      if (indices.length == 2 && 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; }
-            }
+        }
+      } 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.
   var ShadowPrototypeElements = function(obj, from, to) {
     for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(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;
-            }
+      if (indices.length == 2 && 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;
-            }
+        }
+      } 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 SafeRemoveArrayHoles = 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.
@@ skipping 331 matching lines @@
     if (index < 0) {
       index = length + index;
       // If index is still negative, search the entire array.
       if (index < 0) index = 0;
     }
   }
   var min = index;
   var max = length;
   if (UseSparseVariant(this, length, IS_ARRAY(this))) {
     var intervals = %GetArrayKeys(this, length);
-    if (intervals.length == 2 && intervals[0] < 0) {
+    if (intervals.length == 2 && intervals[0] == -1) {
       // A single interval.

[rossberg, 2013/03/28 12:27:07]

Nit: adjust comment ("An interval")

-      var intervalMin = -(intervals[0] + 1);
-      var intervalMax = intervalMin + intervals[1];
-      if (min < intervalMin) min = intervalMin;
-      max = intervalMax;  // Capped by length already.
+      max = intervals[1];  // Capped by length already.
       // Fall through to loop below.
     } else {
       if (intervals.length == 0) return -1;
       // Get all the keys in sorted order.
       var sortedKeys = GetSortedArrayKeys(this, intervals);
       var n = sortedKeys.length;
       var i = 0;
       while (i < n && sortedKeys[i] < index) i++;
       while (i < n) {
         var key = sortedKeys[i];
@@ skipping 35 matching lines @@
     // If index is negative, index from end of the array.
     if (index < 0) index += length;
     // If index is still negative, do not search the array.
     if (index < 0) return -1;
     else if (index >= length) index = length - 1;
   }
   var min = 0;
   var max = index;
   if (UseSparseVariant(this, length, IS_ARRAY(this))) {
     var intervals = %GetArrayKeys(this, index + 1);
-    if (intervals.length == 2 && intervals[0] < 0) {
+    if (intervals.length == 2 && intervals[0] == -1) {
       // A single interval.

[rossberg, 2013/03/28 12:27:07]

Same here

-      var intervalMin = -(intervals[0] + 1);
-      var intervalMax = intervalMin + intervals[1];
-      if (min < intervalMin) min = intervalMin;
-      max = intervalMax;  // Capped by index already.
+      max = intervals[1];  // Capped by index already.
       // Fall through to loop below.
     } else {
       if (intervals.length == 0) return -1;
       // Get all the keys in sorted order.
       var sortedKeys = GetSortedArrayKeys(this, intervals);
       var i = sortedKeys.length - 1;
       while (i >= 0) {
         var key = sortedKeys[i];
         if (!IS_UNDEFINED(key) && this[key] === element) return key;
         i--;
@@ skipping 197 matching lines @@
   ));
 
   SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
     "join", getFunction("join", ArrayJoin),
     "pop", getFunction("pop", ArrayPop),
     "push", getFunction("push", ArrayPush)
   ));
 }
 
 SetUpArray();