[libcxx] Keep track of heap allocated regex states

[timshen]

Summary

Build abstraction on regex's allocation

This fixes a fuzzer crasher from a huge input (provided by Marshall), which seems to be a stackoverflow during destruction. However, I can't reproduce Marshall's crasher even before the change.

No new tests are added, but all old tests pass. I didn't really run valgrind on tests to check for memory leak, as the new allocation is basically correct by construction (only one call site uses new, no explicit delete calls).

[timshen]

Add an assertion to __push.

[mclow.lists]

A couple of notes.

• This change means that <regex> now requires C++11 (the new __push function w/ the varargs). I don't know how important that is; but I'm pretty sure libc++ currently provides <regex> in C++03 mode.
• This is an ABI change; existing code that was compiled with the "old" <regex> implementation will not interoperate with this.
• I think that there may be some exception-safety issues in __push; if the push_back throws, I think we leak.

libcxx/include/regex

4642

Why auto here?

How about unique_ptr<_NodeType> instead, and then

__storage_.__push(__ret.get());
return __ret.release()

[mclow.lists]

I can confirm that with this patch the (large) regex that used to cause a stack overflow does not any more.

[timshen]

In D39308#907424, @mclow.lists wrote:

A couple of notes.

Sorry for the oversights, when a C++11(-only :) contributor doesn't care about ABI stability, nor exceptions, he contributes naive code. :P I'll fix them.

• This change means that <regex> now requires C++11 (the new __push function w/ the varargs). I don't know how important that is; but I'm pretty sure libc++ currently provides <regex> in C++03 mode.
• This is an ABI change; existing code that was compiled with the "old" <regex> implementation will not interoperate with this.

Can you give an example on what would go wrong, while it's not expected to go wrong?

• I think that there may be some exception-safety issues in __push; if the push_back throws, I think we leak.

[timshen]

Remove the uses of variadic template and auto.

I'm not sure of how to implement this without a ABI change (the addition of __storage_).

[mclow.lists]

What we need to do here is to here is to add a new macro _LIBCPP_ABI_REGEX_MEMORY in <__config> (around line 89) and then make these changes available only when this macro is defined.

By default - we get no change.
If _LIBCPP_ABI_REGEX_MEMORY is defined, we get the new behavior.

Then we can start adding other ABI changes as well.

libcxx/include/regex

 #include <initializer_list>
 #include <utility>
 #include <iterator>
 #include <string>
 #include <memory>
 #include <vector>
 #include <deque>
 
+#include <__debug>
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
class __owns_one_state
     : public __has_one_state<_CharT>
 {
     typedef __has_one_state<_CharT> base;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     explicit __owns_one_state(__node<_CharT>* __s)
         : base(__s) {}
-
-    virtual ~__owns_one_state();
 };
 
-template <class _CharT>
-__owns_one_state<_CharT>::~__owns_one_state()
-{
-    delete this->first();
-}
-
 // __empty_state
 
 template <class _CharT>
 class __empty_state
     : public __owns_one_state<_CharT>
 {
     typedef __owns_one_state<_CharT> base;
 
class __owns_two_states
 
     base* __second_;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     explicit __owns_two_states(__node<_CharT>* __s1, base* __s2)
         : base(__s1), __second_(__s2) {}
 
-    virtual ~__owns_two_states();
-
     _LIBCPP_INLINE_VISIBILITY
     base*  second() const {return __second_;}
     _LIBCPP_INLINE_VISIBILITY
     base*& second()       {return __second_;}
 };
 
