1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
7 // This file relies on the fact that the following declarations have been made
9 // var $Array = global.Array;
11 // -------------------------------------------------------------------
13 // Global list of arrays visited during toString, toLocaleString and
15 var visited_arrays = new InternalArray();
18 // Gets a sorted array of array keys. Useful for operations on sparse
19 // arrays. Dupes have not been removed.
20 function GetSortedArrayKeys(array, indices) {
21 var keys = new InternalArray();
22 if (IS_NUMBER(indices)) {
25 for (var i = 0; i < limit; ++i) {
27 if (!IS_UNDEFINED(e) || i in array) {
32 var length = indices.length;
33 for (var k = 0; k < length; ++k) {
35 if (!IS_UNDEFINED(key)) {
37 if (!IS_UNDEFINED(e) || key in array) {
42 %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
48 function SparseJoinWithSeparatorJS(array, len, convert, separator) {
49 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
51 var elements = new InternalArray(keys.length * 2);
53 for (var i = 0; i < keys.length; i++) {
55 if (key != previousKey) { // keys may contain duplicates.
57 if (!IS_STRING(e)) e = convert(e);
58 elements[i * 2] = key;
59 elements[i * 2 + 1] = e;
63 return %SparseJoinWithSeparator(elements, len, separator);
67 // Optimized for sparse arrays if separator is ''.
68 function SparseJoin(array, len, convert) {
69 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
71 var keys_length = keys.length;
73 var elements = new InternalArray(keys_length);
74 var elements_length = 0;
76 for (var i = 0; i < keys_length; i++) {
78 if (key != last_key) {
80 if (!IS_STRING(e)) e = convert(e);
81 elements[elements_length++] = e;
85 return %StringBuilderConcat(elements, elements_length, '');
89 function UseSparseVariant(array, length, is_array, touched) {
90 // Only use the sparse variant on arrays that are likely to be sparse and the
91 // number of elements touched in the operation is relatively small compared to
92 // the overall size of the array.
93 if (!is_array || length < 1000 || %IsObserved(array) ||
94 %HasComplexElements(array)) {
97 if (!%_IsSmi(length)) {
100 var elements_threshold = length >> 2; // No more than 75% holes
101 var estimated_elements = %EstimateNumberOfElements(array);
102 return (estimated_elements < elements_threshold) &&
103 (touched > estimated_elements * 4);
107 function Join(array, length, separator, convert) {
108 if (length == 0) return '';
110 var is_array = IS_ARRAY(array);
113 // If the array is cyclic, return the empty string for already
115 if (!%PushIfAbsent(visited_arrays, array)) return '';
118 // Attempt to convert the elements.
120 if (UseSparseVariant(array, length, is_array, length)) {
121 %NormalizeElements(array);
122 if (separator.length == 0) {
123 return SparseJoin(array, length, convert);
125 return SparseJoinWithSeparatorJS(array, length, convert, separator);
129 // Fast case for one-element arrays.
132 if (IS_STRING(e)) return e;
136 // Construct an array for the elements.
137 var elements = new InternalArray(length);
139 // We pull the empty separator check outside the loop for speed!
140 if (separator.length == 0) {
141 var elements_length = 0;
142 for (var i = 0; i < length; i++) {
144 if (!IS_STRING(e)) e = convert(e);
145 elements[elements_length++] = e;
147 elements.length = elements_length;
148 var result = %_FastOneByteArrayJoin(elements, '');
149 if (!IS_UNDEFINED(result)) return result;
150 return %StringBuilderConcat(elements, elements_length, '');
152 // Non-empty separator case.
153 // If the first element is a number then use the heuristic that the
154 // remaining elements are also likely to be numbers.
155 if (!IS_NUMBER(array[0])) {
156 for (var i = 0; i < length; i++) {
158 if (!IS_STRING(e)) e = convert(e);
162 for (var i = 0; i < length; i++) {
165 e = %_NumberToString(e);
166 } else if (!IS_STRING(e)) {
172 var result = %_FastOneByteArrayJoin(elements, separator);
173 if (!IS_UNDEFINED(result)) return result;
175 return %StringBuilderJoin(elements, length, separator);
177 // Make sure to remove the last element of the visited array no
178 // matter what happens.
179 if (is_array) visited_arrays.length = visited_arrays.length - 1;
184 function ConvertToString(x) {
185 // Assumes x is a non-string.
186 if (IS_NUMBER(x)) return %_NumberToString(x);
187 if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
188 return (IS_NULL_OR_UNDEFINED(x)) ? '' : %ToString(%DefaultString(x));
192 function ConvertToLocaleString(e) {
193 if (IS_NULL_OR_UNDEFINED(e)) {
196 // According to ES5, section 15.4.4.3, the toLocaleString conversion
197 // must throw a TypeError if ToObject(e).toLocaleString isn't
199 var e_obj = ToObject(e);
200 return %ToString(e_obj.toLocaleString());
205 // This function implements the optimized splice implementation that can use
206 // special array operations to handle sparse arrays in a sensible fashion.
207 function SparseSlice(array, start_i, del_count, len, deleted_elements) {
208 // Move deleted elements to a new array (the return value from splice).
209 var indices = %GetArrayKeys(array, start_i + del_count);
210 if (IS_NUMBER(indices)) {
212 for (var i = start_i; i < limit; ++i) {
213 var current = array[i];
214 if (!IS_UNDEFINED(current) || i in array) {
215 %AddElement(deleted_elements, i - start_i, current, NONE);
219 var length = indices.length;
220 for (var k = 0; k < length; ++k) {
221 var key = indices[k];
222 if (!IS_UNDEFINED(key)) {
223 if (key >= start_i) {
224 var current = array[key];
225 if (!IS_UNDEFINED(current) || key in array) {
226 %AddElement(deleted_elements, key - start_i, current, NONE);
235 // This function implements the optimized splice implementation that can use
236 // special array operations to handle sparse arrays in a sensible fashion.
237 function SparseMove(array, start_i, del_count, len, num_additional_args) {
238 // Bail out if no moving is necessary.
239 if (num_additional_args === del_count) return;
240 // Move data to new array.
241 var new_array = new InternalArray(
242 // Clamp array length to 2^32-1 to avoid early RangeError.
243 MathMin(len - del_count + num_additional_args, 0xffffffff));
245 var indices = %GetArrayKeys(array, len);
246 if (IS_NUMBER(indices)) {
248 for (var i = 0; i < start_i && i < limit; ++i) {
249 var current = array[i];
250 if (!IS_UNDEFINED(current) || i in array) {
251 new_array[i] = current;
254 for (var i = start_i + del_count; i < limit; ++i) {
255 var current = array[i];
256 if (!IS_UNDEFINED(current) || i in array) {
257 new_array[i - del_count + num_additional_args] = current;
261 var length = indices.length;
262 for (var k = 0; k < length; ++k) {
263 var key = indices[k];
264 if (!IS_UNDEFINED(key)) {
266 var current = array[key];
267 if (!IS_UNDEFINED(current) || key in array) {
268 new_array[key] = current;
270 } else if (key >= start_i + del_count) {
271 var current = array[key];
272 if (!IS_UNDEFINED(current) || key in array) {
273 var new_key = key - del_count + num_additional_args;
274 new_array[new_key] = current;
275 if (new_key > 0xffffffff) {
276 big_indices = big_indices || new InternalArray();
277 big_indices.push(new_key);
284 // Move contents of new_array into this array
285 %MoveArrayContents(new_array, array);
286 // Add any moved values that aren't elements anymore.
287 if (!IS_UNDEFINED(big_indices)) {
288 var length = big_indices.length;
289 for (var i = 0; i < length; ++i) {
290 var key = big_indices[i];
291 array[key] = new_array[key];
297 // This is part of the old simple-minded splice. We are using it either
298 // because the receiver is not an array (so we have no choice) or because we
299 // know we are not deleting or moving a lot of elements.
300 function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
301 var is_array = IS_ARRAY(array);
302 for (var i = 0; i < del_count; i++) {
303 var index = start_i + i;
304 if (HAS_INDEX(array, index, is_array)) {
305 var current = array[index];
306 // The spec requires [[DefineOwnProperty]] here, %AddElement is close
307 // enough (in that it ignores the prototype).
308 %AddElement(deleted_elements, i, current, NONE);
314 function SimpleMove(array, start_i, del_count, len, num_additional_args) {
315 var is_array = IS_ARRAY(array);
316 if (num_additional_args !== del_count) {
317 // Move the existing elements after the elements to be deleted
318 // to the right position in the resulting array.
319 if (num_additional_args > del_count) {
320 for (var i = len - del_count; i > start_i; i--) {
321 var from_index = i + del_count - 1;
322 var to_index = i + num_additional_args - 1;
323 if (HAS_INDEX(array, from_index, is_array)) {
324 array[to_index] = array[from_index];
326 delete array[to_index];
330 for (var i = start_i; i < len - del_count; i++) {
331 var from_index = i + del_count;
332 var to_index = i + num_additional_args;
333 if (HAS_INDEX(array, from_index, is_array)) {
334 array[to_index] = array[from_index];
336 delete array[to_index];
339 for (var i = len; i > len - del_count + num_additional_args; i--) {
347 // -------------------------------------------------------------------
350 function ArrayToString() {
353 if (IS_ARRAY(this)) {
355 if (func === ArrayJoin) {
356 return Join(this, this.length, ',', ConvertToString);
360 array = ToObject(this);
363 if (!IS_SPEC_FUNCTION(func)) {
364 return %_CallFunction(array, DefaultObjectToString);
366 return %_CallFunction(array, func);
370 function ArrayToLocaleString() {
371 var array = ToObject(this);
372 var arrayLen = array.length;
373 var len = TO_UINT32(arrayLen);
374 if (len === 0) return "";
375 return Join(array, len, ',', ConvertToLocaleString);
379 function ArrayJoin(separator) {
380 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
382 var array = TO_OBJECT_INLINE(this);
383 var length = TO_UINT32(array.length);
384 if (IS_UNDEFINED(separator)) {
386 } else if (!IS_STRING(separator)) {
387 separator = NonStringToString(separator);
390 var result = %_FastOneByteArrayJoin(array, separator);
391 if (!IS_UNDEFINED(result)) return result;
393 // Fast case for one-element arrays.
396 if (IS_STRING(e)) return e;
397 if (IS_NULL_OR_UNDEFINED(e)) return '';
398 return NonStringToString(e);
401 return Join(array, length, separator, ConvertToString);
405 function ObservedArrayPop(n) {
410 BeginPerformSplice(this);
414 EndPerformSplice(this);
415 EnqueueSpliceRecord(this, n, [value], 0);
421 // Removes the last element from the array and returns it. See
422 // ECMA-262, section 15.4.4.6.
423 function ArrayPop() {
424 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
426 var array = TO_OBJECT_INLINE(this);
427 var n = TO_UINT32(array.length);
433 if (%IsObserved(array))
434 return ObservedArrayPop.call(array, n);
437 var value = array[n];
438 Delete(array, ToName(n), true);
444 function ObservedArrayPush() {
445 var n = TO_UINT32(this.length);
446 var m = %_ArgumentsLength();
449 BeginPerformSplice(this);
450 for (var i = 0; i < m; i++) {
451 this[i+n] = %_Arguments(i);
453 var new_length = n + m;
454 this.length = new_length;
456 EndPerformSplice(this);
457 EnqueueSpliceRecord(this, n, [], m);
463 // Appends the arguments to the end of the array and returns the new
464 // length of the array. See ECMA-262, section 15.4.4.7.
465 function ArrayPush() {
466 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
468 if (%IsObserved(this))
469 return ObservedArrayPush.apply(this, arguments);
471 var array = TO_OBJECT_INLINE(this);
472 var n = TO_UINT32(array.length);
473 var m = %_ArgumentsLength();
475 for (var i = 0; i < m; i++) {
476 array[i+n] = %_Arguments(i);
479 var new_length = n + m;
480 array.length = new_length;
485 // Returns an array containing the array elements of the object followed
486 // by the array elements of each argument in order. See ECMA-262,
488 function ArrayConcatJS(arg1) { // length == 1
489 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.concat");
491 var array = ToObject(this);
492 var arg_count = %_ArgumentsLength();
493 var arrays = new InternalArray(1 + arg_count);
495 for (var i = 0; i < arg_count; i++) {
496 arrays[i + 1] = %_Arguments(i);
499 return %ArrayConcat(arrays);
503 // For implementing reverse() on large, sparse arrays.
504 function SparseReverse(array, len) {
505 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
506 var high_counter = keys.length - 1;
508 while (low_counter <= high_counter) {
509 var i = keys[low_counter];
510 var j = keys[high_counter];
512 var j_complement = len - j - 1;
515 if (j_complement <= i) {
517 while (keys[--high_counter] == j) { }
520 if (j_complement >= i) {
522 while (keys[++low_counter] == i) { }
526 var current_i = array[low];
527 if (!IS_UNDEFINED(current_i) || low in array) {
528 var current_j = array[high];
529 if (!IS_UNDEFINED(current_j) || high in array) {
530 array[low] = current_j;
531 array[high] = current_i;
533 array[high] = current_i;
537 var current_j = array[high];
538 if (!IS_UNDEFINED(current_j) || high in array) {
539 array[low] = current_j;
547 function ArrayReverse() {
548 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
550 var array = TO_OBJECT_INLINE(this);
551 var len = TO_UINT32(array.length);
553 if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
554 %NormalizeElements(array);
555 SparseReverse(array, len);
560 for (var i = 0; i < j; i++, j--) {
561 var current_i = array[i];
562 if (!IS_UNDEFINED(current_i) || i in array) {
563 var current_j = array[j];
564 if (!IS_UNDEFINED(current_j) || j in array) {
565 array[i] = current_j;
566 array[j] = current_i;
568 array[j] = current_i;
572 var current_j = array[j];
573 if (!IS_UNDEFINED(current_j) || j in array) {
574 array[i] = current_j;
583 function ObservedArrayShift(len) {
587 BeginPerformSplice(this);
588 SimpleMove(this, 0, 1, len, 0);
589 this.length = len - 1;
591 EndPerformSplice(this);
592 EnqueueSpliceRecord(this, 0, [first], 0);
598 function ArrayShift() {
599 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
601 var array = TO_OBJECT_INLINE(this);
602 var len = TO_UINT32(array.length);
609 if (ObjectIsSealed(array)) {
610 throw MakeTypeError("array_functions_change_sealed",
611 ["Array.prototype.shift"]);
614 if (%IsObserved(array))
615 return ObservedArrayShift.call(array, len);
617 var first = array[0];
619 if (UseSparseVariant(array, len, IS_ARRAY(array), len)) {
620 SparseMove(array, 0, 1, len, 0);
622 SimpleMove(array, 0, 1, len, 0);
625 array.length = len - 1;
630 function ObservedArrayUnshift() {
631 var len = TO_UINT32(this.length);
632 var num_arguments = %_ArgumentsLength();
635 BeginPerformSplice(this);
636 SimpleMove(this, 0, 0, len, num_arguments);
637 for (var i = 0; i < num_arguments; i++) {
638 this[i] = %_Arguments(i);
640 var new_length = len + num_arguments;
641 this.length = new_length;
643 EndPerformSplice(this);
644 EnqueueSpliceRecord(this, 0, [], num_arguments);
650 function ArrayUnshift(arg1) { // length == 1
651 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
653 if (%IsObserved(this))
654 return ObservedArrayUnshift.apply(this, arguments);
656 var array = TO_OBJECT_INLINE(this);
657 var len = TO_UINT32(array.length);
658 var num_arguments = %_ArgumentsLength();
660 if (len > 0 && UseSparseVariant(array, len, IS_ARRAY(array), len) &&
661 !ObjectIsSealed(array)) {
662 SparseMove(array, 0, 0, len, num_arguments);
664 SimpleMove(array, 0, 0, len, num_arguments);
667 for (var i = 0; i < num_arguments; i++) {
668 array[i] = %_Arguments(i);
671 var new_length = len + num_arguments;
672 array.length = new_length;
677 function ArraySlice(start, end) {
678 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
680 var array = TO_OBJECT_INLINE(this);
681 var len = TO_UINT32(array.length);
682 var start_i = TO_INTEGER(start);
685 if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
689 if (start_i < 0) start_i = 0;
691 if (start_i > len) start_i = len;
696 if (end_i < 0) end_i = 0;
698 if (end_i > len) end_i = len;
703 if (end_i < start_i) return result;
705 if (UseSparseVariant(array, len, IS_ARRAY(array), end_i - start_i)) {
706 %NormalizeElements(array);
707 %NormalizeElements(result);
708 SparseSlice(array, start_i, end_i - start_i, len, result);
710 SimpleSlice(array, start_i, end_i - start_i, len, result);
713 result.length = end_i - start_i;
719 function ComputeSpliceStartIndex(start_i, len) {
722 return start_i < 0 ? 0 : start_i;
725 return start_i > len ? len : start_i;
729 function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
730 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
731 // given as a request to delete all the elements from the start.
732 // And it differs from the case of undefined delete count.
733 // This does not follow ECMA-262, but we do the same for
736 if (num_arguments == 1)
737 return len - start_i;
739 del_count = TO_INTEGER(delete_count);
743 if (del_count > len - start_i)
744 return len - start_i;
750 function ObservedArraySplice(start, delete_count) {
751 var num_arguments = %_ArgumentsLength();
752 var len = TO_UINT32(this.length);
753 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
754 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
756 var deleted_elements = [];
757 deleted_elements.length = del_count;
758 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
761 BeginPerformSplice(this);
763 SimpleSlice(this, start_i, del_count, len, deleted_elements);
764 SimpleMove(this, start_i, del_count, len, num_elements_to_add);
766 // Insert the arguments into the resulting array in
767 // place of the deleted elements.
769 var arguments_index = 2;
770 var arguments_length = %_ArgumentsLength();
771 while (arguments_index < arguments_length) {
772 this[i++] = %_Arguments(arguments_index++);
774 this.length = len - del_count + num_elements_to_add;
777 EndPerformSplice(this);
778 if (deleted_elements.length || num_elements_to_add) {
779 EnqueueSpliceRecord(this,
781 deleted_elements.slice(),
782 num_elements_to_add);
786 // Return the deleted elements.
787 return deleted_elements;
791 function ArraySplice(start, delete_count) {
792 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
794 if (%IsObserved(this))
795 return ObservedArraySplice.apply(this, arguments);
797 var num_arguments = %_ArgumentsLength();
798 var array = TO_OBJECT_INLINE(this);
799 var len = TO_UINT32(array.length);
800 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
801 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
803 var deleted_elements = [];
804 deleted_elements.length = del_count;
805 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
807 if (del_count != num_elements_to_add && ObjectIsSealed(array)) {
808 throw MakeTypeError("array_functions_change_sealed",
809 ["Array.prototype.splice"]);
810 } else if (del_count > 0 && ObjectIsFrozen(array)) {
811 throw MakeTypeError("array_functions_on_frozen",
812 ["Array.prototype.splice"]);
815 var changed_elements = del_count;
816 if (num_elements_to_add != del_count) {
817 // If the slice needs to do a actually move elements after the insertion
818 // point, then include those in the estimate of changed elements.
819 changed_elements += len - start_i - del_count;
821 if (UseSparseVariant(array, len, IS_ARRAY(array), changed_elements)) {
822 %NormalizeElements(array);
823 %NormalizeElements(deleted_elements);
824 SparseSlice(array, start_i, del_count, len, deleted_elements);
825 SparseMove(array, start_i, del_count, len, num_elements_to_add);
827 SimpleSlice(array, start_i, del_count, len, deleted_elements);
828 SimpleMove(array, start_i, del_count, len, num_elements_to_add);
831 // Insert the arguments into the resulting array in
832 // place of the deleted elements.
834 var arguments_index = 2;
835 var arguments_length = %_ArgumentsLength();
836 while (arguments_index < arguments_length) {
837 array[i++] = %_Arguments(arguments_index++);
839 array.length = len - del_count + num_elements_to_add;
841 // Return the deleted elements.
842 return deleted_elements;
846 function ArraySort(comparefn) {
847 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
849 // In-place QuickSort algorithm.
850 // For short (length <= 22) arrays, insertion sort is used for efficiency.
852 if (!IS_SPEC_FUNCTION(comparefn)) {
853 comparefn = function (x, y) {
854 if (x === y) return 0;
855 if (%_IsSmi(x) && %_IsSmi(y)) {
856 return %SmiLexicographicCompare(x, y);
860 if (x == y) return 0;
861 else return x < y ? -1 : 1;
864 var receiver = %GetDefaultReceiver(comparefn);
866 var InsertionSort = function InsertionSort(a, from, to) {
867 for (var i = from + 1; i < to; i++) {
869 for (var j = i - 1; j >= from; j--) {
871 var order = %_CallFunction(receiver, tmp, element, comparefn);
882 var GetThirdIndex = function(a, from, to) {
884 // Use both 'from' and 'to' to determine the pivot candidates.
885 var increment = 200 + ((to - from) & 15);
886 for (var i = from + 1, j = 0; i < to - 1; i += increment, j++) {
887 t_array[j] = [i, a[i]];
889 %_CallFunction(t_array, function(a, b) {
890 return %_CallFunction(receiver, a[1], b[1], comparefn);
892 var third_index = t_array[t_array.length >> 1][0];
896 var QuickSort = function QuickSort(a, from, to) {
899 // Insertion sort is faster for short arrays.
900 if (to - from <= 10) {
901 InsertionSort(a, from, to);
904 if (to - from > 1000) {
905 third_index = GetThirdIndex(a, from, to);
907 third_index = from + ((to - from) >> 1);
909 // Find a pivot as the median of first, last and middle element.
912 var v2 = a[third_index];
913 var c01 = %_CallFunction(receiver, v0, v1, comparefn);
915 // v1 < v0, so swap them.
920 var c02 = %_CallFunction(receiver, v0, v2, comparefn);
928 // v0 <= v1 && v0 < v2
929 var c12 = %_CallFunction(receiver, v1, v2, comparefn);
941 var low_end = from + 1; // Upper bound of elements lower than pivot.
942 var high_start = to - 1; // Lower bound of elements greater than pivot.
943 a[third_index] = a[low_end];
946 // From low_end to i are elements equal to pivot.
947 // From i to high_start are elements that haven't been compared yet.
948 partition: for (var i = low_end + 1; i < high_start; i++) {
950 var order = %_CallFunction(receiver, element, pivot, comparefn);
953 a[low_end] = element;
955 } else if (order > 0) {
958 if (high_start == i) break partition;
959 var top_elem = a[high_start];
960 order = %_CallFunction(receiver, top_elem, pivot, comparefn);
962 a[i] = a[high_start];
963 a[high_start] = element;
967 a[low_end] = element;
972 if (to - high_start < low_end - from) {
973 QuickSort(a, high_start, to);
976 QuickSort(a, from, low_end);
982 // Copy elements in the range 0..length from obj's prototype chain
983 // to obj itself, if obj has holes. Return one more than the maximal index
984 // of a prototype property.
985 var CopyFromPrototype = function CopyFromPrototype(obj, length) {
987 for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
988 var indices = %GetArrayKeys(proto, length);
989 if (IS_NUMBER(indices)) {
991 var proto_length = indices;
992 for (var i = 0; i < proto_length; i++) {
993 if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
995 if (i >= max) { max = i + 1; }
999 for (var i = 0; i < indices.length; i++) {
1000 var index = indices[i];
1001 if (!IS_UNDEFINED(index) && !HAS_OWN_PROPERTY(obj, index)
1002 && HAS_OWN_PROPERTY(proto, index)) {
1003 obj[index] = proto[index];
1004 if (index >= max) { max = index + 1; }
1012 // Set a value of "undefined" on all indices in the range from..to
1013 // where a prototype of obj has an element. I.e., shadow all prototype
1014 // elements in that range.
1015 var ShadowPrototypeElements = function(obj, from, to) {
1016 for (var proto = %_GetPrototype(obj); proto; proto = %_GetPrototype(proto)) {
1017 var indices = %GetArrayKeys(proto, to);
1018 if (IS_NUMBER(indices)) {
1019 // It's an interval.
1020 var proto_length = indices;
1021 for (var i = from; i < proto_length; i++) {
1022 if (HAS_OWN_PROPERTY(proto, i)) {
1027 for (var i = 0; i < indices.length; i++) {
1028 var index = indices[i];
1029 if (!IS_UNDEFINED(index) && from <= index &&
1030 HAS_OWN_PROPERTY(proto, index)) {
1031 obj[index] = UNDEFINED;
1038 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1039 // Copy defined elements from the end to fill in all holes and undefineds
1040 // in the beginning of the array. Write undefineds and holes at the end
1041 // after loop is finished.
1042 var first_undefined = 0;
1043 var last_defined = length - 1;
1045 while (first_undefined < last_defined) {
1046 // Find first undefined element.
1047 while (first_undefined < last_defined &&
1048 !IS_UNDEFINED(obj[first_undefined])) {
1051 // Maintain the invariant num_holes = the number of holes in the original
1052 // array with indices <= first_undefined or > last_defined.
1053 if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
1057 // Find last defined element.
1058 while (first_undefined < last_defined &&
1059 IS_UNDEFINED(obj[last_defined])) {
1060 if (!HAS_OWN_PROPERTY(obj, last_defined)) {
1065 if (first_undefined < last_defined) {
1066 // Fill in hole or undefined.
1067 obj[first_undefined] = obj[last_defined];
1068 obj[last_defined] = UNDEFINED;
1071 // If there were any undefineds in the entire array, first_undefined
1072 // points to one past the last defined element. Make this true if
1073 // there were no undefineds, as well, so that first_undefined == number
1074 // of defined elements.
1075 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
1076 // Fill in the undefineds and the holes. There may be a hole where
1077 // an undefined should be and vice versa.
1079 for (i = first_undefined; i < length - num_holes; i++) {
1082 for (i = length - num_holes; i < length; i++) {
1083 // For compatability with Webkit, do not expose elements in the prototype.
1084 if (i in %_GetPrototype(obj)) {
1091 // Return the number of defined elements.
1092 return first_undefined;
1095 var length = TO_UINT32(this.length);
1096 if (length < 2) return this;
1098 var is_array = IS_ARRAY(this);
1099 var max_prototype_element;
1101 // For compatibility with JSC, we also sort elements inherited from
1102 // the prototype chain on non-Array objects.
1103 // We do this by copying them to this object and sorting only
1104 // own elements. This is not very efficient, but sorting with
1105 // inherited elements happens very, very rarely, if at all.
1106 // The specification allows "implementation dependent" behavior
1107 // if an element on the prototype chain has an element that
1108 // might interact with sorting.
1109 max_prototype_element = CopyFromPrototype(this, length);
1112 // %RemoveArrayHoles returns -1 if fast removal is not supported.
1113 var num_non_undefined = %RemoveArrayHoles(this, length);
1115 if (num_non_undefined == -1) {
1116 // The array is observed, or there were indexed accessors in the array.
1117 // Move array holes and undefineds to the end using a Javascript function
1118 // that is safe in the presence of accessors and is observable.
1119 num_non_undefined = SafeRemoveArrayHoles(this);
1122 QuickSort(this, 0, num_non_undefined);
1124 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
1125 // For compatibility with JSC, we shadow any elements in the prototype
1126 // chain that has become exposed by sort moving a hole to its position.
1127 ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
1134 // The following functions cannot be made efficient on sparse arrays while
1135 // preserving the semantics, since the calls to the receiver function can add
1136 // or delete elements from the array.
1137 function ArrayFilter(f, receiver) {
1138 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");
1140 // Pull out the length so that modifications to the length in the
1141 // loop will not affect the looping and side effects are visible.
1142 var array = ToObject(this);
1143 var length = ToUint32(array.length);
1145 if (!IS_SPEC_FUNCTION(f)) {
1146 throw MakeTypeError('called_non_callable', [ f ]);
1148 var needs_wrapper = false;
1149 if (IS_NULL_OR_UNDEFINED(receiver)) {
1150 receiver = %GetDefaultReceiver(f) || receiver;
1152 needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1155 var result = new $Array();
1156 var accumulator = new InternalArray();
1157 var accumulator_length = 0;
1158 var is_array = IS_ARRAY(array);
1159 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1160 for (var i = 0; i < length; i++) {
1161 if (HAS_INDEX(array, i, is_array)) {
1162 var element = array[i];
1163 // Prepare break slots for debugger step in.
1164 if (stepping) %DebugPrepareStepInIfStepping(f);
1165 var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
1166 if (%_CallFunction(new_receiver, element, i, array, f)) {
1167 accumulator[accumulator_length++] = element;
1171 %MoveArrayContents(accumulator, result);
1176 function ArrayForEach(f, receiver) {
1177 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");
1179 // Pull out the length so that modifications to the length in the
1180 // loop will not affect the looping and side effects are visible.
1181 var array = ToObject(this);
1182 var length = TO_UINT32(array.length);
1184 if (!IS_SPEC_FUNCTION(f)) {
1185 throw MakeTypeError('called_non_callable', [ f ]);
1187 var needs_wrapper = false;
1188 if (IS_NULL_OR_UNDEFINED(receiver)) {
1189 receiver = %GetDefaultReceiver(f) || receiver;
1191 needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1194 var is_array = IS_ARRAY(array);
1195 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1196 for (var i = 0; i < length; i++) {
1197 if (HAS_INDEX(array, i, is_array)) {
1198 var element = array[i];
1199 // Prepare break slots for debugger step in.
1200 if (stepping) %DebugPrepareStepInIfStepping(f);
1201 var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
1202 %_CallFunction(new_receiver, element, i, array, f);
1208 // Executes the function once for each element present in the
1209 // array until it finds one where callback returns true.
1210 function ArraySome(f, receiver) {
1211 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");
1213 // Pull out the length so that modifications to the length in the
1214 // loop will not affect the looping and side effects are visible.
1215 var array = ToObject(this);
1216 var length = TO_UINT32(array.length);
1218 if (!IS_SPEC_FUNCTION(f)) {
1219 throw MakeTypeError('called_non_callable', [ f ]);
1221 var needs_wrapper = false;
1222 if (IS_NULL_OR_UNDEFINED(receiver)) {
1223 receiver = %GetDefaultReceiver(f) || receiver;
1225 needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1228 var is_array = IS_ARRAY(array);
1229 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1230 for (var i = 0; i < length; i++) {
1231 if (HAS_INDEX(array, i, is_array)) {
1232 var element = array[i];
1233 // Prepare break slots for debugger step in.
1234 if (stepping) %DebugPrepareStepInIfStepping(f);
1235 var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
1236 if (%_CallFunction(new_receiver, element, i, array, f)) return true;
1243 function ArrayEvery(f, receiver) {
1244 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");
1246 // Pull out the length so that modifications to the length in the
1247 // loop will not affect the looping and side effects are visible.
1248 var array = ToObject(this);
1249 var length = TO_UINT32(array.length);
1251 if (!IS_SPEC_FUNCTION(f)) {
1252 throw MakeTypeError('called_non_callable', [ f ]);
1254 var needs_wrapper = false;
1255 if (IS_NULL_OR_UNDEFINED(receiver)) {
1256 receiver = %GetDefaultReceiver(f) || receiver;
1258 needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1261 var is_array = IS_ARRAY(array);
1262 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1263 for (var i = 0; i < length; i++) {
1264 if (HAS_INDEX(array, i, is_array)) {
1265 var element = array[i];
1266 // Prepare break slots for debugger step in.
1267 if (stepping) %DebugPrepareStepInIfStepping(f);
1268 var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
1269 if (!%_CallFunction(new_receiver, element, i, array, f)) return false;
1275 function ArrayMap(f, receiver) {
1276 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map");
1278 // Pull out the length so that modifications to the length in the
1279 // loop will not affect the looping and side effects are visible.
1280 var array = ToObject(this);
1281 var length = TO_UINT32(array.length);
1283 if (!IS_SPEC_FUNCTION(f)) {
1284 throw MakeTypeError('called_non_callable', [ f ]);
1286 var needs_wrapper = false;
1287 if (IS_NULL_OR_UNDEFINED(receiver)) {
1288 receiver = %GetDefaultReceiver(f) || receiver;
1290 needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
1293 var result = new $Array();
1294 var accumulator = new InternalArray(length);
1295 var is_array = IS_ARRAY(array);
1296 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
1297 for (var i = 0; i < length; i++) {
1298 if (HAS_INDEX(array, i, is_array)) {
1299 var element = array[i];
1300 // Prepare break slots for debugger step in.
1301 if (stepping) %DebugPrepareStepInIfStepping(f);
1302 var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
1303 accumulator[i] = %_CallFunction(new_receiver, element, i, array, f);
1306 %MoveArrayContents(accumulator, result);
1311 function ArrayIndexOf(element, index) {
1312 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1314 var length = TO_UINT32(this.length);
1315 if (length == 0) return -1;
1316 if (IS_UNDEFINED(index)) {
1319 index = TO_INTEGER(index);
1320 // If index is negative, index from the end of the array.
1322 index = length + index;
1323 // If index is still negative, search the entire array.
1324 if (index < 0) index = 0;
1329 if (UseSparseVariant(this, length, IS_ARRAY(this), max - min)) {
1330 %NormalizeElements(this);
1331 var indices = %GetArrayKeys(this, length);
1332 if (IS_NUMBER(indices)) {
1333 // It's an interval.
1334 max = indices; // Capped by length already.
1335 // Fall through to loop below.
1337 if (indices.length == 0) return -1;
1338 // Get all the keys in sorted order.
1339 var sortedKeys = GetSortedArrayKeys(this, indices);
1340 var n = sortedKeys.length;
1342 while (i < n && sortedKeys[i] < index) i++;
1344 var key = sortedKeys[i];
1345 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1351 // Lookup through the array.
1352 if (!IS_UNDEFINED(element)) {
1353 for (var i = min; i < max; i++) {
1354 if (this[i] === element) return i;
1358 // Lookup through the array.
1359 for (var i = min; i < max; i++) {
1360 if (IS_UNDEFINED(this[i]) && i in this) {
1368 function ArrayLastIndexOf(element, index) {
1369 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1371 var length = TO_UINT32(this.length);
1372 if (length == 0) return -1;
1373 if (%_ArgumentsLength() < 2) {
1376 index = TO_INTEGER(index);
1377 // If index is negative, index from end of the array.
1378 if (index < 0) index += length;
1379 // If index is still negative, do not search the array.
1380 if (index < 0) return -1;
1381 else if (index >= length) index = length - 1;
1385 if (UseSparseVariant(this, length, IS_ARRAY(this), index)) {
1386 %NormalizeElements(this);
1387 var indices = %GetArrayKeys(this, index + 1);
1388 if (IS_NUMBER(indices)) {
1389 // It's an interval.
1390 max = indices; // Capped by index already.
1391 // Fall through to loop below.
1393 if (indices.length == 0) return -1;
1394 // Get all the keys in sorted order.
1395 var sortedKeys = GetSortedArrayKeys(this, indices);
1396 var i = sortedKeys.length - 1;
1398 var key = sortedKeys[i];
1399 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1405 // Lookup through the array.
1406 if (!IS_UNDEFINED(element)) {
1407 for (var i = max; i >= min; i--) {
1408 if (this[i] === element) return i;
1412 for (var i = max; i >= min; i--) {
1413 if (IS_UNDEFINED(this[i]) && i in this) {
1421 function ArrayReduce(callback, current) {
1422 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1424 // Pull out the length so that modifications to the length in the
1425 // loop will not affect the looping and side effects are visible.
1426 var array = ToObject(this);
1427 var length = ToUint32(array.length);
1429 if (!IS_SPEC_FUNCTION(callback)) {
1430 throw MakeTypeError('called_non_callable', [callback]);
1433 var is_array = IS_ARRAY(array);
1435 find_initial: if (%_ArgumentsLength() < 2) {
1436 for (; i < length; i++) {
1437 if (HAS_INDEX(array, i, is_array)) {
1438 current = array[i++];
1442 throw MakeTypeError('reduce_no_initial', []);
1445 var receiver = %GetDefaultReceiver(callback);
1446 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1447 for (; i < length; i++) {
1448 if (HAS_INDEX(array, i, is_array)) {
1449 var element = array[i];
1450 // Prepare break slots for debugger step in.
1451 if (stepping) %DebugPrepareStepInIfStepping(callback);
1452 current = %_CallFunction(receiver, current, element, i, array, callback);
1458 function ArrayReduceRight(callback, current) {
1459 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight");
1461 // Pull out the length so that side effects are visible before the
1462 // callback function is checked.
1463 var array = ToObject(this);
1464 var length = ToUint32(array.length);
1466 if (!IS_SPEC_FUNCTION(callback)) {
1467 throw MakeTypeError('called_non_callable', [callback]);
1470 var is_array = IS_ARRAY(array);
1472 find_initial: if (%_ArgumentsLength() < 2) {
1473 for (; i >= 0; i--) {
1474 if (HAS_INDEX(array, i, is_array)) {
1475 current = array[i--];
1479 throw MakeTypeError('reduce_no_initial', []);
1482 var receiver = %GetDefaultReceiver(callback);
1483 var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(callback);
1484 for (; i >= 0; i--) {
1485 if (HAS_INDEX(array, i, is_array)) {
1486 var element = array[i];
1487 // Prepare break slots for debugger step in.
1488 if (stepping) %DebugPrepareStepInIfStepping(callback);
1489 current = %_CallFunction(receiver, current, element, i, array, callback);
1496 function ArrayIsArray(obj) {
1497 return IS_ARRAY(obj);
1501 // -------------------------------------------------------------------
1503 function SetUpArray() {
1504 %CheckIsBootstrapping();
1506 // Set up non-enumerable constructor property on the Array.prototype
1508 %AddNamedProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
1510 // Set up unscopable properties on the Array.prototype object.
1520 %AddNamedProperty($Array.prototype, symbolUnscopables, unscopables,
1521 DONT_ENUM | READ_ONLY);
1523 // Set up non-enumerable functions on the Array object.
1524 InstallFunctions($Array, DONT_ENUM, $Array(
1525 "isArray", ArrayIsArray
1528 var specialFunctions = %SpecialArrayFunctions();
1530 var getFunction = function(name, jsBuiltin, len) {
1532 if (specialFunctions.hasOwnProperty(name)) {
1533 f = specialFunctions[name];
1535 if (!IS_UNDEFINED(len)) {
1536 %FunctionSetLength(f, len);
1541 // Set up non-enumerable functions of the Array.prototype object and
1543 // Manipulate the length of some of the functions to meet
1544 // expectations set by ECMA-262 or Mozilla.
1545 InstallFunctions($Array.prototype, DONT_ENUM, $Array(
1546 "toString", getFunction("toString", ArrayToString),
1547 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
1548 "join", getFunction("join", ArrayJoin),
1549 "pop", getFunction("pop", ArrayPop),
1550 "push", getFunction("push", ArrayPush, 1),
1551 "concat", getFunction("concat", ArrayConcatJS, 1),
1552 "reverse", getFunction("reverse", ArrayReverse),
1553 "shift", getFunction("shift", ArrayShift),
1554 "unshift", getFunction("unshift", ArrayUnshift, 1),
1555 "slice", getFunction("slice", ArraySlice, 2),
1556 "splice", getFunction("splice", ArraySplice, 2),
1557 "sort", getFunction("sort", ArraySort),
1558 "filter", getFunction("filter", ArrayFilter, 1),
1559 "forEach", getFunction("forEach", ArrayForEach, 1),
1560 "some", getFunction("some", ArraySome, 1),
1561 "every", getFunction("every", ArrayEvery, 1),
1562 "map", getFunction("map", ArrayMap, 1),
1563 "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
1564 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1565 "reduce", getFunction("reduce", ArrayReduce, 1),
1566 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1569 %FinishArrayPrototypeSetup($Array.prototype);
1571 // The internal Array prototype doesn't need to be fancy, since it's never
1572 // exposed to user code.
1573 // Adding only the functions that are actually used.
1574 SetUpLockedPrototype(InternalArray, $Array(), $Array(
1575 "concat", getFunction("concat", ArrayConcatJS),
1576 "indexOf", getFunction("indexOf", ArrayIndexOf),
1577 "join", getFunction("join", ArrayJoin),
1578 "pop", getFunction("pop", ArrayPop),
1579 "push", getFunction("push", ArrayPush),
1580 "splice", getFunction("splice", ArraySplice)
1583 SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
1584 "join", getFunction("join", ArrayJoin),
1585 "pop", getFunction("pop", ArrayPop),
1586 "push", getFunction("push", ArrayPush)