/* **********************************************************************************
 *
 * Copyright (c) Microsoft Corporation. All rights reserved.
 *
 * This source code is subject to terms and conditions of the Shared Source License
 * for IronPython. A copy of the license can be found in the License.html file
 * at the root of this distribution. If you can not locate the Shared Source License
 * for IronPython, please send an email to ironpy@microsoft.com.
 * By using this source code in any fashion, you are agreeing to be bound by
 * the terms of the Shared Source License for IronPython.
 *
 * You must not remove this notice, or any other, from this software.
 *
 * **********************************************************************************/

using System;
using System.Threading;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;

using System.Reflection;
using System.Reflection.Emit;

using IronPython.Modules;
using IronPython.Compiler;

using IronMath;

namespace IronPython.Runtime {

    /// <summary>
    /// Contains functions that are called directly from
    /// generated code to perform low-level runtime functionality.
    /// </summary>
    public static partial class Ops {
        private const int MIN_CACHE = -100;
        private const int MAX_CACHE = 1000;

        [ThreadStatic]
        private static ArrayList InfiniteCmp;
        [ThreadStatic]
        private static ArrayList InfiniteRepr;

        public static readonly object NotImplemented = "<NotImplemented>"; //!!! need really singleton objects
        public static readonly object Ellipsis = "..."; //!!!
        public static readonly object TRUE = true;
        public static readonly object FALSE = false;

        internal static SystemState systemState;

        private static readonly object[] EMPTY = new object[0];
        private static readonly object[] cache = new object[MAX_CACHE - MIN_CACHE];
        private static readonly string[] chars = new string[255];
        private static ReflectedType StringType;
        private static Dictionary<Type, DynamicType> dynamicTypes = MakeDynamicTypesTable();
        // The cache for dynamically generated delegates.
        private static Publisher<Type, MethodInfo> dynamicDelegates = new Publisher<Type, MethodInfo>();


        public static object[] MakeArray(object o1) { return new object[] { o1 }; }
        public static object[] MakeArray(object o1, object o2) { return new object[] { o1, o2 }; }


        public static List MakeList() { return List.MakeEmptyList(10); }

        public static List MakeList(params object[] items) {
            return new List(items);
        }

        public static Tuple MakeTuple(params object[] items) {
            return Tuple.MakeTuple(items);
        }

        public static Tuple MakeExpandableTuple(params object[] items) {
            return Tuple.MakeExpandableTuple(items);
        }

        public static object MakeSlice(object start, object stop, object step) {
            return new Slice(start, stop, step);
        }

        public static IronMath.BigInteger MakeIntegerFromHex(string s) {
            return LiteralParser.ParseBigInteger(s, 16);
        }

        public static Dict MakeDict(int size) {
            return new Dict(size);
        }

        public static bool IsTrue(object o) {
            if (o == null) return false;

            return Converter.ConvertToBoolean(o);
        }

        //        public static IList GetList(object o) {
        //            return (IList)o;
        //        }

        public static ArrayList GetReprInfinite() {
            if (InfiniteRepr == null) {
                InfiniteRepr = new ArrayList();
            }
            return InfiniteRepr;
        }

        public static ArrayList GetCmpInfinite() {
            if (InfiniteCmp == null) {
                InfiniteCmp = new ArrayList();
            }
            return InfiniteCmp;
        }

        public static string StringRepr(object o) {
            if (o == null) return "None";
            //!!! this is performance important
            string s = o as string;
            if (s != null) return StringOps.Quote(s);
            if (o is int) return o.ToString();
            if (o is long) return ((long)o).ToString() + "L";
            if (o is BigInteger) return ((BigInteger)o).ToString() + "L";
            if (o is double) return FloatOps.ToString((double)o);
            if (o is float) return FloatOps.ToString((float)o);

            PerfTrack.NoteEvent(PerfTrack.Categories.Temporary, "Repr " + o.GetType().FullName);

            // could be a container object, we need to detect recursion, but only
            // for our own built-in types that we're aware of.  The user can setup
            // infinite recursion in their own class if they want.
            ICodeFormattable f = o as ICodeFormattable;
            if (f != null) {
                ArrayList infinite = GetAndCheckInfinite(o);
                if (infinite == null) return GetInfiniteRepr(o);
                int index = infinite.Add(o);
                try {
                    return f.ToCodeString();
                } finally {
                    System.Diagnostics.Debug.Assert(index == infinite.Count - 1);
                    infinite.RemoveAt(index);
                }
            }

            Array a = o as Array;
            if (a != null) {
                ArrayList infinite = GetAndCheckInfinite(o);
                if (infinite == null) return GetInfiniteRepr(o);
                int index = infinite.Add(o);
                try {
                    return ArrayOps.CodeRepresentation(a);
                } finally {
                    System.Diagnostics.Debug.Assert(index == infinite.Count - 1);
                    infinite.RemoveAt(index);
                }
            }

            return GetDynamicType(o).Repr(o);
        }

        private static ArrayList GetAndCheckInfinite(object o) {
            ArrayList infinite = GetReprInfinite();
            foreach (object o2 in infinite) {
                if (o == o2) {
                    return null;
                }
            }
            return infinite;
        }

        private static string GetInfiniteRepr(object o) {
            object keys;
            return o is List ? "[...]" :
                o is Dict ? "{...}" :
                Ops.TryGetAttr(o, SymbolTable.Keys, out keys) ? "{...}" : // user dictionary
                "...";
        }

        public static string ToString(object o) {
            if (o == null) return "None";
            else if (o is double) return FloatOps.ToString((double)o);
            else if (o is float) return FloatOps.ToString((float)o);
            return o.ToString();
        }


        public static object Repr(object o) {
            return Ops.ToPython(StringRepr(o));
        }

        static Ops() {
            for (int i = 0; i < (MAX_CACHE - MIN_CACHE); i++) {
                cache[i] = (object)(i + MIN_CACHE);
            }

            for (char ch = (char)0; ch < 255; ch++) {
                chars[ch] = new string(ch, 1);
            }
        }

        public static string Char2String(char ch) {
            if (ch < 255) return chars[ch];
            return new string(ch, 1);
        }

        public static object Bool2Object(bool value) {
            return value ? TRUE : FALSE;
        }

        public static object Int2ByteOrInt(object val) {
            if (val is int) {
                int ival = (int)val;
                if (ival < 256 && ival >= 0) return ((byte)ival);
            }
            return val;
        }

        public static object Int2Object(int value) {
            // caches improves pystone by ~5-10% on MS .Net 1.1, this is a very integer intense app
            if (value < MAX_CACHE && value >= MIN_CACHE) {
                return cache[value - MIN_CACHE];
            }
            return (object)value;
        }

        public static object Long2Object(long value) {
            return value;  // just use standard boxing conversion here
        }

        public static Delegate GetDelegate(object o, Type delegateType) {
            Delegate handler = o as Delegate;

            if (handler != null) return handler;
            
            // if we have a python function make sure it's compatible...
            PythonFunction fo = o as PythonFunction;
            if (fo != null &&
                fo.ArgCount < delegateType.GetMethod("Invoke").GetParameters().Length &&
                !(fo is FunctionN)) {
                // the target is no good for this delegate - we don't have enough
                // parameters.
                return null;
            }

            //
            //  This hashtable is keyed off of the delegate type.
            //  More optimal solution is to key it off of the delegate signature only.
            //
            MethodInfo methodInfo = dynamicDelegates.GetOrCreateValue(delegateType,
                delegate() {
                    // creation code
                    return CreateNewDelegate(delegateType);
                });

            return CodeGen.CreateDelegate(methodInfo, delegateType, o);
        }

        private static MethodInfo CreateNewDelegate(Type delegateType) {
            MethodInfo handlerMethod = delegateType.GetMethod("Invoke");
            ParameterInfo[] handlerParams = handlerMethod.GetParameters();

            Type[] delegateParams = new Type[handlerParams.Length + 1];
            delegateParams[0] = typeof(object);
            for (int parameter = 0; parameter < handlerParams.Length; parameter++) {
                delegateParams[parameter + 1] = handlerParams[parameter].ParameterType;
            }
            CodeGen cg = OutputGenerator.Snippets.DefineDynamicMethod(delegateType.ToString(),
                                                                      handlerMethod.ReturnType,
                                                                      delegateParams);

            if (handlerParams.Length <= Ops.MaximumCallArgs) {
                Type[] callParams = CompilerHelpers.MakeRepeatedArray(typeof(object), handlerParams.Length + 1);
                cg.EmitArgGet(0);
                for (int parameter = 0; parameter < handlerParams.Length; parameter++) {
                    ParameterInfo pi = handlerParams[parameter];
                    cg.EmitArgGet(parameter + 1);
                    cg.EmitCastToObject(pi.ParameterType);
                }
                cg.EmitCall(typeof(Ops), "Call", callParams);
            } else {
                cg.EmitArgGet(0);                               //  Get the first argument, this one goes directly
                cg.EmitInt(handlerParams.Length);               //  Rest of arguments go in an object array
                cg.Emit(OpCodes.Newarr, typeof(object));    //   ... create the array

                for (int parameter = 0; parameter < handlerParams.Length; parameter++) {
                    ParameterInfo pi = handlerParams[parameter];
                    cg.Emit(OpCodes.Dup);                                   //  duplicate array handle
                    cg.EmitInt(parameter);                                      //  load index into the array
                    cg.EmitArgGet(parameter + 1);                               //  load the value - from the parameter
                    cg.EmitCastToObject(pi.ParameterType);    //  cast to object
                    cg.Emit(OpCodes.Stelem_Ref);                            //  store it in the array
                }

                cg.EmitCall(typeof(Ops), "Call",
                    new Type[] { typeof(object), typeof(object[]) });
            }

            cg.EmitCastFromObject(handlerMethod.ReturnType);
            cg.Emit(OpCodes.Ret);

            return cg.CreateDelegateMethodInfo(); 
        }

