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