정규식 엔진 내부를 라이브러리로

 (blog.burntsushi.net)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Rust regex crate는 수년간의 재작성 끝에 내부 엔진 상당 부분을 별도 버전의 regex-automata crate API로 공개했고, regex 1.9에서 전환이 완료됨
  • 재작성은 검색 전략의 조합 어려움, 내부 엔진별 테스트 난이도, RegexSet보다 세밀한 다중 패턴 API 요구, 완전 컴파일 DFA 공유 필요에서 출발함
  • regex-automata는 Ast → Hir → 리터럴 추출/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine 흐름으로 정규식 처리를 구성함
  • 성능은 가능한 한 리터럴 검색과 DFA 계열 엔진을 먼저 쓰고, 캡처 그룹이나 예외 상황에서는 PikeVM·bounded backtracker·one-pass DFA로 보완하는 방식으로 확보함
  • 공개 API와 재사용 가능한 추상화는 테스트와 실험을 쉽게 만들었지만 코드량, 바이너리 크기, 컴파일 시간이 늘어났고, 완전 컴파일 DFA는 opt-in으로 두며 regex-lite 가 경량 대안으로 추가됨

regex 재작성과 regex-automata 공개

  • Rust의 regex crate는 내부 조합을 개선하고 최적화를 더 쉽게 추가하면서 정확성을 유지하기 위해 수년간 재작성됨
  • 이 과정에서 regex-automata가 만들어졌고, regex crate 내부 구현 상당 부분을 별도 API로 노출함
  • regex-automata는 정규식 라이브러리 내부를 이 정도로 별도 버전 라이브러리로 공개한 첫 사례로 소개됨
  • regex 1.9는 2023년 7월 5일 릴리스되며 이 재작성을 완료함
  • Rust 프로그래머와 유한 오토마타 기반 정규식 엔진 구현에 관심 있는 사람을 대상으로 하며, 정규식 경험을 전제로 함

재작성 이전의 문제들

  • 기존 regex crate는 RE2 전통을 따라 여러 검색 전략을 내부적으로 사용했지만, 전략들이 유기적으로 추가되며 조합이 어려워짐
    • PikeVM은 최초 전략으로 설계되어 lazy DFA와 조합할 때 필요한 부분 슬라이스 검색 시작·중단 처리가 부족했음
    • 어떤 정규식에 어떤 전략이 쓰이는지 추론하기 어려웠음
    • 여러 match 표현식이 같은 로직을 반복 구현해 동기화가 어긋나기 쉬웠음
    • Aho-Corasick만 쓰면 되는 정규식에서도 사용하지 않을 Thompson NFA가 불필요하게 만들어질 수 있었음
  • 내부 엔진 테스트도 까다로웠음
    • 공개 API는 하나의 정규식 엔진처럼 보이지만 내부에는 여러 전략이 있고, 같은 입력에서 동일하게 동작해야 함
    • regex 1.9 이전에는 내부 전략이 공개 API가 아니어서 각 엔진을 독립적으로 테스트하기 어려웠음
    • 기존 테스트는 내부 API 노출, 문서화되지 않은 From 구현, 매크로, 엔진별 테스트 타깃에 의존하는 해킹에 가까운 구조였음
  • 여러 니치 API 요청도 기존 API 표면에 넣기 애매했음
    • RegexSet은 어떤 패턴이 haystack 어디엔가 매치됐는지만 알려주고, 매치 오프셋이나 캡처 그룹 오프셋은 제공하지 않음
    • 패턴에 ^를 넣지 않고 anchored 검색을 실행하는 기능이 필요했음
    • 검색 중 내부 동기화 없이 mutable scratch space를 직접 전달하는 기능이 요구됨
    • 스트림이나 rope 같은 비연속 haystack에서 정규식을 실행하는 기능도 요청됨
  • 별도 버전 crate로 내부를 공개하면 일반 목적 regex API를 복잡하게 만들지 않고, 전문가용 API를 더 빠른 breaking change 주기로 실험할 수 있음