        public static object ConvertTo(object o, Type toType) {
            return Converter.Convert(o, toType);
        }

        public static object ToPython(Type type, object o) {
            return ToPython(o);
        }

        public static object ToPython(object o) {
            if (o == null) return o;
            if (o is char) return Char2String((char)o);
            if (o.GetType().IsCOMObject && o.GetType().FullName == "System.__ComObject") {
                return ComObject.ObjectToComObject(o);
            }
            return o;
        }

        public static object ToPython(string s) {
            return s;
        }

        public static object Plus(object o) {
            object call;

            if (o is int) return o;
            else if (o is double) return o;
            else if (o is BigInteger) return o;
            else if (o is Complex64) return o;
            else if (o is long) return o;
            else if (o is float) return o;
            else if (Ops.TryGetAttr(o, SymbolTable.Positive, out call)) {
                return Ops.Call(call);
            }

            throw Ops.TypeError("Bad operand for unary +");
        }

        public static object Negate(object o) {
            if (o is int) return IntOps.Negate((int)o);
            else if (o is double) return FloatOps.Negate((double)o);
            else if (o is long) return Int64Ops.Negate((long)o);
            else if (o is BigInteger) return LongOps.Negate((BigInteger)o);
            else if (o is Complex64) return ComplexOps.Negate((Complex64)o);
            else if (o is float) return FloatOps.Negate((float)o);

            object ret = GetDynamicType(o).Negate(o);
            if (ret != Ops.NotImplemented) return ret;

            throw Ops.TypeError("bad operand type for unary -");
        }

        public static object OnesComplement(object o) {
            if (o is int) return ~(int)o;
            if (o is long) return ~(long)o;
            if (o is BigInteger) return ~((BigInteger)o);

            object ret = GetDynamicType(o).OnesComplement(o);
            if (ret != Ops.NotImplemented) return ret;

            throw Ops.TypeError("bad operand type for unary ~");
        }

        public static object Not(object o) {
            return IsTrue(o) ? FALSE : TRUE;
        }


        public static object Is(object x, object y) {
            return x == y;
        }

        public static bool IsRetBool(object x, object y) {
            return x == y;
        }

        public static object IsNot(object x, object y) {
            return x != y;
        }

        public static bool IsNotRetBool(object x, object y) {
            return x != y;
        }

        public static object In(object x, object y) {
            if (y is IDictionary) {
                return Bool2Object(((IDictionary)y).Contains(x));
            }

            if (y is IList) {
                return Bool2Object(((IList)y).Contains(x));
            }

            if (y is string) {
                string s = x as string;
                if (s == null) {
                    throw TypeError("'in <string>' requires string as left operand");
                }
                return ((string)y).Contains(s) ? TRUE : FALSE;
            }

            object contains;
            if (Ops.TryGetAttr(y, SymbolTable.Contains, out contains)) {
                return Ops.IsTrue(Ops.Call(contains, x)) ? TRUE : FALSE;
            }

            IEnumerator e = GetEnumerator(y);
            while (e.MoveNext()) {
                if (Ops.EqualRetBool(e.Current, x)) return TRUE;
            }

            return FALSE;
        }

        public static bool InRetBool(object x, object y) {
            if (y is IDictionary) {
                return ((IDictionary)y).Contains(x);
            }

            if (y is IList) {
                return ((IList)y).Contains(x);
            }

            if (y is string) {
                string s = x as string;
                if (s == null) {
                    throw TypeError("'in <string>' requires string as left operand");
                }
                return ((string)y).Contains(s);
            }

            object contains;
            if (Ops.TryGetAttr(y, SymbolTable.Contains, out contains)) {
                return Ops.IsTrue(Ops.Call(contains, x));
            }

            IEnumerator e = GetEnumerator(y);
            while (e.MoveNext()) {
                if (Ops.EqualRetBool(e.Current, x)) return true;
            }

            return false;
        }

        public static object NotIn(object x, object y) {
            return Not(In(x, y));  //???
        }

        public static bool NotInRetBool(object x, object y) {
            return !InRetBool(x, y);  //???
        }

        //        public static object GetDynamicType1(object o) {
        //            IConvertible ic = o as IConvertible;
        //            if (ic != null) {
        //                switch (ic.GetTypeCode()) {
        //                    case TypeCode.Int32: return "int";
        //                    case TypeCode.Double: return "double";
        //                    default: throw new NotImplementedException();
        //                }
        //            } else {
        //                throw new NotImplementedException();
        //            }
        //        }
        //
        //        private static object[] oas = new object[] { "int", "double" };
        //
        //        public static object GetDynamicType2(object o) {
        //            Type ty = o.GetType();
        //            int hc = ty.GetHashCode();
        //
        //            return oas[hc%1];
        //        }

        private static Dictionary<Type, DynamicType> MakeDynamicTypesTable() {
            Dictionary<Type, DynamicType> ret = new Dictionary<Type, DynamicType>();

            StringType = new StringDynamicType();
            ret[typeof(string)] = StringType;
            ret[typeof(ExtensibleString)] = StringType;

            ret[typeof(object)] = ReflectedType.FromType(typeof(object), true);
            ret[typeof(int)] = IntOps.MakeDynamicType();
            ret[typeof(ExtensibleInt)] = ret[typeof(int)];

            ret[typeof(double)] = FloatOps.MakeDynamicType();
            ret[typeof(ExtensibleFloat)] = ret[typeof(double)];

            ret[typeof(BigInteger)] = LongOps.MakeDynamicType();

            ret[typeof(long)] = Int64Ops.MakeDynamicType((ReflectedType)ret[typeof(BigInteger)]);
            ret[typeof(bool)] = BoolOps.MakeDynamicType((ReflectedType)ret[typeof(int)]);
            ret[typeof(Dict)] = new DictDynamicType();
            ret[typeof(OldInstance)] = OldInstanceType.Instance;
            ret[typeof(Array)] = ArrayOps.MakeDynamicType();
            ret[typeof(Assembly)] = ReflectedAssemblyType.MakeDynamicType();
            ret[typeof(Complex64)] = ComplexOps.MakeDynamicType();
            ret[typeof(Decimal)] = DecimalOps.MakeDynamicType();

            return ret;
        }
        /*
        public static void RegisterDynamicType(Type ty, DynamicType dt) {
            //!!! check that we're not replacing a previous entry
            dynamicTypes[ty] = dt;
        }*/

        public static DynamicType GetDynamicTypeFromClsOnlyType(Type ty) {
            DynamicType ret;
            if (dynamicTypes.TryGetValue(ty, out ret)) return ret;

            ret = ReflectedType.FromClsOnlyType(ty);
            dynamicTypes[ty] = ret;
            return ret;
        }

        public static DynamicType GetDynamicTypeFromType(Type ty) {
            PerfTrack.NoteEvent(PerfTrack.Categories.DictInvoke, "TypeLookup " + ty.FullName);

            lock (dynamicTypes) {
                DynamicType ret;
                if (dynamicTypes.TryGetValue(ty, out ret)) return ret;

                ret = ReflectedType.FromType(ty);
                dynamicTypes[ty] = ret;
                return ret;
            }
        }

        public static DynamicType GetDynamicType(object o) {
            IDynamicObject dt = o as IDynamicObject;
            if (dt != null) return dt.GetDynamicType();

            if (o == null) return NoneType.InstanceOfNoneType;

            if (o is String) return StringType;

            Type ty = o.GetType();
            if (ty.IsCOMObject && o.GetType().FullName == "System.__ComObject") return ComType.DynamicType;

            return GetDynamicTypeFromType(ty);
        }

        public static bool EqualIsTrue(object x, int y) {
            if (x is int) return ((int)x) == y;

            return EqualRetBool(x, y);
        }

        private static bool TryCompare(object x, object y, out int res) {
            object cmpFunc;
            object ret;
            if (Ops.TryGetAttr(x, SymbolTable.Cmp, out cmpFunc)) {
                ret = Ops.Call(cmpFunc, y);
                if (ret is int) {
                    res = (int)ret;
                } else if (ret is ExtensibleInt) {
                    res = ((ExtensibleInt)ret).value;
                } else {
                    throw Ops.TypeError("comparison did not return an int");
                }
            } else if (Ops.TryGetAttr(y, SymbolTable.Cmp, out cmpFunc)) {
                ret = Ops.Call(cmpFunc, x);
                if (ret is int) {
                    res = (int)ret;
                } else if (ret is ExtensibleInt) {
                    res = ((ExtensibleInt)ret).value;
                } else {
                    throw Ops.TypeError("comparison did not return an int");
                }
            } else {
                res = 0;
                return false;
            }
            return true;
        }

        public static object Equal(object x, object y) {
            if (x == y) return TRUE;

