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