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_(), __at_first_(false) {}
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, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
2780         _LIBCPP_INLINE_VISIBILITY
2781         basic_regex&
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, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2802         _LIBCPP_INLINE_VISIBILITY
2803         basic_regex&
2804         assign(_ForwardIterator __first, _ForwardIterator __last,
2805                             flag_type __f = regex_constants::ECMAScript)
2806         {
2807             return assign(basic_regex(__first, __last, __f));
2808         }
2809
2810 #ifndef _LIBCPP_CXX03_LANG
2811
2812     _LIBCPP_INLINE_VISIBILITY
2813     basic_regex& assign(initializer_list<value_type> __il,
2814                         flag_type __f = regex_constants::ECMAScript)
2815         {return assign(__il.begin(), __il.end(), __f);}
2816
2817 #endif // _LIBCPP_CXX03_LANG
2818
2819     // const operations:
2820     _LIBCPP_INLINE_VISIBILITY
2821     unsigned mark_count() const {return __marked_count_;}
2822     _LIBCPP_INLINE_VISIBILITY
2823     flag_type flags() const {return __flags_;}
2824
2825     // locale:
2826     _LIBCPP_INLINE_VISIBILITY
2827     locale_type imbue(locale_type __loc)
2828     {
2829         __member_init(ECMAScript);
2830         __start_.reset();
2831         return __traits_.imbue(__loc);
2832     }
2833     _LIBCPP_INLINE_VISIBILITY
2834     locale_type getloc() const {return __traits_.getloc();}
2835
2836     // swap:
2837     void swap(basic_regex& __r);
2838
2839 private:
2840     _LIBCPP_INLINE_VISIBILITY
2841     unsigned __loop_count() const {return __loop_count_;}
2842
2843     _LIBCPP_INLINE_VISIBILITY
2844     bool __use_multiline() const
2845     {
2846         return __get_grammar(__flags_) == ECMAScript && (__flags_ & multiline);
2847     }
2848
2849     template <class _ForwardIterator>
2850         void
2851         __init(_ForwardIterator __first, _ForwardIterator __last);
2852     template <class _ForwardIterator>
2853         _ForwardIterator
2854         __parse(_ForwardIterator __first, _ForwardIterator __last);
2855     template <class _ForwardIterator>
2856         _ForwardIterator
2857         __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2858     template <class _ForwardIterator>
2859         _ForwardIterator
2860         __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
2861     template <class _ForwardIterator>
2862         _ForwardIterator
2863         __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
2864     template <class _ForwardIterator>
2865         _ForwardIterator
2866         __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
2867     template <class _ForwardIterator>
2868         _ForwardIterator
2869         __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
2870     template <class _ForwardIterator>
2871         _ForwardIterator
2872         __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
2873     template <class _ForwardIterator>
2874         _ForwardIterator
2875         __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
2876     template <class _ForwardIterator>
2877         _ForwardIterator
2878         __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
2879     template <class _ForwardIterator>
2880         _ForwardIterator
2881         __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
2882     template <class _ForwardIterator>
2883         _ForwardIterator
2884         __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
2885     template <class _ForwardIterator>
2886         _ForwardIterator
2887         __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2888     template <class _ForwardIterator>
2889         _ForwardIterator
2890         __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2891     template <class _ForwardIterator>
2892         _ForwardIterator
2893         __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2894                                __owns_one_state<_CharT>* __s,
2895                                unsigned __mexp_begin, unsigned __mexp_end);
2896     template <class _ForwardIterator>
2897         _ForwardIterator
2898         __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2899                                 __owns_one_state<_CharT>* __s,
2900                                 unsigned __mexp_begin, unsigned __mexp_end);
2901     template <class _ForwardIterator>
2902         _ForwardIterator
2903         __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
2904     template <class _ForwardIterator>
2905         _ForwardIterator
2906         __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last,
2907                             __bracket_expression<_CharT, _Traits>* __ml);
2908     template <class _ForwardIterator>
2909         _ForwardIterator
2910         __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last,
2911                                 __bracket_expression<_CharT, _Traits>* __ml);
2912     template <class _ForwardIterator>
2913         _ForwardIterator
2914         __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last,
2915                                   __bracket_expression<_CharT, _Traits>* __ml);
2916     template <class _ForwardIterator>
2917         _ForwardIterator
2918         __parse_character_class(_ForwardIterator __first, _ForwardIterator __last,
2919                                 __bracket_expression<_CharT, _Traits>* __ml);
2920     template <class _ForwardIterator>
2921         _ForwardIterator
2922         __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last,
2923                                  basic_string<_CharT>& __col_sym);
2924     template <class _ForwardIterator>
2925         _ForwardIterator
2926         __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
2927     template <class _ForwardIterator>
2928         _ForwardIterator
2929         __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2930     template <class _ForwardIterator>
2931         _ForwardIterator
2932         __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
2933     template <class _ForwardIterator>
2934         _ForwardIterator
2935         __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
2936     template <class _ForwardIterator>
2937         _ForwardIterator
2938         __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
2939     template <class _ForwardIterator>
2940         _ForwardIterator
2941         __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2942     template <class _ForwardIterator>
2943         _ForwardIterator
2944         __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2945     template <class _ForwardIterator>
2946         _ForwardIterator
2947         __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);
2948     template <class _ForwardIterator>
2949         _ForwardIterator
2950         __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);
2951     template <class _ForwardIterator>
2952         _ForwardIterator
2953         __parse_term(_ForwardIterator __first, _ForwardIterator __last);
2954     template <class _ForwardIterator>
2955         _ForwardIterator
2956         __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);
2957     template <class _ForwardIterator>
2958         _ForwardIterator
2959         __parse_atom(_ForwardIterator __first, _ForwardIterator __last);
2960     template <class _ForwardIterator>
2961         _ForwardIterator
2962         __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);
2963     template <class _ForwardIterator>
2964         _ForwardIterator
2965         __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);
2966     template <class _ForwardIterator>
2967         _ForwardIterator
2968         __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);
2969     template <class _ForwardIterator>
2970         _ForwardIterator
2971         __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last,
2972                                  basic_string<_CharT>* __str = nullptr);
2973     template <class _ForwardIterator>
2974         _ForwardIterator
2975         __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);
2976     template <class _ForwardIterator>
2977         _ForwardIterator
2978         __parse_grep(_ForwardIterator __first, _ForwardIterator __last);
2979     template <class _ForwardIterator>
2980         _ForwardIterator
2981         __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);
2982     template <class _ForwardIterator>
2983         _ForwardIterator
2984         __parse_class_escape(_ForwardIterator __first, _ForwardIterator __last,
2985                           basic_string<_CharT>& __str,
2986                           __bracket_expression<_CharT, _Traits>* __ml);
2987     template <class _ForwardIterator>
2988         _ForwardIterator
2989         __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last,
2990                           basic_string<_CharT>* __str = nullptr);
2991
2992     bool __test_back_ref(_CharT);
2993
2994     _LIBCPP_INLINE_VISIBILITY
2995     void __push_l_anchor();
2996     void __push_r_anchor();
2997     void __push_match_any();
2998     void __push_match_any_but_newline();
2999     _LIBCPP_INLINE_VISIBILITY
3000     void __push_greedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
3001                                   unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
3002         {__push_loop(__min, numeric_limits<size_t>::max(), __s,
3003                      __mexp_begin, __mexp_end);}
3004     _LIBCPP_INLINE_VISIBILITY
3005     void __push_nongreedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
3006                                   unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
3007         {__push_loop(__min, numeric_limits<size_t>::max(), __s,
3008                      __mexp_begin, __mexp_end, false);}
3009     void __push_loop(size_t __min, size_t __max, __owns_one_state<_CharT>* __s,
3010                      size_t __mexp_begin = 0, size_t __mexp_end = 0,
3011                      bool __greedy = true);
3012     __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);
3013     void __push_char(value_type __c);
3014     void __push_back_ref(int __i);
3015     void __push_alternation(__owns_one_state<_CharT>* __sa,
3016                             __owns_one_state<_CharT>* __sb);
3017     void __push_begin_marked_subexpression();
3018     void __push_end_marked_subexpression(unsigned);
3019     void __push_empty();
3020     void __push_word_boundary(bool);
3021     void __push_lookahead(const basic_regex&, bool, unsigned);
3022
3023     template <class _Allocator>
3024         bool
3025         __search(const _CharT* __first, const _CharT* __last,
3026                  match_results<const _CharT*, _Allocator>& __m,
3027                  regex_constants::match_flag_type __flags) const;
3028
3029     template <class _Allocator>
3030         bool
3031         __match_at_start(const _CharT* __first, const _CharT* __last,
3032                  match_results<const _CharT*, _Allocator>& __m,
3033                  regex_constants::match_flag_type __flags, bool) const;
3034     template <class _Allocator>
3035         bool
3036         __match_at_start_ecma(const _CharT* __first, const _CharT* __last,
3037                  match_results<const _CharT*, _Allocator>& __m,
3038                  regex_constants::match_flag_type __flags, bool) const;
3039     template <class _Allocator>
3040         bool
3041         __match_at_start_posix_nosubs(const _CharT* __first, const _CharT* __last,
3042                  match_results<const _CharT*, _Allocator>& __m,
3043                  regex_constants::match_flag_type __flags, bool) const;
3044     template <class _Allocator>
3045         bool
3046         __match_at_start_posix_subs(const _CharT* __first, const _CharT* __last,
3047                  match_results<const _CharT*, _Allocator>& __m,
3048                  regex_constants::match_flag_type __flags, bool) const;
3049
3050     template <class _Bp, class _Ap, class _Cp, class _Tp>
3051     friend
3052     bool
3053     regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
3054                  regex_constants::match_flag_type);
3055
3056     template <class _Ap, class _Cp, class _Tp>
3057     friend
3058     bool
3059     regex_search(const _Cp*, const _Cp*, match_results<const _Cp*, _Ap>&,
3060                  const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
3061
3062     template <class _Bp, class _Cp, class _Tp>
3063     friend
3064     bool
3065     regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&,
3066                  regex_constants::match_flag_type);
3067
3068     template <class _Cp, class _Tp>
3069     friend
3070     bool
3071     regex_search(const _Cp*, const _Cp*,
3072                  const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
3073
3074     template <class _Cp, class _Ap, class _Tp>
3075     friend
3076     bool
3077     regex_search(const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&,
3078                  regex_constants::match_flag_type);
3079
3080     template <class _ST, class _SA, class _Cp, class _Tp>
3081     friend
3082     bool
3083     regex_search(const basic_string<_Cp, _ST, _SA>& __s,
3084                  const basic_regex<_Cp, _Tp>& __e,
3085                  regex_constants::match_flag_type __flags);
3086
3087     template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
3088     friend
3089     bool
3090     regex_search(const basic_string<_Cp, _ST, _SA>& __s,
3091                  match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
3092                  const basic_regex<_Cp, _Tp>& __e,
3093                  regex_constants::match_flag_type __flags);
3094
3095     template <class _Iter, class _Ap, class _Cp, class _Tp>
3096     friend
3097     bool
3098     regex_search(__wrap_iter<_Iter> __first,
3099                  __wrap_iter<_Iter> __last,
3100                  match_results<__wrap_iter<_Iter>, _Ap>& __m,
3101                  const basic_regex<_Cp, _Tp>& __e,
3102                  regex_constants::match_flag_type __flags);
3103
3104     template <class, class> friend class __lookahead;
3105 };
3106
3107 #if _LIBCPP_STD_VER >= 17
3108 template <class _ForwardIterator,
3109           __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
3110 basic_regex(_ForwardIterator, _ForwardIterator,
3111             regex_constants::syntax_option_type = regex_constants::ECMAScript)
3112     -> basic_regex<typename iterator_traits<_ForwardIterator>::value_type>;
3113 #endif
3114
3115 template <class _CharT, class _Traits>
3116     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;
3117 template <class _CharT, class _Traits>
3118     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;
3119 template <class _CharT, class _Traits>
3120     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;
3121 template <class _CharT, class _Traits>
3122     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;
3123 template <class _CharT, class _Traits>
3124     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;
3125 template <class _CharT, class _Traits>
3126     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;
3127 template <class _CharT, class _Traits>
3128     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;
3129 template <class _CharT, class _Traits>
3130     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;
3131 template <class _CharT, class _Traits>
3132     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;
3133 template <class _CharT, class _Traits>
3134     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;
3135
3136 template <class _CharT, class _Traits>
3137 void
3138 basic_regex<_CharT, _Traits>::swap(basic_regex& __r)
3139 {
3140     using _VSTD::swap;
3141     swap(__traits_, __r.__traits_);
3142     swap(__flags_, __r.__flags_);
3143     swap(__marked_count_, __r.__marked_count_);
3144     swap(__loop_count_, __r.__loop_count_);
3145     swap(__open_count_, __r.__open_count_);
3146     swap(__start_, __r.__start_);
3147     swap(__end_, __r.__end_);
3148 }
3149
3150 template <class _CharT, class _Traits>
3151 inline _LIBCPP_INLINE_VISIBILITY
3152 void
3153 swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y)
3154 {
3155     return __x.swap(__y);
3156 }
3157
3158 // __lookahead
3159
3160 template <class _CharT, class _Traits>
3161 class __lookahead
3162     : public __owns_one_state<_CharT>
3163 {
3164     typedef __owns_one_state<_CharT> base;
3165
3166     basic_regex<_CharT, _Traits> __exp_;
3167     unsigned __mexp_;
3168     bool __invert_;
3169
3170     __lookahead(const __lookahead&);
3171     __lookahead& operator=(const __lookahead&);
3172 public:
3173     typedef _VSTD::__state<_CharT> __state;
3174
3175     _LIBCPP_INLINE_VISIBILITY
3176     __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
3177         : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}
3178
3179     _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual void __exec(__state&) const;
3180 };
3181
3182 template <class _CharT, class _Traits>
3183 void
3184 __lookahead<_CharT, _Traits>::__exec(__state& __s) const
3185 {
3186     match_results<const _CharT*> __m;
3187     __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);
3188     bool __matched = __exp_.__match_at_start_ecma(
3189         __s.__current_, __s.__last_,
3190         __m,
3191         (__s.__flags_ | regex_constants::match_continuous) &
3192         ~regex_constants::__full_match,
3193         __s.__at_first_ && __s.__current_ == __s.__first_);
3194     if (__matched != __invert_)
3195     {
3196         __s.__do_ = __state::__accept_but_not_consume;
3197         __s.__node_ = this->first();
3198         for (unsigned __i = 1; __i < __m.size(); ++__i) {
3199             __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
3200         }
3201     }
3202     else
3203     {
3204         __s.__do_ = __state::__reject;
3205         __s.__node_ = nullptr;
3206     }
3207 }
3208
3209 template <class _CharT, class _Traits>
3210 template <class _ForwardIterator>
3211 void
3212 basic_regex<_CharT, _Traits>::__init(_ForwardIterator __first, _ForwardIterator __last)
3213 {
3214     if (__get_grammar(__flags_) == 0) __flags_ |= regex_constants::ECMAScript;
3215     _ForwardIterator __temp = __parse(__first, __last);
3216     if ( __temp != __last)
3217         __throw_regex_error<regex_constants::__re_err_parse>();
3218 }
3219
3220 template <class _CharT, class _Traits>
3221 template <class _ForwardIterator>
3222 _ForwardIterator
3223 basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
3224                                       _ForwardIterator __last)
3225 {
3226     {
3227         unique_ptr<__node> __h(new __end_state<_CharT>);
3228         __start_.reset(new __empty_state<_CharT>(__h.get()));
3229         __h.release();
3230         __end_ = __start_.get();
3231     }
3232     switch (__get_grammar(__flags_))
3233     {
3234     case ECMAScript:
3235         __first = __parse_ecma_exp(__first, __last);
3236         break;
3237     case basic:
3238         __first = __parse_basic_reg_exp(__first, __last);
3239         break;
3240     case extended:
3241     case awk:
3242         __first = __parse_extended_reg_exp(__first, __last);
3243         break;
3244     case grep:
3245         __first = __parse_grep(__first, __last);
3246         break;
3247     case egrep:
3248         __first = __parse_egrep(__first, __last);
3249         break;
3250     default:
3251         __throw_regex_error<regex_constants::__re_err_grammar>();
3252     }
3253     return __first;
3254 }
3255
3256 template <class _CharT, class _Traits>
3257 template <class _ForwardIterator>
3258 _ForwardIterator
3259 basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
3260                                                     _ForwardIterator __last)
3261 {
3262     if (__first != __last)
3263     {
3264         if (*__first == '^')
3265         {
3266             __push_l_anchor();
3267             ++__first;
3268         }
3269         if (__first != __last)
3270         {
3271             __first = __parse_RE_expression(__first, __last);
3272             if (__first != __last)
3273             {
3274                 _ForwardIterator __temp = _VSTD::next(__first);
3275                 if (__temp == __last && *__first == '$')
3276                 {
3277                     __push_r_anchor();
3278                     ++__first;
3279                 }
3280             }
3281         }
3282         if (__first != __last)
3283             __throw_regex_error<regex_constants::__re_err_empty>();
3284     }
3285     return __first;
3286 }
3287
3288 template <class _CharT, class _Traits>
3289 template <class _ForwardIterator>
3290 _ForwardIterator
3291 basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
3292                                                        _ForwardIterator __last)
3293 {
3294     __owns_one_state<_CharT>* __sa = __end_;
3295     _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
3296     if (__temp == __first)
3297         __throw_regex_error<regex_constants::__re_err_empty>();
3298     __first = __temp;
3299     while (__first != __last && *__first == '|')
3300     {
3301         __owns_one_state<_CharT>* __sb = __end_;
3302         __temp = __parse_ERE_branch(++__first, __last);
3303         if (__temp == __first)
3304             __throw_regex_error<regex_constants::__re_err_empty>();
3305         __push_alternation(__sa, __sb);
3306         __first = __temp;
3307     }
3308     return __first;
3309 }
3310
3311 template <class _CharT, class _Traits>
3312 template <class _ForwardIterator>
3313 _ForwardIterator
3314 basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
3315                                                  _ForwardIterator __last)
3316 {
3317     _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
3318     if (__temp == __first)
3319         __throw_regex_error<regex_constants::__re_err_empty>();
3320     do
3321     {
3322         __first = __temp;
3323         __temp = __parse_ERE_expression(__first, __last);
3324     } while (__temp != __first);
3325     return __first;
3326 }
3327
3328 template <class _CharT, class _Traits>
3329 template <class _ForwardIterator>
3330 _ForwardIterator
3331 basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
3332                                                      _ForwardIterator __last)
3333 {
3334     __owns_one_state<_CharT>* __e = __end_;
3335     unsigned __mexp_begin = __marked_count_;
3336     _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
3337     if (__temp == __first && __temp != __last)
3338     {
3339         switch (*__temp)
3340         {
3341         case '^':
3342             __push_l_anchor();
3343             ++__temp;
3344             break;
3345         case '$':
3346             __push_r_anchor();
3347             ++__temp;
3348             break;
3349         case '(':
3350             __push_begin_marked_subexpression();
3351             unsigned __temp_count = __marked_count_;
3352             ++__open_count_;
3353             __temp = __parse_extended_reg_exp(++__temp, __last);
3354             if (__temp == __last || *__temp != ')')
3355                 __throw_regex_error<regex_constants::error_paren>();
3356             __push_end_marked_subexpression(__temp_count);
3357             --__open_count_;
3358             ++__temp;
3359             break;
3360         }
3361     }
3362     if (__temp != __first)
3363         __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin+1,
3364                                          __marked_count_+1);
3365     __first = __temp;
3366     return __first;
3367 }
3368
3369 template <class _CharT, class _Traits>
3370 template <class _ForwardIterator>
3371 _ForwardIterator
3372 basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
3373                                                     _ForwardIterator __last)
3374 {
3375     while (true)
3376     {
3377         _ForwardIterator __temp = __parse_simple_RE(__first, __last);
3378         if (__temp == __first)
3379             break;
3380         __first = __temp;
3381     }
3382     return __first;
3383 }
3384
3385 template <class _CharT, class _Traits>
3386 template <class _ForwardIterator>
3387 _ForwardIterator
3388 basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
3389                                                 _ForwardIterator __last)
3390 {
3391     if (__first != __last)
3392     {
3393         __owns_one_state<_CharT>* __e = __end_;
3394         unsigned __mexp_begin = __marked_count_;
3395         _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
3396         if (__temp != __first)
3397             __first = __parse_RE_dupl_symbol(__temp, __last, __e,
3398                                              __mexp_begin+1, __marked_count_+1);
3399     }
3400     return __first;
3401 }
3402
3403 template <class _CharT, class _Traits>
3404 template <class _ForwardIterator>
3405 _ForwardIterator
3406 basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
3407                                                  _ForwardIterator __last)
3408 {
3409     _ForwardIterator __temp = __first;
3410     __first = __parse_one_char_or_coll_elem_RE(__first, __last);
3411     if (__temp == __first)
3412     {
3413         __temp = __parse_Back_open_paren(__first, __last);
3414         if (__temp != __first)
3415         {
3416             __push_begin_marked_subexpression();
3417             unsigned __temp_count = __marked_count_;
3418             __first = __parse_RE_expression(__temp, __last);
3419             __temp = __parse_Back_close_paren(__first, __last);
3420             if (__temp == __first)
3421                 __throw_regex_error<regex_constants::error_paren>();
3422             __push_end_marked_subexpression(__temp_count);
3423             __first = __temp;
3424         }
3425         else
3426             __first = __parse_BACKREF(__first, __last);
3427     }
3428     return __first;
3429 }
3430
3431 template <class _CharT, class _Traits>
3432 template <class _ForwardIterator>
3433 _ForwardIterator
3434 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
3435                                                        _ForwardIterator __first,
3436                                                        _ForwardIterator __last)
3437 {
3438     _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
3439     if (__temp == __first)
3440     {
3441         __temp = __parse_QUOTED_CHAR(__first, __last);
3442         if (__temp == __first)
3443         {
3444             if (__temp != __last && *__temp == '.')
3445             {
3446                 __push_match_any();
3447                 ++__temp;
3448             }
3449             else
3450                 __temp = __parse_bracket_expression(__first, __last);
3451         }
3452     }
3453     __first = __temp;
3454     return __first;
3455 }
3456
3457 template <class _CharT, class _Traits>
3458 template <class _ForwardIterator>
3459 _ForwardIterator
3460 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
3461                                                        _ForwardIterator __first,
3462                                                        _ForwardIterator __last)
3463 {
3464     _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
3465     if (__temp == __first)
3466     {
3467         __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
3468         if (__temp == __first)
3469         {
3470             if (__temp != __last && *__temp == '.')
3471             {
3472                 __push_match_any();
3473                 ++__temp;
3474             }
3475             else
3476                 __temp = __parse_bracket_expression(__first, __last);
3477         }
3478     }
3479     __first = __temp;
3480     return __first;
3481 }
3482
3483 template <class _CharT, class _Traits>
3484 template <class _ForwardIterator>
3485 _ForwardIterator
3486 basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
3487                                                       _ForwardIterator __last)
3488 {
3489     if (__first != __last)
3490     {
3491         _ForwardIterator __temp = _VSTD::next(__first);
3492         if (__temp != __last)
3493         {
3494             if (*__first == '\\' && *__temp == '(')
3495                 __first = ++__temp;
3496         }
3497     }
3498     return __first;
3499 }
3500
3501 template <class _CharT, class _Traits>
3502 template <class _ForwardIterator>
3503 _ForwardIterator
3504 basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
3505                                                        _ForwardIterator __last)
3506 {
3507     if (__first != __last)
3508     {
3509         _ForwardIterator __temp = _VSTD::next(__first);
3510         if (__temp != __last)
3511         {
3512             if (*__first == '\\' && *__temp == ')')
3513                 __first = ++__temp;
3514         }
3515     }
3516     return __first;
3517 }
3518
3519 template <class _CharT, class _Traits>
3520 template <class _ForwardIterator>
3521 _ForwardIterator
3522 basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
3523                                                       _ForwardIterator __last)
3524 {
3525     if (__first != __last)
3526     {
3527         _ForwardIterator __temp = _VSTD::next(__first);
3528         if (__temp != __last)
3529         {
3530             if (*__first == '\\' && *__temp == '{')
3531                 __first = ++__temp;
3532         }
3533     }
3534     return __first;
3535 }
3536
3537 template <class _CharT, class _Traits>
3538 template <class _ForwardIterator>
3539 _ForwardIterator
3540 basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
3541                                                        _ForwardIterator __last)
3542 {
3543     if (__first != __last)
3544     {
3545         _ForwardIterator __temp = _VSTD::next(__first);
3546         if (__temp != __last)
3547         {
3548             if (*__first == '\\' && *__temp == '}')
3549                 __first = ++__temp;
3550         }
3551     }
3552     return __first;
3553 }
3554
3555 template <class _CharT, class _Traits>
3556 template <class _ForwardIterator>
3557 _ForwardIterator
3558 basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
3559                                               _ForwardIterator __last)
3560 {
3561     if (__first != __last)
3562     {
3563         _ForwardIterator __temp = _VSTD::next(__first);
3564         if (__temp != __last && *__first == '\\' && __test_back_ref(*__temp))
3565             __first = ++__temp;
3566     }
3567     return __first;
3568 }
3569
3570 template <class _CharT, class _Traits>
3571 template <class _ForwardIterator>
3572 _ForwardIterator
3573 basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
3574                                                _ForwardIterator __last)
3575 {
3576     if (__first != __last)
3577     {
3578         _ForwardIterator __temp = _VSTD::next(__first);
3579         if (__temp == __last && *__first == '$')
3580             return __first;
3581         // Not called inside a bracket
3582         if (*__first == '.' || *__first == '\\' || *__first == '[')
3583             return __first;
3584         __push_char(*__first);
3585         ++__first;
3586     }
3587     return __first;
3588 }
3589
3590 template <class _CharT, class _Traits>
3591 template <class _ForwardIterator>
3592 _ForwardIterator
3593 basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
3594                                                    _ForwardIterator __last)
3595 {
3596     if (__first != __last)
3597     {
3598         switch (*__first)
3599         {
3600         case '^':
3601         case '.':
3602         case '[':
3603         case '$':
3604         case '(':
3605         case '|':
3606         case '*':
3607         case '+':
3608         case '?':
3609         case '{':
3610         case '\\':
3611             break;
3612         case ')':
3613             if (__open_count_ == 0)
3614             {
3615                 __push_char(*__first);
3616                 ++__first;
3617             }
3618             break;
3619         default:
3620             __push_char(*__first);
3621             ++__first;
3622             break;
3623         }
3624     }
3625     return __first;
3626 }
3627
3628 template <class _CharT, class _Traits>
3629 template <class _ForwardIterator>
3630 _ForwardIterator
3631 basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
3632                                                   _ForwardIterator __last)
3633 {
3634     if (__first != __last)
3635     {
3636         _ForwardIterator __temp = _VSTD::next(__first);
3637         if (__temp != __last)
3638         {
3639             if (*__first == '\\')
3640             {
3641                 switch (*__temp)
3642                 {
3643                 case '^':
3644                 case '.':
3645                 case '*':
3646                 case '[':
3647                 case '$':
3648                 case '\\':
3649                     __push_char(*__temp);
3650                     __first = ++__temp;
3651                     break;
3652                 }
3653             }
3654         }
3655     }
3656     return __first;
3657 }
3658
3659 template <class _CharT, class _Traits>
3660 template <class _ForwardIterator>
3661 _ForwardIterator
3662 basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
3663                                                       _ForwardIterator __last)
3664 {
3665     if (__first != __last)
3666     {
3667         _ForwardIterator __temp = _VSTD::next(__first);
3668         if (__temp != __last)
3669         {
3670             if (*__first == '\\')
3671             {
3672                 switch (*__temp)
3673                 {
3674                 case '^':
3675                 case '.':
3676                 case '*':
3677                 case '[':
3678                 case '$':
3679                 case '\\':
3680                 case '(':
3681                 case ')':
3682                 case '|':
3683                 case '+':
3684                 case '?':
3685                 case '{':
3686                 case '}':
3687                     __push_char(*__temp);
3688                     __first = ++__temp;
3689                     break;
3690                 default:
3691                     if (__get_grammar(__flags_) == awk)
3692                         __first = __parse_awk_escape(++__first, __last);
3693                     else if(__test_back_ref(*__temp))
3694                         __first = ++__temp;
3695                     break;
3696                 }
3697             }
3698         }
3699     }
3700     return __first;
3701 }
3702
3703 template <class _CharT, class _Traits>
3704 template <class _ForwardIterator>
3705 _ForwardIterator
3706 basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
3707                                                      _ForwardIterator __last,
3708                                                      __owns_one_state<_CharT>* __s,
3709                                                      unsigned __mexp_begin,
3710                                                      unsigned __mexp_end)
3711 {
3712     if (__first != __last)
3713     {
3714         if (*__first == '*')
3715         {
3716             __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3717             ++__first;
3718         }
3719         else
3720         {
3721             _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
3722             if (__temp != __first)
3723             {
3724                 int __min = 0;
3725                 __first = __temp;
3726                 __temp = __parse_DUP_COUNT(__first, __last, __min);
3727                 if (__temp == __first)
3728                     __throw_regex_error<regex_constants::error_badbrace>();
3729                 __first = __temp;
3730                 if (__first == __last)
3731                     __throw_regex_error<regex_constants::error_brace>();
3732                 if (*__first != ',')
3733                 {
3734                     __temp = __parse_Back_close_brace(__first, __last);
3735                     if (__temp == __first)
3736                         __throw_regex_error<regex_constants::error_brace>();
3737                     __push_loop(__min, __min, __s, __mexp_begin, __mexp_end,
3738                                     true);
3739                     __first = __temp;
3740                 }
3741                 else
3742                 {
3743                     ++__first;  // consume ','
3744                     int __max = -1;
3745                     __first = __parse_DUP_COUNT(__first, __last, __max);
3746                     __temp = __parse_Back_close_brace(__first, __last);
3747                     if (__temp == __first)
3748                         __throw_regex_error<regex_constants::error_brace>();
3749                     if (__max == -1)
3750                         __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3751                     else
3752                     {
3753                         if (__max < __min)
3754                             __throw_regex_error<regex_constants::error_badbrace>();
3755                         __push_loop(__min, __max, __s, __mexp_begin, __mexp_end,
3756                                     true);
3757                     }
3758                     __first = __temp;
3759                 }
3760             }
3761         }
3762     }
3763     return __first;
3764 }
3765
3766 template <class _CharT, class _Traits>
3767 template <class _ForwardIterator>
3768 _ForwardIterator
3769 basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
3770                                                       _ForwardIterator __last,
3771                                                       __owns_one_state<_CharT>* __s,
3772                                                       unsigned __mexp_begin,
3773                                                       unsigned __mexp_end)
3774 {
3775     if (__first != __last)
3776     {
3777         unsigned __grammar = __get_grammar(__flags_);
3778         switch (*__first)
3779         {
3780         case '*':
3781             ++__first;
3782             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3783             {
3784                 ++__first;
3785                 __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3786             }
3787             else
3788                 __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3789             break;
3790         case '+':
3791             ++__first;
3792             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3793             {
3794                 ++__first;
3795                 __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3796             }
3797             else
3798                 __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3799             break;
3800         case '?':
3801             ++__first;
3802             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3803             {
3804                 ++__first;
3805                 __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);
3806             }
3807             else
3808                 __push_loop(0, 1, __s, __mexp_begin, __mexp_end);
3809             break;
3810         case '{':
3811             {
3812                 int __min;
3813                 _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);
3814                 if (__temp == __first)
3815                     __throw_regex_error<regex_constants::error_badbrace>();
3816                 __first = __temp;
3817                 if (__first == __last)
3818                     __throw_regex_error<regex_constants::error_brace>();
3819                 switch (*__first)
3820                 {
3821                 case '}':
3822                     ++__first;
3823                     if (__grammar == ECMAScript && __first != __last && *__first == '?')
3824                     {
3825                         ++__first;
3826                         __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);
3827                     }
3828                     else
3829                         __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);
3830                     break;
3831                 case ',':
3832                     ++__first;
3833                     if (__first == __last)
3834                         __throw_regex_error<regex_constants::error_badbrace>();
3835                     if (*__first == '}')
3836                     {
3837                         ++__first;
3838                         if (__grammar == ECMAScript && __first != __last && *__first == '?')
3839                         {
3840                             ++__first;
3841                             __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3842                         }
3843                         else
3844                             __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3845                     }
3846                     else
3847                     {
3848                         int __max = -1;
3849                         __temp = __parse_DUP_COUNT(__first, __last, __max);
3850                         if (__temp == __first)
3851                             __throw_regex_error<regex_constants::error_brace>();
3852                         __first = __temp;
3853                         if (__first == __last || *__first != '}')
3854                             __throw_regex_error<regex_constants::error_brace>();
3855                         ++__first;
3856                         if (__max < __min)
3857                             __throw_regex_error<regex_constants::error_badbrace>();
3858                         if (__grammar == ECMAScript && __first != __last && *__first == '?')
3859                         {
3860                             ++__first;
3861                             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);
3862                         }
3863                         else
3864                             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);
3865                     }
3866                     break;
3867                 default:
3868                     __throw_regex_error<regex_constants::error_badbrace>();
3869                 }
3870             }
3871             break;
3872         }
3873     }
3874     return __first;
3875 }
3876
3877 template <class _CharT, class _Traits>
3878 template <class _ForwardIterator>
3879 _ForwardIterator
3880 basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
3881                                                          _ForwardIterator __last)
3882 {
3883     if (__first != __last && *__first == '[')
3884     {
3885         ++__first;
3886         if (__first == __last)
3887             __throw_regex_error<regex_constants::error_brack>();
3888         bool __negate = false;
3889         if (*__first == '^')
3890         {
3891             ++__first;
3892             __negate = true;
3893         }
3894         __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
3895         // __ml owned by *this
3896         if (__first == __last)
3897             __throw_regex_error<regex_constants::error_brack>();
3898         if (__get_grammar(__flags_) != ECMAScript && *__first == ']')
3899         {
3900             __ml->__add_char(']');
3901             ++__first;
3902         }
3903         __first = __parse_follow_list(__first, __last, __ml);
3904         if (__first == __last)
3905             __throw_regex_error<regex_constants::error_brack>();
3906         if (*__first == '-')
3907         {
3908             __ml->__add_char('-');
3909             ++__first;
3910         }
3911         if (__first == __last || *__first != ']')
3912             __throw_regex_error<regex_constants::error_brack>();
3913         ++__first;
3914     }
3915     return __first;
3916 }
3917
3918 template <class _CharT, class _Traits>
3919 template <class _ForwardIterator>
3920 _ForwardIterator
3921 basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
3922                                     _ForwardIterator __last,
3923                                     __bracket_expression<_CharT, _Traits>* __ml)
3924 {
3925     if (__first != __last)
3926     {
3927         while (true)
3928         {
3929             _ForwardIterator __temp = __parse_expression_term(__first, __last,
3930                                                               __ml);
3931             if (__temp == __first)
3932                 break;
3933             __first = __temp;
3934         }
3935     }
3936     return __first;
3937 }
3938
3939 template <class _CharT, class _Traits>
3940 template <class _ForwardIterator>
3941 _ForwardIterator
3942 basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
3943                                     _ForwardIterator __last,
3944                                     __bracket_expression<_CharT, _Traits>* __ml)
3945 {
3946     if (__first != __last && *__first != ']')
3947     {
3948         _ForwardIterator __temp = _VSTD::next(__first);
3949         basic_string<_CharT> __start_range;
3950         if (__temp != __last && *__first == '[')
3951         {
3952             if (*__temp == '=')
3953                 return __parse_equivalence_class(++__temp, __last, __ml);
3954             else if (*__temp == ':')
3955                 return __parse_character_class(++__temp, __last, __ml);
3956             else if (*__temp == '.')
3957                 __first = __parse_collating_symbol(++__temp, __last, __start_range);
3958         }
3959         unsigned __grammar = __get_grammar(__flags_);
3960         if (__start_range.empty())
3961         {
3962             if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3963             {
3964                 if (__grammar == ECMAScript)
3965                     __first = __parse_class_escape(++__first, __last, __start_range, __ml);
3966                 else
3967                     __first = __parse_awk_escape(++__first, __last, &__start_range);
3968             }
3969             else
3970             {
3971                 __start_range = *__first;
3972                 ++__first;
3973             }
3974         }
3975         if (__first != __last && *__first != ']')
3976         {
3977             __temp = _VSTD::next(__first);
3978             if (__temp != __last && *__first == '-' && *__temp != ']')
3979             {
3980                 // parse a range
3981                 basic_string<_CharT> __end_range;
3982                 __first = __temp;
3983                 ++__temp;
3984                 if (__temp != __last && *__first == '[' && *__temp == '.')
3985                     __first = __parse_collating_symbol(++__temp, __last, __end_range);
3986                 else
3987                 {
3988                     if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3989                     {
3990                         if (__grammar == ECMAScript)
3991                             __first = __parse_class_escape(++__first, __last,
3992                                                            __end_range, __ml);
3993                         else
3994                             __first = __parse_awk_escape(++__first, __last,
3995                                                          &__end_range);
3996                     }
3997                     else
3998                     {
3999                         __end_range = *__first;
4000                         ++__first;
4001                     }
4002                 }
4003                 __ml->__add_range(_VSTD::move(__start_range), _VSTD::move(__end_range));
4004             }
4005             else if (!__start_range.empty())
4006             {
4007                 if (__start_range.size() == 1)
4008                     __ml->__add_char(__start_range[0]);
4009                 else
4010                     __ml->__add_digraph(__start_range[0], __start_range[1]);
4011             }
4012         }
4013         else if (!__start_range.empty())
4014         {
4015             if (__start_range.size() == 1)
4016                 __ml->__add_char(__start_range[0]);
4017             else
4018                 __ml->__add_digraph(__start_range[0], __start_range[1]);
4019         }
4020     }
4021     return __first;
4022 }
4023
4024 template <class _CharT, class _Traits>
4025 template <class _ForwardIterator>
4026 _ForwardIterator
4027 basic_regex<_CharT, _Traits>::__parse_class_escape(_ForwardIterator __first,
4028                           _ForwardIterator __last,
4029                           basic_string<_CharT>& __str,
4030                           __bracket_expression<_CharT, _Traits>* __ml)
4031 {
4032     if (__first == __last)
4033         __throw_regex_error<regex_constants::error_escape>();
4034     switch (*__first)
4035     {
4036     case 0:
4037         __str = *__first;
4038         return ++__first;
4039     case 'b':
4040         __str = _CharT(8);
4041         return ++__first;
4042     case 'd':
4043         __ml->__add_class(ctype_base::digit);
4044         return ++__first;
4045     case 'D':
4046         __ml->__add_neg_class(ctype_base::digit);
4047         return ++__first;
4048     case 's':
4049         __ml->__add_class(ctype_base::space);
4050         return ++__first;
4051     case 'S':
4052         __ml->__add_neg_class(ctype_base::space);
4053         return ++__first;
4054     case 'w':
4055         __ml->__add_class(ctype_base::alnum);
4056         __ml->__add_char('_');
4057         return ++__first;
4058     case 'W':
4059         __ml->__add_neg_class(ctype_base::alnum);
4060         __ml->__add_neg_char('_');
4061         return ++__first;
4062     }
4063     __first = __parse_character_escape(__first, __last, &__str);
4064     return __first;
4065 }
4066
4067 template <class _CharT, class _Traits>
4068 template <class _ForwardIterator>
4069 _ForwardIterator
4070 basic_regex<_CharT, _Traits>::__parse_awk_escape(_ForwardIterator __first,
4071                           _ForwardIterator __last,
4072                           basic_string<_CharT>* __str)
4073 {
4074     if (__first == __last)
4075         __throw_regex_error<regex_constants::error_escape>();
4076     switch (*__first)
4077     {
4078     case '\\':
4079     case '"':
4080     case '/':
4081         if (__str)
4082             *__str = *__first;
4083         else
4084             __push_char(*__first);
4085         return ++__first;
4086     case 'a':
4087         if (__str)
4088             *__str = _CharT(7);
4089         else
4090             __push_char(_CharT(7));
4091         return ++__first;
4092     case 'b':
4093         if (__str)
4094             *__str = _CharT(8);
4095         else
4096             __push_char(_CharT(8));
4097         return ++__first;
4098     case 'f':
4099         if (__str)
4100             *__str = _CharT(0xC);
4101         else
4102             __push_char(_CharT(0xC));
4103         return ++__first;
4104     case 'n':
4105         if (__str)
4106             *__str = _CharT(0xA);
4107         else
4108             __push_char(_CharT(0xA));
4109         return ++__first;
4110     case 'r':
4111         if (__str)
4112             *__str = _CharT(0xD);
4113         else
4114             __push_char(_CharT(0xD));
4115         return ++__first;
4116     case 't':
4117         if (__str)
4118             *__str = _CharT(0x9);
4119         else
4120             __push_char(_CharT(0x9));
4121         return ++__first;
4122     case 'v':
4123         if (__str)
4124             *__str = _CharT(0xB);
4125         else
4126             __push_char(_CharT(0xB));
4127         return ++__first;
4128     }
4129     if ('0' <= *__first && *__first <= '7')
4130     {
4131         unsigned __val = *__first - '0';
4132         if (++__first != __last && ('0' <= *__first && *__first <= '7'))
4133         {
4134             __val = 8 * __val + *__first - '0';
4135             if (++__first != __last && ('0' <= *__first && *__first <= '7'))
4136                 __val = 8 * __val + *__first++ - '0';
4137         }
4138         if (__str)
4139             *__str = _CharT(__val);
4140         else
4141             __push_char(_CharT(__val));
4142     }
4143     else
4144         __throw_regex_error<regex_constants::error_escape>();
4145     return __first;
4146 }
4147
4148 template <class _CharT, class _Traits>
4149 template <class _ForwardIterator>
4150 _ForwardIterator
4151 basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
4152                                     _ForwardIterator __last,
4153                                     __bracket_expression<_CharT, _Traits>* __ml)
4154 {
4155     // Found [=
4156     //   This means =] must exist
4157     value_type __equal_close[2] = {'=', ']'};
4158     _ForwardIterator __temp = _VSTD::search(__first, __last, __equal_close,
4159                                                             __equal_close+2);
4160     if (__temp == __last)
4161         __throw_regex_error<regex_constants::error_brack>();
4162     // [__first, __temp) contains all text in [= ... =]
4163     string_type __collate_name =
4164         __traits_.lookup_collatename(__first, __temp);
4165     if (__collate_name.empty())
4166         __throw_regex_error<regex_constants::error_collate>();
4167     string_type __equiv_name =
4168         __traits_.transform_primary(__collate_name.begin(),
4169                                     __collate_name.end());
4170     if (!__equiv_name.empty())
4171         __ml->__add_equivalence(__equiv_name);
4172     else
4173     {
4174         switch (__collate_name.size())
4175         {
4176         case 1:
4177             __ml->__add_char(__collate_name[0]);
4178             break;
4179         case 2:
4180             __ml->__add_digraph(__collate_name[0], __collate_name[1]);
4181             break;
4182         default:
4183             __throw_regex_error<regex_constants::error_collate>();
4184         }
4185     }
4186     __first = _VSTD::next(__temp, 2);
4187     return __first;
4188 }
4189
4190 template <class _CharT, class _Traits>
4191 template <class _ForwardIterator>
4192 _ForwardIterator
4193 basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
4194                                     _ForwardIterator __last,
4195                                     __bracket_expression<_CharT, _Traits>* __ml)
4196 {
4197     // Found [:
4198     //   This means :] must exist
4199     value_type __colon_close[2] = {':', ']'};
4200     _ForwardIterator __temp = _VSTD::search(__first, __last, __colon_close,
4201                                                             __colon_close+2);
4202     if (__temp == __last)
4203         __throw_regex_error<regex_constants::error_brack>();
4204     // [__first, __temp) contains all text in [: ... :]
4205     typedef typename _Traits::char_class_type char_class_type;
4206     char_class_type __class_type =
4207         __traits_.lookup_classname(__first, __temp, __flags_ & icase);
4208     if (__class_type == 0)
4209         __throw_regex_error<regex_constants::error_ctype>();
4210     __ml->__add_class(__class_type);
4211     __first = _VSTD::next(__temp, 2);
4212     return __first;
4213 }
4214
4215 template <class _CharT, class _Traits>
4216 template <class _ForwardIterator>
4217 _ForwardIterator
4218 basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
4219                                                 _ForwardIterator __last,
4220                                                 basic_string<_CharT>& __col_sym)
4221 {
4222     // Found [.
4223     //   This means .] must exist
4224     value_type __dot_close[2] = {'.', ']'};
4225     _ForwardIterator __temp = _VSTD::search(__first, __last, __dot_close,
4226                                                             __dot_close+2);
4227     if (__temp == __last)
4228         __throw_regex_error<regex_constants::error_brack>();
4229     // [__first, __temp) contains all text in [. ... .]
4230     __col_sym = __traits_.lookup_collatename(__first, __temp);
4231     switch (__col_sym.size())
4232     {
4233     case 1:
4234     case 2:
4235         break;
4236     default:
4237         __throw_regex_error<regex_constants::error_collate>();
4238     }
4239     __first = _VSTD::next(__temp, 2);
4240     return __first;
4241 }
4242
4243 template <class _CharT, class _Traits>
4244 template <class _ForwardIterator>
4245 _ForwardIterator
4246 basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
4247                                                 _ForwardIterator __last,
4248                                                 int& __c)
4249 {
4250     if (__first != __last )
4251     {
4252         int __val = __traits_.value(*__first, 10);
4253         if ( __val != -1 )
4254         {
4255             __c = __val;
4256             for (++__first;
4257                  __first != __last && ( __val = __traits_.value(*__first, 10)) != -1;
4258                  ++__first)
4259             {
4260                 if (__c >= numeric_limits<int>::max() / 10)
4261                     __throw_regex_error<regex_constants::error_badbrace>();
4262                 __c *= 10;
4263                 __c += __val;
4264             }
4265         }
4266     }
4267     return __first;
4268 }
4269
4270 template <class _CharT, class _Traits>
4271 template <class _ForwardIterator>
4272 _ForwardIterator
4273 basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first,
4274                                                _ForwardIterator __last)
4275 {
4276     __owns_one_state<_CharT>* __sa = __end_;
4277     _ForwardIterator __temp = __parse_alternative(__first, __last);
4278     if (__temp == __first)
4279         __push_empty();
4280     __first = __temp;
4281     while (__first != __last && *__first == '|')
4282     {
4283         __owns_one_state<_CharT>* __sb = __end_;
4284         __temp = __parse_alternative(++__first, __last);
4285         if (__temp == __first)
4286             __push_empty();
4287         __push_alternation(__sa, __sb);
4288         __first = __temp;
4289     }
4290     return __first;
4291 }
4292
4293 template <class _CharT, class _Traits>
4294 template <class _ForwardIterator>
4295 _ForwardIterator
4296 basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first,
4297                                                   _ForwardIterator __last)
4298 {
4299     while (true)
4300     {
4301         _ForwardIterator __temp = __parse_term(__first, __last);
4302         if (__temp == __first)
4303             break;
4304         __first = __temp;
4305     }
4306     return __first;
4307 }
4308
4309 template <class _CharT, class _Traits>
4310 template <class _ForwardIterator>
4311 _ForwardIterator
4312 basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first,
4313                                            _ForwardIterator __last)
4314 {
4315     _ForwardIterator __temp = __parse_assertion(__first, __last);
4316     if (__temp == __first)
4317     {
4318         __owns_one_state<_CharT>* __e = __end_;
4319         unsigned __mexp_begin = __marked_count_;
4320         __temp = __parse_atom(__first, __last);
4321         if (__temp != __first)
4322             __first = __parse_ERE_dupl_symbol(__temp, __last, __e,
4323                                               __mexp_begin+1, __marked_count_+1);
4324     }
4325     else
4326         __first = __temp;
4327     return __first;
4328 }
4329
4330 template <class _CharT, class _Traits>
4331 template <class _ForwardIterator>
4332 _ForwardIterator
4333 basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first,
4334                                                 _ForwardIterator __last)
4335 {
4336     if (__first != __last)
4337     {
4338         switch (*__first)
4339         {
4340         case '^':
4341             __push_l_anchor();
4342             ++__first;
4343             break;
4344         case '$':
4345             __push_r_anchor();
4346             ++__first;
4347             break;
4348         case '\\':
4349             {
4350                 _ForwardIterator __temp = _VSTD::next(__first);
4351                 if (__temp != __last)
4352                 {
4353                     if (*__temp == 'b')
4354                     {
4355                         __push_word_boundary(false);
4356                         __first = ++__temp;
4357                     }
4358                     else if (*__temp == 'B')
4359                     {
4360                         __push_word_boundary(true);
4361                         __first = ++__temp;
4362                     }
4363                 }
4364             }
4365             break;
4366         case '(':
4367             {
4368                 _ForwardIterator __temp = _VSTD::next(__first);
4369                 if (__temp != __last && *__temp == '?')
4370                 {
4371                     if (++__temp != __last)
4372                     {
4373                         switch (*__temp)
4374                         {
4375                         case '=':
4376                             {
4377                                 basic_regex __exp;
4378                                 __exp.__flags_ = __flags_;
4379                                 __temp = __exp.__parse(++__temp, __last);
4380                                 unsigned __mexp = __exp.__marked_count_;
4381                                 __push_lookahead(_VSTD::move(__exp), false, __marked_count_);
4382                                 __marked_count_ += __mexp;
4383                                 if (__temp == __last || *__temp != ')')
4384                                     __throw_regex_error<regex_constants::error_paren>();
4385                                 __first = ++__temp;
4386                             }
4387                             break;
4388                         case '!':
4389                             {
4390                                 basic_regex __exp;
4391                                 __exp.__flags_ = __flags_;
4392                                 __temp = __exp.__parse(++__temp, __last);
4393                                 unsigned __mexp = __exp.__marked_count_;
4394                                 __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
4395                                 __marked_count_ += __mexp;
4396                                 if (__temp == __last || *__temp != ')')
4397                                     __throw_regex_error<regex_constants::error_paren>();
4398                                 __first = ++__temp;
4399                             }
4400                             break;
4401                         }
4402                     }
4403                 }
4404             }
4405             break;
4406         }
4407     }
4408     return __first;
4409 }
4410
4411 template <class _CharT, class _Traits>
4412 template <class _ForwardIterator>
4413 _ForwardIterator
4414 basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first,
4415                                            _ForwardIterator __last)
4416 {
4417     if (__first != __last)
4418     {
4419         switch (*__first)
4420         {
4421         case '.':
4422             __push_match_any_but_newline();
4423             ++__first;
4424             break;
4425         case '\\':
4426             __first = __parse_atom_escape(__first, __last);
4427             break;
4428         case '[':
4429             __first = __parse_bracket_expression(__first, __last);
4430             break;
4431         case '(':
4432             {
4433                 ++__first;
4434                 if (__first == __last)
4435                     __throw_regex_error<regex_constants::error_paren>();
4436                 _ForwardIterator __temp = _VSTD::next(__first);
4437                 if (__temp != __last && *__first == '?' && *__temp == ':')
4438                 {
4439                     ++__open_count_;
4440                     __first = __parse_ecma_exp(++__temp, __last);
4441                     if (__first == __last || *__first != ')')
4442                         __throw_regex_error<regex_constants::error_paren>();
4443                     --__open_count_;
4444                     ++__first;
4445                 }
4446                 else
4447                 {
4448                     __push_begin_marked_subexpression();
4449                     unsigned __temp_count = __marked_count_;
4450                     ++__open_count_;
4451                     __first = __parse_ecma_exp(__first, __last);
4452                     if (__first == __last || *__first != ')')
4453                         __throw_regex_error<regex_constants::error_paren>();
4454                     __push_end_marked_subexpression(__temp_count);
4455                     --__open_count_;
4456                     ++__first;
4457                 }
4458             }
4459             break;
4460         case '*':
4461         case '+':
4462         case '?':
4463         case '{':
4464             __throw_regex_error<regex_constants::error_badrepeat>();
4465             break;
4466         default:
4467             __first = __parse_pattern_character(__first, __last);
4468             break;
4469         }
4470     }
4471     return __first;
4472 }
4473
4474 template <class _CharT, class _Traits>
4475 template <class _ForwardIterator>
4476 _ForwardIterator
4477 basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first,
4478                                                   _ForwardIterator __last)
4479 {
4480     if (__first != __last && *__first == '\\')
4481     {
4482         _ForwardIterator __t1 = _VSTD::next(__first);
4483         if (__t1 == __last)
4484             __throw_regex_error<regex_constants::error_escape>();
4485
4486         _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
4487         if (__t2 != __t1)
4488             __first = __t2;
4489         else
4490         {
4491             __t2 = __parse_character_class_escape(__t1, __last);
4492             if (__t2 != __t1)
4493                 __first = __t2;
4494             else
4495             {
4496                 __t2 = __parse_character_escape(__t1, __last);
4497                 if (__t2 != __t1)
4498                     __first = __t2;
4499             }
4500         }
4501     }
4502     return __first;
4503 }
4504
4505 template <class _CharT, class _Traits>
4506 template <class _ForwardIterator>
4507 _ForwardIterator
4508 basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first,
4509                                                      _ForwardIterator __last)
4510 {
4511     if (__first != __last)
4512     {
4513         if (*__first == '0')
4514         {
4515             __push_char(_CharT());
4516             ++__first;
4517         }
4518         else if ('1' <= *__first && *__first <= '9')
4519         {
4520             unsigned __v = *__first - '0';
4521             for (++__first;
4522                     __first != __last && '0' <= *__first && *__first <= '9'; ++__first)
4523                 {
4524                 if (__v >= numeric_limits<unsigned>::max() / 10)
4525                     __throw_regex_error<regex_constants::error_backref>();
4526                 __v = 10 * __v + *__first - '0';
4527                 }
4528             if (__v == 0 || __v > mark_count())
4529                 __throw_regex_error<regex_constants::error_backref>();
4530             __push_back_ref(__v);
4531         }
4532     }
4533     return __first;
4534 }
4535
4536 template <class _CharT, class _Traits>
4537 template <class _ForwardIterator>
4538 _ForwardIterator
4539 basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first,
4540                                                              _ForwardIterator __last)
4541 {
4542     if (__first != __last)
4543     {
4544         __bracket_expression<_CharT, _Traits>* __ml;
4545         switch (*__first)
4546         {
4547         case 'd':
4548             __ml = __start_matching_list(false);
4549             __ml->__add_class(ctype_base::digit);
4550             ++__first;
4551             break;
4552         case 'D':
4553             __ml = __start_matching_list(true);
4554             __ml->__add_class(ctype_base::digit);
4555             ++__first;
4556             break;
4557         case 's':
4558             __ml = __start_matching_list(false);
4559             __ml->__add_class(ctype_base::space);
4560             ++__first;
4561             break;
4562         case 'S':
4563             __ml = __start_matching_list(true);
4564             __ml->__add_class(ctype_base::space);
4565             ++__first;
4566             break;
4567         case 'w':
4568             __ml = __start_matching_list(false);
4569             __ml->__add_class(ctype_base::alnum);
4570             __ml->__add_char('_');
4571             ++__first;
4572             break;
4573         case 'W':
4574             __ml = __start_matching_list(true);
4575             __ml->__add_class(ctype_base::alnum);
4576             __ml->__add_char('_');
4577             ++__first;
4578             break;
4579         }
4580     }
4581     return __first;
4582 }
4583
4584 template <class _CharT, class _Traits>
4585 template <class _ForwardIterator>
4586 _ForwardIterator
4587 basic_regex<_CharT, _Traits>::__parse_character_escape(_ForwardIterator __first,
4588                                                     _ForwardIterator __last,
4589                                                     basic_string<_CharT>* __str)
4590 {
4591     if (__first != __last)
4592     {
4593         _ForwardIterator __t;
4594         unsigned __sum = 0;
4595         int __hd;
4596         switch (*__first)
4597         {
4598         case 'f':
4599             if (__str)
4600                 *__str = _CharT(0xC);
4601             else
4602                 __push_char(_CharT(0xC));
4603             ++__first;
4604             break;
4605         case 'n':
4606             if (__str)
4607                 *__str = _CharT(0xA);
4608             else
4609                 __push_char(_CharT(0xA));
4610             ++__first;
4611             break;
4612         case 'r':
4613             if (__str)
4614                 *__str = _CharT(0xD);
4615             else
4616                 __push_char(_CharT(0xD));
4617             ++__first;
4618             break;
4619         case 't':
4620             if (__str)
4621                 *__str = _CharT(0x9);
4622             else
4623                 __push_char(_CharT(0x9));
4624             ++__first;
4625             break;
4626         case 'v':
4627             if (__str)
4628                 *__str = _CharT(0xB);
4629             else
4630                 __push_char(_CharT(0xB));
4631             ++__first;
4632             break;
4633         case 'c':
4634             if ((__t = _VSTD::next(__first)) != __last)
4635             {
4636                 if (('A' <= *__t && *__t <= 'Z') ||
4637                     ('a' <= *__t && *__t <= 'z'))
4638                 {
4639                     if (__str)
4640                         *__str = _CharT(*__t % 32);
4641                     else
4642                         __push_char(_CharT(*__t % 32));
4643                     __first = ++__t;
4644                 }
4645                 else
4646                     __throw_regex_error<regex_constants::error_escape>();
4647             }
4648             else
4649                 __throw_regex_error<regex_constants::error_escape>();
4650             break;
4651         case 'u':
4652             ++__first;
4653             if (__first == __last)
4654                 __throw_regex_error<regex_constants::error_escape>();
4655             __hd = __traits_.value(*__first, 16);
4656             if (__hd == -1)
4657                 __throw_regex_error<regex_constants::error_escape>();
4658             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4659             ++__first;
4660             if (__first == __last)
4661                 __throw_regex_error<regex_constants::error_escape>();
4662             __hd = __traits_.value(*__first, 16);
4663             if (__hd == -1)
4664                 __throw_regex_error<regex_constants::error_escape>();
4665             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4666             // fallthrough
4667         case 'x':
4668             ++__first;
4669             if (__first == __last)
4670                 __throw_regex_error<regex_constants::error_escape>();
4671             __hd = __traits_.value(*__first, 16);
4672             if (__hd == -1)
4673                 __throw_regex_error<regex_constants::error_escape>();
4674             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4675             ++__first;
4676             if (__first == __last)
4677                 __throw_regex_error<regex_constants::error_escape>();
4678             __hd = __traits_.value(*__first, 16);
4679             if (__hd == -1)
4680                 __throw_regex_error<regex_constants::error_escape>();
4681             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4682             if (__str)
4683                 *__str = _CharT(__sum);
4684             else
4685                 __push_char(_CharT(__sum));
4686             ++__first;
4687             break;
4688         case '0':
4689             if (__str)
4690                 *__str = _CharT(0);
4691             else
4692                 __push_char(_CharT(0));
4693             ++__first;
4694             break;
4695         default:
4696             if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum))
4697             {
4698                 if (__str)
4699                     *__str = *__first;
4700                 else
4701                     __push_char(*__first);
4702                 ++__first;
4703             }
4704             else
4705                 __throw_regex_error<regex_constants::error_escape>();
4706             break;
4707         }
4708     }
4709     return __first;
4710 }
4711
4712 template <class _CharT, class _Traits>
4713 template <class _ForwardIterator>
4714 _ForwardIterator
4715 basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first,
4716                                                         _ForwardIterator __last)
4717 {
4718     if (__first != __last)
4719     {
4720         switch (*__first)
4721         {
4722         case '^':
4723         case '$':
4724         case '\\':
4725         case '.':
4726         case '*':
4727         case '+':
4728         case '?':
4729         case '(':
4730         case ')':
4731         case '[':
4732         case ']':
4733         case '{':
4734         case '}':
4735         case '|':
4736             break;
4737         default:
4738             __push_char(*__first);
4739             ++__first;
4740             break;
4741         }
4742     }
4743     return __first;
4744 }
4745
4746 template <class _CharT, class _Traits>
4747 template <class _ForwardIterator>
4748 _ForwardIterator
4749 basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first,
4750                                            _ForwardIterator __last)
4751 {
4752     __owns_one_state<_CharT>* __sa = __end_;
4753     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4754     if (__t1 != __first)
4755         __parse_basic_reg_exp(__first, __t1);
4756     else
4757         __push_empty();
4758     __first = __t1;
4759     if (__first != __last)
4760         ++__first;
4761     while (__first != __last)
4762     {
4763         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4764         __owns_one_state<_CharT>* __sb = __end_;
4765         if (__t1 != __first)
4766             __parse_basic_reg_exp(__first, __t1);
4767         else
4768             __push_empty();
4769         __push_alternation(__sa, __sb);
4770         __first = __t1;
4771         if (__first != __last)
4772             ++__first;
4773     }
4774     return __first;
4775 }
4776
4777 template <class _CharT, class _Traits>
4778 template <class _ForwardIterator>
4779 _ForwardIterator
4780 basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first,
4781                                             _ForwardIterator __last)
4782 {
4783     __owns_one_state<_CharT>* __sa = __end_;
4784     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4785     if (__t1 != __first)
4786         __parse_extended_reg_exp(__first, __t1);
4787     else
4788         __push_empty();
4789     __first = __t1;
4790     if (__first != __last)
4791         ++__first;
4792     while (__first != __last)
4793     {
4794         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4795         __owns_one_state<_CharT>* __sb = __end_;
4796         if (__t1 != __first)
4797             __parse_extended_reg_exp(__first, __t1);
4798         else
4799             __push_empty();
4800         __push_alternation(__sa, __sb);
4801         __first = __t1;
4802         if (__first != __last)
4803             ++__first;
4804     }
4805     return __first;
4806 }
4807
4808 template <class _CharT, class _Traits>
4809 bool
4810 basic_regex<_CharT, _Traits>::__test_back_ref(_CharT __c)
4811 {
4812     unsigned __val = __traits_.value(__c, 10);
4813     if (__val >= 1 && __val <= 9)
4814     {
4815         if (__val > mark_count())
4816             __throw_regex_error<regex_constants::error_backref>();
4817         __push_back_ref(__val);
4818         return true;
4819     }
4820
4821     return false;
4822 }
4823
4824 template <class _CharT, class _Traits>
4825 void
4826 basic_regex<_CharT, _Traits>::__push_loop(size_t __min, size_t __max,
4827         __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end,
4828         bool __greedy)
4829 {
4830     unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
4831     __end_->first() = nullptr;
4832     unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,
4833                 __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
4834                 __min, __max));
4835     __s->first() = nullptr;
4836     __e1.release();
4837     __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
4838     __end_ = __e2->second();
4839     __s->first() = __e2.release();
4840     ++__loop_count_;
4841 }
4842
4843 template <class _CharT, class _Traits>
4844 void
4845 basic_regex<_CharT, _Traits>::__push_char(value_type __c)
4846 {
4847     if (flags() & icase)
4848         __end_->first() = new __match_char_icase<_CharT, _Traits>
4849                                               (__traits_, __c, __end_->first());
4850     else if (flags() & collate)
4851         __end_->first() = new __match_char_collate<_CharT, _Traits>
4852                                               (__traits_, __c, __end_->first());
4853     else
4854         __end_->first() = new __match_char<_CharT>(__c, __end_->first());
4855     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4856 }
4857
4858 template <class _CharT, class _Traits>
4859 void
4860 basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
4861 {
4862     if (!(__flags_ & nosubs))
4863     {
4864         __end_->first() =
4865                 new __begin_marked_subexpression<_CharT>(++__marked_count_,
4866                                                          __end_->first());
4867         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4868     }
4869 }
4870
4871 template <class _CharT, class _Traits>
4872 void
4873 basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
4874 {
4875     if (!(__flags_ & nosubs))
4876     {
4877         __end_->first() =
4878                 new __end_marked_subexpression<_CharT>(__sub, __end_->first());
4879         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4880     }
4881 }
4882
4883 template <class _CharT, class _Traits>
4884 void
4885 basic_regex<_CharT, _Traits>::__push_l_anchor()
4886 {
4887     __end_->first() = new __l_anchor_multiline<_CharT>(__use_multiline(), __end_->first());
4888     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4889 }
4890
4891 template <class _CharT, class _Traits>
4892 void
4893 basic_regex<_CharT, _Traits>::__push_r_anchor()
4894 {
4895     __end_->first() = new __r_anchor_multiline<_CharT>(__use_multiline(), __end_->first());
4896     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4897 }
4898
4899 template <class _CharT, class _Traits>
4900 void
4901 basic_regex<_CharT, _Traits>::__push_match_any()
4902 {
4903     __end_->first() = new __match_any<_CharT>(__end_->first());
4904     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4905 }
4906
4907 template <class _CharT, class _Traits>
4908 void
4909 basic_regex<_CharT, _Traits>::__push_match_any_but_newline()
4910 {
4911     __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
4912     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4913 }
4914
4915 template <class _CharT, class _Traits>
4916 void
4917 basic_regex<_CharT, _Traits>::__push_empty()
4918 {
4919     __end_->first() = new __empty_state<_CharT>(__end_->first());
4920     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4921 }
4922
4923 template <class _CharT, class _Traits>
4924 void
4925 basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert)
4926 {
4927     __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert,
4928                                                            __end_->first());
4929     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4930 }
4931
4932 template <class _CharT, class _Traits>
4933 void
4934 basic_regex<_CharT, _Traits>::__push_back_ref(int __i)
4935 {
4936     if (flags() & icase)
4937         __end_->first() = new __back_ref_icase<_CharT, _Traits>
4938                                               (__traits_, __i, __end_->first());
4939     else if (flags() & collate)
4940         __end_->first() = new __back_ref_collate<_CharT, _Traits>
4941                                               (__traits_, __i, __end_->first());
4942     else
4943         __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
4944     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4945 }
4946
4947 template <class _CharT, class _Traits>
4948 void
4949 basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa,
4950                                                  __owns_one_state<_CharT>* __ea)
4951 {
4952     __sa->first() = new __alternate<_CharT>(
4953                          static_cast<__owns_one_state<_CharT>*>(__sa->first()),
4954                          static_cast<__owns_one_state<_CharT>*>(__ea->first()));
4955     __ea->first() = nullptr;
4956     __ea->first() = new __empty_state<_CharT>(__end_->first());
4957     __end_->first() = nullptr;
4958     __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
4959     __end_ = static_cast<__owns_one_state<_CharT>*>(__ea->first());
4960 }
4961
4962 template <class _CharT, class _Traits>
4963 __bracket_expression<_CharT, _Traits>*
4964 basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate)
4965 {
4966     __bracket_expression<_CharT, _Traits>* __r =
4967         new __bracket_expression<_CharT, _Traits>(__traits_, __end_->first(),
4968                                                   __negate, __flags_ & icase,
4969                                                   __flags_ & collate);
4970     __end_->first() = __r;
4971     __end_ = __r;
4972     return __r;
4973 }
4974
4975 template <class _CharT, class _Traits>
4976 void
4977 basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp,
4978                                                bool __invert,
4979                                                unsigned __mexp)
4980 {
4981     __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
4982                                                            __end_->first(), __mexp);
4983     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4984 }
4985
4986 // sub_match
4987
4988 typedef sub_match<const char*>             csub_match;
4989 typedef sub_match<string::const_iterator>  ssub_match;
4990 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
4991 typedef sub_match<const wchar_t*>          wcsub_match;
4992 typedef sub_match<wstring::const_iterator> wssub_match;
4993 #endif
4994
4995 template <class _BidirectionalIterator>
4996 class
4997     _LIBCPP_TEMPLATE_VIS
4998     _LIBCPP_PREFERRED_NAME(csub_match)
4999     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcsub_match))
5000     _LIBCPP_PREFERRED_NAME(ssub_match)
5001     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wssub_match))
5002     sub_match
5003     : public pair<_BidirectionalIterator, _BidirectionalIterator>
5004 {
5005 public:
5006     typedef _BidirectionalIterator                              iterator;
5007     typedef typename iterator_traits<iterator>::value_type      value_type;
5008     typedef typename iterator_traits<iterator>::difference_type difference_type;
5009     typedef basic_string<value_type>                            string_type;
5010
5011     bool matched;
5012
5013     _LIBCPP_INLINE_VISIBILITY
5014     _LIBCPP_CONSTEXPR sub_match() : matched() {}
5015
5016     _LIBCPP_INLINE_VISIBILITY
5017     difference_type length() const
5018         {return matched ? _VSTD::distance(this->first, this->second) : 0;}
5019     _LIBCPP_INLINE_VISIBILITY
5020     string_type str() const
5021         {return matched ? string_type(this->first, this->second) : string_type();}
5022     _LIBCPP_INLINE_VISIBILITY
5023     operator string_type() const
5024         {return str();}
5025
5026     _LIBCPP_INLINE_VISIBILITY
5027     int compare(const sub_match& __s) const
5028         {return str().compare(__s.str());}
5029     _LIBCPP_INLINE_VISIBILITY
5030     int compare(const string_type& __s) const
5031         {return str().compare(__s);}
5032     _LIBCPP_INLINE_VISIBILITY
5033     int compare(const value_type* __s) const
5034         {return str().compare(__s);}
5035
5036     _LIBCPP_HIDE_FROM_ABI
5037     void swap(sub_match& __s)
5038 #ifndef _LIBCPP_CXX03_LANG
5039     _NOEXCEPT(__is_nothrow_swappable<_BidirectionalIterator>::value)
5040 #endif // _LIBCPP_CXX03_LANG
5041     {
5042         this->pair<_BidirectionalIterator, _BidirectionalIterator>::swap(__s);
5043         std::swap(matched, __s.matched);
5044     }
5045 };
5046
5047 template <class _BiIter>
5048 inline _LIBCPP_INLINE_VISIBILITY
5049 bool
5050 operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5051 {
5052     return __x.compare(__y) == 0;
5053 }
5054
5055 #if _LIBCPP_STD_VER >= 20
5056 template<class _BiIter>
5057 using __sub_match_cat = compare_three_way_result_t<basic_string<typename iterator_traits<_BiIter>::value_type>>;
5058
5059 template <class _BiIter>
5060 _LIBCPP_HIDE_FROM_ABI auto operator<=>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y) {
5061     return static_cast<__sub_match_cat<_BiIter>>(__x.compare(__y) <=> 0);
5062 }
5063 #else // _LIBCPP_STD_VER >= 20
5064 template <class _BiIter>
5065 inline _LIBCPP_INLINE_VISIBILITY
5066 bool
5067 operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5068 {
5069     return !(__x == __y);
5070 }
5071
5072 template <class _BiIter>
5073 inline _LIBCPP_INLINE_VISIBILITY
5074 bool
5075 operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5076 {
5077     return __x.compare(__y) < 0;
5078 }
5079
5080 template <class _BiIter>
5081 inline _LIBCPP_INLINE_VISIBILITY
5082 bool
5083 operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5084 {
5085     return !(__y < __x);
5086 }
5087
5088 template <class _BiIter>
5089 inline _LIBCPP_INLINE_VISIBILITY
5090 bool
5091 operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5092 {
5093     return !(__x < __y);
5094 }
5095
5096 template <class _BiIter>
5097 inline _LIBCPP_INLINE_VISIBILITY
5098 bool
5099 operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
5100 {
5101     return __y < __x;
5102 }
5103
5104 template <class _BiIter, class _ST, class _SA>
5105 inline _LIBCPP_INLINE_VISIBILITY
5106 bool
5107 operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5108            const sub_match<_BiIter>& __y)
5109 {
5110     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;
5111 }
5112
5113 template <class _BiIter, class _ST, class _SA>
5114 inline _LIBCPP_INLINE_VISIBILITY
5115 bool
5116 operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5117            const sub_match<_BiIter>& __y)
5118 {
5119     return !(__x == __y);
5120 }
5121
5122 template <class _BiIter, class _ST, class _SA>
5123 inline _LIBCPP_INLINE_VISIBILITY
5124 bool
5125 operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5126           const sub_match<_BiIter>& __y)
5127 {
5128     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;
5129 }
5130
5131 template <class _BiIter, class _ST, class _SA>
5132 inline _LIBCPP_INLINE_VISIBILITY
5133 bool
5134 operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5135           const sub_match<_BiIter>& __y)
5136 {
5137     return __y < __x;
5138 }
5139
5140 template <class _BiIter, class _ST, class _SA>
5141 inline _LIBCPP_INLINE_VISIBILITY
5142 bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5143                 const sub_match<_BiIter>& __y)
5144 {
5145     return !(__x < __y);
5146 }
5147
5148 template <class _BiIter, class _ST, class _SA>
5149 inline _LIBCPP_INLINE_VISIBILITY
5150 bool
5151 operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
5152            const sub_match<_BiIter>& __y)
5153 {
5154     return !(__y < __x);
5155 }
5156 #endif // _LIBCPP_STD_VER >= 20
5157
5158 template <class _BiIter, class _ST, class _SA>
5159 inline _LIBCPP_INLINE_VISIBILITY
5160 bool
5161 operator==(const sub_match<_BiIter>& __x,
5162            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5163 {
5164     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;
5165 }
5166
5167 #if _LIBCPP_STD_VER >= 20
5168 template <class _BiIter, class _ST, class _SA>
5169 _LIBCPP_HIDE_FROM_ABI auto operator<=>(
5170     const sub_match<_BiIter>& __x, const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y) {
5171     return static_cast<__sub_match_cat<_BiIter>>(
5172         __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) <=> 0);
5173 }
5174 #else // _LIBCPP_STD_VER >= 20
5175 template <class _BiIter, class _ST, class _SA>
5176 inline _LIBCPP_INLINE_VISIBILITY
5177 bool
5178 operator!=(const sub_match<_BiIter>& __x,
5179            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5180 {
5181     return !(__x == __y);
5182 }
5183
5184 template <class _BiIter, class _ST, class _SA>
5185 inline _LIBCPP_INLINE_VISIBILITY
5186 bool
5187 operator<(const sub_match<_BiIter>& __x,
5188           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5189 {
5190     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;
5191 }
5192
5193 template <class _BiIter, class _ST, class _SA>
5194 inline _LIBCPP_INLINE_VISIBILITY
5195 bool operator>(const sub_match<_BiIter>& __x,
5196                const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5197 {
5198     return __y < __x;
5199 }
5200
5201 template <class _BiIter, class _ST, class _SA>
5202 inline _LIBCPP_INLINE_VISIBILITY
5203 bool
5204 operator>=(const sub_match<_BiIter>& __x,
5205            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5206 {
5207     return !(__x < __y);
5208 }
5209
5210 template <class _BiIter, class _ST, class _SA>
5211 inline _LIBCPP_INLINE_VISIBILITY
5212 bool
5213 operator<=(const sub_match<_BiIter>& __x,
5214            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
5215 {
5216     return !(__y < __x);
5217 }
5218
5219 template <class _BiIter>
5220 inline _LIBCPP_INLINE_VISIBILITY
5221 bool
5222 operator==(typename iterator_traits<_BiIter>::value_type const* __x,
5223            const sub_match<_BiIter>& __y)
5224 {
5225     return __y.compare(__x) == 0;
5226 }
5227
5228 template <class _BiIter>
5229 inline _LIBCPP_INLINE_VISIBILITY
5230 bool
5231 operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
5232            const sub_match<_BiIter>& __y)
5233 {
5234     return !(__x == __y);
5235 }
5236
5237 template <class _BiIter>
5238 inline _LIBCPP_INLINE_VISIBILITY
5239 bool
5240 operator<(typename iterator_traits<_BiIter>::value_type const* __x,
5241           const sub_match<_BiIter>& __y)
5242 {
5243     return __y.compare(__x) > 0;
5244 }
5245
5246 template <class _BiIter>
5247 inline _LIBCPP_INLINE_VISIBILITY
5248 bool
5249 operator>(typename iterator_traits<_BiIter>::value_type const* __x,
5250           const sub_match<_BiIter>& __y)
5251 {
5252     return __y < __x;
5253 }
5254
5255 template <class _BiIter>
5256 inline _LIBCPP_INLINE_VISIBILITY
5257 bool
5258 operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
5259            const sub_match<_BiIter>& __y)
5260 {
5261     return !(__x < __y);
5262 }
5263
5264 template <class _BiIter>
5265 inline _LIBCPP_INLINE_VISIBILITY
5266 bool
5267 operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
5268            const sub_match<_BiIter>& __y)
5269 {
5270     return !(__y < __x);
5271 }
5272 #endif // _LIBCPP_STD_VER >= 20
5273
5274 template <class _BiIter>
5275 inline _LIBCPP_INLINE_VISIBILITY
5276 bool
5277 operator==(const sub_match<_BiIter>& __x,
5278            typename iterator_traits<_BiIter>::value_type const* __y)
5279 {
5280     return __x.compare(__y) == 0;
5281 }
5282
5283 #if _LIBCPP_STD_VER >= 20
5284 template <class _BiIter>
5285 _LIBCPP_HIDE_FROM_ABI auto
5286 operator<=>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const* __y) {
5287     return static_cast<__sub_match_cat<_BiIter>>(__x.compare(__y) <=> 0);
5288 }
5289 #else // _LIBCPP_STD_VER >= 20
5290 template <class _BiIter>
5291 inline _LIBCPP_INLINE_VISIBILITY
5292 bool
5293 operator!=(const sub_match<_BiIter>& __x,
5294            typename iterator_traits<_BiIter>::value_type const* __y)
5295 {
5296     return !(__x == __y);
5297 }
5298
5299 template <class _BiIter>
5300 inline _LIBCPP_INLINE_VISIBILITY
5301 bool
5302 operator<(const sub_match<_BiIter>& __x,
5303           typename iterator_traits<_BiIter>::value_type const* __y)
5304 {
5305     return __x.compare(__y) < 0;
5306 }
5307
5308 template <class _BiIter>
5309 inline _LIBCPP_INLINE_VISIBILITY
5310 bool
5311 operator>(const sub_match<_BiIter>& __x,
5312           typename iterator_traits<_BiIter>::value_type const* __y)
5313 {
5314     return __y < __x;
5315 }
5316
5317 template <class _BiIter>
5318 inline _LIBCPP_INLINE_VISIBILITY
5319 bool
5320 operator>=(const sub_match<_BiIter>& __x,
5321            typename iterator_traits<_BiIter>::value_type const* __y)
5322 {
5323     return !(__x < __y);
5324 }
5325
5326 template <class _BiIter>
5327 inline _LIBCPP_INLINE_VISIBILITY
5328 bool
5329 operator<=(const sub_match<_BiIter>& __x,
5330            typename iterator_traits<_BiIter>::value_type const* __y)
5331 {
5332     return !(__y < __x);
5333 }
5334
5335 template <class _BiIter>
5336 inline _LIBCPP_INLINE_VISIBILITY
5337 bool
5338 operator==(typename iterator_traits<_BiIter>::value_type const& __x,
5339            const sub_match<_BiIter>& __y)
5340 {
5341     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5342     return __y.compare(string_type(1, __x)) == 0;
5343 }
5344
5345 template <class _BiIter>
5346 inline _LIBCPP_INLINE_VISIBILITY
5347 bool
5348 operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
5349            const sub_match<_BiIter>& __y)
5350 {
5351     return !(__x == __y);
5352 }
5353
5354 template <class _BiIter>
5355 inline _LIBCPP_INLINE_VISIBILITY
5356 bool
5357 operator<(typename iterator_traits<_BiIter>::value_type const& __x,
5358           const sub_match<_BiIter>& __y)
5359 {
5360     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5361     return __y.compare(string_type(1, __x)) > 0;
5362 }
5363
5364 template <class _BiIter>
5365 inline _LIBCPP_INLINE_VISIBILITY
5366 bool
5367 operator>(typename iterator_traits<_BiIter>::value_type const& __x,
5368           const sub_match<_BiIter>& __y)
5369 {
5370     return __y < __x;
5371 }
5372
5373 template <class _BiIter>
5374 inline _LIBCPP_INLINE_VISIBILITY
5375 bool
5376 operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
5377            const sub_match<_BiIter>& __y)
5378 {
5379     return !(__x < __y);
5380 }
5381
5382 template <class _BiIter>
5383 inline _LIBCPP_INLINE_VISIBILITY
5384 bool
5385 operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
5386            const sub_match<_BiIter>& __y)
5387 {
5388     return !(__y < __x);
5389 }
5390 #endif // _LIBCPP_STD_VER >= 20
5391
5392 template <class _BiIter>
5393 inline _LIBCPP_INLINE_VISIBILITY
5394 bool
5395 operator==(const sub_match<_BiIter>& __x,
5396            typename iterator_traits<_BiIter>::value_type const& __y)
5397 {
5398     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5399     return __x.compare(string_type(1, __y)) == 0;
5400 }
5401
5402 #if _LIBCPP_STD_VER >= 20
5403 template <class _BiIter>
5404 _LIBCPP_HIDE_FROM_ABI auto
5405 operator<=>(const sub_match<_BiIter>& __x, typename iterator_traits<_BiIter>::value_type const& __y) {
5406     using string_type = basic_string<typename iterator_traits<_BiIter>::value_type>;
5407     return static_cast<__sub_match_cat<_BiIter>>(__x.compare(string_type(1, __y)) <=> 0);
5408 }
5409 #else // _LIBCPP_STD_VER >= 20
5410 template <class _BiIter>
5411 inline _LIBCPP_INLINE_VISIBILITY
5412 bool
5413 operator!=(const sub_match<_BiIter>& __x,
5414            typename iterator_traits<_BiIter>::value_type const& __y)
5415 {
5416     return !(__x == __y);
5417 }
5418
5419 template <class _BiIter>
5420 inline _LIBCPP_INLINE_VISIBILITY
5421 bool
5422 operator<(const sub_match<_BiIter>& __x,
5423           typename iterator_traits<_BiIter>::value_type const& __y)
5424 {
5425     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5426     return __x.compare(string_type(1, __y)) < 0;
5427 }
5428
5429 template <class _BiIter>
5430 inline _LIBCPP_INLINE_VISIBILITY
5431 bool
5432 operator>(const sub_match<_BiIter>& __x,
5433           typename iterator_traits<_BiIter>::value_type const& __y)
5434 {
5435     return __y < __x;
5436 }
5437
5438 template <class _BiIter>
5439 inline _LIBCPP_INLINE_VISIBILITY
5440 bool
5441 operator>=(const sub_match<_BiIter>& __x,
5442            typename iterator_traits<_BiIter>::value_type const& __y)
5443 {
5444     return !(__x < __y);
5445 }
5446
5447 template <class _BiIter>
5448 inline _LIBCPP_INLINE_VISIBILITY
5449 bool
5450 operator<=(const sub_match<_BiIter>& __x,
5451            typename iterator_traits<_BiIter>::value_type const& __y)
5452 {
5453     return !(__y < __x);
5454 }
5455 #endif // _LIBCPP_STD_VER >= 20
5456
5457 template <class _CharT, class _ST, class _BiIter>
5458 inline _LIBCPP_INLINE_VISIBILITY
5459 basic_ostream<_CharT, _ST>&
5460 operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
5461 {
5462     return __os << __m.str();
5463 }
5464
5465 typedef match_results<const char*>             cmatch;
5466 typedef match_results<string::const_iterator>  smatch;
5467 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
5468 typedef match_results<const wchar_t*>          wcmatch;
5469 typedef match_results<wstring::const_iterator> wsmatch;
5470 #endif
5471
5472 template <class _BidirectionalIterator, class _Allocator>
5473 class
5474     _LIBCPP_TEMPLATE_VIS
5475     _LIBCPP_PREFERRED_NAME(cmatch)
5476     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcmatch))
5477     _LIBCPP_PREFERRED_NAME(smatch)
5478     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsmatch))
5479     match_results
5480 {
5481 public:
5482     typedef _Allocator                                        allocator_type;
5483     typedef sub_match<_BidirectionalIterator>                 value_type;
5484 private:
5485     typedef vector<value_type, allocator_type>                __container_type;
5486
5487     __container_type  __matches_;
5488     value_type __unmatched_;
5489     value_type __prefix_;
5490     value_type __suffix_;
5491     bool       __ready_;
5492 public:
5493     _BidirectionalIterator __position_start_;
5494     typedef const value_type&                                 const_reference;
5495     typedef value_type&                                       reference;
5496     typedef typename __container_type::const_iterator         const_iterator;
5497     typedef const_iterator                                    iterator;
5498     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
5499     typedef typename allocator_traits<allocator_type>::size_type size_type;
5500     typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
5501     typedef basic_string<char_type>                           string_type;
5502
5503     // construct/copy/destroy:
5504 #ifndef _LIBCPP_CXX03_LANG
5505     match_results() : match_results(allocator_type()) {}
5506     explicit match_results(const allocator_type& __a);
5507 #else
5508     explicit match_results(const allocator_type& __a = allocator_type());
5509 #endif
5510
5511 //    match_results(const match_results&) = default;
5512 //    match_results& operator=(const match_results&) = default;
5513 //    match_results(match_results&& __m) = default;
5514 //    match_results& operator=(match_results&& __m) = default;
5515 //    ~match_results() = default;
5516
5517     _LIBCPP_INLINE_VISIBILITY
5518     bool ready() const {return __ready_;}
5519
5520     // size:
5521     _LIBCPP_INLINE_VISIBILITY
5522     size_type size() const _NOEXCEPT {return __matches_.size();}
5523     _LIBCPP_INLINE_VISIBILITY
5524     size_type max_size() const _NOEXCEPT {return __matches_.max_size();}
5525     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
5526     bool empty() const _NOEXCEPT {return size() == 0;}
5527
5528     // element access:
5529     _LIBCPP_INLINE_VISIBILITY
5530     difference_type length(size_type __sub = 0) const
5531         {
5532         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::length() called when not ready");
5533         return (*this)[__sub].length();
5534         }
5535     _LIBCPP_INLINE_VISIBILITY
5536     difference_type position(size_type __sub = 0) const
5537         {
5538         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::position() called when not ready");
5539         return _VSTD::distance(__position_start_, (*this)[__sub].first);
5540         }
5541     _LIBCPP_INLINE_VISIBILITY
5542     string_type str(size_type __sub = 0) const
5543         {
5544         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::str() called when not ready");
5545         return (*this)[__sub].str();
5546         }
5547     _LIBCPP_INLINE_VISIBILITY
5548     const_reference operator[](size_type __n) const
5549         {
5550         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::operator[]() called when not ready");
5551         return __n < __matches_.size() ? __matches_[__n] : __unmatched_;
5552         }
5553
5554     _LIBCPP_INLINE_VISIBILITY
5555     const_reference prefix() const
5556         {
5557         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::prefix() called when not ready");
5558         return __prefix_;
5559         }
5560     _LIBCPP_INLINE_VISIBILITY
5561     const_reference suffix() const
5562         {
5563         _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::suffix() called when not ready");
5564         return __suffix_;
5565         }
5566
5567     _LIBCPP_INLINE_VISIBILITY
5568     const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin();}
5569     _LIBCPP_INLINE_VISIBILITY
5570     const_iterator end() const {return __matches_.end();}
5571     _LIBCPP_INLINE_VISIBILITY
5572     const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin();}
5573     _LIBCPP_INLINE_VISIBILITY
5574     const_iterator cend() const {return __matches_.end();}
5575
5576     // format:
5577     template <class _OutputIter>
5578         _OutputIter
5579         format(_OutputIter __output_iter, const char_type* __fmt_first,
5580                const char_type* __fmt_last,
5581                regex_constants::match_flag_type __flags = regex_constants::format_default) const;
5582     template <class _OutputIter, class _ST, class _SA>
5583         _LIBCPP_INLINE_VISIBILITY
5584         _OutputIter
5585         format(_OutputIter __output_iter, const basic_string<char_type, _ST, _SA>& __fmt,
5586                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5587             {return format(__output_iter, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
5588     template <class _ST, class _SA>
5589         _LIBCPP_INLINE_VISIBILITY
5590         basic_string<char_type, _ST, _SA>
5591         format(const basic_string<char_type, _ST, _SA>& __fmt,
5592                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5593         {
5594             basic_string<char_type, _ST, _SA> __r;
5595             format(std::back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
5596                    __flags);
5597             return __r;
5598         }
5599     _LIBCPP_INLINE_VISIBILITY
5600     string_type
5601         format(const char_type* __fmt,
5602                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5603         {
5604             string_type __r;
5605             format(std::back_inserter(__r), __fmt,
5606                    __fmt + char_traits<char_type>::length(__fmt), __flags);
5607             return __r;
5608         }
5609
5610     // allocator:
5611     _LIBCPP_INLINE_VISIBILITY
5612     allocator_type get_allocator() const {return __matches_.get_allocator();}
5613
5614     // swap:
5615     void swap(match_results& __m);
5616
5617     template <class _Bp, class _Ap>
5618         _LIBCPP_INLINE_VISIBILITY
5619         void __assign(_BidirectionalIterator __f, _BidirectionalIterator __l,
5620                       const match_results<_Bp, _Ap>& __m, bool __no_update_pos)
5621     {
5622         _Bp __mf = __m.prefix().first;
5623         __matches_.resize(__m.size());
5624         for (size_type __i = 0; __i < __matches_.size(); ++__i)
5625         {
5626             __matches_[__i].first = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].first));
5627             __matches_[__i].second = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].second));
5628             __matches_[__i].matched = __m[__i].matched;
5629         }
5630         __unmatched_.first   = __l;
5631         __unmatched_.second  = __l;
5632         __unmatched_.matched = false;
5633         __prefix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().first));
5634         __prefix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().second));
5635         __prefix_.matched = __m.prefix().matched;
5636         __suffix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().first));
5637         __suffix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().second));
5638         __suffix_.matched = __m.suffix().matched;
5639         if (!__no_update_pos)
5640             __position_start_ = __prefix_.first;
5641         __ready_ = __m.ready();
5642     }
5643
5644 private:
5645     void __init(unsigned __s,
5646                 _BidirectionalIterator __f, _BidirectionalIterator __l,
5647                 bool __no_update_pos = false);
5648
5649     template <class, class> friend class basic_regex;
5650
5651     template <class _Bp, class _Ap, class _Cp, class _Tp>
5652     friend
5653     bool
5654     regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
5655                 regex_constants::match_flag_type);
5656
5657     template <class _Bp, class _Ap>
5658     friend
5659     bool
5660     operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
5661
5662     template <class, class> friend class __lookahead;
5663 };
5664
5665 template <class _BidirectionalIterator, class _Allocator>
5666 match_results<_BidirectionalIterator, _Allocator>::match_results(
5667         const allocator_type& __a)
5668     : __matches_(__a),
5669       __unmatched_(),
5670       __prefix_(),
5671       __suffix_(),
5672       __ready_(false),
5673       __position_start_()
5674 {
5675 }
5676
5677 template <class _BidirectionalIterator, class _Allocator>
5678 void
5679 match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
5680                          _BidirectionalIterator __f, _BidirectionalIterator __l,
5681                          bool __no_update_pos)
5682 {
5683     __unmatched_.first   = __l;
5684     __unmatched_.second  = __l;
5685     __unmatched_.matched = false;
5686     __matches_.assign(__s, __unmatched_);
5687     __prefix_.first      = __f;
5688     __prefix_.second     = __f;
5689     __prefix_.matched    = false;
5690     __suffix_ = __unmatched_;
5691     if (!__no_update_pos)
5692         __position_start_ = __prefix_.first;
5693     __ready_ = true;
5694 }
5695
5696 template <class _BidirectionalIterator, class _Allocator>
5697 template <class _OutputIter>
5698 _OutputIter
5699 match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __output_iter,
5700         const char_type* __fmt_first, const char_type* __fmt_last,
5701         regex_constants::match_flag_type __flags) const
5702 {
5703     _LIBCPP_ASSERT_UNCATEGORIZED(ready(), "match_results::format() called when not ready");
5704     if (__flags & regex_constants::format_sed)
5705     {
5706         for (; __fmt_first != __fmt_last; ++__fmt_first)
5707         {
5708             if (*__fmt_first == '&')
5709                 __output_iter = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5710                                    __output_iter);
5711             else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
5712             {
5713                 ++__fmt_first;
5714                 if ('0' <= *__fmt_first && *__fmt_first <= '9')
5715                 {
5716                     size_t __i = *__fmt_first - '0';
5717                     __output_iter = _VSTD::copy((*this)[__i].first,
5718                                         (*this)[__i].second, __output_iter);
5719                 }
5720                 else
5721                 {
5722                     *__output_iter = *__fmt_first;
5723                     ++__output_iter;
5724                 }
5725             }
5726             else
5727             {
5728                 *__output_iter = *__fmt_first;
5729                 ++__output_iter;
5730             }
5731         }
5732     }
5733     else
5734     {
5735         for (; __fmt_first != __fmt_last; ++__fmt_first)
5736         {
5737             if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
5738             {
5739                 switch (__fmt_first[1])
5740                 {
5741                 case '$':
5742                     *__output_iter = *++__fmt_first;
5743                     ++__output_iter;
5744                     break;
5745                 case '&':
5746                     ++__fmt_first;
5747                     __output_iter = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5748                                        __output_iter);
5749                     break;
5750                 case '`':
5751                     ++__fmt_first;
5752                     __output_iter = _VSTD::copy(__prefix_.first, __prefix_.second, __output_iter);
5753                     break;
5754                 case '\'':
5755                     ++__fmt_first;
5756                     __output_iter = _VSTD::copy(__suffix_.first, __suffix_.second, __output_iter);
5757                     break;
5758                 default:
5759                     if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5760                     {
5761                         ++__fmt_first;
5762                         size_t __idx = *__fmt_first - '0';
5763                         if (__fmt_first + 1 != __fmt_last &&
5764                             '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5765                         {
5766                             ++__fmt_first;
5767                             if (__idx >= numeric_limits<size_t>::max() / 10)
5768                                 __throw_regex_error<regex_constants::error_escape>();
5769                             __idx = 10 * __idx + *__fmt_first - '0';
5770                         }
5771                         __output_iter = _VSTD::copy((*this)[__idx].first,
5772                                             (*this)[__idx].second, __output_iter);
5773                     }
5774                     else
5775                     {
5776                         *__output_iter = *__fmt_first;
5777                         ++__output_iter;
5778                     }
5779                     break;
5780                 }
5781             }
5782             else
5783             {
5784                 *__output_iter = *__fmt_first;
5785                 ++__output_iter;
5786             }
5787         }
5788     }
5789     return __output_iter;
5790 }
5791
5792 template <class _BidirectionalIterator, class _Allocator>
5793 void
5794 match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
5795 {
5796     using _VSTD::swap;
5797     swap(__matches_, __m.__matches_);
5798     swap(__unmatched_, __m.__unmatched_);
5799     swap(__prefix_, __m.__prefix_);
5800     swap(__suffix_, __m.__suffix_);
5801     swap(__position_start_, __m.__position_start_);
5802     swap(__ready_, __m.__ready_);
5803 }
5804
5805 template <class _BidirectionalIterator, class _Allocator>
5806 _LIBCPP_HIDE_FROM_ABI bool
5807 operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
5808            const match_results<_BidirectionalIterator, _Allocator>& __y)
5809 {
5810     if (__x.__ready_ != __y.__ready_)
5811         return false;
5812     if (!__x.__ready_)
5813         return true;
5814     return __x.__matches_ == __y.__matches_ &&
5815            __x.__prefix_ == __y.__prefix_ &&
5816            __x.__suffix_ == __y.__suffix_;
5817 }
5818
5819 #if _LIBCPP_STD_VER < 20
5820 template <class _BidirectionalIterator, class _Allocator>
5821 inline _LIBCPP_INLINE_VISIBILITY
5822 bool
5823 operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
5824            const match_results<_BidirectionalIterator, _Allocator>& __y)
5825 {
5826     return !(__x == __y);
5827 }
5828 #endif
5829
5830 template <class _BidirectionalIterator, class _Allocator>
5831 inline _LIBCPP_INLINE_VISIBILITY
5832 void
5833 swap(match_results<_BidirectionalIterator, _Allocator>& __x,
5834      match_results<_BidirectionalIterator, _Allocator>& __y)
5835 {
5836     __x.swap(__y);
5837 }
5838
5839 // regex_search
5840
5841 template <class _CharT, class _Traits>
5842 template <class _Allocator>
5843 bool
5844 basic_regex<_CharT, _Traits>::__match_at_start_ecma(
5845         const _CharT* __first, const _CharT* __last,
5846         match_results<const _CharT*, _Allocator>& __m,
5847         regex_constants::match_flag_type __flags, bool __at_first) const
5848 {
5849     vector<__state> __states;
5850     __node* __st = __start_.get();
5851     if (__st)
5852     {
5853         sub_match<const _CharT*> __unmatched;
5854         __unmatched.first   = __last;
5855         __unmatched.second  = __last;
5856         __unmatched.matched = false;
5857
5858         __states.push_back(__state());
5859         __states.back().__do_ = 0;
5860         __states.back().__first_ = __first;
5861         __states.back().__current_ = __first;
5862         __states.back().__last_ = __last;
5863         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5864         __states.back().__loop_data_.resize(__loop_count());
5865         __states.back().__node_ = __st;
5866         __states.back().__flags_ = __flags;
5867         __states.back().__at_first_ = __at_first;
5868         int __counter = 0;
5869         int __length = __last - __first;
5870         do
5871         {
5872             ++__counter;
5873             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
5874                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5875               __throw_regex_error<regex_constants::error_complexity>();
5876             __state& __s = __states.back();
5877             if (__s.__node_)
5878                 __s.__node_->__exec(__s);
5879             switch (__s.__do_)
5880             {
5881             case __state::__end_state:
5882                 if ((__flags & regex_constants::match_not_null) &&
5883                     __s.__current_ == __first)
5884                 {
5885                   __states.pop_back();
5886                   break;
5887                 }
5888                 if ((__flags & regex_constants::__full_match) &&
5889                     __s.__current_ != __last)
5890                 {
5891                   __states.pop_back();
5892                   break;
5893                 }
5894                 __m.__matches_[0].first = __first;
5895                 __m.__matches_[0].second = _VSTD::next(__first, __s.__current_ - __first);
5896                 __m.__matches_[0].matched = true;
5897                 for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
5898                     __m.__matches_[__i+1] = __s.__sub_matches_[__i];
5899                 return true;
5900             case __state::__accept_and_consume:
5901             case __state::__repeat:
5902             case __state::__accept_but_not_consume:
5903                 break;
5904             case __state::__split:
5905                 {
5906                 __state __snext = __s;
5907                 __s.__node_->__exec_split(true, __s);
5908                 __snext.__node_->__exec_split(false, __snext);
5909                 __states.push_back(_VSTD::move(__snext));
5910                 }
5911                 break;
5912             case __state::__reject:
5913                 __states.pop_back();
5914                 break;
5915             default:
5916                 __throw_regex_error<regex_constants::__re_err_unknown>();
5917                 break;
5918
5919             }
5920         } while (!__states.empty());
5921     }
5922     return false;
5923 }
5924
5925 template <class _CharT, class _Traits>
5926 template <class _Allocator>
5927 bool
5928 basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
5929         const _CharT* __first, const _CharT* __last,
5930         match_results<const _CharT*, _Allocator>& __m,
5931         regex_constants::match_flag_type __flags, bool __at_first) const
5932 {
5933     deque<__state> __states;
5934     ptrdiff_t __highest_j = 0;
5935     ptrdiff_t __np = _VSTD::distance(__first, __last);
5936     __node* __st = __start_.get();
5937     if (__st)
5938     {
5939         __states.push_back(__state());
5940         __states.back().__do_ = 0;
5941         __states.back().__first_ = __first;
5942         __states.back().__current_ = __first;
5943         __states.back().__last_ = __last;
5944         __states.back().__loop_data_.resize(__loop_count());
5945         __states.back().__node_ = __st;
5946         __states.back().__flags_ = __flags;
5947         __states.back().__at_first_ = __at_first;
5948         bool __matched = false;
5949         int __counter = 0;
5950         int __length = __last - __first;
5951         do
5952         {
5953             ++__counter;
5954             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
5955                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5956               __throw_regex_error<regex_constants::error_complexity>();
5957             __state& __s = __states.back();
5958             if (__s.__node_)
5959                 __s.__node_->__exec(__s);
5960             switch (__s.__do_)
5961             {
5962             case __state::__end_state:
5963                 if ((__flags & regex_constants::match_not_null) &&
5964                     __s.__current_ == __first)
5965                 {
5966                   __states.pop_back();
5967                   break;
5968                 }
5969                 if ((__flags & regex_constants::__full_match) &&
5970                     __s.__current_ != __last)
5971                 {
5972                   __states.pop_back();
5973                   break;
5974                 }
5975                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5976                     __highest_j = __s.__current_ - __s.__first_;
5977                 __matched = true;
5978                 if (__highest_j == __np)
5979                     __states.clear();
5980                 else
5981                     __states.pop_back();
5982                 break;
5983             case __state::__consume_input:
5984                 break;
5985             case __state::__accept_and_consume:
5986                 __states.push_front(_VSTD::move(__s));
5987                 __states.pop_back();
5988                 break;
5989             case __state::__repeat:
5990             case __state::__accept_but_not_consume:
5991                 break;
5992             case __state::__split:
5993                 {
5994                 __state __snext = __s;
5995                 __s.__node_->__exec_split(true, __s);
5996                 __snext.__node_->__exec_split(false, __snext);
5997                 __states.push_back(_VSTD::move(__snext));
5998                 }
5999                 break;
6000             case __state::__reject:
6001                 __states.pop_back();
6002                 break;
6003             default:
6004                 __throw_regex_error<regex_constants::__re_err_unknown>();
6005                 break;
6006             }
6007         } while (!__states.empty());
6008         if (__matched)
6009         {
6010             __m.__matches_[0].first = __first;
6011             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
6012             __m.__matches_[0].matched = true;
6013             return true;
6014         }
6015     }
6016     return false;
6017 }
6018
6019 template <class _CharT, class _Traits>
6020 template <class _Allocator>
6021 bool
6022 basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
6023         const _CharT* __first, const _CharT* __last,
6024         match_results<const _CharT*, _Allocator>& __m,
6025         regex_constants::match_flag_type __flags, bool __at_first) const
6026 {
6027     vector<__state> __states;
6028     __state __best_state;
6029     ptrdiff_t __highest_j = 0;
6030     ptrdiff_t __np = _VSTD::distance(__first, __last);
6031     __node* __st = __start_.get();
6032     if (__st)
6033     {
6034         sub_match<const _CharT*> __unmatched;
6035         __unmatched.first   = __last;
6036         __unmatched.second  = __last;
6037         __unmatched.matched = false;
6038
6039         __states.push_back(__state());
6040         __states.back().__do_ = 0;
6041         __states.back().__first_ = __first;
6042         __states.back().__current_ = __first;
6043         __states.back().__last_ = __last;
6044         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
6045         __states.back().__loop_data_.resize(__loop_count());
6046         __states.back().__node_ = __st;
6047         __states.back().__flags_ = __flags;
6048         __states.back().__at_first_ = __at_first;
6049         bool __matched = false;
6050         int __counter = 0;
6051         int __length = __last - __first;
6052         do
6053         {
6054             ++__counter;
6055             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
6056                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
6057               __throw_regex_error<regex_constants::error_complexity>();
6058             __state& __s = __states.back();
6059             if (__s.__node_)
6060                 __s.__node_->__exec(__s);
6061             switch (__s.__do_)
6062             {
6063             case __state::__end_state:
6064                 if ((__flags & regex_constants::match_not_null) &&
6065                     __s.__current_ == __first)
6066                 {
6067                   __states.pop_back();
6068                   break;
6069                 }
6070                 if ((__flags & regex_constants::__full_match) &&
6071                     __s.__current_ != __last)
6072                 {
6073                   __states.pop_back();
6074                   break;
6075                 }
6076                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
6077                 {
6078                     __highest_j = __s.__current_ - __s.__first_;
6079                     __best_state = __s;
6080                 }
6081                 __matched = true;
6082                 if (__highest_j == __np)
6083                     __states.clear();
6084                 else
6085                     __states.pop_back();
6086                 break;
6087             case __state::__accept_and_consume:
6088             case __state::__repeat:
6089             case __state::__accept_but_not_consume:
6090                 break;
6091             case __state::__split:
6092                 {
6093                 __state __snext = __s;
6094                 __s.__node_->__exec_split(true, __s);
6095                 __snext.__node_->__exec_split(false, __snext);
6096                 __states.push_back(_VSTD::move(__snext));
6097                 }
6098                 break;
6099             case __state::__reject:
6100                 __states.pop_back();
6101                 break;
6102             default:
6103                 __throw_regex_error<regex_constants::__re_err_unknown>();
6104                 break;
6105             }
6106         } while (!__states.empty());
6107         if (__matched)
6108         {
6109             __m.__matches_[0].first = __first;
6110             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
6111             __m.__matches_[0].matched = true;
6112             for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
6113                 __m.__matches_[__i+1] = __best_state.__sub_matches_[__i];
6114             return true;
6115         }
6116     }
6117     return false;
6118 }
6119
6120 template <class _CharT, class _Traits>
6121 template <class _Allocator>
6122 bool
6123 basic_regex<_CharT, _Traits>::__match_at_start(
6124         const _CharT* __first, const _CharT* __last,
6125         match_results<const _CharT*, _Allocator>& __m,
6126         regex_constants::match_flag_type __flags, bool __at_first) const
6127 {
6128     if (__get_grammar(__flags_) == ECMAScript)
6129         return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
6130     if (mark_count() == 0)
6131         return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
6132     return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
6133 }
6134
6135 template <class _CharT, class _Traits>
6136 template <class _Allocator>
6137 bool
6138 basic_regex<_CharT, _Traits>::__search(
6139         const _CharT* __first, const _CharT* __last,
6140         match_results<const _CharT*, _Allocator>& __m,
6141         regex_constants::match_flag_type __flags) const
6142 {
6143     if (__flags & regex_constants::match_prev_avail)
6144         __flags &= ~(regex_constants::match_not_bol | regex_constants::match_not_bow);
6145
6146     __m.__init(1 + mark_count(), __first, __last,
6147                                     __flags & regex_constants::__no_update_pos);
6148     if (__match_at_start(__first, __last, __m, __flags,
6149                                     !(__flags & regex_constants::__no_update_pos)))
6150     {
6151         __m.__prefix_.second = __m[0].first;
6152         __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
6153         __m.__suffix_.first = __m[0].second;
6154         __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
6155         return true;
6156     }
6157     if (__first != __last && !(__flags & regex_constants::match_continuous))
6158     {
6159         __flags |= regex_constants::match_prev_avail;
6160         for (++__first; __first != __last; ++__first)
6161         {
6162             __m.__matches_.assign(__m.size(), __m.__unmatched_);
6163             if (__match_at_start(__first, __last, __m, __flags, false))
6164             {
6165                 __m.__prefix_.second = __m[0].first;
6166                 __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
6167                 __m.__suffix_.first = __m[0].second;
6168                 __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
6169                 return true;
6170             }
6171             __m.__matches_.assign(__m.size(), __m.__unmatched_);
6172         }
6173     }
6174     __m.__matches_.clear();
6175     return false;
6176 }
6177
6178 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
6179 inline _LIBCPP_INLINE_VISIBILITY
6180 bool
6181 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
6182              match_results<_BidirectionalIterator, _Allocator>& __m,
6183              const basic_regex<_CharT, _Traits>& __e,
6184              regex_constants::match_flag_type __flags = regex_constants::match_default)
6185 {
6186     int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
6187     basic_string<_CharT> __s(_VSTD::prev(__first, __offset), __last);
6188     match_results<const _CharT*> __mc;
6189     bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
6190     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
6191     return __r;
6192 }
6193
6194 template <class _Iter, class _Allocator, class _CharT, class _Traits>
6195 inline _LIBCPP_INLINE_VISIBILITY
6196 bool
6197 regex_search(__wrap_iter<_Iter> __first,
6198              __wrap_iter<_Iter> __last,
6199              match_results<__wrap_iter<_Iter>, _Allocator>& __m,
6200              const basic_regex<_CharT, _Traits>& __e,
6201              regex_constants::match_flag_type __flags = regex_constants::match_default)
6202 {
6203     match_results<const _CharT*> __mc;
6204     bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
6205     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
6206     return __r;
6207 }
6208
6209 template <class _Allocator, class _CharT, class _Traits>
6210 inline _LIBCPP_INLINE_VISIBILITY
6211 bool
6212 regex_search(const _CharT* __first, const _CharT* __last,
6213              match_results<const _CharT*, _Allocator>& __m,
6214              const basic_regex<_CharT, _Traits>& __e,
6215              regex_constants::match_flag_type __flags = regex_constants::match_default)
6216 {
6217     return __e.__search(__first, __last, __m, __flags);
6218 }
6219
6220 template <class _BidirectionalIterator, class _CharT, class _Traits>
6221 inline _LIBCPP_INLINE_VISIBILITY
6222 bool
6223 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
6224              const basic_regex<_CharT, _Traits>& __e,
6225              regex_constants::match_flag_type __flags = regex_constants::match_default)
6226 {
6227     basic_string<_CharT> __s(__first, __last);
6228     match_results<const _CharT*> __mc;
6229     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
6230 }
6231
6232 template <class _CharT, class _Traits>
6233 inline _LIBCPP_INLINE_VISIBILITY
6234 bool
6235 regex_search(const _CharT* __first, const _CharT* __last,
6236              const basic_regex<_CharT, _Traits>& __e,
6237              regex_constants::match_flag_type __flags = regex_constants::match_default)
6238 {
6239     match_results<const _CharT*> __mc;
6240     return __e.__search(__first, __last, __mc, __flags);
6241 }
6242
6243 template <class _CharT, class _Allocator, class _Traits>
6244 inline _LIBCPP_INLINE_VISIBILITY
6245 bool
6246 regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
6247              const basic_regex<_CharT, _Traits>& __e,
6248              regex_constants::match_flag_type __flags = regex_constants::match_default)
6249 {
6250     return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
6251 }
6252
6253 template <class _CharT, class _Traits>
6254 inline _LIBCPP_INLINE_VISIBILITY
6255 bool
6256 regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
6257              regex_constants::match_flag_type __flags = regex_constants::match_default)
6258 {
6259     match_results<const _CharT*> __m;
6260     return _VSTD::regex_search(__str, __m, __e, __flags);
6261 }
6262
6263 template <class _ST, class _SA, class _CharT, class _Traits>
6264 inline _LIBCPP_INLINE_VISIBILITY
6265 bool
6266 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
6267              const basic_regex<_CharT, _Traits>& __e,
6268              regex_constants::match_flag_type __flags = regex_constants::match_default)
6269 {
6270     match_results<const _CharT*> __mc;
6271     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
6272 }
6273
6274 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6275 inline _LIBCPP_INLINE_VISIBILITY
6276 bool
6277 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
6278              match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6279              const basic_regex<_CharT, _Traits>& __e,
6280              regex_constants::match_flag_type __flags = regex_constants::match_default)
6281 {
6282     match_results<const _CharT*> __mc;
6283     bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
6284     __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
6285     return __r;
6286 }
6287
6288 #if _LIBCPP_STD_VER >= 14
6289 template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
6290 bool
6291 regex_search(const basic_string<_Cp, _ST, _SA>&& __s,
6292              match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
6293              const basic_regex<_Cp, _Tp>& __e,
6294              regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
6295 #endif
6296
6297 // regex_match
6298
6299 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
6300 _LIBCPP_HIDE_FROM_ABI bool
6301 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
6302             match_results<_BidirectionalIterator, _Allocator>& __m,
6303             const basic_regex<_CharT, _Traits>& __e,
6304             regex_constants::match_flag_type __flags = regex_constants::match_default)
6305 {
6306     bool __r = _VSTD::regex_search(
6307         __first, __last, __m, __e,
6308         __flags | regex_constants::match_continuous |
6309         regex_constants::__full_match);
6310     if (__r)
6311     {
6312         __r = !__m.suffix().matched;
6313         if (!__r)
6314             __m.__matches_.clear();
6315     }
6316     return __r;
6317 }
6318
6319 template <class _BidirectionalIterator, class _CharT, class _Traits>
6320 inline _LIBCPP_INLINE_VISIBILITY
6321 bool
6322 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
6323             const basic_regex<_CharT, _Traits>& __e,
6324             regex_constants::match_flag_type __flags = regex_constants::match_default)
6325 {
6326     match_results<_BidirectionalIterator> __m;
6327     return _VSTD::regex_match(__first, __last, __m, __e, __flags);
6328 }
6329
6330 template <class _CharT, class _Allocator, class _Traits>
6331 inline _LIBCPP_INLINE_VISIBILITY
6332 bool
6333 regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
6334             const basic_regex<_CharT, _Traits>& __e,
6335             regex_constants::match_flag_type __flags = regex_constants::match_default)
6336 {
6337     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
6338 }
6339
6340 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6341 inline _LIBCPP_INLINE_VISIBILITY
6342 bool
6343 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6344             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6345             const basic_regex<_CharT, _Traits>& __e,
6346             regex_constants::match_flag_type __flags = regex_constants::match_default)
6347 {
6348     return _VSTD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
6349 }
6350
6351 #if _LIBCPP_STD_VER >= 14
6352 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6353 inline _LIBCPP_INLINE_VISIBILITY
6354 bool
6355 regex_match(const basic_string<_CharT, _ST, _SA>&& __s,
6356             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6357             const basic_regex<_CharT, _Traits>& __e,
6358             regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
6359 #endif
6360
6361 template <class _CharT, class _Traits>
6362 inline _LIBCPP_INLINE_VISIBILITY
6363 bool
6364 regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
6365             regex_constants::match_flag_type __flags = regex_constants::match_default)
6366 {
6367     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
6368 }
6369
6370 template <class _ST, class _SA, class _CharT, class _Traits>
6371 inline _LIBCPP_INLINE_VISIBILITY
6372 bool
6373 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6374             const basic_regex<_CharT, _Traits>& __e,
6375             regex_constants::match_flag_type __flags = regex_constants::match_default)
6376 {
6377     return _VSTD::regex_match(__s.begin(), __s.end(), __e, __flags);
6378 }
6379
6380 // regex_iterator
6381
6382 template <class _BidirectionalIterator,
6383           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6384           class _Traits = regex_traits<_CharT> >
6385     class _LIBCPP_TEMPLATE_VIS regex_iterator;
6386
6387 typedef regex_iterator<const char*>             cregex_iterator;
6388 typedef regex_iterator<string::const_iterator>  sregex_iterator;
6389 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
6390 typedef regex_iterator<const wchar_t*>          wcregex_iterator;
6391 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
6392 #endif
6393
6394 template <class _BidirectionalIterator, class _CharT, class _Traits>
6395 class
6396     _LIBCPP_TEMPLATE_VIS
6397     _LIBCPP_PREFERRED_NAME(cregex_iterator)
6398     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_iterator))
6399     _LIBCPP_PREFERRED_NAME(sregex_iterator)
6400     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_iterator))
6401     regex_iterator
6402 {
6403 public:
6404     typedef basic_regex<_CharT, _Traits>          regex_type;
6405     typedef match_results<_BidirectionalIterator> value_type;
6406     typedef ptrdiff_t                             difference_type;
6407     typedef const value_type*                     pointer;
6408     typedef const value_type&                     reference;
6409     typedef forward_iterator_tag                  iterator_category;
6410
6411 private:
6412     _BidirectionalIterator           __begin_;
6413     _BidirectionalIterator           __end_;
6414     const regex_type*                __pregex_;
6415     regex_constants::match_flag_type __flags_;
6416     value_type                       __match_;
6417
6418 public:
6419     regex_iterator();
6420     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6421                    const regex_type& __re,
6422                    regex_constants::match_flag_type __m
6423                                               = regex_constants::match_default);
6424 #if _LIBCPP_STD_VER >= 14
6425     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6426                    const regex_type&& __re,
6427                    regex_constants::match_flag_type __m
6428                                      = regex_constants::match_default) = delete;
6429 #endif
6430
6431     _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_iterator& __x) const;
6432 #if _LIBCPP_STD_VER >= 20
6433     _LIBCPP_HIDE_FROM_ABI bool operator==(default_sentinel_t) const { return *this == regex_iterator(); }
6434 #endif
6435 #if _LIBCPP_STD_VER < 20
6436     _LIBCPP_INLINE_VISIBILITY
6437     bool operator!=(const regex_iterator& __x) const {return !(*this == __x);}
6438 #endif
6439
6440     _LIBCPP_INLINE_VISIBILITY
6441     reference operator*() const {return  __match_;}
6442     _LIBCPP_INLINE_VISIBILITY
6443     pointer operator->() const  {return _VSTD::addressof(__match_);}
6444
6445     regex_iterator& operator++();
6446     _LIBCPP_INLINE_VISIBILITY
6447     regex_iterator operator++(int)
6448     {
6449         regex_iterator __t(*this);
6450         ++(*this);
6451         return __t;
6452     }
6453 };
6454
6455 template <class _BidirectionalIterator, class _CharT, class _Traits>
6456 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
6457     : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_()
6458 {
6459 }
6460
6461 template <class _BidirectionalIterator, class _CharT, class _Traits>
6462 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6463     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6464                    const regex_type& __re, regex_constants::match_flag_type __m)
6465     : __begin_(__a),
6466       __end_(__b),
6467       __pregex_(_VSTD::addressof(__re)),
6468       __flags_(__m)
6469 {
6470     _VSTD::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
6471 }
6472
6473 template <class _BidirectionalIterator, class _CharT, class _Traits>
6474 bool
6475 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6476     operator==(const regex_iterator& __x) const
6477 {
6478     if (__match_.empty() && __x.__match_.empty())
6479         return true;
6480     if (__match_.empty() || __x.__match_.empty())
6481         return false;
6482     return __begin_ == __x.__begin_       &&
6483            __end_ == __x.__end_           &&
6484            __pregex_ == __x.__pregex_     &&
6485            __flags_ == __x.__flags_       &&
6486            __match_[0] == __x.__match_[0];
6487 }
6488
6489 template <class _BidirectionalIterator, class _CharT, class _Traits>
6490 regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
6491 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6492 {
6493     __flags_ |= regex_constants::__no_update_pos;
6494     _BidirectionalIterator __start = __match_[0].second;
6495     if (__match_[0].first == __match_[0].second)
6496     {
6497         if (__start == __end_)
6498         {
6499             __match_ = value_type();
6500             return *this;
6501         }
6502         else if (_VSTD::regex_search(__start, __end_, __match_, *__pregex_,
6503                                     __flags_ | regex_constants::match_not_null |
6504                                     regex_constants::match_continuous))
6505             return *this;
6506         else
6507             ++__start;
6508     }
6509     __flags_ |= regex_constants::match_prev_avail;
6510     if (!_VSTD::regex_search(__start, __end_, __match_, *__pregex_, __flags_))
6511         __match_ = value_type();
6512     return *this;
6513 }
6514
6515 // regex_token_iterator
6516
6517 template <class _BidirectionalIterator,
6518           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6519           class _Traits = regex_traits<_CharT> >
6520     class _LIBCPP_TEMPLATE_VIS regex_token_iterator;
6521
6522 typedef regex_token_iterator<const char*>             cregex_token_iterator;
6523 typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
6524 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
6525 typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
6526 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
6527 #endif
6528
6529 template <class _BidirectionalIterator, class _CharT, class _Traits>
6530 class
6531     _LIBCPP_TEMPLATE_VIS
6532     _LIBCPP_PREFERRED_NAME(cregex_token_iterator)
6533     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wcregex_token_iterator))
6534     _LIBCPP_PREFERRED_NAME(sregex_token_iterator)
6535     _LIBCPP_IF_WIDE_CHARACTERS(_LIBCPP_PREFERRED_NAME(wsregex_token_iterator))
6536     regex_token_iterator
6537 {
6538 public:
6539     typedef basic_regex<_CharT, _Traits>      regex_type;
6540     typedef sub_match<_BidirectionalIterator> value_type;
6541     typedef ptrdiff_t                         difference_type;
6542     typedef const value_type*                 pointer;
6543     typedef const value_type&                 reference;
6544     typedef forward_iterator_tag              iterator_category;
6545
6546 private:
6547     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
6548
6549     _Position         __position_;
6550     const value_type* __result_;
6551     value_type        __suffix_;
6552     ptrdiff_t         __n_;
6553     vector<int>       __subs_;
6554
6555 public:
6556     regex_token_iterator();
6557     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6558                          const regex_type& __re, int __submatch = 0,
6559                          regex_constants::match_flag_type __m =
6560                                                 regex_constants::match_default);
6561 #if _LIBCPP_STD_VER >= 14
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) = delete;
6566 #endif
6567
6568     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6569                          const regex_type& __re, const vector<int>& __submatches,
6570                          regex_constants::match_flag_type __m =
6571                                                 regex_constants::match_default);
6572 #if _LIBCPP_STD_VER >= 14
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) = delete;
6577 #endif
6578
6579 #ifndef _LIBCPP_CXX03_LANG
6580     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6581                          const regex_type& __re,
6582                          initializer_list<int> __submatches,
6583                          regex_constants::match_flag_type __m =
6584                                                 regex_constants::match_default);
6585
6586 #if _LIBCPP_STD_VER >= 14
6587     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6588                          const regex_type&& __re,
6589                          initializer_list<int> __submatches,
6590                          regex_constants::match_flag_type __m =
6591                                        regex_constants::match_default) = delete;
6592 #endif
6593 #endif // _LIBCPP_CXX03_LANG
6594     template <size_t _Np>
6595         regex_token_iterator(_BidirectionalIterator __a,
6596                              _BidirectionalIterator __b,
6597                              const regex_type& __re,
6598                              const int (&__submatches)[_Np],
6599                              regex_constants::match_flag_type __m =
6600                                                 regex_constants::match_default);
6601 #if _LIBCPP_STD_VER >= 14
6602     template <size_t _Np>
6603         regex_token_iterator(_BidirectionalIterator __a,
6604                              _BidirectionalIterator __b,
6605                              const regex_type&& __re,
6606                              const int (&__submatches)[_Np],
6607                              regex_constants::match_flag_type __m =
6608                                       regex_constants::match_default) = delete;
6609 #endif
6610
6611     regex_token_iterator(const regex_token_iterator&);
6612     regex_token_iterator& operator=(const regex_token_iterator&);
6613
6614     _LIBCPP_HIDE_FROM_ABI bool operator==(const regex_token_iterator& __x) const;
6615 #if _LIBCPP_STD_VER >= 20
6616     _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI bool operator==(default_sentinel_t) const {
6617         return *this == regex_token_iterator();
6618     }
6619 #endif
6620 #if _LIBCPP_STD_VER < 20
6621     _LIBCPP_INLINE_VISIBILITY
6622     bool operator!=(const regex_token_iterator& __x) const {return !(*this == __x);}
6623 #endif
6624
6625     _LIBCPP_INLINE_VISIBILITY
6626     const value_type& operator*() const {return *__result_;}
6627     _LIBCPP_INLINE_VISIBILITY
6628     const value_type* operator->() const {return __result_;}
6629
6630     regex_token_iterator& operator++();
6631     _LIBCPP_INLINE_VISIBILITY
6632     regex_token_iterator operator++(int)
6633     {
6634         regex_token_iterator __t(*this);
6635         ++(*this);
6636         return __t;
6637     }
6638
6639 private:
6640     void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
6641     void __establish_result () {
6642         if (__subs_[__n_] == -1)
6643             __result_ = &__position_->prefix();
6644         else
6645             __result_ = &(*__position_)[__subs_[__n_]];
6646         }
6647 };
6648
6649 template <class _BidirectionalIterator, class _CharT, class _Traits>
6650 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6651     regex_token_iterator()
6652     : __result_(nullptr),
6653       __suffix_(),
6654       __n_(0)
6655 {
6656 }
6657
6658 template <class _BidirectionalIterator, class _CharT, class _Traits>
6659 void
6660 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6661     __init(_BidirectionalIterator __a, _BidirectionalIterator __b)
6662 {
6663     if (__position_ != _Position())
6664         __establish_result ();
6665     else if (__subs_[__n_] == -1)
6666     {
6667         __suffix_.matched = true;
6668         __suffix_.first = __a;
6669         __suffix_.second = __b;
6670         __result_ = &__suffix_;
6671     }
6672     else
6673         __result_ = nullptr;
6674 }
6675
6676 template <class _BidirectionalIterator, class _CharT, class _Traits>
6677 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6678     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6679                          const regex_type& __re, int __submatch,
6680                          regex_constants::match_flag_type __m)
6681     : __position_(__a, __b, __re, __m),
6682       __n_(0),
6683       __subs_(1, __submatch)
6684 {
6685     __init(__a, __b);
6686 }
6687
6688 template <class _BidirectionalIterator, class _CharT, class _Traits>
6689 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6690     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6691                          const regex_type& __re, const vector<int>& __submatches,
6692                          regex_constants::match_flag_type __m)
6693     : __position_(__a, __b, __re, __m),
6694       __n_(0),
6695       __subs_(__submatches)
6696 {
6697     __init(__a, __b);
6698 }
6699
6700 #ifndef _LIBCPP_CXX03_LANG
6701
6702 template <class _BidirectionalIterator, class _CharT, class _Traits>
6703 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6704     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6705                          const regex_type& __re,
6706                          initializer_list<int> __submatches,
6707                          regex_constants::match_flag_type __m)
6708     : __position_(__a, __b, __re, __m),
6709       __n_(0),
6710       __subs_(__submatches)
6711 {
6712     __init(__a, __b);
6713 }
6714
6715 #endif // _LIBCPP_CXX03_LANG
6716
6717 template <class _BidirectionalIterator, class _CharT, class _Traits>
6718 template <size_t _Np>
6719 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6720     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6721                              const regex_type& __re,
6722                              const int (&__submatches)[_Np],
6723                              regex_constants::match_flag_type __m)
6724     : __position_(__a, __b, __re, __m),
6725       __n_(0),
6726       __subs_(begin(__submatches), end(__submatches))
6727 {
6728     __init(__a, __b);
6729 }
6730
6731 template <class _BidirectionalIterator, class _CharT, class _Traits>
6732 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6733     regex_token_iterator(const regex_token_iterator& __x)
6734     : __position_(__x.__position_),
6735       __result_(__x.__result_),
6736       __suffix_(__x.__suffix_),
6737       __n_(__x.__n_),
6738       __subs_(__x.__subs_)
6739 {
6740     if (__x.__result_ == &__x.__suffix_)
6741         __result_ = &__suffix_;
6742     else if ( __result_ != nullptr )
6743         __establish_result ();
6744 }
6745
6746 template <class _BidirectionalIterator, class _CharT, class _Traits>
6747 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6748 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6749     operator=(const regex_token_iterator& __x)
6750 {
6751     if (this != &__x)
6752     {
6753         __position_ = __x.__position_;
6754         if (__x.__result_ == &__x.__suffix_)
6755             __result_ = &__suffix_;
6756         else
6757             __result_ = __x.__result_;
6758         __suffix_ = __x.__suffix_;
6759         __n_ = __x.__n_;
6760         __subs_ = __x.__subs_;
6761
6762         if ( __result_ != nullptr && __result_ != &__suffix_ )
6763             __establish_result();
6764     }
6765     return *this;
6766 }
6767
6768 template <class _BidirectionalIterator, class _CharT, class _Traits>
6769 bool
6770 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6771     operator==(const regex_token_iterator& __x) const
6772 {
6773     if (__result_ == nullptr && __x.__result_ == nullptr)
6774         return true;
6775     if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ &&
6776             __suffix_ == __x.__suffix_)
6777         return true;
6778     if (__result_ == nullptr || __x.__result_ == nullptr)
6779         return false;
6780     if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
6781         return false;
6782     return __position_ == __x.__position_ && __n_ == __x.__n_ &&
6783            __subs_ == __x.__subs_;
6784 }
6785
6786 template <class _BidirectionalIterator, class _CharT, class _Traits>
6787 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6788 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6789 {
6790     _Position __prev = __position_;
6791     if (__result_ == &__suffix_)
6792         __result_ = nullptr;
6793     else if (static_cast<size_t>(__n_ + 1) < __subs_.size())
6794     {
6795         ++__n_;
6796         __establish_result();
6797     }
6798     else
6799     {
6800         __n_ = 0;
6801         ++__position_;
6802         if (__position_ != _Position())
6803             __establish_result();
6804         else
6805         {
6806             if (_VSTD::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end()
6807                 && __prev->suffix().length() != 0)
6808             {
6809                 __suffix_.matched = true;
6810                 __suffix_.first = __prev->suffix().first;
6811                 __suffix_.second = __prev->suffix().second;
6812                 __result_ = &__suffix_;
6813             }
6814             else
6815                 __result_ = nullptr;
6816         }
6817     }
6818     return *this;
6819 }
6820
6821 // regex_replace
6822
6823 template <class _OutputIterator, class _BidirectionalIterator,
6824           class _Traits, class _CharT>
6825 _LIBCPP_HIDE_FROM_ABI _OutputIterator
6826 regex_replace(_OutputIterator __output_iter,
6827               _BidirectionalIterator __first, _BidirectionalIterator __last,
6828               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6829               regex_constants::match_flag_type __flags = regex_constants::match_default)
6830 {
6831     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
6832     _Iter __i(__first, __last, __e, __flags);
6833     _Iter __eof;
6834     if (__i == __eof)
6835     {
6836         if (!(__flags & regex_constants::format_no_copy))
6837             __output_iter = _VSTD::copy(__first, __last, __output_iter);
6838     }
6839     else
6840     {
6841         sub_match<_BidirectionalIterator> __lm;
6842         for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i)
6843         {
6844             if (!(__flags & regex_constants::format_no_copy))
6845                 __output_iter = _VSTD::copy(__i->prefix().first, __i->prefix().second, __output_iter);
6846             __output_iter = __i->format(__output_iter, __fmt, __fmt + __len, __flags);
6847             __lm = __i->suffix();
6848             if (__flags & regex_constants::format_first_only)
6849                 break;
6850         }
6851         if (!(__flags & regex_constants::format_no_copy))
6852             __output_iter = _VSTD::copy(__lm.first, __lm.second, __output_iter);
6853     }
6854     return __output_iter;
6855 }
6856
6857 template <class _OutputIterator, class _BidirectionalIterator,
6858           class _Traits, class _CharT, class _ST, class _SA>
6859 inline _LIBCPP_INLINE_VISIBILITY
6860 _OutputIterator
6861 regex_replace(_OutputIterator __output_iter,
6862               _BidirectionalIterator __first, _BidirectionalIterator __last,
6863               const basic_regex<_CharT, _Traits>& __e,
6864               const basic_string<_CharT, _ST, _SA>& __fmt,
6865               regex_constants::match_flag_type __flags = regex_constants::match_default)
6866 {
6867     return _VSTD::regex_replace(__output_iter, __first, __last, __e, __fmt.c_str(), __flags);
6868 }
6869
6870 template <class _Traits, class _CharT, class _ST, class _SA, class _FST,
6871           class _FSA>
6872 inline _LIBCPP_INLINE_VISIBILITY
6873 basic_string<_CharT, _ST, _SA>
6874 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6875               const basic_regex<_CharT, _Traits>& __e,
6876               const basic_string<_CharT, _FST, _FSA>& __fmt,
6877               regex_constants::match_flag_type __flags = regex_constants::match_default)
6878 {
6879     basic_string<_CharT, _ST, _SA> __r;
6880     _VSTD::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e,
6881                         __fmt.c_str(), __flags);
6882     return __r;
6883 }
6884
6885 template <class _Traits, class _CharT, class _ST, class _SA>
6886 inline _LIBCPP_INLINE_VISIBILITY
6887 basic_string<_CharT, _ST, _SA>
6888 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6889               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6890               regex_constants::match_flag_type __flags = regex_constants::match_default)
6891 {
6892     basic_string<_CharT, _ST, _SA> __r;
6893     _VSTD::regex_replace(std::back_inserter(__r), __s.begin(), __s.end(), __e,
6894                         __fmt, __flags);
6895     return __r;
6896 }
6897
6898 template <class _Traits, class _CharT, class _ST, class _SA>
6899 inline _LIBCPP_INLINE_VISIBILITY
6900 basic_string<_CharT>
6901 regex_replace(const _CharT* __s,
6902               const basic_regex<_CharT, _Traits>& __e,
6903               const basic_string<_CharT, _ST, _SA>& __fmt,
6904               regex_constants::match_flag_type __flags = regex_constants::match_default)
6905 {
6906     basic_string<_CharT> __r;
6907     _VSTD::regex_replace(std::back_inserter(__r), __s,
6908                         __s + char_traits<_CharT>::length(__s), __e,
6909                         __fmt.c_str(), __flags);
6910     return __r;
6911 }
6912
6913 template <class _Traits, class _CharT>
6914 inline _LIBCPP_INLINE_VISIBILITY
6915 basic_string<_CharT>
6916 regex_replace(const _CharT* __s,
6917               const basic_regex<_CharT, _Traits>& __e,
6918               const _CharT* __fmt,
6919               regex_constants::match_flag_type __flags = regex_constants::match_default)
6920 {
6921     basic_string<_CharT> __r;
6922     _VSTD::regex_replace(std::back_inserter(__r), __s,
6923                         __s + char_traits<_CharT>::length(__s), __e,
6924                         __fmt, __flags);
6925     return __r;
6926 }
6927
6928 _LIBCPP_END_NAMESPACE_STD
6929
6930 #if _LIBCPP_STD_VER >= 17
6931 _LIBCPP_BEGIN_NAMESPACE_STD
6932 namespace pmr {
6933 template <class _BidirT>
6934 using match_results _LIBCPP_AVAILABILITY_PMR = std::match_results<_BidirT, polymorphic_allocator<std::sub_match<_BidirT>>>;
6935
6936 using cmatch _LIBCPP_AVAILABILITY_PMR  = match_results<const char*>;
6937 using smatch _LIBCPP_AVAILABILITY_PMR  = match_results<std::pmr::string::const_iterator>;
6938
6939 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
6940 using wcmatch _LIBCPP_AVAILABILITY_PMR = match_results<const wchar_t*>;
6941 using wsmatch _LIBCPP_AVAILABILITY_PMR = match_results<std::pmr::wstring::const_iterator>;
6942 #endif
6943 } // namespace pmr
6944 _LIBCPP_END_NAMESPACE_STD
6945 #endif
6946
6947 _LIBCPP_POP_MACROS
6948
6949 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
6950 #  include <atomic>
6951 #  include <concepts>
6952 #  include <cstdlib>
6953 #  include <iosfwd>
6954 #  include <iterator>
6955 #  include <mutex>
6956 #  include <new>
6957 #  include <type_traits>
6958 #  include <typeinfo>
6959 #  include <utility>
6960 #endif
6961
6962 #endif // _LIBCPP_REGEX