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