aboutsummaryrefslogtreecommitdiff
path: root/src/regex/test_regex_iterate_api.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/regex/test_regex_iterate_api.c')
-rw-r--r--src/regex/test_regex_iterate_api.c314
1 files changed, 156 insertions, 158 deletions
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c
index bbc60475e..7711a1154 100644
--- a/src/regex/test_regex_iterate_api.c
+++ b/src/regex/test_regex_iterate_api.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 regex/test_regex_iterate_api.c 21 * @file regex/test_regex_iterate_api.c
22 * @brief test for regex.c 22 * @brief test for regex.c
@@ -41,8 +41,7 @@
41 41
42static unsigned int transition_counter; 42static unsigned int transition_counter;
43 43
44struct IteratorContext 44struct IteratorContext {
45{
46 int error; 45 int error;
47 int should_save_graph; 46 int should_save_graph;
48 FILE *graph_filep; 47 FILE *graph_filep;
@@ -51,8 +50,7 @@ struct IteratorContext
51 unsigned int match_count; 50 unsigned int match_count;
52}; 51};
53 52
54struct RegexStringPair 53struct RegexStringPair {
55{
56 char *regex; 54 char *regex;
57 unsigned int string_count; 55 unsigned int string_count;
58 char *strings[20]; 56 char *strings[20];
@@ -60,63 +58,63 @@ struct RegexStringPair
60 58
61 59
62static void 60static void
63key_iterator (void *cls, const struct GNUNET_HashCode *key, 61key_iterator(void *cls, const struct GNUNET_HashCode *key,
64 const char *proof, 62 const char *proof,
65 int accepting, unsigned int num_edges, 63 int accepting, unsigned int num_edges,
66 const struct REGEX_BLOCK_Edge *edges) 64 const struct REGEX_BLOCK_Edge *edges)
67{ 65{
68 unsigned int i; 66 unsigned int i;
69 struct IteratorContext *ctx = cls; 67 struct IteratorContext *ctx = cls;
70 char *out_str; 68 char *out_str;
71 char *state_id = GNUNET_strdup (GNUNET_h2s (key)); 69 char *state_id = GNUNET_strdup(GNUNET_h2s(key));
72 70
73 GNUNET_assert (NULL != proof); 71 GNUNET_assert(NULL != proof);
74 if (GNUNET_YES == ctx->should_save_graph) 72 if (GNUNET_YES == ctx->should_save_graph)
75 {
76 if (GNUNET_YES == accepting)
77 GNUNET_asprintf (&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
78 else
79 GNUNET_asprintf (&out_str, "\"%s\" [shape=circle]\n", state_id);
80 fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
81 GNUNET_free (out_str);
82
83 for (i = 0; i < num_edges; i++)
84 { 73 {
85 transition_counter++; 74 if (GNUNET_YES == accepting)
86 GNUNET_asprintf (&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n", 75 GNUNET_asprintf(&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
87 state_id, GNUNET_h2s (&edges[i].destination), 76 else
88 edges[i].label, proof); 77 GNUNET_asprintf(&out_str, "\"%s\" [shape=circle]\n", state_id);
89 fwrite (out_str, strlen (out_str), 1, ctx->graph_filep); 78 fwrite(out_str, strlen(out_str), 1, ctx->graph_filep);
90 79 GNUNET_free(out_str);
91 GNUNET_free (out_str); 80
81 for (i = 0; i < num_edges; i++)
82 {
83 transition_counter++;
84 GNUNET_asprintf(&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n",
85 state_id, GNUNET_h2s(&edges[i].destination),
86 edges[i].label, proof);
87 fwrite(out_str, strlen(out_str), 1, ctx->graph_filep);
88
89 GNUNET_free(out_str);
90 }
92 } 91 }
93 }
94 else 92 else
95 { 93 {
96 for (i = 0; i < num_edges; i++) 94 for (i = 0; i < num_edges; i++)
97 transition_counter++; 95 transition_counter++;
98 } 96 }
99 97
100 for (i = 0; i < ctx->string_count; i++) 98 for (i = 0; i < ctx->string_count; i++)
101 { 99 {
102 if (0 == strcmp (proof, ctx->strings[i])) 100 if (0 == strcmp(proof, ctx->strings[i]))
103 ctx->match_count++; 101 ctx->match_count++;
104 } 102 }
105 103
106 if (GNUNET_OK != REGEX_BLOCK_check_proof (proof, strlen (proof), key)) 104 if (GNUNET_OK != REGEX_BLOCK_check_proof(proof, strlen(proof), key))
107 { 105 {
108 ctx->error++; 106 ctx->error++;
109 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 107 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
110 "Proof check failed: proof: %s key: %s\n", proof, state_id); 108 "Proof check failed: proof: %s key: %s\n", proof, state_id);
111 } 109 }
112 GNUNET_free (state_id); 110 GNUNET_free(state_id);
113} 111}
114 112
115 113
116int 114int
117main (int argc, char *argv[]) 115main(int argc, char *argv[])
118{ 116{
119 GNUNET_log_setup ("test-regex", "WARNING", NULL); 117 GNUNET_log_setup("test-regex", "WARNING", NULL);
120 118
121 int error; 119 int error;
122 struct REGEX_INTERNAL_Automaton *dfa; 120 struct REGEX_INTERNAL_Automaton *dfa;
@@ -128,132 +126,132 @@ main (int argc, char *argv[])
128 error = 0; 126 error = 0;
129 127
130 const struct RegexStringPair rxstr[13] = { 128 const struct RegexStringPair rxstr[13] = {
131 {INITIAL_PADDING "ab(c|d)+c*(a(b|c)+d)+(bla)+", 2, 129 { INITIAL_PADDING "ab(c|d)+c*(a(b|c)+d)+(bla)+", 2,
132 {INITIAL_PADDING "abcdcdca", INITIAL_PADDING "abcabdbl"}}, 130 { INITIAL_PADDING "abcdcdca", INITIAL_PADDING "abcabdbl" } },
133 {INITIAL_PADDING 131 { INITIAL_PADDING
134 "abcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd", 1, 132 "abcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd", 1,
135 {INITIAL_PADDING "abcdefgh"}}, 133 { INITIAL_PADDING "abcdefgh" } },
136 {INITIAL_PADDING "VPN-4-1(0|1)*", 2, 134 { INITIAL_PADDING "VPN-4-1(0|1)*", 2,
137 {INITIAL_PADDING "VPN-4-10", INITIAL_PADDING "VPN-4-11"}}, 135 { INITIAL_PADDING "VPN-4-10", INITIAL_PADDING "VPN-4-11" } },
138 {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, 136 { 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,
139 {INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING "aaXXyyyc"}}, 137 { INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING "aaXXyyyc" } },
140 {INITIAL_PADDING "a*", 1, {INITIAL_PADDING "aaaaaaaa"}}, 138 { INITIAL_PADDING "a*", 1, { INITIAL_PADDING "aaaaaaaa" } },
141 {INITIAL_PADDING "xzxzxzxzxz", 1, {INITIAL_PADDING "xzxzxzxz"}}, 139 { INITIAL_PADDING "xzxzxzxzxz", 1, { INITIAL_PADDING "xzxzxzxz" } },
142 {INITIAL_PADDING "xyz*", 1, {INITIAL_PADDING "xyzzzzzz"}}, 140 { INITIAL_PADDING "xyz*", 1, { INITIAL_PADDING "xyzzzzzz" } },
143 {INITIAL_PADDING 141 { INITIAL_PADDING
144 "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)", 142 "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)",
145 2, {INITIAL_PADDING "abcd:000", INITIAL_PADDING "abcd:101"}}, 143 2, { INITIAL_PADDING "abcd:000", INITIAL_PADDING "abcd:101" } },
146 {INITIAL_PADDING "(x*|(0|1|2)(a|b|c|d)+)", 2, 144 { INITIAL_PADDING "(x*|(0|1|2)(a|b|c|d)+)", 2,
147 {INITIAL_PADDING "xxxxxxxx", INITIAL_PADDING "0abcdbad"}}, 145 { INITIAL_PADDING "xxxxxxxx", INITIAL_PADDING "0abcdbad" } },
148 {INITIAL_PADDING "(0|1)(0|1)23456789ABC", 1, {INITIAL_PADDING "11234567"}}, 146 { INITIAL_PADDING "(0|1)(0|1)23456789ABC", 1, { INITIAL_PADDING "11234567" } },
149 {INITIAL_PADDING "0*123456789ABC*", 3, 147 { INITIAL_PADDING "0*123456789ABC*", 3,
150 {INITIAL_PADDING "00123456", INITIAL_PADDING "00000000", 148 { INITIAL_PADDING "00123456", INITIAL_PADDING "00000000",
151 INITIAL_PADDING "12345678"}}, 149 INITIAL_PADDING "12345678" } },
152 {INITIAL_PADDING "0123456789A*BC", 1, {INITIAL_PADDING "01234567"}}, 150 { INITIAL_PADDING "0123456789A*BC", 1, { INITIAL_PADDING "01234567" } },
153 {"GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, {"GNUNETVPN000100000IPEX6-"}} 151 { "GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, { "GNUNETVPN000100000IPEX6-" } }
154 }; 152 };
155 153
156 const char *graph_start_str = "digraph G {\nrankdir=LR\n"; 154 const char *graph_start_str = "digraph G {\nrankdir=LR\n";
157 const char *graph_end_str = "\n}\n"; 155 const char *graph_end_str = "\n}\n";
158 156
159 for (i = 0; i < 13; i++) 157 for (i = 0; i < 13; i++)
160 {
161 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
162 rxstr[i].regex);
163
164
165 /* Create graph */
166 if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
167 { 158 {
168 GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i); 159 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
169 ctx.graph_filep = fopen (filename, "w"); 160 rxstr[i].regex);
170 if (NULL == ctx.graph_filep) 161
171 { 162
172 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, 163 /* Create graph */
173 "Could not open file %s for saving iteration graph.\n", 164 if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
174 filename); 165 {
175 ctx.should_save_graph = GNUNET_NO; 166 GNUNET_asprintf(&filename, "iteration_graph_%u.dot", i);
176 } 167 ctx.graph_filep = fopen(filename, "w");
168 if (NULL == ctx.graph_filep)
169 {
170 GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
171 "Could not open file %s for saving iteration graph.\n",
172 filename);
173 ctx.should_save_graph = GNUNET_NO;
174 }
175 else
176 {
177 ctx.should_save_graph = GNUNET_YES;
178 fwrite(graph_start_str, strlen(graph_start_str), 1, ctx.graph_filep);
179 }
180 GNUNET_free(filename);
181 }
177 else 182 else
178 { 183 {
179 ctx.should_save_graph = GNUNET_YES; 184 ctx.should_save_graph = GNUNET_NO;
180 fwrite (graph_start_str, strlen (graph_start_str), 1, ctx.graph_filep); 185 ctx.graph_filep = NULL;
181 } 186 }
182 GNUNET_free (filename); 187
183 } 188 /* Iterate over DFA edges */
184 else 189 transition_counter = 0;
185 { 190 ctx.string_count = rxstr[i].string_count;
186 ctx.should_save_graph = GNUNET_NO; 191 ctx.strings = rxstr[i].strings;
187 ctx.graph_filep = NULL; 192 ctx.match_count = 0;
188 } 193 dfa =
189 194 REGEX_INTERNAL_construct_dfa(rxstr[i].regex, strlen(rxstr[i].regex), 0);
190 /* Iterate over DFA edges */ 195 REGEX_INTERNAL_iterate_all_edges(dfa, key_iterator, &ctx);
191 transition_counter = 0; 196 num_transitions =
192 ctx.string_count = rxstr[i].string_count; 197 REGEX_INTERNAL_get_transition_count(dfa) - dfa->start->transition_count;
193 ctx.strings = rxstr[i].strings; 198
194 ctx.match_count = 0; 199 if (transition_counter < num_transitions)
195 dfa = 200 {
196 REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0); 201 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
197 REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx); 202 "Automaton has %d transitions, iterated over %d transitions\n",
198 num_transitions = 203 num_transitions, transition_counter);
199 REGEX_INTERNAL_get_transition_count (dfa) - dfa->start->transition_count; 204 error += 1;
200 205 }
201 if (transition_counter < num_transitions) 206
202 { 207 if (ctx.match_count < ctx.string_count)
203 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 208 {
204 "Automaton has %d transitions, iterated over %d transitions\n", 209 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
205 num_transitions, transition_counter); 210 "Missing initial states for regex %s\n", rxstr[i].regex);
206 error += 1; 211 error += (ctx.string_count - ctx.match_count);
207 } 212 }
208 213 else if (ctx.match_count > ctx.string_count)
209 if (ctx.match_count < ctx.string_count) 214 {
210 { 215 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
211 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 216 "Duplicate initial transitions for regex %s\n",
212 "Missing initial states for regex %s\n", rxstr[i].regex); 217 rxstr[i].regex);
213 error += (ctx.string_count - ctx.match_count); 218 error += (ctx.string_count - ctx.match_count);
214 } 219 }
215 else if (ctx.match_count > ctx.string_count) 220
216 { 221 REGEX_INTERNAL_automaton_destroy(dfa);
217 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 222
218 "Duplicate initial transitions for regex %s\n", 223 /* Finish graph */
219 rxstr[i].regex); 224 if (GNUNET_YES == ctx.should_save_graph)
220 error += (ctx.string_count - ctx.match_count); 225 {
221 } 226 fwrite(graph_end_str, strlen(graph_end_str), 1, ctx.graph_filep);
222 227 fclose(ctx.graph_filep);
223 REGEX_INTERNAL_automaton_destroy (dfa); 228 ctx.graph_filep = NULL;
224 229 ctx.should_save_graph = GNUNET_NO;
225 /* Finish graph */ 230 }
226 if (GNUNET_YES == ctx.should_save_graph)
227 {
228 fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep);
229 fclose (ctx.graph_filep);
230 ctx.graph_filep = NULL;
231 ctx.should_save_graph = GNUNET_NO;
232 } 231 }
233 }
234 232
235 233
236 for (i = 0; i < 13; i++) 234 for (i = 0; i < 13; i++)
237 {
238 ctx.string_count = rxstr[i].string_count;
239 ctx.strings = rxstr[i].strings;
240 ctx.match_count = 0;
241
242 dfa =
243 REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0);
244 REGEX_INTERNAL_dfa_add_multi_strides (NULL, dfa, 2);
245 REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx);
246
247 if (ctx.match_count < ctx.string_count)
248 { 235 {
249 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 236 ctx.string_count = rxstr[i].string_count;
250 "Missing initial states for regex %s\n", rxstr[i].regex); 237 ctx.strings = rxstr[i].strings;
251 error += (ctx.string_count - ctx.match_count); 238 ctx.match_count = 0;
239
240 dfa =
241 REGEX_INTERNAL_construct_dfa(rxstr[i].regex, strlen(rxstr[i].regex), 0);
242 REGEX_INTERNAL_dfa_add_multi_strides(NULL, dfa, 2);
243 REGEX_INTERNAL_iterate_all_edges(dfa, key_iterator, &ctx);
244
245 if (ctx.match_count < ctx.string_count)
246 {
247 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
248 "Missing initial states for regex %s\n", rxstr[i].regex);
249 error += (ctx.string_count - ctx.match_count);
250 }
251
252 REGEX_INTERNAL_automaton_destroy(dfa);
252 } 253 }
253 254
254 REGEX_INTERNAL_automaton_destroy (dfa);
255 }
256
257 error += ctx.error; 255 error += ctx.error;
258 256
259 return error; 257 return error;