# RubyのString#succに関する小話 この記事は[eeic （東京大学工学部電気電子・電子情報工学科） Advent Calendar 2020](https://qiita.com/advent-calendar/2020/eeic)，及び[TSG Advent Calendar 2020](https://adventar.org/calendars/4995)の23日目の記事です． 予定では今夏参加させていただいていたYahoo Japan!のインターンでやらせて頂いていたFIDO2，WebAuthn等の話を書くつもりで前々から少しずつ準備していたのですが，想定外に大作となってしまいどう考えても間に合わなことが判明したため急遽お題を変更し，[@n4o847](https://twitter.com/n4o847), [@smallkirby_](https://twitter.com/smallkirby_) と今学期のeeicの後期実験の1つである「[大規模ソフトウェアを手探る](https://doss.eidos.ic.i.u-tokyo.ac.jp/)」にて取り組んだRubyの小話をすることにしました．遅刻大変申し訳ありません． <!--あまり込み入った話はせずサクッと（これは嘘で，書く時間がありませんでした :pensive:）--> 本記事における挙動や仕様は`Ruby 2.7.2` で確認しており，コードについても本バージョンのものを参照しています．https://github.com/ruby/ruby/tree/5445e0435260b449decf2ac16f9d09bae3cafe72 --- Ruby には `String#succ`（あるいは`String#next`）という，文字列の後継の文字列を返すメソッドがあります． https://docs.ruby-lang.org/ja/latest/method/String/i/succ.html 例えば ```ruby= > "a".succ => "b" > "100".succ => "101" > "###".succ => "##$" > "を".succ => "ん" ``` といった具合です． 後述しますが，このメソッドは始端終端が文字列であるRange（例: `"a".."z"` ） の内部で用いられており，例えば，`Range#each`においては今処理している文字の次の文字を決定するために使われています． このメソッドの特筆すべき点として，"文字の繰り上がり" が考慮される場合があり ```ruby= > "9".succ => "10" > "ZZ".succ => "AAA" > 77476.times.reduce("TSG"){|ch| ch.succ} => "EEIC" ``` という様な挙動をします．ざっくり英数字としてマッチする文（後述します）であればこのような繰り上がり処理が行われます． では ```ruby= > "9Zz9".succ ``` の結果は何になるか予想がつきますでしょうか？ 答えは ```ruby= > "9Zz9".succ => "10Aa0" ``` です． このように，隣接する文字種が異なる（これも後述します）場合にも繰り上がりは行われます．最上行桁がどのような値になるかは最左の文字に依存します． では，英数字以外でないもの（例えば記号）を含む場合はどうかというと ```ruby= > "v1.9.9".succ => "v2.0.0" ``` このように記号を無視して繰り上がりが行われます． では，これはどうでしょうか． ```ruby= > "##zz99##zz99##99##".succ ``` これは ```ruby= > "##zz99##zz99##99##".succ => "##zz99##aaa00##00##" ``` という結果になります．英数字でない文字列に接している左右の英数字について，"文字種" が一致しているのであれば繰り上がりを伝播させますが，一致していない場合はさせないという挙動になっています． --- なんとなく`String#succ`の挙動の雰囲気が分かって頂けたと思うので，もう少し掘り下げて解説します． `String#succ`は文字の種類として `:alnum:` であるかそれ以外か，また，`alnum`の中でも`:alpha:`か`:digit:` かを区別します． ここで`:alnum:`，`:alpha:`，`:digit:`とは，POSIX文字クラスに依拠するもので，例えばUnicodeであれば，Character PropertyのうちGeneral Categoryの値で次に対応します - `:alnum:` := Letter | Mark | Decimal_Number - `:alpha:` := Letter | Mark - `:digit:` := Decimal_Number 詳細は https://docs.ruby-lang.org/ja/latest/doc/spec=2fregexp.html#charclass_posix や，https://www.unicode.org/reports/tr44/#GC_Values_Table を参照下さい． 注意として，例えばUTF-8における"あ"のGeneral Category Valueは`Letter, Other[Lo]`ですので，これは`:alnum:`にマッチします． この上で，以下のような挙動をします． #### 文字列が`:alnum:`相当の文字を含まない場合 最右の文字をその文字コードにおける次の文字に置換した文字列を返却します． ```ruby= > "#&)".succ => "#&*" ``` #### 文字列が`:alnum:`相当の文字をを1つ以上含む場合 まずは **非`:alnum:`な文字は取り除いて考えます．** ある文字列の`:alnum:`に相当する文字のみを取り出した文字列において，その最右の文字の文字コード上の次の文字（以降，単に "次の文字" と書きます）の文字種（すなわち`:digit:`か`:alpha:`か）が元の文字のそれと等しいかを確認します． 一致しているのであれば，繰り上がりは発生させず元の最右の文字をその次の文字に置換した文字列を返却します． ```ruby= > "%%&&###1##&&%%".succ => "%%&&###2##&&%%" ``` 但し，文字種が異なる場合でも一文字までなら乗り越えることができます． これは，reservedとなっている[ギリシャ文字のU+03A2](http://www.unicode.org/charts/PDF/U0370.pdf)を乗り越えるために修正された（https://bugs.ruby-lang.org/issues/12204) もののようです．[^hakatashi] [^hakatashi]: U+03A2がなぜreservedになっているかは次の通りです．(thanks to hakatashi) ![](https://i.imgur.com/rPdJuux.png) ```ruby= > "Ρ".succ # => \u03A1 => "Σ" # => \u03A3 ``` 文字種が異なる場合繰り上がりを発生させます． 最右の文字の次の文字，次の次の文字も文字種が異なる場合，まずは，その最右の文字を終端とした文字種が等しい文字コード上の連続した列の始端を探索します． 例えば，`"9"` (ASCII-8BIT)であれば，文字コード上の次，次の次の文字はそれぞれ `":"`, `";"` であり，これは `:digit:`ではありません．よって `"9"` を終端とし，文字種`:digit:`が連続しているような文字コード上の領域の始点を探します．これは，文字コードを `"8"` , `"7"` と逆順に辿っていき，結果 `"0"` が始端の文字となります．（なぜなら，`"0"` の前は `"/"` であり，これは`:digit:` ではありません）．`"Z"` であれば，始端は `"A"` になるでしょう． その上で，文字列の最右の文字をこの始端の文字に置換し，その1文字左にある文字を今まで説明した規則通りに一つ進めます．ここで `:alpha:`か `:digit:`かは考慮しません．（左にある文字が`:alnum:`以外の文字である場合は後述します）．次に，今見ていた文字の1文字左の文字について同じ工程を行います．これを繰り上がりが発生しなくなるか，文字列の最左の文字に到達するまで続けます． 文字列の最左の文字で繰り上がりが発生した場合は新たに左に文字を追加します．その最左の文字が文字種が`:alpha:`である場合は始点の文字を左に，`:digit:` である場合は始点の文字の次の文字を左に追加します． ```ruby= > "zzz".succ => "aaaa" ``` ```ruby= > "999".succ => "1000" ``` <br/> 最後に，無視していた非`:alnum:`な文字たちの処理についてです． 繰り上がりが`:alnum:`以外の文字を跨いで上位の文字，すなわち自分よりも左にある文字に伝播するかは，`:alnum:`以外の文字列が接している左右の`:alnum:`の文字種が一致しているかで決定します． 例えば， ```ruby= > "1##9".succ ``` では，非`:alnum:`である`##`と接している左右の`:alnum:` である `"1"`, `"9"` について，その文字種が一致している（`:digit:`）ため，`"1"` と `"9"` は "繋がっている" 文字列として扱われ，繰り上がりが行われます． ```ruby= > "1##9".succ => "2##0" ``` 一方， ```ruby= > "1&&Z".succ ``` は，`##`と接している左右の`:alnum:`文字種は異なる(`:digit:`, `:alpha:`)ため，各々別々の文字列と考えられた上で繰り上がりが行われます． ```ruby= > "1&&Z".succ => "1&&AA" ``` `:alnum:`を1つ以上含む文字列において，`:alnum:`以外の文字が変更されることはありません． --- 以上を踏まえると，**「お前が本当にRubyエンジニアだというのならば，UTF-8の"ン"(U+30F3)を12回`succ`した文字列を答えてみよ．」** と尋問された場合も，うまく切り抜けることができるでしょう．[^r] [^r]: https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%BC%E3%82%B4%E3%83%AA%E3%83%BB%E3%82%BF%E3%83%A0 https://ja.wikipedia.org/wiki/Unicode%E4%B8%80%E8%A6%A7_3000-3FFF より抜粋したコード表は次の通りです． ![](https://i.imgur.com/YWegLjA.png) ... ... ... ... ... ... ... ... ... ... ... ... 答えは `"ーー"` です． ```ruby= > 12.times.reduce("ン"){|ch| ch.succ} => "ーー" ``` これは，次の規則に従っています． - `"ン"` のGeneral Categoryの値は`Letter, Other[Lo]`であるから`:alnum:`/ `:alpha:` に相当する． - `"ン"` から前に, `"ヴ"`, `"ヵ"`, `"ヶ"`, `"ヷ"`, `"ヸ"`, `"ヹ"`, `"ヺ"` も同じ`Letter, Other[Lo]`であり，これは`:alpha:` に相当することから同じ文字種としてsuccで進む - "ヺ"のUTF-8上の次の文字である `"・"` は`Punctuation, Other[Po]`であることから，これは`:alpha:`ではない（`:alnum:`でもない）．しかし，その次の文字 `"ー"` は `Letter, Modifier[Lm]` ，すなわち`:alpha:` に相当する．文字種の違いも一つまでなら飛ばすことができるというルールから，`"ヺ".succ == "ー"` となる． - `"ー"`, `"ヽ"`, `"ヾ"`, `"ヿ"` は何れも`:alpha:`に相当する． - `"ヿ"` のUTF-8上の次の文字 `"\u3100"`, その次の文字 `"\u3101"` はreservedであり， `:alpha:`には該当しない．よって巻き戻りを行い文字種の始点を探す．この時，`"ヿ"` を終端として文字種が連続して一致するようなUTF-8上の列の始端は `"ー"` である．[^isbug]繰り上がり処理を行い，`"ヿ".succ == "ーー"` となる． [^isbug]:始点となる文字の探索時になぜ1つ飛ばしの場合を考慮しないかはコードを読んだ限りでは意図が分からなかったのですが，この文章を書いていたらバグである可能性も考えられるような気もしてきたので近いうちに相談してみようかなと考えています． --- さて，先程この`String#succ`は始端終端が文字列のRangeの内部で用いられていると説明しました． より正確には，`String#succ`は一部の例外を除いて[^1]`String#upto`の実装の本体である（[rb_str_upto_each@range.c#L4263](https://github.com/ruby/ruby/blob/5445e0435260b449decf2ac16f9d09bae3cafe72/string.c#L4263))で用いられています． ```ruby= > [*"ax".upto("bb")] => ["ax", "ay", "az", "ba", "bb"] ``` さらに`Range#each`など[^step]がこの`rb_str_upto_each`，実質`String#upto`を使っています．また，`Range`の親クラス`Enumerable`においてその要素一つ一つを使うような場面には往々にして`each`を使うため，Rangeの要素に触るようなメソッドには`String#upto`，すなわち`String#succ`が呼ばれると考えて差し支えないでしょう ```ruby= > ("ax".."bb").each{|c| p c} "ax" "ay" "az" "ba" "bb" => "ax".."bb" > [*("ax".."bb")] # to_a => ["ax", "ay", "az", "ba", "bb"] ... ``` [^step]: 他には`Range#step` ところで，これまで説明してきた`String#succ`の複雑さから，「ある文字列からある文字列へsuccを辿って到達できるか」という問題の判定が難しくなっており[^mendou]，これに起因する（と考えられる）パフォーマンスの問題や一貫性のない挙動が幾つかあります（もしくは既に報告されていたり仕様として認められていたりします） [^mendou]: 難しくなっている一因として，非`alnum`で構成された文字列を`succ`で進めた先で`:alnum:`に到達した場合は以降は`:alnum:`を一つ以上含む文字列として扱われることが挙げられます．さらに，これをマルチバイト文字で考慮するには... 例えば，"z"から"aa"までは明らかに`succ`を用いて到達することができる（実際，`"z".succ == "aa"`）のですが， ```ruby= > ("z"..).take(10) => ["z", "aa", "ab", "ac", "ad"] > [*("z".."aa")] => [] ``` となってしまいます．これは，`String#upto`，もとい`rb_str_upto_each`が(恐らく)パフォーマンスの観点から[辞書順で始端 > 終端となるものに関しては処理を走らせないようにしているから](https://github.com/ruby/ruby/blob/5445e0435260b449decf2ac16f9d09bae3cafe72/string.c#L4323)であり，これは既に https://bugs.ruby-lang.org/issues/13663 ，https://bugs.ruby-lang.org/issues/2323 ，https://bugs.ruby-lang.org/issues/5607 などで報告されています． また， `Range#include?` は一部の例外を除いて`String#upto`を逐次呼び出す（すなわちRangeの始端から終端までsuccで辿る間に与えられた文字列が存在するかということを確認する）ため低速です． ```bash= $ time ruby -e '("a".."zzzzz").include?("zzzzz")' ruby -e '("a".."zzzzz").include?("zzzzz")' 2.17s user 0.07s system 96% cpu 2.327 total ``` さらにendless/beginless rangeの場合，その性質上`String#upto`を呼び出して上記のように実際に確認することは困難であるため，現状辞書順判定が採用されています． ```ruby= > ("b"..).include?("aa") => false ``` この周辺の問題をある程度解決させる話を冒頭で述べた通り[@smallkirby_](https://twitter.com/smallkirby_),[@n4o847](https://twitter.com/n4o847) と今学期のEEICの後期実験の1つである「大規模ソフトウェアを手探る」の後半にて取り組んでおり，続報をお待ち頂ければ（？）と思います．[^busy] [^busy]: 実験自体は10月の始め3週程度（2コマ * 10日間）で行われており，実装自体は特にn4o847先生の功績によってほぼほぼ終わっているものの，そこから各々忙しく進展がない状態です :pensive:． ちなみに実験前半は小手調べとしてmrubyにendless rangeを追加する変更を行い，めでたくmergeされました．この話もまた改めて別の機会で公開できればなあとメンバーと話しています． https://github.com/mruby/mruby/pull/5093 [^1]: 例えば`String#upto` は始端及び終端が1文字かつasciiの場合はsuccに従いません (".".."=").to_a => [".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", ":", ";", "<", "="] (".".."13").to_a => [".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13"]
Last changed by  
 
Zuby
ずびしいず
3028

Read more

Zuby 下書き

ずびしいず チケット下書き background hogefuga reachabilty判定の導入によって改善されるもの

12/24/2020
Zuby

Zuby: mrubyへのendless rangeの導入とRubyにおける到達可能性判定の追加 目次 [TOC] はじめに この文章は東大工学部電気電子工学科・電子情報工学科（通称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

11/2/2020
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")'

11/2/2020
Read more from Zuby
Published on HackMD