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
 160     // We only want to match the whole string, because that's what our DFA does, too.
 161     if (eval_check == 0 && (matchptr[0].rm_so != 0 || matchptr[0].rm_eo != strlen (matching_str[i])))
 162       eval_check = 1;
 163
 164     // compare result
 165     if (eval_check != eval)
 166     {
 167       regerror (eval_check, &rx, error, sizeof error);
 168       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 169                   "Unexpected result:\nregex: %s\nstring: %s\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n",
 170                   rand_rx, matching_str, eval, eval_check, error);
 171       result += 1;
 172     }
 173   }
 174   return result;
 175 }
 176
 177 int
 178 test_automaton (struct GNUNET_REGEX_Automaton *a, regex_t *rx, struct Regex_String_Pair *rxstr)
 179 {
 180   int result;
 181   int eval;
 182   int eval_check;
 183   char error[200];
 184   regmatch_t matchptr[1];
 185   int i;
 186
 187   if (NULL == a)
 188   {
 189     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Automaton was NULL\n");
 190     return 1;
 191   }
 192
 193   result = 0;
 194
 195   for (i=0; i<rxstr->string_count; i++)
 196   {
 197     eval = GNUNET_REGEX_eval (a, rxstr->strings[i]);
 198     eval_check = regexec (rx, rxstr->strings[i], 1, matchptr, 0);
 199
 200     // We only want to match the whole string, because that's what our DFA does, too.
 201     if (eval_check == 0 && (matchptr[0].rm_so != 0 || matchptr[0].rm_eo != strlen (rxstr->strings[i])))
 202       eval_check = 1;
 203
 204     if ((rxstr->expected_results[i] == match
 205          && (0 != eval || 0 != eval_check))
 206         ||
 207         (rxstr->expected_results[i] == nomatch
 208          && (0 == eval || 0 == eval_check)))
 209     {
 210         result = 1;
 211         regerror (eval_check, rx, error, sizeof error);
 212         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 213                     "Unexpected result:\nregex: %s\nstring: %s\nexpected result: %i\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\nrm_so: %i\nrm_eo: %i\n\n",
 214                     rxstr->regex, rxstr->strings[i], rxstr->expected_results[i], eval, eval_check, error, matchptr[0].rm_so, matchptr[0].rm_eo);
 215     }
 216   }
 217   return result;
 218 }
 219
 220 int
 221 main (int argc, char *argv[])
 222 {
 223   GNUNET_log_setup ("test-regex",
 224 #if VERBOSE
 225                     "DEBUG",
 226 #else
 227                     "WARNING",
 228 #endif
 229                     NULL);
 230
 231   int check_nfa;
 232   int check_dfa;
 233   int check_rand;
 234   struct Regex_String_Pair rxstr[2] = {
 235     {"ab(c|d)+c*(a(b|c)d)+", 5,
 236      {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", "abccccca", "abcdcdcdccdabdabd"},
 237      {match, nomatch, match, nomatch, match}},
 238     {"ab+c*(a(bx|c)d)+", 5,
 239      {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", "abccccca", "abcdcdcdccdabdabd"},
 240      {nomatch, nomatch, nomatch, nomatch, nomatch}}};
 241   struct GNUNET_REGEX_Automaton *a;
 242   regex_t rx;
 243   int i;
 244
 245   check_nfa = 0;
 246   check_dfa = 0;
 247   check_rand = 0;
 248
 249   for (i=0; i<2; i++)
 250   {
 251     if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED))
 252     {
 253       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not compile regex using regcomp()\n");
 254       return 1;
 255     }
 256
 257     // NFA test
 258     a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex));
 259     check_nfa += test_automaton (a, &rx, &rxstr[i]);
 260     GNUNET_REGEX_automaton_destroy (a);
 261
 262     // DFA test
 263     a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
 264     check_dfa += test_automaton (a, &rx, &rxstr[i]);
 265     GNUNET_REGEX_automaton_destroy (a);
 266
 267     regfree (&rx);
 268   }
 269
 270   srand (time(NULL));
 271   for (i=0; i< 100; i++)
 272     check_rand += test_random (100, 100, 10);
 273
 274   return check_nfa + check_dfa + check_rand;
 275 }