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