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