iT邦幫忙

2024 iThome 鐵人賽

DAY 25
0
Python

為你自己讀 CPython 原始碼系列 第 25

Day 25 - 類別繼承與家族紛爭(中)

  • 分享至 

  • xImage
  •  

本文同步刊載於 「為你自己學 Python - 類別繼承與家族紛爭(中))

類別繼承與家族紛爭(中)

為你自己學 Python

這個章節我們先稍微喘口氣,暫時不看 CPython 的原始碼,先來看看 Python 的多重繼承是怎麼計算方法的查找順序,或是如果遇到上層多個類別都有實作同一個方法的時候,該聽誰的。

C3 線性演算法

關於 Python 採用 C3 線性演算法,我借用維基百科的一段話:

Python 創始人 Guido van Rossum 這樣總結C3超類線性化:「基本上,在 C3 背後的想法是,如果你寫下在複雜的類層級中繼承關系所施加的所有次序規則,這個演算法將確定出滿足所有這些規則的這些類的一個單調次序。如果不能確定出這樣的次序,這個演算法會失敗。」

這裡的重點在於「單調次序(Monotonicity)」,也就是說不管在簡單或複雜的繼承關係裡,C3 線性演算法都會試著計算並找出一個合理的次序,如果能計算的出來,那將會每次都是一樣的結果。

該聽誰的?

我們先來看一段程式碼:

class A:
    def greeting(self):
        print("Hey in A")

class B(A):
    def greeting(self):
        print("Hey in B")

class C(A):
    def greeting(self):
        print("Hey in C")

class D(B, C):
    pass

d = D()
d.greeting()

這是個還算單純的多重繼承結構,類別 D 同時有兩個上層類別,那麼當呼叫 d.greeting() 的時候,該聽誰的?這個狀況比較簡單,因為類別 D 的上一層就是類別 B,而類別 B 有自己的 greeting 方法,所以會呼叫類別 Bgreeting 方法。嗯...但為什麼是 B 而不是 C,這兩個不是同一層嗎?

我讓故事變的複雜一點點,如果類別 B 沒有定義 greeting() 方法呢?像這樣:

class A:
    def greeting(self):
        print("Hey in A")

class B(A): pass

class C(A):
    def greeting(self):
        print("Hey in C")

class D(B, C): pass

如果類別 B 沒有定義 greeting() 方法,那麼接下來是會往上找類別 A,還是往旁邊找同一層的類別 C 呢?在 Python 決定查找順序的設計叫做 MRO,全名是 Method Resolution Order,我們可以透過類別的 .mro() 方法來查看:

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

順序是 D -> B -> C -> A,最後是每個類別的大家長 object,所以如果呼叫 d.greeting() 的時候,在類別 B 沒有定義方法的情況,會往下一個順序,也就是類別 Cgreeting 方法。

Python 的 MRO 是採用「C3 線性演算法(C3 Linearization Algorithm)」,這個演算法在 Python 2.3 之後開始被採用。這個演算法的目的是要找出一個合理的繼承順序,讓每個類別的方法都能被正確的呼叫到。

那麼在 2.3 之前呢?在這之前,Python 使用的是「深度優先搜尋(Depth-First Search)」的方式來找出 MRO,以剛才的範例算出來會是 D -> B -> A -> C,這樣的順序在某些情況下會導致問題,例如傳說中的「菱形繼承(Diamond Inheritance)」問題。

MRO 計算

單一繼承

我們先從最簡單的單一繼承開始,為了簡化,我暫時先讓類別裡就先放個 pass 不做事:

class A: pass
class B(A): pass

現在的繼承圖大概像這樣:

為你自己學 Python - 單一繼承

在計算 A 的 MRO 之前,雖然 A 類別沒有明顯的繼承其他類別,但在 Python 3 會自動幫我們繼承 object 類別,所以現在繼承關係是這樣:

為你自己學 Python - 單一繼承

先從最上層的 object 開始算,接下來我會用 L<類別> 來表示類別的線性化順序(Linearization Order),也就是 MRO:

L<object> = [object]

因為 object 是最上層了,所以只有一個元素 [object]。接下來是類別 A

L<A> = [A] + merge(L<object>, [object])

這公式看起來一開始看的時候有點複雜,其實就是這個類別加上它的這些上層類別的線性化順序,以及這些上層類別的列表的唯一合併的總和。