완전 컴파일 DFA가 만든 추상화 경계

  • regex-automata의 초기 동기는 완전 컴파일 DFA를 만들고 직렬화한 뒤, zero-copy 역직렬화로 검색하는 최소 런타임을 제공하는 것이었음
  • 초기 regex-automata는 bstr의 Unicode 알고리듬 구현용 DFA를 만드는 데 쓰임
  • DFA를 만들다 보니 regex crate와 유사한 NFA 자료구조와 컴파일러가 필요했고, 이 코드가 복잡해지면서 공유 필요성이 커짐
  • 처음에는 regex-nfa 같은 별도 crate를 고려했지만, determinization 과정 등 더 많은 코드가 regex와 regex-automata 사이에서 공유될 수 있었음
  • 추상화 경계는 “NFA”보다 정규식 엔진에 가까웠고, 최종적으로 regex-automata는 여러 엔진의 집합으로 재정의됨
  • 장기 계획은 모든 정규식 엔진을 regex-automata에 두고 regex crate를 그 위의 얇은 래퍼로 만드는 것이었음

regex-cli로 내부 구조 확인

  • regex-cli는 regex crate 저장소에서 관리되는 프로그램으로, regex-syntax, regex-automata, regex의 여러 API에 명령줄 접근을 제공함
  • 설치는 다음 명령으로 가능함
cargo install regex-cli
  • regex-cli debug는 AST, HIR, 리터럴, Thompson NFA, one-pass DFA, dense DFA, sparse DFA 등을 출력할 수 있음
  • Unicode가 켜진 . 정규식은 UTF-8 scalar value를 처리하기 위해 훨씬 복잡한 Thompson NFA를 만들고, Unicode가 꺼진 (?-u:.)는 더 단순한 NFA를 만듦
  • regex-cli find는 임시 검색을 실행할 수 있고, meta engine으로 다중 패턴 검색과 캡처 그룹 출력도 가능함

정규식 처리 데이터 흐름

  • Regex::new에 전달된 패턴 문자열은 먼저 Ast로 파싱됨
  • Ast는 Hir로 변환됨
    • Hir는 Ast보다 세부 정보가 적고, Unicode case folding과 Unicode character class 참조가 변환 중 확장됨
  • Hir에서는 두 가지가 만들어짐
    • 검색 최적화에 쓰이는 리터럴 시퀀스
    • Thompson NFA
  • NFA는 여러 엔진을 만드는 기반이 됨
    • PikeVM: 파싱 가능한 모든 정규식을 처리하고 캡처 그룹 오프셋을 보고함
    • BoundedBacktracker: bounded backtracking으로 캡처 그룹 오프셋을 보고함
    • one-pass DFA: 제한된 정규식에서 캡처 그룹 오프셋을 빠르게 보고함
    • dense DFA: 매우 빠르지만 전체 매치 시작·끝만 보고하며, 구성은 최악 O(2^m) 시간·공간이 필요함
    • lazy DFA: 검색 중 NFA에서 DFA를 만들며, 보통 full DFA만큼 빠르고 full DFA의 지수적 구성 비용을 피함
  • 이 엔진들과 Prefilter는 하나의 meta regex engine으로 조합되고, regex crate는 이 meta engine의 얇은 래퍼임

리터럴 최적화

  • 리터럴 추출은 regex 내부의 핵심 최적화임
    • 예를 들어 (foo|bar|quux)(\s+\w+)의 모든 매치는 foo, bar, quux 중 하나로 시작함
  • 리터럴이 중요한 이유는 단일 또는 소수의 문자열 검색 알고리듬이 매우 빠르기 때문임
    • 벡터 명령으로 haystack의 여러 바이트를 한 번에 처리할 수 있음
    • 일반 정규식 매칭 알고리듬은 같은 방식으로 일관되게 가속하기 어려움
  • 잘 최적화된 substring 검색은 일반 정규식 엔진보다 최소 한 자릿수 이상 빠른 경우가 자주 있었음
  • 리터럴 추출은 휴리스틱임
    • 후보 매치의 false positive rate를 줄여야 함
    • prefilter가 전체 지연 시간에 미치는 영향도 낮춰야 함
    • 두 조건 모두 haystack에 의존하지만, 검색 전에 haystack을 분석하면 전체 검색 시간이 나빠질 수 있음
  • 리터럴 시퀀스는 집합이 아니라 순서가 있는 시퀀스임
    • regex crate는 Perl-like leftmost-first 의미론을 따르므로 |는 교환법칙이 성립하지 않음
    • sam|samwise는 sam만 추출될 수 있지만, samwise|sam은 둘 다 고려됨
  • 단일 문자열 검색에는 memchr crate의 memmem 모듈이 쓰임
    • 주 알고리듬은 최악 O(n) 시간과 상수 공간을 갖는 Two-Way임
    • 짧은 needle과 haystack에는 Rabin-Karp가 쓰임
    • x86_64에서는 generic SIMD 변형이 활용됨
  • 다중 문자열 검색에는 Hyperscan에서 포팅한 Teddy가 주요 알고리듬으로 쓰이며, 일부 경우 Aho-Corasick도 사용됨

