Regex backreference [1/3] Fixes backreferences for extended grammar.

[Mordante]

Summary

The regex backreferences were not properly parsed and used when using
the extended grammar. This change parses them.

The issue was found while working on bug 34297.

[zoecarver]

Maybe add a test to ensure that the correct error is thrown?

[Mordante]

I added a unit test in part 3 of the series [1]. Would you prefer to have the test for this fix in this patch?

[1] https://reviews.llvm.org/D62453

[zoecarver]

Ah yes, I didn't see that patch. I will defer to the code-owners on this, but my $0.02 are, if this patch were a feature or added/removed functionality I would say add the tests to this patch. But, because this patch only fixes a small bug, it should be OK if the tests come later. If for whatever reason the other patch does not make it, you will have to remember to make another patch with the tests.

[mclow.lists]

This looks quite reasonable to me, but I have to agree with Zoe here; since you've added behavior in this patch, the test for it should be in this patch as well.

Especially since I'm not convinced that https://bugs.llvm.org/show_bug.cgi?id=34297 is actually a bug, rather than a "This might be nice"

[mclow.lists]

libcxx/include/regex

3535

Alternately, you could remove these two lines from this patch, and put them into D62453 (where the tests are).

libcxx/test/std/re/re.alg/re.alg.search/extended.pass.cpp

506

Why two checks for m.length(0) here?

Why not just:

assert(static_cast<size_t>(m.length(0)) == std::char_traits<char>::length(s));

since you know that length(s) > 0
(Obviously, this applies to several places)

[Mordante]

libcxx/test/std/re/re.alg/re.alg.search/extended.pass.cpp

506

I agree your proposed style would also work. I emulated the other tests in this file, they all use this assert.
It feels wrong to me to change the new tests to use your proposed style
assert(static_cast<size_t>(m.length(0)) == std::char_traits<char>::length(s));
This would make the style of the new test inconsistent with the style of the existing tests.
Do you prefer to keep the new tests as I wrote them or shall I create a separate patch to modify the style of the existing test?

[mclow.lists]

libcxx/test/std/re/re.alg/re.alg.search/extended.pass.cpp

506

Just keep it the same as the others, and I'll clean them all up sometime.

[Mordante]

Removes the throw and move that to D62453.

[Mordante]

Ping

[zoecarver]

libcxx/include/regex

3536

Is the intent here that __first = ++__temp will be executed regardless of the value of __val, or that it will only be executed if __val is greater than 1 and less than 9? If the former, I think you should unindent the statement, as it makes the intent confusing. If the latter, then you need braces around the if statement.

[Mordante]

libcxx/include/regex

3536

Good catch, still not entirely used to not attaching braces to all ifs. So forgot them when needed. Will upload a new patch later today.

[Mordante]

Fixes the issue found by @zoecarver .

[mclow.lists]

libcxx/include/regex

3532

This looks like a copy/pasta of __first = __parse_BACKREF(__first, __last) to me.
How is it different?

[Mordante]

libcxx/include/regex

3532

It is a copy-paste of the body of __parse_BACKREF . The __parse_BACKREF is used in the basic regex (RE) part of the code. It searches for an entire backreference ( \n where n is a single digit). This code is part of the extended regex (ERE) and already has found a \ so only needs to find the digit.

I can move this block to a seperate function and adjust __parse_BACKREF. However I felt this would be a bit awkward due to updating __first. We can do it like this:

if(__validate_backref(*__temp))
  __first = ++__temp;

or this: __first = __validate_backref(__first, __temp);
But then the __validate_backref has a __first, __current instead of a __first, __last set of iterator arguments.

Do you want me to move the common part to a separate function? If yes which of the two APIs do you prefer or do you have an alternative? Then I also need to adjust D62453 to move the __throw_regex_error the new function.

[mclow.lists]

I'm not a big fan of duplicated code; but especially in this case, since in D62453 you edit the duplicated code to add a throw; but you have to do it twice - once in __parse_backref and once in the new code. Why is that preferable?

[Mordante]

I think there is a minor misunderstanding. I don't mind to avoid duplicating code. But __parse_BACKREF can't be used in both places. So the question was which of the proposed APIs you prefer. I'll post patch with my preferred solution. I'll wait with updating D62453 until this patch is approved.

[Mordante]

Adds a helper function __test_back_ref to avoid code duplication.

[Mordante]

Friendly ping

[Mordante]

Rebased on master

[ldionne]

