1998年、GoやPlan 9で知られるRob Pikeは、Unixハッカー仲間のBrian Kernighanと共著した『The Practice of Programming』のために、C言語でシンプルな正規表現マッチャーを書きました。Kernighanによるこのコードの「解釈」をまだ読んでいないなら、じっくり読むのに必要な30分は間違いなく費やす価値があります。

GoがCの流れを汲んでいること（そしてGo言語に対するPikeの影響）を考え、CのコードがどれくらいうまくGoに移植できるのか、そして移植してもなおエレガントさを保てるのか試してみようと思いました。

オリジナルのC版

まず、Pikeのオリジナルのマッチングコードを見てみましょう。扱う正規表現のメタ文字は.、*、^、$のごく少数に限られていますが、Kernighanによれば日常的な使用例の「95%は軽くカバーできる」うまく選ばれたサブセットです。

試しに自分の.bash_historyからgrepの使用履歴をgrepしてみましたが（なんともメタ的ですね！）、割合は似たようなものでした。ただ、私の場合は約10%でエスケープされたメタ文字（たいていは\.）も使っていました。

以下が、オリジナルの35行からなるC言語のマッチャーです。

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
    if (regexp[0] == '^')
        return matchhere(regexp+1, text);
    do {    /* must look even if string is empty */
        if (matchhere(regexp, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
    if (regexp[0] == '\0')
        return 1;
    if (regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
        return matchhere(regexp+1, text+1);
    return 0;
}

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
    do {    /* a * matches zero or more instances */
        if (matchhere(regexp, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}

美しいですよね？このコードの解説はここではしません。私がするよりもはるかに優れた解説を、Kernighanが「A Regular Expression Matcher」という記事でしています。

Goへの移植

もちろんGoの文字列はchar*ポインタを使いませんが、text[1:]のような文字列のインデックスやスライス操作は（言うなれば）かなり近い対応関係にあります。

Kernighanが指摘しているように、do-whileはCでも比較的珍しい構文ですが、ここでは必要とされています。おそらく幸いなことに、Goにはdo-whileがないので、代わりにループの中でif文を使って早期リターンするようにしています。いずれにせよ、*text++のようなフェッチ＆インクリメント式が使えない以上、do-whileはここでは役に立ちません。

do-whileがないことや、波括弧なしの1行if文が書けないこともあって、Goでは行数が増える部分がいくつかあります。ただ、matchHere内の連続したif文をベアなswitchに置き換えたことで、この関数はC版とほぼ同じくらい簡潔になっています。

Goの文字列のおかげでシンプルになった部分もあります。例えばregexp[0] == '$' && regexp[1] == '\0'は単にregexp == "$"と書けます。

それでは、前置きはこのくらいにして、私のGo版を紹介します（完全なソースはこちら）：

// Match reports whether regexp matches anywhere in text.
func Match(regexp, text string) bool {
    if regexp != "" && regexp[0] == '^' {
        return matchHere(regexp[1:], text)
    }
    for {
        if matchHere(regexp, text) {
            return true
        }
        if text == "" {
            return false
        }
        text = text[1:]
    }
}

// matchHere reports whether regexp matches at beginning of text.
func matchHere(regexp, text string) bool {
    switch {
    case regexp == "":
        return true
    case regexp == "$":
        return text == ""
    case len(regexp) >= 2 && regexp[1] == '*':
        return matchStar(regexp[0], regexp[2:], text)
    case text != "" && (regexp[0] == '.' || regexp[0] == text[0]):
        return matchHere(regexp[1:], text[1:])
    }
    return false
}

// matchStar reports whether c*regexp matches at beginning of text.
func matchStar(c byte, regexp, text string) bool {
    for {
        if matchHere(regexp, text) {
            return true
        }
        if text == "" || (text[0] != c && c != '.') {
            return false
        }
        text = text[1:]
    }
}

C版の35行に対してGo版は43行です。言語に対するPikeの影響もあってか、Go版でもオリジナルのCのエレガンスの多くが保たれていると思います。

最初のバージョンはほんの少しだけ異なり、4行長くなっていました。matchHere内の連続するifをswitchに置き換えるなど、いくつかの点をシンプルにしました。Goのコードをよりシンプル、あるいはよりエレガントにする提案があれば、ぜひ教えてください。

追記：GitHubユーザーのMoiTuxさんが私のバージョンを37行まで短縮するPRを送ってくれました。MatchとmatchStarのループ条件とtext = text[1:]という文をfor行にまとめ、さらに空文字列のケースを扱うためにループの後でもう一度matchHereを呼び出すようにしたのです。完全なソースはこちら。 巧妙ですね！

テスト

Go版が正しく動作することを確認するため、さまざまなエッジケースを（おそらく）カバーするテーブル駆動のテストをたくさん追加しました。各テストは自作のGo版だけでなく、Goのregexpパッケージでも実行しています。さらにos/execを使って各テストをオリジナルのC版でも実行し、結果が一致することを確認しています。

これにはGoのサブテストを使っています。t.Runの呼び出しでサブテストを設定します。実際の動きを示すため、テストコードの大部分を以下に掲載します。

type test struct {
    name    string
    re      string
    text    string
    matched bool
}

var tests = []test{
    {"EmptyBoth", "", "", true},
    {"EmptyRegex", "", "foo", true},
    {"EmptyText", "foo", "", false},
    // ... snipped for brevity ...
}

func TestMatch(t *testing.T) {
    _, err := os.Stat("./matchc")
    haveC := err == nil // does the compiled C version exist?

    for _, test := range tests {
        // Ensure Go matcher passes.
        t.Run(test.name+"/repike", func(t *testing.T) {
            matched := repike.Match(test.re, test.text)
            if matched != test.matched {
                t.Fatalf("got %v, want %v", matched, test.matched)
            }
        })

        // Ensure test passes using Go's regexp package.
        t.Run(test.name+"/regexp", func(t *testing.T) {
            matched, err := regexp.MatchString(test.re, test.text)
            if err != nil {
                t.Fatalf("compile error: %v", err)
            }
            if matched != test.matched {
                t.Fatalf("got %v, want %v", matched, test.matched)
            }
        })

        // Ensure test passes using original C matcher.
        if haveC {
            t.Run(test.name+"/matchc", func(t *testing.T) {
                cmd := exec.Command("./matchc", test.re)
                cmd.Stdin = strings.NewReader(test.text + "\n")
                err := cmd.Run()
                // ... snipped for brevity ...
            })
        }
    }
}

ベンチマーク

それぞれのマッチャー（およびgrep）を使ったgrep風のマッチングプログラムのベンチマークを実行しました。欽定訳聖書を100回連結したテキストに対して、正規表現Ben.*Hでマッチさせています。

Goへの移植版がオリジナルのC版（gcc -O2でコンパイル）とほぼ同じ速度だったのは嬉しい驚きでした。再帰的な構造のため、生成されるコードが両者でかなり似通っているのだと思います。

Goのregexpパッケージは遅いことで知られており、しかもUnicodeを正しく扱うため、少なくともシンプルなマッチャーと同じくらい遅いだろうと思っていました。しかし実際にはほぼ2倍速かったのです。なぜそうなるかは読者への課題としておきますが、私の推測では、このケースでは再帰を使っていないためで、再帰的な関数呼び出しは比較的遅いからです。

もちろん、GNU Grepは約3倍高速です。なぜGNU Grepがこれほど速いのかについては、FreeBSDメーリングリストへの古典的な投稿を読んでみてください。

以下は、私のノートPCでの結果（5回中ベスト）を速い順に並べた表です。

参考までに、使用したのはGCCバージョン11.2、Goバージョン1.18.1、GNU Grep 3.7で、システムは64ビットLinux、2.6GHzのi7-6700HQ CPUを搭載しています。

おまけ：globマッチャー

この件であれこれ寄り道しているうちに、Goで?と*によるワイルドカード形式のマッチングを行う、シンプルな28行のglobマッチャーも書いてみました。パターンとテキストを同時にループで走査し、*のケースでは再帰を使うという、似たような実装になっています。

ソースコードは以下に掲載します（gistにもあります）：

func match(pattern, name string) bool {
    for pattern != "" {
        p := pattern[0]
        pattern = pattern[1:]
        switch p {
        case '*':
            for pattern != "" && pattern[0] == '*' {
                pattern = pattern[1:]
            }
            for i := 0; i <= len(name); i++ {
                if match(pattern, name[i:]) {
                    return true
                }
            }
            return false
        case '?':
            if name == "" {
                return false
            }
        default:
            if name == "" || p != name[0] {
                return false
            }
        }
        name = name[1:]
    }
    return name == ""
}

まとめ

Pikeのコードは有用で、教訓に富み、そして美しいと思います。Kernighanの記事を読み、コードを移植し、この記事を書く過程を私自身とても楽しんだので、読者の皆さんにも楽しんでいただければ幸いです。

なお、C版もGo版もUnicodeを適切に扱っていないことに注意してください。UTF-8入力でも動作はしますが、.やc*はマルチバイト文字を正しくマッチしません（とはいえ多くの場合は問題にならないでしょう）。Go版でこれを修正する最も簡単な方法は、処理を始める前にregexpとtextの文字列をルーンのスライス（[]rune）に変換し、そこから同じアルゴリズムを使うことです。

もちろん、a.*a.*a.*a.aのような巧妙に作られた正規表現でも実行時間がひどくならない、より優れた正規表現マッチングの実装方法もありますが、それについてはRuss Coxの記事「Regular Expression Matching Can Be Simple And Fast」を読んでみてください。

お読みいただきありがとうございました！