Try   HackMD

RubyのString#succに関する小話

この記事はeeic （東京大学工学部電気電子・電子情報工学科） Advent Calendar 2020，及びTSG Advent Calendar 2020の23日目の記事です．

予定では今夏参加させていただいていたYahoo Japan!のインターンでやらせて頂いていたFIDO2，WebAuthn等の話を書くつもりで前々から少しずつ準備していたのですが，想定外に大作となってしまいどう考えても間に合わなことが判明したため急遽お題を変更し，@n4o847, @smallkirby_ と今学期のeeicの後期実験の1つである「大規模ソフトウェアを手探る」にて取り組んだRubyの小話をすることにしました．遅刻大変申し訳ありません．

本記事における挙動や仕様は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

例えば









> "a".succ
=> "b"
> "100".succ
=> "101"
> "###".succ
=> "##$"
> "を".succ
=>  "ん"

といった具合です．

後述しますが，このメソッドは始端終端が文字列であるRange（例: "a".."z" ） の内部で用いられており，例えば，Range#eachにおいては今処理している文字の次の文字を決定するために使われています．

このメソッドの特筆すべき点として，"文字の繰り上がり" が考慮される場合があり







> "9".succ
=> "10"
> "ZZ".succ
=> "AAA"
> 77476.times.reduce("TSG"){|ch| ch.succ}
=> "EEIC"

という様な挙動をします．ざっくり英数字としてマッチする文（後述します）であればこのような繰り上がり処理が行われます．

では

> "9Zz9".succ

の結果は何になるか予想がつきますでしょうか？

答えは



> "9Zz9".succ
=> "10Aa0"

です．

このように，隣接する文字種が異なる（これも後述します）場合にも繰り上がりは行われます．最上行桁がどのような値になるかは最左の文字に依存します．

では，英数字以外でないもの（例えば記号）を含む場合はどうかというと



> "v1.9.9".succ
=> "v2.0.0"

このように記号を無視して繰り上がりが行われます．

では，これはどうでしょうか．

> "##zz99##zz99##99##".succ

これは



> "##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:相当の文字を含まない場合

最右の文字をその文字コードにおける次の文字に置換した文字列を返却します．



> "#&)".succ
=> "#&*"

文字列が:alnum:相当の文字をを1つ以上含む場合

まずは 非:alnum:な文字は取り除いて考えます．

ある文字列の:alnum:に相当する文字のみを取り出した文字列において，その最右の文字の文字コード上の次の文字（以降，単に "次の文字" と書きます）の文字種（すなわち:digit:か:alpha:か）が元の文字のそれと等しいかを確認します．

一致しているのであれば，繰り上がりは発生させず元の最右の文字をその次の文字に置換した文字列を返却します．



> "%%&&###1##&&%%".succ
=> "%%&&###2##&&%%"

但し，文字種が異なる場合でも一文字までなら乗り越えることができます．
これは，reservedとなっているギリシャ文字のU+03A2を乗り越えるために修正された（https://bugs.ruby-lang.org/issues/12204) もののようです．[1]



> "Ρ".succ # => \u03A1
=> "Σ" # => \u03A3

文字種が異なる場合繰り上がりを発生させます．

最右の文字の次の文字，次の次の文字も文字種が異なる場合，まずは，その最右の文字を終端とした文字種が等しい文字コード上の連続した列の始端を探索します．
例えば，"9" (ASCII-8BIT)であれば，文字コード上の次，次の次の文字はそれぞれ ":", ";" であり，これは :digit:ではありません．よって "9" を終端とし，文字種:digit:が連続しているような文字コード上の領域の始点を探します．これは，文字コードを "8" , "7" と逆順に辿っていき，結果 "0" が始端の文字となります．（なぜなら，"0" の前は "/" であり，これは:digit: ではありません）．"Z" であれば，始端は "A" になるでしょう．

その上で，文字列の最右の文字をこの始端の文字に置換し，その1文字左にある文字を今まで説明した規則通りに一つ進めます．ここで :alpha:か :digit:かは考慮しません．（左にある文字が:alnum:以外の文字である場合は後述します）．次に，今見ていた文字の1文字左の文字について同じ工程を行います．これを繰り上がりが発生しなくなるか，文字列の最左の文字に到達するまで続けます．

