请注意:本文编写于 2021-07-25,其中某些信息可能已经失去时效性。
注:本文中给出的所有案例结果都经过实际代码验证可放心食用。
方法解析顺序(Method Resolution Order MRO),指的是在多继承编程语言中查找类的某个方法来自哪个基类的搜索顺序。
周期 | 类存在形式和对应算法 |
---|---|
Python 2.1 | 经典类 -> DFS |
Python 2.2 | 经典类 -> DFS | 新式类 -> BFS |
Python 2.3-2.7 | 经典类 -> DFS | 新式类 -> C3 |
Python 3 | 新式类 -> C3 |
在 Python 2.1 及以前,定义一个类的形式如下:
class A:
def __init__(self):
pass
在 Python 2.2 中引入了一种新的类的定义方式:
class A(object):
def __init__(self):
pass
为了保持向上兼容,Python 2.2 及以后的版本同时保留这两种定义方式而两种方式产生的类及其实例具有不同的特性,为了区分两种定义方式将 Python 2.1 及以前版本的书写方式产生的类称为经典类(Old-style Class)将 Python 2.2 及以后版本的书写方式产生的类称为新式类(New-style Class)。
伴随着 Python3 的推出经典类已经被完全废弃,因为在 Python3 中无论以何种方式定义产生的都是新式类。
参考 [DFS 搜索流程](#DFS 搜索流程),搜索顺序为:A -> B -> D -> H -> E -> C -> F -> G
由于未能在本地下载 Python 2.2 因此无法验证复杂的案例,故这里给出网上反复论证过的案例。
参考 [BFS 搜索流程](#BFS 广度优先搜索),搜索顺序为:A -> B -> C -> D
从 [Python MRO 历史](#Python MRO 历史) 可以看出无论是 DFS 还是 BFS 最终都被 C3 算法代替了,原因是 DFS 和 BFS 在处理复杂继承关系时会出现无法满足局部优先或单调性的问题。
查找过程应该按照子类声明时给定的父类顺序进行查找(从左向右)。
在多继承关系中,假设类 C 的 MRO 结果给出类 A 排在类 B 前面,则在类 C 的所有子类中也需要满足同样的先后顺序;
import inspect
class D:
pass
class B(D):
pass
class C(D):
pass
class A(B, C):
pass
print(inspect.getmro(A))
# 以下是结果(被我按行分割了)
# <class __main__.A at 0x10719d3d0>
# <class __main__.B at 0x10717fd00>
# <class __main__.D at 0x10717fc20>
# <class __main__.C at 0x10719d130>
print(inspect.getmro(B))
# <class __main__.B at 0x10717fd00>
# <class __main__.D at 0x10717fc20>
print(inspect.getmro(C))
# <class __main__.C at 0x10719d130>
# <class __main__.D at 0x10717fc20>
从结果来看,在类 C 的 MRO 中类 D 在类 C 之后,而在类 A 的 MRO 中类 D 在类 C 之前。
由于未能在本地部署 Python 2.2 环境,本案例取自 参考文章-1。
class A(object): pass
class B(A): pass
class C(A, B): pass
print A.__mro__
# <class '__main__.A'>, <type 'object'>
print B.__mro__
# <class '__main__.B'>
# <class '__main__.A'>, <type 'object'>
print C.__mro__
# <class '__main__.C'>
# <class '__main__.B'>
# <class '__main__.A'>
# <type 'object'>
从结果来看,类 C 的 MRO 类 B 在类 A 之前,而在类 C 的声明中类 B 在类 A 之后。
在了解了单调性和局部优先原则以及两个算法的反例之后我又产生了一个疑惑,为什么不满足单调性和局部优先的原则就无法使用,不满足这两个原则所带来的弊端有哪些?
经过简单的思考和搜索我并没有得出答案,以后如果有机会能够实际解除此类问题我会再回来补充。
假设有类 C 继承自类 B1 到 类 BN,则记类 C 的 MRO 为 L[C](L 代表 linearization,线性化),假设 L[C] 最终的结果是一个特殊的 Python list;
对于 L[C] = [B1, B2, B3, … BN],设 [B1] 为 L[C] 的头部,[B2, B3, …, BN] 为 L[C] 的尾部;
所有类都会继承 object,且 L[object] = object, 以下 object 简写为 o;
定义 L[C(B1, B2, …, BN)] = [C] + merge(L[B1], L[B2], …, L[BN], L[o], [B1, B2, …, BN, o])
通过定义可知,整个搜索流程即是 merge 方法运算的流程(假设被搜索的被是类 C):
注意几个点:
先来看一下前面给出的两个失败案例在 C3 算法下的输出结果:
class D:
pass
class B(D):
pass
class C(D):
pass
class A(B, C):
pass
print(A.__mro__)
# <class '__main__.A'>
# <class '__main__.B'>
# <class '__main__.C'>
# <class '__main__.D'> <class 'object'>
print(B.__mro__)
# <class '__main__.B'>
# <class '__main__.D'>, <class 'object'>
print(C.__mro__)
# <class '__main__.C'>
# <class '__main__.D'>, <class 'object'>
C3 执行结果: A: A -> B -> C -> D -> o B: B -> D -> o C: C -> D -> o
DFS 执行结果: A: A -> B -> D -> C B: B -> D C: C -> D
从结果对比来看 C3 算法输出的结果解决了 DFS 算法在此案例中无法满足单调性原则的问题。
下面我们来看一下 C3 算法是如何输出这样的结果的,重点看类 A 的 MRO 生成过程:
注:在展示 merge 方法执行流程时使用加粗的 [] 代表当前列表,使用被 代码块
包裹的类代表待检测类
B
, D, o], [C, D, o], [o], [B, C, o])D
, o], [C, D, o], [o], [C, o])C
, D, o], [o], [C, o])D
, o], [o], [o])o
], [o], [o])class A: pass
class B(A): pass
class C(A, B): pass
print(A.__mro__)
print(B.__mro__)
print(C.__mro__)
# Traceback (most recent call last):
# File "test.py", line 3, in <module>
# class C(A, B): pass
# TypeError: Cannot create a consistent method resolution
# order (MRO) for bases A, B
从结果来看,C3 算法最终会通过引起异常来维护局部优先原则。
下面我们来看一下 C3 算法是如何输出这样的结果的,重点看类 C 的 MRO 生成过程:
注:在展示 merge 方法执行流程时使用加粗的 [] 代表当前列表,使用被 代码块
包裹的类代表待检测类
A
, o], [B, A, o], [o], [A, B, o])B
, A, o], [o], [A, B, o])o
], [A, B, o])A
, B, o])直至 merge 检查完所有参数 list,仍然存在非空参数 list,因此 merge 抛出异常。
这里我们通过 维基百科 给出的复杂案例来进行展示:
注:由于案例过于复杂,这里就不展示源码了,只展示案例依赖图、最终结果和执行过程;
K1
, C, A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K1, K3, K2, o])C
, A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])A
, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])K3
, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])A
, D, o], [K2, B, D, E, o], [o], [K2, o])D
, o], [K2, B, D, E, o], [o], [K2, o])K2
, B, D, E, o], [o], [K2, o])B
, D, E, o], [o], [o])D
, E, o], [o], [o])E
, o], [o], [o])o
], [o], [o])最终得到结果为:Z -> K1 -> C -> K3 -> A -> K2 -> B -> D -> E -> o