array.js 50.3 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
(function(global, utils) {
6

7 8
"use strict";

9 10
%CheckIsBootstrapping();

11 12 13
// -------------------------------------------------------------------
// Imports

14
var Delete;
15
var GlobalArray = global.Array;
16 17 18
var InternalArray = utils.InternalArray;
var InternalPackedArray = utils.InternalPackedArray;
var MathMin;
19 20 21 22
var ObjectHasOwnProperty;
var ObjectIsFrozen;
var ObjectIsSealed;
var ObjectToString;
23 24
var ToNumber;
var ToString;
25
var unscopablesSymbol = utils.ImportNow("unscopables_symbol");
26 27

utils.Import(function(from) {
28
  Delete = from.Delete;
29
  MathMin = from.MathMin;
30 31 32 33
  ObjectHasOwnProperty = from.ObjectHasOwnProperty;
  ObjectIsFrozen = from.ObjectIsFrozen;
  ObjectIsSealed = from.ObjectIsSealed;
  ObjectToString = from.ObjectToString;
34 35
  ToNumber = from.ToNumber;
  ToString = from.ToString;
36
});
37 38 39 40 41

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

// Global list of arrays visited during toString, toLocaleString and
// join invocations.
42
var visited_arrays = new InternalArray();
43 44 45 46


// Gets a sorted array of array keys.  Useful for operations on sparse
// arrays.  Dupes have not been removed.
47 48 49 50 51 52 53 54 55
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);
56
      }
57 58 59 60 61
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
62 63 64 65 66 67 68
      if (!IS_UNDEFINED(key)) {
        var e = array[key];
        if (!IS_UNDEFINED(e) || key in array) {
          keys.push(key);
        }
      }
    }
69
    %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
70 71 72 73 74
  }
  return keys;
}


75
function SparseJoinWithSeparatorJS(array, len, convert, separator) {
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
  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);
}


94 95 96 97 98
// 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;
99

100
  var elements = new InternalArray(keys_length);
101 102
  var elements_length = 0;

103 104 105 106
  for (var i = 0; i < keys_length; i++) {
    var key = keys[i];
    if (key != last_key) {
      var e = array[key];
107 108
      if (!IS_STRING(e)) e = convert(e);
      elements[elements_length++] = e;
109 110 111
      last_key = key;
    }
  }
112
  return %StringBuilderConcat(elements, elements_length, '');
113 114 115
}


116 117 118 119
function UseSparseVariant(array, length, is_array, touched) {
  // Only use the sparse variant on arrays that are likely to be sparse and the
  // number of elements touched in the operation is relatively small compared to
  // the overall size of the array.
120 121
  if (!is_array || length < 1000 || %IsObserved(array) ||
      %HasComplexElements(array)) {
122 123 124 125 126 127 128 129 130
    return false;
  }
  if (!%_IsSmi(length)) {
    return true;
  }
  var elements_threshold = length >> 2;  // No more than 75% holes
  var estimated_elements = %EstimateNumberOfElements(array);
  return (estimated_elements < elements_threshold) &&
    (touched > estimated_elements * 4);
131 132 133 134 135 136 137 138 139 140 141
}


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.
142
    if (!%PushIfAbsent(visited_arrays, array)) return '';
143 144 145 146
  }

  // Attempt to convert the elements.
  try {
147 148
    if (UseSparseVariant(array, length, is_array, length)) {
      %NormalizeElements(array);
149 150 151
      if (separator.length == 0) {
        return SparseJoin(array, length, convert);
      } else {
152
        return SparseJoinWithSeparatorJS(array, length, convert, separator);
153
      }
154 155
    }

156 157 158
    // Fast case for one-element arrays.
    if (length == 1) {
      var e = array[0];
159 160
      if (IS_STRING(e)) return e;
      return convert(e);
161 162
    }

163
    // Construct an array for the elements.
164
    var elements = new InternalArray(length);
165

166 167
    // We pull the empty separator check outside the loop for speed!
    if (separator.length == 0) {
168
      var elements_length = 0;
169 170
      for (var i = 0; i < length; i++) {
        var e = array[i];
171 172
        if (!IS_STRING(e)) e = convert(e);
        elements[elements_length++] = e;
173
      }
174
      elements.length = elements_length;
175
      var result = %_FastOneByteArrayJoin(elements, '');
176 177 178
      if (!IS_UNDEFINED(result)) return result;
      return %StringBuilderConcat(elements, elements_length, '');
    }
179
    // Non-empty separator case.
180
    // If the first element is a number then use the heuristic that the
181 182 183 184
    // remaining elements are also likely to be numbers.
    if (!IS_NUMBER(array[0])) {
      for (var i = 0; i < length; i++) {
        var e = array[i];
185 186
        if (!IS_STRING(e)) e = convert(e);
        elements[i] = e;
187
      }
188
    } else {
189 190
      for (var i = 0; i < length; i++) {
        var e = array[i];
191 192 193 194 195 196
        if (IS_NUMBER(e)) {
          e = %_NumberToString(e);
        } else if (!IS_STRING(e)) {
          e = convert(e);
        }
        elements[i] = e;
197
      }
198
    }
199
    var result = %_FastOneByteArrayJoin(elements, separator);
200
    if (!IS_UNDEFINED(result)) return result;
201

202
    return %StringBuilderJoin(elements, length, separator);
203
  } finally {
204 205 206
    // 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;
207
  }
208
}
209 210


211
function ConvertToString(x) {
212
  // Assumes x is a non-string.
213 214
  if (IS_NUMBER(x)) return %_NumberToString(x);
  if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
215
  return (IS_NULL_OR_UNDEFINED(x)) ? '' : ToString($defaultString(x));
216
}
217 218 219


