[libcxx] regex: fix backreferences in forward assertions

[pammon]

Summary

In regex, forward assertions like '(?=stuff)' are implemented by
constructing a child regular expression 'stuff' and matching that.
If the child regular expression contains a backreference, this would
trip an assertion or reference the wrong capture group, because the
child was ignorant of the capture groups of its parent. For example,
/(x)(?=\1)/ would trip an assertion.

Address this by propagating submatches into the child, so that
backreferences reference the correct capture groups. This also allows us
to eliminate the mexp_ field, because the child expression shares the
entire submatch array with the parent.

[pammon]

ping?

[Qix-]

Ping @EricWF - few years but this is still an issue, rendering ECMAscript regex backreferences almost entirely broken in libcxx :/ Would be great to get a champion for it. OP has indicated on Github that they'd be happy to rebase.

include/regex

private:
     void __push_char(value_type __c);
     void __push_back_ref(int __i);
     void __push_alternation(__owns_one_state<_CharT>* __sa,
                             __owns_one_state<_CharT>* __sb);
     void __push_begin_marked_subexpression();
     void __push_end_marked_subexpression(unsigned);
     void __push_empty();
     void __push_word_boundary(bool);
-    void __push_lookahead(const basic_regex&, bool, unsigned);
+    void __push_lookahead(basic_regex, bool);
 
     template <class _Allocator>
         bool
         __search(const _CharT* __first, const _CharT* __last,
                  match_results<const _CharT*, _Allocator>& __m,
                  regex_constants::match_flag_type __flags) const;
 
     template <class _Allocator>
         bool
         __match_at_start(const _CharT* __first, const _CharT* __last,
                  match_results<const _CharT*, _Allocator>& __m,
                  regex_constants::match_flag_type __flags, bool) const;
     template <class _Allocator>
         bool
         __match_at_start_ecma(const _CharT* __first, const _CharT* __last,
                  match_results<const _CharT*, _Allocator>& __m,
+                 const vector<sub_match<const _CharT *>> &incoming_sub_matches,
                  regex_constants::match_flag_type __flags, bool) const;
     template <class _Allocator>
         bool
         __match_at_start_posix_nosubs(const _CharT* __first, const _CharT* __last,
                  match_results<const _CharT*, _Allocator>& __m,
                  regex_constants::match_flag_type __flags, bool) const;
     template <class _Allocator>
         bool

 
 template <class _CharT, class _Traits>
 class __lookahead
     : public __owns_one_state<_CharT>
 {
     typedef __owns_one_state<_CharT> base;
 
     basic_regex<_CharT, _Traits> __exp_;
-    unsigned __mexp_;
     bool __invert_;
 
     __lookahead(const __lookahead&);
     __lookahead& operator=(const __lookahead&);
 public:
     typedef _VSTD::__state<_CharT> __state;
 
     _LIBCPP_INLINE_VISIBILITY
-    __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
-        : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}
+    __lookahead(basic_regex<_CharT, _Traits> __exp, bool __invert, __node<_CharT>* __s)
+        : base(__s), __exp_(move(__exp)), __invert_(__invert) {}
 
     virtual void __exec(__state&) const;
 };
 
 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,
+        __m, __s.__sub_matches_,
         (__s.__flags_ | regex_constants::match_continuous) &
         ~regex_constants::__full_match,
         __s.__at_first_ && __s.__current_ == __s.__first_);
     if (__matched != __invert_)
     {
         __s.__do_ = __state::__accept_but_not_consume;
         __s.__node_ = this->first();
+        if (__matched) {
             for (unsigned __i = 1; __i < __m.size(); ++__i) {
-            __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
+                __s.__sub_matches_[__i - 1] = __m.__matches_[__i];
+            }
         }
     }
     else
     {
         __s.__do_ = __state::__reject;
         __s.__node_ = nullptr;
     }
 }
