array.js 38.4 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 332 333 334 335 336 337 338 339 340 341 342 343 344
var ArrayJoin;
DEFINE_METHOD(
  GlobalArray.prototype,
  toString() {
    var array;
    var func;
    if (IS_ARRAY(this)) {
      func = this.join;
      if (func === ArrayJoin) {
        return Join(this, this.length, ',', false);
      }
      array = this;
    } else {
      array = TO_OBJECT(this);
      func = array.join;
345
    }
346 347 348 349
    if (!IS_CALLABLE(func)) {
      return %_Call(ObjectToString, array);
    }
    return %_Call(func, array);
350
  }
351
);
352

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


358 359 360 361 362 363 364 365
DEFINE_METHOD(
  GlobalArray.prototype,
  toLocaleString() {
    var array = TO_OBJECT(this);
    var arrayLen = array.length;
    return InnerArrayToLocaleString(array, arrayLen);
  }
);
366

367 368

function InnerArrayJoin(separator, array, length) {
369 370
  if (IS_UNDEFINED(separator)) {
    separator = ',';
371 372
  } else {
    separator = TO_STRING(separator);
373
  }
374

375 376 377 378
  // Fast case for one-element arrays.
  if (length === 1) {
    var e = array[0];
    if (IS_NULL_OR_UNDEFINED(e)) return '';
379
    return TO_STRING(e);
380 381
  }

382
  return Join(array, length, separator, false);
383
}
384 385


386 387 388 389
DEFINE_METHOD(
  GlobalArray.prototype,
  join(separator) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
390

391 392
    var array = TO_OBJECT(this);
    var length = TO_LENGTH(array.length);
393

394 395 396
    return InnerArrayJoin(separator, array, length);
  }
);
397 398


399 400
// Removes the last element from the array and returns it. See
// ECMA-262, section 15.4.4.6.
401
function ArrayPopFallback() {
402
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
403

404
  var array = TO_OBJECT(this);
405
  var n = TO_LENGTH(array.length);
406
  if (n == 0) {
407
    array.length = n;
408 409
    return;
  }
410

411
  n--;
412
  var value = array[n];
413
  delete array[n];
414
  array.length = n;
415
  return value;
416
}
417 418 419 420


// 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.
421
function ArrayPushFallback() {
422
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
423

424
  var array = TO_OBJECT(this);
425
  var n = TO_LENGTH(array.length);
426
  var m = arguments.length;
427

428 429 430
  // 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.
431
  if (m > kMaxSafeInteger - n) throw %make_type_error(kPushPastSafeLength, m, n);
432

433
  for (var i = 0; i < m; i++) {
434
    array[i+n] = arguments[i];
435
  }
436 437

  var new_length = n + m;
438
  array.length = new_length;
439
  return new_length;
440
}
441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456


// 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;
457
      while (keys[--high_counter] == j) { }
458 459 460 461
      low = j_complement;
    }
    if (j_complement >= i) {
      low = i;
462
      while (keys[++low_counter] == i) { }
463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
      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];
      }
    }
  }
}

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


523 524 525 526
DEFINE_METHOD(
  GlobalArray.prototype,
  reverse() {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
527

528 529 530
    var array = TO_OBJECT(this);
    var len = TO_LENGTH(array.length);
    var isArray = IS_ARRAY(array);
531

532 533 534 535 536 537 538 539 540
    if (UseSparseVariant(array, len, isArray, len)) {
      %NormalizeElements(array);
      SparseReverse(array, len);
      return array;
    } else if (isArray && %_HasFastPackedElements(array)) {
      return PackedArrayReverse(array, len);
    } else {
      return GenericArrayReverse(array, len);
    }
541
  }
542
);
543 544


545
function ArrayShiftFallback() {
546
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
547

548
  var array = TO_OBJECT(this);
549
  var len = TO_LENGTH(array.length);
550

551
  if (len === 0) {
552
    array.length = 0;
553 554
    return;
  }
555

556
  if (%object_is_sealed(array)) throw %make_type_error(kArrayFunctionsOnSealed);
557

558
  var first = array[0];
559

560 561
  if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
    SparseMove(array, 0, 1, len, 0);
562 563 564
  } else {
    SimpleMove(array, 0, 1, len, 0);
  }