文字列の最左の文字で繰り上がりが発生した場合は新たに左に文字を追加します．その最左の文字が文字種が:alpha:である場合は始点の文字を左に，:digit: である場合は始点の文字の次の文字を左に追加します．



> "zzz".succ
=> "aaaa"



> "999".succ
=> "1000"

最後に，無視していた非:alnum:な文字たちの処理についてです．

繰り上がりが:alnum:以外の文字を跨いで上位の文字，すなわち自分よりも左にある文字に伝播するかは，:alnum:以外の文字列が接している左右の:alnum:の文字種が一致しているかで決定します．
例えば，

 > "1##9".succ

では，非:alnum:である##と接している左右の:alnum: である "1", "9" について，その文字種が一致している（:digit:）ため，"1" と "9" は "繋がっている" 文字列として扱われ，繰り上がりが行われます．



 > "1##9".succ
=> "2##0"

一方，

> "1&&Z".succ

は，##と接している左右の:alnum:文字種は異なる(:digit:, :alpha:)ため，各々別々の文字列と考えられた上で繰り上がりが行われます．



> "1&&Z".succ
=> "1&&AA"

:alnum:を1つ以上含む文字列において，:alnum:以外の文字が変更されることはありません．

以上を踏まえると，「お前が本当にRubyエンジニアだというのならば，UTF-8の"ン"(U+30F3)を12回succした文字列を答えてみよ．」 と尋問された場合も，うまく切り抜けることができるでしょう．[2]

https://ja.wikipedia.org/wiki/Unicode一覧_3000-3FFF より抜粋したコード表は次の通りです．

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

…

…

…

…

…

…

…

…

…

…

…

…

答えは "ーー" です．



> 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上の列の始端は "ー" である．[3]繰り上がり処理を行い，"ヿ".succ == "ーー" となる．

さて，先程このString#succは始端終端が文字列のRangeの内部で用いられていると説明しました．
より正確には，String#succは一部の例外を除いて[4]String#uptoの実装の本体である（rb_str_upto_each@range.c#L4263)で用いられています．



> [*"ax".upto("bb")]
=> ["ax", "ay", "az", "ba", "bb"]

さらにRange#eachなど[5]がこのrb_str_upto_each，実質String#uptoを使っています．また，Rangeの親クラスEnumerableにおいてその要素一つ一つを使うような場面には往々にしてeachを使うため，Rangeの要素に触るようなメソッドにはString#upto，すなわちString#succが呼ばれると考えて差し支えないでしょう













> ("ax".."bb").each{|c| p c}
"ax"
"ay"
"az"
"ba"
"bb"
=> "ax".."bb"

> [*("ax".."bb")] # to_a
=> ["ax", "ay", "az", "ba", "bb"]

...

ところで，これまで説明してきたString#succの複雑さから，「ある文字列からある文字列へsuccを辿って到達できるか」という問題の判定が難しくなっており[6]，これに起因する（と考えられる）パフォーマンスの問題や一貫性のない挙動が幾つかあります（もしくは既に報告されていたり仕様として認められていたりします）

例えば，"z"から"aa"までは明らかにsuccを用いて到達することができる（実際，"z".succ == "aa"）のですが，





> ("z"..).take(10)
=>  ["z", "aa", "ab", "ac", "ad"]
> [*("z".."aa")]
=> []

となってしまいます．これは，String#upto，もといrb_str_upto_eachが(恐らく)パフォーマンスの観点から辞書順で始端 > 終端となるものに関しては処理を走らせないようにしているからであり，これは既に
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で辿る間に与えられた文字列が存在するかということを確認する）ため低速です．



$ 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を呼び出して上記のように実際に確認することは困難であるため，現状辞書順判定が採用されています．



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

この周辺の問題をある程度解決させる話を冒頭で述べた通り@smallkirby_,@n4o847 と今学期のEEICの後期実験の1つである「大規模ソフトウェアを手探る」の後半にて取り組んでおり，続報をお待ち頂ければ（？）と思います．[7]

