array.js 39.1 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, extrasUtils) {
6

7 8
"use strict";

9 10
%CheckIsBootstrapping();

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

14 15
var GetIterator;
var GetMethod;
16
var GlobalArray = global.Array;
17 18
var InternalArray = utils.InternalArray;
var InternalPackedArray = utils.InternalPackedArray;
19
var MaxSimple;
20
var MinSimple;
21 22
var ObjectHasOwnProperty = global.Object.prototype.hasOwnProperty;
var ObjectToString = global.Object.prototype.toString;
23
var iteratorSymbol = utils.ImportNow("iterator_symbol");
24
var unscopablesSymbol = utils.ImportNow("unscopables_symbol");
25 26

utils.Import(function(from) {
27 28 29
  GetIterator = from.GetIterator;
  GetMethod = from.GetMethod;
  MaxSimple = from.MaxSimple;
30
  MinSimple = from.MinSimple;
31
});
32 33 34

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

35 36

function ArraySpeciesCreate(array, length) {
37
  length = INVERT_NEG_ZERO(length);
38
  var constructor = %ArraySpeciesConstructor(array);
39 40 41 42
  return new constructor(length);
}


43 44 45
function KeySortCompare(a, b) {
  return a - b;
}
46

47 48 49 50
function GetSortedArrayKeys(array, indices) {
  if (IS_NUMBER(indices)) {
    // It's an interval
    var limit = indices;
51
    var keys = new InternalArray();
52 53 54 55
    for (var i = 0; i < limit; ++i) {
      var e = array[i];
      if (!IS_UNDEFINED(e) || i in array) {
        keys.push(i);
56
      }
57
    }
58
    return keys;
59
  }
60
  return InnerArraySort(indices, indices.length, KeySortCompare);
61 62 63
}


64
function SparseJoinWithSeparatorJS(array, keys, length, use_locale, separator) {
65 66 67
  var keys_length = keys.length;
  var elements = new InternalArray(keys_length * 2);
  for (var i = 0; i < keys_length; i++) {
68
    var key = keys[i];
69
    elements[i * 2] = key;
70
    elements[i * 2 + 1] = ConvertToString(use_locale, array[key]);
71
  }
72
  return %SparseJoinWithSeparator(elements, length, separator);
73 74 75
}


76
// Optimized for sparse arrays if separator is ''.
77
function SparseJoin(array, keys, use_locale) {
78
  var keys_length = keys.length;
79
  var elements = new InternalArray(keys_length);
80
  for (var i = 0; i < keys_length; i++) {
81
    elements[i] = ConvertToString(use_locale, array[keys[i]]);
82
  }
83
  return %StringBuilderConcat(elements, keys_length, '');
84 85 86
}


87 88 89 90
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.
91
  if (!is_array || length < 1000 || %HasComplexElements(array)) {
92 93 94 95 96 97 98 99 100
    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);
101 102
}

103 104 105 106
function Stack() {
  this.length = 0;
  this.values = new InternalArray();
}
107

108 109 110 111
// Predeclare the instance variables on the prototype. Otherwise setting them in
// the constructor will leak the instance through settings on Object.prototype.
Stack.prototype.length = null;
Stack.prototype.values = null;
112

113 114 115
function StackPush(stack, value) {
  stack.values[stack.length++] = value;
}
116

117 118 119 120 121 122 123 124 125
function StackPop(stack) {
  stack.values[--stack.length] = null
}

function StackHas(stack, v) {
  var length = stack.length;
  var values = stack.values;
  for (var i = 0; i < length; i++) {
    if (values[i] === v) return true;
126
  }
127 128
  return false;
}
129

130 131 132
// Global list of arrays visited during toString, toLocaleString and
// join invocations.
var visited_arrays = new Stack();
133

134
function DoJoin(array, length, is_array, separator, use_locale) {
135 136 137 138 139
  if (UseSparseVariant(array, length, is_array, length)) {
    %NormalizeElements(array);
    var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length));
    if (separator === '') {
      if (keys.length === 0) return '';
140
      return SparseJoin(array, keys, use_locale);
141
    } else {
142 143
      return SparseJoinWithSeparatorJS(
          array, keys, length, use_locale, separator);
144
    }
145
  }
146

147 148
  // Fast case for one-element arrays.
  if (length === 1) {
149
    return ConvertToString(use_locale, array[0]);
150
  }
