]>
Commit | Line | Data |
---|---|---|
6cb784b6 TS |
1 | // class template regex -*- C++ -*- |
2 | ||
cbe34bb5 | 3 | // Copyright (C) 2013-2017 Free Software Foundation, Inc. |
6cb784b6 TS |
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 | { | |
6cb784b6 TS |
33 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
34 | ||
4a15d842 FD |
35 | namespace __detail |
36 | { | |
6cb784b6 | 37 | #ifdef _GLIBCXX_DEBUG |
ecb249dd | 38 | inline std::ostream& |
7d9d2185 JW |
39 | _State_base::_M_print(std::ostream& ostr) const |
40 | { | |
41 | switch (_M_opcode) | |
6cb784b6 | 42 | { |
7d9d2185 | 43 | case _S_opcode_alternative: |
a670a9bb | 44 | case _S_opcode_repeat: |
7d9d2185 JW |
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; | |
6cb784b6 | 65 | } |
7d9d2185 JW |
66 | return ostr; |
67 | } | |
6cb784b6 TS |
68 | |
69 | // Prints graphviz dot commands for state. | |
ecb249dd | 70 | inline std::ostream& |
7d9d2185 JW |
71 | _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const |
72 | { | |
73 | switch (_M_opcode) | |
6cb784b6 | 74 | { |
7d9d2185 | 75 | case _S_opcode_alternative: |
a670a9bb | 76 | case _S_opcode_repeat: |
7d9d2185 JW |
77 | __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n" |
78 | << __id << " -> " << _M_next | |
a670a9bb | 79 | << " [label=\"next\", tailport=\"s\"];\n" |
7d9d2185 | 80 | << __id << " -> " << _M_alt |
a670a9bb | 81 | << " [label=\"alt\", tailport=\"n\"];\n"; |
7d9d2185 JW |
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; | |
6cb784b6 | 130 | } |
7d9d2185 JW |
131 | return __ostr; |
132 | } | |
6cb784b6 | 133 | |
68e69ce2 | 134 | template<typename _TraitsT> |
7d9d2185 | 135 | std::ostream& |
68e69ce2 | 136 | _NFA<_TraitsT>::_M_dot(std::ostream& __ostr) const |
6cb784b6 TS |
137 | { |
138 | __ostr << "digraph _Nfa {\n" | |
ddf41e9d | 139 | " rankdir=LR;\n"; |
6cb43087 | 140 | for (size_t __i = 0; __i < this->size(); ++__i) |
ddf41e9d | 141 | (*this)[__i]._M_dot(__ostr, __i); |
6cb784b6 TS |
142 | __ostr << "}\n"; |
143 | return __ostr; | |
144 | } | |
145 | #endif | |
146 | ||
68e69ce2 | 147 | template<typename _TraitsT> |
7d9d2185 | 148 | _StateIdT |
68e69ce2 | 149 | _NFA<_TraitsT>::_M_insert_backref(size_t __index) |
ce645eb0 | 150 | { |
e4846be7 | 151 | if (this->_M_flags & regex_constants::__polynomial) |
236d76c4 TS |
152 | __throw_regex_error(regex_constants::error_complexity, |
153 | "Unexpected back-reference in polynomial mode."); | |
ce645eb0 TS |
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) | |
236d76c4 TS |
162 | __throw_regex_error( |
163 | regex_constants::error_backref, | |
164 | "Back-reference index exceeds current sub-expression count."); | |
7d9d2185 | 165 | for (auto __it : this->_M_paren_stack) |
e280b6ff | 166 | if (__index == __it) |
236d76c4 TS |
167 | __throw_regex_error( |
168 | regex_constants::error_backref, | |
169 | "Back-reference referred to an opened sub-expression."); | |
7d9d2185 | 170 | this->_M_has_backref = true; |
7b86458e TS |
171 | _StateT __tmp(_S_opcode_backref); |
172 | __tmp._M_backref_index = __index; | |
7d9d2185 | 173 | return _M_insert_state(std::move(__tmp)); |
ce645eb0 TS |
174 | } |
175 | ||
68e69ce2 | 176 | template<typename _TraitsT> |
7d9d2185 | 177 | void |
68e69ce2 | 178 | _NFA<_TraitsT>::_M_eliminate_dummy() |
6cb784b6 | 179 | { |
7c812a2a TS |
180 | for (auto& __it : *this) |
181 | { | |
81b7ff07 | 182 | while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode() |
7b86458e | 183 | == _S_opcode_dummy) |
7c812a2a | 184 | __it._M_next = (*this)[__it._M_next]._M_next; |
81b7ff07 TS |
185 | if (__it._M_has_alt()) |
186 | while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode() | |
7c812a2a TS |
187 | == _S_opcode_dummy) |
188 | __it._M_alt = (*this)[__it._M_alt]._M_next; | |
189 | } | |
6cb784b6 TS |
190 | } |
191 | ||
7c812a2a | 192 | // Just apply DFS on the sequence and re-link their links. |
68e69ce2 JW |
193 | template<typename _TraitsT> |
194 | _StateSeq<_TraitsT> | |
195 | _StateSeq<_TraitsT>::_M_clone() | |
6cb784b6 | 196 | { |
5bcb66df | 197 | std::map<_StateIdT, _StateIdT> __m; |
7c812a2a TS |
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]; | |
ddf41e9d | 205 | // _M_insert_state() never return -1 |
81b7ff07 | 206 | auto __id = _M_nfa._M_insert_state(std::move(__dup)); |
7c812a2a | 207 | __m[__u] = __id; |
81b7ff07 | 208 | if (__dup._M_has_alt()) |
5bcb66df TS |
209 | if (__dup._M_alt != _S_invalid_state_id |
210 | && __m.count(__dup._M_alt) == 0) | |
7c812a2a | 211 | __stack.push(__dup._M_alt); |
836c42f6 TS |
212 | if (__u == _M_end) |
213 | continue; | |
5bcb66df TS |
214 | if (__dup._M_next != _S_invalid_state_id |
215 | && __m.count(__dup._M_next) == 0) | |
836c42f6 | 216 | __stack.push(__dup._M_next); |
7c812a2a | 217 | } |
5bcb66df | 218 | for (auto __it : __m) |
7c812a2a | 219 | { |
5bcb66df | 220 | auto __v = __it.second; |
ddf41e9d TS |
221 | auto& __ref = _M_nfa[__v]; |
222 | if (__ref._M_next != _S_invalid_state_id) | |
7c812a2a | 223 | { |
2f1e8e7c | 224 | __glibcxx_assert(__m.count(__ref._M_next) > 0); |
7c812a2a TS |
225 | __ref._M_next = __m[__ref._M_next]; |
226 | } | |
81b7ff07 | 227 | if (__ref._M_has_alt()) |
ddf41e9d | 228 | if (__ref._M_alt != _S_invalid_state_id) |
7c812a2a | 229 | { |
2f1e8e7c | 230 | __glibcxx_assert(__m.count(__ref._M_alt) > 0); |
7c812a2a TS |
231 | __ref._M_alt = __m[__ref._M_alt]; |
232 | } | |
233 | } | |
234 | return _StateSeq(_M_nfa, __m[_M_start], __m[_M_end]); | |
6cb784b6 | 235 | } |
4a15d842 | 236 | } // namespace __detail |
6cb784b6 | 237 | |
6cb784b6 | 238 | _GLIBCXX_END_NAMESPACE_VERSION |
6cb784b6 | 239 | } // namespace |