565

566
  array.length = len - 1;
567

568
  return first;
569
}
570

571

572
function ArrayUnshiftFallback(arg1) {  // length == 1
573
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
574

575
  var array = TO_OBJECT(this);
576
  var len = TO_LENGTH(array.length);
577
  var num_arguments = arguments.length;
578

579
  if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) &&
580
      !%object_is_sealed(array)) {
581
    SparseMove(array, 0, 0, len, num_arguments);
582 583 584 585
  } else {
    SimpleMove(array, 0, 0, len, num_arguments);
  }

586
  for (var i = 0; i < num_arguments; i++) {
587
    array[i] = arguments[i];
588
  }
589

590
  var new_length = len + num_arguments;
591
  array.length = new_length;
592
  return new_length;
593
}
594 595


596
function ArraySliceFallback(start, end) {
597
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
598

599
  var array = TO_OBJECT(this);
600
  var len = TO_LENGTH(array.length);
601 602
  var start_i = TO_INTEGER(start);
  var end_i = len;
603

604
  if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
605

606 607 608 609 610 611
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
612

613 614 615 616 617 618
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
619

620
  var result = ArraySpeciesCreate(array, MaxSimple(end_i - start_i, 0));
621 622 623

  if (end_i < start_i) return result;

624 625
  if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
    %NormalizeElements(array);
626
    if (IS_ARRAY(result)) %NormalizeElements(result);
627
    SparseSlice(array, start_i, end_i - start_i, len, result);
628
  } else {
629
    SimpleSlice(array, start_i, end_i - start_i, len, result);
630 631
  }

632
  result.length = end_i - start_i;
633

634
  return result;
635
}
636 637


638
function ComputeSpliceStartIndex(start_i, len) {
639 640
  if (start_i < 0) {
    start_i += len;
641
    return start_i < 0 ? 0 : start_i;
642
  }
643

644 645 646 647 648
  return start_i > len ? len : start_i;
}


function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
649
  // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
650 651
  // given as a request to delete all the elements from the start.
  // And it differs from the case of undefined delete count.
652 653 654
  // This does not follow ECMA-262, but we do the same for
  // compatibility.
  var del_count = 0;
655 656 657 658 659 660 661 662 663 664 665 666
  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;
}
667

668

669
function ArraySpliceFallback(start, delete_count) {
670
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
671

672
  var num_arguments = arguments.length;
673
  var array = TO_OBJECT(this);
674
  var len = TO_LENGTH(array.length);
675 676 677
  var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
  var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
                                           start_i);
678
  var deleted_elements = ArraySpeciesCreate(array, del_count);
679 680 681
  deleted_elements.length = del_count;
  var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;

682
  if (del_count != num_elements_to_add && %object_is_sealed(array)) {
683
    throw %make_type_error(kArrayFunctionsOnSealed);
684
  } else if (del_count > 0 && %object_is_frozen(array)) {
685
    throw %make_type_error(kArrayFunctionsOnFrozen);
686 687
  }

688 689 690 691 692
  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;
693
  }
694 695
  if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
    %NormalizeElements(array);
696
    if (IS_ARRAY(deleted_elements)) %NormalizeElements(deleted_elements);
697 698
    SparseSlice(array, start_i, del_count, len, deleted_elements);
    SparseMove(array, start_i, del_count, len, num_elements_to_add);
699 700 701 702
  } else {
    SimpleSlice(array, start_i, del_count, len, deleted_elements);
    SimpleMove(array, start_i, del_count, len, num_elements_to_add);
  }
703

704 705 706 707
  // Insert the arguments into the resulting array in
  // place of the deleted elements.
  var i = start_i;
  var arguments_index = 2;
708
  var arguments_length = arguments.length;
709
  while (arguments_index < arguments_length) {
710
    array[i++] = arguments[arguments_index++];
711
  }
