src/regex/test_regex_iterate_api.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2012 GNUnet e.V.
   4
   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.
   9
  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.
  14
  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/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19  */
  20 /**
  21  * @file regex/test_regex_iterate_api.c
  22  * @brief test for regex.c
  23  * @author Maximilian Szengel
  24  */
  25 #include <regex.h>
  26 #include <time.h>
  27 #include "platform.h"
  28 #include "regex_internal_lib.h"
  29 #include "regex_block_lib.h"
  30 #include "regex_internal.h"
  31
  32 /**
  33  * Regex initial padding.
  34  */
  35 #define INITIAL_PADDING "PADPADPADPADPADP"
  36
  37 /**
  38  * Set to GNUNET_YES to save a debug graph.
  39  */
  40 #define REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH GNUNET_NO
  41
  42 static unsigned int transition_counter;
  43
  44 struct IteratorContext {
  45   int error;
  46   int should_save_graph;
  47   FILE *graph_filep;
  48   unsigned int string_count;
  49   char *const *strings;
  50   unsigned int match_count;
  51 };
  52
  53 struct RegexStringPair {
  54   char *regex;
  55   unsigned int string_count;
  56   char *strings[20];
  57 };
  58
  59
  60 static void
  61 key_iterator(void *cls, const struct GNUNET_HashCode *key,
  62              const char *proof,
  63              int accepting, unsigned int num_edges,
  64              const struct REGEX_BLOCK_Edge *edges)
  65 {
  66   unsigned int i;
  67   struct IteratorContext *ctx = cls;
  68   char *out_str;
  69   char *state_id = GNUNET_strdup(GNUNET_h2s(key));
  70
  71   GNUNET_assert(NULL != proof);
  72   if (GNUNET_YES == ctx->should_save_graph)
  73     {
  74       if (GNUNET_YES == accepting)
  75         GNUNET_asprintf(&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
  76       else
  77         GNUNET_asprintf(&out_str, "\"%s\" [shape=circle]\n", state_id);
  78       fwrite(out_str, strlen(out_str), 1, ctx->graph_filep);
  79       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         }
  91     }
  92   else
  93     {
  94       for (i = 0; i < num_edges; i++)
  95         transition_counter++;
  96     }
  97
  98   for (i = 0; i < ctx->string_count; i++)
  99     {
 100       if (0 == strcmp(proof, ctx->strings[i]))
 101         ctx->match_count++;
 102     }
 103
 104   if (GNUNET_OK != REGEX_BLOCK_check_proof(proof, strlen(proof), key))
 105     {
 106       ctx->error++;
 107       GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 108                  "Proof check failed: proof: %s key: %s\n", proof, state_id);
 109     }
 110   GNUNET_free(state_id);
 111 }
 112
 113
 114 int
 115 main(int argc, char *argv[])
 116 {
 117   GNUNET_log_setup("test-regex", "WARNING", NULL);
 118
 119   int error;
 120   struct REGEX_INTERNAL_Automaton *dfa;
 121   unsigned int i;
 122   unsigned int num_transitions;
 123   char *filename = NULL;
 124   struct IteratorContext ctx = { 0, 0, NULL, 0, NULL, 0 };
 125
 126   error = 0;
 127
 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" } },
 131     { INITIAL_PADDING
 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" } },
 141     { INITIAL_PADDING
 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-" } }
 152   };
 153
 154   const char *graph_start_str = "digraph G {\nrankdir=LR\n";
 155   const char *graph_end_str = "\n}\n";
 156
 157   for (i = 0; i < 13; i++)
 158     {
 159       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
 160                  rxstr[i].regex);
 161
 162
 163       /* Create graph */
 164       if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
 165         {
 166           GNUNET_asprintf(&filename, "iteration_graph_%u.dot", i);
 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         }
 182       else
 183         {
 184           ctx.should_save_graph = GNUNET_NO;
 185           ctx.graph_filep = NULL;
 186         }
 187
 188       /* Iterate over DFA edges */
 189       transition_counter = 0;
 190       ctx.string_count = rxstr[i].string_count;
 191       ctx.strings = rxstr[i].strings;
 192       ctx.match_count = 0;
 193       dfa =
 194         REGEX_INTERNAL_construct_dfa(rxstr[i].regex, strlen(rxstr[i].regex), 0);
 195       REGEX_INTERNAL_iterate_all_edges(dfa, key_iterator, &ctx);
 196       num_transitions =
 197         REGEX_INTERNAL_get_transition_count(dfa) - dfa->start->transition_count;
 198
 199       if (transition_counter < num_transitions)
 200         {
 201           GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 202                      "Automaton has %d transitions, iterated over %d transitions\n",
 203                      num_transitions, transition_counter);
 204           error += 1;
 205         }
 206
 207       if (ctx.match_count < ctx.string_count)
 208         {
 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);
 212         }
 213       else if (ctx.match_count > ctx.string_count)
 214         {
 215           GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 216                      "Duplicate initial transitions for regex %s\n",
 217                      rxstr[i].regex);
 218           error += (ctx.string_count - ctx.match_count);
 219         }
 220
 221       REGEX_INTERNAL_automaton_destroy(dfa);
 222
 223       /* Finish graph */
 224       if (GNUNET_YES == ctx.should_save_graph)
 225         {
 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;
 230         }
 231     }
 232
 233
 234   for (i = 0; i < 13; i++)
 235     {
 236       ctx.string_count = rxstr[i].string_count;
 237       ctx.strings = rxstr[i].strings;
 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);
 253     }
 254
 255   error += ctx.error;
 256
 257   return error;
 258 }