#golangkyoto 「そうだ、 Go 京都」で「Go に String::Random を移植した話」というタイトルで発表した

これは「そうだ、 Go 京都」で発表した内容をブログ用に起こしたものです。発表スライド自体は公開する予定はありませんが、内容としてはより詳しくなっているはずなのでご容赦ください。

developer.hatenastaff.com

直帰ユーザーにも分かるように最初に宣伝しておくと正規表現によって文字列を生成できる CLI / package を作りました。

% gocha -n 5 '[カコヵか][ッー]{1,3}?[フヒふひ]{1,3}[ィェー]{1,3}[ズス][ドクグュ][リイ][プブぷぶ]{1,3}[トドォ]{1,2}'
カッーひふふーーィスドリブブぷド
コッーーふェズュイぷプトト
カッひふヒィェースュリぶブト
カッフヒふィーェズクリブォ
ヵーひフヒィースグリプトド

家族を生成したりできます。

% gocha -n 5 '[👨👩]\x{200D}[👨👩]\x{200D}[👧👦](\x{200D}[👧👦])?'

👨‍👩‍👧‍👧
👩‍👩‍👦
👩‍👨‍👧 　
👨‍👨‍👦
👨‍👩‍👦‍👧 　
(バッククオート内だとうまく表示されないので外に出してます。)

go で使える正規表現の記法は全部使えると思います。

% gocha -n 1 '\p{Hiragana}{4}'
おねよろ

% gocha -n 1 '(?i)[a-z]{4}'
ſJjm

% gocha -n 1 '[^\D]{4}'
0844

はじめに

発表の趣旨としては String::Random の移植を通じて Go を学びましたというものです。前半に実装方針、後半にコマンドラインツールにする際の一般的なハマりどころやアプローチを紹介しました。話はやや発散しています。

packageとしてもコマンドラインツールとしても使用できるようにしましたが、どちらも名前は gocha です。ランダムということで「ガチャ」と掛けています。

String::Random とは

正規表現に従ってランダムな文字列を生成してくれる perl モジュールです。使い方としては以下のとおりです。

% perl -MString::Random -le 'my $sr = String::Random->new; print $sr->randregex("[a-zA-Z1-9_]{1,20}") for (1..10);'
1mxL
5KSIpwf76XP3A
qS9w
h4mEXPwElOhm28hr
yfr_ny5nMGnNX9hDU
cAPGkgJdL
HFYPc
sfPn2tSTOaUucfIl
jh5CfFZNdgh6BzL54
TW7ALHVFSjarqqF

この例では [a-zA-Z1-9_]{1,20} にマッチする文字列を 10 個作っています。

何に使うのか

主な用途はテストでしょうか。テストでユーザーを作るみたいな場合ユーザー名はランダムで作りたい、ということが多いと思います。他の用途としては余り思いつかないですが、社内でもおそらくテストにしか使っていません。(逆に言うとテストではほぼ100%使っている人気モジュールです。)なくもどうにかなるモジュールですがあったほうが何かと便利です。

ちなみにセキュアなランダム文字列を生成するわけではないのでセキュリティ関連で使うのはご法度です。その点は gocha も同様です。

実装方針1

素朴な正規表現エンジンを作ってみる

そもそも正規表現エンジンがどういう動作をするのかわからなかったので DFA エンジンを実装して見るところから始めました。

github.com

今回実装した正規表現エンジンでは基本3演算子である

連接
選択
くり返し

しか解釈できません。つまり記号としては | と * とグループ化の () です。

しかしながら文字クラスや量指定子も基本3演算子だけで表現できる糖衣構文であるため今は十分です。このへんの解説は正規表現技術入門の第一章で詳しく解説されています。

実装する際は正規表現エンジンを作ろう（1） (1/3)：CodeZine（コードジン）を大いに参考にしました。他にも正規表現技術入門 ――最新エンジン実装と理論的背景：書籍案内｜技術評論社やO'Reilly Japan - 詳説正規表現第3版を読みました。

DFA エンジンの実装については深入りしません。上述の記事では parser すら実装したこともない僕でも実装できるくらい丁寧に解説されているのでそちらを読んで下さい。

どのようにランダム文字列を作るか

素朴な正規表現エンジンを実装し学んだ過程から構文木さえ生成できれば、後はどうにかなりそうということがわかりました。以下その手法です。

a|(bc)* の構文木は以下のような形になります。

各 token は

Union は |
Star は *
Concat は ()
Character は文字列

という対応です。

構文木からランダム文字列を生成する

"計算"規則は以下のようになります。

Union → 子ノードのうちどちらかを選ぶ(ランダム要素)
Star → 0 回以上適当な回数繰り返す(ランダム要素)
Concat → 子ノードを結合する
Character → そのままその文字を使う

