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