712
  array.length = len - del_count + num_elements_to_add;
713

714 715
  // Return the deleted elements.
  return deleted_elements;
716
}
717 718


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

723
  if (!IS_CALLABLE(comparefn)) {
724 725 726 727
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
728
      }
729 730
      x = TO_STRING(x);
      y = TO_STRING(y);
731 732 733
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
734
  }
735
  function InsertionSort(a, from, to) {
olehougaard's avatar
olehougaard committed
736 737
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
738 739
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
740
        var order = comparefn(tmp, element);
741 742
        if (order > 0) {
          a[j + 1] = tmp;
olehougaard's avatar
olehougaard committed
743
        } else {
744
          break;
olehougaard's avatar
olehougaard committed
745 746
        }
      }
747
      a[j + 1] = element;
olehougaard's avatar
olehougaard committed
748
    }
749
  };
750

751
  function GetThirdIndex(a, from, to) {
752
    var t_array = new InternalArray();
753 754
    // Use both 'from' and 'to' to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
755 756 757 758
    var j = 0;
    from += 1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
759
      t_array[j] = [i, a[i]];
760
      j++;
761
    }
762
    t_array.sort(function(a, b) {
763
      return comparefn(a[1], b[1]);
764
    });
765 766 767 768
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

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

855 856
  // 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
857
  // of a prototype property.
858
  function CopyFromPrototype(obj, length) {
859
    var max = 0;
860 861
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
862
      var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
863 864 865 866
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = 0; i < proto_length; i++) {
867
          if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
868 869
            obj[i] = proto[i];
            if (i >= max) { max = i + 1; }
870
          }
871 872 873 874
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
875
          if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
876 877
            obj[index] = proto[index];
            if (index >= max) { max = index + 1; }
878 879 880 881 882
          }
        }
      }
    }
    return max;
883
  };
884 885 886 887

  // 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.
888
  function ShadowPrototypeElements(obj, from, to) {
889 890
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
891
      var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
892 893 894 895
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = from; i < proto_length; i++) {
896
          if (HAS_OWN_PROPERTY(proto, i)) {
897
            obj[i] = UNDEFINED;
898
          }
899 900 901 902
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
903
          if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
904
            obj[index] = UNDEFINED;
905 906 907 908
          }
        }
      }
    }
909
  };
910

911
  function SafeRemoveArrayHoles(obj) {
912 913 914 915 916 917 918 919 920 921 922 923 924 925
    // 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.
926
      if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
927 928 929 930 931 932
        num_holes++;
      }

      // Find last defined element.
      while (first_undefined < last_defined &&
             IS_UNDEFINED(obj[last_defined])) {
933
        if (!HAS_OWN_PROPERTY(obj, last_defined)) {
934 935 936 937 938 939 940
          num_holes++;
        }
        last_defined--;
      }
      if (first_undefined < last_defined) {
        // Fill in hole or undefined.
        obj[first_undefined] = obj[last_defined];
941
        obj[last_defined] = UNDEFINED;
942 943 944 945 946 947 948 949 950 951 952
      }
    }
    // 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++) {
953
      obj[i] = UNDEFINED;
954 955 956
    }
    for (i = length - num_holes; i < length; i++) {
      // For compatability with Webkit, do not expose elements in the prototype.
957
      if (i in %object_get_prototype_of(obj)) {
958
        obj[i] = UNDEFINED;
959 960 961 962 963 964 965
      } else {
        delete obj[i];
      }
    }

    // Return the number of defined elements.
    return first_undefined;
966
  };
967

968
  if (length < 2) return array;
969

970
  var is_array = IS_ARRAY(array);
971 972 973 974 975
  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
976
    // own elements. This is not very efficient, but sorting with
977 978 979 980
    // 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.
981
    max_prototype_element = CopyFromPrototype(array, length);
982 983
  }

984
  // %RemoveArrayHoles returns -1 if fast removal is not supported.
985
  var num_non_undefined = %RemoveArrayHoles(array, length);
986

