Python 多继承(新式类) 的mro算法

转载自：http://www.cnblogs.com/panyinghua/p/3283831.html

mro即method resolution order，主要用于在多继承时判断调的属性的路径(来自于哪个类)。之前查看了很多资料，说mro是基于深度优先搜索算法的。但不完全正确在Python2.3之前是基于此算法，但从Python2.3起应用了新算法:C3算法。

为什么采用C3算法

C3算法最早被提出是用于Lisp的，应用在Python中是为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性的问题。

本地优先级：指声明时父类的顺序，比如C(A,B)，如果访问C类对象属性时，应该根据声明顺序，优先查找A类，然后再查找B类。

单调性：如果在C的解析顺序中，A排在B的前面，那么在C的所有子类里，也必须满足这个顺序。

在Python官网的The Python 2.3 Method Resolution Order中作者举了例子，说明这一情况。

代码段1：

F=type('Food', (), {remember2buy:'spam'})
E=type('Eggs', (F,), {remember2buy:'eggs'})
G=type('GoodFood', (F,E), {})

根据本地优先级在调用G类对象属性时应该优先查找F类，而在Python2.3之前的算法给出的顺序是G E F O，而在心得C3算法中通过阻止类层次不清晰的声明来解决这一问题，以上声明在C3算法中就是非法的。

C3算法

判断mro要先确定一个线性序列，然后查找路径由由序列中类的顺序决定。所以C3算法就是生成一个线性序列。

如果继承自一个基类:

class B(A)

这时B的mro序列为[B,A]

如果继承自多个基类

class B(A1,A2,A3 ...)

这时B的mro序列 mro(B) = [B] + merge(mro(A1), mro(A2), mro(A3) ..., [A1,A2,A3])

merge操作就是C3算法的核心。

遍历执行merge操作的序列，如果一个序列的第一个元素，在其他序列中也是第一个元素，或不在其他序列出现，则从所有执行merge操作序列中删除这个元素，合并到当前的mro中。

merge操作后的序列，继续执行merge操作，直到merge操作的序列为空。

如果merge操作的序列无法为空，则说明不合法。

代码段2：

class A(O):pass
class B(O):pass
class C(O):pass
class E(A,B):pass
class F(B,C):pass
class G(E,F):pass

A、B、C都继承至一个基类，所以mro序列依次为[A,O]、[B,O]、[C,O]

mro(E) = [E] + merge(mro(A), mro(B), [A,B])

= [E] + merge([A,O], [B,O], [A,B])

执行merge操作的序列为[A,O]、[B,O]、[A,B]

A是序列[A,O]中的第一个元素，在序列[B,O]中不出现，在序列[A,B]中也是第一个元素，所以从执行merge操作的序列([A,O]、[B,O]、[A,B])中删除A，合并到当前mro，[E]中。

mro(E) = [E,A] + merge([O], [B,O], [B])

再执行merge操作，O是序列[O]中的第一个元素，但O在序列[B,O]中出现并且不是其中第一个元素。继续查看[B,O]的第一个元素B，B满足条件，所以从执行merge操作的序列中删除B，合并到[E, A]中。

mro(E) = [E,A,B] + merge([O], [O])

= [E,A,B,O]

同理

mro(F) = [F] + merge(mro(B), mro(C), [B,C])

= [F] + merge([B,O], [C,O], [B,C])

= [F,B] + merge([O], [C,O], [C])

= [F,B,C] + merge([O], [O])

= [F,B,C,O]

mro(G) = [G] + merge(mro[E], mro[F], [E,F])

= [G] + merge([E,A,B,O], [F,B,C,O], [E,F])

= [G,E] + merge([A,B,O], [F,B,C,O], [F])

= [G,E,A] + merge([B,O], [F,B,C,O], [F])

= [G,E,A,F] + merge([B,O], [B,C,O])

= [G,E,A,F,B] + merge([O], [C,O])

= [G,E,A,F,B,C] + merge([O], [O])

= [G,E,A,F,B,C,O]

自己实现了一个mro算法

代码段3：

 1 from exceptions import Exception
 2  
 3 def c3_lineration(kls):
 4     if len(kls.__bases__) == 1:
 5         return [kls, kls.__base__]
 6     else:
 7         l = [c3_lineration(base) for base in kls.__bases__]
 8         l.append([base for base in kls.__bases__])
 9         return [kls] + merge(l)
10     
11 def merge(args):
12     if args:
13         for mro_list in args:
14             for class_type in mro_list:
15                 for comp_list in args:
16                     if class_type in comp_list[1:]:
17                         break
18                 else:
19                     next_merge_list = []
20                     for arg in args:
21                         if class_type in arg:
22                             arg.remove(class_type)
23                             if arg:
24                                 next_merge_list.append(arg)
25                         else:
26                             next_merge_list.append(arg)
27                     return [class_type] + merge(next_merge_list)
28         else:
29             raise Exception
30     else:
31         return []

merge

测试代码

代码段4：

class A(object):pass
class B(object):pass
class C(object):pass
class E(A,B):pass
class F(B,C):pass
class G(E,F):pass

if __name__ == "__main__": 
    print c3_lineration(G)

代码段4的输出如下：G E A F B C object.