Zuby 作業ログ

8, 9日目(2020/10/15-19)

• mruby/mrubyへのendless rangeの実装は無事mergeされました
• https://github.com/mruby/mruby/pull/5093

CRuby の Rangeの改善 ネタ

• rubyのRange#include のstringが特殊なケースを除いてString#uptoを呼び出しているため遅い

  ​​​​$ time ruby -e '("a".."zzzzz").include?("zzzzz")'
  ​​​​ruby -e '("a".."zzzzz").include?("zzzzz")'  2.19s user 0.10s system 89% cpu 2.543 total
  

  • Range#includeは始端終端がstringの場合 rb_str_include_range_p@string.c を呼び出す
  • https://github.com/ruby/ruby/blob/master/string.c#L4518
  • 始端終端がasciiかつ1文字の場合のみ単純な比較を行い，それ以外はrb_str_upto_each を呼び出している
  • uptoで用いられるString#succが複雑なため（以下参照）include?の判定も非常に難しい

• rangeの始端もしくは終端にUTF-8文字が含まれると非自明な挙動をする

  • ("a".."あ").to_a #=> ["a", ... , "zzy", "zzz"]
    • str_upto_each はsuccで到達できないものについても処理を書いているので把握済み？
    • https://github.com/ruby/ruby/blob/master/string.c#L4457
    • 本当は始端のsucc* が終端にならないものはそもそもrangeとして受け付けないでほしい（個人的に）
      • これは例えばFloatのrangeを受け入れている以上現実的ではなさそうという気持ちになった
  • [*"z".."aa"] #=> []
    • [*"a"..."z"] + [*"z".."aa"] == [*"a".."aa"] になるのが自然だが、[*"z".."aa"] が空になるためこれは一致しない
    • https://bugs.ruby-lang.org/issues/5607
    • 関連: https://bugs.ruby-lang.org/issues/2323
    • これは string.c#L4444 の判定が誤っていて、例えば(c..a)のようなものにイテレーションを走らせないようにした結果，このように到達できるものもはじいてしまっている
    • 「『a が辞書順で b より大きい』ならば『a は b に unreachable である』」は偽
    • issue でも言われている通り、ASCII に絞った対応なら現実的＆需要があるのでは？
  • ("aa"..).include?("b") #=> true
    • 上とは逆に unreachable なものを reachable 判定してしまう
    • これも辞書順比較だけで済ませてしまっているため
    • 単にbegin/endlessの実装ミスっぽい

• (0..1).include?(0.5) #=> true

  • #cover?は連続値，#include?は離散値という原則が存在するにも関わらず数値のみこういう扱いになっている
  • 仕様らしい
  • https://docs.ruby-lang.org/ja/2.7.0/method/Range/i/cover=3f.html

• String#succ のアルゴリズム

  • str_succ
    • 末尾から見ていき alnum があればそこを次の文字にする
      • 次の文字にするのは enc_succ_alnum_char を使う
      • 次の文字にできない場合は「繰り上がり」のように振る舞う
        • 一個前の alnum を次の文字にする
      • 先頭まで来てしまったら文字を前方向に伸ばす
    • 一個も alnum がなかったら、単に文字として似たことをやる
      • enc_succ_char を使う
  • enc_succ_alnum_char
    • alnum 判定は、Unicode Character Properties に基づくと思われる
    • 非 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 だとバイト長が変わったみたいな意味？

ある文字列からある文字列へのreachabilty判定の導入

• reachabilty判定の導入によって改善されるもの
  • ("b".."aa") のような単純な辞書順比較によって正しく評価されていなかったrangeが正しく評価されるようになる
    • #5607 ("b".."aa").to_a => [] になる問題もこれで解決できる
  • Range#include?
    • String#upto で全列挙していた実装の代わりに本methodを使うことで判定が高速に行えるようになる
    • ("b".."aa").include?("z"), ("b"..).include?("aa") などの辞書順比較を用いていたことによるバグが直る
• マルチバイトを考えると複雑になるのでASCIIのみ対応
  • issueでも言われていた通りASCIIに絞った対応なら現実的？
• 到達可能性判定アルゴリズム？

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

• Cに移植

  • /string.c, /internal/string.h
    • ascii_str_reachable_p
    • rb_str_upto_each
    • rb_str_include_range_p
  • /range.c
    • range_include_internal

• メモ

  • String#uptoがString#succに依存しない例
  ​​​​(".".."13").to_a
  ​​​​=> [".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13"]
  ​​​​(".".."=").to_a
  ​​​​=> [".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", ":", ";", "<", "="]
  

  • https://docs.ruby-lang.org/ja/latest/method/String/i/upto.html