Thompson NFA와 최적화

  • regex crate 내부의 중심 자료구조는 Thompson NFA임
  • Thompson’s construction은 정규식의 구조화 표현에서 NFA를 O(m) 시간에 만들며, m은 counted repetition 확장 후 정규식 크기에 비례함
  • NFA는 직접 정규식 엔진으로 사용할 수 있고, DFA 같은 다른 타입으로 변환해 다른 엔진의 기반으로도 사용됨
  • 새 NFA 컴파일러의 주요 최적화는 epsilon transition을 줄이는 데 집중함
    • Thompson NFA는 구성 시간이 좋지만 epsilon transition을 많이 사용함
    • epsilon closure 계산은 검색이나 DFA 구성 중 반복 비용을 만들 수 있음
  • sparse state 최적화는 여러 범위 전이를 하나의 상태로 표현해 기존의 여러 Split instruction을 줄임
    • [A-Za-z0-9] 같은 정규식에서 불필요한 epsilon transition을 제거함
    • 현재 표현에서는 indirection 때문에 cache 영향과 heap memory 증가 가능성이 있음
  • 최소 UTF-8 오토마타 최적화는 큰 Unicode class에서 NFA 크기를 크게 줄임
    • 예전 byte-oriented NFA에서 \w는 3,564 states를 만들 수 있었음
    • 새 컴파일러는 Daciuk’s algorithm을 사용해 훨씬 적은 상태와 zero epsilon transition을 갖는 구조를 만듦
    • reverse NFA의 shrink는 compile time 비용 때문에 기본 비활성화됨
  • literal trie 최적화는 zap|z|zapper, abc|xyz 같은 리터럴 alternation에서 공통 구조를 trie로 컴파일해 epsilon transition을 줄임
    • leftmost-first 의미론을 보존하기 위해 match가 나타나는 지점마다 transition chunk를 나눔
  • 향후 NFA 작업으로 Glushkov NFA와 단일 contiguous allocation 저장이 검토됨
    • Glushkov NFA는 epsilon transition이 없지만 compile time complexity가 더 나쁨
    • contiguous allocation은 cache friendliness와 zero-copy 직렬화·역직렬화 가능성을 줄 수 있지만 코드 복잡성과 unsafe 사용 가능성이 있음

