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