The Labs \ Source Viewer \ SSCLI \ Microsoft.JScript \ ArrayObject

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. namespace Microsoft.JScript
  16. {
  17.    
  18.     using System;
  19.     using System.Collections;
  20.     using System.Reflection;
  21.     using System.Diagnostics;
  22.     using System.Globalization;
  23.    
  24.     public class ArrayObject : JSObject
  25.     {
  26.         internal const int MaxIndex = 100000;
  27.         internal const int MinDenseSize = 128;
  28.        
  29.         internal uint len;
  30.         internal object[] denseArray;
  31.         internal uint denseArrayLength;
  32.        
  33.         internal ArrayObject(ScriptObject prototype) : base(prototype)
  34.         {
  35.             this.len = 0;
  36.             this.denseArray = null;
  37.             this.denseArrayLength = 0;
  38.             this.noExpando = false;
  39.         }
  40.        
  41.         internal ArrayObject(ScriptObject prototype, Type subType) : base(prototype, subType)
  42.         {
  43.             this.len = 0;
  44.             this.denseArray = null;
  45.             this.denseArrayLength = 0;
  46.             this.noExpando = false;
  47.         }
  48.        
  49.         static internal long Array_index_for(object index)
  50.         {
  51.             if (index is Int32)
  52.                 return (int)index;
  53.             IConvertible ic = Convert.GetIConvertible(index);
  54.             switch (Convert.GetTypeCode(index, ic)) {
  55.                 case TypeCode.Char:
  56.                 case TypeCode.SByte:
  57.                 case TypeCode.Byte:
  58.                 case TypeCode.Int16:
  59.                 case TypeCode.UInt16:
  60.                 case TypeCode.Int32:
  61.                 case TypeCode.UInt32:
  62.                 case TypeCode.Int64:
  63.                 case TypeCode.UInt64:
  64.                 case TypeCode.Decimal:
  65.                 case TypeCode.Single:
  66.                 case TypeCode.Double:
  67.                     double d = ic.ToDouble(null);
  68.                     long l = (long)d;
  69.                     if (l >= 0 && (double)l == d)
  70.                         return l;
  71.                     break;
  72.             }
  73.             return -1;
  74.         }
  75.        
  76.         static internal long Array_index_for(string name)
  77.         {
  78.             int len = name.Length;
  79.             if (len <= 0)
  80.                 return -1;
  81.             char ch = name[0];
  82.             if (ch < '1' || ch > '9')
  83.                 if (ch == '0' && len == 1)
  84.                     return 0;
  85.                 else
  86.                     return -1;
  87.             long result = ch - '0';
  88.             for (int i = 1; i < len; i++) {
  89.                 ch = name[i];
  90.                 if (ch < '0' || ch > '9')
  91.                     return -1;
  92.                 result = result * 10 + (ch - '0');
  93.                 if (result > UInt32.MaxValue)
  94.                     return -1;
  95.             }
  96.             return result;
  97.         }
  98.        
  99.         internal virtual void Concat(ArrayObject source)
  100.         {
  101.             uint sourceLength = source.len;
  102.             if (sourceLength == 0)
  103.                 return;
  104.             uint oldLength = this.len;
  105.             this.SetLength(oldLength + (ulong)sourceLength);
  106.             uint slen = sourceLength;
  107.             if (!(source is ArrayWrapper) && sourceLength > source.denseArrayLength)
  108.                 slen = source.denseArrayLength;
  109.             uint j = oldLength;
  110.             for (uint i = 0; i < slen; i++)
  111.                 this.SetValueAtIndex(j++, source.GetValueAtIndex(i));
  112.             if (slen == sourceLength)
  113.                 return;
  114.             //Iterate over the sparse indices of source
  115.             IDictionaryEnumerator e = source.NameTable.GetEnumerator();
  116.             while (e.MoveNext()) {
  117.                 long i = ArrayObject.Array_index_for(e.Key.ToString());
  118.                 if (i >= 0)
  119.                     this.SetValueAtIndex(oldLength + (uint)i, ((JSField)e.Value).GetValue(null));
  120.             }
  121.         }
  122.        
  123.         internal virtual void Concat(object value)
  124.         {
  125.             Array arr = value as Array;
  126.             if (arr != null && arr.Rank == 1)
  127.                 this.Concat(new ArrayWrapper(ArrayPrototype.ob, arr, true));
  128.             else {
  129.                 uint oldLength = this.len;
  130.                 this.SetLength(1 + (ulong)oldLength);
  131.                 this.SetValueAtIndex(oldLength, value);
  132.             }
  133.         }
  134.        
  135.         internal override bool DeleteMember(string name)
  136.         {
  137.             long i = ArrayObject.Array_index_for(name);
  138.             if (i >= 0)
  139.                 return this.DeleteValueAtIndex((uint)i);
  140.             else
  141.                 return base.DeleteMember(name);
  142.         }
  143.        
  144.         internal virtual bool DeleteValueAtIndex(uint index)
  145.         {
  146.             if (index < this.denseArrayLength)
  147.                 if (this.denseArray[(int)index] is Missing)
  148.                     return false;
  149.                 else {
  150.                     this.denseArray[(int)index] = Missing.Value;
  151.                     return true;
  152.                 }
  153.             else
  154.                 return base.DeleteMember(index.ToString(CultureInfo.InvariantCulture));
  155.         }
  156.        
  157.         private void DeleteRange(uint start, uint end)
  158.         {
  159.             uint denseEnd = this.denseArrayLength;
  160.             if (denseEnd > end)
  161.                 denseEnd = end;
  162.             for (; start < denseEnd; start++)
  163.                 denseArray[(int)start] = Missing.Value;
  164.             if (denseEnd == end)
  165.                 return;
  166.             //Go through the field table entries, deleting those with names that are indices between start and end
  167.             IDictionaryEnumerator e = this.NameTable.GetEnumerator();
  168.             ArrayList arr = new ArrayList(this.name_table.count);
  169.             while (e.MoveNext()) {
  170.                 long i = ArrayObject.Array_index_for(e.Key.ToString());
  171.                 if (i >= start && i <= end)
  172.                     arr.Add(e.Key);
  173.             }
  174.             IEnumerator ae = arr.GetEnumerator();
  175.             while (ae.MoveNext())
  176.                 this.DeleteMember((string)ae.Current);
  177.         }
  178.        
  179.         internal override string GetClassName()
  180.         {
  181.             return "Array";
  182.         }
  183.        
  184.         internal override object GetDefaultValue(PreferredType preferred_type)
  185.         {
  186.             if (this.GetParent() is LenientArrayPrototype)
  187.                 return base.GetDefaultValue(preferred_type);
  188.             if (preferred_type == PreferredType.String) {
  189.                 if (!this.noExpando) {
  190.                     object field = this.NameTable["toString"];
  191.                     if (field != null)
  192.                         return base.GetDefaultValue(preferred_type);
  193.                 }
  194.                 return ArrayPrototype.toString(this);
  195.             }
  196.             else if (preferred_type == PreferredType.LocaleString) {
  197.                 if (!this.noExpando) {
  198.                     object field = this.NameTable["toLocaleString"];
  199.                     if (field != null)
  200.                         return base.GetDefaultValue(preferred_type);
  201.                 }
  202.                 return ArrayPrototype.toLocaleString(this);
  203.             }
  204.             else {
  205.                 if (!this.noExpando) {
  206.                     object field = this.NameTable["valueOf"];
  207.                     if (field == null && preferred_type == PreferredType.Either)
  208.                         field = this.NameTable["toString"];
  209.                     if (field != null)
  210.                         return base.GetDefaultValue(preferred_type);
  211.                 }
  212.                 return ArrayPrototype.toString(this);
  213.             }
  214.         }
  215.        
  216.        
  217.         internal override void GetPropertyEnumerator(ArrayList enums, ArrayList objects)
  218.         {
  219.             if (this.field_table == null)
  220.                 this.field_table = new ArrayList();
  221.             enums.Add(new ArrayEnumerator(this, new ListEnumerator(this.field_table)));
  222.             objects.Add(this);
  223.             if (this.parent != null)
  224.                 this.parent.GetPropertyEnumerator(enums, objects);
  225.         }
  226.        
  227.         internal override object GetValueAtIndex(uint index)
  228.         {
  229.             if (index < this.denseArrayLength) {
  230.                 object result = this.denseArray[(int)index];
  231.                 if (result != Missing.Value)
  232.                     return result;
  233.             }
  234.             return base.GetValueAtIndex(index);
  235.         }
  236.        
  237.         #if !DEBUG
  238.         [DebuggerStepThroughAttribute()]
  239.         [DebuggerHiddenAttribute()]
  240.         #endif
  241.         internal override object GetMemberValue(string name)
  242.         {
  243.             long index = ArrayObject.Array_index_for(name);
  244.             if (index < 0)
  245.                 return base.GetMemberValue(name);
  246.             else
  247.                 return this.GetValueAtIndex((uint)index);
  248.         }
  249.        
  250.         public virtual object length {
  251.             get {
  252.                 //Convert the length from a uint to either an int or a double. The latter two are special cased in arith operations.
  253.                 if (this.len < Int32.MaxValue)
  254.                     return (int)this.len;
  255.                 else
  256.                     return (double)this.len;
  257.             }
  258.             set {
  259.                 IConvertible ic = Convert.GetIConvertible(value);
  260.                 uint newLength = Convert.ToUint32(value, ic);
  261.                 if ((double)newLength != Convert.ToNumber(value, ic))
  262.                     throw new JScriptException(JSError.ArrayLengthAssignIncorrect);
  263.                 this.SetLength(newLength);
  264.             }
  265.         }
  266.        
  267.         private void Realloc(uint newLength)
  268.         {
  269.             Debug.PreCondition(this.denseArrayLength >= this.len);
  270.             Debug.PreCondition(newLength <= ArrayObject.MaxIndex);
  271.             uint oldDenseLength = this.denseArrayLength;
  272.             uint newDenseLength = oldDenseLength * 2;
  273.             if (newDenseLength < newLength)
  274.                 newDenseLength = newLength;
  275.             object[] newArray = new object[(int)newDenseLength];
  276.             if (oldDenseLength > 0)
  277.                 ArrayObject.Copy(this.denseArray, newArray, (int)oldDenseLength);
  278.             for (int i = (int)oldDenseLength; i < newDenseLength; i++)
  279.                 newArray[i] = Missing.Value;
  280.             this.denseArray = newArray;
  281.             this.denseArrayLength = newDenseLength;
  282.         }
  283.        
  284.         private void SetLength(ulong newLength)
  285.         {
  286.             uint oldLength = this.len;
  287.             if (newLength < oldLength)
  288.                 this.DeleteRange((uint)newLength, oldLength);
  289.             else if (newLength > UInt32.MaxValue)
  290.                 throw new JScriptException(JSError.ArrayLengthAssignIncorrect);
  291.             else if (newLength > this.denseArrayLength && oldLength <= this.denseArrayLength && newLength <= ArrayObject.MaxIndex && (newLength <= ArrayObject.MinDenseSize || newLength <= oldLength * 2))
  292.                 //The array is dense, try to keep it dense
  293.                 //Small enough to keep dense
  294.                 //Close enough to existing dense part
  295.                 this.Realloc((uint)newLength);
  296.             this.len = (uint)newLength;
  297.         }
  298.        
  299.         #if !DEBUG
  300.         [DebuggerStepThroughAttribute()]
  301.         [DebuggerHiddenAttribute()]
  302.         #endif
  303.         internal override void SetMemberValue(string name, object value)
  304.         {
  305.             if (name.Equals("length")) {
  306.                 this.length = value;
  307.                 return;
  308.             }
  309.             long index = ArrayObject.Array_index_for(name);
  310.             if (index < 0)
  311.                 base.SetMemberValue(name, value);
  312.             else
  313.                 this.SetValueAtIndex((uint)index, value);
  314.         }
  315.        
  316.         internal override void SetValueAtIndex(uint index, object value)
  317.         {
  318.             if (index >= this.len && index < UInt32.MaxValue)
  319.                 this.SetLength(index + 1);
  320.             if (index < this.denseArrayLength)
  321.                 this.denseArray[(int)index] = value;
  322.             else
  323.                 base.SetMemberValue(index.ToString(CultureInfo.InvariantCulture), value);
  324.         }
  325.        
  326.         internal virtual object Shift()
  327.         {
  328.             object res = null;
  329.             uint thisLength = this.len;
  330.             if (thisLength == 0)
  331.                 return res;
  332.             uint lastItemInDense = (this.denseArrayLength >= thisLength) ? thisLength : this.denseArrayLength;
  333.             if (lastItemInDense > 0) {
  334.                 res = this.denseArray[0];
  335.                 ArrayObject.Copy(this.denseArray, 1, this.denseArray, 0, (int)(lastItemInDense - 1));
  336.             }
  337.             else
  338.                 res = base.GetValueAtIndex(0);
  339.             for (uint i = lastItemInDense; i < thisLength; i++)
  340.                 this.SetValueAtIndex(i - 1, this.GetValueAtIndex(i));
  341.             this.SetValueAtIndex(thisLength - 1, Missing.Value);
  342.             SetLength(thisLength - 1);
  343.             if (res is Missing)
  344.                 return null;
  345.             return res;
  346.         }
  347.        
  348.         internal virtual void Sort(ScriptFunction compareFn)
  349.         {
  350.             QuickSort qs = new QuickSort(this, compareFn);
  351.             uint length = this.len;
  352.             if (length <= this.denseArrayLength)
  353.                 qs.SortArray(0, (int)length - 1);
  354.             else
  355.                 qs.SortObject(0, length - 1);
  356.         }
  357.        
  358.         internal virtual void Splice(uint start, uint deleteCount, object[] args, ArrayObject outArray, uint oldLength, uint newLength)
  359.         {
  360.             if (oldLength > this.denseArrayLength) {
  361.                 SpliceSlowly(start, deleteCount, args, outArray, oldLength, newLength);
  362.                 return;
  363.             }
  364.             if (newLength > oldLength) {
  365.                 this.SetLength(newLength);
  366.                 if (newLength > this.denseArrayLength) {
  367.                     SpliceSlowly(start, deleteCount, args, outArray, oldLength, newLength);
  368.                     return;
  369.                 }
  370.             }
  371.             if (deleteCount > oldLength)
  372.                 deleteCount = oldLength;
  373.             if (deleteCount > 0)
  374.                 ArrayObject.Copy(this.denseArray, (int)start, outArray.denseArray, 0, (int)deleteCount);
  375.             if (oldLength > 0)
  376.                 ArrayObject.Copy(this.denseArray, (int)(start + deleteCount), this.denseArray, (int)(start)+args.Length, (int)(oldLength - start - deleteCount));
  377.             if (args != null) {
  378.                 int n = args.Length;
  379.                 if (n > 0)
  380.                     ArrayObject.Copy(args, 0, this.denseArray, (int)start, n);
  381.                 if (n < deleteCount)
  382.                     this.SetLength(newLength);
  383.             }
  384.             else if (deleteCount > 0)
  385.                 this.SetLength(newLength);
  386.         }
  387.        
  388.         protected void SpliceSlowly(uint start, uint deleteCount, object[] args, ArrayObject outArray, uint oldLength, uint newLength)
  389.         {
  390.             for (uint i = 0; i < deleteCount; i++)
  391.                 outArray.SetValueAtIndex(i, this.GetValueAtIndex(i + start));
  392.             uint n = oldLength - start - deleteCount;
  393.             if (newLength < oldLength) {
  394.                 for (uint i = 0; i < n; i++)
  395.                     this.SetValueAtIndex(i + start + (uint)args.Length, this.GetValueAtIndex(i + start + deleteCount));
  396.                 this.SetLength(newLength);
  397.             }
  398.             else {
  399.                 if (newLength > oldLength)
  400.                     this.SetLength(newLength);
  401.                 for (uint i = n; i > 0; i--)
  402.                     this.SetValueAtIndex(i + start + (uint)args.Length - 1, this.GetValueAtIndex(i + start + deleteCount - 1));
  403.             }
  404.             int m = args == null ? 0 : args.Length;
  405.             for (uint i = 0; i < m; i++)
  406.                 this.SetValueAtIndex(i + start, args[i]);
  407.         }
  408.        
  409.         internal override void SwapValues(uint pi, uint qi)
  410.         {
  411.             if (pi > qi)
  412.                 this.SwapValues(qi, pi);
  413.             else if (pi >= this.denseArrayLength)
  414.                 base.SwapValues(pi, qi);
  415.             else {
  416.                 object temp = this.denseArray[(int)pi];
  417.                 this.denseArray[(int)pi] = this.GetValueAtIndex(qi);
  418.                 if (temp == Missing.Value)
  419.                     this.DeleteValueAtIndex(qi);
  420.                 else
  421.                     this.SetValueAtIndex(qi, temp);
  422.             }
  423.         }
  424.        
  425.         internal virtual object[] ToArray()
  426.         {
  427.             int thisLength = (int)this.len;
  428.             if (thisLength == 0)
  429.                 return new object[0];
  430.             else if (thisLength == this.denseArrayLength)
  431.                 return this.denseArray;
  432.             else if (thisLength < this.denseArrayLength) {
  433.                 object[] result = new object[thisLength];
  434.                 ArrayObject.Copy(this.denseArray, 0, result, 0, thisLength);
  435.                 return result;
  436.             }
  437.             else {
  438.                 object[] result = new object[thisLength];
  439.                 ArrayObject.Copy(this.denseArray, 0, result, 0, (int)this.denseArrayLength);
  440.                 for (uint i = this.denseArrayLength; i < thisLength; i++)
  441.                     result[i] = this.GetValueAtIndex(i);
  442.                 return result;
  443.             }
  444.         }
  445.        
  446.         internal virtual Array ToNativeArray(Type elementType)
  447.         {
  448.             uint n = this.len;
  449.             if (n > Int32.MaxValue)
  450.                 throw new JScriptException(JSError.OutOfMemory);
  451.             if (elementType == null)
  452.                 elementType = typeof(object);
  453.             uint m = this.denseArrayLength;
  454.             if (m > n)
  455.                 m = n;
  456.             Array result = Array.CreateInstance(elementType, (int)n);
  457.             for (int i = 0; i < m; i++)
  458.                 result.SetValue(Convert.CoerceT(this.denseArray[i], elementType), i);
  459.             for (int i = (int)m; i < n; i++)
  460.                 result.SetValue(Convert.CoerceT(this.GetValueAtIndex((uint)i), elementType), i);
  461.             return result;
  462.         }
  463.        
  464.         static internal void Copy(object[] source, object[] target, int n)
  465.         {
  466.             ArrayObject.Copy(source, 0, target, 0, n);
  467.         }
  468.        
  469.         static internal void Copy(object[] source, int i, object[] target, int j, int n)
  470.         {
  471.             if (i < j)
  472.                 for (int m = n - 1; m >= 0; m--)
  473.                     target[j + m] = source[i + m];
  474.             else
  475.                 for (int m = 0; m < n; m++)
  476.                     target[j + m] = source[i + m];
  477.         }
  478.        
  479.         internal virtual ArrayObject Unshift(object[] args)
  480.         {
  481.             Debug.PreCondition(args != null && args.Length > 0);
  482.             uint oldLength = this.len;
  483.             int numArgs = args.Length;
  484.             ulong newLength = oldLength + (ulong)numArgs;
  485.             this.SetLength(newLength);
  486.             if (newLength <= this.denseArrayLength) {
  487.                 for (int i = (int)(oldLength - 1); i >= 0; i--)
  488.                     this.denseArray[i + numArgs] = this.denseArray[i];
  489.                 ArrayObject.Copy(args, 0, this.denseArray, 0, args.Length);
  490.             }
  491.             else {
  492.                 for (long i = oldLength - 1; i >= 0; i--)
  493.                     this.SetValueAtIndex((uint)(i + numArgs), this.GetValueAtIndex((uint)i));
  494.                 for (uint i = 0; i < numArgs; i++)
  495.                     this.SetValueAtIndex(i, args[i]);
  496.             }
  497.             return this;
  498.         }
  499.        
  500.        
  501.         // For temporary use of the debugger - a bug in the COM+ debug API's
  502.         // causes 64 bit literal values to be not passed properly as an argument
  503.         // to a func-eval.
  504.         internal object DebugGetValueAtIndex(int index)
  505.         {
  506.             return this.GetValueAtIndex((uint)index);
  507.         }
  508.        
  509.         internal void DebugSetValueAtIndex(int index, object value)
  510.         {
  511.             this.SetValueAtIndex((uint)index, value);
  512.         }
  513.        
  514.     }
  515.    
  516.     internal sealed class QuickSort
  517.     {
  518.         internal ScriptFunction compareFn;
  519.         internal object obj;
  520.        
  521.         internal QuickSort(object obj, ScriptFunction compareFn)
  522.         {
  523.             this.compareFn = compareFn;
  524.             this.obj = obj;
  525.         }
  526.        
  527.         private int Compare(object x, object y)
  528.         {
  529.             if (x == null || x is Missing)
  530.                 if (y == null || y is Missing)
  531.                     return 0;
  532.                 else
  533.                     return 1;
  534.             else if (y == null || y is Missing)
  535.                 return -1;
  536.             if (this.compareFn != null) {
  537.                 double result = Convert.ToNumber(this.compareFn.Call(new object[] {x, y}, null));
  538.                 if (result != result)
  539.                     throw new JScriptException(JSError.NumberExpected);
  540.                 return (int)Runtime.DoubleToInt64(result);
  541.             }
  542.             else
  543.                 return String.CompareOrdinal(Convert.ToString(x), Convert.ToString(y));
  544.         }
  545.        
  546.         internal void SortObject(long left, long right)
  547.         {
  548.             //left and right are longs to allow for values < 0. Their positives values are always < UInt32.MaxValue.
  549.             object x;
  550.             object y;
  551.             if (right > left) {
  552.                 long piv = left + (long)((right - left) * MathObject.random());
  553.                 LateBinding.SwapValues(this.obj, (uint)piv, (uint)right);
  554.                 x = LateBinding.GetValueAtIndex(this.obj, (ulong)right);
  555.                 long i = left - 1;
  556.                 long j = right;
  557.                 while (true) {
  558.                     do {
  559.                         y = LateBinding.GetValueAtIndex(this.obj, (ulong)++i);
  560.                     }
  561.                     while (i < j && this.Compare(x, y) >= 0);
  562.                     do {
  563.                         y = LateBinding.GetValueAtIndex(this.obj, (ulong)--j);
  564.                     }
  565.                     while (j > i && this.Compare(x, y) <= 0);
  566.                     if (i >= j)
  567.                         break;
  568.                     LateBinding.SwapValues(this.obj, (uint)i, (uint)j);
  569.                 }
  570.                 LateBinding.SwapValues(this.obj, (uint)i, (uint)right);
  571.                 this.SortObject(left, i - 1);
  572.                 this.SortObject(i + 1, right);
  573.             }
  574.         }
  575.        
  576.         internal void SortArray(int left, int right)
  577.         {
  578.             ArrayObject array = (ArrayObject)this.obj;
  579.             object x;
  580.             object y;
  581.             if (right > left) {
  582.                 int piv = left + (int)((right - left) * MathObject.random());
  583.                 x = array.denseArray[piv];
  584.                 array.denseArray[piv] = array.denseArray[right];
  585.                 array.denseArray[right] = x;
  586.                 int i = left - 1;
  587.                 int j = right;
  588.                 while (true) {
  589.                     do {
  590.                         y = array.denseArray[++i];
  591.                     }
  592.                     while (i < j && this.Compare(x, y) >= 0);
  593.                     do {
  594.                         y = array.denseArray[--j];
  595.                     }
  596.                     while (j > i && this.Compare(x, y) <= 0);
  597.                     if (i >= j)
  598.                         break;
  599.                     QuickSort.Swap(array.denseArray, i, j);
  600.                 }
  601.                 QuickSort.Swap(array.denseArray, i, right);
  602.                 this.SortArray(left, i - 1);
  603.                 this.SortArray(i + 1, right);
  604.             }
  605.         }
  606.        
  607.         private static void Swap(object[] array, int i, int j)
  608.         {
  609.             object temp = array[i];
  610.             array[i] = array[j];
  611.             array[j] = temp;
  612.         }
  613.        
  614.     }
  615. }

Developer Fusion