src/regex/test_regex_iterate_api.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012 Christian Grothoff (and other contributing authors)
   4
   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.
   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      General Public License for more details.
  14
  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.
  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 "gnunet_regex_lib.h"
  29 #include "regex_internal.h"
  30
  31 #define GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH GNUNET_NO
  32
  33 static unsigned int transition_counter;
  34
  35 struct IteratorContext
  36 {
  37   int error;
  38   int should_save_graph;
  39   FILE *graph_filep;
  40   unsigned int string_count;
  41   char *const *strings;
  42   unsigned int match_count;
  43 };
  44
  45 struct RegexStringPair
  46 {
  47   char *regex;
  48   unsigned int string_count;
  49   char *strings[20];
  50 };
  51
  52 void
  53 key_iterator (void *cls, const struct GNUNET_HashCode *key, const char *proof,
  54               int accepting, unsigned int num_edges,
  55               const struct GNUNET_REGEX_Edge *edges)
  56 {
  57   unsigned int i;
  58   struct IteratorContext *ctx = cls;
  59   char *out_str;
  60   char *state_id = GNUNET_strdup (GNUNET_h2s (key));
  61
  62   if (GNUNET_YES == ctx->should_save_graph)
  63   {
  64     if (GNUNET_YES == accepting)
  65       GNUNET_asprintf (&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
  66     else
  67       GNUNET_asprintf (&out_str, "\"%s\" [shape=circle]\n", state_id);
  68     fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
  69     GNUNET_free (out_str);
  70
  71     for (i = 0; i < num_edges; i++)
  72     {
  73       transition_counter++;
  74       GNUNET_asprintf (&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n",
  75                        state_id, GNUNET_h2s (&edges[i].destination),
  76                        edges[i].label, proof);
  77       fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
  78
  79       GNUNET_free (out_str);
  80     }
  81   }
  82   else
  83   {
  84     for (i = 0; i < num_edges; i++)
  85       transition_counter++;
  86   }
  87
  88   for (i = 0; i < ctx->string_count; i++)
  89   {
  90     if (0 == strcmp (proof, ctx->strings[i]))
  91       ctx->match_count++;
  92   }
  93
  94   if (GNUNET_OK != GNUNET_REGEX_check_proof (proof, key))
  95   {
  96     ctx->error++;
  97     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
  98                 "Proof check failed: proof: %s key: %s\n", proof, state_id);
  99   }
 100
 101   GNUNET_free (state_id);
 102 }
 103
 104 int
 105 main (int argc, char *argv[])
 106 {
 107   GNUNET_log_setup ("test-regex",
 108 #if VERBOSE
 109                     "DEBUG",
 110 #else
 111                     "WARNING",
 112 #endif
 113                     NULL);
 114
 115   int error;
 116   struct GNUNET_REGEX_Automaton *dfa;
 117   unsigned int i;
 118   unsigned int num_transitions;
 119   char *filename = NULL;
 120   struct IteratorContext ctx = { 0, 0, NULL, 0, NULL, 0 };
 121
 122   error = 0;
 123
 124   const struct RegexStringPair rxstr[14] = {
 125     {"ab(c|d)+c*(a(b|c)+d)+(bla)+", 2, {"abcdcdca", "abcabdbl"}},
 126     {"abcdefghijklmnop*qst", 1, {"abcdefgh"}},
 127     {"VPN-4-1(0|1)*", 2, {"VPN-4-10", "VPN-4-11"}},
 128     {"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", 4,
 129      {"aaaaaaaa", "aaXXyyyc", "p", "Y"}},
 130     {"a*", 8,
 131      {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa"}},
 132     {"xzxzxzxzxz", 1, {"xzxzxzxz"}},
 133     {"xyz*", 2, {"xy", "xyz"}},
 134     {"ab", 1, {"a"}},
 135     {"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)", 2, {"abcd:000", "abcd:101"}},
 136     {"x*|(0|1|2)(a|b|c|d)", 2, {"xxxxxxxx", "0a"}},
 137     {"(0|1)(0|1)23456789ABC", 1, {"11234567"}},
 138     {"0*123456789ABC*", 3, {"00123456", "00000000", "12345678"}},
 139     {"0123456789A*BC", 1, {"01234567"}},
 140     {"GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, {"GNUNETVP"}}
 141   };
 142
 143   const char *graph_start_str = "digraph G {\nrankdir=LR\n";
 144   const char *graph_end_str = "\n}\n";
 145
 146   for (i = 0; i < 14; i++)
 147   {
 148     // Create graph
 149     if (GNUNET_YES == GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH)
 150     {
 151       GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i);
 152       ctx.graph_filep = fopen (filename, "w");
 153       if (NULL == ctx.graph_filep)
 154       {
 155         GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 156                     "Could not open file %s for saving iteration graph.\n",
 157                     filename);
 158         ctx.should_save_graph = GNUNET_NO;
 159       }
 160       else
 161       {
 162         ctx.should_save_graph = GNUNET_YES;
 163         fwrite (graph_start_str, strlen (graph_start_str), 1, ctx.graph_filep);
 164       }
 165       GNUNET_free (filename);
 166     }
 167     else
 168     {
 169       ctx.should_save_graph = GNUNET_NO;
 170       ctx.graph_filep = NULL;
 171     }
 172
 173     // Iterate over DFA edges
 174     transition_counter = 0;
 175     ctx.string_count = rxstr[i].string_count;
 176     ctx.strings = rxstr[i].strings;
 177     ctx.match_count = 0;
 178     dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
 179     GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx);
 180     num_transitions = GNUNET_REGEX_get_transition_count (dfa);
 181
 182     if (transition_counter < num_transitions)
 183     {
 184       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 185                   "Automaton has %d transitions, iterated over %d transitions\n",
 186                   num_transitions, transition_counter);
 187       error += 1;
 188       break;
 189     }
 190
 191     if (ctx.match_count < ctx.string_count)
 192     {
 193       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 194                   "Missing initial states for regex %s\n", rxstr[i].regex);
 195       error += (ctx.string_count - ctx.match_count);
 196     }
 197     else if (ctx.match_count > ctx.string_count)
 198     {
 199       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 200                   "Duplicate initial transitions for regex %s\n",
 201                   rxstr[i].regex);
 202       error += (ctx.string_count - ctx.match_count);
 203     }
 204
 205     GNUNET_REGEX_automaton_destroy (dfa);
 206
 207     // Finish graph
 208     if (GNUNET_YES == ctx.should_save_graph)
 209     {
 210       fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep);
 211       fclose (ctx.graph_filep);
 212       ctx.graph_filep = NULL;
 213       ctx.should_save_graph = GNUNET_NO;
 214     }
 215   }
 216
 217
 218   for (i = 0; i < 10; i++)
 219   {
 220     ctx.string_count = rxstr[i].string_count;
 221     ctx.strings = rxstr[i].strings;
 222     ctx.match_count = 0;
 223
 224     dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
 225     GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2);
 226     GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx);
 227
 228     if (ctx.match_count < ctx.string_count)
 229     {
 230       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 231                   "Missing initial states for regex %s\n", rxstr[i].regex);
 232       error += (ctx.string_count - ctx.match_count);
 233     }
 234
 235     GNUNET_REGEX_automaton_destroy (dfa);
 236   }
 237
 238   error += ctx.error;
 239
 240   return error;
 241 }