Project

General

Profile

Statistics
| Revision:

root / lab4 / .minix-src / include / c++ / regex @ 13

History | View | Annotate | Download (212 KB)

1
// -*- C++ -*-
2
//===--------------------------- regex ------------------------------------===//
3
//
4
//                     The LLVM Compiler Infrastructure
5
//
6
// This file is dual licensed under the MIT and the University of Illinois Open
7
// Source Licenses. See LICENSE.TXT for details.
8
//
9
//===----------------------------------------------------------------------===//
10

    
11
#ifndef _LIBCPP_REGEX
12
#define _LIBCPP_REGEX
13

    
14
/*
15
    regex synopsis
16

    
17
#include <initializer_list>
18

    
19
namespace std
20
{
21

    
22
namespace regex_constants
23
{
24

    
25
emum syntax_option_type
26
{
27
    icase      = unspecified,
28
    nosubs     = unspecified,
29
    optimize   = unspecified,
30
    collate    = unspecified,
31
    ECMAScript = unspecified,
32
    basic      = unspecified,
33
    extended   = unspecified,
34
    awk        = unspecified,
35
    grep       = unspecified,
36
    egrep      = unspecified
37
};
38

    
39
constexpr syntax_option_type operator~(syntax_option_type f);
40
constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
41
constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);
42

    
43
enum match_flag_type
44
{
45
    match_default     = 0,
46
    match_not_bol     = unspecified,
47
    match_not_eol     = unspecified,
48
    match_not_bow     = unspecified,
49
    match_not_eow     = unspecified,
50
    match_any         = unspecified,
51
    match_not_null    = unspecified,
52
    match_continuous  = unspecified,
53
    match_prev_avail  = unspecified,
54
    format_default    = 0,
55
    format_sed        = unspecified,
56
    format_no_copy    = unspecified,
57
    format_first_only = unspecified
58
};
59

    
60
constexpr match_flag_type operator~(match_flag_type f);
61
constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
62
constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);
63

    
64
enum error_type
65
{
66
    error_collate    = unspecified,
67
    error_ctype      = unspecified,
68
    error_escape     = unspecified,
69
    error_backref    = unspecified,
70
    error_brack      = unspecified,
71
    error_paren      = unspecified,
72
    error_brace      = unspecified,
73
    error_badbrace   = unspecified,
74
    error_range      = unspecified,
75
    error_space      = unspecified,
76
    error_badrepeat  = unspecified,
77
    error_complexity = unspecified,
78
    error_stack      = unspecified
79
};
80

    
81
}  // regex_constants
82

    
83
class regex_error
84
    : public runtime_error
85
{
86
public:
87
    explicit regex_error(regex_constants::error_type ecode);
88
    regex_constants::error_type code() const;
89
};
90

    
91
template <class charT>
92
struct regex_traits
93
{
94
public:
95
    typedef charT                   char_type;
96
    typedef basic_string<char_type> string_type;
97
    typedef locale                  locale_type;
98
    typedef /bitmask_type/          char_class_type;
99

    
100
    regex_traits();
101

    
102
    static size_t length(const char_type* p);
103
    charT translate(charT c) const;
104
    charT translate_nocase(charT c) const;
105
    template <class ForwardIterator>
106
        string_type
107
        transform(ForwardIterator first, ForwardIterator last) const;
108
    template <class ForwardIterator>
109
        string_type
110
        transform_primary( ForwardIterator first, ForwardIterator last) const;
111
    template <class ForwardIterator>
112
        string_type
113
        lookup_collatename(ForwardIterator first, ForwardIterator last) const;
114
    template <class ForwardIterator>
115
        char_class_type
116
        lookup_classname(ForwardIterator first, ForwardIterator last,
117
                         bool icase = false) const;
118
    bool isctype(charT c, char_class_type f) const;
119
    int value(charT ch, int radix) const;
120
    locale_type imbue(locale_type l);
121
    locale_type getloc()const;
122
};
123

    
124
template <class charT, class traits = regex_traits<charT>>
125
class basic_regex
126
{
127
public:
128
    // types:
129
    typedef charT                               value_type;
130
    typedef regex_constants::syntax_option_type flag_type;
131
    typedef typename traits::locale_type        locale_type;
132

    
133
    // constants:
134
    static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;
135
    static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
136
    static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;
137
    static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;
138
    static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
139
    static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;
140
    static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;
141
    static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;
142
    static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;
143
    static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;
144

    
145
    // construct/copy/destroy:
146
    basic_regex();
147
    explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);
148
    basic_regex(const charT* p, size_t len, flag_type f);
149
    basic_regex(const basic_regex&);
150
    basic_regex(basic_regex&&) noexcept;
151
    template <class ST, class SA>
152
        explicit basic_regex(const basic_string<charT, ST, SA>& p,
153
                             flag_type f = regex_constants::ECMAScript);
154
    template <class ForwardIterator>
155
        basic_regex(ForwardIterator first, ForwardIterator last,
156
                    flag_type f = regex_constants::ECMAScript);
157
    basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
158

    
159
    ~basic_regex();
160

    
161
    basic_regex& operator=(const basic_regex&);
162
    basic_regex& operator=(basic_regex&&) noexcept;
163
    basic_regex& operator=(const charT* ptr);
164
    basic_regex& operator=(initializer_list<charT> il);
165
    template <class ST, class SA>
166
        basic_regex& operator=(const basic_string<charT, ST, SA>& p);
167

    
168
    // assign:
169
    basic_regex& assign(const basic_regex& that);
170
    basic_regex& assign(basic_regex&& that) noexcept;
171
    basic_regex& assign(const charT* ptr, flag_type f = regex_constants::ECMAScript);
172
    basic_regex& assign(const charT* p, size_t len, flag_type f);
173
    template <class string_traits, class A>
174
        basic_regex& assign(const basic_string<charT, string_traits, A>& s,
175
                            flag_type f = regex_constants::ECMAScript);
176
    template <class InputIterator>
177
        basic_regex& assign(InputIterator first, InputIterator last,
178
                            flag_type f = regex_constants::ECMAScript);
179
    basic_regex& assign(initializer_list<charT>, flag_type = regex_constants::ECMAScript);
180

    
181
    // const operations:
182
    unsigned mark_count() const;
183
    flag_type flags() const;
184

    
185
    // locale:
186
    locale_type imbue(locale_type loc);
187
    locale_type getloc() const;
188

    
189
    // swap:
190
    void swap(basic_regex&);
191
};
192

    
193
typedef basic_regex<char>    regex;
194
typedef basic_regex<wchar_t> wregex;
195

    
196
template <class charT, class traits>
197
    void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);
198

    
199
template <class BidirectionalIterator>
200
class sub_match
201
    : public pair<BidirectionalIterator, BidirectionalIterator>
202
{
203
public:
204
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
205
    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
206
    typedef BidirectionalIterator                                      iterator;
207
    typedef basic_string<value_type>                                string_type;
208

    
209
    bool matched;
210

    
211
    constexpr sub_match();
212

    
213
    difference_type length() const;
214
    operator string_type() const;
215
    string_type str() const;
216

    
217
    int compare(const sub_match& s) const;
218
    int compare(const string_type& s) const;
219
    int compare(const value_type* s) const;
220
};
221

    
222
typedef sub_match<const char*>             csub_match;
223
typedef sub_match<const wchar_t*>          wcsub_match;
224
typedef sub_match<string::const_iterator>  ssub_match;
225
typedef sub_match<wstring::const_iterator> wssub_match;
226

    
227
template <class BiIter>
228
    bool
229
    operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
230

    
231
template <class BiIter>
232
    bool
233
    operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
234

    
235
template <class BiIter>
236
    bool
237
    operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
238

    
239
template <class BiIter>
240
    bool
241
    operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
242

    
243
template <class BiIter>
244
    bool
245
    operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
246

    
247
template <class BiIter>
248
    bool
249
    operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);
250

    
251
template <class BiIter, class ST, class SA>
252
    bool
253
    operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
254
               const sub_match<BiIter>& rhs);
255

    
256
template <class BiIter, class ST, class SA>
257
    bool
258
    operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
259
               const sub_match<BiIter>& rhs);
260

    
261
template <class BiIter, class ST, class SA>
262
    bool
263
    operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
264
              const sub_match<BiIter>& rhs);
265

    
266
template <class BiIter, class ST, class SA>
267
    bool
268
    operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
269
              const sub_match<BiIter>& rhs);
270

    
271
template <class BiIter, class ST, class SA>
272
    bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
273
                    const sub_match<BiIter>& rhs);
274

    
275
template <class BiIter, class ST, class SA>
276
    bool
277
    operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
278
               const sub_match<BiIter>& rhs);
279

    
280
template <class BiIter, class ST, class SA>
281
    bool
282
    operator==(const sub_match<BiIter>& lhs,
283
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
284

    
285
template <class BiIter, class ST, class SA>
286
    bool
287
    operator!=(const sub_match<BiIter>& lhs,
288
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
289

    
290
template <class BiIter, class ST, class SA>
291
    bool
292
    operator<(const sub_match<BiIter>& lhs,
293
              const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
294

    
295
template <class BiIter, class ST, class SA>
296
    bool operator>(const sub_match<BiIter>& lhs,
297
                   const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
298

    
299
template <class BiIter, class ST, class SA>
300
    bool
301
    operator>=(const sub_match<BiIter>& lhs,
302
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
303

    
304
template <class BiIter, class ST, class SA>
305
    bool
306
    operator<=(const sub_match<BiIter>& lhs,
307
               const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);
308

    
309
template <class BiIter>
310
    bool
311
    operator==(typename iterator_traits<BiIter>::value_type const* lhs,
312
               const sub_match<BiIter>& rhs);
313

    
314
template <class BiIter>
315
    bool
316
    operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
317
               const sub_match<BiIter>& rhs);
318

    
319
template <class BiIter>
320
    bool
321
    operator<(typename iterator_traits<BiIter>::value_type const* lhs,
322
              const sub_match<BiIter>& rhs);
323

    
324
template <class BiIter>
325
    bool
326
    operator>(typename iterator_traits<BiIter>::value_type const* lhs,
327
              const sub_match<BiIter>& rhs);
328

    
329
template <class BiIter>
330
    bool
331
    operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
332
               const sub_match<BiIter>& rhs);
333

    
334
template <class BiIter>
335
    bool
336
    operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
337
               const sub_match<BiIter>& rhs);
338

    
339
template <class BiIter>
340
    bool
341
    operator==(const sub_match<BiIter>& lhs,
342
               typename iterator_traits<BiIter>::value_type const* rhs);
343

    
344
template <class BiIter>
345
    bool
346
    operator!=(const sub_match<BiIter>& lhs,
347
               typename iterator_traits<BiIter>::value_type const* rhs);
348

    
349
template <class BiIter>
350
    bool
351
    operator<(const sub_match<BiIter>& lhs,
352
              typename iterator_traits<BiIter>::value_type const* rhs);
353

    
354
template <class BiIter>
355
    bool
356
    operator>(const sub_match<BiIter>& lhs,
357
              typename iterator_traits<BiIter>::value_type const* rhs);
358

    
359
template <class BiIter>
360
    bool
361
    operator>=(const sub_match<BiIter>& lhs,
362
               typename iterator_traits<BiIter>::value_type const* rhs);
363

    
364
template <class BiIter>
365
    bool
366
    operator<=(const sub_match<BiIter>& lhs,
367
               typename iterator_traits<BiIter>::value_type const* rhs);
368

    
369
template <class BiIter>
370
    bool
371
    operator==(typename iterator_traits<BiIter>::value_type const& lhs,
372
               const sub_match<BiIter>& rhs);
373

    
374
template <class BiIter>
375
    bool
376
    operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
377
               const sub_match<BiIter>& rhs);
378

    
379
template <class BiIter>
380
    bool
381
    operator<(typename iterator_traits<BiIter>::value_type const& lhs,
382
              const sub_match<BiIter>& rhs);
383

    
384
template <class BiIter>
385
    bool
386
    operator>(typename iterator_traits<BiIter>::value_type const& lhs,
387
              const sub_match<BiIter>& rhs);
388

    
389
template <class BiIter>
390
    bool
391
    operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
392
               const sub_match<BiIter>& rhs);
393

    
394
template <class BiIter>
395
    bool
396
    operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
397
               const sub_match<BiIter>& rhs);
398

    
399
template <class BiIter>
400
    bool
401
    operator==(const sub_match<BiIter>& lhs,
402
               typename iterator_traits<BiIter>::value_type const& rhs);
403

    
404
template <class BiIter>
405
    bool
406
    operator!=(const sub_match<BiIter>& lhs,
407
               typename iterator_traits<BiIter>::value_type const& rhs);
408

    
409
template <class BiIter>
410
    bool
411
    operator<(const sub_match<BiIter>& lhs,
412
              typename iterator_traits<BiIter>::value_type const& rhs);
413

    
414
template <class BiIter>
415
    bool
416
    operator>(const sub_match<BiIter>& lhs,
417
              typename iterator_traits<BiIter>::value_type const& rhs);
418

    
419
template <class BiIter>
420
    bool
421
    operator>=(const sub_match<BiIter>& lhs,
422
               typename iterator_traits<BiIter>::value_type const& rhs);
423

    
424
template <class BiIter>
425
    bool
426
    operator<=(const sub_match<BiIter>& lhs,
427
               typename iterator_traits<BiIter>::value_type const& rhs);
428

    
429
template <class charT, class ST, class BiIter>
430
    basic_ostream<charT, ST>&
431
    operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);
432

    
433
template <class BidirectionalIterator,
434
          class Allocator = allocator<sub_match<BidirectionalIterator>>>
435
class match_results
436
{
437
public:
438
    typedef sub_match<BidirectionalIterator>                  value_type;
439
    typedef const value_type&                                 const_reference;
440
    typedef value_type&                                       reference;
441
    typedef /implementation-defined/                          const_iterator;
442
    typedef const_iterator                                    iterator;
443
    typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
444
    typedef typename allocator_traits<Allocator>::size_type   size_type;
445
    typedef Allocator                                         allocator_type;
446
    typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;
447
    typedef basic_string<char_type>                           string_type;
448

    
449
    // construct/copy/destroy:
450
    explicit match_results(const Allocator& a = Allocator());
451
    match_results(const match_results& m);
452
    match_results(match_results&& m) noexcept;
453
    match_results& operator=(const match_results& m);
454
    match_results& operator=(match_results&& m);
455
    ~match_results();
456

    
457
    bool ready() const;
458

    
459
    // size:
460
    size_type size() const;
461
    size_type max_size() const;
462
    bool empty() const;
463

    
464
    // element access:
465
    difference_type length(size_type sub = 0) const;
466
    difference_type position(size_type sub = 0) const;
467
    string_type str(size_type sub = 0) const;
468
    const_reference operator[](size_type n) const;
469

    
470
    const_reference prefix() const;
471
    const_reference suffix() const;
472

    
473
    const_iterator begin() const;
474
    const_iterator end() const;
475
    const_iterator cbegin() const;
476
    const_iterator cend() const;
477

    
478
    // format:
479
    template <class OutputIter>
480
        OutputIter
481
        format(OutputIter out, const char_type* fmt_first,
482
               const char_type* fmt_last,
483
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
484
    template <class OutputIter, class ST, class SA>
485
        OutputIter
486
        format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
487
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
488
    template <class ST, class SA>
489
        basic_string<char_type, ST, SA>
490
        format(const basic_string<char_type, ST, SA>& fmt,
491
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
492
    string_type
493
        format(const char_type* fmt,
494
               regex_constants::match_flag_type flags = regex_constants::format_default) const;
495

    
496
    // allocator:
497
    allocator_type get_allocator() const;
498

    
499
    // swap:
500
    void swap(match_results& that);
501
};
502

    
503
typedef match_results<const char*>             cmatch;
504
typedef match_results<const wchar_t*>          wcmatch;
505
typedef match_results<string::const_iterator>  smatch;
506
typedef match_results<wstring::const_iterator> wsmatch;
507

    
508
template <class BidirectionalIterator, class Allocator>
509
    bool
510
    operator==(const match_results<BidirectionalIterator, Allocator>& m1,
511
               const match_results<BidirectionalIterator, Allocator>& m2);
512

    
513
template <class BidirectionalIterator, class Allocator>
514
    bool
515
    operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
516
               const match_results<BidirectionalIterator, Allocator>& m2);
517

    
518
template <class BidirectionalIterator, class Allocator>
519
    void
520
    swap(match_results<BidirectionalIterator, Allocator>& m1,
521
         match_results<BidirectionalIterator, Allocator>& m2);
522

    
523
template <class BidirectionalIterator, class Allocator, class charT, class traits>
524
    bool
525
    regex_match(BidirectionalIterator first, BidirectionalIterator last,
526
                match_results<BidirectionalIterator, Allocator>& m,
527
                const basic_regex<charT, traits>& e,
528
                regex_constants::match_flag_type flags = regex_constants::match_default);
529

    
530
template <class BidirectionalIterator, class charT, class traits>
531
    bool
532
    regex_match(BidirectionalIterator first, BidirectionalIterator last,
533
                const basic_regex<charT, traits>& e,
534
                regex_constants::match_flag_type flags = regex_constants::match_default);
535

    
536
template <class charT, class Allocator, class traits>
537
    bool
538
    regex_match(const charT* str, match_results<const charT*, Allocator>& m,
539
                const basic_regex<charT, traits>& e,
540
                regex_constants::match_flag_type flags = regex_constants::match_default);
541

    
542
template <class ST, class SA, class Allocator, class charT, class traits>
543
    bool
544
    regex_match(const basic_string<charT, ST, SA>& s,
545
                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
546
                const basic_regex<charT, traits>& e,
547
                regex_constants::match_flag_type flags = regex_constants::match_default);
548

    
549
template <class ST, class SA, class Allocator, class charT, class traits>
550
    bool
551
    regex_match(const basic_string<charT, ST, SA>&& s,
552
                match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
553
                const basic_regex<charT, traits>& e,
554
                regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14
555

    
556
template <class charT, class traits>
557
    bool
558
    regex_match(const charT* str, const basic_regex<charT, traits>& e,
559
                regex_constants::match_flag_type flags = regex_constants::match_default);
560

    
561
template <class ST, class SA, class charT, class traits>
562
    bool
563
    regex_match(const basic_string<charT, ST, SA>& s,
564
                const basic_regex<charT, traits>& e,
565
                regex_constants::match_flag_type flags = regex_constants::match_default);
566

    
567
template <class BidirectionalIterator, class Allocator, class charT, class traits>
568
    bool
569
    regex_search(BidirectionalIterator first, BidirectionalIterator last,
570
                 match_results<BidirectionalIterator, Allocator>& m,
571
                 const basic_regex<charT, traits>& e,
572
                 regex_constants::match_flag_type flags = regex_constants::match_default);
573

    
574
template <class BidirectionalIterator, class charT, class traits>
575
    bool
576
    regex_search(BidirectionalIterator first, BidirectionalIterator last,
577
                 const basic_regex<charT, traits>& e,
578
                 regex_constants::match_flag_type flags = regex_constants::match_default);
579

    
580
template <class charT, class Allocator, class traits>
581
    bool
582
    regex_search(const charT* str, match_results<const charT*, Allocator>& m,
583
                 const basic_regex<charT, traits>& e,
584
                 regex_constants::match_flag_type flags = regex_constants::match_default);
585

    
586
template <class charT, class traits>
587
    bool
588
    regex_search(const charT* str, const basic_regex<charT, traits>& e,
589
                 regex_constants::match_flag_type flags = regex_constants::match_default);
590

    
591
template <class ST, class SA, class charT, class traits>
592
    bool
593
    regex_search(const basic_string<charT, ST, SA>& s,
594
                 const basic_regex<charT, traits>& e,
595
                 regex_constants::match_flag_type flags = regex_constants::match_default);
596

    
597
template <class ST, class SA, class Allocator, class charT, class traits>
598
    bool
599
    regex_search(const basic_string<charT, ST, SA>& s,
600
                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
601
                 const basic_regex<charT, traits>& e,
602
                 regex_constants::match_flag_type flags = regex_constants::match_default);
603

    
604
template <class ST, class SA, class Allocator, class charT, class traits>
605
    bool
606
    regex_search(const basic_string<charT, ST, SA>&& s,
607
                 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
608
                 const basic_regex<charT, traits>& e,
609
                 regex_constants::match_flag_type flags = regex_constants::match_default) = delete; // C++14
610

    
611
template <class OutputIterator, class BidirectionalIterator,
612
          class traits, class charT, class ST, class SA>
613
    OutputIterator
614
    regex_replace(OutputIterator out,
615
                  BidirectionalIterator first, BidirectionalIterator last,
616
                  const basic_regex<charT, traits>& e,
617
                  const basic_string<charT, ST, SA>& fmt,
618
                  regex_constants::match_flag_type flags = regex_constants::match_default);
619

    
620
template <class OutputIterator, class BidirectionalIterator,
621
          class traits, class charT>
622
    OutputIterator
623
    regex_replace(OutputIterator out,
624
                  BidirectionalIterator first, BidirectionalIterator last,
625
                  const basic_regex<charT, traits>& e, const charT* fmt,
626
                  regex_constants::match_flag_type flags = regex_constants::match_default);
627

    
628
template <class traits, class charT, class ST, class SA, class FST, class FSA>>
629
    basic_string<charT, ST, SA>
630
    regex_replace(const basic_string<charT, ST, SA>& s,
631
                  const basic_regex<charT, traits>& e,
632
                  const basic_string<charT, FST, FSA>& fmt,
633
                  regex_constants::match_flag_type flags = regex_constants::match_default);
634

    
635
template <class traits, class charT, class ST, class SA>
636
    basic_string<charT, ST, SA>
637
    regex_replace(const basic_string<charT, ST, SA>& s,
638
                  const basic_regex<charT, traits>& e, const charT* fmt,
639
                  regex_constants::match_flag_type flags = regex_constants::match_default);
640

    
641
template <class traits, class charT, class ST, class SA>
642
    basic_string<charT>
643
    regex_replace(const charT* s,
644
                  const basic_regex<charT, traits>& e,
645
                  const basic_string<charT, ST, SA>& fmt,
646
                  regex_constants::match_flag_type flags = regex_constants::match_default);
647

    
648
template <class traits, class charT>
649
    basic_string<charT>
650
    regex_replace(const charT* s,
651
                  const basic_regex<charT, traits>& e,
652
                  const charT* fmt,
653
                  regex_constants::match_flag_type flags = regex_constants::match_default);
654

    
655
template <class BidirectionalIterator,
656
          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
657
          class traits = regex_traits<charT>>
658
class regex_iterator
659
{
660
public:
661
    typedef basic_regex<charT, traits>           regex_type;
662
    typedef match_results<BidirectionalIterator> value_type;
663
    typedef ptrdiff_t                            difference_type;
664
    typedef const value_type*                    pointer;
665
    typedef const value_type&                    reference;
666
    typedef forward_iterator_tag                 iterator_category;
667

    
668
    regex_iterator();
669
    regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
670
                   const regex_type& re,
671
                   regex_constants::match_flag_type m = regex_constants::match_default);
672
    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
673
                   const regex_type&& __re,
674
                   regex_constants::match_flag_type __m 
675
                                     = regex_constants::match_default) = delete; // C++14
676
    regex_iterator(const regex_iterator&);
677
    regex_iterator& operator=(const regex_iterator&);
678

    
679
    bool operator==(const regex_iterator&) const;
680
    bool operator!=(const regex_iterator&) const;
681

    
682
    const value_type& operator*() const;
683
    const value_type* operator->() const;
684

    
685
    regex_iterator& operator++();
686
    regex_iterator operator++(int);
687
};
688

    
689
typedef regex_iterator<const char*>             cregex_iterator;
690
typedef regex_iterator<const wchar_t*>          wcregex_iterator;
691
typedef regex_iterator<string::const_iterator>  sregex_iterator;
692
typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
693

    
694
template <class BidirectionalIterator,
695
          class charT = typename iterator_traits< BidirectionalIterator>::value_type,
696
          class traits = regex_traits<charT>>
697
class regex_token_iterator
698
{
699
public:
700
    typedef basic_regex<charT, traits>       regex_type;
701
    typedef sub_match<BidirectionalIterator> value_type;
702
    typedef ptrdiff_t                        difference_type;
703
    typedef const value_type*                pointer;
704
    typedef const value_type&                reference;
705
    typedef forward_iterator_tag             iterator_category;
706

    
707
    regex_token_iterator();
708
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
709
                         const regex_type& re, int submatch = 0,
710
                         regex_constants::match_flag_type m = regex_constants::match_default);
711
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
712
                         const regex_type&& re, int submatch = 0,
713
                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
714
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
715
                         const regex_type& re, const vector<int>& submatches,
716
                         regex_constants::match_flag_type m = regex_constants::match_default);
717
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
718
                         const regex_type&& re, const vector<int>& submatches,
719
                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
720
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
721
                         const regex_type& re, initializer_list<int> submatches,
722
                         regex_constants::match_flag_type m = regex_constants::match_default);
723
    regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
724
                         const regex_type&& re, initializer_list<int> submatches,
725
                         regex_constants::match_flag_type m = regex_constants::match_default) = delete; // C++14
726
    template <size_t N>
727
        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
728
                             const regex_type& re, const int (&submatches)[N],
729
                             regex_constants::match_flag_type m = regex_constants::match_default);
730
    template <size_t N>
731
        regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
732
                             const regex_type& re, const int (&submatches)[N],
733
                             regex_constants::match_flag_type m = regex_constants::match_default) = delete // C++14;
734
    regex_token_iterator(const regex_token_iterator&);
735
    regex_token_iterator& operator=(const regex_token_iterator&);
736

    
737
    bool operator==(const regex_token_iterator&) const;
738
    bool operator!=(const regex_token_iterator&) const;
739

    
740
    const value_type& operator*() const;
741
    const value_type* operator->() const;
742

    
743
    regex_token_iterator& operator++();
744
    regex_token_iterator operator++(int);
745
};
746

    
747
typedef regex_token_iterator<const char*>             cregex_token_iterator;
748
typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
749
typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
750
typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
751

    
752
} // std
753
*/
754

    
755
#include <__config>
756
#include <stdexcept>
757
#include <__locale>
758
#include <initializer_list>
759
#include <utility>
760
#include <iterator>
761
#include <string>
762
#include <memory>
763
#include <vector>
764
#include <deque>
765
#include <cassert>
766

    
767
#include <__undef_min_max>
768

    
769
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
770
#pragma GCC system_header
771
#endif
772

    
773
_LIBCPP_BEGIN_NAMESPACE_STD
774

    
775
namespace regex_constants
776
{
777

    
778
// syntax_option_type
779

    
780
enum syntax_option_type
781
{
782
    icase      = 1 << 0,
783
    nosubs     = 1 << 1,
784
    optimize   = 1 << 2,
785
    collate    = 1 << 3,
786
    ECMAScript = 0,
787
    basic      = 1 << 4,
788
    extended   = 1 << 5,
789
    awk        = 1 << 6,
790
    grep       = 1 << 7,
791
    egrep      = 1 << 8
792
};
793

    
794
inline _LIBCPP_INLINE_VISIBILITY
795
_LIBCPP_CONSTEXPR
796
syntax_option_type
797
operator~(syntax_option_type __x)
798
{
799
    return syntax_option_type(~int(__x) & 0x1FF);
800
}
801

    
802
inline _LIBCPP_INLINE_VISIBILITY
803
_LIBCPP_CONSTEXPR
804
syntax_option_type
805
operator&(syntax_option_type __x, syntax_option_type __y)
806
{
807
    return syntax_option_type(int(__x) & int(__y));
808
}
809

    
810
inline _LIBCPP_INLINE_VISIBILITY
811
_LIBCPP_CONSTEXPR
812
syntax_option_type
813
operator|(syntax_option_type __x, syntax_option_type __y)
814
{
815
    return syntax_option_type(int(__x) | int(__y));
816
}
817

    
818
inline _LIBCPP_INLINE_VISIBILITY
819
_LIBCPP_CONSTEXPR
820
syntax_option_type
821
operator^(syntax_option_type __x, syntax_option_type __y)
822
{
823
    return syntax_option_type(int(__x) ^ int(__y));
824
}
825

    
826
inline _LIBCPP_INLINE_VISIBILITY
827
syntax_option_type&
828
operator&=(syntax_option_type& __x, syntax_option_type __y)
829
{
830
    __x = __x & __y;
831
    return __x;
832
}
833

    
834
inline _LIBCPP_INLINE_VISIBILITY
835
syntax_option_type&
836
operator|=(syntax_option_type& __x, syntax_option_type __y)
837
{
838
    __x = __x | __y;
839
    return __x;
840
}
841

    
842
inline _LIBCPP_INLINE_VISIBILITY
843
syntax_option_type&
844
operator^=(syntax_option_type& __x, syntax_option_type __y)
845
{
846
    __x = __x ^ __y;
847
    return __x;
848
}
849

    
850
// match_flag_type
851

    
852
enum match_flag_type
853
{
854
    match_default     = 0,
855
    match_not_bol     = 1 << 0,
856
    match_not_eol     = 1 << 1,
857
    match_not_bow     = 1 << 2,
858
    match_not_eow     = 1 << 3,
859
    match_any         = 1 << 4,
860
    match_not_null    = 1 << 5,
861
    match_continuous  = 1 << 6,
862
    match_prev_avail  = 1 << 7,
863
    format_default    = 0,
864
    format_sed        = 1 << 8,
865
    format_no_copy    = 1 << 9,
866
    format_first_only = 1 << 10,
867
    __no_update_pos   = 1 << 11
868
};
869

    
870
inline _LIBCPP_INLINE_VISIBILITY
871
_LIBCPP_CONSTEXPR
872
match_flag_type
873
operator~(match_flag_type __x)
874
{
875
    return match_flag_type(~int(__x) & 0x0FFF);
876
}
877

    
878
inline _LIBCPP_INLINE_VISIBILITY
879
_LIBCPP_CONSTEXPR
880
match_flag_type
881
operator&(match_flag_type __x, match_flag_type __y)
882
{
883
    return match_flag_type(int(__x) & int(__y));
884
}
885

    
886
inline _LIBCPP_INLINE_VISIBILITY
887
_LIBCPP_CONSTEXPR
888
match_flag_type
889
operator|(match_flag_type __x, match_flag_type __y)
890
{
891
    return match_flag_type(int(__x) | int(__y));
892
}
893

    
894
inline _LIBCPP_INLINE_VISIBILITY
895
_LIBCPP_CONSTEXPR
896
match_flag_type
897
operator^(match_flag_type __x, match_flag_type __y)
898
{
899
    return match_flag_type(int(__x) ^ int(__y));
900
}
901

    
902
inline _LIBCPP_INLINE_VISIBILITY
903
match_flag_type&
904
operator&=(match_flag_type& __x, match_flag_type __y)
905
{
906
    __x = __x & __y;
907
    return __x;
908
}
909

    
910
inline _LIBCPP_INLINE_VISIBILITY
911
match_flag_type&
912
operator|=(match_flag_type& __x, match_flag_type __y)
913
{
914
    __x = __x | __y;
915
    return __x;
916
}
917

    
918
inline _LIBCPP_INLINE_VISIBILITY
919
match_flag_type&
920
operator^=(match_flag_type& __x, match_flag_type __y)
921
{
922
    __x = __x ^ __y;
923
    return __x;
924
}
925

    
926
enum error_type
927
{
928
    error_collate = 1,
929
    error_ctype,
930
    error_escape,
931
    error_backref,
932
    error_brack,
933
    error_paren,
934
    error_brace,
935
    error_badbrace,
936
    error_range,
937
    error_space,
938
    error_badrepeat,
939
    error_complexity,
940
    error_stack,
941
    __re_err_grammar,
942
    __re_err_empty,
943
    __re_err_unknown
944
};
945

    
946
}  // regex_constants
947

    
948
class _LIBCPP_EXCEPTION_ABI regex_error
949
    : public runtime_error
