Line data Source code
1 : // class template regex -*- C++ -*-
2 :
3 : // Copyright (C) 2010-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.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 368 : _M_get_nfa() noexcept
69 368 : { 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;
129 :
130 : void
131 1371 : set(_CharT __c) noexcept { _M_type = _Type::_Char; _M_char = __c; }
132 :
133 : _GLIBCXX_NODISCARD _CharT
134 1371 : get() const noexcept { return _M_char; }
135 :
136 : void
137 545 : 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 2081 : _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 379 : _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 14719 : _M_pop()
172 : {
173 14719 : auto ret = _M_stack.top();
174 14719 : _M_stack.pop();
175 14719 : return ret;
176 : }
177 :
178 : static _FlagT
179 368 : _S_validate(_FlagT __f)
180 : {
181 : using namespace regex_constants;
182 368 : switch (__f & (ECMAScript|basic|extended|awk|grep|egrep))
183 : {
184 368 : case ECMAScript:
185 : case basic:
186 : case extended:
187 : case awk:
188 : case grep:
189 : case egrep:
190 368 : return __f;
191 0 : case _FlagT(0):
192 0 : return __f | ECMAScript;
193 0 : default:
194 0 : std::__throw_regex_error(_S_grammar, "conflicting grammar options");
195 : }
196 0 : }
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 _RegexTranslatorBase
210 : {
211 : public:
212 : typedef typename _TraitsT::char_type _CharT;
213 : typedef typename _TraitsT::string_type _StringT;
214 : typedef _StringT _StrTransT;
215 :
216 : explicit
217 24 : _RegexTranslatorBase(const _TraitsT& __traits)
218 24 : : _M_traits(__traits)
219 24 : { }
220 :
221 : _CharT
222 1227 : _M_translate(_CharT __ch) const
223 : {
224 : if (__icase)
225 1227 : return _M_traits.translate_nocase(__ch);
226 : else if (__collate)
227 0 : return _M_traits.translate(__ch);
228 : else
229 : return __ch;
230 : }
231 :
232 : _StrTransT
233 0 : _M_transform(_CharT __ch) const
234 : {
235 0 : _StrTransT __str(1, __ch);
236 0 : return _M_traits.transform(__str.begin(), __str.end());
237 0 : }
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 0 : _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
244 : const _StrTransT& __s) const
245 0 : { return __first <= __s && __s <= __last; }
246 :
247 : protected:
248 0 : bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
249 : {
250 : typedef std::ctype<_CharT> __ctype_type;
251 0 : const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
252 0 : auto __lower = __fctyp.tolower(__ch);
253 0 : auto __upper = __fctyp.toupper(__ch);
254 0 : return (__first <= __lower && __lower <= __last)
255 0 : || (__first <= __upper && __upper <= __last);
256 : }
257 :
258 : const _TraitsT& _M_traits;
259 : };
260 :
261 : template<typename _TraitsT, bool __icase, bool __collate>
262 : class _RegexTranslator
263 : : public _RegexTranslatorBase<_TraitsT, __icase, __collate>
264 : {
265 : public:
266 : typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
267 : using _Base::_Base;
268 : };
269 :
270 : template<typename _TraitsT, bool __icase>
271 : class _RegexTranslator<_TraitsT, __icase, false>
272 : : public _RegexTranslatorBase<_TraitsT, __icase, false>
273 : {
274 : public:
275 : typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
276 : typedef typename _Base::_CharT _CharT;
277 : typedef _CharT _StrTransT;
278 :
279 : using _Base::_Base;
280 :
281 : _StrTransT
282 765 : _M_transform(_CharT __ch) const
283 765 : { return __ch; }
284 :
285 : bool
286 0 : _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
287 : {
288 : if (!__icase)
289 : return __first <= __ch && __ch <= __last;
290 0 : return this->_M_in_range_icase(__first, __last, __ch);
291 : }
292 : };
293 :
294 : template<typename _CharType>
295 : class _RegexTranslator<std::regex_traits<_CharType>, true, true>
296 : : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
297 : {
298 : public:
299 : typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
300 : _Base;
301 : typedef typename _Base::_CharT _CharT;
302 : typedef typename _Base::_StrTransT _StrTransT;
303 :
304 : using _Base::_Base;
305 :
306 : bool
307 0 : _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
308 : const _StrTransT& __str) const
309 : {
310 0 : __glibcxx_assert(__first.size() == 1);
311 0 : __glibcxx_assert(__last.size() == 1);
312 0 : __glibcxx_assert(__str.size() == 1);
313 0 : return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
314 : }
315 : };
316 :
317 : template<typename _TraitsT>
318 : class _RegexTranslator<_TraitsT, false, false>
319 : {
320 : public:
321 : typedef typename _TraitsT::char_type _CharT;
322 : typedef _CharT _StrTransT;
323 :
324 : explicit
325 4859 : _RegexTranslator(const _TraitsT&)
326 4859 : { }
327 :
328 : _CharT
329 1868728 : _M_translate(_CharT __ch) const
330 1868728 : { return __ch; }
331 :
332 : _StrTransT
333 124185 : _M_transform(_CharT __ch) const
334 124185 : { return __ch; }
335 :
336 : bool
337 90021 : _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
338 90021 : { return __first <= __ch && __ch <= __last; }
339 : };
340 :
341 : template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
342 : struct _AnyMatcher;
343 :
344 : template<typename _TraitsT, bool __icase, bool __collate>
345 : struct _AnyMatcher<_TraitsT, false, __icase, __collate>
346 : {
347 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
348 : typedef typename _TransT::_CharT _CharT;
349 :
350 : explicit
351 0 : _AnyMatcher(const _TraitsT& __traits)
352 0 : : _M_translator(__traits)
353 0 : { }
354 :
355 : bool
356 0 : operator()(_CharT __ch) const
357 : {
358 0 : static auto __nul = _M_translator._M_translate('\0');
359 0 : return _M_translator._M_translate(__ch) != __nul;
360 : }
361 :
362 : _TransT _M_translator;
363 : };
364 :
365 : template<typename _TraitsT, bool __icase, bool __collate>
366 : struct _AnyMatcher<_TraitsT, true, __icase, __collate>
367 : {
368 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
369 : typedef typename _TransT::_CharT _CharT;
370 :
371 : explicit
372 347 : _AnyMatcher(const _TraitsT& __traits)
373 347 : : _M_translator(__traits)
374 347 : { }
375 :
376 : bool
377 251747 : operator()(_CharT __ch) const
378 251747 : { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
379 :
380 : bool
381 251747 : _M_apply(_CharT __ch, true_type) const
382 : {
383 251747 : auto __c = _M_translator._M_translate(__ch);
384 251747 : auto __n = _M_translator._M_translate('\n');
385 251747 : auto __r = _M_translator._M_translate('\r');
386 251747 : return __c != __n && __c != __r;
387 : }
388 :
389 : bool
390 : _M_apply(_CharT __ch, false_type) const
391 : {
392 : auto __c = _M_translator._M_translate(__ch);
393 : auto __n = _M_translator._M_translate('\n');
394 : auto __r = _M_translator._M_translate('\r');
395 : auto __u2028 = _M_translator._M_translate(u'\u2028');
396 : auto __u2029 = _M_translator._M_translate(u'\u2029');
397 : return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
398 : }
399 :
400 : _TransT _M_translator;
401 : };
402 :
403 : template<typename _TraitsT, bool __icase, bool __collate>
404 : struct _CharMatcher
405 : {
406 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
407 : typedef typename _TransT::_CharT _CharT;
408 :
409 4047 : _CharMatcher(_CharT __ch, const _TraitsT& __traits)
410 4047 : : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
411 4047 : { }
412 :
413 : bool
414 984491 : operator()(_CharT __ch) const
415 984491 : { return _M_ch == _M_translator._M_translate(__ch); }
416 :
417 : _TransT _M_translator;
418 : _CharT _M_ch;
419 : };
420 :
421 : /// Matches a character range (bracket expression)
422 : template<typename _TraitsT, bool __icase, bool __collate>
423 : struct _BracketMatcher
424 : {
425 : public:
426 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
427 : typedef typename _TransT::_CharT _CharT;
428 : typedef typename _TransT::_StrTransT _StrTransT;
429 : typedef typename _TraitsT::string_type _StringT;
430 : typedef typename _TraitsT::char_class_type _CharClassT;
431 :
432 : public:
433 489 : _BracketMatcher(bool __is_non_matching,
434 : const _TraitsT& __traits)
435 489 : : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
436 978 : _M_is_non_matching(__is_non_matching)
437 489 : { }
438 :
439 : bool
440 114522 : operator()(_CharT __ch) const
441 : {
442 : _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
443 114522 : return _M_apply(__ch, _UseCache());
444 : }
445 :
446 : void
447 992 : _M_add_char(_CharT __c)
448 : {
449 992 : _M_char_set.push_back(_M_translator._M_translate(__c));
450 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
451 992 : }
452 :
453 : _StringT
454 0 : _M_add_collate_element(const _StringT& __s)
455 : {
456 0 : auto __st = _M_traits.lookup_collatename(__s.data(),
457 0 : __s.data() + __s.size());
458 0 : if (__st.empty())
459 0 : __throw_regex_error(regex_constants::error_collate,
460 : "Invalid collate element.");
461 0 : _M_char_set.push_back(_M_translator._M_translate(__st[0]));
462 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
463 0 : return __st;
464 0 : }
465 :
466 : void
467 0 : _M_add_equivalence_class(const _StringT& __s)
468 : {
469 0 : auto __st = _M_traits.lookup_collatename(__s.data(),
470 0 : __s.data() + __s.size());
471 0 : if (__st.empty())
472 0 : __throw_regex_error(regex_constants::error_collate,
473 : "Invalid equivalence class.");
474 0 : __st = _M_traits.transform_primary(__st.data(),
475 0 : __st.data() + __st.size());
476 0 : _M_equiv_set.push_back(__st);
477 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
478 0 : }
479 :
480 : // __neg should be true for \D, \S and \W only.
481 : void
482 255 : _M_add_character_class(const _StringT& __s, bool __neg)
483 : {
484 255 : auto __mask = _M_traits.lookup_classname(__s.data(),
485 255 : __s.data() + __s.size(),
486 : __icase);
487 255 : if (__mask == 0)
488 0 : __throw_regex_error(regex_constants::error_collate,
489 : "Invalid character class.");
490 255 : if (!__neg)
491 255 : _M_class_set |= __mask;
492 : else
493 0 : _M_neg_class_set.push_back(__mask);
494 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
495 255 : }
496 :
497 : void
498 379 : _M_make_range(_CharT __l, _CharT __r)
499 : {
500 379 : if (__l > __r)
501 0 : __throw_regex_error(regex_constants::error_range,
502 : "Invalid range in bracket expression.");
503 379 : _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
504 379 : _M_translator._M_transform(__r)));
505 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
506 379 : }
507 :
508 : void
509 489 : _M_ready()
510 : {
511 489 : std::sort(_M_char_set.begin(), _M_char_set.end());
512 489 : auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
513 489 : _M_char_set.erase(__end, _M_char_set.end());
514 489 : _M_make_cache(_UseCache());
515 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
516 489 : }
517 :
518 : private:
519 : // Currently we only use the cache for char
520 : typedef typename std::is_same<_CharT, char>::type _UseCache;
521 :
522 : static constexpr size_t
523 : _S_cache_size =
524 : 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
525 :
526 : struct _Dummy { };
527 : typedef typename std::conditional<_UseCache::value,
528 : std::bitset<_S_cache_size>,
529 : _Dummy>::type _CacheT;
530 : typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
531 :
532 : bool
533 : _M_apply(_CharT __ch, false_type) const;
534 :
535 : bool
536 114522 : _M_apply(_CharT __ch, true_type) const
537 114522 : { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
538 :
539 : void
540 489 : _M_make_cache(true_type)
541 : {
542 125673 : for (unsigned __i = 0; __i < _M_cache.size(); __i++)
543 125184 : _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
544 489 : }
545 :
546 : void
547 : _M_make_cache(false_type)
548 : { }
549 :
550 : private:
551 : std::vector<_CharT> _M_char_set;
552 : std::vector<_StringT> _M_equiv_set;
553 : std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
554 : std::vector<_CharClassT> _M_neg_class_set;
555 : _CharClassT _M_class_set;
556 : _TransT _M_translator;
557 : const _TraitsT& _M_traits;
558 : bool _M_is_non_matching;
559 : _CacheT _M_cache;
560 : #ifdef _GLIBCXX_DEBUG
561 : bool _M_is_ready = false;
562 : #endif
563 : };
564 :
565 : ///@} regex-detail
566 : } // namespace __detail
567 : _GLIBCXX_END_NAMESPACE_VERSION
568 : } // namespace std
569 :
570 : #include <bits/regex_compiler.tcc>
|
