]>
Commit | Line | Data |
---|---|---|
6cb784b6 TS |
1 | // class template regex -*- C++ -*- |
2 | ||
85ec4feb | 3 | // Copyright (C) 2013-2018 Free Software Foundation, Inc. |
6cb784b6 TS |
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 | ||
b21abcee TS |
31 | // FIXME convert comments to doxygen format. |
32 | ||
6cb784b6 TS |
33 | namespace std _GLIBCXX_VISIBILITY(default) |
34 | { | |
6cb784b6 TS |
35 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
36 | ||
4a15d842 FD |
37 | namespace __detail |
38 | { | |
6cb784b6 TS |
39 | /** |
40 | * @addtogroup regex-detail | |
41 | * @{ | |
42 | */ | |
43 | ||
ee54a3b3 | 44 | /** |
097f0bcf | 45 | * @brief Takes a regex and an input string and does the matching. |
ee54a3b3 TS |
46 | * |
47 | * The %_Executor class has two modes: DFS mode and BFS mode, controlled | |
48 | * by the template parameter %__dfs_mode. | |
49 | */ | |
9f0d9611 | 50 | template<typename _BiIter, typename _Alloc, typename _TraitsT, |
7d9d2185 | 51 | bool __dfs_mode> |
6cb784b6 TS |
52 | class _Executor |
53 | { | |
097f0bcf JW |
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 | ||
6cb784b6 | 60 | public: |
9f0d9611 TS |
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; | |
68e69ce2 | 66 | typedef _NFA<_TraitsT> _NFAT; |
6cb784b6 | 67 | |
b21abcee TS |
68 | public: |
69 | _Executor(_BiIter __begin, | |
70 | _BiIter __end, | |
c2669da9 | 71 | _ResultsVec& __results, |
b21abcee TS |
72 | const _RegexT& __re, |
73 | _FlagT __flags) | |
74 | : _M_begin(__begin), | |
75 | _M_end(__end), | |
b21abcee | 76 | _M_re(__re), |
9f0d9611 | 77 | _M_nfa(*__re._M_automaton), |
ab1c993b | 78 | _M_results(__results), |
a670a9bb | 79 | _M_rep_count(_M_nfa.size()), |
097f0bcf | 80 | _M_states(_M_nfa._M_start(), _M_nfa.size()), |
c2669da9 TS |
81 | _M_flags((__flags & regex_constants::match_prev_avail) |
82 | ? (__flags | |
83 | & ~regex_constants::match_not_bol | |
84 | & ~regex_constants::match_not_bow) | |
097f0bcf | 85 | : __flags) |
96937d47 TS |
86 | { } |
87 | ||
097f0bcf | 88 | // Set matched when string exactly matches the pattern. |
b21abcee TS |
89 | bool |
90 | _M_match() | |
91 | { | |
9f0d9611 | 92 | _M_current = _M_begin; |
097f0bcf | 93 | return _M_main(_Match_mode::_Exact); |
b21abcee | 94 | } |
6cb784b6 TS |
95 | |
96 | // Set matched when some prefix of the string matches the pattern. | |
b21abcee TS |
97 | bool |
98 | _M_search_from_first() | |
99 | { | |
9f0d9611 | 100 | _M_current = _M_begin; |
097f0bcf | 101 | return _M_main(_Match_mode::_Prefix); |
b21abcee | 102 | } |
7b86458e | 103 | |
b21abcee | 104 | bool |
18971f1f | 105 | _M_search(); |
6cb784b6 | 106 | |
9f0d9611 | 107 | private: |
097f0bcf JW |
108 | void |
109 | _M_rep_once_more(_Match_mode __match_mode, _StateIdT); | |
a670a9bb | 110 | |
d79d6252 TS |
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 | ||
097f0bcf JW |
144 | void |
145 | _M_dfs(_Match_mode __match_mode, _StateIdT __start); | |
9f0d9611 | 146 | |
097f0bcf JW |
147 | bool |
148 | _M_main(_Match_mode __match_mode) | |
149 | { 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); | |
9f0d9611 | 156 | |
7b86458e | 157 | bool |
b21abcee | 158 | _M_is_word(_CharT __ch) const |
7b86458e | 159 | { |
7d9d2185 | 160 | static const _CharT __s[2] = { 'w' }; |
2bde8cac TS |
161 | return _M_re._M_automaton->_M_traits.isctype |
162 | (__ch, _M_re._M_automaton->_M_traits.lookup_classname(__s, __s+1)); | |
b21abcee TS |
163 | } |
164 | ||
165 | bool | |
166 | _M_at_begin() const | |
167 | { | |
168 | return _M_current == _M_begin | |
169 | && !(_M_flags & (regex_constants::match_not_bol | |
170 | | regex_constants::match_prev_avail)); | |
7b86458e TS |
171 | } |
172 | ||
b21abcee TS |
173 | bool |
174 | _M_at_end() const | |
175 | { | |
176 | return _M_current == _M_end | |
177 | && !(_M_flags & regex_constants::match_not_eol); | |
178 | } | |
179 | ||
180 | bool | |
4d838433 | 181 | _M_word_boundary() const; |
b21abcee TS |
182 | |
183 | bool | |
81b7ff07 | 184 | _M_lookahead(_StateIdT __next); |
6cb784b6 | 185 | |
097f0bcf JW |
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 | _State_info(_StateIdT __start, size_t __n) | |
8aed2f2f | 195 | : _M_visited_states(new bool[__n]()), _M_start(__start) |
097f0bcf JW |
196 | { } |
197 | ||
198 | bool _M_visited(_StateIdT __i) | |
199 | { | |
200 | if (_M_visited_states[__i]) | |
201 | return true; | |
202 | _M_visited_states[__i] = true; | |
203 | return false; | |
204 | } | |
205 | ||
206 | void _M_queue(_StateIdT __i, const _ResultsVec& __res) | |
207 | { _M_match_queue.emplace_back(__i, __res); } | |
208 | ||
ad9ec7b3 TS |
209 | // Dummy implementations for BFS mode. |
210 | _BiIter* _M_get_sol_pos() { return nullptr; } | |
211 | ||
097f0bcf JW |
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 | _State_info(_StateIdT __start, size_t) : _M_start(__start) | |
225 | { } | |
226 | ||
227 | // Dummy implementations for DFS mode. | |
228 | bool _M_visited(_StateIdT) const { return false; } | |
229 | void _M_queue(_StateIdT, const _ResultsVec&) { } | |
230 | ||
ad9ec7b3 TS |
231 | _BiIter* _M_get_sol_pos() { return &_M_sol_pos; } |
232 | ||
097f0bcf JW |
233 | // To record current solution. |
234 | _StateIdT _M_start; | |
ad9ec7b3 | 235 | _BiIter _M_sol_pos; |
097f0bcf JW |
236 | }; |
237 | ||
b21abcee | 238 | public: |
ddf41e9d TS |
239 | _ResultsVec _M_cur_results; |
240 | _BiIter _M_current; | |
02ba3fc2 | 241 | _BiIter _M_begin; |
ddf41e9d TS |
242 | const _BiIter _M_end; |
243 | const _RegexT& _M_re; | |
244 | const _NFAT& _M_nfa; | |
245 | _ResultsVec& _M_results; | |
a670a9bb | 246 | vector<pair<_BiIter, int>> _M_rep_count; |
097f0bcf | 247 | _State_info<__search_mode, _ResultsVec> _M_states; |
ddf41e9d | 248 | _FlagT _M_flags; |
9f0d9611 | 249 | // Do we have a solution so far? |
ddf41e9d | 250 | bool _M_has_sol; |
6cb784b6 TS |
251 | }; |
252 | ||
253 | //@} regex-detail | |
6cb784b6 | 254 | } // namespace __detail |
4a15d842 | 255 | _GLIBCXX_END_NAMESPACE_VERSION |
6cb784b6 TS |
256 | } // namespace std |
257 | ||
258 | #include <bits/regex_executor.tcc> |