151

152 153
  // Construct an array for the elements.
  var elements = new InternalArray(length);
154 155 156
  for (var i = 0; i < length; i++) {
    elements[i] = ConvertToString(use_locale, array[i]);
  }
157 158 159

  if (separator === '') {
    return %StringBuilderConcat(elements, length, '');
160
  } else {
161
    return %StringBuilderJoin(elements, length, separator);
162 163 164
  }
}

165
function Join(array, length, separator, use_locale) {
166 167 168 169 170 171 172 173 174 175 176 177 178
  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.
    if (StackHas(visited_arrays, array)) return '';
    StackPush(visited_arrays, array);
  }

  // Attempt to convert the elements.
  try {
179
    return DoJoin(array, length, is_array, separator, use_locale);
180
  } finally {
181 182
    // Make sure to remove the last element of the visited array no
    // matter what happens.
183
    if (is_array) StackPop(visited_arrays);
184
  }
185
}
186 187


188
function ConvertToString(use_locale, x) {
189
  if (IS_NULL_OR_UNDEFINED(x)) return '';
190
  return TO_STRING(use_locale ? x.toLocaleString() : x);
191
}
192 193 194 195


// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
196
function SparseSlice(array, start_i, del_count, len, deleted_elements) {
197
  // Move deleted elements to a new array (the return value from splice).
198 199 200 201 202 203
  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) {
204
        %CreateDataProperty(deleted_elements, i - start_i, current);
205
      }
206 207 208 209 210
    }
  } else {
    var length = indices.length;
    for (var k = 0; k < length; ++k) {
      var key = indices[k];
211 212 213
      if (key >= start_i) {
        var current = array[key];
        if (!IS_UNDEFINED(current) || key in array) {
214
          %CreateDataProperty(deleted_elements, key - start_i, current);
215 216 217 218
        }
      }
    }
  }
219
}
220 221


222 223
// This function implements the optimized splice implementation that can use
// special array operations to handle sparse arrays in a sensible fashion.
224
function SparseMove(array, start_i, del_count, len, num_additional_args) {
225 226
  // Bail out if no moving is necessary.
  if (num_additional_args === del_count) return;
227
  // Move data to new array.
228 229
  var new_array = new InternalArray(
      // Clamp array length to 2^32-1 to avoid early RangeError.
230
      MinSimple(len - del_count + num_additional_args, 0xffffffff));
231
  var big_indices;
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
  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];
251 252 253 254 255 256 257 258 259 260 261 262 263
      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) {
          var new_key = key - del_count + num_additional_args;
          new_array[new_key] = current;
          if (new_key > 0xfffffffe) {
            big_indices = big_indices || new InternalArray();
            big_indices.push(new_key);
264 265 266 267 268 269 270
          }
        }
      }
    }
  }
  // Move contents of new_array into this array
  %MoveArrayContents(new_array, array);
271 272 273 274 275 276 277 278
  // 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];
    }
  }
279 280 281
}


282 283 284 285 286 287
// 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;
288
    if (index in array) {
289
      var current = array[index];
290
      %CreateDataProperty(deleted_elements, i, current);
291
    }
292
  }
293
}
294 295


296 297
function SimpleMove(array, start_i, del_count, len, num_additional_args) {
  if (num_additional_args !== del_count) {
298 299 300 301 302 303
    // 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;
304
        if (from_index in array) {
305
          array[to_index] = array[from_index];
306 307 308 309 310 311 312 313
        } 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;
314
        if (from_index in array) {
315
          array[to_index] = array[from_index];
316 317 318 319 320 321 322 323 324
        } else {
          delete array[to_index];
        }
      }
      for (var i = len; i > len - del_count + num_additional_args; i--) {
        delete array[i - 1];
      }
    }
  }
325
}
326 327 328 329 330 331


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


function ArrayToString() {
332 333 334 335 336
  var array;
  var func;
  if (IS_ARRAY(this)) {
    func = this.join;
    if (func === ArrayJoin) {
337
      return Join(this, this.length, ',', false);
338 339 340
    }
    array = this;
  } else {
341
    array = TO_OBJECT(this);
342
    func = array.join;
343
  }
344
  if (!IS_CALLABLE(func)) {
345
    return %_Call(ObjectToString, array);
346
  }
347
  return %_Call(func, array);
348
}
349 350


