/* **********************************************************************************
 *
 * 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.Collections.Generic;
using System.Reflection;
using System.Reflection.Emit;
using System.Diagnostics;
using System.Text;

using IronPython.Runtime;

namespace IronPython.Compiler {
    /// <summary>
    /// Represents a tree of parameters & their associated methods.
    /// Each branch down the tree represents the next parameter. There 
    /// is a branch / parameter type. 
    /// </summary>
    [DebuggerDisplay("ParamTree: {ToString()}")]
    class ParamTree {
        #region Private member variables
        ParamTreeNode root = new ParamTreeNode(null, NodeFlags.None);
        int depth;
        bool fFinished;
        MethodInfo optimized;
        FunctionType funcType;
        List<int> extraReturnPositions;
        #endregion

        #region Public API Surface

        public static ParamTree Build(FunctionType functionType, MethodTracker[] methods, int argCnt) {
            ParamTree pt = new ParamTree(argCnt);
            pt.funcType = functionType;

            for (int i = 0; i < methods.Length; i++) {
                pt.AddMethod(methods[i]);
            }

            pt.FinishTree();

            //pt.Walk(new ParamTreeDumper(pt, methods[0].Name));
            return pt;
        }

        public MethodInfo OptimizedMethod {
            get {
                return optimized;
            }
            set {
                optimized = value;
            }
        }

        public List<int> ReturnPositions {
            get {
                return extraReturnPositions;
            }
        }
        
        /// <summary>
        /// Performs a depth-first walk of the tree
        /// </summary>
        public void Walk(IParamWalker callback) {
            callback.PreArgument(0, root.Children.Count);

            for (int i = 0; i < root.Children.Count; i++) {
                WalkWorker(callback, root.Children[i], 0);
            }
            callback.PostArgument(0);
        }

        /// <summary>
        /// Represent settings which make param nodes unique inface of a type that is identical.
        /// </summary>
        public enum NodeFlags {
            None = 0x00,
            ByRef = 0x01,
            Out = 0x02,
            Params = 0x04,
            MixedInstanceStatic = 0x08
        }

        #endregion

        #region Private helper methods

        public ParamTree(int argumentCount) {
            depth = argumentCount;
        }

        public void AddMethod(MethodTracker method) {
            if (fFinished) throw new InvalidOperationException("Cannot add methods to finished param trees");

            ParamTreeNode curNode = root;
            ParameterInfo[] pis = method.GetParameters();
            bool fIsParams = false;

            if (pis.Length > 0 && ReflectionUtil.IsParamArray(pis[pis.Length - 1])) fIsParams = true;

            if (!method.IsStatic) {
                Type instType = method.DeclaringType;
                if ((funcType & FunctionType.FunctionMethodMask) == FunctionType.FunctionMethodMask) {
                    instType = typeof(InstanceArgument);
                }

                curNode = curNode.AppendChild(method, instType, NodeFlags.None, depth == 1);
                AppendParameters(method, curNode, pis, fIsParams, 1, 0);
            } else {
                int depthStart = 0;
                if ((funcType & FunctionType.OpsFunction) != 0 && 
                    (funcType & FunctionType.FunctionMethodMask) == FunctionType.FunctionMethodMask) {
                    // this is an ops function that is combined w/ an ops method.  We need to support
                    // disambiguating between bound & unbound method calls, so we transform arg 1
                    // to an instance just like we do for non-static functions, and then skip the 1st
                    // parameter in AppendParameters.  In either case we want both depths to
                    // start at 1 (we're appending @ depth 1, and reading from param 1 because we've
                    // used param 0) so we just use depthStart here for both.
                    depthStart = 1;
                    curNode = curNode.AppendChild(method, typeof(InstanceArgument), NodeFlags.None, depth == 1);
                }

                AppendParameters(method, curNode, pis, fIsParams, depthStart, depthStart);
            }
            
            root.Methods.Add(method);
        }

        private void AppendParameters(MethodTracker method, ParamTreeNode curNode, ParameterInfo[] pis, bool fIsParams, int depthStart, int pisStart) {
            for (int i = depthStart; i < depth; i++) {
                NodeFlags flags;
                Type curType = GetCurrentType(pis, i - depthStart+pisStart, fIsParams, out flags);

                bool fLastArg = (i == depth - 1);

                curNode = curNode.AppendChild(method, curType, flags, fLastArg);
            }
        }

        /// <summary>
        /// Marks the tree as being finished allowing it to calculate
        /// any final state & throw away any temporary state necessary
        /// for building the tree.  A finished tree cannot have new methods added.
        /// </summary>
        public void FinishTree() {
            fFinished = true;
            if (depth == 0) return;

            // if we have a sole param array our signature should
            // be a param array as well...
            ParameterInfo[] pis = root.Methods[0].GetParameters();

            // if we dont have static & instance methods in this set then
            // the reflect optimizer needs to generate code to check both
            // instance & argument values.  We mark methods that are truly mixed.
            bool fStaticThis=false, fInstance=false;
            for (int i = 0; i < root.Methods.Count; i++) {
                if (root.Methods[i].IsStatic) {
                    if (pis.Length > 0 && pis[0].ParameterType == root.Methods[i].DeclaringType) {
                        fStaticThis = true;
                    }
                } else {
                    fInstance = true;
                }
            }

            if (fStaticThis && fInstance) {
                for (int i = 0; i < root.Children.Count; i++) {
                    root.Children[i].Flags |= NodeFlags.MixedInstanceStatic;
                }
            }
        }

        private Type GetCurrentType(ParameterInfo[] pis, int curArg, bool fIsParams, out NodeFlags flags) {
            flags = fIsParams ? NodeFlags.Params : NodeFlags.None;
            if (!fIsParams || curArg < (pis.Length - 1)) {
                // out & by-ref: out becomes null (we won't include it), by-ref becomes
                // it's normal type and an in-out arg.
                if (pis[curArg].IsOut && !pis[curArg].IsIn) flags |= NodeFlags.Out;
                else if (pis[curArg].ParameterType.IsByRef) flags |= NodeFlags.ByRef;

                if(flags != NodeFlags.None){
                    if (extraReturnPositions == null) extraReturnPositions = new List<int>();
                    extraReturnPositions.Add(curArg);
                }
                
                return pis[curArg].ParameterType;
            } else {
                return pis[pis.Length - 1].ParameterType.GetElementType();
            }
        }

        private void WalkWorker(IParamWalker callback, ParamTreeNode curNode, int depth) {
            callback.Walk(depth, curNode);

            if (curNode.Children.Count != 0) {
                callback.PreArgument(depth + 1, curNode.Children.Count);

                for (int i = 0; i < curNode.Children.Count; i++) {
                    WalkWorker(callback, curNode.Children[i], depth + 1);
                }

                callback.PostArgument(depth + 1);
            }
        }

        #endregion

#if DEBUG
        public override string ToString() {
            StringBuilder sb = new StringBuilder();
            Walk(new ParamTreeDumper(this, this.root.Methods[0].Name, sb));
            return sb.ToString();
        }
#endif

    }

    class ParamTreeNode {
        public Type ParamType;
        public ParamTree.NodeFlags Flags;
        public List<MethodTracker> Methods;
        public List<ParamTreeNode> Children;

        public ParamTreeNode(Type t, ParamTree.NodeFlags flags) {
            ParamType = t;
            Flags = flags;
            Methods = new List<MethodTracker>();
            Children = new List<ParamTreeNode>();
        }

        public ParamTreeNode AppendChild(MethodTracker method, Type curType, ParamTree.NodeFlags flags, bool fLastArg) {
            bool fFound = false;
            ParamTreeNode res = this;

            for (int i = 0; i < Children.Count; i++) {
                if (Children[i].ParamType == curType && Children[i].Flags == flags) {
                    res = Children[i];
                    res.Methods.Add(method);
                    fFound = true;
                    break;
                }
            }

            if (!fFound) {
                res = InsertNewNode(curType, flags);
                res.Methods.Add(method);
            } else if (fLastArg) {
                // last node, we shouldn't be adding
                // extra methods here.  We have two ways
                // we get here:
                //  1. We have a static and non-static overload, prefer the instance method
                //  2. We have default values for one of the methods, prefer the one w/o defaults.
                // 
                // Both of these are identical checks: We prefer the method w/ less parameters.

                Debug.Assert(res.Methods.Count == 2);

                if (method.GetParameters().Length < res.Methods[0].GetParameters().Length) {
                    // remove the old one.
                    res.Methods.RemoveAt(0);
                } else {
                    // remove the new one.
                    res.Methods.RemoveAt(1);
                }
            }

            return res;

        }

        private ParamTreeNode InsertNewNode(Type newNodeType, ParamTree.NodeFlags flags) {
            ParamTreeNode newNode = new ParamTreeNode(newNodeType, flags);

            // we've made the node, use the element type for the checks below...
            if (newNodeType.IsByRef) newNodeType = newNodeType.GetElementType();

            // insert based upon subclassing order (if we're a subclass
            // of someone we need to come first). When we walk the tree we'll
            // then emit checks for more specific types before less specific types.

            OpsReflectedType newDt = Ops.GetDynamicTypeFromType(newNodeType) as OpsReflectedType;
            Type extensibleType = null;
            if (newDt != null) {
                extensibleType = newDt.GetTypeToExtend();
            }

            if(newNodeType != typeof(object)){
                for (int i = 0; i < Children.Count; i++) {                
                    Type childParamType = Children[i].ParamType;
                    if (childParamType.IsByRef) childParamType = childParamType.GetElementType();

                    // extensible types are logically subclasses of their "parent" type, and
                    // therefore their check needs to go first.  If extensible is added first
                    // then the real type will come next automatically, otherwise we'll
                    // check for the type here & early out if we're adding the extensible type.
                    if (newNodeType == extensibleType && childParamType == newDt.type) {
                        Children.Insert(i, newNode);
                        return newNode;
                    }

                    //!!! IsAssignableFrom instead to match TryCall?    
                    if (newNodeType.IsSubclassOf(childParamType) ||
                        (newNodeType.IsClass && childParamType.IsInterface)) {      // classes before interfaces
                        Children.Insert(i, newNode);
                        return newNode;
                    }
                }
            }

            Children.Add(newNode);

            return newNode;
        }
    }

    interface IParamWalker {
        void PreArgument(int param, int typeCount);
        void Walk(int param, ParamTreeNode node);
        void PostArgument(int param);
    }

#if DEBUG
    class ParamTreeDumper : IParamWalker
    {
        private ParamTree pt;
        private StringBuilder sb;
        public ParamTreeDumper(ParamTree pt, string name, StringBuilder sb){
            this.sb = sb;
            this.pt = pt;
            Write(String.Format("Param tree for: {0}", name));
        }

        public ParamTreeDumper(ParamTree pt, string name) : this(pt,name,null) {
        }

        #region IParamWalker Members

        public void PreArgument(int param, int typeCount) {
        }

        public void Walk(int param, ParamTreeNode node) {
            for(int i = 0; i<param+1; i++) Write("    ");
            WriteLine(String.Format("{0} {1}", node.ParamType, node.Flags));
        }

        public void PostArgument(int param) {
        }

        private void Write(string s) {
            if (sb == null) Console.Write(s);
            else sb.Append(s);
        }

        private void WriteLine(string s) {
            if (sb == null) Console.WriteLine(s);
            else sb.AppendLine(s);
        }

        #endregion
    }
#endif
}
