0에서 11까지 버그 수정: GoAWK가 내 3000배 빠른 Regex Engine을 검증한 방법

Source: Dev.to

가장 좋은 피드백

일주일 전, 나는 “Go’s Regexp is Slow. So I Built My Own”를 발표했습니다. 반응은 놀라웠지만, 가장 가치 있는 피드백은 Ben Hoyt에게서 왔습니다. 그는 GoAWK의 제작자입니다.

그는 단순히 글을 읽지 않았습니다. 그는 실제로 coregex를 사용해 보았습니다.

“I’ve started integrating coregex into GoAWK… I’m finding a few issues.”

그 메시지는 내가 경험한 가장 생산적인 디버깅 주 중 하나로 이어졌습니다.

7일 동안 11개의 버그

Ben의 GoAWK 테스트 스위트는 가혹합니다 – 내가 상상도 못한 에지 케이스를 포함한 1000개 이상의 정규식 패턴. 그가 찾은 내용은 다음과 같습니다:

각 버그는 나에게 무언가를 가르쳐 주었습니다. 일부는 당혹스러운 실수였고, 다른 일부는 내 이해의 근본적인 공백을 드러냈습니다.

가장 심각한 버그: ^ 앵커

시작 앵커(^)는 나의 적이었습니다. 간단해 보였죠 – 위치 0에서만 매치. 하지만 다중 엔진 아키텍처에서는 “간단함”이 금방 복잡해집니다.

• 버전 1 – 순진하게 pos == 0을 확인했습니다. IsMatch에서는 동작했지만 FindAllIndex에서는 깨졌습니다.
• 버전 2 – FindAt(haystack, offset) 메서드를 추가했습니다. 이제 FindAllIndex는 엔진에 “원본 문자열의 위치 5”임을 알릴 수 있었습니다.
• 버전 3 – DFA의 epsilonClosure가 앵커를 무시한다는 것을 발견했습니다. Rust의 regex‑automata를 따라 적절한 LookSet을 구현했습니다.

2일에 걸친 세 번의 시도. Ben은 계속 테스트했고, 나는 계속 수정했습니다.

가장 교묘한 버그: Longest()

이 버그는 겸손하게 만들었습니다. Longest() 메서드는 v0.8.2부터 존재했지만, 문서는 작동한다고 주장했고 테스트도 통과했지만 실제로는 아무 동작도 하지 않는 스텁이었습니다.

// What I wrote (v0.8.2)
func (r *Regex) Longest() {
    // TODO: implement leftmost-longest semantics
}

// What Ben expected
re := coregex.MustCompile(`(a|ab)`)
re.Longest()
// "ab" should match "ab" (longest), not "a" (first)

AWK는 POSIX 의미론(왼쪽-가장-긴)을 사용합니다. Go 표준 라이브러리는 기본적으로 Perl 의미론(왼쪽-가장-첫)을 사용하지만, Longest()는 모드를 전환합니다. 내 엔진은 Perl 의미론만 지원했습니다.

수정에는 근본적인 구분을 이해해야 했습니다:

Leftmost‑First (Perl):   (a|ab) on "ab" → "a" (first alternative wins)
Leftmost‑Longest (POSIX): (a|ab) on "ab" → "ab" (longer match wins)

이를 PikeVM에 구현하는 데 약 100줄이 필요했습니다. 기본 모드에서는 성능 저하가 없습니다.

수정 속도