diff --git a/include/regex b/include/regex
index b1deaeb..c1bacff 100644
--- a/include/regex
+++ b/include/regex
@@ -726,6 +726,7 @@
 #include <string>
 #include <memory>
 #include <vector>
+#include <__split_buffer>
 
 #pragma GCC system_header
 
@@ -1214,214 +1215,520 @@
     return __value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
 }
 
-template <class _CharT> class __transition;
+template <class _CharT> class __state;
+
+template <class _CharT>
+struct __command
+{
+    enum
+    {
+        __end_state = -1000,
+        __consume_input,  // -999
+//        __try_state,      // -998
+        __begin_marked_expr, // -998
+        __end_marked_expr,   // -997
+        __go_back,           // -996
+        __accept_and_consume,  // -995
+        __accept_but_not_consume,  // -994
+        __reject,                  // -993
+        __zero_loop_count,
+        __increment_loop_count,
+        __zero_marked_exprs,
+    };
+
+    typedef __state<_CharT> __state;
+
+    int __do_;
+    int __data_;
+    const __state* first;
+    const __state* second;
+
+    __command() : __do_(__reject), first(nullptr), second(nullptr) {}
+    explicit __command(int __do)
+        : __do_(__do), first(nullptr), second(nullptr) {}
+    __command(int __do, const __state* __s1, const __state* __s2 = nullptr)
+        : __do_(__do), first(__s1), second(__s2) {}
+    explicit __command(const __state* __s1, const __state* __s2 = nullptr)
+        : __do_(0), first(__s1), second(__s2) {}
+};
+
+template <class _BidirectionalIterator> class sub_match;
+
+// __state
 
 template <class _CharT>
 class __state
 {
-    typedef __transition<_CharT> __transition;
-    __transition* __t1_;
-    __transition* __t2_;
-    int __state_;
-    enum
-    {
-        __not_tried = 0,
-        __1_succeded = 1,
-        __1_failed = 2,
-        __2_not_tried = 0,
-        __2_succeded = 4,
-        __2_failed = 8
-    };
-
     __state(const __state&);
     __state& operator=(const __state&);
 public:
-    __state()
-        : __t1_(), __t2_(), __state_() {}
-    ~__state();
+    typedef __command<_CharT> __command;
 
-    __state* __test(_CharT __c, bool& __consume, unsigned& __begin_sub,
-                                                 unsigned& __end_sub);
+    __state() {}
+    virtual ~__state() {}
 
-    void __add_one(__transition* __t) {__t1_ = __t;}
-
-    void __reset_state();
+    virtual __command __test(const _CharT* __first, const _CharT* __current,
+                             const _CharT* __last,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>* __m,
+                             regex_constants::match_flag_type __flags) const = 0;
 };
 
-template <class _CharT>
-__state<_CharT>::~__state()
-{
-    delete __t1_;
-    delete __t2_;
-}
+// __end_state
 
 template <class _CharT>
-__state<_CharT>*
-__state<_CharT>::__test(_CharT __c, bool& __consume, unsigned& __begin_sub,
-                                                     unsigned& __end_sub)
+class __end_state
+    : public __state<_CharT>
 {
-    __state* __r = nullptr;
-    if ((__state_ & 3) == 0)
-    {
-        if (__t1_)
-        {
-            __r = __t1_->__test(__c, __consume, __begin_sub, __end_sub);
-            if (__r)
-                __state_ |= __1_succeded;
-            else
-                __state_ |= __1_failed;
-        }
-        else
-            __state_ |= __1_failed;
-    }
-    else if ((__state_ & 0xC) == 0)
-    {
-        if (__t2_)
-        {
-            __r = __t2_->__test(__c, __consume, __begin_sub, __end_sub);
-            if (__r)
-                __state_ |= __2_succeded;
-            else
-                __state_ |= __2_failed;
-        }
-        else
-            __state_ |= __2_failed;
-    }
-    return __r;
-}
-
-template <class _CharT>
-void
-__state<_CharT>::__reset_state()
-{
-    __state_ = __not_tried;
-    if (__t1_)
-        __t1_->__reset_state();
-    if (__t2_)
-        __t2_->__reset_state();
-}
-
-template <class _CharT>
-class __transition
-{
-    __transition(const __transition&);
-    __transition& operator=(const __transition&);
-
-protected:
-    typedef __state<_CharT> __state;
-    typedef unique_ptr<__state, void(*)(__state*)> __sptr;
-
-    static void __delete_state(__state* __p) {delete __p;}
-    static void __ignore_state(__state*) {}
-
-    __sptr __sptr_;
 public:
-    __transition(bool __owns, __state* __st)
-        : __sptr_(__st, __owns ? &__delete_state : &__ignore_state) {}
-    virtual ~__transition() {}
+    typedef __command<_CharT> __command;
 
-    virtual __state* __test(_CharT, bool& __consume, unsigned& __begin_sub,
-                                                     unsigned& __end_sub);
+    __end_state() {}
 
-    void __reset_state();
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
 };
 
 template <class _CharT>
