contrib/libc++/include/regex

   1 // -*- C++ -*-
   2 //===--------------------------- regex ------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_REGEX
  12 #define _LIBCPP_REGEX
  13
  14 /*
  15     regex synopsis
  16
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 namespace regex_constants
  23 {
  24
  25 emum syntax_option_type
  26 {
  27     icase      = unspecified,
  28     nosubs     = unspecified,
  29     optimize   = unspecified,
  30     collate    = unspecified,
  31     ECMAScript = unspecified,
  32     basic      = unspecified,
  33     extended   = unspecified,
  34     awk        = unspecified,
  35     grep       = unspecified,
  36     egrep      = unspecified
  37 };
  38
  39 constexpr syntax_option_type operator~(syntax_option_type f);
  40 constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
  41 constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);
  42
  43 enum match_flag_type
  44 {
  45     match_default     = 0,
  46     match_not_bol     = unspecified,
  47     match_not_eol     = unspecified,
  48     match_not_bow     = unspecified,
  49     match_not_eow     = unspecified,
  50     match_any         = unspecified,
  51     match_not_null    = unspecified,
  52     match_continuous  = unspecified,
  53     match_prev_avail  = unspecified,
  54     format_default    = 0,
  55     format_sed        = unspecified,
  56     format_no_copy    = unspecified,
  57     format_first_only = unspecified
  58 };
  59
  60 constexpr match_flag_type operator~(match_flag_type f);
  61 constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
  62 constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);
  63
  64 enum error_type
  65 {
  66     error_collate    = unspecified,
  67     error_ctype      = unspecified,
  68     error_escape     = unspecified,
  69     error_backref    = unspecified,
  70     error_brack      = unspecified,
  71     error_paren      = unspecified,
  72     error_brace      = unspecified,
  73     error_badbrace   = unspecified,
  74     error_range      = unspecified,
  75     error_space      = unspecified,
  76     error_badrepeat  = unspecified,
  77     error_complexity = unspecified,
  78     error_stack      = unspecified
  79 };
  80
  81 }  // regex_constants
  82
  83 class regex_error
  84     : public runtime_error
  85 {
  86 public:
  87     explicit regex_error(regex_constants::error_type ecode);
  88     regex_constants::error_type code() const;
  89 };
  90
  91 template <class charT>
  92 struct regex_traits
  93 {
  94 public:
  95     typedef charT                   char_type;
  96     typedef basic_string<char_type> string_type;
  97     typedef locale                  locale_type;
  98     typedef /bitmask_type/          char_class_type;
  99
 100     regex_traits();
 101
 102     static size_t length(const char_type* p);
 103     charT translate(charT c) const;
 104     charT translate_nocase(charT c) const;
 105     template <class ForwardIterator>
 106         string_type
 107         transform(ForwardIterator first, ForwardIterator last) const;
 108     template <class ForwardIterator>
 109         string_type
 110         transform_primary( ForwardIterator first, ForwardIterator last) const;
 111     template <class ForwardIterator>
 112         string_type
 113         lookup_collatename(ForwardIterator first, ForwardIterator last) const;
 114     template <class ForwardIterator>
 115         char_class_type
 116         lookup_classname(ForwardIterator first, ForwardIterator last,
 117                          bool icase = false) const;
 118     bool isctype(charT c, char_class_type f) const;
 119     int value(charT ch, int radix) const;
 120     locale_type imbue(locale_type l);
 121     locale_type getloc()const;
 122 };
 123
 124 template <class charT, class traits = regex_traits<charT>>
 125 class basic_regex
 126 {
 127 public:
 128     // types:
 129     typedef charT                               value_type;
 130     typedef traits                              traits_type;
 131     typedef typename traits::string_type        string_type;
 132     typedef regex_constants::syntax_option_type flag_type;
 133     typedef typename traits::locale_type        locale_type;
 134
 135     // constants:
 136     static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;
 137     static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
 138     static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;
 139     static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;
 140     static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
 141     static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;
 142     static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;
 143     static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;
 144     static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;
 145     static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;
 146
 147     // construct/copy/destroy:
 148     basic_regex();
 149     explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);
 150     basic_regex(const charT* p, size_t len, flag_type f = regex_constants::ECMAScript);
 151     basic_regex(const basic_regex&);
 152     basic_regex(basic_regex&&) noexcept;
 153     template <class ST, class SA>
 154         explicit basic_regex(const basic_string<charT, ST, SA>& p,
 155                              flag_type f = regex_constants::ECMAScript);
 156     template <class ForwardIterator>
 157         basic_regex(ForwardIterator first, ForwardIterator last,
 158                     flag_type f = regex_constants::ECMAScript);
 159     basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
 160
 161     ~basic_regex();
 162
 163     basic_regex& operator=(const basic_regex&);
 164     basic_regex& operator=(basic_regex&&) noexcept;
 165     basic_regex& operator=(const charT* ptr);
 166     basic_regex& operator=(initializer_list<charT> il);
 167     template <class ST, class SA>
 168         basic_regex& operator=(const basic_string<charT, ST, SA>& p);
 169
 170     // assign:
 171     basic_regex& assign(const basic_regex& that);
 172     basic_regex& assign(basic_regex&& that) noexcept;
 173     basic_regex& assign(const charT* ptr, flag_type f = regex_constants::ECMAScript);
 174     basic_regex& assign(const charT* p, size_t len, flag_type f);
 175     template <class string_traits, class A>
 176         basic_regex& assign(const basic_string<charT, string_traits, A>& s,
 177                             flag_type f = regex_constants::ECMAScript);
 178     template <class InputIterator>
 179         basic_regex& assign(InputIterator first, InputIterator last,
 180                             flag_type f = regex_constants::ECMAScript);
 181     basic_regex& assign(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
 182
 183     // const operations:
 184     unsigned mark_count() const;
 185     flag_type flags() const;
 186
 187     // locale:
 188     locale_type imbue(locale_type loc);
 189     locale_type getloc() const;
 190
 191     // swap:
 192     void swap(basic_regex&);
 193 };
 194
 195 template<class ForwardIterator>
 196 basic_regex(ForwardIterator, ForwardIterator,
 197             regex_constants::syntax_option_type = regex_constants::ECMAScript)
 198     -> basic_regex<typename iterator_traits<ForwardIterator>::value_type>; // C++17
 199
 200 typedef basic_regex<char>    regex;
 201 typedef basic_regex<wchar_t> wregex;
 202
 203 template <class charT, class traits>
 204     void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);
 205
 206 template <class BidirectionalIterator>
 207 class sub_match
 208     : public pair<BidirectionalIterator, BidirectionalIterator>
 209 {
 210 public:
 211     typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
 212     typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
 213     typedef BidirectionalIterator                                      iterator;
 214     typedef basic_string<value_type>                                string_type;
 215
 216     bool matched;
 217
 218     constexpr sub_match();
 219
 220     difference_type length() const;
 221     operator string_type() const;
 222     string_type str() const;
 223
 224     int compare(const sub_match& s) const;
 225     int compare(const string_type& s) const;
 226     int compare(const value_type* s) const;
 227 };
 228
 229 typedef sub_match<const char*>             csub_match;
 230 typedef sub_match<const wchar_t*>          wcsub_match;
 231 typedef sub_match<string::const_iterator>  ssub_match;
 232 typedef sub_match<wstring::const_iterator> wssub_match;
 233
 234 template <class BiIter>
 235     bool
 236     operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 237
 238 template <class BiIter>
 239     bool
 240     operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 241
 242 template <class BiIter>
 243     bool
 244     operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 245
 246 template <class BiIter>
 247     bool
 248     operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 249
 250 template <class BiIter>
 251     bool
 252     operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 253
 254 template <class BiIter>
 255     bool
 256     operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
 257
 258 template <class BiIter, class ST, class SA>
 259     bool
 260     operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 261                const sub_match<BiIter>& rhs);
 262
 263 template <class BiIter, class ST, class SA>
 264     bool
 265     operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 266                const sub_match<BiIter>& rhs);
 267
 268 template <class BiIter, class ST, class SA>
 269     bool
 270     operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 271               const sub_match<BiIter>& rhs);
 272
 273 template <class BiIter, class ST, class SA>
 274     bool
 275     operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 276               const sub_match<BiIter>& rhs);
 277
 278 template <class BiIter, class ST, class SA>
 279     bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 280                     const sub_match<BiIter>& rhs);
 281
 282 template <class BiIter, class ST, class SA>
 283     bool
 284     operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 285                const sub_match<BiIter>& rhs);
 286
 287 template <class BiIter, class ST, class SA>
 288     bool
 289     operator==(const sub_match<BiIter>& lhs,
 290                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 291
 292 template <class BiIter, class ST, class SA>
 293     bool
 294     operator!=(const sub_match<BiIter>& lhs,
 295                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 296
 297 template <class BiIter, class ST, class SA>
 298     bool
 299     operator<(const sub_match<BiIter>& lhs,
 300               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 301
 302 template <class BiIter, class ST, class SA>
 303     bool operator>(const sub_match<BiIter>& lhs,
 304                    const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 305
 306 template <class BiIter, class ST, class SA>
 307     bool
 308     operator>=(const sub_match<BiIter>& lhs,
 309                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 310
 311 template <class BiIter, class ST, class SA>
 312     bool
 313     operator<=(const sub_match<BiIter>& lhs,
 314                const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
 315
 316 template <class BiIter>
 317     bool
 318     operator==(typename iterator_traits<BiIter>::value_type const* lhs,
 319                const sub_match<BiIter>& rhs);
 320
 321 template <class BiIter>
 322     bool
 323     operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
 324                const sub_match<BiIter>& rhs);
 325
 326 template <class BiIter>
 327     bool
 328     operator<(typename iterator_traits<BiIter>::value_type const* lhs,
 329               const sub_match<BiIter>& rhs);
 330
 331 template <class BiIter>
 332     bool
 333     operator>(typename iterator_traits<BiIter>::value_type const* lhs,
 334               const sub_match<BiIter>& rhs);
 335
 336 template <class BiIter>
 337     bool
 338     operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
 339                const sub_match<BiIter>& rhs);
 340
 341 template <class BiIter>
 342     bool
 343     operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
 344                const sub_match<BiIter>& rhs);
 345
 346 template <class BiIter>
 347     bool
 348     operator==(const sub_match<BiIter>& lhs,
 349                typename iterator_traits<BiIter>::value_type const* rhs);
 350
 351 template <class BiIter>
 352     bool
 353     operator!=(const sub_match<BiIter>& lhs,
 354                typename iterator_traits<BiIter>::value_type const* rhs);
 355
 356 template <class BiIter>
 357     bool
 358     operator<(const sub_match<BiIter>& lhs,
 359               typename iterator_traits<BiIter>::value_type const* rhs);
 360
 361 template <class BiIter>
 362     bool
 363     operator>(const sub_match<BiIter>& lhs,
 364               typename iterator_traits<BiIter>::value_type const* rhs);
 365
 366 template <class BiIter>
 367     bool
 368     operator>=(const sub_match<BiIter>& lhs,
 369                typename iterator_traits<BiIter>::value_type const* rhs);
 370
 371 template <class BiIter>
 372     bool
 373     operator<=(const sub_match<BiIter>& lhs,
 374                typename iterator_traits<BiIter>::value_type const* rhs);
 375
 376 template <class BiIter>
 377     bool
 378     operator==(typename iterator_traits<BiIter>::value_type const& lhs,
 379                const sub_match<BiIter>& rhs);
 380
 381 template <class BiIter>
 382     bool
 383     operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
 384                const sub_match<BiIter>& rhs);
 385
 386 template <class BiIter>
 387     bool
 388     operator<(typename iterator_traits<BiIter>::value_type const& lhs,
 389               const sub_match<BiIter>& rhs);
 390
 391 template <class BiIter>
 392     bool
 393     operator>(typename iterator_traits<BiIter>::value_type const& lhs,
 394               const sub_match<BiIter>& rhs);
 395
 396 template <class BiIter>
 397     bool
 398     operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
 399                const sub_match<BiIter>& rhs);
 400
 401 template <class BiIter>
 402     bool
 403     operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
 404                const sub_match<BiIter>& rhs);
 405
 406 template <class BiIter>
 407     bool
 408     operator==(const sub_match<BiIter>& lhs,
 409                typename iterator_traits<BiIter>::value_type const& rhs);
 410
 411 template <class BiIter>
 412     bool
 413     operator!=(const sub_match<BiIter>& lhs,
 414                typename iterator_traits<BiIter>::value_type const& rhs);
 415
 416 template <class BiIter>
 417     bool
 418     operator<(const sub_match<BiIter>& lhs,
 419               typename iterator_traits<BiIter>::value_type const& rhs);
 420
 421 template <class BiIter>
 422     bool
 423     operator>(const sub_match<BiIter>& lhs,
 424               typename iterator_traits<BiIter>::value_type const& rhs);
 425
 426 template <class BiIter>
 427     bool
 428     operator>=(const sub_match<BiIter>& lhs,
 429                typename iterator_traits<BiIter>::value_type const& rhs);
 430
 431 template <class BiIter>
 432     bool
 433     operator<=(const sub_match<BiIter>& lhs,
 434                typename iterator_traits<BiIter>::value_type const& rhs);
 435
 436 template <class charT, class ST, class BiIter>
 437     basic_ostream<charT, ST>&
 438     operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);
 439
 440 template <class BidirectionalIterator,
 441           class Allocator = allocator<sub_match<BidirectionalIterator>>>
 442 class match_results
 443 {
 444 public:
 445     typedef sub_match<BidirectionalIterator>                  value_type;
 446     typedef const value_type&                                 const_reference;
 447     typedef value_type&                                       reference;
 448     typedef /implementation-defined/                          const_iterator;
 449     typedef const_iterator                                    iterator;
 450     typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
 451     typedef typename allocator_traits<Allocator>::size_type   size_type;
 452     typedef Allocator                                         allocator_type;
 453     typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;
 454     typedef basic_string<char_type>                           string_type;
 455
 456     // construct/copy/destroy:
 457     explicit match_results(const Allocator& a = Allocator());
 458     match_results(const match_results& m);
 459     match_results(match_results&& m) noexcept;
 460     match_results& operator=(const match_results& m);
 461     match_results& operator=(match_results&& m);
 462     ~match_results();
 463
 464     bool ready() const;
 465
 466     // size:
 467     size_type size() const;
 468     size_type max_size() const;
 469     bool empty() const;
 470
 471     // element access:
 472     difference_type length(size_type sub = 0) const;
 473     difference_type position(size_type sub = 0) const;
 474     string_type str(size_type sub = 0) const;
 475     const_reference operator[](size_type n) const;
 476
 477     const_reference prefix() const;
 478     const_reference suffix() const;
 479
 480     const_iterator begin() const;
 481     const_iterator end() const;
 482     const_iterator cbegin() const;
 483     const_iterator cend() const;
 484
 485     // format:
 486     template <class OutputIter>
 487         OutputIter
 488         format(OutputIter out, const char_type* fmt_first,
 489                const char_type* fmt_last,
 490                regex_constants::match_flag_type flags = regex_constants::format_default) const;
 491     template <class OutputIter, class ST, class SA>
 492         OutputIter
 493         format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
 494                regex_constants::match_flag_type flags = regex_constants::format_default) const;
 495     template <class ST, class SA>
 496         basic_string<char_type, ST, SA>
 497         format(const basic_string<char_type, ST, SA>& fmt,
 498                regex_constants::match_flag_type flags = regex_constants::format_default) const;
 499     string_type
 500         format(const char_type* fmt,
 501                regex_constants::match_flag_type flags = regex_constants::format_default) const;
 502
 503     // allocator:
 504     allocator_type get_allocator() const;
 505
 506     // swap:
 507     void swap(match_results& that);
 508 };
 509
 510 typedef match_results<const char*>             cmatch;
 511 typedef match_results<const wchar_t*>          wcmatch;
 512 typedef match_results<string::const_iterator>  smatch;
 513 typedef match_results<wstring::const_iterator> wsmatch;
 514
 515 template <class BidirectionalIterator, class Allocator>
 516     bool
 517     operator==(const match_results<BidirectionalIterator, Allocator>& m1,
 518                const match_results<BidirectionalIterator, Allocator>& m2);
 519
 520 template <class BidirectionalIterator, class Allocator>
 521     bool
 522     operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
 523                const match_results<BidirectionalIterator, Allocator>& m2);
 524
 525 template <class BidirectionalIterator, class Allocator>
 526     void
 527     swap(match_results<BidirectionalIterator, Allocator>& m1,
 528          match_results<BidirectionalIterator, Allocator>& m2);
 529
 530 template <class BidirectionalIterator, class Allocator, class charT, class traits>
 531     bool
 532     regex_match(BidirectionalIterator first, BidirectionalIterator last,
 533                 match_results<BidirectionalIterator, Allocator>& m,
 534                 const basic_regex<charT, traits>& e,
 535                 regex_constants::match_flag_type flags = regex_constants::match_default);
 536
 537 template <class BidirectionalIterator, class charT, class traits>
 538     bool
 539     regex_match(BidirectionalIterator first, BidirectionalIterator last,
 540                 const basic_regex<charT, traits>& e,
 541                 regex_constants::match_flag_type flags = regex_constants::match_default);
 542
 543 template <class charT, class Allocator, class traits>
 544     bool
 545     regex_match(const charT* str, match_results<const charT*, Allocator>& m,
 546                 const basic_regex<charT, traits>& e,
 547                 regex_constants::match_flag_type flags = regex_constants::match_default);
 548
 549 template <class ST, class SA, class Allocator, class charT, class traits>
 550     bool
 551     regex_match(const basic_string<charT, ST, SA>& s,
 552                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 553                 const basic_regex<charT, traits>& e,
 554                 regex_constants::match_flag_type flags = regex_constants::match_default);
 555
 556 template <class ST, class SA, class Allocator, class charT, class traits>
 557     bool
 558     regex_match(const basic_string<charT, ST, SA>&& s,
 559                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 560                 const basic_regex<charT, traits>& e,
 561                 regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14
 562
 563 template <class charT, class traits>
 564     bool
 565     regex_match(const charT* str, const basic_regex<charT, traits>& e,
 566                 regex_constants::match_flag_type flags = regex_constants::match_default);
 567
 568 template <class ST, class SA, class charT, class traits>
 569     bool
 570     regex_match(const basic_string<charT, ST, SA>& s,
 571                 const basic_regex<charT, traits>& e,
 572                 regex_constants::match_flag_type flags = regex_constants::match_default);
 573
 574 template <class BidirectionalIterator, class Allocator, class charT, class traits>
 575     bool
 576     regex_search(BidirectionalIterator first, BidirectionalIterator last,
 577                  match_results<BidirectionalIterator, Allocator>& m,
 578                  const basic_regex<charT, traits>& e,
 579                  regex_constants::match_flag_type flags = regex_constants::match_default);
 580
 581 template <class BidirectionalIterator, class charT, class traits>
 582     bool
 583     regex_search(BidirectionalIterator first, BidirectionalIterator last,
 584                  const basic_regex<charT, traits>& e,
 585                  regex_constants::match_flag_type flags = regex_constants::match_default);
 586
 587 template <class charT, class Allocator, class traits>
 588     bool
 589     regex_search(const charT* str, match_results<const charT*, Allocator>& m,
 590                  const basic_regex<charT, traits>& e,
 591                  regex_constants::match_flag_type flags = regex_constants::match_default);
 592
 593 template <class charT, class traits>
 594     bool
 595     regex_search(const charT* str, const basic_regex<charT, traits>& e,
 596                  regex_constants::match_flag_type flags = regex_constants::match_default);
 597
 598 template <class ST, class SA, class charT, class traits>
 599     bool
 600     regex_search(const basic_string<charT, ST, SA>& s,
 601                  const basic_regex<charT, traits>& e,
 602                  regex_constants::match_flag_type flags = regex_constants::match_default);
 603
 604 template <class ST, class SA, class Allocator, class charT, class traits>
 605     bool
 606     regex_search(const basic_string<charT, ST, SA>& s,
 607                  match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 608                  const basic_regex<charT, traits>& e,
 609                  regex_constants::match_flag_type flags = regex_constants::match_default);
 610
 611 template <class ST, class SA, class Allocator, class charT, class traits>
 612     bool
 613     regex_search(const basic_string<charT, ST, SA>&& s,
 614                  match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 615                  const basic_regex<charT, traits>& e,
 616                  regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14
 617
 618 template <class OutputIterator, class BidirectionalIterator,
 619           class traits, class charT, class ST, class SA>
 620     OutputIterator
 621     regex_replace(OutputIterator out,
 622                   BidirectionalIterator first, BidirectionalIterator last,
 623                   const basic_regex<charT, traits>& e,
 624                   const basic_string<charT, ST, SA>& fmt,
 625                   regex_constants::match_flag_type flags = regex_constants::match_default);
 626
 627 template <class OutputIterator, class BidirectionalIterator,
 628           class traits, class charT>
 629     OutputIterator
 630     regex_replace(OutputIterator out,
 631                   BidirectionalIterator first, BidirectionalIterator last,
 632                   const basic_regex<charT, traits>& e, const charT* fmt,
 633                   regex_constants::match_flag_type flags = regex_constants::match_default);
 634
 635 template <class traits, class charT, class ST, class SA, class FST, class FSA>>
 636     basic_string<charT, ST, SA>
 637     regex_replace(const basic_string<charT, ST, SA>& s,
 638                   const basic_regex<charT, traits>& e,
 639                   const basic_string<charT, FST, FSA>& fmt,
 640                   regex_constants::match_flag_type flags = regex_constants::match_default);
 641
 642 template <class traits, class charT, class ST, class SA>
 643     basic_string<charT, ST, SA>
 644     regex_replace(const basic_string<charT, ST, SA>& s,
 645                   const basic_regex<charT, traits>& e, const charT* fmt,
 646                   regex_constants::match_flag_type flags = regex_constants::match_default);
 647
 648 template <class traits, class charT, class ST, class SA>
 649     basic_string<charT>
 650     regex_replace(const charT* s,
 651                   const basic_regex<charT, traits>& e,
 652                   const basic_string<charT, ST, SA>& fmt,
 653                   regex_constants::match_flag_type flags = regex_constants::match_default);
 654
 655 template <class traits, class charT>
 656     basic_string<charT>
 657     regex_replace(const charT* s,
 658                   const basic_regex<charT, traits>& e,
 659                   const charT* fmt,
 660                   regex_constants::match_flag_type flags = regex_constants::match_default);
 661
 662 template <class BidirectionalIterator,
 663           class charT = typename iterator_traits< BidirectionalIterator>::value_type,
 664           class traits = regex_traits<charT>>
 665 class regex_iterator
 666 {
 667 public:
 668     typedef basic_regex<charT, traits>           regex_type;
 669     typedef match_results<BidirectionalIterator> value_type;
 670     typedef ptrdiff_t                            difference_type;
 671     typedef const value_type*                    pointer;
 672     typedef const value_type&                    reference;
 673     typedef forward_iterator_tag                 iterator_category;
 674
 675     regex_iterator();
 676     regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
 677                    const regex_type& re,
 678                    regex_constants::match_flag_type m = regex_constants::match_default);
 679     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
 680                    const regex_type&& __re,
 681                    regex_constants::match_flag_type __m
 682                                      = regex_constants::match_default) = delete; // C++14
 683     regex_iterator(const regex_iterator&);
 684     regex_iterator& operator=(const regex_iterator&);
 685
 686     bool operator==(const regex_iterator&) const;
 687     bool operator!=(const regex_iterator&) const;
 688
 689     const value_type& operator*() const;
 690     const value_type* operator->() const;
 691
 692     regex_iterator& operator++();
 693     regex_iterator operator++(int);
 694 };
 695
 696 typedef regex_iterator<const char*>             cregex_iterator;
 697 typedef regex_iterator<const wchar_t*>          wcregex_iterator;
 698 typedef regex_iterator<string::const_iterator>  sregex_iterator;
 699 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
 700
 701 template <class BidirectionalIterator,
 702           class charT = typename iterator_traits< BidirectionalIterator>::value_type,
 703           class traits = regex_traits<charT>>
 704 class regex_token_iterator
 705 {
 706 public:
 707     typedef basic_regex<charT, traits>       regex_type;
 708     typedef sub_match<BidirectionalIterator> value_type;
 709     typedef ptrdiff_t                        difference_type;
 710     typedef const value_type*                pointer;
 711     typedef const value_type&                reference;
 712     typedef forward_iterator_tag             iterator_category;
 713
 714     regex_token_iterator();
 715     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 716                          const regex_type& re, int submatch = 0,
 717                          regex_constants::match_flag_type m = regex_constants::match_default);
 718     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 719                          const regex_type&& re, int submatch = 0,
 720                          regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
 721     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 722                          const regex_type& re, const vector<int>& submatches,
 723                          regex_constants::match_flag_type m = regex_constants::match_default);
 724     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 725                          const regex_type&& re, const vector<int>& submatches,
 726                          regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
 727     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 728                          const regex_type& re, initializer_list<int> submatches,
 729                          regex_constants::match_flag_type m = regex_constants::match_default);
 730     regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 731                          const regex_type&& re, initializer_list<int> submatches,
 732                          regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
 733     template <size_t N>
 734         regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 735                              const regex_type& re, const int (&submatches)[N],
 736                              regex_constants::match_flag_type m = regex_constants::match_default);
 737     template <size_t N>
 738         regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 739                              const regex_type& re, const int (&submatches)[N],
 740                              regex_constants::match_flag_type m = regex_constants::match_default) = delete // C++14;
 741     regex_token_iterator(const regex_token_iterator&);
 742     regex_token_iterator& operator=(const regex_token_iterator&);
 743
 744     bool operator==(const regex_token_iterator&) const;
 745     bool operator!=(const regex_token_iterator&) const;
 746
 747     const value_type& operator*() const;
 748     const value_type* operator->() const;
 749
 750     regex_token_iterator& operator++();
 751     regex_token_iterator operator++(int);
 752 };
 753
 754 typedef regex_token_iterator<const char*>             cregex_token_iterator;
 755 typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
 756 typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
 757 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
 758
 759 } // std
 760 */
 761
 762 #include <__config>
 763 #include <stdexcept>
 764 #include <__locale>
 765 #include <initializer_list>
 766 #include <utility>
 767 #include <iterator>
 768 #include <string>
 769 #include <memory>
 770 #include <vector>
 771 #include <deque>
 772
 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         // When there's at least one of __neg_chars_ and __neg_mask_, the set
