array.js 48.2 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// This file relies on the fact that the following declarations have been made
// in runtime.js:
30
// var $Array = global.Array;
31 32 33 34 35

// -------------------------------------------------------------------

// Global list of arrays visited during toString, toLocaleString and
// join invocations.
36
var visited_arrays = new InternalArray();
37 38 39 40


// Gets a sorted array of array keys.  Useful for operations on sparse
// arrays.  Dupes have not been removed.
41 42 43 44 45 46 47 48 49
function GetSortedArrayKeys(array, indices) {
  var keys = new InternalArray();
  if (IS_NUMBER(indices)) {
    // It's an interval
    var limit = indices;
    for (var i = 0; i < limit; ++i) {
      var e = array[i];
      if (!IS_UNDEFINED(e) || i in array) {
        keys.push(i);
50
      }
51 52 53 54 55
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
56 57 58 59 60 61 62
      if (!IS_UNDEFINED(key)) {
        var e = array[key];
        if (!IS_UNDEFINED(e) || key in array) {
          keys.push(key);
        }
      }
    }
63
    %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
64 65 66 67 68
  }
  return keys;
}


69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
function SparseJoinWithSeparator(array, len, convert, separator) {
  var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
  var totalLength = 0;
  var elements = new InternalArray(keys.length * 2);
  var previousKey = -1;
  for (var i = 0; i < keys.length; i++) {
    var key = keys[i];
    if (key != previousKey) {  // keys may contain duplicates.
      var e = array[key];
      if (!IS_STRING(e)) e = convert(e);
      elements[i * 2] = key;
      elements[i * 2 + 1] = e;
      previousKey = key;
    }
  }
  return %SparseJoinWithSeparator(elements, len, separator);
}


88 89 90 91 92
// Optimized for sparse arrays if separator is ''.
function SparseJoin(array, len, convert) {
  var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
  var last_key = -1;
  var keys_length = keys.length;
93

94
  var elements = new InternalArray(keys_length);
95 96
  var elements_length = 0;

97 98 99 100
  for (var i = 0; i < keys_length; i++) {
    var key = keys[i];
    if (key != last_key) {
      var e = array[key];
101 102
      if (!IS_STRING(e)) e = convert(e);
      elements[elements_length++] = e;
103 104 105
      last_key = key;
    }
  }
106
  return %StringBuilderConcat(elements, elements_length, '');
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
}


function UseSparseVariant(object, length, is_array) {
   return is_array &&
       length > 1000 &&
       (!%_IsSmi(length) ||
        %EstimateNumberOfElements(object) < (length >> 2));
}


function Join(array, length, separator, convert) {
  if (length == 0) return '';

  var is_array = IS_ARRAY(array);

  if (is_array) {
    // If the array is cyclic, return the empty string for already
    // visited arrays.
126
    if (!%PushIfAbsent(visited_arrays, array)) return '';
127 128 129 130
  }

  // Attempt to convert the elements.
  try {
131 132 133 134 135 136
    if (UseSparseVariant(array, length, is_array)) {
      if (separator.length == 0) {
        return SparseJoin(array, length, convert);
      } else {
        return SparseJoinWithSeparator(array, length, convert, separator);
      }
137 138
    }

139 140 141
    // Fast case for one-element arrays.
    if (length == 1) {
      var e = array[0];
142 143
      if (IS_STRING(e)) return e;
      return convert(e);
144 145
    }

146
    // Construct an array for the elements.
147
    var elements = new InternalArray(length);
148

149 150
    // We pull the empty separator check outside the loop for speed!
    if (separator.length == 0) {
151
      var elements_length = 0;
152 153
      for (var i = 0; i < length; i++) {
        var e = array[i];
154 155
        if (!IS_STRING(e)) e = convert(e);
        elements[elements_length++] = e;
156
      }
157 158 159 160 161
      elements.length = elements_length;
      var result = %_FastAsciiArrayJoin(elements, '');
      if (!IS_UNDEFINED(result)) return result;
      return %StringBuilderConcat(elements, elements_length, '');
    }
162
    // Non-empty separator case.
163
    // If the first element is a number then use the heuristic that the
164 165 166 167
    // remaining elements are also likely to be numbers.
    if (!IS_NUMBER(array[0])) {
      for (var i = 0; i < length; i++) {
        var e = array[i];
168 169
        if (!IS_STRING(e)) e = convert(e);
        elements[i] = e;
170
      }
171
    } else {
172 173
      for (var i = 0; i < length; i++) {
        var e = array[i];
174 175 176 177 178 179
        if (IS_NUMBER(e)) {
          e = %_NumberToString(e);
        } else if (!IS_STRING(e)) {
          e = convert(e);
        }
        elements[i] = e;
180
      }
181
    }
182
    var result = %_FastAsciiArrayJoin(elements, separator);
183
    if (!IS_UNDEFINED(result)) return result;
184

185
    return %StringBuilderJoin(elements, length, separator);
186
  } finally {
187 188 189
    // Make sure to remove the last element of the visited array no
    // matter what happens.
    if (is_array) visited_arrays.length = visited_arrays.length - 1;
190
  }
191
}
192 193


194
function ConvertToString(x) {
195
  // Assumes x is a non-string.
196 197 198
  if (IS_NUMBER(x)) return %_NumberToString(x);
  if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
  return (IS_NULL_OR_UNDEFINED(x)) ? '' : %ToString(%DefaultString(x));
199
}
200 201 202


function ConvertToLocaleString(e) {
203
  if (IS_NULL_OR_UNDEFINED(e)) {
204 205
    return '';
  } else {
206
    // According to ES5, section 15.4.4.3, the toLocaleString conversion
207 208
    // must throw a TypeError if ToObject(e).toLocaleString isn't
    // callable.
209
    var e_obj = ToObject(e);
210
    return %ToString(e_obj.toLocaleString());
211
  }
212
}
213 214 215 216 217 218


// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
function SmartSlice(array, start_i, del_count, len, deleted_elements) {
  // Move deleted elements to a new array (the return value from splice).
219 220 221 222 223 224 225
  var indices = %GetArrayKeys(array, start_i + del_count);
  if (IS_NUMBER(indices)) {
    var limit = indices;
    for (var i = start_i; i < limit; ++i) {
      var current = array[i];
      if (!IS_UNDEFINED(current) || i in array) {
        deleted_elements[i - start_i] = current;
226
      }
227 228 229 230 231
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
232 233 234 235 236 237 238 239 240 241
      if (!IS_UNDEFINED(key)) {
        if (key >= start_i) {
          var current = array[key];
          if (!IS_UNDEFINED(current) || key in array) {
            deleted_elements[key - start_i] = current;
          }
        }
      }
    }
  }
242
}
243 244 245 246 247 248


// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
function SmartMove(array, start_i, del_count, len, num_additional_args) {
  // Move data to new array.
249
  var new_array = new InternalArray(len - del_count + num_additional_args);
250 251 252 253 254 255 256
  var indices = %GetArrayKeys(array, len);
  if (IS_NUMBER(indices)) {
    var limit = indices;
    for (var i = 0; i < start_i && i < limit; ++i) {
      var current = array[i];
      if (!IS_UNDEFINED(current) || i in array) {
        new_array[i] = current;
257
      }
258 259 260 261 262
    }
    for (var i = start_i + del_count; i < limit; ++i) {
      var current = array[i];
      if (!IS_UNDEFINED(current) || i in array) {
        new_array[i - del_count + num_additional_args] = current;
263
      }
264 265 266 267 268
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
269 270 271
      if (!IS_UNDEFINED(key)) {
        if (key < start_i) {
          var current = array[key];
272
          if (!IS_UNDEFINED(current) || key in array) {
273
            new_array[key] = current;
274
          }
275 276
        } else if (key >= start_i + del_count) {
          var current = array[key];
277
          if (!IS_UNDEFINED(current) || key in array) {
278
            new_array[key - del_count + num_additional_args] = current;
279
          }
280 281 282 283 284 285
        }
      }
    }
  }
  // Move contents of new_array into this array
  %MoveArrayContents(new_array, array);
286
}
287 288 289 290 291 292 293 294 295 296 297 298


// This is part of the old simple-minded splice.  We are using it either
// because the receiver is not an array (so we have no choice) or because we
// know we are not deleting or moving a lot of elements.
function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
  for (var i = 0; i < del_count; i++) {
    var index = start_i + i;
    // The spec could also be interpreted such that %HasLocalProperty
    // would be the appropriate test.  We follow KJS in consulting the
    // prototype.
    var current = array[index];
299
    if (!IS_UNDEFINED(current) || index in array) {
300
      deleted_elements[i] = current;
301
    }
302
  }
303
}
304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342


function SimpleMove(array, start_i, del_count, len, num_additional_args) {
  if (num_additional_args !== del_count) {
    // Move the existing elements after the elements to be deleted
    // to the right position in the resulting array.
    if (num_additional_args > del_count) {
      for (var i = len - del_count; i > start_i; i--) {
        var from_index = i + del_count - 1;
        var to_index = i + num_additional_args - 1;
        // The spec could also be interpreted such that
        // %HasLocalProperty would be the appropriate test.  We follow
        // KJS in consulting the prototype.
        var current = array[from_index];
        if (!IS_UNDEFINED(current) || from_index in array) {
          array[to_index] = current;
        } else {
          delete array[to_index];
        }
      }
    } else {
      for (var i = start_i; i < len - del_count; i++) {
        var from_index = i + del_count;
        var to_index = i + num_additional_args;
        // The spec could also be interpreted such that
        // %HasLocalProperty would be the appropriate test.  We follow
        // KJS in consulting the prototype.
        var current = array[from_index];
        if (!IS_UNDEFINED(current) || from_index in array) {
          array[to_index] = current;
        } else {
          delete array[to_index];
        }
      }
      for (var i = len; i > len - del_count + num_additional_args; i--) {
        delete array[i - 1];
      }
    }
  }
343
}
344 345 346 347 348 349


// -------------------------------------------------------------------


function ArrayToString() {
350 351 352 353 354 355 356 357 358 359 360
  var array;
  var func;
  if (IS_ARRAY(this)) {
    func = this.join;
    if (func === ArrayJoin) {
      return Join(this, this.length, ',', ConvertToString);
    }
    array = this;
  } else {
    array = ToObject(this);
    func = array.join;
361
  }
362 363 364 365
  if (!IS_SPEC_FUNCTION(func)) {
    return %_CallFunction(array, ObjectToString);
  }
  return %_CallFunction(array, func);
366
}
367 368 369


function ArrayToLocaleString() {
370 371 372 373 374
  var array = ToObject(this);
  var arrayLen = array.length;
  var len = TO_UINT32(arrayLen);
  if (len === 0) return "";
  return Join(array, len, ',', ConvertToLocaleString);
375
}
376 377 378


function ArrayJoin(separator) {
379
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
380

381
  var length = TO_UINT32(this.length);
382 383 384
  if (IS_UNDEFINED(separator)) {
    separator = ',';
  } else if (!IS_STRING(separator)) {
385
    separator = NonStringToString(separator);
386
  }
387 388

  var result = %_FastAsciiArrayJoin(this, separator);
389
  if (!IS_UNDEFINED(result)) return result;
390

391
  return Join(this, length, separator, ConvertToString);
392
}
393 394


395 396 397 398 399 400 401 402 403 404
function ObservedArrayPop(n) {
  n--;
  var value = this[n];

  try {
    BeginPerformSplice(this);
    delete this[n];
    this.length = n;
  } finally {
    EndPerformSplice(this);
405
    EnqueueSpliceRecord(this, n, [value], 0);
406 407 408 409 410
  }

  return value;
}

