이전 글: https://gall.dcinside.com/mgallery/board/view?id=github&no=75421


 


열심히 만든 20MB짜리 정규식이 ErrorPatternTooLarge 라는 결과를 받고 슬퍼진 깃붕이는 에러를 고쳐보기로 해요


re2를 세팅하고, q=2,3,5,7,11,13 에 대해서 테스트를 했어요


a.cpp

#include <bits/stdc++.h>
#include <re2/re2.h>
using namespace std;

int main() {
int q=13,a=?,b=?;
ifstream regexFile(string("q")+to_string(q)+".txt");
string pattern;
std::getline(regexFile,pattern);

RE2 regex(pattern);
if(!regex.ok()){
cout<<regex.error()<<endl;
return 1;
}

long long base = 28194721654673498ll;
for(long long i=base;i<base+1000;i++){
assert(((i%q-a)*(i%q-b)%q==0)==(RE2::FullMatch(to_string(i),regex)==true));
cout<<((i%q-a)*(i%q-b)%q==0)<<" "<<(RE2::FullMatch(to_string(i),regex)==true)<<endl;
}
cout<<"OK"<<endl;
}


q=7정도일 때부터 `DFA out of memory:` 로 실패하고 있어요


다행히도 RE2::Options::set_max_mem 함수로 메모리 상한을 늘려주면 될 것 같아요


평범한 깃붕이라면 2^60 byte 메모리 정도는 하나씩 가지고 있을테니 아래처럼 설정해주도록 해요


RE2::Options o;
o.set_max_mem(1ll << 60);
RE2 regex(pattern, o);


이제 q=11까지 넘어가지만, q=13부터 ErrorPatternTooLarge 오류를 받아요


정규식은 이미 오토마타 고수의 라이브러리를 사용했기때문에


정규식을 최적화하는쪽으로는 더이상 가망이 없어보여요


하지만 깃붕이는 포기하지 않고 오류메시지를 다시 살펴보았어요


E0000 00:00:1738089543.522041 1508448 simplify.cc:228] CoalesceWalker::ShortVisit called
E0000 00:00:1738089543.522047 1508448 re2.cc:262] Error compiling '((((((((((((0|65)|(7(2*(8|15))))|((62|(7(2*(5|12))))(1*4...'
pattern too large - compile failed


pattern too large로 실패하기 전에 CoalesceWalker::ShortVisit called라는 수상한 오류메시지가 출력되고 있어요


해당 함수를 찾아가보면 Should never be called 라는 주석이 달려있네요. 그래서 해당 함수가 어디서 호출되는지 찾아갔어요


walker-inl.h:178

template<typename T> T Regexp::Walker<T>::WalkInternal(Regexp* re,
//코드 생략
if (--max_visits_ < 0) {
stopped_early_ = true;
t = ShortVisit(re, s->parent_arg);
break;
}


ShortVisit 함수는 WalkInternal 단 한 곳에서만 사용되고 있었어요


이 코드의 위치로 max_visits_번 이상 오게 되면 ShortVisit을 호출해서 문제가 될 것 같아요


template<typename T> T Regexp::Walker<T>::Walk(Regexp* re, T top_arg) {
// Without the exponential walking behavior,
// this budget should be more than enough for any
// regexp, and yet not enough to get us in trouble
// as far as CPU time.
max_visits_ = 1000000;
return WalkInternal(re, top_arg, true);
}


max_visits_ 값을 초기화하는 위치를 찾았어요


주석에 따르면 잘 처리하기 위해서 더 큰 값이 필요하지만, CPU시간을 너무 많이 잡아먹지 않도록 작은값을 사용하고 있다는듯 하네요.


이제 max_visits_ = 1<<30 정도로 설정하고 돌려보도록 해요



re2에서 긴 regex 컴파일에 실패하는 문제를 해결했어요




제출2: https://limewire.com/d/1dc793a5-ca93-45ca-8566-a416c5e9acfe#xOBcYteP-XZxS5ylsMGIWTi7DyDf8Au2lpGudAc9bgo


re2 뜯어본 소감: RIIR 해줄 멋진 깃붕이가 필요하다 ㅇㅅㅇ