2418         // of "__found" chars is
2419         //   union(complement(union(__neg_chars_, __neg_mask_)),
2420         //         other cases...)
2421         //
2422         // It doesn't make sense to check this when there are no __neg_chars_
2423         // and no __neg_mask_.
2424         if (!(__neg_mask_ == 0 && __neg_chars_.empty()))
2425         {
2426             const bool __in_neg_mask = __traits_.isctype(__ch, __neg_mask_);
2427           const bool __in_neg_chars =
2428               std::find(__neg_chars_.begin(), __neg_chars_.end(), __ch) !=
2429               __neg_chars_.end();
2430           if (!(__in_neg_mask || __in_neg_chars))
2431           {
2432             __found = true;
2433             goto __exit;
2434           }
2435         }
2436         if (!__ranges_.empty())
2437         {
2438             string_type __s2 = __collate_ ?
2439                                    __traits_.transform(&__ch, &__ch + 1) :
2440                                    string_type(1, __ch);
2441             for (size_t __i = 0; __i < __ranges_.size(); ++__i)
2442             {
2443                 if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second)
2444                 {
2445                     __found = true;
2446                     goto __exit;
2447                 }
2448             }
2449         }
2450         if (!__equivalences_.empty())
2451         {
2452             string_type __s2 = __traits_.transform_primary(&__ch, &__ch + 1);
2453             for (size_t __i = 0; __i < __equivalences_.size(); ++__i)
2454             {
2455                 if (__s2 == __equivalences_[__i])
2456                 {
2457                     __found = true;
2458                     goto __exit;
2459                 }
2460             }
2461         }
2462         if (__traits_.isctype(__ch, __mask_))
2463         {
2464             __found = true;
2465             goto __exit;
2466         }
2467     }
2468     else
2469         __found = __negate_;  // force reject
2470 __exit:
2471     if (__found != __negate_)
2472     {
2473         __s.__do_ = __state::__accept_and_consume;
2474         __s.__current_ += __consumed;
2475         __s.__node_ = this->first();
2476     }
2477     else
2478     {
2479         __s.__do_ = __state::__reject;
2480         __s.__node_ = nullptr;
2481     }
2482 }
2483
2484 template <class _CharT, class _Traits> class __lookahead;
2485
2486 template <class _CharT, class _Traits = regex_traits<_CharT> >
2487 class _LIBCPP_TEMPLATE_VIS basic_regex
2488 {
2489 public:
2490     // types:
2491     typedef _CharT                              value_type;
2492     typedef _Traits                             traits_type;
2493     typedef typename _Traits::string_type       string_type;
2494     typedef regex_constants::syntax_option_type flag_type;
2495     typedef typename _Traits::locale_type       locale_type;
2496
2497 private:
2498     _Traits   __traits_;
2499     flag_type __flags_;
2500     unsigned __marked_count_;
2501     unsigned __loop_count_;
2502     int __open_count_;
2503     shared_ptr<__empty_state<_CharT> > __start_;
2504     __owns_one_state<_CharT>* __end_;
2505
2506     typedef _VSTD::__state<_CharT> __state;
2507     typedef _VSTD::__node<_CharT> __node;
2508
2509 public:
2510     // constants:
2511     static const regex_constants::syntax_option_type icase = regex_constants::icase;
2512     static const regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
2513     static const regex_constants::syntax_option_type optimize = regex_constants::optimize;
2514     static const regex_constants::syntax_option_type collate = regex_constants::collate;
2515     static const regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
2516     static const regex_constants::syntax_option_type basic = regex_constants::basic;
2517     static const regex_constants::syntax_option_type extended = regex_constants::extended;
2518     static const regex_constants::syntax_option_type awk = regex_constants::awk;
2519     static const regex_constants::syntax_option_type grep = regex_constants::grep;
2520     static const regex_constants::syntax_option_type egrep = regex_constants::egrep;
2521
2522     // construct/copy/destroy:
2523     _LIBCPP_INLINE_VISIBILITY
2524     basic_regex()
2525         : __flags_(), __marked_count_(0), __loop_count_(0), __open_count_(0),
2526           __end_(0)
2527         {}
2528     _LIBCPP_INLINE_VISIBILITY
2529     explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
2530         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2531           __end_(0)
2532         {__parse(__p, __p + __traits_.length(__p));}
2533     _LIBCPP_INLINE_VISIBILITY
2534     basic_regex(const value_type* __p, size_t __len, flag_type __f = regex_constants::ECMAScript)
2535         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2536           __end_(0)
2537         {__parse(__p, __p + __len);}
2538 //     basic_regex(const basic_regex&) = default;
2539 //     basic_regex(basic_regex&&) = default;
2540     template <class _ST, class _SA>
2541         _LIBCPP_INLINE_VISIBILITY
2542         explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
2543                              flag_type __f = regex_constants::ECMAScript)
2544         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2545           __end_(0)
2546         {__parse(__p.begin(), __p.end());}
2547     template <class _ForwardIterator>
2548         _LIBCPP_INLINE_VISIBILITY
2549         basic_regex(_ForwardIterator __first, _ForwardIterator __last,
2550                     flag_type __f = regex_constants::ECMAScript)
2551         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2552           __end_(0)
2553         {__parse(__first, __last);}
2554 #ifndef _LIBCPP_CXX03_LANG
2555     _LIBCPP_INLINE_VISIBILITY
2556     basic_regex(initializer_list<value_type> __il,
2557                 flag_type __f = regex_constants::ECMAScript)
2558         : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2559           __end_(0)
2560         {__parse(__il.begin(), __il.end());}
2561 #endif  // _LIBCPP_CXX03_LANG
2562
2563 //    ~basic_regex() = default;
2564
2565 //     basic_regex& operator=(const basic_regex&) = default;
2566 //     basic_regex& operator=(basic_regex&&) = default;
2567     _LIBCPP_INLINE_VISIBILITY
2568     basic_regex& operator=(const value_type* __p)
2569         {return assign(__p);}
2570 #ifndef _LIBCPP_CXX03_LANG
2571     _LIBCPP_INLINE_VISIBILITY
2572     basic_regex& operator=(initializer_list<value_type> __il)
2573         {return assign(__il);}
2574 #endif  // _LIBCPP_CXX03_LANG
2575     template <class _ST, class _SA>
2576         _LIBCPP_INLINE_VISIBILITY
2577         basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p)
2578         {return assign(__p);}
2579
2580     // assign:
2581     _LIBCPP_INLINE_VISIBILITY
2582     basic_regex& assign(const basic_regex& __that)
2583         {return *this = __that;}
2584 #ifndef _LIBCPP_CXX03_LANG
2585     _LIBCPP_INLINE_VISIBILITY
2586     basic_regex& assign(basic_regex&& __that) _NOEXCEPT
2587         {return *this = _VSTD::move(__that);}
2588 #endif
2589     _LIBCPP_INLINE_VISIBILITY
2590     basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
2591         {return assign(__p, __p + __traits_.length(__p), __f);}
2592     _LIBCPP_INLINE_VISIBILITY
2593     basic_regex& assign(const value_type* __p, size_t __len, flag_type __f)
2594         {return assign(__p, __p + __len, __f);}
2595     template <class _ST, class _SA>
2596         _LIBCPP_INLINE_VISIBILITY
2597         basic_regex& assign(const basic_string<value_type, _ST, _SA>& __s,
2598                             flag_type __f = regex_constants::ECMAScript)
2599             {return assign(__s.begin(), __s.end(), __f);}
2600
2601     template <class _InputIterator>
2602         _LIBCPP_INLINE_VISIBILITY
2603         typename enable_if
2604         <
2605              __is_input_iterator  <_InputIterator>::value &&
2606             !__is_forward_iterator<_InputIterator>::value,
2607             basic_regex&
2608         >::type
2609         assign(_InputIterator __first, _InputIterator __last,
2610                             flag_type __f = regex_constants::ECMAScript)
2611         {
2612             basic_string<_CharT> __t(__first, __last);
2613             return assign(__t.begin(), __t.end(), __f);
2614         }
2615
2616 private:
2617     _LIBCPP_INLINE_VISIBILITY
2618     void __member_init(flag_type __f)
2619     {
2620         __flags_ = __f;
2621         __marked_count_ = 0;
2622         __loop_count_ = 0;
2623         __open_count_ = 0;
2624         __end_ = nullptr;
2625     }
2626 public:
2627
2628     template <class _ForwardIterator>
2629         _LIBCPP_INLINE_VISIBILITY
2630         typename enable_if
2631         <
2632             __is_forward_iterator<_ForwardIterator>::value,
2633             basic_regex&
2634         >::type
2635         assign(_ForwardIterator __first, _ForwardIterator __last,
2636                             flag_type __f = regex_constants::ECMAScript)
2637         {
2638             return assign(basic_regex(__first, __last, __f));
2639         }
2640
2641 #ifndef _LIBCPP_CXX03_LANG
2642
2643     _LIBCPP_INLINE_VISIBILITY
2644     basic_regex& assign(initializer_list<value_type> __il,
2645                         flag_type __f = regex_constants::ECMAScript)
2646         {return assign(__il.begin(), __il.end(), __f);}
2647
2648 #endif  // _LIBCPP_CXX03_LANG
2649
2650     // const operations:
2651     _LIBCPP_INLINE_VISIBILITY
2652     unsigned mark_count() const {return __marked_count_;}
2653     _LIBCPP_INLINE_VISIBILITY
2654     flag_type flags() const {return __flags_;}
2655
2656     // locale:
2657     _LIBCPP_INLINE_VISIBILITY
2658     locale_type imbue(locale_type __loc)
2659     {
2660         __member_init(ECMAScript);
2661         __start_.reset();
2662         return __traits_.imbue(__loc);
2663     }
2664     _LIBCPP_INLINE_VISIBILITY
2665     locale_type getloc() const {return __traits_.getloc();}
2666
2667     // swap:
2668     void swap(basic_regex& __r);
2669
2670 private:
2671     _LIBCPP_INLINE_VISIBILITY
2672     unsigned __loop_count() const {return __loop_count_;}
2673
2674     template <class _ForwardIterator>
2675         _ForwardIterator
2676         __parse(_ForwardIterator __first, _ForwardIterator __last);
2677     template <class _ForwardIterator>
2678         _ForwardIterator
2679         __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2680     template <class _ForwardIterator>
2681         _ForwardIterator
2682         __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
2683     template <class _ForwardIterator>
2684         _ForwardIterator
2685         __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
2686     template <class _ForwardIterator>
2687         _ForwardIterator
2688         __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
2689     template <class _ForwardIterator>
2690         _ForwardIterator
2691         __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
2692     template <class _ForwardIterator>
2693         _ForwardIterator
2694         __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
2695     template <class _ForwardIterator>
2696         _ForwardIterator
2697         __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
2698     template <class _ForwardIterator>
2699         _ForwardIterator
2700         __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
2701     template <class _ForwardIterator>
2702         _ForwardIterator
2703         __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
2704     template <class _ForwardIterator>
2705         _ForwardIterator
2706         __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
2707     template <class _ForwardIterator>
2708         _ForwardIterator
2709         __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2710     template <class _ForwardIterator>
2711         _ForwardIterator
2712         __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2713     template <class _ForwardIterator>
2714         _ForwardIterator
2715         __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2716                                __owns_one_state<_CharT>* __s,
2717                                unsigned __mexp_begin, unsigned __mexp_end);
2718     template <class _ForwardIterator>
2719         _ForwardIterator
2720         __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2721                                 __owns_one_state<_CharT>* __s,
2722                                 unsigned __mexp_begin, unsigned __mexp_end);
2723     template <class _ForwardIterator>
2724         _ForwardIterator
2725         __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
2726     template <class _ForwardIterator>
2727         _ForwardIterator
2728         __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last,
2729                             __bracket_expression<_CharT, _Traits>* __ml);
2730     template <class _ForwardIterator>
2731         _ForwardIterator
2732         __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last,
2733                                 __bracket_expression<_CharT, _Traits>* __ml);
2734     template <class _ForwardIterator>
2735         _ForwardIterator
2736         __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last,
2737                                   __bracket_expression<_CharT, _Traits>* __ml);
2738     template <class _ForwardIterator>
2739         _ForwardIterator
2740         __parse_character_class(_ForwardIterator __first, _ForwardIterator __last,
2741                                 __bracket_expression<_CharT, _Traits>* __ml);
2742     template <class _ForwardIterator>
2743         _ForwardIterator
2744         __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last,
2745                                  basic_string<_CharT>& __col_sym);
2746     template <class _ForwardIterator>
2747         _ForwardIterator
2748         __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
2749     template <class _ForwardIterator>
2750         _ForwardIterator
2751         __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2752     template <class _ForwardIterator>
2753         _ForwardIterator
2754         __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
2755     template <class _ForwardIterator>
2756         _ForwardIterator
2757         __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
2758     template <class _ForwardIterator>
2759         _ForwardIterator
2760         __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
2761     template <class _ForwardIterator>
2762         _ForwardIterator
2763         __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2764     template <class _ForwardIterator>
2765         _ForwardIterator
2766         __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2767     template <class _ForwardIterator>
2768         _ForwardIterator
2769         __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);
2770     template <class _ForwardIterator>
2771         _ForwardIterator
2772         __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);
2773     template <class _ForwardIterator>
2774         _ForwardIterator
2775         __parse_term(_ForwardIterator __first, _ForwardIterator __last);
2776     template <class _ForwardIterator>
2777         _ForwardIterator
2778         __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);
2779     template <class _ForwardIterator>
2780         _ForwardIterator
2781         __parse_atom(_ForwardIterator __first, _ForwardIterator __last);
2782     template <class _ForwardIterator>
2783         _ForwardIterator
2784         __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);
2785     template <class _ForwardIterator>
2786         _ForwardIterator
2787         __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);
2788     template <class _ForwardIterator>
2789         _ForwardIterator
2790         __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);
2791     template <class _ForwardIterator>
2792         _ForwardIterator
2793         __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last,
2794                                  basic_string<_CharT>* __str = nullptr);
2795     template <class _ForwardIterator>
2796         _ForwardIterator
2797         __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);
2798     template <class _ForwardIterator>
2799         _ForwardIterator
2800         __parse_grep(_ForwardIterator __first, _ForwardIterator __last);
2801     template <class _ForwardIterator>
2802         _ForwardIterator
2803         __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);
2804     template <class _ForwardIterator>
2805         _ForwardIterator
2806         __parse_class_escape(_ForwardIterator __first, _ForwardIterator __last,
2807                           basic_string<_CharT>& __str,
2808                           __bracket_expression<_CharT, _Traits>* __ml);
2809     template <class _ForwardIterator>
2810         _ForwardIterator
2811         __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last,
2812                           basic_string<_CharT>* __str = nullptr);
2813
2814     _LIBCPP_INLINE_VISIBILITY
2815     void __push_l_anchor();
2816     void __push_r_anchor();
2817     void __push_match_any();
2818     void __push_match_any_but_newline();
2819     _LIBCPP_INLINE_VISIBILITY
2820     void __push_greedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
2821                                   unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
2822         {__push_loop(__min, numeric_limits<size_t>::max(), __s,
2823                      __mexp_begin, __mexp_end);}
2824     _LIBCPP_INLINE_VISIBILITY
2825     void __push_nongreedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
2826                                   unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
2827         {__push_loop(__min, numeric_limits<size_t>::max(), __s,
2828                      __mexp_begin, __mexp_end, false);}
2829     void __push_loop(size_t __min, size_t __max, __owns_one_state<_CharT>* __s,
2830                      size_t __mexp_begin = 0, size_t __mexp_end = 0,
2831                      bool __greedy = true);
2832     __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);
2833     void __push_char(value_type __c);
2834     void __push_back_ref(int __i);
2835     void __push_alternation(__owns_one_state<_CharT>* __sa,
2836                             __owns_one_state<_CharT>* __sb);
2837     void __push_begin_marked_subexpression();
2838     void __push_end_marked_subexpression(unsigned);
2839     void __push_empty();
2840     void __push_word_boundary(bool);
2841     void __push_lookahead(const basic_regex&, bool, unsigned);
2842
2843     template <class _Allocator>
2844         bool
2845         __search(const _CharT* __first, const _CharT* __last,
2846                  match_results<const _CharT*, _Allocator>& __m,
2847                  regex_constants::match_flag_type __flags) const;
2848
2849     template <class _Allocator>
2850         bool
2851         __match_at_start(const _CharT* __first, const _CharT* __last,
2852                  match_results<const _CharT*, _Allocator>& __m,
2853                  regex_constants::match_flag_type __flags, bool) const;
2854     template <class _Allocator>
2855         bool
2856         __match_at_start_ecma(const _CharT* __first, const _CharT* __last,
2857                  match_results<const _CharT*, _Allocator>& __m,
2858                  regex_constants::match_flag_type __flags, bool) const;
2859     template <class _Allocator>
2860         bool
2861         __match_at_start_posix_nosubs(const _CharT* __first, const _CharT* __last,
2862                  match_results<const _CharT*, _Allocator>& __m,
2863                  regex_constants::match_flag_type __flags, bool) const;
2864     template <class _Allocator>
2865         bool
2866         __match_at_start_posix_subs(const _CharT* __first, const _CharT* __last,
2867                  match_results<const _CharT*, _Allocator>& __m,
2868                  regex_constants::match_flag_type __flags, bool) const;
2869
2870     template <class _Bp, class _Ap, class _Cp, class _Tp>
2871     friend
2872     bool
2873     regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
2874                  regex_constants::match_flag_type);
2875
2876     template <class _Ap, class _Cp, class _Tp>
2877     friend
2878     bool
2879     regex_search(const _Cp*, const _Cp*, match_results<const _Cp*, _Ap>&,
2880                  const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2881
2882     template <class _Bp, class _Cp, class _Tp>
2883     friend
2884     bool
2885     regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&,
2886                  regex_constants::match_flag_type);
2887
2888     template <class _Cp, class _Tp>
2889     friend
2890     bool
2891     regex_search(const _Cp*, const _Cp*,
2892                  const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2893
2894     template <class _Cp, class _Ap, class _Tp>
2895     friend
2896     bool
2897     regex_search(const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&,
2898                  regex_constants::match_flag_type);
2899
2900     template <class _ST, class _SA, class _Cp, class _Tp>
2901     friend
2902     bool
2903     regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2904                  const basic_regex<_Cp, _Tp>& __e,
2905                  regex_constants::match_flag_type __flags);
2906
2907     template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
2908     friend
2909     bool
2910     regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2911                  match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
2912                  const basic_regex<_Cp, _Tp>& __e,
2913                  regex_constants::match_flag_type __flags);
2914
2915     template <class _Iter, class _Ap, class _Cp, class _Tp>
2916     friend
2917     bool
2918     regex_search(__wrap_iter<_Iter> __first,
2919                  __wrap_iter<_Iter> __last,
2920                  match_results<__wrap_iter<_Iter>, _Ap>& __m,
2921                  const basic_regex<_Cp, _Tp>& __e,
2922                  regex_constants::match_flag_type __flags);
2923
2924     template <class, class> friend class __lookahead;
2925 };
2926
2927 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2928 template <class _ForwardIterator,
2929           class = typename enable_if<__is_forward_iterator<_ForwardIterator>::value, nullptr_t>::type
2930 >
2931 basic_regex(_ForwardIterator, _ForwardIterator,
2932             regex_constants::syntax_option_type = regex_constants::ECMAScript)
2933     -> basic_regex<typename iterator_traits<_ForwardIterator>::value_type>;
2934 #endif
2935
2936 template <class _CharT, class _Traits>
2937     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;
2938 template <class _CharT, class _Traits>
2939     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;
2940 template <class _CharT, class _Traits>
2941     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;
2942 template <class _CharT, class _Traits>
2943     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;
2944 template <class _CharT, class _Traits>
2945     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;
2946 template <class _CharT, class _Traits>
2947     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;
2948 template <class _CharT, class _Traits>
2949     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;
2950 template <class _CharT, class _Traits>
2951     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;
2952 template <class _CharT, class _Traits>
2953     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;
2954 template <class _CharT, class _Traits>
2955     const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;
2956
2957 template <class _CharT, class _Traits>
2958 void
2959 basic_regex<_CharT, _Traits>::swap(basic_regex& __r)
2960 {
2961     using _VSTD::swap;
2962     swap(__traits_, __r.__traits_);
2963     swap(__flags_, __r.__flags_);
2964     swap(__marked_count_, __r.__marked_count_);
2965     swap(__loop_count_, __r.__loop_count_);
2966     swap(__open_count_, __r.__open_count_);
2967     swap(__start_, __r.__start_);
2968     swap(__end_, __r.__end_);
2969 }
2970
2971 template <class _CharT, class _Traits>
2972 inline _LIBCPP_INLINE_VISIBILITY
2973 void
2974 swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y)
2975 {
2976     return __x.swap(__y);
2977 }
2978
2979 // __lookahead
2980
2981 template <class _CharT, class _Traits>
2982 class __lookahead
2983     : public __owns_one_state<_CharT>
2984 {
2985     typedef __owns_one_state<_CharT> base;
2986
2987     basic_regex<_CharT, _Traits> __exp_;
2988     unsigned __mexp_;
2989     bool __invert_;
2990
2991     __lookahead(const __lookahead&);
2992     __lookahead& operator=(const __lookahead&);
2993 public:
2994     typedef _VSTD::__state<_CharT> __state;
2995
2996     _LIBCPP_INLINE_VISIBILITY
2997     __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
2998         : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}
2999
3000     virtual void __exec(__state&) const;
3001 };
3002
3003 template <class _CharT, class _Traits>
3004 void
3005 __lookahead<_CharT, _Traits>::__exec(__state& __s) const
3006 {
3007     match_results<const _CharT*> __m;
3008     __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);
3009     bool __matched = __exp_.__match_at_start_ecma(
3010         __s.__current_, __s.__last_,
3011         __m,
3012         (__s.__flags_ | regex_constants::match_continuous) &
3013         ~regex_constants::__full_match,
3014         __s.__at_first_ && __s.__current_ == __s.__first_);
3015     if (__matched != __invert_)
3016     {
3017         __s.__do_ = __state::__accept_but_not_consume;
3018         __s.__node_ = this->first();
3019         for (unsigned __i = 1; __i < __m.size(); ++__i) {
3020             __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
3021         }
3022     }
3023     else
3024     {
3025         __s.__do_ = __state::__reject;
3026         __s.__node_ = nullptr;
3027     }
3028 }
3029
3030 template <class _CharT, class _Traits>
3031 template <class _ForwardIterator>
3032 _ForwardIterator
3033 basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
3034                                       _ForwardIterator __last)
3035 {
3036     {
3037         unique_ptr<__node> __h(new __end_state<_CharT>);
3038         __start_.reset(new __empty_state<_CharT>(__h.get()));
3039         __h.release();
3040         __end_ = __start_.get();
3041     }
3042     switch (__flags_ & 0x1F0)
3043     {
3044     case ECMAScript:
3045         __first = __parse_ecma_exp(__first, __last);
3046         break;
3047     case basic:
3048         __first = __parse_basic_reg_exp(__first, __last);
3049         break;
3050     case extended:
3051     case awk:
3052         __first = __parse_extended_reg_exp(__first, __last);
3053         break;
3054     case grep:
3055         __first = __parse_grep(__first, __last);
3056         break;
3057     case egrep:
3058         __first = __parse_egrep(__first, __last);
3059         break;
3060     default:
3061         __throw_regex_error<regex_constants::__re_err_grammar>();
3062     }
3063     return __first;
3064 }
3065
3066 template <class _CharT, class _Traits>
3067 template <class _ForwardIterator>
3068 _ForwardIterator
3069 basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
3070                                                     _ForwardIterator __last)
3071 {
3072     if (__first != __last)
3073     {
3074         if (*__first == '^')
3075         {
3076             __push_l_anchor();
3077             ++__first;
3078         }
3079         if (__first != __last)
3080         {
3081             __first = __parse_RE_expression(__first, __last);
3082             if (__first != __last)
3083             {
3084                 _ForwardIterator __temp = _VSTD::next(__first);
3085                 if (__temp == __last && *__first == '$')
3086                 {
3087                     __push_r_anchor();
3088                     ++__first;
3089                 }
3090             }
3091         }
3092         if (__first != __last)
3093             __throw_regex_error<regex_constants::__re_err_empty>();
3094     }
3095     return __first;
3096 }
3097
3098 template <class _CharT, class _Traits>
3099 template <class _ForwardIterator>
3100 _ForwardIterator
3101 basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
3102                                                        _ForwardIterator __last)
3103 {
3104     __owns_one_state<_CharT>* __sa = __end_;
3105     _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
3106     if (__temp == __first)
3107         __throw_regex_error<regex_constants::__re_err_empty>();
3108     __first = __temp;
3109     while (__first != __last && *__first == '|')
3110     {
3111         __owns_one_state<_CharT>* __sb = __end_;
3112         __temp = __parse_ERE_branch(++__first, __last);
3113         if (__temp == __first)
3114             __throw_regex_error<regex_constants::__re_err_empty>();
3115         __push_alternation(__sa, __sb);
3116         __first = __temp;
3117     }
3118     return __first;
3119 }
3120
3121 template <class _CharT, class _Traits>
3122 template <class _ForwardIterator>
3123 _ForwardIterator
3124 basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
3125                                                  _ForwardIterator __last)
3126 {
3127     _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
3128     if (__temp == __first)
3129         __throw_regex_error<regex_constants::__re_err_empty>();
3130     do
3131     {
3132         __first = __temp;
3133         __temp = __parse_ERE_expression(__first, __last);
3134     } while (__temp != __first);
3135     return __first;
3136 }
3137
3138 template <class _CharT, class _Traits>
3139 template <class _ForwardIterator>
3140 _ForwardIterator
3141 basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
3142                                                      _ForwardIterator __last)
3143 {
3144     __owns_one_state<_CharT>* __e = __end_;
3145     unsigned __mexp_begin = __marked_count_;
3146     _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
3147     if (__temp == __first && __temp != __last)
3148     {
3149         switch (*__temp)
3150         {
3151         case '^':
3152             __push_l_anchor();
3153             ++__temp;
3154             break;
3155         case '$':
3156             __push_r_anchor();
3157             ++__temp;
3158             break;
3159         case '(':
3160             __push_begin_marked_subexpression();
3161             unsigned __temp_count = __marked_count_;
3162             ++__open_count_;
3163             __temp = __parse_extended_reg_exp(++__temp, __last);
3164             if (__temp == __last || *__temp != ')')
3165                 __throw_regex_error<regex_constants::error_paren>();
3166             __push_end_marked_subexpression(__temp_count);
3167             --__open_count_;
3168             ++__temp;
3169             break;
3170         }
3171     }
3172     if (__temp != __first)
3173         __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin+1,
3174                                          __marked_count_+1);
3175     __first = __temp;
3176     return __first;
3177 }
3178
3179 template <class _CharT, class _Traits>
3180 template <class _ForwardIterator>
3181 _ForwardIterator
3182 basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
3183                                                     _ForwardIterator __last)
3184 {
3185     while (true)
3186     {
3187         _ForwardIterator __temp = __parse_simple_RE(__first, __last);
3188         if (__temp == __first)
3189             break;
3190         __first = __temp;
3191     }
3192     return __first;
3193 }
3194
3195 template <class _CharT, class _Traits>
3196 template <class _ForwardIterator>
3197 _ForwardIterator
3198 basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
3199                                                 _ForwardIterator __last)
3200 {
3201     if (__first != __last)
3202     {
3203         __owns_one_state<_CharT>* __e = __end_;
3204         unsigned __mexp_begin = __marked_count_;
3205         _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
3206         if (__temp != __first)
3207             __first = __parse_RE_dupl_symbol(__temp, __last, __e,
3208                                              __mexp_begin+1, __marked_count_+1);
3209     }
3210     return __first;
3211 }
3212
3213 template <class _CharT, class _Traits>
3214 template <class _ForwardIterator>
3215 _ForwardIterator
3216 basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
3217                                                  _ForwardIterator __last)
3218 {
3219     _ForwardIterator __temp = __first;
3220     __first = __parse_one_char_or_coll_elem_RE(__first, __last);
3221     if (__temp == __first)
3222     {
3223         __temp = __parse_Back_open_paren(__first, __last);
3224         if (__temp != __first)
3225         {
3226             __push_begin_marked_subexpression();
3227             unsigned __temp_count = __marked_count_;
3228             __first = __parse_RE_expression(__temp, __last);
3229             __temp = __parse_Back_close_paren(__first, __last);
3230             if (__temp == __first)
3231                 __throw_regex_error<regex_constants::error_paren>();
3232             __push_end_marked_subexpression(__temp_count);
3233             __first = __temp;
3234         }
3235         else
3236             __first = __parse_BACKREF(__first, __last);
3237     }
3238     return __first;
3239 }
3240
3241 template <class _CharT, class _Traits>
3242 template <class _ForwardIterator>
3243 _ForwardIterator
3244 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
3245                                                        _ForwardIterator __first,
3246                                                        _ForwardIterator __last)
3247 {
3248     _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
3249     if (__temp == __first)
3250     {
3251         __temp = __parse_QUOTED_CHAR(__first, __last);
3252         if (__temp == __first)
3253         {
3254             if (__temp != __last && *__temp == '.')
3255             {
3256                 __push_match_any();
3257                 ++__temp;
3258             }
3259             else
3260                 __temp = __parse_bracket_expression(__first, __last);
3261         }
3262     }
3263     __first = __temp;
3264     return __first;
3265 }
3266
3267 template <class _CharT, class _Traits>
3268 template <class _ForwardIterator>
3269 _ForwardIterator
3270 basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
3271                                                        _ForwardIterator __first,
3272                                                        _ForwardIterator __last)
3273 {
3274     _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
3275     if (__temp == __first)
3276     {
3277         __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
3278         if (__temp == __first)
3279         {
3280             if (__temp != __last && *__temp == '.')
3281             {
3282                 __push_match_any();
3283                 ++__temp;
3284             }
3285             else
3286                 __temp = __parse_bracket_expression(__first, __last);
3287         }
3288     }
3289     __first = __temp;
3290     return __first;
3291 }
3292
3293 template <class _CharT, class _Traits>
3294 template <class _ForwardIterator>
3295 _ForwardIterator
3296 basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
3297                                                       _ForwardIterator __last)
3298 {
3299     if (__first != __last)
3300     {
3301         _ForwardIterator __temp = _VSTD::next(__first);
3302         if (__temp != __last)
3303         {
3304             if (*__first == '\\' && *__temp == '(')
3305                 __first = ++__temp;
3306         }
3307     }
3308     return __first;
3309 }
3310
3311 template <class _CharT, class _Traits>
3312 template <class _ForwardIterator>
3313 _ForwardIterator
3314 basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
3315                                                        _ForwardIterator __last)
3316 {
3317     if (__first != __last)
3318     {
3319         _ForwardIterator __temp = _VSTD::next(__first);
3320         if (__temp != __last)
3321         {
3322             if (*__first == '\\' && *__temp == ')')
3323                 __first = ++__temp;
3324         }
3325     }
3326     return __first;
3327 }
3328
3329 template <class _CharT, class _Traits>
3330 template <class _ForwardIterator>
3331 _ForwardIterator
3332 basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
3333                                                       _ForwardIterator __last)
3334 {
3335     if (__first != __last)
3336     {
3337         _ForwardIterator __temp = _VSTD::next(__first);
3338         if (__temp != __last)
3339         {
3340             if (*__first == '\\' && *__temp == '{')
3341                 __first = ++__temp;
3342         }
3343     }
3344     return __first;
3345 }
3346
3347 template <class _CharT, class _Traits>
3348 template <class _ForwardIterator>
3349 _ForwardIterator
3350 basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
3351                                                        _ForwardIterator __last)
3352 {
3353     if (__first != __last)
3354     {
3355         _ForwardIterator __temp = _VSTD::next(__first);
3356         if (__temp != __last)
3357         {
3358             if (*__first == '\\' && *__temp == '}')
3359                 __first = ++__temp;
3360         }
3361     }
3362     return __first;
3363 }
3364
3365 template <class _CharT, class _Traits>
3366 template <class _ForwardIterator>
3367 _ForwardIterator
3368 basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
3369                                               _ForwardIterator __last)
3370 {
3371     if (__first != __last)
3372     {
3373         _ForwardIterator __temp = _VSTD::next(__first);
3374         if (__temp != __last)
3375         {
3376             if (*__first == '\\')
3377             {
3378                 int __val = __traits_.value(*__temp, 10);
3379                 if (__val >= 1 && __val <= 9)
3380                 {
3381                     __push_back_ref(__val);
3382                     __first = ++__temp;
3383                 }
3384             }
3385         }
3386     }
3387     return __first;
3388 }
3389
3390 template <class _CharT, class _Traits>
3391 template <class _ForwardIterator>
3392 _ForwardIterator
3393 basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
3394                                                _ForwardIterator __last)
3395 {
3396     if (__first != __last)
3397     {
3398         _ForwardIterator __temp = _VSTD::next(__first);
3399         if (__temp == __last && *__first == '$')
3400             return __first;
3401         // Not called inside a bracket
3402         if (*__first == '.' || *__first == '\\' || *__first == '[')
3403             return __first;
3404         __push_char(*__first);
3405         ++__first;
3406     }
3407     return __first;
3408 }
3409
3410 template <class _CharT, class _Traits>
3411 template <class _ForwardIterator>
3412 _ForwardIterator
3413 basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
3414                                                    _ForwardIterator __last)
3415 {
3416     if (__first != __last)
3417     {
3418         switch (*__first)
3419         {
3420         case '^':
3421         case '.':
3422         case '[':
3423         case '$':
3424         case '(':
3425         case '|':
3426         case '*':
3427         case '+':
3428         case '?':
3429         case '{':
3430         case '\\':
3431             break;
3432         case ')':
3433             if (__open_count_ == 0)
3434             {
3435                 __push_char(*__first);
3436                 ++__first;
3437             }
3438             break;
3439         default:
3440             __push_char(*__first);
3441             ++__first;
3442             break;
3443         }
3444     }
3445     return __first;
3446 }
3447
3448 template <class _CharT, class _Traits>
3449 template <class _ForwardIterator>
3450 _ForwardIterator
3451 basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
3452                                                   _ForwardIterator __last)
3453 {
3454     if (__first != __last)
3455     {
3456         _ForwardIterator __temp = _VSTD::next(__first);
3457         if (__temp != __last)
3458         {
3459             if (*__first == '\\')
3460             {
3461                 switch (*__temp)
3462                 {
3463                 case '^':
3464                 case '.':
3465                 case '*':
3466                 case '[':
3467                 case '$':
3468                 case '\\':
3469                     __push_char(*__temp);
3470                     __first = ++__temp;
3471                     break;
3472                 }
3473             }
3474         }
3475     }
3476     return __first;
3477 }
3478
3479 template <class _CharT, class _Traits>
3480 template <class _ForwardIterator>
3481 _ForwardIterator
3482 basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
3483                                                       _ForwardIterator __last)
3484 {
3485     if (__first != __last)
3486     {
3487         _ForwardIterator __temp = _VSTD::next(__first);
3488         if (__temp != __last)
3489         {
3490             if (*__first == '\\')
3491             {
3492                 switch (*__temp)
3493                 {
3494                 case '^':
3495                 case '.':
3496                 case '*':
3497                 case '[':
3498                 case '$':
3499                 case '\\':
3500                 case '(':
3501                 case ')':
3502                 case '|':
3503                 case '+':
3504                 case '?':
3505                 case '{':
3506                 case '}':
3507                     __push_char(*__temp);
3508                     __first = ++__temp;
3509                     break;
3510                 default:
3511                     if ((__flags_ & 0x1F0) == awk)
3512                         __first = __parse_awk_escape(++__first, __last);
3513                     break;
3514                 }
3515             }
3516         }
3517     }
3518     return __first;
3519 }
3520
3521 template <class _CharT, class _Traits>
3522 template <class _ForwardIterator>
3523 _ForwardIterator
3524 basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
3525                                                      _ForwardIterator __last,
3526                                                      __owns_one_state<_CharT>* __s,
3527                                                      unsigned __mexp_begin,
3528                                                      unsigned __mexp_end)
3529 {
3530     if (__first != __last)
3531     {
3532         if (*__first == '*')
3533         {
3534             __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3535             ++__first;
3536         }
3537         else
3538         {
3539             _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
3540             if (__temp != __first)
3541             {
3542                 int __min = 0;
3543                 __first = __temp;
3544                 __temp = __parse_DUP_COUNT(__first, __last, __min);
3545                 if (__temp == __first)
3546                     __throw_regex_error<regex_constants::error_badbrace>();
3547                 __first = __temp;
3548                 if (__first == __last)
3549                     __throw_regex_error<regex_constants::error_brace>();
3550                 if (*__first != ',')
3551                 {
3552                     __temp = __parse_Back_close_brace(__first, __last);
3553                     if (__temp == __first)
3554                         __throw_regex_error<regex_constants::error_brace>();
3555                     __push_loop(__min, __min, __s, __mexp_begin, __mexp_end,
3556                                     true);
3557                     __first = __temp;
3558                 }
3559                 else
3560                 {
3561                     ++__first;  // consume ','
3562                     int __max = -1;
3563                     __first = __parse_DUP_COUNT(__first, __last, __max);
3564                     __temp = __parse_Back_close_brace(__first, __last);
3565                     if (__temp == __first)
3566                         __throw_regex_error<regex_constants::error_brace>();
3567                     if (__max == -1)
3568                         __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3569                     else
3570                     {
3571                         if (__max < __min)
3572                             __throw_regex_error<regex_constants::error_badbrace>();
3573                         __push_loop(__min, __max, __s, __mexp_begin, __mexp_end,
3574                                     true);
3575                     }
3576                     __first = __temp;
3577                 }
3578             }
3579         }
3580     }
3581     return __first;
3582 }
3583
3584 template <class _CharT, class _Traits>
3585 template <class _ForwardIterator>
3586 _ForwardIterator
3587 basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
3588                                                       _ForwardIterator __last,
3589                                                       __owns_one_state<_CharT>* __s,
3590                                                       unsigned __mexp_begin,
3591                                                       unsigned __mexp_end)
3592 {
3593     if (__first != __last)
3594     {
3595         unsigned __grammar = __flags_ & 0x1F0;
3596         switch (*__first)
3597         {
3598         case '*':
3599             ++__first;
3600             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3601             {
3602                 ++__first;
3603                 __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3604             }
3605             else
3606                 __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3607             break;
3608         case '+':
3609             ++__first;
3610             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3611             {
3612                 ++__first;
3613                 __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3614             }
3615             else
3616                 __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3617             break;
3618         case '?':
3619             ++__first;
3620             if (__grammar == ECMAScript && __first != __last && *__first == '?')
3621             {
3622                 ++__first;
3623                 __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);
3624             }
3625             else
3626                 __push_loop(0, 1, __s, __mexp_begin, __mexp_end);
3627             break;
3628         case '{':
3629             {
3630                 int __min;
3631                 _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);
3632                 if (__temp == __first)
3633                     __throw_regex_error<regex_constants::error_badbrace>();
3634                 __first = __temp;
3635                 if (__first == __last)
3636                     __throw_regex_error<regex_constants::error_brace>();
3637                 switch (*__first)
3638                 {
3639                 case '}':
3640                     ++__first;
3641                     if (__grammar == ECMAScript && __first != __last && *__first == '?')
3642                     {
3643                         ++__first;
3644                         __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);
3645                     }
3646                     else
3647                         __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);
3648                     break;
3649                 case ',':
3650                     ++__first;
3651                     if (__first == __last)
3652                         __throw_regex_error<regex_constants::error_badbrace>();
3653                     if (*__first == '}')
3654                     {
3655                         ++__first;
3656                         if (__grammar == ECMAScript && __first != __last && *__first == '?')
3657                         {
3658                             ++__first;
3659                             __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3660                         }
3661                         else
3662                             __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3663                     }
3664                     else
3665                     {
3666                         int __max = -1;
3667                         __temp = __parse_DUP_COUNT(__first, __last, __max);
3668                         if (__temp == __first)
3669                             __throw_regex_error<regex_constants::error_brace>();
3670                         __first = __temp;
3671                         if (__first == __last || *__first != '}')
3672                             __throw_regex_error<regex_constants::error_brace>();
3673                         ++__first;
3674                         if (__max < __min)
3675                             __throw_regex_error<regex_constants::error_badbrace>();
3676                         if (__grammar == ECMAScript && __first != __last && *__first == '?')
3677                         {
3678                             ++__first;
3679                             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);
3680                         }
3681                         else
3682                             __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);
3683                     }
3684                     break;
3685                 default:
3686                     __throw_regex_error<regex_constants::error_badbrace>();
3687                 }
3688             }
3689             break;
3690         }
3691     }
3692     return __first;
3693 }
3694
3695 template <class _CharT, class _Traits>
3696 template <class _ForwardIterator>
3697 _ForwardIterator
3698 basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
3699                                                          _ForwardIterator __last)
3700 {
3701     if (__first != __last && *__first == '[')
3702     {
3703         ++__first;
3704         if (__first == __last)
3705             __throw_regex_error<regex_constants::error_brack>();
3706         bool __negate = false;
3707         if (*__first == '^')
3708         {
3709             ++__first;
3710             __negate = true;
3711         }
3712         __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
3713         // __ml owned by *this
3714         if (__first == __last)
3715             __throw_regex_error<regex_constants::error_brack>();
3716         if ((__flags_ & 0x1F0) != ECMAScript && *__first == ']')
3717         {
3718             __ml->__add_char(']');
3719             ++__first;
3720         }
3721         __first = __parse_follow_list(__first, __last, __ml);
3722         if (__first == __last)
3723             __throw_regex_error<regex_constants::error_brack>();
3724         if (*__first == '-')
3725         {
3726             __ml->__add_char('-');
3727             ++__first;
3728         }
3729         if (__first == __last || *__first != ']')
3730             __throw_regex_error<regex_constants::error_brack>();
3731         ++__first;
3732     }
3733     return __first;
3734 }
3735
3736 template <class _CharT, class _Traits>
3737 template <class _ForwardIterator>
3738 _ForwardIterator
3739 basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
3740                                     _ForwardIterator __last,
3741                                     __bracket_expression<_CharT, _Traits>* __ml)
3742 {
3743     if (__first != __last)
3744     {
3745         while (true)
3746         {
3747             _ForwardIterator __temp = __parse_expression_term(__first, __last,
3748                                                               __ml);
3749             if (__temp == __first)
3750                 break;
3751             __first = __temp;
3752         }
3753     }
3754     return __first;
3755 }
3756
3757 template <class _CharT, class _Traits>
3758 template <class _ForwardIterator>
3759 _ForwardIterator
3760 basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
3761                                     _ForwardIterator __last,
3762                                     __bracket_expression<_CharT, _Traits>* __ml)
3763 {
3764     if (__first != __last && *__first != ']')
3765     {
3766         _ForwardIterator __temp = _VSTD::next(__first);
3767         basic_string<_CharT> __start_range;
3768         if (__temp != __last && *__first == '[')
3769         {
3770             if (*__temp == '=')
3771                 return __parse_equivalence_class(++__temp, __last, __ml);
3772             else if (*__temp == ':')
3773                 return __parse_character_class(++__temp, __last, __ml);
3774             else if (*__temp == '.')
3775                 __first = __parse_collating_symbol(++__temp, __last, __start_range);
3776         }
3777         unsigned __grammar = __flags_ & 0x1F0;
3778         if (__start_range.empty())
3779         {
3780             if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3781             {
3782                 if (__grammar == ECMAScript)
3783                     __first = __parse_class_escape(++__first, __last, __start_range, __ml);
3784                 else
3785                     __first = __parse_awk_escape(++__first, __last, &__start_range);
3786             }
3787             else
3788             {
3789                 __start_range = *__first;
3790                 ++__first;
3791             }
3792         }
3793         if (__first != __last && *__first != ']')
3794         {
3795             __temp = _VSTD::next(__first);
3796             if (__temp != __last && *__first == '-' && *__temp != ']')
3797             {
3798                 // parse a range
3799                 basic_string<_CharT> __end_range;
3800                 __first = __temp;
3801                 ++__temp;
3802                 if (__temp != __last && *__first == '[' && *__temp == '.')
3803                     __first = __parse_collating_symbol(++__temp, __last, __end_range);
3804                 else
3805                 {
3806                     if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3807                     {
3808                         if (__grammar == ECMAScript)
3809                             __first = __parse_class_escape(++__first, __last,
3810                                                            __end_range, __ml);
3811                         else
3812                             __first = __parse_awk_escape(++__first, __last,
3813                                                          &__end_range);
3814                     }
3815                     else
3816                     {
3817                         __end_range = *__first;
3818                         ++__first;
3819                     }
3820                 }
3821                 __ml->__add_range(_VSTD::move(__start_range), _VSTD::move(__end_range));
3822             }
3823             else if (!__start_range.empty())
3824             {
3825                 if (__start_range.size() == 1)
3826                     __ml->__add_char(__start_range[0]);
3827                 else
3828                     __ml->__add_digraph(__start_range[0], __start_range[1]);
3829             }
3830         }
3831         else if (!__start_range.empty())
3832         {
3833             if (__start_range.size() == 1)
3834                 __ml->__add_char(__start_range[0]);
3835             else
3836                 __ml->__add_digraph(__start_range[0], __start_range[1]);
3837         }
3838     }
3839     return __first;
3840 }
3841
3842 template <class _CharT, class _Traits>
3843 template <class _ForwardIterator>
3844 _ForwardIterator
3845 basic_regex<_CharT, _Traits>::__parse_class_escape(_ForwardIterator __first,
3846                           _ForwardIterator __last,
3847                           basic_string<_CharT>& __str,
3848                           __bracket_expression<_CharT, _Traits>* __ml)
3849 {
3850     if (__first == __last)
3851         __throw_regex_error<regex_constants::error_escape>();
3852     switch (*__first)
3853     {
3854     case 0:
3855         __str = *__first;
3856         return ++__first;
3857     case 'b':
3858         __str = _CharT(8);
3859         return ++__first;
3860     case 'd':
3861         __ml->__add_class(ctype_base::digit);
3862         return ++__first;
3863     case 'D':
3864         __ml->__add_neg_class(ctype_base::digit);
3865         return ++__first;
3866     case 's':
3867         __ml->__add_class(ctype_base::space);
3868         return ++__first;
3869     case 'S':
3870         __ml->__add_neg_class(ctype_base::space);
3871         return ++__first;
3872     case 'w':
3873         __ml->__add_class(ctype_base::alnum);
3874         __ml->__add_char('_');
3875         return ++__first;
3876     case 'W':
3877         __ml->__add_neg_class(ctype_base::alnum);
3878         __ml->__add_neg_char('_');
3879         return ++__first;
3880     }
3881     __first = __parse_character_escape(__first, __last, &__str);
3882     return __first;
3883 }
3884
3885 template <class _CharT, class _Traits>
3886 template <class _ForwardIterator>
3887 _ForwardIterator
3888 basic_regex<_CharT, _Traits>::__parse_awk_escape(_ForwardIterator __first,
3889                           _ForwardIterator __last,
3890                           basic_string<_CharT>* __str)
3891 {
3892     if (__first == __last)
3893         __throw_regex_error<regex_constants::error_escape>();
3894     switch (*__first)
3895     {
3896     case '\\':
3897     case '"':
3898     case '/':
3899         if (__str)
3900             *__str = *__first;
3901         else
3902             __push_char(*__first);
3903         return ++__first;
3904     case 'a':
3905         if (__str)
3906             *__str = _CharT(7);
3907         else
3908             __push_char(_CharT(7));
3909         return ++__first;
3910     case 'b':
3911         if (__str)
3912             *__str = _CharT(8);
3913         else
3914             __push_char(_CharT(8));
3915         return ++__first;
3916     case 'f':
3917         if (__str)
3918             *__str = _CharT(0xC);
3919         else
3920             __push_char(_CharT(0xC));
3921         return ++__first;
3922     case 'n':
3923         if (__str)
3924             *__str = _CharT(0xA);
3925         else
3926             __push_char(_CharT(0xA));
3927         return ++__first;
3928     case 'r':
3929         if (__str)
3930             *__str = _CharT(0xD);
3931         else
3932             __push_char(_CharT(0xD));
3933         return ++__first;
3934     case 't':
3935         if (__str)
3936             *__str = _CharT(0x9);
3937         else
3938             __push_char(_CharT(0x9));
3939         return ++__first;
3940     case 'v':
3941         if (__str)
3942             *__str = _CharT(0xB);
3943         else
3944             __push_char(_CharT(0xB));
3945         return ++__first;
3946     }
3947     if ('0' <= *__first && *__first <= '7')
3948     {
3949         unsigned __val = *__first - '0';
3950         if (++__first != __last && ('0' <= *__first && *__first <= '7'))
3951         {
3952             __val = 8 * __val + *__first - '0';
3953             if (++__first != __last && ('0' <= *__first && *__first <= '7'))
3954                 __val = 8 * __val + *__first++ - '0';
3955         }
3956         if (__str)
3957             *__str = _CharT(__val);
3958         else
3959             __push_char(_CharT(__val));
3960     }
3961     else
3962         __throw_regex_error<regex_constants::error_escape>();
3963     return __first;
3964 }
3965
3966 template <class _CharT, class _Traits>
3967 template <class _ForwardIterator>
3968 _ForwardIterator
3969 basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
3970                                     _ForwardIterator __last,
3971                                     __bracket_expression<_CharT, _Traits>* __ml)
3972 {
3973     // Found [=
3974     //   This means =] must exist
3975     value_type _Equal_close[2] = {'=', ']'};
3976     _ForwardIterator __temp = _VSTD::search(__first, __last, _Equal_close,
3977                                                             _Equal_close+2);
3978     if (__temp == __last)
3979         __throw_regex_error<regex_constants::error_brack>();
3980     // [__first, __temp) contains all text in [= ... =]
3981     string_type __collate_name =
3982         __traits_.lookup_collatename(__first, __temp);
3983     if (__collate_name.empty())
3984         __throw_regex_error<regex_constants::error_collate>();
3985     string_type __equiv_name =
3986         __traits_.transform_primary(__collate_name.begin(),
3987                                     __collate_name.end());
3988     if (!__equiv_name.empty())
3989         __ml->__add_equivalence(__equiv_name);
3990     else
3991     {
3992         switch (__collate_name.size())
3993         {
3994         case 1:
3995             __ml->__add_char(__collate_name[0]);
3996             break;
3997         case 2:
3998             __ml->__add_digraph(__collate_name[0], __collate_name[1]);
3999             break;
4000         default:
4001             __throw_regex_error<regex_constants::error_collate>();
4002         }
4003     }
4004     __first = _VSTD::next(__temp, 2);
4005     return __first;
4006 }
4007
4008 template <class _CharT, class _Traits>
4009 template <class _ForwardIterator>
4010 _ForwardIterator
4011 basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
4012                                     _ForwardIterator __last,
4013                                     __bracket_expression<_CharT, _Traits>* __ml)
4014 {
4015     // Found [:
4016     //   This means :] must exist
4017     value_type _Colon_close[2] = {':', ']'};
4018     _ForwardIterator __temp = _VSTD::search(__first, __last, _Colon_close,
4019                                                             _Colon_close+2);
4020     if (__temp == __last)
4021         __throw_regex_error<regex_constants::error_brack>();
4022     // [__first, __temp) contains all text in [: ... :]
4023     typedef typename _Traits::char_class_type char_class_type;
4024     char_class_type __class_type =
4025         __traits_.lookup_classname(__first, __temp, __flags_ & icase);
4026     if (__class_type == 0)
4027         __throw_regex_error<regex_constants::error_ctype>();
4028     __ml->__add_class(__class_type);
4029     __first = _VSTD::next(__temp, 2);
4030     return __first;
4031 }
4032
4033 template <class _CharT, class _Traits>
4034 template <class _ForwardIterator>
4035 _ForwardIterator
4036 basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
4037                                                 _ForwardIterator __last,
4038                                                 basic_string<_CharT>& __col_sym)
4039 {
4040     // Found [.
4041     //   This means .] must exist
4042     value_type _Dot_close[2] = {'.', ']'};
4043     _ForwardIterator __temp = _VSTD::search(__first, __last, _Dot_close,
4044                                                             _Dot_close+2);
4045     if (__temp == __last)
4046         __throw_regex_error<regex_constants::error_brack>();
4047     // [__first, __temp) contains all text in [. ... .]
4048     __col_sym = __traits_.lookup_collatename(__first, __temp);
4049     switch (__col_sym.size())
4050     {
4051     case 1:
4052     case 2:
4053         break;
4054     default:
4055         __throw_regex_error<regex_constants::error_collate>();
4056     }
4057     __first = _VSTD::next(__temp, 2);
4058     return __first;
4059 }
4060
4061 template <class _CharT, class _Traits>
4062 template <class _ForwardIterator>
4063 _ForwardIterator
4064 basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
4065                                                 _ForwardIterator __last,
4066                                                 int& __c)
4067 {
4068     if (__first != __last )
4069     {
4070         int __val = __traits_.value(*__first, 10);
4071         if ( __val != -1 )
4072         {
4073             __c = __val;
4074             for (++__first;
4075                  __first != __last && ( __val = __traits_.value(*__first, 10)) != -1;
4076                  ++__first)
4077             {
4078                 if (__c >= std::numeric_limits<int>::max() / 10)
4079                     __throw_regex_error<regex_constants::error_badbrace>();
4080                 __c *= 10;
4081                 __c += __val;
4082             }
4083         }
4084     }
4085     return __first;
4086 }
4087
4088 template <class _CharT, class _Traits>
4089 template <class _ForwardIterator>
4090 _ForwardIterator
4091 basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first,
4092                                                _ForwardIterator __last)
4093 {
4094     __owns_one_state<_CharT>* __sa = __end_;
4095     _ForwardIterator __temp = __parse_alternative(__first, __last);
4096     if (__temp == __first)
4097         __push_empty();
4098     __first = __temp;
4099     while (__first != __last && *__first == '|')
4100     {
4101         __owns_one_state<_CharT>* __sb = __end_;
4102         __temp = __parse_alternative(++__first, __last);
4103         if (__temp == __first)
4104             __push_empty();
4105         __push_alternation(__sa, __sb);
4106         __first = __temp;
4107     }
4108     return __first;
4109 }
4110
4111 template <class _CharT, class _Traits>
4112 template <class _ForwardIterator>
4113 _ForwardIterator
4114 basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first,
4115                                                   _ForwardIterator __last)
4116 {
4117     while (true)
4118     {
4119         _ForwardIterator __temp = __parse_term(__first, __last);
4120         if (__temp == __first)
4121             break;
4122         __first = __temp;
4123     }
4124     return __first;
4125 }
4126
4127 template <class _CharT, class _Traits>
4128 template <class _ForwardIterator>
4129 _ForwardIterator
4130 basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first,
4131                                            _ForwardIterator __last)
4132 {
4133     _ForwardIterator __temp = __parse_assertion(__first, __last);
4134     if (__temp == __first)
4135     {
4136         __owns_one_state<_CharT>* __e = __end_;
4137         unsigned __mexp_begin = __marked_count_;
4138         __temp = __parse_atom(__first, __last);
4139         if (__temp != __first)
4140             __first = __parse_ERE_dupl_symbol(__temp, __last, __e,
4141                                               __mexp_begin+1, __marked_count_+1);
4142     }
4143     else
4144         __first = __temp;
4145     return __first;
4146 }
4147
4148 template <class _CharT, class _Traits>
4149 template <class _ForwardIterator>
4150 _ForwardIterator
4151 basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first,
4152                                                 _ForwardIterator __last)
4153 {
4154     if (__first != __last)
4155     {
4156         switch (*__first)
4157         {
4158         case '^':
4159             __push_l_anchor();
4160             ++__first;
4161             break;
4162         case '$':
4163             __push_r_anchor();
4164             ++__first;
4165             break;
4166         case '\\':
4167             {
4168                 _ForwardIterator __temp = _VSTD::next(__first);
4169                 if (__temp != __last)
4170                 {
4171                     if (*__temp == 'b')
4172                     {
4173                         __push_word_boundary(false);
4174                         __first = ++__temp;
4175                     }
4176                     else if (*__temp == 'B')
4177                     {
4178                         __push_word_boundary(true);
4179                         __first = ++__temp;
4180                     }
4181                 }
4182             }
4183             break;
4184         case '(':
4185             {
4186                 _ForwardIterator __temp = _VSTD::next(__first);
4187                 if (__temp != __last && *__temp == '?')
4188                 {
4189                     if (++__temp != __last)
4190                     {
4191                         switch (*__temp)
4192                         {
4193                         case '=':
4194                             {
4195                                 basic_regex __exp;
4196                                 __exp.__flags_ = __flags_;
4197                                 __temp = __exp.__parse(++__temp, __last);
4198                                 unsigned __mexp = __exp.__marked_count_;
4199                                 __push_lookahead(_VSTD::move(__exp), false, __marked_count_);
4200                                 __marked_count_ += __mexp;
4201                                 if (__temp == __last || *__temp != ')')
4202                                     __throw_regex_error<regex_constants::error_paren>();
4203                                 __first = ++__temp;
4204                             }
4205                             break;
4206                         case '!':
4207                             {
4208                                 basic_regex __exp;
4209                                 __exp.__flags_ = __flags_;
4210                                 __temp = __exp.__parse(++__temp, __last);
4211                                 unsigned __mexp = __exp.__marked_count_;
4212                                 __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
4213                                 __marked_count_ += __mexp;
4214                                 if (__temp == __last || *__temp != ')')
4215                                     __throw_regex_error<regex_constants::error_paren>();
4216                                 __first = ++__temp;
4217                             }
4218                             break;
4219                         }
4220                     }
4221                 }
4222             }
4223             break;
4224         }
4225     }
4226     return __first;
4227 }
4228
4229 template <class _CharT, class _Traits>
4230 template <class _ForwardIterator>
4231 _ForwardIterator
4232 basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first,
4233                                            _ForwardIterator __last)
4234 {
4235     if (__first != __last)
4236     {
4237         switch (*__first)
4238         {
4239         case '.':
4240             __push_match_any_but_newline();
4241             ++__first;
4242             break;
4243         case '\\':
4244             __first = __parse_atom_escape(__first, __last);
4245             break;
4246         case '[':
4247             __first = __parse_bracket_expression(__first, __last);
4248             break;
4249         case '(':
4250             {
4251                 ++__first;
4252                 if (__first == __last)
4253                     __throw_regex_error<regex_constants::error_paren>();
4254                 _ForwardIterator __temp = _VSTD::next(__first);
4255                 if (__temp != __last && *__first == '?' && *__temp == ':')
4256                 {
4257                     ++__open_count_;
4258                     __first = __parse_ecma_exp(++__temp, __last);
4259                     if (__first == __last || *__first != ')')
4260                         __throw_regex_error<regex_constants::error_paren>();
4261                     --__open_count_;
4262                     ++__first;
4263                 }
4264                 else
4265                 {
4266                     __push_begin_marked_subexpression();
4267                     unsigned __temp_count = __marked_count_;
4268                     ++__open_count_;
4269                     __first = __parse_ecma_exp(__first, __last);
4270                     if (__first == __last || *__first != ')')
4271                         __throw_regex_error<regex_constants::error_paren>();
4272                     __push_end_marked_subexpression(__temp_count);
4273                     --__open_count_;
4274                     ++__first;
4275                 }
4276             }
4277             break;
4278         case '*':
4279         case '+':
4280         case '?':
4281         case '{':
4282             __throw_regex_error<regex_constants::error_badrepeat>();
4283             break;
4284         default:
4285             __first = __parse_pattern_character(__first, __last);
4286             break;
4287         }
4288     }
4289     return __first;
4290 }
4291
4292 template <class _CharT, class _Traits>
4293 template <class _ForwardIterator>
4294 _ForwardIterator
4295 basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first,
4296                                                   _ForwardIterator __last)
4297 {
4298     if (__first != __last && *__first == '\\')
4299     {
4300         _ForwardIterator __t1 = _VSTD::next(__first);
4301         if (__t1 == __last)
4302             __throw_regex_error<regex_constants::error_escape>();
4303
4304         _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
4305         if (__t2 != __t1)
4306             __first = __t2;
4307         else
4308         {
4309             __t2 = __parse_character_class_escape(__t1, __last);
4310             if (__t2 != __t1)
4311                 __first = __t2;
4312             else
4313             {
4314                 __t2 = __parse_character_escape(__t1, __last);
4315                 if (__t2 != __t1)
4316                     __first = __t2;
4317             }
4318         }
4319     }
4320     return __first;
4321 }
4322
4323 template <class _CharT, class _Traits>
4324 template <class _ForwardIterator>
4325 _ForwardIterator
4326 basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first,
4327                                                      _ForwardIterator __last)
4328 {
4329     if (__first != __last)
4330     {
4331         if (*__first == '0')
4332         {
4333             __push_char(_CharT());
4334             ++__first;
4335         }
4336         else if ('1' <= *__first && *__first <= '9')
4337         {
4338             unsigned __v = *__first - '0';
4339             for (++__first;
4340                     __first != __last && '0' <= *__first && *__first <= '9'; ++__first)
4341                 {
4342                 if (__v >= std::numeric_limits<unsigned>::max() / 10)
4343                     __throw_regex_error<regex_constants::error_backref>();
4344                 __v = 10 * __v + *__first - '0';
4345                 }
4346             if (__v == 0 || __v > mark_count())
4347                 __throw_regex_error<regex_constants::error_backref>();
4348             __push_back_ref(__v);
4349         }
4350     }
4351     return __first;
4352 }
4353
4354 template <class _CharT, class _Traits>
4355 template <class _ForwardIterator>
4356 _ForwardIterator
4357 basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first,
4358                                                              _ForwardIterator __last)
4359 {
4360     if (__first != __last)
4361     {
4362         __bracket_expression<_CharT, _Traits>* __ml;
4363         switch (*__first)
4364         {
4365         case 'd':
4366             __ml = __start_matching_list(false);
4367             __ml->__add_class(ctype_base::digit);
4368             ++__first;
4369             break;
4370         case 'D':
4371             __ml = __start_matching_list(true);
4372             __ml->__add_class(ctype_base::digit);
4373             ++__first;
4374             break;
4375         case 's':
4376             __ml = __start_matching_list(false);
4377             __ml->__add_class(ctype_base::space);
4378             ++__first;
4379             break;
4380         case 'S':
4381             __ml = __start_matching_list(true);
4382             __ml->__add_class(ctype_base::space);
4383             ++__first;
4384             break;
4385         case 'w':
4386             __ml = __start_matching_list(false);
4387             __ml->__add_class(ctype_base::alnum);
4388             __ml->__add_char('_');
4389             ++__first;
4390             break;
4391         case 'W':
4392             __ml = __start_matching_list(true);
4393             __ml->__add_class(ctype_base::alnum);
4394             __ml->__add_char('_');
4395             ++__first;
4396             break;
4397         }
4398     }
4399     return __first;
4400 }
4401
4402 template <class _CharT, class _Traits>
4403 template <class _ForwardIterator>
4404 _ForwardIterator
4405 basic_regex<_CharT, _Traits>::__parse_character_escape(_ForwardIterator __first,
4406                                                     _ForwardIterator __last,
4407                                                     basic_string<_CharT>* __str)
4408 {
4409     if (__first != __last)
4410     {
4411         _ForwardIterator __t;
4412         unsigned __sum = 0;
4413         int __hd;
4414         switch (*__first)
4415         {
4416         case 'f':
4417             if (__str)
4418                 *__str = _CharT(0xC);
4419             else
4420                 __push_char(_CharT(0xC));
4421             ++__first;
4422             break;
4423         case 'n':
4424             if (__str)
4425                 *__str = _CharT(0xA);
4426             else
4427                 __push_char(_CharT(0xA));
4428             ++__first;
4429             break;
4430         case 'r':
4431             if (__str)
4432                 *__str = _CharT(0xD);
4433             else
4434                 __push_char(_CharT(0xD));
4435             ++__first;
4436             break;
4437         case 't':
4438             if (__str)
4439                 *__str = _CharT(0x9);
4440             else
4441                 __push_char(_CharT(0x9));
4442             ++__first;
4443             break;
4444         case 'v':
4445             if (__str)
4446                 *__str = _CharT(0xB);
4447             else
4448                 __push_char(_CharT(0xB));
4449             ++__first;
4450             break;
4451         case 'c':
4452             if ((__t = _VSTD::next(__first)) != __last)
4453             {
4454                 if (('A' <= *__t && *__t <= 'Z') ||
4455                     ('a' <= *__t && *__t <= 'z'))
4456                 {
4457                     if (__str)
4458                         *__str = _CharT(*__t % 32);
4459                     else
4460                         __push_char(_CharT(*__t % 32));
4461                     __first = ++__t;
4462                 }
4463                 else
4464                     __throw_regex_error<regex_constants::error_escape>();
4465             }
4466             else
4467                 __throw_regex_error<regex_constants::error_escape>();
4468             break;
4469         case 'u':
4470             ++__first;
4471             if (__first == __last)
4472                 __throw_regex_error<regex_constants::error_escape>();
4473             __hd = __traits_.value(*__first, 16);
4474             if (__hd == -1)
4475                 __throw_regex_error<regex_constants::error_escape>();
4476             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4477             ++__first;
4478             if (__first == __last)
4479                 __throw_regex_error<regex_constants::error_escape>();
4480             __hd = __traits_.value(*__first, 16);
4481             if (__hd == -1)
4482                 __throw_regex_error<regex_constants::error_escape>();
4483             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4484             // drop through
4485         case 'x':
4486             ++__first;
4487             if (__first == __last)
4488                 __throw_regex_error<regex_constants::error_escape>();
4489             __hd = __traits_.value(*__first, 16);
4490             if (__hd == -1)
4491                 __throw_regex_error<regex_constants::error_escape>();
4492             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4493             ++__first;
4494             if (__first == __last)
4495                 __throw_regex_error<regex_constants::error_escape>();
4496             __hd = __traits_.value(*__first, 16);
4497             if (__hd == -1)
4498                 __throw_regex_error<regex_constants::error_escape>();
4499             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4500             if (__str)
4501                 *__str = _CharT(__sum);
4502             else
4503                 __push_char(_CharT(__sum));
4504             ++__first;
4505             break;
4506         case '0':
4507             if (__str)
4508                 *__str = _CharT(0);
4509             else
4510                 __push_char(_CharT(0));
4511             ++__first;
4512             break;
4513         default:
4514             if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum))
4515             {
4516                 if (__str)
4517                     *__str = *__first;
4518                 else
4519                     __push_char(*__first);
4520                 ++__first;
4521             }
4522             else
4523                 __throw_regex_error<regex_constants::error_escape>();
4524             break;
4525         }
4526     }
4527     return __first;
4528 }
4529
4530 template <class _CharT, class _Traits>
4531 template <class _ForwardIterator>
4532 _ForwardIterator
4533 basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first,
4534                                                         _ForwardIterator __last)
4535 {
4536     if (__first != __last)
4537     {
4538         switch (*__first)
4539         {
4540         case '^':
4541         case '$':
4542         case '\\':
4543         case '.':
4544         case '*':
4545         case '+':
4546         case '?':
4547         case '(':
4548         case ')':
4549         case '[':
4550         case ']':
4551         case '{':
4552         case '}':
4553         case '|':
4554             break;
4555         default:
4556             __push_char(*__first);
4557             ++__first;
4558             break;
4559         }
4560     }
4561     return __first;
4562 }
4563
4564 template <class _CharT, class _Traits>
4565 template <class _ForwardIterator>
4566 _ForwardIterator
4567 basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first,
4568                                            _ForwardIterator __last)
4569 {
4570     __owns_one_state<_CharT>* __sa = __end_;
4571     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4572     if (__t1 != __first)
4573         __parse_basic_reg_exp(__first, __t1);
4574     else
4575         __push_empty();
4576     __first = __t1;
4577     if (__first != __last)
4578         ++__first;
4579     while (__first != __last)
4580     {
4581         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4582         __owns_one_state<_CharT>* __sb = __end_;
4583         if (__t1 != __first)
4584             __parse_basic_reg_exp(__first, __t1);
4585         else
4586             __push_empty();
4587         __push_alternation(__sa, __sb);
4588         __first = __t1;
4589         if (__first != __last)
4590             ++__first;
4591     }
4592     return __first;
4593 }
4594
4595 template <class _CharT, class _Traits>
4596 template <class _ForwardIterator>
4597 _ForwardIterator
4598 basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first,
4599                                             _ForwardIterator __last)
4600 {
4601     __owns_one_state<_CharT>* __sa = __end_;
4602     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4603     if (__t1 != __first)
4604         __parse_extended_reg_exp(__first, __t1);
4605     else
4606         __push_empty();
4607     __first = __t1;
4608     if (__first != __last)
4609         ++__first;
4610     while (__first != __last)
4611     {
4612         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4613         __owns_one_state<_CharT>* __sb = __end_;
4614         if (__t1 != __first)
4615             __parse_extended_reg_exp(__first, __t1);
4616         else
4617             __push_empty();
4618         __push_alternation(__sa, __sb);
4619         __first = __t1;
4620         if (__first != __last)
4621             ++__first;
4622     }
4623     return __first;
4624 }
4625
4626 template <class _CharT, class _Traits>
4627 void
4628 basic_regex<_CharT, _Traits>::__push_loop(size_t __min, size_t __max,
4629         __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end,
4630         bool __greedy)
4631 {
4632     unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
4633     __end_->first() = nullptr;
4634     unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,
4635                 __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
4636                 __min, __max));
4637     __s->first() = nullptr;
4638     __e1.release();
4639     __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
4640     __end_ = __e2->second();
4641     __s->first() = __e2.release();
4642     ++__loop_count_;
4643 }
4644
4645 template <class _CharT, class _Traits>
4646 void
4647 basic_regex<_CharT, _Traits>::__push_char(value_type __c)
4648 {
4649     if (flags() & icase)
4650         __end_->first() = new __match_char_icase<_CharT, _Traits>
4651                                               (__traits_, __c, __end_->first());
4652     else if (flags() & collate)
4653         __end_->first() = new __match_char_collate<_CharT, _Traits>
4654                                               (__traits_, __c, __end_->first());
4655     else
4656         __end_->first() = new __match_char<_CharT>(__c, __end_->first());
4657     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4658 }
4659
4660 template <class _CharT, class _Traits>
4661 void
4662 basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
4663 {
4664     if (!(__flags_ & nosubs))
4665     {
4666         __end_->first() =
4667                 new __begin_marked_subexpression<_CharT>(++__marked_count_,
4668                                                          __end_->first());
4669         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4670     }
4671 }
4672
4673 template <class _CharT, class _Traits>
4674 void
4675 basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
4676 {
4677     if (!(__flags_ & nosubs))
4678     {
4679         __end_->first() =
4680                 new __end_marked_subexpression<_CharT>(__sub, __end_->first());
4681         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4682     }
4683 }
4684
4685 template <class _CharT, class _Traits>
4686 void
4687 basic_regex<_CharT, _Traits>::__push_l_anchor()
4688 {
4689     __end_->first() = new __l_anchor<_CharT>(__end_->first());
4690     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4691 }
4692
4693 template <class _CharT, class _Traits>
4694 void
4695 basic_regex<_CharT, _Traits>::__push_r_anchor()
4696 {
4697     __end_->first() = new __r_anchor<_CharT>(__end_->first());
4698     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4699 }
4700
4701 template <class _CharT, class _Traits>
4702 void
4703 basic_regex<_CharT, _Traits>::__push_match_any()
4704 {
4705     __end_->first() = new __match_any<_CharT>(__end_->first());
4706     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4707 }
4708
4709 template <class _CharT, class _Traits>
4710 void
4711 basic_regex<_CharT, _Traits>::__push_match_any_but_newline()
4712 {
4713     __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
4714     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4715 }
4716
4717 template <class _CharT, class _Traits>
4718 void
4719 basic_regex<_CharT, _Traits>::__push_empty()
4720 {
4721     __end_->first() = new __empty_state<_CharT>(__end_->first());
4722     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4723 }
4724
4725 template <class _CharT, class _Traits>
4726 void
4727 basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert)
4728 {
4729     __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert,
4730                                                            __end_->first());
4731     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4732 }
4733
4734 template <class _CharT, class _Traits>
4735 void
4736 basic_regex<_CharT, _Traits>::__push_back_ref(int __i)
4737 {
4738     if (flags() & icase)
4739         __end_->first() = new __back_ref_icase<_CharT, _Traits>
4740                                               (__traits_, __i, __end_->first());
4741     else if (flags() & collate)
4742         __end_->first() = new __back_ref_collate<_CharT, _Traits>
4743                                               (__traits_, __i, __end_->first());
4744     else
4745         __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
4746     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4747 }
4748
4749 template <class _CharT, class _Traits>
4750 void
4751 basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa,
4752                                                  __owns_one_state<_CharT>* __ea)
4753 {
4754     __sa->first() = new __alternate<_CharT>(
4755                          static_cast<__owns_one_state<_CharT>*>(__sa->first()),
4756                          static_cast<__owns_one_state<_CharT>*>(__ea->first()));
4757     __ea->first() = nullptr;
4758     __ea->first() = new __empty_state<_CharT>(__end_->first());
4759     __end_->first() = nullptr;
4760     __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
4761     __end_ = static_cast<__owns_one_state<_CharT>*>(__ea->first());
4762 }
4763
4764 template <class _CharT, class _Traits>
4765 __bracket_expression<_CharT, _Traits>*
4766 basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate)
4767 {
4768     __bracket_expression<_CharT, _Traits>* __r =
4769         new __bracket_expression<_CharT, _Traits>(__traits_, __end_->first(),
4770                                                   __negate, __flags_ & icase,
4771                                                   __flags_ & collate);
4772     __end_->first() = __r;
4773     __end_ = __r;
4774     return __r;
4775 }
4776
4777 template <class _CharT, class _Traits>
4778 void
4779 basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp,
4780                                                bool __invert,
4781                                                unsigned __mexp)
4782 {
4783     __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
4784                                                            __end_->first(), __mexp);
4785     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4786 }
4787
4788 typedef basic_regex<char>    regex;
4789 typedef basic_regex<wchar_t> wregex;
4790
4791 // sub_match
4792
4793 template <class _BidirectionalIterator>
4794 class _LIBCPP_TEMPLATE_VIS sub_match
4795     : public pair<_BidirectionalIterator, _BidirectionalIterator>
4796 {
4797 public:
4798     typedef _BidirectionalIterator                              iterator;
4799     typedef typename iterator_traits<iterator>::value_type      value_type;
4800     typedef typename iterator_traits<iterator>::difference_type difference_type;
4801     typedef basic_string<value_type>                            string_type;
4802
4803     bool matched;
4804
4805     _LIBCPP_INLINE_VISIBILITY
4806     _LIBCPP_CONSTEXPR sub_match() : matched() {}
4807
4808     _LIBCPP_INLINE_VISIBILITY
4809     difference_type length() const
4810         {return matched ? _VSTD::distance(this->first, this->second) : 0;}
4811     _LIBCPP_INLINE_VISIBILITY
4812     string_type str() const
4813         {return matched ? string_type(this->first, this->second) : string_type();}
4814     _LIBCPP_INLINE_VISIBILITY
4815     operator string_type() const
4816         {return str();}
4817
4818     _LIBCPP_INLINE_VISIBILITY
4819     int compare(const sub_match& __s) const
4820         {return str().compare(__s.str());}
4821     _LIBCPP_INLINE_VISIBILITY
4822     int compare(const string_type& __s) const
4823         {return str().compare(__s);}
4824     _LIBCPP_INLINE_VISIBILITY
4825     int compare(const value_type* __s) const
4826         {return str().compare(__s);}
4827 };
4828
4829 typedef sub_match<const char*>             csub_match;
4830 typedef sub_match<const wchar_t*>          wcsub_match;
4831 typedef sub_match<string::const_iterator>  ssub_match;
4832 typedef sub_match<wstring::const_iterator> wssub_match;
4833
4834 template <class _BiIter>
4835 inline _LIBCPP_INLINE_VISIBILITY
4836 bool
4837 operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4838 {
4839     return __x.compare(__y) == 0;
4840 }
4841
4842 template <class _BiIter>
4843 inline _LIBCPP_INLINE_VISIBILITY
4844 bool
4845 operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4846 {
4847     return !(__x == __y);
4848 }
4849
4850 template <class _BiIter>
4851 inline _LIBCPP_INLINE_VISIBILITY
4852 bool
4853 operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4854 {
4855     return __x.compare(__y) < 0;
4856 }
4857
4858 template <class _BiIter>
4859 inline _LIBCPP_INLINE_VISIBILITY
4860 bool
4861 operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4862 {
4863     return !(__y < __x);
4864 }
4865
4866 template <class _BiIter>
4867 inline _LIBCPP_INLINE_VISIBILITY
4868 bool
4869 operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4870 {
4871     return !(__x < __y);
4872 }
4873
4874 template <class _BiIter>
4875 inline _LIBCPP_INLINE_VISIBILITY
4876 bool
4877 operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4878 {
4879     return __y < __x;
4880 }
4881
4882 template <class _BiIter, class _ST, class _SA>
4883 inline _LIBCPP_INLINE_VISIBILITY
4884 bool
4885 operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4886            const sub_match<_BiIter>& __y)
4887 {
4888     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;
4889 }
4890
4891 template <class _BiIter, class _ST, class _SA>
4892 inline _LIBCPP_INLINE_VISIBILITY
4893 bool
4894 operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4895            const sub_match<_BiIter>& __y)
4896 {
4897     return !(__x == __y);
4898 }
4899
4900 template <class _BiIter, class _ST, class _SA>
4901 inline _LIBCPP_INLINE_VISIBILITY
4902 bool
4903 operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4904           const sub_match<_BiIter>& __y)
4905 {
4906     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;
4907 }
4908
4909 template <class _BiIter, class _ST, class _SA>
4910 inline _LIBCPP_INLINE_VISIBILITY
4911 bool
4912 operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4913           const sub_match<_BiIter>& __y)
4914 {
4915     return __y < __x;
4916 }
4917
4918 template <class _BiIter, class _ST, class _SA>
4919 inline _LIBCPP_INLINE_VISIBILITY
4920 bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4921                 const sub_match<_BiIter>& __y)
4922 {
4923     return !(__x < __y);
4924 }
4925
4926 template <class _BiIter, class _ST, class _SA>
4927 inline _LIBCPP_INLINE_VISIBILITY
4928 bool
4929 operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4930            const sub_match<_BiIter>& __y)
4931 {
4932     return !(__y < __x);
4933 }
4934
4935 template <class _BiIter, class _ST, class _SA>
4936 inline _LIBCPP_INLINE_VISIBILITY
4937 bool
4938 operator==(const sub_match<_BiIter>& __x,
4939            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4940 {
4941     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;
4942 }
4943
4944 template <class _BiIter, class _ST, class _SA>
4945 inline _LIBCPP_INLINE_VISIBILITY
4946 bool
4947 operator!=(const sub_match<_BiIter>& __x,
4948            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4949 {
4950     return !(__x == __y);
4951 }
4952
4953 template <class _BiIter, class _ST, class _SA>
4954 inline _LIBCPP_INLINE_VISIBILITY
4955 bool
4956 operator<(const sub_match<_BiIter>& __x,
4957           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4958 {
4959     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;
4960 }
4961
4962 template <class _BiIter, class _ST, class _SA>
4963 inline _LIBCPP_INLINE_VISIBILITY
4964 bool operator>(const sub_match<_BiIter>& __x,
4965                const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4966 {
4967     return __y < __x;
4968 }
4969
4970 template <class _BiIter, class _ST, class _SA>
4971 inline _LIBCPP_INLINE_VISIBILITY
4972 bool
4973 operator>=(const sub_match<_BiIter>& __x,
4974            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4975 {
4976     return !(__x < __y);
4977 }
4978
4979 template <class _BiIter, class _ST, class _SA>
4980 inline _LIBCPP_INLINE_VISIBILITY
4981 bool
4982 operator<=(const sub_match<_BiIter>& __x,
4983            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4984 {
4985     return !(__y < __x);
4986 }
4987
4988 template <class _BiIter>
4989 inline _LIBCPP_INLINE_VISIBILITY
4990 bool
4991 operator==(typename iterator_traits<_BiIter>::value_type const* __x,
4992            const sub_match<_BiIter>& __y)
4993 {
4994     return __y.compare(__x) == 0;
4995 }
4996
4997 template <class _BiIter>
4998 inline _LIBCPP_INLINE_VISIBILITY
4999 bool
5000 operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
5001            const sub_match<_BiIter>& __y)
5002 {
5003     return !(__x == __y);
5004 }
5005
5006 template <class _BiIter>
5007 inline _LIBCPP_INLINE_VISIBILITY
5008 bool
5009 operator<(typename iterator_traits<_BiIter>::value_type const* __x,
5010           const sub_match<_BiIter>& __y)
5011 {
5012     return __y.compare(__x) > 0;
5013 }
5014
5015 template <class _BiIter>
5016 inline _LIBCPP_INLINE_VISIBILITY
5017 bool
5018 operator>(typename iterator_traits<_BiIter>::value_type const* __x,
5019           const sub_match<_BiIter>& __y)
5020 {
5021     return __y < __x;
5022 }
5023
5024 template <class _BiIter>
5025 inline _LIBCPP_INLINE_VISIBILITY
5026 bool
5027 operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
5028            const sub_match<_BiIter>& __y)
5029 {
5030     return !(__x < __y);
5031 }
5032
5033 template <class _BiIter>
5034 inline _LIBCPP_INLINE_VISIBILITY
5035 bool
5036 operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
5037            const sub_match<_BiIter>& __y)
5038 {
5039     return !(__y < __x);
5040 }
5041
5042 template <class _BiIter>
5043 inline _LIBCPP_INLINE_VISIBILITY
5044 bool
5045 operator==(const sub_match<_BiIter>& __x,
5046            typename iterator_traits<_BiIter>::value_type const* __y)
5047 {
5048     return __x.compare(__y) == 0;
5049 }
5050
5051 template <class _BiIter>
5052 inline _LIBCPP_INLINE_VISIBILITY
5053 bool
5054 operator!=(const sub_match<_BiIter>& __x,
5055            typename iterator_traits<_BiIter>::value_type const* __y)
5056 {
5057     return !(__x == __y);
5058 }
5059
5060 template <class _BiIter>
5061 inline _LIBCPP_INLINE_VISIBILITY
5062 bool
5063 operator<(const sub_match<_BiIter>& __x,
5064           typename iterator_traits<_BiIter>::value_type const* __y)
5065 {
5066     return __x.compare(__y) < 0;
5067 }
5068
5069 template <class _BiIter>
5070 inline _LIBCPP_INLINE_VISIBILITY
5071 bool
5072 operator>(const sub_match<_BiIter>& __x,
5073           typename iterator_traits<_BiIter>::value_type const* __y)
5074 {
5075     return __y < __x;
5076 }
5077
5078 template <class _BiIter>
5079 inline _LIBCPP_INLINE_VISIBILITY
5080 bool
5081 operator>=(const sub_match<_BiIter>& __x,
5082            typename iterator_traits<_BiIter>::value_type const* __y)
5083 {
5084     return !(__x < __y);
5085 }
5086
5087 template <class _BiIter>
5088 inline _LIBCPP_INLINE_VISIBILITY
5089 bool
5090 operator<=(const sub_match<_BiIter>& __x,
5091            typename iterator_traits<_BiIter>::value_type const* __y)
5092 {
5093     return !(__y < __x);
5094 }
5095
5096 template <class _BiIter>
5097 inline _LIBCPP_INLINE_VISIBILITY
5098 bool
5099 operator==(typename iterator_traits<_BiIter>::value_type const& __x,
5100            const sub_match<_BiIter>& __y)
5101 {
5102     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5103     return __y.compare(string_type(1, __x)) == 0;
5104 }
5105
5106 template <class _BiIter>
5107 inline _LIBCPP_INLINE_VISIBILITY
5108 bool
5109 operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
5110            const sub_match<_BiIter>& __y)
5111 {
5112     return !(__x == __y);
5113 }
5114
5115 template <class _BiIter>
5116 inline _LIBCPP_INLINE_VISIBILITY
5117 bool
5118 operator<(typename iterator_traits<_BiIter>::value_type const& __x,
5119           const sub_match<_BiIter>& __y)
5120 {
5121     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5122     return __y.compare(string_type(1, __x)) > 0;
5123 }
5124
5125 template <class _BiIter>
5126 inline _LIBCPP_INLINE_VISIBILITY
5127 bool
5128 operator>(typename iterator_traits<_BiIter>::value_type const& __x,
5129           const sub_match<_BiIter>& __y)
5130 {
5131     return __y < __x;
5132 }
5133
5134 template <class _BiIter>
5135 inline _LIBCPP_INLINE_VISIBILITY
5136 bool
5137 operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
5138            const sub_match<_BiIter>& __y)
5139 {
5140     return !(__x < __y);
5141 }
5142
5143 template <class _BiIter>
5144 inline _LIBCPP_INLINE_VISIBILITY
5145 bool
5146 operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
5147            const sub_match<_BiIter>& __y)
5148 {
5149     return !(__y < __x);
5150 }
5151
5152 template <class _BiIter>
5153 inline _LIBCPP_INLINE_VISIBILITY
5154 bool
5155 operator==(const sub_match<_BiIter>& __x,
5156            typename iterator_traits<_BiIter>::value_type const& __y)
5157 {
5158     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5159     return __x.compare(string_type(1, __y)) == 0;
5160 }
5161
5162 template <class _BiIter>
5163 inline _LIBCPP_INLINE_VISIBILITY
5164 bool
5165 operator!=(const sub_match<_BiIter>& __x,
5166            typename iterator_traits<_BiIter>::value_type const& __y)
5167 {
5168     return !(__x == __y);
5169 }
5170
5171 template <class _BiIter>
5172 inline _LIBCPP_INLINE_VISIBILITY
5173 bool
5174 operator<(const sub_match<_BiIter>& __x,
5175           typename iterator_traits<_BiIter>::value_type const& __y)
5176 {
5177     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5178     return __x.compare(string_type(1, __y)) < 0;
5179 }
5180
5181 template <class _BiIter>
5182 inline _LIBCPP_INLINE_VISIBILITY
5183 bool
5184 operator>(const sub_match<_BiIter>& __x,
5185           typename iterator_traits<_BiIter>::value_type const& __y)
5186 {
5187     return __y < __x;
5188 }
5189
5190 template <class _BiIter>
5191 inline _LIBCPP_INLINE_VISIBILITY
5192 bool
5193 operator>=(const sub_match<_BiIter>& __x,
5194            typename iterator_traits<_BiIter>::value_type const& __y)
5195 {
5196     return !(__x < __y);
5197 }
5198
5199 template <class _BiIter>
5200 inline _LIBCPP_INLINE_VISIBILITY
5201 bool
5202 operator<=(const sub_match<_BiIter>& __x,
5203            typename iterator_traits<_BiIter>::value_type const& __y)
5204 {
5205     return !(__y < __x);
5206 }
5207
5208 template <class _CharT, class _ST, class _BiIter>
5209 inline _LIBCPP_INLINE_VISIBILITY
5210 basic_ostream<_CharT, _ST>&
5211 operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
5212 {
5213     return __os << __m.str();
5214 }
5215
5216 template <class _BidirectionalIterator, class _Allocator>
5217 class _LIBCPP_TEMPLATE_VIS match_results
5218 {
5219 public:
5220     typedef _Allocator                                        allocator_type;
5221     typedef sub_match<_BidirectionalIterator>                 value_type;
5222 private:
5223     typedef vector<value_type, allocator_type>                __container_type;
5224
5225     __container_type  __matches_;
5226     value_type __unmatched_;
5227     value_type __prefix_;
5228     value_type __suffix_;
5229     bool       __ready_;
5230 public:
5231     _BidirectionalIterator __position_start_;
5232     typedef const value_type&                                 const_reference;
5233     typedef value_type&                                       reference;
5234     typedef typename __container_type::const_iterator         const_iterator;
5235     typedef const_iterator                                    iterator;
5236     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
5237     typedef typename allocator_traits<allocator_type>::size_type size_type;
5238     typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
5239     typedef basic_string<char_type>                           string_type;
5240
5241     // construct/copy/destroy:
5242     explicit match_results(const allocator_type& __a = allocator_type());
5243 //    match_results(const match_results&) = default;
5244 //    match_results& operator=(const match_results&) = default;
5245 //    match_results(match_results&& __m) = default;
5246 //    match_results& operator=(match_results&& __m) = default;
5247 //    ~match_results() = default;
5248
5249     _LIBCPP_INLINE_VISIBILITY
5250     bool ready() const {return __ready_;}
5251
5252     // size:
5253     _LIBCPP_INLINE_VISIBILITY
5254     size_type size() const _NOEXCEPT {return __matches_.size();}
5255     _LIBCPP_INLINE_VISIBILITY
5256     size_type max_size() const _NOEXCEPT {return __matches_.max_size();}
5257     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
5258     bool empty() const _NOEXCEPT {return size() == 0;}
5259
5260     // element access:
5261     _LIBCPP_INLINE_VISIBILITY
5262     difference_type length(size_type __sub = 0) const
5263         {return (*this)[__sub].length();}
5264     _LIBCPP_INLINE_VISIBILITY
5265     difference_type position(size_type __sub = 0) const
5266         {return _VSTD::distance(__position_start_, (*this)[__sub].first);}
5267     _LIBCPP_INLINE_VISIBILITY
5268     string_type str(size_type __sub = 0) const
5269         {return (*this)[__sub].str();}
5270     _LIBCPP_INLINE_VISIBILITY
5271     const_reference operator[](size_type __n) const
5272         {return __n < __matches_.size() ? __matches_[__n] : __unmatched_;}
5273
5274     _LIBCPP_INLINE_VISIBILITY
5275     const_reference prefix() const {return __prefix_;}
5276     _LIBCPP_INLINE_VISIBILITY
5277     const_reference suffix() const {return __suffix_;}
5278
5279     _LIBCPP_INLINE_VISIBILITY
5280     const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin();}
5281     _LIBCPP_INLINE_VISIBILITY
5282     const_iterator end() const {return __matches_.end();}
5283     _LIBCPP_INLINE_VISIBILITY
5284     const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin();}
5285     _LIBCPP_INLINE_VISIBILITY
5286     const_iterator cend() const {return __matches_.end();}
5287
5288     // format:
5289     template <class _OutputIter>
5290         _OutputIter
5291         format(_OutputIter __output_iter, const char_type* __fmt_first,
5292                const char_type* __fmt_last,
5293                regex_constants::match_flag_type __flags = regex_constants::format_default) const;
5294     template <class _OutputIter, class _ST, class _SA>
5295         _LIBCPP_INLINE_VISIBILITY
5296         _OutputIter
5297         format(_OutputIter __output_iter, const basic_string<char_type, _ST, _SA>& __fmt,
5298                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5299             {return format(__output_iter, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
5300     template <class _ST, class _SA>
5301         _LIBCPP_INLINE_VISIBILITY
5302         basic_string<char_type, _ST, _SA>
5303         format(const basic_string<char_type, _ST, _SA>& __fmt,
5304                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5305         {
5306             basic_string<char_type, _ST, _SA> __r;
5307             format(back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
5308                    __flags);
5309             return __r;
5310         }
5311     _LIBCPP_INLINE_VISIBILITY
5312     string_type
5313         format(const char_type* __fmt,
5314                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5315         {
5316             string_type __r;
5317             format(back_inserter(__r), __fmt,
5318                    __fmt + char_traits<char_type>::length(__fmt), __flags);
5319             return __r;
5320         }
5321
5322     // allocator:
5323     _LIBCPP_INLINE_VISIBILITY
5324     allocator_type get_allocator() const {return __matches_.get_allocator();}
5325
5326     // swap:
5327     void swap(match_results& __m);
5328
5329     template <class _Bp, class _Ap>
5330         _LIBCPP_INLINE_VISIBILITY
5331         void __assign(_BidirectionalIterator __f, _BidirectionalIterator __l,
5332                       const match_results<_Bp, _Ap>& __m, bool __no_update_pos)
5333     {
5334         _Bp __mf = __m.prefix().first;
5335         __matches_.resize(__m.size());
5336         for (size_type __i = 0; __i < __matches_.size(); ++__i)
5337         {
5338             __matches_[__i].first = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].first));
5339             __matches_[__i].second = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].second));
5340             __matches_[__i].matched = __m[__i].matched;
5341         }
5342         __unmatched_.first   = __l;
5343         __unmatched_.second  = __l;
5344         __unmatched_.matched = false;
5345         __prefix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().first));
5346         __prefix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().second));
5347         __prefix_.matched = __m.prefix().matched;
5348         __suffix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().first));
5349         __suffix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().second));
5350         __suffix_.matched = __m.suffix().matched;
5351         if (!__no_update_pos)
5352             __position_start_ = __prefix_.first;
5353         __ready_ = __m.ready();
5354     }
5355
5356 private:
5357     void __init(unsigned __s,
5358                 _BidirectionalIterator __f, _BidirectionalIterator __l,
5359                 bool __no_update_pos = false);
5360
5361     template <class, class> friend class basic_regex;
5362
5363     template <class _Bp, class _Ap, class _Cp, class _Tp>
5364     friend
5365     bool
5366     regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
5367                 regex_constants::match_flag_type);
5368
5369     template <class _Bp, class _Ap>
5370     friend
5371     bool
5372     operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
5373
5374     template <class, class> friend class __lookahead;
5375 };
5376
5377 template <class _BidirectionalIterator, class _Allocator>
5378 match_results<_BidirectionalIterator, _Allocator>::match_results(
5379         const allocator_type& __a)
5380     : __matches_(__a),
5381       __unmatched_(),
5382       __prefix_(),
5383       __suffix_(),
5384       __ready_(false),
5385       __position_start_()
5386 {
5387 }
5388
5389 template <class _BidirectionalIterator, class _Allocator>
5390 void
5391 match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
5392                          _BidirectionalIterator __f, _BidirectionalIterator __l,
5393                          bool __no_update_pos)
5394 {
5395     __unmatched_.first   = __l;
5396     __unmatched_.second  = __l;
5397     __unmatched_.matched = false;
5398     __matches_.assign(__s, __unmatched_);
5399     __prefix_.first      = __f;
5400     __prefix_.second     = __f;
5401     __prefix_.matched    = false;
5402     __suffix_ = __unmatched_;
5403     if (!__no_update_pos)
5404         __position_start_ = __prefix_.first;
5405     __ready_ = true;
5406 }
5407
5408 template <class _BidirectionalIterator, class _Allocator>
5409 template <class _OutputIter>
5410 _OutputIter
5411 match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __output_iter,
5412         const char_type* __fmt_first, const char_type* __fmt_last,
5413         regex_constants::match_flag_type __flags) const
5414 {
5415     if (__flags & regex_constants::format_sed)
5416     {
5417         for (; __fmt_first != __fmt_last; ++__fmt_first)
5418         {
5419             if (*__fmt_first == '&')
5420                 __output_iter = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5421                                    __output_iter);
5422             else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
5423             {
5424                 ++__fmt_first;
5425                 if ('0' <= *__fmt_first && *__fmt_first <= '9')
5426                 {
5427                     size_t __i = *__fmt_first - '0';
5428                     __output_iter = _VSTD::copy((*this)[__i].first,
5429                                         (*this)[__i].second, __output_iter);
5430                 }
5431                 else
5432                 {
5433                     *__output_iter = *__fmt_first;
5434                     ++__output_iter;
5435                 }
5436             }
5437             else
5438             {
5439                 *__output_iter = *__fmt_first;
5440                 ++__output_iter;
5441             }
5442         }
5443     }
5444     else
5445     {
5446         for (; __fmt_first != __fmt_last; ++__fmt_first)
5447         {
5448             if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
5449             {
5450                 switch (__fmt_first[1])
5451                 {
5452                 case '$':
5453                     *__output_iter = *++__fmt_first;
5454                     ++__output_iter;
5455                     break;
5456                 case '&':
5457                     ++__fmt_first;
5458                     __output_iter = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5459                                        __output_iter);
5460                     break;
5461                 case '`':
5462                     ++__fmt_first;
5463                     __output_iter = _VSTD::copy(__prefix_.first, __prefix_.second, __output_iter);
5464                     break;
5465                 case '\'':
5466                     ++__fmt_first;
5467                     __output_iter = _VSTD::copy(__suffix_.first, __suffix_.second, __output_iter);
5468                     break;
5469                 default:
5470                     if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5471                     {
5472                         ++__fmt_first;
5473                         size_t __idx = *__fmt_first - '0';
5474                         if (__fmt_first + 1 != __fmt_last &&
5475                             '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5476                         {
5477                             ++__fmt_first;
5478                             if (__idx >= std::numeric_limits<size_t>::max() / 10)
5479                                 __throw_regex_error<regex_constants::error_escape>();
5480                             __idx = 10 * __idx + *__fmt_first - '0';
5481                         }
5482                         __output_iter = _VSTD::copy((*this)[__idx].first,
5483                                             (*this)[__idx].second, __output_iter);
5484                     }
5485                     else
5486                     {
5487                         *__output_iter = *__fmt_first;
5488                         ++__output_iter;
5489                     }
5490                     break;
5491                 }
5492             }
5493             else
5494             {
5495                 *__output_iter = *__fmt_first;
5496                 ++__output_iter;
5497             }
5498         }
5499     }
5500     return __output_iter;
5501 }
5502
5503 template <class _BidirectionalIterator, class _Allocator>
5504 void
5505 match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
5506 {
5507     using _VSTD::swap;
5508     swap(__matches_, __m.__matches_);
5509     swap(__unmatched_, __m.__unmatched_);
5510     swap(__prefix_, __m.__prefix_);
5511     swap(__suffix_, __m.__suffix_);
5512     swap(__position_start_, __m.__position_start_);
5513     swap(__ready_, __m.__ready_);
5514 }
5515
5516 typedef match_results<const char*>             cmatch;
5517 typedef match_results<const wchar_t*>          wcmatch;
5518 typedef match_results<string::const_iterator>  smatch;
5519 typedef match_results<wstring::const_iterator> wsmatch;
5520
5521 template <class _BidirectionalIterator, class _Allocator>
5522 bool
5523 operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
5524            const match_results<_BidirectionalIterator, _Allocator>& __y)
5525 {
5526     if (__x.__ready_ != __y.__ready_)
5527         return false;
5528     if (!__x.__ready_)
5529         return true;
5530     return __x.__matches_ == __y.__matches_ &&
5531            __x.__prefix_ == __y.__prefix_ &&
5532            __x.__suffix_ == __y.__suffix_;
5533 }
5534
5535 template <class _BidirectionalIterator, class _Allocator>
5536 inline _LIBCPP_INLINE_VISIBILITY
5537 bool
5538 operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
5539            const match_results<_BidirectionalIterator, _Allocator>& __y)
5540 {
5541     return !(__x == __y);
5542 }
5543
5544 template <class _BidirectionalIterator, class _Allocator>
5545 inline _LIBCPP_INLINE_VISIBILITY
5546 void
5547 swap(match_results<_BidirectionalIterator, _Allocator>& __x,
5548      match_results<_BidirectionalIterator, _Allocator>& __y)
5549 {
5550     __x.swap(__y);
5551 }
5552
5553 // regex_search
5554
5555 template <class _CharT, class _Traits>
5556 template <class _Allocator>
5557 bool
5558 basic_regex<_CharT, _Traits>::__match_at_start_ecma(
5559         const _CharT* __first, const _CharT* __last,
5560         match_results<const _CharT*, _Allocator>& __m,
5561         regex_constants::match_flag_type __flags, bool __at_first) const
5562 {
5563     vector<__state> __states;
5564     __node* __st = __start_.get();
5565     if (__st)
5566     {
5567         sub_match<const _CharT*> __unmatched;
5568         __unmatched.first   = __last;
5569         __unmatched.second  = __last;
5570         __unmatched.matched = false;
5571
5572         __states.push_back(__state());
5573         __states.back().__do_ = 0;
5574         __states.back().__first_ = __first;
5575         __states.back().__current_ = __first;
5576         __states.back().__last_ = __last;
5577         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5578         __states.back().__loop_data_.resize(__loop_count());
5579         __states.back().__node_ = __st;
5580         __states.back().__flags_ = __flags;
5581         __states.back().__at_first_ = __at_first;
5582         int __counter = 0;
5583         int __length = __last - __first;
5584         do
5585         {
5586             ++__counter;
5587             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
5588                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5589               __throw_regex_error<regex_constants::error_complexity>();
5590             __state& __s = __states.back();
5591             if (__s.__node_)
5592                 __s.__node_->__exec(__s);
5593             switch (__s.__do_)
5594             {
5595             case __state::__end_state:
5596                 if ((__flags & regex_constants::match_not_null) &&
5597                     __s.__current_ == __first)
5598                 {
5599                   __states.pop_back();
5600                   break;
5601                 }
5602                 if ((__flags & regex_constants::__full_match) &&
5603                     __s.__current_ != __last)
5604                 {
5605                   __states.pop_back();
5606                   break;
5607                 }
5608                 __m.__matches_[0].first = __first;
5609                 __m.__matches_[0].second = _VSTD::next(__first, __s.__current_ - __first);
5610                 __m.__matches_[0].matched = true;
5611                 for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
5612                     __m.__matches_[__i+1] = __s.__sub_matches_[__i];
5613                 return true;
5614             case __state::__accept_and_consume:
5615             case __state::__repeat:
5616             case __state::__accept_but_not_consume:
5617                 break;
5618             case __state::__split:
5619                 {
5620                 __state __snext = __s;
5621                 __s.__node_->__exec_split(true, __s);
5622                 __snext.__node_->__exec_split(false, __snext);
5623                 __states.push_back(_VSTD::move(__snext));
5624                 }
5625                 break;
5626             case __state::__reject:
5627                 __states.pop_back();
5628                 break;
5629             default:
5630                 __throw_regex_error<regex_constants::__re_err_unknown>();
5631                 break;
5632
5633             }
5634         } while (!__states.empty());
5635     }
5636     return false;
5637 }
5638
5639 template <class _CharT, class _Traits>
5640 template <class _Allocator>
5641 bool
5642 basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
5643         const _CharT* __first, const _CharT* __last,
5644         match_results<const _CharT*, _Allocator>& __m,
5645         regex_constants::match_flag_type __flags, bool __at_first) const
5646 {
5647     deque<__state> __states;
5648     ptrdiff_t __highest_j = 0;
5649     ptrdiff_t _Np = _VSTD::distance(__first, __last);
5650     __node* __st = __start_.get();
5651     if (__st)
5652     {
5653         __states.push_back(__state());
5654         __states.back().__do_ = 0;
5655         __states.back().__first_ = __first;
5656         __states.back().__current_ = __first;
5657         __states.back().__last_ = __last;
5658         __states.back().__loop_data_.resize(__loop_count());
5659         __states.back().__node_ = __st;
5660         __states.back().__flags_ = __flags;
5661         __states.back().__at_first_ = __at_first;
5662         bool __matched = false;
5663         int __counter = 0;
5664         int __length = __last - __first;
5665         do
5666         {
5667             ++__counter;
5668             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
5669                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5670               __throw_regex_error<regex_constants::error_complexity>();
5671             __state& __s = __states.back();
5672             if (__s.__node_)
5673                 __s.__node_->__exec(__s);
5674             switch (__s.__do_)
5675             {
5676             case __state::__end_state:
5677                 if ((__flags & regex_constants::match_not_null) &&
5678                     __s.__current_ == __first)
5679                 {
5680                   __states.pop_back();
5681                   break;
5682                 }
5683                 if ((__flags & regex_constants::__full_match) &&
5684                     __s.__current_ != __last)
5685                 {
5686                   __states.pop_back();
5687                   break;
5688                 }
5689                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5690                     __highest_j = __s.__current_ - __s.__first_;
5691                 __matched = true;
5692                 if (__highest_j == _Np)
5693                     __states.clear();
5694                 else
5695                     __states.pop_back();
5696                 break;
5697             case __state::__consume_input:
5698                 break;
5699             case __state::__accept_and_consume:
5700                 __states.push_front(_VSTD::move(__s));
5701                 __states.pop_back();
5702                 break;
5703             case __state::__repeat:
5704             case __state::__accept_but_not_consume:
5705                 break;
5706             case __state::__split:
5707                 {
5708                 __state __snext = __s;
5709                 __s.__node_->__exec_split(true, __s);
5710                 __snext.__node_->__exec_split(false, __snext);
5711                 __states.push_back(_VSTD::move(__snext));
5712                 }
5713                 break;
5714             case __state::__reject:
5715                 __states.pop_back();
5716                 break;
5717             default:
5718                 __throw_regex_error<regex_constants::__re_err_unknown>();
5719                 break;
5720             }
5721         } while (!__states.empty());
5722         if (__matched)
5723         {
5724             __m.__matches_[0].first = __first;
5725             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5726             __m.__matches_[0].matched = true;
5727             return true;
5728         }
5729     }
5730     return false;
5731 }
5732
5733 template <class _CharT, class _Traits>
5734 template <class _Allocator>
5735 bool
5736 basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
5737         const _CharT* __first, const _CharT* __last,
5738         match_results<const _CharT*, _Allocator>& __m,
5739         regex_constants::match_flag_type __flags, bool __at_first) const
5740 {
5741     vector<__state> __states;
5742     __state __best_state;
5743     ptrdiff_t __j = 0;
5744     ptrdiff_t __highest_j = 0;
5745     ptrdiff_t _Np = _VSTD::distance(__first, __last);
5746     __node* __st = __start_.get();
5747     if (__st)
5748     {
5749         sub_match<const _CharT*> __unmatched;
5750         __unmatched.first   = __last;
5751         __unmatched.second  = __last;
5752         __unmatched.matched = false;
5753
5754         __states.push_back(__state());
5755         __states.back().__do_ = 0;
5756         __states.back().__first_ = __first;
5757         __states.back().__current_ = __first;
5758         __states.back().__last_ = __last;
5759         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5760         __states.back().__loop_data_.resize(__loop_count());
5761         __states.back().__node_ = __st;
5762         __states.back().__flags_ = __flags;
5763         __states.back().__at_first_ = __at_first;
5764         const _CharT* __current = __first;
5765         bool __matched = false;
5766         int __counter = 0;
5767         int __length = __last - __first;
5768         do
5769         {
5770             ++__counter;
5771             if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
5772                 __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
5773               __throw_regex_error<regex_constants::error_complexity>();
5774             __state& __s = __states.back();
5775             if (__s.__node_)
5776                 __s.__node_->__exec(__s);
5777             switch (__s.__do_)
5778             {
5779             case __state::__end_state:
5780                 if ((__flags & regex_constants::match_not_null) &&
5781                     __s.__current_ == __first)
5782                 {
5783                   __states.pop_back();
5784                   break;
5785                 }
5786                 if ((__flags & regex_constants::__full_match) &&
5787                     __s.__current_ != __last)
5788                 {
5789                   __states.pop_back();
5790                   break;
5791                 }
5792                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5793                 {
5794                     __highest_j = __s.__current_ - __s.__first_;
5795                     __best_state = __s;
5796                 }
5797                 __matched = true;
5798                 if (__highest_j == _Np)
5799                     __states.clear();
5800                 else
5801                     __states.pop_back();
5802                 break;
5803             case __state::__accept_and_consume:
5804                 __j += __s.__current_ - __current;
5805                 __current = __s.__current_;
5806                 break;
5807             case __state::__repeat:
5808             case __state::__accept_but_not_consume:
5809                 break;
5810             case __state::__split:
5811                 {
5812                 __state __snext = __s;
5813                 __s.__node_->__exec_split(true, __s);
5814                 __snext.__node_->__exec_split(false, __snext);
5815                 __states.push_back(_VSTD::move(__snext));
5816                 }
5817                 break;
5818             case __state::__reject:
5819                 __states.pop_back();
5820                 break;
5821             default:
5822                 __throw_regex_error<regex_constants::__re_err_unknown>();
5823                 break;
5824             }
5825         } while (!__states.empty());
5826         if (__matched)
5827         {
5828             __m.__matches_[0].first = __first;
5829             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5830             __m.__matches_[0].matched = true;
5831             for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
5832                 __m.__matches_[__i+1] = __best_state.__sub_matches_[__i];
5833             return true;
5834         }
5835     }
5836     return false;
5837 }
5838
5839 template <class _CharT, class _Traits>
5840 template <class _Allocator>
5841 bool
5842 basic_regex<_CharT, _Traits>::__match_at_start(
5843         const _CharT* __first, const _CharT* __last,
5844         match_results<const _CharT*, _Allocator>& __m,
5845         regex_constants::match_flag_type __flags, bool __at_first) const
5846 {
5847     if ((__flags_ & 0x1F0) == ECMAScript)
5848         return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
5849     if (mark_count() == 0)
5850         return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
5851     return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
5852 }
5853
5854 template <class _CharT, class _Traits>
5855 template <class _Allocator>
5856 bool
5857 basic_regex<_CharT, _Traits>::__search(
5858         const _CharT* __first, const _CharT* __last,
5859         match_results<const _CharT*, _Allocator>& __m,
5860         regex_constants::match_flag_type __flags) const
5861 {
5862     __m.__init(1 + mark_count(), __first, __last,
5863                                     __flags & regex_constants::__no_update_pos);
5864     if (__match_at_start(__first, __last, __m, __flags,
5865                                     !(__flags & regex_constants::__no_update_pos)))
5866     {
5867         __m.__prefix_.second = __m[0].first;
5868         __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5869         __m.__suffix_.first = __m[0].second;
5870         __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5871         return true;
5872     }
5873     if (__first != __last && !(__flags & regex_constants::match_continuous))
5874     {
5875         __flags |= regex_constants::match_prev_avail;
5876         for (++__first; __first != __last; ++__first)
5877         {
5878             __m.__matches_.assign(__m.size(), __m.__unmatched_);
5879             if (__match_at_start(__first, __last, __m, __flags, false))
5880             {
5881                 __m.__prefix_.second = __m[0].first;
5882                 __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5883                 __m.__suffix_.first = __m[0].second;
5884                 __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5885                 return true;
5886             }
5887             __m.__matches_.assign(__m.size(), __m.__unmatched_);
5888         }
5889     }
5890     __m.__matches_.clear();
5891     return false;
5892 }
5893
5894 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5895 inline _LIBCPP_INLINE_VISIBILITY
5896 bool
5897 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5898              match_results<_BidirectionalIterator, _Allocator>& __m,
5899              const basic_regex<_CharT, _Traits>& __e,
5900              regex_constants::match_flag_type __flags = regex_constants::match_default)
5901 {
5902     int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
5903     basic_string<_CharT> __s(_VSTD::prev(__first, __offset), __last);
5904     match_results<const _CharT*> __mc;
5905     bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
5906     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5907     return __r;
5908 }
5909
5910 template <class _Iter, class _Allocator, class _CharT, class _Traits>
5911 inline _LIBCPP_INLINE_VISIBILITY
5912 bool
5913 regex_search(__wrap_iter<_Iter> __first,
5914              __wrap_iter<_Iter> __last,
5915              match_results<__wrap_iter<_Iter>, _Allocator>& __m,
5916              const basic_regex<_CharT, _Traits>& __e,
5917              regex_constants::match_flag_type __flags = regex_constants::match_default)
5918 {
5919     match_results<const _CharT*> __mc;
5920     bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
5921     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5922     return __r;
5923 }
5924
5925 template <class _Allocator, class _CharT, class _Traits>
5926 inline _LIBCPP_INLINE_VISIBILITY
5927 bool
5928 regex_search(const _CharT* __first, const _CharT* __last,
5929              match_results<const _CharT*, _Allocator>& __m,
5930              const basic_regex<_CharT, _Traits>& __e,
5931              regex_constants::match_flag_type __flags = regex_constants::match_default)
5932 {
5933     return __e.__search(__first, __last, __m, __flags);
5934 }
5935
5936 template <class _BidirectionalIterator, class _CharT, class _Traits>
5937 inline _LIBCPP_INLINE_VISIBILITY
5938 bool
5939 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5940              const basic_regex<_CharT, _Traits>& __e,
5941              regex_constants::match_flag_type __flags = regex_constants::match_default)
5942 {
5943     basic_string<_CharT> __s(__first, __last);
5944     match_results<const _CharT*> __mc;
5945     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5946 }
5947
5948 template <class _CharT, class _Traits>
5949 inline _LIBCPP_INLINE_VISIBILITY
5950 bool
5951 regex_search(const _CharT* __first, const _CharT* __last,
5952              const basic_regex<_CharT, _Traits>& __e,
5953              regex_constants::match_flag_type __flags = regex_constants::match_default)
5954 {
5955     match_results<const _CharT*> __mc;
5956     return __e.__search(__first, __last, __mc, __flags);
5957 }
5958
5959 template <class _CharT, class _Allocator, class _Traits>
5960 inline _LIBCPP_INLINE_VISIBILITY
5961 bool
5962 regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
5963              const basic_regex<_CharT, _Traits>& __e,
5964              regex_constants::match_flag_type __flags = regex_constants::match_default)
5965 {
5966     return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
5967 }
5968
5969 template <class _CharT, class _Traits>
5970 inline _LIBCPP_INLINE_VISIBILITY
5971 bool
5972 regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
5973              regex_constants::match_flag_type __flags = regex_constants::match_default)
5974 {
5975     match_results<const _CharT*> __m;
5976     return _VSTD::regex_search(__str, __m, __e, __flags);
5977 }
5978
5979 template <class _ST, class _SA, class _CharT, class _Traits>
5980 inline _LIBCPP_INLINE_VISIBILITY
5981 bool
5982 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5983              const basic_regex<_CharT, _Traits>& __e,
5984              regex_constants::match_flag_type __flags = regex_constants::match_default)
5985 {
5986     match_results<const _CharT*> __mc;
5987     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5988 }
5989
5990 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5991 inline _LIBCPP_INLINE_VISIBILITY
5992 bool
5993 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5994              match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5995              const basic_regex<_CharT, _Traits>& __e,
5996              regex_constants::match_flag_type __flags = regex_constants::match_default)
5997 {
5998     match_results<const _CharT*> __mc;
5999     bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
6000     __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
6001     return __r;
6002 }
6003
6004 #if _LIBCPP_STD_VER > 11
6005 template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
6006 bool
6007 regex_search(const basic_string<_Cp, _ST, _SA>&& __s,
6008              match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
6009              const basic_regex<_Cp, _Tp>& __e,
6010              regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
6011 #endif
6012
6013 // regex_match
6014
6015 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
6016 bool
6017 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
6018             match_results<_BidirectionalIterator, _Allocator>& __m,
6019             const basic_regex<_CharT, _Traits>& __e,
6020             regex_constants::match_flag_type __flags = regex_constants::match_default)
6021 {
6022     bool __r = _VSTD::regex_search(
6023         __first, __last, __m, __e,
6024         __flags | regex_constants::match_continuous |
6025         regex_constants::__full_match);
6026     if (__r)
6027     {
6028         __r = !__m.suffix().matched;
6029         if (!__r)
6030             __m.__matches_.clear();
6031     }
6032     return __r;
6033 }
6034
6035 template <class _BidirectionalIterator, class _CharT, class _Traits>
6036 inline _LIBCPP_INLINE_VISIBILITY
6037 bool
6038 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
6039             const basic_regex<_CharT, _Traits>& __e,
6040             regex_constants::match_flag_type __flags = regex_constants::match_default)
6041 {
6042     match_results<_BidirectionalIterator> __m;
6043     return _VSTD::regex_match(__first, __last, __m, __e, __flags);
6044 }
6045
6046 template <class _CharT, class _Allocator, class _Traits>
6047 inline _LIBCPP_INLINE_VISIBILITY
6048 bool
6049 regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
6050             const basic_regex<_CharT, _Traits>& __e,
6051             regex_constants::match_flag_type __flags = regex_constants::match_default)
6052 {
6053     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
6054 }
6055
6056 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6057 inline _LIBCPP_INLINE_VISIBILITY
6058 bool
6059 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6060             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6061             const basic_regex<_CharT, _Traits>& __e,
6062             regex_constants::match_flag_type __flags = regex_constants::match_default)
6063 {
6064     return _VSTD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
6065 }
6066
6067 #if _LIBCPP_STD_VER > 11
6068 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6069 inline _LIBCPP_INLINE_VISIBILITY
6070 bool
6071 regex_match(const basic_string<_CharT, _ST, _SA>&& __s,
6072             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6073             const basic_regex<_CharT, _Traits>& __e,
6074             regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
6075 #endif
6076
6077 template <class _CharT, class _Traits>
6078 inline _LIBCPP_INLINE_VISIBILITY
6079 bool
6080 regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
6081             regex_constants::match_flag_type __flags = regex_constants::match_default)
6082 {
6083     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
6084 }
6085
6086 template <class _ST, class _SA, class _CharT, class _Traits>
6087 inline _LIBCPP_INLINE_VISIBILITY
6088 bool
6089 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6090             const basic_regex<_CharT, _Traits>& __e,
6091             regex_constants::match_flag_type __flags = regex_constants::match_default)
6092 {
6093     return _VSTD::regex_match(__s.begin(), __s.end(), __e, __flags);
6094 }
6095
6096 // regex_iterator
6097
6098 template <class _BidirectionalIterator,
6099           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6100           class _Traits = regex_traits<_CharT> >
6101 class _LIBCPP_TEMPLATE_VIS regex_iterator
6102 {
6103 public:
6104     typedef basic_regex<_CharT, _Traits>          regex_type;
6105     typedef match_results<_BidirectionalIterator> value_type;
6106     typedef ptrdiff_t                             difference_type;
6107     typedef const value_type*                     pointer;
6108     typedef const value_type&                     reference;
6109     typedef forward_iterator_tag                  iterator_category;
6110
6111 private:
6112     _BidirectionalIterator           __begin_;
6113     _BidirectionalIterator           __end_;
6114     const regex_type*                __pregex_;
6115     regex_constants::match_flag_type __flags_;
6116     value_type                       __match_;
6117
6118 public:
6119     regex_iterator();
6120     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6121                    const regex_type& __re,
6122                    regex_constants::match_flag_type __m
6123                                               = regex_constants::match_default);
6124 #if _LIBCPP_STD_VER > 11
6125     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6126                    const regex_type&& __re,
6127                    regex_constants::match_flag_type __m
6128                                      = regex_constants::match_default) = delete;
6129 #endif
6130
6131     bool operator==(const regex_iterator& __x) const;
6132     _LIBCPP_INLINE_VISIBILITY
6133     bool operator!=(const regex_iterator& __x) const {return !(*this == __x);}
6134
6135     _LIBCPP_INLINE_VISIBILITY
6136     reference operator*() const {return  __match_;}
6137     _LIBCPP_INLINE_VISIBILITY
6138     pointer operator->() const  {return &__match_;}
6139
6140     regex_iterator& operator++();
6141     _LIBCPP_INLINE_VISIBILITY
6142     regex_iterator operator++(int)
6143     {
6144         regex_iterator __t(*this);
6145         ++(*this);
6146         return __t;
6147     }
6148 };
6149
6150 template <class _BidirectionalIterator, class _CharT, class _Traits>
6151 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
6152     : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_()
6153 {
6154 }
6155
6156 template <class _BidirectionalIterator, class _CharT, class _Traits>
6157 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6158     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6159                    const regex_type& __re, regex_constants::match_flag_type __m)
6160     : __begin_(__a),
6161       __end_(__b),
6162       __pregex_(&__re),
6163       __flags_(__m)
6164 {
6165     _VSTD::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
6166 }
6167
6168 template <class _BidirectionalIterator, class _CharT, class _Traits>
6169 bool
6170 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6171     operator==(const regex_iterator& __x) const
6172 {
6173     if (__match_.empty() && __x.__match_.empty())
6174         return true;
6175     if (__match_.empty() || __x.__match_.empty())
6176         return false;
6177     return __begin_ == __x.__begin_       &&
6178            __end_ == __x.__end_           &&
6179            __pregex_ == __x.__pregex_     &&
6180            __flags_ == __x.__flags_       &&
6181            __match_[0] == __x.__match_[0];
6182 }
6183
6184 template <class _BidirectionalIterator, class _CharT, class _Traits>
6185 regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
6186 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6187 {
6188     __flags_ |= regex_constants::__no_update_pos;
6189     _BidirectionalIterator __start = __match_[0].second;
6190     if (__match_[0].first == __match_[0].second)
6191     {
6192         if (__start == __end_)
6193         {
6194             __match_ = value_type();
6195             return *this;
6196         }
6197         else if (_VSTD::regex_search(__start, __end_, __match_, *__pregex_,
6198                                     __flags_ | regex_constants::match_not_null |
6199                                     regex_constants::match_continuous))
6200             return *this;
6201         else
6202             ++__start;
6203     }
6204     __flags_ |= regex_constants::match_prev_avail;
6205     if (!_VSTD::regex_search(__start, __end_, __match_, *__pregex_, __flags_))
6206         __match_ = value_type();
6207     return *this;
6208 }
6209
6210 typedef regex_iterator<const char*>             cregex_iterator;
6211 typedef regex_iterator<const wchar_t*>          wcregex_iterator;
6212 typedef regex_iterator<string::const_iterator>  sregex_iterator;
6213 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
6214
6215 // regex_token_iterator
6216
6217 template <class _BidirectionalIterator,
6218           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6219           class _Traits = regex_traits<_CharT> >
6220 class _LIBCPP_TEMPLATE_VIS regex_token_iterator
6221 {
6222 public:
6223     typedef basic_regex<_CharT, _Traits>      regex_type;
6224     typedef sub_match<_BidirectionalIterator> value_type;
6225     typedef ptrdiff_t                         difference_type;
6226     typedef const value_type*                 pointer;
6227     typedef const value_type&                 reference;
6228     typedef forward_iterator_tag              iterator_category;
6229
6230 private:
6231     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
6232
6233     _Position         __position_;
6234     const value_type* __result_;
6235     value_type        __suffix_;
6236     ptrdiff_t         __n_;
6237     vector<int>       __subs_;
6238
6239 public:
6240     regex_token_iterator();
6241     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6242                          const regex_type& __re, int __submatch = 0,
6243                          regex_constants::match_flag_type __m =
6244                                                 regex_constants::match_default);
6245 #if _LIBCPP_STD_VER > 11
6246     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6247                          const regex_type&& __re, int __submatch = 0,
6248                          regex_constants::match_flag_type __m =
6249                                        regex_constants::match_default) = delete;
6250 #endif
6251
6252     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6253                          const regex_type& __re, const vector<int>& __submatches,
6254                          regex_constants::match_flag_type __m =
6255                                                 regex_constants::match_default);
6256 #if _LIBCPP_STD_VER > 11
6257     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6258                          const regex_type&& __re, const vector<int>& __submatches,
6259                          regex_constants::match_flag_type __m =
6260                                      regex_constants::match_default) = delete;
6261 #endif
6262
6263 #ifndef _LIBCPP_CXX03_LANG
6264     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6265                          const regex_type& __re,
6266                          initializer_list<int> __submatches,
6267                          regex_constants::match_flag_type __m =
6268                                                 regex_constants::match_default);
6269
6270 #if _LIBCPP_STD_VER > 11
6271     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6272                          const regex_type&& __re,
6273                          initializer_list<int> __submatches,
6274                          regex_constants::match_flag_type __m =
6275                                        regex_constants::match_default) = delete;
6276 #endif
6277 #endif  // _LIBCPP_CXX03_LANG
6278     template <size_t _Np>
6279         regex_token_iterator(_BidirectionalIterator __a,
6280                              _BidirectionalIterator __b,
6281                              const regex_type& __re,
6282                              const int (&__submatches)[_Np],
6283                              regex_constants::match_flag_type __m =
6284                                                 regex_constants::match_default);
6285 #if _LIBCPP_STD_VER > 11
6286     template <std::size_t _Np>
6287         regex_token_iterator(_BidirectionalIterator __a,
6288                              _BidirectionalIterator __b,
6289                              const regex_type&& __re,
6290                              const int (&__submatches)[_Np],
6291                              regex_constants::match_flag_type __m =
6292                                       regex_constants::match_default) = delete;
6293 #endif
6294
6295     regex_token_iterator(const regex_token_iterator&);
6296     regex_token_iterator& operator=(const regex_token_iterator&);
6297
6298     bool operator==(const regex_token_iterator& __x) const;
6299     _LIBCPP_INLINE_VISIBILITY
6300     bool operator!=(const regex_token_iterator& __x) const {return !(*this == __x);}
6301
6302     _LIBCPP_INLINE_VISIBILITY
6303     const value_type& operator*() const {return *__result_;}
6304     _LIBCPP_INLINE_VISIBILITY
6305     const value_type* operator->() const {return __result_;}
6306
6307     regex_token_iterator& operator++();
6308     _LIBCPP_INLINE_VISIBILITY
6309     regex_token_iterator operator++(int)
6310     {
6311         regex_token_iterator __t(*this);
6312         ++(*this);
6313         return __t;
6314     }
6315
6316 private:
6317     void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
6318     void __establish_result () {
6319         if (__subs_[__n_] == -1)
6320             __result_ = &__position_->prefix();
6321         else
6322             __result_ = &(*__position_)[__subs_[__n_]];
6323         }
6324 };
6325
6326 template <class _BidirectionalIterator, class _CharT, class _Traits>
6327 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6328     regex_token_iterator()
6329     : __result_(nullptr),
6330       __suffix_(),
6331       __n_(0)
6332 {
6333 }
6334
6335 template <class _BidirectionalIterator, class _CharT, class _Traits>
6336 void
6337 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6338     __init(_BidirectionalIterator __a, _BidirectionalIterator __b)
6339 {
6340     if (__position_ != _Position())
6341         __establish_result ();
6342     else if (__subs_[__n_] == -1)
6343     {
6344         __suffix_.matched = true;
6345         __suffix_.first = __a;
6346         __suffix_.second = __b;
6347         __result_ = &__suffix_;
6348     }
6349     else
6350         __result_ = nullptr;
6351 }
6352
6353 template <class _BidirectionalIterator, class _CharT, class _Traits>
6354 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6355     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6356                          const regex_type& __re, int __submatch,
6357                          regex_constants::match_flag_type __m)
6358     : __position_(__a, __b, __re, __m),
6359       __n_(0),
6360       __subs_(1, __submatch)
6361 {
6362     __init(__a, __b);
6363 }
6364
6365 template <class _BidirectionalIterator, class _CharT, class _Traits>
6366 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6367     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6368                          const regex_type& __re, const vector<int>& __submatches,
6369                          regex_constants::match_flag_type __m)
6370     : __position_(__a, __b, __re, __m),
6371       __n_(0),
6372       __subs_(__submatches)
6373 {
6374     __init(__a, __b);
6375 }
6376
6377 #ifndef _LIBCPP_CXX03_LANG
6378
6379 template <class _BidirectionalIterator, class _CharT, class _Traits>
6380 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6381     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6382                          const regex_type& __re,
6383                          initializer_list<int> __submatches,
6384                          regex_constants::match_flag_type __m)
6385     : __position_(__a, __b, __re, __m),
6386       __n_(0),
6387       __subs_(__submatches)
6388 {
6389     __init(__a, __b);
6390 }
6391
6392 #endif  // _LIBCPP_CXX03_LANG
6393
6394 template <class _BidirectionalIterator, class _CharT, class _Traits>
6395 template <size_t _Np>
6396 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6397     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6398                              const regex_type& __re,
6399                              const int (&__submatches)[_Np],
6400                              regex_constants::match_flag_type __m)
6401     : __position_(__a, __b, __re, __m),
6402       __n_(0),
6403       __subs_(__submatches, __submatches + _Np)
6404 {
6405     __init(__a, __b);
6406 }
6407
6408 template <class _BidirectionalIterator, class _CharT, class _Traits>
6409 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6410     regex_token_iterator(const regex_token_iterator& __x)
6411     : __position_(__x.__position_),
6412       __result_(__x.__result_),
6413       __suffix_(__x.__suffix_),
6414       __n_(__x.__n_),
6415       __subs_(__x.__subs_)
6416 {
6417     if (__x.__result_ == &__x.__suffix_)
6418         __result_ = &__suffix_;
6419     else if ( __result_ != nullptr )
6420         __establish_result ();
6421 }
6422
6423 template <class _BidirectionalIterator, class _CharT, class _Traits>
6424 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6425 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6426     operator=(const regex_token_iterator& __x)
6427 {
6428     if (this != &__x)
6429     {
6430         __position_ = __x.__position_;
6431         if (__x.__result_ == &__x.__suffix_)
6432             __result_ = &__suffix_;
6433         else
6434             __result_ = __x.__result_;
6435         __suffix_ = __x.__suffix_;
6436         __n_ = __x.__n_;
6437         __subs_ = __x.__subs_;
6438
6439         if ( __result_ != nullptr && __result_ != &__suffix_ )
6440             __establish_result();
6441     }
6442     return *this;
6443 }
6444
6445 template <class _BidirectionalIterator, class _CharT, class _Traits>
6446 bool
6447 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6448     operator==(const regex_token_iterator& __x) const
6449 {
6450     if (__result_ == nullptr && __x.__result_ == nullptr)
6451         return true;
6452     if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ &&
6453             __suffix_ == __x.__suffix_)
6454         return true;
6455     if (__result_ == nullptr || __x.__result_ == nullptr)
6456         return false;
6457     if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
6458         return false;
6459     return __position_ == __x.__position_ && __n_ == __x.__n_ &&
6460            __subs_ == __x.__subs_;
6461 }
6462
6463 template <class _BidirectionalIterator, class _CharT, class _Traits>
6464 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6465 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6466 {
6467     _Position __prev = __position_;
6468     if (__result_ == &__suffix_)
6469         __result_ = nullptr;
6470     else if (static_cast<size_t>(__n_ + 1) < __subs_.size())
6471     {
6472         ++__n_;
6473         __establish_result();
6474     }
6475     else
6476     {
6477         __n_ = 0;
6478         ++__position_;
6479         if (__position_ != _Position())
6480             __establish_result();
6481         else
6482         {
6483             if (_VSTD::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end()
6484                 && __prev->suffix().length() != 0)
6485             {
6486                 __suffix_.matched = true;
6487                 __suffix_.first = __prev->suffix().first;
6488                 __suffix_.second = __prev->suffix().second;
6489                 __result_ = &__suffix_;
6490             }
6491             else
6492                 __result_ = nullptr;
6493         }
6494     }
6495     return *this;
6496 }
6497
6498 typedef regex_token_iterator<const char*>             cregex_token_iterator;
6499 typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
6500 typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
6501 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
6502
6503 // regex_replace
6504
6505 template <class _OutputIterator, class _BidirectionalIterator,
6506           class _Traits, class _CharT>
6507 _OutputIterator
6508 regex_replace(_OutputIterator __output_iter,
6509               _BidirectionalIterator __first, _BidirectionalIterator __last,
6510               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6511               regex_constants::match_flag_type __flags = regex_constants::match_default)
6512 {
6513     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
6514     _Iter __i(__first, __last, __e, __flags);
6515     _Iter __eof;
6516     if (__i == __eof)
6517     {
6518         if (!(__flags & regex_constants::format_no_copy))
6519             __output_iter = _VSTD::copy(__first, __last, __output_iter);
6520     }
6521     else
6522     {
6523         sub_match<_BidirectionalIterator> __lm;
6524         for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i)
6525         {
6526             if (!(__flags & regex_constants::format_no_copy))
6527                 __output_iter = _VSTD::copy(__i->prefix().first, __i->prefix().second, __output_iter);
6528             __output_iter = __i->format(__output_iter, __fmt, __fmt + __len, __flags);
6529             __lm = __i->suffix();
6530             if (__flags & regex_constants::format_first_only)
6531                 break;
6532         }
6533         if (!(__flags & regex_constants::format_no_copy))
6534             __output_iter = _VSTD::copy(__lm.first, __lm.second, __output_iter);
6535     }
6536     return __output_iter;
6537 }
6538
6539 template <class _OutputIterator, class _BidirectionalIterator,
6540           class _Traits, class _CharT, class _ST, class _SA>
6541 inline _LIBCPP_INLINE_VISIBILITY
6542 _OutputIterator
6543 regex_replace(_OutputIterator __output_iter,
6544               _BidirectionalIterator __first, _BidirectionalIterator __last,
6545               const basic_regex<_CharT, _Traits>& __e,
6546               const basic_string<_CharT, _ST, _SA>& __fmt,
6547               regex_constants::match_flag_type __flags = regex_constants::match_default)
6548 {
6549     return _VSTD::regex_replace(__output_iter, __first, __last, __e, __fmt.c_str(), __flags);
6550 }
6551
6552 template <class _Traits, class _CharT, class _ST, class _SA, class _FST,
6553           class _FSA>
6554 inline _LIBCPP_INLINE_VISIBILITY
6555 basic_string<_CharT, _ST, _SA>
6556 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6557               const basic_regex<_CharT, _Traits>& __e,
6558               const basic_string<_CharT, _FST, _FSA>& __fmt,
6559               regex_constants::match_flag_type __flags = regex_constants::match_default)
6560 {
6561     basic_string<_CharT, _ST, _SA> __r;
6562     _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6563                         __fmt.c_str(), __flags);
6564     return __r;
6565 }
6566
6567 template <class _Traits, class _CharT, class _ST, class _SA>
6568 inline _LIBCPP_INLINE_VISIBILITY
6569 basic_string<_CharT, _ST, _SA>
6570 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6571               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6572               regex_constants::match_flag_type __flags = regex_constants::match_default)
6573 {
6574     basic_string<_CharT, _ST, _SA> __r;
6575     _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6576                         __fmt, __flags);
6577     return __r;
6578 }
6579
6580 template <class _Traits, class _CharT, class _ST, class _SA>
6581 inline _LIBCPP_INLINE_VISIBILITY
6582 basic_string<_CharT>
6583 regex_replace(const _CharT* __s,
6584               const basic_regex<_CharT, _Traits>& __e,
6585               const basic_string<_CharT, _ST, _SA>& __fmt,
6586               regex_constants::match_flag_type __flags = regex_constants::match_default)
6587 {
6588     basic_string<_CharT> __r;
6589     _VSTD::regex_replace(back_inserter(__r), __s,
6590                         __s + char_traits<_CharT>::length(__s), __e,
6591                         __fmt.c_str(), __flags);
6592     return __r;
6593 }
6594
6595 template <class _Traits, class _CharT>
6596 inline _LIBCPP_INLINE_VISIBILITY
6597 basic_string<_CharT>
6598 regex_replace(const _CharT* __s,
6599               const basic_regex<_CharT, _Traits>& __e,
6600               const _CharT* __fmt,
6601               regex_constants::match_flag_type __flags = regex_constants::match_default)
6602 {
6603     basic_string<_CharT> __r;
6604     _VSTD::regex_replace(back_inserter(__r), __s,
6605                         __s + char_traits<_CharT>::length(__s), __e,
6606                         __fmt, __flags);
6607     return __r;
6608 }
6609
6610 _LIBCPP_END_NAMESPACE_STD
6611
6612 _LIBCPP_POP_MACROS
6613
6614 #endif  // _LIBCPP_REGEX