Move V8 to external/v8
Change-Id: If68025d67453785a651c5dfb34fad298c16676a4
diff --git a/src/array.js b/src/array.js
new file mode 100644
index 0000000..f8e63d0
--- /dev/null
+++ b/src/array.js
@@ -0,0 +1,1120 @@
+// Copyright 2006-2008 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// This file relies on the fact that the following declarations have been made
+// in runtime.js:
+// const $Array = global.Array;
+
+// -------------------------------------------------------------------
+
+// Global list of arrays visited during toString, toLocaleString and
+// join invocations.
+var visited_arrays = new $Array();
+
+
+// Gets a sorted array of array keys. Useful for operations on sparse
+// arrays. Dupes have not been removed.
+function GetSortedArrayKeys(array, intervals) {
+ var length = intervals.length;
+ var keys = [];
+ for (var k = 0; k < length; k++) {
+ var key = intervals[k];
+ if (key < 0) {
+ var j = -1 - key;
+ var limit = j + intervals[++k];
+ for (; j < limit; j++) {
+ var e = array[j];
+ if (!IS_UNDEFINED(e) || j in array) {
+ keys.push(j);
+ }
+ }
+ } else {
+ // The case where key is undefined also ends here.
+ if (!IS_UNDEFINED(key)) {
+ var e = array[key];
+ if (!IS_UNDEFINED(e) || key in array) {
+ keys.push(key);
+ }
+ }
+ }
+ }
+ keys.sort(function(a, b) { return a - b; });
+ return keys;
+}
+
+
+// Optimized for sparse arrays if separator is ''.
+function SparseJoin(array, len, convert) {
+ var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
+ var builder = new StringBuilder();
+ var last_key = -1;
+ var keys_length = keys.length;
+ for (var i = 0; i < keys_length; i++) {
+ var key = keys[i];
+ if (key != last_key) {
+ var e = array[key];
+ builder.add(convert(e));
+ last_key = key;
+ }
+ }
+ return builder.generate();
+}
+
+
+function UseSparseVariant(object, length, is_array) {
+ return is_array &&
+ length > 1000 &&
+ (!%_IsSmi(length) ||
+ %EstimateNumberOfElements(object) < (length >> 2));
+}
+
+
+function Join(array, length, separator, convert) {
+ 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 (!%PushIfAbsent(visited_arrays, array)) return '';
+ }
+
+ // Attempt to convert the elements.
+ try {
+ if (UseSparseVariant(array, length, is_array) && separator === '') {
+ return SparseJoin(array, length, convert);
+ }
+
+ // Fast case for one-element arrays.
+ if (length == 1) {
+ var e = array[0];
+ if (!IS_UNDEFINED(e) || (0 in array)) {
+ return convert(e);
+ }
+ }
+
+ var builder = new StringBuilder();
+
+ for (var i = 0; i < length; i++) {
+ var e = array[i];
+ if (i != 0) builder.add(separator);
+ if (!IS_UNDEFINED(e) || (i in array)) {
+ builder.add(convert(e));
+ }
+ }
+ return builder.generate();
+ } finally {
+ // Make sure to pop the visited array no matter what happens.
+ if (is_array) visited_arrays.pop();
+ }
+}
+
+
+function ConvertToString(e) {
+ if (e == null) return '';
+ else return ToString(e);
+}
+
+
+function ConvertToLocaleString(e) {
+ if (e == null) return '';
+ else {
+ // e_obj's toLocaleString might be overwritten, check if it is a function.
+ // Call ToString if toLocaleString is not a function.
+ // See issue 877615.
+ var e_obj = ToObject(e);
+ if (IS_FUNCTION(e_obj.toLocaleString))
+ return e_obj.toLocaleString();
+ else
+ return ToString(e);
+ }
+}
+
+
+// This function implements the optimized splice implementation that can use
+// special array operations to handle sparse arrays in a sensible fashion.
+function SmartSlice(array, start_i, del_count, len, deleted_elements) {
+ // Move deleted elements to a new array (the return value from splice).
+ // Intervals array can contain keys and intervals. See comment in Concat.
+ var intervals = %GetArrayKeys(array, start_i + del_count);
+ var length = intervals.length;
+ for (var k = 0; k < length; k++) {
+ var key = intervals[k];
+ if (key < 0) {
+ var j = -1 - key;
+ var interval_limit = j + intervals[++k];
+ if (j < start_i) {
+ j = start_i;
+ }
+ for (; j < interval_limit; j++) {
+ // ECMA-262 15.4.4.12 line 10. The spec could also be
+ // interpreted such that %HasLocalProperty would be the
+ // appropriate test. We follow KJS in consulting the
+ // prototype.
+ var current = array[j];
+ if (!IS_UNDEFINED(current) || j in array) {
+ deleted_elements[j - start_i] = current;
+ }
+ }
+ } else {
+ if (!IS_UNDEFINED(key)) {
+ if (key >= start_i) {
+ // ECMA-262 15.4.4.12 line 10. The spec could also be
+ // interpreted such that %HasLocalProperty would be the
+ // appropriate test. We follow KJS in consulting the
+ // prototype.
+ var current = array[key];
+ if (!IS_UNDEFINED(current) || key in array) {
+ deleted_elements[key - start_i] = current;
+ }
+ }
+ }
+ }
+ }
+}
+
+
+// This function implements the optimized splice implementation that can use
+// special array operations to handle sparse arrays in a sensible fashion.
+function SmartMove(array, start_i, del_count, len, num_additional_args) {
+ // Move data to new array.
+ var new_array = new $Array(len - del_count + num_additional_args);
+ var intervals = %GetArrayKeys(array, len);
+ var length = intervals.length;
+ for (var k = 0; k < length; k++) {
+ var key = intervals[k];
+ if (key < 0) {
+ var j = -1 - key;
+ var interval_limit = j + intervals[++k];
+ while (j < start_i && j < interval_limit) {
+ // The spec could also be interpreted such that
+ // %HasLocalProperty would be the appropriate test. We follow
+ // KJS in consulting the prototype.
+ var current = array[j];
+ if (!IS_UNDEFINED(current) || j in array) {
+ new_array[j] = current;
+ }
+ j++;
+ }
+ j = start_i + del_count;
+ while (j < interval_limit) {
+ // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also be
+ // interpreted such that %HasLocalProperty would be the
+ // appropriate test. We follow KJS in consulting the
+ // prototype.
+ var current = array[j];
+ if (!IS_UNDEFINED(current) || j in array) {
+ new_array[j - del_count + num_additional_args] = current;
+ }
+ j++;
+ }
+ } else {
+ if (!IS_UNDEFINED(key)) {
+ if (key < start_i) {
+ // The spec could also be interpreted such that
+ // %HasLocalProperty would be the appropriate test. We follow
+ // KJS in consulting the prototype.
+ var current = array[key];
+ if (!IS_UNDEFINED(current) || key in array) {
+ new_array[key] = current;
+ }
+ } else if (key >= start_i + del_count) {
+ // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also
+ // be interpreted such that %HasLocalProperty would be the
+ // appropriate test. We follow KJS in consulting the
+ // prototype.
+ var current = array[key];
+ if (!IS_UNDEFINED(current) || key in array) {
+ new_array[key - del_count + num_additional_args] = current;
+ }
+ }
+ }
+ }
+ }
+ // Move contents of new_array into this array
+ %MoveArrayContents(new_array, array);
+}
+
+
+// This is part of the old simple-minded splice. We are using it either
+// because the receiver is not an array (so we have no choice) or because we
+// know we are not deleting or moving a lot of elements.
+function SimpleSlice(array, start_i, del_count, len, deleted_elements) {
+ for (var i = 0; i < del_count; i++) {
+ var index = start_i + i;
+ // The spec could also be interpreted such that %HasLocalProperty
+ // would be the appropriate test. We follow KJS in consulting the
+ // prototype.
+ var current = array[index];
+ if (!IS_UNDEFINED(current) || index in array)
+ deleted_elements[i] = current;
+ }
+}
+
+
+function SimpleMove(array, start_i, del_count, len, num_additional_args) {
+ if (num_additional_args !== del_count) {
+ // Move the existing elements after the elements to be deleted
+ // to the right position in the resulting array.
+ if (num_additional_args > del_count) {
+ for (var i = len - del_count; i > start_i; i--) {
+ var from_index = i + del_count - 1;
+ var to_index = i + num_additional_args - 1;
+ // The spec could also be interpreted such that
+ // %HasLocalProperty would be the appropriate test. We follow
+ // KJS in consulting the prototype.
+ var current = array[from_index];
+ if (!IS_UNDEFINED(current) || from_index in array) {
+ array[to_index] = current;
+ } else {
+ delete array[to_index];
+ }
+ }
+ } else {
+ for (var i = start_i; i < len - del_count; i++) {
+ var from_index = i + del_count;
+ var to_index = i + num_additional_args;
+ // The spec could also be interpreted such that
+ // %HasLocalProperty would be the appropriate test. We follow
+ // KJS in consulting the prototype.
+ var current = array[from_index];
+ if (!IS_UNDEFINED(current) || from_index in array) {
+ array[to_index] = current;
+ } else {
+ delete array[to_index];
+ }
+ }
+ for (var i = len; i > len - del_count + num_additional_args; i--) {
+ delete array[i - 1];
+ }
+ }
+ }
+}
+
+
+// -------------------------------------------------------------------
+
+
+function ArrayToString() {
+ if (!IS_ARRAY(this)) {
+ throw new $TypeError('Array.prototype.toString is not generic');
+ }
+ return Join(this, this.length, ',', ConvertToString);
+}
+
+
+function ArrayToLocaleString() {
+ if (!IS_ARRAY(this)) {
+ throw new $TypeError('Array.prototype.toString is not generic');
+ }
+ return Join(this, this.length, ',', ConvertToLocaleString);
+}
+
+
+function ArrayJoin(separator) {
+ if (IS_UNDEFINED(separator)) separator = ',';
+ else separator = ToString(separator);
+ return Join(this, ToUint32(this.length), separator, ConvertToString);
+}
+
+
+// Removes the last element from the array and returns it. See
+// ECMA-262, section 15.4.4.6.
+function ArrayPop() {
+ var n = ToUint32(this.length);
+ if (n == 0) {
+ this.length = n;
+ return;
+ }
+ n--;
+ var value = this[n];
+ this.length = n;
+ delete this[n];
+ return value;
+}
+
+
+// Appends the arguments to the end of the array and returns the new
+// length of the array. See ECMA-262, section 15.4.4.7.
+function ArrayPush() {
+ var n = ToUint32(this.length);
+ var m = %_ArgumentsLength();
+ for (var i = 0; i < m; i++) {
+ this[i+n] = %_Arguments(i);
+ }
+ this.length = n + m;
+ return this.length;
+}
+
+
+function ArrayConcat(arg1) { // length == 1
+ // TODO: can we just use arguments?
+ var arg_count = %_ArgumentsLength();
+ var arrays = new $Array(1 + arg_count);
+ arrays[0] = this;
+ for (var i = 0; i < arg_count; i++) {
+ arrays[i + 1] = %_Arguments(i);
+ }
+
+ return %ArrayConcat(arrays);
+}
+
+
+// For implementing reverse() on large, sparse arrays.
+function SparseReverse(array, len) {
+ var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
+ var high_counter = keys.length - 1;
+ var low_counter = 0;
+ while (low_counter <= high_counter) {
+ var i = keys[low_counter];
+ var j = keys[high_counter];
+
+ var j_complement = len - j - 1;
+ var low, high;
+
+ if (j_complement <= i) {
+ high = j;
+ while (keys[--high_counter] == j);
+ low = j_complement;
+ }
+ if (j_complement >= i) {
+ low = i;
+ while (keys[++low_counter] == i);
+ high = len - i - 1;
+ }
+
+ var current_i = array[low];
+ if (!IS_UNDEFINED(current_i) || low in array) {
+ var current_j = array[high];
+ if (!IS_UNDEFINED(current_j) || high in array) {
+ array[low] = current_j;
+ array[high] = current_i;
+ } else {
+ array[high] = current_i;
+ delete array[low];
+ }
+ } else {
+ var current_j = array[high];
+ if (!IS_UNDEFINED(current_j) || high in array) {
+ array[low] = current_j;
+ delete array[high];
+ }
+ }
+ }
+}
+
+
+function ArrayReverse() {
+ var j = ToUint32(this.length) - 1;
+
+ if (UseSparseVariant(this, j, IS_ARRAY(this))) {
+ SparseReverse(this, j+1);
+ return this;
+ }
+
+ for (var i = 0; i < j; i++, j--) {
+ var current_i = this[i];
+ if (!IS_UNDEFINED(current_i) || i in this) {
+ var current_j = this[j];
+ if (!IS_UNDEFINED(current_j) || j in this) {
+ this[i] = current_j;
+ this[j] = current_i;
+ } else {
+ this[j] = current_i;
+ delete this[i];
+ }
+ } else {
+ var current_j = this[j];
+ if (!IS_UNDEFINED(current_j) || j in this) {
+ this[i] = current_j;
+ delete this[j];
+ }
+ }
+ }
+ return this;
+}
+
+
+function ArrayShift() {
+ var len = ToUint32(this.length);
+
+ if (len === 0) {
+ this.length = 0;
+ return;
+ }
+
+ var first = this[0];
+
+ if (IS_ARRAY(this))
+ SmartMove(this, 0, 1, len, 0);
+ else
+ SimpleMove(this, 0, 1, len, 0);
+
+ this.length = len - 1;
+
+ return first;
+}
+
+
+function ArrayUnshift(arg1) { // length == 1
+ var len = ToUint32(this.length);
+ var num_arguments = %_ArgumentsLength();
+
+ if (IS_ARRAY(this))
+ SmartMove(this, 0, 0, len, num_arguments);
+ else
+ SimpleMove(this, 0, 0, len, num_arguments);
+
+ for (var i = 0; i < num_arguments; i++) {
+ this[i] = %_Arguments(i);
+ }
+
+ this.length = len + num_arguments;
+
+ return len + num_arguments;
+}
+
+
+function ArraySlice(start, end) {
+ var len = ToUint32(this.length);
+ var start_i = TO_INTEGER(start);
+ var end_i = len;
+
+ if (end !== void 0) end_i = TO_INTEGER(end);
+
+ if (start_i < 0) {
+ start_i += len;
+ if (start_i < 0) start_i = 0;
+ } else {
+ if (start_i > len) start_i = len;
+ }
+
+ if (end_i < 0) {
+ end_i += len;
+ if (end_i < 0) end_i = 0;
+ } else {
+ if (end_i > len) end_i = len;
+ }
+
+ var result = [];
+
+ if (end_i < start_i) return result;
+
+ if (IS_ARRAY(this)) {
+ SmartSlice(this, start_i, end_i - start_i, len, result);
+ } else {
+ SimpleSlice(this, start_i, end_i - start_i, len, result);
+ }
+
+ result.length = end_i - start_i;
+
+ return result;
+}
+
+
+function ArraySplice(start, delete_count) {
+ var num_arguments = %_ArgumentsLength();
+
+ // SpiderMonkey and KJS return undefined in the case where no
+ // arguments are given instead of using the implicit undefined
+ // arguments. This does not follow ECMA-262, but we do the same for
+ // compatibility.
+ if (num_arguments == 0) return;
+
+ var len = ToUint32(this.length);
+ var start_i = TO_INTEGER(start);
+
+ if (start_i < 0) {
+ start_i += len;
+ if (start_i < 0) start_i = 0;
+ } else {
+ if (start_i > len) start_i = len;
+ }
+
+ // SpiderMonkey and KJS treat the case where no delete count is
+ // given differently from when an undefined delete count is given.
+ // This does not follow ECMA-262, but we do the same for
+ // compatibility.
+ var del_count = 0;
+ if (num_arguments > 1) {
+ del_count = TO_INTEGER(delete_count);
+ if (del_count < 0) del_count = 0;
+ if (del_count > len - start_i) del_count = len - start_i;
+ } else {
+ del_count = len - start_i;
+ }
+
+ var deleted_elements = [];
+ deleted_elements.length = del_count;
+
+ // Number of elements to add.
+ var num_additional_args = 0;
+ if (num_arguments > 2) {
+ num_additional_args = num_arguments - 2;
+ }
+
+ var use_simple_splice = true;
+
+ if (IS_ARRAY(this) && num_additional_args !== del_count) {
+ // If we are only deleting/moving a few things near the end of the
+ // array then the simple version is going to be faster, because it
+ // doesn't touch most of the array.
+ var estimated_non_hole_elements = %EstimateNumberOfElements(this);
+ if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
+ use_simple_splice = false;
+ }
+ }
+
+ if (use_simple_splice) {
+ SimpleSlice(this, start_i, del_count, len, deleted_elements);
+ SimpleMove(this, start_i, del_count, len, num_additional_args);
+ } else {
+ SmartSlice(this, start_i, del_count, len, deleted_elements);
+ SmartMove(this, start_i, del_count, len, num_additional_args);
+ }
+
+ // Insert the arguments into the resulting array in
+ // place of the deleted elements.
+ var i = start_i;
+ var arguments_index = 2;
+ var arguments_length = %_ArgumentsLength();
+ while (arguments_index < arguments_length) {
+ this[i++] = %_Arguments(arguments_index++);
+ }
+ this.length = len - del_count + num_additional_args;
+
+ // Return the deleted elements.
+ return deleted_elements;
+}
+
+
+function ArraySort(comparefn) {
+ // In-place QuickSort algorithm.
+ // For short (length <= 22) arrays, insertion sort is used for efficiency.
+
+ var custom_compare = IS_FUNCTION(comparefn);
+
+ function Compare(x,y) {
+ // Assume the comparefn, if any, is a consistent comparison function.
+ // If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11.
+ if (x === y) return 0;
+ if (custom_compare) {
+ // Don't call directly to avoid exposing the builtin's global object.
+ return comparefn.call(null, x, y);
+ }
+ if (%_IsSmi(x) && %_IsSmi(y)) {
+ return %SmiLexicographicCompare(x, y);
+ }
+ x = ToString(x);
+ y = ToString(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];
+ // Pre-convert the element to a string for comparison if we know
+ // it will happen on each compare anyway.
+ var key =
+ (custom_compare || %_IsSmi(element)) ? element : ToString(element);
+ // place element in a[from..i[
+ // binary search
+ var min = from;
+ var max = i;
+ // The search interval is a[min..max[
+ while (min < max) {
+ var mid = min + ((max - min) >> 1);
+ var order = Compare(a[mid], key);
+ if (order == 0) {
+ min = max = mid;
+ break;
+ }
+ if (order < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ // place element at position min==max.
+ for (var j = i; j > min; j--) {
+ a[j] = a[j - 1];
+ }
+ a[min] = element;
+ }
+ }
+
+ function QuickSort(a, from, to) {
+ // Insertion sort is faster for short arrays.
+ if (to - from <= 22) {
+ InsertionSort(a, from, to);
+ return;
+ }
+ var pivot_index = $floor($random() * (to - from)) + from;
+ var pivot = a[pivot_index];
+ // Pre-convert the element to a string for comparison if we know
+ // it will happen on each compare anyway.
+ var pivot_key =
+ (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot);
+ // Issue 95: Keep the pivot element out of the comparisons to avoid
+ // infinite recursion if comparefn(pivot, pivot) != 0.
+ a[pivot_index] = a[from];
+ a[from] = pivot;
+ var low_end = from; // Upper bound of the elements lower than pivot.
+ var high_start = to; // Lower bound of the elements greater than pivot.
+ // From low_end to i are elements equal to pivot.
+ // From i to high_start are elements that haven't been compared yet.
+ for (var i = from + 1; i < high_start; ) {
+ var element = a[i];
+ var order = Compare(element, pivot_key);
+ if (order < 0) {
+ a[i] = a[low_end];
+ a[low_end] = element;
+ i++;
+ low_end++;
+ } else if (order > 0) {
+ high_start--;
+ a[i] = a[high_start];
+ a[high_start] = element;
+ } else { // order == 0
+ i++;
+ }
+ }
+ QuickSort(a, from, low_end);
+ QuickSort(a, high_start, to);
+ }
+
+ var length;
+
+ // Copies elements in the range 0..length from obj's prototype chain
+ // to obj itself, if obj has holes. Returns one more than the maximal index
+ // of a prototype property.
+ function CopyFromPrototype(obj, length) {
+ var max = 0;
+ for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
+ var indices = %GetArrayKeys(proto, length);
+ if (indices.length > 0) {
+ if (indices[0] == -1) {
+ // It's an interval.
+ var proto_length = indices[1];
+ for (var i = 0; i < proto_length; i++) {
+ if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
+ obj[i] = proto[i];
+ if (i >= max) { max = i + 1; }
+ }
+ }
+ } else {
+ for (var i = 0; i < indices.length; i++) {
+ var index = indices[i];
+ if (!IS_UNDEFINED(index) &&
+ !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) {
+ obj[index] = proto[index];
+ if (index >= max) { max = index + 1; }
+ }
+ }
+ }
+ }
+ }
+ return max;
+ }
+
+ // Set a value of "undefined" on all indices in the range from..to
+ // where a prototype of obj has an element. I.e., shadow all prototype
+ // elements in that range.
+ function ShadowPrototypeElements(obj, from, to) {
+ for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
+ var indices = %GetArrayKeys(proto, to);
+ if (indices.length > 0) {
+ if (indices[0] == -1) {
+ // It's an interval.
+ var proto_length = indices[1];
+ for (var i = from; i < proto_length; i++) {
+ if (proto.hasOwnProperty(i)) {
+ obj[i] = void 0;
+ }
+ }
+ } else {
+ for (var i = 0; i < indices.length; i++) {
+ var index = indices[i];
+ if (!IS_UNDEFINED(index) && from <= index &&
+ proto.hasOwnProperty(index)) {
+ obj[index] = void 0;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ function SafeRemoveArrayHoles(obj) {
+ // Copy defined elements from the end to fill in all holes and undefineds
+ // in the beginning of the array. Write undefineds and holes at the end
+ // after loop is finished.
+ var first_undefined = 0;
+ var last_defined = length - 1;
+ var num_holes = 0;
+ while (first_undefined < last_defined) {
+ // Find first undefined element.
+ while (first_undefined < last_defined &&
+ !IS_UNDEFINED(obj[first_undefined])) {
+ first_undefined++;
+ }
+ // Maintain the invariant num_holes = the number of holes in the original
+ // array with indices <= first_undefined or > last_defined.
+ if (!obj.hasOwnProperty(first_undefined)) {
+ num_holes++;
+ }
+
+ // Find last defined element.
+ while (first_undefined < last_defined &&
+ IS_UNDEFINED(obj[last_defined])) {
+ if (!obj.hasOwnProperty(last_defined)) {
+ num_holes++;
+ }
+ last_defined--;
+ }
+ if (first_undefined < last_defined) {
+ // Fill in hole or undefined.
+ obj[first_undefined] = obj[last_defined];
+ obj[last_defined] = void 0;
+ }
+ }
+ // If there were any undefineds in the entire array, first_undefined
+ // points to one past the last defined element. Make this true if
+ // there were no undefineds, as well, so that first_undefined == number
+ // of defined elements.
+ if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
+ // Fill in the undefineds and the holes. There may be a hole where
+ // an undefined should be and vice versa.
+ var i;
+ for (i = first_undefined; i < length - num_holes; i++) {
+ obj[i] = void 0;
+ }
+ for (i = length - num_holes; i < length; i++) {
+ // For compatability with Webkit, do not expose elements in the prototype.
+ if (i in obj.__proto__) {
+ obj[i] = void 0;
+ } else {
+ delete obj[i];
+ }
+ }
+
+ // Return the number of defined elements.
+ return first_undefined;
+ }
+
+ length = ToUint32(this.length);
+ if (length < 2) return this;
+
+ var is_array = IS_ARRAY(this);
+ var max_prototype_element;
+ if (!is_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
+ // local 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.
+ max_prototype_element = CopyFromPrototype(this, length);
+ }
+
+ var num_non_undefined = %RemoveArrayHoles(this, length);
+ if (num_non_undefined == -1) {
+ // There were indexed accessors in the array. Move array holes and
+ // undefineds to the end using a Javascript function that is safe
+ // in the presence of accessors.
+ num_non_undefined = SafeRemoveArrayHoles(this);
+ }
+
+ QuickSort(this, 0, num_non_undefined);
+
+ if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
+ // For compatibility with JSC, we shadow any elements in the prototype
+ // chain that has become exposed by sort moving a hole to its position.
+ ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
+ }
+
+ return this;
+}
+
+
+// The following functions cannot be made efficient on sparse arrays while
+// preserving the semantics, since the calls to the receiver function can add
+// or delete elements from the array.
+function ArrayFilter(f, receiver) {
+ if (!IS_FUNCTION(f)) {
+ throw MakeTypeError('called_non_callable', [ f ]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ var result = [];
+ var result_length = 0;
+ for (var i = 0; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ if (f.call(receiver, current, i, this)) result[result_length++] = current;
+ }
+ }
+ return result;
+}
+
+
+function ArrayForEach(f, receiver) {
+ if (!IS_FUNCTION(f)) {
+ throw MakeTypeError('called_non_callable', [ f ]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ for (var i = 0; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ f.call(receiver, current, i, this);
+ }
+ }
+}
+
+
+// Executes the function once for each element present in the
+// array until it finds one where callback returns true.
+function ArraySome(f, receiver) {
+ if (!IS_FUNCTION(f)) {
+ throw MakeTypeError('called_non_callable', [ f ]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ for (var i = 0; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ if (f.call(receiver, current, i, this)) return true;
+ }
+ }
+ return false;
+}
+
+
+function ArrayEvery(f, receiver) {
+ if (!IS_FUNCTION(f)) {
+ throw MakeTypeError('called_non_callable', [ f ]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ for (var i = 0; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ if (!f.call(receiver, current, i, this)) return false;
+ }
+ }
+
+ return true;
+}
+
+
+function ArrayMap(f, receiver) {
+ if (!IS_FUNCTION(f)) {
+ throw MakeTypeError('called_non_callable', [ f ]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ var result = new $Array(length);
+ for (var i = 0; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ result[i] = f.call(receiver, current, i, this);
+ }
+ }
+ return result;
+}
+
+
+function ArrayIndexOf(element, index) {
+ var length = this.length;
+ if (index == null) {
+ index = 0;
+ } else {
+ index = TO_INTEGER(index);
+ // If index is negative, index from the end of the array.
+ if (index < 0) index = length + index;
+ // If index is still negative, search the entire array.
+ if (index < 0) index = 0;
+ }
+ // Lookup through the array.
+ for (var i = index; i < length; i++) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ if (current === element) return i;
+ }
+ }
+ return -1;
+}
+
+
+function ArrayLastIndexOf(element, index) {
+ var length = this.length;
+ if (index == null) {
+ index = length - 1;
+ } else {
+ index = TO_INTEGER(index);
+ // If index is negative, index from end of the array.
+ if (index < 0) index = length + index;
+ // If index is still negative, do not search the array.
+ if (index < 0) index = -1;
+ else if (index >= length) index = length - 1;
+ }
+ // Lookup through the array.
+ for (var i = index; i >= 0; i--) {
+ var current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ if (current === element) return i;
+ }
+ }
+ return -1;
+}
+
+
+function ArrayReduce(callback, current) {
+ if (!IS_FUNCTION(callback)) {
+ throw MakeTypeError('called_non_callable', [callback]);
+ }
+ // Pull out the length so that modifications to the length in the
+ // loop will not affect the looping.
+ var length = this.length;
+ var i = 0;
+
+ find_initial: if (%_ArgumentsLength() < 2) {
+ for (; i < length; i++) {
+ current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ i++;
+ break find_initial;
+ }
+ }
+ throw MakeTypeError('reduce_no_initial', []);
+ }
+
+ for (; i < length; i++) {
+ var element = this[i];
+ if (!IS_UNDEFINED(element) || i in this) {
+ current = callback.call(null, current, element, i, this);
+ }
+ }
+ return current;
+}
+
+function ArrayReduceRight(callback, current) {
+ if (!IS_FUNCTION(callback)) {
+ throw MakeTypeError('called_non_callable', [callback]);
+ }
+ var i = this.length - 1;
+
+ find_initial: if (%_ArgumentsLength() < 2) {
+ for (; i >= 0; i--) {
+ current = this[i];
+ if (!IS_UNDEFINED(current) || i in this) {
+ i--;
+ break find_initial;
+ }
+ }
+ throw MakeTypeError('reduce_no_initial', []);
+ }
+
+ for (; i >= 0; i--) {
+ var element = this[i];
+ if (!IS_UNDEFINED(element) || i in this) {
+ current = callback.call(null, current, element, i, this);
+ }
+ }
+ return current;
+}
+
+
+// -------------------------------------------------------------------
+
+
+function UpdateFunctionLengths(lengths) {
+ for (var key in lengths) {
+ %FunctionSetLength(this[key], lengths[key]);
+ }
+}
+
+
+// -------------------------------------------------------------------
+function SetupArray() {
+ // Setup non-enumerable constructor property on the Array.prototype
+ // object.
+ %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM);
+
+ // Setup non-enumerable functions of the Array.prototype object and
+ // set their names.
+ InstallFunctionsOnHiddenPrototype($Array.prototype, DONT_ENUM, $Array(
+ "toString", ArrayToString,
+ "toLocaleString", ArrayToLocaleString,
+ "join", ArrayJoin,
+ "pop", ArrayPop,
+ "push", ArrayPush,
+ "concat", ArrayConcat,
+ "reverse", ArrayReverse,
+ "shift", ArrayShift,
+ "unshift", ArrayUnshift,
+ "slice", ArraySlice,
+ "splice", ArraySplice,
+ "sort", ArraySort,
+ "filter", ArrayFilter,
+ "forEach", ArrayForEach,
+ "some", ArraySome,
+ "every", ArrayEvery,
+ "map", ArrayMap,
+ "indexOf", ArrayIndexOf,
+ "lastIndexOf", ArrayLastIndexOf,
+ "reduce", ArrayReduce,
+ "reduceRight", ArrayReduceRight));
+
+ // Manipulate the length of some of the functions to meet
+ // expectations set by ECMA-262 or Mozilla.
+ UpdateFunctionLengths({
+ ArrayFilter: 1,
+ ArrayForEach: 1,
+ ArraySome: 1,
+ ArrayEvery: 1,
+ ArrayMap: 1,
+ ArrayIndexOf: 1,
+ ArrayLastIndexOf: 1,
+ ArrayPush: 1,
+ ArrayReduce: 1,
+ ArrayReduceRight: 1
+ });
+}
+
+
+SetupArray();