src/regex/test_regex_eval_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_eval_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
  30 enum Match_Result
  31 {
  32   match = 0,
  33   nomatch = 1
  34 };
  35
  36 struct Regex_String_Pair
  37 {
  38   char *regex;
  39   int string_count;
  40   char *strings[20];
  41   enum Match_Result expected_results[20];
  42 };
  43
  44 static const char allowed_literals[] =
  45     "0123456789" "ABCDEFGHIJKLMNOPQRSTUVWXYZ" "abcdefghijklmnopqrstuvwxyz";
  46
  47 int
  48 test_random (unsigned int rx_length, unsigned int max_str_len,
  49              unsigned int str_count)
  50 {
  51   int i;
  52   int j;
  53   int rx_exp;
  54   char rand_rx[rx_length + 1];
  55   char matching_str[str_count][max_str_len + 1];
  56   char *rand_rxp;
  57   char *matching_strp;
  58   int char_op_switch;
  59   int last_was_op;
  60   char current_char;
  61   int eval;
  62   int eval_check;
  63   struct GNUNET_REGEX_Automaton *dfa;
  64   regex_t rx;
  65   regmatch_t matchptr[1];
  66   char error[200];
  67   int result;
  68   unsigned int str_len;
  69
  70   // At least one string is needed for matching
  71   GNUNET_assert (str_count > 0);
  72   // The string should be at least as long as the regex itself
  73   GNUNET_assert (max_str_len >= rx_length);
  74
  75   rand_rxp = rand_rx;
  76   matching_strp = matching_str[0];
  77   current_char = 0;
  78   last_was_op = 1;
  79
  80   // Generate random regex and a string that matches the regex
  81   for (i = 0; i < rx_length; i++)
  82   {
  83     char_op_switch = 0 + (int) (1.0 * rand () / (RAND_MAX + 1.0));
  84
  85     if (0 == char_op_switch && !last_was_op)
  86     {
  87       last_was_op = 1;
  88       rx_exp = rand () % 4;
  89
  90       switch (rx_exp)
  91       {
  92       case 0:
  93         current_char = '+';
  94         break;
  95       case 1:
  96         current_char = '*';
  97         break;
  98       case 2:
  99         current_char = '?';
 100         break;
 101       case 3:
 102         if (i < rx_length - 1)  // '|' cannot be at the end
 103           current_char = '|';
 104         else
 105           current_char =
 106               allowed_literals[rand () % (sizeof (allowed_literals) - 1)];
 107         break;
 108       }
 109     }
 110     else
 111     {
 112       current_char =
 113           allowed_literals[rand () % (sizeof (allowed_literals) - 1)];
 114       last_was_op = 0;
 115     }
 116
 117     if (current_char != '+' && current_char != '*' && current_char != '?' &&
 118         current_char != '|')
 119     {
 120       *matching_strp = current_char;
 121       matching_strp++;
 122     }
 123
 124     *rand_rxp = current_char;
 125     rand_rxp++;
 126   }
 127   *rand_rxp = '\0';
 128   *matching_strp = '\0';
 129
 130   // Generate some random strings for matching...
 131   // Start at 1, because the first string is generated above during regex generation
 132   for (i = 1; i < str_count; i++)
 133   {
 134     str_len = rand () % max_str_len;
 135     for (j = 0; j < str_len; j++)
 136       matching_str[i][j] =
 137           allowed_literals[rand () % (sizeof (allowed_literals) - 1)];
 138     matching_str[i][str_len] = '\0';
 139   }
 140
 141   // Now match
 142   result = 0;
 143   for (i = 0; i < str_count; i++)
 144   {
 145     // Match string using DFA
 146     dfa = GNUNET_REGEX_construct_dfa (rand_rx, strlen (rand_rx));
 147     if (NULL == dfa)
 148     {
 149       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n");
 150       return -1;
 151     }
 152
 153     eval = GNUNET_REGEX_eval (dfa, matching_str[i]);
 154     GNUNET_REGEX_automaton_destroy (dfa);
 155
 156     // Match string using glibc regex
 157     if (0 != regcomp (&rx, rand_rx, REG_EXTENDED))
 158     {
 159       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 160                   "Could not compile regex using regcomp\n");
 161       return -1;
 162     }
 163
 164     eval_check = regexec (&rx, matching_str[i], 1, matchptr, 0);
 165     regfree (&rx);
 166
 167     // We only want to match the whole string, because that's what our DFA does, too.
 168     if (eval_check == 0 &&
 169         (matchptr[0].rm_so != 0 ||
 170          matchptr[0].rm_eo != strlen (matching_str[i])))
 171       eval_check = 1;
 172
 173     // compare result
 174     if (eval_check != eval)
 175     {
 176       regerror (eval_check, &rx, error, sizeof error);
 177       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 178                   "Unexpected result:\nregex: %s\nstring: %s\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n",
 179                   rand_rx, matching_str, eval, eval_check, error);
 180       result += 1;
 181     }
 182   }
 183   return result;
 184 }
 185
 186 int
 187 test_automaton (struct GNUNET_REGEX_Automaton *a, regex_t * rx,
 188                 struct Regex_String_Pair *rxstr)
 189 {
 190   int result;
 191   int eval;
 192   int eval_check;
 193   char error[200];
 194   regmatch_t matchptr[1];
 195   int i;
 196
 197   if (NULL == a)
 198   {
 199     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Automaton was NULL\n");
 200     return 1;
 201   }
 202
 203   result = 0;
 204
 205   for (i = 0; i < rxstr->string_count; i++)
 206   {
 207     eval = GNUNET_REGEX_eval (a, rxstr->strings[i]);
 208     eval_check = regexec (rx, rxstr->strings[i], 1, matchptr, 0);
 209
 210     // We only want to match the whole string, because that's what our DFA does, too.
 211     if (eval_check == 0 &&
 212         (matchptr[0].rm_so != 0 ||
 213          matchptr[0].rm_eo != strlen (rxstr->strings[i])))
 214       eval_check = 1;
 215
 216     if ((rxstr->expected_results[i] == match && (0 != eval || 0 != eval_check))
 217         || (rxstr->expected_results[i] == nomatch &&
 218             (0 == eval || 0 == eval_check)))
 219     {
 220       result = 1;
 221       regerror (eval_check, rx, error, sizeof error);
 222       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 223                   "Unexpected result:\nregex: %s\nstring: %s\nexpected result: %i\n"
 224                   "gnunet regex: %i\nglibc regex: %i\nglibc error: %s\nrm_so: %i\nrm_eo: %i\n\n",
 225                   rxstr->regex, rxstr->strings[i], rxstr->expected_results[i],
 226                   eval, eval_check, error, matchptr[0].rm_so,
 227                   matchptr[0].rm_eo);
 228     }
 229   }
 230   return result;
 231 }
 232
 233 int
 234 main (int argc, char *argv[])
 235 {
 236   GNUNET_log_setup ("test-regex",
 237 #if VERBOSE
 238                     "DEBUG",
 239 #else
 240                     "WARNING",
 241 #endif
 242                     NULL);
 243
 244   struct GNUNET_REGEX_Automaton *a;
 245   regex_t rx;
 246   int i;
 247   int check_nfa;
 248   int check_dfa;
 249   int check_rand;
 250
 251   struct Regex_String_Pair rxstr[5] = {
 252     {"ab?(abcd)?", 5,
 253      {"ababcd", "abab", "aabcd", "a", "abb"},
 254      {match, nomatch, match, match, nomatch}},
 255     {"ab(c|d)+c*(a(b|c)d)+", 5,
 256      {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd",
 257       "abccccca", "abcdcdcdccdabdabd"},
 258      {match, nomatch, match, nomatch, match}},
 259     {"ab+c*(a(bx|c)d)+", 5,
 260      {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd",
 261       "abccccca", "abcdcdcdccdabdabd"},
 262      {nomatch, nomatch, nomatch, nomatch, nomatch}},
 263     {"k|a+X*y+c|Q*e|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*g|N+V|t+L|P*j*3*9+X*h*J|J*6|b|E*i*f*R+S|Z|R|Y*Z|g*", 1,
 264      {"kaXycQepRZKyRwY6nhkwVFWBegNVtLPj39XhJJ6bEifRSZRYZg"},
 265      {nomatch}},
 266     {"F?W+m+2*6*c*s|P?U?a|B|y*i+t+A|V|6*C*7*e?Z*n*i|J?5+g?W*V?7*j?p?1|r?B?C+E+3+6*i+W*P?K?0|D+7?y*m+3?g?K?", 1,
 267      {"osfjsodfonONONOnosndfsdnfsd"},
 268      {nomatch}}
 269   };
 270
 271   check_nfa = 0;
 272   check_dfa = 0;
 273   check_rand = 0;
 274
 275   for (i = 0; i < 5; i++)
 276   {
 277     if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED))
 278     {
 279       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 280                   "Could not compile regex using regcomp()\n");
 281       return 1;
 282     }
 283
 284     // NFA test
 285     a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex));
 286     check_nfa += test_automaton (a, &rx, &rxstr[i]);
 287     GNUNET_REGEX_automaton_destroy (a);
 288
 289     // DFA test
 290     a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
 291     check_dfa += test_automaton (a, &rx, &rxstr[i]);
 292     GNUNET_REGEX_automaton_destroy (a);
 293
 294     regfree (&rx);
 295   }
 296
 297   srand (time (NULL));
 298   for (i = 0; i < 100; i++)
 299     check_rand += test_random (100, 150, 20);
 300
 301   return check_nfa + check_dfa + check_rand;
 302 }