1 // class template regex -*- C++ -*-
2
3 // Copyright (C) 2010-2020 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
_GLIBCXX_VISIBILITY(default)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 _M_get_nfa()
70 { 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 _M_pop()
141 {
142 auto ret = _M_stack.top();
143 _M_stack.pop();
144 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 __compile_nfa(_FwdIter __first, _FwdIter __last,
177 const typename _TraitsT::locale_type& __loc,
178 regex_constants::syntax_option_type __flags)
179 {
180 size_t __len = __last - __first;
181 const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
182 using _Cmplr = _Compiler<_TraitsT>;
183 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 _RegexTranslatorBase(const _TraitsT& __traits)
208 : _M_traits(__traits)
209 { }
210
211 _CharT
212 _M_translate(_CharT __ch) const
213 {
214 if (__icase)
215 return _M_traits.translate_nocase(__ch);
216 else if (__collate)
217 return _M_traits.translate(__ch);
218 else
219 return __ch;
220 }
221
222 _StrTransT
223 _M_transform(_CharT __ch) const
224 {
225 _StrTransT __str(1, __ch);
226 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 bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
239 {
240 typedef std::ctype<_CharT> __ctype_type;
241 const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
242 auto __lower = __fctyp.tolower(__ch);
243 auto __upper = __fctyp.toupper(__ch);
244 return (__first <= __lower && __lower <= __last)
245 || (__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 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 using _Base::_Base;
270
271 _StrTransT
272 _M_transform(_CharT __ch) const
273 { return __ch; }
274
275 bool
276 _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
277 {
278 if (!__icase)
279 return __first <= __ch && __ch <= __last;
280 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 using _Base::_Base;
295
296 bool
297 _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 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 _RegexTranslator(const _TraitsT&)
316 { }
317
318 _CharT
319 _M_translate(_CharT __ch) const
320 { return __ch; }
321
322 _StrTransT
323 _M_transform(_CharT __ch) const
324 { return __ch; }
325
326 bool
327 _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
328 { 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 _AnyMatcher(const _TraitsT& __traits)
342 : _M_translator(__traits)
343 { }
344
345 bool
346 operator()(_CharT __ch) const
347 {
348 static auto __nul = _M_translator._M_translate('\0');
349 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 _AnyMatcher(const _TraitsT& __traits)
363 : _M_translator(__traits)
364 { }
365
366 bool
367 operator()(_CharT __ch) const
368 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
369
370 bool
371 _M_apply(_CharT __ch, true_type) const
372 {
373 auto __c = _M_translator._M_translate(__ch);
374 auto __n = _M_translator._M_translate('\n');
375 auto __r = _M_translator._M_translate('\r');
376 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 _CharMatcher(_CharT __ch, const _TraitsT& __traits)
400 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
401 { }
402
403 bool
404 operator()(_CharT __ch) const
405 { 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 _BracketMatcher(bool __is_non_matching,
424 const _TraitsT& __traits)
425 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
426 _M_is_non_matching(__is_non_matching)
427 { }
428
429 bool
430 operator()(_CharT __ch) const
431 {
432 _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
433 return _M_apply(__ch, _UseCache());
434 }
435
436 void
437 _M_add_char(_CharT __c)
438 {
439 _M_char_set.push_back(_M_translator._M_translate(__c));
440 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
441 }
442
443 _StringT
444 _M_add_collate_element(const _StringT& __s)
445 {
446 auto __st = _M_traits.lookup_collatename(__s.data(),
447 __s.data() + __s.size());
448 if (__st.empty())
449 __throw_regex_error(regex_constants::error_collate,
450 "Invalid collate element.");
451 _M_char_set.push_back(_M_translator._M_translate(__st[0]));
452 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
453 return __st;
454 }
455
456 void
457 _M_add_equivalence_class(const _StringT& __s)
458 {
459 auto __st = _M_traits.lookup_collatename(__s.data(),
460 __s.data() + __s.size());
461 if (__st.empty())
462 __throw_regex_error(regex_constants::error_collate,
463 "Invalid equivalence class.");
464 __st = _M_traits.transform_primary(__st.data(),
465 __st.data() + __st.size());
466 _M_equiv_set.push_back(__st);
467 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
468 }
469
470 // __neg should be true for \D, \S and \W only.
471 void
472 _M_add_character_class(const _StringT& __s, bool __neg)
473 {
474 auto __mask = _M_traits.lookup_classname(__s.data(),
475 __s.data() + __s.size(),
476 __icase);
477 if (__mask == 0)
478 __throw_regex_error(regex_constants::error_collate,
479 "Invalid character class.");
480 if (!__neg)
481 _M_class_set |= __mask;
482 else
483 _M_neg_class_set.push_back(__mask);
484 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
485 }
486
487 void
488 _M_make_range(_CharT __l, _CharT __r)
489 {
490 if (__l > __r)
491 __throw_regex_error(regex_constants::error_range,
492 "Invalid range in bracket expression.");
493 _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 }
497
498 void
499 _M_ready()
500 {
501 std::sort(_M_char_set.begin(), _M_char_set.end());
502 auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
503 _M_char_set.erase(__end, _M_char_set.end());
504 _M_make_cache(_UseCache());
505 _GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
506 }
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 _M_apply(_CharT __ch, true_type) const
527 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
528
529 void
530 _M_make_cache(true_type)
531 {
532 for (unsigned __i = 0; __i < _M_cache.size(); __i++)
533 _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
534 }
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>
561