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

## はじめに

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

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

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

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

## ディレクトリとファイル

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

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

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

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

## クラスとファイル

`Array#sort` に話を戻します。 `Array` は [組み込みライブラリ](https://docs.ruby-lang.org/ja/latest/library/_builtin.html) の１つです。
なので、まずは、直下のディレクトリを探します。

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

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

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

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

https://github.com/ruby/ruby/blob/e51014f9c05aa65cbf203442d37fef7c12390015/array.c#L8868-L8869
```c
    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` で実装されていることがわかります。

https://github.com/ruby/ruby/blob/e51014f9c05aa65cbf203442d37fef7c12390015/string.c#L11990

```c
    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)みましょう。


https://github.com/ruby/ruby/blob/e51014f9c05aa65cbf203442d37fef7c12390015/array.c#L3672-L3678

```c
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` の中身を見てみましょう。こちらはかなり長いですが、注意深く見ていくと次の実装が見つかります。

https://github.com/ruby/ruby/blob/e51014f9c05aa65cbf203442d37fef7c12390015/array.c#L3584-L3585

```c
            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` にそのものズバリの定義があることが多いので、そちらを先に読みます）

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

https://github.com/ruby/ruby/blob/e51014f9c05aa65cbf203442d37fef7c12390015/include/ruby/util.h#L118-L128
```c
/**
 * 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](https://github.com/gagern/gnulib/blob/6465306025facca3881bcea411b757b0fe8e8df8/lib/qsort_r.c#L42) がシステムで定義されているならば」 という意味です。
`#define ruby_qsort qsort_r` は、 「ruby_qsort は、[qsort_r](https://github.com/gagern/gnulib/blob/6465306025facca3881bcea411b757b0fe8e8df8/lib/qsort_r.c#L42) として定義するよ」ということです。

システムで定義されていない場合はこの記事の範囲を超えてしまうので割愛します。`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さんに感謝します。