1// class template regex -*- C++ -*-
2
3// Copyright (C) 2013-2018 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
31namespace std _GLIBCXX_VISIBILITY(default)
32{
33_GLIBCXX_BEGIN_NAMESPACE_VERSION
34
35namespace __detail
36{
37#ifdef _GLIBCXX_DEBUG
38 inline std::ostream&
39 _State_base::_M_print(std::ostream& ostr) const
40 {
41 switch (_M_opcode)
42 {
43 case _S_opcode_alternative:
44 case _S_opcode_repeat:
45 ostr << "alt next=" << _M_next << " alt=" << _M_alt;
46 break;
47 case _S_opcode_subexpr_begin:
48 ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr;
49 break;
50 case _S_opcode_subexpr_end:
51 ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr;
52 break;
53 case _S_opcode_backref:
54 ostr << "backref next=" << _M_next << " index=" << _M_backref_index;
55 break;
56 case _S_opcode_match:
57 ostr << "match next=" << _M_next;
58 break;
59 case _S_opcode_accept:
60 ostr << "accept next=" << _M_next;
61 break;
62 default:
63 ostr << "unknown next=" << _M_next;
64 break;
65 }
66 return ostr;
67 }
68
69 // Prints graphviz dot commands for state.
70 inline std::ostream&
71 _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const
72 {
73 switch (_M_opcode)
74 {
75 case _S_opcode_alternative:
76 case _S_opcode_repeat:
77 __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n"
78 << __id << " -> " << _M_next
79 << " [label=\"next\", tailport=\"s\"];\n"
80 << __id << " -> " << _M_alt
81 << " [label=\"alt\", tailport=\"n\"];\n";
82 break;
83 case _S_opcode_backref:
84 __ostr << __id << " [label=\"" << __id << "\\nBACKREF "
85 << _M_subexpr << "\"];\n"
86 << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
87 break;
88 case _S_opcode_line_begin_assertion:
89 __ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n"
90 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
91 break;
92 case _S_opcode_line_end_assertion:
93 __ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n"
94 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
95 break;
96 case _S_opcode_word_boundary:
97 __ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY "
98 << _M_neg << "\"];\n"
99 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
100 break;
101 case _S_opcode_subexpr_lookahead:
102 __ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n"
103 << __id << " -> " << _M_next
104 << " [label=\"epsilon\", tailport=\"s\"];\n"
105 << __id << " -> " << _M_alt
106 << " [label=\"<assert>\", tailport=\"n\"];\n";
107 break;
108 case _S_opcode_subexpr_begin:
109 __ostr << __id << " [label=\"" << __id << "\\nSBEGIN "
110 << _M_subexpr << "\"];\n"
111 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
112 break;
113 case _S_opcode_subexpr_end:
114 __ostr << __id << " [label=\"" << __id << "\\nSEND "
115 << _M_subexpr << "\"];\n"
116 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n";
117 break;
118 case _S_opcode_dummy:
119 break;
120 case _S_opcode_match:
121 __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n"
122 << __id << " -> " << _M_next << " [label=\"<match>\"];\n";
123 break;
124 case _S_opcode_accept:
125 __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ;
126 break;
127 default:
128 _GLIBCXX_DEBUG_ASSERT(false);
129 break;
130 }
131 return __ostr;
132 }
133
134 template<typename _TraitsT>
135 std::ostream&
136 _NFA<_TraitsT>::_M_dot(std::ostream& __ostr) const
137 {
138 __ostr << "digraph _Nfa {\n"
139 " rankdir=LR;\n";
140 for (size_t __i = 0; __i < this->size(); ++__i)
141 (*this)[__i]._M_dot(__ostr, __i);
142 __ostr << "}\n";
143 return __ostr;
144 }
145#endif
146
147 template<typename _TraitsT>
148 _StateIdT
149 _NFA<_TraitsT>::_M_insert_backref(size_t __index)
150 {
151 if (this->_M_flags & regex_constants::__polynomial)
152 __throw_regex_error(regex_constants::error_complexity,
153 "Unexpected back-reference in polynomial mode.");
154 // To figure out whether a backref is valid, a stack is used to store
155 // unfinished sub-expressions. For example, when parsing
156 // "(a(b)(c\\1(d)))" at '\\1', _M_subexpr_count is 3, indicating that 3
157 // sub expressions are parsed or partially parsed(in the stack), aka,
158 // "(a..", "(b)" and "(c..").
159 // _M_paren_stack is {1, 3}, for incomplete "(a.." and "(c..". At this
160 // time, "\\2" is valid, but "\\1" and "\\3" are not.
161 if (__index >= _M_subexpr_count)
162 __throw_regex_error(
163 regex_constants::error_backref,
164 "Back-reference index exceeds current sub-expression count.");
165 for (auto __it : this->_M_paren_stack)
166 if (__index == __it)
167 __throw_regex_error(
168 regex_constants::error_backref,
169 "Back-reference referred to an opened sub-expression.");
170 this->_M_has_backref = true;
171 _StateT __tmp(_S_opcode_backref);
172 __tmp._M_backref_index = __index;
173 return _M_insert_state(std::move(__tmp));
174 }
175
176 template<typename _TraitsT>
177 void
178 _NFA<_TraitsT>::_M_eliminate_dummy()
179 {
180 for (auto& __it : *this)
181 {
182 while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode()
183 == _S_opcode_dummy)
184 __it._M_next = (*this)[__it._M_next]._M_next;
185 if (__it._M_has_alt())
186 while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode()
187 == _S_opcode_dummy)
188 __it._M_alt = (*this)[__it._M_alt]._M_next;
189 }
190 }
191
192 // Just apply DFS on the sequence and re-link their links.
193 template<typename _TraitsT>
194 _StateSeq<_TraitsT>
195 _StateSeq<_TraitsT>::_M_clone()
196 {
197 std::map<_StateIdT, _StateIdT> __m;
198 std::stack<_StateIdT> __stack;
199 __stack.push(_M_start);
200 while (!__stack.empty())
201 {
202 auto __u = __stack.top();
203 __stack.pop();
204 auto __dup = _M_nfa[__u];
205 // _M_insert_state() never return -1
206 auto __id = _M_nfa._M_insert_state(std::move(__dup));
207 __m[__u] = __id;
208 if (__dup._M_has_alt())
209 if (__dup._M_alt != _S_invalid_state_id
210 && __m.count(__dup._M_alt) == 0)
211 __stack.push(__dup._M_alt);
212 if (__u == _M_end)
213 continue;
214 if (__dup._M_next != _S_invalid_state_id
215 && __m.count(__dup._M_next) == 0)
216 __stack.push(__dup._M_next);
217 }
218 for (auto __it : __m)
219 {
220 auto __v = __it.second;
221 auto& __ref = _M_nfa[__v];
222 if (__ref._M_next != _S_invalid_state_id)
223 {
224 __glibcxx_assert(__m.count(__ref._M_next) > 0);
225 __ref._M_next = __m[__ref._M_next];
226 }
227 if (__ref._M_has_alt())
228 if (__ref._M_alt != _S_invalid_state_id)
229 {
230 __glibcxx_assert(__m.count(__ref._M_alt) > 0);
231 __ref._M_alt = __m[__ref._M_alt];
232 }
233 }
234 return _StateSeq(_M_nfa, __m[_M_start], __m[_M_end]);
235 }
236} // namespace __detail
237
238_GLIBCXX_END_NAMESPACE_VERSION
239} // namespace
240