411 412 413
// Removes the last element from the array and returns it. See
// ECMA-262, section 15.4.4.6.
function ArrayPop() {
414
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
415

416
  var n = TO_UINT32(this.length);
417 418 419 420
  if (n == 0) {
    this.length = n;
    return;
  }
421

422 423 424 425 426
  if ($Object.isSealed(this)) {
    throw MakeTypeError("array_functions_change_sealed",
                        ["Array.prototype.pop"]);
  }

427 428 429
  if (%IsObserved(this))
    return ObservedArrayPop.call(this, n);

430 431
  n--;
  var value = this[n];
432
  Delete(this, ToName(n), true);
433
  this.length = n;
434
  return value;
435
}
436 437


438 439 440 441 442 443 444 445 446 447 448 449
function ObservedArrayPush() {
  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();

  try {
    BeginPerformSplice(this);
    for (var i = 0; i < m; i++) {
      this[i+n] = %_Arguments(i);
    }
    this.length = n + m;
  } finally {
    EndPerformSplice(this);
450
    EnqueueSpliceRecord(this, n, [], m);
451 452 453 454 455
  }

  return this.length;
}

456 457 458
// Appends the arguments to the end of the array and returns the new
// length of the array. See ECMA-262, section 15.4.4.7.
function ArrayPush() {
459
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
460

461 462 463 464 465 466 467
  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  if (m > 0 && $Object.isSealed(this)) {
    throw MakeTypeError("array_functions_change_sealed",
                        ["Array.prototype.push"]);
  }

468 469 470
  if (%IsObserved(this))
    return ObservedArrayPush.apply(this, arguments);

471 472 473 474 475
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
476
}
477 478


479 480 481
// Returns an array containing the array elements of the object followed
// by the array elements of each argument in order. See ECMA-262,
// section 15.4.4.7.
482
function ArrayConcat(arg1) {  // length == 1
483
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.concat");
484

485
  var array = ToObject(this);
486
  var arg_count = %_ArgumentsLength();
487
  var arrays = new InternalArray(1 + arg_count);
488
  arrays[0] = array;
489 490
  for (var i = 0; i < arg_count; i++) {
    arrays[i + 1] = %_Arguments(i);
491 492
  }

493
  return %ArrayConcat(arrays);
494
}
495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510


// For implementing reverse() on large, sparse arrays.
function SparseReverse(array, len) {
  var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
  var high_counter = keys.length - 1;
  var low_counter = 0;
  while (low_counter <= high_counter) {
    var i = keys[low_counter];
    var j = keys[high_counter];

    var j_complement = len - j - 1;
    var low, high;

    if (j_complement <= i) {
      high = j;
511
      while (keys[--high_counter] == j) { }
512 513 514 515
      low = j_complement;
    }
    if (j_complement >= i) {
      low = i;
516
      while (keys[++low_counter] == i) { }
517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541
      high = len - i - 1;
    }

    var current_i = array[low];
    if (!IS_UNDEFINED(current_i) || low in array) {
      var current_j = array[high];
      if (!IS_UNDEFINED(current_j) || high in array) {
        array[low] = current_j;
        array[high] = current_i;
      } else {
        array[high] = current_i;
        delete array[low];
      }
    } else {
      var current_j = array[high];
      if (!IS_UNDEFINED(current_j) || high in array) {
        array[low] = current_j;
        delete array[high];
      }
    }
  }
}


function ArrayReverse() {
542
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
543

544
  var j = TO_UINT32(this.length) - 1;
545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570

  if (UseSparseVariant(this, j, IS_ARRAY(this))) {
    SparseReverse(this, j+1);
    return this;
  }

  for (var i = 0; i < j; i++, j--) {
    var current_i = this[i];
    if (!IS_UNDEFINED(current_i) || i in this) {
      var current_j = this[j];
      if (!IS_UNDEFINED(current_j) || j in this) {
        this[i] = current_j;
        this[j] = current_i;
      } else {
        this[j] = current_i;
        delete this[i];
      }
    } else {
      var current_j = this[j];
      if (!IS_UNDEFINED(current_j) || j in this) {
        this[i] = current_j;
        delete this[j];
      }
    }
  }
  return this;
571
}
572 573


574 575 576 577 578 579 580 581 582
function ObservedArrayShift(len) {
  var first = this[0];

  try {
    BeginPerformSplice(this);
    SimpleMove(this, 0, 1, len, 0);
    this.length = len - 1;
  } finally {
    EndPerformSplice(this);
583
    EnqueueSpliceRecord(this, 0, [first], 0);
584 585 586 587 588
  }

  return first;
}

589
function ArrayShift() {
590
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
591

592
  var len = TO_UINT32(this.length);
593

594 595 596 597
  if (len === 0) {
    this.length = 0;
    return;
  }
598

599 600 601 602 603
  if ($Object.isSealed(this)) {
    throw MakeTypeError("array_functions_change_sealed",
                        ["Array.prototype.shift"]);
  }

604 605 606
  if (%IsObserved(this))
    return ObservedArrayShift.call(this, len);

607
  var first = this[0];
608

609
  if (IS_ARRAY(this)) {
610
    SmartMove(this, 0, 1, len, 0);
611
  } else {
612
    SimpleMove(this, 0, 1, len, 0);
613
  }
614

615
  this.length = len - 1;
616

617
  return first;
618
}
619

620 621 622 623 624 625 626 627 628 629 630 631 632
function ObservedArrayUnshift() {
  var len = TO_UINT32(this.length);
  var num_arguments = %_ArgumentsLength();

  try {
    BeginPerformSplice(this);
    SimpleMove(this, 0, 0, len, num_arguments);
    for (var i = 0; i < num_arguments; i++) {
      this[i] = %_Arguments(i);
    }
    this.length = len + num_arguments;
  } finally {
    EndPerformSplice(this);
633
    EnqueueSpliceRecord(this, 0, [], num_arguments);
634 635 636 637
  }

  return len + num_arguments;
}
638 639

