2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your 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 Affero General Public License for more details.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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 {
46 int should_save_graph;
48 unsigned int string_count;
50 unsigned int match_count;
53 struct RegexStringPair {
55 unsigned int string_count;
61 key_iterator(void *cls, const struct GNUNET_HashCode *key,
63 int accepting, unsigned int num_edges,
64 const struct REGEX_BLOCK_Edge *edges)
67 struct IteratorContext *ctx = cls;
69 char *state_id = GNUNET_strdup(GNUNET_h2s(key));
71 GNUNET_assert(NULL != proof);
72 if (GNUNET_YES == ctx->should_save_graph)
74 if (GNUNET_YES == accepting)
75 GNUNET_asprintf(&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
77 GNUNET_asprintf(&out_str, "\"%s\" [shape=circle]\n", state_id);
78 fwrite(out_str, strlen(out_str), 1, ctx->graph_filep);
81 for (i = 0; i < num_edges; i++)
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);
94 for (i = 0; i < num_edges; i++)
98 for (i = 0; i < ctx->string_count; i++)
100 if (0 == strcmp(proof, ctx->strings[i]))
104 if (GNUNET_OK != REGEX_BLOCK_check_proof(proof, strlen(proof), key))
107 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
108 "Proof check failed: proof: %s key: %s\n", proof, state_id);
110 GNUNET_free(state_id);
115 main(int argc, char *argv[])
117 GNUNET_log_setup("test-regex", "WARNING", NULL);
120 struct REGEX_INTERNAL_Automaton *dfa;
122 unsigned int num_transitions;
123 char *filename = NULL;
124 struct IteratorContext ctx = { 0, 0, NULL, 0, NULL, 0 };
128 const struct RegexStringPair rxstr[13] = {
129 { INITIAL_PADDING "ab(c|d)+c*(a(b|c)+d)+(bla)+", 2,
130 { INITIAL_PADDING "abcdcdca", INITIAL_PADDING "abcabdbl" } },
132 "abcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd", 1,
133 { INITIAL_PADDING "abcdefgh" } },
134 { INITIAL_PADDING "VPN-4-1(0|1)*", 2,
135 { INITIAL_PADDING "VPN-4-10", INITIAL_PADDING "VPN-4-11" } },
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,
137 { INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING "aaXXyyyc" } },
138 { INITIAL_PADDING "a*", 1, { INITIAL_PADDING "aaaaaaaa" } },
139 { INITIAL_PADDING "xzxzxzxzxz", 1, { INITIAL_PADDING "xzxzxzxz" } },
140 { INITIAL_PADDING "xyz*", 1, { INITIAL_PADDING "xyzzzzzz" } },
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)",
143 2, { INITIAL_PADDING "abcd:000", INITIAL_PADDING "abcd:101" } },
144 { INITIAL_PADDING "(x*|(0|1|2)(a|b|c|d)+)", 2,
145 { INITIAL_PADDING "xxxxxxxx", INITIAL_PADDING "0abcdbad" } },
146 { INITIAL_PADDING "(0|1)(0|1)23456789ABC", 1, { INITIAL_PADDING "11234567" } },
147 { INITIAL_PADDING "0*123456789ABC*", 3,
148 { INITIAL_PADDING "00123456", INITIAL_PADDING "00000000",
149 INITIAL_PADDING "12345678" } },
150 { INITIAL_PADDING "0123456789A*BC", 1, { INITIAL_PADDING "01234567" } },
151 { "GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, { "GNUNETVPN000100000IPEX6-" } }
154 const char *graph_start_str = "digraph G {\nrankdir=LR\n";
155 const char *graph_end_str = "\n}\n";
157 for (i = 0; i < 13; i++)
159 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
164 if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
166 GNUNET_asprintf(&filename, "iteration_graph_%u.dot", i);
167 ctx.graph_filep = fopen(filename, "w");
168 if (NULL == ctx.graph_filep)
170 GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
171 "Could not open file %s for saving iteration graph.\n",
173 ctx.should_save_graph = GNUNET_NO;
177 ctx.should_save_graph = GNUNET_YES;
178 fwrite(graph_start_str, strlen(graph_start_str), 1, ctx.graph_filep);
180 GNUNET_free(filename);
184 ctx.should_save_graph = GNUNET_NO;
185 ctx.graph_filep = NULL;
188 /* Iterate over DFA edges */
189 transition_counter = 0;
190 ctx.string_count = rxstr[i].string_count;
191 ctx.strings = rxstr[i].strings;
194 REGEX_INTERNAL_construct_dfa(rxstr[i].regex, strlen(rxstr[i].regex), 0);
195 REGEX_INTERNAL_iterate_all_edges(dfa, key_iterator, &ctx);
197 REGEX_INTERNAL_get_transition_count(dfa) - dfa->start->transition_count;
199 if (transition_counter < num_transitions)
201 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
202 "Automaton has %d transitions, iterated over %d transitions\n",
203 num_transitions, transition_counter);
207 if (ctx.match_count < ctx.string_count)
209 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
210 "Missing initial states for regex %s\n", rxstr[i].regex);
211 error += (ctx.string_count - ctx.match_count);
213 else if (ctx.match_count > ctx.string_count)
215 GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
216 "Duplicate initial transitions for regex %s\n",
218 error += (ctx.string_count - ctx.match_count);
221 REGEX_INTERNAL_automaton_destroy(dfa);
224 if (GNUNET_YES == ctx.should_save_graph)
226 fwrite(graph_end_str, strlen(graph_end_str), 1, ctx.graph_filep);
227 fclose(ctx.graph_filep);
228 ctx.graph_filep = NULL;
229 ctx.should_save_graph = GNUNET_NO;
234 for (i = 0; i < 13; i++)
236 ctx.string_count = rxstr[i].string_count;
237 ctx.strings = rxstr[i].strings;
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);
245 if (ctx.match_count < ctx.string_count)
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);
252 REGEX_INTERNAL_automaton_destroy(dfa);