950
{
951
    regex_constants::error_type __code_;
952
public:
953
    explicit regex_error(regex_constants::error_type __ecode);
954
    virtual ~regex_error() throw();
955
     _LIBCPP_INLINE_VISIBILITY
956
    regex_constants::error_type code() const {return __code_;}
957
};
958

    
959
template <regex_constants::error_type _Ev>
960
_LIBCPP_ALWAYS_INLINE
961
void __throw_regex_error()
962
{
963
#ifndef _LIBCPP_NO_EXCEPTIONS
964
    throw regex_error(_Ev);
965
#else
966
    assert(!"regex_error");
967
#endif
968
}
969

    
970
template <class _CharT>
971
struct _LIBCPP_TYPE_VIS_ONLY regex_traits
972
{
973
public:
974
    typedef _CharT                  char_type;
975
    typedef basic_string<char_type> string_type;
976
    typedef locale                  locale_type;
977
    typedef ctype_base::mask        char_class_type;
978

    
979
    static const char_class_type __regex_word = 0x80;
980
private:
981
    locale __loc_;
982
    const ctype<char_type>* __ct_;
983
    const collate<char_type>* __col_;
984

    
985
public:
986
    regex_traits();
987

    
988
    _LIBCPP_INLINE_VISIBILITY
989
    static size_t length(const char_type* __p)
990
        {return char_traits<char_type>::length(__p);}
991
    _LIBCPP_INLINE_VISIBILITY
992
    char_type translate(char_type __c) const {return __c;}
993
    char_type translate_nocase(char_type __c) const;
994
    template <class _ForwardIterator>
995
        string_type
996
        transform(_ForwardIterator __f, _ForwardIterator __l) const;
997
    template <class _ForwardIterator>
998
        _LIBCPP_INLINE_VISIBILITY
999
        string_type
1000
        transform_primary( _ForwardIterator __f, _ForwardIterator __l) const
1001
            {return __transform_primary(__f, __l, char_type());}
1002
    template <class _ForwardIterator>
1003
        _LIBCPP_INLINE_VISIBILITY
1004
        string_type
1005
        lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const
1006
            {return __lookup_collatename(__f, __l, char_type());}
1007
    template <class _ForwardIterator>
1008
        _LIBCPP_INLINE_VISIBILITY
1009
        char_class_type
1010
        lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
1011
                         bool __icase = false) const
1012
            {return __lookup_classname(__f, __l, __icase, char_type());}
1013
    bool isctype(char_type __c, char_class_type __m) const;
1014
    _LIBCPP_INLINE_VISIBILITY
1015
    int value(char_type __ch, int __radix) const
1016
        {return __regex_traits_value(__ch, __radix);}
1017
    locale_type imbue(locale_type __l);
1018
    _LIBCPP_INLINE_VISIBILITY
1019
    locale_type getloc()const {return __loc_;}
1020

    
1021
private:
1022
    void __init();
1023

    
1024
    template <class _ForwardIterator>
1025
        string_type
1026
        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
1027
    template <class _ForwardIterator>
1028
        string_type
1029
        __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
1030

    
1031
    template <class _ForwardIterator>
1032
        string_type
1033
        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
1034
    template <class _ForwardIterator>
1035
        string_type
1036
        __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;
1037

    
1038
    template <class _ForwardIterator>
1039
        char_class_type
1040
        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
1041
                           bool __icase, char) const;
1042
    template <class _ForwardIterator>
1043
        char_class_type
1044
        __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
1045
                           bool __icase, wchar_t) const;
1046

    
1047
    static int __regex_traits_value(unsigned char __ch, int __radix);
1048
    _LIBCPP_INLINE_VISIBILITY
1049
    int __regex_traits_value(char __ch, int __radix) const
1050
        {return __regex_traits_value(static_cast<unsigned char>(__ch), __radix);}
1051
    int __regex_traits_value(wchar_t __ch, int __radix) const;
1052
};
1053

    
1054
template <class _CharT>
1055
const typename regex_traits<_CharT>::char_class_type
1056
regex_traits<_CharT>::__regex_word;
1057

    
1058
template <class _CharT>
1059
regex_traits<_CharT>::regex_traits()
1060
{
1061
    __init();
1062
}
1063

    
1064
template <class _CharT>
1065
typename regex_traits<_CharT>::char_type
1066
regex_traits<_CharT>::translate_nocase(char_type __c) const
1067
{
1068
    return __ct_->tolower(__c);
1069
}
1070

    
1071
template <class _CharT>
1072
template <class _ForwardIterator>
1073
typename regex_traits<_CharT>::string_type
1074
regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const
1075
{
1076
    string_type __s(__f, __l);
1077
    return __col_->transform(__s.data(), __s.data() + __s.size());
1078
}
1079

    
1080
template <class _CharT>
1081
void
1082
regex_traits<_CharT>::__init()
1083
{
1084
    __ct_ = &use_facet<ctype<char_type> >(__loc_);
1085
    __col_ = &use_facet<collate<char_type> >(__loc_);
1086
}
1087

    
1088
template <class _CharT>
1089
typename regex_traits<_CharT>::locale_type
1090
regex_traits<_CharT>::imbue(locale_type __l)
1091
{
1092
    locale __r = __loc_;
1093
    __loc_ = __l;
1094
    __init();
1095
    return __r;
1096
}
1097

    
1098
// transform_primary is very FreeBSD-specific
1099

    
1100
template <class _CharT>
1101
template <class _ForwardIterator>
1102
typename regex_traits<_CharT>::string_type
1103
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
1104
                                          _ForwardIterator __l, char) const
1105
{
1106
    const string_type __s(__f, __l);
1107
    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
1108
    switch (__d.size())
1109
    {
1110
    case 1:
1111
        break;
1112
    case 12:
1113
        __d[11] = __d[3];
1114
        break;
1115
    default:
1116
        __d.clear();
1117
        break;
1118
    }
1119
    return __d;
1120
}
1121

    
1122
template <class _CharT>
1123
template <class _ForwardIterator>
1124
typename regex_traits<_CharT>::string_type
1125
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
1126
                                          _ForwardIterator __l, wchar_t) const
1127
{
1128
    const string_type __s(__f, __l);
1129
    string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
1130
    switch (__d.size())
1131
    {
1132
    case 1:
1133
        break;
1134
    case 3:
1135
        __d[2] = __d[0];
1136
        break;
1137
    default:
1138
        __d.clear();
1139
        break;
1140
    }
1141
    return __d;
1142
}
1143

    
1144
// lookup_collatename is very FreeBSD-specific
1145

    
1146
_LIBCPP_FUNC_VIS string __get_collation_name(const char* __s);
1147

    
1148
template <class _CharT>
1149
template <class _ForwardIterator>
1150
typename regex_traits<_CharT>::string_type
1151
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
1152
                                           _ForwardIterator __l, char) const
1153
{
1154
    string_type __s(__f, __l);
1155
    string_type __r;
1156
    if (!__s.empty())
1157
    {
1158
        __r = __get_collation_name(__s.c_str());
1159
        if (__r.empty() && __s.size() <= 2)
1160
        {
1161
            __r = __col_->transform(__s.data(), __s.data() + __s.size());
1162
            if (__r.size() == 1 || __r.size() == 12)
1163
                __r = __s;
1164
            else
1165
                __r.clear();
1166
        }
1167
    }
1168
    return __r;
1169
}
1170

    
1171
template <class _CharT>
1172
template <class _ForwardIterator>
1173
typename regex_traits<_CharT>::string_type
1174
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
1175
                                           _ForwardIterator __l, wchar_t) const
1176
{
1177
    string_type __s(__f, __l);
1178
    string __n;
1179
    __n.reserve(__s.size());
1180
    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
1181
                                                              __i != __e; ++__i)
1182
    {
1183
        if (static_cast<unsigned>(*__i) >= 127)
1184
            return string_type();
1185
        __n.push_back(char(*__i));
1186
    }
1187
    string_type __r;
1188
    if (!__s.empty())
1189
    {
1190
        __n = __get_collation_name(__n.c_str());
1191
        if (!__n.empty())
1192
            __r.assign(__n.begin(), __n.end());
1193
        else if (__s.size() <= 2)
1194
        {
1195
            __r = __col_->transform(__s.data(), __s.data() + __s.size());
1196
            if (__r.size() == 1 || __r.size() == 3)
1197
                __r = __s;
1198
            else
1199
                __r.clear();
1200
        }
1201
    }
1202
    return __r;
1203
}
1204

    
1205
// lookup_classname
1206

    
1207
regex_traits<char>::char_class_type _LIBCPP_FUNC_VIS
1208
__get_classname(const char* __s, bool __icase);
1209

    
1210
template <class _CharT>
1211
template <class _ForwardIterator>
1212
typename regex_traits<_CharT>::char_class_type
1213
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
1214
                                         _ForwardIterator __l,
1215
                                         bool __icase, char) const
1216
{
1217
    string_type __s(__f, __l);
1218
    __ct_->tolower(&__s[0], &__s[0] + __s.size());
1219
    return __get_classname(__s.c_str(), __icase);
1220
}
1221

    
1222
template <class _CharT>
1223
template <class _ForwardIterator>
1224
typename regex_traits<_CharT>::char_class_type
1225
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
1226
                                         _ForwardIterator __l,
1227
                                         bool __icase, wchar_t) const
1228
{
1229
    string_type __s(__f, __l);
1230
    __ct_->tolower(&__s[0], &__s[0] + __s.size());
1231
    string __n;
1232
    __n.reserve(__s.size());
1233
    for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
1234
                                                              __i != __e; ++__i)
1235
    {
1236
        if (static_cast<unsigned>(*__i) >= 127)
1237
            return char_class_type();
1238
        __n.push_back(char(*__i));
1239
    }
1240
    return __get_classname(__n.c_str(), __icase);
1241
}
1242

    
1243
template <class _CharT>
1244
bool
1245
regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const
1246
{
1247
    if (__ct_->is(__m, __c))
1248
        return true;
1249
    return (__c == '_' && (__m & __regex_word));
1250
}
1251

    
1252
template <class _CharT>
1253
int
1254
regex_traits<_CharT>::__regex_traits_value(unsigned char __ch, int __radix)
1255
{
1256
    if ((__ch & 0xF8u) == 0x30)  // '0' <= __ch && __ch <= '7'
1257
        return __ch - '0';
1258
    if (__radix != 8)
1259
    {
1260
        if ((__ch & 0xFEu) == 0x38)  // '8' <= __ch && __ch <= '9'
1261
            return __ch - '0';
1262
        if (__radix == 16)
1263
        {
1264
            __ch |= 0x20;  // tolower
1265
            if ('a' <= __ch && __ch <= 'f')
1266
                return __ch - ('a' - 10);
1267
        }
1268
    }
1269
    return -1;
1270
}
1271

    
1272
template <class _CharT>
1273
inline _LIBCPP_INLINE_VISIBILITY
1274
int
1275
regex_traits<_CharT>::__regex_traits_value(wchar_t __ch, int __radix) const
1276
{
1277
    return __regex_traits_value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
1278
}
1279

    
1280
template <class _CharT> class __node;
1281

    
1282
template <class _BidirectionalIterator> class _LIBCPP_TYPE_VIS_ONLY sub_match;
1283

    
1284
template <class _BidirectionalIterator,
1285
          class _Allocator = allocator<sub_match<_BidirectionalIterator> > >
1286
class _LIBCPP_TYPE_VIS_ONLY match_results;
1287

    
1288
template <class _CharT>
1289
struct __state
1290
{
1291
    enum
1292
    {
1293
        __end_state = -1000,
1294
        __consume_input,  // -999
1295
        __begin_marked_expr, // -998
1296
        __end_marked_expr,   // -997
1297
        __pop_state,           // -996
1298
        __accept_and_consume,  // -995
1299
        __accept_but_not_consume,  // -994
1300
        __reject,                  // -993
1301
        __split,
1302
        __repeat
1303
    };
1304

    
1305
    int __do_;
1306
    const _CharT* __first_;
1307
    const _CharT* __current_;
1308
    const _CharT* __last_;
1309
    vector<sub_match<const _CharT*> > __sub_matches_;
1310
    vector<pair<size_t, const _CharT*> > __loop_data_;
1311
    const __node<_CharT>* __node_;
1312
    regex_constants::match_flag_type __flags_;
1313
    bool __at_first_;
1314

    
1315
    _LIBCPP_INLINE_VISIBILITY
1316
    __state()
1317
        : __do_(0), __first_(nullptr), __current_(nullptr), __last_(nullptr),
1318
          __node_(nullptr), __flags_() {}
1319
};
1320

    
1321
// __node
1322

    
1323
template <class _CharT>
1324
class __node
1325
{
1326
    __node(const __node&);
1327
    __node& operator=(const __node&);
1328
public:
1329
    typedef _VSTD::__state<_CharT> __state;
1330

    
1331
    _LIBCPP_INLINE_VISIBILITY
1332
    __node() {}
1333
    _LIBCPP_INLINE_VISIBILITY
1334
    virtual ~__node() {}
1335

    
1336
    _LIBCPP_INLINE_VISIBILITY
1337
    virtual void __exec(__state&) const {};
1338
    _LIBCPP_INLINE_VISIBILITY
1339
    virtual void __exec_split(bool, __state&) const {};
1340
};
1341

    
1342
// __end_state
1343

    
1344
template <class _CharT>
1345
class __end_state
1346
    : public __node<_CharT>
1347
{
1348
public:
1349
    typedef _VSTD::__state<_CharT> __state;
1350

    
1351
    _LIBCPP_INLINE_VISIBILITY
1352
    __end_state() {}
1353

    
1354
    virtual void __exec(__state&) const;
1355
};
1356

    
1357
template <class _CharT>
1358
void
1359
__end_state<_CharT>::__exec(__state& __s) const
1360
{
1361
    __s.__do_ = __state::__end_state;
1362
}
1363

    
1364
// __has_one_state
1365

    
1366
template <class _CharT>
1367
class __has_one_state
1368
    : public __node<_CharT>
1369
{
1370
    __node<_CharT>* __first_;
1371

    
1372
public:
1373
    _LIBCPP_INLINE_VISIBILITY
1374
    explicit __has_one_state(__node<_CharT>* __s)
1375
        : __first_(__s) {}
1376

    
1377
    _LIBCPP_INLINE_VISIBILITY
1378
    __node<_CharT>*  first() const {return __first_;}
1379
    _LIBCPP_INLINE_VISIBILITY
1380
    __node<_CharT>*& first()       {return __first_;}
1381
};
1382

    
1383
// __owns_one_state
1384

    
1385
template <class _CharT>
1386
class __owns_one_state
1387
    : public __has_one_state<_CharT>
1388
{
1389
    typedef __has_one_state<_CharT> base;
1390

    
1391
public:
1392
    _LIBCPP_INLINE_VISIBILITY
1393
    explicit __owns_one_state(__node<_CharT>* __s)
1394
        : base(__s) {}
1395

    
1396
    virtual ~__owns_one_state();
1397
};
1398

    
1399
template <class _CharT>
1400
__owns_one_state<_CharT>::~__owns_one_state()
1401
{
1402
    delete this->first();
1403
}
1404

    
1405
// __empty_state
1406

    
1407
template <class _CharT>
1408
class __empty_state
1409
    : public __owns_one_state<_CharT>
1410
{
1411
    typedef __owns_one_state<_CharT> base;
1412

    
1413
public:
1414
    typedef _VSTD::__state<_CharT> __state;
1415

    
1416
    _LIBCPP_INLINE_VISIBILITY
1417
    explicit __empty_state(__node<_CharT>* __s)
1418
        : base(__s) {}
1419

    
1420
    virtual void __exec(__state&) const;
1421
};
1422

    
1423
template <class _CharT>
1424
void
1425
__empty_state<_CharT>::__exec(__state& __s) const
1426
{
1427
    __s.__do_ = __state::__accept_but_not_consume;
1428
    __s.__node_ = this->first();
1429
}
1430

    
1431
// __empty_non_own_state
1432

    
1433
template <class _CharT>
1434
class __empty_non_own_state
1435
    : public __has_one_state<_CharT>
1436
{
1437
    typedef __has_one_state<_CharT> base;
1438

    
1439
public:
1440
    typedef _VSTD::__state<_CharT> __state;
1441

    
1442
    _LIBCPP_INLINE_VISIBILITY
1443
    explicit __empty_non_own_state(__node<_CharT>* __s)
1444
        : base(__s) {}
1445

    
1446
    virtual void __exec(__state&) const;
1447
};
1448

    
1449
template <class _CharT>
1450
void
1451
__empty_non_own_state<_CharT>::__exec(__state& __s) const
1452
{
1453
    __s.__do_ = __state::__accept_but_not_consume;
1454
    __s.__node_ = this->first();
1455
}
1456

    
1457
// __repeat_one_loop
1458

    
1459
template <class _CharT>
1460
class __repeat_one_loop
1461
    : public __has_one_state<_CharT>
1462
{
1463
    typedef __has_one_state<_CharT> base;
1464

    
1465
public:
1466
    typedef _VSTD::__state<_CharT> __state;
1467

    
1468
    _LIBCPP_INLINE_VISIBILITY
1469
    explicit __repeat_one_loop(__node<_CharT>* __s)
1470
        : base(__s) {}
1471

    
1472
    virtual void __exec(__state&) const;
1473
};
1474

    
1475
template <class _CharT>
1476
void
1477
__repeat_one_loop<_CharT>::__exec(__state& __s) const
1478
{
1479
    __s.__do_ = __state::__repeat;
1480
    __s.__node_ = this->first();
1481
}
1482

    
1483
// __owns_two_states
1484

    
1485
template <class _CharT>
1486
class __owns_two_states
1487
    : public __owns_one_state<_CharT>
1488
{
1489
    typedef __owns_one_state<_CharT> base;
1490

    
1491
    base* __second_;
1492

    
1493
public:
1494
    _LIBCPP_INLINE_VISIBILITY
1495
    explicit __owns_two_states(__node<_CharT>* __s1, base* __s2)
1496
        : base(__s1), __second_(__s2) {}
1497

    
1498
    virtual ~__owns_two_states();
1499

    
1500
    _LIBCPP_INLINE_VISIBILITY
1501
    base*  second() const {return __second_;}
1502
    _LIBCPP_INLINE_VISIBILITY
1503
    base*& second()       {return __second_;}
1504
};
1505

    
1506
template <class _CharT>
1507
__owns_two_states<_CharT>::~__owns_two_states()
1508
{
1509
    delete __second_;
1510
}
1511

    
1512
// __loop
1513

    
1514
template <class _CharT>
1515
class __loop
1516
    : public __owns_two_states<_CharT>
1517
{
1518
    typedef __owns_two_states<_CharT> base;
1519

    
1520
    size_t __min_;
1521
    size_t __max_;
1522
    unsigned __loop_id_;
1523
    unsigned __mexp_begin_;
1524
    unsigned __mexp_end_;
1525
    bool __greedy_;
1526

    
1527
public:
1528
    typedef _VSTD::__state<_CharT> __state;
1529

    
1530
    _LIBCPP_INLINE_VISIBILITY
1531
    explicit __loop(unsigned __loop_id,
1532
                          __node<_CharT>* __s1, __owns_one_state<_CharT>* __s2,
1533
                          unsigned __mexp_begin, unsigned __mexp_end,
1534
                          bool __greedy = true,
1535
                          size_t __min = 0,
1536
                          size_t __max = numeric_limits<size_t>::max())
1537
        : base(__s1, __s2), __min_(__min), __max_(__max), __loop_id_(__loop_id),
1538
          __mexp_begin_(__mexp_begin), __mexp_end_(__mexp_end),
1539
          __greedy_(__greedy) {}
1540

    
1541
    virtual void __exec(__state& __s) const;
1542
    virtual void __exec_split(bool __second, __state& __s) const;
1543

    
1544
private:
1545
    _LIBCPP_INLINE_VISIBILITY
1546
    void __init_repeat(__state& __s) const
1547
    {
1548
        __s.__loop_data_[__loop_id_].second = __s.__current_;
1549
        for (size_t __i = __mexp_begin_-1; __i != __mexp_end_-1; ++__i)
1550
        {
1551
            __s.__sub_matches_[__i].first = __s.__last_;
1552
            __s.__sub_matches_[__i].second = __s.__last_;
1553
            __s.__sub_matches_[__i].matched = false;
1554
        }
1555
    }
1556
};
1557

    
1558
template <class _CharT>
1559
void
1560
__loop<_CharT>::__exec(__state& __s) const
1561
{
1562
    if (__s.__do_ == __state::__repeat)
1563
    {
1564
        bool __do_repeat = ++__s.__loop_data_[__loop_id_].first < __max_;
1565
        bool __do_alt = __s.__loop_data_[__loop_id_].first >= __min_;
1566
        if (__do_repeat && __do_alt &&
1567
                               __s.__loop_data_[__loop_id_].second == __s.__current_)
1568
            __do_repeat = false;
1569
        if (__do_repeat && __do_alt)
1570
            __s.__do_ = __state::__split;
1571
        else if (__do_repeat)
1572
        {
1573
            __s.__do_ = __state::__accept_but_not_consume;
1574
            __s.__node_ = this->first();
1575
            __init_repeat(__s);
1576
        }
1577
        else
1578
        {
1579
            __s.__do_ = __state::__accept_but_not_consume;
1580
            __s.__node_ = this->second();
1581
        }
1582
    }
1583
    else
1584
    {
1585
        __s.__loop_data_[__loop_id_].first = 0;
1586
        bool __do_repeat = 0 < __max_;
1587
        bool __do_alt = 0 >= __min_;
1588
        if (__do_repeat && __do_alt)
1589
            __s.__do_ = __state::__split;
1590
        else if (__do_repeat)
1591
        {
1592
            __s.__do_ = __state::__accept_but_not_consume;
1593
            __s.__node_ = this->first();
1594
            __init_repeat(__s);
1595
        }
1596
        else
1597
        {
1598
            __s.__do_ = __state::__accept_but_not_consume;
1599
            __s.__node_ = this->second();
1600
        }
1601
    }
1602
}
1603

    
1604
template <class _CharT>
1605
void
1606
__loop<_CharT>::__exec_split(bool __second, __state& __s) const
1607
{
1608
    __s.__do_ = __state::__accept_but_not_consume;
1609
    if (__greedy_ != __second)
1610
    {
1611
        __s.__node_ = this->first();
1612
        __init_repeat(__s);
1613
    }
1614
    else
1615
        __s.__node_ = this->second();
1616
}
1617

    
1618
// __alternate
1619

    
1620
template <class _CharT>
1621
class __alternate
1622
    : public __owns_two_states<_CharT>
1623
{
1624
    typedef __owns_two_states<_CharT> base;
1625

    
1626
public:
1627
    typedef _VSTD::__state<_CharT> __state;
1628

    
1629
    _LIBCPP_INLINE_VISIBILITY
1630
    explicit __alternate(__owns_one_state<_CharT>* __s1,
1631
                         __owns_one_state<_CharT>* __s2)
1632
        : base(__s1, __s2) {}
1633

    
1634
    virtual void __exec(__state& __s) const;
1635
    virtual void __exec_split(bool __second, __state& __s) const;
1636
};
1637

    
1638
template <class _CharT>
1639
void
1640
__alternate<_CharT>::__exec(__state& __s) const
1641
{
1642
    __s.__do_ = __state::__split;
1643
}
1644

    
1645
template <class _CharT>
1646
void
1647
__alternate<_CharT>::__exec_split(bool __second, __state& __s) const
1648
{
1649
    __s.__do_ = __state::__accept_but_not_consume;
1650
    if (__second)
1651
        __s.__node_ = this->second();
1652
    else
1653
        __s.__node_ = this->first();
1654
}
1655

    
1656
// __begin_marked_subexpression
1657

    
1658
template <class _CharT>
1659
class __begin_marked_subexpression
1660
    : public __owns_one_state<_CharT>
1661
{
1662
    typedef __owns_one_state<_CharT> base;
1663

    
1664
    unsigned __mexp_;
1665
public:
1666
    typedef _VSTD::__state<_CharT> __state;
1667

    
1668
    _LIBCPP_INLINE_VISIBILITY
1669
    explicit __begin_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
1670
        : base(__s), __mexp_(__mexp) {}
1671

    
1672
    virtual void __exec(__state&) const;
1673
};
1674

    
1675
template <class _CharT>
1676
void
1677
__begin_marked_subexpression<_CharT>::__exec(__state& __s) const
1678
{
1679
    __s.__do_ = __state::__accept_but_not_consume;
1680
    __s.__sub_matches_[__mexp_-1].first = __s.__current_;
1681
    __s.__node_ = this->first();
1682
}
1683

    
1684
// __end_marked_subexpression
1685

    
1686
template <class _CharT>
1687
class __end_marked_subexpression
1688
    : public __owns_one_state<_CharT>
1689
{
1690
    typedef __owns_one_state<_CharT> base;
1691

    
1692
    unsigned __mexp_;
1693
public:
1694
    typedef _VSTD::__state<_CharT> __state;
1695

    
1696
    _LIBCPP_INLINE_VISIBILITY
1697
    explicit __end_marked_subexpression(unsigned __mexp, __node<_CharT>* __s)
1698
        : base(__s), __mexp_(__mexp) {}
1699

    
1700
    virtual void __exec(__state&) const;
1701
};
1702

    
1703
template <class _CharT>
1704
void
1705
__end_marked_subexpression<_CharT>::__exec(__state& __s) const
1706
{
1707
    __s.__do_ = __state::__accept_but_not_consume;
1708
    __s.__sub_matches_[__mexp_-1].second = __s.__current_;
1709
    __s.__sub_matches_[__mexp_-1].matched = true;
1710
    __s.__node_ = this->first();
1711
}
1712

    
1713
// __back_ref
1714

    
1715
template <class _CharT>
1716
class __back_ref
1717
    : public __owns_one_state<_CharT>