            object ret = Ops.NotImplemented;
            if (x is int) {
                ret = IntOps.Equals((int)x, y);
            } else if (x is string) {
                ret = StringOps.Equals((string)x, y);
            } else if (x is double) {
                ret = FloatOps.Equals((double)x, y);
            } else if (x is BigInteger) {
                ret = LongOps.Equals((BigInteger)x, y);
            } else if (x is Complex64) {
                ret = ComplexOps.Equals((Complex64)x, y);
            } else if (x == null) {
                if (y == null) return true;
                else if (y.GetType().IsPrimitive || y is BigInteger) return false;
            } else if (x is bool) {
                ret = BoolOps.Equals((bool)x, y);
            } else if (x is ExtensibleInt) {
                ret = IntOps.Equals(((ExtensibleInt)x).value, y);
            } else if (x is ExtensibleString) {
                ret = StringOps.Equals(((ExtensibleString)x).Value, y);
            } else if (x is ExtensibleFloat) {
                ret = FloatOps.Equals(((ExtensibleFloat)x).value, y);
            } else if (x is byte) {
                ret = IntOps.Equals((int)(byte)x, y);
            } else if (x is long) {
                ret = Int64Ops.Equals((long)x, y);
            } else if (x is float) {
                ret = FloatOps.Equals((float)x, y);
            } else if (x is Enum) {
                ret = EnumOps.Equal(x, y);
            } else if (x is sbyte) {
                ret = IntOps.Equals((int)(sbyte)x, y);
            } else if (x is short) {
                ret = IntOps.Equals((int)(short)x, y);
            } else if (x is ushort) {
                ret = IntOps.Equals((int)(ushort)x, y);
            } else if (x is uint) {
                ret = LongOps.Equals(BigInteger.Create((uint)x), y);
            } else if (x is ulong) {
                ret = LongOps.Equals(BigInteger.Create((ulong)x), y);
            } else if (x is decimal) {
                ret = FloatOps.Equals((double)(decimal)x, y);
            }

            if (ret != Ops.NotImplemented) return ret;

            IPythonEquality ipe = x as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(y);
            if (ret != Ops.NotImplemented) return ret;

            ipe = y as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(x);
            if (ret != Ops.NotImplemented) return ret;

            ret = GetDynamicType(x).Equal(x, y);
            if (ret != Ops.NotImplemented) return ret;

            ret = GetDynamicType(y).Equal(y, x);
            if (ret != Ops.NotImplemented) return ret;

            return Bool2Object(x.Equals(y));
        }

        public static bool EqualRetBool(object x, object y) {
            if (x == y) return true;

            if (x is int) {
                return IntOps.EqualsRetBool((int)x, y);
            } else if (x is string) {
                return StringOps.EqualsRetBool((string)x, y);
            } else if (x is double) {
                return FloatOps.EqualsRetBool((double)x, y);
            } else if (x is BigInteger) {
                return LongOps.EqualsRetBool((BigInteger)x, y);
            } else if (x is Complex64) {
                return ComplexOps.EqualsRetBool((Complex64)x, y);
            } else if (x == null) {
                if (y == null) return true;
                else if (y.GetType().IsPrimitive || y is BigInteger) return false;
            } else if (x is bool) {
                return BoolOps.EqualsRetBool((bool)x, y);
            } else if (x is ExtensibleInt) {
                return IntOps.EqualsRetBool(((ExtensibleInt)x).value, y);
            } else if (x is ExtensibleString) {
                return StringOps.EqualsRetBool(((ExtensibleString)x).Value, y);
            } else if (x is ExtensibleFloat) {
                return FloatOps.EqualsRetBool(((ExtensibleFloat)x).value, y);
            } else if (x is byte) {
                return IntOps.EqualsRetBool((int)(byte)x, y);
            } else if (x is long) {
                return Int64Ops.EqualsRetBool((long)x, y);
            } else if (x is float) {
                return FloatOps.EqualsRetBool((float)x, y);
            } else if (x is Enum) {
                return EnumOps.EqualRetBool(x, y);
            } else if (x is sbyte) {
                return IntOps.EqualsRetBool((int)(sbyte)x, y);
            } else if (x is short) {
                return IntOps.EqualsRetBool((int)(short)x, y);
            } else if (x is ushort) {
                return IntOps.EqualsRetBool((int)(ushort)x, y);
            } else if (x is uint) {
                return LongOps.EqualsRetBool(BigInteger.Create((uint)x), y);
            } else if (x is ulong) {
                return LongOps.EqualsRetBool(BigInteger.Create((ulong)x), y);
            } else if (x is decimal) {
                return FloatOps.EqualsRetBool((double)(decimal)x, y);
            }

            return DynamicEqualRetBool(x, y);
        }

        public static bool DynamicEqualRetBool(object x, object y) {
            object ret = Ops.NotImplemented;

            IPythonEquality ipe = x as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(y);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            ipe = y as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(x);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            ret = GetDynamicType(x).Equal(x, y);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            ret = GetDynamicType(y).Equal(y, x);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            // we've tried all the possible comparisons... if x is null
            // then y doesn't know how to compare against it
            if (x == null) return false;
            return x.Equals(y);
        }

        public static object NotEqual(object x, object y) {
            if (x == y) return FALSE;

            object ret = Ops.NotImplemented;
            if (x is int) {
                ret = IntOps.Equals((int)x, y);
            } else if (x is string) {
                ret = StringOps.Equals((string)x, y);
            } else if (x is double) {
                ret = FloatOps.Equals((double)x, y);
            } else if (x is BigInteger) {
                ret = LongOps.Equals((BigInteger)x, y);
            } else if (x is Complex64) {
                ret = ComplexOps.Equals((Complex64)x, y);
            } else if (x == null) {
                if (y == null) return false;
                else if (y.GetType().IsPrimitive || y is BigInteger) return true;
            } else if (x is bool) {
                ret = BoolOps.Equals((bool)x, y);
            } else if (x is ExtensibleInt) {
                ret = IntOps.Equals(((ExtensibleInt)x).value, y);
            } else if (x is ExtensibleString) {
                ret = StringOps.Equals(((ExtensibleString)x).Value, y);
            } else if (x is ExtensibleFloat) {
                ret = FloatOps.Equals(((ExtensibleFloat)x).value, y);
            } else if (x is byte) {
                ret = IntOps.Equals((int)(byte)x, y);
            } else if (x is long) {
                ret = Int64Ops.Equals((long)x, y);
            } else if (x is float) {
                ret = FloatOps.Equals((float)x, y);
            } else if (x is Enum) {
                ret = EnumOps.Equal(x, y);
            } else if (x is sbyte) {
                ret = IntOps.Equals((int)(sbyte)x, y);
            } else if (x is short) {
                ret = IntOps.Equals((int)(short)x, y);
            } else if (x is ushort) {
                ret =  IntOps.Equals((int)(ushort)x, y);
            } else if (x is uint) {
                ret = LongOps.Equals(BigInteger.Create((uint)x), y);
            } else if (x is ulong) {
                ret = LongOps.Equals(BigInteger.Create((ulong)x), y);
            } else if (x is decimal) {
                ret = FloatOps.Equals((double)(decimal)x, y);
            }

            if (ret != Ops.NotImplemented) return Not(ret);

            IPythonEquality ipe = x as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(y);
            if (ret != Ops.NotImplemented) return Not(ret);

            ipe = y as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(x);
            if (ret != Ops.NotImplemented) return Not(ret);

            ret = GetDynamicType(x).NotEqual(x, y);
            if (ret != Ops.NotImplemented) return ret;

            ret = GetDynamicType(y).NotEqual(y, x);
            if (ret != Ops.NotImplemented) return ret;

            return Bool2Object(!x.Equals(y));
        }

        public static bool NotEqualRetBool(object x, object y) {
            if (x == y) return false;

            if (x is int) {
                return !IntOps.EqualsRetBool((int)x, y);
            } else if (x is string) {
                return !StringOps.EqualsRetBool((string)x, y);
            } else if (x is double) {
                return !FloatOps.EqualsRetBool((double)x, y);
            } else if (x is BigInteger) {
                return !LongOps.EqualsRetBool((BigInteger)x, y);
            } else if (x is Complex64) {
                return !ComplexOps.EqualsRetBool((Complex64)x, y);
            } else if (x == null) {
                if (y == null) return false;
                else if (y.GetType().IsPrimitive || y is BigInteger) return true;
            } else if (x is bool) {
                return !BoolOps.EqualsRetBool((bool)x, y);
            } else if (x is ExtensibleInt) {
                return !IntOps.EqualsRetBool(((ExtensibleInt)x).value, y);
            } else if (x is ExtensibleString) {
                return !StringOps.EqualsRetBool(((ExtensibleString)x).Value, y);
            } else if (x is ExtensibleFloat) {
                return !FloatOps.EqualsRetBool(((ExtensibleFloat)x).value, y);
            } else if (x is byte) {
                return !IntOps.EqualsRetBool((int)(byte)x, y);
            } else if (x is long) {
                return !Int64Ops.EqualsRetBool((long)x, y);
            } else if (x is float) {
                return !FloatOps.EqualsRetBool((float)x, y);
            } else if (x is Enum) {
                return !EnumOps.EqualRetBool(x, y);
            } else if (x is sbyte) {
                return !IntOps.EqualsRetBool((int)(sbyte)x, y);
            } else if (x is short) {
                return !IntOps.EqualsRetBool((int)(short)x, y);
            } else if (x is ushort) {
                return !IntOps.EqualsRetBool((int)(ushort)x, y);
            } else if (x is uint) {
                return !LongOps.EqualsRetBool(BigInteger.Create((uint)x), y);
            } else if (x is ulong) {
                return !LongOps.EqualsRetBool(BigInteger.Create((ulong)x), y);
            } else if (x is decimal) {
                return !FloatOps.EqualsRetBool((double)(decimal)x, y);
            }

            return DynamicNotEqualRetBool(x, y);
        }