function ArrayUnshift(arg1) {  // length == 1
640
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
641

642
  var len = TO_UINT32(this.length);
643
  var num_arguments = %_ArgumentsLength();
644
  var is_sealed = $Object.isSealed(this);
645

646 647 648 649 650 651 652 653 654
  if (num_arguments > 0 && is_sealed) {
    throw MakeTypeError("array_functions_change_sealed",
                        ["Array.prototype.unshift"]);
  }

  if (%IsObserved(this))
    return ObservedArrayUnshift.apply(this, arguments);

  if (IS_ARRAY(this) && !is_sealed) {
655
    SmartMove(this, 0, 0, len, num_arguments);
656
  } else {
657 658 659 660 661 662 663 664 665 666 667
    if (num_arguments == 0 && $Object.isFrozen(this)) {
      // In the zero argument case, values from the prototype come into the
      // object. This can't be allowed on frozen arrays.
      for (var i = 0; i < len; i++) {
        if (!this.hasOwnProperty(i) && !IS_UNDEFINED(this[i])) {
          throw MakeTypeError("array_functions_on_frozen",
                              ["Array.prototype.shift"]);
        }
      }
    }

668
    SimpleMove(this, 0, 0, len, num_arguments);
669
  }
670

671 672 673
  for (var i = 0; i < num_arguments; i++) {
    this[i] = %_Arguments(i);
  }
674

675
  this.length = len + num_arguments;
676

677
  return this.length;
678
}
679 680 681


function ArraySlice(start, end) {
682
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
683

684
  var len = TO_UINT32(this.length);
685 686
  var start_i = TO_INTEGER(start);
  var end_i = len;
687

688
  if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
689

690 691 692 693 694 695
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
696

697 698 699 700 701 702
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
703

704
  var result = [];
705 706 707

  if (end_i < start_i) return result;

708
  if (IS_ARRAY(this) &&
709
      !%IsObserved(this) &&
710 711
      (end_i > 1000) &&
      (%EstimateNumberOfElements(this) < end_i)) {
712
    SmartSlice(this, start_i, end_i - start_i, len, result);
713
  } else {
714
    SimpleSlice(this, start_i, end_i - start_i, len, result);
715 716
  }

717
  result.length = end_i - start_i;
718

719
  return result;
720
}
721 722


723
function ComputeSpliceStartIndex(start_i, len) {
724 725
  if (start_i < 0) {
    start_i += len;
726
    return start_i < 0 ? 0 : start_i;
727
  }
728

729 730 731 732 733
  return start_i > len ? len : start_i;
}


function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
734
  // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
735 736
  // given as a request to delete all the elements from the start.
  // And it differs from the case of undefined delete count.
737 738 739
  // This does not follow ECMA-262, but we do the same for
  // compatibility.
  var del_count = 0;
740 741 742 743 744 745 746 747 748 749 750 751
  if (num_arguments == 1)
    return len - start_i;

  del_count = TO_INTEGER(delete_count);
  if (del_count < 0)
    return 0;

  if (del_count > len - start_i)
    return len - start_i;

  return del_count;
}
752

753 754 755 756 757 758 759

function ObservedArraySplice(start, delete_count) {
  var num_arguments = %_ArgumentsLength();
  var len = TO_UINT32(this.length);
  var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
  var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
                                           start_i);
760 761
  var deleted_elements = [];
  deleted_elements.length = del_count;
762 763 764 765
  var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;

  try {
    BeginPerformSplice(this);
766

767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
    SimpleSlice(this, start_i, del_count, len, deleted_elements);
    SimpleMove(this, start_i, del_count, len, num_elements_to_add);

    // Insert the arguments into the resulting array in
    // place of the deleted elements.
    var i = start_i;
    var arguments_index = 2;
    var arguments_length = %_ArgumentsLength();
    while (arguments_index < arguments_length) {
      this[i++] = %_Arguments(arguments_index++);
    }
    this.length = len - del_count + num_elements_to_add;

  } finally {
    EndPerformSplice(this);
    if (deleted_elements.length || num_elements_to_add) {
       EnqueueSpliceRecord(this,
                           start_i,
                           deleted_elements.slice(),
                           num_elements_to_add);
    }
788
  }
789

790 791 792 793 794 795
  // Return the deleted elements.
  return deleted_elements;
}


function ArraySplice(start, delete_count) {
796
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
797

798 799 800 801 802 803 804 805 806 807 808 809
  if (%IsObserved(this))
    return ObservedArraySplice.apply(this, arguments);

  var num_arguments = %_ArgumentsLength();
  var len = TO_UINT32(this.length);
  var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
  var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
                                           start_i);
  var deleted_elements = [];
  deleted_elements.length = del_count;
  var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;

810 811 812 813 814 815 816 817
  if (del_count != num_elements_to_add && $Object.isSealed(this)) {
    throw MakeTypeError("array_functions_change_sealed",
                        ["Array.prototype.splice"]);
  } else if (del_count > 0 && $Object.isFrozen(this)) {
    throw MakeTypeError("array_functions_on_frozen",
                        ["Array.prototype.splice"]);
  }

818
  var use_simple_splice = true;
819
  if (IS_ARRAY(this) &&
820
      num_elements_to_add !== del_count) {
821 822 823 824 825 826 827 828
    // If we are only deleting/moving a few things near the end of the
    // array then the simple version is going to be faster, because it
    // doesn't touch most of the array.
    var estimated_non_hole_elements = %EstimateNumberOfElements(this);
    if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
      use_simple_splice = false;
    }
  }
