array.js.svn-base

Google浏览器V8内核代码

// 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
  var arg_number = 0, arg_count = %_ArgumentsLength();
  var n = 0;

  var A = $Array(1 + arg_count);
  var E = this;

  while (true) {
    if (IS_ARRAY(E)) {
      // This is an array of intervals or an array of keys.  Keys are
      // represented by non-negative integers.  Intervals are represented by
      // negative integers, followed by positive counts.  The interval start
      // is determined by subtracting the entry from -1.  There may also be
      // undefined entries in the array which should be skipped.
      var intervals = %GetArrayKeys(E, E.length);
      var length = intervals.length;
      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++) {
            if (j in E) {
              A[n + j] = E[j];
            }
          }
        } else {
          // The case where key is undefined also ends here.
          if (!IS_UNDEFINED(key)) {
            A[n + key] = E[key];
          }
        }
      }
      n += E.length;
    } else {
      A[n++] = E;
    }
    if (arg_number == arg_count) break;
    E = %_Arguments(arg_number++);
  }

  A.length = n;  // may contain empty arrays
  return A;
};


// 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];
      }
    }
  }
}