How to find most recent common ancestor (base type) of several types in python?

user_1424589 0
Viewed 427

I need to find the last common ancestor of a group of classes so I can return that type.

Context, I'm doing some rather complex meta-programing involving overloading numpy functionality. (don't ask) I have a variable number of arguments to a function the types of which I have extracted into a set (with some filtering out of irrelevant types) using this information I need to figure out what the furthest down the type tree where all types share the same base type. I have some first pass attempts but I'm getting tripped up by multiple inheritance and the like.

first pass:

def lca_type(types):
    if len(types) == 1:
        return types.pop()
    filtered_types = set()
    for type in types:
        if not any(issubclass(type, x) for x in types):
            filtered_types.add(type)
    if len(filtered_types) == 1:
        return filtered_types.pop()
    # TODO: things get tricky here

consider the following class hierarchy:

class A(object):
    pass
class B(A):
    pass
class C(A):
    pass
class D(A):
    pass
class B1(B):
    pass
class B2(B):
    pass
class BC(C, B1):
    pass
class CD(C, D):
    pass
class D1(D):
    pass
class BD(B, D):
    pass
class B1_1(B1):
    pass

expected results:

lca_type({A,BD}) == A
lca_type({C}) == C
lca_type({B1,B2}) == B
lca_type({{B1_1, D}) == A
lca_type({CD, BD}) == D
lca_type({B1_1, BC}) == B1
casting inheritance oop python types
2 Answers

You can use the mro method of each class to get a list of ancestor classes. Map the list of ancestors to collections.Counter so that you can use the & operator on them to get common ancestors while maintaining the key order, effectively emulating getting the intersection of ordered sets. Then use the next function on the sequence of ancestors from the keys of the aggregated Counter object to obtain the most recent ancestor:

from functools import reduce
from operator import and_
from collections import Counter

def lca_type(classes):
    return next(iter(reduce(and_, (Counter(cls.mro()) for cls in classes))))

so that the following expressions will all be True:

lca_type({A, BD}) == A
lca_type({C}) == C
lca_type({B1, B2}) == B
lca_type({B1_1, D}) == A
lca_type({CD, BD}) == D
lca_type({B1_1, BC}) == B1
lca_type({B1_1, BC, BD}) == B

Note that the key order is only maintained for Python 3.7+, so for previous Python versions, you can replace Counter with a subclass of collections.OrderedDict that reuses the attributes of Counter instead:

from functools import reduce
from operator import and_
from collections import Counter, OrderedDict
import collections

collections.Counter = Counter = type('Counter', (OrderedDict,), dict(vars(Counter)))

def lca_type(classes):
    return next(iter(reduce(and_, (Counter(cls.mro()) for cls in classes))))
user_68909120

Take the set of all common ancestors, use a naive minimum algorithm to find the lowest common ancestor, then verify that it's actually most recent:

def lca_type(types):
    mros = [t.__mro__ for t in types]
    all_common_ancestors = set(mros[0]).intersection(*mros[1:])

    ancestor_iter = iter(all_common_ancestors)
    candidate = next(ancestor_iter)
    for next_candidate in ancestor_iter:
        if issubclass(next_candidate, candidate):
            candidate = next_candidate

    if all(issubclass(candidate, ancestor) for ancestor in all_common_ancestors):
        return candidate
    else:
        raise ValueError("No unambiguous lowest common ancestor")

The use of a naive minimum may look questionable, but it's actually fine, even in multiple inheritance. If there is an unambiguous lowest common ancestor, then it's a subclass of every element of all_common_ancestors (including itself), so we'll set candidate to the lowest common ancestor when we reach it and then never change candidate again. If there is no unambiguous lowest common ancestor, then whatever candidate ends up as at the end of the loop, it won't pass the verification check.

The trickier part is dealing with __subclasscheck__/__subclasshook__ overrides. I think this implementation should be robust enough to handle most common ABC cases, but the entire concept of a lowest common ancestor gets weird when arbitrary __subclasscheck__ implementations make the graph defined by issubclass not even a DAG.

user_23571120
Related