개별 정규식 엔진

  • regex-automata의 엔진들은 비슷한 API를 공유함
    • Input: haystack, 검색 범위, anchored 여부, early stop 여부를 설정함
    • Match: 매치된 byte span과 PatternID를 담음
    • MatchError: 검색 결과를 결정할 수 없는 오류를 나타냄

  • PikeVM

    • regex-syntax가 파싱할 수 있는 전체 기능을 지원하고, 어떤 길이의 haystack에서도 동작함
    • 캡처 그룹 위치를 추적하고, active state들을 lock-step으로 계산해 최악 O(m * n) 시간을 보장함
    • 많은 상태와 캡처 그룹 위치를 추적해야 하므로 성능이 주요 약점임
    • regex-automata 엔진 중 검색 중 오류를 반환하지 않는 고유한 특성이 있음

  • BoundedBacktracker

    • Thompson NFA 위에서 backtracking을 쓰지만 이미 수행한 작업을 다시 추적하지 않도록 추가 상태를 사용함
    • 최악 O(m * n) 시간을 보장하지만 O(m * n) 공간을 사용함
    • 대략적인 실험에서 보통 PikeVM보다 약 2배 빠름
    • haystack 길이와 정규식 크기가 설정된 visited capacity를 넘으면 실패할 수 있음

  • one-pass DFA

    • 제한된 one-pass NFA에서 캡처 그룹 오프셋을 매우 빠르게 보고함
    • 캡처 그룹을 보고할 수 있는 가장 빠른 방식으로 꼽힘
    • anchored search만 지원하며, 많은 정규식은 one-pass가 아님
    • Unicode 모드에서는 byte level transition overlap 때문에 one-pass가 아니던 정규식이 Unicode를 끄면 one-pass가 될 수 있음

  • fully compiled DFA

    • forward DFA와 reverse DFA 두 개로 구성되어 전체 매치 끝과 시작을 찾음
    • 구성은 최악 O(2^m) 시간·공간이고, dense DFA는 메모리를 많이 씀
    • full DFA 엔진은 regex crate에서 기본 비활성화되어 있으며 perf-dfa-full feature로 opt-in해야 함
    • mutable Cache 없이 동작하고, raw bytes로 직렬화해 core만 있는 환경에서도 검색 런타임을 사용할 수 있음

  • hybrid NFA/DFA, lazy DFA

    • full DFA와 유사하지만 transition table을 검색 중에 만듦
    • cache에 이미 계산된 transition이 있으면 재사용하고, 없으면 NFA powerset construction으로 해당 transition만 계산함
    • 최악 검색 시간은 O(m * n), 공간은 구성 시 정한 cache capacity로 제한됨
    • 일반적인 경우 대부분의 state와 transition이 캐시되어 평균 O(n)처럼 동작하며, 실제로 많은 정규식에서 full DFA와 비슷한 검색 성능을 보임
    • cache가 반복적으로 가득 차 비효율적이면 오류를 반환하고, meta engine에서는 보통 다른 엔진으로 재시도함

meta regex engine의 역할

  • meta regex engine은 여러 엔진을 하나로 묶고, 호출자에게 infallible API를 제공하려고 함
  • 호출자는 각 검색마다 Cache를 직접 만들고 전달하지 않아도 됨
    • meta engine은 내부 thread-safe cache pool을 관리함
    • 동기화 비용을 피하려는 경우 명시적으로 Cache를 전달하는 lower-level API도 제공함
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet은 모두 meta engine의 얇은 래퍼임
  • meta engine의 내부 전략은 대략 다음과 같음
    • 정규식 엔진 없이 단일·다중 substring 검색만으로 처리할 수 있으면 NFA 구성도 피함
    • 가능하면 prefix 리터럴 시퀀스를 추출해 Prefilter로 사용함
    • prefix가 적절하지 않으면 reverse anchored, reverse suffix, reverse inner 최적화를 시도함
    • 그 외에는 PikeVM, bounded backtracker, one-pass DFA, lazy DFA, full DFA를 포함한 core strategy로 fallback함
  • 전체 전략은 두 문장으로 압축됨
    • 가능한 한 리터럴을 검색함
    • 가능한 한 PikeVM 사용을 피함
  • reverse suffix와 reverse inner 최적화는 잘못하면 haystack 크기에 대해 최악 O(m * n^2)가 될 수 있음
    • meta engine은 reverse scan이 이전 suffix match 끝을 넘어가려는 상황을 감지하고 core strategy로 fallback해 시간 복잡도 보장을 유지함

RE2와의 차이

  • regex crate와 RE2는 유사점이 많음
    • RE2에도 PikeVM에 해당하는 NFA, bitstate backtracker, one-pass NFA, lazy DFA, 여러 엔진을 조합하는 구조가 있음
    • 위 엔진 중 RE2에 없는 것은 fully compiled DFA임
  • 주요 차이는 다음과 같음
    • RE2는 leftmost-first 외에 POSIX식 leftmost-longest 의미론을 옵션으로 지원함
    • RE2는 Unicode 지원이 더 제한적이며, \w, \s, \d, \b를 Unicode 정의로 쓰는 옵션이 없음
    • RE2는 character class set operation 중 union 외 지원이 제한적임
    • RE2의 PikeVM은 더 메모리 효율적일 가능성이 있음
    • RE2의 리터럴 최적화는 제한적이며, regex crate가 더 많은 리터럴 최적화를 수행함
    • RE2 lazy DFA는 여러 thread가 같은 transition cache를 공유해 동기화가 필요하지만, regex crate는 thread별 별도 cache를 요구해 더 많은 메모리를 씀
    • regex crate는 regex-syntax와 regex-automata를 별도 버전 라이브러리로 공개하지만, RE2는 이를 지원하지 않음
    • regex-automata는 모든 엔진에서 first-class multi-pattern regex를 지원하고, 각 매칭 패턴의 match 및 capture group offset도 보고할 수 있음