Union と Star はランダム要素なので実装によって結果が違います。Union に関しては子ノードを等確率で選べば良いですが、Star に関しては検討の余地があります。すなわち a* にマッチングする文字列は空文字、a、aa、aaa、...と無限に存在します。とは言え *a と気軽に指定したらとんでもなく巨大な文字列が生成されても困るので、適当な数で区切ります。つまり * の場合は 0 から 10 回ランダムに繰り返すという感じです。

実際にランダムな文字列を生成する手順です。葉から計算していく Character として確定させていく感じです。

Character は特に何もすることはないので a が確定します
b を確定させます
c を確定させます
Concat は子ノードをつなげれば良いので bc です
Star は繰り返しなので bc や bcbc や bcbcbc です。ここでは bcbcbc とします
a か bcbcbc のうちどちらかを選びます。ここでは a とします

というプロセスで a|(bc)* から a を生成することができます。

Union と Star はランダム要素なので同じ構文木から

a
bc
bcbc
空文字

といった他の文字列も生成される可能性があります。

この実装の問題点

対応できていない記法がまだ大量にあります。

文字クラス
- [a-z] \d
量指定子
- ? {2,4}
Unicode文字プロパティ、ブロック、スクリプト
- \p{L} \p{HAN}
オプション
- (?i)
否定
- [^a-z]

解決策？

* | () だけ解釈できれば基本的には他の記法は糖衣構文であるため理論的にはこの方針で対応できます。すなわち

\d → 0|1|2|3|4|5|6|7|8|9
x{1,3} → x|xx|xxx

のように一つ一つ丁寧に変換則を書いて実装していくということです。

ですが実際には現実的ではないでしょう。例えば

Unicode 文字プロパティやスクリプトの全てに対応するには数が多すぎる
i オプションは意外と難しい
- (?i)[a-z] は [a-zA-Z] と等価ではない
  - 全社には LATIN SMALL LETTER LONG S と KELVIN SIGN

などの Unicode の膨大な知識と、それを実装する気力が必要になってきます。現実的ではないレベルだと思います。

使用頻度の高いものだけ対応するという方針も考えられます。実際に Perl の String::Random は Perl が使える正規表現よりだいぶ使える記法が狭いです。

実装方針2

Go が対応する正規表現にはすべて対応したいので、 Go の標準パッケージに乗ることを考えます。

regexp/syntax

Prog 構造体が定義されています。これは Go の正規表現(Go の正規表現エンジンはVM型です)が使う program を表現した構造体です。実際に Println したものを見てみるとバイトコードっぽい表示がされるのでイメージしやすいでしょう。

pattern := `a|b`
exp, _ := syntax.Parse(pattern, syntax.Perl)
prog, _ := syntax.Compile(exp.Simplify())

fmt.Println(prog)

// 0     fail
// 1*    rune "ab" -> 2
// 2     match

というわけで実装方針2は Prog を利用します。すなわちオペランドから文字列しつつ program counter をすすめ match に到達することを目指します。

オペランドの一覧はsyntax - The Go Programming Languageにありますのでこれらに対応する操作を考えていきます。

例を見ていきましょう。

a{1,3}

0     fail
1*    rune1 "a" -> 5
2     rune1 "a" -> 4
3     rune1 "a" -> 6
4     alt -> 3, 6
5     alt -> 2, 6
6     match

* がついているのが初期位置です。rune1 ( InstRune1 )は特に考えることなく 'a' を確定させ 5 へ進みます。 alt は進み先をランダムに選べばよいです。この場合 3 か 6 になります。6 に移った場合生成文字列は a となります。 2 に移った場合は同じ事を繰り返す aa や aaa などが生成されます。

[a-c]

0     fail
1*    rune "ac" -> 2
2     match

rune の場合は a Unicode コードポイントから c のコードポイントまでのうちランダムで選ぶという操作をします。これにより a か b か c が生成されます。

このように InstOp に対応する操作を全て定義すれば完成です。

この方針の問題点

a* を指定したときの偏り
- alt を等確率で分岐させているのでくり返しが少ない方に偏ります

% gocha -n 100000 'a*' | sort | uniq -c
50054
24894 a
12633 aa
6278 aaa
2994 aaaa
1517 aaaaa
 809 aaaaaa
 400 aaaaaaa
 206 aaaaaaaa
 109 aaaaaaaaa
  54 aaaaaaaaaa
  22 aaaaaaaaaaa
  15 aaaaaaaaaaaa
   7 aaaaaaaaaaaaa
   4 aaaaaaaaaaaaaa
   3 aaaaaaaaaaaaaaa
   1 aaaaaaaaaaaaaaaa

文字集合が広い
例えば . を指定した場合全てのコードポイントから等確率で選ばれるので大抵は表示できないような文字がでます

