Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #include <regex>
00032
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00036
00037 namespace
00038 {
00039
00040
00041 typedef std::stack<std::__regex::_StateIdT,
00042 std::vector<std::__regex::_StateIdT>
00043 > _StateStack;
00044
00045
00046
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
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
00090
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 }
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
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
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
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 }
00179
00180 _GLIBCXX_END_NAMESPACE_VERSION
00181 }