7日目(2020/10/13)

• PRを出しました
  • https://github.com/mruby/mruby/pull/5093

  • matz: I will merge this PR after updating master by mruby3 branch.
• 次取り組む課題について調査

6日目(2020/10/12)

• テストの追加，最終確認
  • /test/t/string.rb
    • String#[] with Range
    • Ruby では本来 ここ にテストが書かれるべきだが、忘れられている？
    • mruby にそもそも String#[]= with Range がなかったので生やした
  • /mrbgems/mruby-enum-ext/test/enum.rb
    • Enumerable#take など各種メソッド
    • 変更が増えるので見送り
  • その他放置していたテストのTODOを解決
    • Range#dupとか
• PR
  • [BETTER] Range#minのテストミス
    • https://github.com/mruby/mruby/pull/5089
    • merged
  • [BUG] MRB_WITHOUT_FLOAT でコンパイルが通らない
    • https://github.com/mruby/mruby/pull/5090
    • merged
  • [BETTER]Range#eachでlenが2重代入されている
    • 別コミットで対応
    • https://github.com/mruby/mruby/pull/5091
    • merged
• 本PRを書く
  • 下書きに書いています

5日目(2020/10/8)

mrubyへのendless/beginless rangeの追加

• Range#to_s, Range#inspect
  • nil.to_s は空文字になるので結果的に Range#to_s 改変の必要はない
• Range#{include?(member), #min, #===, #cover?}
  • https://github.com/ruby/ruby/commit/db1bdecb0d925b4668c0735158fce466333848f1
    • min
      • ブロック渡された場合は比較不可能なのでRangeErrorにする
    • include?, member?, ===
      • ('b'..'d').include?('ba') の挙動が ruby と mruby で異なる問題がある // TODO
    • cover?
• Range#{max, last}
  • nilではなくてraiseするようにする
  • https://github.com/ruby/ruby/commit/cae45174190b49ca3c67ca606c5f4b71e3847842
    • last
    • max
• Range#sizeについて
  • 本家RubyではFloat::INFINITYを返しているがmrubyはFloat無しの環境もありえる．この場合に何を返すか．
  • https://github.com/ruby/ruby/commit/342619300ce26f9a134249002270c5d38d5993b3
  • とりあえず nil を返すようにして PR 時に相談
  • そもそも MRB_WITHOUT_FLOAT 下での動作確認が十分になされていなさそう
  • 始端終端がNumericじゃない場合はnilらしい
    • ('a'..'z').size # => nil
• eachで初期値がFIXNUM::MAXのときどうするか
  • https://github.com/ruby/ruby/commit/db885d0850653425b2c7896f9e6730c57b030ab1
    • そもそもmrubyではfixnumの範囲を超えるとFloatになるのでendless rangeでない場合も壊れる
    ​​​​​​​​(9223372036854775807..9223372036854775808).each{|e| p e}
    

    • 別PRにする
• Range#to_a
  • https://github.com/ruby/ruby/commit/c19ecf05b4c728951e1a1e223a40ae6883a4f8e0
  • coreのRuby側に生やした
• Range#lastとRange#endについて
  • 元々のJIS規格ではRange#lastとRange#endは全く同じで（15.2.14.4.10）mruby coreのほうでも実際そうなっている
  • ところが，extでRange#lastは再定義されていて現状のRubyに沿うようになっている（具体的には引数が取れるようになっている等）
  • extのRange#lastでendless rangeについてはraiseするようにしたため，Range#each,max,minなどでで終端を得るのにlastを使っているためこれらが全落ちする
  • にも関わらずテストが通っていた（？？？？）
    • irbで試すとちゃんと死ぬ
    ​​​​​​​​ > (1..).each{}
    ​​​​​​​​cannot get the last element of endless range (RangeError)
    

  • 例外よりはnilが帰ってきてくれると嬉しいのとbeginless対応も見据えfirst, lastをbegin, endにした
  • Range#firstとRange#startも同様の関係であるのに，Range#lastの拡張はC実装なのにRange#firstの拡張はRubyで実装されている
    • C実装かRuby実装かの違いは他も含めあまり良くわからない