-template <class _CharT>
-__owns_two_states<_CharT>::~__owns_two_states()
-{
-    delete __second_;
-}
-
 // __loop
 
 template <class _CharT>
 class __loop
     : public __owns_two_states<_CharT>
 {
     typedef __owns_two_states<_CharT> base;
 
public:
     // types:
     typedef _CharT                              value_type;
     typedef _Traits                             traits_type;
     typedef typename _Traits::string_type       string_type;
     typedef regex_constants::syntax_option_type flag_type;
     typedef typename _Traits::locale_type       locale_type;
 
 private:
+    typedef _VSTD::__state<_CharT> __state;
+    typedef _VSTD::__node<_CharT> __node;
+
+    // Shared, append-only storage for regexes.
+    class __storage
+    {
+      // invariant: __v_ is never nullptr.
+      shared_ptr<vector<unique_ptr<__node>>> __v_;
+
+    public:
+      __storage() : __v_(make_shared<vector<unique_ptr<__node>>>()) {}
+      __storage(const __storage&) = default;
+      __storage(__storage&& __rhs) : __v_(std::move(__rhs.__v_))
+      { __rhs.__clear(); }
+
+      __storage& operator=(const __storage&) = default;
+      __storage& operator=(__storage&& __rhs)
+      {
+        __v_ = std::move(__rhs.__v_);
+        __rhs.__clear();
+        return *this;
+      }
+
+      void __push(__node* __n)
+      {
+        _LIBCPP_ASSERT(__v_.use_count() == 1,
+                       "__push should be called only "
+                       "when the storage is not shared");
+        __v_->emplace_back(__n);
+      }
+
+      void __clear()
+      { __v_ = make_shared<vector<unique_ptr<__node>>>(); }
+    };
+
     _Traits   __traits_;
     flag_type __flags_;
     unsigned __marked_count_;
     unsigned __loop_count_;
     int __open_count_;
-    shared_ptr<__empty_state<_CharT> > __start_;
+    __storage __storage_;
+    __empty_state<_CharT>* __start_;
     __owns_one_state<_CharT>* __end_;
 
-    typedef _VSTD::__state<_CharT> __state;
-    typedef _VSTD::__node<_CharT> __node;
-
 public:
     // constants:
     static const regex_constants::syntax_option_type icase = regex_constants::icase;
     static const regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
     static const regex_constants::syntax_option_type optimize = regex_constants::optimize;
     static const regex_constants::syntax_option_type collate = regex_constants::collate;
     static const regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
     static const regex_constants::syntax_option_type basic = regex_constants::basic;
     static const regex_constants::syntax_option_type extended = regex_constants::extended;
     static const regex_constants::syntax_option_type awk = regex_constants::awk;
     static const regex_constants::syntax_option_type grep = regex_constants::grep;
     static const regex_constants::syntax_option_type egrep = regex_constants::egrep;
 
     // construct/copy/destroy:
     _LIBCPP_INLINE_VISIBILITY
     basic_regex()
         : __flags_(), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {}
     _LIBCPP_INLINE_VISIBILITY
     explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {__parse(__p, __p + __traits_.length(__p));}
     _LIBCPP_INLINE_VISIBILITY
     basic_regex(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript)
         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {__parse(__p, __p + __len);}
 //     basic_regex(const basic_regex&) = default;
 //     basic_regex(basic_regex&&) = default;
     template <class _ST, class _SA>
         _LIBCPP_INLINE_VISIBILITY
         explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
                              flag_type __f = regex_constants::ECMAScript)
         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {__parse(__p.begin(), __p.end());}
     template <class _ForwardIterator>
         _LIBCPP_INLINE_VISIBILITY
         basic_regex(_ForwardIterator __first, _ForwardIterator __last,
                     flag_type __f = regex_constants::ECMAScript)
         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {__parse(__first, __last);}
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     basic_regex(initializer_list<value_type> __il,
                 flag_type __f = regex_constants::ECMAScript)
         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
-          __end_(0)
+          __start_(0), __end_(0)
         {__parse(__il.begin(), __il.end());}
 #endif  // _LIBCPP_CXX03_LANG
 
 //    ~basic_regex() = default;
 
 //     basic_regex& operator=(const basic_regex&) = default;
 //     basic_regex& operator=(basic_regex&&) = default;
     _LIBCPP_INLINE_VISIBILITY
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     flag_type flags() const {return __flags_;}
 
     // locale:
     _LIBCPP_INLINE_VISIBILITY
     locale_type imbue(locale_type __loc)
     {
         __member_init(ECMAScript);
-        __start_.reset();
+        __storage_.__clear();
+        __start_ = nullptr;
         return __traits_.imbue(__loc);
     }
     _LIBCPP_INLINE_VISIBILITY
     locale_type getloc() const {return __traits_.getloc();}
 
     // swap:
     void swap(basic_regex& __r);
 
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);
 