function ConvertToLocaleString(e) {
220
  if (IS_NULL_OR_UNDEFINED(e)) {
221 222
    return '';
  } else {
223
    // According to ES5, section 15.4.4.3, the toLocaleString conversion
224 225
    // must throw a TypeError if ToObject(e).toLocaleString isn't
    // callable.
226
    var e_obj = TO_OBJECT(e);
227
    return ToString(e_obj.toLocaleString());
228
  }
229
}
230 231 232 233


// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
234
function SparseSlice(array, start_i, del_count, len, deleted_elements) {
235
  // Move deleted elements to a new array (the return value from splice).
236 237 238 239 240 241
  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) {
242
        %AddElement(deleted_elements, i - start_i, current);
243
      }
244 245 246 247 248
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
249 250 251 252
      if (!IS_UNDEFINED(key)) {
        if (key >= start_i) {
          var current = array[key];
          if (!IS_UNDEFINED(current) || key in array) {
253
            %AddElement(deleted_elements, key - start_i, current);
254 255 256 257 258
          }
        }
      }
    }
  }
259
}
260 261


262 263
// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
264
function SparseMove(array, start_i, del_count, len, num_additional_args) {
265 266
  // Bail out if no moving is necessary.
  if (num_additional_args === del_count) return;
267
  // Move data to new array.
268 269
  var new_array = new InternalArray(
      // Clamp array length to 2^32-1 to avoid early RangeError.
270
      MathMin(len - del_count + num_additional_args, 0xffffffff));
271
  var big_indices;
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
  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;
      }
    }
    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;
      }
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
      if (!IS_UNDEFINED(key)) {
        if (key < start_i) {
          var current = array[key];
          if (!IS_UNDEFINED(current) || key in array) {
            new_array[key] = current;
          }
        } else if (key >= start_i + del_count) {
          var current = array[key];
          if (!IS_UNDEFINED(current) || key in array) {
300 301
            var new_key = key - del_count + num_additional_args;
            new_array[new_key] = current;
302
            if (new_key > 0xfffffffe) {
303 304 305
              big_indices = big_indices || new InternalArray();
              big_indices.push(new_key);
            }
306 307 308 309 310 311 312
          }
        }
      }
    }
  }
  // Move contents of new_array into this array
  %MoveArrayContents(new_array, array);
313 314 315 316 317 318 319 320
  // Add any moved values that aren't elements anymore.
  if (!IS_UNDEFINED(big_indices)) {
    var length = big_indices.length;
    for (var i = 0; i < length; ++i) {
      var key = big_indices[i];
      array[key] = new_array[key];
    }
  }
321 322 323
}


324 325 326 327
// 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) {
328
  var is_array = IS_ARRAY(array);
329 330
  for (var i = 0; i < del_count; i++) {
    var index = start_i + i;
331
    if (HAS_INDEX(array, index, is_array)) {
332
      var current = array[index];
333 334
      // The spec requires [[DefineOwnProperty]] here, %AddElement is close
      // enough (in that it ignores the prototype).
335
      %AddElement(deleted_elements, i, current);
336
    }
337
  }
338
}
339 340


341
function SimpleMove(array, start_i, del_count, len, num_additional_args) {
342
  var is_array = IS_ARRAY(array);
343
  if (num_additional_args !== del_count) {
344 345 346 347 348 349
    // 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;
350
        if (HAS_INDEX(array, from_index, is_array)) {
351
          array[to_index] = array[from_index];
352 353 354 355 356 357 358 359
        } 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;
360
        if (HAS_INDEX(array, from_index, is_array)) {
361
          array[to_index] = array[from_index];
362 363 364 365 366 367 368 369 370
        } else {
          delete array[to_index];
        }
      }
      for (var i = len; i > len - del_count + num_additional_args; i--) {
        delete array[i - 1];
      }
    }
  }
371
}
372 373 374 375 376 377


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


function ArrayToString() {
378 379 380 381 382 383 384 385 386
  var array;
  var func;
  if (IS_ARRAY(this)) {
    func = this.join;
    if (func === ArrayJoin) {
      return Join(this, this.length, ',', ConvertToString);
    }
    array = this;
  } else {
387
    array = TO_OBJECT(this);
388
    func = array.join;
389
  }
390
  if (!IS_CALLABLE(func)) {
391
    return %_CallFunction(array, ObjectToString);
392 393
  }
  return %_CallFunction(array, func);
394
}
395 396


397 398
function InnerArrayToLocaleString(array, length) {
  var len = TO_UINT32(length);
399 400
  if (len === 0) return "";
  return Join(array, len, ',', ConvertToLocaleString);
401
}
402 403


404
function ArrayToLocaleString() {
405
  var array = TO_OBJECT(this);
406 407 408
  var arrayLen = array.length;
  return InnerArrayToLocaleString(array, arrayLen);
}
409

410 411

function InnerArrayJoin(separator, array, length) {
412 413 414
  if (IS_UNDEFINED(separator)) {
    separator = ',';
  } else if (!IS_STRING(separator)) {
415
    separator = $nonStringToString(separator);
416
  }
417

418
  var result = %_FastOneByteArrayJoin(array, separator);
419
  if (!IS_UNDEFINED(result)) return result;
420

421 422 423 424 425
  // Fast case for one-element arrays.
  if (length === 1) {
    var e = array[0];
    if (IS_STRING(e)) return e;
    if (IS_NULL_OR_UNDEFINED(e)) return '';
426
    return $nonStringToString(e);
427 428
  }

429
  return Join(array, length, separator, ConvertToString);
430
}
431 432


