array.js revision 402d937239b0e2fd11bf2f4fe972ad78aa9fd481
1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2006-2008 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Redistribution and use in source and binary forms, with or without 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// modification, are permitted provided that the following conditions are 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// met: 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions of source code must retain the above copyright 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// notice, this list of conditions and the following disclaimer. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions in binary form must reproduce the above 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// copyright notice, this list of conditions and the following 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// disclaimer in the documentation and/or other materials provided 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// with the distribution. 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Neither the name of Google Inc. nor the names of its 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// contributors may be used to endorse or promote products derived 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from this software without specific prior written permission. 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This file relies on the fact that the following declarations have been made 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// in runtime.js: 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// const $Array = global.Array; 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 32a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ------------------------------------------------------------------- 33a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Global list of arrays visited during toString, toLocaleString and 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// join invocations. 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar visited_arrays = new $Array(); 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Gets a sorted array of array keys. Useful for operations on sparse 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// arrays. Dupes have not been removed. 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction GetSortedArrayKeys(array, intervals) { 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = intervals.length; 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var keys = []; 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var k = 0; k < length; k++) { 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = intervals[k]; 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < 0) { 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var j = -1 - key; 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var limit = j + intervals[++k]; 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; j < limit; j++) { 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var e = array[j]; 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(e) || j in array) { 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block keys.push(j); 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The case where key is undefined also ends here. 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(key)) { 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var e = array[key]; 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(e) || key in array) { 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block keys.push(key); 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block keys.sort(function(a, b) { return a - b; }); 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return keys; 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Optimized for sparse arrays if separator is ''. 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SparseJoin(array, len, convert) { 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var last_key = -1; 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var keys_length = keys.length; 75e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke 76e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var elements = new $Array(keys_length); 77e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var elements_length = 0; 78e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < keys_length; i++) { 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = keys[i]; 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key != last_key) { 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var e = array[key]; 83e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (!IS_STRING(e)) e = convert(e); 84e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke elements[elements_length++] = e; 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block last_key = key; 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 87a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 88e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke return %StringBuilderConcat(elements, elements_length, ''); 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction UseSparseVariant(object, length, is_array) { 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return is_array && 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length > 1000 && 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block (!%_IsSmi(length) || 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block %EstimateNumberOfElements(object) < (length >> 2)); 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Join(array, length, separator, convert) { 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (length == 0) return ''; 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var is_array = IS_ARRAY(array); 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (is_array) { 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If the array is cyclic, return the empty string for already 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // visited arrays. 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!%PushIfAbsent(visited_arrays, array)) return ''; 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Attempt to convert the elements. 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block try { 113e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (UseSparseVariant(array, length, is_array) && (separator.length == 0)) { 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return SparseJoin(array, length, convert); 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Fast case for one-element arrays. 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (length == 1) { 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var e = array[0]; 120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(e) || (0 in array)) { 121e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (IS_STRING(e)) return e; 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return convert(e); 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 126e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke // Construct an array for the elements. 127e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var elements; 128e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var elements_length = 0; 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 130d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block // We pull the empty separator check outside the loop for speed! 131d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block if (separator.length == 0) { 132e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke elements = new $Array(length); 133d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block for (var i = 0; i < length; i++) { 134d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block var e = array[i]; 135d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block if (!IS_UNDEFINED(e) || (i in array)) { 136e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (!IS_STRING(e)) e = convert(e); 137e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke elements[elements_length++] = e; 138d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block } 139d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block } 140d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block } else { 141e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke elements = new $Array(length << 1); 142d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block for (var i = 0; i < length; i++) { 143d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block var e = array[i]; 144e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (i != 0) elements[elements_length++] = separator; 145d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block if (!IS_UNDEFINED(e) || (i in array)) { 146e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (!IS_STRING(e)) e = convert(e); 147e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke elements[elements_length++] = e; 148d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block } 149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 151e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke return %StringBuilderConcat(elements, elements_length, ''); 152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } finally { 153a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Make sure to pop the visited array no matter what happens. 154a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (is_array) visited_arrays.pop(); 155a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 156a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 157a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 158a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 159a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ConvertToString(e) { 160a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (e == null) return ''; 161a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else return ToString(e); 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ConvertToLocaleString(e) { 166e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (e == null) { 167e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke return ''; 168e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke } else { 169a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // e_obj's toLocaleString might be overwritten, check if it is a function. 170a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Call ToString if toLocaleString is not a function. 171a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // See issue 877615. 172a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var e_obj = ToObject(e); 173a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (IS_FUNCTION(e_obj.toLocaleString)) 174d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return ToString(e_obj.toLocaleString()); 175a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else 176a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return ToString(e); 177a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 178a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 179a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 180a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This function implements the optimized splice implementation that can use 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// special array operations to handle sparse arrays in a sensible fashion. 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SmartSlice(array, start_i, del_count, len, deleted_elements) { 184a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Move deleted elements to a new array (the return value from splice). 185a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Intervals array can contain keys and intervals. See comment in Concat. 186a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var intervals = %GetArrayKeys(array, start_i + del_count); 187a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = intervals.length; 188a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var k = 0; k < length; k++) { 189a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = intervals[k]; 190a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < 0) { 191a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var j = -1 - key; 192a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var interval_limit = j + intervals[++k]; 193a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (j < start_i) { 194a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block j = start_i; 195a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 196a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; j < interval_limit; j++) { 197a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // ECMA-262 15.4.4.12 line 10. The spec could also be 198a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // interpreted such that %HasLocalProperty would be the 199a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // appropriate test. We follow KJS in consulting the 200a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // prototype. 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[j]; 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || j in array) { 203a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block deleted_elements[j - start_i] = current; 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 205a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(key)) { 208a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key >= start_i) { 209a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // ECMA-262 15.4.4.12 line 10. The spec could also be 210a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // interpreted such that %HasLocalProperty would be the 211a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // appropriate test. We follow KJS in consulting the 212a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // prototype. 213a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[key]; 214a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || key in array) { 215a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block deleted_elements[key - start_i] = current; 216a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 218a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 219a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 220a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 221a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 222a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 223a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 224a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This function implements the optimized splice implementation that can use 225a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// special array operations to handle sparse arrays in a sensible fashion. 226a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SmartMove(array, start_i, del_count, len, num_additional_args) { 227a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Move data to new array. 228a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var new_array = new $Array(len - del_count + num_additional_args); 229a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var intervals = %GetArrayKeys(array, len); 230a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = intervals.length; 231a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var k = 0; k < length; k++) { 232a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = intervals[k]; 233a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < 0) { 234a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var j = -1 - key; 235a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var interval_limit = j + intervals[++k]; 236a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (j < start_i && j < interval_limit) { 237a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The spec could also be interpreted such that 238a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // %HasLocalProperty would be the appropriate test. We follow 239a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // KJS in consulting the prototype. 240a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[j]; 241a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || j in array) { 242a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new_array[j] = current; 243a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 244a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block j++; 245a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 246a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block j = start_i + del_count; 247a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (j < interval_limit) { 248a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also be 249a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // interpreted such that %HasLocalProperty would be the 250a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // appropriate test. We follow KJS in consulting the 251a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // prototype. 252a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[j]; 253a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || j in array) { 254a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new_array[j - del_count + num_additional_args] = current; 255a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 256a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block j++; 257a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 258a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 259a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(key)) { 260a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < start_i) { 261a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The spec could also be interpreted such that 262a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // %HasLocalProperty would be the appropriate test. We follow 263a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // KJS in consulting the prototype. 264a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[key]; 265a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || key in array) { 266a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new_array[key] = current; 267a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 268a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else if (key >= start_i + del_count) { 269a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also 270a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // be interpreted such that %HasLocalProperty would be the 271a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // appropriate test. We follow KJS in consulting the 272a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // prototype. 273a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[key]; 274a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || key in array) { 275a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new_array[key - del_count + num_additional_args] = current; 276a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 277a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 278a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 279a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 280a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 281a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Move contents of new_array into this array 282a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block %MoveArrayContents(new_array, array); 283a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 284a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 285a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 286a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This is part of the old simple-minded splice. We are using it either 287a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// because the receiver is not an array (so we have no choice) or because we 288a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// know we are not deleting or moving a lot of elements. 289a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SimpleSlice(array, start_i, del_count, len, deleted_elements) { 290a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < del_count; i++) { 291a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var index = start_i + i; 292a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The spec could also be interpreted such that %HasLocalProperty 293a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // would be the appropriate test. We follow KJS in consulting the 294a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // prototype. 295a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[index]; 296a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || index in array) 297a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block deleted_elements[i] = current; 298a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 299a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 300a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 301a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 302a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SimpleMove(array, start_i, del_count, len, num_additional_args) { 303a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_additional_args !== del_count) { 304a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Move the existing elements after the elements to be deleted 305a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // to the right position in the resulting array. 306a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_additional_args > del_count) { 307a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = len - del_count; i > start_i; i--) { 308a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var from_index = i + del_count - 1; 309a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var to_index = i + num_additional_args - 1; 310a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The spec could also be interpreted such that 311a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // %HasLocalProperty would be the appropriate test. We follow 312a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // KJS in consulting the prototype. 313a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[from_index]; 314a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || from_index in array) { 315a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[to_index] = current; 316a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 317a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete array[to_index]; 318a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 319a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 320a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 321a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = start_i; i < len - del_count; i++) { 322a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var from_index = i + del_count; 323a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var to_index = i + num_additional_args; 324a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The spec could also be interpreted such that 325a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // %HasLocalProperty would be the appropriate test. We follow 326a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // KJS in consulting the prototype. 327a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = array[from_index]; 328a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || from_index in array) { 329a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[to_index] = current; 330a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 331a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete array[to_index]; 332a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 333a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 334a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = len; i > len - del_count + num_additional_args; i--) { 335a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete array[i - 1]; 336a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 341a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 342a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ------------------------------------------------------------------- 343a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 344a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 345a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayToString() { 346a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_ARRAY(this)) { 347a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw new $TypeError('Array.prototype.toString is not generic'); 348a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 349a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Join(this, this.length, ',', ConvertToString); 350a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 351a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 352a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 353a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayToLocaleString() { 354a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_ARRAY(this)) { 355a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw new $TypeError('Array.prototype.toString is not generic'); 356a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 357a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Join(this, this.length, ',', ConvertToLocaleString); 358a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 359a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 360a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 361a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayJoin(separator) { 362e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke if (IS_UNDEFINED(separator)) { 363e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke separator = ','; 364e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke } else if (!IS_STRING(separator)) { 365e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke separator = ToString(separator); 366e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke } 367e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var length = TO_UINT32(this.length); 368e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke return Join(this, length, separator, ConvertToString); 369a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 370a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 371a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 372a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Removes the last element from the array and returns it. See 373a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ECMA-262, section 15.4.4.6. 374a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayPop() { 375e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var n = TO_UINT32(this.length); 376a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (n == 0) { 377a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = n; 378a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 379a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 380a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block n--; 381a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var value = this[n]; 382a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = n; 383a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete this[n]; 384a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return value; 385a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 386a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 387a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 388a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Appends the arguments to the end of the array and returns the new 389a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// length of the array. See ECMA-262, section 15.4.4.7. 390a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayPush() { 391e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var n = TO_UINT32(this.length); 392a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var m = %_ArgumentsLength(); 393a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < m; i++) { 394a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[i+n] = %_Arguments(i); 395a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 396a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = n + m; 397a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.length; 398a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 399a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 400a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 401a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayConcat(arg1) { // length == 1 402a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // TODO: can we just use arguments? 403a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var arg_count = %_ArgumentsLength(); 404a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var arrays = new $Array(1 + arg_count); 405a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block arrays[0] = this; 406a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < arg_count; i++) { 407a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block arrays[i + 1] = %_Arguments(i); 408a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 409a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 410a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return %ArrayConcat(arrays); 411a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 412a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 413a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 414a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// For implementing reverse() on large, sparse arrays. 415a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SparseReverse(array, len) { 416a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); 417a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var high_counter = keys.length - 1; 418a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var low_counter = 0; 419a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (low_counter <= high_counter) { 420a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i = keys[low_counter]; 421a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var j = keys[high_counter]; 422a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 423a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var j_complement = len - j - 1; 424a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var low, high; 425a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 426a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (j_complement <= i) { 427a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block high = j; 428a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (keys[--high_counter] == j); 429a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block low = j_complement; 430a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 431a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (j_complement >= i) { 432a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block low = i; 433a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (keys[++low_counter] == i); 434a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block high = len - i - 1; 435a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 436a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 437a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_i = array[low]; 438a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_i) || low in array) { 439a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_j = array[high]; 440a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_j) || high in array) { 441a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[low] = current_j; 442a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[high] = current_i; 443a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 444a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[high] = current_i; 445a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete array[low]; 446a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 447a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 448a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_j = array[high]; 449a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_j) || high in array) { 450a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array[low] = current_j; 451a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete array[high]; 452a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 453a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 454a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 455a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 456a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 457a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 458a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayReverse() { 459e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var j = TO_UINT32(this.length) - 1; 460a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 461a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (UseSparseVariant(this, j, IS_ARRAY(this))) { 462a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SparseReverse(this, j+1); 463a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this; 464a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 465a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 466a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < j; i++, j--) { 467a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_i = this[i]; 468a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_i) || i in this) { 469a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_j = this[j]; 470a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_j) || j in this) { 471a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[i] = current_j; 472a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[j] = current_i; 473a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 474a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[j] = current_i; 475a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete this[i]; 476a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 477a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 478a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current_j = this[j]; 479a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current_j) || j in this) { 480a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[i] = current_j; 481a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete this[j]; 482a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 483a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 484a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 485a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this; 486a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 487a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 488a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 489a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayShift() { 490e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var len = TO_UINT32(this.length); 491a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 492a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (len === 0) { 493a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = 0; 494a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 495a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 496a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 497a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var first = this[0]; 498a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 499a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (IS_ARRAY(this)) 500a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SmartMove(this, 0, 1, len, 0); 501a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else 502a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SimpleMove(this, 0, 1, len, 0); 503a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 504a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = len - 1; 505a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 506a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return first; 507a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 508a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 509a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 510a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayUnshift(arg1) { // length == 1 511e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var len = TO_UINT32(this.length); 512a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var num_arguments = %_ArgumentsLength(); 513a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 514a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (IS_ARRAY(this)) 515a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SmartMove(this, 0, 0, len, num_arguments); 516a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else 517a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SimpleMove(this, 0, 0, len, num_arguments); 518a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 519a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < num_arguments; i++) { 520a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[i] = %_Arguments(i); 521a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 522a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 523a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = len + num_arguments; 524a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 525a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return len + num_arguments; 526a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 527a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 528a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 529a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArraySlice(start, end) { 530e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var len = TO_UINT32(this.length); 531a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var start_i = TO_INTEGER(start); 532a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var end_i = len; 533a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 534a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (end !== void 0) end_i = TO_INTEGER(end); 535a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 536a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i < 0) { 537a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block start_i += len; 538a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i < 0) start_i = 0; 539a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 540a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i > len) start_i = len; 541a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 542a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 543a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (end_i < 0) { 544a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block end_i += len; 545a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (end_i < 0) end_i = 0; 546a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 547a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (end_i > len) end_i = len; 548a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 549a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 550a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var result = []; 551a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 552a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (end_i < start_i) return result; 553a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 554a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (IS_ARRAY(this)) { 555a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SmartSlice(this, start_i, end_i - start_i, len, result); 556a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 557a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SimpleSlice(this, start_i, end_i - start_i, len, result); 558a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 559a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 560a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block result.length = end_i - start_i; 561a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 562a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return result; 563a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 564a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 565a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 566a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArraySplice(start, delete_count) { 567a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var num_arguments = %_ArgumentsLength(); 568a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 569402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu // SpiderMonkey and JSC return undefined in the case where no 570a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // arguments are given instead of using the implicit undefined 571a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // arguments. This does not follow ECMA-262, but we do the same for 572a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // compatibility. 573402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu // TraceMonkey follows ECMA-262 though. 574a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_arguments == 0) return; 575a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 576e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var len = TO_UINT32(this.length); 577a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var start_i = TO_INTEGER(start); 578a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 579a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i < 0) { 580a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block start_i += len; 581a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i < 0) start_i = 0; 582a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 583a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (start_i > len) start_i = len; 584a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 585a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 586402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is 587a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // given differently from when an undefined delete count is given. 588a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // This does not follow ECMA-262, but we do the same for 589a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // compatibility. 590a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var del_count = 0; 591a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_arguments > 1) { 592a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block del_count = TO_INTEGER(delete_count); 593a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (del_count < 0) del_count = 0; 594a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (del_count > len - start_i) del_count = len - start_i; 595a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 596a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block del_count = len - start_i; 597a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 598a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 599a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var deleted_elements = []; 600a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block deleted_elements.length = del_count; 601a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 602a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Number of elements to add. 603a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var num_additional_args = 0; 604a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_arguments > 2) { 605a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block num_additional_args = num_arguments - 2; 606a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 607a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 608a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var use_simple_splice = true; 609a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 610a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (IS_ARRAY(this) && num_additional_args !== del_count) { 611a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If we are only deleting/moving a few things near the end of the 612a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // array then the simple version is going to be faster, because it 613a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // doesn't touch most of the array. 614a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var estimated_non_hole_elements = %EstimateNumberOfElements(this); 615a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) { 616a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block use_simple_splice = false; 617a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 618a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 619a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 620a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (use_simple_splice) { 621a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SimpleSlice(this, start_i, del_count, len, deleted_elements); 622a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SimpleMove(this, start_i, del_count, len, num_additional_args); 623a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 624a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SmartSlice(this, start_i, del_count, len, deleted_elements); 625a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block SmartMove(this, start_i, del_count, len, num_additional_args); 626a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 627a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 628a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Insert the arguments into the resulting array in 629a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // place of the deleted elements. 630a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i = start_i; 631a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var arguments_index = 2; 632a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var arguments_length = %_ArgumentsLength(); 633a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (arguments_index < arguments_length) { 634a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this[i++] = %_Arguments(arguments_index++); 635a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 636a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.length = len - del_count + num_additional_args; 637a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 638a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Return the deleted elements. 639a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return deleted_elements; 640a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 641a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 642a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 643a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArraySort(comparefn) { 644a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // In-place QuickSort algorithm. 645a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // For short (length <= 22) arrays, insertion sort is used for efficiency. 646a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 647a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var custom_compare = IS_FUNCTION(comparefn); 648a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 649a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function Compare(x,y) { 650a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Assume the comparefn, if any, is a consistent comparison function. 651a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11. 652a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (x === y) return 0; 653a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (custom_compare) { 654a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Don't call directly to avoid exposing the builtin's global object. 655a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return comparefn.call(null, x, y); 656a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 657a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (%_IsSmi(x) && %_IsSmi(y)) { 658a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return %SmiLexicographicCompare(x, y); 659a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 660a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block x = ToString(x); 661a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block y = ToString(y); 662a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (x == y) return 0; 663a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else return x < y ? -1 : 1; 664a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block }; 665a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 666a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function InsertionSort(a, from, to) { 667a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = from + 1; i < to; i++) { 668a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var element = a[i]; 669a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pre-convert the element to a string for comparison if we know 670a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // it will happen on each compare anyway. 671a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = 672a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block (custom_compare || %_IsSmi(element)) ? element : ToString(element); 673a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // place element in a[from..i[ 674a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // binary search 675a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var min = from; 676a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var max = i; 677a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The search interval is a[min..max[ 678a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (min < max) { 679a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var mid = min + ((max - min) >> 1); 680a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var order = Compare(a[mid], key); 681a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (order == 0) { 682a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block min = max = mid; 683a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 684a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 685a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (order < 0) { 686a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block min = mid + 1; 687a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 688a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block max = mid; 689a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 690a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 691a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // place element at position min==max. 692a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var j = i; j > min; j--) { 693a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[j] = a[j - 1]; 694a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 695a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[min] = element; 696a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 697a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 698a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 699a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function QuickSort(a, from, to) { 700a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Insertion sort is faster for short arrays. 701a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (to - from <= 22) { 702a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block InsertionSort(a, from, to); 703a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 704a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 705a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var pivot_index = $floor($random() * (to - from)) + from; 706a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var pivot = a[pivot_index]; 707a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pre-convert the element to a string for comparison if we know 708a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // it will happen on each compare anyway. 709a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var pivot_key = 710a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); 711a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Issue 95: Keep the pivot element out of the comparisons to avoid 712a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // infinite recursion if comparefn(pivot, pivot) != 0. 713a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[pivot_index] = a[from]; 714a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[from] = pivot; 715a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var low_end = from; // Upper bound of the elements lower than pivot. 716a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var high_start = to; // Lower bound of the elements greater than pivot. 717a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // From low_end to i are elements equal to pivot. 718a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // From i to high_start are elements that haven't been compared yet. 719a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = from + 1; i < high_start; ) { 720a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var element = a[i]; 721a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var order = Compare(element, pivot_key); 722a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (order < 0) { 723a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[i] = a[low_end]; 724a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[low_end] = element; 725a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block i++; 726a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block low_end++; 727a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else if (order > 0) { 728a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block high_start--; 729a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[i] = a[high_start]; 730a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block a[high_start] = element; 731a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { // order == 0 732a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block i++; 733a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 734a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 735a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block QuickSort(a, from, low_end); 736a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block QuickSort(a, high_start, to); 737a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 738a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 739a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length; 740a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 741a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Copies elements in the range 0..length from obj's prototype chain 742a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // to obj itself, if obj has holes. Returns one more than the maximal index 743a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // of a prototype property. 744a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function CopyFromPrototype(obj, length) { 745a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var max = 0; 746a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var proto = obj.__proto__; proto; proto = proto.__proto__) { 747a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var indices = %GetArrayKeys(proto, length); 748a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (indices.length > 0) { 749a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (indices[0] == -1) { 750a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // It's an interval. 751a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var proto_length = indices[1]; 752a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < proto_length; i++) { 753a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { 754a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[i] = proto[i]; 755a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (i >= max) { max = i + 1; } 756a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 757a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 758a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 759a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < indices.length; i++) { 760a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var index = indices[i]; 761a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(index) && 762a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { 763a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[index] = proto[index]; 764a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index >= max) { max = index + 1; } 765a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 766a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 767a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 768a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 769a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 770a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return max; 771a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 772a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 773a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Set a value of "undefined" on all indices in the range from..to 774a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // where a prototype of obj has an element. I.e., shadow all prototype 775a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // elements in that range. 776a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function ShadowPrototypeElements(obj, from, to) { 777a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var proto = obj.__proto__; proto; proto = proto.__proto__) { 778a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var indices = %GetArrayKeys(proto, to); 779a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (indices.length > 0) { 780a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (indices[0] == -1) { 781a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // It's an interval. 782a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var proto_length = indices[1]; 783a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = from; i < proto_length; i++) { 784a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (proto.hasOwnProperty(i)) { 785a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[i] = void 0; 786a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 787a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 788a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 789a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < indices.length; i++) { 790a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var index = indices[i]; 791a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(index) && from <= index && 792a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block proto.hasOwnProperty(index)) { 793a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[index] = void 0; 794a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 795a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 796a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 797a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 798a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 799a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 800a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 801a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function SafeRemoveArrayHoles(obj) { 802a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Copy defined elements from the end to fill in all holes and undefineds 803a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // in the beginning of the array. Write undefineds and holes at the end 804a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // after loop is finished. 805a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var first_undefined = 0; 806a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var last_defined = length - 1; 807a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var num_holes = 0; 808a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (first_undefined < last_defined) { 809a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Find first undefined element. 810a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (first_undefined < last_defined && 811a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block !IS_UNDEFINED(obj[first_undefined])) { 812a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block first_undefined++; 813a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 814a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Maintain the invariant num_holes = the number of holes in the original 815a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // array with indices <= first_undefined or > last_defined. 816a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!obj.hasOwnProperty(first_undefined)) { 817a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block num_holes++; 818a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 819a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 820a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Find last defined element. 821a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (first_undefined < last_defined && 822a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block IS_UNDEFINED(obj[last_defined])) { 823a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!obj.hasOwnProperty(last_defined)) { 824a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block num_holes++; 825a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 826a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block last_defined--; 827a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 828a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (first_undefined < last_defined) { 829a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Fill in hole or undefined. 830a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[first_undefined] = obj[last_defined]; 831a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[last_defined] = void 0; 832a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 833a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 834a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If there were any undefineds in the entire array, first_undefined 835a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // points to one past the last defined element. Make this true if 836a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // there were no undefineds, as well, so that first_undefined == number 837a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // of defined elements. 838a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++; 839a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Fill in the undefineds and the holes. There may be a hole where 840a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // an undefined should be and vice versa. 841a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i; 842a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (i = first_undefined; i < length - num_holes; i++) { 843a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[i] = void 0; 844a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 845a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (i = length - num_holes; i < length; i++) { 846a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // For compatability with Webkit, do not expose elements in the prototype. 847a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (i in obj.__proto__) { 848a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block obj[i] = void 0; 849a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 850a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block delete obj[i]; 851a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 852a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 853a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 854a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Return the number of defined elements. 855a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return first_undefined; 856a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 857a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 858e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke length = TO_UINT32(this.length); 859a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (length < 2) return this; 860a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 861a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var is_array = IS_ARRAY(this); 862a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var max_prototype_element; 863a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!is_array) { 864a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // For compatibility with JSC, we also sort elements inherited from 865a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // the prototype chain on non-Array objects. 866a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // We do this by copying them to this object and sorting only 867a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // local elements. This is not very efficient, but sorting with 868a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // inherited elements happens very, very rarely, if at all. 869a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The specification allows "implementation dependent" behavior 870a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // if an element on the prototype chain has an element that 871a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // might interact with sorting. 872a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block max_prototype_element = CopyFromPrototype(this, length); 873a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 874a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 875a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var num_non_undefined = %RemoveArrayHoles(this, length); 876a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (num_non_undefined == -1) { 877a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // There were indexed accessors in the array. Move array holes and 878a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // undefineds to the end using a Javascript function that is safe 879a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // in the presence of accessors. 880a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block num_non_undefined = SafeRemoveArrayHoles(this); 881a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 882a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 883a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block QuickSort(this, 0, num_non_undefined); 884a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 885a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!is_array && (num_non_undefined + 1 < max_prototype_element)) { 886a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // For compatibility with JSC, we shadow any elements in the prototype 887a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // chain that has become exposed by sort moving a hole to its position. 888a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ShadowPrototypeElements(this, num_non_undefined, max_prototype_element); 889a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 890a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 891a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this; 892a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 893a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 894a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 895a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// The following functions cannot be made efficient on sparse arrays while 896a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// preserving the semantics, since the calls to the receiver function can add 897a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// or delete elements from the array. 898a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayFilter(f, receiver) { 899a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(f)) { 900a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [ f ]); 901a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 902a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 903a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 904a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = this.length; 905a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var result = []; 906a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var result_length = 0; 907a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length; i++) { 908a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 909a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 910a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (f.call(receiver, current, i, this)) result[result_length++] = current; 911a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 912a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 913a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return result; 914a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 915a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 916a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 917a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayForEach(f, receiver) { 918a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(f)) { 919a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [ f ]); 920a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 921a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 922a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 923e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var length = TO_UINT32(this.length); 924a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length; i++) { 925a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 926a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 927a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block f.call(receiver, current, i, this); 928a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 929a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 930a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 931a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 932a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 933a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Executes the function once for each element present in the 934a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// array until it finds one where callback returns true. 935a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArraySome(f, receiver) { 936a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(f)) { 937a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [ f ]); 938a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 939a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 940a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 941e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var length = TO_UINT32(this.length); 942a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length; i++) { 943a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 944a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 945a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (f.call(receiver, current, i, this)) return true; 946a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 947a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 948a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return false; 949a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 950a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 951a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 952a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayEvery(f, receiver) { 953a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(f)) { 954a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [ f ]); 955a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 956a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 957a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 958e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var length = TO_UINT32(this.length); 959a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length; i++) { 960a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 961a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 962a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!f.call(receiver, current, i, this)) return false; 963a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 964a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 965a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return true; 966a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 967a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 968a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayMap(f, receiver) { 969a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(f)) { 970a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [ f ]); 971a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 972a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 973a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 974e46be819fca9468a0cd4e74859ce0f778eb8ca60Leon Clarke var length = TO_UINT32(this.length); 975a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var result = new $Array(length); 976a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length; i++) { 977a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 978a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 979a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block result[i] = f.call(receiver, current, i, this); 980a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 981a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 982a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return result; 983a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 984a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 985a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 986a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayIndexOf(element, index) { 987a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = this.length; 988a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index == null) { 989a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block index = 0; 990a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 991a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block index = TO_INTEGER(index); 992a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If index is negative, index from the end of the array. 993a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index < 0) index = length + index; 994a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If index is still negative, search the entire array. 995a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index < 0) index = 0; 996a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 997a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Lookup through the array. 998a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = index; i < length; i++) { 999a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 1000a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 1001a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (current === element) return i; 1002a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1003a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1004a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return -1; 1005a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1006a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1007a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1008a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayLastIndexOf(element, index) { 1009a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = this.length; 1010a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index == null) { 1011a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block index = length - 1; 1012a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 1013a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block index = TO_INTEGER(index); 1014a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If index is negative, index from end of the array. 1015a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index < 0) index = length + index; 1016a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If index is still negative, do not search the array. 1017a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (index < 0) index = -1; 1018a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else if (index >= length) index = length - 1; 1019a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1020a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Lookup through the array. 1021a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = index; i >= 0; i--) { 1022a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this[i]; 1023a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 1024a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (current === element) return i; 1025a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1026a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1027a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return -1; 1028a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1029a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1030a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1031a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayReduce(callback, current) { 1032a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(callback)) { 1033a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [callback]); 1034a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1035a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Pull out the length so that modifications to the length in the 1036a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // loop will not affect the looping. 1037a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = this.length; 1038a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i = 0; 1039a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1040a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block find_initial: if (%_ArgumentsLength() < 2) { 1041a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; i < length; i++) { 1042a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = this[i]; 1043a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 1044a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block i++; 1045a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break find_initial; 1046a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1047a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1048a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('reduce_no_initial', []); 1049a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1050a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1051a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; i < length; i++) { 1052a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var element = this[i]; 1053a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(element) || i in this) { 1054a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = callback.call(null, current, element, i, this); 1055a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1056a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1057a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return current; 1058a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1059a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1060a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ArrayReduceRight(callback, current) { 1061a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_FUNCTION(callback)) { 1062a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('called_non_callable', [callback]); 1063a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1064a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i = this.length - 1; 1065a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1066a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block find_initial: if (%_ArgumentsLength() < 2) { 1067a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; i >= 0; i--) { 1068a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = this[i]; 1069a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(current) || i in this) { 1070a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block i--; 1071a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break find_initial; 1072a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1073a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1074a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw MakeTypeError('reduce_no_initial', []); 1075a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1076a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1077a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (; i >= 0; i--) { 1078a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var element = this[i]; 1079a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!IS_UNDEFINED(element) || i in this) { 1080a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = callback.call(null, current, element, i, this); 1081a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1082a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1083a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return current; 1084a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1085a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 10863ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block// ES5, 15.4.3.2 10873ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Blockfunction ArrayIsArray(obj) { 10883ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block return IS_ARRAY(obj); 10893ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block} 1090a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1091a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ------------------------------------------------------------------- 1092a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1093a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1094a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction UpdateFunctionLengths(lengths) { 1095a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var key in lengths) { 1096a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block %FunctionSetLength(this[key], lengths[key]); 1097a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 1098a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1099a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ------------------------------------------------------------------- 1102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SetupArray() { 1103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Setup non-enumerable constructor property on the Array.prototype 1104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // object. 1105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM); 1106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 11073ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block // Setup non-enumerable functions on the Array object. 11083ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block InstallFunctions($Array, DONT_ENUM, $Array( 11093ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block "isArray", ArrayIsArray 11103ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block )); 11113ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block 1112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Setup non-enumerable functions of the Array.prototype object and 1113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // set their names. 1114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block InstallFunctionsOnHiddenPrototype($Array.prototype, DONT_ENUM, $Array( 1115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "toString", ArrayToString, 1116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "toLocaleString", ArrayToLocaleString, 1117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "join", ArrayJoin, 1118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "pop", ArrayPop, 1119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "push", ArrayPush, 1120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "concat", ArrayConcat, 1121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "reverse", ArrayReverse, 1122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "shift", ArrayShift, 1123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "unshift", ArrayUnshift, 1124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "slice", ArraySlice, 1125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "splice", ArraySplice, 1126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "sort", ArraySort, 1127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "filter", ArrayFilter, 1128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "forEach", ArrayForEach, 1129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "some", ArraySome, 1130a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "every", ArrayEvery, 1131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "map", ArrayMap, 1132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "indexOf", ArrayIndexOf, 1133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "lastIndexOf", ArrayLastIndexOf, 1134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block "reduce", ArrayReduce, 11353ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block "reduceRight", ArrayReduceRight 11363ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block )); 11373ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block 1138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Manipulate the length of some of the functions to meet 1139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // expectations set by ECMA-262 or Mozilla. 1140a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block UpdateFunctionLengths({ 1141a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayFilter: 1, 1142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayForEach: 1, 1143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArraySome: 1, 1144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayEvery: 1, 1145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayMap: 1, 1146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayIndexOf: 1, 1147a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayLastIndexOf: 1, 1148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayPush: 1, 1149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayReduce: 1, 1150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ArrayReduceRight: 1 1151a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block }); 1152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1153a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1154a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1155a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSetupArray(); 1156