351
function InnerArrayToLocaleString(array, length) {
352
  return Join(array, TO_LENGTH(length), ',', true);
353
}
354 355


356
function ArrayToLocaleString() {
357
  var array = TO_OBJECT(this);
358 359 360
  var arrayLen = array.length;
  return InnerArrayToLocaleString(array, arrayLen);
}
361

362 363

function InnerArrayJoin(separator, array, length) {
364 365
  if (IS_UNDEFINED(separator)) {
    separator = ',';
366 367
  } else {
    separator = TO_STRING(separator);
368
  }
369

370 371 372 373
  // Fast case for one-element arrays.
  if (length === 1) {
    var e = array[0];
    if (IS_NULL_OR_UNDEFINED(e)) return '';
374
    return TO_STRING(e);
375 376
  }

377
  return Join(array, length, separator, false);
378
}
379 380


381 382 383
function ArrayJoin(separator) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");

384
  var array = TO_OBJECT(this);
385
  var length = TO_LENGTH(array.length);
386 387 388 389 390

  return InnerArrayJoin(separator, array, length);
}


391 392 393
// Removes the last element from the array and returns it. See
// ECMA-262, section 15.4.4.6.
function ArrayPop() {
394
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
395

396
  var array = TO_OBJECT(this);
397
  var n = TO_LENGTH(array.length);
398
  if (n == 0) {
399
    array.length = n;
400 401
    return;
  }
402

403
  n--;
404
  var value = array[n];
405
  delete array[n];
406
  array.length = n;
407
  return value;
408
}
409 410 411 412 413


// 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() {
414
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
415

416
  var array = TO_OBJECT(this);
417
  var n = TO_LENGTH(array.length);
418
  var m = arguments.length;
419

420 421 422
  // Subtract n from kMaxSafeInteger rather than testing m + n >
  // kMaxSafeInteger. n may already be kMaxSafeInteger. In that case adding
  // e.g., 1 would not be safe.
423
  if (m > kMaxSafeInteger - n) throw %make_type_error(kPushPastSafeLength, m, n);
424

425
  for (var i = 0; i < m; i++) {
426
    array[i+n] = arguments[i];
427
  }
428 429

  var new_length = n + m;
430
  array.length = new_length;
431
  return new_length;
432
}
433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448


// 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;
449
      while (keys[--high_counter] == j) { }
450 451 452 453
      low = j_complement;
    }
    if (j_complement >= i) {
      low = i;
454
      while (keys[++low_counter] == i) { }
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
      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];
      }
    }
  }
}

478
function PackedArrayReverse(array, len) {
479
  var j = len - 1;
480
  for (var i = 0; i < j; i++, j--) {
481
    var current_i = array[i];
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
    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];
497 498
        array[i] = current_j;
        array[j] = current_i;
499
      } else {
500 501
        array[j] = current_i;
        delete array[i];
502 503
      }
    } else {
504 505
      if (j in array) {
        var current_j = array[j];
506 507
        array[i] = current_j;
        delete array[j];
508 509 510
      }
    }
  }
511
  return array;
512
}
513 514


515 516 517
function ArrayReverse() {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");

518
  var array = TO_OBJECT(this);
519
  var len = TO_LENGTH(array.length);
520
  var isArray = IS_ARRAY(array);
521

522
  if (UseSparseVariant(array, len, isArray, len)) {
523 524 525
    %NormalizeElements(array);
    SparseReverse(array, len);
    return array;
526 527 528 529
  } else if (isArray && %_HasFastPackedElements(array)) {
    return PackedArrayReverse(array, len);
  } else {
    return GenericArrayReverse(array, len);
530 531 532 533
  }
}


534
function ArrayShift() {
535
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
536

537
  var array = TO_OBJECT(this);
538
  var len = TO_LENGTH(array.length);
539

540
  if (len === 0) {
541
    array.length = 0;
542 543
    return;
  }
544

545
  if (%object_is_sealed(array)) throw %make_type_error(kArrayFunctionsOnSealed);
546

547
  var first = array[0];
548

549 550
  if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
    SparseMove(array, 0, 1, len, 0);
551 552 553
  } else {
    SimpleMove(array, 0, 1, len, 0);
  }
554

555
  array.length = len - 1;
556

557
  return first;
558
}
559

560

