跳转至

4.2.多重继承和MRO

Windows 10
Python 3.7.3 @ MSC v.1915 64 bit (AMD64)
Latest build date 2020.06.26

在使用多重继承的语言中，查找方法时搜索基类的顺序通常称为方法解析顺序（Method Resolution Order, MRO）。MRO定义了多个继承存在时，Python 解释器查找函数解析的具体顺序。

对于只支持单继承的语言来说，MRO 是无趣的; 但是当多重继承开始使用时，MRO 算法的选择可能是非常微妙的。Python 至少有三种不同的 MRO 算法: classic、Python 2.2 new-style 和 Python 2.3 new-style (又名 C3)。在 Python 3中，只有C3算法幸存下来。

classic MCO

什么是函数解析顺序？我们首先用一个简单的例子来说明：

# example 1
class A:
    def save(self):
        pass

class B(A):
    pass

class C:
    def save(self):
        pass

class D(B, C):
    pass

D().save()

Python多重继承1

Python 2.1 及之前，old-style class 使用一个简单的 MRO 方案：在查找方法时，使用一个简单的深度优先的从左到右方案搜索基类，将返回在此搜索过程中找到的第一个匹配对象。该种MRO方案可以被称为classic。这个过程具体如下：

  1. 检查当前的类里面是否有该函数，如果有则直接调用。
  2. 检查当前类的第一个父类里面是否有该函数，如果没有则检查父类的第一个父类是否有该函数，以此递归深度遍历。
  3. 如果没有则回溯一层，检查下一个父类里面是否有该函数并按照 2 中的方式递归。

步骤 2 总是按照继承列表中类的先后顺序来选择分支的遍历顺序。

因此，如果是old-style class，那么save方法的搜索顺序如下：

D B A C

所以，D().save()会调用A的save方法。

old-style class 的MRO方案在简单的情况下运行良好，但如果是diamond inheritance（菱形继承），问题就会出现。

# example 2
class A:
    def save(self):
        pass

class B(A):
    pass

class C(A):
    def save(self):
        pass

class D(B, C):
    pass

D().save()

Python菱形继承

按照深度优先的MRO方案，save方法的搜索顺序如下：

D B A C A

因此，D().save()还是会调用A的save方法。然而，这可能不是你想要的结果。既然 B 和 C 都继承自 A，为什么D不调用直接基类C的save方法呢？可以说重新定义的方法 C.save ()是更可能想要调用的方法，因为 C.save ()可以看成是比A.save ()更具体化的方法。

MRO for Python 2.2 new-style class

尽管这种类型的多重继承在Python2的代码中很少见，但是new-style class的出现将使它变得司空见惯。 这是因为所有新式类都是通过继承object对象来定义的。 因此，在任何新式类中使用多重继承都会创建上面描述的菱形关系。 例如:

# example 3
class B(object):
    pass

class C(object):
    def __setattr__(self, name, value):
        pass

class D(B, C):
    pass

Python菱形继承2

因此，如果基类对象重定义了魔术方法（如上例中的__setattr__()），解析顺序就会变得至关重要。在上面的代码中，方法 c.__setattr__()应该被类 D 继承。

为了修正 Python 2.2 中新样式类的方法解析顺序，Guido van Rossum 采用了一个新的MRO方案，

  1. 首先按照 old-style class 的MRO方案预先计算：

D B O C O

  1. 如果前面的类在后面也出现了，则删除前面重复的类，得到最终的搜索顺序：

D B C O

实际上，Python 2.2 的new-style class的MRO算法比这还要复杂一些，因为有些情况，使用上面简单的MRO算法并不起作用，例如下面的情况：

# example 4
class A(object): pass
class B(object): pass
class X(A, B): pass
class Y(B, A): pass
class Z(X, Y): pass

Python多重继承2

如果使用简单的MRO算法，结果是这样的：

result of the first step:  Z X A B O Y B A O
            final result:  Z X Y B A O