一つ目はランダムとは何かという話になるのでこんなもんかなと思っています。例えば a と a x 100000000000000 の文字列が等確率で出ても困るし、ある程度( x 10 )くらいで区切るくらいならば確率に任せたいという気持ちです。単純に今の仕組みだと実装が難しいというのももちろんあります。

2つ目に関しては文字クラスがあるので適切に指定してほしいです。

コマンドラインツールにする

ファイル配置

Goのファイル配置はパッケージの単位とファイルの単位が一致しいない為難しく感じるのですが、どのように使わせたいかを考え以下のように決定しました。つまり

packageとしては

import (
    "github.com/t-mrt/gocha"
)

コマンドラインとしては

$ go get github.com/t-mrt/gocha/cmd/gocha

のようにインストールできる配置です。

.
├── README.md
├── build.pl
├── cmd
│   └── gocha
│       ├── cli.go      - 実際のCLIでの処理
│       ├── cli_test.go
│       ├── main.go     - 標準入力、出力、エラーを渡し、exitコードを返すだけ
│       └── version.go
├── dist
│   └── 成果物.zip
├── gocha.go             - gocha本体
└── gocha_test.go        - テスト

テスタビリティの高い CLI ツールの書き方

main() にはとにかく何もさせず CLI に任せるという方針です。

package main

import "os"

func main() {
    cli := &CLI{outStream: os.Stdout, errStream: os.Stderr}
    os.Exit(cli.Run(os.Args))
}

これにより出力結果や引数のパースや exit code までテストできます。

テストでは CLI に bytes.Buffer を渡しexit code はその返り値として表現されます。

func TestRun(t *testing.T) {
    t.Run("ExitCodeOK", func(t *testing.T) {
        outStream, errStream := new(bytes.Buffer), new(bytes.Buffer)
        cli := &CLI{outStream: outStream, errStream: errStream}
        args := strings.Split("gocha -n 1 '[a]{3}'", " ")
        status := cli.Run(args)

        if status != ExitCodeOK {
            t.Errorf("ExitStatus=%d, want %d", status, ExitCodeOK)
        }

        expected := fmt.Sprintf("")
        if errStream.String() != expected {
            t.Errorf("Output=%q, want %q", errStream.String(), expected)
        }

        expected = fmt.Sprintf("'aaa'\n")
        if outStream.String() != expected {
            t.Errorf("Output=%q, want %q", outStream.String(), expected)
        }
    })
}

コマンドライン引数解析 package 選定

gocha では alecthomas/kingpin を使いました。詳しくは

blog.yux3.net

ベンチマーク

標準でベンチマークツールがついてくるので便利。

func BenchmarkGenN(b *testing.B) {
    _, g := New(`[a-zA-Z]{1000}`)
    g.GenN(5000)
}

% go test  -count 10 -bench BenchmarkGenN
BenchmarkGenN-4                1        2235998736 ns/op
BenchmarkGenN-4                1        2294084063 ns/op
BenchmarkGenN-4                1        2339268452 ns/op
BenchmarkGenN-4                1        2333507380 ns/op
BenchmarkGenN-4                1        2378251220 ns/op
BenchmarkGenN-4                1        3409727990 ns/op
BenchmarkGenN-4                1        2410747070 ns/op
BenchmarkGenN-4                1        2353380556 ns/op
BenchmarkGenN-4                1        2284454174 ns/op
BenchmarkGenN-4                1        2454841612 ns/op
PASS
ok      github.com/t-mrt/gocha  24.548s

goroutine ってやつ使えば並列になって速くなるんでしょ？って感じで何となく書いたけど、ベンチマーク取ったら大して早くならなかったのでやめました。*1

質問で id:y_uuki さんから処理内容がしょぼいので goroutine 生成のオーバーヘッドのほうが大きそうという指摘頂きました。

バイナリ配布

https://github.com/t-mrt/gocha/blob/master/build.pl

version.go からバージョンを取得し github releases にアップロードするまでの手順ですがあんまり完成度高くないです。最後は手でやってますし。 version.go つくったのは gocha -v に対応したかったからですが、今見ると対応してないです。

バイナリ配布しても使ってもらう人がいないのでモチベーション低くとりあえず揃えた感じなのでご勘弁を。

まとめ

go で String::Random の移植版 gocha を作りました
- 本家より高性能色々な記法に対応してるし、コマンドラインツールも用意したので使ってください
go はコアパッケージも go で書かれてて勉強になる
- 利用もできるので今回みたいな事もできる
go 始めたいけど作りたくないものがない場合、他言語の便利モジュール移植が手軽
作成の際は「みんなのGo言語」を大いに参考しました
- おすすめです

*1:ちなみに使い方間違っていたらしくPR頂きました

角待ちは対空

おもむろガウェイン