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, intervals) {
42 var length = intervals.length;
44 for (var k = 0; k < length; k++) {
45 var key = intervals[k];
48 var limit = j + intervals[++k];
49 for (; j < limit; j++) {
51 if (!IS_UNDEFINED(e) || j in array) {
56 // The case where key is undefined also ends here.
57 if (!IS_UNDEFINED(key)) {
59 if (!IS_UNDEFINED(e) || key in array) {
65 keys.sort(function(a, b) { return a - b; });
70 function SparseJoinWithSeparator(array, len, convert, separator) {
71 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
73 var elements = new InternalArray(keys.length * 2);
75 for (var i = 0; i < keys.length; i++) {
77 if (key != previousKey) { // keys may contain duplicates.
79 if (!IS_STRING(e)) e = convert(e);
80 elements[i * 2] = key;
81 elements[i * 2 + 1] = e;
85 return %SparseJoinWithSeparator(elements, len, separator);
89 // Optimized for sparse arrays if separator is ''.
90 function SparseJoin(array, len, convert) {
91 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
93 var keys_length = keys.length;
95 var elements = new InternalArray(keys_length);
96 var elements_length = 0;
98 for (var i = 0; i < keys_length; i++) {
100 if (key != last_key) {
102 if (!IS_STRING(e)) e = convert(e);
103 elements[elements_length++] = e;
107 return %StringBuilderConcat(elements, elements_length, '');
111 function UseSparseVariant(object, length, is_array) {
115 %EstimateNumberOfElements(object) < (length >> 2));
119 function Join(array, length, separator, convert) {
120 if (length == 0) return '';
122 var is_array = IS_ARRAY(array);
125 // If the array is cyclic, return the empty string for already
127 if (!%PushIfAbsent(visited_arrays, array)) return '';
130 // Attempt to convert the elements.
132 if (UseSparseVariant(array, length, is_array)) {
133 if (separator.length == 0) {
134 return SparseJoin(array, length, convert);
136 return SparseJoinWithSeparator(array, length, convert, separator);
140 // Fast case for one-element arrays.
143 if (IS_STRING(e)) return e;
147 // Construct an array for the elements.
148 var elements = new InternalArray(length);
150 // We pull the empty separator check outside the loop for speed!
151 if (separator.length == 0) {
152 var elements_length = 0;
153 for (var i = 0; i < length; i++) {
155 if (!IS_STRING(e)) e = convert(e);
156 elements[elements_length++] = e;
158 elements.length = elements_length;
159 var result = %_FastAsciiArrayJoin(elements, '');
160 if (!IS_UNDEFINED(result)) return result;
161 return %StringBuilderConcat(elements, elements_length, '');
163 // Non-empty separator case.
164 // If the first element is a number then use the heuristic that the
165 // remaining elements are also likely to be numbers.
166 if (!IS_NUMBER(array[0])) {
167 for (var i = 0; i < length; i++) {
169 if (!IS_STRING(e)) e = convert(e);
173 for (var i = 0; i < length; i++) {
176 e = %_NumberToString(e);
177 } else if (!IS_STRING(e)) {
183 var result = %_FastAsciiArrayJoin(elements, separator);
184 if (!IS_UNDEFINED(result)) return result;
186 return %StringBuilderJoin(elements, length, separator);
188 // Make sure to remove the last element of the visited array no
189 // matter what happens.
190 if (is_array) visited_arrays.length = visited_arrays.length - 1;
195 function ConvertToString(x) {
196 // Assumes x is a non-string.
197 if (IS_NUMBER(x)) return %_NumberToString(x);
198 if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
199 return (IS_NULL_OR_UNDEFINED(x)) ? '' : %ToString(%DefaultString(x));
203 function ConvertToLocaleString(e) {
204 if (IS_NULL_OR_UNDEFINED(e)) {
207 // According to ES5, section 15.4.4.3, the toLocaleString conversion
208 // must throw a TypeError if ToObject(e).toLocaleString isn't
210 var e_obj = ToObject(e);
211 return %ToString(e_obj.toLocaleString());
216 // This function implements the optimized splice implementation that can use
217 // special array operations to handle sparse arrays in a sensible fashion.
218 function SmartSlice(array, start_i, del_count, len, deleted_elements) {
219 // Move deleted elements to a new array (the return value from splice).
220 // Intervals array can contain keys and intervals. See comment in Concat.
221 var intervals = %GetArrayKeys(array, start_i + del_count);
222 var length = intervals.length;
223 for (var k = 0; k < length; k++) {
224 var key = intervals[k];
227 var interval_limit = j + intervals[++k];
231 for (; j < interval_limit; j++) {
232 // ECMA-262 15.4.4.12 line 10. The spec could also be
233 // interpreted such that %HasLocalProperty would be the
234 // appropriate test. We follow KJS in consulting the
236 var current = array[j];
237 if (!IS_UNDEFINED(current) || j in array) {
238 deleted_elements[j - start_i] = current;
242 if (!IS_UNDEFINED(key)) {
243 if (key >= start_i) {
244 // ECMA-262 15.4.4.12 line 10. The spec could also be
245 // interpreted such that %HasLocalProperty would be the
246 // appropriate test. We follow KJS in consulting the
248 var current = array[key];
249 if (!IS_UNDEFINED(current) || key in array) {
250 deleted_elements[key - start_i] = current;
259 // This function implements the optimized splice implementation that can use
260 // special array operations to handle sparse arrays in a sensible fashion.
261 function SmartMove(array, start_i, del_count, len, num_additional_args) {
262 // Move data to new array.
263 var new_array = new InternalArray(len - del_count + num_additional_args);
264 var intervals = %GetArrayKeys(array, len);
265 var length = intervals.length;
266 for (var k = 0; k < length; k++) {
267 var key = intervals[k];
270 var interval_limit = j + intervals[++k];
271 while (j < start_i && j < interval_limit) {
272 // The spec could also be interpreted such that
273 // %HasLocalProperty would be the appropriate test. We follow
274 // KJS in consulting the prototype.
275 var current = array[j];
276 if (!IS_UNDEFINED(current) || j in array) {
277 new_array[j] = current;
281 j = start_i + del_count;
282 while (j < interval_limit) {
283 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also be
284 // interpreted such that %HasLocalProperty would be the
285 // appropriate test. We follow KJS in consulting the
287 var current = array[j];
288 if (!IS_UNDEFINED(current) || j in array) {
289 new_array[j - del_count + num_additional_args] = current;
294 if (!IS_UNDEFINED(key)) {
296 // The spec could also be interpreted such that
297 // %HasLocalProperty would be the appropriate test. We follow
298 // KJS in consulting the prototype.
299 var current = array[key];
300 if (!IS_UNDEFINED(current) || key in array) {
301 new_array[key] = current;
303 } else if (key >= start_i + del_count) {
304 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also
305 // be interpreted such that %HasLocalProperty would be the
306 // appropriate test. We follow KJS in consulting the
308 var current = array[key];
309 if (!IS_UNDEFINED(current) || key in array) {
310 new_array[key - del_count + num_additional_args] = current;
316 // Move contents of new_array into this array
317 %MoveArrayContents(new_array, array);
321 // This is part of the old simple-minded splice. We are using it either
322 // because the receiver is not an array (so we have no choice) or because we
323 // know we are not deleting or moving a lot of elements.
324 function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
325 for (var i = 0; i < del_count; i++) {
326 var index = start_i + i;
327 // The spec could also be interpreted such that %HasLocalProperty
328 // would be the appropriate test. We follow KJS in consulting the
330 var current = array[index];
331 if (!IS_UNDEFINED(current) || index in array) {
332 deleted_elements[i] = current;
338 function SimpleMove(array, start_i, del_count, len, num_additional_args) {
339 if (num_additional_args !== del_count) {
340 // Move the existing elements after the elements to be deleted
341 // to the right position in the resulting array.
342 if (num_additional_args > del_count) {
343 for (var i = len - del_count; i > start_i; i--) {
344 var from_index = i + del_count - 1;
345 var to_index = i + num_additional_args - 1;
346 // The spec could also be interpreted such that
347 // %HasLocalProperty would be the appropriate test. We follow
348 // KJS in consulting the prototype.
349 var current = array[from_index];
350 if (!IS_UNDEFINED(current) || from_index in array) {
351 array[to_index] = current;
353 delete array[to_index];
357 for (var i = start_i; i < len - del_count; i++) {
358 var from_index = i + del_count;
359 var to_index = i + num_additional_args;
360 // The spec could also be interpreted such that
361 // %HasLocalProperty would be the appropriate test. We follow
362 // KJS in consulting the prototype.
363 var current = array[from_index];
364 if (!IS_UNDEFINED(current) || from_index in array) {
365 array[to_index] = current;
367 delete array[to_index];
370 for (var i = len; i > len - del_count + num_additional_args; i--) {
378 // -------------------------------------------------------------------
381 function ArrayToString() {
384 if (IS_ARRAY(this)) {
386 if (func === ArrayJoin) {
387 return Join(this, this.length, ',', ConvertToString);
391 array = ToObject(this);
394 if (!IS_SPEC_FUNCTION(func)) {
395 return %_CallFunction(array, ObjectToString);
397 return %_CallFunction(array, func);
401 function ArrayToLocaleString() {
402 var array = ToObject(this);
403 var arrayLen = array.length;
404 var len = TO_UINT32(arrayLen);
405 if (len === 0) return "";
406 return Join(array, len, ',', ConvertToLocaleString);
410 function ArrayJoin(separator) {
411 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
412 throw MakeTypeError("called_on_null_or_undefined",
413 ["Array.prototype.join"]);
416 if (IS_UNDEFINED(separator)) {
418 } else if (!IS_STRING(separator)) {
419 separator = NonStringToString(separator);
422 var result = %_FastAsciiArrayJoin(this, separator);
423 if (!IS_UNDEFINED(result)) return result;
425 return Join(this, TO_UINT32(this.length), separator, ConvertToString);
429 // Removes the last element from the array and returns it. See
430 // ECMA-262, section 15.4.4.6.
431 function ArrayPop() {
432 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
433 throw MakeTypeError("called_on_null_or_undefined",
434 ["Array.prototype.pop"]);
437 var n = TO_UINT32(this.length);
450 // Appends the arguments to the end of the array and returns the new
451 // length of the array. See ECMA-262, section 15.4.4.7.
452 function ArrayPush() {
453 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
454 throw MakeTypeError("called_on_null_or_undefined",
455 ["Array.prototype.push"]);
458 var n = TO_UINT32(this.length);
459 var m = %_ArgumentsLength();
460 for (var i = 0; i < m; i++) {
461 this[i+n] = %_Arguments(i);
468 // Returns an array containing the array elements of the object followed
469 // by the array elements of each argument in order. See ECMA-262,
471 function ArrayConcat(arg1) { // length == 1
472 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
473 throw MakeTypeError("called_on_null_or_undefined",
474 ["Array.prototype.concat"]);
477 var array = ToObject(this);
478 var arg_count = %_ArgumentsLength();
479 var arrays = new InternalArray(1 + arg_count);
481 for (var i = 0; i < arg_count; i++) {
482 arrays[i + 1] = %_Arguments(i);
485 return %ArrayConcat(arrays);
489 // For implementing reverse() on large, sparse arrays.
490 function SparseReverse(array, len) {
491 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
492 var high_counter = keys.length - 1;
494 while (low_counter <= high_counter) {
495 var i = keys[low_counter];
496 var j = keys[high_counter];
498 var j_complement = len - j - 1;
501 if (j_complement <= i) {
503 while (keys[--high_counter] == j) { }
506 if (j_complement >= i) {
508 while (keys[++low_counter] == i) { }
512 var current_i = array[low];
513 if (!IS_UNDEFINED(current_i) || low in array) {
514 var current_j = array[high];
515 if (!IS_UNDEFINED(current_j) || high in array) {
516 array[low] = current_j;
517 array[high] = current_i;
519 array[high] = current_i;
523 var current_j = array[high];
524 if (!IS_UNDEFINED(current_j) || high in array) {
525 array[low] = current_j;
533 function ArrayReverse() {
534 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
535 throw MakeTypeError("called_on_null_or_undefined",
536 ["Array.prototype.reverse"]);
539 var j = TO_UINT32(this.length) - 1;
541 if (UseSparseVariant(this, j, IS_ARRAY(this))) {
542 SparseReverse(this, j+1);
546 for (var i = 0; i < j; i++, j--) {
547 var current_i = this[i];
548 if (!IS_UNDEFINED(current_i) || i in this) {
549 var current_j = this[j];
550 if (!IS_UNDEFINED(current_j) || j in this) {
558 var current_j = this[j];
559 if (!IS_UNDEFINED(current_j) || j in this) {
569 function ArrayShift() {
570 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
571 throw MakeTypeError("called_on_null_or_undefined",
572 ["Array.prototype.shift"]);
575 var len = TO_UINT32(this.length);
584 if (IS_ARRAY(this)) {
585 SmartMove(this, 0, 1, len, 0);
587 SimpleMove(this, 0, 1, len, 0);
590 this.length = len - 1;
596 function ArrayUnshift(arg1) { // length == 1
597 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
598 throw MakeTypeError("called_on_null_or_undefined",
599 ["Array.prototype.unshift"]);
602 var len = TO_UINT32(this.length);
603 var num_arguments = %_ArgumentsLength();
605 if (IS_ARRAY(this)) {
606 SmartMove(this, 0, 0, len, num_arguments);
608 SimpleMove(this, 0, 0, len, num_arguments);
611 for (var i = 0; i < num_arguments; i++) {
612 this[i] = %_Arguments(i);
615 this.length = len + num_arguments;
617 return len + num_arguments;
621 function ArraySlice(start, end) {
622 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
623 throw MakeTypeError("called_on_null_or_undefined",
624 ["Array.prototype.slice"]);
627 var len = TO_UINT32(this.length);
628 var start_i = TO_INTEGER(start);
631 if (end !== void 0) end_i = TO_INTEGER(end);
635 if (start_i < 0) start_i = 0;
637 if (start_i > len) start_i = len;
642 if (end_i < 0) end_i = 0;
644 if (end_i > len) end_i = len;
649 if (end_i < start_i) return result;
651 if (IS_ARRAY(this) &&
653 (%EstimateNumberOfElements(this) < end_i)) {
654 SmartSlice(this, start_i, end_i - start_i, len, result);
656 SimpleSlice(this, start_i, end_i - start_i, len, result);
659 result.length = end_i - start_i;
665 function ArraySplice(start, delete_count) {
666 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
667 throw MakeTypeError("called_on_null_or_undefined",
668 ["Array.prototype.splice"]);
671 var num_arguments = %_ArgumentsLength();
673 var len = TO_UINT32(this.length);
674 var start_i = TO_INTEGER(start);
678 if (start_i < 0) start_i = 0;
680 if (start_i > len) start_i = len;
683 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
684 // given as a request to delete all the elements from the start.
685 // And it differs from the case of undefined delete count.
686 // This does not follow ECMA-262, but we do the same for
689 if (num_arguments == 1) {
690 del_count = len - start_i;
692 del_count = TO_INTEGER(delete_count);
693 if (del_count < 0) del_count = 0;
694 if (del_count > len - start_i) del_count = len - start_i;
697 var deleted_elements = [];
698 deleted_elements.length = del_count;
700 // Number of elements to add.
701 var num_additional_args = 0;
702 if (num_arguments > 2) {
703 num_additional_args = num_arguments - 2;
706 var use_simple_splice = true;
708 if (IS_ARRAY(this) && num_additional_args !== del_count) {
709 // If we are only deleting/moving a few things near the end of the
710 // array then the simple version is going to be faster, because it
711 // doesn't touch most of the array.
712 var estimated_non_hole_elements = %EstimateNumberOfElements(this);
713 if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
714 use_simple_splice = false;
718 if (use_simple_splice) {
719 SimpleSlice(this, start_i, del_count, len, deleted_elements);
720 SimpleMove(this, start_i, del_count, len, num_additional_args);
722 SmartSlice(this, start_i, del_count, len, deleted_elements);
723 SmartMove(this, start_i, del_count, len, num_additional_args);
726 // Insert the arguments into the resulting array in
727 // place of the deleted elements.
729 var arguments_index = 2;
730 var arguments_length = %_ArgumentsLength();
731 while (arguments_index < arguments_length) {
732 this[i++] = %_Arguments(arguments_index++);
734 this.length = len - del_count + num_additional_args;
736 // Return the deleted elements.
737 return deleted_elements;
741 function ArraySort(comparefn) {
742 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
743 throw MakeTypeError("called_on_null_or_undefined",
744 ["Array.prototype.sort"]);
747 // In-place QuickSort algorithm.
748 // For short (length <= 22) arrays, insertion sort is used for efficiency.
750 if (!IS_SPEC_FUNCTION(comparefn)) {
751 comparefn = function (x, y) {
752 if (x === y) return 0;
753 if (%_IsSmi(x) && %_IsSmi(y)) {
754 return %SmiLexicographicCompare(x, y);
758 if (x == y) return 0;
759 else return x < y ? -1 : 1;
762 var receiver = %GetDefaultReceiver(comparefn);
764 var InsertionSort = function InsertionSort(a, from, to) {
765 for (var i = from + 1; i < to; i++) {
767 for (var j = i - 1; j >= from; j--) {
769 var order = %_CallFunction(receiver, tmp, element, comparefn);
780 var QuickSort = function QuickSort(a, from, to) {
781 // Insertion sort is faster for short arrays.
782 if (to - from <= 10) {
783 InsertionSort(a, from, to);
786 // Find a pivot as the median of first, last and middle element.
789 var middle_index = from + ((to - from) >> 1);
790 var v2 = a[middle_index];
791 var c01 = %_CallFunction(receiver, v0, v1, comparefn);
793 // v1 < v0, so swap them.
798 var c02 = %_CallFunction(receiver, v0, v2, comparefn);
806 // v0 <= v1 && v0 < v2
807 var c12 = %_CallFunction(receiver, v1, v2, comparefn);
819 var low_end = from + 1; // Upper bound of elements lower than pivot.
820 var high_start = to - 1; // Lower bound of elements greater than pivot.
821 a[middle_index] = a[low_end];
824 // From low_end to i are elements equal to pivot.
825 // From i to high_start are elements that haven't been compared yet.
826 partition: for (var i = low_end + 1; i < high_start; i++) {
828 var order = %_CallFunction(receiver, element, pivot, comparefn);
831 a[low_end] = element;
833 } else if (order > 0) {
836 if (high_start == i) break partition;
837 var top_elem = a[high_start];
838 order = %_CallFunction(receiver, top_elem, pivot, comparefn);
840 a[i] = a[high_start];
841 a[high_start] = element;
845 a[low_end] = element;
850 QuickSort(a, from, low_end);
851 QuickSort(a, high_start, to);
854 // Copy elements in the range 0..length from obj's prototype chain
855 // to obj itself, if obj has holes. Return one more than the maximal index
856 // of a prototype property.
857 var CopyFromPrototype = function CopyFromPrototype(obj, length) {
859 for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
860 var indices = %GetArrayKeys(proto, length);
861 if (indices.length > 0) {
862 if (indices[0] == -1) {
864 var proto_length = indices[1];
865 for (var i = 0; i < proto_length; i++) {
866 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
868 if (i >= max) { max = i + 1; }
872 for (var i = 0; i < indices.length; i++) {
873 var index = indices[i];
874 if (!IS_UNDEFINED(index) &&
875 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) {
876 obj[index] = proto[index];
877 if (index >= max) { max = index + 1; }
886 // Set a value of "undefined" on all indices in the range from..to
887 // where a prototype of obj has an element. I.e., shadow all prototype
888 // elements in that range.
889 var ShadowPrototypeElements = function(obj, from, to) {
890 for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
891 var indices = %GetArrayKeys(proto, to);
892 if (indices.length > 0) {
893 if (indices[0] == -1) {
895 var proto_length = indices[1];
896 for (var i = from; i < proto_length; i++) {
897 if (proto.hasOwnProperty(i)) {
902 for (var i = 0; i < indices.length; i++) {
903 var index = indices[i];
904 if (!IS_UNDEFINED(index) && from <= index &&
905 proto.hasOwnProperty(index)) {
914 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
915 // Copy defined elements from the end to fill in all holes and undefineds
916 // in the beginning of the array. Write undefineds and holes at the end
917 // after loop is finished.
918 var first_undefined = 0;
919 var last_defined = length - 1;
921 while (first_undefined < last_defined) {
922 // Find first undefined element.
923 while (first_undefined < last_defined &&
924 !IS_UNDEFINED(obj[first_undefined])) {
927 // Maintain the invariant num_holes = the number of holes in the original
928 // array with indices <= first_undefined or > last_defined.
929 if (!obj.hasOwnProperty(first_undefined)) {
933 // Find last defined element.
934 while (first_undefined < last_defined &&
935 IS_UNDEFINED(obj[last_defined])) {
936 if (!obj.hasOwnProperty(last_defined)) {
941 if (first_undefined < last_defined) {
942 // Fill in hole or undefined.
943 obj[first_undefined] = obj[last_defined];
944 obj[last_defined] = void 0;
947 // If there were any undefineds in the entire array, first_undefined
948 // points to one past the last defined element. Make this true if
949 // there were no undefineds, as well, so that first_undefined == number
950 // of defined elements.
951 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
952 // Fill in the undefineds and the holes. There may be a hole where
953 // an undefined should be and vice versa.
955 for (i = first_undefined; i < length - num_holes; i++) {
958 for (i = length - num_holes; i < length; i++) {
959 // For compatability with Webkit, do not expose elements in the prototype.
960 if (i in obj.__proto__) {
967 // Return the number of defined elements.
968 return first_undefined;
971 var length = TO_UINT32(this.length);
972 if (length < 2) return this;
974 var is_array = IS_ARRAY(this);
975 var max_prototype_element;
977 // For compatibility with JSC, we also sort elements inherited from
978 // the prototype chain on non-Array objects.
979 // We do this by copying them to this object and sorting only
980 // local elements. This is not very efficient, but sorting with
981 // inherited elements happens very, very rarely, if at all.
982 // The specification allows "implementation dependent" behavior
983 // if an element on the prototype chain has an element that
984 // might interact with sorting.
985 max_prototype_element = CopyFromPrototype(this, length);
988 var num_non_undefined = %RemoveArrayHoles(this, length);
989 if (num_non_undefined == -1) {
990 // There were indexed accessors in the array. Move array holes and
991 // undefineds to the end using a Javascript function that is safe
992 // in the presence of accessors.
993 num_non_undefined = SafeRemoveArrayHoles(this);
996 QuickSort(this, 0, num_non_undefined);
998 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
999 // For compatibility with JSC, we shadow any elements in the prototype
1000 // chain that has become exposed by sort moving a hole to its position.
1001 ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
1008 // The following functions cannot be made efficient on sparse arrays while
1009 // preserving the semantics, since the calls to the receiver function can add
1010 // or delete elements from the array.
1011 function ArrayFilter(f, receiver) {
1012 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1013 throw MakeTypeError("called_on_null_or_undefined",
1014 ["Array.prototype.filter"]);
1017 // Pull out the length so that modifications to the length in the
1018 // loop will not affect the looping and side effects are visible.
1019 var array = ToObject(this);
1020 var length = ToUint32(array.length);
1022 if (!IS_SPEC_FUNCTION(f)) {
1023 throw MakeTypeError('called_non_callable', [ f ]);
1025 if (IS_NULL_OR_UNDEFINED(receiver)) {
1026 receiver = %GetDefaultReceiver(f) || receiver;
1027 } else if (!IS_SPEC_OBJECT(receiver)) {
1028 receiver = ToObject(receiver);
1031 var result = new $Array();
1032 var accumulator = new InternalArray();
1033 var accumulator_length = 0;
1034 if (%DebugCallbackSupportsStepping(f)) {
1035 for (var i = 0; i < length; i++) {
1037 var element = array[i];
1038 // Prepare break slots for debugger step in.
1039 %DebugPrepareStepInIfStepping(f);
1040 if (%_CallFunction(receiver, element, i, array, f)) {
1041 accumulator[accumulator_length++] = element;
1046 // This is a duplicate of the previous loop sans debug stepping.
1047 for (var i = 0; i < length; i++) {
1049 var element = array[i];
1050 if (%_CallFunction(receiver, element, i, array, f)) {
1051 accumulator[accumulator_length++] = element;
1055 // End of duplicate.
1057 %MoveArrayContents(accumulator, result);
1062 function ArrayForEach(f, receiver) {
1063 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1064 throw MakeTypeError("called_on_null_or_undefined",
1065 ["Array.prototype.forEach"]);
1068 // Pull out the length so that modifications to the length in the
1069 // loop will not affect the looping and side effects are visible.
1070 var array = ToObject(this);
1071 var length = TO_UINT32(array.length);
1073 if (!IS_SPEC_FUNCTION(f)) {
1074 throw MakeTypeError('called_non_callable', [ f ]);
1076 if (IS_NULL_OR_UNDEFINED(receiver)) {
1077 receiver = %GetDefaultReceiver(f) || receiver;
1078 } else if (!IS_SPEC_OBJECT(receiver)) {
1079 receiver = ToObject(receiver);
1081 if (%DebugCallbackSupportsStepping(f)) {
1082 for (var i = 0; i < length; i++) {
1084 var element = array[i];
1085 // Prepare break slots for debugger step in.
1086 %DebugPrepareStepInIfStepping(f);
1087 %_CallFunction(receiver, element, i, array, f);
1091 // This is a duplicate of the previous loop sans debug stepping.
1092 for (var i = 0; i < length; i++) {
1094 var element = array[i];
1095 %_CallFunction(receiver, element, i, array, f);
1098 // End of duplicate.
1103 // Executes the function once for each element present in the
1104 // array until it finds one where callback returns true.
1105 function ArraySome(f, receiver) {
1106 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1107 throw MakeTypeError("called_on_null_or_undefined",
1108 ["Array.prototype.some"]);
1111 // Pull out the length so that modifications to the length in the
1112 // loop will not affect the looping and side effects are visible.
1113 var array = ToObject(this);
1114 var length = TO_UINT32(array.length);
1116 if (!IS_SPEC_FUNCTION(f)) {
1117 throw MakeTypeError('called_non_callable', [ f ]);
1119 if (IS_NULL_OR_UNDEFINED(receiver)) {
1120 receiver = %GetDefaultReceiver(f) || receiver;
1121 } else if (!IS_SPEC_OBJECT(receiver)) {
1122 receiver = ToObject(receiver);
1125 if (%DebugCallbackSupportsStepping(f)) {
1126 for (var i = 0; i < length; i++) {
1128 var element = array[i];
1129 // Prepare break slots for debugger step in.
1130 %DebugPrepareStepInIfStepping(f);
1131 if (%_CallFunction(receiver, element, i, array, f)) return true;
1135 // This is a duplicate of the previous loop sans debug stepping.
1136 for (var i = 0; i < length; i++) {
1138 var element = array[i];
1139 if (%_CallFunction(receiver, element, i, array, f)) return true;
1142 // End of duplicate.
1148 function ArrayEvery(f, receiver) {
1149 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1150 throw MakeTypeError("called_on_null_or_undefined",
1151 ["Array.prototype.every"]);
1154 // Pull out the length so that modifications to the length in the
1155 // loop will not affect the looping and side effects are visible.
1156 var array = ToObject(this);
1157 var length = TO_UINT32(array.length);
1159 if (!IS_SPEC_FUNCTION(f)) {
1160 throw MakeTypeError('called_non_callable', [ f ]);
1162 if (IS_NULL_OR_UNDEFINED(receiver)) {
1163 receiver = %GetDefaultReceiver(f) || receiver;
1164 } else if (!IS_SPEC_OBJECT(receiver)) {
1165 receiver = ToObject(receiver);
1168 if (%DebugCallbackSupportsStepping(f)) {
1169 for (var i = 0; i < length; i++) {
1171 var element = array[i];
1172 // Prepare break slots for debugger step in.
1173 %DebugPrepareStepInIfStepping(f);
1174 if (!%_CallFunction(receiver, element, i, array, f)) return false;
1178 // This is a duplicate of the previous loop sans debug stepping.
1179 for (var i = 0; i < length; i++) {
1181 var element = array[i];
1182 if (!%_CallFunction(receiver, element, i, array, f)) return false;
1185 // End of duplicate.
1190 function ArrayMap(f, receiver) {
1191 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1192 throw MakeTypeError("called_on_null_or_undefined",
1193 ["Array.prototype.map"]);
1196 // Pull out the length so that modifications to the length in the
1197 // loop will not affect the looping and side effects are visible.
1198 var array = ToObject(this);
1199 var length = TO_UINT32(array.length);
1201 if (!IS_SPEC_FUNCTION(f)) {
1202 throw MakeTypeError('called_non_callable', [ f ]);
1204 if (IS_NULL_OR_UNDEFINED(receiver)) {
1205 receiver = %GetDefaultReceiver(f) || receiver;
1206 } else if (!IS_SPEC_OBJECT(receiver)) {
1207 receiver = ToObject(receiver);
1210 var result = new $Array();
1211 var accumulator = new InternalArray(length);
1212 if (%DebugCallbackSupportsStepping(f)) {
1213 for (var i = 0; i < length; i++) {
1215 var element = array[i];
1216 // Prepare break slots for debugger step in.
1217 %DebugPrepareStepInIfStepping(f);
1218 accumulator[i] = %_CallFunction(receiver, element, i, array, f);
1222 // This is a duplicate of the previous loop sans debug stepping.
1223 for (var i = 0; i < length; i++) {
1225 var element = array[i];
1226 accumulator[i] = %_CallFunction(receiver, element, i, array, f);
1229 // End of duplicate.
1231 %MoveArrayContents(accumulator, result);
1236 function ArrayIndexOf(element, index) {
1237 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1238 throw MakeTypeError("called_on_null_or_undefined",
1239 ["Array.prototype.indexOf"]);
1242 var length = TO_UINT32(this.length);
1243 if (length == 0) return -1;
1244 if (IS_UNDEFINED(index)) {
1247 index = TO_INTEGER(index);
1248 // If index is negative, index from the end of the array.
1250 index = length + index;
1251 // If index is still negative, search the entire array.
1252 if (index < 0) index = 0;
1257 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1258 var intervals = %GetArrayKeys(this, length);
1259 if (intervals.length == 2 && intervals[0] < 0) {
1260 // A single interval.
1261 var intervalMin = -(intervals[0] + 1);
1262 var intervalMax = intervalMin + intervals[1];
1263 if (min < intervalMin) min = intervalMin;
1264 max = intervalMax; // Capped by length already.
1265 // Fall through to loop below.
1267 if (intervals.length == 0) return -1;
1268 // Get all the keys in sorted order.
1269 var sortedKeys = GetSortedArrayKeys(this, intervals);
1270 var n = sortedKeys.length;
1272 while (i < n && sortedKeys[i] < index) i++;
1274 var key = sortedKeys[i];
1275 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1281 // Lookup through the array.
1282 if (!IS_UNDEFINED(element)) {
1283 for (var i = min; i < max; i++) {
1284 if (this[i] === element) return i;
1288 // Lookup through the array.
1289 for (var i = min; i < max; i++) {
1290 if (IS_UNDEFINED(this[i]) && i in this) {
1298 function ArrayLastIndexOf(element, index) {
1299 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1300 throw MakeTypeError("called_on_null_or_undefined",
1301 ["Array.prototype.lastIndexOf"]);
1304 var length = TO_UINT32(this.length);
1305 if (length == 0) return -1;
1306 if (%_ArgumentsLength() < 2) {
1309 index = TO_INTEGER(index);
1310 // If index is negative, index from end of the array.
1311 if (index < 0) index += length;
1312 // If index is still negative, do not search the array.
1313 if (index < 0) return -1;
1314 else if (index >= length) index = length - 1;
1318 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1319 var intervals = %GetArrayKeys(this, index + 1);
1320 if (intervals.length == 2 && intervals[0] < 0) {
1321 // A single interval.
1322 var intervalMin = -(intervals[0] + 1);
1323 var intervalMax = intervalMin + intervals[1];
1324 if (min < intervalMin) min = intervalMin;
1325 max = intervalMax; // Capped by index already.
1326 // Fall through to loop below.
1328 if (intervals.length == 0) return -1;
1329 // Get all the keys in sorted order.
1330 var sortedKeys = GetSortedArrayKeys(this, intervals);
1331 var i = sortedKeys.length - 1;
1333 var key = sortedKeys[i];
1334 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1340 // Lookup through the array.
1341 if (!IS_UNDEFINED(element)) {
1342 for (var i = max; i >= min; i--) {
1343 if (this[i] === element) return i;
1347 for (var i = max; i >= min; i--) {
1348 if (IS_UNDEFINED(this[i]) && i in this) {
1356 function ArrayReduce(callback, current) {
1357 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1358 throw MakeTypeError("called_on_null_or_undefined",
1359 ["Array.prototype.reduce"]);
1362 // Pull out the length so that modifications to the length in the
1363 // loop will not affect the looping and side effects are visible.
1364 var array = ToObject(this);
1365 var length = ToUint32(array.length);
1367 if (!IS_SPEC_FUNCTION(callback)) {
1368 throw MakeTypeError('called_non_callable', [callback]);
1372 find_initial: if (%_ArgumentsLength() < 2) {
1373 for (; i < length; i++) {
1375 if (!IS_UNDEFINED(current) || i in array) {
1380 throw MakeTypeError('reduce_no_initial', []);
1383 var receiver = %GetDefaultReceiver(callback);
1385 if (%DebugCallbackSupportsStepping(callback)) {
1386 for (; i < length; i++) {
1388 var element = array[i];
1389 // Prepare break slots for debugger step in.
1390 %DebugPrepareStepInIfStepping(callback);
1392 %_CallFunction(receiver, current, element, i, array, callback);
1396 // This is a duplicate of the previous loop sans debug stepping.
1397 for (; i < length; i++) {
1399 var element = array[i];
1401 %_CallFunction(receiver, current, element, i, array, callback);
1404 // End of duplicate.
1409 function ArrayReduceRight(callback, current) {
1410 if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
1411 throw MakeTypeError("called_on_null_or_undefined",
1412 ["Array.prototype.reduceRight"]);
1415 // Pull out the length so that side effects are visible before the
1416 // callback function is checked.
1417 var array = ToObject(this);
1418 var length = ToUint32(array.length);
1420 if (!IS_SPEC_FUNCTION(callback)) {
1421 throw MakeTypeError('called_non_callable', [callback]);
1425 find_initial: if (%_ArgumentsLength() < 2) {
1426 for (; i >= 0; i--) {
1428 if (!IS_UNDEFINED(current) || i in array) {
1433 throw MakeTypeError('reduce_no_initial', []);
1436 var receiver = %GetDefaultReceiver(callback);
1438 if (%DebugCallbackSupportsStepping(callback)) {
1439 for (; i >= 0; i--) {
1441 var element = array[i];
1442 // Prepare break slots for debugger step in.
1443 %DebugPrepareStepInIfStepping(callback);
1445 %_CallFunction(receiver, current, element, i, array, callback);
1449 // This is a duplicate of the previous loop sans debug stepping.
1450 for (; i >= 0; i--) {
1452 var element = array[i];
1454 %_CallFunction(receiver, current, element, i, array, callback);
1457 // End of duplicate.
1463 function ArrayIsArray(obj) {
1464 return IS_ARRAY(obj);
1468 // -------------------------------------------------------------------
1469 function SetUpArray() {
1470 %CheckIsBootstrapping();
1471 // Set up non-enumerable constructor property on the Array.prototype
1473 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
1475 // Set up non-enumerable functions on the Array object.
1476 InstallFunctions($Array, DONT_ENUM, $Array(
1477 "isArray", ArrayIsArray
1480 var specialFunctions = %SpecialArrayFunctions({});
1482 var getFunction = function(name, jsBuiltin, len) {
1484 if (specialFunctions.hasOwnProperty(name)) {
1485 f = specialFunctions[name];
1487 if (!IS_UNDEFINED(len)) {
1488 %FunctionSetLength(f, len);
1493 // Set up non-enumerable functions of the Array.prototype object and
1495 // Manipulate the length of some of the functions to meet
1496 // expectations set by ECMA-262 or Mozilla.
1497 InstallFunctions($Array.prototype, DONT_ENUM, $Array(
1498 "toString", getFunction("toString", ArrayToString),
1499 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
1500 "join", getFunction("join", ArrayJoin),
1501 "pop", getFunction("pop", ArrayPop),
1502 "push", getFunction("push", ArrayPush, 1),
1503 "concat", getFunction("concat", ArrayConcat, 1),
1504 "reverse", getFunction("reverse", ArrayReverse),
1505 "shift", getFunction("shift", ArrayShift),
1506 "unshift", getFunction("unshift", ArrayUnshift, 1),
1507 "slice", getFunction("slice", ArraySlice, 2),
1508 "splice", getFunction("splice", ArraySplice, 2),
1509 "sort", getFunction("sort", ArraySort),
1510 "filter", getFunction("filter", ArrayFilter, 1),
1511 "forEach", getFunction("forEach", ArrayForEach, 1),
1512 "some", getFunction("some", ArraySome, 1),
1513 "every", getFunction("every", ArrayEvery, 1),
1514 "map", getFunction("map", ArrayMap, 1),
1515 "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
1516 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1517 "reduce", getFunction("reduce", ArrayReduce, 1),
1518 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1521 %FinishArrayPrototypeSetup($Array.prototype);
1523 // The internal Array prototype doesn't need to be fancy, since it's never
1524 // exposed to user code.
1525 // Adding only the functions that are actually used.
1526 SetUpLockedPrototype(InternalArray, $Array(), $Array(
1527 "join", getFunction("join", ArrayJoin),
1528 "pop", getFunction("pop", ArrayPop),
1529 "push", getFunction("push", ArrayPush)