@mclow.lists Do you still have a concern about code duplication? If not, I would go ahead and commit both this and https://reviews.llvm.org/D62453, and close http://llvm.org/PR34297.

[Mordante]

Friendly ping.

[ldionne]

Thanks for the patch and thanks for being patient!

[Mordante]

Thanks for the review and committing! (BTW I have commit access.)

libcxx/include/regex

template <class _ForwardIterator>
         __parse_class_escape(_ForwardIterator __first, _ForwardIterator __last,
                           basic_string<_CharT>& __str,
                           __bracket_expression<_CharT, _Traits>* __ml);
     template <class _ForwardIterator>
         _ForwardIterator
         __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last,
                           basic_string<_CharT>* __str = nullptr);
 
+    bool __test_back_ref(_CharT c);
+
     _LIBCPP_INLINE_VISIBILITY
     void __push_l_anchor();
     void __push_r_anchor();
     void __push_match_any();
     void __push_match_any_but_newline();
     _LIBCPP_INLINE_VISIBILITY
     void __push_greedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
                                   unsigned __mexp_begin = 0, unsigned __mexp_end = 0)

 template <class _ForwardIterator>
 _ForwardIterator
 basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
                                               _ForwardIterator __last)
 {
     if (__first != __last)
     {
         _ForwardIterator __temp = _VSTD::next(__first);
-        if (__temp != __last)
-        {
-            if (*__first == '\\')
-            {
-                int __val = __traits_.value(*__temp, 10);
-                if (__val >= 1 && __val <= 9)
-                {
-                    __push_back_ref(__val);
-                    __first = ++__temp;
-                }
-            }
-        }
-    }
+        if (__temp != __last && *__first == '\\' && __test_back_ref(*__temp))
     return __first;
 }
 
 template <class _CharT, class _Traits>
 template <class _ForwardIterator>
 _ForwardIterator
 basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
                                                _ForwardIterator __last)
if (__first != __last)
                 case '{':
                 case '}':
                     __push_char(*__temp);
                     __first = ++__temp;
                     break;
                 default:
                     if (__get_grammar(__flags_) == awk)
                         __first = __parse_awk_escape(++__first, __last);
+                    else if(__test_back_ref(*__temp))
+                        __first = ++__temp;
                     break;
                 }
             }
         }
     }
     return __first;
 }
 
 template <class _CharT, class _Traits>
 template <class _ForwardIterator>
 _ForwardIterator
while (__first != __last)
         __first = __t1;
         if (__first != __last)
             ++__first;
     }
     return __first;
 }
 
 template <class _CharT, class _Traits>
