// 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
}
}