        public static bool DynamicNotEqualRetBool(object x, object y) {
            object ret = Ops.NotImplemented;

            IPythonEquality ipe = x as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(y);
            if (ret != Ops.NotImplemented) return !Ops.IsTrue(ret);

            ipe = y as IPythonEquality;
            if (ipe != null) ret = ipe.PythonEquals(x);
            if (ret != Ops.NotImplemented) return !Ops.IsTrue(ret);

            ret = GetDynamicType(x).NotEqual(x, y);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            ret = GetDynamicType(y).NotEqual(y, x);
            if (ret != Ops.NotImplemented) return Ops.IsTrue(ret);

            // we've tried all the possible comparisons... if x is null
            // then y doesn't know how to compare against it
            if (x == null) return true;
            return !x.Equals(y);
        }

        public static int Compare(object x, object y) {
            if (x == y) return 0;
            //!!! This is going to be fun

            // built-in types need to be special cased here (like for equals)
            // because they don't implement our interfaces.

            // it'd be nice to check for null ahead of time, but we can't...
            // the user could have defined __cmp__ on a class and have it
            // compare specially against null it's self.

            object ret = Ops.NotImplemented;
            if (x is int) {
                ret = IntOps.Compare((int)x, y);
            } else if (x is double) {
                ret = FloatOps.Compare((double)x, y);
            } else if (x is BigInteger) {
                ret = LongOps.Compare((BigInteger)x, y);
            } else if (x is string && y is string) {
                int temp = string.CompareOrdinal((string)x, (string)y);
                return (temp == 0) ? 0 : (temp > 0 ? 1 : -1);
            } else if (x is Complex64 || y is Complex64) {
                return ComplexOps.TrueCompare(x, y);
            } else if (x is bool) {
                ret = BoolOps.Compare((bool)x, y);
            } else if(x is long) {
                ret = Int64Ops.Compare((long)x, y);
            } else if(x is ulong) {
                ret = Int64Ops.Compare((ulong)x, y);
            } else if(x is short) {
                ret = IntOps.Compare((int)(short)x, y);
            } else if(x is ushort) {
                ret = IntOps.Compare((int)(ushort)x, y);
            } else if(x is byte) {
                ret = IntOps.Compare((int)(byte)x, y);
            } else if (x is sbyte) {
                ret = IntOps.Compare((int)(sbyte)x, y);
            } else if(x is decimal) {
                ret = FloatOps.Compare((double)(decimal)x, y);
            } else if(x is uint) {
                ret = Int64Ops.Compare((long)(uint)x, y);
            } else if (x == null) {
                if (y.GetType().IsPrimitive || y is BigInteger) {
                    // built-in type that doesn't implement our comparable
                    // interfaces, being compared against null, go ahead
                    // and skip the rest of the checks.
                    return -1;
                }
            }

            if (ret != Ops.NotImplemented) return (int)ret;

            IPythonComparable pc1 = x as IPythonComparable;
            if (pc1 != null) {
                if ((ret = pc1.LessThan(y)) != Ops.NotImplemented) { if (Ops.IsTrue(ret)) return -1; }
                if ((ret = pc1.GreaterThan(y)) != Ops.NotImplemented) { if (Ops.IsTrue(ret)) return 1; }
            }

            IPythonComparable pc2 = y as IPythonComparable;
            if (pc2 != null) {
                if ((ret = pc2.LessThan(x)) != Ops.NotImplemented) { if (Ops.IsTrue(ret)) return 1; }
                if ((ret = pc2.GreaterThan(x)) != Ops.NotImplemented) { if (Ops.IsTrue(ret)) return -1; }
            }

            if (pc1 != null)
                if ((ret = pc1.CompareTo(y)) != Ops.NotImplemented) return Ops.CompareToZero(ret);
            if (pc2 != null)
                if ((ret = pc2.CompareTo(x)) != Ops.NotImplemented) return -1 * Ops.CompareToZero(ret);

            Type xType = (x == null) ? null : x.GetType(), yType = (y == null) ? null : y.GetType();

            IComparable c = x as IComparable;
            if (c != null) {
                if (xType != null && xType != yType) {
                    object z;
                    try {
                        Conversion conversion;
                        z = Converter.TryConvert(y, xType, out conversion);
                        if (conversion < Conversion.NonStandard) {
                            int res = c.CompareTo(z);
                            return res < 0 ? -1 : res > 0 ? 1 : 0;
                        }
                    } catch {
                    }
                } else {
                    int res = c.CompareTo(y);
                    return res < 0 ? -1 : res > 0 ? 1 : 0;
                }
            }
            c = y as IComparable;
            if (c != null) {
                if (yType != null && xType != yType) {
                    try {
                        Conversion conversion;
                        object z = Converter.TryConvert(x, yType, out conversion);
                        if (conversion < Conversion.NonStandard) {
                            int res = c.CompareTo(z);
                            return res < 0 ? 1 : res > 0 ? -1 : 0;
                        }
                    } catch {
                    }
                } else {
                    int res = c.CompareTo(x);
                    return res < 0 ? -1 : res > 0 ? 1 : 0;
                }
            }

            DynamicType dt1 = GetDynamicType(x);
            DynamicType dt2 = GetDynamicType(y);
            if ((ret = dt1.GreaterThan(x, y)) != Ops.NotImplemented) { if (IsTrue(ret)) return 1; }
            if ((ret = dt1.LessThan(x, y)) != Ops.NotImplemented) { if (IsTrue(ret)) return -1; }
            if ((ret = dt1.Equal(x, y)) != Ops.NotImplemented) { if (IsTrue(ret)) return 0; }

            if ((ret = dt2.GreaterThan(y, x)) != Ops.NotImplemented) { if (IsTrue(ret)) return -1; }
            if ((ret = dt2.LessThan(y, x)) != Ops.NotImplemented) { if (IsTrue(ret)) return 1; }
            if ((ret = dt2.Equal(y, x)) != Ops.NotImplemented) { if (IsTrue(ret)) return 0; }

            if ((ret = dt1.CompareTo(x, y)) != Ops.NotImplemented) return Ops.CompareToZero(ret);
            if ((ret = dt2.CompareTo(y, x)) != Ops.NotImplemented) return -1 * Ops.CompareToZero(ret);

            if (xType == yType) {
                return (int)(IdDispenser.GetId(x) - IdDispenser.GetId(y));
            } else {
                string xName = (xType == null) ? "NoneType" : xType.Name, yName = (yType == null) ? "NoneType" : yType.Name;

                return string.CompareOrdinal(xName, yName);
            }
        }

        public static int CompareToZero(object value) {
            Conversion conversion;
            double val = Converter.TryConvertToDouble(value, out conversion);
            if (conversion == Conversion.None) {
                throw Ops.TypeError("unable to compare type {0} with 0 ", Ops.GetDynamicType(value).__name__);
            }
            if (val > 0) return 1;
            if (val < 0) return -1;
            return 0;
        }

        public static int CompareArrays(object[] data0, int size0, object[] data1, int size1) {
            int size = Math.Min(size0, size1);
            for (int i = 0; i < size; i++) {
                int c = Ops.Compare(data0[i], data1[i]);
                if (c != 0) return c;
            }
            if (size0 == size1) return 0;
            return size0 > size1 ? +1 : -1;
        }

        public static object PowerMod(object x, object y, object z) {
            object ret;
            if (x is int) {
                ret = IntOps.PowerMod((int)x, y, z);
                if (ret != NotImplemented) return ret;
            } else if (x is long) {
                ret = Int64Ops.PowerMod((long)x, y, z);
                if (ret != NotImplemented) return ret;
            } else if (x is IronMath.BigInteger) {
                ret = LongOps.PowerMod((IronMath.BigInteger)x, y, z);
                if (ret != NotImplemented) return ret;
            }

            //            ret = GetDynamicType(x).Power(x, y);
            //            if (ret != NotImplemented) return ret;
            //            ret = GetDynamicType(y).ReversePower(y, x);
            //            if (ret != NotImplemented) return ret;
            throw Ops.TypeError("unsupported operand type(s) for power with modulus: '{0}' and '{1}'",
                GetDynamicType(x).__name__, GetDynamicType(y).__name__);
        }

        public static ICollection GetCollection(object o) {
            ICollection ret = o as ICollection;
            if (ret != null) return ret;

            ArrayList al = new ArrayList();
            IEnumerator e = GetEnumerator(o);
            while (e.MoveNext()) al.Add(e.Current);
            return al;
        }

        public static bool TryGetEnumerator(object o, out IEnumerator ie) {
            if (o is string) {
                ie = StringOps.GetEnumerator((string)o);
                return true;
            } else if (o is IEnumerable) {
                ie = ((IEnumerable)o).GetEnumerator();
                return true;
            } else if (o is IEnumerator) {
                ie = (IEnumerator)o;
                return true;
            }

            IEnumerator enumerator;
            if (PythonEnumerator.Create(o, out enumerator)) {
                ie = enumerator;
                return true;
            }
            if (ItemEnumerator.Create(o, out enumerator)) {
                ie = enumerator;
                return true;
            }
            ie = null;
            return false;
        }

