contrib/libc++/include/regex

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