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