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