테스트 전략과 벤치마크

  • 새 테스트 전략은 내부 엔진을 독립적인 first-class API로 만들고 각 엔진을 직접 테스트하는 방식임
  • 모든 정규식 테스트는 TOML 파일로 지정됨
  • regex-test crate가 TOML 테스트를 읽어 구조화된 표현으로 변환함
  • 각 엔진 구성마다 하나의 Rust unit test를 두고, 해당 엔진에 적용 가능한 모든 TOML 테스트를 실행함
  • Rust unit test framework가 확장 가능하지 않아, 특정 테스트 필터링을 위한 자체 environment variable 인프라가 추가됨
  • regex-automata에만 450개가 넘는 documentation test가 있음
  • regex 1.9 준비 과정에서 fuzz testing target도 많이 추가되었고, Addison Crump의 도움으로 몇몇 버그를 찾음
  • 벤치마크는 rebar라는 regex barometer로 공개됨
    • rebar는 regex crate뿐 아니라 여러 정규식 엔진을 벤치마크함
    • 242개 벤치마크에서 regex 1.9는 검색 시간 기준 regex 1.7.3보다 평균 1.5배 빠름
    • 정규식을 빌드하는 시간은 다소 회귀함
    • 1.8은 일부 전환 작업이 포함된 transition release라 비교 기준으로 1.7이 사용됨

