libcxx/include/regex

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