        public static IEnumerator GetEnumerator(object o) {
            IEnumerator ie;
            if (!TryGetEnumerator(o, out ie)) {
                throw Ops.TypeError("{0} is not enumerable", StringRepr(o));
            }
            return ie;
        }

        // Returns the number of elements in the collection.
        // The enumerator should have just been created or Reset when this method is called.
        // It will Reset the enumerator on return
        public static int GetEnumeratorCount(IEnumerator ie) {
            int count = 0;
            while (ie.MoveNext()) {
                count++;
            }
            ie.Reset();
            return count;
        }

        public static long Id(object o) {
            return IdDispenser.GetId(o);
        }

        public static string HexId(object o) {
            return string.Format("0x{0:X16}", Id(o));
        }

        public static int Hash(object o) {
            if (o is int) return (int)o;
            if (o is string) return o.GetHashCode();    // avoid lookups on strings - A) We can stack overflow w/ Dict B) they don't define __hash__
            if (o is double) return (int)(double)o; //??? fuzzy
            if (o == null) return NoneType.NoneHashCode;

            IPythonEquality ipe = o as IPythonEquality;
            if (ipe != null) {
                object res = ipe.PythonGetHashCode();
                if (res != Ops.NotImplemented) return (int)res;
            }

            return o.GetHashCode();
        }

        public static object Hex(object o) {
            if (o is int) return IntOps.Hex((int)o);
            else if (o is long) return Int64Ops.Hex((long)o);
            else if (o is BigInteger) return LongOps.Hex((BigInteger)o);

            object hex;
            if (TryGetAttr(o, SymbolTable.ConvertToHex, out hex)) {
                return Call(hex);
            }
            throw TypeError("hex() argument cannot be converted to hex");
        }

        public static object Oct(object o) {
            if (o is int) {
                return IntOps.Oct((int)o);
            } else if (o is long) {
                return Int64Ops.Oct((long)o);
            } else if (o is BigInteger) {
                return LongOps.Oct((BigInteger)o);
            }

            object hex;
            if (TryGetAttr(o, SymbolTable.ConvertToOctal, out hex)) {
                return Call(hex);
            }
            throw TypeError("hex() argument cannot be converted to hex");
        }

        public static object CallWithContext(ICallerContext context, object func, params object[] args) {
            ICallableWithCallerContext icc = func as ICallableWithCallerContext;
            if (icc != null) return icc.Call(context, args);

            ICallable ic = func as ICallable;
            if (ic != null) return ic.Call(args);

            return GetDynamicType(func).Call(func, args);
        }

        public static object CallWithContext(ICallerContext context, object func, object[] args, string[] names) {
            IFancyCallable ic = func as IFancyCallable;
            if (ic != null) return ic.Call(args, names);

            object callMeth;
            if (Ops.TryGetAttr(func, SymbolTable.Call, out callMeth)) {
                ic = callMeth as IFancyCallable;

                if (ic != null) return ic.Call(args, names);
            }

            throw new Exception("this object is not callable with keyword parameters");
        }

        public static object CallWithArgsTupleAndContext(ICallerContext context, object func, object[] args, object argsTuple) {
            Tuple tp = argsTuple as Tuple;
            if (tp != null) {
                object[] nargs = new object[args.Length + tp.Count];
                for (int i = 0; i < args.Length; i++) nargs[i] = args[i];
                for (int i = 0; i < tp.Count; i++) nargs[i + args.Length] = tp[i];
                return CallWithContext(context, func, nargs);
            }

            List allArgs = List.MakeEmptyList(args.Length + 10);
            IEnumerator e = Ops.GetEnumerator(argsTuple);
            while (e.MoveNext()) allArgs.AddNoLock(e.Current);

            return CallWithContext(context, func, allArgs.GetObjectArray());
        }

        public static object CallWithArgsTupleAndKeywordDictAndContext(ICallerContext context, object func, object[] args, string[] names, object argsTuple, object kwDict) {
            IDictionary kws = kwDict as IDictionary;
            if (kws == null && kwDict != null) throw Ops.TypeError("argument after ** must be a dictionary");

            if ((kws == null || kws.Count == 0) && names.Length == 0) {
                ArrayList largs = new ArrayList(args);
                if (argsTuple != null) {
                    largs.AddRange(Ops.GetCollection(argsTuple));
                }
                return CallWithContext(context, func, (object[])largs.ToArray(typeof(object)));
            } else {
                IFancyCallable ic = func as IFancyCallable;
                if (ic == null) throw new Exception("this object is not callable with keyword parameters");

                List<object> largs;

                if (argsTuple != null && args.Length == names.Length) {
                    largs = new List<object>((Tuple)argsTuple);
                    largs.AddRange(args);
                } else {
                    largs = new List<object>(args);
                    if (argsTuple != null) {
                        largs.InsertRange(args.Length - names.Length, (Tuple)argsTuple);
                    }
                }

                List<string> lnames = new List<string>(names);

                if (kws != null) {
                    IDictionaryEnumerator ide = kws.GetEnumerator();
                    while (ide.MoveNext()) {
                        lnames.Add((string)ide.Key);
                        largs.Add(ide.Value);
                    }
                }

                return ic.Call(largs.ToArray(), lnames.ToArray());
            }
        }

        public static bool TryCall(object func, out object ret) {
            return TryCall(func, new object[0], out ret);
        }

        public static bool TryCall(object func, object arg0, out object ret) {
            return TryCall(func, new object[] { arg0 }, out ret);
        }

        public static bool TryCall(object func, object arg0, object arg1, out object ret) {
            return TryCall(func, new object[] { arg0, arg1 }, out ret);
        }

        public static bool TryCall(object func, object[] args, out object ret) {
            ITryCallable itc = func as ITryCallable;
            if (itc != null) return itc.TryCall(args, out ret);

            ret = Call(func, args);
            return true;
        }

        public static object Call(object func, params object[] args) {
            ICallable ic = func as ICallable;
            if (ic != null) return ic.Call(args);

            return GetDynamicType(func).Call(func, args);
        }

        public static object Call(object func, object[] args, string[] names) {
            IFancyCallable ic = func as IFancyCallable;
            if (ic != null) return ic.Call(args, names);

            object callMeth;
            if (Ops.TryGetAttr(func, SymbolTable.Call, out callMeth)) {
                ic = callMeth as IFancyCallable;

                if (ic != null) return ic.Call(args, names);
            }

            throw new Exception("this object is not callable with keyword parameters");
        }

        public static object CallWithArgsTuple(object func, object[] args, object argsTuple) {
            Tuple tp = argsTuple as Tuple;
            if (tp != null) {
                object[] nargs = new object[args.Length + tp.Count];
                for (int i = 0; i < args.Length; i++) nargs[i] = args[i];
                for (int i = 0; i < tp.Count; i++) nargs[i + args.Length] = tp[i];
                return Call(func, nargs);
            }

            List allArgs = List.MakeEmptyList(args.Length + 10);
            IEnumerator e = Ops.GetEnumerator(argsTuple);
            while (e.MoveNext()) allArgs.AddNoLock(e.Current);

            return Call(func, allArgs.GetObjectArray());
        }

        public static object CallWithArgsTupleAndKeywordDict(object func, object[] args, string[] names, object argsTuple, object kwDict) {
            IDictionary<object, object> kws = kwDict as IDictionary<object, object>;
            if (kws == null) throw Ops.TypeError("argument after ** must be a dictionary");

            if (kws.Count == 0 && names.Length == 0) {
                ArrayList largs = new ArrayList(args);
                if (argsTuple != null) {
                    largs.AddRange(Ops.GetCollection(argsTuple));
                }
                return Call(func, (object[])largs.ToArray(typeof(object)));
            } else {
                IFancyCallable ic = func as IFancyCallable;
                if (ic == null) throw new Exception("this object is not callable with keyword parameters");

                //!!! should use generics and look at fastpaths for common cases
                ArrayList largs = new ArrayList(args);
                ArrayList lnames = new ArrayList(names);

                if (argsTuple != null) {
                    largs.InsertRange(args.Length - names.Length, Ops.GetCollection(argsTuple));
                }


                foreach (KeyValuePair<object, object> entry in kws) {
                    lnames.Add(entry.Key);
                    largs.Add(entry.Value);
                }

                return ic.Call(largs.ToArray(), (string[])lnames.ToArray(typeof(string)));
            }
        }

        public static object GetIndex(object o, object index) {
            ISequence seq = o as ISequence;
            if (seq != null) {
                if (index is int) return seq[(int)index];
                else if (index is Slice) return seq[(Slice)index];
                //???
            }

            string s = o as string;
            if (s != null) {
                if (index is int) return StringOps.__getitem__(s, (int)index);
                else if (index is Slice) return StringOps.__getitem__(s, (Slice)index);
                //???
            }

            IMapping map = o as IMapping;
            if (map != null) {
                return map[index];
            }

            Array array = o as Array;
            if (array != null) {
                return ArrayOps.GetIndex(array, index);
            }

            IList list = o as IList;
            if (list != null) {
                Conversion conv;
                int val = Converter.TryConvertToInt32(index, out conv);
                if (conv != Conversion.None) {
                    return list[val];
                }
            }