+    template <class _NodeType, class... _Args>
+        _NodeType* __push(_Args&&... __args);
+
     _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)

 basic_regex<_CharT, _Traits>::swap(basic_regex& __r)
 {
     using _VSTD::swap;
     swap(__traits_, __r.__traits_);
     swap(__flags_, __r.__flags_);
     swap(__marked_count_, __r.__marked_count_);
     swap(__loop_count_, __r.__loop_count_);
     swap(__open_count_, __r.__open_count_);
+    swap(__storage_, __r.__storage_);
     swap(__start_, __r.__start_);
     swap(__end_, __r.__end_);
 }
 
 template <class _CharT, class _Traits>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y)

 
 template <class _CharT, class _Traits>
 template <class _ForwardIterator>
 _ForwardIterator
 basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
                                       _ForwardIterator __last)
 {
     {
-        unique_ptr<__node> __h(new __end_state<_CharT>);
-        __start_.reset(new __empty_state<_CharT>(__h.get()));
-        __h.release();
-        __end_ = __start_.get();
+        __storage_.__clear();
+        __start_ = __push<__empty_state<_CharT>>(__push<__end_state<_CharT>>());
+        __end_ = __start_;
     }
     switch (__flags_ & 0x1F0)
     {
     case ECMAScript:
         __first = __parse_ecma_exp(__first, __last);
         break;
     case basic:
         __first = __parse_basic_reg_exp(__first, __last);
while (__first != __last)
         __first = __t1;
         if (__first != __last)
             ++__first;
     }
     return __first;
 }
 
 template <class _CharT, class _Traits>
+template <class _NodeType, class... _Args>
+_NodeType* basic_regex<_CharT, _Traits>::__push(_Args&&... __args)
+{
+  auto __ret = new _NodeType(std::forward<_Args>(__args)...);
+  __storage_.__push(__ret);
+  return __ret;
+}
+
+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()));
+    __empty_state<_CharT>* __e1(__push<__empty_state<_CharT>>(__end_->first()));
     __end_->first() = nullptr;
-    unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,
-                __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
+    __loop<_CharT>* __e2(__push<__loop<_CharT>>(__loop_count_,
+                __s->first(), __e1, __mexp_begin, __mexp_end, __greedy,
                 __min, __max));
     __s->first() = nullptr;
-    __e1.release();
-    __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
+    __end_->first() = __push<__repeat_one_loop<_CharT>>(__e2);
     __end_ = __e2->second();
