Python MRO C3

方法解析顺序 MRO
面向对象中有一个重要特性是继承,如果是单重继承,要调用一个方法,只要按照继承的顺序查找基类即可。但多重继承时,MRO算法的选择(即基类的搜索顺序)非常微妙。
Python先后有三种不同的MRO:经典方式、Python2.2 新式算法、Python2.3 新式算法(C3)。Python 3中只保留了最后一种,即C3算法。
经典方式: 非常简单,深度优先,按定义从左到右
例如:菱形继承结构,按经典方式,d类MRO为dbaca。缺点是如果c类重写了a类中得方法,c类的方法将不会被调用到。此问题即本地优先顺序问题
class a:pass
class b(a):pass
class c(a):pass
class d(b,c):pass

 

新式算法:还是经典方式,但出现重复的,只保留最后一个。上面的例子,MRO为 dbca。问题 单调性。
比如d继承b,c 且b在c的前面。如果f继承d,那么f的mro中也应该和d的一样b在c的前面。单调性即继承时要保持顺序。
现在e继承c,b 且c在b的前面。f继承d,e时,bc的顺序就没法决定了。无论怎样排都违反了单调性。
C3 算法:MRO是一个有序列表L,在类被创建时就计算出来。
L(Child(Base1,Base2)) = [ Child + merge( L(Base1) ,  L(Base2) ,  Base1Base2 )]
L(object) = [ object ]
L的性质:结果为列表,列表中至少有一个元素即自己。
+        : 添加到列表的末尾,即 [ A + B ] = [ A,B ]
merge: ① 如果列表空则结束,非空 读merge中第一个列表的表头,
               ② 查看该表头是否在 merge中所有列表的表尾中。
               ②–>③ 不在,则 放入 最终的L中,并从merge中的所有列表中删除,然后 回到①中
               ②–>④ 在,查看 当前列表是否是merge中的最后一个列表
               ④–>⑤ 不是 ,跳过当前列表,读merge中下一个列表的表头,然后 回到 ②中
               ④–>⑥ 是,异常。类定义失败。
表头: 列表的第一个元素
表尾: 列表中表头以外的元素集合(可以为空)
merge 简单的说即寻找合法表头(也就是不在表尾中的表头),如果所有表中都未找到合法表头则异常。
如(例2):
L(O)= O #  O为 object 简写,省略[]符号,即 [object]
L(E(O)) = E + merge( L(O) , O )
                      = E + merge( O , O )
                      = E + O  = EO
L ( F( O ) )     = FO
L ( D ( O ) )   = DO
L ( B ( D,E)  )  =  B + merge(  L(D) ,  L(E), DE )
                       = B + merge( DO,  EO, DE )  # 代入前面的结果,因为类的MRO是在类建立时计算出来的,所以 基类的MRO是已知的。
                       =  B + D + merge( O, EO , E )
                       =  B + D + E + merge( O , O )
                       =  BDEO
L ( C ( D,F ))   =  CDFO
L (  A( B,C ) )   =  A + merge( L(B),  L(C), BC )
                        =  A + merge( BDEO,   CDFO,  BC)
                        =  A + B + merge(  DEO, CDFO, C )  #  找到了合法表头B,回到第一个列表继续找, 第一个表头D不合法, 找第二个,第二个C合法
                        =  A + B + C + merge( DEO,   CDFO , C ) # 找到了合法表头C,回到第一个列表继续找
                        =  A + B + C + merge( DEO, DFO ) # 找到了合法表头D,回到第一个列表继续找
                        =  A + B + C + D + merge( EO, FO )
                        = ABCDEFO
问题: 没有异常情况下的C3算法 等效于 从左到右 的 广度优先 算法吗?
答案不是。
如(例3): O为所有类的基类,A为我们要计算MRO的类。A直接继承自B,C 。B继承D,D继承O。
    —  B — D —
A– – C  ——– O
整个继承树有四层,按继承关系,BC 在同一层,都是A的直接父类。
C3 结果为 ABDCO, 而广度为 ABCDO。
区别在于 ②–>③–>① 这里。
根据C3,一个类的MRO: 表头显然即是类自己,表尾为所有基类
第一次进行merge时,merge中的列表的表头显然都是A的直接父类,处于同一层次。
第一个列表的第二元素则是该列表表头的基类,根据与A的继承关系,显然和第二个列表的表头不在同一层次。
C3进行完第③步后,回到①继续读第一个列表的表头,没有读 同层次的,即第二个列表的表头。于是出现区别。
为什么 前面那个例子 这恰好 和 广度 优先 算法结果相同?
答案是 merge中的 另一个路径 ②–>④–>⑤。
这两条路径的区别即是C 的层次问题,也就是BC,CD的层次关系。
对A而言逻辑上BC处于同一层次,D是B的下一层,”看起来 D也应该是C的下一层。“
实际上不是,C3算法中C是B的下一个(A的直接父类,左右关系决定),同时D也是B的下一个(BD继承关系决定)。
在这种关系下,既然DC都是B的下一个,也就是DC处于同一层次,根据左右规则 显然 D前C后。
也就是 除非在另一个列表的辅助下明确D是C的下一层,如果 D不在C的表尾中,那么 D 不会比C的层次低。
如 (例4):  A(B,C,F) B(D) F(D)   MRO为 ABCFDO
A 添加了直接父类F,由于左右关系C在F的上一个,由于继承关系F在D的上一个。所以C在D的前面。
MRO 实际 就是 离散数学中的全序问题,在 继承关系中的 层次 由于 MRO中左右优先的规则而被改变(从A的父类角度)。
不过 ,如果 我们 从 O的子类来看 层次问题,如CD都是O的直接子类,而AB都不是直接子类。
这时,结果是对的,也就是 C3中的层次 是以 到O的最长步长为其所在的层次,同层次从左到右。
但 不管 从什么角度,在最终结果中 去掉左右顺序后的继承关系的顺序是确定的。
也就是离散数学中的偏序,通过左右的先后顺序,将偏序变成全序。
全序还可以换个说法是 存在一条路径遍历全部节点而不重复。
从动作上看就是捏住两端,拉直。(每个节点间绳子具有最大弹性,保证拉直,最小为两个节点多路径下的最大步长)
【2】参考:http://python3.blogspot.com/2010/07/method-resolution-order.html (该文参考python作者维护的python历史博客)