Coverage Report

Created: 2020-07-11 14:00

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