3-计算机科学1-理论计算机科学4-编程语言和编译器Python
Source
Edit
History

Python MRO

请注意：本文编写于 2021-07-25，其中某些信息可能已经失去时效性。

前言

注：本文中给出的所有案例结果都经过实际代码验证可放心食用。

什么是 MRO

方法解析顺序（Method Resolution Order MRO），指的是在多继承编程语言中查找类的某个方法来自哪个基类的搜索顺序。

Python MRO 历史

周期 类存在形式和对应算法
Python 2.1 经典类 -> DFS
Python 2.2 经典类 -> DFS | 新式类 -> BFS
Python 2.3-2.7 经典类 -> DFS | 新式类 -> C3
Python 3 新式类 -> C3

经典类和新式类

在 Python 2.1 及以前，定义一个类的形式如下：

1
2
3
class A:
def __init__(self):
    pass

在 Python 2.2 中引入了一种新的类的定义方式：

1
2
3
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 搜索流程

  1. 检查当前类是否有目标函数，如果有则直接调用，如果没有则进入下一步；
  2. 按照从左至右的方向将当前类的第一个父类赋值为当前类并重复步骤一，若前类无父类则进入下一步；
  3. 向上回溯一层并按照步骤二规定的方向将当前类的下一个父类赋值为当前类并重复步骤一，直至无法继续回溯；

案例分析

DFS 案例分析

