libstdc++
|
00001 // class template regex -*- C++ -*- 00002 00003 // Copyright (C) 2010-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file bits/regex_compiler.h 00027 * This is an internal header file, included by other library headers. 00028 * Do not attempt to use it directly. @headername{regex} 00029 */ 00030 00031 namespace std _GLIBCXX_VISIBILITY(default) 00032 { 00033 namespace __detail 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00036 00037 /** 00038 * @addtogroup regex-detail 00039 * @{ 00040 */ 00041 00042 template<typename, bool, bool> 00043 struct _BracketMatcher; 00044 00045 /** 00046 * @brief Builds an NFA from an input iterator range. 00047 * 00048 * The %_TraitsT type should fulfill requirements [28.3]. 00049 */ 00050 template<typename _TraitsT> 00051 class _Compiler 00052 { 00053 public: 00054 typedef typename _TraitsT::char_type _CharT; 00055 typedef const _CharT* _IterT; 00056 typedef _NFA<_TraitsT> _RegexT; 00057 typedef regex_constants::syntax_option_type _FlagT; 00058 00059 _Compiler(_IterT __b, _IterT __e, 00060 const typename _TraitsT::locale_type& __traits, _FlagT __flags); 00061 00062 shared_ptr<const _RegexT> 00063 _M_get_nfa() 00064 { return std::move(_M_nfa); } 00065 00066 private: 00067 typedef _Scanner<_CharT> _ScannerT; 00068 typedef typename _TraitsT::string_type _StringT; 00069 typedef typename _ScannerT::_TokenT _TokenT; 00070 typedef _StateSeq<_TraitsT> _StateSeqT; 00071 typedef std::stack<_StateSeqT> _StackT; 00072 typedef std::ctype<_CharT> _CtypeT; 00073 00074 // accepts a specific token or returns false. 00075 bool 00076 _M_match_token(_TokenT __token); 00077 00078 void 00079 _M_disjunction(); 00080 00081 void 00082 _M_alternative(); 00083 00084 bool 00085 _M_term(); 00086 00087 bool 00088 _M_assertion(); 00089 00090 bool 00091 _M_quantifier(); 00092 00093 bool 00094 _M_atom(); 00095 00096 bool 00097 _M_bracket_expression(); 00098 00099 template<bool __icase, bool __collate> 00100 void 00101 _M_insert_any_matcher_ecma(); 00102 00103 template<bool __icase, bool __collate> 00104 void 00105 _M_insert_any_matcher_posix(); 00106 00107 template<bool __icase, bool __collate> 00108 void 00109 _M_insert_char_matcher(); 00110 00111 template<bool __icase, bool __collate> 00112 void 00113 _M_insert_character_class_matcher(); 00114 00115 template<bool __icase, bool __collate> 00116 void 00117 _M_insert_bracket_matcher(bool __neg); 00118 00119 // Returns true if successfully matched one term and should continue. 00120 // Returns false if the compiler should move on. 00121 template<bool __icase, bool __collate> 00122 bool 00123 _M_expression_term(pair<bool, _CharT>& __last_char, 00124 _BracketMatcher<_TraitsT, __icase, __collate>& 00125 __matcher); 00126 00127 int 00128 _M_cur_int_value(int __radix); 00129 00130 bool 00131 _M_try_char(); 00132 00133 _StateSeqT 00134 _M_pop() 00135 { 00136 auto ret = _M_stack.top(); 00137 _M_stack.pop(); 00138 return ret; 00139 } 00140 00141 _FlagT _M_flags; 00142 _ScannerT _M_scanner; 00143 shared_ptr<_RegexT> _M_nfa; 00144 _StringT _M_value; 00145 _StackT _M_stack; 00146 const _TraitsT& _M_traits; 00147 const _CtypeT& _M_ctype; 00148 }; 00149 00150 template<typename _Tp> 00151 struct __has_contiguous_iter : std::false_type { }; 00152 00153 template<typename _Ch, typename _Tr, typename _Alloc> 00154 struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>> 00155 : std::true_type 00156 { }; 00157 00158 template<typename _Tp, typename _Alloc> 00159 struct __has_contiguous_iter<std::vector<_Tp, _Alloc>> 00160 : std::true_type 00161 { }; 00162 00163 template<typename _Tp> 00164 struct __is_contiguous_normal_iter : std::false_type { }; 00165 00166 template<typename _CharT> 00167 struct __is_contiguous_normal_iter<_CharT*> : std::true_type { }; 00168 00169 template<typename _Tp, typename _Cont> 00170 struct 00171 __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>> 00172 : __has_contiguous_iter<_Cont>::type 00173 { }; 00174 00175 template<typename _Iter, typename _TraitsT> 00176 using __enable_if_contiguous_normal_iter 00177 = typename enable_if< __is_contiguous_normal_iter<_Iter>::value, 00178 std::shared_ptr<const _NFA<_TraitsT>> >::type; 00179 00180 template<typename _Iter, typename _TraitsT> 00181 using __disable_if_contiguous_normal_iter 00182 = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value, 00183 std::shared_ptr<const _NFA<_TraitsT>> >::type; 00184 00185 template<typename _FwdIter, typename _TraitsT> 00186 inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT> 00187 __compile_nfa(_FwdIter __first, _FwdIter __last, 00188 const typename _TraitsT::locale_type& __loc, 00189 regex_constants::syntax_option_type __flags) 00190 { 00191 size_t __len = __last - __first; 00192 const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr; 00193 using _Cmplr = _Compiler<_TraitsT>; 00194 return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa(); 00195 } 00196 00197 template<typename _FwdIter, typename _TraitsT> 00198 inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT> 00199 __compile_nfa(_FwdIter __first, _FwdIter __last, 00200 const typename _TraitsT::locale_type& __loc, 00201 regex_constants::syntax_option_type __flags) 00202 { 00203 basic_string<typename _TraitsT::char_type> __str(__first, __last); 00204 return __compile_nfa(__str.data(), __str.data() + __str.size(), __loc, 00205 __flags); 00206 } 00207 00208 // [28.13.14] 00209 template<typename _TraitsT, bool __icase, bool __collate> 00210 class _RegexTranslator 00211 { 00212 public: 00213 typedef typename _TraitsT::char_type _CharT; 00214 typedef typename _TraitsT::string_type _StringT; 00215 typedef typename std::conditional<__collate, 00216 _StringT, 00217 _CharT>::type _StrTransT; 00218 00219 explicit 00220 _RegexTranslator(const _TraitsT& __traits) 00221 : _M_traits(__traits) 00222 { } 00223 00224 _CharT 00225 _M_translate(_CharT __ch) const 00226 { 00227 if (__icase) 00228 return _M_traits.translate_nocase(__ch); 00229 else if (__collate) 00230 return _M_traits.translate(__ch); 00231 else 00232 return __ch; 00233 } 00234 00235 _StrTransT 00236 _M_transform(_CharT __ch) const 00237 { 00238 return _M_transform_impl(__ch, typename integral_constant<bool, 00239 __collate>::type()); 00240 } 00241 00242 private: 00243 _StrTransT 00244 _M_transform_impl(_CharT __ch, false_type) const 00245 { return __ch; } 00246 00247 _StrTransT 00248 _M_transform_impl(_CharT __ch, true_type) const 00249 { 00250 _StrTransT __str = _StrTransT(1, _M_translate(__ch)); 00251 return _M_traits.transform(__str.begin(), __str.end()); 00252 } 00253 00254 const _TraitsT& _M_traits; 00255 }; 00256 00257 template<typename _TraitsT> 00258 class _RegexTranslator<_TraitsT, false, false> 00259 { 00260 public: 00261 typedef typename _TraitsT::char_type _CharT; 00262 typedef _CharT _StrTransT; 00263 00264 explicit 00265 _RegexTranslator(const _TraitsT&) 00266 { } 00267 00268 _CharT 00269 _M_translate(_CharT __ch) const 00270 { return __ch; } 00271 00272 _StrTransT 00273 _M_transform(_CharT __ch) const 00274 { return __ch; } 00275 }; 00276 00277 template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate> 00278 struct _AnyMatcher; 00279 00280 template<typename _TraitsT, bool __icase, bool __collate> 00281 struct _AnyMatcher<_TraitsT, false, __icase, __collate> 00282 { 00283 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00284 typedef typename _TransT::_CharT _CharT; 00285 00286 explicit 00287 _AnyMatcher(const _TraitsT& __traits) 00288 : _M_translator(__traits) 00289 { } 00290 00291 bool 00292 operator()(_CharT __ch) const 00293 { 00294 static auto __nul = _M_translator._M_translate('\0'); 00295 return _M_translator._M_translate(__ch) != __nul; 00296 } 00297 00298 _TransT _M_translator; 00299 }; 00300 00301 template<typename _TraitsT, bool __icase, bool __collate> 00302 struct _AnyMatcher<_TraitsT, true, __icase, __collate> 00303 { 00304 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00305 typedef typename _TransT::_CharT _CharT; 00306 00307 explicit 00308 _AnyMatcher(const _TraitsT& __traits) 00309 : _M_translator(__traits) 00310 { } 00311 00312 bool 00313 operator()(_CharT __ch) const 00314 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); } 00315 00316 bool 00317 _M_apply(_CharT __ch, true_type) const 00318 { 00319 auto __c = _M_translator._M_translate(__ch); 00320 auto __n = _M_translator._M_translate('\n'); 00321 auto __r = _M_translator._M_translate('\r'); 00322 return __c != __n && __c != __r; 00323 } 00324 00325 bool 00326 _M_apply(_CharT __ch, false_type) const 00327 { 00328 auto __c = _M_translator._M_translate(__ch); 00329 auto __n = _M_translator._M_translate('\n'); 00330 auto __r = _M_translator._M_translate('\r'); 00331 auto __u2028 = _M_translator._M_translate(u'\u2028'); 00332 auto __u2029 = _M_translator._M_translate(u'\u2029'); 00333 return __c != __n && __c != __r && __c != __u2028 && __c != __u2029; 00334 } 00335 00336 _TransT _M_translator; 00337 }; 00338 00339 template<typename _TraitsT, bool __icase, bool __collate> 00340 struct _CharMatcher 00341 { 00342 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00343 typedef typename _TransT::_CharT _CharT; 00344 00345 _CharMatcher(_CharT __ch, const _TraitsT& __traits) 00346 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch)) 00347 { } 00348 00349 bool 00350 operator()(_CharT __ch) const 00351 { return _M_ch == _M_translator._M_translate(__ch); } 00352 00353 _TransT _M_translator; 00354 _CharT _M_ch; 00355 }; 00356 00357 /// Matches a character range (bracket expression) 00358 template<typename _TraitsT, bool __icase, bool __collate> 00359 struct _BracketMatcher 00360 { 00361 public: 00362 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00363 typedef typename _TransT::_CharT _CharT; 00364 typedef typename _TransT::_StrTransT _StrTransT; 00365 typedef typename _TraitsT::string_type _StringT; 00366 typedef typename _TraitsT::char_class_type _CharClassT; 00367 00368 public: 00369 _BracketMatcher(bool __is_non_matching, 00370 const _TraitsT& __traits) 00371 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits), 00372 _M_is_non_matching(__is_non_matching) 00373 #ifdef _GLIBCXX_DEBUG 00374 , _M_is_ready(false) 00375 #endif 00376 { } 00377 00378 bool 00379 operator()(_CharT __ch) const 00380 { 00381 _GLIBCXX_DEBUG_ASSERT(_M_is_ready); 00382 return _M_apply(__ch, _UseCache()); 00383 } 00384 00385 void 00386 _M_add_char(_CharT __c) 00387 { 00388 _M_char_set.push_back(_M_translator._M_translate(__c)); 00389 #ifdef _GLIBCXX_DEBUG 00390 _M_is_ready = false; 00391 #endif 00392 } 00393 00394 _StringT 00395 _M_add_collate_element(const _StringT& __s) 00396 { 00397 auto __st = _M_traits.lookup_collatename(__s.data(), 00398 __s.data() + __s.size()); 00399 if (__st.empty()) 00400 __throw_regex_error(regex_constants::error_collate); 00401 _M_char_set.push_back(_M_translator._M_translate(__st[0])); 00402 #ifdef _GLIBCXX_DEBUG 00403 _M_is_ready = false; 00404 #endif 00405 return __st; 00406 } 00407 00408 void 00409 _M_add_equivalence_class(const _StringT& __s) 00410 { 00411 auto __st = _M_traits.lookup_collatename(__s.data(), 00412 __s.data() + __s.size()); 00413 if (__st.empty()) 00414 __throw_regex_error(regex_constants::error_collate); 00415 __st = _M_traits.transform_primary(__st.data(), 00416 __st.data() + __st.size()); 00417 _M_equiv_set.push_back(__st); 00418 #ifdef _GLIBCXX_DEBUG 00419 _M_is_ready = false; 00420 #endif 00421 } 00422 00423 // __neg should be true for \D, \S and \W only. 00424 void 00425 _M_add_character_class(const _StringT& __s, bool __neg) 00426 { 00427 auto __mask = _M_traits.lookup_classname(__s.data(), 00428 __s.data() + __s.size(), 00429 __icase); 00430 if (__mask == 0) 00431 __throw_regex_error(regex_constants::error_ctype); 00432 if (!__neg) 00433 _M_class_set |= __mask; 00434 else 00435 _M_neg_class_set.push_back(__mask); 00436 #ifdef _GLIBCXX_DEBUG 00437 _M_is_ready = false; 00438 #endif 00439 } 00440 00441 void 00442 _M_make_range(_CharT __l, _CharT __r) 00443 { 00444 if (__l > __r) 00445 __throw_regex_error(regex_constants::error_range); 00446 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l), 00447 _M_translator._M_transform(__r))); 00448 #ifdef _GLIBCXX_DEBUG 00449 _M_is_ready = false; 00450 #endif 00451 } 00452 00453 void 00454 _M_ready() 00455 { 00456 std::sort(_M_char_set.begin(), _M_char_set.end()); 00457 auto __end = std::unique(_M_char_set.begin(), _M_char_set.end()); 00458 _M_char_set.erase(__end, _M_char_set.end()); 00459 _M_make_cache(_UseCache()); 00460 #ifdef _GLIBCXX_DEBUG 00461 _M_is_ready = true; 00462 #endif 00463 } 00464 00465 private: 00466 // Currently we only use the cache for char 00467 typedef typename std::is_same<_CharT, char>::type _UseCache; 00468 00469 static constexpr size_t 00470 _S_cache_size() 00471 { 00472 return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value)); 00473 } 00474 00475 struct _Dummy { }; 00476 typedef typename std::conditional<_UseCache::value, 00477 std::bitset<_S_cache_size()>, 00478 _Dummy>::type _CacheT; 00479 typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT; 00480 00481 bool 00482 _M_apply(_CharT __ch, false_type) const; 00483 00484 bool 00485 _M_apply(_CharT __ch, true_type) const 00486 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; } 00487 00488 void 00489 _M_make_cache(true_type) 00490 { 00491 for (unsigned __i = 0; __i < _M_cache.size(); __i++) 00492 _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type()); 00493 } 00494 00495 void 00496 _M_make_cache(false_type) 00497 { } 00498 00499 private: 00500 std::vector<_CharT> _M_char_set; 00501 std::vector<_StringT> _M_equiv_set; 00502 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set; 00503 std::vector<_CharClassT> _M_neg_class_set; 00504 _CharClassT _M_class_set; 00505 _TransT _M_translator; 00506 const _TraitsT& _M_traits; 00507 bool _M_is_non_matching; 00508 _CacheT _M_cache; 00509 #ifdef _GLIBCXX_DEBUG 00510 bool _M_is_ready; 00511 #endif 00512 }; 00513 00514 //@} regex-detail 00515 _GLIBCXX_END_NAMESPACE_VERSION 00516 } // namespace __detail 00517 } // namespace std 00518 00519 #include <bits/regex_compiler.tcc>