1 // class template regex -*- C++ -*- 2 3 // Copyright (C) 2010-2015 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 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 #ifdef _GLIBCXX_DEBUG 375 , _M_is_ready(false) 376 #endif 377 { } 378 379 bool 380 operator()(_CharT __ch) const 381 { 382 _GLIBCXX_DEBUG_ASSERT(_M_is_ready); 383 return _M_apply(__ch, _UseCache()); 384 } 385 386 void 387 _M_add_char(_CharT __c) 388 { 389 _M_char_set.push_back(_M_translator._M_translate(__c)); 390 #ifdef _GLIBCXX_DEBUG 391 _M_is_ready = false; 392 #endif 393 } 394 395 _StringT 396 _M_add_collate_element(const _StringT& __s) 397 { 398 auto __st = _M_traits.lookup_collatename(__s.data(), 399 __s.data() + __s.size()); 400 if (__st.empty()) 401 __throw_regex_error(regex_constants::error_collate); 402 _M_char_set.push_back(_M_translator._M_translate(__st[0])); 403 #ifdef _GLIBCXX_DEBUG 404 _M_is_ready = false; 405 #endif 406 return __st; 407 } 408 409 void 410 _M_add_equivalence_class(const _StringT& __s) 411 { 412 auto __st = _M_traits.lookup_collatename(__s.data(), 413 __s.data() + __s.size()); 414 if (__st.empty()) 415 __throw_regex_error(regex_constants::error_collate); 416 __st = _M_traits.transform_primary(__st.data(), 417 __st.data() + __st.size()); 418 _M_equiv_set.push_back(__st); 419 #ifdef _GLIBCXX_DEBUG 420 _M_is_ready = false; 421 #endif 422 } 423 424 // __neg should be true for \D, \S and \W only. 425 void 426 _M_add_character_class(const _StringT& __s, bool __neg) 427 { 428 auto __mask = _M_traits.lookup_classname(__s.data(), 429 __s.data() + __s.size(), 430 __icase); 431 if (__mask == 0) 432 __throw_regex_error(regex_constants::error_ctype); 433 if (!__neg) 434 _M_class_set |= __mask; 435 else 436 _M_neg_class_set.push_back(__mask); 437 #ifdef _GLIBCXX_DEBUG 438 _M_is_ready = false; 439 #endif 440 } 441 442 void 443 _M_make_range(_CharT __l, _CharT __r) 444 { 445 if (__l > __r) 446 __throw_regex_error(regex_constants::error_range); 447 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l), 448 _M_translator._M_transform(__r))); 449 #ifdef _GLIBCXX_DEBUG 450 _M_is_ready = false; 451 #endif 452 } 453 454 void 455 _M_ready() 456 { 457 std::sort(_M_char_set.begin(), _M_char_set.end()); 458 auto __end = std::unique(_M_char_set.begin(), _M_char_set.end()); 459 _M_char_set.erase(__end, _M_char_set.end()); 460 _M_make_cache(_UseCache()); 461 #ifdef _GLIBCXX_DEBUG 462 _M_is_ready = true; 463 #endif 464 } 465 466 private: 467 // Currently we only use the cache for char 468 typedef typename std::is_same<_CharT, char>::type _UseCache; 469 470 static constexpr size_t 471 _S_cache_size() 472 { 473 return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value)); 474 } 475 476 struct _Dummy { }; 477 typedef typename std::conditional<_UseCache::value, 478 std::bitset<_S_cache_size()>, 479 _Dummy>::type _CacheT; 480 typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT; 481 482 bool 483 _M_apply(_CharT __ch, false_type) const; 484 485 bool 486 _M_apply(_CharT __ch, true_type) const 487 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; } 488 489 void 490 _M_make_cache(true_type) 491 { 492 for (unsigned __i = 0; __i < _M_cache.size(); __i++) 493 _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type()); 494 } 495 496 void 497 _M_make_cache(false_type) 498 { } 499 500 private: 501 std::vector<_CharT> _M_char_set; 502 std::vector<_StringT> _M_equiv_set; 503 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set; 504 std::vector<_CharClassT> _M_neg_class_set; 505 _CharClassT _M_class_set; 506 _TransT _M_translator; 507 const _TraitsT& _M_traits; 508 bool _M_is_non_matching; 509 _CacheT _M_cache; 510 #ifdef _GLIBCXX_DEBUG 511 bool _M_is_ready; 512 #endif 513 }; 514 515 //@} regex-detail 516 _GLIBCXX_END_NAMESPACE_VERSION 517 } // namespace __detail 518 } // namespace std 519 520 #include <bits/regex_compiler.tcc> 521