contrib/libc++/include/regex

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