// regex standard header

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#ifndef _REGEX_
#define _REGEX_
#include <yvals_core.h>
#if _STL_COMPILER_PREPROCESSOR

#include <algorithm>
#include <cctype>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cwchar>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#if _HAS_CXX17
#include <xpolymorphic_allocator.h>
#endif // _HAS_CXX17

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new

// Controls whether LWG-2503 "multiline option should be added to syntax_option_type" is implemented.
// Defining this to 0 requests Standard behavior:
// * For ECMAScript, matching is non-multiline by default, but regex_constants::multiline can be requested.
// * For POSIX grammars, matching is non-multiline, and regex_constants::multiline is ignored (N5008 [tab:re.synopt]).
// Defining this to 1 requests legacy behavior:
// * For all grammars, matching is multiline, and regex_constants::multiline is redundant.
#ifndef _REGEX_LEGACY_MULTILINE_MODE
#define _REGEX_LEGACY_MULTILINE_MODE 0
#endif

#ifndef _ENHANCED_REGEX_VISUALIZER
#ifdef _DEBUG
#define _ENHANCED_REGEX_VISUALIZER 1
#else // ^^^ defined(_DEBUG) / !defined(_DEBUG) vvv
#define _ENHANCED_REGEX_VISUALIZER 0
#endif // ^^^ !defined(_DEBUG) ^^^
#endif // !defined(_ENHANCED_REGEX_VISUALIZER)

#if defined(_CPPRTTI) && !defined(_M_CEE_PURE)
extern "C" {
_STD size_t __stdcall __std_regex_transform_primary_char(
    _Out_writes_(_Last1 - _First1) _Post_readable_size_(return) char* _First1, char* _Last1,
    _In_reads_(_Last2 - _First2) const char* _First2, const char* _Last2, _In_opt_ const _Collvec*) noexcept;
_STD size_t __stdcall __std_regex_transform_primary_wchar_t(
    _Out_writes_(_Last1 - _First1) _Post_readable_size_(return) wchar_t* _First1, wchar_t* _Last1,
    _In_reads_(_Last2 - _First2) const wchar_t* _First2, const wchar_t* _Last2, _In_opt_ const _Collvec*) noexcept;
} // extern "C"
#endif // ^^^ defined(_CPPRTTI) && !defined(_M_CEE_PURE) ^^^

_STD_BEGIN

enum _Meta_type : int { // meta character representations for parser
    _Meta_lpar  = '(',
    _Meta_rpar  = ')',
    _Meta_dlr   = '$',
    _Meta_caret = '^',
    _Meta_dot   = '.',
    _Meta_star  = '*',
    _Meta_plus  = '+',
    _Meta_query = '?',
    _Meta_lsq   = '[',
    _Meta_rsq   = ']',
    _Meta_bar   = '|',
    _Meta_esc   = '\\',
    _Meta_dash  = '-',
    _Meta_lbr   = '{',
    _Meta_rbr   = '}',
    _Meta_comma = ',',
    _Meta_colon = ':',
    _Meta_equal = '=',
    _Meta_exc   = '!',
    _Meta_eos   = -1,
    _Meta_nl    = '\n',
    _Meta_cr    = '\r',
    _Meta_bsp   = '\b',
    _Meta_ls    = L'\u2028',
    _Meta_ps    = L'\u2029',
    _Meta_chr   = 0,

    _Esc_bsl      = '\\',
    _Esc_word     = 'b',
    _Esc_not_word = 'B',
    _Esc_ctrl_a   = 'a',
    _Esc_ctrl_b   = 'b',
    _Esc_ctrl_f   = 'f',
    _Esc_ctrl_n   = 'n',
    _Esc_ctrl_r   = 'r',
    _Esc_ctrl_t   = 't',
    _Esc_ctrl_v   = 'v',
    _Esc_ctrl     = 'c',
    _Esc_hex      = 'x',
    _Esc_uni      = 'u'
};

namespace regex_constants {
    // constants used in regular expressions
    _EXPORT_STD enum syntax_option_type : int { // specify RE syntax rules
        ECMAScript = 0x01,
        basic      = 0x02,
        extended   = 0x04,
        awk        = 0x08,
        grep       = 0x10,
        egrep      = 0x20,
        _Gmask     = 0x3F,
        _Any_posix = basic | extended | grep | egrep | awk,

        icase     = 0x0100,
        nosubs    = 0x0200,
        optimize  = 0x0400,
        collate   = 0x0800,
        multiline = 0x1000
    };

    _BITMASK_OPS(_EXPORT_STD, syntax_option_type)

    _EXPORT_STD enum match_flag_type : int { // specify matching and formatting rules
        match_default     = 0x0000,
        match_not_bol     = 0x0001,
        match_not_eol     = 0x0002,
        match_not_bow     = 0x0004,
        match_not_eow     = 0x0008,
        match_any         = 0x0010,
        match_not_null    = 0x0020,
        match_continuous  = 0x0040,
        match_prev_avail  = 0x0100,
        format_default    = 0x0000,
        format_sed        = 0x0400,
        format_no_copy    = 0x0800,
        format_first_only = 0x1000,
        _Match_not_null   = 0x2000,
        _Skip_zero_length = 0x4000,
    };

    _BITMASK_OPS(_EXPORT_STD, match_flag_type)

    _EXPORT_STD enum error_type { // identify error
        error_collate,
        error_ctype,
        error_escape,
        error_backref,
        error_brack,
        error_paren,
        error_brace,
        error_badbrace,
        error_range,
        error_space,
        error_badrepeat,
        error_complexity,
        error_stack,
        _Error_parse, // TRANSITION, was error_parse, keeping behavior
        _Error_syntax // TRANSITION, was error_syntax, keeping behavior
    };
} // namespace regex_constants

extern "C++" [[noreturn]] _CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Xregex_error(regex_constants::error_type _Code);

_EXPORT_STD template <class _Elem>
class regex_traits;

struct _Cl_names { // structure to associate class name with mask value
    const char* _Narrow;
    const wchar_t* _Wide;
    unsigned int _Len;
    ctype_base::mask _Ctype;

    template <class _Elem>
    _NODISCARD const _Elem* _Get() const noexcept {
        if constexpr (is_same_v<_Elem, char>) {
            return _Narrow;
        } else {
            return _Wide;
        }
    }
};

template <class _CharT>
struct _Std_char_traits_eq {
    static bool operator()(_CharT _Left, _CharT _Right) noexcept {
        return char_traits<_CharT>::eq(_Left, _Right);
    }
};

template <class _CharT>
struct _Std_char_traits_lt {
    static bool operator()(_CharT _Left, _CharT _Right) noexcept {
        return char_traits<_CharT>::lt(_Left, _Right);
    }
};

// signed char and other unsigned integral types are supported as an extension.
template <class _Ty>
constexpr bool _Is_predefined_char_like_type = _Is_character<_Ty>::value || is_unsigned_v<_Ty>;

// library-provided char_traits::eq behaves like equal_to<_Elem>
template <class _Elem>
constexpr bool _Can_memcmp_elements_with_pred<_Elem, _Elem, _Std_char_traits_eq<_Elem>> =
    _Is_predefined_char_like_type<_Elem> && _Can_memcmp_elements<_Elem, _Elem>;

template <class _Elem, bool = _Is_predefined_char_like_type<_Elem>>
struct _Lex_compare_memcmp_classify_pred_for_std_char_traits_lt {
    using _UElem = make_unsigned_t<_Elem>;
    using _Pred  = conditional_t<_Lex_compare_memcmp_classify_elements<_UElem, _UElem>, less<int>, void>;
};
template <class _Elem>
struct _Lex_compare_memcmp_classify_pred_for_std_char_traits_lt<_Elem, false> {
    using _Pred = void;
};

// library-provided char_traits::lt behaves like less<make_unsigned_t<_Elem>>
template <class _Elem>
struct _Lex_compare_memcmp_classify_pred<_Elem, _Elem, _Std_char_traits_lt<_Elem>>
    : _Lex_compare_memcmp_classify_pred_for_std_char_traits_lt<_Elem> {};

template <class _RxTraits>
struct _Cmp_icase { // functor to compare for equality following case-insensitive translation of both characters
    using _Elem = typename _RxTraits::char_type;

    explicit _Cmp_icase(const _RxTraits& _Tr) noexcept : _Traits(_Tr) {}

    bool operator()(_Elem _Ex1, _Elem _Ex2) const {
        return _Traits.translate_nocase(_Ex1) == _Traits.translate_nocase(_Ex2);
    }

    const _RxTraits& _Traits;
};

template <class _RxTraits>
struct _Cmp_collate { // functor to compare for equality following collating translation of both characters
    using _Elem = typename _RxTraits::char_type;

    explicit _Cmp_collate(const _RxTraits& _Tr) noexcept : _Traits(_Tr) {}

    bool operator()(_Elem _Ex1, _Elem _Ex2) const {
        return _Traits.translate(_Ex1) == _Traits.translate(_Ex2);
    }

    const _RxTraits& _Traits;
};

template <class _RxTraits>
struct _Cmp_icase_translateleft {
    // functor to compare for equality following case-insensitive translation of the left character
    using _Elem = typename _RxTraits::char_type;

    explicit _Cmp_icase_translateleft(const _RxTraits& _Tr) noexcept : _Traits(_Tr) {}

    bool operator()(_Elem _Ex1, _Elem _Ex2) const {
        return _Traits.translate_nocase(_Ex1) == _Ex2;
    }

    const _RxTraits& _Traits;
};

template <class _RxTraits>
struct _Cmp_collate_translateleft {
    // functor to compare for equality following collating translation of the left character
    using _Elem = typename _RxTraits::char_type;

    explicit _Cmp_collate_translateleft(const _RxTraits& _Tr) noexcept : _Traits(_Tr) {}

    bool operator()(_Elem _Ex1, _Elem _Ex2) const {
        return _Traits.translate(_Ex1) == _Ex2;
    }

    const _RxTraits& _Traits;
};

struct _Regex_traits_base { // base of all regular expression traits
    enum _Char_class_type {
        _Ch_alnum  = ctype_base::alnum,
        _Ch_alpha  = ctype_base::alpha,
        _Ch_cntrl  = ctype_base::cntrl,
        _Ch_digit  = ctype_base::digit,
        _Ch_graph  = ctype_base::graph,
        _Ch_lower  = ctype_base::lower,
        _Ch_print  = ctype_base::print,
        _Ch_punct  = ctype_base::punct,
        _Ch_space  = ctype_base::space,
        _Ch_upper  = ctype_base::upper,
        _Ch_xdigit = ctype_base::xdigit,
        _Ch_blank  = ctype_base::blank
    };
    using char_class_type = ctype_base::mask;
};

#if defined(_CPPRTTI) && !defined(_M_CEE_PURE)
inline size_t _Regex_transform_primary(_Out_writes_(_Last1 - _First1) _Post_readable_size_(return) char* _First1,
    char* _Last1, _In_reads_(_Last2 - _First2) const char* _First2, const char* _Last2,
    _In_opt_ const _Locinfo::_Collvec* _Vector) noexcept {
    return __std_regex_transform_primary_char(_First1, _Last1, _First2, _Last2, _Vector);
}

inline size_t _Regex_transform_primary(_Out_writes_(_Last1 - _First1) _Post_readable_size_(return) wchar_t* _First1,
    wchar_t* _Last1, _In_reads_(_Last2 - _First2) const wchar_t* _First2, const wchar_t* _Last2,
    _In_opt_ const _Locinfo::_Collvec* _Vector) noexcept {
    return __std_regex_transform_primary_wchar_t(_First1, _Last1, _First2, _Last2, _Vector);
}
#endif // ^^^ defined(_CPPRTTI) && !defined(_M_CEE_PURE) ^^^

template <class _Elem>
class _Regex_traits : public _Regex_traits_base { // base class for regular expression traits
public:
    using char_type   = _Elem;
    using size_type   = size_t;
    using string_type = basic_string<_Elem>;
    using locale_type = locale;

    static size_type length(const _Elem* _Str) {
        return char_traits<_Elem>::length(_Str);
    }

    _Regex_traits() {
        _Cache_locale();
    }

    _Regex_traits(const _Regex_traits& _Right) : _Loc(_Right._Loc) {
        _Cache_locale();
    }

    _Regex_traits& operator=(const _Regex_traits& _Right) {
        _Loc = _Right._Loc;
        _Cache_locale();
        return *this;
    }

    _Elem translate(_Elem _Ch) const { // provide locale-sensitive mapping
        return _Ch;
    }

    _Elem translate_nocase(_Elem _Ch) const { // provide case-insensitive mapping
        return _Getctype()->tolower(_Ch);
    }

    template <class _FwdIt>
    string_type transform(_FwdIt _First, _FwdIt _Last) const { // apply locale-specific transformation
        const string_type _Str(_First, _Last);
        return _Getcoll()->transform(_Str.data(), _Str.data() + _Str.size());
    }

    template <class _FwdIt>
    string_type transform_primary(_FwdIt _First, _FwdIt _Last) const {
        // apply locale-specific case-insensitive transformation
        string_type _Res;
#if defined(_CPPRTTI) && !defined(_M_CEE_PURE)
        if (_First != _Last) {
            const collate<_Elem>* _Coll = _Getcoll();
            const auto& _Coll_type      = typeid(*_Coll);
            // TRANSITION, ABI: GH-5394: locale creates collate objects of type collate, not collate_byname.
            // Depending on the resolution of LWG-2338, comparison to typeid(collate) might also become
            // required by the standard.
            if (_Coll_type == typeid(collate_byname<_Elem>) || _Coll_type == typeid(collate<_Elem>)) {
                // non-empty string with known collate facet, transform it
                const string_type _Src(_First, _Last);
                const auto _Src_first = _Src.data();
                const auto _Src_last  = _Src_first + _Src.size();

                size_t _Count = _Src.size();
                while (_Res.size() < _Count) {
                    _Res.resize(_Count);
                    _Count = _STD _Regex_transform_primary(
                        &_Res[0], &_Res[0] + _Count, _Src_first, _Src_last, &_Coll->_Coll);

                    if (_Count == static_cast<size_t>(-1)) {
                        // return empty string in case of error
                        _Count = 0;
                        break;
                    }
                }
                _Res.resize(_Count);
            }
        }
#else // ^^^ defined(_CPPRTTI) && !defined(_M_CEE_PURE) / !defined(_CPPRTTI) || defined(_M_CEE_PURE) vvv
        (void) _First;
        (void) _Last;
#endif // ^^^ !defined(_CPPRTTI) || defined(_M_CEE_PURE) ^^^
        return _Res;
    }

    bool isctype(_Elem _Ch, char_class_type _Fx) const {
        if (_Fx != static_cast<char_class_type>(-1)) {
            return _Getctype()->is(_Fx, _Ch);
        } else {
            return _Ch == '_' // assumes L'_' == '_'
                || _Getctype()->is(_Ch_alnum, _Ch);
        }
    }

    template <class _Iter>
    char_class_type lookup_classname(_Iter _First, _Iter _Last, bool _Icase = false) const {
        // map [_First, _Last) to character class mask value
#define _REGEX_CHAR_CLASS_NAME(n, c)                            \
    {                                                           \
        n, L##n, static_cast<unsigned int>(_STD size(n) - 1), c \
    }
        static constexpr _Cl_names _Names[] = {
            // map class names to numeric constants
            _REGEX_CHAR_CLASS_NAME("alnum", _Ch_alnum),
            _REGEX_CHAR_CLASS_NAME("alpha", _Ch_alpha),
            _REGEX_CHAR_CLASS_NAME("blank", _Ch_blank),
            _REGEX_CHAR_CLASS_NAME("cntrl", _Ch_cntrl),
            _REGEX_CHAR_CLASS_NAME("d", _Ch_digit),
            _REGEX_CHAR_CLASS_NAME("digit", _Ch_digit),
            _REGEX_CHAR_CLASS_NAME("graph", _Ch_graph),
            _REGEX_CHAR_CLASS_NAME("lower", _Ch_lower),
            _REGEX_CHAR_CLASS_NAME("print", _Ch_print),
            _REGEX_CHAR_CLASS_NAME("punct", _Ch_punct),
            _REGEX_CHAR_CLASS_NAME("space", _Ch_space),
            _REGEX_CHAR_CLASS_NAME("s", _Ch_space),
            _REGEX_CHAR_CLASS_NAME("upper", _Ch_upper),
            _REGEX_CHAR_CLASS_NAME("w", static_cast<ctype_base::mask>(-1)),
            _REGEX_CHAR_CLASS_NAME("xdigit", _Ch_xdigit),
            {nullptr, nullptr, 0, 0},
        };
#undef _REGEX_CHAR_CLASS_NAME

        _Adl_verify_range(_First, _Last);
        unsigned int _Ix = 0;
        for (; _Names[_Ix]._Get<_Elem>(); ++_Ix) {
            if (_STD equal(_Get_unwrapped(_First), _Get_unwrapped(_Last), _Names[_Ix]._Get<_Elem>(),
                    _Names[_Ix]._Get<_Elem>() + _Names[_Ix]._Len, _Cmp_icase<_Regex_traits<_Elem>>{*this})) {
                break;
            }
        }

        char_class_type _Mask{};
        if (_Names[_Ix]._Get<_Elem>()) {
            _Mask = _Names[_Ix]._Ctype;
        }

        if (_Icase && (_Mask & (_Ch_lower | _Ch_upper))) {
            _Mask |= _Ch_lower | _Ch_upper;
        }

        return _Mask;
    }

    template <class _FwdIt>
    string_type lookup_collatename(_FwdIt _First, _FwdIt _Last) const { // map [_First, _Last) to collation element
        if (_First != _Last && _STD next(_First) == _Last) {
            return string_type{_First, _Last};
        }
        return string_type{};
    }

    locale_type imbue(locale_type _Lx) { // store locale object
        locale_type _Tmp = _Loc;
        _Loc             = _Lx;
        _Cache_locale();
        return _Tmp;
    }

    locale_type getloc() const noexcept /* strengthened */ {
        return _Loc;
    }

    const collate<_Elem>* _Getcoll() const noexcept { // get collate facet pointer
        return _Pcoll;
    }

    const ctype<_Elem>* _Getctype() const noexcept { // get ctype facet pointer
        return _Pctype;
    }

private:
    void _Cache_locale() { // populate _Pcoll and _Pctype with _Loc locale
        _Pcoll  = _STD addressof(_STD use_facet<collate<_Elem>>(_Loc));
        _Pctype = _STD addressof(_STD use_facet<ctype<_Elem>>(_Loc));
    }

    const collate<_Elem>* _Pcoll;
    const ctype<_Elem>* _Pctype;
    locale_type _Loc;
};

template <>
class regex_traits<char> : public _Regex_traits<char> {
public:
    int value(char _Ch, int _Base) const { // map character value to numeric value
        if ((_Base != 8 && '0' <= _Ch && _Ch <= '9') || (_Base == 8 && '0' <= _Ch && _Ch <= '7')) {
            return _Ch - '0';
        }

        if (_Base != 16) {
            return -1;
        }

        if ('a' <= _Ch && _Ch <= 'f') {
            return _Ch - 'a' + 10;
        }

        if ('A' <= _Ch && _Ch <= 'F') {
            return _Ch - 'A' + 10;
        }

        return -1;
    }
};

template <>
class regex_traits<wchar_t> : public _Regex_traits<wchar_t> {
public:
    int value(wchar_t _Ch, int _Base) const { // map character value to numeric value
        if ((_Base != 8 && L'0' <= _Ch && _Ch <= L'9') || (_Base == 8 && L'0' <= _Ch && _Ch <= L'7')) {
            return _Ch - L'0';
        }

        if (_Base != 16) {
            return -1;
        }

        if (L'a' <= _Ch && _Ch <= L'f') {
            return _Ch - L'a' + 10;
        }

        if (L'A' <= _Ch && _Ch <= L'F') {
            return _Ch - L'A' + 10;
        }

        return -1;
    }
};

_EXPORT_STD class _NODISCARD regex_error : public runtime_error { // type of all regular expression exceptions
public:
    explicit regex_error(regex_constants::error_type _Ex) : runtime_error(_Stringify(_Ex)), _Err(_Ex) {}

    _NODISCARD regex_constants::error_type code() const noexcept /* strengthened */ {
        return _Err;
    }

private:
    static const char* _Stringify(regex_constants::error_type _Ex) noexcept { // map error code to string
        switch (_Ex) { // select known error_type message
        case regex_constants::error_collate:
            return "regex_error(error_collate): The expression "
                   "contained an invalid collating element name.";
        case regex_constants::error_ctype:
            return "regex_error(error_ctype): The expression "
                   "contained an invalid character class name.";
        case regex_constants::error_escape:
            return "regex_error(error_escape): The expression "
                   "contained an invalid escaped character, "
                   "or a trailing escape.";
        case regex_constants::error_backref:
            return "regex_error(error_backref): The expression "
                   "contained an invalid back reference.";
        case regex_constants::error_brack:
            return "regex_error(error_brack): The expression "
                   "contained mismatched [ and ].";
        case regex_constants::error_paren:
            return "regex_error(error_paren): The expression "
                   "contained mismatched ( and ).";
        case regex_constants::error_brace:
            return "regex_error(error_brace): The expression "
                   "contained mismatched { and }.";
        case regex_constants::error_badbrace:
            return "regex_error(error_badbrace): The expression "
                   "contained an invalid range in a {} expression.";
        case regex_constants::error_range:
            return "regex_error(error_range): The expression "
                   "contained an invalid character range, "
                   "such as [b-a] in most encodings.";
        case regex_constants::error_space:
            return "regex_error(error_space): There was insufficient "
                   "memory to convert the expression into "
                   "a finite state machine.";
        case regex_constants::error_badrepeat:
            return "regex_error(error_badrepeat): One of *?+{ "
                   "was not preceded by a valid regular expression.";
        case regex_constants::error_complexity:
            return "regex_error(error_complexity): The complexity of "
                   "an attempted match against a regular expression "
                   "exceeded a pre-set level.";
        case regex_constants::error_stack:
            return "regex_error(error_stack): There was insufficient "
                   "memory to determine whether the regular expression "
                   "could match the specified character sequence.";
        case regex_constants::_Error_parse: // TRANSITION, keeping behavior
            return "regex_error(error_parse)";
        case regex_constants::_Error_syntax:
            return "regex_error(error_syntax)";
        default:
            return "regex_error";
        }
    }

    regex_constants::error_type _Err;
};

inline bool _Is_word(unsigned char _UCh) {
    // special casing char to avoid branches for std::regex in this path
    static constexpr bool _Is_word_table[_STD _Max_limit<unsigned char>() + 1] = {
        //       X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 XA XB XC XD XE XF
        /* 0X */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 1X */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 2X */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 3X */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, // 0-9
        /* 4X */ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // A-Z
        /* 5X */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, // 5F == _
        /* 6X */ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // a-z
        /* 7X */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
        // non-ASCII values initialized to 0
    };
    return _Is_word_table[_UCh];
}

inline bool _Is_word(char _Ch) {
    return _Is_word(static_cast<unsigned char>(_Ch));
}

template <class _Elem>
bool _Is_word(_Elem _Ch) {
    // assumes that ASCII characters are represented at ASCII code points
    const auto _Uchar = static_cast<unsigned char>(_Ch);
    return static_cast<_Elem>(_Uchar) == _Ch && _Uchar <= 'z' && _Is_word(_Uchar);
}

_EXPORT_STD template <class _BidIt>
class sub_match : public pair<_BidIt, _BidIt> { // class to hold contents of a capture group
public:
    using _Mybase         = pair<_BidIt, _BidIt>;
    using value_type      = typename iterator_traits<_BidIt>::value_type;
    using difference_type = typename iterator_traits<_BidIt>::difference_type;
    using iterator        = _BidIt;
    using string_type     = basic_string<value_type>;

    constexpr sub_match() = default;

    bool matched = false;

    _NODISCARD difference_type length() const {
        const _Mybase _Range(_Effective_range());
        return _STD distance(_Range.first, _Range.second);
    }

    operator string_type() const { // convert matched text to string
        return str();
    }

    _NODISCARD string_type str() const { // convert matched text to string
        const _Mybase _Range(_Effective_range());
        return string_type{_Range.first, _Range.second};
    }

    _NODISCARD int compare(const sub_match& _Right) const { // compare *this to _Right
        const _Mybase _LRange(_Effective_range());
        const _Mybase _RRange(_Right._Effective_range());
        return _Iter_compare(_LRange.first, _LRange.second, _RRange.first, _RRange.second);
    }

    _NODISCARD int compare(const string_type& _Right) const { // compare *this to _Right
        return _Compare(_Right.data(), _Right.size());
    }

    _NODISCARD int compare(_In_z_ const value_type* _Ptr) const { // compare *this to array pointed to by _Ptr
        return _Compare(_Ptr, char_traits<value_type>::length(_Ptr));
    }

    void swap(sub_match& _Other) noexcept(_Is_nothrow_swappable<_BidIt>::value) {
        _Mybase::swap(_Other);
        _STD swap(matched, _Other.matched);
    }

