# Python: 多继承模式下 MRO(Method Resolution Order) 的计算方式

```用 CN 表示一个类：C1, C2, C3, ..., CN
C1 C2 C3 ... CN 表示的是一个包含多个类的列表 [C1, C2, C3, ..., CN]
```

```head = C1
tail = C2 ... CN
```

```C + (C1 C2 ... CN) = C C1 C2 ... CN
[C] + [C1, C2, ... ,CN] = [C, C1, C2, ..., CN]
```

L[C] 表示类 C 的线性值，其实就是 C 的 MRO, 其中

```L[object] = object
```

```class C(B1, B2, ..., BN): pass
```

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

merge 的计算规则如下 [1]

1. take the head of the first list, i.e L[B1][0]; (取第一个列表的第一个元素)
2. 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. (如果这个元素是其他包含这个元素的列表的第一个元素或者其他列表都不包含这个元素，把它加到 C 的线性化值列表中，并从待计算的 merge 列表中删除这个元素，否则就从下个列表中取第一个元素进行比较， 如果这个元素满足条件的话就用它)
3. 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. (一直重复这个步骤，直到所有的类都被从 merge 列表中删除或者当出现无法找到符合规则的元素时。 当出现无法计算 merge 规则的情况时，Python 2.3 将拒绝创建类 C 同时抛出一个异常）

## 计算 MRO¶

```class B(object): pass

L[B] = L[B(object)]
= B + merge(L[object])
= B + L[object]
= B object

>>> B.mro()
[<class '__main__.B'>, <type 'object'>]
```

```class C(B): pass

L[C] = L[C(B)]
= C + merge(L[B])
= C + L[B]
= C B object     # 从上面已经知道了 L[B] = B object

>>> C.mro()
[<class '__main__.C'>, <class '__main__.B'>, <type 'object'>]
```

```>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(D,E): pass
>>> class A(B,C): pass
```

```L[O] = O = object
L[F] = L[F(O)] = F  O
L[E] = L[E(O)] = E  O
L[D] = L[D(O)] = D  O
```

L[C]:

```L[C] = L[C(D, F)]
= C + merge(L[D], L[F], DF)
# 从前面可知 L[D] 和 L[F] 的结果
= C +  merge(DO, FO, DF)
# 因为 D 是顺序第一个并且在几个包含 D 的 list 中是 head，
# 所以这一次取 D 同时从列表中删除 D
= C + D + merge(O, FO, F)
# 因为 O 虽然是顺序第一个但在其他 list (FO)中不是 head, 跳过,
# 改为检查第二个list FO
# F 是第二个 list 和其他 list 的 head,
# 取 F同时从列表中删除 F
= C + D + F + merge(O)
= C D F O

>>> C.mro()
[<class '__main__.C'>, <class '__main__.D'>, <class '__main__.F'>, <type 'object'>]
```

L[B]:

```L[B] = L[B(D, E)]
= B + merge(L[D], L[E], DE)
= B + merge(DO, EO, DE)
= B + D + merge(O, EO, E)
= B + D + E + merge(O)
= B D E O

>>> B.mro()
[<class '__main__.B'>, <class '__main__.D'>, <class '__main__.E'>, <type 'object'>]
```

L[A]:

```L[A] = L[A(B, C)]
= A + merge(L(B), L(C), BC)
= A + merge(BDEO, CDFO, BC)
= A + B + merge(DEO, CDFO, C)
# 所以改为从下一个 list CDFO 开始
= A + B + C + merge(DEO, DFO)
= A + B + C + D + merge(EO, FO)
= A + B + C  + D + E + merge(O, FO)
= A + B + C + D + E + F + merge(O)
= A B C D E F O

>>> A.mro()
[<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>,
<class '__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <type 'object'>]
```

```>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(E,D): pass
>>> class A(B,C): pass
```

```L[O] = O = object
L[F(O)] = F  O
L[E(O)] = E  O
L[D(O)] = D  O

L[C] = L[C(D, F)]
= C + merge(L[D], L[F], DF)
= C D F O

L[B] = L[B(E, D)]
= B + merge(L[E], L[D], ED)
= B + merge(EO, DO, ED)
= B + E + merge(O, DO, D)
= B + E + D + merge(O)
= B E D O
>>> B.mro()
[<class '__main__.B'>, <class '__main__.E'>, <class '__main__.D'>, <type 'object'>]

L[A] = L[A(B, C)]
= A + merge(L[B], L[C], BC)
= A + merge(BEDO, CDFO, BC)
= A + B + merge(EDO, CDFO, C)
= A + B + E + merge(DO, CDFO, C)
= A + B + E + C + merge(DO, DFO)
= A + B + E + C + D + merge(O, FO)
= A + B + E + C + D + F + merge(O)
= A B E C D F O
>>> A.mro()
[<class '__main__.A'>, <class '__main__.B'>, <class '__main__.E'>,
<class '__main__.C'>, <class '__main__.D'>, <class '__main__.F'>, <type 'object'>]
```