mirror of
https://github.com/SSCLI/sscli_20021101
synced 2026-06-08 12:28:57 +00:00
yallie
536 lines
19 KiB
C#
536 lines
19 KiB
C#
// ==++==
|
|
//
|
|
//
|
|
// Copyright (c) 2002 Microsoft Corporation. All rights reserved.
|
|
//
|
|
// The use and distribution terms for this software are contained in the file
|
|
// named license.txt, which can be found in the root of this distribution.
|
|
// By using this software in any fashion, you are agreeing to be bound by the
|
|
// terms of this license.
|
|
//
|
|
// You must not remove this notice, or any other, from this software.
|
|
//
|
|
//
|
|
// ==--==
|
|
namespace Microsoft.JScript
|
|
{
|
|
|
|
using System;
|
|
using System.Collections;
|
|
using System.Reflection;
|
|
using System.Diagnostics;
|
|
|
|
public class ArrayObject : JSObject{
|
|
internal const int MaxIndex = 100000;
|
|
internal const int MinDenseSize = 128;
|
|
|
|
internal uint len;
|
|
internal Object[] denseArray;
|
|
internal uint denseArrayLength;
|
|
|
|
internal ArrayObject(ScriptObject prototype)
|
|
: base(prototype){
|
|
this.len = 0;
|
|
this.denseArray = null;
|
|
this.denseArrayLength = 0;
|
|
this.noExpando = false;
|
|
}
|
|
|
|
internal ArrayObject(ScriptObject prototype, Type subType)
|
|
: base(prototype, subType) {
|
|
this.len = 0;
|
|
this.denseArray = null;
|
|
this.denseArrayLength = 0;
|
|
this.noExpando = false;
|
|
}
|
|
|
|
internal static long Array_index_for(Object index){
|
|
if (index is Int32) return (int)index;
|
|
IConvertible ic = Convert.GetIConvertible(index);
|
|
switch (Convert.GetTypeCode(index, ic)){
|
|
case TypeCode.Char:
|
|
case TypeCode.SByte:
|
|
case TypeCode.Byte:
|
|
case TypeCode.Int16:
|
|
case TypeCode.UInt16:
|
|
case TypeCode.Int32:
|
|
case TypeCode.UInt32:
|
|
case TypeCode.Int64:
|
|
case TypeCode.UInt64:
|
|
case TypeCode.Decimal:
|
|
case TypeCode.Single:
|
|
case TypeCode.Double:
|
|
double d = ic.ToDouble(null);
|
|
long l = (long)d;
|
|
if (l >= 0 && (double)l == d)
|
|
return l;
|
|
break;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
internal static long Array_index_for(String name){
|
|
int len = name.Length;
|
|
if (len <= 0) return -1;
|
|
Char ch = name[0];
|
|
if (ch < '1' || ch > '9')
|
|
if (ch == '0' && len == 1)
|
|
return 0;
|
|
else
|
|
return -1;
|
|
long result = ch - '0';
|
|
for (int i = 1; i < len; i++){
|
|
ch = name[i];
|
|
if (ch < '0' || ch > '9') return -1;
|
|
result = result*10 + (ch - '0');
|
|
if (result > UInt32.MaxValue) return -1;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
internal virtual void Concat(ArrayObject source){
|
|
uint sourceLength = source.len;
|
|
if (sourceLength == 0)
|
|
return;
|
|
uint oldLength = this.len;
|
|
this.SetLength(oldLength + (ulong)sourceLength);
|
|
uint slen = sourceLength;
|
|
if (!(source is ArrayWrapper) && sourceLength > source.denseArrayLength)
|
|
slen = source.denseArrayLength;
|
|
uint j = oldLength;
|
|
for (uint i = 0; i < slen; i++)
|
|
this.SetValueAtIndex(j++, source.GetValueAtIndex(i));
|
|
if (slen == sourceLength) return;
|
|
//Iterate over the sparse indices of source
|
|
IDictionaryEnumerator e = source.NameTable.GetEnumerator();
|
|
while (e.MoveNext()){
|
|
long i = ArrayObject.Array_index_for(e.Key.ToString());
|
|
if (i >= 0)
|
|
this.SetValueAtIndex(oldLength+(uint)i, ((JSField)e.Value).GetValue(null));
|
|
}
|
|
}
|
|
|
|
internal virtual void Concat(Object value){
|
|
Array arr = value as Array;
|
|
if (arr != null && arr.Rank == 1)
|
|
this.Concat(new ArrayWrapper(ArrayPrototype.ob, arr, true));
|
|
else {
|
|
uint oldLength = this.len;
|
|
this.SetLength(1 + (ulong)oldLength);
|
|
this.SetValueAtIndex(oldLength, value);
|
|
}
|
|
}
|
|
|
|
internal override bool DeleteMember(String name){
|
|
long i = ArrayObject.Array_index_for(name);
|
|
if (i >= 0)
|
|
return this.DeleteValueAtIndex((uint)i);
|
|
else
|
|
return base.DeleteMember(name);
|
|
}
|
|
|
|
internal virtual bool DeleteValueAtIndex(uint index){
|
|
if (index < this.denseArrayLength)
|
|
if (this.denseArray[(int)index] is Missing)
|
|
return false;
|
|
else{
|
|
this.denseArray[(int)index] = Missing.Value;
|
|
return true;
|
|
}
|
|
else
|
|
return base.DeleteMember(index.ToString());
|
|
}
|
|
|
|
private void DeleteRange(uint start, uint end){
|
|
uint denseEnd = this.denseArrayLength;
|
|
if (denseEnd > end)
|
|
denseEnd = end;
|
|
for (; start < denseEnd; start++)
|
|
denseArray[(int)start] = Missing.Value;
|
|
if (denseEnd == end) return;
|
|
//Go through the field table entries, deleting those with names that are indices between start and end
|
|
IDictionaryEnumerator e = this.NameTable.GetEnumerator();
|
|
ArrayList arr = new ArrayList(this.name_table.count);
|
|
while (e.MoveNext()){
|
|
long i = ArrayObject.Array_index_for(e.Key.ToString());
|
|
if (i >= start && i <= end)
|
|
arr.Add(e.Key);
|
|
}
|
|
IEnumerator ae = arr.GetEnumerator();
|
|
while (ae.MoveNext())
|
|
this.DeleteMember((String)ae.Current);
|
|
}
|
|
|
|
internal override String GetClassName(){
|
|
return "Array";
|
|
}
|
|
|
|
internal override Object GetDefaultValue(PreferredType preferred_type){
|
|
if (this.GetParent() is LenientArrayPrototype) return base.GetDefaultValue(preferred_type);
|
|
if (preferred_type == PreferredType.String){
|
|
if (!this.noExpando){
|
|
Object field = this.NameTable["toString"];
|
|
if (field != null) return base.GetDefaultValue(preferred_type);
|
|
}
|
|
return ArrayPrototype.toString(this);
|
|
}else if (preferred_type == PreferredType.LocaleString){
|
|
if (!this.noExpando){
|
|
Object field = this.NameTable["toLocaleString"];
|
|
if (field != null) return base.GetDefaultValue(preferred_type);
|
|
}
|
|
return ArrayPrototype.toLocaleString(this);
|
|
}else{
|
|
if (!this.noExpando){
|
|
Object field = this.NameTable["valueOf"];
|
|
if (field == null && preferred_type == PreferredType.Either)
|
|
field = this.NameTable["toString"];
|
|
if (field != null) return base.GetDefaultValue(preferred_type);
|
|
}
|
|
return ArrayPrototype.toString(this);
|
|
}
|
|
}
|
|
|
|
|
|
internal override void GetPropertyEnumerator(ArrayList enums, ArrayList objects){
|
|
if (this.field_table == null) this.field_table = new ArrayList();
|
|
enums.Add(new ArrayEnumerator(this, new ListEnumerator(this.field_table)));
|
|
objects.Add(this);
|
|
if (this.parent != null)
|
|
this.parent.GetPropertyEnumerator(enums, objects);
|
|
}
|
|
|
|
internal override Object GetValueAtIndex(uint index){
|
|
if (index < this.denseArrayLength){
|
|
Object result = this.denseArray[(int)index];
|
|
if (result != Missing.Value)
|
|
return result;
|
|
}
|
|
return base.GetValueAtIndex(index);
|
|
}
|
|
|
|
#if !DEBUG
|
|
[DebuggerStepThroughAttribute]
|
|
[DebuggerHiddenAttribute]
|
|
#endif
|
|
internal override Object GetMemberValue(String name){
|
|
long index = ArrayObject.Array_index_for(name);
|
|
if (index < 0)
|
|
return base.GetMemberValue(name);
|
|
else
|
|
return this.GetValueAtIndex((uint)index);
|
|
}
|
|
|
|
public virtual Object length{
|
|
get{
|
|
//Convert the length from a uint to either an int or a double. The latter two are special cased in arith operations.
|
|
if (this.len < Int32.MaxValue)
|
|
return (int)this.len;
|
|
else
|
|
return (double)this.len;
|
|
}
|
|
set{
|
|
IConvertible ic = Convert.GetIConvertible(value);
|
|
uint newLength = Convert.ToUint32(value, ic);
|
|
if ((double)newLength != Convert.ToNumber(value, ic))
|
|
throw new JScriptException(JSError.ArrayLengthAssignIncorrect);
|
|
this.SetLength(newLength);
|
|
}
|
|
}
|
|
|
|
private void Realloc(uint newLength){
|
|
Debug.PreCondition(this.denseArrayLength >= this.len);
|
|
Debug.PreCondition(newLength <= ArrayObject.MaxIndex);
|
|
uint oldDenseLength = this.denseArrayLength;
|
|
uint newDenseLength = oldDenseLength*2;
|
|
if (newDenseLength < newLength) newDenseLength = newLength;
|
|
Object[] newArray = new Object[(int)newDenseLength];
|
|
if (oldDenseLength > 0)
|
|
ArrayObject.Copy(this.denseArray, newArray, (int)oldDenseLength);
|
|
for (int i = (int)oldDenseLength; i < newDenseLength; i++)
|
|
newArray[i] = Missing.Value;
|
|
this.denseArray = newArray;
|
|
this.denseArrayLength = newDenseLength;
|
|
}
|
|
|
|
private void SetLength(ulong newLength){
|
|
uint oldLength = this.len;
|
|
if (newLength < oldLength)
|
|
this.DeleteRange((uint)newLength, oldLength);
|
|
else if (newLength > UInt32.MaxValue)
|
|
throw new JScriptException(JSError.ArrayLengthAssignIncorrect);
|
|
else if (newLength > this.denseArrayLength && oldLength <= this.denseArrayLength //The array is dense, try to keep it dense
|
|
&& newLength <= ArrayObject.MaxIndex //Small enough to keep dense
|
|
&& (newLength <= ArrayObject.MinDenseSize || newLength <= oldLength * 2)) //Close enough to existing dense part
|
|
this.Realloc((uint)newLength);
|
|
this.len = (uint)newLength;
|
|
}
|
|
|
|
#if !DEBUG
|
|
[DebuggerStepThroughAttribute]
|
|
[DebuggerHiddenAttribute]
|
|
#endif
|
|
internal override void SetMemberValue(String name, Object value){
|
|
if (name.Equals("length")){
|
|
this.length = value;
|
|
return;
|
|
}
|
|
long index = ArrayObject.Array_index_for(name);
|
|
if (index < 0)
|
|
base.SetMemberValue(name, value);
|
|
else
|
|
this.SetValueAtIndex((uint)index, value);
|
|
}
|
|
|
|
internal override void SetValueAtIndex(uint index, Object value){
|
|
if (index >= this.len && index < UInt32.MaxValue)
|
|
this.SetLength(index + 1);
|
|
if (index < this.denseArrayLength)
|
|
this.denseArray[(int)index] = value;
|
|
else
|
|
base.SetMemberValue(index.ToString(), value);
|
|
}
|
|
|
|
internal virtual Object Shift(){
|
|
Object res = null;
|
|
uint thisLength = this.len;
|
|
if (thisLength == 0)
|
|
return res;
|
|
uint lastItemInDense = (this.denseArrayLength >= thisLength) ? thisLength : this.denseArrayLength;
|
|
if (lastItemInDense > 0){
|
|
res = this.denseArray[0];
|
|
ArrayObject.Copy(this.denseArray, 1, this.denseArray, 0, (int)(lastItemInDense-1));
|
|
}else
|
|
res = base.GetValueAtIndex(0);
|
|
for (uint i = lastItemInDense; i < thisLength; i++)
|
|
this.SetValueAtIndex(i-1, this.GetValueAtIndex(i));
|
|
this.SetValueAtIndex(thisLength-1, Missing.Value);
|
|
SetLength(thisLength - 1);
|
|
if (res is Missing) return null;
|
|
return res;
|
|
}
|
|
|
|
internal virtual void Sort(ScriptFunction compareFn){
|
|
QuickSort qs = new QuickSort(this, compareFn);
|
|
uint length = this.len;
|
|
if (length <= this.denseArrayLength)
|
|
qs.SortArray(0, (int)length - 1);
|
|
else
|
|
qs.SortObject(0, length - 1);
|
|
}
|
|
|
|
internal virtual void Splice(uint start, uint deleteCount, Object[] args, ArrayObject outArray, uint oldLength, uint newLength){
|
|
if (oldLength > this.denseArrayLength){
|
|
SpliceSlowly(start, deleteCount, args, outArray, oldLength, newLength);
|
|
return;
|
|
}
|
|
if (newLength > oldLength){
|
|
this.SetLength(newLength);
|
|
if (newLength > this.denseArrayLength){
|
|
SpliceSlowly(start, deleteCount, args, outArray, oldLength, newLength);
|
|
return;
|
|
}
|
|
}
|
|
if (deleteCount > oldLength)
|
|
deleteCount = oldLength;
|
|
if (deleteCount > 0)
|
|
ArrayObject.Copy(this.denseArray, (int)start, outArray.denseArray, 0, (int)deleteCount);
|
|
if (oldLength > 0)
|
|
ArrayObject.Copy(this.denseArray, (int)(start+deleteCount), this.denseArray, (int)(start)+args.Length, (int)(oldLength-start-deleteCount));
|
|
if (args != null){
|
|
int n = args.Length;
|
|
if (n > 0)
|
|
ArrayObject.Copy(args, 0, this.denseArray, (int)start, n);
|
|
if (n < deleteCount)
|
|
this.SetLength(newLength);
|
|
}else if (deleteCount > 0)
|
|
this.SetLength(newLength);
|
|
}
|
|
|
|
protected void SpliceSlowly(uint start, uint deleteCount, Object[] args, ArrayObject outArray, uint oldLength, uint newLength){
|
|
for (uint i = 0; i < deleteCount; i++)
|
|
outArray.SetValueAtIndex(i, this.GetValueAtIndex(i+start));
|
|
uint n = oldLength-start-deleteCount;
|
|
if (newLength < oldLength){
|
|
for (uint i = 0; i < n; i++)
|
|
this.SetValueAtIndex(i+start+(uint)args.Length, this.GetValueAtIndex(i+start+deleteCount));
|
|
this.SetLength(newLength);
|
|
}else{
|
|
if (newLength > oldLength)
|
|
this.SetLength(newLength);
|
|
for (uint i = n; i > 0; i--)
|
|
this.SetValueAtIndex(i+start+(uint)args.Length-1, this.GetValueAtIndex(i+start+deleteCount-1));
|
|
}
|
|
int m = args == null ? 0 : args.Length;
|
|
for (uint i = 0; i < m; i++)
|
|
this.SetValueAtIndex(i+start, args[i]);
|
|
}
|
|
|
|
internal override void SwapValues(uint pi, uint qi){
|
|
if (pi > qi)
|
|
this.SwapValues(qi, pi);
|
|
else if (pi >= this.denseArrayLength)
|
|
base.SwapValues(pi, qi);
|
|
else{
|
|
Object temp = this.denseArray[(int)pi];
|
|
this.denseArray[(int)pi] = this.GetValueAtIndex(qi);
|
|
if (temp == Missing.Value)
|
|
this.DeleteValueAtIndex(qi);
|
|
else
|
|
this.SetValueAtIndex(qi, temp);
|
|
}
|
|
}
|
|
|
|
internal virtual Object[] ToArray(){
|
|
int thisLength = (int)this.len;
|
|
if (thisLength == 0)
|
|
return new Object[0];
|
|
else if (thisLength == this.denseArrayLength)
|
|
return this.denseArray;
|
|
else if (thisLength < this.denseArrayLength){
|
|
Object[] result = new Object[thisLength];
|
|
ArrayObject.Copy(this.denseArray, 0, result, 0, thisLength);
|
|
return result;
|
|
}else{
|
|
Object[] result = new Object[thisLength];
|
|
ArrayObject.Copy(this.denseArray, 0, result, 0, (int)this.denseArrayLength);
|
|
for (uint i = this.denseArrayLength; i < thisLength; i++)
|
|
result[i] = this.GetValueAtIndex(i);
|
|
return result;
|
|
}
|
|
}
|
|
|
|
internal virtual Array ToNativeArray(Type elementType){
|
|
uint n = this.len;
|
|
if (n > Int32.MaxValue)
|
|
throw new JScriptException(JSError.OutOfMemory);
|
|
if (elementType == null) elementType = Typeob.Object;
|
|
uint m = this.denseArrayLength;
|
|
if (m > n) m = n;
|
|
Array result = Array.CreateInstance(elementType, (int)n);
|
|
for (int i = 0; i < m; i++)
|
|
result.SetValue(Convert.CoerceT(this.denseArray[i], elementType), i);
|
|
for (int i = (int)m; i < n; i++)
|
|
result.SetValue(Convert.CoerceT(this.GetValueAtIndex((uint)i), elementType), i);
|
|
return result;
|
|
}
|
|
|
|
internal static void Copy(Object[] source, Object[] target, int n){
|
|
ArrayObject.Copy(source, 0, target, 0, n);
|
|
}
|
|
|
|
internal static void Copy(Object[] source, int i, Object[] target, int j, int n){
|
|
if (i < j)
|
|
for (int m = n-1; m >= 0; m--)
|
|
target[j+m] = source[i+m];
|
|
else
|
|
for (int m = 0; m < n; m++)
|
|
target[j+m] = source[i+m];
|
|
}
|
|
|
|
internal virtual ArrayObject Unshift(Object[] args){
|
|
Debug.PreCondition(args != null && args.Length > 0);
|
|
uint oldLength = this.len;
|
|
int numArgs = args.Length;
|
|
ulong newLength = oldLength + (ulong)numArgs;
|
|
this.SetLength(newLength);
|
|
if (newLength <= this.denseArrayLength){
|
|
for (int i = (int)(oldLength - 1); i >= 0; i--)
|
|
this.denseArray[i+numArgs] = this.denseArray[i];
|
|
ArrayObject.Copy(args, 0, this.denseArray, 0, args.Length);
|
|
}else{
|
|
for (long i = oldLength - 1; i >= 0; i--)
|
|
this.SetValueAtIndex((uint)(i + numArgs), this.GetValueAtIndex((uint)i));
|
|
for (uint i = 0; i < numArgs; i++)
|
|
this.SetValueAtIndex(i, args[i]);
|
|
}
|
|
return this;
|
|
}
|
|
|
|
|
|
}
|
|
|
|
internal sealed class QuickSort{
|
|
internal ScriptFunction compareFn;
|
|
internal Object obj;
|
|
|
|
internal QuickSort(Object obj, ScriptFunction compareFn){
|
|
this.compareFn = compareFn;
|
|
this.obj = obj;
|
|
}
|
|
|
|
private int Compare(Object x, Object y){
|
|
if (x == null || x is Missing)
|
|
if (y == null || y is Missing)
|
|
return 0;
|
|
else
|
|
return 1;
|
|
else if (y == null || y is Missing)
|
|
return -1;
|
|
if (this.compareFn != null){
|
|
double result = Convert.ToNumber(this.compareFn.Call(new Object[]{x, y}, null));
|
|
if (result != result)
|
|
throw new JScriptException(JSError.NumberExpected);
|
|
return (int)result;
|
|
}else
|
|
return String.CompareOrdinal(Convert.ToString(x), Convert.ToString(y));
|
|
}
|
|
|
|
internal void SortObject(long left, long right){ //left and right are longs to allow for values < 0. Their positives values are always < UInt32.MaxValue.
|
|
Object x, y;
|
|
if (right > left){
|
|
long piv = left + (long)((right - left)*MathObject.random());
|
|
LateBinding.SwapValues(this.obj, (uint)piv, (uint)right);
|
|
x = LateBinding.GetValueAtIndex(this.obj, (ulong)right);
|
|
long i = left - 1, j = right;
|
|
while(true){
|
|
do{
|
|
y = LateBinding.GetValueAtIndex(this.obj, (ulong)++i);
|
|
}while(i < j && this.Compare(x, y) >= 0);
|
|
do{
|
|
y = LateBinding.GetValueAtIndex(this.obj, (ulong)--j);
|
|
}while(j > i && this.Compare(x, y) <= 0);
|
|
if (i >= j)
|
|
break;
|
|
LateBinding.SwapValues(this.obj, (uint)i, (uint)j);
|
|
}
|
|
LateBinding.SwapValues(this.obj, (uint)i, (uint)right);
|
|
this.SortObject(left, i-1);
|
|
this.SortObject(i+1, right);
|
|
}
|
|
}
|
|
|
|
internal void SortArray(int left, int right){
|
|
ArrayObject array = (ArrayObject)this.obj;
|
|
Object x, y;
|
|
if (right > left){
|
|
int piv = left + (int)((right - left)*MathObject.random());
|
|
x = array.denseArray[piv];
|
|
array.denseArray[piv] = array.denseArray[right];
|
|
array.denseArray[right] = x;
|
|
int i = left - 1, j = right;
|
|
while(true){
|
|
do{
|
|
y = array.denseArray[++i];
|
|
}while(i < j && this.Compare(x, y) >= 0);
|
|
do{
|
|
y = array.denseArray[--j];
|
|
}while(j > i && this.Compare(x, y) <= 0);
|
|
if (i >= j)
|
|
break;
|
|
QuickSort.Swap(array.denseArray, i, j);
|
|
}
|
|
QuickSort.Swap(array.denseArray, i, right);
|
|
this.SortArray(left, i-1);
|
|
this.SortArray(i+1, right);
|
|
}
|
|
}
|
|
|
|
private static void Swap(Object[] array, int i, int j){
|
|
Object temp = array[i];
|
|
array[i] = array[j];
|
|
array[j] = temp;
|
|
}
|
|
|
|
}
|
|
}
|