1998년, Go와 Plan 9로 유명한 Rob Pike는 동료 유닉스 해커 Brian Kernighan과 함께 쓴 책 The Practice of Programming을 위해 C로 간단한 정규식 매처를 작성했다. Kernighan이 쓴 이 코드에 대한 “주해”를 아직 읽어보지 않았다면, 천천히 읽어보는 데 30분 정도를 투자할 가치는 충분히 있다.

Go가 C의 전통을 이어받은 데다 Pike가 Go 언어에 끼친 영향까지 생각하면, 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++ 같은 fetch-and-increment 표현식을 쓸 수 없기 때문에 do-while이 있더라도 여기서는 별 도움이 되지 않는다.

여러 부분이 Go에서 더 많은 줄을 차지하는데, 일부는 do-while이 없기 때문이고, 또 중괄호 없이 한 줄짜리 if문을 쓸 수 없기 때문이다. 다만 matchHere에 연속된 if문들을 bare 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 패키지는 느리기로 알려져 있고 유니코드도 올바르게 처리하므로, 단순한 매처들만큼은 느릴 거라 예상했다. 하지만 거의 두 배나 빨랐다. 왜 그런지는 독자를 위한 연습 문제로 남겨두겠다. 내 추측으로는 이 케이스에서는 재귀를 쓰지 않기 때문이며, 재귀 함수 호출은 상대적으로 느리다.

물론 GNU Grep은 약 세 배 더 빠르다. GNU Grep이 왜 그렇게 빠른지 더 알고 싶다면 이 유명한 FreeBSD 메일링 리스트 글을 읽어보라.

내 노트북에서 측정한 결과(5회 중 최고 기록)를 빠른 순으로 정리하면 다음과 같다:

참고로 GCC 11.2, Go 1.18.1, GNU Grep 3.7을 사용했고, 시스템은 2.6GHz i7-6700HQ CPU를 탑재한 64비트 Linux다.

보너스: 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 버전 모두 유니코드를 제대로 처리하지 않는다는 점에 유의하자. UTF-8 입력에서는 동작하지만 .나 c*가 멀티바이트 문자를 올바르게 매칭하지 못한다(다만 많은 경우 문제가 되지 않는다). Go 버전에서 이를 고치는 가장 간단한 방법은 시작 전에 regexp와 text 문자열을 룬 슬라이스([]rune)로 변환한 뒤 같은 알고리즘을 사용하는 것이다.

물론 a.*a.*a.*a.a처럼 교묘하게 만든 정규식에서 끔찍한 실행 시간을 보이지 않는 더 나은 정규식 매칭 구현 방법도 있지만, 그에 대해서는 Russ Cox의 글 “Regular Expression Matching Can Be Simple And Fast”를 읽어봐야 한다.

읽어줘서 고맙다!