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