433 434 435
function ArrayJoin(separator) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");

436
  var array = TO_OBJECT(this);
437 438 439 440 441 442
  var length = TO_UINT32(array.length);

  return InnerArrayJoin(separator, array, length);
}


443 444 445 446 447
function ObservedArrayPop(n) {
  n--;
  var value = this[n];

  try {
448
    $observeBeginPerformSplice(this);
449 450 451
    delete this[n];
    this.length = n;
  } finally {
452 453
    $observeEndPerformSplice(this);
    $observeEnqueueSpliceRecord(this, n, [value], 0);
454 455 456 457 458
  }

  return value;
}

459

460 461 462
// Removes the last element from the array and returns it. See
// ECMA-262, section 15.4.4.6.
function ArrayPop() {
463
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
464

465
  var array = TO_OBJECT(this);
466
  var n = TO_UINT32(array.length);
467
  if (n == 0) {
468
    array.length = n;
469 470
    return;
  }
471

472 473
  if (%IsObserved(array))
    return ObservedArrayPop.call(array, n);
474

475
  n--;
476
  var value = array[n];
477
  Delete(array, n, true);
478
  array.length = n;
479
  return value;
480
}
481 482


483 484 485 486 487
function ObservedArrayPush() {
  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();

  try {
488
    $observeBeginPerformSplice(this);
489 490 491
    for (var i = 0; i < m; i++) {
      this[i+n] = %_Arguments(i);
    }
492 493
    var new_length = n + m;
    this.length = new_length;
494
  } finally {
495 496
    $observeEndPerformSplice(this);
    $observeEnqueueSpliceRecord(this, n, [], m);
497 498
  }

499
  return new_length;
500 501
}

502

503 504 505
// 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() {
506
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
507

508 509 510
  if (%IsObserved(this))
    return ObservedArrayPush.apply(this, arguments);

511
  var array = TO_OBJECT(this);
512 513 514
  var n = TO_UINT32(array.length);
  var m = %_ArgumentsLength();

515
  for (var i = 0; i < m; i++) {
516
    array[i+n] = %_Arguments(i);
517
  }
518 519

  var new_length = n + m;
520
  array.length = new_length;
521
  return new_length;
522
}
523 524


525 526 527
// 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.
528
function ArrayConcatJS(arg1) {  // length == 1
529
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.concat");
530

531
  var array = TO_OBJECT(this);
532
  var arg_count = %_ArgumentsLength();
533
  var arrays = new InternalArray(1 + arg_count);
534
  arrays[0] = array;
535 536
  for (var i = 0; i < arg_count; i++) {
    arrays[i + 1] = %_Arguments(i);
537 538
  }

539
  return %ArrayConcat(arrays);
540
}
541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556


// 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;
557
      while (keys[--high_counter] == j) { }
558 559 560 561
      low = j_complement;
    }
    if (j_complement >= i) {
      low = i;
562
      while (keys[++low_counter] == i) { }
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585
      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];
      }
    }
  }
}

586
function PackedArrayReverse(array, len) {
587
  var j = len - 1;
588
  for (var i = 0; i < j; i++, j--) {
589
    var current_i = array[i];
590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
    var current_j = array[j];
    array[i] = current_j;
    array[j] = current_i;
  }
  return array;
}


function GenericArrayReverse(array, len) {
  var j = len - 1;
  for (var i = 0; i < j; i++, j--) {
    if (i in array) {
      var current_i = array[i];
      if (j in array) {
        var current_j = array[j];
605 606
        array[i] = current_j;
        array[j] = current_i;
607
      } else {
608 609
        array[j] = current_i;
        delete array[i];
610 611
      }
    } else {
612 613
      if (j in array) {
        var current_j = array[j];
614 615
        array[i] = current_j;
        delete array[j];
616 617 618
      }
    }
  }
619
  return array;
620
}
621 622


623 624 625
function ArrayReverse() {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");

626
  var array = TO_OBJECT(this);
627
  var len = TO_UINT32(array.length);
628
  var isArray = IS_ARRAY(array);
629

630
  if (UseSparseVariant(array, len, isArray, len)) {
631 632 633
    %NormalizeElements(array);
    SparseReverse(array, len);
    return array;
634 635 636 637
  } else if (isArray && %_HasFastPackedElements(array)) {
    return PackedArrayReverse(array, len);
  } else {
    return GenericArrayReverse(array, len);
638 639 640 641
  }
}


642 643 644 645
function ObservedArrayShift(len) {
  var first = this[0];

  try {
646
    $observeBeginPerformSplice(this);
647 648 649
    SimpleMove(this, 0, 1, len, 0);
    this.length = len - 1;
  } finally {
650 651
    $observeEndPerformSplice(this);
    $observeEnqueueSpliceRecord(this, 0, [first], 0);
652 653 654 655 656
  }

  return first;
}

657

658
function ArrayShift() {
659
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
660

661
  var array = TO_OBJECT(this);
662
  var len = TO_UINT32(array.length);
663

664
  if (len === 0) {
665
    array.length = 0;
666 667
    return;
  }
668

669
  if (ObjectIsSealed(array)) throw MakeTypeError(kArrayFunctionsOnSealed);
670

671 672
  if (%IsObserved(array))
    return ObservedArrayShift.call(array, len);
673

674
  var first = array[0];
675

676 677
  if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
    SparseMove(array, 0, 1, len, 0);
678 679 680
  } else {
    SimpleMove(array, 0, 1, len, 0);
  }
681

682
  array.length = len - 1;
683

684
  return first;
