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