メソッド解決順序(MRO)

多重継承が利用可能な言語では、メソッドを探索するときのベースクラスを探索する順序を、メソッド解決順序(MRO)と呼んでいる。Pythonではメソッドだけではなく、属性の探索でもこれが利用される。単一継承しかサポートしていない言語では、MROはとてもつまらない話題であるが、多重継承の場合には必要となってきて、MROアルゴリズムの選択が極めて難しい問題となりうる。Pythonでは、クラシック、Python 2.2の新スタイル、Python 2.3の新スタイル(C3とも呼ばれる)の3種類のMROアルゴリズムを持っていることが知られている。Python 3では、最後のアルゴリズムだけが生き残っている。

旧スタイルクラスはシンプルなMROの方式を利用していた。メソッドを探す場合には、シンプルに深さ優先探索を行って、ベースクラスの中で最初にマッチしたオブジェクトが返される。例えば、次のようなクラス構造について見てみよう。

class A:
  def save(self): pass

class B(A): pass

class C:
  def save(self): pass

class D(B, C): pass

クラスDのインスタンスxを作ったとすると、クラシック方式のメソッド解決順序では、D, B, A, Cという順序でクラスが探索されることとなる。そのため、x.save()というメソッド呼び出しが行われると、C.save()ではなく、A.save()が実行される。この方式は単純なケースではうまく行くが、より複雑なケースでは問題が発生してくる。次のような、ダイアモンド継承下でのメソッド検索の問題について見てみよう。

class A:
  def save(self): pass

class B(A): pass

class C(A):
  def save(self): pass

class D(B, C): pass

ここでは、クラスDはBとCを継承しており、その両方ともがクラスAを継承している。クラシックMROを使うと、D, B, A, C, Aという順序でメソッドを探索していくため、x.save()は、A.save()を参照する。しかし、この場合は、あなたが期待するのと違っているはずだ。BとCの両方がAを継承しており、再定義されてクラスAよりも詳細化されたC.save()を、クラスAのメソッドよりも呼びたいと考える人もいるだろう。実際はA.save()が常に呼ばれる。例えば、save()メソッドがオブジェクトの状態の保存に使用されるのであれば、クラスCによって定義されたメソッドが呼ばれないことで、Cに関する状態が無視されてプログラムの動作に問題が生じる。

この種の多重継承は、既存のコードの中でもめったに使われていないが、新スタイルクラスを使うとこの問題が日常茶飯事となる。新スタイルクラスはベースクラスであるobjectを継承することで行われる。新スタイルクラスでは、どのように多重継承を行っても、必ず上記のようなダイアモンド継承状態になる。

class B(object): pass

class C(object):
  def __setattr__(self, name, value): pass

class D(B, C): pass

それに加えて、派生クラスで拡張されるような(__setattr__()など)、いくつかのメソッドをobjectクラスが持っているため、このメソッドの解決順序の重要性は以前よりも高くなった。例えば、上記のコードの場合には、C.__setattr__は、クラスDのインスタンスにも適用されるべきである。

Python 2.2では、新スタイルクラスの導入のためにメソッド解決順序の見直しを行い、クラス定義時にあらかじめ順序を計算しておき、クラスオブジェクトごとに属性として格納するという方式のMROを適用した。以前の公式ドキュメントでは、深さ優先探索のMROを利用していると書かれていた。この検索順序の中で同じクラスが重複すると、MROのリストの中で後半に出てきた方が削除されるようになった。そのため、前に挙げたサンプルでは、D, B, C, Aという順序になり、以前のクラシッククラスで説明したD, B, A, C, Aとは違う結果になる。

実際には、MROの計算はこれよりもはるかに複雑である。私は、この新しいMROアルゴリズムがうまく働かないようなケースをいくつか発見した。2つのベースクラス(A, B)が、2つの異なる派生クラス(X, Y)のMROのリストの中でそれぞれ異なる順序で並ぶという特殊なケースがある。これらのクラスは元のクラスをそれぞれ異なる順序で継承しており、さらにそれを他のクラス(Z)が継承している。

class A:
class A(object): pass
class B(object): pass
class X(A, B): pass
class Y(B, A): pass
class Z(X, Y): pass

試しにこの新しいMROアルゴリズムを使用してみると、これらのクラスのMROは、Z, X, Y, B, A, objectという順序に並ぶ。objectというのは、共通のベースクラスである。しかし、私はBとAが逆になっているというのが気に入らなかった。本当のMROは、それらの順番を入れ替えて、Z, X, Y, A, B, objectという順番にする。このアルゴリズムは最初に検索したときに見つかった順番をなるべく保存しようとする。クラスZの場合には、継承リストの順番が先ということで、ベースクラスXが先に検索される。XはAとBを継承しているため、MROアルゴリズムはこの順番を保存しようとする。これはPython 2.2で実装されたもので、初期のアルゴリズムとしてドキュメント化した。

しかし、Python 2.2で新スタイルクラスが導入されてすぐに、Samuel Pedroni氏は、このドキュメント化されたMROアルゴリズムと、実際にコードを動かした結果が異なるということを発見した。さらに、これらの矛盾は上記のような特別な場合以外でも発生していた。長い時間をかけて議論を行い、Python 2.2で採用されたMROは壊れていることが確認され、"A Monotonic Superclass Linearization for Dylan" (K. Barrett, et al, presented at OOPSLA'96) で説明されている、C3線形化アルゴリズムを採用することが決定された。

本質的には、Python 2.2のMROアルゴリズムの本質的な問題は、探索順を線形に並べるという問題に関係していた。継承階層が複雑になると、それぞれの継承の関係は、シンプルなルールでクラスがどのような順番に並ぶかのチェックが行われる。明らかに、クラスAがクラスBを継承している場合にはMROはAがBの前にあることをチェックしなければならない。同様に、クラスBがクラスCとDを多重継承している場合には、BはCの前にあり、CはDの前にあることがチェックされなければならない。

複雑な継承階層の中では、順番を線形化する場合に、これらのルールをすべて満足するようにしたいと思うだろう。つまり、クラスAがクラスBの前になければならないということが決められた場合に、クラスBの方がクラスAの前に来るという矛盾した状態にはなって欲しくはない。その場合には結果が未定義なので、そのような継承階層はリジェクトされなければならない。オリジナルのMROが間違っていて、C3アルゴリズムがうまくいくのはこのような場面である。基本的に、C3の背後にあるアイディアは、複雑なクラス継承を行ったときにも、継承の関係から作られた順番のルールをすべてリストアップした場合に、すべてのクラス間でこれらのルールを満足するようなクラスの順番に、一列に並べることができるというものである。もしも、順番が一意に決まらない場合には、このアルゴリズムはその継承をエラーとして失敗させるようになっている。

そのため、Python 2.3では、Python 2.2で自前作ったMROアルゴリズムを捨て、アカデミックな目でチェックされたC3アルゴリズムを選択することにした。これにより、矛盾した順序を持つ継承を行うと、Pythonがそれをエラーとするようになった。例えば、先ほどの例で言えば、クラスXとクラスYの間では、順序に矛盾がある。クラスXを見るとクラスBの前にクラスAがなければならないということになるが、クラスYを見ると、クラスAの前にクラスBがなければならないことになっている。個別に見れば、これらの矛盾は問題ないが、これらのクラスXとYが、同じ継承階層の中に現れる(例えば、ここではクラスZが定義されることによってこれが発生する)と、C3アルゴリズムはこのクラスをリジェクトする。これは言うまでもなく、Pythonのthe Zen of Pythonの「問題があるときには、こっそりと処理してはならない」というルールにもマッチしている。