Guido van Rossum不喜欢 B 和 A 的顺序颠倒。 因此，真正的 new-style class MRO 保持搜索过程中最先出现的基类的顺序，所以最终结果是这样的：

Z X Y A B O

这是Guido van Rossum为 Python 2.2 new-style class 实现的MRO。

C3 for Python 2.3 +

然而，在 Python 2.2 中引入新式类之后不久，Samuele Pedroni 发现文档中的 MRO 算法与实际在实际代码中观察到的结果不一致。 此外，即使在不属于上述特殊情况的代码中也会出现不一致的情况。经过大量讨论，他们决定放弃 Python 2.2 采用的 MRO，让 Python2.3 及之后的版本使用C3 Linearization algorithm（A Monotonic Superclass Linearization for Dylan, K. Barrett, et al, presented at OOPSLA'96）。

在介绍C3算法之前，我们首先约定需要使用的符号。我们用 $C_{1}C_{2} \cdots C_{N}$表示包含 N 个类的列表，并令

$$ \begin{array}{c}\operatorname{head}\left(C_{1} C_{2} \cdots C_{N}\right)=C_{1} \ \operatorname{tail}\left(C_{1} C_{2} \cdots C_{N}\right)=C_{2} C_{3} \cdots C_{N}\end{array} $$

为了方便做列表连接操作，我们记：

$$ C_{1}+\left(C_{2} C_{3} \cdots C_{N}\right)=C_{1} C_{2} \cdots C_{N} $$

假设类 $C$ 继承自父类 $B_{1}, \cdots, B_{N}$，那么根据 C3 线性化，类 $C$ 的方法解析列表通过如下公式确定：

$$ L[C(B_{1} \cdots B_{N})] = C + merge(L[B_{1}], \cdots, L[B_{N}], B_{1} \cdots B_{N}) $$

这个公式表明 $C$ 的解析列表是通过对其所有父类的解析列表及其父类一起做 merge 操作所得到。

merge是 C3 线性化中最重要的操作，该操作可以分为以下几个步骤：

  1. 选取 merge中的第一个列表记为当前列表 $K$。
  2. 令 $h = head(K)$，如果 $h$ 没有出现在其他任何列表的 $\text{tail}$ 当中，那么将其加入到类 $C$ 的线性化列表中，并将其从 merge 中所有列表中移除，之后重复步骤 2。
  3. 否则，设置 $K$ 为 merge 中的下一个列表，并重复 2 中的操作。
  4. 如果 merge中所有的类都被移除，则输出类创建成功；如果不能找到下一个 $h$，则输出拒绝创建类 $C$ 并抛出异常。

使用 example 4 的例子来执行C3算法：

class A(object): pass
class B(object): pass
class X(A, B): pass
class Y(B, A): pass
class Z(X, Y): pass

Python多重继承2

首先我们有：

$$ L[A] = [A, O] \tag{1} $$

$$ L[B] = [B, O] \tag{2} $$

根据(1)和(2)，有：

$$ \begin{aligned} L[X] &= X + merge\left[ L[A], L[B], A, B \right] \\ &= X + [[A, O], [B,O], A, B] \\ &= [X, A] + [[O], [B,O], B] \\ &= [X, A, B] + [[O], [O]] \\ &= [X, A, B, O] + [ ] \\ &= [X, A, B, O] \end{aligned} \tag{3} $$

同理可得：

$$ L[Y] = [Y, B, A, O] \tag{4} $$

根据(3)和(4)，有：

$$ \begin{aligned} L[Z] &= Z + merge\left[ L[X], L[Y], X, Y \right] \\ &= Z + [[X, A, B, O], [Y, B,A, O], X, Y] \\ &= [Z,X] + [[A, B, O], [Y, B,A, O], Y] \\ &= [Z,X,Y] + [[A, B, O], [B,A, O]] \end{aligned} \tag{5} $$

最后产生冲突，Python会抛出TypeError异常。