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 SparseJoinWithSeparator(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(object, length, is_array) {
93 %EstimateNumberOfElements(object) < (length >> 2));
97 function Join(array, length, separator, convert) {
98 if (length == 0) return '';
100 var is_array = IS_ARRAY(array);
103 // If the array is cyclic, return the empty string for already
105 if (!%PushIfAbsent(visited_arrays, array)) return '';
108 // Attempt to convert the elements.
110 if (UseSparseVariant(array, length, is_array)) {
111 if (separator.length == 0) {
112 return SparseJoin(array, length, convert);
114 return SparseJoinWithSeparator(array, length, convert, separator);
118 // Fast case for one-element arrays.
121 if (IS_STRING(e)) return e;
125 // Construct an array for the elements.
126 var elements = new InternalArray(length);
128 // We pull the empty separator check outside the loop for speed!
129 if (separator.length == 0) {
130 var elements_length = 0;
131 for (var i = 0; i < length; i++) {
133 if (!IS_STRING(e)) e = convert(e);
134 elements[elements_length++] = e;
136 elements.length = elements_length;
137 var result = %_FastAsciiArrayJoin(elements, '');
138 if (!IS_UNDEFINED(result)) return result;
139 return %StringBuilderConcat(elements, elements_length, '');
141 // Non-empty separator case.
142 // If the first element is a number then use the heuristic that the
143 // remaining elements are also likely to be numbers.
144 if (!IS_NUMBER(array[0])) {
145 for (var i = 0; i < length; i++) {
147 if (!IS_STRING(e)) e = convert(e);
151 for (var i = 0; i < length; i++) {
154 e = %_NumberToString(e);
155 } else if (!IS_STRING(e)) {
161 var result = %_FastAsciiArrayJoin(elements, separator);
162 if (!IS_UNDEFINED(result)) return result;
164 return %StringBuilderJoin(elements, length, separator);
166 // Make sure to remove the last element of the visited array no
167 // matter what happens.
168 if (is_array) visited_arrays.length = visited_arrays.length - 1;
173 function ConvertToString(x) {
174 // Assumes x is a non-string.
175 if (IS_NUMBER(x)) return %_NumberToString(x);
176 if (IS_BOOLEAN(x)) return x ? 'true' : 'false';
177 return (IS_NULL_OR_UNDEFINED(x)) ? '' : %ToString(%DefaultString(x));
181 function ConvertToLocaleString(e) {
182 if (IS_NULL_OR_UNDEFINED(e)) {
185 // According to ES5, section 15.4.4.3, the toLocaleString conversion
186 // must throw a TypeError if ToObject(e).toLocaleString isn't
188 var e_obj = ToObject(e);
189 return %ToString(e_obj.toLocaleString());
194 // This function implements the optimized splice implementation that can use
195 // special array operations to handle sparse arrays in a sensible fashion.
196 function SmartSlice(array, start_i, del_count, len, deleted_elements) {
197 // Move deleted elements to a new array (the return value from splice).
198 var indices = %GetArrayKeys(array, start_i + del_count);
199 if (IS_NUMBER(indices)) {
201 for (var i = start_i; i < limit; ++i) {
202 var current = array[i];
203 if (!IS_UNDEFINED(current) || i in array) {
204 deleted_elements[i - start_i] = current;
208 var length = indices.length;
209 for (var k = 0; k < length; ++k) {
210 var key = indices[k];
211 if (!IS_UNDEFINED(key)) {
212 if (key >= start_i) {
213 var current = array[key];
214 if (!IS_UNDEFINED(current) || key in array) {
215 deleted_elements[key - start_i] = current;
224 // This function implements the optimized splice implementation that can use
225 // special array operations to handle sparse arrays in a sensible fashion.
226 function SmartMove(array, start_i, del_count, len, num_additional_args) {
227 // Move data to new array.
228 var new_array = new InternalArray(len - del_count + num_additional_args);
229 var indices = %GetArrayKeys(array, len);
230 if (IS_NUMBER(indices)) {
232 for (var i = 0; i < start_i && i < limit; ++i) {
233 var current = array[i];
234 if (!IS_UNDEFINED(current) || i in array) {
235 new_array[i] = current;
238 for (var i = start_i + del_count; i < limit; ++i) {
239 var current = array[i];
240 if (!IS_UNDEFINED(current) || i in array) {
241 new_array[i - del_count + num_additional_args] = current;
245 var length = indices.length;
246 for (var k = 0; k < length; ++k) {
247 var key = indices[k];
248 if (!IS_UNDEFINED(key)) {
250 var current = array[key];
251 if (!IS_UNDEFINED(current) || key in array) {
252 new_array[key] = current;
254 } else if (key >= start_i + del_count) {
255 var current = array[key];
256 if (!IS_UNDEFINED(current) || key in array) {
257 new_array[key - del_count + num_additional_args] = current;
263 // Move contents of new_array into this array
264 %MoveArrayContents(new_array, array);
268 // This is part of the old simple-minded splice. We are using it either
269 // because the receiver is not an array (so we have no choice) or because we
270 // know we are not deleting or moving a lot of elements.
271 function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
272 for (var i = 0; i < del_count; i++) {
273 var index = start_i + i;
274 // The spec could also be interpreted such that %HasLocalProperty
275 // would be the appropriate test. We follow KJS in consulting the
277 var current = array[index];
278 if (!IS_UNDEFINED(current) || index in array) {
279 deleted_elements[i] = current;
285 function SimpleMove(array, start_i, del_count, len, num_additional_args) {
286 if (num_additional_args !== del_count) {
287 // Move the existing elements after the elements to be deleted
288 // to the right position in the resulting array.
289 if (num_additional_args > del_count) {
290 for (var i = len - del_count; i > start_i; i--) {
291 var from_index = i + del_count - 1;
292 var to_index = i + num_additional_args - 1;
293 // The spec could also be interpreted such that
294 // %HasLocalProperty would be the appropriate test. We follow
295 // KJS in consulting the prototype.
296 var current = array[from_index];
297 if (!IS_UNDEFINED(current) || from_index in array) {
298 array[to_index] = current;
300 delete array[to_index];
304 for (var i = start_i; i < len - del_count; i++) {
305 var from_index = i + del_count;
306 var to_index = i + num_additional_args;
307 // The spec could also be interpreted such that
308 // %HasLocalProperty would be the appropriate test. We follow
309 // KJS in consulting the prototype.
310 var current = array[from_index];
311 if (!IS_UNDEFINED(current) || from_index in array) {
312 array[to_index] = current;
314 delete array[to_index];
317 for (var i = len; i > len - del_count + num_additional_args; i--) {
325 // -------------------------------------------------------------------
328 function ArrayToString() {
331 if (IS_ARRAY(this)) {
333 if (func === ArrayJoin) {
334 return Join(this, this.length, ',', ConvertToString);
338 array = ToObject(this);
341 if (!IS_SPEC_FUNCTION(func)) {
342 return %_CallFunction(array, ObjectToString);
344 return %_CallFunction(array, func);
348 function ArrayToLocaleString() {
349 var array = ToObject(this);
350 var arrayLen = array.length;
351 var len = TO_UINT32(arrayLen);
352 if (len === 0) return "";
353 return Join(array, len, ',', ConvertToLocaleString);
357 function ArrayJoin(separator) {
358 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.join");
360 var array = TO_OBJECT_INLINE(this);
361 var length = TO_UINT32(array.length);
362 if (IS_UNDEFINED(separator)) {
364 } else if (!IS_STRING(separator)) {
365 separator = NonStringToString(separator);
368 var result = %_FastAsciiArrayJoin(array, separator);
369 if (!IS_UNDEFINED(result)) return result;
371 return Join(array, length, separator, ConvertToString);
375 function ObservedArrayPop(n) {
380 BeginPerformSplice(this);
384 EndPerformSplice(this);
385 EnqueueSpliceRecord(this, n, [value], 0);
391 // Removes the last element from the array and returns it. See
392 // ECMA-262, section 15.4.4.6.
393 function ArrayPop() {
394 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.pop");
396 var array = TO_OBJECT_INLINE(this);
397 var n = TO_UINT32(array.length);
403 if (%IsObserved(array))
404 return ObservedArrayPop.call(array, n);
407 var value = array[n];
408 Delete(array, ToName(n), true);
414 function ObservedArrayPush() {
415 var n = TO_UINT32(this.length);
416 var m = %_ArgumentsLength();
419 BeginPerformSplice(this);
420 for (var i = 0; i < m; i++) {
421 this[i+n] = %_Arguments(i);
423 var new_length = n + m;
424 this.length = new_length;
426 EndPerformSplice(this);
427 EnqueueSpliceRecord(this, n, [], m);
433 // Appends the arguments to the end of the array and returns the new
434 // length of the array. See ECMA-262, section 15.4.4.7.
435 function ArrayPush() {
436 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.push");
438 if (%IsObserved(this))
439 return ObservedArrayPush.apply(this, arguments);
441 var array = TO_OBJECT_INLINE(this);
442 var n = TO_UINT32(array.length);
443 var m = %_ArgumentsLength();
445 for (var i = 0; i < m; i++) {
446 // Use SetProperty rather than a direct keyed store to ensure that the store
447 // site doesn't become poisened with an elements transition KeyedStoreIC.
448 %SetProperty(array, i+n, %_Arguments(i), 0, kStrictMode);
451 var new_length = n + m;
452 array.length = new_length;
457 // Returns an array containing the array elements of the object followed
458 // by the array elements of each argument in order. See ECMA-262,
460 function ArrayConcat(arg1) { // length == 1
461 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.concat");
463 var array = ToObject(this);
464 var arg_count = %_ArgumentsLength();
465 var arrays = new InternalArray(1 + arg_count);
467 for (var i = 0; i < arg_count; i++) {
468 arrays[i + 1] = %_Arguments(i);
471 return %ArrayConcat(arrays);
475 // For implementing reverse() on large, sparse arrays.
476 function SparseReverse(array, len) {
477 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
478 var high_counter = keys.length - 1;
480 while (low_counter <= high_counter) {
481 var i = keys[low_counter];
482 var j = keys[high_counter];
484 var j_complement = len - j - 1;
487 if (j_complement <= i) {
489 while (keys[--high_counter] == j) { }
492 if (j_complement >= i) {
494 while (keys[++low_counter] == i) { }
498 var current_i = array[low];
499 if (!IS_UNDEFINED(current_i) || low in array) {
500 var current_j = array[high];
501 if (!IS_UNDEFINED(current_j) || high in array) {
502 array[low] = current_j;
503 array[high] = current_i;
505 array[high] = current_i;
509 var current_j = array[high];
510 if (!IS_UNDEFINED(current_j) || high in array) {
511 array[low] = current_j;
519 function ArrayReverse() {
520 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reverse");
522 var array = TO_OBJECT_INLINE(this);
523 var j = TO_UINT32(array.length) - 1;
525 if (UseSparseVariant(array, j, IS_ARRAY(array))) {
526 SparseReverse(array, j+1);
530 for (var i = 0; i < j; i++, j--) {
531 var current_i = array[i];
532 if (!IS_UNDEFINED(current_i) || i in array) {
533 var current_j = array[j];
534 if (!IS_UNDEFINED(current_j) || j in array) {
535 array[i] = current_j;
536 array[j] = current_i;
538 array[j] = current_i;
542 var current_j = array[j];
543 if (!IS_UNDEFINED(current_j) || j in array) {
544 array[i] = current_j;
553 function ObservedArrayShift(len) {
557 BeginPerformSplice(this);
558 SimpleMove(this, 0, 1, len, 0);
559 this.length = len - 1;
561 EndPerformSplice(this);
562 EnqueueSpliceRecord(this, 0, [first], 0);
568 function ArrayShift() {
569 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.shift");
571 var array = TO_OBJECT_INLINE(this);
572 var len = TO_UINT32(array.length);
579 if (ObjectIsSealed(array)) {
580 throw MakeTypeError("array_functions_change_sealed",
581 ["Array.prototype.shift"]);
584 if (%IsObserved(array))
585 return ObservedArrayShift.call(array, len);
587 var first = array[0];
589 if (IS_ARRAY(array)) {
590 SmartMove(array, 0, 1, len, 0);
592 SimpleMove(array, 0, 1, len, 0);
595 array.length = len - 1;
600 function ObservedArrayUnshift() {
601 var len = TO_UINT32(this.length);
602 var num_arguments = %_ArgumentsLength();
605 BeginPerformSplice(this);
606 SimpleMove(this, 0, 0, len, num_arguments);
607 for (var i = 0; i < num_arguments; i++) {
608 this[i] = %_Arguments(i);
610 var new_length = len + num_arguments;
611 this.length = new_length;
613 EndPerformSplice(this);
614 EnqueueSpliceRecord(this, 0, [], num_arguments);
620 function ArrayUnshift(arg1) { // length == 1
621 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.unshift");
623 if (%IsObserved(this))
624 return ObservedArrayUnshift.apply(this, arguments);
626 var array = TO_OBJECT_INLINE(this);
627 var len = TO_UINT32(array.length);
628 var num_arguments = %_ArgumentsLength();
629 var is_sealed = ObjectIsSealed(array);
631 if (IS_ARRAY(array) && !is_sealed) {
632 SmartMove(array, 0, 0, len, num_arguments);
634 SimpleMove(array, 0, 0, len, num_arguments);
637 for (var i = 0; i < num_arguments; i++) {
638 array[i] = %_Arguments(i);
641 var new_length = len + num_arguments;
642 array.length = new_length;
647 function ArraySlice(start, end) {
648 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.slice");
650 var array = TO_OBJECT_INLINE(this);
651 var len = TO_UINT32(array.length);
652 var start_i = TO_INTEGER(start);
655 if (!IS_UNDEFINED(end)) end_i = TO_INTEGER(end);
659 if (start_i < 0) start_i = 0;
661 if (start_i > len) start_i = len;
666 if (end_i < 0) end_i = 0;
668 if (end_i > len) end_i = len;
673 if (end_i < start_i) return result;
675 if (IS_ARRAY(array) &&
676 !%IsObserved(array) &&
678 (%EstimateNumberOfElements(array) < end_i)) {
679 SmartSlice(array, start_i, end_i - start_i, len, result);
681 SimpleSlice(array, start_i, end_i - start_i, len, result);
684 result.length = end_i - start_i;
690 function ComputeSpliceStartIndex(start_i, len) {
693 return start_i < 0 ? 0 : start_i;
696 return start_i > len ? len : start_i;
700 function ComputeSpliceDeleteCount(delete_count, num_arguments, len, start_i) {
701 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
702 // given as a request to delete all the elements from the start.
703 // And it differs from the case of undefined delete count.
704 // This does not follow ECMA-262, but we do the same for
707 if (num_arguments == 1)
708 return len - start_i;
710 del_count = TO_INTEGER(delete_count);
714 if (del_count > len - start_i)
715 return len - start_i;
721 function ObservedArraySplice(start, delete_count) {
722 var num_arguments = %_ArgumentsLength();
723 var len = TO_UINT32(this.length);
724 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
725 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
727 var deleted_elements = [];
728 deleted_elements.length = del_count;
729 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
732 BeginPerformSplice(this);
734 SimpleSlice(this, start_i, del_count, len, deleted_elements);
735 SimpleMove(this, start_i, del_count, len, num_elements_to_add);
737 // Insert the arguments into the resulting array in
738 // place of the deleted elements.
740 var arguments_index = 2;
741 var arguments_length = %_ArgumentsLength();
742 while (arguments_index < arguments_length) {
743 this[i++] = %_Arguments(arguments_index++);
745 this.length = len - del_count + num_elements_to_add;
748 EndPerformSplice(this);
749 if (deleted_elements.length || num_elements_to_add) {
750 EnqueueSpliceRecord(this,
752 deleted_elements.slice(),
753 num_elements_to_add);
757 // Return the deleted elements.
758 return deleted_elements;
762 function ArraySplice(start, delete_count) {
763 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.splice");
765 if (%IsObserved(this))
766 return ObservedArraySplice.apply(this, arguments);
768 var num_arguments = %_ArgumentsLength();
769 var array = TO_OBJECT_INLINE(this);
770 var len = TO_UINT32(array.length);
771 var start_i = ComputeSpliceStartIndex(TO_INTEGER(start), len);
772 var del_count = ComputeSpliceDeleteCount(delete_count, num_arguments, len,
774 var deleted_elements = [];
775 deleted_elements.length = del_count;
776 var num_elements_to_add = num_arguments > 2 ? num_arguments - 2 : 0;
778 if (del_count != num_elements_to_add && ObjectIsSealed(array)) {
779 throw MakeTypeError("array_functions_change_sealed",
780 ["Array.prototype.splice"]);
781 } else if (del_count > 0 && ObjectIsFrozen(array)) {
782 throw MakeTypeError("array_functions_on_frozen",
783 ["Array.prototype.splice"]);
786 var use_simple_splice = true;
787 if (IS_ARRAY(array) &&
788 num_elements_to_add !== del_count) {
789 // If we are only deleting/moving a few things near the end of the
790 // array then the simple version is going to be faster, because it
791 // doesn't touch most of the array.
792 var estimated_non_hole_elements = %EstimateNumberOfElements(array);
793 if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
794 use_simple_splice = false;
798 if (use_simple_splice) {
799 SimpleSlice(array, start_i, del_count, len, deleted_elements);
800 SimpleMove(array, start_i, del_count, len, num_elements_to_add);
802 SmartSlice(array, start_i, del_count, len, deleted_elements);
803 SmartMove(array, start_i, del_count, len, num_elements_to_add);
806 // Insert the arguments into the resulting array in
807 // place of the deleted elements.
809 var arguments_index = 2;
810 var arguments_length = %_ArgumentsLength();
811 while (arguments_index < arguments_length) {
812 array[i++] = %_Arguments(arguments_index++);
814 array.length = len - del_count + num_elements_to_add;
816 // Return the deleted elements.
817 return deleted_elements;
821 function ArraySort(comparefn) {
822 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
824 // In-place QuickSort algorithm.
825 // For short (length <= 22) arrays, insertion sort is used for efficiency.
827 if (!IS_SPEC_FUNCTION(comparefn)) {
828 comparefn = function (x, y) {
829 if (x === y) return 0;
830 if (%_IsSmi(x) && %_IsSmi(y)) {
831 return %SmiLexicographicCompare(x, y);
835 if (x == y) return 0;
836 else return x < y ? -1 : 1;
839 var receiver = %GetDefaultReceiver(comparefn);
841 var InsertionSort = function InsertionSort(a, from, to) {
842 for (var i = from + 1; i < to; i++) {
844 for (var j = i - 1; j >= from; j--) {
846 var order = %_CallFunction(receiver, tmp, element, comparefn);
857 var GetThirdIndex = function(a, from, to) {
859 // Use both 'from' and 'to' to determine the pivot candidates.
860 var increment = 200 + ((to - from) & 15);
861 for (var i = from + 1; i < to - 1; i += increment) {
862 t_array.push([i, a[i]]);
864 t_array.sort(function(a, b) {
865 return %_CallFunction(receiver, a[1], b[1], comparefn) } );
866 var third_index = t_array[t_array.length >> 1][0];
870 var QuickSort = function QuickSort(a, from, to) {
873 // Insertion sort is faster for short arrays.
874 if (to - from <= 10) {
875 InsertionSort(a, from, to);
878 if (to - from > 1000) {
879 third_index = GetThirdIndex(a, from, to);
881 third_index = from + ((to - from) >> 1);
883 // Find a pivot as the median of first, last and middle element.
886 var v2 = a[third_index];
887 var c01 = %_CallFunction(receiver, v0, v1, comparefn);
889 // v1 < v0, so swap them.
894 var c02 = %_CallFunction(receiver, v0, v2, comparefn);
902 // v0 <= v1 && v0 < v2
903 var c12 = %_CallFunction(receiver, v1, v2, comparefn);
915 var low_end = from + 1; // Upper bound of elements lower than pivot.
916 var high_start = to - 1; // Lower bound of elements greater than pivot.
917 a[third_index] = a[low_end];
920 // From low_end to i are elements equal to pivot.
921 // From i to high_start are elements that haven't been compared yet.
922 partition: for (var i = low_end + 1; i < high_start; i++) {
924 var order = %_CallFunction(receiver, element, pivot, comparefn);
927 a[low_end] = element;
929 } else if (order > 0) {
932 if (high_start == i) break partition;
933 var top_elem = a[high_start];
934 order = %_CallFunction(receiver, top_elem, pivot, comparefn);
936 a[i] = a[high_start];
937 a[high_start] = element;
941 a[low_end] = element;
946 if (to - high_start < low_end - from) {
947 QuickSort(a, high_start, to);
950 QuickSort(a, from, low_end);
956 // Copy elements in the range 0..length from obj's prototype chain
957 // to obj itself, if obj has holes. Return one more than the maximal index
958 // of a prototype property.
959 var CopyFromPrototype = function CopyFromPrototype(obj, length) {
961 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
962 var indices = %GetArrayKeys(proto, length);
963 if (IS_NUMBER(indices)) {
965 var proto_length = indices;
966 for (var i = 0; i < proto_length; i++) {
967 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
969 if (i >= max) { max = i + 1; }
973 for (var i = 0; i < indices.length; i++) {
974 var index = indices[i];
975 if (!IS_UNDEFINED(index) &&
976 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) {
977 obj[index] = proto[index];
978 if (index >= max) { max = index + 1; }
986 // Set a value of "undefined" on all indices in the range from..to
987 // where a prototype of obj has an element. I.e., shadow all prototype
988 // elements in that range.
989 var ShadowPrototypeElements = function(obj, from, to) {
990 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) {
991 var indices = %GetArrayKeys(proto, to);
992 if (IS_NUMBER(indices)) {
994 var proto_length = indices;
995 for (var i = from; i < proto_length; i++) {
996 if (proto.hasOwnProperty(i)) {
1001 for (var i = 0; i < indices.length; i++) {
1002 var index = indices[i];
1003 if (!IS_UNDEFINED(index) && from <= index &&
1004 proto.hasOwnProperty(index)) {
1005 obj[index] = UNDEFINED;
1012 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
1013 // Copy defined elements from the end to fill in all holes and undefineds
1014 // in the beginning of the array. Write undefineds and holes at the end
1015 // after loop is finished.
1016 var first_undefined = 0;
1017 var last_defined = length - 1;
1019 while (first_undefined < last_defined) {
1020 // Find first undefined element.
1021 while (first_undefined < last_defined &&
1022 !IS_UNDEFINED(obj[first_undefined])) {
1025 // Maintain the invariant num_holes = the number of holes in the original
1026 // array with indices <= first_undefined or > last_defined.
1027 if (!obj.hasOwnProperty(first_undefined)) {
1031 // Find last defined element.
1032 while (first_undefined < last_defined &&
1033 IS_UNDEFINED(obj[last_defined])) {
1034 if (!obj.hasOwnProperty(last_defined)) {
1039 if (first_undefined < last_defined) {
1040 // Fill in hole or undefined.
1041 obj[first_undefined] = obj[last_defined];
1042 obj[last_defined] = UNDEFINED;
1045 // If there were any undefineds in the entire array, first_undefined
1046 // points to one past the last defined element. Make this true if
1047 // there were no undefineds, as well, so that first_undefined == number
1048 // of defined elements.
1049 if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
1050 // Fill in the undefineds and the holes. There may be a hole where
1051 // an undefined should be and vice versa.
1053 for (i = first_undefined; i < length - num_holes; i++) {
1056 for (i = length - num_holes; i < length; i++) {
1057 // For compatability with Webkit, do not expose elements in the prototype.
1058 if (i in %GetPrototype(obj)) {
1065 // Return the number of defined elements.
1066 return first_undefined;
1069 var length = TO_UINT32(this.length);
1070 if (length < 2) return this;
1072 var is_array = IS_ARRAY(this);
1073 var max_prototype_element;
1075 // For compatibility with JSC, we also sort elements inherited from
1076 // the prototype chain on non-Array objects.
1077 // We do this by copying them to this object and sorting only
1078 // local elements. This is not very efficient, but sorting with
1079 // inherited elements happens very, very rarely, if at all.
1080 // The specification allows "implementation dependent" behavior
1081 // if an element on the prototype chain has an element that
1082 // might interact with sorting.
1083 max_prototype_element = CopyFromPrototype(this, length);
1086 // %RemoveArrayHoles returns -1 if fast removal is not supported.
1087 var num_non_undefined = %RemoveArrayHoles(this, length);
1089 if (num_non_undefined == -1) {
1090 // The array is observed, or there were indexed accessors in the array.
1091 // Move array holes and undefineds to the end using a Javascript function
1092 // that is safe in the presence of accessors and is observable.
1093 num_non_undefined = SafeRemoveArrayHoles(this);
1096 QuickSort(this, 0, num_non_undefined);
1098 if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
1099 // For compatibility with JSC, we shadow any elements in the prototype
1100 // chain that has become exposed by sort moving a hole to its position.
1101 ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
1108 // The following functions cannot be made efficient on sparse arrays while
1109 // preserving the semantics, since the calls to the receiver function can add
1110 // or delete elements from the array.
1111 function ArrayFilter(f, receiver) {
1112 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.filter");
1114 // Pull out the length so that modifications to the length in the
1115 // loop will not affect the looping and side effects are visible.
1116 var array = ToObject(this);
1117 var length = ToUint32(array.length);
1119 if (!IS_SPEC_FUNCTION(f)) {
1120 throw MakeTypeError('called_non_callable', [ f ]);
1122 if (IS_NULL_OR_UNDEFINED(receiver)) {
1123 receiver = %GetDefaultReceiver(f) || receiver;
1124 } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1125 receiver = ToObject(receiver);
1128 var result = new $Array();
1129 var accumulator = new InternalArray();
1130 var accumulator_length = 0;
1131 var stepping = %_DebugCallbackSupportsStepping(f);
1132 for (var i = 0; i < length; i++) {
1134 var element = array[i];
1135 // Prepare break slots for debugger step in.
1136 if (stepping) %DebugPrepareStepInIfStepping(f);
1137 if (%_CallFunction(receiver, element, i, array, f)) {
1138 accumulator[accumulator_length++] = element;
1142 %MoveArrayContents(accumulator, result);
1147 function ArrayForEach(f, receiver) {
1148 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.forEach");
1150 // Pull out the length so that modifications to the length in the
1151 // loop will not affect the looping and side effects are visible.
1152 var array = ToObject(this);
1153 var length = TO_UINT32(array.length);
1155 if (!IS_SPEC_FUNCTION(f)) {
1156 throw MakeTypeError('called_non_callable', [ f ]);
1158 if (IS_NULL_OR_UNDEFINED(receiver)) {
1159 receiver = %GetDefaultReceiver(f) || receiver;
1160 } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1161 receiver = ToObject(receiver);
1164 var stepping = %_DebugCallbackSupportsStepping(f);
1165 for (var i = 0; i < length; i++) {
1167 var element = array[i];
1168 // Prepare break slots for debugger step in.
1169 if (stepping) %DebugPrepareStepInIfStepping(f);
1170 %_CallFunction(receiver, element, i, array, f);
1176 // Executes the function once for each element present in the
1177 // array until it finds one where callback returns true.
1178 function ArraySome(f, receiver) {
1179 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.some");
1181 // Pull out the length so that modifications to the length in the
1182 // loop will not affect the looping and side effects are visible.
1183 var array = ToObject(this);
1184 var length = TO_UINT32(array.length);
1186 if (!IS_SPEC_FUNCTION(f)) {
1187 throw MakeTypeError('called_non_callable', [ f ]);
1189 if (IS_NULL_OR_UNDEFINED(receiver)) {
1190 receiver = %GetDefaultReceiver(f) || receiver;
1191 } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1192 receiver = ToObject(receiver);
1195 var stepping = %_DebugCallbackSupportsStepping(f);
1196 for (var i = 0; i < length; i++) {
1198 var element = array[i];
1199 // Prepare break slots for debugger step in.
1200 if (stepping) %DebugPrepareStepInIfStepping(f);
1201 if (%_CallFunction(receiver, element, i, array, f)) return true;
1208 function ArrayEvery(f, receiver) {
1209 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.every");
1211 // Pull out the length so that modifications to the length in the
1212 // loop will not affect the looping and side effects are visible.
1213 var array = ToObject(this);
1214 var length = TO_UINT32(array.length);
1216 if (!IS_SPEC_FUNCTION(f)) {
1217 throw MakeTypeError('called_non_callable', [ f ]);
1219 if (IS_NULL_OR_UNDEFINED(receiver)) {
1220 receiver = %GetDefaultReceiver(f) || receiver;
1221 } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1222 receiver = ToObject(receiver);
1225 var stepping = %_DebugCallbackSupportsStepping(f);
1226 for (var i = 0; i < length; i++) {
1228 var element = array[i];
1229 // Prepare break slots for debugger step in.
1230 if (stepping) %DebugPrepareStepInIfStepping(f);
1231 if (!%_CallFunction(receiver, element, i, array, f)) return false;
1237 function ArrayMap(f, receiver) {
1238 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.map");
1240 // Pull out the length so that modifications to the length in the
1241 // loop will not affect the looping and side effects are visible.
1242 var array = ToObject(this);
1243 var length = TO_UINT32(array.length);
1245 if (!IS_SPEC_FUNCTION(f)) {
1246 throw MakeTypeError('called_non_callable', [ f ]);
1248 if (IS_NULL_OR_UNDEFINED(receiver)) {
1249 receiver = %GetDefaultReceiver(f) || receiver;
1250 } else if (!IS_SPEC_OBJECT(receiver) && %IsSloppyModeFunction(f)) {
1251 receiver = ToObject(receiver);
1254 var result = new $Array();
1255 var accumulator = new InternalArray(length);
1256 var stepping = %_DebugCallbackSupportsStepping(f);
1257 for (var i = 0; i < length; i++) {
1259 var element = array[i];
1260 // Prepare break slots for debugger step in.
1261 if (stepping) %DebugPrepareStepInIfStepping(f);
1262 accumulator[i] = %_CallFunction(receiver, element, i, array, f);
1265 %MoveArrayContents(accumulator, result);
1270 function ArrayIndexOf(element, index) {
1271 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.indexOf");
1273 var length = TO_UINT32(this.length);
1274 if (length == 0) return -1;
1275 if (IS_UNDEFINED(index)) {
1278 index = TO_INTEGER(index);
1279 // If index is negative, index from the end of the array.
1281 index = length + index;
1282 // If index is still negative, search the entire array.
1283 if (index < 0) index = 0;
1288 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1289 var indices = %GetArrayKeys(this, length);
1290 if (IS_NUMBER(indices)) {
1291 // It's an interval.
1292 max = indices; // Capped by length already.
1293 // Fall through to loop below.
1295 if (indices.length == 0) return -1;
1296 // Get all the keys in sorted order.
1297 var sortedKeys = GetSortedArrayKeys(this, indices);
1298 var n = sortedKeys.length;
1300 while (i < n && sortedKeys[i] < index) i++;
1302 var key = sortedKeys[i];
1303 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1309 // Lookup through the array.
1310 if (!IS_UNDEFINED(element)) {
1311 for (var i = min; i < max; i++) {
1312 if (this[i] === element) return i;
1316 // Lookup through the array.
1317 for (var i = min; i < max; i++) {
1318 if (IS_UNDEFINED(this[i]) && i in this) {
1326 function ArrayLastIndexOf(element, index) {
1327 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.lastIndexOf");
1329 var length = TO_UINT32(this.length);
1330 if (length == 0) return -1;
1331 if (%_ArgumentsLength() < 2) {
1334 index = TO_INTEGER(index);
1335 // If index is negative, index from end of the array.
1336 if (index < 0) index += length;
1337 // If index is still negative, do not search the array.
1338 if (index < 0) return -1;
1339 else if (index >= length) index = length - 1;
1343 if (UseSparseVariant(this, length, IS_ARRAY(this))) {
1344 var indices = %GetArrayKeys(this, index + 1);
1345 if (IS_NUMBER(indices)) {
1346 // It's an interval.
1347 max = indices; // Capped by index already.
1348 // Fall through to loop below.
1350 if (indices.length == 0) return -1;
1351 // Get all the keys in sorted order.
1352 var sortedKeys = GetSortedArrayKeys(this, indices);
1353 var i = sortedKeys.length - 1;
1355 var key = sortedKeys[i];
1356 if (!IS_UNDEFINED(key) && this[key] === element) return key;
1362 // Lookup through the array.
1363 if (!IS_UNDEFINED(element)) {
1364 for (var i = max; i >= min; i--) {
1365 if (this[i] === element) return i;
1369 for (var i = max; i >= min; i--) {
1370 if (IS_UNDEFINED(this[i]) && i in this) {
1378 function ArrayReduce(callback, current) {
1379 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduce");
1381 // Pull out the length so that modifications to the length in the
1382 // loop will not affect the looping and side effects are visible.
1383 var array = ToObject(this);
1384 var length = ToUint32(array.length);
1386 if (!IS_SPEC_FUNCTION(callback)) {
1387 throw MakeTypeError('called_non_callable', [callback]);
1391 find_initial: if (%_ArgumentsLength() < 2) {
1392 for (; i < length; i++) {
1394 if (!IS_UNDEFINED(current) || i in array) {
1399 throw MakeTypeError('reduce_no_initial', []);
1402 var receiver = %GetDefaultReceiver(callback);
1403 var stepping = %_DebugCallbackSupportsStepping(callback);
1404 for (; i < length; i++) {
1406 var element = array[i];
1407 // Prepare break slots for debugger step in.
1408 if (stepping) %DebugPrepareStepInIfStepping(callback);
1409 current = %_CallFunction(receiver, current, element, i, array, callback);
1415 function ArrayReduceRight(callback, current) {
1416 CHECK_OBJECT_COERCIBLE(this, "Array.prototype.reduceRight");
1418 // Pull out the length so that side effects are visible before the
1419 // callback function is checked.
1420 var array = ToObject(this);
1421 var length = ToUint32(array.length);
1423 if (!IS_SPEC_FUNCTION(callback)) {
1424 throw MakeTypeError('called_non_callable', [callback]);
1428 find_initial: if (%_ArgumentsLength() < 2) {
1429 for (; i >= 0; i--) {
1431 if (!IS_UNDEFINED(current) || i in array) {
1436 throw MakeTypeError('reduce_no_initial', []);
1439 var receiver = %GetDefaultReceiver(callback);
1440 var stepping = %_DebugCallbackSupportsStepping(callback);
1441 for (; i >= 0; i--) {
1443 var element = array[i];
1444 // Prepare break slots for debugger step in.
1445 if (stepping) %DebugPrepareStepInIfStepping(callback);
1446 current = %_CallFunction(receiver, current, element, i, array, callback);
1453 function ArrayIsArray(obj) {
1454 return IS_ARRAY(obj);
1458 // -------------------------------------------------------------------
1460 function SetUpArray() {
1461 %CheckIsBootstrapping();
1463 // Set up non-enumerable constructor property on the Array.prototype
1465 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
1467 // Set up non-enumerable functions on the Array object.
1468 InstallFunctions($Array, DONT_ENUM, $Array(
1469 "isArray", ArrayIsArray
1472 var specialFunctions = %SpecialArrayFunctions({});
1474 var getFunction = function(name, jsBuiltin, len) {
1476 if (specialFunctions.hasOwnProperty(name)) {
1477 f = specialFunctions[name];
1479 if (!IS_UNDEFINED(len)) {
1480 %FunctionSetLength(f, len);
1485 // Set up non-enumerable functions of the Array.prototype object and
1487 // Manipulate the length of some of the functions to meet
1488 // expectations set by ECMA-262 or Mozilla.
1489 InstallFunctions($Array.prototype, DONT_ENUM, $Array(
1490 "toString", getFunction("toString", ArrayToString),
1491 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString),
1492 "join", getFunction("join", ArrayJoin),
1493 "pop", getFunction("pop", ArrayPop),
1494 "push", getFunction("push", ArrayPush, 1),
1495 "concat", getFunction("concat", ArrayConcat, 1),
1496 "reverse", getFunction("reverse", ArrayReverse),
1497 "shift", getFunction("shift", ArrayShift),
1498 "unshift", getFunction("unshift", ArrayUnshift, 1),
1499 "slice", getFunction("slice", ArraySlice, 2),
1500 "splice", getFunction("splice", ArraySplice, 2),
1501 "sort", getFunction("sort", ArraySort),
1502 "filter", getFunction("filter", ArrayFilter, 1),
1503 "forEach", getFunction("forEach", ArrayForEach, 1),
1504 "some", getFunction("some", ArraySome, 1),
1505 "every", getFunction("every", ArrayEvery, 1),
1506 "map", getFunction("map", ArrayMap, 1),
1507 "indexOf", getFunction("indexOf", ArrayIndexOf, 1),
1508 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
1509 "reduce", getFunction("reduce", ArrayReduce, 1),
1510 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
1513 %FinishArrayPrototypeSetup($Array.prototype);
1515 // The internal Array prototype doesn't need to be fancy, since it's never
1516 // exposed to user code.
1517 // Adding only the functions that are actually used.
1518 SetUpLockedPrototype(InternalArray, $Array(), $Array(
1519 "concat", getFunction("concat", ArrayConcat),
1520 "indexOf", getFunction("indexOf", ArrayIndexOf),
1521 "join", getFunction("join", ArrayJoin),
1522 "pop", getFunction("pop", ArrayPop),
1523 "push", getFunction("push", ArrayPush),
1524 "splice", getFunction("splice", ArraySplice)
1527 SetUpLockedPrototype(InternalPackedArray, $Array(), $Array(
1528 "join", getFunction("join", ArrayJoin),
1529 "pop", getFunction("pop", ArrayPop),
1530 "push", getFunction("push", ArrayPush)