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