| // Copyright 2012 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| (function(global, utils, extrasUtils) { |
| |
| "use strict"; |
| |
| %CheckIsBootstrapping(); |
| |
| // ------------------------------------------------------------------- |
| // Imports |
| |
| var GlobalArray = global.Array; |
| var InternalArray = utils.InternalArray; |
| var ObjectToString = global.Object.prototype.toString; |
| var iteratorSymbol = utils.ImportNow("iterator_symbol"); |
| var unscopablesSymbol = utils.ImportNow("unscopables_symbol"); |
| |
| // ------------------------------------------------------------------- |
| |
| macro INVERT_NEG_ZERO(arg) |
| ((arg) + 0) |
| endmacro |
| |
| function ArraySpeciesCreate(array, length) { |
| length = INVERT_NEG_ZERO(length); |
| var constructor = %ArraySpeciesConstructor(array); |
| return new constructor(length); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function KeySortCompare(a, b) { |
| return a - b; |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function GetSortedArrayKeys(array, indices) { |
| if (IS_NUMBER(indices)) { |
| // It's an interval |
| var limit = indices; |
| var keys = new InternalArray(); |
| for (var i = 0; i < limit; ++i) { |
| var e = array[i]; |
| if (!IS_UNDEFINED(e) || i in array) { |
| keys.push(i); |
| } |
| } |
| return keys; |
| } |
| return InnerArraySort(indices, indices.length, KeySortCompare); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function SparseJoinWithSeparatorJS( |
| array, keys, length, use_locale, separator, locales, options) { |
| var keys_length = keys.length; |
| var elements = new InternalArray(keys_length * 2); |
| for (var i = 0; i < keys_length; i++) { |
| var key = keys[i]; |
| elements[i * 2] = key; |
| elements[i * 2 + 1] = ConvertToString( |
| use_locale, array[key], locales, options); |
| } |
| return %SparseJoinWithSeparator(elements, length, separator); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| // Optimized for sparse arrays if separator is ''. |
| function SparseJoin(array, keys, use_locale, locales, options) { |
| var keys_length = keys.length; |
| var elements = new InternalArray(keys_length); |
| for (var i = 0; i < keys_length; i++) { |
| elements[i] = ConvertToString(use_locale, array[keys[i]], locales, options); |
| } |
| return %StringBuilderConcat(elements, keys_length, ''); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function UseSparseVariant(array, length, is_array, touched) { |
| // Only use the sparse variant on arrays that are likely to be sparse and the |
| // number of elements touched in the operation is relatively small compared to |
| // the overall size of the array. |
| if (!is_array || length < 1000 || %HasComplexElements(array)) { |
| return false; |
| } |
| if (!%_IsSmi(length)) { |
| return true; |
| } |
| var elements_threshold = length >> 2; // No more than 75% holes |
| var estimated_elements = %EstimateNumberOfElements(array); |
| return (estimated_elements < elements_threshold) && |
| (touched > estimated_elements * 4); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function Stack() { |
| this.length = 0; |
| this.values = new InternalArray(); |
| } |
| |
| // Predeclare the instance variables on the prototype. Otherwise setting them in |
| // the constructor will leak the instance through settings on Object.prototype. |
| Stack.prototype.length = null; |
| Stack.prototype.values = null; |
| |
| function StackPush(stack, value) { |
| stack.values[stack.length++] = value; |
| } |
| |
| function StackPop(stack) { |
| stack.values[--stack.length] = null |
| } |
| |
| function StackHas(stack, v) { |
| var length = stack.length; |
| var values = stack.values; |
| for (var i = 0; i < length; i++) { |
| if (values[i] === v) return true; |
| } |
| return false; |
| } |
| |
| // Global list of arrays visited during toString, toLocaleString and |
| // join invocations. |
| var visited_arrays = new Stack(); |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function DoJoin( |
| array, length, is_array, separator, use_locale, locales, options) { |
| if (UseSparseVariant(array, length, is_array, length)) { |
| %NormalizeElements(array); |
| var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length)); |
| if (separator === '') { |
| if (keys.length === 0) return ''; |
| return SparseJoin(array, keys, use_locale, locales, options); |
| } else { |
| return SparseJoinWithSeparatorJS( |
| array, keys, length, use_locale, separator, locales, options); |
| } |
| } |
| |
| // Fast case for one-element arrays. |
| if (length === 1) { |
| return ConvertToString(use_locale, array[0], locales, options); |
| } |
| |
| // Construct an array for the elements. |
| var elements = new InternalArray(length); |
| for (var i = 0; i < length; i++) { |
| elements[i] = ConvertToString(use_locale, array[i], locales, options); |
| } |
| |
| if (separator === '') { |
| return %StringBuilderConcat(elements, length, ''); |
| } else { |
| return %StringBuilderJoin(elements, length, separator); |
| } |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function Join(array, length, separator, use_locale, locales, options) { |
| if (length === 0) return ''; |
| |
| var is_array = IS_ARRAY(array); |
| |
| if (is_array) { |
| // If the array is cyclic, return the empty string for already |
| // visited arrays. |
| if (StackHas(visited_arrays, array)) return ''; |
| StackPush(visited_arrays, array); |
| } |
| |
| // Attempt to convert the elements. |
| try { |
| return DoJoin( |
| array, length, is_array, separator, use_locale, locales, options); |
| } finally { |
| // Make sure to remove the last element of the visited array no |
| // matter what happens. |
| if (is_array) StackPop(visited_arrays); |
| } |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function ConvertToString(use_locale, x, locales, options) { |
| if (IS_NULL_OR_UNDEFINED(x)) return ''; |
| if (use_locale) { |
| if (IS_NULL_OR_UNDEFINED(locales)) { |
| return TO_STRING(x.toLocaleString()); |
| } else if (IS_NULL_OR_UNDEFINED(options)) { |
| return TO_STRING(x.toLocaleString(locales)); |
| } |
| return TO_STRING(x.toLocaleString(locales, options)); |
| } |
| |
| return TO_STRING(x); |
| } |
| |
| |
| // ------------------------------------------------------------------- |
| |
| // ecma402 #sup-array.prototype.tolocalestring |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function InnerArrayToLocaleString(array, length, locales, options) { |
| return Join(array, TO_LENGTH(length), ',', true, locales, options); |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function InnerArrayJoin(separator, array, length) { |
| if (IS_UNDEFINED(separator)) { |
| separator = ','; |
| } else { |
| separator = TO_STRING(separator); |
| } |
| |
| // Fast case for one-element arrays. |
| if (length === 1) { |
| var e = array[0]; |
| if (IS_NULL_OR_UNDEFINED(e)) return ''; |
| return TO_STRING(e); |
| } |
| |
| return Join(array, length, separator, false); |
| } |
| |
| |
| |
| |
| // Oh the humanity... don't remove the following function because js2c for some |
| // reason gets symbol minifiation wrong if it's not there. Instead of spending |
| // the time fixing js2c (which will go away when all of the internal .js runtime |
| // files are gone), just keep this work-around. |
| function ArraySliceFallback(start, end) { |
| return null; |
| } |
| |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| function InnerArraySort(array, length, comparefn) { |
| // In-place QuickSort algorithm. |
| // For short (length <= 10) arrays, insertion sort is used for efficiency. |
| |
| if (!IS_CALLABLE(comparefn)) { |
| comparefn = function (x, y) { |
| if (x === y) return 0; |
| if (%_IsSmi(x) && %_IsSmi(y)) { |
| return %SmiLexicographicCompare(x, y); |
| } |
| x = TO_STRING(x); |
| y = TO_STRING(y); |
| if (x == y) return 0; |
| else return x < y ? -1 : 1; |
| }; |
| } |
| function InsertionSort(a, from, to) { |
| for (var i = from + 1; i < to; i++) { |
| var element = a[i]; |
| for (var j = i - 1; j >= from; j--) { |
| var tmp = a[j]; |
| var order = comparefn(tmp, element); |
| if (order > 0) { |
| a[j + 1] = tmp; |
| } else { |
| break; |
| } |
| } |
| a[j + 1] = element; |
| } |
| }; |
| |
| function GetThirdIndex(a, from, to) { |
| var t_array = new InternalArray(); |
| // Use both 'from' and 'to' to determine the pivot candidates. |
| var increment = 200 + ((to - from) & 15); |
| var j = 0; |
| from += 1; |
| to -= 1; |
| for (var i = from; i < to; i += increment) { |
| t_array[j] = [i, a[i]]; |
| j++; |
| } |
| t_array.sort(function(a, b) { |
| return comparefn(a[1], b[1]); |
| }); |
| var third_index = t_array[t_array.length >> 1][0]; |
| return third_index; |
| } |
| |
| function QuickSort(a, from, to) { |
| var third_index = 0; |
| while (true) { |
| // Insertion sort is faster for short arrays. |
| if (to - from <= 10) { |
| InsertionSort(a, from, to); |
| return; |
| } |
| if (to - from > 1000) { |
| third_index = GetThirdIndex(a, from, to); |
| } else { |
| third_index = from + ((to - from) >> 1); |
| } |
| // Find a pivot as the median of first, last and middle element. |
| var v0 = a[from]; |
| var v1 = a[to - 1]; |
| var v2 = a[third_index]; |
| var c01 = comparefn(v0, v1); |
| if (c01 > 0) { |
| // v1 < v0, so swap them. |
| var tmp = v0; |
| v0 = v1; |
| v1 = tmp; |
| } // v0 <= v1. |
| var c02 = comparefn(v0, v2); |
| if (c02 >= 0) { |
| // v2 <= v0 <= v1. |
| var tmp = v0; |
| v0 = v2; |
| v2 = v1; |
| v1 = tmp; |
| } else { |
| // v0 <= v1 && v0 < v2 |
| var c12 = comparefn(v1, v2); |
| if (c12 > 0) { |
| // v0 <= v2 < v1 |
| var tmp = v1; |
| v1 = v2; |
| v2 = tmp; |
| } |
| } |
| // v0 <= v1 <= v2 |
| a[from] = v0; |
| a[to - 1] = v2; |
| var pivot = v1; |
| var low_end = from + 1; // Upper bound of elements lower than pivot. |
| var high_start = to - 1; // Lower bound of elements greater than pivot. |
| a[third_index] = a[low_end]; |
| a[low_end] = pivot; |
| |
| // From low_end to i are elements equal to pivot. |
| // From i to high_start are elements that haven't been compared yet. |
| partition: for (var i = low_end + 1; i < high_start; i++) { |
| var element = a[i]; |
| var order = comparefn(element, pivot); |
| if (order < 0) { |
| a[i] = a[low_end]; |
| a[low_end] = element; |
| low_end++; |
| } else if (order > 0) { |
| do { |
| high_start--; |
| if (high_start == i) break partition; |
| var top_elem = a[high_start]; |
| order = comparefn(top_elem, pivot); |
| } while (order > 0); |
| a[i] = a[high_start]; |
| a[high_start] = element; |
| if (order < 0) { |
| element = a[i]; |
| a[i] = a[low_end]; |
| a[low_end] = element; |
| low_end++; |
| } |
| } |
| } |
| if (to - high_start < low_end - from) { |
| QuickSort(a, high_start, to); |
| to = low_end; |
| } else { |
| QuickSort(a, from, low_end); |
| from = high_start; |
| } |
| } |
| }; |
| |
| if (length < 2) return array; |
| |
| // For compatibility with JSC, we also sort elements inherited from |
| // the prototype chain on non-Array objects. |
| // We do this by copying them to this object and sorting only |
| // own elements. This is not very efficient, but sorting with |
| // inherited elements happens very, very rarely, if at all. |
| // The specification allows "implementation dependent" behavior |
| // if an element on the prototype chain has an element that |
| // might interact with sorting. |
| // |
| // We also move all non-undefined elements to the front of the |
| // array and move the undefineds after that. Holes are removed. |
| // This happens for Array as well as non-Array objects. |
| var num_non_undefined = %PrepareElementsForSort(array, length); |
| |
| QuickSort(array, 0, num_non_undefined); |
| |
| return array; |
| } |
| |
| |
| // Set up unscopable properties on the Array.prototype object. |
| var unscopables = { |
| __proto__: null, |
| copyWithin: true, |
| entries: true, |
| fill: true, |
| find: true, |
| findIndex: true, |
| includes: true, |
| keys: true, |
| }; |
| |
| %ToFastProperties(unscopables); |
| |
| %AddNamedProperty(GlobalArray.prototype, unscopablesSymbol, unscopables, |
| DONT_ENUM | READ_ONLY); |
| |
| var ArrayIndexOf = GlobalArray.prototype.indexOf; |
| var ArrayJoin = GlobalArray.prototype.join; |
| var ArrayPop = GlobalArray.prototype.pop; |
| var ArrayPush = GlobalArray.prototype.push; |
| var ArraySlice = GlobalArray.prototype.slice; |
| var ArrayShift = GlobalArray.prototype.shift; |
| var ArraySort = GlobalArray.prototype.sort; |
| var ArraySplice = GlobalArray.prototype.splice; |
| var ArrayToString = GlobalArray.prototype.toString; |
| var ArrayUnshift = GlobalArray.prototype.unshift; |
| |
| // Array prototype functions that return iterators. They are exposed to the |
| // public API via Template::SetIntrinsicDataProperty(). |
| var ArrayEntries = GlobalArray.prototype.entries; |
| var ArrayForEach = GlobalArray.prototype.forEach; |
| var ArrayKeys = GlobalArray.prototype.keys; |
| var ArrayValues = GlobalArray.prototype[iteratorSymbol]; |
| |
| |
| // The internal Array prototype doesn't need to be fancy, since it's never |
| // exposed to user code. |
| // Adding only the functions that are actually used. |
| utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [ |
| "indexOf", ArrayIndexOf, |
| "join", ArrayJoin, |
| "pop", ArrayPop, |
| "push", ArrayPush, |
| "shift", ArrayShift, |
| "sort", ArraySort, |
| "splice", ArraySplice |
| ]); |
| |
| // V8 extras get a separate copy of InternalPackedArray. We give them the basic |
| // manipulation methods. |
| utils.SetUpLockedPrototype(extrasUtils.InternalPackedArray, GlobalArray(), [ |
| "push", ArrayPush, |
| "pop", ArrayPop, |
| "shift", ArrayShift, |
| "unshift", ArrayUnshift, |
| "splice", ArraySplice, |
| "slice", ArraySlice |
| ]); |
| |
| // ------------------------------------------------------------------- |
| // Exports |
| |
| utils.Export(function(to) { |
| to.ArrayJoin = ArrayJoin; |
| to.ArrayPush = ArrayPush; |
| to.ArrayToString = ArrayToString; |
| to.ArrayValues = ArrayValues; |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| to.InnerArrayJoin = InnerArrayJoin; |
| // TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque. |
| to.InnerArrayToLocaleString = InnerArrayToLocaleString; |
| }); |
| |
| %InstallToContext([ |
| "array_entries_iterator", ArrayEntries, |
| "array_for_each_iterator", ArrayForEach, |
| "array_keys_iterator", ArrayKeys, |
| "array_values_iterator", ArrayValues, |
| ]); |
| |
| }); |