            return GetDynamicType(o).GetIndex(o, index);
        }

        public static void SetIndex(object o, object index, object value) {
            IMutableSequence seq = o as IMutableSequence;
            if (seq != null) {
                if (index is int) {
                    seq[(int)index] = value;
                    return;
                } else if (index is Slice) {
                    seq[(Slice)index] = value;
                    return;
                }
                //???
            }

            IMapping map = o as IMapping;
            if (map != null) {
                map[index] = value;
                return;
            }

            Array array = o as Array;
            if (array != null) {
                ArrayOps.SetIndex(array, index, value);
                return;
            }

            IList list = o as IList;
            if (list != null) {
                list[Converter.ConvertToInt32(index)] = value;
                return;
            }

            GetDynamicType(o).SetIndex(o, index, value);
        }

        public static void SetIndexStackHelper(object value, object o, object index) {
            SetIndex(o, index, value);
        }

        public static void DelIndex(object o, object index) {
            if (index == null) {
                throw Ops.TypeError("index must be integer or slice");
            }

            IMutableSequence seq = o as IMutableSequence;
            if (seq != null) {
                if (index is int) {
                    seq.DeleteItem((int)index);
                    return;
                } else if (index is Slice) {
                    seq.DeleteItem((Slice)index);
                    return;
                }
                //???
            }

            IMapping map = o as IMapping;
            if (map != null) {
                map.DeleteItem(index);
                return;
            }

            GetDynamicType(o).DelIndex(o, index);
        }

        public static bool TryGetAttr(object o, SymbolId name, out object ret) {
            return TryGetAttr(DefaultContext.Default, o, name, out ret);
        }

        public static bool TryGetAttr(ICallerContext context, object o, SymbolId name, out object ret) {
            ICustomAttributes ids = o as ICustomAttributes;
            if (ids != null) {
                return ids.TryGetAttr(context, name, out ret);
            }

            return GetDynamicType(o).TryGetAttr(context, o, name, out ret);
        }

        public static object GetAttr(ICallerContext context, object o, SymbolId name) {
            ICustomAttributes ifca = o as ICustomAttributes;
            if (ifca != null) {
                object ret;
                if (ifca.TryGetAttr(context, name, out ret)) return ret;

                if (o.GetType().IsSubclassOf(typeof(UserType))) {
                    //!!! we have an instance of a class that is built w/
                    // a meta-class.  We need to check the metaclasses
                    // properties as well, which ICustomAttrs didn't do.
                    // we'll fall through to GetAttr (we should probably
                    // do special overrides in NewTypeMaker instead)
                } else if (o is DynamicType) {
                    throw Ops.AttributeError("type object '{0}' has no attribute '{1}'",
                        ((DynamicType)o).__name__, SymbolTable.IdToString(name));
                } else {
                    throw Ops.AttributeError("'{0}' object has no attribute '{1}'", GetDynamicType(o).__name__, SymbolTable.IdToString(name));
                }
            }

            // fall through to normal case...
            return GetDynamicType(o).GetAttr(context, o, name);
        }

        public static void SetAttr(ICallerContext context, object o, SymbolId name, object value) {
            ICustomAttributes ids = o as ICustomAttributes;

            if (ids != null) {
                ids.SetAttr(context, name, value);
                return;
            }

            GetDynamicType(o).SetAttr(context, o, name, value);
        }

        public static void SetAttrStackHelper(object value, object o, SymbolId name, ICallerContext context) {
            SetAttr(context, o, name, value);
        }

        public static void DelAttr(ICallerContext context, object o, SymbolId name) {
            ICustomAttributes ifca = o as ICustomAttributes;
            if (ifca != null) {
                ifca.DeleteAttr(context, name);
                return;
            }

            GetDynamicType(o).DelAttr(context, o, name);
        }

        public static List GetAttrNames(ICallerContext context, object o) {
            ICustomAttributes ids = o as ICustomAttributes;

            if (ids != null) {
                return ids.GetAttrNames(context);
            }

            return GetDynamicType(o).GetAttrNames(context, o);
        }

        public static IDictionary<object, object> GetAttrDict(ICallerContext context, object o) {
            ICustomAttributes ids = o as ICustomAttributes;
            if (ids != null) {
                return ids.GetAttrDict(context);
            }
            return GetDynamicType(o).GetAttrDict(context, o);
        }

        public static void CheckInitialized(object o) {
            if (o is Uninitialized) throw Ops.NameError("name '{0}' not defined", ((Uninitialized)o).name);
        }

        public static object GetDescriptor(object o, object instance, object context) {
            PythonFunction f = o as PythonFunction;
            if (f != null) return f.GetAttribute(instance, context);

            IDescriptor id = o as IDescriptor;
            if (id != null) return id.GetAttribute(instance, context);

            if (!(o is ISuperDynamicObject)) return o;   //???

            // slow, but only encountred for user defined descriptors.
            PerfTrack.NoteEvent(PerfTrack.Categories.DictInvoke, "__delete__");
            object ret;
            if (TryToInvoke(o, SymbolTable.GetDescriptor, out ret, instance, context)) return ret;

            return o;
        }

        public static bool SetDescriptor(object o, object instance, object value) {
            IDataDescriptor id = o as IDataDescriptor;
            if (id != null) {
                return id.SetAttribute(instance, value);
            }

            if (instance == null) return false;

            // slow, but only encountred for user defined descriptors.
            PerfTrack.NoteEvent(PerfTrack.Categories.DictInvoke, "__delete__");
            object ret;
            if (TryToInvoke(o, SymbolTable.SetDescriptor, out ret, instance, value)) return true;

            return false;
        }

        public static bool DelDescriptor(object o, object instance) {
            IDataDescriptor id = o as IDataDescriptor;
            if (id != null) {
                return id.DeleteAttribute(instance);
            }

            if (instance == null) return false;

            // slow, but only encountred for user defined descriptors.
            PerfTrack.NoteEvent(PerfTrack.Categories.DictInvoke, "__delete__");
            object ret;
            if (TryToInvoke(o, SymbolTable.DeleteDescriptor, out ret, instance)) return true;

            return false;
        }

        public static object[] ExtractArrayTail(object[] a0) {
            int N = a0.Length - 1;
            object[] ret = new object[N];
            Array.Copy(a0, 1, ret, 0, N);
            return ret;
        }

        public static object InvokeMethod(object meth, object type, object self) {
            PythonFunction f = meth as PythonFunction;
            if (f != null) return f.Call(self);
            return Ops.Call(Ops.GetDescriptor(meth, self, type));
        }
        public static object InvokeMethod(object meth, object type, object self, object arg0) {
            PythonFunction f = meth as PythonFunction;
            if (f != null) return f.Call(self, arg0);
            return Ops.Call(Ops.GetDescriptor(meth, self, type), arg0);
        }
        public static object InvokeMethod(object meth, object type, object self, object arg0, object arg1) {
            PythonFunction f = meth as PythonFunction;
            if (f != null) return f.Call(self, arg0, arg1);
            return Ops.Call(Ops.GetDescriptor(meth, self, type), arg0, arg1);
        }

        public static object InvokeMethod(object meth, object type, object[] selfAndArgs) {
            PythonFunction f = meth as PythonFunction;
            if (f != null) return f.Call(selfAndArgs);
            object self = selfAndArgs[0];
            object[] args = new object[selfAndArgs.Length - 1];
            Array.Copy(selfAndArgs, 1, args, 0, args.Length);
            return Ops.Call(Ops.GetDescriptor(meth, self, type), args);
        }

        public static Exception MissingInvokeMethodException(object self, string name) {
            return Ops.MakeAttributeError(self, name);
        }

        //!!! try to use consistently
        static Exception MakeAttributeError(object o, string name) {
            if (o is DynamicType) {
                throw Ops.AttributeError("type object '{0}' has no attribute '{1}'",
                    ((DynamicType)o).__name__, name);
            } else {
                throw Ops.AttributeError("'{0}' object has no attribute '{1}'", GetDynamicType(o).__name__, name);
            }
        }

        public static object Invoke(object target, SymbolId name, params object[] args) {
            object meth = GetAttr(DefaultContext.Default, target, name);
            return Call(meth, args);
        }

        public static bool TryToInvoke(object target, SymbolId name, out object ret, params object[] args) {
            object meth;
            if (TryGetAttr(target, name, out meth)) {
                ret = Call(meth, args);
                return true;
            } else {
                ret = null;
                return false;
            }
        }

        private static void Write(object f, string text) {
            if (f == null) f = State.stdout;
            if (f == null || f is Uninitialized) throw Ops.RuntimeError("lost sys.std_out");
            Ops.Invoke(f, SymbolTable.ConsoleWrite, text);
        }

        private static object ReadLine(object f) {
            if (f == null || f is Uninitialized) throw Ops.RuntimeError("lost sys.std_in");
            return Ops.Invoke(f, SymbolTable.ConsoleReadLine);
        }

        private static void WriteSoftspace(object f) {
            if (CheckSoftspace(f)) {
                SetSoftspace(f, FALSE);
                Write(f, " ");
            }
        }

        private static void SetSoftspace(object f, object value) {
            Ops.SetAttr(DefaultContext.Default, f, SymbolTable.Softspace, value);
        }

        private static bool CheckSoftspace(object f) {
            object result;
            if (Ops.TryGetAttr(f, SymbolTable.Softspace, out result)) return Ops.IsTrue(result);
            return false;
        }


