Python 多重繼承 mro

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中作者舉了例子，說明這一情況。

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操作的序列無法為空，則說明不合法。

例子： 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算法 from exceptions import Exception

def c3_lineration(kls):     if len(kls.__bases__) == 1:         return [kls, kls.__base__]     else:         l = [c3_lineration(base) for base in kls.__bases__]         l.append([base for base in kls.__bases__])         return [kls] + merge(l)      def merge(args):     if args:         for mro_list in args:             for class_type in mro_list:                 for comp_list in args:                     if class_type in comp_list[1:]:                         break                 else:                     next_merge_list = []                     for arg in args:                         if class_type in arg:                             arg.remove(class_type)                             if arg:                                 next_merge_list.append(arg)                         else:                             next_merge_list.append(arg)                     return [class_type] + merge(next_merge_list)         else:             raise Exception     else:         return []

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

print c3_lineration(G)