-typename __transition<_CharT>::__state*
-__transition<_CharT>::__test(_CharT, bool& __consume, unsigned&, unsigned&)
+__command<_CharT>
+__end_state<_CharT>::__test(const _CharT*, const _CharT*,
+                            const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                            regex_constants::match_flag_type) const
 {
-    __consume = false;
-    return __sptr_.get();
+    return __command(__command::__end_state);
 }
- 
+
+// __has_one_state
+
 template <class _CharT>
-void
-__transition<_CharT>::__reset_state()
+class __has_one_state
+    : public __state<_CharT>
 {
-    if (__sptr_.get_deleter() == &__delete_state)
-        __sptr_->__reset_state();
+    __state<_CharT>* __first_;
+
+public:
+    explicit __has_one_state(__state<_CharT>* __s)
+        : __first_(__s) {}
+
+    __state<_CharT>*  first() const {return __first_;}
+    __state<_CharT>*& first()       {return __first_;}
+};
+
+// __owns_one_state
+
+template <class _CharT>
+class __owns_one_state
+    : public __has_one_state<_CharT>
+{
+    typedef __has_one_state<_CharT> base;
+
+public:
+    explicit __owns_one_state(__state<_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;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __empty_state(__state<_CharT>* __s)
+        : base(__s) {}
+
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__empty_state<_CharT>::__test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    return __command(__command::__accept_but_not_consume, this->first());
+}
+
+// __empty_non_own_state
+
+template <class _CharT>
+class __empty_non_own_state
+    : public __has_one_state<_CharT>
+{
+    typedef __has_one_state<_CharT> base;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __empty_non_own_state(__state<_CharT>* __s)
+        : base(__s) {}
+
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__empty_non_own_state<_CharT>::__test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    return __command(__command::__accept_but_not_consume, this->first());
+}
+
+// __owns_two_states
+
+template <class _CharT>
+class __owns_two_states
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    base* __second_;
+
+public:
+    explicit __owns_two_states(__state<_CharT>* __s1, base* __s2)
+        : base(__s1), __second_(__s2) {}
+
+    virtual ~__owns_two_states();
+
+    base*  second() const {return __second_;}
+    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;
+
+    size_t __min_;
+    size_t __max_;
+    unsigned __loop_id_;
+    bool __greedy_;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __loop(unsigned __loop_id,
+                          __state<_CharT>* __s1, __owns_one_state<_CharT>* __s2,
+                          bool __greedy = true,
+                          size_t __min = 0,
+                          size_t __max = numeric_limits<size_t>::max())
+        : base(__s1, __s2), __min_(__min), __max_(__max), __loop_id_(__loop_id),
+          __greedy_(__greedy) {}
+
+    virtual __command __test(const _CharT* __first, const _CharT* __current,
+                             const _CharT* __last,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type __flags) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__loop<_CharT>::__test(const _CharT* __first, const _CharT* __current,
+                             const _CharT* __last,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>* __m,
+                             regex_constants::match_flag_type __flags) const
+{
+    size_t __count = __lc[__loop_id_];
+    if (__min_ <= __count && __count < __max_)
+        if (__greedy_)
+            return __command(__command::__accept_but_not_consume, this->first(),
+                                                                  this->second());
+        else
+            return __command(__command::__accept_but_not_consume, this->second(),
+                                                                  this->first());
+    if (__min_ <= __count)
+        return __command(__command::__accept_but_not_consume, this->second());
+    if (__count < __max_)
+        return __command(__command::__accept_but_not_consume, this->first());
+    throw regex_error(regex_constants::error_temp);
+}
+
+// __zero_loop_count
+
+template <class _CharT>
+class __zero_loop_count
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    size_t __loop_id_;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __zero_loop_count(size_t __loop_id,
+                          __state<_CharT>* __s1)
+        : base(__s1), __loop_id_(__loop_id) {}
+
+    virtual __command __test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__zero_loop_count<_CharT>::__test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    __lc[__loop_id_] = 0;
+    return __command(__command::__accept_but_not_consume, this->first());
+}
+
+// __increment_loop_count
+
+template <class _CharT>
+class __increment_loop_count
+    : public __has_one_state<_CharT>
+{
+    typedef __has_one_state<_CharT> base;
+
+    size_t __loop_id_;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __increment_loop_count(size_t __loop_id,
+                          __state<_CharT>* __s1)
+        : base(__s1), __loop_id_(__loop_id) {}
+
+    virtual __command __test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__increment_loop_count<_CharT>::__test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>& __lc,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    ++__lc[__loop_id_];
+    return __command(__command::__accept_but_not_consume, this->first());
+}
+
+// __zero_marked_exprs
+
+template <class _CharT>
+class __zero_marked_exprs
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    size_t __begin_;
+    size_t __end_;
+
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __zero_marked_exprs(size_t __begin, size_t __end,
+                          __state<_CharT>* __s1)
+        : base(__s1), __begin_(__begin), __end_(__end) {}
+
+    virtual __command __test(const _CharT*, const _CharT*, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>* __sm,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__zero_marked_exprs<_CharT>::__test(const _CharT*, const _CharT*,
+                             const _CharT* __last,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>* __sm,
+                             regex_constants::match_flag_type) const
+{
+    for (size_t __i = __begin_; __i != __end_; ++__i)
+    {
+        __sm[__i].first = __last;
+        __sm[__i].second = __last;
+        __sm[__i].matched = false;
+    }
+    return __command(__command::__accept_but_not_consume, this->first());
+}
+
+// __begin_marked_subexpression
+
+template <class _CharT>
+class __begin_marked_subexpression
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    __begin_marked_subexpression(const __begin_marked_subexpression&);
+    __begin_marked_subexpression& operator=(const __begin_marked_subexpression&);
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __begin_marked_subexpression(__state<_CharT>* __s)
+        : base(__s) {}
+
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__begin_marked_subexpression<_CharT>::__test(const _CharT*, const _CharT* __c, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    return __command(__command::__begin_marked_expr, this->first());
+}
+
+// __end_marked_subexpression
+
+template <class _CharT>
+class __end_marked_subexpression
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    __end_marked_subexpression(const __end_marked_subexpression&);
+    __end_marked_subexpression& operator=(const __end_marked_subexpression&);
+public:
+    typedef __command<_CharT> __command;
+
+    explicit __end_marked_subexpression(__state<_CharT>* __s)
+        : base(__s) {}
+
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__end_marked_subexpression<_CharT>::__test(const _CharT*, const _CharT* __c, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    return __command(__command::__end_marked_expr, this->first());
+}
+
+// __state_arg
+
+template <class _CharT>
+class __state_arg
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    unsigned __arg_;
+
+    __state_arg(const __state_arg&);
+    __state_arg& operator=(const __state_arg&);
+public:
+    typedef __command<_CharT> __command;
+
+    __state_arg(unsigned __a, __state<_CharT>* __s)
+        : base(__s), __arg_(__a) {}
+
+    virtual __command __test(const _CharT*, const _CharT*,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
+};
+
+template <class _CharT>
+__command<_CharT>
+__state_arg<_CharT>::__test(const _CharT*, const _CharT* __c, const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
+{
+    return __command(__arg_, this->first());
+}
+
+// __match_char
+
 template <class _CharT>
 class __match_char
-    : public __transition<_CharT>
+    : public __owns_one_state<_CharT>
 {
-    typedef __transition<_CharT> base;
+    typedef __owns_one_state<_CharT> base;
+
     _CharT __c_;
+
+    __match_char(const __match_char&);
+    __match_char& operator=(const __match_char&);
 public:
-    typedef typename base::__state __state;
+    typedef __command<_CharT> __command;
 
-    __match_char(_CharT __c, bool __owns, __state* __st)
-        : base(__owns, __st), __c_(__c) {}
+    __match_char(_CharT __c, __state<_CharT>* __s)
+        : base(__s), __c_(__c) {}
 
-    virtual __state* __test(_CharT __c, bool& __consume, unsigned&, unsigned&);
+    virtual __command __test(const _CharT*, const _CharT* __c,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const;
 };
 
 template <class _CharT>
-typename __match_char<_CharT>::__state*
-__match_char<_CharT>::__test(_CharT __c, bool& __consume, unsigned&, unsigned&)
+__command<_CharT>
+__match_char<_CharT>::__test(const _CharT*, const _CharT* __c,
+                             const _CharT*,
+                             vector<size_t>&,
+                             sub_match<const _CharT*>*,
+                             regex_constants::match_flag_type) const
 {
-    if (__c == __c_)
-    {
-        __consume = true;
-        return base::__sptr_.get();
-    }
-    __consume = false;
-    return nullptr;
+    return __c_ == *__c ?
+        __command(__command::__accept_and_consume, this->first()) : __command();
 }
- 
-template <class _CharT>
-class __begin_marked_subexpression
-    : public __transition<_CharT>
-{
-    typedef __transition<_CharT> base;
-    unsigned __sub_;
-public:
-    typedef typename base::__state __state;
 
-    __begin_marked_subexpression(unsigned __sub, bool __owns, __state* __st)
-        : base(__owns, __st), __sub_(__sub) {}
-
-    virtual __state* __test(_CharT, bool& __consume, unsigned& __begin_sub,
-                                                     unsigned&);
-};
-
-template <class _CharT>
-typename __begin_marked_subexpression<_CharT>::__state*
-__begin_marked_subexpression<_CharT>::__test(_CharT, bool& __consume,
-                                             unsigned& __begin_sub, unsigned&)
-{
-    __consume = false;
-    __begin_sub = __sub_;
-    return base::__sptr_.get();
-}
- 
-template <class _CharT>
-class __end_marked_subexpression
-    : public __transition<_CharT>
-{
-    typedef __transition<_CharT> base;
-    unsigned __sub_;
-public:
-    typedef typename base::__state __state;
-
-    __end_marked_subexpression(unsigned __sub, bool __owns, __state* __st)
-        : base(__owns, __st), __sub_(__sub) {}
-
-    virtual __state* __test(_CharT, bool& __consume, unsigned&,
-                                                     unsigned& __end_sub);
-};
-
-template <class _CharT>
-typename __end_marked_subexpression<_CharT>::__state*
-__end_marked_subexpression<_CharT>::__test(_CharT, bool& __consume,
-                                           unsigned&, unsigned& __end_sub)
-{
-    __consume = false;
-    __end_sub = __sub_;
-    return base::__sptr_.get();
-}
- 
 template <class, class> class match_results;
 
 template <class _CharT, class _Traits = regex_traits<_CharT> >
@@ -1437,9 +1744,13 @@
     _Traits   __traits_;
     flag_type __flags_;
     unsigned __marked_count_;
+    unsigned __loop_count_;
     int __open_count_;
-    shared_ptr<__state<_CharT> > __start_;
-    __state<_CharT>* __end_;
+    shared_ptr<__empty_state<_CharT> > __start_;
+    __owns_one_state<_CharT>* __end_;
+
+    typedef __command<_CharT> __command;
+    typedef __state<_CharT> __state;
 
 public:
     // constants:
@@ -1455,12 +1766,14 @@
     static const/*expr*/ regex_constants::syntax_option_type egrep = regex_constants::egrep;
 
     // construct/copy/destroy:
-    basic_regex();
+    basic_regex()
+        : __flags_(), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
+        {}
     explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
-        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
         {__parse(__p, __p + __traits_.length(__p));}
     basic_regex(const value_type* __p, size_t __len, flag_type __f)
-        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
         {__parse(__p, __p + __len);}
     basic_regex(const basic_regex&);
 #ifdef _LIBCPP_MOVE
@@ -1469,16 +1782,16 @@
     template <class _ST, class _SA>
         explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
                              flag_type __f = regex_constants::ECMAScript)
-        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
         {__parse(__p.begin(), __p.end());}
     template <class _ForwardIterator>
         basic_regex(_ForwardIterator __first, _ForwardIterator __last,
                     flag_type __f = regex_constants::ECMAScript)
-        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
         {__parse(__first, __last);}
     basic_regex(initializer_list<value_type> __il,
                 flag_type __f = regex_constants::ECMAScript)
-        : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(0)
         {__parse(__il.begin(), __il.end());}
 
     ~basic_regex();
@@ -1520,6 +1833,8 @@
     void swap(basic_regex&);
 
 private:
+    unsigned __loop_count() const {return __loop_count_;}
+
     template <class _ForwardIterator>
         void __parse(_ForwardIterator __first, _ForwardIterator __last);
     template <class _ForwardIterator>
@@ -1560,7 +1875,8 @@
         __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
     template <class _ForwardIterator>
         _ForwardIterator
-        __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
+        __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
+                               __owns_one_state<_CharT>* __s);
     template <class _ForwardIterator>
         _ForwardIterator
         __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
@@ -1607,9 +1923,12 @@
     void __push_l_anchor() {}
     void __push_r_anchor() {}
     void __push_match_any() {}
-    void __push_greedy_inf_repeat(int __min) {}
+    void __push_greedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s)
+        {__push_loop(__min, numeric_limits<size_t>::max(), __s);}
     void __push_exact_repeat(int __count) {}
