【超入門】キミにも読める！Rubyのソースコードの歩き方 #Ruby

はじめに

先日、会社のSlackで、新入社員から Array#sort の動作（ソートのアルゴリズム）が良くわからないという質問がありました。
「多分、クイックソートじゃないかと思うが Rubyのソースコードのどこに実装されているかわからない ので、Rubyコミッターに聞きましょう。」
みたいな先輩社員（私の同僚）からのアドバイスがあり、私に?話が振られてきました。

言われてみれば、みんな、Rubyのソースコードのどこに何があるか知らないのかもと思いました。
ずいぶん前に、「【超入門】キミにも作れる！ Ruby拡張ライブラリ開発」を書きましたが、今回は読み方の超入門編です。

Array#sort を題材に説明していきます。

なお、 Ruby のバージョンは、 3.2.2 を前提とします。

ディレクトリとファイル

Rubyのメソッドの大半は、以下のどこかのディレクトリにあるファイルで実装されています。

直下のディレクトリ。C言語で書かれた組み込みライブラリのソースコード。
lib ディレクトリ。標準添付ライブラリのうち、Rubyで書かれたコードが含まれています。
ext ディレクトリ。標準添付ライブラリのうち、C言語で書かれたコードが含まれています。

中には例外もあるかも知れませんが、大雑把にはこの3つのどこかにあると思っておけばいいでしょう。

lib ディレクトリは普通に、Rubyで書かれたファイルが含まれているので、C言語はちょっと...という方は、とっかかりとして、lib ディレクトリの中の Rubyのコードが書かれたファイルを読んでみると良いと思います。

クラスとファイル

Array#sort に話を戻します。 Array は組み込みライブラリの１つです。
なので、まずは、直下のディレクトリを探します。

Rubyのソースコードとクラスは大体、対応しています。
Array クラスなら array.c ファイル、 String クラスなら string.c ファイルで実装されています。

例外はありますが、ファイル名が、クラス名.downcase + '.c' になるファイルで実装されていると思っておけばいいでしょう。

メソッドからC言語の関数へ

では、 array.c の中身を見てみましょう。 array.c は 9000行近くありますが、恐れることはありません。
rb_define_method と書かれている箇所を探しましょう。大体、 ファイルの最後の方に書かれていることが多い です。
その中で、 sort と書かれている箇所に絞り込みます。すると以下が見つかります。

    rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
    rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);

rb_cArray は、Array クラスのことで、 "sort" は sort メソッドのことです。
rb_ary_sort は、C言語の関数です。

1行目は、 Array#sort は、C言語の rb_ary_sort で実装されている。
2行目は、 Array#sort! は、 C言語の rb_ary_sort_bang で実装されている。

ことを意味します。詳細の説明は割愛しますが、数字の0は、メソッドの引数の数を意味しています。

ここでは以下の4点を抑えておけばいいでしょう（例外もある）。

Rubyのメソッドは、 rb_define_method で定義されている。
rb_define_method の1番目の引数がメソッドを持つクラスである。
rb_define_method の2番目がメソッド名である。
rb_define_method の3番目がメソッドを実装しているC言語の関数。

同じように String#downcase を探してみると string.c の中で rb_str_downcase で実装されていることがわかります。

    rb_define_method(rb_cString, "downcase", rb_str_downcase, -1);

C言語の中へ

では、 rb_ary_sort を array.c の中から探してみましょう。
array.c の中で、 rb_ary_sort が1文字目から登場する行 を探して(/^rb_ary_sort/ で grep)みましょう。

VALUE
rb_ary_sort(VALUE ary)
{
    ary = rb_ary_dup(ary);
    rb_ary_sort_bang(ary);
    return ary;
}

rb_ary_sort は、 rb_ary_dup を実行して rb_ary_sort_bang を実行していることがわかりました。
ところで、 rb_ary_sort_bang は Array#sort! の実装でした。

ここからわかることは、 Array#sort (のC言語による実装) は、 rb_ary_dup を実行してから Array#sort! (のC言語による実装) を実行しているので、 Array#sort! より遅いということです。

rb_ary_sort_bang の中へ

rb_ary_sort_bang の中身を見てみましょう。こちらはかなり長いですが、注意深く見ていくと次の実装が見つかります。

            ruby_qsort(ptr, len, sizeof(VALUE),
                       rb_block_given_p()?sort_1:sort_2, &data);

ruby_qsort が見つかります。それっぽい名前の関数です。

ruby_qsort を探す

ruby_qsort を探してみましょう。 ruby_qsort は、 array.c の中にはありません。
ここで、grep を使って探してみます。

util.c と include/ruby/util.h にそれらしきものがいくつか見つかりますが、まずは、 include/ruby/util.h を見ましょう。
（xxx.h にそのものズバリの定義があることが多いので、そちらを先に読みます）

ファイルの中を読むと以下の記述が見つかります。

/**
 * Reentrant implementation of  quick sort.  If your  system provides something
 * (like  C11 qsort_s),  this is  a thin  wrapper of  that routine.   Otherwise
 * resorts to our own version.
 */
#ifdef HAVE_GNU_QSORT_R
# define ruby_qsort qsort_r
#else
void ruby_qsort(void *, const size_t, const size_t,
                int (*)(const void *, const void *, void *), void *);
#endif

Reentrant implementation of quick sort. からどうやら、クイックソートのアルゴリズムが使われているらしいことがわかります。

C言語の深いところに入りますが、 #ifdef HAVE_GNU_QSORT_R は「 GNU の qsort_r がシステムで定義されているならば」という意味です。
#define ruby_qsort qsort_r は、「ruby_qsort は、qsort_r として定義するよ」ということです。

システムで定義されていない場合はこの記事の範囲を超えてしまうので割愛します。util.c の中を細かく追っていけばわかりますが、ざっくり言うと GNU の qsort_r がないシステムでは、 qsort_s やそれに類する関数を利用してruby_qsort を実装しています。使えそうな関数がないシステムでは、まるごと自前で ruby_qsort を実装しています。

ということで、 Array#sort は、qsort_r が使われており（使われてない場合もあるけど）、クイックソートのアルゴリズムを使ってソートしていることがわかりました。

まとめ

Rubyのメソッドは、直下のディレクトリか、ext ディレクトリか、lib ディレクトリか、いずれかのディレクトリで定義されている (例外もある)。
クラス名とファイル名が対応する(例外もある)。
メソッドは、 rb_define_method で定義され、1番目の引数がクラス、2番目がメソッド名、3番目がメソッドをC言語レベルで実装している関数名である(例外もある)。

こういったことを頭に入れて、気になるメソッドの実装がどうなっているか、たまには眺めてみてはいかがでしょうか？

謝辞

この記事を書くきっかけをくれた新入社員のMさん、私？にネタを振ってくれたBさんに感謝します。