685
}
686

687

688 689 690 691 692
function ObservedArrayUnshift() {
  var len = TO_UINT32(this.length);
  var num_arguments = %_ArgumentsLength();

  try {
693
    $observeBeginPerformSplice(this);
694 695 696 697
    SimpleMove(this, 0, 0, len, num_arguments);
    for (var i = 0; i < num_arguments; i++) {
      this[i] = %_Arguments(i);
    }
698 699
    var new_length = len + num_arguments;
    this.length = new_length;
700
  } finally {
701 702
    $observeEndPerformSplice(this);
    $observeEnqueueSpliceRecord(this, 0, [], num_arguments);
703 704
  }

705
  return new_length;
706
}
707

708

709
function ArrayUnshift(arg1) {  // length == 1
710
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
711

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

715
  var array = TO_OBJECT(this);
716 717
  var len = TO_UINT32(array.length);
  var num_arguments = %_ArgumentsLength();
718

719
  if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) &&
720
      !ObjectIsSealed(array)) {
721
    SparseMove(array, 0, 0, len, num_arguments);
722 723 724 725
  } else {
    SimpleMove(array, 0, 0, len, num_arguments);
  }

726
  for (var i = 0; i < num_arguments; i++) {
727
    array[i] = %_Arguments(i);
728
  }
729

730
  var new_length = len + num_arguments;
731
  array.length = new_length;
732
  return new_length;
733
}
734 735 736


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

739
  var array = TO_OBJECT(this);
740
  var len = TO_UINT32(array.length);
741 742
  var start_i = TO_INTEGER(start);
  var end_i = len;
743

744
  if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
745

746 747 748 749 750 751
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
752

753 754 755 756 757 758
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
759

760
  var result = [];
761 762 763

  if (end_i < start_i) return result;

764 765 766
  if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
    %NormalizeElements(array);
    %NormalizeElements(result);
767
    SparseSlice(array, start_i, end_i - start_i, len, result);
768
  } else {
769
    SimpleSlice(array, start_i, end_i - start_i, len, result);
770 771
  }

772
  result.length = end_i - start_i;
773

774
  return result;
775
}
776 777


778
function ComputeSpliceStartIndex(start_i, len) {
779 780
  if (start_i < 0) {
    start_i += len;
781
    return start_i < 0 ? 0 : start_i;
782
  }
783

784 785 786 787 788
  return start_i > len ? len : start_i;
}


function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
789
  // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
790 791
  // given as a request to delete all the elements from the start.
  // And it differs from the case of undefined delete count.
792 793 794
  // This does not follow ECMA-262, but we do the same for
  // compatibility.
  var del_count = 0;
795 796 797 798 799 800 801 802 803 804 805 806
  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;
}
807

808 809 810 811 812 813 814

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);
815 816
  var deleted_elements = [];
  deleted_elements.length = del_count;
817 818 819
  var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;

  try {
820
    $observeBeginPerformSplice(this);
821

822 823 824 825 826 827 828 829 830 831 832 833 834 835
    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 {
836
    $observeEndPerformSplice(this);
837
    if (deleted_elements.length || num_elements_to_add) {
838 839 840 841
      $observeEnqueueSpliceRecord(this,
                                  start_i,
                                  deleted_elements.slice(),
                                  num_elements_to_add);
842
    }
843
  }
844

845 846 847 848 849 850
  // Return the deleted elements.
  return deleted_elements;
}


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

853 854 855 856
  if (%IsObserved(this))
    return ObservedArraySplice.apply(this, arguments);

  var num_arguments = %_ArgumentsLength();
857
  var array = TO_OBJECT(this);
858
  var len = TO_UINT32(array.length);
859 860 861 862 863 864 865
  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;

866
  if (del_count != num_elements_to_add && ObjectIsSealed(array)) {
867
    throw MakeTypeError(kArrayFunctionsOnSealed);
868
  } else if (del_count > 0 && ObjectIsFrozen(array)) {
869
    throw MakeTypeError(kArrayFunctionsOnFrozen);
870 871
  }

872 873 874 875 876
  var changed_elements = del_count;
  if (num_elements_to_add != del_count) {
    // If the slice needs to do a actually move elements after the insertion
    // point, then include those in the estimate of changed elements.
    changed_elements += len - start_i - del_count;
877
  }
878 879 880
  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
    %NormalizeElements(array);
    %NormalizeElements(deleted_elements);
881 882
    SparseSlice(array, start_i, del_count, len, deleted_elements);
    SparseMove(array, start_i, del_count, len, num_elements_to_add);
883 884 885 886
  } else {
    SimpleSlice(array, start_i, del_count, len, deleted_elements);
    SimpleMove(array, start_i, del_count, len, num_elements_to_add);
  }
887

888 889 890 891 892 893
  // 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) {
894
    array[i++] = %_Arguments(arguments_index++);
895
  }
896
  array.length = len - del_count + num_elements_to_add;
897

898 899
  // Return the deleted elements.
  return deleted_elements;
900
}
901 902


903
function InnerArraySort(length, comparefn) {
olehougaard's avatar
olehougaard committed
904
  // In-place QuickSort algorithm.
olehougaard's avatar
olehougaard committed
905
  // For short (length <= 22) arrays, insertion sort is used for efficiency.
906

907
  if (!IS_CALLABLE(comparefn)) {
908 909 910 911
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
912
      }
913 914
      x = ToString(x);
      y = ToString(y);
915 916 917
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
918
  }