-    void __push_repeat(int __min, int __max) {}
+    void __push_loop(size_t __min, size_t __max, __owns_one_state<_CharT>* __s,
+                     size_t __mexp_begin = 0, size_t __mexp_end = 0,
+                     bool __greedy = true);
     void __start_nonmatching_list() {}
     void __start_matching_list() {}
     void __end_nonmatching_list() {}
@@ -1629,19 +1948,36 @@
                  match_results<_BidirectionalIterator, _Allocator>& __m,
                  regex_constants::match_flag_type __flags) const;
 
+    template <class _BidirectionalIterator, class _Allocator>
+        bool
+        __match_at_start(_BidirectionalIterator __first, _BidirectionalIterator __last,
+                 match_results<_BidirectionalIterator, _Allocator>& __m,
+                 vector<size_t>& __lc,
+                 regex_constants::match_flag_type __flags) const;
+    template <class _BidirectionalIterator, class _Allocator>
+        bool
+        __match_at_start_ecma(_BidirectionalIterator __first, _BidirectionalIterator __last,
+                 match_results<_BidirectionalIterator, _Allocator>& __m,
+                 regex_constants::match_flag_type __flags) const;
+    template <class _BidirectionalIterator, class _Allocator>
+        bool
+        __match_at_start_posix_nosubs(const _CharT* __first, const _CharT* __last,
+                 match_results<_BidirectionalIterator, _Allocator>& __m,
+                 vector<size_t>& __lc,
+                 regex_constants::match_flag_type __flags) const;
+    template <class _BidirectionalIterator, class _Allocator>
+        bool
+        __match_at_start_posix_subs(_BidirectionalIterator __first, _BidirectionalIterator __last,
+                 match_results<_BidirectionalIterator, _Allocator>& __m,
+                 regex_constants::match_flag_type __flags) const;
+
     template <class _B, class _A, class _C, class _T>
     friend
     bool
     regex_search(_B, _B, match_results<_B, _A>&, const basic_regex<_C, _T>&,
                  regex_constants::match_flag_type);
