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