| blob | 8551e0d29a7c8a72de150c4988a95e4e06b01210 |
1 // class template regex -*- C++ -*-
3 // Copyright (C) 2013-2014 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.
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.
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.
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/>.
25 /**
26 * @file bits/regex_compiler.tcc
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{regex}
29 */
31 // FIXME make comments doxygen format.
33 // This compiler refers to "Regular Expression Matching Can Be Simple And Fast"
34 // (http://swtch.com/~rsc/regexp/regexp1.html"),
35 // but doesn't strictly follow it.
36 //
37 // When compiling, states are *chained* instead of tree- or graph-constructed.
38 // It's more like structured programs: there's if statement and loop statement.
39 //
40 // For alternative structure(say "a|b"), aka "if statement", two branchs should
41 // be constructed. However, these two shall merge to an "end_tag" at the end of
42 // this operator:
43 //
44 // branch1
45 // / \
46 // => begin_tag end_tag =>
47 // \ /
48 // branch2
49 //
50 // This is the difference between this implementation and that in Russ's
51 // article.
52 //
53 // That's why we introduced dummy node here ------ "end_tag" is a dummy node.
54 // All dummy node will be eliminated at the end of compiling process.
56 namespace std _GLIBCXX_VISIBILITY(default)
57 {
58 namespace __detail
59 {
60 _GLIBCXX_BEGIN_NAMESPACE_VERSION
62 template<typename _TraitsT>
63 _Compiler<_TraitsT>::
64 _Compiler(_IterT __b, _IterT __e,
65 const _TraitsT& __traits, _FlagT __flags)
66 : _M_flags((__flags
67 & (regex_constants::ECMAScript
68 | regex_constants::basic
69 | regex_constants::extended
70 | regex_constants::grep
71 | regex_constants::egrep
72 | regex_constants::awk))
73 ? __flags
74 : __flags | regex_constants::ECMAScript),
75 _M_traits(__traits),
76 _M_ctype(std::use_facet<_CtypeT>(_M_traits.getloc())),
77 _M_scanner(__b, __e, _M_flags, _M_traits.getloc()),
78 _M_nfa(_M_flags)
79 {
80 _StateSeqT __r(_M_nfa, _M_nfa._M_start());
81 __r._M_append(_M_nfa._M_insert_subexpr_begin());
82 this->_M_disjunction();
83 if (!_M_match_token(_ScannerT::_S_token_eof))
84 __throw_regex_error(regex_constants::error_paren);
85 __r._M_append(_M_pop());
86 _GLIBCXX_DEBUG_ASSERT(_M_stack.empty());
87 __r._M_append(_M_nfa._M_insert_subexpr_end());
88 __r._M_append(_M_nfa._M_insert_accept());
89 _M_nfa._M_eliminate_dummy();
90 }
92 template<typename _TraitsT>
93 void
94 _Compiler<_TraitsT>::
95 _M_disjunction()
96 {
97 this->_M_alternative();
98 while (_M_match_token(_ScannerT::_S_token_or))
99 {
100 _StateSeqT __alt1 = _M_pop();
101 this->_M_alternative();
102 _StateSeqT __alt2 = _M_pop();
103 auto __end = _M_nfa._M_insert_dummy();
104 __alt1._M_append(__end);
105 __alt2._M_append(__end);
106 _M_stack.push(_StateSeqT(_M_nfa,
107 _M_nfa._M_insert_alt(__alt1._M_start,
108 __alt2._M_start, false),
109 __end));
110 }
111 }
113 template<typename _TraitsT>
114 void
115 _Compiler<_TraitsT>::
116 _M_alternative()
117 {
118 if (this->_M_term())
119 {
120 _StateSeqT __re = _M_pop();
121 this->_M_alternative();
122 __re._M_append(_M_pop());
123 _M_stack.push(__re);
124 }
125 else
126 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_dummy()));
127 }
129 template<typename _TraitsT>
130 bool
131 _Compiler<_TraitsT>::
132 _M_term()
133 {
134 if (this->_M_assertion())
135 return true;
136 if (this->_M_atom())
137 {
138 while (this->_M_quantifier());
139 return true;
140 }
141 return false;
142 }
144 template<typename _TraitsT>
145 bool
146 _Compiler<_TraitsT>::
147 _M_assertion()
148 {
149 if (_M_match_token(_ScannerT::_S_token_line_begin))
150 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_begin()));
151 else if (_M_match_token(_ScannerT::_S_token_line_end))
152 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_end()));
153 else if (_M_match_token(_ScannerT::_S_token_word_bound))
154 // _M_value[0] == 'n' means it's negtive, say "not word boundary".
155 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
156 _M_insert_word_bound(_M_value[0] == 'n')));
157 else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
158 {
159 auto __neg = _M_value[0] == 'n';
160 this->_M_disjunction();
161 if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
162 __throw_regex_error(regex_constants::error_paren);
163 auto __tmp = _M_pop();
164 __tmp._M_append(_M_nfa._M_insert_accept());
165 _M_stack.push(
166 _StateSeqT(
167 _M_nfa,
168 _M_nfa._M_insert_lookahead(__tmp._M_start, __neg)));
169 }
170 else
171 return false;
172 return true;
173 }
175 template<typename _TraitsT>
176 bool
177 _Compiler<_TraitsT>::
178 _M_quantifier()
179 {
180 bool __neg = (_M_flags & regex_constants::ECMAScript);
181 auto __init = [this, &__neg]()
182 {
183 if (_M_stack.empty())
184 __throw_regex_error(regex_constants::error_badrepeat);
185 __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
186 };
187 if (_M_match_token(_ScannerT::_S_token_closure0))
188 {
189 __init();
190 auto __e = _M_pop();
191 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id,
192 __e._M_start, __neg));
193 __e._M_append(__r);
194 _M_stack.push(__r);
195 }
196 else if (_M_match_token(_ScannerT::_S_token_closure1))
197 {
198 __init();
199 auto __e = _M_pop();
200 __e._M_append(_M_nfa._M_insert_alt(_S_invalid_state_id, __e._M_start,
201 __neg));
202 _M_stack.push(__e);
203 }
204 else if (_M_match_token(_ScannerT::_S_token_opt))
205 {
206 __init();
207 auto __e = _M_pop();
208 auto __end = _M_nfa._M_insert_dummy();
209 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id,
210 __e._M_start, __neg));
211 __e._M_append(__end);
212 __r._M_append(__end);
213 _M_stack.push(__r);
214 }
215 else if (_M_match_token(_ScannerT::_S_token_interval_begin))
216 {
217 if (_M_stack.empty())
218 __throw_regex_error(regex_constants::error_badrepeat);
219 if (!_M_match_token(_ScannerT::_S_token_dup_count))
220 __throw_regex_error(regex_constants::error_badbrace);
221 _StateSeqT __r(_M_pop());
222 _StateSeqT __e(_M_nfa, _M_nfa._M_insert_dummy());
223 long __min_rep = _M_cur_int_value(10);
224 bool __infi = false;
225 long __n;
227 // {3
228 if (_M_match_token(_ScannerT::_S_token_comma))
229 if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
230 __n = _M_cur_int_value(10) - __min_rep;
231 else
232 __infi = true;
233 else
234 __n = 0;
235 if (!_M_match_token(_ScannerT::_S_token_interval_end))
236 __throw_regex_error(regex_constants::error_brace);
238 __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
240 for (long __i = 0; __i < __min_rep; ++__i)
241 __e._M_append(__r._M_clone());
243 if (__infi)
244 {
245 auto __tmp = __r._M_clone();
246 _StateSeqT __s(_M_nfa,
247 _M_nfa._M_insert_alt(_S_invalid_state_id,
248 __tmp._M_start, __neg));
249 __tmp._M_append(__s);
250 __e._M_append(__s);
251 }
252 else
253 {
254 if (__n < 0)
255 __throw_regex_error(regex_constants::error_badbrace);
256 auto __end = _M_nfa._M_insert_dummy();
257 // _M_alt is the "match more" branch, and _M_next is the
258 // "match less" one. Switch _M_alt and _M_next of all created
259 // nodes. This is a hacking but IMO works well.
260 std::stack<_StateIdT> __stack;
261 for (long __i = 0; __i < __n; ++__i)
262 {
263 auto __tmp = __r._M_clone();
264 auto __alt = _M_nfa._M_insert_alt(__tmp._M_start,
265 __end, __neg);
266 __stack.push(__alt);
267 __e._M_append(_StateSeqT(_M_nfa, __alt, __tmp._M_end));
268 }
269 __e._M_append(__end);
270 while (!__stack.empty())
271 {
272 auto& __tmp = _M_nfa[__stack.top()];
273 __stack.pop();
274 std::swap(__tmp._M_next, __tmp._M_alt);
275 }
276 }
277 _M_stack.push(__e);
278 }
279 else
280 return false;
281 return true;
282 }
284 #define __INSERT_REGEX_MATCHER(__func, args...)\
285 do\
286 if (!(_M_flags & regex_constants::icase))\
287 if (!(_M_flags & regex_constants::collate))\
288 __func<false, false>(args);\
289 else\
290 __func<false, true>(args);\
291 else\
292 if (!(_M_flags & regex_constants::collate))\
293 __func<true, false>(args);\
294 else\
295 __func<true, true>(args);\
296 while (false)
298 template<typename _TraitsT>
299 bool
300 _Compiler<_TraitsT>::
301 _M_atom()
302 {
303 if (_M_match_token(_ScannerT::_S_token_anychar))
304 {
305 if (!(_M_flags & regex_constants::ECMAScript))
306 __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
307 else
308 __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
309 }
310 else if (_M_try_char())
311 __INSERT_REGEX_MATCHER(_M_insert_char_matcher);
312 else if (_M_match_token(_ScannerT::_S_token_backref))
313 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
314 _M_insert_backref(_M_cur_int_value(10))));
315 else if (_M_match_token(_ScannerT::_S_token_quoted_class))
316 __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
317 else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
318 {
319 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_dummy());
320 this->_M_disjunction();
321 if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
322 __throw_regex_error(regex_constants::error_paren);
323 __r._M_append(_M_pop());
324 _M_stack.push(__r);
325 }
326 else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
327 {
328 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_subexpr_begin());
329 this->_M_disjunction();
330 if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
331 __throw_regex_error(regex_constants::error_paren);
332 __r._M_append(_M_pop());
333 __r._M_append(_M_nfa._M_insert_subexpr_end());
334 _M_stack.push(__r);
335 }
336 else if (!_M_bracket_expression())
337 return false;
338 return true;
339 }
341 template<typename _TraitsT>
342 bool
343 _Compiler<_TraitsT>::
344 _M_bracket_expression()
345 {
346 bool __neg =
347 _M_match_token(_ScannerT::_S_token_bracket_neg_begin);
348 if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
349 return false;
350 __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
351 return true;
352 }
353 #undef __INSERT_REGEX_MATCHER
355 template<typename _TraitsT>
356 template<bool __icase, bool __collate>
357 void
358 _Compiler<_TraitsT>::
359 _M_insert_any_matcher_ecma()
360 {
361 _M_stack.push(_StateSeqT(_M_nfa,
362 _M_nfa._M_insert_matcher
363 (_AnyMatcher<_TraitsT, true, __icase, __collate>
364 (_M_traits))));
365 }
367 template<typename _TraitsT>
368 template<bool __icase, bool __collate>
369 void
370 _Compiler<_TraitsT>::
371 _M_insert_any_matcher_posix()
372 {
373 _M_stack.push(_StateSeqT(_M_nfa,
374 _M_nfa._M_insert_matcher
375 (_AnyMatcher<_TraitsT, false, __icase, __collate>
376 (_M_traits))));
377 }
379 template<typename _TraitsT>
380 template<bool __icase, bool __collate>
381 void
382 _Compiler<_TraitsT>::
383 _M_insert_char_matcher()
384 {
385 _M_stack.push(_StateSeqT(_M_nfa,
386 _M_nfa._M_insert_matcher
387 (_CharMatcher<_TraitsT, __icase, __collate>
388 (_M_value[0], _M_traits))));
389 }
391 template<typename _TraitsT>
392 template<bool __icase, bool __collate>
393 void
394 _Compiler<_TraitsT>::
395 _M_insert_character_class_matcher()
396 {
397 _GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1);
398 _BracketMatcher<_TraitsT, __icase, __collate> __matcher
399 (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
400 __matcher._M_add_character_class(_M_value, false);
401 __matcher._M_ready();
402 _M_stack.push(_StateSeqT(_M_nfa,
403 _M_nfa._M_insert_matcher(std::move(__matcher))));
404 }
406 template<typename _TraitsT>
407 template<bool __icase, bool __collate>
408 void
409 _Compiler<_TraitsT>::
410 _M_insert_bracket_matcher(bool __neg)
411 {
412 _BracketMatcher<_TraitsT, __icase, __collate> __matcher(__neg, _M_traits);
413 pair<bool, _CharT> __last_char; // Optional<_CharT>
414 __last_char.first = false;
415 if (!(_M_flags & regex_constants::ECMAScript))
416 if (_M_try_char())
417 {
418 __matcher._M_add_char(_M_value[0]);
419 __last_char.first = true;
420 __last_char.second = _M_value[0];
421 }
422 while (!_M_match_token(_ScannerT::_S_token_bracket_end))
423 _M_expression_term(__last_char, __matcher);
424 __matcher._M_ready();
425 _M_stack.push(_StateSeqT(
426 _M_nfa,
427 _M_nfa._M_insert_matcher(std::move(__matcher))));
428 }
430 template<typename _TraitsT>
431 template<bool __icase, bool __collate>
432 void
433 _Compiler<_TraitsT>::
434 _M_expression_term(pair<bool, _CharT>& __last_char,
435 _BracketMatcher<_TraitsT, __icase, __collate>& __matcher)
437 {
438 if (_M_match_token(_ScannerT::_S_token_collsymbol))
439 __matcher._M_add_collating_element(_M_value);
440 else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
441 __matcher._M_add_equivalence_class(_M_value);
442 else if (_M_match_token(_ScannerT::_S_token_char_class_name))
443 __matcher._M_add_character_class(_M_value, false);
444 // POSIX doesn't permit '-' as a start-range char (say [a-z--0]),
445 // except when the '-' is the first character in the bracket expression
446 // ([--0]). ECMAScript treats all '-' after a range as a normal character.
447 // Also see above, where _M_expression_term gets called.
448 //
449 // As a result, POSIX rejects [-----], but ECMAScript doesn't.
450 // Boost (1.57.0) always uses POSIX style even in its ECMAScript syntax.
451 // Clang (3.5) always uses ECMAScript style even in its POSIX syntax.
452 //
453 // It turns out that no one reads BNFs ;)
454 else if (_M_try_char())
455 {
456 if (!__last_char.first)
457 {
458 if (_M_value[0] == '-'
459 && !(_M_flags & regex_constants::ECMAScript))
460 __throw_regex_error(regex_constants::error_range);
461 __matcher._M_add_char(_M_value[0]);
462 __last_char.first = true;
463 __last_char.second = _M_value[0];
464 }
465 else
466 {
467 if (_M_value[0] == '-')
468 {
469 if (_M_try_char())
470 {
471 __matcher._M_make_range(__last_char.second , _M_value[0]);
472 __last_char.first = false;
473 }
474 else
475 {
476 if (_M_scanner._M_get_token()
477 != _ScannerT::_S_token_bracket_end)
478 __throw_regex_error(regex_constants::error_range);
479 __matcher._M_add_char(_M_value[0]);
480 }
481 }
482 else
483 {
484 __matcher._M_add_char(_M_value[0]);
485 __last_char.second = _M_value[0];
486 }
487 }
488 }
489 else if (_M_match_token(_ScannerT::_S_token_quoted_class))
490 __matcher._M_add_character_class(_M_value,
491 _M_ctype.is(_CtypeT::upper,
492 _M_value[0]));
493 else
494 __throw_regex_error(regex_constants::error_brack);
495 }
497 template<typename _TraitsT>
498 bool
499 _Compiler<_TraitsT>::
500 _M_try_char()
501 {
502 bool __is_char = false;
503 if (_M_match_token(_ScannerT::_S_token_oct_num))
504 {
505 __is_char = true;
506 _M_value.assign(1, _M_cur_int_value(8));
507 }
508 else if (_M_match_token(_ScannerT::_S_token_hex_num))
509 {
510 __is_char = true;
511 _M_value.assign(1, _M_cur_int_value(16));
512 }
513 else if (_M_match_token(_ScannerT::_S_token_ord_char))
514 __is_char = true;
515 return __is_char;
516 }
518 template<typename _TraitsT>
519 bool
520 _Compiler<_TraitsT>::
521 _M_match_token(_TokenT token)
522 {
523 if (token == _M_scanner._M_get_token())
524 {
525 _M_value = _M_scanner._M_get_value();
526 _M_scanner._M_advance();
527 return true;
528 }
529 return false;
530 }
532 template<typename _TraitsT>
533 int
534 _Compiler<_TraitsT>::
535 _M_cur_int_value(int __radix)
536 {
537 long __v = 0;
538 for (typename _StringT::size_type __i = 0;
539 __i < _M_value.length(); ++__i)
540 __v =__v * __radix + _M_traits.value(_M_value[__i], __radix);
541 return __v;
542 }
544 template<typename _TraitsT, bool __icase, bool __collate>
545 bool
546 _BracketMatcher<_TraitsT, __icase, __collate>::
547 _M_apply(_CharT __ch, false_type) const
548 {
549 bool __ret = false;
550 if (std::find(_M_char_set.begin(), _M_char_set.end(),
551 _M_translator._M_translate(__ch))
552 != _M_char_set.end())
553 __ret = true;
554 else
555 {
556 auto __s = _M_translator._M_transform(__ch);
557 for (auto& __it : _M_range_set)
558 if (__it.first <= __s && __s <= __it.second)
559 {
560 __ret = true;
561 break;
562 }
563 if (_M_traits.isctype(__ch, _M_class_set))
564 __ret = true;
565 else if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
566 _M_traits.transform_primary(&__ch, &__ch+1))
567 != _M_equiv_set.end())
568 __ret = true;
569 else
570 {
571 for (auto& __it : _M_neg_class_set)
572 if (!_M_traits.isctype(__ch, __it))
573 {
574 __ret = true;
575 break;
576 }
577 }
578 }
579 if (_M_is_non_matching)
580 return !__ret;
581 else
582 return __ret;
583 }
585 _GLIBCXX_END_NAMESPACE_VERSION
586 } // namespace __detail
587 } // namespace