contrib/llvm-project/libcxx/include/regex

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