if (__first != __last)
                 _ForwardIterator __temp = _VSTD::next(__first);
                 if (__temp != __last && *__temp == '?')
                 {
                     if (++__temp != __last)
                     {
                         switch (*__temp)
                         {
                         case '=':
-                            {
-                                basic_regex __exp;
-                                __exp.__flags_ = __flags_;
-                                __temp = __exp.__parse(++__temp, __last);
-                                unsigned __mexp = __exp.__marked_count_;
-                                __push_lookahead(_VSTD::move(__exp), false, __marked_count_);
-                                __marked_count_ += __mexp;
-                                if (__temp == __last || *__temp != ')')
-                                    __throw_regex_error<regex_constants::error_paren>();
-                                __first = ++__temp;
-                            }
-                            break;
                         case '!':
                             {
+                                bool __invert = (*__temp == '!');
                                 basic_regex __exp;
                                 __exp.__flags_ = __flags_;
+                                __exp.__marked_count_ = __marked_count_;
                                 __temp = __exp.__parse(++__temp, __last);
                                 unsigned __mexp = __exp.__marked_count_;
-                                __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
-                                __marked_count_ += __mexp;
+                                __push_lookahead(_VSTD::move(__exp), __invert);
+                                __marked_count_ = __mexp;
                                 if (__temp == __last || *__temp != ')')
                                     __throw_regex_error<regex_constants::error_paren>();
                                 __first = ++__temp;
                             }
                             break;
                         }
                     }
                 }
__bracket_expression<_CharT, _Traits>* __r =
                                                   __flags_ & collate);
     __end_->first() = __r;
     __end_ = __r;
     return __r;
 }
 
 template <class _CharT, class _Traits>
 void
-basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp,
-                                               bool __invert,
-                                               unsigned __mexp)
+basic_regex<_CharT, _Traits>::__push_lookahead(basic_regex __exp,
+                                               bool __invert)
 {
-    __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
-                                                           __end_->first(), __mexp);
+    __end_->first() = new __lookahead<_CharT, _Traits>(move(__exp), __invert,
+                                                           __end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 typedef basic_regex<char>    regex;
 typedef basic_regex<wchar_t> wregex;
 
 // sub_match
 

 // regex_search
 
 template <class _CharT, class _Traits>
 template <class _Allocator>
 bool
 basic_regex<_CharT, _Traits>::__match_at_start_ecma(
         const _CharT* __first, const _CharT* __last,
         match_results<const _CharT*, _Allocator>& __m,
+        const vector<sub_match<const _CharT *>> &incoming_sub_matches,
         regex_constants::match_flag_type __flags, bool __at_first) const
 {
     vector<__state> __states;
     __node* __st = __start_.get();
     if (__st)
     {
         sub_match<const _CharT*> __unmatched;
         __unmatched.first   = __last;
         __unmatched.second  = __last;
         __unmatched.matched = false;
+        vector<sub_match<const _CharT *>> sub_matches = incoming_sub_matches;
+        sub_matches.resize(mark_count(), __unmatched);
 
         __states.push_back(__state());
         __states.back().__do_ = 0;
         __states.back().__first_ = __first;
         __states.back().__current_ = __first;
         __states.back().__last_ = __last;
-        __states.back().__sub_matches_.resize(mark_count(), __unmatched);
+        __states.back().__sub_matches_ = move(sub_matches);
         __states.back().__loop_data_.resize(__loop_count());
         __states.back().__node_ = __st;
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
         do
         {
             __state& __s = __states.back();
             if (__s.__node_)

 template <class _Allocator>
 bool
 basic_regex<_CharT, _Traits>::__match_at_start(
         const _CharT* __first, const _CharT* __last,
         match_results<const _CharT*, _Allocator>& __m,
         regex_constants::match_flag_type __flags, bool __at_first) const
 {
     if ((__flags_ & 0x1F0) == ECMAScript)
-        return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
+        return __match_at_start_ecma(__first, __last, __m, {}, __flags, __at_first);
     if (mark_count() == 0)
         return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
     return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
 }
 
 template <class _CharT, class _Traits>
 template <class _Allocator>
 bool

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

std::locale::global(std::locale(LOCALE_cs_CZ_ISO8859_2));
         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);
     }
     {
-        std::cmatch m;
+      const char s[] = "abcabc";
+      assert(std::regex_match(s, m, std::regex("(.+)(?=\\1)(\\1)")));
+      assert(m.size() == 3);
+      assert(m.str(1) == "abc");
+      assert(m.str(2) == "abc");
+    }
+    {
+      std::cmatch m;
+      const char s[] = "aa";
+      assert(std::regex_match(s, m, std::regex("(a+)(?!\\1)(a*)")));
+      assert(m.size() == 3);
+      assert(m.str(1) == "aa");
+      assert(m.str(2) == "");
+    }
+    {
+        std::cmatch m;
         const char s[] = "foobar";
         assert(std::regex_match(s, m, std::regex("[^\\0]*")));
         assert(m.size() == 1);
     }
     {
         std::cmatch m;
         const char s[] = "foo\0bar";
         assert(std::regex_match(s, s+7, m, std::regex("[abfor\\0]*")));