ちなみに実験前半は小手調べとしてmrubyにendless rangeを追加する変更を行い，めでたくmergeされました．この話もまた改めて別の機会で公開できればなあとメンバーと話しています．
https://github.com/mruby/mruby/pull/5093

  1. U+03A2がなぜreservedになっているかは次の通りです．(thanks to hakatashi)
    ↩︎

  2. https://ja.wikipedia.org/wiki/イーゴリ・タム ↩︎

  3. 始点となる文字の探索時になぜ1つ飛ばしの場合を考慮しないかはコードを読んだ限りでは意図が分からなかったのですが，この文章を書いていたらバグである可能性も考えられるような気もしてきたので近いうちに相談してみようかなと考えています． ↩︎

  4. 例えば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"] ↩︎

  5. 他にはRange#step ↩︎

  6. 難しくなっている一因として，非alnumで構成された文字列をsuccで進めた先で:alnum:に到達した場合は以降は:alnum:を一つ以上含む文字列として扱われることが挙げられます．さらに，これをマルチバイト文字で考慮するには… ↩︎

  7. 実験自体は10月の始め3週程度（2コマ * 10日間）で行われており，実装自体は特にn4o847先生の功績によってほぼほぼ終わっているものの，そこから各々忙しく進展がない状態です :pensive:． ↩︎

Last changed by 
 
Zuby
ずびしいず
0
1
3630

Read more

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