829

830 831
  if (use_simple_splice) {
    SimpleSlice(this, start_i, del_count, len, deleted_elements);
832
    SimpleMove(this, start_i, del_count, len, num_elements_to_add);
833 834
  } else {
    SmartSlice(this, start_i, del_count, len, deleted_elements);
835
    SmartMove(this, start_i, del_count, len, num_elements_to_add);
836
  }
837

838 839 840 841 842 843 844 845
  // Insert the arguments into the resulting array in
  // place of the deleted elements.
  var i = start_i;
  var arguments_index = 2;
  var arguments_length = %_ArgumentsLength();
  while (arguments_index < arguments_length) {
    this[i++] = %_Arguments(arguments_index++);
  }
846
  this.length = len - del_count + num_elements_to_add;
847

848 849
  // Return the deleted elements.
  return deleted_elements;
850
}
851 852 853


function ArraySort(comparefn) {
854
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
855

olehougaard's avatar
olehougaard committed
856
  // In-place QuickSort algorithm.
olehougaard's avatar
olehougaard committed
857
  // For short (length <= 22) arrays, insertion sort is used for efficiency.
858

859
  if (!IS_SPEC_FUNCTION(comparefn)) {
860 861 862 863
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
864
      }
865 866 867 868 869
      x = ToString(x);
      y = ToString(y);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
870
  }
871
  var receiver = %GetDefaultReceiver(comparefn);
872

873
  var InsertionSort = function InsertionSort(a, from, to) {
olehougaard's avatar
olehougaard committed
874 875
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
876 877
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
878
        var order = %_CallFunction(receiver, tmp, element, comparefn);
879 880
        if (order > 0) {
          a[j + 1] = tmp;
olehougaard's avatar
olehougaard committed
881
        } else {
882
          break;
olehougaard's avatar
olehougaard committed
883 884
        }
      }
885
      a[j + 1] = element;
olehougaard's avatar
olehougaard committed
886
    }
887
  };
888

889 890 891 892 893 894 895 896 897 898 899 900 901
  var GetThirdIndex = function(a, from, to) {
    var t_array = [];
    // Use both 'from' and 'to' to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
    for (var i = from + 1; i < to - 1; i += increment) {
      t_array.push([i, a[i]]);
    }
    t_array.sort(function(a, b) {
        return %_CallFunction(receiver, a[1], b[1], comparefn) } );
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

902
  var QuickSort = function QuickSort(a, from, to) {
903
    var third_index = 0;
904 905 906 907 908
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
909
      }
910 911 912 913 914
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
915 916 917
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
918
      var v2 = a[third_index];
919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948
      var c01 = %_CallFunction(receiver, v0, v1, comparefn);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = %_CallFunction(receiver, v0, v2, comparefn);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = %_CallFunction(receiver, v1, v2, comparefn);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
949
      a[third_index] = a[low_end];
950 951 952 953 954 955 956
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = %_CallFunction(receiver, element, pivot, comparefn);
957
        if (order < 0) {
958 959
          a[i] = a[low_end];
          a[low_end] = element;
960
          low_end++;
961 962 963 964 965 966 967 968 969 970 971 972 973 974 975
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = %_CallFunction(receiver, top_elem, pivot, comparefn);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
976
        }
977
      }
978 979 980 981 982 983 984
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
985
    }
986
  };
987

988 989
  // Copy elements in the range 0..length from obj's prototype chain
  // to obj itself, if obj has holes. Return one more than the maximal index
990
  // of a prototype property.
991
  var CopyFromPrototype = function CopyFromPrototype(obj, length) {
992
    var max = 0;
993
    for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
994
      var indices = %GetArrayKeys(proto, length);
995 996 997 998 999 1000 1001
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = 0; i < proto_length; i++) {
          if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
            obj[i] = proto[i];
            if (i >= max) { max = i + 1; }
1002
          }
1003 1004 1005 1006 1007 1008 1009 1010
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
          if (!IS_UNDEFINED(index) &&
              !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) {
            obj[index] = proto[index];
            if (index >= max) { max = index + 1; }
1011 1012 1013 1014 1015
          }
        }
      }
    }
    return max;
1016
  };
1017 1018 1019 1020

  // Set a value of "undefined" on all indices in the range from..to
  // where a prototype of obj has an element. I.e., shadow all prototype
  // elements in that range.
1021
  var ShadowPrototypeElements = function(obj, from, to) {
1022
    for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
1023
      var indices = %GetArrayKeys(proto, to);
1024 1025 1026 1027 1028
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = from; i < proto_length; i++) {
          if (proto.hasOwnProperty(i)) {
1029
            obj[i] = UNDEFINED;
1030
          }
1031 1032 1033 1034 1035 1036
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
          if (!IS_UNDEFINED(index) && from <= index &&
              proto.hasOwnProperty(index)) {
1037
            obj[index] = UNDEFINED;
1038 1039 1040 1041
          }
        }
      }
    }
1042
  };
1043

