libstdc++
|
00001 // class template regex -*- C++ -*- 00002 00003 // Copyright (C) 2010-2014 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 interval. 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 _TraitsT& __traits, _FlagT __flags); 00061 00062 std::shared_ptr<_RegexT> 00063 _M_get_nfa() 00064 { return make_shared<_RegexT>(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 const _TraitsT& _M_traits; 00143 const _CtypeT& _M_ctype; 00144 _ScannerT _M_scanner; 00145 _RegexT _M_nfa; 00146 _StringT _M_value; 00147 _StackT _M_stack; 00148 }; 00149 00150 template<typename _TraitsT> 00151 inline std::shared_ptr<_NFA<_TraitsT>> 00152 __compile_nfa(const typename _TraitsT::char_type* __first, 00153 const typename _TraitsT::char_type* __last, 00154 const _TraitsT& __traits, 00155 regex_constants::syntax_option_type __flags) 00156 { 00157 using _Cmplr = _Compiler<_TraitsT>; 00158 return _Cmplr(__first, __last, __traits, __flags)._M_get_nfa(); 00159 } 00160 00161 // [28.13.14] 00162 template<typename _TraitsT, bool __icase, bool __collate> 00163 class _RegexTranslator 00164 { 00165 public: 00166 typedef typename _TraitsT::char_type _CharT; 00167 typedef typename _TraitsT::string_type _StringT; 00168 typedef typename std::conditional<__collate, 00169 _StringT, 00170 _CharT>::type _StrTransT; 00171 00172 explicit 00173 _RegexTranslator(const _TraitsT& __traits) 00174 : _M_traits(__traits) 00175 { } 00176 00177 _CharT 00178 _M_translate(_CharT __ch) const 00179 { 00180 if (__icase) 00181 return _M_traits.translate_nocase(__ch); 00182 else if (__collate) 00183 return _M_traits.translate(__ch); 00184 else 00185 return __ch; 00186 } 00187 00188 _StrTransT 00189 _M_transform(_CharT __ch) const 00190 { 00191 return _M_transform_impl(__ch, typename integral_constant<bool, 00192 __collate>::type()); 00193 } 00194 00195 private: 00196 _StrTransT 00197 _M_transform_impl(_CharT __ch, false_type) const 00198 { return __ch; } 00199 00200 _StrTransT 00201 _M_transform_impl(_CharT __ch, true_type) const 00202 { 00203 _StrTransT __str = _StrTransT(1, _M_translate(__ch)); 00204 return _M_traits.transform(__str.begin(), __str.end()); 00205 } 00206 00207 const _TraitsT& _M_traits; 00208 }; 00209 00210 template<typename _TraitsT> 00211 class _RegexTranslator<_TraitsT, false, false> 00212 { 00213 public: 00214 typedef typename _TraitsT::char_type _CharT; 00215 typedef _CharT _StrTransT; 00216 00217 explicit 00218 _RegexTranslator(const _TraitsT& __traits) 00219 { } 00220 00221 _CharT 00222 _M_translate(_CharT __ch) const 00223 { return __ch; } 00224 00225 _StrTransT 00226 _M_transform(_CharT __ch) const 00227 { return __ch; } 00228 }; 00229 00230 template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate> 00231 struct _AnyMatcher; 00232 00233 template<typename _TraitsT, bool __icase, bool __collate> 00234 struct _AnyMatcher<_TraitsT, false, __icase, __collate> 00235 { 00236 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00237 typedef typename _TransT::_CharT _CharT; 00238 00239 explicit 00240 _AnyMatcher(const _TraitsT& __traits) 00241 : _M_translator(__traits) 00242 { } 00243 00244 bool 00245 operator()(_CharT __ch) const 00246 { 00247 static auto __nul = _M_translator._M_translate('\0'); 00248 return _M_translator._M_translate(__ch) != __nul; 00249 } 00250 00251 _TransT _M_translator; 00252 }; 00253 00254 template<typename _TraitsT, bool __icase, bool __collate> 00255 struct _AnyMatcher<_TraitsT, true, __icase, __collate> 00256 { 00257 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00258 typedef typename _TransT::_CharT _CharT; 00259 00260 explicit 00261 _AnyMatcher(const _TraitsT& __traits) 00262 : _M_translator(__traits) 00263 { } 00264 00265 bool 00266 operator()(_CharT __ch) const 00267 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); } 00268 00269 bool 00270 _M_apply(_CharT __ch, true_type) const 00271 { 00272 auto __c = _M_translator._M_translate(__ch); 00273 auto __n = _M_translator._M_translate('\n'); 00274 auto __r = _M_translator._M_translate('\r'); 00275 return __c != __n && __c != __r; 00276 } 00277 00278 bool 00279 _M_apply(_CharT __ch, false_type) const 00280 { 00281 auto __c = _M_translator._M_translate(__ch); 00282 auto __n = _M_translator._M_translate('\n'); 00283 auto __r = _M_translator._M_translate('\r'); 00284 auto __u2028 = _M_translator._M_translate(u'\u2028'); 00285 auto __u2029 = _M_translator._M_translate(u'\u2029'); 00286 return __c != __n && __c != __r && __c != __u2028 && __c != __u2029; 00287 } 00288 00289 _TransT _M_translator; 00290 }; 00291 00292 template<typename _TraitsT, bool __icase, bool __collate> 00293 struct _CharMatcher 00294 { 00295 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00296 typedef typename _TransT::_CharT _CharT; 00297 00298 _CharMatcher(_CharT __ch, const _TraitsT& __traits) 00299 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch)) 00300 { } 00301 00302 bool 00303 operator()(_CharT __ch) const 00304 { return _M_ch == _M_translator._M_translate(__ch); } 00305 00306 _TransT _M_translator; 00307 _CharT _M_ch; 00308 }; 00309 00310 /// Matches a character range (bracket expression) 00311 template<typename _TraitsT, bool __icase, bool __collate> 00312 struct _BracketMatcher 00313 { 00314 public: 00315 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 00316 typedef typename _TransT::_CharT _CharT; 00317 typedef typename _TransT::_StrTransT _StrTransT; 00318 typedef typename _TraitsT::string_type _StringT; 00319 typedef typename _TraitsT::char_class_type _CharClassT; 00320 00321 public: 00322 _BracketMatcher(bool __is_non_matching, 00323 const _TraitsT& __traits) 00324 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits), 00325 _M_is_non_matching(__is_non_matching) 00326 #ifdef _GLIBCXX_DEBUG 00327 , _M_is_ready(false) 00328 #endif 00329 { } 00330 00331 bool 00332 operator()(_CharT __ch) const 00333 { 00334 _GLIBCXX_DEBUG_ASSERT(_M_is_ready); 00335 return _M_apply(__ch, _IsChar()); 00336 } 00337 00338 void 00339 _M_add_char(_CharT __c) 00340 { 00341 _M_char_set.push_back(_M_translator._M_translate(__c)); 00342 #ifdef _GLIBCXX_DEBUG 00343 _M_is_ready = false; 00344 #endif 00345 } 00346 00347 _StringT 00348 _M_add_collate_element(const _StringT& __s) 00349 { 00350 auto __st = _M_traits.lookup_collatename(__s.data(), 00351 __s.data() + __s.size()); 00352 if (__st.empty()) 00353 __throw_regex_error(regex_constants::error_collate); 00354 _M_char_set.push_back(_M_translator._M_translate(__st[0])); 00355 #ifdef _GLIBCXX_DEBUG 00356 _M_is_ready = false; 00357 #endif 00358 return __st; 00359 } 00360 00361 void 00362 _M_add_equivalence_class(const _StringT& __s) 00363 { 00364 auto __st = _M_traits.lookup_collatename(__s.data(), 00365 __s.data() + __s.size()); 00366 if (__st.empty()) 00367 __throw_regex_error(regex_constants::error_collate); 00368 __st = _M_traits.transform_primary(__st.data(), 00369 __st.data() + __st.size()); 00370 _M_equiv_set.push_back(__st); 00371 #ifdef _GLIBCXX_DEBUG 00372 _M_is_ready = false; 00373 #endif 00374 } 00375 00376 // __neg should be true for \D, \S and \W only. 00377 void 00378 _M_add_character_class(const _StringT& __s, bool __neg) 00379 { 00380 auto __mask = _M_traits.lookup_classname(__s.data(), 00381 __s.data() + __s.size(), 00382 __icase); 00383 if (__mask == 0) 00384 __throw_regex_error(regex_constants::error_ctype); 00385 if (!__neg) 00386 _M_class_set |= __mask; 00387 else 00388 _M_neg_class_set.push_back(__mask); 00389 #ifdef _GLIBCXX_DEBUG 00390 _M_is_ready = false; 00391 #endif 00392 } 00393 00394 void 00395 _M_make_range(_CharT __l, _CharT __r) 00396 { 00397 if (__l > __r) 00398 __throw_regex_error(regex_constants::error_range); 00399 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l), 00400 _M_translator._M_transform(__r))); 00401 #ifdef _GLIBCXX_DEBUG 00402 _M_is_ready = false; 00403 #endif 00404 } 00405 00406 void 00407 _M_ready() 00408 { 00409 _M_make_cache(_IsChar()); 00410 #ifdef _GLIBCXX_DEBUG 00411 _M_is_ready = true; 00412 #endif 00413 } 00414 00415 private: 00416 typedef typename is_same<_CharT, char>::type _IsChar; 00417 struct _Dummy { }; 00418 typedef typename conditional<_IsChar::value, 00419 std::bitset<1 << (8 * sizeof(_CharT))>, 00420 _Dummy>::type _CacheT; 00421 typedef typename make_unsigned<_CharT>::type _UnsignedCharT; 00422 00423 private: 00424 bool 00425 _M_apply(_CharT __ch, false_type) const; 00426 00427 bool 00428 _M_apply(_CharT __ch, true_type) const 00429 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; } 00430 00431 void 00432 _M_make_cache(true_type) 00433 { 00434 for (int __i = 0; __i < _M_cache.size(); __i++) 00435 _M_cache[static_cast<_UnsignedCharT>(__i)] = 00436 _M_apply(__i, false_type()); 00437 } 00438 00439 void 00440 _M_make_cache(false_type) 00441 { } 00442 00443 private: 00444 _CacheT _M_cache; 00445 std::vector<_CharT> _M_char_set; 00446 std::vector<_StringT> _M_equiv_set; 00447 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set; 00448 std::vector<_CharClassT> _M_neg_class_set; 00449 _CharClassT _M_class_set; 00450 _TransT _M_translator; 00451 const _TraitsT& _M_traits; 00452 bool _M_is_non_matching; 00453 #ifdef _GLIBCXX_DEBUG 00454 bool _M_is_ready; 00455 #endif 00456 }; 00457 00458 //@} regex-detail 00459 _GLIBCXX_END_NAMESPACE_VERSION 00460 } // namespace __detail 00461 } // namespace std 00462 00463 #include <bits/regex_compiler.tcc>