        public static void PrintNewline() {
            PrintNewlineWithDest(State.stdout);
        }

        public static void PrintNewlineWithDest(object dest) {
            Write(dest, "\n");
            SetSoftspace(dest, FALSE);
        }

        public static void Print(object o) {
            PrintWithDest(State.stdout, o);
        }

        public static void PrintNoNewline(object o) {
            PrintWithDestNoNewline(State.stdout, o);
        }

        public static void PrintComma(object o) {
            PrintCommaWithDest(State.stdout, o);
        }

        public static void PrintWithDest(object dest, object o) {
            PrintWithDestNoNewline(dest, o);
            Write(dest, "\n");
        }

        public static void PrintWithDestNoNewline(object dest, object o) {
            WriteSoftspace(dest);
            Write(dest, o == null ? "None" : ToString(o));
        }

        public static void PrintCommaWithDest(object dest, object o) {
            WriteSoftspace(dest);
            string s = o == null ? "None" : ToString(o);

            Write(dest, s);
            SetSoftspace(dest, !s.EndsWith("\n"));
        }

        public static void PrintNotNoneRepr(object o) {
            if (o != null) Print(Ops.StringRepr(o));
        }

        public static void PrintRepr(object o) {
            if (o != null) PrintNoNewline(Ops.StringRepr(o));
        }

        public static object ReadLineFromSrc(object src) {
            return ReadLine(src);
        }

        // import spam.eggs
        public static object Import(PythonModule mod, string fullName) {
            return Importer.Import(mod, fullName, List.Make());
        }

        // import spam as ham
        public static object ImportAs(PythonModule mod, string fullName, string asName) {
            return Importer.Import(mod, fullName, List.MakeList(asName));
        }

        // from spam import eggs1, eggs2
        public static object ImportFrom(PythonModule mod, string fullName, string[] names) {
            return ImportFromAs(mod, fullName, names, names);
        }

        // from spam import eggs1 as ham1, eggs2 as ham2
        public static object ImportFromAs(PythonModule mod, string fullName, string[] names, string[] asNames) {
            return Importer.Import(mod, fullName, List.Make(asNames));
        }

        public static object ImportOneFrom(ICallerContext context, object fromObj, string name) {
            return Importer.ImportFrom(context, fromObj, name);
        }

        // from spam import *
        public static void ImportStar(PythonModule mod, string fullName) {
            object newmod = Importer.Import(mod, fullName, List.MakeList("*"));

            if (newmod is PythonModule) {
                object all;
                if (((PythonModule)newmod).TryGetAttr(DefaultContext.Default, SymbolTable.All, out all)) {
                    IEnumerator exports = GetEnumerator(all);

                    while (exports.MoveNext()) {
                        string name = exports.Current as string;
                        if (name == null) continue;

                        SymbolId fieldId = SymbolTable.StringToId(name);
                        mod.SetAttr(mod, fieldId, GetAttr(DefaultContext.Default, newmod, fieldId));
                    }
                    return;
                }
            }

            foreach (string name in Ops.GetAttrNames(DefaultContext.Default, newmod)) {
                if (name != null) {
                    if (name.Length == 0) continue;
                    if (name[0] == '_') continue;

                    SymbolId fieldId = SymbolTable.StringToId(name);
                    mod.SetAttr(mod, fieldId, GetAttr(DefaultContext.Default, newmod, fieldId));
                }
            }
        }

        public static Delegate CreateDynamicDelegate(DynamicMethod meth, Type delegateType, object target) {
            // Always close delegate around its own instance of the frame
            return meth.CreateDelegate(delegateType, target);
        }

        private static object FindMetaclass(ICallerContext context, Tuple bases, IDictionary<object, object> dict) {
            // If dict['__metaclass__'] exists, it is used. 
            object ret;
            if (dict.TryGetValue("__metaclass__", out ret) && ret != null) return ret;

            //Otherwise, if there is at least one base class, its metaclass is used
            if (bases.Count > 0) {
                for (int i = 0; i < bases.Count; i++) {
                    if (!(bases[i] is OldClass)) return Ops.GetDynamicType(bases[i]);
                }
            }

            //Otherwise, if there's a global variable named __metaclass__, it is used.
            if (context.Module.TryGetAttr(context, SymbolTable.MetaClass, out ret) && ret != null) {
                return ret;
            }

            //Otherwise, the classic metaclass (types.ClassType) is used.
            return OldInstanceType.Instance;
        }

        public static object MakeClass(ICallerContext mod, string modName, string name, Tuple bases, IDictionary<object, object> vars) {
            // __module__ is available when we call __metaclass__, so
            // we ensure it's in the dictionary here and flow it through
            // to our internal classes via the dictionary.
            if (!vars.ContainsKey("__module__")) {
                if (modName == null) {
                    vars["__module__"] = "__builtin__";
                } else {
                    vars["__module__"] = modName;
                }
            }

            object metaclass = FindMetaclass(mod, bases, vars);
            if (metaclass == OldInstanceType.Instance)
                return new OldClass(name, bases, vars);
            if (metaclass == TypeCache.ReflectedType || metaclass == TypeCache.UserType)
                return UserType.MakeClass(name, bases, vars); //!!!
            if (metaclass is UserType)
                return ((ICallableWithCallerContext)metaclass).Call(mod, new object[] { name, bases, vars });

            // eg:
            // def foo(*args): print args
            // __metaclass__ = foo
            // class bar: pass
            // calls our function...
            return Ops.CallWithContext(mod, metaclass, name, bases, vars);
        }


        public static void Exec(ICallerContext context, object code) {
            IDictionary<object, object> locals = (IDictionary<object, object>)context.Locals;
            IDictionary<object, object> globals = (IDictionary<object, object>)context.Globals;

            // if the user passes us a tuple we'll extract the 3 values out of it            
            Tuple codeTuple = code as Tuple;
            if (codeTuple != null && codeTuple.Count > 0 && codeTuple.Count <= 3) {
                code = codeTuple[0];

                if (codeTuple.Count > 1 && codeTuple[1] != null) {
                    globals = codeTuple[1] as IDictionary<object, object>;
                    if (globals == null) throw Ops.TypeError("globals must be dictionary or none");
                }

                if (codeTuple.Count > 2 && codeTuple[2] != null) {
                    locals = codeTuple[2] as IDictionary<object, object>;
                    if (locals == null) throw Ops.TypeError("locals must be dictionary or none");
                } else if (globals != context.Globals)
                    locals = globals;
            }

            Exec(context, code, locals, globals);
        }

        public static void Exec(ICallerContext context, object code, IDictionary<object, object> locals) {
            Exec(context, code, locals, (IDictionary<object, object>)(context.Module.__dict__));
        }

        public static void Exec(ICallerContext context, object code, IDictionary<object, object> locals, IDictionary<object, object> globals) {
            if (code is PythonFile) {
                PythonFile pf = code as PythonFile;
                List lines = pf.ReadLines();
                StringBuilder fullCode = new StringBuilder();
                for (int i = 0; i < lines.Count; i++) {
                    fullCode.Append(lines[i]);
                }

                code = fullCode.ToString();
            } else if (code is Stream) {
                Stream cs = code as Stream;
                code = new StreamReader(cs).ReadToEnd();
            }

            if (code is String) {
                CompilerContext cc = context.CreateCompilerContext();
                Parser p = Parser.FromString(cc, (string)code);
                //  could be multiple statements e.g. exec "\nprint "abc"\nprint "def"\n"
                Stmt s = p.ParseFileInput();
                code = new FunctionCode(OutputGenerator.GenerateSnippet(cc, s, "<exec>", false));
            }

            FunctionCode fc = code as FunctionCode;
            if (fc == null) {
                throw Ops.TypeError("arg 1 must be a string, file, Stream, or code object");
            }

            fc.Call(new Frame(context.Module, globals, locals));
        }

        public static void Raise() {
            if (SystemState.RawException != null) {
                PerfTrack.NoteEvent(PerfTrack.Categories.Exceptions, SystemState.RawException);
                throw SystemState.RawException;
            } else {
                throw Ops.TypeError("throwing a non-exception type, NoneType");
            }
        }

        public static void Raise(object type, object value, object traceback) {
            // non-reraise.
            // type is the type of exception to throwo or an instance.  If it 
            // is an instance then value should be null.  

            // If type is a type then value can either be an instance of type,
            // a Tuple, or a single value.  This case is handled by EC.CreateThrowable.

            // Currently we ignore the traceback.
            Exception throwable;

            if (traceback != null) {
                TraceBack tb = traceback as TraceBack;
                if (tb == null) throw Ops.TypeError("traceback argument must be a traceback object");
                tb.IsUserSupplied = true;

                SystemState.RawTraceBack = tb;
            }

            if (type is Exception) throwable = type as Exception;
            else if (Builtin.IsInstance(type, Builtin.Exception)) throwable = ExceptionConverter.ToClr(type);
            else if (type is string) throwable = new StringException(type.ToString(), value);
            else if (type is OldClass) {
                if (value == null)
                    throwable = ExceptionConverter.CreateThrowable(type);
                else
                    throwable = ExceptionConverter.CreateThrowable(type, value);
            } else if (type is OldInstance) throwable = ExceptionConverter.ToClr(type);
            else throwable = Ops.TypeError("exceptions must be classes, instances, or strings (deprecated), not {0}", Ops.GetDynamicType(type));

            PerfTrack.NoteEvent(PerfTrack.Categories.Exceptions, throwable);

            throw throwable;
        }

