1 // class template regex -*- C++ -*- 2 3 // Copyright (C) 2010 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_grep_matcher.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 #include <regex> 32 33 namespace std _GLIBCXX_VISIBILITY(default) 34 { 35 namespace 36 { 37 // A stack of states used in evaluating the NFA. 38 typedef std::stack<std::__regex::_StateIdT, 39 std::vector<std::__regex::_StateIdT> 40 > _StateStack; 41 42 // Obtains the next state set given the current state set __s and the current 43 // input character. 44 inline std::__regex::_StateSet 45 __move(const std::__regex::_PatternCursor& __p, 46 const std::__regex::_Nfa& __nfa, 47 const std::__regex::_StateSet& __s) 48 { 49 std::__regex::_StateSet __m; 50 for (std::__regex::_StateSet::const_iterator __i = __s.begin(); 51 __i != __s.end(); ++__i) 52 { 53 if (*__i == std::__regex::_S_invalid_state_id) 54 continue; 55 56 const std::__regex::_State& __state = __nfa[*__i]; 57 if (__state._M_opcode == std::__regex::_S_opcode_match 58 && __state._M_matches(__p)) 59 __m.insert(__state._M_next); 60 } 61 return __m; 62 } 63 64 // returns true if (__s intersect __t) is not empty 65 inline bool 66 __includes_some(const std::__regex::_StateSet& __s, 67 const std::__regex::_StateSet& __t) 68 { 69 if (__s.size() > 0 && __t.size() > 0) 70 { 71 std::__regex::_StateSet::const_iterator __first = __s.begin(); 72 std::__regex::_StateSet::const_iterator __second = __t.begin(); 73 while (__first != __s.end() && __second != __t.end()) 74 { 75 if (*__first < *__second) 76 ++__first; 77 else if (*__second < *__first) 78 ++__second; 79 else 80 return true; 81 } 82 } 83 return false; 84 } 85 86 // If an identified state __u is not already in the current state set __e, 87 // insert it and push it on the current state stack __s. 88 inline void 89 __add_visited_state(const std::__regex::_StateIdT __u, 90 _StateStack& __s, 91 std::__regex::_StateSet& __e) 92 { 93 if (__e.count(__u) == 0) 94 { 95 __e.insert(__u); 96 __s.push(__u); 97 } 98 } 99 100 } // anonymous namespace 101 102 namespace __regex 103 { 104 _GLIBCXX_BEGIN_NAMESPACE_VERSION 105 106 inline _Grep_matcher:: 107 _Grep_matcher(_PatternCursor& __p, _Results& __r, 108 const _AutomatonPtr& __nfa, 109 regex_constants::match_flag_type __flags) 110 : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r) 111 { 112 __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start()); 113 for (; !_M_pattern._M_at_end(); _M_pattern._M_next()) 114 __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t)); 115 116 _M_results._M_set_matched(0, 117 __includes_some(_M_nfa->_M_final_states(), __t)); 118 } 119 120 // Creates the e-closure set for the initial state __i. 121 inline _StateSet _Grep_matcher:: 122 _M_e_closure(_StateIdT __i) 123 { 124 _StateSet __s; 125 __s.insert(__i); 126 _StateStack __stack; 127 __stack.push(__i); 128 return this->_M_e_closure(__stack, __s); 129 } 130 131 // Creates the e-closure set for an arbitrary state set __s. 132 inline _StateSet _Grep_matcher:: 133 _M_e_closure(const _StateSet& __s) 134 { 135 _StateStack __stack; 136 for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i) 137 __stack.push(*__i); 138 return this->_M_e_closure(__stack, __s); 139 } 140 141 inline _StateSet _Grep_matcher:: 142 _M_e_closure(_StateStack& __stack, const _StateSet& __s) 143 { 144 _StateSet __e = __s; 145 while (!__stack.empty()) 146 { 147 _StateIdT __t = __stack.top(); __stack.pop(); 148 if (__t == _S_invalid_state_id) 149 continue; 150 // for each __u with edge from __t to __u labeled e do ... 151 const _State& __state = _M_nfa->operator[](__t); 152 switch (__state._M_opcode) 153 { 154 case _S_opcode_alternative: 155 __add_visited_state(__state._M_next, __stack, __e); 156 __add_visited_state(__state._M_alt, __stack, __e); 157 break; 158 case _S_opcode_subexpr_begin: 159 __add_visited_state(__state._M_next, __stack, __e); 160 __state._M_tagger(_M_pattern, _M_results); 161 break; 162 case _S_opcode_subexpr_end: 163 __add_visited_state(__state._M_next, __stack, __e); 164 __state._M_tagger(_M_pattern, _M_results); 165 _M_results._M_set_matched(__state._M_subexpr, true); 166 break; 167 case _S_opcode_accept: 168 __add_visited_state(__state._M_next, __stack, __e); 169 break; 170 default: 171 break; 172 } 173 } 174 return __e; 175 } 176 177 _GLIBCXX_END_NAMESPACE_VERSION 178 } // namespace __regex 179 } // namespace 180