src/array.js

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 (function(global, utils) {
   6
   7 "use strict";
   8
   9 %CheckIsBootstrapping();
  10
  11 // -------------------------------------------------------------------
  12 // Imports
  13
  14 var Delete;
  15 var GlobalArray = global.Array;
  16 var InternalArray = utils.InternalArray;
  17 var InternalPackedArray = utils.InternalPackedArray;
  18 var MathMin;
  19 var ObjectHasOwnProperty;
  20 var ObjectIsFrozen;
  21 var ObjectIsSealed;
  22 var ObjectToString;
  23 var ToNumber;
  24 var ToString;
  25 var unscopablesSymbol = utils.ImportNow("unscopables_symbol");
  26
  27 utils.Import(function(from) {
  28   Delete = from.Delete;
  29   MathMin = from.MathMin;
  30   ObjectHasOwnProperty = from.ObjectHasOwnProperty;
  31   ObjectIsFrozen = from.ObjectIsFrozen;
  32   ObjectIsSealed = from.ObjectIsSealed;
  33   ObjectToString = from.ObjectToString;
  34   ToNumber = from.ToNumber;
  35   ToString = from.ToString;
  36 });
  37
  38 // -------------------------------------------------------------------
  39
  40 // Global list of arrays visited during toString, toLocaleString and
  41 // join invocations.
  42 var visited_arrays = new InternalArray();
  43
  44
  45 // Gets a sorted array of array keys.  Useful for operations on sparse
  46 // arrays.  Dupes have not been removed.
  47 function GetSortedArrayKeys(array, indices) {
  48   var keys = new InternalArray();
  49   if (IS_NUMBER(indices)) {
  50     // It's an interval
  51     var limit = indices;
  52     for (var i = 0; i < limit; ++i) {
  53       var e = array[i];
  54       if (!IS_UNDEFINED(e) || i in array) {
  55         keys.push(i);
  56       }
  57     }
  58   } else {
  59     var length = indices.length;
  60     for (var k = 0; k < length; ++k) {
  61       var key = indices[k];
  62       if (!IS_UNDEFINED(key)) {
  63         var e = array[key];
  64         if (!IS_UNDEFINED(e) || key in array) {
  65           keys.push(key);
  66         }
  67       }
  68     }
  69     keys.sort(function(a, b) { return a - b; });
  70   }
  71   return keys;
  72 }
  73
  74
  75 function SparseJoinWithSeparatorJS(array, len, convert, separator) {
  76   var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
  77   var totalLength = 0;
  78   var elements = new InternalArray(keys.length * 2);
  79   var previousKey = -1;
  80   for (var i = 0; i < keys.length; i++) {
  81     var key = keys[i];
  82     if (key != previousKey) {  // keys may contain duplicates.
  83       var e = array[key];
  84       if (!IS_STRING(e)) e = convert(e);
  85       elements[i * 2] = key;
  86       elements[i * 2 + 1] = e;
  87       previousKey = key;
  88     }
  89   }
  90   return %SparseJoinWithSeparator(elements, len, separator);
  91 }
  92
  93
  94 // Optimized for sparse arrays if separator is ''.
  95 function SparseJoin(array, len, convert) {
  96   var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
  97   var last_key = -1;
  98   var keys_length = keys.length;
  99
 100   var elements = new InternalArray(keys_length);
 101   var elements_length = 0;
 102
 103   for (var i = 0; i < keys_length; i++) {
 104     var key = keys[i];
 105     if (key != last_key) {
 106       var e = array[key];
 107       if (!IS_STRING(e)) e = convert(e);
 108       elements[elements_length++] = e;
 109       last_key = key;
 110     }
 111   }
 112   return %StringBuilderConcat(elements, elements_length, '');
 113 }
 114
 115
 116 function UseSparseVariant(array, length, is_array, touched) {
 117   // Only use the sparse variant on arrays that are likely to be sparse and the
 118   // number of elements touched in the operation is relatively small compared to
 119   // the overall size of the array.
 120   if (!is_array || length < 1000 || %IsObserved(array) ||
 121       %HasComplexElements(array)) {
 122     return false;
 123   }
 124   if (!%_IsSmi(length)) {
 125     return true;
 126   }
 127   var elements_threshold = length >> 2;  // No more than 75% holes
 128   var estimated_elements = %EstimateNumberOfElements(array);
 129   return (estimated_elements < elements_threshold) &&
 130     (touched > estimated_elements * 4);
 131 }
 132
 133
 134 function Join(array, length, separator, convert) {
 135   if (length == 0) return '';
 136
 137   var is_array = IS_ARRAY(array);
 138
 139   if (is_array) {
 140     // If the array is cyclic, return the empty string for already
 141     // visited arrays.
 142     if (!%PushIfAbsent(visited_arrays, array)) return '';
 143   }
 144
 145   // Attempt to convert the elements.
 146   try {
 147     if (UseSparseVariant(array, length, is_array, length)) {
 148       %NormalizeElements(array);
 149       if (separator.length == 0) {
 150         return SparseJoin(array, length, convert);
 151       } else {
 152         return SparseJoinWithSeparatorJS(array, length, convert, separator);
 153       }
 154     }
 155
 156     // Fast case for one-element arrays.
 157     if (length == 1) {
 158       var e = array[0];
 159       if (IS_STRING(e)) return e;
 160       return convert(e);
 161     }
 162
 163     // Construct an array for the elements.
 164     var elements = new InternalArray(length);
 165
 166     // We pull the empty separator check outside the loop for speed!
 167     if (separator.length == 0) {
 168       var elements_length = 0;
 169       for (var i = 0; i < length; i++) {
 170         var e = array[i];
 171         if (!IS_STRING(e)) e = convert(e);
 172         elements[elements_length++] = e;
 173       }
 174       elements.length = elements_length;
 175       var result = %_FastOneByteArrayJoin(elements, '');
 176       if (!IS_UNDEFINED(result)) return result;
 177       return %StringBuilderConcat(elements, elements_length, '');
 178     }
 179     // Non-empty separator case.
 180     // If the first element is a number then use the heuristic that the
 181     // remaining elements are also likely to be numbers.
 182     if (!IS_NUMBER(array[0])) {
 183       for (var i = 0; i < length; i++) {
 184         var e = array[i];
 185         if (!IS_STRING(e)) e = convert(e);
 186         elements[i] = e;
 187       }
 188     } else {
 189       for (var i = 0; i < length; i++) {
 190         var e = array[i];
 191         if (IS_NUMBER(e)) {
 192           e = %_NumberToString(e);
 193         } else if (!IS_STRING(e)) {
 194           e = convert(e);
 195         }
 196         elements[i] = e;
 197       }
 198     }
 199     var result = %_FastOneByteArrayJoin(elements, separator);
 200     if (!IS_UNDEFINED(result)) return result;
 201
 202     return %StringBuilderJoin(elements, length, separator);
 203   } finally {
 204     // Make sure to remove the last element of the visited array no
 205     // matter what happens.
 206     if (is_array) visited_arrays.length = visited_arrays.length - 1;
 207   }
 208 }
 209
 210
 211 function ConvertToString(x) {
 212   // Assumes x is a non-string.
 213   if (IS_NUMBER(x)) return %_NumberToString(x);
 214   if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
 215   return (IS_NULL_OR_UNDEFINED(x)) ? '' : ToString($defaultString(x));
 216 }
 217
 218
 219 function ConvertToLocaleString(e) {
 220   if (IS_NULL_OR_UNDEFINED(e)) {
 221     return '';
 222   } else {
 223     // According to ES5, section 15.4.4.3, the toLocaleString conversion
 224     // must throw a TypeError if ToObject(e).toLocaleString isn't
 225     // callable.
 226     var e_obj = TO_OBJECT(e);
 227     return ToString(e_obj.toLocaleString());
 228   }
 229 }
 230
 231
 232 // This function implements the optimized splice implementation that can use
 233 // special array operations to handle sparse arrays in a sensible fashion.
 234 function SparseSlice(array, start_i, del_count, len, deleted_elements) {
 235   // Move deleted elements to a new array (the return value from splice).
 236   var indices = %GetArrayKeys(array, start_i + del_count);
 237   if (IS_NUMBER(indices)) {
 238     var limit = indices;
 239     for (var i = start_i; i < limit; ++i) {
 240       var current = array[i];
 241       if (!IS_UNDEFINED(current) || i in array) {
 242         %AddElement(deleted_elements, i - start_i, current);
 243       }
 244     }
 245   } else {
 246     var length = indices.length;
 247     for (var k = 0; k < length; ++k) {
 248       var key = indices[k];
 249       if (!IS_UNDEFINED(key)) {
 250         if (key >= start_i) {
 251           var current = array[key];
 252           if (!IS_UNDEFINED(current) || key in array) {
 253             %AddElement(deleted_elements, key - start_i, current);
 254           }
 255         }
 256       }
 257     }
 258   }
 259 }
 260
 261
 262 // This function implements the optimized splice implementation that can use
 263 // special array operations to handle sparse arrays in a sensible fashion.
 264 function SparseMove(array, start_i, del_count, len, num_additional_args) {
 265   // Bail out if no moving is necessary.
 266   if (num_additional_args === del_count) return;
 267   // Move data to new array.
 268   var new_array = new InternalArray(
 269       // Clamp array length to 2^32-1 to avoid early RangeError.
 270       MathMin(len - del_count + num_additional_args, 0xffffffff));
 271   var big_indices;
 272   var indices = %GetArrayKeys(array, len);
 273   if (IS_NUMBER(indices)) {
 274     var limit = indices;
 275     for (var i = 0; i < start_i && i < limit; ++i) {
 276       var current = array[i];
 277       if (!IS_UNDEFINED(current) || i in array) {
 278         new_array[i] = current;
 279       }
 280     }
 281     for (var i = start_i + del_count; i < limit; ++i) {
 282       var current = array[i];
 283       if (!IS_UNDEFINED(current) || i in array) {
 284         new_array[i - del_count + num_additional_args] = current;
 285       }
 286     }
 287   } else {
 288     var length = indices.length;
 289     for (var k = 0; k < length; ++k) {
 290       var key = indices[k];
 291       if (!IS_UNDEFINED(key)) {
 292         if (key < start_i) {
 293           var current = array[key];
 294           if (!IS_UNDEFINED(current) || key in array) {
 295             new_array[key] = current;
 296           }
 297         } else if (key >= start_i + del_count) {
 298           var current = array[key];
 299           if (!IS_UNDEFINED(current) || key in array) {
 300             var new_key = key - del_count + num_additional_args;
 301             new_array[new_key] = current;
 302             if (new_key > 0xfffffffe) {
 303               big_indices = big_indices || new InternalArray();
 304               big_indices.push(new_key);
 305             }
 306           }
 307         }
 308       }
 309     }
 310   }
 311   // Move contents of new_array into this array
 312   %MoveArrayContents(new_array, array);
 313   // Add any moved values that aren't elements anymore.
 314   if (!IS_UNDEFINED(big_indices)) {
 315     var length = big_indices.length;
 316     for (var i = 0; i < length; ++i) {
 317       var key = big_indices[i];
 318       array[key] = new_array[key];
 319     }
 320   }
 321 }
 322
 323
 324 // This is part of the old simple-minded splice.  We are using it either
 325 // because the receiver is not an array (so we have no choice) or because we
 326 // know we are not deleting or moving a lot of elements.
 327 function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
 328   var is_array = IS_ARRAY(array);
 329   for (var i = 0; i < del_count; i++) {
 330     var index = start_i + i;
 331     if (HAS_INDEX(array, index, is_array)) {
 332       var current = array[index];
 333       // The spec requires [[DefineOwnProperty]] here, %AddElement is close
 334       // enough (in that it ignores the prototype).
 335       %AddElement(deleted_elements, i, current);
 336     }
 337   }
 338 }
 339
 340
 341 function SimpleMove(array, start_i, del_count, len, num_additional_args) {
 342   var is_array = IS_ARRAY(array);
 343   if (num_additional_args !== del_count) {
 344     // Move the existing elements after the elements to be deleted
 345     // to the right position in the resulting array.
 346     if (num_additional_args > del_count) {
 347       for (var i = len - del_count; i > start_i; i--) {
 348         var from_index = i + del_count - 1;
 349         var to_index = i + num_additional_args - 1;
 350         if (HAS_INDEX(array, from_index, is_array)) {
 351           array[to_index] = array[from_index];
 352         } else {
 353           delete array[to_index];
 354         }
 355       }
 356     } else {
 357       for (var i = start_i; i < len - del_count; i++) {
 358         var from_index = i + del_count;
 359         var to_index = i + num_additional_args;
 360         if (HAS_INDEX(array, from_index, is_array)) {
 361           array[to_index] = array[from_index];
 362         } else {
 363           delete array[to_index];
 364         }
 365       }
 366       for (var i = len; i > len - del_count + num_additional_args; i--) {
 367         delete array[i - 1];
 368       }
 369     }
 370   }
 371 }
 372
 373
 374 // -------------------------------------------------------------------
 375
 376
 377 function ArrayToString() {
 378   var array;
 379   var func;
 380   if (IS_ARRAY(this)) {
 381     func = this.join;
 382     if (func === ArrayJoin) {
 383       return Join(this, this.length, ',', ConvertToString);
 384     }
 385     array = this;
 386   } else {
 387     array = TO_OBJECT(this);
 388     func = array.join;
 389   }
 390   if (!IS_CALLABLE(func)) {
 391     return %_CallFunction(array, ObjectToString);
 392   }
 393   return %_Call(func, array);
 394 }
 395
 396
 397 function InnerArrayToLocaleString(array, length) {
 398   var len = TO_LENGTH_OR_UINT32(length);
 399   if (len === 0) return "";
 400   return Join(array, len, ',', ConvertToLocaleString);
 401 }
 402
 403
 404 function ArrayToLocaleString() {
 405   var array = TO_OBJECT(this);
 406   var arrayLen = array.length;
 407   return InnerArrayToLocaleString(array, arrayLen);
 408 }
 409
 410
 411 function InnerArrayJoin(separator, array, length) {
 412   if (IS_UNDEFINED(separator)) {
 413     separator = ',';
 414   } else {
 415     separator = TO_STRING(separator);
 416   }
 417
 418   var result = %_FastOneByteArrayJoin(array, separator);
 419   if (!IS_UNDEFINED(result)) return result;
 420
 421   // Fast case for one-element arrays.
 422   if (length === 1) {
 423     var e = array[0];
 424     if (IS_NULL_OR_UNDEFINED(e)) return '';
 425     return TO_STRING(e);
 426   }
 427
 428   return Join(array, length, separator, ConvertToString);
 429 }
 430
 431
 432 function ArrayJoin(separator) {
 433   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
 434
 435   var array = TO_OBJECT(this);
 436   var length = TO_LENGTH_OR_UINT32(array.length);
 437
 438   return InnerArrayJoin(separator, array, length);
 439 }
 440
 441
 442 function ObservedArrayPop(n) {
 443   n--;
 444   var value = this[n];
 445
 446   try {
 447     $observeBeginPerformSplice(this);
 448     delete this[n];
 449     this.length = n;
 450   } finally {
 451     $observeEndPerformSplice(this);
 452     $observeEnqueueSpliceRecord(this, n, [value], 0);
 453   }
 454
 455   return value;
 456 }
 457
 458
 459 // Removes the last element from the array and returns it. See
 460 // ECMA-262, section 15.4.4.6.
 461 function ArrayPop() {
 462   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
 463
 464   var array = TO_OBJECT(this);
 465   var n = TO_LENGTH_OR_UINT32(array.length);
 466   if (n == 0) {
 467     array.length = n;
 468     return;
 469   }
 470
 471   if (%IsObserved(array))
 472     return ObservedArrayPop.call(array, n);
 473
 474   n--;
 475   var value = array[n];
 476   Delete(array, n, true);
 477   array.length = n;
 478   return value;
 479 }
 480
 481
 482 function ObservedArrayPush() {
 483   var n = TO_LENGTH_OR_UINT32(this.length);
 484   var m = %_ArgumentsLength();
 485
 486   try {
 487     $observeBeginPerformSplice(this);
 488     for (var i = 0; i < m; i++) {
 489       this[i+n] = %_Arguments(i);
 490     }
 491     var new_length = n + m;
 492     this.length = new_length;
 493   } finally {
 494     $observeEndPerformSplice(this);
 495     $observeEnqueueSpliceRecord(this, n, [], m);
 496   }
 497
 498   return new_length;
 499 }
 500
 501
 502 // Appends the arguments to the end of the array and returns the new
 503 // length of the array. See ECMA-262, section 15.4.4.7.
 504 function ArrayPush() {
 505   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
 506
 507   if (%IsObserved(this))
 508     return ObservedArrayPush.apply(this, arguments);
 509
 510   var array = TO_OBJECT(this);
 511   var n = TO_LENGTH_OR_UINT32(array.length);
 512   var m = %_ArgumentsLength();
 513
 514   for (var i = 0; i < m; i++) {
 515     array[i+n] = %_Arguments(i);
 516   }
 517
 518   var new_length = n + m;
 519   array.length = new_length;
 520   return new_length;
 521 }
 522
 523
 524 // For implementing reverse() on large, sparse arrays.
 525 function SparseReverse(array, len) {
 526   var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
 527   var high_counter = keys.length - 1;
 528   var low_counter = 0;
 529   while (low_counter <= high_counter) {
 530     var i = keys[low_counter];
 531     var j = keys[high_counter];
 532
 533     var j_complement = len - j - 1;
 534     var low, high;
 535
 536     if (j_complement <= i) {
 537       high = j;
 538       while (keys[--high_counter] == j) { }
 539       low = j_complement;
 540     }
 541     if (j_complement >= i) {
 542       low = i;
 543       while (keys[++low_counter] == i) { }
 544       high = len - i - 1;
 545     }
 546
 547     var current_i = array[low];
 548     if (!IS_UNDEFINED(current_i) || low in array) {
 549       var current_j = array[high];
 550       if (!IS_UNDEFINED(current_j) || high in array) {
 551         array[low] = current_j;
 552         array[high] = current_i;
 553       } else {
 554         array[high] = current_i;
 555         delete array[low];
 556       }
 557     } else {
 558       var current_j = array[high];
 559       if (!IS_UNDEFINED(current_j) || high in array) {
 560         array[low] = current_j;
 561         delete array[high];
 562       }
 563     }
 564   }
 565 }
 566
 567 function PackedArrayReverse(array, len) {
 568   var j = len - 1;
 569   for (var i = 0; i < j; i++, j--) {
 570     var current_i = array[i];
 571     var current_j = array[j];
 572     array[i] = current_j;
 573     array[j] = current_i;
 574   }
 575   return array;
 576 }
 577
 578
 579 function GenericArrayReverse(array, len) {
 580   var j = len - 1;
 581   for (var i = 0; i < j; i++, j--) {
 582     if (i in array) {
 583       var current_i = array[i];
 584       if (j in array) {
 585         var current_j = array[j];
 586         array[i] = current_j;
 587         array[j] = current_i;
 588       } else {
 589         array[j] = current_i;
 590         delete array[i];
 591       }
 592     } else {
 593       if (j in array) {
 594         var current_j = array[j];
 595         array[i] = current_j;
 596         delete array[j];
 597       }
 598     }
 599   }
 600   return array;
 601 }
 602
 603
 604 function ArrayReverse() {
 605   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
 606
 607   var array = TO_OBJECT(this);
 608   var len = TO_LENGTH_OR_UINT32(array.length);
 609   var isArray = IS_ARRAY(array);
 610
 611   if (UseSparseVariant(array, len, isArray, len)) {
 612     %NormalizeElements(array);
 613     SparseReverse(array, len);
 614     return array;
 615   } else if (isArray && %_HasFastPackedElements(array)) {
 616     return PackedArrayReverse(array, len);
 617   } else {
 618     return GenericArrayReverse(array, len);
 619   }
 620 }
 621
 622
 623 function ObservedArrayShift(len) {
 624   var first = this[0];
 625
 626   try {
 627     $observeBeginPerformSplice(this);
 628     SimpleMove(this, 0, 1, len, 0);
 629     this.length = len - 1;
 630   } finally {
 631     $observeEndPerformSplice(this);
 632     $observeEnqueueSpliceRecord(this, 0, [first], 0);
 633   }
 634
 635   return first;
 636 }
 637
 638
 639 function ArrayShift() {
 640   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
 641
 642   var array = TO_OBJECT(this);
 643   var len = TO_LENGTH_OR_UINT32(array.length);
 644
 645   if (len === 0) {
 646     array.length = 0;
 647     return;
 648   }
 649
 650   if (ObjectIsSealed(array)) throw MakeTypeError(kArrayFunctionsOnSealed);
 651
 652   if (%IsObserved(array))
 653     return ObservedArrayShift.call(array, len);
 654
 655   var first = array[0];
 656
 657   if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
 658     SparseMove(array, 0, 1, len, 0);
 659   } else {
 660     SimpleMove(array, 0, 1, len, 0);
 661   }
 662
 663   array.length = len - 1;
 664
 665   return first;
 666 }
 667
 668
 669 function ObservedArrayUnshift() {
 670   var len = TO_LENGTH_OR_UINT32(this.length);
 671   var num_arguments = %_ArgumentsLength();
 672
 673   try {
 674     $observeBeginPerformSplice(this);
 675     SimpleMove(this, 0, 0, len, num_arguments);
 676     for (var i = 0; i < num_arguments; i++) {
 677       this[i] = %_Arguments(i);
 678     }
 679     var new_length = len + num_arguments;
 680     this.length = new_length;
 681   } finally {
 682     $observeEndPerformSplice(this);
 683     $observeEnqueueSpliceRecord(this, 0, [], num_arguments);
 684   }
 685
 686   return new_length;
 687 }
 688
 689
 690 function ArrayUnshift(arg1) {  // length == 1
 691   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
 692
 693   if (%IsObserved(this))
 694     return ObservedArrayUnshift.apply(this, arguments);
 695
 696   var array = TO_OBJECT(this);
 697   var len = TO_LENGTH_OR_UINT32(array.length);
 698   var num_arguments = %_ArgumentsLength();
 699
 700   if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) &&
 701       !ObjectIsSealed(array)) {
 702     SparseMove(array, 0, 0, len, num_arguments);
 703   } else {
 704     SimpleMove(array, 0, 0, len, num_arguments);
 705   }
 706
 707   for (var i = 0; i < num_arguments; i++) {
 708     array[i] = %_Arguments(i);
 709   }
 710
 711   var new_length = len + num_arguments;
 712   array.length = new_length;
 713   return new_length;
 714 }
 715
 716
 717 function ArraySlice(start, end) {
 718   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
 719
 720   var array = TO_OBJECT(this);
 721   var len = TO_LENGTH_OR_UINT32(array.length);
 722   var start_i = TO_INTEGER(start);
 723   var end_i = len;
 724
 725   if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
 726
 727   if (start_i < 0) {
 728     start_i += len;
 729     if (start_i < 0) start_i = 0;
 730   } else {
 731     if (start_i > len) start_i = len;
 732   }
 733
 734   if (end_i < 0) {
 735     end_i += len;
 736     if (end_i < 0) end_i = 0;
 737   } else {
 738     if (end_i > len) end_i = len;
 739   }
 740
 741   var result = [];
 742
 743   if (end_i < start_i) return result;
 744
 745   if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
 746     %NormalizeElements(array);
 747     %NormalizeElements(result);
 748     SparseSlice(array, start_i, end_i - start_i, len, result);
 749   } else {
 750     SimpleSlice(array, start_i, end_i - start_i, len, result);
 751   }
 752
 753   result.length = end_i - start_i;
 754
 755   return result;
 756 }
 757
 758
 759 function ComputeSpliceStartIndex(start_i, len) {
 760   if (start_i < 0) {
 761     start_i += len;
 762     return start_i < 0 ? 0 : start_i;
 763   }
 764
 765   return start_i > len ? len : start_i;
 766 }
 767
 768
 769 function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
 770   // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
 771   // given as a request to delete all the elements from the start.
 772   // And it differs from the case of undefined delete count.
 773   // This does not follow ECMA-262, but we do the same for
 774   // compatibility.
 775   var del_count = 0;
 776   if (num_arguments == 1)
 777     return len - start_i;
 778
 779   del_count = TO_INTEGER(delete_count);
 780   if (del_count < 0)
 781     return 0;
 782
 783   if (del_count > len - start_i)
 784     return len - start_i;
 785
 786   return del_count;
 787 }
 788
 789
 790 function ObservedArraySplice(start, delete_count) {
 791   var num_arguments = %_ArgumentsLength();
 792   var len = TO_LENGTH_OR_UINT32(this.length);
 793   var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
 794   var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
 795                                            start_i);
 796   var deleted_elements = [];
 797   deleted_elements.length = del_count;
 798   var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
 799
 800   try {
 801     $observeBeginPerformSplice(this);
 802
 803     SimpleSlice(this, start_i, del_count, len, deleted_elements);
 804     SimpleMove(this, start_i, del_count, len, num_elements_to_add);
 805
 806     // Insert the arguments into the resulting array in
 807     // place of the deleted elements.
 808     var i = start_i;
 809     var arguments_index = 2;
 810     var arguments_length = %_ArgumentsLength();
 811     while (arguments_index < arguments_length) {
 812       this[i++] = %_Arguments(arguments_index++);
 813     }
 814     this.length = len - del_count + num_elements_to_add;
 815
 816   } finally {
 817     $observeEndPerformSplice(this);
 818     if (deleted_elements.length || num_elements_to_add) {
 819       $observeEnqueueSpliceRecord(this,
 820                                   start_i,
 821                                   deleted_elements.slice(),
 822                                   num_elements_to_add);
 823     }
 824   }
 825
 826   // Return the deleted elements.
 827   return deleted_elements;
 828 }
 829
 830
 831 function ArraySplice(start, delete_count) {
 832   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
 833
 834   if (%IsObserved(this))
 835     return ObservedArraySplice.apply(this, arguments);
 836
 837   var num_arguments = %_ArgumentsLength();
 838   var array = TO_OBJECT(this);
 839   var len = TO_LENGTH_OR_UINT32(array.length);
 840   var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
 841   var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
 842                                            start_i);
 843   var deleted_elements = [];
 844   deleted_elements.length = del_count;
 845   var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
 846
 847   if (del_count != num_elements_to_add && ObjectIsSealed(array)) {
 848     throw MakeTypeError(kArrayFunctionsOnSealed);
 849   } else if (del_count > 0 && ObjectIsFrozen(array)) {
 850     throw MakeTypeError(kArrayFunctionsOnFrozen);
 851   }
 852
 853   var changed_elements = del_count;
 854   if (num_elements_to_add != del_count) {
 855     // If the slice needs to do a actually move elements after the insertion
 856     // point, then include those in the estimate of changed elements.
 857     changed_elements += len - start_i - del_count;
 858   }
 859   if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
 860     %NormalizeElements(array);
 861     %NormalizeElements(deleted_elements);
 862     SparseSlice(array, start_i, del_count, len, deleted_elements);
 863     SparseMove(array, start_i, del_count, len, num_elements_to_add);
 864   } else {
 865     SimpleSlice(array, start_i, del_count, len, deleted_elements);
 866     SimpleMove(array, start_i, del_count, len, num_elements_to_add);
 867   }
 868
 869   // Insert the arguments into the resulting array in
 870   // place of the deleted elements.
 871   var i = start_i;
 872   var arguments_index = 2;
 873   var arguments_length = %_ArgumentsLength();
 874   while (arguments_index < arguments_length) {
 875     array[i++] = %_Arguments(arguments_index++);
 876   }
 877   array.length = len - del_count + num_elements_to_add;
 878
 879   // Return the deleted elements.
 880   return deleted_elements;
 881 }
 882
 883
 884 function InnerArraySort(array, length, comparefn) {
 885   // In-place QuickSort algorithm.
 886   // For short (length <= 22) arrays, insertion sort is used for efficiency.
 887
 888   if (!IS_CALLABLE(comparefn)) {
 889     comparefn = function (x, y) {
 890       if (x === y) return 0;
 891       if (%_IsSmi(x) && %_IsSmi(y)) {
 892         return %SmiLexicographicCompare(x, y);
 893       }
 894       x = ToString(x);
 895       y = ToString(y);
 896       if (x == y) return 0;
 897       else return x < y ? -1 : 1;
 898     };
 899   }
 900   var InsertionSort = function InsertionSort(a, from, to) {
 901     for (var i = from + 1; i < to; i++) {
 902       var element = a[i];
 903       for (var j = i - 1; j >= from; j--) {
 904         var tmp = a[j];
 905         var order = comparefn(tmp, element);
 906         if (order > 0) {
 907           a[j + 1] = tmp;
 908         } else {
 909           break;
 910         }
 911       }
 912       a[j + 1] = element;
 913     }
 914   };
 915
 916   var GetThirdIndex = function(a, from, to) {
 917     var t_array = new InternalArray();
 918     // Use both 'from' and 'to' to determine the pivot candidates.
 919     var increment = 200 + ((to - from) & 15);
 920     var j = 0;
 921     from += 1;
 922     to -= 1;
 923     for (var i = from; i < to; i += increment) {
 924       t_array[j] = [i, a[i]];
 925       j++;
 926     }
 927     t_array.sort(function(a, b) {
 928       return comparefn(a[1], b[1]);
 929     });
 930     var third_index = t_array[t_array.length >> 1][0];
 931     return third_index;
 932   }
 933
 934   var QuickSort = function QuickSort(a, from, to) {
 935     var third_index = 0;
 936     while (true) {
 937       // Insertion sort is faster for short arrays.
 938       if (to - from <= 10) {
 939         InsertionSort(a, from, to);
 940         return;
 941       }
 942       if (to - from > 1000) {
 943         third_index = GetThirdIndex(a, from, to);
 944       } else {
 945         third_index = from + ((to - from) >> 1);
 946       }
 947       // Find a pivot as the median of first, last and middle element.
 948       var v0 = a[from];
 949       var v1 = a[to - 1];
 950       var v2 = a[third_index];
 951       var c01 = comparefn(v0, v1);
 952       if (c01 > 0) {
 953         // v1 < v0, so swap them.
 954         var tmp = v0;
 955         v0 = v1;
 956         v1 = tmp;
 957       } // v0 <= v1.
 958       var c02 = comparefn(v0, v2);
 959       if (c02 >= 0) {
 960         // v2 <= v0 <= v1.
 961         var tmp = v0;
 962         v0 = v2;
 963         v2 = v1;
 964         v1 = tmp;
 965       } else {
 966         // v0 <= v1 && v0 < v2
 967         var c12 = comparefn(v1, v2);
 968         if (c12 > 0) {
 969           // v0 <= v2 < v1
 970           var tmp = v1;
 971           v1 = v2;
 972           v2 = tmp;
 973         }
 974       }
 975       // v0 <= v1 <= v2
 976       a[from] = v0;
 977       a[to - 1] = v2;
 978       var pivot = v1;
 979       var low_end = from + 1;   // Upper bound of elements lower than pivot.
 980       var high_start = to - 1;  // Lower bound of elements greater than pivot.
 981       a[third_index] = a[low_end];
 982       a[low_end] = pivot;
 983
 984       // From low_end to i are elements equal to pivot.
 985       // From i to high_start are elements that haven't been compared yet.
 986       partition: for (var i = low_end + 1; i < high_start; i++) {
 987         var element = a[i];
 988         var order = comparefn(element, pivot);
 989         if (order < 0) {
 990           a[i] = a[low_end];
 991           a[low_end] = element;
 992           low_end++;
 993         } else if (order > 0) {
 994           do {
 995             high_start--;
 996             if (high_start == i) break partition;
 997             var top_elem = a[high_start];
 998             order = comparefn(top_elem, pivot);
 999           } while (order > 0);
1000           a[i] = a[high_start];
1001           a[high_start] = element;
1002           if (order < 0) {
1003             element = a[i];
1004             a[i] = a[low_end];
1005             a[low_end] = element;
1006             low_end++;
1007           }
1008         }
1009       }
1010       if (to - high_start < low_end - from) {
1011         QuickSort(a, high_start, to);
1012         to = low_end;
1013       } else {
1014         QuickSort(a, from, low_end);
1015         from = high_start;
1016       }
1017     }
1018   };
1019
1020   // Copy elements in the range 0..length from obj's prototype chain
1021   // to obj itself, if obj has holes. Return one more than the maximal index
1022   // of a prototype property.
1023   var CopyFromPrototype = function CopyFromPrototype(obj, length) {
1024     var max = 0;
1025     for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
1026       var indices = %GetArrayKeys(proto, length);
1027       if (IS_NUMBER(indices)) {
1028         // It's an interval.
1029         var proto_length = indices;
1030         for (var i = 0; i < proto_length; i++) {
1031           if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
1032             obj[i] = proto[i];
1033             if (i >= max) { max = i + 1; }
1034           }
1035         }
1036       } else {
1037         for (var i = 0; i < indices.length; i++) {
1038           var index = indices[i];
1039           if (!IS_UNDEFINED(index) && !HAS_OWN_PROPERTY(obj, index)
1040               && HAS_OWN_PROPERTY(proto, index)) {
1041             obj[index] = proto[index];
1042             if (index >= max) { max = index + 1; }
1043           }
1044         }
1045       }
1046     }
1047     return max;
1048   };
1049
1050   // Set a value of "undefined" on all indices in the range from..to
1051   // where a prototype of obj has an element. I.e., shadow all prototype
1052   // elements in that range.
1053   var ShadowPrototypeElements = function(obj, from, to) {
1054     for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
1055       var indices = %GetArrayKeys(proto, to);
1056       if (IS_NUMBER(indices)) {
1057         // It's an interval.
1058         var proto_length = indices;
1059         for (var i = from; i < proto_length; i++) {
1060           if (HAS_OWN_PROPERTY(proto, i)) {
1061             obj[i] = UNDEFINED;
1062           }
1063         }
1064       } else {
1065         for (var i = 0; i < indices.length; i++) {
1066           var index = indices[i];
1067           if (!IS_UNDEFINED(index) && from <= index &&
1068               HAS_OWN_PROPERTY(proto, index)) {
1069             obj[index] = UNDEFINED;
1070           }
1071         }
1072       }
1073     }
1074   };
1075
1076   var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1077     // Copy defined elements from the end to fill in all holes and undefineds
1078     // in the beginning of the array.  Write undefineds and holes at the end
1079     // after loop is finished.
1080     var first_undefined = 0;
1081     var last_defined = length - 1;
1082     var num_holes = 0;
1083     while (first_undefined < last_defined) {
1084       // Find first undefined element.
1085       while (first_undefined < last_defined &&
1086              !IS_UNDEFINED(obj[first_undefined])) {
1087         first_undefined++;
1088       }
1089       // Maintain the invariant num_holes = the number of holes in the original
1090       // array with indices <= first_undefined or > last_defined.
1091       if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
1092         num_holes++;
1093       }
1094
1095       // Find last defined element.
1096       while (first_undefined < last_defined &&
1097              IS_UNDEFINED(obj[last_defined])) {
1098         if (!HAS_OWN_PROPERTY(obj, last_defined)) {
1099           num_holes++;
1100         }
1101         last_defined--;
1102       }
1103       if (first_undefined < last_defined) {
1104         // Fill in hole or undefined.
1105         obj[first_undefined] = obj[last_defined];
1106         obj[last_defined] = UNDEFINED;
1107       }
1108     }
1109     // If there were any undefineds in the entire array, first_undefined
1110     // points to one past the last defined element.  Make this true if
1111     // there were no undefineds, as well, so that first_undefined == number
1112     // of defined elements.
1113     if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
1114     // Fill in the undefineds and the holes.  There may be a hole where
1115     // an undefined should be and vice versa.
1116     var i;
1117     for (i = first_undefined; i < length - num_holes; i++) {
1118       obj[i] = UNDEFINED;
1119     }
1120     for (i = length - num_holes; i < length; i++) {
1121       // For compatability with Webkit, do not expose elements in the prototype.
1122       if (i in %_GetPrototype(obj)) {
1123         obj[i] = UNDEFINED;
1124       } else {
1125         delete obj[i];
1126       }
1127     }
1128
1129     // Return the number of defined elements.
1130     return first_undefined;
1131   };
1132
1133   if (length < 2) return array;
1134
1135   var is_array = IS_ARRAY(array);
1136   var max_prototype_element;
1137   if (!is_array) {
1138     // For compatibility with JSC, we also sort elements inherited from
1139     // the prototype chain on non-Array objects.
1140     // We do this by copying them to this object and sorting only
1141     // own elements. This is not very efficient, but sorting with
1142     // inherited elements happens very, very rarely, if at all.
1143     // The specification allows "implementation dependent" behavior
1144     // if an element on the prototype chain has an element that
1145     // might interact with sorting.
1146     max_prototype_element = CopyFromPrototype(array, length);
1147   }
1148
1149   // %RemoveArrayHoles returns -1 if fast removal is not supported.
1150   var num_non_undefined = %RemoveArrayHoles(array, length);
1151
1152   if (num_non_undefined == -1) {
1153     // The array is observed, or there were indexed accessors in the array.
1154     // Move array holes and undefineds to the end using a Javascript function
1155     // that is safe in the presence of accessors and is observable.
1156     num_non_undefined = SafeRemoveArrayHoles(array);
1157   }
1158
1159   QuickSort(array, 0, num_non_undefined);
1160
1161   if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
1162     // For compatibility with JSC, we shadow any elements in the prototype
1163     // chain that has become exposed by sort moving a hole to its position.
1164     ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
1165   }
1166
1167   return array;
1168 }
1169
1170
1171 function ArraySort(comparefn) {
1172   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
1173
1174   var array = TO_OBJECT(this);
1175   var length = TO_LENGTH_OR_UINT32(array.length);
1176   return InnerArraySort(array, length, comparefn);
1177 }
1178
1179
1180 // The following functions cannot be made efficient on sparse arrays while
1181 // preserving the semantics, since the calls to the receiver function can add
1182 // or delete elements from the array.
1183 function InnerArrayFilter(f, receiver, array, length) {
1184   if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1185
1186   var accumulator = new InternalArray();
1187   var accumulator_length = 0;
1188   var is_array = IS_ARRAY(array);
1189   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1190   for (var i = 0; i < length; i++) {
1191     if (HAS_INDEX(array, i, is_array)) {
1192       var element = array[i];
1193       // Prepare break slots for debugger step in.
1194       if (stepping) %DebugPrepareStepInIfStepping(f);
1195       if (%_Call(f, receiver, element, i, array)) {
1196         accumulator[accumulator_length++] = element;
1197       }
1198     }
1199   }
1200   return accumulator;
1201 }
1202
1203 function ArrayFilter(f, receiver) {
1204   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");
1205
1206   // Pull out the length so that modifications to the length in the
1207   // loop will not affect the looping and side effects are visible.
1208   var array = TO_OBJECT(this);
1209   var length = TO_LENGTH_OR_UINT32(array.length);
1210   var accumulator = InnerArrayFilter(f, receiver, array, length);
1211   var result = new GlobalArray();
1212   %MoveArrayContents(accumulator, result);
1213   return result;
1214 }
1215
1216 function InnerArrayForEach(f, receiver, array, length) {
1217   if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1218
1219   var is_array = IS_ARRAY(array);
1220   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1221   for (var i = 0; i < length; i++) {
1222     if (HAS_INDEX(array, i, is_array)) {
1223       var element = array[i];
1224       // Prepare break slots for debugger step in.
1225       if (stepping) %DebugPrepareStepInIfStepping(f);
1226       %_Call(f, receiver, element, i, array);
1227     }
1228   }
1229 }
1230
1231 function ArrayForEach(f, receiver) {
1232   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");
1233
1234   // Pull out the length so that modifications to the length in the
1235   // loop will not affect the looping and side effects are visible.
1236   var array = TO_OBJECT(this);
1237   var length = TO_LENGTH_OR_UINT32(array.length);
1238   InnerArrayForEach(f, receiver, array, length);
1239 }
1240
1241
1242 function InnerArraySome(f, receiver, array, length) {
1243   if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1244
1245   var is_array = IS_ARRAY(array);
1246   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1247   for (var i = 0; i < length; i++) {
1248     if (HAS_INDEX(array, i, is_array)) {
1249       var element = array[i];
1250       // Prepare break slots for debugger step in.
1251       if (stepping) %DebugPrepareStepInIfStepping(f);
1252       if (%_Call(f, receiver, element, i, array)) return true;
1253     }
1254   }
1255   return false;
1256 }
1257
1258
1259 // Executes the function once for each element present in the
1260 // array until it finds one where callback returns true.
1261 function ArraySome(f, receiver) {
1262   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");
1263
1264   // Pull out the length so that modifications to the length in the
1265   // loop will not affect the looping and side effects are visible.
1266   var array = TO_OBJECT(this);
1267   var length = TO_LENGTH_OR_UINT32(array.length);
1268   return InnerArraySome(f, receiver, array, length);
1269 }
1270
1271
1272 function InnerArrayEvery(f, receiver, array, length) {
1273   if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1274
1275   var is_array = IS_ARRAY(array);
1276   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1277   for (var i = 0; i < length; i++) {
1278     if (HAS_INDEX(array, i, is_array)) {
1279       var element = array[i];
1280       // Prepare break slots for debugger step in.
1281       if (stepping) %DebugPrepareStepInIfStepping(f);
1282       if (!%_Call(f, receiver, element, i, array)) return false;
1283     }
1284   }
1285   return true;
1286 }
1287
1288 function ArrayEvery(f, receiver) {
1289   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");
1290
1291   // Pull out the length so that modifications to the length in the
1292   // loop will not affect the looping and side effects are visible.
1293   var array = TO_OBJECT(this);
1294   var length = TO_LENGTH_OR_UINT32(array.length);
1295   return InnerArrayEvery(f, receiver, array, length);
1296 }
1297
1298
1299 function InnerArrayMap(f, receiver, array, length) {
1300   if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1301
1302   var accumulator = new InternalArray(length);
1303   var is_array = IS_ARRAY(array);
1304   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1305   for (var i = 0; i < length; i++) {
1306     if (HAS_INDEX(array, i, is_array)) {
1307       var element = array[i];
1308       // Prepare break slots for debugger step in.
1309       if (stepping) %DebugPrepareStepInIfStepping(f);
1310       accumulator[i] = %_Call(f, receiver, element, i, array);
1311     }
1312   }
1313   return accumulator;
1314 }
1315
1316
1317 function ArrayMap(f, receiver) {
1318   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map");
1319
1320   // Pull out the length so that modifications to the length in the
1321   // loop will not affect the looping and side effects are visible.
1322   var array = TO_OBJECT(this);
1323   var length = TO_LENGTH_OR_UINT32(array.length);
1324   var accumulator = InnerArrayMap(f, receiver, array, length);
1325   var result = new GlobalArray();
1326   %MoveArrayContents(accumulator, result);
1327   return result;
1328 }
1329
1330
1331 // For .indexOf, we don't need to pass in the number of arguments
1332 // at the callsite since ToInteger(undefined) == 0; however, for
1333 // .lastIndexOf, we need to pass it, since the behavior for passing
1334 // undefined is 0 but for not including the argument is length-1.
1335 function InnerArrayIndexOf(array, element, index, length) {
1336   if (length == 0) return -1;
1337   if (IS_UNDEFINED(index)) {
1338     index = 0;
1339   } else {
1340     index = TO_INTEGER(index);
1341     // If index is negative, index from the end of the array.
1342     if (index < 0) {
1343       index = length + index;
1344       // If index is still negative, search the entire array.
1345       if (index < 0) index = 0;
1346     }
1347   }
1348   var min = index;
1349   var max = length;
1350   if (UseSparseVariant(array, length, IS_ARRAY(array), max - min)) {
1351     %NormalizeElements(array);
1352     var indices = %GetArrayKeys(array, length);
1353     if (IS_NUMBER(indices)) {
1354       // It's an interval.
1355       max = indices;  // Capped by length already.
1356       // Fall through to loop below.
1357     } else {
1358       if (indices.length == 0) return -1;
1359       // Get all the keys in sorted order.
1360       var sortedKeys = GetSortedArrayKeys(array, indices);
1361       var n = sortedKeys.length;
1362       var i = 0;
1363       while (i < n && sortedKeys[i] < index) i++;
1364       while (i < n) {
1365         var key = sortedKeys[i];
1366         if (!IS_UNDEFINED(key) && array[key] === element) return key;
1367         i++;
1368       }
1369       return -1;
1370     }
1371   }
1372   // Lookup through the array.
1373   if (!IS_UNDEFINED(element)) {
1374     for (var i = min; i < max; i++) {
1375       if (array[i] === element) return i;
1376     }
1377     return -1;
1378   }
1379   // Lookup through the array.
1380   for (var i = min; i < max; i++) {
1381     if (IS_UNDEFINED(array[i]) && i in array) {
1382       return i;
1383     }
1384   }
1385   return -1;
1386 }
1387
1388
1389 function ArrayIndexOf(element, index) {
1390   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1391
1392   var length = TO_LENGTH_OR_UINT32(this.length);
1393   return InnerArrayIndexOf(this, element, index, length);
1394 }
1395
1396
1397 function InnerArrayLastIndexOf(array, element, index, length, argumentsLength) {
1398   if (length == 0) return -1;
1399   if (argumentsLength < 2) {
1400     index = length - 1;
1401   } else {
1402     index = TO_INTEGER(index);
1403     // If index is negative, index from end of the array.
1404     if (index < 0) index += length;
1405     // If index is still negative, do not search the array.
1406     if (index < 0) return -1;
1407     else if (index >= length) index = length - 1;
1408   }
1409   var min = 0;
1410   var max = index;
1411   if (UseSparseVariant(array, length, IS_ARRAY(array), index)) {
1412     %NormalizeElements(array);
1413     var indices = %GetArrayKeys(array, index + 1);
1414     if (IS_NUMBER(indices)) {
1415       // It's an interval.
1416       max = indices;  // Capped by index already.
1417       // Fall through to loop below.
1418     } else {
1419       if (indices.length == 0) return -1;
1420       // Get all the keys in sorted order.
1421       var sortedKeys = GetSortedArrayKeys(array, indices);
1422       var i = sortedKeys.length - 1;
1423       while (i >= 0) {
1424         var key = sortedKeys[i];
1425         if (!IS_UNDEFINED(key) && array[key] === element) return key;
1426         i--;
1427       }
1428       return -1;
1429     }
1430   }
1431   // Lookup through the array.
1432   if (!IS_UNDEFINED(element)) {
1433     for (var i = max; i >= min; i--) {
1434       if (array[i] === element) return i;
1435     }
1436     return -1;
1437   }
1438   for (var i = max; i >= min; i--) {
1439     if (IS_UNDEFINED(array[i]) && i in array) {
1440       return i;
1441     }
1442   }
1443   return -1;
1444 }
1445
1446
1447 function ArrayLastIndexOf(element, index) {
1448   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1449
1450   var length = TO_LENGTH_OR_UINT32(this.length);
1451   return InnerArrayLastIndexOf(this, element, index, length,
1452                         %_ArgumentsLength());
1453 }
1454
1455
1456 function InnerArrayReduce(callback, current, array, length, argumentsLength) {
1457   if (!IS_CALLABLE(callback)) {
1458     throw MakeTypeError(kCalledNonCallable, callback);
1459   }
1460
1461   var is_array = IS_ARRAY(array);
1462   var i = 0;
1463   find_initial: if (argumentsLength < 2) {
1464     for (; i < length; i++) {
1465       if (HAS_INDEX(array, i, is_array)) {
1466         current = array[i++];
1467         break find_initial;
1468       }
1469     }
1470     throw MakeTypeError(kReduceNoInitial);
1471   }
1472
1473   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1474   for (; i < length; i++) {
1475     if (HAS_INDEX(array, i, is_array)) {
1476       var element = array[i];
1477       // Prepare break slots for debugger step in.
1478       if (stepping) %DebugPrepareStepInIfStepping(callback);
1479       current = callback(current, element, i, array);
1480     }
1481   }
1482   return current;
1483 }
1484
1485
1486 function ArrayReduce(callback, current) {
1487   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1488
1489   // Pull out the length so that modifications to the length in the
1490   // loop will not affect the looping and side effects are visible.
1491   var array = TO_OBJECT(this);
1492   var length = TO_LENGTH_OR_UINT32(array.length);
1493   return InnerArrayReduce(callback, current, array, length,
1494                           %_ArgumentsLength());
1495 }
1496
1497
1498 function InnerArrayReduceRight(callback, current, array, length,
1499                                argumentsLength) {
1500   if (!IS_CALLABLE(callback)) {
1501     throw MakeTypeError(kCalledNonCallable, callback);
1502   }
1503
1504   var is_array = IS_ARRAY(array);
1505   var i = length - 1;
1506   find_initial: if (argumentsLength < 2) {
1507     for (; i >= 0; i--) {
1508       if (HAS_INDEX(array, i, is_array)) {
1509         current = array[i--];
1510         break find_initial;
1511       }
1512     }
1513     throw MakeTypeError(kReduceNoInitial);
1514   }
1515
1516   var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1517   for (; i >= 0; i--) {
1518     if (HAS_INDEX(array, i, is_array)) {
1519       var element = array[i];
1520       // Prepare break slots for debugger step in.
1521       if (stepping) %DebugPrepareStepInIfStepping(callback);
1522       current = callback(current, element, i, array);
1523     }
1524   }
1525   return current;
1526 }
1527
1528
1529 function ArrayReduceRight(callback, current) {
1530   CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight");
1531
1532   // Pull out the length so that side effects are visible before the
1533   // callback function is checked.
1534   var array = TO_OBJECT(this);
1535   var length = TO_LENGTH_OR_UINT32(array.length);
1536   return InnerArrayReduceRight(callback, current, array, length,
1537                                %_ArgumentsLength());
1538 }
1539
1540 // ES5, 15.4.3.2
1541 function ArrayIsArray(obj) {
1542   return IS_ARRAY(obj);
1543 }
1544
1545
1546 // -------------------------------------------------------------------
1547
1548 // Set up non-enumerable constructor property on the Array.prototype
1549 // object.
1550 %AddNamedProperty(GlobalArray.prototype, "constructor", GlobalArray,
1551                   DONT_ENUM);
1552
1553 // Set up unscopable properties on the Array.prototype object.
1554 var unscopables = {
1555   __proto__: null,
1556   copyWithin: true,
1557   entries: true,
1558   fill: true,
1559   find: true,
1560   findIndex: true,
1561   keys: true,
1562 };
1563
1564 %AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables,
1565                   DONT_ENUM | READ_ONLY);
1566
1567 // Set up non-enumerable functions on the Array object.
1568 utils.InstallFunctions(GlobalArray, DONT_ENUM, [
1569   "isArray", ArrayIsArray
1570 ]);
1571
1572 var specialFunctions = %SpecialArrayFunctions();
1573
1574 var getFunction = function(name, jsBuiltin, len) {
1575   var f = jsBuiltin;
1576   if (specialFunctions.hasOwnProperty(name)) {
1577     f = specialFunctions[name];
1578   }
1579   if (!IS_UNDEFINED(len)) {
1580     %FunctionSetLength(f, len);
1581   }
1582   return f;
1583 };
1584
1585 // Set up non-enumerable functions of the Array.prototype object and
1586 // set their names.
1587 // Manipulate the length of some of the functions to meet
1588 // expectations set by ECMA-262 or Mozilla.
1589 utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [
1590   "toString", getFunction("toString", ArrayToString),
1591   "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
1592   "join", getFunction("join", ArrayJoin),
1593   "pop", getFunction("pop", ArrayPop),
1594   "push", getFunction("push", ArrayPush, 1),
1595   "reverse", getFunction("reverse", ArrayReverse),
1596   "shift", getFunction("shift", ArrayShift),
1597   "unshift", getFunction("unshift", ArrayUnshift, 1),
1598   "slice", getFunction("slice", ArraySlice, 2),
1599   "splice", getFunction("splice", ArraySplice, 2),
1600   "sort", getFunction("sort", ArraySort),
1601   "filter", getFunction("filter", ArrayFilter, 1),
1602   "forEach", getFunction("forEach", ArrayForEach, 1),
1603   "some", getFunction("some", ArraySome, 1),
1604   "every", getFunction("every", ArrayEvery, 1),
1605   "map", getFunction("map", ArrayMap, 1),
1606   "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
1607   "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1608   "reduce", getFunction("reduce", ArrayReduce, 1),
1609   "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1610 ]);
1611
1612 %FinishArrayPrototypeSetup(GlobalArray.prototype);
1613
1614 // The internal Array prototype doesn't need to be fancy, since it's never
1615 // exposed to user code.
1616 // Adding only the functions that are actually used.
1617 utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [
1618   "indexOf", getFunction("indexOf", ArrayIndexOf),
1619   "join", getFunction("join", ArrayJoin),
1620   "pop", getFunction("pop", ArrayPop),
1621   "push", getFunction("push", ArrayPush),
1622   "shift", getFunction("shift", ArrayShift),
1623   "sort", getFunction("sort", ArraySort),
1624   "splice", getFunction("splice", ArraySplice)
1625 ]);
1626
1627 utils.SetUpLockedPrototype(InternalPackedArray, GlobalArray(), [
1628   "join", getFunction("join", ArrayJoin),
1629   "pop", getFunction("pop", ArrayPop),
1630   "push", getFunction("push", ArrayPush),
1631   "shift", getFunction("shift", ArrayShift)
1632 ]);
1633
1634 // -------------------------------------------------------------------
1635 // Exports
1636
1637 utils.Export(function(to) {
1638   to.ArrayIndexOf = ArrayIndexOf;
1639   to.ArrayJoin = ArrayJoin;
1640   to.ArrayPush = ArrayPush;
1641   to.ArrayToString = ArrayToString;
1642   to.InnerArrayEvery = InnerArrayEvery;
1643   to.InnerArrayFilter = InnerArrayFilter;
1644   to.InnerArrayForEach = InnerArrayForEach;
1645   to.InnerArrayIndexOf = InnerArrayIndexOf;
1646   to.InnerArrayJoin = InnerArrayJoin;
1647   to.InnerArrayLastIndexOf = InnerArrayLastIndexOf;
1648   to.InnerArrayMap = InnerArrayMap;
1649   to.InnerArrayReduce = InnerArrayReduce;
1650   to.InnerArrayReduceRight = InnerArrayReduceRight;
1651   to.InnerArraySome = InnerArraySome;
1652   to.InnerArraySort = InnerArraySort;
1653   to.InnerArrayToLocaleString = InnerArrayToLocaleString;
1654   to.PackedArrayReverse = PackedArrayReverse;
1655 });
1656
1657 %InstallToContext([
1658   "array_pop", ArrayPop,
1659   "array_push", ArrayPush,
1660   "array_shift", ArrayShift,
1661   "array_splice", ArraySplice,
1662   "array_slice", ArraySlice,
1663   "array_unshift", ArrayUnshift,
1664 ]);
1665
1666 });