Try   HackMD

Zuby: mrubyへのendless rangeの導入とRubyにおける到達可能性判定の追加

目次

はじめに

この文章は東大工学部電気電子工学科・電子情報工学科（通称eeic）の3年後期実験の科目の1つである大規模ソフトウェアを手探る のレポートとして書かれたものです．実験の内容は端的に述べると10日間の実験期間で大規模なOSSを選び何らかの機能実装を試みるというもので，今回我々の班ではRubyの処理系であるCRuby, mrubyを手探りました．いくつかの機能の新規実装・改善を行いそのうち一部については実際にPull Requestを出しmergeをしていただけましたので，その一部始終を以下に記します．

mrubyについて

Rubyの処理系の一つであり，組込み向けに処理系のサイズや速度が最適化されているのが特徴です．CとRubyを用いて実装されており，CRubyと同様にMatzを中心にメンテがなされています．Rubyの言語仕様のうちJIS規格準拠のものを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

[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をするような実装をしました．

その他細かい挙動の実装

テストを書く

各メソッドについて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? というメソッドがあります．

("a".."z").include?("s") #=> true
("0".."100").include?("101") #=> false

これが特定のケースのとき遅くなるような実装がされているのを発見しました．

$ 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 が厄介で，具体的な例を挙げると

"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 を呼び出して実際の列をたどっている，というのが上の問題の原因でした．























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;
}


















    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 を配列化すると不思議な結果になります．

("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 を配列化すると空になります．

("b".."aa").to_a #=> []

同じrangeについて，始端から到達可能であるはずなのに到達可能でないような判定がされます．

("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についてのイテレーションを受け付けないようにするための処理（と考えられるもの）です．

さらに，以下のような場合始端から到達可能でないはずなのに到達可能であるような判定がされます．

("aa"..).include?("b") #=> true

endless rangeについてはそもそもrb_str_upto_each を呼んでsuccで辿ろうにも仮に始端からsuccで引数で与えた文字に到達できなかった場合処理が停止しなくなってしまいます．そこでこれについても同様に辞書順での判定を行っており(L1569~1574)，結果上のように誤った判定をしています．

https://github.com/ruby/ruby/blob/9f3adaf5293d6347250df218bad9dcd3cd8da9ba/range.c#L1540







































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の場合にも以下のような判定ミスが起こります．

> (.."aa").include?("b") #=> false

これも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のアルゴリズム

まず 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で書いたものが以下になります．
























































































































































































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の判定にこれを用いるように実装しました．

主要な変更点 
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;
    }
}

@@ -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;
 }

@@ -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;
+       }
     }

before

$ time ruby -e '("a".."zzzzz").include?("zzzzz")'
real    0m1.368s
user    0m1.354s
sys     0m0.014s

after

$ time bin/ruby -e '("a".."zzzzz").include?("zzzzz")'
real    0m0.125s
user    0m0.117s
sys     0m0.008s

("b".."aa").to_a #=> ["b", "c", ... "z", "aa]
("b".."aa").include?("z") #=> true
("b".."aa").include?("z") #=> true
("aa"..).include?("b") #=> false

現在PR準備中です．

おわりに

Last changed by 
 
Zuby
ずびしいず
0
637

Read more

RubyのString#succに関する小話

