]>
Commit | Line | Data |
---|---|---|
6cb784b6 TS |
1 | // class template regex -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2013 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 | |
7d9d2185 JW |
38 | std::ostream& |
39 | _State_base::_M_print(std::ostream& ostr) const | |
40 | { | |
41 | switch (_M_opcode) | |
6cb784b6 | 42 | { |
7d9d2185 JW |
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; | |
6cb784b6 | 64 | } |
7d9d2185 JW |
65 | return ostr; |
66 | } | |
6cb784b6 TS |
67 | |
68 | // Prints graphviz dot commands for state. | |
7d9d2185 JW |
69 | std::ostream& |
70 | _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const | |
71 | { | |
72 | switch (_M_opcode) | |
6cb784b6 | 73 | { |
7d9d2185 JW |
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; | |
6cb784b6 | 128 | } |
7d9d2185 JW |
129 | return __ostr; |
130 | } | |
6cb784b6 | 131 | |
68e69ce2 | 132 | template<typename _TraitsT> |
7d9d2185 | 133 | std::ostream& |
68e69ce2 | 134 | _NFA<_TraitsT>::_M_dot(std::ostream& __ostr) const |
6cb784b6 TS |
135 | { |
136 | __ostr << "digraph _Nfa {\n" | |
7d9d2185 | 137 | " rankdir=LR;\n"; |
6cb43087 | 138 | for (size_t __i = 0; __i < this->size(); ++__i) |
7d9d2185 | 139 | (*this)[__i]._M_dot(__ostr, __i); |
6cb784b6 TS |
140 | __ostr << "}\n"; |
141 | return __ostr; | |
142 | } | |
143 | #endif | |
144 | ||
68e69ce2 | 145 | template<typename _TraitsT> |
7d9d2185 | 146 | _StateIdT |
68e69ce2 | 147 | _NFA<_TraitsT>::_M_insert_backref(size_t __index) |
ce645eb0 TS |
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) | |
e280b6ff | 157 | __throw_regex_error(regex_constants::error_backref); |
7d9d2185 | 158 | for (auto __it : this->_M_paren_stack) |
e280b6ff TS |
159 | if (__index == __it) |
160 | __throw_regex_error(regex_constants::error_backref); | |
7d9d2185 | 161 | this->_M_has_backref = true; |
7b86458e TS |
162 | _StateT __tmp(_S_opcode_backref); |
163 | __tmp._M_backref_index = __index; | |
7d9d2185 | 164 | return _M_insert_state(std::move(__tmp)); |
ce645eb0 TS |
165 | } |
166 | ||
68e69ce2 | 167 | template<typename _TraitsT> |
7d9d2185 | 168 | void |
68e69ce2 | 169 | _NFA<_TraitsT>::_M_eliminate_dummy() |
6cb784b6 | 170 | { |
7c812a2a TS |
171 | for (auto& __it : *this) |
172 | { | |
173 | while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode | |
7b86458e | 174 | == _S_opcode_dummy) |
7c812a2a | 175 | __it._M_next = (*this)[__it._M_next]._M_next; |
70b50ed7 TS |
176 | if (__it._M_opcode == _S_opcode_alternative |
177 | || __it._M_opcode == _S_opcode_subexpr_lookahead) | |
7c812a2a TS |
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 | } | |
6cb784b6 TS |
182 | } |
183 | ||
7c812a2a | 184 | // Just apply DFS on the sequence and re-link their links. |
68e69ce2 JW |
185 | template<typename _TraitsT> |
186 | _StateSeq<_TraitsT> | |
187 | _StateSeq<_TraitsT>::_M_clone() | |
6cb784b6 | 188 | { |
7c812a2a TS |
189 | std::map<_StateIdT, _StateIdT> __m; |
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); | |
70b50ed7 TS |
203 | if (__dup._M_opcode == _S_opcode_alternative |
204 | || __dup._M_opcode == _S_opcode_subexpr_lookahead) | |
7c812a2a TS |
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 | } | |
70b50ed7 TS |
216 | if (__ref._M_opcode == _S_opcode_alternative |
217 | || __ref._M_opcode == _S_opcode_subexpr_lookahead) | |
7c812a2a TS |
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]); | |
6cb784b6 TS |
225 | } |
226 | ||
6cb784b6 TS |
227 | _GLIBCXX_END_NAMESPACE_VERSION |
228 | } // namespace __detail | |
229 | } // namespace |