よくわからないので実装して理解するRubyのメソッド解決順序



いままであまり気にする機会がなかったので、深く考えたことなかったのだけど、Rubyのメソッド解決順序はどのようになっているかということについて、疑問に思いいろいろ試してみた。ソースを読めばいいんだろうけど、いろいろ試しながら実装していけば理解できるだろうと思い立ち、なぜかJavaScriptで実装してみた。

https://github.com/hirokidaichi/js-ruby-mro



## メソッド解決順序(MRO)

メソッド解決順序とは、``hoge.fuga``のようにメソッド呼び出しをしたときに
どのクラスから順番にmethod名を探すかという順序のこと。

これらに影響を与えそうな要素は以下

* 継承
* モジュールの``include``
* モジュールの``prepend``
* 特異クラス
* 特異メソッド
* ``method_missing`` 

こんなものだろうか。
クラスオブジェクトに対して、``ancestors``メソッドを呼べば、
どのような順序でmethodの探索がなされるかがArrayとして帰ってくる。

```ruby

class A
end

class B < A
end

p B.ancestors
# [B, A, Object, Kernel, BasicObject]


```

この例であれば、B,A,Object ... という順序でmethodの探索が行われることがわかる。

## 菱形継承問題
菱形継承問題というのがある。
それは、詳しくはwikipediaを読んでもらいたいのだけど、多重継承が可能な言語において、菱形上に継承関係が作られるとどのような順序でメソッドが探索されるのかということについて曖昧さが残るという話。

http://ja.wikipedia.org/wiki/%E8%8F%B1%E5%BD%A2%E7%B6%99%E6%89%BF%E5%95%8F%E9%A1%8C


たとえば、こんなとき

```ruby

class D end
class B < D end
class C < D end
class A < B,C end

```
![220px-Diamond_inheritance.svg.png](https://qiita-image-store.s3.amazonaws.com/0/35671/65b92645-7754-ef50-1a0f-1a5cc2193565.png "220px-Diamond_inheritance.svg.png")

実際には、rubyには多重継承はないがmoduleの``include``は多重にできる。


```ruby

module D end
module B
 include D
end
module C 
 include D 
end
class A 
 include B
 include C
end
# [A, C, B, D, Object, Kernel, BasicObject]
```

このようになったときに、A,C,B,Dの順序で呼ばれる。

## 深さ優先探索なMRO
もし、ナイーブにクラスの継承関係をたどろうと思ったら、こんな感じになるだろう。

```javascript
function ancestors(classOrModule) {
	return classOrModule.modules.map(ancestors);
}
```

再帰的にそれぞれの要素に対して、ancestorsを呼び出すことで、include関係木をたどろうとするだろう。

しかしこの場合、[A,C,D,B]となる。

```perl
use strict;
use warnings;

package D1 {
    sub hoge { }
};

package C1 {
    use base qw/D1/;
}

package B1 {
    use base qw/D1/;
}

package A1 {
    use base qw/B1 C1/;
}
use 5.010;
use mro;
our $, = ",";
say @{ mro::get_linear_isa("A1") };

```
実際、Perlでは特に指定しない場合のメソッド解決順序は、深さ優先で探索される。
この場合、 *B1からみて、自分よりもあとにD1を探索してほしいという宣言が無効化されてしまう*。

近年のperlでは、次のようにすれば深さ優先ではなく、探索アルゴリズムを切り替えることができる。

```perl
use strict;
use warnings;

package D1 {
    sub hoge { }
};

package C1 {
    use base qw/D1/;
}

package B1 {
    use base qw/D1/;
}

package A1 {
    use mro 'c3'; 
    use base qw/B1 C1/;
}
use 5.010;
use mro;
our $, = ",";
say @{ mro::get_linear_isa("A1") };
```

ここで使われているのは、C3線形化アルゴリズムというものだ。

## C3線形化アルゴリズム
http://en.wikipedia.org/wiki/C3_linearization


これだけだと、幅優先探索を単純にした場合と結果が同じになってしまうので、
もう一つエントリを増やして、C3アルゴリズムの違いを見る。

```perl
use strict;
use warnings;

package D1 {
    sub hoge { }
};
package E1 {
    sub hoge {};
}
package C1 {
    use base qw/D1/;
}

package B1 {
    use base qw/D1/;
}

package A1 {
    use mro "c3";
    use base qw/B1 C1 E1/;
}
use 5.010;
use mro;
our $, = ",";
say @{ mro::get_linear_isa("A1") };
# A1,B1,C1,D1,E1

```

また、Rubyのincludeではどうだろうか。

```ruby
module D 
end

module B
 include D
end

module C 
 include D
end

module E
end
class A 
 include E
 include C
 include B
end

p A.ancestors
# [A, B, C, D, E, Object, Kernel, BasicObject]
```

お、一致した。どうやらrubyも少なくとも単純な幅優先探索をしている訳ではなさそうだ。

C3アルゴリズムの詳細はここがくわしい。
https://www.python.org/download/releases/2.3/mro/

> L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)
これをみると、
mergeという関数を再帰的に呼び出しているようだ。

