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