-};
 
-template <class _CharT, class _Traits>
-inline
-basic_regex<_CharT, _Traits>::basic_regex()
-    : __traits_(), __flags_(), __marked_count_(0)
-{
-}
+};
 
 template <class _CharT, class _Traits>
 basic_regex<_CharT, _Traits>::~basic_regex()
@@ -1654,6 +1990,12 @@
 basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
                                       _ForwardIterator __last)
 {
+    {
+        unique_ptr<__state> __h(new __end_state<_CharT>);
+        __start_.reset(new __empty_state<_CharT>(__h.get()));
+        __h.release();
+        __end_ = __start_.get();
+    }
     switch (__flags_ & 0x3F0)
     {
     case ECMAScript:
@@ -1808,12 +2150,10 @@
 {
     if (__first != __last)
     {
+        __owns_one_state<_CharT>* __e = __end_;
         _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
         if (__temp != __first)
-        {
-            __first = __temp;
-            __first = __parse_RE_dupl_symbol(__first, __last);
-        }
+            __first = __parse_RE_dupl_symbol(__temp, __last, __e);
     }
     return __first;
 }
@@ -2121,13 +2461,14 @@
 template <class _ForwardIterator>
 _ForwardIterator
 basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
-                                                     _ForwardIterator __last)
+                                                     _ForwardIterator __last,
+                                                     __owns_one_state<_CharT>* __s)
 {
     if (__first != __last)
     {
         if (*__first == '*')
         {
-            __push_greedy_inf_repeat(0);
+            __push_greedy_inf_repeat(0, __s);
             ++__first;
         }
         else
@@ -2160,12 +2501,12 @@
                     if (__temp == __first)
                         throw regex_error(regex_constants::error_brace);
                     if (__max == -1)
-                        __push_greedy_inf_repeat(__min);
+                        __push_greedy_inf_repeat(__min, __s);
                     else
                     {
                         if (__max < __min)
                             throw regex_error(regex_constants::error_badbrace);
-                        __push_repeat(__min, __max);
+                        __push_loop(__min, __max, __s);
                     }
                     __first = __temp;
                 }
@@ -2186,15 +2527,15 @@
         switch (*__first)
         {
         case '*':
-            __push_greedy_inf_repeat(0);
+            __push_greedy_inf_repeat(0, nullptr);
             ++__first;
             break;
         case '+':
-            __push_greedy_inf_repeat(1);
+            __push_greedy_inf_repeat(1, nullptr);
             ++__first;
             break;
         case '?':
-            __push_repeat(0, 1);
+            __push_loop(0, 1, nullptr);
             ++__first;
             break;
         case '{':
@@ -2217,7 +2558,7 @@
                         throw regex_error(regex_constants::error_badbrace);
                     if (*__first == '}')
                     {
-                        __push_greedy_inf_repeat(__min);
+                        __push_greedy_inf_repeat(__min, nullptr);
                         ++__first;
                     }
                     else
@@ -2232,7 +2573,7 @@
                         ++__first;
                         if (__max < __min)
                             throw regex_error(regex_constants::error_badbrace);
-                        __push_repeat(__min, __max);
+                        __push_loop(__min, __max, nullptr);
                     }
                 default:
                     throw regex_error(regex_constants::error_badbrace);
@@ -2457,53 +2798,73 @@
 
 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;
+    if (__mexp_begin != __mexp_end)
+    {
+        unique_ptr<__zero_marked_exprs<_CharT> >
+                __e3(new __zero_marked_exprs<_CharT>(__mexp_begin, __mexp_end,
+                                                     __s->first()));
+        __s->first() = nullptr;
+        __e2.reset(new __loop<_CharT>(__loop_count_, __e3.get(), __e1.get(),
+                                      __greedy, __min, __max));
+        __e3.release();
+        __e1.release();
+    }
+    else
+    {
+        __e2.reset(new __loop<_CharT>(__loop_count_, __s->first(), __e1.get(),
+                                      __greedy, __min, __max));
+        __s->first() = nullptr;
+        __e1.release();
+    }
+    __end_->first() = new __increment_loop_count<_CharT>(__loop_count_, __e2.get());
+    __end_ = __e2->second();
+    __s->first() = new __zero_loop_count<_CharT>(__loop_count_, __e2.get());
+    __e2.release();
+    ++__loop_count_;
+}
+
+template <class _CharT, class _Traits>
+void
 basic_regex<_CharT, _Traits>::__push_char(value_type __c)
 {
-    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
-    unique_ptr<__transition<_CharT> > __new_transition(
-        new __match_char<_CharT>(__c, true, __new_end.get()));
-    __state<_CharT>* __e = __new_end.release();
-    if (__end_ == nullptr)
-    {
-        __start_.reset(new __state<_CharT>);
-        __end_ = __start_.get();
-    }
-    __end_->__add_one(__new_transition.release());
-    __end_ = __e;
+    __match_char<_CharT>* __s = new __match_char<_CharT>(__c, __end_->first());
+    __end_->first() = __s;
+    __end_ = __s;
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
 {
-    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
-    unique_ptr<__transition<_CharT> > __new_transition(
-        new __begin_marked_subexpression<_CharT>(++__marked_count_, true, __new_end.get()));
-    __state<_CharT>* __e = __new_end.release();
-    if (__end_ == nullptr)
-    {
-        __start_.reset(new __state<_CharT>);
-        __end_ = __start_.get();
-    }
-    __end_->__add_one(__new_transition.release());
-    __end_ = __e;
+    __begin_marked_subexpression<_CharT>* __s =
+                     new __begin_marked_subexpression<_CharT>(__end_->first());
+    __end_->first() = __s;
+    __end_ = __s;
+    __state_arg<_CharT>* __a = new __state_arg<_CharT>(++__marked_count_,
+                                                               __end_->first());
+    __end_->first() = __a;
+    __end_ = __a;
 }
 
 template <class _CharT, class _Traits>
 void
 basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
 {
-    unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
-    unique_ptr<__transition<_CharT> > __new_transition(
-        new __end_marked_subexpression<_CharT>(__sub, true, __new_end.get()));
-    __state<_CharT>* __e = __new_end.release();
-    if (__end_ == nullptr)
-    {
-        __start_.reset(new __state<_CharT>);
-        __end_ = __start_.get();
-    }
-    __end_->__add_one(__new_transition.release());
-    __end_ = __e;
+    __end_marked_subexpression<_CharT>* __s =
+                        new __end_marked_subexpression<_CharT>(__end_->first());
+    __end_->first() = __s;
+    __end_ = __s;
+    __state_arg<_CharT>* __a = new __state_arg<_CharT>(++__marked_count_,
+                                                               __end_->first());
+    __end_->first() = __a;
+    __end_ = __a;
 }
 
 typedef basic_regex<char>    regex;
@@ -3034,16 +3395,10 @@
 match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
                          _BidirectionalIterator __f, _BidirectionalIterator __l)
 {
-    __matches_.resize(__s);
-    for (unsigned __i = 0; __i < __s; ++__i)
-    {
-        __matches_[__i].first   = __l;
-        __matches_[__i].second  = __l;
-        __matches_[__i].matched = false;
-    }
     __unmatched_.first   = __l;
     __unmatched_.second  = __l;
     __unmatched_.matched = false;
+    __matches_.assign(__s, __unmatched_);
     __prefix_.first      = __f;
     __prefix_.second     = __f;
     __prefix_.matched    = false;
@@ -3077,72 +3432,154 @@
 template <class _CharT, class _Traits>
 template <class _BidirectionalIterator, class _Allocator>
 bool
+basic_regex<_CharT, _Traits>::__match_at_start_ecma(
+        _BidirectionalIterator __first, _BidirectionalIterator __last,
+        match_results<_BidirectionalIterator, _Allocator>& __m,
+        regex_constants::match_flag_type __flags) const
+{
+    return false;
+}
+
+template <class _CharT, class _Traits>
+template <class _BidirectionalIterator, class _Allocator>
+bool
+basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
+        const _CharT* __first, const _CharT* __last,
+        match_results<_BidirectionalIterator, _Allocator>& __m,
+        vector<size_t>& __lc,
+        regex_constants::match_flag_type __flags) const
+{
+/*
+    How do you set __m.__matches[i].first and second?
+    With const _CharT* [__first, __last), we need a reference
+    _BidirectionalIterator to bounce off of.  Something like:
+    __m.__matches_[0].second = next(__m.__matches_[0].first, __current - __first_);
+
+    Pre:  __m.__matches_[0].first <-> __first ? or
+          __m.__prefix_.first <-> first and
+          __m.__suffix_.second <-> last ?
+*/
+    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
+    __split_buffer<__command> __commands;
+    difference_type __j = 0;
+    difference_type __highest_j = 0;
+    difference_type _N = _STD::distance(__first, __last);
+    __state* __st = __start_.get();
+    if (__st)
+    {
+        __commands.push_front(__command(__st));
+        __commands.push_front(__command(__command::__consume_input));
+        _BidirectionalIterator __current = __first;
+        do
+        {
+            __command __cmd = __commands.back();
+            __commands.pop_back();
+            if (__cmd.first != nullptr)
+                __cmd = __cmd.first->__test(__first, __current, __last, __lc,
+                                            __m.__matches_.data(), __flags);
+            switch (__cmd.__do_)
+            {
+            case __command::__end_state:
+                __highest_j = _STD::max(__highest_j, __j);
+                break;
+            case __command::__consume_input:
+                if (__j == _N)
+                    return false;
+                ++__current;
+                if (++__j != _N && !__commands.empty())
+                    __commands.push_front(__command(__command::__consume_input));
+                break;
+            case __command::__accept_and_consume:
+                __commands.push_front(__command(__cmd.first));
+                if (__cmd.second != nullptr)
+                    __commands.push_front(__command(__cmd.second));
+                break;
+            case __command::__accept_but_not_consume:
+                __commands.push_back(__command(__cmd.first));
+                if (__cmd.second != nullptr)
+                    __commands.push_back(__command(__cmd.second));
+                break;
+            case __command::__reject:
+                break;
+            default:
+                throw regex_error(regex_constants::error_temp);
+                break;
+            }
+        } while (!__commands.empty());
+        if (__highest_j != 0)
+        {
+            __m.__matches_[0].first = __first;
+            __m.__matches_[0].second = _STD::next(__first, __highest_j);
+            __m.__matches_[0].matched = true;
+            return true;
+        }
+    }
+    return false;
+}
+
+template <class _CharT, class _Traits>
+template <class _BidirectionalIterator, class _Allocator>
+bool
+basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
+        _BidirectionalIterator __first, _BidirectionalIterator __last,
+        match_results<_BidirectionalIterator, _Allocator>& __m,
+        regex_constants::match_flag_type __flags) const
+{
+    return false;
+}
+
+template <class _CharT, class _Traits>
+template <class _BidirectionalIterator, class _Allocator>
+bool
+basic_regex<_CharT, _Traits>::__match_at_start(
+        _BidirectionalIterator __first, _BidirectionalIterator __last,
+        match_results<_BidirectionalIterator, _Allocator>& __m,
+        vector<size_t>& __lc,
+        regex_constants::match_flag_type __flags) const
+{
+    if (__flags_ & ECMAScript)
+        return __match_at_start_ecma(__first, __last, __m, __flags);
+    if (mark_count() == 0)
+        return __match_at_start_posix_nosubs(__first, __last, __m, __lc, __flags);
+    return __match_at_start_posix_subs(__first, __last, __m, __flags);
+}
+
+template <class _CharT, class _Traits>
+template <class _BidirectionalIterator, class _Allocator>
+bool
 basic_regex<_CharT, _Traits>::__search(
         _BidirectionalIterator __first, _BidirectionalIterator __last,
         match_results<_BidirectionalIterator, _Allocator>& __m,
         regex_constants::match_flag_type __flags) const
 {
-    bool __r = false;
-    if (__start_)
+    __m.__init(1 + mark_count(), __first, __last);
+    vector<size_t> __lc(__loop_count());
+    if (__match_at_start(__first, __last, __m, __lc, __flags))
     {
-        __m.__init(1 + mark_count(), __first, __last);
-        for (; __first != __last; ++__first)
+        __m.__prefix_.second = __m[0].first;
+        __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
+        __m.__suffix_.first = __m[0].second;
+        __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
+        return true;
+    }
+    if (!(__flags & regex_constants::match_continuous))
+    {
+        __m.__matches_.assign(__m.size(), __m.__unmatched_);
+        for (++__first; __first != __last; ++__first)
         {
-            __start_->__reset_state();
-            unsigned __begin_sub = 0;
-            unsigned __end_sub = 0;
-            bool __consume;
-            __state<_CharT>* __st = __start_->__test(*__first, __consume,
-                                                     __begin_sub, __end_sub);
-            if (__st)
+            if (__match_at_start(__first, __last, __m, __lc, __flags))
             {
-                _BidirectionalIterator& __f = __m.__matches_[0].first;
-                _BidirectionalIterator& __l = __m.__matches_[0].second;
-                __f = __l = __first;
-                if (__begin_sub != 0)
-                    __m.__matches_[__begin_sub].first = __l;
-                if (__end_sub != 0)
-                {
-                    __m.__matches_[__end_sub].second = __l;
-                    __m.__matches_[__end_sub].matched = true;
-                }
-                if (__consume)
-                    ++__l;
-                while (__l != __last && __st != __end_)
-                {
-                    __begin_sub = 0;
-                    __end_sub = 0;
-                    __st = __st->__test(*__l, __consume, __begin_sub, __end_sub);
-                    if (__st == nullptr)
-                        break;
-                    if (__begin_sub != 0)
-                        __m.__matches_[__begin_sub].first = __l;
-                    if (__end_sub != 0)
-                    {
-                        __m.__matches_[__end_sub].second = __l;
-                        __m.__matches_[__end_sub].matched = true;
-                    }
-                    if (__consume)
-                        ++__l;
-                }
-                if (__st == __end_)
-                {
-                    __r = __m.__matches_[0].matched = true;
-                    __m.__prefix_.second = __first;
-                    __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
-                    __m.__suffix_.first = __l;
-                    __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
-                    break;
-                }
-                __m.__matches_.assign(__m.__matches_.size(), __m.__unmatched_);
+                __m.__prefix_.second = __m[0].first;
+                __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
+                __m.__suffix_.first = __m[0].second;
+                __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
+                return true;
             }
-            if (__flags & regex_constants::match_continuous)
-                break;
+            __m.__matches_.assign(__m.size(), __m.__unmatched_);
         }
     }
-    if (!__r)
-        __m.__matches_.clear();
-    return __r;
+    __m.__matches_.clear();
+    return false;
 }
 
 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>