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