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 namespace
00036 {
00037
00038 typedef std::stack<std::__regex::_StateIdT,
00039 std::vector<std::__regex::_StateIdT>
00040 > _StateStack;
00041
00042
00043
00044 inline std::__regex::_StateSet
00045 __move(const std::__regex::_PatternCursor& __p,
00046 const std::__regex::_Nfa& __nfa,
00047 const std::__regex::_StateSet& __s)
00048 {
00049 std::__regex::_StateSet __m;
00050 for (std::__regex::_StateSet::const_iterator __i = __s.begin();
00051 __i != __s.end(); ++__i)
00052 {
00053 if (*__i == std::__regex::_S_invalid_state_id)
00054 continue;
00055
00056 const std::__regex::_State& __state = __nfa[*__i];
00057 if (__state._M_opcode == std::__regex::_S_opcode_match
00058 && __state._M_matches(__p))
00059 __m.insert(__state._M_next);
00060 }
00061 return __m;
00062 }
00063
00064
00065 inline bool
00066 __includes_some(const std::__regex::_StateSet& __s,
00067 const std::__regex::_StateSet& __t)
00068 {
00069 if (__s.size() > 0 && __t.size() > 0)
00070 {
00071 std::__regex::_StateSet::const_iterator __first = __s.begin();
00072 std::__regex::_StateSet::const_iterator __second = __t.begin();
00073 while (__first != __s.end() && __second != __t.end())
00074 {
00075 if (*__first < *__second)
00076 ++__first;
00077 else if (*__second < *__first)
00078 ++__second;
00079 else
00080 return true;
00081 }
00082 }
00083 return false;
00084 }
00085
00086
00087
00088 inline void
00089 __add_visited_state(const std::__regex::_StateIdT __u,
00090 _StateStack& __s,
00091 std::__regex::_StateSet& __e)
00092 {
00093 if (__e.count(__u) == 0)
00094 {
00095 __e.insert(__u);
00096 __s.push(__u);
00097 }
00098 }
00099
00100 }
00101
00102 namespace __regex
00103 {
00104 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00105
00106 inline _Grep_matcher::
00107 _Grep_matcher(_PatternCursor& __p, _Results& __r,
00108 const _AutomatonPtr& __nfa,
00109 regex_constants::match_flag_type __flags)
00110 : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r)
00111 {
00112 __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
00113 for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
00114 __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
00115
00116 _M_results._M_set_matched(0,
00117 __includes_some(_M_nfa->_M_final_states(), __t));
00118 }
00119
00120
00121 inline _StateSet _Grep_matcher::
00122 _M_e_closure(_StateIdT __i)
00123 {
00124 _StateSet __s;
00125 __s.insert(__i);
00126 _StateStack __stack;
00127 __stack.push(__i);
00128 return this->_M_e_closure(__stack, __s);
00129 }
00130
00131
00132 inline _StateSet _Grep_matcher::
00133 _M_e_closure(const _StateSet& __s)
00134 {
00135 _StateStack __stack;
00136 for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i)
00137 __stack.push(*__i);
00138 return this->_M_e_closure(__stack, __s);
00139 }
00140
00141 inline _StateSet _Grep_matcher::
00142 _M_e_closure(_StateStack& __stack, const _StateSet& __s)
00143 {
00144 _StateSet __e = __s;
00145 while (!__stack.empty())
00146 {
00147 _StateIdT __t = __stack.top(); __stack.pop();
00148 if (__t == _S_invalid_state_id)
00149 continue;
00150
00151 const _State& __state = _M_nfa->operator[](__t);
00152 switch (__state._M_opcode)
00153 {
00154 case _S_opcode_alternative:
00155 __add_visited_state(__state._M_next, __stack, __e);
00156 __add_visited_state(__state._M_alt, __stack, __e);
00157 break;
00158 case _S_opcode_subexpr_begin:
00159 __add_visited_state(__state._M_next, __stack, __e);
00160 __state._M_tagger(_M_pattern, _M_results);
00161 break;
00162 case _S_opcode_subexpr_end:
00163 __add_visited_state(__state._M_next, __stack, __e);
00164 __state._M_tagger(_M_pattern, _M_results);
00165 _M_results._M_set_matched(__state._M_subexpr, true);
00166 break;
00167 case _S_opcode_accept:
00168 __add_visited_state(__state._M_next, __stack, __e);
00169 break;
00170 default:
00171 break;
00172 }
00173 }
00174 return __e;
00175 }
00176
00177 _GLIBCXX_END_NAMESPACE_VERSION
00178 }
00179 }