How to find the minimum covariant type for best fi

There's IsAssignableFrom method returns a boolean value indicates if one type is assignable from another type.

How can we not only test if they are assignable from or to each other, but also know the minimum covariant type for best fit?

Consider the following example(C# 4.0)

Code

// method body of Func is irrelevant, use default() instead
Func<char[]> x = default(Func<char[]>);
Func<int[]> y = default(Func<int[]>);

Func<Array> f = default(Func<Array>);
Func<IList> g = default(Func<IList>);

g=x;
g=y;

y=x; // won't compile
x=y; // won't compile

// following two are okay; Array is the type for the covariance
f=x; // Array > char[] -> Func<Array> > Func<char[]> 
f=y; // Array > int[] -> Func<Array> > Func<int[]> 

// following two are okay; IList is the interface for the covariance
g=x;
g=y;

In the example above, what to find is the type between char[] and int[].

回答1:

update:

It turns out FindInterfaceWith can be simplified and to build a flatten type hierarchy becomes redundant as the base classes are not necessarily involved, as long as we take the type itself into account when it is an interface; so I've added an extension method GetInterfaces(bool). Since we can sort the interaces by the rules of coverage, the sorted intersection of interfaces are the candidates. If all of them are equally good, I said none of them is considered the best one. If it's not the case, then the best one must cover one of the others; and because they are sorted, this kind of relationship should exists in the right most two interfaces in the array to denote that there is a best interface in common which is the most specific.

The code can be simplified by using Linq; but in my scenario, I should reduce the requirement of references and namespaces as possible ..

Code

using System;

public static class TypeExtensions {
    static int CountOverlapped<T>(T[] ax, T[] ay) {
        return IntersectPreserveOrder(ay, ax).Length;
    }

    static int CountOccurrence(Type[] ax, Type ty) {
        var a = Array.FindAll(ax, x => Array.Exists(x.GetInterfaces(), tx => tx.Equals(ty)));
        return a.Length;
    }

    static Comparison<Type> GetCoverageComparison(Type[] az) {
        return (tx, ty) => {
            int overlapped, occurrence;
            var ay = ty.GetInterfaces();
            var ax = tx.GetInterfaces();

            if(0!=(overlapped=CountOverlapped(az, ax).CompareTo(CountOverlapped(az, ay)))) {
                return overlapped;
            }

            if(0!=(occurrence=CountOccurrence(az, tx).CompareTo(CountOccurrence(az, ty)))) {
                return occurrence;
            }

            return 0;
        };
    }

    static T[] IntersectPreserveOrder<T>(T[] ax, T[] ay) {
        return Array.FindAll(ax, x => Array.FindIndex(ay, y => y.Equals(x))>=0);
    }

    /*
    static T[] SubtractPreserveOrder<T>(T[] ax, T[] ay) {
        return Array.FindAll(ax, x => Array.FindIndex(ay, y => y.Equals(x))<0);
    }

    static Type[] GetTypesArray(Type typeNode) {
        if(null==typeNode) {
            return Type.EmptyTypes;
        }

        var baseArray = GetTypesArray(typeNode.BaseType);
        var interfaces = SubtractPreserveOrder(typeNode.GetInterfaces(), baseArray);
        var index = interfaces.Length+baseArray.Length;
        var typeArray = new Type[1+index];
        typeArray[index]=typeNode;
        Array.Sort(interfaces, GetCoverageComparison(interfaces));
        Array.Copy(interfaces, 0, typeArray, index-interfaces.Length, interfaces.Length);
        Array.Copy(baseArray, typeArray, baseArray.Length);
        return typeArray;
    }
    */

    public static Type[] GetInterfaces(this Type x, bool includeThis) {
        var a = x.GetInterfaces();

        if(includeThis&&x.IsInterface) {
            Array.Resize(ref a, 1+a.Length);
            a[a.Length-1]=x;
        }

        return a;
    }

    public static Type FindInterfaceWith(this Type type1, Type type2) {
        var ay = type2.GetInterfaces(true);
        var ax = type1.GetInterfaces(true);
        var types = IntersectPreserveOrder(ax, ay);

        if(types.Length<1) {
            return null;
        }

        Array.Sort(types, GetCoverageComparison(types));
        var type3 = types[types.Length-1];

        if(types.Length<2) {
            return type3;
        }

        var type4 = types[types.Length-2];
        return Array.Exists(type3.GetInterfaces(), x => x.Equals(type4)) ? type3 : null;
    }

    public static Type FindBaseClassWith(this Type type1, Type type2) {
        if(null==type1) {
            return type2;
        }

        if(null==type2) {
            return type1;
        }

        for(var type4 = type2; null!=type4; type4=type4.BaseType) {
            for(var type3 = type1; null!=type3; type3=type3.BaseType) {
                if(type4==type3) {
                    return type4;
                }
            }
        }

        return null;
    }

    public static Type FindAssignableWith(this Type type1, Type type2) {
        var baseClass = type2.FindBaseClassWith(type1);

        if(null==baseClass||typeof(object)==baseClass) {
            var @interface = type2.FindInterfaceWith(type1);

            if(null!=@interface) {
                return @interface;
            }
        }

        return baseClass;
    }
}

There're two recursive methods; one is FindInterfaceWith, the other is an important method GetTypesArray as there is already a method named GetTypeArray of class Type with a different of usage.

It works like the method Akim provided GetClassHierarchy; but in this version, it builds an array like:

output of hierarchy

a[8]=System.String
a[7]=System.Collections.Generic.IEnumerable`1[System.Char]
a[6]=System.Collections.IEnumerable
a[5]=System.ICloneable
a[4]=System.IComparable
a[3]=System.IConvertible
a[2]=System.IEquatable`1[System.String]
a[1]=System.IComparable`1[System.String]
a[0]=System.Object

As we are aware of they are in a particular order, which is how it makes things work. The array GetTypesArray built is in fact a flatten tree. The array is actually in the model as the following:

diagram

Note the relation of some interfaces implementation such as IList<int> implements ICollection<int> are not linked with lines in this diagram.

The interfaces in the returning array is sorted by Array.Sort with the ordering rules provided by the GetCoverageComparison.

There are some things to mention, for example, the possibility of multiple interfaces implementation been mentioned not only once in some answers(like [this]); and I have defined the way to solve them, those are:

note
1. The GetInterfaces method does not return interfaces in a particular order, such as alphabetical or declaration order. Your code must not depend on the order in which interfaces are returned, because that order varies.
2. Because of recursion, the base classes are always ordered.
3. If two interfaces have the same coverage, neither of them will be considered eligible.
  
  Suppose we have these interfaces defined(or classes are just fine):
```
public interface IDelta {
}

public interface ICharlie {
}

public interface IBravo: IDelta, ICharlie {
}

public interface IAlpha: IDelta, ICharlie {
}
```
  then which one is better for assignment of IAlpha and IBravo? In this case, FindInterfaceWith just returns null.

In the question [ How to find the smallest assignable type in two types (duplicate)? ], I stated:

a wrong deduction

If this supposition was correct, then the FindInterfaceWith becomes a redundant method; because of the only difference between FindInterfaceWith and FindAssignableWith is:

FindInterfaceWith returns null if there was a best choice of class; while FindAssignableWith returns the exact class directly.

However, now we can look at the method FindAssignableWith, it has to call other two methods is based on the original assumption, The paradoxical bug just disappeared magically.

About coverage comparison rule of ordering interfaces, in the delegate GetCoverageComparison, I use:

dual rules
1. compare two interfaces in a source interfaces array, with each covering how many others in the source, by calling CountOverlapped
2. If rule 1 does not distinguish them (returns 0), the secondary ordering is to call CountOccurrence to determine which has been inherited more times by others and then comparing
  
  the two rules are equivalent to the Linq query:
```
interfaces=(
    from it in interfaces
    let order1=it.GetInterfaces().Intersect(interfaces).Count()
    let order2=(
        from x in interfaces
        where x.GetInterfaces().Contains(it)
        select x
        ).Count()
    orderby order1, order2
    select it
    ).ToArray();
```
  FindInterfaceWith will then perform the possibly recursive call, to figure out is this interface sufficient to recognized as the most common interface or just another relation like IAlpha and IBravo.

And about the method FindBaseClassWith, what it returns is different from the original assumption of if any parameter is null then it returns null. It actually returns another argument passed in.

This is related to the question [ What should the method `FindBaseClassWith` return? ] about method chaining of FindBaseClassWith. In the current implementation, we can call it like:

method chaining

var type=
    typeof(int[])
        .FindBaseClassWith(null)
        .FindBaseClassWith(null)
        .FindBaseClassWith(typeof(char[]));

It will return typeof(Array); thank to this feature, we can even call

var type=
    typeof(String)
        .FindAssignableWith(null)
        .FindAssignableWith(null)
        .FindAssignableWith(typeof(String));

What we may not able to do with my implementation is to call FindInterfaceWith like above, because of the possibility of relations like IAlpha and IBravo.

I've had the code tested in some situations by calling FindAssignableWith as the examples shown:

output of assignable types

(Dictionary`2, Dictionary`2) = Dictionary`2
(List`1, List`1) = IList
(Dictionary`2, KeyValuePair`2) = Object
(IAlpha, IBravo) = <null>
(IBravo, IAlpha) = <null>
(ICollection, IList) = ICollection
(IList, ICollection) = ICollection
(Char[], Int32[]) = IList
(Int32[], Char[]) = IList
(IEnumerable`1, IEnumerable`1) = IEnumerable
(String, Array) = Object
(Array, String) = Object
(Char[], Int32[]) = IList
(Form, SplitContainer) = ContainerControl
(SplitContainer, Form) = ContainerControl

The List'1 test appears IList is because I tested typeof(List<int>) with typeof(List<String>); and the Dictionary'2 are both Dictionary<String, String>. Sorry that I did not do the work to present the exact type names.

回答2:

The simplest case would be iterating over the base types of one object and checking them for being assignable with the other type, like this:

Code

public Type GetClosestType(Type a, Type b) {
    var t=a;

    while(a!=null) {
        if(a.IsAssignableFrom(b))
            return a;

        a=a.BaseType;
    }

    return null;
}

This will produce System.Object for two types which are unrelated, if they are both classes. I'm not sure if this behaviour met your requirement.

For more advanced cases, I'm using a custom extension method called IsExtendablyAssignableFrom.

It can handle different numeric types, generics, interfaces, generic parameters, implicit conversions, nullable, boxing/unboxing, and pretty much all the types I have come across with when implementing my own compiler.

I've uploaded the code into a separate github repository [here], so you could use it in your project.

回答3:

If you look at base classes only, the problem is trivial and a solution is given by Impworks's answer ("iterating over one object's parents and checking them for being assignable with the other type").

But if you want to include also interfaces, there's no unique solution to the problem, as you note yourself with your IDelta and ICharlie example. Two or more interfaces can easily be equally "good", so there's no single best solution. One can easily construct arbitrarily complex diagrams (graphs) of interface inheritances, and it's easy to see from such diagrams that there's no well-defined "FindAssignableWith".

Besides, covariance/contravariance in C# are used for variance kinds of generic types. Let me give an example. Supose we have

type1: System.Func<string>
type2: System.Func<Tuple<int>>

then of course with base classes, the "FindAssignableWith" could be

solutionA: System.MulticastDelegate

But the type Func<out T> is also covariant (out) in its type parameter T. Therefore, the type

solutionB: System.Func<System.Object>

is also a solution in the sense that it IsAssignableFrom the two given types type1 and type2. But the same could be said of

solutionC: System.Func<System.IComparable>

which works because both string and Tuple<> are IComparable.

So in the general case, there's no unique solution. So unless you specify precise rules describing what you want, we can't come up with an algorithm that finds your solution.