1 // class template regex -*- C++ -*-
3 // Copyright (C) 2010-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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}
31 namespace std _GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 * @addtogroup regex-detail
42 template<typename, bool, bool>
43 struct _BracketMatcher;
46 * @brief Builds an NFA from an input iterator range.
48 * The %_TraitsT type should fulfill requirements [28.3].
50 template<typename _TraitsT>
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;
59 _Compiler(_IterT __b, _IterT __e,
60 const typename _TraitsT::locale_type& __traits, _FlagT __flags);
62 shared_ptr<const _RegexT>
64 { return std::move(_M_nfa); }
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;
74 // accepts a specific token or returns false.
76 _M_match_token(_TokenT __token);
97 _M_bracket_expression();
99 template<bool __icase, bool __collate>
101 _M_insert_any_matcher_ecma();
103 template<bool __icase, bool __collate>
105 _M_insert_any_matcher_posix();
107 template<bool __icase, bool __collate>
109 _M_insert_char_matcher();
111 template<bool __icase, bool __collate>
113 _M_insert_character_class_matcher();
115 template<bool __icase, bool __collate>
117 _M_insert_bracket_matcher(bool __neg);
119 template<bool __icase, bool __collate>
121 _M_expression_term(pair<bool, _CharT>& __last_char,
122 _BracketMatcher<_TraitsT, __icase, __collate>&
126 _M_cur_int_value(int __radix);
134 auto ret = _M_stack.top();
140 _ScannerT _M_scanner;
141 shared_ptr<_RegexT> _M_nfa;
144 const _TraitsT& _M_traits;
145 const _CtypeT& _M_ctype;
148 template<typename _Tp>
149 struct __has_contiguous_iter : std::false_type { };
151 template<typename _Ch, typename _Tr, typename _Alloc>
152 struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
156 template<typename _Tp, typename _Alloc>
157 struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
161 template<typename _Tp>
162 struct __is_contiguous_normal_iter : std::false_type { };
164 template<typename _CharT>
165 struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
167 template<typename _Tp, typename _Cont>
169 __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
170 : __has_contiguous_iter<_Cont>::type
173 template<typename _Iter, typename _TraitsT>
174 using __enable_if_contiguous_normal_iter
175 = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
176 std::shared_ptr<const _NFA<_TraitsT>> >::type;
178 template<typename _Iter, typename _TraitsT>
179 using __disable_if_contiguous_normal_iter
180 = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
181 std::shared_ptr<const _NFA<_TraitsT>> >::type;
183 template<typename _FwdIter, typename _TraitsT>
184 inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
185 __compile_nfa(_FwdIter __first, _FwdIter __last,
186 const typename _TraitsT::locale_type& __loc,
187 regex_constants::syntax_option_type __flags)
189 size_t __len = __last - __first;
190 const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
191 using _Cmplr = _Compiler<_TraitsT>;
192 return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
195 template<typename _FwdIter, typename _TraitsT>
196 inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
197 __compile_nfa(_FwdIter __first, _FwdIter __last,
198 const typename _TraitsT::locale_type& __loc,
199 regex_constants::syntax_option_type __flags)
201 basic_string<typename _TraitsT::char_type> __str(__first, __last);
202 return __compile_nfa(__str.data(), __str.data() + __str.size(), __loc,
207 template<typename _TraitsT, bool __icase, bool __collate>
208 class _RegexTranslator
211 typedef typename _TraitsT::char_type _CharT;
212 typedef typename _TraitsT::string_type _StringT;
213 typedef typename std::conditional<__collate,
215 _CharT>::type _StrTransT;
218 _RegexTranslator(const _TraitsT& __traits)
219 : _M_traits(__traits)
223 _M_translate(_CharT __ch) const
226 return _M_traits.translate_nocase(__ch);
228 return _M_traits.translate(__ch);
234 _M_transform(_CharT __ch) const
236 return _M_transform_impl(__ch, typename integral_constant<bool,
242 _M_transform_impl(_CharT __ch, false_type) const
246 _M_transform_impl(_CharT __ch, true_type) const
248 _StrTransT __str = _StrTransT(1, _M_translate(__ch));
249 return _M_traits.transform(__str.begin(), __str.end());
252 const _TraitsT& _M_traits;
255 template<typename _TraitsT>
256 class _RegexTranslator<_TraitsT, false, false>
259 typedef typename _TraitsT::char_type _CharT;
260 typedef _CharT _StrTransT;
263 _RegexTranslator(const _TraitsT&)
267 _M_translate(_CharT __ch) const
271 _M_transform(_CharT __ch) const
275 template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
278 template<typename _TraitsT, bool __icase, bool __collate>
279 struct _AnyMatcher<_TraitsT, false, __icase, __collate>
281 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
282 typedef typename _TransT::_CharT _CharT;
285 _AnyMatcher(const _TraitsT& __traits)
286 : _M_translator(__traits)
290 operator()(_CharT __ch) const
292 static auto __nul = _M_translator._M_translate('\0');
293 return _M_translator._M_translate(__ch) != __nul;
296 _TransT _M_translator;
299 template<typename _TraitsT, bool __icase, bool __collate>
300 struct _AnyMatcher<_TraitsT, true, __icase, __collate>
302 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
303 typedef typename _TransT::_CharT _CharT;
306 _AnyMatcher(const _TraitsT& __traits)
307 : _M_translator(__traits)
311 operator()(_CharT __ch) const
312 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
315 _M_apply(_CharT __ch, true_type) const
317 auto __c = _M_translator._M_translate(__ch);
318 auto __n = _M_translator._M_translate('\n');
319 auto __r = _M_translator._M_translate('\r');
320 return __c != __n && __c != __r;
324 _M_apply(_CharT __ch, false_type) const
326 auto __c = _M_translator._M_translate(__ch);
327 auto __n = _M_translator._M_translate('\n');
328 auto __r = _M_translator._M_translate('\r');
329 auto __u2028 = _M_translator._M_translate(u'\u2028');
330 auto __u2029 = _M_translator._M_translate(u'\u2029');
331 return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
334 _TransT _M_translator;
337 template<typename _TraitsT, bool __icase, bool __collate>
340 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
341 typedef typename _TransT::_CharT _CharT;
343 _CharMatcher(_CharT __ch, const _TraitsT& __traits)
344 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
348 operator()(_CharT __ch) const
349 { return _M_ch == _M_translator._M_translate(__ch); }
351 _TransT _M_translator;
355 /// Matches a character range (bracket expression)
356 template<typename _TraitsT, bool __icase, bool __collate>
357 struct _BracketMatcher
360 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
361 typedef typename _TransT::_CharT _CharT;
362 typedef typename _TransT::_StrTransT _StrTransT;
363 typedef typename _TraitsT::string_type _StringT;
364 typedef typename _TraitsT::char_class_type _CharClassT;
367 _BracketMatcher(bool __is_non_matching,
368 const _TraitsT& __traits)
369 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
370 _M_is_non_matching(__is_non_matching)
371 #ifdef _GLIBCXX_DEBUG
377 operator()(_CharT __ch) const
379 _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
380 return _M_apply(__ch, _UseCache());
384 _M_add_char(_CharT __c)
386 _M_char_set.push_back(_M_translator._M_translate(__c));
387 #ifdef _GLIBCXX_DEBUG
393 _M_add_collating_element(const _StringT& __s)
395 auto __st = _M_traits.lookup_collatename(__s.data(),
396 __s.data() + __s.size());
398 __throw_regex_error(regex_constants::error_collate);
399 _M_char_set.push_back(_M_translator._M_translate(__st[0]));
400 #ifdef _GLIBCXX_DEBUG
406 _M_add_equivalence_class(const _StringT& __s)
408 auto __st = _M_traits.lookup_collatename(__s.data(),
409 __s.data() + __s.size());
411 __throw_regex_error(regex_constants::error_collate);
412 __st = _M_traits.transform_primary(__st.data(),
413 __st.data() + __st.size());
414 _M_equiv_set.push_back(__st);
415 #ifdef _GLIBCXX_DEBUG
420 // __neg should be true for \D, \S and \W only.
422 _M_add_character_class(const _StringT& __s, bool __neg)
424 auto __mask = _M_traits.lookup_classname(__s.data(),
425 __s.data() + __s.size(),
428 __throw_regex_error(regex_constants::error_ctype);
430 _M_class_set |= __mask;
432 _M_neg_class_set.push_back(__mask);
433 #ifdef _GLIBCXX_DEBUG
439 _M_make_range(_CharT __l, _CharT __r)
442 __throw_regex_error(regex_constants::error_range);
443 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
444 _M_translator._M_transform(__r)));
445 #ifdef _GLIBCXX_DEBUG
453 std::sort(_M_char_set.begin(), _M_char_set.end());
454 auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
455 _M_char_set.erase(__end, _M_char_set.end());
456 _M_make_cache(_UseCache());
457 #ifdef _GLIBCXX_DEBUG
463 // Currently we only use the cache for char
464 typedef typename std::is_same<_CharT, char>::type _UseCache;
466 static constexpr size_t
469 return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
473 typedef typename std::conditional<_UseCache::value,
474 std::bitset<_S_cache_size()>,
475 _Dummy>::type _CacheT;
476 typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
479 _M_apply(_CharT __ch, false_type) const;
482 _M_apply(_CharT __ch, true_type) const
483 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
486 _M_make_cache(true_type)
488 for (unsigned __i = 0; __i < _M_cache.size(); __i++)
489 _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
493 _M_make_cache(false_type)
497 std::vector<_CharT> _M_char_set;
498 std::vector<_StringT> _M_equiv_set;
499 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
500 std::vector<_CharClassT> _M_neg_class_set;
501 _CharClassT _M_class_set;
502 _TransT _M_translator;
503 const _TraitsT& _M_traits;
504 bool _M_is_non_matching;
506 #ifdef _GLIBCXX_DEBUG
512 _GLIBCXX_END_NAMESPACE_VERSION
513 } // namespace __detail
516 #include <bits/regex_compiler.tcc>