&#x3053;&#x306E;&#x8A18;&#x4E8B;&#x306F;eeic &#xFF08;&#x6771;&#x4EAC;&#x5927;&#x5B66;&#x5DE5;&#x5B66;&#x90E8;&#x96FB;&#x6C17;&#x96FB;&#x5B50;&#x30FB;&#x96FB;&#x5B50;&#x60C5;&#x5831;&#x5DE5;&#x5B66;&#x79D1;&#xFF09; Advent Calendar 2020&#xFF0C;&#x53CA;&#x3073;TSG Advent Calendar 2020&#x306E;23&#x65E5;&#x76EE;&#x306E;&#x8A18;&#x4E8B;&#x3067;&#x3059;&#xFF0E; &#x4E88;&#x5B9A;&#x3067;&#x306F;&#x4ECA;&#x590F;&#x53C2;&#x52A0;&#x3055;&#x305B;&#x3066;&#x3044;&#x305F;&#x3060;&#x3044;&#x3066;&#x3044;&#x305F;Yahoo Japan!&#x306E;&#x30A4;&#x30F3;&#x30BF;&#x30FC;&#x30F3;&#x3067;&#x3084;&#x3089;&#x305B;&#x3066;&#x9802;&#x3044;&#x3066;&#x3044;&#x305F;FIDO2&#xFF0C;WebAuthn&#x7B49;&#x306E;&#x8A71;&#x3092;&#x66F8;&#x304F;&#x3064;&#x3082;&#x308A;&#x3067;&#x524D;&#x3005;&#x304B;&#x3089;&#x5C11;&#x3057;&#x305A;&#x3064;&#x6E96;&#x5099;&#x3057;&#x3066;&#x3044;&#x305F;&#x306E;&#x3067;&#x3059;&#x304C;&#xFF0C;&#x60F3;&#x5B9A;&#x5916;&#x306B;&#x5927;&#x4F5C;&#x3068;&#x306A;&#x3063;&#x3066;&#x3057;&#x307E;&#x3044;&#x3069;&#x3046;&#x8003;&#x3048;&#x3066;&#x3082;&#x9593;&#x306B;&#x5408;&#x308F;&#x306A;&#x3053;&#x3068;&#x304C;&#x5224;&#x660E;&#x3057;&#x305F;&#x305F;&#x3081;&#x6025;&#x907D;&#x304A;&#x984C;&#x3092;&#x5909;&#x66F4;&#x3057;&#xFF0C;@n4o847, @smallkirby_ &#x3068;&#x4ECA;&#x5B66;&#x671F;&#x306E;eeic&#x306E;&#x5F8C;&#x671F;&#x5B9F;&#x9A13;&#x306E;1&#x3064;&#x3067;&#x3042;&#x308B;&#x300C;&#x5927;&#x898F;&#x6A21;&#x30BD;&#x30D5;&#x30C8;&#x30A6;&#x30A7;&#x30A2;&#x3092;&#x624B;&#x63A2;&#x308B;&#x300D;&#x306B;&#x3066;&#x53D6;&#x308A;&#x7D44;&#x3093;&#x3060;Ruby&#x306E;&#x5C0F;&#x8A71;&#x3092;&#x3059;&#x308B;&#x3053;&#x3068;&#x306B;&#x3057;&#x307E;&#x3057;&#x305F;&#xFF0E;&#x9045;&#x523B;&#x5927;&#x5909;&#x7533;&#x3057;&#x8A33;&#x3042;&#x308A;&#x307E;&#x305B;&#x3093;&#xFF0E; &#x672C;&#x8A18;&#x4E8B;&#x306B;&#x304A;&#x3051;&#x308B;&#x6319;&#x52D5;&#x3084;&#x4ED5;&#x69D8;&#x306F;Ruby 2.7.2 &#x3067;&#x78BA;&#x8A8D;&#x3057;&#x3066;&#x304A;&#x308A;&#xFF0C;&#x30B3;&#x30FC;&#x30C9;&#x306B;&#x3064;&#x3044;&#x3066;&#x3082;&#x672C;&#x30D0;&#x30FC;&#x30B8;&#x30E7;&#x30F3;&#x306E;&#x3082;&#x306E;&#x3092;&#x53C2;&#x7167;&#x3057;&#x3066;&#x3044;&#x307E;&#x3059;&#xFF0E;https://github.com/ruby/ruby/tree/5445e0435260b449decf2ac16f9d09bae3cafe72 Ruby &#x306B;&#x306F; String#succ&#xFF08;&#x3042;&#x308B;&#x3044;&#x306F;String#next&#xFF09;&#x3068;&#x3044;&#x3046;&#xFF0C;&#x6587;&#x5B57;&#x5217;&#x306E;&#x5F8C;&#x7D99;&#x306E;&#x6587;&#x5B57;&#x5217;&#x3092;&#x8FD4;&#x3059;&#x30E1;&#x30BD;&#x30C3;&#x30C9;&#x304C;&#x3042;&#x308A;&#x307E;&#x3059;&#xFF0E; https://docs.ruby-lang.org/ja/latest/method/String/i/succ.html &#x4F8B;&#x3048;&#x3070;

May 26, 2022
Zuby 下書き

&#x305A;&#x3073;&#x3057;&#x3044;&#x305A; &#x30C1;&#x30B1;&#x30C3;&#x30C8;&#x4E0B;&#x66F8;&#x304D; background hogefuga reachabilty&#x5224;&#x5B9A;&#x306E;&#x5C0E;&#x5165;&#x306B;&#x3088;&#x3063;&#x3066;&#x6539;&#x5584;&#x3055;&#x308C;&#x308B;&#x3082;&#x306E;

Dec 24, 2020
Zuby 作業ログ

8, 9&#x65E5;&#x76EE;(2020/10/15-19) mruby/mruby&#x3078;&#x306E;endless range&#x306E;&#x5B9F;&#x88C5;&#x306F;&#x7121;&#x4E8B;merge&#x3055;&#x308C;&#x307E;&#x3057;&#x305F; https://github.com/mruby/mruby/pull/5093 CRuby &#x306E; Range&#x306E;&#x6539;&#x5584; &#x30CD;&#x30BF; ruby&#x306E;Range#include &#x306E;string&#x304C;&#x7279;&#x6B8A;&#x306A;&#x30B1;&#x30FC;&#x30B9;&#x3092;&#x9664;&#x3044;&#x3066;String#upto&#x3092;&#x547C;&#x3073;&#x51FA;&#x3057;&#x3066;&#x3044;&#x308B;&#x305F;&#x3081;&#x9045;&#x3044; $ time ruby -e &apos;(&quot;a&quot;..&quot;zzzzz&quot;).include?(&quot;zzzzz&quot;)&apos;

Nov 2, 2020
Read more from Zuby
Published on HackMD