1718
{
1719
    typedef __owns_one_state<_CharT> base;
1720

    
1721
    unsigned __mexp_;
1722
public:
1723
    typedef _VSTD::__state<_CharT> __state;
1724

    
1725
    _LIBCPP_INLINE_VISIBILITY
1726
    explicit __back_ref(unsigned __mexp, __node<_CharT>* __s)
1727
        : base(__s), __mexp_(__mexp) {}
1728

    
1729
    virtual void __exec(__state&) const;
1730
};
1731

    
1732
template <class _CharT>
1733
void
1734
__back_ref<_CharT>::__exec(__state& __s) const
1735
{
1736
    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
1737
    if (__sm.matched)
1738
    {
1739
        ptrdiff_t __len = __sm.second - __sm.first;
1740
        if (__s.__last_ - __s.__current_ >= __len &&
1741
            _VSTD::equal(__sm.first, __sm.second, __s.__current_))
1742
        {
1743
            __s.__do_ = __state::__accept_but_not_consume;
1744
            __s.__current_ += __len;
1745
            __s.__node_ = this->first();
1746
        }
1747
        else
1748
        {
1749
            __s.__do_ = __state::__reject;
1750
            __s.__node_ = nullptr;
1751
        }
1752
    }
1753
    else
1754
    {
1755
        __s.__do_ = __state::__reject;
1756
        __s.__node_ = nullptr;
1757
    }
1758
}
1759

    
1760
// __back_ref_icase
1761

    
1762
template <class _CharT, class _Traits>
1763
class __back_ref_icase
1764
    : public __owns_one_state<_CharT>
1765
{
1766
    typedef __owns_one_state<_CharT> base;
1767

    
1768
    _Traits __traits_;
1769
    unsigned __mexp_;
1770
public:
1771
    typedef _VSTD::__state<_CharT> __state;
1772

    
1773
    _LIBCPP_INLINE_VISIBILITY
1774
    explicit __back_ref_icase(const _Traits& __traits, unsigned __mexp,
1775
                              __node<_CharT>* __s)
1776
        : base(__s), __traits_(__traits), __mexp_(__mexp) {}
1777

    
1778
    virtual void __exec(__state&) const;
1779
};
1780

    
1781
template <class _CharT, class _Traits>
1782
void
1783
__back_ref_icase<_CharT, _Traits>::__exec(__state& __s) const
1784
{
1785
    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
1786
    if (__sm.matched)
1787
    {
1788
        ptrdiff_t __len = __sm.second - __sm.first;
1789
        if (__s.__last_ - __s.__current_ >= __len)
1790
        {
1791
            for (ptrdiff_t __i = 0; __i < __len; ++__i)
1792
            {
1793
                if (__traits_.translate_nocase(__sm.first[__i]) !=
1794
                                __traits_.translate_nocase(__s.__current_[__i]))
1795
                    goto __not_equal;
1796
            }
1797
            __s.__do_ = __state::__accept_but_not_consume;
1798
            __s.__current_ += __len;
1799
            __s.__node_ = this->first();
1800
        }
1801
        else
1802
        {
1803
            __s.__do_ = __state::__reject;
1804
            __s.__node_ = nullptr;
1805
        }
1806
    }
1807
    else
1808
    {
1809
__not_equal:
1810
        __s.__do_ = __state::__reject;
1811
        __s.__node_ = nullptr;
1812
    }
1813
}
1814

    
1815
// __back_ref_collate
1816

    
1817
template <class _CharT, class _Traits>
1818
class __back_ref_collate
1819
    : public __owns_one_state<_CharT>
1820
{
1821
    typedef __owns_one_state<_CharT> base;
1822

    
1823
    _Traits __traits_;
1824
    unsigned __mexp_;
1825
public:
1826
    typedef _VSTD::__state<_CharT> __state;
1827

    
1828
    _LIBCPP_INLINE_VISIBILITY
1829
    explicit __back_ref_collate(const _Traits& __traits, unsigned __mexp,
1830
                              __node<_CharT>* __s)
1831
        : base(__s), __traits_(__traits), __mexp_(__mexp) {}
1832

    
1833
    virtual void __exec(__state&) const;
1834
};
1835

    
1836
template <class _CharT, class _Traits>
1837
void
1838
__back_ref_collate<_CharT, _Traits>::__exec(__state& __s) const
1839
{
1840
    sub_match<const _CharT*>& __sm = __s.__sub_matches_[__mexp_-1];
1841
    if (__sm.matched)
1842
    {
1843
        ptrdiff_t __len = __sm.second - __sm.first;
1844
        if (__s.__last_ - __s.__current_ >= __len)
1845
        {
1846
            for (ptrdiff_t __i = 0; __i < __len; ++__i)
1847
            {
1848
                if (__traits_.translate(__sm.first[__i]) !=
1849
                                       __traits_.translate(__s.__current_[__i]))
1850
                    goto __not_equal;
1851
            }
1852
            __s.__do_ = __state::__accept_but_not_consume;
1853
            __s.__current_ += __len;
1854
            __s.__node_ = this->first();
1855
        }
1856
        else
1857
        {
1858
            __s.__do_ = __state::__reject;
1859
            __s.__node_ = nullptr;
1860
        }
1861
    }
1862
    else
1863
    {
1864
__not_equal:
1865
        __s.__do_ = __state::__reject;
1866
        __s.__node_ = nullptr;
1867
    }
1868
}
1869

    
1870
// __word_boundary
1871

    
1872
template <class _CharT, class _Traits>
1873
class __word_boundary
1874
    : public __owns_one_state<_CharT>
1875
{
1876
    typedef __owns_one_state<_CharT> base;
1877

    
1878
    _Traits __traits_;
1879
    bool __invert_;
1880
public:
1881
    typedef _VSTD::__state<_CharT> __state;
1882

    
1883
    _LIBCPP_INLINE_VISIBILITY
1884
    explicit __word_boundary(const _Traits& __traits, bool __invert,
1885
                             __node<_CharT>* __s)
1886
        : base(__s), __traits_(__traits), __invert_(__invert) {}
1887

    
1888
    virtual void __exec(__state&) const;
1889
};
1890

    
1891
template <class _CharT, class _Traits>
1892
void
1893
__word_boundary<_CharT, _Traits>::__exec(__state& __s) const
1894
{
1895
    bool __is_word_b = false;
1896
    if (__s.__first_ != __s.__last_)
1897
    {
1898
        if (__s.__current_ == __s.__last_)
1899
        {
1900
            if (!(__s.__flags_ & regex_constants::match_not_eow))
1901
            {
1902
                _CharT __c = __s.__current_[-1];
1903
                __is_word_b = __c == '_' ||
1904
                              __traits_.isctype(__c, ctype_base::alnum);
1905
            }
1906
        }
1907
        else if (__s.__current_ == __s.__first_ &&
1908
                !(__s.__flags_ & regex_constants::match_prev_avail))
1909
        {
1910
            if (!(__s.__flags_ & regex_constants::match_not_bow))
1911
            {
1912
                _CharT __c = *__s.__current_;
1913
                __is_word_b = __c == '_' ||
1914
                              __traits_.isctype(__c, ctype_base::alnum);
1915
            }
1916
        }
1917
        else
1918
        {
1919
            _CharT __c1 = __s.__current_[-1];
1920
            _CharT __c2 = *__s.__current_;
1921
            bool __is_c1_b = __c1 == '_' ||
1922
                             __traits_.isctype(__c1, ctype_base::alnum);
1923
            bool __is_c2_b = __c2 == '_' ||
1924
                             __traits_.isctype(__c2, ctype_base::alnum);
1925
            __is_word_b = __is_c1_b != __is_c2_b;
1926
        }
1927
    }
1928
    if (__is_word_b != __invert_)
1929
    {
1930
        __s.__do_ = __state::__accept_but_not_consume;
1931
        __s.__node_ = this->first();
1932
    }
1933
    else
1934
    {
1935
        __s.__do_ = __state::__reject;
1936
        __s.__node_ = nullptr;
1937
    }
1938
}
1939

    
1940
// __l_anchor
1941

    
1942
template <class _CharT>
1943
class __l_anchor
1944
    : public __owns_one_state<_CharT>
1945
{
1946
    typedef __owns_one_state<_CharT> base;
1947

    
1948
public:
1949
    typedef _VSTD::__state<_CharT> __state;
1950

    
1951
    _LIBCPP_INLINE_VISIBILITY
1952
    __l_anchor(__node<_CharT>* __s)
1953
        : base(__s) {}
1954

    
1955
    virtual void __exec(__state&) const;
1956
};
1957

    
1958
template <class _CharT>
1959
void
1960
__l_anchor<_CharT>::__exec(__state& __s) const
1961
{
1962
    if (__s.__at_first_ && __s.__current_ == __s.__first_ &&
1963
        !(__s.__flags_ & regex_constants::match_not_bol))
1964
    {
1965
        __s.__do_ = __state::__accept_but_not_consume;
1966
        __s.__node_ = this->first();
1967
    }
1968
    else
1969
    {
1970
        __s.__do_ = __state::__reject;
1971
        __s.__node_ = nullptr;
1972
    }
1973
}
1974

    
1975
// __r_anchor
1976

    
1977
template <class _CharT>
1978
class __r_anchor
1979
    : public __owns_one_state<_CharT>
1980
{
1981
    typedef __owns_one_state<_CharT> base;
1982

    
1983
public:
1984
    typedef _VSTD::__state<_CharT> __state;
1985

    
1986
    _LIBCPP_INLINE_VISIBILITY
1987
    __r_anchor(__node<_CharT>* __s)
1988
        : base(__s) {}
1989

    
1990
    virtual void __exec(__state&) const;
1991
};
1992

    
1993
template <class _CharT>
1994
void
1995
__r_anchor<_CharT>::__exec(__state& __s) const
1996
{
1997
    if (__s.__current_ == __s.__last_ &&
1998
        !(__s.__flags_ & regex_constants::match_not_eol))
1999
    {
2000
        __s.__do_ = __state::__accept_but_not_consume;
2001
        __s.__node_ = this->first();
2002
    }
2003
    else
2004
    {
2005
        __s.__do_ = __state::__reject;
2006
        __s.__node_ = nullptr;
2007
    }
2008
}
2009

    
2010
// __match_any
2011

    
2012
template <class _CharT>
2013
class __match_any
2014
    : public __owns_one_state<_CharT>
2015
{
2016
    typedef __owns_one_state<_CharT> base;
2017

    
2018
public:
2019
    typedef _VSTD::__state<_CharT> __state;
2020

    
2021
    _LIBCPP_INLINE_VISIBILITY
2022
    __match_any(__node<_CharT>* __s)
2023
        : base(__s) {}
2024

    
2025
    virtual void __exec(__state&) const;
2026
};
2027

    
2028
template <class _CharT>
2029
void
2030
__match_any<_CharT>::__exec(__state& __s) const
2031
{
2032
    if (__s.__current_ != __s.__last_ && *__s.__current_ != 0)
2033
    {
2034
        __s.__do_ = __state::__accept_and_consume;
2035
        ++__s.__current_;
2036
        __s.__node_ = this->first();
2037
    }
2038
    else
2039
    {
2040
        __s.__do_ = __state::__reject;
2041
        __s.__node_ = nullptr;
2042
    }
2043
}
2044

    
2045
// __match_any_but_newline
2046

    
2047
template <class _CharT>
2048
class __match_any_but_newline
2049
    : public __owns_one_state<_CharT>
2050
{
2051
    typedef __owns_one_state<_CharT> base;
2052

    
2053
public:
2054
    typedef _VSTD::__state<_CharT> __state;
2055

    
2056
    _LIBCPP_INLINE_VISIBILITY
2057
    __match_any_but_newline(__node<_CharT>* __s)
2058
        : base(__s) {}
2059

    
2060
    virtual void __exec(__state&) const;
2061
};
2062

    
2063
template <> _LIBCPP_FUNC_VIS void __match_any_but_newline<char>::__exec(__state&) const;
2064
template <> _LIBCPP_FUNC_VIS void __match_any_but_newline<wchar_t>::__exec(__state&) const;
2065

    
2066
// __match_char
2067

    
2068
template <class _CharT>
2069
class __match_char
2070
    : public __owns_one_state<_CharT>
2071
{
2072
    typedef __owns_one_state<_CharT> base;
2073

    
2074
    _CharT __c_;
2075

    
2076
    __match_char(const __match_char&);
2077
    __match_char& operator=(const __match_char&);
2078
public:
2079
    typedef _VSTD::__state<_CharT> __state;
2080

    
2081
    _LIBCPP_INLINE_VISIBILITY
2082
    __match_char(_CharT __c, __node<_CharT>* __s)
2083
        : base(__s), __c_(__c) {}
2084

    
2085
    virtual void __exec(__state&) const;
2086
};
2087

    
2088
template <class _CharT>
2089
void
2090
__match_char<_CharT>::__exec(__state& __s) const
2091
{
2092
    if (__s.__current_ != __s.__last_ && *__s.__current_ == __c_)
2093
    {
2094
        __s.__do_ = __state::__accept_and_consume;
2095
        ++__s.__current_;
2096
        __s.__node_ = this->first();
2097
    }
2098
    else
2099
    {
2100
        __s.__do_ = __state::__reject;
2101
        __s.__node_ = nullptr;
2102
    }
2103
}
2104

    
2105
// __match_char_icase
2106

    
2107
template <class _CharT, class _Traits>
2108
class __match_char_icase
2109
    : public __owns_one_state<_CharT>
2110
{
2111
    typedef __owns_one_state<_CharT> base;
2112

    
2113
    _Traits __traits_;
2114
    _CharT __c_;
2115

    
2116
    __match_char_icase(const __match_char_icase&);
2117
    __match_char_icase& operator=(const __match_char_icase&);
2118
public:
2119
    typedef _VSTD::__state<_CharT> __state;
2120

    
2121
    _LIBCPP_INLINE_VISIBILITY
2122
    __match_char_icase(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
2123
        : base(__s), __traits_(__traits), __c_(__traits.translate_nocase(__c)) {}
2124

    
2125
    virtual void __exec(__state&) const;
2126
};
2127

    
2128
template <class _CharT, class _Traits>
2129
void
2130
__match_char_icase<_CharT, _Traits>::__exec(__state& __s) const
2131
{
2132
    if (__s.__current_ != __s.__last_ &&
2133
        __traits_.translate_nocase(*__s.__current_) == __c_)
2134
    {
2135
        __s.__do_ = __state::__accept_and_consume;
2136
        ++__s.__current_;
2137
        __s.__node_ = this->first();
2138
    }
2139
    else
2140
    {
2141
        __s.__do_ = __state::__reject;
2142
        __s.__node_ = nullptr;
2143
    }
2144
}
2145

    
2146
// __match_char_collate
2147

    
2148
template <class _CharT, class _Traits>
2149
class __match_char_collate
2150
    : public __owns_one_state<_CharT>
2151
{
2152
    typedef __owns_one_state<_CharT> base;
2153

    
2154
    _Traits __traits_;
2155
    _CharT __c_;
2156

    
2157
    __match_char_collate(const __match_char_collate&);
2158
    __match_char_collate& operator=(const __match_char_collate&);
2159
public:
2160
    typedef _VSTD::__state<_CharT> __state;
2161

    
2162
    _LIBCPP_INLINE_VISIBILITY
2163
    __match_char_collate(const _Traits& __traits, _CharT __c, __node<_CharT>* __s)
2164
        : base(__s), __traits_(__traits), __c_(__traits.translate(__c)) {}
2165

    
2166
    virtual void __exec(__state&) const;
2167
};
2168

    
2169
template <class _CharT, class _Traits>
2170
void
2171
__match_char_collate<_CharT, _Traits>::__exec(__state& __s) const
2172
{
2173
    if (__s.__current_ != __s.__last_ &&
2174
        __traits_.translate(*__s.__current_) == __c_)
2175
    {
2176
        __s.__do_ = __state::__accept_and_consume;
2177
        ++__s.__current_;
2178
        __s.__node_ = this->first();
2179
    }
2180
    else
2181
    {
2182
        __s.__do_ = __state::__reject;
2183
        __s.__node_ = nullptr;
2184
    }
2185
}
2186

    
2187
// __bracket_expression
2188

    
2189
template <class _CharT, class _Traits>
2190
class __bracket_expression
2191
    : public __owns_one_state<_CharT>
2192
{
2193
    typedef __owns_one_state<_CharT> base;
2194
    typedef typename _Traits::string_type string_type;
2195

    
2196
    _Traits __traits_;
2197
    vector<_CharT> __chars_;
2198
    vector<_CharT> __neg_chars_;
2199
    vector<pair<string_type, string_type> > __ranges_;
2200
    vector<pair<_CharT, _CharT> > __digraphs_;
2201
    vector<string_type> __equivalences_;
2202
    typename regex_traits<_CharT>::char_class_type __mask_;
2203
    typename regex_traits<_CharT>::char_class_type __neg_mask_;
2204
    bool __negate_;
2205
    bool __icase_;
2206
    bool __collate_;
2207
    bool __might_have_digraph_;
2208

    
2209
    __bracket_expression(const __bracket_expression&);
2210
    __bracket_expression& operator=(const __bracket_expression&);
2211
public:
2212
    typedef _VSTD::__state<_CharT> __state;
2213

    
2214
    _LIBCPP_INLINE_VISIBILITY
2215
    __bracket_expression(const _Traits& __traits, __node<_CharT>* __s,
2216
                                 bool __negate, bool __icase, bool __collate)
2217
        : base(__s), __traits_(__traits), __mask_(), __neg_mask_(),
2218
          __negate_(__negate), __icase_(__icase), __collate_(__collate),
2219
          __might_have_digraph_(__traits_.getloc().name() != "C") {}
2220

    
2221
    virtual void __exec(__state&) const;
2222

    
2223
    _LIBCPP_INLINE_VISIBILITY
2224
    bool __negated() const {return __negate_;}
2225

    
2226
    _LIBCPP_INLINE_VISIBILITY
2227
    void __add_char(_CharT __c)
2228
        {
2229
            if (__icase_)
2230
                __chars_.push_back(__traits_.translate_nocase(__c));
2231
            else if (__collate_)
2232
                __chars_.push_back(__traits_.translate(__c));
2233
            else
2234
                __chars_.push_back(__c);
2235
        }
2236
    _LIBCPP_INLINE_VISIBILITY
2237
    void __add_neg_char(_CharT __c)
2238
        {
2239
            if (__icase_)
2240
                __neg_chars_.push_back(__traits_.translate_nocase(__c));
2241
            else if (__collate_)
2242
                __neg_chars_.push_back(__traits_.translate(__c));
2243
            else
2244
                __neg_chars_.push_back(__c);
2245
        }
2246
    _LIBCPP_INLINE_VISIBILITY
2247
    void __add_range(string_type __b, string_type __e)
2248
        {
2249
            if (__collate_)
2250
            {
2251
                if (__icase_)
2252
                {
2253
                    for (size_t __i = 0; __i < __b.size(); ++__i)
2254
                        __b[__i] = __traits_.translate_nocase(__b[__i]);
2255
                    for (size_t __i = 0; __i < __e.size(); ++__i)
2256
                        __e[__i] = __traits_.translate_nocase(__e[__i]);
2257
                }
2258
                else
2259
                {
2260
                    for (size_t __i = 0; __i < __b.size(); ++__i)
2261
                        __b[__i] = __traits_.translate(__b[__i]);
2262
                    for (size_t __i = 0; __i < __e.size(); ++__i)
2263
                        __e[__i] = __traits_.translate(__e[__i]);
2264
                }
2265
                __ranges_.push_back(make_pair(
2266
                                  __traits_.transform(__b.begin(), __b.end()),
2267
                                  __traits_.transform(__e.begin(), __e.end())));
2268
            }
2269
            else
2270
            {
2271
                if (__b.size() != 1 || __e.size() != 1)
2272
                    __throw_regex_error<regex_constants::error_collate>();
2273
                if (__icase_)
2274
                {
2275
                    __b[0] = __traits_.translate_nocase(__b[0]);
2276
                    __e[0] = __traits_.translate_nocase(__e[0]);
2277
                }
2278
                __ranges_.push_back(make_pair(_VSTD::move(__b), _VSTD::move(__e)));
2279
            }
2280
        }
2281
    _LIBCPP_INLINE_VISIBILITY
2282
    void __add_digraph(_CharT __c1, _CharT __c2)
2283
        {
2284
            if (__icase_)
2285
                __digraphs_.push_back(make_pair(__traits_.translate_nocase(__c1),
2286
                                                __traits_.translate_nocase(__c2)));
2287
            else if (__collate_)
2288
                __digraphs_.push_back(make_pair(__traits_.translate(__c1),
2289
                                                __traits_.translate(__c2)));
2290
            else
2291
                __digraphs_.push_back(make_pair(__c1, __c2));
2292
        }
2293
    _LIBCPP_INLINE_VISIBILITY
2294
    void __add_equivalence(const string_type& __s)
2295
        {__equivalences_.push_back(__s);}
2296
    _LIBCPP_INLINE_VISIBILITY
2297
    void __add_class(typename regex_traits<_CharT>::char_class_type __mask)
2298
        {__mask_ |= __mask;}
2299
    _LIBCPP_INLINE_VISIBILITY
2300
    void __add_neg_class(typename regex_traits<_CharT>::char_class_type __mask)
2301
        {__neg_mask_ |= __mask;}
2302
};
2303

    
2304
template <class _CharT, class _Traits>
2305
void
2306
__bracket_expression<_CharT, _Traits>::__exec(__state& __s) const
2307
{
2308
    bool __found = false;
2309
    unsigned __consumed = 0;
2310
    if (__s.__current_ != __s.__last_)
2311
    {
2312
        ++__consumed;
2313
        if (__might_have_digraph_)
2314
        {
2315
            const _CharT* __next = _VSTD::next(__s.__current_);
2316
            if (__next != __s.__last_)
2317
            {
2318
                pair<_CharT, _CharT> __ch2(*__s.__current_, *__next);
2319
                if (__icase_)
2320
                {
2321
                    __ch2.first = __traits_.translate_nocase(__ch2.first);
2322
                    __ch2.second = __traits_.translate_nocase(__ch2.second);
2323
                }
2324
                else if (__collate_)
2325
                {
2326
                    __ch2.first = __traits_.translate(__ch2.first);
2327
                    __ch2.second = __traits_.translate(__ch2.second);
2328
                }
2329
                if (!__traits_.lookup_collatename(&__ch2.first, &__ch2.first+2).empty())
2330
                {
2331
                    // __ch2 is a digraph in this locale
2332
                    ++__consumed;
2333
                    for (size_t __i = 0; __i < __digraphs_.size(); ++__i)
2334
                    {
2335
                        if (__ch2 == __digraphs_[__i])
2336
                        {
2337
                            __found = true;
2338
                            goto __exit;
2339
                        }
2340
                    }
2341
                    if (__collate_ && !__ranges_.empty())
2342
                    {
2343
                        string_type __s2 = __traits_.transform(&__ch2.first,
2344
                                                               &__ch2.first + 2);
2345
                        for (size_t __i = 0; __i < __ranges_.size(); ++__i)
2346
                        {
2347
                            if (__ranges_[__i].first <= __s2 &&
2348
                                __s2 <= __ranges_[__i].second)
2349
                            {
2350
                                __found = true;
2351
                                goto __exit;
2352
                            }
2353
                        }
2354
                    }
2355
                    if (!__equivalences_.empty())
2356
                    {
2357
                        string_type __s2 = __traits_.transform_primary(&__ch2.first,
2358
                                                                       &__ch2.first + 2);
2359
                        for (size_t __i = 0; __i < __equivalences_.size(); ++__i)
2360
                        {
2361
                            if (__s2 == __equivalences_[__i])
2362
                            {
2363
                                __found = true;
2364
                                goto __exit;
2365
                            }
2366
                        }
2367
                    }
2368
                    if (__traits_.isctype(__ch2.first, __mask_) &&
2369
                        __traits_.isctype(__ch2.second, __mask_))
2370
                    {
2371
                        __found = true;
2372
                        goto __exit;
2373
                    }
2374
                    if (!__traits_.isctype(__ch2.first, __neg_mask_) &&
2375
                        !__traits_.isctype(__ch2.second, __neg_mask_))
2376
                    {
2377
                        __found = true;
2378
                        goto __exit;
2379
                    }
2380
                    goto __exit;
2381
                }
2382
            }
2383
        }
2384
        // test *__s.__current_ as not a digraph
2385
        _CharT __ch = *__s.__current_;
2386
        if (__icase_)
2387
            __ch = __traits_.translate_nocase(__ch);
2388
        else if (__collate_)
2389
            __ch = __traits_.translate(__ch);
2390
        for (size_t __i = 0; __i < __chars_.size(); ++__i)
2391
        {
2392
            if (__ch == __chars_[__i])
2393
            {
2394
                __found = true;
2395
                goto __exit;
2396
            }
2397
        }
2398
        if (!__neg_chars_.empty())
2399
        {
2400
            for (size_t __i = 0; __i < __neg_chars_.size(); ++__i)
2401
            {
2402
                if (__ch == __neg_chars_[__i])
2403
                    goto __is_neg_char;
2404
            }
2405
            __found = true;
2406
            goto __exit;
2407
        }
2408
__is_neg_char:
2409
        if (!__ranges_.empty())
2410
        {
2411
            string_type __s2 = __collate_ ?
2412
                                   __traits_.transform(&__ch, &__ch + 1) :
2413
                                   string_type(1, __ch);
2414
            for (size_t __i = 0; __i < __ranges_.size(); ++__i)
2415
            {
2416
                if (__ranges_[__i].first <= __s2 && __s2 <= __ranges_[__i].second)
2417
                {
2418
                    __found = true;
2419
                    goto __exit;
2420
                }
2421
            }
2422
        }
2423
        if (!__equivalences_.empty())
2424
        {
2425
            string_type __s2 = __traits_.transform_primary(&__ch, &__ch + 1);
2426
            for (size_t __i = 0; __i < __equivalences_.size(); ++__i)
2427
            {
2428
                if (__s2 == __equivalences_[__i])
2429
                {
2430
                    __found = true;
2431
                    goto __exit;
2432
                }
2433
            }
2434
        }
2435
        if (__traits_.isctype(__ch, __mask_))
2436
        {
2437
            __found = true;
2438
            goto __exit;
2439
        }
2440
        if (__neg_mask_ && !__traits_.isctype(__ch, __neg_mask_))
2441
        {
2442
            __found = true;
2443
            goto __exit;
2444
        }
2445
    }
2446
    else
2447
        __found = __negate_;  // force reject
2448
__exit:
2449
    if (__found != __negate_)
2450
    {
2451
        __s.__do_ = __state::__accept_and_consume;
2452
        __s.__current_ += __consumed;
2453
        __s.__node_ = this->first();
2454
    }
2455
    else
2456
    {
2457
        __s.__do_ = __state::__reject;
2458
        __s.__node_ = nullptr;
2459
    }
2460
}
2461

    
2462
template <class _CharT, class _Traits> class __lookahead;
2463

    
2464
template <class _CharT, class _Traits = regex_traits<_CharT> >
2465
class _LIBCPP_TYPE_VIS_ONLY basic_regex
2466
{
2467
public:
2468
    // types:
2469
    typedef _CharT                              value_type;
2470
    typedef regex_constants::syntax_option_type flag_type;
2471
    typedef typename _Traits::locale_type       locale_type;
2472

    
2473
private:
2474
    _Traits   __traits_;
2475
    flag_type __flags_;
2476
    unsigned __marked_count_;
2477
    unsigned __loop_count_;
2478
    int __open_count_;
2479
    shared_ptr<__empty_state<_CharT> > __start_;
2480
    __owns_one_state<_CharT>* __end_;
2481

    
2482
    typedef _VSTD::__state<_CharT> __state;
2483
    typedef _VSTD::__node<_CharT> __node;
2484

    
2485
public:
2486
    // constants:
2487
    static const regex_constants::syntax_option_type icase = regex_constants::icase;
2488
    static const regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
2489
    static const regex_constants::syntax_option_type optimize = regex_constants::optimize;
2490
    static const regex_constants::syntax_option_type collate = regex_constants::collate;
2491
    static const regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
2492
    static const regex_constants::syntax_option_type basic = regex_constants::basic;
2493
    static const regex_constants::syntax_option_type extended = regex_constants::extended;
2494
    static const regex_constants::syntax_option_type awk = regex_constants::awk;
2495
    static const regex_constants::syntax_option_type grep = regex_constants::grep;
2496
    static const regex_constants::syntax_option_type egrep = regex_constants::egrep;
2497

    
2498
    // construct/copy/destroy:
2499
    _LIBCPP_INLINE_VISIBILITY
2500
    basic_regex()
2501
        : __flags_(), __marked_count_(0), __loop_count_(0), __open_count_(0),
2502
          __end_(0)
2503
        {}
2504
    _LIBCPP_INLINE_VISIBILITY
2505
    explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
2506
        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2507
          __end_(0)
2508
        {__parse(__p, __p + __traits_.length(__p));}
2509
    _LIBCPP_INLINE_VISIBILITY
2510
    basic_regex(const value_type* __p, size_t __len, flag_type __f)
2511
        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2512
          __end_(0)
2513
        {__parse(__p, __p + __len);}
2514
//     basic_regex(const basic_regex&) = default;
2515
//     basic_regex(basic_regex&&) = default;
2516
    template <class _ST, class _SA>
2517
        _LIBCPP_INLINE_VISIBILITY
2518
        explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
2519
                             flag_type __f = regex_constants::ECMAScript)
2520
        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2521
          __end_(0)
2522
        {__parse(__p.begin(), __p.end());}
2523
    template <class _ForwardIterator>
2524
        _LIBCPP_INLINE_VISIBILITY
2525
        basic_regex(_ForwardIterator __first, _ForwardIterator __last,
2526
                    flag_type __f = regex_constants::ECMAScript)
2527
        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2528
          __end_(0)
2529
        {__parse(__first, __last);}
2530
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2531
    _LIBCPP_INLINE_VISIBILITY
2532
    basic_regex(initializer_list<value_type> __il,
2533
                flag_type __f = regex_constants::ECMAScript)
2534
        : __flags_(__f), __marked_count_(0), __loop_count_(0), __open_count_(0),
2535
          __end_(0)
2536
        {__parse(__il.begin(), __il.end());}
2537
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2538

    
2539
//    ~basic_regex() = default;
2540

    
2541
//     basic_regex& operator=(const basic_regex&) = default;
2542
//     basic_regex& operator=(basic_regex&&) = default;
2543
    _LIBCPP_INLINE_VISIBILITY
2544
    basic_regex& operator=(const value_type* __p)
2545
        {return assign(__p);}
2546
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2547
    _LIBCPP_INLINE_VISIBILITY
2548
    basic_regex& operator=(initializer_list<value_type> __il)
2549
        {return assign(__il);}
2550
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2551
    template <class _ST, class _SA>
2552
        _LIBCPP_INLINE_VISIBILITY
2553
        basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p)
