[libcxx] Make regex_match backtrack when search fails

[timshen]

Summary

Fixes PR19851.
alg.re.match/ecma.pass.cpp still XFAILS on linux, but after commenting out
locale-related tests, it passes. I don't have a freebsd machine to produce a
full pass.

[mclow.lists]

LGTM. One minor suggestion (adding a comment to a test).

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

374 ↗

(On Diff #75995)

I would be tempted to put a reference to http://wg21.link/LWG2273 here. (in a comment)

[timshen]

Added http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2273 as comments.

[timshen]

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

374 ↗

(On Diff #75995)

For consistency with other LWG defects references, I used the open-std.org link.

libcxx/trunk/include/regex

enum match_flag_type
     match_any         = 1 << 4,
     match_not_null    = 1 << 5,
     match_continuous  = 1 << 6,
     match_prev_avail  = 1 << 7,
     format_default    = 0,
     format_sed        = 1 << 8,
     format_no_copy    = 1 << 9,
     format_first_only = 1 << 10,
-    __no_update_pos   = 1 << 11
+    __no_update_pos   = 1 << 11,
+    __full_match      = 1 << 12
 };
 
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR
 match_flag_type
 operator~(match_flag_type __x)
 {
     return match_flag_type(~int(__x) & 0x0FFF);

 };
 
 template <class _CharT, class _Traits>
 void
 __lookahead<_CharT, _Traits>::__exec(__state& __s) const
 {
     match_results<const _CharT*> __m;
     __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);
-    bool __matched = __exp_.__match_at_start_ecma(__s.__current_, __s.__last_,
-                                                  __m,
-                                                  __s.__flags_ | regex_constants::match_continuous,
-                                                  __s.__at_first_ && __s.__current_ == __s.__first_);
+    bool __matched = __exp_.__match_at_start_ecma(
+        __s.__current_, __s.__last_,
+        (__s.__flags_ | regex_constants::match_continuous) &
+        ~regex_constants::__full_match,
     if (__matched != __invert_)
     {
         __s.__do_ = __state::__accept_but_not_consume;
         __s.__node_ = this->first();
         for (unsigned __i = 1; __i < __m.size(); ++__i) {
             __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
         }
     }
if (__st)
         do
         {
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
-                if (__flags & regex_constants::match_not_null &&
+                if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)
                 {
                   __states.pop_back();
                   break;
                 }
+                if ((__flags & regex_constants::__full_match) &&
+                    __s.__current_ != __last)
+                {
+                  __states.pop_back();
+                  break;
+                }
                 __m.__matches_[0].first = __first;
                 __m.__matches_[0].second = _VSTD::next(__first, __s.__current_ - __first);
                 __m.__matches_[0].matched = true;
                 for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
                     __m.__matches_[__i+1] = __s.__sub_matches_[__i];
                 return true;
             case __state::__accept_and_consume:
             case __state::__repeat:
if (__st)
         do
         {
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
-                if (__flags & regex_constants::match_not_null &&
+                if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)
                 {
                   __states.pop_back();
                   break;
                 }
+                if ((__flags & regex_constants::__full_match) &&
+                    __s.__current_ != __last)
+                {
+                  __states.pop_back();
+                  break;
+                }
                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
                     __highest_j = __s.__current_ - __s.__first_;
                 __matched = true;
                 if (__highest_j == _Np)
                     __states.clear();
                 else
                     __states.pop_back();
                 break;
if (__st)
         do
         {
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
-                if (__flags & regex_constants::match_not_null &&
+                if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)
                 {
                   __states.pop_back();
                   break;
                 }
+                if ((__flags & regex_constants::__full_match) &&
+                    __s.__current_ != __last)
+                {
+                  __states.pop_back();
+                  break;
+                }
                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
                 {
                     __highest_j = __s.__current_ - __s.__first_;
                     __best_state = __s;
                 }
                 __matched = true;
                 if (__highest_j == _Np)
                     __states.clear();

 
 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
 bool
 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
             match_results<_BidirectionalIterator, _Allocator>& __m,
             const basic_regex<_CharT, _Traits>& __e,
             regex_constants::match_flag_type __flags = regex_constants::match_default)
 {
-    bool __r = _VSTD::regex_search(__first, __last, __m, __e,
-                            __flags | regex_constants::match_continuous);
+    bool __r = _VSTD::regex_search(
+        __first, __last, __m, __e,
+        __flags | regex_constants::match_continuous |
+        regex_constants::__full_match);
     if (__r)
     {
         __r = !__m.suffix().matched;
         if (!__r)
             __m.__matches_.clear();
     }
     return __r;
 }

libcxx/trunk/test/std/re/re.alg/re.alg.match/ecma.pass.cpp

int main()
     {
         std::cmatch m;
         const char s[] = "adefghic";
         assert(!std::regex_match(s, m, std::regex("a.{3,5}c")));
         assert(m.size() == 0);
     }
     {
         std::cmatch m;
+        // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2273
         const char s[] = "tournament";
-        assert(!std::regex_match(s, m, std::regex("tour|to|tournament")));
-        assert(m.size() == 0);
+        assert(std::regex_match(s, m, std::regex("tour|to|tournament")));
+        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);
+        assert(m.length(0) == std::char_traits<char>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
     }
     {
         std::cmatch m;
+        // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2273
         const char s[] = "tournamenttotour";
-        assert(!std::regex_match(s, m, std::regex("(tour|to|tournament)+",
+        assert(
+            std::regex_match(s, m, std::regex("(tour|to|tournament)+",
                                               std::regex_constants::nosubs)));
-        assert(m.size() == 0);
+        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);
+        assert(m.length(0) == std::char_traits<char>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
     }
     {
         std::cmatch m;
         const char s[] = "ttotour";
         assert(std::regex_match(s, m, std::regex("(tour|to|t)+")));
         assert(m.size() == 2);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);

     {
         std::wcmatch m;
         const wchar_t s[] = L"adefghic";
         assert(!std::regex_match(s, m, std::wregex(L"a.{3,5}c")));
         assert(m.size() == 0);
     }
     {
         std::wcmatch m;
+        // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2273
         const wchar_t s[] = L"tournament";
-        assert(!std::regex_match(s, m, std::wregex(L"tour|to|tournament")));
-        assert(m.size() == 0);
+        assert(std::regex_match(s, m, std::wregex(L"tour|to|tournament")));
+        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);
+        assert(m.length(0) == std::char_traits<wchar_t>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
     }
     {
         std::wcmatch m;
+        // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2273
         const wchar_t s[] = L"tournamenttotour";
-        assert(!std::regex_match(s, m, std::wregex(L"(tour|to|tournament)+",
+        assert(
+            std::regex_match(s, m, std::wregex(L"(tour|to|tournament)+",
                                                std::regex_constants::nosubs)));
-        assert(m.size() == 0);
+        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);
+        assert(m.length(0) == std::char_traits<wchar_t>::length(s));
+        assert(m.position(0) == 0);
+        assert(m.str(0) == s);
     }
     {
         std::wcmatch m;
         const wchar_t s[] = L"ttotour";
         assert(std::regex_match(s, m, std::wregex(L"(tour|to|t)+")));
         assert(m.size() == 2);
         assert(!m.prefix().matched);
         assert(m.prefix().first == s);