1 // class template regex -*- C++ -*- 2 3 // Copyright (C) 2013-2014 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.tcc 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 // FIXME make comments doxygen format. 32 33 // This compiler refers to "Regular Expression Matching Can Be Simple And Fast" 34 // (http://swtch.com/~rsc/regexp/regexp1.html"), 35 // but doesn't strictly follow it. 36 // 37 // When compiling, states are *chained* instead of tree- or graph-constructed. 38 // It's more like structured programs: there's if statement and loop statement. 39 // 40 // For alternative structure(say "a|b"), aka "if statement", two branchs should 41 // be constructed. However, these two shall merge to an "end_tag" at the end of 42 // this operator: 43 // 44 // branch1 45 // / \ 46 // => begin_tag end_tag => 47 // \ / 48 // branch2 49 // 50 // This is the difference between this implementation and that in Russ's 51 // article. 52 // 53 // That's why we introduced dummy node here ------ "end_tag" is a dummy node. 54 // All dummy node will be eliminated at the end of compiling process. 55 56 namespace std _GLIBCXX_VISIBILITY(default) 57 { 58 namespace __detail 59 { 60 _GLIBCXX_BEGIN_NAMESPACE_VERSION 61 62 template<typename _TraitsT> 63 _Compiler<_TraitsT>:: _Compiler(_IterT __b,_IterT __e,const _TraitsT & __traits,_FlagT __flags)64 _Compiler(_IterT __b, _IterT __e, 65 const _TraitsT& __traits, _FlagT __flags) 66 : _M_flags((__flags 67 & (regex_constants::ECMAScript 68 | regex_constants::basic 69 | regex_constants::extended 70 | regex_constants::grep 71 | regex_constants::egrep 72 | regex_constants::awk)) 73 ? __flags 74 : __flags | regex_constants::ECMAScript), 75 _M_traits(__traits), 76 _M_ctype(std::use_facet<_CtypeT>(_M_traits.getloc())), 77 _M_scanner(__b, __e, _M_flags, _M_traits.getloc()), 78 _M_nfa(_M_flags) 79 { 80 _StateSeqT __r(_M_nfa, _M_nfa._M_start()); 81 __r._M_append(_M_nfa._M_insert_subexpr_begin()); 82 this->_M_disjunction(); 83 if (!_M_match_token(_ScannerT::_S_token_eof)) 84 __throw_regex_error(regex_constants::error_paren); 85 __r._M_append(_M_pop()); 86 _GLIBCXX_DEBUG_ASSERT(_M_stack.empty()); 87 __r._M_append(_M_nfa._M_insert_subexpr_end()); 88 __r._M_append(_M_nfa._M_insert_accept()); 89 _M_nfa._M_eliminate_dummy(); 90 } 91 92 template<typename _TraitsT> 93 void 94 _Compiler<_TraitsT>:: _M_disjunction()95 _M_disjunction() 96 { 97 this->_M_alternative(); 98 while (_M_match_token(_ScannerT::_S_token_or)) 99 { 100 _StateSeqT __alt1 = _M_pop(); 101 this->_M_alternative(); 102 _StateSeqT __alt2 = _M_pop(); 103 auto __end = _M_nfa._M_insert_dummy(); 104 __alt1._M_append(__end); 105 __alt2._M_append(__end); 106 _M_stack.push(_StateSeqT(_M_nfa, 107 _M_nfa._M_insert_alt(__alt1._M_start, 108 __alt2._M_start, false), 109 __end)); 110 } 111 } 112 113 template<typename _TraitsT> 114 void 115 _Compiler<_TraitsT>:: _M_alternative()116 _M_alternative() 117 { 118 if (this->_M_term()) 119 { 120 _StateSeqT __re = _M_pop(); 121 this->_M_alternative(); 122 __re._M_append(_M_pop()); 123 _M_stack.push(__re); 124 } 125 else 126 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_dummy())); 127 } 128 129 template<typename _TraitsT> 130 bool 131 _Compiler<_TraitsT>:: _M_term()132 _M_term() 133 { 134 if (this->_M_assertion()) 135 return true; 136 if (this->_M_atom()) 137 { 138 while (this->_M_quantifier()); 139 return true; 140 } 141 return false; 142 } 143 144 template<typename _TraitsT> 145 bool 146 _Compiler<_TraitsT>:: _M_assertion()147 _M_assertion() 148 { 149 if (_M_match_token(_ScannerT::_S_token_line_begin)) 150 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_begin())); 151 else if (_M_match_token(_ScannerT::_S_token_line_end)) 152 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_end())); 153 else if (_M_match_token(_ScannerT::_S_token_word_bound)) 154 // _M_value[0] == 'n' means it's negtive, say "not word boundary". 155 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. 156 _M_insert_word_bound(_M_value[0] == 'n'))); 157 else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin)) 158 { 159 auto __neg = _M_value[0] == 'n'; 160 this->_M_disjunction(); 161 if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) 162 __throw_regex_error(regex_constants::error_paren); 163 auto __tmp = _M_pop(); 164 __tmp._M_append(_M_nfa._M_insert_accept()); 165 _M_stack.push( 166 _StateSeqT( 167 _M_nfa, 168 _M_nfa._M_insert_lookahead(__tmp._M_start, __neg))); 169 } 170 else 171 return false; 172 return true; 173 } 174 175 template<typename _TraitsT> 176 bool 177 _Compiler<_TraitsT>:: _M_quantifier()178 _M_quantifier() 179 { 180 bool __neg = (_M_flags & regex_constants::ECMAScript); 181 auto __init = [this, &__neg]() 182 { 183 if (_M_stack.empty()) 184 __throw_regex_error(regex_constants::error_badrepeat); 185 __neg = __neg && _M_match_token(_ScannerT::_S_token_opt); 186 }; 187 if (_M_match_token(_ScannerT::_S_token_closure0)) 188 { 189 __init(); 190 auto __e = _M_pop(); 191 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id, 192 __e._M_start, __neg)); 193 __e._M_append(__r); 194 _M_stack.push(__r); 195 } 196 else if (_M_match_token(_ScannerT::_S_token_closure1)) 197 { 198 __init(); 199 auto __e = _M_pop(); 200 __e._M_append(_M_nfa._M_insert_alt(_S_invalid_state_id, __e._M_start, 201 __neg)); 202 _M_stack.push(__e); 203 } 204 else if (_M_match_token(_ScannerT::_S_token_opt)) 205 { 206 __init(); 207 auto __e = _M_pop(); 208 auto __end = _M_nfa._M_insert_dummy(); 209 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id, 210 __e._M_start, __neg)); 211 __e._M_append(__end); 212 __r._M_append(__end); 213 _M_stack.push(__r); 214 } 215 else if (_M_match_token(_ScannerT::_S_token_interval_begin)) 216 { 217 if (_M_stack.empty()) 218 __throw_regex_error(regex_constants::error_badrepeat); 219 if (!_M_match_token(_ScannerT::_S_token_dup_count)) 220 __throw_regex_error(regex_constants::error_badbrace); 221 _StateSeqT __r(_M_pop()); 222 _StateSeqT __e(_M_nfa, _M_nfa._M_insert_dummy()); 223 long __min_rep = _M_cur_int_value(10); 224 bool __infi = false; 225 long __n; 226 227 // {3 228 if (_M_match_token(_ScannerT::_S_token_comma)) 229 if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7} 230 __n = _M_cur_int_value(10) - __min_rep; 231 else 232 __infi = true; 233 else 234 __n = 0; 235 if (!_M_match_token(_ScannerT::_S_token_interval_end)) 236 __throw_regex_error(regex_constants::error_brace); 237 238 __neg = __neg && _M_match_token(_ScannerT::_S_token_opt); 239 240 for (long __i = 0; __i < __min_rep; ++__i) 241 __e._M_append(__r._M_clone()); 242 243 if (__infi) 244 { 245 auto __tmp = __r._M_clone(); 246 _StateSeqT __s(_M_nfa, 247 _M_nfa._M_insert_alt(_S_invalid_state_id, 248 __tmp._M_start, __neg)); 249 __tmp._M_append(__s); 250 __e._M_append(__s); 251 } 252 else 253 { 254 if (__n < 0) 255 __throw_regex_error(regex_constants::error_badbrace); 256 auto __end = _M_nfa._M_insert_dummy(); 257 // _M_alt is the "match more" branch, and _M_next is the 258 // "match less" one. Switch _M_alt and _M_next of all created 259 // nodes. This is a hacking but IMO works well. 260 std::stack<_StateIdT> __stack; 261 for (long __i = 0; __i < __n; ++__i) 262 { 263 auto __tmp = __r._M_clone(); 264 auto __alt = _M_nfa._M_insert_alt(__tmp._M_start, 265 __end, __neg); 266 __stack.push(__alt); 267 __e._M_append(_StateSeqT(_M_nfa, __alt, __tmp._M_end)); 268 } 269 __e._M_append(__end); 270 while (!__stack.empty()) 271 { 272 auto& __tmp = _M_nfa[__stack.top()]; 273 __stack.pop(); 274 std::swap(__tmp._M_next, __tmp._M_alt); 275 } 276 } 277 _M_stack.push(__e); 278 } 279 else 280 return false; 281 return true; 282 } 283 284 #define __INSERT_REGEX_MATCHER(__func, args...)\ 285 do\ 286 if (!(_M_flags & regex_constants::icase))\ 287 if (!(_M_flags & regex_constants::collate))\ 288 __func<false, false>(args);\ 289 else\ 290 __func<false, true>(args);\ 291 else\ 292 if (!(_M_flags & regex_constants::collate))\ 293 __func<true, false>(args);\ 294 else\ 295 __func<true, true>(args);\ 296 while (false) 297 298 template<typename _TraitsT> 299 bool 300 _Compiler<_TraitsT>:: _M_atom()301 _M_atom() 302 { 303 if (_M_match_token(_ScannerT::_S_token_anychar)) 304 { 305 if (!(_M_flags & regex_constants::ECMAScript)) 306 __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix); 307 else 308 __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma); 309 } 310 else if (_M_try_char()) 311 __INSERT_REGEX_MATCHER(_M_insert_char_matcher); 312 else if (_M_match_token(_ScannerT::_S_token_backref)) 313 _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. 314 _M_insert_backref(_M_cur_int_value(10)))); 315 else if (_M_match_token(_ScannerT::_S_token_quoted_class)) 316 __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher); 317 else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin)) 318 { 319 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_dummy()); 320 this->_M_disjunction(); 321 if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) 322 __throw_regex_error(regex_constants::error_paren); 323 __r._M_append(_M_pop()); 324 _M_stack.push(__r); 325 } 326 else if (_M_match_token(_ScannerT::_S_token_subexpr_begin)) 327 { 328 _StateSeqT __r(_M_nfa, _M_nfa._M_insert_subexpr_begin()); 329 this->_M_disjunction(); 330 if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) 331 __throw_regex_error(regex_constants::error_paren); 332 __r._M_append(_M_pop()); 333 __r._M_append(_M_nfa._M_insert_subexpr_end()); 334 _M_stack.push(__r); 335 } 336 else if (!_M_bracket_expression()) 337 return false; 338 return true; 339 } 340 341 template<typename _TraitsT> 342 bool 343 _Compiler<_TraitsT>:: _M_bracket_expression()344 _M_bracket_expression() 345 { 346 bool __neg = 347 _M_match_token(_ScannerT::_S_token_bracket_neg_begin); 348 if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin))) 349 return false; 350 __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg); 351 return true; 352 } 353 #undef __INSERT_REGEX_MATCHER 354 355 template<typename _TraitsT> 356 template<bool __icase, bool __collate> 357 void 358 _Compiler<_TraitsT>:: _M_insert_any_matcher_ecma()359 _M_insert_any_matcher_ecma() 360 { 361 _M_stack.push(_StateSeqT(_M_nfa, 362 _M_nfa._M_insert_matcher 363 (_AnyMatcher<_TraitsT, true, __icase, __collate> 364 (_M_traits)))); 365 } 366 367 template<typename _TraitsT> 368 template<bool __icase, bool __collate> 369 void 370 _Compiler<_TraitsT>:: _M_insert_any_matcher_posix()371 _M_insert_any_matcher_posix() 372 { 373 _M_stack.push(_StateSeqT(_M_nfa, 374 _M_nfa._M_insert_matcher 375 (_AnyMatcher<_TraitsT, false, __icase, __collate> 376 (_M_traits)))); 377 } 378 379 template<typename _TraitsT> 380 template<bool __icase, bool __collate> 381 void 382 _Compiler<_TraitsT>:: _M_insert_char_matcher()383 _M_insert_char_matcher() 384 { 385 _M_stack.push(_StateSeqT(_M_nfa, 386 _M_nfa._M_insert_matcher 387 (_CharMatcher<_TraitsT, __icase, __collate> 388 (_M_value[0], _M_traits)))); 389 } 390 391 template<typename _TraitsT> 392 template<bool __icase, bool __collate> 393 void 394 _Compiler<_TraitsT>:: _M_insert_character_class_matcher()395 _M_insert_character_class_matcher() 396 { 397 _GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1); 398 _BracketMatcher<_TraitsT, __icase, __collate> __matcher 399 (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits); 400 __matcher._M_add_character_class(_M_value, false); 401 __matcher._M_ready(); 402 _M_stack.push(_StateSeqT(_M_nfa, 403 _M_nfa._M_insert_matcher(std::move(__matcher)))); 404 } 405 406 template<typename _TraitsT> 407 template<bool __icase, bool __collate> 408 void 409 _Compiler<_TraitsT>:: _M_insert_bracket_matcher(bool __neg)410 _M_insert_bracket_matcher(bool __neg) 411 { 412 _BracketMatcher<_TraitsT, __icase, __collate> __matcher(__neg, _M_traits); 413 pair<bool, _CharT> __last_char; // Optional<_CharT> 414 __last_char.first = false; 415 if (!(_M_flags & regex_constants::ECMAScript)) 416 if (_M_try_char()) 417 { 418 __matcher._M_add_char(_M_value[0]); 419 __last_char.first = true; 420 __last_char.second = _M_value[0]; 421 } 422 while (_M_expression_term(__last_char, __matcher)); 423 __matcher._M_ready(); 424 _M_stack.push(_StateSeqT( 425 _M_nfa, 426 _M_nfa._M_insert_matcher(std::move(__matcher)))); 427 } 428 429 template<typename _TraitsT> 430 template<bool __icase, bool __collate> 431 bool 432 _Compiler<_TraitsT>:: _M_expression_term(pair<bool,_CharT> & __last_char,_BracketMatcher<_TraitsT,__icase,__collate> & __matcher)433 _M_expression_term(pair<bool, _CharT>& __last_char, 434 _BracketMatcher<_TraitsT, __icase, __collate>& __matcher) 435 436 { 437 if (_M_match_token(_ScannerT::_S_token_bracket_end)) 438 return false; 439 440 if (_M_match_token(_ScannerT::_S_token_collsymbol)) 441 { 442 auto __symbol = __matcher._M_add_collate_element(_M_value); 443 if (__symbol.size() == 1) 444 { 445 __last_char.first = true; 446 __last_char.second = __symbol[0]; 447 } 448 } 449 else if (_M_match_token(_ScannerT::_S_token_equiv_class_name)) 450 __matcher._M_add_equivalence_class(_M_value); 451 else if (_M_match_token(_ScannerT::_S_token_char_class_name)) 452 __matcher._M_add_character_class(_M_value, false); 453 // POSIX doesn't allow '-' as a start-range char (say [a-z--0]), 454 // except when the '-' is the first or last character in the bracket 455 // expression ([--0]). ECMAScript treats all '-' after a range as a 456 // normal character. Also see above, where _M_expression_term gets called. 457 // 458 // As a result, POSIX rejects [-----], but ECMAScript doesn't. 459 // Boost (1.57.0) always uses POSIX style even in its ECMAScript syntax. 460 // Clang (3.5) always uses ECMAScript style even in its POSIX syntax. 461 // 462 // It turns out that no one reads BNFs ;) 463 else if (_M_try_char()) 464 { 465 if (!__last_char.first) 466 { 467 __matcher._M_add_char(_M_value[0]); 468 if (_M_value[0] == '-' 469 && !(_M_flags & regex_constants::ECMAScript)) 470 { 471 if (_M_match_token(_ScannerT::_S_token_bracket_end)) 472 return false; 473 __throw_regex_error(regex_constants::error_range); 474 } 475 __last_char.first = true; 476 __last_char.second = _M_value[0]; 477 } 478 else 479 { 480 if (_M_value[0] == '-') 481 { 482 if (_M_try_char()) 483 { 484 __matcher._M_make_range(__last_char.second , _M_value[0]); 485 __last_char.first = false; 486 } 487 else 488 { 489 if (_M_scanner._M_get_token() 490 != _ScannerT::_S_token_bracket_end) 491 __throw_regex_error(regex_constants::error_range); 492 __matcher._M_add_char(_M_value[0]); 493 } 494 } 495 else 496 { 497 __matcher._M_add_char(_M_value[0]); 498 __last_char.second = _M_value[0]; 499 } 500 } 501 } 502 else if (_M_match_token(_ScannerT::_S_token_quoted_class)) 503 __matcher._M_add_character_class(_M_value, 504 _M_ctype.is(_CtypeT::upper, 505 _M_value[0])); 506 else 507 __throw_regex_error(regex_constants::error_brack); 508 509 return true; 510 } 511 512 template<typename _TraitsT> 513 bool 514 _Compiler<_TraitsT>:: _M_try_char()515 _M_try_char() 516 { 517 bool __is_char = false; 518 if (_M_match_token(_ScannerT::_S_token_oct_num)) 519 { 520 __is_char = true; 521 _M_value.assign(1, _M_cur_int_value(8)); 522 } 523 else if (_M_match_token(_ScannerT::_S_token_hex_num)) 524 { 525 __is_char = true; 526 _M_value.assign(1, _M_cur_int_value(16)); 527 } 528 else if (_M_match_token(_ScannerT::_S_token_ord_char)) 529 __is_char = true; 530 return __is_char; 531 } 532 533 template<typename _TraitsT> 534 bool 535 _Compiler<_TraitsT>:: _M_match_token(_TokenT token)536 _M_match_token(_TokenT token) 537 { 538 if (token == _M_scanner._M_get_token()) 539 { 540 _M_value = _M_scanner._M_get_value(); 541 _M_scanner._M_advance(); 542 return true; 543 } 544 return false; 545 } 546 547 template<typename _TraitsT> 548 int 549 _Compiler<_TraitsT>:: _M_cur_int_value(int __radix)550 _M_cur_int_value(int __radix) 551 { 552 long __v = 0; 553 for (typename _StringT::size_type __i = 0; 554 __i < _M_value.length(); ++__i) 555 __v =__v * __radix + _M_traits.value(_M_value[__i], __radix); 556 return __v; 557 } 558 559 template<typename _TraitsT, bool __icase, bool __collate> 560 bool 561 _BracketMatcher<_TraitsT, __icase, __collate>:: _M_apply(_CharT __ch,false_type) const562 _M_apply(_CharT __ch, false_type) const 563 { 564 bool __ret = false; 565 if (std::find(_M_char_set.begin(), _M_char_set.end(), 566 _M_translator._M_translate(__ch)) 567 != _M_char_set.end()) 568 __ret = true; 569 else 570 { 571 auto __s = _M_translator._M_transform(__ch); 572 for (auto& __it : _M_range_set) 573 if (__it.first <= __s && __s <= __it.second) 574 { 575 __ret = true; 576 break; 577 } 578 if (_M_traits.isctype(__ch, _M_class_set)) 579 __ret = true; 580 else if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(), 581 _M_traits.transform_primary(&__ch, &__ch+1)) 582 != _M_equiv_set.end()) 583 __ret = true; 584 else 585 { 586 for (auto& __it : _M_neg_class_set) 587 if (!_M_traits.isctype(__ch, __it)) 588 { 589 __ret = true; 590 break; 591 } 592 } 593 } 594 if (_M_is_non_matching) 595 return !__ret; 596 else 597 return __ret; 598 } 599 600 _GLIBCXX_END_NAMESPACE_VERSION 601 } // namespace __detail 602 } // namespace 603