ConstructDFA.xs

filter: Statementstmt 94.8% 258 / 272 Branchbran 58.6% 264 / 450 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 72.3% 522 / 722 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Algorithm/ConstructDFA/XS.pm ↑ Summary
1 #include <bitset>
2 #include <map>
3 #include <list>
4 #include <vector>
5 #include <set>
6 #include <cstdint>
7 #include <queue>
8 #include <algorithm>
9 #include <iterator>
10 #include <utility>
11 #include <stack>
12 #include <deque>
13
14 extern "C"
15 {
16 #include "EXTERN.h"
17 #include "perl.h"
18 #include "XSUB.h"
19 }
20
21 using namespace std;
22
23 // TODO: more error handling when Perl API functions fail
24 // TODO: use a vector for lookup tables like `successors`
25 // TODO: exploit that a list rather than a sub can be used
26 // to identify accepting configurations, the call_sv
27 // and the associated array copying is a bottleneck
28
29 typedef UV State;
30 typedef set<State> States;
31 typedef UV Label;
32 typedef size_t StatesId;
33
34 template <class T>
35 class VectorBasedSet {
36 public:
37 std::vector<bool> included;
38 std::vector<T> elements;
39 11763 bool empty() { return elements.empty(); };
40 38764 bool contains(const T& s) {
41 38764 ▶ return s < included.size() && included[s];
Branch: 3 branches
BranchTrueFalseTotal
return s < included.size() && included[s]; 31107 7657 38764
return s < included.size() && included[s]; 31107 0 31107
return s < included.size() && included[s]; 5693 25414 31107
42 }
43 29084 void insert(const T& s) {
44 29084 ▶ if (!contains(s)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!contains(s)) { 26391 2693 29084
45 26391 ▶ if (included.size() <= s) {
Branch: 1 branch
BranchTrueFalseTotal
if (included.size() <= s) { 6745 19646 26391
46 6745 included.resize(s + 1);
47 }
48 26391 ▶ included[s] = true;
Branch: 1 branch
BranchTrueFalseTotal
included[s] = true; 26391 0 26391
49 26391 elements.push_back(s);
50 }
51 29084 };
52 19360 T& back() {
53 19360 return elements.back();
54 }
55 9680 void pop_back() {
56 9680 auto back_element = back();
57 9680 ▶ included[back_element] = false;
Branch: 1 branch
BranchTrueFalseTotal
included[back_element] = false; 9680 0 9680
58 9680 elements.pop_back();
59 9680 }
60 2083 void clear() {
61 2083 included.clear();
62 2083 elements.clear();
63 2083 }
64 };
65
66 void
67 2083 add_all_reachable_and_self(
68 VectorBasedSet<State>& todo,
69 VectorBasedSet<State>& s,
70 map<State, bool>& nullable,
71 map<State, vector<State>>& successors) {
72
73 12114 ▶ for (auto i = s.elements.begin(); i != s.elements.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = s.elements.begin(); i != s.elements.end(); ++i) { 10031 2083 12114
74 10031 ▶ if (!nullable[*i])
Branch: 2 branches
BranchTrueFalseTotal
if (!nullable[*i]) 10031 0 10031
if (!nullable[*i]) 6535 3496 10031
75 6535 continue;
76
77 3496 ▶ auto x = successors[*i];
Branch: 2 branches
BranchTrueFalseTotal
auto x = successors[*i]; 3496 0 3496
auto x = successors[*i]; 3496 0 3496
78
79 11778 ▶ for (auto k = x.begin(); k != x.end(); ++k)
Branch: 1 branch
BranchTrueFalseTotal
for (auto k = x.begin(); k != x.end(); ++k) 8282 3496 11778
80 8282 ▶ todo.insert(*k);
Branch: 1 branch
BranchTrueFalseTotal
todo.insert(*k); 8282 0 8282
81 3496 }
82
83 11763 ▶ while (!todo.empty()) {
Branch: 1 branch
BranchTrueFalseTotal
while (!todo.empty()) { 9680 2083 11763
84 9680 State current = todo.back();
85 9680 ▶ todo.pop_back();
Branch: 1 branch
BranchTrueFalseTotal
todo.pop_back(); 9680 0 9680
86
87 9680 ▶ if (s.contains(current)) {
Branch: 2 branches
BranchTrueFalseTotal
if (s.contains(current)) { 9680 0 9680
if (s.contains(current)) { 3000 6680 9680
88 3000 continue;
89 }
90
91 6680 ▶ s.insert(current);
Branch: 1 branch
BranchTrueFalseTotal
s.insert(current); 6680 0 6680
92
93 6680 ▶ if (nullable[current]) {
Branch: 2 branches
BranchTrueFalseTotal
if (nullable[current]) { 6680 0 6680
if (nullable[current]) { 1079 5601 6680
94 1079 ▶ auto x = successors[current];
Branch: 2 branches
BranchTrueFalseTotal
auto x = successors[current]; 1079 0 1079
auto x = successors[current]; 1079 0 1079
95
96 3655 ▶ for (auto i = x.begin(); i != x.end(); ++i)
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = x.begin(); i != x.end(); ++i) 2576 1079 3655
97 2576 ▶ todo.insert(*i);
Branch: 1 branch
BranchTrueFalseTotal
todo.insert(*i); 2576 0 2576
98 1079 }
99 }
100 2083 }
101
102 868 bool does_accept(SV* accept_sv, vector<State> s) {
103 868 dSP;
104
105 868 ENTER;
106 868 SAVETMPS;
107
108 868 ▶ PUSHMARK(SP);
Branch: 1 branch
BranchTrueFalseTotal
PUSHMARK(SP); 0 868 868
109
110 6851 ▶ for (auto i = s.begin(); i != s.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = s.begin(); i != s.end(); ++i) { 5983 868 6851
111 5983 ▶ mXPUSHs(newSVuv(*i));
Branch: 4 branches
BranchTrueFalseTotal
mXPUSHs(newSVuv(*i)); 0 5983 5983
mXPUSHs(newSVuv(*i)); 0 0 0
mXPUSHs(newSVuv(*i)); 5983 0 5983
mXPUSHs(newSVuv(*i)); 5983 0 5983
112 }
113
114 868 PUTBACK;
115
116 868 I32 count = call_sv(accept_sv, G_SCALAR);
117
118 868 SPAGAIN;
119
120 868 bool result = false;
121
122 868 ▶ if (count == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (count == 1) { 868 0 868
123 868 result = (bool)POPi;
124 } else {
125 0 warn("bad accept");
126 }
127
128 868 PUTBACK;
129 868 ▶ FREETMPS;
Branch: 1 branch
BranchTrueFalseTotal
FREETMPS; 868 0 868
130 868 LEAVE;
131
132 868 return result;
133 }
134
135 class StatesBimap {
136 public:
137 std::map<vector<State>, StatesId> s2id;
138 std::vector<vector<State>> id2s;
139
140 86 StatesBimap() {
141 86 ▶ states_to_id(States());
Branch: 1 branch
BranchTrueFalseTotal
states_to_id(States()); 86 0 86
142 86 };
143
144 430 StatesId states_to_id(const States& s) {
145 430 vector<State> v;
146
147 430 ▶ std::copy(s.begin(), s.end(),
Branch: 2 branches
BranchTrueFalseTotal
std::copy(s.begin(), s.end(), 430 0 430
std::copy(s.begin(), s.end(), 430 0 430
148 std::back_inserter(v));
149
150 860 ▶ return states_to_id(v);
Branch: 1 branch
BranchTrueFalseTotal
return states_to_id(v); 430 0 430
151 430 }
152
153 2427 StatesId states_to_id(const vector<State>& s) {
154 2427 ▶ auto v = s;
Branch: 1 branch
BranchTrueFalseTotal
auto v = s; 2427 0 2427
155 2427 ▶ std::sort(v.begin(), v.end());
Branch: 1 branch
BranchTrueFalseTotal
std::sort(v.begin(), v.end()); 2427 0 2427
156
157 2427 ▶ if (s2id.find(v) == s2id.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (s2id.find(v) == s2id.end()) { 2427 0 2427
if (s2id.find(v) == s2id.end()) { 871 1556 2427
158 871 ▶ s2id[v] = id2s.size();
Branch: 1 branch
BranchTrueFalseTotal
s2id[v] = id2s.size(); 871 0 871
159 871 ▶ id2s.push_back(v);
Branch: 1 branch
BranchTrueFalseTotal
id2s.push_back(v); 871 0 871
160 }
161 4854 ▶ return s2id[v];
Branch: 1 branch
BranchTrueFalseTotal
return s2id[v]; 2427 0 2427
162 2427 }
163
164 1901 const vector<State>& id_to_states(StatesId id) {
165 1901 ▶ if (id >= id2s.size()) {
Branch: 1 branch
BranchTrueFalseTotal
if (id >= id2s.size()) { 0 1901 1901
166 0 warn("Programmer error looking up %u", id);
167 }
168 1901 return id2s[id];
169 }
170 };
171
172 map<size_t, HV*>
173 86 build_dfa(SV* accept_sv, AV* args) {
174
175 typedef map<pair<StatesId, Label>, StatesId> Automaton;
176 86 ▶ StatesBimap m;
Branch: 1 branch
BranchTrueFalseTotal
StatesBimap m; 86 0 86
177 86 VectorBasedSet<State> sub_todo;
178
179 // Input from Perl
180 86 map<State, vector<State>> successors;
181 86 map<State, bool> nullable;
182 86 map<State, Label> label;
183 86 map<size_t, States> start_states;
184
185 86 ▶ I32 args_len = av_len(args);
Branch: 1 branch
BranchTrueFalseTotal
I32 args_len = av_len(args); 86 0 86
186
187 1298 ▶ for (int ix = 0; ix <= args_len; ++ix) {
Branch: 1 branch
BranchTrueFalseTotal
for (int ix = 0; ix <= args_len; ++ix) { 1212 86 1298
188 1212 ▶ SV** current_svp = av_fetch(args, ix, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** current_svp = av_fetch(args, ix, 0); 1212 0 1212
189
190 1212 ▶ if (current_svp == NULL)
Branch: 1 branch
BranchTrueFalseTotal
if (current_svp == NULL) 0 1212 1212
191 0 croak("Bad arguments");
192
193 1212 SV* current_sv = (SV*)*current_svp;
194
195 1212 ▶ if (!( SvROK(current_sv) && SvTYPE(SvRV(current_sv)) == SVt_PVAV))
Branch: 2 branches
BranchTrueFalseTotal
if (!( SvROK(current_sv) && SvTYPE(SvRV(current_sv)) == SVt_PVAV)) 1212 0 1212
if (!( SvROK(current_sv) && SvTYPE(SvRV(current_sv)) == SVt_PVAV)) 0 1212 1212
196 0 croak("Bad arguments");
197
198 1212 AV* current_av = (AV*)SvRV(current_sv);
199
200 // [vertex, label, nullable, in_start, successors...]
201
202 1212 ▶ if (av_len(current_av) < 3)
Branch: 2 branches
BranchTrueFalseTotal
if (av_len(current_av) < 3) 1212 0 1212
if (av_len(current_av) < 3) 0 1212 1212
203 0 croak("Bad arguments");
204
205 1212 ▶ SV** vertex_svp = av_fetch(current_av, 0, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** vertex_svp = av_fetch(current_av, 0, 0); 1212 0 1212
206 1212 ▶ SV** label_svp = av_fetch(current_av, 1, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** label_svp = av_fetch(current_av, 1, 0); 1212 0 1212
207 1212 ▶ SV** null_svp = av_fetch(current_av, 2, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** null_svp = av_fetch(current_av, 2, 0); 1212 0 1212
208 1212 ▶ SV** start_svp = av_fetch(current_av, 3, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** start_svp = av_fetch(current_av, 3, 0); 1212 0 1212
209
210 1212 ▶ if (!(vertex_svp && label_svp && null_svp && start_svp))
Branch: 4 branches
BranchTrueFalseTotal
if (!(vertex_svp && label_svp && null_svp && start_svp)) 1212 0 1212
if (!(vertex_svp && label_svp && null_svp && start_svp)) 1212 0 1212
if (!(vertex_svp && label_svp && null_svp && start_svp)) 1212 0 1212
if (!(vertex_svp && label_svp && null_svp && start_svp)) 0 1212 1212
211 0 croak("Internal error");
212
213 1212 ▶ nullable[SvUV(*vertex_svp)] = SvTRUE(*null_svp);
Branch: 3 branches
BranchTrueFalseTotal
nullable[SvUV(*vertex_svp)] = SvTRUE(*null_svp); 1212 0 1212
nullable[SvUV(*vertex_svp)] = SvTRUE(*null_svp); 1212 0 1212
nullable[SvUV(*vertex_svp)] = SvTRUE(*null_svp); 1212 0 1212
214
215 1212 ▶ if (SvOK(*label_svp))
Branch: 1 branch
BranchTrueFalseTotal
if (SvOK(*label_svp)) 939 273 1212
216 939 ▶ label[SvUV(*vertex_svp)] = SvUV(*label_svp);
Branch: 3 branches
BranchTrueFalseTotal
label[SvUV(*vertex_svp)] = SvUV(*label_svp); 939 0 939
label[SvUV(*vertex_svp)] = SvUV(*label_svp); 939 0 939
label[SvUV(*vertex_svp)] = SvUV(*label_svp); 939 0 939
217
218
219 1212 ▶ if (!( SvROK(*start_svp) && SvTYPE(SvRV(*start_svp)) == SVt_PVAV))
Branch: 2 branches
BranchTrueFalseTotal
if (!( SvROK(*start_svp) && SvTYPE(SvRV(*start_svp)) == SVt_PVAV)) 1212 0 1212
if (!( SvROK(*start_svp) && SvTYPE(SvRV(*start_svp)) == SVt_PVAV)) 0 1212 1212
220 0 croak("Bad arguments");
221
222 1212 AV* start_av = (AV*)SvRV(*start_svp);
223 1212 ▶ I32 start_av_len = av_len(start_av);
Branch: 1 branch
BranchTrueFalseTotal
I32 start_av_len = av_len(start_av); 1212 0 1212
224
225 1323 ▶ for (int k = 0; k <= start_av_len; ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (int k = 0; k <= start_av_len; ++k) { 111 1212 1323
226 111 ▶ SV** item_svp = av_fetch(start_av, k, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** item_svp = av_fetch(start_av, k, 0); 111 0 111
227 111 ▶ if (SvUV(*item_svp) == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (SvUV(*item_svp) == 0) { 111 0 111
if (SvUV(*item_svp) == 0) { 0 111 111
228 0 croak("Bad arguments (start vertex)");
229 }
230 111 ▶ start_states[SvUV(*item_svp)].insert(SvUV(*vertex_svp));
Branch: 4 branches
BranchTrueFalseTotal
start_states[SvUV(*item_svp)].insert(SvUV(*vertex_svp)); 111 0 111
start_states[SvUV(*item_svp)].insert(SvUV(*vertex_svp)); 111 0 111
start_states[SvUV(*item_svp)].insert(SvUV(*vertex_svp)); 111 0 111
start_states[SvUV(*item_svp)].insert(SvUV(*vertex_svp)); 111 0 111
231 }
232
233 1212 ▶ I32 current_av_len = av_len(current_av);
Branch: 1 branch
BranchTrueFalseTotal
I32 current_av_len = av_len(current_av); 1212 0 1212
234
235 3297 ▶ for (int k = 4; k <= current_av_len; ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (int k = 4; k <= current_av_len; ++k) { 2085 1212 3297
236 2085 ▶ SV** successor_svp = av_fetch(current_av, k, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** successor_svp = av_fetch(current_av, k, 0); 2085 0 2085
237
238 2085 ▶ if (!successor_svp)
Branch: 1 branch
BranchTrueFalseTotal
if (!successor_svp) 0 2085 2085
239 0 croak("Internal error");
240
241 2085 ▶ successors[SvUV(*vertex_svp)].push_back(SvUV(*successor_svp));
Branch: 4 branches
BranchTrueFalseTotal
successors[SvUV(*vertex_svp)].push_back(SvUV(*successor_svp)); 2085 0 2085
successors[SvUV(*vertex_svp)].push_back(SvUV(*successor_svp)); 2085 0 2085
successors[SvUV(*vertex_svp)].push_back(SvUV(*successor_svp)); 2085 0 2085
successors[SvUV(*vertex_svp)].push_back(SvUV(*successor_svp)); 2085 0 2085
242 }
243 }
244
245 86 VectorBasedSet<State> sub_temp;
246 86 set<StatesId> seen;
247 86 list<StatesId> todo;
248 86 set<StatesId> final_states;
249 86 Automaton automaton;
250 86 map<StatesId, set<StatesId>> predecessors;
251 86 map<StatesId, bool> accepting;
252
253 172 ▶ for (auto s = start_states.begin(); s != start_states.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = start_states.begin(); s != start_states.end(); ++s) { 86 86 172
254 86 States& start_state = s->second;
255
256 86 sub_temp.clear();
257
258 197 ▶ for (auto i = start_state.begin(); i != start_state.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = start_state.begin(); i != start_state.end(); ++i) { 111 86 197
259 111 ▶ sub_temp.insert(*i);
Branch: 1 branch
BranchTrueFalseTotal
sub_temp.insert(*i); 111 0 111
260 }
261
262 86 ▶ add_all_reachable_and_self(sub_todo, sub_temp, nullable, successors);
Branch: 1 branch
BranchTrueFalseTotal
add_all_reachable_and_self(sub_todo, sub_temp, nullable, successors); 86 0 86
263
264 86 ▶ start_state.insert(sub_temp.elements.begin(), sub_temp.elements.end());
Branch: 1 branch
BranchTrueFalseTotal
start_state.insert(sub_temp.elements.begin(), sub_temp.elements.end()); 86 0 86
265
266 86 ▶ auto startId = m.states_to_id(start_state);
Branch: 1 branch
BranchTrueFalseTotal
auto startId = m.states_to_id(start_state); 86 0 86
267 86 ▶ todo.push_front(startId);
Branch: 1 branch
BranchTrueFalseTotal
todo.push_front(startId); 86 0 86
268 }
269
270 2169 ▶ while (!todo.empty()) {
Branch: 1 branch
BranchTrueFalseTotal
while (!todo.empty()) { 2083 86 2169
271 2083 StatesId currentId = todo.front();
272 2083 todo.pop_front();
273
274 2083 ▶ if (seen.find(currentId) != seen.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (seen.find(currentId) != seen.end()) { 2083 0 2083
if (seen.find(currentId) != seen.end()) { 1258 825 2083
275 1258 continue;
276 }
277
278 825 ▶ seen.insert(currentId);
Branch: 1 branch
BranchTrueFalseTotal
seen.insert(currentId); 825 0 825
279
280 825 ▶ vector<State> current = m.id_to_states(currentId);
Branch: 2 branches
BranchTrueFalseTotal
vector<State> current = m.id_to_states(currentId); 825 0 825
vector<State> current = m.id_to_states(currentId); 825 0 825
281
282 825 ▶ if (accepting.find(currentId) == accepting.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (accepting.find(currentId) == accepting.end()) { 825 0 825
if (accepting.find(currentId) == accepting.end()) { 825 0 825
283 825 ▶ accepting[currentId] = does_accept(accept_sv, current);
Branch: 3 branches
BranchTrueFalseTotal
accepting[currentId] = does_accept(accept_sv, current); 825 0 825
accepting[currentId] = does_accept(accept_sv, current); 825 0 825
accepting[currentId] = does_accept(accept_sv, current); 825 0 825
284 }
285
286 825 ▶ if (accepting[currentId]) {
Branch: 2 branches
BranchTrueFalseTotal
if (accepting[currentId]) { 825 0 825
if (accepting[currentId]) { 334 491 825
287 334 ▶ final_states.insert(currentId);
Branch: 1 branch
BranchTrueFalseTotal
final_states.insert(currentId); 334 0 334
288 }
289
290 825 map<Label, States> by_label;
291
292 6792 ▶ for (auto i = current.begin(); i != current.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = current.begin(); i != current.end(); ++i) { 5967 825 6792
293 5967 ▶ if (label.find(*i) == label.end())
Branch: 2 branches
BranchTrueFalseTotal
if (label.find(*i) == label.end()) 5967 0 5967
if (label.find(*i) == label.end()) 773 5194 5967
294 773 continue;
295
296 5194 ▶ by_label[label[*i]].insert(*i);
Branch: 3 branches
BranchTrueFalseTotal
by_label[label[*i]].insert(*i); 5194 0 5194
by_label[label[*i]].insert(*i); 5194 0 5194
by_label[label[*i]].insert(*i); 5194 0 5194
297 }
298
299 2822 ▶ for (auto i = by_label.begin(); i != by_label.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = by_label.begin(); i != by_label.end(); ++i) { 1997 825 2822
300 1997 States destination;
301 1997 ▶ auto second = i->second;
Branch: 1 branch
BranchTrueFalseTotal
auto second = i->second; 1997 0 1997
302 1997 auto current_label = i->first;
303
304 1997 sub_temp.clear();
305
306 7191 ▶ for (auto j = second.begin(); j != second.end(); ++j) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto j = second.begin(); j != second.end(); ++j) { 5194 1997 7191
307 5194 ▶ auto x = successors[*j];
Branch: 2 branches
BranchTrueFalseTotal
auto x = successors[*j]; 5194 0 5194
auto x = successors[*j]; 5194 0 5194
308 16629 ▶ for (auto k = x.begin(); k != x.end(); ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto k = x.begin(); k != x.end(); ++k) { 11435 5194 16629
309 11435 ▶ sub_temp.insert(*k);
Branch: 1 branch
BranchTrueFalseTotal
sub_temp.insert(*k); 11435 0 11435
310 }
311 5194 }
312
313 1997 ▶ add_all_reachable_and_self(sub_todo, sub_temp, nullable, successors);
Branch: 1 branch
BranchTrueFalseTotal
add_all_reachable_and_self(sub_todo, sub_temp, nullable, successors); 1997 0 1997
314
315 1997 ▶ StatesId destinationId = m.states_to_id(sub_temp.elements);
Branch: 1 branch
BranchTrueFalseTotal
StatesId destinationId = m.states_to_id(sub_temp.elements); 1997 0 1997
316 1997 ▶ automaton[make_pair(currentId, current_label)] = destinationId;
Branch: 2 branches
BranchTrueFalseTotal
automaton[make_pair(currentId, current_label)] = destinationId; 1997 0 1997
automaton[make_pair(currentId, current_label)] = destinationId; 1997 0 1997
317 1997 ▶ predecessors[destinationId].insert(currentId);
Branch: 2 branches
BranchTrueFalseTotal
predecessors[destinationId].insert(currentId); 1997 0 1997
predecessors[destinationId].insert(currentId); 1997 0 1997
318 1997 ▶ todo.push_front(destinationId);
Branch: 1 branch
BranchTrueFalseTotal
todo.push_front(destinationId); 1997 0 1997
319 1997 }
320 825 }
321
322 86 set<StatesId> reachable;
323 86 list<StatesId> reachable_todo;
324
325 86 ▶ std::copy(final_states.begin(), final_states.end(),
Branch: 2 branches
BranchTrueFalseTotal
std::copy(final_states.begin(), final_states.end(), 86 0 86
std::copy(final_states.begin(), final_states.end(), 86 0 86
326 std::front_inserter(reachable_todo));
327
328 2202 ▶ while (!reachable_todo.empty()) {
Branch: 1 branch
BranchTrueFalseTotal
while (!reachable_todo.empty()) { 2116 86 2202
329 2116 StatesId current = reachable_todo.front();
330 2116 reachable_todo.pop_front();
331
332 2116 ▶ if (reachable.find(current) != reachable.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (reachable.find(current) != reachable.end()) { 2116 0 2116
if (reachable.find(current) != reachable.end()) { 1377 739 2116
333 1377 continue;
334 }
335
336 739 ▶ reachable.insert(current);
Branch: 1 branch
BranchTrueFalseTotal
reachable.insert(current); 739 0 739
337
338 1478 ▶ std::copy(predecessors[current].begin(),
Branch: 3 branches
BranchTrueFalseTotal
std::copy(predecessors[current].begin(), 739 0 739
std::copy(predecessors[current].begin(), 739 0 739
std::copy(predecessors[current].begin(), 739 0 739
339 739 ▶ predecessors[current].end(),
Branch: 1 branch
BranchTrueFalseTotal
predecessors[current].end(), 739 0 739
340 std::front_inserter(reachable_todo));
341 }
342
343 86 States sink;
344
345 2083 ▶ for (auto s = automaton.begin(); s != automaton.end(); /* */) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = automaton.begin(); s != automaton.end(); /* */) { 1997 86 2083
346 1997 StatesId src = s->first.first;
347 1997 Label label = s->first.second;
348 1997 StatesId dst = s->second;
349
350 1997 ▶ if (reachable.find(src) == reachable.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (reachable.find(src) == reachable.end()) { 1997 0 1997
if (reachable.find(src) == reachable.end()) { 51 1946 1997
351 51 ▶ vector<State> x = m.id_to_states(src);
Branch: 2 branches
BranchTrueFalseTotal
vector<State> x = m.id_to_states(src); 51 0 51
vector<State> x = m.id_to_states(src); 51 0 51
352 51 ▶ sink.insert(x.begin(), x.end());
Branch: 1 branch
BranchTrueFalseTotal
sink.insert(x.begin(), x.end()); 51 0 51
353 51 ▶ s = automaton.erase(s);
Branch: 1 branch
BranchTrueFalseTotal
s = automaton.erase(s); 51 0 51
354 51 continue;
355 51 }
356
357 1946 ▶ if (reachable.find(dst) == reachable.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (reachable.find(dst) == reachable.end()) { 1946 0 1946
if (reachable.find(dst) == reachable.end()) { 157 1789 1946
358 157 ▶ vector<State> x = m.id_to_states(dst);
Branch: 2 branches
BranchTrueFalseTotal
vector<State> x = m.id_to_states(dst); 157 0 157
vector<State> x = m.id_to_states(dst); 157 0 157
359 157 ▶ sink.insert(x.begin(), x.end());
Branch: 1 branch
BranchTrueFalseTotal
sink.insert(x.begin(), x.end()); 157 0 157
360 157 ▶ s = automaton.erase(s);
Branch: 1 branch
BranchTrueFalseTotal
s = automaton.erase(s); 157 0 157
361 157 continue;
362 157 }
363
364 1789 s++;
365 }
366
367 86 ▶ auto sinkId = m.states_to_id(sink);
Branch: 1 branch
BranchTrueFalseTotal
auto sinkId = m.states_to_id(sink); 86 0 86
368
369 86 ▶ if (accepting.find(sinkId) == accepting.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (accepting.find(sinkId) == accepting.end()) { 86 0 86
if (accepting.find(sinkId) == accepting.end()) { 43 43 86
370 43 ▶ accepting[sinkId] = does_accept(accept_sv, m.id_to_states(sinkId));
Branch: 4 branches
BranchTrueFalseTotal
accepting[sinkId] = does_accept(accept_sv, m.id_to_states(sinkId)); 43 0 43
accepting[sinkId] = does_accept(accept_sv, m.id_to_states(sinkId)); 43 0 43
accepting[sinkId] = does_accept(accept_sv, m.id_to_states(sinkId)); 43 0 43
accepting[sinkId] = does_accept(accept_sv, m.id_to_states(sinkId)); 43 0 43
371 }
372
373 86 ▶ seen.insert(sinkId);
Branch: 1 branch
BranchTrueFalseTotal
seen.insert(sinkId); 86 0 86
374
375 86 map<StatesId, size_t> state_map;
376 86 ▶ state_map[sinkId] = 0;
Branch: 1 branch
BranchTrueFalseTotal
state_map[sinkId] = 0; 86 0 86
377 86 size_t state_next = 1 + start_states.size();
378
379 86 map<StatesId, size_t> start_ix_to_state_map_id;
380
381 172 ▶ for (auto s = start_states.begin(); s != start_states.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = start_states.begin(); s != start_states.end(); ++s) { 86 86 172
382 86 auto startIx = s->first;
383 86 ▶ auto state = s->second;
Branch: 1 branch
BranchTrueFalseTotal
auto state = s->second; 86 0 86
384 86 ▶ auto startId = m.states_to_id(state);
Branch: 1 branch
BranchTrueFalseTotal
auto startId = m.states_to_id(state); 86 0 86
385
386 86 ▶ if (reachable.find(startId) == reachable.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (reachable.find(startId) == reachable.end()) { 86 0 86
if (reachable.find(startId) == reachable.end()) { 0 86 86
387 0 croak("start state %u unreachable", startIx);
388 }
389
390 86 ▶ if (state_map.find(startId) != state_map.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (state_map.find(startId) != state_map.end()) { 86 0 86
if (state_map.find(startId) != state_map.end()) { 86 0 86
391 // This happens when equivalent start states are passed to the
392 // construction function.
393 } else {
394 86 ▶ state_map[startId] = startIx;
Branch: 1 branch
BranchTrueFalseTotal
state_map[startId] = startIx; 86 0 86
395 }
396 86 }
397
398 // ...
399 86 map<size_t, HV*> dfa;
400
401 86 ▶ reachable.insert(sinkId);
Branch: 1 branch
BranchTrueFalseTotal
reachable.insert(sinkId); 86 0 86
402
403 911 ▶ for (auto s = reachable.begin(); s != reachable.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = reachable.begin(); s != reachable.end(); ++s) { 825 86 911
404 825 ▶ if (state_map.find(*s) == state_map.end()) {
Branch: 2 branches
BranchTrueFalseTotal
if (state_map.find(*s) == state_map.end()) { 825 0 825
if (state_map.find(*s) == state_map.end()) { 653 172 825
405 653 ▶ state_map[*s] = state_next++;
Branch: 1 branch
BranchTrueFalseTotal
state_map[*s] = state_next++; 653 0 653
406 }
407 }
408
409 86 map<size_t, StatesId> state_map_r;
410
411 911 ▶ for (auto s = state_map.begin(); s != state_map.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = state_map.begin(); s != state_map.end(); ++s) { 825 86 911
412 825 ▶ state_map_r[s->second] = s->first;
Branch: 1 branch
BranchTrueFalseTotal
state_map_r[s->second] = s->first; 825 0 825
413 }
414
415 // If multiple start states are passed to the construction function and
416 // they either are identical, or turn out to be equivalent once all the
417 // epsilon-reachable states are added to them, mapping distinct states
418 // to distinct numbers leaves out the duplicates. Since the API conven-
419 // tion is that states 1..n in the generated DFA correspond to the 1..n
420 // start state in the input, the duplicates have to be generated here.
421
422 172 ▶ for (auto s = start_states.begin(); s != start_states.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = start_states.begin(); s != start_states.end(); ++s) { 86 86 172
423 86 auto startIx = s->first;
424 86 ▶ auto state = s->second;
Branch: 1 branch
BranchTrueFalseTotal
auto state = s->second; 86 0 86
425 86 ▶ auto startId = m.states_to_id(state);
Branch: 1 branch
BranchTrueFalseTotal
auto startId = m.states_to_id(state); 86 0 86
426 86 ▶ state_map_r[startIx] = startId;
Branch: 1 branch
BranchTrueFalseTotal
state_map_r[startIx] = startId; 86 0 86
427 86 }
428
429 86 multimap<StatesId, HV*> id_to_hvs;
430
431 911 ▶ for (auto s = state_map_r.begin(); s != state_map_r.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = state_map_r.begin(); s != state_map_r.end(); ++s) { 825 86 911
432
433 825 ▶ HV* state_hv = newHV();
Branch: 1 branch
BranchTrueFalseTotal
HV* state_hv = newHV(); 825 0 825
434 825 ▶ AV* combines_av = newAV();
Branch: 1 branch
BranchTrueFalseTotal
AV* combines_av = newAV(); 825 0 825
435 825 ▶ SV* combines_rv = newRV_noinc((SV*)combines_av);
Branch: 1 branch
BranchTrueFalseTotal
SV* combines_rv = newRV_noinc((SV*)combines_av); 825 0 825
436 825 ▶ HV* next_over_hv = newHV();
Branch: 1 branch
BranchTrueFalseTotal
HV* next_over_hv = newHV(); 825 0 825
437 825 ▶ SV* next_over_rv = newRV_noinc((SV*)next_over_hv);
Branch: 1 branch
BranchTrueFalseTotal
SV* next_over_rv = newRV_noinc((SV*)next_over_hv); 825 0 825
438
439 825 ▶ auto he1 = hv_store(state_hv, "Accepts", 7, newSVuv(accepting[s->second]), 0);
Branch: 3 branches
BranchTrueFalseTotal
auto he1 = hv_store(state_hv, "Accepts", 7, newSVuv(accepting[s->second]), 0); 825 0 825
auto he1 = hv_store(state_hv, "Accepts", 7, newSVuv(accepting[s->second]), 0); 825 0 825
auto he1 = hv_store(state_hv, "Accepts", 7, newSVuv(accepting[s->second]), 0); 825 0 825
440 825 ▶ auto he2 = hv_store(state_hv, "Combines", 8, combines_rv, 0);
Branch: 1 branch
BranchTrueFalseTotal
auto he2 = hv_store(state_hv, "Combines", 8, combines_rv, 0); 825 0 825
441 825 ▶ auto he3 = hv_store(state_hv, "NextOver", 8, next_over_rv, 0);
Branch: 1 branch
BranchTrueFalseTotal
auto he3 = hv_store(state_hv, "NextOver", 8, next_over_rv, 0); 825 0 825
442
443 825 ▶ vector<State> x = m.id_to_states(s->second);
Branch: 2 branches
BranchTrueFalseTotal
vector<State> x = m.id_to_states(s->second); 825 0 825
vector<State> x = m.id_to_states(s->second); 825 0 825
444
445 6779 ▶ for (auto k = x.begin(); k != x.end(); ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto k = x.begin(); k != x.end(); ++k) { 5954 825 6779
446 5954 ▶ av_push(combines_av, newSVuv(*k));
Branch: 2 branches
BranchTrueFalseTotal
av_push(combines_av, newSVuv(*k)); 5954 0 5954
av_push(combines_av, newSVuv(*k)); 5954 0 5954
447 }
448
449 825 ▶ dfa[s->first] = state_hv;
Branch: 1 branch
BranchTrueFalseTotal
dfa[s->first] = state_hv; 825 0 825
450
451 825 ▶ id_to_hvs.insert(make_pair(s->second, state_hv));
Branch: 2 branches
BranchTrueFalseTotal
id_to_hvs.insert(make_pair(s->second, state_hv)); 825 0 825
id_to_hvs.insert(make_pair(s->second, state_hv)); 825 0 825
452 825 }
453
454 1875 ▶ for (auto s = automaton.begin(); s != automaton.end(); ++s) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto s = automaton.begin(); s != automaton.end(); ++s) { 1789 86 1875
455 1789 StatesId srcId = s->first.first;
456 1789 Label label = s->first.second;
457 1789 StatesId dstId = s->second;
458
459 1789 ▶ if (dfa.find(state_map[srcId]) == dfa.end()) {
Branch: 3 branches
BranchTrueFalseTotal
if (dfa.find(state_map[srcId]) == dfa.end()) { 1789 0 1789
if (dfa.find(state_map[srcId]) == dfa.end()) { 1789 0 1789
if (dfa.find(state_map[srcId]) == dfa.end()) { 0 1789 1789
460 0 croak("...");
461 }
462
463 3578 ▶ for (auto p = id_to_hvs.find(srcId); p != id_to_hvs.end(); ++p) {
Branch: 2 branches
BranchTrueFalseTotal
for (auto p = id_to_hvs.find(srcId); p != id_to_hvs.end(); ++p) { 1789 0 1789
for (auto p = id_to_hvs.find(srcId); p != id_to_hvs.end(); ++p) { 3473 105 3578
464 3473 ▶ if (p->first != srcId)
Branch: 1 branch
BranchTrueFalseTotal
if (p->first != srcId) 1684 1789 3473
465 1684 break;
466
467 1789 ▶ SV** next_over_svp = hv_fetch(p->second, "NextOver", 8, 0);
Branch: 1 branch
BranchTrueFalseTotal
SV** next_over_svp = hv_fetch(p->second, "NextOver", 8, 0); 1789 0 1789
468
469 1789 ▶ if (!next_over_svp)
Branch: 1 branch
BranchTrueFalseTotal
if (!next_over_svp) 0 1789 1789
470 0 croak("...");
471
472 1789 ▶ SV* label_sv = newSVuv(label);
Branch: 1 branch
BranchTrueFalseTotal
SV* label_sv = newSVuv(label); 1789 0 1789
473
474 1789 ▶ HE* he = hv_store_ent((HV*)SvRV(*next_over_svp),
Branch: 3 branches
BranchTrueFalseTotal
HE* he = hv_store_ent((HV*)SvRV(*next_over_svp), 1789 0 1789
HE* he = hv_store_ent((HV*)SvRV(*next_over_svp), 1789 0 1789
HE* he = hv_store_ent((HV*)SvRV(*next_over_svp), 1789 0 1789
475 label_sv, newSVuv(state_map[dstId]), 0);
476
477 1789 ▶ if (he == NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (he == NULL) { 0 1789 1789
478 0 ▶ warn("hv_store_ent failed");
Branch: 1 branch
BranchTrueFalseTotal
warn("hv_store_ent failed"); 0 0 0
479 0 ▶ SvREFCNT_dec(label_sv);
Branch: 1 branch
BranchTrueFalseTotal
SvREFCNT_dec(label_sv); 0 0 0
480 }
481 }
482 }
483
484 172 return dfa;
485 86 }
486
487 MODULE = Algorithm::ConstructDFA::XS PACKAGE = Algorithm::ConstructDFA::XS
488
489 void
490 _internal_construct_dfa_xs(accepts_sv, args_sv)
491 SV* accepts_sv
492 SV* args_sv
493 PREINIT:
494 AV* args;
495 PPCODE:
496 86 args = (AV*)SvRV(args_sv);
497
498 86 PUTBACK;
499 86 ▶ auto dfa = build_dfa(accepts_sv, args);
Branch: 1 branch
BranchTrueFalseTotal
auto dfa = build_dfa(accepts_sv, args); 86 0 86
500 86 SPAGAIN;
501
502 911 ▶ for (auto i = dfa.begin(); i != dfa.end(); ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (auto i = dfa.begin(); i != dfa.end(); ++i) { 825 86 911
503 825 ▶ mXPUSHs(newSVuv(i->first));
Branch: 4 branches
BranchTrueFalseTotal
mXPUSHs(newSVuv(i->first)); 0 825 825
mXPUSHs(newSVuv(i->first)); 0 0 0
mXPUSHs(newSVuv(i->first)); 825 0 825
mXPUSHs(newSVuv(i->first)); 825 0 825
504 825 ▶ mXPUSHs(newRV_noinc((SV*)(i->second)));
Branch: 4 branches
BranchTrueFalseTotal
mXPUSHs(newRV_noinc((SV*)(i->second))); 0 825 825
mXPUSHs(newRV_noinc((SV*)(i->second))); 0 0 0
mXPUSHs(newRV_noinc((SV*)(i->second))); 825 0 825
mXPUSHs(newRV_noinc((SV*)(i->second))); 825 0 825
505 }
« blib/lib/Algorithm/ConstructDFA/XS.pm ↑ Summary