        public static object ExtractException(Exception e) {
            Ops.State.SetRawException(e);
            object res = ExceptionConverter.ToPython(e);
            System.Diagnostics.Debug.Assert(res != null);
            return res;
        }

        public static void ClearException() {
            Ops.State.ClearException();
        }

        public static void UpdateTraceBack(ICallerContext context, string funcName, string filename, int line) {
            TraceBack curTrace = SystemState.RawTraceBack;
            if (curTrace == null || !curTrace.IsUserSupplied) {
                PythonFunction fx = new Function0(context.Module, funcName, null, new string[0], new object[0]);

                TraceBackFrame tbf = new TraceBackFrame(context.Globals, context.Locals, fx.FunctionCode);
                ((FunctionCode)fx.FunctionCode).SetFilename(filename);
                ((FunctionCode)fx.FunctionCode).SetLineNumber(line);
                TraceBack tb = new TraceBack(curTrace, tbf);
                tb.SetLine(line);

                SystemState.RawTraceBack = tb;
            }
        }

        public static object CheckException(object exc, object test) {
            System.Diagnostics.Debug.Assert(exc != null);

            StringException strex;
            if (test is Tuple) {
                // we handle multiple exceptions, we'll check them one at a time.
                Tuple tt = test as Tuple;
                for (int i = 0; i < tt.Count; i++) {
                    object res = CheckException(exc, tt[i]);
                    if (res != null) return res;
                }
            } else if ((strex = exc as StringException) != null) {
                // catching a string
                if (test.GetType() != typeof(string)) return null;
                if (strex.Message == (string)test) {
                    if (strex.Value == null) return strex.Message;
                    return strex.Value;
                }
                return null;
            } else if (test is DynamicType) {
                if (Builtin.IsInstance(exc, test)) {
                    // catching a Python type.
                    return exc;
                } else if (Builtin.IsSubClass(test as DynamicType, Ops.GetDynamicTypeFromType(typeof(Exception)))) {
                    // catching a CLR exception type explicitly.
                    Exception clrEx = ExceptionConverter.ToClr(exc);
                    if (Builtin.IsInstance(clrEx, test)) return clrEx;
                }
            }

            return null;
        }

        public static int FixSliceIndex(int v, int len) {
            if (v < 0) v = len + v;
            if (v < 0) return 0;
            if (v > len) return len;
            return v;
        }

        public static void FixSlice(int length, object start, object stop, object step,
                                    out int ostart, out int ostop, out int ostep, out int ocount) {
            if (step == null) {
                ostep = 1;
            } else {
                ostep = Converter.ConvertToSliceIndex(step);
                if (ostep == 0) {
                    throw Ops.ValueError("step cannot be zero");
                }
            }

            if (start == null) {
                ostart = ostep > 0 ? 0 : length - 1;
            } else {
                ostart = Converter.ConvertToSliceIndex(start);
                if (ostart < 0) {
                    ostart += length;
                    if (ostart < 0) {
                        ostart = ostep > 0 ? Math.Min(length, 0) : Math.Min(length - 1, -1);
                    }
                } else if (ostart >= length) {
                    ostart = ostep > 0 ? length : length - 1;
                }
            }

            if (stop == null) {
                ostop = ostep > 0 ? length : -1;
            } else {
                ostop = Converter.ConvertToSliceIndex(stop);
                if (ostop < 0) {
                    ostop += length;
                    if (ostop < 0) {
                        ostop = Math.Min(length, -1);
                    }
                } else if (ostop > length) {
                    ostop = length;
                }
            }

            ocount = ostep > 0 ? (ostop - ostart + ostep - 1) / ostep
                               : (ostop - ostart + ostep + 1) / ostep;
        }

        public static int FixIndex(int v, int len) {
            if (v < 0) {
                v += len;
                if (v < 0) {
                    throw Ops.IndexError("index out of range: {0}", v - len);
                }
            } else if (v >= len) {
                throw Ops.IndexError("index out of range: {0}", v);
            }
            return v;
        }

        public static SystemState State {
            get {
                if (systemState == null) {
                    systemState = new SystemState();
                }
                return systemState;
            }
        }

        public static void LoadAssembly(Assembly asm) {
            ReflectedPackage.LoadAssembly(asm);
        }

        #region CLS Compatible exception factories

        public static Exception ValueError(string format, params object[] args) {
            return new ArgumentException(string.Format(format, args));
        }

        public static Exception KeyError(string format, params object[] args) {
            return new KeyNotFoundException(string.Format(format, args));
        }

        public static Exception StopIteration(string format, params object[] args) {
            return new StopIterationException(string.Format(format, args));
        }

        public static Exception UnicodeEncodeError(string format, params object[] args) {
            return new System.Text.DecoderFallbackException(string.Format(format, args));
        }

        public static Exception UnicodeDecodeError(string format, params object[] args) {
            return new System.Text.EncoderFallbackException(string.Format(format, args));
        }

        public static Exception IOError(string format, params object[] args) {
            return new System.IO.IOException(string.Format(format, args));
        }

        public static Exception EofError(string format, params object[] args) {
            return new System.IO.EndOfStreamException(string.Format(format, args));
        }

        public static Exception StandardError(string format, params object[] args) {
            return new SystemException(string.Format(format, args));
        }

        public static Exception ZeroDivisionError(string format, params object[] args) {
            return new DivideByZeroException(string.Format(format, args));
        }

        public static Exception SystemError(string format, params object[] args) {
            return new SystemException(string.Format(format, args));
        }

        public static Exception TypeError(string format, params object[] args) {
            return new ArgumentTypeException(string.Format(format, args));
        }

        public static Exception IndexError(string format, params object[] args) {
            return new System.IndexOutOfRangeException(string.Format(format, args));
        }

        public static Exception MemoryError(string format, params object[] args) {
            return new OutOfMemoryException(string.Format(format, args));
        }

        public static Exception ArithmeticError(string format, params object[] args) {
            return new ArithmeticException(string.Format(format, args));
        }

        public static Exception NotImplementedError(string format, params object[] args) {
            return new NotImplementedException(string.Format(format, args));
        }

        public static Exception AttributeError(string format, params object[] args) {
            return new MissingMemberException(string.Format(format, args));
        }

        public static Exception OverflowError(string format, params object[] args) {
            return new System.OverflowException(string.Format(format, args));
        }

        public static Exception WindowsError(string format, params object[] args) {
            return new System.ComponentModel.Win32Exception(string.Format(format, args));
        }

        public static Exception SystemExit(string format, params object[] args) {
            return new PythonSystemExit(string.Format(format, args));
        }

        public static Exception SyntaxError(string format, params object[] args) {
            return new PythonSyntaxError(string.Format(format, args));
        }

        public static Exception SyntaxError(string msg, string filename, int line, int column, string lineText, Hosting.Severity severity) {
            return new PythonSyntaxError(msg, filename, line, column, lineText, severity);
        }

        #endregion


        public static Exception StopIteration() {
            return StopIteration("");
        }

        public static Exception AssertionError(string message) {
            return AssertionError(message != null ? message : String.Empty, new object[0]);
        }

        public static Exception InvalidType(object o, RuntimeTypeHandle handle) {
            System.Diagnostics.Debug.Assert(Options.GenerateSafeCasts);
            Type type = Type.GetTypeFromHandle(handle);
            return TypeError("Object {0} is not of type {1}", o == null ? "None" : o, type);
        }

        public static Exception ZeroDivisionError() {
            return ZeroDivisionError("Attempted to divide by zero.");
        }

        // If you do "(a, b) = (1, 2, 3, 4)"
        public static Exception ValueErrorForUnpackMismatch(int elementCount) {
            return ValueError("incorrect number of values ({0}) to unpack.", elementCount);
        }

        public static Exception TypeErrorForBuiltinAttributeChange(string typeName) {
            throw Ops.TypeError("can't set attributes of built-in/extension type '{0}'", typeName);
        }

        // If an unbound method is called without a "self" argument, or a "self" argument of a bad type
        public static Exception TypeErrorForUnboundMethodCall(string methodName, Type methodType, object instance) {
            return TypeErrorForUnboundMethodCall(methodName, GetDynamicTypeFromType(methodType), instance);
        }

        public static Exception TypeErrorForUnboundMethodCall(string methodName, DynamicType methodType, object instance) {
            string message = string.Format("unbound method {0}() must be called with {1} instance as first argument (got {2} instead)",
                                           methodName, methodType, GetDynamicType(instance));
            return TypeError(message);
        }

        // If a method is called with an incorrect number of arguments
        // You should use TypeErrorForUnboundMethodCall() for unbound methods called with 0 arguments
        public static Exception TypeErrorForArgumentCountMismatch(string methodName, int expectedArgCount, int actualArgCount) {
            return TypeError("{0}() takes exactly {1} argument{2} ({3} given)",
                             methodName, expectedArgCount, expectedArgCount == 1 ? "" : "s", actualArgCount);
        }

        // If hash is called on an instance of an unhashable type
        // We have 2 versions to maintain compatibility with the 2 messages that CPython uses.
        public static Exception TypeErrorForUnhashableType(string typeName) {
            return TypeError(typeName + " objects are unhashable");
        }

        public static Exception TypeErrorForUnhashableType() {
            return TypeError("unhashable type");
        }
    }
}
