diff options
Diffstat (limited to 'src/regex/regex_test_graph.c')
-rw-r--r-- | src/regex/regex_test_graph.c | 289 |
1 files changed, 144 insertions, 145 deletions
diff --git a/src/regex/regex_test_graph.c b/src/regex/regex_test_graph.c index 54ee1d17f..e809d578d 100644 --- a/src/regex/regex_test_graph.c +++ b/src/regex/regex_test_graph.c | |||
@@ -11,12 +11,12 @@ | |||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Affero General Public License for more details. | 13 | Affero General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU Affero General Public License | 15 | You should have received a copy of the GNU Affero General Public License |
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | /** | 20 | /** |
21 | * @file src/regex/regex_test_graph.c | 21 | * @file src/regex/regex_test_graph.c |
22 | * @brief functions for creating .dot graphs from regexes | 22 | * @brief functions for creating .dot graphs from regexes |
@@ -31,8 +31,7 @@ | |||
31 | * Context for graph creation. Passed as the cls to | 31 | * Context for graph creation. Passed as the cls to |
32 | * REGEX_TEST_automaton_save_graph_step. | 32 | * REGEX_TEST_automaton_save_graph_step. |
33 | */ | 33 | */ |
34 | struct REGEX_TEST_Graph_Context | 34 | struct REGEX_TEST_Graph_Context { |
35 | { | ||
36 | /** | 35 | /** |
37 | * File pointer to the dot file used for output. | 36 | * File pointer to the dot file used for output. |
38 | */ | 37 | */ |
@@ -63,10 +62,10 @@ struct REGEX_TEST_Graph_Context | |||
63 | * @param stack_size current size of the stack | 62 | * @param stack_size current size of the stack |
64 | */ | 63 | */ |
65 | static void | 64 | static void |
66 | scc_tarjan_strongconnect (unsigned int *scc_counter, | 65 | scc_tarjan_strongconnect(unsigned int *scc_counter, |
67 | struct REGEX_INTERNAL_State *v, unsigned int *index, | 66 | struct REGEX_INTERNAL_State *v, unsigned int *index, |
68 | struct REGEX_INTERNAL_State **stack, | 67 | struct REGEX_INTERNAL_State **stack, |
69 | unsigned int *stack_size) | 68 | unsigned int *stack_size) |
70 | { | 69 | { |
71 | struct REGEX_INTERNAL_State *w; | 70 | struct REGEX_INTERNAL_State *w; |
72 | struct REGEX_INTERNAL_Transition *t; | 71 | struct REGEX_INTERNAL_Transition *t; |
@@ -78,32 +77,32 @@ scc_tarjan_strongconnect (unsigned int *scc_counter, | |||
78 | v->contained = 1; | 77 | v->contained = 1; |
79 | 78 | ||
80 | for (t = v->transitions_head; NULL != t; t = t->next) | 79 | for (t = v->transitions_head; NULL != t; t = t->next) |
81 | { | ||
82 | w = t->to_state; | ||
83 | |||
84 | if (NULL == w) | ||
85 | continue; | ||
86 | |||
87 | if (w->index < 0) | ||
88 | { | 80 | { |
89 | scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size); | 81 | w = t->to_state; |
90 | v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink; | 82 | |
83 | if (NULL == w) | ||
84 | continue; | ||
85 | |||
86 | if (w->index < 0) | ||
87 | { | ||
88 | scc_tarjan_strongconnect(scc_counter, w, index, stack, stack_size); | ||
89 | v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink; | ||
90 | } | ||
91 | else if (1 == w->contained) | ||
92 | v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink; | ||
91 | } | 93 | } |
92 | else if (1 == w->contained) | ||
93 | v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink; | ||
94 | } | ||
95 | 94 | ||
96 | if (v->lowlink == v->index) | 95 | if (v->lowlink == v->index) |
97 | { | ||
98 | (*scc_counter)++; | ||
99 | do | ||
100 | { | 96 | { |
101 | w = stack[--(*stack_size)]; | 97 | (*scc_counter)++; |
102 | w->contained = 0; | 98 | do |
103 | w->scc_id = *scc_counter; | 99 | { |
100 | w = stack[--(*stack_size)]; | ||
101 | w->contained = 0; | ||
102 | w->scc_id = *scc_counter; | ||
103 | } | ||
104 | while (w != v); | ||
104 | } | 105 | } |
105 | while (w != v); | ||
106 | } | ||
107 | } | 106 | } |
108 | 107 | ||
109 | 108 | ||
@@ -114,7 +113,7 @@ scc_tarjan_strongconnect (unsigned int *scc_counter, | |||
114 | * @param a the automaton for which SCCs should be computed and assigned. | 113 | * @param a the automaton for which SCCs should be computed and assigned. |
115 | */ | 114 | */ |
116 | static void | 115 | static void |
117 | scc_tarjan (struct REGEX_INTERNAL_Automaton *a) | 116 | scc_tarjan(struct REGEX_INTERNAL_Automaton *a) |
118 | { | 117 | { |
119 | unsigned int index; | 118 | unsigned int index; |
120 | unsigned int scc_counter; | 119 | unsigned int scc_counter; |
@@ -123,21 +122,21 @@ scc_tarjan (struct REGEX_INTERNAL_Automaton *a) | |||
123 | unsigned int stack_size; | 122 | unsigned int stack_size; |
124 | 123 | ||
125 | for (v = a->states_head; NULL != v; v = v->next) | 124 | for (v = a->states_head; NULL != v; v = v->next) |
126 | { | 125 | { |
127 | v->contained = 0; | 126 | v->contained = 0; |
128 | v->index = -1; | 127 | v->index = -1; |
129 | v->lowlink = -1; | 128 | v->lowlink = -1; |
130 | } | 129 | } |
131 | 130 | ||
132 | stack_size = 0; | 131 | stack_size = 0; |
133 | index = 0; | 132 | index = 0; |
134 | scc_counter = 0; | 133 | scc_counter = 0; |
135 | 134 | ||
136 | for (v = a->states_head; NULL != v; v = v->next) | 135 | for (v = a->states_head; NULL != v; v = v->next) |
137 | { | 136 | { |
138 | if (v->index < 0) | 137 | if (v->index < 0) |
139 | scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size); | 138 | scc_tarjan_strongconnect(&scc_counter, v, &index, stack, &stack_size); |
140 | } | 139 | } |
141 | } | 140 | } |
142 | 141 | ||
143 | 142 | ||
@@ -151,8 +150,8 @@ scc_tarjan (struct REGEX_INTERNAL_Automaton *a) | |||
151 | * @param s state. | 150 | * @param s state. |
152 | */ | 151 | */ |
153 | void | 152 | void |
154 | REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count, | 153 | REGEX_TEST_automaton_save_graph_step(void *cls, unsigned int count, |
155 | struct REGEX_INTERNAL_State *s) | 154 | struct REGEX_INTERNAL_State *s) |
156 | { | 155 | { |
157 | struct REGEX_TEST_Graph_Context *ctx = cls; | 156 | struct REGEX_TEST_Graph_Context *ctx = cls; |
158 | struct REGEX_INTERNAL_Transition *ctran; | 157 | struct REGEX_INTERNAL_Transition *ctran; |
@@ -162,100 +161,100 @@ REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count, | |||
162 | char *to_name; | 161 | char *to_name; |
163 | 162 | ||
164 | if (GNUNET_YES == ctx->verbose) | 163 | if (GNUNET_YES == ctx->verbose) |
165 | GNUNET_asprintf (&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof, | 164 | GNUNET_asprintf(&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof, |
166 | GNUNET_h2s (&s->hash)); | 165 | GNUNET_h2s(&s->hash)); |
167 | else | 166 | else |
168 | GNUNET_asprintf (&name, "%i", s->dfs_id); | 167 | GNUNET_asprintf(&name, "%i", s->dfs_id); |
169 | 168 | ||
170 | if (s->accepting) | 169 | if (s->accepting) |
171 | { | ||
172 | if (GNUNET_YES == ctx->coloring) | ||
173 | { | 170 | { |
174 | GNUNET_asprintf (&s_acc, | 171 | if (GNUNET_YES == ctx->coloring) |
175 | "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n", | 172 | { |
176 | name, s->scc_id * s->scc_id); | 173 | GNUNET_asprintf(&s_acc, |
174 | "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n", | ||
175 | name, s->scc_id * s->scc_id); | ||
176 | } | ||
177 | else | ||
178 | { | ||
179 | GNUNET_asprintf(&s_acc, "\"%s\" [shape=doublecircle];\n", name, | ||
180 | s->scc_id); | ||
181 | } | ||
177 | } | 182 | } |
178 | else | 183 | else if (GNUNET_YES == ctx->coloring) |
179 | { | 184 | { |
180 | GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name, | 185 | GNUNET_asprintf(&s_acc, |
181 | s->scc_id); | 186 | "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name, |
187 | s->scc_id * s->scc_id); | ||
182 | } | 188 | } |
183 | } | ||
184 | else if (GNUNET_YES == ctx->coloring) | ||
185 | { | ||
186 | GNUNET_asprintf (&s_acc, | ||
187 | "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name, | ||
188 | s->scc_id * s->scc_id); | ||
189 | } | ||
190 | else | 189 | else |
191 | { | 190 | { |
192 | GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id); | 191 | GNUNET_asprintf(&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id); |
193 | } | 192 | } |
194 | 193 | ||
195 | GNUNET_assert (NULL != s_acc); | 194 | GNUNET_assert(NULL != s_acc); |
196 | 195 | ||
197 | fwrite (s_acc, strlen (s_acc), 1, ctx->filep); | 196 | fwrite(s_acc, strlen(s_acc), 1, ctx->filep); |
198 | GNUNET_free (s_acc); | 197 | GNUNET_free(s_acc); |
199 | s_acc = NULL; | 198 | s_acc = NULL; |
200 | 199 | ||
201 | for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next) | 200 | for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next) |
202 | { | ||
203 | if (NULL == ctran->to_state) | ||
204 | { | ||
205 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
206 | "Transition from State %i has no state for transitioning\n", | ||
207 | s->id); | ||
208 | continue; | ||
209 | } | ||
210 | |||
211 | if (GNUNET_YES == ctx->verbose) | ||
212 | { | 201 | { |
213 | GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id, | 202 | if (NULL == ctran->to_state) |
214 | ctran->to_state->name, ctran->to_state->proof, | 203 | { |
215 | GNUNET_h2s (&ctran->to_state->hash)); | 204 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
216 | } | 205 | "Transition from State %i has no state for transitioning\n", |
217 | else | 206 | s->id); |
218 | GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id); | 207 | continue; |
219 | 208 | } | |
220 | if (NULL == ctran->label) | 209 | |
221 | { | 210 | if (GNUNET_YES == ctx->verbose) |
222 | if (GNUNET_YES == ctx->coloring) | 211 | { |
223 | { | 212 | GNUNET_asprintf(&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id, |
224 | GNUNET_asprintf (&s_tran, | 213 | ctran->to_state->name, ctran->to_state->proof, |
225 | "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n", | 214 | GNUNET_h2s(&ctran->to_state->hash)); |
226 | name, to_name, s->scc_id * s->scc_id); | 215 | } |
227 | } | ||
228 | else | 216 | else |
229 | { | 217 | GNUNET_asprintf(&to_name, "%i", ctran->to_state->dfs_id); |
230 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name, | 218 | |
231 | to_name, s->scc_id); | 219 | if (NULL == ctran->label) |
232 | } | 220 | { |
233 | } | 221 | if (GNUNET_YES == ctx->coloring) |
234 | else | 222 | { |
235 | { | 223 | GNUNET_asprintf(&s_tran, |
236 | if (GNUNET_YES == ctx->coloring) | 224 | "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n", |
237 | { | 225 | name, to_name, s->scc_id * s->scc_id); |
238 | GNUNET_asprintf (&s_tran, | 226 | } |
239 | "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n", | 227 | else |
240 | name, to_name, ctran->label, s->scc_id * s->scc_id); | 228 | { |
241 | } | 229 | GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name, |
230 | to_name, s->scc_id); | ||
231 | } | ||
232 | } | ||
242 | else | 233 | else |
243 | { | 234 | { |
244 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name, | 235 | if (GNUNET_YES == ctx->coloring) |
245 | to_name, ctran->label, s->scc_id); | 236 | { |
246 | } | 237 | GNUNET_asprintf(&s_tran, |
238 | "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n", | ||
239 | name, to_name, ctran->label, s->scc_id * s->scc_id); | ||
240 | } | ||
241 | else | ||
242 | { | ||
243 | GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name, | ||
244 | to_name, ctran->label, s->scc_id); | ||
245 | } | ||
246 | } | ||
247 | |||
248 | GNUNET_free(to_name); | ||
249 | |||
250 | GNUNET_assert(NULL != s_tran); | ||
251 | |||
252 | fwrite(s_tran, strlen(s_tran), 1, ctx->filep); | ||
253 | GNUNET_free(s_tran); | ||
254 | s_tran = NULL; | ||
247 | } | 255 | } |
248 | 256 | ||
249 | GNUNET_free (to_name); | 257 | GNUNET_free(name); |
250 | |||
251 | GNUNET_assert (NULL != s_tran); | ||
252 | |||
253 | fwrite (s_tran, strlen (s_tran), 1, ctx->filep); | ||
254 | GNUNET_free (s_tran); | ||
255 | s_tran = NULL; | ||
256 | } | ||
257 | |||
258 | GNUNET_free (name); | ||
259 | } | 258 | } |
260 | 259 | ||
261 | 260 | ||
@@ -268,51 +267,51 @@ REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count, | |||
268 | * mode | 267 | * mode |
269 | */ | 268 | */ |
270 | void | 269 | void |
271 | REGEX_TEST_automaton_save_graph (struct REGEX_INTERNAL_Automaton *a, | 270 | REGEX_TEST_automaton_save_graph(struct REGEX_INTERNAL_Automaton *a, |
272 | const char *filename, | 271 | const char *filename, |
273 | enum REGEX_TEST_GraphSavingOptions options) | 272 | enum REGEX_TEST_GraphSavingOptions options) |
274 | { | 273 | { |
275 | char *start; | 274 | char *start; |
276 | char *end; | 275 | char *end; |
277 | struct REGEX_TEST_Graph_Context ctx; | 276 | struct REGEX_TEST_Graph_Context ctx; |
278 | 277 | ||
279 | if (NULL == a) | 278 | if (NULL == a) |
280 | { | 279 | { |
281 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!"); | 280 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!"); |
282 | return; | 281 | return; |
283 | } | 282 | } |
284 | 283 | ||
285 | if (NULL == filename || strlen (filename) < 1) | 284 | if (NULL == filename || strlen(filename) < 1) |
286 | { | 285 | { |
287 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!"); | 286 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "No Filename given!"); |
288 | return; | 287 | return; |
289 | } | 288 | } |
290 | 289 | ||
291 | ctx.filep = fopen (filename, "w"); | 290 | ctx.filep = fopen(filename, "w"); |
292 | ctx.verbose = | 291 | ctx.verbose = |
293 | (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES; | 292 | (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES; |
294 | ctx.coloring = | 293 | ctx.coloring = |
295 | (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES; | 294 | (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES; |
296 | 295 | ||
297 | if (NULL == ctx.filep) | 296 | if (NULL == ctx.filep) |
298 | { | 297 | { |
299 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s", | 298 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s", |
300 | filename); | 299 | filename); |
301 | return; | 300 | return; |
302 | } | 301 | } |
303 | 302 | ||
304 | /* First add the SCCs to the automaton, so we can color them nicely */ | 303 | /* First add the SCCs to the automaton, so we can color them nicely */ |
305 | if (GNUNET_YES == ctx.coloring) | 304 | if (GNUNET_YES == ctx.coloring) |
306 | scc_tarjan (a); | 305 | scc_tarjan(a); |
307 | 306 | ||
308 | start = "digraph G {\nrankdir=LR\n"; | 307 | start = "digraph G {\nrankdir=LR\n"; |
309 | fwrite (start, strlen (start), 1, ctx.filep); | 308 | fwrite(start, strlen(start), 1, ctx.filep); |
310 | 309 | ||
311 | REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL, | 310 | REGEX_INTERNAL_automaton_traverse(a, a->start, NULL, NULL, |
312 | ®EX_TEST_automaton_save_graph_step, | 311 | ®EX_TEST_automaton_save_graph_step, |
313 | &ctx); | 312 | &ctx); |
314 | 313 | ||
315 | end = "\n}\n"; | 314 | end = "\n}\n"; |
316 | fwrite (end, strlen (end), 1, ctx.filep); | 315 | fwrite(end, strlen(end), 1, ctx.filep); |
317 | fclose (ctx.filep); | 316 | fclose(ctx.filep); |
318 | } | 317 | } |