libcxx/include/regex

   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-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_REGEX
  11 #define _LIBCPP_REGEX
  12
  13 /*
  14     regex synopsis
  15
  16 #include <compare>
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 namespace regex_constants
  23 {
  24
  25 enum syntax_option_type
  26 {
  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  = unspecified
  38 };
  39
  40 constexpr syntax_option_type operator~(syntax_option_type f);
  41 constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
  42 constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);
  43
  44 enum match_flag_type
  45 {
  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 = unspecified
  59 };
  60
  61 constexpr match_flag_type operator~(match_flag_type f);
  62 constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
  63 constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);
  64
  65 enum error_type
  66 {
  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      = unspecified
  80 };
  81
  82 }  // regex_constants
  83
  84 class regex_error
  85     : public runtime_error
  86 {
  87 public:
  88     explicit regex_error(regex_constants::error_type ecode);
  89     regex_constants::error_type code() const;
  90 };
  91
  92 template <class charT>
  93 struct regex_traits
  94 {
  95 public:
  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_type
 108         transform(ForwardIterator first, ForwardIterator last) const;
 109     template <class ForwardIterator>
 110         string_type
 111         transform_primary( ForwardIterator first, ForwardIterator last) const;
 112     template <class ForwardIterator>
 113         string_type
 114         lookup_collatename(ForwardIterator first, ForwardIterator last) const;
 115     template <class ForwardIterator>
 116         char_class_type
 117         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
 125 template <class charT, class traits = regex_traits<charT>>
 126 class basic_regex
 127 {
 128 public:
 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
 197 template<class ForwardIterator>
 198 basic_regex(ForwardIterator, ForwardIterator,
 199             regex_constants::syntax_option_type = regex_constants::ECMAScript)
 200     -> basic_regex<typename iterator_traits<ForwardIterator>::value_type>; // C++17
 201
 202 typedef basic_regex<char>    regex;
 203 typedef basic_regex<wchar_t> wregex;
 204
 205 template <class charT, class traits>
 206     void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);
 207
 208 template <class BidirectionalIterator>
 209 class sub_match
 210     : public pair<BidirectionalIterator, BidirectionalIterator>
 211 {
 212 public:
 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
 233 typedef sub_match<const char*>             csub_match;
 234 typedef sub_match<const wchar_t*>          wcsub_match;
 235 typedef sub_match<string::const_iterator>  ssub_match;
 236 typedef sub_match<wstring::const_iterator> wssub_match;
 237
 238 template <class BiIter>
 239     bool
 240     operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 241
 242 template <class BiIter>
 243     auto
 244     operator<=>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs); // Since C++20
 245
 246  template <class BiIter>                                                     // Removed in C++20
 247     bool
 248     operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 249
 250 template <class BiIter>                                                      // Removed in C++20
 251     bool
 252     operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 253
 254 template <class BiIter>                                                      // Removed in C++20
 255     bool
 256     operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 257
 258 template <class BiIter>                                                      // Removed in C++20
 259     bool
 260     operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 261
 262 template <class BiIter>                                                      // Removed in C++20
 263     bool
 264     operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 265
 266 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 267     bool
 268     operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 269                const sub_match<BiIter>& rhs);
 270
 271 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 272     bool
 273     operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 274                const sub_match<BiIter>& rhs);
 275
 276 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 277     bool
 278     operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 279               const sub_match<BiIter>& rhs);
 280
 281 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 282     bool
 283     operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 284               const sub_match<BiIter>& rhs);
 285
 286 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 287     bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 288                     const sub_match<BiIter>& rhs);
 289
 290 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 291     bool
 292     operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 293                const sub_match<BiIter>& rhs);
 294
 295 template <class BiIter, class ST, class SA>
 296     bool
 297     operator==(const sub_match<BiIter>& lhs,
 298                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 299
 300 template <class BiIter, class ST, class SA>                                  // Since C++20
 301     auto
 302     operator<=>(const sub_match<BiIter>& lhs,
 303                 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 304
 305 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 306     bool
 307     operator!=(const sub_match<BiIter>& lhs,
 308                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 309
 310 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 311     bool
 312     operator<(const sub_match<BiIter>& lhs,
 313               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 314
 315 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 316     bool
 317     operator>(const sub_match<BiIter>& lhs,
 318                    const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 319
 320 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 321     bool
 322     operator>=(const sub_match<BiIter>& lhs,
 323                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 324
 325 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 326     bool
 327     operator<=(const sub_match<BiIter>& lhs,
 328                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 329
 330 template <class BiIter>                                                      // Removed in C++20
 331     bool
 332     operator==(typename iterator_traits<BiIter>::value_type const* lhs,
 333                const sub_match<BiIter>& rhs);
 334
 335 template <class BiIter>                                                      // Removed in C++20
 336     bool
 337     operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
 338                const sub_match<BiIter>& rhs);
 339
 340 template <class BiIter>                                                      // Removed in C++20
 341     bool
 342     operator<(typename iterator_traits<BiIter>::value_type const* lhs,
 343               const sub_match<BiIter>& rhs);
 344
 345 template <class BiIter>                                                      // Removed in C++20
 346     bool
 347     operator>(typename iterator_traits<BiIter>::value_type const* lhs,
 348               const sub_match<BiIter>& rhs);
 349
 350 template <class BiIter>                                                      // Removed in C++20
 351     bool
 352     operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
 353                const sub_match<BiIter>& rhs);
 354
 355 template <class BiIter>                                                      // Removed in C++20
 356     bool
 357     operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
 358                const sub_match<BiIter>& rhs);
 359
 360 template <class BiIter>
 361     bool
 362     operator==(const sub_match<BiIter>& lhs,
 363                typename iterator_traits<BiIter>::value_type const* rhs);
 364
 365 template <class BiIter>                                                      // Since C++20
 366     auto
 367     operator<=>(const sub_match<BiIter>& lhs,
 368                 typename iterator_traits<BiIter>::value_type const* rhs);
 369
 370 template <class BiIter, class ST, class SA>                                  // Removed in C++20
 371     bool
 372     operator!=(const sub_match<BiIter>& lhs,
 373                typename iterator_traits<BiIter>::value_type const* rhs);
 374
 375 template <class BiIter>                                                      // Removed in C++20
 376     bool
 377     operator<(const sub_match<BiIter>& lhs,
 378               typename iterator_traits<BiIter>::value_type const* rhs);
 379
 380 template <class BiIter>                                                      // Removed in C++20
 381     bool
 382     operator>(const sub_match<BiIter>& lhs,
 383               typename iterator_traits<BiIter>::value_type const* rhs);
 384
 385 template <class BiIter>                                                      // Removed in C++20
 386     bool
 387     operator>=(const sub_match<BiIter>& lhs,
 388                typename iterator_traits<BiIter>::value_type const* rhs);
 389
 390 template <class BiIter>                                                      // Removed in C++20
 391     bool
 392     operator<=(const sub_match<BiIter>& lhs,
 393                typename iterator_traits<BiIter>::value_type const* rhs);
 394
 395 template <class BiIter>                                                      // Removed in C++20
 396     bool
 397     operator==(typename iterator_traits<BiIter>::value_type const& lhs,
 398                const sub_match<BiIter>& rhs);
 399
 400 template <class BiIter>                                                      // Removed in C++20
 401     bool
 402     operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
 403                const sub_match<BiIter>& rhs);
 404
 405 template <class BiIter>                                                      // Removed in C++20
 406     bool
 407     operator<(typename iterator_traits<BiIter>::value_type const& lhs,
 408               const sub_match<BiIter>& rhs);
 409
 410 template <class BiIter>                                                      // Removed in C++20
 411     bool
 412     operator>(typename iterator_traits<BiIter>::value_type const& lhs,
 413               const sub_match<BiIter>& rhs);
 414
 415 template <class BiIter>                                                      // Removed in C++20
 416     bool
 417     operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
 418                const sub_match<BiIter>& rhs);
 419
 420 template <class BiIter>                                                      // Removed in C++20
 421     bool
 422     operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
 423                const sub_match<BiIter>& rhs);
 424
 425 template <class BiIter>
 426     bool
 427     operator==(const sub_match<BiIter>& lhs,
 428                typename iterator_traits<BiIter>::value_type const& rhs);
 429
 430 template <class BiIter>                                                      // Since C++20
 431     auto
 432     operator<=>(const sub_match<BiIter>& lhs,
 433                 typename iterator_traits<BiIter>::value_type const& rhs);
 434
 435 template <class BiIter>                                                      // Removed in C++20
 436     bool
 437     operator!=(const sub_match<BiIter>& lhs,
 438                typename iterator_traits<BiIter>::value_type const& rhs);
 439
 440 template <class BiIter>                                                      // Removed in C++20
 441     bool
 442     operator<(const sub_match<BiIter>& lhs,
 443               typename iterator_traits<BiIter>::value_type const& rhs);
 444
 445 template <class BiIter>                                                      // Removed in C++20
 446     bool
 447     operator>(const sub_match<BiIter>& lhs,
 448               typename iterator_traits<BiIter>::value_type const& rhs);
 449
 450 template <class BiIter>                                                      // Removed in C++20
 451     bool
 452     operator>=(const sub_match<BiIter>& lhs,
 453                typename iterator_traits<BiIter>::value_type const& rhs);
 454
 455 template <class BiIter>                                                      // Removed in C++20
 456     bool
 457     operator<=(const sub_match<BiIter>& lhs,
 458                typename iterator_traits<BiIter>::value_type const& rhs);
 459
 460 template <class charT, class ST, class BiIter>
 461     basic_ostream<charT, ST>&
 462     operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);
 463
 464 template <class BidirectionalIterator,
 465           class Allocator = allocator<sub_match<BidirectionalIterator>>>
 466 class match_results
 467 {
 468 public:
 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++20
 482     match_results() : match_results(Allocator()) {}           // C++20
 483     explicit match_results(const Allocator& a);               // C++20
 484     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         OutputIter
 514         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         OutputIter
 519         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_type
 526         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
 536 typedef match_results<const char*>             cmatch;
 537 typedef match_results<const wchar_t*>          wcmatch;
 538 typedef match_results<string::const_iterator>  smatch;
 539 typedef match_results<wstring::const_iterator> wsmatch;
 540
 541 template <class BidirectionalIterator, class Allocator>
 542     bool
 543     operator==(const match_results<BidirectionalIterator, Allocator>& m1,
 544                const match_results<BidirectionalIterator, Allocator>& m2);
 545
 546 template <class BidirectionalIterator, class Allocator>                    // Removed in C++20
 547     bool
 548     operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
 549                const match_results<BidirectionalIterator, Allocator>& m2);
 550
 551 template <class BidirectionalIterator, class Allocator>
 552     void
 553     swap(match_results<BidirectionalIterator, Allocator>& m1,
 554          match_results<BidirectionalIterator, Allocator>& m2);
 555
 556 template <class BidirectionalIterator, class Allocator, class charT, class traits>
 557     bool
 558     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
 563 template <class BidirectionalIterator, class charT, class traits>
 564     bool
 565     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
 569 template <class charT, class Allocator, class traits>
 570     bool
 571     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
 575 template <class ST, class SA, class Allocator, class charT, class traits>
 576     bool
 577     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
 582 template <class ST, class SA, class Allocator, class charT, class traits>
 583     bool
 584     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++14
 588
 589 template <class charT, class traits>
 590     bool
 591     regex_match(const charT* str, const basic_regex<charT, traits>& e,
 592                 regex_constants::match_flag_type flags = regex_constants::match_default);
 593
 594 template <class ST, class SA, class charT, class traits>
 595     bool
 596     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
 600 template <class BidirectionalIterator, class Allocator, class charT, class traits>
 601     bool
 602     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
 607 template <class BidirectionalIterator, class charT, class traits>
 608     bool
 609     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
 613 template <class charT, class Allocator, class traits>
 614     bool
 615     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
 619 template <class charT, class traits>
 620     bool
 621     regex_search(const charT* str, const basic_regex<charT, traits>& e,
 622                  regex_constants::match_flag_type flags = regex_constants::match_default);
 623
 624 template <class ST, class SA, class charT, class traits>
 625     bool
 626     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
 630 template <class ST, class SA, class Allocator, class charT, class traits>
 631     bool
 632     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
 637 template <class ST, class SA, class Allocator, class charT, class traits>
 638     bool
 639     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++14
 643
 644 template <class OutputIterator, class BidirectionalIterator,
 645           class traits, class charT, class ST, class SA>
 646     OutputIterator
 647     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
 653 template <class OutputIterator, class BidirectionalIterator,
 654           class traits, class charT>
 655     OutputIterator
 656     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
 661 template <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
 668 template <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
 674 template <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
 681 template <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
 688 template <class BidirectionalIterator,
 689           class charT = typename iterator_traits< BidirectionalIterator>::value_type,
 690           class traits = regex_traits<charT>>
 691 class regex_iterator
 692 {
 693 public:
 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++20
 701
 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 m
 709                                      = regex_constants::match_default) = delete; // C++14
 710     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++20
 715     bool operator!=(const regex_iterator&) const;                                   // Removed in C++20
 716
 717     const value_type& operator*() const;
 718     const value_type* operator->() const;
 719
 720     regex_iterator& operator++();
 721     regex_iterator operator++(int);
 722 };
 723
 724 typedef regex_iterator<const char*>             cregex_iterator;
 725 typedef regex_iterator<const wchar_t*>          wcregex_iterator;
 726 typedef regex_iterator<string::const_iterator>  sregex_iterator;
 727 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
 728
 729 template <class BidirectionalIterator,
 730           class charT = typename iterator_traits<BidirectionalIterator>::value_type,
 731           class traits = regex_traits<charT>>
 732 class regex_token_iterator
 733 {
 734 public:
 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++20
 742
 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++14
 750     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++14
 756     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++14
 762     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++14
 770     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++20
 775     bool operator!=(const regex_token_iterator&) const;                                   // Removed in C++20
 776
 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
 784 typedef regex_token_iterator<const char*>             cregex_token_iterator;
 785 typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
 786 typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
 787 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
 788
 789 } // std
 790 */
 791
 792 #include <__algorithm/find.h>
 793 #include <__algorithm/search.h>
 794 #include <__assert>
 795 #include <__config>
 796 #include <__iterator/back_insert_iterator.h>
 797 #include <__iterator/default_sentinel.h>
 798 #include <__iterator/wrap_iter.h>
 799 #include <__locale>
 800 #include <__memory/shared_ptr.h>
 801 #include <__memory_resource/polymorphic_allocator.h>
 802 #include <__type_traits/is_swappable.h>
 803 #include <__utility/move.h>
 804 #include <__utility/pair.h>
 805 #include <__utility/swap.h>
 806 #include <__verbose_abort>
 807 #include <deque>
 808 #include <stdexcept>
 809 #include <string>
 810 #include <vector>
 811 #include <version>
 812
 813 // standard-mandated includes
 814
 815 // [iterator.range]
 816 #include <__iterator/access.h>
 817 #include <__iterator/data.h>
 818 #include <__iterator/empty.h>
 819 #include <__iterator/reverse_access.h>
 820 #include <__iterator/size.h>
 821
 822 // [re.syn]
 823 #include <compare>
 824 #include <initializer_list>
 825
 826 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 827 #  pragma GCC system_header
 828 #endif
 829
 830 _LIBCPP_PUSH_MACROS
 831 #include <__undef_macros>
 832
 833 #define _LIBCPP_REGEX_COMPLEXITY_FACTOR 4096
 834
 835 _LIBCPP_BEGIN_NAMESPACE_STD
 836
 837 namespace regex_constants {
 838
 839 // syntax_option_type
 840
 841 enum syntax_option_type {
 842   icase    = 1 << 0,
 843   nosubs   = 1 << 1,
 844   optimize = 1 << 2,
 845   collate  = 1 << 3,
 846 #ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO
 847   ECMAScript = 1 << 9,
 848 #else
 849   ECMAScript = 0,
 850 #endif
 851   basic    = 1 << 4,
 852   extended = 1 << 5,
 853   awk      = 1 << 6,
 854   grep     = 1 << 7,
 855   egrep    = 1 << 8,
 856   // 1 << 9 may be used by ECMAScript
 857   multiline = 1 << 10
 858 };
 859
 860 _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR syntax_option_type __get_grammar(syntax_option_type __g) {
 861 #ifdef _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO
 862   return static_cast<syntax_option_type>(__g & 0x3F0);
 863 #else
 864   return static_cast<syntax_option_type>(__g & 0x1F0);
 865 #endif
 866 }
 867
 868 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type operator~(syntax_option_type __x) {
 869   return syntax_option_type(~int(__x) & 0x1FF);
 870 }
 871
 872 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
 873 operator&(syntax_option_type __x, syntax_option_type __y) {
 874   return syntax_option_type(int(__x) & int(__y));
 875 }
 876
 877 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
 878 operator|(syntax_option_type __x, syntax_option_type __y) {
 879   return syntax_option_type(int(__x) | int(__y));
 880 }
 881
 882 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR syntax_option_type
 883 operator^(syntax_option_type __x, syntax_option_type __y) {
 884   return syntax_option_type(int(__x) ^ int(__y));
 885 }
 886
 887 inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator&=(syntax_option_type& __x, syntax_option_type __y) {
 888   __x = __x & __y;
 889   return __x;
 890 }
 891
 892 inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator|=(syntax_option_type& __x, syntax_option_type __y) {
 893   __x = __x | __y;
 894   return __x;
 895 }
 896
 897 inline _LIBCPP_HIDE_FROM_ABI syntax_option_type& operator^=(syntax_option_type& __x, syntax_option_type __y) {
 898   __x = __x ^ __y;
 899   return __x;
 900 }
 901
 902 // match_flag_type
 903
 904 enum match_flag_type {
 905   match_default     = 0,
 906   match_not_bol     = 1 << 0,
 907   match_not_eol     = 1 << 1,
 908   match_not_bow     = 1 << 2,
 909   match_not_eow     = 1 << 3,
 910   match_any         = 1 << 4,
 911   match_not_null    = 1 << 5,
 912   match_continuous  = 1 << 6,
 913   match_prev_avail  = 1 << 7,
 914   format_default    = 0,
 915   format_sed        = 1 << 8,
 916   format_no_copy    = 1 << 9,
 917   format_first_only = 1 << 10,
 918   __no_update_pos   = 1 << 11,
 919   __full_match      = 1 << 12
 920 };
 921
 922 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator~(match_flag_type __x) {
 923   return match_flag_type(~int(__x) & 0x0FFF);
 924 }
 925
 926 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator&(match_flag_type __x, match_flag_type __y) {
 927   return match_flag_type(int(__x) & int(__y));
 928 }
 929
 930 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator|(match_flag_type __x, match_flag_type __y) {
 931   return match_flag_type(int(__x) | int(__y));
 932 }
 933
 934 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR match_flag_type operator^(match_flag_type __x, match_flag_type __y) {
 935   return match_flag_type(int(__x) ^ int(__y));
 936 }
 937
 938 inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator&=(match_flag_type& __x, match_flag_type __y) {
 939   __x = __x & __y;
 940   return __x;
 941 }
 942
 943 inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator|=(match_flag_type& __x, match_flag_type __y) {
 944   __x = __x | __y;
 945   return __x;
 946 }
 947
 948 inline _LIBCPP_HIDE_FROM_ABI match_flag_type& operator^=(match_flag_type& __x, match_flag_type __y) {
 949   __x = __x ^ __y;
 950   return __x;
 951 }
 952
 953 enum error_type {
 954   error_collate = 1,
 955   error_ctype,
 956   error_escape,
 957   error_backref,
 958   error_brack,
 959   error_paren,
 960   error_brace,
 961   error_badbrace,
 962   error_range,
 963   error_space,
 964   error_badrepeat,
 965   error_complexity,
 966   error_stack,
 967   __re_err_grammar,
 968   __re_err_empty,
 969   __re_err_unknown,
 970   __re_err_parse
 971 };
 972
 973 } // namespace regex_constants
 974
 975 class _LIBCPP_EXPORTED_FROM_ABI regex_error : public runtime_error {
 976   regex_constants::error_type __code_;
 977
 978 public:
 979   explicit regex_error(regex_constants::error_type __ecode);
 980   _LIBCPP_HIDE_FROM_ABI regex_error(const regex_error&) _NOEXCEPT = default;
 981   ~regex_error() _NOEXCEPT override;
 982   _LIBCPP_HIDE_FROM_ABI regex_constants::error_type code() const { return __code_; }
 983 };
 984
 985 template <regex_constants::error_type _Ev>
 986 [[__noreturn__]] inline _LIBCPP_HIDE_FROM_ABI void __throw_regex_error() {
 987 #if _LIBCPP_HAS_EXCEPTIONS
 988   throw regex_error(_Ev);
 989 #else
 990   _LIBCPP_VERBOSE_ABORT("regex_error was thrown in -fno-exceptions mode");
 991 #endif
 992 }
 993
 994 template <class _CharT>
 995 struct _LIBCPP_TEMPLATE_VIS regex_traits {
 996 public:
 997   typedef _CharT char_type;
 998   typedef basic_string<char_type> string_type;
 999   typedef locale locale_type;
1000 #if defined(__BIONIC__) || defined(_NEWLIB_VERSION)
1001   // Originally bionic's ctype_base used its own ctype masks because the
1002   // builtin ctype implementation wasn't in libc++ yet. Bionic's ctype mask
1003   // was only 8 bits wide and already saturated, so it used a wider type here
1004   // to make room for __regex_word (then a part of this class rather than
1005   // ctype_base). Bionic has since moved to the builtin ctype_base
1006   // implementation, but this was not updated to match. Since then Android has
1007   // needed to maintain a stable libc++ ABI, and this can't be changed without
1008   // an ABI break.
1009   // We also need this workaround for newlib since _NEWLIB_VERSION is not
1010   // defined yet inside __config, so we can't set the
1011   // _LIBCPP_PROVIDES_DEFAULT_RUNE_TABLE macro. Additionally, newlib is
1012   // often used for space constrained environments, so it makes sense not to
1013   // duplicate the ctype table.
1014   typedef uint16_t char_class_type;
1015 #else
1016   typedef ctype_base::mask char_class_type;
1017 #endif
1018
1019   static const char_class_type __regex_word = ctype_base::__regex_word;
1020
1021 private:
1022   locale __loc_;
1023   const ctype<char_type>* __ct_;
1024   const collate<char_type>* __col_;
1025
1026 public:
1027   regex_traits();
1028
1029   _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __p) { return char_traits<char_type>::length(__p); }
1030   _LIBCPP_HIDE_FROM_ABI char_type translate(char_type __c) const { return __c; }
1031   char_type translate_nocase(char_type __c) const;
1032   template <class _ForwardIterator>
1033   string_type transform(_ForwardIterator __f, _ForwardIterator __l) const;
1034   template <class _ForwardIterator>
1035   _LIBCPP_HIDE_FROM_ABI string_type transform_primary(_ForwardIterator __f, _ForwardIterator __l) const {
1036     return __transform_primary(__f, __l, char_type());
1037   }
1038   template <class _ForwardIterator>
1039   _LIBCPP_HIDE_FROM_ABI string_type lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const {
1040     return __lookup_collatename(__f, __l, char_type());
1041   }
1042   template <class _ForwardIterator>
1043   _LIBCPP_HIDE_FROM_ABI char_class_type
1044   lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase = false) const {
1045     return __lookup_classname(__f, __l, __icase, char_type());
1046   }
1047   bool isctype(char_type __c, char_class_type __m) const;
1048   _LIBCPP_HIDE_FROM_ABI int value(char_type __ch, int __radix) const { return __regex_traits_value(__ch, __radix); }
1049   locale_type imbue(locale_type __l);
1050   _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __loc_; }
1051
1052 private:
1053   void __init();
1054
1055   template <class _ForwardIterator>
1056   string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
1057 #if _LIBCPP_HAS_WIDE_CHARACTERS
1058   template <class _ForwardIterator>
1059   string_type __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
1060 #endif
1061   template <class _ForwardIterator>
1062   string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
1063 #if _LIBCPP_HAS_WIDE_CHARACTERS
1064   template <class _ForwardIterator>
1065   string_type __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
1066 #endif
1067   template <class _ForwardIterator>
1068   char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, char) const;
1069 #if _LIBCPP_HAS_WIDE_CHARACTERS
1070   template <class _ForwardIterator>
1071   char_class_type __lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, wchar_t) const;
1072 #endif
1073
1074   static int __regex_traits_value(unsigned char __ch, int __radix);
1075   _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(char __ch, int __radix) const {
1076     return __regex_traits_value(static_cast<unsigned char>(__ch), __radix);
1077   }
1078 #if _LIBCPP_HAS_WIDE_CHARACTERS
1079   _LIBCPP_HIDE_FROM_ABI int __regex_traits_value(wchar_t __ch, int __radix) const;
1080 #endif
1081 };
1082
1083 template <class _CharT>
1084 const typename regex_traits<_CharT>::char_class_type regex_traits<_CharT>::__regex_word;
1085
1086 template <class _CharT>
1087 regex_traits<_CharT>::regex_traits() {
1088   __init();
1089 }
1090
1091 template <class _CharT>
1092 typename regex_traits<_CharT>::char_type regex_traits<_CharT>::translate_nocase(char_type __c) const {
1093   return __ct_->tolower(__c);
1094 }
1095
1096 template <class _CharT>
1097 template <class _ForwardIterator>
1098 typename regex_traits<_CharT>::string_type
1099 regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const {
1100   string_type __s(__f, __l);
1101   return __col_->transform(__s.data(), __s.data() + __s.size());
1102 }
1103
1104 template <class _CharT>
1105 void regex_traits<_CharT>::__init() {
1106   __ct_  = &std::use_facet<ctype<char_type> >(__loc_);
1107   __col_ = &std::use_facet<collate<char_type> >(__loc_);
1108 }
1109
1110 template <class _CharT>
1111 typename regex_traits<_CharT>::locale_type regex_traits<_CharT>::imbue(locale_type __l) {
1112   locale __r = __loc_;
1113   __loc_     = __l;
1114   __init();
1115   return __r;
1116 }
1117
1118 // transform_primary is very FreeBSD-specific
1119
1120 template <class _CharT>
1121 template <class _ForwardIterator>
1122 typename regex_traits<_CharT>::string_type
1123 regex_traits<_CharT>::__transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const {
1124   const string_type __s(__f, __l);
1125   string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
1126   switch (__d.size()) {
1127   case 1:
1128     break;
1129   case 12:
1130     __d[11] = __d[3];
1131     break;
1132   default:
1133     __d.clear();
1134     break;
1135   }
1136   return __d;
1137 }
1138
1139 #if _LIBCPP_HAS_WIDE_CHARACTERS
1140 template <class _CharT>
1141 template <class _ForwardIterator>
1142 typename regex_traits<_CharT>::string_type
1143 regex_traits<_CharT>::__transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const {
1144   const string_type __s(__f, __l);
1145   string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
1146   switch (__d.size()) {
1147   case 1:
1148     break;
1149   case 3:
1150     __d[2] = __d[0];
1151     break;
1152   default:
1153     __d.clear();
1154     break;
1155   }
1156   return __d;
1157 }
1158 #endif
1159
1160 // lookup_collatename is very FreeBSD-specific
1161
1162 _LIBCPP_EXPORTED_FROM_ABI string __get_collation_name(const char* __s);
1163
1164 template <class _CharT>
1165 template <class _ForwardIterator>
1166 typename regex_traits<_CharT>::string_type
1167 regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const {
1168   string_type __s(__f, __l);
1169   string_type __r;
1170   if (!__s.empty()) {
1171     __r = std::__get_collation_name(__s.c_str());
1172     if (__r.empty() && __s.size() <= 2) {
1173       __r = __col_->transform(__s.data(), __s.data() + __s.size());
1174       if (__r.size() == 1 || __r.size() == 12)
1175         __r = __s;
1176       else
1177         __r.clear();
1178     }
1179   }
1180   return __r;
1181 }
1182
1183 #if _LIBCPP_HAS_WIDE_CHARACTERS
1184 template <class _CharT>
1185 template <class _ForwardIterator>
1186 typename regex_traits<_CharT>::string_type
1187 regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const {
1188   string_type __s(__f, __l);
1189   string __n;
1190   __n.reserve(__s.size());
1191   for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end(); __i != __e; ++__i) {
1192     if (static_cast<unsigned>(*__i) >= 127)
1193       return string_type();
1194     __n.push_back(char(*__i));
1195   }
1196   string_type __r;
1197   if (!__s.empty()) {
1198     __n = __get_collation_name(__n.c_str());
1199     if (!__n.empty())
1200       __r.assign(__n.begin(), __n.end());
1201     else if (__s.size() <= 2) {
1202       __r = __col_->transform(__s.data(), __s.data() + __s.size());
1203       if (__r.size() == 1 || __r.size() == 3)
1204         __r = __s;
1205       else
1206         __r.clear();
1207     }
1208   }
1209   return __r;
1210 }
1211 #endif // _LIBCPP_HAS_WIDE_CHARACTERS
1212
1213 // lookup_classname
1214
1215 regex_traits<char>::char_class_type _LIBCPP_EXPORTED_FROM_ABI __get_classname(const char* __s, bool __icase);
1216
1217 template <class _CharT>
1218 template <class _ForwardIterator>
1219 typename regex_traits<_CharT>::char_class_type
1220 regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, char) const {
1221   string_type __s(__f, __l);
1222   __ct_->tolower(&__s[0], &__s[0] + __s.size());
1223   return std::__get_classname(__s.c_str(), __icase);
1224 }
1225
1226 #if _LIBCPP_HAS_WIDE_CHARACTERS
1227 template <class _CharT>
1228 template <class _ForwardIterator>
1229 typename regex_traits<_CharT>::char_class_type
1230 regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f, _ForwardIterator __l, bool __icase, wchar_t) const {
1231   string_type __s(__f, __l);
1232   __ct_->tolower(&__s[0], &__s[0] + __s.size());
1233   string __n;
1234   __n.reserve(__s.size());
1235   for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end(); __i != __e; ++__i) {
1236     if (static_cast<unsigned>(*__i) >= 127)
1237       return char_class_type();
1238     __n.push_back(char(*__i));
1239   }
1240   return __get_classname(__n.c_str(), __icase);
1241 }
1242 #endif // _LIBCPP_HAS_WIDE_CHARACTERS
1243
1244 template <class _CharT>
1245 bool regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const {
1246   if (__ct_->is(__m, __c))
1247     return true;
1248   return (__c == '_' && (__m & __regex_word));
1249 }
1250
1251 inline _LIBCPP_HIDE_FROM_ABI bool __is_07(unsigned char __c) {
1252   return (__c & 0xF8u) ==
1253 #if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
1254          0xF0;
1255 #else
1256          0x30;
1257 #endif
1258 }
1259
1260 inline _LIBCPP_HIDE_FROM_ABI bool __is_89(unsigned char __c) {
1261   return (__c & 0xFEu) ==
1262 #if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
1263          0xF8;
1264 #else
1265          0x38;
1266 #endif
1267 }
1268
1269 inline _LIBCPP_HIDE_FROM_ABI unsigned char __to_lower(unsigned char __c) {
1270 #if defined(__MVS__) && !defined(__NATIVE_ASCII_F)
1271   return __c & 0xBF;
1272 #else
1273   return __c | 0x20;
1274 #endif
1275 }
1276
1277 template <class _CharT>
1278 int regex_traits<_CharT>::__regex_traits_value(unsigned char __ch, int __radix) {
1279   if (__is_07(__ch)) // '0' <= __ch && __ch <= '7'
1280     return __ch - '0';
1281   if (__radix != 8) {
1282     if (__is_89(__ch)) // '8' <= __ch && __ch <= '9'
1283       return __ch - '0';
1284     if (__radix == 16) {
1285       __ch = __to_lower(__ch); // tolower
1286       if ('a' <= __ch && __ch <= 'f')
1287         return __ch - ('a' - 10);
1288     }
1289   }
1290   return -1;
1291 }
1292
1293 #if _LIBCPP_HAS_WIDE_CHARACTERS
1294 template <class _CharT>
1295 inline int regex_traits<_CharT>::__regex_traits_value(wchar_t __ch, int __radix) const {
1296   return __regex_traits_value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
1297 }
1298 #endif
1299
1300 template <class _CharT>
1301 class __node;
1302
1303 template <class _BidirectionalIterator>
1304 class _LIBCPP_TEMPLATE_VIS sub_match;
1305
1306 template <class _BidirectionalIterator, class _Allocator = allocator<sub_match<_BidirectionalIterator> > >
1307 class _LIBCPP_TEMPLATE_VIS match_results;
1308
1309 template <class _CharT>
1310 struct __state {
1311   enum {
1312     __end_state = -1000,
1313     __consume_input,          // -999
1314     __begin_marked_expr,      // -998
1315     __end_marked_expr,        // -997
1316     __pop_state,              // -996
1317     __accept_and_consume,     // -995
1318     __accept_but_not_consume, // -994
1319     __reject,                 // -993
1320     __split,
1321     __repeat
1322   };
1323
1324   int __do_;
1325   const _CharT* __first_;
1326   const _CharT* __current_;
1327   const _CharT* __last_;
1328   vector<sub_match<const _CharT*> > __sub_matches_;
1329   vector<pair<size_t, const _CharT*> > __loop_data_;
1330   const __node<_CharT>* __node_;
1331   regex_constants::match_flag_type __flags_;
1332   bool __at_first_;
1333
1334   _LIBCPP_HIDE_FROM_ABI __state()
1335       : __do_(0),
1336         __first_(nullptr),
1337         __current_(nullptr),
1338         __last_(nullptr),
1339         __node_(nullptr),
1340         __flags_(),
1341         __at_first_(false) {}
1342 };
1343
1344 // __node
1345
1346 template <class _CharT>
1347 class __node {
1348 public:
1349   typedef std::__state<_CharT> __state;
1350
1351   _LIBCPP_HIDE_FROM_ABI __node() {}
1352   __node(const __node&)            = delete;
1353   __node& operator=(const __node&) = delete;
1354   _LIBCPP_HIDE_FROM_ABI_VIRTUAL
1355   virtual ~__node() {}
1356
1357   _LIBCPP_HIDE_FROM_ABI_VIRTUAL
1358   virtual void __exec(__state&) const {}
1359   _LIBCPP_HIDE_FROM_ABI_VIRTUAL
1360   virtual void __exec_split(bool, __state&) const {}
1361 };
1362
1363 // __end_state
1364
1365 template <class _CharT>
1366 class __end_state : public __node<_CharT> {
1367 public:
1368   typedef std::__state<_CharT> __state;
1369
1370   _LIBCPP_HIDE_FROM_ABI __end_state() {}
1371
1372   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1373 };
1374
1375 template <class _CharT>
1376 void __end_state<_CharT>::__exec(__state& __s) const {
1377   __s.__do_ = __state::__end_state;
1378 }
1379
1380 // __has_one_state
1381
1382 template <class _CharT>
1383 class __has_one_state : public __node<_CharT> {
1384   __node<_CharT>* __first_;
1385
1386 public:
1387   _LIBCPP_HIDE_FROM_ABI explicit __has_one_state(__node<_CharT>* __s) : __first_(__s) {}
1388
1389   _LIBCPP_HIDE_FROM_ABI __node<_CharT>* first() const { return __first_; }
1390   _LIBCPP_HIDE_FROM_ABI __node<_CharT>*& first() { return __first_; }
1391 };
1392
1393 // __owns_one_state
1394
1395 template <class _CharT>
1396 class __owns_one_state : public __has_one_state<_CharT> {
1397   typedef __has_one_state<_CharT> base;
1398
1399 public:
1400   _LIBCPP_HIDE_FROM_ABI explicit __owns_one_state(__node<_CharT>* __s) : base(__s) {}
1401
1402   ~__owns_one_state() override;
1403 };
1404
1405 template <class _CharT>
1406 __owns_one_state<_CharT>::~__owns_one_state() {
1407   delete this->first();
1408 }
1409
1410 // __empty_state
1411
1412 template <class _CharT>
1413 class __empty_state : public __owns_one_state<_CharT> {
1414   typedef __owns_one_state<_CharT> base;
1415
1416 public:
1417   typedef std::__state<_CharT> __state;
1418
1419   _LIBCPP_HIDE_FROM_ABI explicit __empty_state(__node<_CharT>* __s) : base(__s) {}
1420
1421   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1422 };
1423
1424 template <class _CharT>
1425 void __empty_state<_CharT>::__exec(__state& __s) const {
1426   __s.__do_   = __state::__accept_but_not_consume;
1427   __s.__node_ = this->first();
1428 }
1429
1430 // __empty_non_own_state
1431
1432 template <class _CharT>
1433 class __empty_non_own_state : public __has_one_state<_CharT> {
1434   typedef __has_one_state<_CharT> base;
1435
1436 public:
1437   typedef std::__state<_CharT> __state;
1438
1439   _LIBCPP_HIDE_FROM_ABI explicit __empty_non_own_state(__node<_CharT>* __s) : base(__s) {}
1440
1441   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1442 };
1443
1444 template <class _CharT>
1445 void __empty_non_own_state<_CharT>::__exec(__state& __s) const {
1446   __s.__do_   = __state::__accept_but_not_consume;
1447   __s.__node_ = this->first();
1448 }
1449
1450 // __repeat_one_loop
1451
1452 template <class _CharT>
1453 class __repeat_one_loop : public __has_one_state<_CharT> {
1454   typedef __has_one_state<_CharT> base;
1455
1456 public:
1457   typedef std::__state<_CharT> __state;
1458
1459   _LIBCPP_HIDE_FROM_ABI explicit __repeat_one_loop(__node<_CharT>* __s) : base(__s) {}
1460
1461   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1462 };
1463
1464 template <class _CharT>
1465 void __repeat_one_loop<_CharT>::__exec(__state& __s) const {
1466   __s.__do_   = __state::__repeat;
1467   __s.__node_ = this->first();
1468 }
1469
1470 // __owns_two_states
1471
1472 template <class _CharT>
1473 class __owns_two_states : public __owns_one_state<_CharT> {
1474   typedef __owns_one_state<_CharT> base;
1475
1476   base* __second_;
1477
1478 public:
1479   _LIBCPP_HIDE_FROM_ABI explicit __owns_two_states(__node<_CharT>* __s1, base* __s2) : base(__s1), __second_(__s2) {}
1480
1481   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual ~__owns_two_states();
1482
1483   _LIBCPP_HIDE_FROM_ABI base* second() const { return __second_; }
1484   _LIBCPP_HIDE_FROM_ABI base*& second() { return __second_; }
1485 };
1486
1487 template <class _CharT>
1488 __owns_two_states<_CharT>::~__owns_two_states() {
1489   delete __second_;
1490 }
1491
1492 // __loop
1493
1494 template <class _CharT>
1495 class __loop : public __owns_two_states<_CharT> {
1496   typedef __owns_two_states<_CharT> base;
1497
1498   size_t __min_;
1499   size_t __max_;
1500   unsigned __loop_id_;
1501   unsigned __mexp_begin_;
1502   unsigned __mexp_end_;
1503   bool __greedy_;
1504
1505 public:
1506   typedef std::__state<_CharT> __state;
1507
1508   _LIBCPP_HIDE_FROM_ABI explicit __loop(
1509       unsigned __loop_id,
1510       __node<_CharT>* __s1,
1511       __owns_one_state<_CharT>* __s2,
1512       unsigned __mexp_begin,
1513       unsigned __mexp_end,
1514       bool __greedy = true,
1515       size_t __min  = 0,
1516       size_t __max  = numeric_limits<size_t>::max())
1517       : base(__s1, __s2),
1518         __min_(__min),
1519         __max_(__max),
1520         __loop_id_(__loop_id),
1521         __mexp_begin_(__mexp_begin),
1522         __mexp_end_(__mexp_end),
1523         __greedy_(__greedy) {}
1524
1525   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;
1526   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec_split(bool __second, __state& __s) const;
1527
1528 private:
1529   _LIBCPP_HIDE_FROM_ABI void __init_repeat(__state& __s) const {
1530     __s.__loop_data_[__loop_id_].second = __s.__current_;
1531     for (size_t __i = __mexp_begin_ - 1; __i != __mexp_end_ - 1; ++__i) {
1532       __s.__sub_matches_[__i].first   = __s.__last_;
1533       __s.__sub_matches_[__i].second  = __s.__last_;
1534       __s.__sub_matches_[__i].matched = false;
1535     }
1536   }
1537 };
1538
1539 template <class _CharT>
1540 void __loop<_CharT>::__exec(__state& __s) const {
1541   if (__s.__do_ == __state::__repeat) {
1542     bool __do_repeat = ++__s.__loop_data_[__loop_id_].first < __max_;
1543     bool __do_alt    = __s.__loop_data_[__loop_id_].first >= __min_;
1544     if (__do_repeat && __do_alt && __s.__loop_data_[__loop_id_].second == __s.__current_)
1545       __do_repeat = false;
1546     if (__do_repeat && __do_alt)
1547       __s.__do_ = __state::__split;
1548     else if (__do_repeat) {
1549       __s.__do_   = __state::__accept_but_not_consume;
1550       __s.__node_ = this->first();
1551       __init_repeat(__s);
1552     } else {
1553       __s.__do_   = __state::__accept_but_not_consume;
1554       __s.__node_ = this->second();
1555     }
1556   } else {
1557     __s.__loop_data_[__loop_id_].first = 0;
1558     bool __do_repeat                   = 0 < __max_;
1559     bool __do_alt                      = 0 >= __min_;
1560     if (__do_repeat && __do_alt)
1561       __s.__do_ = __state::__split;
1562     else if (__do_repeat) {
1563       __s.__do_   = __state::__accept_but_not_consume;
1564       __s.__node_ = this->first();
1565       __init_repeat(__s);
1566     } else {
1567       __s.__do_   = __state::__accept_but_not_consume;
1568       __s.__node_ = this->second();
1569     }
1570   }
1571 }
1572
1573 template <class _CharT>
1574 void __loop<_CharT>::__exec_split(bool __second, __state& __s) const {
1575   __s.__do_ = __state::__accept_but_not_consume;
1576   if (__greedy_ != __second) {
1577     __s.__node_ = this->first();
1578     __init_repeat(__s);
1579   } else
1580     __s.__node_ = this->second();
1581 }
1582
1583 // __alternate
1584
1585 template <class _CharT>
1586 class __alternate : public __owns_two_states<_CharT> {
1587   typedef __owns_two_states<_CharT> base;
1588
1589 public:
1590   typedef std::__state<_CharT> __state;
1591
1592   _LIBCPP_HIDE_FROM_ABI explicit __alternate(__owns_one_state<_CharT>* __s1, __owns_one_state<_CharT>* __s2)
1593       : base(__s1, __s2) {}
1594
1595   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state& __s) const;
1596   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec_split(bool __second, __state& __s) const;
1597 };
1598
1599 template <class _CharT>
1600 void __alternate<_CharT>::__exec(__state& __s) const {
1601   __s.__do_ = __state::__split;
1602 }
1603
1604 template <class _CharT>
1605 void __alternate<_CharT>::__exec_split(bool __second, __state& __s) const {
1606   __s.__do_ = __state::__accept_but_not_consume;
1607   if (__second)
1608     __s.__node_ = this->second();
1609   else
1610     __s.__node_ = this->first();
1611 }
1612
1613 // __begin_marked_subexpression
1614
1615 template <class _CharT>
1616 class __begin_marked_subexpression : public __owns_one_state<_CharT> {
1617   typedef __owns_one_state<_CharT> base;
1618
1619   unsigned __mexp_;
1620
1621 public:
1622   typedef std::__state<_CharT> __state;
1623
1624   _LIBCPP_HIDE_FROM_ABI explicit __begin_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
1625       : base(__s), __mexp_(__mexp) {}
1626
1627   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1628 };
1629
1630 template <class _CharT>
1631 void __begin_marked_subexpression<_CharT>::__exec(__state& __s) const {
1632   __s.__do_                             = __state::__accept_but_not_consume;
1633   __s.__sub_matches_[__mexp_ - 1].first = __s.__current_;
1634   __s.__node_                           = this->first();
1635 }
1636
1637 // __end_marked_subexpression
1638
1639 template <class _CharT>
1640 class __end_marked_subexpression : public __owns_one_state<_CharT> {
1641   typedef __owns_one_state<_CharT> base;
1642
1643   unsigned __mexp_;
1644
1645 public:
1646   typedef std::__state<_CharT> __state;
1647
1648   _LIBCPP_HIDE_FROM_ABI explicit __end_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
1649       : base(__s), __mexp_(__mexp) {}
1650
1651   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1652 };
1653
1654 template <class _CharT>
1655 void __end_marked_subexpression<_CharT>::__exec(__state& __s) const {
1656   __s.__do_                               = __state::__accept_but_not_consume;
1657   __s.__sub_matches_[__mexp_ - 1].second  = __s.__current_;
1658   __s.__sub_matches_[__mexp_ - 1].matched = true;
1659   __s.__node_                             = this->first();
1660 }
1661
1662 // __back_ref
1663
1664 template <class _CharT>
1665 class __back_ref : public __owns_one_state<_CharT> {
1666   typedef __owns_one_state<_CharT> base;
1667
1668   unsigned __mexp_;
1669
1670 public:
1671   typedef std::__state<_CharT> __state;
1672
1673   _LIBCPP_HIDE_FROM_ABI explicit __back_ref(unsigned __mexp, __node<_CharT>* __s) : base(__s), __mexp_(__mexp) {}
1674
1675   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1676 };
1677
1678 template <class _CharT>
1679 void __back_ref<_CharT>::__exec(__state& __s) const {
1680   if (__mexp_ > __s.__sub_matches_.size())
1681     __throw_regex_error<regex_constants::error_backref>();
1682   sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];
1683   if (__sm.matched) {
1684     ptrdiff_t __len = __sm.second - __sm.first;
1685     if (__s.__last_ - __s.__current_ >= __len && std::equal(__sm.first, __sm.second, __s.__current_)) {
1686       __s.__do_ = __state::__accept_but_not_consume;
1687       __s.__current_ += __len;
1688       __s.__node_ = this->first();
1689     } else {
1690       __s.__do_   = __state::__reject;
1691       __s.__node_ = nullptr;
1692     }
1693   } else {
1694     __s.__do_   = __state::__reject;
1695     __s.__node_ = nullptr;
1696   }
1697 }
1698
1699 // __back_ref_icase
1700
1701 template <class _CharT, class _Traits>
1702 class __back_ref_icase : public __owns_one_state<_CharT> {
1703   typedef __owns_one_state<_CharT> base;
1704
1705   _Traits __traits_;
1706   unsigned __mexp_;
1707
1708 public:
1709   typedef std::__state<_CharT> __state;
1710
1711   _LIBCPP_HIDE_FROM_ABI explicit __back_ref_icase(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)
1712       : base(__s), __traits_(__traits), __mexp_(__mexp) {}
1713
1714   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1715 };
1716
1717 template <class _CharT, class _Traits>
1718 void __back_ref_icase<_CharT, _Traits>::__exec(__state& __s) const {
1719   sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];
1720   if (__sm.matched) {
1721     ptrdiff_t __len = __sm.second - __sm.first;
1722     if (__s.__last_ - __s.__current_ >= __len) {
1723       for (ptrdiff_t __i = 0; __i < __len; ++__i) {
1724         if (__traits_.translate_nocase(__sm.first[__i]) != __traits_.translate_nocase(__s.__current_[__i]))
1725           goto __not_equal;
1726       }
1727       __s.__do_ = __state::__accept_but_not_consume;
1728       __s.__current_ += __len;
1729       __s.__node_ = this->first();
1730     } else {
1731       __s.__do_   = __state::__reject;
1732       __s.__node_ = nullptr;
1733     }
1734   } else {
1735   __not_equal:
1736     __s.__do_   = __state::__reject;
1737     __s.__node_ = nullptr;
1738   }
1739 }
1740
1741 // __back_ref_collate
1742
1743 template <class _CharT, class _Traits>
1744 class __back_ref_collate : public __owns_one_state<_CharT> {
1745   typedef __owns_one_state<_CharT> base;
1746
1747   _Traits __traits_;
1748   unsigned __mexp_;
1749
1750 public:
1751   typedef std::__state<_CharT> __state;
1752
1753   _LIBCPP_HIDE_FROM_ABI explicit __back_ref_collate(const _Traits& __traits, unsigned __mexp, __node<_CharT>* __s)
1754       : base(__s), __traits_(__traits), __mexp_(__mexp) {}
1755
1756   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1757 };
1758
1759 template <class _CharT, class _Traits>
1760 void __back_ref_collate<_CharT, _Traits>::__exec(__state& __s) const {
1761   sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_ - 1];
1762   if (__sm.matched) {
1763     ptrdiff_t __len = __sm.second - __sm.first;
1764     if (__s.__last_ - __s.__current_ >= __len) {
1765       for (ptrdiff_t __i = 0; __i < __len; ++__i) {
1766         if (__traits_.translate(__sm.first[__i]) != __traits_.translate(__s.__current_[__i]))
1767           goto __not_equal;
1768       }
1769       __s.__do_ = __state::__accept_but_not_consume;
1770       __s.__current_ += __len;
1771       __s.__node_ = this->first();
1772     } else {
1773       __s.__do_   = __state::__reject;
1774       __s.__node_ = nullptr;
1775     }
1776   } else {
1777   __not_equal:
1778     __s.__do_   = __state::__reject;
1779     __s.__node_ = nullptr;
1780   }
1781 }
1782
1783 // __word_boundary
1784
1785 template <class _CharT, class _Traits>
1786 class __word_boundary : public __owns_one_state<_CharT> {
1787   typedef __owns_one_state<_CharT> base;
1788
1789   _Traits __traits_;
1790   bool __invert_;
1791
1792 public:
1793   typedef std::__state<_CharT> __state;
1794
1795   _LIBCPP_HIDE_FROM_ABI explicit __word_boundary(const _Traits& __traits, bool __invert, __node<_CharT>* __s)
1796       : base(__s), __traits_(__traits), __invert_(__invert) {}
1797
1798   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1799 };
1800
1801 template <class _CharT, class _Traits>
1802 void __word_boundary<_CharT, _Traits>::__exec(__state& __s) const {
1803   bool __is_word_b = false;
1804   if (__s.__first_ != __s.__last_) {
1805     if (__s.__current_ == __s.__last_) {
1806       if (!(__s.__flags_ & regex_constants::match_not_eow)) {
1807         _CharT __c  = __s.__current_[-1];
1808         __is_word_b = __c == '_' || __traits_.isctype(__c, ctype_base::alnum);
1809       }
1810     } else if (__s.__current_ == __s.__first_ && !(__s.__flags_ & regex_constants::match_prev_avail)) {
1811       if (!(__s.__flags_ & regex_constants::match_not_bow)) {
1812         _CharT __c  = *__s.__current_;
1813         __is_word_b = __c == '_' || __traits_.isctype(__c, ctype_base::alnum);
1814       }
1815     } else {
1816       _CharT __c1    = __s.__current_[-1];
1817       _CharT __c2    = *__s.__current_;
1818       bool __is_c1_b = __c1 == '_' || __traits_.isctype(__c1, ctype_base::alnum);
1819       bool __is_c2_b = __c2 == '_' || __traits_.isctype(__c2, ctype_base::alnum);
1820       __is_word_b    = __is_c1_b != __is_c2_b;
1821     }
1822   }
1823   if (__is_word_b != __invert_) {
1824     __s.__do_   = __state::__accept_but_not_consume;
1825     __s.__node_ = this->first();
1826   } else {
1827     __s.__do_   = __state::__reject;
1828     __s.__node_ = nullptr;
1829   }
1830 }
1831
1832 // __l_anchor
1833
1834 template <class _CharT>
1835 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool __is_eol(_CharT __c) {
1836   return __c == '\r' || __c == '\n';
1837 }
1838
1839 template <class _CharT>
1840 class __l_anchor_multiline : public __owns_one_state<_CharT> {
1841   typedef __owns_one_state<_CharT> base;
1842
1843   bool __multiline_;
1844
1845 public:
1846   typedef std::__state<_CharT> __state;
1847
1848   _LIBCPP_HIDE_FROM_ABI __l_anchor_multiline(bool __multiline, __node<_CharT>* __s)
1849       : base(__s), __multiline_(__multiline) {}
1850
1851   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1852 };
1853
1854 template <class _CharT>
1855 void __l_anchor_multiline<_CharT>::__exec(__state& __s) const {
1856   if (__s.__at_first_ && __s.__current_ == __s.__first_ && !(__s.__flags_ & regex_constants::match_not_bol)) {
1857     __s.__do_   = __state::__accept_but_not_consume;
1858     __s.__node_ = this->first();
1859   } else if (__multiline_ && !__s.__at_first_ && std::__is_eol(*std::prev(__s.__current_))) {
1860     __s.__do_   = __state::__accept_but_not_consume;
1861     __s.__node_ = this->first();
1862   } else {
1863     __s.__do_   = __state::__reject;
1864     __s.__node_ = nullptr;
1865   }
1866 }
1867
1868 // __r_anchor
1869
1870 template <class _CharT>
1871 class __r_anchor_multiline : public __owns_one_state<_CharT> {
1872   typedef __owns_one_state<_CharT> base;
1873
1874   bool __multiline_;
1875
1876 public:
1877   typedef std::__state<_CharT> __state;
1878
1879   _LIBCPP_HIDE_FROM_ABI __r_anchor_multiline(bool __multiline, __node<_CharT>* __s)
1880       : base(__s), __multiline_(__multiline) {}
1881
1882   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1883 };
1884
1885 template <class _CharT>
1886 void __r_anchor_multiline<_CharT>::__exec(__state& __s) const {
1887   if (__s.__current_ == __s.__last_ && !(__s.__flags_ & regex_constants::match_not_eol)) {
1888     __s.__do_   = __state::__accept_but_not_consume;
1889     __s.__node_ = this->first();
1890   } else if (__multiline_ && std::__is_eol(*__s.__current_)) {
1891     __s.__do_   = __state::__accept_but_not_consume;
1892     __s.__node_ = this->first();
1893   } else {
1894     __s.__do_   = __state::__reject;
1895     __s.__node_ = nullptr;
1896   }
1897 }
1898
1899 // __match_any
1900
1901 template <class _CharT>
1902 class __match_any : public __owns_one_state<_CharT> {
1903   typedef __owns_one_state<_CharT> base;
1904
1905 public:
1906   typedef std::__state<_CharT> __state;
1907
1908   _LIBCPP_HIDE_FROM_ABI __match_any(__node<_CharT>* __s) : base(__s) {}
1909
1910   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1911 };
1912
1913 template <class _CharT>
1914 void __match_any<_CharT>::__exec(__state& __s) const {
1915   if (__s.__current_ != __s.__last_ && *__s.__current_ != 0) {
1916     __s.__do_ = __state::__accept_and_consume;
1917     ++__s.__current_;
1918     __s.__node_ = this->first();
1919   } else {
1920     __s.__do_   = __state::__reject;
1921     __s.__node_ = nullptr;
1922   }
1923 }
1924
1925 // __match_any_but_newline
1926
1927 template <class _CharT>
1928 class __match_any_but_newline : public __owns_one_state<_CharT> {
1929   typedef __owns_one_state<_CharT> base;
1930
1931 public:
1932   typedef std::__state<_CharT> __state;
1933
1934   _LIBCPP_HIDE_FROM_ABI __match_any_but_newline(__node<_CharT>* __s) : base(__s) {}
1935
1936   void __exec(__state&) const override;
1937 };
1938
1939 template <>
1940 _LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<char>::__exec(__state&) const;
1941 #if _LIBCPP_HAS_WIDE_CHARACTERS
1942 template <>
1943 _LIBCPP_EXPORTED_FROM_ABI void __match_any_but_newline<wchar_t>::__exec(__state&) const;
1944 #endif
1945
1946 // __match_char
1947
1948 template <class _CharT>
1949 class __match_char : public __owns_one_state<_CharT> {
1950   typedef __owns_one_state<_CharT> base;
1951
1952   _CharT __c_;
1953
1954 public:
1955   typedef std::__state<_CharT> __state;
1956
1957   _LIBCPP_HIDE_FROM_ABI __match_char(_CharT __c, __node<_CharT>* __s) : base(__s), __c_(__c) {}
1958
1959   __match_char(const __match_char&)            = delete;
1960   __match_char& operator=(const __match_char&) = delete;
1961
1962   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1963 };
1964
1965 template <class _CharT>
1966 void __match_char<_CharT>::__exec(__state& __s) const {
1967   if (__s.__current_ != __s.__last_ && *__s.__current_ == __c_) {
1968     __s.__do_ = __state::__accept_and_consume;
1969     ++__s.__current_;
1970     __s.__node_ = this->first();
1971   } else {
1972     __s.__do_   = __state::__reject;
1973     __s.__node_ = nullptr;
1974   }
1975 }
1976
1977 // __match_char_icase
1978
1979 template <class _CharT, class _Traits>
1980 class __match_char_icase : public __owns_one_state<_CharT> {
1981   typedef __owns_one_state<_CharT> base;
1982
1983   _Traits __traits_;
1984   _CharT __c_;
1985
1986 public:
1987   typedef std::__state<_CharT> __state;
1988
1989   _LIBCPP_HIDE_FROM_ABI __match_char_icase(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
1990       : base(__s), __traits_(__traits), __c_(__traits.translate_nocase(__c)) {}
1991
1992   __match_char_icase(const __match_char_icase&)            = delete;
1993   __match_char_icase& operator=(const __match_char_icase&) = delete;
1994
1995   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
1996 };
1997
1998 template <class _CharT, class _Traits>
1999 void __match_char_icase<_CharT, _Traits>::__exec(__state& __s) const {
2000   if (__s.__current_ != __s.__last_ && __traits_.translate_nocase(*__s.__current_) == __c_) {
2001     __s.__do_ = __state::__accept_and_consume;
2002     ++__s.__current_;
2003     __s.__node_ = this->first();
2004   } else {
2005     __s.__do_   = __state::__reject;
2006     __s.__node_ = nullptr;
2007   }
2008 }
2009
2010 // __match_char_collate
2011
2012 template <class _CharT, class _Traits>
2013 class __match_char_collate : public __owns_one_state<_CharT> {
2014   typedef __owns_one_state<_CharT> base;
2015
2016   _Traits __traits_;
2017   _CharT __c_;
2018
2019 public:
2020   typedef std::__state<_CharT> __state;
2021
2022   _LIBCPP_HIDE_FROM_ABI __match_char_collate(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
2023       : base(__s), __traits_(__traits), __c_(__traits.translate(__c)) {}
2024
2025   __match_char_collate(const __match_char_collate&)            = delete;
2026   __match_char_collate& operator=(const __match_char_collate&) = delete;
2027
2028   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
2029 };
2030
2031 template <class _CharT, class _Traits>
2032 void __match_char_collate<_CharT, _Traits>::__exec(__state& __s) const {
2033   if (__s.__current_ != __s.__last_ && __traits_.translate(*__s.__current_) == __c_) {
2034     __s.__do_ = __state::__accept_and_consume;
2035     ++__s.__current_;
2036     __s.__node_ = this->first();
2037   } else {
2038     __s.__do_   = __state::__reject;
2039     __s.__node_ = nullptr;
2040   }
2041 }
2042
2043 // __bracket_expression
2044
2045 template <class _CharT, class _Traits>
2046 class __bracket_expression : public __owns_one_state<_CharT> {
2047   typedef __owns_one_state<_CharT> base;
2048   typedef typename _Traits::string_type string_type;
2049
2050   _Traits __traits_;
2051   vector<_CharT> __chars_;
2052   vector<_CharT> __neg_chars_;
2053   vector<pair<string_type, string_type> > __ranges_;
2054   vector<pair<_CharT, _CharT> > __digraphs_;
2055   vector<string_type> __equivalences_;
2056   typename regex_traits<_CharT>::char_class_type __mask_;
2057   typename regex_traits<_CharT>::char_class_type __neg_mask_;
2058   bool __negate_;
2059   bool __icase_;
2060   bool __collate_;
2061   bool __might_have_digraph_;
2062
2063 public:
2064   typedef std::__state<_CharT> __state;
2065
2066   _LIBCPP_HIDE_FROM_ABI
2067   __bracket_expression(const _Traits& __traits, __node<_CharT>* __s, bool __negate, bool __icase, bool __collate)
2068       : base(__s),
2069         __traits_(__traits),
2070         __mask_(),
2071         __neg_mask_(),
2072         __negate_(__negate),
2073         __icase_(__icase),
2074         __collate_(__collate),
2075         __might_have_digraph_(__traits_.getloc().name() != "C") {}
2076
2077   __bracket_expression(const __bracket_expression&)            = delete;
2078   __bracket_expression& operator=(const __bracket_expression&) = delete;
2079
2080   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
2081
2082   _LIBCPP_HIDE_FROM_ABI bool __negated() const { return __negate_; }
2083
2084   _LIBCPP_HIDE_FROM_ABI void __add_char(_CharT __c) {
2085     if (__icase_)
2086       __chars_.push_back(__traits_.translate_nocase(__c));
2087     else if (__collate_)
2088       __chars_.push_back(__traits_.translate(__c));
2089     else
2090       __chars_.push_back(__c);
2091   }
2092   _LIBCPP_HIDE_FROM_ABI void __add_neg_char(_CharT __c) {
2093     if (__icase_)
2094       __neg_chars_.push_back(__traits_.translate_nocase(__c));
2095     else if (__collate_)
2096       __neg_chars_.push_back(__traits_.translate(__c));
2097     else
2098       __neg_chars_.push_back(__c);
2099   }
2100   _LIBCPP_HIDE_FROM_ABI void __add_range(string_type __b, string_type __e) {
2101     if (__collate_) {
2102       if (__icase_) {
2103         for (size_t __i = 0; __i < __b.size(); ++__i)
2104           __b[__i] = __traits_.translate_nocase(__b[__i]);
2105         for (size_t __i = 0; __i < __e.size(); ++__i)
2106           __e[__i] = __traits_.translate_nocase(__e[__i]);
2107       } else {
2108         for (size_t __i = 0; __i < __b.size(); ++__i)
2109           __b[__i] = __traits_.translate(__b[__i]);
2110         for (size_t __i = 0; __i < __e.size(); ++__i)
2111           __e[__i] = __traits_.translate(__e[__i]);
2112       }
2113       __ranges_.push_back(
2114           std::make_pair(__traits_.transform(__b.begin(), __b.end()), __traits_.transform(__e.begin(), __e.end())));
2115     } else {
2116       if (__b.size() != 1 || __e.size() != 1)
2117         __throw_regex_error<regex_constants::error_range>();
2118       if (__icase_) {
2119         __b[0] = __traits_.translate_nocase(__b[0]);
2120         __e[0] = __traits_.translate_nocase(__e[0]);
2121       }
2122       __ranges_.push_back(std::make_pair(std::move(__b), std::move(__e)));
2123     }
2124   }
2125   _LIBCPP_HIDE_FROM_ABI void __add_digraph(_CharT __c1, _CharT __c2) {
2126     if (__icase_)
2127       __digraphs_.push_back(std::make_pair(__traits_.translate_nocase(__c1), __traits_.translate_nocase(__c2)));
2128     else if (__collate_)
2129       __digraphs_.push_back(std::make_pair(__traits_.translate(__c1), __traits_.translate(__c2)));
2130     else
2131       __digraphs_.push_back(std::make_pair(__c1, __c2));
2132   }
2133   _LIBCPP_HIDE_FROM_ABI void __add_equivalence(const string_type& __s) { __equivalences_.push_back(__s); }
2134   _LIBCPP_HIDE_FROM_ABI void __add_class(typename regex_traits<_CharT>::char_class_type __mask) { __mask_ |= __mask; }
2135   _LIBCPP_HIDE_FROM_ABI void __add_neg_class(typename regex_traits<_CharT>::char_class_type __mask) {
2136     __neg_mask_ |= __mask;
2137   }
2138 };
2139
2140 template <class _CharT, class _Traits>
2141 void __bracket_expression<_CharT, _Traits>::__exec(__state& __s) const {
2142   bool __found        = false;
2143   unsigned __consumed = 0;
2144   if (__s.__current_ != __s.__last_) {
2145     ++__consumed;
2146     if (__might_have_digraph_) {
2147       const _CharT* __next = std::next(__s.__current_);
2148       if (__next != __s.__last_) {
2149         pair<_CharT, _CharT> __ch2(*__s.__current_, *__next);
2150         if (__icase_) {
2151           __ch2.first  = __traits_.translate_nocase(__ch2.first);
2152           __ch2.second = __traits_.translate_nocase(__ch2.second);
2153         } else if (__collate_) {
2154           __ch2.first  = __traits_.translate(__ch2.first);
2155           __ch2.second = __traits_.translate(__ch2.second);
2156         }
2157         if (!__traits_.lookup_collatename(&__ch2.first, &__ch2.first + 2).empty()) {
2158           // __ch2 is a digraph in this locale
2159           ++__consumed;
2160           for (size_t __i = 0; __i < __digraphs_.size(); ++__i) {
2161             if (__ch2 == __digraphs_[__i]) {
2162               __found = true;
2163               goto __exit;
2164             }
2165           }
2166           if (__collate_ && !__ranges_.empty()) {
2167             string_type __s2 = __traits_.transform(&__ch2.first, &__ch2.first + 2);
2168             for (size_t __i = 0; __i < __ranges_.size(); ++__i) {
2169               if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second) {
2170                 __found = true;
2171                 goto __exit;
2172               }
2173             }
2174           }
2175           if (!__equivalences_.empty()) {
2176             string_type __s2 = __traits_.transform_primary(&__ch2.first, &__ch2.first + 2);
2177             for (size_t __i = 0; __i < __equivalences_.size(); ++__i) {
2178               if (__s2 == __equivalences_[__i]) {
2179                 __found = true;
2180                 goto __exit;
2181               }
2182             }
2183           }
2184           if (__traits_.isctype(__ch2.first, __mask_) && __traits_.isctype(__ch2.second, __mask_)) {
2185             __found = true;
2186             goto __exit;
2187           }
2188           if (!__traits_.isctype(__ch2.first, __neg_mask_) && !__traits_.isctype(__ch2.second, __neg_mask_)) {
2189             __found = true;
2190             goto __exit;
2191           }
2192           goto __exit;
2193         }
2194       }
2195     }
2196     // test *__s.__current_ as not a digraph
2197     _CharT __ch = *__s.__current_;
2198     if (__icase_)
2199       __ch = __traits_.translate_nocase(__ch);
2200     else if (__collate_)
2201       __ch = __traits_.translate(__ch);
2202     for (size_t __i = 0; __i < __chars_.size(); ++__i) {
2203       if (__ch == __chars_[__i]) {
2204         __found = true;
2205         goto __exit;
2206       }
2207     }
2208     // When there's at least one of __neg_chars_ and __neg_mask_, the set
2209     // of "__found" chars is
2210     //   union(complement(union(__neg_chars_, __neg_mask_)),
2211     //         other cases...)
2212     //
2213     // It doesn't make sense to check this when there are no __neg_chars_
2214     // and no __neg_mask_.
2215     if (!(__neg_mask_ == 0 && __neg_chars_.empty())) {
2216       const bool __in_neg_mask  = __traits_.isctype(__ch, __neg_mask_);
2217       const bool __in_neg_chars = std::find(__neg_chars_.begin(), __neg_chars_.end(), __ch) != __neg_chars_.end();
2218       if (!(__in_neg_mask || __in_neg_chars)) {
2219         __found = true;
2220         goto __exit;
2221       }
2222     }
2223     if (!__ranges_.empty()) {
2224       string_type __s2 = __collate_ ? __traits_.transform(&__ch, &__ch + 1) : string_type(1, __ch);
2225       for (size_t __i = 0; __i < __ranges_.size(); ++__i) {
2226         if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second) {
2227           __found = true;
2228           goto __exit;
2229         }
2230       }
2231     }
2232     if (!__equivalences_.empty()) {
2233       string_type __s2 = __traits_.transform_primary(&__ch, &__ch + 1);
2234       for (size_t __i = 0; __i < __equivalences_.size(); ++__i) {
2235         if (__s2 == __equivalences_[__i]) {
2236           __found = true;
2237           goto __exit;
2238         }
2239       }
2240     }
2241     if (__traits_.isctype(__ch, __mask_)) {
2242       __found = true;
2243       goto __exit;
2244     }
2245   } else
2246     __found = __negate_; // force reject
2247 __exit:
2248   if (__found != __negate_) {
2249     __s.__do_ = __state::__accept_and_consume;
2250     __s.__current_ += __consumed;
2251     __s.__node_ = this->first();
2252   } else {
2253     __s.__do_   = __state::__reject;
2254     __s.__node_ = nullptr;
2255   }
2256 }
2257
2258 template <class _CharT, class _Traits>
2259 class __lookahead;
2260
2261 template <class _CharT, class _Traits = regex_traits<_CharT> >
2262 class _LIBCPP_TEMPLATE_VIS basic_regex;
2263
2264 typedef basic_regex<char> regex;
2265 #if _LIBCPP_HAS_WIDE_CHARACTERS
2266 typedef basic_regex<wchar_t> wregex;
2267 #endif
2268
2269 template <class _CharT, class _Traits>
2270 class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(regex)
2271     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wregex)) basic_regex {
2272 public:
2273   // types:
2274   typedef _CharT value_type;
2275   typedef _Traits traits_type;
2276   typedef typename _Traits::string_type string_type;
2277   typedef regex_constants::syntax_option_type flag_type;
2278   typedef typename _Traits::locale_type locale_type;
2279
2280 private:
2281   _Traits __traits_;
2282   flag_type __flags_;
2283   unsigned __marked_count_;
2284   unsigned __loop_count_;
2285   int __open_count_;
2286   shared_ptr<__empty_state<_CharT> > __start_;
2287   __owns_one_state<_CharT>* __end_;
2288
2289   typedef std::__state<_CharT> __state;
2290   typedef std::__node<_CharT> __node;
2291
2292 public:
2293   // constants:
2294   static const regex_constants::syntax_option_type icase      = regex_constants::icase;
2295   static const regex_constants::syntax_option_type nosubs     = regex_constants::nosubs;
2296   static const regex_constants::syntax_option_type optimize   = regex_constants::optimize;
2297   static const regex_constants::syntax_option_type collate    = regex_constants::collate;
2298   static const regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
2299   static const regex_constants::syntax_option_type basic      = regex_constants::basic;
2300   static const regex_constants::syntax_option_type extended   = regex_constants::extended;
2301   static const regex_constants::syntax_option_type awk        = regex_constants::awk;
2302   static const regex_constants::syntax_option_type grep       = regex_constants::grep;
2303   static const regex_constants::syntax_option_type egrep      = regex_constants::egrep;
2304   static const regex_constants::syntax_option_type multiline  = regex_constants::multiline;
2305
2306   // construct/copy/destroy:
2307   _LIBCPP_HIDE_FROM_ABI basic_regex()
2308       : __flags_(regex_constants::ECMAScript),
2309         __marked_count_(0),
2310         __loop_count_(0),
2311         __open_count_(0),
2312         __end_(nullptr) {}
2313   _LIBCPP_HIDE_FROM_ABI explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
2314       : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
2315     __init(__p, __p + __traits_.length(__p));
2316   }
2317
2318   _LIBCPP_HIDE_FROM_ABI basic_regex(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript)
2319       : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
2320     __init(__p, __p + __len);
2321   }
2322
2323   //     basic_regex(const basic_regex&) = default;
2324   //     basic_regex(basic_regex&&) = default;
2325   template <class _ST, class _SA>
2326   _LIBCPP_HIDE_FROM_ABI explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
2327                                              flag_type __f = regex_constants::ECMAScript)
2328       : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
2329     __init(__p.begin(), __p.end());
2330   }
2331
2332   template <class _ForwardIterator>
2333   _LIBCPP_HIDE_FROM_ABI
2334   basic_regex(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript)
2335       : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
2336     __init(__first, __last);
2337   }
2338 #ifndef _LIBCPP_CXX03_LANG
2339   _LIBCPP_HIDE_FROM_ABI basic_regex(initializer_list<value_type> __il, flag_type __f = regex_constants::ECMAScript)
2340       : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0), __end_(nullptr) {
2341     __init(__il.begin(), __il.end());
2342   }
2343 #endif // _LIBCPP_CXX03_LANG
2344
2345   //    ~basic_regex() = default;
2346
2347   //     basic_regex& operator=(const basic_regex&) = default;
2348   //     basic_regex& operator=(basic_regex&&) = default;
2349   _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const value_type* __p) { return assign(__p); }
2350 #ifndef _LIBCPP_CXX03_LANG
2351   _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(initializer_list<value_type> __il) { return assign(__il); }
2352 #endif // _LIBCPP_CXX03_LANG
2353   template <class _ST, class _SA>
2354   _LIBCPP_HIDE_FROM_ABI basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p) {
2355     return assign(__p);
2356   }
2357
2358   // assign:
2359   _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const basic_regex& __that) { return *this = __that; }
2360 #ifndef _LIBCPP_CXX03_LANG
2361   _LIBCPP_HIDE_FROM_ABI basic_regex& assign(basic_regex&& __that) _NOEXCEPT { return *this = std::move(__that); }
2362 #endif
2363   _LIBCPP_HIDE_FROM_ABI basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript) {
2364     return assign(__p, __p + __traits_.length(__p), __f);
2365   }
2366   _LIBCPP_HIDE_FROM_ABI basic_regex&
2367   assign(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript) {
2368     return assign(__p, __p + __len, __f);
2369   }
2370   template <class _ST, class _SA>
2371   _LIBCPP_HIDE_FROM_ABI basic_regex&
2372   assign(const basic_string<value_type, _ST, _SA>& __s, flag_type __f = regex_constants::ECMAScript) {
2373     return assign(__s.begin(), __s.end(), __f);
2374   }
2375
2376   template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
2377   _LIBCPP_HIDE_FROM_ABI basic_regex&
2378   assign(_InputIterator __first, _InputIterator __last, flag_type __f = regex_constants::ECMAScript) {
2379     basic_string<_CharT> __t(__first, __last);
2380     return assign(__t.begin(), __t.end(), __f);
2381   }
2382
2383 private:
2384   _LIBCPP_HIDE_FROM_ABI void __member_init(flag_type __f) {
2385     __flags_        = __f;
2386     __marked_count_ = 0;
2387     __loop_count_   = 0;
2388     __open_count_   = 0;
2389     __end_          = nullptr;
2390   }
2391
2392 public:
2393   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2394   _LIBCPP_HIDE_FROM_ABI basic_regex&
2395   assign(_ForwardIterator __first, _ForwardIterator __last, flag_type __f = regex_constants::ECMAScript) {
2396     return assign(basic_regex(__first, __last, __f));
2397   }
2398
2399 #ifndef _LIBCPP_CXX03_LANG
2400
2401   _LIBCPP_HIDE_FROM_ABI basic_regex&
2402   assign(initializer_list<value_type> __il, flag_type __f = regex_constants::ECMAScript) {
2403     return assign(__il.begin(), __il.end(), __f);
2404   }
2405
2406 #endif // _LIBCPP_CXX03_LANG
2407
2408   // const operations:
2409   _LIBCPP_HIDE_FROM_ABI unsigned mark_count() const { return __marked_count_; }
2410   _LIBCPP_HIDE_FROM_ABI flag_type flags() const { return __flags_; }
2411
2412   // locale:
2413   _LIBCPP_HIDE_FROM_ABI locale_type imbue(locale_type __loc) {
2414     __member_init(ECMAScript);
2415     __start_.reset();
2416     return __traits_.imbue(__loc);
2417   }
2418   _LIBCPP_HIDE_FROM_ABI locale_type getloc() const { return __traits_.getloc(); }
2419
2420   // swap:
2421   void swap(basic_regex& __r);
2422
2423 private:
2424   _LIBCPP_HIDE_FROM_ABI unsigned __loop_count() const { return __loop_count_; }
2425
2426   _LIBCPP_HIDE_FROM_ABI bool __use_multiline() const {
2427     return __get_grammar(__flags_) == ECMAScript && (__flags_ & multiline);
2428   }
2429
2430   template <class _ForwardIterator>
2431   void __init(_ForwardIterator __first, _ForwardIterator __last);
2432   template <class _ForwardIterator>
2433   _ForwardIterator __parse(_ForwardIterator __first, _ForwardIterator __last);
2434   template <class _ForwardIterator>
2435   _ForwardIterator __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2436   template <class _ForwardIterator>
2437   _ForwardIterator __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
2438   template <class _ForwardIterator>
2439   _ForwardIterator __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
2440   template <class _ForwardIterator>
2441   _ForwardIterator __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
2442   template <class _ForwardIterator>
2443   _ForwardIterator __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
2444   template <class _ForwardIterator>
2445   _ForwardIterator __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
2446   template <class _ForwardIterator>
2447   _ForwardIterator __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
2448   template <class _ForwardIterator>
2449   _ForwardIterator __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
2450   template <class _ForwardIterator>
2451   _ForwardIterator __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
2452   template <class _ForwardIterator>
2453   _ForwardIterator __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
2454   template <class _ForwardIterator>
2455   _ForwardIterator __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2456   template <class _ForwardIterator>
2457   _ForwardIterator __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2458   template <class _ForwardIterator>
2459   _ForwardIterator __parse_RE_dupl_symbol(
2460       _ForwardIterator __first,
2461       _ForwardIterator __last,
2462       __owns_one_state<_CharT>* __s,
2463       unsigned __mexp_begin,
2464       unsigned __mexp_end);
2465   template <class _ForwardIterator>
2466   _ForwardIterator __parse_ERE_dupl_symbol(
2467       _ForwardIterator __first,
2468       _ForwardIterator __last,
2469       __owns_one_state<_CharT>* __s,
2470       unsigned __mexp_begin,
2471       unsigned __mexp_end);
2472   template <class _ForwardIterator>
2473   _ForwardIterator __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
2474   template <class _ForwardIterator>
2475   _ForwardIterator
2476   __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);
2477   template <class _ForwardIterator>
2478   _ForwardIterator __parse_expression_term(
2479       _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);
2480   template <class _ForwardIterator>
2481   _ForwardIterator __parse_equivalence_class(
2482       _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);
2483   template <class _ForwardIterator>
2484   _ForwardIterator __parse_character_class(
2485       _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml);
2486   template <class _ForwardIterator>
2487   _ForwardIterator
2488   __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>& __col_sym);
2489   template <class _ForwardIterator>
2490   _ForwardIterator __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
2491   template <class _ForwardIterator>
2492   _ForwardIterator __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2493   template <class _ForwardIterator>
2494   _ForwardIterator __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
2495   template <class _ForwardIterator>
2496   _ForwardIterator __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
2497   template <class _ForwardIterator>
2498   _ForwardIterator __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
2499   template <class _ForwardIterator>
2500   _ForwardIterator __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2501   template <class _ForwardIterator>
2502   _ForwardIterator __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2503   template <class _ForwardIterator>
2504   _ForwardIterator __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);
2505   template <class _ForwardIterator>
2506   _ForwardIterator __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);
2507   template <class _ForwardIterator>
2508   _ForwardIterator __parse_term(_ForwardIterator __first, _ForwardIterator __last);
2509   template <class _ForwardIterator>
2510   _ForwardIterator __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);
2511   template <class _ForwardIterator>
2512   _ForwardIterator __parse_atom(_ForwardIterator __first, _ForwardIterator __last);
2513   template <class _ForwardIterator>
2514   _ForwardIterator __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);
2515   template <class _ForwardIterator>
2516   _ForwardIterator __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);
2517   template <class _ForwardIterator>
2518   _ForwardIterator __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);
2519   template <class _ForwardIterator>
2520   _ForwardIterator
2521   __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str = nullptr);
2522   template <class _ForwardIterator>
2523   _ForwardIterator __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);
2524   template <class _ForwardIterator>
2525   _ForwardIterator __parse_grep(_ForwardIterator __first, _ForwardIterator __last);
2526   template <class _ForwardIterator>
2527   _ForwardIterator __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);
2528   template <class _ForwardIterator>
2529   _ForwardIterator __parse_class_escape(
2530       _ForwardIterator __first,
2531       _ForwardIterator __last,
2532       basic_string<_CharT>& __str,
2533       __bracket_expression<_CharT, _Traits>* __ml);
2534   template <class _ForwardIterator>
2535   _ForwardIterator
2536   __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str = nullptr);
2537
2538   bool __test_back_ref(_CharT);
2539
2540   _LIBCPP_HIDE_FROM_ABI void __push_l_anchor();
2541   void __push_r_anchor();
2542   void __push_match_any();
2543   void __push_match_any_but_newline();
2544   _LIBCPP_HIDE_FROM_ABI void __push_greedy_inf_repeat(
2545       size_t __min, __owns_one_state<_CharT>* __s, unsigned __mexp_begin = 0, unsigned __mexp_end = 0) {
2546     __push_loop(__min, numeric_limits<size_t>::max(), __s, __mexp_begin, __mexp_end);
2547   }
2548   _LIBCPP_HIDE_FROM_ABI void __push_nongreedy_inf_repeat(
2549       size_t __min, __owns_one_state<_CharT>* __s, unsigned __mexp_begin = 0, unsigned __mexp_end = 0) {
2550     __push_loop(__min, numeric_limits<size_t>::max(), __s, __mexp_begin, __mexp_end, false);
2551   }
2552   void __push_loop(size_t __min,
2553                    size_t __max,
2554                    __owns_one_state<_CharT>* __s,
2555                    size_t __mexp_begin = 0,
2556                    size_t __mexp_end   = 0,
2557                    bool __greedy       = true);
2558   __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);
2559   void __push_char(value_type __c);
2560   void __push_back_ref(int __i);
2561   void __push_alternation(__owns_one_state<_CharT>* __sa, __owns_one_state<_CharT>* __sb);
2562   void __push_begin_marked_subexpression();
2563   void __push_end_marked_subexpression(unsigned);
2564   void __push_empty();
2565   void __push_word_boundary(bool);
2566   void __push_lookahead(const basic_regex&, bool, unsigned);
2567
2568   template <class _Allocator>
2569   bool __search(const _CharT* __first,
2570                 const _CharT* __last,
2571                 match_results<const _CharT*, _Allocator>& __m,
2572                 regex_constants::match_flag_type __flags) const;
2573
2574   template <class _Allocator>
2575   bool __match_at_start(const _CharT* __first,
2576                         const _CharT* __last,
2577                         match_results<const _CharT*, _Allocator>& __m,
2578                         regex_constants::match_flag_type __flags,
2579                         bool) const;
2580   template <class _Allocator>
2581   bool __match_at_start_ecma(
2582       const _CharT* __first,
2583       const _CharT* __last,
2584       match_results<const _CharT*, _Allocator>& __m,
2585       regex_constants::match_flag_type __flags,
2586       bool) const;
2587   template <class _Allocator>
2588   bool __match_at_start_posix_nosubs(
2589       const _CharT* __first,
2590       const _CharT* __last,
2591       match_results<const _CharT*, _Allocator>& __m,
2592       regex_constants::match_flag_type __flags,
2593       bool) const;
2594   template <class _Allocator>
2595   bool __match_at_start_posix_subs(
2596       const _CharT* __first,
2597       const _CharT* __last,
2598       match_results<const _CharT*, _Allocator>& __m,
2599       regex_constants::match_flag_type __flags,
2600       bool) const;
2601
2602   template <class _Bp, class _Ap, class _Cp, class _Tp>
2603   friend bool
2604   regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2605
2606   template <class _Ap, class _Cp, class _Tp>
2607   friend bool
2608   regex_search(const _Cp*,
2609                const _Cp*,
2610                match_results<const _Cp*, _Ap>&,
2611                const basic_regex<_Cp, _Tp>&,
2612                regex_constants::match_flag_type);
2613
2614   template <class _Bp, class _Cp, class _Tp>
2615   friend bool regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2616
2617   template <class _Cp, class _Tp>
2618   friend bool regex_search(const _Cp*, const _Cp*, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2619
2620   template <class _Cp, class _Ap, class _Tp>
2621   friend bool regex_search(
2622       const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2623
2624   template <class _ST, class _SA, class _Cp, class _Tp>
2625   friend bool regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2626                            const basic_regex<_Cp, _Tp>& __e,
2627                            regex_constants::match_flag_type __flags);
2628
2629   template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
2630   friend bool regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2631                            match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
2632                            const basic_regex<_Cp, _Tp>& __e,
2633                            regex_constants::match_flag_type __flags);
2634
2635   template <class _Iter, class _Ap, class _Cp, class _Tp>
2636   friend bool
2637   regex_search(__wrap_iter<_Iter> __first,
2638                __wrap_iter<_Iter> __last,
2639                match_results<__wrap_iter<_Iter>, _Ap>& __m,
2640                const basic_regex<_Cp, _Tp>& __e,
2641                regex_constants::match_flag_type __flags);
2642
2643   template <class, class>
2644   friend class __lookahead;
2645 };
2646
2647 #if _LIBCPP_STD_VER >= 17
2648 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2649 basic_regex(_ForwardIterator, _ForwardIterator, regex_constants::syntax_option_type = regex_constants::ECMAScript)
2650     -> basic_regex<typename iterator_traits<_ForwardIterator>::value_type>;
2651 #endif
2652
2653 template <class _CharT, class _Traits>
2654 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;
2655 template <class _CharT, class _Traits>
2656 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;
2657 template <class _CharT, class _Traits>
2658 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;
2659 template <class _CharT, class _Traits>
2660 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;
2661 template <class _CharT, class _Traits>
2662 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;
2663 template <class _CharT, class _Traits>
2664 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;
2665 template <class _CharT, class _Traits>
2666 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;
2667 template <class _CharT, class _Traits>
2668 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;
2669 template <class _CharT, class _Traits>
2670 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;
2671 template <class _CharT, class _Traits>
2672 const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;
2673
2674 template <class _CharT, class _Traits>
2675 void basic_regex<_CharT, _Traits>::swap(basic_regex& __r) {
2676   using std::swap;
2677   swap(__traits_, __r.__traits_);
2678   swap(__flags_, __r.__flags_);
2679   swap(__marked_count_, __r.__marked_count_);
2680   swap(__loop_count_, __r.__loop_count_);
2681   swap(__open_count_, __r.__open_count_);
2682   swap(__start_, __r.__start_);
2683   swap(__end_, __r.__end_);
2684 }
2685
2686 template <class _CharT, class _Traits>
2687 inline _LIBCPP_HIDE_FROM_ABI void swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y) {
2688   return __x.swap(__y);
2689 }
2690
2691 // __lookahead
2692
2693 template <class _CharT, class _Traits>
2694 class __lookahead : public __owns_one_state<_CharT> {
2695   typedef __owns_one_state<_CharT> base;
2696
2697   basic_regex<_CharT, _Traits> __exp_;
2698   unsigned __mexp_;
2699   bool __invert_;
2700
2701 public:
2702   typedef std::__state<_CharT> __state;
2703
2704   _LIBCPP_HIDE_FROM_ABI
2705   __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
2706       : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}
2707
2708   __lookahead(const __lookahead&)            = delete;
2709   __lookahead& operator=(const __lookahead&) = delete;
2710
2711   _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
2712 };
2713
2714 template <class _CharT, class _Traits>
2715 void __lookahead<_CharT, _Traits>::__exec(__state& __s) const {
2716   match_results<const _CharT*> __m;
2717   __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);
2718   bool __matched = __exp_.__match_at_start_ecma(
2719       __s.__current_,
2720       __s.__last_,
2721       __m,
2722       (__s.__flags_ | regex_constants::match_continuous) & ~regex_constants::__full_match,
2723       __s.__at_first_ && __s.__current_ == __s.__first_);
2724   if (__matched != __invert_) {
2725     __s.__do_   = __state::__accept_but_not_consume;
2726     __s.__node_ = this->first();
2727     for (unsigned __i = 1; __i < __m.size(); ++__i) {
2728       __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
2729     }
2730   } else {
2731     __s.__do_   = __state::__reject;
2732     __s.__node_ = nullptr;
2733   }
2734 }
2735
2736 template <class _CharT, class _Traits>
2737 template <class _ForwardIterator>
2738 void basic_regex<_CharT, _Traits>::__init(_ForwardIterator __first, _ForwardIterator __last) {
2739   if (__get_grammar(__flags_) == 0)
2740     __flags_ |= regex_constants::ECMAScript;
2741   _ForwardIterator __temp = __parse(__first, __last);
2742   if (__temp != __last)
2743     __throw_regex_error<regex_constants::__re_err_parse>();
2744 }
2745
2746 template <class _CharT, class _Traits>
2747 template <class _ForwardIterator>
2748 _ForwardIterator basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first, _ForwardIterator __last) {
2749   {
2750     unique_ptr<__node> __h(new __end_state<_CharT>);
2751     __start_.reset(new __empty_state<_CharT>(__h.get()));
2752     __h.release();
2753     __end_ = __start_.get();
2754   }
2755   switch (__get_grammar(__flags_)) {
2756   case ECMAScript:
2757     __first = __parse_ecma_exp(__first, __last);
2758     break;
2759   case basic:
2760     __first = __parse_basic_reg_exp(__first, __last);
2761     break;
2762   case extended:
2763   case awk:
2764     __first = __parse_extended_reg_exp(__first, __last);
2765     break;
2766   case grep:
2767     __first = __parse_grep(__first, __last);
2768     break;
2769   case egrep:
2770     __first = __parse_egrep(__first, __last);
2771     break;
2772   default:
2773     __throw_regex_error<regex_constants::__re_err_grammar>();
2774   }
2775   return __first;
2776 }
2777
2778 template <class _CharT, class _Traits>
2779 template <class _ForwardIterator>
2780 _ForwardIterator
2781 basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last) {
2782   if (__first != __last) {
2783     if (*__first == '^') {
2784       __push_l_anchor();
2785       ++__first;
2786     }
2787     if (__first != __last) {
2788       __first = __parse_RE_expression(__first, __last);
2789       if (__first != __last) {
2790         _ForwardIterator __temp = std::next(__first);
2791         if (__temp == __last && *__first == '$') {
2792           __push_r_anchor();
2793           ++__first;
2794         }
2795       }
2796     }
2797     if (__first != __last)
2798       __throw_regex_error<regex_constants::__re_err_empty>();
2799   }
2800   return __first;
2801 }
2802
2803 template <class _CharT, class _Traits>
2804 template <class _ForwardIterator>
2805 _ForwardIterator
2806 basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last) {
2807   __owns_one_state<_CharT>* __sa = __end_;
2808   _ForwardIterator __temp        = __parse_ERE_branch(__first, __last);
2809   if (__temp == __first)
2810     __throw_regex_error<regex_constants::__re_err_empty>();
2811   __first = __temp;
2812   while (__first != __last && *__first == '|') {
2813     __owns_one_state<_CharT>* __sb = __end_;
2814     __temp                         = __parse_ERE_branch(++__first, __last);
2815     if (__temp == __first)
2816       __throw_regex_error<regex_constants::__re_err_empty>();
2817     __push_alternation(__sa, __sb);
2818     __first = __temp;
2819   }
2820   return __first;
2821 }
2822
2823 template <class _CharT, class _Traits>
2824 template <class _ForwardIterator>
2825 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last) {
2826   _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
2827   if (__temp == __first)
2828     __throw_regex_error<regex_constants::__re_err_empty>();
2829   do {
2830     __first = __temp;
2831     __temp  = __parse_ERE_expression(__first, __last);
2832   } while (__temp != __first);
2833   return __first;
2834 }
2835
2836 template <class _CharT, class _Traits>
2837 template <class _ForwardIterator>
2838 _ForwardIterator
2839 basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last) {
2840   __owns_one_state<_CharT>* __e = __end_;
2841   unsigned __mexp_begin         = __marked_count_;
2842   _ForwardIterator __temp       = __parse_one_char_or_coll_elem_ERE(__first, __last);
2843   if (__temp == __first && __temp != __last) {
2844     switch (*__temp) {
2845     case '^':
2846       __push_l_anchor();
2847       ++__temp;
2848       break;
2849     case '$':
2850       __push_r_anchor();
2851       ++__temp;
2852       break;
2853     case '(':
2854       __push_begin_marked_subexpression();
2855       unsigned __temp_count = __marked_count_;
2856       ++__open_count_;
2857       __temp = __parse_extended_reg_exp(++__temp, __last);
2858       if (__temp == __last || *__temp != ')')
2859         __throw_regex_error<regex_constants::error_paren>();
2860       __push_end_marked_subexpression(__temp_count);
2861       --__open_count_;
2862       ++__temp;
2863       break;
2864     }
2865   }
2866   if (__temp != __first)
2867     __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);
2868   __first = __temp;
2869   return __first;
2870 }
2871
2872 template <class _CharT, class _Traits>
2873 template <class _ForwardIterator>
2874 _ForwardIterator
2875 basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last) {
2876   while (true) {
2877     _ForwardIterator __temp = __parse_simple_RE(__first, __last);
2878     if (__temp == __first)
2879       break;
2880     __first = __temp;
2881   }
2882   return __first;
2883 }
2884
2885 template <class _CharT, class _Traits>
2886 template <class _ForwardIterator>
2887 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last) {
2888   if (__first != __last) {
2889     __owns_one_state<_CharT>* __e = __end_;
2890     unsigned __mexp_begin         = __marked_count_;
2891     _ForwardIterator __temp       = __parse_nondupl_RE(__first, __last);
2892     if (__temp != __first)
2893       __first = __parse_RE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);
2894   }
2895   return __first;
2896 }
2897
2898 template <class _CharT, class _Traits>
2899 template <class _ForwardIterator>
2900 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last) {
2901   _ForwardIterator __temp = __first;
2902   __first                 = __parse_one_char_or_coll_elem_RE(__first, __last);
2903   if (__temp == __first) {
2904     __temp = __parse_Back_open_paren(__first, __last);
2905     if (__temp != __first) {
2906       __push_begin_marked_subexpression();
2907       unsigned __temp_count = __marked_count_;
2908       __first               = __parse_RE_expression(__temp, __last);
2909       __temp                = __parse_Back_close_paren(__first, __last);
2910       if (__temp == __first)
2911         __throw_regex_error<regex_constants::error_paren>();
2912       __push_end_marked_subexpression(__temp_count);
2913       __first = __temp;
2914     } else
2915       __first = __parse_BACKREF(__first, __last);
2916   }
2917   return __first;
2918 }
2919
2920 template <class _CharT, class _Traits>
2921 template <class _ForwardIterator>
2922 _ForwardIterator
2923 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last) {
2924   _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
2925   if (__temp == __first) {
2926     __temp = __parse_QUOTED_CHAR(__first, __last);
2927     if (__temp == __first) {
2928       if (__temp != __last && *__temp == '.') {
2929         __push_match_any();
2930         ++__temp;
2931       } else
2932         __temp = __parse_bracket_expression(__first, __last);
2933     }
2934   }
2935   __first = __temp;
2936   return __first;
2937 }
2938
2939 template <class _CharT, class _Traits>
2940 template <class _ForwardIterator>
2941 _ForwardIterator
2942 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last) {
2943   _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
2944   if (__temp == __first) {
2945     __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
2946     if (__temp == __first) {
2947       if (__temp != __last && *__temp == '.') {
2948         __push_match_any();
2949         ++__temp;
2950       } else
2951         __temp = __parse_bracket_expression(__first, __last);
2952     }
2953   }
2954   __first = __temp;
2955   return __first;
2956 }
2957
2958 template <class _CharT, class _Traits>
2959 template <class _ForwardIterator>
2960 _ForwardIterator
2961 basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_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
2972 template <class _CharT, class _Traits>
2973 template <class _ForwardIterator>
2974 _ForwardIterator
2975 basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last) {
2976   if (__first != __last) {
2977     _ForwardIterator __temp = std::next(__first);
2978     if (__temp != __last) {
2979       if (*__first == '\\' && *__temp == ')')
2980         __first = ++__temp;
2981     }
2982   }
2983   return __first;
2984 }
2985
2986 template <class _CharT, class _Traits>
2987 template <class _ForwardIterator>
2988 _ForwardIterator
2989 basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last) {
2990   if (__first != __last) {
2991     _ForwardIterator __temp = std::next(__first);
2992     if (__temp != __last) {
2993       if (*__first == '\\' && *__temp == '{')
2994         __first = ++__temp;
2995     }
2996   }
2997   return __first;
2998 }
2999
3000 template <class _CharT, class _Traits>
3001 template <class _ForwardIterator>
3002 _ForwardIterator
3003 basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last) {
3004   if (__first != __last) {
3005     _ForwardIterator __temp = std::next(__first);
3006     if (__temp != __last) {
3007       if (*__first == '\\' && *__temp == '}')
3008         __first = ++__temp;
3009     }
3010   }
3011   return __first;
3012 }
3013
3014 template <class _CharT, class _Traits>
3015 template <class _ForwardIterator>
3016 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last) {
3017   if (__first != __last) {
3018     _ForwardIterator __temp = std::next(__first);
3019     if (__temp != __last && *__first == '\\' && __test_back_ref(*__temp))
3020       __first = ++__temp;
3021   }
3022   return __first;
3023 }
3024
3025 template <class _CharT, class _Traits>
3026 template <class _ForwardIterator>
3027 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last) {
3028   if (__first != __last) {
3029     _ForwardIterator __temp = std::next(__first);
3030     if (__temp == __last && *__first == '$')
3031       return __first;
3032     // Not called inside a bracket
3033     if (*__first == '.' || *__first == '\\' || *__first == '[')
3034       return __first;
3035     __push_char(*__first);
3036     ++__first;
3037   }
3038   return __first;
3039 }
3040
3041 template <class _CharT, class _Traits>
3042 template <class _ForwardIterator>
3043 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last) {
3044   if (__first != __last) {
3045     switch (*__first) {
3046     case '^':
3047     case '.':
3048     case '[':
3049     case '$':
3050     case '(':
3051     case '|':
3052     case '*':
3053     case '+':
3054     case '?':
3055     case '{':
3056     case '\\':
3057       break;
3058     case ')':
3059       if (__open_count_ == 0) {
3060         __push_char(*__first);
3061         ++__first;
3062       }
3063       break;
3064     default:
3065       __push_char(*__first);
3066       ++__first;
3067       break;
3068     }
3069   }
3070   return __first;
3071 }
3072
3073 template <class _CharT, class _Traits>
3074 template <class _ForwardIterator>
3075 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last) {
3076   if (__first != __last) {
3077     _ForwardIterator __temp = std::next(__first);
3078     if (__temp != __last) {
3079       if (*__first == '\\') {
3080         switch (*__temp) {
3081         case '^':
3082         case '.':
3083         case '*':
3084         case '[':
3085         case '$':
3086         case '\\':
3087           __push_char(*__temp);
3088           __first = ++__temp;
3089           break;
3090         }
3091       }
3092     }
3093   }
3094   return __first;
3095 }
3096
3097 template <class _CharT, class _Traits>
3098 template <class _ForwardIterator>
3099 _ForwardIterator
3100 basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last) {
3101   if (__first != __last) {
3102     _ForwardIterator __temp = std::next(__first);
3103     if (__temp != __last) {
3104       if (*__first == '\\') {
3105         switch (*__temp) {
3106         case '^':
3107         case '.':
3108         case '*':
3109         case '[':
3110         case '$':
3111         case '\\':
3112         case '(':
3113         case ')':
3114         case '|':
3115         case '+':
3116         case '?':
3117         case '{':
3118         case '}':
3119           __push_char(*__temp);
3120           __first = ++__temp;
3121           break;
3122         default:
3123           if (__get_grammar(__flags_) == awk)
3124             __first = __parse_awk_escape(++__first, __last);
3125           else if (__test_back_ref(*__temp))
3126             __first = ++__temp;
3127           break;
3128         }
3129       }
3130     }
3131   }
3132   return __first;
3133 }
3134
3135 template <class _CharT, class _Traits>
3136 template <class _ForwardIterator>
3137 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(
3138     _ForwardIterator __first,
3139     _ForwardIterator __last,
3140     __owns_one_state<_CharT>* __s,
3141     unsigned __mexp_begin,
3142     unsigned __mexp_end) {
3143   if (__first != __last) {
3144     if (*__first == '*') {
3145       __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3146       ++__first;
3147     } else {
3148       _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
3149       if (__temp != __first) {
3150         int __min = 0;
3151         __first   = __temp;
3152         __temp    = __parse_DUP_COUNT(__first, __last, __min);
3153         if (__temp == __first)
3154           __throw_regex_error<regex_constants::error_badbrace>();
3155         __first = __temp;
3156         if (__first == __last)
3157           __throw_regex_error<regex_constants::error_brace>();
3158         if (*__first != ',') {
3159           __temp = __parse_Back_close_brace(__first, __last);
3160           if (__temp == __first)
3161             __throw_regex_error<regex_constants::error_brace>();
3162           __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, true);
3163           __first = __temp;
3164         } else {
3165           ++__first; // consume ','
3166           int __max = -1;
3167           __first   = __parse_DUP_COUNT(__first, __last, __max);
3168           __temp    = __parse_Back_close_brace(__first, __last);
3169           if (__temp == __first)
3170             __throw_regex_error<regex_constants::error_brace>();
3171           if (__max == -1)
3172             __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3173           else {
3174             if (__max < __min)
3175               __throw_regex_error<regex_constants::error_badbrace>();
3176             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, true);
3177           }
3178           __first = __temp;
3179         }
3180       }
3181     }
3182   }
3183   return __first;
3184 }
3185
3186 template <class _CharT, class _Traits>
3187 template <class _ForwardIterator>
3188 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(
3189     _ForwardIterator __first,
3190     _ForwardIterator __last,
3191     __owns_one_state<_CharT>* __s,
3192     unsigned __mexp_begin,
3193     unsigned __mexp_end) {
3194   if (__first != __last) {
3195     unsigned __grammar = __get_grammar(__flags_);
3196     switch (*__first) {
3197     case '*':
3198       ++__first;
3199       if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3200         ++__first;
3201         __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3202       } else
3203         __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3204       break;
3205     case '+':
3206       ++__first;
3207       if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3208         ++__first;
3209         __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3210       } else
3211         __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3212       break;
3213     case '?':
3214       ++__first;
3215       if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3216         ++__first;
3217         __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);
3218       } else
3219         __push_loop(0, 1, __s, __mexp_begin, __mexp_end);
3220       break;
3221     case '{': {
3222       int __min;
3223       _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);
3224       if (__temp == __first)
3225         __throw_regex_error<regex_constants::error_badbrace>();
3226       __first = __temp;
3227       if (__first == __last)
3228         __throw_regex_error<regex_constants::error_brace>();
3229       switch (*__first) {
3230       case '}':
3231         ++__first;
3232         if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3233           ++__first;
3234           __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);
3235         } else
3236           __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);
3237         break;
3238       case ',':
3239         ++__first;
3240         if (__first == __last)
3241           __throw_regex_error<regex_constants::error_badbrace>();
3242         if (*__first == '}') {
3243           ++__first;
3244           if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3245             ++__first;
3246             __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3247           } else
3248             __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3249         } else {
3250           int __max = -1;
3251           __temp    = __parse_DUP_COUNT(__first, __last, __max);
3252           if (__temp == __first)
3253             __throw_regex_error<regex_constants::error_brace>();
3254           __first = __temp;
3255           if (__first == __last || *__first != '}')
3256             __throw_regex_error<regex_constants::error_brace>();
3257           ++__first;
3258           if (__max < __min)
3259             __throw_regex_error<regex_constants::error_badbrace>();
3260           if (__grammar == ECMAScript && __first != __last && *__first == '?') {
3261             ++__first;
3262             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);
3263           } else
3264             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);
3265         }
3266         break;
3267       default:
3268         __throw_regex_error<regex_constants::error_badbrace>();
3269       }
3270     } break;
3271     }
3272   }
3273   return __first;
3274 }
3275
3276 template <class _CharT, class _Traits>
3277 template <class _ForwardIterator>
3278 _ForwardIterator
3279 basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last) {
3280   if (__first != __last && *__first == '[') {
3281     ++__first;
3282     if (__first == __last)
3283       __throw_regex_error<regex_constants::error_brack>();
3284     bool __negate = false;
3285     if (*__first == '^') {
3286       ++__first;
3287       __negate = true;
3288     }
3289     __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
3290     // __ml owned by *this
3291     if (__first == __last)
3292       __throw_regex_error<regex_constants::error_brack>();
3293     if (__get_grammar(__flags_) != ECMAScript && *__first == ']') {
3294       __ml->__add_char(']');
3295       ++__first;
3296     }
3297     __first = __parse_follow_list(__first, __last, __ml);
3298     if (__first == __last)
3299       __throw_regex_error<regex_constants::error_brack>();
3300     if (*__first == '-') {
3301       __ml->__add_char('-');
3302       ++__first;
3303     }
3304     if (__first == __last || *__first != ']')
3305       __throw_regex_error<regex_constants::error_brack>();
3306     ++__first;
3307   }
3308   return __first;
3309 }
3310
3311 template <class _CharT, class _Traits>
3312 template <class _ForwardIterator>
3313 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_follow_list(
3314     _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {
3315   if (__first != __last) {
3316     while (true) {
3317       _ForwardIterator __temp = __parse_expression_term(__first, __last, __ml);
3318       if (__temp == __first)
3319         break;
3320       __first = __temp;
3321     }
3322   }
3323   return __first;
3324 }
3325
3326 template <class _CharT, class _Traits>
3327 template <class _ForwardIterator>
3328 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_expression_term(
3329     _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {
3330   if (__first != __last && *__first != ']') {
3331     _ForwardIterator __temp = std::next(__first);
3332     basic_string<_CharT> __start_range;
3333     if (__temp != __last && *__first == '[') {
3334       if (*__temp == '=')
3335         return __parse_equivalence_class(++__temp, __last, __ml);
3336       else if (*__temp == ':')
3337         return __parse_character_class(++__temp, __last, __ml);
3338       else if (*__temp == '.')
3339         __first = __parse_collating_symbol(++__temp, __last, __start_range);
3340     }
3341     unsigned __grammar = __get_grammar(__flags_);
3342     if (__start_range.empty()) {
3343       if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\') {
3344         if (__grammar == ECMAScript)
3345           __first = __parse_class_escape(++__first, __last, __start_range, __ml);
3346         else
3347           __first = __parse_awk_escape(++__first, __last, &__start_range);
3348       } else {
3349         __start_range = *__first;
3350         ++__first;
3351       }
3352     }
3353     if (__first != __last && *__first != ']') {
3354       __temp = std::next(__first);
3355       if (__temp != __last && *__first == '-' && *__temp != ']') {
3356         // parse a range
3357         basic_string<_CharT> __end_range;
3358         __first = __temp;
3359         ++__temp;
3360         if (__temp != __last && *__first == '[' && *__temp == '.')
3361           __first = __parse_collating_symbol(++__temp, __last, __end_range);
3362         else {
3363           if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\') {
3364             if (__grammar == ECMAScript)
3365               __first = __parse_class_escape(++__first, __last, __end_range, __ml);
3366             else
3367               __first = __parse_awk_escape(++__first, __last, &__end_range);
3368           } else {
3369             __end_range = *__first;
3370             ++__first;
3371           }
3372         }
3373         __ml->__add_range(std::move(__start_range), std::move(__end_range));
3374       } else if (!__start_range.empty()) {
3375         if (__start_range.size() == 1)
3376           __ml->__add_char(__start_range[0]);
3377         else
3378           __ml->__add_digraph(__start_range[0], __start_range[1]);
3379       }
3380     } else if (!__start_range.empty()) {
3381       if (__start_range.size() == 1)
3382         __ml->__add_char(__start_range[0]);
3383       else
3384         __ml->__add_digraph(__start_range[0], __start_range[1]);
3385     }
3386   }
3387   return __first;
3388 }
3389
3390 template <class _CharT, class _Traits>
3391 template <class _ForwardIterator>
3392 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_class_escape(
3393     _ForwardIterator __first,
3394     _ForwardIterator __last,
3395     basic_string<_CharT>& __str,
3396     __bracket_expression<_CharT, _Traits>* __ml) {
3397   if (__first == __last)
3398     __throw_regex_error<regex_constants::error_escape>();
3399   switch (*__first) {
3400   case 0:
3401     __str = *__first;
3402     return ++__first;
3403   case 'b':
3404     __str = _CharT(8);
3405     return ++__first;
3406   case 'd':
3407     __ml->__add_class(ctype_base::digit);
3408     return ++__first;
3409   case 'D':
3410     __ml->__add_neg_class(ctype_base::digit);
3411     return ++__first;
3412   case 's':
3413     __ml->__add_class(ctype_base::space);
3414     return ++__first;
3415   case 'S':
3416     __ml->__add_neg_class(ctype_base::space);
3417     return ++__first;
3418   case 'w':
3419     __ml->__add_class(ctype_base::alnum);
3420     __ml->__add_char('_');
3421     return ++__first;
3422   case 'W':
3423     __ml->__add_neg_class(ctype_base::alnum);
3424     __ml->__add_neg_char('_');
3425     return ++__first;
3426   }
3427   __first = __parse_character_escape(__first, __last, &__str);
3428   return __first;
3429 }
3430
3431 template <class _CharT, class _Traits>
3432 template <class _ForwardIterator>
3433 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_awk_escape(
3434     _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str) {
3435   if (__first == __last)
3436     __throw_regex_error<regex_constants::error_escape>();
3437   switch (*__first) {
3438   case '\\':
3439   case '"':
3440   case '/':
3441     if (__str)
3442       *__str = *__first;
3443     else
3444       __push_char(*__first);
3445     return ++__first;
3446   case 'a':
3447     if (__str)
3448       *__str = _CharT(7);
3449     else
3450       __push_char(_CharT(7));
3451     return ++__first;
3452   case 'b':
3453     if (__str)
3454       *__str = _CharT(8);
3455     else
3456       __push_char(_CharT(8));
3457     return ++__first;
3458   case 'f':
3459     if (__str)
3460       *__str = _CharT(0xC);
3461     else
3462       __push_char(_CharT(0xC));
3463     return ++__first;
3464   case 'n':
3465     if (__str)
3466       *__str = _CharT(0xA);
3467     else
3468       __push_char(_CharT(0xA));
3469     return ++__first;
3470   case 'r':
3471     if (__str)
3472       *__str = _CharT(0xD);
3473     else
3474       __push_char(_CharT(0xD));
3475     return ++__first;
3476   case 't':
3477     if (__str)
3478       *__str = _CharT(0x9);
3479     else
3480       __push_char(_CharT(0x9));
3481     return ++__first;
3482   case 'v':
3483     if (__str)
3484       *__str = _CharT(0xB);
3485     else
3486       __push_char(_CharT(0xB));
3487     return ++__first;
3488   }
3489   if ('0' <= *__first && *__first <= '7') {
3490     unsigned __val = *__first - '0';
3491     if (++__first != __last && ('0' <= *__first && *__first <= '7')) {
3492       __val = 8 * __val + *__first - '0';
3493       if (++__first != __last && ('0' <= *__first && *__first <= '7'))
3494         __val = 8 * __val + *__first++ - '0';
3495     }
3496     if (__str)
3497       *__str = _CharT(__val);
3498     else
3499       __push_char(_CharT(__val));
3500   } else
3501     __throw_regex_error<regex_constants::error_escape>();
3502   return __first;
3503 }
3504
3505 template <class _CharT, class _Traits>
3506 template <class _ForwardIterator>
3507 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_equivalence_class(
3508     _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {
3509   // Found [=
3510   //   This means =] must exist
3511   value_type __equal_close[2] = {'=', ']'};
3512   _ForwardIterator __temp     = std::search(__first, __last, __equal_close, __equal_close + 2);
3513   if (__temp == __last)
3514     __throw_regex_error<regex_constants::error_brack>();
3515   // [__first, __temp) contains all text in [= ... =]
3516   string_type __collate_name = __traits_.lookup_collatename(__first, __temp);
3517   if (__collate_name.empty())
3518     __throw_regex_error<regex_constants::error_collate>();
3519   string_type __equiv_name = __traits_.transform_primary(__collate_name.begin(), __collate_name.end());
3520   if (!__equiv_name.empty())
3521     __ml->__add_equivalence(__equiv_name);
3522   else {
3523     switch (__collate_name.size()) {
3524     case 1:
3525       __ml->__add_char(__collate_name[0]);
3526       break;
3527     case 2:
3528       __ml->__add_digraph(__collate_name[0], __collate_name[1]);
3529       break;
3530     default:
3531       __throw_regex_error<regex_constants::error_collate>();
3532     }
3533   }
3534   __first = std::next(__temp, 2);
3535   return __first;
3536 }
3537
3538 template <class _CharT, class _Traits>
3539 template <class _ForwardIterator>
3540 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_character_class(
3541     _ForwardIterator __first, _ForwardIterator __last, __bracket_expression<_CharT, _Traits>* __ml) {
3542   // Found [:
3543   //   This means :] must exist
3544   value_type __colon_close[2] = {':', ']'};
3545   _ForwardIterator __temp     = std::search(__first, __last, __colon_close, __colon_close + 2);
3546   if (__temp == __last)
3547     __throw_regex_error<regex_constants::error_brack>();
3548   // [__first, __temp) contains all text in [: ... :]
3549   typedef typename _Traits::char_class_type char_class_type;
3550   char_class_type __class_type = __traits_.lookup_classname(__first, __temp, __flags_ & icase);
3551   if (__class_type == 0)
3552     __throw_regex_error<regex_constants::error_ctype>();
3553   __ml->__add_class(__class_type);
3554   __first = std::next(__temp, 2);
3555   return __first;
3556 }
3557
3558 template <class _CharT, class _Traits>
3559 template <class _ForwardIterator>
3560 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_collating_symbol(
3561     _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>& __col_sym) {
3562   // Found [.
3563   //   This means .] must exist
3564   value_type __dot_close[2] = {'.', ']'};
3565   _ForwardIterator __temp   = std::search(__first, __last, __dot_close, __dot_close + 2);
3566   if (__temp == __last)
3567     __throw_regex_error<regex_constants::error_brack>();
3568   // [__first, __temp) contains all text in [. ... .]
3569   __col_sym = __traits_.lookup_collatename(__first, __temp);
3570   switch (__col_sym.size()) {
3571   case 1:
3572   case 2:
3573     break;
3574   default:
3575     __throw_regex_error<regex_constants::error_collate>();
3576   }
3577   __first = std::next(__temp, 2);
3578   return __first;
3579 }
3580
3581 template <class _CharT, class _Traits>
3582 template <class _ForwardIterator>
3583 _ForwardIterator
3584 basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c) {
3585   if (__first != __last) {
3586     int __val = __traits_.value(*__first, 10);
3587     if (__val != -1) {
3588       __c = __val;
3589       for (++__first; __first != __last && (__val = __traits_.value(*__first, 10)) != -1; ++__first) {
3590         if (__c >= numeric_limits<int>::max() / 10)
3591           __throw_regex_error<regex_constants::error_badbrace>();
3592         __c *= 10;
3593         __c += __val;
3594       }
3595     }
3596   }
3597   return __first;
3598 }
3599
3600 template <class _CharT, class _Traits>
3601 template <class _ForwardIterator>
3602 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last) {
3603   __owns_one_state<_CharT>* __sa = __end_;
3604   _ForwardIterator __temp        = __parse_alternative(__first, __last);
3605   if (__temp == __first)
3606     __push_empty();
3607   __first = __temp;
3608   while (__first != __last && *__first == '|') {
3609     __owns_one_state<_CharT>* __sb = __end_;
3610     __temp                         = __parse_alternative(++__first, __last);
3611     if (__temp == __first)
3612       __push_empty();
3613     __push_alternation(__sa, __sb);
3614     __first = __temp;
3615   }
3616   return __first;
3617 }
3618
3619 template <class _CharT, class _Traits>
3620 template <class _ForwardIterator>
3621 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first, _ForwardIterator __last) {
3622   while (true) {
3623     _ForwardIterator __temp = __parse_term(__first, __last);
3624     if (__temp == __first)
3625       break;
3626     __first = __temp;
3627   }
3628   return __first;
3629 }
3630
3631 template <class _CharT, class _Traits>
3632 template <class _ForwardIterator>
3633 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first, _ForwardIterator __last) {
3634   _ForwardIterator __temp = __parse_assertion(__first, __last);
3635   if (__temp == __first) {
3636     __owns_one_state<_CharT>* __e = __end_;
3637     unsigned __mexp_begin         = __marked_count_;
3638     __temp                        = __parse_atom(__first, __last);
3639     if (__temp != __first)
3640       __first = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin + 1, __marked_count_ + 1);
3641   } else
3642     __first = __temp;
3643   return __first;
3644 }
3645
3646 template <class _CharT, class _Traits>
3647 template <class _ForwardIterator>
3648 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first, _ForwardIterator __last) {
3649   if (__first != __last) {
3650     switch (*__first) {
3651     case '^':
3652       __push_l_anchor();
3653       ++__first;
3654       break;
3655     case '$':
3656       __push_r_anchor();
3657       ++__first;
3658       break;
3659     case '\\': {
3660       _ForwardIterator __temp = std::next(__first);
3661       if (__temp != __last) {
3662         if (*__temp == 'b') {
3663           __push_word_boundary(false);
3664           __first = ++__temp;
3665         } else if (*__temp == 'B') {
3666           __push_word_boundary(true);
3667           __first = ++__temp;
3668         }
3669       }
3670     } break;
3671     case '(': {
3672       _ForwardIterator __temp = std::next(__first);
3673       if (__temp != __last && *__temp == '?') {
3674         if (++__temp != __last) {
3675           switch (*__temp) {
3676           case '=': {
3677             basic_regex __exp;
3678             __exp.__flags_  = __flags_;
3679             __temp          = __exp.__parse(++__temp, __last);
3680             unsigned __mexp = __exp.__marked_count_;
3681             __push_lookahead(std::move(__exp), false, __marked_count_);
3682             __marked_count_ += __mexp;
3683             if (__temp == __last || *__temp != ')')
3684               __throw_regex_error<regex_constants::error_paren>();
3685             __first = ++__temp;
3686           } break;
3687           case '!': {
3688             basic_regex __exp;
3689             __exp.__flags_  = __flags_;
3690             __temp          = __exp.__parse(++__temp, __last);
3691             unsigned __mexp = __exp.__marked_count_;
3692             __push_lookahead(std::move(__exp), true, __marked_count_);
3693             __marked_count_ += __mexp;
3694             if (__temp == __last || *__temp != ')')
3695               __throw_regex_error<regex_constants::error_paren>();
3696             __first = ++__temp;
3697           } break;
3698           }
3699         }
3700       }
3701     } break;
3702     }
3703   }
3704   return __first;
3705 }
3706
3707 template <class _CharT, class _Traits>
3708 template <class _ForwardIterator>
3709 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first, _ForwardIterator __last) {
3710   if (__first != __last) {
3711     switch (*__first) {
3712     case '.':
3713       __push_match_any_but_newline();
3714       ++__first;
3715       break;
3716     case '\\':
3717       __first = __parse_atom_escape(__first, __last);
3718       break;
3719     case '[':
3720       __first = __parse_bracket_expression(__first, __last);
3721       break;
3722     case '(': {
3723       ++__first;
3724       if (__first == __last)
3725         __throw_regex_error<regex_constants::error_paren>();
3726       _ForwardIterator __temp = std::next(__first);
3727       if (__temp != __last && *__first == '?' && *__temp == ':') {
3728         ++__open_count_;
3729         __first = __parse_ecma_exp(++__temp, __last);
3730         if (__first == __last || *__first != ')')
3731           __throw_regex_error<regex_constants::error_paren>();
3732         --__open_count_;
3733         ++__first;
3734       } else {
3735         __push_begin_marked_subexpression();
3736         unsigned __temp_count = __marked_count_;
3737         ++__open_count_;
3738         __first = __parse_ecma_exp(__first, __last);
3739         if (__first == __last || *__first != ')')
3740           __throw_regex_error<regex_constants::error_paren>();
3741         __push_end_marked_subexpression(__temp_count);
3742         --__open_count_;
3743         ++__first;
3744       }
3745     } break;
3746     case '*':
3747     case '+':
3748     case '?':
3749     case '{':
3750       __throw_regex_error<regex_constants::error_badrepeat>();
3751       break;
3752     default:
3753       __first = __parse_pattern_character(__first, __last);
3754       break;
3755     }
3756   }
3757   return __first;
3758 }
3759
3760 template <class _CharT, class _Traits>
3761 template <class _ForwardIterator>
3762 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last) {
3763   if (__first != __last && *__first == '\\') {
3764     _ForwardIterator __t1 = std::next(__first);
3765     if (__t1 == __last)
3766       __throw_regex_error<regex_constants::error_escape>();
3767
3768     _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
3769     if (__t2 != __t1)
3770       __first = __t2;
3771     else {
3772       __t2 = __parse_character_class_escape(__t1, __last);
3773       if (__t2 != __t1)
3774         __first = __t2;
3775       else {
3776         __t2 = __parse_character_escape(__t1, __last);
3777         if (__t2 != __t1)
3778           __first = __t2;
3779       }
3780     }
3781   }
3782   return __first;
3783 }
3784
3785 template <class _CharT, class _Traits>
3786 template <class _ForwardIterator>
3787 _ForwardIterator
3788 basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last) {
3789   if (__first != __last) {
3790     if (*__first == '0') {
3791       __push_char(_CharT());
3792       ++__first;
3793     } else if ('1' <= *__first && *__first <= '9') {
3794       unsigned __v = *__first - '0';
3795       for (++__first; __first != __last && '0' <= *__first && *__first <= '9'; ++__first) {
3796         if (__v >= numeric_limits<unsigned>::max() / 10)
3797           __throw_regex_error<regex_constants::error_backref>();
3798         __v = 10 * __v + *__first - '0';
3799       }
3800       if (__v == 0 || __v > mark_count())
3801         __throw_regex_error<regex_constants::error_backref>();
3802       __push_back_ref(__v);
3803     }
3804   }
3805   return __first;
3806 }
3807
3808 template <class _CharT, class _Traits>
3809 template <class _ForwardIterator>
3810 _ForwardIterator
3811 basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last) {
3812   if (__first != __last) {
3813     __bracket_expression<_CharT, _Traits>* __ml;
3814     switch (*__first) {
3815     case 'd':
3816       __ml = __start_matching_list(false);
3817       __ml->__add_class(ctype_base::digit);
3818       ++__first;
3819       break;
3820     case 'D':
3821       __ml = __start_matching_list(true);
3822       __ml->__add_class(ctype_base::digit);
3823       ++__first;
3824       break;
3825     case 's':
3826       __ml = __start_matching_list(false);
3827       __ml->__add_class(ctype_base::space);
3828       ++__first;
3829       break;
3830     case 'S':
3831       __ml = __start_matching_list(true);
3832       __ml->__add_class(ctype_base::space);
3833       ++__first;
3834       break;
3835     case 'w':
3836       __ml = __start_matching_list(false);
3837       __ml->__add_class(ctype_base::alnum);
3838       __ml->__add_char('_');
3839       ++__first;
3840       break;
3841     case 'W':
3842       __ml = __start_matching_list(true);
3843       __ml->__add_class(ctype_base::alnum);
3844       __ml->__add_char('_');
3845       ++__first;
3846       break;
3847     }
3848   }
3849   return __first;
3850 }
3851
3852 template <class _CharT, class _Traits>
3853 template <class _ForwardIterator>
3854 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_character_escape(
3855     _ForwardIterator __first, _ForwardIterator __last, basic_string<_CharT>* __str) {
3856   if (__first != __last) {
3857     _ForwardIterator __t;
3858     unsigned __sum = 0;
3859     int __hd;
3860     switch (*__first) {
3861     case 'f':
3862       if (__str)
3863         *__str = _CharT(0xC);
3864       else
3865         __push_char(_CharT(0xC));
3866       ++__first;
3867       break;
3868     case 'n':
3869       if (__str)
3870         *__str = _CharT(0xA);
3871       else
3872         __push_char(_CharT(0xA));
3873       ++__first;
3874       break;
3875     case 'r':
3876       if (__str)
3877         *__str = _CharT(0xD);
3878       else
3879         __push_char(_CharT(0xD));
3880       ++__first;
3881       break;
3882     case 't':
3883       if (__str)
3884         *__str = _CharT(0x9);
3885       else
3886         __push_char(_CharT(0x9));
3887       ++__first;
3888       break;
3889     case 'v':
3890       if (__str)
3891         *__str = _CharT(0xB);
3892       else
3893         __push_char(_CharT(0xB));
3894       ++__first;
3895       break;
3896     case 'c':
3897       if ((__t = std::next(__first)) != __last) {
3898         if (('A' <= *__t && *__t <= 'Z') || ('a' <= *__t && *__t <= 'z')) {
3899           if (__str)
3900             *__str = _CharT(*__t % 32);
3901           else
3902             __push_char(_CharT(*__t % 32));
3903           __first = ++__t;
3904         } else
3905           __throw_regex_error<regex_constants::error_escape>();
3906       } else
3907         __throw_regex_error<regex_constants::error_escape>();
3908       break;
3909     case 'u':
3910       ++__first;
3911       if (__first == __last)
3912         __throw_regex_error<regex_constants::error_escape>();
3913       __hd = __traits_.value(*__first, 16);
3914       if (__hd == -1)
3915         __throw_regex_error<regex_constants::error_escape>();
3916       __sum = 16 * __sum + static_cast<unsigned>(__hd);
3917       ++__first;
3918       if (__first == __last)
3919         __throw_regex_error<regex_constants::error_escape>();
3920       __hd = __traits_.value(*__first, 16);
3921       if (__hd == -1)
3922         __throw_regex_error<regex_constants::error_escape>();
3923       __sum = 16 * __sum + static_cast<unsigned>(__hd);
3924       _LIBCPP_FALLTHROUGH();
3925     case 'x':
3926       ++__first;
3927       if (__first == __last)
3928         __throw_regex_error<regex_constants::error_escape>();
3929       __hd = __traits_.value(*__first, 16);
3930       if (__hd == -1)
3931         __throw_regex_error<regex_constants::error_escape>();
3932       __sum = 16 * __sum + static_cast<unsigned>(__hd);
3933       ++__first;
3934       if (__first == __last)
3935         __throw_regex_error<regex_constants::error_escape>();
3936       __hd = __traits_.value(*__first, 16);
3937       if (__hd == -1)
3938         __throw_regex_error<regex_constants::error_escape>();
3939       __sum = 16 * __sum + static_cast<unsigned>(__hd);
3940       if (__str)
3941         *__str = _CharT(__sum);
3942       else
3943         __push_char(_CharT(__sum));
3944       ++__first;
3945       break;
3946     case '0':
3947       if (__str)
3948         *__str = _CharT(0);
3949       else
3950         __push_char(_CharT(0));
3951       ++__first;
3952       break;
3953     default:
3954       if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum)) {
3955         if (__str)
3956           *__str = *__first;
3957         else
3958           __push_char(*__first);
3959         ++__first;
3960       } else
3961         __throw_regex_error<regex_constants::error_escape>();
3962       break;
3963     }
3964   }
3965   return __first;
3966 }
3967
3968 template <class _CharT, class _Traits>
3969 template <class _ForwardIterator>
3970 _ForwardIterator
3971 basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last) {
3972   if (__first != __last) {
3973     switch (*__first) {
3974     case '^':
3975     case '$':
3976     case '\\':
3977     case '.':
3978     case '*':
3979     case '+':
3980     case '?':
3981     case '(':
3982     case ')':
3983     case '[':
3984     case ']':
3985     case '{':
3986     case '}':
3987     case '|':
3988       break;
3989     default:
3990       __push_char(*__first);
3991       ++__first;
3992       break;
3993     }
3994   }
3995   return __first;
3996 }
3997
3998 template <class _CharT, class _Traits>
3999 template <class _ForwardIterator>
4000 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first, _ForwardIterator __last) {
4001   __owns_one_state<_CharT>* __sa = __end_;
4002   _ForwardIterator __t1          = std::find(__first, __last, _CharT('\n'));
4003   if (__t1 != __first)
4004     __parse_basic_reg_exp(__first, __t1);
4005   else
4006     __push_empty();
4007   __first = __t1;
4008   if (__first != __last)
4009     ++__first;
4010   while (__first != __last) {
4011     __t1                           = std::find(__first, __last, _CharT('\n'));
4012     __owns_one_state<_CharT>* __sb = __end_;
4013     if (__t1 != __first)
4014       __parse_basic_reg_exp(__first, __t1);
4015     else
4016       __push_empty();
4017     __push_alternation(__sa, __sb);
4018     __first = __t1;
4019     if (__first != __last)
4020       ++__first;
4021   }
4022   return __first;
4023 }
4024
4025 template <class _CharT, class _Traits>
4026 template <class _ForwardIterator>
4027 _ForwardIterator basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first, _ForwardIterator __last) {
4028   __owns_one_state<_CharT>* __sa = __end_;
4029   _ForwardIterator __t1          = std::find(__first, __last, _CharT('\n'));
4030   if (__t1 != __first)
4031     __parse_extended_reg_exp(__first, __t1);
4032   else
4033     __push_empty();
4034   __first = __t1;
4035   if (__first != __last)
4036     ++__first;
4037   while (__first != __last) {
4038     __t1                           = std::find(__first, __last, _CharT('\n'));
4039     __owns_one_state<_CharT>* __sb = __end_;
4040     if (__t1 != __first)
4041       __parse_extended_reg_exp(__first, __t1);
4042     else
4043       __push_empty();
4044     __push_alternation(__sa, __sb);
4045     __first = __t1;
4046     if (__first != __last)
4047       ++__first;
4048   }
4049   return __first;
4050 }
4051
4052 template <class _CharT, class _Traits>
4053 bool basic_regex<_CharT, _Traits>::__test_back_ref(_CharT __c) {
4054   unsigned __val = __traits_.value(__c, 10);
4055   if (__val >= 1 && __val <= 9) {
4056     if (__val > mark_count())
4057       __throw_regex_error<regex_constants::error_backref>();
4058     __push_back_ref(__val);
4059     return true;
4060   }
4061
4062   return false;
4063 }
4064
4065 template <class _CharT, class _Traits>
4066 void basic_regex<_CharT, _Traits>::__push_loop(
4067     size_t __min, size_t __max, __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end, bool __greedy) {
4068   unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
4069   __end_->first() = nullptr;
4070   unique_ptr<__loop<_CharT> > __e2(
4071       new __loop<_CharT>(__loop_count_, __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy, __min, __max));
4072   __s->first() = nullptr;
4073   __e1.release();
4074   __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
4075   __end_          = __e2->second();
4076   __s->first()    = __e2.release();
4077   ++__loop_count_;
4078 }
4079
4080 template <class _CharT, class _Traits>
4081 void basic_regex<_CharT, _Traits>::__push_char(value_type __c) {
4082   if (flags() & icase)
4083     __end_->first() = new __match_char_icase<_CharT, _Traits>(__traits_, __c, __end_->first());
4084   else if (flags() & collate)
4085     __end_->first() = new __match_char_collate<_CharT, _Traits>(__traits_, __c, __end_->first());
4086   else
4087     __end_->first() = new __match_char<_CharT>(__c, __end_->first());
4088   __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4089 }
4090
4091 template <class _CharT, class _Traits>
4092 void basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression() {
4093   if (!(__flags_ & nosubs)) {
4094     __end_->first() = new __begin_marked_subexpression<_CharT>(++__marked_count_, __end_->first());
4095     __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4096   }
4097 }
4098
4099 template <class _CharT, class _Traits>
4100 void basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub) {
4101   if (!(__flags_ & nosubs)) {
4102     __end_->first() = new __end_marked_subexpression<_CharT>(__sub, __end_->first());
4103     __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4104   }
4105 }
4106
4107 template <class _CharT, class _Traits>
4108 void basic_regex<_CharT, _Traits>::__push_l_anchor() {
4109   __end_->first() = new __l_anchor_multiline<_CharT>(__use_multiline(), __end_->first());
4110   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4111 }
4112
4113 template <class _CharT, class _Traits>
4114 void basic_regex<_CharT, _Traits>::__push_r_anchor() {
4115   __end_->first() = new __r_anchor_multiline<_CharT>(__use_multiline(), __end_->first());
4116   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4117 }
4118
4119 template <class _CharT, class _Traits>
4120 void basic_regex<_CharT, _Traits>::__push_match_any() {
4121   __end_->first() = new __match_any<_CharT>(__end_->first());
4122   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4123 }
4124
4125 template <class _CharT, class _Traits>
4126 void basic_regex<_CharT, _Traits>::__push_match_any_but_newline() {
4127   __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
4128   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4129 }
4130
4131 template <class _CharT, class _Traits>
4132 void basic_regex<_CharT, _Traits>::__push_empty() {
4133   __end_->first() = new __empty_state<_CharT>(__end_->first());
4134   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4135 }
4136
4137 template <class _CharT, class _Traits>
4138 void basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert) {
4139   __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert, __end_->first());
4140   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4141 }
4142
4143 template <class _CharT, class _Traits>
4144 void basic_regex<_CharT, _Traits>::__push_back_ref(int __i) {
4145   if (flags() & icase)
4146     __end_->first() = new __back_ref_icase<_CharT, _Traits>(__traits_, __i, __end_->first());
4147   else if (flags() & collate)
4148     __end_->first() = new __back_ref_collate<_CharT, _Traits>(__traits_, __i, __end_->first());
4149   else
4150     __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
4151   __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4152 }
4153
4154 template <class _CharT, class _Traits>
4155 void basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa, __owns_one_state<_CharT>* __ea) {
4156   __sa->first() = new __alternate<_CharT>(
4157       static_cast<__owns_one_state<_CharT>*>(__sa->first()), static_cast<__owns_one_state<_CharT>*>(__ea->first()));
4158   __ea->first()   = nullptr;
4159   __ea->first()   = new __empty_state<_CharT>(__end_->first());
4160   __end_->first() = nullptr;
4161   __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
4162   __end_          = static_cast<__owns_one_state<_CharT>*>(__ea->first());
4163 }
4164
4165 template <class _CharT, class _Traits>
4166 __bracket_expression<_CharT, _Traits>* basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate) {
4167   __bracket_expression<_CharT, _Traits>* __r = new __bracket_expression<_CharT, _Traits>(
4168       __traits_, __end_->first(), __negate, __flags_ & icase, __flags_ & collate);
4169   __end_->first() = __r;
4170   __end_          = __r;
4171   return __r;
4172 }
4173
4174 template <class _CharT, class _Traits>
4175 void basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp, bool __invert, unsigned __mexp) {
4176   __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert, __end_->first(), __mexp);
4177   __end_          = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4178 }
4179
4180 // sub_match
4181
4182 typedef sub_match<const char*> csub_match;
4183 typedef sub_match<string::const_iterator> ssub_match;
4184 #if _LIBCPP_HAS_WIDE_CHARACTERS
4185 typedef sub_match<const wchar_t*> wcsub_match;
4186 typedef sub_match<wstring::const_iterator> wssub_match;
4187 #endif
4188
4189 template <class _BidirectionalIterator>
4190 class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(csub_match)
4191     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcsub_match)) _LIBCPP_PREFERRED_NAME(ssub_match)
4192         _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wssub_match)) sub_match
4193     : public pair<_BidirectionalIterator, _BidirectionalIterator> {
4194 public:
4195   typedef _BidirectionalIterator iterator;
4196   typedef typename iterator_traits<iterator>::value_type value_type;
4197   typedef typename iterator_traits<iterator>::difference_type difference_type;
4198   typedef basic_string<value_type> string_type;
4199
4200   bool matched;
4201
4202   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR sub_match() : matched() {}
4203
4204   _LIBCPP_HIDE_FROM_ABI difference_type length() const {
4205     return matched ? std::distance(this->first, this->second) : 0;
4206   }
4207   _LIBCPP_HIDE_FROM_ABI string_type str() const {
4208     return matched ? string_type(this->first, this->second) : string_type();
4209   }
4210   _LIBCPP_HIDE_FROM_ABI operator string_type() const { return str(); }
4211
4212   _LIBCPP_HIDE_FROM_ABI int compare(const sub_match& __s) const { return str().compare(__s.str()); }
4213   _LIBCPP_HIDE_FROM_ABI int compare(const string_type& __s) const { return str().compare(__s); }
4214   _LIBCPP_HIDE_FROM_ABI int compare(const value_type* __s) const { return str().compare(__s); }
4215
4216   _LIBCPP_HIDE_FROM_ABI void swap(sub_match& __s) _NOEXCEPT_(__is_nothrow_swappable_v<_BidirectionalIterator>) {
4217     this->pair<_BidirectionalIterator, _BidirectionalIterator>::swap(__s);
4218     std::swap(matched, __s.matched);
4219   }
4220 };
4221
4222 template <class _BiIter>
4223 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4224   return __x.compare(__y) == 0;
4225 }
4226
4227 #if _LIBCPP_STD_VER >= 20
4228 template <class _BiIter>
4229 using __sub_match_cat = compare_three_way_result_t<basic_string<typename iterator_traits<_BiIter>::value_type>>;
4230
4231 template <class _BiIter>
4232 _LIBCPP_HIDE_FROM_ABI auto operator<=>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4233   return static_cast<__sub_match_cat<_BiIter>>(__x.compare(__y) <=> 0);
4234 }
4235 #else  // _LIBCPP_STD_VER >= 20
4236 template <class _BiIter>
4237 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4238   return !(__x == __y);
4239 }
4240
4241 template <class _BiIter>
4242 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4243   return __x.compare(__y) < 0;
4244 }
4245
4246 template <class _BiIter>
4247 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4248   return !(__y < __x);
4249 }
4250
4251 template <class _BiIter>
4252 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4253   return !(__x < __y);
4254 }
4255
4256 template <class _BiIter>
4257 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
4258   return __y < __x;
4259 }
4260
4261 template <class _BiIter, class _ST, class _SA>
4262 inline _LIBCPP_HIDE_FROM_ABI bool
4263 operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4264            const sub_match<_BiIter>& __y) {
4265   return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;
4266 }
4267
4268 template <class _BiIter, class _ST, class _SA>
4269 inline _LIBCPP_HIDE_FROM_ABI bool
4270 operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4271            const sub_match<_BiIter>& __y) {
4272   return !(__x == __y);
4273 }
4274
4275 template <class _BiIter, class _ST, class _SA>
4276 inline _LIBCPP_HIDE_FROM_ABI bool
4277 operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4278           const sub_match<_BiIter>& __y) {
4279   return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;
4280 }
4281
4282 template <class _BiIter, class _ST, class _SA>
4283 inline _LIBCPP_HIDE_FROM_ABI bool
4284 operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4285           const sub_match<_BiIter>& __y) {
4286   return __y < __x;
4287 }
4288
4289 template <class _BiIter, class _ST, class _SA>
4290 inline _LIBCPP_HIDE_FROM_ABI bool
4291 operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4292            const sub_match<_BiIter>& __y) {
4293   return !(__x < __y);
4294 }
4295
4296 template <class _BiIter, class _ST, class _SA>
4297 inline _LIBCPP_HIDE_FROM_ABI bool
4298 operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4299            const sub_match<_BiIter>& __y) {
4300   return !(__y < __x);
4301 }
4302 #endif // _LIBCPP_STD_VER >= 20
4303
4304 template <class _BiIter, class _ST, class _SA>
4305 inline _LIBCPP_HIDE_FROM_ABI bool
4306 operator==(const sub_match<_BiIter>& __x,
4307            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4308   return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;
4309 }
4310
4311 #if _LIBCPP_STD_VER >= 20
4312 template <class _BiIter, class _ST, class _SA>
4313 _LIBCPP_HIDE_FROM_ABI auto
4314 operator<=>(const sub_match<_BiIter>& __x,
4315             const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4316   return static_cast<__sub_match_cat<_BiIter>>(
4317       __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) <=> 0);
4318 }
4319 #else  // _LIBCPP_STD_VER >= 20
4320 template <class _BiIter, class _ST, class _SA>
4321 inline _LIBCPP_HIDE_FROM_ABI bool
4322 operator!=(const sub_match<_BiIter>& __x,
4323            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4324   return !(__x == __y);
4325 }
4326
4327 template <class _BiIter, class _ST, class _SA>
4328 inline _LIBCPP_HIDE_FROM_ABI bool
4329 operator<(const sub_match<_BiIter>& __x,
4330           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4331   return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;
4332 }
4333
4334 template <class _BiIter, class _ST, class _SA>
4335 inline _LIBCPP_HIDE_FROM_ABI bool
4336 operator>(const sub_match<_BiIter>& __x,
4337           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4338   return __y < __x;
4339 }
4340
4341 template <class _BiIter, class _ST, class _SA>
4342 inline _LIBCPP_HIDE_FROM_ABI bool
4343 operator>=(const sub_match<_BiIter>& __x,
4344            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4345   return !(__x < __y);
4346 }
4347
4348 template <class _BiIter, class _ST, class _SA>
4349 inline _LIBCPP_HIDE_FROM_ABI bool
4350 operator<=(const sub_match<_BiIter>& __x,
4351            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
4352   return !(__y < __x);
4353 }
4354
4355 template <class _BiIter>
4356 inline _LIBCPP_HIDE_FROM_ABI bool
4357 operator==(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4358   return __y.compare(__x) == 0;
4359 }
4360
4361 template <class _BiIter>
4362 inline _LIBCPP_HIDE_FROM_ABI bool
4363 operator!=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4364   return !(__x == __y);
4365 }
4366
4367 template <class _BiIter>
4368 inline _LIBCPP_HIDE_FROM_ABI bool
4369 operator<(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4370   return __y.compare(__x) > 0;
4371 }
4372
4373 template <class _BiIter>
4374 inline _LIBCPP_HIDE_FROM_ABI bool
4375 operator>(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4376   return __y < __x;
4377 }
4378
4379 template <class _BiIter>
4380 inline _LIBCPP_HIDE_FROM_ABI bool
4381 operator>=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4382   return !(__x < __y);
4383 }
4384
4385 template <class _BiIter>
4386 inline _LIBCPP_HIDE_FROM_ABI bool
4387 operator<=(typename iterator_traits<_BiIter>::value_type const* __x, const sub_match<_BiIter>& __y) {
4388   return !(__y < __x);
4389 }
4390 #endif // _LIBCPP_STD_VER >= 20
4391
4392 template <class _BiIter>
4393 inline _LIBCPP_HIDE_FROM_ABI bool
4394 operator==(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4395   return __x.compare(__y) == 0;
4396 }
4397
4398 #if _LIBCPP_STD_VER >= 20
4399 template <class _BiIter>
4400 _LIBCPP_HIDE_FROM_ABI auto
4401 operator<=>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4402   return static_cast<__sub_match_cat<_BiIter>>(__x.compare(__y) <=> 0);
4403 }
4404 #else  // _LIBCPP_STD_VER >= 20
4405 template <class _BiIter>
4406 inline _LIBCPP_HIDE_FROM_ABI bool
4407 operator!=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4408   return !(__x == __y);
4409 }
4410
4411 template <class _BiIter>
4412 inline _LIBCPP_HIDE_FROM_ABI bool
4413 operator<(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4414   return __x.compare(__y) < 0;
4415 }
4416
4417 template <class _BiIter>
4418 inline _LIBCPP_HIDE_FROM_ABI bool
4419 operator>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4420   return __y < __x;
4421 }
4422
4423 template <class _BiIter>
4424 inline _LIBCPP_HIDE_FROM_ABI bool
4425 operator>=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4426   return !(__x < __y);
4427 }
4428
4429 template <class _BiIter>
4430 inline _LIBCPP_HIDE_FROM_ABI bool
4431 operator<=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
4432   return !(__y < __x);
4433 }
4434
4435 template <class _BiIter>
4436 inline _LIBCPP_HIDE_FROM_ABI bool
4437 operator==(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4438   typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
4439   return __y.compare(string_type(1, __x)) == 0;
4440 }
4441
4442 template <class _BiIter>
4443 inline _LIBCPP_HIDE_FROM_ABI bool
4444 operator!=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4445   return !(__x == __y);
4446 }
4447
4448 template <class _BiIter>
4449 inline _LIBCPP_HIDE_FROM_ABI bool
4450 operator<(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4451   typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
4452   return __y.compare(string_type(1, __x)) > 0;
4453 }
4454
4455 template <class _BiIter>
4456 inline _LIBCPP_HIDE_FROM_ABI bool
4457 operator>(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4458   return __y < __x;
4459 }
4460
4461 template <class _BiIter>
4462 inline _LIBCPP_HIDE_FROM_ABI bool
4463 operator>=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4464   return !(__x < __y);
4465 }
4466
4467 template <class _BiIter>
4468 inline _LIBCPP_HIDE_FROM_ABI bool
4469 operator<=(typename iterator_traits<_BiIter>::value_type const& __x, const sub_match<_BiIter>& __y) {
4470   return !(__y < __x);
4471 }
4472 #endif // _LIBCPP_STD_VER >= 20
4473
4474 template <class _BiIter>
4475 inline _LIBCPP_HIDE_FROM_ABI bool
4476 operator==(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4477   typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
4478   return __x.compare(string_type(1, __y)) == 0;
4479 }
4480
4481 #if _LIBCPP_STD_VER >= 20
4482 template <class _BiIter>
4483 _LIBCPP_HIDE_FROM_ABI auto
4484 operator<=>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4485   using string_type = basic_string<typename iterator_traits<_BiIter>::value_type>;
4486   return static_cast<__sub_match_cat<_BiIter>>(__x.compare(string_type(1, __y)) <=> 0);
4487 }
4488 #else  // _LIBCPP_STD_VER >= 20
4489 template <class _BiIter>
4490 inline _LIBCPP_HIDE_FROM_ABI bool
4491 operator!=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4492   return !(__x == __y);
4493 }
4494
4495 template <class _BiIter>
4496 inline _LIBCPP_HIDE_FROM_ABI bool
4497 operator<(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4498   typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
4499   return __x.compare(string_type(1, __y)) < 0;
4500 }
4501
4502 template <class _BiIter>
4503 inline _LIBCPP_HIDE_FROM_ABI bool
4504 operator>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4505   return __y < __x;
4506 }
4507
4508 template <class _BiIter>
4509 inline _LIBCPP_HIDE_FROM_ABI bool
4510 operator>=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4511   return !(__x < __y);
4512 }
4513
4514 template <class _BiIter>
4515 inline _LIBCPP_HIDE_FROM_ABI bool
4516 operator<=(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
4517   return !(__y < __x);
4518 }
4519 #endif // _LIBCPP_STD_VER >= 20
4520
4521 template <class _CharT, class _ST, class _BiIter>
4522 inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _ST>&
4523 operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m) {
4524   return __os << __m.str();
4525 }
4526
4527 typedef match_results<const char*> cmatch;
4528 typedef match_results<string::const_iterator> smatch;
4529 #if _LIBCPP_HAS_WIDE_CHARACTERS
4530 typedef match_results<const wchar_t*> wcmatch;
4531 typedef match_results<wstring::const_iterator> wsmatch;
4532 #endif
4533
4534 template <class _BidirectionalIterator, class _Allocator>
4535 class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cmatch) _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcmatch))
4536     _LIBCPP_PREFERRED_NAME(smatch) _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsmatch)) match_results {
4537 public:
4538   typedef _Allocator allocator_type;
4539   typedef sub_match<_BidirectionalIterator> value_type;
4540
4541 private:
4542   typedef vector<value_type, allocator_type> __container_type;
4543
4544   __container_type __matches_;
4545   value_type __unmatched_;
4546   value_type __prefix_;
4547   value_type __suffix_;
4548   bool __ready_;
4549
4550 public:
4551   _BidirectionalIterator __position_start_;
4552   typedef const value_type& const_reference;
4553   typedef value_type& reference;
4554   typedef typename __container_type::const_iterator const_iterator;
4555   typedef const_iterator iterator;
4556   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4557   typedef typename allocator_traits<allocator_type>::size_type size_type;
4558   typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
4559   typedef basic_string<char_type> string_type;
4560
4561   // construct/copy/destroy:
4562 #ifndef _LIBCPP_CXX03_LANG
4563   match_results() : match_results(allocator_type()) {}
4564   explicit match_results(const allocator_type& __a);
4565 #else
4566   explicit match_results(const allocator_type& __a = allocator_type());
4567 #endif
4568
4569   //    match_results(const match_results&) = default;
4570   //    match_results& operator=(const match_results&) = default;
4571   //    match_results(match_results&& __m) = default;
4572   //    match_results& operator=(match_results&& __m) = default;
4573   //    ~match_results() = default;
4574
4575   _LIBCPP_HIDE_FROM_ABI bool ready() const { return __ready_; }
4576
4577   // size:
4578   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __matches_.size(); }
4579   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __matches_.max_size(); }
4580   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return size() == 0; }
4581
4582   // element access:
4583   _LIBCPP_HIDE_FROM_ABI difference_type length(size_type __sub = 0) const {
4584     // If the match results are not ready, this will return `0`.
4585     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::length() called when not ready");
4586     return (*this)[__sub].length();
4587   }
4588   _LIBCPP_HIDE_FROM_ABI difference_type position(size_type __sub = 0) const {
4589     // If the match results are not ready, this will return the result of subtracting two default-constructed iterators
4590     // (which is typically a well-defined operation).
4591     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::position() called when not ready");
4592     return std::distance(__position_start_, (*this)[__sub].first);
4593   }
4594   _LIBCPP_HIDE_FROM_ABI string_type str(size_type __sub = 0) const {
4595     // If the match results are not ready, this will return an empty string.
4596     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::str() called when not ready");
4597     return (*this)[__sub].str();
4598   }
4599   _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const {
4600     // If the match results are not ready, this call will be equivalent to calling this function with `__n >= size()`,
4601     // returning an empty subrange.
4602     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::operator[]() called when not ready");
4603     return __n < __matches_.size() ? __matches_[__n] : __unmatched_;
4604   }
4605
4606   _LIBCPP_HIDE_FROM_ABI const_reference prefix() const {
4607     // If the match results are not ready, this will return a default-constructed empty `__suffix_`.
4608     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::prefix() called when not ready");
4609     return __prefix_;
4610   }
4611   _LIBCPP_HIDE_FROM_ABI const_reference suffix() const {
4612     // If the match results are not ready, this will return a default-constructed empty `__suffix_`.
4613     _LIBCPP_ASSERT_PEDANTIC(ready(), "match_results::suffix() called when not ready");
4614     return __suffix_;
4615   }
4616
4617   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return empty() ? __matches_.end() : __matches_.begin(); }
4618   _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __matches_.end(); }
4619   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const { return empty() ? __matches_.end() : __matches_.begin(); }
4620   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const { return __matches_.end(); }
4621
4622   // format:
4623   template <class _OutputIter>
4624   _OutputIter format(_OutputIter __output_iter,
4625                      const char_type* __fmt_first,
4626                      const char_type* __fmt_last,
4627                      regex_constants::match_flag_type __flags = regex_constants::format_default) const;
4628   template <class _OutputIter, class _ST, class _SA>
4629   _LIBCPP_HIDE_FROM_ABI _OutputIter
4630   format(_OutputIter __output_iter,
4631          const basic_string<char_type, _ST, _SA>& __fmt,
4632          regex_constants::match_flag_type __flags = regex_constants::format_default) const {
4633     return format(__output_iter, __fmt.data(), __fmt.data() + __fmt.size(), __flags);
4634   }
4635   template <class _ST, class _SA>
4636   _LIBCPP_HIDE_FROM_ABI basic_string<char_type, _ST, _SA>
4637   format(const basic_string<char_type, _ST, _SA>& __fmt,
4638          regex_constants::match_flag_type __flags = regex_constants::format_default) const {
4639     basic_string<char_type, _ST, _SA> __r;
4640     format(std::back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(), __flags);
4641     return __r;
4642   }
4643   _LIBCPP_HIDE_FROM_ABI string_type
4644   format(const char_type* __fmt, regex_constants::match_flag_type __flags = regex_constants::format_default) const {
4645     string_type __r;
4646     format(std::back_inserter(__r), __fmt, __fmt + char_traits<char_type>::length(__fmt), __flags);
4647     return __r;
4648   }
4649
4650   // allocator:
4651   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return __matches_.get_allocator(); }
4652
4653   // swap:
4654   void swap(match_results& __m);
4655
4656   template <class _Bp, class _Ap>
4657   _LIBCPP_HIDE_FROM_ABI void
4658   __assign(_BidirectionalIterator __f,
4659            _BidirectionalIterator __l,
4660            const match_results<_Bp, _Ap>& __m,
4661            bool __no_update_pos) {
4662     _Bp __mf = __m.prefix().first;
4663     __matches_.resize(__m.size());
4664     for (size_type __i = 0; __i < __matches_.size(); ++__i) {
4665       __matches_[__i].first   = std::next(__f, std::distance(__mf, __m[__i].first));
4666       __matches_[__i].second  = std::next(__f, std::distance(__mf, __m[__i].second));
4667       __matches_[__i].matched = __m[__i].matched;
4668     }
4669     __unmatched_.first   = __l;
4670     __unmatched_.second  = __l;
4671     __unmatched_.matched = false;
4672     __prefix_.first      = std::next(__f, std::distance(__mf, __m.prefix().first));
4673     __prefix_.second     = std::next(__f, std::distance(__mf, __m.prefix().second));
4674     __prefix_.matched    = __m.prefix().matched;
4675     __suffix_.first      = std::next(__f, std::distance(__mf, __m.suffix().first));
4676     __suffix_.second     = std::next(__f, std::distance(__mf, __m.suffix().second));
4677     __suffix_.matched    = __m.suffix().matched;
4678     if (!__no_update_pos)
4679       __position_start_ = __prefix_.first;
4680     __ready_ = __m.ready();
4681   }
4682
4683 private:
4684   void __init(unsigned __s, _BidirectionalIterator __f, _BidirectionalIterator __l, bool __no_update_pos = false);
4685
4686   template <class, class>
4687   friend class basic_regex;
4688
4689   template <class _Bp, class _Ap, class _Cp, class _Tp>
4690   friend bool
4691   regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
4692
4693   template <class _Bp, class _Ap>
4694   friend bool operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
4695
4696   template <class, class>
4697   friend class __lookahead;
4698
4699   template <class, class, class>
4700   friend class regex_iterator;
4701 };
4702
4703 template <class _BidirectionalIterator, class _Allocator>
4704 match_results<_BidirectionalIterator, _Allocator>::match_results(const allocator_type& __a)
4705     : __matches_(__a), __unmatched_(), __prefix_(), __suffix_(), __ready_(false), __position_start_() {}
4706
4707 template <class _BidirectionalIterator, class _Allocator>
4708 void match_results<_BidirectionalIterator, _Allocator>::__init(
4709     unsigned __s, _BidirectionalIterator __f, _BidirectionalIterator __l, bool __no_update_pos) {
4710   __unmatched_.first   = __l;
4711   __unmatched_.second  = __l;
4712   __unmatched_.matched = false;
4713   __matches_.assign(__s, __unmatched_);
4714   __prefix_.first   = __f;
4715   __prefix_.second  = __f;
4716   __prefix_.matched = false;
4717   __suffix_         = __unmatched_;
4718   if (!__no_update_pos)
4719     __position_start_ = __prefix_.first;
4720   __ready_ = true;
4721 }
4722
4723 template <class _BidirectionalIterator, class _Allocator>
4724 template <class _OutputIter>
4725 _OutputIter match_results<_BidirectionalIterator, _Allocator>::format(
4726     _OutputIter __output_iter,
4727     const char_type* __fmt_first,
4728     const char_type* __fmt_last,
4729     regex_constants::match_flag_type __flags) const {
4730   // Note: this duplicates a check in `vector::operator[]` but provides a better error message.
4731   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(ready(), "match_results::format() called when not ready");
4732   if (__flags & regex_constants::format_sed) {
4733     for (; __fmt_first != __fmt_last; ++__fmt_first) {
4734       if (*__fmt_first == '&')
4735         __output_iter = std::copy(__matches_[0].first, __matches_[0].second, __output_iter);
4736       else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last) {
4737         ++__fmt_first;
4738         if ('0' <= *__fmt_first && *__fmt_first <= '9') {
4739           size_t __i    = *__fmt_first - '0';
4740           __output_iter = std::copy((*this)[__i].first, (*this)[__i].second, __output_iter);
4741         } else {
4742           *__output_iter = *__fmt_first;
4743           ++__output_iter;
4744         }
4745       } else {
4746         *__output_iter = *__fmt_first;
4747         ++__output_iter;
4748       }
4749     }
4750   } else {
4751     for (; __fmt_first != __fmt_last; ++__fmt_first) {
4752       if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last) {
4753         switch (__fmt_first[1]) {
4754         case '$':
4755           *__output_iter = *++__fmt_first;
4756           ++__output_iter;
4757           break;
4758         case '&':
4759           ++__fmt_first;
4760           __output_iter = std::copy(__matches_[0].first, __matches_[0].second, __output_iter);
4761           break;
4762         case '`':
4763           ++__fmt_first;
4764           __output_iter = std::copy(__prefix_.first, __prefix_.second, __output_iter);
4765           break;
4766         case '\'':
4767           ++__fmt_first;
4768           __output_iter = std::copy(__suffix_.first, __suffix_.second, __output_iter);
4769           break;
4770         default:
4771           if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9') {
4772             ++__fmt_first;
4773             size_t __idx = *__fmt_first - '0';
4774             if (__fmt_first + 1 != __fmt_last && '0' <= __fmt_first[1] && __fmt_first[1] <= '9') {
4775               ++__fmt_first;
4776               if (__idx >= numeric_limits<size_t>::max() / 10)
4777                 __throw_regex_error<regex_constants::error_escape>();
4778               __idx = 10 * __idx + *__fmt_first - '0';
4779             }
4780             __output_iter = std::copy((*this)[__idx].first, (*this)[__idx].second, __output_iter);
4781           } else {
4782             *__output_iter = *__fmt_first;
4783             ++__output_iter;
4784           }
4785           break;
4786         }
4787       } else {
4788         *__output_iter = *__fmt_first;
4789         ++__output_iter;
4790       }
4791     }
4792   }
4793   return __output_iter;
4794 }
4795
4796 template <class _BidirectionalIterator, class _Allocator>
4797 void match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m) {
4798   using std::swap;
4799   swap(__matches_, __m.__matches_);
4800   swap(__unmatched_, __m.__unmatched_);
4801   swap(__prefix_, __m.__prefix_);
4802   swap(__suffix_, __m.__suffix_);
4803   swap(__position_start_, __m.__position_start_);
4804   swap(__ready_, __m.__ready_);
4805 }
4806
4807 template <class _BidirectionalIterator, class _Allocator>
4808 _LIBCPP_HIDE_FROM_ABI bool operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
4809                                       const match_results<_BidirectionalIterator, _Allocator>& __y) {
4810   if (__x.__ready_ != __y.__ready_)
4811     return false;
4812   if (!__x.__ready_)
4813     return true;
4814   return __x.__matches_ == __y.__matches_ && __x.__prefix_ == __y.__prefix_ && __x.__suffix_ == __y.__suffix_;
4815 }
4816
4817 #if _LIBCPP_STD_VER < 20
4818 template <class _BidirectionalIterator, class _Allocator>
4819 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
4820                                              const match_results<_BidirectionalIterator, _Allocator>& __y) {
4821   return !(__x == __y);
4822 }
4823 #endif
4824
4825 template <class _BidirectionalIterator, class _Allocator>
4826 inline _LIBCPP_HIDE_FROM_ABI void
4827 swap(match_results<_BidirectionalIterator, _Allocator>& __x, match_results<_BidirectionalIterator, _Allocator>& __y) {
4828   __x.swap(__y);
4829 }
4830
4831 // regex_search
4832
4833 template <class _CharT, class _Traits>
4834 template <class _Allocator>
4835 bool basic_regex<_CharT, _Traits>::__match_at_start_ecma(
4836     const _CharT* __first,
4837     const _CharT* __last,
4838     match_results<const _CharT*, _Allocator>& __m,
4839     regex_constants::match_flag_type __flags,
4840     bool __at_first) const {
4841   vector<__state> __states;
4842   __node* __st = __start_.get();
4843   if (__st) {
4844     sub_match<const _CharT*> __unmatched;
4845     __unmatched.first   = __last;
4846     __unmatched.second  = __last;
4847     __unmatched.matched = false;
4848
4849     __states.push_back(__state());
4850     __states.back().__do_      = 0;
4851     __states.back().__first_   = __first;
4852     __states.back().__current_ = __first;
4853     __states.back().__last_    = __last;
4854     __states.back().__sub_matches_.resize(mark_count(), __unmatched);
4855     __states.back().__loop_data_.resize(__loop_count());
4856     __states.back().__node_     = __st;
4857     __states.back().__flags_    = __flags;
4858     __states.back().__at_first_ = __at_first;
4859     int __counter               = 0;
4860     int __length                = __last - __first;
4861     do {
4862       ++__counter;
4863       if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
4864         __throw_regex_error<regex_constants::error_complexity>();
4865       __state& __s = __states.back();
4866       if (__s.__node_)
4867         __s.__node_->__exec(__s);
4868       switch (__s.__do_) {
4869       case __state::__end_state:
4870         if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {
4871           __states.pop_back();
4872           break;
4873         }
4874         if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {
4875           __states.pop_back();
4876           break;
4877         }
4878         __m.__matches_[0].first   = __first;
4879         __m.__matches_[0].second  = std::next(__first, __s.__current_ - __first);
4880         __m.__matches_[0].matched = true;
4881         for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
4882           __m.__matches_[__i + 1] = __s.__sub_matches_[__i];
4883         return true;
4884       case __state::__accept_and_consume:
4885       case __state::__repeat:
4886       case __state::__accept_but_not_consume:
4887         break;
4888       case __state::__split: {
4889         __state __snext = __s;
4890         __s.__node_->__exec_split(true, __s);
4891         __snext.__node_->__exec_split(false, __snext);
4892         __states.push_back(std::move(__snext));
4893       } break;
4894       case __state::__reject:
4895         __states.pop_back();
4896         break;
4897       default:
4898         __throw_regex_error<regex_constants::__re_err_unknown>();
4899         break;
4900       }
4901     } while (!__states.empty());
4902   }
4903   return false;
4904 }
4905
4906 template <class _CharT, class _Traits>
4907 template <class _Allocator>
4908 bool basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
4909     const _CharT* __first,
4910     const _CharT* __last,
4911     match_results<const _CharT*, _Allocator>& __m,
4912     regex_constants::match_flag_type __flags,
4913     bool __at_first) const {
4914   deque<__state> __states;
4915   ptrdiff_t __highest_j = 0;
4916   ptrdiff_t __np        = std::distance(__first, __last);
4917   __node* __st          = __start_.get();
4918   if (__st) {
4919     __states.push_back(__state());
4920     __states.back().__do_      = 0;
4921     __states.back().__first_   = __first;
4922     __states.back().__current_ = __first;
4923     __states.back().__last_    = __last;
4924     __states.back().__loop_data_.resize(__loop_count());
4925     __states.back().__node_     = __st;
4926     __states.back().__flags_    = __flags;
4927     __states.back().__at_first_ = __at_first;
4928     bool __matched              = false;
4929     int __counter               = 0;
4930     int __length                = __last - __first;
4931     do {
4932       ++__counter;
4933       if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
4934         __throw_regex_error<regex_constants::error_complexity>();
4935       __state& __s = __states.back();
4936       if (__s.__node_)
4937         __s.__node_->__exec(__s);
4938       switch (__s.__do_) {
4939       case __state::__end_state:
4940         if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {
4941           __states.pop_back();
4942           break;
4943         }
4944         if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {
4945           __states.pop_back();
4946           break;
4947         }
4948         if (!__matched || __highest_j < __s.__current_ - __s.__first_)
4949           __highest_j = __s.__current_ - __s.__first_;
4950         __matched = true;
4951         if (__highest_j == __np)
4952           __states.clear();
4953         else
4954           __states.pop_back();
4955         break;
4956       case __state::__consume_input:
4957         break;
4958       case __state::__accept_and_consume:
4959         __states.push_front(std::move(__s));
4960         __states.pop_back();
4961         break;
4962       case __state::__repeat:
4963       case __state::__accept_but_not_consume:
4964         break;
4965       case __state::__split: {
4966         __state __snext = __s;
4967         __s.__node_->__exec_split(true, __s);
4968         __snext.__node_->__exec_split(false, __snext);
4969         __states.push_back(std::move(__snext));
4970       } break;
4971       case __state::__reject:
4972         __states.pop_back();
4973         break;
4974       default:
4975         __throw_regex_error<regex_constants::__re_err_unknown>();
4976         break;
4977       }
4978     } while (!__states.empty());
4979     if (__matched) {
4980       __m.__matches_[0].first   = __first;
4981       __m.__matches_[0].second  = std::next(__first, __highest_j);
4982       __m.__matches_[0].matched = true;
4983       return true;
4984     }
4985   }
4986   return false;
4987 }
4988
4989 template <class _CharT, class _Traits>
4990 template <class _Allocator>
4991 bool basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
4992     const _CharT* __first,
4993     const _CharT* __last,
4994     match_results<const _CharT*, _Allocator>& __m,
4995     regex_constants::match_flag_type __flags,
4996     bool __at_first) const {
4997   vector<__state> __states;
4998   __state __best_state;
4999   ptrdiff_t __highest_j = 0;
5000   ptrdiff_t __np        = std::distance(__first, __last);
5001   __node* __st          = __start_.get();
5002   if (__st) {
5003     sub_match<const _CharT*> __unmatched;
5004     __unmatched.first   = __last;
5005     __unmatched.second  = __last;
5006     __unmatched.matched = false;
5007
5008     __states.push_back(__state());
5009     __states.back().__do_      = 0;
5010     __states.back().__first_   = __first;
5011     __states.back().__current_ = __first;
5012     __states.back().__last_    = __last;
5013     __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5014     __states.back().__loop_data_.resize(__loop_count());
5015     __states.back().__node_     = __st;
5016     __states.back().__flags_    = __flags;
5017     __states.back().__at_first_ = __at_first;
5018     bool __matched              = false;
5019     int __counter               = 0;
5020     int __length                = __last - __first;
5021     do {
5022       ++__counter;
5023       if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 && __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5024         __throw_regex_error<regex_constants::error_complexity>();
5025       __state& __s = __states.back();
5026       if (__s.__node_)
5027         __s.__node_->__exec(__s);
5028       switch (__s.__do_) {
5029       case __state::__end_state:
5030         if ((__flags & regex_constants::match_not_null) && __s.__current_ == __first) {
5031           __states.pop_back();
5032           break;
5033         }
5034         if ((__flags & regex_constants::__full_match) && __s.__current_ != __last) {
5035           __states.pop_back();
5036           break;
5037         }
5038         if (!__matched || __highest_j < __s.__current_ - __s.__first_) {
5039           __highest_j  = __s.__current_ - __s.__first_;
5040           __best_state = __s;
5041         }
5042         __matched = true;
5043         if (__highest_j == __np)
5044           __states.clear();
5045         else
5046           __states.pop_back();
5047         break;
5048       case __state::__accept_and_consume:
5049       case __state::__repeat:
5050       case __state::__accept_but_not_consume:
5051         break;
5052       case __state::__split: {
5053         __state __snext = __s;
5054         __s.__node_->__exec_split(true, __s);
5055         __snext.__node_->__exec_split(false, __snext);
5056         __states.push_back(std::move(__snext));
5057       } break;
5058       case __state::__reject:
5059         __states.pop_back();
5060         break;
5061       default:
5062         __throw_regex_error<regex_constants::__re_err_unknown>();
5063         break;
5064       }
5065     } while (!__states.empty());
5066     if (__matched) {
5067       __m.__matches_[0].first   = __first;
5068       __m.__matches_[0].second  = std::next(__first, __highest_j);
5069       __m.__matches_[0].matched = true;
5070       for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
5071         __m.__matches_[__i + 1] = __best_state.__sub_matches_[__i];
5072       return true;
5073     }
5074   }
5075   return false;
5076 }
5077
5078 template <class _CharT, class _Traits>
5079 template <class _Allocator>
5080 bool basic_regex<_CharT, _Traits>::__match_at_start(
5081     const _CharT* __first,
5082     const _CharT* __last,
5083     match_results<const _CharT*, _Allocator>& __m,
5084     regex_constants::match_flag_type __flags,
5085     bool __at_first) const {
5086   if (__get_grammar(__flags_) == ECMAScript)
5087     return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
5088   if (mark_count() == 0)
5089     return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
5090   return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
5091 }
5092
5093 template <class _CharT, class _Traits>
5094 template <class _Allocator>
5095 bool basic_regex<_CharT, _Traits>::__search(
5096     const _CharT* __first,
5097     const _CharT* __last,
5098     match_results<const _CharT*, _Allocator>& __m,
5099     regex_constants::match_flag_type __flags) const {
5100   if (__flags & regex_constants::match_prev_avail)
5101     __flags &= ~(regex_constants::match_not_bol | regex_constants::match_not_bow);
5102
5103   __m.__init(1 + mark_count(), __first, __last, __flags & regex_constants::__no_update_pos);
5104   if (__match_at_start(__first, __last, __m, __flags, !(__flags & regex_constants::__no_update_pos))) {
5105     __m.__prefix_.second  = __m[0].first;
5106     __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5107     __m.__suffix_.first   = __m[0].second;
5108     __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5109     return true;
5110   }
5111   if (__first != __last && !(__flags & regex_constants::match_continuous)) {
5112     __flags |= regex_constants::match_prev_avail;
5113     for (++__first; __first != __last; ++__first) {
5114       __m.__matches_.assign(__m.size(), __m.__unmatched_);
5115       if (__match_at_start(__first, __last, __m, __flags, false)) {
5116         __m.__prefix_.second  = __m[0].first;
5117         __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5118         __m.__suffix_.first   = __m[0].second;
5119         __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5120         return true;
5121       }
5122       __m.__matches_.assign(__m.size(), __m.__unmatched_);
5123     }
5124     __m.__matches_.assign(__m.size(), __m.__unmatched_);
5125     if (__match_at_start(__first, __last, __m, __flags, false)) {
5126       __m.__prefix_.second  = __m[0].first;
5127       __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5128       __m.__suffix_.first   = __m[0].second;
5129       __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5130       return true;
5131     }
5132   }
5133   __m.__matches_.clear();
5134   return false;
5135 }
5136
5137 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5138 inline _LIBCPP_HIDE_FROM_ABI bool
5139 regex_search(_BidirectionalIterator __first,
5140              _BidirectionalIterator __last,
5141              match_results<_BidirectionalIterator, _Allocator>& __m,
5142              const basic_regex<_CharT, _Traits>& __e,
5143              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5144   int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
5145   basic_string<_CharT> __s(std::prev(__first, __offset), __last);
5146   match_results<const _CharT*> __mc;
5147   bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
5148   __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5149   return __r;
5150 }
5151
5152 template <class _Iter, class _Allocator, class _CharT, class _Traits>
5153 inline _LIBCPP_HIDE_FROM_ABI bool
5154 regex_search(__wrap_iter<_Iter> __first,
5155              __wrap_iter<_Iter> __last,
5156              match_results<__wrap_iter<_Iter>, _Allocator>& __m,
5157              const basic_regex<_CharT, _Traits>& __e,
5158              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5159   match_results<const _CharT*> __mc;
5160   bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
5161   __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5162   return __r;
5163 }
5164
5165 template <class _Allocator, class _CharT, class _Traits>
5166 inline _LIBCPP_HIDE_FROM_ABI bool
5167 regex_search(const _CharT* __first,
5168              const _CharT* __last,
5169              match_results<const _CharT*, _Allocator>& __m,
5170              const basic_regex<_CharT, _Traits>& __e,
5171              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5172   return __e.__search(__first, __last, __m, __flags);
5173 }
5174
5175 template <class _BidirectionalIterator, class _CharT, class _Traits>
5176 inline _LIBCPP_HIDE_FROM_ABI bool
5177 regex_search(_BidirectionalIterator __first,
5178              _BidirectionalIterator __last,
5179              const basic_regex<_CharT, _Traits>& __e,
5180              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5181   basic_string<_CharT> __s(__first, __last);
5182   match_results<const _CharT*> __mc;
5183   return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5184 }
5185
5186 template <class _CharT, class _Traits>
5187 inline _LIBCPP_HIDE_FROM_ABI bool
5188 regex_search(const _CharT* __first,
5189              const _CharT* __last,
5190              const basic_regex<_CharT, _Traits>& __e,
5191              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5192   match_results<const _CharT*> __mc;
5193   return __e.__search(__first, __last, __mc, __flags);
5194 }
5195
5196 template <class _CharT, class _Allocator, class _Traits>
5197 inline _LIBCPP_HIDE_FROM_ABI bool
5198 regex_search(const _CharT* __str,
5199              match_results<const _CharT*, _Allocator>& __m,
5200              const basic_regex<_CharT, _Traits>& __e,
5201              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5202   return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
5203 }
5204
5205 template <class _CharT, class _Traits>
5206 inline _LIBCPP_HIDE_FROM_ABI bool
5207 regex_search(const _CharT* __str,
5208              const basic_regex<_CharT, _Traits>& __e,
5209              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5210   match_results<const _CharT*> __m;
5211   return std::regex_search(__str, __m, __e, __flags);
5212 }
5213
5214 template <class _ST, class _SA, class _CharT, class _Traits>
5215 inline _LIBCPP_HIDE_FROM_ABI bool
5216 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5217              const basic_regex<_CharT, _Traits>& __e,
5218              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5219   match_results<const _CharT*> __mc;
5220   return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5221 }
5222
5223 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5224 inline _LIBCPP_HIDE_FROM_ABI bool
5225 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5226              match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5227              const basic_regex<_CharT, _Traits>& __e,
5228              regex_constants::match_flag_type __flags = regex_constants::match_default) {
5229   match_results<const _CharT*> __mc;
5230   bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5231   __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
5232   return __r;
5233 }
5234
5235 #if _LIBCPP_STD_VER >= 14
5236 template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
5237 bool regex_search(const basic_string<_Cp, _ST, _SA>&& __s,
5238                   match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
5239                   const basic_regex<_Cp, _Tp>& __e,
5240                   regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
5241 #endif
5242
5243 // regex_match
5244
5245 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5246 _LIBCPP_HIDE_FROM_ABI bool
5247 regex_match(_BidirectionalIterator __first,
5248             _BidirectionalIterator __last,
5249             match_results<_BidirectionalIterator, _Allocator>& __m,
5250             const basic_regex<_CharT, _Traits>& __e,
5251             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5252   bool __r = std::regex_search(
5253       __first, __last, __m, __e, __flags | regex_constants::match_continuous | regex_constants::__full_match);
5254   if (__r) {
5255     __r = !__m.suffix().matched;
5256     if (!__r)
5257       __m.__matches_.clear();
5258   }
5259   return __r;
5260 }
5261
5262 template <class _BidirectionalIterator, class _CharT, class _Traits>
5263 inline _LIBCPP_HIDE_FROM_ABI bool
5264 regex_match(_BidirectionalIterator __first,
5265             _BidirectionalIterator __last,
5266             const basic_regex<_CharT, _Traits>& __e,
5267             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5268   match_results<_BidirectionalIterator> __m;
5269   return std::regex_match(__first, __last, __m, __e, __flags);
5270 }
5271
5272 template <class _CharT, class _Allocator, class _Traits>
5273 inline _LIBCPP_HIDE_FROM_ABI bool
5274 regex_match(const _CharT* __str,
5275             match_results<const _CharT*, _Allocator>& __m,
5276             const basic_regex<_CharT, _Traits>& __e,
5277             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5278   return std::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
5279 }
5280
5281 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5282 inline _LIBCPP_HIDE_FROM_ABI bool
5283 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
5284             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5285             const basic_regex<_CharT, _Traits>& __e,
5286             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5287   return std::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
5288 }
5289
5290 #if _LIBCPP_STD_VER >= 14
5291 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5292 inline _LIBCPP_HIDE_FROM_ABI bool
5293 regex_match(const basic_string<_CharT, _ST, _SA>&& __s,
5294             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5295             const basic_regex<_CharT, _Traits>& __e,
5296             regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
5297 #endif
5298
5299 template <class _CharT, class _Traits>
5300 inline _LIBCPP_HIDE_FROM_ABI bool
5301 regex_match(const _CharT* __str,
5302             const basic_regex<_CharT, _Traits>& __e,
5303             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5304   return std::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
5305 }
5306
5307 template <class _ST, class _SA, class _CharT, class _Traits>
5308 inline _LIBCPP_HIDE_FROM_ABI bool
5309 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
5310             const basic_regex<_CharT, _Traits>& __e,
5311             regex_constants::match_flag_type __flags = regex_constants::match_default) {
5312   return std::regex_match(__s.begin(), __s.end(), __e, __flags);
5313 }
5314
5315 // regex_iterator
5316
5317 template <class _BidirectionalIterator,
5318           class _CharT  = typename iterator_traits<_BidirectionalIterator>::value_type,
5319           class _Traits = regex_traits<_CharT> >
5320 class _LIBCPP_TEMPLATE_VIS regex_iterator;
5321
5322 typedef regex_iterator<const char*> cregex_iterator;
5323 typedef regex_iterator<string::const_iterator> sregex_iterator;
5324 #if _LIBCPP_HAS_WIDE_CHARACTERS
5325 typedef regex_iterator<const wchar_t*> wcregex_iterator;
5326 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
5327 #endif
5328
5329 template <class _BidirectionalIterator, class _CharT, class _Traits>
5330 class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cregex_iterator)
5331     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_iterator)) _LIBCPP_PREFERRED_NAME(sregex_iterator)
5332         _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_iterator)) regex_iterator {
5333 public:
5334   typedef basic_regex<_CharT, _Traits> regex_type;
5335   typedef match_results<_BidirectionalIterator> value_type;
5336   typedef ptrdiff_t difference_type;
5337   typedef const value_type* pointer;
5338   typedef const value_type& reference;
5339   typedef forward_iterator_tag iterator_category;
5340 #if _LIBCPP_STD_VER >= 20
5341   typedef input_iterator_tag iterator_concept;
5342 #endif
5343
5344 private:
5345   _BidirectionalIterator __begin_;
5346   _BidirectionalIterator __end_;
5347   const regex_type* __pregex_;
5348   regex_constants::match_flag_type __flags_;
5349   value_type __match_;
5350
5351 public:
5352   regex_iterator();
5353   regex_iterator(_BidirectionalIterator __a,
5354                  _BidirectionalIterator __b,
5355                  const regex_type& __re,
5356                  regex_constants::match_flag_type __m = regex_constants::match_default);
5357 #if _LIBCPP_STD_VER >= 14
5358   regex_iterator(_BidirectionalIterator __a,
5359                  _BidirectionalIterator __b,
5360                  const regex_type&& __re,
5361                  regex_constants::match_flag_type __m = regex_constants::match_default) = delete;
5362 #endif
5363
5364   _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_iterator& __x) const;
5365 #if _LIBCPP_STD_VER >= 20
5366   _LIBCPP_HIDE_FROM_ABI bool operator==(default_sentinel_t) const { return *this == regex_iterator(); }
5367 #endif
5368 #if _LIBCPP_STD_VER < 20
5369   _LIBCPP_HIDE_FROM_ABI bool operator!=(const regex_iterator& __x) const { return !(*this == __x); }
5370 #endif
5371
5372   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __match_; }
5373   _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return std::addressof(__match_); }
5374
5375   regex_iterator& operator++();
5376   _LIBCPP_HIDE_FROM_ABI regex_iterator operator++(int) {
5377     regex_iterator __t(*this);
5378     ++(*this);
5379     return __t;
5380   }
5381 };
5382
5383 template <class _BidirectionalIterator, class _CharT, class _Traits>
5384 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
5385     : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_() {}
5386
5387 template <class _BidirectionalIterator, class _CharT, class _Traits>
5388 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator(
5389     _BidirectionalIterator __a,
5390     _BidirectionalIterator __b,
5391     const regex_type& __re,
5392     regex_constants::match_flag_type __m)
5393     : __begin_(__a), __end_(__b), __pregex_(std::addressof(__re)), __flags_(__m) {
5394   std::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
5395 }
5396
5397 template <class _BidirectionalIterator, class _CharT, class _Traits>
5398 bool regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator==(const regex_iterator& __x) const {
5399   if (__match_.empty() && __x.__match_.empty())
5400     return true;
5401   if (__match_.empty() || __x.__match_.empty())
5402     return false;
5403   return __begin_ == __x.__begin_ && __end_ == __x.__end_ && __pregex_ == __x.__pregex_ && __flags_ == __x.__flags_ &&
5404          __match_[0] == __x.__match_[0];
5405 }
5406
5407 template <class _BidirectionalIterator, class _CharT, class _Traits>
5408 regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
5409 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++() {
5410   __flags_ |= regex_constants::__no_update_pos;
5411   _BidirectionalIterator __start        = __match_[0].second;
5412   _BidirectionalIterator __prefix_start = __start;
5413
5414   if (__match_[0].first == __match_[0].second) {
5415     if (__start == __end_) {
5416       __match_ = value_type();
5417       return *this;
5418     } else if (std::regex_search(__start,
5419                                  __end_,
5420                                  __match_,
5421                                  *__pregex_,
5422                                  __flags_ | regex_constants::match_not_null | regex_constants::match_continuous))
5423       return *this;
5424     else
5425       ++__start;
5426   }
5427
5428   __flags_ |= regex_constants::match_prev_avail;
5429   if (!std::regex_search(__start, __end_, __match_, *__pregex_, __flags_)) {
5430     __match_ = value_type();
5431
5432   } else {
5433     // The Standard mandates that if `regex_search` returns true ([re.regiter.incr]), "`match.prefix().first` shall be
5434     // equal to the previous value of `match[0].second`... It is unspecified how the implementation makes these
5435     // adjustments." The adjustment is necessary if we incremented `__start` above (the branch that deals with
5436     // zero-length matches).
5437     auto& __prefix   = __match_.__prefix_;
5438     __prefix.first   = __prefix_start;
5439     __prefix.matched = __prefix.first != __prefix.second;
5440   }
5441
5442   return *this;
5443 }
5444
5445 // regex_token_iterator
5446
5447 template <class _BidirectionalIterator,
5448           class _CharT  = typename iterator_traits<_BidirectionalIterator>::value_type,
5449           class _Traits = regex_traits<_CharT> >
5450 class _LIBCPP_TEMPLATE_VIS regex_token_iterator;
5451
5452 typedef regex_token_iterator<const char*> cregex_token_iterator;
5453 typedef regex_token_iterator<string::const_iterator> sregex_token_iterator;
5454 #if _LIBCPP_HAS_WIDE_CHARACTERS
5455 typedef regex_token_iterator<const wchar_t*> wcregex_token_iterator;
5456 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
5457 #endif
5458
5459 template <class _BidirectionalIterator, class _CharT, class _Traits>
5460 class _LIBCPP_TEMPLATE_VIS _LIBCPP_PREFERRED_NAME(cregex_token_iterator)
5461     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_token_iterator))
5462         _LIBCPP_PREFERRED_NAME(sregex_token_iterator)
5463             _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_token_iterator)) regex_token_iterator {
5464 public:
5465   typedef basic_regex<_CharT, _Traits> regex_type;
5466   typedef sub_match<_BidirectionalIterator> value_type;
5467   typedef ptrdiff_t difference_type;
5468   typedef const value_type* pointer;
5469   typedef const value_type& reference;
5470   typedef forward_iterator_tag iterator_category;
5471 #if _LIBCPP_STD_VER >= 20
5472   typedef input_iterator_tag iterator_concept;
5473 #endif
5474
5475 private:
5476   typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
5477
5478   _Position __position_;
5479   const value_type* __result_;
5480   value_type __suffix_;
5481   ptrdiff_t __n_;
5482   vector<int> __subs_;
5483
5484 public:
5485   regex_token_iterator();
5486   regex_token_iterator(_BidirectionalIterator __a,
5487                        _BidirectionalIterator __b,
5488                        const regex_type& __re,
5489                        int __submatch                       = 0,
5490                        regex_constants::match_flag_type __m = regex_constants::match_default);
5491 #if _LIBCPP_STD_VER >= 14
5492   regex_token_iterator(_BidirectionalIterator __a,
5493                        _BidirectionalIterator __b,
5494                        const regex_type&& __re,
5495                        int __submatch                       = 0,
5496                        regex_constants::match_flag_type __m = regex_constants::match_default) = delete;
5497 #endif
5498
5499   regex_token_iterator(_BidirectionalIterator __a,
5500                        _BidirectionalIterator __b,
5501                        const regex_type& __re,
5502                        const vector<int>& __submatches,
5503                        regex_constants::match_flag_type __m = regex_constants::match_default);
5504 #if _LIBCPP_STD_VER >= 14
5505   regex_token_iterator(_BidirectionalIterator __a,
5506                        _BidirectionalIterator __b,
5507                        const regex_type&& __re,
5508                        const vector<int>& __submatches,
5509                        regex_constants::match_flag_type __m = regex_constants::match_default) = delete;
5510 #endif
5511
5512 #ifndef _LIBCPP_CXX03_LANG
5513   regex_token_iterator(_BidirectionalIterator __a,
5514                        _BidirectionalIterator __b,
5515                        const regex_type& __re,
5516                        initializer_list<int> __submatches,
5517                        regex_constants::match_flag_type __m = regex_constants::match_default);
5518
5519 #  if _LIBCPP_STD_VER >= 14
5520   regex_token_iterator(_BidirectionalIterator __a,
5521                        _BidirectionalIterator __b,
5522                        const regex_type&& __re,
5523                        initializer_list<int> __submatches,
5524                        regex_constants::match_flag_type __m = regex_constants::match_default) = delete;
5525 #  endif
5526 #endif // _LIBCPP_CXX03_LANG
5527   template <size_t _Np>
5528   regex_token_iterator(_BidirectionalIterator __a,
5529                        _BidirectionalIterator __b,
5530                        const regex_type& __re,
5531                        const int (&__submatches)[_Np],
5532                        regex_constants::match_flag_type __m = regex_constants::match_default);
5533 #if _LIBCPP_STD_VER >= 14
5534   template <size_t _Np>
5535   regex_token_iterator(_BidirectionalIterator __a,
5536                        _BidirectionalIterator __b,
5537                        const regex_type&& __re,
5538                        const int (&__submatches)[_Np],
5539                        regex_constants::match_flag_type __m = regex_constants::match_default) = delete;
5540 #endif
5541
5542   regex_token_iterator(const regex_token_iterator&);
5543   regex_token_iterator& operator=(const regex_token_iterator&);
5544
5545   _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_token_iterator& __x) const;
5546 #if _LIBCPP_STD_VER >= 20
5547   _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI bool operator==(default_sentinel_t) const {
5548     return *this == regex_token_iterator();
5549   }
5550 #endif
5551 #if _LIBCPP_STD_VER < 20
5552   _LIBCPP_HIDE_FROM_ABI bool operator!=(const regex_token_iterator& __x) const { return !(*this == __x); }
5553 #endif
5554
5555   _LIBCPP_HIDE_FROM_ABI const value_type& operator*() const { return *__result_; }
5556   _LIBCPP_HIDE_FROM_ABI const value_type* operator->() const { return __result_; }
5557
5558   regex_token_iterator& operator++();
5559   _LIBCPP_HIDE_FROM_ABI regex_token_iterator operator++(int) {
5560     regex_token_iterator __t(*this);
5561     ++(*this);
5562     return __t;
5563   }
5564
5565 private:
5566   void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
5567   void __establish_result() {
5568     if (__subs_[__n_] == -1)
5569       __result_ = &__position_->prefix();
5570     else
5571       __result_ = &(*__position_)[__subs_[__n_]];
5572   }
5573 };
5574
5575 template <class _BidirectionalIterator, class _CharT, class _Traits>
5576 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator()
5577     : __result_(nullptr), __suffix_(), __n_(0) {}
5578
5579 template <class _BidirectionalIterator, class _CharT, class _Traits>
5580 void regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::__init(
5581     _BidirectionalIterator __a, _BidirectionalIterator __b) {
5582   if (__position_ != _Position())
5583     __establish_result();
5584   else if (__subs_[__n_] == -1) {
5585     __suffix_.matched = true;
5586     __suffix_.first   = __a;
5587     __suffix_.second  = __b;
5588     __result_         = &__suffix_;
5589   } else
5590     __result_ = nullptr;
5591 }
5592
5593 template <class _BidirectionalIterator, class _CharT, class _Traits>
5594 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(
5595     _BidirectionalIterator __a,
5596     _BidirectionalIterator __b,
5597     const regex_type& __re,
5598     int __submatch,
5599     regex_constants::match_flag_type __m)
5600     : __position_(__a, __b, __re, __m), __n_(0), __subs_(1, __submatch) {
5601   __init(__a, __b);
5602 }
5603
5604 template <class _BidirectionalIterator, class _CharT, class _Traits>
5605 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(
5606     _BidirectionalIterator __a,
5607     _BidirectionalIterator __b,
5608     const regex_type& __re,
5609     const vector<int>& __submatches,
5610     regex_constants::match_flag_type __m)
5611     : __position_(__a, __b, __re, __m), __n_(0), __subs_(__submatches) {
5612   __init(__a, __b);
5613 }
5614
5615 #ifndef _LIBCPP_CXX03_LANG
5616
5617 template <class _BidirectionalIterator, class _CharT, class _Traits>
5618 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(
5619     _BidirectionalIterator __a,
5620     _BidirectionalIterator __b,
5621     const regex_type& __re,
5622     initializer_list<int> __submatches,
5623     regex_constants::match_flag_type __m)
5624     : __position_(__a, __b, __re, __m), __n_(0), __subs_(__submatches) {
5625   __init(__a, __b);
5626 }
5627
5628 #endif // _LIBCPP_CXX03_LANG
5629
5630 template <class _BidirectionalIterator, class _CharT, class _Traits>
5631 template <size_t _Np>
5632 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(
5633     _BidirectionalIterator __a,
5634     _BidirectionalIterator __b,
5635     const regex_type& __re,
5636     const int (&__submatches)[_Np],
5637     regex_constants::match_flag_type __m)
5638     : __position_(__a, __b, __re, __m), __n_(0), __subs_(begin(__submatches), end(__submatches)) {
5639   __init(__a, __b);
5640 }
5641
5642 template <class _BidirectionalIterator, class _CharT, class _Traits>
5643 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_token_iterator(const regex_token_iterator& __x)
5644     : __position_(__x.__position_),
5645       __result_(__x.__result_),
5646       __suffix_(__x.__suffix_),
5647       __n_(__x.__n_),
5648       __subs_(__x.__subs_) {
5649   if (__x.__result_ == &__x.__suffix_)
5650     __result_ = &__suffix_;
5651   else if (__result_ != nullptr)
5652     __establish_result();
5653 }
5654
5655 template <class _BidirectionalIterator, class _CharT, class _Traits>
5656 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
5657 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator=(const regex_token_iterator& __x) {
5658   if (this != &__x) {
5659     __position_ = __x.__position_;
5660     if (__x.__result_ == &__x.__suffix_)
5661       __result_ = &__suffix_;
5662     else
5663       __result_ = __x.__result_;
5664     __suffix_ = __x.__suffix_;
5665     __n_      = __x.__n_;
5666     __subs_   = __x.__subs_;
5667
5668     if (__result_ != nullptr && __result_ != &__suffix_)
5669       __establish_result();
5670   }
5671   return *this;
5672 }
5673
5674 template <class _BidirectionalIterator, class _CharT, class _Traits>
5675 bool regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator==(const regex_token_iterator& __x) const {
5676   if (__result_ == nullptr && __x.__result_ == nullptr)
5677     return true;
5678   if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ && __suffix_ == __x.__suffix_)
5679     return true;
5680   if (__result_ == nullptr || __x.__result_ == nullptr)
5681     return false;
5682   if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
5683     return false;
5684   return __position_ == __x.__position_ && __n_ == __x.__n_ && __subs_ == __x.__subs_;
5685 }
5686
5687 template <class _BidirectionalIterator, class _CharT, class _Traits>
5688 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
5689 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++() {
5690   _Position __prev = __position_;
5691   if (__result_ == &__suffix_)
5692     __result_ = nullptr;
5693   else if (static_cast<size_t>(__n_ + 1) < __subs_.size()) {
5694     ++__n_;
5695     __establish_result();
5696   } else {
5697     __n_ = 0;
5698     ++__position_;
5699     if (__position_ != _Position())
5700       __establish_result();
5701     else {
5702       if (std::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end() && __prev->suffix().length() != 0) {
5703         __suffix_.matched = true;
5704         __suffix_.first   = __prev->suffix().first;
5705         __suffix_.second  = __prev->suffix().second;
5706         __result_         = &__suffix_;
5707       } else
5708         __result_ = nullptr;
5709     }
5710   }
5711   return *this;
5712 }
5713
5714 // regex_replace
5715
5716 template <class _OutputIterator, class _BidirectionalIterator, class _Traits, class _CharT>
5717 _LIBCPP_HIDE_FROM_ABI _OutputIterator regex_replace(
5718     _OutputIterator __output_iter,
5719     _BidirectionalIterator __first,
5720     _BidirectionalIterator __last,
5721     const basic_regex<_CharT, _Traits>& __e,
5722     const _CharT* __fmt,
5723     regex_constants::match_flag_type __flags = regex_constants::match_default) {
5724   typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
5725   _Iter __i(__first, __last, __e, __flags);
5726   _Iter __eof;
5727   if (__i == __eof) {
5728     if (!(__flags & regex_constants::format_no_copy))
5729       __output_iter = std::copy(__first, __last, __output_iter);
5730   } else {
5731     sub_match<_BidirectionalIterator> __lm;
5732     for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i) {
5733       if (!(__flags & regex_constants::format_no_copy))
5734         __output_iter = std::copy(__i->prefix().first, __i->prefix().second, __output_iter);
5735       __output_iter = __i->format(__output_iter, __fmt, __fmt + __len, __flags);
5736       __lm          = __i->suffix();
5737       if (__flags & regex_constants::format_first_only)
5738         break;
5739     }
5740     if (!(__flags & regex_constants::format_no_copy))
5741       __output_iter = std::copy(__lm.first, __lm.second, __output_iter);
5742   }
5743   return __output_iter;
5744 }
5745
5746 template <class _OutputIterator, class _BidirectionalIterator, class _Traits, class _CharT, class _ST, class _SA>
5747 inline _LIBCPP_HIDE_FROM_ABI _OutputIterator regex_replace(
5748     _OutputIterator __output_iter,
5749     _BidirectionalIterator __first,
5750     _BidirectionalIterator __last,
5751     const basic_regex<_CharT, _Traits>& __e,
5752     const basic_string<_CharT, _ST, _SA>& __fmt,
5753     regex_constants::match_flag_type __flags = regex_constants::match_default) {
5754   return std::regex_replace(__output_iter, __first, __last, __e, __fmt.c_str(), __flags);
5755 }
5756
5757 template <class _Traits, class _CharT, class _ST, class _SA, class _FST, class _FSA>
5758 inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT, _ST, _SA>
5759 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
5760               const basic_regex<_CharT, _Traits>& __e,
5761               const basic_string<_CharT, _FST, _FSA>& __fmt,
5762               regex_constants::match_flag_type __flags = regex_constants::match_default) {
5763   basic_string<_CharT, _ST, _SA> __r;
5764   std::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e, __fmt.c_str(), __flags);
5765   return __r;
5766 }
5767
5768 template <class _Traits, class _CharT, class _ST, class _SA>
5769 inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT, _ST, _SA>
5770 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
5771               const basic_regex<_CharT, _Traits>& __e,
5772               const _CharT* __fmt,
5773               regex_constants::match_flag_type __flags = regex_constants::match_default) {
5774   basic_string<_CharT, _ST, _SA> __r;
5775   std::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e, __fmt, __flags);
5776   return __r;
5777 }
5778
5779 template <class _Traits, class _CharT, class _ST, class _SA>
5780 inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT>
5781 regex_replace(const _CharT* __s,
5782               const basic_regex<_CharT, _Traits>& __e,
5783               const basic_string<_CharT, _ST, _SA>& __fmt,
5784               regex_constants::match_flag_type __flags = regex_constants::match_default) {
5785   basic_string<_CharT> __r;
5786   std::regex_replace(std::back_inserter(__r), __s, __s + char_traits<_CharT>::length(__s), __e, __fmt.c_str(), __flags);
5787   return __r;
5788 }
5789
5790 template <class _Traits, class _CharT>
5791 inline _LIBCPP_HIDE_FROM_ABI basic_string<_CharT>
5792 regex_replace(const _CharT* __s,
5793               const basic_regex<_CharT, _Traits>& __e,
5794               const _CharT* __fmt,
5795               regex_constants::match_flag_type __flags = regex_constants::match_default) {
5796   basic_string<_CharT> __r;
5797   std::regex_replace(std::back_inserter(__r), __s, __s + char_traits<_CharT>::length(__s), __e, __fmt, __flags);
5798   return __r;
5799 }
5800
5801 _LIBCPP_END_NAMESPACE_STD
5802
5803 #if _LIBCPP_STD_VER >= 17
5804 _LIBCPP_BEGIN_NAMESPACE_STD
5805 namespace pmr {
5806 template <class _BidirT>
5807 using match_results _LIBCPP_AVAILABILITY_PMR =
5808     std::match_results<_BidirT, polymorphic_allocator<std::sub_match<_BidirT>>>;
5809
5810 using cmatch _LIBCPP_AVAILABILITY_PMR = match_results<const char*>;
5811 using smatch _LIBCPP_AVAILABILITY_PMR = match_results<std::pmr::string::const_iterator>;
5812
5813 #  if _LIBCPP_HAS_WIDE_CHARACTERS
5814 using wcmatch _LIBCPP_AVAILABILITY_PMR = match_results<const wchar_t*>;
5815 using wsmatch _LIBCPP_AVAILABILITY_PMR = match_results<std::pmr::wstring::const_iterator>;
5816 #  endif
5817 } // namespace pmr
5818 _LIBCPP_END_NAMESPACE_STD
5819 #endif
5820
5821 _LIBCPP_POP_MACROS
5822
5823 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
5824 #  include <atomic>
5825 #  include <concepts>
5826 #  include <cstdlib>
5827 #  include <iosfwd>
5828 #  include <iterator>
5829 #  include <mutex>
5830 #  include <new>
5831 #  include <type_traits>
5832 #  include <typeinfo>
5833 #  include <utility>
5834 #endif
5835
5836 #endif // _LIBCPP_REGEX