비용과 경량 대안

  • 재작성에는 지난 몇 년간 작성자의 자유 시간 대부분이 쓰였고, ripgrep 같은 프로젝트는 한동안 릴리스되지 못함
  • 재사용 가능한 공개 추상화는 내부 전용 추상화보다 코드가 더 많아지는 경향이 있음
    • 결과적으로 바이너리 크기와 컴파일 시간이 증가함
  • 내부 엔진 API가 별도 버전으로 공개되면서, API를 깨려면 regex-automata의 적절한 breaking change release가 필요함
  • 비용 완화를 위해 두 가지 조치가 적용됨
    • fully compiled DFA 엔진은 기본 비활성화하고 opt-in feature로 둠
    • regex-lite를 새 crate로 공개함
  • regex-lite는 regex crate의 거의 drop-in replacement를 목표로 하지만, 바이너리 크기와 컴파일 시간 최적화에 집중함
    • Unicode와 성능 측면의 기능을 포기함
    • O(m * n) 시간 복잡도 보장은 유지함
    • 의존성이 0개이며, 자체 정규식 파서를 포함해 regex crate와 코드를 공유하지 않음
  • regex-lite는 아직 실험적 완화책이지만, regex crate의 feature로 최적화와 Unicode 기능을 꺼도 regex-lite의 바이너리 크기와 컴파일 시간에는 가까워지기 어렵다는 점을 보여줌

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 대충 훑어봤을 뿐인데도 Rust regex 크레이트는 정말 인상적임
    BurntSushi가 만든 훌륭한 것들이 많지만 Rust의 regex 크레이트는 전설적이고, Rust 생태계가 오래전부터 성능 좋고 쓰기 쉬운 정규식 라이브러리를 갖고 있었다는 건 커뮤니티에 큰 축복임
    Russ Cox의 정규식 글 시리즈도 훌륭해서, 정규식이 이론과 실무의 완벽한 교차점처럼 느껴지기 시작했을 때 여름 동안 정규식 엔진을 만드는 데 참고했음
    이번 글의 더 깊은 테스트 변화도 흥미롭고, 생태계에 핵심적인 크레이트인 만큼 이런 깊은 주제의 설명이 고마움
    정규식은 가끔 읽기 어렵고 이메일 검증 같은 데 남용되기도 하지만, 거의 모든 언어에서 가장 밀도 높은 도구 중 하나임
    실용서로는 Jeffrey Friedl의 Mastering Regular Expressions 정도만 잘 알고 있고, 이론 쪽은 컴파일러 책들이 다루며 Dragon Book도 구현 관점에서 괜찮았음. 다른 정규식 책 추천이 궁금함

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l...와 https://kean.blog/post/lets-build-regex는 단순화한 정규식 엔진 구현 입문으로 훌륭함
      정규식에 대해 비결정적 유한 오토마톤을 만들고, 그 결과 방향 그래프에서 탐색해 종료 상태에 해당하는 정점에 도달 가능하면 매치로 보는 방식임
      정규식을 쓰는 사람이라면 이 연습으로 생각보다 마법이 적다는 걸 이해할 수 있고, NFA 위에서 공들이 튀어 다니는 모습을 떠올리면 프로덕션에서 결국 마주치는 재앙적 백트래킹 버그도 물리적인 의미를 갖게 됨
      원문과 관련해서는 https://github.com/rust-lang/regex/issues/822의 마지막 BurntSushi 댓글이 틈새 API 문단 https://blog.burntsushi.net/regex-internals/#problem-request...에 유용한 맥락을 더해줌. 여러 정규식을 텍스트에 동시에 검색하는 건 매우 복잡하지만 매우 유용해서, 이 패턴으로 커뮤니티가 무엇을 만들지 기대됨
    • 정규식이 파싱 비슷한 작업에서 빛나는 대표 사례는 구분자가 다양한 형식을 다룰 때임
      예를 들어 header:field1,field2,field3"data"hash처럼 필드 수가 고정된 형식이나, suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2처럼 대부분 요소가 선택적인 형식에서는 split 같은 기본 도구로는 부족하고 정규식이 잘 맞음
      정규식이 빨리 읽기 어려워지는 이유도 여기 있음. 정규식 하나에 필드 사이 구분자, 각 필드의 유효성, 어떤 필드가 선택적인지가 모두 섞임
      이건 원래 세 가지 별개 관심사인데, 대부분의 정규식 API는 이를 단계별로 분리하게 해주지 못하고 전부 합친 문자열 하나만 받게 함
    • 이 RegEx 라이브러리는 대부분의 JavaScript 구현처럼 JIT를 쓰는지 궁금함. 아니라면 JavaScript가 Rust를 이기는 사례일 수도 있음
    • 최근 RegEx 작업을 조금 하면서 이 글을 훑어봤는데, 사용한 언어는 다른 엔진들과 달리 오류를 반환하지 않는 걸 보면 PikeVM을 쓰는 듯했음
      언어의 제약과 저작권 보호 상태 때문에 직접 RegEx 기능을 새로 만들어야 했고, 정규식은 정말 부두술처럼 느껴질 때가 있음
      다른 엔진들이 얼마나 자주 쓰이는지는 모르지만, 많은 프로그래밍 언어가 PikeVM을 쓴다면 Google이 서버용 자체 OS를 만들고 특정 상황에서 더 빠른 엔진을 동원해 몇 클록 사이클이라도 아끼려 한 이유를 이해할 수 있음
      검색 문자열에 문자 몇 개만 더해도 패턴 매칭이 크게 느려지는 걸 잘 알고 있음. “푼돈을 챙기면 큰돈은 알아서 챙겨진다”는 속담은 RegEx와 클록 사이클에도 잘 맞고, 초당 수백만 레코드를 처리하던 90년대 대화들을 돌아보면 이게 몇몇 코더를 매우 부자로 만들었을 듯함
    • 가장 큰 불만은 정규식 방언의 작은 차이들임
      특히 방언과 문맥마다 따옴표 처리나 식 종료 방식이 너무 달라서, 외우려는 걸 포기하고 필요할 때마다 예제를 검색하게 됨

  • ActiveState에서 학교를 막 졸업한 동료와 함께 Komodo 편집기용 정규식 디버거를 만들라는 일을 맡았음
    전설적인 Perl 전문가 Mark Jason Dominus를 고용해 Perl 정규식 엔진에 훅을 넣게 했고, 그 훅을 UI에 노출해 사용자가 정규식 실행을 단계별로 볼 수 있게 만들었음
    요즘은 웹 기반 도구들이 더 뛰어나지만, 2001년 Komodo의 Rx Debugger는 최첨단이었고 작업하는 재미도 컸음

    • 과거에 오프라인 정규식 디버거가 필요했던 적이 있음
      에어갭 네트워크를 다루고 있어서 도구를 써야 하는 사람들이 온라인 사이트에 접근할 수 없었고, 어떤 설계든 작업 데이터를 온라인 도구에 넣는 건 생각조차 허용되지 않았음
      그런데 대부분의 노력이 온라인 도구에 집중되어 있고, 오프라인 도구는 https://regex101.com/ 같은 것에 비해 드물고 부족함
    • 이 용도로 쓸 만한 구체적인 웹 기반 도구 추천이 궁금함

  • 문자열이 아닌 리스트에도 이걸 쓸 수 있는지 궁금함
    문자 리스트를 검색하고 수정하는 강력한 장치는 있는데, 숫자나 날짜 리스트가 되는 순간 전부 사라지는 게 늘 답답했음
    예를 들어 로그인 시도 날짜 리스트에서 실패 5회 이상 뒤 성공이 오는 모든 시퀀스를 찾고 싶다면 정규식으로는 간단하지만, 실제로는 직접 루프, 플래그, 임시 리스트를 만들어야 함
    리스트를 문자열로 바꿔 처리한 뒤 다시 되돌릴 수도 있겠지만 단점이 뻔함. 문자열 기반 정규식만큼 빠르지 않더라도, 임의의 리스트 타입을 위한 정규식이 왜 없으면 안 되는지 모르겠음
    예전에 만든 Python 프로토타입도 찾았음: https://github.com/boppreh/listregex
    매우 느리지만 API 실험으로는 만족스럽고, 패턴 반전·교집합·짝 맞추기처럼 정규식에 없는 도구도 제공함

    • 안 됨. 이 regex 라이브러리는 문자열 검색에 강하게 결합되어 있고, 그건 의도적인 설계 결정임
      이런 정규식 엔진이 제네릭 알파벳을 갖게 만드는 건 시작부터 무리임. 특히 API 설계와 주 사용 사례의 성능을 해치지 않는 방식이 현실적으로 너무 어려움
      성능을 신경 쓰지 않는 그런 정규식 엔진은 만들기 어렵지 않음. 예를 들어 공개한 regex-lite 크레이트를 가져다 원하는 만큼 제네릭하게 고칠 수 있고, 그 과정에서 흥미로운 난관들을 만나게 될 것임
      이런 것이 아예 없는 것도 아님. 사람들이 만들려고 시도함[1]. 다만 일반적 유용성을 다소 과장하고 있어서 보통 큰 traction을 얻지 못하는 듯함 :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • C++ 표준 라이브러리의 std::basic_regex는 사용자 정의 문자 타입에 대한 템플릿 클래스를 노출해서 이런 시도를 함: https://en.cppreference.com/w/cpp/regex/basic_regex
      사용자 정의 “문자”에 필요한 동작을 정의하는 trait 클래스를 제공할 수 있음
      하지만 성능은 크게 떨어지고, 임의의 비문자 객체를 사용자 정의 std::basic_string에 넣는 것만큼 잘 동작할 가능성이 큼
    • 값들의 슬라이딩 윈도우 위에서 매칭하는 API를 어떻게든 정의해야 함
      불가능한 일은 아니지만, 대부분의 언어가 이를 위한 좋은 인터페이스를 갖고 있지는 않음

  • 코드나 텍스트 파일에서 무언가를 찾을 때 Ripgrep을 매일 쓰고, Windows, Linux, Mac, VSCode, Vim 어디서든 쓸 때마다 고마움
    내 삶과 일하는 방식을 바꾼 소프트웨어 중 하나임
    grep을 억지로 써야 할 때면 모든 게 단일 코어 CPU에서 돌고 데이터는 느린 PATA/IDE 회전식 하드디스크에 있던 시대로 돌아간 느낌임
    BurntSushi는 위대한 프로그래머들 사이에서 충분히 존경받을 만함

    • ripgrep에는 계보가 있음. 그 전에는 ag, 그 전에는 ack가 있었고, 모두 단순한 grep보다 훨씬 나은 인터페이스를 제공하려 했음

  • 업무 문제로 매우 긴 정규식 1천만 개 이상으로 RegexSet을 만들어야 했음
    어떤 엔진도 기본 상태로는 감당하지 못했고, Rust의 RegexSet도 기본값으로는 충분하지 않았음
    그래도 regex-automata와 regex-syntax를 사용하고 코드를 읽어보는 과정은 2018년에도 매우 유익한 학습 자료였음
    결국 업무 프로젝트는 Lucene API를 모델로 삼았지만, 기본기는 regex 크레이트들에서 배운 뒤 가능했음

    • 정규식 1천만 개는 엄청난 규모임. Aho-Corasick도 리터럴 1천만 개는 간신히 다룰 정도임
      앞으로의 작업은 정규식 엔진이 더 많은 패턴에서 더 잘 확장되게 만드는 것임. 지금은 1천만 정규식 훨씬 전에 무너질 것이고, 그 목표가 실제로 가능한지도 확신하기 어려움
      그래도 지금보다는 분명 나아질 수 있음
      물론 다중 패턴 검색에서는 Hyperscan이 사실상 금본위제 같은 존재임. 다만 패턴 1천만 개를 얼마나 잘 처리할지는 모르겠음
    • 처음부터 자세히 쓰지 않은 걸 보면 답은 “아니오”일 것 같지만, 혹시 가능하다면 그 문제나 프로젝트가 무엇이었는지 더 공유할 수 있는지 궁금함

  • 예전에 regex-automata 크레이트를 실험해봤는데, 내부 DFA에 직접 접근할 수 있어서 텍스트 편집기에 쓸 수 있는 유일한 라이브러리였음
    일반적인 정규식 라이브러리 API는 입력이 하나의 연속된 문자열이라고 기대하지만, 이 방식은 어떤 텍스트 자료구조와도 호환됨

  • regex-automata 코드, 그것도 초기 0.2.0 릴리스를 쓰는 코드를 작성하던 중에 이 글이 나왔음
    새 내부 구조를 다시 파야 하는지 확인할 시간이 된 듯함
    아직 글은 못 읽었지만 매우 흥미롭고 타이밍도 절묘한 글처럼 보임
    몇 분 뒤 보니 답은 “그럴 수도 있음”에 가까웠지만, 정식 릴리스라서 오히려 코드를 크게 단순화할 수 있을 듯함
    다시 10분쯤 뒤에는 꽤 painless했고 새 Builder::patch 메서드는 완전한 업그레이드였음
    추신으로, 아직도 당신의 모든 GitHub 저장소에서 차단되어 있는데 많은 크레이트가 널리 쓰이는 걸 고려하면 좀 불공평하다고 생각함. 원래 사건은 기억나지 않음. regex 크레이트 자체는 이제 rust-lang 조직 아래인 것 같지만, 여전히 상호작용할 수 없는 것들이 있음

    • regex-automata 0.2.0 문서에는 이에 대한 큰 경고가 있었고, 0.1을 쓰라고 강하게 권장했음: https://docs.rs/regex-automata/0.2.0/regex_automata/
      나도 원래 사건은 기억나지 않음. 여러 이유로 많은 사람을 차단하지만, 이제 차단을 풀었음

  • BioJulia는 컴파일 시점에 임의의 Julia 코드를 삽입할 수 있는 순수 Julia 정규식 엔진 Automa.jl을 공개했음
    Rust의 regex가 Automa보다 훨씬 진보했다는 점을 깎아내리려는 건 아니지만, 정규식 내부를 라이브러리로 노출한 첫 사례라는 표현에는 동의하기 어려움

    • 이건 서로 다른 두 가지로 들림
      예를 들어 PCRE2에는 말한 것과 비슷하게 들리는 “callout” 지원이 있음: https://www.pcre.org/current/doc/html/pcre2callout.html
      ragel이나 re2c 같은 것들도 비슷한 일을 해왔음
      이 블로그에서 말하는 건 정규식 라이브러리 자체의 내부를 꺼내 별도로 버전 관리되는 라이브러리로 만들고, 다른 사람들이 조합할 수 있게 하는 것임
      백트래커는 보통 엔진이 백트래커 하나뿐이라 이 방식이 덜 자연스럽지만, 오토마톤 기반 라이브러리는 여러 엔진을 다양한 방식으로 조합하는 경우가 많음
      그래도 백트래커도 실제로는 노출하지 않는 정규식 파서나 AST 같은 것들을 노출할 수는 있음
답변달기