早在 1998 年，以 Go 和 Plan 9 聞名的 Rob Pike 為他與 Unix 駭客夥伴 Brian Kernighan 合著的《The Practice of Programming》一書，用 C 寫了一個簡易的正則表達式匹配器。如果你還沒讀過 Kernighan 對這段程式碼的「釋義」，絕對值得花 30 分鐘慢慢細讀。

考量到 Go 繼承了 C 的血統（以及 Pike 對 Go 語言的影響），我想試試看這段 C 程式碼轉譯成 Go 會有多順利，是否依然優雅。

原始 C 版本

首先來看看 Pike 原始的匹配程式碼。它只處理少數幾個正則表達式的元字元，也就是 .、*、^ 和 $，但這是經過精心挑選的子集，Kernighan 說這「輕鬆涵蓋了他日常使用中 95% 的情況」。

我剛用 grep 搜尋了自己的 .bash_history 裡 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 判斷並提早 return。除此之外，就算有 do-while 也幫不上太多忙，因為我們還是無法使用像 *text++ 這種取值並遞增的寫法。

有不少地方在 Go 中需要更多行數，一部分是因為沒有 do-while，另一部分則是因為不能寫不加大括號的單行 if。不過，我把 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 提交了一個 PR，把我的版本縮短到了 37 行。他把 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），以正則表達式 Ben.*H 去匹配由King James Bible 串接 100 次而成的文本。

讓我有點驚喜的是，Go 的轉譯版本速度竟然和原始的 C 版本（以 gcc -O2 編譯）差不多。我猜是因為其遞迴結構，使得兩者產生的程式碼相當類似。

Go 的 regexp 套件出了名的慢，而且它還要正確處理 Unicode，所以我原本以為它的速度至少會和這些簡易匹配器一樣慢。然而，它的執行速度卻快了將近一倍。至於原因，就留給讀者當作練習；我的猜測是，在這個情況下它並非採用遞迴，而遞迴函式呼叫相對來說比較慢。

當然，GNU Grep 的速度大約快了三倍。想了解為何 GNU Grep 如此快速，可以參考這篇經典的 FreeBSD 郵件論壇貼文。

以下是我的筆電上五次測試中最佳成績的結果表格，依速度由快到慢排列：

僅作記錄，我使用的是 GCC 11.2 版、Go 1.18.1 版以及 GNU Grep 3.7。我的系統是 64 位元 Linux，搭載 2.6GHz 的 i7-6700HQ CPU。

番外篇：glob 匹配器

在研究這些東西分心的過程中，我還用 Go 寫了一個簡單的 28 行 glob 匹配器，可處理 ? 和 * 這類萬用字元匹配。它採用類似的實作方式，同時遍歷 pattern 和 text，並在處理 * 時使用遞迴。

原始碼如下（另有 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 切片（[]rune），然後再套用相同的演算法。

當然，也有更好的正則匹配實作方式，不會在像 a.*a.*a.*a.a 這種精心構造的正則表達式上出現糟糕的執行時間，但這部分就請閱讀 Russ Cox 的文章〈Regular Expression Matching Can Be Simple And Fast〉來了解更多。

感謝閱讀！