561
function ArrayUnshift(arg1) {  // length == 1
562
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
563

564
  var array = TO_OBJECT(this);
565
  var len = TO_LENGTH(array.length);
566
  var num_arguments = arguments.length;
567

568
  if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) &&
569
      !%object_is_sealed(array)) {
570
    SparseMove(array, 0, 0, len, num_arguments);
571 572 573 574
  } else {
    SimpleMove(array, 0, 0, len, num_arguments);
  }

575
  for (var i = 0; i < num_arguments; i++) {
576
    array[i] = arguments[i];
577
  }
578

579
  var new_length = len + num_arguments;
580
  array.length = new_length;
581
  return new_length;
582
}
583 584 585


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

588
  var array = TO_OBJECT(this);
589
  var len = TO_LENGTH(array.length);
590 591
  var start_i = TO_INTEGER(start);
  var end_i = len;
592

593
  if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
594

595 596 597 598 599 600
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
601

602 603 604 605 606 607
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
608

609
  var result = ArraySpeciesCreate(array, MaxSimple(end_i - start_i, 0));
610 611 612

  if (end_i < start_i) return result;

613 614
  if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
    %NormalizeElements(array);
615
    if (IS_ARRAY(result)) %NormalizeElements(result);
616
    SparseSlice(array, start_i, end_i - start_i, len, result);
617
  } else {
618
    SimpleSlice(array, start_i, end_i - start_i, len, result);
619 620
  }

621
  result.length = end_i - start_i;
622

623
  return result;
624
}
625 626


627
function ComputeSpliceStartIndex(start_i, len) {
628 629
  if (start_i < 0) {
    start_i += len;
630
    return start_i < 0 ? 0 : start_i;
631
  }
632

633 634 635 636 637
  return start_i > len ? len : start_i;
}


function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
638
  // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
639 640
  // given as a request to delete all the elements from the start.
  // And it differs from the case of undefined delete count.
641 642 643
  // This does not follow ECMA-262, but we do the same for
  // compatibility.
  var del_count = 0;
644 645 646 647 648 649 650 651 652 653 654 655
  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;
}
656

657 658

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

661
  var num_arguments = arguments.length;
662
  var array = TO_OBJECT(this);
663
  var len = TO_LENGTH(array.length);
664 665 666
  var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
  var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
                                           start_i);
667
  var deleted_elements = ArraySpeciesCreate(array, del_count);
668 669 670
  deleted_elements.length = del_count;
  var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;

671
  if (del_count != num_elements_to_add && %object_is_sealed(array)) {
672
    throw %make_type_error(kArrayFunctionsOnSealed);
673
  } else if (del_count > 0 && %object_is_frozen(array)) {
674
    throw %make_type_error(kArrayFunctionsOnFrozen);
675 676
  }

677 678 679 680 681
  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;
682
  }
683 684
  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
    %NormalizeElements(array);
685
    if (IS_ARRAY(deleted_elements)) %NormalizeElements(deleted_elements);
686 687
    SparseSlice(array, start_i, del_count, len, deleted_elements);
    SparseMove(array, start_i, del_count, len, num_elements_to_add);
688 689 690 691
  } else {
    SimpleSlice(array, start_i, del_count, len, deleted_elements);
    SimpleMove(array, start_i, del_count, len, num_elements_to_add);
  }
692

693 694 695 696
  // Insert the arguments into the resulting array in
  // place of the deleted elements.
  var i = start_i;
  var arguments_index = 2;
697
  var arguments_length = arguments.length;
698
  while (arguments_index < arguments_length) {
699
    array[i++] = arguments[arguments_index++];
700
  }
701
  array.length = len - del_count + num_elements_to_add;
702

703 704
  // Return the deleted elements.
  return deleted_elements;
705
}
706 707


708
function InnerArraySort(array, length, comparefn) {
olehougaard's avatar
olehougaard committed
709
  // In-place QuickSort algorithm.
710
  // For short (length <= 10) arrays, insertion sort is used for efficiency.
711

712
  if (!IS_CALLABLE(comparefn)) {
713 714 715 716
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
717
      }
718 719
      x = TO_STRING(x);
      y = TO_STRING(y);
720 721 722
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
723
  }
724
  function InsertionSort(a, from, to) {
olehougaard's avatar
olehougaard committed
725 726
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
727 728
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
729
        var order = comparefn(tmp, element);
730 731
        if (order > 0) {
          a[j + 1] = tmp;
olehougaard's avatar
olehougaard committed
732
        } else {
733
          break;
olehougaard's avatar
olehougaard committed
734 735
        }
      }