1044
  var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073
    // Copy defined elements from the end to fill in all holes and undefineds
    // in the beginning of the array.  Write undefineds and holes at the end
    // after loop is finished.
    var first_undefined = 0;
    var last_defined = length - 1;
    var num_holes = 0;
    while (first_undefined < last_defined) {
      // Find first undefined element.
      while (first_undefined < last_defined &&
             !IS_UNDEFINED(obj[first_undefined])) {
        first_undefined++;
      }
      // Maintain the invariant num_holes = the number of holes in the original
      // array with indices <= first_undefined or > last_defined.
      if (!obj.hasOwnProperty(first_undefined)) {
        num_holes++;
      }

      // Find last defined element.
      while (first_undefined < last_defined &&
             IS_UNDEFINED(obj[last_defined])) {
        if (!obj.hasOwnProperty(last_defined)) {
          num_holes++;
        }
        last_defined--;
      }
      if (first_undefined < last_defined) {
        // Fill in hole or undefined.
        obj[first_undefined] = obj[last_defined];
1074
        obj[last_defined] = UNDEFINED;
1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085
      }
    }
    // If there were any undefineds in the entire array, first_undefined
    // points to one past the last defined element.  Make this true if
    // there were no undefineds, as well, so that first_undefined == number
    // of defined elements.
    if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
    // Fill in the undefineds and the holes.  There may be a hole where
    // an undefined should be and vice versa.
    var i;
    for (i = first_undefined; i < length - num_holes; i++) {
1086
      obj[i] = UNDEFINED;
1087 1088 1089
    }
    for (i = length - num_holes; i < length; i++) {
      // For compatability with Webkit, do not expose elements in the prototype.
1090
      if (i in %GetPrototype(obj)) {
1091
        obj[i] = UNDEFINED;
1092 1093 1094 1095 1096 1097 1098
      } else {
        delete obj[i];
      }
    }

    // Return the number of defined elements.
    return first_undefined;
1099
  };
1100

1101
  var length = TO_UINT32(this.length);
1102
  if (length < 2) return this;
1103

1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
  var is_array = IS_ARRAY(this);
  var max_prototype_element;
  if (!is_array) {
    // For compatibility with JSC, we also sort elements inherited from
    // the prototype chain on non-Array objects.
    // We do this by copying them to this object and sorting only
    // local elements. This is not very efficient, but sorting with
    // inherited elements happens very, very rarely, if at all.
    // The specification allows "implementation dependent" behavior
    // if an element on the prototype chain has an element that
    // might interact with sorting.
    max_prototype_element = CopyFromPrototype(this, length);
  }

1118 1119 1120
  var num_non_undefined = %IsObserved(this) ?
      -1 : %RemoveArrayHoles(this, length);

1121
  if (num_non_undefined == -1) {
1122 1123 1124
    // The array is observed, or there were indexed accessors in the array.
    // Move array holes and undefineds to the end using a Javascript function
    // that is safe in the presence of accessors and is observable.
1125 1126
    num_non_undefined = SafeRemoveArrayHoles(this);
  }
1127

1128
  QuickSort(this, 0, num_non_undefined);
1129

1130 1131 1132 1133 1134 1135
  if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
    // For compatibility with JSC, we shadow any elements in the prototype
    // chain that has become exposed by sort moving a hole to its position.
    ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
  }

1136
  return this;
1137
}
1138 1139 1140 1141 1142 1143


// The following functions cannot be made efficient on sparse arrays while
// preserving the semantics, since the calls to the receiver function can add
// or delete elements from the array.
function ArrayFilter(f, receiver) {
1144
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");
1145

1146 1147 1148 1149 1150
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = ToUint32(array.length);

1151
  if (!IS_SPEC_FUNCTION(f)) {
1152 1153
    throw MakeTypeError('called_non_callable', [ f ]);
  }
1154 1155
  if (IS_NULL_OR_UNDEFINED(receiver)) {
    receiver = %GetDefaultReceiver(f) || receiver;
1156
  } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1157
    receiver = ToObject(receiver);
1158
  }
1159

1160 1161 1162
  var result = new $Array();
  var accumulator = new InternalArray();
  var accumulator_length = 0;
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181
  if (%DebugCallbackSupportsStepping(f)) {
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(f);
        if (%_CallFunction(receiver, element, i, array, f)) {
          accumulator[accumulator_length++] = element;
        }
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        if (%_CallFunction(receiver, element, i, array, f)) {
          accumulator[accumulator_length++] = element;
        }
1182
      }
1183
    }
1184
    // End of duplicate.
1185
  }
1186
  %MoveArrayContents(accumulator, result);
1187
  return result;
1188
}
1189 1190 1191


function ArrayForEach(f, receiver) {
1192
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");
1193

1194 1195 1196 1197 1198
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = TO_UINT32(array.length);

1199
  if (!IS_SPEC_FUNCTION(f)) {
1200 1201
    throw MakeTypeError('called_non_callable', [ f ]);
  }
1202 1203
  if (IS_NULL_OR_UNDEFINED(receiver)) {
    receiver = %GetDefaultReceiver(f) || receiver;
1204
  } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1205
    receiver = ToObject(receiver);
1206
  }
1207

1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223
  if (%DebugCallbackSupportsStepping(f)) {
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(f);
        %_CallFunction(receiver, element, i, array, f);
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        %_CallFunction(receiver, element, i, array, f);
      }
1224
    }
1225
    // End of duplicate.
1226
  }
1227
}
1228 1229 1230 1231 1232


// Executes the function once for each element present in the
// array until it finds one where callback returns true.
function ArraySome(f, receiver) {
1233
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");
1234

1235 1236 1237 1238 1239
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = TO_UINT32(array.length);

1240
  if (!IS_SPEC_FUNCTION(f)) {
1241 1242
    throw MakeTypeError('called_non_callable', [ f ]);
  }
1243 1244
  if (IS_NULL_OR_UNDEFINED(receiver)) {
    receiver = %GetDefaultReceiver(f) || receiver;
1245
  } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1246
    receiver = ToObject(receiver);
1247
  }
1248

1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264
  if (%DebugCallbackSupportsStepping(f)) {
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(f);
        if (%_CallFunction(receiver, element, i, array, f)) return true;
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        if (%_CallFunction(receiver, element, i, array, f)) return true;
      }
1265
    }
1266
    // End of duplicate.
1267 1268
  }
  return false;
1269
}
1270 1271 1272


function ArrayEvery(f, receiver) {
1273
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");
1274

1275 1276 1277 1278 1279
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = TO_UINT32(array.length);

1280
  if (!IS_SPEC_FUNCTION(f)) {
1281 1282
    throw MakeTypeError('called_non_callable', [ f ]);
  }
1283 1284
  if (IS_NULL_OR_UNDEFINED(receiver)) {
    receiver = %GetDefaultReceiver(f) || receiver;
1285
  } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1286
    receiver = ToObject(receiver);
1287
  }
