contrib/libc++/include/regex

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