contrib/libc++/include/regex

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