919
  var InsertionSort = function InsertionSort(a, from, to) {
olehougaard's avatar
olehougaard committed
920 921
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
922 923
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
924
        var order = %_CallFunction(UNDEFINED, tmp, element, comparefn);
925 926
        if (order > 0) {
          a[j + 1] = tmp;
olehougaard's avatar
olehougaard committed
927
        } else {
928
          break;
olehougaard's avatar
olehougaard committed
929 930
        }
      }
931
      a[j + 1] = element;
olehougaard's avatar
olehougaard committed
932
    }
933
  };
934

935 936 937 938
  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);
939 940
    for (var i = from + 1, j = 0; i < to - 1; i += increment, j++) {
      t_array[j] = [i, a[i]];
941
    }
942
    %_CallFunction(t_array, function(a, b) {
943
      return %_CallFunction(UNDEFINED, a[1], b[1], comparefn);
944
    }, ArraySort);
945 946 947 948
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

949
  var QuickSort = function QuickSort(a, from, to) {
950
    var third_index = 0;
951 952 953 954 955
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
956
      }
957 958 959 960 961
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
962 963 964
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
965
      var v2 = a[third_index];
966
      var c01 = %_CallFunction(UNDEFINED, v0, v1, comparefn);
967 968 969 970 971 972
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
973
      var c02 = %_CallFunction(UNDEFINED, v0, v2, comparefn);
974 975 976 977 978 979 980 981
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
982
        var c12 = %_CallFunction(UNDEFINED, v1, v2, comparefn);
983 984 985 986 987 988 989 990 991 992 993 994 995
        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.
996
      a[third_index] = a[low_end];
997 998 999 1000 1001 1002
      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];
1003
        var order = %_CallFunction(UNDEFINED, element, pivot, comparefn);
1004
        if (order < 0) {
1005 1006
          a[i] = a[low_end];
          a[low_end] = element;
1007
          low_end++;
1008 1009 1010 1011 1012
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
1013
            order = %_CallFunction(UNDEFINED, top_elem, pivot, comparefn);
1014 1015 1016 1017 1018 1019 1020 1021 1022
          } 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++;
          }
1023
        }
1024
      }
1025 1026 1027 1028 1029 1030 1031
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
1032
    }
1033
  };
1034

1035 1036
  // 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
1037
  // of a prototype property.
1038
  var CopyFromPrototype = function CopyFromPrototype(obj, length) {
1039
    var max = 0;
arv's avatar
arv committed
1040
    for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
1041
      var indices = %GetArrayKeys(proto, length);
1042 1043 1044 1045
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = 0; i < proto_length; i++) {
1046
          if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
1047 1048
            obj[i] = proto[i];
            if (i >= max) { max = i + 1; }
1049
          }
1050 1051 1052 1053
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
1054 1055
          if (!IS_UNDEFINED(index) && !HAS_OWN_PROPERTY(obj, index)
              && HAS_OWN_PROPERTY(proto, index)) {
1056 1057
            obj[index] = proto[index];
            if (index >= max) { max = index + 1; }
1058 1059 1060 1061 1062
          }
        }
      }
    }
    return max;
1063
  };
1064 1065 1066 1067

  // 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.
1068
  var ShadowPrototypeElements = function(obj, from, to) {
arv's avatar
arv committed
1069
    for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
1070
      var indices = %GetArrayKeys(proto, to);
1071 1072 1073 1074
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = from; i < proto_length; i++) {
1075
          if (HAS_OWN_PROPERTY(proto, i)) {
1076
            obj[i] = UNDEFINED;
1077
          }
1078 1079 1080 1081 1082
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
          if (!IS_UNDEFINED(index) && from <= index &&
1083
              HAS_OWN_PROPERTY(proto, index)) {
1084
            obj[index] = UNDEFINED;
1085 1086 1087 1088
          }
        }
      }
    }
1089
  };
1090

1091
  var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
    // 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.
1106
      if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
1107 1108 1109 1110 1111 1112
        num_holes++;
      }

      // Find last defined element.
      while (first_undefined < last_defined &&
             IS_UNDEFINED(obj[last_defined])) {
1113
        if (!HAS_OWN_PROPERTY(obj, last_defined)) {
1114 1115 1116 1117 1118 1119 1120
          num_holes++;
        }
        last_defined--;
      }
      if (first_undefined < last_defined) {
        // Fill in hole or undefined.
        obj[first_undefined] = obj[last_defined];
1121
        obj[last_defined] = UNDEFINED;
1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132
      }
    }
    // 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++) {
1133
      obj[i] = UNDEFINED;
1134 1135 1136
    }
    for (i = length - num_holes; i < length; i++) {
      // For compatability with Webkit, do not expose elements in the prototype.
arv's avatar
arv committed
1137
      if (i in %_GetPrototype(obj)) {
1138
        obj[i] = UNDEFINED;
1139 1140 1141 1142 1143 1144 1145
      } else {
        delete obj[i];
      }
    }

    // Return the number of defined elements.
    return first_undefined;
1146
  };
1147

1148
  if (length < 2) return this;
1149

1150 1151 1152 1153 1154 1155
  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
1156
    // own elements. This is not very efficient, but sorting with
1157 1158 1159 1160 1161 1162 1163
    // 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);
  }

1164 1165
  // %RemoveArrayHoles returns -1 if fast removal is not supported.
  var num_non_undefined = %RemoveArrayHoles(this, length);
1166

1167
  if (num_non_undefined == -1) {
1168 1169 1170
    // 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.
1171 1172
    num_non_undefined = SafeRemoveArrayHoles(this);
  }
1173

1174
  QuickSort(this, 0, num_non_undefined);
1175

1176 1177 1178 1179 1180 1181
  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);
  }

1182
  return this;