2554
        {return assign(__p);}
2555

    
2556
    // assign:
2557
    _LIBCPP_INLINE_VISIBILITY
2558
    basic_regex& assign(const basic_regex& __that)
2559
        {return *this = __that;}
2560
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2561
    _LIBCPP_INLINE_VISIBILITY
2562
    basic_regex& assign(basic_regex&& __that) _NOEXCEPT
2563
        {return *this = _VSTD::move(__that);}
2564
#endif
2565
    _LIBCPP_INLINE_VISIBILITY
2566
    basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
2567
        {return assign(__p, __p + __traits_.length(__p), __f);}
2568
    _LIBCPP_INLINE_VISIBILITY
2569
    basic_regex& assign(const value_type* __p, size_t __len, flag_type __f)
2570
        {return assign(__p, __p + __len, __f);}
2571
    template <class _ST, class _SA>
2572
        _LIBCPP_INLINE_VISIBILITY
2573
        basic_regex& assign(const basic_string<value_type, _ST, _SA>& __s,
2574
                            flag_type __f = regex_constants::ECMAScript)
2575
            {return assign(__s.begin(), __s.end(), __f);}
2576

    
2577
    template <class _InputIterator>
2578
        _LIBCPP_INLINE_VISIBILITY
2579
        typename enable_if
2580
        <
2581
             __is_input_iterator  <_InputIterator>::value &&
2582
            !__is_forward_iterator<_InputIterator>::value,
2583
            basic_regex&
2584
        >::type
2585
        assign(_InputIterator __first, _InputIterator __last,
2586
                            flag_type __f = regex_constants::ECMAScript)
2587
        {
2588
            basic_string<_CharT> __t(__first, __last);
2589
            return assign(__t.begin(), __t.end(), __f);
2590
        }
2591

    
2592
private:
2593
    _LIBCPP_INLINE_VISIBILITY
2594
    void __member_init(flag_type __f)
2595
    {
2596
        __flags_ = __f;
2597
        __marked_count_ = 0;
2598
        __loop_count_ = 0;
2599
        __open_count_ = 0;
2600
        __end_ = nullptr;
2601
    }
2602
public:
2603

    
2604
    template <class _ForwardIterator>
2605
        _LIBCPP_INLINE_VISIBILITY
2606
        typename enable_if
2607
        <
2608
            __is_forward_iterator<_ForwardIterator>::value,
2609
            basic_regex&
2610
        >::type
2611
        assign(_ForwardIterator __first, _ForwardIterator __last,
2612
                            flag_type __f = regex_constants::ECMAScript)
2613
        {
2614
            return assign(basic_regex(__first, __last, __f));
2615
        }
2616

    
2617
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2618

    
2619
    _LIBCPP_INLINE_VISIBILITY
2620
    basic_regex& assign(initializer_list<value_type> __il,
2621
                        flag_type __f = regex_constants::ECMAScript)
2622
        {return assign(__il.begin(), __il.end(), __f);}
2623

    
2624
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2625

    
2626
    // const operations:
2627
    _LIBCPP_INLINE_VISIBILITY
2628
    unsigned mark_count() const {return __marked_count_;}
2629
    _LIBCPP_INLINE_VISIBILITY
2630
    flag_type flags() const {return __flags_;}
2631

    
2632
    // locale:
2633
    _LIBCPP_INLINE_VISIBILITY
2634
    locale_type imbue(locale_type __loc)
2635
    {
2636
        __member_init(ECMAScript);
2637
        __start_.reset();
2638
        return __traits_.imbue(__loc);
2639
    }
2640
    _LIBCPP_INLINE_VISIBILITY
2641
    locale_type getloc() const {return __traits_.getloc();}
2642

    
2643
    // swap:
2644
    void swap(basic_regex& __r);
2645

    
2646
private:
2647
    _LIBCPP_INLINE_VISIBILITY
2648
    unsigned __loop_count() const {return __loop_count_;}
2649

    
2650
    template <class _ForwardIterator>
2651
        _ForwardIterator
2652
        __parse(_ForwardIterator __first, _ForwardIterator __last);
2653
    template <class _ForwardIterator>
2654
        _ForwardIterator
2655
        __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2656
    template <class _ForwardIterator>
2657
        _ForwardIterator
2658
        __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
2659
    template <class _ForwardIterator>
2660
        _ForwardIterator
2661
        __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
2662
    template <class _ForwardIterator>
2663
        _ForwardIterator
2664
        __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
2665
    template <class _ForwardIterator>
2666
        _ForwardIterator
2667
        __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
2668
    template <class _ForwardIterator>
2669
        _ForwardIterator
2670
        __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
2671
    template <class _ForwardIterator>
2672
        _ForwardIterator
2673
        __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
2674
    template <class _ForwardIterator>
2675
        _ForwardIterator
2676
        __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
2677
    template <class _ForwardIterator>
2678
        _ForwardIterator
2679
        __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
2680
    template <class _ForwardIterator>
2681
        _ForwardIterator
2682
        __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
2683
    template <class _ForwardIterator>
2684
        _ForwardIterator
2685
        __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2686
    template <class _ForwardIterator>
2687
        _ForwardIterator
2688
        __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
2689
    template <class _ForwardIterator>
2690
        _ForwardIterator
2691
        __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2692
                               __owns_one_state<_CharT>* __s,
2693
                               unsigned __mexp_begin, unsigned __mexp_end);
2694
    template <class _ForwardIterator>
2695
        _ForwardIterator
2696
        __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last,
2697
                                __owns_one_state<_CharT>* __s,
2698
                                unsigned __mexp_begin, unsigned __mexp_end);
2699
    template <class _ForwardIterator>
2700
        _ForwardIterator
2701
        __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
2702
    template <class _ForwardIterator>
2703
        _ForwardIterator
2704
        __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last,
2705
                            __bracket_expression<_CharT, _Traits>* __ml);
2706
    template <class _ForwardIterator>
2707
        _ForwardIterator
2708
        __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last,
2709
                                __bracket_expression<_CharT, _Traits>* __ml);
2710
    template <class _ForwardIterator>
2711
        _ForwardIterator
2712
        __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last,
2713
                                  __bracket_expression<_CharT, _Traits>* __ml);
2714
    template <class _ForwardIterator>
2715
        _ForwardIterator
2716
        __parse_character_class(_ForwardIterator __first, _ForwardIterator __last,
2717
                                __bracket_expression<_CharT, _Traits>* __ml);
2718
    template <class _ForwardIterator>
2719
        _ForwardIterator
2720
        __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last,
2721
                                 basic_string<_CharT>& __col_sym);
2722
    template <class _ForwardIterator>
2723
        _ForwardIterator
2724
        __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
2725
    template <class _ForwardIterator>
2726
        _ForwardIterator
2727
        __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
2728
    template <class _ForwardIterator>
2729
        _ForwardIterator
2730
        __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
2731
    template <class _ForwardIterator>
2732
        _ForwardIterator
2733
        __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
2734
    template <class _ForwardIterator>
2735
        _ForwardIterator
2736
        __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
2737
    template <class _ForwardIterator>
2738
        _ForwardIterator
2739
        __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2740
    template <class _ForwardIterator>
2741
        _ForwardIterator
2742
        __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
2743
    template <class _ForwardIterator>
2744
        _ForwardIterator
2745
        __parse_ecma_exp(_ForwardIterator __first, _ForwardIterator __last);
2746
    template <class _ForwardIterator>
2747
        _ForwardIterator
2748
        __parse_alternative(_ForwardIterator __first, _ForwardIterator __last);
2749
    template <class _ForwardIterator>
2750
        _ForwardIterator
2751
        __parse_term(_ForwardIterator __first, _ForwardIterator __last);
2752
    template <class _ForwardIterator>
2753
        _ForwardIterator
2754
        __parse_assertion(_ForwardIterator __first, _ForwardIterator __last);
2755
    template <class _ForwardIterator>
2756
        _ForwardIterator
2757
        __parse_atom(_ForwardIterator __first, _ForwardIterator __last);
2758
    template <class _ForwardIterator>
2759
        _ForwardIterator
2760
        __parse_atom_escape(_ForwardIterator __first, _ForwardIterator __last);
2761
    template <class _ForwardIterator>
2762
        _ForwardIterator
2763
        __parse_decimal_escape(_ForwardIterator __first, _ForwardIterator __last);
2764
    template <class _ForwardIterator>
2765
        _ForwardIterator
2766
        __parse_character_class_escape(_ForwardIterator __first, _ForwardIterator __last);
2767
    template <class _ForwardIterator>
2768
        _ForwardIterator
2769
        __parse_character_escape(_ForwardIterator __first, _ForwardIterator __last,
2770
                                 basic_string<_CharT>* __str = nullptr);
2771
    template <class _ForwardIterator>
2772
        _ForwardIterator
2773
        __parse_pattern_character(_ForwardIterator __first, _ForwardIterator __last);
2774
    template <class _ForwardIterator>
2775
        _ForwardIterator
2776
        __parse_grep(_ForwardIterator __first, _ForwardIterator __last);
2777
    template <class _ForwardIterator>
2778
        _ForwardIterator
2779
        __parse_egrep(_ForwardIterator __first, _ForwardIterator __last);
2780
    template <class _ForwardIterator>
2781
        _ForwardIterator
2782
        __parse_class_escape(_ForwardIterator __first, _ForwardIterator __last,
2783
                          basic_string<_CharT>& __str,
2784
                          __bracket_expression<_CharT, _Traits>* __ml);
2785
    template <class _ForwardIterator>
2786
        _ForwardIterator
2787
        __parse_awk_escape(_ForwardIterator __first, _ForwardIterator __last,
2788
                          basic_string<_CharT>* __str = nullptr);
2789

    
2790
    _LIBCPP_INLINE_VISIBILITY
2791
    void __push_l_anchor();
2792
    void __push_r_anchor();
2793
    void __push_match_any();
2794
    void __push_match_any_but_newline();
2795
    _LIBCPP_INLINE_VISIBILITY
2796
    void __push_greedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
2797
                                  unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
2798
        {__push_loop(__min, numeric_limits<size_t>::max(), __s,
2799
                     __mexp_begin, __mexp_end);}
2800
    _LIBCPP_INLINE_VISIBILITY
2801
    void __push_nongreedy_inf_repeat(size_t __min, __owns_one_state<_CharT>* __s,
2802
                                  unsigned __mexp_begin = 0, unsigned __mexp_end = 0)
2803
        {__push_loop(__min, numeric_limits<size_t>::max(), __s,
2804
                     __mexp_begin, __mexp_end, false);}
2805
    void __push_loop(size_t __min, size_t __max, __owns_one_state<_CharT>* __s,
2806
                     size_t __mexp_begin = 0, size_t __mexp_end = 0,
2807
                     bool __greedy = true);
2808
    __bracket_expression<_CharT, _Traits>* __start_matching_list(bool __negate);
2809
    void __push_char(value_type __c);
2810
    void __push_back_ref(int __i);
2811
    void __push_alternation(__owns_one_state<_CharT>* __sa,
2812
                            __owns_one_state<_CharT>* __sb);
2813
    void __push_begin_marked_subexpression();
2814
    void __push_end_marked_subexpression(unsigned);
2815
    void __push_empty();
2816
    void __push_word_boundary(bool);
2817
    void __push_lookahead(const basic_regex&, bool, unsigned);
2818

    
2819
    template <class _Allocator>
2820
        bool
2821
        __search(const _CharT* __first, const _CharT* __last,
2822
                 match_results<const _CharT*, _Allocator>& __m,
2823
                 regex_constants::match_flag_type __flags) const;
2824

    
2825
    template <class _Allocator>
2826
        bool
2827
        __match_at_start(const _CharT* __first, const _CharT* __last,
2828
                 match_results<const _CharT*, _Allocator>& __m,
2829
                 regex_constants::match_flag_type __flags, bool) const;
2830
    template <class _Allocator>
2831
        bool
2832
        __match_at_start_ecma(const _CharT* __first, const _CharT* __last,
2833
                 match_results<const _CharT*, _Allocator>& __m,
2834
                 regex_constants::match_flag_type __flags, bool) const;
2835
    template <class _Allocator>
2836
        bool
2837
        __match_at_start_posix_nosubs(const _CharT* __first, const _CharT* __last,
2838
                 match_results<const _CharT*, _Allocator>& __m,
2839
                 regex_constants::match_flag_type __flags, bool) const;
2840
    template <class _Allocator>
2841
        bool
2842
        __match_at_start_posix_subs(const _CharT* __first, const _CharT* __last,
2843
                 match_results<const _CharT*, _Allocator>& __m,
2844
                 regex_constants::match_flag_type __flags, bool) const;
2845

    
2846
    template <class _Bp, class _Ap, class _Cp, class _Tp>
2847
    friend
2848
    bool
2849
    regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
2850
                 regex_constants::match_flag_type);
2851

    
2852
    template <class _Ap, class _Cp, class _Tp>
2853
    friend
2854
    bool
2855
    regex_search(const _Cp*, const _Cp*, match_results<const _Cp*, _Ap>&,
2856
                 const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2857

    
2858
    template <class _Bp, class _Cp, class _Tp>
2859
    friend
2860
    bool
2861
    regex_search(_Bp, _Bp, const basic_regex<_Cp, _Tp>&,
2862
                 regex_constants::match_flag_type);
2863

    
2864
    template <class _Cp, class _Tp>
2865
    friend
2866
    bool
2867
    regex_search(const _Cp*, const _Cp*,
2868
                 const basic_regex<_Cp, _Tp>&, regex_constants::match_flag_type);
2869

    
2870
    template <class _Cp, class _Ap, class _Tp>
2871
    friend
2872
    bool
2873
    regex_search(const _Cp*, match_results<const _Cp*, _Ap>&, const basic_regex<_Cp, _Tp>&,
2874
                 regex_constants::match_flag_type);
2875

    
2876
    template <class _ST, class _SA, class _Cp, class _Tp>
2877
    friend
2878
    bool
2879
    regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2880
                 const basic_regex<_Cp, _Tp>& __e,
2881
                 regex_constants::match_flag_type __flags);
2882

    
2883
    template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
2884
    friend
2885
    bool
2886
    regex_search(const basic_string<_Cp, _ST, _SA>& __s,
2887
                 match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
2888
                 const basic_regex<_Cp, _Tp>& __e,
2889
                 regex_constants::match_flag_type __flags);
2890

    
2891
    template <class _Iter, class _Ap, class _Cp, class _Tp>
2892
    friend
2893
    bool
2894
    regex_search(__wrap_iter<_Iter> __first,
2895
                 __wrap_iter<_Iter> __last,
2896
                 match_results<__wrap_iter<_Iter>, _Ap>& __m,
2897
                 const basic_regex<_Cp, _Tp>& __e,
2898
                 regex_constants::match_flag_type __flags);
2899

    
2900
    template <class, class> friend class __lookahead;
2901
};
2902

    
2903
template <class _CharT, class _Traits>
2904
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::icase;
2905
template <class _CharT, class _Traits>
2906
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::nosubs;
2907
template <class _CharT, class _Traits>
2908
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::optimize;
2909
template <class _CharT, class _Traits>
2910
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::collate;
2911
template <class _CharT, class _Traits>
2912
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::ECMAScript;
2913
template <class _CharT, class _Traits>
2914
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::basic;
2915
template <class _CharT, class _Traits>
2916
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::extended;
2917
template <class _CharT, class _Traits>
2918
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::awk;
2919
template <class _CharT, class _Traits>
2920
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::grep;
2921
template <class _CharT, class _Traits>
2922
    const regex_constants::syntax_option_type basic_regex<_CharT, _Traits>::egrep;
2923

    
2924
template <class _CharT, class _Traits>
2925
void
2926
basic_regex<_CharT, _Traits>::swap(basic_regex& __r)
2927
{
2928
    using _VSTD::swap;
2929
    swap(__traits_, __r.__traits_);
2930
    swap(__flags_, __r.__flags_);
2931
    swap(__marked_count_, __r.__marked_count_);
2932
    swap(__loop_count_, __r.__loop_count_);
2933
    swap(__open_count_, __r.__open_count_);
2934
    swap(__start_, __r.__start_);
2935
    swap(__end_, __r.__end_);
2936
}
2937

    
2938
template <class _CharT, class _Traits>
2939
inline _LIBCPP_INLINE_VISIBILITY
2940
void
2941
swap(basic_regex<_CharT, _Traits>& __x, basic_regex<_CharT, _Traits>& __y)
2942
{
2943
    return __x.swap(__y);
2944
}
2945

    
2946
// __lookahead
2947

    
2948
template <class _CharT, class _Traits>
2949
class __lookahead
2950
    : public __owns_one_state<_CharT>
2951
{
2952
    typedef __owns_one_state<_CharT> base;
2953

    
2954
    basic_regex<_CharT, _Traits> __exp_;
2955
    unsigned __mexp_;
2956
    bool __invert_;
2957

    
2958
    __lookahead(const __lookahead&);
2959
    __lookahead& operator=(const __lookahead&);
2960
public:
2961
    typedef _VSTD::__state<_CharT> __state;
2962

    
2963
    _LIBCPP_INLINE_VISIBILITY
2964
    __lookahead(const basic_regex<_CharT, _Traits>& __exp, bool __invert, __node<_CharT>* __s, unsigned __mexp)
2965
        : base(__s), __exp_(__exp), __mexp_(__mexp), __invert_(__invert) {}
2966

    
2967
    virtual void __exec(__state&) const;
2968
};
2969

    
2970
template <class _CharT, class _Traits>
2971
void
2972
__lookahead<_CharT, _Traits>::__exec(__state& __s) const
2973
{
2974
    match_results<const _CharT*> __m;
2975
    __m.__init(1 + __exp_.mark_count(), __s.__current_, __s.__last_);
2976
    bool __matched = __exp_.__match_at_start_ecma(__s.__current_, __s.__last_,
2977
                                                  __m,
2978
                                                  __s.__flags_ | regex_constants::match_continuous,
2979
                                                  __s.__at_first_ && __s.__current_ == __s.__first_);
2980
    if (__matched != __invert_)
2981
    {
2982
        __s.__do_ = __state::__accept_but_not_consume;
2983
        __s.__node_ = this->first();
2984
        for (unsigned __i = 1; __i < __m.size(); ++__i) {
2985
            __s.__sub_matches_[__mexp_ + __i - 1] = __m.__matches_[__i];
2986
        }
2987
    }
2988
    else
2989
    {
2990
        __s.__do_ = __state::__reject;
2991
        __s.__node_ = nullptr;
2992
    }
2993
}
2994

    
2995
template <class _CharT, class _Traits>
2996
template <class _ForwardIterator>
2997
_ForwardIterator
2998
basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
2999
                                      _ForwardIterator __last)
3000
{
3001
    {
3002
        unique_ptr<__node> __h(new __end_state<_CharT>);
3003
        __start_.reset(new __empty_state<_CharT>(__h.get()));
3004
        __h.release();
3005
        __end_ = __start_.get();
3006
    }
3007
    switch (__flags_ & 0x1F0)
3008
    {
3009
    case ECMAScript:
3010
        __first = __parse_ecma_exp(__first, __last);
3011
        break;
3012
    case basic:
3013
        __first = __parse_basic_reg_exp(__first, __last);
3014
        break;
3015
    case extended:
3016
    case awk:
3017
        __first = __parse_extended_reg_exp(__first, __last);
3018
        break;
3019
    case grep:
3020
        __first = __parse_grep(__first, __last);
3021
        break;
3022
    case egrep:
3023
        __first = __parse_egrep(__first, __last);
3024
        break;
3025
    default:
3026
        __throw_regex_error<regex_constants::__re_err_grammar>();
3027
    }
3028
    return __first;
3029
}
3030

    
3031
template <class _CharT, class _Traits>
3032
template <class _ForwardIterator>
3033
_ForwardIterator
3034
basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
3035
                                                    _ForwardIterator __last)
3036
{
3037
    if (__first != __last)
3038
    {
3039
        if (*__first == '^')
3040
        {
3041
            __push_l_anchor();
3042
            ++__first;
3043
        }
3044
        if (__first != __last)
3045
        {
3046
            __first = __parse_RE_expression(__first, __last);
3047
            if (__first != __last)
3048
            {
3049
                _ForwardIterator __temp = _VSTD::next(__first);
3050
                if (__temp == __last && *__first == '$')
3051
                {
3052
                    __push_r_anchor();
3053
                    ++__first;
3054
                }
3055
            }
3056
        }
3057
        if (__first != __last)
3058
            __throw_regex_error<regex_constants::__re_err_empty>();
3059
    }
3060
    return __first;
3061
}
3062

    
3063
template <class _CharT, class _Traits>
3064
template <class _ForwardIterator>
3065
_ForwardIterator
3066
basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
3067
                                                       _ForwardIterator __last)
3068
{
3069
    __owns_one_state<_CharT>* __sa = __end_;
3070
    _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
3071
    if (__temp == __first)
3072
        __throw_regex_error<regex_constants::__re_err_empty>();
3073
    __first = __temp;
3074
    while (__first != __last && *__first == '|')
3075
    {
3076
        __owns_one_state<_CharT>* __sb = __end_;
3077
        __temp = __parse_ERE_branch(++__first, __last);
3078
        if (__temp == __first)
3079
            __throw_regex_error<regex_constants::__re_err_empty>();
3080
        __push_alternation(__sa, __sb);
3081
        __first = __temp;
3082
    }
3083
    return __first;
3084
}
3085

    
3086
template <class _CharT, class _Traits>
3087
template <class _ForwardIterator>
3088
_ForwardIterator
3089
basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
3090
                                                 _ForwardIterator __last)
3091
{
3092
    _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
3093
    if (__temp == __first)
3094
        __throw_regex_error<regex_constants::__re_err_empty>();
3095
    do
3096
    {
3097
        __first = __temp;
3098
        __temp = __parse_ERE_expression(__first, __last);
3099
    } while (__temp != __first);
3100
    return __first;
3101
}
3102

    
3103
template <class _CharT, class _Traits>
3104
template <class _ForwardIterator>
3105
_ForwardIterator
3106
basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
3107
                                                     _ForwardIterator __last)
3108
{
3109
    __owns_one_state<_CharT>* __e = __end_;
3110
    unsigned __mexp_begin = __marked_count_;
3111
    _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
3112
    if (__temp == __first && __temp != __last)
3113
    {
3114
        switch (*__temp)
3115
        {
3116
        case '^':
3117
            __push_l_anchor();
3118
            ++__temp;
3119
            break;
3120
        case '$':
3121
            __push_r_anchor();
3122
            ++__temp;
3123
            break;
3124
        case '(':
3125
            __push_begin_marked_subexpression();
3126
            unsigned __temp_count = __marked_count_;
3127
            ++__open_count_;
3128
            __temp = __parse_extended_reg_exp(++__temp, __last);
3129
            if (__temp == __last || *__temp != ')')
3130
                __throw_regex_error<regex_constants::error_paren>();
3131
            __push_end_marked_subexpression(__temp_count);
3132
            --__open_count_;
3133
            ++__temp;
3134
            break;
3135
        }
3136
    }
3137
    if (__temp != __first)
3138
        __temp = __parse_ERE_dupl_symbol(__temp, __last, __e, __mexp_begin+1,
3139
                                         __marked_count_+1);
3140
    __first = __temp;
3141
    return __first;
3142
}
3143

    
3144
template <class _CharT, class _Traits>
3145
template <class _ForwardIterator>
3146
_ForwardIterator
3147
basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
3148
                                                    _ForwardIterator __last)
3149
{
3150
    while (true)
3151
    {
3152
        _ForwardIterator __temp = __parse_simple_RE(__first, __last);
3153
        if (__temp == __first)
3154
            break;
3155
        __first = __temp;
3156
    }
3157
    return __first;
3158
}
3159

    
3160
template <class _CharT, class _Traits>
3161
template <class _ForwardIterator>
3162
_ForwardIterator
3163
basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
3164
                                                _ForwardIterator __last)
3165
{
3166
    if (__first != __last)
3167
    {
3168
        __owns_one_state<_CharT>* __e = __end_;
3169
        unsigned __mexp_begin = __marked_count_;
3170
        _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
3171
        if (__temp != __first)
3172
            __first = __parse_RE_dupl_symbol(__temp, __last, __e,
3173
                                             __mexp_begin+1, __marked_count_+1);
3174
    }
3175
    return __first;
3176
}
3177

    
3178
template <class _CharT, class _Traits>
3179
template <class _ForwardIterator>
3180
_ForwardIterator
3181
basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
3182
                                                 _ForwardIterator __last)
3183
{
3184
    _ForwardIterator __temp = __first;
3185
    __first = __parse_one_char_or_coll_elem_RE(__first, __last);
3186
    if (__temp == __first)
3187
    {
3188
        __temp = __parse_Back_open_paren(__first, __last);
3189
        if (__temp != __first)
3190
        {
3191
            __push_begin_marked_subexpression();
3192
            unsigned __temp_count = __marked_count_;
3193
            __first = __parse_RE_expression(__temp, __last);
3194
            __temp = __parse_Back_close_paren(__first, __last);
3195
            if (__temp == __first)
3196
                __throw_regex_error<regex_constants::error_paren>();
3197
            __push_end_marked_subexpression(__temp_count);
3198
            __first = __temp;
3199
        }
3200
        else
3201
            __first = __parse_BACKREF(__first, __last);
3202
    }
3203
    return __first;
3204
}
3205

    
3206
template <class _CharT, class _Traits>
3207
template <class _ForwardIterator>
3208
_ForwardIterator
3209
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
3210
                                                       _ForwardIterator __first,
3211
                                                       _ForwardIterator __last)
3212
{
3213
    _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
3214
    if (__temp == __first)
3215
    {
3216
        __temp = __parse_QUOTED_CHAR(__first, __last);
3217
        if (__temp == __first)
3218
        {
3219
            if (__temp != __last && *__temp == '.')
3220
            {
3221
                __push_match_any();
3222
                ++__temp;
3223
            }
3224
            else
3225
                __temp = __parse_bracket_expression(__first, __last);
3226
        }
3227
    }
3228
    __first = __temp;
3229
    return __first;
3230
}
3231

    
3232
template <class _CharT, class _Traits>
3233
template <class _ForwardIterator>
3234
_ForwardIterator
3235
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
3236
                                                       _ForwardIterator __first,
3237
                                                       _ForwardIterator __last)
3238
{
3239
    _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
3240
    if (__temp == __first)
3241
    {
3242
        __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
3243
        if (__temp == __first)
3244
        {
3245
            if (__temp != __last && *__temp == '.')
3246
            {
3247
                __push_match_any();
3248
                ++__temp;
3249
            }
3250
            else
3251
                __temp = __parse_bracket_expression(__first, __last);
3252
        }
3253
    }
3254
    __first = __temp;
3255
    return __first;
3256
}
3257

    
3258
template <class _CharT, class _Traits>
3259
template <class _ForwardIterator>
3260
_ForwardIterator
3261
basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
3262
                                                      _ForwardIterator __last)
