1 // class template regex -*- C++ -*-
2
3 // Copyright (C) 2010, 2011 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /**
26 * @file bits/regex_compiler.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{regex}
29 */
30
_GLIBCXX_VISIBILITY(default)31 namespace std _GLIBCXX_VISIBILITY(default)
32 {
33 namespace __regex
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36
37 struct _Scanner_base
38 {
39 typedef unsigned int _StateT;
40
41 static constexpr _StateT _S_state_at_start = 1 << 0;
42 static constexpr _StateT _S_state_in_brace = 1 << 2;
43 static constexpr _StateT _S_state_in_bracket = 1 << 3;
44
45 virtual ~_Scanner_base() { };
46 };
47
48 //
49 // @brief Scans an input range for regex tokens.
50 //
51 // The %_Scanner class interprets the regular expression pattern in the input
52 // range passed to its constructor as a sequence of parse tokens passed to
53 // the regular expression compiler. The sequence of tokens provided depends
54 // on the flag settings passed to the constructor: different regular
55 // expression grammars will interpret the same input pattern in
56 // syntactically different ways.
57 //
58 template<typename _InputIterator>
59 class _Scanner: public _Scanner_base
60 {
61 public:
62 typedef _InputIterator _IteratorT;
63 typedef typename std::iterator_traits<_IteratorT>::value_type _CharT;
64 typedef std::basic_string<_CharT> _StringT;
65 typedef regex_constants::syntax_option_type _FlagT;
66 typedef const std::ctype<_CharT> _CtypeT;
67
68 // Token types returned from the scanner.
69 enum _TokenT
70 {
71 _S_token_anychar,
72 _S_token_backref,
73 _S_token_bracket_begin,
74 _S_token_bracket_end,
75 _S_token_inverse_class,
76 _S_token_char_class_name,
77 _S_token_closure0,
78 _S_token_closure1,
79 _S_token_collelem_multi,
80 _S_token_collelem_single,
81 _S_token_collsymbol,
82 _S_token_comma,
83 _S_token_dash,
84 _S_token_dup_count,
85 _S_token_eof,
86 _S_token_equiv_class_name,
87 _S_token_interval_begin,
88 _S_token_interval_end,
89 _S_token_line_begin,
90 _S_token_line_end,
91 _S_token_opt,
92 _S_token_or,
93 _S_token_ord_char,
94 _S_token_quoted_char,
95 _S_token_subexpr_begin,
96 _S_token_subexpr_end,
97 _S_token_word_begin,
98 _S_token_word_end,
99 _S_token_unknown
100 };
101
102 public:
103 _Scanner(_IteratorT __begin, _IteratorT __end, _FlagT __flags,
104 std::locale __loc)
105 : _M_current(__begin) , _M_end(__end) , _M_flags(__flags),
106 _M_ctype(std::use_facet<_CtypeT>(__loc)), _M_state(_S_state_at_start)
107 { _M_advance(); }
108
109 void
110 _M_advance();
111
112 _TokenT
113 _M_token() const
114 { return _M_curToken; }
115
116 const _StringT&
117 _M_value() const
118 { return _M_curValue; }
119
120 #ifdef _GLIBCXX_DEBUG
121 std::ostream&
122 _M_print(std::ostream&);
123 #endif
124
125 private:
126 void
127 _M_eat_escape();
128
129 void
130 _M_scan_in_brace();
131
132 void
133 _M_scan_in_bracket();
134
135 void
136 _M_eat_charclass();
137
138 void
139 _M_eat_equivclass();
140
141 void
142 _M_eat_collsymbol();
143
144 private:
145 _IteratorT _M_current;
146 _IteratorT _M_end;
147 _FlagT _M_flags;
148 _CtypeT& _M_ctype;
149 _TokenT _M_curToken;
150 _StringT _M_curValue;
151 _StateT _M_state;
152 };
153
154 template<typename _InputIterator>
155 void
156 _Scanner<_InputIterator>::
157 _M_advance()
158 {
159 if (_M_current == _M_end)
160 {
161 _M_curToken = _S_token_eof;
162 return;
163 }
164
165 _CharT __c = *_M_current;
166 if (_M_state & _S_state_in_bracket)
167 {
168 _M_scan_in_bracket();
169 return;
170 }
171 if (_M_state & _S_state_in_brace)
172 {
173 _M_scan_in_brace();
174 return;
175 }
176 #if 0
177 // TODO: re-enable line anchors when _M_assertion is implemented.
178 // See PR libstdc++/47724
179 else if (_M_state & _S_state_at_start && __c == _M_ctype.widen('^'))
180 {
181 _M_curToken = _S_token_line_begin;
182 ++_M_current;
183 return;
184 }
185 else if (__c == _M_ctype.widen('$'))
186 {
187 _M_curToken = _S_token_line_end;
188 ++_M_current;
189 return;
190 }
191 #endif
192 else if (__c == _M_ctype.widen('.'))
193 {
194 _M_curToken = _S_token_anychar;
195 ++_M_current;
196 return;
197 }
198 else if (__c == _M_ctype.widen('*'))
199 {
200 _M_curToken = _S_token_closure0;
201 ++_M_current;
202 return;
203 }
204 else if (__c == _M_ctype.widen('+'))
205 {
206 _M_curToken = _S_token_closure1;
207 ++_M_current;
208 return;
209 }
210 else if (__c == _M_ctype.widen('|'))
211 {
212 _M_curToken = _S_token_or;
213 ++_M_current;
214 return;
215 }
216 else if (__c == _M_ctype.widen('['))
217 {
218 _M_curToken = _S_token_bracket_begin;
219 _M_state |= (_S_state_in_bracket | _S_state_at_start);
220 ++_M_current;
221 return;
222 }
223 else if (__c == _M_ctype.widen('\\'))
224 {
225 _M_eat_escape();
226 return;
227 }
228 else if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
229 {
230 if (__c == _M_ctype.widen('('))
231 {
232 _M_curToken = _S_token_subexpr_begin;
233 ++_M_current;
234 return;
235 }
236 else if (__c == _M_ctype.widen(')'))
237 {
238 _M_curToken = _S_token_subexpr_end;
239 ++_M_current;
240 return;
241 }
242 else if (__c == _M_ctype.widen('{'))
243 {
244 _M_curToken = _S_token_interval_begin;
245 _M_state |= _S_state_in_brace;
246 ++_M_current;
247 return;
248 }
249 }
250
251 _M_curToken = _S_token_ord_char;
252 _M_curValue.assign(1, __c);
253 ++_M_current;
254 }
255
256
257 template<typename _InputIterator>
258 void
259 _Scanner<_InputIterator>::
260 _M_scan_in_brace()
261 {
262 if (_M_ctype.is(_CtypeT::digit, *_M_current))
263 {
264 _M_curToken = _S_token_dup_count;
265 _M_curValue.assign(1, *_M_current);
266 ++_M_current;
267 while (_M_current != _M_end
268 && _M_ctype.is(_CtypeT::digit, *_M_current))
269 {
270 _M_curValue += *_M_current;
271 ++_M_current;
272 }
273 return;
274 }
275 else if (*_M_current == _M_ctype.widen(','))
276 {
277 _M_curToken = _S_token_comma;
278 ++_M_current;
279 return;
280 }
281 if (_M_flags & (regex_constants::basic | regex_constants::grep))
282 {
283 if (*_M_current == _M_ctype.widen('\\'))
284 _M_eat_escape();
285 }
286 else
287 {
288 if (*_M_current == _M_ctype.widen('}'))
289 {
290 _M_curToken = _S_token_interval_end;
291 _M_state &= ~_S_state_in_brace;
292 ++_M_current;
293 return;
294 }
295 }
296 }
297
298 template<typename _InputIterator>
299 void
300 _Scanner<_InputIterator>::
301 _M_scan_in_bracket()
302 {
303 if (_M_state & _S_state_at_start && *_M_current == _M_ctype.widen('^'))
304 {
305 _M_curToken = _S_token_inverse_class;
306 _M_state &= ~_S_state_at_start;
307 ++_M_current;
308 return;
309 }
310 else if (*_M_current == _M_ctype.widen('['))
311 {
312 ++_M_current;
313 if (_M_current == _M_end)
314 {
315 _M_curToken = _S_token_eof;
316 return;
317 }
318
319 if (*_M_current == _M_ctype.widen('.'))
320 {
321 _M_curToken = _S_token_collsymbol;
322 _M_eat_collsymbol();
323 return;
324 }
325 else if (*_M_current == _M_ctype.widen(':'))
326 {
327 _M_curToken = _S_token_char_class_name;
328 _M_eat_charclass();
329 return;
330 }
331 else if (*_M_current == _M_ctype.widen('='))
332 {
333 _M_curToken = _S_token_equiv_class_name;
334 _M_eat_equivclass();
335 return;
336 }
337 }
338 else if (*_M_current == _M_ctype.widen('-'))
339 {
340 _M_curToken = _S_token_dash;
341 ++_M_current;
342 return;
343 }
344 else if (*_M_current == _M_ctype.widen(']'))
345 {
346 if (!(_M_flags & regex_constants::ECMAScript)
347 || !(_M_state & _S_state_at_start))
348 {
349 // special case: only if _not_ chr first after
350 // '[' or '[^' and if not ECMAscript
351 _M_curToken = _S_token_bracket_end;
352 ++_M_current;
353 return;
354 }
355 }
356 _M_curToken = _S_token_collelem_single;
357 _M_curValue.assign(1, *_M_current);
358 ++_M_current;
359 }
360
361 template<typename _InputIterator>
362 void
363 _Scanner<_InputIterator>::
364 _M_eat_escape()
365 {
366 ++_M_current;
367 if (_M_current == _M_end)
368 {
369 _M_curToken = _S_token_eof;
370 return;
371 }
372 _CharT __c = *_M_current;
373 ++_M_current;
374
375 if (__c == _M_ctype.widen('('))
376 {
377 if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
378 {
379 _M_curToken = _S_token_ord_char;
380 _M_curValue.assign(1, __c);
381 }
382 else
383 _M_curToken = _S_token_subexpr_begin;
384 }
385 else if (__c == _M_ctype.widen(')'))
386 {
387 if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
388 {
389 _M_curToken = _S_token_ord_char;
390 _M_curValue.assign(1, __c);
391 }
392 else
393 _M_curToken = _S_token_subexpr_end;
394 }
395 else if (__c == _M_ctype.widen('{'))
396 {
397 if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
398 {
399 _M_curToken = _S_token_ord_char;
400 _M_curValue.assign(1, __c);
401 }
402 else
403 {
404 _M_curToken = _S_token_interval_begin;
405 _M_state |= _S_state_in_brace;
406 }
407 }
408 else if (__c == _M_ctype.widen('}'))
409 {
410 if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))
411 {
412 _M_curToken = _S_token_ord_char;
413 _M_curValue.assign(1, __c);
414 }
415 else
416 {
417 if (!(_M_state && _S_state_in_brace))
418 __throw_regex_error(regex_constants::error_badbrace);
419 _M_state &= ~_S_state_in_brace;
420 _M_curToken = _S_token_interval_end;
421 }
422 }
423 else if (__c == _M_ctype.widen('x'))
424 {
425 ++_M_current;
426 if (_M_current == _M_end)
427 {
428 _M_curToken = _S_token_eof;
429 return;
430 }
431 if (_M_ctype.is(_CtypeT::digit, *_M_current))
432 {
433 _M_curValue.assign(1, *_M_current);
434 ++_M_current;
435 if (_M_current == _M_end)
436 {
437 _M_curToken = _S_token_eof;
438 return;
439 }
440 if (_M_ctype.is(_CtypeT::digit, *_M_current))
441 {
442 _M_curValue += *_M_current;
443 ++_M_current;
444 return;
445 }
446 }
447 }
448 else if (__c == _M_ctype.widen('^')
449 || __c == _M_ctype.widen('.')
450 || __c == _M_ctype.widen('*')
451 || __c == _M_ctype.widen('$')
452 || __c == _M_ctype.widen('\\'))
453 {
454 _M_curToken = _S_token_ord_char;
455 _M_curValue.assign(1, __c);
456 }
457 else if (_M_ctype.is(_CtypeT::digit, __c))
458 {
459 _M_curToken = _S_token_backref;
460 _M_curValue.assign(1, __c);
461 }
462 else
463 __throw_regex_error(regex_constants::error_escape);
464 }
465
466
467 // Eats a character class or throwns an exception.
468 // current point to ':' delimiter on entry, char after ']' on return
469 template<typename _InputIterator>
470 void
471 _Scanner<_InputIterator>::
472 _M_eat_charclass()
473 {
474 ++_M_current; // skip ':'
475 if (_M_current == _M_end)
476 __throw_regex_error(regex_constants::error_ctype);
477 for (_M_curValue.clear();
478 _M_current != _M_end && *_M_current != _M_ctype.widen(':');
479 ++_M_current)
480 _M_curValue += *_M_current;
481 if (_M_current == _M_end)
482 __throw_regex_error(regex_constants::error_ctype);
483 ++_M_current; // skip ':'
484 if (*_M_current != _M_ctype.widen(']'))
485 __throw_regex_error(regex_constants::error_ctype);
486 ++_M_current; // skip ']'
487 }
488
489
490 template<typename _InputIterator>
491 void
492 _Scanner<_InputIterator>::
493 _M_eat_equivclass()
494 {
495 ++_M_current; // skip '='
496 if (_M_current == _M_end)
497 __throw_regex_error(regex_constants::error_collate);
498 for (_M_curValue.clear();
499 _M_current != _M_end && *_M_current != _M_ctype.widen('=');
500 ++_M_current)
501 _M_curValue += *_M_current;
502 if (_M_current == _M_end)
503 __throw_regex_error(regex_constants::error_collate);
504 ++_M_current; // skip '='
505 if (*_M_current != _M_ctype.widen(']'))
506 __throw_regex_error(regex_constants::error_collate);
507 ++_M_current; // skip ']'
508 }
509
510
511 template<typename _InputIterator>
512 void
513 _Scanner<_InputIterator>::
514 _M_eat_collsymbol()
515 {
516 ++_M_current; // skip '.'
517 if (_M_current == _M_end)
518 __throw_regex_error(regex_constants::error_collate);
519 for (_M_curValue.clear();
520 _M_current != _M_end && *_M_current != _M_ctype.widen('.');
521 ++_M_current)
522 _M_curValue += *_M_current;
523 if (_M_current == _M_end)
524 __throw_regex_error(regex_constants::error_collate);
525 ++_M_current; // skip '.'
526 if (*_M_current != _M_ctype.widen(']'))
527 __throw_regex_error(regex_constants::error_collate);
528 ++_M_current; // skip ']'
529 }
530
531 #ifdef _GLIBCXX_DEBUG
532 template<typename _InputIterator>
533 std::ostream&
534 _Scanner<_InputIterator>::
535 _M_print(std::ostream& ostr)
536 {
537 switch (_M_curToken)
538 {
539 case _S_token_anychar:
540 ostr << "any-character\n";
541 break;
542 case _S_token_backref:
543 ostr << "backref\n";
544 break;
545 case _S_token_bracket_begin:
546 ostr << "bracket-begin\n";
547 break;
548 case _S_token_bracket_end:
549 ostr << "bracket-end\n";
550 break;
551 case _S_token_char_class_name:
552 ostr << "char-class-name \"" << _M_curValue << "\"\n";
553 break;
554 case _S_token_closure0:
555 ostr << "closure0\n";
556 break;
557 case _S_token_closure1:
558 ostr << "closure1\n";
559 break;
560 case _S_token_collelem_multi:
561 ostr << "coll-elem-multi \"" << _M_curValue << "\"\n";
562 break;
563 case _S_token_collelem_single:
564 ostr << "coll-elem-single \"" << _M_curValue << "\"\n";
565 break;
566 case _S_token_collsymbol:
567 ostr << "collsymbol \"" << _M_curValue << "\"\n";
568 break;
569 case _S_token_comma:
570 ostr << "comma\n";
571 break;
572 case _S_token_dash:
573 ostr << "dash\n";
574 break;
575 case _S_token_dup_count:
576 ostr << "dup count: " << _M_curValue << "\n";
577 break;
578 case _S_token_eof:
579 ostr << "EOF\n";
580 break;
581 case _S_token_equiv_class_name:
582 ostr << "equiv-class-name \"" << _M_curValue << "\"\n";
583 break;
584 case _S_token_interval_begin:
585 ostr << "interval begin\n";
586 break;
587 case _S_token_interval_end:
588 ostr << "interval end\n";
589 break;
590 case _S_token_line_begin:
591 ostr << "line begin\n";
592 break;
593 case _S_token_line_end:
594 ostr << "line end\n";
595 break;
596 case _S_token_opt:
597 ostr << "opt\n";
598 break;
599 case _S_token_or:
600 ostr << "or\n";
601 break;
602 case _S_token_ord_char:
603 ostr << "ordinary character: \"" << _M_value() << "\"\n";
604 break;
605 case _S_token_quoted_char:
606 ostr << "quoted char\n";
607 break;
608 case _S_token_subexpr_begin:
609 ostr << "subexpr begin\n";
610 break;
611 case _S_token_subexpr_end:
612 ostr << "subexpr end\n";
613 break;
614 case _S_token_word_begin:
615 ostr << "word begin\n";
616 break;
617 case _S_token_word_end:
618 ostr << "word end\n";
619 break;
620 case _S_token_unknown:
621 ostr << "-- unknown token --\n";
622 break;
623 }
624 return ostr;
625 }
626 #endif
627
628 // Builds an NFA from an input iterator interval.
629 template<typename _InIter, typename _TraitsT>
630 class _Compiler
631 {
632 public:
633 typedef _InIter _IterT;
634 typedef typename std::iterator_traits<_InIter>::value_type _CharT;
635 typedef std::basic_string<_CharT> _StringT;
636 typedef regex_constants::syntax_option_type _FlagT;
637
638 public:
639 _Compiler(const _InIter& __b, const _InIter& __e,
640 _TraitsT& __traits, _FlagT __flags);
641
642 const _Nfa&
643 _M_nfa() const
644 { return _M_state_store; }
645
646 private:
647 typedef _Scanner<_InIter> _ScannerT;
648 typedef typename _ScannerT::_TokenT _TokenT;
649 typedef std::stack<_StateSeq, std::vector<_StateSeq> > _StackT;
650 typedef _RangeMatcher<_InIter, _TraitsT> _RMatcherT;
651
652 // accepts a specific token or returns false.
653 bool
654 _M_match_token(_TokenT __token);
655
656 void
657 _M_disjunction();
658
659 bool
660 _M_alternative();
661
662 bool
663 _M_term();
664
665 bool
666 _M_assertion();
667
668 bool
669 _M_quantifier();
670
671 bool
672 _M_atom();
673
674 bool
675 _M_bracket_expression();
676
677 bool
678 _M_bracket_list(_RMatcherT& __matcher);
679
680 bool
681 _M_follow_list(_RMatcherT& __matcher);
682
683 bool
684 _M_follow_list2(_RMatcherT& __matcher);
685
686 bool
687 _M_expression_term(_RMatcherT& __matcher);
688
689 bool
690 _M_range_expression(_RMatcherT& __matcher);
691
692 bool
693 _M_start_range(_RMatcherT& __matcher);
694
695 bool
696 _M_collating_symbol(_RMatcherT& __matcher);
697
698 bool
699 _M_equivalence_class(_RMatcherT& __matcher);
700
701 bool
702 _M_character_class(_RMatcherT& __matcher);
703
704 int
705 _M_cur_int_value(int __radix);
706
707 private:
708 _TraitsT& _M_traits;
709 _ScannerT _M_scanner;
710 _StringT _M_cur_value;
711 _Nfa _M_state_store;
712 _StackT _M_stack;
713 };
714
715 template<typename _InIter, typename _TraitsT>
716 _Compiler<_InIter, _TraitsT>::
717 _Compiler(const _InIter& __b, const _InIter& __e, _TraitsT& __traits,
718 _Compiler<_InIter, _TraitsT>::_FlagT __flags)
719 : _M_traits(__traits), _M_scanner(__b, __e, __flags, _M_traits.getloc()),
720 _M_state_store(__flags)
721 {
722 typedef _StartTagger<_InIter, _TraitsT> _Start;
723 typedef _EndTagger<_InIter, _TraitsT> _End;
724
725 _StateSeq __r(_M_state_store,
726 _M_state_store._M_insert_subexpr_begin(_Start(0)));
727 _M_disjunction();
728 if (!_M_stack.empty())
729 {
730 __r._M_append(_M_stack.top());
731 _M_stack.pop();
732 }
733 __r._M_append(_M_state_store._M_insert_subexpr_end(0, _End(0)));
734 __r._M_append(_M_state_store._M_insert_accept());
735 }
736
737 template<typename _InIter, typename _TraitsT>
738 bool
739 _Compiler<_InIter, _TraitsT>::
740 _M_match_token(_Compiler<_InIter, _TraitsT>::_TokenT token)
741 {
742 if (token == _M_scanner._M_token())
743 {
744 _M_cur_value = _M_scanner._M_value();
745 _M_scanner._M_advance();
746 return true;
747 }
748 return false;
749 }
750
751 template<typename _InIter, typename _TraitsT>
752 void
753 _Compiler<_InIter, _TraitsT>::
754 _M_disjunction()
755 {
756 this->_M_alternative();
757 if (_M_match_token(_ScannerT::_S_token_or))
758 {
759 _StateSeq __alt1 = _M_stack.top(); _M_stack.pop();
760 this->_M_disjunction();
761 _StateSeq __alt2 = _M_stack.top(); _M_stack.pop();
762 _M_stack.push(_StateSeq(__alt1, __alt2));
763 }
764 }
765
766 template<typename _InIter, typename _TraitsT>
767 bool
768 _Compiler<_InIter, _TraitsT>::
769 _M_alternative()
770 {
771 if (this->_M_term())
772 {
773 _StateSeq __re = _M_stack.top(); _M_stack.pop();
774 this->_M_alternative();
775 if (!_M_stack.empty())
776 {
777 __re._M_append(_M_stack.top());
778 _M_stack.pop();
779 }
780 _M_stack.push(__re);
781 return true;
782 }
783 return false;
784 }
785
786 template<typename _InIter, typename _TraitsT>
787 bool
788 _Compiler<_InIter, _TraitsT>::
789 _M_term()
790 {
791 if (this->_M_assertion())
792 return true;
793 if (this->_M_atom())
794 {
795 this->_M_quantifier();
796 return true;
797 }
798 return false;
799 }
800
801 template<typename _InIter, typename _TraitsT>
802 bool
803 _Compiler<_InIter, _TraitsT>::
804 _M_assertion()
805 {
806 if (_M_match_token(_ScannerT::_S_token_line_begin))
807 {
808 // __m.push(_Matcher::_S_opcode_line_begin);
809 return true;
810 }
811 if (_M_match_token(_ScannerT::_S_token_line_end))
812 {
813 // __m.push(_Matcher::_S_opcode_line_end);
814 return true;
815 }
816 if (_M_match_token(_ScannerT::_S_token_word_begin))
817 {
818 // __m.push(_Matcher::_S_opcode_word_begin);
819 return true;
820 }
821 if (_M_match_token(_ScannerT::_S_token_word_end))
822 {
823 // __m.push(_Matcher::_S_opcode_word_end);
824 return true;
825 }
826 return false;
827 }
828
829 template<typename _InIter, typename _TraitsT>
830 bool
831 _Compiler<_InIter, _TraitsT>::
832 _M_quantifier()
833 {
834 if (_M_match_token(_ScannerT::_S_token_closure0))
835 {
836 if (_M_stack.empty())
837 __throw_regex_error(regex_constants::error_badrepeat);
838 _StateSeq __r(_M_stack.top(), -1);
839 __r._M_append(__r._M_front());
840 _M_stack.pop();
841 _M_stack.push(__r);
842 return true;
843 }
844 if (_M_match_token(_ScannerT::_S_token_closure1))
845 {
846 if (_M_stack.empty())
847 __throw_regex_error(regex_constants::error_badrepeat);
848 _StateSeq __r(_M_state_store,
849 _M_state_store.
850 _M_insert_alt(_S_invalid_state_id,
851 _M_stack.top()._M_front()));
852 _M_stack.top()._M_append(__r);
853 return true;
854 }
855 if (_M_match_token(_ScannerT::_S_token_opt))
856 {
857 if (_M_stack.empty())
858 __throw_regex_error(regex_constants::error_badrepeat);
859 _StateSeq __r(_M_stack.top(), -1);
860 _M_stack.pop();
861 _M_stack.push(__r);
862 return true;
863 }
864 if (_M_match_token(_ScannerT::_S_token_interval_begin))
865 {
866 if (_M_stack.empty())
867 __throw_regex_error(regex_constants::error_badrepeat);
868 if (!_M_match_token(_ScannerT::_S_token_dup_count))
869 __throw_regex_error(regex_constants::error_badbrace);
870 _StateSeq __r(_M_stack.top());
871 int __min_rep = _M_cur_int_value(10);
872 for (int __i = 1; __i < __min_rep; ++__i)
873 _M_stack.top()._M_append(__r._M_clone());
874 if (_M_match_token(_ScannerT::_S_token_comma))
875 if (_M_match_token(_ScannerT::_S_token_dup_count))
876 {
877 int __n = _M_cur_int_value(10) - __min_rep;
878 if (__n < 0)
879 __throw_regex_error(regex_constants::error_badbrace);
880 for (int __i = 0; __i < __n; ++__i)
881 {
882 _StateSeq __r(_M_state_store,
883 _M_state_store.
884 _M_insert_alt(_S_invalid_state_id,
885 _M_stack.top()._M_front()));
886 _M_stack.top()._M_append(__r);
887 }
888 }
889 else
890 {
891 _StateSeq __r(_M_stack.top(), -1);
892 __r._M_push_back(__r._M_front());
893 _M_stack.pop();
894 _M_stack.push(__r);
895 }
896 if (!_M_match_token(_ScannerT::_S_token_interval_end))
897 __throw_regex_error(regex_constants::error_brace);
898 return true;
899 }
900 return false;
901 }
902
903 template<typename _InIter, typename _TraitsT>
904 bool
905 _Compiler<_InIter, _TraitsT>::
906 _M_atom()
907 {
908 typedef _CharMatcher<_InIter, _TraitsT> _CMatcher;
909 typedef _StartTagger<_InIter, _TraitsT> _Start;
910 typedef _EndTagger<_InIter, _TraitsT> _End;
911
912 if (_M_match_token(_ScannerT::_S_token_anychar))
913 {
914 _M_stack.push(_StateSeq(_M_state_store,
915 _M_state_store._M_insert_matcher
916 (_AnyMatcher)));
917 return true;
918 }
919 if (_M_match_token(_ScannerT::_S_token_ord_char))
920 {
921 _M_stack.push(_StateSeq(_M_state_store,
922 _M_state_store._M_insert_matcher
923 (_CMatcher(_M_cur_value[0], _M_traits))));
924 return true;
925 }
926 if (_M_match_token(_ScannerT::_S_token_quoted_char))
927 {
928 // note that in the ECMA grammar, this case covers backrefs.
929 _M_stack.push(_StateSeq(_M_state_store,
930 _M_state_store._M_insert_matcher
931 (_CMatcher(_M_cur_value[0], _M_traits))));
932 return true;
933 }
934 if (_M_match_token(_ScannerT::_S_token_backref))
935 {
936 // __m.push(_Matcher::_S_opcode_ordchar, _M_cur_value);
937 return true;
938 }
939 if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
940 {
941 int __mark = _M_state_store._M_sub_count();
942 _StateSeq __r(_M_state_store,
943 _M_state_store.
944 _M_insert_subexpr_begin(_Start(__mark)));
945 this->_M_disjunction();
946 if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
947 __throw_regex_error(regex_constants::error_paren);
948 if (!_M_stack.empty())
949 {
950 __r._M_append(_M_stack.top());
951 _M_stack.pop();
952 }
953 __r._M_append(_M_state_store._M_insert_subexpr_end
954 (__mark, _End(__mark)));
955 _M_stack.push(__r);
956 return true;
957 }
958 return _M_bracket_expression();
959 }
960
961 template<typename _InIter, typename _TraitsT>
962 bool
963 _Compiler<_InIter, _TraitsT>::
964 _M_bracket_expression()
965 {
966 if (_M_match_token(_ScannerT::_S_token_bracket_begin))
967 {
968 _RMatcherT __matcher(_M_match_token(_ScannerT::_S_token_line_begin),
969 _M_traits);
970 if (!_M_bracket_list(__matcher)
971 || !_M_match_token(_ScannerT::_S_token_bracket_end))
972 __throw_regex_error(regex_constants::error_brack);
973 _M_stack.push(_StateSeq(_M_state_store,
974 _M_state_store._M_insert_matcher(__matcher)));
975 return true;
976 }
977 return false;
978 }
979
980 // If the dash is the last character in the bracket expression, it is not
981 // special.
982 template<typename _InIter, typename _TraitsT>
983 bool
984 _Compiler<_InIter, _TraitsT>::
985 _M_bracket_list(_RMatcherT& __matcher)
986 {
987 if (_M_follow_list(__matcher))
988 {
989 if (_M_match_token(_ScannerT::_S_token_dash))
990 __matcher._M_add_char(_M_cur_value[0]);
991 return true;
992 }
993 return false;
994 }
995
996 template<typename _InIter, typename _TraitsT>
997 bool
998 _Compiler<_InIter, _TraitsT>::
999 _M_follow_list(_RMatcherT& __matcher)
1000 { return _M_expression_term(__matcher) && _M_follow_list2(__matcher); }
1001
1002 template<typename _InIter, typename _TraitsT>
1003 bool
1004 _Compiler<_InIter, _TraitsT>::
1005 _M_follow_list2(_RMatcherT& __matcher)
1006 {
1007 if (_M_expression_term(__matcher))
1008 return _M_follow_list2(__matcher);
1009 return true;
1010 }
1011
1012 template<typename _InIter, typename _TraitsT>
1013 bool
1014 _Compiler<_InIter, _TraitsT>::
1015 _M_expression_term(_RMatcherT& __matcher)
1016 {
1017 return (_M_collating_symbol(__matcher)
1018 || _M_character_class(__matcher)
1019 || _M_equivalence_class(__matcher)
1020 || (_M_start_range(__matcher)
1021 && _M_range_expression(__matcher)));
1022 }
1023
1024 template<typename _InIter, typename _TraitsT>
1025 bool
1026 _Compiler<_InIter, _TraitsT>::
1027 _M_range_expression(_RMatcherT& __matcher)
1028 {
1029 if (!_M_collating_symbol(__matcher))
1030 if (!_M_match_token(_ScannerT::_S_token_dash))
1031 __throw_regex_error(regex_constants::error_range);
1032 __matcher._M_make_range();
1033 return true;
1034 }
1035
1036 template<typename _InIter, typename _TraitsT>
1037 bool
1038 _Compiler<_InIter, _TraitsT>::
1039 _M_start_range(_RMatcherT& __matcher)
1040 { return _M_match_token(_ScannerT::_S_token_dash); }
1041
1042 template<typename _InIter, typename _TraitsT>
1043 bool
1044 _Compiler<_InIter, _TraitsT>::
1045 _M_collating_symbol(_RMatcherT& __matcher)
1046 {
1047 if (_M_match_token(_ScannerT::_S_token_collelem_single))
1048 {
1049 __matcher._M_add_char(_M_cur_value[0]);
1050 return true;
1051 }
1052 if (_M_match_token(_ScannerT::_S_token_collsymbol))
1053 {
1054 __matcher._M_add_collating_element(_M_cur_value);
1055 return true;
1056 }
1057 return false;
1058 }
1059
1060 template<typename _InIter, typename _TraitsT>
1061 bool
1062 _Compiler<_InIter, _TraitsT>::
1063 _M_equivalence_class(_RMatcherT& __matcher)
1064 {
1065 if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
1066 {
1067 __matcher._M_add_equivalence_class(_M_cur_value);
1068 return true;
1069 }
1070 return false;
1071 }
1072
1073 template<typename _InIter, typename _TraitsT>
1074 bool
1075 _Compiler<_InIter, _TraitsT>::
1076 _M_character_class(_RMatcherT& __matcher)
1077 {
1078 if (_M_match_token(_ScannerT::_S_token_char_class_name))
1079 {
1080 __matcher._M_add_character_class(_M_cur_value);
1081 return true;
1082 }
1083 return false;
1084 }
1085
1086 template<typename _InIter, typename _TraitsT>
1087 int
1088 _Compiler<_InIter, _TraitsT>::
1089 _M_cur_int_value(int __radix)
1090 {
1091 int __v = 0;
1092 for (typename _StringT::size_type __i = 0;
1093 __i < _M_cur_value.length(); ++__i)
1094 __v =__v * __radix + _M_traits.value(_M_cur_value[__i], __radix);
1095 return __v;
1096 }
1097
1098 template<typename _InIter, typename _TraitsT>
1099 _AutomatonPtr
1100 __compile(const _InIter& __b, const _InIter& __e, _TraitsT& __t,
1101 regex_constants::syntax_option_type __f)
1102 { return _AutomatonPtr(new _Nfa(_Compiler<_InIter, _TraitsT>(__b, __e, __t,
1103 __f)._M_nfa())); }
1104
1105 _GLIBCXX_END_NAMESPACE_VERSION
1106 } // namespace __regex
1107 } // namespace std
1108
1109 /* vim: set ts=8 sw=2 sts=2: */
1110