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_HAS_NO_GENERALIZED_INITIALIZERS
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_HAS_NO_GENERALIZED_INITIALIZERS
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_HAS_NO_GENERALIZED_INITIALIZERS
2559     _LIBCPP_INLINE_VISIBILITY
2560     basic_regex& operator=(initializer_list<value_type> __il)
2561         {return assign(__il);}
2562 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
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_HAS_NO_RVALUE_REFERENCES
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_HAS_NO_GENERALIZED_INITIALIZERS
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_HAS_NO_GENERALIZED_INITIALIZERS
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     typedef typename _Traits::string_type string_type;
3961     string_type __collate_name =
3962         __traits_.lookup_collatename(__first, __temp);
3963     if (__collate_name.empty())
3964         __throw_regex_error<regex_constants::error_collate>();
3965     string_type __equiv_name =
3966         __traits_.transform_primary(__collate_name.begin(),
3967                                     __collate_name.end());
3968     if (!__equiv_name.empty())
3969         __ml->__add_equivalence(__equiv_name);
3970     else
3971     {
3972         switch (__collate_name.size())
3973         {
3974         case 1:
3975             __ml->__add_char(__collate_name[0]);
3976             break;
3977         case 2:
3978             __ml->__add_digraph(__collate_name[0], __collate_name[1]);
3979             break;
3980         default:
3981             __throw_regex_error<regex_constants::error_collate>();
3982         }
3983     }
3984     __first = _VSTD::next(__temp, 2);
3985     return __first;
3986 }
3987
3988 template <class _CharT, class _Traits>
3989 template <class _ForwardIterator>
3990 _ForwardIterator
3991 basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
3992                                     _ForwardIterator __last,
3993                                     __bracket_expression<_CharT, _Traits>* __ml)
3994 {
3995     // Found [:
3996     //   This means :] must exist
3997     value_type _Colon_close[2] = {':', ']'};
3998     _ForwardIterator __temp = _VSTD::search(__first, __last, _Colon_close,
3999                                                             _Colon_close+2);
4000     if (__temp == __last)
4001         __throw_regex_error<regex_constants::error_brack>();
4002     // [__first, __temp) contains all text in [: ... :]
4003     typedef typename _Traits::char_class_type char_class_type;
4004     char_class_type __class_type =
4005         __traits_.lookup_classname(__first, __temp, __flags_ & icase);
4006     if (__class_type == 0)
4007         __throw_regex_error<regex_constants::error_brack>();
4008     __ml->__add_class(__class_type);
4009     __first = _VSTD::next(__temp, 2);
4010     return __first;
4011 }
4012
4013 template <class _CharT, class _Traits>
4014 template <class _ForwardIterator>
4015 _ForwardIterator
4016 basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
4017                                                 _ForwardIterator __last,
4018                                                 basic_string<_CharT>& __col_sym)
4019 {
4020     // Found [.
4021     //   This means .] must exist
4022     value_type _Dot_close[2] = {'.', ']'};
4023     _ForwardIterator __temp = _VSTD::search(__first, __last, _Dot_close,
4024                                                             _Dot_close+2);
4025     if (__temp == __last)
4026         __throw_regex_error<regex_constants::error_brack>();
4027     // [__first, __temp) contains all text in [. ... .]
4028     __col_sym = __traits_.lookup_collatename(__first, __temp);
4029     switch (__col_sym.size())
4030     {
4031     case 1:
4032     case 2:
4033         break;
4034     default:
4035         __throw_regex_error<regex_constants::error_collate>();
4036     }
4037     __first = _VSTD::next(__temp, 2);
4038     return __first;
4039 }
4040
4041 template <class _CharT, class _Traits>
4042 template <class _ForwardIterator>
4043 _ForwardIterator
4044 basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
4045                                                 _ForwardIterator __last,
4046                                                 int& __c)
4047 {
4048     if (__first != __last )
4049     {
4050         int __val = __traits_.value(*__first, 10);
4051         if ( __val != -1 )
4052         {
4053             __c = __val;
4054             for (++__first;
4055                  __first != __last && ( __val = __traits_.value(*__first, 10)) != -1;
4056                  ++__first)
4057             {
4058                 __c *= 10;
4059                 __c += __val;
4060             }
4061         }
4062     }
4063     return __first;
4064 }
4065
4066 template <class _CharT, class _Traits>
4067 template <class _ForwardIterator>
4068 _ForwardIterator
4069 basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first,
4070                                                _ForwardIterator __last)
4071 {
4072     __owns_one_state<_CharT>* __sa = __end_;
4073     _ForwardIterator __temp = __parse_alternative(__first, __last);
4074     if (__temp == __first)
4075         __push_empty();
4076     __first = __temp;
4077     while (__first != __last && *__first == '|')
4078     {
4079         __owns_one_state<_CharT>* __sb = __end_;
4080         __temp = __parse_alternative(++__first, __last);
4081         if (__temp == __first)
4082             __push_empty();
4083         __push_alternation(__sa, __sb);
4084         __first = __temp;
4085     }
4086     return __first;
4087 }
4088
4089 template <class _CharT, class _Traits>
4090 template <class _ForwardIterator>
4091 _ForwardIterator
4092 basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first,
4093                                                   _ForwardIterator __last)
4094 {
4095     while (true)
4096     {
4097         _ForwardIterator __temp = __parse_term(__first, __last);
4098         if (__temp == __first)
4099             break;
4100         __first = __temp;
4101     }
4102     return __first;
4103 }
4104
4105 template <class _CharT, class _Traits>
4106 template <class _ForwardIterator>
4107 _ForwardIterator
4108 basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first,
4109                                            _ForwardIterator __last)
4110 {
4111     _ForwardIterator __temp = __parse_assertion(__first, __last);
4112     if (__temp == __first)
4113     {
4114         __owns_one_state<_CharT>* __e = __end_;
4115         unsigned __mexp_begin = __marked_count_;
4116         __temp = __parse_atom(__first, __last);
4117         if (__temp != __first)
4118             __first = __parse_ERE_dupl_symbol(__temp, __last, __e,
4119                                               __mexp_begin+1, __marked_count_+1);
4120     }
4121     else
4122         __first = __temp;
4123     return __first;
4124 }
4125
4126 template <class _CharT, class _Traits>
4127 template <class _ForwardIterator>
4128 _ForwardIterator
4129 basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first,
4130                                                 _ForwardIterator __last)
4131 {
4132     if (__first != __last)
4133     {
4134         switch (*__first)
4135         {
4136         case '^':
4137             __push_l_anchor();
4138             ++__first;
4139             break;
4140         case '$':
4141             __push_r_anchor();
4142             ++__first;
4143             break;
4144         case '\\':
4145             {
4146                 _ForwardIterator __temp = _VSTD::next(__first);
4147                 if (__temp != __last)
4148                 {
4149                     if (*__temp == 'b')
4150                     {
4151                         __push_word_boundary(false);
4152                         __first = ++__temp;
4153                     }
4154                     else if (*__temp == 'B')
4155                     {
4156                         __push_word_boundary(true);
4157                         __first = ++__temp;
4158                     }
4159                 }
4160             }
4161             break;
4162         case '(':
4163             {
4164                 _ForwardIterator __temp = _VSTD::next(__first);
4165                 if (__temp != __last && *__temp == '?')
4166                 {
4167                     if (++__temp != __last)
4168                     {
4169                         switch (*__temp)
4170                         {
4171                         case '=':
4172                             {
4173                                 basic_regex __exp;
4174                                 __exp.__flags_ = __flags_;
4175                                 __temp = __exp.__parse(++__temp, __last);
4176                                 unsigned __mexp = __exp.__marked_count_;
4177                                 __push_lookahead(_VSTD::move(__exp), false, __marked_count_);
4178                                 __marked_count_ += __mexp;
4179                                 if (__temp == __last || *__temp != ')')
4180                                     __throw_regex_error<regex_constants::error_paren>();
4181                                 __first = ++__temp;
4182                             }
4183                             break;
4184                         case '!':
4185                             {
4186                                 basic_regex __exp;
4187                                 __exp.__flags_ = __flags_;
4188                                 __temp = __exp.__parse(++__temp, __last);
4189                                 unsigned __mexp = __exp.__marked_count_;
4190                                 __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
4191                                 __marked_count_ += __mexp;
4192                                 if (__temp == __last || *__temp != ')')
4193                                     __throw_regex_error<regex_constants::error_paren>();
4194                                 __first = ++__temp;
4195                             }
4196                             break;
4197                         }
4198                     }
4199                 }
4200             }
4201             break;
4202         }
4203     }
4204     return __first;
4205 }
4206
4207 template <class _CharT, class _Traits>
4208 template <class _ForwardIterator>
4209 _ForwardIterator
4210 basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first,
4211                                            _ForwardIterator __last)
4212 {
4213     if (__first != __last)
4214     {
4215         switch (*__first)
4216         {
4217         case '.':
4218             __push_match_any_but_newline();
4219             ++__first;
4220             break;
4221         case '\\':
4222             __first = __parse_atom_escape(__first, __last);
4223             break;
4224         case '[':
4225             __first = __parse_bracket_expression(__first, __last);
4226             break;
4227         case '(':
4228             {
4229                 ++__first;
4230                 if (__first == __last)
4231                     __throw_regex_error<regex_constants::error_paren>();
4232                 _ForwardIterator __temp = _VSTD::next(__first);
4233                 if (__temp != __last && *__first == '?' && *__temp == ':')
4234                 {
4235                     ++__open_count_;
4236                     __first = __parse_ecma_exp(++__temp, __last);
4237                     if (__first == __last || *__first != ')')
4238                         __throw_regex_error<regex_constants::error_paren>();
4239                     --__open_count_;
4240                     ++__first;
4241                 }
4242                 else
4243                 {
4244                     __push_begin_marked_subexpression();
4245                     unsigned __temp_count = __marked_count_;
4246                     ++__open_count_;
4247                     __first = __parse_ecma_exp(__first, __last);
4248                     if (__first == __last || *__first != ')')
4249                         __throw_regex_error<regex_constants::error_paren>();
4250                     __push_end_marked_subexpression(__temp_count);
4251                     --__open_count_;
4252                     ++__first;
4253                 }
4254             }
4255             break;
4256         case '*':
4257         case '+':
4258         case '?':
4259         case '{':
4260             __throw_regex_error<regex_constants::error_badrepeat>();
4261             break;
4262         default:
4263             __first = __parse_pattern_character(__first, __last);
4264             break;
4265         }
4266     }
4267     return __first;
4268 }
4269
4270 template <class _CharT, class _Traits>
4271 template <class _ForwardIterator>
4272 _ForwardIterator
4273 basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first,
4274                                                   _ForwardIterator __last)
4275 {
4276     if (__first != __last && *__first == '\\')
4277     {
4278         _ForwardIterator __t1 = _VSTD::next(__first);
4279         if (__t1 == __last)
4280             __throw_regex_error<regex_constants::error_escape>();
4281
4282         _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
4283         if (__t2 != __t1)
4284             __first = __t2;
4285         else
4286         {
4287             __t2 = __parse_character_class_escape(__t1, __last);
4288             if (__t2 != __t1)
4289                 __first = __t2;
4290             else
4291             {
4292                 __t2 = __parse_character_escape(__t1, __last);
4293                 if (__t2 != __t1)
4294                     __first = __t2;
4295             }
4296         }
4297     }
4298     return __first;
4299 }
4300
4301 template <class _CharT, class _Traits>
4302 template <class _ForwardIterator>
4303 _ForwardIterator
4304 basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first,
4305                                                      _ForwardIterator __last)
4306 {
4307     if (__first != __last)
4308     {
4309         if (*__first == '0')
4310         {
4311             __push_char(_CharT());
4312             ++__first;
4313         }
4314         else if ('1' <= *__first && *__first <= '9')
4315         {
4316             unsigned __v = *__first - '0';
4317             for (++__first;
4318                     __first != __last && '0' <= *__first && *__first <= '9'; ++__first)
4319                 __v = 10 * __v + *__first - '0';
4320             if (__v > mark_count())
4321                 __throw_regex_error<regex_constants::error_backref>();
4322             __push_back_ref(__v);
4323         }
4324     }
4325     return __first;
4326 }
4327
4328 template <class _CharT, class _Traits>
4329 template <class _ForwardIterator>
4330 _ForwardIterator
4331 basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first,
4332                                                              _ForwardIterator __last)
4333 {
4334     if (__first != __last)
4335     {
4336         __bracket_expression<_CharT, _Traits>* __ml;
4337         switch (*__first)
4338         {
4339         case 'd':
4340             __ml = __start_matching_list(false);
4341             __ml->__add_class(ctype_base::digit);
4342             ++__first;
4343             break;
4344         case 'D':
4345             __ml = __start_matching_list(true);
4346             __ml->__add_class(ctype_base::digit);
4347             ++__first;
4348             break;
4349         case 's':
4350             __ml = __start_matching_list(false);
4351             __ml->__add_class(ctype_base::space);
4352             ++__first;
4353             break;
4354         case 'S':
4355             __ml = __start_matching_list(true);
4356             __ml->__add_class(ctype_base::space);
4357             ++__first;
4358             break;
4359         case 'w':
4360             __ml = __start_matching_list(false);
4361             __ml->__add_class(ctype_base::alnum);
4362             __ml->__add_char('_');
4363             ++__first;
4364             break;
4365         case 'W':
4366             __ml = __start_matching_list(true);
4367             __ml->__add_class(ctype_base::alnum);
4368             __ml->__add_char('_');
4369             ++__first;
4370             break;
4371         }
4372     }
4373     return __first;
4374 }
4375
4376 template <class _CharT, class _Traits>
4377 template <class _ForwardIterator>
4378 _ForwardIterator
4379 basic_regex<_CharT, _Traits>::__parse_character_escape(_ForwardIterator __first,
4380                                                     _ForwardIterator __last,
4381                                                     basic_string<_CharT>* __str)
4382 {
4383     if (__first != __last)
4384     {
4385         _ForwardIterator __t;
4386         unsigned __sum = 0;
4387         int __hd;
4388         switch (*__first)
4389         {
4390         case 'f':
4391             if (__str)
4392                 *__str = _CharT(0xC);
4393             else
4394                 __push_char(_CharT(0xC));
4395             ++__first;
4396             break;
4397         case 'n':
4398             if (__str)
4399                 *__str = _CharT(0xA);
4400             else
4401                 __push_char(_CharT(0xA));
4402             ++__first;
4403             break;
4404         case 'r':
4405             if (__str)
4406                 *__str = _CharT(0xD);
4407             else
4408                 __push_char(_CharT(0xD));
4409             ++__first;
4410             break;
4411         case 't':
4412             if (__str)
4413                 *__str = _CharT(0x9);
4414             else
4415                 __push_char(_CharT(0x9));
4416             ++__first;
4417             break;
4418         case 'v':
4419             if (__str)
4420                 *__str = _CharT(0xB);
4421             else
4422                 __push_char(_CharT(0xB));
4423             ++__first;
4424             break;
4425         case 'c':
4426             if ((__t = _VSTD::next(__first)) != __last)
4427             {
4428                 if (('A' <= *__t && *__t <= 'Z') ||
4429                     ('a' <= *__t && *__t <= 'z'))
4430                 {
4431                     if (__str)
4432                         *__str = _CharT(*__t % 32);
4433                     else
4434                         __push_char(_CharT(*__t % 32));
4435                     __first = ++__t;
4436                 }
4437                 else
4438                     __throw_regex_error<regex_constants::error_escape>();
4439             }
4440             else
4441                 __throw_regex_error<regex_constants::error_escape>();
4442             break;
4443         case 'u':
4444             ++__first;
4445             if (__first == __last)
4446                 __throw_regex_error<regex_constants::error_escape>();
4447             __hd = __traits_.value(*__first, 16);
4448             if (__hd == -1)
4449                 __throw_regex_error<regex_constants::error_escape>();
4450             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4451             ++__first;
4452             if (__first == __last)
4453                 __throw_regex_error<regex_constants::error_escape>();
4454             __hd = __traits_.value(*__first, 16);
4455             if (__hd == -1)
4456                 __throw_regex_error<regex_constants::error_escape>();
4457             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4458             // drop through
4459         case 'x':
4460             ++__first;
4461             if (__first == __last)
4462                 __throw_regex_error<regex_constants::error_escape>();
4463             __hd = __traits_.value(*__first, 16);
4464             if (__hd == -1)
4465                 __throw_regex_error<regex_constants::error_escape>();
4466             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4467             ++__first;
4468             if (__first == __last)
4469                 __throw_regex_error<regex_constants::error_escape>();
4470             __hd = __traits_.value(*__first, 16);
4471             if (__hd == -1)
4472                 __throw_regex_error<regex_constants::error_escape>();
4473             __sum = 16 * __sum + static_cast<unsigned>(__hd);
4474             if (__str)
4475                 *__str = _CharT(__sum);
4476             else
4477                 __push_char(_CharT(__sum));
4478             ++__first;
4479             break;
4480         case '0':
4481             if (__str)
4482                 *__str = _CharT(0);
4483             else
4484                 __push_char(_CharT(0));
4485             ++__first;
4486             break;
4487         default:
4488             if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum))
4489             {
4490                 if (__str)
4491                     *__str = *__first;
4492                 else
4493                     __push_char(*__first);
4494                 ++__first;
4495             }
4496             else
4497                 __throw_regex_error<regex_constants::error_escape>();
4498             break;
4499         }
4500     }
4501     return __first;
4502 }
4503
4504 template <class _CharT, class _Traits>
4505 template <class _ForwardIterator>
4506 _ForwardIterator
4507 basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first,
4508                                                         _ForwardIterator __last)
4509 {
4510     if (__first != __last)
4511     {
4512         switch (*__first)
4513         {
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         case '|':
4528             break;
4529         default:
4530             __push_char(*__first);
4531             ++__first;
4532             break;
4533         }
4534     }
4535     return __first;
4536 }
4537
4538 template <class _CharT, class _Traits>
4539 template <class _ForwardIterator>
4540 _ForwardIterator
4541 basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first,
4542                                            _ForwardIterator __last)
4543 {
4544     __owns_one_state<_CharT>* __sa = __end_;
4545     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4546     if (__t1 != __first)
4547         __parse_basic_reg_exp(__first, __t1);
4548     else
4549         __push_empty();
4550     __first = __t1;
4551     if (__first != __last)
4552         ++__first;
4553     while (__first != __last)
4554     {
4555         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4556         __owns_one_state<_CharT>* __sb = __end_;
4557         if (__t1 != __first)
4558             __parse_basic_reg_exp(__first, __t1);
4559         else
4560             __push_empty();
4561         __push_alternation(__sa, __sb);
4562         __first = __t1;
4563         if (__first != __last)
4564             ++__first;
4565     }
4566     return __first;
4567 }
4568
4569 template <class _CharT, class _Traits>
4570 template <class _ForwardIterator>
4571 _ForwardIterator
4572 basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first,
4573                                             _ForwardIterator __last)
4574 {
4575     __owns_one_state<_CharT>* __sa = __end_;
4576     _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4577     if (__t1 != __first)
4578         __parse_extended_reg_exp(__first, __t1);
4579     else
4580         __push_empty();
4581     __first = __t1;
4582     if (__first != __last)
4583         ++__first;
4584     while (__first != __last)
4585     {
4586         __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4587         __owns_one_state<_CharT>* __sb = __end_;
4588         if (__t1 != __first)
4589             __parse_extended_reg_exp(__first, __t1);
4590         else
4591             __push_empty();
4592         __push_alternation(__sa, __sb);
4593         __first = __t1;
4594         if (__first != __last)
4595             ++__first;
4596     }
4597     return __first;
4598 }
4599
4600 template <class _CharT, class _Traits>
4601 void
4602 basic_regex<_CharT, _Traits>::__push_loop(size_t __min, size_t __max,
4603         __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end,
4604         bool __greedy)
4605 {
4606     unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
4607     __end_->first() = nullptr;
4608     unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,
4609                 __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
4610                 __min, __max));
4611     __s->first() = nullptr;
4612     __e1.release();
4613     __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
4614     __end_ = __e2->second();
4615     __s->first() = __e2.release();
4616     ++__loop_count_;
4617 }
4618
4619 template <class _CharT, class _Traits>
4620 void
4621 basic_regex<_CharT, _Traits>::__push_char(value_type __c)
4622 {
4623     if (flags() & icase)
4624         __end_->first() = new __match_char_icase<_CharT, _Traits>
4625                                               (__traits_, __c, __end_->first());
4626     else if (flags() & collate)
4627         __end_->first() = new __match_char_collate<_CharT, _Traits>
4628                                               (__traits_, __c, __end_->first());
4629     else
4630         __end_->first() = new __match_char<_CharT>(__c, __end_->first());
4631     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4632 }
4633
4634 template <class _CharT, class _Traits>
4635 void
4636 basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
4637 {
4638     if (!(__flags_ & nosubs))
4639     {
4640         __end_->first() =
4641                 new __begin_marked_subexpression<_CharT>(++__marked_count_,
4642                                                          __end_->first());
4643         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4644     }
4645 }
4646
4647 template <class _CharT, class _Traits>
4648 void
4649 basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
4650 {
4651     if (!(__flags_ & nosubs))
4652     {
4653         __end_->first() =
4654                 new __end_marked_subexpression<_CharT>(__sub, __end_->first());
4655         __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4656     }
4657 }
4658
4659 template <class _CharT, class _Traits>
4660 void
4661 basic_regex<_CharT, _Traits>::__push_l_anchor()
4662 {
4663     __end_->first() = new __l_anchor<_CharT>(__end_->first());
4664     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4665 }
4666
4667 template <class _CharT, class _Traits>
4668 void
4669 basic_regex<_CharT, _Traits>::__push_r_anchor()
4670 {
4671     __end_->first() = new __r_anchor<_CharT>(__end_->first());
4672     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4673 }
4674
4675 template <class _CharT, class _Traits>
4676 void
4677 basic_regex<_CharT, _Traits>::__push_match_any()
4678 {
4679     __end_->first() = new __match_any<_CharT>(__end_->first());
4680     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4681 }
4682
4683 template <class _CharT, class _Traits>
4684 void
4685 basic_regex<_CharT, _Traits>::__push_match_any_but_newline()
4686 {
4687     __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
4688     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4689 }
4690
4691 template <class _CharT, class _Traits>
4692 void
4693 basic_regex<_CharT, _Traits>::__push_empty()
4694 {
4695     __end_->first() = new __empty_state<_CharT>(__end_->first());
4696     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4697 }
4698
4699 template <class _CharT, class _Traits>
4700 void
4701 basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert)
4702 {
4703     __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert,
4704                                                            __end_->first());
4705     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4706 }
4707
4708 template <class _CharT, class _Traits>
4709 void
4710 basic_regex<_CharT, _Traits>::__push_back_ref(int __i)
4711 {
4712     if (flags() & icase)
4713         __end_->first() = new __back_ref_icase<_CharT, _Traits>
4714                                               (__traits_, __i, __end_->first());
4715     else if (flags() & collate)
4716         __end_->first() = new __back_ref_collate<_CharT, _Traits>
4717                                               (__traits_, __i, __end_->first());
4718     else
4719         __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
4720     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4721 }
4722
4723 template <class _CharT, class _Traits>
4724 void
4725 basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa,
4726                                                  __owns_one_state<_CharT>* __ea)
4727 {
4728     __sa->first() = new __alternate<_CharT>(
4729                          static_cast<__owns_one_state<_CharT>*>(__sa->first()),
4730                          static_cast<__owns_one_state<_CharT>*>(__ea->first()));
4731     __ea->first() = nullptr;
4732     __ea->first() = new __empty_state<_CharT>(__end_->first());
4733     __end_->first() = nullptr;
4734     __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
4735     __end_ = static_cast<__owns_one_state<_CharT>*>(__ea->first());
4736 }
4737
4738 template <class _CharT, class _Traits>
4739 __bracket_expression<_CharT, _Traits>*
4740 basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate)
4741 {
4742     __bracket_expression<_CharT, _Traits>* __r =
4743         new __bracket_expression<_CharT, _Traits>(__traits_, __end_->first(),
4744                                                   __negate, __flags_ & icase,
4745                                                   __flags_ & collate);
4746     __end_->first() = __r;
4747     __end_ = __r;
4748     return __r;
4749 }
4750
4751 template <class _CharT, class _Traits>
4752 void
4753 basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp,
4754                                                bool __invert,
4755                                                unsigned __mexp)
4756 {
4757     __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
4758                                                            __end_->first(), __mexp);
4759     __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4760 }
4761
4762 typedef basic_regex<char>    regex;
4763 typedef basic_regex<wchar_t> wregex;
4764
4765 // sub_match
4766
4767 template <class _BidirectionalIterator>
4768 class _LIBCPP_TEMPLATE_VIS sub_match
4769     : public pair<_BidirectionalIterator, _BidirectionalIterator>
4770 {
4771 public:
4772     typedef _BidirectionalIterator                              iterator;
4773     typedef typename iterator_traits<iterator>::value_type      value_type;
4774     typedef typename iterator_traits<iterator>::difference_type difference_type;
4775     typedef basic_string<value_type>                            string_type;
4776
4777     bool matched;
4778
4779     _LIBCPP_INLINE_VISIBILITY
4780     _LIBCPP_CONSTEXPR sub_match() : matched() {}
4781
4782     _LIBCPP_INLINE_VISIBILITY
4783     difference_type length() const
4784         {return matched ? _VSTD::distance(this->first, this->second) : 0;}
4785     _LIBCPP_INLINE_VISIBILITY
4786     string_type str() const
4787         {return matched ? string_type(this->first, this->second) : string_type();}
4788     _LIBCPP_INLINE_VISIBILITY
4789     operator string_type() const
4790         {return str();}
4791
4792     _LIBCPP_INLINE_VISIBILITY
4793     int compare(const sub_match& __s) const
4794         {return str().compare(__s.str());}
4795     _LIBCPP_INLINE_VISIBILITY
4796     int compare(const string_type& __s) const
4797         {return str().compare(__s);}
4798     _LIBCPP_INLINE_VISIBILITY
4799     int compare(const value_type* __s) const
4800         {return str().compare(__s);}
4801 };
4802
4803 typedef sub_match<const char*>             csub_match;
4804 typedef sub_match<const wchar_t*>          wcsub_match;
4805 typedef sub_match<string::const_iterator>  ssub_match;
4806 typedef sub_match<wstring::const_iterator> wssub_match;
4807
4808 template <class _BiIter>
4809 inline _LIBCPP_INLINE_VISIBILITY
4810 bool
4811 operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4812 {
4813     return __x.compare(__y) == 0;
4814 }
4815
4816 template <class _BiIter>
4817 inline _LIBCPP_INLINE_VISIBILITY
4818 bool
4819 operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4820 {
4821     return !(__x == __y);
4822 }
4823
4824 template <class _BiIter>
4825 inline _LIBCPP_INLINE_VISIBILITY
4826 bool
4827 operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4828 {
4829     return __x.compare(__y) < 0;
4830 }
4831
4832 template <class _BiIter>
4833 inline _LIBCPP_INLINE_VISIBILITY
4834 bool
4835 operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4836 {
4837     return !(__y < __x);
4838 }
4839
4840 template <class _BiIter>
4841 inline _LIBCPP_INLINE_VISIBILITY
4842 bool
4843 operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4844 {
4845     return !(__x < __y);
4846 }
4847
4848 template <class _BiIter>
4849 inline _LIBCPP_INLINE_VISIBILITY
4850 bool
4851 operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4852 {
4853     return __y < __x;
4854 }
4855
4856 template <class _BiIter, class _ST, class _SA>
4857 inline _LIBCPP_INLINE_VISIBILITY
4858 bool
4859 operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4860            const sub_match<_BiIter>& __y)
4861 {
4862     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;
4863 }
4864
4865 template <class _BiIter, class _ST, class _SA>
4866 inline _LIBCPP_INLINE_VISIBILITY
4867 bool
4868 operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4869            const sub_match<_BiIter>& __y)
4870 {
4871     return !(__x == __y);
4872 }
4873
4874 template <class _BiIter, class _ST, class _SA>
4875 inline _LIBCPP_INLINE_VISIBILITY
4876 bool
4877 operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4878           const sub_match<_BiIter>& __y)
4879 {
4880     return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;
4881 }
4882
4883 template <class _BiIter, class _ST, class _SA>
4884 inline _LIBCPP_INLINE_VISIBILITY
4885 bool
4886 operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4887           const sub_match<_BiIter>& __y)
4888 {
4889     return __y < __x;
4890 }
4891
4892 template <class _BiIter, class _ST, class _SA>
4893 inline _LIBCPP_INLINE_VISIBILITY
4894 bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4895                 const sub_match<_BiIter>& __y)
4896 {
4897     return !(__x < __y);
4898 }
4899
4900 template <class _BiIter, class _ST, class _SA>
4901 inline _LIBCPP_INLINE_VISIBILITY
4902 bool
4903 operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4904            const sub_match<_BiIter>& __y)
4905 {
4906     return !(__y < __x);
4907 }
4908
4909 template <class _BiIter, class _ST, class _SA>
4910 inline _LIBCPP_INLINE_VISIBILITY
4911 bool
4912 operator==(const sub_match<_BiIter>& __x,
4913            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4914 {
4915     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;
4916 }
4917
4918 template <class _BiIter, class _ST, class _SA>
4919 inline _LIBCPP_INLINE_VISIBILITY
4920 bool
4921 operator!=(const sub_match<_BiIter>& __x,
4922            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4923 {
4924     return !(__x == __y);
4925 }
4926
4927 template <class _BiIter, class _ST, class _SA>
4928 inline _LIBCPP_INLINE_VISIBILITY
4929 bool
4930 operator<(const sub_match<_BiIter>& __x,
4931           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4932 {
4933     return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;
4934 }
4935
4936 template <class _BiIter, class _ST, class _SA>
4937 inline _LIBCPP_INLINE_VISIBILITY
4938 bool operator>(const sub_match<_BiIter>& __x,
4939                const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4940 {
4941     return __y < __x;
4942 }
4943
4944 template <class _BiIter, class _ST, class _SA>
4945 inline _LIBCPP_INLINE_VISIBILITY
4946 bool
4947 operator>=(const sub_match<_BiIter>& __x,
4948            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4949 {
4950     return !(__x < __y);
4951 }
4952
4953 template <class _BiIter, class _ST, class _SA>
4954 inline _LIBCPP_INLINE_VISIBILITY
4955 bool
4956 operator<=(const sub_match<_BiIter>& __x,
4957            const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4958 {
4959     return !(__y < __x);
4960 }
4961
4962 template <class _BiIter>
4963 inline _LIBCPP_INLINE_VISIBILITY
4964 bool
4965 operator==(typename iterator_traits<_BiIter>::value_type const* __x,
4966            const sub_match<_BiIter>& __y)
4967 {
4968     return __y.compare(__x) == 0;
4969 }
4970
4971 template <class _BiIter>
4972 inline _LIBCPP_INLINE_VISIBILITY
4973 bool
4974 operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
4975            const sub_match<_BiIter>& __y)
4976 {
4977     return !(__x == __y);
4978 }
4979
4980 template <class _BiIter>
4981 inline _LIBCPP_INLINE_VISIBILITY
4982 bool
4983 operator<(typename iterator_traits<_BiIter>::value_type const* __x,
4984           const sub_match<_BiIter>& __y)
4985 {
4986     return __y.compare(__x) > 0;
4987 }
4988
4989 template <class _BiIter>
4990 inline _LIBCPP_INLINE_VISIBILITY
4991 bool
4992 operator>(typename iterator_traits<_BiIter>::value_type const* __x,
4993           const sub_match<_BiIter>& __y)
4994 {
4995     return __y < __x;
4996 }
4997
4998 template <class _BiIter>
4999 inline _LIBCPP_INLINE_VISIBILITY
5000 bool
5001 operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
5002            const sub_match<_BiIter>& __y)
5003 {
5004     return !(__x < __y);
5005 }
5006
5007 template <class _BiIter>
5008 inline _LIBCPP_INLINE_VISIBILITY
5009 bool
5010 operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
5011            const sub_match<_BiIter>& __y)
5012 {
5013     return !(__y < __x);
5014 }
5015
5016 template <class _BiIter>
5017 inline _LIBCPP_INLINE_VISIBILITY
5018 bool
5019 operator==(const sub_match<_BiIter>& __x,
5020            typename iterator_traits<_BiIter>::value_type const* __y)
5021 {
5022     return __x.compare(__y) == 0;
5023 }
5024
5025 template <class _BiIter>
5026 inline _LIBCPP_INLINE_VISIBILITY
5027 bool
5028 operator!=(const sub_match<_BiIter>& __x,
5029            typename iterator_traits<_BiIter>::value_type const* __y)
5030 {
5031     return !(__x == __y);
5032 }
5033
5034 template <class _BiIter>
5035 inline _LIBCPP_INLINE_VISIBILITY
5036 bool
5037 operator<(const sub_match<_BiIter>& __x,
5038           typename iterator_traits<_BiIter>::value_type const* __y)
5039 {
5040     return __x.compare(__y) < 0;
5041 }
5042
5043 template <class _BiIter>
5044 inline _LIBCPP_INLINE_VISIBILITY
5045 bool
5046 operator>(const sub_match<_BiIter>& __x,
5047           typename iterator_traits<_BiIter>::value_type const* __y)
5048 {
5049     return __y < __x;
5050 }
5051
5052 template <class _BiIter>
5053 inline _LIBCPP_INLINE_VISIBILITY
5054 bool
5055 operator>=(const sub_match<_BiIter>& __x,
5056            typename iterator_traits<_BiIter>::value_type const* __y)
5057 {
5058     return !(__x < __y);
5059 }
5060
5061 template <class _BiIter>
5062 inline _LIBCPP_INLINE_VISIBILITY
5063 bool
5064 operator<=(const sub_match<_BiIter>& __x,
5065            typename iterator_traits<_BiIter>::value_type const* __y)
5066 {
5067     return !(__y < __x);
5068 }
5069
5070 template <class _BiIter>
5071 inline _LIBCPP_INLINE_VISIBILITY
5072 bool
5073 operator==(typename iterator_traits<_BiIter>::value_type const& __x,
5074            const sub_match<_BiIter>& __y)
5075 {
5076     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5077     return __y.compare(string_type(1, __x)) == 0;
5078 }
5079
5080 template <class _BiIter>
5081 inline _LIBCPP_INLINE_VISIBILITY
5082 bool
5083 operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
5084            const sub_match<_BiIter>& __y)
5085 {
5086     return !(__x == __y);
5087 }
5088
5089 template <class _BiIter>
5090 inline _LIBCPP_INLINE_VISIBILITY
5091 bool
5092 operator<(typename iterator_traits<_BiIter>::value_type const& __x,
5093           const sub_match<_BiIter>& __y)
5094 {
5095     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5096     return __y.compare(string_type(1, __x)) > 0;
5097 }
5098
5099 template <class _BiIter>
5100 inline _LIBCPP_INLINE_VISIBILITY
5101 bool
5102 operator>(typename iterator_traits<_BiIter>::value_type const& __x,
5103           const sub_match<_BiIter>& __y)
5104 {
5105     return __y < __x;
5106 }
5107
5108 template <class _BiIter>
5109 inline _LIBCPP_INLINE_VISIBILITY
5110 bool
5111 operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
5112            const sub_match<_BiIter>& __y)
5113 {
5114     return !(__x < __y);
5115 }
5116
5117 template <class _BiIter>
5118 inline _LIBCPP_INLINE_VISIBILITY
5119 bool
5120 operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
5121            const sub_match<_BiIter>& __y)
5122 {
5123     return !(__y < __x);
5124 }
5125
5126 template <class _BiIter>
5127 inline _LIBCPP_INLINE_VISIBILITY
5128 bool
5129 operator==(const sub_match<_BiIter>& __x,
5130            typename iterator_traits<_BiIter>::value_type const& __y)
5131 {
5132     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5133     return __x.compare(string_type(1, __y)) == 0;
5134 }
5135
5136 template <class _BiIter>
5137 inline _LIBCPP_INLINE_VISIBILITY
5138 bool
5139 operator!=(const sub_match<_BiIter>& __x,
5140            typename iterator_traits<_BiIter>::value_type const& __y)
5141 {
5142     return !(__x == __y);
5143 }
5144
5145 template <class _BiIter>
5146 inline _LIBCPP_INLINE_VISIBILITY
5147 bool
5148 operator<(const sub_match<_BiIter>& __x,
5149           typename iterator_traits<_BiIter>::value_type const& __y)
5150 {
5151     typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5152     return __x.compare(string_type(1, __y)) < 0;
5153 }
5154
5155 template <class _BiIter>
5156 inline _LIBCPP_INLINE_VISIBILITY
5157 bool
5158 operator>(const sub_match<_BiIter>& __x,
5159           typename iterator_traits<_BiIter>::value_type const& __y)
5160 {
5161     return __y < __x;
5162 }
5163
5164 template <class _BiIter>
5165 inline _LIBCPP_INLINE_VISIBILITY
5166 bool
5167 operator>=(const sub_match<_BiIter>& __x,
5168            typename iterator_traits<_BiIter>::value_type const& __y)
5169 {
5170     return !(__x < __y);
5171 }
5172
5173 template <class _BiIter>
5174 inline _LIBCPP_INLINE_VISIBILITY
5175 bool
5176 operator<=(const sub_match<_BiIter>& __x,
5177            typename iterator_traits<_BiIter>::value_type const& __y)
5178 {
5179     return !(__y < __x);
5180 }
5181
5182 template <class _CharT, class _ST, class _BiIter>
5183 inline _LIBCPP_INLINE_VISIBILITY
5184 basic_ostream<_CharT, _ST>&
5185 operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
5186 {
5187     return __os << __m.str();
5188 }
5189
5190 template <class _BidirectionalIterator, class _Allocator>
5191 class _LIBCPP_TEMPLATE_VIS match_results
5192 {
5193 public:
5194     typedef _Allocator                                        allocator_type;
5195     typedef sub_match<_BidirectionalIterator>                 value_type;
5196 private:
5197     typedef vector<value_type, allocator_type>                __container_type;
5198
5199     __container_type  __matches_;
5200     value_type __unmatched_;
5201     value_type __prefix_;
5202     value_type __suffix_;
5203     bool       __ready_;
5204 public:
5205     _BidirectionalIterator __position_start_;
5206     typedef const value_type&                                 const_reference;
5207     typedef value_type&                                       reference;
5208     typedef typename __container_type::const_iterator         const_iterator;
5209     typedef const_iterator                                    iterator;
5210     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
5211     typedef typename allocator_traits<allocator_type>::size_type size_type;
5212     typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
5213     typedef basic_string<char_type>                           string_type;
5214
5215     // construct/copy/destroy:
5216     explicit match_results(const allocator_type& __a = allocator_type());
5217 //    match_results(const match_results&) = default;
5218 //    match_results& operator=(const match_results&) = default;
5219 //    match_results(match_results&& __m) = default;
5220 //    match_results& operator=(match_results&& __m) = default;
5221 //    ~match_results() = default;
5222
5223     _LIBCPP_INLINE_VISIBILITY
5224     bool ready() const {return __ready_;}
5225
5226     // size:
5227     _LIBCPP_INLINE_VISIBILITY
5228     size_type size() const {return __matches_.size();}
5229     _LIBCPP_INLINE_VISIBILITY
5230     size_type max_size() const {return __matches_.max_size();}
5231     _LIBCPP_INLINE_VISIBILITY
5232     bool empty() const {return size() == 0;}
5233
5234     // element access:
5235     _LIBCPP_INLINE_VISIBILITY
5236     difference_type length(size_type __sub = 0) const
5237         {return (*this)[__sub].length();}
5238     _LIBCPP_INLINE_VISIBILITY
5239     difference_type position(size_type __sub = 0) const
5240         {return _VSTD::distance(__position_start_, (*this)[__sub].first);}
5241     _LIBCPP_INLINE_VISIBILITY
5242     string_type str(size_type __sub = 0) const
5243         {return (*this)[__sub].str();}
5244     _LIBCPP_INLINE_VISIBILITY
5245     const_reference operator[](size_type __n) const
5246         {return __n < __matches_.size() ? __matches_[__n] : __unmatched_;}
5247
5248     _LIBCPP_INLINE_VISIBILITY
5249     const_reference prefix() const {return __prefix_;}
5250     _LIBCPP_INLINE_VISIBILITY
5251     const_reference suffix() const {return __suffix_;}
5252
5253     _LIBCPP_INLINE_VISIBILITY
5254     const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin();}
5255     _LIBCPP_INLINE_VISIBILITY
5256     const_iterator end() const {return __matches_.end();}
5257     _LIBCPP_INLINE_VISIBILITY
5258     const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin();}
5259     _LIBCPP_INLINE_VISIBILITY
5260     const_iterator cend() const {return __matches_.end();}
5261
5262     // format:
5263     template <class _OutputIter>
5264         _OutputIter
5265         format(_OutputIter __output, const char_type* __fmt_first,
5266                const char_type* __fmt_last,
5267                regex_constants::match_flag_type __flags = regex_constants::format_default) const;
5268     template <class _OutputIter, class _ST, class _SA>
5269         _LIBCPP_INLINE_VISIBILITY
5270         _OutputIter
5271         format(_OutputIter __output, const basic_string<char_type, _ST, _SA>& __fmt,
5272                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5273             {return format(__output, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
5274     template <class _ST, class _SA>
5275         _LIBCPP_INLINE_VISIBILITY
5276         basic_string<char_type, _ST, _SA>
5277         format(const basic_string<char_type, _ST, _SA>& __fmt,
5278                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5279         {
5280             basic_string<char_type, _ST, _SA> __r;
5281             format(back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
5282                    __flags);
5283             return __r;
5284         }
5285     _LIBCPP_INLINE_VISIBILITY
5286     string_type
5287         format(const char_type* __fmt,
5288                regex_constants::match_flag_type __flags = regex_constants::format_default) const
5289         {
5290             string_type __r;
5291             format(back_inserter(__r), __fmt,
5292                    __fmt + char_traits<char_type>::length(__fmt), __flags);
5293             return __r;
5294         }
5295
5296     // allocator:
5297     _LIBCPP_INLINE_VISIBILITY
5298     allocator_type get_allocator() const {return __matches_.get_allocator();}
5299
5300     // swap:
5301     void swap(match_results& __m);
5302
5303     template <class _Bp, class _Ap>
5304         _LIBCPP_INLINE_VISIBILITY
5305         void __assign(_BidirectionalIterator __f, _BidirectionalIterator __l,
5306                       const match_results<_Bp, _Ap>& __m, bool __no_update_pos)
5307     {
5308         _Bp __mf = __m.prefix().first;
5309         __matches_.resize(__m.size());
5310         for (size_type __i = 0; __i < __matches_.size(); ++__i)
5311         {
5312             __matches_[__i].first = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].first));
5313             __matches_[__i].second = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].second));
5314             __matches_[__i].matched = __m[__i].matched;
5315         }
5316         __unmatched_.first   = __l;
5317         __unmatched_.second  = __l;
5318         __unmatched_.matched = false;
5319         __prefix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().first));
5320         __prefix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().second));
5321         __prefix_.matched = __m.prefix().matched;
5322         __suffix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().first));
5323         __suffix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().second));
5324         __suffix_.matched = __m.suffix().matched;
5325         if (!__no_update_pos)
5326             __position_start_ = __prefix_.first;
5327         __ready_ = __m.ready();
5328     }
5329
5330 private:
5331     void __init(unsigned __s,
5332                 _BidirectionalIterator __f, _BidirectionalIterator __l,
5333                 bool __no_update_pos = false);
5334
5335     template <class, class> friend class basic_regex;
5336
5337     template <class _Bp, class _Ap, class _Cp, class _Tp>
5338     friend
5339     bool
5340     regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
5341                 regex_constants::match_flag_type);
5342
5343     template <class _Bp, class _Ap>
5344     friend
5345     bool
5346     operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
5347
5348     template <class, class> friend class __lookahead;
5349 };
5350
5351 template <class _BidirectionalIterator, class _Allocator>
5352 match_results<_BidirectionalIterator, _Allocator>::match_results(
5353         const allocator_type& __a)
5354     : __matches_(__a),
5355       __unmatched_(),
5356       __prefix_(),
5357       __suffix_(),
5358       __ready_(false),
5359       __position_start_()
5360 {
5361 }
5362
5363 template <class _BidirectionalIterator, class _Allocator>
5364 void
5365 match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
5366                          _BidirectionalIterator __f, _BidirectionalIterator __l,
5367                          bool __no_update_pos)
5368 {
5369     __unmatched_.first   = __l;
5370     __unmatched_.second  = __l;
5371     __unmatched_.matched = false;
5372     __matches_.assign(__s, __unmatched_);
5373     __prefix_.first      = __f;
5374     __prefix_.second     = __f;
5375     __prefix_.matched    = false;
5376     __suffix_ = __unmatched_;
5377     if (!__no_update_pos)
5378         __position_start_ = __prefix_.first;
5379     __ready_ = true;
5380 }
5381
5382 template <class _BidirectionalIterator, class _Allocator>
5383 template <class _OutputIter>
5384 _OutputIter
5385 match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __output,
5386         const char_type* __fmt_first, const char_type* __fmt_last,
5387         regex_constants::match_flag_type __flags) const
5388 {
5389     if (__flags & regex_constants::format_sed)
5390     {
5391         for (; __fmt_first != __fmt_last; ++__fmt_first)
5392         {
5393             if (*__fmt_first == '&')
5394                 __output = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5395                                    __output);
5396             else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
5397             {
5398                 ++__fmt_first;
5399                 if ('0' <= *__fmt_first && *__fmt_first <= '9')
5400                 {
5401                     size_t __i = *__fmt_first - '0';
5402                     __output = _VSTD::copy((*this)[__i].first,
5403                                         (*this)[__i].second, __output);
5404                 }
5405                 else
5406                 {
5407                     *__output = *__fmt_first;
5408                     ++__output;
5409                 }
5410             }
5411             else
5412             {
5413                 *__output = *__fmt_first;
5414                 ++__output;
5415             }
5416         }
5417     }
5418     else
5419     {
5420         for (; __fmt_first != __fmt_last; ++__fmt_first)
5421         {
5422             if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
5423             {
5424                 switch (__fmt_first[1])
5425                 {
5426                 case '$':
5427                     *__output = *++__fmt_first;
5428                     ++__output;
5429                     break;
5430                 case '&':
5431                     ++__fmt_first;
5432                     __output = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5433                                        __output);
5434                     break;
5435                 case '`':
5436                     ++__fmt_first;
5437                     __output = _VSTD::copy(__prefix_.first, __prefix_.second, __output);
5438                     break;
5439                 case '\'':
5440                     ++__fmt_first;
5441                     __output = _VSTD::copy(__suffix_.first, __suffix_.second, __output);
5442                     break;
5443                 default:
5444                     if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5445                     {
5446                         ++__fmt_first;
5447                         size_t __i = *__fmt_first - '0';
5448                         if (__fmt_first + 1 != __fmt_last &&
5449                             '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5450                         {
5451                             ++__fmt_first;
5452                             __i = 10 * __i + *__fmt_first - '0';
5453                         }
5454                         __output = _VSTD::copy((*this)[__i].first,
5455                                             (*this)[__i].second, __output);
5456                     }
5457                     else
5458                     {
5459                         *__output = *__fmt_first;
5460                         ++__output;
5461                     }
5462                     break;
5463                 }
5464             }
5465             else
5466             {
5467                 *__output = *__fmt_first;
5468                 ++__output;
5469             }
5470         }
5471     }
5472     return __output;
5473 }
5474
5475 template <class _BidirectionalIterator, class _Allocator>
5476 void
5477 match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
5478 {
5479     using _VSTD::swap;
5480     swap(__matches_, __m.__matches_);
5481     swap(__unmatched_, __m.__unmatched_);
5482     swap(__prefix_, __m.__prefix_);
5483     swap(__suffix_, __m.__suffix_);
5484     swap(__position_start_, __m.__position_start_);
5485     swap(__ready_, __m.__ready_);
5486 }
5487
5488 typedef match_results<const char*>             cmatch;
5489 typedef match_results<const wchar_t*>          wcmatch;
5490 typedef match_results<string::const_iterator>  smatch;
5491 typedef match_results<wstring::const_iterator> wsmatch;
5492
5493 template <class _BidirectionalIterator, class _Allocator>
5494 bool
5495 operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
5496            const match_results<_BidirectionalIterator, _Allocator>& __y)
5497 {
5498     if (__x.__ready_ != __y.__ready_)
5499         return false;
5500     if (!__x.__ready_)
5501         return true;
5502     return __x.__matches_ == __y.__matches_ &&
5503            __x.__prefix_ == __y.__prefix_ &&
5504            __x.__suffix_ == __y.__suffix_;
5505 }
5506
5507 template <class _BidirectionalIterator, class _Allocator>
5508 inline _LIBCPP_INLINE_VISIBILITY
5509 bool
5510 operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
5511            const match_results<_BidirectionalIterator, _Allocator>& __y)
5512 {
5513     return !(__x == __y);
5514 }
5515
5516 template <class _BidirectionalIterator, class _Allocator>
5517 inline _LIBCPP_INLINE_VISIBILITY
5518 void
5519 swap(match_results<_BidirectionalIterator, _Allocator>& __x,
5520      match_results<_BidirectionalIterator, _Allocator>& __y)
5521 {
5522     __x.swap(__y);
5523 }
5524
5525 // regex_search
5526
5527 template <class _CharT, class _Traits>
5528 template <class _Allocator>
5529 bool
5530 basic_regex<_CharT, _Traits>::__match_at_start_ecma(
5531         const _CharT* __first, const _CharT* __last,
5532         match_results<const _CharT*, _Allocator>& __m,
5533         regex_constants::match_flag_type __flags, bool __at_first) const
5534 {
5535     vector<__state> __states;
5536     __node* __st = __start_.get();
5537     if (__st)
5538     {
5539         sub_match<const _CharT*> __unmatched;
5540         __unmatched.first   = __last;
5541         __unmatched.second  = __last;
5542         __unmatched.matched = false;
5543
5544         __states.push_back(__state());
5545         __states.back().__do_ = 0;
5546         __states.back().__first_ = __first;
5547         __states.back().__current_ = __first;
5548         __states.back().__last_ = __last;
5549         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5550         __states.back().__loop_data_.resize(__loop_count());
5551         __states.back().__node_ = __st;
5552         __states.back().__flags_ = __flags;
5553         __states.back().__at_first_ = __at_first;
5554         do
5555         {
5556             __state& __s = __states.back();
5557             if (__s.__node_)
5558                 __s.__node_->__exec(__s);
5559             switch (__s.__do_)
5560             {
5561             case __state::__end_state:
5562                 if ((__flags & regex_constants::match_not_null) &&
5563                     __s.__current_ == __first)
5564                 {
5565                   __states.pop_back();
5566                   break;
5567                 }
5568                 if ((__flags & regex_constants::__full_match) &&
5569                     __s.__current_ != __last)
5570                 {
5571                   __states.pop_back();
5572                   break;
5573                 }
5574                 __m.__matches_[0].first = __first;
5575                 __m.__matches_[0].second = _VSTD::next(__first, __s.__current_ - __first);
5576                 __m.__matches_[0].matched = true;
5577                 for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
5578                     __m.__matches_[__i+1] = __s.__sub_matches_[__i];
5579                 return true;
5580             case __state::__accept_and_consume:
5581             case __state::__repeat:
5582             case __state::__accept_but_not_consume:
5583                 break;
5584             case __state::__split:
5585                 {
5586                 __state __snext = __s;
5587                 __s.__node_->__exec_split(true, __s);
5588                 __snext.__node_->__exec_split(false, __snext);
5589                 __states.push_back(_VSTD::move(__snext));
5590                 }
5591                 break;
5592             case __state::__reject:
5593                 __states.pop_back();
5594                 break;
5595             default:
5596                 __throw_regex_error<regex_constants::__re_err_unknown>();
5597                 break;
5598
5599             }
5600         } while (!__states.empty());
5601     }
5602     return false;
5603 }
5604
5605 template <class _CharT, class _Traits>
5606 template <class _Allocator>
5607 bool
5608 basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
5609         const _CharT* __first, const _CharT* __last,
5610         match_results<const _CharT*, _Allocator>& __m,
5611         regex_constants::match_flag_type __flags, bool __at_first) const
5612 {
5613     deque<__state> __states;
5614     ptrdiff_t __highest_j = 0;
5615     ptrdiff_t _Np = _VSTD::distance(__first, __last);
5616     __node* __st = __start_.get();
5617     if (__st)
5618     {
5619         __states.push_back(__state());
5620         __states.back().__do_ = 0;
5621         __states.back().__first_ = __first;
5622         __states.back().__current_ = __first;
5623         __states.back().__last_ = __last;
5624         __states.back().__loop_data_.resize(__loop_count());
5625         __states.back().__node_ = __st;
5626         __states.back().__flags_ = __flags;
5627         __states.back().__at_first_ = __at_first;
5628         bool __matched = false;
5629         do
5630         {
5631             __state& __s = __states.back();
5632             if (__s.__node_)
5633                 __s.__node_->__exec(__s);
5634             switch (__s.__do_)
5635             {
5636             case __state::__end_state:
5637                 if ((__flags & regex_constants::match_not_null) &&
5638                     __s.__current_ == __first)
5639                 {
5640                   __states.pop_back();
5641                   break;
5642                 }
5643                 if ((__flags & regex_constants::__full_match) &&
5644                     __s.__current_ != __last)
5645                 {
5646                   __states.pop_back();
5647                   break;
5648                 }
5649                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5650                     __highest_j = __s.__current_ - __s.__first_;
5651                 __matched = true;
5652                 if (__highest_j == _Np)
5653                     __states.clear();
5654                 else
5655                     __states.pop_back();
5656                 break;
5657             case __state::__consume_input:
5658                 break;
5659             case __state::__accept_and_consume:
5660                 __states.push_front(_VSTD::move(__s));
5661                 __states.pop_back();
5662                 break;
5663             case __state::__repeat:
5664             case __state::__accept_but_not_consume:
5665                 break;
5666             case __state::__split:
5667                 {
5668                 __state __snext = __s;
5669                 __s.__node_->__exec_split(true, __s);
5670                 __snext.__node_->__exec_split(false, __snext);
5671                 __states.push_back(_VSTD::move(__snext));
5672                 }
5673                 break;
5674             case __state::__reject:
5675                 __states.pop_back();
5676                 break;
5677             default:
5678                 __throw_regex_error<regex_constants::__re_err_unknown>();
5679                 break;
5680             }
5681         } while (!__states.empty());
5682         if (__matched)
5683         {
5684             __m.__matches_[0].first = __first;
5685             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5686             __m.__matches_[0].matched = true;
5687             return true;
5688         }
5689     }
5690     return false;
5691 }
5692
5693 template <class _CharT, class _Traits>
5694 template <class _Allocator>
5695 bool
5696 basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
5697         const _CharT* __first, const _CharT* __last,
5698         match_results<const _CharT*, _Allocator>& __m,
5699         regex_constants::match_flag_type __flags, bool __at_first) const
5700 {
5701     vector<__state> __states;
5702     __state __best_state;
5703     ptrdiff_t __j = 0;
5704     ptrdiff_t __highest_j = 0;
5705     ptrdiff_t _Np = _VSTD::distance(__first, __last);
5706     __node* __st = __start_.get();
5707     if (__st)
5708     {
5709         sub_match<const _CharT*> __unmatched;
5710         __unmatched.first   = __last;
5711         __unmatched.second  = __last;
5712         __unmatched.matched = false;
5713
5714         __states.push_back(__state());
5715         __states.back().__do_ = 0;
5716         __states.back().__first_ = __first;
5717         __states.back().__current_ = __first;
5718         __states.back().__last_ = __last;
5719         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5720         __states.back().__loop_data_.resize(__loop_count());
5721         __states.back().__node_ = __st;
5722         __states.back().__flags_ = __flags;
5723         __states.back().__at_first_ = __at_first;
5724         const _CharT* __current = __first;
5725         bool __matched = false;
5726         do
5727         {
5728             __state& __s = __states.back();
5729             if (__s.__node_)
5730                 __s.__node_->__exec(__s);
5731             switch (__s.__do_)
5732             {
5733             case __state::__end_state:
5734                 if ((__flags & regex_constants::match_not_null) &&
5735                     __s.__current_ == __first)
5736                 {
5737                   __states.pop_back();
5738                   break;
5739                 }
5740                 if ((__flags & regex_constants::__full_match) &&
5741                     __s.__current_ != __last)
5742                 {
5743                   __states.pop_back();
5744                   break;
5745                 }
5746                 if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5747                 {
5748                     __highest_j = __s.__current_ - __s.__first_;
5749                     __best_state = __s;
5750                 }
5751                 __matched = true;
5752                 if (__highest_j == _Np)
5753                     __states.clear();
5754                 else
5755                     __states.pop_back();
5756                 break;
5757             case __state::__accept_and_consume:
5758                 __j += __s.__current_ - __current;
5759                 __current = __s.__current_;
5760                 break;
5761             case __state::__repeat:
5762             case __state::__accept_but_not_consume:
5763                 break;
5764             case __state::__split:
5765                 {
5766                 __state __snext = __s;
5767                 __s.__node_->__exec_split(true, __s);
5768                 __snext.__node_->__exec_split(false, __snext);
5769                 __states.push_back(_VSTD::move(__snext));
5770                 }
5771                 break;
5772             case __state::__reject:
5773                 __states.pop_back();
5774                 break;
5775             default:
5776                 __throw_regex_error<regex_constants::__re_err_unknown>();
5777                 break;
5778             }
5779         } while (!__states.empty());
5780         if (__matched)
5781         {
5782             __m.__matches_[0].first = __first;
5783             __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5784             __m.__matches_[0].matched = true;
5785             for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
5786                 __m.__matches_[__i+1] = __best_state.__sub_matches_[__i];
5787             return true;
5788         }
5789     }
5790     return false;
5791 }
5792
5793 template <class _CharT, class _Traits>
5794 template <class _Allocator>
5795 bool
5796 basic_regex<_CharT, _Traits>::__match_at_start(
5797         const _CharT* __first, const _CharT* __last,
5798         match_results<const _CharT*, _Allocator>& __m,
5799         regex_constants::match_flag_type __flags, bool __at_first) const
5800 {
5801     if ((__flags_ & 0x1F0) == ECMAScript)
5802         return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
5803     if (mark_count() == 0)
5804         return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
5805     return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
5806 }
5807
5808 template <class _CharT, class _Traits>
5809 template <class _Allocator>
5810 bool
5811 basic_regex<_CharT, _Traits>::__search(
5812         const _CharT* __first, const _CharT* __last,
5813         match_results<const _CharT*, _Allocator>& __m,
5814         regex_constants::match_flag_type __flags) const
5815 {
5816     __m.__init(1 + mark_count(), __first, __last,
5817                                     __flags & regex_constants::__no_update_pos);
5818     if (__match_at_start(__first, __last, __m, __flags,
5819                                     !(__flags & regex_constants::__no_update_pos)))
5820     {
5821         __m.__prefix_.second = __m[0].first;
5822         __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5823         __m.__suffix_.first = __m[0].second;
5824         __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5825         return true;
5826     }
5827     if (__first != __last && !(__flags & regex_constants::match_continuous))
5828     {
5829         __flags |= regex_constants::match_prev_avail;
5830         for (++__first; __first != __last; ++__first)
5831         {
5832             __m.__matches_.assign(__m.size(), __m.__unmatched_);
5833             if (__match_at_start(__first, __last, __m, __flags, false))
5834             {
5835                 __m.__prefix_.second = __m[0].first;
5836                 __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5837                 __m.__suffix_.first = __m[0].second;
5838                 __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5839                 return true;
5840             }
5841             __m.__matches_.assign(__m.size(), __m.__unmatched_);
5842         }
5843     }
5844     __m.__matches_.clear();
5845     return false;
5846 }
5847
5848 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5849 inline _LIBCPP_INLINE_VISIBILITY
5850 bool
5851 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5852              match_results<_BidirectionalIterator, _Allocator>& __m,
5853              const basic_regex<_CharT, _Traits>& __e,
5854              regex_constants::match_flag_type __flags = regex_constants::match_default)
5855 {
5856     int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
5857     basic_string<_CharT> __s(_VSTD::prev(__first, __offset), __last);
5858     match_results<const _CharT*> __mc;
5859     bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
5860     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5861     return __r;
5862 }
5863
5864 template <class _Iter, class _Allocator, class _CharT, class _Traits>
5865 inline _LIBCPP_INLINE_VISIBILITY
5866 bool
5867 regex_search(__wrap_iter<_Iter> __first,
5868              __wrap_iter<_Iter> __last,
5869              match_results<__wrap_iter<_Iter>, _Allocator>& __m,
5870              const basic_regex<_CharT, _Traits>& __e,
5871              regex_constants::match_flag_type __flags = regex_constants::match_default)
5872 {
5873     match_results<const _CharT*> __mc;
5874     bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
5875     __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5876     return __r;
5877 }
5878
5879 template <class _Allocator, class _CharT, class _Traits>
5880 inline _LIBCPP_INLINE_VISIBILITY
5881 bool
5882 regex_search(const _CharT* __first, const _CharT* __last,
5883              match_results<const _CharT*, _Allocator>& __m,
5884              const basic_regex<_CharT, _Traits>& __e,
5885              regex_constants::match_flag_type __flags = regex_constants::match_default)
5886 {
5887     return __e.__search(__first, __last, __m, __flags);
5888 }
5889
5890 template <class _BidirectionalIterator, class _CharT, class _Traits>
5891 inline _LIBCPP_INLINE_VISIBILITY
5892 bool
5893 regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5894              const basic_regex<_CharT, _Traits>& __e,
5895              regex_constants::match_flag_type __flags = regex_constants::match_default)
5896 {
5897     basic_string<_CharT> __s(__first, __last);
5898     match_results<const _CharT*> __mc;
5899     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5900 }
5901
5902 template <class _CharT, class _Traits>
5903 inline _LIBCPP_INLINE_VISIBILITY
5904 bool
5905 regex_search(const _CharT* __first, const _CharT* __last,
5906              const basic_regex<_CharT, _Traits>& __e,
5907              regex_constants::match_flag_type __flags = regex_constants::match_default)
5908 {
5909     match_results<const _CharT*> __mc;
5910     return __e.__search(__first, __last, __mc, __flags);
5911 }
5912
5913 template <class _CharT, class _Allocator, class _Traits>
5914 inline _LIBCPP_INLINE_VISIBILITY
5915 bool
5916 regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
5917              const basic_regex<_CharT, _Traits>& __e,
5918              regex_constants::match_flag_type __flags = regex_constants::match_default)
5919 {
5920     return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
5921 }
5922
5923 template <class _CharT, class _Traits>
5924 inline _LIBCPP_INLINE_VISIBILITY
5925 bool
5926 regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
5927              regex_constants::match_flag_type __flags = regex_constants::match_default)
5928 {
5929     match_results<const _CharT*> __m;
5930     return _VSTD::regex_search(__str, __m, __e, __flags);
5931 }
5932
5933 template <class _ST, class _SA, class _CharT, class _Traits>
5934 inline _LIBCPP_INLINE_VISIBILITY
5935 bool
5936 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5937              const basic_regex<_CharT, _Traits>& __e,
5938              regex_constants::match_flag_type __flags = regex_constants::match_default)
5939 {
5940     match_results<const _CharT*> __mc;
5941     return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5942 }
5943
5944 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5945 inline _LIBCPP_INLINE_VISIBILITY
5946 bool
5947 regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5948              match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5949              const basic_regex<_CharT, _Traits>& __e,
5950              regex_constants::match_flag_type __flags = regex_constants::match_default)
5951 {
5952     match_results<const _CharT*> __mc;
5953     bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5954     __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
5955     return __r;
5956 }
5957
5958 #if _LIBCPP_STD_VER > 11
5959 template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
5960 bool
5961 regex_search(const basic_string<_Cp, _ST, _SA>&& __s,
5962              match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
5963              const basic_regex<_Cp, _Tp>& __e,
5964              regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
5965 #endif
5966
5967 // regex_match
5968
5969 template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5970 bool
5971 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
5972             match_results<_BidirectionalIterator, _Allocator>& __m,
5973             const basic_regex<_CharT, _Traits>& __e,
5974             regex_constants::match_flag_type __flags = regex_constants::match_default)
5975 {
5976     bool __r = _VSTD::regex_search(
5977         __first, __last, __m, __e,
5978         __flags | regex_constants::match_continuous |
5979         regex_constants::__full_match);
5980     if (__r)
5981     {
5982         __r = !__m.suffix().matched;
5983         if (!__r)
5984             __m.__matches_.clear();
5985     }
5986     return __r;
5987 }
5988
5989 template <class _BidirectionalIterator, class _CharT, class _Traits>
5990 inline _LIBCPP_INLINE_VISIBILITY
5991 bool
5992 regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
5993             const basic_regex<_CharT, _Traits>& __e,
5994             regex_constants::match_flag_type __flags = regex_constants::match_default)
5995 {
5996     match_results<_BidirectionalIterator> __m;
5997     return _VSTD::regex_match(__first, __last, __m, __e, __flags);
5998 }
5999
6000 template <class _CharT, class _Allocator, class _Traits>
6001 inline _LIBCPP_INLINE_VISIBILITY
6002 bool
6003 regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
6004             const basic_regex<_CharT, _Traits>& __e,
6005             regex_constants::match_flag_type __flags = regex_constants::match_default)
6006 {
6007     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
6008 }
6009
6010 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6011 inline _LIBCPP_INLINE_VISIBILITY
6012 bool
6013 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6014             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6015             const basic_regex<_CharT, _Traits>& __e,
6016             regex_constants::match_flag_type __flags = regex_constants::match_default)
6017 {
6018     return _VSTD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
6019 }
6020
6021 #if _LIBCPP_STD_VER > 11
6022 template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
6023 inline _LIBCPP_INLINE_VISIBILITY
6024 bool
6025 regex_match(const basic_string<_CharT, _ST, _SA>&& __s,
6026             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
6027             const basic_regex<_CharT, _Traits>& __e,
6028             regex_constants::match_flag_type __flags = regex_constants::match_default) = delete;
6029 #endif
6030
6031 template <class _CharT, class _Traits>
6032 inline _LIBCPP_INLINE_VISIBILITY
6033 bool
6034 regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
6035             regex_constants::match_flag_type __flags = regex_constants::match_default)
6036 {
6037     return _VSTD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
6038 }
6039
6040 template <class _ST, class _SA, class _CharT, class _Traits>
6041 inline _LIBCPP_INLINE_VISIBILITY
6042 bool
6043 regex_match(const basic_string<_CharT, _ST, _SA>& __s,
6044             const basic_regex<_CharT, _Traits>& __e,
6045             regex_constants::match_flag_type __flags = regex_constants::match_default)
6046 {
6047     return _VSTD::regex_match(__s.begin(), __s.end(), __e, __flags);
6048 }
6049
6050 // regex_iterator
6051
6052 template <class _BidirectionalIterator,
6053           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6054           class _Traits = regex_traits<_CharT> >
6055 class _LIBCPP_TEMPLATE_VIS regex_iterator
6056 {
6057 public:
6058     typedef basic_regex<_CharT, _Traits>          regex_type;
6059     typedef match_results<_BidirectionalIterator> value_type;
6060     typedef ptrdiff_t                             difference_type;
6061     typedef const value_type*                     pointer;
6062     typedef const value_type&                     reference;
6063     typedef forward_iterator_tag                  iterator_category;
6064
6065 private:
6066     _BidirectionalIterator           __begin_;
6067     _BidirectionalIterator           __end_;
6068     const regex_type*                __pregex_;
6069     regex_constants::match_flag_type __flags_;
6070     value_type                       __match_;
6071
6072 public:
6073     regex_iterator();
6074     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6075                    const regex_type& __re,
6076                    regex_constants::match_flag_type __m
6077                                               = regex_constants::match_default);
6078 #if _LIBCPP_STD_VER > 11
6079     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6080                    const regex_type&& __re,
6081                    regex_constants::match_flag_type __m
6082                                      = regex_constants::match_default) = delete;
6083 #endif
6084
6085     bool operator==(const regex_iterator& __x) const;
6086     _LIBCPP_INLINE_VISIBILITY
6087     bool operator!=(const regex_iterator& __x) const {return !(*this == __x);}
6088
6089     _LIBCPP_INLINE_VISIBILITY
6090     reference operator*() const {return  __match_;}
6091     _LIBCPP_INLINE_VISIBILITY
6092     pointer operator->() const  {return &__match_;}
6093
6094     regex_iterator& operator++();
6095     _LIBCPP_INLINE_VISIBILITY
6096     regex_iterator operator++(int)
6097     {
6098         regex_iterator __t(*this);
6099         ++(*this);
6100         return __t;
6101     }
6102 };
6103
6104 template <class _BidirectionalIterator, class _CharT, class _Traits>
6105 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
6106     : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_()
6107 {
6108 }
6109
6110 template <class _BidirectionalIterator, class _CharT, class _Traits>
6111 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6112     regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6113                    const regex_type& __re, regex_constants::match_flag_type __m)
6114     : __begin_(__a),
6115       __end_(__b),
6116       __pregex_(&__re),
6117       __flags_(__m)
6118 {
6119     _VSTD::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
6120 }
6121
6122 template <class _BidirectionalIterator, class _CharT, class _Traits>
6123 bool
6124 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6125     operator==(const regex_iterator& __x) const
6126 {
6127     if (__match_.empty() && __x.__match_.empty())
6128         return true;
6129     if (__match_.empty() || __x.__match_.empty())
6130         return false;
6131     return __begin_ == __x.__begin_       &&
6132            __end_ == __x.__end_           &&
6133            __pregex_ == __x.__pregex_     &&
6134            __flags_ == __x.__flags_       &&
6135            __match_[0] == __x.__match_[0];
6136 }
6137
6138 template <class _BidirectionalIterator, class _CharT, class _Traits>
6139 regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
6140 regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6141 {
6142     __flags_ |= regex_constants::__no_update_pos;
6143     _BidirectionalIterator __start = __match_[0].second;
6144     if (__match_.empty())
6145     {
6146         if (__start == __end_)
6147         {
6148             __match_ = value_type();
6149             return *this;
6150         }
6151         else if (_VSTD::regex_search(__start, __end_, __match_, *__pregex_,
6152                                     __flags_ | regex_constants::match_not_null |
6153                                     regex_constants::match_continuous))
6154             return *this;
6155         else
6156             ++__start;
6157     }
6158     __flags_ |= regex_constants::match_prev_avail;
6159     if (!_VSTD::regex_search(__start, __end_, __match_, *__pregex_, __flags_))
6160         __match_ = value_type();
6161     return *this;
6162 }
6163
6164 typedef regex_iterator<const char*>             cregex_iterator;
6165 typedef regex_iterator<const wchar_t*>          wcregex_iterator;
6166 typedef regex_iterator<string::const_iterator>  sregex_iterator;
6167 typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
6168
6169 // regex_token_iterator
6170
6171 template <class _BidirectionalIterator,
6172           class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6173           class _Traits = regex_traits<_CharT> >
6174 class _LIBCPP_TEMPLATE_VIS regex_token_iterator
6175 {
6176 public:
6177     typedef basic_regex<_CharT, _Traits>      regex_type;
6178     typedef sub_match<_BidirectionalIterator> value_type;
6179     typedef ptrdiff_t                         difference_type;
6180     typedef const value_type*                 pointer;
6181     typedef const value_type&                 reference;
6182     typedef forward_iterator_tag              iterator_category;
6183
6184 private:
6185     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
6186
6187     _Position         __position_;
6188     const value_type* __result_;
6189     value_type        __suffix_;
6190     ptrdiff_t         __n_;
6191     vector<int>       __subs_;
6192
6193 public:
6194     regex_token_iterator();
6195     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6196                          const regex_type& __re, int __submatch = 0,
6197                          regex_constants::match_flag_type __m =
6198                                                 regex_constants::match_default);
6199 #if _LIBCPP_STD_VER > 11
6200     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6201                          const regex_type&& __re, int __submatch = 0,
6202                          regex_constants::match_flag_type __m =
6203                                        regex_constants::match_default) = delete;
6204 #endif
6205
6206     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6207                          const regex_type& __re, const vector<int>& __submatches,
6208                          regex_constants::match_flag_type __m =
6209                                                 regex_constants::match_default);
6210 #if _LIBCPP_STD_VER > 11
6211     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6212                          const regex_type&& __re, const vector<int>& __submatches,
6213                          regex_constants::match_flag_type __m =
6214                                      regex_constants::match_default) = delete;
6215 #endif
6216
6217 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6218     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6219                          const regex_type& __re,
6220                          initializer_list<int> __submatches,
6221                          regex_constants::match_flag_type __m =
6222                                                 regex_constants::match_default);
6223
6224 #if _LIBCPP_STD_VER > 11
6225     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6226                          const regex_type&& __re,
6227                          initializer_list<int> __submatches,
6228                          regex_constants::match_flag_type __m =
6229                                        regex_constants::match_default) = delete;
6230 #endif
6231 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6232     template <size_t _Np>
6233         regex_token_iterator(_BidirectionalIterator __a,
6234                              _BidirectionalIterator __b,
6235                              const regex_type& __re,
6236                              const int (&__submatches)[_Np],
6237                              regex_constants::match_flag_type __m =
6238                                                 regex_constants::match_default);
6239 #if _LIBCPP_STD_VER > 11
6240     template <std::size_t _Np>
6241         regex_token_iterator(_BidirectionalIterator __a,
6242                              _BidirectionalIterator __b,
6243                              const regex_type&& __re,
6244                              const int (&__submatches)[_Np],
6245                              regex_constants::match_flag_type __m =
6246                                       regex_constants::match_default) = delete;
6247 #endif
6248
6249     regex_token_iterator(const regex_token_iterator&);
6250     regex_token_iterator& operator=(const regex_token_iterator&);
6251
6252     bool operator==(const regex_token_iterator& __x) const;
6253     _LIBCPP_INLINE_VISIBILITY
6254     bool operator!=(const regex_token_iterator& __x) const {return !(*this == __x);}
6255
6256     _LIBCPP_INLINE_VISIBILITY
6257     const value_type& operator*() const {return *__result_;}
6258     _LIBCPP_INLINE_VISIBILITY
6259     const value_type* operator->() const {return __result_;}
6260
6261     regex_token_iterator& operator++();
6262     _LIBCPP_INLINE_VISIBILITY
6263     regex_token_iterator operator++(int)
6264     {
6265         regex_token_iterator __t(*this);
6266         ++(*this);
6267         return __t;
6268     }
6269
6270 private:
6271     void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
6272     void __establish_result () {
6273         if (__subs_[__n_] == -1)
6274             __result_ = &__position_->prefix();
6275         else
6276             __result_ = &(*__position_)[__subs_[__n_]];
6277         }
6278 };
6279
6280 template <class _BidirectionalIterator, class _CharT, class _Traits>
6281 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6282     regex_token_iterator()
6283     : __result_(nullptr),
6284       __suffix_(),
6285       __n_(0)
6286 {
6287 }
6288
6289 template <class _BidirectionalIterator, class _CharT, class _Traits>
6290 void
6291 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6292     __init(_BidirectionalIterator __a, _BidirectionalIterator __b)
6293 {
6294     if (__position_ != _Position())
6295         __establish_result ();
6296     else if (__subs_[__n_] == -1)
6297     {
6298         __suffix_.matched = true;
6299         __suffix_.first = __a;
6300         __suffix_.second = __b;
6301         __result_ = &__suffix_;
6302     }
6303     else
6304         __result_ = nullptr;
6305 }
6306
6307 template <class _BidirectionalIterator, class _CharT, class _Traits>
6308 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6309     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6310                          const regex_type& __re, int __submatch,
6311                          regex_constants::match_flag_type __m)
6312     : __position_(__a, __b, __re, __m),
6313       __n_(0),
6314       __subs_(1, __submatch)
6315 {
6316     __init(__a, __b);
6317 }
6318
6319 template <class _BidirectionalIterator, class _CharT, class _Traits>
6320 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6321     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6322                          const regex_type& __re, const vector<int>& __submatches,
6323                          regex_constants::match_flag_type __m)
6324     : __position_(__a, __b, __re, __m),
6325       __n_(0),
6326       __subs_(__submatches)
6327 {
6328     __init(__a, __b);
6329 }
6330
6331 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6332
6333 template <class _BidirectionalIterator, class _CharT, class _Traits>
6334 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6335     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6336                          const regex_type& __re,
6337                          initializer_list<int> __submatches,
6338                          regex_constants::match_flag_type __m)
6339     : __position_(__a, __b, __re, __m),
6340       __n_(0),
6341       __subs_(__submatches)
6342 {
6343     __init(__a, __b);
6344 }
6345
6346 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6347
6348 template <class _BidirectionalIterator, class _CharT, class _Traits>
6349 template <size_t _Np>
6350 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6351     regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6352                              const regex_type& __re,
6353                              const int (&__submatches)[_Np],
6354                              regex_constants::match_flag_type __m)
6355     : __position_(__a, __b, __re, __m),
6356       __n_(0),
6357       __subs_(__submatches, __submatches + _Np)
6358 {
6359     __init(__a, __b);
6360 }
6361
6362 template <class _BidirectionalIterator, class _CharT, class _Traits>
6363 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6364     regex_token_iterator(const regex_token_iterator& __x)
6365     : __position_(__x.__position_),
6366       __result_(__x.__result_),
6367       __suffix_(__x.__suffix_),
6368       __n_(__x.__n_),
6369       __subs_(__x.__subs_)
6370 {
6371     if (__x.__result_ == &__x.__suffix_)
6372         __result_ = &__suffix_;
6373     else if ( __result_ != nullptr )
6374         __establish_result ();
6375 }
6376
6377 template <class _BidirectionalIterator, class _CharT, class _Traits>
6378 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6379 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6380     operator=(const regex_token_iterator& __x)
6381 {
6382     if (this != &__x)
6383     {
6384         __position_ = __x.__position_;
6385         if (__x.__result_ == &__x.__suffix_)
6386             __result_ = &__suffix_;
6387         else
6388             __result_ = __x.__result_;
6389         __suffix_ = __x.__suffix_;
6390         __n_ = __x.__n_;
6391         __subs_ = __x.__subs_;
6392
6393         if ( __result_ != nullptr && __result_ != &__suffix_ )
6394             __establish_result();
6395     }
6396     return *this;
6397 }
6398
6399 template <class _BidirectionalIterator, class _CharT, class _Traits>
6400 bool
6401 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6402     operator==(const regex_token_iterator& __x) const
6403 {
6404     if (__result_ == nullptr && __x.__result_ == nullptr)
6405         return true;
6406     if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ &&
6407             __suffix_ == __x.__suffix_)
6408         return true;
6409     if (__result_ == nullptr || __x.__result_ == nullptr)
6410         return false;
6411     if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
6412         return false;
6413     return __position_ == __x.__position_ && __n_ == __x.__n_ &&
6414            __subs_ == __x.__subs_;
6415 }
6416
6417 template <class _BidirectionalIterator, class _CharT, class _Traits>
6418 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6419 regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6420 {
6421     _Position __prev = __position_;
6422     if (__result_ == &__suffix_)
6423         __result_ = nullptr;
6424     else if (static_cast<size_t>(__n_ + 1) < __subs_.size())
6425     {
6426         ++__n_;
6427         __establish_result();
6428     }
6429     else
6430     {
6431         __n_ = 0;
6432         ++__position_;
6433         if (__position_ != _Position())
6434             __establish_result();
6435         else
6436         {
6437             if (_VSTD::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end()
6438                 && __prev->suffix().length() != 0)
6439             {
6440                 __suffix_.matched = true;
6441                 __suffix_.first = __prev->suffix().first;
6442                 __suffix_.second = __prev->suffix().second;
6443                 __result_ = &__suffix_;
6444             }
6445             else
6446                 __result_ = nullptr;
6447         }
6448     }
6449     return *this;
6450 }
6451
6452 typedef regex_token_iterator<const char*>             cregex_token_iterator;
6453 typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
6454 typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
6455 typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
6456
6457 // regex_replace
6458
6459 template <class _OutputIterator, class _BidirectionalIterator,
6460           class _Traits, class _CharT>
6461 _OutputIterator
6462 regex_replace(_OutputIterator __output,
6463               _BidirectionalIterator __first, _BidirectionalIterator __last,
6464               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6465               regex_constants::match_flag_type __flags = regex_constants::match_default)
6466 {
6467     typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
6468     _Iter __i(__first, __last, __e, __flags);
6469     _Iter __eof;
6470     if (__i == __eof)
6471     {
6472         if (!(__flags & regex_constants::format_no_copy))
6473             __output = _VSTD::copy(__first, __last, __output);
6474     }
6475     else
6476     {
6477         sub_match<_BidirectionalIterator> __lm;
6478         for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i)
6479         {
6480             if (!(__flags & regex_constants::format_no_copy))
6481                 __output = _VSTD::copy(__i->prefix().first, __i->prefix().second, __output);
6482             __output = __i->format(__output, __fmt, __fmt + __len, __flags);
6483             __lm = __i->suffix();
6484             if (__flags & regex_constants::format_first_only)
6485                 break;
6486         }
6487         if (!(__flags & regex_constants::format_no_copy))
6488             __output = _VSTD::copy(__lm.first, __lm.second, __output);
6489     }
6490     return __output;
6491 }
6492
6493 template <class _OutputIterator, class _BidirectionalIterator,
6494           class _Traits, class _CharT, class _ST, class _SA>
6495 inline _LIBCPP_INLINE_VISIBILITY
6496 _OutputIterator
6497 regex_replace(_OutputIterator __output,
6498               _BidirectionalIterator __first, _BidirectionalIterator __last,
6499               const basic_regex<_CharT, _Traits>& __e,
6500               const basic_string<_CharT, _ST, _SA>& __fmt,
6501               regex_constants::match_flag_type __flags = regex_constants::match_default)
6502 {
6503     return _VSTD::regex_replace(__output, __first, __last, __e, __fmt.c_str(), __flags);
6504 }
6505
6506 template <class _Traits, class _CharT, class _ST, class _SA, class _FST,
6507           class _FSA>
6508 inline _LIBCPP_INLINE_VISIBILITY
6509 basic_string<_CharT, _ST, _SA>
6510 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6511               const basic_regex<_CharT, _Traits>& __e,
6512               const basic_string<_CharT, _FST, _FSA>& __fmt,
6513               regex_constants::match_flag_type __flags = regex_constants::match_default)
6514 {
6515     basic_string<_CharT, _ST, _SA> __r;
6516     _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6517                         __fmt.c_str(), __flags);
6518     return __r;
6519 }
6520
6521 template <class _Traits, class _CharT, class _ST, class _SA>
6522 inline _LIBCPP_INLINE_VISIBILITY
6523 basic_string<_CharT, _ST, _SA>
6524 regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6525               const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6526               regex_constants::match_flag_type __flags = regex_constants::match_default)
6527 {
6528     basic_string<_CharT, _ST, _SA> __r;
6529     _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6530                         __fmt, __flags);
6531     return __r;
6532 }
6533
6534 template <class _Traits, class _CharT, class _ST, class _SA>
6535 inline _LIBCPP_INLINE_VISIBILITY
6536 basic_string<_CharT>
6537 regex_replace(const _CharT* __s,
6538               const basic_regex<_CharT, _Traits>& __e,
6539               const basic_string<_CharT, _ST, _SA>& __fmt,
6540               regex_constants::match_flag_type __flags = regex_constants::match_default)
6541 {
6542     basic_string<_CharT> __r;
6543     _VSTD::regex_replace(back_inserter(__r), __s,
6544                         __s + char_traits<_CharT>::length(__s), __e,
6545                         __fmt.c_str(), __flags);
6546     return __r;
6547 }
6548
6549 template <class _Traits, class _CharT>
6550 inline _LIBCPP_INLINE_VISIBILITY
6551 basic_string<_CharT>
6552 regex_replace(const _CharT* __s,
6553               const basic_regex<_CharT, _Traits>& __e,
6554               const _CharT* __fmt,
6555               regex_constants::match_flag_type __flags = regex_constants::match_default)
6556 {
6557     basic_string<_CharT> __r;
6558     _VSTD::regex_replace(back_inserter(__r), __s,
6559                         __s + char_traits<_CharT>::length(__s), __e,
6560                         __fmt, __flags);
6561     return __r;
6562 }
6563
6564 _LIBCPP_END_NAMESPACE_STD
6565
6566 #endif  // _LIBCPP_REGEX