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