3263
{
3264
    if (__first != __last)
3265
    {
3266
        _ForwardIterator __temp = _VSTD::next(__first);
3267
        if (__temp != __last)
3268
        {
3269
            if (*__first == '\\' && *__temp == '(')
3270
                __first = ++__temp;
3271
        }
3272
    }
3273
    return __first;
3274
}
3275

    
3276
template <class _CharT, class _Traits>
3277
template <class _ForwardIterator>
3278
_ForwardIterator
3279
basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
3280
                                                       _ForwardIterator __last)
3281
{
3282
    if (__first != __last)
3283
    {
3284
        _ForwardIterator __temp = _VSTD::next(__first);
3285
        if (__temp != __last)
3286
        {
3287
            if (*__first == '\\' && *__temp == ')')
3288
                __first = ++__temp;
3289
        }
3290
    }
3291
    return __first;
3292
}
3293

    
3294
template <class _CharT, class _Traits>
3295
template <class _ForwardIterator>
3296
_ForwardIterator
3297
basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
3298
                                                      _ForwardIterator __last)
3299
{
3300
    if (__first != __last)
3301
    {
3302
        _ForwardIterator __temp = _VSTD::next(__first);
3303
        if (__temp != __last)
3304
        {
3305
            if (*__first == '\\' && *__temp == '{')
3306
                __first = ++__temp;
3307
        }
3308
    }
3309
    return __first;
3310
}
3311

    
3312
template <class _CharT, class _Traits>
3313
template <class _ForwardIterator>
3314
_ForwardIterator
3315
basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
3316
                                                       _ForwardIterator __last)
3317
{
3318
    if (__first != __last)
3319
    {
3320
        _ForwardIterator __temp = _VSTD::next(__first);
3321
        if (__temp != __last)
3322
        {
3323
            if (*__first == '\\' && *__temp == '}')
3324
                __first = ++__temp;
3325
        }
3326
    }
3327
    return __first;
3328
}
3329

    
3330
template <class _CharT, class _Traits>
3331
template <class _ForwardIterator>
3332
_ForwardIterator
3333
basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
3334
                                              _ForwardIterator __last)
3335
{
3336
    if (__first != __last)
3337
    {
3338
        _ForwardIterator __temp = _VSTD::next(__first);
3339
        if (__temp != __last)
3340
        {
3341
            if (*__first == '\\')
3342
            { 
3343
                int __val = __traits_.value(*__temp, 10);
3344
                if (__val >= 1 && __val <= 9)
3345
                {
3346
                    __push_back_ref(__val);
3347
                    __first = ++__temp;
3348
                }
3349
            }
3350
        }
3351
    }
3352
    return __first;
3353
}
3354

    
3355
template <class _CharT, class _Traits>
3356
template <class _ForwardIterator>
3357
_ForwardIterator
3358
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
3359
                                               _ForwardIterator __last)
3360
{
3361
    if (__first != __last)
3362
    {
3363
        _ForwardIterator __temp = _VSTD::next(__first);
3364
        if (__temp == __last && *__first == '$')
3365
            return __first;
3366
        // Not called inside a bracket
3367
        if (*__first == '.' || *__first == '\\' || *__first == '[')
3368
            return __first;
3369
        __push_char(*__first);
3370
        ++__first;
3371
    }
3372
    return __first;
3373
}
3374

    
3375
template <class _CharT, class _Traits>
3376
template <class _ForwardIterator>
3377
_ForwardIterator
3378
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
3379
                                                   _ForwardIterator __last)
3380
{
3381
    if (__first != __last)
3382
    {
3383
        switch (*__first)
3384
        {
3385
        case '^':
3386
        case '.':
3387
        case '[':
3388
        case '$':
3389
        case '(':
3390
        case '|':
3391
        case '*':
3392
        case '+':
3393
        case '?':
3394
        case '{':
3395
        case '\\':
3396
            break;
3397
        case ')':
3398
            if (__open_count_ == 0)
3399
            {
3400
                __push_char(*__first);
3401
                ++__first;
3402
            }
3403
            break;
3404
        default:
3405
            __push_char(*__first);
3406
            ++__first;
3407
            break;
3408
        }
3409
    }
3410
    return __first;
3411
}
3412

    
3413
template <class _CharT, class _Traits>
3414
template <class _ForwardIterator>
3415
_ForwardIterator
3416
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
3417
                                                  _ForwardIterator __last)
3418
{
3419
    if (__first != __last)
3420
    {
3421
        _ForwardIterator __temp = _VSTD::next(__first);
3422
        if (__temp != __last)
3423
        {
3424
            if (*__first == '\\')
3425
            {
3426
                switch (*__temp)
3427
                {
3428
                case '^':
3429
                case '.':
3430
                case '*':
3431
                case '[':
3432
                case '$':
3433
                case '\\':
3434
                    __push_char(*__temp);
3435
                    __first = ++__temp;
3436
                    break;
3437
                }
3438
            }
3439
        }
3440
    }
3441
    return __first;
3442
}
3443

    
3444
template <class _CharT, class _Traits>
3445
template <class _ForwardIterator>
3446
_ForwardIterator
3447
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
3448
                                                      _ForwardIterator __last)
3449
{
3450
    if (__first != __last)
3451
    {
3452
        _ForwardIterator __temp = _VSTD::next(__first);
3453
        if (__temp != __last)
3454
        {
3455
            if (*__first == '\\')
3456
            {
3457
                switch (*__temp)
3458
                {
3459
                case '^':
3460
                case '.':
3461
                case '*':
3462
                case '[':
3463
                case '$':
3464
                case '\\':
3465
                case '(':
3466
                case ')':
3467
                case '|':
3468
                case '+':
3469
                case '?':
3470
                case '{':
3471
                case '}':
3472
                    __push_char(*__temp);
3473
                    __first = ++__temp;
3474
                    break;
3475
                default:
3476
                    if ((__flags_ & 0x1F0) == awk)
3477
                        __first = __parse_awk_escape(++__first, __last);
3478
                    break;
3479
                }
3480
            }
3481
        }
3482
    }
3483
    return __first;
3484
}
3485

    
3486
template <class _CharT, class _Traits>
3487
template <class _ForwardIterator>
3488
_ForwardIterator
3489
basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
3490
                                                     _ForwardIterator __last,
3491
                                                     __owns_one_state<_CharT>* __s,
3492
                                                     unsigned __mexp_begin,
3493
                                                     unsigned __mexp_end)
3494
{
3495
    if (__first != __last)
3496
    {
3497
        if (*__first == '*')
3498
        {
3499
            __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3500
            ++__first;
3501
        }
3502
        else
3503
        {
3504
            _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
3505
            if (__temp != __first)
3506
            {
3507
                int __min = 0;
3508
                __first = __temp;
3509
                __temp = __parse_DUP_COUNT(__first, __last, __min);
3510
                if (__temp == __first)
3511
                    __throw_regex_error<regex_constants::error_badbrace>();
3512
                __first = __temp;
3513
                if (__first == __last)
3514
                    __throw_regex_error<regex_constants::error_brace>();
3515
                if (*__first != ',')
3516
                {
3517
                    __temp = __parse_Back_close_brace(__first, __last);
3518
                    if (__temp == __first)
3519
                        __throw_regex_error<regex_constants::error_brace>();
3520
                    __push_loop(__min, __min, __s, __mexp_begin, __mexp_end,
3521
                                    true);
3522
                    __first = __temp;
3523
                }
3524
                else
3525
                {
3526
                    ++__first;  // consume ','
3527
                    int __max = -1;
3528
                    __first = __parse_DUP_COUNT(__first, __last, __max);
3529
                    __temp = __parse_Back_close_brace(__first, __last);
3530
                    if (__temp == __first)
3531
                        __throw_regex_error<regex_constants::error_brace>();
3532
                    if (__max == -1)
3533
                        __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3534
                    else
3535
                    {
3536
                        if (__max < __min)
3537
                            __throw_regex_error<regex_constants::error_badbrace>();
3538
                        __push_loop(__min, __max, __s, __mexp_begin, __mexp_end,
3539
                                    true);
3540
                    }
3541
                    __first = __temp;
3542
                }
3543
            }
3544
        }
3545
    }
3546
    return __first;
3547
}
3548

    
3549
template <class _CharT, class _Traits>
3550
template <class _ForwardIterator>
3551
_ForwardIterator
3552
basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
3553
                                                      _ForwardIterator __last,
3554
                                                      __owns_one_state<_CharT>* __s,
3555
                                                      unsigned __mexp_begin,
3556
                                                      unsigned __mexp_end)
3557
{
3558
    if (__first != __last)
3559
    {
3560
        unsigned __grammar = __flags_ & 0x1F0;
3561
        switch (*__first)
3562
        {
3563
        case '*':
3564
            ++__first;
3565
            if (__grammar == ECMAScript && __first != __last && *__first == '?')
3566
            {
3567
                ++__first;
3568
                __push_nongreedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3569
            }
3570
            else
3571
                __push_greedy_inf_repeat(0, __s, __mexp_begin, __mexp_end);
3572
            break;
3573
        case '+':
3574
            ++__first;
3575
            if (__grammar == ECMAScript && __first != __last && *__first == '?')
3576
            {
3577
                ++__first;
3578
                __push_nongreedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3579
            }
3580
            else
3581
                __push_greedy_inf_repeat(1, __s, __mexp_begin, __mexp_end);
3582
            break;
3583
        case '?':
3584
            ++__first;
3585
            if (__grammar == ECMAScript && __first != __last && *__first == '?')
3586
            {
3587
                ++__first;
3588
                __push_loop(0, 1, __s, __mexp_begin, __mexp_end, false);
3589
            }
3590
            else
3591
                __push_loop(0, 1, __s, __mexp_begin, __mexp_end);
3592
            break;
3593
        case '{':
3594
            {
3595
                int __min;
3596
                _ForwardIterator __temp = __parse_DUP_COUNT(++__first, __last, __min);
3597
                if (__temp == __first)
3598
                    __throw_regex_error<regex_constants::error_badbrace>();
3599
                __first = __temp;
3600
                if (__first == __last)
3601
                    __throw_regex_error<regex_constants::error_brace>();
3602
                switch (*__first)
3603
                {
3604
                case '}':
3605
                    ++__first;
3606
                    if (__grammar == ECMAScript && __first != __last && *__first == '?')
3607
                    {
3608
                        ++__first;
3609
                        __push_loop(__min, __min, __s, __mexp_begin, __mexp_end, false);
3610
                    }
3611
                    else
3612
                        __push_loop(__min, __min, __s, __mexp_begin, __mexp_end);
3613
                    break;
3614
                case ',':
3615
                    ++__first;
3616
                    if (__first == __last)
3617
                        __throw_regex_error<regex_constants::error_badbrace>();
3618
                    if (*__first == '}')
3619
                    {
3620
                        ++__first;
3621
                        if (__grammar == ECMAScript && __first != __last && *__first == '?')
3622
                        {
3623
                            ++__first;
3624
                            __push_nongreedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3625
                        }
3626
                        else
3627
                            __push_greedy_inf_repeat(__min, __s, __mexp_begin, __mexp_end);
3628
                    }
3629
                    else
3630
                    {
3631
                        int __max = -1;
3632
                        __temp = __parse_DUP_COUNT(__first, __last, __max);
3633
                        if (__temp == __first)
3634
                            __throw_regex_error<regex_constants::error_brace>();
3635
                        __first = __temp;
3636
                        if (__first == __last || *__first != '}')
3637
                            __throw_regex_error<regex_constants::error_brace>();
3638
                        ++__first;
3639
                        if (__max < __min)
3640
                            __throw_regex_error<regex_constants::error_badbrace>();
3641
                        if (__grammar == ECMAScript && __first != __last && *__first == '?')
3642
                        {
3643
                            ++__first;
3644
                            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end, false);
3645
                        }
3646
                        else
3647
                            __push_loop(__min, __max, __s, __mexp_begin, __mexp_end);
3648
                    }
3649
                    break;
3650
                default:
3651
                    __throw_regex_error<regex_constants::error_badbrace>();
3652
                }
3653
            }
3654
            break;
3655
        }
3656
    }
3657
    return __first;
3658
}
3659

    
3660
template <class _CharT, class _Traits>
3661
template <class _ForwardIterator>
3662
_ForwardIterator
3663
basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
3664
                                                         _ForwardIterator __last)
3665
{
3666
    if (__first != __last && *__first == '[')
3667
    {
3668
        ++__first;
3669
        if (__first == __last)
3670
            __throw_regex_error<regex_constants::error_brack>();
3671
        bool __negate = false;
3672
        if (*__first == '^')
3673
        {
3674
            ++__first;
3675
            __negate = true;
3676
        }
3677
        __bracket_expression<_CharT, _Traits>* __ml = __start_matching_list(__negate);
3678
        // __ml owned by *this
3679
        if (__first == __last)
3680
            __throw_regex_error<regex_constants::error_brack>();
3681
        if ((__flags_ & 0x1F0) != ECMAScript && *__first == ']')
3682
        {
3683
            __ml->__add_char(']');
3684
            ++__first;
3685
        }
3686
        __first = __parse_follow_list(__first, __last, __ml);
3687
        if (__first == __last)
3688
            __throw_regex_error<regex_constants::error_brack>();
3689
        if (*__first == '-')
3690
        {
3691
            __ml->__add_char('-');
3692
            ++__first;
3693
        }
3694
        if (__first == __last || *__first != ']')
3695
            __throw_regex_error<regex_constants::error_brack>();
3696
        ++__first;
3697
    }
3698
    return __first;
3699
}
3700

    
3701
template <class _CharT, class _Traits>
3702
template <class _ForwardIterator>
3703
_ForwardIterator
3704
basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
3705
                                    _ForwardIterator __last,
3706
                                    __bracket_expression<_CharT, _Traits>* __ml)
3707
{
3708
    if (__first != __last)
3709
    {
3710
        while (true)
3711
        {
3712
            _ForwardIterator __temp = __parse_expression_term(__first, __last,
3713
                                                              __ml);
3714
            if (__temp == __first)
3715
                break;
3716
            __first = __temp;
3717
        }
3718
    }
3719
    return __first;
3720
}
3721

    
3722
template <class _CharT, class _Traits>
3723
template <class _ForwardIterator>
3724
_ForwardIterator
3725
basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
3726
                                    _ForwardIterator __last,
3727
                                    __bracket_expression<_CharT, _Traits>* __ml)
3728
{
3729
    if (__first != __last && *__first != ']')
3730
    {
3731
        _ForwardIterator __temp = _VSTD::next(__first);
3732
        basic_string<_CharT> __start_range;
3733
        if (__temp != __last && *__first == '[')
3734
        {
3735
            if (*__temp == '=')
3736
                return __parse_equivalence_class(++__temp, __last, __ml);
3737
            else if (*__temp == ':')
3738
                return __parse_character_class(++__temp, __last, __ml);
3739
            else if (*__temp == '.')
3740
                __first = __parse_collating_symbol(++__temp, __last, __start_range);
3741
        }
3742
        unsigned __grammar = __flags_ & 0x1F0;
3743
        if (__start_range.empty())
3744
        {
3745
            if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3746
            {
3747
                if (__grammar == ECMAScript)
3748
                    __first = __parse_class_escape(++__first, __last, __start_range, __ml);
3749
                else
3750
                    __first = __parse_awk_escape(++__first, __last, &__start_range);
3751
            }
3752
            else
3753
            {
3754
                __start_range = *__first;
3755
                ++__first;
3756
            }
3757
        }
3758
        if (__first != __last && *__first != ']')
3759
        {
3760
            __temp = _VSTD::next(__first);
3761
            if (__temp != __last && *__first == '-' && *__temp != ']')
3762
            {
3763
                // parse a range
3764
                basic_string<_CharT> __end_range;
3765
                __first = __temp;
3766
                ++__temp;
3767
                if (__temp != __last && *__first == '[' && *__temp == '.')
3768
                    __first = __parse_collating_symbol(++__temp, __last, __end_range);
3769
                else
3770
                {
3771
                    if ((__grammar == ECMAScript || __grammar == awk) && *__first == '\\')
3772
                    {
3773
                        if (__grammar == ECMAScript)
3774
                            __first = __parse_class_escape(++__first, __last,
3775
                                                           __end_range, __ml);
3776
                        else
3777
                            __first = __parse_awk_escape(++__first, __last,
3778
                                                         &__end_range);
3779
                    }
3780
                    else
3781
                    {
3782
                        __end_range = *__first;
3783
                        ++__first;
3784
                    }
3785
                }
3786
                __ml->__add_range(_VSTD::move(__start_range), _VSTD::move(__end_range));
3787
            }
3788
            else if (!__start_range.empty())
3789
            {
3790
                if (__start_range.size() == 1)
3791
                    __ml->__add_char(__start_range[0]);
3792
                else
3793
                    __ml->__add_digraph(__start_range[0], __start_range[1]);
3794
            }
3795
        }
3796
        else if (!__start_range.empty())
3797
        {
3798
            if (__start_range.size() == 1)
3799
                __ml->__add_char(__start_range[0]);
3800
            else
3801
                __ml->__add_digraph(__start_range[0], __start_range[1]);
3802
        }
3803
    }
3804
    return __first;
3805
}
3806

    
3807
template <class _CharT, class _Traits>
3808
template <class _ForwardIterator>
3809
_ForwardIterator
3810
basic_regex<_CharT, _Traits>::__parse_class_escape(_ForwardIterator __first,
3811
                          _ForwardIterator __last,
3812
                          basic_string<_CharT>& __str,
3813
                          __bracket_expression<_CharT, _Traits>* __ml)
3814
{
3815
    if (__first == __last)
3816
        __throw_regex_error<regex_constants::error_escape>();
3817
    switch (*__first)
3818
    {
3819
    case 0:
3820
        __str = *__first;
3821
        return ++__first;
3822
    case 'b':
3823
        __str = _CharT(8);
3824
        return ++__first;
3825
    case 'd':
3826
        __ml->__add_class(ctype_base::digit);
3827
        return ++__first;
3828
    case 'D':
3829
        __ml->__add_neg_class(ctype_base::digit);
3830
        return ++__first;
3831
    case 's':
3832
        __ml->__add_class(ctype_base::space);
3833
        return ++__first;
3834
    case 'S':
3835
        __ml->__add_neg_class(ctype_base::space);
3836
        return ++__first;
3837
    case 'w':
3838
        __ml->__add_class(ctype_base::alnum);
3839
        __ml->__add_char('_');
3840
        return ++__first;
3841
    case 'W':
3842
        __ml->__add_neg_class(ctype_base::alnum);
3843
        __ml->__add_neg_char('_');
3844
        return ++__first;
3845
    }
3846
    __first = __parse_character_escape(__first, __last, &__str);
3847
    return __first;
3848
}
3849

    
3850
template <class _CharT, class _Traits>
3851
template <class _ForwardIterator>
3852
_ForwardIterator
3853
basic_regex<_CharT, _Traits>::__parse_awk_escape(_ForwardIterator __first,
3854
                          _ForwardIterator __last,
3855
                          basic_string<_CharT>* __str)
3856
{
3857
    if (__first == __last)
3858
        __throw_regex_error<regex_constants::error_escape>();
3859
    switch (*__first)
3860
    {
3861
    case '\\':
3862
    case '"':
3863
    case '/':
3864
        if (__str)
3865
            *__str = *__first;
3866
        else
3867
            __push_char(*__first);
3868
        return ++__first;
3869
    case 'a':
3870
        if (__str)
3871
            *__str = _CharT(7);
3872
        else
3873
            __push_char(_CharT(7));
3874
        return ++__first;
3875
    case 'b':
3876
        if (__str)
3877
            *__str = _CharT(8);
3878
        else
3879
            __push_char(_CharT(8));
3880
        return ++__first;
3881
    case 'f':
3882
        if (__str)
3883
            *__str = _CharT(0xC);
3884
        else
3885
            __push_char(_CharT(0xC));
3886
        return ++__first;
3887
    case 'n':
3888
        if (__str)
3889
            *__str = _CharT(0xA);
3890
        else
3891
            __push_char(_CharT(0xA));
3892
        return ++__first;
3893
    case 'r':
3894
        if (__str)
3895
            *__str = _CharT(0xD);
3896
        else
3897
            __push_char(_CharT(0xD));
3898
        return ++__first;
3899
    case 't':
3900
        if (__str)
3901
            *__str = _CharT(0x9);
3902
        else
3903
            __push_char(_CharT(0x9));
3904
        return ++__first;
3905
    case 'v':
3906
        if (__str)
3907
            *__str = _CharT(0xB);
3908
        else
3909
            __push_char(_CharT(0xB));
3910
        return ++__first;
3911
    }
3912
    if ('0' <= *__first && *__first <= '7')
3913
    {
3914
        unsigned __val = *__first - '0';
3915
        if (++__first != __last && ('0' <= *__first && *__first <= '7'))
3916
        {
3917
            __val = 8 * __val + *__first - '0';
3918
            if (++__first != __last && ('0' <= *__first && *__first <= '7'))
3919
                __val = 8 * __val + *__first++ - '0';
3920
        }
3921
        if (__str)
3922
            *__str = _CharT(__val);
3923
        else
3924
            __push_char(_CharT(__val));
3925
    }
3926
    else
3927
        __throw_regex_error<regex_constants::error_escape>();
3928
    return __first;
3929
}
3930

    
3931
template <class _CharT, class _Traits>
3932
template <class _ForwardIterator>
3933
_ForwardIterator
3934
basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
3935
                                    _ForwardIterator __last,
3936
                                    __bracket_expression<_CharT, _Traits>* __ml)
3937
{
3938
    // Found [=
3939
    //   This means =] must exist
3940
    value_type _Equal_close[2] = {'=', ']'};
3941
    _ForwardIterator __temp = _VSTD::search(__first, __last, _Equal_close,
3942
                                                            _Equal_close+2);
3943
    if (__temp == __last)
3944
        __throw_regex_error<regex_constants::error_brack>();
3945
    // [__first, __temp) contains all text in [= ... =]
3946
    typedef typename _Traits::string_type string_type;
3947
    string_type __collate_name =
3948
        __traits_.lookup_collatename(__first, __temp);
3949
    if (__collate_name.empty())
3950
        __throw_regex_error<regex_constants::error_collate>();
3951
    string_type __equiv_name =
3952
        __traits_.transform_primary(__collate_name.begin(),
3953
                                    __collate_name.end());
3954
    if (!__equiv_name.empty())
3955
        __ml->__add_equivalence(__equiv_name);
3956
    else
3957
    {
3958
        switch (__collate_name.size())
3959
        {
3960
        case 1:
3961
            __ml->__add_char(__collate_name[0]);
3962
            break;
3963
        case 2:
3964
            __ml->__add_digraph(__collate_name[0], __collate_name[1]);
3965
            break;
3966
        default:
3967
            __throw_regex_error<regex_constants::error_collate>();
3968
        }
3969
    }
3970
    __first = _VSTD::next(__temp, 2);
3971
    return __first;
3972
}
3973

    
3974
template <class _CharT, class _Traits>
3975
template <class _ForwardIterator>
3976
_ForwardIterator
3977
basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
3978
                                    _ForwardIterator __last,
3979
                                    __bracket_expression<_CharT, _Traits>* __ml)
3980
{
3981
    // Found [:
3982
    //   This means :] must exist
3983
    value_type _Colon_close[2] = {':', ']'};
3984
    _ForwardIterator __temp = _VSTD::search(__first, __last, _Colon_close,
3985
                                                            _Colon_close+2);
3986
    if (__temp == __last)
3987
        __throw_regex_error<regex_constants::error_brack>();
3988
    // [__first, __temp) contains all text in [: ... :]
3989
    typedef typename _Traits::char_class_type char_class_type;
3990
    char_class_type __class_type =
3991
        __traits_.lookup_classname(__first, __temp, __flags_ & icase);
3992
    if (__class_type == 0)
3993
        __throw_regex_error<regex_constants::error_brack>();
3994
    __ml->__add_class(__class_type);
3995
    __first = _VSTD::next(__temp, 2);
3996
    return __first;
3997
}
3998

    
3999
template <class _CharT, class _Traits>
4000
template <class _ForwardIterator>
4001
_ForwardIterator
4002
basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
4003
                                                _ForwardIterator __last,
4004
                                                basic_string<_CharT>& __col_sym)
4005
{
4006
    // Found [.
4007
    //   This means .] must exist
4008
    value_type _Dot_close[2] = {'.', ']'};
4009
    _ForwardIterator __temp = _VSTD::search(__first, __last, _Dot_close,
4010
                                                            _Dot_close+2);
4011
    if (__temp == __last)
4012
        __throw_regex_error<regex_constants::error_brack>();
4013
    // [__first, __temp) contains all text in [. ... .]
4014
    __col_sym = __traits_.lookup_collatename(__first, __temp);
4015
    switch (__col_sym.size())
4016
    {
4017
    case 1:
4018
    case 2:
4019
        break;
4020
    default:
4021
        __throw_regex_error<regex_constants::error_collate>();
4022
    }
4023
    __first = _VSTD::next(__temp, 2);
4024
    return __first;
4025
}
4026

    
4027
template <class _CharT, class _Traits>
4028
template <class _ForwardIterator>
4029
_ForwardIterator
4030
basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
4031
                                                _ForwardIterator __last,
4032
                                                int& __c)
4033
{
4034
    if (__first != __last )
4035
    {
4036
        int __val = __traits_.value(*__first, 10);
4037
        if ( __val != -1 )
4038
        {
4039
            __c = __val;
4040
            for (++__first; 
4041
                 __first != __last && ( __val = __traits_.value(*__first, 10)) != -1;
4042
                 ++__first)
4043
            {
4044
                __c *= 10;
4045
                __c += __val;
4046
            }
4047
        }
4048
    }
4049
    return __first;
4050
}
4051

    
4052
template <class _CharT, class _Traits>
4053
template <class _ForwardIterator>
4054
_ForwardIterator
4055
basic_regex<_CharT, _Traits>::__parse_ecma_exp(_ForwardIterator __first,
4056
                                               _ForwardIterator __last)
4057
{
4058
    __owns_one_state<_CharT>* __sa = __end_;
4059
    _ForwardIterator __temp = __parse_alternative(__first, __last);
4060
    if (__temp == __first)
4061
        __push_empty();
4062
    __first = __temp;
4063
    while (__first != __last && *__first == '|')
4064
    {
4065
        __owns_one_state<_CharT>* __sb = __end_;
4066
        __temp = __parse_alternative(++__first, __last);
4067
        if (__temp == __first)
4068
            __push_empty();
4069
        __push_alternation(__sa, __sb);
4070
        __first = __temp;
4071
    }
4072
    return __first;
4073
}
4074

    
4075
template <class _CharT, class _Traits>
4076
template <class _ForwardIterator>
4077
_ForwardIterator
4078
basic_regex<_CharT, _Traits>::__parse_alternative(_ForwardIterator __first,
4079
                                                  _ForwardIterator __last)
4080
{
4081
    while (true)
4082
    {
4083
        _ForwardIterator __temp = __parse_term(__first, __last);
4084
        if (__temp == __first)
4085
            break;
4086
        __first = __temp;
4087
    }
4088
    return __first;
4089
}
4090

    
4091
template <class _CharT, class _Traits>
4092
template <class _ForwardIterator>
4093
_ForwardIterator
4094
basic_regex<_CharT, _Traits>::__parse_term(_ForwardIterator __first,
4095
                                           _ForwardIterator __last)
4096
{
4097
    _ForwardIterator __temp = __parse_assertion(__first, __last);
4098
    if (__temp == __first)
4099
    {
4100
        __owns_one_state<_CharT>* __e = __end_;
4101
        unsigned __mexp_begin = __marked_count_;
4102
        __temp = __parse_atom(__first, __last);
4103
        if (__temp != __first)
4104
            __first = __parse_ERE_dupl_symbol(__temp, __last, __e,
4105
                                              __mexp_begin+1, __marked_count_+1);
4106
    }
4107
    else
4108
        __first = __temp;
4109
    return __first;
4110
}
4111

    
4112
template <class _CharT, class _Traits>
4113
template <class _ForwardIterator>
4114
_ForwardIterator
4115
basic_regex<_CharT, _Traits>::__parse_assertion(_ForwardIterator __first,
4116
                                                _ForwardIterator __last)