736
      a[j + 1] = element;
olehougaard's avatar
olehougaard committed
737
    }
738
  };
739

740
  function GetThirdIndex(a, from, to) {
741
    var t_array = new InternalArray();
742 743
    // Use both 'from' and 'to' to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
744 745 746 747
    var j = 0;
    from += 1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
748
      t_array[j] = [i, a[i]];
749
      j++;
750
    }
751
    t_array.sort(function(a, b) {
752
      return comparefn(a[1], b[1]);
753
    });
754 755 756 757
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

758
  function QuickSort(a, from, to) {
759
    var third_index = 0;
760 761 762 763 764
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
765
      }
766 767 768 769 770
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
771 772 773
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
774
      var v2 = a[third_index];
775
      var c01 = comparefn(v0, v1);
776 777 778 779 780 781
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
782
      var c02 = comparefn(v0, v2);
783 784 785 786 787 788 789 790
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
791
        var c12 = comparefn(v1, v2);
792 793 794 795 796 797 798 799 800 801 802 803 804
        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.
805
      a[third_index] = a[low_end];
806 807 808 809 810 811
      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];
812
        var order = comparefn(element, pivot);
813
        if (order < 0) {
814 815
          a[i] = a[low_end];
          a[low_end] = element;
816
          low_end++;
817 818 819 820 821
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
822
            order = comparefn(top_elem, pivot);
823 824 825 826 827 828 829 830 831
          } 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++;
          }
832
        }
833
      }
834 835 836 837 838 839 840
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
841
    }
842
  };
843

844 845
  // 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
846
  // of a prototype property.
847
  function CopyFromPrototype(obj, length) {
848
    var max = 0;
849 850
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
851
      var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
852 853 854 855
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = 0; i < proto_length; i++) {
856
          if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
857 858
            obj[i] = proto[i];
            if (i >= max) { max = i + 1; }
859
          }
860 861 862 863
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
864
          if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
865 866
            obj[index] = proto[index];
            if (index >= max) { max = index + 1; }
867 868 869 870 871
          }
        }
      }
    }
    return max;
872
  };
873 874 875 876

  // 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.
877
  function ShadowPrototypeElements(obj, from, to) {
878 879
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
880
      var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
881 882 883 884
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = from; i < proto_length; i++) {
885
          if (HAS_OWN_PROPERTY(proto, i)) {
886
            obj[i] = UNDEFINED;
887
          }
888 889 890 891
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
892
          if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
893
            obj[index] = UNDEFINED;
894 895 896 897
          }
        }
      }
    }
898
  };
899

900
  function SafeRemoveArrayHoles(obj) {
901 902 903 904 905 906 907 908 909 910 911 912 913 914
    // 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.
915
      if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
916 917 918 919 920 921
        num_holes++;
      }

      // Find last defined element.
      while (first_undefined < last_defined &&
             IS_UNDEFINED(obj[last_defined])) {
922
        if (!HAS_OWN_PROPERTY(obj, last_defined)) {
923 924 925 926 927 928 929
          num_holes++;
        }
        last_defined--;
      }
      if (first_undefined < last_defined) {
        // Fill in hole or undefined.
        obj[first_undefined] = obj[last_defined];
930
        obj[last_defined] = UNDEFINED;
931 932 933 934 935 936 937 938 939 940 941
      }
    }
    // 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++) {
942
      obj[i] = UNDEFINED;
943 944 945
    }
    for (i = length - num_holes; i < length; i++) {
      // For compatability with Webkit, do not expose elements in the prototype.
946
      if (i in %object_get_prototype_of(obj)) {
947
        obj[i] = UNDEFINED;
948 949 950 951 952 953 954
      } else {
        delete obj[i];
      }
    }

    // Return the number of defined elements.
    return first_undefined;
955
  };
956

957
  if (length < 2) return array;
958

959
  var is_array = IS_ARRAY(array);
960 961 962 963 964
  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
965
    // own elements. This is not very efficient, but sorting with
966 967 968 969
    // 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.
970
    max_prototype_element = CopyFromPrototype(array, length);
971 972
  }

973
  // %RemoveArrayHoles returns -1 if fast removal is not supported.
974
  var num_non_undefined = %RemoveArrayHoles(array, length);
975