1183
}
1184 1185


1186 1187 1188
function ArraySort(comparefn) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");

1189
  var array = TO_OBJECT(this);
1190 1191
  var length = TO_UINT32(array.length);
  return %_CallFunction(array, length, comparefn, InnerArraySort);
1192 1193 1194
}


1195 1196 1197
// 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.
1198
function InnerArrayFilter(f, receiver, array, length) {
1199
  if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1200
  var needs_wrapper = false;
1201 1202 1203
  if (IS_NULL(receiver)) {
    if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
  } else if (!IS_UNDEFINED(receiver)) {
1204
    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1205
  }
1206

1207 1208
  var accumulator = new InternalArray();
  var accumulator_length = 0;
1209
  var is_array = IS_ARRAY(array);
1210
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1211
  for (var i = 0; i < length; i++) {
1212
    if (HAS_INDEX(array, i, is_array)) {
1213 1214 1215
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(f);
1216
      var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
1217
      if (%_CallFunction(new_receiver, element, i, array, f)) {
1218
        accumulator[accumulator_length++] = element;
1219
      }
1220 1221
    }
  }
1222 1223 1224 1225 1226 1227 1228 1229
  return accumulator;
}

function ArrayFilter(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1230
  var array = TO_OBJECT(this);
1231
  var length = TO_UINT32(array.length);
1232 1233
  var accumulator = InnerArrayFilter(f, receiver, array, length);
  var result = new GlobalArray();
1234
  %MoveArrayContents(accumulator, result);
1235
  return result;
1236
}
1237

1238
function InnerArrayForEach(f, receiver, array, length) {
1239
  if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1240
  var needs_wrapper = false;
1241 1242 1243
  if (IS_NULL(receiver)) {
    if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
  } else if (!IS_UNDEFINED(receiver)) {
1244
    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1245
  }
1246

1247
  var is_array = IS_ARRAY(array);
1248
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1249
  for (var i = 0; i < length; i++) {
1250
    if (HAS_INDEX(array, i, is_array)) {
1251 1252 1253
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(f);
1254
      var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
1255
      %_CallFunction(new_receiver, element, i, array, f);
1256 1257
    }
  }
1258
}
1259

1260 1261 1262 1263 1264
function ArrayForEach(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1265
  var array = TO_OBJECT(this);
1266 1267 1268 1269
  var length = TO_UINT32(array.length);
  InnerArrayForEach(f, receiver, array, length);
}

1270

1271
function InnerArraySome(f, receiver, array, length) {
1272
  if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1273
  var needs_wrapper = false;
1274 1275 1276
  if (IS_NULL(receiver)) {
    if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
  } else if (!IS_UNDEFINED(receiver)) {
1277
    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1278
  }
1279

1280
  var is_array = IS_ARRAY(array);
1281
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1282
  for (var i = 0; i < length; i++) {
1283
    if (HAS_INDEX(array, i, is_array)) {
1284 1285 1286
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(f);
1287
      var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
1288
      if (%_CallFunction(new_receiver, element, i, array, f)) return true;
1289
    }
1290 1291
  }
  return false;
1292
}
1293 1294


1295 1296 1297 1298 1299 1300 1301
// Executes the function once for each element present in the
// array until it finds one where callback returns true.
function ArraySome(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1302
  var array = TO_OBJECT(this);
1303 1304 1305 1306 1307
  var length = TO_UINT32(array.length);
  return InnerArraySome(f, receiver, array, length);
}


1308
function InnerArrayEvery(f, receiver, array, length) {
1309
  if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1310
  var needs_wrapper = false;
1311 1312 1313
  if (IS_NULL(receiver)) {
    if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
  } else if (!IS_UNDEFINED(receiver)) {
1314
    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1315
  }
1316

1317
  var is_array = IS_ARRAY(array);
1318
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1319
  for (var i = 0; i < length; i++) {
1320
    if (HAS_INDEX(array, i, is_array)) {
1321 1322 1323
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(f);
1324
      var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
1325
      if (!%_CallFunction(new_receiver, element, i, array, f)) return false;
1326
    }
1327 1328
  }
  return true;
1329
}
1330

1331 1332 1333 1334 1335
function ArrayEvery(f, receiver) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1336
  var array = TO_OBJECT(this);
1337 1338 1339 1340
  var length = TO_UINT32(array.length);
  return InnerArrayEvery(f, receiver, array, length);
}

1341

1342
function InnerArrayMap(f, receiver, array, length) {
1343
  if (!IS_CALLABLE(f)) throw MakeTypeError(kCalledNonCallable, f);
1344
  var needs_wrapper = false;
1345 1346 1347
  if (IS_NULL(receiver)) {
    if (%IsSloppyModeFunction(f)) receiver = UNDEFINED;
  } else if (!IS_UNDEFINED(receiver)) {
1348
    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1349
  }
1350

1351
  var accumulator = new InternalArray(length);
1352
  var is_array = IS_ARRAY(array);
1353
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1354
  for (var i = 0; i < length; i++) {
1355
    if (HAS_INDEX(array, i, is_array)) {
1356 1357 1358
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(f);
1359
      var new_receiver = needs_wrapper ? TO_OBJECT(receiver) : receiver;
1360
      accumulator[i] = %_CallFunction(new_receiver, element, i, array, f);
1361 1362
    }
  }
1363 1364 1365 1366 1367 1368 1369 1370 1371
  return accumulator;
}


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

  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1372
  var array = TO_OBJECT(this);
1373 1374 1375
  var length = TO_UINT32(array.length);
  var accumulator = InnerArrayMap(f, receiver, array, length);
  var result = new GlobalArray();
