---
title: Zuby
disqus: hackmd
---
Zuby: mrubyへのendless rangeの導入とRubyにおける到達可能性判定の追加
===
## 目次
[TOC]
## はじめに
この文章は東大工学部電気電子工学科・電子情報工学科（通称eeic）の3年後期実験の科目の1つである[大規模ソフトウェアを手探る](https://doss.eidos.ic.i.u-tokyo.ac.jp/) のレポートとして書かれたものです．実験の内容は端的に述べると10日間の実験期間で大規模なOSSを選び何らかの機能実装を試みるというもので，今回我々の班ではRubyの処理系であるCRuby, mrubyを手探りました．いくつかの機能の新規実装・改善を行いそのうち一部については実際にPull Requestを出しmergeをしていただけましたので，その一部始終を以下に記します．
## mrubyについて
Rubyの処理系の一つであり，組込み向けに処理系のサイズや速度が最適化されているのが特徴です．CとRubyを用いて実装されており，CRubyと同様にMatzを中心にメンテがなされています．Rubyの言語仕様のうち[JIS規格](https://kikakurui.com/x3/X3017-2013-01.html)準拠のものをcoreとして実装しており，その他の機能は拡張という形で実装されています．とはいえ組み込み向けであるので拡張にすら移植されていないRuby(CRuby)の機能も多く存在します．以下のリポジトリで管理されています．
https://github.com/mruby/mruby
## Ruby, mrubyのビルド方法
環境
- Ubuntu 20.04
### CRuby
基本的なビルドツール，bisonなどのパーサージェネレータの他にRubyが必要です
```
$ sudo apt-get install build-essential ruby
```
ビルドは以下で行うことができます．
```
$ git clone https://github.com/ruby/ruby
$ cd ruby
$ autoconf
$ ./configure optflags="-O0" --disable-install-doc
$ make -j4
```
ドキュメントの生成に時間がかかるため`--disable-install-doc`にてこれを無効にします．また，optflagsを`-O0`としてあげることで最適化を無効にしデバッグをやりやすいようにします．gdbを用いた具体的なデバッグの方法の例は https://techlife.cookpad.com/entry/2015/12/09/163746 などが詳しいです．
以下でテストを実行することができます
```
$ make test
```
### mruby
基本的には以下にまとめられています．
https://github.com/mruby/mruby/blob/master/doc/guides/compile.md
ビルドにはCRubyと同じく基本的なビルドツール，bisonの他にRubyが必要です．
以下のコマンドでビルドができます
```
$ rake
```
また，以下でテストの実行ができます
```
$ rake test
```
## ①mrubyへのendless rangeの導入
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
### Parserの変更
CRubyにおいて endless rangeは `Range.new(1, nil)` のように終端がnilであるrangeとして扱われます．これは`1..nil` のように範囲式で書くことができ，さらに糖衣構文としてnilを省略した`1..`も許容されています．この終端のnilを省略した記法を受け入れるためにparserを変更しました．
https://github.com/zubycz/mruby/blob/bec4d053400c3a11c8efd68c3e8bd5ea4a0bcc54/mrbgems/mruby-compiler/core/parse.y#L2117
### Rangeの諸メソッドにおけるendlessの場合の挙動の実装
#### Range#each
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つの方策を検討しました．
- Ruby実装でStringクラスにendless range用のメソッドを新たに用意する
- 隠蔽ができない
- `String#upto` の第一引数endに `nil` を渡すことを許容する
- 本家と挙動が異なってしまう / 元々のuptoインターフェースを破壊してしまう
- `Range#each` 内でStringにパッチをあてるなりしてupto_endlessを生やす / 黒魔術を使う
- String#upto は拡張として切り分けられているのににも関わらず比較的量の多い / 汚い実装をcore入れてしまうのはいただけない（と思う）
- C言語側で実装する
- Ruby側から使うにはメソッドなりなんなりで登録する必要があり結局隠蔽ができない．
ここで，mrubyの他のコードを眺めていると`__sub_replace@string.rb` のように `__` prefixつきのメソッドを事実上privateとして実装しているものを発見しました．そこで，ひとまずはこの慣習と覚しきものを踏襲すべく`String#__upto_endless`を実装し，PR時に相談することにしました．
#### String, Arrayの`#[](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
```ruby
[1, 2, 3][1..] # =>[2, 3]
```
#### Range#last, Range#end
元々の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` を返す
- https://github.com/ruby/ruby/commit/342619300ce26f9a134249002270c5d38d5993b3
ところが，mrubyにはFPUが無い組み込み環境向けにMRB_WITHOUT_FLOATというFloatを使わないビルドオプションが存在します．この場合何を返すべきか．
とりあえずPR時に相談することにしました．
また，始終端がNumericじゃない場合はCRubyに従いnilを返すようにしました(`('a'..'z').size # => nil`)
- `Range#max`, `Range#last` についてはCRubyに従いendless rangeの場合はraiseするようにしました(上述の通り#lastはextのみ)
- https://github.com/ruby/ruby/commit/cae45174190b49ca3c67ca606c5f4b71e3847842
- `#to_a` はendless rangeの場合はできないのでraiseするようにしました
- https://github.com/ruby/ruby/commit/c19ecf05b4c728951e1a1e223a40ae6883a4f8e0
- `Range#min` について，引数なしで呼び出された場合は始端を返せば良いが独自の比較用のblockが渡された場合はRangeErrorをraiseするようにするようにしました
- https://github.com/ruby/ruby/commit/db1bdecb0d925b4668c0735158fce466333848f1
- その他のメソッドについても必要に応じて修正変更をしました．
### テストを書く
各メソッドについてCRubyと挙動を一つ一つ確認しつつ書きました．
### PR, merge
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への到達可能性判定の導入
### 文字列の範囲の諸問題
Ruby の Range には，範囲内に引数の値が存在するかどうかを判定する Range#include? というメソッドがあります．
```ruby
("a".."z").include?("s") #=> true
("0".."100").include?("101") #=> false
```
これが特定のケースのとき遅くなるような実装がされているのを発見しました．
```bash
$ time ruby -e '("a".."zzzzz").include?("zzzzz")'
ruby -e '("a".."zzzzz").include?("zzzzz")' 2.19s user 0.10s system 89% cpu 2.543 total
```
これが起きる原因は，文字列の範囲の特殊さにあります．
Ruby における文字列の範囲の扱いは，メソッドにもよりますが，Range#include? をはじめ大抵の場合は単なる文字列の辞書順ではありません．始点となる文字列から始めて，その次の文字列，その次の文字列，……というような順序関係の列を作るメソッド String#upto によって定められます．そしてこの「ある文字列の次の文字列」は String#succ というメソッドによって決められます．この String#succ が厄介で，具体的な例を挙げると
```ruby
"a".succ == "b"
"WA".succ == "WB"
"0".succ == "1"
"z".succ == "aa"
"99".succ == "100"
"1.9.9".succ == "2.0.0"
"HOGE9".succ == "HOGF0"
"$$$".succ == "$$%"
"##zz99##zz99##99##".succ == "##zz99##aaa00##00##"
```
のような挙動をします．マルチバイト文字になるともっと厄介です．
このような非自明な順序関係からなる列の中に含まれるかを判定するのは難しいため，文字列の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`を呼び出していることが分かる．
https://github.com/ruby/ruby/blob/539b89075a61f27c8b5b5cd749f66bda47bc78b0/string.c#L4517
```Ruby=4517
VALUE
rb_str_include_range_p(VALUE beg, VALUE end, VALUE val, VALUE exclusive)
{
beg = rb_str_new_frozen(beg);
StringValue(end);
end = rb_str_new_frozen(end);
if (NIL_P(val)) return Qfalse;
val = rb_check_string_type(val);
if (NIL_P(val)) return Qfalse;
if (rb_enc_asciicompat(STR_ENC_GET(beg)) &&
rb_enc_asciicompat(STR_ENC_GET(end)) &&
rb_enc_asciicompat(STR_ENC_GET(val))) {
const char *bp = RSTRING_PTR(beg);
const char *ep = RSTRING_PTR(end);
const char *vp = RSTRING_PTR(val);
if (RSTRING_LEN(beg) == 1 && RSTRING_LEN(end) == 1) {
(snip) // 両端が1文字のasciiである場合の処理
}
rb_str_upto_each(beg, end, RTEST(exclusive), include_range_i, (VALUE)&val);
return NIL_P(val) ? Qtrue : Qfalse;
}
```
- `rb_str_upto_each` 関数の実装の一部．L4451でsuccを呼び出してcurrentを進めつつループを回していることがわかる．
https://github.com/ruby/ruby/blob/539b89075a61f27c8b5b5cd749f66bda47bc78b0/string.c#L4443
```ruby=4443
n = rb_str_cmp(beg, end);
if (n > 0 || (excl && n == 0)) return beg;
after_end = rb_funcallv(end, succ, 0, 0);
current = rb_str_dup(beg);
while (!rb_str_equal(current, after_end)) {
VALUE next = Qnil;
if (excl || !rb_str_equal(current, end))
next = rb_funcallv(current, succ, 0, 0);
if ((*each)(current, arg)) break;
if (NIL_P(next)) break;
current = next;
StringValue(current);
if (excl && rb_str_equal(current, end)) break;
if (RSTRING_LEN(current) > RSTRING_LEN(end) || RSTRING_LEN(current) == 0)
break;
}
```
ちなみにこの方法では文字列の長さに対して指数関数的に最悪探索時間が増加するため，本当に効率の悪い方法であることがわかります．
この String#succ の奇妙さに起因する問題は他にもあります．
例えば以下の range を配列化すると不思議な結果になります．
```ruby
("a".."あ").to_a #=> ["a", ... , "zzy", "zzz"]
```
これは上述した通りある文字からある文字への到達可能性がString#succの複雑さにより簡単に判別できないためとりあえず`rb_str_upto_each`を使い始端から#succを辿ろうという実装になっているからです．`rb_str_upto_each`の実装の該当箇所を以下に示します．"あ"はUTF-8において3byteですから，始端の"a" から順にsuccで辿っていき，`"zzz".succ == "aaaa"` と4byteになる直前でL4457に引っかかりループを抜けるといった具合です．（もし始端がsuccを辿って終端に到達できるのであればL4456でループを抜けるでしょう．）
また，以下のように始端から終端までつながっているはずの range を配列化すると空になります．
```ruby
("b".."aa").to_a #=> []
```
同じrangeについて，始端から到達可能であるはずなのに到達可能でないような判定がされます．
```ruby
("b".."aa").include?("z") #=> false
```
"b"からはsuccを辿ってそれぞれ, "z", "aa"にたどり着くことができます．実際，`25.times.reduce("b"){|c|c.succ} #=> "aa"`です．この誤判定の原因は先程示した`rb_str_upto_each`内のL4443-4444の辞書順比較の判定によるもので，本来であれば"b".."a"のようなrangeについてのイテレーションを受け付けないようにするための処理（と考えられるもの）です．
さらに，以下のような場合始端から到達可能でないはずなのに到達可能であるような判定がされます．
```ruby
("aa"..).include?("b") #=> true
```
endless rangeについてはそもそも`rb_str_upto_each` を呼んでsuccで辿ろうにも仮に始端からsuccで引数で与えた文字に到達できなかった場合処理が停止しなくなってしまいます．そこでこれについても同様に辞書順での判定を行っており(L1569~1574)，結果上のように誤った判定をしています．
https://github.com/ruby/ruby/blob/9f3adaf5293d6347250df218bad9dcd3cd8da9ba/range.c#L1540
```ruby=1540
static VALUE
range_include_internal(VALUE range, VALUE val, int string_use_cover)
{
VALUE beg = RANGE_BEG(range);
VALUE end = RANGE_END(range);
int nv = FIXNUM_P(beg) || FIXNUM_P(end) ||
linear_object_p(beg) || linear_object_p(end);
if (nv ||
!NIL_P(rb_check_to_integer(beg, "to_int")) ||
!NIL_P(rb_check_to_integer(end, "to_int"))) {
return r_cover_p(range, beg, end, val);
}
else if (RB_TYPE_P(beg, T_STRING) || RB_TYPE_P(end, T_STRING)) {
if (RB_TYPE_P(beg, T_STRING) && RB_TYPE_P(end, T_STRING)) {
if (string_use_cover) {
return r_cover_p(range, beg, end, val);
}
else {
VALUE rb_str_include_range_p(VALUE beg, VALUE end, VALUE val, VALUE exclusive);
return rb_str_include_range_p(beg, end, val, RANGE_EXCL(range));
}
}
else if (NIL_P(beg)) {
VALUE r = rb_funcall(val, id_cmp, 1, end);
if (NIL_P(r)) return Qfalse;
if (rb_cmpint(r, val, end) <= 0) return Qtrue;
return Qfalse;
}
else if (NIL_P(end)) {
VALUE r = rb_funcall(beg, id_cmp, 1, val);
if (NIL_P(r)) return Qfalse;
if (rb_cmpint(r, beg, val) <= 0) return Qtrue;
return Qfalse;
}
}
return Qundef;
}
```
同様の理由でbeginless rangeの場合にも以下のような判定ミスが起こります．
```ruby
> (.."aa").include?("b") #=> false
```
これもL1563~L1568の辞書順判定に起因しています．
これらに関連したissueは既に幾つか上がっていました．
- [Feature #2323: "Z".."Z".succが空](https://bugs.ruby-lang.org/issues/5607)
- [Feature #5607: Inconsistent reaction in Range of String](https://bugs.ruby-lang.org/issues/2323)
### 解決策の導入
これらの問題をまとめて解決するための方法が，ある文字列からある文字列に 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のアルゴリズム
まず String#succ のアルゴリズムを理解するために見る必要があった関数や値は以下の通りです．
- 文字種
- 文字ごとに alpha, digit, その他という属性が備わっている
- alpha と digit をまとめて alnum と呼ぶ
- この判定は，Unicode Character Properties に基づくと思われる
- `str_succ`
- 末尾の文字から順に見ていき alnum が存在すればそこをコードポイント上の次の文字にする
- 次の文字にするのは `enc_succ_alnum_char` を使う
- `enc_succ_alnum_char` が巻き戻しを起こした場合，繰り上がりのように振る舞う
- 一個前の alnum を次の文字にする
- ただし繰り上がろうとして壁まで来てしまったら文字を前方向に伸ばす．壁になりうるのは
- 文字列の先頭
- alpha と digit が異なるものに挟まれている非 alnum
- 逆に壁にならないのは
- 隣り合っている alnum
- alpha 同士，digit 同士に挟まれている非 alnum
- 伸ばすときに付け足されるのは，`enc_succ_alnum_char` によって巻き戻った一番先頭の文字と同じ文字
- だが，digit のときはその次の文字（"9" の次が "00" ではなく "10" になるようにするため）
- 一個も alnum がなかったら，単に文字として似たことをやる
- `enc_succ_char` を使う
- `enc_succ_alnum_char`
- alpha なら次が alpha であれば，digit なら次が digit であれば進める
- コードポイント上の非 alnum を1回までなら超えられる（この回数は `max_gaps` によって定められる．コメントによるとギリシャ文字のための対応らしい）
- だめならコードポイント上で巻き戻れるだけ巻き戻す（巻き戻しは非 alnum を超えられない）
- `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で書いたものが以下になります．
```ruby=
ASCII = /[[:ascii:]]/
ALNUM = /[[:alnum:]]/
ALPHA = /[[:alpha:]]/
UPPER = /[[:upper:]]/
LOWER = /[[:lower:]]/
DIGIT = /[[:digit:]]/
def ascii_str_reachable?(a, b)
raise unless a.ascii_only?
raise unless b.ascii_only?
return true if a == "" && b == ""
return false if a == "" || b == ""
# succ によって文字数が減ることはないので弾ける
return false if a.size > b.size
# assert a.size <= b.size
# 参考: string.c str_succ L4241-L4264
# 後ろから見ていき，任意回の succ によって変更されうる始点を見つける
# 非 alnum を超えるには {digit / alpha} が一致している必要がある ...(1)
last_alnum_index = nil
neighbor_is_alnum = true
i = a.size - 1
while i >= 0
if !neighbor_is_alnum && last_alnum_index
case a[i]
when DIGIT
break if a[last_alnum_index] =~ ALPHA
when ALPHA
break if a[last_alnum_index] =~ DIGIT
end
end
if a[i] =~ ALNUM
last_alnum_index = i
neighbor_is_alnum = true
else
neighbor_is_alnum = false
end
i -= 1
end
if last_alnum_index
# last_alnum_index より以前は変化しないので一致している必要がある
for i in 0...last_alnum_index
return false if a[i] != b[i]
end
# 後ろから見て {digit / upper / lower / else} が一致している必要がある
# else なら文字自体が一致している必要がある
# b の超過分については a[last_alnum_index] のものと一致している必要がある ...(2)
# （ルール(1)と(2)によって，任意回の succ をしても last_alnum_index の位置が変わらないことが言える）
i = a.size - 1
j = b.size - 1
prepend = false
while j >= last_alnum_index
case a[i]
when DIGIT
return false if b[j] !~ DIGIT
return false if prepend && b[j] == "0"
when UPPER
return false if b[j] !~ UPPER
when LOWER
return false if b[j] !~ LOWER
else
return false if a[i] != b[j]
end
if i > last_alnum_index
i -= 1
else
prepend = true
end
j -= 1
end
# あとは普通の自然数の大小比較と同じ
case
when a.size < b.size
return true
when a.size == b.size
i = last_alnum_index
while i < a.size
if a[i] =~ ALNUM
case
when a[i] > b[i]
return false
when a[i] < b[i]
return true
end
end
i += 1
end
return true
end
else
# TODO: alnum を含まない場合
# 参考: string.c str_succ L4265-L4297
# UTF-8の場合は \x7f の次が \x00 になって繰り上がる
# (ASCII-8bitの場合 \x7f.succ == \x80)
# 十分な回数やると alnum ありにたどり着く
# a[-1] を succ していき，
# - '0', 'A', 'a' に突入するパターン
# - 突入するまでに b と一致するパターン
# - 突入し，繰り上がりが起こるなどして b と一致するパターン
# - '\x7f' を超えるパターン
# - 超えるまでに b と一致するパターン
# - 繰り上がって a[-1] 自身が '0' に突入するパターン
# - 突入するまでに b と一致するパターン
# - 突入し，繰り上がりが起こるなどして b と一致するパターン
# - 繰り上げられた文字が '0', 'A', 'a' に突入するパターン
# - 繰り上がって先頭に '\x01' がつき a[-1] が '0' に突入するパターン
# - 突入するまでに b と一致するパターン
# - 突入し，繰り上がりが起こるなどして b と一致するパターン
# [wrap_start, wrap_end) ... a[-1] から到達しうる ['0', '9'), ['A', 'Z'), ['a', 'z'), ['\x80', ) などの区間
# [carry_pos, carry_pos + carry_len) ... a から succ していって alnum を含み始めたとき b のどの部分に含みうるか
wrap_start = nil
wrap_end = nil
carry_pos = nil
carry_len = nil
ch = a[-1].ord
ch += 1 while ch.chr =~ ASCII && ch.chr !~ ALNUM
wrap_start = ch.chr
if wrap_start =~ ASCII
return false if a[...(a.size - 1)] != b[...(a.size - 1)]
return true if a.size == b.size && a[-1] <= b[-1] && b[-1] <= wrap_start
carry_pos = a.size - 1
carry_len = b.size - carry_pos
else
return true if a.size == b.size && a[...(a.size - 1)] != b[...(a.size - 1)] && a[-1] <= b[-1] && b[-1] < wrap_start
carry_pos = a.size - 2
carry_pos -= 1 while carry_pos >= 0 && (a[carry_pos].ord + 1).chr !~ ASCII
if carry_pos >= 0
return false if a[...carry_pos] != b[...carry_pos]
if (a[carry_pos].ord + 1).chr !~ ALNUM
return false if (a[carry_pos].ord + 1).chr != b[carry_pos]
for j in (carry_pos + 1)...(a.size - 1)
return false if b[j] != "\0"
end
ch = "\0".ord
ch += 1 while ch.chr !~ ALNUM
wrap_start = ch.chr
return true if a.size == b.size && b[-1] < wrap_start
carry_pos = a.size - 1
carry_len = b.size - carry_pos
else
wrap_start = (a[carry_pos].ord + 1).chr
carry_len = 1 + (b.size - a.size)
for j in (carry_pos + carry_len)...b.size
return false if b[j] != "\0"
end
end
else
return false if b[0] != "\x01"
for j in 1...a.size
return false if b[j] != "\0"
end
ch = "\0".ord
ch += 1 while ch.chr !~ ALNUM
wrap_start = ch.chr
return true if a.size + 1 == b.size && b[-1] < wrap_start
carry_pos = a.size
carry_len = b.size - a.size
end
end
ch = wrap_start.ord
ch += 1 while ch.chr =~ ALNUM
wrap_end = ch.chr
if wrap_start =~ DIGIT
return false if carry_len > 1 && b[carry_pos] == wrap_start
end
for j in carry_pos...(carry_pos + carry_len)
return false if b[j] < wrap_start || wrap_end <= b[j]
end
return true
end
end
```
### 結果
上記の到達可能性判定アルゴリズムを`ascii_str_reachable_p`という関数として実装し，これを用い`rb_str_include_range_p` 内で始端終端がasciiの場合は到達判定が正確かつ高速にできるように，また`rb_str_upto_each` での到達判定を辞書順でなく正確にできるように変更しました．また`range_include_internal`のendless/beginless rangeの判定にこれを用いるように実装しました．
<details>
<summary>主要な変更点</summary>
```c
bool
ascii_str_reachable_p(char *a, int alen, char *b, int blen, rb_encoding *enc)
{
int found_alnum = false;
int last_alnum_index = -1;
int neighbor_is_alnum = true;
int prepended = false;
int i, j;
char ch, wrap_start, wrap_end;
int carry_pos, carry_len;
if (alen == 0 && blen == 0) return true;
if (alen == 0 || blen == 0) return false;
if (alen > blen) return false;
for (i = alen - 1; i >= 0; i--) {
if (!neighbor_is_alnum && found_alnum) {
if (ISALPHA(a[last_alnum_index]) ? ISDIGIT(a[i]) :
ISDIGIT(a[last_alnum_index]) ? ISALPHA(a[i]) : 0) {
break;
}
}
if (ISALNUM(a[i])) {
found_alnum = true;
last_alnum_index = i;
neighbor_is_alnum = true;
}
else {
neighbor_is_alnum = false;
}
}
if (found_alnum) {
for (i = 0; i < last_alnum_index; i++) {
if (a[i] != b[i]) return false;
}
for (i = alen - 1, j = blen - 1; j >= last_alnum_index; ) {
if (ISDIGIT(a[i]) ? !ISDIGIT(b[j]) || (prepended && b[j] == '0') :
ISUPPER(a[i]) ? !ISUPPER(b[j]) :
ISLOWER(a[i]) ? !ISLOWER(b[j]) :
a[i] != b[j]) {
return false;
}
if (i > last_alnum_index) i--;
else prepended = true;
j--;
}
if (alen < blen) return true;
for (i = last_alnum_index; i < alen; i++) {
if (ISALNUM(a[i])) {
if (a[i] == b[i]) continue;
else return a[i] < b[i];
}
}
return true;
}
else {
ch = a[alen - 1];
while (ISASCII(ch) && !ISALNUM(ch)) ch++;
wrap_start = ch;
if (ISASCII(wrap_start)) {
if (memcmp(a, b, alen - 1) != 0) return false;
if (alen == blen && a[alen - 1] <= b[blen - 1] && b[blen - 1] < wrap_start) {
return true;
}
carry_pos = alen - 1;
carry_len = blen - carry_pos;
}
else {
if (alen == blen && memcmp(a, b, alen - 1) == 0 && a[alen - 1] <= b[blen - 1]) {
return true;
}
carry_pos = alen - 2;
while (carry_pos >= 0 && !ISASCII(a[carry_pos] + 1)) carry_pos--;
if (carry_pos >= 0) {
if (memcmp(a, b, carry_pos) != 0) return false;
if (!ISALNUM(a[carry_pos] + 1)) {
if (a[carry_pos] + 1 != b[carry_pos]) return false;
for (j = carry_pos + 1; j < alen - 1; j++) {
if (b[j] != '\0') return false;
}
ch = '\0';
while (!ISALNUM(ch)) ch++;
wrap_start = ch;
if (alen == blen && b[blen - 1] < wrap_start) return true;
carry_pos = alen - 1;
carry_len = blen - carry_pos;
}
else {
wrap_start = a[carry_pos] + 1;
carry_len = 1 + (blen - alen);
for (j = carry_pos + carry_len; j < blen ; j++) {
if (b[j] != '\0') return false;
}
}
}
else {
if (b[0] != '\x01') return false;
for (j = 1; j < alen; j++) {
if (b[j] != '\0') return false;
}
ch = '\0';
while (!ISALNUM(ch)) ch++;
wrap_start = ch;
if (alen + 1 == blen && b[blen - 1] < wrap_start) return true;
carry_pos = alen;
carry_len = blen - alen;
}
}
ch = wrap_start;
while (ISALNUM(ch)) ch++;
wrap_end = ch;
if (ISDIGIT(wrap_start)) {
if (carry_len > 1 && b[carry_pos] == wrap_start) return false;
}
for (j = carry_pos; j < carry_pos + carry_len; j++) {
if (b[j] < wrap_start || wrap_end <= b[j]) return false;
}
return true;
}
}
```
```diff
@@ -1505,6 +1505,9 @@ range_include_internal(VALUE range, VALUE val, int string_use_cover)
{
VALUE beg = RANGE_BEG(range);
VALUE end = RANGE_END(range);
+ rb_encoding *enc;
+ bool reachable;
+
int nv = FIXNUM_P(beg) || FIXNUM_P(end) ||
linear_object_p(beg) || linear_object_p(end);
@@ -1524,17 +1527,33 @@ range_include_internal(VALUE range, VALUE val, int string_use_cover)
}
}
else if (NIL_P(beg)) {
- VALUE r = rb_funcall(val, id_cmp, 1, end);
- if (NIL_P(r)) return Qfalse;
- if (rb_cmpint(r, val, end) <= 0) return Qtrue;
- return Qfalse;
+ if (is_ascii_string(val) && is_ascii_string(end)) {
+ enc = rb_enc_check(val, end);
+ reachable = ascii_str_reachable_p(RSTRING_PTR(val), RSTRING_LEN(val), RSTRING_PTR(end), RSTRING_LEN(end), enc);
+ if (EXCL(val)) reachable && !rb_str_equal(val, end)? Qtrue : Qfalse;
+ else return reachable ? Qtrue : Qfalse;
+ }
+ else {
+ VALUE r = rb_funcall(val, id_cmp, 1, end);
+ if (NIL_P(r)) return Qfalse;
+ if (rb_cmpint(r, val, end) <= 0) return Qtrue;
+ return Qfalse;
+ }
+ }
+ else if (NIL_P(end)) {
+ if (is_ascii_string(beg) && is_ascii_string(val)) {
+ enc = rb_enc_check(beg, val);
+ reachable = ascii_str_reachable_p(RSTRING_PTR(beg), RSTRING_LEN(beg), RSTRING_PTR(val), RSTRING_LEN(val), enc);
+ if (EXCL(val)) reachable && !rb_str_equal(beg, end) ? Qtrue : Qfalse;
+ else return reachable ? Qtrue : Qfalse;
+ }
+ else {
+ VALUE r = rb_funcall(beg, id_cmp, 1, val);
+ if (NIL_P(r)) return Qfalse;
+ if (rb_cmpint(r, beg, val) <= 0) return Qtrue;
+ return Qfalse;
+ }
}
- else if (NIL_P(end)) {
- VALUE r = rb_funcall(beg, id_cmp, 1, val);
- if (NIL_P(r)) return Qfalse;
- if (rb_cmpint(r, beg, val) <= 0) return Qtrue;
- return Qfalse;
- }
}
return Qundef;
}
```
```diff
@@ -4440,8 +4556,16 @@ rb_str_upto_each(VALUE beg, VALUE end, int excl, int (*each)(VALUE, VALUE), VALU
return beg;
}
/* normal case */
- n = rb_str_cmp(beg, end);
- if (n > 0 || (excl && n == 0)) return beg;
+ if (ascii && rb_enc_asciicompat(enc)) {
+ if (!ascii_str_reachable_p(RSTRING_PTR(beg), RSTRING_LEN(beg), RSTRING_PTR(end), RSTRING_LEN(end), enc)) {
+ return beg;
+ }
+ if (excl && rb_str_equal(beg, end)) return beg;
+ }
+ else {
+ n = rb_str_cmp(beg, end);
+ if (n > 0 || (excl && n == 0)) return beg;
+ }
after_end = rb_funcallv(end, succ, 0, 0);
current = rb_str_dup(beg);
```diff
@@ -4552,6 +4678,20 @@ rb_str_include_range_p(VALUE beg, VALUE end, VALUE val, VALUE exclusive)
/* TODO */
}
#endif
+ if (is_ascii_string(beg) && is_ascii_string(end) && is_ascii_string(val)) {
+ enc = rb_enc_check_str(beg, val);
+ rb_enc_check_str(val, end);
+ if (!ascii_str_reachable_p(RSTRING_PTR(beg), RSTRING_LEN(beg), RSTRING_PTR(val), RSTRING_LEN(val), enc)) {
+ return Qfalse;
+ }
+ if (!ascii_str_reachable_p(RSTRING_PTR(val), RSTRING_LEN(val), RSTRING_PTR(end), RSTRING_LEN(end), enc)) {
+ return Qfalse;
+ }
+ if (RTEST(exclusive) && rb_str_equal(val, end)) {
+ return Qfalse;
+ }
+ return Qtrue;
+ }
}
```
</details>
before
```ruby
$ time ruby -e '("a".."zzzzz").include?("zzzzz")'
real 0m1.368s
user 0m1.354s
sys 0m0.014s
```
after
```ruby
$ time bin/ruby -e '("a".."zzzzz").include?("zzzzz")'
real 0m0.125s
user 0m0.117s
sys 0m0.008s
```
```ruby
("b".."aa").to_a #=> ["b", "c", ... "z", "aa]
("b".."aa").include?("z") #=> true
("b".."aa").include?("z") #=> true
("aa"..).include?("b") #=> false
```
現在PR準備中です．
## おわりに
Sign in with Wallet
Connect another wallet