// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_REGEX
#define _LIBCPP_REGEX

/*
    regex synopsis

#include <compare>
#include <initializer_list>

namespace std
{

namespace regex_constants
{

enum syntax_option_type
{
    icase      = unspecified,
    nosubs     = unspecified,
    optimize   = unspecified,
    collate    = unspecified,
    ECMAScript = unspecified,
    basic      = unspecified,
    extended   = unspecified,
    awk        = unspecified,
    grep       = unspecified,
    egrep      = unspecified,
    multiline  = 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 traits                              traits_type;
    typedef typename traits::string_type        string_type;
    typedef regex_constants::syntax_option_type flag_type;
    typedef typename traits::locale_type        locale_type;

    // 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;
    static constexpr regex_constants::syntax_option_type multiline = regex_constants::multiline;

    // 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 = regex_constants::ECMAScript);
    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 = regex_constants::ECMAScript);
    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 f = 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&);
};

template<class ForwardIterator>
basic_regex(ForwardIterator, ForwardIterator,
            regex_constants::syntax_option_type = regex_constants::ECMAScript)
    -> basic_regex<typename iterator_traits<ForwardIterator>::value_type>; // C++17

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;

    void swap(sub_match& s) noexcept(see below);
};

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>
    auto
    operator<=>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs); // Since C++20

 template <class BiIter>                                                     // Removed in C++20
    bool
    operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Since C++20
    auto
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    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>                                  // Removed in C++20
    bool
    operator<=(const sub_match<BiIter>& lhs,
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator==(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<(typename iterator_traits<BiIter>::value_type const* lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>(typename iterator_traits<BiIter>::value_type const* lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    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>                                                      // Since C++20
    auto
    operator<=>(const sub_match<BiIter>& lhs,
                typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter, class ST, class SA>                                  // Removed in C++20
    bool
    operator!=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator==(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<(typename iterator_traits<BiIter>::value_type const& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>(typename iterator_traits<BiIter>::value_type const& lhs,
              const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
               const sub_match<BiIter>& rhs);

template <class BiIter>                                                      // Removed in C++20
    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>                                                      // Since C++20
    auto
    operator<=>(const sub_match<BiIter>& lhs,
                typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator!=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator<(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>(const sub_match<BiIter>& lhs,
              typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>                                                      // Removed in C++20
    bool
    operator>=(const sub_match<BiIter>& lhs,
               typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>                                                      // Removed in C++20
    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 value_type&                                       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()); // before C++20
    match_results() : match_results(Allocator()) {}           // C++20
    explicit match_results(const Allocator& a);               // C++20
    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>                    // Removed in C++20
    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 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) = delete; // C++14

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 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) = delete; // C++14

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;
    typedef input_iterator_tag                   iterator_concept; // since C++20

    regex_iterator();
    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
                   const regex_type& re,
                   regex_constants::match_flag_type m = regex_constants::match_default);
    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
                   const regex_type&& re,
                   regex_constants::match_flag_type m
                                     = regex_constants::match_default) = delete; // C++14
    regex_iterator(const regex_iterator&);
    regex_iterator& operator=(const regex_iterator&);

    bool operator==(const regex_iterator&) const;
    bool operator==(default_sentinel_t) const { return *this == regex_iterator(); } // since C++20
    bool operator!=(const regex_iterator&) const;                                   // Removed in C++20

    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;
    typedef input_iterator_tag               iterator_concept; // since C++20

    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, int submatch = 0,
                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
    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, const vector<int>& submatches,
                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
    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);
    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) = delete; // C++14
    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);
    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) = delete; // C++14
    regex_token_iterator(const regex_token_iterator&);
    regex_token_iterator& operator=(const regex_token_iterator&);

    bool operator==(const regex_token_iterator&) const;
    bool operator==(default_sentinel_t) const { return *this == regex_token_iterator(); } // since C++20
    bool operator!=(const regex_token_iterator&) const;                                   // Removed in C++20

    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 <__algorithm/find.h>
#include <__algorithm/search.h>
#include <__assert> // all public C++ headers provide the assertion handler
#include <__availability>
#include <__config>
#include <__iterator/back_insert_iterator.h>
#include <__iterator/default_sentinel.h>
#include <__iterator/wrap_iter.h>
#include <__locale>
#include <__memory/shared_ptr.h>
#include <__memory_resource/polymorphic_allocator.h>
#include <__type_traits/is_swappable.h>
#include <__utility/move.h>
#include <__utility/pair.h>
#include <__utility/swap.h>
#include <__verbose_abort>
#include <deque>
#include <stdexcept>
#include <string>
#include <vector>
#include <version>

// standard-mandated includes

// [iterator.range]
#include <__iterator/access.h>
#include <__iterator/data.h>
#include <__iterator/empty.h>
#include <__iterator/reverse_access.h>
#include <__iterator/size.h>

// [re.syn]
#include <compare>
#include <initializer_list>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

#define _LIBCPP_REGEX_COMPLEXITY_FACTOR 4096

_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,
#ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO
  ECMAScript = 1 << 9,
#else
  ECMAScript = 0,
#endif
  basic    = 1 << 4,
  extended = 1 << 5,
  awk      = 1 << 6,
  grep     = 1 << 7,
  egrep    = 1 << 8,
  // 1 << 9 may be used by ECMAScript
  multiline = 1 << 10
};

_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR syntax_option_type __get_grammar(syntax_option_type __g) {
#ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO
  return static_cast<syntax_option_type>(__g & 0x3F0);
#else
  return static_cast<syntax_option_type>(__g & 0x1F0);
#endif
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type operator~(syntax_option_type __x) {
  return syntax_option_type(~int(__x) & 0x1FF);
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
operator&(syntax_option_type __x, syntax_option_type __y) {
  return syntax_option_type(int(__x) & int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
operator|(syntax_option_type __x, syntax_option_type __y) {
  return syntax_option_type(int(__x) | int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
operator^(syntax_option_type __x, syntax_option_type __y) {
  return syntax_option_type(int(__x) ^ int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator&=(syntax_option_type& __x, syntax_option_type __y) {
  __x = __x & __y;
  return __x;
}

inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator|=(syntax_option_type& __x, syntax_option_type __y) {
  __x = __x | __y;
  return __x;
}

inline _LIBCPP_HIDE_FROM_ABI 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,
  __full_match      = 1 << 12
};

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator~(match_flag_type __x) {
  return match_flag_type(~int(__x) & 0x0FFF);
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator&(match_flag_type __x, match_flag_type __y) {
  return match_flag_type(int(__x) & int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator|(match_flag_type __x, match_flag_type __y) {
  return match_flag_type(int(__x) | int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator^(match_flag_type __x, match_flag_type __y) {
  return match_flag_type(int(__x) ^ int(__y));
}

inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator&=(match_flag_type& __x, match_flag_type __y) {
  __x = __x & __y;
  return __x;
}

inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator|=(match_flag_type& __x, match_flag_type __y) {
  __x = __x | __y;
  return __x;
}

inline _LIBCPP_HIDE_FROM_ABI 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,
  __re_err_parse
};

} // namespace regex_constants

class _LIBCPP_EXPORTED_FROM_ABI regex_error : public runtime_error {
  regex_constants::error_type __code_;

public:
  explicit regex_error(regex_constants::error_type __ecode);
  _LIBCPP_HIDE_FROM_ABI regex_error(const regex_error&) _NOEXCEPT = default;
  ~regex_error() _NOEXCEPT override;
  _LIBCPP_HIDE_FROM_ABI regex_constants::error_type code() const { return __code_; }
};

template <regex_constants::error_type _Ev>
_LIBCPP_NORETURN inline _LIBCPP_HIDE_FROM_ABI void __throw_regex_error() {
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
  throw regex_error(_Ev);
#else
  _LIBCPP_VERBOSE_ABORT("regex_error was thrown in -fno-exceptions mode");
#endif
}

template <class _CharT>
struct _LIBCPP_TEMPLATE_VIS regex_traits {
public:
  typedef _CharT char_type;
  typedef basic_string<char_type> string_type;
  typedef locale locale_type;
#if defined(__BIONIC__) || defined(_NEWLIB_VERSION)
  // Originally bionic's ctype_base used its own ctype masks because the
  // builtin ctype implementation wasn't in libc++ yet. Bionic's ctype mask
  // was only 8 bits wide and already saturated, so it used a wider type here
  // to make room for __regex_word (then a part of this class rather than
  // ctype_base). Bionic has since moved to the builtin ctype_base
  // implementation, but this was not updated to match. Since then Android has
  // needed to maintain a stable libc++ ABI, and this can't be changed without
  // an ABI break.
  // We also need this workaround for newlib since _NEWLIB_VERSION is not
  // defined yet inside __config, so we can't set the
  // _LIBCPP_PROVIDES_DEFAULT_RUNE_TABLE macro. Additionally, newlib is
  // often used for space constrained environments, so it makes sense not to
  // duplicate the ctype table.
  typedef uint16_t char_class_type;
#else
  typedef ctype_base::mask char_class_type;
#endif

  static const char_class_type __regex_word = ctype_base::__regex_word;

private:
  locale __loc_;
  const ctype<char_type>* __ct_;
  const collate<char_type>* __col_;

public:
  regex_traits();

  _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __p) { return char_traits<char_type>::length(__p); }
  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI string_type transform_primary(_ForwardIterator __f, _ForwardIterator __l) const {
    return __transform_primary(__f, __l, char_type());
  }
  template <class _ForwardIterator>
  _LIBCPP_HIDE_FROM_ABI string_type lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const {
    return __lookup_collatename(__f, __l, char_type());
  }
  template <class _ForwardIterator>
  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI int value(char_type __ch, int __radix) const { return __regex_traits_value(__ch, __radix); }
  locale_type imbue(locale_type __l);
  _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __loc_; }

private:
  void __init();

  template <class _ForwardIterator>
  string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  template <class _ForwardIterator>
  string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
#endif
  template <class _ForwardIterator>
  string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  template <class _ForwardIterator>
  string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
#endif
  template <class _ForwardIterator>
  char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, char) const;
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  template <class _ForwardIterator>
  char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, wchar_t) const;
#endif

  static int __regex_traits_value(unsigned char __ch, int __radix);
  _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(char __ch, int __radix) const {
    return __regex_traits_value(static_cast<unsigned char>(__ch), __radix);
  }
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(wchar_t __ch, int __radix) const;
#endif
};

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_  = &std::use_facet<ctype<char_type> >(__loc_);
  __col_ = &std::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;
}

#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
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;
}
#endif

// lookup_collatename is very FreeBSD-specific

_LIBCPP_EXPORTED_FROM_ABI 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 = std::__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;
}

#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
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;
}
#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS

// lookup_classname

regex_traits<char>::char_class_type _LIBCPP_EXPORTED_FROM_ABI __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 std::__get_classname(__s.c_str(), __icase);
}

#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
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);
}
#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS

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));
}

inline _LIBCPP_HIDE_FROM_ABI bool __is_07(unsigned char __c) {
  return (__c & 0xF8u) ==
#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
         0xF0;
#else
         0x30;
#endif
}

inline _LIBCPP_HIDE_FROM_ABI bool __is_89(unsigned char __c) {
  return (__c & 0xFEu) ==
#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
         0xF8;
#else
         0x38;
#endif
}

inline _LIBCPP_HIDE_FROM_ABI unsigned char __to_lower(unsigned char __c) {
#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
  return __c & 0xBF;
#else
  return __c | 0x20;
#endif
}

template <class _CharT>
int regex_traits<_CharT>::__regex_traits_value(unsigned char __ch, int __radix) {
  if (__is_07(__ch)) // '0' <= __ch && __ch <= '7'
    return __ch - '0';
  if (__radix != 8) {
    if (__is_89(__ch)) // '8' <= __ch && __ch <= '9'
      return __ch - '0';
    if (__radix == 16) {
      __ch = __to_lower(__ch); // tolower
      if ('a' <= __ch && __ch <= 'f')
        return __ch - ('a' - 10);
    }
  }
  return -1;
}

#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
template <class _CharT>
inline 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);
}
#endif

template <class _CharT>
class __node;

template <class _BidirectionalIterator>
class _LIBCPP_TEMPLATE_VIS sub_match;

template <class _BidirectionalIterator, class _Allocator = allocator<sub_match<_BidirectionalIterator> > >
class _LIBCPP_TEMPLATE_VIS 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_HIDE_FROM_ABI __state()
      : __do_(0),
        __first_(nullptr),
        __current_(nullptr),
        __last_(nullptr),
        __node_(nullptr),
        __flags_(),
        __at_first_(false) {}
};

// __node

template <class _CharT>
class __node {
  __node(const __node&);
  __node& operator=(const __node&);

public:
  typedef std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __node() {}
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL
  virtual ~__node() {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL
  virtual void __exec(__state&) const {}
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL
  virtual void __exec_split(bool, __state&) const {}
};

// __end_state

template <class _CharT>
class __end_state : public __node<_CharT> {
public:
  typedef std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __end_state() {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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_HIDE_FROM_ABI explicit __has_one_state(__node<_CharT>* __s) : __first_(__s) {}

  _LIBCPP_HIDE_FROM_ABI __node<_CharT>* first() const { return __first_; }
  _LIBCPP_HIDE_FROM_ABI __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_HIDE_FROM_ABI explicit __owns_one_state(__node<_CharT>* __s) : base(__s) {}

  ~__owns_one_state() override;
};

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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __empty_state(__node<_CharT>* __s) : base(__s) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __empty_non_own_state(__node<_CharT>* __s) : base(__s) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __repeat_one_loop(__node<_CharT>* __s) : base(__s) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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_HIDE_FROM_ABI explicit __owns_two_states(__node<_CharT>* __s1, base* __s2) : base(__s1), __second_(__s2) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual ~__owns_two_states();

  _LIBCPP_HIDE_FROM_ABI base* second() const { return __second_; }
  _LIBCPP_HIDE_FROM_ABI 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI 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) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec_split(bool __second, __state& __s) const;

private:
  _LIBCPP_HIDE_FROM_ABI 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __alternate(__owns_one_state<_CharT>* __s1, __owns_one_state<_CharT>* __s2)
      : base(__s1, __s2) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __begin_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
      : base(__s), __mexp_(__mexp) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __end_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
      : base(__s), __mexp_(__mexp) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __back_ref(unsigned __mexp, __node<_CharT>* __s) : base(__s), __mexp_(__mexp) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
};

template <class _CharT>
void __back_ref<_CharT>::__exec(__state& __s) const {
  if (__mexp_ > __s.__sub_matches_.size())
    __throw_regex_error<regex_constants::error_backref>();
  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 && std::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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __back_ref_icase(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)
      : base(__s), __traits_(__traits), __mexp_(__mexp) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __back_ref_collate(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)
      : base(__s), __traits_(__traits), __mexp_(__mexp) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI explicit __word_boundary(const _Traits& __traits, bool __invert, __node<_CharT>* __s)
      : base(__s), __traits_(__traits), __invert_(__invert) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool __is_eol(_CharT __c) {
  return __c == '\r' || __c == '\n';
}

template <class _CharT>
class __l_anchor_multiline : public __owns_one_state<_CharT> {
  typedef __owns_one_state<_CharT> base;

  bool __multiline_;

public:
  typedef std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __l_anchor_multiline(bool __multiline, __node<_CharT>* __s)
      : base(__s), __multiline_(__multiline) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
};

template <class _CharT>
void __l_anchor_multiline<_CharT>::__exec(__state& __s) const {
  if (__s.__at_first_ && __s.__current_ == __s.__first_ && !(__s.__flags_ & regex_constants::match_not_bol)) {
    __s.__do_   = __state::__accept_but_not_consume;
    __s.__node_ = this->first();
  } else if (__multiline_ && !__s.__at_first_ && std::__is_eol(*std::prev(__s.__current_))) {
    __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_multiline : public __owns_one_state<_CharT> {
  typedef __owns_one_state<_CharT> base;

  bool __multiline_;

public:
  typedef std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __r_anchor_multiline(bool __multiline, __node<_CharT>* __s)
      : base(__s), __multiline_(__multiline) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
};

template <class _CharT>
void __r_anchor_multiline<_CharT>::__exec(__state& __s) const {
  if (__s.__current_ == __s.__last_ && !(__s.__flags_ & regex_constants::match_not_eol)) {
    __s.__do_   = __state::__accept_but_not_consume;
    __s.__node_ = this->first();
  } else if (__multiline_ && std::__is_eol(*__s.__current_)) {
    __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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __match_any(__node<_CharT>* __s) : base(__s) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __match_any_but_newline(__node<_CharT>* __s) : base(__s) {}

  void __exec(__state&) const override;
};

template <>
_LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<char>::__exec(__state&) const;
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
template <>
_LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<wchar_t>::__exec(__state&) const;
#endif

// __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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __match_char(_CharT __c, __node<_CharT>* __s) : base(__s), __c_(__c) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __match_char_icase(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
      : base(__s), __traits_(__traits), __c_(__traits.translate_nocase(__c)) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI __match_char_collate(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
      : base(__s), __traits_(__traits), __c_(__traits.translate(__c)) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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_;
  typename regex_traits<_CharT>::char_class_type __mask_;
  typename regex_traits<_CharT>::char_class_type __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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI
  __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") {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;

  _LIBCPP_HIDE_FROM_ABI bool __negated() const { return __negate_; }

  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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(
          std::make_pair(__traits_.transform(__b.begin(), __b.end()), __traits_.transform(__e.begin(), __e.end())));
    } else {
      if (__b.size() != 1 || __e.size() != 1)
        __throw_regex_error<regex_constants::error_range>();
      if (__icase_) {
        __b[0] = __traits_.translate_nocase(__b[0]);
        __e[0] = __traits_.translate_nocase(__e[0]);
      }
      __ranges_.push_back(std::make_pair(std::move(__b), std::move(__e)));
    }
  }
  _LIBCPP_HIDE_FROM_ABI void __add_digraph(_CharT __c1, _CharT __c2) {
    if (__icase_)
      __digraphs_.push_back(std::make_pair(__traits_.translate_nocase(__c1), __traits_.translate_nocase(__c2)));
    else if (__collate_)
      __digraphs_.push_back(std::make_pair(__traits_.translate(__c1), __traits_.translate(__c2)));
    else
      __digraphs_.push_back(std::make_pair(__c1, __c2));
  }
  _LIBCPP_HIDE_FROM_ABI void __add_equivalence(const string_type& __s) { __equivalences_.push_back(__s); }
  _LIBCPP_HIDE_FROM_ABI void __add_class(typename regex_traits<_CharT>::char_class_type __mask) { __mask_ |= __mask; }
  _LIBCPP_HIDE_FROM_ABI void __add_neg_class(typename regex_traits<_CharT>::char_class_type __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 = std::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;
      }
    }
    // When there's at least one of __neg_chars_ and __neg_mask_, the set
    // of "__found" chars is
    //   union(complement(union(__neg_chars_, __neg_mask_)),
    //         other cases...)
    //
    // It doesn't make sense to check this when there are no __neg_chars_
    // and no __neg_mask_.
    if (!(__neg_mask_ == 0 && __neg_chars_.empty())) {
      const bool __in_neg_mask  = __traits_.isctype(__ch, __neg_mask_);
      const bool __in_neg_chars = std::find(__neg_chars_.begin(), __neg_chars_.end(), __ch) != __neg_chars_.end();
      if (!(__in_neg_mask || __in_neg_chars)) {
        __found = true;
        goto __exit;
      }
    }
    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;
    }
  } 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_TEMPLATE_VIS basic_regex;

typedef basic_regex<char> regex;
#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
typedef basic_regex<wchar_t> wregex;
#endif

template <class _CharT, class _Traits>
class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(regex)
    _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wregex)) basic_regex {
public:
  // types:
  typedef _CharT value_type;
  typedef _Traits traits_type;
  typedef typename _Traits::string_type string_type;
  typedef regex_constants::syntax_option_type flag_type;
  typedef typename _Traits::locale_type locale_type;

private:
  _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 std::__state<_CharT> __state;
  typedef std::__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;
  static const regex_constants::syntax_option_type multiline  = regex_constants::multiline;

  // construct/copy/destroy:
  _LIBCPP_HIDE_FROM_ABI basic_regex()
      : __flags_(regex_constants::ECMAScript),
        __marked_count_(0),
        __loop_count_(0),
        __open_count_(0),
        __end_(nullptr) {}
  _LIBCPP_HIDE_FROM_ABI 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_(nullptr) {
    __init(__p, __p + __traits_.length(__p));
  }

  _LIBCPP_HIDE_FROM_ABI basic_regex(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript)
      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
    __init(__p, __p + __len);
  }

  //     basic_regex(const basic_regex&) = default;
  //     basic_regex(basic_regex&&) = default;
  template <class _ST, class _SA>
  _LIBCPP_HIDE_FROM_ABI 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_(nullptr) {
    __init(__p.begin(), __p.end());
  }

  template <class _ForwardIterator>
  _LIBCPP_HIDE_FROM_ABI
  basic_regex(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript)
      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
    __init(__first, __last);
  }
#ifndef _LIBCPP_CXX03_LANG
  _LIBCPP_HIDE_FROM_ABI 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_(nullptr) {
    __init(__il.begin(), __il.end());
  }
#endif // _LIBCPP_CXX03_LANG

  //    ~basic_regex() = default;

  //     basic_regex& operator=(const basic_regex&) = default;
  //     basic_regex& operator=(basic_regex&&) = default;
  _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const value_type* __p) { return assign(__p); }
#ifndef _LIBCPP_CXX03_LANG
  _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(initializer_list<value_type> __il) { return assign(__il); }
#endif // _LIBCPP_CXX03_LANG
  template <class _ST, class _SA>
  _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p) {
    return assign(__p);
  }

  // assign:
  _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const basic_regex& __that) { return *this = __that; }
#ifndef _LIBCPP_CXX03_LANG
  _LIBCPP_HIDE_FROM_ABI basic_regex& assign(basic_regex&& __that) _NOEXCEPT { return *this = std::move(__that); }
#endif
  _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript) {
    return assign(__p, __p + __traits_.length(__p), __f);
  }
  _LIBCPP_HIDE_FROM_ABI basic_regex&
  assign(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript) {
    return assign(__p, __p + __len, __f);
  }
  template <class _ST, class _SA>
  _LIBCPP_HIDE_FROM_ABI 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, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
  _LIBCPP_HIDE_FROM_ABI basic_regex&
  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_HIDE_FROM_ABI void __member_init(flag_type __f) {
    __flags_        = __f;
    __marked_count_ = 0;
    __loop_count_   = 0;
    __open_count_   = 0;
    __end_          = nullptr;
  }

public:
  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
  _LIBCPP_HIDE_FROM_ABI basic_regex&
  assign(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript) {
    return assign(basic_regex(__first, __last, __f));
  }

#ifndef _LIBCPP_CXX03_LANG

  _LIBCPP_HIDE_FROM_ABI basic_regex&
  assign(initializer_list<value_type> __il, flag_type __f = regex_constants::ECMAScript) {
    return assign(__il.begin(), __il.end(), __f);
  }

#endif // _LIBCPP_CXX03_LANG

  // const operations:
  _LIBCPP_HIDE_FROM_ABI unsigned mark_count() const { return __marked_count_; }
  _LIBCPP_HIDE_FROM_ABI flag_type flags() const { return __flags_; }

  // locale:
  _LIBCPP_HIDE_FROM_ABI locale_type imbue(locale_type __loc) {
    __member_init(ECMAScript);
    __start_.reset();
    return __traits_.imbue(__loc);
  }
  _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __traits_.getloc(); }

  // swap:
  void swap(basic_regex& __r);

private:
  _LIBCPP_HIDE_FROM_ABI unsigned __loop_count() const { return __loop_count_; }

  _LIBCPP_HIDE_FROM_ABI bool __use_multiline() const {
    return __get_grammar(__flags_) == ECMAScript && (__flags_ & multiline);
  }

  template <class _ForwardIterator>
  void __init(_ForwardIterator __first, _ForwardIterator __last);
  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);

  bool __test_back_ref(_CharT);

  _LIBCPP_HIDE_FROM_ABI void __push_l_anchor();
  void __push_r_anchor();
  void __push_match_any();
  void __push_match_any_but_newline();
  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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;
};

#if _LIBCPP_STD_VER >= 17
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
basic_regex(_ForwardIterator, _ForwardIterator, regex_constants::syntax_option_type = regex_constants::ECMAScript)
    -> basic_regex<typename iterator_traits<_ForwardIterator>::value_type>;
#endif

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 std::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_HIDE_FROM_ABI 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 std::__state<_CharT> __state;

  _LIBCPP_HIDE_FROM_ABI
  __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
      : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}

  _LIBCPP_HIDE_FROM_ABI_VIRTUAL 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) & ~regex_constants::__full_match,
      __s.__at_first_ && __s.__current_ == __s.__first_);
  if (__matched != __invert_) {
    __s.__do_   = __state::__accept_but_not_consume;
    __s.__node_ = this->first();
    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>
void basic_regex<_CharT, _Traits>::__init(_ForwardIterator __first, _ForwardIterator __last) {
  if (__get_grammar(__flags_) == 0)
    __flags_ |= regex_constants::ECMAScript;
  _ForwardIterator __temp = __parse(__first, __last);
  if (__temp != __last)
    __throw_regex_error<regex_constants::__re_err_parse>();
}

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 (__get_grammar(__flags_)) {
  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;
  default:
    __throw_regex_error<regex_constants::__re_err_grammar>();
  }
  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 = std::next(__first);
        if (__temp == __last && *__first == '$') {
          __push_r_anchor();
          ++__first;
        }
      }
    }
    if (__first != __last)
      __throw_regex_error<regex_constants::__re_err_empty>();
  }
  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);
  if (__temp == __first)
    __throw_regex_error<regex_constants::__re_err_empty>();
  __first = __temp;
  while (__first != __last && *__first == '|') {
    __owns_one_state<_CharT>* __sb = __end_;
    __temp                         = __parse_ERE_branch(++__first, __last);
    if (__temp == __first)
      __throw_regex_error<regex_constants::__re_err_empty>();
    __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);
  if (__temp == __first)
    __throw_regex_error<regex_constants::__re_err_empty>();
  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);
      if (__temp == __last || *__temp != ')')
        __throw_regex_error<regex_constants::error_paren>();
      __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);
      if (__temp == __first)
        __throw_regex_error<regex_constants::error_paren>();
      __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 = std::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 = std::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 = std::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 = std::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 = std::next(__first);
    if (__temp != __last && *__first == '\\' && __test_back_ref(*__temp))
      __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 = std::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 = std::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 = std::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 (__get_grammar(__flags_) == awk)
            __first = __parse_awk_escape(++__first, __last);
          else if (__test_back_ref(*__temp))
            __first = ++__temp;
          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);
        if (__temp == __first)
          __throw_regex_error<regex_constants::error_badbrace>();
        __first = __temp;
        if (__first == __last)
          __throw_regex_error<regex_constants::error_brace>();
        if (*__first != ',') {
          __temp = __parse_Back_close_brace(__first, __last);
          if (__temp == __first)
            __throw_regex_error<regex_constants::error_brace>();
          __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);
          if (__temp == __first)
            __throw_regex_error<regex_constants::error_brace>();
          if (__max == -1)
            __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
          else {
            if (__max < __min)
              __throw_regex_error<regex_constants::error_badbrace>();
            __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 = __get_grammar(__flags_);
    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);
      if (__temp == __first)
        __throw_regex_error<regex_constants::error_badbrace>();
      __first = __temp;
      if (__first == __last)
        __throw_regex_error<regex_constants::error_brace>();
      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;
        if (__first == __last)
          __throw_regex_error<regex_constants::error_badbrace>();
        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);
          if (__temp == __first)
            __throw_regex_error<regex_constants::error_brace>();
          __first = __temp;
          if (__first == __last || *__first != '}')
            __throw_regex_error<regex_constants::error_brace>();
          ++__first;
          if (__max < __min)
            __throw_regex_error<regex_constants::error_badbrace>();
          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;
      default:
        __throw_regex_error<regex_constants::error_badbrace>();
      }
    } 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;
    if (__first == __last)
      __throw_regex_error<regex_constants::error_brack>();
    bool __negate = false;
    if (*__first == '^') {
      ++__first;
      __negate = true;
    }
    __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
    // __ml owned by *this
    if (__first == __last)
      __throw_regex_error<regex_constants::error_brack>();
    if (__get_grammar(__flags_) != ECMAScript && *__first == ']') {
      __ml->__add_char(']');
      ++__first;
    }
    __first = __parse_follow_list(__first, __last, __ml);
    if (__first == __last)
      __throw_regex_error<regex_constants::error_brack>();
    if (*__first == '-') {
      __ml->__add_char('-');
      ++__first;
    }
    if (__first == __last || *__first != ']')
      __throw_regex_error<regex_constants::error_brack>();
    ++__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 = std::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 = __get_grammar(__flags_);
    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 = std::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(std::move(__start_range), std::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) {
  if (__first == __last)
    __throw_regex_error<regex_constants::error_escape>();
  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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 