+bool
+basic_regex<_CharT, _Traits>::__test_back_ref(_CharT c)
+{
+    unsigned __val = __traits_.value(c, 10);
+    if (__val >= 1 && __val <= 9)
+    {
+        __push_back_ref(__val);
+        return true;
+    }
+
+    return false;
+}
+
+template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_loop(size_t __min, size_t __max,
         __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end,
         bool __greedy)
 {
     unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
     __end_->first() = nullptr;
     unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,

libcxx/test/std/re/re.alg/re.alg.match/extended.pass.cpp

int main(int, char**)
         std::cmatch m;
         const char s[] = "-ab,ab-";
         assert(!std::regex_match(s, m, std::regex("-(.*),\1-", std::regex_constants::extended)));
         assert(m.size() == 0);
     }
     {
         std::cmatch m;
         const char s[] = "-ab,ab-";
+        assert(std::regex_match(s, m, std::regex("-(.*),\\1-", std::regex_constants::extended)));
+        assert(m.size() == 2);
+        assert(!m.prefix().matched);
+        assert(m.prefix().first == s);
+        assert(m.prefix().second == m[0].first);
+        assert(!m.suffix().matched);
+        assert(m.suffix().first == m[0].second);
+        assert(m.suffix().second == m[0].second);
+        assert(m.length(0) >= 0 && static_cast<size_t>(m.length(0)) == std::char_traits<char>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
+        assert(m.length(1) == 2);
+        assert(m.position(1) == 1);
+        assert(m.str(1) == "ab");
+    }
+    {
+        std::cmatch m;
+        const char s[] = "-ab,ab-";
         assert(std::regex_match(s, m, std::regex("-.*,.*-", std::regex_constants::extended)));
         assert(m.size() == 1);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);
         assert(m.prefix().second == m[0].first);
         assert(!m.suffix().matched);
         assert(m.suffix().first == m[0].second);
         assert(m.suffix().second == m[0].second);
std::locale::global(std::locale("C"));
         std::wcmatch m;
         const wchar_t s[] = L"-ab,ab-";
         assert(!std::regex_match(s, m, std::wregex(L"-(.*),\1-", std::regex_constants::extended)));
         assert(m.size() == 0);
     }
     {
         std::wcmatch m;
         const wchar_t s[] = L"-ab,ab-";
+        assert(std::regex_match(s, m, std::wregex(L"-(.*),\\1-", std::regex_constants::extended)));
+        assert(m.size() == 2);
+        assert(!m.prefix().matched);
+        assert(m.prefix().first == s);
+        assert(m.prefix().second == m[0].first);
+        assert(!m.suffix().matched);
+        assert(m.suffix().first == m[0].second);
+        assert(m.suffix().second == m[0].second);
+        assert(m.length(0) >= 0 && static_cast<size_t>(m.length(0)) == std::char_traits<wchar_t>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
+        assert(m.length(1) == 2);
+        assert(m.position(1) == 1);
+        assert(m.str(1) == L"ab");
+    }
+    {
+        std::wcmatch m;
+        const wchar_t s[] = L"-ab,ab-";
         assert(std::regex_match(s, m, std::wregex(L"-.*,.*-", std::regex_constants::extended)));
         assert(m.size() == 1);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);
         assert(m.prefix().second == m[0].first);
         assert(!m.suffix().matched);
         assert(m.suffix().first == m[0].second);
         assert(m.suffix().second == m[0].second);

libcxx/test/std/re/re.alg/re.alg.search/extended.pass.cpp

int main(int, char**)
         std::cmatch m;
         const char s[] = "-ab,ab-";
         assert(!std::regex_search(s, m, std::regex("-(.*),\1-", std::regex_constants::extended)));
         assert(m.size() == 0);
     }
     {
         std::cmatch m;
         const char s[] = "-ab,ab-";
+        assert(std::regex_search(s, m, std::regex("-(.*),\\1-", std::regex_constants::extended)));
+        assert(m.size() == 2);
+        assert(!m.prefix().matched);
+        assert(m.prefix().first == s);
+        assert(m.prefix().second == m[0].first);
+        assert(!m.suffix().matched);
+        assert(m.suffix().first == m[0].second);
+        assert(m.suffix().second == m[0].second);
+        assert(m.length(0) >= 0 && static_cast<size_t>(m.length(0)) == std::char_traits<char>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
+        assert(m.length(1) == 2);
+        assert(m.position(1) == 1);
+        assert(m.str(1) == "ab");
+    }
+    {
+        std::cmatch m;
+        const char s[] = "-ab,ab-";
         assert(std::regex_search(s, m, std::regex("-.*,.*-", std::regex_constants::extended)));
         assert(m.size() == 1);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);
         assert(m.prefix().second == m[0].first);
         assert(!m.suffix().matched);
         assert(m.suffix().first == m[0].second);
         assert(m.suffix().second == m[0].second);
std::locale::global(std::locale("C"));
         std::wcmatch m;
         const wchar_t s[] = L"-ab,ab-";
         assert(!std::regex_search(s, m, std::wregex(L"-(.*),\1-", std::regex_constants::extended)));
         assert(m.size() == 0);
     }
     {
         std::wcmatch m;
         const wchar_t s[] = L"-ab,ab-";
+        assert(std::regex_search(s, m, std::wregex(L"-(.*),\\1-", std::regex_constants::extended)));
+        assert(m.size() == 2);
+        assert(!m.prefix().matched);
+        assert(m.prefix().first == s);
+        assert(m.prefix().second == m[0].first);
+        assert(!m.suffix().matched);
+        assert(m.suffix().first == m[0].second);
+        assert(m.suffix().second == m[0].second);
+        assert(m.length(0) >= 0 && static_cast<size_t>(m.length(0)) == std::char_traits<wchar_t>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
+        assert(m.length(1) == 2);
+        assert(m.position(1) == 1);
+        assert(m.str(1) == L"ab");
+    }
+    {
+        std::wcmatch m;
+        const wchar_t s[] = L"-ab,ab-";
         assert(std::regex_search(s, m, std::wregex(L"-.*,.*-", std::regex_constants::extended)));
         assert(m.size() == 1);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);
         assert(m.prefix().second == m[0].first);
         assert(!m.suffix().matched);
         assert(m.suffix().first == m[0].second);
         assert(m.suffix().second == m[0].second);