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