Python 的 MRO、C3 线性化是否深度优先？根据经验，它没有

Question

我正在阅读 Python Multiple Inheritance (on Programiz) and then I found this Whosebug question, Method Resolution Order (MRO) in new-style classes? 但在这个问题中，一些程序员如 Alex Martelli 说它使用深度优先方法，我对此表示怀疑。

示例：

class H():
    def m(self):
        print("H")

class G(H):
    def m(self):
        print("G")
        super().m()

class I(G):
    def m(self):
        print("I")
        super().m()


class F(H):
    def m(self):
        print("F")
        super().m()

class E(H):
    def m(self):
        print("E")
        super().m()

class D(F):
    def m(self):
        print("D")
        super().m()

class C(E, F, G):
    def m(self):
        print("C")
        super().m()

class B():
    def m(self):
        print("B")
        super().m()

class A(B, C, D):
    def m(self):
        print("A")
        super().m()

x = A()
x.m()

因此，如果我基于 MRO 构建图表，那么根据深度优先，它应该遵循以下内容：

路径应该是：

A-->B-->C-->E-->F-->G-->D-->H

但是如果你运行上面的代码你会得到：

A
B
C
E
D
F
G
H

因为它走的是这条路：

A-->B-->C-->E-->D-->F-->G-->H

现在我对节点“D”或class“D”感到困惑，它在深度上首先出现在较早的时候，在 MRO 中它出现较晚。

这是怎么回事？

Answer 1

and path should be:

A-->B-->C-->E-->F-->G-->D-->H

F 不能出现在 D 之前 - 这会自相矛盾 - 参见 class D.

C3线性化算法的工作方式，你要线性化parent，然后，只要不矛盾，你就可以线性化child。所以我一次线性化这些，从 parents 开始。在我们到达 C 和 A 之前，大多数都是微不足道的：

class PrettyType(type):
    """make the repr of the classes look nice when finally listed"""
    def __repr__(self):
        return self.__name__

# subclasses of O will also have the metaclass:
class O(metaclass=PrettyType): 'O, object'

class H(O): 'H, O, object'
# H's parent is O

class G(H): 'G, H, O, object'
# G's linearization is itself followed by its parent's linearization.

class I(G): 'I, G, H, O, object'
# I's linearization is I followed by G's

class F(H): 'F, H, O, object'

class E(H): 'E, H, O, object'

class D(F): 'D, F, H, O, object'

class C(E, F, G): 'C, E, F, G, H, O, object' 
# C's linearization is C followed by a consistent linearization of 
# its parents, left to right. 
# First C, then E - then you might be tempted to put H after E,
# but H must come after F and G (see class F and G)
# so we try F's linearization, noting that H comes after G,
# so we try G's linearization, H then consistently comes next, then object

class B(O): 'B, O, object'

而 A 是：

class A(B, C, D): 'A, B, C, E, D, F, G, H, O, object'
# final complex case -      ^--^ can't go from E to F 
#                                D must come before F (see class D)
#                              ^--^ After D, can do F, 
#                                    then finish with C's MRO 
#                                    with no contradictions

这 3 个标准是，正如我要解释的那样：

parents MRO 保持一致
本地 MRO 保持一致
无周期性

正如我所说，该算法是您从左到右尊重 parent，但深度优先，除非您会到达被 [=49 阻挡的共享 parent =] （例如 F 被 child, D 挡住了）在这种情况下你会寻找其他候选人（D 那么，不矛盾，没关系，那么你可以 select F 和其余的C的MRO。)

>>> A.mro()
[A, B, C, E, D, F, G, H, O, <class 'object'>]

直接线性化而不首先线性化 parents

我们可以通过避免矛盾来完成线性化。

再次，

从左到右
深度优先——除非分享parent被屏蔽（一定能回来）
不允许有循环关系

Python 的 MRO、C3 线性化是否深度优先？根据经验，它没有

Does Python's MRO, C3 linearization work depth-first? Empirically it does not

python

graph

method-resolution-order

python-3.x

直接线性化而不首先线性化 parents