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