この記事は、フィヨルドブートキャンプ Part 1 Advent Calendar 2023 の 18 日目の記事です。
はじめに
自分はここ 2 年ほど Ruby on Rails を学習しており、個人開発で作った Web アプリ(これ)も、Rails で開発しています。
先日、Ruby の基礎を改めて復習しようと Ruby Silver の試験を受けたのですが、試験に向けた学習で色々なメソッドを触っているうちに、「これらの実装をのぞいてみたいな……?」と思い立ちました。
初めて Ruby 本体のリポジトリを clone してきて、ふんわりだけど読めた!というのはひとつの嬉しい体験だったので、残しておこうと思います。
こちらの記事のおかげ
こちらの Qiita 記事を見つけたおかげで、ひとまず読んでみちゃおう〜という気持ちになれました。ありがたいです。
String#succ を読んでみる🙋♀️
String#succ の実装を読んでみることにしました。
Ruby マニュアルの説明:
self の「次の」文字列を返します。
「次の」文字列は、対象の文字列の右端からアルファベットなら アルファベット順(aの次はb, zの次はa, 大文字も同様)に、数字なら 10 進数(9 の次は 0)とみなして計算されます。
なんかおもしろいな〜と思ったのと、「次の」ってどういう定義なんだろう? と思ったのでチョイス。
# 基本的な例 p "aa".succ # => "ab" p "111".succ # => "112" # 文字、数字ともに繰り上がりが起きる p "9".succ # => "10" p "zz".succ # => "aaa" # 数字と文字が混在していても繰り上がる p "1z".succ # => "2a" p "a9".succ # => "b0" p "AZ".succ # => "BA" # 文字が続けば記号をまたいで繰り上がる p "a?Z".succ # => # "b?A" p "a?9".succ # => # "a?10" # 文字と数字と記号が混在していれば、文字同士または数字同士続くところまで繰り上がる p "a.9.9".succ # => # "a.10.0" # 記号だけの文字列のときは、次の記号になる p "..".succ # => "./" # 符号は無視される p "-9".succ # => "-10" # 空文字の時は空文字を返す p "".succ # => ""
実装コードを確認する
Ruby のリポジトリからソースコードを clone し、読んでいきます。2023/12/18 時点の安定版である 3.2.2 の Git タグを参照しています。
先述の Qiita によると
Rubyのソースコードとクラスは大体、対応しています。 Array クラスなら array.c ファイル、 String クラスなら string.c ファイルで実装されています。
とのことでした。
string.c の中で検索してみると、succ メソッドの定義が見つかりました。(該当箇所)
rb_str_succ
という関数に実体が定義されているみたい。
rb_define_method(rb_cString, "succ", rb_str_succ, 0); // 略 rb_define_method(rb_cString, "next", rb_str_succ, 0);
同じく string.c 内に、rb_str_succ
関数の定義がありました。 (該当箇所)
「『次の文字』とは何か、が分かる」を目指して、この関数を読み進めていきます。
(ちなみに自分の場合、C言語は学生の時にちょっぴり触れたくらいです。)
VALUE rb_str_succ(VALUE orig) { VALUE str; str = rb_str_new(RSTRING_PTR(orig), RSTRING_LEN(orig)); rb_enc_cr_str_copy_for_substr(str, orig); return str_succ(str); } static VALUE str_succ(VALUE str) { rb_encoding *enc; char *sbeg, *s, *e, *last_alnum = 0; int found_alnum = 0; long l, slen; char carry[ONIGENC_CODE_TO_MBC_MAXLEN] = "\1"; long carry_pos = 0, carry_len = 1; enum neighbor_char neighbor = NEIGHBOR_FOUND; slen = RSTRING_LEN(str); if (slen == 0) return str; enc = STR_ENC_GET(str); sbeg = RSTRING_PTR(str); s = e = sbeg + slen; while ((s = rb_enc_prev_char(sbeg, s, e, enc)) != 0) { if (neighbor == NEIGHBOR_NOT_CHAR && last_alnum) { if (ISALPHA(*last_alnum) ? ISDIGIT(*s) : ISDIGIT(*last_alnum) ? ISALPHA(*s) : 0) { break; } } l = rb_enc_precise_mbclen(s, e, enc); if (!ONIGENC_MBCLEN_CHARFOUND_P(l)) continue; l = ONIGENC_MBCLEN_CHARFOUND_LEN(l); neighbor = enc_succ_alnum_char(s, l, enc, carry); switch (neighbor) { case NEIGHBOR_NOT_CHAR: continue; case NEIGHBOR_FOUND: return str; case NEIGHBOR_WRAPPED: last_alnum = s; break; } found_alnum = 1; carry_pos = s - sbeg; carry_len = l; } if (!found_alnum) { /* str contains no alnum */ s = e; while ((s = rb_enc_prev_char(sbeg, s, e, enc)) != 0) { enum neighbor_char neighbor; char tmp[ONIGENC_CODE_TO_MBC_MAXLEN]; l = rb_enc_precise_mbclen(s, e, enc); if (!ONIGENC_MBCLEN_CHARFOUND_P(l)) continue; l = ONIGENC_MBCLEN_CHARFOUND_LEN(l); MEMCPY(tmp, s, char, l); neighbor = enc_succ_char(tmp, l, enc); switch (neighbor) { case NEIGHBOR_FOUND: MEMCPY(s, tmp, char, l); return str; break; case NEIGHBOR_WRAPPED: MEMCPY(s, tmp, char, l); break; case NEIGHBOR_NOT_CHAR: break; } if (rb_enc_precise_mbclen(s, s+l, enc) != l) { /* wrapped to \0...\0. search next valid char. */ enc_succ_char(s, l, enc); } if (!rb_enc_asciicompat(enc)) { MEMCPY(carry, s, char, l); carry_len = l; } carry_pos = s - sbeg; } ENC_CODERANGE_SET(str, ENC_CODERANGE_UNKNOWN); } RESIZE_CAPA(str, slen + carry_len); sbeg = RSTRING_PTR(str); s = sbeg + carry_pos; memmove(s + carry_len, s, slen - carry_pos); memmove(s, carry, carry_len); slen += carry_len; STR_SET_LEN(str, slen); TERM_FILL(&sbeg[slen], rb_enc_mbminlen(enc)); rb_enc_str_coderange(str); return str; }
① rb_str_succ 関数
頭から読んでいきます。
VALUE rb_str_succ(VALUE orig) { VALUE str; str = rb_str_new(RSTRING_PTR(orig), RSTRING_LEN(orig)); rb_enc_cr_str_copy_for_substr(str, orig); return str_succ(str); }
VALUE 型がいきなり分からないな〜と思ったけれど、README.EXT.ja - Documentation for Ruby 2.0.0 などを見ると
Cの変数には型があり,データには型がありません.ですから,たとえばポインタをintの変数に代入すると,その値は整数として取り扱われます.逆にRubyの変数には型がなく,データに型があります.
この違いのため,CとRubyは相互に変換しなければ,お互いのデータをアクセスできません.RubyのデータはVALUEというCの型で表現されます.VALUE型のデータはそのデータタイプを自分で知っています.このデータタイプというのはデータ(オブジェクト)の実際の構造を意味していて,Rubyのクラスとはまた違ったものです.
とのことなので、Ruby のデータを扱うための汎用的な型なのだろうな〜くらいの理解で先へ進む。
引数で受け取った元の文字列のコピーを作成して、コピーのほうをstr_succ
関数に渡しています。
RSTRING_LEN
は文字列の長さを、RSTRING_PTR
は文字列先頭のポインタを取得するマクロとのこと。
str_succ
関数で実際に次の文字列を算出して return しているみたい。
② str_succ 関数の前編(処理の準備)
受け取った文字列の情報(サイズやエンコーディング)の取得や、各種変数の初期化。
carry は、繰り上がりに関する何か。
空文字の場合はそこで return 。
sbeg + slen で文字列末尾のポインタを取得して、この後末尾から走査をしていきます。
"aa".succ => "ab"
のように、右端の桁から文字を進めていくために、末尾(=右端)からスタートしているようです。
static VALUE str_succ(VALUE str) { rb_encoding *enc; char *sbeg, *s, *e, *last_alnum = 0; int found_alnum = 0; long l, slen; char carry[ONIGENC_CODE_TO_MBC_MAXLEN] = "\1"; long carry_pos = 0, carry_len = 1; enum neighbor_char neighbor = NEIGHBOR_FOUND; slen = RSTRING_LEN(str); if (slen == 0) return str; enc = STR_ENC_GET(str); sbeg = RSTRING_PTR(str); s = e = sbeg + slen; // 略 }
ONIGENC_CODE_TO_MBC_MAXLEN
のマクロは 7 が定義されていました。
(該当箇所)
マルチバイト文字の最大長らしい。
enum neighbor_char
はこのように定義。(該当箇所)
enum neighbor_char {
NEIGHBOR_NOT_CHAR,
NEIGHBOR_FOUND,
NEIGHBOR_WRAPPED
};
それぞれこんな意味っぽい。
- NEIGHBOR_NOT_CHAR:非アルファベットまたは非数字だった
- NEIGHBOR_FOUND:次の文字が見つかった
- NEIGHBOR_WRAPPED:繰り上がった
③ str_succ 関数の後編
文字列の走査開始。
rb_enc_prev_char
は、1 つ左の文字を返すメソッドです。
(該当箇所)
先述のように右端の文字からスタートし、1 文字チェックするごとに s が指す現在地の文字は左にずれていって、それより左の文字がなく NULL を返すと、s != 0 が FALSE になってループを抜ける形。
enc_succ_alnum_char
関数で文字列を1 つ進め、返り値に応じて分岐しています。
NEIGHBOR_FOUND
(次の文字が見つかった)であればその状態の文字列を返して終了する。NEIGHBOR_WRAPPED
(繰り上がった)であればfound_alnum
(記号でない文字列が見つかった)フラグと、 carry(繰り上がり)の情報を更新してから次のイテレーションに進む。NEIGHBOR_NOT_CHAR
(非アルファベットまたは非数字だった)であれば、何もせず次のイテレーションへ進む。
それぞれに対応する例を考えると、下記のようになりそうです。
- 文字列が
"dog"
で現在の文字が"g"
だったら、1 ループ目で次の文字"h"
が見つかってNEIGHBOR_FOUND
となり、"doh"
を return して終了する。 - 文字列が
"129"
で現在の文字が"9"
だったら、"9"
は"0"
になり、NEIGHBOR_WRAPPED
となって次のイテレーションで"2"
のチェックに進む。 - 文字列が
a."
で現在の文字が"."
だったら、NEIGHBOR_NOT_CHAR
となって次のイテレーションで"a"
のチェックに進む。
while ((s = rb_enc_prev_char(sbeg, s, e, enc)) != 0) { if (neighbor == NEIGHBOR_NOT_CHAR && last_alnum) { if (ISALPHA(*last_alnum) ? ISDIGIT(*s) : ISDIGIT(*last_alnum) ? ISALPHA(*s) : 0) { break; } } l = rb_enc_precise_mbclen(s, e, enc); if (!ONIGENC_MBCLEN_CHARFOUND_P(l)) continue; l = ONIGENC_MBCLEN_CHARFOUND_LEN(l); neighbor = enc_succ_alnum_char(s, l, enc, carry); switch (neighbor) { case NEIGHBOR_NOT_CHAR: continue; case NEIGHBOR_FOUND: return str; case NEIGHBOR_WRAPPED: last_alnum = s; break; } found_alnum = 1; carry_pos = s - sbeg; carry_len = l; }
なおif(neighbor == NEIGHBOR_NOT_CHAR && last_alnum) .....
の ブロックでは、 last_alnum
(記号の右側にあった文字)と s
(記号の左側にある現在の文字) が異なる種類(一方がアルファベットで他方が数字、またはその逆)であればループを抜けることで、下記のような「文字と数字と記号が混在していれば、文字同士または数字同士続くところまで繰り上がる」という仕様を実現していそうです。
# 数字同士が続いているところまで繰り上がり、文字には影響しない p "a.9.9".succ # => # "a.10.0"
全ての文字でNEIGHBOR_NOT_CHAR
だった場合は、次の if 文内のループに入り、enc_succ_char
関数で記号を1つ次の文字に更新していきます。
前半と似た形で、
enc_succ_char
関数で文字列を1つ進め、返り値がNEIGHBOR_FOUND
であればその状態の文字列を返して終了。enc_succ_char
関数の返り値がNEIGHBOR_WRAPPED
またはNEIGHBOR_NOT_CHAR
であれば、繰り上がりの処理をして次のイテレーションに進む
という感じみたいです。
rb_enc_precise_mbclen
は指定したポインタにある文字のバイト数を取得する関数(参照箇所1、2)、
rb_enc_asciicompat
はエンコーディングが何らかの意味で ASCII と互換性があるかどうかを取得する関数(参照箇所)のよう。
if (!found_alnum) { /* str contains no alnum */ s = e; while ((s = rb_enc_prev_char(sbeg, s, e, enc)) != 0) { enum neighbor_char neighbor; char tmp[ONIGENC_CODE_TO_MBC_MAXLEN]; l = rb_enc_precise_mbclen(s, e, enc); if (!ONIGENC_MBCLEN_CHARFOUND_P(l)) continue; l = ONIGENC_MBCLEN_CHARFOUND_LEN(l); MEMCPY(tmp, s, char, l); neighbor = enc_succ_char(tmp, l, enc); switch (neighbor) { case NEIGHBOR_FOUND: MEMCPY(s, tmp, char, l); return str; break; case NEIGHBOR_WRAPPED: MEMCPY(s, tmp, char, l); break; case NEIGHBOR_NOT_CHAR: break; } if (rb_enc_precise_mbclen(s, s+l, enc) != l) { /* wrapped to \0...\0. search next valid char. */ enc_succ_char(s, l, enc); } if (!rb_enc_asciicompat(enc)) { MEMCPY(carry, s, char, l); carry_len = l; } carry_pos = s - sbeg; } ENC_CODERANGE_SET(str, ENC_CODERANGE_UNKNOWN); }
最後のところでは、最後の桁の繰り上がりを反映して、最終的な文字列を返してそう。
RESIZE_CAPA(str, slen + carry_len); sbeg = RSTRING_PTR(str); s = sbeg + carry_pos; memmove(s + carry_len, s, slen - carry_pos); memmove(s, carry, carry_len); slen += carry_len; STR_SET_LEN(str, slen); TERM_FILL(&sbeg[slen], rb_enc_mbminlen(enc)); rb_enc_str_coderange(str); return str;
ここまで読んでみると、「次の文字」を探す実質のロジックはenc_succ_alnum_char
とenc_succ_char
に書いてあるみたいです。
④ enc_succ_alnum_char 関数
文字か数字かを判定し、それに応じて ctype を設定しています。
どちらにも当てはまらない(=記号など)場合は早々にNEIGHBOR_NOT_CHAR
を return して終了。
for 文内でenc_succ_char
関数を実行し、次の文字への更新と、enum neighbor_char(NEIGHBOR_NOT_CHAR
/NEIGHBOR_FOUND
/NEIGHBOR_WRAPPED
)の結果を受け取っています。
次の文字が見つかり、かつ元の文字と同じタイプであればNEIGHBOR_FOUND
を返し、次の文字が同じタイプでない(=ラップが生じた)であればNEIGHBOR_WRAPPED
を、無効な文字であればNEIGHBOR_NOT_CHAR
を返しているみたいです。
「次の文字」の決め方はenc_succ_char
関数を見ないと分からなかった。
/* overwrite +p+ by succeeding letter in +enc+ and returns NEIGHBOR_FOUND or NEIGHBOR_WRAPPED. When NEIGHBOR_WRAPPED, carried-out letter is stored into carry. assuming each ranges are successive, and mbclen never change in each ranges. NEIGHBOR_NOT_CHAR is returned if invalid character or the range has only one character. */ static enum neighbor_char enc_succ_alnum_char(char *p, long len, rb_encoding *enc, char *carry) { enum neighbor_char ret; unsigned int c; int ctype; int range; char save[ONIGENC_CODE_TO_MBC_MAXLEN]; /* skip 03A2, invalid char between GREEK CAPITAL LETTERS */ int try; const int max_gaps = 1; c = rb_enc_mbc_to_codepoint(p, p+len, enc); if (rb_enc_isctype(c, ONIGENC_CTYPE_DIGIT, enc)) ctype = ONIGENC_CTYPE_DIGIT; else if (rb_enc_isctype(c, ONIGENC_CTYPE_ALPHA, enc)) ctype = ONIGENC_CTYPE_ALPHA; else return NEIGHBOR_NOT_CHAR; MEMCPY(save, p, char, len); for (try = 0; try <= max_gaps; ++try) { ret = enc_succ_char(p, len, enc); if (ret == NEIGHBOR_FOUND) { c = rb_enc_mbc_to_codepoint(p, p+len, enc); if (rb_enc_isctype(c, ctype, enc)) return NEIGHBOR_FOUND; } } MEMCPY(p, save, char, len); range = 1; while (1) { MEMCPY(save, p, char, len); ret = enc_pred_char(p, len, enc); if (ret == NEIGHBOR_FOUND) { c = rb_enc_mbc_to_codepoint(p, p+len, enc); if (!rb_enc_isctype(c, ctype, enc)) { MEMCPY(p, save, char, len); break; } } else { MEMCPY(p, save, char, len); break; } range++; } if (range == 1) { return NEIGHBOR_NOT_CHAR; } if (ctype != ONIGENC_CTYPE_DIGIT) { MEMCPY(carry, p, char, len); return NEIGHBOR_WRAPPED; } MEMCPY(carry, p, char, len); enc_succ_char(carry, len, enc); return NEIGHBOR_WRAPPED; }
⑤ enc_succ_char 関数
現在の文字を指すポインタと、文字列の長さ、エンコーディングを入力として、neighbor_char
の enum(NEIGHBOR_NOT_CHAR
/NEIGHBOR_FOUND
/NEIGHBOR_WRAPPED
)を返しています。
マルチバイト文字を含むエンコーディング(rb_enc_mbminlen(enc) > 1
が true )のときは、有効な文字列かどうかをチェックのうえ、
c = rb_enc_mbc_to_codepoint(p, p + len, enc) + 1;
によって「コードポイントに 1 を加算する」ことで次の文字を求めていました。
コードポイントは、文字ごとに割り当てられた番号のこと。(Code point (コードポイント) | MDN)
シングルバイト文字のみのエンコーディングのときは、
++((unsigned char*)p)[i];
の箇所でインクリメントを実行しています。
static enum neighbor_char enc_succ_char(char *p, long len, rb_encoding *enc) { long i; int l; if (rb_enc_mbminlen(enc) > 1) { /* wchar, trivial case */ int r = rb_enc_precise_mbclen(p, p + len, enc), c; if (!MBCLEN_CHARFOUND_P(r)) { return NEIGHBOR_NOT_CHAR; } c = rb_enc_mbc_to_codepoint(p, p + len, enc) + 1; l = rb_enc_code_to_mbclen(c, enc); if (!l) return NEIGHBOR_NOT_CHAR; if (l != len) return NEIGHBOR_WRAPPED; rb_enc_mbcput(c, p, enc); r = rb_enc_precise_mbclen(p, p + len, enc); if (!MBCLEN_CHARFOUND_P(r)) { return NEIGHBOR_NOT_CHAR; } return NEIGHBOR_FOUND; } while (1) { for (i = len-1; 0 <= i && (unsigned char)p[i] == 0xff; i--) p[i] = '\0'; if (i < 0) return NEIGHBOR_WRAPPED; ++((unsigned char*)p)[i]; l = rb_enc_precise_mbclen(p, p+len, enc); if (MBCLEN_CHARFOUND_P(l)) { l = MBCLEN_CHARFOUND_LEN(l); if (l == len) { return NEIGHBOR_FOUND; } else { memset(p+l, 0xff, len-l); } } if (MBCLEN_INVALID_P(l) && i < len-1) { long len2; int l2; for (len2 = len-1; 0 < len2; len2--) { l2 = rb_enc_precise_mbclen(p, p+len2, enc); if (!MBCLEN_INVALID_P(l2)) break; } memset(p+len2+1, 0xff, len-(len2+1)); } } }
実装を読んでのまとめ
知りたいこととして最初に掲げた「『次の文字』とは何か」は、「文字コードの数字を 1 進めた」文字のことでした。
とはいえ単純に +1 すれば終わるという話ではなく、
といった考慮のうえで実現されていることも分かりました。
irbで確認
String#succ が、文字コードの数字を 1 進めることによって次の文字を取得している様子を、irb で確認してみました。
エンコーディングは UTF-8 です。
漢字
漢字でも、ちゃんと 171581 → 171582 にインクリメントされています。
> "𩸽".codepoints => [171581] > "𩸽".succ => "𩸾" > "𩸾".codepoints => [171582]
絵文字
家族の絵文字って、複数の文字の組み合わせとして実現されているんですね。
この絵文字も、succ を実行すると一番右の文字コードが 1 進んでいます。
(向かって右下の子供が変わっています)
> "👨👩👧👦".succ => "👨👩👧👧" > "👨👩👧👦".codepoints => [128104, 8205, 128105, 8205, 128103, 8205, 128102] > "👨👩👧👧".codepoints => [128104, 8205, 128105, 8205, 128103, 8205, 128103]
おわりに
Ruby Silver 試験の役立ったかは分かりませんが、面白かったです。
正直ちゃんと隅々理解しようと思うとハードルが高くて難しかったのですが、ざっくり処理を見てみるくらいなら意外と気軽にできるんだな〜と思ってもらえれば幸いです。