Python 基础知识：Method Resolution Order (MRO) 和 super

2016-12-03

面向对象语言的一个重要特性就是继承。对于单继承而言，调用一个方法，只要按照继承的顺序搜索就可以；但对于多重继承而言，不同的搜索算法得到的结果不一样。这种方法（或属性）搜索的顺序就是所谓的方法解析顺序（Method Resolution Order, MRO）。

在 Python 2.2 采用的是深度优先、从左到右的搜索算法，而在 Python 2.2 之后（包括 Python 3）的采用的是C3算法。它们的区别可见于下图：
图片来源

局部优先和单调性

之所以在 Python 2.2 之后采用C3算法，是因为 Python 2.2 经典类和新式类都可能出现违反局部优先（Local Precedence Ordering）和单调性（Monotonic）的规则。详细可参见Python 官方文档。

对于局部优先规则，Python 官方文档并没有明确定义，不过可总结为：搜索父类时，应该按照声明时的顺序进行搜索，如声明类 C(A, B)，那在搜索类 C 的父类时，先搜索 A，再搜索 B。而对于单调性，在该文档中，Michele Simionato 有明确定义：

A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C. Otherwise, the innocuous operation of deriving a new class could change the resolution order of methods, potentially introducing very subtle bugs.

也即，如果在 C 的搜索顺序（Linearization，实际就是 MRO）中，C1 排在 C2 的前边，那么，对于 C 的任何子类，它们的搜索顺序也必须满足 C1 排在 C2 的前边。

C3 算法

这部分主要参考自 Python 官方文档。

一些定义

类列表

1	C1 C2 ... CN 表示类列表 [C1 C2 ... CN]

列表头部和尾部

1 2	head = C1 tail = C2 ... CN

列表加法

1	C + (C1 C2 ... CN) = C C1 C2 ... CN

MRO 表示

1	L(C) 表示类 C 的搜索顺序（即 Linearization）

C3 算法

C3 算法很简单：

the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

用公式来表达就是：

L[C(B1 … BN)] = C + merge(L[B1] … L[BN], B1 … BN)

特别地，

L[object] = object.

具体的算法步骤如下：

take the head of the first list, i.e L[B1][0]; if this head is not in the tail of any of the other lists, then add it to the linearization of C and remove it from the lists in the merge, otherwise look at the head of the next list and take it, if it is a good head. Then repeat the operation until all the class are removed or it is impossible to find good heads. In this case, it is impossible to construct the merge, Python 2.3 will refuse to create the class C and will raise an exception.

需要注意一下 good head 和 bad head 的定义：当一个列表的 head 不在其他列表的 tail，则称该 head 为 good head，反之为 bad head。

步骤拆分如下：

取第一个列表 L[B1] 的 head（L[B1][0]），如果它不在其他列表（L[B2], …, B1 … BN）的 tail（即为 good head），那就把这个 head 加入到类 C 的搜索顺序中，并移除其它列表与该 head 一样的 head
如果第一个列表查找不到 good head，则从第二个列表查找 good head，并移除其它列表的与该 head 一样的 head，以此类推
循环查找，直到所有列表都被清空
如果遇到无法合并（merge）的情况（即找不到 good head，而所有列表还没清空），Python 2.3 会不允许创建类 C 和抛出异常

样例

成功

我们改造一个官方文档的例子如下：

class F(object):
    pass

class E(object):
    pass

class D(object):
    pass

class C(D, F):
    pass

class B(D, E):
    pass

class A(B, C):
    pass

print 'MRO of every class:'
print 'class F: %s' % str(F.__mro__)
print 'class E: %s' % str(E.__mro__)
print 'class D: %s' % str(D.__mro__)
print 'class C: %s' % str(C.__mro__)
print 'class B: %s' % str(B.__mro__)
print 'class A: %s' % str(A.__mro__)
# outputs
# MRO of every class:
# class F: (<class '__main__.F'>, <type 'object'>)
# class E: (<class '__main__.E'>, <type 'object'>)
# class D: (<class '__main__.D'>, <type 'object'>)
# class C: (<class '__main__.C'>, <class '__main__.D'>, <class '__main__.F'>, <type 'object'>)
# class B: (<class '__main__.B'>, <class '__main__.D'>, <class '__main__.E'>, <type 'object'>)
# class A: (<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <type 'object'>)

现在我们来看一下如何结算得到 L(A)：

L(F) = FO
L(E) = EO
L(D) = EO
L(C) = C + merge(L(D), L(F), DF) = C + merge(DO, FO, DF) = CD + merge(O, FO, F) = CDF + merge(O, O, ) = CDFO
L(B) = BDEO
L(A) = A + merge(L(B), L(C), BC) = A + merge(BDEO, CDFO, BC) = AB + merge(DEO, CDFO, C) = ABC + merge(DEO, DFO, ) 
     = ABCD + merge(EO, FO, ) = ABCDE + merge(O, FO, ) = ABCDEF + merge(O, O, ) = ABCDEFO

