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