976
  if (num_non_undefined == -1) {
977
    // There were indexed accessors in the array.
978
    // Move array holes and undefineds to the end using a Javascript function
979
    // that is safe in the presence of accessors.
980
    num_non_undefined = SafeRemoveArrayHoles(array);
981
  }
982

983
  QuickSort(array, 0, num_non_undefined);
984

985 986 987
  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.
988
    ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
989 990
  }

991
  return array;
992
}
993 994


995 996 997
function ArraySort(comparefn) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");

998
  var array = TO_OBJECT(this);
999
  var length = TO_LENGTH(array.length);
1000
  return InnerArraySort(array, length, comparefn);
1001 1002
}

1003 1004 1005 1006 1007 1008
function ArrayLastIndexOf(element, index) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");

  var array = this;
  var length = TO_LENGTH(this.length);

1009
  if (length == 0) return -1;
1010
  if (arguments.length < 2) {
1011 1012
    index = length - 1;
  } else {
1013
    index = INVERT_NEG_ZERO(TO_INTEGER(index));
1014
    // If index is negative, index from end of the array.
1015
    if (index < 0) index += length;
1016
    // If index is still negative, do not search the array.
1017
    if (index < 0) return -1;
1018 1019
    else if (index >= length) index = length - 1;
  }
1020 1021
  var min = 0;
  var max = index;
1022 1023 1024
  if (UseSparseVariant(array, length, IS_ARRAY(array), index)) {
    %NormalizeElements(array);
    var indices = %GetArrayKeys(array, index + 1);
1025 1026 1027
    if (IS_NUMBER(indices)) {
      // It's an interval.
      max = indices;  // Capped by index already.
1028 1029
      // Fall through to loop below.
    } else {
1030
      if (indices.length == 0) return -1;
1031
      // Get all the keys in sorted order.
1032
      var sortedKeys = GetSortedArrayKeys(array, indices);
1033 1034 1035
      var i = sortedKeys.length - 1;
      while (i >= 0) {
        var key = sortedKeys[i];
1036
        if (array[key] === element) return key;
1037 1038 1039 1040 1041
        i--;
      }
      return -1;
    }
  }
1042
  // Lookup through the array.
1043
  if (!IS_UNDEFINED(element)) {
1044
    for (var i = max; i >= min; i--) {
1045
      if (array[i] === element) return i;
1046 1047 1048
    }
    return -1;
  }
1049
  for (var i = max; i >= min; i--) {
1050
    if (IS_UNDEFINED(array[i]) && i in array) {
1051
      return i;
1052 1053 1054
    }
  }
  return -1;
1055
}
1056

1057 1058 1059 1060 1061 1062 1063 1064
// ES#sec-array.prototype.copywithin
// (Array.prototype.copyWithin ( target, start [ , end ] )
function ArrayCopyWithin(target, start, end) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.copyWithin");

  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);

1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113
  target = TO_INTEGER(target);
  var to;
  if (target < 0) {
    to = MaxSimple(length + target, 0);
  } else {
    to = MinSimple(target, length);
  }

  start = TO_INTEGER(start);
  var from;
  if (start < 0) {
    from = MaxSimple(length + start, 0);
  } else {
    from = MinSimple(start, length);
  }

  end = IS_UNDEFINED(end) ? length : TO_INTEGER(end);
  var final;
  if (end < 0) {
    final = MaxSimple(length + end, 0);
  } else {
    final = MinSimple(end, length);
  }

  var count = MinSimple(final - from, length - to);
  var direction = 1;
  if (from < to && to < (from + count)) {
    direction = -1;
    from = from + count - 1;
    to = to + count - 1;
  }

  while (count > 0) {
    if (from in array) {
      array[to] = array[from];
    } else {
      delete array[to];
    }
    from = from + direction;
    to = to + direction;
    count--;
  }

  return array;
}


function InnerArrayFind(predicate, thisArg, array, length) {
  if (!IS_CALLABLE(predicate)) {
1114
    throw %make_type_error(kCalledNonCallable, predicate);
1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140
  }

  for (var i = 0; i < length; i++) {
    var element = array[i];
    if (%_Call(predicate, thisArg, element, i, array)) {
      return element;
    }
  }

  return;
}


// ES6 draft 07-15-13, section 15.4.3.23
function ArrayFind(predicate, thisArg) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.find");

  var array = TO_OBJECT(this);
  var length = TO_INTEGER(array.length);

  return InnerArrayFind(predicate, thisArg, array, length);
}


