libstdc++
|
00001 // class template regex -*- C++ -*- 00002 00003 // Copyright (C) 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file bits/regex_grep_matcher.tcc 00027 * This is an internal header file, included by other library headers. 00028 * Do not attempt to use it directly. @headername{regex} 00029 */ 00030 00031 #include <regex> 00032 00033 namespace std _GLIBCXX_VISIBILITY(default) 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00036 00037 namespace 00038 { 00039 00040 // A stack of states used in evaluating the NFA. 00041 typedef std::stack<std::__regex::_StateIdT, 00042 std::vector<std::__regex::_StateIdT> 00043 > _StateStack; 00044 00045 // Obtains the next state set given the current state set __s and the current 00046 // input character. 00047 inline std::__regex::_StateSet 00048 __move(const std::__regex::_PatternCursor& __p, 00049 const std::__regex::_Nfa& __nfa, 00050 const std::__regex::_StateSet& __s) 00051 { 00052 std::__regex::_StateSet __m; 00053 for (std::__regex::_StateSet::const_iterator __i = __s.begin(); 00054 __i != __s.end(); ++__i) 00055 { 00056 if (*__i == std::__regex::_S_invalid_state_id) 00057 continue; 00058 00059 const std::__regex::_State& __state = __nfa[*__i]; 00060 if (__state._M_opcode == std::__regex::_S_opcode_match 00061 && __state._M_matches(__p)) 00062 __m.insert(__state._M_next); 00063 } 00064 return __m; 00065 } 00066 00067 // returns true if (__s intersect __t) is not empty 00068 inline bool 00069 __includes_some(const std::__regex::_StateSet& __s, 00070 const std::__regex::_StateSet& __t) 00071 { 00072 if (__s.size() > 0 && __t.size() > 0) 00073 { 00074 std::__regex::_StateSet::const_iterator __first = __s.begin(); 00075 std::__regex::_StateSet::const_iterator __second = __t.begin(); 00076 while (__first != __s.end() && __second != __t.end()) 00077 { 00078 if (*__first < *__second) 00079 ++__first; 00080 else if (*__second < *__first) 00081 ++__second; 00082 else 00083 return true; 00084 } 00085 } 00086 return false; 00087 } 00088 00089 // If an identified state __u is not already in the current state set __e, 00090 // insert it and push it on the current state stack __s. 00091 inline void 00092 __add_visited_state(const std::__regex::_StateIdT __u, 00093 _StateStack& __s, 00094 std::__regex::_StateSet& __e) 00095 { 00096 if (__e.count(__u) == 0) 00097 { 00098 __e.insert(__u); 00099 __s.push(__u); 00100 } 00101 } 00102 00103 } // anonymous namespace 00104 00105 namespace __regex 00106 { 00107 inline _Grep_matcher:: 00108 _Grep_matcher(_PatternCursor& __p, _Results& __r, 00109 const _AutomatonPtr& __nfa, 00110 regex_constants::match_flag_type __flags) 00111 : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r) 00112 { 00113 __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start()); 00114 for (; !_M_pattern._M_at_end(); _M_pattern._M_next()) 00115 __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t)); 00116 00117 _M_results._M_set_matched(0, 00118 __includes_some(_M_nfa->_M_final_states(), __t)); 00119 } 00120 00121 // Creates the e-closure set for the initial state __i. 00122 inline _StateSet _Grep_matcher:: 00123 _M_e_closure(_StateIdT __i) 00124 { 00125 _StateSet __s; 00126 __s.insert(__i); 00127 _StateStack __stack; 00128 __stack.push(__i); 00129 return this->_M_e_closure(__stack, __s); 00130 } 00131 00132 // Creates the e-closure set for an arbitrary state set __s. 00133 inline _StateSet _Grep_matcher:: 00134 _M_e_closure(const _StateSet& __s) 00135 { 00136 _StateStack __stack; 00137 for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i) 00138 __stack.push(*__i); 00139 return this->_M_e_closure(__stack, __s); 00140 } 00141 00142 inline _StateSet _Grep_matcher:: 00143 _M_e_closure(_StateStack& __stack, const _StateSet& __s) 00144 { 00145 _StateSet __e = __s; 00146 while (!__stack.empty()) 00147 { 00148 _StateIdT __t = __stack.top(); __stack.pop(); 00149 if (__t == _S_invalid_state_id) 00150 continue; 00151 // for each __u with edge from __t to __u labeled e do ... 00152 const _State& __state = _M_nfa->operator[](__t); 00153 switch (__state._M_opcode) 00154 { 00155 case _S_opcode_alternative: 00156 __add_visited_state(__state._M_next, __stack, __e); 00157 __add_visited_state(__state._M_alt, __stack, __e); 00158 break; 00159 case _S_opcode_subexpr_begin: 00160 __add_visited_state(__state._M_next, __stack, __e); 00161 __state._M_tagger(_M_pattern, _M_results); 00162 break; 00163 case _S_opcode_subexpr_end: 00164 __add_visited_state(__state._M_next, __stack, __e); 00165 __state._M_tagger(_M_pattern, _M_results); 00166 _M_results._M_set_matched(__state._M_subexpr, true); 00167 break; 00168 case _S_opcode_accept: 00169 __add_visited_state(__state._M_next, __stack, __e); 00170 break; 00171 default: 00172 break; 00173 } 00174 } 00175 return __e; 00176 } 00177 00178 } // namespace __regex 00179 00180 _GLIBCXX_END_NAMESPACE_VERSION 00181 } // namespace