1 // class template regex -*- C++ -*-
3 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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}
33 namespace std _GLIBCXX_VISIBILITY(default)
37 // A stack of states used in evaluating the NFA.
38 typedef std::stack<std::__detail::_StateIdT,
39 std::vector<std::__detail::_StateIdT>
42 // Obtains the next state set given the current state set __s and the current
44 inline std::__detail::_StateSet
45 __move(const std::__detail::_PatternCursor& __p,
46 const std::__detail::_Nfa& __nfa,
47 const std::__detail::_StateSet& __s)
49 std::__detail::_StateSet __m;
50 for (std::__detail::_StateSet::const_iterator __i = __s.begin();
51 __i != __s.end(); ++__i)
53 if (*__i == std::__detail::_S_invalid_state_id)
56 const std::__detail::_State& __state = __nfa[*__i];
57 if (__state._M_opcode == std::__detail::_S_opcode_match
58 && __state._M_matches(__p))
59 __m.insert(__state._M_next);
64 // returns true if (__s intersect __t) is not empty
66 __includes_some(const std::__detail::_StateSet& __s,
67 const std::__detail::_StateSet& __t)
69 if (__s.size() > 0 && __t.size() > 0)
71 std::__detail::_StateSet::const_iterator __first = __s.begin();
72 std::__detail::_StateSet::const_iterator __second = __t.begin();
73 while (__first != __s.end() && __second != __t.end())
75 if (*__first < *__second)
77 else if (*__second < *__first)
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.
89 __add_visited_state(const std::__detail::_StateIdT __u,
91 std::__detail::_StateSet& __e)
93 if (__e.count(__u) == 0)
100 } // anonymous namespace
104 _GLIBCXX_BEGIN_NAMESPACE_VERSION
106 // _M_dfs() take a state, along with current string cursor(_M_pattern),
107 // trying to match current state with current character.
108 // Only _S_opcode_match will consume a character.
109 // TODO: This is too slow. Try to compile the NFA to a DFA.
110 template<bool __match_mode>
112 _M_dfs(_StateIdT __i)
114 if (__i == _S_invalid_state_id)
115 // This is not that certain. Need deeper investigate.
117 const auto& __state = (*_M_nfa)[__i];
119 switch (__state._M_opcode)
121 case _S_opcode_alternative:
122 // Greedy mode by default. For non-greedy mode,
123 // swap _M_alt and _M_next.
124 __ret = _M_dfs<__match_mode>(__state._M_alt)
125 || _M_dfs<__match_mode>(__state._M_next);
127 case _S_opcode_subexpr_begin:
128 __state._M_tagger(_M_pattern, _M_results);
129 __ret = _M_dfs<__match_mode>(__state._M_next);
131 case _S_opcode_subexpr_end:
132 __state._M_tagger(_M_pattern, _M_results);
133 __ret = _M_dfs<__match_mode>(__state._M_next);
134 _M_results._M_set_matched(__state._M_subexpr, __ret);
136 case _S_opcode_match:
137 if (!_M_pattern._M_at_end() && __state._M_matches(_M_pattern))
139 _M_pattern._M_next();
140 __ret = _M_dfs<__match_mode>(__state._M_next);
141 _M_pattern._M_prev();
144 case _S_opcode_accept:
146 __ret = _M_pattern._M_at_end();
151 _GLIBCXX_DEBUG_ASSERT( false );
156 inline void _Grep_matcher::
159 __detail::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
160 for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
161 __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
163 _M_results._M_set_matched(0,
164 __includes_some(_M_nfa->_M_final_states(), __t));
167 inline void _Grep_matcher::
168 _M_search_from_first()
170 __detail::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
171 for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
173 if (__includes_some(_M_nfa->_M_final_states(), __t)) // KISS
175 _M_results._M_set_matched(0, true);
178 __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
180 _M_results._M_set_matched(0, false);
183 // Creates the e-closure set for the initial state __i.
184 inline _StateSet _Grep_matcher::
185 _M_e_closure(_StateIdT __i)
191 return this->_M_e_closure(__stack, __s);
194 // Creates the e-closure set for an arbitrary state set __s.
195 inline _StateSet _Grep_matcher::
196 _M_e_closure(const _StateSet& __s)
199 for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i)
201 return this->_M_e_closure(__stack, __s);
204 inline _StateSet _Grep_matcher::
205 _M_e_closure(_StateStack& __stack, const _StateSet& __s)
208 while (!__stack.empty())
210 _StateIdT __t = __stack.top(); __stack.pop();
211 if (__t == _S_invalid_state_id)
213 // for each __u with edge from __t to __u labeled e do ...
214 const _State& __state = _M_nfa->operator[](__t);
215 switch (__state._M_opcode)
217 case _S_opcode_alternative:
218 __add_visited_state(__state._M_next, __stack, __e);
219 __add_visited_state(__state._M_alt, __stack, __e);
221 case _S_opcode_subexpr_begin:
222 __add_visited_state(__state._M_next, __stack, __e);
223 __state._M_tagger(_M_pattern, _M_results);
225 case _S_opcode_subexpr_end:
226 __add_visited_state(__state._M_next, __stack, __e);
227 __state._M_tagger(_M_pattern, _M_results);
228 _M_results._M_set_matched(__state._M_subexpr, true);
230 case _S_opcode_accept:
231 __add_visited_state(__state._M_next, __stack, __e);
240 _GLIBCXX_END_NAMESPACE_VERSION
241 } // namespace __detail