    template <class _FwdIt2>
    static int _Iter_compare(_BidIt _First1, _BidIt _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) {
        // compare two iterator ranges:
        // if [_First1, _Last1) is lexicographically less than [_First2, _Last2), a negative value
        // if [_First2, _Last2) is lexicographically less than [_First1, _Last1), a positive value
        // otherwise, zero
        static_assert(is_same_v<_Iter_value_t<_FwdIt2>, value_type>, "bad _FwdIt2 to _Iter_compare");

        _Adl_verify_range(_First1, _Last1);
        _Adl_verify_range(_First2, _Last2);

        auto _UFirst1 = _Get_unwrapped(_First1);
        auto _ULast1  = _Get_unwrapped(_Last1);
        auto _UFirst2 = _Get_unwrapped(_First2);
        auto _ULast2  = _Get_unwrapped(_Last2);

        if constexpr (is_pointer_v<decltype(_UFirst1)> && is_pointer_v<decltype(_UFirst2)>) {
            return _Traits_compare<char_traits<value_type>>(
                _UFirst1, static_cast<size_t>(_ULast1 - _UFirst1), _UFirst2, static_cast<size_t>(_ULast2 - _UFirst2));
        } else {
            const auto _Cmp = _STD mismatch(_UFirst1, _ULast1, _UFirst2, _ULast2, _Std_char_traits_eq<value_type>{});

            if (_Cmp.first == _ULast1) {
                if (_Cmp.second == _ULast2) {
                    return 0;
                } else {
                    return -1;
                }
            }

            if (_Cmp.second == _ULast2) {
                return 1;
            }

            if (char_traits<value_type>::lt(*_Cmp.first, *_Cmp.second)) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    int _Compare(const value_type* const _Ptr, const size_t _Count) const {
        // compare *this to array [_Ptr, _Ptr + _Count)
        const _Mybase _Range(_Effective_range());
        return _Iter_compare(_Range.first, _Range.second, _Ptr, _Ptr + _Count);
    }

    bool _Match_equal(const sub_match& _Right) const { // check *this to _Right for equality
        const _Mybase _LRange(_Effective_range());
        const _Mybase _RRange(_Right._Effective_range());
        return _STD equal(
            _LRange.first, _LRange.second, _RRange.first, _RRange.second, _Std_char_traits_eq<value_type>{});
    }

    bool _Match_equal(const value_type* const _Ptr, const size_t _Count) const {
        // check *this to array [_Ptr, _Ptr + _Count) for equality
        const _Mybase _Range(_Effective_range());
        return _STD equal(_Range.first, _Range.second, _Ptr, _Ptr + _Count, _Std_char_traits_eq<value_type>{});
    }

    bool _Match_equal(const value_type* const _Ptr) const { // check *this to C-string _Ptr for equality
        return _Match_equal(_Ptr, char_traits<value_type>::length(_Ptr));
    }

    bool _Less(const sub_match& _Right) const { // check whether *this is less than _Right
        const _Mybase _LRange(_Effective_range());
        const _Mybase _RRange(_Right._Effective_range());
        return _STD lexicographical_compare(
            _LRange.first, _LRange.second, _RRange.first, _RRange.second, _Std_char_traits_lt<value_type>{});
    }

    bool _Less(const value_type* const _Ptr, const size_t _Count) const {
        // check whether *this is less than [_Ptr, _Ptr + _Count)
        const _Mybase _Range(_Effective_range());
        return _STD lexicographical_compare(
            _Range.first, _Range.second, _Ptr, _Ptr + _Count, _Std_char_traits_lt<value_type>{});
    }

    bool _Less(const value_type* const _Ptr) const { // check whether *this is less than C-string _Ptr
        return _Less(_Ptr, char_traits<value_type>::length(_Ptr));
    }

    bool _Greater(const value_type* const _Ptr, const size_t _Count) const {
        // check whether *this is greater than [_Ptr, _Ptr + _Count)
        const _Mybase _Range(_Effective_range());
        return _STD lexicographical_compare(
            _Ptr, _Ptr + _Count, _Range.first, _Range.second, _Std_char_traits_lt<value_type>{});
    }

    bool _Greater(const value_type* const _Ptr) const { // check whether *this is greater than C-string _Ptr
        return _Greater(_Ptr, char_traits<value_type>::length(_Ptr));
    }

    _Mybase _Effective_range() const { // if matched, returns *this; otherwise returns an empty range
        if (matched) {
            return *this;
        } else {
            return _Mybase{};
        }
    }
};

_EXPORT_STD using csub_match  = sub_match<const char*>;
_EXPORT_STD using wcsub_match = sub_match<const wchar_t*>;
_EXPORT_STD using ssub_match  = sub_match<string::const_iterator>;
_EXPORT_STD using wssub_match = sub_match<wstring::const_iterator>;

_EXPORT_STD template <class _BidIt>
_NODISCARD bool operator==(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Left._Match_equal(_Right);
}

#if _HAS_CXX20
_EXPORT_STD template <class _BidIt>
_NODISCARD auto operator<=>(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    using _Comparison_category = _Get_comparison_category_t<char_traits<_Iter_value_t<_BidIt>>>;
    return static_cast<_Comparison_category>(_Left.compare(_Right) <=> 0);
}
#else // ^^^ _HAS_CXX20 / !_HAS_CXX20 vvv
template <class _BidIt>
_NODISCARD bool operator!=(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt>
_NODISCARD bool operator<(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Left._Less(_Right);
}

template <class _BidIt>
_NODISCARD bool operator>(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right < _Left;
}

template <class _BidIt>
_NODISCARD bool operator<=(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt>
_NODISCARD bool operator>=(const sub_match<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left < _Right);
}
#endif // ^^^ !_HAS_CXX20 ^^^

_EXPORT_STD template <class _BidIt>
_NODISCARD bool operator==(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return _Left._Match_equal(_Right);
}

#if _HAS_CXX20
_EXPORT_STD template <class _BidIt>
_NODISCARD auto operator<=>(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    using _Comparison_category = _Get_comparison_category_t<char_traits<_Iter_value_t<_BidIt>>>;
    return static_cast<_Comparison_category>(_Left.compare(_Right) <=> 0);
}
#else // ^^^ _HAS_CXX20 / !_HAS_CXX20 vvv
template <class _BidIt>
_NODISCARD bool operator==(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Match_equal(_Left);
}

template <class _BidIt>
_NODISCARD bool operator!=(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt>
_NODISCARD bool operator<(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Greater(_Left);
}

template <class _BidIt>
_NODISCARD bool operator>(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return _Right < _Left;
}

template <class _BidIt>
_NODISCARD bool operator<=(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt>
_NODISCARD bool operator>=(const _Iter_value_t<_BidIt>* _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left < _Right);
}

template <class _BidIt>
_NODISCARD bool operator!=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return !(_Left == _Right);
}

template <class _BidIt>
_NODISCARD bool operator<(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return _Left._Less(_Right);
}

template <class _BidIt>
_NODISCARD bool operator>(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return _Right < _Left;
}

template <class _BidIt>
_NODISCARD bool operator<=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return !(_Right < _Left);
}

template <class _BidIt>
_NODISCARD bool operator>=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>* _Right) {
    return !(_Left < _Right);
}
#endif // ^^^ !_HAS_CXX20 ^^^

_EXPORT_STD template <class _BidIt>
_NODISCARD bool operator==(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return _Left._Match_equal(_STD addressof(_Right), 1);
}

#if _HAS_CXX20
_EXPORT_STD template <class _BidIt>
_NODISCARD auto operator<=>(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    using _Comparison_category = _Get_comparison_category_t<char_traits<_Iter_value_t<_BidIt>>>;
    return static_cast<_Comparison_category>(_Left._Compare(_STD addressof(_Right), 1) <=> 0);
}
#else // ^^^ _HAS_CXX20 / !_HAS_CXX20 vvv
template <class _BidIt>
_NODISCARD bool operator==(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Match_equal(_STD addressof(_Left), 1);
}

template <class _BidIt>
_NODISCARD bool operator!=(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt>
_NODISCARD bool operator<(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Greater(_STD addressof(_Left), 1);
}

template <class _BidIt>
_NODISCARD bool operator>(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right < _Left;
}

template <class _BidIt>
_NODISCARD bool operator<=(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt>
_NODISCARD bool operator>=(const _Iter_value_t<_BidIt>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left < _Right);
}

template <class _BidIt>
_NODISCARD bool operator!=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt>
_NODISCARD bool operator<(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return _Left._Less(_STD addressof(_Right), 1);
}

template <class _BidIt>
_NODISCARD bool operator>(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return _Right < _Left;
}

template <class _BidIt>
_NODISCARD bool operator<=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt>
_NODISCARD bool operator>=(const sub_match<_BidIt>& _Left, const _Iter_value_t<_BidIt>& _Right) {
    return !(_Left < _Right);
}
#endif // ^^^ !_HAS_CXX20 ^^^

_EXPORT_STD template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator==(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return _Left._Match_equal(_Right.data(), _Right.size());
}

#if _HAS_CXX20
_EXPORT_STD template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD auto operator<=>(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    using _Comparison_category = _Get_comparison_category_t<char_traits<_Iter_value_t<_BidIt>>>;
    return static_cast<_Comparison_category>(_Left._Compare(_Right.data(), _Right.size()) <=> 0);
}
#else // ^^^ _HAS_CXX20 / !_HAS_CXX20 vvv
template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator==(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Match_equal(_Left.data(), _Left.size());
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator!=(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator<(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right._Greater(_Left.data(), _Left.size());
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator>(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return _Right < _Left;
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator<=(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator>=(
    const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Left, const sub_match<_BidIt>& _Right) {
    return !(_Left < _Right);
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator!=(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return !(_Left == _Right);
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator<(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return _Left._Less(_Right.data(), _Right.size());
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator>(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return _Right < _Left;
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator<=(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return !(_Right < _Left);
}

template <class _BidIt, class _Traits, class _Alloc>
_NODISCARD bool operator>=(
    const sub_match<_BidIt>& _Left, const basic_string<_Iter_value_t<_BidIt>, _Traits, _Alloc>& _Right) {
    return !(_Left < _Right);
}
#endif // ^^^ !_HAS_CXX20 ^^^

_EXPORT_STD template <class _Elem, class _Traits, class _BidIt>
basic_ostream<_Elem, _Traits>& operator<<(basic_ostream<_Elem, _Traits>& _Ostr, const sub_match<_BidIt>& _Match) {
    return _Ostr << _Match.str();
}

_EXPORT_STD template <class _BidIt, class _Alloc = allocator<sub_match<_BidIt>>>
class match_results;

template <class _BidIt, class _Alloc, class _InIt, class _OutIt>
_OutIt _Format_default(const match_results<_BidIt, _Alloc>& _Match, _OutIt _Out, _InIt _First, _InIt _Last,
    regex_constants::match_flag_type _Flags = regex_constants::format_default);

template <class _BidIt, class _Alloc, class _InIt, class _OutIt>
_OutIt _Format_sed(const match_results<_BidIt, _Alloc>& _Match, _OutIt _Out, _InIt _First, _InIt _Last,
    regex_constants::match_flag_type _Flags = regex_constants::format_default);

_EXPORT_STD template <class _BidIt, class _Alloc>
class match_results { // class to hold contents of all capture groups
public:
    using _Elem     = sub_match<_BidIt>;
    using _MyCont   = vector<_Elem, _Alloc>;
    using _Mytraits = allocator_traits<_Alloc>;

    using value_type      = _Elem;
    using const_reference = const value_type&;
    using reference       = value_type&;
    using const_iterator  = typename _MyCont::const_iterator;
    using iterator        = const_iterator;
    using difference_type = typename iterator_traits<_BidIt>::difference_type;
    using size_type       = typename _Mytraits::size_type;
    using allocator_type  = _Alloc;
    using char_type       = typename iterator_traits<_BidIt>::value_type;
    using string_type     = basic_string<char_type>;

    match_results() = default;

    explicit match_results(const _Alloc& _Al) : _Matches(_Al) {}

    match_results(const match_results& _Other, const _Alloc& _Al)
        : _Org(_Other._Org), _Ready(_Other._Ready), _Matches(_Other._Matches, _Al), _Prefix(_Other._Prefix),
          _Suffix(_Other._Suffix), _Null_elem(_Other._Null_elem) {}

    match_results(match_results&& _Other, const _Alloc& _Al) noexcept(
        conjunction_v<typename _Mytraits::is_always_equal, is_nothrow_move_constructible<_BidIt>>) // strengthened
        : _Org(_STD move(_Other._Org)), _Ready(_Other._Ready), _Matches(_STD move(_Other._Matches), _Al),
          _Prefix(_STD move(_Other._Prefix)), _Suffix(_STD move(_Other._Suffix)),
          _Null_elem(_STD move(_Other._Null_elem)) {}

    _NODISCARD bool ready() const noexcept /* strengthened */ {
        return _Ready;
    }

    _NODISCARD size_type size() const noexcept /* strengthened */ {
        return _Matches.size();
    }

    _NODISCARD size_type max_size() const noexcept /* strengthened */ {
        return _Matches.max_size();
    }

    _NODISCARD bool empty() const noexcept /* strengthened */ {
        return _Matches.empty();
    }

    _NODISCARD difference_type length(size_type _Sub = 0) const {
        return (*this)[_Sub].length();
    }

    _NODISCARD difference_type position(size_type _Sub = 0) const {
        return _STD distance(_Org, (*this)[_Sub].first);
    }

    _NODISCARD string_type str(size_type _Sub = 0) const {
        return string_type{(*this)[_Sub]};
    }

    _NODISCARD const_reference operator[](size_type _Sub) const noexcept /* strengthened */ {
        return _Matches.size() <= _Sub ? _Null_elem : _Matches[_Sub];
    }

    _NODISCARD const_reference prefix() const noexcept /* strengthened */ {
        return _Prefix;
    }

    _NODISCARD const_reference suffix() const noexcept /* strengthened */ {
        return _Suffix;
    }

    _NODISCARD const_iterator begin() const noexcept /* strengthened */ {
        return _Matches.begin();
    }

    _NODISCARD const_iterator end() const noexcept /* strengthened */ {
        return _Matches.end();
    }

    _NODISCARD const_iterator cbegin() const noexcept /* strengthened */ {
        return _Matches.begin();
    }

    _NODISCARD const_iterator cend() const noexcept /* strengthened */ {
        return _Matches.end();
    }

    const _Elem* _Unchecked_begin() const noexcept {
        return _Matches._Unchecked_begin();
    }

    const _Elem* _Unchecked_end() const noexcept {
        return _Matches._Unchecked_end();
    }

    template <class _OutIt>
    _OutIt _Format1(_OutIt _Out, const char_type* _Fmt_begin, const char_type* _Fmt_end,
        regex_constants::match_flag_type _Flags) const { // format text, replacing matches
        return _Flags & regex_constants::format_sed ? _Format_sed(*this, _Out, _Fmt_begin, _Fmt_end, _Flags)
                                                    : _Format_default(*this, _Out, _Fmt_begin, _Fmt_end, _Flags);
    }

    template <class _OutIt>
    _OutIt format(_OutIt _Out, const char_type* _Fmt_begin, const char_type* _Fmt_end,
        regex_constants::match_flag_type _Flags = regex_constants::format_default) const {
        // format text, replacing matches
        _Adl_verify_range(_Fmt_begin, _Fmt_end);
        _Seek_wrapped(_Out, _Format1(_Get_unwrapped_unverified(_Out), _Fmt_begin, _Fmt_end, _Flags));
        return _Out;
    }

    template <class _OutIt, class _Traits1, class _Alloc1>
    _OutIt format(_OutIt _Out, const basic_string<char_type, _Traits1, _Alloc1>& _Fmt,
        regex_constants::match_flag_type _Flags = regex_constants::format_default) const {
        // format text, replacing matches
        _Seek_wrapped(_Out, _Format1(_Get_unwrapped_unverified(_Out), _Fmt.data(), _Fmt.data() + _Fmt.size(), _Flags));
        return _Out;
    }

    template <class _Traits1, class _Alloc1>
    _NODISCARD basic_string<char_type, _Traits1, _Alloc1> format(const basic_string<char_type, _Traits1, _Alloc1>& _Fmt,
        regex_constants::match_flag_type _Flags = regex_constants::format_default) const {
        // format text, replacing matches
        basic_string<char_type, _Traits1, _Alloc1> _Str;
        format(_STD back_inserter(_Str), _Fmt.data(), _Fmt.data() + _Fmt.size(), _Flags);
        return _Str;
    }

    _NODISCARD string_type format(
        const char_type* _Fmt_begin, regex_constants::match_flag_type _Flags = regex_constants::format_default) const {
        // format text, replacing matches
        return format(static_cast<string_type>(_Fmt_begin), _Flags);
    }

    _NODISCARD allocator_type get_allocator() const noexcept /* strengthened */ {
        return static_cast<allocator_type>(_Matches.get_allocator());
    }

    void swap(match_results& _Right) noexcept(_Is_nothrow_swappable<_BidIt>::value) /* strengthened */ {
        using _STD swap;
        _STD swap(_Ready, _Right._Ready);
        swap(_Org, _Right._Org); // intentional ADL
        _Matches.swap(_Right._Matches);
        _STD swap(_Prefix, _Right._Prefix);
        _STD swap(_Suffix, _Right._Suffix);
    }

    void _Resize(unsigned int _Nx) {
        _Matches.resize(_Nx);
    }

    _Elem& _Pfx() noexcept {
        return _Prefix;
    }

    _Elem& _Sfx() noexcept {
        return _Suffix;
    }

    _Elem& _Null() noexcept {
        return _Null_elem;
    }

    _Elem& _At(unsigned int _Sub) noexcept {
        return _Matches[_Sub];
    }

    _Elem _At(unsigned int _Sub) const noexcept {
        return _Matches[_Sub];
    }

    _BidIt _Org = _BidIt();
    bool _Ready = false;

private:
    _MyCont _Matches;
    _Elem _Prefix;
    _Elem _Suffix;
    _Elem _Null_elem;
};

_EXPORT_STD template <class _BidIt, class _Alloc>
_NODISCARD bool operator==(const match_results<_BidIt, _Alloc>& _Left, const match_results<_BidIt, _Alloc>& _Right) {
    if (!_Left.ready() && !_Right.ready()) {
        return true;
    } else if (!_Left.ready() || !_Right.ready()) {
        return false;
    } else if (_Left.empty() && _Right.empty()) {
        return true;
    } else if (_Left.empty() || _Right.empty()) {
        return false;
    } else {
        return _Left.size() == _Right.size() && _Left.prefix() == _Right.prefix() && _Left.suffix() == _Right.suffix()
            && _STD equal(_Left.begin(), _Left.end(), _Right.begin());
    }
}

#if !_HAS_CXX20
template <class _BidIt, class _Alloc>
_NODISCARD bool operator!=(const match_results<_BidIt, _Alloc>& _Left, const match_results<_BidIt, _Alloc>& _Right) {
    return !(_Left == _Right);
}
#endif // !_HAS_CXX20

_INLINE_VAR constexpr unsigned int _Bmp_max   = 256U; // must fit in an unsigned int
_INLINE_VAR constexpr unsigned int _Bmp_shift = 3U;
_INLINE_VAR constexpr unsigned int _Bmp_chrs  = 1U << _Bmp_shift; // # of bits to be stored in each char
_INLINE_VAR constexpr unsigned int _Bmp_mask  = _Bmp_chrs - 1U;
_INLINE_VAR constexpr unsigned int _Bmp_size  = (_Bmp_max + _Bmp_chrs - 1U) / _Bmp_chrs;

_INLINE_VAR constexpr unsigned int _ARRAY_THRESHOLD = 4U;

enum _Node_flags : int { // flags for nfa nodes with special properties
    _Fl_none              = 0x0000,
    _Fl_negate            = 0x0001,
    _Fl_greedy            = 0x0002,
    _Fl_longest           = 0x0008, // TRANSITION, ABI: 0x004 is unused; the parser previously marked some nodes with it
    _Fl_class_negated_w   = 0x0100,
    _Fl_class_negated_s   = 0x0200,
    _Fl_class_negated_d   = 0x0400,
    _Fl_class_cl_all_bits = 0x0800, // TRANSITION, ABI: GH-5242
    _Fl_begin_needs_w     = 0x0100,
    _Fl_begin_needs_s     = 0x0200,
    _Fl_begin_needs_d     = 0x0400,
    _Fl_rep_branchless    = 0x1000,
};

_BITMASK_OPS(_EMPTY_ARGUMENT, _Node_flags)

enum _Node_type { // type flag for nfa nodes
    _N_none,
    _N_nop,
    _N_bol,
    _N_eol,
    _N_wbound,
    _N_dot,
    _N_str,
    _N_class,
    _N_group,
    _N_end_group,
    _N_assert,
    _N_neg_assert,
    _N_end_assert,
    _N_capture,
    _N_end_capture,
    _N_back,
    _N_if,
    _N_endif,
    _N_rep,
    _N_end_rep,
    _N_begin,
    _N_end
};

template <class _Elem>
struct _Buf { // character buffer
    _Buf() = default;

    ~_Buf() noexcept {
        _CSTD free(_Chrs);
    }

    unsigned int _Size() const noexcept {
        return _Nchrs;
    }

    _Elem _At(unsigned int _Idx) const {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Idx < _Nchrs, "regex buffer subscript out of range");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return _Chrs[_Idx];
    }

    const _Elem* _Str() const {
        return _Chrs;
    }

    void _Insert2(_Elem _Ch) { // append _Ch
        if (_Sz <= _Nchrs) {
            _Expand2(1U);
        }

        _Chrs[_Nchrs++] = _Ch;
    }

    _Elem _Del() noexcept { // remove and return last character
        return _Chrs[--_Nchrs];
    }

    template <class _FwdIt>
    void _Insert2(_FwdIt _First, _FwdIt _Last) { // append multiple characters
        while (_First != _Last) {
            _Insert2(*_First++);
        }
    }

private:
    unsigned int _Calculate_expansion(unsigned int _Increase) const {
        constexpr size_t _Max_elems      = static_cast<size_t>(-1) / sizeof(_Elem);
        constexpr unsigned int _Max_uint = static_cast<unsigned int>(-1);
        constexpr unsigned int _Max      = _Max_elems < _Max_uint ? static_cast<unsigned int>(_Max_elems) : _Max_uint;

        constexpr unsigned int _Buf_incr = 16U;

        if (_Increase < _Buf_incr) {
            _Increase = _Buf_incr;
        }

        if (_Increase < (_Sz >> 1)) {
            _Increase = _Sz >> 1;
        }

        if (_Max <= _Increase || _Max - _Increase <= _Sz) {
            return _Max;
        }

        return _Sz + _Increase;
    }

    void _Expand2(const unsigned int _Min_increase) { // expand buffer by at least _Min_increase
        const unsigned int _Len = _Calculate_expansion(_Min_increase);
        if (_Len - _Sz < _Min_increase) {
            _Xregex_error(regex_constants::error_space);
        }
        _Elem* _Tmp = static_cast<_Elem*>(_CSTD realloc(_Chrs, sizeof(_Elem) * static_cast<size_t>(_Len)));
        if (!_Tmp) {
            _Xregex_error(regex_constants::error_space);
        }

        _Chrs = _Tmp;
        _Sz   = _Len;
    }

    unsigned int _Sz    = 0;
    unsigned int _Nchrs = 0;
    _Elem* _Chrs        = nullptr;
};

struct _Bitmap { // accelerator table for small character values
    _Bitmap() = default;

    template <class _Elem>
    void _Mark(_Elem _Ch) noexcept { // mark character _Ch
        static_assert(is_unsigned_v<_Elem>, "_Elem must be unsigned");
        unsigned int _Wide = _Ch;
        _Chrs[_Wide >> _Bmp_shift] |= (1 << (_Wide & _Bmp_mask));
    }

    template <class _Elem>
    bool _Find(_Elem _Ch) const noexcept {
        static_assert(is_unsigned_v<_Elem>, "_Elem must be unsigned");
        unsigned int _Wide = _Ch;
        return (_Chrs[_Wide >> _Bmp_shift] & (1 << (_Wide & _Bmp_mask))) != 0;
    }

private:
    unsigned char _Chrs[_Bmp_size]{};
};

template <class _Elem>
struct _Sequence { // holds sequences of _Sz elements
    explicit _Sequence(unsigned int _Len) noexcept : _Sz(_Len) {}

    unsigned int _Sz;
    _Buf<_Elem> _Data;
    _Sequence* _Next = nullptr;
};

class _Node_base { // base class for all nfa nodes
public:
    explicit _Node_base(_Node_type _Ty, _Node_flags _Fl = _Fl_none) noexcept : _Kind(_Ty), _Flags(_Fl) {}

    _Node_type _Kind;
    _Node_flags _Flags;
    _Node_base* _Next = nullptr;
    _Node_base* _Prev = nullptr;

    virtual ~_Node_base() noexcept {}
};

inline void _Destroy_node(_Node_base* _Nx, _Node_base* _Ne = nullptr) noexcept { // destroy sublist of nodes
    while (_Nx != _Ne && _Nx) { // destroy node
        _Node_base* _Tmp = _Nx;
        _Nx              = _Nx->_Next;
        _Tmp->_Next      = nullptr;
        delete _Tmp;
    }
}

class _Root_node : public _Node_base { // root of parse tree
public:
    _Root_node() noexcept : _Node_base(_N_begin) {
        static_assert(sizeof(_Refs) == sizeof(_Atomic_counter_t), "invalid _Refs size");
    }

    regex_constants::syntax_option_type _Fl{};
    unsigned int _Loops = 0;
    unsigned int _Marks = 0;
    unsigned int _Refs  = 0;
};

class _Node_end_group : public _Node_base { // node that marks end of a group
public:
    _Node_end_group(_Node_type _Ty, _Node_flags _Fl, _Node_base* _Bx) noexcept : _Node_base(_Ty, _Fl), _Back(_Bx) {}

    _Node_base* _Back;
};

class _Node_assert : public _Node_base { // node that holds an ECMAScript assertion
public:
    explicit _Node_assert(_Node_type _Ty, _Node_flags _Fl = _Fl_none) noexcept : _Node_base(_Ty, _Fl) {}

    ~_Node_assert() noexcept {
        _Destroy_node(_Child);
    }

    _Node_base* _Child = nullptr;
};

class _Node_capture : public _Node_base { // node that marks beginning of a capture group
public:
    explicit _Node_capture(unsigned int _Ix) noexcept : _Node_base(_N_capture, _Fl_none), _Idx(_Ix) {}

    unsigned int _Idx;
};

class _Node_back : public _Node_base { // node that holds a back reference
public:
    explicit _Node_back(unsigned int _Ix) noexcept : _Node_base(_N_back, _Fl_none), _Idx(_Ix) {}

    unsigned int _Idx;
};

template <class _Elem>
class _Node_str : public _Node_base { // node that holds text
public:
    explicit _Node_str(_Node_flags _Fl = _Fl_none) noexcept : _Node_base(_N_str, _Fl) {}

    _Buf<_Elem> _Data;
};

template <class _Elem, class _RxTraits>
class _Node_class : public _Node_base { // node that holds a character class (POSIX bracket expression)
public:
    explicit _Node_class(_Node_type _Ty = _N_class, _Node_flags _Fl = _Fl_none) noexcept : _Node_base(_Ty, _Fl) {}

    ~_Node_class() noexcept {
        _Tidy(_Coll);
        delete _Small;
        delete _Large;
        delete _Ranges;
        _Tidy(_Equiv);
    }

    void _Tidy(_Sequence<_Elem>* _Head) noexcept { // clean up a list of sequences
        while (_Head) { // delete the head of the list
            _Sequence<_Elem>* _Temp = _Head;
            _Head                   = _Head->_Next;
            delete _Temp;
        }
    }

    _Sequence<_Elem>* _Coll = nullptr;
    _Bitmap* _Small         = nullptr;
    _Buf<_Elem>* _Large     = nullptr;
    _Buf<_Elem>* _Ranges    = nullptr;
    typename _RxTraits::char_class_type _Classes{};
    _Sequence<_Elem>* _Equiv = nullptr;
};

class _Node_endif : public _Node_base { // node that marks the end of an alternative
public:
    _Node_endif() noexcept : _Node_base(_N_endif, _Fl_none) {}
};

class _Node_if : public _Node_base { // node that marks the beginning of an alternative
public:
    explicit _Node_if(_Node_base* _End) noexcept
        : _Node_base(_N_if, _Fl_none), _Endif(static_cast<_Node_endif*>(_End)) {}

    ~_Node_if() noexcept {
        _Node_if* _Cur = _Child;
        while (_Cur) { // destroy branch
            _Node_if* _Tmp = _Cur;
            _Cur           = _Cur->_Child;
            _Tmp->_Child   = nullptr;
            _Destroy_node(_Tmp, _Endif);
        }
    }

    _Node_endif* _Endif;
    _Node_if* _Child = nullptr;
};

class _Node_rep;

class _Node_end_rep : public _Node_base { // node that marks the end of a repetition
public:
    _Node_end_rep() noexcept : _Node_base(_N_end_rep) {}

    _Node_rep* _Begin_rep = nullptr;

    _Node_end_rep& operator=(const _Node_end_rep&) = delete;
};

template <class _Diff>
struct _Loop_vals_v3_t { // storage for loop administration
    size_t _Loop_frame_idx    = 0;
    int _Loop_idx             = 0;
    unsigned int _Group_first = 0;
    _Diff _Loop_length{};
};

class _Node_rep : public _Node_base { // node that marks the beginning of a repetition
public:
    _Node_rep(bool _Greedy, int _Min_, int _Max_, _Node_end_rep* _End, unsigned int _Number) noexcept
        : _Node_base(_N_rep, _Greedy ? _Fl_greedy : _Fl_none), _Min(_Min_), _Max(_Max_), _End_rep(_End),
          _Loop_number(_Number) {}

    const int _Min;
    const int _Max; // non-negative if bounded, -1 if unbounded
    _Node_end_rep* _End_rep;
    unsigned int _Loop_number;
    int _Simple_loop = -1; // -1 undetermined, 0 contains if/do, 1 simple

    _Node_rep& operator=(const _Node_rep&) = delete;
};

enum class _Rx_char_class_kind : int { // must be aligned with corresponding _Node_flags
    _Positive  = 0,
    _Negated_w = _Fl_class_negated_w,
    _Negated_s = _Fl_class_negated_s,
    _Negated_d = _Fl_class_negated_d
};

template <class _FwdIt, class _Elem, class _RxTraits>
class _Builder2 { // provides operations used by _Parser2 to build the nfa
public:
    _Builder2(const _RxTraits& _Tr, regex_constants::syntax_option_type);
    void _Setlong();
    void _Tidy() noexcept;
    _Node_base* _Getmark() const;

    void _Add_bol();
    void _Add_eol();
    void _Add_wbound();
    void _Add_dot();
    void _Add_char(_Elem _Ch);
    void _Add_class();
    void _Add_char_to_class(_Elem _Ch);
    void _Add_range(_Elem, _Elem);
    void _Add_named_class(typename _RxTraits::char_class_type, _Rx_char_class_kind);
    void _Add_equiv(const _Elem*, const _Elem*);
    void _Add_coll(const _Elem*, const _Elem*);
    _Node_base* _Begin_group();
    void _End_group(_Node_base* _Back);
    _Node_base* _Begin_assert_group(bool);
    void _End_assert_group(_Node_base*);
    _Node_base* _Begin_capture_group(unsigned int _Idx);
    void _Add_backreference(unsigned int _Idx);
    _Node_base* _Begin_if(_Node_base* _Start);
    void _Else_if(_Node_base*, _Node_base*);
    void _Add_rep(int _Min, int _Max, bool _Greedy);
    void _Negate();
    _Root_node* _End_pattern();

private:
    _Node_base* _Link_node(_Node_base*);
    static void _Insert_node(_Node_base*, _Node_base*);
    _Node_base* _New_node(_Node_type _Kind);
    void _Add_str_node();
    void _Add_char_to_bitmap(unsigned char _Ch);
    void _Add_char_to_array(_Elem _Ch);
    void _Add_elts(_Node_class<_Elem, _RxTraits>*, typename _RxTraits::char_class_type, bool);
    void _Char_to_elts(const _Elem*, const _Elem*, _Sequence<_Elem>**);

    _Root_node* _Root;
    _Node_base* _Current;
    regex_constants::syntax_option_type _Flags;
    const _RxTraits& _Traits;

public:
    _Builder2(const _Builder2&)            = delete;
    _Builder2& operator=(const _Builder2&) = delete;
};

template <class _Ty, class _Alloc = allocator<_Ty>>
class _Rx_fixed_size_buffer {
public:
    using _Al_pointer       = _Alloc_ptr_t<_Alloc>;
    using _Al_const_pointer = typename allocator_traits<_Alloc>::const_pointer;

private:
    using _Al_size_type = _Alloc_size_t<_Alloc>;

    struct _Buffer_range {
        _Al_pointer _First{};
        _Al_pointer _Last{};
        bool _Allocated{false};
    };

public:
    explicit _Rx_fixed_size_buffer(const _Alloc& _Al = _Alloc{}) : _Mypair(_One_then_variadic_args_t{}, _Al) {}

    _Rx_fixed_size_buffer(const _Rx_fixed_size_buffer&)            = delete;
    _Rx_fixed_size_buffer(_Rx_fixed_size_buffer&&)                 = delete;
    _Rx_fixed_size_buffer& operator=(const _Rx_fixed_size_buffer&) = delete;
    _Rx_fixed_size_buffer& operator=(_Rx_fixed_size_buffer&&)      = delete;

    void _Initialize(void*& _Stack_buf, size_t& _Stack_size, const size_t _Size) {
        if (_Size == 0U) {
            return; // nothing to do
        }

        const auto _Bytes = _Size * sizeof(_Ty);

        if (_STD align(alignof(_Ty), _Bytes, _Stack_buf, _Stack_size)) {
            _Use_external_buf(_Stack_buf, _Size);

            _Stack_buf = static_cast<unsigned char*>(_Stack_buf) + _Bytes;
            _Stack_size -= _Bytes;
        } else {
            _Allocate_buf(_Size);
        }
    }

    ~_Rx_fixed_size_buffer() {
        auto& _Data = _Mypair._Myval2;
        if (_Data._Allocated) {
            auto& _Al = _Mypair._Get_first();
            _STD _Destroy_range(_Data._First, _Data._Last, _Al);
            _Al.deallocate(_Data._First, static_cast<_Al_size_type>(_Data._Last - _Data._First));
        } else {
            _STD _Destroy_range(_Data._First, _Data._Last);
        }
    }

    _NODISCARD _Ty& operator[](const size_t _Pos) {
        auto& _Data = _Mypair._Myval2;
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(
            _Pos < static_cast<size_t>(_Data._Last - _Data._First), "_Rx_fixed_size_buffer subscript out of range");
#endif
        return _Data._First[_Pos];
    }

    _NODISCARD const _Ty& operator[](const size_t _Pos) const {
        auto& _Data = _Mypair._Myval2;
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(
            _Pos < static_cast<size_t>(_Data._Last - _Data._First), "_Rx_fixed_size_buffer subscript out of range");
#endif
        return _Data._First[_Pos];
    }

    _NODISCARD _Al_pointer _Begin() {
        return _Mypair._Myval2._First;
    }

    _NODISCARD _Al_const_pointer _Begin() const {
        return _Mypair._Myval2._First;
    }

    _NODISCARD _Al_pointer _End() {
        return _Mypair._Myval2._Last;
    }

    _NODISCARD _Al_const_pointer _End() const {
        return _Mypair._Myval2._Last;
    }

    _NODISCARD size_t _Size() const {
        auto& _Data = _Mypair._Myval2;
        return static_cast<size_t>(_Data._Last - _Data._First);
    }

private:
    void _Use_external_buf(void* _Buf, size_t _Ty_size) {
        auto _Ty_first = _STD _Refancy<_Al_pointer>(reinterpret_cast<_Ty*>(_Buf));
        auto _Ty_last  = _Ty_first + _Ty_size;
        auto& _Data    = _Mypair._Myval2;
        _STD uninitialized_fill(_Ty_first, _Ty_last, _Ty{}); // uninitialized_value_construct() is C++17
        _Data._Allocated = false;
        _Data._First     = _Ty_first;
        _Data._Last      = _Ty_last;
    }

    void _Allocate_buf(size_t _Ty_size) {
        auto& _Al = _Mypair._Get_first();

        if (_Ty_size > size_t{PTRDIFF_MAX} || _Ty_size > allocator_traits<_Alloc>::max_size(_Al)) {
            _Xregex_error(regex_constants::error_stack);
        }

        auto _Al_size  = static_cast<_Al_size_type>(_Ty_size);
        auto _Ty_first = _Al.allocate(_Al_size);
        _Allocation_guard<_Alloc> _Guard{_Al, _Ty_first, _Al_size};
        auto& _Data      = _Mypair._Myval2;
        _Data._Last      = _STD _Uninitialized_value_construct_n(_Ty_first, _Ty_size, _Al);
        _Data._Allocated = true;
        _Data._First     = _Ty_first;
        _Guard._Ptr      = nullptr;
    }

    _Compressed_pair<_Alloc, _Buffer_range> _Mypair;
};

using _Rx_bitset_int_type = size_t;

template <class _Alloc = allocator<bool>>
class _Rx_fixed_size_bitset {
private:
    static constexpr size_t _Bits = sizeof(_Rx_bitset_int_type) * CHAR_BIT;

    using _Buffer_type = _Rx_fixed_size_buffer<_Rx_bitset_int_type, _Rebind_alloc_t<_Alloc, _Rx_bitset_int_type>>;

public:
    explicit _Rx_fixed_size_bitset(const _Alloc& _Al) : _Buffer(_Al) {}

    void _Initialize(void*& _Stack_buf, size_t& _Stack_size, const size_t _Bit_size) {
        const auto _Word_size = _Bit_size / _Bits + (_Bit_size % _Bits != 0U);
        _Buffer._Initialize(_Stack_buf, _Stack_size, _Word_size);
    }

    _NODISCARD bool _Get(const size_t _Pos) const {
        return (_Buffer[_Pos / _Bits] & static_cast<_Rx_bitset_int_type>(_Rx_bitset_int_type{1} << (_Pos % _Bits)))
            != _Rx_bitset_int_type{};
    }

    void _Clear(const size_t _Pos) {
        _Buffer[_Pos / _Bits] &= static_cast<_Rx_bitset_int_type>(~(_Rx_bitset_int_type{1} << (_Pos % _Bits)));
    }

    void _Set(const size_t _Pos) {
        _Buffer[_Pos / _Bits] |= static_cast<_Rx_bitset_int_type>(_Rx_bitset_int_type{1} << (_Pos % _Bits));
    }

    void _Clear_range_at_least_until(const size_t _First, const size_t _Last) {
        if (_First < _Last) {
            size_t _Buffer_first      = _First / _Bits;
            const size_t _Buffer_last = _Last / _Bits + (_Last % _Bits != 0U);

#if _ITERATOR_DEBUG_LEVEL != 0
            _STL_VERIFY(_Buffer_last <= _Buffer._Size(), "_Rx_fixed_size_bitset subscript out of range");
#endif

            _Buffer[_Buffer_first] &=
                static_cast<_Rx_bitset_int_type>((_Rx_bitset_int_type{1} << (_First % _Bits)) - 1U);

            ++_Buffer_first;
            if (_Buffer_first < _Buffer_last) {
                auto _Begin = _Buffer._Begin();
                _STD fill(_Begin + static_cast<ptrdiff_t>(_Buffer_first), _Begin + static_cast<ptrdiff_t>(_Buffer_last),
                    _Rx_bitset_int_type{});
            }
        }
    }

    _NODISCARD typename _Buffer_type::_Al_pointer _Buffer_begin() {
        return _Buffer._Begin();
    }

    _NODISCARD typename _Buffer_type::_Al_const_pointer _Buffer_begin() const {
        return _Buffer._Begin();
    }

    _NODISCARD typename _Buffer_type::_Al_pointer _Buffer_end() {
        return _Buffer._End();
    }

    _NODISCARD typename _Buffer_type::_Al_const_pointer _Buffer_end() const {
        return _Buffer._End();
    }

private:
    _Buffer_type _Buffer;
};

template <class _BidIt>
struct _Rx_capture_range_t { // stores a pair of iterators
    _BidIt _Begin{};
    _BidIt _End{};
};

template <class _BidIt, class _Alloc>
class _Tgt_state_v2_t { // holds the current state of the match
public:
    explicit _Tgt_state_v2_t(const _Alloc& _Al = _Alloc()) : _Grps(_Al), _Grp_valid(_Al) {}

    void _Copy_from(const _Tgt_state_v2_t& _Source) {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Source._Grps._End() - _Source._Grps._Begin() == _Grps._End() - _Grps._Begin(),
            "Source and destination must have same amount of storage for capture group ranges");
        _STL_VERIFY(_Source._Grp_valid._Buffer_end() - _Source._Grp_valid._Buffer_begin()
                        == _Grp_valid._Buffer_end() - _Grp_valid._Buffer_begin(),
            "Source and destination must have same amount of storage for capture group validity markers");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        _Cur = _Source._Cur;
        _STD copy(_Source._Grps._Begin(), _Source._Grps._End(), _Grps._Begin());
        _STD copy(_Source._Grp_valid._Buffer_begin(), _Source._Grp_valid._Buffer_end(), _Grp_valid._Buffer_begin());
    }

    _BidIt _Cur;
    _Rx_fixed_size_buffer<_Rx_capture_range_t<_BidIt>, _Rebind_alloc_t<_Alloc, _Rx_capture_range_t<_BidIt>>> _Grps;
    _Rx_fixed_size_bitset<_Rebind_alloc_t<_Alloc, bool>> _Grp_valid;
};

enum class _Rx_unwind_ops {
    _After_assert = 1,
    _After_neg_assert,
    _Disjunction_eval_alternative,
    _Do_nothing,
    _Loop_simple_nongreedy,
    _Loop_simple_greedy_firstrep,
    _Loop_simple_greedy_intermediaterep,
    _Loop_simple_greedy_lastrep,
    _Loop_nongreedy,
    _Loop_greedy,
    _Loop_restore_vals,
    _Capture_restore_begin,
    _Capture_restore_unmatched_end,
    _Capture_restore_matched_end,
    _Capture_restore_matched,
};

template <class _BidIt>
class _Rx_state_frame_t {
public:
    _Rx_unwind_ops _Code{};
    union {
        int _Loop_idx_sav;
        unsigned int _Capture_idx;
    };
    _Node_base* _Node{};
    _BidIt _Pos{};
    size_t _Loop_frame_idx_sav{};
};

template <class _Ty, class _Alloc = allocator<_Ty>>
class _Rx_small_vector {
private:
    using _Al_pointer       = _Alloc_ptr_t<_Alloc>;
    using _Al_const_pointer = typename allocator_traits<_Alloc>::const_pointer;
    using _Al_size_type     = _Alloc_size_t<_Alloc>;

    struct _Vector_state {
        _Al_pointer _First{};
        _Al_pointer _Last{};
        _Al_pointer _End{};
        bool _Allocated{false};
    };

public:
    _CONSTEXPR20 explicit _Rx_small_vector(const _Alloc& _Al = _Alloc{}) : _Mypair(_One_then_variadic_args_t{}, _Al) {}

    _Rx_small_vector(const _Rx_small_vector&)            = delete;
    _Rx_small_vector(_Rx_small_vector&&)                 = delete;
    _Rx_small_vector& operator=(const _Rx_small_vector&) = delete;
    _Rx_small_vector& operator=(_Rx_small_vector&&)      = delete;

    void _Initialize_and_consume_remaining_buffer(void*& _Stack_buf, size_t& _Stack_buf_size) {
        if (_STD align(alignof(_Ty), sizeof(_Ty), _Stack_buf, _Stack_buf_size)) {
            const size_t _Count = _Stack_buf_size / sizeof(_Ty); // must calculate after calling _STD align()

            auto& _Data        = _Mypair._Myval2;
            const auto _Ty_buf = reinterpret_cast<_Ty*>(_Stack_buf);
            _Data._First       = _STD _Refancy(_Ty_buf);
            _Data._Last        = _Data._First;
            _Data._End         = _STD _Refancy(_Ty_buf + _Count);
        }

        _Stack_buf      = nullptr;
        _Stack_buf_size = 0;
    }

    _CONSTEXPR20 ~_Rx_small_vector() {
        auto& _Data = _Mypair._Myval2;
        if (_Data._Allocated) {
            auto& _Al = _Mypair._Get_first();
            _STD _Destroy_range(_Data._First, _Data._Last, _Al);
            _Al.deallocate(_Data._First, static_cast<_Al_size_type>(_Data._End - _Data._First));
        } else {
            _STD _Destroy_range(_Data._First, _Data._Last);
        }
    }

    _NODISCARD _Ty& operator[](const size_t _Pos) {
        auto& _Data = _Mypair._Myval2;
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Pos < static_cast<size_t>(_Data._Last - _Data._First), "_Rx_small_vector subscript out of range");
#endif
        return _Data._First[_Pos];
    }

    _NODISCARD const _Ty& operator[](const size_t _Pos) const {
        auto& _Data = _Mypair._Myval2;
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Pos < static_cast<size_t>(_Data._Last - _Data._First), "_Rx_small_vector subscript out of range");
#endif
        return _Data._First[_Pos];
    }

    void _Push_back(_Ty&& _Val) {
        auto& _Data = _Mypair._Myval2;
        if (_Data._Last == _Data._End) {
            _Realloc_buf();
        }

        if (_Data._Allocated) {
            allocator_traits<_Alloc>::construct(
                _Mypair._Get_first(), _STD _Unfancy(_Data._Last), _STD forward<_Ty>(_Val));
        } else {
            _STD _Construct_in_place(*_Data._Last, _STD forward<_Ty>(_Val));
        }
        ++_Data._Last;
    }

    _NODISCARD _CONSTEXPR20 size_t _Max_size() const noexcept {
        const auto _Max_capacity = (_STD min) (static_cast<_Al_size_type>(_STD _Max_limit<_Iter_diff_t<_Al_pointer>>()),
            allocator_traits<_Alloc>::max_size(_Mypair._Get_first()));
        if (_Max_capacity > size_t{PTRDIFF_MAX}) {
            return size_t{PTRDIFF_MAX};
        }
        return static_cast<size_t>(_Max_capacity);
    }

    _NODISCARD size_t _Size() const {
        auto& _Data = _Mypair._Myval2;
        return static_cast<size_t>(_Data._Last - _Data._First);
    }

    _NODISCARD _Al_pointer _Begin() {
        return _Mypair._Myval2._First;
    }

    _NODISCARD _Al_const_pointer _Begin() const {
        return _Mypair._Myval2._First;
    }

    _NODISCARD _Al_pointer _End() {
        return _Mypair._Myval2._Last;
    }

    _NODISCARD _Al_const_pointer _End() const {
        return _Mypair._Myval2._Last;
    }

private:
    _NODISCARD _Al_size_type _Calculate_new_capacity() {
        auto& _Data              = _Mypair._Myval2;
        const auto _Old_capacity = static_cast<_Al_size_type>(_Data._End - _Data._First);
        const auto _Max_capacity = static_cast<_Al_size_type>(_Max_size());

        const auto _Increase = (_STD max) (_Old_capacity / 2, _Al_size_type{1});

        if (_Max_capacity - _Increase < _Old_capacity) {
            return _Max_capacity;
        } else {
            return _Old_capacity + _Increase;
        }
    }

    void _Realloc_buf() {
        auto& _Al                = _Mypair._Get_first();
        auto& _Data              = _Mypair._Myval2;
        const auto _Old_first    = _Data._First;
        const auto _Old_last     = _Data._Last;
        const auto _Old_end      = _Data._End;
        const auto _Old_capacity = static_cast<_Al_size_type>(_Old_end - _Old_first);
        auto _New_capacity       = _Calculate_new_capacity();
        if (_Old_capacity >= _New_capacity) {
            _Xregex_error(regex_constants::error_stack);
        }

        const auto _New_first = _STD _Allocate_at_least_helper(_Al, _New_capacity);
        _Allocation_guard<_Alloc> _Guard{_Al, _New_first, _New_capacity};
        const auto _New_last = _STD _Uninitialized_move(_Old_first, _Old_last, _New_first, _Al);
        _Data._First         = _New_first;
        _Data._Last          = _New_last;
        _Data._End           = _New_first + static_cast<_Iter_diff_t<_Al_pointer>>(_New_capacity);
        _Guard._Ptr          = nullptr;

        if (_Data._Allocated) {
            _STD _Destroy_range(_Old_first, _Old_last, _Al);
            _Al.deallocate(_Old_first, _Old_capacity);
        } else {
            _Data._Allocated = true;
            _STD _Destroy_range(_Old_first, _Old_last);
        }
    }

    _Compressed_pair<_Alloc, _Vector_state> _Mypair;
};

template <class _Elem, class _RxTraits, class _It, class _Alloc>
class _Matcher3 { // provides ways to match a regular expression to a text sequence
private:
    using _Loop_vals_type   = _Loop_vals_v3_t<_Iter_diff_t<_It>>;
    using _Tgt_state_type   = _Tgt_state_v2_t<_It, allocator<_It>>;
    using _State_frame_type = _Rx_state_frame_t<_It>;

public:
    template <size_t _Stack_storage_size>
    _Matcher3(_It _Pfirst, _It _Plast, const _RxTraits& _Tr, _Root_node* _Re, unsigned int _Nx,
        regex_constants::syntax_option_type _Sf, regex_constants::match_flag_type _Mf,
        unsigned char (&_Stack_storage)[_Stack_storage_size])
        : _Traits(_Tr), _Begin(_Pfirst), _End(_Plast), _Sflags(_Sf), _Mflags(_Mf), _Ncap(_Nx),
          _Longest((_Re->_Flags & _Fl_longest) && !(_Mf & regex_constants::match_any)) {
        _Adl_verify_range(_Pfirst, _Plast);
        if (_Re->_Flags & _Fl_begin_needs_w) {
            _Char_class_w = _Lookup_char_class(static_cast<_Elem>('W'));
        }

        if (_Re->_Flags & _Fl_begin_needs_s) {
            _Char_class_s = _Lookup_char_class(static_cast<_Elem>('S'));
        }

        if (_Re->_Flags & _Fl_begin_needs_d) {
            _Char_class_d = _Lookup_char_class(static_cast<_Elem>('D'));
        }

        _Iter_diff_t<_It> _Input_length = _STD distance(_Pfirst, _Plast);
        _Frames_limit                   = _Calculate_frames_limit(_Input_length);
        _Complexity_limit               = _Calculate_complexity_limit(_Input_length);

        // TRANSITION, ABI, GH-6025:
        // The first two nodes are of types _N_begin and _N_capture with capturing group 0.
        // These nodes do not affect the state of the matcher and thus can be skipped immediately
        // before engaging the expensive NFA interpreter loop.
        _Start = _Re->_Next->_Next;

        {
            void* _Buf       = _Stack_storage;
            size_t _Buf_size = _Stack_storage_size;

            _Loop_vals._Initialize(_Buf, _Buf_size, _Re->_Loops);

            if (_Ncap > 1U) {
                _Tgt_state._Grps._Initialize(_Buf, _Buf_size, _Ncap - 1U);
                if (_Longest) {
                    _Res._Grps._Initialize(_Buf, _Buf_size, _Ncap - 1U);
                }

                _Tgt_state._Grp_valid._Initialize(_Buf, _Buf_size, _Ncap - 1U);
                if (_Longest) {
                    _Res._Grp_valid._Initialize(_Buf, _Buf_size, _Ncap - 1U);
                }
            }

            _Frames._Initialize_and_consume_remaining_buffer(_Buf, _Buf_size);
        }

// sanitize multiline mode setting
#if _REGEX_LEGACY_MULTILINE_MODE
        _Sflags |= regex_constants::multiline; // old matcher applied multiline mode for all grammars
#else // ^^^ _REGEX_LEGACY_MULTILINE_MODE / !_REGEX_LEGACY_MULTILINE_MODE vvv
        if (_Sflags & regex_constants::_Any_posix) { // multiline mode is ECMAScript-only
            _Sflags &= ~regex_constants::multiline;
        }
#endif // ^^^ !_REGEX_LEGACY_MULTILINE_MODE ^^^
    }

    void _Setf(regex_constants::match_flag_type _Mf) { // set specified flags
        _Mflags |= _Mf;
    }

    void _Clearf(regex_constants::match_flag_type _Mf) { // clear specified flags
        _Mflags &= ~_Mf;
    }

    bool _Match(_It _Pfirst, bool _Full_match) { // try to match
        _Begin = _Pfirst;
        return _Match(_Full_match);
    }

    bool _Match(bool _Full_match) { // try to match
        _Tgt_state._Cur = _Begin;
        _Full           = _Full_match;
        _Frames_count   = 0;
        _Matched        = false;

        return _Match_pat(_Start) || _Matched;
    }

    template <class _BidIt, class _Alsubmatch>
    void _Copy_captures(match_results<_BidIt, _Alsubmatch>& _Matches);

    _It _Skip(_It _First, _It _Last, const _Node_base* _Node_arg = nullptr, unsigned int _Recursion_depth = 0U);

private:
    long long _Complexity_limit;
    _Tgt_state_type _Tgt_state;
    _Tgt_state_type _Res;
    _Rx_fixed_size_buffer<_Loop_vals_type> _Loop_vals;
    _Rx_small_vector<_State_frame_type> _Frames;
    size_t _Frames_count;
    size_t _Frames_limit;
    _Node_base* _Start;
    const _RxTraits& _Traits;
    _It _Begin;
    _It _End;
    regex_constants::syntax_option_type _Sflags;
    regex_constants::match_flag_type _Mflags;
    unsigned int _Ncap;
    typename _RxTraits::char_class_type _Char_class_w{};
    typename _RxTraits::char_class_type _Char_class_s{};
    typename _RxTraits::char_class_type _Char_class_d{};
    bool _Matched = false;
    bool _Longest;
    bool _Full;

    size_t _Push_frame(_Rx_unwind_ops _Code, _Node_base* _Node);

    size_t _Calculate_frames_limit(_Iter_diff_t<_It> _Input_length);
    long long _Calculate_complexity_limit(_Iter_diff_t<_It> _Input_length);
    void _Increase_complexity_count(_Iter_diff_t<_It> _Count);

    void _Prepare_rep(_Node_rep*);
    bool _Find_first_inner_capture_group(_Node_base*, _Loop_vals_type*);
    void _Reset_capture_groups(unsigned int _First);
    _It _Do_class(const _Node_base*, _It);
    bool _Match_pat(_Node_base*);
    bool _Better_match();
    bool _Is_wbound() const;
    typename _RxTraits::char_class_type _Lookup_char_class(_Elem) const;

public:
    _Matcher3(const _Matcher3&)            = delete;
    _Matcher3& operator=(const _Matcher3&) = delete;
};

enum _Prs_ret { // indicate class element type
    _Prs_none,
    _Prs_chr,
    _Prs_set
};

enum class _Lex_mode : unsigned char { _Default, _Character_class };

template <class _FwdIt, class _Elem, class _RxTraits>
class _Parser2 { // parse a regular expression
public:
    _Parser2(const _RxTraits& _Tr, _FwdIt _Pfirst, _FwdIt _Plast, regex_constants::syntax_option_type _Fx);
    _Root_node* _Compile();

private:
    unsigned int _Mark_count() const noexcept {
        return _Grp_idx + 1;
    }

    // lexing
    [[noreturn]] void _Error(regex_constants::error_type);

    bool _Is_esc(_FwdIt) const;
    void _Trans();
    void _Next();
    void _Expect(_Meta_type, regex_constants::error_type);

    // parsing
    int _Do_digits(int _Base, int _Initial, int _Count, regex_constants::error_type _Error_type);
    bool _DecimalDigits(regex_constants::error_type _Error_type, int _Initial = 0);
    void _HexDigits(int);
    bool _OctalDigits();
    _Prs_ret _Do_ex_class(_Meta_type);
    bool _CharacterClassEscape(bool);
    _Prs_ret _ClassEscape();
    _Prs_ret _ClassAtom(bool);
    void _ClassRanges();
    void _CharacterClass();
    bool _IdentityEscape(bool);
    bool _IsIdentityEscape(bool) const;
    bool _Do_ffn(_Elem);
    bool _Do_ffnx(_Elem);
    bool _CharacterEscape(bool);
    void _AtomEscape();
    void _Do_capture_group();
    void _Do_noncapture_group();
    void _Do_assert_group(bool);
    bool _Wrapped_disjunction();
    void _Quantifier();
    bool _Alternative();
    void _Disjunction();
    void _Calculate_loop_simplicity(_Node_base* _Nx, _Node_base* _Ne, _Node_rep* _Outer_rep, bool _Nonreentrant);

    _FwdIt _Pat;
    _FwdIt _End;
    unsigned int _Grp_idx = 0;
    int _Disj_count       = 0;
    vector<bool> _Finished_grps;
    _Builder2<_FwdIt, _Elem, _RxTraits> _Nfa;
    const _RxTraits& _Traits;
    unsigned long long _L_flags;
    regex_constants::syntax_option_type _Flags;
    int _Val;
    _Meta_type _Mchar;
    _Lex_mode _Mode = _Lex_mode::_Default;
    _Elem _Char;
    _Elem _Unescaped_char;
};

enum _Lang_flags2 : unsigned long long { // describe language properties
    _L_ext_rep    = 0x000000001ULL, // + and ? repetitions
    _L_alt_pipe   = 0x000000002ULL, // uses '|' for alternation
    _L_alt_nl     = 0x000000004ULL, // newlines outside parentheses/brackets represent alternations (grep, egrep)
    _L_nex_grp    = 0x000000008ULL, // has non-escaped capture groups
    _L_nex_rep    = 0x000000010ULL, // has non-escaped repeats
    _L_nc_asrt    = 0x000000020ULL, // has non-capture groups (?:xxx) and generalized assertions (?=xxx), (?!xxx)
    _L_asrt_wrd   = 0x000000040ULL, // has word boundary assertions (\b, \B)
    _L_bckr       = 0x000000080ULL, // has backreferences (ERE doesn't)
    _L_lim_bckr   = 0x000000100ULL, // has limited backreferences (BRE \1-\9)
    _L_non_greedy = 0x000000200ULL, // has non-greedy repeats
    _L_esc_uni    = 0x000000400ULL, // has Unicode escape sequences
    _L_esc_hex    = 0x000000800ULL, // has hexadecimal escape sequences
    _L_esc_oct    = 0x000001000ULL, // has octal escape sequences (awk)
    _L_esc_bsp    = 0x000002000ULL, // has backspace escape in character classes
    _L_esc_ffnx   = 0x000004000ULL, // has extra file escapes (\a and \b) (awk)
    _L_esc_ffn    = 0x000008000ULL, // has limited file escapes (\f \n \r \t \v)
    _L_esc_wsd    = 0x000010000ULL, // has w, s, and d character set escapes
    _L_esc_ctrl   = 0x000020000ULL, // has control escape
    _L_no_nl      = 0x000040000ULL, // newlines within parentheses/brackets are syntax errors (grep, egrep)
    _L_bzr_chr    = 0x000080000ULL, // \0 is a valid character constant
    _L_grp_esc    = 0x000100000ULL, // \ is special character in group
    _L_ident_ECMA = 0x000200000ULL, // ECMA identity escape (not identifierpart)
    _L_ident_ERE  = 0x000400000ULL, // ERE identity escape (.[\*^$, plus {+?}()
    _L_ident_awk  = 0x000800000ULL, // awk identity escape (awk additionally supports " and / characters)
    _L_anch_rstr  = 0x001000000ULL, // anchor restricted to beginning/end (BRE)
    _L_star_beg   = 0x002000000ULL, // star okay at beginning of RE/expr (BRE)
    _L_empty_grp  = 0x004000000ULL, // empty group allowed (ERE prohibits "()")
    _L_paren_bal  = 0x008000000ULL, // ')'/'}' special only after '('/'{' (ERE)
    _L_brk_bal    = 0x010000000ULL, // ']' special only after '[' (ERE, BRE)
    _L_brk_rstr   = 0x020000000ULL, // ']' not special when first character in set (ERE, BRE)
    _L_dsh_rstr   = 0x040000000ULL, // '-' forbidden at range start in set except when first character (ERE, BRE)
    _L_mtch_long  = 0x080000000ULL, // find longest match (ERE, BRE)
};

class _Regex_base : public _Container_base { // base class for basic_regex to construct and destroy proxy
public:
#if 0 < _ITERATOR_DEBUG_LEVEL
    _Regex_base() { // construct proxy
        this->_Myproxy = new _Container_proxy;
        this->_Myproxy->_Mycont = this;
    }

    ~_Regex_base() noexcept {
        this->_Orphan_all();
        delete this->_Myproxy;
        this->_Myproxy = nullptr;
    }
#endif // 0 < _ITERATOR_DEBUG_LEVEL
};

_EXPORT_STD template <class _Elem, class _RxTraits = regex_traits<_Elem>>
class basic_regex : public _Regex_base { // regular expression
public:
    using value_type  = _Elem;
    using traits_type = _RxTraits;
    using locale_type = typename _RxTraits::locale_type;
    using string_type = typename _RxTraits::string_type;
    using flag_type   = regex_constants::syntax_option_type;

    static constexpr flag_type icase      = regex_constants::icase;
    static constexpr flag_type nosubs     = regex_constants::nosubs;
    static constexpr flag_type optimize   = regex_constants::optimize;
    static constexpr flag_type collate    = regex_constants::collate;
    static constexpr flag_type ECMAScript = regex_constants::ECMAScript;
    static constexpr flag_type basic      = regex_constants::basic;
    static constexpr flag_type extended   = regex_constants::extended;
    static constexpr flag_type awk        = regex_constants::awk;
    static constexpr flag_type grep       = regex_constants::grep;
    static constexpr flag_type egrep      = regex_constants::egrep;
    static constexpr flag_type multiline  = regex_constants::multiline;

    basic_regex() = default; // construct empty object

    explicit basic_regex(_In_z_ const _Elem* _Ptr, flag_type _Flags = regex_constants::ECMAScript) {
        _Reset(_Ptr, _Ptr + _RxTraits::length(_Ptr), _Flags);
    }

    basic_regex(_In_reads_(_Count) const _Elem* _Ptr, size_t _Count, flag_type _Flags = regex_constants::ECMAScript) {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Ptr != nullptr || _Count == 0, "constructing basic_regex from an invalid range");
#endif // ^^^ _ITERATOR_DEBUG_LEVEL != 0 ^^^
        _Reset(_Ptr, _Ptr + _Count, _Flags);
    }

    template <class _STtraits, class _STalloc>
    explicit basic_regex(
        const basic_string<_Elem, _STtraits, _STalloc>& _Str, flag_type _Flags = regex_constants::ECMAScript) {
        _Reset(_Str.data(), _Str.data() + static_cast<ptrdiff_t>(_Str.size()), _Flags);
    }

    template <class _InIt>
    basic_regex(_InIt _First, _InIt _Last, flag_type _Flags) {
        _Adl_verify_range(_First, _Last);
        _Reset(_Get_unwrapped(_First), _Get_unwrapped(_Last), _Flags);
    }

    template <class _InIt>
    basic_regex(_InIt _First, _InIt _Last) {
        _Adl_verify_range(_First, _Last);
        _Reset(_Get_unwrapped(_First), _Get_unwrapped(_Last), regex_constants::ECMAScript);
    }

    basic_regex(const basic_regex& _Right)
#if _ENHANCED_REGEX_VISUALIZER
        : _Traits(_Right._Traits), _Visualization(_Right._Visualization)
#else
        : _Traits(_Right._Traits)
#endif
    { // construct copy of _Right
        _Reset(_Right._Rep);
    }

    basic_regex(initializer_list<_Elem> _Ilist, flag_type _Flags = regex_constants::ECMAScript) {
        _Reset(_Ilist.begin(), _Ilist.end(), _Flags);
    }

    basic_regex& operator=(initializer_list<_Elem> _Ilist) { // replace with regular expression in initializer_list
        return assign(_Ilist);
    }

    basic_regex& assign(initializer_list<_Elem> _Ilist, flag_type _Flags = regex_constants::ECMAScript) {
        // replace with regular expression in initializer_list
        _Reset(_Ilist.begin(), _Ilist.end(), _Flags);
        return *this;
    }

    basic_regex(basic_regex&& _Right) noexcept {
        _Assign_rv(_STD move(_Right));
    }

    basic_regex& operator=(basic_regex&& _Right) noexcept {
        _Assign_rv(_STD move(_Right));
        return *this;
    }

    void _Assign_rv(basic_regex&& _Right) {
        if (this != _STD addressof(_Right)) { // clear this and steal from _Right
            _Tidy();

#if _ENHANCED_REGEX_VISUALIZER
            _Visualization = _STD move(_Right._Visualization);
#endif // _ENHANCED_REGEX_VISUALIZER

            _Rep        = _Right._Rep;
            _Right._Rep = nullptr;
        }
    }

    basic_regex& assign(basic_regex&& _Right) noexcept {
        _Assign_rv(_STD move(_Right));
        return *this;
    }

    ~basic_regex() noexcept {
        _Tidy();

#if _MSVC_STL_DESTRUCTOR_TOMBSTONES
        const auto _Tombstone{reinterpret_cast<_Root_node*>(_MSVC_STL_UINTPTR_TOMBSTONE_VALUE)};
        _Rep = _Tombstone;
#endif // _MSVC_STL_DESTRUCTOR_TOMBSTONES
    }

    basic_regex& operator=(const basic_regex& _Right) {
        return assign(_Right);
    }

    basic_regex& operator=(_In_z_ const _Elem* _Ptr) {
        _Reset(_Ptr, _Ptr + _RxTraits::length(_Ptr), ECMAScript);
        return *this;
    }

    template <class _STtraits, class _STalloc>
    basic_regex& operator=(const basic_string<_Elem, _STtraits, _STalloc>& _Str) {
        _Reset(_Str.data(), _Str.data() + static_cast<ptrdiff_t>(_Str.size()), ECMAScript);
        return *this;
    }

    unsigned int _Loop_count() const noexcept {
        return _Rep ? _Rep->_Loops : 0;
    }

    _NODISCARD unsigned int mark_count() const noexcept /* strengthened */ {
        return _Rep ? _Rep->_Marks - 1 : 0;
    }

    basic_regex& assign(const basic_regex& _Right) {
#if _ENHANCED_REGEX_VISUALIZER
        _Visualization = _Right._Visualization;
#endif // _ENHANCED_REGEX_VISUALIZER

        _Reset(_Right._Rep);
        return *this;
    }

    basic_regex& assign(_In_z_ const _Elem* _Ptr, flag_type _Flags = regex_constants::ECMAScript) {
        return assign(_Ptr, _RxTraits::length(_Ptr), _Flags);
    }

    basic_regex& assign(
        _In_reads_(_Count) const _Elem* _Ptr, size_t _Count, flag_type _Flags = regex_constants::ECMAScript) {
        _Reset(_Ptr, _Ptr + _Count, _Flags);
        return *this;
    }

    template <class _STtraits, class _STalloc>
    basic_regex& assign(
        const basic_string<_Elem, _STtraits, _STalloc>& _Str, flag_type _Flags = regex_constants::ECMAScript) {
        _Reset(_Str.data(), _Str.data() + static_cast<ptrdiff_t>(_Str.size()), _Flags);
        return *this;
    }

    template <class _InIt>
    basic_regex& assign(_InIt _First, _InIt _Last, flag_type _Flags = regex_constants::ECMAScript) {
        _Adl_verify_range(_First, _Last);
        _Reset(_Get_unwrapped(_First), _Get_unwrapped(_Last), _Flags);
        return *this;
    }

    _NODISCARD flag_type flags() const noexcept /* strengthened */ {
        return _Rep ? _Rep->_Fl : flag_type{};
    }

    locale_type imbue(locale_type _Loc) { // clear regular expression and set locale to argument
        _Tidy();
        return _Traits.imbue(_Loc);
    }

    locale_type getloc() const {
        return _Traits.getloc();
    }

    void swap(basic_regex& _Right) noexcept /* strengthened */ {
        _STD swap(_Rep, _Right._Rep);

#if _ENHANCED_REGEX_VISUALIZER
        _Visualization.swap(_Right._Visualization);
#endif // _ENHANCED_REGEX_VISUALIZER
    }

    _Root_node* _Get() const noexcept {
        return _Rep;
    }

    bool _Empty() const noexcept {
        return _Rep == nullptr;
    }

    const _RxTraits& _Get_traits() const noexcept {
        return _Traits;
    }

private:
    _Root_node* _Rep = nullptr;
    _RxTraits _Traits;

#if _ENHANCED_REGEX_VISUALIZER
    basic_string<_Elem> _Visualization;
#endif // _ENHANCED_REGEX_VISUALIZER

    void _Tidy() noexcept { // free all storage
        if (_Rep && _MT_DECR(reinterpret_cast<_Atomic_counter_t&>(_Rep->_Refs)) == 0) {
            _Destroy_node(_Rep);
        }

        _Rep = nullptr;
    }

    template <class _InIt>
    void _Reset(_InIt _First, _InIt _Last, flag_type _Flags) {
        // build regular expression from iterator range
        if constexpr (_Is_ranges_fwd_iter_v<_InIt>) {
#if _ENHANCED_REGEX_VISUALIZER
            _Visualization.assign(_First, _Last);
#endif // _ENHANCED_REGEX_VISUALIZER

            _Parser2<_InIt, _Elem, _RxTraits> _Prs(_Traits, _First, _Last, _Flags);
            _Root_node* _Rx = _Prs._Compile();
            _Reset(_Rx);
        } else {
            static_assert(_Is_ranges_input_iter_v<_InIt>, "Iterators must be at least input iterators");

            basic_string<_Iter_value_t<_InIt>> _Str(_First, _Last);

            _Reset(_Str.data(), _Str.data() + static_cast<ptrdiff_t>(_Str.size()), _Flags);
        }
    }

    void _Reset(_Root_node* _Rx) { // build regular expression holding root node _Rx
        if (_Rx) {
            _MT_INCR(reinterpret_cast<_Atomic_counter_t&>(_Rx->_Refs));
        }

        _Tidy();
        _Rep = _Rx;
    }
};

#if _HAS_CXX17
template <class _FwdIt>
basic_regex(_FwdIt, _FwdIt, regex_constants::syntax_option_type = regex_constants::ECMAScript)
    -> basic_regex<typename iterator_traits<_FwdIt>::value_type>;
#endif // _HAS_CXX17

_EXPORT_STD template <class _Elem, class _RxTraits>
void swap(basic_regex<_Elem, _RxTraits>& _Left, basic_regex<_Elem, _RxTraits>& _Right) noexcept /* strengthened */ {
    _Left.swap(_Right);
}

_EXPORT_STD template <class _BidIt, class _Alloc>
void swap(match_results<_BidIt, _Alloc>& _Left, match_results<_BidIt, _Alloc>& _Right)
    noexcept(noexcept(_Left.swap(_Right))) /* strengthened */ {
    _Left.swap(_Right);
}

_EXPORT_STD using regex   = basic_regex<char>;
_EXPORT_STD using wregex  = basic_regex<wchar_t>;
_EXPORT_STD using cmatch  = match_results<const char*>;
_EXPORT_STD using wcmatch = match_results<const wchar_t*>;
_EXPORT_STD using smatch  = match_results<string::const_iterator>;
_EXPORT_STD using wsmatch = match_results<wstring::const_iterator>;

template <class _BidIt, class _Alloc, class _InIt, class _OutIt>
_OutIt _Format_default(const match_results<_BidIt, _Alloc>& _Match, _OutIt _Out, _InIt _First, _InIt _Last,
    regex_constants::match_flag_type) { // format with ECMAScript rules
    while (_First != _Last) { // process one character or escape sequence
        if (*_First != '$') {
            *_Out++ = *_First++;
        } else if (++_First == _Last) {
            *_Out++ = '$'; // preserve $ at end
        } else if (*_First == '$') { // replace $$
            *_Out++ = '$';
            ++_First;
        } else if (*_First == '`') { // replace $`
            _Out = _STD copy(_Match.prefix().first, _Match.prefix().second, _Out);
            ++_First;
        } else if (*_First == '\'') { // replace $'
            _Out = _STD copy(_Match.suffix().first, _Match.suffix().second, _Out);
            ++_First;
        } else if (*_First == '&') { // replace $&
            ++_First;
            if (_Match.size() != 0) {
                _Out = _STD copy(_Match._At(0).first, _Match._At(0).second, _Out);
            }
        } else if ('0' <= *_First && *_First <= '9') { // replace capture group descriptors $n, $nn
            auto _Num              = static_cast<unsigned int>(*_First++ - '0');
            const bool _Two_digits = _First != _Last && '0' <= *_First && *_First <= '9';
            if (_Two_digits) { // process second digit
                _Num *= 10;
                _Num += static_cast<unsigned int>(*_First++ - '0');
            }

            if (_Num == 0) { // preserve $0, $00
                *_Out++ = '$';
                *_Out++ = '0';
                if (_Two_digits) {
                    *_Out++ = '0';
                }
            } else if (_Num < _Match.size()) {
                _Out = _STD copy(_Match._At(_Num).first, _Match._At(_Num).second, _Out);
            }
        } else { // replace $x
            *_Out++ = '$';
            *_Out++ = *_First++;
        }
    }
    return _Out;
}

template <class _BidIt, class _Alloc, class _InIt, class _OutIt>
_OutIt _Format_sed(const match_results<_BidIt, _Alloc>& _Match, _OutIt _Out, _InIt _First, _InIt _Last,
    regex_constants::match_flag_type) { // format with sed rules
    while (_First != _Last) { // process one character or escape sequence
        if (*_First == '&') { // replace with full match
            ++_First;
            if (_Match.size() != 0) {
                _Out = _STD copy(_Match._At(0).first, _Match._At(0).second, _Out);
            }
        } else if (*_First != '\\') {
            *_Out++ = *_First++;
        } else if (++_First != _Last) {
            if ('0' <= *_First && *_First <= '9') { // replace \n, including \0
                const auto _Num = static_cast<unsigned int>(*_First++ - '0');
                if (_Num < _Match.size()) {
                    _Out = _STD copy(_Match._At(_Num).first, _Match._At(_Num).second, _Out);
                }
            } else {
                *_Out++ = *_First++; // replace \x, including \\, \&
            }
        }
    }

    return _Out;
}

template <class _BidIt, class _Alloc, class _Elem, class _RxTraits, class _It>
bool _Regex_match1(_It _First, _It _Last, match_results<_BidIt, _Alloc>* _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs,
    bool _Full) { // try to match regular expression to target text
    static_assert(_Is_ranges_bidi_iter_v<_It>,
        "regex_match requires bidirectional iterators or stronger. See N5014 [re.alg.match]/1.");

    if (_Matches) { // clear _Matches before doing work
        _Matches->_Ready = true;
        _Matches->_Resize(0);
    }

    if (_Re._Empty()) {
        return false;
    }

    alignas(_Loop_vals_v3_t<_Iter_diff_t<_It>>) alignas(_Rx_capture_range_t<_It>) //
        alignas(_Rx_state_frame_t<_It>) unsigned char _Stackbuf[4096];
    _Matcher3<_Elem, _RxTraits, _It, void> _Mx(
        _First, _Last, _Re._Get_traits(), _Re._Get(), _Re.mark_count() + 1, _Re.flags(), _Flgs, _Stackbuf);

    if (!_Mx._Match(_Full)) {
        return false;
    }

    if (_Matches) {
        _Mx._Copy_captures(*_Matches);
        _Matches->_Org           = _First;
        _Matches->_Pfx().first   = _First;
        _Matches->_Pfx().matched = _Matches->_Pfx().first != _Matches->_Pfx().second;
    }

    return true;
}

_EXPORT_STD template <class _BidIt, class _Alloc, class _Elem, class _RxTraits>
bool regex_match(_BidIt _First, _BidIt _Last, match_results<_BidIt, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    _Adl_verify_range(_First, _Last);
    return _Regex_match1(_First, _Last, _STD addressof(_Matches), _Re, _Flgs, true);
}

_EXPORT_STD template <class _BidIt, class _Elem, class _RxTraits>
_NODISCARD bool regex_match(_BidIt _First, _BidIt _Last, const basic_regex<_Elem, _RxTraits>& _Re,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    _Adl_verify_range(_First, _Last);
    return _Regex_match1(_Get_unwrapped(_First), _Get_unwrapped(_Last),
        static_cast<match_results<_Unwrapped_t<const _BidIt&>>*>(nullptr), _Re, _Flgs | regex_constants::match_any,
        true);
}

_EXPORT_STD template <class _Elem, class _RxTraits>
_NODISCARD bool regex_match(_In_z_ const _Elem* _Str, const basic_regex<_Elem, _RxTraits>& _Re,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    const _Elem* _Last = _Str + char_traits<_Elem>::length(_Str);
    return _Regex_match1(
        _Str, _Last, static_cast<match_results<const _Elem*>*>(nullptr), _Re, _Flgs | regex_constants::match_any, true);
}

_EXPORT_STD template <class _Elem, class _Alloc, class _RxTraits>
bool regex_match(_In_z_ const _Elem* _Str, match_results<const _Elem*, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    const _Elem* _Last = _Str + char_traits<_Elem>::length(_Str);
    return _Regex_match1(_Str, _Last, _STD addressof(_Matches), _Re, _Flgs, true);
}

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Alloc, class _Elem, class _RxTraits>
bool regex_match(const basic_string<_Elem, _StTraits, _StAlloc>& _Str,
    match_results<typename basic_string<_Elem, _StTraits, _StAlloc>::const_iterator, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    return _Regex_match1(_Str.begin(), _Str.end(), _STD addressof(_Matches), _Re, _Flgs, true);
}

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Alloc, class _Elem, class _RxTraits>
bool regex_match(const basic_string<_Elem, _StTraits, _StAlloc>&&,
    match_results<typename basic_string<_Elem, _StTraits, _StAlloc>::const_iterator, _Alloc>&,
    const basic_regex<_Elem, _RxTraits>&, regex_constants::match_flag_type = regex_constants::match_default) = delete;

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Elem, class _RxTraits>
_NODISCARD bool regex_match(const basic_string<_Elem, _StTraits, _StAlloc>& _Str,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // try to match regular expression to target text
    return _Regex_match1(_Str.data(), _Str.data() + _Str.size(), static_cast<match_results<const _Elem*>*>(nullptr),
        _Re, _Flgs | regex_constants::match_any, true);
}

template <class _BidIt, class _Alloc, class _Elem, class _RxTraits, class _It>
bool _Regex_search2(_It _First, _It _Last, match_results<_BidIt, _Alloc>* _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs, _It _Org) {
    // search for regular expression match in target text
    static_assert(_Is_ranges_bidi_iter_v<_It>,
        "regex_search requires bidirectional iterators or stronger. See N5014 [re.alg.search]/1.");

    if (_Matches) { // clear _Matches before doing work
        _Matches->_Ready = true;
        _Matches->_Resize(0);
    }

    if (_Re._Empty()) {
        return false;
    }

    bool _Found      = false;
    const _It _Begin = _First;
    if ((_Flgs & regex_constants::_Skip_zero_length) && _First != _Last) {
        ++_First;
    }

    alignas(_Loop_vals_v3_t<_Iter_diff_t<_It>>) alignas(_Rx_capture_range_t<_It>) //
        alignas(_Rx_state_frame_t<_It>) unsigned char _Stackbuf[4096];
    _Matcher3<_Elem, _RxTraits, _It, void> _Mx(
        _First, _Last, _Re._Get_traits(), _Re._Get(), _Re.mark_count() + 1, _Re.flags(), _Flgs, _Stackbuf);

    if (_Mx._Match(false)) {
        _Found = true;
    } else if (_First != _Last && !(_Flgs & regex_constants::match_continuous)) { // try more on suffixes
        _Mx._Setf(regex_constants::match_prev_avail);
        _Mx._Clearf(regex_constants::_Match_not_null);
        while ((_First = _Mx._Skip(++_First, _Last)) != _Last) {
            if (_Mx._Match(_First, false)) { // found match starting at _First
                _Found = true;
                break;
            }
        }

        if (!_Found && _Mx._Match(_Last, false)) {
            _Found = true;
        }
    }

    if (_Found && _Matches) { // update _Matches
        _Mx._Copy_captures(*_Matches);
        _Matches->_Org           = _Org;
        _Matches->_Pfx().first   = _Begin;
        _Matches->_Pfx().matched = _Matches->_Pfx().first != _Matches->_Pfx().second;
    }
    return _Found;
}

_EXPORT_STD template <class _BidIt, class _Alloc, class _Elem, class _RxTraits>
bool regex_search(_BidIt _First, _BidIt _Last, match_results<_BidIt, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    _Adl_verify_range(_First, _Last);
    return _Regex_search2(_First, _Last, _STD addressof(_Matches), _Re, _Flgs, _First);
}

_EXPORT_STD template <class _BidIt, class _Elem, class _RxTraits>
_NODISCARD bool regex_search(_BidIt _First, _BidIt _Last, const basic_regex<_Elem, _RxTraits>& _Re,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    _Adl_verify_range(_First, _Last);
    return _Regex_search2(_Get_unwrapped(_First), _Get_unwrapped(_Last),
        static_cast<match_results<_Unwrapped_t<const _BidIt&>>*>(nullptr), _Re, _Flgs | regex_constants::match_any,
        _Get_unwrapped(_First));
}

_EXPORT_STD template <class _Elem, class _RxTraits>
_NODISCARD bool regex_search(_In_z_ const _Elem* _Str, const basic_regex<_Elem, _RxTraits>& _Re,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    const _Elem* _Last = _Str + char_traits<_Elem>::length(_Str);
    return _Regex_search2(
        _Str, _Last, static_cast<match_results<const _Elem*>*>(nullptr), _Re, _Flgs | regex_constants::match_any, _Str);
}

_EXPORT_STD template <class _Elem, class _Alloc, class _RxTraits>
bool regex_search(_In_z_ const _Elem* _Str, match_results<const _Elem*, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    const _Elem* _Last = _Str + char_traits<_Elem>::length(_Str);
    return _Regex_search2(_Str, _Last, _STD addressof(_Matches), _Re, _Flgs, _Str);
}

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Alloc, class _Elem, class _RxTraits>
bool regex_search(const basic_string<_Elem, _StTraits, _StAlloc>& _Str,
    match_results<typename basic_string<_Elem, _StTraits, _StAlloc>::const_iterator, _Alloc>& _Matches,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    return _Regex_search2(_Str.begin(), _Str.end(), _STD addressof(_Matches), _Re, _Flgs, _Str.begin());
}

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Alloc, class _Elem, class _RxTraits>
bool regex_search(const basic_string<_Elem, _StTraits, _StAlloc>&&,
    match_results<typename basic_string<_Elem, _StTraits, _StAlloc>::const_iterator, _Alloc>&,
    const basic_regex<_Elem, _RxTraits>&, regex_constants::match_flag_type = regex_constants::match_default) = delete;

_EXPORT_STD template <class _StTraits, class _StAlloc, class _Elem, class _RxTraits>
_NODISCARD bool regex_search(const basic_string<_Elem, _StTraits, _StAlloc>& _Str,
    const basic_regex<_Elem, _RxTraits>& _Re, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search for regular expression match in target text
    using _Iter = typename basic_string<_Elem, _StTraits, _StAlloc>::const_pointer;

    _Iter _First = _Str.c_str();
    _Iter _Last  = _First + _Str.size();
    return _Regex_search2(
        _First, _Last, static_cast<match_results<_Iter>*>(nullptr), _Re, _Flgs | regex_constants::match_any, _First);
}

template <class _OutIt, class _BidIt, class _RxTraits, class _Elem, class _Traits, class _Alloc>
_OutIt _Regex_replace1(_OutIt _Result, _BidIt _First, _BidIt _Last, const basic_regex<_Elem, _RxTraits>& _Re,
    const basic_string<_Elem, _Traits, _Alloc>& _Fmt, regex_constants::match_flag_type _Flgs) {
    static_assert(_Is_ranges_bidi_iter_v<_BidIt>,
        "regex_replace requires bidirectional iterators or stronger. See N5014 [re.alg.replace].");
    // search and replace
    match_results<_BidIt> _Matches;
    _BidIt _Pos                             = _First;
    regex_constants::match_flag_type _Flags = _Flgs;
    regex_constants::match_flag_type _Not_null{};

    while (
        _Regex_search2(_Pos, _Last, _STD addressof(_Matches), _Re, _Flags | _Not_null, _Pos)) { // replace at each match
        if (!(_Flgs & regex_constants::format_no_copy)) {
            _Result = _STD copy(_Matches.prefix().first, _Matches.prefix().second, _Result);
        }

        _Result = _Matches._Format1(_Result, _Fmt.data(), _Fmt.data() + _Fmt.size(), _Flags);

        _Pos = _Matches[0].second;
        if (_Pos == _Last || (_Flgs & regex_constants::format_first_only)) {
            break;
        }

        if (_Matches[0].first == _Matches[0].second) {
            _Not_null = regex_constants::_Match_not_null;
        } else { // non-null match, recognize earlier text
            _Not_null = regex_constants::match_flag_type{};
            _Flags |= regex_constants::match_prev_avail;
        }
    }
    return _Flgs & regex_constants::format_no_copy ? _Result : _STD _Copy_unchecked(_Pos, _Last, _Result);
}

_EXPORT_STD template <class _OutIt, class _BidIt, class _RxTraits, class _Elem, class _Traits, class _Alloc>
_OutIt regex_replace(_OutIt _Result, _BidIt _First, _BidIt _Last, const basic_regex<_Elem, _RxTraits>& _Re,
    const basic_string<_Elem, _Traits, _Alloc>& _Fmt,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, iterator result, string format
    _Adl_verify_range(_First, _Last);
    _Seek_wrapped(_Result, _Regex_replace1(_Get_unwrapped_unverified(_Result), _Get_unwrapped(_First),
                               _Get_unwrapped(_Last), _Re, _Fmt, _Flgs));
    return _Result;
}

_EXPORT_STD template <class _OutIt, class _BidIt, class _RxTraits, class _Elem>
_OutIt regex_replace(_OutIt _Result, _BidIt _First, _BidIt _Last, const basic_regex<_Elem, _RxTraits>& _Re,
    const _Elem* _Ptr, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, iterator result, NTBS format
    const basic_string<_Elem> _Fmt(_Ptr);
    return _STD regex_replace(_Result, _First, _Last, _Re, _Fmt, _Flgs);
}

_EXPORT_STD template <class _RxTraits, class _Elem, class _Traits1, class _Alloc1, class _Traits2, class _Alloc2>
_NODISCARD basic_string<_Elem, _Traits1, _Alloc1> regex_replace(const basic_string<_Elem, _Traits1, _Alloc1>& _Str,
    const basic_regex<_Elem, _RxTraits>& _Re, const basic_string<_Elem, _Traits2, _Alloc2>& _Fmt,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, string result, string target, string format
    basic_string<_Elem, _Traits1, _Alloc1> _Res;
    _STD regex_replace(_STD back_inserter(_Res), _Str.begin(), _Str.end(), _Re, _Fmt, _Flgs);
    return _Res;
}

_EXPORT_STD template <class _RxTraits, class _Elem, class _Traits1, class _Alloc1>
_NODISCARD basic_string<_Elem, _Traits1, _Alloc1> regex_replace(const basic_string<_Elem, _Traits1, _Alloc1>& _Str,
    const basic_regex<_Elem, _RxTraits>& _Re, const _Elem* _Ptr,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, string result, string target, NTBS format
    basic_string<_Elem, _Traits1, _Alloc1> _Res;
    const basic_string<_Elem> _Fmt(_Ptr);
    _STD regex_replace(_STD back_inserter(_Res), _Str.begin(), _Str.end(), _Re, _Fmt, _Flgs);
    return _Res;
}

_EXPORT_STD template <class _RxTraits, class _Elem, class _Traits2, class _Alloc2>
_NODISCARD basic_string<_Elem> regex_replace(const _Elem* _Pstr, const basic_regex<_Elem, _RxTraits>& _Re,
    const basic_string<_Elem, _Traits2, _Alloc2>& _Fmt,
    regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, string result, NTBS target, string format
    basic_string<_Elem> _Res;
    const basic_string<_Elem> _Str(_Pstr);
    _STD regex_replace(_STD back_inserter(_Res), _Str.begin(), _Str.end(), _Re, _Fmt, _Flgs);
    return _Res;
}

_EXPORT_STD template <class _RxTraits, class _Elem>
_NODISCARD basic_string<_Elem> regex_replace(const _Elem* _Pstr, const basic_regex<_Elem, _RxTraits>& _Re,
    const _Elem* _Ptr, regex_constants::match_flag_type _Flgs = regex_constants::match_default) {
    // search and replace, string result, NTBS target, NTBS format
    basic_string<_Elem> _Res;
    const basic_string<_Elem> _Str(_Pstr);
    const basic_string<_Elem> _Fmt(_Ptr);
    _STD regex_replace(_STD back_inserter(_Res), _Str.begin(), _Str.end(), _Re, _Fmt, _Flgs);
    return _Res;
}

_EXPORT_STD template <class _BidIt, class _Elem = _Iter_value_t<_BidIt>, class _RxTraits = regex_traits<_Elem>>
class regex_iterator : public _Iterator_base {
public:
    using regex_type        = basic_regex<_Elem, _RxTraits>;
    using value_type        = match_results<_BidIt>;
    using difference_type   = ptrdiff_t;
    using pointer           = const value_type*;
    using reference         = const value_type&;
    using iterator_category = forward_iterator_tag;
#if _HAS_CXX20
    using iterator_concept = input_iterator_tag;
#endif // _HAS_CXX20

    regex_iterator() = default; // construct end of sequence iterator

    regex_iterator(_BidIt _First, _BidIt _Last, const regex_type& _Re,
        regex_constants::match_flag_type _Fl = regex_constants::match_default)
        : _Begin(_First), _End(_Last), _MyRe(_STD addressof(_Re)), _Flags(_Fl) {
        _Adl_verify_range(_Begin, _End);
        if (!_Regex_search2(_Begin, _End, _STD addressof(_MyVal), *_MyRe, _Flags, _Begin)) {
            _MyRe = nullptr;
        } else {
            this->_Adopt(_MyRe);
        }
    }

    regex_iterator(
        _BidIt, _BidIt, const regex_type&&, regex_constants::match_flag_type = regex_constants::match_default) = delete;

    _NODISCARD bool operator==(const regex_iterator& _Right) const {
        if (_MyRe != _Right._MyRe) {
            return false;
        } else if (!_MyRe) {
            return true;
        }

        return _Begin == _Right._Begin && _End == _Right._End && _Flags == _Right._Flags
            && _MyVal._At(0) == _Right._MyVal._At(0);
    }

#if !_HAS_CXX20
    _NODISCARD bool operator!=(const regex_iterator& _Right) const {
        return !(*this == _Right);
    }
#endif // !_HAS_CXX20

#if _HAS_CXX20
    _NODISCARD bool operator==(default_sentinel_t) const noexcept /* strengthened */ {
        return !_MyRe;
    }
#endif // _HAS_CXX20

    _NODISCARD const value_type& operator*() const noexcept /* strengthened */ {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_MyRe, "regex_iterator not dereferenceable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return _MyVal;
    }

    _NODISCARD const value_type* operator->() const noexcept /* strengthened */ {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_MyRe, "regex_iterator not dereferenceable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return _STD addressof(_MyVal);
    }

    regex_iterator& operator++() {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_MyRe, "regex_iterator not incrementable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        _BidIt _Start = _MyVal._At(0).second;

#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(this->_Getcont(), "regex_iterator orphaned");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        bool _Skip_empty_match = false;
        if (_MyVal._At(0).first == _MyVal._At(0).second) { // handle zero-length match
            if (_Start == _End) { // store end-of-sequence iterator
                _MyRe = nullptr;

#if _ITERATOR_DEBUG_LEVEL == 2
                this->_Adopt(nullptr);
#endif // _ITERATOR_DEBUG_LEVEL == 2

                return *this;
            }

            // _Adl_verify_range(_Start, _End) checked in constructor
            if (_Regex_search2(_Start, _End, _STD addressof(_MyVal), *_MyRe,
                    _Flags | regex_constants::match_not_null | regex_constants::match_continuous, _Begin)) {
                return *this;
            }

            _Skip_empty_match = true;
        }
        _Flags = _Flags | regex_constants::match_prev_avail;

        auto _Tmp_flags = _Flags;
        if (_Skip_empty_match) {
            _Tmp_flags |= regex_constants::_Skip_zero_length;
        }

        // _Adl_verify_range(_Start, _End) checked in constructor
        if (!_Regex_search2(_Start, _End, _STD addressof(_MyVal), *_MyRe, _Tmp_flags, _Begin)) {
            // mark at end of sequence
            _MyRe = nullptr;
        }

        return *this;
    }

    regex_iterator operator++(int) {
        regex_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    bool _Atend() const noexcept { // test for end iterator
        return !_MyRe;
    }

private:
    _BidIt _Begin{}; // input sequence
    _BidIt _End{}; // input sequence
    const regex_type* _MyRe = nullptr; // pointer to basic_regex object
    regex_constants::match_flag_type _Flags{};
    match_results<_BidIt> _MyVal; // lookahead value (if _MyRe not null)
};

_EXPORT_STD using cregex_iterator  = regex_iterator<const char*>;
_EXPORT_STD using wcregex_iterator = regex_iterator<const wchar_t*>;
_EXPORT_STD using sregex_iterator  = regex_iterator<string::const_iterator>;
_EXPORT_STD using wsregex_iterator = regex_iterator<wstring::const_iterator>;

_EXPORT_STD template <class _BidIt, class _Elem = _Iter_value_t<_BidIt>, class _RxTraits = regex_traits<_Elem>>
class regex_token_iterator {
public:
    using _Position         = regex_iterator<_BidIt, _Elem, _RxTraits>;
    using regex_type        = basic_regex<_Elem, _RxTraits>;
    using value_type        = sub_match<_BidIt>;
    using difference_type   = ptrdiff_t;
    using pointer           = const value_type*;
    using reference         = const value_type&;
    using iterator_category = forward_iterator_tag;
#if _HAS_CXX20
    using iterator_concept = input_iterator_tag;
#endif // _HAS_CXX20

    regex_token_iterator() = default; // construct end of sequence iterator

    regex_token_iterator(_BidIt _First, _BidIt _Last, const regex_type& _Re, int _Sub = 0,
        regex_constants::match_flag_type _Fl = regex_constants::match_default)
        : _Pos(_First, _Last, _Re, _Fl), _Cur(0), _Subs(&_Sub, &_Sub + 1) {
        _Init(_First, _Last);
    }

    regex_token_iterator(_BidIt _First, _BidIt _Last, const regex_type& _Re, const vector<int>& _Subx,
        regex_constants::match_flag_type _Fl = regex_constants::match_default)
        : _Pos(_First, _Last, _Re, _Fl), _Cur(0), _Subs(_Subx.begin(), _Subx.end()) {
        if (_Subs.empty()) {
            _Res = nullptr; // treat empty vector as end of sequence
        } else {
            _Init(_First, _Last);
        }
    }

    template <size_t _Nx>
    regex_token_iterator(_BidIt _First, _BidIt _Last, const regex_type& _Re, const int (&_Subx)[_Nx],
        regex_constants::match_flag_type _Fl = regex_constants::match_default)
        : _Pos(_First, _Last, _Re, _Fl), _Cur(0), _Subs(_Subx, _Subx + _Nx) {
        _Init(_First, _Last);
    }

    regex_token_iterator(_BidIt _First, _BidIt _Last, const regex_type& _Re, initializer_list<int> _Ilist,
        regex_constants::match_flag_type _Fl = regex_constants::match_default)
        : _Pos(_First, _Last, _Re, _Fl), _Cur(0), _Subs(_Ilist.begin(), _Ilist.end()) {
        _Init(_First, _Last);
    }

    regex_token_iterator(_BidIt, _BidIt, const regex_type&&, int = 0,
        regex_constants::match_flag_type = regex_constants::match_default) = delete;

    regex_token_iterator(_BidIt, _BidIt, const regex_type&&, const vector<int>&,
        regex_constants::match_flag_type = regex_constants::match_default) = delete;

    template <size_t _Nx>
    regex_token_iterator(_BidIt, _BidIt, const regex_type&&, const int (&)[_Nx],
        regex_constants::match_flag_type = regex_constants::match_default) = delete;

    regex_token_iterator(_BidIt, _BidIt, const regex_type&&, initializer_list<int>,
        regex_constants::match_flag_type = regex_constants::match_default) = delete;

    regex_token_iterator(const regex_token_iterator& _Right)
        : _Pos(_Right._Pos), _Suffix(_Right._Suffix), _Cur(_Right._Cur), _Subs(_Right._Subs) {
        // construct copy of _Right
        if (!_Right._Res) {
            _Res = nullptr;
        } else if (_Right._Res == _STD addressof(_Right._Suffix)) {
            _Res = _STD addressof(_Suffix);
        } else {
            _Res = _Current();
        }
    }

    regex_token_iterator& operator=(const regex_token_iterator& _Right) {
        if (this != _STD addressof(_Right)) { // copy from _Right
            _Pos    = _Right._Pos;
            _Cur    = _Right._Cur;
            _Suffix = _Right._Suffix;
            _Subs   = _Right._Subs;
            if (!_Right._Res) {
                _Res = nullptr;
            } else if (_Right._Res == _STD addressof(_Right._Suffix)) {
                _Res = _STD addressof(_Suffix);
            } else {
                _Res = _Current();
            }
        }
        return *this;
    }

    _NODISCARD bool operator==(const regex_token_iterator& _Right) const {
        if (!_Res || !_Right._Res) {
            return _Res == _Right._Res;
        }

        return *_Res == *_Right._Res && _Pos == _Right._Pos && _Subs == _Right._Subs;
    }

#if !_HAS_CXX20
    _NODISCARD bool operator!=(const regex_token_iterator& _Right) const {
        return !(*this == _Right);
    }
#endif // !_HAS_CXX20

#if _HAS_CXX20
    _NODISCARD bool operator==(default_sentinel_t) const noexcept /* strengthened */ {
        return !_Res;
    }
#endif // _HAS_CXX20

    _NODISCARD const value_type& operator*() const noexcept /* strengthened */ {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Res, "regex_token_iterator not dereferenceable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        _Analysis_assume_(_Res);
        return *_Res;
    }

    _NODISCARD const value_type* operator->() const noexcept /* strengthened */ {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Res, "regex_token_iterator not dereferenceable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return _Res;
    }

    regex_token_iterator& operator++() {
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Res, "regex_token_iterator not incrementable");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        if (_Res == _STD addressof(_Suffix)) {
            _Res = nullptr;
        } else if (++_Cur < _Subs.size()) {
            _Res = _Current();
        } else { // advance to next full match
            _Cur = 0;
            _Position _Prev(_Pos);
            ++_Pos;
            if (!_Pos._Atend()) {
                _Res = _Current();
            } else if (_Has_suffix() && _Prev->suffix().length() != 0) { // mark suffix
                _Suffix.matched = true;
                _Suffix.first   = _Prev->suffix().first;
                _Suffix.second  = _Prev->suffix().second;
                _Res            = _STD addressof(_Suffix);
            } else {
                _Res = nullptr;
            }
        }

        return *this;
    }

    regex_token_iterator operator++(int) {
        regex_token_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

private:
    _Position _Pos;
    const value_type* _Res = nullptr;
    value_type _Suffix;
    size_t _Cur = 0;
    vector<int> _Subs;

    bool _Has_suffix() const { // check for suffix specifier
        return _STD find(_Subs.begin(), _Subs.end(), -1) != _Subs.end();
    }

    void _Init(_BidIt _First, _BidIt _Last) { // initialize
        _Adl_verify_range(_First, _Last);
        if (!_Pos._Atend()) {
            _Res = _Current();
        } else if (_Has_suffix()) { // mark suffix (no match)
            _Suffix.matched = true;
            _Suffix.first   = _First;
            _Suffix.second  = _Last;
            _Res            = _STD addressof(_Suffix);
        } else {
            _Res = nullptr;
        }
    }

    const value_type* _Current() const noexcept {
        return &(_Subs[_Cur] == -1 ? _Pos->prefix() : (*_Pos)[static_cast<size_t>(_Subs[_Cur])]);
    }
};

_EXPORT_STD using cregex_token_iterator  = regex_token_iterator<const char*>;
_EXPORT_STD using wcregex_token_iterator = regex_token_iterator<const wchar_t*>;
_EXPORT_STD using sregex_token_iterator  = regex_token_iterator<string::const_iterator>;
_EXPORT_STD using wsregex_token_iterator = regex_token_iterator<wstring::const_iterator>;

template <class _FwdIt, class _Elem, class _RxTraits>
_Builder2<_FwdIt, _Elem, _RxTraits>::_Builder2(const _RxTraits& _Tr, regex_constants::syntax_option_type _Fx)
    : _Root(new _Root_node), _Current(_Root), _Flags(_Fx), _Traits(_Tr) {}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Setlong() { // set flag
    _Root->_Flags |= _Fl_longest;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Negate() { // set flag
    _Current->_Flags ^= _Fl_negate;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Getmark() const {
    return _Current;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Link_node(_Node_base* _Nx) { // insert _Nx at current location
    _Nx->_Prev = _Current;
    if (_Current->_Next) { // set back pointer
        _Nx->_Next             = _Current->_Next;
        _Current->_Next->_Prev = _Nx;
    }
    _Current->_Next = _Nx;
    _Current        = _Nx;
    return _Nx;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Insert_node(_Node_base* _Insert_before, _Node_base* _To_insert) {
    // insert _To_insert into the graph before the node _Insert_before
    _Insert_before->_Prev->_Next = _To_insert;
    _To_insert->_Prev            = _Insert_before->_Prev;
    _Insert_before->_Prev        = _To_insert;
    _To_insert->_Next            = _Insert_before;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_New_node(_Node_type _Kind) { // allocate and link simple node
    return _Link_node(new _Node_base(_Kind));
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_bol() { // add bol node
    _New_node(_N_bol);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_eol() { // add eol node
    _New_node(_N_eol);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_wbound() { // add wbound node
    _New_node(_N_wbound);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_dot() { // add dot node
    _New_node(_N_dot);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_str_node() { // add string node
    _Link_node(new _Node_str<_Elem>);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_char(_Elem _Ch) { // append character
    if (_Current->_Kind != _N_str) {
        _Add_str_node();
    }

    if (_Flags & regex_constants::icase) {
        _Ch = _Traits.translate_nocase(_Ch);
    } else if (_Flags & regex_constants::collate) {
        _Ch = _Traits.translate(_Ch);
    }

    _Node_str<_Elem>* _Node = static_cast<_Node_str<_Elem>*>(_Current);
    _Node->_Data._Insert2(_Ch);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_class() { // add bracket expression node
    _Link_node(new _Node_class<_Elem, _RxTraits>);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_char_to_bitmap(unsigned char _Ch) { // add character to accelerator table
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);

    if (!_Node->_Small) {
        _Node->_Small = new _Bitmap;
    }

    _Node->_Small->_Mark(_Ch);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_char_to_array(_Elem _Ch) { // append character to character array
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);
    if (!_Node->_Large) {
        _Node->_Large = new _Buf<_Elem>;
    }

    _Node->_Large->_Insert2(_Ch);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_char_to_class(_Elem _Ch) { // add character to bracket expression
    if (_Flags & regex_constants::icase) {
        _Ch = _Traits.translate_nocase(_Ch);
    } else if (_Flags & regex_constants::collate) {
        _Ch = _Traits.translate(_Ch);
    }

    auto _Uchar = static_cast<unsigned char>(_Ch);
    if (static_cast<_Elem>(_Uchar) == _Ch) {
        _Add_char_to_bitmap(_Uchar);
    } else {
        _Add_char_to_array(_Ch);
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_range(_Elem _Arg0, const _Elem _Arg1) {
    // add character range to set
    using _String_type                   = typename _RxTraits::string_type;
    using _Char_traits_type              = typename _String_type::traits_type;
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);

    // set bits and check that the range is non-empty
    if (_Flags & regex_constants::collate) {
        _Elem _Ch;
        const auto _Ch_ptr           = _STD addressof(_Ch);
        const auto _Arg0_ptr         = _STD addressof(_Arg0);
        const auto _Arg1_ptr         = _STD addressof(_Arg1);
        const _String_type _Arg0_key = _Traits.transform(_Arg0_ptr, _Arg0_ptr + 1);
        const _String_type _Arg1_key = _Traits.transform(_Arg1_ptr, _Arg1_ptr + 1);

        if (_Arg0_key > _Arg1_key) {
            _Xregex_error(regex_constants::error_range);
        }

        for (unsigned int _UCh = 0; _UCh < _Bmp_max; ++_UCh) {
            _Ch                        = static_cast<_Elem>(_UCh);
            const _String_type _Ch_key = _Traits.transform(_Ch_ptr, _Ch_ptr + 1);
            if (_Arg0_key <= _Ch_key && _Ch_key <= _Arg1_key) {
                if (!_Node->_Small) {
                    _Node->_Small = new _Bitmap;
                }
                _Node->_Small->_Mark(_UCh);
            }
        }
    } else if (_Char_traits_type::lt(_Arg1, _Arg0)) {
        _Xregex_error(regex_constants::error_range);
    } else {
        unsigned int _Ex0 = static_cast<unsigned char>(_Arg0);
        if (static_cast<_Elem>(_Ex0) == _Arg0) {
            if (!_Node->_Small) {
                _Node->_Small = new _Bitmap;
            }

            unsigned int _Ex1           = static_cast<unsigned char>(_Arg1);
            bool _Extends_beyond_bitmap = static_cast<_Elem>(_Ex1) != _Arg1;
            if (_Extends_beyond_bitmap) {
                _Ex1 = _Bmp_max - 1;
            }

            for (; _Ex0 <= _Ex1; ++_Ex0) {
                _Node->_Small->_Mark(_Ex0);
            }

            if (!_Extends_beyond_bitmap) {
                return;
            }

            _Arg0 = static_cast<_Elem>(_Ex0);
        }

        if constexpr (sizeof(_Elem) > 1U) {
            if constexpr (is_integral_v<_Elem> || is_enum_v<_Elem>) {
                using _Uelem = make_unsigned_t<_Elem>;
                auto _First  = static_cast<_Uelem>(_Arg0);
                auto _Last   = static_cast<_Uelem>(_Arg1);
                auto _Count  = static_cast<_Uelem>(_Last - _First);
                ++_Count;
                if (_Count <= _ARRAY_THRESHOLD) {
                    for (; _Count > 0; ++_First, --_Count) {
                        _Add_char_to_array(static_cast<_Elem>(_First));
                    }
                    return;
                }
            } else {
                auto _Last = static_cast<unsigned int>(_Arg1);
                if (static_cast<_Elem>(_Last) == _Arg1) {
                    auto _First = static_cast<unsigned int>(_Arg0);
                    auto _Count = _Last - _First + 1U;
                    if (_Count <= _ARRAY_THRESHOLD) {
                        for (; _Count > 0; ++_First, --_Count) {
                            _Add_char_to_array(static_cast<_Elem>(_First));
                        }
                        return;
                    }
                }
            }
        }
    }

    // store remaining range as pair
    if (!_Node->_Ranges) {
        _Node->_Ranges = new _Buf<_Elem>;
    }

    _Node->_Ranges->_Insert2(_Arg0);
    _Node->_Ranges->_Insert2(_Arg1);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_elts(
    _Node_class<_Elem, _RxTraits>* _Node, typename _RxTraits::char_class_type _Cl, bool _Negative) {
    // add characters in named class to set
    for (unsigned int _Ch = 0; _Ch < _Bmp_max; ++_Ch) { // add elements or their inverse
        bool _Matches = _Traits.isctype(static_cast<_Elem>(_Ch), _Cl);
        if (_Matches != _Negative) { // add contents of named class to accelerator table
            if (!_Node->_Small) {
                _Node->_Small = new _Bitmap;
            }

            _Node->_Small->_Mark(_Ch);
        }
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_named_class(
    typename _RxTraits::char_class_type _Cl, const _Rx_char_class_kind _Kind) {
    // add contents of named class to bracket expression
    using _Char_class_type               = typename _RxTraits::char_class_type;
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);
    _Add_elts(_Node, _Cl, _Kind != _Rx_char_class_kind::_Positive);
    if constexpr (sizeof(_Elem) > 1U) {
        if (_Kind == _Rx_char_class_kind::_Positive) {
            auto _Cl_all_bits_set = static_cast<_Char_class_type>(-1);
            if ((_Node->_Classes != _Cl_all_bits_set && _Cl != _Cl_all_bits_set)
                || _Node->_Classes == _Char_class_type{}) {
                _Node->_Classes = static_cast<_Char_class_type>(_Node->_Classes | _Cl);
            } else if (_Node->_Classes != _Cl) {
                _Node->_Classes = static_cast<_Char_class_type>(_Node->_Classes & _Cl);
                _Node->_Flags |= _Fl_class_cl_all_bits;
            }
        } else {
            auto _Node_flag = static_cast<_Node_flags>(_Kind);
            _Node->_Flags |= _Node_flag;
            _Root->_Flags |= _Node_flag;
        }
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Char_to_elts(const _Elem* const _First, const _Elem* const _Last,
    _Sequence<_Elem>** _Cur) { // add collation element to element sequence
    auto _Diff = static_cast<unsigned int>(_Last - _First);
    while (*_Cur && _Diff < (*_Cur)->_Sz) {
        _Cur = &(*_Cur)->_Next;
    }

    if (!(*_Cur) || _Diff != (*_Cur)->_Sz) {
        // add new sequence holding elements of the same length
        _Sequence<_Elem>* _Node = *_Cur;
        *_Cur                   = new _Sequence<_Elem>(_Diff);
        (*_Cur)->_Next          = _Node;
    }
    (*_Cur)->_Data._Insert2(_First, _Last);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_equiv(const _Elem* const _First, const _Elem* const _Last) {
    // add elements of equivalence class to bracket expression
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);
    typename _RxTraits::string_type _Str = _Traits.transform_primary(_First, _Last);

    if (_Str.empty()) {
        _Xregex_error(regex_constants::error_collate);
    }

    for (unsigned int _Ch = 0; _Ch < _Bmp_max; ++_Ch) { // add elements
        _Elem _Ex = static_cast<_Elem>(_Ch);
        if (_Traits.transform_primary(_STD addressof(_Ex), _STD addressof(_Ex) + 1)
            == _Str) { // insert equivalent character into bitmap
            if (!_Node->_Small) {
                _Node->_Small = new _Bitmap;
            }

            _Node->_Small->_Mark(_Ch);
        }
    }

    if constexpr (sizeof(_Elem) > 1U) { // map range
        _Sequence<_Elem>** _Cur = _STD addressof(_Node->_Equiv);
        _Char_to_elts(_First, _Last, _Cur);
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_coll(const _Elem* const _First, const _Elem* const _Last) {
    // add collation element to bracket expression
    _Node_class<_Elem, _RxTraits>* _Node = static_cast<_Node_class<_Elem, _RxTraits>*>(_Current);
    _Sequence<_Elem>** _Cur              = _STD addressof(_Node->_Coll);
    _Char_to_elts(_First, _Last, _Cur);
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Begin_group() { // add group node
    return _New_node(_N_group);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_End_group(_Node_base* _Back) { // add end of group node
    _Node_type _Elt;
    if (_Back->_Kind == _N_group) {
        _Elt = _N_end_group;
    } else if (_Back->_Kind == _N_assert || _Back->_Kind == _N_neg_assert) {
        _Elt = _N_end_assert;
    } else {
        _Elt = _N_end_capture;
    }

    _Link_node(new _Node_end_group(_Elt, _Fl_none, _Back));
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Begin_assert_group(const bool _Neg) { // add assert node
    auto _Node1_unique   = _STD make_unique<_Node_assert>(_Neg ? _N_neg_assert : _N_assert);
    _Node_base* _Node2   = new _Node_base(_N_nop);
    _Node_assert* _Node1 = _Node1_unique.release();
    _Link_node(_Node1);
    _Node1->_Child = _Node2;
    _Node2->_Prev  = _Node1;
    _Current       = _Node2;
    return _Node1;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_End_assert_group(_Node_base* _Nx) { // add end of assert node
    _End_group(_Nx);
    _Current = _Nx;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Begin_capture_group(unsigned int _Idx) { // add capture group node
    return _Link_node(new _Node_capture(_Idx));
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_backreference(unsigned int _Idx) { // add back reference node
    _Link_node(new _Node_back(_Idx));
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Node_base* _Builder2<_FwdIt, _Elem, _RxTraits>::_Begin_if(_Node_base* _Start) { // add if node
    // append endif node
    _Node_base* _Res = new _Node_endif;
    _Link_node(_Res);

    // insert if_node
    _Node_if* _Node1 = new _Node_if(_Res);
    _Node_base* _Pos = _Start->_Next;
    _Insert_node(_Pos, _Node1);
    return _Res;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Else_if(_Node_base* _Start, _Node_base* _End) { // add else node
    _Node_if* _Parent  = static_cast<_Node_if*>(_Start->_Next);
    _Node_base* _First = _End->_Next;
    _End->_Next        = nullptr;
    _Node_base* _Last  = _Current;
    _Current           = _End;
    _End->_Next        = nullptr;
    _Last->_Next       = _End;
    while (_Parent->_Child) {
        _Parent = _Parent->_Child;
    }

    _Parent->_Child        = new _Node_if(_End);
    _Parent->_Child->_Next = _First;
    _First->_Prev          = _Parent->_Child;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Add_rep(int _Min, int _Max, bool _Greedy) { // add repeat node
    if (_Current->_Kind == _N_str
        && static_cast<_Node_str<_Elem>*>(_Current)->_Data._Size() != 1) { // move final character to new string node
        _Node_str<_Elem>* _Node = static_cast<_Node_str<_Elem>*>(_Current);
        _Add_str_node();
        _Add_char(_Node->_Data._Del());
    }

    _Node_base* _Pos = _Current;
    if (_Pos->_Kind == _N_end_group || _Pos->_Kind == _N_end_capture) {
        _Pos = static_cast<_Node_end_group*>(_Pos)->_Back;
    } else if (_Min == 0 && _Max == 1) {
        // Rewrite zero-or-one quantifiers as alternations to make the
        // "simple loop" optimization more likely to engage.
        //
        // GH-5490: This rewrite becomes observably incorrect
        // if the subexpression contains capture groups,
        // so we don't apply it if the subexpression is surrounded
        // by a capturing or non-capturing group.
        _Node_endif* _End       = new _Node_endif;
        _Node_if* _If_expr      = new _Node_if(_End);
        _Node_if* _If_empty_str = new _Node_if(_End);
        _Node_base* _Gbegin     = new _Node_base(_N_group);
        _Node_end_group* _Gend  = new _Node_end_group(_N_end_group, _Fl_none, _Gbegin);

        _If_empty_str->_Next = _Gbegin;
        _Gbegin->_Prev       = _If_empty_str;

        _Gbegin->_Next = _Gend;
        _Gend->_Prev   = _Gbegin;

        _Gend->_Next = _End;

        _If_expr->_Child = _If_empty_str;

        _Link_node(_End);
        _Insert_node(_Pos, _If_expr);

        if (!_Greedy) {
            swap(_If_expr->_Next->_Prev, _If_empty_str->_Next->_Prev); // intentional ADL
            swap(_If_expr->_Next, _If_empty_str->_Next); // intentional ADL
        }
        return;
    }

    if (_Root->_Loops == static_cast<unsigned int>(-1)) {
        _Xregex_error(regex_constants::error_space);
    }

    _Node_end_rep* _Node0 = new _Node_end_rep();
    _Link_node(_Node0);
    _Node_rep* _Nx     = new _Node_rep(_Greedy, _Min, _Max, _Node0, _Root->_Loops++);
    _Node0->_Begin_rep = _Nx;
    _Insert_node(_Pos, _Nx);
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Root_node* _Builder2<_FwdIt, _Elem, _RxTraits>::_End_pattern() { // wrap up
    _New_node(_N_end);
    return _Root;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Builder2<_FwdIt, _Elem, _RxTraits>::_Tidy() noexcept { // free memory
    _Destroy_node(_Root);
    _Root = nullptr;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
size_t _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Push_frame(_Rx_unwind_ops _Code, _Node_base* _Node) {
    if (_Frames_count >= _Frames._Size()) {
        if (_Frames_count >= _Frames_limit) {
            _Xregex_error(regex_constants::error_stack);
        }

        _Frames._Push_back({_Code, {0}, _Node, _Tgt_state._Cur, size_t{}});
    } else {
        auto& _Frame = _Frames[_Frames_count];
        _Frame._Code = _Code;
        _Frame._Node = _Node;
        _Frame._Pos  = _Tgt_state._Cur;
    }
    return _Frames_count++;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
size_t _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Calculate_frames_limit(_Iter_diff_t<_It> _Input_length) {
    constexpr size_t _Fixed_part  = 10000000U / sizeof(_State_frame_type);
    constexpr size_t _Divisor     = sizeof(_State_frame_type) / 10U;
    const auto _Variable_part     = _Input_length / static_cast<_Iter_diff_t<_It>>(_Divisor);
    const size_t _Max_frames_size = _Frames._Max_size();

    if (PTRDIFF_MAX < _Variable_part) {
        return _Max_frames_size;
    }

    return (_STD min) (_Max_frames_size, static_cast<size_t>(_Variable_part) + _Fixed_part);
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
long long _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Calculate_complexity_limit(_Iter_diff_t<_It> _Input_length) {
    constexpr long long _Intercept = 300000LL;
    constexpr long long _Gradient  = 256LL;
    if ((LLONG_MAX - _Intercept) / _Gradient < _Input_length) {
        return LLONG_MAX;
    }
    return _Gradient * static_cast<long long>(_Input_length) + _Intercept;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
void _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Increase_complexity_count(_Iter_diff_t<_It> _Count) {
    if (_Complexity_limit < _Count) {
        _Xregex_error(regex_constants::error_complexity);
    } else {
        _Complexity_limit -= static_cast<long long>(_Count);
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
void _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Prepare_rep(_Node_rep* _Node) {
    const auto _Psav = &_Loop_vals[_Node->_Loop_number];

    // Determine first capture group in repetition for later capture group reset, if not done so previously.
    // No capture group reset is performed for POSIX regexes,
    // so we prevent any reset by setting the first capture group to the size of the capture group vector.
    if (_Psav->_Group_first == 0U) {
        if ((_Sflags & regex_constants::_Any_posix) || !_Find_first_inner_capture_group(_Node->_Next, _Psav)) {
            _Psav->_Group_first = static_cast<unsigned int>(_Tgt_state._Grps._Size());
        }
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
bool _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Find_first_inner_capture_group(
    _Node_base* _Nx, _Loop_vals_type* _Loop_state) {

    bool _Found_group = false;
    while (_Nx) {
        switch (_Nx->_Kind) {
        case _N_nop:
        case _N_bol:
        case _N_eol:
        case _N_wbound:
        case _N_dot:
        case _N_str:
        case _N_class:
        case _N_group:
        case _N_end_group:
        case _N_end_capture:
        case _N_back:
        case _N_begin:
            break;

        case _N_assert:
        case _N_neg_assert:
            if (_Find_first_inner_capture_group(static_cast<_Node_assert*>(_Nx)->_Child, _Loop_state)) {
                _Found_group = true;
                _Nx          = nullptr;
            }
            break;

        case _N_capture:
            {
                _Node_capture* _Node      = static_cast<_Node_capture*>(_Nx);
                _Loop_state->_Group_first = _Node->_Idx - 1U;
                _Found_group              = true;
                _Nx                       = nullptr;
                break;
            }

        case _N_if:
            for (_Node_if* _Node = static_cast<_Node_if*>(_Nx); _Node; _Node = _Node->_Child) {
                if (_Find_first_inner_capture_group(_Node->_Next, _Loop_state)) {
                    _Found_group = true;
                    _Nx          = nullptr;
                    break;
                }
            }

            if (_Nx) { // continue search after the branches of the _N_if node
                _Nx = static_cast<_Node_if*>(_Nx)->_Endif;
            }
            break;

        case _N_rep:
            {
                const auto _Inner_rep        = static_cast<_Node_rep*>(_Nx);
                const auto _Inner_loop_state = &_Loop_vals[_Inner_rep->_Loop_number];
                if (_Find_first_inner_capture_group(_Inner_rep->_Next, _Inner_loop_state)) {
                    _Loop_state->_Group_first = _Inner_loop_state->_Group_first;
                    _Found_group              = true;
                    _Nx                       = nullptr;
                } else {
                    _Inner_loop_state->_Group_first = static_cast<unsigned int>(_Tgt_state._Grps._Size());
                    _Nx                             = _Inner_rep->_End_rep;
                }
                break;
            }

        case _N_end_assert:
        case _N_endif:
        case _N_end_rep:
        case _N_end:
        case _N_none:
        default:
            _Nx = nullptr;
            break;
        }

        if (_Nx) {
            _Nx = _Nx->_Next;
        }
    }

    return _Found_group;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
void _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Reset_capture_groups(unsigned int _First) {
    size_t _Size = _Tgt_state._Grps._Size();
    for (; _First < _Size; ++_First) {
        if (_Tgt_state._Grp_valid._Get(_First)) {
            _Tgt_state._Grp_valid._Clear(_First);
            auto _Frame_idx                  = _Push_frame(_Rx_unwind_ops::_Capture_restore_matched, nullptr);
            _Frames[_Frame_idx]._Capture_idx = _First;
        }
    }
}

template <class _BidIt1, class _BidIt2, class _Counter, class _Pr>
_BidIt1 _Cmp_chrange(_BidIt1 _Begin1, _BidIt1 _End1, _BidIt2 _Begin2, _BidIt2 _End2, _Counter& _Count, _Pr _Pred) {
    // compare character ranges
    _BidIt1 _Res = _Begin1;
    while (_Begin1 != _End1 && _Begin2 != _End2) {
        ++_Count;
        if (!_Pred(*_Begin1++, *_Begin2++)) {
            return _Res;
        }
    }
    return _Begin2 == _End2 ? _Begin1 : _Res;
}

template <class _BidIt1, class _BidIt2, class _RxTraits, class _Counter>
_BidIt1 _Compare_translate_both(_BidIt1 _Begin1, _BidIt1 _End1, _BidIt2 _Begin2, _BidIt2 _End2,
    const _RxTraits& _Traits, regex_constants::syntax_option_type _Sflags, _Counter& _Count) {
    // compare character ranges, translating characters in both ranges according to syntax options
    if (_Sflags & regex_constants::icase) {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, _Cmp_icase<_RxTraits>{_Traits});
    } else if constexpr (_Is_any_of_v<_RxTraits, regex_traits<char>, regex_traits<wchar_t>>) {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, equal_to<typename _RxTraits::char_type>{});
    } else if (_Sflags & regex_constants::collate) {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, _Cmp_collate<_RxTraits>{_Traits});
    } else {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, equal_to<typename _RxTraits::char_type>{});
    }
}

template <class _BidIt1, class _BidIt2, class _RxTraits, class _Counter>
_BidIt1 _Compare_translate_left(_BidIt1 _Begin1, _BidIt1 _End1, _BidIt2 _Begin2, _BidIt2 _End2,
    const _RxTraits& _Traits, regex_constants::syntax_option_type _Sflags, _Counter& _Count) {
    // compare character ranges, translating characters in the left range according to syntax options
    if (_Sflags & regex_constants::icase) {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, _Cmp_icase_translateleft<_RxTraits>{_Traits});
    } else if constexpr (_Is_any_of_v<_RxTraits, regex_traits<char>, regex_traits<wchar_t>>) {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, equal_to<typename _RxTraits::char_type>{});
    } else if (_Sflags & regex_constants::collate) {
        return _STD _Cmp_chrange(
            _Begin1, _End1, _Begin2, _End2, _Count, _Cmp_collate_translateleft<_RxTraits>{_Traits});
    } else {
        return _STD _Cmp_chrange(_Begin1, _End1, _Begin2, _End2, _Count, equal_to<typename _RxTraits::char_type>{});
    }
}

template <class _BidIt1, class _BidIt2, class _RxTraits>
_BidIt1 _Search_translate_left(_BidIt1 _Begin1, _BidIt1 _End1, _BidIt2 _Begin2, _BidIt2 _End2, const _RxTraits& _Traits,
    regex_constants::syntax_option_type _Sflags) {
    // searching the right character sequence in the left sequence,
    // after translating characters in the left sequence according to syntax options
    if (_Sflags & regex_constants::icase) {
        return _STD search(_Begin1, _End1, _Begin2, _End2, _Cmp_icase_translateleft<_RxTraits>{_Traits});
    } else if constexpr (_Is_any_of_v<_RxTraits, regex_traits<char>, regex_traits<wchar_t>>) {
        return _STD search(_Begin1, _End1, _Begin2, _End2, equal_to<typename _RxTraits::char_type>{});
    } else if (_Sflags & regex_constants::collate) {
        return _STD search(_Begin1, _End1, _Begin2, _End2, _Cmp_collate_translateleft<_RxTraits>{_Traits});
    } else {
        return _STD search(_Begin1, _End1, _Begin2, _End2, equal_to<typename _RxTraits::char_type>{});
    }
}

template <class _Char_traits, class _Elem>
bool _Lookup_range(const _Elem _Ch, const _Buf<_Elem>* const _Bufptr) { // check whether _Ch is in _Buf
    for (unsigned int _Ix = 0; _Ix < _Bufptr->_Size(); _Ix += 2) { // check current position
        const _Elem _Left  = _Bufptr->_At(_Ix);
        const _Elem _Right = _Bufptr->_At(_Ix + 1);

        bool _Within_range;
        if constexpr (is_same_v<_Char_traits, char_traits<char>>) {
            const auto _Uchar = static_cast<unsigned char>(_Ch);
            _Within_range = static_cast<unsigned char>(_Left) <= _Uchar && _Uchar <= static_cast<unsigned char>(_Right);
        } else if constexpr (is_same_v<_Char_traits, char_traits<wchar_t>>) {
            _Within_range = _Left <= _Ch && _Ch <= _Right;
        } else {
            _Within_range = !_Char_traits::lt(_Ch, _Left) && !_Char_traits::lt(_Right, _Ch);
        }

        if (_Within_range) {
            return true;
        }
    }

    return false;
}

template <class _Elem, class _RxTraits>
bool _Lookup_collating_range(const _Elem _Ch, const _Buf<_Elem>* const _Bufptr, const _RxTraits& _Traits) {
    const typename _RxTraits::string_type _Str = _Traits.transform(_STD addressof(_Ch), _STD addressof(_Ch) + 1);
    for (unsigned int _Ix = 0; _Ix < _Bufptr->_Size(); _Ix += 2) { // check current position
        const _Elem _Left  = _Bufptr->_At(_Ix);
        const _Elem _Right = _Bufptr->_At(_Ix + 1);
        if (_Traits.transform(_STD addressof(_Left), _STD addressof(_Left) + 1) <= _Str
            && _Str <= _Traits.transform(_STD addressof(_Right), _STD addressof(_Right) + 1)) {
            return true;
        }
    }
    return false;
}

template <class _Elem, class _RxTraits>
bool _Lookup_equiv2(_Elem _Ch, const _Sequence<_Elem>* _Eq, const _RxTraits& _Traits) {
    // check whether _Ch is in _Eq
    typename _RxTraits::string_type _Str0;
    typename _RxTraits::string_type _Str1;
    _Str1.push_back(_Ch);
    _Str1 = _Traits.transform_primary(_Str1.begin(), _Str1.end());
    while (_Eq) { // look for sequence of elements that are the right size
        for (unsigned int _Ix = 0; _Ix < _Eq->_Data._Size(); _Ix += _Eq->_Sz) { // look for _Ch
            _Str0.assign(_Eq->_Data._Str() + _Ix, _Eq->_Sz);
            _Str0 = _Traits.transform_primary(_Str0.begin(), _Str0.end());
            if (_Str0 == _Str1) {
                return true;
            }
        }
        _Eq = _Eq->_Next;
    }
    return false;
}

template <class _BidIt, class _Elem, class _RxTraits>
_BidIt _Lookup_coll2(_Elem _First_ch, _BidIt _First, const _BidIt _Last, const _Sequence<_Elem>* _Seq,
    const _RxTraits& _Traits, const regex_constants::syntax_option_type _Flags) {
    // look for collation element [_First, _Last) in _Seq
    typename _RxTraits::string_type _Str;

    // extend translated input character sequence
    if (_Seq) { // the longest collating elements come first
        _Str.push_back(_First_ch);
        const auto _Coll_size = _Seq->_Sz;
        size_t _Str_size      = 1;
        _BidIt _Pos           = _First;
        ++_Pos;

        for (; _Str_size < _Coll_size && _Pos != _Last; ++_Pos) {
            _Elem _Ch = *_Pos;
            if (_Flags & regex_constants::icase) {
                _Ch = _Traits.translate_nocase(_Ch);
            } else if (_Flags & regex_constants::collate) {
                _Ch = _Traits.translate(_Ch);
            }
            _Str.push_back(_Ch);
            ++_Str_size;
        }
    }

    while (_Seq) { // look for sequence of elements that are the right size
        const auto _Size = _Seq->_Sz;

        // match input character sequence to stored collating elements
        if (_Str.size() >= _Size) {
            const _Elem* const _Str_first = _Str.data();
            const _Elem* const _Str_last  = _Str_first + _Size;
            const _Elem* _Current         = _Seq->_Data._Str();
            for (auto _Remaining = _Seq->_Data._Size(); _Remaining >= _Size; _Current += _Size, _Remaining -= _Size) {
                if (_STD equal(_Str_first, _Str_last, _Current)) {
                    _STD advance(_First, static_cast<_Iter_diff_t<_BidIt>>(_Size));
                    return _First;
                }
            }
        }
        _Seq = _Seq->_Next;
    }
    return _First;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
_It _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Do_class(const _Node_base* const _Nx, _It _First) {
    // apply bracket expression
    bool _Found;
    _Elem _Ch = *_First;
    if (_Sflags & regex_constants::icase) {
        _Ch = _Traits.translate_nocase(_Ch);
    } else if (_Sflags & regex_constants::collate) {
        _Ch = _Traits.translate(_Ch);
    }
    const auto _Uchar = static_cast<unsigned char>(_Ch);

    _It _Res0 = _First;
    ++_Res0;
    _It _Resx;
    const auto _Node = static_cast<const _Node_class<_Elem, _RxTraits>*>(_Nx);
    if (_Node->_Coll
        && (_Resx = _STD _Lookup_coll2(_Ch, _First, _End, _Node->_Coll, _Traits, _Sflags))
               != _First) { // check for collation element
        _Res0  = _Resx;
        _Found = true;
    } else if (_Node->_Ranges
               && (_Sflags & regex_constants::collate
                       ? _STD _Lookup_collating_range(_Ch, _Node->_Ranges, _Traits)
                       : _STD _Lookup_range<typename _RxTraits::string_type::traits_type>(_Ch, _Node->_Ranges))) {
        _Found = true;
    } else if (static_cast<_Elem>(_Uchar) == _Ch) {
        _Found = _Node->_Small && _Node->_Small->_Find(_Uchar);
    } else if (_Node->_Large
               && _STD find(_Node->_Large->_Str(), _Node->_Large->_Str() + _Node->_Large->_Size(), _Ch)
                      != _Node->_Large->_Str() + _Node->_Large->_Size()) {
        _Found = true;
    } else if (_Node->_Classes != typename _RxTraits::char_class_type{} && _Traits.isctype(_Ch, _Node->_Classes)) {
        _Found = true;
    } else if ((_Node->_Flags & _Fl_class_cl_all_bits)
               && _Traits.isctype(_Ch, static_cast<typename _RxTraits::char_class_type>(-1))) {
        _Found = true;
    } else if (_Node->_Equiv && _STD _Lookup_equiv2(_Ch, _Node->_Equiv, _Traits)) {
        _Found = true;
    } else if ((_Node->_Flags & _Fl_class_negated_w) && !_Traits.isctype(_Ch, _Char_class_w)) {
        _Found = true;
    } else if ((_Node->_Flags & _Fl_class_negated_s) && !_Traits.isctype(_Ch, _Char_class_s)) {
        _Found = true;
    } else if ((_Node->_Flags & _Fl_class_negated_d) && !_Traits.isctype(_Ch, _Char_class_d)) {
        _Found = true;
    } else {
        _Found = false;
    }

    const bool _Negated = (_Node->_Flags & _Fl_negate) != 0;

    if (_Found == _Negated) {
        return _First;
    } else {
        return _Res0;
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
bool _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Better_match() {
    // check for better match under leftmost-longest rule

    // a longer match is better than a shorter one
    if (_Res._Cur != _Tgt_state._Cur) {
        return _STD distance(_Begin, _Res._Cur) < _STD distance(_Begin, _Tgt_state._Cur);
    }

    for (unsigned int _Ix = 0U; _Ix < _Ncap - 1U; ++_Ix) { // check each capture group
        // any match (even an empty one) is better than no match at all
        const bool _Valid_in_tgt_state = _Tgt_state._Grp_valid._Get(_Ix);
        if (_Res._Grp_valid._Get(_Ix) != _Valid_in_tgt_state) {
            return _Valid_in_tgt_state;
        }

        if (_Valid_in_tgt_state) { // now known to be equal to _Res._Grp_valid._Get(_Ix), no need to test both
            // if both groups are matched, prefer the leftmost one
            if (_Res._Grps[_Ix]._Begin != _Tgt_state._Grps[_Ix]._Begin) {
                return _STD distance(_Begin, _Res._Grps[_Ix]._Begin)
                     > _STD distance(_Begin, _Tgt_state._Grps[_Ix]._Begin);
            }

            // if both groups start at the same position, prefer the longer one
            if (_Res._Grps[_Ix]._End != _Tgt_state._Grps[_Ix]._End) {
                return _STD distance(_Res._Grps[_Ix]._Begin, _Res._Grps[_Ix]._End)
                     < _STD distance(_Tgt_state._Grps[_Ix]._Begin, _Tgt_state._Grps[_Ix]._End);
            }
        }
    }
    return false;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
bool _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Is_wbound() const {
    if ((_Mflags & regex_constants::match_prev_avail)
        || _Tgt_state._Cur != _Begin) { // if --_Cur is valid, check for preceding word character
        if (_Tgt_state._Cur == _End) {
            return (_Mflags & regex_constants::match_not_eow) == 0 && _STD _Is_word(*_Prev_iter(_Tgt_state._Cur));
        } else {
            return _STD _Is_word(*_Prev_iter(_Tgt_state._Cur)) != _STD _Is_word(*_Tgt_state._Cur);
        }
    } else { // --_Cur is not valid
        if (_Tgt_state._Cur == _End) {
            return false;
        } else {
            return (_Mflags & regex_constants::match_not_bow) == 0 && _STD _Is_word(*_Tgt_state._Cur);
        }
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
typename _RxTraits::char_class_type _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Lookup_char_class(
    const _Elem _Class_name) const {
    // look up character class with single-character name
    auto _Ptr = _STD addressof(_Class_name);
    return _Traits.lookup_classname(_Ptr, _Ptr + 1, (_Sflags & regex_constants::icase) != 0);
}

template <class _Elem>
bool _Is_ecmascript_line_terminator(_Elem _Ch) {
    if constexpr (is_same_v<_Elem, char>) {
        return _Ch == _Meta_nl || _Ch == _Meta_cr;
    } else if constexpr (is_same_v<_Elem, wchar_t>) {
        return _Ch == _Meta_nl || _Ch == _Meta_cr || _Ch == _Meta_ls || _Ch == _Meta_ps;
    } else {
        auto _UCh = static_cast<unsigned int>(_Ch);
        return static_cast<_Elem>(_UCh) == _Ch
            && (_UCh == _Meta_nl || _UCh == _Meta_cr || _UCh == _Meta_ls || _UCh == _Meta_ps);
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
bool _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Match_pat(_Node_base* _Nx) { // check for match
    bool _Failed = false;

    while (_Nx) {
        do { // match current node
            _Increase_complexity_count(_Iter_diff_t<_It>{1}); // one state transition
            _Node_base* _Next = _Nx->_Next;
            switch (_Nx->_Kind) { // handle current node's type
            case _N_nop:
                break;

            case _N_bol:
                if ((_Mflags & regex_constants::match_prev_avail)
                    || _Tgt_state._Cur != _Begin) { // if --_Cur is valid, check for preceding newline
                    _Failed = !(_Sflags & regex_constants::multiline)
                           || !_STD _Is_ecmascript_line_terminator(*_STD _Prev_iter(_Tgt_state._Cur));
                } else {
                    _Failed = (_Mflags & regex_constants::match_not_bol) != 0;
                }
                break;

            case _N_eol:
                if (_Tgt_state._Cur == _End) {
                    _Failed = (_Mflags & regex_constants::match_not_eol) != 0;
                } else {
                    _Failed = !(_Sflags & regex_constants::multiline)
                           || !_STD _Is_ecmascript_line_terminator(*_Tgt_state._Cur);
                }

                break;

            case _N_wbound:
                _Failed = _Is_wbound() == ((_Nx->_Flags & _Fl_negate) != 0);
                break;

            case _N_dot:
                if (_Tgt_state._Cur == _End) {
                    _Failed = true;
                } else {
                    const _Elem _Ch = *_Tgt_state._Cur;
                    if (_Sflags & regex_constants::_Any_posix) {
                        if (_Ch == _Elem()) {
                            _Failed = true;
                        }
                    } else if (_STD _Is_ecmascript_line_terminator(_Ch)) {
                        _Failed = true;
                    }

                    if (!_Failed) {
                        ++_Tgt_state._Cur;
                    }
                }

                break;

            case _N_str:
                { // check for string match
                    _Node_str<_Elem>* _Node = static_cast<_Node_str<_Elem>*>(_Nx);
                    _It _Res0;
                    _Iter_diff_t<_It> _Count{};
                    if ((_Res0 = _STD _Compare_translate_left(_Tgt_state._Cur, _End, _Node->_Data._Str(),
                             _Node->_Data._Str() + _Node->_Data._Size(), _Traits, _Sflags, _Count))
                        != _Tgt_state._Cur) {
                        _Tgt_state._Cur = _Res0;
                    } else {
                        _Failed = true;
                    }

                    // divide by 64 because character comparisons are cheaper than state transitions
                    _Increase_complexity_count(static_cast<_Iter_diff_t<_It>>(_Count / 64));

                    break;
                }

            case _N_class:
                { // check for bracket expression match
                    _It _Res;
                    if (_Tgt_state._Cur != _End && (_Res = _Do_class(_Nx, _Tgt_state._Cur)) != _Tgt_state._Cur) {
                        _Tgt_state._Cur = _Res;
                    } else {
                        _Failed = true;
                    }
                    break;
                }

            case _N_group:
                break;

            case _N_end_group:
                break;

            case _N_assert:
                { // check assert
                    auto _Node = static_cast<_Node_assert*>(_Nx);
                    _Push_frame(_Rx_unwind_ops::_After_assert, _Node);
                    _Next = _Node->_Child;
                    break;
                }

            case _N_neg_assert:
                { // check negative assert
                    auto _Node = static_cast<_Node_assert*>(_Nx);
                    _Push_frame(_Rx_unwind_ops::_After_neg_assert, _Node);
                    _Next = _Node->_Child;
                    break;
                }

            case _N_end_assert:
                {
                    size_t _Last_capture_restore_frame = 0U;
                    unsigned int _Capture_first        = UINT_MAX;
                    unsigned int _Capture_back         = 0U;
                    for (;;) {
                        --_Frames_count;
                        const auto& _Frame = _Frames[_Frames_count];
                        const auto _Code   = _Frame._Code;
                        if (_Code == _Rx_unwind_ops::_After_assert || _Code == _Rx_unwind_ops::_After_neg_assert) {
                            if (_Code == _Rx_unwind_ops::_After_assert) {
                                _Tgt_state._Cur = _Frame._Pos;
                                _Next           = _Frame._Node->_Next;
                                if (_Last_capture_restore_frame != 0U) {
                                    auto _Not_capture_restore = [](const auto& _Other_frame) static {
                                        return _Other_frame._Code != _Rx_unwind_ops::_Capture_restore_begin
                                            && _Other_frame._Code != _Rx_unwind_ops::_Capture_restore_unmatched_end;
                                    };
                                    const auto _Effective_frames_end =
                                        _STD remove_if(_Frames._Begin() + static_cast<ptrdiff_t>(_Frames_count),
                                            _Frames._Begin() + static_cast<ptrdiff_t>(_Last_capture_restore_frame) + 1,
                                            _Not_capture_restore);
                                    _Frames_count = static_cast<size_t>(_Effective_frames_end - _Frames._Begin());
                                }
                            } else {
                                _Failed = true;
                                if (_Capture_first <= _Capture_back) {
                                    _Tgt_state._Grp_valid._Clear_range_at_least_until(
                                        _Capture_first, _Capture_back + 1U);
                                }
                            }
                            break;
                        } else if (_Code == _Rx_unwind_ops::_Capture_restore_unmatched_end) {
                            auto _Capture_idx = _Frame._Capture_idx;
                            if (_Capture_first > _Capture_idx) {
                                _Capture_first = _Capture_idx;
                            }

                            if (_Capture_back < _Capture_idx) {
                                _Capture_back = _Capture_idx;
                            }

                            if (_Last_capture_restore_frame == 0U) {
                                _Last_capture_restore_frame = _Frames_count;
                            }
                        }
                    }
                }
                break;

            case _N_capture:
                { // record current position
                    auto _Node = static_cast<_Node_capture*>(_Nx);
                    _STL_INTERNAL_CHECK(_Node->_Idx != 0U);
                    auto _Idx           = _Node->_Idx - 1U;
                    auto& _Group        = _Tgt_state._Grps[_Idx];
                    auto _Frame_idx     = _Push_frame(_Rx_unwind_ops::_Capture_restore_begin, _Node);
                    auto& _Frame        = _Frames[_Frame_idx];
                    _Frame._Pos         = _Group._Begin;
                    _Frame._Capture_idx = _Idx;
                    _Group._Begin       = _Tgt_state._Cur;
                    break;
                }

            case _N_end_capture:
                { // record successful capture
                    auto _Node  = static_cast<_Node_end_group*>(_Nx);
                    auto _Node0 = static_cast<_Node_capture*>(_Node->_Back);
                    if (_Node0->_Idx != 0U) { // update capture data
                        auto _Idx           = _Node0->_Idx - 1U;
                        auto& _Group        = _Tgt_state._Grps[_Idx];
                        bool _Matched       = _Tgt_state._Grp_valid._Get(_Idx);
                        const auto _Code    = _Matched ? _Rx_unwind_ops::_Capture_restore_matched_end
                                                       : _Rx_unwind_ops::_Capture_restore_unmatched_end;
                        auto _Frame_idx     = _Push_frame(_Code, _Node0);
                        auto& _Frame        = _Frames[_Frame_idx];
                        _Frame._Pos         = _Group._End;
                        _Frame._Capture_idx = _Idx;
                        _Group._End         = _Tgt_state._Cur;
                        _Tgt_state._Grp_valid._Set(_Idx);
                    }
                    break;
                }

            case _N_back:
                { // check back reference
                    _STL_INTERNAL_CHECK(
                        (_Sflags & (regex_constants::extended | regex_constants::egrep | regex_constants::awk))
                        == 0); // these grammars don't have backreferences
                    _Node_back* _Node = static_cast<_Node_back*>(_Nx);
                    const auto _Idx   = _Node->_Idx - 1U;
                    if (_Tgt_state._Grp_valid._Get(_Idx)) { // check for match
                        _It _Res0 = _Tgt_state._Cur;
                        _It _Bx   = _Tgt_state._Grps[_Idx]._Begin;
                        _It _Ex   = _Tgt_state._Grps[_Idx]._End;
                        _Iter_diff_t<_It> _Count{};
                        if (_Bx != _Ex // _Bx == _Ex for zero-length match
                            && (_Res0 = _STD _Compare_translate_both(
                                    _Tgt_state._Cur, _End, _Bx, _Ex, _Traits, _Sflags, _Count))
                                   == _Tgt_state._Cur) {
                            _Failed = true;
                        } else {
                            _Tgt_state._Cur = _Res0;
                        }

                        // divide by 64 because character comparisons are cheaper than state transitions
                        _Increase_complexity_count(static_cast<_Iter_diff_t<_It>>(_Count / 64));
                    } else if (_Sflags & (regex_constants::basic | regex_constants::grep)) {
                        _Failed = true;
                    }
                    break;
                }

            case _N_if:
                {
                    auto _Node = static_cast<_Node_if*>(_Nx);
                    if (_Node->_Child) {
                        _Push_frame(_Rx_unwind_ops::_Disjunction_eval_alternative, _Node->_Child);
                    }
                    break;
                }

            case _N_endif:
                break;

            case _N_rep:
                { // handle start of loop
                    auto _Node = static_cast<_Node_rep*>(_Nx);
                    _Prepare_rep(_Node);
                    bool _Greedy = (_Node->_Flags & _Fl_greedy) != 0;
                    auto& _Sav   = _Loop_vals[_Node->_Loop_number];

                    if (_Node->_Simple_loop == 1) {
                        _Sav._Loop_frame_idx = _Push_frame(_Rx_unwind_ops::_Do_nothing, _Node);
                        if (_Node->_Min > 0 || (_Greedy && !_Longest && _Node->_Max != 0)) { // try a rep first
                            _Sav._Loop_idx = 1;
                            // _Next is already assigned correctly for matching a rep

                            // set up stack unwinding for greedy matching if no rep is allowed
                            if (_Node->_Min == 0) {
                                auto& _Frame = _Frames[_Sav._Loop_frame_idx];
                                _Frame._Code = _Rx_unwind_ops::_Loop_simple_greedy_firstrep;
                            }
                        } else { // try tail first
                            _Sav._Loop_idx = 0;
                            _Next          = _Node->_End_rep->_Next;

                            // set up stack unwinding for non-greedy matching if at least one rep is allowed
                            if (_Node->_Max != 0) {
                                _Push_frame(_Rx_unwind_ops::_Loop_simple_nongreedy, _Node);
                            }
                        }
                    } else {
                        if (_Node->_Min > 0 || (_Greedy && !_Longest && _Node->_Max != 0)) { // try a rep first
                            // set up stack unwinding for greedy matching or loop val restoration
                            const auto _Code =
                                _Node->_Min == 0 ? _Rx_unwind_ops::_Loop_greedy : _Rx_unwind_ops::_Loop_restore_vals;
                            auto _Frame_idx            = _Push_frame(_Code, _Node);
                            auto& _Frame               = _Frames[_Frame_idx];
                            _Frame._Loop_idx_sav       = _Sav._Loop_idx;
                            _Frame._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                            _Sav._Loop_idx             = 1;
                            _Sav._Loop_frame_idx       = _Frame_idx;
                            // _Next is already assigned correctly for matching a rep
                        } else { // try tail first
                            _Next = _Node->_End_rep->_Next;
                            // set up stack unwinding for non-greedy matching if at least one rep is allowed
                            if (_Node->_Max != 0) {
                                auto _Frame_idx            = _Push_frame(_Rx_unwind_ops::_Loop_nongreedy, _Node);
                                auto& _Frame               = _Frames[_Frame_idx];
                                _Frame._Loop_idx_sav       = _Sav._Loop_idx;
                                _Frame._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                                _Sav._Loop_idx             = 0;
                                _Sav._Loop_frame_idx       = _Frame_idx;
                            }
                        }
                    }
                }

                break;

            case _N_end_rep:
                { // handle end of loop
                    _Node_rep* _Nr = static_cast<_Node_end_rep*>(_Nx)->_Begin_rep;
                    auto& _Sav     = _Loop_vals[_Nr->_Loop_number];
                    bool _Greedy   = (_Nr->_Flags & _Fl_greedy) != 0;
                    if (_Nr->_Simple_loop != 0 || (_Nr->_Flags & _Fl_rep_branchless) != 0) {
                        if (_Sav._Loop_idx == 1) {
                            auto& _Base_frame = _Frames[_Sav._Loop_frame_idx];
                            _Sav._Loop_length = _STD distance(_Base_frame._Pos, _Tgt_state._Cur);

                            if (_Sav._Loop_length == _Iter_diff_t<_It>{}) { // initial match empty
                                // loop is branchless, so it will only ever match empty strings
                                // -> we only try tail for POSIX or if minimum number of reps is non-zero
                                // _Next is already assigned correctly for matching tail
                                if (!(_Sflags & regex_constants::_Any_posix) && _Nr->_Min == 0) {
                                    _Failed = true;
                                }
                                break;
                            }

                            // allocate stack frame holding loop-specific unwinding opcode for second rep and beyond
                            auto _New_frame_code = _Base_frame._Code == _Rx_unwind_ops::_Loop_simple_greedy_firstrep
                                                        || _Base_frame._Code == _Rx_unwind_ops::_Loop_greedy
                                                     ? _Rx_unwind_ops::_Loop_simple_greedy_lastrep
                                                     : _Rx_unwind_ops::_Do_nothing;
                            auto _New_frame_idx  = _Push_frame(_New_frame_code, _Nr);
                            _Frames[_New_frame_idx]._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                            _Sav._Loop_frame_idx                        = _New_frame_idx;
                        } else { // discard stack frames for capturing group changes generated by this rep
                            _Frames_count = _Sav._Loop_frame_idx + 1U;
                        }

                        if (_Sav._Loop_idx < _Nr->_Min) { // at least one more rep to reach minimum
                            _Next = _Nr->_Next;
                            ++_Sav._Loop_idx;
                        } else if (_Greedy && !_Longest) { // greedy matching
                            auto& _Frame = _Frames[_Sav._Loop_frame_idx];
                            if (_Frame._Code == _Rx_unwind_ops::_Do_nothing) { // min reps reached
                                _Frame._Code = _Rx_unwind_ops::_Loop_simple_greedy_lastrep;
                                // set iterator in base frame to start of prior rep
                                // (so to start of rep before reaching min reps)
                                auto& _Before_unwind_pos = _Frames[_Frame._Loop_frame_idx_sav]._Pos;
                                _Before_unwind_pos       = _Tgt_state._Cur;
                                _STD advance(_Before_unwind_pos, -_Sav._Loop_length);
                            } else {
                                _STL_INTERNAL_CHECK(_Frame._Code == _Rx_unwind_ops::_Loop_simple_greedy_lastrep);
                            }
                            _Frame._Pos = _Tgt_state._Cur;

                            if (_Sav._Loop_idx != _Nr->_Max) { // try one more rep
                                _Next = _Nr->_Next;
                                if (_Sav._Loop_idx < INT_MAX) { // avoid overflowing _Loop_idx
                                    ++_Sav._Loop_idx;
                                }
                            } else { // try tail
                                _STD advance(_Frame._Pos, -_Sav._Loop_length);
                                if (_Frame._Pos != _Frames[_Frame._Loop_frame_idx_sav]._Pos) {
                                    // capturing groups must be shifted when backtracking from tail
                                    _Frame._Code = _Rx_unwind_ops::_Loop_simple_greedy_intermediaterep;
                                } else {
                                    --_Frames_count;
                                }
                                // _Next is already assigned correctly for matching tail
                            }
                        } else { // non-greedy matching
                            // set up stack unwinding for non-greedy matching if one more rep is allowed
                            if (_Sav._Loop_idx != _Nr->_Max) {
                                auto& _Frame = _Frames[_Sav._Loop_frame_idx];
                                _Frame._Pos  = _Tgt_state._Cur;
                                _Frame._Code = _Rx_unwind_ops::_Loop_simple_nongreedy;
                                _Frame._Node = _Nr;
                            } else {
                                --_Frames_count;
                            }
                            // _Next is already assigned correctly for matching tail
                        }
                    } else {
                        const bool _Progress = _Frames[_Sav._Loop_frame_idx]._Pos != _Tgt_state._Cur;
                        if (_Sav._Loop_idx < _Nr->_Min) { // try another required match
                            auto _Frame_idx            = _Push_frame(_Rx_unwind_ops::_Loop_restore_vals, _Nr);
                            auto& _Frame               = _Frames[_Frame_idx];
                            _Frame._Loop_idx_sav       = _Sav._Loop_idx;
                            _Frame._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                            _Sav._Loop_frame_idx       = _Frame_idx;

                            // optimization: try only one more match after an empty match
                            // if there is no maximum number of reps
                            if (!_Progress && _Nr->_Max < 0) {
                                _Sav._Loop_idx = _Nr->_Min;
                            } else {
                                ++_Sav._Loop_idx;
                            }

                            _Reset_capture_groups(_Sav._Group_first);
                            _Next = _Nr->_Next;
                        } else if (!_Progress) { // latest rep match empty
                            // An empty match is allowed if it is needed to reach the minimum number of reps.
                            // Moreover, POSIX allows an empty repetition if the subexpression is matched only once.
                            // So try tail in either case, else fail.
                            if (_Sav._Loop_idx != _Nr->_Min
                                && !((_Sflags & regex_constants::_Any_posix) && _Sav._Loop_idx == 1)) {
                                _Failed = true;
                            }
                            // _Next is already assigned correctly for matching tail
                        } else if (_Greedy && !_Longest && _Sav._Loop_idx != _Nr->_Max) { // one more rep to try next
                            // set up stack unwinding for greedy matching
                            auto _Frame_idx            = _Push_frame(_Rx_unwind_ops::_Loop_greedy, _Nr);
                            auto& _Frame               = _Frames[_Frame_idx];
                            _Frame._Loop_idx_sav       = _Sav._Loop_idx;
                            _Frame._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                            _Sav._Loop_frame_idx       = _Frame_idx;
                            if (_Sav._Loop_idx < INT_MAX) {
                                ++_Sav._Loop_idx;
                            }

                            _Reset_capture_groups(_Sav._Group_first);
                            _Next = _Nr->_Next;
                        } else { // non-greedy matching or greedy matching with maximum reached
                            // set up stack unwinding for non-greedy matching if one more rep is allowed
                            if (_Sav._Loop_idx != _Nr->_Max) {
                                auto _Frame_idx            = _Push_frame(_Rx_unwind_ops::_Loop_nongreedy, _Nr);
                                auto& _Frame               = _Frames[_Frame_idx];
                                _Frame._Loop_idx_sav       = _Sav._Loop_idx;
                                _Frame._Loop_frame_idx_sav = _Sav._Loop_frame_idx;
                                _Sav._Loop_frame_idx       = _Frame_idx;
                            }
                            // _Next is already assigned correctly for matching tail
                        }
                    }
                    break;
                }

            case _N_begin:
                break;

            case _N_end:
                if (((_Mflags & (regex_constants::match_not_null | regex_constants::_Match_not_null))
                        && _Begin == _Tgt_state._Cur)
                    || (_Full && _Tgt_state._Cur != _End)) {
                    _Failed = true;
                } else if (!_Longest) { // match result found, skip unwinding
                    return true;
                } else if (!_Matched || _Better_match()) { // record successful match
                    _Res._Copy_from(_Tgt_state);
                    _Matched = true;
                }
                _Next = nullptr;
                break;

            case _N_none:
            default:
#if _ITERATOR_DEBUG_LEVEL != 0
                _STL_REPORT_ERROR("internal data of regex node corrupted");
#endif
                return false;
            }

            if (_Failed) {
                _Nx = nullptr;
            } else {
                _Nx = _Next;
            }
        } while (_Nx);

        while (_Frames_count > 0 && !_Nx) {
            _STL_INTERNAL_CHECK(_Failed || _Longest);

            auto& _Frame = _Frames[--_Frames_count];
            switch (_Frame._Code) {
            case _Rx_unwind_ops::_After_assert: // matching pattern of positive assert failed
            case _Rx_unwind_ops::_Do_nothing:
                break;

            case _Rx_unwind_ops::_After_neg_assert:
                { // matching pattern of negative assert failed
                    _Tgt_state._Cur = _Frame._Pos;
                    _Nx             = _Frame._Node->_Next;
                    _Failed         = false;
                    break;
                }

            case _Rx_unwind_ops::_Disjunction_eval_alternative:
                { // try next alternative in a disjunction
                    auto _Node      = static_cast<_Node_if*>(_Frame._Node);
                    _Nx             = _Node->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;
                    if (_Node->_Child) {
                        _Frame._Node = _Node->_Child;
                        ++_Frames_count;
                    }
                    break;
                }

            case _Rx_unwind_ops::_Loop_simple_nongreedy:
                { // try one more rep
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);
                    auto& _Sav = _Loop_vals[_Node->_Loop_number];

                    _Nx             = _Node->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;
                    if (_Sav._Loop_idx < INT_MAX) { // avoid overflowing _Loop_idx
                        ++_Sav._Loop_idx;
                    }
                }
                break;

            case _Rx_unwind_ops::_Loop_simple_greedy_firstrep:
                { // try tail after backtracking from first rep
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);

                    _Nx             = _Node->_End_rep->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;
                }
                break;

            case _Rx_unwind_ops::_Loop_simple_greedy_intermediaterep:
                {
                    // shift capturing groups, set up unwinding prior rep and try tail
                    // when backtracking between the second and the last attempted rep
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);

                    // adjust capturing group begin and end iterators by rep length
                    auto& _Sav = _Loop_vals[_Node->_Loop_number];
                    for (auto _Capture_frame_idx = _Frame._Loop_frame_idx_sav + 1U; _Capture_frame_idx != _Frames_count;
                        ++_Capture_frame_idx) {
                        const auto& _Capture_frame = _Frames[_Capture_frame_idx];
                        _STL_INTERNAL_CHECK(_Capture_frame._Code == _Rx_unwind_ops::_Capture_restore_begin
                                            || _Capture_frame._Code == _Rx_unwind_ops::_Capture_restore_matched_end
                                            || _Capture_frame._Code == _Rx_unwind_ops::_Capture_restore_unmatched_end);
                        auto& _Grp = _Tgt_state._Grps[_Capture_frame._Capture_idx];
                        _STD advance(
                            _Capture_frame._Code == _Rx_unwind_ops::_Capture_restore_begin ? _Grp._Begin : _Grp._End,
                            -_Sav._Loop_length);
                    }
                }
                _FALLTHROUGH;

            case _Rx_unwind_ops::_Loop_simple_greedy_lastrep:
                {
                    // set up unwinding prior rep and try tail
                    // when backtracking from last attempted rep
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);

                    _Nx             = _Node->_End_rep->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;

                    auto& _Sav = _Loop_vals[_Node->_Loop_number];
                    _STD advance(_Frame._Pos, -_Sav._Loop_length);

                    // set up unwinding if prior rep is not first or minimum rep
                    if (_Frames[_Frame._Loop_frame_idx_sav]._Pos != _Frame._Pos) {
                        _Frame._Code = _Rx_unwind_ops::_Loop_simple_greedy_intermediaterep;
                        ++_Frames_count;
                    }
                }
                break;

            case _Rx_unwind_ops::_Loop_greedy:
                { // try tail
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);

                    _Nx             = _Node->_End_rep->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;
                }
                _FALLTHROUGH;

            case _Rx_unwind_ops::_Loop_restore_vals:
                { // restore loop vals after processing of a rep is completed
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);
                    auto& _Sav = _Loop_vals[_Node->_Loop_number];

                    _Sav._Loop_idx       = _Frame._Loop_idx_sav;
                    _Sav._Loop_frame_idx = _Frame._Loop_frame_idx_sav;
                }
                break;

            case _Rx_unwind_ops::_Loop_nongreedy:
                { // try another rep
                    auto _Node = static_cast<_Node_rep*>(_Frame._Node);
                    auto& _Sav = _Loop_vals[_Node->_Loop_number];

                    _Nx             = _Node->_Next;
                    _Tgt_state._Cur = _Frame._Pos;
                    _Failed         = false;
                    if (_Sav._Loop_idx < INT_MAX) { // avoid overflowing _Loop_idx
                        ++_Sav._Loop_idx;
                    }

                    _Frame._Code = _Rx_unwind_ops::_Loop_restore_vals;
                    ++_Frames_count;
                    _Reset_capture_groups(_Sav._Group_first);
                }
                break;

            case _Rx_unwind_ops::_Capture_restore_begin:
                { // restore begin of capturing group
                    _Tgt_state._Grps[_Frame._Capture_idx]._Begin = _Frame._Pos;
                }
                break;

            case _Rx_unwind_ops::_Capture_restore_unmatched_end:
                { // restore end of capturing group that was previously unmatched
                    _Tgt_state._Grp_valid._Clear(_Frame._Capture_idx);
                }
                _FALLTHROUGH;

            case _Rx_unwind_ops::_Capture_restore_matched_end:
                { // restore end of capturing group that was already matched
                    _Tgt_state._Grps[_Frame._Capture_idx]._End = _Frame._Pos;
                }
                break;

            case _Rx_unwind_ops::_Capture_restore_matched:
                { // restore matched status of capturing group
                    _Tgt_state._Grp_valid._Set(_Frame._Capture_idx);
                }
                break;

            default:
#if _ITERATOR_DEBUG_LEVEL != 0
                _STL_REPORT_ERROR("internal stack of regex matcher corrupted");
#endif
                return false;
            }
        }
    }

    _STL_INTERNAL_CHECK(_Frames_count == 0);

    return !_Failed;
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
template <class _BidIt, class _Alsubmatch>
void _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Copy_captures(match_results<_BidIt, _Alsubmatch>& _Matches) {
    // copy captures into match_results
    _Matches._Resize(_Ncap);
    const auto& _Result = _Longest ? _Res : _Tgt_state;

    auto& _Submatch0   = _Matches._At(0U);
    _Submatch0.matched = true;
    _Submatch0.first   = _Begin;
    _Submatch0.second  = _Result._Cur;

    for (unsigned int _Idx = 1U; _Idx < _Ncap; ++_Idx) { // copy submatch _Idx
        if (_Result._Grp_valid._Get(_Idx - 1U)) { // copy successful match
            _Matches._At(_Idx).matched = true;
            _Matches._At(_Idx).first   = _Result._Grps[_Idx - 1U]._Begin;
            _Matches._At(_Idx).second  = _Result._Grps[_Idx - 1U]._End;
        } else { // copy failed match
            _Matches._At(_Idx).matched = false;
            _Matches._At(_Idx).first   = _End;
            _Matches._At(_Idx).second  = _End;
        }
    }
    _Matches._Pfx().second = _Matches._At(0).first;

    _Matches._Sfx().first   = _Matches._At(0).second;
    _Matches._Sfx().second  = _End;
    _Matches._Sfx().matched = _Matches._Sfx().first != _Matches._Sfx().second;

    _Matches._Null().first  = _End;
    _Matches._Null().second = _End;
}

template <class _FwdIt, class _Int>
void _Advance_at_most(_FwdIt& _Pos, const _FwdIt& _Last, _Int _Amount) {
    if constexpr (_Is_ranges_random_iter_v<_FwdIt>) {
        auto _Shift_amount = _Last - _Pos;
        if (_Shift_amount > _Amount) {
            _Shift_amount = static_cast<decltype(_Shift_amount)>(_Amount);
        }

        _Pos += _Shift_amount;
    } else {
        while (_Amount > 0 && _Pos != _Last) {
            ++_Pos;
            --_Amount;
        }
    }
}

template <class _Elem, class _RxTraits, class _It, class _Alloc>
_It _Matcher3<_Elem, _RxTraits, _It, _Alloc>::_Skip(
    _It _First, const _It _Last, const _Node_base* const _Node_arg, const unsigned int _Recursion_depth) {
    // skip until possible match
    // assumes --_First is valid
    static constexpr char _Line_terminators_char[]       = {static_cast<char>(_Meta_cr), static_cast<char>(_Meta_nl)};
    static constexpr wchar_t _Line_terminators_wchar_t[] = {static_cast<wchar_t>(_Meta_cr),
        static_cast<wchar_t>(_Meta_nl), static_cast<wchar_t>(_Meta_ls), static_cast<wchar_t>(_Meta_ps)};
    constexpr unsigned int _Max_recursion_depth          = 50U;
    constexpr short _Max_lookahead                       = 512;
    const _Node_base* _Nx                                = _Node_arg ? _Node_arg : _Start;

    while (_First != _Last && _Nx) { // check current node
        switch (_Nx->_Kind) { // handle current node's type
        case _N_nop:
            break;

        case _N_bol: // check for beginning anchor
            if (_Sflags & regex_constants::multiline) {
                // multiline mode: check for embedded line terminator
                // return iterator to character just after the newline; for input like "\nabc"
                // matching "^abc", _First could be pointing at 'a', so we need to check --_First for '\n'
                if (!_STD _Is_ecmascript_line_terminator(*_STD _Prev_iter(_First))) {
                    if constexpr (sizeof(_Elem) == 1) {
                        _First =
                            _STD find_first_of(_First, _Last, _Line_terminators_char, _STD end(_Line_terminators_char));
                    } else {
                        _First = _STD find_first_of(
                            _First, _Last, _Line_terminators_wchar_t, _STD end(_Line_terminators_wchar_t));
                    }

                    if (_First != _Last) {
                        ++_First;
                    }
                }

                return _First;
            } else {
                // non-multiline mode: never matches because --_First is valid
                return _Last;
            }

        case _N_eol:
            if (_Sflags & regex_constants::multiline) {
                // multiline mode: matches at next line terminator or end of input
                if constexpr (sizeof(_Elem) == 1) {
                    return _STD find_first_of(_First, _Last, _Line_terminators_char, _STD end(_Line_terminators_char));
                } else {
                    return _STD find_first_of(
                        _First, _Last, _Line_terminators_wchar_t, _STD end(_Line_terminators_wchar_t));
                }
            } else {
                return _Last; // non-multiline mode: matches at end of input or not at all
            }

        case _N_str:
            { // check for string match
                const auto _Node         = static_cast<const _Node_str<_Elem>*>(_Nx);
                const auto _Str          = _Node->_Data._Str();
                const unsigned int _Size = _Node->_Data._Size();

                auto _Shifted_last = _Last;
                if (_Last != _End && _Size > 1U) { // have to continue search beyond the search window
                    _STD _Advance_at_most(_Shifted_last, _End, static_cast<long long>(_Size - 1U));
                }

                auto _Result = _STD _Search_translate_left(_First, _Shifted_last, _Str, _Str + _Size, _Traits, _Sflags);
                if (_Shifted_last == _Result) { // correct for search window shift
                    return _Last;
                } else {
                    return _Result;
                }
            }

        case _N_class:
            { // check for string match
                const auto _Node = static_cast<const _Node_class<_Elem, _RxTraits>*>(_Nx);

                for (; _First != _Last; ++_First) { // look for starting match
                    if (_Do_class(_Node, _First) != _First) { // may read beyond search window
                        return _First;
                    }
                }
            }
            return _First;

        case _N_group:
            break;

        case _N_end_group:
            break;

        case _N_end_assert:
            _Nx = nullptr;
            break;

        case _N_capture:
            break;

        case _N_end_capture:
            break;

        case _N_if:
            {
                const auto _Node = static_cast<const _Node_if*>(_Nx);

                // TRANSITION, ABI: After GH-5539, the parser no longer generates single-branch _N_if nodes.
                // But we retain this special handling to avoid some performance regression
                // when an old parser gets mixed with a new matcher.
                if (!_Node->_Child) {
                    break;
                }

                if (_Recursion_depth >= _Max_recursion_depth) {
                    return _First;
                }

                // GH-5452: If this node has two or more branches, examining all alternatives in a disjunction
                // until the end of the input string could result in quadratic worst-case complexity.
                // For this reason, we split the input string into search windows with a constant maximum length.
                // This ensures that this heuristic has linear time complexity, because this bounds the number
                // of characters that were read beyond the finally determined skip position by a constant.

                for (;;) {
                    _It _Lookahead_last = _First;
                    _STD _Advance_at_most(_Lookahead_last, _Last, _Max_lookahead);

                    _It _Alt_last = _Lookahead_last;

                    for (const _Node_if* _Alternative = _Node; _Alternative && _First != _Alt_last;
                        _Alternative                  = _Alternative->_Child) {
                        _Alt_last = _Skip(_First, _Alt_last, _Alternative->_Next, _Recursion_depth + 1U);
                    }

                    _First = _Alt_last;
                    if (_First != _Lookahead_last || _First == _Last) {
                        break;
                    }
                }

                return _First;
            }

        case _N_rep:
            {
                const auto _Node = static_cast<const _Node_rep*>(_Nx);

                if (_Node->_Min > 0) {
                    break;
                }

                if (_Recursion_depth >= _Max_recursion_depth) {
                    return _First;
                }

                // As in GH-5452, examining the cases with no repetition and at least one repetition
                // until the end of the input string could result in quadratic worst-case complexity.
                // For this reason, we split the input string into search windows with a constant maximum length.
                // This ensures that this heuristic has linear time complexity, because this bounds the number
                // of characters that were read beyond the finally determined skip position by a constant.

                for (;;) {
                    _It _Lookahead_last = _First;
                    _STD _Advance_at_most(_Lookahead_last, _Last, _Max_lookahead);
                    const _It _Intermediate = _Skip(_First, _Lookahead_last, _Node->_Next, _Recursion_depth + 1U);
                    _First = _Skip(_First, _Intermediate, _Node->_End_rep->_Next, _Recursion_depth + 1U);

                    if (_First != _Lookahead_last || _First == _Last) {
                        break;
                    }
                }

                return _First;
            }

        case _N_assert:
            {
                if (_Recursion_depth >= _Max_recursion_depth) {
                    return _First;
                }

                const auto _Node = static_cast<const _Node_assert*>(_Nx);
                _First           = _Skip(_First, _Last, _Node->_Child, _Recursion_depth + 1U);
                _It _Next;
                for (;;) {
                    _Next = _Skip(_First, _Last, _Node->_Next, _Recursion_depth + 1U);
                    if (_Next == _First) {
                        return _First;
                    }

                    _First = _Skip(_Next, _Last, _Node->_Child, _Recursion_depth + 1U);
                    if (_Next == _First) {
                        return _First;
                    }
                }
            }

        case _N_neg_assert:
            // we skip the negated assertion body and continue examining the rest of the regex
            break;

        case _N_wbound:
            {
                const bool _Negated = (_Nx->_Flags & _Fl_negate) != 0;
                bool _Prev_word     = _STD _Is_word(*_STD _Prev_iter(_First));
                for (; _First != _Last; ++_First) {
                    const bool _Next_word = _STD _Is_word(*_First);
                    if (_Negated == (_Next_word == _Prev_word)) {
                        break;
                    }
                    _Prev_word = _Next_word;
                }
                return _First;
            }

        case _N_dot:
            {
                if (_Recursion_depth >= _Max_recursion_depth) {
                    return _First;
                }

                _First = _Skip(++_First, _Last, _Nx->_Next, _Recursion_depth + 1U);
                return --_First;
            }

        case _N_begin:
        case _N_endif:
            break;

        case _N_end:
        case _N_none:
        case _N_back:
        case _N_end_rep:
        default:
            return _First;
        }
        if (_Nx) {
            _Nx = _Nx->_Next;
        }
    }
    return _First;
}

template <class _FwdIt, class _Elem, class _RxTraits>
[[noreturn]] void _Parser2<_FwdIt, _Elem, _RxTraits>::_Error(regex_constants::error_type _Code) { // handle error
    _Xregex_error(_Code);
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_Is_esc(_FwdIt _Ch0) const { // assumes _Ch0 != _End
    return _Mode == _Lex_mode::_Default && ++_Ch0 != _End
        && ((!(_L_flags & _L_nex_grp)
                && (*_Ch0 == static_cast<char>(_Meta_lpar) || *_Ch0 == static_cast<char>(_Meta_rpar)))
            || (!(_L_flags & _L_nex_rep)
                && (*_Ch0 == static_cast<char>(_Meta_lbr) || *_Ch0 == static_cast<char>(_Meta_rbr))));
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Trans() { // map character to meta-character
    static constexpr char _Meta_map[] = {_Meta_lpar, _Meta_rpar, _Meta_dlr, _Meta_caret, _Meta_dot, _Meta_star,
        _Meta_plus, _Meta_query, _Meta_lsq, _Meta_rsq, _Meta_bar, _Meta_esc, _Meta_dash, _Meta_lbr, _Meta_rbr,
        _Meta_comma, _Meta_colon, _Meta_equal, _Meta_exc, _Meta_nl, _Meta_cr, _Meta_bsp, 0}; // array of meta chars

    if (_Pat == _End) {
        _Mchar = _Meta_eos;
        _Char  = _Elem{};
    } else { // map current character
        _Char       = *_Pat;
        auto _Uchar = static_cast<unsigned char>(_Char);
        if (static_cast<_Elem>(_Uchar) == _Char && _CSTD strchr(_Meta_map, static_cast<char>(_Uchar))) {
            _Mchar = static_cast<_Meta_type>(_Uchar);
        } else {
            _Mchar = _Meta_chr;
        }
    }

    switch (int{_Mchar}) { // handle special cases
    case _Meta_esc:
        if (_Is_esc(_Pat)) { // replace escape sequence
            _FwdIt _Ch0 = _Pat;
            _Char       = *++_Ch0;
            _Mchar      = static_cast<_Meta_type>(static_cast<unsigned char>(_Char));
        }
        break;

    case _Meta_nl:
        if ((_L_flags & _L_alt_nl) && _Disj_count == 0) {
            _Mchar = _Meta_bar;
        }

        break;

    case _Meta_lpar:
    case _Meta_rpar:
        if (!(_L_flags & _L_nex_grp)) {
            _Mchar = _Meta_chr;
        }

        break;

    case _Meta_lbr:
    case _Meta_rbr:
        if (!(_L_flags & _L_nex_rep)) {
            _Mchar = _Meta_chr;
        }

        break;

    case _Meta_star:
        // A star can always act as a quantifier outside bracket expressions,
        // but _L_star_beg (used by basic/grep) allows its use as an ordinary character
        // at the beginning of a (sub-)expression (potentially after an optional caret anchor).
        // We'll handle that when we are parsing alternatives in disjunctions.
        break;

    case _Meta_caret:
        // A caret can always negate a bracket expression,
        // but _L_anch_rstr (used by basic/grep) restricts caret anchors to the beginning.
        // We'll handle that restriction when we're about to add a bol node.
        break;

    case _Meta_dlr:
        { // check if $ is special
            _FwdIt _Next = _Pat;
            if ((_L_flags & _L_anch_rstr) && ++_Next != _End) {
                const bool _Escaped = *_Next == static_cast<char>(_Meta_esc) && _Is_esc(_Next);
                if (_Escaped) {
                    ++_Next;
                }

                // Only the basic and grep grammars set _L_anch_rstr, so _L_alt_pipe and _L_nex_grp must be unset.
                // Therefore, we don't need to handle "dollar followed by pipe '|' for alternation"
                // or "dollar followed by non-escaped right parenthesis ')' closing a group" below.
                _STL_INTERNAL_CHECK((_L_flags & (_L_alt_pipe | _L_nex_grp)) == 0);

                const _Elem _Ch = *_Next;
                const bool _Is_end_of_alternative =
                    ((_L_flags & _L_alt_nl) && _Ch == static_cast<char>(_Meta_nl)
                        && _Disj_count == 0) // dollar followed by newline '\n' for alternation
                    || (_Escaped && _Ch == static_cast<char>(_Meta_rpar)
                        && _Disj_count != 0); // dollar followed by (escaped) right parenthesis ')' closing a group

                if (!_Is_end_of_alternative) {
                    _Mchar = _Meta_chr;
                }
            }

            break;
        }

    case _Meta_plus:
    case _Meta_query:
        if (!(_L_flags & _L_ext_rep)) {
            _Mchar = _Meta_chr;
        }

        break;

    case _Meta_bar:
        if (!(_L_flags & _L_alt_pipe)) {
            _Mchar = _Meta_chr;
        }

        break;

    default:
        break;
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Next() { // advance to next input character
    if (_Pat != _End) { // advance
        if (*_Pat == static_cast<char>(_Meta_esc) && _Is_esc(_Pat)) {
            ++_Pat;
        }

        ++_Pat;
    }
    _Trans();
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Expect(_Meta_type _St, regex_constants::error_type _Code) {
    // check whether current meta-character is _St
    if (_Mchar != _St) {
        _Error(_Code);
    }

    _Next();
}

template <class _FwdIt, class _Elem, class _RxTraits>
int _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_digits(
    int _Base, int _Initial, int _Count, regex_constants::error_type _Error_type) { // translate digits to numeric value
    int _Chv;
    _Val = _Initial;
    while (_Count != 0 && (_Chv = _Traits.value(_Char, _Base)) != -1) { // append next digit
        if (_Val > (INT_MAX - _Chv) / _Base) {
            _Error(_Error_type);
        }
        --_Count;
        _Val *= _Base;
        _Val += _Chv;
        _Next();
    }
    return _Count;
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_DecimalDigits(
    const regex_constants::error_type _Error_type, const int _Initial /* = 0 */) { // check for decimal value
    return _Do_digits(10, _Initial, INT_MAX, _Error_type) != INT_MAX;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_HexDigits(int _Count) { // check for _Count hex digits
    if (_Do_digits(16, 0, _Count, regex_constants::error_escape) != 0) {
        _Error(regex_constants::error_escape);
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_OctalDigits() { // check for up to 3 octal digits
    return _Do_digits(8, 0, 3, regex_constants::error_escape) != 3;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Prs_ret _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_ex_class(
    _Meta_type _End_arg) { // handle delimited expressions within bracket expression
    const regex_constants::error_type _Errtype =
        _End_arg == _Meta_colon ? regex_constants::error_ctype : regex_constants::error_collate;
    const _FwdIt _Beg = _Pat;

    while (_Mchar != _Meta_colon && _Mchar != _Meta_equal && _Mchar != _Meta_dot && _Mchar != _Meta_eos) {
        // advance to end delimiter
        _Next();
    }

    const _FwdIt _End = _Pat;
    _Expect(_End_arg, _Errtype);
    _Expect(_Meta_rsq, _Errtype);

    if (_End_arg == _Meta_colon) { // handle named character class
        typename _RxTraits::char_class_type _Cls =
            _Traits.lookup_classname(_Beg, _End, (_Flags & regex_constants::icase) != 0);
        if (!_Cls) {
            _Error(regex_constants::error_ctype);
        }

        _Nfa._Add_named_class(_Cls, _Rx_char_class_kind::_Positive);
        return _Prs_set;
    } else {
        typename _RxTraits::string_type _Coll_elem = _Traits.lookup_collatename(_Beg, _End);
        const auto _Size                           = _Coll_elem.size();

        if (_Size == 0) {
            _Error(regex_constants::error_collate);
        }

        if (_Size > _Max_limit<unsigned int>()) {
            _Error(regex_constants::error_space);
        }

        _Elem* const _Coll_elem_first      = &_Coll_elem.front();
        const _Elem* const _Coll_elem_last = _Coll_elem_first + _Size;

        if (_Size == 1 && _End_arg == _Meta_dot) {
            // process single-element collating elements like individual characters
            _Unescaped_char = *_Coll_elem_first;
            return _Prs_chr;
        }

        if (_Flags & regex_constants::icase) {
            for (auto _Current = _Coll_elem_first; _Current != _Coll_elem_last; ++_Current) {
                *_Current = _Traits.translate_nocase(*_Current);
            }
        } else if (_Flags & regex_constants::collate) {
            for (auto _Current = _Coll_elem_first; _Current != _Coll_elem_last; ++_Current) {
                *_Current = _Traits.translate(*_Current);
            }
        }

        if (_End_arg == _Meta_equal) { // process equivalence
            _Nfa._Add_equiv(_Coll_elem_first, _Coll_elem_last);
            return _Prs_set;
        } else { // process collating element

            // Character ranges with multi-character bounds cannot be represented in NFA nodes yet (see GH-5391).
            // Provisionally treat multi-character collating elements as character sets.
            _Nfa._Add_coll(_Coll_elem_first, _Coll_elem_last);
            return _Prs_set;
        }
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_CharacterClassEscape(bool _Addit) { // check for character class escape
    typename _RxTraits::char_class_type _Cls;
    _FwdIt _Ch0 = _Pat;
    if (_Ch0 == _End || (_Cls = _Traits.lookup_classname(_Pat, ++_Ch0, (_Flags & regex_constants::icase) != 0)) == 0) {
        return false;
    }

    auto _Kind = (_Char == 'W'   ? _Rx_char_class_kind::_Negated_w
                  : _Char == 'S' ? _Rx_char_class_kind::_Negated_s
                  : _Char == 'D' ? _Rx_char_class_kind::_Negated_d
                                 : _Rx_char_class_kind::_Positive);

    if (_Addit) {
        _Nfa._Add_class();
        // GH-992: Outside character class definitions, _Cls completely defines the character class
        // so negating _Cls and negating the entire character class are equivalent.
        // Since the former negation is defective, do the latter instead.
        if (_Kind != _Rx_char_class_kind::_Positive) {
            _Nfa._Negate();
            _Kind = _Rx_char_class_kind::_Positive;
        }
    }

    _Nfa._Add_named_class(_Cls, _Kind);
    _Next();
    return true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Prs_ret _Parser2<_FwdIt, _Elem, _RxTraits>::_ClassEscape() { // check for class escape
    if ((_L_flags & _L_esc_bsp) && _Char == static_cast<char>(_Esc_ctrl_b)) { // handle backspace escape
        _Next();
        _Unescaped_char = static_cast<_Elem>(static_cast<char>(_Meta_bsp));
        return _Prs_chr;
    } else if ((_L_flags & (_L_bzr_chr | _L_bckr))
               && (_Val = _Traits.value(_Char, 10)) != -1) { // handle \0 and reject other escaped decimal literals
        _Next();
        if (!(_L_flags & _L_bzr_chr) || _Val != 0 || _Traits.value(_Char, 10) != -1) {
            _Error(regex_constants::error_escape);
        }

        _Unescaped_char = _Elem{};
        return _Prs_chr;
    } else if (_CharacterEscape(true)) {
        return _Prs_chr;
    } else if ((_L_flags & _L_esc_wsd) && _CharacterClassEscape(false)) {
        return _Prs_set;
    }

    _Error(regex_constants::error_escape);
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Prs_ret _Parser2<_FwdIt, _Elem, _RxTraits>::_ClassAtom(const bool _Initial) { // check for class atom
    if (_Mchar == _Meta_esc && (_L_flags & _L_grp_esc)) { // check for valid escape sequence
        _Next();
        return _ClassEscape();
    } else if (_Mchar == _Meta_lsq) { // check for valid delimited expression
        _Elem _Lsq = _Char;
        _Next();
        if (_Mchar == _Meta_colon || _Mchar == _Meta_equal || _Mchar == _Meta_dot) { // handle delimited expression
            _Meta_type _St = _Mchar;
            _Next();
            return _Do_ex_class(_St);
        } else { // handle ordinary [
            _Unescaped_char = _Lsq;
            return _Prs_chr;
        }
    } else if ((_Mchar == _Meta_rsq
                   && (!(_L_flags & _L_brk_rstr)
                       || !_Initial)) // initial ] does not close the class when it is not special
               || _Mchar == _Meta_eos) {
        return _Prs_none;
    } else { // handle ordinary character
        _Unescaped_char = _Char;
        _Next();
        return _Prs_chr;
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_ClassRanges() { // check for valid class ranges
    _Prs_ret _Ret;

    bool _Initial = true;
    for (;;) { // process characters through end of bracket expression
        if ((_Ret = _ClassAtom(_Initial)) == _Prs_none) {
            return;
        }
        _Initial = false;

        if (_Ret == _Prs_chr && !(_L_flags & _L_bzr_chr) && _Unescaped_char == _Elem{}) {
            _Error(regex_constants::error_escape);
        }

        if (_Mchar == _Meta_dash) { // check for valid range
            _Elem _Chr1 = _Unescaped_char;
            _Elem _Dash = _Char;
            _Next();
            const bool _Set_preceding = _Ret == _Prs_set;
            if ((_Ret = _ClassAtom(false)) == _Prs_none) { // treat - as ordinary character
                if (!_Set_preceding) {
                    _Nfa._Add_char_to_class(_Chr1);
                }
                _Nfa._Add_char_to_class(_Dash);
                return;
            }

            if (_Set_preceding || _Ret == _Prs_set) {
                _Error(regex_constants::error_range); // set precedes or follows dash
            }

            _Elem _Chr2 = _Unescaped_char;

            // translate ends of range
            if (_Flags & regex_constants::icase) {
                _Chr1 = _Traits.translate_nocase(_Chr1);
                _Chr2 = _Traits.translate_nocase(_Chr2);
            } else if (_Flags & regex_constants::collate) {
                _Chr1 = _Traits.translate(_Chr1);
                _Chr2 = _Traits.translate(_Chr2);
            }

            _Nfa._Add_range(_Chr1, _Chr2);
        } else if (_Ret == _Prs_chr) {
            _Nfa._Add_char_to_class(_Unescaped_char);
        }
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_CharacterClass() { // add bracket expression
    _Nfa._Add_class();
    if (_Mchar == _Meta_caret) { // negate bracket expression
        _Nfa._Negate();
        _Next();
    }

    _ClassRanges();
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_capture_group() { // add capture group
    ++_Grp_idx;

    if (_Grp_idx >= 1000) { // hardcoded limit
        _Xregex_error(regex_constants::error_stack);
    }

    _Node_base* _Pos1 = _Nfa._Begin_capture_group(_Grp_idx);
    _Disjunction();
    _Nfa._End_group(_Pos1);
    _Finished_grps.resize(_Grp_idx + 1);
    _Finished_grps[static_cast<_Node_capture*>(_Pos1)->_Idx] = true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_noncapture_group() { // add non-capture group
    _Node_base* _Pos1 = _Nfa._Begin_group();
    _Disjunction();
    _Nfa._End_group(_Pos1);
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_assert_group(bool _Neg) { // add assert group
    _Node_base* _Pos1 = _Nfa._Begin_assert_group(_Neg);
    _Disjunction();
    _Nfa._End_assert_group(_Pos1);
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_Wrapped_disjunction() { // add disjunction inside group
    ++_Disj_count;
    if (_Disj_count >= 1000) { // hardcoded limit
        _Error(regex_constants::error_stack);
    }

    if (!(_L_flags & _L_empty_grp) && _Mchar == _Meta_rpar) {
        _Error(regex_constants::error_paren);
    } else if ((_L_flags & _L_nc_asrt) && _Mchar == _Meta_query) { // check for valid ECMAScript (?x ... ) group
        _Next();
        _Meta_type _Ch = _Mchar;
        _Next();
        if (_Ch == _Meta_colon) { // process non-capture group (?:meow)
            _Do_noncapture_group();
        } else if (_Ch == _Meta_exc) { // process negative lookahead assertion (?!meow)
            _Do_assert_group(true);
            --_Disj_count;
            return false;
        } else if (_Ch == _Meta_equal) { // process positive lookahead assertion (?=meow)
            _Do_assert_group(false);
            --_Disj_count;
            return false;
        } else {
            _Error(regex_constants::error_badrepeat);
        }
    } else if (_Flags & regex_constants::nosubs) {
        _Do_noncapture_group();
    } else {
        _Do_capture_group();
    }

    --_Disj_count;
    return true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_IsIdentityEscape(bool _In_character_class) const {
    // check for valid identity escape
    auto _Uchar = static_cast<unsigned char>(_Char);

    if (_L_flags & _L_ident_ECMA) {
        // ECMAScript identity escape characters
        if (static_cast<_Elem>(_Uchar) != _Char) {
            return true;
        }

        switch (_Uchar) {
        case 'c': // ASCII control character
        case 'd': // digit
        case 'D':
        case 's': // whitespace
        case 'S':
        case 'w': // word character
        case 'W':
            return false;
        default:
            return true;
        }
    }

    if (static_cast<_Elem>(_Uchar) != _Char) {
        return false;
    }

    switch (_Uchar) {
    case _Meta_esc:
        // BRE, ERE, awk identity escape characters (anywhere in awk)
        return true;
    case _Meta_dot:
    case _Meta_lsq:
    case _Meta_rsq:
    case _Meta_star:
    case _Meta_caret:
    case _Meta_dlr:
        // BRE, ERE, awk identity escape characters (outside character classes only)
        return !_In_character_class;
    case _Meta_lpar:
    case _Meta_rpar:
    case _Meta_bar:
    case _Meta_plus:
    case _Meta_query:
    case _Meta_lbr:
    case _Meta_rbr:
        // additional ERE identity escape characters (outside character classes only)
        return (_L_flags & _L_ident_ERE) != 0 && !_In_character_class;
    case '"':
    case '/':
        // additional awk identity escape characters (anywhere)
        return (_L_flags & _L_ident_awk) != 0;
    default:
        return false;
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_IdentityEscape(bool _In_character_class) {
    // check whether an escape is valid, and process it if so
    if (_IsIdentityEscape(_In_character_class)) {
        _Unescaped_char = _Char;
        _Next();
        return true;
    } else {
        return false;
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_ffn(_Elem _Ch) { // check for limited file format escape characters
    if (_Ch == static_cast<char>(_Esc_ctrl_f)) {
        _Val = '\f';
    } else if (_Ch == static_cast<char>(_Esc_ctrl_n)) {
        _Val = '\n';
    } else if (_Ch == static_cast<char>(_Esc_ctrl_r)) {
        _Val = '\r';
    } else if (_Ch == static_cast<char>(_Esc_ctrl_t)) {
        _Val = '\t';
    } else if (_Ch == static_cast<char>(_Esc_ctrl_v)) {
        _Val = '\v';
    } else {
        return false;
    }

    return true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_Do_ffnx(_Elem _Ch) { // check for the remaining file format escape characters
    if (_Ch == static_cast<char>(_Esc_ctrl_a)) {
        _Val = '\a';
    } else if (_Ch == static_cast<char>(_Esc_ctrl_b)) {
        _Val = '\b';
    } else {
        return false;
    }

    return true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_CharacterEscape(bool _In_character_class) {
    // check for valid character escape
    if (_Mchar == _Meta_eos) {
        _Error(regex_constants::error_escape);
    }

    if ((_L_flags & _L_esc_ffn && _Do_ffn(_Char)) || (_L_flags & _L_esc_ffnx && _Do_ffnx(_Char))) {
        _Next();
    } else if (_Char == static_cast<char>(_Esc_ctrl) && (_L_flags & _L_esc_ctrl)) { // handle control escape sequence
        _Next();

        using _Char_traits_type = typename _RxTraits::string_type::traits_type;
        if ((_Char_traits_type::lt(_Char, static_cast<_Elem>('a'))
                || _Char_traits_type::lt(static_cast<_Elem>('z'), _Char))
            && (_Char_traits_type::lt(_Char, static_cast<_Elem>('A'))
                || _Char_traits_type::lt(static_cast<_Elem>('Z'), _Char))) {
            _Error(regex_constants::error_escape);
        }

        _Val = static_cast<unsigned char>(_Char) % 32;
        _Next();
    } else if (_Char == static_cast<char>(_Esc_hex) && (_L_flags & _L_esc_hex)) { // handle hexadecimal escape sequence
        _Next();
        _HexDigits(2);
    } else if (_Char == static_cast<char>(_Esc_uni) && (_L_flags & _L_esc_uni)) { // handle Unicode escape sequence
        _Next();
        _HexDigits(4);
    } else if ((_L_flags & _L_esc_oct) && _OctalDigits()) { // handle octal escape sequence
        if (_Val == 0) {
            _Error(regex_constants::error_escape);
        }
    } else {
        return _IdentityEscape(_In_character_class);
    }

    _Unescaped_char = static_cast<_Elem>(static_cast<unsigned int>(_Val));
    int _Cast_val;
    if constexpr (is_integral_v<_Elem> || is_enum_v<_Elem>) {
        _Cast_val = static_cast<int>(static_cast<make_unsigned_t<_Elem>>(_Unescaped_char));
    } else {
        _Cast_val = static_cast<int>(static_cast<unsigned int>(_Unescaped_char));
    }

    if (_Cast_val != _Val) {
        _Error(regex_constants::error_escape);
    }

    return true;
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_AtomEscape() { // check for valid atom escape
    if ((_L_flags & (_L_bzr_chr | _L_bckr)) && (_Val = _Traits.value(_Char, 10)) != -1) { // escaped decimal sequence
        _Next();
        if ((_L_flags & _L_bzr_chr) && _Val == 0) { // handle \0
            if (_Traits.value(_Char, 10) != -1) {
                _Error(regex_constants::error_escape);
            }
            _Nfa._Add_char(_Elem{});
        } else if (_L_flags & _L_bckr) { // check for valid backreference
            if (!(_L_flags & _L_lim_bckr)) {
                (void) _DecimalDigits(regex_constants::error_backref, _Val);
            }

            if (_Val == 0) {
                _Error(regex_constants::error_escape);
            } else if (_Grp_idx < static_cast<size_t>(_Val) || _Finished_grps.size() <= static_cast<size_t>(_Val)
                       || !_Finished_grps[static_cast<size_t>(_Val)]) {
                _Error(regex_constants::error_backref);
            } else {
                _Nfa._Add_backreference(static_cast<size_t>(_Val));
            }
        }
    } else if (_CharacterEscape(false)) {
        _Nfa._Add_char(_Unescaped_char);
    } else if (!(_L_flags & _L_esc_wsd) || !_CharacterClassEscape(true)) {
        _Error(regex_constants::error_escape);
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Quantifier() { // check for quantifier following atom
    int _Min = 0;
    int _Max = -1;
    if (_Mchar != _Meta_star) {
        if (_Mchar == _Meta_plus) {
            _Min = 1;
        } else if (_Mchar == _Meta_query) {
            _Max = 1;
        } else if (_Mchar == _Meta_lbr) { // check for valid bracketed value
            _Next();
            if (!_DecimalDigits(regex_constants::error_badbrace)) {
                _Error(regex_constants::error_badbrace);
            }

            _Min = _Val;
            if (_Mchar != _Meta_comma) {
                _Max = _Min;
            } else { // check for decimal constant following comma
                _Next();
                if (_Mchar != _Meta_rbr) {
                    if (!_DecimalDigits(regex_constants::error_badbrace)) {
                        _Error(regex_constants::error_badbrace);
                    }

                    _Max = _Val;
                }
            }

            if (_Mchar != _Meta_rbr || (_Max != -1 && _Max < _Min)) {
                _Error(regex_constants::error_badbrace);
            }
        } else {
            return;
        }
    }

    _Next();
    const bool _Greedy = !(_L_flags & _L_non_greedy) || _Mchar != _Meta_query;
    if (!_Greedy) { // add non-greedy repeat node
        _Next();
    }

    _Nfa._Add_rep(_Min, _Max, _Greedy);
}

template <class _FwdIt, class _Elem, class _RxTraits>
bool _Parser2<_FwdIt, _Elem, _RxTraits>::_Alternative() { // check for valid alternative
    bool _Found = false;
    for (;;) { // concatenate valid elements
        bool _Quant = true;
        if (_Mchar == _Meta_eos || _Mchar == _Meta_bar || (_Mchar == _Meta_rpar && _Disj_count != 0)) {
            return _Found;
        } else if (_Mchar == _Meta_rpar && !(_L_flags & _L_paren_bal)) {
            _Error(regex_constants::error_paren);
        } else if (_Mchar == _Meta_dot) { // add dot node
            _Nfa._Add_dot();
            _Next();
        } else if (_Mchar == _Meta_esc) { // check for valid escape sequence
            _Next();
            if ((_L_flags & _L_asrt_wrd) && _Char == static_cast<char>(_Esc_word)) { // add word assert
                _Nfa._Add_wbound();
                _Next();
                _Quant = false;
            } else if ((_L_flags & _L_asrt_wrd) && _Char == static_cast<char>(_Esc_not_word)) { // add not-word assert
                _Nfa._Add_wbound();
                _Nfa._Negate();
                _Next();
                _Quant = false;
            } else {
                _AtomEscape();
            }
        } else if (_Mchar == _Meta_lsq) { // add bracket expression
            _Mode = _Lex_mode::_Character_class;
            _Next();
            _CharacterClass();
            _Mode = _Lex_mode::_Default;
            _Expect(_Meta_rsq, regex_constants::error_brack);
        } else if (_Mchar == _Meta_lpar) { // check for valid group
            _Next();
            _Quant = _Wrapped_disjunction();
            _Expect(_Meta_rpar, regex_constants::error_paren);
        } else if (_Mchar == _Meta_caret && (!(_L_flags & _L_anch_rstr) || !_Found)) { // add bol node
            _Nfa._Add_bol();
            _Next();
            if ((_L_flags & _L_star_beg) && _Mchar == _Meta_star && !_Found) {
                _Nfa._Add_char(_Char);
                _Next();
            } else {
                _Quant = false;
            }
        } else if (_Mchar == _Meta_dlr) { // add eol node
            _Nfa._Add_eol();
            _Next();
            _Quant = false;
        } else if ((_Mchar == _Meta_star && (!(_L_flags & _L_star_beg) || _Found)) || _Mchar == _Meta_plus
                   || _Mchar == _Meta_query || _Mchar == _Meta_lbr) {
            _Error(regex_constants::error_badrepeat);
        } else if (_Mchar == _Meta_rbr && !(_L_flags & _L_paren_bal)) {
            _Error(regex_constants::error_brace);
        } else if (_Mchar == _Meta_rsq && !(_L_flags & _L_brk_bal)) {
            _Error(regex_constants::error_brack);
        } else { // add character
            _Nfa._Add_char(_Char);
            _Next();
        }

        if (_Quant) {
            _Quantifier();
        }

        _Found = true;
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Disjunction() { // check for valid disjunction
    _Node_base* _Pos1 = _Nfa._Getmark();
    if (!_Alternative()) {
        if (_Mchar != _Meta_bar) {
            return; // zero-length alternative not followed by '|'
        }

        // zero-length leading alternative
        _Node_base* _Pos3 = _Nfa._Begin_group();
        _Nfa._End_group(_Pos3);
    }

    if (_Mchar == _Meta_bar) {
        _Node_base* _Pos2 = _Nfa._Begin_if(_Pos1);
        do { // append terms as long as we keep finding | characters
            _Next();
            if (!_Alternative()) { // zero-length trailing alternative
                _Node_base* _Pos3 = _Nfa._Begin_group();
                _Nfa._End_group(_Pos3);
            }

            _Nfa._Else_if(_Pos1, _Pos2);
        } while (_Mchar == _Meta_bar);
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
void _Parser2<_FwdIt, _Elem, _RxTraits>::_Calculate_loop_simplicity(
    _Node_base* _Nx, _Node_base* _Ne, _Node_rep* _Outer_rep, const bool _Nonreentrant) {
    // walks regex NFA, calculates values of _Node_rep::_Simple_loop
    for (; _Nx != _Ne && _Nx; _Nx = _Nx->_Next) {
        switch (_Nx->_Kind) {
        case _N_if:
            // _Node_if inside a _Node_rep makes the rep not simple
            if (_Outer_rep) {
                _Outer_rep->_Simple_loop = 0;
                _Outer_rep->_Flags &= ~_Fl_rep_branchless;
            }

            // visit each branch of the if
            for (_Node_if* _Branch = static_cast<_Node_if*>(_Nx)->_Child; _Branch; _Branch = _Branch->_Child) {
                _Calculate_loop_simplicity(_Branch->_Next, _Branch->_Endif, _Outer_rep, _Nonreentrant);
            }
            break;

        case _N_assert:
            // A positive lookahead assertion inside a _Node_rep makes the rep not simple
            if (_Outer_rep) {
                _Outer_rep->_Simple_loop = 0;
                _Outer_rep->_Flags &= ~_Fl_rep_branchless;
            }
            _FALLTHROUGH;

        case _N_neg_assert:
            // visit the assertion body
            // note _Outer_rep being reset: the assertion regex is completely independent
            _Calculate_loop_simplicity(static_cast<_Node_assert*>(_Nx)->_Child, nullptr, nullptr, true);
            break;

        case _N_rep:
            // _Node_rep inside another _Node_rep makes both not simple if _Outer_rep can be repeated more than once
            // because the matcher does not reset capture group boundaries when handling simple loops.
            // If _Outer_rep can repeat at most once, we have to analyze the structure of the inner loop.
            if (_Outer_rep) {
                _Outer_rep->_Simple_loop = 0;
                _Outer_rep->_Flags &= ~_Fl_rep_branchless;
                auto _Inner_rep = static_cast<_Node_rep*>(_Nx);
                _Inner_rep->_Flags |= _Fl_rep_branchless;
                const bool _Inner_nonreentrant = _Outer_rep->_Max >= 0 && _Outer_rep->_Max <= 1 && _Nonreentrant;
                if (!_Inner_nonreentrant) {
                    _Inner_rep->_Simple_loop = 0;
                }

                _Calculate_loop_simplicity(
                    _Inner_rep->_Next, _Inner_rep->_End_rep->_Next, _Inner_rep, _Inner_nonreentrant);
                _Nx = _Inner_rep->_End_rep;
            } else {
                _Outer_rep = static_cast<_Node_rep*>(_Nx);
                _Outer_rep->_Flags |= _Fl_rep_branchless;
            }
            break;

        case _N_end_rep:
            if (_Outer_rep == static_cast<_Node_end_rep*>(_Nx)->_Begin_rep) {
                // if the _Node_rep is still undetermined when we reach its end, it is simple
                _Analysis_assume_(_Outer_rep);
                if (_Outer_rep->_Simple_loop == -1) {
                    _Outer_rep->_Simple_loop = 1;
                }
                _Outer_rep = nullptr;
            }
            break;

        case _N_class:
            if (_Outer_rep) {
                // _Node_rep is not simple if a class can match character sequences of different lengths
                auto _Node = static_cast<const _Node_class<_Elem, _RxTraits>*>(_Nx);
                bool _Coll_diff_size =
                    _Node->_Coll
                    && (_Node->_Small || _Node->_Large || _Node->_Ranges || _Node->_Classes || _Node->_Coll->_Next);
                if (_Coll_diff_size || _Node->_Equiv
                    || ((_Flags & regex_constants::collate) && (_Node->_Ranges || (_Node->_Flags & _Fl_negate)))) {
                    _Outer_rep->_Simple_loop = 0;
                    _Outer_rep->_Flags &= ~_Fl_rep_branchless;
                }
            }
            break;

        case _N_back:
            if (_Outer_rep && !_Nonreentrant) {
                // The content and thus length of a back-reference may change
                // when a loop is reentered
                _Outer_rep->_Flags &= ~_Fl_rep_branchless;
            }
            break;

        case _N_group:
        case _N_capture:
        case _N_none:
        case _N_nop:
        case _N_bol:
        case _N_eol:
        case _N_wbound:
        case _N_dot:
        case _N_str:
        case _N_end_group:
        case _N_end_assert:
        case _N_end_capture:
        case _N_endif:
        case _N_begin:
        case _N_end:
        default:
            break;
        }
    }
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Root_node* _Parser2<_FwdIt, _Elem, _RxTraits>::_Compile() { // compile regular expression
    _Root_node* _Res = nullptr;
    _Tidy_guard<decltype(_Nfa)> _Guard{_STD addressof(_Nfa)};
    _Node_base* _Pos1 = _Nfa._Begin_capture_group(0);
    _Disjunction();
    _STL_INTERNAL_CHECK(_Pat == _End);

    _Nfa._End_group(_Pos1);
    _Res         = _Nfa._End_pattern();
    _Res->_Fl    = _Flags;
    _Res->_Marks = _Mark_count();
    _Calculate_loop_simplicity(_Res, nullptr, nullptr, true);
    _Guard._Target = nullptr;
    return _Res;
}

template <class _FwdIt, class _Elem, class _RxTraits>
_Parser2<_FwdIt, _Elem, _RxTraits>::_Parser2(
    const _RxTraits& _Tr, _FwdIt _Pfirst, _FwdIt _Plast, regex_constants::syntax_option_type _Fx)
    : _Pat(_Pfirst), _End(_Plast), _Nfa(_Tr, _Fx), _Traits(_Tr), _Flags(_Fx) {

    constexpr unsigned long long _ECMA_flags = _L_ext_rep | _L_alt_pipe | _L_nex_grp | _L_nex_rep | _L_nc_asrt
                                             | _L_asrt_wrd | _L_bckr | _L_non_greedy | _L_esc_uni | _L_esc_hex
                                             | _L_esc_bsp | _L_esc_ffn | _L_esc_wsd | _L_esc_ctrl | _L_bzr_chr
                                             | _L_grp_esc | _L_ident_ECMA | _L_empty_grp;

    constexpr unsigned long long _Basic_flags = _L_bckr | _L_lim_bckr | _L_anch_rstr | _L_star_beg | _L_empty_grp
                                              | _L_brk_bal | _L_brk_rstr | _L_dsh_rstr | _L_mtch_long;

    constexpr unsigned long long _Grep_flags = _Basic_flags | _L_alt_nl | _L_no_nl;

    constexpr unsigned long long _Extended_flags = _L_ext_rep | _L_alt_pipe | _L_nex_grp | _L_nex_rep | _L_ident_ERE
                                                 | _L_paren_bal | _L_brk_bal | _L_brk_rstr | _L_dsh_rstr | _L_mtch_long;

    constexpr unsigned long long _Awk_flags =
        _Extended_flags | _L_esc_oct | _L_esc_ffn | _L_esc_ffnx | _L_grp_esc | _L_ident_awk;

    constexpr unsigned long long _Egrep_flags = _Extended_flags | _L_alt_nl | _L_no_nl;

    const regex_constants::syntax_option_type _Masked = _Flags & regex_constants::_Gmask;

    if (_Masked == regex_constants::ECMAScript || _Masked == 0) {
        _L_flags = _ECMA_flags;
    } else if (_Masked == regex_constants::basic) {
        _L_flags = _Basic_flags;
    } else if (_Masked == regex_constants::extended) {
        _L_flags = _Extended_flags;
    } else if (_Masked == regex_constants::awk) {
        _L_flags = _Awk_flags;
    } else if (_Masked == regex_constants::grep) {
        _L_flags = _Grep_flags;
    } else if (_Masked == regex_constants::egrep) {
        _L_flags = _Egrep_flags;
    } else {
        _L_flags = 0;
    }

    if (_L_flags & _L_mtch_long) {
        _Nfa._Setlong();
    }

    _Trans();
}

#if _HAS_CXX17
namespace pmr {
    _EXPORT_STD template <class _BidIt>
    using match_results = _STD match_results<_BidIt, polymorphic_allocator<sub_match<_BidIt>>>;

    _EXPORT_STD using cmatch  = match_results<const char*>;
    _EXPORT_STD using wcmatch = match_results<const wchar_t*>;
    _EXPORT_STD using smatch  = match_results<string::const_iterator>;
    _EXPORT_STD using wsmatch = match_results<wstring::const_iterator>;
} // namespace pmr
#endif // _HAS_CXX17
_STD_END
#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // _STL_COMPILER_PREPROCESSOR
#endif // _REGEX_
