How can you programmatically find the deepest common base type from a bunch of subclasses?

Question

Given a collection of disparate objects, is it possible to find the most-specific base class they all share?

For instance, given objects with these class hierarchies...

object -> Vehicle -> WheeledVehicle -> Car -> SportsCar
object -> Vehicle -> WheeledVehicle -> Bus
object -> Vehicle -> WheeledVehicle -> MotorCycle
object -> Vehicle -> WheeledVehicle -> Tricycle -> BigWheel
object -> Vehicle -> WheeledVehicle -> Tricycle -> Green Machine

(For fun... http://www.wired.com/autopia/2011/03/green-machine-bike-is-a-big-wheel-for-grownups)

Is it possible to write a function with this signature...

public Type GetCommonBaseType(List<object> objects)
{
    ...
};

...and have it return 'WheeledVehicle'?

My thinking is to somehow build up lists of inheritance chains for each object, reverse them so they all start with 'object', then walk down each of them checking for a match across all lists. If any of the items don't match, then the step before is your deepest matching base type.

However, I'm not sure how to go about building up the chain since 'base' is an internal member. Is this something you can use Reflection to determine?

Answer 1

You can use reflection to do this. Let's assume we are starting from Type instances instead of objects -- this is more generalized and you can trivially convert a list of objects to a list of their runtime types to cover the use case you mentioned.

The idea is to traverse all base classes of each input type and increment a "type instance counter" for each one. After doing this all the common bases of the input types will necessarily have their counter equal to the number of input types. Which one of them is the most derived? Easy, pick any of the input types and start traversing its type hierarchy until you find one of the common bases; that type is the most derived common base.

The code

I 'll use this extension method:

public static IEnumerable<Type> TypeHierarchy(this Type type)
{
    do
    {
        yield return type;
        type = type.BaseType;
    } while (type != null);
}

which then allows this implementation -- thanks to LINQ it reads almost like english:

public Type MostDerivedCommonBase(IEnumerable<Type> types)
{
    if (!types.Any()) return null;

    var counts = new Dictionary<Type, int>();
    var total = types.Count();
    foreach(var type in types.SelectMany(t => t.TypeHierarchy()))
    {
        if (!counts.ContainsKey(type))
        {
            counts[type] = 1;
        }
        else
        {
            counts[type]++;
        }
    }

    return types.First().TypeHierarchy().First(t => counts[t] == total);
}

You can exercise this very easily with e.g.

var types = new[] { typeof(MemoryStream), typeof(FileStream) };
Console.WriteLine(MostDerivedCommonBase(types)); // System.IO.Stream

Update

In hindsight it's obvious that building the dictionary of types to counts can also be done entirely with LINQ. So if compact is your cup of tea, the code can be reduced to:

public Type MostDerivedCommonBase(IEnumerable<Type> types)
{
    if (!types.Any()) return null;

    var counts = types.SelectMany(t => t.TypeHierarchy())
                      .GroupBy(t => t)
                      .ToDictionary(g => g.Key, g => g.Count());

    var total = counts[typeof(object)]; // optimization instead of types.Count()
    return types.First().TypeHierarchy().First(t => counts[t] == total);
}