Python 中的 MRO

发表于 分类于 阅读次数： 本文字数： 5.2k
剖析 Python 中的 MRO 算法

问题引入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class A:
    def show():
        print("A")

# B 直接继承 object
class B:
    def show():
        print("B")

class C(A):
    pass

class D(C, B):
    pass

D.show() # A

继承图

graph TD;
    A-->C;
    C-->D;
    B-->D;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class A:
    def show():
        print("A")

# 修改 B 的定义继承自 A
class B(A):
    def show():
        print("B")

class C(A):
    pass

class D(C, B):
    pass

D.show() # B

继承图

graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;

Python MRO 简介

Python 中的 MRO (Method Resolution Order 方法解析顺序)是指在多重继承的情况下，确定调用方法的顺序。

Python 历史中主要存在过三种 MRO 算法，分别是 DFS 算法、改进的 DFS 算法、C3算法。

Python 有两种类：经典类（classic class）和新式类（new-style class）。

  • Python 所有的经典类都是使用的 DFS 算法
  • Python2.2 中引入了新式类，使用的是改进的 DFS 算法
  • Python2.3 中将新式类的 MRO 算法改为 C3 算法，由于 Python3 中只有新式类，所以 Python3 中的 MRO 算法就是 C3 算法

查看 Python 的 MRO 顺序方法：

1
2
3
4
5
6
7
8
# 经典类的查看方法
import inspect
inspect.getmro(D)

# 新式类的查看方法
D.__mro__
D.mro()
inspect.getmro(D)

算法分析的关系代码

1
2
3
4
5
6
7
8
class A:
    pass
class B(A):
    pass
class C(A):
    pass
class D(B, C):
    pass

以上的类继承关系可以用下面的图表示：

graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;

DFS 算法

DFS 算法是 Python 2 中经典类的 MRO 算法，其基本思想是从左到右，深度优先遍历所有的父类，将遍历到的父类放入一个列表中，如果遍历到的父类已经在列表中，则跳过。

将上面的类继承按照深度优先算法获取继承顺序为 D, B, A, C, A，重复类只保留第一个，所以得到的 MRO 为 [D, B, A, C]

改进的 DFS 算法

在 Python2.2 中，新式类的 MRO 算法改为了改进的 DFS 算法，其基本思想是从左到右，深度优先遍历所有的父类，将遍历到的父类放入一个列表中，如果遍历到的父类已经在列表中，将其移动到列表的最后。

将上面的类继承按照深度优先算法获取继承顺序为 D, B, A, C, A，重复类只保留最后一个，所以得到的 MRO 为 D, B, C, A

C3 算法

算法原理

C3 算法才是本文的重点，C3 的名称是因为该算法实现了三个重要的一致性(consistent)属性

  • 基于一致性扩展的优先图(extended precedence graph)

    • 找到两个类的最小公共子类，然后寻找着这两个类到最小公共子类之间，两个类或者两个类的任意子类谁在最前面，谁就是应该被优先使用的类

    • 如果B和C都是A的基类，B继承了D，C继承了E，那D和E的顺序是不受局部优先规则的制约的，需要使用一致性扩展的优先图来确定D和E的顺序

      graph TD;
  D-->B;
  E-->B;
  D-->C;
  F-->C;
  B-->A;
  C-->A;

      如果只有在 E 和 F 中实现了该方法，那边 A 应该使用 E 还是 F 就需要使用一致性扩展的优先图来确定

  • 局部优先原则(local precedence order)

    • 当一个类同时继承了多个类的时候，优先使用前面这个类里面的方法
    • 比如A继承B和C，那么A读取父类方法，应该优先使用B的方法而不是C的方法

  • 单调性原则(monotonicity)

    • 子类和父类的搜索顺序一致，类所使用的方法必须是它的直接父类中某一个类使用的方法，如果直接父类没有调用过这个方法，子类是不允许调用这个方法的
    • 子类不能改变父类的方法搜索顺序

C3 的合并方法是选择这些列表的头部中第一个符合条件者，它不出现在任何这些列表的尾部（一个列表的除了第一个元素的所有元素）之中。注意一个良好头部，可以同时出现为多个列表的第一个元素，但是禁止它出现在任何其他地方。将选择的元素从以它作为头部的所有列表中移除，并将它填加到输出列表。重复选择并移除良好头部并扩展输出列表的过程，直到所有余下的列表被竭尽。如果在某一点上，因为所有余下列表的头部都出现在某个列表的尾部中，而没有良好头部可选，那么由于在继承层级中依赖的不一致次序，归并过程不能计算下去，故而最初类的线性化不存在。

总结下来合并步骤

  1. 获取直接继承类的 MRO 顺序
  2. 从前向后找每个列表中的第一个元素
    • 如果该元素没有出现在其他列表中，则将该元素添加到结果列表中
    • 如果该元素仅出现在其他列表的开头，则将该元素添加到结果列表中，并且在每个列表中删除该元素
    • 如果该元素出现在其他列表的开头以外的位置，则跳过该列表，继续下个列表进行检测
    • 如果所有列表都没有找到符合条件的元素，则抛出异常(TypeError)

示例

graph TD;
    object-->X;
    object-->Y;
    X-->A;
    Y-->A;
    Y-->B;
    A-->C;
    B-->C;
