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