4117
{
4118
    if (__first != __last)
4119
    {
4120
        switch (*__first)
4121
        {
4122
        case '^':
4123
            __push_l_anchor();
4124
            ++__first;
4125
            break;
4126
        case '$':
4127
            __push_r_anchor();
4128
            ++__first;
4129
            break;
4130
        case '\\':
4131
            {
4132
                _ForwardIterator __temp = _VSTD::next(__first);
4133
                if (__temp != __last)
4134
                {
4135
                    if (*__temp == 'b')
4136
                    {
4137
                        __push_word_boundary(false);
4138
                        __first = ++__temp;
4139
                    }
4140
                    else if (*__temp == 'B')
4141
                    {
4142
                        __push_word_boundary(true);
4143
                        __first = ++__temp;
4144
                    }
4145
                }
4146
            }
4147
            break;
4148
        case '(':
4149
            {
4150
                _ForwardIterator __temp = _VSTD::next(__first);
4151
                if (__temp != __last && *__temp == '?')
4152
                {
4153
                    if (++__temp != __last)
4154
                    {
4155
                        switch (*__temp)
4156
                        {
4157
                        case '=':
4158
                            {
4159
                                basic_regex __exp;
4160
                                __exp.__flags_ = __flags_;
4161
                                __temp = __exp.__parse(++__temp, __last);
4162
                                unsigned __mexp = __exp.__marked_count_;
4163
                                __push_lookahead(_VSTD::move(__exp), false, __marked_count_);
4164
                                __marked_count_ += __mexp;
4165
                                if (__temp == __last || *__temp != ')')
4166
                                    __throw_regex_error<regex_constants::error_paren>();
4167
                                __first = ++__temp;
4168
                            }
4169
                            break;
4170
                        case '!':
4171
                            {
4172
                                basic_regex __exp;
4173
                                __exp.__flags_ = __flags_;
4174
                                __temp = __exp.__parse(++__temp, __last);
4175
                                unsigned __mexp = __exp.__marked_count_;
4176
                                __push_lookahead(_VSTD::move(__exp), true, __marked_count_);
4177
                                __marked_count_ += __mexp;
4178
                                if (__temp == __last || *__temp != ')')
4179
                                    __throw_regex_error<regex_constants::error_paren>();
4180
                                __first = ++__temp;
4181
                            }
4182
                            break;
4183
                        }
4184
                    }
4185
                }
4186
            }
4187
            break;
4188
        }
4189
    }
4190
    return __first;
4191
}
4192

    
4193
template <class _CharT, class _Traits>
4194
template <class _ForwardIterator>
4195
_ForwardIterator
4196
basic_regex<_CharT, _Traits>::__parse_atom(_ForwardIterator __first,
4197
                                           _ForwardIterator __last)
4198
{
4199
    if (__first != __last)
4200
    {
4201
        switch (*__first)
4202
        {
4203
        case '.':
4204
            __push_match_any_but_newline();
4205
            ++__first;
4206
            break;
4207
        case '\\':
4208
            __first = __parse_atom_escape(__first, __last);
4209
            break;
4210
        case '[':
4211
            __first = __parse_bracket_expression(__first, __last);
4212
            break;
4213
        case '(':
4214
            {
4215
                ++__first;
4216
                if (__first == __last)
4217
                    __throw_regex_error<regex_constants::error_paren>();
4218
                _ForwardIterator __temp = _VSTD::next(__first);
4219
                if (__temp != __last && *__first == '?' && *__temp == ':')
4220
                {
4221
                    ++__open_count_;
4222
                    __first = __parse_ecma_exp(++__temp, __last);
4223
                    if (__first == __last || *__first != ')')
4224
                        __throw_regex_error<regex_constants::error_paren>();
4225
                    --__open_count_;
4226
                    ++__first;
4227
                }
4228
                else
4229
                {
4230
                    __push_begin_marked_subexpression();
4231
                    unsigned __temp_count = __marked_count_;
4232
                    ++__open_count_;
4233
                    __first = __parse_ecma_exp(__first, __last);
4234
                    if (__first == __last || *__first != ')')
4235
                        __throw_regex_error<regex_constants::error_paren>();
4236
                    __push_end_marked_subexpression(__temp_count);
4237
                    --__open_count_;
4238
                    ++__first;
4239
                }
4240
            }
4241
            break;
4242
        case '*':
4243
        case '+':
4244
        case '?':
4245
        case '{':
4246
            __throw_regex_error<regex_constants::error_badrepeat>();
4247
            break;
4248
        default:
4249
            __first = __parse_pattern_character(__first, __last);
4250
            break;
4251
        }
4252
    }
4253
    return __first;
4254
}
4255

    
4256
template <class _CharT, class _Traits>
4257
template <class _ForwardIterator>
4258
_ForwardIterator
4259
basic_regex<_CharT, _Traits>::__parse_atom_escape(_ForwardIterator __first,
4260
                                                  _ForwardIterator __last)
4261
{
4262
    if (__first != __last && *__first == '\\')
4263
    {
4264
        _ForwardIterator __t1 = _VSTD::next(__first);
4265
        _ForwardIterator __t2 = __parse_decimal_escape(__t1, __last);
4266
        if (__t2 != __t1)
4267
            __first = __t2;
4268
        else
4269
        {
4270
            __t2 = __parse_character_class_escape(__t1, __last);
4271
            if (__t2 != __t1)
4272
                __first = __t2;
4273
            else
4274
            {
4275
                __t2 = __parse_character_escape(__t1, __last);
4276
                if (__t2 != __t1)
4277
                    __first = __t2;
4278
            }
4279
        }
4280
    }
4281
    return __first;
4282
}
4283

    
4284
template <class _CharT, class _Traits>
4285
template <class _ForwardIterator>
4286
_ForwardIterator
4287
basic_regex<_CharT, _Traits>::__parse_decimal_escape(_ForwardIterator __first,
4288
                                                     _ForwardIterator __last)
4289
{
4290
    if (__first != __last)
4291
    {
4292
        if (*__first == '0')
4293
        {
4294
            __push_char(_CharT());
4295
            ++__first;
4296
        }
4297
        else if ('1' <= *__first && *__first <= '9')
4298
        {
4299
            unsigned __v = *__first - '0';
4300
            for (++__first; '0' <= *__first && *__first <= '9'; ++__first)
4301
                __v = 10 * __v + *__first - '0';
4302
            if (__v > mark_count())
4303
                __throw_regex_error<regex_constants::error_backref>();
4304
            __push_back_ref(__v);
4305
        }
4306
    }
4307
    return __first;
4308
}
4309

    
4310
template <class _CharT, class _Traits>
4311
template <class _ForwardIterator>
4312
_ForwardIterator
4313
basic_regex<_CharT, _Traits>::__parse_character_class_escape(_ForwardIterator __first,
4314
                                                             _ForwardIterator __last)
4315
{
4316
    if (__first != __last)
4317
    {
4318
        __bracket_expression<_CharT, _Traits>* __ml;
4319
        switch (*__first)
4320
        {
4321
        case 'd':
4322
            __ml = __start_matching_list(false);
4323
            __ml->__add_class(ctype_base::digit);
4324
            ++__first;
4325
            break;
4326
        case 'D':
4327
            __ml = __start_matching_list(true);
4328
            __ml->__add_class(ctype_base::digit);
4329
            ++__first;
4330
            break;
4331
        case 's':
4332
            __ml = __start_matching_list(false);
4333
            __ml->__add_class(ctype_base::space);
4334
            ++__first;
4335
            break;
4336
        case 'S':
4337
            __ml = __start_matching_list(true);
4338
            __ml->__add_class(ctype_base::space);
4339
            ++__first;
4340
            break;
4341
        case 'w':
4342
            __ml = __start_matching_list(false);
4343
            __ml->__add_class(ctype_base::alnum);
4344
            __ml->__add_char('_');
4345
            ++__first;
4346
            break;
4347
        case 'W':
4348
            __ml = __start_matching_list(true);
4349
            __ml->__add_class(ctype_base::alnum);
4350
            __ml->__add_char('_');
4351
            ++__first;
4352
            break;
4353
        }
4354
    }
4355
    return __first;
4356
}
4357

    
4358
template <class _CharT, class _Traits>
4359
template <class _ForwardIterator>
4360
_ForwardIterator
4361
basic_regex<_CharT, _Traits>::__parse_character_escape(_ForwardIterator __first,
4362
                                                    _ForwardIterator __last,
4363
                                                    basic_string<_CharT>* __str)
4364
{
4365
    if (__first != __last)
4366
    {
4367
        _ForwardIterator __t;
4368
        unsigned __sum = 0;
4369
        int __hd;
4370
        switch (*__first)
4371
        {
4372
        case 'f':
4373
            if (__str)
4374
                *__str = _CharT(0xC);
4375
            else
4376
                __push_char(_CharT(0xC));
4377
            ++__first;
4378
            break;
4379
        case 'n':
4380
            if (__str)
4381
                *__str = _CharT(0xA);
4382
            else
4383
                __push_char(_CharT(0xA));
4384
            ++__first;
4385
            break;
4386
        case 'r':
4387
            if (__str)
4388
                *__str = _CharT(0xD);
4389
            else
4390
                __push_char(_CharT(0xD));
4391
            ++__first;
4392
            break;
4393
        case 't':
4394
            if (__str)
4395
                *__str = _CharT(0x9);
4396
            else
4397
                __push_char(_CharT(0x9));
4398
            ++__first;
4399
            break;
4400
        case 'v':
4401
            if (__str)
4402
                *__str = _CharT(0xB);
4403
            else
4404
                __push_char(_CharT(0xB));
4405
            ++__first;
4406
            break;
4407
        case 'c':
4408
            if ((__t = _VSTD::next(__first)) != __last)
4409
            {
4410
                if (('A' <= *__t && *__t <= 'Z') || 
4411
                    ('a' <= *__t && *__t <= 'z'))
4412
                {
4413
                    if (__str)
4414
                        *__str = _CharT(*__t % 32);
4415
                    else
4416
                        __push_char(_CharT(*__t % 32));
4417
                    __first = ++__t;
4418
                }
4419
                else 
4420
                    __throw_regex_error<regex_constants::error_escape>();
4421
            }
4422
            else
4423
                __throw_regex_error<regex_constants::error_escape>();
4424
            break;
4425
        case 'u':
4426
            ++__first;
4427
            if (__first == __last)
4428
                __throw_regex_error<regex_constants::error_escape>();
4429
            __hd = __traits_.value(*__first, 16);
4430
            if (__hd == -1)
4431
                __throw_regex_error<regex_constants::error_escape>();
4432
            __sum = 16 * __sum + static_cast<unsigned>(__hd);
4433
            ++__first;
4434
            if (__first == __last)
4435
                __throw_regex_error<regex_constants::error_escape>();
4436
            __hd = __traits_.value(*__first, 16);
4437
            if (__hd == -1)
4438
                __throw_regex_error<regex_constants::error_escape>();
4439
            __sum = 16 * __sum + static_cast<unsigned>(__hd);
4440
            // drop through
4441
        case 'x':
4442
            ++__first;
4443
            if (__first == __last)
4444
                __throw_regex_error<regex_constants::error_escape>();
4445
            __hd = __traits_.value(*__first, 16);
4446
            if (__hd == -1)
4447
                __throw_regex_error<regex_constants::error_escape>();
4448
            __sum = 16 * __sum + static_cast<unsigned>(__hd);
4449
            ++__first;
4450
            if (__first == __last)
4451
                __throw_regex_error<regex_constants::error_escape>();
4452
            __hd = __traits_.value(*__first, 16);
4453
            if (__hd == -1)
4454
                __throw_regex_error<regex_constants::error_escape>();
4455
            __sum = 16 * __sum + static_cast<unsigned>(__hd);
4456
            if (__str)
4457
                *__str = _CharT(__sum);
4458
            else
4459
                __push_char(_CharT(__sum));
4460
            ++__first;
4461
            break;
4462
        case '0':
4463
            if (__str)
4464
                *__str = _CharT(0);
4465
            else
4466
                __push_char(_CharT(0));
4467
            ++__first;
4468
            break;
4469
        default:
4470
            if (*__first != '_' && !__traits_.isctype(*__first, ctype_base::alnum))
4471
            {
4472
                if (__str)
4473
                    *__str = *__first;
4474
                else
4475
                    __push_char(*__first);
4476
                ++__first;
4477
            }
4478
            else
4479
                __throw_regex_error<regex_constants::error_escape>();
4480
            break;
4481
        }
4482
    }
4483
    return __first;
4484
}
4485

    
4486
template <class _CharT, class _Traits>
4487
template <class _ForwardIterator>
4488
_ForwardIterator
4489
basic_regex<_CharT, _Traits>::__parse_pattern_character(_ForwardIterator __first,
4490
                                                        _ForwardIterator __last)
4491
{
4492
    if (__first != __last)
4493
    {
4494
        switch (*__first)
4495
        {
4496
        case '^':
4497
        case '$':
4498
        case '\\':
4499
        case '.':
4500
        case '*':
4501
        case '+':
4502
        case '?':
4503
        case '(':
4504
        case ')':
4505
        case '[':
4506
        case ']':
4507
        case '{':
4508
        case '}':
4509
        case '|':
4510
            break;
4511
        default:
4512
            __push_char(*__first);
4513
            ++__first;
4514
            break;
4515
        }
4516
    }
4517
    return __first;
4518
}
4519

    
4520
template <class _CharT, class _Traits>
4521
template <class _ForwardIterator>
4522
_ForwardIterator
4523
basic_regex<_CharT, _Traits>::__parse_grep(_ForwardIterator __first,
4524
                                           _ForwardIterator __last)
4525
{
4526
    __owns_one_state<_CharT>* __sa = __end_;
4527
    _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4528
    if (__t1 != __first)
4529
        __parse_basic_reg_exp(__first, __t1);
4530
    else
4531
        __push_empty();
4532
    __first = __t1;
4533
    if (__first != __last)
4534
        ++__first;
4535
    while (__first != __last)
4536
    {
4537
        __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4538
        __owns_one_state<_CharT>* __sb = __end_;
4539
        if (__t1 != __first)
4540
            __parse_basic_reg_exp(__first, __t1);
4541
        else
4542
            __push_empty();
4543
        __push_alternation(__sa, __sb);
4544
        __first = __t1;
4545
        if (__first != __last)
4546
            ++__first;
4547
    }
4548
    return __first;
4549
}
4550

    
4551
template <class _CharT, class _Traits>
4552
template <class _ForwardIterator>
4553
_ForwardIterator
4554
basic_regex<_CharT, _Traits>::__parse_egrep(_ForwardIterator __first,
4555
                                            _ForwardIterator __last)
4556
{
4557
    __owns_one_state<_CharT>* __sa = __end_;
4558
    _ForwardIterator __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4559
    if (__t1 != __first)
4560
        __parse_extended_reg_exp(__first, __t1);
4561
    else
4562
        __push_empty();
4563
    __first = __t1;
4564
    if (__first != __last)
4565
        ++__first;
4566
    while (__first != __last)
4567
    {
4568
        __t1 = _VSTD::find(__first, __last, _CharT('\n'));
4569
        __owns_one_state<_CharT>* __sb = __end_;
4570
        if (__t1 != __first)
4571
            __parse_extended_reg_exp(__first, __t1);
4572
        else
4573
            __push_empty();
4574
        __push_alternation(__sa, __sb);
4575
        __first = __t1;
4576
        if (__first != __last)
4577
            ++__first;
4578
    }
4579
    return __first;
4580
}
4581

    
4582
template <class _CharT, class _Traits>
4583
void
4584
basic_regex<_CharT, _Traits>::__push_loop(size_t __min, size_t __max,
4585
        __owns_one_state<_CharT>* __s, size_t __mexp_begin, size_t __mexp_end,
4586
        bool __greedy)
4587
{
4588
    unique_ptr<__empty_state<_CharT> > __e1(new __empty_state<_CharT>(__end_->first()));
4589
    __end_->first() = nullptr;
4590
    unique_ptr<__loop<_CharT> > __e2(new __loop<_CharT>(__loop_count_,
4591
                __s->first(), __e1.get(), __mexp_begin, __mexp_end, __greedy,
4592
                __min, __max));
4593
    __s->first() = nullptr;
4594
    __e1.release();
4595
    __end_->first() = new __repeat_one_loop<_CharT>(__e2.get());
4596
    __end_ = __e2->second();
4597
    __s->first() = __e2.release();
4598
    ++__loop_count_;
4599
}
4600

    
4601
template <class _CharT, class _Traits>
4602
void
4603
basic_regex<_CharT, _Traits>::__push_char(value_type __c)
4604
{
4605
    if (flags() & icase)
4606
        __end_->first() = new __match_char_icase<_CharT, _Traits>
4607
                                              (__traits_, __c, __end_->first());
4608
    else if (flags() & collate)
4609
        __end_->first() = new __match_char_collate<_CharT, _Traits>
4610
                                              (__traits_, __c, __end_->first());
4611
    else
4612
        __end_->first() = new __match_char<_CharT>(__c, __end_->first());
4613
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4614
}
4615

    
4616
template <class _CharT, class _Traits>
4617
void
4618
basic_regex<_CharT, _Traits>::__push_begin_marked_subexpression()
4619
{
4620
    if (!(__flags_ & nosubs))
4621
    {
4622
        __end_->first() =
4623
                new __begin_marked_subexpression<_CharT>(++__marked_count_,
4624
                                                         __end_->first());
4625
        __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4626
    }
4627
}
4628

    
4629
template <class _CharT, class _Traits>
4630
void
4631
basic_regex<_CharT, _Traits>::__push_end_marked_subexpression(unsigned __sub)
4632
{
4633
    if (!(__flags_ & nosubs))
4634
    {
4635
        __end_->first() =
4636
                new __end_marked_subexpression<_CharT>(__sub, __end_->first());
4637
        __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4638
    }
4639
}
4640

    
4641
template <class _CharT, class _Traits>
4642
void
4643
basic_regex<_CharT, _Traits>::__push_l_anchor()
4644
{
4645
    __end_->first() = new __l_anchor<_CharT>(__end_->first());
4646
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4647
}
4648

    
4649
template <class _CharT, class _Traits>
4650
void
4651
basic_regex<_CharT, _Traits>::__push_r_anchor()
4652
{
4653
    __end_->first() = new __r_anchor<_CharT>(__end_->first());
4654
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4655
}
4656

    
4657
template <class _CharT, class _Traits>
4658
void
4659
basic_regex<_CharT, _Traits>::__push_match_any()
4660
{
4661
    __end_->first() = new __match_any<_CharT>(__end_->first());
4662
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4663
}
4664

    
4665
template <class _CharT, class _Traits>
4666
void
4667
basic_regex<_CharT, _Traits>::__push_match_any_but_newline()
4668
{
4669
    __end_->first() = new __match_any_but_newline<_CharT>(__end_->first());
4670
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4671
}
4672

    
4673
template <class _CharT, class _Traits>
4674
void
4675
basic_regex<_CharT, _Traits>::__push_empty()
4676
{
4677
    __end_->first() = new __empty_state<_CharT>(__end_->first());
4678
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4679
}
4680

    
4681
template <class _CharT, class _Traits>
4682
void
4683
basic_regex<_CharT, _Traits>::__push_word_boundary(bool __invert)
4684
{
4685
    __end_->first() = new __word_boundary<_CharT, _Traits>(__traits_, __invert,
4686
                                                           __end_->first());
4687
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4688
}
4689

    
4690
template <class _CharT, class _Traits>
4691
void
4692
basic_regex<_CharT, _Traits>::__push_back_ref(int __i)
4693
{
4694
    if (flags() & icase)
4695
        __end_->first() = new __back_ref_icase<_CharT, _Traits>
4696
                                              (__traits_, __i, __end_->first());
4697
    else if (flags() & collate)
4698
        __end_->first() = new __back_ref_collate<_CharT, _Traits>
4699
                                              (__traits_, __i, __end_->first());
4700
    else
4701
        __end_->first() = new __back_ref<_CharT>(__i, __end_->first());
4702
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4703
}
4704

    
4705
template <class _CharT, class _Traits>
4706
void
4707
basic_regex<_CharT, _Traits>::__push_alternation(__owns_one_state<_CharT>* __sa,
4708
                                                 __owns_one_state<_CharT>* __ea)
4709
{
4710
    __sa->first() = new __alternate<_CharT>(
4711
                         static_cast<__owns_one_state<_CharT>*>(__sa->first()),
4712
                         static_cast<__owns_one_state<_CharT>*>(__ea->first()));
4713
    __ea->first() = nullptr;
4714
    __ea->first() = new __empty_state<_CharT>(__end_->first());
4715
    __end_->first() = nullptr;
4716
    __end_->first() = new __empty_non_own_state<_CharT>(__ea->first());
4717
    __end_ = static_cast<__owns_one_state<_CharT>*>(__ea->first());
4718
}
4719

    
4720
template <class _CharT, class _Traits>
4721
__bracket_expression<_CharT, _Traits>*
4722
basic_regex<_CharT, _Traits>::__start_matching_list(bool __negate)
4723
{
4724
    __bracket_expression<_CharT, _Traits>* __r =
4725
        new __bracket_expression<_CharT, _Traits>(__traits_, __end_->first(),
4726
                                                  __negate, __flags_ & icase,
4727
                                                  __flags_ & collate);
4728
    __end_->first() = __r;
4729
    __end_ = __r;
4730
    return __r;
4731
}
4732

    
4733
template <class _CharT, class _Traits>
4734
void
4735
basic_regex<_CharT, _Traits>::__push_lookahead(const basic_regex& __exp,
4736
                                               bool __invert,
4737
                                               unsigned __mexp)
4738
{
4739
    __end_->first() = new __lookahead<_CharT, _Traits>(__exp, __invert,
4740
                                                           __end_->first(), __mexp);
4741
    __end_ = static_cast<__owns_one_state<_CharT>*>(__end_->first());
4742
}
4743

    
4744
typedef basic_regex<char>    regex;
4745
typedef basic_regex<wchar_t> wregex;
4746

    
4747
// sub_match
4748

    
4749
template <class _BidirectionalIterator>
4750
class _LIBCPP_TYPE_VIS_ONLY sub_match
4751
    : public pair<_BidirectionalIterator, _BidirectionalIterator>
4752
{
4753
public:
4754
    typedef _BidirectionalIterator                              iterator;
4755
    typedef typename iterator_traits<iterator>::value_type      value_type;
4756
    typedef typename iterator_traits<iterator>::difference_type difference_type;
4757
    typedef basic_string<value_type>                            string_type;
4758

    
4759
    bool matched;
4760

    
4761
    _LIBCPP_INLINE_VISIBILITY
4762
    _LIBCPP_CONSTEXPR sub_match() : matched() {}
4763

    
4764
    _LIBCPP_INLINE_VISIBILITY
4765
    difference_type length() const
4766
        {return matched ? _VSTD::distance(this->first, this->second) : 0;}
4767
    _LIBCPP_INLINE_VISIBILITY
4768
    string_type str() const
4769
        {return matched ? string_type(this->first, this->second) : string_type();}
4770
    _LIBCPP_INLINE_VISIBILITY
4771
    operator string_type() const
4772
        {return str();}
4773

    
4774
    _LIBCPP_INLINE_VISIBILITY
4775
    int compare(const sub_match& __s) const
4776
        {return str().compare(__s.str());}
4777
    _LIBCPP_INLINE_VISIBILITY
4778
    int compare(const string_type& __s) const
4779
        {return str().compare(__s);}
4780
    _LIBCPP_INLINE_VISIBILITY
4781
    int compare(const value_type* __s) const
4782
        {return str().compare(__s);}
4783
};
4784

    
4785
typedef sub_match<const char*>             csub_match;
4786
typedef sub_match<const wchar_t*>          wcsub_match;
4787
typedef sub_match<string::const_iterator>  ssub_match;
4788
typedef sub_match<wstring::const_iterator> wssub_match;
4789

    
4790
template <class _BiIter>
4791
inline _LIBCPP_INLINE_VISIBILITY
4792
bool
4793
operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4794
{
4795
    return __x.compare(__y) == 0;
4796
}
4797

    
4798
template <class _BiIter>
4799
inline _LIBCPP_INLINE_VISIBILITY
4800
bool
4801
operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4802
{
4803
    return !(__x == __y);
4804
}
4805

    
4806
template <class _BiIter>
4807
inline _LIBCPP_INLINE_VISIBILITY
4808
bool
4809
operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4810
{
4811
    return __x.compare(__y) < 0;
4812
}
4813

    
4814
template <class _BiIter>
4815
inline _LIBCPP_INLINE_VISIBILITY
4816
bool
4817
operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4818
{
4819
    return !(__y < __x);
4820
}
4821

    
4822
template <class _BiIter>
4823
inline _LIBCPP_INLINE_VISIBILITY
4824
bool
4825
operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4826
{
4827
    return !(__x < __y);
4828
}
4829

    
4830
template <class _BiIter>
4831
inline _LIBCPP_INLINE_VISIBILITY
4832
bool
4833
operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
4834
{
4835
    return __y < __x;
4836
}
4837

    
4838
template <class _BiIter, class _ST, class _SA>
4839
inline _LIBCPP_INLINE_VISIBILITY
4840
bool
4841
operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4842
           const sub_match<_BiIter>& __y)
4843
{
4844
    return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) == 0;
4845
}
4846

    
4847
template <class _BiIter, class _ST, class _SA>
4848
inline _LIBCPP_INLINE_VISIBILITY
4849
bool
4850
operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4851
           const sub_match<_BiIter>& __y)
4852
{
4853
    return !(__x == __y);
4854
}
4855

    
4856
template <class _BiIter, class _ST, class _SA>
4857
inline _LIBCPP_INLINE_VISIBILITY
4858
bool
4859
operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4860
          const sub_match<_BiIter>& __y)
4861
{
4862
    return __y.compare(typename sub_match<_BiIter>::string_type(__x.data(), __x.size())) > 0;
4863
}
4864

    
4865
template <class _BiIter, class _ST, class _SA>
4866
inline _LIBCPP_INLINE_VISIBILITY
4867
bool
4868
operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4869
          const sub_match<_BiIter>& __y)
4870
{
4871
    return __y < __x;
4872
}
4873

    
4874
template <class _BiIter, class _ST, class _SA>
4875
inline _LIBCPP_INLINE_VISIBILITY
4876
bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4877
                const sub_match<_BiIter>& __y)
4878
{
4879
    return !(__x < __y);
4880
}
4881

    
4882
template <class _BiIter, class _ST, class _SA>
4883
inline _LIBCPP_INLINE_VISIBILITY
4884
bool
4885
operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
4886
           const sub_match<_BiIter>& __y)
