Add libc++ and libc++abi to third-party.

third_party/libc++/include/regex

Index: third_party/libc++/include/regex
===================================================================
--- third_party/libc++/include/regex	(revision 0)
+++ third_party/libc++/include/regex	(revision 0)
@@ -0,0 +1,6487 @@
+// -*- C++ -*-
+//===--------------------------- regex ------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_REGEX
+#define _LIBCPP_REGEX
+
+/*
+    regex synopsis
+
+#include <initializer_list>
+
+namespace std
+{
+
+namespace regex_constants
+{
+
+emum syntax_option_type
+{
+    icase      = unspecified,
+    nosubs     = unspecified,
+    optimize   = unspecified,
+    collate    = unspecified,
+    ECMAScript = unspecified,
+    basic      = unspecified,
+    extended   = unspecified,
+    awk        = unspecified,
+    grep       = unspecified,
+    egrep      = unspecified
+};
+
+constexpr syntax_option_type operator~(syntax_option_type f);
+constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
+constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);
+
+enum match_flag_type
+{
+    match_default     = 0,
+    match_not_bol     = unspecified,
+    match_not_eol     = unspecified,
+    match_not_bow     = unspecified,
+    match_not_eow     = unspecified,
+    match_any         = unspecified,
+    match_not_null    = unspecified,
+    match_continuous  = unspecified,
+    match_prev_avail  = unspecified,
+    format_default    = 0,
+    format_sed        = unspecified,
+    format_no_copy    = unspecified,
+    format_first_only = unspecified
+};
+
+constexpr match_flag_type operator~(match_flag_type f);
+constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
+constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);
+
+enum error_type
+{
+    error_collate    = unspecified,
+    error_ctype      = unspecified,
+    error_escape     = unspecified,
+    error_backref    = unspecified,
+    error_brack      = unspecified,
+    error_paren      = unspecified,
+    error_brace      = unspecified,
+    error_badbrace   = unspecified,
+    error_range      = unspecified,
+    error_space      = unspecified,
+    error_badrepeat  = unspecified,
+    error_complexity = unspecified,
+    error_stack      = unspecified
+};
+
+}  // regex_constants
+
+class regex_error
+    : public runtime_error
+{
+public:
+    explicit regex_error(regex_constants::error_type ecode);
+    regex_constants::error_type code() const;
+};
+
+template <class charT>
+struct regex_traits
+{
+public:
+    typedef charT                   char_type;
+    typedef basic_string<char_type> string_type;
+    typedef locale                  locale_type;
+    typedef /bitmask_type/          char_class_type;
+
+    regex_traits();
+
+    static size_t length(const char_type* p);
+    charT translate(charT c) const;
+    charT translate_nocase(charT c) const;
+    template <class ForwardIterator>
+        string_type
+        transform(ForwardIterator first, ForwardIterator last) const;
+    template <class ForwardIterator>
+        string_type
+        transform_primary( ForwardIterator first, ForwardIterator last) const;
+    template <class ForwardIterator>
+        string_type
+        lookup_collatename(ForwardIterator first, ForwardIterator last) const;
+    template <class ForwardIterator>
+        char_class_type
+        lookup_classname(ForwardIterator first, ForwardIterator last,
+                         bool icase = false) const;
+    bool isctype(charT c, char_class_type f) const;
+    int value(charT ch, int radix) const;
+    locale_type imbue(locale_type l);
+    locale_type getloc()const;
+};
+
+template <class charT, class traits = regex_traits<charT>>
+class basic_regex
+{
+public:
+    // types:
+    typedef charT                               value_type;
+    typedef regex_constants::syntax_option_type flag_type;
+    typedef typename traits::locale_type        locale_type;
+
+    // constants:
+    static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;
+    static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
+    static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;
+    static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;
+    static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
+    static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;
+    static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;
+    static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;
+    static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;
+    static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;
+
+    // construct/copy/destroy:
+    basic_regex();
+    explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);
+    basic_regex(const charT* p, size_t len, flag_type f);
+    basic_regex(const basic_regex&);
+    basic_regex(basic_regex&&) noexcept;
+    template <class ST, class SA>
+        explicit basic_regex(const basic_string<charT, ST, SA>& p,
+                             flag_type f = regex_constants::ECMAScript);
+    template <class ForwardIterator>
+        basic_regex(ForwardIterator first, ForwardIterator last,
+                    flag_type f = regex_constants::ECMAScript);
+    basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
+
+    ~basic_regex();
+
+    basic_regex& operator=(const basic_regex&);
+    basic_regex& operator=(basic_regex&&) noexcept;
+    basic_regex& operator=(const charT* ptr);
+    basic_regex& operator=(initializer_list<charT> il);
+    template <class ST, class SA>
+        basic_regex& operator=(const basic_string<charT, ST, SA>& p);
+
+    // assign:
+    basic_regex& assign(const basic_regex& that);
+    basic_regex& assign(basic_regex&& that) noexcept;
+    basic_regex& assign(const charT* ptr, flag_type f = regex_constants::ECMAScript);
+    basic_regex& assign(const charT* p, size_t len, flag_type f);
+    template <class string_traits, class A>
+        basic_regex& assign(const basic_string<charT, string_traits, A>& s,
+                            flag_type f = regex_constants::ECMAScript);
+    template <class InputIterator>
+        basic_regex& assign(InputIterator first, InputIterator last,
+                            flag_type f = regex_constants::ECMAScript);
+    basic_regex& assign(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
+
+    // const operations:
+    unsigned mark_count() const;
+    flag_type flags() const;
+
+    // locale:
+    locale_type imbue(locale_type loc);
+    locale_type getloc() const;
+
+    // swap:
+    void swap(basic_regex&);
+};
+
+typedef basic_regex<char>    regex;
+typedef basic_regex<wchar_t> wregex;
+
+template <class charT, class traits>
+    void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);
+
+template <class BidirectionalIterator>
+class sub_match
+    : public pair<BidirectionalIterator, BidirectionalIterator>
+{
+public:
+    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
+    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
+    typedef BidirectionalIterator                                      iterator;
+    typedef basic_string<value_type>                                string_type;
+
+    bool matched;
+
+    constexpr sub_match();
+
+    difference_type length() const;
+    operator string_type() const;
+    string_type str() const;
+
+    int compare(const sub_match& s) const;
+    int compare(const string_type& s) const;
+    int compare(const value_type* s) const;
+};
+
+typedef sub_match<const char*>             csub_match;
+typedef sub_match<const wchar_t*>          wcsub_match;
+typedef sub_match<string::const_iterator>  ssub_match;
+typedef sub_match<wstring::const_iterator> wssub_match;
+
+template <class BiIter>
+    bool
+    operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+                    const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator==(const sub_match<BiIter>& lhs,
+               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator!=(const sub_match<BiIter>& lhs,
+               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator<(const sub_match<BiIter>& lhs,
+              const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool operator>(const sub_match<BiIter>& lhs,
+                   const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator>=(const sub_match<BiIter>& lhs,
+               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter, class ST, class SA>
+    bool
+    operator<=(const sub_match<BiIter>& lhs,
+               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
+
+template <class BiIter>
+    bool
+    operator==(typename iterator_traits<BiIter>::value_type const* lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<(typename iterator_traits<BiIter>::value_type const* lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>(typename iterator_traits<BiIter>::value_type const* lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator==(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator!=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator<(const sub_match<BiIter>& lhs,
+              typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator>(const sub_match<BiIter>& lhs,
+              typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator>=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator<=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const* rhs);
+
+template <class BiIter>
+    bool
+    operator==(typename iterator_traits<BiIter>::value_type const& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<(typename iterator_traits<BiIter>::value_type const& lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>(typename iterator_traits<BiIter>::value_type const& lhs,
+              const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
+               const sub_match<BiIter>& rhs);
+
+template <class BiIter>
+    bool
+    operator==(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class BiIter>
+    bool
+    operator!=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class BiIter>
+    bool
+    operator<(const sub_match<BiIter>& lhs,
+              typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class BiIter>
+    bool
+    operator>(const sub_match<BiIter>& lhs,
+              typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class BiIter>
+    bool
+    operator>=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class BiIter>
+    bool
+    operator<=(const sub_match<BiIter>& lhs,
+               typename iterator_traits<BiIter>::value_type const& rhs);
+
+template <class charT, class ST, class BiIter>
+    basic_ostream<charT, ST>&
+    operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);
+
+template <class BidirectionalIterator,
+          class Allocator = allocator<sub_match<BidirectionalIterator>>>
+class match_results
+{
+public:
+    typedef sub_match<BidirectionalIterator>                  value_type;
+    typedef const value_type&                                 const_reference;
+    typedef const_reference                                   reference;
+    typedef /implementation-defined/                          const_iterator;
+    typedef const_iterator                                    iterator;
+    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
+    typedef typename allocator_traits<Allocator>::size_type   size_type;
+    typedef Allocator                                         allocator_type;
+    typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;
+    typedef basic_string<char_type>                           string_type;
+
+    // construct/copy/destroy:
+    explicit match_results(const Allocator& a = Allocator());
+    match_results(const match_results& m);
+    match_results(match_results&& m) noexcept;
+    match_results& operator=(const match_results& m);
+    match_results& operator=(match_results&& m);
+    ~match_results();
+
+    bool ready() const;
+
+    // size:
+    size_type size() const;
+    size_type max_size() const;
+    bool empty() const;
+
+    // element access:
+    difference_type length(size_type sub = 0) const;
+    difference_type position(size_type sub = 0) const;
+    string_type str(size_type sub = 0) const;
+    const_reference operator[](size_type n) const;
+
+    const_reference prefix() const;
+    const_reference suffix() const;
+
+    const_iterator begin() const;
+    const_iterator end() const;
+    const_iterator cbegin() const;
+    const_iterator cend() const;
+
+    // format:
+    template <class OutputIter>
+        OutputIter
+        format(OutputIter out, const char_type* fmt_first,
+               const char_type* fmt_last,
+               regex_constants::match_flag_type flags = regex_constants::format_default) const;
+    template <class OutputIter, class ST, class SA>
+        OutputIter
+        format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
+               regex_constants::match_flag_type flags = regex_constants::format_default) const;
+    template <class ST, class SA>
+        basic_string<char_type, ST, SA>
+        format(const basic_string<char_type, ST, SA>& fmt,
+               regex_constants::match_flag_type flags = regex_constants::format_default) const;
+    string_type
+        format(const char_type* fmt,
+               regex_constants::match_flag_type flags = regex_constants::format_default) const;
+
+    // allocator:
+    allocator_type get_allocator() const;
+
+    // swap:
+    void swap(match_results& that);
+};
+
+typedef match_results<const char*>             cmatch;
+typedef match_results<const wchar_t*>          wcmatch;
+typedef match_results<string::const_iterator>  smatch;
+typedef match_results<wstring::const_iterator> wsmatch;
+
+template <class BidirectionalIterator, class Allocator>
+    bool
+    operator==(const match_results<BidirectionalIterator, Allocator>& m1,
+               const match_results<BidirectionalIterator, Allocator>& m2);
+
+template <class BidirectionalIterator, class Allocator>
+    bool
+    operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
+               const match_results<BidirectionalIterator, Allocator>& m2);
+
+template <class BidirectionalIterator, class Allocator>
+    void
+    swap(match_results<BidirectionalIterator, Allocator>& m1,
+         match_results<BidirectionalIterator, Allocator>& m2);
+
+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);
+
+template <class BidirectionalIterator, class charT, class traits>
+    bool
+    regex_match(BidirectionalIterator first, BidirectionalIterator last,
+                const basic_regex<charT, traits>& e,
+                regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class charT, class Allocator, class traits>
+    bool
+    regex_match(const charT* str, match_results<const charT*, Allocator>& m,
+                const basic_regex<charT, traits>& e,
+                regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class ST, class SA, class Allocator, class charT, class traits>
+    bool
+    regex_match(const basic_string<charT, ST, SA>& s,
+                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
+                const basic_regex<charT, traits>& e,
+                regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class charT, class traits>
+    bool
+    regex_match(const charT* str, const basic_regex<charT, traits>& e,
+                regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class ST, class SA, class charT, class traits>
+    bool
+    regex_match(const basic_string<charT, ST, SA>& s,
+                const basic_regex<charT, traits>& e,
+                regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class BidirectionalIterator, class Allocator, class charT, class traits>
+    bool
+    regex_search(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);
+
+template <class BidirectionalIterator, class charT, class traits>
+    bool
+    regex_search(BidirectionalIterator first, BidirectionalIterator last,
+                 const basic_regex<charT, traits>& e,
+                 regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class charT, class Allocator, class traits>
+    bool
+    regex_search(const charT* str, match_results<const charT*, Allocator>& m,
+                 const basic_regex<charT, traits>& e,
+                 regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class charT, class traits>
+    bool
+    regex_search(const charT* str, const basic_regex<charT, traits>& e,
+                 regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class ST, class SA, class charT, class traits>
+    bool
+    regex_search(const basic_string<charT, ST, SA>& s,
+                 const basic_regex<charT, traits>& e,
+                 regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class ST, class SA, class Allocator, class charT, class traits>
+    bool
+    regex_search(const basic_string<charT, ST, SA>& s,
+                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
+                 const basic_regex<charT, traits>& e,
+                 regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class OutputIterator, class BidirectionalIterator,
+          class traits, class charT, class ST, class SA>
+    OutputIterator
+    regex_replace(OutputIterator out,
+                  BidirectionalIterator first, BidirectionalIterator last,
+                  const basic_regex<charT, traits>& e,
+                  const basic_string<charT, ST, SA>& fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class OutputIterator, class BidirectionalIterator,
+          class traits, class charT>
+    OutputIterator
+    regex_replace(OutputIterator out,
+                  BidirectionalIterator first, BidirectionalIterator last,
+                  const basic_regex<charT, traits>& e, const charT* fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class traits, class charT, class ST, class SA, class FST, class FSA>>
+    basic_string<charT, ST, SA>
+    regex_replace(const basic_string<charT, ST, SA>& s,
+                  const basic_regex<charT, traits>& e,
+                  const basic_string<charT, FST, FSA>& fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class traits, class charT, class ST, class SA>
+    basic_string<charT, ST, SA>
+    regex_replace(const basic_string<charT, ST, SA>& s,
+                  const basic_regex<charT, traits>& e, const charT* fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class traits, class charT, class ST, class SA>
+    basic_string<charT>
+    regex_replace(const charT* s,
+                  const basic_regex<charT, traits>& e,
+                  const basic_string<charT, ST, SA>& fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class traits, class charT>
+    basic_string<charT>
+    regex_replace(const charT* s,
+                  const basic_regex<charT, traits>& e,
+                  const charT* fmt,
+                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+template <class BidirectionalIterator,
+          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
+          class traits = regex_traits<charT>>
+class regex_iterator
+{
+public:
+    typedef basic_regex<charT, traits>           regex_type;
+    typedef match_results<BidirectionalIterator> value_type;
+    typedef ptrdiff_t                            difference_type;
+    typedef const value_type*                    pointer;
+    typedef const value_type&                    reference;
+    typedef forward_iterator_tag                 iterator_category;
+
+    regex_iterator();
+    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
+                   const regex_type& re,
+                   regex_constants::match_flag_type m = regex_constants::match_default);
+    regex_iterator(const regex_iterator&);
+    regex_iterator& operator=(const regex_iterator&);
+
+    bool operator==(const regex_iterator&) const;
+    bool operator!=(const regex_iterator&) const;
+
+    const value_type& operator*() const;
+    const value_type* operator->() const;
+
+    regex_iterator& operator++();
+    regex_iterator operator++(int);
+};
+
+typedef regex_iterator<const char*>             cregex_iterator;
+typedef regex_iterator<const wchar_t*>          wcregex_iterator;
+typedef regex_iterator<string::const_iterator>  sregex_iterator;
+typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
+
+template <class BidirectionalIterator,
+          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
+          class traits = regex_traits<charT>>
+class regex_token_iterator
+{
+public:
+    typedef basic_regex<charT, traits>       regex_type;
+    typedef sub_match<BidirectionalIterator> value_type;
+    typedef ptrdiff_t                        difference_type;
+    typedef const value_type*                pointer;
+    typedef const value_type&                reference;
+    typedef forward_iterator_tag             iterator_category;
+
+    regex_token_iterator();
+    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
+                         const regex_type& re, int submatch = 0,
+                         regex_constants::match_flag_type m = regex_constants::match_default);
+    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
+                         const regex_type& re, const vector<int>& submatches,
+                         regex_constants::match_flag_type m = regex_constants::match_default);
+    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
+                         const regex_type& re, initializer_list<int> submatches,
+                         regex_constants::match_flag_type m = regex_constants::match_default);
+    template <size_t N>
+        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
+                             const regex_type& re, const int (&submatches)[N],
+                             regex_constants::match_flag_type m = regex_constants::match_default);
+    regex_token_iterator(const regex_token_iterator&);
+    regex_token_iterator& operator=(const regex_token_iterator&);
+
+    bool operator==(const regex_token_iterator&) const;
+    bool operator!=(const regex_token_iterator&) const;
+
+    const value_type& operator*() const;
+    const value_type* operator->() const;
+
+    regex_token_iterator& operator++();
+    regex_token_iterator operator++(int);
+};
+
+typedef regex_token_iterator<const char*>             cregex_token_iterator;
+typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
+typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
+typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
+
+} // std
+*/
+
+#include <__config>
+#include <stdexcept>
+#include <__locale>
+#include <initializer_list>
+#include <utility>
+#include <iterator>
+#include <string>
+#include <memory>
+#include <vector>
+#include <deque>
+
+#include <__undef_min_max>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace regex_constants
+{
+
+// syntax_option_type
+
+enum syntax_option_type
+{
+    icase      = 1 << 0,
+    nosubs     = 1 << 1,
+    optimize   = 1 << 2,
+    collate    = 1 << 3,
+    ECMAScript = 0,
+    basic      = 1 << 4,
+    extended   = 1 << 5,
+    awk        = 1 << 6,
+    grep       = 1 << 7,
+    egrep      = 1 << 8
+};
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+syntax_option_type
+operator~(syntax_option_type __x)
+{
+    return syntax_option_type(~int(__x) & 0x1FF);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+syntax_option_type
+operator&(syntax_option_type __x, syntax_option_type __y)
+{
+    return syntax_option_type(int(__x) & int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+syntax_option_type
+operator|(syntax_option_type __x, syntax_option_type __y)
+{
+    return syntax_option_type(int(__x) | int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+syntax_option_type
+operator^(syntax_option_type __x, syntax_option_type __y)
+{
+    return syntax_option_type(int(__x) ^ int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+syntax_option_type&
+operator&=(syntax_option_type& __x, syntax_option_type __y)
+{
+    __x = __x & __y;
+    return __x;
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+syntax_option_type&
+operator|=(syntax_option_type& __x, syntax_option_type __y)
+{
+    __x = __x | __y;
+    return __x;
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+syntax_option_type&
+operator^=(syntax_option_type& __x, syntax_option_type __y)
+{
+    __x = __x ^ __y;
+    return __x;
+}
+
+// match_flag_type
+
+enum match_flag_type
+{
+    match_default     = 0,
+    match_not_bol     = 1 << 0,
+    match_not_eol     = 1 << 1,
+    match_not_bow     = 1 << 2,
+    match_not_eow     = 1 << 3,
+    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
+};
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+match_flag_type
+operator~(match_flag_type __x)
+{
+    return match_flag_type(~int(__x) & 0x0FFF);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+match_flag_type
+operator&(match_flag_type __x, match_flag_type __y)
+{
+    return match_flag_type(int(__x) & int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+match_flag_type
+operator|(match_flag_type __x, match_flag_type __y)
+{
+    return match_flag_type(int(__x) | int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR
+match_flag_type
+operator^(match_flag_type __x, match_flag_type __y)
+{
+    return match_flag_type(int(__x) ^ int(__y));
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+match_flag_type&
+operator&=(match_flag_type& __x, match_flag_type __y)
+{
+    __x = __x & __y;
+    return __x;
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+match_flag_type&
+operator|=(match_flag_type& __x, match_flag_type __y)
+{
+    __x = __x | __y;
+    return __x;
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+match_flag_type&
+operator^=(match_flag_type& __x, match_flag_type __y)
+{
+    __x = __x ^ __y;
+    return __x;
+}
+
+enum error_type
+{
+    error_collate = 1,
+    error_ctype,
+    error_escape,
+    error_backref,
+    error_brack,
+    error_paren,
+    error_brace,
+    error_badbrace,
+    error_range,
+    error_space,
+    error_badrepeat,
+    error_complexity,
+    error_stack,
+    __re_err_grammar,
+    __re_err_empty,
+    __re_err_unknown
+};
+
+}  // regex_constants
+
+class _LIBCPP_EXCEPTION_ABI regex_error
+    : public runtime_error
+{
+    regex_constants::error_type __code_;
+public:
+    explicit regex_error(regex_constants::error_type __ecode);
+    virtual ~regex_error() throw();
+     _LIBCPP_INLINE_VISIBILITY
+    regex_constants::error_type code() const {return __code_;}
+};
+
+template <class _CharT>
+struct _LIBCPP_TYPE_VIS_ONLY regex_traits
+{
+public:
+    typedef _CharT                  char_type;
+    typedef basic_string<char_type> string_type;
+    typedef locale                  locale_type;
+    typedef ctype_base::mask        char_class_type;
+
+    static const char_class_type __regex_word = 0x80;
+private:
+    locale __loc_;
+    const ctype<char_type>* __ct_;
+    const collate<char_type>* __col_;
+
+public:
+    regex_traits();
+
+    _LIBCPP_INLINE_VISIBILITY
+    static size_t length(const char_type* __p)
+        {return char_traits<char_type>::length(__p);}
+    _LIBCPP_INLINE_VISIBILITY
+    char_type translate(char_type __c) const {return __c;}
+    char_type translate_nocase(char_type __c) const;
+    template <class _ForwardIterator>
+        string_type
+        transform(_ForwardIterator __f, _ForwardIterator __l) const;
+    template <class _ForwardIterator>
+        _LIBCPP_INLINE_VISIBILITY
+        string_type
+        transform_primary( _ForwardIterator __f, _ForwardIterator __l) const
+            {return __transform_primary(__f, __l, char_type());}
+    template <class _ForwardIterator>
+        _LIBCPP_INLINE_VISIBILITY
+        string_type
+        lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const
+            {return __lookup_collatename(__f, __l, char_type());}
+    template <class _ForwardIterator>
+        _LIBCPP_INLINE_VISIBILITY
+        char_class_type
+        lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
+                         bool __icase = false) const
+            {return __lookup_classname(__f, __l, __icase, char_type());}
+    bool isctype(char_type __c, char_class_type __m) const;
+    _LIBCPP_INLINE_VISIBILITY
+    int value(char_type __ch, int __radix) const
+        {return __regex_traits_value(__ch, __radix);}
+    locale_type imbue(locale_type __l);
+    _LIBCPP_INLINE_VISIBILITY
+    locale_type getloc()const {return __loc_;}
+
+private:
+    void __init();
+
+    template <class _ForwardIterator>
+        string_type
+        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
+    template <class _ForwardIterator>
+        string_type
+        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
+
+    template <class _ForwardIterator>
+        string_type
+        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
+    template <class _ForwardIterator>
+        string_type
+        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
+
+    template <class _ForwardIterator>
+        char_class_type
+        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
+                           bool __icase, char) const;
+    template <class _ForwardIterator>
+        char_class_type
+        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
+                           bool __icase, wchar_t) const;
+
+    static int __regex_traits_value(unsigned char __ch, int __radix);
+    _LIBCPP_INLINE_VISIBILITY
+    int __regex_traits_value(char __ch, int __radix) const
+        {return __regex_traits_value(static_cast<unsigned char>(__ch), __radix);}
+    int __regex_traits_value(wchar_t __ch, int __radix) const;
+};
+
+template <class _CharT>
+const typename regex_traits<_CharT>::char_class_type
+regex_traits<_CharT>::__regex_word;
+
+template <class _CharT>
+regex_traits<_CharT>::regex_traits()
+{
+    __init();
+}
+
+template <class _CharT>
+typename regex_traits<_CharT>::char_type
+regex_traits<_CharT>::translate_nocase(char_type __c) const
+{
+    return __ct_->tolower(__c);
+}
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::string_type
+regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const
+{
+    string_type __s(__f, __l);
+    return __col_->transform(__s.data(), __s.data() + __s.size());
+}
+
+template <class _CharT>
+void
+regex_traits<_CharT>::__init()
+{
+    __ct_ = &use_facet<ctype<char_type> >(__loc_);
+    __col_ = &use_facet<collate<char_type> >(__loc_);
+}
+
+template <class _CharT>
+typename regex_traits<_CharT>::locale_type
+regex_traits<_CharT>::imbue(locale_type __l)
+{
+    locale __r = __loc_;
+    __loc_ = __l;
+    __init();
+    return __r;
+}
+
+// transform_primary is very FreeBSD-specific
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::string_type
+regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
+                                          _ForwardIterator __l, char) const
+{
+    const string_type __s(__f, __l);
+    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
+    switch (__d.size())
+    {
+    case 1:
+        break;
+    case 12:
+        __d[11] = __d[3];
+        break;
+    default:
+        __d.clear();
+        break;
+    }
+    return __d;
+}
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::string_type
+regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
+                                          _ForwardIterator __l, wchar_t) const
+{
+    const string_type __s(__f, __l);
+    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
+    switch (__d.size())
+    {
+    case 1:
+        break;
+    case 3:
+        __d[2] = __d[0];
+        break;
+    default:
+        __d.clear();
+        break;
+    }
+    return __d;
+}
+
+// lookup_collatename is very FreeBSD-specific
+
+_LIBCPP_FUNC_VIS string __get_collation_name(const char* __s);
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::string_type
+regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
+                                           _ForwardIterator __l, char) const
+{
+    string_type __s(__f, __l);
+    string_type __r;
+    if (!__s.empty())
+    {
+        __r = __get_collation_name(__s.c_str());
+        if (__r.empty() && __s.size() <= 2)
+        {
+            __r = __col_->transform(__s.data(), __s.data() + __s.size());
+            if (__r.size() == 1 || __r.size() == 12)
+                __r = __s;
+            else
+                __r.clear();
+        }
+    }
+    return __r;
+}
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::string_type
+regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
+                                           _ForwardIterator __l, wchar_t) const
+{
+    string_type __s(__f, __l);
+    string __n;
+    __n.reserve(__s.size());
+    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
+                                                              __i != __e; ++__i)
+    {
+        if (static_cast<unsigned>(*__i) >= 127)
+            return string_type();
+        __n.push_back(char(*__i));
+    }
+    string_type __r;
+    if (!__s.empty())
+    {
+        __n = __get_collation_name(__n.c_str());
+        if (!__n.empty())
+            __r.assign(__n.begin(), __n.end());
+        else if (__s.size() <= 2)
+        {
+            __r = __col_->transform(__s.data(), __s.data() + __s.size());
+            if (__r.size() == 1 || __r.size() == 3)
+                __r = __s;
+            else
+                __r.clear();
+        }
+    }
+    return __r;
+}
+
+// lookup_classname
+
+ctype_base::mask _LIBCPP_FUNC_VIS __get_classname(const char* __s, bool __icase);
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::char_class_type
+regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
+                                         _ForwardIterator __l,
+                                         bool __icase, char) const
+{
+    string_type __s(__f, __l);
+    __ct_->tolower(&__s[0], &__s[0] + __s.size());
+    return __get_classname(__s.c_str(), __icase);
+}
+
+template <class _CharT>
+template <class _ForwardIterator>
+typename regex_traits<_CharT>::char_class_type
+regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
+                                         _ForwardIterator __l,
+                                         bool __icase, wchar_t) const
+{
+    string_type __s(__f, __l);
+    __ct_->tolower(&__s[0], &__s[0] + __s.size());
+    string __n;
+    __n.reserve(__s.size());
+    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
+                                                              __i != __e; ++__i)
+    {
+        if (static_cast<unsigned>(*__i) >= 127)
+            return char_class_type();
+        __n.push_back(char(*__i));
+    }
+    return __get_classname(__n.c_str(), __icase);
+}
+
+template <class _CharT>
+bool
+regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const
+{
+    if (__ct_->is(__m, __c))
+        return true;
+    return (__c == '_' && (__m & __regex_word));
+}
+
+template <class _CharT>
+int
+regex_traits<_CharT>::__regex_traits_value(unsigned char __ch, int __radix)
+{
+    if ((__ch & 0xF8u) == 0x30)  // '0' <= __ch && __ch <= '7'
+        return __ch - '0';
+    if (__radix != 8)
+    {
+        if ((__ch & 0xFEu) == 0x38)  // '8' <= __ch && __ch <= '9'
+            return __ch - '0';
+        if (__radix == 16)
+        {
+            __ch |= 0x20;  // tolower
+            if ('a' <= __ch && __ch <= 'f')
+                return __ch - ('a' - 10);
+        }
+    }
+    return -1;
+}
+
+template <class _CharT>
+inline _LIBCPP_INLINE_VISIBILITY
+int
+regex_traits<_CharT>::__regex_traits_value(wchar_t __ch, int __radix) const
+{
+    return __regex_traits_value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
+}
+
+template <class _CharT> class __node;
+
+template <class _BidirectionalIterator> class _LIBCPP_TYPE_VIS_ONLY sub_match;
+
+template <class _BidirectionalIterator,
+          class _Allocator = allocator<sub_match<_BidirectionalIterator> > >
+class _LIBCPP_TYPE_VIS_ONLY match_results;
+
+template <class _CharT>
+struct __state
+{
+    enum
+    {
+        __end_state = -1000,
+        __consume_input,  // -999
+        __begin_marked_expr, // -998
+        __end_marked_expr,   // -997
+        __pop_state,           // -996
+        __accept_and_consume,  // -995
+        __accept_but_not_consume,  // -994
+        __reject,                  // -993
+        __split,
+        __repeat
+    };
+
+    int __do_;
+    const _CharT* __first_;
+    const _CharT* __current_;
+    const _CharT* __last_;
+    vector<sub_match<const _CharT*> > __sub_matches_;
+    vector<pair<size_t, const _CharT*> > __loop_data_;
+    const __node<_CharT>* __node_;
+    regex_constants::match_flag_type __flags_;
+    bool __at_first_;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __state()
+        : __do_(0), __first_(nullptr), __current_(nullptr), __last_(nullptr),
+          __node_(nullptr), __flags_() {}
+};
+
+// __node
+
+template <class _CharT>
+class __node
+{
+    __node(const __node&);
+    __node& operator=(const __node&);
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node() {}
+    _LIBCPP_INLINE_VISIBILITY
+    virtual ~__node() {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    virtual void __exec(__state&) const {};
+    _LIBCPP_INLINE_VISIBILITY
+    virtual void __exec_split(bool, __state&) const {};
+};
+
+// __end_state
+
+template <class _CharT>
+class __end_state
+    : public __node<_CharT>
+{
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __end_state() {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__end_state<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__end_state;
+}
+
+// __has_one_state
+
+template <class _CharT>
+class __has_one_state
+    : public __node<_CharT>
+{
+    __node<_CharT>* __first_;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __has_one_state(__node<_CharT>* __s)
+        : __first_(__s) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node<_CharT>*  first() const {return __first_;}
+    _LIBCPP_INLINE_VISIBILITY
+    __node<_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:
+    _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;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __empty_state(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__empty_state<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    __s.__node_ = 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 _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __empty_non_own_state(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__empty_non_own_state<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    __s.__node_ = this->first();
+}
+
+// __repeat_one_loop
+
+template <class _CharT>
+class __repeat_one_loop
+    : public __has_one_state<_CharT>
+{
+    typedef __has_one_state<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __repeat_one_loop(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__repeat_one_loop<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__repeat;
+    __s.__node_ = 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:
+    _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;
+
+    size_t __min_;
+    size_t __max_;
+    unsigned __loop_id_;
+    unsigned __mexp_begin_;
+    unsigned __mexp_end_;
+    bool __greedy_;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __loop(unsigned __loop_id,
+                          __node<_CharT>* __s1, __owns_one_state<_CharT>* __s2,
+                          unsigned __mexp_begin, unsigned __mexp_end,
+                          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),
+          __mexp_begin_(__mexp_begin), __mexp_end_(__mexp_end),
+          __greedy_(__greedy) {}
+
+    virtual void __exec(__state& __s) const;
+    virtual void __exec_split(bool __second, __state& __s) const;
+
+private:
+    _LIBCPP_INLINE_VISIBILITY
+    void __init_repeat(__state& __s) const
+    {
+        __s.__loop_data_[__loop_id_].second = __s.__current_;
+        for (size_t __i = __mexp_begin_-1; __i != __mexp_end_-1; ++__i)
+        {
+            __s.__sub_matches_[__i].first = __s.__last_;
+            __s.__sub_matches_[__i].second = __s.__last_;
+            __s.__sub_matches_[__i].matched = false;
+        }
+    }
+};
+
+template <class _CharT>
+void
+__loop<_CharT>::__exec(__state& __s) const
+{
+    if (__s.__do_ == __state::__repeat)
+    {
+        bool __do_repeat = ++__s.__loop_data_[__loop_id_].first < __max_;
+        bool __do_alt = __s.__loop_data_[__loop_id_].first >= __min_;
+        if (__do_repeat && __do_alt &&
+                               __s.__loop_data_[__loop_id_].second == __s.__current_)
+            __do_repeat = false;
+        if (__do_repeat && __do_alt)
+            __s.__do_ = __state::__split;
+        else if (__do_repeat)
+        {
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__node_ = this->first();
+            __init_repeat(__s);
+        }
+        else
+        {
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__node_ = this->second();
+        }
+    }
+    else
+    {
+        __s.__loop_data_[__loop_id_].first = 0;
+        bool __do_repeat = 0 < __max_;
+        bool __do_alt = 0 >= __min_;
+        if (__do_repeat && __do_alt)
+            __s.__do_ = __state::__split;
+        else if (__do_repeat)
+        {
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__node_ = this->first();
+            __init_repeat(__s);
+        }
+        else
+        {
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__node_ = this->second();
+        }
+    }
+}
+
+template <class _CharT>
+void
+__loop<_CharT>::__exec_split(bool __second, __state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    if (__greedy_ != __second)
+    {
+        __s.__node_ = this->first();
+        __init_repeat(__s);
+    }
+    else
+        __s.__node_ = this->second();
+}
+
+// __alternate
+
+template <class _CharT>
+class __alternate
+    : public __owns_two_states<_CharT>
+{
+    typedef __owns_two_states<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __alternate(__owns_one_state<_CharT>* __s1,
+                         __owns_one_state<_CharT>* __s2)
+        : base(__s1, __s2) {}
+
+    virtual void __exec(__state& __s) const;
+    virtual void __exec_split(bool __second, __state& __s) const;
+};
+
+template <class _CharT>
+void
+__alternate<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__split;
+}
+
+template <class _CharT>
+void
+__alternate<_CharT>::__exec_split(bool __second, __state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    if (__second)
+        __s.__node_ = this->second();
+    else
+        __s.__node_ = this->first();
+}
+
+// __begin_marked_subexpression
+
+template <class _CharT>
+class __begin_marked_subexpression
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    unsigned __mexp_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __begin_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
+        : base(__s), __mexp_(__mexp) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__begin_marked_subexpression<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    __s.__sub_matches_[__mexp_-1].first = __s.__current_;
+    __s.__node_ = this->first();
+}
+
+// __end_marked_subexpression
+
+template <class _CharT>
+class __end_marked_subexpression
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    unsigned __mexp_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __end_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
+        : base(__s), __mexp_(__mexp) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__end_marked_subexpression<_CharT>::__exec(__state& __s) const
+{
+    __s.__do_ = __state::__accept_but_not_consume;
+    __s.__sub_matches_[__mexp_-1].second = __s.__current_;
+    __s.__sub_matches_[__mexp_-1].matched = true;
+    __s.__node_ = this->first();
+}
+
+// __back_ref
+
+template <class _CharT>
+class __back_ref
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    unsigned __mexp_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __back_ref(unsigned __mexp, __node<_CharT>* __s)
+        : base(__s), __mexp_(__mexp) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__back_ref<_CharT>::__exec(__state& __s) const
+{
+    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
+    if (__sm.matched)
+    {
+        ptrdiff_t __len = __sm.second - __sm.first;
+        if (__s.__last_ - __s.__current_ >= __len &&
+            _VSTD::equal(__sm.first, __sm.second, __s.__current_))
+        {
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__current_ += __len;
+            __s.__node_ = this->first();
+        }
+        else
+        {
+            __s.__do_ = __state::__reject;
+            __s.__node_ = nullptr;
+        }
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __back_ref_icase
+
+template <class _CharT, class _Traits>
+class __back_ref_icase
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _Traits __traits_;
+    unsigned __mexp_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __back_ref_icase(const _Traits& __traits, unsigned __mexp,
+                              __node<_CharT>* __s)
+        : base(__s), __traits_(__traits), __mexp_(__mexp) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT, class _Traits>
+void
+__back_ref_icase<_CharT, _Traits>::__exec(__state& __s) const
+{
+    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
+    if (__sm.matched)
+    {
+        ptrdiff_t __len = __sm.second - __sm.first;
+        if (__s.__last_ - __s.__current_ >= __len)
+        {
+            for (ptrdiff_t __i = 0; __i < __len; ++__i)
+            {
+                if (__traits_.translate_nocase(__sm.first[__i]) !=
+                                __traits_.translate_nocase(__s.__current_[__i]))
+                    goto __not_equal;
+            }
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__current_ += __len;
+            __s.__node_ = this->first();
+        }
+        else
+        {
+            __s.__do_ = __state::__reject;
+            __s.__node_ = nullptr;
+        }
+    }
+    else
+    {
+__not_equal:
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __back_ref_collate
+
+template <class _CharT, class _Traits>
+class __back_ref_collate
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _Traits __traits_;
+    unsigned __mexp_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __back_ref_collate(const _Traits& __traits, unsigned __mexp,
+                              __node<_CharT>* __s)
+        : base(__s), __traits_(__traits), __mexp_(__mexp) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT, class _Traits>
+void
+__back_ref_collate<_CharT, _Traits>::__exec(__state& __s) const
+{
+    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
+    if (__sm.matched)
+    {
+        ptrdiff_t __len = __sm.second - __sm.first;
+        if (__s.__last_ - __s.__current_ >= __len)
+        {
+            for (ptrdiff_t __i = 0; __i < __len; ++__i)
+            {
+                if (__traits_.translate(__sm.first[__i]) !=
+                                       __traits_.translate(__s.__current_[__i]))
+                    goto __not_equal;
+            }
+            __s.__do_ = __state::__accept_but_not_consume;
+            __s.__current_ += __len;
+            __s.__node_ = this->first();
+        }
+        else
+        {
+            __s.__do_ = __state::__reject;
+            __s.__node_ = nullptr;
+        }
+    }
+    else
+    {
+__not_equal:
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __word_boundary
+
+template <class _CharT, class _Traits>
+class __word_boundary
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _Traits __traits_;
+    bool __invert_;
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __word_boundary(const _Traits& __traits, bool __invert,
+                             __node<_CharT>* __s)
+        : base(__s), __traits_(__traits), __invert_(__invert) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT, class _Traits>
+void
+__word_boundary<_CharT, _Traits>::__exec(__state& __s) const
+{
+    bool __is_word_b = false;
+    if (__s.__first_ != __s.__last_)
+    {
+        if (__s.__current_ == __s.__last_)
+        {
+            if (!(__s.__flags_ & regex_constants::match_not_eow))
+            {
+                _CharT __c = __s.__current_[-1];
+                __is_word_b = __c == '_' ||
+                              __traits_.isctype(__c, ctype_base::alnum);
+            }
+        }
+        else if (__s.__current_ == __s.__first_ &&
+                !(__s.__flags_ & regex_constants::match_prev_avail))
+        {
+            if (!(__s.__flags_ & regex_constants::match_not_bow))
+            {
+                _CharT __c = *__s.__current_;
+                __is_word_b = __c == '_' ||
+                              __traits_.isctype(__c, ctype_base::alnum);
+            }
+        }
+        else
+        {
+            _CharT __c1 = __s.__current_[-1];
+            _CharT __c2 = *__s.__current_;
+            bool __is_c1_b = __c1 == '_' ||
+                             __traits_.isctype(__c1, ctype_base::alnum);
+            bool __is_c2_b = __c2 == '_' ||
+                             __traits_.isctype(__c2, ctype_base::alnum);
+            __is_word_b = __is_c1_b != __is_c2_b;
+        }
+    }
+    if (__is_word_b != __invert_)
+    {
+        __s.__do_ = __state::__accept_but_not_consume;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __l_anchor
+
+template <class _CharT>
+class __l_anchor
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __l_anchor(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__l_anchor<_CharT>::__exec(__state& __s) const
+{
+    if (__s.__at_first_ && __s.__current_ == __s.__first_)
+    {
+        __s.__do_ = __state::__accept_but_not_consume;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __r_anchor
+
+template <class _CharT>
+class __r_anchor
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __r_anchor(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__r_anchor<_CharT>::__exec(__state& __s) const
+{
+    if (__s.__current_ == __s.__last_)
+    {
+        __s.__do_ = __state::__accept_but_not_consume;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __match_any
+
+template <class _CharT>
+class __match_any
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __match_any(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__match_any<_CharT>::__exec(__state& __s) const
+{
+    if (__s.__current_ != __s.__last_ && *__s.__current_ != 0)
+    {
+        __s.__do_ = __state::__accept_and_consume;
+        ++__s.__current_;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __match_any_but_newline
+
+template <class _CharT>
+class __match_any_but_newline
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __match_any_but_newline(__node<_CharT>* __s)
+        : base(__s) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <> _LIBCPP_FUNC_VIS void __match_any_but_newline<char>::__exec(__state&) const;
+template <> _LIBCPP_FUNC_VIS void __match_any_but_newline<wchar_t>::__exec(__state&) const;
+
+// __match_char
+
+template <class _CharT>
+class __match_char
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _CharT __c_;
+
+    __match_char(const __match_char&);
+    __match_char& operator=(const __match_char&);
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __match_char(_CharT __c, __node<_CharT>* __s)
+        : base(__s), __c_(__c) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT>
+void
+__match_char<_CharT>::__exec(__state& __s) const
+{
+    if (__s.__current_ != __s.__last_ && *__s.__current_ == __c_)
+    {
+        __s.__do_ = __state::__accept_and_consume;
+        ++__s.__current_;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __match_char_icase
+
+template <class _CharT, class _Traits>
+class __match_char_icase
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _Traits __traits_;
+    _CharT __c_;
+
+    __match_char_icase(const __match_char_icase&);
+    __match_char_icase& operator=(const __match_char_icase&);
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __match_char_icase(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
+        : base(__s), __traits_(__traits), __c_(__traits.translate_nocase(__c)) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT, class _Traits>
+void
+__match_char_icase<_CharT, _Traits>::__exec(__state& __s) const
+{
+    if (__s.__current_ != __s.__last_ &&
+        __traits_.translate_nocase(*__s.__current_) == __c_)
+    {
+        __s.__do_ = __state::__accept_and_consume;
+        ++__s.__current_;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __match_char_collate
+
+template <class _CharT, class _Traits>
+class __match_char_collate
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+
+    _Traits __traits_;
+    _CharT __c_;
+
+    __match_char_collate(const __match_char_collate&);
+    __match_char_collate& operator=(const __match_char_collate&);
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __match_char_collate(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
+        : base(__s), __traits_(__traits), __c_(__traits.translate(__c)) {}
+
+    virtual void __exec(__state&) const;
+};
+
+template <class _CharT, class _Traits>
+void
+__match_char_collate<_CharT, _Traits>::__exec(__state& __s) const
+{
+    if (__s.__current_ != __s.__last_ &&
+        __traits_.translate(*__s.__current_) == __c_)
+    {
+        __s.__do_ = __state::__accept_and_consume;
+        ++__s.__current_;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+// __bracket_expression
+
+template <class _CharT, class _Traits>
+class __bracket_expression
+    : public __owns_one_state<_CharT>
+{
+    typedef __owns_one_state<_CharT> base;
+    typedef typename _Traits::string_type string_type;
+
+    _Traits __traits_;
+    vector<_CharT> __chars_;
+    vector<_CharT> __neg_chars_;
+    vector<pair<string_type, string_type> > __ranges_;
+    vector<pair<_CharT, _CharT> > __digraphs_;
+    vector<string_type> __equivalences_;
+    ctype_base::mask __mask_;
+    ctype_base::mask __neg_mask_;
+    bool __negate_;
+    bool __icase_;
+    bool __collate_;
+    bool __might_have_digraph_;
+
+    __bracket_expression(const __bracket_expression&);
+    __bracket_expression& operator=(const __bracket_expression&);
+public:
+    typedef _VSTD::__state<_CharT> __state;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __bracket_expression(const _Traits& __traits, __node<_CharT>* __s,
+                                 bool __negate, bool __icase, bool __collate)
+        : base(__s), __traits_(__traits), __mask_(), __neg_mask_(),
+          __negate_(__negate), __icase_(__icase), __collate_(__collate),
+          __might_have_digraph_(__traits_.getloc().name() != "C") {}
+
+    virtual void __exec(__state&) const;
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __negated() const {return __negate_;}
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_char(_CharT __c)
+        {
+            if (__icase_)
+                __chars_.push_back(__traits_.translate_nocase(__c));
+            else if (__collate_)
+                __chars_.push_back(__traits_.translate(__c));
+            else
+                __chars_.push_back(__c);
+        }
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_neg_char(_CharT __c)
+        {
+            if (__icase_)
+                __neg_chars_.push_back(__traits_.translate_nocase(__c));
+            else if (__collate_)
+                __neg_chars_.push_back(__traits_.translate(__c));
+            else
+                __neg_chars_.push_back(__c);
+        }
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_range(string_type __b, string_type __e)
+        {
+            if (__collate_)
+            {
+                if (__icase_)
+                {
+                    for (size_t __i = 0; __i < __b.size(); ++__i)
+                        __b[__i] = __traits_.translate_nocase(__b[__i]);
+                    for (size_t __i = 0; __i < __e.size(); ++__i)
+                        __e[__i] = __traits_.translate_nocase(__e[__i]);
+                }
+                else
+                {
+                    for (size_t __i = 0; __i < __b.size(); ++__i)
+                        __b[__i] = __traits_.translate(__b[__i]);
+                    for (size_t __i = 0; __i < __e.size(); ++__i)
+                        __e[__i] = __traits_.translate(__e[__i]);
+                }
+                __ranges_.push_back(make_pair(
+                                  __traits_.transform(__b.begin(), __b.end()),
+                                  __traits_.transform(__e.begin(), __e.end())));
+            }
+            else
+            {
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__b.size() != 1 || __e.size() != 1)
+                    throw regex_error(regex_constants::error_collate);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                if (__icase_)
+                {
+                    __b[0] = __traits_.translate_nocase(__b[0]);
+                    __e[0] = __traits_.translate_nocase(__e[0]);
+                }
+                __ranges_.push_back(make_pair(_VSTD::move(__b), _VSTD::move(__e)));
+            }
+        }
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_digraph(_CharT __c1, _CharT __c2)
+        {
+            if (__icase_)
+                __digraphs_.push_back(make_pair(__traits_.translate_nocase(__c1),
+                                                __traits_.translate_nocase(__c2)));
+            else if (__collate_)
+                __digraphs_.push_back(make_pair(__traits_.translate(__c1),
+                                                __traits_.translate(__c2)));
+            else
+                __digraphs_.push_back(make_pair(__c1, __c2));
+        }
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_equivalence(const string_type& __s)
+        {__equivalences_.push_back(__s);}
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_class(ctype_base::mask __mask)
+        {__mask_ |= __mask;}
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_neg_class(ctype_base::mask __mask)
+        {__neg_mask_ |= __mask;}
+};
+
+template <class _CharT, class _Traits>
+void
+__bracket_expression<_CharT, _Traits>::__exec(__state& __s) const
+{
+    bool __found = false;
+    unsigned __consumed = 0;
+    if (__s.__current_ != __s.__last_)
+    {
+        ++__consumed;
+        if (__might_have_digraph_)
+        {
+            const _CharT* __next = _VSTD::next(__s.__current_);
+            if (__next != __s.__last_)
+            {
+                pair<_CharT, _CharT> __ch2(*__s.__current_, *__next);
+                if (__icase_)
+                {
+                    __ch2.first = __traits_.translate_nocase(__ch2.first);
+                    __ch2.second = __traits_.translate_nocase(__ch2.second);
+                }
+                else if (__collate_)
+                {
+                    __ch2.first = __traits_.translate(__ch2.first);
+                    __ch2.second = __traits_.translate(__ch2.second);
+                }
+                if (!__traits_.lookup_collatename(&__ch2.first, &__ch2.first+2).empty())
+                {
+                    // __ch2 is a digraph in this locale
+                    ++__consumed;
+                    for (size_t __i = 0; __i < __digraphs_.size(); ++__i)
+                    {
+                        if (__ch2 == __digraphs_[__i])
+                        {
+                            __found = true;
+                            goto __exit;
+                        }
+                    }
+                    if (__collate_ && !__ranges_.empty())
+                    {
+                        string_type __s2 = __traits_.transform(&__ch2.first,
+                                                               &__ch2.first + 2);
+                        for (size_t __i = 0; __i < __ranges_.size(); ++__i)
+                        {
+                            if (__ranges_[__i].first <= __s2 &&
+                                __s2 <= __ranges_[__i].second)
+                            {
+                                __found = true;
+                                goto __exit;
+                            }
+                        }
+                    }
+                    if (!__equivalences_.empty())
+                    {
+                        string_type __s2 = __traits_.transform_primary(&__ch2.first,
+                                                                       &__ch2.first + 2);
+                        for (size_t __i = 0; __i < __equivalences_.size(); ++__i)
+                        {
+                            if (__s2 == __equivalences_[__i])
+                            {
+                                __found = true;
+                                goto __exit;
+                            }
+                        }
+                    }
+                    if (__traits_.isctype(__ch2.first, __mask_) &&
+                        __traits_.isctype(__ch2.second, __mask_))
+                    {
+                        __found = true;
+                        goto __exit;
+                    }
+                    if (!__traits_.isctype(__ch2.first, __neg_mask_) &&
+                        !__traits_.isctype(__ch2.second, __neg_mask_))
+                    {
+                        __found = true;
+                        goto __exit;
+                    }
+                    goto __exit;
+                }
+            }
+        }
+        // test *__s.__current_ as not a digraph
+        _CharT __ch = *__s.__current_;
+        if (__icase_)
+            __ch = __traits_.translate_nocase(__ch);
+        else if (__collate_)
+            __ch = __traits_.translate(__ch);
+        for (size_t __i = 0; __i < __chars_.size(); ++__i)
+        {
+            if (__ch == __chars_[__i])
+            {
+                __found = true;
+                goto __exit;
+            }
+        }
+        if (!__neg_chars_.empty())
+        {
+            for (size_t __i = 0; __i < __neg_chars_.size(); ++__i)
+            {
+                if (__ch == __neg_chars_[__i])
+                    goto __is_neg_char;
+            }
+            __found = true;
+            goto __exit;
+        }
+__is_neg_char:
+        if (!__ranges_.empty())
+        {
+            string_type __s2 = __collate_ ?
+                                   __traits_.transform(&__ch, &__ch + 1) :
+                                   string_type(1, __ch);
+            for (size_t __i = 0; __i < __ranges_.size(); ++__i)
+            {
+                if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second)
+                {
+                    __found = true;
+                    goto __exit;
+                }
+            }
+        }
+        if (!__equivalences_.empty())
+        {
+            string_type __s2 = __traits_.transform_primary(&__ch, &__ch + 1);
+            for (size_t __i = 0; __i < __equivalences_.size(); ++__i)
+            {
+                if (__s2 == __equivalences_[__i])
+                {
+                    __found = true;
+                    goto __exit;
+                }
+            }
+        }
+        if (__traits_.isctype(__ch, __mask_))
+        {
+            __found = true;
+            goto __exit;
+        }
+        if (__neg_mask_ && !__traits_.isctype(__ch, __neg_mask_))
+        {
+            __found = true;
+            goto __exit;
+        }
+    }
+    else
+        __found = __negate_;  // force reject
+__exit:
+    if (__found != __negate_)
+    {
+        __s.__do_ = __state::__accept_and_consume;
+        __s.__current_ += __consumed;
+        __s.__node_ = this->first();
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+template <class _CharT, class _Traits> class __lookahead;
+
+template <class _CharT, class _Traits = regex_traits<_CharT> >
+class _LIBCPP_TYPE_VIS_ONLY basic_regex
+{
+public:
+    // types:
+    typedef _CharT                              value_type;
+    typedef regex_constants::syntax_option_type flag_type;
+    typedef typename _Traits::locale_type       locale_type;
+
+private:
+    _Traits   __traits_;
+    flag_type __flags_;
+    unsigned __marked_count_;
+    unsigned __loop_count_;
+    int __open_count_;
+    shared_ptr<__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)
+        {}
+    _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)
+        {__parse(__p, __p + __traits_.length(__p));}
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex(const value_type* __p, size_t __len, flag_type __f)
+        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(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)
+        {__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)
+        {__parse(__first, __last);}
+#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+    _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)
+        {__parse(__il.begin(), __il.end());}
+#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+
+//    ~basic_regex() = default;
+
+//     basic_regex& operator=(const basic_regex&) = default;
+//     basic_regex& operator=(basic_regex&&) = default;
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& operator=(const value_type* __p)
+        {return assign(__p);}
+#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& operator=(initializer_list<value_type> __il)
+        {return assign(__il);}
+#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+    template <class _ST, class _SA>
+        _LIBCPP_INLINE_VISIBILITY
+        basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p)
+        {return assign(__p);}
+
+    // assign:
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& assign(const basic_regex& __that)
+        {return *this = __that;}
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& assign(basic_regex&& __that) _NOEXCEPT
+        {return *this = _VSTD::move(__that);}
+#endif
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
+        {return assign(__p, __p + __traits_.length(__p), __f);}
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& assign(const value_type* __p, size_t __len, flag_type __f)
+        {return assign(__p, __p + __len, __f);}
+    template <class _ST, class _SA>
+        _LIBCPP_INLINE_VISIBILITY
+        basic_regex& assign(const basic_string<value_type, _ST, _SA>& __s,
+                            flag_type __f = regex_constants::ECMAScript)
+            {return assign(__s.begin(), __s.end(), __f);}
+
+    template <class _InputIterator>
+        _LIBCPP_INLINE_VISIBILITY
+        typename enable_if
+        <
+             __is_input_iterator  <_InputIterator>::value &&
+            !__is_forward_iterator<_InputIterator>::value,
+            basic_regex&
+        >::type
+        assign(_InputIterator __first, _InputIterator __last,
+                            flag_type __f = regex_constants::ECMAScript)
+        {
+            basic_string<_CharT> __t(__first, __last);
+            return assign(__t.begin(), __t.end(), __f);
+        }
+
+private:
+    _LIBCPP_INLINE_VISIBILITY
+    void __member_init(flag_type __f)
+    {
+        __flags_ = __f;
+        __marked_count_ = 0;
+        __loop_count_ = 0;
+        __open_count_ = 0;
+        __end_ = nullptr;
+    }
+public:
+
+    template <class _ForwardIterator>
+        _LIBCPP_INLINE_VISIBILITY
+        typename enable_if
+        <
+            __is_forward_iterator<_ForwardIterator>::value,
+            basic_regex&
+        >::type
+        assign(_ForwardIterator __first, _ForwardIterator __last,
+                            flag_type __f = regex_constants::ECMAScript)
+        {
+            __member_init(__f);
+            __parse(__first, __last);
+            return *this;
+        }
+
+#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+
+    _LIBCPP_INLINE_VISIBILITY
+    basic_regex& assign(initializer_list<value_type> __il,
+                        flag_type __f = regex_constants::ECMAScript)
+        {return assign(__il.begin(), __il.end(), __f);}
+
+#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+
+    // const operations:
+    _LIBCPP_INLINE_VISIBILITY
+    unsigned mark_count() const {return __marked_count_;}
+    _LIBCPP_INLINE_VISIBILITY
+    flag_type flags() const {return __flags_;}
+
+    // locale:
+    _LIBCPP_INLINE_VISIBILITY
+    locale_type imbue(locale_type __loc)
+    {
+        __member_init(ECMAScript);
+        __start_.reset();
+        return __traits_.imbue(__loc);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    locale_type getloc() const {return __traits_.getloc();}
+
+    // swap:
+    void swap(basic_regex& __r);
+
+private:
+    _LIBCPP_INLINE_VISIBILITY
+    unsigned __loop_count() const {return __loop_count_;}
+
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
+                               __owns_one_state<_CharT>* __s,
+                               unsigned __mexp_begin, unsigned __mexp_end);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
+                                __owns_one_state<_CharT>* __s,
+                                unsigned __mexp_begin, unsigned __mexp_end);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last,
+                            __bracket_expression<_CharT, _Traits>* __ml);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last,
+                                __bracket_expression<_CharT, _Traits>* __ml);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last,
+                                  __bracket_expression<_CharT, _Traits>* __ml);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_character_class(_ForwardIterator __first, _ForwardIterator __last,
+                                __bracket_expression<_CharT, _Traits>* __ml);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last,
+                                 basic_string<_CharT>& __col_sym);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_term(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_atom(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last,
+                                 basic_string<_CharT>* __str = nullptr);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_grep(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _ForwardIterator
+        __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);
+    template <class _ForwardIterator>
+        _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);
+
+    _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)
+        {__push_loop(__min, numeric_limits<size_t>::max(), __s,
+                     __mexp_begin, __mexp_end);}
+    _LIBCPP_INLINE_VISIBILITY
+    void __push_nongreedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
+                                  unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
+        {__push_loop(__min, numeric_limits<size_t>::max(), __s,
+                     __mexp_begin, __mexp_end, false);}
+    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);
+    __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);
+    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);
+
+    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,
+                 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
+        __match_at_start_posix_subs(const _CharT* __first, const _CharT* __last,
+                 match_results<const _CharT*, _Allocator>& __m,
+                 regex_constants::match_flag_type __flags, bool) const;
+
+    template <class _Bp, class _Ap, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
+                 regex_constants::match_flag_type);
+
+    template <class _Ap, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(const _Cp*, const _Cp*, match_results<const _Cp*, _Ap>&,
+                 const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
+
+    template <class _Bp, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&,
+                 regex_constants::match_flag_type);
+
+    template <class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(const _Cp*, const _Cp*,
+                 const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
+
+    template <class _Cp, class _Ap, class _Tp>
+    friend
+    bool
+    regex_search(const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&,
+                 regex_constants::match_flag_type);
+
+    template <class _ST, class _SA, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(const basic_string<_Cp, _ST, _SA>& __s,
+                 const basic_regex<_Cp, _Tp>& __e,
+                 regex_constants::match_flag_type __flags);
+
+    template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(const basic_string<_Cp, _ST, _SA>& __s,
+                 match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
+                 const basic_regex<_Cp, _Tp>& __e,
+                 regex_constants::match_flag_type __flags);
+
+    template <class _Iter, class _Ap, class _Cp, class _Tp>
+    friend
+    bool
+    regex_search(__wrap_iter<_Iter> __first,
+                 __wrap_iter<_Iter> __last,
+                 match_results<__wrap_iter<_Iter>, _Ap>& __m,
+                 const basic_regex<_Cp, _Tp>& __e,
+                 regex_constants::match_flag_type __flags);
+
+    template <class, class> friend class __lookahead;
+};
+
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;
+template <class _CharT, class _Traits>
+    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;
+
+template <class _CharT, class _Traits>
+void
+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(__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)
+{
+    return __x.swap(__y);
+}
+
+// __lookahead
+
+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), __invert_(__invert), __mexp_(__mexp) {}
+
+    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,
+                                                  __s.__flags_ | regex_constants::match_continuous,
+                                                  __s.__at_first_ && __s.__current_ == __s.__first_);
+    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];
+        }
+    }
+    else
+    {
+        __s.__do_ = __state::__reject;
+        __s.__node_ = nullptr;
+    }
+}
+
+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();
+    }
+    switch (__flags_ & 0x1F0)
+    {
+    case ECMAScript:
+        __first = __parse_ecma_exp(__first, __last);
+        break;
+    case basic:
+        __first = __parse_basic_reg_exp(__first, __last);
+        break;
+    case extended:
+    case awk:
+        __first = __parse_extended_reg_exp(__first, __last);
+        break;
+    case grep:
+        __first = __parse_grep(__first, __last);
+        break;
+    case egrep:
+        __first = __parse_egrep(__first, __last);
+        break;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    default:
+        throw regex_error(regex_constants::__re_err_grammar);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
+                                                    _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        if (*__first == '^')
+        {
+            __push_l_anchor();
+            ++__first;
+        }
+        if (__first != __last)
+        {
+            __first = __parse_RE_expression(__first, __last);
+            if (__first != __last)
+            {
+                _ForwardIterator __temp = _VSTD::next(__first);
+                if (__temp == __last && *__first == '$')
+                {
+                    __push_r_anchor();
+                    ++__first;
+                }
+            }
+        }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__first != __last)
+            throw regex_error(regex_constants::__re_err_empty);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
+                                                       _ForwardIterator __last)
+{
+    __owns_one_state<_CharT>* __sa = __end_;
+    _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__temp == __first)
+        throw regex_error(regex_constants::__re_err_empty);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    __first = __temp;
+    while (__first != __last && *__first == '|')
+    {
+        __owns_one_state<_CharT>* __sb = __end_;
+        __temp = __parse_ERE_branch(++__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__temp == __first)
+            throw regex_error(regex_constants::__re_err_empty);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        __push_alternation(__sa, __sb);
+        __first = __temp;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
+                                                 _ForwardIterator __last)
+{
+    _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__temp == __first)
+        throw regex_error(regex_constants::__re_err_empty);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    do
+    {
+        __first = __temp;
+        __temp = __parse_ERE_expression(__first, __last);
+    } while (__temp != __first);
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
+                                                     _ForwardIterator __last)
+{
+    __owns_one_state<_CharT>* __e = __end_;
+    unsigned __mexp_begin = __marked_count_;
+    _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
+    if (__temp == __first && __temp != __last)
+    {
+        switch (*__temp)
+        {
+        case '^':
+            __push_l_anchor();
+            ++__temp;
+            break;
+        case '$':
+            __push_r_anchor();
+            ++__temp;
+            break;
+        case '(':
+            __push_begin_marked_subexpression();
+            unsigned __temp_count = __marked_count_;
+            ++__open_count_;
+            __temp = __parse_extended_reg_exp(++__temp, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__temp == __last || *__temp != ')')
+                throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __push_end_marked_subexpression(__temp_count);
+            --__open_count_;
+            ++__temp;
+            break;
+        }
+    }
+    if (__temp != __first)
+        __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin+1,
+                                         __marked_count_+1);
+    __first = __temp;
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
+                                                    _ForwardIterator __last)
+{
+    while (true)
+    {
+        _ForwardIterator __temp = __parse_simple_RE(__first, __last);
+        if (__temp == __first)
+            break;
+        __first = __temp;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
+                                                _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        __owns_one_state<_CharT>* __e = __end_;
+        unsigned __mexp_begin = __marked_count_;
+        _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
+        if (__temp != __first)
+            __first = __parse_RE_dupl_symbol(__temp, __last, __e,
+                                             __mexp_begin+1, __marked_count_+1);
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
+                                                 _ForwardIterator __last)
+{
+    _ForwardIterator __temp = __first;
+    __first = __parse_one_char_or_coll_elem_RE(__first, __last);
+    if (__temp == __first)
+    {
+        __temp = __parse_Back_open_paren(__first, __last);
+        if (__temp != __first)
+        {
+            __push_begin_marked_subexpression();
+            unsigned __temp_count = __marked_count_;
+            __first = __parse_RE_expression(__temp, __last);
+            __temp = __parse_Back_close_paren(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__temp == __first)
+                throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __push_end_marked_subexpression(__temp_count);
+            __first = __temp;
+        }
+        else
+            __first = __parse_BACKREF(__first, __last);
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
+                                                       _ForwardIterator __first,
+                                                       _ForwardIterator __last)
+{
+    _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
+    if (__temp == __first)
+    {
+        __temp = __parse_QUOTED_CHAR(__first, __last);
+        if (__temp == __first)
+        {
+            if (__temp != __last && *__temp == '.')
+            {
+                __push_match_any();
+                ++__temp;
+            }
+            else
+                __temp = __parse_bracket_expression(__first, __last);
+        }
+    }
+    __first = __temp;
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
+                                                       _ForwardIterator __first,
+                                                       _ForwardIterator __last)
+{
+    _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
+    if (__temp == __first)
+    {
+        __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
+        if (__temp == __first)
+        {
+            if (__temp != __last && *__temp == '.')
+            {
+                __push_match_any();
+                ++__temp;
+            }
+            else
+                __temp = __parse_bracket_expression(__first, __last);
+        }
+    }
+    __first = __temp;
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
+                                                      _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\' && *__temp == '(')
+                __first = ++__temp;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
+                                                       _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\' && *__temp == ')')
+                __first = ++__temp;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
+                                                      _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\' && *__temp == '{')
+                __first = ++__temp;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
+                                                       _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\' && *__temp == '}')
+                __first = ++__temp;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+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 == '\\' && '1' <= *__temp && *__temp <= '9')
+            {
+                __push_back_ref(*__temp - '0');
+                __first = ++__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)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp == __last && *__first == '$')
+            return __first;
+        // Not called inside a bracket
+        if (*__first == '.' || *__first == '\\' || *__first == '[')
+            return __first;
+        __push_char(*__first);
+        ++__first;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
+                                                   _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        switch (*__first)
+        {
+        case '^':
+        case '.':
+        case '[':
+        case '$':
+        case '(':
+        case '|':
+        case '*':
+        case '+':
+        case '?':
+        case '{':
+        case '\\':
+            break;
+        case ')':
+            if (__open_count_ == 0)
+            {
+                __push_char(*__first);
+                ++__first;
+            }
+            break;
+        default:
+            __push_char(*__first);
+            ++__first;
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
+                                                  _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\')
+            {
+                switch (*__temp)
+                {
+                case '^':
+                case '.':
+                case '*':
+                case '[':
+                case '$':
+                case '\\':
+                    __push_char(*__temp);
+                    __first = ++__temp;
+                    break;
+                }
+            }
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
+                                                      _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        if (__temp != __last)
+        {
+            if (*__first == '\\')
+            {
+                switch (*__temp)
+                {
+                case '^':
+                case '.':
+                case '*':
+                case '[':
+                case '$':
+                case '\\':
+                case '(':
+                case ')':
+                case '|':
+                case '+':
+                case '?':
+                case '{':
+                case '}':
+                    __push_char(*__temp);
+                    __first = ++__temp;
+                    break;
+                default:
+                    if ((__flags_ & 0x1F0) == awk)
+                        __first = __parse_awk_escape(++__first, __last);
+                    break;
+                }
+            }
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
+                                                     _ForwardIterator __last,
+                                                     __owns_one_state<_CharT>* __s,
+                                                     unsigned __mexp_begin,
+                                                     unsigned __mexp_end)
+{
+    if (__first != __last)
+    {
+        if (*__first == '*')
+        {
+            __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
+            ++__first;
+        }
+        else
+        {
+            _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
+            if (__temp != __first)
+            {
+                int __min = 0;
+                __first = __temp;
+                __temp = __parse_DUP_COUNT(__first, __last, __min);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__temp == __first)
+                    throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                __first = __temp;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__first == __last)
+                    throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                if (*__first != ',')
+                {
+                    __temp = __parse_Back_close_brace(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                    if (__temp == __first)
+                        throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                    __push_loop(__min, __min, __s, __mexp_begin, __mexp_end,
+                                    true);
+                    __first = __temp;
+                }
+                else
+                {
+                    ++__first;  // consume ','
+                    int __max = -1;
+                    __first = __parse_DUP_COUNT(__first, __last, __max);
+                    __temp = __parse_Back_close_brace(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                    if (__temp == __first)
+                        throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                    if (__max == -1)
+                        __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
+                    else
+                    {
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                        if (__max < __min)
+                            throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                        __push_loop(__min, __max, __s, __mexp_begin, __mexp_end,
+                                    true);
+                    }
+                    __first = __temp;
+                }
+            }
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
+                                                      _ForwardIterator __last,
+                                                      __owns_one_state<_CharT>* __s,
+                                                      unsigned __mexp_begin,
+                                                      unsigned __mexp_end)
+{
+    if (__first != __last)
+    {
+        unsigned __grammar = __flags_ & 0x1F0;
+        switch (*__first)
+        {
+        case '*':
+            ++__first;
+            if (__grammar == ECMAScript && __first != __last && *__first == '?')
+            {
+                ++__first;
+                __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
+            }
+            else
+                __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
+            break;
+        case '+':
+            ++__first;
+            if (__grammar == ECMAScript && __first != __last && *__first == '?')
+            {
+                ++__first;
+                __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
+            }
+            else
+                __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
+            break;
+        case '?':
+            ++__first;
+            if (__grammar == ECMAScript && __first != __last && *__first == '?')
+            {
+                ++__first;
+                __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);
+            }
+            else
+                __push_loop(0, 1, __s, __mexp_begin, __mexp_end);
+            break;
+        case '{':
+            {
+                int __min;
+                _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__temp == __first)
+                    throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                __first = __temp;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__first == __last)
+                    throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                switch (*__first)
+                {
+                case '}':
+                    ++__first;
+                    if (__grammar == ECMAScript && __first != __last && *__first == '?')
+                    {
+                        ++__first;
+                        __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);
+                    }
+                    else
+                        __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);
+                    break;
+                case ',':
+                    ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                    if (__first == __last)
+                        throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                    if (*__first == '}')
+                    {
+                        ++__first;
+                        if (__grammar == ECMAScript && __first != __last && *__first == '?')
+                        {
+                            ++__first;
+                            __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
+                        }
+                        else
+                            __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
+                    }
+                    else
+                    {
+                        int __max = -1;
+                        __temp = __parse_DUP_COUNT(__first, __last, __max);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                        if (__temp == __first)
+                            throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                        __first = __temp;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                        if (__first == __last || *__first != '}')
+                            throw regex_error(regex_constants::error_brace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                        ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                        if (__max < __min)
+                            throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                        if (__grammar == ECMAScript && __first != __last && *__first == '?')
+                        {
+                            ++__first;
+                            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);
+                        }
+                        else
+                            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);
+                    }
+                    break;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                default:
+                    throw regex_error(regex_constants::error_badbrace);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                }
+            }
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
+                                                         _ForwardIterator __last)
+{
+    if (__first != __last && *__first == '[')
+    {
+        ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__first == __last)
+            throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        bool __negate = false;
+        if (*__first == '^')
+        {
+            ++__first;
+            __negate = true;
+        }
+        __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
+        // __ml owned by *this
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__first == __last)
+            throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        if ((__flags_ & 0x1F0) != ECMAScript && *__first == ']')
+        {
+            __ml->__add_char(']');
+            ++__first;
+        }
+        __first = __parse_follow_list(__first, __last, __ml);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__first == __last)
+            throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        if (*__first == '-')
+        {
+            __ml->__add_char('-');
+            ++__first;
+        }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        if (__first == __last || *__first != ']')
+            throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        ++__first;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
+                                    _ForwardIterator __last,
+                                    __bracket_expression<_CharT, _Traits>* __ml)
+{
+    if (__first != __last)
+    {
+        while (true)
+        {
+            _ForwardIterator __temp = __parse_expression_term(__first, __last,
+                                                              __ml);
+            if (__temp == __first)
+                break;
+            __first = __temp;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
+                                    _ForwardIterator __last,
+                                    __bracket_expression<_CharT, _Traits>* __ml)
+{
+    if (__first != __last && *__first != ']')
+    {
+        _ForwardIterator __temp = _VSTD::next(__first);
+        basic_string<_CharT> __start_range;
+        if (__temp != __last && *__first == '[')
+        {
+            if (*__temp == '=')
+                return __parse_equivalence_class(++__temp, __last, __ml);
+            else if (*__temp == ':')
+                return __parse_character_class(++__temp, __last, __ml);
+            else if (*__temp == '.')
+                __first = __parse_collating_symbol(++__temp, __last, __start_range);
+        }
+        unsigned __grammar = __flags_ & 0x1F0;
+        if (__start_range.empty())
+        {
+            if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
+            {
+                if (__grammar == ECMAScript)
+                    __first = __parse_class_escape(++__first, __last, __start_range, __ml);
+                else
+                    __first = __parse_awk_escape(++__first, __last, &__start_range);
+            }
+            else
+            {
+                __start_range = *__first;
+                ++__first;
+            }
+        }
+        if (__first != __last && *__first != ']')
+        {
+            __temp = _VSTD::next(__first);
+            if (__temp != __last && *__first == '-' && *__temp != ']')
+            {
+                // parse a range
+                basic_string<_CharT> __end_range;
+                __first = __temp;
+                ++__temp;
+                if (__temp != __last && *__first == '[' && *__temp == '.')
+                    __first = __parse_collating_symbol(++__temp, __last, __end_range);
+                else
+                {
+                    if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
+                    {
+                        if (__grammar == ECMAScript)
+                            __first = __parse_class_escape(++__first, __last,
+                                                           __end_range, __ml);
+                        else
+                            __first = __parse_awk_escape(++__first, __last,
+                                                         &__end_range);
+                    }
+                    else
+                    {
+                        __end_range = *__first;
+                        ++__first;
+                    }
+                }
+                __ml->__add_range(_VSTD::move(__start_range), _VSTD::move(__end_range));
+            }
+            else if (!__start_range.empty())
+            {
+                if (__start_range.size() == 1)
+                    __ml->__add_char(__start_range[0]);
+                else
+                    __ml->__add_digraph(__start_range[0], __start_range[1]);
+            }
+        }
+        else if (!__start_range.empty())
+        {
+            if (__start_range.size() == 1)
+                __ml->__add_char(__start_range[0]);
+            else
+                __ml->__add_digraph(__start_range[0], __start_range[1]);
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_class_escape(_ForwardIterator __first,
+                          _ForwardIterator __last,
+                          basic_string<_CharT>& __str,
+                          __bracket_expression<_CharT, _Traits>* __ml)
+{
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__first == __last)
+        throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    switch (*__first)
+    {
+    case 0:
+        __str = *__first;
+        return ++__first;
+    case 'b':
+        __str = _CharT(8);
+        return ++__first;
+    case 'd':
+        __ml->__add_class(ctype_base::digit);
+        return ++__first;
+    case 'D':
+        __ml->__add_neg_class(ctype_base::digit);
+        return ++__first;
+    case 's':
+        __ml->__add_class(ctype_base::space);
+        return ++__first;
+    case 'S':
+        __ml->__add_neg_class(ctype_base::space);
+        return ++__first;
+    case 'w':
+        __ml->__add_class(ctype_base::alnum);
+        __ml->__add_char('_');
+        return ++__first;
+    case 'W':
+        __ml->__add_neg_class(ctype_base::alnum);
+        __ml->__add_neg_char('_');
+        return ++__first;
+    }
+    __first = __parse_character_escape(__first, __last, &__str);
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_awk_escape(_ForwardIterator __first,
+                          _ForwardIterator __last,
+                          basic_string<_CharT>* __str)
+{
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__first == __last)
+        throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    switch (*__first)
+    {
+    case '\\':
+    case '"':
+    case '/':
+        if (__str)
+            *__str = *__first;
+        else
+            __push_char(*__first);
+        return ++__first;
+    case 'a':
+        if (__str)
+            *__str = _CharT(7);
+        else
+            __push_char(_CharT(7));
+        return ++__first;
+    case 'b':
+        if (__str)
+            *__str = _CharT(8);
+        else
+            __push_char(_CharT(8));
+        return ++__first;
+    case 'f':
+        if (__str)
+            *__str = _CharT(0xC);
+        else
+            __push_char(_CharT(0xC));
+        return ++__first;
+    case 'n':
+        if (__str)
+            *__str = _CharT(0xA);
+        else
+            __push_char(_CharT(0xA));
+        return ++__first;
+    case 'r':
+        if (__str)
+            *__str = _CharT(0xD);
+        else
+            __push_char(_CharT(0xD));
+        return ++__first;
+    case 't':
+        if (__str)
+            *__str = _CharT(0x9);
+        else
+            __push_char(_CharT(0x9));
+        return ++__first;
+    case 'v':
+        if (__str)
+            *__str = _CharT(0xB);
+        else
+            __push_char(_CharT(0xB));
+        return ++__first;
+    }
+    if ('0' <= *__first && *__first <= '7')
+    {
+        unsigned __val = *__first - '0';
+        if (++__first != __last && ('0' <= *__first && *__first <= '7'))
+        {
+            __val = 8 * __val + *__first - '0';
+            if (++__first != __last && ('0' <= *__first && *__first <= '7'))
+                __val = 8 * __val + *__first++ - '0';
+        }
+        if (__str)
+            *__str = _CharT(__val);
+        else
+            __push_char(_CharT(__val));
+    }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    else
+        throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
+                                    _ForwardIterator __last,
+                                    __bracket_expression<_CharT, _Traits>* __ml)
+{
+    // Found [=
+    //   This means =] must exist
+    value_type _Equal_close[2] = {'=', ']'};
+    _ForwardIterator __temp = _VSTD::search(__first, __last, _Equal_close,
+                                                            _Equal_close+2);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__temp == __last)
+        throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    // [__first, __temp) contains all text in [= ... =]
+    typedef typename _Traits::string_type string_type;
+    string_type __collate_name =
+        __traits_.lookup_collatename(__first, __temp);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__collate_name.empty())
+        throw regex_error(regex_constants::error_collate);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    string_type __equiv_name =
+        __traits_.transform_primary(__collate_name.begin(),
+                                    __collate_name.end());
+    if (!__equiv_name.empty())
+        __ml->__add_equivalence(__equiv_name);
+    else
+    {
+        switch (__collate_name.size())
+        {
+        case 1:
+            __ml->__add_char(__collate_name[0]);
+            break;
+        case 2:
+            __ml->__add_digraph(__collate_name[0], __collate_name[1]);
+            break;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+        default:
+            throw regex_error(regex_constants::error_collate);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+        }
+    }
+    __first = _VSTD::next(__temp, 2);
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
+                                    _ForwardIterator __last,
+                                    __bracket_expression<_CharT, _Traits>* __ml)
+{
+    // Found [:
+    //   This means :] must exist
+    value_type _Colon_close[2] = {':', ']'};
+    _ForwardIterator __temp = _VSTD::search(__first, __last, _Colon_close,
+                                                            _Colon_close+2);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__temp == __last)
+        throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    // [__first, __temp) contains all text in [: ... :]
+    typedef typename _Traits::char_class_type char_class_type;
+    char_class_type __class_type =
+        __traits_.lookup_classname(__first, __temp, __flags_ & icase);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__class_type == 0)
+        throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    __ml->__add_class(__class_type);
+    __first = _VSTD::next(__temp, 2);
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
+                                                _ForwardIterator __last,
+                                                basic_string<_CharT>& __col_sym)
+{
+    // Found [.
+    //   This means .] must exist
+    value_type _Dot_close[2] = {'.', ']'};
+    _ForwardIterator __temp = _VSTD::search(__first, __last, _Dot_close,
+                                                            _Dot_close+2);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    if (__temp == __last)
+        throw regex_error(regex_constants::error_brack);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    // [__first, __temp) contains all text in [. ... .]
+    typedef typename _Traits::string_type string_type;
+    __col_sym = __traits_.lookup_collatename(__first, __temp);
+    switch (__col_sym.size())
+    {
+    case 1:
+    case 2:
+        break;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+    default:
+        throw regex_error(regex_constants::error_collate);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+    }
+    __first = _VSTD::next(__temp, 2);
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
+                                                _ForwardIterator __last,
+                                                int& __c)
+{
+    if (__first != __last && '0' <= *__first && *__first <= '9')
+    {
+        __c = *__first - '0';
+        for (++__first; __first != __last && '0' <= *__first && *__first <= '9';
+                                                                      ++__first)
+        {
+            __c *= 10;
+            __c += *__first - '0';
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first,
+                                               _ForwardIterator __last)
+{
+    __owns_one_state<_CharT>* __sa = __end_;
+    _ForwardIterator __temp = __parse_alternative(__first, __last);
+    if (__temp == __first)
+        __push_empty();
+    __first = __temp;
+    while (__first != __last && *__first == '|')
+    {
+        __owns_one_state<_CharT>* __sb = __end_;
+        __temp = __parse_alternative(++__first, __last);
+        if (__temp == __first)
+            __push_empty();
+        __push_alternation(__sa, __sb);
+        __first = __temp;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first,
+                                                  _ForwardIterator __last)
+{
+    while (true)
+    {
+        _ForwardIterator __temp = __parse_term(__first, __last);
+        if (__temp == __first)
+            break;
+        __first = __temp;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first,
+                                           _ForwardIterator __last)
+{
+    _ForwardIterator __temp = __parse_assertion(__first, __last);
+    if (__temp == __first)
+    {
+        __owns_one_state<_CharT>* __e = __end_;
+        unsigned __mexp_begin = __marked_count_;
+        __temp = __parse_atom(__first, __last);
+        if (__temp != __first)
+            __first = __parse_ERE_dupl_symbol(__temp, __last, __e,
+                                              __mexp_begin+1, __marked_count_+1);
+    }
+    else
+        __first = __temp;
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first,
+                                                _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        switch (*__first)
+        {
+        case '^':
+            __push_l_anchor();
+            ++__first;
+            break;
+        case '$':
+            __push_r_anchor();
+            ++__first;
+            break;
+        case '\\':
+            {
+                _ForwardIterator __temp = _VSTD::next(__first);
+                if (__temp != __last)
+                {
+                    if (*__temp == 'b')
+                    {
+                        __push_word_boundary(false);
+                        __first = ++__temp;
+                    }
+                    else if (*__temp == 'B')
+                    {
+                        __push_word_boundary(true);
+                        __first = ++__temp;
+                    }
+                }
+            }
+            break;
+        case '(':
+            {
+                _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;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                                if (__temp == __last || *__temp != ')')
+                                    throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                                __first = ++__temp;
+                            }
+                            break;
+                        case '!':
+                            {
+                                basic_regex __exp;
+                                __exp.__flags_ = __flags_;
+                                __temp = __exp.__parse(++__temp, __last);
+                                unsigned __mexp = __exp.__marked_count_;
+                                __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
+                                __marked_count_ += __mexp;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                                if (__temp == __last || *__temp != ')')
+                                    throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                                __first = ++__temp;
+                            }
+                            break;
+                        }
+                    }
+                }
+            }
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first,
+                                           _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        switch (*__first)
+        {
+        case '.':
+            __push_match_any_but_newline();
+            ++__first;
+            break;
+        case '\\':
+            __first = __parse_atom_escape(__first, __last);
+            break;
+        case '[':
+            __first = __parse_bracket_expression(__first, __last);
+            break;
+        case '(':
+            {
+                ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                if (__first == __last)
+                    throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                _ForwardIterator __temp = _VSTD::next(__first);
+                if (__temp != __last && *__first == '?' && *__temp == ':')
+                {
+                    ++__open_count_;
+                    __first = __parse_ecma_exp(++__temp, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                    if (__first == __last || *__first != ')')
+                        throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                    --__open_count_;
+                    ++__first;
+                }
+                else
+                {
+                    __push_begin_marked_subexpression();
+                    unsigned __temp_count = __marked_count_;
+                    ++__open_count_;
+                    __first = __parse_ecma_exp(__first, __last);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                    if (__first == __last || *__first != ')')
+                        throw regex_error(regex_constants::error_paren);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+                    __push_end_marked_subexpression(__temp_count);
+                    --__open_count_;
+                    ++__first;
+                }
+            }
+            break;
+        default:
+            __first = __parse_pattern_character(__first, __last);
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first,
+                                                  _ForwardIterator __last)
+{
+    if (__first != __last && *__first == '\\')
+    {
+        _ForwardIterator __t1 = _VSTD::next(__first);
+        _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
+        if (__t2 != __t1)
+            __first = __t2;
+        else
+        {
+            __t2 = __parse_character_class_escape(__t1, __last);
+            if (__t2 != __t1)
+                __first = __t2;
+            else
+            {
+                __t2 = __parse_character_escape(__t1, __last);
+                if (__t2 != __t1)
+                    __first = __t2;
+            }
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first,
+                                                     _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        if (*__first == '0')
+        {
+            __push_char(_CharT());
+            ++__first;
+        }
+        else if ('1' <= *__first && *__first <= '9')
+        {
+            unsigned __v = *__first - '0';
+            for (++__first; '0' <= *__first && *__first <= '9'; ++__first)
+                __v = 10 * __v + *__first - '0';
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__v > mark_count())
+                throw regex_error(regex_constants::error_backref);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __push_back_ref(__v);
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first,
+                                                             _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        __bracket_expression<_CharT, _Traits>* __ml;
+        switch (*__first)
+        {
+        case 'd':
+            __ml = __start_matching_list(false);
+            __ml->__add_class(ctype_base::digit);
+            ++__first;
+            break;
+        case 'D':
+            __ml = __start_matching_list(true);
+            __ml->__add_class(ctype_base::digit);
+            ++__first;
+            break;
+        case 's':
+            __ml = __start_matching_list(false);
+            __ml->__add_class(ctype_base::space);
+            ++__first;
+            break;
+        case 'S':
+            __ml = __start_matching_list(true);
+            __ml->__add_class(ctype_base::space);
+            ++__first;
+            break;
+        case 'w':
+            __ml = __start_matching_list(false);
+            __ml->__add_class(ctype_base::alnum);
+            __ml->__add_char('_');
+            ++__first;
+            break;
+        case 'W':
+            __ml = __start_matching_list(true);
+            __ml->__add_class(ctype_base::alnum);
+            __ml->__add_char('_');
+            ++__first;
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_character_escape(_ForwardIterator __first,
+                                                    _ForwardIterator __last,
+                                                    basic_string<_CharT>* __str)
+{
+    if (__first != __last)
+    {
+        _ForwardIterator __t;
+        unsigned __sum = 0;
+        int __hd;
+        switch (*__first)
+        {
+        case 'f':
+            if (__str)
+                *__str = _CharT(0xC);
+            else
+                __push_char(_CharT(0xC));
+            ++__first;
+            break;
+        case 'n':
+            if (__str)
+                *__str = _CharT(0xA);
+            else
+                __push_char(_CharT(0xA));
+            ++__first;
+            break;
+        case 'r':
+            if (__str)
+                *__str = _CharT(0xD);
+            else
+                __push_char(_CharT(0xD));
+            ++__first;
+            break;
+        case 't':
+            if (__str)
+                *__str = _CharT(0x9);
+            else
+                __push_char(_CharT(0x9));
+            ++__first;
+            break;
+        case 'v':
+            if (__str)
+                *__str = _CharT(0xB);
+            else
+                __push_char(_CharT(0xB));
+            ++__first;
+            break;
+        case 'c':
+            if ((__t = _VSTD::next(__first)) != __last)
+            {
+                if (('A' <= *__t && *__t <= 'Z') || 
+                    ('a' <= *__t && *__t <= 'z'))
+                {
+                    if (__str)
+                        *__str = _CharT(*__t % 32);
+                    else
+                        __push_char(_CharT(*__t % 32));
+                    __first = ++__t;
+                }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                else 
+                    throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            else
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            break;
+        case 'u':
+            ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__first == __last)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __hd = __traits_.value(*__first, 16);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__hd == -1)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __sum = 16 * __sum + static_cast<unsigned>(__hd);
+            ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__first == __last)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __hd = __traits_.value(*__first, 16);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__hd == -1)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __sum = 16 * __sum + static_cast<unsigned>(__hd);
+            // drop through
+        case 'x':
+            ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__first == __last)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __hd = __traits_.value(*__first, 16);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__hd == -1)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __sum = 16 * __sum + static_cast<unsigned>(__hd);
+            ++__first;
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__first == __last)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __hd = __traits_.value(*__first, 16);
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            if (__hd == -1)
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            __sum = 16 * __sum + static_cast<unsigned>(__hd);
+            if (__str)
+                *__str = _CharT(__sum);
+            else
+                __push_char(_CharT(__sum));
+            ++__first;
+            break;
+        default:
+            if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum))
+            {
+                if (__str)
+                    *__str = *__first;
+                else
+                    __push_char(*__first);
+                ++__first;
+            }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+            else
+                throw regex_error(regex_constants::error_escape);
+#endif  // _LIBCPP_NO_EXCEPTIONS
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first,
+                                                        _ForwardIterator __last)
+{
+    if (__first != __last)
+    {
+        switch (*__first)
+        {
+        case '^':
+        case '$':
+        case '\\':
+        case '.':
+        case '*':
+        case '+':
+        case '?':
+        case '(':
+        case ')':
+        case '[':
+        case ']':
+        case '{':
+        case '}':
+        case '|':
+            break;
+        default:
+            __push_char(*__first);
+            ++__first;
+            break;
+        }
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first,
+                                           _ForwardIterator __last)
+{
+    __owns_one_state<_CharT>* __sa = __end_;
+    _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
+    if (__t1 != __first)
+        __parse_basic_reg_exp(__first, __t1);
+    else
+        __push_empty();
+    __first = __t1;
+    if (__first != __last)
+        ++__first;
+    while (__first != __last)
+    {
+        __t1 = _VSTD::find(__first, __last, _CharT('\n'));
+        __owns_one_state<_CharT>* __sb = __end_;
+        if (__t1 != __first)
+            __parse_basic_reg_exp(__first, __t1);
+        else
+            __push_empty();
+        __push_alternation(__sa, __sb);
+        __first = __t1;
+        if (__first != __last)
+            ++__first;
+    }
+    return __first;
+}
+
+template <class _CharT, class _Traits>
+template <class _ForwardIterator>
+_ForwardIterator
+basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first,
+                                            _ForwardIterator __last)
+{
+    __owns_one_state<_CharT>* __sa = __end_;
+    _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
+    if (__t1 != __first)
+        __parse_extended_reg_exp(__first, __t1);
+    else
+        __push_empty();
+    __first = __t1;
+    if (__first != __last)
+        ++__first;
+    while (__first != __last)
+    {
+        __t1 = _VSTD::find(__first, __last, _CharT('\n'));
+        __owns_one_state<_CharT>* __sb = __end_;
+        if (__t1 != __first)
+            __parse_extended_reg_exp(__first, __t1);
+        else
+            __push_empty();
+        __push_alternation(__sa, __sb);
+        __first = __t1;
+        if (__first != __last)
+            ++__first;
+    }
+    return __first;
+}
+
+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_,
+                __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
+                __min, __max));
+    __s->first() = nullptr;
+    __e1.release();
+    __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
+    __end_ = __e2->second();
+    __s->first() = __e2.release();
+    ++__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>
+                                              (__traits_, __c, __end_->first());
+    else if (flags() & collate)
+        __end_->first() = new __match_char_collate<_CharT, _Traits>
+                                              (__traits_, __c, __end_->first());
+    else
+        __end_->first() = new __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_ = 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_ = 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_ = 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_ = 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_ = 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_ = 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_ = 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_ = 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>
+                                              (__traits_, __i, __end_->first());
+    else if (flags() & collate)
+        __end_->first() = new __back_ref_collate<_CharT, _Traits>
+                                              (__traits_, __i, __end_->first());
+    else
+        __end_->first() = new __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>(
+                         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());
+    __end_->first() = nullptr;
+    __end_->first() = new __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);
+    __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_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
+}
+
+typedef basic_regex<char>    regex;
+typedef basic_regex<wchar_t> wregex;
+
+// sub_match
+
+template <class _BidirectionalIterator>
+class _LIBCPP_TYPE_VIS_ONLY sub_match
+    : public pair<_BidirectionalIterator, _BidirectionalIterator>
+{
+public:
+    typedef _BidirectionalIterator                              iterator;
+    typedef typename iterator_traits<iterator>::value_type      value_type;
+    typedef typename iterator_traits<iterator>::difference_type difference_type;
+    typedef basic_string<value_type>                            string_type;
+
+    bool matched;
+
+    _LIBCPP_INLINE_VISIBILITY
+    _LIBCPP_CONSTEXPR sub_match() : matched() {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    difference_type length() const
+        {return matched ? _VSTD::distance(this->first, this->second) : 0;}
+    _LIBCPP_INLINE_VISIBILITY
+    string_type str() const
+        {return matched ? string_type(this->first, this->second) : string_type();}
+    _LIBCPP_INLINE_VISIBILITY
+    operator string_type() const
+        {return str();}
+
+    _LIBCPP_INLINE_VISIBILITY
+    int compare(const sub_match& __s) const
+        {return str().compare(__s.str());}
+    _LIBCPP_INLINE_VISIBILITY
+    int compare(const string_type& __s) const
+        {return str().compare(__s);}
+    _LIBCPP_INLINE_VISIBILITY
+    int compare(const value_type* __s) const
+        {return str().compare(__s);}
+};
+
+typedef sub_match<const char*>             csub_match;
+typedef sub_match<const wchar_t*>          wcsub_match;
+typedef sub_match<string::const_iterator>  ssub_match;
+typedef sub_match<wstring::const_iterator> wssub_match;
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return __x.compare(__y) == 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return __x.compare(__y) < 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return __y.compare(__x.c_str()) == 0;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+          const sub_match<_BiIter>& __y)
+{
+    return __y.compare(__x.c_str()) > 0;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+          const sub_match<_BiIter>& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+                const sub_match<_BiIter>& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(const sub_match<_BiIter>& __x,
+           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return __x.compare(__y.c_str()) == 0;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const sub_match<_BiIter>& __x,
+           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(const sub_match<_BiIter>& __x,
+          const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return __x.compare(__y.c_str()) < 0;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool operator>(const sub_match<_BiIter>& __x,
+               const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(const sub_match<_BiIter>& __x,
+           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(const sub_match<_BiIter>& __x,
+           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(typename iterator_traits<_BiIter>::value_type const* __x,
+           const sub_match<_BiIter>& __y)
+{
+    return __y.compare(__x) == 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(typename iterator_traits<_BiIter>::value_type const* __x,
+          const sub_match<_BiIter>& __y)
+{
+    return __y.compare(__x) > 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(typename iterator_traits<_BiIter>::value_type const* __x,
+          const sub_match<_BiIter>& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return __x.compare(__y) == 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(const sub_match<_BiIter>& __x,
+          typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return __x.compare(__y) < 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(const sub_match<_BiIter>& __x,
+          typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const* __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(typename iterator_traits<_BiIter>::value_type const& __x,
+           const sub_match<_BiIter>& __y)
+{
+    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
+    return __y.compare(string_type(1, __x)) == 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(typename iterator_traits<_BiIter>::value_type const& __x,
+          const sub_match<_BiIter>& __y)
+{
+    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
+    return __y.compare(string_type(1, __x)) > 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(typename iterator_traits<_BiIter>::value_type const& __x,
+          const sub_match<_BiIter>& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
+           const sub_match<_BiIter>& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator==(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
+    return __x.compare(string_type(1, __y)) == 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<(const sub_match<_BiIter>& __x,
+          typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
+    return __x.compare(string_type(1, __y)) < 0;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>(const sub_match<_BiIter>& __x,
+          typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    return __y < __x;
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator>=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    return !(__x < __y);
+}
+
+template <class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator<=(const sub_match<_BiIter>& __x,
+           typename iterator_traits<_BiIter>::value_type const& __y)
+{
+    return !(__y < __x);
+}
+
+template <class _CharT, class _ST, class _BiIter>
+inline _LIBCPP_INLINE_VISIBILITY
+basic_ostream<_CharT, _ST>&
+operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
+{
+    return __os << __m.str();
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+class _LIBCPP_TYPE_VIS_ONLY match_results
+{
+public:
+    typedef _Allocator                                        allocator_type;
+    typedef sub_match<_BidirectionalIterator>                 value_type;
+private:
+    typedef vector<value_type, allocator_type>                __container_type;
+
+    __container_type  __matches_;
+    value_type __unmatched_;
+    value_type __prefix_;
+    value_type __suffix_;
+    bool       __ready_;
+public:
+    _BidirectionalIterator __position_start_;
+    typedef const value_type&                                 const_reference;
+    typedef const_reference                                   reference;
+    typedef typename __container_type::const_iterator         const_iterator;
+    typedef const_iterator                                    iterator;
+    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
+    typedef typename allocator_traits<allocator_type>::size_type size_type;
+    typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
+    typedef basic_string<char_type>                           string_type;
+
+    // construct/copy/destroy:
+    explicit match_results(const allocator_type& __a = allocator_type());
+//    match_results(const match_results&) = default;
+//    match_results& operator=(const match_results&) = default;
+//    match_results(match_results&& __m) = default;
+//    match_results& operator=(match_results&& __m) = default;
+//    ~match_results() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool ready() const {return __ready_;}
+
+    // size:
+    _LIBCPP_INLINE_VISIBILITY
+    size_type size() const {return __matches_.size();}
+    _LIBCPP_INLINE_VISIBILITY
+    size_type max_size() const {return __matches_.max_size();}
+    _LIBCPP_INLINE_VISIBILITY
+    bool empty() const {return size() == 0;}
+
+    // element access:
+    _LIBCPP_INLINE_VISIBILITY
+    difference_type length(size_type __sub = 0) const
+        {return (*this)[__sub].length();}
+    _LIBCPP_INLINE_VISIBILITY
+    difference_type position(size_type __sub = 0) const
+        {return _VSTD::distance(__position_start_, (*this)[__sub].first);}
+    _LIBCPP_INLINE_VISIBILITY
+    string_type str(size_type __sub = 0) const
+        {return (*this)[__sub].str();}
+    _LIBCPP_INLINE_VISIBILITY
+    const_reference operator[](size_type __n) const
+        {return __n < __matches_.size() ? __matches_[__n] : __unmatched_;}
+
+    _LIBCPP_INLINE_VISIBILITY
+    const_reference prefix() const {return __prefix_;}
+    _LIBCPP_INLINE_VISIBILITY
+    const_reference suffix() const {return __suffix_;}
+
+    _LIBCPP_INLINE_VISIBILITY
+    const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin();}
+    _LIBCPP_INLINE_VISIBILITY
+    const_iterator end() const {return __matches_.end();}
+    _LIBCPP_INLINE_VISIBILITY
+    const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin();}
+    _LIBCPP_INLINE_VISIBILITY
+    const_iterator cend() const {return __matches_.end();}
+
+    // format:
+    template <class _OutputIter>
+        _OutputIter
+        format(_OutputIter __out, const char_type* __fmt_first,
+               const char_type* __fmt_last,
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
+    template <class _OutputIter, class _ST, class _SA>
+        _LIBCPP_INLINE_VISIBILITY
+        _OutputIter
+        format(_OutputIter __out, const basic_string<char_type, _ST, _SA>& __fmt,
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+            {return format(__out, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
+    template <class _ST, class _SA>
+        _LIBCPP_INLINE_VISIBILITY
+        basic_string<char_type, _ST, _SA>
+        format(const basic_string<char_type, _ST, _SA>& __fmt,
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+        {
+            basic_string<char_type, _ST, _SA> __r;
+            format(back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
+                   __flags);
+            return __r;
+        }
+    _LIBCPP_INLINE_VISIBILITY
+    string_type
+        format(const char_type* __fmt,
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+        {
+            string_type __r;
+            format(back_inserter(__r), __fmt,
+                   __fmt + char_traits<char_type>::length(__fmt), __flags);
+            return __r;
+        }
+
+    // allocator:
+    _LIBCPP_INLINE_VISIBILITY
+    allocator_type get_allocator() const {return __matches_.get_allocator();}
+
+    // swap:
+    void swap(match_results& __m);
+
+    template <class _Bp, class _Ap>
+        _LIBCPP_INLINE_VISIBILITY
+        void __assign(_BidirectionalIterator __f, _BidirectionalIterator __l,
+                      const match_results<_Bp, _Ap>& __m, bool __no_update_pos)
+    {
+        _Bp __mf = __m.prefix().first;
+        __matches_.resize(__m.size());
+        for (size_type __i = 0; __i < __matches_.size(); ++__i)
+        {
+            __matches_[__i].first = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].first));
+            __matches_[__i].second = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].second));
+            __matches_[__i].matched = __m[__i].matched;
+        }
+        __unmatched_.first   = __l;
+        __unmatched_.second  = __l;
+        __unmatched_.matched = false;
+        __prefix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().first));
+        __prefix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().second));
+        __prefix_.matched = __m.prefix().matched;
+        __suffix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().first));
+        __suffix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().second));
+        __suffix_.matched = __m.suffix().matched;
+        if (!__no_update_pos)
+            __position_start_ = __prefix_.first;
+        __ready_ = __m.ready();
+    }
+
+private:
+    void __init(unsigned __s,
+                _BidirectionalIterator __f, _BidirectionalIterator __l,
+                bool __no_update_pos = false);
+
+    template <class, class> friend class basic_regex;
+
+    template <class _Bp, class _Ap, class _Cp, class _Tp>
+    friend
+    bool
+    regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
+                regex_constants::match_flag_type);
+
+    template <class _Bp, class _Ap>
+    friend
+    bool
+    operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
+
+    template <class, class> friend class __lookahead;
+};
+
+template <class _BidirectionalIterator, class _Allocator>
+match_results<_BidirectionalIterator, _Allocator>::match_results(
+        const allocator_type& __a)
+    : __matches_(__a),
+      __unmatched_(),
+      __prefix_(),
+      __suffix_(),
+      __position_start_(),
+      __ready_(false)
+{
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+void
+match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
+                         _BidirectionalIterator __f, _BidirectionalIterator __l,
+                         bool __no_update_pos)
+{
+    __unmatched_.first   = __l;
+    __unmatched_.second  = __l;
+    __unmatched_.matched = false;
+    __matches_.assign(__s, __unmatched_);
+    __prefix_.first      = __f;
+    __prefix_.second     = __f;
+    __prefix_.matched    = false;
+    __suffix_ = __unmatched_;
+    if (!__no_update_pos)
+        __position_start_ = __prefix_.first;
+    __ready_ = true;
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+template <class _OutputIter>
+_OutputIter
+match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __out,
+        const char_type* __fmt_first, const char_type* __fmt_last,
+        regex_constants::match_flag_type __flags) const
+{
+    if (__flags & regex_constants::format_sed)
+    {
+        for (; __fmt_first != __fmt_last; ++__fmt_first)
+        {
+            if (*__fmt_first == '&')
+                __out = _VSTD::copy(__matches_[0].first, __matches_[0].second,
+                                   __out);
+            else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
+            {
+                ++__fmt_first;
+                if ('0' <= *__fmt_first && *__fmt_first <= '9')
+                {
+                    size_t __i = *__fmt_first - '0';
+                    __out = _VSTD::copy(__matches_[__i].first,
+                                       __matches_[__i].second, __out);
+                }
+                else
+                {
+                    *__out = *__fmt_first;
+                    ++__out;
+                }
+            }
+            else
+            {
+                *__out = *__fmt_first;
+                ++__out;
+            }
+        }
+    }
+    else
+    {
+        for (; __fmt_first != __fmt_last; ++__fmt_first)
+        {
+            if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
+            {
+                switch (__fmt_first[1])
+                {
+                case '$':
+                    *__out = *++__fmt_first;
+                    ++__out;
+                    break;
+                case '&':
+                    ++__fmt_first;
+                    __out = _VSTD::copy(__matches_[0].first, __matches_[0].second,
+                                       __out);
+                    break;
+                case '`':
+                    ++__fmt_first;
+                    __out = _VSTD::copy(__prefix_.first, __prefix_.second, __out);
+                    break;
+                case '\'':
+                    ++__fmt_first;
+                    __out = _VSTD::copy(__suffix_.first, __suffix_.second, __out);
+                    break;
+                default:
+                    if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
+                    {
+                        ++__fmt_first;
+                        size_t __i = *__fmt_first - '0';
+                        if (__fmt_first + 1 != __fmt_last &&
+                            '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
+                        {
+                            ++__fmt_first;
+                            __i = 10 * __i + *__fmt_first - '0';
+                        }
+                        __out = _VSTD::copy(__matches_[__i].first,
+                                           __matches_[__i].second, __out);
+                    }
+                    else
+                    {
+                        *__out = *__fmt_first;
+                        ++__out;
+                    }
+                    break;
+                }
+            }
+            else
+            {
+                *__out = *__fmt_first;
+                ++__out;
+            }
+        }
+    }
+    return __out;
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+void
+match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
+{
+    using _VSTD::swap;
+    swap(__matches_, __m.__matches_);
+    swap(__unmatched_, __m.__unmatched_);
+    swap(__prefix_, __m.__prefix_);
+    swap(__suffix_, __m.__suffix_);
+    swap(__position_start_, __m.__position_start_);
+    swap(__ready_, __m.__ready_);
+}
+
+typedef match_results<const char*>             cmatch;
+typedef match_results<const wchar_t*>          wcmatch;
+typedef match_results<string::const_iterator>  smatch;
+typedef match_results<wstring::const_iterator> wsmatch;
+
+template <class _BidirectionalIterator, class _Allocator>
+bool
+operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
+           const match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    if (__x.__ready_ != __y.__ready_)
+        return false;
+    if (!__x.__ready_)
+        return true;
+    return __x.__matches_ == __y.__matches_ &&
+           __x.__prefix_ == __y.__prefix_ &&
+           __x.__suffix_ == __y.__suffix_;
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
+           const match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    return !(__x == __y);
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+inline _LIBCPP_INLINE_VISIBILITY
+void
+swap(match_results<_BidirectionalIterator, _Allocator>& __x,
+     match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    __x.swap(__y);
+}
+
+// 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,
+        regex_constants::match_flag_type __flags, bool __at_first) const
+{
+    vector<__state> __states;
+    __node* __st = __start_.get();
+    if (__st)
+    {
+        __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());
+        __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_)
+                __s.__node_->__exec(__s);
+            switch (__s.__do_)
+            {
+            case __state::__end_state:
+                __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:
+            case __state::__accept_but_not_consume:
+                break;
+            case __state::__split:
+                {
+                __state __snext = __s;
+                __s.__node_->__exec_split(true, __s);
+                __snext.__node_->__exec_split(false, __snext);
+                __states.push_back(_VSTD::move(__snext));
+                }
+                break;
+            case __state::__reject:
+                __states.pop_back();
+                break;
+            default:
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                throw regex_error(regex_constants::__re_err_unknown);
+#endif
+                break;
+
+            }
+        } while (!__states.empty());
+    }
+    return false;
+}
+
+template <class _CharT, class _Traits>
+template <class _Allocator>
+bool
+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();
+    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());
+        __states.back().__node_ = __st;
+        __states.back().__flags_ = __flags;
+        __states.back().__at_first_ = __at_first;
+        bool __matched = false;
+        do
+        {
+            __state& __s = __states.back();
+            if (__s.__node_)
+                __s.__node_->__exec(__s);
+            switch (__s.__do_)
+            {
+            case __state::__end_state:
+                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;
+            case __state::__consume_input:
+                break;
+            case __state::__accept_and_consume:
+                __states.push_front(_VSTD::move(__s));
+                __states.pop_back();
+                break;
+            case __state::__repeat:
+            case __state::__accept_but_not_consume:
+                break;
+            case __state::__split:
+                {
+                __state __snext = __s;
+                __s.__node_->__exec_split(true, __s);
+                __snext.__node_->__exec_split(false, __snext);
+                __states.push_back(_VSTD::move(__snext));
+                }
+                break;
+            case __state::__reject:
+                __states.pop_back();
+                break;
+            default:
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                throw regex_error(regex_constants::__re_err_unknown);
+#endif
+                break;
+            }
+        } while (!__states.empty());
+        if (__matched)
+        {
+            __m.__matches_[0].first = __first;
+            __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
+            __m.__matches_[0].matched = true;
+            return true;
+        }
+    }
+    return false;
+}
+
+template <class _CharT, class _Traits>
+template <class _Allocator>
+bool
+basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
+        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;
+    __state __best_state;
+    ptrdiff_t __j = 0;
+    ptrdiff_t __highest_j = 0;
+    ptrdiff_t _Np = _VSTD::distance(__first, __last);
+    __node* __st = __start_.get();
+    if (__st)
+    {
+        __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());
+        __states.back().__loop_data_.resize(__loop_count());
+        __states.back().__node_ = __st;
+        __states.back().__flags_ = __flags;
+        __states.back().__at_first_ = __at_first;
+        const _CharT* __current = __first;
+        bool __matched = false;
+        do
+        {
+            __state& __s = __states.back();
+            if (__s.__node_)
+                __s.__node_->__exec(__s);
+            switch (__s.__do_)
+            {
+            case __state::__end_state:
+                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();
+                else
+                    __states.pop_back();
+                break;
+            case __state::__accept_and_consume:
+                __j += __s.__current_ - __current;
+                __current = __s.__current_;
+                break;
+            case __state::__repeat:
+            case __state::__accept_but_not_consume:
+                break;
+            case __state::__split:
+                {
+                __state __snext = __s;
+                __s.__node_->__exec_split(true, __s);
+                __snext.__node_->__exec_split(false, __snext);
+                __states.push_back(_VSTD::move(__snext));
+                }
+                break;
+            case __state::__reject:
+                __states.pop_back();
+                break;
+            default:
+#ifndef _LIBCPP_NO_EXCEPTIONS
+                throw regex_error(regex_constants::__re_err_unknown);
+#endif
+                break;
+            }
+        } while (!__states.empty());
+        if (__matched)
+        {
+            __m.__matches_[0].first = __first;
+            __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
+            __m.__matches_[0].matched = true;
+            for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
+                __m.__matches_[__i+1] = __best_state.__sub_matches_[__i];
+            return true;
+        }
+    }
+    return false;
+}
+
+template <class _CharT, class _Traits>
+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);
+    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
+basic_regex<_CharT, _Traits>::__search(
+        const _CharT* __first, const _CharT* __last,
+        match_results<const _CharT*, _Allocator>& __m,
+        regex_constants::match_flag_type __flags) const
+{
+    __m.__init(1 + mark_count(), __first, __last,
+                                    __flags & regex_constants::__no_update_pos);
+    if (__match_at_start(__first, __last, __m, __flags, 
+                                    !(__flags & regex_constants::__no_update_pos)))
+    {
+        __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 (__first != __last && !(__flags & regex_constants::match_continuous))
+    {
+        __flags |= regex_constants::match_prev_avail;
+        for (++__first; __first != __last; ++__first)
+        {
+            __m.__matches_.assign(__m.size(), __m.__unmatched_);
+            if (__match_at_start(__first, __last, __m, __flags, false))
+            {
+                __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;
+            }
+            __m.__matches_.assign(__m.size(), __m.__unmatched_);
+        }
+    }
+    __m.__matches_.clear();
+    return false;
+}
+
+template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(_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)
+{
+    int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
+    basic_string<_CharT> __s(_VSTD::prev(__first, __offset), __last);
+    match_results<const _CharT*> __mc;
+    bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
+    __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
+    return __r;
+}
+
+template <class _Iter, class _Allocator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(__wrap_iter<_Iter> __first,
+             __wrap_iter<_Iter> __last,
+             match_results<__wrap_iter<_Iter>, _Allocator>& __m,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<const _CharT*> __mc;
+    bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
+    __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
+    return __r;
+}
+
+template <class _Allocator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const _CharT* __first, const _CharT* __last,
+             match_results<const _CharT*, _Allocator>& __m,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return __e.__search(__first, __last, __m, __flags);
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    basic_string<_CharT> __s(__first, __last);
+    match_results<const _CharT*> __mc;
+    return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
+}
+
+template <class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const _CharT* __first, const _CharT* __last,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<const _CharT*> __mc;
+    return __e.__search(__first, __last, __mc, __flags);
+}
+
+template <class _CharT, class _Allocator, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
+}
+
+template <class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<const _CharT*> __m;
+    return _VSTD::regex_search(__str, __m, __e, __flags);
+}
+
+template <class _ST, class _SA, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const basic_string<_CharT, _ST, _SA>& __s,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<const _CharT*> __mc;
+    return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
+}
+
+template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_search(const basic_string<_CharT, _ST, _SA>& __s,
+             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
+             const basic_regex<_CharT, _Traits>& __e,
+             regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<const _CharT*> __mc;
+    bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
+    __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
+    return __r;
+}
+
+// regex_match
+
+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);
+    if (__r)
+    {
+        __r = !__m.suffix().matched;
+        if (!__r)
+            __m.__matches_.clear();
+    }
+    return __r;
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
+            const basic_regex<_CharT, _Traits>& __e,
+            regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    match_results<_BidirectionalIterator> __m;
+    return _VSTD::regex_match(__first, __last, __m, __e, __flags);
+}
+
+template <class _CharT, class _Allocator, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
+            const basic_regex<_CharT, _Traits>& __e,
+            regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return _VSTD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
+}
+
+template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_match(const basic_string<_CharT, _ST, _SA>& __s,
+            match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
+            const basic_regex<_CharT, _Traits>& __e,
+            regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return _VSTD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
+}
+
+template <class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
+            regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return _VSTD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
+}
+
+template <class _ST, class _SA, class _CharT, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+regex_match(const basic_string<_CharT, _ST, _SA>& __s,
+            const basic_regex<_CharT, _Traits>& __e,
+            regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return _VSTD::regex_match(__s.begin(), __s.end(), __e, __flags);
+}
+
+// regex_iterator
+
+template <class _BidirectionalIterator,
+          class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
+          class _Traits = regex_traits<_CharT> >
+class _LIBCPP_TYPE_VIS_ONLY regex_iterator
+{
+public:
+    typedef basic_regex<_CharT, _Traits>          regex_type;
+    typedef match_results<_BidirectionalIterator> value_type;
+    typedef ptrdiff_t                             difference_type;
+    typedef const value_type*                     pointer;
+    typedef const value_type&                     reference;
+    typedef forward_iterator_tag                  iterator_category;
+
+private:
+    _BidirectionalIterator           __begin_;
+    _BidirectionalIterator           __end_;
+    const regex_type*                __pregex_;
+    regex_constants::match_flag_type __flags_;
+    value_type                       __match_;
+
+public:
+    regex_iterator();
+    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                   const regex_type& __re,
+                   regex_constants::match_flag_type __m = regex_constants::match_default);
+
+    bool operator==(const regex_iterator& __x) const;
+    _LIBCPP_INLINE_VISIBILITY
+    bool operator!=(const regex_iterator& __x) const {return !(*this == __x);}
+
+    _LIBCPP_INLINE_VISIBILITY
+    reference operator*() const {return  __match_;}
+    _LIBCPP_INLINE_VISIBILITY
+    pointer operator->() const  {return &__match_;}
+
+    regex_iterator& operator++();
+    _LIBCPP_INLINE_VISIBILITY
+    regex_iterator operator++(int)
+    {
+        regex_iterator __t(*this);
+        ++(*this);
+        return __t;
+    }
+};
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
+    : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_()
+{
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                   const regex_type& __re, regex_constants::match_flag_type __m)
+    : __begin_(__a),
+      __end_(__b),
+      __pregex_(&__re),
+      __flags_(__m)
+{
+    _VSTD::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+bool
+regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    operator==(const regex_iterator& __x) const
+{
+    if (__match_.empty() && __x.__match_.empty())
+        return true;
+    if (__match_.empty() || __x.__match_.empty())
+        return false;
+    return __begin_ == __x.__begin_       &&
+           __end_ == __x.__end_           &&
+           __pregex_ == __x.__pregex_     &&
+           __flags_ == __x.__flags_       &&
+           __match_[0] == __x.__match_[0];
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
+regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
+{
+    __flags_ |= regex_constants::__no_update_pos;
+    _BidirectionalIterator __start = __match_[0].second;
+    if (__match_.empty())
+    {
+        if (__start == __end_)
+        {
+            __match_ = value_type();
+            return *this;
+        }
+        else if (_VSTD::regex_search(__start, __end_, __match_, *__pregex_,
+                                    __flags_ | regex_constants::match_not_null |
+                                    regex_constants::match_continuous))
+            return *this;
+        else
+            ++__start;
+    }
+    __flags_ |= regex_constants::match_prev_avail;
+    if (!_VSTD::regex_search(__start, __end_, __match_, *__pregex_, __flags_))
+        __match_ = value_type();
+    return *this;
+}
+
+typedef regex_iterator<const char*>             cregex_iterator;
+typedef regex_iterator<const wchar_t*>          wcregex_iterator;
+typedef regex_iterator<string::const_iterator>  sregex_iterator;
+typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
+
+// regex_token_iterator
+
+template <class _BidirectionalIterator,
+          class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
+          class _Traits = regex_traits<_CharT> >
+class _LIBCPP_TYPE_VIS_ONLY regex_token_iterator
+{
+public:
+    typedef basic_regex<_CharT, _Traits>      regex_type;
+    typedef sub_match<_BidirectionalIterator> value_type;
+    typedef ptrdiff_t                         difference_type;
+    typedef const value_type*                 pointer;
+    typedef const value_type&                 reference;
+    typedef forward_iterator_tag              iterator_category;
+
+private:
+    typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
+
+    _Position         __position_;
+    const value_type* __result_;
+    value_type        __suffix_;
+    ptrdiff_t         _N_;
+    vector<int>       __subs_;
+
+public:
+    regex_token_iterator();
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re, int __submatch = 0,
+                         regex_constants::match_flag_type __m =
+                                                regex_constants::match_default);
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re, const vector<int>& __submatches,
+                         regex_constants::match_flag_type __m =
+                                                regex_constants::match_default);
+#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re,
+                         initializer_list<int> __submatches,
+                         regex_constants::match_flag_type __m =
+                                                regex_constants::match_default);
+#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+    template <size_t _Np>
+        regex_token_iterator(_BidirectionalIterator __a,
+                             _BidirectionalIterator __b,
+                             const regex_type& __re,
+                             const int (&__submatches)[_Np],
+                             regex_constants::match_flag_type __m =
+                                                regex_constants::match_default);
+    regex_token_iterator(const regex_token_iterator&);
+    regex_token_iterator& operator=(const regex_token_iterator&);
+
+    bool operator==(const regex_token_iterator& __x) const;
+    _LIBCPP_INLINE_VISIBILITY
+    bool operator!=(const regex_token_iterator& __x) const {return !(*this == __x);}
+
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type& operator*() const {return *__result_;}
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type* operator->() const {return __result_;}
+
+    regex_token_iterator& operator++();
+    _LIBCPP_INLINE_VISIBILITY
+    regex_token_iterator operator++(int)
+    {
+        regex_token_iterator __t(*this);
+        ++(*this);
+        return __t;
+    }
+
+private:
+    void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
+};
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator()
+    : __result_(nullptr),
+      __suffix_(),
+      _N_(0)
+{
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+void
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    __init(_BidirectionalIterator __a, _BidirectionalIterator __b)
+{
+    if (__position_ != _Position())
+    {
+        if (__subs_[_N_] == -1)
+            __result_ = &__position_->prefix();
+        else
+            __result_ = &(*__position_)[__subs_[_N_]];
+    }
+    else if (__subs_[_N_] == -1)
+    {
+        __suffix_.matched = true;
+        __suffix_.first = __a;
+        __suffix_.second = __b;
+        __result_ = &__suffix_;
+    }
+    else
+        __result_ = nullptr;
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re, int __submatch,
+                         regex_constants::match_flag_type __m)
+    : __position_(__a, __b, __re, __m),
+      _N_(0),
+      __subs_(1, __submatch)
+{
+    __init(__a, __b);
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re, const vector<int>& __submatches,
+                         regex_constants::match_flag_type __m)
+    : __position_(__a, __b, __re, __m),
+      _N_(0),
+      __subs_(__submatches)
+{
+    __init(__a, __b);
+}
+
+#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                         const regex_type& __re,
+                         initializer_list<int> __submatches,
+                         regex_constants::match_flag_type __m)
+    : __position_(__a, __b, __re, __m),
+      _N_(0),
+      __subs_(__submatches)
+{
+    __init(__a, __b);
+}
+
+#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+template <size_t _Np>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
+                             const regex_type& __re,
+                             const int (&__submatches)[_Np],
+                             regex_constants::match_flag_type __m)
+    : __position_(__a, __b, __re, __m),
+      _N_(0),
+      __subs_(__submatches, __submatches + _Np)
+{
+    __init(__a, __b);
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    regex_token_iterator(const regex_token_iterator& __x)
+    : __position_(__x.__position_),
+      __result_(__x.__result_),
+      __suffix_(__x.__suffix_),
+      _N_(__x._N_),
+      __subs_(__x.__subs_)
+{
+    if (__x.__result_ == &__x.__suffix_)
+        __result_ == &__suffix_;
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    operator=(const regex_token_iterator& __x)
+{
+    if (this != &__x)
+    {
+        __position_ = __x.__position_;
+        if (__x.__result_ == &__x.__suffix_)
+            __result_ == &__suffix_;
+        else
+            __result_ = __x.__result_;
+        __suffix_ = __x.__suffix_;
+        _N_ = __x._N_;
+        __subs_ = __x.__subs_;
+    }
+    return *this;
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+bool
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
+    operator==(const regex_token_iterator& __x) const
+{
+    if (__result_ == nullptr && __x.__result_ == nullptr)
+        return true;
+    if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ &&
+            __suffix_ == __x.__suffix_)
+        return true;
+    if (__result_ == nullptr || __x.__result_ == nullptr)
+        return false;
+    if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
+        return false;
+    return __position_ == __x.__position_ && _N_ == __x._N_ &&
+           __subs_ == __x.__subs_;
+}
+
+template <class _BidirectionalIterator, class _CharT, class _Traits>
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
+regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
+{
+    _Position __prev = __position_;
+    if (__result_ == &__suffix_)
+        __result_ = nullptr;
+    else if (_N_ + 1 < __subs_.size())
+    {
+        ++_N_;
+        if (__subs_[_N_] == -1)
+            __result_ = &__position_->prefix();
+        else
+            __result_ = &(*__position_)[__subs_[_N_]];
+    }
+    else
+    {
+        _N_ = 0;
+        ++__position_;
+        if (__position_ != _Position())
+        {
+            if (__subs_[_N_] == -1)
+                __result_ = &__position_->prefix();
+            else
+                __result_ = &(*__position_)[__subs_[_N_]];
+        }
+        else
+        {
+            if (_VSTD::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end()
+                && __prev->suffix().length() != 0)
+            {
+                __suffix_.matched = true;
+                __suffix_.first = __prev->suffix().first;
+                __suffix_.second = __prev->suffix().second;
+                __result_ = &__suffix_;
+            }
+            else
+                __result_ = nullptr;
+        }
+    }
+    return *this;
+}
+
+typedef regex_token_iterator<const char*>             cregex_token_iterator;
+typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
+typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
+typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
+
+// regex_replace
+
+template <class _OutputIterator, class _BidirectionalIterator,
+          class _Traits, class _CharT>
+_OutputIterator
+regex_replace(_OutputIterator __out,
+              _BidirectionalIterator __first, _BidirectionalIterator __last,
+              const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
+    _Iter __i(__first, __last, __e, __flags);
+    _Iter __eof;
+    if (__i == __eof)
+    {
+        if (!(__flags & regex_constants::format_no_copy))
+            __out = _VSTD::copy(__first, __last, __out);
+    }
+    else
+    {
+        sub_match<_BidirectionalIterator> __lm;
+        for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i)
+        {
+            if (!(__flags & regex_constants::format_no_copy))
+                __out = _VSTD::copy(__i->prefix().first, __i->prefix().second, __out);
+            __out = __i->format(__out, __fmt, __fmt + __len, __flags);
+            __lm = __i->suffix();
+            if (__flags & regex_constants::format_first_only)
+                break;
+        }
+        if (!(__flags & regex_constants::format_no_copy))
+            __out = _VSTD::copy(__lm.first, __lm.second, __out);
+    }
+    return __out;
+}
+
+template <class _OutputIterator, class _BidirectionalIterator,
+          class _Traits, class _CharT, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+_OutputIterator
+regex_replace(_OutputIterator __out,
+              _BidirectionalIterator __first, _BidirectionalIterator __last,
+              const basic_regex<_CharT, _Traits>& __e,
+              const basic_string<_CharT, _ST, _SA>& __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    return _VSTD::regex_replace(__out, __first, __last, __e, __fmt.c_str(), __flags);
+}
+
+template <class _Traits, class _CharT, class _ST, class _SA, class _FST,
+          class _FSA>
+inline _LIBCPP_INLINE_VISIBILITY
+basic_string<_CharT, _ST, _SA>
+regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
+              const basic_regex<_CharT, _Traits>& __e,
+              const basic_string<_CharT, _FST, _FSA>& __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    basic_string<_CharT, _ST, _SA> __r;
+    _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
+                        __fmt.c_str(), __flags);
+    return __r;
+}
+
+template <class _Traits, class _CharT, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+basic_string<_CharT, _ST, _SA>
+regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
+              const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    basic_string<_CharT, _ST, _SA> __r;
+    _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
+                        __fmt, __flags);
+    return __r;
+}
+
+template <class _Traits, class _CharT, class _ST, class _SA>
+inline _LIBCPP_INLINE_VISIBILITY
+basic_string<_CharT>
+regex_replace(const _CharT* __s,
+              const basic_regex<_CharT, _Traits>& __e,
+              const basic_string<_CharT, _ST, _SA>& __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    basic_string<_CharT> __r;
+    _VSTD::regex_replace(back_inserter(__r), __s,
+                        __s + char_traits<_CharT>::length(__s), __e,
+                        __fmt.c_str(), __flags);
+    return __r;
+}
+
+template <class _Traits, class _CharT>
+inline _LIBCPP_INLINE_VISIBILITY
+basic_string<_CharT>
+regex_replace(const _CharT* __s,
+              const basic_regex<_CharT, _Traits>& __e,
+              const _CharT* __fmt,
+              regex_constants::match_flag_type __flags = regex_constants::match_default)
+{
+    basic_string<_CharT> __r;
+    _VSTD::regex_replace(back_inserter(__r), __s,
+                        __s + char_traits<_CharT>::length(__s), __e,
+                        __fmt, __flags);
+    return __r;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif  // _LIBCPP_REGEX