1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 // This file relies on the fact that the following declarations have been made
30 // var $Array = global.Array;
32 // -------------------------------------------------------------------
34 // Global list of arrays visited during toString, toLocaleString and
36 var visited_arrays = new InternalArray();
39 // Gets a sorted array of array keys. Useful for operations on sparse
40 // arrays. Dupes have not been removed.
41 function GetSortedArrayKeys(array, indices) {
42 var keys = new InternalArray();
43 if (IS_NUMBER(indices)) {
46 for (var i = 0; i < limit; ++i) {
48 if (!IS_UNDEFINED(e) || i in array) {
53 var length = indices.length;
54 for (var k = 0; k < length; ++k) {
56 if (!IS_UNDEFINED(key)) {
58 if (!IS_UNDEFINED(e) || key in array) {
63 %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort);
69 function SparseJoinWithSeparator(array, len, convert, separator) {
70 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
72 var elements = new InternalArray(keys.length * 2);
74 for (var i = 0; i < keys.length; i++) {
76 if (key != previousKey) { // keys may contain duplicates.
78 if (!IS_STRING(e)) e = convert(e);
79 elements[i * 2] = key;
80 elements[i * 2 + 1] = e;
84 return %SparseJoinWithSeparator(elements, len, separator);
88 // Optimized for sparse arrays if separator is ''.
89 function SparseJoin(array, len, convert) {
90 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
92 var keys_length = keys.length;
94 var elements = new InternalArray(keys_length);
95 var elements_length = 0;
97 for (var i = 0; i < keys_length; i++) {
99 if (key != last_key) {
101 if (!IS_STRING(e)) e = convert(e);
102 elements[elements_length++] = e;
106 return %StringBuilderConcat(elements, elements_length, '');
110 function UseSparseVariant(object, length, is_array) {
114 %EstimateNumberOfElements(object) < (length >> 2));
118 function Join(array, length, separator, convert) {
119 if (length == 0) return '';
121 var is_array = IS_ARRAY(array);
124 // If the array is cyclic, return the empty string for already
126 if (!%PushIfAbsent(visited_arrays, array)) return '';
129 // Attempt to convert the elements.
131 if (UseSparseVariant(array, length, is_array)) {
132 if (separator.length == 0) {
133 return SparseJoin(array, length, convert);
135 return SparseJoinWithSeparator(array, length, convert, separator);
139 // Fast case for one-element arrays.
142 if (IS_STRING(e)) return e;
146 // Construct an array for the elements.
147 var elements = new InternalArray(length);
149 // We pull the empty separator check outside the loop for speed!
150 if (separator.length == 0) {
151 var elements_length = 0;
152 for (var i = 0; i < length; i++) {
154 if (!IS_STRING(e)) e = convert(e);
155 elements[elements_length++] = e;
157 elements.length = elements_length;
158 var result = %_FastAsciiArrayJoin(elements, '');
159 if (!IS_UNDEFINED(result)) return result;
160 return %StringBuilderConcat(elements, elements_length, '');
162 // Non-empty separator case.
163 // If the first element is a number then use the heuristic that the
164 // remaining elements are also likely to be numbers.
165 if (!IS_NUMBER(array[0])) {
166 for (var i = 0; i < length; i++) {
168 if (!IS_STRING(e)) e = convert(e);
172 for (var i = 0; i < length; i++) {
175 e = %_NumberToString(e);
176 } else if (!IS_STRING(e)) {
182 var result = %_FastAsciiArrayJoin(elements, separator);
183 if (!IS_UNDEFINED(result)) return result;
185 return %StringBuilderJoin(elements, length, separator);
187 // Make sure to remove the last element of the visited array no
188 // matter what happens.
189 if (is_array) visited_arrays.length = visited_arrays.length - 1;
194 function ConvertToString(x) {
195 // Assumes x is a non-string.
196 if (IS_NUMBER(x)) return %_NumberToString(x);
197 if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
198 return (IS_NULL_OR_UNDEFINED(x)) ? '' : %ToString(%DefaultString(x));
202 function ConvertToLocaleString(e) {
203 if (IS_NULL_OR_UNDEFINED(e)) {
206 // According to ES5, section 15.4.4.3, the toLocaleString conversion
207 // must throw a TypeError if ToObject(e).toLocaleString isn't
209 var e_obj = ToObject(e);
210 return %ToString(e_obj.toLocaleString());
215 // This function implements the optimized splice implementation that can use
216 // special array operations to handle sparse arrays in a sensible fashion.
217 function SmartSlice(array, start_i, del_count, len, deleted_elements) {
218 // Move deleted elements to a new array (the return value from splice).
219 var indices = %GetArrayKeys(array, start_i + del_count);
220 if (IS_NUMBER(indices)) {
222 for (var i = start_i; i < limit; ++i) {
223 var current = array[i];
224 if (!IS_UNDEFINED(current) || i in array) {
225 deleted_elements[i - start_i] = current;
229 var length = indices.length;
230 for (var k = 0; k < length; ++k) {
231 var key = indices[k];
232 if (!IS_UNDEFINED(key)) {
233 if (key >= start_i) {
234 var current = array[key];
235 if (!IS_UNDEFINED(current) || key in array) {
236 deleted_elements[key - start_i] = current;
245 // This function implements the optimized splice implementation that can use
246 // special array operations to handle sparse arrays in a sensible fashion.
247 function SmartMove(array, start_i, del_count, len, num_additional_args) {
248 // Move data to new array.
249 var new_array = new InternalArray(len - del_count + num_additional_args);
250 var indices = %GetArrayKeys(array, len);
251 if (IS_NUMBER(indices)) {
253 for (var i = 0; i < start_i && i < limit; ++i) {
254 var current = array[i];
255 if (!IS_UNDEFINED(current) || i in array) {
256 new_array[i] = current;
259 for (var i = start_i + del_count; i < limit; ++i) {
260 var current = array[i];
261 if (!IS_UNDEFINED(current) || i in array) {
262 new_array[i - del_count + num_additional_args] = current;
266 var length = indices.length;
267 for (var k = 0; k < length; ++k) {
268 var key = indices[k];
269 if (!IS_UNDEFINED(key)) {
271 var current = array[key];
272 if (!IS_UNDEFINED(current) || key in array) {
273 new_array[key] = current;
275 } else if (key >= start_i + del_count) {
276 var current = array[key];
277 if (!IS_UNDEFINED(current) || key in array) {
278 new_array[key - del_count + num_additional_args] = current;
284 // Move contents of new_array into this array
285 %MoveArrayContents(new_array, array);
289 // This is part of the old simple-minded splice. We are using it either
290 // because the receiver is not an array (so we have no choice) or because we
291 // know we are not deleting or moving a lot of elements.
292 function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
293 for (var i = 0; i < del_count; i++) {
294 var index = start_i + i;
295 // The spec could also be interpreted such that %HasLocalProperty
296 // would be the appropriate test. We follow KJS in consulting the
298 var current = array[index];
299 if (!IS_UNDEFINED(current) || index in array) {
300 deleted_elements[i] = current;
306 function SimpleMove(array, start_i, del_count, len, num_additional_args) {
307 if (num_additional_args !== del_count) {
308 // Move the existing elements after the elements to be deleted
309 // to the right position in the resulting array.
310 if (num_additional_args > del_count) {
311 for (var i = len - del_count; i > start_i; i--) {
312 var from_index = i + del_count - 1;
313 var to_index = i + num_additional_args - 1;
314 // The spec could also be interpreted such that
315 // %HasLocalProperty would be the appropriate test. We follow
316 // KJS in consulting the prototype.
317 var current = array[from_index];
318 if (!IS_UNDEFINED(current) || from_index in array) {
319 array[to_index] = current;
321 delete array[to_index];
325 for (var i = start_i; i < len - del_count; i++) {
326 var from_index = i + del_count;
327 var to_index = i + num_additional_args;
328 // The spec could also be interpreted such that
329 // %HasLocalProperty would be the appropriate test. We follow
330 // KJS in consulting the prototype.
331 var current = array[from_index];
332 if (!IS_UNDEFINED(current) || from_index in array) {
333 array[to_index] = current;
335 delete array[to_index];
338 for (var i = len; i > len - del_count + num_additional_args; i--) {
346 // -------------------------------------------------------------------
349 function ArrayToString() {
352 if (IS_ARRAY(this)) {
354 if (func === ArrayJoin) {
355 return Join(this, this.length, ',', ConvertToString);
359 array = ToObject(this);
362 if (!IS_SPEC_FUNCTION(func)) {
363 return %_CallFunction(array, ObjectToString);
365 return %_CallFunction(array, func);
369 function ArrayToLocaleString() {
370 var array = ToObject(this);
371 var arrayLen = array.length;
372 var len = TO_UINT32(arrayLen);
373 if (len === 0) return "";
374 return Join(array, len, ',', ConvertToLocaleString);
378 function ArrayJoin(separator) {
379 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
381 var length = TO_UINT32(this.length);
382 if (IS_UNDEFINED(separator)) {
384 } else if (!IS_STRING(separator)) {
385 separator = NonStringToString(separator);
388 var result = %_FastAsciiArrayJoin(this, separator);
389 if (!IS_UNDEFINED(result)) return result;
391 return Join(this, length, separator, ConvertToString);
395 function ObservedArrayPop(n) {
400 BeginPerformSplice(this);
404 EndPerformSplice(this);
405 EnqueueSpliceRecord(this, n, [value], 0);
411 // Removes the last element from the array and returns it. See
412 // ECMA-262, section 15.4.4.6.
413 function ArrayPop() {
414 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
416 var n = TO_UINT32(this.length);
422 if ($Object.isSealed(this)) {
423 throw MakeTypeError("array_functions_change_sealed",
424 ["Array.prototype.pop"]);
427 if (%IsObserved(this))
428 return ObservedArrayPop.call(this, n);
432 Delete(this, ToName(n), true);
438 function ObservedArrayPush() {
439 var n = TO_UINT32(this.length);
440 var m = %_ArgumentsLength();
443 BeginPerformSplice(this);
444 for (var i = 0; i < m; i++) {
445 this[i+n] = %_Arguments(i);
449 EndPerformSplice(this);
450 EnqueueSpliceRecord(this, n, [], m);
456 // Appends the arguments to the end of the array and returns the new
457 // length of the array. See ECMA-262, section 15.4.4.7.
458 function ArrayPush() {
459 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
461 var n = TO_UINT32(this.length);
462 var m = %_ArgumentsLength();
463 if (m > 0 && $Object.isSealed(this)) {
464 throw MakeTypeError("array_functions_change_sealed",
465 ["Array.prototype.push"]);
468 if (%IsObserved(this))
469 return ObservedArrayPush.apply(this, arguments);
471 for (var i = 0; i < m; i++) {
472 this[i+n] = %_Arguments(i);
479 // Returns an array containing the array elements of the object followed
480 // by the array elements of each argument in order. See ECMA-262,
482 function ArrayConcat(arg1) { // length == 1
483 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.concat");
485 var array = ToObject(this);
486 var arg_count = %_ArgumentsLength();
487 var arrays = new InternalArray(1 + arg_count);
489 for (var i = 0; i < arg_count; i++) {
490 arrays[i + 1] = %_Arguments(i);
493 return %ArrayConcat(arrays);
497 // For implementing reverse() on large, sparse arrays.
498 function SparseReverse(array, len) {
499 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
500 var high_counter = keys.length - 1;
502 while (low_counter <= high_counter) {
503 var i = keys[low_counter];
504 var j = keys[high_counter];
506 var j_complement = len - j - 1;
509 if (j_complement <= i) {
511 while (keys[--high_counter] == j) { }
514 if (j_complement >= i) {
516 while (keys[++low_counter] == i) { }
520 var current_i = array[low];
521 if (!IS_UNDEFINED(current_i) || low in array) {
522 var current_j = array[high];
523 if (!IS_UNDEFINED(current_j) || high in array) {
524 array[low] = current_j;
525 array[high] = current_i;
527 array[high] = current_i;
531 var current_j = array[high];
532 if (!IS_UNDEFINED(current_j) || high in array) {
533 array[low] = current_j;
541 function ArrayReverse() {
542 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
544 var j = TO_UINT32(this.length) - 1;
546 if (UseSparseVariant(this, j, IS_ARRAY(this))) {
547 SparseReverse(this, j+1);
551 for (var i = 0; i < j; i++, j--) {
552 var current_i = this[i];
553 if (!IS_UNDEFINED(current_i) || i in this) {
554 var current_j = this[j];
555 if (!IS_UNDEFINED(current_j) || j in this) {
563 var current_j = this[j];
564 if (!IS_UNDEFINED(current_j) || j in this) {
574 function ObservedArrayShift(len) {
578 BeginPerformSplice(this);
579 SimpleMove(this, 0, 1, len, 0);
580 this.length = len - 1;
582 EndPerformSplice(this);
583 EnqueueSpliceRecord(this, 0, [first], 0);
589 function ArrayShift() {
590 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
592 var len = TO_UINT32(this.length);
599 if ($Object.isSealed(this)) {
600 throw MakeTypeError("array_functions_change_sealed",
601 ["Array.prototype.shift"]);
604 if (%IsObserved(this))
605 return ObservedArrayShift.call(this, len);
609 if (IS_ARRAY(this)) {
610 SmartMove(this, 0, 1, len, 0);
612 SimpleMove(this, 0, 1, len, 0);
615 this.length = len - 1;
620 function ObservedArrayUnshift() {
621 var len = TO_UINT32(this.length);
622 var num_arguments = %_ArgumentsLength();
625 BeginPerformSplice(this);
626 SimpleMove(this, 0, 0, len, num_arguments);
627 for (var i = 0; i < num_arguments; i++) {
628 this[i] = %_Arguments(i);
630 this.length = len + num_arguments;
632 EndPerformSplice(this);
633 EnqueueSpliceRecord(this, 0, [], num_arguments);
636 return len + num_arguments;
639 function ArrayUnshift(arg1) { // length == 1
640 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
642 var len = TO_UINT32(this.length);
643 var num_arguments = %_ArgumentsLength();
644 var is_sealed = $Object.isSealed(this);
646 if (num_arguments > 0 && is_sealed) {
647 throw MakeTypeError("array_functions_change_sealed",
648 ["Array.prototype.unshift"]);
651 if (%IsObserved(this))
652 return ObservedArrayUnshift.apply(this, arguments);
654 if (IS_ARRAY(this) && !is_sealed) {
655 SmartMove(this, 0, 0, len, num_arguments);
657 if (num_arguments == 0 && $Object.isFrozen(this)) {
658 // In the zero argument case, values from the prototype come into the
659 // object. This can't be allowed on frozen arrays.
660 for (var i = 0; i < len; i++) {
661 if (!this.hasOwnProperty(i) && !IS_UNDEFINED(this[i])) {
662 throw MakeTypeError("array_functions_on_frozen",
663 ["Array.prototype.shift"]);
668 SimpleMove(this, 0, 0, len, num_arguments);
671 for (var i = 0; i < num_arguments; i++) {
672 this[i] = %_Arguments(i);
675 this.length = len + num_arguments;
681 function ArraySlice(start, end) {
682 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
684 var len = TO_UINT32(this.length);
685 var start_i = TO_INTEGER(start);
688 if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
692 if (start_i < 0) start_i = 0;
694 if (start_i > len) start_i = len;
699 if (end_i < 0) end_i = 0;
701 if (end_i > len) end_i = len;
706 if (end_i < start_i) return result;
708 if (IS_ARRAY(this) &&
709 !%IsObserved(this) &&
711 (%EstimateNumberOfElements(this) < end_i)) {
712 SmartSlice(this, start_i, end_i - start_i, len, result);
714 SimpleSlice(this, start_i, end_i - start_i, len, result);
717 result.length = end_i - start_i;
723 function ComputeSpliceStartIndex(start_i, len) {
726 return start_i < 0 ? 0 : start_i;
729 return start_i > len ? len : start_i;
733 function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
734 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
735 // given as a request to delete all the elements from the start.
736 // And it differs from the case of undefined delete count.
737 // This does not follow ECMA-262, but we do the same for
740 if (num_arguments == 1)
741 return len - start_i;
743 del_count = TO_INTEGER(delete_count);
747 if (del_count > len - start_i)
748 return len - start_i;
754 function ObservedArraySplice(start, delete_count) {
755 var num_arguments = %_ArgumentsLength();
756 var len = TO_UINT32(this.length);
757 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
758 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
760 var deleted_elements = [];
761 deleted_elements.length = del_count;
762 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
765 BeginPerformSplice(this);
767 SimpleSlice(this, start_i, del_count, len, deleted_elements);
768 SimpleMove(this, start_i, del_count, len, num_elements_to_add);
770 // Insert the arguments into the resulting array in
771 // place of the deleted elements.
773 var arguments_index = 2;
774 var arguments_length = %_ArgumentsLength();
775 while (arguments_index < arguments_length) {
776 this[i++] = %_Arguments(arguments_index++);
778 this.length = len - del_count + num_elements_to_add;
781 EndPerformSplice(this);
782 if (deleted_elements.length || num_elements_to_add) {
783 EnqueueSpliceRecord(this,
785 deleted_elements.slice(),
786 num_elements_to_add);
790 // Return the deleted elements.
791 return deleted_elements;
795 function ArraySplice(start, delete_count) {
796 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
798 if (%IsObserved(this))
799 return ObservedArraySplice.apply(this, arguments);
801 var num_arguments = %_ArgumentsLength();
802 var len = TO_UINT32(this.length);
803 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
804 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
806 var deleted_elements = [];
807 deleted_elements.length = del_count;
808 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
810 if (del_count != num_elements_to_add && $Object.isSealed(this)) {
811 throw MakeTypeError("array_functions_change_sealed",
812 ["Array.prototype.splice"]);
813 } else if (del_count > 0 && $Object.isFrozen(this)) {
814 throw MakeTypeError("array_functions_on_frozen",
815 ["Array.prototype.splice"]);
818 var use_simple_splice = true;
819 if (IS_ARRAY(this) &&
820 num_elements_to_add !== del_count) {
821 // If we are only deleting/moving a few things near the end of the
822 // array then the simple version is going to be faster, because it
823 // doesn't touch most of the array.
824 var estimated_non_hole_elements = %EstimateNumberOfElements(this);
825 if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
826 use_simple_splice = false;
830 if (use_simple_splice) {
831 SimpleSlice(this, start_i, del_count, len, deleted_elements);
832 SimpleMove(this, start_i, del_count, len, num_elements_to_add);
834 SmartSlice(this, start_i, del_count, len, deleted_elements);
835 SmartMove(this, start_i, del_count, len, num_elements_to_add);
838 // Insert the arguments into the resulting array in
839 // place of the deleted elements.
841 var arguments_index = 2;
842 var arguments_length = %_ArgumentsLength();
843 while (arguments_index < arguments_length) {
844 this[i++] = %_Arguments(arguments_index++);
846 this.length = len - del_count + num_elements_to_add;
848 // Return the deleted elements.
849 return deleted_elements;
853 function ArraySort(comparefn) {
854 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
856 // In-place QuickSort algorithm.
857 // For short (length <= 22) arrays, insertion sort is used for efficiency.
859 if (!IS_SPEC_FUNCTION(comparefn)) {
860 comparefn = function (x, y) {
861 if (x === y) return 0;
862 if (%_IsSmi(x) && %_IsSmi(y)) {
863 return %SmiLexicographicCompare(x, y);
867 if (x == y) return 0;
868 else return x < y ? -1 : 1;
871 var receiver = %GetDefaultReceiver(comparefn);
873 var InsertionSort = function InsertionSort(a, from, to) {
874 for (var i = from + 1; i < to; i++) {
876 for (var j = i - 1; j >= from; j--) {
878 var order = %_CallFunction(receiver, tmp, element, comparefn);
889 var GetThirdIndex = function(a, from, to) {
891 // Use both 'from' and 'to' to determine the pivot candidates.
892 var increment = 200 + ((to - from) & 15);
893 for (var i = from + 1; i < to - 1; i += increment) {
894 t_array.push([i, a[i]]);
896 t_array.sort(function(a, b) {
897 return %_CallFunction(receiver, a[1], b[1], comparefn) } );
898 var third_index = t_array[t_array.length >> 1][0];
902 var QuickSort = function QuickSort(a, from, to) {
905 // Insertion sort is faster for short arrays.
906 if (to - from <= 10) {
907 InsertionSort(a, from, to);
910 if (to - from > 1000) {
911 third_index = GetThirdIndex(a, from, to);
913 third_index = from + ((to - from) >> 1);
915 // Find a pivot as the median of first, last and middle element.
918 var v2 = a[third_index];
919 var c01 = %_CallFunction(receiver, v0, v1, comparefn);
921 // v1 < v0, so swap them.
926 var c02 = %_CallFunction(receiver, v0, v2, comparefn);
934 // v0 <= v1 && v0 < v2
935 var c12 = %_CallFunction(receiver, v1, v2, comparefn);
947 var low_end = from + 1; // Upper bound of elements lower than pivot.
948 var high_start = to - 1; // Lower bound of elements greater than pivot.
949 a[third_index] = a[low_end];
952 // From low_end to i are elements equal to pivot.
953 // From i to high_start are elements that haven't been compared yet.
954 partition: for (var i = low_end + 1; i < high_start; i++) {
956 var order = %_CallFunction(receiver, element, pivot, comparefn);
959 a[low_end] = element;
961 } else if (order > 0) {
964 if (high_start == i) break partition;
965 var top_elem = a[high_start];
966 order = %_CallFunction(receiver, top_elem, pivot, comparefn);
968 a[i] = a[high_start];
969 a[high_start] = element;
973 a[low_end] = element;
978 if (to - high_start < low_end - from) {
979 QuickSort(a, high_start, to);
982 QuickSort(a, from, low_end);
988 // Copy elements in the range 0..length from obj's prototype chain
989 // to obj itself, if obj has holes. Return one more than the maximal index
990 // of a prototype property.
991 var CopyFromPrototype = function CopyFromPrototype(obj, length) {
993 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
994 var indices = %GetArrayKeys(proto, length);
995 if (IS_NUMBER(indices)) {
997 var proto_length = indices;
998 for (var i = 0; i < proto_length; i++) {
999 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
1001 if (i >= max) { max = i + 1; }
1005 for (var i = 0; i < indices.length; i++) {
1006 var index = indices[i];
1007 if (!IS_UNDEFINED(index) &&
1008 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) {
1009 obj[index] = proto[index];
1010 if (index >= max) { max = index + 1; }
1018 // Set a value of "undefined" on all indices in the range from..to
1019 // where a prototype of obj has an element. I.e., shadow all prototype
1020 // elements in that range.
1021 var ShadowPrototypeElements = function(obj, from, to) {
1022 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
1023 var indices = %GetArrayKeys(proto, to);
1024 if (IS_NUMBER(indices)) {
1025 // It's an interval.
1026 var proto_length = indices;
1027 for (var i = from; i < proto_length; i++) {
1028 if (proto.hasOwnProperty(i)) {
1033 for (var i = 0; i < indices.length; i++) {
1034 var index = indices[i];
1035 if (!IS_UNDEFINED(index) && from <= index &&
1036 proto.hasOwnProperty(index)) {
1037 obj[index] = UNDEFINED;
1044 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1045 // Copy defined elements from the end to fill in all holes and undefineds
1046 // in the beginning of the array. Write undefineds and holes at the end
1047 // after loop is finished.
1048 var first_undefined = 0;
1049 var last_defined = length - 1;
1051 while (first_undefined < last_defined) {
1052 // Find first undefined element.
1053 while (first_undefined < last_defined &&
1054 !IS_UNDEFINED(obj[first_undefined])) {
1057 // Maintain the invariant num_holes = the number of holes in the original
1058 // array with indices <= first_undefined or > last_defined.
1059 if (!obj.hasOwnProperty(first_undefined)) {
1063 // Find last defined element.
1064 while (first_undefined < last_defined &&
1065 IS_UNDEFINED(obj[last_defined])) {
1066 if (!obj.hasOwnProperty(last_defined)) {
1071 if (first_undefined < last_defined) {
1072 // Fill in hole or undefined.
1073 obj[first_undefined] = obj[last_defined];
1074 obj[last_defined] = UNDEFINED;
1077 // If there were any undefineds in the entire array, first_undefined
1078 // points to one past the last defined element. Make this true if
1079 // there were no undefineds, as well, so that first_undefined == number
1080 // of defined elements.
1081 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
1082 // Fill in the undefineds and the holes. There may be a hole where
1083 // an undefined should be and vice versa.
1085 for (i = first_undefined; i < length - num_holes; i++) {
1088 for (i = length - num_holes; i < length; i++) {
1089 // For compatability with Webkit, do not expose elements in the prototype.
1090 if (i in %GetPrototype(obj)) {
1097 // Return the number of defined elements.
1098 return first_undefined;
1101 var length = TO_UINT32(this.length);
1102 if (length < 2) return this;
1104 var is_array = IS_ARRAY(this);
1105 var max_prototype_element;
1107 // For compatibility with JSC, we also sort elements inherited from
1108 // the prototype chain on non-Array objects.
1109 // We do this by copying them to this object and sorting only
1110 // local elements. This is not very efficient, but sorting with
1111 // inherited elements happens very, very rarely, if at all.
1112 // The specification allows "implementation dependent" behavior
1113 // if an element on the prototype chain has an element that
1114 // might interact with sorting.
1115 max_prototype_element = CopyFromPrototype(this, length);
1118 var num_non_undefined = %IsObserved(this) ?
1119 -1 : %RemoveArrayHoles(this, length);
1121 if (num_non_undefined == -1) {
1122 // The array is observed, or there were indexed accessors in the array.
1123 // Move array holes and undefineds to the end using a Javascript function
1124 // that is safe in the presence of accessors and is observable.
1125 num_non_undefined = SafeRemoveArrayHoles(this);
1128 QuickSort(this, 0, num_non_undefined);
1130 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
1131 // For compatibility with JSC, we shadow any elements in the prototype
1132 // chain that has become exposed by sort moving a hole to its position.
1133 ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
1140 // The following functions cannot be made efficient on sparse arrays while
1141 // preserving the semantics, since the calls to the receiver function can add
1142 // or delete elements from the array.
1143 function ArrayFilter(f, receiver) {
1144 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");
1146 // Pull out the length so that modifications to the length in the
1147 // loop will not affect the looping and side effects are visible.
1148 var array = ToObject(this);
1149 var length = ToUint32(array.length);
1151 if (!IS_SPEC_FUNCTION(f)) {
1152 throw MakeTypeError('called_non_callable', [ f ]);
1154 if (IS_NULL_OR_UNDEFINED(receiver)) {
1155 receiver = %GetDefaultReceiver(f) || receiver;
1156 } else if (!IS_SPEC_OBJECT(receiver) && %IsClassicModeFunction(f)) {
1157 receiver = ToObject(receiver);
1160 var result = new $Array();
1161 var accumulator = new InternalArray();
1162 var accumulator_length = 0;
1163 if (%DebugCallbackSupportsStepping(f)) {
1164 for (var i = 0; i < length; i++) {
1166 var element = array[i];
1167 // Prepare break slots for debugger step in.
1168 %DebugPrepareStepInIfStepping(f);
1169 if (%_CallFunction(receiver, element, i, array, f)) {
1170 accumulator[accumulator_length++] = element;
1175 // This is a duplicate of the previous loop sans debug stepping.
1176 for (var i = 0; i < length; i++) {
1178 var element = array[i];
1179 if (%_CallFunction(receiver, element, i, array, f)) {
1180 accumulator[accumulator_length++] = element;
1184 // End of duplicate.
1186 %MoveArrayContents(accumulator, result);
1191 function ArrayForEach(f, receiver) {
1192 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");
1194 // Pull out the length so that modifications to the length in the
1195 // loop will not affect the looping and side effects are visible.
1196 var array = ToObject(this);
1197 var length = TO_UINT32(array.length);
1199 if (!IS_SPEC_FUNCTION(f)) {
1200 throw MakeTypeError('called_non_callable', [ f ]);
1202 if (IS_NULL_OR_UNDEFINED(receiver)) {
1203 receiver = %GetDefaultReceiver(f) || receiver;
1204 } else if (!IS_SPEC_OBJECT(receiver) && %IsClassicModeFunction(f)) {
1205 receiver = ToObject(receiver);
1208 if (%DebugCallbackSupportsStepping(f)) {
1209 for (var i = 0; i < length; i++) {
1211 var element = array[i];
1212 // Prepare break slots for debugger step in.
1213 %DebugPrepareStepInIfStepping(f);
1214 %_CallFunction(receiver, element, i, array, f);
1218 // This is a duplicate of the previous loop sans debug stepping.
1219 for (var i = 0; i < length; i++) {
1221 var element = array[i];
1222 %_CallFunction(receiver, element, i, array, f);
1225 // End of duplicate.
1230 // Executes the function once for each element present in the
1231 // array until it finds one where callback returns true.
1232 function ArraySome(f, receiver) {
1233 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");
1235 // Pull out the length so that modifications to the length in the
1236 // loop will not affect the looping and side effects are visible.
1237 var array = ToObject(this);
1238 var length = TO_UINT32(array.length);
1240 if (!IS_SPEC_FUNCTION(f)) {
1241 throw MakeTypeError('called_non_callable', [ f ]);
1243 if (IS_NULL_OR_UNDEFINED(receiver)) {
1244 receiver = %GetDefaultReceiver(f) || receiver;
1245 } else if (!IS_SPEC_OBJECT(receiver) && %IsClassicModeFunction(f)) {
1246 receiver = ToObject(receiver);
1249 if (%DebugCallbackSupportsStepping(f)) {
1250 for (var i = 0; i < length; i++) {
1252 var element = array[i];
1253 // Prepare break slots for debugger step in.
1254 %DebugPrepareStepInIfStepping(f);
1255 if (%_CallFunction(receiver, element, i, array, f)) return true;
1259 // This is a duplicate of the previous loop sans debug stepping.
1260 for (var i = 0; i < length; i++) {
1262 var element = array[i];
1263 if (%_CallFunction(receiver, element, i, array, f)) return true;
1266 // End of duplicate.
1272 function ArrayEvery(f, receiver) {
1273 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");
1275 // Pull out the length so that modifications to the length in the
1276 // loop will not affect the looping and side effects are visible.
1277 var array = ToObject(this);
1278 var length = TO_UINT32(array.length);
1280 if (!IS_SPEC_FUNCTION(f)) {
1281 throw MakeTypeError('called_non_callable', [ f ]);
1283 if (IS_NULL_OR_UNDEFINED(receiver)) {
1284 receiver = %GetDefaultReceiver(f) || receiver;
1285 } else if (!IS_SPEC_OBJECT(receiver) && %IsClassicModeFunction(f)) {
1286 receiver = ToObject(receiver);
1289 if (%DebugCallbackSupportsStepping(f)) {
1290 for (var i = 0; i < length; i++) {
1292 var element = array[i];
1293 // Prepare break slots for debugger step in.
1294 %DebugPrepareStepInIfStepping(f);
1295 if (!%_CallFunction(receiver, element, i, array, f)) return false;
1299 // This is a duplicate of the previous loop sans debug stepping.
1300 for (var i = 0; i < length; i++) {
1302 var element = array[i];
1303 if (!%_CallFunction(receiver, element, i, array, f)) return false;
1306 // End of duplicate.
1311 function ArrayMap(f, receiver) {
1312 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map");
1314 // Pull out the length so that modifications to the length in the
1315 // loop will not affect the looping and side effects are visible.
1316 var array = ToObject(this);
1317 var length = TO_UINT32(array.length);
1319 if (!IS_SPEC_FUNCTION(f)) {
1320 throw MakeTypeError('called_non_callable', [ f ]);
1322 if (IS_NULL_OR_UNDEFINED(receiver)) {
1323 receiver = %GetDefaultReceiver(f) || receiver;
1324 } else if (!IS_SPEC_OBJECT(receiver) && %IsClassicModeFunction(f)) {
1325 receiver = ToObject(receiver);
1328 var result = new $Array();
1329 var accumulator = new InternalArray(length);
1330 if (%DebugCallbackSupportsStepping(f)) {
1331 for (var i = 0; i < length; i++) {
1333 var element = array[i];
1334 // Prepare break slots for debugger step in.
1335 %DebugPrepareStepInIfStepping(f);
1336 accumulator[i] = %_CallFunction(receiver, element, i, array, f);
1340 // This is a duplicate of the previous loop sans debug stepping.
1341 for (var i = 0; i < length; i++) {
1343 var element = array[i];
1344 accumulator[i] = %_CallFunction(receiver, element, i, array, f);
1347 // End of duplicate.
1349 %MoveArrayContents(accumulator, result);
1354 function ArrayIndexOf(element, index) {
1355 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1357 var length = TO_UINT32(this.length);
1358 if (length == 0) return -1;
1359 if (IS_UNDEFINED(index)) {
1362 index = TO_INTEGER(index);
1363 // If index is negative, index from the end of the array.
1365 index = length + index;
1366 // If index is still negative, search the entire array.
1367 if (index < 0) index = 0;
1372 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1373 var indices = %GetArrayKeys(this, length);
1374 if (IS_NUMBER(indices)) {
1375 // It's an interval.
1376 max = indices; // Capped by length already.
1377 // Fall through to loop below.
1379 if (indices.length == 0) return -1;
1380 // Get all the keys in sorted order.
1381 var sortedKeys = GetSortedArrayKeys(this, indices);
1382 var n = sortedKeys.length;
1384 while (i < n && sortedKeys[i] < index) i++;
1386 var key = sortedKeys[i];
1387 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1393 // Lookup through the array.
1394 if (!IS_UNDEFINED(element)) {
1395 for (var i = min; i < max; i++) {
1396 if (this[i] === element) return i;
1400 // Lookup through the array.
1401 for (var i = min; i < max; i++) {
1402 if (IS_UNDEFINED(this[i]) && i in this) {
1410 function ArrayLastIndexOf(element, index) {
1411 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1413 var length = TO_UINT32(this.length);
1414 if (length == 0) return -1;
1415 if (%_ArgumentsLength() < 2) {
1418 index = TO_INTEGER(index);
1419 // If index is negative, index from end of the array.
1420 if (index < 0) index += length;
1421 // If index is still negative, do not search the array.
1422 if (index < 0) return -1;
1423 else if (index >= length) index = length - 1;
1427 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1428 var indices = %GetArrayKeys(this, index + 1);
1429 if (IS_NUMBER(indices)) {
1430 // It's an interval.
1431 max = indices; // Capped by index already.
1432 // Fall through to loop below.
1434 if (indices.length == 0) return -1;
1435 // Get all the keys in sorted order.
1436 var sortedKeys = GetSortedArrayKeys(this, indices);
1437 var i = sortedKeys.length - 1;
1439 var key = sortedKeys[i];
1440 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1446 // Lookup through the array.
1447 if (!IS_UNDEFINED(element)) {
1448 for (var i = max; i >= min; i--) {
1449 if (this[i] === element) return i;
1453 for (var i = max; i >= min; i--) {
1454 if (IS_UNDEFINED(this[i]) && i in this) {
1462 function ArrayReduce(callback, current) {
1463 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1465 // Pull out the length so that modifications to the length in the
1466 // loop will not affect the looping and side effects are visible.
1467 var array = ToObject(this);
1468 var length = ToUint32(array.length);
1470 if (!IS_SPEC_FUNCTION(callback)) {
1471 throw MakeTypeError('called_non_callable', [callback]);
1475 find_initial: if (%_ArgumentsLength() < 2) {
1476 for (; i < length; i++) {
1478 if (!IS_UNDEFINED(current) || i in array) {
1483 throw MakeTypeError('reduce_no_initial', []);
1486 var receiver = %GetDefaultReceiver(callback);
1488 if (%DebugCallbackSupportsStepping(callback)) {
1489 for (; i < length; i++) {
1491 var element = array[i];
1492 // Prepare break slots for debugger step in.
1493 %DebugPrepareStepInIfStepping(callback);
1495 %_CallFunction(receiver, current, element, i, array, callback);
1499 // This is a duplicate of the previous loop sans debug stepping.
1500 for (; i < length; i++) {
1502 var element = array[i];
1504 %_CallFunction(receiver, current, element, i, array, callback);
1507 // End of duplicate.
1512 function ArrayReduceRight(callback, current) {
1513 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight");
1515 // Pull out the length so that side effects are visible before the
1516 // callback function is checked.
1517 var array = ToObject(this);
1518 var length = ToUint32(array.length);
1520 if (!IS_SPEC_FUNCTION(callback)) {
1521 throw MakeTypeError('called_non_callable', [callback]);
1525 find_initial: if (%_ArgumentsLength() < 2) {
1526 for (; i >= 0; i--) {
1528 if (!IS_UNDEFINED(current) || i in array) {
1533 throw MakeTypeError('reduce_no_initial', []);
1536 var receiver = %GetDefaultReceiver(callback);
1538 if (%DebugCallbackSupportsStepping(callback)) {
1539 for (; i >= 0; i--) {
1541 var element = array[i];
1542 // Prepare break slots for debugger step in.
1543 %DebugPrepareStepInIfStepping(callback);
1545 %_CallFunction(receiver, current, element, i, array, callback);
1549 // This is a duplicate of the previous loop sans debug stepping.
1550 for (; i >= 0; i--) {
1552 var element = array[i];
1554 %_CallFunction(receiver, current, element, i, array, callback);
1557 // End of duplicate.
1563 function ArrayIsArray(obj) {
1564 return IS_ARRAY(obj);
1568 // -------------------------------------------------------------------
1570 function SetUpArray() {
1571 %CheckIsBootstrapping();
1573 // Set up non-enumerable constructor property on the Array.prototype
1575 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
1577 // Set up non-enumerable functions on the Array object.
1578 InstallFunctions($Array, DONT_ENUM, $Array(
1579 "isArray", ArrayIsArray
1582 var specialFunctions = %SpecialArrayFunctions({});
1584 var getFunction = function(name, jsBuiltin, len) {
1586 if (specialFunctions.hasOwnProperty(name)) {
1587 f = specialFunctions[name];
1589 if (!IS_UNDEFINED(len)) {
1590 %FunctionSetLength(f, len);
1595 // Set up non-enumerable functions of the Array.prototype object and
1597 // Manipulate the length of some of the functions to meet
1598 // expectations set by ECMA-262 or Mozilla.
1599 InstallFunctions($Array.prototype, DONT_ENUM, $Array(
1600 "toString", getFunction("toString", ArrayToString),
1601 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
1602 "join", getFunction("join", ArrayJoin),
1603 "pop", getFunction("pop", ArrayPop),
1604 "push", getFunction("push", ArrayPush, 1),
1605 "concat", getFunction("concat", ArrayConcat, 1),
1606 "reverse", getFunction("reverse", ArrayReverse),
1607 "shift", getFunction("shift", ArrayShift),
1608 "unshift", getFunction("unshift", ArrayUnshift, 1),
1609 "slice", getFunction("slice", ArraySlice, 2),
1610 "splice", getFunction("splice", ArraySplice, 2),
1611 "sort", getFunction("sort", ArraySort),
1612 "filter", getFunction("filter", ArrayFilter, 1),
1613 "forEach", getFunction("forEach", ArrayForEach, 1),
1614 "some", getFunction("some", ArraySome, 1),
1615 "every", getFunction("every", ArrayEvery, 1),
1616 "map", getFunction("map", ArrayMap, 1),
1617 "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
1618 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1619 "reduce", getFunction("reduce", ArrayReduce, 1),
1620 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1623 %FinishArrayPrototypeSetup($Array.prototype);
1625 // The internal Array prototype doesn't need to be fancy, since it's never
1626 // exposed to user code.
1627 // Adding only the functions that are actually used.
1628 SetUpLockedPrototype(InternalArray, $Array(), $Array(
1629 "concat", getFunction("concat", ArrayConcat),
1630 "indexOf", getFunction("indexOf", ArrayIndexOf),
1631 "join", getFunction("join", ArrayJoin),
1632 "pop", getFunction("pop", ArrayPop),
1633 "push", getFunction("push", ArrayPush),
1634 "splice", getFunction("splice", ArraySplice)
1637 SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
1638 "join", getFunction("join", ArrayJoin),
1639 "pop", getFunction("pop", ArrayPop),
1640 "push", getFunction("push", ArrayPush)