libstdc++
regex_automaton.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_automaton.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 #ifdef _GLIBCXX_DEBUG
39  _State_base::_M_print(std::ostream& ostr) const
40  {
41  switch (_M_opcode)
42  {
43  case _S_opcode_alternative:
44  ostr << "alt next=" << _M_next << " alt=" << _M_alt;
45  break;
46  case _S_opcode_subexpr_begin:
47  ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr;
48  break;
49  case _S_opcode_subexpr_end:
50  ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr;
51  break;
52  case _S_opcode_backref:
53  ostr << "backref next=" << _M_next << " index=" << _M_backref_index;
54  break;
55  case _S_opcode_match:
56  ostr << "match next=" << _M_next;
57  break;
58  case _S_opcode_accept:
59  ostr << "accept next=" << _M_next;
60  break;
61  default:
62  ostr << "unknown next=" << _M_next;
63  break;
64  }
65  return ostr;
66  }
67 
68  // Prints graphviz dot commands for state.
70  _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const
71  {
72  switch (_M_opcode)
73  {
74  case _S_opcode_alternative:
75  __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n"
76  << __id << " -> " << _M_next
77  << " [label=\"epsilon\", tailport=\"s\"];\n"
78  << __id << " -> " << _M_alt
79  << " [label=\"epsilon\", tailport=\"n\"];\n";
80  break;
81  case _S_opcode_backref:
82  __ostr << __id << " [label=\"" << __id << "\\nBACKREF "
83  << _M_subexpr << "\"];\n"
84  << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
85  break;
86  case _S_opcode_line_begin_assertion:
87  __ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n"
88  << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
89  break;
90  case _S_opcode_line_end_assertion:
91  __ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n"
92  << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
93  break;
94  case _S_opcode_word_boundary:
95  __ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY "
96  << _M_neg << "\"];\n"
97  << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
98  break;
99  case _S_opcode_subexpr_lookahead:
100  __ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n"
101  << __id << " -> " << _M_next
102  << " [label=\"epsilon\", tailport=\"s\"];\n"
103  << __id << " -> " << _M_alt
104  << " [label=\"<assert>\", tailport=\"n\"];\n";
105  break;
106  case _S_opcode_subexpr_begin:
107  __ostr << __id << " [label=\"" << __id << "\\nSBEGIN "
108  << _M_subexpr << "\"];\n"
109  << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
110  break;
111  case _S_opcode_subexpr_end:
112  __ostr << __id << " [label=\"" << __id << "\\nSEND "
113  << _M_subexpr << "\"];\n"
114  << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
115  break;
116  case _S_opcode_dummy:
117  break;
118  case _S_opcode_match:
119  __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n"
120  << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
121  break;
122  case _S_opcode_accept:
123  __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ;
124  break;
125  default:
126  _GLIBCXX_DEBUG_ASSERT(false);
127  break;
128  }
129  return __ostr;
130  }
131 
132  template<typename _TraitsT>
133  std::ostream&
134  _NFA<_TraitsT>::_M_dot(std::ostream& __ostr) const
135  {
136  __ostr << "digraph _Nfa {\n"
137  " rankdir=LR;\n";
138  for (size_t __i = 0; __i < this->size(); ++__i)
139  (*this)[__i]._M_dot(__ostr, __i);
140  __ostr << "}\n";
141  return __ostr;
142  }
143 #endif
144 
145  template<typename _TraitsT>
146  _StateIdT
147  _NFA<_TraitsT>::_M_insert_backref(size_t __index)
148  {
149  // To figure out whether a backref is valid, a stack is used to store
150  // unfinished sub-expressions. For example, when parsing
151  // "(a(b)(c\\1(d)))" at '\\1', _M_subexpr_count is 3, indicating that 3
152  // sub expressions are parsed or partially parsed(in the stack), aka,
153  // "(a..", "(b)" and "(c..").
154  // _M_paren_stack is {1, 3}, for incomplete "(a.." and "(c..". At this
155  // time, "\\2" is valid, but "\\1" and "\\3" are not.
156  if (__index >= _M_subexpr_count)
157  __throw_regex_error(regex_constants::error_backref);
158  for (auto __it : this->_M_paren_stack)
159  if (__index == __it)
160  __throw_regex_error(regex_constants::error_backref);
161  this->_M_has_backref = true;
162  _StateT __tmp(_S_opcode_backref);
163  __tmp._M_backref_index = __index;
164  return _M_insert_state(std::move(__tmp));
165  }
166 
167  template<typename _TraitsT>
168  void
169  _NFA<_TraitsT>::_M_eliminate_dummy()
170  {
171  for (auto& __it : *this)
172  {
173  while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode
174  == _S_opcode_dummy)
175  __it._M_next = (*this)[__it._M_next]._M_next;
176  if (__it._M_opcode == _S_opcode_alternative
177  || __it._M_opcode == _S_opcode_subexpr_lookahead)
178  while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode
179  == _S_opcode_dummy)
180  __it._M_alt = (*this)[__it._M_alt]._M_next;
181  }
182  }
183 
184  // Just apply DFS on the sequence and re-link their links.
185  template<typename _TraitsT>
186  _StateSeq<_TraitsT>
187  _StateSeq<_TraitsT>::_M_clone()
188  {
190  std::stack<_StateIdT> __stack;
191  __stack.push(_M_start);
192  while (!__stack.empty())
193  {
194  auto __u = __stack.top();
195  __stack.pop();
196  auto __dup = _M_nfa[__u];
197  auto __id = _M_nfa._M_insert_state(__dup);
198  __m[__u] = __id;
199  if (__u == _M_end)
200  continue;
201  if (__m.count(__dup._M_next) == 0)
202  __stack.push(__dup._M_next);
203  if (__dup._M_opcode == _S_opcode_alternative
204  || __dup._M_opcode == _S_opcode_subexpr_lookahead)
205  if (__m.count(__dup._M_alt) == 0)
206  __stack.push(__dup._M_alt);
207  }
208  for (auto __it : __m)
209  {
210  auto& __ref = _M_nfa[__it.second];
211  if (__ref._M_next != -1)
212  {
213  _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_next));
214  __ref._M_next = __m[__ref._M_next];
215  }
216  if (__ref._M_opcode == _S_opcode_alternative
217  || __ref._M_opcode == _S_opcode_subexpr_lookahead)
218  if (__ref._M_alt != -1)
219  {
220  _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_alt));
221  __ref._M_alt = __m[__ref._M_alt];
222  }
223  }
224  return _StateSeq(_M_nfa, __m[_M_start], __m[_M_end]);
225  }
226 
227 _GLIBCXX_END_NAMESPACE_VERSION
228 } // namespace __detail
229 } // namespace
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition: bitset:1293
size_type count(const key_type &__x) const
Finds the number of elements with given key.
Definition: stl_map.h:885
reference top()
Definition: stl_stack.h:159
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:96
void pop()
Removes first element.
Definition: stl_stack.h:212
constexpr error_type error_backref(_S_error_backref)
void push(const value_type &__x)
Add data to the top of the stack.
Definition: stl_stack.h:186
A standard container giving FILO behavior.
Definition: stl_stack.h:96