libstdc++
regex_grep_matcher.tcc
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2010 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_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}
29  */
30 
31 #include <regex>
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 namespace
36 {
37  // A stack of states used in evaluating the NFA.
38  typedef std::stack<std::__regex::_StateIdT,
40  > _StateStack;
41 
42  // Obtains the next state set given the current state set __s and the current
43  // input character.
45  __move(const std::__regex::_PatternCursor& __p,
46  const std::__regex::_Nfa& __nfa,
47  const std::__regex::_StateSet& __s)
48  {
51  __i != __s.end(); ++__i)
52  {
53  if (*__i == std::__regex::_S_invalid_state_id)
54  continue;
55 
56  const std::__regex::_State& __state = __nfa[*__i];
57  if (__state._M_opcode == std::__regex::_S_opcode_match
58  && __state._M_matches(__p))
59  __m.insert(__state._M_next);
60  }
61  return __m;
62  }
63 
64  // returns true if (__s intersect __t) is not empty
65  inline bool
66  __includes_some(const std::__regex::_StateSet& __s,
67  const std::__regex::_StateSet& __t)
68  {
69  if (__s.size() > 0 && __t.size() > 0)
70  {
73  while (__first != __s.end() && __second != __t.end())
74  {
75  if (*__first < *__second)
76  ++__first;
77  else if (*__second < *__first)
78  ++__second;
79  else
80  return true;
81  }
82  }
83  return false;
84  }
85 
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.
88  inline void
89  __add_visited_state(const std::__regex::_StateIdT __u,
90  _StateStack& __s,
92  {
93  if (__e.count(__u) == 0)
94  {
95  __e.insert(__u);
96  __s.push(__u);
97  }
98  }
99 
100 } // anonymous namespace
101 
102 namespace __regex
103 {
104 _GLIBCXX_BEGIN_NAMESPACE_VERSION
105 
106  inline _Grep_matcher::
107  _Grep_matcher(_PatternCursor& __p, _Results& __r,
108  const _AutomatonPtr& __nfa,
110  : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r)
111  {
112  __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
113  for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
114  __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
115 
116  _M_results._M_set_matched(0,
117  __includes_some(_M_nfa->_M_final_states(), __t));
118  }
119 
120  // Creates the e-closure set for the initial state __i.
121  inline _StateSet _Grep_matcher::
122  _M_e_closure(_StateIdT __i)
123  {
124  _StateSet __s;
125  __s.insert(__i);
126  _StateStack __stack;
127  __stack.push(__i);
128  return this->_M_e_closure(__stack, __s);
129  }
130 
131  // Creates the e-closure set for an arbitrary state set __s.
132  inline _StateSet _Grep_matcher::
133  _M_e_closure(const _StateSet& __s)
134  {
135  _StateStack __stack;
136  for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i)
137  __stack.push(*__i);
138  return this->_M_e_closure(__stack, __s);
139  }
140 
141  inline _StateSet _Grep_matcher::
142  _M_e_closure(_StateStack& __stack, const _StateSet& __s)
143  {
144  _StateSet __e = __s;
145  while (!__stack.empty())
146  {
147  _StateIdT __t = __stack.top(); __stack.pop();
148  if (__t == _S_invalid_state_id)
149  continue;
150  // for each __u with edge from __t to __u labeled e do ...
151  const _State& __state = _M_nfa->operator[](__t);
152  switch (__state._M_opcode)
153  {
154  case _S_opcode_alternative:
155  __add_visited_state(__state._M_next, __stack, __e);
156  __add_visited_state(__state._M_alt, __stack, __e);
157  break;
158  case _S_opcode_subexpr_begin:
159  __add_visited_state(__state._M_next, __stack, __e);
160  __state._M_tagger(_M_pattern, _M_results);
161  break;
162  case _S_opcode_subexpr_end:
163  __add_visited_state(__state._M_next, __stack, __e);
164  __state._M_tagger(_M_pattern, _M_results);
165  _M_results._M_set_matched(__state._M_subexpr, true);
166  break;
167  case _S_opcode_accept:
168  __add_visited_state(__state._M_next, __stack, __e);
169  break;
170  default:
171  break;
172  }
173  }
174  return __e;
175  }
176 
177 _GLIBCXX_END_NAMESPACE_VERSION
178 } // namespace __regex
179 } // namespace
size_type count(const key_type &__x) const
Finds the number of elements.
Definition: stl_set.h:594
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the set.
Definition: stl_set.h:412
A standard container giving FILO behavior.
Definition: stl_stack.h:95
std::bitset< _S_match_flag_last > match_flag_type
This is a bitmask type indicating regex matching rules.
_Rep_type::const_iterator const_iterator
Iterator-related typedefs.
Definition: stl_set.h:129
size_type size() const _GLIBCXX_NOEXCEPT
Returns the size of the set.
Definition: stl_set.h:374
iterator begin() const _GLIBCXX_NOEXCEPT
Definition: stl_set.h:299
iterator end() const _GLIBCXX_NOEXCEPT
Definition: stl_set.h:308
A standard container which offers fixed time access to individual elements in any order...
Definition: stl_vector.h:208