Как найти самый последний общий предок (базовый тип) нескольких типов в 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

Возьмите множество всех общих предков, используйте алгоритм наивного минимума, чтобы найти самого низкого общего предка, а затем убедитесь, что он действительно самый последний:

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.

Answer 2

Вы можете использовать метод mro каждого класса, чтобы получить список классов предков. Сопоставьте список предков с collections.Counter, чтобы на них можно было использовать оператор &, чтобы получить общих предков при сохранении порядка ключей, эффективно эмулируя получение пересечения упорядоченных множеств. Затем используйте функцию next для последовательности предков из ключей агрегированного объекта Counter, чтобы получить самого последнего предка:

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