• テストの追加
  • /test/t/range.rb
    • Range
      • Range#Hashのテストが無かったり，Float skipがあったりなかったりする
  • /mrbgems/mruby-range-ext/test/range.rb
  • /test/t/array.rb
    • Array#[], Array#[]=
  • /test/t/string.rb
    • String#[] with Range
    • Ruby では本来 ここ にテストが書かれるべきだが、忘れられている？
  • /mrbgems/mruby-string-ext/test/range.rb
    • Range の要素が String のときのテスト
  • /mrbgems/mruby-enum-ext/test/enum.rb
    • Enumerable#take
• Rubyの変更コードとの比較(最終確認)

副産物として見つけたバグなど

• [BETTER]Range#eachでlenが2重代入されている
• [BETTER]Range#Hashのテストが無い
  • 書いた
• [BETTER]RangeのテストでFloat skipがあったりなかったりする
  • 多分MRB_WITHOUT_FLOATすると落ちる
• [BETTER] RubyのString#[]にendless/beginless rangeのテストが無い
• [BUG] mrubyで ('b'..'d').include?('ba') # => false
• [BUG] mrubyで(9223372036854775807..9223372036854775808).each が壊れる
  • これはmrubyにBigintが無く64bit環境において9223372036854775808はFixnumの範囲を超えるのでFloatに変換されるため
• [BUG]integral_div()@numeric.cでMRB_WITHOUT_FLOATありでビルドするとmrb_fixnum_value()への引数の数がおかしいので落ちる。

4日目(2020/10/6)

mrubyへのendless/beginless rangeの追加

• 進捗状況
  • parserの変更
  • Range#eachのInteger(FIXNUM)の場合の実装
  • Range#eachのStringの場合の実装
    • ("a"..).each{|c| p c}
    • 本家ではC側で処理していて通常の String#upto に対応するrb_str_uptoおよびこれのメインロジックに相当するrb_str_upto_eachとは別にendless用にrb_str_upto_endless_eachを用意している．
    • mrubyではRuby側で処理していて String#upto を使っている
    • ここにendless range用の処理を組み込む場合どうするか
      • String#upto の第一引数endに nil を渡すことを許容する
        • 本家と挙動が異なってしまう / 元々のuptoインターフェースを破壊してしまう
      • Ruby側でStringクラスにendless range用のメソッドを新たに用意する
        • どうやって隠蔽？
        • String#__sub_replace という前例が存在
          • 隠蔽はできてない
      • each内でStringにパッチをあてるなりしてupto_endlessを生やす / インラインでベタ書きしちゃう
        • String#upto は拡張として切り分けられているのにまあまあな量の処理を拡張でないところに入れてしまうのは
      • C側で生やす
        • Ruby側から使うにはメソッドなりなんなりで登録する必要があり結局隠蔽ができない．
      • mrubyの他のコードで__ prefixつきのメソッドをprivateとして実装しているものがあるためこれを踏襲する（使えてはしまうが）
        • [e-mail] など
        • _の数は1個だったり2個だったりする（え？）
    • とりあえずアンスコでの実装を選択，完了
  • [1,2,3][0..]の実装(mrb_range_beg_len()@range.c)
  • EXCLUSIVE[0…]への対応(mrb_range_beg_len()@range.c)
  • Range#to_s, Range#inspect
  • テストの追加
    • Range
    • Array#[], Array#[]=
    • String#[], String#[]=
  • Rubyの変更コードとの比較(この部分はいる・いらない選択, 最終確認)

3日目(2020/10/5)

