对于支持继承的编程语言来说，其方法和属性可能定义在当前类，也可能来自基类，所以在方法调用时就需要对当前类和基类进行搜索以确定方法的位置。搜索的顺序，就是方法解析顺序 (Method Resolution Order, MRO)。对于只支持单继承的语言来说，MRO 比较简单；但对于Python这种支持多继承的语言来说，MRO 会相对复杂。

Python 的类

Python 有两种类：

  • 经典类
    • python 2.1 之前，经典类是唯一可用的形式
  • 新式类
    • python2.2 引入
    • python3 只支持新式类
    • 新式类继承自 object

Python 的 MRO

从一个例子入手：

如图，有如下继承关系：

继承

c 是 CBase 的一个实例，那么 c.pprint() 到底会调用哪个 pprint 方法呢？如果按照 [CBase, BBase, Base, ABase] 的搜索顺序，那么实际上调用的是 Base 的方法；如果按照 [CBase, BBase, ABase, Base] 的顺序，那么最终调用的是 ABase 的方法。

由此可见，MRO 是把类的继承关系线性化的一个过程，而线性化方式决定了程序运行过程中具体会调用哪个方法。既然如此，那什么样的 MRO 才是最合理的？Python 中又是如何实现的呢？

我们把上面的集成关系翻译为实际的 Python Code(Python3 环境)


class Base(object):
    def pprint(self):
        print('Base')

class ABase(Base):
    def pprint(self):
        print('ABase')

class BBase(Base):
    pass

class CBase(BBase, ABase):
    pass

然后我们执行: CBase.__mro__ 会得到如下结果

(__main__.CBase, __main__.BBase, __main__.ABase, __main__.Base, object)

我们由此猜测，Python实际可能使用的是 广度优先的搜索顺序。真实情况究竟是怎样的呢？

Python 中的 MRO

实际上，Python 至少有三种 MRO：

  • 经典类的深度优先搜索(DFS)，从左到右
  • Python2.2 的新式类的广度优先搜索(BFS)，从左到右
  • Python2.3 的新式类 C3 算法，Python3 仅支持 C3

由此提出两个问题：

  • 为什么新式类放弃了 DFS ？
  • 为什么新式类又放弃了 BFS ?

Python2.3 引入了 C3 算法作为新式类的MRO，原因是 Python2.2 之前新式类的 BFS，经典类的 DFS，都不是满足局部优先顺序、单调性 的 MRO 算法。

介绍一下局部优先顺序 和 单调性 的概念：

  • 局部优先顺序：查找子类对象属性时，应该依照声明子类时的父类顺序进行查找。
  • 单调性：如果在类C的 MRO 顺序中，类A排在类B前面，那么在C的所有子类中，也必须满足这个顺序。

先看下经典类 的 DFS ：

# Python2 中经典类：
import inspect

class A:
    pass
class B(A):
    pass
class C(A):
    pass
class D(B, C):
    pass

print inspect.getmro(A)
print inspect.getmro(B)
print inspect.getmro(C)
print inspect.getmro(D)

输出结果为

(<class __main__.A at 0x110f8d4c8>,)
(<class __main__.B at 0x110f8d460>, <class __main__.A at 0x110f8d4c8>)
(<class __main__.C at 0x110f8d530>, <class __main__.A at 0x110f8d4c8>)
(<class __main__.D at 0x110f8d598>, <class __main__.B at 0x110f8d460>, <class __main__.A at 0x110f8d4c8>, <class __main__.C at 0x110f8d530>)

D->B->A->C, 很明显是深度遍历，我们看到，在 D 的mro序列中，A 出现在了 C 的前面，而 在 C 的mro 序列中，C 是在 A 前面的，这就违背了单调性。

在看下 Python2.3 之后里的新式类，也就是 C3 算法：

class A(object):
    pass

class B(A):
    pass
class C(A):
    pass
class D(B, C):
    pass

print D.__mro__

输入结果为

(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <type 'object'>)

从结果可以分析出，单调性，局部优先性都是没有问题的。

再看 Python2.2 的新式类的BFS：

class A(object): pass
class B(A): pass
class C(A, B): pass

print A.__mro__
print B.__mro__
print C.__mro__

Python2.2 可以正常运行，运行结果如下：


(<class '__main__.A'>, <type 'object'>)
(<class '__main__.B'>, <class '__main__.A'>, <type 'object'>)
(<class '__main__.C'>, <class '__main__.B'>, <class '__main__.A'>, <type 'object'>)

根据局部优先级，在调用C类对象属性时，应该优先查找A类，而在结果中我们看到，在 类C 的 mro 顺序中 B 出现在了 A 前面，Python2.2 的 BFS 违背了C 的局部优先顺序。

Python2.3 及以后的版本都会报错，通过阻止类层次不清晰的声明来解决这一问题：

TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases B, A

C3 算法实际上是在拓扑排序的基础上考虑了基类出现的顺序，从而保证了单调性和局部优先顺序。

参考资料