Line data Source code
1 : // class template regex -*- C++ -*-
2 :
3 : // Copyright (C) 2013-2021 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.tcc
27 : * This is an internal header file, included by other library headers.
28 : * Do not attempt to use it directly. @headername{regex}
29 : */
30 :
31 : // FIXME make comments doxygen format.
32 :
33 : /*
34 : // This compiler refers to "Regular Expression Matching Can Be Simple And Fast"
35 : // (http://swtch.com/~rsc/regexp/regexp1.html),
36 : // but doesn't strictly follow it.
37 : //
38 : // When compiling, states are *chained* instead of tree- or graph-constructed.
39 : // It's more like structured programs: there's if statement and loop statement.
40 : //
41 : // For alternative structure (say "a|b"), aka "if statement", two branches
42 : // should be constructed. However, these two shall merge to an "end_tag" at
43 : // the end of this operator:
44 : //
45 : // branch1
46 : // / \
47 : // => begin_tag end_tag =>
48 : // \ /
49 : // branch2
50 : //
51 : // This is the difference between this implementation and that in Russ's
52 : // article.
53 : //
54 : // That's why we introduced dummy node here ------ "end_tag" is a dummy node.
55 : // All dummy nodes will be eliminated at the end of compilation.
56 : */
57 :
58 : namespace std _GLIBCXX_VISIBILITY(default)
59 : {
60 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
61 :
62 : namespace __detail
63 : {
64 : template<typename _TraitsT>
65 368 : _Compiler<_TraitsT>::
66 : _Compiler(const _CharT* __b, const _CharT* __e,
67 : const typename _TraitsT::locale_type& __loc, _FlagT __flags)
68 368 : : _M_flags(_S_validate(__flags)),
69 368 : _M_scanner(__b, __e, _M_flags, __loc),
70 368 : _M_nfa(make_shared<_RegexT>(__loc, _M_flags)),
71 368 : _M_traits(_M_nfa->_M_traits),
72 736 : _M_ctype(std::use_facet<_CtypeT>(__loc))
73 : {
74 368 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_start());
75 368 : __r._M_append(_M_nfa->_M_insert_subexpr_begin());
76 368 : this->_M_disjunction();
77 368 : if (!_M_match_token(_ScannerT::_S_token_eof))
78 0 : __throw_regex_error(regex_constants::error_paren);
79 368 : __r._M_append(_M_pop());
80 368 : __glibcxx_assert(_M_stack.empty());
81 368 : __r._M_append(_M_nfa->_M_insert_subexpr_end());
82 368 : __r._M_append(_M_nfa->_M_insert_accept());
83 368 : _M_nfa->_M_eliminate_dummy();
84 368 : }
85 :
86 : template<typename _TraitsT>
87 : void
88 1196 : _Compiler<_TraitsT>::
89 : _M_disjunction()
90 : {
91 1196 : this->_M_alternative();
92 1524 : while (_M_match_token(_ScannerT::_S_token_or))
93 : {
94 328 : _StateSeqT __alt1 = _M_pop();
95 328 : this->_M_alternative();
96 328 : _StateSeqT __alt2 = _M_pop();
97 328 : auto __end = _M_nfa->_M_insert_dummy();
98 328 : __alt1._M_append(__end);
99 328 : __alt2._M_append(__end);
100 : // __alt2 is state._M_next, __alt1 is state._M_alt. The executor
101 : // executes _M_alt before _M_next, as well as executing left
102 : // alternative before right one.
103 328 : _M_stack.push(_StateSeqT(*_M_nfa,
104 328 : _M_nfa->_M_insert_alt(
105 : __alt2._M_start, __alt1._M_start, false),
106 : __end));
107 : }
108 1196 : }
109 :
110 : template<typename _TraitsT>
111 : void
112 7416 : _Compiler<_TraitsT>::
113 : _M_alternative()
114 : {
115 7416 : if (this->_M_term())
116 : {
117 5892 : _StateSeqT __re = _M_pop();
118 5892 : this->_M_alternative();
119 5892 : __re._M_append(_M_pop());
120 5892 : _M_stack.push(__re);
121 : }
122 : else
123 1524 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_dummy()));
124 7416 : }
125 :
126 : template<typename _TraitsT>
127 : bool
128 7416 : _Compiler<_TraitsT>::
129 : _M_term()
130 : {
131 7416 : if (this->_M_assertion())
132 181 : return true;
133 7235 : if (this->_M_atom())
134 : {
135 6794 : while (this->_M_quantifier())
136 : ;
137 5711 : return true;
138 : }
139 1524 : return false;
140 : }
141 :
142 : template<typename _TraitsT>
143 : bool
144 7416 : _Compiler<_TraitsT>::
145 : _M_assertion()
146 : {
147 7416 : if (_M_match_token(_ScannerT::_S_token_line_begin))
148 96 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_begin()));
149 7320 : else if (_M_match_token(_ScannerT::_S_token_line_end))
150 85 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_end()));
151 7235 : else if (_M_match_token(_ScannerT::_S_token_word_bound))
152 : // _M_value[0] == 'n' means it's negative, say "not word boundary".
153 0 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
154 0 : _M_insert_word_bound(_M_value[0] == 'n')));
155 7235 : else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
156 : {
157 0 : auto __neg = _M_value[0] == 'n';
158 0 : this->_M_disjunction();
159 0 : if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
160 0 : __throw_regex_error(regex_constants::error_paren,
161 : "Parenthesis is not closed.");
162 0 : auto __tmp = _M_pop();
163 0 : __tmp._M_append(_M_nfa->_M_insert_accept());
164 0 : _M_stack.push(
165 0 : _StateSeqT(
166 0 : *_M_nfa,
167 0 : _M_nfa->_M_insert_lookahead(__tmp._M_start, __neg)));
168 : }
169 : else
170 7235 : return false;
171 181 : return true;
172 : }
173 :
174 : template<typename _TraitsT>
175 : bool
176 6794 : _Compiler<_TraitsT>::
177 : _M_quantifier()
178 : {
179 6794 : bool __neg = (_M_flags & regex_constants::ECMAScript);
180 10710 : auto __init = [this, &__neg]()
181 : {
182 979 : if (_M_stack.empty())
183 0 : __throw_regex_error(regex_constants::error_badrepeat,
184 : "Nothing to repeat before a quantifier.");
185 979 : __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
186 : };
187 6794 : if (_M_match_token(_ScannerT::_S_token_closure0))
188 : {
189 111 : __init();
190 111 : auto __e = _M_pop();
191 111 : _StateSeqT __r(*_M_nfa,
192 111 : _M_nfa->_M_insert_repeat(_S_invalid_state_id,
193 : __e._M_start, __neg));
194 111 : __e._M_append(__r);
195 111 : _M_stack.push(__r);
196 : }
197 6683 : else if (_M_match_token(_ScannerT::_S_token_closure1))
198 : {
199 548 : __init();
200 548 : auto __e = _M_pop();
201 548 : __e._M_append(_M_nfa->_M_insert_repeat(_S_invalid_state_id,
202 : __e._M_start, __neg));
203 548 : _M_stack.push(__e);
204 : }
205 6135 : else if (_M_match_token(_ScannerT::_S_token_opt))
206 : {
207 320 : __init();
208 320 : auto __e = _M_pop();
209 320 : auto __end = _M_nfa->_M_insert_dummy();
210 320 : _StateSeqT __r(*_M_nfa,
211 320 : _M_nfa->_M_insert_repeat(_S_invalid_state_id,
212 : __e._M_start, __neg));
213 320 : __e._M_append(__end);
214 320 : __r._M_append(__end);
215 320 : _M_stack.push(__r);
216 : }
217 5815 : else if (_M_match_token(_ScannerT::_S_token_interval_begin))
218 : {
219 104 : if (_M_stack.empty())
220 0 : __throw_regex_error(regex_constants::error_badrepeat,
221 : "Nothing to repeat before a quantifier.");
222 104 : if (!_M_match_token(_ScannerT::_S_token_dup_count))
223 0 : __throw_regex_error(regex_constants::error_badbrace,
224 : "Unexpected token in brace expression.");
225 104 : _StateSeqT __r(_M_pop());
226 104 : _StateSeqT __e(*_M_nfa, _M_nfa->_M_insert_dummy());
227 104 : long __min_rep = _M_cur_int_value(10);
228 104 : bool __infi = false;
229 104 : long __n = 0;
230 :
231 : // {3
232 104 : if (_M_match_token(_ScannerT::_S_token_comma))
233 : {
234 104 : if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
235 104 : __n = _M_cur_int_value(10) - __min_rep;
236 : else
237 0 : __infi = true;
238 : }
239 104 : if (!_M_match_token(_ScannerT::_S_token_interval_end))
240 0 : __throw_regex_error(regex_constants::error_brace,
241 : "Unexpected end of brace expression.");
242 :
243 104 : __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
244 :
245 208 : for (long __i = 0; __i < __min_rep; ++__i)
246 104 : __e._M_append(__r._M_clone());
247 :
248 104 : if (__infi)
249 : {
250 0 : auto __tmp = __r._M_clone();
251 0 : _StateSeqT __s(*_M_nfa,
252 0 : _M_nfa->_M_insert_repeat(_S_invalid_state_id,
253 : __tmp._M_start, __neg));
254 0 : __tmp._M_append(__s);
255 0 : __e._M_append(__s);
256 : }
257 : else
258 : {
259 104 : if (__n < 0)
260 0 : __throw_regex_error(regex_constants::error_badbrace,
261 : "Invalid range in brace expression.");
262 104 : auto __end = _M_nfa->_M_insert_dummy();
263 : // _M_alt is the "match more" branch, and _M_next is the
264 : // "match less" one. Switch _M_alt and _M_next of all created
265 : // nodes. This is a hack but IMO works well.
266 104 : std::stack<_StateIdT> __stack;
267 5380 : for (long __i = 0; __i < __n; ++__i)
268 : {
269 5276 : auto __tmp = __r._M_clone();
270 5276 : auto __alt = _M_nfa->_M_insert_repeat(__tmp._M_start,
271 : __end, __neg);
272 5276 : __stack.push(__alt);
273 5276 : __e._M_append(_StateSeqT(*_M_nfa, __alt, __tmp._M_end));
274 : }
275 104 : __e._M_append(__end);
276 5380 : while (!__stack.empty())
277 : {
278 5276 : auto& __tmp = (*_M_nfa)[__stack.top()];
279 5276 : __stack.pop();
280 5276 : std::swap(__tmp._M_next, __tmp._M_alt);
281 : }
282 104 : }
283 104 : _M_stack.push(__e);
284 : }
285 : else
286 5711 : return false;
287 1083 : return true;
288 : }
289 :
290 : #define __INSERT_REGEX_MATCHER(__func, ...)\
291 : do {\
292 : if (!(_M_flags & regex_constants::icase))\
293 : if (!(_M_flags & regex_constants::collate))\
294 : __func<false, false>(__VA_ARGS__);\
295 : else\
296 : __func<false, true>(__VA_ARGS__);\
297 : else\
298 : if (!(_M_flags & regex_constants::collate))\
299 : __func<true, false>(__VA_ARGS__);\
300 : else\
301 : __func<true, true>(__VA_ARGS__);\
302 : } while (false)
303 :
304 : template<typename _TraitsT>
305 : bool
306 7235 : _Compiler<_TraitsT>::
307 : _M_atom()
308 : {
309 7235 : if (_M_match_token(_ScannerT::_S_token_anychar))
310 : {
311 347 : if (!(_M_flags & regex_constants::ECMAScript))
312 0 : __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
313 : else
314 347 : __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
315 : }
316 6888 : else if (_M_try_char())
317 4047 : __INSERT_REGEX_MATCHER(_M_insert_char_matcher);
318 2841 : else if (_M_match_token(_ScannerT::_S_token_backref))
319 0 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
320 0 : _M_insert_backref(_M_cur_int_value(10))));
321 2841 : else if (_M_match_token(_ScannerT::_S_token_quoted_class))
322 89 : __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
323 2752 : else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
324 : {
325 141 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_dummy());
326 141 : this->_M_disjunction();
327 141 : if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
328 0 : __throw_regex_error(regex_constants::error_paren,
329 : "Parenthesis is not closed.");
330 141 : __r._M_append(_M_pop());
331 141 : _M_stack.push(__r);
332 : }
333 2611 : else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
334 : {
335 687 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_subexpr_begin());
336 687 : this->_M_disjunction();
337 687 : if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
338 0 : __throw_regex_error(regex_constants::error_paren,
339 : "Parenthesis is not closed.");
340 687 : __r._M_append(_M_pop());
341 687 : __r._M_append(_M_nfa->_M_insert_subexpr_end());
342 687 : _M_stack.push(__r);
343 : }
344 1924 : else if (!_M_bracket_expression())
345 1524 : return false;
346 5711 : return true;
347 : }
348 :
349 : template<typename _TraitsT>
350 : bool
351 1924 : _Compiler<_TraitsT>::
352 : _M_bracket_expression()
353 : {
354 : bool __neg =
355 1924 : _M_match_token(_ScannerT::_S_token_bracket_neg_begin);
356 1924 : if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
357 1524 : return false;
358 400 : __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
359 400 : return true;
360 : }
361 : #undef __INSERT_REGEX_MATCHER
362 :
363 : template<typename _TraitsT>
364 : template<bool __icase, bool __collate>
365 : void
366 347 : _Compiler<_TraitsT>::
367 : _M_insert_any_matcher_ecma()
368 : {
369 347 : _M_stack.push(_StateSeqT(*_M_nfa,
370 347 : _M_nfa->_M_insert_matcher
371 347 : (_AnyMatcher<_TraitsT, true, __icase, __collate>
372 : (_M_traits))));
373 347 : }
374 :
375 : template<typename _TraitsT>
376 : template<bool __icase, bool __collate>
377 : void
378 0 : _Compiler<_TraitsT>::
379 : _M_insert_any_matcher_posix()
380 : {
381 0 : _M_stack.push(_StateSeqT(*_M_nfa,
382 0 : _M_nfa->_M_insert_matcher
383 0 : (_AnyMatcher<_TraitsT, false, __icase, __collate>
384 : (_M_traits))));
385 0 : }
386 :
387 : template<typename _TraitsT>
388 : template<bool __icase, bool __collate>
389 : void
390 4047 : _Compiler<_TraitsT>::
391 : _M_insert_char_matcher()
392 : {
393 4047 : _M_stack.push(_StateSeqT(*_M_nfa,
394 4047 : _M_nfa->_M_insert_matcher
395 12141 : (_CharMatcher<_TraitsT, __icase, __collate>
396 4047 : (_M_value[0], _M_traits))));
397 4047 : }
398 :
399 : template<typename _TraitsT>
400 : template<bool __icase, bool __collate>
401 : void
402 89 : _Compiler<_TraitsT>::
403 : _M_insert_character_class_matcher()
404 : {
405 89 : __glibcxx_assert(_M_value.size() == 1);
406 89 : _BracketMatcher<__icase, __collate> __matcher
407 89 : (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
408 89 : __matcher._M_add_character_class(_M_value, false);
409 89 : __matcher._M_ready();
410 89 : _M_stack.push(_StateSeqT(*_M_nfa,
411 89 : _M_nfa->_M_insert_matcher(std::move(__matcher))));
412 89 : }
413 :
414 : template<typename _TraitsT>
415 : template<bool __icase, bool __collate>
416 : void
417 400 : _Compiler<_TraitsT>::
418 : _M_insert_bracket_matcher(bool __neg)
419 : {
420 400 : _BracketMatcher<__icase, __collate> __matcher(__neg, _M_traits);
421 400 : _BracketState __last_char;
422 400 : if (_M_try_char())
423 233 : __last_char.set(_M_value[0]);
424 167 : else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
425 : // Dash as first character is a normal character.
426 2 : __last_char.set('-');
427 2081 : while (_M_expression_term(__last_char, __matcher))
428 : ;
429 400 : if (__last_char._M_is_char())
430 242 : __matcher._M_add_char(__last_char.get());
431 400 : __matcher._M_ready();
432 800 : _M_stack.push(_StateSeqT(
433 400 : *_M_nfa,
434 400 : _M_nfa->_M_insert_matcher(std::move(__matcher))));
435 400 : }
436 :
437 : template<typename _TraitsT>
438 : template<bool __icase, bool __collate>
439 : bool
440 2081 : _Compiler<_TraitsT>::
441 : _M_expression_term(_BracketState& __last_char,
442 : _BracketMatcher<__icase, __collate>& __matcher)
443 : {
444 2081 : if (_M_match_token(_ScannerT::_S_token_bracket_end))
445 400 : return false;
446 :
447 : // Add any previously cached char into the matcher and update cache.
448 5839 : const auto __push_char = [&](_CharT __ch)
449 : {
450 1136 : if (__last_char._M_is_char())
451 750 : __matcher._M_add_char(__last_char.get());
452 1136 : __last_char.set(__ch);
453 : };
454 : // Add any previously cached char into the matcher and update cache.
455 2179 : const auto __push_class = [&]
456 : {
457 166 : if (__last_char._M_is_char())
458 0 : __matcher._M_add_char(__last_char.get());
459 : // We don't cache anything here, just record that the last thing
460 : // processed was a character class (or similar).
461 166 : __last_char.reset(_BracketState::_Type::_Class);
462 : };
463 :
464 1681 : if (_M_match_token(_ScannerT::_S_token_collsymbol))
465 : {
466 0 : auto __symbol = __matcher._M_add_collate_element(_M_value);
467 0 : if (__symbol.size() == 1)
468 0 : __push_char(__symbol[0]);
469 : else
470 0 : __push_class();
471 0 : }
472 1681 : else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
473 : {
474 0 : __push_class();
475 0 : __matcher._M_add_equivalence_class(_M_value);
476 : }
477 1681 : else if (_M_match_token(_ScannerT::_S_token_char_class_name))
478 : {
479 0 : __push_class();
480 0 : __matcher._M_add_character_class(_M_value, false);
481 : }
482 1681 : else if (_M_try_char())
483 1136 : __push_char(_M_value[0]);
484 : // POSIX doesn't allow '-' as a start-range char (say [a-z--0]),
485 : // except when the '-' is the first or last character in the bracket
486 : // expression ([--0]). ECMAScript treats all '-' after a range as a
487 : // normal character. Also see above, where _M_expression_term gets called.
488 : //
489 : // As a result, POSIX rejects [-----], but ECMAScript doesn't.
490 : // Boost (1.57.0) always uses POSIX style even in its ECMAScript syntax.
491 : // Clang (3.5) always uses ECMAScript style even in its POSIX syntax.
492 : //
493 : // It turns out that no one reads BNFs ;)
494 545 : else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
495 : {
496 379 : if (_M_match_token(_ScannerT::_S_token_bracket_end))
497 : {
498 : // For "-]" the dash is a literal character.
499 0 : __push_char('-');
500 0 : return false;
501 : }
502 379 : else if (__last_char._M_is_class())
503 : {
504 : // "\\w-" is invalid, start of range must be a single char.
505 0 : __throw_regex_error(regex_constants::error_range,
506 : "Invalid start of range in bracket expression.");
507 : }
508 379 : else if (__last_char._M_is_char())
509 : {
510 379 : if (_M_try_char())
511 : {
512 : // "x-y"
513 379 : __matcher._M_make_range(__last_char.get(), _M_value[0]);
514 379 : __last_char.reset();
515 : }
516 0 : else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
517 : {
518 : // "x--"
519 0 : __matcher._M_make_range(__last_char.get(), '-');
520 0 : __last_char.reset();
521 : }
522 : else
523 0 : __throw_regex_error(regex_constants::error_range,
524 : "Invalid end of range in bracket expression.");
525 : }
526 0 : else if (_M_flags & regex_constants::ECMAScript)
527 : {
528 : // A dash that is not part of an existing range. Might be the
529 : // start of a new range, or might just be a literal '-' char.
530 : // Only ECMAScript allows that in the middle of a bracket expr.
531 0 : __push_char('-');
532 : }
533 : else
534 0 : __throw_regex_error(regex_constants::error_range,
535 : "Invalid dash in bracket expression.");
536 : }
537 166 : else if (_M_match_token(_ScannerT::_S_token_quoted_class))
538 : {
539 166 : __push_class();
540 166 : __matcher._M_add_character_class(_M_value,
541 332 : _M_ctype.is(_CtypeT::upper,
542 166 : _M_value[0]));
543 : }
544 : else
545 0 : __throw_regex_error(regex_constants::error_brack,
546 : "Unexpected character in bracket expression.");
547 :
548 1681 : return true;
549 : }
550 :
551 : template<typename _TraitsT>
552 : bool
553 9348 : _Compiler<_TraitsT>::
554 : _M_try_char()
555 : {
556 9348 : bool __is_char = false;
557 9348 : if (_M_match_token(_ScannerT::_S_token_oct_num))
558 : {
559 0 : __is_char = true;
560 0 : _M_value.assign(1, _M_cur_int_value(8));
561 : }
562 9348 : else if (_M_match_token(_ScannerT::_S_token_hex_num))
563 : {
564 0 : __is_char = true;
565 0 : _M_value.assign(1, _M_cur_int_value(16));
566 : }
567 9348 : else if (_M_match_token(_ScannerT::_S_token_ord_char))
568 5795 : __is_char = true;
569 9348 : return __is_char;
570 : }
571 :
572 : template<typename _TraitsT>
573 : bool
574 117294 : _Compiler<_TraitsT>::
575 : _M_match_token(_TokenT __token)
576 : {
577 117294 : if (__token == _M_scanner._M_get_token())
578 : {
579 11613 : _M_value = _M_scanner._M_get_value();
580 11613 : _M_scanner._M_advance();
581 11613 : return true;
582 : }
583 105681 : return false;
584 : }
585 :
586 : template<typename _TraitsT>
587 : int
588 208 : _Compiler<_TraitsT>::
589 : _M_cur_int_value(int __radix)
590 : {
591 208 : int __v = 0;
592 498 : for (_CharT __c : _M_value)
593 580 : if (__builtin_mul_overflow(__v, __radix, &__v)
594 290 : || __builtin_add_overflow(__v, _M_traits.value(__c, __radix), &__v))
595 0 : std::__throw_regex_error(regex_constants::error_backref,
596 : "invalid back reference");
597 208 : return __v;
598 : }
599 :
600 : template<typename _TraitsT, bool __icase, bool __collate>
601 : bool
602 125184 : _BracketMatcher<_TraitsT, __icase, __collate>::
603 : _M_apply(_CharT __ch, false_type) const
604 : {
605 1373537 : return [this, __ch]
606 : {
607 125184 : if (std::binary_search(_M_char_set.begin(), _M_char_set.end(),
608 250368 : _M_translator._M_translate(__ch)))
609 992 : return true;
610 124192 : auto __s = _M_translator._M_transform(__ch);
611 206791 : for (auto& __it : _M_range_set)
612 90021 : if (_M_translator._M_match_range(__it.first, __it.second, __s))
613 7422 : return true;
614 116770 : if (_M_traits.isctype(__ch, _M_class_set))
615 8208 : return true;
616 217124 : if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
617 108562 : _M_traits.transform_primary(&__ch, &__ch+1))
618 325686 : != _M_equiv_set.end())
619 0 : return true;
620 108562 : for (auto& __it : _M_neg_class_set)
621 0 : if (!_M_traits.isctype(__ch, __it))
622 0 : return true;
623 108562 : return false;
624 125184 : }() ^ _M_is_non_matching;
625 : }
626 : } // namespace __detail
627 :
628 : _GLIBCXX_END_NAMESPACE_VERSION
629 : } // namespace
|