1288

1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304
  if (%DebugCallbackSupportsStepping(f)) {
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(f);
        if (!%_CallFunction(receiver, element, i, array, f)) return false;
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        if (!%_CallFunction(receiver, element, i, array, f)) return false;
      }
1305
    }
1306
    // End of duplicate.
1307 1308
  }
  return true;
1309
}
1310 1311

function ArrayMap(f, receiver) {
1312
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map");
1313

1314 1315 1316 1317 1318
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = TO_UINT32(array.length);

1319
  if (!IS_SPEC_FUNCTION(f)) {
1320 1321
    throw MakeTypeError('called_non_callable', [ f ]);
  }
1322 1323
  if (IS_NULL_OR_UNDEFINED(receiver)) {
    receiver = %GetDefaultReceiver(f) || receiver;
1324
  } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1325
    receiver = ToObject(receiver);
1326
  }
1327

1328 1329
  var result = new $Array();
  var accumulator = new InternalArray(length);
1330 1331 1332 1333 1334 1335 1336 1337
  if (%DebugCallbackSupportsStepping(f)) {
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(f);
        accumulator[i] = %_CallFunction(receiver, element, i, array, f);
      }
1338
    }
1339 1340 1341 1342 1343 1344 1345 1346 1347
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (var i = 0; i < length; i++) {
      if (i in array) {
        var element = array[i];
        accumulator[i] = %_CallFunction(receiver, element, i, array, f);
      }
    }
    // End of duplicate.
1348
  }
1349
  %MoveArrayContents(accumulator, result);
1350
  return result;
1351
}
1352 1353 1354


function ArrayIndexOf(element, index) {
1355
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1356

1357 1358
  var length = TO_UINT32(this.length);
  if (length == 0) return -1;
1359
  if (IS_UNDEFINED(index)) {
1360 1361 1362 1363
    index = 0;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from the end of the array.
1364 1365 1366 1367 1368
    if (index < 0) {
      index = length + index;
      // If index is still negative, search the entire array.
      if (index < 0) index = 0;
    }
1369
  }
1370 1371
  var min = index;
  var max = length;
lrn@chromium.org's avatar
lrn@chromium.org committed
1372
  if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1373 1374 1375 1376
    var indices = %GetArrayKeys(this, length);
    if (IS_NUMBER(indices)) {
      // It's an interval.
      max = indices;  // Capped by length already.
1377 1378
      // Fall through to loop below.
    } else {
1379
      if (indices.length == 0) return -1;
1380
      // Get all the keys in sorted order.
1381
      var sortedKeys = GetSortedArrayKeys(this, indices);
1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392
      var n = sortedKeys.length;
      var i = 0;
      while (i < n && sortedKeys[i] < index) i++;
      while (i < n) {
        var key = sortedKeys[i];
        if (!IS_UNDEFINED(key) && this[key] === element) return key;
        i++;
      }
      return -1;
    }
  }
1393
  // Lookup through the array.
1394
  if (!IS_UNDEFINED(element)) {
1395
    for (var i = min; i < max; i++) {
1396 1397 1398 1399
      if (this[i] === element) return i;
    }
    return -1;
  }
1400 1401
  // Lookup through the array.
  for (var i = min; i < max; i++) {
1402 1403
    if (IS_UNDEFINED(this[i]) && i in this) {
      return i;
1404 1405 1406
    }
  }
  return -1;
1407
}
1408 1409 1410


function ArrayLastIndexOf(element, index) {
1411
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1412

1413 1414
  var length = TO_UINT32(this.length);
  if (length == 0) return -1;
1415
  if (%_ArgumentsLength() < 2) {
1416 1417 1418 1419
    index = length - 1;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from end of the array.
1420
    if (index < 0) index += length;
1421
    // If index is still negative, do not search the array.
1422
    if (index < 0) return -1;
1423 1424
    else if (index >= length) index = length - 1;
  }
1425 1426
  var min = 0;
  var max = index;
lrn@chromium.org's avatar
lrn@chromium.org committed
1427
  if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1428 1429 1430 1431
    var indices = %GetArrayKeys(this, index + 1);
    if (IS_NUMBER(indices)) {
      // It's an interval.
      max = indices;  // Capped by index already.
1432 1433
      // Fall through to loop below.
    } else {
1434
      if (indices.length == 0) return -1;
1435
      // Get all the keys in sorted order.
1436
      var sortedKeys = GetSortedArrayKeys(this, indices);
1437 1438 1439 1440 1441 1442 1443 1444 1445
      var i = sortedKeys.length - 1;
      while (i >= 0) {
        var key = sortedKeys[i];
        if (!IS_UNDEFINED(key) && this[key] === element) return key;
        i--;
      }
      return -1;
    }
  }
1446
  // Lookup through the array.
1447
  if (!IS_UNDEFINED(element)) {
1448
    for (var i = max; i >= min; i--) {
1449 1450 1451 1452
      if (this[i] === element) return i;
    }
    return -1;
  }
1453
  for (var i = max; i >= min; i--) {
1454 1455
    if (IS_UNDEFINED(this[i]) && i in this) {
      return i;
1456 1457 1458
    }
  }
  return -1;
1459
}
1460 1461


