Go to Qiita Advent Calendar 2024 Top
LoginSignup
40
42

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@hirokidaichi(広木 大地)in株式会社Rector

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

Last updated at Posted at 2014-05-02

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

メソッド解決順序(MRO)

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

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

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

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


class A
end

class B < A
end

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

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

菱形継承問題

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

たとえば、こんなとき


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

220px-Diamond_inheritance.svg.png

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


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

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

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

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

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

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では、次のようにすれば深さ優先ではなく、探索アルゴリズムを切り替えることができる。

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線形化アルゴリズム

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

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ではどうだろうか。

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を先に探索するのであれば、
同一のモジュールを継承よりも先に見つかった場合はどうするのか。
次のような例を見てみる。

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が後から読まれている。
あとにあるのであれば、後回し。というルールがありそうだ。

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

var modules = c3.linearlize(PREPEND_TABLE, INCLUDE_TABLE, className);
  :
  :
return modules.diff(parentAncestors).concat(parentAncestors);

おなじ依存関係を適応してみると、

    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の実装だとこんな感じ

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

実際に試してみると、

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実装の方でも

    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");

お、一致した。

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

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

40
42
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
40
42

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?