-    __s->first() = __e2.release();
+    __s->first() = __e2;
     ++__loop_count_;
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_char(value_type __c)
 {
     if (flags() & icase)
-        __end_->first() = new __match_char_icase<_CharT, _Traits>
+        __end_->first() = __push<__match_char_icase<_CharT, _Traits>>
                                               (__traits_, __c, __end_->first());
     else if (flags() & collate)
-        __end_->first() = new __match_char_collate<_CharT, _Traits>
+        __end_->first() = __push<__match_char_collate<_CharT, _Traits>>
                                               (__traits_, __c, __end_->first());
     else
-        __end_->first() = new __match_char<_CharT>(__c, __end_->first());
+        __end_->first() = __push<__match_char<_CharT>>(__c, __end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
 {
     if (!(__flags_ & nosubs))
     {
-        __end_->first() =
-                new __begin_marked_subexpression<_CharT>(++__marked_count_,
-                                                         __end_->first());
+        __end_->first() = __push<__begin_marked_subexpression<_CharT>>(
+                ++__marked_count_, __end_->first());
         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
     }
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
 {
     if (!(__flags_ & nosubs))
     {
-        __end_->first() =
-                new __end_marked_subexpression<_CharT>(__sub, __end_->first());
+        __end_->first() = __push<__end_marked_subexpression<_CharT>>(
+                __sub, __end_->first());
         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
     }
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_l_anchor()
 {
-    __end_->first() = new __l_anchor<_CharT>(__end_->first());
+    __end_->first() = __push<__l_anchor<_CharT>>(__end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_r_anchor()
 {
-    __end_->first() = new __r_anchor<_CharT>(__end_->first());
+    __end_->first() = __push<__r_anchor<_CharT>>(__end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_match_any()
 {
-    __end_->first() = new __match_any<_CharT>(__end_->first());
+    __end_->first() = __push<__match_any<_CharT>>(__end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_match_any_but_newline()
 {
-    __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
+    __end_->first() = __push<__match_any_but_newline<_CharT>>(__end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_empty()
 {
-    __end_->first() = new __empty_state<_CharT>(__end_->first());
+    __end_->first() = __push<__empty_state<_CharT>>(__end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert)
 {
-    __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert,
-                                                           __end_->first());
+    __end_->first() = __push<__word_boundary<_CharT, _Traits>>(
+            __traits_, __invert, __end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_back_ref(int __i)
 {
     if (flags() & icase)
-        __end_->first() = new __back_ref_icase<_CharT, _Traits>
+        __end_->first() = __push<__back_ref_icase<_CharT, _Traits>>
                                               (__traits_, __i, __end_->first());
     else if (flags() & collate)
-        __end_->first() = new __back_ref_collate<_CharT, _Traits>
+        __end_->first() = __push<__back_ref_collate<_CharT, _Traits>>
                                               (__traits_, __i, __end_->first());
     else
-        __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
+        __end_->first() = __push<__back_ref<_CharT>>(__i, __end_->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa,
                                                  __owns_one_state<_CharT>* __ea)
 {
-    __sa->first() = new __alternate<_CharT>(
+    __sa->first() = __push<__alternate<_CharT>>(
                          static_cast<__owns_one_state<_CharT>*>(__sa->first()),
                          static_cast<__owns_one_state<_CharT>*>(__ea->first()));
     __ea->first() = nullptr;
-    __ea->first() = new __empty_state<_CharT>(__end_->first());
+    __ea->first() = __push<__empty_state<_CharT>>(__end_->first());
     __end_->first() = nullptr;
-    __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
+    __end_->first() = __push<__empty_non_own_state<_CharT>>(__ea->first());
     __end_ = static_cast<__owns_one_state<_CharT>*>(__ea->first());
 }
 
 template <class _CharT, class _Traits>
 __bracket_expression<_CharT, _Traits>*
 basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate)
 {
     __bracket_expression<_CharT, _Traits>* __r =
-        new __bracket_expression<_CharT, _Traits>(__traits_, __end_->first(),
-                                                  __negate, __flags_ & icase,
-                                                  __flags_ & collate);
+        __push<__bracket_expression<_CharT, _Traits>>(
+            __traits_, __end_->first(), __negate, __flags_ & icase,
     __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)
 {
-    __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
-                                                           __end_->first(), __mexp);
+    __end_->first() = __push<__lookahead<_CharT, _Traits>>(
+            __exp, __invert, __end_->first(), __mexp);
     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
 }
 
 typedef basic_regex<char>    regex;
 typedef basic_regex<wchar_t> wregex;
 
 // sub_match
 

 template <class _Allocator>
 bool
 basic_regex<_CharT, _Traits>::__match_at_start_ecma(
         const _CharT* __first, const _CharT* __last,
         match_results<const _CharT*, _Allocator>& __m,
         regex_constants::match_flag_type __flags, bool __at_first) const
 {
     vector<__state> __states;
-    __node* __st = __start_.get();
+    __node* __st = __start_;
     if (__st)
     {
         sub_match<const _CharT*> __unmatched;
         __unmatched.first   = __last;
         __unmatched.second  = __last;
         __unmatched.matched = false;
 
         __states.push_back(__state());

 basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
         const _CharT* __first, const _CharT* __last,
         match_results<const _CharT*, _Allocator>& __m,
         regex_constants::match_flag_type __flags, bool __at_first) const
 {
     deque<__state> __states;
     ptrdiff_t __highest_j = 0;
     ptrdiff_t _Np = _VSTD::distance(__first, __last);
-    __node* __st = __start_.get();
+    __node* __st = __start_;
     if (__st)
     {
         __states.push_back(__state());
         __states.back().__do_ = 0;
         __states.back().__first_ = __first;
         __states.back().__current_ = __first;
         __states.back().__last_ = __last;
         __states.back().__loop_data_.resize(__loop_count());
basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
         match_results<const _CharT*, _Allocator>& __m,
         regex_constants::match_flag_type __flags, bool __at_first) const
 {
     vector<__state> __states;
     __state __best_state;
     ptrdiff_t __j = 0;
     ptrdiff_t __highest_j = 0;
     ptrdiff_t _Np = _VSTD::distance(__first, __last);
-    __node* __st = __start_.get();
+    __node* __st = __start_;
     if (__st)
     {
         sub_match<const _CharT*> __unmatched;
         __unmatched.first   = __last;
         __unmatched.second  = __last;
         __unmatched.matched = false;
 
         __states.push_back(__state());