external/bsd/libc++/dist/libcxx/include/regex

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