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