brintos / llvm-project-archived public Read only

1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_REGEX11#define _LIBCPP___CXX03_REGEX12 13/*14    regex synopsis15 16#include <__cxx03/compare>17#include <__cxx03/initializer_list>18 19namespace std20{21 22namespace regex_constants23{24 25enum syntax_option_type26{27    icase      = unspecified,28    nosubs     = unspecified,29    optimize   = unspecified,30    collate    = unspecified,31    ECMAScript = unspecified,32    basic      = unspecified,33    extended   = unspecified,34    awk        = unspecified,35    grep       = unspecified,36    egrep      = unspecified,37    multiline  = unspecified38};39 40constexpr syntax_option_type operator~(syntax_option_type f);41constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);42constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);43 44enum match_flag_type45{46    match_default     = 0,47    match_not_bol     = unspecified,48    match_not_eol     = unspecified,49    match_not_bow     = unspecified,50    match_not_eow     = unspecified,51    match_any         = unspecified,52    match_not_null    = unspecified,53    match_continuous  = unspecified,54    match_prev_avail  = unspecified,55    format_default    = 0,56    format_sed        = unspecified,57    format_no_copy    = unspecified,58    format_first_only = unspecified59};60 61constexpr match_flag_type operator~(match_flag_type f);62constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);63constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);64 65enum error_type66{67    error_collate    = unspecified,68    error_ctype      = unspecified,69    error_escape     = unspecified,70    error_backref    = unspecified,71    error_brack      = unspecified,72    error_paren      = unspecified,73    error_brace      = unspecified,74    error_badbrace   = unspecified,75    error_range      = unspecified,76    error_space      = unspecified,77    error_badrepeat  = unspecified,78    error_complexity = unspecified,79    error_stack      = unspecified80};81 82}  // regex_constants83 84class regex_error85    : public runtime_error86{87public:88    explicit regex_error(regex_constants::error_type ecode);89    regex_constants::error_type code() const;90};91 92template <class charT>93struct regex_traits94{95public:96    typedef charT                   char_type;97    typedef basic_string<char_type> string_type;98    typedef locale                  locale_type;99    typedef /bitmask_type/          char_class_type;100 101    regex_traits();102 103    static size_t length(const char_type* p);104    charT translate(charT c) const;105    charT translate_nocase(charT c) const;106    template <class ForwardIterator>107        string_type108        transform(ForwardIterator first, ForwardIterator last) const;109    template <class ForwardIterator>110        string_type111        transform_primary( ForwardIterator first, ForwardIterator last) const;112    template <class ForwardIterator>113        string_type114        lookup_collatename(ForwardIterator first, ForwardIterator last) const;115    template <class ForwardIterator>116        char_class_type117        lookup_classname(ForwardIterator first, ForwardIterator last,118                         bool icase = false) const;119    bool isctype(charT c, char_class_type f) const;120    int value(charT ch, int radix) const;121    locale_type imbue(locale_type l);122    locale_type getloc()const;123};124 125template <class charT, class traits = regex_traits<charT>>126class basic_regex127{128public:129    // types:130    typedef charT                               value_type;131    typedef traits                              traits_type;132    typedef typename traits::string_type        string_type;133    typedef regex_constants::syntax_option_type flag_type;134    typedef typename traits::locale_type        locale_type;135 136    // constants:137    static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;138    static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;139    static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;140    static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;141    static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;142    static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;143    static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;144    static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;145    static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;146    static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;147    static constexpr regex_constants::syntax_option_type multiline = regex_constants::multiline;148 149    // construct/copy/destroy:150    basic_regex();151    explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);152    basic_regex(const charT* p, size_t len, flag_type f = regex_constants::ECMAScript);153    basic_regex(const basic_regex&);154    basic_regex(basic_regex&&) noexcept;155    template <class ST, class SA>156        explicit basic_regex(const basic_string<charT, ST, SA>& p,157                             flag_type f = regex_constants::ECMAScript);158    template <class ForwardIterator>159        basic_regex(ForwardIterator first, ForwardIterator last,160                    flag_type f = regex_constants::ECMAScript);161    basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);162 163    ~basic_regex();164 165    basic_regex& operator=(const basic_regex&);166    basic_regex& operator=(basic_regex&&) noexcept;167    basic_regex& operator=(const charT* ptr);168    basic_regex& operator=(initializer_list<charT> il);169    template <class ST, class SA>170        basic_regex& operator=(const basic_string<charT, ST, SA>& p);171 172    // assign:173    basic_regex& assign(const basic_regex& that);174    basic_regex& assign(basic_regex&& that) noexcept;175    basic_regex& assign(const charT* ptr,           flag_type f = regex_constants::ECMAScript);176    basic_regex& assign(const charT* p, size_t len, flag_type f = regex_constants::ECMAScript);177    template <class string_traits, class A>178        basic_regex& assign(const basic_string<charT, string_traits, A>& s,179                                                    flag_type f = regex_constants::ECMAScript);180    template <class InputIterator>181        basic_regex& assign(InputIterator first, InputIterator last,182                                                    flag_type f = regex_constants::ECMAScript);183    basic_regex& assign(initializer_list<charT>,    flag_type f = regex_constants::ECMAScript);184 185    // const operations:186    unsigned mark_count() const;187    flag_type flags() const;188 189    // locale:190    locale_type imbue(locale_type loc);191    locale_type getloc() const;192 193    // swap:194    void swap(basic_regex&);195};196 197template<class ForwardIterator>198basic_regex(ForwardIterator, ForwardIterator,199            regex_constants::syntax_option_type = regex_constants::ECMAScript)200    -> basic_regex<typename iterator_traits<ForwardIterator>::value_type>; // C++17201 202typedef basic_regex<char>    regex;203typedef basic_regex<wchar_t> wregex;204 205template <class charT, class traits>206    void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);207 208template <class BidirectionalIterator>209class sub_match210    : public pair<BidirectionalIterator, BidirectionalIterator>211{212public:213    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;214    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;215    typedef BidirectionalIterator                                      iterator;216    typedef basic_string<value_type>                                string_type;217 218    bool matched;219 220    constexpr sub_match();221 222    difference_type length() const;223    operator string_type() const;224    string_type str() const;225 226    int compare(const sub_match& s) const;227    int compare(const string_type& s) const;228    int compare(const value_type* s) const;229 230    void swap(sub_match& s) noexcept(see below);231};232 233typedef sub_match<const char*>             csub_match;234typedef sub_match<const wchar_t*>          wcsub_match;235typedef sub_match<string::const_iterator>  ssub_match;236typedef sub_match<wstring::const_iterator> wssub_match;237 238template <class BiIter>239    bool240    operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);241 242template <class BiIter>243    auto244    operator<=>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs); // Since C++20245 246 template <class BiIter>                                                     // Removed in C++20247    bool248    operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);249 250template <class BiIter>                                                      // Removed in C++20251    bool252    operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);253 254template <class BiIter>                                                      // Removed in C++20255    bool256    operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);257 258template <class BiIter>                                                      // Removed in C++20259    bool260    operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);261 262template <class BiIter>                                                      // Removed in C++20263    bool264    operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);265 266template <class BiIter, class ST, class SA>                                  // Removed in C++20267    bool268    operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,269               const sub_match<BiIter>& rhs);270 271template <class BiIter, class ST, class SA>                                  // Removed in C++20272    bool273    operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,274               const sub_match<BiIter>& rhs);275 276template <class BiIter, class ST, class SA>                                  // Removed in C++20277    bool278    operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,279              const sub_match<BiIter>& rhs);280 281template <class BiIter, class ST, class SA>                                  // Removed in C++20282    bool283    operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,284              const sub_match<BiIter>& rhs);285 286template <class BiIter, class ST, class SA>                                  // Removed in C++20287    bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,288                    const sub_match<BiIter>& rhs);289 290template <class BiIter, class ST, class SA>                                  // Removed in C++20291    bool292    operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,293               const sub_match<BiIter>& rhs);294 295template <class BiIter, class ST, class SA>296    bool297    operator==(const sub_match<BiIter>& lhs,298               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);299 300template <class BiIter, class ST, class SA>                                  // Since C++20301    auto302    operator<=>(const sub_match<BiIter>& lhs,303                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);304 305template <class BiIter, class ST, class SA>                                  // Removed in C++20306    bool307    operator!=(const sub_match<BiIter>& lhs,308               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);309 310template <class BiIter, class ST, class SA>                                  // Removed in C++20311    bool312    operator<(const sub_match<BiIter>& lhs,313              const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);314 315template <class BiIter, class ST, class SA>                                  // Removed in C++20316    bool317    operator>(const sub_match<BiIter>& lhs,318                   const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);319 320template <class BiIter, class ST, class SA>                                  // Removed in C++20321    bool322    operator>=(const sub_match<BiIter>& lhs,323               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);324 325template <class BiIter, class ST, class SA>                                  // Removed in C++20326    bool327    operator<=(const sub_match<BiIter>& lhs,328               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);329 330template <class BiIter>                                                      // Removed in C++20331    bool332    operator==(typename iterator_traits<BiIter>::value_type const* lhs,333               const sub_match<BiIter>& rhs);334 335template <class BiIter>                                                      // Removed in C++20336    bool337    operator!=(typename iterator_traits<BiIter>::value_type const* lhs,338               const sub_match<BiIter>& rhs);339 340template <class BiIter>                                                      // Removed in C++20341    bool342    operator<(typename iterator_traits<BiIter>::value_type const* lhs,343              const sub_match<BiIter>& rhs);344 345template <class BiIter>                                                      // Removed in C++20346    bool347    operator>(typename iterator_traits<BiIter>::value_type const* lhs,348              const sub_match<BiIter>& rhs);349 350template <class BiIter>                                                      // Removed in C++20351    bool352    operator>=(typename iterator_traits<BiIter>::value_type const* lhs,353               const sub_match<BiIter>& rhs);354 355template <class BiIter>                                                      // Removed in C++20356    bool357    operator<=(typename iterator_traits<BiIter>::value_type const* lhs,358               const sub_match<BiIter>& rhs);359 360template <class BiIter>361    bool362    operator==(const sub_match<BiIter>& lhs,363               typename iterator_traits<BiIter>::value_type const* rhs);364 365template <class BiIter>                                                      // Since C++20366    auto367    operator<=>(const sub_match<BiIter>& lhs,368                typename iterator_traits<BiIter>::value_type const* rhs);369 370template <class BiIter, class ST, class SA>                                  // Removed in C++20371    bool372    operator!=(const sub_match<BiIter>& lhs,373               typename iterator_traits<BiIter>::value_type const* rhs);374 375template <class BiIter>                                                      // Removed in C++20376    bool377    operator<(const sub_match<BiIter>& lhs,378              typename iterator_traits<BiIter>::value_type const* rhs);379 380template <class BiIter>                                                      // Removed in C++20381    bool382    operator>(const sub_match<BiIter>& lhs,383              typename iterator_traits<BiIter>::value_type const* rhs);384 385template <class BiIter>                                                      // Removed in C++20386    bool387    operator>=(const sub_match<BiIter>& lhs,388               typename iterator_traits<BiIter>::value_type const* rhs);389 390template <class BiIter>                                                      // Removed in C++20391    bool392    operator<=(const sub_match<BiIter>& lhs,393               typename iterator_traits<BiIter>::value_type const* rhs);394 395template <class BiIter>                                                      // Removed in C++20396    bool397    operator==(typename iterator_traits<BiIter>::value_type const& lhs,398               const sub_match<BiIter>& rhs);399 400template <class BiIter>                                                      // Removed in C++20401    bool402    operator!=(typename iterator_traits<BiIter>::value_type const& lhs,403               const sub_match<BiIter>& rhs);404 405template <class BiIter>                                                      // Removed in C++20406    bool407    operator<(typename iterator_traits<BiIter>::value_type const& lhs,408              const sub_match<BiIter>& rhs);409 410template <class BiIter>                                                      // Removed in C++20411    bool412    operator>(typename iterator_traits<BiIter>::value_type const& lhs,413              const sub_match<BiIter>& rhs);414 415template <class BiIter>                                                      // Removed in C++20416    bool417    operator>=(typename iterator_traits<BiIter>::value_type const& lhs,418               const sub_match<BiIter>& rhs);419 420template <class BiIter>                                                      // Removed in C++20421    bool422    operator<=(typename iterator_traits<BiIter>::value_type const& lhs,423               const sub_match<BiIter>& rhs);424 425template <class BiIter>426    bool427    operator==(const sub_match<BiIter>& lhs,428               typename iterator_traits<BiIter>::value_type const& rhs);429 430template <class BiIter>                                                      // Since C++20431    auto432    operator<=>(const sub_match<BiIter>& lhs,433                typename iterator_traits<BiIter>::value_type const& rhs);434 435template <class BiIter>                                                      // Removed in C++20436    bool437    operator!=(const sub_match<BiIter>& lhs,438               typename iterator_traits<BiIter>::value_type const& rhs);439 440template <class BiIter>                                                      // Removed in C++20441    bool442    operator<(const sub_match<BiIter>& lhs,443              typename iterator_traits<BiIter>::value_type const& rhs);444 445template <class BiIter>                                                      // Removed in C++20446    bool447    operator>(const sub_match<BiIter>& lhs,448              typename iterator_traits<BiIter>::value_type const& rhs);449 450template <class BiIter>                                                      // Removed in C++20451    bool452    operator>=(const sub_match<BiIter>& lhs,453               typename iterator_traits<BiIter>::value_type const& rhs);454 455template <class BiIter>                                                      // Removed in C++20456    bool457    operator<=(const sub_match<BiIter>& lhs,458               typename iterator_traits<BiIter>::value_type const& rhs);459 460template <class charT, class ST, class BiIter>461    basic_ostream<charT, ST>&462    operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);463 464template <class BidirectionalIterator,465          class Allocator = allocator<sub_match<BidirectionalIterator>>>466class match_results467{468public:469    typedef sub_match<BidirectionalIterator>                  value_type;470    typedef const value_type&                                 const_reference;471    typedef value_type&                                       reference;472    typedef /implementation-defined/                          const_iterator;473    typedef const_iterator                                    iterator;474    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;475    typedef typename allocator_traits<Allocator>::size_type   size_type;476    typedef Allocator                                         allocator_type;477    typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;478    typedef basic_string<char_type>                           string_type;479 480    // construct/copy/destroy:481    explicit match_results(const Allocator& a = Allocator()); // before C++20482    match_results() : match_results(Allocator()) {}           // C++20483    explicit match_results(const Allocator& a);               // C++20484    match_results(const match_results& m);485    match_results(match_results&& m) noexcept;486    match_results& operator=(const match_results& m);487    match_results& operator=(match_results&& m);488    ~match_results();489 490    bool ready() const;491 492    // size:493    size_type size() const;494    size_type max_size() const;495    bool empty() const;496 497    // element access:498    difference_type length(size_type sub = 0) const;499    difference_type position(size_type sub = 0) const;500    string_type str(size_type sub = 0) const;501    const_reference operator[](size_type n) const;502 503    const_reference prefix() const;504    const_reference suffix() const;505 506    const_iterator begin() const;507    const_iterator end() const;508    const_iterator cbegin() const;509    const_iterator cend() const;510 511    // format:512    template <class OutputIter>513        OutputIter514        format(OutputIter out, const char_type* fmt_first,515               const char_type* fmt_last,516               regex_constants::match_flag_type flags = regex_constants::format_default) const;517    template <class OutputIter, class ST, class SA>518        OutputIter519        format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,520               regex_constants::match_flag_type flags = regex_constants::format_default) const;521    template <class ST, class SA>522        basic_string<char_type, ST, SA>523        format(const basic_string<char_type, ST, SA>& fmt,524               regex_constants::match_flag_type flags = regex_constants::format_default) const;525    string_type526        format(const char_type* fmt,527               regex_constants::match_flag_type flags = regex_constants::format_default) const;528 529    // allocator:530    allocator_type get_allocator() const;531 532    // swap:533    void swap(match_results& that);534};535 536typedef match_results<const char*>             cmatch;537typedef match_results<const wchar_t*>          wcmatch;538typedef match_results<string::const_iterator>  smatch;539typedef match_results<wstring::const_iterator> wsmatch;540 541template <class BidirectionalIterator, class Allocator>542    bool543    operator==(const match_results<BidirectionalIterator, Allocator>& m1,544               const match_results<BidirectionalIterator, Allocator>& m2);545 546template <class BidirectionalIterator, class Allocator>                    // Removed in C++20547    bool548    operator!=(const match_results<BidirectionalIterator, Allocator>& m1,549               const match_results<BidirectionalIterator, Allocator>& m2);550 551template <class BidirectionalIterator, class Allocator>552    void553    swap(match_results<BidirectionalIterator, Allocator>& m1,554         match_results<BidirectionalIterator, Allocator>& m2);555 556template <class BidirectionalIterator, class Allocator, class charT, class traits>557    bool558    regex_match(BidirectionalIterator first, BidirectionalIterator last,559                match_results<BidirectionalIterator, Allocator>& m,560                const basic_regex<charT, traits>& e,561                regex_constants::match_flag_type flags = regex_constants::match_default);562 563template <class BidirectionalIterator, class charT, class traits>564    bool565    regex_match(BidirectionalIterator first, BidirectionalIterator last,566                const basic_regex<charT, traits>& e,567                regex_constants::match_flag_type flags = regex_constants::match_default);568 569template <class charT, class Allocator, class traits>570    bool571    regex_match(const charT* str, match_results<const charT*, Allocator>& m,572                const basic_regex<charT, traits>& e,573                regex_constants::match_flag_type flags = regex_constants::match_default);574 575template <class ST, class SA, class Allocator, class charT, class traits>576    bool577    regex_match(const basic_string<charT, ST, SA>& s,578                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,579                const basic_regex<charT, traits>& e,580                regex_constants::match_flag_type flags = regex_constants::match_default);581 582template <class ST, class SA, class Allocator, class charT, class traits>583    bool584    regex_match(const basic_string<charT, ST, SA>&& s,585                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,586                const basic_regex<charT, traits>& e,587                regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14588 589template <class charT, class traits>590    bool591    regex_match(const charT* str, const basic_regex<charT, traits>& e,592                regex_constants::match_flag_type flags = regex_constants::match_default);593 594template <class ST, class SA, class charT, class traits>595    bool596    regex_match(const basic_string<charT, ST, SA>& s,597                const basic_regex<charT, traits>& e,598                regex_constants::match_flag_type flags = regex_constants::match_default);599 600template <class BidirectionalIterator, class Allocator, class charT, class traits>601    bool602    regex_search(BidirectionalIterator first, BidirectionalIterator last,603                 match_results<BidirectionalIterator, Allocator>& m,604                 const basic_regex<charT, traits>& e,605                 regex_constants::match_flag_type flags = regex_constants::match_default);606 607template <class BidirectionalIterator, class charT, class traits>608    bool609    regex_search(BidirectionalIterator first, BidirectionalIterator last,610                 const basic_regex<charT, traits>& e,611                 regex_constants::match_flag_type flags = regex_constants::match_default);612 613template <class charT, class Allocator, class traits>614    bool615    regex_search(const charT* str, match_results<const charT*, Allocator>& m,616                 const basic_regex<charT, traits>& e,617                 regex_constants::match_flag_type flags = regex_constants::match_default);618 619template <class charT, class traits>620    bool621    regex_search(const charT* str, const basic_regex<charT, traits>& e,622                 regex_constants::match_flag_type flags = regex_constants::match_default);623 624template <class ST, class SA, class charT, class traits>625    bool626    regex_search(const basic_string<charT, ST, SA>& s,627                 const basic_regex<charT, traits>& e,628                 regex_constants::match_flag_type flags = regex_constants::match_default);629 630template <class ST, class SA, class Allocator, class charT, class traits>631    bool632    regex_search(const basic_string<charT, ST, SA>& s,633                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,634                 const basic_regex<charT, traits>& e,635                 regex_constants::match_flag_type flags = regex_constants::match_default);636 637template <class ST, class SA, class Allocator, class charT, class traits>638    bool639    regex_search(const basic_string<charT, ST, SA>&& s,640                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,641                 const basic_regex<charT, traits>& e,642                 regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14643 644template <class OutputIterator, class BidirectionalIterator,645          class traits, class charT, class ST, class SA>646    OutputIterator647    regex_replace(OutputIterator out,648                  BidirectionalIterator first, BidirectionalIterator last,649                  const basic_regex<charT, traits>& e,650                  const basic_string<charT, ST, SA>& fmt,651                  regex_constants::match_flag_type flags = regex_constants::match_default);652 653template <class OutputIterator, class BidirectionalIterator,654          class traits, class charT>655    OutputIterator656    regex_replace(OutputIterator out,657                  BidirectionalIterator first, BidirectionalIterator last,658                  const basic_regex<charT, traits>& e, const charT* fmt,659                  regex_constants::match_flag_type flags = regex_constants::match_default);660 661template <class traits, class charT, class ST, class SA, class FST, class FSA>662    basic_string<charT, ST, SA>663    regex_replace(const basic_string<charT, ST, SA>& s,664                  const basic_regex<charT, traits>& e,665                  const basic_string<charT, FST, FSA>& fmt,666                  regex_constants::match_flag_type flags = regex_constants::match_default);667 668template <class traits, class charT, class ST, class SA>669    basic_string<charT, ST, SA>670    regex_replace(const basic_string<charT, ST, SA>& s,671                  const basic_regex<charT, traits>& e, const charT* fmt,672                  regex_constants::match_flag_type flags = regex_constants::match_default);673 674template <class traits, class charT, class ST, class SA>675    basic_string<charT>676    regex_replace(const charT* s,677                  const basic_regex<charT, traits>& e,678                  const basic_string<charT, ST, SA>& fmt,679                  regex_constants::match_flag_type flags = regex_constants::match_default);680 681template <class traits, class charT>682    basic_string<charT>683    regex_replace(const charT* s,684                  const basic_regex<charT, traits>& e,685                  const charT* fmt,686                  regex_constants::match_flag_type flags = regex_constants::match_default);687 688template <class BidirectionalIterator,689          class charT = typename iterator_traits< BidirectionalIterator>::value_type,690          class traits = regex_traits<charT>>691class regex_iterator692{693public:694    typedef basic_regex<charT, traits>           regex_type;695    typedef match_results<BidirectionalIterator> value_type;696    typedef ptrdiff_t                            difference_type;697    typedef const value_type*                    pointer;698    typedef const value_type&                    reference;699    typedef forward_iterator_tag                 iterator_category;700    typedef input_iterator_tag                   iterator_concept; // since C++20701 702    regex_iterator();703    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,704                   const regex_type& re,705                   regex_constants::match_flag_type m = regex_constants::match_default);706    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,707                   const regex_type&& re,708                   regex_constants::match_flag_type m709                                     = regex_constants::match_default) = delete; // C++14710    regex_iterator(const regex_iterator&);711    regex_iterator& operator=(const regex_iterator&);712 713    bool operator==(const regex_iterator&) const;714    bool operator==(default_sentinel_t) const { return *this == regex_iterator(); } // since C++20715    bool operator!=(const regex_iterator&) const;                                   // Removed in C++20716 717    const value_type& operator*() const;718    const value_type* operator->() const;719 720    regex_iterator& operator++();721    regex_iterator operator++(int);722};723 724typedef regex_iterator<const char*>             cregex_iterator;725typedef regex_iterator<const wchar_t*>          wcregex_iterator;726typedef regex_iterator<string::const_iterator>  sregex_iterator;727typedef regex_iterator<wstring::const_iterator> wsregex_iterator;728 729template <class BidirectionalIterator,730          class charT = typename iterator_traits<BidirectionalIterator>::value_type,731          class traits = regex_traits<charT>>732class regex_token_iterator733{734public:735    typedef basic_regex<charT, traits>       regex_type;736    typedef sub_match<BidirectionalIterator> value_type;737    typedef ptrdiff_t                        difference_type;738    typedef const value_type*                pointer;739    typedef const value_type&                reference;740    typedef forward_iterator_tag             iterator_category;741    typedef input_iterator_tag               iterator_concept; // since C++20742 743    regex_token_iterator();744    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,745                         const regex_type& re, int submatch = 0,746                         regex_constants::match_flag_type m = regex_constants::match_default);747    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,748                         const regex_type&& re, int submatch = 0,749                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14750    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,751                         const regex_type& re, const vector<int>& submatches,752                         regex_constants::match_flag_type m = regex_constants::match_default);753    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,754                         const regex_type&& re, const vector<int>& submatches,755                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14756    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,757                         const regex_type& re, initializer_list<int> submatches,758                         regex_constants::match_flag_type m = regex_constants::match_default);759    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,760                         const regex_type&& re, initializer_list<int> submatches,761                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14762    template <size_t N>763        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,764                             const regex_type& re, const int (&submatches)[N],765                             regex_constants::match_flag_type m = regex_constants::match_default);766    template <size_t N>767        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,768                             const regex_type&& re, const int (&submatches)[N],769                             regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14770    regex_token_iterator(const regex_token_iterator&);771    regex_token_iterator& operator=(const regex_token_iterator&);772 773    bool operator==(const regex_token_iterator&) const;774    bool operator==(default_sentinel_t) const { return *this == regex_token_iterator(); } // since C++20775    bool operator!=(const regex_token_iterator&) const;                                   // Removed in C++20776 777    const value_type& operator*() const;778    const value_type* operator->() const;779 780    regex_token_iterator& operator++();781    regex_token_iterator operator++(int);782};783 784typedef regex_token_iterator<const char*>             cregex_token_iterator;785typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;786typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;787typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;788 789} // std790*/791 792#include <__cxx03/__algorithm/find.h>793#include <__cxx03/__algorithm/search.h>794#include <__cxx03/__assert>795#include <__cxx03/__config>796#include <__cxx03/__iterator/back_insert_iterator.h>797#include <__cxx03/__iterator/wrap_iter.h>798#include <__cxx03/__locale>799#include <__cxx03/__memory/shared_ptr.h>800#include <__cxx03/__type_traits/is_swappable.h>801#include <__cxx03/__utility/move.h>802#include <__cxx03/__utility/pair.h>803#include <__cxx03/__utility/swap.h>804#include <__cxx03/__verbose_abort>805#include <__cxx03/deque>806#include <__cxx03/stdexcept>807#include <__cxx03/string>808#include <__cxx03/vector>809#include <__cxx03/version>810 811// standard-mandated includes812 813// [iterator.range]814#include <__cxx03/__iterator/access.h>815 816#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)817#  pragma GCC system_header818#endif819 820_LIBCPP_PUSH_MACROS821#include <__cxx03/__undef_macros>822 823#define _LIBCPP_REGEX_COMPLEXITY_FACTOR 4096824 825_LIBCPP_BEGIN_NAMESPACE_STD826 827namespace regex_constants {828 829// syntax_option_type830 831enum syntax_option_type {832  icase    = 1 << 0,833  nosubs   = 1 << 1,834  optimize = 1 << 2,835  collate  = 1 << 3,836#ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO837  ECMAScript = 1 << 9,838#else839  ECMAScript = 0,840#endif841  basic    = 1 << 4,842  extended = 1 << 5,843  awk      = 1 << 6,844  grep     = 1 << 7,845  egrep    = 1 << 8,846  // 1 << 9 may be used by ECMAScript847  multiline = 1 << 10848};849 850_LIBCPP_HIDE_FROM_ABI inline syntax_option_type __get_grammar(syntax_option_type __g) {851#ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO852  return static_cast<syntax_option_type>(__g & 0x3F0);853#else854  return static_cast<syntax_option_type>(__g & 0x1F0);855#endif856}857 858inline _LIBCPP_HIDE_FROM_ABI syntax_option_type operator~(syntax_option_type __x) {859  return syntax_option_type(~int(__x) & 0x1FF);860}861 862inline _LIBCPP_HIDE_FROM_ABI syntax_option_type operator&(syntax_option_type __x, syntax_option_type __y) {863  return syntax_option_type(int(__x) & int(__y));864}865 866inline _LIBCPP_HIDE_FROM_ABI syntax_option_type operator|(syntax_option_type __x, syntax_option_type __y) {867  return syntax_option_type(int(__x) | int(__y));868}869 870inline _LIBCPP_HIDE_FROM_ABI syntax_option_type operator^(syntax_option_type __x, syntax_option_type __y) {871  return syntax_option_type(int(__x) ^ int(__y));872}873 874inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator&=(syntax_option_type& __x, syntax_option_type __y) {875  __x = __x & __y;876  return __x;877}878 879inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator|=(syntax_option_type& __x, syntax_option_type __y) {880  __x = __x | __y;881  return __x;882}883 884inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator^=(syntax_option_type& __x, syntax_option_type __y) {885  __x = __x ^ __y;886  return __x;887}888 889// match_flag_type890 891enum match_flag_type {892  match_default     = 0,893  match_not_bol     = 1 << 0,894  match_not_eol     = 1 << 1,895  match_not_bow     = 1 << 2,896  match_not_eow     = 1 << 3,897  match_any         = 1 << 4,898  match_not_null    = 1 << 5,899  match_continuous  = 1 << 6,900  match_prev_avail  = 1 << 7,901  format_default    = 0,902  format_sed        = 1 << 8,903  format_no_copy    = 1 << 9,904  format_first_only = 1 << 10,905  __no_update_pos   = 1 << 11,906  __full_match      = 1 << 12907};908 909inline _LIBCPP_HIDE_FROM_ABI match_flag_type operator~(match_flag_type __x) {910  return match_flag_type(~int(__x) & 0x0FFF);911}912 913inline _LIBCPP_HIDE_FROM_ABI match_flag_type operator&(match_flag_type __x, match_flag_type __y) {914  return match_flag_type(int(__x) & int(__y));915}916 917inline _LIBCPP_HIDE_FROM_ABI match_flag_type operator|(match_flag_type __x, match_flag_type __y) {918  return match_flag_type(int(__x) | int(__y));919}920 921inline _LIBCPP_HIDE_FROM_ABI match_flag_type operator^(match_flag_type __x, match_flag_type __y) {922  return match_flag_type(int(__x) ^ int(__y));923}924 925inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator&=(match_flag_type& __x, match_flag_type __y) {926  __x = __x & __y;927  return __x;928}929 930inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator|=(match_flag_type& __x, match_flag_type __y) {931  __x = __x | __y;932  return __x;933}934 935inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator^=(match_flag_type& __x, match_flag_type __y) {936  __x = __x ^ __y;937  return __x;938}939 940enum error_type {941  error_collate = 1,942  error_ctype,943  error_escape,944  error_backref,945  error_brack,946  error_paren,947  error_brace,948  error_badbrace,949  error_range,950  error_space,951  error_badrepeat,952  error_complexity,953  error_stack,954  __re_err_grammar,955  __re_err_empty,956  __re_err_unknown,957  __re_err_parse958};959 960} // namespace regex_constants961 962class _LIBCPP_EXPORTED_FROM_ABI regex_error : public runtime_error {963  regex_constants::error_type __code_;964 965public:966  explicit regex_error(regex_constants::error_type __ecode);967  _LIBCPP_HIDE_FROM_ABI regex_error(const regex_error&) _NOEXCEPT = default;968  ~regex_error() _NOEXCEPT override;969  _LIBCPP_HIDE_FROM_ABI regex_constants::error_type code() const { return __code_; }970};971 972template <regex_constants::error_type _Ev>973_LIBCPP_NORETURN inline _LIBCPP_HIDE_FROM_ABI void __throw_regex_error() {974#ifndef _LIBCPP_HAS_NO_EXCEPTIONS975  throw regex_error(_Ev);976#else977  _LIBCPP_VERBOSE_ABORT("regex_error was thrown in -fno-exceptions mode");978#endif979}980 981template <class _CharT>982struct _LIBCPP_TEMPLATE_VIS regex_traits {983public:984  typedef _CharT char_type;985  typedef basic_string<char_type> string_type;986  typedef locale locale_type;987#if defined(__BIONIC__) || _LIBCPP_LIBC_NEWLIB988  // Originally bionic's ctype_base used its own ctype masks because the989  // builtin ctype implementation wasn't in libc++ yet. Bionic's ctype mask990  // was only 8 bits wide and already saturated, so it used a wider type here991  // to make room for __regex_word (then a part of this class rather than992  // ctype_base). Bionic has since moved to the builtin ctype_base993  // implementation, but this was not updated to match. Since then Android has994  // needed to maintain a stable libc++ ABI, and this can't be changed without995  // an ABI break.996  // We also need this workaround for newlib since newlib is997  // often used for space constrained environments, so it makes sense not to998  // duplicate the ctype table.999  typedef uint16_t char_class_type;1000#else1001  typedef ctype_base::mask char_class_type;1002#endif1003 1004  static const char_class_type __regex_word = ctype_base::__regex_word;1005 1006private:1007  locale __loc_;1008  const ctype<char_type>* __ct_;1009  const collate<char_type>* __col_;1010 1011public:1012  regex_traits();1013 1014  _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __p) { return char_traits<char_type>::length(__p); }1015  _LIBCPP_HIDE_FROM_ABI char_type translate(char_type __c) const { return __c; }1016  char_type translate_nocase(char_type __c) const;1017  template <class _ForwardIterator>1018  string_type transform(_ForwardIterator __f, _ForwardIterator __l) const;1019  template <class _ForwardIterator>1020  _LIBCPP_HIDE_FROM_ABI string_type transform_primary(_ForwardIterator __f, _ForwardIterator __l) const {1021    return __transform_primary(__f, __l, char_type());1022  }1023  template <class _ForwardIterator>1024  _LIBCPP_HIDE_FROM_ABI string_type lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const {1025    return __lookup_collatename(__f, __l, char_type());1026  }1027  template <class _ForwardIterator>1028  _LIBCPP_HIDE_FROM_ABI char_class_type1029  lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase = false) const {1030    return __lookup_classname(__f, __l, __icase, char_type());1031  }1032  bool isctype(char_type __c, char_class_type __m) const;1033  _LIBCPP_HIDE_FROM_ABI int value(char_type __ch, int __radix) const { return __regex_traits_value(__ch, __radix); }1034  locale_type imbue(locale_type __l);1035  _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __loc_; }1036 1037private:1038  void __init();1039 1040  template <class _ForwardIterator>1041  string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;1042#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1043  template <class _ForwardIterator>1044  string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;1045#endif1046  template <class _ForwardIterator>1047  string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;1048#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1049  template <class _ForwardIterator>1050  string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;1051#endif1052  template <class _ForwardIterator>1053  char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, char) const;1054#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1055  template <class _ForwardIterator>1056  char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, wchar_t) const;1057#endif1058 1059  static int __regex_traits_value(unsigned char __ch, int __radix);1060  _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(char __ch, int __radix) const {1061    return __regex_traits_value(static_cast<unsigned char>(__ch), __radix);1062  }1063#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1064  _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(wchar_t __ch, int __radix) const;1065#endif1066};1067 1068template <class _CharT>1069const typename regex_traits<_CharT>::char_class_type regex_traits<_CharT>::__regex_word;1070 1071template <class _CharT>1072regex_traits<_CharT>::regex_traits() {1073  __init();1074}1075 1076template <class _CharT>1077typename regex_traits<_CharT>::char_type regex_traits<_CharT>::translate_nocase(char_type __c) const {1078  return __ct_->tolower(__c);1079}1080 1081template <class _CharT>1082template <class _ForwardIterator>1083typename regex_traits<_CharT>::string_type1084regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const {1085  string_type __s(__f, __l);1086  return __col_->transform(__s.data(), __s.data() + __s.size());1087}1088 1089template <class _CharT>1090void regex_traits<_CharT>::__init() {1091  __ct_  = &std::use_facet<ctype<char_type> >(__loc_);1092  __col_ = &std::use_facet<collate<char_type> >(__loc_);1093}1094 1095template <class _CharT>1096typename regex_traits<_CharT>::locale_type regex_traits<_CharT>::imbue(locale_type __l) {1097  locale __r = __loc_;1098  __loc_     = __l;1099  __init();1100  return __r;1101}1102 1103// transform_primary is very FreeBSD-specific1104 1105template <class _CharT>1106template <class _ForwardIterator>1107typename regex_traits<_CharT>::string_type1108regex_traits<_CharT>::__transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const {1109  const string_type __s(__f, __l);1110  string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());1111  switch (__d.size()) {1112  case 1:1113    break;1114  case 12:1115    __d[11] = __d[3];1116    break;1117  default:1118    __d.clear();1119    break;1120  }1121  return __d;1122}1123 1124#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1125template <class _CharT>1126template <class _ForwardIterator>1127typename regex_traits<_CharT>::string_type1128regex_traits<_CharT>::__transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const {1129  const string_type __s(__f, __l);1130  string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());1131  switch (__d.size()) {1132  case 1:1133    break;1134  case 3:1135    __d[2] = __d[0];1136    break;1137  default:1138    __d.clear();1139    break;1140  }1141  return __d;1142}1143#endif1144 1145// lookup_collatename is very FreeBSD-specific1146 1147_LIBCPP_EXPORTED_FROM_ABI string __get_collation_name(const char* __s);1148 1149template <class _CharT>1150template <class _ForwardIterator>1151typename regex_traits<_CharT>::string_type1152regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const {1153  string_type __s(__f, __l);1154  string_type __r;1155  if (!__s.empty()) {1156    __r = std::__get_collation_name(__s.c_str());1157    if (__r.empty() && __s.size() <= 2) {1158      __r = __col_->transform(__s.data(), __s.data() + __s.size());1159      if (__r.size() == 1 || __r.size() == 12)1160        __r = __s;1161      else1162        __r.clear();1163    }1164  }1165  return __r;1166}1167 1168#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1169template <class _CharT>1170template <class _ForwardIterator>1171typename regex_traits<_CharT>::string_type1172regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const {1173  string_type __s(__f, __l);1174  string __n;1175  __n.reserve(__s.size());1176  for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end(); __i != __e; ++__i) {1177    if (static_cast<unsigned>(*__i) >= 127)1178      return string_type();1179    __n.push_back(char(*__i));1180  }1181  string_type __r;1182  if (!__s.empty()) {1183    __n = __get_collation_name(__n.c_str());1184    if (!__n.empty())1185      __r.assign(__n.begin(), __n.end());1186    else if (__s.size() <= 2) {1187      __r = __col_->transform(__s.data(), __s.data() + __s.size());1188      if (__r.size() == 1 || __r.size() == 3)1189        __r = __s;1190      else1191        __r.clear();1192    }1193  }1194  return __r;1195}1196#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS1197 1198// lookup_classname1199 1200regex_traits<char>::char_class_type _LIBCPP_EXPORTED_FROM_ABI __get_classname(const char* __s, bool __icase);1201 1202template <class _CharT>1203template <class _ForwardIterator>1204typename regex_traits<_CharT>::char_class_type1205regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, char) const {1206  string_type __s(__f, __l);1207  __ct_->tolower(&__s[0], &__s[0] + __s.size());1208  return std::__get_classname(__s.c_str(), __icase);1209}1210 1211#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1212template <class _CharT>1213template <class _ForwardIterator>1214typename regex_traits<_CharT>::char_class_type1215regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, wchar_t) const {1216  string_type __s(__f, __l);1217  __ct_->tolower(&__s[0], &__s[0] + __s.size());1218  string __n;1219  __n.reserve(__s.size());1220  for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end(); __i != __e; ++__i) {1221    if (static_cast<unsigned>(*__i) >= 127)1222      return char_class_type();1223    __n.push_back(char(*__i));1224  }1225  return __get_classname(__n.c_str(), __icase);1226}1227#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS1228 1229template <class _CharT>1230bool regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const {1231  if (__ct_->is(__m, __c))1232    return true;1233  return (__c == '_' && (__m & __regex_word));1234}1235 1236inline _LIBCPP_HIDE_FROM_ABI bool __is_07(unsigned char __c) {1237  return (__c & 0xF8u) ==1238#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)1239         0xF0;1240#else1241         0x30;1242#endif1243}1244 1245inline _LIBCPP_HIDE_FROM_ABI bool __is_89(unsigned char __c) {1246  return (__c & 0xFEu) ==1247#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)1248         0xF8;1249#else1250         0x38;1251#endif1252}1253 1254inline _LIBCPP_HIDE_FROM_ABI unsigned char __to_lower(unsigned char __c) {1255#if defined(__MVS__) && !defined(__NATIVE_ASCII_F)1256  return __c & 0xBF;1257#else1258  return __c | 0x20;1259#endif1260}1261 1262template <class _CharT>1263int regex_traits<_CharT>::__regex_traits_value(unsigned char __ch, int __radix) {1264  if (__is_07(__ch)) // '0' <= __ch && __ch <= '7'1265    return __ch - '0';1266  if (__radix != 8) {1267    if (__is_89(__ch)) // '8' <= __ch && __ch <= '9'1268      return __ch - '0';1269    if (__radix == 16) {1270      __ch = __to_lower(__ch); // tolower1271      if ('a' <= __ch && __ch <= 'f')1272        return __ch - ('a' - 10);1273    }1274  }1275  return -1;1276}1277 1278#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1279template <class _CharT>1280inline int regex_traits<_CharT>::__regex_traits_value(wchar_t __ch, int __radix) const {1281  return __regex_traits_value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);1282}1283#endif1284 1285template <class _CharT>1286class __node;1287 1288template <class _BidirectionalIterator>1289class _LIBCPP_TEMPLATE_VIS sub_match;1290 1291template <class _BidirectionalIterator, class _Allocator = allocator<sub_match<_BidirectionalIterator> > >1292class _LIBCPP_TEMPLATE_VIS match_results;1293 1294template <class _CharT>1295struct __state {1296  enum {1297    __end_state = -1000,1298    __consume_input,          // -9991299    __begin_marked_expr,      // -9981300    __end_marked_expr,        // -9971301    __pop_state,              // -9961302    __accept_and_consume,     // -9951303    __accept_but_not_consume, // -9941304    __reject,                 // -9931305    __split,1306    __repeat1307  };1308 1309  int __do_;1310  const _CharT* __first_;1311  const _CharT* __current_;1312  const _CharT* __last_;1313  vector<sub_match<const _CharT*> > __sub_matches_;1314  vector<pair<size_t, const _CharT*> > __loop_data_;1315  const __node<_CharT>* __node_;1316  regex_constants::match_flag_type __flags_;1317  bool __at_first_;1318 1319  _LIBCPP_HIDE_FROM_ABI __state()1320      : __do_(0),1321        __first_(nullptr),1322        __current_(nullptr),1323        __last_(nullptr),1324        __node_(nullptr),1325        __flags_(),1326        __at_first_(false) {}1327};1328 1329// __node1330 1331template <class _CharT>1332class __node {1333public:1334  typedef std::__state<_CharT> __state;1335 1336  _LIBCPP_HIDE_FROM_ABI __node() {}1337  __node(const __node&)            = delete;1338  __node& operator=(const __node&) = delete;1339  _LIBCPP_HIDE_FROM_ABI_VIRTUAL1340  virtual ~__node() {}1341 1342  _LIBCPP_HIDE_FROM_ABI_VIRTUAL1343  virtual void __exec(__state&) const {}1344  _LIBCPP_HIDE_FROM_ABI_VIRTUAL1345  virtual void __exec_split(bool, __state&) const {}1346};1347 1348// __end_state1349 1350template <class _CharT>1351class __end_state : public __node<_CharT> {1352public:1353  typedef std::__state<_CharT> __state;1354 1355  _LIBCPP_HIDE_FROM_ABI __end_state() {}1356 1357  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1358};1359 1360template <class _CharT>1361void __end_state<_CharT>::__exec(__state& __s) const {1362  __s.__do_ = __state::__end_state;1363}1364 1365// __has_one_state1366 1367template <class _CharT>1368class __has_one_state : public __node<_CharT> {1369  __node<_CharT>* __first_;1370 1371public:1372  _LIBCPP_HIDE_FROM_ABI explicit __has_one_state(__node<_CharT>* __s) : __first_(__s) {}1373 1374  _LIBCPP_HIDE_FROM_ABI __node<_CharT>* first() const { return __first_; }1375  _LIBCPP_HIDE_FROM_ABI __node<_CharT>*& first() { return __first_; }1376};1377 1378// __owns_one_state1379 1380template <class _CharT>1381class __owns_one_state : public __has_one_state<_CharT> {1382  typedef __has_one_state<_CharT> base;1383 1384public:1385  _LIBCPP_HIDE_FROM_ABI explicit __owns_one_state(__node<_CharT>* __s) : base(__s) {}1386 1387  ~__owns_one_state() override;1388};1389 1390template <class _CharT>1391__owns_one_state<_CharT>::~__owns_one_state() {1392  delete this->first();1393}1394 1395// __empty_state1396 1397template <class _CharT>1398class __empty_state : public __owns_one_state<_CharT> {1399  typedef __owns_one_state<_CharT> base;1400 1401public:1402  typedef std::__state<_CharT> __state;1403 1404  _LIBCPP_HIDE_FROM_ABI explicit __empty_state(__node<_CharT>* __s) : base(__s) {}1405 1406  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1407};1408 1409template <class _CharT>1410void __empty_state<_CharT>::__exec(__state& __s) const {1411  __s.__do_   = __state::__accept_but_not_consume;1412  __s.__node_ = this->first();1413}1414 1415// __empty_non_own_state1416 1417template <class _CharT>1418class __empty_non_own_state : public __has_one_state<_CharT> {1419  typedef __has_one_state<_CharT> base;1420 1421public:1422  typedef std::__state<_CharT> __state;1423 1424  _LIBCPP_HIDE_FROM_ABI explicit __empty_non_own_state(__node<_CharT>* __s) : base(__s) {}1425 1426  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1427};1428 1429template <class _CharT>1430void __empty_non_own_state<_CharT>::__exec(__state& __s) const {1431  __s.__do_   = __state::__accept_but_not_consume;1432  __s.__node_ = this->first();1433}1434 1435// __repeat_one_loop1436 1437template <class _CharT>1438class __repeat_one_loop : public __has_one_state<_CharT> {1439  typedef __has_one_state<_CharT> base;1440 1441public:1442  typedef std::__state<_CharT> __state;1443 1444  _LIBCPP_HIDE_FROM_ABI explicit __repeat_one_loop(__node<_CharT>* __s) : base(__s) {}1445 1446  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1447};1448 1449template <class _CharT>1450void __repeat_one_loop<_CharT>::__exec(__state& __s) const {1451  __s.__do_   = __state::__repeat;1452  __s.__node_ = this->first();1453}1454 1455// __owns_two_states1456 1457template <class _CharT>1458class __owns_two_states : public __owns_one_state<_CharT> {1459  typedef __owns_one_state<_CharT> base;1460 1461  base* __second_;1462 1463public:1464  _LIBCPP_HIDE_FROM_ABI explicit __owns_two_states(__node<_CharT>* __s1, base* __s2) : base(__s1), __second_(__s2) {}1465 1466  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual ~__owns_two_states();1467 1468  _LIBCPP_HIDE_FROM_ABI base* second() const { return __second_; }1469  _LIBCPP_HIDE_FROM_ABI base*& second() { return __second_; }1470};1471 1472template <class _CharT>1473__owns_two_states<_CharT>::~__owns_two_states() {1474  delete __second_;1475}1476 1477// __loop1478 1479template <class _CharT>1480class __loop : public __owns_two_states<_CharT> {1481  typedef __owns_two_states<_CharT> base;1482 1483  size_t __min_;1484  size_t __max_;1485  unsigned __loop_id_;1486  unsigned __mexp_begin_;1487  unsigned __mexp_end_;1488  bool __greedy_;1489 1490public:1491  typedef std::__state<_CharT> __state;1492 1493  _LIBCPP_HIDE_FROM_ABI explicit __loop(1494      unsigned __loop_id,1495      __node<_CharT>* __s1,1496      __owns_one_state<_CharT>* __s2,1497      unsigned __mexp_begin,1498      unsigned __mexp_end,1499      bool __greedy = true,1500      size_t __min  = 0,1501      size_t __max  = numeric_limits<size_t>::max())1502      : base(__s1, __s2),1503        __min_(__min),1504        __max_(__max),1505        __loop_id_(__loop_id),1506        __mexp_begin_(__mexp_begin),1507        __mexp_end_(__mexp_end),1508        __greedy_(__greedy) {}1509 1510  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;1511  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec_split(bool __second, __state& __s) const;1512 1513private:1514  _LIBCPP_HIDE_FROM_ABI void __init_repeat(__state& __s) const {1515    __s.__loop_data_[__loop_id_].second = __s.__current_;1516    for (size_t __i = __mexp_begin_ - 1; __i != __mexp_end_ - 1; ++__i) {1517      __s.__sub_matches_[__i].first   = __s.__last_;1518      __s.__sub_matches_[__i].second  = __s.__last_;1519      __s.__sub_matches_[__i].matched = false;1520    }1521  }1522};1523 1524template <class _CharT>1525void __loop<_CharT>::__exec(__state& __s) const {1526  if (__s.__do_ == __state::__repeat) {1527    bool __do_repeat = ++__s.__loop_data_[__loop_id_].first < __max_;1528    bool __do_alt    = __s.__loop_data_[__loop_id_].first >= __min_;1529    if (__do_repeat && __do_alt && __s.__loop_data_[__loop_id_].second == __s.__current_)1530      __do_repeat = false;1531    if (__do_repeat && __do_alt)1532      __s.__do_ = __state::__split;1533    else if (__do_repeat) {1534      __s.__do_   = __state::__accept_but_not_consume;1535      __s.__node_ = this->first();1536      __init_repeat(__s);1537    } else {1538      __s.__do_   = __state::__accept_but_not_consume;1539      __s.__node_ = this->second();1540    }1541  } else {1542    __s.__loop_data_[__loop_id_].first = 0;1543    bool __do_repeat                   = 0 < __max_;1544    bool __do_alt                      = 0 >= __min_;1545    if (__do_repeat && __do_alt)1546      __s.__do_ = __state::__split;1547    else if (__do_repeat) {1548      __s.__do_   = __state::__accept_but_not_consume;1549      __s.__node_ = this->first();1550      __init_repeat(__s);1551    } else {1552      __s.__do_   = __state::__accept_but_not_consume;1553      __s.__node_ = this->second();1554    }1555  }1556}1557 1558template <class _CharT>1559void __loop<_CharT>::__exec_split(bool __second, __state& __s) const {1560  __s.__do_ = __state::__accept_but_not_consume;1561  if (__greedy_ != __second) {1562    __s.__node_ = this->first();1563    __init_repeat(__s);1564  } else1565    __s.__node_ = this->second();1566}1567 1568// __alternate1569 1570template <class _CharT>1571class __alternate : public __owns_two_states<_CharT> {1572  typedef __owns_two_states<_CharT> base;1573 1574public:1575  typedef std::__state<_CharT> __state;1576 1577  _LIBCPP_HIDE_FROM_ABI explicit __alternate(__owns_one_state<_CharT>* __s1, __owns_one_state<_CharT>* __s2)1578      : base(__s1, __s2) {}1579 1580  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;1581  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec_split(bool __second, __state& __s) const;1582};1583 1584template <class _CharT>1585void __alternate<_CharT>::__exec(__state& __s) const {1586  __s.__do_ = __state::__split;1587}1588 1589template <class _CharT>1590void __alternate<_CharT>::__exec_split(bool __second, __state& __s) const {1591  __s.__do_ = __state::__accept_but_not_consume;1592  if (__second)1593    __s.__node_ = this->second();1594  else1595    __s.__node_ = this->first();1596}1597 1598// __begin_marked_subexpression1599 1600template <class _CharT>1601class __begin_marked_subexpression : public __owns_one_state<_CharT> {1602  typedef __owns_one_state<_CharT> base;1603 1604  unsigned __mexp_;1605 1606public:1607  typedef std::__state<_CharT> __state;1608 1609  _LIBCPP_HIDE_FROM_ABI explicit __begin_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)1610      : base(__s), __mexp_(__mexp) {}1611 1612  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1613};1614 1615template <class _CharT>1616void __begin_marked_subexpression<_CharT>::__exec(__state& __s) const {1617  __s.__do_                             = __state::__accept_but_not_consume;1618  __s.__sub_matches_[__mexp_ - 1].first = __s.__current_;1619  __s.__node_                           = this->first();1620}1621 1622// __end_marked_subexpression1623 1624template <class _CharT>1625class __end_marked_subexpression : public __owns_one_state<_CharT> {1626  typedef __owns_one_state<_CharT> base;1627 1628  unsigned __mexp_;1629 1630public:1631  typedef std::__state<_CharT> __state;1632 1633  _LIBCPP_HIDE_FROM_ABI explicit __end_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)1634      : base(__s), __mexp_(__mexp) {}1635 1636  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1637};1638 1639template <class _CharT>1640void __end_marked_subexpression<_CharT>::__exec(__state& __s) const {1641  __s.__do_                               = __state::__accept_but_not_consume;1642  __s.__sub_matches_[__mexp_ - 1].second  = __s.__current_;1643  __s.__sub_matches_[__mexp_ - 1].matched = true;1644  __s.__node_                             = this->first();1645}1646 1647// __back_ref1648 1649template <class _CharT>1650class __back_ref : public __owns_one_state<_CharT> {1651  typedef __owns_one_state<_CharT> base;1652 1653  unsigned __mexp_;1654 1655public:1656  typedef std::__state<_CharT> __state;1657 1658  _LIBCPP_HIDE_FROM_ABI explicit __back_ref(unsigned __mexp, __node<_CharT>* __s) : base(__s), __mexp_(__mexp) {}1659 1660  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1661};1662 1663template <class _CharT>1664void __back_ref<_CharT>::__exec(__state& __s) const {1665  if (__mexp_ > __s.__sub_matches_.size())1666    __throw_regex_error<regex_constants::error_backref>();1667  sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];1668  if (__sm.matched) {1669    ptrdiff_t __len = __sm.second - __sm.first;1670    if (__s.__last_ - __s.__current_ >= __len && std::equal(__sm.first, __sm.second, __s.__current_)) {1671      __s.__do_ = __state::__accept_but_not_consume;1672      __s.__current_ += __len;1673      __s.__node_ = this->first();1674    } else {1675      __s.__do_   = __state::__reject;1676      __s.__node_ = nullptr;1677    }1678  } else {1679    __s.__do_   = __state::__reject;1680    __s.__node_ = nullptr;1681  }1682}1683 1684// __back_ref_icase1685 1686template <class _CharT, class _Traits>1687class __back_ref_icase : public __owns_one_state<_CharT> {1688  typedef __owns_one_state<_CharT> base;1689 1690  _Traits __traits_;1691  unsigned __mexp_;1692 1693public:1694  typedef std::__state<_CharT> __state;1695 1696  _LIBCPP_HIDE_FROM_ABI explicit __back_ref_icase(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)1697      : base(__s), __traits_(__traits), __mexp_(__mexp) {}1698 1699  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1700};1701 1702template <class _CharT, class _Traits>1703void __back_ref_icase<_CharT, _Traits>::__exec(__state& __s) const {1704  sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];1705  if (__sm.matched) {1706    ptrdiff_t __len = __sm.second - __sm.first;1707    if (__s.__last_ - __s.__current_ >= __len) {1708      for (ptrdiff_t __i = 0; __i < __len; ++__i) {1709        if (__traits_.translate_nocase(__sm.first[__i]) != __traits_.translate_nocase(__s.__current_[__i]))1710          goto __not_equal;1711      }1712      __s.__do_ = __state::__accept_but_not_consume;1713      __s.__current_ += __len;1714      __s.__node_ = this->first();1715    } else {1716      __s.__do_   = __state::__reject;1717      __s.__node_ = nullptr;1718    }1719  } else {1720  __not_equal:1721    __s.__do_   = __state::__reject;1722    __s.__node_ = nullptr;1723  }1724}1725 1726// __back_ref_collate1727 1728template <class _CharT, class _Traits>1729class __back_ref_collate : public __owns_one_state<_CharT> {1730  typedef __owns_one_state<_CharT> base;1731 1732  _Traits __traits_;1733  unsigned __mexp_;1734 1735public:1736  typedef std::__state<_CharT> __state;1737 1738  _LIBCPP_HIDE_FROM_ABI explicit __back_ref_collate(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)1739      : base(__s), __traits_(__traits), __mexp_(__mexp) {}1740 1741  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1742};1743 1744template <class _CharT, class _Traits>1745void __back_ref_collate<_CharT, _Traits>::__exec(__state& __s) const {1746  sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];1747  if (__sm.matched) {1748    ptrdiff_t __len = __sm.second - __sm.first;1749    if (__s.__last_ - __s.__current_ >= __len) {1750      for (ptrdiff_t __i = 0; __i < __len; ++__i) {1751        if (__traits_.translate(__sm.first[__i]) != __traits_.translate(__s.__current_[__i]))1752          goto __not_equal;1753      }1754      __s.__do_ = __state::__accept_but_not_consume;1755      __s.__current_ += __len;1756      __s.__node_ = this->first();1757    } else {1758      __s.__do_   = __state::__reject;1759      __s.__node_ = nullptr;1760    }1761  } else {1762  __not_equal:1763    __s.__do_   = __state::__reject;1764    __s.__node_ = nullptr;1765  }1766}1767 1768// __word_boundary1769 1770template <class _CharT, class _Traits>1771class __word_boundary : public __owns_one_state<_CharT> {1772  typedef __owns_one_state<_CharT> base;1773 1774  _Traits __traits_;1775  bool __invert_;1776 1777public:1778  typedef std::__state<_CharT> __state;1779 1780  _LIBCPP_HIDE_FROM_ABI explicit __word_boundary(const _Traits& __traits, bool __invert, __node<_CharT>* __s)1781      : base(__s), __traits_(__traits), __invert_(__invert) {}1782 1783  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1784};1785 1786template <class _CharT, class _Traits>1787void __word_boundary<_CharT, _Traits>::__exec(__state& __s) const {1788  bool __is_word_b = false;1789  if (__s.__first_ != __s.__last_) {1790    if (__s.__current_ == __s.__last_) {1791      if (!(__s.__flags_ & regex_constants::match_not_eow)) {1792        _CharT __c  = __s.__current_[-1];1793        __is_word_b = __c == '_' || __traits_.isctype(__c, ctype_base::alnum);1794      }1795    } else if (__s.__current_ == __s.__first_ && !(__s.__flags_ & regex_constants::match_prev_avail)) {1796      if (!(__s.__flags_ & regex_constants::match_not_bow)) {1797        _CharT __c  = *__s.__current_;1798        __is_word_b = __c == '_' || __traits_.isctype(__c, ctype_base::alnum);1799      }1800    } else {1801      _CharT __c1    = __s.__current_[-1];1802      _CharT __c2    = *__s.__current_;1803      bool __is_c1_b = __c1 == '_' || __traits_.isctype(__c1, ctype_base::alnum);1804      bool __is_c2_b = __c2 == '_' || __traits_.isctype(__c2, ctype_base::alnum);1805      __is_word_b    = __is_c1_b != __is_c2_b;1806    }1807  }1808  if (__is_word_b != __invert_) {1809    __s.__do_   = __state::__accept_but_not_consume;1810    __s.__node_ = this->first();1811  } else {1812    __s.__do_   = __state::__reject;1813    __s.__node_ = nullptr;1814  }1815}1816 1817// __l_anchor1818 1819template <class _CharT>1820_LIBCPP_HIDE_FROM_ABI bool __is_eol(_CharT __c) {1821  return __c == '\r' || __c == '\n';1822}1823 1824template <class _CharT>1825class __l_anchor_multiline : public __owns_one_state<_CharT> {1826  typedef __owns_one_state<_CharT> base;1827 1828  bool __multiline_;1829 1830public:1831  typedef std::__state<_CharT> __state;1832 1833  _LIBCPP_HIDE_FROM_ABI __l_anchor_multiline(bool __multiline, __node<_CharT>* __s)1834      : base(__s), __multiline_(__multiline) {}1835 1836  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1837};1838 1839template <class _CharT>1840void __l_anchor_multiline<_CharT>::__exec(__state& __s) const {1841  if (__s.__at_first_ && __s.__current_ == __s.__first_ && !(__s.__flags_ & regex_constants::match_not_bol)) {1842    __s.__do_   = __state::__accept_but_not_consume;1843    __s.__node_ = this->first();1844  } else if (__multiline_ && !__s.__at_first_ && std::__is_eol(*std::prev(__s.__current_))) {1845    __s.__do_   = __state::__accept_but_not_consume;1846    __s.__node_ = this->first();1847  } else {1848    __s.__do_   = __state::__reject;1849    __s.__node_ = nullptr;1850  }1851}1852 1853// __r_anchor1854 1855template <class _CharT>1856class __r_anchor_multiline : public __owns_one_state<_CharT> {1857  typedef __owns_one_state<_CharT> base;1858 1859  bool __multiline_;1860 1861public:1862  typedef std::__state<_CharT> __state;1863 1864  _LIBCPP_HIDE_FROM_ABI __r_anchor_multiline(bool __multiline, __node<_CharT>* __s)1865      : base(__s), __multiline_(__multiline) {}1866 1867  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1868};1869 1870template <class _CharT>1871void __r_anchor_multiline<_CharT>::__exec(__state& __s) const {1872  if (__s.__current_ == __s.__last_ && !(__s.__flags_ & regex_constants::match_not_eol)) {1873    __s.__do_   = __state::__accept_but_not_consume;1874    __s.__node_ = this->first();1875  } else if (__multiline_ && std::__is_eol(*__s.__current_)) {1876    __s.__do_   = __state::__accept_but_not_consume;1877    __s.__node_ = this->first();1878  } else {1879    __s.__do_   = __state::__reject;1880    __s.__node_ = nullptr;1881  }1882}1883 1884// __match_any1885 1886template <class _CharT>1887class __match_any : public __owns_one_state<_CharT> {1888  typedef __owns_one_state<_CharT> base;1889 1890public:1891  typedef std::__state<_CharT> __state;1892 1893  _LIBCPP_HIDE_FROM_ABI __match_any(__node<_CharT>* __s) : base(__s) {}1894 1895  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1896};1897 1898template <class _CharT>1899void __match_any<_CharT>::__exec(__state& __s) const {1900  if (__s.__current_ != __s.__last_ && *__s.__current_ != 0) {1901    __s.__do_ = __state::__accept_and_consume;1902    ++__s.__current_;1903    __s.__node_ = this->first();1904  } else {1905    __s.__do_   = __state::__reject;1906    __s.__node_ = nullptr;1907  }1908}1909 1910// __match_any_but_newline1911 1912template <class _CharT>1913class __match_any_but_newline : public __owns_one_state<_CharT> {1914  typedef __owns_one_state<_CharT> base;1915 1916public:1917  typedef std::__state<_CharT> __state;1918 1919  _LIBCPP_HIDE_FROM_ABI __match_any_but_newline(__node<_CharT>* __s) : base(__s) {}1920 1921  void __exec(__state&) const override;1922};1923 1924template <>1925_LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<char>::__exec(__state&) const;1926#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS1927template <>1928_LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<wchar_t>::__exec(__state&) const;1929#endif1930 1931// __match_char1932 1933template <class _CharT>1934class __match_char : public __owns_one_state<_CharT> {1935  typedef __owns_one_state<_CharT> base;1936 1937  _CharT __c_;1938 1939public:1940  typedef std::__state<_CharT> __state;1941 1942  _LIBCPP_HIDE_FROM_ABI __match_char(_CharT __c, __node<_CharT>* __s) : base(__s), __c_(__c) {}1943 1944  __match_char(const __match_char&)            = delete;1945  __match_char& operator=(const __match_char&) = delete;1946 1947  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1948};1949 1950template <class _CharT>1951void __match_char<_CharT>::__exec(__state& __s) const {1952  if (__s.__current_ != __s.__last_ && *__s.__current_ == __c_) {1953    __s.__do_ = __state::__accept_and_consume;1954    ++__s.__current_;1955    __s.__node_ = this->first();1956  } else {1957    __s.__do_   = __state::__reject;1958    __s.__node_ = nullptr;1959  }1960}1961 1962// __match_char_icase1963 1964template <class _CharT, class _Traits>1965class __match_char_icase : public __owns_one_state<_CharT> {1966  typedef __owns_one_state<_CharT> base;1967 1968  _Traits __traits_;1969  _CharT __c_;1970 1971public:1972  typedef std::__state<_CharT> __state;1973 1974  _LIBCPP_HIDE_FROM_ABI __match_char_icase(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)1975      : base(__s), __traits_(__traits), __c_(__traits.translate_nocase(__c)) {}1976 1977  __match_char_icase(const __match_char_icase&)            = delete;1978  __match_char_icase& operator=(const __match_char_icase&) = delete;1979 1980  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;1981};1982 1983template <class _CharT, class _Traits>1984void __match_char_icase<_CharT, _Traits>::__exec(__state& __s) const {1985  if (__s.__current_ != __s.__last_ && __traits_.translate_nocase(*__s.__current_) == __c_) {1986    __s.__do_ = __state::__accept_and_consume;1987    ++__s.__current_;1988    __s.__node_ = this->first();1989  } else {1990    __s.__do_   = __state::__reject;1991    __s.__node_ = nullptr;1992  }1993}1994 1995// __match_char_collate1996 1997template <class _CharT, class _Traits>1998class __match_char_collate : public __owns_one_state<_CharT> {1999  typedef __owns_one_state<_CharT> base;2000 2001  _Traits __traits_;2002  _CharT __c_;2003 2004public:2005  typedef std::__state<_CharT> __state;2006 2007  _LIBCPP_HIDE_FROM_ABI __match_char_collate(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)2008      : base(__s), __traits_(__traits), __c_(__traits.translate(__c)) {}2009 2010  __match_char_collate(const __match_char_collate&)            = delete;2011  __match_char_collate& operator=(const __match_char_collate&) = delete;2012 2013  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;2014};2015 2016template <class _CharT, class _Traits>2017void __match_char_collate<_CharT, _Traits>::__exec(__state& __s) const {2018  if (__s.__current_ != __s.__last_ && __traits_.translate(*__s.__current_) == __c_) {2019    __s.__do_ = __state::__accept_and_consume;2020    ++__s.__current_;2021    __s.__node_ = this->first();2022  } else {2023    __s.__do_   = __state::__reject;2024    __s.__node_ = nullptr;2025  }2026}2027 2028// __bracket_expression2029 2030template <class _CharT, class _Traits>2031class __bracket_expression : public __owns_one_state<_CharT> {2032  typedef __owns_one_state<_CharT> base;2033  typedef typename _Traits::string_type string_type;2034 2035  _Traits __traits_;2036  vector<_CharT> __chars_;2037  vector<_CharT> __neg_chars_;2038  vector<pair<string_type, string_type> > __ranges_;2039  vector<pair<_CharT, _CharT> > __digraphs_;2040  vector<string_type> __equivalences_;2041  typename regex_traits<_CharT>::char_class_type __mask_;2042  typename regex_traits<_CharT>::char_class_type __neg_mask_;2043  bool __negate_;2044  bool __icase_;2045  bool __collate_;2046  bool __might_have_digraph_;2047 2048public:2049  typedef std::__state<_CharT> __state;2050 2051  _LIBCPP_HIDE_FROM_ABI2052  __bracket_expression(const _Traits& __traits, __node<_CharT>* __s, bool __negate, bool __icase, bool __collate)2053      : base(__s),2054        __traits_(__traits),2055        __mask_(),2056        __neg_mask_(),2057        __negate_(__negate),2058        __icase_(__icase),2059        __collate_(__collate),2060        __might_have_digraph_(__traits_.getloc().name() != "C") {}2061 2062  __bracket_expression(const __bracket_expression&)            = delete;2063  __bracket_expression& operator=(const __bracket_expression&) = delete;2064 2065  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;2066 2067  _LIBCPP_HIDE_FROM_ABI bool __negated() const { return __negate_; }2068 2069  _LIBCPP_HIDE_FROM_ABI void __add_char(_CharT __c) {2070    if (__icase_)2071      __chars_.push_back(__traits_.translate_nocase(__c));2072    else if (__collate_)2073      __chars_.push_back(__traits_.translate(__c));2074    else2075      __chars_.push_back(__c);2076  }2077  _LIBCPP_HIDE_FROM_ABI void __add_neg_char(_CharT __c) {2078    if (__icase_)2079      __neg_chars_.push_back(__traits_.translate_nocase(__c));2080    else if (__collate_)2081      __neg_chars_.push_back(__traits_.translate(__c));2082    else2083      __neg_chars_.push_back(__c);2084  }2085  _LIBCPP_HIDE_FROM_ABI void __add_range(string_type __b, string_type __e) {2086    if (__collate_) {2087      if (__icase_) {2088        for (size_t __i = 0; __i < __b.size(); ++__i)2089          __b[__i] = __traits_.translate_nocase(__b[__i]);2090        for (size_t __i = 0; __i < __e.size(); ++__i)2091          __e[__i] = __traits_.translate_nocase(__e[__i]);2092      } else {2093        for (size_t __i = 0; __i < __b.size(); ++__i)2094          __b[__i] = __traits_.translate(__b[__i]);2095        for (size_t __i = 0; __i < __e.size(); ++__i)2096          __e[__i] = __traits_.translate(__e[__i]);2097      }2098      __ranges_.push_back(2099          std::make_pair(__traits_.transform(__b.begin(), __b.end()), __traits_.transform(__e.begin(), __e.end())));2100    } else {2101      if (__b.size() != 1 || __e.size() != 1 || char_traits<typename string_type::value_type>::lt(__e[0], __b[0]))2102        __throw_regex_error<regex_constants::error_range>();2103      if (__icase_) {2104        __b[0] = __traits_.translate_nocase(__b[0]);2105        __e[0] = __traits_.translate_nocase(__e[0]);2106      }2107      __ranges_.push_back(std::make_pair(std::move(__b), std::move(__e)));2108    }2109  }2110  _LIBCPP_HIDE_FROM_ABI void __add_digraph(_CharT __c1, _CharT __c2) {2111    if (__icase_)2112      __digraphs_.push_back(std::make_pair(__traits_.translate_nocase(__c1), __traits_.translate_nocase(__c2)));2113    else if (__collate_)2114      __digraphs_.push_back(std::make_pair(__traits_.translate(__c1), __traits_.translate(__c2)));2115    else2116      __digraphs_.push_back(std::make_pair(__c1, __c2));2117  }2118  _LIBCPP_HIDE_FROM_ABI void __add_equivalence(const string_type& __s) { __equivalences_.push_back(__s); }2119  _LIBCPP_HIDE_FROM_ABI void __add_class(typename regex_traits<_CharT>::char_class_type __mask) { __mask_ |= __mask; }2120  _LIBCPP_HIDE_FROM_ABI void __add_neg_class(typename regex_traits<_CharT>::char_class_type __mask) {2121    __neg_mask_ |= __mask;2122  }2123};2124 2125template <class _CharT, class _Traits>2126void __bracket_expression<_CharT, _Traits>::__exec(__state& __s) const {2127  bool __found        = false;2128  unsigned __consumed = 0;2129  if (__s.__current_ != __s.__last_) {2130    ++__consumed;2131    if (__might_have_digraph_) {2132      const _CharT* __next = std::next(__s.__current_);2133      if (__next != __s.__last_) {2134        pair<_CharT, _CharT> __ch2(*__s.__current_, *__next);2135        if (__icase_) {2136          __ch2.first  = __traits_.translate_nocase(__ch2.first);2137          __ch2.second = __traits_.translate_nocase(__ch2.second);2138        } else if (__collate_) {2139          __ch2.first  = __traits_.translate(__ch2.first);2140          __ch2.second = __traits_.translate(__ch2.second);2141        }2142        if (!__traits_.lookup_collatename(&__ch2.first, &__ch2.first + 2).empty()) {2143          // __ch2 is a digraph in this locale2144          ++__consumed;2145          for (size_t __i = 0; __i < __digraphs_.size(); ++__i) {2146            if (__ch2 == __digraphs_[__i]) {2147              __found = true;2148              goto __exit;2149            }2150          }2151          if (__collate_ && !__ranges_.empty()) {2152            string_type __s2 = __traits_.transform(&__ch2.first, &__ch2.first + 2);2153            for (size_t __i = 0; __i < __ranges_.size(); ++__i) {2154              if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second) {2155                __found = true;2156                goto __exit;2157              }2158            }2159          }2160          if (!__equivalences_.empty()) {2161            string_type __s2 = __traits_.transform_primary(&__ch2.first, &__ch2.first + 2);2162            for (size_t __i = 0; __i < __equivalences_.size(); ++__i) {2163              if (__s2 == __equivalences_[__i]) {2164                __found = true;2165                goto __exit;2166              }2167            }2168          }2169          if (__traits_.isctype(__ch2.first, __mask_) && __traits_.isctype(__ch2.second, __mask_)) {2170            __found = true;2171            goto __exit;2172          }2173          if (!__traits_.isctype(__ch2.first, __neg_mask_) && !__traits_.isctype(__ch2.second, __neg_mask_)) {2174            __found = true;2175            goto __exit;2176          }2177          goto __exit;2178        }2179      }2180    }2181    // test *__s.__current_ as not a digraph2182    _CharT __ch = *__s.__current_;2183    if (__icase_)2184      __ch = __traits_.translate_nocase(__ch);2185    else if (__collate_)2186      __ch = __traits_.translate(__ch);2187    for (size_t __i = 0; __i < __chars_.size(); ++__i) {2188      if (__ch == __chars_[__i]) {2189        __found = true;2190        goto __exit;2191      }2192    }2193    // When there's at least one of __neg_chars_ and __neg_mask_, the set2194    // of "__found" chars is2195    //   union(complement(union(__neg_chars_, __neg_mask_)),2196    //         other cases...)2197    //2198    // It doesn't make sense to check this when there are no __neg_chars_2199    // and no __neg_mask_.2200    if (!(__neg_mask_ == 0 && __neg_chars_.empty())) {2201      const bool __in_neg_mask  = __traits_.isctype(__ch, __neg_mask_);2202      const bool __in_neg_chars = std::find(__neg_chars_.begin(), __neg_chars_.end(), __ch) != __neg_chars_.end();2203      if (!(__in_neg_mask || __in_neg_chars)) {2204        __found = true;2205        goto __exit;2206      }2207    }2208    if (!__ranges_.empty()) {2209      string_type __s2 = __collate_ ? __traits_.transform(&__ch, &__ch + 1) : string_type(1, __ch);2210      for (size_t __i = 0; __i < __ranges_.size(); ++__i) {2211        if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second) {2212          __found = true;2213          goto __exit;2214        }2215      }2216    }2217    if (!__equivalences_.empty()) {2218      string_type __s2 = __traits_.transform_primary(&__ch, &__ch + 1);2219      for (size_t __i = 0; __i < __equivalences_.size(); ++__i) {2220        if (__s2 == __equivalences_[__i]) {2221          __found = true;2222          goto __exit;2223        }2224      }2225    }2226    if (__traits_.isctype(__ch, __mask_)) {2227      __found = true;2228      goto __exit;2229    }2230  } else2231    __found = __negate_; // force reject2232__exit:2233  if (__found != __negate_) {2234    __s.__do_ = __state::__accept_and_consume;2235    __s.__current_ += __consumed;2236    __s.__node_ = this->first();2237  } else {2238    __s.__do_   = __state::__reject;2239    __s.__node_ = nullptr;2240  }2241}2242 2243template <class _CharT, class _Traits>2244class __lookahead;2245 2246template <class _CharT, class _Traits = regex_traits<_CharT> >2247class _LIBCPP_TEMPLATE_VIS basic_regex;2248 2249typedef basic_regex<char> regex;2250#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS2251typedef basic_regex<wchar_t> wregex;2252#endif2253 2254template <class _CharT, class _Traits>2255class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(regex)2256    _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wregex)) basic_regex {2257public:2258  // types:2259  typedef _CharT value_type;2260  typedef _Traits traits_type;2261  typedef typename _Traits::string_type string_type;2262  typedef regex_constants::syntax_option_type flag_type;2263  typedef typename _Traits::locale_type locale_type;2264 2265private:2266  _Traits __traits_;2267  flag_type __flags_;2268  unsigned __marked_count_;2269  unsigned __loop_count_;2270  int __open_count_;2271  shared_ptr<__empty_state<_CharT> > __start_;2272  __owns_one_state<_CharT>* __end_;2273 2274  typedef std::__state<_CharT> __state;2275  typedef std::__node<_CharT> __node;2276 2277public:2278  // constants:2279  static const regex_constants::syntax_option_type icase      = regex_constants::icase;2280  static const regex_constants::syntax_option_type nosubs     = regex_constants::nosubs;2281  static const regex_constants::syntax_option_type optimize   = regex_constants::optimize;2282  static const regex_constants::syntax_option_type collate    = regex_constants::collate;2283  static const regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;2284  static const regex_constants::syntax_option_type basic      = regex_constants::basic;2285  static const regex_constants::syntax_option_type extended   = regex_constants::extended;2286  static const regex_constants::syntax_option_type awk        = regex_constants::awk;2287  static const regex_constants::syntax_option_type grep       = regex_constants::grep;2288  static const regex_constants::syntax_option_type egrep      = regex_constants::egrep;2289  static const regex_constants::syntax_option_type multiline  = regex_constants::multiline;2290 2291  // construct/copy/destroy:2292  _LIBCPP_HIDE_FROM_ABI basic_regex()2293      : __flags_(regex_constants::ECMAScript),2294        __marked_count_(0),2295        __loop_count_(0),2296        __open_count_(0),2297        __end_(nullptr) {}2298  _LIBCPP_HIDE_FROM_ABI explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)2299      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {2300    __init(__p, __p + __traits_.length(__p));2301  }2302 2303  _LIBCPP_HIDE_FROM_ABI basic_regex(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript)2304      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {2305    __init(__p, __p + __len);2306  }2307 2308  //     basic_regex(const basic_regex&) = default;2309  //     basic_regex(basic_regex&&) = default;2310  template <class _ST, class _SA>2311  _LIBCPP_HIDE_FROM_ABI explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,2312                                             flag_type __f = regex_constants::ECMAScript)2313      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {2314    __init(__p.begin(), __p.end());2315  }2316 2317  template <class _ForwardIterator>2318  _LIBCPP_HIDE_FROM_ABI2319  basic_regex(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript)2320      : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {2321    __init(__first, __last);2322  }2323 2324  //    ~basic_regex() = default;2325 2326  //     basic_regex& operator=(const basic_regex&) = default;2327  //     basic_regex& operator=(basic_regex&&) = default;2328  _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const value_type* __p) { return assign(__p); }2329  template <class _ST, class _SA>2330  _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p) {2331    return assign(__p);2332  }2333 2334  // assign:2335  _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const basic_regex& __that) { return *this = __that; }2336  _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript) {2337    return assign(__p, __p + __traits_.length(__p), __f);2338  }2339  _LIBCPP_HIDE_FROM_ABI basic_regex&2340  assign(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript) {2341    return assign(__p, __p + __len, __f);2342  }2343  template <class _ST, class _SA>2344  _LIBCPP_HIDE_FROM_ABI basic_regex&2345  assign(const basic_string<value_type, _ST, _SA>& __s, flag_type __f = regex_constants::ECMAScript) {2346    return assign(__s.begin(), __s.end(), __f);2347  }2348 2349  template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>2350  _LIBCPP_HIDE_FROM_ABI basic_regex&2351  assign(_InputIterator __first, _InputIterator __last, flag_type __f = regex_constants::ECMAScript) {2352    basic_string<_CharT> __t(__first, __last);2353    return assign(__t.begin(), __t.end(), __f);2354  }2355 2356private:2357  _LIBCPP_HIDE_FROM_ABI void __member_init(flag_type __f) {2358    __flags_        = __f;2359    __marked_count_ = 0;2360    __loop_count_   = 0;2361    __open_count_   = 0;2362    __end_          = nullptr;2363  }2364 2365public:2366  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>2367  _LIBCPP_HIDE_FROM_ABI basic_regex&2368  assign(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript) {2369    return assign(basic_regex(__first, __last, __f));2370  }2371 2372  // const operations:2373  _LIBCPP_HIDE_FROM_ABI unsigned mark_count() const { return __marked_count_; }2374  _LIBCPP_HIDE_FROM_ABI flag_type flags() const { return __flags_; }2375 2376  // locale:2377  _LIBCPP_HIDE_FROM_ABI locale_type imbue(locale_type __loc) {2378    __member_init(ECMAScript);2379    __start_.reset();2380    return __traits_.imbue(__loc);2381  }2382  _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __traits_.getloc(); }2383 2384  // swap:2385  void swap(basic_regex& __r);2386 2387private:2388  _LIBCPP_HIDE_FROM_ABI unsigned __loop_count() const { return __loop_count_; }2389 2390  _LIBCPP_HIDE_FROM_ABI bool __use_multiline() const {2391    return __get_grammar(__flags_) == ECMAScript && (__flags_ & multiline);2392  }2393 2394  template <class _ForwardIterator>2395  void __init(_ForwardIterator __first, _ForwardIterator __last);2396  template <class _ForwardIterator>2397  _ForwardIterator __parse(_ForwardIterator __first, _ForwardIterator __last);2398  template <class _ForwardIterator>2399  _ForwardIterator __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);2400  template <class _ForwardIterator>2401  _ForwardIterator __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);2402  template <class _ForwardIterator>2403  _ForwardIterator __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);2404  template <class _ForwardIterator>2405  _ForwardIterator __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);2406  template <class _ForwardIterator>2407  _ForwardIterator __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);2408  template <class _ForwardIterator>2409  _ForwardIterator __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);2410  template <class _ForwardIterator>2411  _ForwardIterator __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);2412  template <class _ForwardIterator>2413  _ForwardIterator __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);2414  template <class _ForwardIterator>2415  _ForwardIterator __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);2416  template <class _ForwardIterator>2417  _ForwardIterator __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);2418  template <class _ForwardIterator>2419  _ForwardIterator __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);2420  template <class _ForwardIterator>2421  _ForwardIterator __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);2422  template <class _ForwardIterator>2423  _ForwardIterator __parse_RE_dupl_symbol(2424      _ForwardIterator __first,2425      _ForwardIterator __last,2426      __owns_one_state<_CharT>* __s,2427      unsigned __mexp_begin,2428      unsigned __mexp_end);2429  template <class _ForwardIterator>2430  _ForwardIterator __parse_ERE_dupl_symbol(2431      _ForwardIterator __first,2432      _ForwardIterator __last,2433      __owns_one_state<_CharT>* __s,2434      unsigned __mexp_begin,2435      unsigned __mexp_end);2436  template <class _ForwardIterator>2437  _ForwardIterator __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);2438  template <class _ForwardIterator>2439  _ForwardIterator2440  __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);2441  template <class _ForwardIterator>2442  _ForwardIterator __parse_expression_term(2443      _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);2444  template <class _ForwardIterator>2445  _ForwardIterator __parse_equivalence_class(2446      _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);2447  template <class _ForwardIterator>2448  _ForwardIterator __parse_character_class(2449      _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);2450  template <class _ForwardIterator>2451  _ForwardIterator2452  __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>& __col_sym);2453  template <class _ForwardIterator>2454  _ForwardIterator __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);2455  template <class _ForwardIterator>2456  _ForwardIterator __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);2457  template <class _ForwardIterator>2458  _ForwardIterator __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);2459  template <class _ForwardIterator>2460  _ForwardIterator __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);2461  template <class _ForwardIterator>2462  _ForwardIterator __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);2463  template <class _ForwardIterator>2464  _ForwardIterator __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);2465  template <class _ForwardIterator>2466  _ForwardIterator __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);2467  template <class _ForwardIterator>2468  _ForwardIterator __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);2469  template <class _ForwardIterator>2470  _ForwardIterator __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);2471  template <class _ForwardIterator>2472  _ForwardIterator __parse_term(_ForwardIterator __first, _ForwardIterator __last);2473  template <class _ForwardIterator>2474  _ForwardIterator __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);2475  template <class _ForwardIterator>2476  _ForwardIterator __parse_atom(_ForwardIterator __first, _ForwardIterator __last);2477  template <class _ForwardIterator>2478  _ForwardIterator __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);2479  template <class _ForwardIterator>2480  _ForwardIterator __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);2481  template <class _ForwardIterator>2482  _ForwardIterator __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);2483  template <class _ForwardIterator>2484  _ForwardIterator2485  __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str = nullptr);2486  template <class _ForwardIterator>2487  _ForwardIterator __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);2488  template <class _ForwardIterator>2489  _ForwardIterator __parse_grep(_ForwardIterator __first, _ForwardIterator __last);2490  template <class _ForwardIterator>2491  _ForwardIterator __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);2492  template <class _ForwardIterator>2493  _ForwardIterator __parse_class_escape(2494      _ForwardIterator __first,2495      _ForwardIterator __last,2496      basic_string<_CharT>& __str,2497      __bracket_expression<_CharT, _Traits>* __ml);2498  template <class _ForwardIterator>2499  _ForwardIterator2500  __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str = nullptr);2501 2502  bool __test_back_ref(_CharT);2503 2504  _LIBCPP_HIDE_FROM_ABI void __push_l_anchor();2505  void __push_r_anchor();2506  void __push_match_any();2507  void __push_match_any_but_newline();2508  _LIBCPP_HIDE_FROM_ABI void __push_greedy_inf_repeat(2509      size_t __min, __owns_one_state<_CharT>* __s, unsigned __mexp_begin = 0, unsigned __mexp_end = 0) {2510    __push_loop(__min, numeric_limits<size_t>::max(), __s, __mexp_begin, __mexp_end);2511  }2512  _LIBCPP_HIDE_FROM_ABI void __push_nongreedy_inf_repeat(2513      size_t __min, __owns_one_state<_CharT>* __s, unsigned __mexp_begin = 0, unsigned __mexp_end = 0) {2514    __push_loop(__min, numeric_limits<size_t>::max(), __s, __mexp_begin, __mexp_end, false);2515  }2516  void __push_loop(size_t __min,2517                   size_t __max,2518                   __owns_one_state<_CharT>* __s,2519                   size_t __mexp_begin = 0,2520                   size_t __mexp_end   = 0,2521                   bool __greedy       = true);2522  __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);2523  void __push_char(value_type __c);2524  void __push_back_ref(int __i);2525  void __push_alternation(__owns_one_state<_CharT>* __sa, __owns_one_state<_CharT>* __sb);2526  void __push_begin_marked_subexpression();2527  void __push_end_marked_subexpression(unsigned);2528  void __push_empty();2529  void __push_word_boundary(bool);2530  void __push_lookahead(const basic_regex&, bool, unsigned);2531 2532  template <class _Allocator>2533  bool __search(const _CharT* __first,2534                const _CharT* __last,2535                match_results<const _CharT*, _Allocator>& __m,2536                regex_constants::match_flag_type __flags) const;2537 2538  template <class _Allocator>2539  bool __match_at_start(const _CharT* __first,2540                        const _CharT* __last,2541                        match_results<const _CharT*, _Allocator>& __m,2542                        regex_constants::match_flag_type __flags,2543                        bool) const;2544  template <class _Allocator>2545  bool __match_at_start_ecma(2546      const _CharT* __first,2547      const _CharT* __last,2548      match_results<const _CharT*, _Allocator>& __m,2549      regex_constants::match_flag_type __flags,2550      bool) const;2551  template <class _Allocator>2552  bool __match_at_start_posix_nosubs(2553      const _CharT* __first,2554      const _CharT* __last,2555      match_results<const _CharT*, _Allocator>& __m,2556      regex_constants::match_flag_type __flags,2557      bool) const;2558  template <class _Allocator>2559  bool __match_at_start_posix_subs(2560      const _CharT* __first,2561      const _CharT* __last,2562      match_results<const _CharT*, _Allocator>& __m,2563      regex_constants::match_flag_type __flags,2564      bool) const;2565 2566  template <class _Bp, class _Ap, class _Cp, class _Tp>2567  friend bool2568  regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);2569 2570  template <class _Ap, class _Cp, class _Tp>2571  friend bool2572  regex_search(const _Cp*,2573               const _Cp*,2574               match_results<const _Cp*, _Ap>&,2575               const basic_regex<_Cp, _Tp>&,2576               regex_constants::match_flag_type);2577 2578  template <class _Bp, class _Cp, class _Tp>2579  friend bool regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);2580 2581  template <class _Cp, class _Tp>2582  friend bool regex_search(const _Cp*, const _Cp*, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);2583 2584  template <class _Cp, class _Ap, class _Tp>2585  friend bool regex_search(2586      const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);2587 2588  template <class _ST, class _SA, class _Cp, class _Tp>2589  friend bool regex_search(const basic_string<_Cp, _ST, _SA>& __s,2590                           const basic_regex<_Cp, _Tp>& __e,2591                           regex_constants::match_flag_type __flags);2592 2593  template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>2594  friend bool regex_search(const basic_string<_Cp, _ST, _SA>& __s,2595                           match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,2596                           const basic_regex<_Cp, _Tp>& __e,2597                           regex_constants::match_flag_type __flags);2598 2599  template <class _Iter, class _Ap, class _Cp, class _Tp>2600  friend bool2601  regex_search(__wrap_iter<_Iter> __first,2602               __wrap_iter<_Iter> __last,2603               match_results<__wrap_iter<_Iter>, _Ap>& __m,2604               const basic_regex<_Cp, _Tp>& __e,2605               regex_constants::match_flag_type __flags);2606 2607  template <class, class>2608  friend class __lookahead;2609};2610 2611template <class _CharT, class _Traits>2612const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;2613template <class _CharT, class _Traits>2614const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;2615template <class _CharT, class _Traits>2616const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;2617template <class _CharT, class _Traits>2618const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;2619template <class _CharT, class _Traits>2620const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;2621template <class _CharT, class _Traits>2622const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;2623template <class _CharT, class _Traits>2624const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;2625template <class _CharT, class _Traits>2626const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;2627template <class _CharT, class _Traits>2628const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;2629template <class _CharT, class _Traits>2630const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;2631 2632template <class _CharT, class _Traits>2633void basic_regex<_CharT, _Traits>::swap(basic_regex& __r) {2634  using std::swap;2635  swap(__traits_, __r.__traits_);2636  swap(__flags_, __r.__flags_);2637  swap(__marked_count_, __r.__marked_count_);2638  swap(__loop_count_, __r.__loop_count_);2639  swap(__open_count_, __r.__open_count_);2640  swap(__start_, __r.__start_);2641  swap(__end_, __r.__end_);2642}2643 2644template <class _CharT, class _Traits>2645inline _LIBCPP_HIDE_FROM_ABI void swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y) {2646  return __x.swap(__y);2647}2648 2649// __lookahead2650 2651template <class _CharT, class _Traits>2652class __lookahead : public __owns_one_state<_CharT> {2653  typedef __owns_one_state<_CharT> base;2654 2655  basic_regex<_CharT, _Traits> __exp_;2656  unsigned __mexp_;2657  bool __invert_;2658 2659public:2660  typedef std::__state<_CharT> __state;2661 2662  _LIBCPP_HIDE_FROM_ABI2663  __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)2664      : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}2665 2666  __lookahead(const __lookahead&)            = delete;2667  __lookahead& operator=(const __lookahead&) = delete;2668 2669  _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;2670};2671 2672template <class _CharT, class _Traits>2673void __lookahead<_CharT, _Traits>::__exec(__state& __s) const {2674  match_results<const _CharT*> __m;2675  __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);2676  bool __matched = __exp_.__match_at_start_ecma(2677      __s.__current_,2678      __s.__last_,2679      __m,2680      (__s.__flags_ | regex_constants::match_continuous) & ~regex_constants::__full_match,2681      __s.__at_first_ && __s.__current_ == __s.__first_);2682  if (__matched != __invert_) {2683    __s.__do_   = __state::__accept_but_not_consume;2684    __s.__node_ = this->first();2685    for (unsigned __i = 1; __i < __m.size(); ++__i) {2686      __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];2687    }2688  } else {2689    __s.__do_   = __state::__reject;2690    __s.__node_ = nullptr;2691  }2692}2693 2694template <class _CharT, class _Traits>2695template <class _ForwardIterator>2696void basic_regex<_CharT, _Traits>::__init(_ForwardIterator __first, _ForwardIterator __last) {2697  if (__get_grammar(__flags_) == 0)2698    __flags_ |= regex_constants::ECMAScript;2699  _ForwardIterator __temp = __parse(__first, __last);2700  if (__temp != __last)2701    __throw_regex_error<regex_constants::__re_err_parse>();2702}2703 2704template <class _CharT, class _Traits>2705template <class _ForwardIterator>2706_ForwardIterator basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first, _ForwardIterator __last) {2707  {2708    unique_ptr<__node> __h(new __end_state<_CharT>);2709    __start_.reset(new __empty_state<_CharT>(__h.get()));2710    __h.release();2711    __end_ = __start_.get();2712  }2713  switch (__get_grammar(__flags_)) {2714  case ECMAScript:2715    __first = __parse_ecma_exp(__first, __last);2716    break;2717  case basic:2718    __first = __parse_basic_reg_exp(__first, __last);2719    break;2720  case extended:2721  case awk:2722    __first = __parse_extended_reg_exp(__first, __last);2723    break;2724  case grep:2725    __first = __parse_grep(__first, __last);2726    break;2727  case egrep:2728    __first = __parse_egrep(__first, __last);2729    break;2730  default:2731    __throw_regex_error<regex_constants::__re_err_grammar>();2732  }2733  return __first;2734}2735 2736template <class _CharT, class _Traits>2737template <class _ForwardIterator>2738_ForwardIterator2739basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last) {2740  if (__first != __last) {2741    if (*__first == '^') {2742      __push_l_anchor();2743      ++__first;2744    }2745    if (__first != __last) {2746      __first = __parse_RE_expression(__first, __last);2747      if (__first != __last) {2748        _ForwardIterator __temp = std::next(__first);2749        if (__temp == __last && *__first == '$') {2750          __push_r_anchor();2751          ++__first;2752        }2753      }2754    }2755    if (__first != __last)2756      __throw_regex_error<regex_constants::__re_err_empty>();2757  }2758  return __first;2759}2760 2761template <class _CharT, class _Traits>2762template <class _ForwardIterator>2763_ForwardIterator2764basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last) {2765  __owns_one_state<_CharT>* __sa = __end_;2766  _ForwardIterator __temp        = __parse_ERE_branch(__first, __last);2767  if (__temp == __first)2768    __throw_regex_error<regex_constants::__re_err_empty>();2769  __first = __temp;2770  while (__first != __last && *__first == '|') {2771    __owns_one_state<_CharT>* __sb = __end_;2772    __temp                         = __parse_ERE_branch(++__first, __last);2773    if (__temp == __first)2774      __throw_regex_error<regex_constants::__re_err_empty>();2775    __push_alternation(__sa, __sb);2776    __first = __temp;2777  }2778  return __first;2779}2780 2781template <class _CharT, class _Traits>2782template <class _ForwardIterator>2783_ForwardIterator basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last) {2784  _ForwardIterator __temp = __parse_ERE_expression(__first, __last);2785  if (__temp == __first)2786    __throw_regex_error<regex_constants::__re_err_empty>();2787  do {2788    __first = __temp;2789    __temp  = __parse_ERE_expression(__first, __last);2790  } while (__temp != __first);2791  return __first;2792}2793 2794template <class _CharT, class _Traits>2795template <class _ForwardIterator>2796_ForwardIterator2797basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last) {2798  __owns_one_state<_CharT>* __e = __end_;2799  unsigned __mexp_begin         = __marked_count_;2800  _ForwardIterator __temp       = __parse_one_char_or_coll_elem_ERE(__first, __last);2801  if (__temp == __first && __temp != __last) {2802    switch (*__temp) {2803    case '^':2804      __push_l_anchor();2805      ++__temp;2806      break;2807    case '$':2808      __push_r_anchor();2809      ++__temp;2810      break;2811    case '(':2812      __push_begin_marked_subexpression();2813      unsigned __temp_count = __marked_count_;2814      ++__open_count_;2815      __temp = __parse_extended_reg_exp(++__temp, __last);2816      if (__temp == __last || *__temp != ')')2817        __throw_regex_error<regex_constants::error_paren>();2818      __push_end_marked_subexpression(__temp_count);2819      --__open_count_;2820      ++__temp;2821      break;2822    }2823  }2824  if (__temp != __first)2825    __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);2826  __first = __temp;2827  return __first;2828}2829 2830template <class _CharT, class _Traits>2831template <class _ForwardIterator>2832_ForwardIterator2833basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last) {2834  while (true) {2835    _ForwardIterator __temp = __parse_simple_RE(__first, __last);2836    if (__temp == __first)2837      break;2838    __first = __temp;2839  }2840  return __first;2841}2842 2843template <class _CharT, class _Traits>2844template <class _ForwardIterator>2845_ForwardIterator basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last) {2846  if (__first != __last) {2847    __owns_one_state<_CharT>* __e = __end_;2848    unsigned __mexp_begin         = __marked_count_;2849    _ForwardIterator __temp       = __parse_nondupl_RE(__first, __last);2850    if (__temp != __first)2851      __first = __parse_RE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);2852  }2853  return __first;2854}2855 2856template <class _CharT, class _Traits>2857template <class _ForwardIterator>2858_ForwardIterator basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last) {2859  _ForwardIterator __temp = __first;2860  __first                 = __parse_one_char_or_coll_elem_RE(__first, __last);2861  if (__temp == __first) {2862    __temp = __parse_Back_open_paren(__first, __last);2863    if (__temp != __first) {2864      __push_begin_marked_subexpression();2865      unsigned __temp_count = __marked_count_;2866      __first               = __parse_RE_expression(__temp, __last);2867      __temp                = __parse_Back_close_paren(__first, __last);2868      if (__temp == __first)2869        __throw_regex_error<regex_constants::error_paren>();2870      __push_end_marked_subexpression(__temp_count);2871      __first = __temp;2872    } else2873      __first = __parse_BACKREF(__first, __last);2874  }2875  return __first;2876}2877 2878template <class _CharT, class _Traits>2879template <class _ForwardIterator>2880_ForwardIterator2881basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last) {2882  _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);2883  if (__temp == __first) {2884    __temp = __parse_QUOTED_CHAR(__first, __last);2885    if (__temp == __first) {2886      if (__temp != __last && *__temp == '.') {2887        __push_match_any();2888        ++__temp;2889      } else2890        __temp = __parse_bracket_expression(__first, __last);2891    }2892  }2893  __first = __temp;2894  return __first;2895}2896 2897template <class _CharT, class _Traits>2898template <class _ForwardIterator>2899_ForwardIterator2900basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last) {2901  _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);2902  if (__temp == __first) {2903    __temp = __parse_QUOTED_CHAR_ERE(__first, __last);2904    if (__temp == __first) {2905      if (__temp != __last && *__temp == '.') {2906        __push_match_any();2907        ++__temp;2908      } else2909        __temp = __parse_bracket_expression(__first, __last);2910    }2911  }2912  __first = __temp;2913  return __first;2914}2915 2916template <class _CharT, class _Traits>2917template <class _ForwardIterator>2918_ForwardIterator2919basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last) {2920  if (__first != __last) {2921    _ForwardIterator __temp = std::next(__first);2922    if (__temp != __last) {2923      if (*__first == '\\' && *__temp == '(')2924        __first = ++__temp;2925    }2926  }2927  return __first;2928}2929 2930template <class _CharT, class _Traits>2931template <class _ForwardIterator>2932_ForwardIterator2933basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last) {2934  if (__first != __last) {2935    _ForwardIterator __temp = std::next(__first);2936    if (__temp != __last) {2937      if (*__first == '\\' && *__temp == ')')2938        __first = ++__temp;2939    }2940  }2941  return __first;2942}2943 2944template <class _CharT, class _Traits>2945template <class _ForwardIterator>2946_ForwardIterator2947basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last) {2948  if (__first != __last) {2949    _ForwardIterator __temp = std::next(__first);2950    if (__temp != __last) {2951      if (*__first == '\\' && *__temp == '{')2952        __first = ++__temp;2953    }2954  }2955  return __first;2956}2957 2958template <class _CharT, class _Traits>2959template <class _ForwardIterator>2960_ForwardIterator2961basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last) {2962  if (__first != __last) {2963    _ForwardIterator __temp = std::next(__first);2964    if (__temp != __last) {2965      if (*__first == '\\' && *__temp == '}')2966        __first = ++__temp;2967    }2968  }2969  return __first;2970}2971 2972template <class _CharT, class _Traits>2973template <class _ForwardIterator>2974_ForwardIterator basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last) {2975  if (__first != __last) {2976    _ForwardIterator __temp = std::next(__first);2977    if (__temp != __last && *__first == '\\' && __test_back_ref(*__temp))2978      __first = ++__temp;2979  }2980  return __first;2981}2982 2983template <class _CharT, class _Traits>2984template <class _ForwardIterator>2985_ForwardIterator basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last) {2986  if (__first != __last) {2987    _ForwardIterator __temp = std::next(__first);2988    if (__temp == __last && *__first == '$')2989      return __first;2990    // Not called inside a bracket2991    if (*__first == '.' || *__first == '\\' || *__first == '[')2992      return __first;2993    __push_char(*__first);2994    ++__first;2995  }2996  return __first;2997}2998 2999template <class _CharT, class _Traits>3000template <class _ForwardIterator>3001_ForwardIterator basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last) {3002  if (__first != __last) {3003    switch (*__first) {3004    case '^':3005    case '.':3006    case '[':3007    case '$':3008    case '(':3009    case '|':3010    case '*':3011    case '+':3012    case '?':3013    case '{':3014    case '\\':3015      break;3016    case ')':3017      if (__open_count_ == 0) {3018        __push_char(*__first);3019        ++__first;3020      }3021      break;3022    default:3023      __push_char(*__first);3024      ++__first;3025      break;3026    }3027  }3028  return __first;3029}3030 3031template <class _CharT, class _Traits>3032template <class _ForwardIterator>3033_ForwardIterator basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last) {3034  if (__first != __last) {3035    _ForwardIterator __temp = std::next(__first);3036    if (__temp != __last) {3037      if (*__first == '\\') {3038        switch (*__temp) {3039        case '^':3040        case '.':3041        case '*':3042        case '[':3043        case '$':3044        case '\\':3045          __push_char(*__temp);3046          __first = ++__temp;3047          break;3048        }3049      }3050    }3051  }3052  return __first;3053}3054 3055template <class _CharT, class _Traits>3056template <class _ForwardIterator>3057_ForwardIterator3058basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last) {3059  if (__first != __last) {3060    _ForwardIterator __temp = std::next(__first);3061    if (__temp != __last) {3062      if (*__first == '\\') {3063        switch (*__temp) {3064        case '^':3065        case '.':3066        case '*':3067        case '[':3068        case '$':3069        case '\\':3070        case '(':3071        case ')':3072        case '|':3073        case '+':3074        case '?':3075        case '{':3076        case '}':3077          __push_char(*__temp);3078          __first = ++__temp;3079          break;3080        default:3081          if (__get_grammar(__flags_) == awk)3082            __first = __parse_awk_escape(++__first, __last);3083          else if (__test_back_ref(*__temp))3084            __first = ++__temp;3085          break;3086        }3087      }3088    }3089  }3090  return __first;3091}3092 3093template <class _CharT, class _Traits>3094template <class _ForwardIterator>3095_ForwardIterator basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(3096    _ForwardIterator __first,3097    _ForwardIterator __last,3098    __owns_one_state<_CharT>* __s,3099    unsigned __mexp_begin,3100    unsigned __mexp_end) {3101  if (__first != __last) {3102    if (*__first == '*') {3103      __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);3104      ++__first;3105    } else {3106      _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);3107      if (__temp != __first) {3108        int __min = 0;3109        __first   = __temp;3110        __temp    = __parse_DUP_COUNT(__first, __last, __min);3111        if (__temp == __first)3112          __throw_regex_error<regex_constants::error_badbrace>();3113        __first = __temp;3114        if (__first == __last)3115          __throw_regex_error<regex_constants::error_brace>();3116        if (*__first != ',') {3117          __temp = __parse_Back_close_brace(__first, __last);3118          if (__temp == __first)3119            __throw_regex_error<regex_constants::error_brace>();3120          __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, true);3121          __first = __temp;3122        } else {3123          ++__first; // consume ','3124          int __max = -1;3125          __first   = __parse_DUP_COUNT(__first, __last, __max);3126          __temp    = __parse_Back_close_brace(__first, __last);3127          if (__temp == __first)3128            __throw_regex_error<regex_constants::error_brace>();3129          if (__max == -1)3130            __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);3131          else {3132            if (__max < __min)3133              __throw_regex_error<regex_constants::error_badbrace>();3134            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, true);3135          }3136          __first = __temp;3137        }3138      }3139    }3140  }3141  return __first;3142}3143 3144template <class _CharT, class _Traits>3145template <class _ForwardIterator>3146_ForwardIterator basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(3147    _ForwardIterator __first,3148    _ForwardIterator __last,3149    __owns_one_state<_CharT>* __s,3150    unsigned __mexp_begin,3151    unsigned __mexp_end) {3152  if (__first != __last) {3153    unsigned __grammar = __get_grammar(__flags_);3154    switch (*__first) {3155    case '*':3156      ++__first;3157      if (__grammar == ECMAScript && __first != __last && *__first == '?') {3158        ++__first;3159        __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);3160      } else3161        __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);3162      break;3163    case '+':3164      ++__first;3165      if (__grammar == ECMAScript && __first != __last && *__first == '?') {3166        ++__first;3167        __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);3168      } else3169        __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);3170      break;3171    case '?':3172      ++__first;3173      if (__grammar == ECMAScript && __first != __last && *__first == '?') {3174        ++__first;3175        __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);3176      } else3177        __push_loop(0, 1, __s, __mexp_begin, __mexp_end);3178      break;3179    case '{': {3180      int __min;3181      _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);3182      if (__temp == __first)3183        __throw_regex_error<regex_constants::error_badbrace>();3184      __first = __temp;3185      if (__first == __last)3186        __throw_regex_error<regex_constants::error_brace>();3187      switch (*__first) {3188      case '}':3189        ++__first;3190        if (__grammar == ECMAScript && __first != __last && *__first == '?') {3191          ++__first;3192          __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);3193        } else3194          __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);3195        break;3196      case ',':3197        ++__first;3198        if (__first == __last)3199          __throw_regex_error<regex_constants::error_badbrace>();3200        if (*__first == '}') {3201          ++__first;3202          if (__grammar == ECMAScript && __first != __last && *__first == '?') {3203            ++__first;3204            __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);3205          } else3206            __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);3207        } else {3208          int __max = -1;3209          __temp    = __parse_DUP_COUNT(__first, __last, __max);3210          if (__temp == __first)3211            __throw_regex_error<regex_constants::error_brace>();3212          __first = __temp;3213          if (__first == __last || *__first != '}')3214            __throw_regex_error<regex_constants::error_brace>();3215          ++__first;3216          if (__max < __min)3217            __throw_regex_error<regex_constants::error_badbrace>();3218          if (__grammar == ECMAScript && __first != __last && *__first == '?') {3219            ++__first;3220            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);3221          } else3222            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);3223        }3224        break;3225      default:3226        __throw_regex_error<regex_constants::error_badbrace>();3227      }3228    } break;3229    }3230  }3231  return __first;3232}3233 3234template <class _CharT, class _Traits>3235template <class _ForwardIterator>3236_ForwardIterator3237basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last) {3238  if (__first != __last && *__first == '[') {3239    ++__first;3240    if (__first == __last)3241      __throw_regex_error<regex_constants::error_brack>();3242    bool __negate = false;3243    if (*__first == '^') {3244      ++__first;3245      __negate = true;3246    }3247    __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);3248    // __ml owned by *this3249    if (__first == __last)3250      __throw_regex_error<regex_constants::error_brack>();3251    if (__get_grammar(__flags_) != ECMAScript && *__first == ']') {3252      __ml->__add_char(']');3253      ++__first;3254    }3255    __first = __parse_follow_list(__first, __last, __ml);3256    if (__first == __last)3257      __throw_regex_error<regex_constants::error_brack>();3258    if (*__first == '-') {3259      __ml->__add_char('-');3260      ++__first;3261    }3262    if (__first == __last || *__first != ']')3263      __throw_regex_error<regex_constants::error_brack>();3264    ++__first;3265  }3266  return __first;3267}3268 3269template <class _CharT, class _Traits>3270template <class _ForwardIterator>3271_ForwardIterator basic_regex<_CharT, _Traits>::__parse_follow_list(3272    _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {3273  if (__first != __last) {3274    while (true) {3275      _ForwardIterator __temp = __parse_expression_term(__first, __last, __ml);3276      if (__temp == __first)3277        break;3278      __first = __temp;3279    }3280  }3281  return __first;3282}3283 3284template <class _CharT, class _Traits>3285template <class _ForwardIterator>3286_ForwardIterator basic_regex<_CharT, _Traits>::__parse_expression_term(3287    _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {3288  if (__first != __last && *__first != ']') {3289    _ForwardIterator __temp = std::next(__first);3290    basic_string<_CharT> __start_range;3291    if (__temp != __last && *__first == '[') {3292      if (*__temp == '=')3293        return __parse_equivalence_class(++__temp, __last, __ml);3294      else if (*__temp == ':')3295        return __parse_character_class(++__temp, __last, __ml);3296      else if (*__temp == '.')3297        __first = __parse_collating_symbol(++__temp, __last, __start_range);3298    }3299    unsigned __grammar = __get_grammar(__flags_);3300    if (__start_range.empty()) {3301      if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\') {3302        if (__grammar == ECMAScript)3303          __first = __parse_class_escape(++__first, __last, __start_range, __ml);3304        else3305          __first = __parse_awk_escape(++__first, __last, &__start_range);3306      } else {3307        __start_range = *__first;3308        ++__first;3309      }3310    }3311    if (__first != __last && *__first != ']') {3312      __temp = std::next(__first);3313      if (__temp != __last && *__first == '-' && *__temp != ']') {3314        // parse a range3315        basic_string<_CharT> __end_range;3316        __first = __temp;3317        ++__temp;3318        if (__temp != __last && *__first == '[' && *__temp == '.')3319          __first = __parse_collating_symbol(++__temp, __last, __end_range);3320        else {3321          if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\') {3322            if (__grammar == ECMAScript)3323              __first = __parse_class_escape(++__first, __last, __end_range, __ml);3324            else3325              __first = __parse_awk_escape(++__first, __last, &__end_range);3326          } else {3327            __end_range = *__first;3328            ++__first;3329          }3330        }3331        __ml->__add_range(std::move(__start_range), std::move(__end_range));3332      } else if (!__start_range.empty()) {3333        if (__start_range.size() == 1)3334          __ml->__add_char(__start_range[0]);3335        else3336          __ml->__add_digraph(__start_range[0], __start_range[1]);3337      }3338    } else if (!__start_range.empty()) {3339      if (__start_range.size() == 1)3340        __ml->__add_char(__start_range[0]);3341      else3342        __ml->__add_digraph(__start_range[0], __start_range[1]);3343    }3344  }3345  return __first;3346}3347 3348template <class _CharT, class _Traits>3349template <class _ForwardIterator>3350_ForwardIterator basic_regex<_CharT, _Traits>::__parse_class_escape(3351    _ForwardIterator __first,3352    _ForwardIterator __last,3353    basic_string<_CharT>& __str,3354    __bracket_expression<_CharT, _Traits>* __ml) {3355  if (__first == __last)3356    __throw_regex_error<regex_constants::error_escape>();3357  switch (*__first) {3358  case 0:3359    __str = *__first;3360    return ++__first;3361  case 'b':3362    __str = _CharT(8);3363    return ++__first;3364  case 'd':3365    __ml->__add_class(ctype_base::digit);3366    return ++__first;3367  case 'D':3368    __ml->__add_neg_class(ctype_base::digit);3369    return ++__first;3370  case 's':3371    __ml->__add_class(ctype_base::space);3372    return ++__first;3373  case 'S':3374    __ml->__add_neg_class(ctype_base::space);3375    return ++__first;3376  case 'w':3377    __ml->__add_class(ctype_base::alnum);3378    __ml->__add_char('_');3379    return ++__first;3380  case 'W':3381    __ml->__add_neg_class(ctype_base::alnum);3382    __ml->__add_neg_char('_');3383    return ++__first;3384  }3385  __first = __parse_character_escape(__first, __last, &__str);3386  return __first;3387}3388 3389template <class _CharT, class _Traits>3390template <class _ForwardIterator>3391_ForwardIterator basic_regex<_CharT, _Traits>::__parse_awk_escape(3392    _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str) {3393  if (__first == __last)3394    __throw_regex_error<regex_constants::error_escape>();3395  switch (*__first) {3396  case '\\':3397  case '"':3398  case '/':3399    if (__str)3400      *__str = *__first;3401    else3402      __push_char(*__first);3403    return ++__first;3404  case 'a':3405    if (__str)3406      *__str = _CharT(7);3407    else3408      __push_char(_CharT(7));3409    return ++__first;3410  case 'b':3411    if (__str)3412      *__str = _CharT(8);3413    else3414      __push_char(_CharT(8));3415    return ++__first;3416  case 'f':3417    if (__str)3418      *__str = _CharT(0xC);3419    else3420      __push_char(_CharT(0xC));3421    return ++__first;3422  case 'n':3423    if (__str)3424      *__str = _CharT(0xA);3425    else3426      __push_char(_CharT(0xA));3427    return ++__first;3428  case 'r':3429    if (__str)3430      *__str = _CharT(0xD);3431    else3432      __push_char(_CharT(0xD));3433    return ++__first;3434  case 't':3435    if (__str)3436      *__str = _CharT(0x9);3437    else3438      __push_char(_CharT(0x9));3439    return ++__first;3440  case 'v':3441    if (__str)3442      *__str = _CharT(0xB);3443    else3444      __push_char(_CharT(0xB));3445    return ++__first;3446  }3447  if ('0' <= *__first && *__first <= '7') {3448    unsigned __val = *__first - '0';3449    if (++__first != __last && ('0' <= *__first && *__first <= '7')) {3450      __val = 8 * __val + *__first - '0';3451      if (++__first != __last && ('0' <= *__first && *__first <= '7'))3452        __val = 8 * __val + *__first++ - '0';3453    }3454    if (__str)3455      *__str = _CharT(__val);3456    else3457      __push_char(_CharT(__val));3458  } else3459    __throw_regex_error<regex_constants::error_escape>();3460  return __first;3461}3462 3463template <class _CharT, class _Traits>3464template <class _ForwardIterator>3465_ForwardIterator basic_regex<_CharT, _Traits>::__parse_equivalence_class(3466    _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {3467  // Found [=3468  //   This means =] must exist3469  value_type __equal_close[2] = {'=', ']'};3470  _ForwardIterator __temp     = std::search(__first, __last, __equal_close, __equal_close + 2);3471  if (__temp == __last)3472    __throw_regex_error<regex_constants::error_brack>();3473  // [__first, __temp) contains all text in [= ... =]3474  string_type __collate_name = __traits_.lookup_collatename(__first, __temp);3475  if (__collate_name.empty())3476    __throw_regex_error<regex_constants::error_collate>();3477  string_type __equiv_name = __traits_.transform_primary(__collate_name.begin(), __collate_name.end());3478  if (!__equiv_name.empty())3479    __ml->__add_equivalence(__equiv_name);3480  else {3481    switch (__collate_name.size()) {3482    case 1:3483      __ml->__add_char(__collate_name[0]);3484      break;3485    case 2:3486      __ml->__add_digraph(__collate_name[0], __collate_name[1]);3487      break;3488    default:3489      __throw_regex_error<regex_constants::error_collate>();3490    }3491  }3492  __first = std::next(__temp, 2);3493  return __first;3494}3495 3496template <class _CharT, class _Traits>3497template <class _ForwardIterator>3498_ForwardIterator basic_regex<_CharT, _Traits>::__parse_character_class(3499    _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {3500  // Found [:3501  //   This means :] must exist3502  value_type __colon_close[2] = {':', ']'};3503  _ForwardIterator __temp     = std::search(__first, __last, __colon_close, __colon_close + 2);3504  if (__temp == __last)3505    __throw_regex_error<regex_constants::error_brack>();3506  // [__first, __temp) contains all text in [: ... :]3507  typedef typename _Traits::char_class_type char_class_type;3508  char_class_type __class_type = __traits_.lookup_classname(__first, __temp, __flags_ & icase);3509  if (__class_type == 0)3510    __throw_regex_error<regex_constants::error_ctype>();3511  __ml->__add_class(__class_type);3512  __first = std::next(__temp, 2);3513  return __first;3514}3515 3516template <class _CharT, class _Traits>3517template <class _ForwardIterator>3518_ForwardIterator basic_regex<_CharT, _Traits>::__parse_collating_symbol(3519    _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>& __col_sym) {3520  // Found [.3521  //   This means .] must exist3522  value_type __dot_close[2] = {'.', ']'};3523  _ForwardIterator __temp   = std::search(__first, __last, __dot_close, __dot_close + 2);3524  if (__temp == __last)3525    __throw_regex_error<regex_constants::error_brack>();3526  // [__first, __temp) contains all text in [. ... .]3527  __col_sym = __traits_.lookup_collatename(__first, __temp);3528  switch (__col_sym.size()) {3529  case 1:3530  case 2:3531    break;3532  default:3533    __throw_regex_error<regex_constants::error_collate>();3534  }3535  __first = std::next(__temp, 2);3536  return __first;3537}3538 3539template <class _CharT, class _Traits>3540template <class _ForwardIterator>3541_ForwardIterator3542basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c) {3543  if (__first != __last) {3544    int __val = __traits_.value(*__first, 10);3545    if (__val != -1) {3546      __c = __val;3547      for (++__first; __first != __last && (__val = __traits_.value(*__first, 10)) != -1; ++__first) {3548        if (__c >= numeric_limits<int>::max() / 10)3549          __throw_regex_error<regex_constants::error_badbrace>();3550        __c *= 10;3551        __c += __val;3552      }3553    }3554  }3555  return __first;3556}3557 3558template <class _CharT, class _Traits>3559template <class _ForwardIterator>3560_ForwardIterator basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last) {3561  __owns_one_state<_CharT>* __sa = __end_;3562  _ForwardIterator __temp        = __parse_alternative(__first, __last);3563  if (__temp == __first)3564    __push_empty();3565  __first = __temp;3566  while (__first != __last && *__first == '|') {3567    __owns_one_state<_CharT>* __sb = __end_;3568    __temp                         = __parse_alternative(++__first, __last);3569    if (__temp == __first)3570      __push_empty();3571    __push_alternation(__sa, __sb);3572    __first = __temp;3573  }3574  return __first;3575}3576 3577template <class _CharT, class _Traits>3578template <class _ForwardIterator>3579_ForwardIterator basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first, _ForwardIterator __last) {3580  while (true) {3581    _ForwardIterator __temp = __parse_term(__first, __last);3582    if (__temp == __first)3583      break;3584    __first = __temp;3585  }3586  return __first;3587}3588 3589template <class _CharT, class _Traits>3590template <class _ForwardIterator>3591_ForwardIterator basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first, _ForwardIterator __last) {3592  _ForwardIterator __temp = __parse_assertion(__first, __last);3593  if (__temp == __first) {3594    __owns_one_state<_CharT>* __e = __end_;3595    unsigned __mexp_begin         = __marked_count_;3596    __temp                        = __parse_atom(__first, __last);3597    if (__temp != __first)3598      __first = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);3599  } else3600    __first = __temp;3601  return __first;3602}3603 3604template <class _CharT, class _Traits>3605template <class _ForwardIterator>3606_ForwardIterator basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first, _ForwardIterator __last) {3607  if (__first != __last) {3608    switch (*__first) {3609    case '^':3610      __push_l_anchor();3611      ++__first;3612      break;3613    case '$':3614      __push_r_anchor();3615      ++__first;3616      break;3617    case '\\': {3618      _ForwardIterator __temp = std::next(__first);3619      if (__temp != __last) {3620        if (*__temp == 'b') {3621          __push_word_boundary(false);3622          __first = ++__temp;3623        } else if (*__temp == 'B') {3624          __push_word_boundary(true);3625          __first = ++__temp;3626        }3627      }3628    } break;3629    case '(': {3630      _ForwardIterator __temp = std::next(__first);3631      if (__temp != __last && *__temp == '?') {3632        if (++__temp != __last) {3633          switch (*__temp) {3634          case '=': {3635            basic_regex __exp;3636            __exp.__flags_  = __flags_;3637            __temp          = __exp.__parse(++__temp, __last);3638            unsigned __mexp = __exp.__marked_count_;3639            __push_lookahead(std::move(__exp), false, __marked_count_);3640            __marked_count_ += __mexp;3641            if (__temp == __last || *__temp != ')')3642              __throw_regex_error<regex_constants::error_paren>();3643            __first = ++__temp;3644          } break;3645          case '!': {3646            basic_regex __exp;3647            __exp.__flags_  = __flags_;3648            __temp          = __exp.__parse(++__temp, __last);3649            unsigned __mexp = __exp.__marked_count_;3650            __push_lookahead(std::move(__exp), true, __marked_count_);3651            __marked_count_ += __mexp;3652            if (__temp == __last || *__temp != ')')3653              __throw_regex_error<regex_constants::error_paren>();3654            __first = ++__temp;3655          } break;3656          }3657        }3658      }3659    } break;3660    }3661  }3662  return __first;3663}3664 3665template <class _CharT, class _Traits>3666template <class _ForwardIterator>3667_ForwardIterator basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first, _ForwardIterator __last) {3668  if (__first != __last) {3669    switch (*__first) {3670    case '.':3671      __push_match_any_but_newline();3672      ++__first;3673      break;3674    case '\\':3675      __first = __parse_atom_escape(__first, __last);3676      break;3677    case '[':3678      __first = __parse_bracket_expression(__first, __last);3679      break;3680    case '(': {3681      ++__first;3682      if (__first == __last)3683        __throw_regex_error<regex_constants::error_paren>();3684      _ForwardIterator __temp = std::next(__first);3685      if (__temp != __last && *__first == '?' && *__temp == ':') {3686        ++__open_count_;3687        __first = __parse_ecma_exp(++__temp, __last);3688        if (__first == __last || *__first != ')')3689          __throw_regex_error<regex_constants::error_paren>();3690        --__open_count_;3691        ++__first;3692      } else {3693        __push_begin_marked_subexpression();3694        unsigned __temp_count = __marked_count_;3695        ++__open_count_;3696        __first = __parse_ecma_exp(__first, __last);3697        if (__first == __last || *__first != ')')3698          __throw_regex_error<regex_constants::error_paren>();3699        __push_end_marked_subexpression(__temp_count);3700        --__open_count_;3701        ++__first;3702      }3703    } break;3704    case '*':3705    case '+':3706    case '?':3707    case '{':3708      __throw_regex_error<regex_constants::error_badrepeat>();3709      break;3710    default:3711      __first = __parse_pattern_character(__first, __last);3712      break;3713    }3714  }3715  return __first;3716}3717 3718template <class _CharT, class _Traits>3719template <class _ForwardIterator>3720_ForwardIterator basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last) {3721  if (__first != __last && *__first == '\\') {3722    _ForwardIterator __t1 = std::next(__first);3723    if (__t1 == __last)3724      __throw_regex_error<regex_constants::error_escape>();3725 3726    _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);3727    if (__t2 != __t1)3728      __first = __t2;3729    else {3730      __t2 = __parse_character_class_escape(__t1, __last);3731      if (__t2 != __t1)3732        __first = __t2;3733      else {3734        __t2 = __parse_character_escape(__t1, __last);3735        if (__t2 != __t1)3736          __first = __t2;3737      }3738    }3739  }3740  return __first;3741}3742 3743template <class _CharT, class _Traits>3744template <class _ForwardIterator>3745_ForwardIterator3746basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last) {3747  if (__first != __last) {3748    if (*__first == '0') {3749      __push_char(_CharT());3750      ++__first;3751    } else if ('1' <= *__first && *__first <= '9') {3752      unsigned __v = *__first - '0';3753      for (++__first; __first != __last && '0' <= *__first && *__first <= '9'; ++__first) {3754        if (__v >= numeric_limits<unsigned>::max() / 10)3755          __throw_regex_error<regex_constants::error_backref>();3756        __v = 10 * __v + *__first - '0';3757      }3758      if (__v == 0 || __v > mark_count())3759        __throw_regex_error<regex_constants::error_backref>();3760      __push_back_ref(__v);3761    }3762  }3763  return __first;3764}3765 3766template <class _CharT, class _Traits>3767template <class _ForwardIterator>3768_ForwardIterator3769basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last) {3770  if (__first != __last) {3771    __bracket_expression<_CharT, _Traits>* __ml;3772    switch (*__first) {3773    case 'd':3774      __ml = __start_matching_list(false);3775      __ml->__add_class(ctype_base::digit);3776      ++__first;3777      break;3778    case 'D':3779      __ml = __start_matching_list(true);3780      __ml->__add_class(ctype_base::digit);3781      ++__first;3782      break;3783    case 's':3784      __ml = __start_matching_list(false);3785      __ml->__add_class(ctype_base::space);3786      ++__first;3787      break;3788    case 'S':3789      __ml = __start_matching_list(true);3790      __ml->__add_class(ctype_base::space);3791      ++__first;3792      break;3793    case 'w':3794      __ml = __start_matching_list(false);3795      __ml->__add_class(ctype_base::alnum);3796      __ml->__add_char('_');3797      ++__first;3798      break;3799    case 'W':3800      __ml = __start_matching_list(true);3801      __ml->__add_class(ctype_base::alnum);3802      __ml->__add_char('_');3803      ++__first;3804      break;3805    }3806  }3807  return __first;3808}3809 3810template <class _CharT, class _Traits>3811template <class _ForwardIterator>3812_ForwardIterator basic_regex<_CharT, _Traits>::__parse_character_escape(3813    _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str) {3814  if (__first != __last) {3815    _ForwardIterator __t;3816    unsigned __sum = 0;3817    int __hd;3818    switch (*__first) {3819    case 'f':3820      if (__str)3821        *__str = _CharT(0xC);3822      else3823        __push_char(_CharT(0xC));3824      ++__first;3825      break;3826    case 'n':3827      if (__str)3828        *__str = _CharT(0xA);3829      else3830        __push_char(_CharT(0xA));3831      ++__first;3832      break;3833    case 'r':3834      if (__str)3835        *__str = _CharT(0xD);3836      else3837        __push_char(_CharT(0xD));3838      ++__first;3839      break;3840    case 't':3841      if (__str)3842        *__str = _CharT(0x9);3843      else3844        __push_char(_CharT(0x9));3845      ++__first;3846      break;3847    case 'v':3848      if (__str)3849        *__str = _CharT(0xB);3850      else3851        __push_char(_CharT(0xB));3852      ++__first;3853      break;3854    case 'c':3855      if ((__t = std::next(__first)) != __last) {3856        if (('A' <= *__t && *__t <= 'Z') || ('a' <= *__t && *__t <= 'z')) {3857          if (__str)3858            *__str = _CharT(*__t % 32);3859          else3860            __push_char(_CharT(*__t % 32));3861          __first = ++__t;3862        } else3863          __throw_regex_error<regex_constants::error_escape>();3864      } else3865        __throw_regex_error<regex_constants::error_escape>();3866      break;3867    case 'u':3868      ++__first;3869      if (__first == __last)3870        __throw_regex_error<regex_constants::error_escape>();3871      __hd = __traits_.value(*__first, 16);3872      if (__hd == -1)3873        __throw_regex_error<regex_constants::error_escape>();3874      __sum = 16 * __sum + static_cast<unsigned>(__hd);3875      ++__first;3876      if (__first == __last)3877        __throw_regex_error<regex_constants::error_escape>();3878      __hd = __traits_.value(*__first, 16);3879      if (__hd == -1)3880        __throw_regex_error<regex_constants::error_escape>();3881      __sum = 16 * __sum + static_cast<unsigned>(__hd);3882      // fallthrough3883    case 'x':3884      ++__first;3885      if (__first == __last)3886        __throw_regex_error<regex_constants::error_escape>();3887      __hd = __traits_.value(*__first, 16);3888      if (__hd == -1)3889        __throw_regex_error<regex_constants::error_escape>();3890      __sum = 16 * __sum + static_cast<unsigned>(__hd);3891      ++__first;3892      if (__first == __last)3893        __throw_regex_error<regex_constants::error_escape>();3894      __hd = __traits_.value(*__first, 16);3895      if (__hd == -1)3896        __throw_regex_error<regex_constants::error_escape>();3897      __sum = 16 * __sum + static_cast<unsigned>(__hd);3898      if (__str)3899        *__str = _CharT(__sum);3900      else3901        __push_char(_CharT(__sum));3902      ++__first;3903      break;3904    case '0':3905      if (__str)3906        *__str = _CharT(0);3907      else3908        __push_char(_CharT(0));3909      ++__first;3910      break;3911    default:3912      if (!__traits_.isctype(*__first, ctype_base::alnum)) {3913        if (__str)3914          *__str = *__first;3915        else3916          __push_char(*__first);3917        ++__first;3918      } else3919        __throw_regex_error<regex_constants::error_escape>();3920      break;3921    }3922  }3923  return __first;3924}3925 3926template <class _CharT, class _Traits>3927template <class _ForwardIterator>3928_ForwardIterator3929basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last) {3930  if (__first != __last) {3931    switch (*__first) {3932    case '^':3933    case '$':3934    case '\\':3935    case '.':3936    case '*':3937    case '+':3938    case '?':3939    case '(':3940    case ')':3941    case '[':3942    case ']':3943    case '{':3944    case '}':3945    case '|':3946      break;3947    default:3948      __push_char(*__first);3949      ++__first;3950      break;3951    }3952  }3953  return __first;3954}3955 3956template <class _CharT, class _Traits>3957template <class _ForwardIterator>3958_ForwardIterator basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first, _ForwardIterator __last) {3959  __owns_one_state<_CharT>* __sa = __end_;3960  _ForwardIterator __t1          = std::find(__first, __last, _CharT('\n'));3961  if (__t1 != __first)3962    __parse_basic_reg_exp(__first, __t1);3963  else3964    __push_empty();3965  __first = __t1;3966  if (__first != __last)3967    ++__first;3968  while (__first != __last) {3969    __t1                           = std::find(__first, __last, _CharT('\n'));3970    __owns_one_state<_CharT>* __sb = __end_;3971    if (__t1 != __first)3972      __parse_basic_reg_exp(__first, __t1);3973    else3974      __push_empty();3975    __push_alternation(__sa, __sb);3976    __first = __t1;3977    if (__first != __last)3978      ++__first;3979  }3980  return __first;3981}3982 3983template <class _CharT, class _Traits>3984template <class _ForwardIterator>3985_ForwardIterator basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first, _ForwardIterator __last) {3986  __owns_one_state<_CharT>* __sa = __end_;3987  _ForwardIterator __t1          = std::find(__first, __last, _CharT('\n'));3988  if (__t1 != __first)3989    __parse_extended_reg_exp(__first, __t1);3990  else3991    __push_empty();3992  __first = __t1;3993  if (__first != __last)3994    ++__first;3995  while (__first != __last) {3996    __t1                           = std::find(__first, __last, _CharT('\n'));3997    __owns_one_state<_CharT>* __sb = __end_;3998    if (__t1 != __first)3999      __parse_extended_reg_exp(__first, __t1);4000    else4001      __push_empty();4002    __push_alternation(__sa, __sb);4003    __first = __t1;4004    if (__first != __last)4005      ++__first;4006  }4007  return __first;4008}4009 4010template <class _CharT, class _Traits>4011bool basic_regex<_CharT, _Traits>::__test_back_ref(_CharT __c) {4012  unsigned __val = __traits_.value(__c, 10);4013  if (__val >= 1 && __val <= 9) {4014    if (__val > mark_count())4015      __throw_regex_error<regex_constants::error_backref>();4016    __push_back_ref(__val);4017    return true;4018  }4019 4020  return false;4021}4022 4023template <class _CharT, class _Traits>4024void basic_regex<_CharT, _Traits>::__push_loop(4025    size_t __min, size_t __max, __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end, bool __greedy) {4026  unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));4027  __end_->first() = nullptr;4028  unique_ptr<__loop<_CharT> > __e2(4029      new __loop<_CharT>(__loop_count_, __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy, __min, __max));4030  __s->first() = nullptr;4031  __e1.release();4032  __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());4033  __end_          = __e2->second();4034  __s->first()    = __e2.release();4035  ++__loop_count_;4036}4037 4038template <class _CharT, class _Traits>4039void basic_regex<_CharT, _Traits>::__push_char(value_type __c) {4040  if (flags() & icase)4041    __end_->first() = new __match_char_icase<_CharT, _Traits>(__traits_, __c, __end_->first());4042  else if (flags() & collate)4043    __end_->first() = new __match_char_collate<_CharT, _Traits>(__traits_, __c, __end_->first());4044  else4045    __end_->first() = new __match_char<_CharT>(__c, __end_->first());4046  __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());4047}4048 4049template <class _CharT, class _Traits>4050void basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression() {4051  if (!(__flags_ & nosubs)) {4052    __end_->first() = new __begin_marked_subexpression<_CharT>(++__marked_count_, __end_->first());4053    __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4054  }4055}4056 4057template <class _CharT, class _Traits>4058void basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub) {4059  if (!(__flags_ & nosubs)) {4060    __end_->first() = new __end_marked_subexpression<_CharT>(__sub, __end_->first());4061    __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4062  }4063}4064 4065template <class _CharT, class _Traits>4066void basic_regex<_CharT, _Traits>::__push_l_anchor() {4067  __end_->first() = new __l_anchor_multiline<_CharT>(__use_multiline(), __end_->first());4068  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4069}4070 4071template <class _CharT, class _Traits>4072void basic_regex<_CharT, _Traits>::__push_r_anchor() {4073  __end_->first() = new __r_anchor_multiline<_CharT>(__use_multiline(), __end_->first());4074  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4075}4076 4077template <class _CharT, class _Traits>4078void basic_regex<_CharT, _Traits>::__push_match_any() {4079  __end_->first() = new __match_any<_CharT>(__end_->first());4080  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4081}4082 4083template <class _CharT, class _Traits>4084void basic_regex<_CharT, _Traits>::__push_match_any_but_newline() {4085  __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());4086  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4087}4088 4089template <class _CharT, class _Traits>4090void basic_regex<_CharT, _Traits>::__push_empty() {4091  __end_->first() = new __empty_state<_CharT>(__end_->first());4092  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4093}4094 4095template <class _CharT, class _Traits>4096void basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert) {4097  __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert, __end_->first());4098  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4099}4100 4101template <class _CharT, class _Traits>4102void basic_regex<_CharT, _Traits>::__push_back_ref(int __i) {4103  if (flags() & icase)4104    __end_->first() = new __back_ref_icase<_CharT, _Traits>(__traits_, __i, __end_->first());4105  else if (flags() & collate)4106    __end_->first() = new __back_ref_collate<_CharT, _Traits>(__traits_, __i, __end_->first());4107  else4108    __end_->first() = new __back_ref<_CharT>(__i, __end_->first());4109  __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());4110}4111 4112template <class _CharT, class _Traits>4113void basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa, __owns_one_state<_CharT>* __ea) {4114  __sa->first() = new __alternate<_CharT>(4115      static_cast<__owns_one_state<_CharT>*>(__sa->first()), static_cast<__owns_one_state<_CharT>*>(__ea->first()));4116  __ea->first()   = nullptr;4117  __ea->first()   = new __empty_state<_CharT>(__end_->first());4118  __end_->first() = nullptr;4119  __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());4120  __end_          = static_cast<__owns_one_state<_CharT>*>(__ea->first());4121}4122 4123template <class _CharT, class _Traits>4124__bracket_expression<_CharT, _Traits>* basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate) {4125  __bracket_expression<_CharT, _Traits>* __r = new __bracket_expression<_CharT, _Traits>(4126      __traits_, __end_->first(), __negate, __flags_ & icase, __flags_ & collate);4127  __end_->first() = __r;4128  __end_          = __r;4129  return __r;4130}4131 4132template <class _CharT, class _Traits>4133void basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp, bool __invert, unsigned __mexp) {4134  __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert, __end_->first(), __mexp);4135  __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());4136}4137 4138// sub_match4139 4140typedef sub_match<const char*> csub_match;4141typedef sub_match<string::const_iterator> ssub_match;4142#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS4143typedef sub_match<const wchar_t*> wcsub_match;4144typedef sub_match<wstring::const_iterator> wssub_match;4145#endif4146 4147template <class _BidirectionalIterator>4148class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(csub_match)4149    _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcsub_match)) _LIBCPP_PREFERRED_NAME(ssub_match)4150        _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wssub_match)) sub_match4151    : public pair<_BidirectionalIterator, _BidirectionalIterator> {4152public:4153  typedef _BidirectionalIterator iterator;4154  typedef typename iterator_traits<iterator>::value_type value_type;4155  typedef typename iterator_traits<iterator>::difference_type difference_type;4156  typedef basic_string<value_type> string_type;4157 4158  bool matched;4159 4160  _LIBCPP_HIDE_FROM_ABI sub_match() : matched() {}4161 4162  _LIBCPP_HIDE_FROM_ABI difference_type length() const {4163    return matched ? std::distance(this->first, this->second) : 0;4164  }4165  _LIBCPP_HIDE_FROM_ABI string_type str() const {4166    return matched ? string_type(this->first, this->second) : string_type();4167  }4168  _LIBCPP_HIDE_FROM_ABI operator string_type() const { return str(); }4169 4170  _LIBCPP_HIDE_FROM_ABI int compare(const sub_match& __s) const { return str().compare(__s.str()); }4171  _LIBCPP_HIDE_FROM_ABI int compare(const string_type& __s) const { return str().compare(__s); }4172  _LIBCPP_HIDE_FROM_ABI int compare(const value_type* __s) const { return str().compare(__s); }4173 4174  _LIBCPP_HIDE_FROM_ABI void swap(sub_match& __s) {4175    this->pair<_BidirectionalIterator, _BidirectionalIterator>::swap(__s);4176    std::swap(matched, __s.matched);4177  }4178};4179 4180template <class _BiIter>4181inline _LIBCPP_HIDE_FROM_ABI bool operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4182  return __x.compare(__y) == 0;4183}4184 4185template <class _BiIter>4186inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4187  return !(__x == __y);4188}4189 4190template <class _BiIter>4191inline _LIBCPP_HIDE_FROM_ABI bool operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4192  return __x.compare(__y) < 0;4193}4194 4195template <class _BiIter>4196inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4197  return !(__y < __x);4198}4199 4200template <class _BiIter>4201inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4202  return !(__x < __y);4203}4204 4205template <class _BiIter>4206inline _LIBCPP_HIDE_FROM_ABI bool operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {4207  return __y < __x;4208}4209 4210template <class _BiIter, class _ST, class _SA>4211inline _LIBCPP_HIDE_FROM_ABI bool4212operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4213           const sub_match<_BiIter>& __y) {4214  return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;4215}4216 4217template <class _BiIter, class _ST, class _SA>4218inline _LIBCPP_HIDE_FROM_ABI bool4219operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4220           const sub_match<_BiIter>& __y) {4221  return !(__x == __y);4222}4223 4224template <class _BiIter, class _ST, class _SA>4225inline _LIBCPP_HIDE_FROM_ABI bool4226operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4227          const sub_match<_BiIter>& __y) {4228  return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;4229}4230 4231template <class _BiIter, class _ST, class _SA>4232inline _LIBCPP_HIDE_FROM_ABI bool4233operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4234          const sub_match<_BiIter>& __y) {4235  return __y < __x;4236}4237 4238template <class _BiIter, class _ST, class _SA>4239inline _LIBCPP_HIDE_FROM_ABI bool4240operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4241           const sub_match<_BiIter>& __y) {4242  return !(__x < __y);4243}4244 4245template <class _BiIter, class _ST, class _SA>4246inline _LIBCPP_HIDE_FROM_ABI bool4247operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,4248           const sub_match<_BiIter>& __y) {4249  return !(__y < __x);4250}4251 4252template <class _BiIter, class _ST, class _SA>4253inline _LIBCPP_HIDE_FROM_ABI bool4254operator==(const sub_match<_BiIter>& __x,4255           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4256  return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;4257}4258 4259template <class _BiIter, class _ST, class _SA>4260inline _LIBCPP_HIDE_FROM_ABI bool4261operator!=(const sub_match<_BiIter>& __x,4262           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4263  return !(__x == __y);4264}4265 4266template <class _BiIter, class _ST, class _SA>4267inline _LIBCPP_HIDE_FROM_ABI bool4268operator<(const sub_match<_BiIter>& __x,4269          const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4270  return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;4271}4272 4273template <class _BiIter, class _ST, class _SA>4274inline _LIBCPP_HIDE_FROM_ABI bool4275operator>(const sub_match<_BiIter>& __x,4276          const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4277  return __y < __x;4278}4279 4280template <class _BiIter, class _ST, class _SA>4281inline _LIBCPP_HIDE_FROM_ABI bool4282operator>=(const sub_match<_BiIter>& __x,4283           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4284  return !(__x < __y);4285}4286 4287template <class _BiIter, class _ST, class _SA>4288inline _LIBCPP_HIDE_FROM_ABI bool4289operator<=(const sub_match<_BiIter>& __x,4290           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {4291  return !(__y < __x);4292}4293 4294template <class _BiIter>4295inline _LIBCPP_HIDE_FROM_ABI bool4296operator==(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4297  return __y.compare(__x) == 0;4298}4299 4300template <class _BiIter>4301inline _LIBCPP_HIDE_FROM_ABI bool4302operator!=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4303  return !(__x == __y);4304}4305 4306template <class _BiIter>4307inline _LIBCPP_HIDE_FROM_ABI bool4308operator<(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4309  return __y.compare(__x) > 0;4310}4311 4312template <class _BiIter>4313inline _LIBCPP_HIDE_FROM_ABI bool4314operator>(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4315  return __y < __x;4316}4317 4318template <class _BiIter>4319inline _LIBCPP_HIDE_FROM_ABI bool4320operator>=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4321  return !(__x < __y);4322}4323 4324template <class _BiIter>4325inline _LIBCPP_HIDE_FROM_ABI bool4326operator<=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {4327  return !(__y < __x);4328}4329 4330template <class _BiIter>4331inline _LIBCPP_HIDE_FROM_ABI bool4332operator==(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4333  return __x.compare(__y) == 0;4334}4335 4336template <class _BiIter>4337inline _LIBCPP_HIDE_FROM_ABI bool4338operator!=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4339  return !(__x == __y);4340}4341 4342template <class _BiIter>4343inline _LIBCPP_HIDE_FROM_ABI bool4344operator<(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4345  return __x.compare(__y) < 0;4346}4347 4348template <class _BiIter>4349inline _LIBCPP_HIDE_FROM_ABI bool4350operator>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4351  return __y < __x;4352}4353 4354template <class _BiIter>4355inline _LIBCPP_HIDE_FROM_ABI bool4356operator>=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4357  return !(__x < __y);4358}4359 4360template <class _BiIter>4361inline _LIBCPP_HIDE_FROM_ABI bool4362operator<=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {4363  return !(__y < __x);4364}4365 4366template <class _BiIter>4367inline _LIBCPP_HIDE_FROM_ABI bool4368operator==(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4369  typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;4370  return __y.compare(string_type(1, __x)) == 0;4371}4372 4373template <class _BiIter>4374inline _LIBCPP_HIDE_FROM_ABI bool4375operator!=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4376  return !(__x == __y);4377}4378 4379template <class _BiIter>4380inline _LIBCPP_HIDE_FROM_ABI bool4381operator<(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4382  typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;4383  return __y.compare(string_type(1, __x)) > 0;4384}4385 4386template <class _BiIter>4387inline _LIBCPP_HIDE_FROM_ABI bool4388operator>(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4389  return __y < __x;4390}4391 4392template <class _BiIter>4393inline _LIBCPP_HIDE_FROM_ABI bool4394operator>=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4395  return !(__x < __y);4396}4397 4398template <class _BiIter>4399inline _LIBCPP_HIDE_FROM_ABI bool4400operator<=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {4401  return !(__y < __x);4402}4403 4404template <class _BiIter>4405inline _LIBCPP_HIDE_FROM_ABI bool4406operator==(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4407  typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;4408  return __x.compare(string_type(1, __y)) == 0;4409}4410 4411template <class _BiIter>4412inline _LIBCPP_HIDE_FROM_ABI bool4413operator!=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4414  return !(__x == __y);4415}4416 4417template <class _BiIter>4418inline _LIBCPP_HIDE_FROM_ABI bool4419operator<(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4420  typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;4421  return __x.compare(string_type(1, __y)) < 0;4422}4423 4424template <class _BiIter>4425inline _LIBCPP_HIDE_FROM_ABI bool4426operator>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4427  return __y < __x;4428}4429 4430template <class _BiIter>4431inline _LIBCPP_HIDE_FROM_ABI bool4432operator>=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4433  return !(__x < __y);4434}4435 4436template <class _BiIter>4437inline _LIBCPP_HIDE_FROM_ABI bool4438operator<=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {4439  return !(__y < __x);4440}4441 4442template <class _CharT, class _ST, class _BiIter>4443inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _ST>&4444operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m) {4445  return __os << __m.str();4446}4447 4448typedef match_results<const char*> cmatch;4449typedef match_results<string::const_iterator> smatch;4450#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS4451typedef match_results<const wchar_t*> wcmatch;4452typedef match_results<wstring::const_iterator> wsmatch;4453#endif4454 4455template <class _BidirectionalIterator, class _Allocator>4456class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cmatch) _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcmatch))4457    _LIBCPP_PREFERRED_NAME(smatch) _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsmatch)) match_results {4458public:4459  typedef _Allocator allocator_type;4460  typedef sub_match<_BidirectionalIterator> value_type;4461 4462private:4463  typedef vector<value_type, allocator_type> __container_type;4464 4465  __container_type __matches_;4466  value_type __unmatched_;4467  value_type __prefix_;4468  value_type __suffix_;4469  bool __ready_;4470 4471public:4472  _BidirectionalIterator __position_start_;4473  typedef const value_type& const_reference;4474  typedef value_type& reference;4475  typedef typename __container_type::const_iterator const_iterator;4476  typedef const_iterator iterator;4477  typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;4478  typedef typename allocator_traits<allocator_type>::size_type size_type;4479  typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;4480  typedef basic_string<char_type> string_type;4481 4482  // construct/copy/destroy:4483  explicit match_results(const allocator_type& __a = allocator_type());4484 4485  //    match_results(const match_results&) = default;4486  //    match_results& operator=(const match_results&) = default;4487  //    match_results(match_results&& __m) = default;4488  //    match_results& operator=(match_results&& __m) = default;4489  //    ~match_results() = default;4490 4491  _LIBCPP_HIDE_FROM_ABI bool ready() const { return __ready_; }4492 4493  // size:4494  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __matches_.size(); }4495  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __matches_.max_size(); }4496  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return size() == 0; }4497 4498  // element access:4499  _LIBCPP_HIDE_FROM_ABI difference_type length(size_type __sub = 0) const {4500    // If the match results are not ready, this will return `0`.4501    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::length() called when not ready");4502    return (*this)[__sub].length();4503  }4504  _LIBCPP_HIDE_FROM_ABI difference_type position(size_type __sub = 0) const {4505    // If the match results are not ready, this will return the result of subtracting two default-constructed iterators4506    // (which is typically a well-defined operation).4507    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::position() called when not ready");4508    return std::distance(__position_start_, (*this)[__sub].first);4509  }4510  _LIBCPP_HIDE_FROM_ABI string_type str(size_type __sub = 0) const {4511    // If the match results are not ready, this will return an empty string.4512    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::str() called when not ready");4513    return (*this)[__sub].str();4514  }4515  _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const {4516    // If the match results are not ready, this call will be equivalent to calling this function with `__n >= size()`,4517    // returning an empty subrange.4518    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::operator[]() called when not ready");4519    return __n < __matches_.size() ? __matches_[__n] : __unmatched_;4520  }4521 4522  _LIBCPP_HIDE_FROM_ABI const_reference prefix() const {4523    // If the match results are not ready, this will return a default-constructed empty `__suffix_`.4524    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::prefix() called when not ready");4525    return __prefix_;4526  }4527  _LIBCPP_HIDE_FROM_ABI const_reference suffix() const {4528    // If the match results are not ready, this will return a default-constructed empty `__suffix_`.4529    _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::suffix() called when not ready");4530    return __suffix_;4531  }4532 4533  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return empty() ? __matches_.end() : __matches_.begin(); }4534  _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __matches_.end(); }4535  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const { return empty() ? __matches_.end() : __matches_.begin(); }4536  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const { return __matches_.end(); }4537 4538  // format:4539  template <class _OutputIter>4540  _OutputIter format(_OutputIter __output_iter,4541                     const char_type* __fmt_first,4542                     const char_type* __fmt_last,4543                     regex_constants::match_flag_type __flags = regex_constants::format_default) const;4544  template <class _OutputIter, class _ST, class _SA>4545  _LIBCPP_HIDE_FROM_ABI _OutputIter4546  format(_OutputIter __output_iter,4547         const basic_string<char_type, _ST, _SA>& __fmt,4548         regex_constants::match_flag_type __flags = regex_constants::format_default) const {4549    return format(__output_iter, __fmt.data(), __fmt.data() + __fmt.size(), __flags);4550  }4551  template <class _ST, class _SA>4552  _LIBCPP_HIDE_FROM_ABI basic_string<char_type, _ST, _SA>4553  format(const basic_string<char_type, _ST, _SA>& __fmt,4554         regex_constants::match_flag_type __flags = regex_constants::format_default) const {4555    basic_string<char_type, _ST, _SA> __r;4556    format(std::back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(), __flags);4557    return __r;4558  }4559  _LIBCPP_HIDE_FROM_ABI string_type4560  format(const char_type* __fmt, regex_constants::match_flag_type __flags = regex_constants::format_default) const {4561    string_type __r;4562    format(std::back_inserter(__r), __fmt, __fmt + char_traits<char_type>::length(__fmt), __flags);4563    return __r;4564  }4565 4566  // allocator:4567  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return __matches_.get_allocator(); }4568 4569  // swap:4570  void swap(match_results& __m);4571 4572  template <class _Bp, class _Ap>4573  _LIBCPP_HIDE_FROM_ABI void4574  __assign(_BidirectionalIterator __f,4575           _BidirectionalIterator __l,4576           const match_results<_Bp, _Ap>& __m,4577           bool __no_update_pos) {4578    _Bp __mf = __m.prefix().first;4579    __matches_.resize(__m.size());4580    for (size_type __i = 0; __i < __matches_.size(); ++__i) {4581      __matches_[__i].first   = std::next(__f, std::distance(__mf, __m[__i].first));4582      __matches_[__i].second  = std::next(__f, std::distance(__mf, __m[__i].second));4583      __matches_[__i].matched = __m[__i].matched;4584    }4585    __unmatched_.first   = __l;4586    __unmatched_.second  = __l;4587    __unmatched_.matched = false;4588    __prefix_.first      = std::next(__f, std::distance(__mf, __m.prefix().first));4589    __prefix_.second     = std::next(__f, std::distance(__mf, __m.prefix().second));4590    __prefix_.matched    = __m.prefix().matched;4591    __suffix_.first      = std::next(__f, std::distance(__mf, __m.suffix().first));4592    __suffix_.second     = std::next(__f, std::distance(__mf, __m.suffix().second));4593    __suffix_.matched    = __m.suffix().matched;4594    if (!__no_update_pos)4595      __position_start_ = __prefix_.first;4596    __ready_ = __m.ready();4597  }4598 4599private:4600  void __init(unsigned __s, _BidirectionalIterator __f, _BidirectionalIterator __l, bool __no_update_pos = false);4601 4602  template <class, class>4603  friend class basic_regex;4604 4605  template <class _Bp, class _Ap, class _Cp, class _Tp>4606  friend bool4607  regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);4608 4609  template <class _Bp, class _Ap>4610  friend bool operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);4611 4612  template <class, class>4613  friend class __lookahead;4614 4615  template <class, class, class>4616  friend class regex_iterator;4617};4618 4619template <class _BidirectionalIterator, class _Allocator>4620match_results<_BidirectionalIterator, _Allocator>::match_results(const allocator_type& __a)4621    : __matches_(__a), __unmatched_(), __prefix_(), __suffix_(), __ready_(false), __position_start_() {}4622 4623template <class _BidirectionalIterator, class _Allocator>4624void match_results<_BidirectionalIterator, _Allocator>::__init(4625    unsigned __s, _BidirectionalIterator __f, _BidirectionalIterator __l, bool __no_update_pos) {4626  __unmatched_.first   = __l;4627  __unmatched_.second  = __l;4628  __unmatched_.matched = false;4629  __matches_.assign(__s, __unmatched_);4630  __prefix_.first   = __f;4631  __prefix_.second  = __f;4632  __prefix_.matched = false;4633  __suffix_         = __unmatched_;4634  if (!__no_update_pos)4635    __position_start_ = __prefix_.first;4636  __ready_ = true;4637}4638 4639template <class _BidirectionalIterator, class _Allocator>4640template <class _OutputIter>4641_OutputIter match_results<_BidirectionalIterator, _Allocator>::format(4642    _OutputIter __output_iter,4643    const char_type* __fmt_first,4644    const char_type* __fmt_last,4645    regex_constants::match_flag_type __flags) const {4646  // Note: this duplicates a check in `vector::operator[]` but provides a better error message.4647  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(ready(), "match_results::format() called when not ready");4648  if (__flags & regex_constants::format_sed) {4649    for (; __fmt_first != __fmt_last; ++__fmt_first) {4650      if (*__fmt_first == '&')4651        __output_iter = std::copy(__matches_[0].first, __matches_[0].second, __output_iter);4652      else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last) {4653        ++__fmt_first;4654        if ('0' <= *__fmt_first && *__fmt_first <= '9') {4655          size_t __i    = *__fmt_first - '0';4656          __output_iter = std::copy((*this)[__i].first, (*this)[__i].second, __output_iter);4657        } else {4658          *__output_iter = *__fmt_first;4659          ++__output_iter;4660        }4661      } else {4662        *__output_iter = *__fmt_first;4663        ++__output_iter;4664      }4665    }4666  } else {4667    for (; __fmt_first != __fmt_last; ++__fmt_first) {4668      if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last) {4669        switch (__fmt_first[1]) {4670        case '$':4671          *__output_iter = *++__fmt_first;4672          ++__output_iter;4673          break;4674        case '&':4675          ++__fmt_first;4676          __output_iter = std::copy(__matches_[0].first, __matches_[0].second, __output_iter);4677          break;4678        case '`':4679          ++__fmt_first;4680          __output_iter = std::copy(__prefix_.first, __prefix_.second, __output_iter);4681          break;4682        case '\'':4683          ++__fmt_first;4684          __output_iter = std::copy(__suffix_.first, __suffix_.second, __output_iter);4685          break;4686        default:4687          if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9') {4688            ++__fmt_first;4689            size_t __idx = *__fmt_first - '0';4690            if (__fmt_first + 1 != __fmt_last && '0' <= __fmt_first[1] && __fmt_first[1] <= '9') {4691              ++__fmt_first;4692              if (__idx >= numeric_limits<size_t>::max() / 10)4693                __throw_regex_error<regex_constants::error_escape>();4694              __idx = 10 * __idx + *__fmt_first - '0';4695            }4696            __output_iter = std::copy((*this)[__idx].first, (*this)[__idx].second, __output_iter);4697          } else {4698            *__output_iter = *__fmt_first;4699            ++__output_iter;4700          }4701          break;4702        }4703      } else {4704        *__output_iter = *__fmt_first;4705        ++__output_iter;4706      }4707    }4708  }4709  return __output_iter;4710}4711 4712template <class _BidirectionalIterator, class _Allocator>4713void match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m) {4714  using std::swap;4715  swap(__matches_, __m.__matches_);4716  swap(__unmatched_, __m.__unmatched_);4717  swap(__prefix_, __m.__prefix_);4718  swap(__suffix_, __m.__suffix_);4719  swap(__position_start_, __m.__position_start_);4720  swap(__ready_, __m.__ready_);4721}4722 4723template <class _BidirectionalIterator, class _Allocator>4724_LIBCPP_HIDE_FROM_ABI bool operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,4725                                      const match_results<_BidirectionalIterator, _Allocator>& __y) {4726  if (__x.__ready_ != __y.__ready_)4727    return false;4728  if (!__x.__ready_)4729    return true;4730  return __x.__matches_ == __y.__matches_ && __x.__prefix_ == __y.__prefix_ && __x.__suffix_ == __y.__suffix_;4731}4732 4733template <class _BidirectionalIterator, class _Allocator>4734inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,4735                                             const match_results<_BidirectionalIterator, _Allocator>& __y) {4736  return !(__x == __y);4737}4738 4739template <class _BidirectionalIterator, class _Allocator>4740inline _LIBCPP_HIDE_FROM_ABI void4741swap(match_results<_BidirectionalIterator, _Allocator>& __x, match_results<_BidirectionalIterator, _Allocator>& __y) {4742  __x.swap(__y);4743}4744 4745// regex_search4746 4747template <class _CharT, class _Traits>4748template <class _Allocator>4749bool basic_regex<_CharT, _Traits>::__match_at_start_ecma(4750    const _CharT* __first,4751    const _CharT* __last,4752    match_results<const _CharT*, _Allocator>& __m,4753    regex_constants::match_flag_type __flags,4754    bool __at_first) const {4755  vector<__state> __states;4756  __node* __st = __start_.get();4757  if (__st) {4758    sub_match<const _CharT*> __unmatched;4759    __unmatched.first   = __last;4760    __unmatched.second  = __last;4761    __unmatched.matched = false;4762 4763    __states.push_back(__state());4764    __states.back().__do_      = 0;4765    __states.back().__first_   = __first;4766    __states.back().__current_ = __first;4767    __states.back().__last_    = __last;4768    __states.back().__sub_matches_.resize(mark_count(), __unmatched);4769    __states.back().__loop_data_.resize(__loop_count());4770    __states.back().__node_     = __st;4771    __states.back().__flags_    = __flags;4772    __states.back().__at_first_ = __at_first;4773    int __counter               = 0;4774    int __length                = __last - __first;4775    do {4776      ++__counter;4777      if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)4778        __throw_regex_error<regex_constants::error_complexity>();4779      __state& __s = __states.back();4780      if (__s.__node_)4781        __s.__node_->__exec(__s);4782      switch (__s.__do_) {4783      case __state::__end_state:4784        if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {4785          __states.pop_back();4786          break;4787        }4788        if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {4789          __states.pop_back();4790          break;4791        }4792        __m.__matches_[0].first   = __first;4793        __m.__matches_[0].second  = std::next(__first, __s.__current_ - __first);4794        __m.__matches_[0].matched = true;4795        for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)4796          __m.__matches_[__i + 1] = __s.__sub_matches_[__i];4797        return true;4798      case __state::__accept_and_consume:4799      case __state::__repeat:4800      case __state::__accept_but_not_consume:4801        break;4802      case __state::__split: {4803        __state __snext = __s;4804        __s.__node_->__exec_split(true, __s);4805        __snext.__node_->__exec_split(false, __snext);4806        __states.push_back(std::move(__snext));4807      } break;4808      case __state::__reject:4809        __states.pop_back();4810        break;4811      default:4812        __throw_regex_error<regex_constants::__re_err_unknown>();4813        break;4814      }4815    } while (!__states.empty());4816  }4817  return false;4818}4819 4820template <class _CharT, class _Traits>4821template <class _Allocator>4822bool basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(4823    const _CharT* __first,4824    const _CharT* __last,4825    match_results<const _CharT*, _Allocator>& __m,4826    regex_constants::match_flag_type __flags,4827    bool __at_first) const {4828  deque<__state> __states;4829  ptrdiff_t __highest_j = 0;4830  ptrdiff_t __np        = std::distance(__first, __last);4831  __node* __st          = __start_.get();4832  if (__st) {4833    __states.push_back(__state());4834    __states.back().__do_      = 0;4835    __states.back().__first_   = __first;4836    __states.back().__current_ = __first;4837    __states.back().__last_    = __last;4838    __states.back().__loop_data_.resize(__loop_count());4839    __states.back().__node_     = __st;4840    __states.back().__flags_    = __flags;4841    __states.back().__at_first_ = __at_first;4842    bool __matched              = false;4843    int __counter               = 0;4844    int __length                = __last - __first;4845    do {4846      ++__counter;4847      if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)4848        __throw_regex_error<regex_constants::error_complexity>();4849      __state& __s = __states.back();4850      if (__s.__node_)4851        __s.__node_->__exec(__s);4852      switch (__s.__do_) {4853      case __state::__end_state:4854        if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {4855          __states.pop_back();4856          break;4857        }4858        if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {4859          __states.pop_back();4860          break;4861        }4862        if (!__matched || __highest_j < __s.__current_ - __s.__first_)4863          __highest_j = __s.__current_ - __s.__first_;4864        __matched = true;4865        if (__highest_j == __np)4866          __states.clear();4867        else4868          __states.pop_back();4869        break;4870      case __state::__consume_input:4871        break;4872      case __state::__accept_and_consume:4873        __states.push_front(std::move(__s));4874        __states.pop_back();4875        break;4876      case __state::__repeat:4877      case __state::__accept_but_not_consume:4878        break;4879      case __state::__split: {4880        __state __snext = __s;4881        __s.__node_->__exec_split(true, __s);4882        __snext.__node_->__exec_split(false, __snext);4883        __states.push_back(std::move(__snext));4884      } break;4885      case __state::__reject:4886        __states.pop_back();4887        break;4888      default:4889        __throw_regex_error<regex_constants::__re_err_unknown>();4890        break;4891      }4892    } while (!__states.empty());4893    if (__matched) {4894      __m.__matches_[0].first   = __first;4895      __m.__matches_[0].second  = std::next(__first, __highest_j);4896      __m.__matches_[0].matched = true;4897      return true;4898    }4899  }4900  return false;4901}4902 4903template <class _CharT, class _Traits>4904template <class _Allocator>4905bool basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(4906    const _CharT* __first,4907    const _CharT* __last,4908    match_results<const _CharT*, _Allocator>& __m,4909    regex_constants::match_flag_type __flags,4910    bool __at_first) const {4911  vector<__state> __states;4912  __state __best_state;4913  ptrdiff_t __highest_j = 0;4914  ptrdiff_t __np        = std::distance(__first, __last);4915  __node* __st          = __start_.get();4916  if (__st) {4917    sub_match<const _CharT*> __unmatched;4918    __unmatched.first   = __last;4919    __unmatched.second  = __last;4920    __unmatched.matched = false;4921 4922    __states.push_back(__state());4923    __states.back().__do_      = 0;4924    __states.back().__first_   = __first;4925    __states.back().__current_ = __first;4926    __states.back().__last_    = __last;4927    __states.back().__sub_matches_.resize(mark_count(), __unmatched);4928    __states.back().__loop_data_.resize(__loop_count());4929    __states.back().__node_     = __st;4930    __states.back().__flags_    = __flags;4931    __states.back().__at_first_ = __at_first;4932    bool __matched              = false;4933    int __counter               = 0;4934    int __length                = __last - __first;4935    do {4936      ++__counter;4937      if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)4938        __throw_regex_error<regex_constants::error_complexity>();4939      __state& __s = __states.back();4940      if (__s.__node_)4941        __s.__node_->__exec(__s);4942      switch (__s.__do_) {4943      case __state::__end_state:4944        if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {4945          __states.pop_back();4946          break;4947        }4948        if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {4949          __states.pop_back();4950          break;4951        }4952        if (!__matched || __highest_j < __s.__current_ - __s.__first_) {4953          __highest_j  = __s.__current_ - __s.__first_;4954          __best_state = __s;4955        }4956        __matched = true;4957        if (__highest_j == __np)4958          __states.clear();4959        else4960          __states.pop_back();4961        break;4962      case __state::__accept_and_consume:4963      case __state::__repeat:4964      case __state::__accept_but_not_consume:4965        break;4966      case __state::__split: {4967        __state __snext = __s;4968        __s.__node_->__exec_split(true, __s);4969        __snext.__node_->__exec_split(false, __snext);4970        __states.push_back(std::move(__snext));4971      } break;4972      case __state::__reject:4973        __states.pop_back();4974        break;4975      default:4976        __throw_regex_error<regex_constants::__re_err_unknown>();4977        break;4978      }4979    } while (!__states.empty());4980    if (__matched) {4981      __m.__matches_[0].first   = __first;4982      __m.__matches_[0].second  = std::next(__first, __highest_j);4983      __m.__matches_[0].matched = true;4984      for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)4985        __m.__matches_[__i + 1] = __best_state.__sub_matches_[__i];4986      return true;4987    }4988  }4989  return false;4990}4991 4992template <class _CharT, class _Traits>4993template <class _Allocator>4994bool basic_regex<_CharT, _Traits>::__match_at_start(4995    const _CharT* __first,4996    const _CharT* __last,4997    match_results<const _CharT*, _Allocator>& __m,4998    regex_constants::match_flag_type __flags,4999    bool __at_first) const {5000  if (__get_grammar(__flags_) == ECMAScript)5001    return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);5002  if (mark_count() == 0)5003    return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);5004  return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);5005}5006 5007template <class _CharT, class _Traits>5008template <class _Allocator>5009bool basic_regex<_CharT, _Traits>::__search(5010    const _CharT* __first,5011    const _CharT* __last,5012    match_results<const _CharT*, _Allocator>& __m,5013    regex_constants::match_flag_type __flags) const {5014  if (__flags & regex_constants::match_prev_avail)5015    __flags &= ~(regex_constants::match_not_bol | regex_constants::match_not_bow);5016 5017  __m.__init(1 + mark_count(), __first, __last, __flags & regex_constants::__no_update_pos);5018  if (__match_at_start(__first, __last, __m, __flags, !(__flags & regex_constants::__no_update_pos))) {5019    __m.__prefix_.second  = __m[0].first;5020    __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;5021    __m.__suffix_.first   = __m[0].second;5022    __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;5023    return true;5024  }5025  if (__first != __last && !(__flags & regex_constants::match_continuous)) {5026    __flags |= regex_constants::match_prev_avail;5027    for (++__first; __first != __last; ++__first) {5028      __m.__matches_.assign(__m.size(), __m.__unmatched_);5029      if (__match_at_start(__first, __last, __m, __flags, false)) {5030        __m.__prefix_.second  = __m[0].first;5031        __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;5032        __m.__suffix_.first   = __m[0].second;5033        __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;5034        return true;5035      }5036      __m.__matches_.assign(__m.size(), __m.__unmatched_);5037    }5038    __m.__matches_.assign(__m.size(), __m.__unmatched_);5039    if (__match_at_start(__first, __last, __m, __flags, false)) {5040      __m.__prefix_.second  = __m[0].first;5041      __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;5042      __m.__suffix_.first   = __m[0].second;5043      __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;5044      return true;5045    }5046  }5047  __m.__matches_.clear();5048  return false;5049}5050 5051template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>5052inline _LIBCPP_HIDE_FROM_ABI bool5053regex_search(_BidirectionalIterator __first,5054             _BidirectionalIterator __last,5055             match_results<_BidirectionalIterator, _Allocator>& __m,5056             const basic_regex<_CharT, _Traits>& __e,5057             regex_constants::match_flag_type __flags = regex_constants::match_default) {5058  int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;5059  basic_string<_CharT> __s(std::prev(__first, __offset), __last);5060  match_results<const _CharT*> __mc;5061  bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);5062  __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);5063  return __r;5064}5065 5066template <class _Iter, class _Allocator, class _CharT, class _Traits>5067inline _LIBCPP_HIDE_FROM_ABI bool5068regex_search(__wrap_iter<_Iter> __first,5069             __wrap_iter<_Iter> __last,5070             match_results<__wrap_iter<_Iter>, _Allocator>& __m,5071             const basic_regex<_CharT, _Traits>& __e,5072             regex_constants::match_flag_type __flags = regex_constants::match_default) {5073  match_results<const _CharT*> __mc;5074  bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);5075  __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);5076  return __r;5077}5078 5079template <class _Allocator, class _CharT, class _Traits>5080inline _LIBCPP_HIDE_FROM_ABI bool5081regex_search(const _CharT* __first,5082             const _CharT* __last,5083             match_results<const _CharT*, _Allocator>& __m,5084             const basic_regex<_CharT, _Traits>& __e,5085             regex_constants::match_flag_type __flags = regex_constants::match_default) {5086  return __e.__search(__first, __last, __m, __flags);5087}5088 5089template <class _BidirectionalIterator, class _CharT, class _Traits>5090inline _LIBCPP_HIDE_FROM_ABI bool5091regex_search(_BidirectionalIterator __first,5092             _BidirectionalIterator __last,5093             const basic_regex<_CharT, _Traits>& __e,5094             regex_constants::match_flag_type __flags = regex_constants::match_default) {5095  basic_string<_CharT> __s(__first, __last);5096  match_results<const _CharT*> __mc;5097  return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);5098}5099 5100template <class _CharT, class _Traits>5101inline _LIBCPP_HIDE_FROM_ABI bool5102regex_search(const _CharT* __first,5103             const _CharT* __last,5104             const basic_regex<_CharT, _Traits>& __e,5105             regex_constants::match_flag_type __flags = regex_constants::match_default) {5106  match_results<const _CharT*> __mc;5107  return __e.__search(__first, __last, __mc, __flags);5108}5109 5110template <class _CharT, class _Allocator, class _Traits>5111inline _LIBCPP_HIDE_FROM_ABI bool5112regex_search(const _CharT* __str,5113             match_results<const _CharT*, _Allocator>& __m,5114             const basic_regex<_CharT, _Traits>& __e,5115             regex_constants::match_flag_type __flags = regex_constants::match_default) {5116  return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);5117}5118 5119template <class _CharT, class _Traits>5120inline _LIBCPP_HIDE_FROM_ABI bool5121regex_search(const _CharT* __str,5122             const basic_regex<_CharT, _Traits>& __e,5123             regex_constants::match_flag_type __flags = regex_constants::match_default) {5124  match_results<const _CharT*> __m;5125  return std::regex_search(__str, __m, __e, __flags);5126}5127 5128template <class _ST, class _SA, class _CharT, class _Traits>5129inline _LIBCPP_HIDE_FROM_ABI bool5130regex_search(const basic_string<_CharT, _ST, _SA>& __s,5131             const basic_regex<_CharT, _Traits>& __e,5132             regex_constants::match_flag_type __flags = regex_constants::match_default) {5133  match_results<const _CharT*> __mc;5134  return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);5135}5136 5137template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>5138inline _LIBCPP_HIDE_FROM_ABI bool5139regex_search(const basic_string<_CharT, _ST, _SA>& __s,5140             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,5141             const basic_regex<_CharT, _Traits>& __e,5142             regex_constants::match_flag_type __flags = regex_constants::match_default) {5143  match_results<const _CharT*> __mc;5144  bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);5145  __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);5146  return __r;5147}5148 5149// regex_match5150 5151template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>5152_LIBCPP_HIDE_FROM_ABI bool5153regex_match(_BidirectionalIterator __first,5154            _BidirectionalIterator __last,5155            match_results<_BidirectionalIterator, _Allocator>& __m,5156            const basic_regex<_CharT, _Traits>& __e,5157            regex_constants::match_flag_type __flags = regex_constants::match_default) {5158  bool __r = std::regex_search(5159      __first, __last, __m, __e, __flags | regex_constants::match_continuous | regex_constants::__full_match);5160  if (__r) {5161    __r = !__m.suffix().matched;5162    if (!__r)5163      __m.__matches_.clear();5164  }5165  return __r;5166}5167 5168template <class _BidirectionalIterator, class _CharT, class _Traits>5169inline _LIBCPP_HIDE_FROM_ABI bool5170regex_match(_BidirectionalIterator __first,5171            _BidirectionalIterator __last,5172            const basic_regex<_CharT, _Traits>& __e,5173            regex_constants::match_flag_type __flags = regex_constants::match_default) {5174  match_results<_BidirectionalIterator> __m;5175  return std::regex_match(__first, __last, __m, __e, __flags);5176}5177 5178template <class _CharT, class _Allocator, class _Traits>5179inline _LIBCPP_HIDE_FROM_ABI bool5180regex_match(const _CharT* __str,5181            match_results<const _CharT*, _Allocator>& __m,5182            const basic_regex<_CharT, _Traits>& __e,5183            regex_constants::match_flag_type __flags = regex_constants::match_default) {5184  return std::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);5185}5186 5187template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>5188inline _LIBCPP_HIDE_FROM_ABI bool5189regex_match(const basic_string<_CharT, _ST, _SA>& __s,5190            match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,5191            const basic_regex<_CharT, _Traits>& __e,5192            regex_constants::match_flag_type __flags = regex_constants::match_default) {5193  return std::regex_match(__s.begin(), __s.end(), __m, __e, __flags);5194}5195 5196template <class _CharT, class _Traits>5197inline _LIBCPP_HIDE_FROM_ABI bool5198regex_match(const _CharT* __str,5199            const basic_regex<_CharT, _Traits>& __e,5200            regex_constants::match_flag_type __flags = regex_constants::match_default) {5201  return std::regex_match(__str, __str + _Traits::length(__str), __e, __flags);5202}5203 5204template <class _ST, class _SA, class _CharT, class _Traits>5205inline _LIBCPP_HIDE_FROM_ABI bool5206regex_match(const basic_string<_CharT, _ST, _SA>& __s,5207            const basic_regex<_CharT, _Traits>& __e,5208            regex_constants::match_flag_type __flags = regex_constants::match_default) {5209  return std::regex_match(__s.begin(), __s.end(), __e, __flags);5210}5211 5212// regex_iterator5213 5214template <class _BidirectionalIterator,5215          class _CharT  = typename iterator_traits<_BidirectionalIterator>::value_type,5216          class _Traits = regex_traits<_CharT> >5217class _LIBCPP_TEMPLATE_VIS regex_iterator;5218 5219typedef regex_iterator<const char*> cregex_iterator;5220typedef regex_iterator<string::const_iterator> sregex_iterator;5221#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS5222typedef regex_iterator<const wchar_t*> wcregex_iterator;5223typedef regex_iterator<wstring::const_iterator> wsregex_iterator;5224#endif5225 5226template <class _BidirectionalIterator, class _CharT, class _Traits>5227class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cregex_iterator)5228    _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_iterator)) _LIBCPP_PREFERRED_NAME(sregex_iterator)5229        _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_iterator)) regex_iterator {5230public:5231  typedef basic_regex<_CharT, _Traits> regex_type;5232  typedef match_results<_BidirectionalIterator> value_type;5233  typedef ptrdiff_t difference_type;5234  typedef const value_type* pointer;5235  typedef const value_type& reference;5236  typedef forward_iterator_tag iterator_category;5237 5238private:5239  _BidirectionalIterator __begin_;5240  _BidirectionalIterator __end_;5241  const regex_type* __pregex_;5242  regex_constants::match_flag_type __flags_;5243  value_type __match_;5244 5245public:5246  regex_iterator();5247  regex_iterator(_BidirectionalIterator __a,5248                 _BidirectionalIterator __b,5249                 const regex_type& __re,5250                 regex_constants::match_flag_type __m = regex_constants::match_default);5251 5252  _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_iterator& __x) const;5253  _LIBCPP_HIDE_FROM_ABI bool operator!=(const regex_iterator& __x) const { return !(*this == __x); }5254 5255  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __match_; }5256  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return std::addressof(__match_); }5257 5258  regex_iterator& operator++();5259  _LIBCPP_HIDE_FROM_ABI regex_iterator operator++(int) {5260    regex_iterator __t(*this);5261    ++(*this);5262    return __t;5263  }5264};5265 5266template <class _BidirectionalIterator, class _CharT, class _Traits>5267regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()5268    : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_() {}5269 5270template <class _BidirectionalIterator, class _CharT, class _Traits>5271regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator(5272    _BidirectionalIterator __a,5273    _BidirectionalIterator __b,5274    const regex_type& __re,5275    regex_constants::match_flag_type __m)5276    : __begin_(__a), __end_(__b), __pregex_(std::addressof(__re)), __flags_(__m) {5277  std::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);5278}5279 5280template <class _BidirectionalIterator, class _CharT, class _Traits>5281bool regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator==(const regex_iterator& __x) const {5282  if (__match_.empty() && __x.__match_.empty())5283    return true;5284  if (__match_.empty() || __x.__match_.empty())5285    return false;5286  return __begin_ == __x.__begin_ && __end_ == __x.__end_ && __pregex_ == __x.__pregex_ && __flags_ == __x.__flags_ &&5287         __match_[0] == __x.__match_[0];5288}5289 5290template <class _BidirectionalIterator, class _CharT, class _Traits>5291regex_iterator<_BidirectionalIterator, _CharT, _Traits>&5292regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++() {5293  __flags_ |= regex_constants::__no_update_pos;5294  _BidirectionalIterator __start        = __match_[0].second;5295  _BidirectionalIterator __prefix_start = __start;5296 5297  if (__match_[0].first == __match_[0].second) {5298    if (__start == __end_) {5299      __match_ = value_type();5300      return *this;5301    } else if (std::regex_search(__start,5302                                 __end_,5303                                 __match_,5304                                 *__pregex_,5305                                 __flags_ | regex_constants::match_not_null | regex_constants::match_continuous))5306      return *this;5307    else5308      ++__start;5309  }5310 5311  __flags_ |= regex_constants::match_prev_avail;5312  if (!std::regex_search(__start, __end_, __match_, *__pregex_, __flags_)) {5313    __match_ = value_type();5314 5315  } else {5316    // The Standard mandates that if `regex_search` returns true ([re.regiter.incr]), "`match.prefix().first` shall be5317    // equal to the previous value of `match[0].second`... It is unspecified how the implementation makes these5318    // adjustments." The adjustment is necessary if we incremented `__start` above (the branch that deals with5319    // zero-length matches).5320    auto& __prefix   = __match_.__prefix_;5321    __prefix.first   = __prefix_start;5322    __prefix.matched = __prefix.first != __prefix.second;5323  }5324 5325  return *this;5326}5327 5328// regex_token_iterator5329 5330template <class _BidirectionalIterator,5331          class _CharT  = typename iterator_traits<_BidirectionalIterator>::value_type,5332          class _Traits = regex_traits<_CharT> >5333class _LIBCPP_TEMPLATE_VIS regex_token_iterator;5334 5335typedef regex_token_iterator<const char*> cregex_token_iterator;5336typedef regex_token_iterator<string::const_iterator> sregex_token_iterator;5337#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS5338typedef regex_token_iterator<const wchar_t*> wcregex_token_iterator;5339typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;5340#endif5341 5342template <class _BidirectionalIterator, class _CharT, class _Traits>5343class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cregex_token_iterator)5344    _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_token_iterator))5345        _LIBCPP_PREFERRED_NAME(sregex_token_iterator)5346            _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_token_iterator)) regex_token_iterator {5347public:5348  typedef basic_regex<_CharT, _Traits> regex_type;5349  typedef sub_match<_BidirectionalIterator> value_type;5350  typedef ptrdiff_t difference_type;5351  typedef const value_type* pointer;5352  typedef const value_type& reference;5353  typedef forward_iterator_tag iterator_category;5354 5355private:5356  typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;5357 5358  _Position __position_;5359  const value_type* __result_;5360  value_type __suffix_;5361  ptrdiff_t __n_;5362  vector<int> __subs_;5363 5364public:5365  regex_token_iterator();5366  regex_token_iterator(_BidirectionalIterator __a,5367                       _BidirectionalIterator __b,5368                       const regex_type& __re,5369                       int __submatch                       = 0,5370                       regex_constants::match_flag_type __m = regex_constants::match_default);5371 5372  regex_token_iterator(_BidirectionalIterator __a,5373                       _BidirectionalIterator __b,5374                       const regex_type& __re,5375                       const vector<int>& __submatches,5376                       regex_constants::match_flag_type __m = regex_constants::match_default);5377 5378  template <size_t _Np>5379  regex_token_iterator(_BidirectionalIterator __a,5380                       _BidirectionalIterator __b,5381                       const regex_type& __re,5382                       const int (&__submatches)[_Np],5383                       regex_constants::match_flag_type __m = regex_constants::match_default);5384 5385  regex_token_iterator(const regex_token_iterator&);5386  regex_token_iterator& operator=(const regex_token_iterator&);5387 5388  _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_token_iterator& __x) const;5389  _LIBCPP_HIDE_FROM_ABI bool operator!=(const regex_token_iterator& __x) const { return !(*this == __x); }5390 5391  _LIBCPP_HIDE_FROM_ABI const value_type& operator*() const { return *__result_; }5392  _LIBCPP_HIDE_FROM_ABI const value_type* operator->() const { return __result_; }5393 5394  regex_token_iterator& operator++();5395  _LIBCPP_HIDE_FROM_ABI regex_token_iterator operator++(int) {5396    regex_token_iterator __t(*this);5397    ++(*this);5398    return __t;5399  }5400 5401private:5402  void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);5403  void __establish_result() {5404    if (__subs_[__n_] == -1)5405      __result_ = &__position_->prefix();5406    else5407      __result_ = &(*__position_)[__subs_[__n_]];5408  }5409};5410 5411template <class _BidirectionalIterator, class _CharT, class _Traits>5412regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator()5413    : __result_(nullptr), __suffix_(), __n_(0) {}5414 5415template <class _BidirectionalIterator, class _CharT, class _Traits>5416void regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::__init(5417    _BidirectionalIterator __a, _BidirectionalIterator __b) {5418  if (__position_ != _Position())5419    __establish_result();5420  else if (__subs_[__n_] == -1) {5421    __suffix_.matched = true;5422    __suffix_.first   = __a;5423    __suffix_.second  = __b;5424    __result_         = &__suffix_;5425  } else5426    __result_ = nullptr;5427}5428 5429template <class _BidirectionalIterator, class _CharT, class _Traits>5430regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(5431    _BidirectionalIterator __a,5432    _BidirectionalIterator __b,5433    const regex_type& __re,5434    int __submatch,5435    regex_constants::match_flag_type __m)5436    : __position_(__a, __b, __re, __m), __n_(0), __subs_(1, __submatch) {5437  __init(__a, __b);5438}5439 5440template <class _BidirectionalIterator, class _CharT, class _Traits>5441regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(5442    _BidirectionalIterator __a,5443    _BidirectionalIterator __b,5444    const regex_type& __re,5445    const vector<int>& __submatches,5446    regex_constants::match_flag_type __m)5447    : __position_(__a, __b, __re, __m), __n_(0), __subs_(__submatches) {5448  __init(__a, __b);5449}5450 5451template <class _BidirectionalIterator, class _CharT, class _Traits>5452template <size_t _Np>5453regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(5454    _BidirectionalIterator __a,5455    _BidirectionalIterator __b,5456    const regex_type& __re,5457    const int (&__submatches)[_Np],5458    regex_constants::match_flag_type __m)5459    : __position_(__a, __b, __re, __m), __n_(0), __subs_(begin(__submatches), end(__submatches)) {5460  __init(__a, __b);5461}5462 5463template <class _BidirectionalIterator, class _CharT, class _Traits>5464regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(const regex_token_iterator& __x)5465    : __position_(__x.__position_),5466      __result_(__x.__result_),5467      __suffix_(__x.__suffix_),5468      __n_(__x.__n_),5469      __subs_(__x.__subs_) {5470  if (__x.__result_ == &__x.__suffix_)5471    __result_ = &__suffix_;5472  else if (__result_ != nullptr)5473    __establish_result();5474}5475 5476template <class _BidirectionalIterator, class _CharT, class _Traits>5477regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&5478regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator=(const regex_token_iterator& __x) {5479  if (this != &__x) {5480    __position_ = __x.__position_;5481    if (__x.__result_ == &__x.__suffix_)5482      __result_ = &__suffix_;5483    else5484      __result_ = __x.__result_;5485    __suffix_ = __x.__suffix_;5486    __n_      = __x.__n_;5487    __subs_   = __x.__subs_;5488 5489    if (__result_ != nullptr && __result_ != &__suffix_)5490      __establish_result();5491  }5492  return *this;5493}5494 5495template <class _BidirectionalIterator, class _CharT, class _Traits>5496bool regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator==(const regex_token_iterator& __x) const {5497  if (__result_ == nullptr && __x.__result_ == nullptr)5498    return true;5499  if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ && __suffix_ == __x.__suffix_)5500    return true;5501  if (__result_ == nullptr || __x.__result_ == nullptr)5502    return false;5503  if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)5504    return false;5505  return __position_ == __x.__position_ && __n_ == __x.__n_ && __subs_ == __x.__subs_;5506}5507 5508template <class _BidirectionalIterator, class _CharT, class _Traits>5509regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&5510regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++() {5511  _Position __prev = __position_;5512  if (__result_ == &__suffix_)5513    __result_ = nullptr;5514  else if (static_cast<size_t>(__n_ + 1) < __subs_.size()) {5515    ++__n_;5516    __establish_result();5517  } else {5518    __n_ = 0;5519    ++__position_;5520    if (__position_ != _Position())5521      __establish_result();5522    else {5523      if (std::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end() && __prev->suffix().length() != 0) {5524        __suffix_.matched = true;5525        __suffix_.first   = __prev->suffix().first;5526        __suffix_.second  = __prev->suffix().second;5527        __result_         = &__suffix_;5528      } else5529        __result_ = nullptr;5530    }5531  }5532  return *this;5533}5534 5535// regex_replace5536 5537template <class _OutputIterator, class _BidirectionalIterator, class _Traits, class _CharT>5538_LIBCPP_HIDE_FROM_ABI _OutputIterator regex_replace(5539    _OutputIterator __output_iter,5540    _BidirectionalIterator __first,5541    _BidirectionalIterator __last,5542    const basic_regex<_CharT, _Traits>& __e,5543    const _CharT* __fmt,5544    regex_constants::match_flag_type __flags = regex_constants::match_default) {5545  typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;5546  _Iter __i(__first, __last, __e, __flags);5547  _Iter __eof;5548  if (__i == __eof) {5549    if (!(__flags & regex_constants::format_no_copy))5550      __output_iter = std::copy(__first, __last, __output_iter);5551  } else {5552    sub_match<_BidirectionalIterator> __lm;5553    for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i) {5554      if (!(__flags & regex_constants::format_no_copy))5555        __output_iter = std::copy(__i->prefix().first, __i->prefix().second, __output_iter);5556      __output_iter = __i->format(__output_iter, __fmt, __fmt + __len, __flags);5557      __lm          = __i->suffix();5558      if (__flags & regex_constants::format_first_only)5559        break;5560    }5561    if (!(__flags & regex_constants::format_no_copy))5562      __output_iter = std::copy(__lm.first, __lm.second, __output_iter);5563  }5564  return __output_iter;5565}5566 5567template <class _OutputIterator, class _BidirectionalIterator, class _Traits, class _CharT, class _ST, class _SA>5568inline _LIBCPP_HIDE_FROM_ABI _OutputIterator regex_replace(5569    _OutputIterator __output_iter,5570    _BidirectionalIterator __first,5571    _BidirectionalIterator __last,5572    const basic_regex<_CharT, _Traits>& __e,5573    const basic_string<_CharT, _ST, _SA>& __fmt,5574    regex_constants::match_flag_type __flags = regex_constants::match_default) {5575  return std::regex_replace(__output_iter, __first, __last, __e, __fmt.c_str(), __flags);5576}5577 5578template <class _Traits, class _CharT, class _ST, class _SA, class _FST, class _FSA>5579inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT, _ST, _SA>5580regex_replace(const basic_string<_CharT, _ST, _SA>& __s,5581              const basic_regex<_CharT, _Traits>& __e,5582              const basic_string<_CharT, _FST, _FSA>& __fmt,5583              regex_constants::match_flag_type __flags = regex_constants::match_default) {5584  basic_string<_CharT, _ST, _SA> __r;5585  std::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e, __fmt.c_str(), __flags);5586  return __r;5587}5588 5589template <class _Traits, class _CharT, class _ST, class _SA>5590inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT, _ST, _SA>5591regex_replace(const basic_string<_CharT, _ST, _SA>& __s,5592              const basic_regex<_CharT, _Traits>& __e,5593              const _CharT* __fmt,5594              regex_constants::match_flag_type __flags = regex_constants::match_default) {5595  basic_string<_CharT, _ST, _SA> __r;5596  std::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e, __fmt, __flags);5597  return __r;5598}5599 5600template <class _Traits, class _CharT, class _ST, class _SA>5601inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT>5602regex_replace(const _CharT* __s,5603              const basic_regex<_CharT, _Traits>& __e,5604              const basic_string<_CharT, _ST, _SA>& __fmt,5605              regex_constants::match_flag_type __flags = regex_constants::match_default) {5606  basic_string<_CharT> __r;5607  std::regex_replace(std::back_inserter(__r), __s, __s + char_traits<_CharT>::length(__s), __e, __fmt.c_str(), __flags);5608  return __r;5609}5610 5611template <class _Traits, class _CharT>5612inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT>5613regex_replace(const _CharT* __s,5614              const basic_regex<_CharT, _Traits>& __e,5615              const _CharT* __fmt,5616              regex_constants::match_flag_type __flags = regex_constants::match_default) {5617  basic_string<_CharT> __r;5618  std::regex_replace(std::back_inserter(__r), __s, __s + char_traits<_CharT>::length(__s), __e, __fmt, __flags);5619  return __r;5620}5621 5622_LIBCPP_END_NAMESPACE_STD5623 5624_LIBCPP_POP_MACROS5625 5626#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)5627#  include <__cxx03/atomic>5628#  include <__cxx03/cstdlib>5629#  include <__cxx03/iosfwd>5630#  include <__cxx03/iterator>5631#  include <__cxx03/mutex>5632#  include <__cxx03/new>5633#  include <__cxx03/type_traits>5634#  include <__cxx03/typeinfo>5635#  include <__cxx03/utility>5636#endif5637 5638#endif // _LIBCPP___CXX03_REGEX5639