失败

一个典型的例子如下：

class F(object):
    pass

class E(object):
    pass

class D(E, F):
    pass

class C(F, E):
    pass

class B(C, D):
    pass

# outputs:
# Traceback (most recent call last):
#   File "D:/TestProjects/PyProjects/Test/mro.py", line 41, in <module>
#     class B(C, D):
# TypeError: Error when calling the metaclass bases
#     Cannot create a consistent method resolution
# order (MRO) for bases E, F

对类 B，

1	L(B) = B + merge(L(C), L(D), CD) = B + merge(CFEO, DEFO, CD) = BC + merge(FEO, DEFO, D) = BCD + merge(FEO, EFO, ) = ?

到这一步，已经找不到 good head，所以合并失败，无法创建类 B，并抛出异常。

super

super 是 Python 中出现概率很大的一个关键词，不过一般我们都用其指代父类，从而调用父类的方法或属性，不过 super 真的就是指代父类？且看下边一篇转载的博文理解 Python super：

今天在知乎回答了一个问题，居然一个赞都没有，也是神奇，毕竟这算是我非常认真答的题之一。既然如此就贴过来好了，有些内容之后再补充。

原问题

Python中既然可以直接通过父类名调用父类方法为什么还会存在super函数？
比如

1
2
3

class Child(Parent):
	def __init__(self):
		Parent.__init__(self)

这种方式与super(Child, self).init()有区别么？

回答
针对你的问题，答案是可以，并没有区别。但是这题下的回答我感觉都不够好。

要谈论 super，首先我们应该无视 “super” 这个名字带给我们的干扰。

不要一说到 super 就想到父类！super 指的是 MRO 中的下一个类！
不要一说到 super 就想到父类！super 指的是 MRO 中的下一个类！
不要一说到 super 就想到父类！super 指的是 MRO 中的下一个类！

一说到 super 就想到父类这是初学者很容易犯的一个错误，也是我当年犯的错误。忘记了这件事之后，再去看这篇文章：Python’s super() considered super! 这是 Raymond Hettinger 写的一篇文章，也是全世界公认的对 super 讲解最透彻的一篇文章，凡是讨论 super 都一定会提到它（当然还有一篇 Python’s Super Considered Harmful）。

如果不想看长篇大论就去看这个答案，super 其实干的是这件事：

1
2
3

def super(cls, inst):
    mro = inst.__class__.mro()
    return mro[mro.index(cls) + 1]

两个参数 cls 和 inst 分别做了两件事：

inst 负责生成 MRO 的 list
通过 cls 定位当前 MRO 中的 index, 并返回 mro[index + 1]

这两件事才是 super 的实质，一定要记住！

MRO 全称 Method Resolution Order，它代表了类继承的顺序。后面详细说。

举个例子

class Root(object):
    def __init__(self):
        print("this is Root")

class B(Root):
    def __init__(self):
        print("enter B")
        # print(self)  # this will print <__main__.D object at 0x...>
        super(B, self).__init__()
        print("leave B")

class C(Root):
    def __init__(self):
        print("enter C")
        super(C, self).__init__()
        print("leave C")

class D(B, C):
    pass

d = D()
print(d.__class__.__mro__)

输出

enter B
enter C
this is Root
leave C
leave B
(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.Root'>, <type 'object'>)

知道了 super 和父类其实没有实质关联之后，我们就不难理解为什么 enter B 下一句是 enter C 而不是 this is Root（如果认为 super 代表“调用父类的方法”，会想当然的认为下一句应该是 this is Root）。流程如下，在 B 的 __init__ 函数中：

1	super(B, self).__init__()

首先，我们获取 self.__class__.__mro__，注意这里的 self 是 D 的 instance 而不是 B 的

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

然后，通过 B 来定位 MRO 中的 index，并找到下一个。显然 B 的下一个是 C。于是，我们调用 C 的 __init__，打出 enter C。

顺便说一句为什么 B 的 __init__ 会被调用：因为 D 没有定义 __init__，所以会在 MRO 中找下一个类，去查看它有没有定义 __init__，也就是去调用 B 的 __init__。

其实这一切逻辑还是很清晰的，关键是理解 super 到底做了什么。

于是，MRO 中类的顺序到底是怎么排的呢？Python’s super() considered super!中已经有很好的解释，我翻译一下：

在 MRO 中，基类永远出现在派生类后面，如果有多个基类，基类的相对顺序保持不变。

关于 MRO 的官方文档参见：The Python 2.3 Method Resolution Order，有一些关于 MRO 顺序的理论上的解释。

最后的最后，提醒大家. 什么 super 啊，MRO 啊，都是针对 new-style class。如果不是 new-style class，就老老实实用父类的类名去调用函数吧。