Zuby: mruby&#x3078;&#x306E;endless range&#x306E;&#x5C0E;&#x5165;&#x3068;Ruby&#x306B;&#x304A;&#x3051;&#x308B;&#x5230;&#x9054;&#x53EF;&#x80FD;&#x6027;&#x5224;&#x5B9A;&#x306E;&#x8FFD;&#x52A0; &#x76EE;&#x6B21; [TOC] &#x306F;&#x3058;&#x3081;&#x306B; &#x3053;&#x306E;&#x6587;&#x7AE0;&#x306F;&#x6771;&#x5927;&#x5DE5;&#x5B66;&#x90E8;&#x96FB;&#x6C17;&#x96FB;&#x5B50;&#x5DE5;&#x5B66;&#x79D1;&#x30FB;&#x96FB;&#x5B50;&#x60C5;&#x5831;&#x5DE5;&#x5B66;&#x79D1;&#xFF08;&#x901A;&#x79F0;eeic&#xFF09;&#x306E;3&#x5E74;&#x5F8C;&#x671F;&#x5B9F;&#x9A13;&#x306E;&#x79D1;&#x76EE;&#x306E;1&#x3064;&#x3067;&#x3042;&#x308B;&#x5927;&#x898F;&#x6A21;&#x30BD;&#x30D5;&#x30C8;&#x30A6;&#x30A7;&#x30A2;&#x3092;&#x624B;&#x63A2;&#x308B; &#x306E;&#x30EC;&#x30DD;&#x30FC;&#x30C8;&#x3068;&#x3057;&#x3066;&#x66F8;&#x304B;&#x308C;&#x305F;&#x3082;&#x306E;&#x3067;&#x3059;&#xFF0E;&#x5B9F;&#x9A13;&#x306E;&#x5185;&#x5BB9;&#x306F;&#x7AEF;&#x7684;&#x306B;&#x8FF0;&#x3079;&#x308B;&#x3068;10&#x65E5;&#x9593;&#x306E;&#x5B9F;&#x9A13;&#x671F;&#x9593;&#x3067;&#x5927;&#x898F;&#x6A21;&#x306A;OSS&#x3092;&#x9078;&#x3073;&#x4F55;&#x3089;&#x304B;&#x306E;&#x6A5F;&#x80FD;&#x5B9F;&#x88C5;&#x3092;&#x8A66;&#x307F;&#x308B;&#x3068;&#x3044;&#x3046;&#x3082;&#x306E;&#x3067;&#xFF0C;&#x4ECA;&#x56DE;&#x6211;&#x3005;&#x306E;&#x73ED;&#x3067;&#x306F;Ruby&#x306E;&#x51E6;&#x7406;&#x7CFB;&#x3067;&#x3042;&#x308B;CRuby, mruby&#x3092;&#x624B;&#x63A2;&#x308A;&#x307E;&#x3057;&#x305F;&#xFF0E;&#x3044;&#x304F;&#x3064;&#x304B;&#x306E;&#x6A5F;&#x80FD;&#x306E;&#x65B0;&#x898F;&#x5B9F;&#x88C5;&#x30FB;&#x6539;&#x5584;&#x3092;&#x884C;&#x3044;&#x305D;&#x306E;&#x3046;&#x3061;&#x4E00;&#x90E8;&#x306B;&#x3064;&#x3044;&#x3066;&#x306F;&#x5B9F;&#x969B;&#x306B;Pull Request&#x3092;&#x51FA;&#x3057;merge&#x3092;&#x3057;&#x3066;&#x3044;&#x305F;&#x3060;&#x3051;&#x307E;&#x3057;&#x305F;&#x306E;&#x3067;&#xFF0C;&#x305D;&#x306E;&#x4E00;&#x90E8;&#x59CB;&#x7D42;&#x3092;&#x4EE5;&#x4E0B;&#x306B;&#x8A18;&#x3057;&#x307E;&#x3059;&#xFF0E; mruby&#x306B;&#x3064;&#x3044;&#x3066; Ruby&#x306E;&#x51E6;&#x7406;&#x7CFB;&#x306E;&#x4E00;&#x3064;&#x3067;&#x3042;&#x308A;&#xFF0C;&#x7D44;&#x8FBC;&#x307F;&#x5411;&#x3051;&#x306B;&#x51E6;&#x7406;&#x7CFB;&#x306E;&#x30B5;&#x30A4;&#x30BA;&#x3084;&#x901F;&#x5EA6;&#x304C;&#x6700;&#x9069;&#x5316;&#x3055;&#x308C;&#x3066;&#x3044;&#x308B;&#x306E;&#x304C;&#x7279;&#x5FB4;&#x3067;&#x3059;&#xFF0E;C&#x3068;Ruby&#x3092;&#x7528;&#x3044;&#x3066;&#x5B9F;&#x88C5;&#x3055;&#x308C;&#x3066;&#x304A;&#x308A;&#xFF0C;CRuby&#x3068;&#x540C;&#x69D8;&#x306B;Matz&#x3092;&#x4E2D;&#x5FC3;&#x306B;&#x30E1;&#x30F3;&#x30C6;&#x304C;&#x306A;&#x3055;&#x308C;&#x3066;&#x3044;&#x307E;&#x3059;&#xFF0E;Ruby&#x306E;&#x8A00;&#x8A9E;&#x4ED5;&#x69D8;&#x306E;&#x3046;&#x3061;JIS&#x898F;&#x683C;&#x6E96;&#x62E0;&#x306E;&#x3082;&#x306E;&#x3092;core&#x3068;&#x3057;&#x3066;&#x5B9F;&#x88C5;&#x3057;&#x3066;&#x304A;&#x308A;&#xFF0C;&#x305D;&#x306E;&#x4ED6;&#x306E;&#x6A5F;&#x80FD;&#x306F;&#x62E1;&#x5F35;&#x3068;&#x3044;&#x3046;&#x5F62;&#x3067;&#x5B9F;&#x88C5;&#x3055;&#x308C;&#x3066;&#x3044;&#x307E;&#x3059;&#xFF0E;&#x3068;&#x306F;&#x3044;&#x3048;&#x7D44;&#x307F;&#x8FBC;&#x307F;&#x5411;&#x3051;&#x3067;&#x3042;&#x308B;&#x306E;&#x3067;&#x62E1;&#x5F35;&#x306B;&#x3059;&#x3089;&#x79FB;&#x690D;&#x3055;&#x308C;&#x3066;&#x3044;&#x306A;&#x3044;Ruby(CRuby)&#x306E;&#x6A5F;&#x80FD;&#x3082;&#x591A;&#x304F;&#x5B58;&#x5728;&#x3057;&#x307E;&#x3059;&#xFF0E;&#x4EE5;&#x4E0B;&#x306E;&#x30EA;&#x30DD;&#x30B8;&#x30C8;&#x30EA;&#x3067;&#x7BA1;&#x7406;&#x3055;&#x308C;&#x3066;&#x3044;&#x307E;&#x3059;&#xFF0E; https://github.com/mruby/mruby

Nov 2, 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