function InnerArrayFindIndex(predicate, thisArg, array, length) {
  if (!IS_CALLABLE(predicate)) {
1141
    throw %make_type_error(kCalledNonCallable, predicate);
1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166
  }

  for (var i = 0; i < length; i++) {
    var element = array[i];
    if (%_Call(predicate, thisArg, element, i, array)) {
      return i;
    }
  }

  return -1;
}


// ES6 draft 07-15-13, section 15.4.3.24
function ArrayFindIndex(predicate, thisArg) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.findIndex");

  var array = TO_OBJECT(this);
  var length = TO_INTEGER(array.length);

  return InnerArrayFindIndex(predicate, thisArg, array, length);
}


// ES6, draft 04-05-14, section 22.1.3.6
1167 1168 1169 1170 1171 1172
function ArrayFill(value, start, end) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.fill");

  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);

1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189
  var i = IS_UNDEFINED(start) ? 0 : TO_INTEGER(start);
  var end = IS_UNDEFINED(end) ? length : TO_INTEGER(end);

  if (i < 0) {
    i += length;
    if (i < 0) i = 0;
  } else {
    if (i > length) i = length;
  }

  if (end < 0) {
    end += length;
    if (end < 0) end = 0;
  } else {
    if (end > length) end = length;
  }

1190
  if ((end - i) > 0 && %object_is_frozen(array)) {
1191
    throw %make_type_error(kArrayFunctionsOnFrozen);
1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206
  }

  for (; i < end; i++)
    array[i] = value;
  return array;
}


// ES6, draft 10-14-14, section 22.1.2.1
function ArrayFrom(arrayLike, mapfn, receiver) {
  var items = TO_OBJECT(arrayLike);
  var mapping = !IS_UNDEFINED(mapfn);

  if (mapping) {
    if (!IS_CALLABLE(mapfn)) {
1207
      throw %make_type_error(kCalledNonCallable, mapfn);
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220
    }
  }

  var iterable = GetMethod(items, iteratorSymbol);
  var k;
  var result;
  var mappedValue;
  var nextValue;

  if (!IS_UNDEFINED(iterable)) {
    result = %IsConstructor(this) ? new this() : [];
    k = 0;

1221 1222
    for (nextValue of
         { [iteratorSymbol]() { return GetIterator(items, iterable) } }) {
1223 1224 1225 1226 1227
      if (mapping) {
        mappedValue = %_Call(mapfn, receiver, nextValue, k);
      } else {
        mappedValue = nextValue;
      }
1228
      %CreateDataProperty(result, k, mappedValue);
1229 1230
      k++;
    }
1231 1232
    result.length = k;
    return result;
1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243
  } else {
    var len = TO_LENGTH(items.length);
    result = %IsConstructor(this) ? new this(len) : new GlobalArray(len);

    for (k = 0; k < len; ++k) {
      nextValue = items[k];
      if (mapping) {
        mappedValue = %_Call(mapfn, receiver, nextValue, k);
      } else {
        mappedValue = nextValue;
      }
1244
      %CreateDataProperty(result, k, mappedValue);
1245 1246 1247 1248 1249 1250 1251 1252 1253
    }

    result.length = k;
    return result;
  }
}


// ES6, draft 05-22-14, section 22.1.2.3
1254 1255
function ArrayOf(...args) {
  var length = args.length;
1256 1257 1258 1259
  var constructor = this;
  // TODO: Implement IsConstructor (ES6 section 7.2.5)
  var array = %IsConstructor(constructor) ? new constructor(length) : [];
  for (var i = 0; i < length; i++) {
1260
    %CreateDataProperty(array, i, args[i]);
1261 1262 1263 1264 1265
  }
  array.length = length;
  return array;
}

1266
// -------------------------------------------------------------------
1267

1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280
// 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,
1281
  includes: true,
1282 1283 1284
  keys: true,
};

1285
%AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables,
1286 1287
                  DONT_ENUM | READ_ONLY);

1288 1289
%FunctionSetLength(ArrayFrom, 1);

1290
// Set up non-enumerable functions on the Array object.
1291
utils.InstallFunctions(GlobalArray, DONT_ENUM, [
1292 1293
  "from", ArrayFrom,
  "of", ArrayOf
1294 1295
]);