987
  if (num_non_undefined == -1) {
988
    // There were indexed accessors in the array.
989
    // Move array holes and undefineds to the end using a Javascript function
990
    // that is safe in the presence of accessors.
991
    num_non_undefined = SafeRemoveArrayHoles(array);
992
  }
993

994
  QuickSort(array, 0, num_non_undefined);
995

996 997 998
  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.
999
    ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
1000 1001
  }

1002
  return array;
1003
}
1004 1005


1006 1007 1008 1009
DEFINE_METHOD(
  GlobalArray.prototype,
  sort(comparefn) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
1010

1011 1012 1013 1014 1015
    var array = TO_OBJECT(this);
    var length = TO_LENGTH(array.length);
    return InnerArraySort(array, length, comparefn);
  }
);
1016

1017 1018 1019 1020
DEFINE_METHOD_LEN(
  GlobalArray.prototype,
  lastIndexOf(element, index) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1021

1022 1023
    var array = this;
    var length = TO_LENGTH(this.length);
1024

1025 1026 1027
    if (length == 0) return -1;
    if (arguments.length < 2) {
      index = length - 1;
1028
    } else {
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
      index = INVERT_NEG_ZERO(TO_INTEGER(index));
      // If index is negative, index from end of the array.
      if (index < 0) index += length;
      // If index is still negative, do not search the array.
      if (index < 0) return -1;
      else if (index >= length) index = length - 1;
    }
    var min = 0;
    var max = index;
    if (UseSparseVariant(array, length, IS_ARRAY(array), index)) {
      %NormalizeElements(array);
      var indices = %GetArrayKeys(array, index + 1);
      if (IS_NUMBER(indices)) {
        // It's an interval.
        max = indices;  // Capped by index already.
        // Fall through to loop below.
      } else {
        if (indices.length == 0) return -1;
        // Get all the keys in sorted order.
        var sortedKeys = GetSortedArrayKeys(array, indices);
        var i = sortedKeys.length - 1;
        while (i >= 0) {
          var key = sortedKeys[i];
          if (array[key] === element) return key;
          i--;
        }
        return -1;
      }
    }
    // Lookup through the array.
    if (!IS_UNDEFINED(element)) {
      for (var i = max; i >= min; i--) {
        if (array[i] === element) return i;
1062 1063 1064 1065
      }
      return -1;
    }
    for (var i = max; i >= min; i--) {
1066 1067 1068
      if (IS_UNDEFINED(array[i]) && i in array) {
        return i;
      }
1069 1070
    }
    return -1;
1071 1072 1073 1074
  },
  1  /* Set function length */
);

1075

1076 1077
// ES#sec-array.prototype.copywithin
// (Array.prototype.copyWithin ( target, start [ , end ] )
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092
DEFINE_METHOD_LEN(
  GlobalArray.prototype,
  copyWithin(target, start, end) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.copyWithin");

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

    target = TO_INTEGER(target);
    var to;
    if (target < 0) {
      to = MaxSimple(length + target, 0);
    } else {
      to = MinSimple(target, length);
    }
1093

1094 1095 1096 1097 1098 1099 1100
    start = TO_INTEGER(start);
    var from;
    if (start < 0) {
      from = MaxSimple(length + start, 0);
    } else {
      from = MinSimple(start, length);
    }
1101

1102 1103 1104 1105 1106 1107 1108
    end = IS_UNDEFINED(end) ? length : TO_INTEGER(end);
    var final;
    if (end < 0) {
      final = MaxSimple(length + end, 0);
    } else {
      final = MinSimple(end, length);
    }
1109

1110 1111 1112 1113 1114 1115 1116
    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;
    }
1117

1118 1119 1120 1121 1122 1123 1124 1125 1126
    while (count > 0) {
      if (from in array) {
        array[to] = array[from];
      } else {
        delete array[to];
      }
      from = from + direction;
      to = to + direction;
      count--;
1127 1128
    }

1129 1130 1131 1132
    return array;
  },
  2  /* Set function length */
);
1133 1134 1135 1136