1376
  %MoveArrayContents(accumulator, result);
1377
  return result;
1378
}
1379 1380


1381 1382 1383 1384 1385
// For .indexOf, we don't need to pass in the number of arguments
// at the callsite since ToInteger(undefined) == 0; however, for
// .lastIndexOf, we need to pass it, since the behavior for passing
// undefined is 0 but for not including the argument is length-1.
function InnerArrayIndexOf(element, index, length) {
1386
  if (length == 0) return -1;
1387
  if (IS_UNDEFINED(index)) {
1388 1389 1390 1391
    index = 0;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from the end of the array.
1392 1393 1394 1395 1396
    if (index < 0) {
      index = length + index;
      // If index is still negative, search the entire array.
      if (index < 0) index = 0;
    }
1397
  }
1398 1399
  var min = index;
  var max = length;
1400 1401
  if (UseSparseVariant(this, length, IS_ARRAY(this), max - min)) {
    %NormalizeElements(this);
1402 1403 1404 1405
    var indices = %GetArrayKeys(this, length);
    if (IS_NUMBER(indices)) {
      // It's an interval.
      max = indices;  // Capped by length already.
1406 1407
      // Fall through to loop below.
    } else {
1408
      if (indices.length == 0) return -1;
1409
      // Get all the keys in sorted order.
1410
      var sortedKeys = GetSortedArrayKeys(this, indices);
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421
      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;
    }
  }
1422
  // Lookup through the array.
1423
  if (!IS_UNDEFINED(element)) {
1424
    for (var i = min; i < max; i++) {
1425 1426 1427 1428
      if (this[i] === element) return i;
    }
    return -1;
  }
1429 1430
  // Lookup through the array.
  for (var i = min; i < max; i++) {
1431 1432
    if (IS_UNDEFINED(this[i]) && i in this) {
      return i;
1433 1434 1435
    }
  }
  return -1;
1436
}
1437 1438


1439 1440
function ArrayIndexOf(element, index) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1441

1442
  var length = TO_UINT32(this.length);
1443 1444 1445 1446 1447
  return %_CallFunction(this, element, index, length, InnerArrayIndexOf);
}


function InnerArrayLastIndexOf(element, index, length, argumentsLength) {
1448
  if (length == 0) return -1;
1449
  if (argumentsLength < 2) {
1450 1451 1452 1453
    index = length - 1;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from end of the array.
1454
    if (index < 0) index += length;
1455
    // If index is still negative, do not search the array.
1456
    if (index < 0) return -1;
1457 1458
    else if (index >= length) index = length - 1;
  }
1459 1460
  var min = 0;
  var max = index;
1461 1462
  if (UseSparseVariant(this, length, IS_ARRAY(this), index)) {
    %NormalizeElements(this);
1463 1464 1465 1466
    var indices = %GetArrayKeys(this, index + 1);
    if (IS_NUMBER(indices)) {
      // It's an interval.
      max = indices;  // Capped by index already.
1467 1468
      // Fall through to loop below.
    } else {
1469
      if (indices.length == 0) return -1;
1470
      // Get all the keys in sorted order.
1471
      var sortedKeys = GetSortedArrayKeys(this, indices);
1472 1473 1474 1475 1476 1477 1478 1479 1480
      var i = sortedKeys.length - 1;
      while (i >= 0) {
        var key = sortedKeys[i];
        if (!IS_UNDEFINED(key) && this[key] === element) return key;
        i--;
      }
      return -1;
    }
  }
1481
  // Lookup through the array.
1482
  if (!IS_UNDEFINED(element)) {
1483
    for (var i = max; i >= min; i--) {
1484 1485 1486 1487
      if (this[i] === element) return i;
    }
    return -1;
  }
1488
  for (var i = max; i >= min; i--) {
1489 1490
    if (IS_UNDEFINED(this[i]) && i in this) {
      return i;
1491 1492 1493
    }
  }
  return -1;
1494
}
1495 1496


1497 1498 1499 1500 1501 1502 1503 1504 1505
function ArrayLastIndexOf(element, index) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");

  var length = TO_UINT32(this.length);
  return %_CallFunction(this, element, index, length,
                        %_ArgumentsLength(), InnerArrayLastIndexOf);
}


1506
function InnerArrayReduce(callback, current, array, length, argumentsLength) {
1507
  if (!IS_CALLABLE(callback)) {
1508
    throw MakeTypeError(kCalledNonCallable, callback);
1509
  }
1510

1511
  var is_array = IS_ARRAY(array);
1512
  var i = 0;
1513
  find_initial: if (argumentsLength < 2) {
1514
    for (; i < length; i++) {
1515
      if (HAS_INDEX(array, i, is_array)) {
1516
        current = array[i++];
1517 1518 1519
        break find_initial;
      }
    }
1520
    throw MakeTypeError(kReduceNoInitial);
1521 1522
  }

1523
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1524
  for (; i < length; i++) {
1525
    if (HAS_INDEX(array, i, is_array)) {
1526 1527 1528
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(callback);
1529
      current = %_CallFunction(UNDEFINED, current, element, i, array, callback);
1530
    }
1531 1532 1533 1534
  }
  return current;
}

1535

1536 1537
function ArrayReduce(callback, current) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1538

1539 1540
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping and side effects are visible.
1541
  var array = TO_OBJECT(this);
1542
  var length = TO_UINT32(array.length);
1543 1544 1545 1546
  return InnerArrayReduce(callback, current, array, length,
                          %_ArgumentsLength());
}

1547