• チームとしての作業

  • ネタ探し

    • irbのendless method definitionのバグは既出のPRで直っていそう
    • priority queue ほしい（三浦が個人的に）
      • データ構造の名前としては binary heap
      • 検索しても特に既存の提案は見つからない
      • set みたいに標準ライブラリであってほしい
    • Haskell の scan ほしい（三浦が個人的に）
      • 流石に既出だったし実装済みだった（提案3ヶ月前、最終更新1ヶ月前）
      • https://bugs.ruby-lang.org/issues/17016
      • https://github.com/ruby/ruby/pull/3078
      • 名前決めの段階？　若干放置気味
    • 実装したものを新しいFeatureとして投げるのは有り
    • mruby
      • Issue
        • https://github.com/mruby/mruby/issues/5085
          • endless-range: ruby-2.6.0-preview2から実装
            • https://bugs.ruby-lang.org/issues/12912
            • https://github.com/ruby/ruby/commit/7f95eed19e22cb9a4867819355fe4ab99f85fd16
          • beginless-range: v2_7_0_preview1から実装
            • https://github.com/ruby/ruby/commit/95f7992b89efd35de6b28ac095c4d3477019c583
          • mRubyのRangeでnil指定した場合の挙動をrubyに合わせ
          • Matzさんが"Accept"しているが"priority is low"としている
            • mrubyよく知らんけど、rubyの該当コードぱくるだけになりそう?
            • https://github.com/ruby/ruby/blame/master/range.c#L430
              • 構文木とかもいじらないといけないかも(Range.newだけならnilチェックだけでいいだろうけど、``1..`のような場合)
            • Rubyとmrubyの実装が似て非なる感じなのでいい感じに移植が大変そう？
              • コア
                • https://github.com/mruby/mruby/blob/master/src/range.c
                • https://github.com/mruby/mruby/blob/master/mrblib/range.rb
              • 構文解析
                • https://github.com/mruby/mruby/blob/master/mrbgems/mruby-compiler/core/parse.y#L2117-L2124
              • 拡張？
                • https://github.com/mruby/mruby/blob/master/mrbgems/mruby-range-ext/src/range.c
                • https://github.com/mruby/mruby/blob/master/mrbgems/mruby-range-ext/mrblib/range.rb

  • 一旦、mrubyにendless rangeを移植することを目標とすることにした

  • 各々、RubyとmRubyのRange周りの実装をリーディング

• 個人作業

  • 水橋
  • 三浦
  • 橋本
    • 取り敢えずmruby/rubyのRange周りコードリーディング
    • Range.new(1.nil).each {}が動くようにした

2日目(2020/10/1)

• チームとしての作業

  • ネタ探し
    • Ruby本体
      • 先週にRuby 3.0.0のpreview1がリリースされたため，これ関連のbugを探すのが良さそう？
    • irb
      • コードの読み込みが pry-byebug(https://github.com/deivid-rodriguez/byebug, https://github.com/deivid-rodriguez/pry-byebug) に比べて有意に遅いのでこれを改善したい
        • 適当に数行のコードを貼り付けるとかなり分かるはず
        • 恐らくsyntax highlightが重い？ ruby/relineも含めて見る必要がありそう
      • チケット切られてるバグ
        • Endless method definitionにlambdaを食わせると正しく動作しない
          • https://bugs.ruby-lang.org/issues/17193
          • Endless method definitionについて
            • https://bugs.ruby-lang.org/issues/16746
            • https://github.com/ruby/ruby/pull/2996
    • mruby
      • 組み込み用途のRuby
      • 言語仕様が本家より小さいので手を付けやすい？
      • 具体的に何したいかは未定
    • rbs
      • Rubyコードで型シグニチャ（所謂型アノテーション？）が使えるようにするgem
      • https://www.ruby-lang.org/en/news/2020/09/25/ruby-3-0-0-preview1-released/
        • v3.xの一部としてリリースされることになっているらしい
      • https://tadd.hatenablog.jp/entry/2020/09/10/205812
        • 今年GSoCでrbsをやっていた人のレポート

• 個人作業

  • 水橋

    • Ruby 3.0.0preview1のビルド
      • macOS10.14以降で/usr/includeが無い問題はcommand line toolsのものを認識させてあげればよく（ /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include とかにありそう），これは export SDKROOT="$(xcrun --sdk macosx --show-sdk-path)" で解決する（いつもの）．
    • llvm周りでコケている→llvmのversionを10系にしたらこけなくなった
    • こけた
      ​​​​​​​​​​​​(snip)
      ​​​​​​​​​​​​linking static-library libruby.3.0-static.a
      ​​​​​​​​​​​​llvm-ar: error: unknown option n
      

    • Macでやるの諦めたい
    • Ubuntu 20.04でやりました．ログ:
      ​​​​​​​​​​​​# bento/ubuntu-20.04 with vagrant
      ​​​​​​​​​​​​# sudo apt-get install -y build-essential
      ​​​​​​​​​​​​$ sudo apt-get install -y autoconf ruby bison
      ​​​​​​​​​​​​$ git clone https://github.com/ruby/ruby
      ​​​​​​​​​​​​$ cd ruby && git checkout v3_0_0_preview1
      ​​​​​​​​​​​​$ autoconf
      ​​​​​​​​​​​​$ ./configure --prefix=/home/vagrant/.bin/ruby-dev
      ​​​​​​​​​​​​$ make -j4 && make install 
      

  • 橋本

    • Ruby 3.0.0preview1・mruby(master)のビルド
      • ok
    • チケット・Issue漁り

  • 三浦

    • ruby/ruby masterのビルド
      • configureにRubyが必要
    • ruby-jp slackに入る