공백 정규 표현식을 사용할 때의 무한 순환

묘사

다음은 무한 순환을 초래하는 간단한 테스트 용례이다.

regex = RE2::Regexp.new('')
regex.scan('test').map { |match| match }

이것도 실패했다.

regex = RE2::Regexp.new('()')
regex.scan('test').map { |match| match }

Ruby의 작동 방식은 다음과 같습니다.

'test'.scan('').map { |match| match }
=> ["", "", "", "", ""]

관련 질문:https://stackoverflow.com/a/30047809/1992201
re2의 노트.h 파일 정보:https://github.com/google/re2/blob/master/re2/re2.h#L133-L138
이러한 행과 연관:https://github.com/mudge/re2/blob/v1.0.0/ext/re2/re2.cc#L224- L225

토론 #1

이것은 Scanner가 실현한 문제인 것 같다. 일치하는 항목이 존재하면 입력이 고급이 아니더라도 무한 순환할 수 있다.
올바른 형식:

r = RE2::Regexp.new('')
scanner = r.scan('test')
scanner.scan.to_a

잘못된 테이블:

r = RE2::Regexp.new('')
r.scan('test').map { |x| x }

토론 #2

@stanhu:re2.h에서 온 평론이 특히 유용합니다.당신은 올바른 행동이 무엇이어야 한다고 생각합니까?

// If the regular expression being used might match
// an empty string, the loop body must check for this case and either
// advance the string or break out of the loop.

우리는 스스로 입력을 추진해야 합니까 아니면 순환을 중지해야 합니까?

토론 #셋

는 빈 매칭이나 빈 포획 매칭을 만났을 때 우리가 직접 remove_prefix 를 사용하여 입력을 추진하는 것처럼 보이지만 무한 순환을 해결하지만 입력이 끝날 때 되돌아오기nil는 좀 번거롭다.

토론 #4

네, 저도 같은 방법을 시도해 봤는데 효과가 별로 없어요.

