Python进阶_方法解析顺序(MRO)

方法解析顺序(MRO)

参考https://hanjianwei.com/2013/07/25/python-mro/

对于支持继承的语言来说，一个对象的方法可能定义在当前类，也可能继承自基类。因此调用该方法的时候，就需要通过搜索确定该方法的位置，搜索的顺序就是方法解析顺序MRO（Method Resolution Order）。

二义性问题

Python支持多继承，因此会遇到MRO的二义性问题：

1. 倒三角继承，基类方法同名，同名二义性：基类A，B，派生类C继承自A和B。A和B都定义了方法a，那么调用C的方法a时，不能确定使用哪个基类的方法a。
2. 菱形继承，访问路径不唯一，路径二义性：基类A定义了方法a，基类B和基类C继承自基类A，派生类D继承自基类B和基类C。派生类D不能确定继承基类B还是基类C的方法a。

同名二义性	路径二义性

C++也支持多继承。对于问题1，采用了同名覆盖解决，也即在子类中定义同名方法，子类的方法或属性会被优先调用。如果要在子类中访问被屏蔽的基类成员，使用 <基类名>::<方法名>；对于问题2，采用了虚继承解决，以 virtual 修饰直接基类，从而不会产生多个祖父基类的副本；或者采用同名覆盖、作用域限定符（只能限定访问某个直接基类，访问祖父基类仍然存在二义性）。

简单来说，解决MRO的二义性就是将有向无环图变为线性结构，可用的有深度优先遍历、广度优先遍历、拓扑排序。而Python3采用了 C3_Linearization 算法。

经典类的MRO

Python2.2之前都为经典类（classic class），采用从左至右的深度优先遍历（DFS）作为MRO方法，重复类保留第一个。

# Python2.7 Shell
A.show()
>>> import inspect
>>> class A:
...     def show(self):
...             print "A.show()"
...
>>> class B(A): pass
...
>>> class C(A):
...     def show(self):
...             print "C.show()"
...
>>> class D(B, C): pass
...
>>> inspect.getmro(D)
(<class __main__.D at 0x0000000003AA70A8>, <class __main__.B at 0x0000000003A1B948>, <class __main__.A at 0x0000000003A1BD08>, <class __main__.C at 0x0000000003A1BD68>)
>>> x = D()
>>> x.show()
A.show()

可以发现，DFS产生的MRO为 [D, B, A, C]，也就是说，如果 C 中定义了更好的 show() 方法，作为 C 的直接子类的 D 永远无法访问到 C.show()。

经典类和新式类并存的MRO

Python2.2-2.7引入新式类（new-type class），所有类继承自 object。采用重复类保留最后一个的 DFS 或者说 广度优先遍历 BFS。经典类仍为 重复类保留第一个的 DFS。

# Python2.7 Shell
>>> import inspect
>>> class A(object):
...     def show(self):
...             print "A.show()"
...
>>> class B(A): pass
...
>>> class C(A):
...     def show(self):
...             print "C.show()"
...
>>> class D(B, C): pass
...
>>> inspect.getmro(D)
(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <type 'object'>)
>>> x = D()
>>> x.show()
C.show()

对于新式类来说，BFS产生的MRO为 [D, B, C, A, object]，解决了子类无法重写基类方法的问题。

但是会出现违反单调性原则的问题：

单调性原则：基类的搜索顺序在子类的搜索顺序中不发生改变。

除了单调性原则之外，Python 2.2 及经典类的 MRO 也可能违反继承的局部优先级。

>>> class X(object): pass
>>> class Y(object): pass
>>> class A(X, Y): pass
>>> class B(Y, X): pass
>>> class C(A, B): pass

对于 A：[A, X, Y, object]；

对于 B：[B, Y, X, object]；

对于 C：[C, A, B, X, Y, object]。（Python 2.2 在实现该方法的时候进行了调整，使其更尊重基类中类出现的顺序，原本 X 和 Y 应交换位置）

在 C 的MRO中，[... B, X, Y, object] 与 B 的MRO顺序相反。这样 C 继承自 B 后，在 B 的行为上发生了改变，容易导致不易察觉的问题。

C3的MRO

Python3之后，只存在新式类，不过不必显式继承 object，能够隐式继承 object。

C3算法解释如下：

将类 C 的 MRO 记为 L[C] = [C1, C2,…,CN]。其中 C1 称为 L[C] 的 Head，其余元素 [C2,…,CN] 称为 Tail。如果类 C 继承自基类 B1、B2、……、BN，那么可以根据以下两步迭代计算出 L[C]：

1. L[object] = [object]
2. L[C(B1…BN)] = [C] + merge(L[B1]…L[BN], [B1]…[BN])

这里的关键在于 merge，其输入是一组列表，按照如下方式输出一个列表：

1. 检查第一个列表的头元素（如 L[B1] 的头），记作 H。
2. 若 H 未出现在其它列表的尾部，则将其输出，并将其从所有列表中删除，然后回到步骤1；否则，取出下一个列表的头部记作 H，继续该步骤。
3. 重复上述步骤，直至输入列表为空或者不能再找出可以输出的元素。如果是前一种情况，则算法结束；如果是后一种情况，说明无法构建继承关系，Python 会抛出异常。

简单说来，就是考虑了基类顺序的拓扑排序。

# Python3.7 Shell
>> class D(object): pass
...
>>> class E(object): pass
...
>>> class F(object): pass
...
>>> class B(D, E): pass
...
>>> class C(D, F): pass
...
>>> class A(B, C): pass
...
>>> A.__mro__
(<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <class 'object'>)