Line data Source code
1 : // class template regex -*- C++ -*-
2 :
3 : // Copyright (C) 2013-2019 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_executor.h
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 : // FIXME convert comments to doxygen format.
32 :
33 : namespace std _GLIBCXX_VISIBILITY(default)
34 : {
35 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 :
37 : namespace __detail
38 : {
39 : /**
40 : * @addtogroup regex-detail
41 : * @{
42 : */
43 :
44 : /**
45 : * @brief Takes a regex and an input string and does the matching.
46 : *
47 : * The %_Executor class has two modes: DFS mode and BFS mode, controlled
48 : * by the template parameter %__dfs_mode.
49 : */
50 : template<typename _BiIter, typename _Alloc, typename _TraitsT,
51 : bool __dfs_mode>
52 : class _Executor
53 : {
54 : using __search_mode = integral_constant<bool, __dfs_mode>;
55 : using __dfs = true_type;
56 : using __bfs = false_type;
57 :
58 : enum class _Match_mode : unsigned char { _Exact, _Prefix };
59 :
60 : public:
61 : typedef typename iterator_traits<_BiIter>::value_type _CharT;
62 : typedef basic_regex<_CharT, _TraitsT> _RegexT;
63 : typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec;
64 : typedef regex_constants::match_flag_type _FlagT;
65 : typedef typename _TraitsT::char_class_type _ClassT;
66 : typedef _NFA<_TraitsT> _NFAT;
67 :
68 : public:
69 955 : _Executor(_BiIter __begin,
70 : _BiIter __end,
71 : _ResultsVec& __results,
72 : const _RegexT& __re,
73 : _FlagT __flags)
74 : : _M_begin(__begin),
75 : _M_end(__end),
76 : _M_re(__re),
77 955 : _M_nfa(*__re._M_automaton),
78 : _M_results(__results),
79 : _M_rep_count(_M_nfa.size()),
80 955 : _M_states(_M_nfa._M_start(), _M_nfa.size()),
81 955 : _M_flags((__flags & regex_constants::match_prev_avail)
82 : ? (__flags
83 : & ~regex_constants::match_not_bol
84 0 : & ~regex_constants::match_not_bow)
85 955 : : __flags)
86 955 : { }
87 :
88 : // Set matched when string exactly matches the pattern.
89 : bool
90 955 : _M_match()
91 : {
92 955 : _M_current = _M_begin;
93 955 : return _M_main(_Match_mode::_Exact);
94 : }
95 :
96 : // Set matched when some prefix of the string matches the pattern.
97 : bool
98 0 : _M_search_from_first()
99 : {
100 0 : _M_current = _M_begin;
101 0 : return _M_main(_Match_mode::_Prefix);
102 : }
103 :
104 : bool
105 : _M_search();
106 :
107 : private:
108 : void
109 : _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
110 :
111 : void
112 : _M_handle_repeat(_Match_mode, _StateIdT);
113 :
114 : void
115 : _M_handle_subexpr_begin(_Match_mode, _StateIdT);
116 :
117 : void
118 : _M_handle_subexpr_end(_Match_mode, _StateIdT);
119 :
120 : void
121 : _M_handle_line_begin_assertion(_Match_mode, _StateIdT);
122 :
123 : void
124 : _M_handle_line_end_assertion(_Match_mode, _StateIdT);
125 :
126 : void
127 : _M_handle_word_boundary(_Match_mode, _StateIdT);
128 :
129 : void
130 : _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
131 :
132 : void
133 : _M_handle_match(_Match_mode, _StateIdT);
134 :
135 : void
136 : _M_handle_backref(_Match_mode, _StateIdT);
137 :
138 : void
139 : _M_handle_accept(_Match_mode, _StateIdT);
140 :
141 : void
142 : _M_handle_alternative(_Match_mode, _StateIdT);
143 :
144 : void
145 : _M_dfs(_Match_mode __match_mode, _StateIdT __start);
146 :
147 : bool
148 955 : _M_main(_Match_mode __match_mode)
149 955 : { return _M_main_dispatch(__match_mode, __search_mode{}); }
150 :
151 : bool
152 : _M_main_dispatch(_Match_mode __match_mode, __dfs);
153 :
154 : bool
155 : _M_main_dispatch(_Match_mode __match_mode, __bfs);
156 :
157 : bool
158 0 : _M_is_word(_CharT __ch) const
159 : {
160 : static const _CharT __s[2] = { 'w' };
161 0 : return _M_re._M_automaton->_M_traits.isctype
162 0 : (__ch, _M_re._M_automaton->_M_traits.lookup_classname(__s, __s+1));
163 : }
164 :
165 : bool
166 0 : _M_at_begin() const
167 : {
168 0 : return _M_current == _M_begin
169 0 : && !(_M_flags & (regex_constants::match_not_bol
170 : | regex_constants::match_prev_avail));
171 : }
172 :
173 : bool
174 0 : _M_at_end() const
175 : {
176 0 : return _M_current == _M_end
177 0 : && !(_M_flags & regex_constants::match_not_eol);
178 : }
179 :
180 : bool
181 : _M_word_boundary() const;
182 :
183 : bool
184 : _M_lookahead(_StateIdT __next);
185 :
186 : // Holds additional information used in BFS-mode.
187 : template<typename _SearchMode, typename _ResultsVec>
188 : struct _State_info;
189 :
190 : template<typename _ResultsVec>
191 : struct _State_info<__bfs, _ResultsVec>
192 : {
193 : explicit
194 0 : _State_info(_StateIdT __start, size_t __n)
195 0 : : _M_visited_states(new bool[__n]()), _M_start(__start)
196 0 : { }
197 :
198 0 : bool _M_visited(_StateIdT __i)
199 : {
200 0 : if (_M_visited_states[__i])
201 : return true;
202 0 : _M_visited_states[__i] = true;
203 : return false;
204 : }
205 :
206 0 : void _M_queue(_StateIdT __i, const _ResultsVec& __res)
207 0 : { _M_match_queue.emplace_back(__i, __res); }
208 :
209 : // Dummy implementations for BFS mode.
210 : _BiIter* _M_get_sol_pos() { return nullptr; }
211 :
212 : // Saves states that need to be considered for the next character.
213 : vector<pair<_StateIdT, _ResultsVec>> _M_match_queue;
214 : // Indicates which states are already visited.
215 : unique_ptr<bool[]> _M_visited_states;
216 : // To record current solution.
217 : _StateIdT _M_start;
218 : };
219 :
220 : template<typename _ResultsVec>
221 : struct _State_info<__dfs, _ResultsVec>
222 : {
223 : explicit
224 955 : _State_info(_StateIdT __start, size_t) : _M_start(__start)
225 : { }
226 :
227 : // Dummy implementations for DFS mode.
228 2594 : bool _M_visited(_StateIdT) const { return false; }
229 : void _M_queue(_StateIdT, const _ResultsVec&) { }
230 :
231 0 : _BiIter* _M_get_sol_pos() { return &_M_sol_pos; }
232 :
233 : // To record current solution.
234 : _StateIdT _M_start;
235 : _BiIter _M_sol_pos;
236 : };
237 :
238 : public:
239 : _ResultsVec _M_cur_results;
240 : _BiIter _M_current;
241 : _BiIter _M_begin;
242 : const _BiIter _M_end;
243 : const _RegexT& _M_re;
244 : const _NFAT& _M_nfa;
245 : _ResultsVec& _M_results;
246 : vector<pair<_BiIter, int>> _M_rep_count;
247 : _State_info<__search_mode, _ResultsVec> _M_states;
248 : _FlagT _M_flags;
249 : // Do we have a solution so far?
250 : bool _M_has_sol;
251 : };
252 :
253 : ///@} regex-detail
254 : } // namespace __detail
255 : _GLIBCXX_END_NAMESPACE_VERSION
256 : } // namespace std
257 :
258 : #include <bits/regex_executor.tcc>
|
