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