1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
| // class template regex -*- C++ -*-
// Copyright (C) 2013-2017 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/**
* @file bits/regex_executor.h
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{regex}
*/
// FIXME convert comments to doxygen format.
namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __detail
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
/**
* @addtogroup regex-detail
* @{
*/
/**
* @brief Takes a regex and an input string and does the matching.
*
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the template parameter %__dfs_mode.
*/
template<typename _BiIter, typename _Alloc, typename _TraitsT,
bool __dfs_mode>
class _Executor
{
using __search_mode = integral_constant<bool, __dfs_mode>;
using __dfs = true_type;
using __bfs = false_type;
enum class _Match_mode : unsigned char { _Exact, _Prefix };
public:
typedef typename iterator_traits<_BiIter>::value_type _CharT;
typedef basic_regex<_CharT, _TraitsT> _RegexT;
typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec;
typedef regex_constants::match_flag_type _FlagT;
typedef typename _TraitsT::char_class_type _ClassT;
typedef _NFA<_TraitsT> _NFAT;
public:
_Executor(_BiIter __begin,
_BiIter __end,
_ResultsVec& __results,
const _RegexT& __re,
_FlagT __flags)
: _M_begin(__begin),
_M_end(__end),
_M_re(__re),
_M_nfa(*__re._M_automaton),
_M_results(__results),
_M_rep_count(_M_nfa.size()),
_M_states(_M_nfa._M_start(), _M_nfa.size()),
_M_flags((__flags & regex_constants::match_prev_avail)
? (__flags
& ~regex_constants::match_not_bol
& ~regex_constants::match_not_bow)
: __flags)
{ }
// Set matched when string exactly matches the pattern.
bool
_M_match()
{
_M_current = _M_begin;
return _M_main(_Match_mode::_Exact);
}
// Set matched when some prefix of the string matches the pattern.
bool
_M_search_from_first()
{
_M_current = _M_begin;
return _M_main(_Match_mode::_Prefix);
}
bool
_M_search();
private:
void
_M_rep_once_more(_Match_mode __match_mode, _StateIdT);
void
_M_handle_repeat(_Match_mode, _StateIdT);
void
_M_handle_subexpr_begin(_Match_mode, _StateIdT);
void
_M_handle_subexpr_end(_Match_mode, _StateIdT);
void
_M_handle_line_begin_assertion(_Match_mode, _StateIdT);
void
_M_handle_line_end_assertion(_Match_mode, _StateIdT);
void
_M_handle_word_boundary(_Match_mode, _StateIdT);
void
_M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
void
_M_handle_match(_Match_mode, _StateIdT);
void
_M_handle_backref(_Match_mode, _StateIdT);
void
_M_handle_accept(_Match_mode, _StateIdT);
void
_M_handle_alternative(_Match_mode, _StateIdT);
void
_M_dfs(_Match_mode __match_mode, _StateIdT __start);
bool
_M_main(_Match_mode __match_mode)
{ return _M_main_dispatch(__match_mode, __search_mode{}); }
bool
_M_main_dispatch(_Match_mode __match_mode, __dfs);
bool
_M_main_dispatch(_Match_mode __match_mode, __bfs);
bool
_M_is_word(_CharT __ch) const
{
static const _CharT __s[2] = { 'w' };
return _M_re._M_automaton->_M_traits.isctype
(__ch, _M_re._M_automaton->_M_traits.lookup_classname(__s, __s+1));
}
bool
_M_at_begin() const
{
return _M_current == _M_begin
&& !(_M_flags & (regex_constants::match_not_bol
| regex_constants::match_prev_avail));
}
bool
_M_at_end() const
{
return _M_current == _M_end
&& !(_M_flags & regex_constants::match_not_eol);
}
bool
_M_word_boundary() const;
bool
_M_lookahead(_StateIdT __next);
// Holds additional information used in BFS-mode.
template<typename _SearchMode, typename _ResultsVec>
struct _State_info;
template<typename _ResultsVec>
struct _State_info<__bfs, _ResultsVec>
{
explicit
_State_info(_StateIdT __start, size_t __n)
: _M_visited_states(new bool[__n]()), _M_start(__start)
{ }
bool _M_visited(_StateIdT __i)
{
if (_M_visited_states[__i])
return true;
_M_visited_states[__i] = true;
return false;
}
void _M_queue(_StateIdT __i, const _ResultsVec& __res)
{ _M_match_queue.emplace_back(__i, __res); }
// Dummy implementations for BFS mode.
_BiIter* _M_get_sol_pos() { return nullptr; }
// Saves states that need to be considered for the next character.
vector<pair<_StateIdT, _ResultsVec>> _M_match_queue;
// Indicates which states are already visited.
unique_ptr<bool[]> _M_visited_states;
// To record current solution.
_StateIdT _M_start;
};
template<typename _ResultsVec>
struct _State_info<__dfs, _ResultsVec>
{
explicit
_State_info(_StateIdT __start, size_t) : _M_start(__start)
{ }
// Dummy implementations for DFS mode.
bool _M_visited(_StateIdT) const { return false; }
void _M_queue(_StateIdT, const _ResultsVec&) { }
_BiIter* _M_get_sol_pos() { return &_M_sol_pos; }
// To record current solution.
_StateIdT _M_start;
_BiIter _M_sol_pos;
};
public:
_ResultsVec _M_cur_results;
_BiIter _M_current;
_BiIter _M_begin;
const _BiIter _M_end;
const _RegexT& _M_re;
const _NFAT& _M_nfa;
_ResultsVec& _M_results;
vector<pair<_BiIter, int>> _M_rep_count;
_State_info<__search_mode, _ResultsVec> _M_states;
_FlagT _M_flags;
// Do we have a solution so far?
bool _M_has_sol;
};
//@} regex-detail
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
} // namespace std
#include <bits/regex_executor.tcc>
|