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