libstdc++
regex_executor.tcc
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2013-2014 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.tcc
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 namespace std _GLIBCXX_VISIBILITY(default)
32 {
33 namespace __detail
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 
37  template<typename _BiIter, typename _Alloc, typename _TraitsT,
38  bool __dfs_mode>
39  bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
40  _M_search()
41  {
42  if (_M_flags & regex_constants::match_continuous)
43  return _M_search_from_first();
44  auto __cur = _M_begin;
45  do
46  {
47  _M_current = __cur;
48  if (_M_main<false>())
49  return true;
50  }
51  // Continue when __cur == _M_end
52  while (__cur++ != _M_end);
53  return false;
54  }
55 
56  // This function operates in different modes, DFS mode or BFS mode, indicated
57  // by template parameter __dfs_mode. See _M_main for details.
58  //
59  // ------------------------------------------------------------
60  //
61  // DFS mode:
62  //
63  // It applies a Depth-First-Search (aka backtracking) on given NFA and input
64  // string.
65  // At the very beginning the executor stands in the start state, then it tries
66  // every possible state transition in current state recursively. Some state
67  // transitions consume input string, say, a single-char-matcher or a
68  // back-reference matcher; some don't, like assertion or other anchor nodes.
69  // When the input is exhausted and/or the current state is an accepting state,
70  // the whole executor returns true.
71  //
72  // TODO: This approach is exponentially slow for certain input.
73  // Try to compile the NFA to a DFA.
74  //
75  // Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
76  // Space complexity: \theta(match_results.size() + match_length)
77  //
78  // ------------------------------------------------------------
79  //
80  // BFS mode:
81  //
82  // Russ Cox's article (http://swtch.com/~rsc/regexp/regexp1.html)
83  // explained this algorithm clearly.
84  //
85  // It first computes epsilon closure (states that can be achieved without
86  // consuming characters) for every state that's still matching,
87  // using the same DFS algorithm, but doesn't re-enter states (find a true in
88  // _M_visited), nor follows _S_opcode_match.
89  //
90  // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
91  // state.
92  //
93  // It significantly reduces potential duplicate states, so has a better
94  // upper bound; but it requires more overhead.
95  //
96  // Time complexity: \Omega(match_length * match_results.size())
97  // O(match_length * _M_nfa.size() * match_results.size())
98  // Space complexity: \Omega(_M_nfa.size() + match_results.size())
99  // O(_M_nfa.size() * match_results.size())
100  template<typename _BiIter, typename _Alloc, typename _TraitsT,
101  bool __dfs_mode>
102  template<bool __match_mode>
103  bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
104  _M_main()
105  {
106  if (__dfs_mode)
107  {
108  _M_has_sol = false;
109  _M_cur_results = _M_results;
110  _M_dfs<__match_mode>(_M_start_state);
111  return _M_has_sol;
112  }
113  else
114  {
115  _M_match_queue->push_back(make_pair(_M_start_state, _M_results));
116  bool __ret = false;
117  while (1)
118  {
119  _M_has_sol = false;
120  if (_M_match_queue->empty())
121  break;
122  _M_visited->assign(_M_visited->size(), false);
123  auto __old_queue = std::move(*_M_match_queue);
124  for (auto& __task : __old_queue)
125  {
126  _M_cur_results = std::move(__task.second);
127  _M_dfs<__match_mode>(__task.first);
128  }
129  if (!__match_mode)
130  __ret |= _M_has_sol;
131  if (_M_current == _M_end)
132  break;
133  ++_M_current;
134  }
135  if (__match_mode)
136  __ret = _M_has_sol;
137  return __ret;
138  }
139  }
140 
141  // Return whether now match the given sub-NFA.
142  template<typename _BiIter, typename _Alloc, typename _TraitsT,
143  bool __dfs_mode>
144  bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
145  _M_lookahead(_State<_TraitsT> __state)
146  {
147  // Backreferences may refer to captured content.
148  // We may want to make this faster by not copying,
149  // but let's not be clever prematurely.
150  _ResultsVec __what(_M_cur_results);
151  auto __sub = std::unique_ptr<_Executor>(new _Executor(_M_current,
152  _M_end,
153  __what,
154  _M_re,
155  _M_flags));
156  __sub->_M_start_state = __state._M_alt;
157  if (__sub->_M_search_from_first())
158  {
159  for (size_t __i = 0; __i < __what.size(); __i++)
160  if (__what[__i].matched)
161  _M_cur_results[__i] = __what[__i];
162  return true;
163  }
164  return false;
165  }
166 
167  // TODO: Use a function vector to dispatch, instead of using switch-case.
168  template<typename _BiIter, typename _Alloc, typename _TraitsT,
169  bool __dfs_mode>
170  template<bool __match_mode>
171  void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
172  _M_dfs(_StateIdT __i)
173  {
174  if (!__dfs_mode)
175  {
176  if ((*_M_visited)[__i])
177  return;
178  (*_M_visited)[__i] = true;
179  }
180 
181  const auto& __state = _M_nfa[__i];
182  // Every change on _M_cur_results and _M_current will be rolled back after
183  // finishing the recursion step.
184  switch (__state._M_opcode)
185  {
186  // _M_alt branch is "match once more", while _M_next is "get me out
187  // of this quantifier". Executing _M_next first or _M_alt first don't
188  // mean the same thing, and we need to choose the correct order under
189  // given greedy mode.
190  case _S_opcode_alternative:
191  // Greedy.
192  if (!__state._M_neg)
193  {
194  // "Once more" is preferred in greedy mode.
195  _M_dfs<__match_mode>(__state._M_alt);
196  // If it's DFS executor and already accepted, we're done.
197  if (!__dfs_mode || !_M_has_sol)
198  _M_dfs<__match_mode>(__state._M_next);
199  }
200  else // Non-greedy mode
201  {
202  if (__dfs_mode)
203  {
204  // vice-versa.
205  _M_dfs<__match_mode>(__state._M_next);
206  if (!_M_has_sol)
207  _M_dfs<__match_mode>(__state._M_alt);
208  }
209  else
210  {
211  // DON'T attempt anything, because there's already another
212  // state with higher priority accepted. This state cannot be
213  // better by attempting its next node.
214  if (!_M_has_sol)
215  {
216  _M_dfs<__match_mode>(__state._M_next);
217  // DON'T attempt anything if it's already accepted. An
218  // accepted state *must* be better than a solution that
219  // matches a non-greedy quantifier one more time.
220  if (!_M_has_sol)
221  _M_dfs<__match_mode>(__state._M_alt);
222  }
223  }
224  }
225  break;
226  case _S_opcode_subexpr_begin:
227  // If there's nothing changed since last visit, do NOT continue.
228  // This prevents the executor from get into infinite loop when using
229  // "()*" to match "".
230  if (!_M_cur_results[__state._M_subexpr].matched
231  || _M_cur_results[__state._M_subexpr].first != _M_current)
232  {
233  auto& __res = _M_cur_results[__state._M_subexpr];
234  auto __back = __res.first;
235  __res.first = _M_current;
236  _M_dfs<__match_mode>(__state._M_next);
237  __res.first = __back;
238  }
239  break;
240  case _S_opcode_subexpr_end:
241  if (_M_cur_results[__state._M_subexpr].second != _M_current
242  || _M_cur_results[__state._M_subexpr].matched != true)
243  {
244  auto& __res = _M_cur_results[__state._M_subexpr];
245  auto __back = __res;
246  __res.second = _M_current;
247  __res.matched = true;
248  _M_dfs<__match_mode>(__state._M_next);
249  __res = __back;
250  }
251  else
252  _M_dfs<__match_mode>(__state._M_next);
253  break;
254  case _S_opcode_line_begin_assertion:
255  if (_M_at_begin())
256  _M_dfs<__match_mode>(__state._M_next);
257  break;
258  case _S_opcode_line_end_assertion:
259  if (_M_at_end())
260  _M_dfs<__match_mode>(__state._M_next);
261  break;
262  case _S_opcode_word_boundary:
263  if (_M_word_boundary(__state) == !__state._M_neg)
264  _M_dfs<__match_mode>(__state._M_next);
265  break;
266  // Here __state._M_alt offers a single start node for a sub-NFA.
267  // We recursively invoke our algorithm to match the sub-NFA.
268  case _S_opcode_subexpr_lookahead:
269  if (_M_lookahead(__state) == !__state._M_neg)
270  _M_dfs<__match_mode>(__state._M_next);
271  break;
272  case _S_opcode_match:
273  if (_M_current == _M_end)
274  break;
275  if (__dfs_mode)
276  {
277  if (__state._M_matches(*_M_current))
278  {
279  ++_M_current;
280  _M_dfs<__match_mode>(__state._M_next);
281  --_M_current;
282  }
283  }
284  else
285  if (__state._M_matches(*_M_current))
286  _M_match_queue->push_back(make_pair(__state._M_next,
287  _M_cur_results));
288  break;
289  // First fetch the matched result from _M_cur_results as __submatch;
290  // then compare it with
291  // (_M_current, _M_current + (__submatch.second - __submatch.first)).
292  // If matched, keep going; else just return and try another state.
293  case _S_opcode_backref:
294  {
295  _GLIBCXX_DEBUG_ASSERT(__dfs_mode);
296  auto& __submatch = _M_cur_results[__state._M_backref_index];
297  if (!__submatch.matched)
298  break;
299  auto __last = _M_current;
300  for (auto __tmp = __submatch.first;
301  __last != _M_end && __tmp != __submatch.second;
302  ++__tmp)
303  ++__last;
304  if (_M_re._M_traits.transform(__submatch.first,
305  __submatch.second)
306  == _M_re._M_traits.transform(_M_current, __last))
307  {
308  if (__last != _M_current)
309  {
310  auto __backup = _M_current;
311  _M_current = __last;
312  _M_dfs<__match_mode>(__state._M_next);
313  _M_current = __backup;
314  }
315  else
316  _M_dfs<__match_mode>(__state._M_next);
317  }
318  }
319  break;
320  case _S_opcode_accept:
321  if (__dfs_mode)
322  {
323  _GLIBCXX_DEBUG_ASSERT(!_M_has_sol);
324  if (__match_mode)
325  _M_has_sol = _M_current == _M_end;
326  else
327  _M_has_sol = true;
328  if (_M_current == _M_begin
329  && (_M_flags & regex_constants::match_not_null))
330  _M_has_sol = false;
331  if (_M_has_sol)
332  _M_results = _M_cur_results;
333  }
334  else
335  {
336  if (_M_current == _M_begin
337  && (_M_flags & regex_constants::match_not_null))
338  break;
339  if (!__match_mode || _M_current == _M_end)
340  if (!_M_has_sol)
341  {
342  _M_has_sol = true;
343  _M_results = _M_cur_results;
344  }
345  }
346  break;
347  default:
348  _GLIBCXX_DEBUG_ASSERT(false);
349  }
350  }
351 
352  // Return whether now is at some word boundary.
353  template<typename _BiIter, typename _Alloc, typename _TraitsT,
354  bool __dfs_mode>
355  bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
356  _M_word_boundary(_State<_TraitsT> __state) const
357  {
358  bool __left_is_word = false;
359  if (_M_current != _M_begin
360  || (_M_flags & regex_constants::match_prev_avail))
361  {
362  auto __prev = _M_current;
363  if (_M_is_word(*std::prev(__prev)))
364  __left_is_word = true;
365  }
366  bool __right_is_word =
367  _M_current != _M_end && _M_is_word(*_M_current);
368 
369  if (__left_is_word == __right_is_word)
370  return false;
371  if (__left_is_word && !(_M_flags & regex_constants::match_not_eow))
372  return true;
373  if (__right_is_word && !(_M_flags & regex_constants::match_not_bow))
374  return true;
375  return false;
376  }
377 
378 _GLIBCXX_END_NAMESPACE_VERSION
379 } // namespace __detail
380 } // namespace
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276
20.7.1.2 unique_ptr for single objects.
Definition: unique_ptr.h:129