4887
{
4888
    return !(__y < __x);
4889
}
4890

    
4891
template <class _BiIter, class _ST, class _SA>
4892
inline _LIBCPP_INLINE_VISIBILITY
4893
bool
4894
operator==(const sub_match<_BiIter>& __x,
4895
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4896
{
4897
    return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) == 0;
4898
}
4899

    
4900
template <class _BiIter, class _ST, class _SA>
4901
inline _LIBCPP_INLINE_VISIBILITY
4902
bool
4903
operator!=(const sub_match<_BiIter>& __x,
4904
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4905
{
4906
    return !(__x == __y);
4907
}
4908

    
4909
template <class _BiIter, class _ST, class _SA>
4910
inline _LIBCPP_INLINE_VISIBILITY
4911
bool
4912
operator<(const sub_match<_BiIter>& __x,
4913
          const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4914
{
4915
    return __x.compare(typename sub_match<_BiIter>::string_type(__y.data(), __y.size())) < 0;
4916
}
4917

    
4918
template <class _BiIter, class _ST, class _SA>
4919
inline _LIBCPP_INLINE_VISIBILITY
4920
bool operator>(const sub_match<_BiIter>& __x,
4921
               const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4922
{
4923
    return __y < __x;
4924
}
4925

    
4926
template <class _BiIter, class _ST, class _SA>
4927
inline _LIBCPP_INLINE_VISIBILITY
4928
bool
4929
operator>=(const sub_match<_BiIter>& __x,
4930
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4931
{
4932
    return !(__x < __y);
4933
}
4934

    
4935
template <class _BiIter, class _ST, class _SA>
4936
inline _LIBCPP_INLINE_VISIBILITY
4937
bool
4938
operator<=(const sub_match<_BiIter>& __x,
4939
           const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
4940
{
4941
    return !(__y < __x);
4942
}
4943

    
4944
template <class _BiIter>
4945
inline _LIBCPP_INLINE_VISIBILITY
4946
bool
4947
operator==(typename iterator_traits<_BiIter>::value_type const* __x,
4948
           const sub_match<_BiIter>& __y)
4949
{
4950
    return __y.compare(__x) == 0;
4951
}
4952

    
4953
template <class _BiIter>
4954
inline _LIBCPP_INLINE_VISIBILITY
4955
bool
4956
operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
4957
           const sub_match<_BiIter>& __y)
4958
{
4959
    return !(__x == __y);
4960
}
4961

    
4962
template <class _BiIter>
4963
inline _LIBCPP_INLINE_VISIBILITY
4964
bool
4965
operator<(typename iterator_traits<_BiIter>::value_type const* __x,
4966
          const sub_match<_BiIter>& __y)
4967
{
4968
    return __y.compare(__x) > 0;
4969
}
4970

    
4971
template <class _BiIter>
4972
inline _LIBCPP_INLINE_VISIBILITY
4973
bool
4974
operator>(typename iterator_traits<_BiIter>::value_type const* __x,
4975
          const sub_match<_BiIter>& __y)
4976
{
4977
    return __y < __x;
4978
}
4979

    
4980
template <class _BiIter>
4981
inline _LIBCPP_INLINE_VISIBILITY
4982
bool
4983
operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
4984
           const sub_match<_BiIter>& __y)
4985
{
4986
    return !(__x < __y);
4987
}
4988

    
4989
template <class _BiIter>
4990
inline _LIBCPP_INLINE_VISIBILITY
4991
bool
4992
operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
4993
           const sub_match<_BiIter>& __y)
4994
{
4995
    return !(__y < __x);
4996
}
4997

    
4998
template <class _BiIter>
4999
inline _LIBCPP_INLINE_VISIBILITY
5000
bool
5001
operator==(const sub_match<_BiIter>& __x,
5002
           typename iterator_traits<_BiIter>::value_type const* __y)
5003
{
5004
    return __x.compare(__y) == 0;
5005
}
5006

    
5007
template <class _BiIter>
5008
inline _LIBCPP_INLINE_VISIBILITY
5009
bool
5010
operator!=(const sub_match<_BiIter>& __x,
5011
           typename iterator_traits<_BiIter>::value_type const* __y)
5012
{
5013
    return !(__x == __y);
5014
}
5015

    
5016
template <class _BiIter>
5017
inline _LIBCPP_INLINE_VISIBILITY
5018
bool
5019
operator<(const sub_match<_BiIter>& __x,
5020
          typename iterator_traits<_BiIter>::value_type const* __y)
5021
{
5022
    return __x.compare(__y) < 0;
5023
}
5024

    
5025
template <class _BiIter>
5026
inline _LIBCPP_INLINE_VISIBILITY
5027
bool
5028
operator>(const sub_match<_BiIter>& __x,
5029
          typename iterator_traits<_BiIter>::value_type const* __y)
5030
{
5031
    return __y < __x;
5032
}
5033

    
5034
template <class _BiIter>
5035
inline _LIBCPP_INLINE_VISIBILITY
5036
bool
5037
operator>=(const sub_match<_BiIter>& __x,
5038
           typename iterator_traits<_BiIter>::value_type const* __y)
5039
{
5040
    return !(__x < __y);
5041
}
5042

    
5043
template <class _BiIter>
5044
inline _LIBCPP_INLINE_VISIBILITY
5045
bool
5046
operator<=(const sub_match<_BiIter>& __x,
5047
           typename iterator_traits<_BiIter>::value_type const* __y)
5048
{
5049
    return !(__y < __x);
5050
}
5051

    
5052
template <class _BiIter>
5053
inline _LIBCPP_INLINE_VISIBILITY
5054
bool
5055
operator==(typename iterator_traits<_BiIter>::value_type const& __x,
5056
           const sub_match<_BiIter>& __y)
5057
{
5058
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5059
    return __y.compare(string_type(1, __x)) == 0;
5060
}
5061

    
5062
template <class _BiIter>
5063
inline _LIBCPP_INLINE_VISIBILITY
5064
bool
5065
operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
5066
           const sub_match<_BiIter>& __y)
5067
{
5068
    return !(__x == __y);
5069
}
5070

    
5071
template <class _BiIter>
5072
inline _LIBCPP_INLINE_VISIBILITY
5073
bool
5074
operator<(typename iterator_traits<_BiIter>::value_type const& __x,
5075
          const sub_match<_BiIter>& __y)
5076
{
5077
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5078
    return __y.compare(string_type(1, __x)) > 0;
5079
}
5080

    
5081
template <class _BiIter>
5082
inline _LIBCPP_INLINE_VISIBILITY
5083
bool
5084
operator>(typename iterator_traits<_BiIter>::value_type const& __x,
5085
          const sub_match<_BiIter>& __y)
5086
{
5087
    return __y < __x;
5088
}
5089

    
5090
template <class _BiIter>
5091
inline _LIBCPP_INLINE_VISIBILITY
5092
bool
5093
operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
5094
           const sub_match<_BiIter>& __y)
5095
{
5096
    return !(__x < __y);
5097
}
5098

    
5099
template <class _BiIter>
5100
inline _LIBCPP_INLINE_VISIBILITY
5101
bool
5102
operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
5103
           const sub_match<_BiIter>& __y)
5104
{
5105
    return !(__y < __x);
5106
}
5107

    
5108
template <class _BiIter>
5109
inline _LIBCPP_INLINE_VISIBILITY
5110
bool
5111
operator==(const sub_match<_BiIter>& __x,
5112
           typename iterator_traits<_BiIter>::value_type const& __y)
5113
{
5114
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5115
    return __x.compare(string_type(1, __y)) == 0;
5116
}
5117

    
5118
template <class _BiIter>
5119
inline _LIBCPP_INLINE_VISIBILITY
5120
bool
5121
operator!=(const sub_match<_BiIter>& __x,
5122
           typename iterator_traits<_BiIter>::value_type const& __y)
5123
{
5124
    return !(__x == __y);
5125
}
5126

    
5127
template <class _BiIter>
5128
inline _LIBCPP_INLINE_VISIBILITY
5129
bool
5130
operator<(const sub_match<_BiIter>& __x,
5131
          typename iterator_traits<_BiIter>::value_type const& __y)
5132
{
5133
    typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
5134
    return __x.compare(string_type(1, __y)) < 0;
5135
}
5136

    
5137
template <class _BiIter>
5138
inline _LIBCPP_INLINE_VISIBILITY
5139
bool
5140
operator>(const sub_match<_BiIter>& __x,
5141
          typename iterator_traits<_BiIter>::value_type const& __y)
5142
{
5143
    return __y < __x;
5144
}
5145

    
5146
template <class _BiIter>
5147
inline _LIBCPP_INLINE_VISIBILITY
5148
bool
5149
operator>=(const sub_match<_BiIter>& __x,
5150
           typename iterator_traits<_BiIter>::value_type const& __y)
5151
{
5152
    return !(__x < __y);
5153
}
5154

    
5155
template <class _BiIter>
5156
inline _LIBCPP_INLINE_VISIBILITY
5157
bool
5158
operator<=(const sub_match<_BiIter>& __x,
5159
           typename iterator_traits<_BiIter>::value_type const& __y)
5160
{
5161
    return !(__y < __x);
5162
}
5163

    
5164
template <class _CharT, class _ST, class _BiIter>
5165
inline _LIBCPP_INLINE_VISIBILITY
5166
basic_ostream<_CharT, _ST>&
5167
operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
5168
{
5169
    return __os << __m.str();
5170
}
5171

    
5172
template <class _BidirectionalIterator, class _Allocator>
5173
class _LIBCPP_TYPE_VIS_ONLY match_results
5174
{
5175
public:
5176
    typedef _Allocator                                        allocator_type;
5177
    typedef sub_match<_BidirectionalIterator>                 value_type;
5178
private:
5179
    typedef vector<value_type, allocator_type>                __container_type;
5180

    
5181
    __container_type  __matches_;
5182
    value_type __unmatched_;
5183
    value_type __prefix_;
5184
    value_type __suffix_;
5185
    bool       __ready_;
5186
public:
5187
    _BidirectionalIterator __position_start_;
5188
    typedef const value_type&                                 const_reference;
5189
    typedef value_type&                                       reference;
5190
    typedef typename __container_type::const_iterator         const_iterator;
5191
    typedef const_iterator                                    iterator;
5192
    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
5193
    typedef typename allocator_traits<allocator_type>::size_type size_type;
5194
    typedef typename iterator_traits<_BidirectionalIterator>::value_type char_type;
5195
    typedef basic_string<char_type>                           string_type;
5196

    
5197
    // construct/copy/destroy:
5198
    explicit match_results(const allocator_type& __a = allocator_type());
5199
//    match_results(const match_results&) = default;
5200
//    match_results& operator=(const match_results&) = default;
5201
//    match_results(match_results&& __m) = default;
5202
//    match_results& operator=(match_results&& __m) = default;
5203
//    ~match_results() = default;
5204

    
5205
    _LIBCPP_INLINE_VISIBILITY
5206
    bool ready() const {return __ready_;}
5207

    
5208
    // size:
5209
    _LIBCPP_INLINE_VISIBILITY
5210
    size_type size() const {return __matches_.size();}
5211
    _LIBCPP_INLINE_VISIBILITY
5212
    size_type max_size() const {return __matches_.max_size();}
5213
    _LIBCPP_INLINE_VISIBILITY
5214
    bool empty() const {return size() == 0;}
5215

    
5216
    // element access:
5217
    _LIBCPP_INLINE_VISIBILITY
5218
    difference_type length(size_type __sub = 0) const
5219
        {return (*this)[__sub].length();}
5220
    _LIBCPP_INLINE_VISIBILITY
5221
    difference_type position(size_type __sub = 0) const
5222
        {return _VSTD::distance(__position_start_, (*this)[__sub].first);}
5223
    _LIBCPP_INLINE_VISIBILITY
5224
    string_type str(size_type __sub = 0) const
5225
        {return (*this)[__sub].str();}
5226
    _LIBCPP_INLINE_VISIBILITY
5227
    const_reference operator[](size_type __n) const
5228
        {return __n < __matches_.size() ? __matches_[__n] : __unmatched_;}
5229

    
5230
    _LIBCPP_INLINE_VISIBILITY
5231
    const_reference prefix() const {return __prefix_;}
5232
    _LIBCPP_INLINE_VISIBILITY
5233
    const_reference suffix() const {return __suffix_;}
5234

    
5235
    _LIBCPP_INLINE_VISIBILITY
5236
    const_iterator begin() const {return empty() ? __matches_.end() : __matches_.begin();}
5237
    _LIBCPP_INLINE_VISIBILITY
5238
    const_iterator end() const {return __matches_.end();}
5239
    _LIBCPP_INLINE_VISIBILITY
5240
    const_iterator cbegin() const {return empty() ? __matches_.end() : __matches_.begin();}
5241
    _LIBCPP_INLINE_VISIBILITY
5242
    const_iterator cend() const {return __matches_.end();}
5243

    
5244
    // format:
5245
    template <class _OutputIter>
5246
        _OutputIter
5247
        format(_OutputIter __out, const char_type* __fmt_first,
5248
               const char_type* __fmt_last,
5249
               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
5250
    template <class _OutputIter, class _ST, class _SA>
5251
        _LIBCPP_INLINE_VISIBILITY
5252
        _OutputIter
5253
        format(_OutputIter __out, const basic_string<char_type, _ST, _SA>& __fmt,
5254
               regex_constants::match_flag_type __flags = regex_constants::format_default) const
5255
            {return format(__out, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
5256
    template <class _ST, class _SA>
5257
        _LIBCPP_INLINE_VISIBILITY
5258
        basic_string<char_type, _ST, _SA>
5259
        format(const basic_string<char_type, _ST, _SA>& __fmt,
5260
               regex_constants::match_flag_type __flags = regex_constants::format_default) const
5261
        {
5262
            basic_string<char_type, _ST, _SA> __r;
5263
            format(back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
5264
                   __flags);
5265
            return __r;
5266
        }
5267
    _LIBCPP_INLINE_VISIBILITY
5268
    string_type
5269
        format(const char_type* __fmt,
5270
               regex_constants::match_flag_type __flags = regex_constants::format_default) const
5271
        {
5272
            string_type __r;
5273
            format(back_inserter(__r), __fmt,
5274
                   __fmt + char_traits<char_type>::length(__fmt), __flags);
5275
            return __r;
5276
        }
5277

    
5278
    // allocator:
5279
    _LIBCPP_INLINE_VISIBILITY
5280
    allocator_type get_allocator() const {return __matches_.get_allocator();}
5281

    
5282
    // swap:
5283
    void swap(match_results& __m);
5284

    
5285
    template <class _Bp, class _Ap>
5286
        _LIBCPP_INLINE_VISIBILITY
5287
        void __assign(_BidirectionalIterator __f, _BidirectionalIterator __l,
5288
                      const match_results<_Bp, _Ap>& __m, bool __no_update_pos)
5289
    {
5290
        _Bp __mf = __m.prefix().first;
5291
        __matches_.resize(__m.size());
5292
        for (size_type __i = 0; __i < __matches_.size(); ++__i)
5293
        {
5294
            __matches_[__i].first = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].first));
5295
            __matches_[__i].second = _VSTD::next(__f, _VSTD::distance(__mf, __m[__i].second));
5296
            __matches_[__i].matched = __m[__i].matched;
5297
        }
5298
        __unmatched_.first   = __l;
5299
        __unmatched_.second  = __l;
5300
        __unmatched_.matched = false;
5301
        __prefix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().first));
5302
        __prefix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.prefix().second));
5303
        __prefix_.matched = __m.prefix().matched;
5304
        __suffix_.first = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().first));
5305
        __suffix_.second = _VSTD::next(__f, _VSTD::distance(__mf, __m.suffix().second));
5306
        __suffix_.matched = __m.suffix().matched;
5307
        if (!__no_update_pos)
5308
            __position_start_ = __prefix_.first;
5309
        __ready_ = __m.ready();
5310
    }
5311

    
5312
private:
5313
    void __init(unsigned __s,
5314
                _BidirectionalIterator __f, _BidirectionalIterator __l,
5315
                bool __no_update_pos = false);
5316

    
5317
    template <class, class> friend class basic_regex;
5318

    
5319
    template <class _Bp, class _Ap, class _Cp, class _Tp>
5320
    friend
5321
    bool
5322
    regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Cp, _Tp>&,
5323
                regex_constants::match_flag_type);
5324

    
5325
    template <class _Bp, class _Ap>
5326
    friend
5327
    bool
5328
    operator==(const match_results<_Bp, _Ap>&, const match_results<_Bp, _Ap>&);
5329

    
5330
    template <class, class> friend class __lookahead;
5331
};
5332

    
5333
template <class _BidirectionalIterator, class _Allocator>
5334
match_results<_BidirectionalIterator, _Allocator>::match_results(
5335
        const allocator_type& __a)
5336
    : __matches_(__a),
5337
      __unmatched_(),
5338
      __prefix_(),
5339
      __suffix_(),
5340
      __ready_(false),
5341
      __position_start_()
5342
{
5343
}
5344

    
5345
template <class _BidirectionalIterator, class _Allocator>
5346
void
5347
match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
5348
                         _BidirectionalIterator __f, _BidirectionalIterator __l,
5349
                         bool __no_update_pos)
5350
{
5351
    __unmatched_.first   = __l;
5352
    __unmatched_.second  = __l;
5353
    __unmatched_.matched = false;
5354
    __matches_.assign(__s, __unmatched_);
5355
    __prefix_.first      = __f;
5356
    __prefix_.second     = __f;
5357
    __prefix_.matched    = false;
5358
    __suffix_ = __unmatched_;
5359
    if (!__no_update_pos)
5360
        __position_start_ = __prefix_.first;
5361
    __ready_ = true;
5362
}
5363

    
5364
template <class _BidirectionalIterator, class _Allocator>
5365
template <class _OutputIter>
5366
_OutputIter
5367
match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __out,
5368
        const char_type* __fmt_first, const char_type* __fmt_last,
5369
        regex_constants::match_flag_type __flags) const
5370
{
5371
    if (__flags & regex_constants::format_sed)
5372
    {
5373
        for (; __fmt_first != __fmt_last; ++__fmt_first)
5374
        {
5375
            if (*__fmt_first == '&')
5376
                __out = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5377
                                   __out);
5378
            else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
5379
            {
5380
                ++__fmt_first;
5381
                if ('0' <= *__fmt_first && *__fmt_first <= '9')
5382
                {
5383
                    size_t __i = *__fmt_first - '0';
5384
                    __out = _VSTD::copy(__matches_[__i].first,
5385
                                       __matches_[__i].second, __out);
5386
                }
5387
                else
5388
                {
5389
                    *__out = *__fmt_first;
5390
                    ++__out;
5391
                }
5392
            }
5393
            else
5394
            {
5395
                *__out = *__fmt_first;
5396
                ++__out;
5397
            }
5398
        }
5399
    }
5400
    else
5401
    {
5402
        for (; __fmt_first != __fmt_last; ++__fmt_first)
5403
        {
5404
            if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
5405
            {
5406
                switch (__fmt_first[1])
5407
                {
5408
                case '$':
5409
                    *__out = *++__fmt_first;
5410
                    ++__out;
5411
                    break;
5412
                case '&':
5413
                    ++__fmt_first;
5414
                    __out = _VSTD::copy(__matches_[0].first, __matches_[0].second,
5415
                                       __out);
5416
                    break;
5417
                case '`':
5418
                    ++__fmt_first;
5419
                    __out = _VSTD::copy(__prefix_.first, __prefix_.second, __out);
5420
                    break;
5421
                case '\'':
5422
                    ++__fmt_first;
5423
                    __out = _VSTD::copy(__suffix_.first, __suffix_.second, __out);
5424
                    break;
5425
                default:
5426
                    if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5427
                    {
5428
                        ++__fmt_first;
5429
                        size_t __i = *__fmt_first - '0';
5430
                        if (__fmt_first + 1 != __fmt_last &&
5431
                            '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
5432
                        {
5433
                            ++__fmt_first;
5434
                            __i = 10 * __i + *__fmt_first - '0';
5435
                        }
5436
                        __out = _VSTD::copy(__matches_[__i].first,
5437
                                           __matches_[__i].second, __out);
5438
                    }
5439
                    else
5440
                    {
5441
                        *__out = *__fmt_first;
5442
                        ++__out;
5443
                    }
5444
                    break;
5445
                }
5446
            }
5447
            else
5448
            {
5449
                *__out = *__fmt_first;
5450
                ++__out;
5451
            }
5452
        }
5453
    }
5454
    return __out;
5455
}
5456

    
5457
template <class _BidirectionalIterator, class _Allocator>
5458
void
5459
match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
5460
{
5461
    using _VSTD::swap;
5462
    swap(__matches_, __m.__matches_);
5463
    swap(__unmatched_, __m.__unmatched_);
5464
    swap(__prefix_, __m.__prefix_);
5465
    swap(__suffix_, __m.__suffix_);
5466
    swap(__position_start_, __m.__position_start_);
5467
    swap(__ready_, __m.__ready_);
5468
}
5469

    
5470
typedef match_results<const char*>             cmatch;
5471
typedef match_results<const wchar_t*>          wcmatch;
5472
typedef match_results<string::const_iterator>  smatch;
5473
typedef match_results<wstring::const_iterator> wsmatch;
5474

    
5475
template <class _BidirectionalIterator, class _Allocator>
5476
bool
5477
operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
5478
           const match_results<_BidirectionalIterator, _Allocator>& __y)
5479
{
5480
    if (__x.__ready_ != __y.__ready_)
5481
        return false;
5482
    if (!__x.__ready_)
5483
        return true;
5484
    return __x.__matches_ == __y.__matches_ &&
5485
           __x.__prefix_ == __y.__prefix_ &&
5486
           __x.__suffix_ == __y.__suffix_;
5487
}
5488

    
5489
template <class _BidirectionalIterator, class _Allocator>
5490
inline _LIBCPP_INLINE_VISIBILITY
5491
bool
5492
operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
5493
           const match_results<_BidirectionalIterator, _Allocator>& __y)
5494
{
5495
    return !(__x == __y);
5496
}
5497

    
5498
template <class _BidirectionalIterator, class _Allocator>
5499
inline _LIBCPP_INLINE_VISIBILITY
5500
void
5501
swap(match_results<_BidirectionalIterator, _Allocator>& __x,
5502
     match_results<_BidirectionalIterator, _Allocator>& __y)
5503
{
5504
    __x.swap(__y);
5505
}
5506

    
5507
// regex_search
5508

    
5509
template <class _CharT, class _Traits>
5510
template <class _Allocator>
5511
bool
5512
basic_regex<_CharT, _Traits>::__match_at_start_ecma(
5513
        const _CharT* __first, const _CharT* __last,
5514
        match_results<const _CharT*, _Allocator>& __m,
5515
        regex_constants::match_flag_type __flags, bool __at_first) const
5516
{
5517
    vector<__state> __states;
5518
    __node* __st = __start_.get();
5519
    if (__st)
5520
    {
5521
        sub_match<const _CharT*> __unmatched;
5522
        __unmatched.first   = __last;
5523
        __unmatched.second  = __last;
5524
        __unmatched.matched = false;
5525

    
5526
        __states.push_back(__state());
5527
        __states.back().__do_ = 0;
5528
        __states.back().__first_ = __first;
5529
        __states.back().__current_ = __first;
5530
        __states.back().__last_ = __last;
5531
        __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5532
        __states.back().__loop_data_.resize(__loop_count());
5533
        __states.back().__node_ = __st;
5534
        __states.back().__flags_ = __flags;
5535
        __states.back().__at_first_ = __at_first;
5536
        do
5537
        {
5538
            __state& __s = __states.back();
5539
            if (__s.__node_)
5540
                __s.__node_->__exec(__s);
5541
            switch (__s.__do_)
5542
            {
5543
            case __state::__end_state:
5544
                __m.__matches_[0].first = __first;
5545
                __m.__matches_[0].second = _VSTD::next(__first, __s.__current_ - __first);
5546
                __m.__matches_[0].matched = true;
5547
                for (unsigned __i = 0; __i < __s.__sub_matches_.size(); ++__i)
5548
                    __m.__matches_[__i+1] = __s.__sub_matches_[__i];
5549
                return true;
5550
            case __state::__accept_and_consume:
5551
            case __state::__repeat:
5552
            case __state::__accept_but_not_consume:
5553
                break;
5554
            case __state::__split:
5555
                {
5556
                __state __snext = __s;
5557
                __s.__node_->__exec_split(true, __s);
5558
                __snext.__node_->__exec_split(false, __snext);
5559
                __states.push_back(_VSTD::move(__snext));
5560
                }
5561
                break;
5562
            case __state::__reject:
5563
                __states.pop_back();
5564
                break;
5565
            default:
5566
                __throw_regex_error<regex_constants::__re_err_unknown>();
5567
                break;
5568

    
5569
            }
5570
        } while (!__states.empty());
5571
    }
5572
    return false;
5573
}
5574

    
5575
template <class _CharT, class _Traits>
5576
template <class _Allocator>
5577
bool
5578
basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
5579
        const _CharT* __first, const _CharT* __last,
5580
        match_results<const _CharT*, _Allocator>& __m,
5581
        regex_constants::match_flag_type __flags, bool __at_first) const
5582
{
5583
    deque<__state> __states;
5584
    ptrdiff_t __highest_j = 0;
5585
    ptrdiff_t _Np = _VSTD::distance(__first, __last);
5586
    __node* __st = __start_.get();
5587
    if (__st)
5588
    {
5589
        __states.push_back(__state());
5590
        __states.back().__do_ = 0;
5591
        __states.back().__first_ = __first;
5592
        __states.back().__current_ = __first;
5593
        __states.back().__last_ = __last;
5594
        __states.back().__loop_data_.resize(__loop_count());
5595
        __states.back().__node_ = __st;
5596
        __states.back().__flags_ = __flags;
5597
        __states.back().__at_first_ = __at_first;
5598
        bool __matched = false;
5599
        do
5600
        {
5601
            __state& __s = __states.back();
5602
            if (__s.__node_)
5603
                __s.__node_->__exec(__s);
5604
            switch (__s.__do_)
5605
            {
5606
            case __state::__end_state:
5607
                if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5608
                    __highest_j = __s.__current_ - __s.__first_;
5609
                __matched = true;
5610
                if (__highest_j == _Np)
5611
                    __states.clear();
5612
                else
5613
                    __states.pop_back();
5614
                break;
5615
            case __state::__consume_input:
5616
                break;
5617
            case __state::__accept_and_consume:
5618
                __states.push_front(_VSTD::move(__s));
5619
                __states.pop_back();
5620
                break;
5621
            case __state::__repeat:
5622
            case __state::__accept_but_not_consume:
5623
                break;
5624
            case __state::__split:
5625
                {
5626
                __state __snext = __s;
5627
                __s.__node_->__exec_split(true, __s);
5628
                __snext.__node_->__exec_split(false, __snext);
5629
                __states.push_back(_VSTD::move(__snext));
5630
                }
5631
                break;
5632
            case __state::__reject:
5633
                __states.pop_back();
5634
                break;
5635
            default:
5636
                __throw_regex_error<regex_constants::__re_err_unknown>();
5637
                break;
5638
            }
5639
        } while (!__states.empty());
5640
        if (__matched)
5641
        {
5642
            __m.__matches_[0].first = __first;
5643
            __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5644
            __m.__matches_[0].matched = true;
5645
            return true;
5646
        }
5647
    }
5648
    return false;
5649
}
5650

    
5651
template <class _CharT, class _Traits>
5652
template <class _Allocator>
5653
bool
5654
basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
5655
        const _CharT* __first, const _CharT* __last,
5656
        match_results<const _CharT*, _Allocator>& __m,
5657
        regex_constants::match_flag_type __flags, bool __at_first) const
5658
{
5659
    vector<__state> __states;
5660
    __state __best_state;
5661
    ptrdiff_t __j = 0;
5662
    ptrdiff_t __highest_j = 0;
5663
    ptrdiff_t _Np = _VSTD::distance(__first, __last);
5664
    __node* __st = __start_.get();
5665
    if (__st)
5666
    {
5667
        sub_match<const _CharT*> __unmatched;
5668
        __unmatched.first   = __last;
5669
        __unmatched.second  = __last;
5670
        __unmatched.matched = false;
5671

    
5672
        __states.push_back(__state());
5673
        __states.back().__do_ = 0;
5674
        __states.back().__first_ = __first;
5675
        __states.back().__current_ = __first;
5676
        __states.back().__last_ = __last;
5677
        __states.back().__sub_matches_.resize(mark_count(), __unmatched);
5678
        __states.back().__loop_data_.resize(__loop_count());
5679
        __states.back().__node_ = __st;
5680
        __states.back().__flags_ = __flags;
5681
        __states.back().__at_first_ = __at_first;
5682
        const _CharT* __current = __first;
5683
        bool __matched = false;
5684
        do
5685
        {
5686
            __state& __s = __states.back();
5687
            if (__s.__node_)
5688
                __s.__node_->__exec(__s);
5689
            switch (__s.__do_)
5690
            {
5691
            case __state::__end_state:
5692
                if (!__matched || __highest_j < __s.__current_ - __s.__first_)
5693
                {
5694
                    __highest_j = __s.__current_ - __s.__first_;
5695
                    __best_state = __s;
5696
                }
5697
                __matched = true;
5698
                if (__highest_j == _Np)
5699
                    __states.clear();
5700
                else
5701
                    __states.pop_back();
5702
                break;
5703
            case __state::__accept_and_consume:
5704
                __j += __s.__current_ - __current;
5705
                __current = __s.__current_;
5706
                break;
5707
            case __state::__repeat:
5708
            case __state::__accept_but_not_consume:
5709
                break;
5710
            case __state::__split:
5711
                {
5712
                __state __snext = __s;
5713
                __s.__node_->__exec_split(true, __s);
5714
                __snext.__node_->__exec_split(false, __snext);
5715
                __states.push_back(_VSTD::move(__snext));
5716
                }
5717
                break;
5718
            case __state::__reject:
5719
                __states.pop_back();
5720
                break;
5721
            default:
5722
                __throw_regex_error<regex_constants::__re_err_unknown>();
5723
                break;
5724
            }
5725
        } while (!__states.empty());
5726
        if (__matched)
5727
        {
5728
            __m.__matches_[0].first = __first;
5729
            __m.__matches_[0].second = _VSTD::next(__first, __highest_j);
5730
            __m.__matches_[0].matched = true;
5731
            for (unsigned __i = 0; __i < __best_state.__sub_matches_.size(); ++__i)
5732
                __m.__matches_[__i+1] = __best_state.__sub_matches_[__i];
5733
            return true;
5734
        }
5735
    }
5736
    return false;
5737
}
5738

    
5739
template <class _CharT, class _Traits>
5740
template <class _Allocator>
5741
bool
5742
basic_regex<_CharT, _Traits>::__match_at_start(
5743
        const _CharT* __first, const _CharT* __last,
5744
        match_results<const _CharT*, _Allocator>& __m,
5745
        regex_constants::match_flag_type __flags, bool __at_first) const
5746
{
5747
    if ((__flags_ & 0x1F0) == ECMAScript)
5748
        return __match_at_start_ecma(__first, __last, __m, __flags, __at_first);
5749
    if (mark_count() == 0)
5750
        return __match_at_start_posix_nosubs(__first, __last, __m, __flags, __at_first);
5751
    return __match_at_start_posix_subs(__first, __last, __m, __flags, __at_first);
5752
}
5753

    
5754
template <class _CharT, class _Traits>
5755
template <class _Allocator>
5756
bool
5757
basic_regex<_CharT, _Traits>::__search(
5758
        const _CharT* __first, const _CharT* __last,
5759
        match_results<const _CharT*, _Allocator>& __m,
5760
        regex_constants::match_flag_type __flags) const