function InnerArrayFind(predicate, thisArg, array, length) {
  if (!IS_CALLABLE(predicate)) {
1137
    throw %make_type_error(kCalledNonCallable, predicate);
1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151
  }

  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
1152 1153 1154 1155
DEFINE_METHOD_LEN(
  GlobalArray.prototype,
  find(predicate, thisArg) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.find");
1156

1157 1158
    var array = TO_OBJECT(this);
    var length = TO_INTEGER(array.length);
1159

1160 1161 1162 1163
    return InnerArrayFind(predicate, thisArg, array, length);
  },
  1  /* Set function length */
);
1164 1165 1166 1167


function InnerArrayFindIndex(predicate, thisArg, array, length) {
  if (!IS_CALLABLE(predicate)) {
1168
    throw %make_type_error(kCalledNonCallable, predicate);
1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
  }

  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
1183 1184 1185 1186
DEFINE_METHOD_LEN(
  GlobalArray.prototype,
  findIndex(predicate, thisArg) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.findIndex");
1187

1188 1189
    var array = TO_OBJECT(this);
    var length = TO_INTEGER(array.length);
1190

1191 1192 1193 1194
    return InnerArrayFindIndex(predicate, thisArg, array, length);
  },
  1  /* Set function length */
);
1195 1196 1197


// ES6, draft 04-05-14, section 22.1.3.6
1198 1199 1200 1201
DEFINE_METHOD_LEN(
  GlobalArray.prototype,
  fill(value, start, end) {
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.fill");
1202

1203 1204
    var array = TO_OBJECT(this);
    var length = TO_LENGTH(array.length);
1205

1206 1207
    var i = IS_UNDEFINED(start) ? 0 : TO_INTEGER(start);
    var end = IS_UNDEFINED(end) ? length : TO_INTEGER(end);
1208

1209 1210 1211 1212 1213 1214
    if (i < 0) {
      i += length;
      if (i < 0) i = 0;
    } else {
      if (i > length) i = length;
    }
1215

1216 1217 1218 1219 1220 1221
    if (end < 0) {
      end += length;
      if (end < 0) end = 0;
    } else {
      if (end > length) end = length;
    }
1222

1223 1224 1225
    if ((end - i) > 0 && %object_is_frozen(array)) {
      throw %make_type_error(kArrayFunctionsOnFrozen);
    }
1226

1227 1228 1229 1230 1231 1232
    for (; i < end; i++)
      array[i] = value;
    return array;
  },
  1  /* Set function length */
);
1233 1234 1235


// ES6, draft 10-14-14, section 22.1.2.1
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245
DEFINE_METHOD_LEN(
  GlobalArray,
  'from'(arrayLike, mapfn, receiver) {
    var items = TO_OBJECT(arrayLike);
    var mapping = !IS_UNDEFINED(mapfn);

    if (mapping) {
      if (!IS_CALLABLE(mapfn)) {
        throw %make_type_error(kCalledNonCallable, mapfn);
      }
1246 1247
    }

1248 1249 1250 1251 1252
    var iterable = GetMethod(items, iteratorSymbol);
    var k;
    var result;
    var mappedValue;
    var nextValue;
1253

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

1258 1259 1260 1261 1262 1263 1264 1265 1266
      for (nextValue of
           { [iteratorSymbol]() { return GetIterator(items, iterable) } }) {
        if (mapping) {
          mappedValue = %_Call(mapfn, receiver, nextValue, k);
        } else {
          mappedValue = nextValue;
        }
        %CreateDataProperty(result, k, mappedValue);
        k++;
1267
      }
1268 1269 1270 1271 1272
      result.length = k;
      return result;
    } else {
      var len = TO_LENGTH(items.length);
      result = %IsConstructor(this) ? new this(len) : new GlobalArray(len);
1273

1274 1275 1276 1277 1278 1279 1280 1281
      for (k = 0; k < len; ++k) {
        nextValue = items[k];
        if (mapping) {
          mappedValue = %_Call(mapfn, receiver, nextValue, k);
        } else {
          mappedValue = nextValue;
        }
        %CreateDataProperty(result, k, mappedValue);
1282 1283
      }

1284 1285 1286 1287 1288 1289
      result.length = k;
      return result;
    }
  },
  1  /* Set function length. */
);
1290 1291

