2 This file is part of GNUnet
3 (C) 2012 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
21 * @file regex/test_regex_iterate_api.c
22 * @brief test for regex.c
23 * @author Maximilian Szengel
28 #include "regex_internal_lib.h"
29 #include "regex_block_lib.h"
30 #include "regex_internal.h"
33 * Regex initial padding.
35 #define INITIAL_PADDING "PADPADPADPADPADP"
38 * Set to GNUNET_YES to save a debug graph.
40 #define REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH GNUNET_NO
42 static unsigned int transition_counter;
44 struct IteratorContext
47 int should_save_graph;
49 unsigned int valid_string_count;
50 char *const *valid_strings;
51 unsigned int match_count;
52 unsigned int invalid_string_count;
53 char *const *invalid_strings;
54 unsigned int invalid_match_count;
57 struct RegexStringPair
60 unsigned int valid_string_count;
61 char *valid_strings[20];
62 unsigned int invalid_string_count;
63 char *invalid_strings[20];
68 key_iterator (void *cls, const struct GNUNET_HashCode *key,
70 int accepting, unsigned int num_edges,
71 const struct REGEX_BLOCK_Edge *edges)
74 struct IteratorContext *ctx = cls;
76 char *state_id = GNUNET_strdup (GNUNET_h2s (key));
78 GNUNET_assert (NULL != proof);
79 if (GNUNET_YES == ctx->should_save_graph)
81 if (GNUNET_YES == accepting)
82 GNUNET_asprintf (&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
84 GNUNET_asprintf (&out_str, "\"%s\" [shape=circle]\n", state_id);
85 fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
86 GNUNET_free (out_str);
88 for (i = 0; i < num_edges; i++)
91 GNUNET_asprintf (&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n",
92 state_id, GNUNET_h2s (&edges[i].destination),
93 edges[i].label, proof);
94 fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
96 GNUNET_free (out_str);
101 for (i = 0; i < num_edges; i++)
102 transition_counter++;
105 for (i = 0; i < ctx->valid_string_count; i++)
107 if (0 == strcmp (proof, ctx->valid_strings[i]))
111 for (i = 0; i < ctx->invalid_string_count; i++)
113 if (0 == strcmp (proof, ctx->invalid_strings[i])) {
114 ctx->invalid_match_count++;
118 if (GNUNET_OK != REGEX_BLOCK_check_proof (proof, strlen (proof), key))
121 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
122 "Proof check failed: proof: %s key: %s\n", proof, state_id);
124 GNUNET_free (state_id);
129 main (int argc, char *argv[])
131 GNUNET_log_setup ("test-regex", "WARNING", NULL);
134 struct REGEX_INTERNAL_Automaton *dfa;
136 unsigned int num_transitions;
137 char *filename = NULL;
138 struct IteratorContext ctx = { 0, 0, NULL, 0, NULL, 0 };
142 const struct RegexStringPair rxstr[14] = {
143 {INITIAL_PADDING "ab(c|d)+c*(a(b|c)+d)+(bla)+", 2,
144 {INITIAL_PADDING "abcdcdca", INITIAL_PADDING "abcabdbl"}, 2,
145 {INITIAL_PADDING, INITIAL_PADDING "ab"}},
147 "abcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd", 1,
148 {INITIAL_PADDING "abcdefgh"}, 2, {INITIAL_PADDING, INITIAL_PADDING "a"}},
149 {INITIAL_PADDING "VPN-4-1(0|1)*", 2,
150 {INITIAL_PADDING "VPN-4-10", INITIAL_PADDING "VPN-4-11"},
151 1, {INITIAL_PADDING}},
152 {INITIAL_PADDING "(a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*)", 2,
153 {INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING "aaXXyyyc"}},
154 {INITIAL_PADDING "a*", 2, {INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING}},
155 {INITIAL_PADDING "xzxzxzxzxz", 1, {INITIAL_PADDING "xzxzxzxz"},
156 1, {INITIAL_PADDING}},
157 {INITIAL_PADDING "xyz*", 1, {INITIAL_PADDING "xyzzzzzz"},
158 1, {INITIAL_PADDING}},
160 "abcd:(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1):(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)",
161 2, {INITIAL_PADDING "abcd:000", INITIAL_PADDING "abcd:101"},
162 1, {INITIAL_PADDING}},
163 {INITIAL_PADDING "(x*|(0|1|2)(a|b|c|d)+)", 2,
164 {INITIAL_PADDING "xxxxxxxx", INITIAL_PADDING "0abcdbad"}},
165 {INITIAL_PADDING "(0|1)(0|1)23456789ABC", 1, {INITIAL_PADDING "11234567"},
166 1, {INITIAL_PADDING}},
167 {INITIAL_PADDING "0*123456789ABC*", 3,
168 {INITIAL_PADDING "00123456", INITIAL_PADDING "00000000",
169 INITIAL_PADDING "12345678"}},
170 {INITIAL_PADDING "0123456789A*BC", 1, {INITIAL_PADDING "01234567"}},
171 {"GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, {"GNUNETVPN000100000IPEX6-"},
172 1, {INITIAL_PADDING}},
173 {"my long prefix - hello world(0|1)*", 0, {"my long prefix - hello world"},
174 1, {"my long prefix"}}
177 const char *graph_start_str = "digraph G {\nrankdir=LR\n";
178 const char *graph_end_str = "\n}\n";
180 for (i = 0; i < 14; i++)
182 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
187 if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
189 GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i);
190 ctx.graph_filep = fopen (filename, "w");
191 if (NULL == ctx.graph_filep)
193 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
194 "Could not open file %s for saving iteration graph.\n",
196 ctx.should_save_graph = GNUNET_NO;
200 ctx.should_save_graph = GNUNET_YES;
201 fwrite (graph_start_str, strlen (graph_start_str), 1, ctx.graph_filep);
203 GNUNET_free (filename);
207 ctx.should_save_graph = GNUNET_NO;
208 ctx.graph_filep = NULL;
211 /* Iterate over DFA edges */
212 ctx.valid_string_count = rxstr[i].valid_string_count;
213 ctx.valid_strings = rxstr[i].valid_strings;
215 ctx.invalid_string_count = rxstr[i].invalid_string_count;
216 ctx.invalid_strings = rxstr[i].invalid_strings;
217 ctx.invalid_match_count = 0;
219 REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 1);
220 REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx);
222 if (0 != ctx.invalid_match_count)
224 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
225 "Found invalid initial states for regex %s\n",
227 error += ctx.invalid_match_count;
230 if (ctx.match_count < ctx.valid_string_count)
232 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
233 "Missing initial states for regex %s\n", rxstr[i].regex);
234 error += (ctx.valid_string_count - ctx.match_count);
236 else if (ctx.match_count > ctx.valid_string_count)
238 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
239 "Duplicate initial transitions for regex %s\n",
241 error += (ctx.valid_string_count - ctx.match_count);
244 REGEX_INTERNAL_automaton_destroy (dfa);
247 if (GNUNET_YES == ctx.should_save_graph)
249 fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep);
250 fclose (ctx.graph_filep);
251 ctx.graph_filep = NULL;
252 ctx.should_save_graph = GNUNET_NO;
257 for (i = 0; i < 14; i++)
259 transition_counter = 0;
260 ctx.valid_string_count = rxstr[i].valid_string_count;
261 ctx.valid_strings = rxstr[i].valid_strings;
263 ctx.invalid_string_count = rxstr[i].invalid_string_count;
264 ctx.invalid_strings = rxstr[i].invalid_strings;
265 ctx.invalid_match_count = 0;
268 REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0);
269 REGEX_INTERNAL_dfa_add_multi_strides (NULL, dfa, 2);
270 REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx);
272 REGEX_INTERNAL_get_transition_count (dfa) - dfa->start->transition_count;
274 if (transition_counter < num_transitions)
276 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
277 "Automaton has %d transitions, iterated over %d transitions\n",
278 num_transitions, transition_counter);
282 if (ctx.match_count < ctx.valid_string_count)
284 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
285 "Missing initial states for regex %s\n", rxstr[i].regex);
286 error += (ctx.valid_string_count - ctx.match_count);
289 if (0 != ctx.invalid_match_count)
291 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
292 "Found invalid initial states for regex %s\n",
294 error += ctx.invalid_match_count;
297 REGEX_INTERNAL_automaton_destroy (dfa);