Coverage Report

Created: 2020-02-15 09:57

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