// Copyright (C) 2007 Jesse Jones
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Smokey
{    
    /// Thrown if none of the overloads can be called with the actual arguments.
    /// For example, if the overloads are:
    ///    long Add(int lhs, int rhs);
    ///    long Add(long lhs, long rhs);
    /// and the actual arguments are int and long then neither overload is
    /// applicable (can't assign a long to an int).
    internal class NoApplicableOverloadException : Exception
    {
        public NoApplicableOverloadException(string text) : base(text)
        {
        }
    }    
    
    /// Thrown if no most specific overload can be found. For example, if Trash
    /// is a subclass of Container and the overloads are:
    ///    void DragAndDrop(Trash, object);
    ///    void DragAndDrop(Container, Image);
    /// Then Trash is more specific than Container, but Image is more specific
    /// than object. Therefore neither method is more specific than the other
    /// and we have an ambiguity.
    internal class AmbiguousOverloadException : Exception
    {
        public AmbiguousOverloadException(string text) : base(text)
        {
        }
    }
    
    /// Like most languages C# offers two forms of method dispatch: at compile
    /// time methods are selected based on the name of the method and the 
    /// compile time type of the formal arguments (overloading), at runtime 
    /// methods are selected based on the actual type of the this argument 
    /// (virtuals). It's also possible to dynamically select methods based on 
    /// the runtime type of all the arguments. This is known as multiple 
    /// dispatch and treats all arguments identically: there is no special this 
    /// argument.
    ///
    /// By far the most useful form of multiple dispatch is double dispatch
    /// which is useful whenever you have an operation which can apply to two 
    /// types at once. Examples include drag and drop, shape intersection, and 
    /// working with polymorphic trees or graphs. Without double dispatch this 
    /// sort of thing is typically done with the visitor pattern which is much 
    /// invasive and much clumsier.
    ///    
    /// The way this works is that we have a set of method overloads (in our 
    /// case this is an instance of DoubleDispatch). When the method is called
    /// the actual runtime types of the arguments are used to find the most 
    /// specific overload which is then executed. The overload can then elect 
    /// to call the next most specific overload.
    ///
    /// Conceptually double dispatch works like this, when the method is called:
    ///
    /// 1) A list of applicable overloads is constructed. These are the overloads
    /// which can be called with the actual argument types.
    ///
    /// 2) The list is sorted by specificity. For two overloads A and B:
    /// 
    /// 2a) If the formal arguments for A and B are the same for an argument 
    /// position then A and B are unordered at that position (that argument 
    /// supplies no information about the order of the two overloads).
    /// 
    /// 2b) If the formal argument for A is a subclass of the formal argument for
    /// B at a position then A precedes B at that position.
    ///
    /// 2c) Otherwise the overloads are unordered at that position.
    ///
    /// The method A is more specific than B if and only if A preceded B for at 
    /// least one argument position and B does not precede A in any argument 
    /// position. Otherwise A and B are ambiguous. Note that the overloads after
    /// a most specific overload may be ambiguous.
    public class DoubleDispatch<R>
    {        
        public delegate R Typed<T1, T2>(T1 lhs, T2 rhs);
                        
        /// Adds an overload to the method set. 
        public void Register<T1, T2>(Typed<T1, T2> overload)
        {
            foreach (Overload existing in m_overloads)
                Debug.Assert(existing.Lhs != typeof(T1) || existing.Rhs != typeof(T2));    // adding the same overload twice will make it ambiguous

            Untyped thunk = delegate (object lhs, object rhs)
            {
                return overload((T1) lhs, (T2) rhs);
            };
            
            m_overloads.Add(new Overload(typeof(T1), typeof(T2), thunk));
            m_cache.Clear();
            m_sorted = false;
        }
        
        /// Uses the runtime types of lhs and rhs to find the most specific
        /// overload which can be called with the arguments. If no overloads 
        /// can be called with the actual arguments NoApplicableOverloadException 
        /// is thrown.If no most specific overload can be found 
        /// AmbiguousOverloadException is thrown. 
        public R Dispatch(object lhs, object rhs)
        {    
            m_actual.Lhs = lhs.GetType();
            m_actual.Rhs = rhs.GetType();
            
            List<Overload> temp;
            if (m_cache.TryGetValue(m_actual, out temp))
            {
                m_applicable = temp;
            }
            else
            {
                DoGetOverloads();
                m_cache[m_actual] = m_applicable;
            }
            
            m_current = 0;
            return m_applicable[m_current].Target(lhs, rhs);
        }
        
        /// Overloads can use this to call the next most specific overload (which
        /// may be ambiguous). The arguments should be the same that were passed 
        /// to Dispatch.
        public R Next(object lhs, object rhs)
        {
            Debug.Assert(lhs.GetType() == m_actual.Lhs);
            Debug.Assert(rhs.GetType() == m_actual.Rhs);
            Debug.Assert(m_current >= 0);
            
            if (++m_current < m_applicable.Count)
            {
                if (m_current + 1 < m_applicable.Count)
                    if (m_applicable[m_current].Precedes(m_applicable[m_current + 1]) == 0)
                        throw new AmbiguousOverloadException(string.Format("Ambiguous overloads {0} and {1} when calling Next", m_actual.Lhs, m_actual.Rhs));
                
                return m_applicable[m_current].Target(lhs, rhs);
            }
            else
                throw new NoApplicableOverloadException(string.Format("Couldn't find any compatible overloads for {0} and {1} when calling Next", m_actual.Lhs, m_actual.Rhs));
        }
        
        #region Internal types
        private delegate R Untyped(object lhs, object rhs);

        private struct ActualTypes 
        {
            public Type Lhs;
            public Type Rhs;
            
            public ActualTypes(Type lhs, Type rhs)
            {
                Lhs = lhs;
                Rhs = rhs;
            }
    
            public override bool Equals(object rhsObj)
            {
                if (rhsObj == null)            
                    return false;
                
                if (GetType() != rhsObj.GetType()) 
                    return false;
                
                ActualTypes rhs = (ActualTypes) rhsObj;                
                return Lhs == rhs.Lhs && Rhs == rhs.Rhs;
            }
                
            public bool Equals(ActualTypes rhs)
            {                
                return Lhs == rhs.Lhs && Rhs == rhs.Rhs;
            }

            public static bool operator==(ActualTypes lhs, ActualTypes rhs)
            {                
                return lhs.Lhs == rhs.Lhs && lhs.Rhs == rhs.Rhs;
            }
            
            public static bool operator!=(ActualTypes lhs, ActualTypes rhs)
            {
                return !(lhs == rhs);
            }
            
            public override int GetHashCode()    
            {
                return Lhs.GetHashCode() ^ Rhs.GetHashCode();
            }
        }

        private struct Overload 
        {
            public Type Lhs;
            public Type Rhs;
            public Untyped Target; 
            
            public Overload(Type lhs, Type rhs, Untyped target)
            {
                Lhs = lhs;
                Rhs = rhs;
                Target = target;
            }

            public int Precedes(Overload rhs)
            {
                bool lhsBetterFor1 = Lhs.IsSubclassOf(rhs.Lhs);
                bool lhsBetterFor2 = Rhs.IsSubclassOf(rhs.Rhs);

                bool rhsBetterFor1 = rhs.Lhs.IsSubclassOf(Lhs);
                bool rhsBetterFor2 = rhs.Rhs.IsSubclassOf(Rhs);
                
                if ((lhsBetterFor1 || lhsBetterFor2) && !rhsBetterFor1 && !rhsBetterFor2)
                    return -1;
                else if ((rhsBetterFor1 || rhsBetterFor2) && !lhsBetterFor1 && !lhsBetterFor2)
                    return +1;
                else
                    return 0;
            }    
        }
        #endregion

        #region Private methods    
        private void DoGetOverloads()
        {
            if (!m_sorted)
            {
                m_overloads.Sort(delegate (Overload a, Overload b) // sort order doesn't depend on actual arguments so we can do it once
                {
                    return a.Precedes(b);
                });

                m_sorted = true;
            }
            
            DoGetApplicableOverloads(m_actual.Lhs, m_actual.Rhs);

            if (m_applicable.Count > 0)
            {
                if (m_applicable.Count > 1 && m_applicable[0].Precedes(m_applicable[1]) == 0)
                    throw new AmbiguousOverloadException(string.Format("Ambiguous overloads {0} and {1}", m_actual.Lhs, m_actual.Rhs));
            }
            else
                throw new NoApplicableOverloadException(string.Format("Couldn't find any compatible overloads for {0} and {1}", m_actual.Lhs, m_actual.Rhs));
        }
        
        private void DoGetApplicableOverloads(Type lhs, Type rhs)
        {
            m_applicable.Clear();
            
            foreach (Overload overload in m_overloads)
            {
                if (overload.Lhs.IsAssignableFrom(lhs))
                    if (overload.Rhs.IsAssignableFrom(rhs))
                        m_applicable.Add(overload);
            }
        }
        #endregion

        #region Fields
        private Dictionary<ActualTypes, List<Overload>> m_cache = new Dictionary<ActualTypes, List<Overload>>();
        private List<Overload> m_overloads = new List<Overload>();
        private bool m_sorted = false;
        
        private ActualTypes m_actual = new ActualTypes();
        private List<Overload> m_applicable = new List<Overload>();
        private int m_current = -1;
        #endregion
    }
}