--- a/ext/re2/re2.cc
+++ b/ext/re2/re2.cc
@@ -204,12 +204,15 @@ static VALUE re2_scanner_rewind(VALUE self) {
  */
 static VALUE re2_scanner_scan(VALUE self) {
   int i;
+  int found_match = 0;
+  size_t original_size;
   re2_pattern *p;
   re2_scanner *c;
   VALUE result;

   Data_Get_Struct(self, re2_scanner, c);
   Data_Get_Struct(c->regexp, re2_pattern, p);
+  original_size = c->input->size();

   vector<RE2::Arg> argv(c->number_of_capturing_groups);
   vector<RE2::Arg*> args(c->number_of_capturing_groups);
@@ -228,6 +231,7 @@ static VALUE re2_scanner_scan(VALUE self) {
       if (matches[i].empty()) {
         rb_ary_push(result, Qnil);
       } else {
+        found_match = 1;
         rb_ary_push(result, ENCODED_STR_NEW(matches[i].data(),
               matches[i].size(),
               p->pattern->options().utf8() ? "UTF-8" : "ISO-8859-1"));
@@ -237,6 +241,17 @@ static VALUE re2_scanner_scan(VALUE self) {
     result = Qnil;
   }

+  /* In case we matched a null string, advance the pointer to avoid an infinite loop */
+  if (!found_match &&
+      c->number_of_capturing_groups &&
+      c->input->size() &&
+      (original_size == c->input->size())) {
+      c->input->remove_prefix(1);
+  }
+
   return result;
 }

GitLab에서, 우리는 교체 match 를 통해 루비 코드를 바꾸어 이 문제를 해결하고 있다.패치를 나중에 보낼게요.

토론 #5

두 가지 상황에서 나는 입력에서 1바이트 접두사를 삭제하고(입력 크기가 0이 아니라면) 몇 가지 기능을 실현했다.

포획조에서 되돌아오는 일치가 비어 있을 때;

일치하는 경우(즉, FindAndConsumeN이true로 되돌아오는 경우) 캡처 그룹의 수는 0입니다.

나는 오늘 저녁에 없지만, 나는 가능한 한 빨리 볼 것이다. 왜냐하면 주요한 도전은 논리를 명확하게 유지하는 것이기 때문이다.
또 다른 궁금한 것은 빈 포획조 (예를 들어 빈 문자열로 되돌아오는 것) 와 포획조가 전혀 일치하지 않는 것을 구분해야 하는지 하는 것이다.이것은 앞으로 호환되지 않을 수도 있기 때문에 우리는 잠시 연기할 수 있다.

토론 #6

GitLab에서 수행한 사항은 참고용으로만 제공됩니다.https://gitlab.com/nick.thomas/gitlab-ce/commit/dabc1fa388143808bab792448504dac4bae8992b

토론 #7

루비의 Regexp 차이는 다음과 같습니다.

"foo".scan(//) # ["", "", "", ""]
"foo".scan(/()/) # [[""], [""], [""], [""]]
"foo".scan(/foo()/) # [[""]]
"foo".scan(/(foo())/) [["foo", ""]]

토론 #8

#35의 변화에 따른 결과는 다음과 같습니다.

[9] pry(main)> RE2::Regexp.new('').scan("foo").to_a
=> [[], [], []]
[10] pry(main)> RE2::Regexp.new('()').scan("foo").to_a
=> [[nil], [nil], [nil]]
[11] pry(main)> RE2::Regexp.new('foo()').scan("foo").to_a
=> [[nil]]
[12] pry(main)> RE2::Regexp.new('(foo())').scan("foo").to_a
=> [["foo", nil]]

빈 문자열/nil의 차이를 제외하고re2는 빈 패턴과 일치하는 것을 줄였다. 이것은 나에게 매우 직관적이다. (문자마다 일치하고 멈추는 것). 그러나 아마도 내가 무엇을 빠뜨렸을 것이다.

토론 #9

네, 루비의 빈 문자열과 빈 모드의 기본 대소문자는 리2에서도 그것을 보존해야 하는지 알고 싶습니다.

> ''.scan(//)
=> [""]

이를 위해 스캐너가 다 소모되었는지 다시 스캔해야 할 수도 있습니다. 즉, 일치하는 문자열은 입력 문자열의 끝을 넘어섰습니다. 입력 크기가 0일 때가 아니라.

토론 #10

#35를 업데이트하여 Ruby 동작과 일치시킴(빈 문자열이 아닌 호환성 재반환nil:

[1] pry(main)> RE2::Regexp.new('').scan('foo').to_a
=> [[], [], [], []]
[2] pry(main)> RE2::Regexp.new('()').scan('foo').to_a
=> [[nil], [nil], [nil], [nil]]
[3] pry(main)> RE2::Regexp.new('foo()').scan('foo').to_a
=> [[nil]]
[4] pry(main)> RE2::Regexp.new('(foo())').scan('foo').to_a
=> [["foo", nil]]

이것은 당신의 기대에 부합됩니까?

토론 #11

저는 v1.1.0를 발표했습니다. 이 문제를 해결할 수 있기를 바랍니다. 한번 해 보세요. 만약 그것이 당신의 문제를 해결할 수 있다면 저에게 알려주세요.

토론 #12

@mudge에서 빠른 답변 감사합니다!https://gitlab.com/gitlab-org/gitlab-ce/merge_requests/13036re2 v1을 사용하려면 gitlab를 업데이트합니다.1.0 직접 만든 검색을 삭제할 수 있습니다.
나는 1MiB 구축 추적에서 0 매칭과 빈 매칭 상황을 테스트했는데, 그것들은 모두 매우 빠르다.잘했어!

토론 #13

천만에요!(코드를 삭제하는 것은 확실히 나를 기쁘게 한다.)

토론 #14

@mudge 감사합니다!