参考 [DFS 搜索流程](#DFS 搜索流程)，搜索顺序为：A -> B -> D -> H -> E -> C -> F -> G

BFS 广度优先搜索

BFS 搜索流程

  1. 检查当前类是否有目标函数，如果有则直接调用，如果没有则进入下一步；
  2. 按照从左至右的方向依次检查当前类的一级父类是否有目标函数，如果有则直接调用，否则依旧按照当前方向检查当前类的下一级父类是否有目标函数直至检查完当前类的最高级父类；

BFS 案例分析

由于未能在本地下载 Python 2.2 因此无法验证复杂的案例，故这里给出网上反复论证过的案例。

BFS 案例分析

参考 [BFS 搜索流程](#BFS 广度优先搜索)，搜索顺序为：A -> B -> C -> D

为什么放弃 DFS 和 BFS

从 [Python MRO 历史](#Python MRO 历史) 可以看出无论是 DFS 还是 BFS 最终都被 C3 算法代替了，原因是 DFS 和 BFS 在处理复杂继承关系时会出现无法满足局部优先或单调性的问题。

局部优先

查找过程应该按照子类声明时给定的父类顺序进行查找（从左向右）。

单调性

在多继承关系中，假设类 C 的 MRO 结果给出类 A 排在类 B 前面，则在类 C 的所有子类中也需要满足同样的先后顺序；

参考案例

DFS 不满足单调性案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 之前。

BFS 不满足局部优先性案例

由于未能在本地部署 Python 2.2 环境，本案例取自 参考文章-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 之后。

疑惑

在了解了单调性和局部优先原则以及两个算法的反例之后我又产生了一个疑惑，为什么不满足单调性和局部优先的原则就无法使用，不满足这两个原则所带来的弊端有哪些？

经过简单的思考和搜索我并没有得出答案，以后如果有机会能够实际解除此类问题我会再回来补充。

C3 线性化算法

概念梳理

假设有类 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）：

  1. merge 会从左至右依次解析参数中的 list：
    1. 选取 list 中的头部，检查头部是否在 merge 参数中其他列表的尾部中里出现：
      1. 如果未出现，则将头部代表的类加入到类 C 的 MRO 中并将此头部代表的类从所有列表中删除，此后重复步骤 1.1；
      2. 如果出现，跳出对本 list 的检查重复步骤 1，直至 merge 中所有参数 list 都被检查完毕；
  2. 如果 merge 的所有参数列表都被清空，则输出 MRO，否则抛出异常。

注意几个点：

  1. 在步骤 1.1 中检查是否在其他列表的尾部中出现时也会检查公式中 [B1, B2, …, BN, o] 这一部分；
  2. MRO 也可以看做是一个 list，插入的时候采用的是尾部插入；

案例分析

BFS 和 DFS 失败案例演示

先来看一下前面给出的两个失败案例在 C3 算法下的输出结果：

DFS 失败案例在 C3 算法下的输出结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 方法执行流程时使用加粗的 [] 代表当前列表，使用被 代码块 包裹的类代表待检测类

  1. 根据公式：L[A] = [A] + merge(L[B], L[C], L[o], [B, C, o])
  2. L[B] = [B] + merge(L[D], L[o], [D, o])
  3. L[C] = [C] + merge(L[D], L[o], [D, o])
  4. L[D] = [D] + merge(L[o], [o]) = [D, o]
  5. 将 L[D] 结果反向带入后:
    1. L[B] = [B, D, o]
    2. L[C] = [C, D, o]
    3. L[A] = [A] + merge([B, D, o], [C, D, o], [o], [B, C, o])，根据 merge 方法执行流程：
      1. L[A] = [A] + merge([B, D, o], [C, D, o], [o], [B, C, o])
      2. L[A] = [A, B] + merge([D, o], [C, D, o], [o], [C, o])
      3. L[A] = [A, B] + merge([D, o], [C, D, o], [o], [C, o])
      4. L[A] = [A, B, C] + merge([D, o], [D, o], [o], [o])
      5. L[A] = [A, B, C, D] + merge([o], [o], [o], [o])
      6. L[A] = [A, B, C, D, o] + merge([], [], [], [])
BFS 失败案例在 C3 算法下的输出结果
1
2
3
4
5
6
7
8
9
10
11
12
13
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 方法执行流程时使用加粗的 [] 代表当前列表，使用被 代码块 包裹的类代表待检测类

  1. 根据公式：L[C] = [C] + merge(L[A], L[B], L[o], [A, B, o])
  2. L[A] = [A] + merge(L[o], [o]) = [A, o]
  3. L[B] = [B] + merge(L[A], L[o], [A, o])
  4. 将 L[A] 结果反向带入后:
    1. L[B] = [B, A, o]
    2. L[C] = [C] + merge([A, o], [B, A, o], L[o], [A, B, o])，根据 merge 方法执行流程：
      1. L[C] = [C] + merge([A, o], [B, A, o], [o], [A, B, o])
      2. L[C] = [C] + merge([A, o], [B, A, o], [o], [A, B, o])
      3. L[C] = [C] + merge([A, o], [B, A, o], [o], [A, B, o])
      4. L[C] = [C] + merge([A, o], [B, A, o], [o], [A, B, o])
      5. L[C] = [C] + merge([A, o], [B, A, o], L[o], [A, B, o])

直至 merge 检查完所有参数 list，仍然存在非空参数 list，因此 merge 抛出异常。

复杂案例演示

这里我们通过 维基百科 给出的复杂案例来进行展示：

注：由于案例过于复杂，这里就不展示源码了，只展示案例依赖图、最终结果和执行过程；

复杂案例展示

  1. 根据公式：L[Z] = [Z] + merge(L[K1], L[K3], L[K2], L[o], [K1, K3, K2, o])
  2. L[K1] = [K1] + merge(L[C], L[A], L[B], L[o], [C, A, B, o]) = [K1, C, A, B, o]
  3. L[K2] = [A] + merge(L[B], L[D], L[E], L[o], [B, D, E, o]) = [K2, B, D, E, o]
  4. L[K3] = [A] + merge(L[A], L[D], L[o], [A, D, o]) = [K3, A, D, o]
  5. L[A] = [A] + merge(L[o], [o]) = [A, o]
  6. L[B] = [B] + merge(L[o], [o]) = [B, o]
  7. L[C] = [C] + merge(L[o], [o]) = [C, o]
  8. L[D] = [D] + merge(L[o], [o]) = [D, o]
  9. L[E] = [E] + merge(L[o], [o]) = [E, o]
  10. 将结果反向带入得到 L[Z] = [Z] + merge([K1, C, A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K1, K3, K2, o])，根据 merge 方法执行流程：
    1. L[Z] = [Z] + merge([K1, C, A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K1, K3, K2, o])
    2. L[Z] = [Z, K1] + merge([C, A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])
    3. L[Z] = [Z, K1, C] + merge([A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])
    4. L[Z] = [Z, K1, C] + merge([A, B, o], [K3, A, D, o], [K2, B, D, E, o], [o], [K3, K2, o])
    5. L[Z] = [Z, K1, C, K3] + merge([A, B, o], [A, D, o], [K2, B, D, E, o], [o], [K2, o])
    6. L[Z] = [Z, K1, C, K3, A] + merge([B, o], [D, o], [K2, B, D, E, o], [o], [K2, o])
    7. L[Z] = [Z, K1, C, K3, A] + merge([B, o], [D, o], [K2, B, D, E, o], [o], [K2, o])
    8. L[Z] = [Z, K1, C, K3, A, K2] + merge([B, o], [D, o], [B, D, E, o], [o], [o])
    9. L[Z] = [Z, K1, C, K3, A, K2, B] + merge([o], [D, o], [D, E, o], [o], [o])
    10. L[Z] = [Z, K1, C, K3, A, K2, B, D] + merge([o], [o], [E, o], [o], [o])
    11. L[Z] = [Z, K1, C, K3, A, K2, B, D, E] + merge([o], [o], [o], [o], [o])
    12. L[Z] = [Z, K1, C, K3, A, K2, B, D, E, o] + merge([], [], [], [], [])

最终得到结果为：Z -> K1 -> C -> K3 -> A -> K2 -> B -> D -> E -> o

小技巧

小技巧展示

  1. 在多层级多继承关系中最高能够在第二层通过肉眼快速确定 MRO（本类 + 继承类顺序排列 + object）；
  2. 想要快速确定复杂多继承类的 MRO，应该从第二层开始向上层查找；

参考

  1. 艽野尘梦：Python 方法解析顺序 MRO
  2. JonPan：Python的多继承问题-MRO和C3算法
  3. YuanBao：C3 线性化算法与 MRO
  4. 三点水：C3 算法-Python 多继承的内部原理