この文章は東大工学部電気電子工学科・電子情報工学科(通称eeic)の3年後期実験の科目の1つである大規模ソフトウェアを手探る のレポートとして書かれたものです.実験の内容は端的に述べると10日間の実験期間で大規模なOSSを選び何らかの機能実装を試みるというもので,今回我々の班ではRubyの処理系であるCRuby, mrubyを手探りました.いくつかの機能の新規実装・改善を行いそのうち一部については実際にPull Requestを出しmergeをしていただけましたので,その一部始終を以下に記します.
Rubyの処理系の一つであり,組込み向けに処理系のサイズや速度が最適化されているのが特徴です.CとRubyを用いて実装されており,CRubyと同様にMatzを中心にメンテがなされています.Rubyの言語仕様のうちJIS規格準拠のものをcoreとして実装しており,その他の機能は拡張という形で実装されています.とはいえ組み込み向けであるので拡張にすら移植されていないRuby(CRuby)の機能も多く存在します.以下のリポジトリで管理されています.
https://github.com/mruby/mruby
環境
基本的なビルドツール,bisonなどのパーサージェネレータの他にRubyが必要です
ビルドは以下で行うことができます.
ドキュメントの生成に時間がかかるため--disable-install-doc
にてこれを無効にします.また,optflagsを-O0
としてあげることで最適化を無効にしデバッグをやりやすいようにします.gdbを用いた具体的なデバッグの方法の例は https://techlife.cookpad.com/entry/2015/12/09/163746 などが詳しいです.
以下でテストを実行することができます
基本的には以下にまとめられています.
https://github.com/mruby/mruby/blob/master/doc/guides/compile.md
ビルドにはCRubyと同じく基本的なビルドツール,bisonの他にRubyが必要です.
以下のコマンドでビルドができます
また,以下でテストの実行ができます
Rubyには 数字・文字などの範囲を表す Range と呼ばれる class があります.詳しくは以下のドキュメントをご参照下さい.
https://docs.ruby-lang.org/ja/latest/class/Range.html
このRangeについて,Ruby 2.6から終端にnilを許容する endless range,Ruby 2.7から始端にnilを許容する beginless range が導入されていました.
mrubyのIssueを眺めていたところ,このendless/beginless range をmrubyでも実装してほしいというIssueが出ており,それに対してMatzが「優先度は低いけどそのうちやる」という返答をしていることを確認しました.
https://github.com/mruby/mruby/issues/5085
そこで,とりあえず小手調べとしてmruby にこの endless range を追加してみようという方針で実装しPRを投げることにしました.
以下実装時に加えた主な変更点についていくつか解説します.コード見たほうが話が早いぜという方は以下をご参照を下さい.
https://github.com/mruby/mruby/pull/5093
CRubyにおいて endless rangeは Range.new(1, nil)
のように終端がnilであるrangeとして扱われます.これは1..nil
のように範囲式で書くことができ,さらに糖衣構文としてnilを省略した1..
も許容されています.この終端のnilを省略した記法を受け入れるためにparserを変更しました.
Integerの場合とStringの場合について.このうち,("a"..).each{}
CRubyは全てCで実装されており,通常の String#upto
のロジックに相当するrb_str_upto_each
とは別にendless用にrb_str_upto_endless_each
という関数を用意するような実装になっています. このうちメソッドとして公開されているのはrb_str_upto_each
のみであり,rb_str_upto_endless_each
はメソッドとして公開されていません.
一方mrubyは処理系の核となる部分はCで実装されているのに対し,いくつかのメソッドについてはrubyのオープンクラスを利用する形でrubyで書かかれています.String#upto
,およびそれを呼び出す Range#each
もrubyで実装されていました.ここにendless range用のuptoを既存のString#upto
と同じく例えばString#upto_endless
のようにRubyで実装するとこれも上記の理由から言語の利用者側も触れられるメソッドになってしまします.しかし,このメソッドはRangeから使えなければいけません.この問題について以下の4つの方策を検討しました.
String#upto
の第一引数endに nil
を渡すことを許容する
Range#each
内でStringにパッチをあてるなりしてupto_endlessを生やす / 黒魔術を使う
ここで,mrubyの他のコードを眺めていると__sub_replace@string.rb
のように __
prefixつきのメソッドを事実上privateとして実装しているものを発見しました.そこで,ひとまずはこの慣習と覚しきものを踏襲すべくString#__upto_endless
を実装し,PR時に相談することにしました.
#[](slice)
, #[]=
の第一引数として用いられる場合の実装Range オブジェクトは 例えば"Ruby"[1..3] => "uby"
のように,
#[]
, #[]=
の引数として渡すことができます.(詳しくは https://docs.ruby-lang.org/ja/latest/method/String/i/=5b=5d.html , https://docs.ruby-lang.org/ja/latest/method/String/i/=5b=5d.html などをご参照下さい.)この時,mrubyの実装ではmrb_range_beg_lenという関数が呼ばれます.これは与えられたrangeについて負数("hoge"[1..-1] == "oge"
) や末端を含んでいるかどうか(...
, ..
の違い)を考慮しつつ始端begpと始端から幾つ分だけ辿ればいいかを表す長さlenpを返す関数になっており,#[]
, #[]=
はこの情報を用いてどの範囲をsliceすべきかを判断しています.今回のendless rengeの場合については終端が-1であるrangeと考えて処理してあげれば良さそうです.
https://github.com/mruby/mruby/blob/bec4d053400c3a11c8efd68c3e8bd5ea4a0bcc54/src/range.c#L386
元々のJIS規格では Range#last
は Range#end
のaliasで(15.2.14.4.10) mrubyのcoreでは実際そのような挙動になっています.一方でmrubyにおいて規格に沿わない機能はmrubyの拡張として実装するのが基本になっており,実際mrubyのextensionではRange#lastは再定義されていてより現状のRubyに沿うようになっています(具体的には引数が取れるようになっている等).CRubyにおいてendless rangeの場合Range#end
はnilを返却するのに対し,Range#last
は raise をするという挙動になっているため,これらを上記に従いmrubyのcoreではRange#last
, Range#end
ともにnilを返しextensionではRange#last
はraiseをするような実装をしました.
Range#size
はCRubyにおいてendlessの場合 Float::Infinity
を返す
('a'..'z').size # => nil
)Range#max
, Range#last
についてはCRubyに従いendless rangeの場合はraiseするようにしました(上述の通り#lastはextのみ)
#to_a
はendless rangeの場合はできないのでraiseするようにしました
Range#min
について,引数なしで呼び出された場合は始端を返せば良いが独自の比較用のblockが渡された場合はRangeErrorをraiseするようにするようにしました
各メソッドについてCRubyと挙動を一つ一つ確認しつつ書きました.
endless rangeを実装する上で見つけた既存の問題点について,endless rangeが実装される前にmergeしてほしいものについては先にPRを作成しました.
https://github.com/mruby/mruby/pull/5089
https://github.com/mruby/mruby/pull/5090
https://github.com/mruby/mruby/pull/5091
この3件は全て速攻mergeしていただけました.
その上で,万を持して以下のPRを作成しました.
https://github.com/mruby/mruby/pull/5093
直ぐにmruby 3.0.0へのアップデート作業が終わったらmergeするとの返答をいただき,その2日後にめでたくmergeしていただけました.
Ruby の Range には,範囲内に引数の値が存在するかどうかを判定する Range#include? というメソッドがあります.
これが特定のケースのとき遅くなるような実装がされているのを発見しました.
これが起きる原因は,文字列の範囲の特殊さにあります.
Ruby における文字列の範囲の扱いは,メソッドにもよりますが,Range#include? をはじめ大抵の場合は単なる文字列の辞書順ではありません.始点となる文字列から始めて,その次の文字列,その次の文字列,……というような順序関係の列を作るメソッド String#upto によって定められます.そしてこの「ある文字列の次の文字列」は String#succ というメソッドによって決められます.この String#succ が厄介で,具体的な例を挙げると
のような挙動をします.マルチバイト文字になるともっと厄介です.
このような非自明な順序関係からなる列の中に含まれるかを判定するのは難しいため,文字列のRange#include? はごく簡単なケース(始端終端が1文字かつASCIIのとき)を除いて内部で String#upto に相当する関数であるrb_str_upto_each
を呼び出し(L4535@string.c),さらにこれは一回一回 String#succ を呼び出して実際の列をたどっている,というのが上の問題の原因でした.
Range#include?
にて始端終端が文字列の場合に呼び出される関数rb_str_include_range_p
の実装.特殊ケースを除いてL4535でrb_str_upto_each
を呼び出していることが分かる.rb_str_upto_each
関数の実装の一部.L4451でsuccを呼び出してcurrentを進めつつループを回していることがわかる.ちなみにこの方法では文字列の長さに対して指数関数的に最悪探索時間が増加するため,本当に効率の悪い方法であることがわかります.
この String#succ の奇妙さに起因する問題は他にもあります.
例えば以下の range を配列化すると不思議な結果になります.
これは上述した通りある文字からある文字への到達可能性がString#succの複雑さにより簡単に判別できないためとりあえずrb_str_upto_each
を使い始端から#succを辿ろうという実装になっているからです.rb_str_upto_each
の実装の該当箇所を以下に示します."あ"はUTF-8において3byteですから,始端の"a" から順にsuccで辿っていき,"zzz".succ == "aaaa"
と4byteになる直前でL4457に引っかかりループを抜けるといった具合です.(もし始端がsuccを辿って終端に到達できるのであればL4456でループを抜けるでしょう.)
また,以下のように始端から終端までつながっているはずの range を配列化すると空になります.
同じrangeについて,始端から到達可能であるはずなのに到達可能でないような判定がされます.
"b"からはsuccを辿ってそれぞれ, "z", "aa"にたどり着くことができます.実際,25.times.reduce("b"){|c|c.succ} #=> "aa"
です.この誤判定の原因は先程示したrb_str_upto_each
内のL4443-4444の辞書順比較の判定によるもので,本来であれば"b".."a"のようなrangeについてのイテレーションを受け付けないようにするための処理(と考えられるもの)です.
さらに,以下のような場合始端から到達可能でないはずなのに到達可能であるような判定がされます.
endless rangeについてはそもそもrb_str_upto_each
を呼んでsuccで辿ろうにも仮に始端からsuccで引数で与えた文字に到達できなかった場合処理が停止しなくなってしまいます.そこでこれについても同様に辞書順での判定を行っており(L1569~1574),結果上のように誤った判定をしています.
https://github.com/ruby/ruby/blob/9f3adaf5293d6347250df218bad9dcd3cd8da9ba/range.c#L1540
同様の理由でbeginless rangeの場合にも以下のような判定ミスが起こります.
これもL1563~L1568の辞書順判定に起因しています.
これらに関連したissueは既に幾つか上がっていました.
これらの問題をまとめて解決するための方法が,ある文字列からある文字列に String#succ で到達できるかどうかの判定を導入することです.
この到達可能性判定の導入によって,以下が改善されます.
("b".."aa")
のような単純な辞書順比較によって正しく評価されていなかったrangeが正しく評価されるようになる
("b".."aa").to_a => []
になる問題もこれで解決できるRange#include?
String#upto
で全列挙していた実装の代わりに本methodを使うことで判定が高速に行えるようになる ("b".."aa").include?("z")
, ("b"..).include?("aa")
などの辞書順比較を用いていたことによるバグが直るしかしながらマルチバイトまで含めて考えると極めて複雑になるため,上記のissueでも言われていた通りASCIIに絞った対応なら現実的と考えました.
まず String#succ のアルゴリズムを理解するために見る必要があった関数や値は以下の通りです.
str_succ
enc_succ_alnum_char
を使うenc_succ_alnum_char
が巻き戻しを起こした場合,繰り上がりのように振る舞う
enc_succ_alnum_char
によって巻き戻った一番先頭の文字と同じ文字
enc_succ_char
を使うenc_succ_alnum_char
max_gaps
によって定められる.コメントによるとギリシャ文字のための対応らしい)enc_succ_char
enc_pred_char
enc_succ_char
の逆enum neighbor_char
NEIGHBOR_NOT_CHAR
NEIGHBOR_FOUND
NEIGHBOR_WRAPPED
enc_succ_alnum_char
だと「次が文字として無効だったから巻き戻せるところまで巻き戻した」みたいな意味enc_succ_char
だとバイト長が変わったみたいな意味String#succ によって始端の文字がどう変わりうるか追っていくことで,素直に確かめれば文字列の長さの指数関数時間かかる判定を,文字列の長さの線形時間に収めることができます.ただし,上記の String#succ の挙動の複雑さのせいで,ASCIIに絞った対応であるにもかかわらず大量の場合分けが必要となりました.
この到達可能性判定アルゴリズムをRubyで書いたものが以下になります.
上記の到達可能性判定アルゴリズムをascii_str_reachable_p
という関数として実装し,これを用いrb_str_include_range_p
内で始端終端がasciiの場合は到達判定が正確かつ高速にできるように,またrb_str_upto_each
での到達判定を辞書順でなく正確にできるように変更しました.またrange_include_internal
のendless/beginless rangeの判定にこれを用いるように実装しました.
before
after
現在PR準備中です.