そしてmergeの実装は

> L[A] = A + merge(BDEO,CDFO,BC)
     = A + B + merge(DEO,CDFO,C)
     = A + B + C + merge(DEO,DFO)
     = A + B + C + D + merge(EO,FO)
     = A + B + C + D + E + merge(O,FO)
     = A + B + C + D + E + F + merge(O,O)
     = A B C D E F O

この例にあるように、

> 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.

先頭を取り出し、残りのリストの*先頭以外*にその要素が含まれない場合、それをgoodHeadと見なす。含まれていた場合は、そいつは後回しにして、次のリストからheadをとりだす。

つまり、「あとに機会があれば、あとにまわす。」という至極単純なものだった。

```c3.js

function merge(list) {

    if (list.length == 0)
        return []
    //good headとなる最初のリストを取り出す。
    var goodHeadList = list.first(function(elem) {
        var head = elem.head();
        //　そのリスト以外を対象に
        var theOther = list.remove(elem);
        //  headと一致するものがあるか調べ、すべてなければ条件を満たす。
        return theOther.every(function(otherElem) {
            return (otherElem.tail().indexOf(head) < 0);
        });
    });
    if (!goodHeadList) {
        return [];
    }
    var goodHead = goodHeadList.head();
    // 見つかれば、それをリストから取り除き、
    var headRemoved = remove(list, goodHead).filter(function(l) {
        return (l.length > 0);
    });
    if (isEmpty(headRemoved))
        return [goodHead];
    // 残りをmergeする。
    return [goodHead].concat(merge(headRemoved));

}
```
jsで実装してみるとこんなかんじ。わかりやすく実装するため、無駄が多い感じになってる。

## 継承との組み合わせ
継承先よりもincludeされたmoduleを先に探索するのであれば、
同一のモジュールを継承よりも先に見つかった場合はどうするのか。
次のような例を見てみる。

```ruby:include-inherit-include.rb
module O1
end

module B1
  include O1
end

module A1
  include O1
end

class P
  include A1
  include B1
end

module B2
  include O1
end

module A2
  include O1
end

class K < P
  include A2
  include B2
end

p K.ancestors;
# [K, B2, A2, P, B1, A1, O1, Object, Kernel, BasicObject]

```
これをみると、O1が後から読まれている。
あとにあるのであれば、後回し。というルールがありそうだ。

ここは単純に差集合を使ってみるか。

```javascript
var modules = c3.linearlize(PREPEND_TABLE, INCLUDE_TABLE, className);
  :
  :
return modules.diff(parentAncestors).concat(parentAncestors);
```
おなじ依存関係を適応してみると、


```javascript
    def.module("O1");
    def.module("B1").include("O1");
    def.module("A1").include("O1");
    def.class("P")
        .include("A1")
        .include("B1");

    def.module("B2").include("O1");
    def.module("A2").include("O1");
    var k = def.class("K")
        .extend("P")
        .include("A2")
        .include("B2");
    assertEqualArray(k.ancestors(), ['K', 'B2', 'A2', 'P', 'B1', 'A1', 'O1'], "include inherit include 3");
```

お、一致した。違ってるかもしれないが、後回しルールで把握しておくと良さそうだ。

## prepend登場

ruby2.0からclass自身よりも前にmoduleを探索するというprependが登場した。
これにより、すでに存在するmethodをwrapするような動作が簡単に記述できるようになった。

とりあえず、あと回しルールを採用してみるか。


javascriptの実装だとこんな感じ

```javascript
    var ancestors = (parents) ? merge(parents.map(linearlizeBind)) : [];
    var descendant = (children) ? merge(children.map(linearlizeBind)) : [];
    return descendant.diff(ancestors).concat([name]).concat(ancestors);
```

実際に試してみると、

```ruby
module O1
end

module B1
  include O1
end

module A1
  include O1
end

module B2
  include O1
end

module A2
  include O1
end

class K
  include A1
  include B1
  prepend A2
  prepend B2
end

p K.ancestors
# [B2, A2, K, B1, A1, O1, Object, Kernel, BasicObject]

```

O1がしっかり後回しになっている！

js実装の方でも

```javascript
    def.clear();
    def.module("O1");
    def.module("B1").include("O1");
    def.module("A1").include("O1");


    def.module("O2");
    def.module("B2").include("O2");
    def.module("A2").include("O2");
    var k = def.class("K")
        .include("A1")
        .include("B1")
        .prepend("A2")
        .prepend("B2");

    assertEqualArray(k.ancestors(), ["B2", "A2", "O2", "K", "B1", "A1", "O1"], "prepend and include");

```
お、一致した。

もっと複雑な例とかでは違ってくるかもしれないけれど、
基本的には、「明日やれることは明日やる」という後回しポリシーで考えておけばよさそうですね！

実際はちがうよ！とか本当はこうだよ！というコメントも待ってます。