Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/bits/regex_compiler.h
$ cat -n /usr/include/c++/11/bits/regex_compiler.h 1 // class template regex -*- C++ -*- 2 3 // Copyright (C) 2010-2021 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; 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 (__icase) 225 return _M_traits.translate_nocase(__ch); 226 else if (__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 (!__icase) 289 return __first <= __ch && __ch <= __last; 290 return this->_M_in_range_icase(__first, __last, __ch); 291 } 292 }; 293 294 template<typename _CharType> 295 class _RegexTranslator<std::regex_traits<_CharType>, true, true> 296 : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true> 297 { 298 public: 299 typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true> 300 _Base; 301 typedef typename _Base::_CharT _CharT; 302 typedef typename _Base::_StrTransT _StrTransT; 303 304 using _Base::_Base; 305 306 bool 307 _M_match_range(const _StrTransT& __first, const _StrTransT& __last, 308 const _StrTransT& __str) const 309 { 310 __glibcxx_assert(__first.size() == 1); 311 __glibcxx_assert(__last.size() == 1); 312 __glibcxx_assert(__str.size() == 1); 313 return this->_M_in_range_icase(__first[0], __last[0], __str[0]); 314 } 315 }; 316 317 template<typename _TraitsT> 318 class _RegexTranslator<_TraitsT, false, false> 319 { 320 public: 321 typedef typename _TraitsT::char_type _CharT; 322 typedef _CharT _StrTransT; 323 324 explicit 325 _RegexTranslator(const _TraitsT&) 326 { } 327 328 _CharT 329 _M_translate(_CharT __ch) const 330 { return __ch; } 331 332 _StrTransT 333 _M_transform(_CharT __ch) const 334 { return __ch; } 335 336 bool 337 _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const 338 { return __first <= __ch && __ch <= __last; } 339 }; 340 341 template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate> 342 struct _AnyMatcher; 343 344 template<typename _TraitsT, bool __icase, bool __collate> 345 struct _AnyMatcher<_TraitsT, false, __icase, __collate> 346 { 347 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 348 typedef typename _TransT::_CharT _CharT; 349 350 explicit 351 _AnyMatcher(const _TraitsT& __traits) 352 : _M_translator(__traits) 353 { } 354 355 bool 356 operator()(_CharT __ch) const 357 { 358 static auto __nul = _M_translator._M_translate('\0'); 359 return _M_translator._M_translate(__ch) != __nul; 360 } 361 362 _TransT _M_translator; 363 }; 364 365 template<typename _TraitsT, bool __icase, bool __collate> 366 struct _AnyMatcher<_TraitsT, true, __icase, __collate> 367 { 368 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 369 typedef typename _TransT::_CharT _CharT; 370 371 explicit 372 _AnyMatcher(const _TraitsT& __traits) 373 : _M_translator(__traits) 374 { } 375 376 bool 377 operator()(_CharT __ch) const 378 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); } 379 380 bool 381 _M_apply(_CharT __ch, true_type) const 382 { 383 auto __c = _M_translator._M_translate(__ch); 384 auto __n = _M_translator._M_translate('\n'); 385 auto __r = _M_translator._M_translate('\r'); 386 return __c != __n && __c != __r; 387 } 388 389 bool 390 _M_apply(_CharT __ch, false_type) const 391 { 392 auto __c = _M_translator._M_translate(__ch); 393 auto __n = _M_translator._M_translate('\n'); 394 auto __r = _M_translator._M_translate('\r'); 395 auto __u2028 = _M_translator._M_translate(u'\u2028'); 396 auto __u2029 = _M_translator._M_translate(u'\u2029'); 397 return __c != __n && __c != __r && __c != __u2028 && __c != __u2029; 398 } 399 400 _TransT _M_translator; 401 }; 402 403 template<typename _TraitsT, bool __icase, bool __collate> 404 struct _CharMatcher 405 { 406 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 407 typedef typename _TransT::_CharT _CharT; 408 409 _CharMatcher(_CharT __ch, const _TraitsT& __traits) 410 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch)) 411 { } 412 413 bool 414 operator()(_CharT __ch) const 415 { return _M_ch == _M_translator._M_translate(__ch); } 416 417 _TransT _M_translator; 418 _CharT _M_ch; 419 }; 420 421 /// Matches a character range (bracket expression) 422 template<typename _TraitsT, bool __icase, bool __collate> 423 struct _BracketMatcher 424 { 425 public: 426 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT; 427 typedef typename _TransT::_CharT _CharT; 428 typedef typename _TransT::_StrTransT _StrTransT; 429 typedef typename _TraitsT::string_type _StringT; 430 typedef typename _TraitsT::char_class_type _CharClassT; 431 432 public: 433 _BracketMatcher(bool __is_non_matching, 434 const _TraitsT& __traits) 435 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits), 436 _M_is_non_matching(__is_non_matching) 437 { } 438 439 bool 440 operator()(_CharT __ch) const 441 { 442 _GLIBCXX_DEBUG_ASSERT(_M_is_ready); 443 return _M_apply(__ch, _UseCache()); 444 } 445 446 void 447 _M_add_char(_CharT __c) 448 { 449 _M_char_set.push_back(_M_translator._M_translate(__c)); 450 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); 451 } 452 453 _StringT 454 _M_add_collate_element(const _StringT& __s) 455 { 456 auto __st = _M_traits.lookup_collatename(__s.data(), 457 __s.data() + __s.size()); 458 if (__st.empty()) 459 __throw_regex_error(regex_constants::error_collate, 460 "Invalid collate element."); 461 _M_char_set.push_back(_M_translator._M_translate(__st[0])); 462 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); 463 return __st; 464 } 465 466 void 467 _M_add_equivalence_class(const _StringT& __s) 468 { 469 auto __st = _M_traits.lookup_collatename(__s.data(), 470 __s.data() + __s.size()); 471 if (__st.empty()) 472 __throw_regex_error(regex_constants::error_collate, 473 "Invalid equivalence class."); 474 __st = _M_traits.transform_primary(__st.data(), 475 __st.data() + __st.size()); 476 _M_equiv_set.push_back(__st); 477 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); 478 } 479 480 // __neg should be true for \D, \S and \W only. 481 void 482 _M_add_character_class(const _StringT& __s, bool __neg) 483 { 484 auto __mask = _M_traits.lookup_classname(__s.data(), 485 __s.data() + __s.size(), 486 __icase); 487 if (__mask == 0) 488 __throw_regex_error(regex_constants::error_collate, 489 "Invalid character class."); 490 if (!__neg) 491 _M_class_set |= __mask; 492 else 493 _M_neg_class_set.push_back(__mask); 494 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); 495 } 496 497 void 498 _M_make_range(_CharT __l, _CharT __r) 499 { 500 if (__l > __r) 501 __throw_regex_error(regex_constants::error_range, 502 "Invalid range in bracket expression."); 503 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l), 504 _M_translator._M_transform(__r))); 505 _GLIBCXX_DEBUG_ONLY(_M_is_ready = false); 506 } 507 508 void 509 _M_ready() 510 { 511 std::sort(_M_char_set.begin(), _M_char_set.end()); 512 auto __end = std::unique(_M_char_set.begin(), _M_char_set.end()); 513 _M_char_set.erase(__end, _M_char_set.end()); 514 _M_make_cache(_UseCache()); 515 _GLIBCXX_DEBUG_ONLY(_M_is_ready = true); 516 } 517 518 private: 519 // Currently we only use the cache for char 520 typedef typename std::is_same<_CharT, char>::type _UseCache; 521 522 static constexpr size_t 523 _S_cache_size = 524 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value)); 525 526 struct _Dummy { }; 527 typedef typename std::conditional<_UseCache::value, 528 std::bitset<_S_cache_size>, 529 _Dummy>::type _CacheT; 530 typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT; 531 532 bool 533 _M_apply(_CharT __ch, false_type) const; 534 535 bool 536 _M_apply(_CharT __ch, true_type) const 537 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; } 538 539 void 540 _M_make_cache(true_type) 541 { 542 for (unsigned __i = 0; __i < _M_cache.size(); __i++) 543 _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type()); 544 } 545 546 void 547 _M_make_cache(false_type) 548 { } 549 550 private: 551 std::vector<_CharT> _M_char_set; 552 std::vector<_StringT> _M_equiv_set; 553 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set; 554 std::vector<_CharClassT> _M_neg_class_set; 555 _CharClassT _M_class_set; 556 _TransT _M_translator; 557 const _TraitsT& _M_traits; 558 bool _M_is_non_matching; 559 _CacheT _M_cache; 560 #ifdef _GLIBCXX_DEBUG 561 bool _M_is_ready = false; 562 #endif 563 }; 564 565 ///@} regex-detail 566 } // namespace __detail 567 _GLIBCXX_END_NAMESPACE_VERSION 568 } // namespace std 569 570 #include <bits/regex_compiler.tcc>
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
