Add sparse array handling to Array.protoype.indexOf/lastIndexOf.

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 946 matching lines @@
   if (length == 0) return -1;
   if (IS_UNDEFINED(index)) {
     index = 0;
   } else {
     index = TO_INTEGER(index);
     // If index is negative, index from the end of the array.
     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, true)) {
+    var intervals = %GetArrayKeys(this, length);
+    if (intervals.length == 2 && intervals[0] < 0) {
+      // A single interval.
+      var intervalMin = -(intervals[0] + 1);
+      var intervalMax = intervalMin + intervals[1];
+      min = MAX(min, intervalMin);
+      max = intervalMax;  // 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];
+        if (!IS_UNDEFINED(key) && this[key] === element) return key;
+        i++;
+      }
+      return -1;
+    }
+  }
   // Lookup through the array.
   if (!IS_UNDEFINED(element)) {
-    for (var i = index; i < length; i++) {
+    for (var i = min; i < max; i++) {
       if (this[i] === element) return i;
     }
     return -1;
   }
-  for (var i = index; i < length; i++) {
+  // Lookup through the array.
+  for (var i = min; i < max; i++) {
     if (IS_UNDEFINED(this[i]) && i in this) {
       return i;
     }
   }
   return -1;
 }
 
 
 function ArrayLastIndexOf(element, index) {
   var length = TO_UINT32(this.length);
   if (length == 0) return -1;
   if (%_ArgumentsLength() < 2) {
     index = length - 1;
   } else {
     index = TO_INTEGER(index);
     // If index is negative, index from end of the array.
-    if (index < 0) index = length + index;
+    if (index < 0) index += length;
     // If index is still negative, do not search the array.
-    if (index < 0) index = -1;
+    if (index < 0) return -1;
     else if (index >= length) index = length - 1;
   }
+  var min = 0;
+  var max = index;
+  if (UseSparseVariant(this, length, true)) {
+    var intervals = %GetArrayKeys(this, index + 1);
+    if (intervals.length == 2 && intervals[0] < 0) {
+      // A single interval.
+      var intervalMin = -(intervals[0] + 1);
+      var intervalMax = intervalMin + intervals[1];
+      min = MAX(min, intervalMin);
+      max = intervalMax;  // 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--;
+      }
+      return -1;
+    }
+  }
   // Lookup through the array.
   if (!IS_UNDEFINED(element)) {
-    for (var i = index; i >= 0; i--) {
+    for (var i = max; i >= min; i--) {
       if (this[i] === element) return i;
     }
     return -1;
   }
-  for (var i = index; i >= 0; i--) {
+  for (var i = max; i >= min; i--) {
     if (IS_UNDEFINED(this[i]) && i in this) {
       return i;
     }
   }
   return -1;
 }
 
 
 function ArrayReduce(callback, current) {
   if (!IS_FUNCTION(callback)) {
@@ skipping 106 matching lines @@
     "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
     "reduce", getFunction("reduce", ArrayReduce, 1),
     "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
   ));
 
   %FinishArrayPrototypeSetup($Array.prototype);
 }
 
 
 SetupArray();