1548 1549
function InnerArrayReduceRight(callback, current, array, length,
                               argumentsLength) {
1550
  if (!IS_CALLABLE(callback)) {
1551
    throw MakeTypeError(kCalledNonCallable, callback);
1552 1553
  }

1554
  var is_array = IS_ARRAY(array);
1555
  var i = length - 1;
1556
  find_initial: if (argumentsLength < 2) {
1557
    for (; i >= 0; i--) {
1558
      if (HAS_INDEX(array, i, is_array)) {
1559
        current = array[i--];
1560 1561 1562
        break find_initial;
      }
    }
1563
    throw MakeTypeError(kReduceNoInitial);
1564 1565
  }

1566
  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1567
  for (; i >= 0; i--) {
1568
    if (HAS_INDEX(array, i, is_array)) {
1569 1570 1571
      var element = array[i];
      // Prepare break slots for debugger step in.
      if (stepping) %DebugPrepareStepInIfStepping(callback);
1572
      current = %_CallFunction(UNDEFINED, current, element, i, array, callback);
1573 1574 1575 1576 1577
    }
  }
  return current;
}

1578 1579 1580 1581 1582 1583

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

  // Pull out the length so that side effects are visible before the
  // callback function is checked.
1584
  var array = TO_OBJECT(this);
1585
  var length = TO_UINT32(array.length);
1586 1587 1588 1589
  return InnerArrayReduceRight(callback, current, array, length,
                               %_ArgumentsLength());
}

1590 1591 1592 1593
// ES5, 15.4.3.2
function ArrayIsArray(obj) {
  return IS_ARRAY(obj);
}
1594

1595 1596

// -------------------------------------------------------------------
1597

1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613
// Set up non-enumerable constructor property on the Array.prototype
// object.
%AddNamedProperty(GlobalArray.prototype, "constructor", GlobalArray,
                  DONT_ENUM);

// Set up unscopable properties on the Array.prototype object.
var unscopables = {
  __proto__: null,
  copyWithin: true,
  entries: true,
  fill: true,
  find: true,
  findIndex: true,
  keys: true,
};

1614
%AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables,
1615 1616 1617
                  DONT_ENUM | READ_ONLY);

// Set up non-enumerable functions on the Array object.
1618
utils.InstallFunctions(GlobalArray, DONT_ENUM, [
1619 1620 1621
  "isArray", ArrayIsArray
]);

1622
var specialFunctions = %SpecialArrayFunctions();
1623

1624 1625 1626 1627 1628 1629 1630 1631 1632 1633
var getFunction = function(name, jsBuiltin, len) {
  var f = jsBuiltin;
  if (specialFunctions.hasOwnProperty(name)) {
    f = specialFunctions[name];
  }
  if (!IS_UNDEFINED(len)) {
    %FunctionSetLength(f, len);
  }
  return f;
};
1634 1635 1636 1637 1638

// Set up non-enumerable functions of the Array.prototype object and
// set their names.
// Manipulate the length of some of the functions to meet
// expectations set by ECMA-262 or Mozilla.
1639
utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [
1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660
  "toString", getFunction("toString", ArrayToString),
  "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush, 1),
  "concat", getFunction("concat", ArrayConcatJS, 1),
  "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)
1661 1662 1663 1664 1665 1666 1667
]);

%FinishArrayPrototypeSetup(GlobalArray.prototype);

// The internal Array prototype doesn't need to be fancy, since it's never
// exposed to user code.
// Adding only the functions that are actually used.
1668
utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [
1669 1670 1671 1672 1673 1674 1675
  "concat", getFunction("concat", ArrayConcatJS),
  "indexOf", getFunction("indexOf", ArrayIndexOf),
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush),
  "shift", getFunction("shift", ArrayShift),
  "splice", getFunction("splice", ArraySplice)
1676 1677
]);

1678
utils.SetUpLockedPrototype(InternalPackedArray, GlobalArray(), [
1679 1680 1681 1682
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush),
  "shift", getFunction("shift", ArrayShift)
1683 1684
]);

1685 1686 1687 1688
// -------------------------------------------------------------------
// Exports

utils.Export(function(to) {
1689
  to.ArrayIndexOf = ArrayIndexOf;
1690
  to.ArrayJoin = ArrayJoin;
1691
  to.ArrayPush = ArrayPush;
1692
  to.ArrayToString = ArrayToString;
1693 1694 1695 1696
  to.InnerArrayEvery = InnerArrayEvery;
  to.InnerArrayFilter = InnerArrayFilter;
  to.InnerArrayForEach = InnerArrayForEach;
  to.InnerArrayIndexOf = InnerArrayIndexOf;
1697
  to.InnerArrayJoin = InnerArrayJoin;
1698 1699
  to.InnerArrayLastIndexOf = InnerArrayLastIndexOf;
  to.InnerArrayMap = InnerArrayMap;
1700 1701
  to.InnerArrayReduce = InnerArrayReduce;
  to.InnerArrayReduceRight = InnerArrayReduceRight;
1702 1703
  to.InnerArraySome = InnerArraySome;
  to.InnerArraySort = InnerArraySort;
1704
  to.InnerArrayToLocaleString = InnerArrayToLocaleString;
1705
  to.PackedArrayReverse = PackedArrayReverse;
1706 1707
});

1708
%InstallToContext([
1709
  "array_concat", ArrayConcatJS,
1710 1711 1712 1713 1714 1715 1716
  "array_pop", ArrayPop,
  "array_push", ArrayPush,
  "array_shift", ArrayShift,
  "array_splice", ArraySplice,
  "array_slice", ArraySlice,
  "array_unshift", ArrayUnshift,
]);
1717

1718
});