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