合併的計算方法,是選擇這些列表的頭部(Head)中第一個符合條件的,如果符合條件,稱之「良好頭部(Good Head)」,但我個人比較喜歡叫它「好線頭」,因為就像是在整理一堆線的時候,要找一條好的線頭開始整理。

要當一個好線頭的條件,就是這個元素在其它的列表不再出現,或是就算出現也是出現在列表的頭部。我們直接來進行計算可能會更清楚一點。在上面的公式中,首先要先把 L<object> 展開,所以原來的公式就會變成:

L<A> = [A] + merge([object], [object])

然後開始找頭,不過因為這裡只有一個 object,所以就直接把它從列表裡抽出來,L(A) 經過合併計算後:

L<A> = [A, object]

這個有點太簡單感受不太出來計算的過程,接下來我們再來看看 B 類別:

L<B> = [B] + merge(L<A>, [A])

這個合併就要稍微算一下了,首先,我把前面算過的 L<A>先展開,變成:

L<B> = [B] + merge([A, object], [A])

再來,merge 的過程要從後面這幾個列表裡抽出一個好的線頭(Good Head),先從第一個 A 開始。我剛好用這個例子,再把當一個好線頭的遊戲規則整理如下:

  1. 如果 A 沒有出現在後續的其它列表,或是有出現,而且也是第一個,那就是個好的線頭,跳到步驟 3。
  2. 承步驟 1,如果 A 不是合適的線頭,找下一個列表的頭,然後回到步驟 1。
  3. A 從所有列表裡抽出來往前擺,然後回到步驟 1,繼續找下一個元素。

在這裡例子裡,A 有出現在最後一個列表裡而且是第一個,所以它是個好線頭,把 A 從所有列表裡抽出來,現在變成:

L<B> = [B, A] + merge([object])

再來的合併就簡單了,因為 object 在所有列表裡都是第一個(也就剩它一個),最後的結果是:

L<B> = [B, A, object]

執行類別的 .mro() 方法來驗算一下:

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

看起來沒問題。這是單一繼承的情況,再來我們來看看多重繼承的情況。

多重繼承

先來個單純一點的多重繼承:

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass

現在的繼承結構大概像這樣:

為你自己學 Python - 多重繼承

這裡的 L<A> 跟上面的例子一樣,而 L<B>L<C> 分開看的話,其實它們兩個對類別 A 來說是單一繼承,所以算出來的答案跟前面單一繼承的答案差不多,分別是:

L<B> = [B, A, object]
L<C> = [C, A, object]

重點是最下層的 L<D>

L<D> = [D] + merge(L<B>, L<C>, [B, C])

L<B>L<C> 展開,準備進行合併:

L<D> = [D] + merge([B, A, object], [C, A, object], [B, C])

開始找好線頭,先從 B 開始,B 有出現在最後一個列表裡而且是第一個,所以是好線頭,把 B 從所有列表裡抽出來:

L<D> = [D, B] + merge([A, object], [C, A, object], [C])

繼續找下一個線頭,下一個是 AA 有出現在第二個列表 [C, A, object],但它不是第一個,所以不是個好線頭。沒關係,換下一個列表的頭 C 來試試看。嗯,C 有出現在最後一個列表裡而且是第一個,所以是好線頭,把 C 從所有列表裡抽出來:

L<D> = [D, B, C] + merge([A, object], [A, object], [A, object])

繼續找下一個線頭 AA 有出現在所有列表裡而且是第一個,所以是好線頭,把 A 從所有列表裡抽出來:

L<D> = [D, B, C, A] + merge([object], [object], [object])

最後收尾,把 object 從所有列表裡抽出來:

L<D> = [D, B, C, A, object]

來驗算一下:

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

結果跟我們手算的是一樣的。

以結果來說,看起來流程是是先往上層找,接著往平行層找,平行層都找完之後再繼續往上層找,直到最後的上層類別 object 為止。但這是比較單純一點的例子,我們來看個稍微複雜一點的例子...

複雜一點的繼承

先上程式碼:

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

這看起來好像不只複雜一點點:

為你自己學 Python - 多重繼承

沒關係,我們一樣從最簡單的開始:

L<A> = [A, object]
L<B> = [B, object]
L<C> = [C, A, B, object]

然後 L<D> 是單一繼承,所以也不難算:

L<D> = [D, B, object]

再來是 L<E>

L<E> = [E] + merge(L<C>, [E])

先展開 L<C>

L<E> = [E] + merge([C, A, B, object], [C])

開始合併,C 是好線頭,抽出來:

L<E> = [E, C] + merge([A, B, object])

後面剩一個列表就沒什麼好抽了,直接合併:

L<E> = [E, C, A, B, object]

再來算 L<F>

L<F> = [F] + merge(L<D>, L<C>, [D, C])

展開 L<D>L<C>

L<F> = [F] + merge([D, B, object], [C, A, B, object], [D, C])

開始合併,D 是個好線頭,抽出來:

L<F> = [F, D] + merge([B, object], [C, A, B, object], [C])

接著,B 有在後面的列表出現,但不是頭部的位置,不是好線頭。換下一個列表的 C,它符合好線頭的條件,抽出來:

L<F> = [F, D, C] + merge([B, object], [A, B, object])

再試一次 B,但很可惜現在它一樣不是好線頭,所以只好選擇下一個列表的 A,它是好線頭,抽出來:

L<F> = [F, D, C, A] + merge([B, object], [B, object])

剩下的都一樣,可直接合併,最後得到:

L<F> = [F, D, C, A, B, object]

最後一個 L<G>

L<G> = [G] + merge(L<F>, L<E>, [F, E])

展開 L<F>L<E>

L<G> = [G] + merge([F, D, C, A, B, object], [E, C, A, B, object], [F, E])

為了節省篇幅,這裡稍微快轉一下:

L<G> = [G] + merge([F, D, C, A, B, object], [E, C, A, B, object], [F, E])
L<G> = [G, F] + merge([D, C, A, B, object], [E, C, A, B, object], [E])
L<G> = [G, F, D] + merge([C, A, B, object], [E, C, A, B, object], [E])
L<G> = [G, F, D, E] + merge([C, A, B, object], [C, A, B, object])
L<G> = [G, F, D, E, C, A, B, object]

基本上也是照著先往上層找,再往平行層找,然後再繼續往上層找的順序。驗
驗算一下 FG

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

看起來沒錯。

其實整個計算的過程只是看起來複雜,但流程都是一樣的。透過 C3 線性演算法,Python 可以確保在多重繼承的情況下,繼承順序是有序而且每次都是唯一的。

算不出來?

再來個例子:

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass
class E(C, D): pass

現在的繼承圖大概長這樣:

為你自己學 Python - 多重繼承

L<A> = [A, object]
L<B> = [B, A, object]
L<C> = [C, A, object]

再來是 L<D>

L<D> = [D] + merge(L<B>, L<C>, [B, C])

展開 L<B>L<C>

L<D> = [D] + merge([B, A, object], [C, A, object], [B, C])

開始合併,快轉一下:

L<D> = [D] + merge([B, A, object], [C, A, object], [B, C])
L<D> = [D, B] + merge([A, object], [C, A, object], [C])
L<D> = [D, B, C] + merge([A, object], [A, object])
L<D> = [D, B, C, A, object]

最後一個 L<E>

L<E> = [E] + merge(L<C>, L<D>, [C, D])

展開 L<C>L<D>

L<E> = [E] + merge([C, A, object], [D, B, C, A, object], [C, D])

開始合併,先從 C 開始,嗯,它不是好線頭,換下一個 D,嗯...它也不是,再換下一個又是 C,啊,沒了,沒有任何一個好線頭,也就是這樣的繼承關係無法滿足 C3 線性化的合併條件。這時候 Python 會拋出一個 TypeError 的例外:

TypeError: Cannot create a consistent method resolution
order (MRO) for bases C, D

「不是每個戀曲都有美好回憶♫♪」

並不是所有的多重繼承都能夠成功算出 MRO,這時候就要考慮一下是不是真的需要這麼複雜的繼承關係,或是可以透過改變繼承順序來解決這個問題。

下一集,我們繼續來看看 C3 演算法在 CPython 裡是怎麼實作的。

本文同步刊載於 「為你自己學 Python - 類別繼承與家族紛爭(中))


上一篇
Day 24 - 類別繼承與家族紛爭(上)
下一篇
Day 26 - 類別繼承與家族紛爭(下)
系列文
為你自己讀 CPython 原始碼31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言