Pythonのメソッド順序解決を理解する

## はじめに
エキスパートPython第二版でPythonのメソッド順序解決について，学んだことを備忘録としてまとめる．


## Pythonのメソッド解決順序を理解する
>Python2.3以降には，Dylan言語のために考案されたC3線形化アルゴリズムに基づく，新しいメソッド解決順序(MRO)が追加されている

よくわからん．
まず，メソッド順序解決(MRO)とは何ぞや．これは，多重継承したクラスのメソッドが呼び出されるときに，どのメソッドがどういう順番で呼び出されるかを特定することを指す．
例えば，クラスAを継承するBクラスとCクラスがあるとする．またBクラスとCクラスを多重継承するDクラスが存在する．この場合，メソッドを解決する順序として，D→B→A(→C→A)という経路(深さ優先探索アルゴリズム)と，D→B→C→Aという経路(幅優先探索アルゴリズム)が少なくと列挙できる．

ここで，Pythonの多重継承では，C3線形化アルゴリズムによってMROが実装されている．

ではC3線形化とはどういったものか．[公式ドキュメント](https://www.python.org/download/releases/2.3/mro/)を拝見する.

以下、一部抜粋．
>take the head of the first list, i.e L[B1][0]; 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. 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.

headはリストの最初の要素．tailは残りの要素．例えば，(Base1,Base2,,,BaseN)の配列があったとき，Base1がhead,(Base2,...,BaseN)がtailに該当．実装例をもとに具体的にどういうことが起こっているかを説明する．

```python

class Base0():
    pass
class CommonBase(Base0):
    def method(self):
        print('CommonBase')
        
class Base1(CommonBase):
    pass

class Base2(CommonBase):
    def method(self):
        super(Base2,self).method()
        print('Base2')
        
class Base3(Base0):
    def method(self):
        super(Base3,self).method()
        print('Base3')
        
class MyClass(Base1,Base2,Base3):
    pass

MyClass().method()
#以下，結果
CommonBase
Base2
```
Base3クラスはCommonBaseクラスではなく、Base0クラスを継承している．これにより，Base3のmethod()が呼び出されない．

次に，`__mro__`属性により、クラスの継承関係を確認する．

```python
def L(cls):
    return [k.__name__ for k in cls.__mro__]
L(MyClass)
#以下，結果
['MyClass', 'Base1', 'Base2', 'CommonBase', 'Base3', 'Base0', 'object']
```
### 実装例をもとに考察
それぞれの基底クラスに対して深さ方向への再帰的な探索を行い，クラスが複数のリストに含まれている場合には，左方優先のルールによって順序を決定している．


この場合だと，

1. Base1(MyClassのhead)をMyClassの線形化リスト(クラスが呼び出される優先順位を並べたようなもの)に追加．
* Base1の線形化リストの先頭要素はCommonBaseクラスであり，CommonBaseクラスが他のクラスのtailに含まれているかどうか確認する
* CommonBaseクラスはBase2のリストにも含まれており，Base2をMyClassの線形化リストに追加．
* Base2の先頭要素，CommonBaseクラスが他クラスのリストに含まれているか確認する.CommonBaseはBase3には含まれていないので，CommonBaseクラスを線形化リストに追加する．
* CommBaseクラスをベースにして，同様に動作を繰り返す．

1～5までのことが上記の公式ドキュメントで説明されていると考えている．


##ただし、まだ謎な部分が存在する．

```python
if __name__ == "__main__":
    class Base0():
        pass
    class CommonBase(Base0):
        def method(self):
            print('CommonBase')

    class Base1(CommonBase):
        pass

    class Base2(CommonBase):
        def method(self):
            super(Base2,self).method()
            print('Base2')

    class Base3(CommonBase):
        def method(self):
            super(Base3,self).method()
            print('Base3')

    class MyClass(Base1,Base2,Base3):
        pass

    MyClass().method()

    def L(cls):
        return [k.__name__ for k in cls.__mro__]
    print(L(MyClass))
```
上記の実装は，Base1,2,3クラスの全てがCommonBaseクラスを継承している．
以下，予想される結果を考えたが、実際は異なる結果となる.

```予想される結果.
CommonBase
Base2
Base3
['MyClass', 'Base1', 'Base2', 'Base3', 'CommonBase', 'Base0', 'object']
```
```実際の結果.
CommonBase
Base3
Base2
['MyClass', 'Base1', 'Base2', 'Base3', 'CommonBase', 'Base0', 'object']
```

Base2クラスのmethod()よりもBase3クラスのmethod()が先に呼び出されている．これはなんであるか，現時点では不明．