1462
function ArrayReduce(callback, current) {
1463
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1464

1465 1466 1467 1468 1469
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
  var array = ToObject(this);
  var length = ToUint32(array.length);

1470
  if (!IS_SPEC_FUNCTION(callback)) {
1471 1472
    throw MakeTypeError('called_non_callable', [callback]);
  }
1473

1474 1475 1476
  var i = 0;
  find_initial: if (%_ArgumentsLength() < 2) {
    for (; i < length; i++) {
1477 1478
      current = array[i];
      if (!IS_UNDEFINED(current) || i in array) {
1479 1480 1481 1482 1483 1484 1485
        i++;
        break find_initial;
      }
    }
    throw MakeTypeError('reduce_no_initial', []);
  }

1486
  var receiver = %GetDefaultReceiver(callback);
1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505

  if (%DebugCallbackSupportsStepping(callback)) {
    for (; i < length; i++) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(callback);
        current =
          %_CallFunction(receiver, current, element, i, array, callback);
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (; i < length; i++) {
      if (i in array) {
        var element = array[i];
        current =
          %_CallFunction(receiver, current, element, i, array, callback);
      }
1506
    }
1507
    // End of duplicate.
1508 1509 1510 1511 1512
  }
  return current;
}

function ArrayReduceRight(callback, current) {
1513
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight");
1514

1515 1516 1517 1518 1519
  // Pull out the length so that side effects are visible before the
  // callback function is checked.
  var array = ToObject(this);
  var length = ToUint32(array.length);

1520
  if (!IS_SPEC_FUNCTION(callback)) {
1521 1522 1523
    throw MakeTypeError('called_non_callable', [callback]);
  }

1524
  var i = length - 1;
1525 1526
  find_initial: if (%_ArgumentsLength() < 2) {
    for (; i >= 0; i--) {
1527 1528
      current = array[i];
      if (!IS_UNDEFINED(current) || i in array) {
1529 1530 1531 1532 1533 1534 1535
        i--;
        break find_initial;
      }
    }
    throw MakeTypeError('reduce_no_initial', []);
  }

1536
  var receiver = %GetDefaultReceiver(callback);
1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555

  if (%DebugCallbackSupportsStepping(callback)) {
    for (; i >= 0; i--) {
      if (i in array) {
        var element = array[i];
        // Prepare break slots for debugger step in.
        %DebugPrepareStepInIfStepping(callback);
        current =
          %_CallFunction(receiver, current, element, i, array, callback);
      }
    }
  } else {
    // This is a duplicate of the previous loop sans debug stepping.
    for (; i >= 0; i--) {
      if (i in array) {
        var element = array[i];
        current =
          %_CallFunction(receiver, current, element, i, array, callback);
      }
1556
    }
1557
    // End of duplicate.
1558 1559 1560 1561
  }
  return current;
}

1562 1563 1564 1565
// ES5, 15.4.3.2
function ArrayIsArray(obj) {
  return IS_ARRAY(obj);
}
1566

1567 1568

// -------------------------------------------------------------------
1569

1570 1571
function SetUpArray() {
  %CheckIsBootstrapping();
1572

1573
  // Set up non-enumerable constructor property on the Array.prototype
1574
  // object.
1575
  %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
1576

1577
  // Set up non-enumerable functions on the Array object.
1578 1579 1580 1581
  InstallFunctions($Array, DONT_ENUM, $Array(
    "isArray", ArrayIsArray
  ));

1582 1583
  var specialFunctions = %SpecialArrayFunctions({});

1584
  var getFunction = function(name, jsBuiltin, len) {
1585 1586 1587 1588
    var f = jsBuiltin;
    if (specialFunctions.hasOwnProperty(name)) {
      f = specialFunctions[name];
    }
1589
    if (!IS_UNDEFINED(len)) {
1590 1591 1592
      %FunctionSetLength(f, len);
    }
    return f;
1593
  };
1594

1595
  // Set up non-enumerable functions of the Array.prototype object and
1596
  // set their names.
1597 1598
  // Manipulate the length of some of the functions to meet
  // expectations set by ECMA-262 or Mozilla.
1599
  InstallFunctions($Array.prototype, DONT_ENUM, $Array(
1600 1601 1602 1603 1604
    "toString", getFunction("toString", ArrayToString),
    "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
    "join", getFunction("join", ArrayJoin),
    "pop", getFunction("pop", ArrayPop),
    "push", getFunction("push", ArrayPush, 1),
1605
    "concat", getFunction("concat", ArrayConcat, 1),
1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
    "reverse", getFunction("reverse", ArrayReverse),
    "shift", getFunction("shift", ArrayShift),
    "unshift", getFunction("unshift", ArrayUnshift, 1),
    "slice", getFunction("slice", ArraySlice, 2),
    "splice", getFunction("splice", ArraySplice, 2),
    "sort", getFunction("sort", ArraySort),
    "filter", getFunction("filter", ArrayFilter, 1),
    "forEach", getFunction("forEach", ArrayForEach, 1),
    "some", getFunction("some", ArraySome, 1),
    "every", getFunction("every", ArrayEvery, 1),
    "map", getFunction("map", ArrayMap, 1),
    "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
    "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
    "reduce", getFunction("reduce", ArrayReduce, 1),
    "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1621
  ));
1622

1623
  %FinishArrayPrototypeSetup($Array.prototype);
1624 1625

  // The internal Array prototype doesn't need to be fancy, since it's never
1626 1627 1628
  // exposed to user code.
  // Adding only the functions that are actually used.
  SetUpLockedPrototype(InternalArray, $Array(), $Array(
1629
    "concat", getFunction("concat", ArrayConcat),
1630
    "indexOf", getFunction("indexOf", ArrayIndexOf),
1631 1632
    "join", getFunction("join", ArrayJoin),
    "pop", getFunction("pop", ArrayPop),
1633 1634
    "push", getFunction("push", ArrayPush),
    "splice", getFunction("splice", ArraySplice)
1635
  ));
1636 1637 1638 1639 1640 1641

  SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
    "join", getFunction("join", ArrayJoin),
    "pop", getFunction("pop", ArrayPop),
    "push", getFunction("push", ArrayPush)
  ));
1642
}
1643

1644
SetUpArray();