1296
var specialFunctions = %SpecialArrayFunctions();
1297

1298
function getFunction(name, jsBuiltin, len) {
1299 1300 1301 1302 1303 1304 1305 1306 1307
  var f = jsBuiltin;
  if (specialFunctions.hasOwnProperty(name)) {
    f = specialFunctions[name];
  }
  if (!IS_UNDEFINED(len)) {
    %FunctionSetLength(f, len);
  }
  return f;
};
1308

1309 1310 1311 1312 1313 1314 1315
// Array prototype functions that return iterators. They are exposed to the
// public API via Template::SetIntrinsicDataProperty().
var IteratorFunctions = {
    "entries": getFunction("entries", null, 0),
    "keys": getFunction("keys", null, 0),
    "values": getFunction("values", null, 0)
}
1316

1317 1318 1319 1320
// 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.
1321
utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [
1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
  "toString", getFunction("toString", ArrayToString),
  "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush, 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),
1333
  "indexOf", getFunction("indexOf", null, 1),
1334
  "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1335 1336 1337
  "copyWithin", getFunction("copyWithin", ArrayCopyWithin, 2),
  "find", getFunction("find", ArrayFind, 1),
  "findIndex", getFunction("findIndex", ArrayFindIndex, 1),
1338
  "fill", getFunction("fill", ArrayFill, 1),
1339
  "includes", getFunction("includes", null, 1),
1340 1341 1342
  "entries", IteratorFunctions.entries,
  "keys", IteratorFunctions.keys,
  iteratorSymbol, IteratorFunctions.values
1343 1344
]);

1345 1346 1347
%FunctionSetName(IteratorFunctions.entries, "entries");
%FunctionSetName(IteratorFunctions.keys, "keys");
%FunctionSetName(IteratorFunctions.values, "values");
1348

1349 1350 1351
// 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.
1352
utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [
1353
  "indexOf", getFunction("indexOf", null),
1354 1355 1356 1357
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush),
  "shift", getFunction("shift", ArrayShift),
1358
  "sort", getFunction("sort", ArraySort),
1359
  "splice", getFunction("splice", ArraySplice)
1360 1361
]);

1362
utils.SetUpLockedPrototype(InternalPackedArray, GlobalArray(), [
1363 1364 1365 1366
  "join", getFunction("join", ArrayJoin),
  "pop", getFunction("pop", ArrayPop),
  "push", getFunction("push", ArrayPush),
  "shift", getFunction("shift", ArrayShift)
1367 1368
]);

1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
// V8 extras get a separate copy of InternalPackedArray. We give them the basic
// manipulation methods.
utils.SetUpLockedPrototype(extrasUtils.InternalPackedArray, GlobalArray(), [
  "push", getFunction("push", ArrayPush),
  "pop", getFunction("pop", ArrayPop),
  "shift", getFunction("shift", ArrayShift),
  "unshift", getFunction("unshift", ArrayUnshift),
  "splice", getFunction("splice", ArraySplice),
  "slice", getFunction("slice", ArraySlice)
]);

1380 1381 1382 1383
// -------------------------------------------------------------------
// Exports

utils.Export(function(to) {
1384
  to.ArrayFrom = ArrayFrom;
1385
  to.ArrayJoin = ArrayJoin;
1386
  to.ArrayPush = ArrayPush;
1387
  to.ArrayToString = ArrayToString;
1388
  to.ArrayValues = IteratorFunctions.values,
1389 1390
  to.InnerArrayFind = InnerArrayFind;
  to.InnerArrayFindIndex = InnerArrayFindIndex;
1391
  to.InnerArrayJoin = InnerArrayJoin;
1392
  to.InnerArraySort = InnerArraySort;
1393
  to.InnerArrayToLocaleString = InnerArrayToLocaleString;
1394 1395
});

1396
%InstallToContext([
1397 1398
  "array_entries_iterator", IteratorFunctions.entries,
  "array_keys_iterator", IteratorFunctions.keys,
1399 1400 1401 1402 1403 1404
  "array_pop", ArrayPop,
  "array_push", ArrayPush,
  "array_shift", ArrayShift,
  "array_splice", ArraySplice,
  "array_slice", ArraySlice,
  "array_unshift", ArrayUnshift,
1405
  "array_values_iterator", IteratorFunctions.values,
1406
]);
1407

1408
});