如何在python中找到几种类型的最新共同祖先（基类型）？

Question

我需要找到一组类的最后一个公共祖先，以便返回该类型。你知道吗

上下文，我正在做一些相当复杂的元程序，包括重载numpy功能。（不要问）我对一个函数有一个数量可变的参数，我已经将它的类型提取到一个集合中（过滤掉一些不相关的类型），使用这个信息，我需要找出类型树最下面的哪个部分，其中所有类型共享同一个基类型。我有一些首次通过的尝试，但我被多重继承等绊倒了。你知道吗

第一次通过：

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

考虑以下类层次结构：

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

预期结果：

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

Answer 1

您可以使用每个类的mro方法来获取祖先类的列表。将祖先列表映射到collections.Counter，这样就可以对它们使用&操作符来获取公共祖先，同时保持键顺序，有效地模拟获取有序集的交集。然后对聚集的Counter对象的键的祖先序列使用next函数来获取最近的祖先：

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))))

所以下面的表达式都是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

请注意，键顺序仅为Python 3.7+维护，因此对于以前的Python版本，可以使用重用Counter属性的collections.OrderedDict子类替换Counter：

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))))

Answer 2

取所有共同祖先的集合，使用简单的最小算法来查找最低的共同祖先，然后验证它实际上是最新的：

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")

使用一个简单的最小值看起来可能有问题，但它实际上是好的，即使是在多重继承中。如果有一个明确的最低共同祖先，那么它是all_common_ancestors（包括它本身）的每个元素的子类，因此我们将在到达它时将candidate设置为最低共同祖先，然后再也不会更改candidate。如果没有明确的最低公共祖先，那么无论candidate以循环结尾结束，它都不会通过验证检查。你知道吗

更棘手的部分是处理__subclasscheck__/__subclasshook__覆盖。我认为这个实现应该足够健壮，可以处理大多数常见的ABC情况，但是当任意的__subclasscheck__实现使得issubclass定义的图甚至不是DAG时，最低公共祖先的整个概念就变得奇怪了。你知道吗