contrib/libc++/include/regex

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