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