1 | // class template regex -*- C++ -*- |
2 | |
3 | // Copyright (C) 2010-2024 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 | |
31 | namespace std _GLIBCXX_VISIBILITY(default) |
32 | { |
33 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
34 | _GLIBCXX_BEGIN_NAMESPACE_CXX11 |
35 | |
36 | template<typename> |
37 | class regex_traits; |
38 | |
39 | _GLIBCXX_END_NAMESPACE_CXX11 |
40 | |
41 | namespace __detail |
42 | { |
43 | /** |
44 | * @addtogroup regex-detail |
45 | * @{ |
46 | */ |
47 | |
48 | template<typename, bool, bool> |
49 | struct _BracketMatcher; |
50 | |
51 | /** |
52 | * @brief Builds an NFA from an input iterator range. |
53 | * |
54 | * The %_TraitsT type should fulfill requirements [28.3]. |
55 | */ |
56 | template<typename _TraitsT> |
57 | class _Compiler |
58 | { |
59 | public: |
60 | typedef typename _TraitsT::char_type _CharT; |
61 | typedef _NFA<_TraitsT> _RegexT; |
62 | typedef regex_constants::syntax_option_type _FlagT; |
63 | |
64 | _Compiler(const _CharT* __b, const _CharT* __e, |
65 | const typename _TraitsT::locale_type& __traits, _FlagT __flags); |
66 | |
67 | shared_ptr<const _RegexT> |
68 | _M_get_nfa() noexcept |
69 | { return std::move(_M_nfa); } |
70 | |
71 | private: |
72 | typedef _Scanner<_CharT> _ScannerT; |
73 | typedef typename _TraitsT::string_type _StringT; |
74 | typedef typename _ScannerT::_TokenT _TokenT; |
75 | typedef _StateSeq<_TraitsT> _StateSeqT; |
76 | typedef std::stack<_StateSeqT> _StackT; |
77 | typedef std::ctype<_CharT> _CtypeT; |
78 | |
79 | // accepts a specific token or returns false. |
80 | bool |
81 | _M_match_token(_TokenT __token); |
82 | |
83 | void |
84 | _M_disjunction(); |
85 | |
86 | void |
87 | _M_alternative(); |
88 | |
89 | bool |
90 | _M_term(); |
91 | |
92 | bool |
93 | _M_assertion(); |
94 | |
95 | bool |
96 | _M_quantifier(); |
97 | |
98 | bool |
99 | _M_atom(); |
100 | |
101 | bool |
102 | _M_bracket_expression(); |
103 | |
104 | template<bool __icase, bool __collate> |
105 | void |
106 | _M_insert_any_matcher_ecma(); |
107 | |
108 | template<bool __icase, bool __collate> |
109 | void |
110 | _M_insert_any_matcher_posix(); |
111 | |
112 | template<bool __icase, bool __collate> |
113 | void |
114 | _M_insert_char_matcher(); |
115 | |
116 | template<bool __icase, bool __collate> |
117 | void |
118 | _M_insert_character_class_matcher(); |
119 | |
120 | template<bool __icase, bool __collate> |
121 | void |
122 | _M_insert_bracket_matcher(bool __neg); |
123 | |
124 | // Cache of the last atom seen in a bracketed range expression. |
125 | struct _BracketState |
126 | { |
127 | enum class _Type : char { _None, _Char, _Class } _M_type = _Type::_None; |
128 | _CharT _M_char = _CharT(); |
129 | |
130 | void |
131 | set(_CharT __c) noexcept { _M_type = _Type::_Char; _M_char = __c; } |
132 | |
133 | _GLIBCXX_NODISCARD _CharT |
134 | get() const noexcept { return _M_char; } |
135 | |
136 | void |
137 | reset(_Type __t = _Type::_None) noexcept { _M_type = __t; } |
138 | |
139 | explicit operator bool() const noexcept |
140 | { return _M_type != _Type::_None; } |
141 | |
142 | // Previous token was a single character. |
143 | _GLIBCXX_NODISCARD bool |
144 | _M_is_char() const noexcept { return _M_type == _Type::_Char; } |
145 | |
146 | // Previous token was a character class, equivalent class, |
147 | // collating symbol etc. |
148 | _GLIBCXX_NODISCARD bool |
149 | _M_is_class() const noexcept { return _M_type == _Type::_Class; } |
150 | }; |
151 | |
152 | template<bool __icase, bool __collate> |
153 | using _BracketMatcher |
154 | = std::__detail::_BracketMatcher<_TraitsT, __icase, __collate>; |
155 | |
156 | // Returns true if successfully parsed one term and should continue |
157 | // compiling a bracket expression. |
158 | // Returns false if the compiler should move on. |
159 | template<bool __icase, bool __collate> |
160 | bool |
161 | _M_expression_term(_BracketState& __last_char, |
162 | _BracketMatcher<__icase, __collate>& __matcher); |
163 | |
164 | int |
165 | _M_cur_int_value(int __radix); |
166 | |
167 | bool |
168 | _M_try_char(); |
169 | |
170 | _StateSeqT |
171 | _M_pop() |
172 | { |
173 | auto ret = _M_stack.top(); |
174 | _M_stack.pop(); |
175 | return ret; |
176 | } |
177 | |
178 | static _FlagT |
179 | _S_validate(_FlagT __f) |
180 | { |
181 | using namespace regex_constants; |
182 | switch (__f & (ECMAScript|basic|extended|awk|grep|egrep)) |
183 | { |
184 | case ECMAScript: |
185 | case basic: |
186 | case extended: |
187 | case awk: |
188 | case grep: |
189 | case egrep: |
190 | return __f; |
191 | case _FlagT(0): |
192 | return __f | ECMAScript; |
193 | default: |
194 | std::__throw_regex_error(ecode: _S_grammar, what: "conflicting grammar options" ); |
195 | } |
196 | } |
197 | |
198 | _FlagT _M_flags; |
199 | _ScannerT _M_scanner; |
200 | shared_ptr<_RegexT> _M_nfa; |
201 | _StringT _M_value; |
202 | _StackT _M_stack; |
203 | const _TraitsT& _M_traits; |
204 | const _CtypeT& _M_ctype; |
205 | }; |
206 | |
207 | // [28.13.14] |
208 | template<typename _TraitsT, bool __icase, bool __collate> |
209 | class |
210 | { |
211 | public: |
212 | typedef typename _TraitsT::char_type ; |
213 | typedef typename _TraitsT::string_type ; |
214 | typedef _StringT ; |
215 | |
216 | explicit |
217 | (const _TraitsT& __traits) |
218 | : _M_traits(__traits) |
219 | { } |
220 | |
221 | _CharT |
222 | (_CharT __ch) const |
223 | { |
224 | if _GLIBCXX17_CONSTEXPR (__icase) |
225 | return _M_traits.translate_nocase(__ch); |
226 | else if _GLIBCXX17_CONSTEXPR (__collate) |
227 | return _M_traits.translate(__ch); |
228 | else |
229 | return __ch; |
230 | } |
231 | |
232 | _StrTransT |
233 | (_CharT __ch) const |
234 | { |
235 | _StrTransT __str(1, __ch); |
236 | return _M_traits.transform(__str.begin(), __str.end()); |
237 | } |
238 | |
239 | // See LWG 523. It's not efficiently implementable when _TraitsT is not |
240 | // std::regex_traits<>, and __collate is true. See specializations for |
241 | // implementations of other cases. |
242 | bool |
243 | (const _StrTransT& __first, const _StrTransT& __last, |
244 | const _StrTransT& __s) const |
245 | { return __first <= __s && __s <= __last; } |
246 | |
247 | protected: |
248 | bool (_CharT __first, _CharT __last, _CharT __ch) const |
249 | { |
250 | typedef std::ctype<_CharT> __ctype_type; |
251 | const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc()); |
252 | auto __lower = __fctyp.tolower(__ch); |
253 | auto __upper = __fctyp.toupper(__ch); |
254 | return (__first <= __lower && __lower <= __last) |
255 | || (__first <= __upper && __upper <= __last); |
256 | } |
257 | |
258 | const _TraitsT& ; |
259 | }; |
260 | |
261 | template<typename _TraitsT, bool __icase, bool __collate> |
262 | class |
263 | : public _RegexTranslatorBase<_TraitsT, __icase, __collate> |
264 | { |
265 | public: |
266 | typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> ; |
267 | using _Base::_Base; |
268 | }; |
269 | |
270 | template<typename _TraitsT, bool __icase> |
271 | class <_TraitsT, __icase, false> |
272 | : public _RegexTranslatorBase<_TraitsT, __icase, false> |
273 | { |
274 | public: |
275 | typedef _RegexTranslatorBase<_TraitsT, __icase, false> ; |
276 | typedef typename _Base::_CharT ; |
277 | typedef _CharT ; |
278 | |
279 | using _Base::_Base; |
280 | |
281 | _StrTransT |
282 | (_CharT __ch) const |
283 | { return __ch; } |
284 | |
285 | bool |
286 | (_CharT __first, _CharT __last, _CharT __ch) const |
287 | { |
288 | if _GLIBCXX17_CONSTEXPR (!__icase) |
289 | return __first <= __ch && __ch <= __last; |
290 | else |
291 | return this->_M_in_range_icase(__first, __last, __ch); |
292 | } |
293 | }; |
294 | |
295 | template<typename _CharType> |
296 | class <std::regex_traits<_CharType>, true, true> |
297 | : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true> |
298 | { |
299 | public: |
300 | typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true> |
301 | ; |
302 | typedef typename _Base::_CharT ; |
303 | typedef typename _Base::_StrTransT ; |
304 | |
305 | using _Base::_Base; |
306 | |
307 | bool |
308 | (const _StrTransT& __first, const _StrTransT& __last, |
309 | const _StrTransT& __str) const |
310 | { |
311 | __glibcxx_assert(__first.size() == 1); |
312 | __glibcxx_assert(__last.size() == 1); |
313 | __glibcxx_assert(__str.size() == 1); |
314 | return this->_M_in_range_icase(__first[0], __last[0], __str[0]); |
315 | } |
316 | }; |
317 | |
318 | template<typename _TraitsT> |
319 | class <_TraitsT, false, false> |
320 | { |
321 | public: |
322 | typedef typename _TraitsT::char_type ; |
323 | typedef _CharT ; |
324 | |
325 | explicit |
326 | (const _TraitsT&) |
327 | { } |
328 | |
329 | _CharT |
330 | (_CharT __ch) const |
331 | { return __ch; } |
332 | |
333 | _StrTransT |
334 | (_CharT __ch) const |
335 | { return __ch; } |
336 | |
337 | bool |
338 | (_CharT __first, _CharT __last, _CharT __ch) const |
339 | { return __first <= __ch && __ch <= __last; } |
340 | }; |
341 | |
342 | template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate> |
343 | struct _AnyMatcher; |
344 | |
345 | template<typename _TraitsT, bool __icase, bool __collate> |
346 | struct _AnyMatcher<_TraitsT, false, __icase, __collate> |
347 | { |
348 | typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; |
349 | typedef typename _TransT::_CharT _CharT; |
350 | |
351 | explicit |
352 | _AnyMatcher(const _TraitsT& __traits) |
353 | : _M_translator(__traits) |
354 | { } |
355 | |
356 | bool |
357 | (_CharT __ch) const |
358 | { |
359 | static auto __nul = _M_translator._M_translate('\0'); |
360 | return _M_translator._M_translate(__ch) != __nul; |
361 | } |
362 | |
363 | _TransT _M_translator; |
364 | }; |
365 | |
366 | template<typename _TraitsT, bool __icase, bool __collate> |
367 | struct _AnyMatcher<_TraitsT, true, __icase, __collate> |
368 | { |
369 | typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; |
370 | typedef typename _TransT::_CharT _CharT; |
371 | |
372 | explicit |
373 | _AnyMatcher(const _TraitsT& __traits) |
374 | : _M_translator(__traits) |
375 | { } |
376 | |
377 | bool |
378 | (_CharT __ch) const |
379 | { return _M_apply(__ch, typename is_same<_CharT, char>::type()); } |
380 | |
381 | bool |
382 | (_CharT __ch, true_type) const |
383 | { |
384 | auto __c = _M_translator._M_translate(__ch); |
385 | auto __n = _M_translator._M_translate('\n'); |
386 | auto __r = _M_translator._M_translate('\r'); |
387 | return __c != __n && __c != __r; |
388 | } |
389 | |
390 | bool |
391 | (_CharT __ch, false_type) const |
392 | { |
393 | auto __c = _M_translator._M_translate(__ch); |
394 | auto __n = _M_translator._M_translate('\n'); |
395 | auto __r = _M_translator._M_translate('\r'); |
396 | auto __u2028 = _M_translator._M_translate(u'\u2028'); |
397 | auto __u2029 = _M_translator._M_translate(u'\u2029'); |
398 | return __c != __n && __c != __r && __c != __u2028 && __c != __u2029; |
399 | } |
400 | |
401 | _TransT _M_translator; |
402 | }; |
403 | |
404 | template<typename _TraitsT, bool __icase, bool __collate> |
405 | struct _CharMatcher |
406 | { |
407 | typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; |
408 | typedef typename _TransT::_CharT _CharT; |
409 | |
410 | (_CharT __ch, const _TraitsT& __traits) |
411 | : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch)) |
412 | { } |
413 | |
414 | bool |
415 | (_CharT __ch) const |
416 | { return _M_ch == _M_translator._M_translate(__ch); } |
417 | |
418 | _TransT _M_translator; |
419 | _CharT _M_ch; |
420 | }; |
421 | |
422 | /// Matches a character range (bracket expression) |
423 | template<typename _TraitsT, bool __icase, bool __collate> |
424 | struct _BracketMatcher |
425 | { |
426 | public: |
427 | typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; |
428 | typedef typename _TransT::_CharT _CharT; |
429 | typedef typename _TransT::_StrTransT _StrTransT; |
430 | typedef typename _TraitsT::string_type _StringT; |
431 | typedef typename _TraitsT::char_class_type _CharClassT; |
432 | |
433 | public: |
434 | _BracketMatcher(bool __is_non_matching, |
435 | const _TraitsT& __traits) |
436 | : _M_class_set(0), _M_translator(__traits), _M_traits(__traits), |
437 | _M_is_non_matching(__is_non_matching) |
438 | { } |
439 | |
440 | bool |
441 | (_CharT __ch) const |
442 | { |
443 | _GLIBCXX_DEBUG_ASSERT(_M_is_ready); |
444 | return _M_apply(__ch, _UseCache()); |
445 | } |
446 | |
447 | void |
448 | (_CharT __c) |
449 | { |
450 | _M_char_set.push_back(_M_translator._M_translate(__c)); |
451 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); |
452 | } |
453 | |
454 | _StringT |
455 | _M_add_collate_element(const _StringT& __s) |
456 | { |
457 | auto __st = _M_traits.lookup_collatename(__s.data(), |
458 | __s.data() + __s.size()); |
459 | if (__st.empty()) |
460 | __throw_regex_error(ecode: regex_constants::error_collate, |
461 | what: "Invalid collate element." ); |
462 | _M_char_set.push_back(_M_translator._M_translate(__st[0])); |
463 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); |
464 | return __st; |
465 | } |
466 | |
467 | void |
468 | _M_add_equivalence_class(const _StringT& __s) |
469 | { |
470 | auto __st = _M_traits.lookup_collatename(__s.data(), |
471 | __s.data() + __s.size()); |
472 | if (__st.empty()) |
473 | __throw_regex_error(ecode: regex_constants::error_collate, |
474 | what: "Invalid equivalence class." ); |
475 | __st = _M_traits.transform_primary(__st.data(), |
476 | __st.data() + __st.size()); |
477 | _M_equiv_set.push_back(__st); |
478 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); |
479 | } |
480 | |
481 | // __neg should be true for \D, \S and \W only. |
482 | void |
483 | _M_add_character_class(const _StringT& __s, bool __neg) |
484 | { |
485 | auto __mask = _M_traits.lookup_classname(__s.data(), |
486 | __s.data() + __s.size(), |
487 | __icase); |
488 | if (__mask == 0) |
489 | __throw_regex_error(ecode: regex_constants::error_collate, |
490 | what: "Invalid character class." ); |
491 | if (!__neg) |
492 | _M_class_set |= __mask; |
493 | else |
494 | _M_neg_class_set.push_back(__mask); |
495 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); |
496 | } |
497 | |
498 | void |
499 | (_CharT __l, _CharT __r) |
500 | { |
501 | if (__l > __r) |
502 | __throw_regex_error(ecode: regex_constants::error_range, |
503 | what: "Invalid range in bracket expression." ); |
504 | _M_range_set.push_back(make_pair(_M_translator._M_transform(__l), |
505 | _M_translator._M_transform(__r))); |
506 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); |
507 | } |
508 | |
509 | void |
510 | _M_ready() |
511 | { |
512 | std::sort(_M_char_set.begin(), _M_char_set.end()); |
513 | auto __end = std::unique(_M_char_set.begin(), _M_char_set.end()); |
514 | _M_char_set.erase(__end, _M_char_set.end()); |
515 | _M_make_cache(_UseCache()); |
516 | _GLIBCXX_DEBUG_ONLY(_M_is_ready = true); |
517 | } |
518 | |
519 | private: |
520 | // Currently we only use the cache for char |
521 | using _UseCache = typename std::is_same<_CharT, char>::type; |
522 | |
523 | static constexpr size_t |
524 | _S_cache_size = |
525 | 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value)); |
526 | |
527 | struct _Dummy { }; |
528 | using _CacheT = std::__conditional_t<_UseCache::value, |
529 | std::bitset<_S_cache_size>, |
530 | _Dummy>; |
531 | using _UnsignedCharT = typename std::make_unsigned<_CharT>::type; |
532 | |
533 | bool |
534 | (_CharT __ch, false_type) const; |
535 | |
536 | bool |
537 | (_CharT __ch, true_type) const |
538 | { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; } |
539 | |
540 | void |
541 | _M_make_cache(true_type) |
542 | { |
543 | for (unsigned __i = 0; __i < _M_cache.size(); __i++) |
544 | _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type()); |
545 | } |
546 | |
547 | void |
548 | _M_make_cache(false_type) |
549 | { } |
550 | |
551 | private: |
552 | _GLIBCXX_STD_C::vector<_CharT> _M_char_set; |
553 | _GLIBCXX_STD_C::vector<_StringT> _M_equiv_set; |
554 | _GLIBCXX_STD_C::vector<pair<_StrTransT, _StrTransT>> _M_range_set; |
555 | _GLIBCXX_STD_C::vector<_CharClassT> _M_neg_class_set; |
556 | _CharClassT _M_class_set; |
557 | _TransT _M_translator; |
558 | const _TraitsT& _M_traits; |
559 | bool _M_is_non_matching; |
560 | _CacheT _M_cache; |
561 | #ifdef _GLIBCXX_DEBUG |
562 | bool _M_is_ready = false; |
563 | #endif |
564 | }; |
565 | |
566 | ///@} regex-detail |
567 | } // namespace __detail |
568 | _GLIBCXX_END_NAMESPACE_VERSION |
569 | } // namespace std |
570 | |
571 | #include <bits/regex_compiler.tcc> |
572 | |