5761
{
5762
    __m.__init(1 + mark_count(), __first, __last,
5763
                                    __flags & regex_constants::__no_update_pos);
5764
    if (__match_at_start(__first, __last, __m, __flags, 
5765
                                    !(__flags & regex_constants::__no_update_pos)))
5766
    {
5767
        __m.__prefix_.second = __m[0].first;
5768
        __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5769
        __m.__suffix_.first = __m[0].second;
5770
        __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5771
        return true;
5772
    }
5773
    if (__first != __last && !(__flags & regex_constants::match_continuous))
5774
    {
5775
        __flags |= regex_constants::match_prev_avail;
5776
        for (++__first; __first != __last; ++__first)
5777
        {
5778
            __m.__matches_.assign(__m.size(), __m.__unmatched_);
5779
            if (__match_at_start(__first, __last, __m, __flags, false))
5780
            {
5781
                __m.__prefix_.second = __m[0].first;
5782
                __m.__prefix_.matched = __m.__prefix_.first != __m.__prefix_.second;
5783
                __m.__suffix_.first = __m[0].second;
5784
                __m.__suffix_.matched = __m.__suffix_.first != __m.__suffix_.second;
5785
                return true;
5786
            }
5787
            __m.__matches_.assign(__m.size(), __m.__unmatched_);
5788
        }
5789
    }
5790
    __m.__matches_.clear();
5791
    return false;
5792
}
5793

    
5794
template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5795
inline _LIBCPP_INLINE_VISIBILITY
5796
bool
5797
regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5798
             match_results<_BidirectionalIterator, _Allocator>& __m,
5799
             const basic_regex<_CharT, _Traits>& __e,
5800
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5801
{
5802
    int __offset = (__flags & regex_constants::match_prev_avail) ? 1 : 0;
5803
    basic_string<_CharT> __s(_VSTD::prev(__first, __offset), __last);
5804
    match_results<const _CharT*> __mc;
5805
    bool __r = __e.__search(__s.data() + __offset, __s.data() + __s.size(), __mc, __flags);
5806
    __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5807
    return __r;
5808
}
5809

    
5810
template <class _Iter, class _Allocator, class _CharT, class _Traits>
5811
inline _LIBCPP_INLINE_VISIBILITY
5812
bool
5813
regex_search(__wrap_iter<_Iter> __first,
5814
             __wrap_iter<_Iter> __last,
5815
             match_results<__wrap_iter<_Iter>, _Allocator>& __m,
5816
             const basic_regex<_CharT, _Traits>& __e,
5817
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5818
{
5819
    match_results<const _CharT*> __mc;
5820
    bool __r = __e.__search(__first.base(), __last.base(), __mc, __flags);
5821
    __m.__assign(__first, __last, __mc, __flags & regex_constants::__no_update_pos);
5822
    return __r;
5823
}
5824

    
5825
template <class _Allocator, class _CharT, class _Traits>
5826
inline _LIBCPP_INLINE_VISIBILITY
5827
bool
5828
regex_search(const _CharT* __first, const _CharT* __last,
5829
             match_results<const _CharT*, _Allocator>& __m,
5830
             const basic_regex<_CharT, _Traits>& __e,
5831
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5832
{
5833
    return __e.__search(__first, __last, __m, __flags);
5834
}
5835

    
5836
template <class _BidirectionalIterator, class _CharT, class _Traits>
5837
inline _LIBCPP_INLINE_VISIBILITY
5838
bool
5839
regex_search(_BidirectionalIterator __first, _BidirectionalIterator __last,
5840
             const basic_regex<_CharT, _Traits>& __e,
5841
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5842
{
5843
    basic_string<_CharT> __s(__first, __last);
5844
    match_results<const _CharT*> __mc;
5845
    return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5846
}
5847

    
5848
template <class _CharT, class _Traits>
5849
inline _LIBCPP_INLINE_VISIBILITY
5850
bool
5851
regex_search(const _CharT* __first, const _CharT* __last,
5852
             const basic_regex<_CharT, _Traits>& __e,
5853
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5854
{
5855
    match_results<const _CharT*> __mc;
5856
    return __e.__search(__first, __last, __mc, __flags);
5857
}
5858

    
5859
template <class _CharT, class _Allocator, class _Traits>
5860
inline _LIBCPP_INLINE_VISIBILITY
5861
bool
5862
regex_search(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
5863
             const basic_regex<_CharT, _Traits>& __e,
5864
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5865
{
5866
    return __e.__search(__str, __str + _Traits::length(__str), __m, __flags);
5867
}
5868

    
5869
template <class _CharT, class _Traits>
5870
inline _LIBCPP_INLINE_VISIBILITY
5871
bool
5872
regex_search(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
5873
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5874
{
5875
    match_results<const _CharT*> __m;
5876
    return _VSTD::regex_search(__str, __m, __e, __flags);
5877
}
5878

    
5879
template <class _ST, class _SA, class _CharT, class _Traits>
5880
inline _LIBCPP_INLINE_VISIBILITY
5881
bool
5882
regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5883
             const basic_regex<_CharT, _Traits>& __e,
5884
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5885
{
5886
    match_results<const _CharT*> __mc;
5887
    return __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5888
}
5889

    
5890
template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5891
inline _LIBCPP_INLINE_VISIBILITY
5892
bool
5893
regex_search(const basic_string<_CharT, _ST, _SA>& __s,
5894
             match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5895
             const basic_regex<_CharT, _Traits>& __e,
5896
             regex_constants::match_flag_type __flags = regex_constants::match_default)
5897
{
5898
    match_results<const _CharT*> __mc;
5899
    bool __r = __e.__search(__s.data(), __s.data() + __s.size(), __mc, __flags);
5900
    __m.__assign(__s.begin(), __s.end(), __mc, __flags & regex_constants::__no_update_pos);
5901
    return __r;
5902
}
5903

    
5904
#if _LIBCPP_STD_VER > 11
5905
template <class _ST, class _SA, class _Ap, class _Cp, class _Tp>
5906
bool
5907
regex_search(const basic_string<_Cp, _ST, _SA>&& __s,
5908
             match_results<typename basic_string<_Cp, _ST, _SA>::const_iterator, _Ap>&,
5909
             const basic_regex<_Cp, _Tp>& __e,
5910
             regex_constants::match_flag_type __flags = regex_constants::match_default) = delete; 
5911
#endif
5912

    
5913
// regex_match
5914

    
5915
template <class _BidirectionalIterator, class _Allocator, class _CharT, class _Traits>
5916
bool
5917
regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
5918
            match_results<_BidirectionalIterator, _Allocator>& __m,
5919
            const basic_regex<_CharT, _Traits>& __e,
5920
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5921
{
5922
    bool __r = _VSTD::regex_search(__first, __last, __m, __e,
5923
                            __flags | regex_constants::match_continuous);
5924
    if (__r)
5925
    {
5926
        __r = !__m.suffix().matched;
5927
        if (!__r)
5928
            __m.__matches_.clear();
5929
    }
5930
    return __r;
5931
}
5932

    
5933
template <class _BidirectionalIterator, class _CharT, class _Traits>
5934
inline _LIBCPP_INLINE_VISIBILITY
5935
bool
5936
regex_match(_BidirectionalIterator __first, _BidirectionalIterator __last,
5937
            const basic_regex<_CharT, _Traits>& __e,
5938
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5939
{
5940
    match_results<_BidirectionalIterator> __m;
5941
    return _VSTD::regex_match(__first, __last, __m, __e, __flags);
5942
}
5943

    
5944
template <class _CharT, class _Allocator, class _Traits>
5945
inline _LIBCPP_INLINE_VISIBILITY
5946
bool
5947
regex_match(const _CharT* __str, match_results<const _CharT*, _Allocator>& __m,
5948
            const basic_regex<_CharT, _Traits>& __e,
5949
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5950
{
5951
    return _VSTD::regex_match(__str, __str + _Traits::length(__str), __m, __e, __flags);
5952
}
5953

    
5954
template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5955
inline _LIBCPP_INLINE_VISIBILITY
5956
bool
5957
regex_match(const basic_string<_CharT, _ST, _SA>& __s,
5958
            match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5959
            const basic_regex<_CharT, _Traits>& __e,
5960
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5961
{
5962
    return _VSTD::regex_match(__s.begin(), __s.end(), __m, __e, __flags);
5963
}
5964

    
5965
#if _LIBCPP_STD_VER > 11
5966
template <class _ST, class _SA, class _Allocator, class _CharT, class _Traits>
5967
inline _LIBCPP_INLINE_VISIBILITY
5968
bool
5969
regex_match(const basic_string<_CharT, _ST, _SA>&& __s,
5970
            match_results<typename basic_string<_CharT, _ST, _SA>::const_iterator, _Allocator>& __m,
5971
            const basic_regex<_CharT, _Traits>& __e,
5972
            regex_constants::match_flag_type __flags = regex_constants::match_default) = delete; 
5973
#endif
5974

    
5975
template <class _CharT, class _Traits>
5976
inline _LIBCPP_INLINE_VISIBILITY
5977
bool
5978
regex_match(const _CharT* __str, const basic_regex<_CharT, _Traits>& __e,
5979
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5980
{
5981
    return _VSTD::regex_match(__str, __str + _Traits::length(__str), __e, __flags);
5982
}
5983

    
5984
template <class _ST, class _SA, class _CharT, class _Traits>
5985
inline _LIBCPP_INLINE_VISIBILITY
5986
bool
5987
regex_match(const basic_string<_CharT, _ST, _SA>& __s,
5988
            const basic_regex<_CharT, _Traits>& __e,
5989
            regex_constants::match_flag_type __flags = regex_constants::match_default)
5990
{
5991
    return _VSTD::regex_match(__s.begin(), __s.end(), __e, __flags);
5992
}
5993

    
5994
// regex_iterator
5995

    
5996
template <class _BidirectionalIterator,
5997
          class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
5998
          class _Traits = regex_traits<_CharT> >
5999
class _LIBCPP_TYPE_VIS_ONLY regex_iterator
6000
{
6001
public:
6002
    typedef basic_regex<_CharT, _Traits>          regex_type;
6003
    typedef match_results<_BidirectionalIterator> value_type;
6004
    typedef ptrdiff_t                             difference_type;
6005
    typedef const value_type*                     pointer;
6006
    typedef const value_type&                     reference;
6007
    typedef forward_iterator_tag                  iterator_category;
6008

    
6009
private:
6010
    _BidirectionalIterator           __begin_;
6011
    _BidirectionalIterator           __end_;
6012
    const regex_type*                __pregex_;
6013
    regex_constants::match_flag_type __flags_;
6014
    value_type                       __match_;
6015

    
6016
public:
6017
    regex_iterator();
6018
    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6019
                   const regex_type& __re,
6020
                   regex_constants::match_flag_type __m
6021
                                              = regex_constants::match_default);
6022
#if _LIBCPP_STD_VER > 11
6023
    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6024
                   const regex_type&& __re,
6025
                   regex_constants::match_flag_type __m 
6026
                                     = regex_constants::match_default) = delete;
6027
#endif
6028

    
6029
    bool operator==(const regex_iterator& __x) const;
6030
    _LIBCPP_INLINE_VISIBILITY
6031
    bool operator!=(const regex_iterator& __x) const {return !(*this == __x);}
6032

    
6033
    _LIBCPP_INLINE_VISIBILITY
6034
    reference operator*() const {return  __match_;}
6035
    _LIBCPP_INLINE_VISIBILITY
6036
    pointer operator->() const  {return &__match_;}
6037

    
6038
    regex_iterator& operator++();
6039
    _LIBCPP_INLINE_VISIBILITY
6040
    regex_iterator operator++(int)
6041
    {
6042
        regex_iterator __t(*this);
6043
        ++(*this);
6044
        return __t;
6045
    }
6046
};
6047

    
6048
template <class _BidirectionalIterator, class _CharT, class _Traits>
6049
regex_iterator<_BidirectionalIterator, _CharT, _Traits>::regex_iterator()
6050
    : __begin_(), __end_(), __pregex_(nullptr), __flags_(), __match_()
6051
{
6052
}
6053

    
6054
template <class _BidirectionalIterator, class _CharT, class _Traits>
6055
regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6056
    regex_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6057
                   const regex_type& __re, regex_constants::match_flag_type __m)
6058
    : __begin_(__a),
6059
      __end_(__b),
6060
      __pregex_(&__re),
6061
      __flags_(__m)
6062
{
6063
    _VSTD::regex_search(__begin_, __end_, __match_, *__pregex_, __flags_);
6064
}
6065

    
6066
template <class _BidirectionalIterator, class _CharT, class _Traits>
6067
bool
6068
regex_iterator<_BidirectionalIterator, _CharT, _Traits>::
6069
    operator==(const regex_iterator& __x) const
6070
{
6071
    if (__match_.empty() && __x.__match_.empty())
6072
        return true;
6073
    if (__match_.empty() || __x.__match_.empty())
6074
        return false;
6075
    return __begin_ == __x.__begin_       &&
6076
           __end_ == __x.__end_           &&
6077
           __pregex_ == __x.__pregex_     &&
6078
           __flags_ == __x.__flags_       &&
6079
           __match_[0] == __x.__match_[0];
6080
}
6081

    
6082
template <class _BidirectionalIterator, class _CharT, class _Traits>
6083
regex_iterator<_BidirectionalIterator, _CharT, _Traits>&
6084
regex_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6085
{
6086
    __flags_ |= regex_constants::__no_update_pos;
6087
    _BidirectionalIterator __start = __match_[0].second;
6088
    if (__match_.empty())
6089
    {
6090
        if (__start == __end_)
6091
        {
6092
            __match_ = value_type();
6093
            return *this;
6094
        }
6095
        else if (_VSTD::regex_search(__start, __end_, __match_, *__pregex_,
6096
                                    __flags_ | regex_constants::match_not_null |
6097
                                    regex_constants::match_continuous))
6098
            return *this;
6099
        else
6100
            ++__start;
6101
    }
6102
    __flags_ |= regex_constants::match_prev_avail;
6103
    if (!_VSTD::regex_search(__start, __end_, __match_, *__pregex_, __flags_))
6104
        __match_ = value_type();
6105
    return *this;
6106
}
6107

    
6108
typedef regex_iterator<const char*>             cregex_iterator;
6109
typedef regex_iterator<const wchar_t*>          wcregex_iterator;
6110
typedef regex_iterator<string::const_iterator>  sregex_iterator;
6111
typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
6112

    
6113
// regex_token_iterator
6114

    
6115
template <class _BidirectionalIterator,
6116
          class _CharT = typename iterator_traits<_BidirectionalIterator>::value_type,
6117
          class _Traits = regex_traits<_CharT> >
6118
class _LIBCPP_TYPE_VIS_ONLY regex_token_iterator
6119
{
6120
public:
6121
    typedef basic_regex<_CharT, _Traits>      regex_type;
6122
    typedef sub_match<_BidirectionalIterator> value_type;
6123
    typedef ptrdiff_t                         difference_type;
6124
    typedef const value_type*                 pointer;
6125
    typedef const value_type&                 reference;
6126
    typedef forward_iterator_tag              iterator_category;
6127

    
6128
private:
6129
    typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Position;
6130

    
6131
    _Position         __position_;
6132
    const value_type* __result_;
6133
    value_type        __suffix_;
6134
    ptrdiff_t         _N_;
6135
    vector<int>       __subs_;
6136

    
6137
public:
6138
    regex_token_iterator();
6139
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6140
                         const regex_type& __re, int __submatch = 0,
6141
                         regex_constants::match_flag_type __m =
6142
                                                regex_constants::match_default);
6143
#if _LIBCPP_STD_VER > 11
6144
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6145
                         const regex_type&& __re, int __submatch = 0,
6146
                         regex_constants::match_flag_type __m =
6147
                                       regex_constants::match_default) = delete;
6148
#endif
6149

    
6150
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6151
                         const regex_type& __re, const vector<int>& __submatches,
6152
                         regex_constants::match_flag_type __m =
6153
                                                regex_constants::match_default);
6154
#if _LIBCPP_STD_VER > 11
6155
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6156
                         const regex_type&& __re, const vector<int>& __submatches,
6157
                         regex_constants::match_flag_type __m =
6158
                                     regex_constants::match_default) = delete;
6159
#endif
6160

    
6161
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6162
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6163
                         const regex_type& __re,
6164
                         initializer_list<int> __submatches,
6165
                         regex_constants::match_flag_type __m =
6166
                                                regex_constants::match_default);
6167

    
6168
#if _LIBCPP_STD_VER > 11
6169
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6170
                         const regex_type&& __re,
6171
                         initializer_list<int> __submatches,
6172
                         regex_constants::match_flag_type __m =
6173
                                       regex_constants::match_default) = delete;
6174
#endif
6175
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6176
    template <size_t _Np>
6177
        regex_token_iterator(_BidirectionalIterator __a,
6178
                             _BidirectionalIterator __b,
6179
                             const regex_type& __re,
6180
                             const int (&__submatches)[_Np],
6181
                             regex_constants::match_flag_type __m =
6182
                                                regex_constants::match_default);
6183
#if _LIBCPP_STD_VER > 11
6184
    template <std::size_t _Np>
6185
        regex_token_iterator(_BidirectionalIterator __a,
6186
                             _BidirectionalIterator __b,
6187
                             const regex_type&& __re,
6188
                             const int (&__submatches)[_Np],
6189
                             regex_constants::match_flag_type __m =
6190
                                      regex_constants::match_default) = delete;
6191
#endif
6192

    
6193
    regex_token_iterator(const regex_token_iterator&);
6194
    regex_token_iterator& operator=(const regex_token_iterator&);
6195

    
6196
    bool operator==(const regex_token_iterator& __x) const;
6197
    _LIBCPP_INLINE_VISIBILITY
6198
    bool operator!=(const regex_token_iterator& __x) const {return !(*this == __x);}
6199

    
6200
    _LIBCPP_INLINE_VISIBILITY
6201
    const value_type& operator*() const {return *__result_;}
6202
    _LIBCPP_INLINE_VISIBILITY
6203
    const value_type* operator->() const {return __result_;}
6204

    
6205
    regex_token_iterator& operator++();
6206
    _LIBCPP_INLINE_VISIBILITY
6207
    regex_token_iterator operator++(int)
6208
    {
6209
        regex_token_iterator __t(*this);
6210
        ++(*this);
6211
        return __t;
6212
    }
6213

    
6214
private:
6215
    void __init(_BidirectionalIterator __a, _BidirectionalIterator __b);
6216
    void __establish_result () {
6217
        if (__subs_[_N_] == -1)
6218
            __result_ = &__position_->prefix();
6219
        else
6220
            __result_ = &(*__position_)[__subs_[_N_]];
6221
        }       
6222
};
6223

    
6224
template <class _BidirectionalIterator, class _CharT, class _Traits>
6225
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6226
    regex_token_iterator()
6227
    : __result_(nullptr),
6228
      __suffix_(),
6229
      _N_(0)
6230
{
6231
}
6232

    
6233
template <class _BidirectionalIterator, class _CharT, class _Traits>
6234
void
6235
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6236
    __init(_BidirectionalIterator __a, _BidirectionalIterator __b)
6237
{
6238
    if (__position_ != _Position())
6239
        __establish_result ();
6240
    else if (__subs_[_N_] == -1)
6241
    {
6242
        __suffix_.matched = true;
6243
        __suffix_.first = __a;
6244
        __suffix_.second = __b;
6245
        __result_ = &__suffix_;
6246
    }
6247
    else
6248
        __result_ = nullptr;
6249
}
6250

    
6251
template <class _BidirectionalIterator, class _CharT, class _Traits>
6252
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6253
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6254
                         const regex_type& __re, int __submatch,
6255
                         regex_constants::match_flag_type __m)
6256
    : __position_(__a, __b, __re, __m),
6257
      _N_(0),
6258
      __subs_(1, __submatch)
6259
{
6260
    __init(__a, __b);
6261
}
6262

    
6263
template <class _BidirectionalIterator, class _CharT, class _Traits>
6264
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6265
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6266
                         const regex_type& __re, const vector<int>& __submatches,
6267
                         regex_constants::match_flag_type __m)
6268
    : __position_(__a, __b, __re, __m),
6269
      _N_(0),
6270
      __subs_(__submatches)
6271
{
6272
    __init(__a, __b);
6273
}
6274

    
6275
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6276

    
6277
template <class _BidirectionalIterator, class _CharT, class _Traits>
6278
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6279
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6280
                         const regex_type& __re,
6281
                         initializer_list<int> __submatches,
6282
                         regex_constants::match_flag_type __m)
6283
    : __position_(__a, __b, __re, __m),
6284
      _N_(0),
6285
      __subs_(__submatches)
6286
{
6287
    __init(__a, __b);
6288
}
6289

    
6290
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6291

    
6292
template <class _BidirectionalIterator, class _CharT, class _Traits>
6293
template <size_t _Np>
6294
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6295
    regex_token_iterator(_BidirectionalIterator __a, _BidirectionalIterator __b,
6296
                             const regex_type& __re,
6297
                             const int (&__submatches)[_Np],
6298
                             regex_constants::match_flag_type __m)
6299
    : __position_(__a, __b, __re, __m),
6300
      _N_(0),
6301
      __subs_(__submatches, __submatches + _Np)
6302
{
6303
    __init(__a, __b);
6304
}
6305

    
6306
template <class _BidirectionalIterator, class _CharT, class _Traits>
6307
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6308
    regex_token_iterator(const regex_token_iterator& __x)
6309
    : __position_(__x.__position_),
6310
      __result_(__x.__result_),
6311
      __suffix_(__x.__suffix_),
6312
      _N_(__x._N_),
6313
      __subs_(__x.__subs_)
6314
{
6315
    if (__x.__result_ == &__x.__suffix_)
6316
        __result_ = &__suffix_;
6317
    else if ( __result_ != nullptr )
6318
        __establish_result ();
6319
}
6320

    
6321
template <class _BidirectionalIterator, class _CharT, class _Traits>
6322
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6323
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6324
    operator=(const regex_token_iterator& __x)
6325
{
6326
    if (this != &__x)
6327
    {
6328
        __position_ = __x.__position_;
6329
        if (__x.__result_ == &__x.__suffix_)
6330
            __result_ = &__suffix_;
6331
        else
6332
            __result_ = __x.__result_;
6333
        __suffix_ = __x.__suffix_;
6334
        _N_ = __x._N_;
6335
        __subs_ = __x.__subs_;
6336

    
6337
        if ( __result_ != nullptr && __result_ != &__suffix_ )
6338
            __establish_result();
6339
    }
6340
    return *this;
6341
}
6342

    
6343
template <class _BidirectionalIterator, class _CharT, class _Traits>
6344
bool
6345
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::
6346
    operator==(const regex_token_iterator& __x) const
6347
{
6348
    if (__result_ == nullptr && __x.__result_ == nullptr)
6349
        return true;
6350
    if (__result_ == &__suffix_ && __x.__result_ == &__x.__suffix_ &&
6351
            __suffix_ == __x.__suffix_)
6352
        return true;
6353
    if (__result_ == nullptr || __x.__result_ == nullptr)
6354
        return false;
6355
    if (__result_ == &__suffix_ || __x.__result_ == &__x.__suffix_)
6356
        return false;
6357
    return __position_ == __x.__position_ && _N_ == __x._N_ &&
6358
           __subs_ == __x.__subs_;
6359
}
6360

    
6361
template <class _BidirectionalIterator, class _CharT, class _Traits>
6362
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>&
6363
regex_token_iterator<_BidirectionalIterator, _CharT, _Traits>::operator++()
6364
{
6365
    _Position __prev = __position_;
6366
    if (__result_ == &__suffix_)
6367
        __result_ = nullptr;
6368
    else if (_N_ + 1 < __subs_.size())
6369
    {
6370
        ++_N_;
6371
        __establish_result();
6372
    }
6373
    else
6374
    {
6375
        _N_ = 0;
6376
        ++__position_;
6377
        if (__position_ != _Position())
6378
            __establish_result();
6379
        else
6380
        {
6381
            if (_VSTD::find(__subs_.begin(), __subs_.end(), -1) != __subs_.end()
6382
                && __prev->suffix().length() != 0)
6383
            {
6384
                __suffix_.matched = true;
6385
                __suffix_.first = __prev->suffix().first;
6386
                __suffix_.second = __prev->suffix().second;
6387
                __result_ = &__suffix_;
6388
            }
6389
            else
6390
                __result_ = nullptr;
6391
        }
6392
    }
6393
    return *this;
6394
}
6395

    
6396
typedef regex_token_iterator<const char*>             cregex_token_iterator;
6397
typedef regex_token_iterator<const wchar_t*>          wcregex_token_iterator;
6398
typedef regex_token_iterator<string::const_iterator>  sregex_token_iterator;
6399
typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
6400

    
6401
// regex_replace
6402

    
6403
template <class _OutputIterator, class _BidirectionalIterator,
6404
          class _Traits, class _CharT>
6405
_OutputIterator
6406
regex_replace(_OutputIterator __out,
6407
              _BidirectionalIterator __first, _BidirectionalIterator __last,
6408
              const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6409
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6410
{
6411
    typedef regex_iterator<_BidirectionalIterator, _CharT, _Traits> _Iter;
6412
    _Iter __i(__first, __last, __e, __flags);
6413
    _Iter __eof;
6414
    if (__i == __eof)
6415
    {
6416
        if (!(__flags & regex_constants::format_no_copy))
6417
            __out = _VSTD::copy(__first, __last, __out);
6418
    }
6419
    else
6420
    {
6421
        sub_match<_BidirectionalIterator> __lm;
6422
        for (size_t __len = char_traits<_CharT>::length(__fmt); __i != __eof; ++__i)
6423
        {
6424
            if (!(__flags & regex_constants::format_no_copy))
6425
                __out = _VSTD::copy(__i->prefix().first, __i->prefix().second, __out);
6426
            __out = __i->format(__out, __fmt, __fmt + __len, __flags);
6427
            __lm = __i->suffix();
6428
            if (__flags & regex_constants::format_first_only)
6429
                break;
6430
        }
6431
        if (!(__flags & regex_constants::format_no_copy))
6432
            __out = _VSTD::copy(__lm.first, __lm.second, __out);
6433
    }
6434
    return __out;
6435
}
6436

    
6437
template <class _OutputIterator, class _BidirectionalIterator,
6438
          class _Traits, class _CharT, class _ST, class _SA>
6439
inline _LIBCPP_INLINE_VISIBILITY
6440
_OutputIterator
6441
regex_replace(_OutputIterator __out,
6442
              _BidirectionalIterator __first, _BidirectionalIterator __last,
6443
              const basic_regex<_CharT, _Traits>& __e,
6444
              const basic_string<_CharT, _ST, _SA>& __fmt,
6445
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6446
{
6447
    return _VSTD::regex_replace(__out, __first, __last, __e, __fmt.c_str(), __flags);
6448
}
6449

    
6450
template <class _Traits, class _CharT, class _ST, class _SA, class _FST,
6451
          class _FSA>
6452
inline _LIBCPP_INLINE_VISIBILITY
6453
basic_string<_CharT, _ST, _SA>
6454
regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6455
              const basic_regex<_CharT, _Traits>& __e,
6456
              const basic_string<_CharT, _FST, _FSA>& __fmt,
6457
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6458
{
6459
    basic_string<_CharT, _ST, _SA> __r;
6460
    _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6461
                        __fmt.c_str(), __flags);
6462
    return __r;
6463
}
6464

    
6465
template <class _Traits, class _CharT, class _ST, class _SA>
6466
inline _LIBCPP_INLINE_VISIBILITY
6467
basic_string<_CharT, _ST, _SA>
6468
regex_replace(const basic_string<_CharT, _ST, _SA>& __s,
6469
              const basic_regex<_CharT, _Traits>& __e, const _CharT* __fmt,
6470
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6471
{
6472
    basic_string<_CharT, _ST, _SA> __r;
6473
    _VSTD::regex_replace(back_inserter(__r), __s.begin(), __s.end(), __e,
6474
                        __fmt, __flags);
6475
    return __r;
6476
}
6477

    
6478
template <class _Traits, class _CharT, class _ST, class _SA>
6479
inline _LIBCPP_INLINE_VISIBILITY
6480
basic_string<_CharT>
6481
regex_replace(const _CharT* __s,
6482
              const basic_regex<_CharT, _Traits>& __e,
6483
              const basic_string<_CharT, _ST, _SA>& __fmt,
6484
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6485
{
6486
    basic_string<_CharT> __r;
6487
    _VSTD::regex_replace(back_inserter(__r), __s,
6488
                        __s + char_traits<_CharT>::length(__s), __e,
6489
                        __fmt.c_str(), __flags);
6490
    return __r;
6491
}
6492

    
6493
template <class _Traits, class _CharT>
6494
inline _LIBCPP_INLINE_VISIBILITY
6495
basic_string<_CharT>
6496
regex_replace(const _CharT* __s,
6497
              const basic_regex<_CharT, _Traits>& __e,
6498
              const _CharT* __fmt,
6499
              regex_constants::match_flag_type __flags = regex_constants::match_default)
6500
{
6501
    basic_string<_CharT> __r;
6502
    _VSTD::regex_replace(back_inserter(__r), __s,
6503
                        __s + char_traits<_CharT>::length(__s), __e,
6504
                        __fmt, __flags);
6505
    return __r;
6506
}
6507

    
6508
_LIBCPP_END_NAMESPACE_STD
6509

    
6510
#endif  // _LIBCPP_REGEX