早在 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 并提前返回的方式。况且，就算有 do-while 也帮不上太多，因为我们仍然无法使用 *text++ 这样的取值并自增表达式。

有不少地方在 Go 里会多占几行，一部分是因为没有 do-while，另一部分则是因为 Go 里不带花括号就不能写单行 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:]
    }
}

这一版是 43 行，而原版是 35 行。一定程度上得益于 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 的匹配程序的基准测试，在一份拼接了 100 遍的《钦定版圣经》上匹配正则 Ben.*H。

令我惊喜的是，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，CPU 为 2.6GHz 的 i7-6700HQ。

彩蛋：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 切片（[]rune），然后再用同样的算法处理。

当然，还有更好的正则匹配实现方式，可以避免在 a.*a.*a.*a.a 这类精心构造的正则上出现糟糕的运行时间，想了解更多可以去读 Russ Cox 的文章《Regular Expression Matching Can Be Simple And Fast》。

感谢阅读！