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