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