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 343 : _Compiler<_TraitsT>::
66 : _Compiler(const _CharT* __b, const _CharT* __e,
67 : const typename _TraitsT::locale_type& __loc, _FlagT __flags)
68 343 : : _M_flags(_S_validate(__flags)),
69 343 : _M_scanner(__b, __e, _M_flags, __loc),
70 343 : _M_nfa(make_shared<_RegexT>(__loc, _M_flags)),
71 343 : _M_traits(_M_nfa->_M_traits),
72 686 : _M_ctype(std::use_facet<_CtypeT>(__loc))
73 : {
74 343 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_start());
75 343 : __r._M_append(_M_nfa->_M_insert_subexpr_begin());
76 343 : this->_M_disjunction();
77 343 : if (!_M_match_token(_ScannerT::_S_token_eof))
78 0 : __throw_regex_error(regex_constants::error_paren);
79 343 : __r._M_append(_M_pop());
80 343 : __glibcxx_assert(_M_stack.empty());
81 343 : __r._M_append(_M_nfa->_M_insert_subexpr_end());
82 343 : __r._M_append(_M_nfa->_M_insert_accept());
83 343 : _M_nfa->_M_eliminate_dummy();
84 343 : }
85 :
86 : template<typename _TraitsT>
87 : void
88 1129 : _Compiler<_TraitsT>::
89 : _M_disjunction()
90 : {
91 1129 : this->_M_alternative();
92 1451 : while (_M_match_token(_ScannerT::_S_token_or))
93 : {
94 322 : _StateSeqT __alt1 = _M_pop();
95 322 : this->_M_alternative();
96 322 : _StateSeqT __alt2 = _M_pop();
97 322 : auto __end = _M_nfa->_M_insert_dummy();
98 322 : __alt1._M_append(__end);
99 322 : __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 322 : _M_stack.push(_StateSeqT(*_M_nfa,
104 322 : _M_nfa->_M_insert_alt(
105 : __alt2._M_start, __alt1._M_start, false),
106 : __end));
107 : }
108 1129 : }
109 :
110 : template<typename _TraitsT>
111 : void
112 7145 : _Compiler<_TraitsT>::
113 : _M_alternative()
114 : {
115 7145 : if (this->_M_term())
116 : {
117 5694 : _StateSeqT __re = _M_pop();
118 5694 : this->_M_alternative();
119 5694 : __re._M_append(_M_pop());
120 5694 : _M_stack.push(__re);
121 : }
122 : else
123 1451 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_dummy()));
124 7145 : }
125 :
126 : template<typename _TraitsT>
127 : bool
128 7145 : _Compiler<_TraitsT>::
129 : _M_term()
130 : {
131 7145 : if (this->_M_assertion())
132 175 : return true;
133 6970 : if (this->_M_atom())
134 : {
135 6556 : while (this->_M_quantifier())
136 : ;
137 5519 : return true;
138 : }
139 1451 : return false;
140 : }
141 :
142 : template<typename _TraitsT>
143 : bool
144 7145 : _Compiler<_TraitsT>::
145 : _M_assertion()
146 : {
147 7145 : if (_M_match_token(_ScannerT::_S_token_line_begin))
148 92 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_begin()));
149 7053 : else if (_M_match_token(_ScannerT::_S_token_line_end))
150 83 : _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_end()));
151 6970 : 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 6970 : 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 6970 : return false;
171 175 : return true;
172 : }
173 :
174 : template<typename _TraitsT>
175 : bool
176 6556 : _Compiler<_TraitsT>::
177 : _M_quantifier()
178 : {
179 6556 : bool __neg = (_M_flags & regex_constants::ECMAScript);
180 10312 : auto __init = [this, &__neg]()
181 : {
182 939 : if (_M_stack.empty())
183 0 : __throw_regex_error(regex_constants::error_badrepeat,
184 : "Nothing to repeat before a quantifier.");
185 939 : __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
186 : };
187 6556 : if (_M_match_token(_ScannerT::_S_token_closure0))
188 : {
189 115 : __init();
190 115 : auto __e = _M_pop();
191 115 : _StateSeqT __r(*_M_nfa,
192 115 : _M_nfa->_M_insert_repeat(_S_invalid_state_id,
193 : __e._M_start, __neg));
194 115 : __e._M_append(__r);
195 115 : _M_stack.push(__r);
196 : }
197 6441 : else if (_M_match_token(_ScannerT::_S_token_closure1))
198 : {
199 515 : __init();
200 515 : auto __e = _M_pop();
201 515 : __e._M_append(_M_nfa->_M_insert_repeat(_S_invalid_state_id,
202 : __e._M_start, __neg));
203 515 : _M_stack.push(__e);
204 : }
205 5926 : else if (_M_match_token(_ScannerT::_S_token_opt))
206 : {
207 309 : __init();
208 309 : auto __e = _M_pop();
209 309 : auto __end = _M_nfa->_M_insert_dummy();
210 309 : _StateSeqT __r(*_M_nfa,
211 309 : _M_nfa->_M_insert_repeat(_S_invalid_state_id,
212 : __e._M_start, __neg));
213 309 : __e._M_append(__end);
214 309 : __r._M_append(__end);
215 309 : _M_stack.push(__r);
216 : }
217 5617 : else if (_M_match_token(_ScannerT::_S_token_interval_begin))
218 : {
219 98 : if (_M_stack.empty())
220 0 : __throw_regex_error(regex_constants::error_badrepeat,
221 : "Nothing to repeat before a quantifier.");
222 98 : 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 98 : _StateSeqT __r(_M_pop());
226 98 : _StateSeqT __e(*_M_nfa, _M_nfa->_M_insert_dummy());
227 98 : long __min_rep = _M_cur_int_value(10);
228 98 : bool __infi = false;
229 98 : long __n = 0;
230 :
231 : // {3
232 98 : if (_M_match_token(_ScannerT::_S_token_comma))
233 : {
234 98 : if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
235 98 : __n = _M_cur_int_value(10) - __min_rep;
236 : else
237 0 : __infi = true;
238 : }
239 98 : 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 98 : __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
244 :
245 196 : for (long __i = 0; __i < __min_rep; ++__i)
246 98 : __e._M_append(__r._M_clone());
247 :
248 98 : 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 98 : if (__n < 0)
260 0 : __throw_regex_error(regex_constants::error_badbrace,
261 : "Invalid range in brace expression.");
262 98 : 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 98 : std::stack<_StateIdT> __stack;
267 5228 : for (long __i = 0; __i < __n; ++__i)
268 : {
269 5130 : auto __tmp = __r._M_clone();
270 5130 : auto __alt = _M_nfa->_M_insert_repeat(__tmp._M_start,
271 : __end, __neg);
272 5130 : __stack.push(__alt);
273 5130 : __e._M_append(_StateSeqT(*_M_nfa, __alt, __tmp._M_end));
274 : }
275 98 : __e._M_append(__end);
276 5228 : while (!__stack.empty())
277 : {
278 5130 : auto& __tmp = (*_M_nfa)[__stack.top()];
279 5130 : __stack.pop();
280 5130 : std::swap(__tmp._M_next, __tmp._M_alt);
281 : }
282 98 : }
283 98 : _M_stack.push(__e);
284 : }
285 : else
286 5519 : return false;
287 1037 : 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 6970 : _Compiler<_TraitsT>::
307 : _M_atom()
308 : {
309 6970 : if (_M_match_token(_ScannerT::_S_token_anychar))
310 : {
311 353 : if (!(_M_flags & regex_constants::ECMAScript))
312 0 : __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
313 : else
314 353 : __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
315 : }
316 6617 : else if (_M_try_char())
317 3921 : __INSERT_REGEX_MATCHER(_M_insert_char_matcher);
318 2696 : 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 2696 : else if (_M_match_token(_ScannerT::_S_token_quoted_class))
322 104 : __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
323 2592 : else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
324 : {
325 138 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_dummy());
326 138 : this->_M_disjunction();
327 138 : if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
328 0 : __throw_regex_error(regex_constants::error_paren,
329 : "Parenthesis is not closed.");
330 138 : __r._M_append(_M_pop());
331 138 : _M_stack.push(__r);
332 : }
333 2454 : else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
334 : {
335 648 : _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_subexpr_begin());
336 648 : this->_M_disjunction();
337 648 : if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
338 0 : __throw_regex_error(regex_constants::error_paren,
339 : "Parenthesis is not closed.");
340 648 : __r._M_append(_M_pop());
341 648 : __r._M_append(_M_nfa->_M_insert_subexpr_end());
342 648 : _M_stack.push(__r);
343 : }
344 1806 : else if (!_M_bracket_expression())
345 1451 : return false;
346 5519 : return true;
347 : }
348 :
349 : template<typename _TraitsT>
350 : bool
351 1806 : _Compiler<_TraitsT>::
352 : _M_bracket_expression()
353 : {
354 : bool __neg =
355 1806 : _M_match_token(_ScannerT::_S_token_bracket_neg_begin);
356 1806 : if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
357 1451 : return false;
358 355 : __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
359 355 : return true;
360 : }
361 : #undef __INSERT_REGEX_MATCHER
362 :
363 : template<typename _TraitsT>
364 : template<bool __icase, bool __collate>
365 : void
366 353 : _Compiler<_TraitsT>::
367 : _M_insert_any_matcher_ecma()
368 : {
369 353 : _M_stack.push(_StateSeqT(*_M_nfa,
370 353 : _M_nfa->_M_insert_matcher
371 353 : (_AnyMatcher<_TraitsT, true, __icase, __collate>
372 : (_M_traits))));
373 353 : }
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 3921 : _Compiler<_TraitsT>::
391 : _M_insert_char_matcher()
392 : {
393 3921 : _M_stack.push(_StateSeqT(*_M_nfa,
394 3921 : _M_nfa->_M_insert_matcher
395 11763 : (_CharMatcher<_TraitsT, __icase, __collate>
396 3921 : (_M_value[0], _M_traits))));
397 3921 : }
398 :
399 : template<typename _TraitsT>
400 : template<bool __icase, bool __collate>
401 : void
402 104 : _Compiler<_TraitsT>::
403 : _M_insert_character_class_matcher()
404 : {
405 104 : __glibcxx_assert(_M_value.size() == 1);
406 104 : _BracketMatcher<__icase, __collate> __matcher
407 104 : (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
408 104 : __matcher._M_add_character_class(_M_value, false);
409 104 : __matcher._M_ready();
410 104 : _M_stack.push(_StateSeqT(*_M_nfa,
411 104 : _M_nfa->_M_insert_matcher(std::move(__matcher))));
412 104 : }
413 :
414 : template<typename _TraitsT>
415 : template<bool __icase, bool __collate>
416 : void
417 355 : _Compiler<_TraitsT>::
418 : _M_insert_bracket_matcher(bool __neg)
419 : {
420 355 : _BracketMatcher<__icase, __collate> __matcher(__neg, _M_traits);
421 355 : _BracketState __last_char;
422 355 : if (_M_try_char())
423 192 : __last_char.set(_M_value[0]);
424 163 : 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 1950 : while (_M_expression_term(__last_char, __matcher))
428 : ;
429 355 : if (__last_char._M_is_char())
430 210 : __matcher._M_add_char(__last_char.get());
431 355 : __matcher._M_ready();
432 710 : _M_stack.push(_StateSeqT(
433 355 : *_M_nfa,
434 355 : _M_nfa->_M_insert_matcher(std::move(__matcher))));
435 355 : }
436 :
437 : template<typename _TraitsT>
438 : template<bool __icase, bool __collate>
439 : bool
440 1950 : _Compiler<_TraitsT>::
441 : _M_expression_term(_BracketState& __last_char,
442 : _BracketMatcher<__icase, __collate>& __matcher)
443 : {
444 1950 : if (_M_match_token(_ScannerT::_S_token_bracket_end))
445 355 : return false;
446 :
447 : // Add any previously cached char into the matcher and update cache.
448 5586 : const auto __push_char = [&](_CharT __ch)
449 : {
450 1088 : if (__last_char._M_is_char())
451 727 : __matcher._M_add_char(__last_char.get());
452 1088 : __last_char.set(__ch);
453 : };
454 : // Add any previously cached char into the matcher and update cache.
455 2081 : const auto __push_class = [&]
456 : {
457 162 : 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 162 : __last_char.reset(_BracketState::_Type::_Class);
462 : };
463 :
464 1595 : 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 1595 : 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 1595 : 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 1595 : else if (_M_try_char())
483 1088 : __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 507 : else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
495 : {
496 345 : 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 345 : 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 345 : else if (__last_char._M_is_char())
509 : {
510 345 : if (_M_try_char())
511 : {
512 : // "x-y"
513 345 : __matcher._M_make_range(__last_char.get(), _M_value[0]);
514 345 : __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 162 : else if (_M_match_token(_ScannerT::_S_token_quoted_class))
538 : {
539 162 : __push_class();
540 162 : __matcher._M_add_character_class(_M_value,
541 324 : _M_ctype.is(_CtypeT::upper,
542 162 : _M_value[0]));
543 : }
544 : else
545 0 : __throw_regex_error(regex_constants::error_brack,
546 : "Unexpected character in bracket expression.");
547 :
548 1595 : return true;
549 : }
550 :
551 : template<typename _TraitsT>
552 : bool
553 8912 : _Compiler<_TraitsT>::
554 : _M_try_char()
555 : {
556 8912 : bool __is_char = false;
557 8912 : 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 8912 : 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 8912 : else if (_M_match_token(_ScannerT::_S_token_ord_char))
568 5546 : __is_char = true;
569 8912 : return __is_char;
570 : }
571 :
572 : template<typename _TraitsT>
573 : bool
574 112266 : _Compiler<_TraitsT>::
575 : _M_match_token(_TokenT __token)
576 : {
577 112266 : if (__token == _M_scanner._M_get_token())
578 : {
579 11066 : _M_value = _M_scanner._M_get_value();
580 11066 : _M_scanner._M_advance();
581 11066 : return true;
582 : }
583 101200 : return false;
584 : }
585 :
586 : template<typename _TraitsT>
587 : int
588 196 : _Compiler<_TraitsT>::
589 : _M_cur_int_value(int __radix)
590 : {
591 196 : int __v = 0;
592 472 : for (_CharT __c : _M_value)
593 552 : if (__builtin_mul_overflow(__v, __radix, &__v)
594 276 : || __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 196 : return __v;
598 : }
599 :
600 : template<typename _TraitsT, bool __icase, bool __collate>
601 : bool
602 117504 : _BracketMatcher<_TraitsT, __icase, __collate>::
603 : _M_apply(_CharT __ch, false_type) const
604 : {
605 1282328 : return [this, __ch]
606 : {
607 117504 : if (std::binary_search(_M_char_set.begin(), _M_char_set.end(),
608 235008 : _M_translator._M_translate(__ch)))
609 937 : return true;
610 116567 : auto __s = _M_translator._M_transform(__ch);
611 191652 : for (auto& __it : _M_range_set)
612 81919 : if (_M_translator._M_match_range(__it.first, __it.second, __s))
613 6834 : return true;
614 109733 : if (_M_traits.isctype(__ch, _M_class_set))
615 8727 : return true;
616 202012 : if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
617 101006 : _M_traits.transform_primary(&__ch, &__ch+1))
618 303018 : != _M_equiv_set.end())
619 0 : return true;
620 101006 : for (auto& __it : _M_neg_class_set)
621 0 : if (!_M_traits.isctype(__ch, __it))
622 0 : return true;
623 101006 : return false;
624 117504 : }() ^ _M_is_non_matching;
625 : }
626 : } // namespace __detail
627 :
628 : _GLIBCXX_END_NAMESPACE_VERSION
629 : } // namespace
|