text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
X = [X, object]
Y = [Y, object]
A = [A, X(), Y()]
  = [A, [X, object], [Y, object]]
  = [A, X, [object], [Y, object]]
  = [A, X, Y, [object], [object]]
  = [A, X, Y, object]

B = [B, Y()]
  = [B, [Y, object]]
  = [B, Y, [object]]
  = [B, Y, object]

C = [C, A(), B()]
  = [C, [A, X, Y, object], [B, Y, object]]
  = [C, A, [X, Y, object], [B, Y, object]]
  = [C, A, X, [Y, object], [B, Y, object]]
  = [C, A, X, B, [Y, object], [Y, object]]
  = [C, A, X, B, Y, [object], [object]]
  = [C, A, X, B, Y, object]

代码验证

1
2
3
4
5
6
7
8
9
10
11
12
class X:
    pass
class Y:
    pass
class A(X, Y):
    pass
class B(Y):
    pass
class C(A, B):
    pass
C.mro()
# [__main__.C, __main__.A, __main__.X, __main__.B, __main__.Y, object]

错误示例

graph TD;
    object-->X;
    object-->Y;
    X-->A;
    Y-->A;
    Y-->B;
    X-->B;
    A-->C;
    B-->C;
text
1
2
3
4
5
6
X = [X, object]
Y = [Y, object]
A = [A, X(), Y()] = [A, [X, object], [Y, object]] = [A, X, [object], [Y, object]] = [A, X, Y, [object], [object]] = [A, X, Y, object]
B = [B, Y(), X()] = [B, [Y, object], [X, object]] = [B, Y, [object], [X, object]] = [B, Y, X, [object], [object]] = [B, Y, X, object]
C = [C, A(), B()] = [C, [A, X, Y, object], [B, Y, X, object]] = [C, A, [X, Y, object], [B, Y, X, object]] = [C, A, B, [X, Y, object], [Y, X, object]]
此时，无法找到符合条件的元素，所以抛出异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class X:
    pass

class Y:
    pass

class A(X, Y):
    pass

class B(Y, X):
    pass

class C(A, B):
    pass
# TypeError: Cannot create a consistent method resolution
# order (MRO) for bases X, Y

问题解答

现在解答最开始的问题

第一个代码块中输出 A 的原因

graph TD;
    A-->C;
    C-->D;
    B-->D;
text
1
2
3
4
5
6
7
8
9
10
11
A = [A, object]
C = [C, A()] = [C, [A, object]] = [C, A, object]
B = [B, object]
D = [D, C(), B()]
  = [D, [C, A, object], [B, object]]
  = [D, C, [A, object], [B, object]]
  = [D, C, A, [object], [B, object]]
  = [D, C, A, B, [object], [object]]
  = [D, C, A, B, object]

D -> C -> A -> B -> object

第二个代码块中输出 B 的原因

graph TD;
    A-->C;
    A-->B;
    C-->D;
    B-->D;
text
1
2
3
4
5
6
7
8
9
10
11
A = [A, object]
C = [C, A()] = [C, [A, object]] = [C, A, object]
B = [B, A()] = [B, [A, object]] = [B, A, object]
D = [D, C(), B()]
  = [D, [C, A, object], [B, A, object]]
  = [D, C, [A, object], [B, A, object]]
  = [D, C, B, [A, object], [A, object]]
  = [D, C, B, A, [object], [object]]
  = [D, C, B, A, object]

D -> C -> B -> A -> object

super 的使用

super([type, [type_or_object]])

  • 第一个参数决定了在 mro 链上从哪个 class 开始向后找
  • 第二个参数决定了这个函数 bind 到那个 object 上，同时决定使用哪个类的 mro

如果两个参数都不传，只能在 class 中使用，会隐式的做两件事

  • 寻找这个 super 是在哪个类里面定义的，将这个类当做第一个参数传入 super
  • 寻找这个 super 是在哪个函数中定义的，将函数的第一个参数作为 super 的第二个参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class User:
    def __init__(self, name):
        self.name = name

class Admin(User):
    def __init__(self, name, group):
        #--------------------------
        # 第一种写法
        super().__init__(name)
        # 第二种写法
        super(Admin, self).__init__(name)
        #--------------------------
        self.group = group

admin = Admin("name", "finance")
# 第三种写法，类外使用
super(Admin, admin).__init__("stolen")

证明两个参数含义的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class A:
    def show(self):
        print("A")

class B(A):
    def show(self):
        super().show()

class C(A):
    def show(self):
        print("C")

class D(B, C):
    def show(self):
        B.show(self)

d = D()
d.show() # C
graph TD;
    A-show-->B;
    A-show-->C-show;
    B-->D;
    C-show-->D;

说明：

  • D 的 mro 为 [D, B, C, A, object]
  • D 中 show 方法调用了 B 中的 show 方法，B 中的 show 方法使用了 super
  • 根据前面的知识，可以知道 B 中的 super 的两个参数分别是 B 和 self，但是 self 又是来自于 D
  • 最后的调用含义为用 D 的 mro 链中从 B 开始向后找，找到第一个是 C，所以最后的输出为 C

最后提醒

Python 的 MRO 从来没有使用过广度优先算法，只是很多情况下 C3 线性化的结果和广度优先算法的结果一致。

参考资料