Line data Source code
1 : // class template regex -*- C++ -*-
2 :
3 : // Copyright (C) 2010-2018 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 0 : _M_get_nfa()
70 0 : { 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 : // Cache of the last atom seen in a bracketed range expression.
126 : struct _BracketState
127 : {
128 : enum class _Type : char { _None, _Char, _Class } _M_type = _Type::_None;
129 : _CharT _M_char;
130 :
131 : void
132 523 : set(_CharT __c) noexcept { _M_type = _Type::_Char; _M_char = __c; }
133 :
134 : _GLIBCXX_NODISCARD _CharT
135 523 : get() const noexcept { return _M_char; }
136 :
137 : void
138 210 : reset(_Type __t = _Type::_None) noexcept { _M_type = __t; }
139 :
140 : explicit operator bool() const noexcept
141 : { return _M_type != _Type::_None; }
142 :
143 : // Previous token was a single character.
144 : _GLIBCXX_NODISCARD bool
145 769 : _M_is_char() const noexcept { return _M_type == _Type::_Char; }
146 :
147 : // Previous token was a character class, equivalent class,
148 : // collating symbol etc.
149 : _GLIBCXX_NODISCARD bool
150 174 : _M_is_class() const noexcept { return _M_type == _Type::_Class; }
151 : };
152 :
153 : template<bool __icase, bool __collate>
154 : using _BracketMatcher
155 : = std::__detail::_BracketMatcher<_TraitsT, __icase, __collate>;
156 :
157 : // Returns true if successfully parsed one term and should continue
158 : // compiling a bracket expression.
159 : // Returns false if the compiler should move on.
160 : template<bool __icase, bool __collate>
161 : bool
162 : _M_expression_term(_BracketState& __last_char,
163 : _BracketMatcher<__icase, __collate>& __matcher);
164 :
165 : int
166 : _M_cur_int_value(int __radix);
167 :
168 : bool
169 : _M_try_char();
170 :
171 : _StateSeqT
172 5077949 : _M_pop()
173 : {
174 5077949 : auto ret = _M_stack.top();
175 5077949 : _M_stack.pop();
176 5077949 : return ret;
177 : }
178 :
179 : _FlagT _M_flags;
180 : _ScannerT _M_scanner;
181 : shared_ptr<_RegexT> _M_nfa;
182 : _StringT _M_value;
183 : _StackT _M_stack;
184 : const _TraitsT& _M_traits;
185 : const _CtypeT& _M_ctype;
186 : };
187 :
188 : template<typename _Tp>
189 : struct __has_contiguous_iter : std::false_type { };
190 :
191 : template<typename _Ch, typename _Tr, typename _Alloc>
192 : struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
193 : : std::true_type
194 : { };
195 :
196 : template<typename _Tp, typename _Alloc>
197 : struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
198 : : std::true_type
199 : { };
200 :
201 : template<typename _Tp>
202 : struct __is_contiguous_normal_iter : std::false_type { };
203 :
204 : template<typename _CharT>
205 : struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
206 :
207 : template<typename _Tp, typename _Cont>
208 : struct
209 : __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
210 : : __has_contiguous_iter<_Cont>::type
211 : { };
212 :
213 : template<typename _Iter, typename _TraitsT>
214 : using __enable_if_contiguous_normal_iter
215 : = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
216 : std::shared_ptr<const _NFA<_TraitsT>> >::type;
217 :
218 : template<typename _Iter, typename _TraitsT>
219 : using __disable_if_contiguous_normal_iter
220 : = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
221 : std::shared_ptr<const _NFA<_TraitsT>> >::type;
222 :
223 : template<typename _TraitsT, typename _FwdIter>
224 : inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
225 0 : __compile_nfa(_FwdIter __first, _FwdIter __last,
226 : const typename _TraitsT::locale_type& __loc,
227 : regex_constants::syntax_option_type __flags)
228 : {
229 0 : size_t __len = __last - __first;
230 0 : const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
231 : using _Cmplr = _Compiler<_TraitsT>;
232 0 : return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
233 : }
234 :
235 : template<typename _TraitsT, typename _FwdIter>
236 : inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
237 : __compile_nfa(_FwdIter __first, _FwdIter __last,
238 : const typename _TraitsT::locale_type& __loc,
239 : regex_constants::syntax_option_type __flags)
240 : {
241 : const basic_string<typename _TraitsT::char_type> __str(__first, __last);
242 : return __compile_nfa<_TraitsT>(__str.data(), __str.data() + __str.size(),
243 : __loc, __flags);
244 : }
245 :
246 : // [28.13.14]
247 : template<typename _TraitsT, bool __icase, bool __collate>
248 : class _RegexTranslatorBase
249 : {
250 : public:
251 : typedef typename _TraitsT::char_type _CharT;
252 : typedef typename _TraitsT::string_type _StringT;
253 : typedef _StringT _StrTransT;
254 :
255 : explicit
256 0 : _RegexTranslatorBase(const _TraitsT& __traits)
257 0 : : _M_traits(__traits)
258 0 : { }
259 :
260 : _CharT
261 0 : _M_translate(_CharT __ch) const
262 : {
263 : if (__icase)
264 0 : return _M_traits.translate_nocase(__ch);
265 : else if (__collate)
266 0 : return _M_traits.translate(__ch);
267 : else
268 : return __ch;
269 : }
270 :
271 : _StrTransT
272 0 : _M_transform(_CharT __ch) const
273 : {
274 0 : _StrTransT __str(1, __ch);
275 0 : return _M_traits.transform(__str.begin(), __str.end());
276 : }
277 :
278 : // See LWG 523. It's not efficiently implementable when _TraitsT is not
279 : // std::regex_traits<>, and __collate is true. See specializations for
280 : // implementations of other cases.
281 : bool
282 0 : _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
283 : const _StrTransT& __s) const
284 0 : { return __first <= __s && __s <= __last; }
285 :
286 : protected:
287 0 : bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
288 : {
289 : typedef std::ctype<_CharT> __ctype_type;
290 0 : const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
291 0 : auto __lower = __fctyp.tolower(__ch);
292 0 : auto __upper = __fctyp.toupper(__ch);
293 0 : return (__first <= __lower && __lower <= __last)
294 0 : || (__first <= __upper && __upper <= __last);
295 : }
296 :
297 : const _TraitsT& _M_traits;
298 : };
299 :
300 : template<typename _TraitsT, bool __icase, bool __collate>
301 : class _RegexTranslator
302 : : public _RegexTranslatorBase<_TraitsT, __icase, __collate>
303 : {
304 : public:
305 : typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
306 : using _Base::_Base;
307 : };
308 :
309 : template<typename _TraitsT, bool __icase>
310 : class _RegexTranslator<_TraitsT, __icase, false>
311 : : public _RegexTranslatorBase<_TraitsT, __icase, false>
312 : {
313 : public:
314 : typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
315 : typedef typename _Base::_CharT _CharT;
316 : typedef _CharT _StrTransT;
317 :
318 : using _Base::_Base;
319 :
320 : _StrTransT
321 0 : _M_transform(_CharT __ch) const
322 0 : { return __ch; }
323 :
324 : bool
325 0 : _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
326 : {
327 : if (!__icase)
328 : return __first <= __ch && __ch <= __last;
329 0 : return this->_M_in_range_icase(__first, __last, __ch);
330 : }
331 : };
332 :
333 : template<typename _CharType>
334 : class _RegexTranslator<std::regex_traits<_CharType>, true, true>
335 : : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
336 : {
337 : public:
338 : typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
339 : _Base;
340 : typedef typename _Base::_CharT _CharT;
341 : typedef typename _Base::_StrTransT _StrTransT;
342 :
343 : using _Base::_Base;
344 :
345 : bool
346 0 : _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
347 : const _StrTransT& __str) const
348 : {
349 : __glibcxx_assert(__first.size() == 1);
350 : __glibcxx_assert(__last.size() == 1);
351 : __glibcxx_assert(__str.size() == 1);
352 0 : return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
353 : }
354 : };
355 :
356 : template<typename _TraitsT>
357 : class _RegexTranslator<_TraitsT, false, false>
358 : {
359 : public:
360 : typedef typename _TraitsT::char_type _CharT;
361 : typedef _CharT _StrTransT;
362 :
363 : explicit
364 2231101 : _RegexTranslator(const _TraitsT&)
365 2231101 : { }
366 :
367 : _CharT
368 2447392 : _M_translate(_CharT __ch) const
369 2447392 : { return __ch; }
370 :
371 : _StrTransT
372 66047 : _M_transform(_CharT __ch) const
373 66047 : { return __ch; }
374 :
375 : bool
376 42934 : _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
377 42934 : { return __first <= __ch && __ch <= __last; }
378 : };
379 :
380 : template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
381 : struct _AnyMatcher;
382 :
383 : template<typename _TraitsT, bool __icase, bool __collate>
384 : struct _AnyMatcher<_TraitsT, false, __icase, __collate>
385 : {
386 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
387 : typedef typename _TransT::_CharT _CharT;
388 :
389 : explicit
390 0 : _AnyMatcher(const _TraitsT& __traits)
391 0 : : _M_translator(__traits)
392 0 : { }
393 :
394 : bool
395 0 : operator()(_CharT __ch) const
396 : {
397 0 : static auto __nul = _M_translator._M_translate('\0');
398 0 : return _M_translator._M_translate(__ch) != __nul;
399 : }
400 :
401 : _TransT _M_translator;
402 : };
403 :
404 : template<typename _TraitsT, bool __icase, bool __collate>
405 : struct _AnyMatcher<_TraitsT, true, __icase, __collate>
406 : {
407 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
408 : typedef typename _TransT::_CharT _CharT;
409 :
410 : explicit
411 73 : _AnyMatcher(const _TraitsT& __traits)
412 73 : : _M_translator(__traits)
413 73 : { }
414 :
415 : bool
416 2522 : operator()(_CharT __ch) const
417 2522 : { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
418 :
419 : bool
420 2522 : _M_apply(_CharT __ch, true_type) const
421 : {
422 2522 : auto __c = _M_translator._M_translate(__ch);
423 2522 : auto __n = _M_translator._M_translate('\n');
424 2522 : auto __r = _M_translator._M_translate('\r');
425 2522 : return __c != __n && __c != __r;
426 : }
427 :
428 : bool
429 : _M_apply(_CharT __ch, false_type) const
430 : {
431 : auto __c = _M_translator._M_translate(__ch);
432 : auto __n = _M_translator._M_translate('\n');
433 : auto __r = _M_translator._M_translate('\r');
434 : auto __u2028 = _M_translator._M_translate(u'\u2028');
435 : auto __u2029 = _M_translator._M_translate(u'\u2029');
436 : return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
437 : }
438 :
439 : _TransT _M_translator;
440 : };
441 :
442 : template<typename _TraitsT, bool __icase, bool __collate>
443 : struct _CharMatcher
444 : {
445 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
446 : typedef typename _TransT::_CharT _CharT;
447 :
448 2230770 : _CharMatcher(_CharT __ch, const _TraitsT& __traits)
449 2230770 : : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
450 2230770 : { }
451 :
452 : bool
453 142659 : operator()(_CharT __ch) const
454 142659 : { return _M_ch == _M_translator._M_translate(__ch); }
455 :
456 : _TransT _M_translator;
457 : _CharT _M_ch;
458 : };
459 :
460 : /// Matches a character range (bracket expression)
461 : template<typename _TraitsT, bool __icase, bool __collate>
462 : struct _BracketMatcher
463 : {
464 : public:
465 : typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
466 : typedef typename _TransT::_CharT _CharT;
467 : typedef typename _TransT::_StrTransT _StrTransT;
468 : typedef typename _TraitsT::string_type _StringT;
469 : typedef typename _TraitsT::char_class_type _CharClassT;
470 :
471 : public:
472 258 : _BracketMatcher(bool __is_non_matching,
473 : const _TraitsT& __traits)
474 : : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
475 258 : _M_is_non_matching(__is_non_matching)
476 258 : { }
477 :
478 : bool
479 4072 : operator()(_CharT __ch) const
480 : {
481 : _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
482 4072 : return _M_apply(__ch, _UseCache());
483 : }
484 :
485 : void
486 349 : _M_add_char(_CharT __c)
487 : {
488 349 : _M_char_set.push_back(_M_translator._M_translate(__c));
489 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
490 349 : }
491 :
492 : _StringT
493 0 : _M_add_collate_element(const _StringT& __s)
494 : {
495 0 : auto __st = _M_traits.lookup_collatename(__s.data(),
496 0 : __s.data() + __s.size());
497 0 : if (__st.empty())
498 0 : __throw_regex_error(regex_constants::error_collate,
499 : "Invalid collate element.");
500 0 : _M_char_set.push_back(_M_translator._M_translate(__st[0]));
501 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
502 0 : return __st;
503 : }
504 :
505 : void
506 0 : _M_add_equivalence_class(const _StringT& __s)
507 : {
508 0 : auto __st = _M_traits.lookup_collatename(__s.data(),
509 0 : __s.data() + __s.size());
510 0 : if (__st.empty())
511 0 : __throw_regex_error(regex_constants::error_collate,
512 : "Invalid equivalence class.");
513 0 : __st = _M_traits.transform_primary(__st.data(),
514 0 : __st.data() + __st.size());
515 0 : _M_equiv_set.push_back(__st);
516 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
517 0 : }
518 :
519 : // __neg should be true for \D, \S and \W only.
520 : void
521 36 : _M_add_character_class(const _StringT& __s, bool __neg)
522 : {
523 36 : auto __mask = _M_traits.lookup_classname(__s.data(),
524 36 : __s.data() + __s.size(),
525 : __icase);
526 36 : if (__mask == 0)
527 0 : __throw_regex_error(regex_constants::error_collate,
528 : "Invalid character class.");
529 36 : if (!__neg)
530 36 : _M_class_set |= __mask;
531 : else
532 0 : _M_neg_class_set.push_back(__mask);
533 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
534 36 : }
535 :
536 : void
537 174 : _M_make_range(_CharT __l, _CharT __r)
538 : {
539 174 : if (__l > __r)
540 0 : __throw_regex_error(regex_constants::error_range,
541 : "Invalid range in bracket expression.");
542 174 : _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
543 : _M_translator._M_transform(__r)));
544 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
545 174 : }
546 :
547 : void
548 258 : _M_ready()
549 : {
550 258 : std::sort(_M_char_set.begin(), _M_char_set.end());
551 258 : auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
552 258 : _M_char_set.erase(__end, _M_char_set.end());
553 258 : _M_make_cache(_UseCache());
554 : _GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
555 258 : }
556 :
557 : private:
558 : // Currently we only use the cache for char
559 : typedef typename std::is_same<_CharT, char>::type _UseCache;
560 :
561 : static constexpr size_t
562 : _S_cache_size()
563 : {
564 : return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
565 : }
566 :
567 : struct _Dummy { };
568 : typedef typename std::conditional<_UseCache::value,
569 : std::bitset<_S_cache_size()>,
570 : _Dummy>::type _CacheT;
571 : typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
572 :
573 : bool
574 : _M_apply(_CharT __ch, false_type) const;
575 :
576 : bool
577 4072 : _M_apply(_CharT __ch, true_type) const
578 4072 : { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
579 :
580 : void
581 258 : _M_make_cache(true_type)
582 : {
583 66306 : for (unsigned __i = 0; __i < _M_cache.size(); __i++)
584 66048 : _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
585 258 : }
586 :
587 : void
588 : _M_make_cache(false_type)
589 : { }
590 :
591 : private:
592 : std::vector<_CharT> _M_char_set;
593 : std::vector<_StringT> _M_equiv_set;
594 : std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
595 : std::vector<_CharClassT> _M_neg_class_set;
596 : _CharClassT _M_class_set;
597 : _TransT _M_translator;
598 : const _TraitsT& _M_traits;
599 : bool _M_is_non_matching;
600 : _CacheT _M_cache;
601 : #ifdef _GLIBCXX_DEBUG
602 : bool _M_is_ready = false;
603 : #endif
604 : };
605 :
606 : //@} regex-detail
607 : } // namespace __detail
608 : _GLIBCXX_END_NAMESPACE_VERSION
609 : } // namespace std
610 :
611 : #include <bits/regex_compiler.tcc>
|