// ES6, draft 05-22-14, section 22.1.2.3
1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303
DEFINE_METHOD(
  GlobalArray,
  of(...args) {
    var length = args.length;
    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++) {
      %CreateDataProperty(array, i, args[i]);
    }
    array.length = length;
    return array;
1304
  }
1305
);
1306

1307
// -------------------------------------------------------------------
1308

1309 1310 1311 1312 1313 1314 1315 1316
// Set up unscopable properties on the Array.prototype object.
var unscopables = {
  __proto__: null,
  copyWithin: true,
  entries: true,
  fill: true,
  find: true,
  findIndex: true,
1317
  includes: true,
1318 1319 1320
  keys: true,
};

1321 1322
%ToFastProperties(unscopables);

1323
%AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables,
1324 1325
                  DONT_ENUM | READ_ONLY);

1326 1327 1328 1329 1330 1331 1332 1333 1334 1335
var ArrayIndexOf = GlobalArray.prototype.indexOf;
var ArrayJoin = GlobalArray.prototype.join;
var ArrayPop = GlobalArray.prototype.pop;
var ArrayPush = GlobalArray.prototype.push;
var ArraySlice = GlobalArray.prototype.slice;
var ArrayShift = GlobalArray.prototype.shift;
var ArraySort = GlobalArray.prototype.sort;
var ArraySplice = GlobalArray.prototype.splice;
var ArrayToString = GlobalArray.prototype.toString;
var ArrayUnshift = GlobalArray.prototype.unshift;
1336

1337 1338
// Array prototype functions that return iterators. They are exposed to the
// public API via Template::SetIntrinsicDataProperty().
1339 1340 1341 1342
var ArrayEntries = GlobalArray.prototype.entries;
var ArrayForEach = GlobalArray.prototype.forEach;
var ArrayKeys = GlobalArray.prototype.keys;
var ArrayValues = GlobalArray.prototype[iteratorSymbol];
1343

1344

1345 1346 1347
// 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.
1348
utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [
1349 1350 1351 1352 1353 1354 1355
  "indexOf", ArrayIndexOf,
  "join", ArrayJoin,
  "pop", ArrayPop,
  "push", ArrayPush,
  "shift", ArrayShift,
  "sort", ArraySort,
  "splice", ArraySplice
1356 1357
]);

1358
utils.SetUpLockedPrototype(InternalPackedArray, GlobalArray(), [
1359 1360 1361 1362
  "join", ArrayJoin,
  "pop", ArrayPop,
  "push", ArrayPush,
  "shift", ArrayShift
1363 1364
]);

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

1376 1377 1378 1379 1380
// -------------------------------------------------------------------
// Exports

utils.Export(function(to) {
  to.ArrayJoin = ArrayJoin;
1381
  to.ArrayPush = ArrayPush;
1382
  to.ArrayToString = ArrayToString;
1383
  to.ArrayValues = ArrayValues;
1384 1385
  to.InnerArrayFind = InnerArrayFind;
  to.InnerArrayFindIndex = InnerArrayFindIndex;
1386
  to.InnerArrayJoin = InnerArrayJoin;
1387
  to.InnerArraySort = InnerArraySort;
1388
  to.InnerArrayToLocaleString = InnerArrayToLocaleString;
1389 1390
});

1391
%InstallToContext([
1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402
  "array_entries_iterator", ArrayEntries,
  "array_for_each_iterator", ArrayForEach,
  "array_keys_iterator", ArrayKeys,
  "array_values_iterator", ArrayValues,
  // Fallback implementations of Array builtins.
  "array_pop", ArrayPopFallback,
  "array_push", ArrayPushFallback,
  "array_shift", ArrayShiftFallback,
  "array_splice", ArraySpliceFallback,
  "array_slice", ArraySliceFallback,
  "array_unshift", ArrayUnshiftFallback,
1403
]);
1404

1405
});