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 "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 {
  46   int error;
  47   int should_save_graph;
  48   FILE *graph_filep;
  49   unsigned int valid_string_count;
  50   char *const *valid_strings;
  51   unsigned int match_count;
  52   unsigned int invalid_string_count;
  53   char *const *invalid_strings;
  54   unsigned int invalid_match_count;
  55 };
  56
  57 struct RegexStringPair
  58 {
  59   char *regex;
  60   unsigned int valid_string_count;
  61   char *valid_strings[20];
  62   unsigned int invalid_string_count;
  63   char *invalid_strings[20];
  64 };
  65
  66
  67 static void
  68 key_iterator (void *cls, const struct GNUNET_HashCode *key,
  69               const char *proof,
  70               int accepting, unsigned int num_edges,
  71               const struct REGEX_BLOCK_Edge *edges)
  72 {
  73   unsigned int i;
  74   struct IteratorContext *ctx = cls;
  75   char *out_str;
  76   char *state_id = GNUNET_strdup (GNUNET_h2s (key));
  77
  78   GNUNET_assert (NULL != proof);
  79   if (GNUNET_YES == ctx->should_save_graph)
  80   {
  81     if (GNUNET_YES == accepting)
  82       GNUNET_asprintf (&out_str, "\"%s\" [shape=doublecircle]\n", state_id);
  83     else
  84       GNUNET_asprintf (&out_str, "\"%s\" [shape=circle]\n", state_id);
  85     fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
  86     GNUNET_free (out_str);
  87
  88     for (i = 0; i < num_edges; i++)
  89     {
  90       transition_counter++;
  91       GNUNET_asprintf (&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n",
  92                        state_id, GNUNET_h2s (&edges[i].destination),
  93                        edges[i].label, proof);
  94       fwrite (out_str, strlen (out_str), 1, ctx->graph_filep);
  95
  96       GNUNET_free (out_str);
  97     }
  98   }
  99   else
 100   {
 101     for (i = 0; i < num_edges; i++)
 102       transition_counter++;
 103   }
 104
 105   for (i = 0; i < ctx->valid_string_count; i++)
 106   {
 107     if (0 == strcmp (proof, ctx->valid_strings[i]))
 108       ctx->match_count++;
 109   }
 110
 111   for (i = 0; i < ctx->invalid_string_count; i++)
 112   {
 113     if (0 == strcmp (proof, ctx->invalid_strings[i])) {
 114       ctx->invalid_match_count++;
 115     }
 116   }
 117
 118   if (GNUNET_OK != REGEX_BLOCK_check_proof (proof, strlen (proof), key))
 119   {
 120     ctx->error++;
 121     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 122                 "Proof check failed: proof: %s key: %s\n", proof, state_id);
 123   }
 124   GNUNET_free (state_id);
 125 }
 126
 127
 128 int
 129 main (int argc, char *argv[])
 130 {
 131   GNUNET_log_setup ("test-regex", "WARNING", NULL);
 132
 133   int error;
 134   struct REGEX_INTERNAL_Automaton *dfa;
 135   unsigned int i;
 136   unsigned int num_transitions;
 137   char *filename = NULL;
 138   struct IteratorContext ctx = { 0, 0, NULL, 0, NULL, 0 };
 139
 140   error = 0;
 141
 142   const struct RegexStringPair rxstr[14] = {
 143     {INITIAL_PADDING "ab(c|d)+c*(a(b|c)+d)+(bla)+", 2,
 144      {INITIAL_PADDING "abcdcdca", INITIAL_PADDING "abcabdbl"}, 2,
 145      {INITIAL_PADDING, INITIAL_PADDING "ab"}},
 146     {INITIAL_PADDING
 147      "abcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd", 1,
 148      {INITIAL_PADDING "abcdefgh"}, 2, {INITIAL_PADDING, INITIAL_PADDING "a"}},
 149     {INITIAL_PADDING "VPN-4-1(0|1)*", 2,
 150      {INITIAL_PADDING "VPN-4-10", INITIAL_PADDING "VPN-4-11"},
 151      1, {INITIAL_PADDING}},
 152     {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,
 153      {INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING "aaXXyyyc"}},
 154     {INITIAL_PADDING "a*", 2, {INITIAL_PADDING "aaaaaaaa", INITIAL_PADDING}},
 155     {INITIAL_PADDING "xzxzxzxzxz", 1, {INITIAL_PADDING "xzxzxzxz"},
 156      1, {INITIAL_PADDING}},
 157     {INITIAL_PADDING "xyz*", 1, {INITIAL_PADDING "xyzzzzzz"},
 158      1, {INITIAL_PADDING}},
 159     {INITIAL_PADDING
 160      "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)",
 161      2, {INITIAL_PADDING "abcd:000", INITIAL_PADDING "abcd:101"},
 162      1, {INITIAL_PADDING}},
 163     {INITIAL_PADDING "(x*|(0|1|2)(a|b|c|d)+)", 2,
 164      {INITIAL_PADDING "xxxxxxxx", INITIAL_PADDING "0abcdbad"}},
 165     {INITIAL_PADDING "(0|1)(0|1)23456789ABC", 1, {INITIAL_PADDING "11234567"},
 166      1, {INITIAL_PADDING}},
 167     {INITIAL_PADDING "0*123456789ABC*", 3,
 168      {INITIAL_PADDING "00123456", INITIAL_PADDING "00000000",
 169       INITIAL_PADDING "12345678"}},
 170     {INITIAL_PADDING "0123456789A*BC", 1, {INITIAL_PADDING "01234567"}},
 171     {"GNUNETVPN000100000IPEX6-fc5a:4e1:c2ba::1", 1, {"GNUNETVPN000100000IPEX6-"},
 172      1, {INITIAL_PADDING}},
 173     {"my long prefix - hello world(0|1)*", 0, {"my long prefix - hello world"},
 174      1, {"my long prefix"}}
 175   };
 176
 177   const char *graph_start_str = "digraph G {\nrankdir=LR\n";
 178   const char *graph_end_str = "\n}\n";
 179
 180   for (i = 0; i < 14; i++)
 181   {
 182     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating DFA for regex %s\n",
 183                 rxstr[i].regex);
 184
 185
 186     /* Create graph */
 187     if (GNUNET_YES == REGEX_INTERNAL_ITERATE_SAVE_DEBUG_GRAPH)
 188     {
 189       GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i);
 190       ctx.graph_filep = fopen (filename, "w");
 191       if (NULL == ctx.graph_filep)
 192       {
 193         GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 194                     "Could not open file %s for saving iteration graph.\n",
 195                     filename);
 196         ctx.should_save_graph = GNUNET_NO;
 197       }
 198       else
 199       {
 200         ctx.should_save_graph = GNUNET_YES;
 201         fwrite (graph_start_str, strlen (graph_start_str), 1, ctx.graph_filep);
 202       }
 203       GNUNET_free (filename);
 204     }
 205     else
 206     {
 207       ctx.should_save_graph = GNUNET_NO;
 208       ctx.graph_filep = NULL;
 209     }
 210
 211     /* Iterate over DFA edges */
 212     ctx.valid_string_count = rxstr[i].valid_string_count;
 213     ctx.valid_strings = rxstr[i].valid_strings;
 214     ctx.match_count = 0;
 215     ctx.invalid_string_count = rxstr[i].invalid_string_count;
 216     ctx.invalid_strings = rxstr[i].invalid_strings;
 217     ctx.invalid_match_count = 0;
 218     dfa =
 219         REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 1);
 220     REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx);
 221
 222     if (0 != ctx.invalid_match_count)
 223     {
 224       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 225                   "Found invalid initial states for regex %s\n",
 226                   rxstr[i].regex);
 227       error += ctx.invalid_match_count;
 228     }
 229
 230     if (ctx.match_count < ctx.valid_string_count)
 231     {
 232       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 233                   "Missing initial states for regex %s\n", rxstr[i].regex);
 234       error += (ctx.valid_string_count - ctx.match_count);
 235     }
 236     else if (ctx.match_count > ctx.valid_string_count)
 237     {
 238       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 239                   "Duplicate initial transitions for regex %s\n",
 240                   rxstr[i].regex);
 241       error += (ctx.valid_string_count - ctx.match_count);
 242     }
 243
 244     REGEX_INTERNAL_automaton_destroy (dfa);
 245
 246     /* Finish graph */
 247     if (GNUNET_YES == ctx.should_save_graph)
 248     {
 249       fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep);
 250       fclose (ctx.graph_filep);
 251       ctx.graph_filep = NULL;
 252       ctx.should_save_graph = GNUNET_NO;
 253     }
 254   }
 255
 256
 257   for (i = 0; i < 14; i++)
 258   {
 259     transition_counter = 0;
 260     ctx.valid_string_count = rxstr[i].valid_string_count;
 261     ctx.valid_strings = rxstr[i].valid_strings;
 262     ctx.match_count = 0;
 263     ctx.invalid_string_count = rxstr[i].invalid_string_count;
 264     ctx.invalid_strings = rxstr[i].invalid_strings;
 265     ctx.invalid_match_count = 0;
 266
 267     dfa =
 268         REGEX_INTERNAL_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0);
 269     REGEX_INTERNAL_dfa_add_multi_strides (NULL, dfa, 2);
 270     REGEX_INTERNAL_iterate_all_edges (dfa, key_iterator, &ctx);
 271     num_transitions =
 272         REGEX_INTERNAL_get_transition_count (dfa) - dfa->start->transition_count;
 273
 274     if (transition_counter < num_transitions)
 275     {
 276       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 277                   "Automaton has %d transitions, iterated over %d transitions\n",
 278                   num_transitions, transition_counter);
 279       error += 1;
 280     }
 281
 282     if (ctx.match_count < ctx.valid_string_count)
 283     {
 284       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 285                   "Missing initial states for regex %s\n", rxstr[i].regex);
 286       error += (ctx.valid_string_count - ctx.match_count);
 287     }
 288
 289     if (0 != ctx.invalid_match_count)
 290     {
 291       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 292                   "Found invalid initial states for regex %s\n",
 293                   rxstr[i].regex);
 294       error += ctx.invalid_match_count;
 295     }
 296
 297     REGEX_INTERNAL_automaton_destroy (dfa);
 298   }
 299
 300   error += ctx.error;
 301
 302   return error;
 303 }