src/regex/test_regex_proofs.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_proofs.c
  22  * @brief test for regex.c
  23  * @author Maximilian Szengel
  24  */
  25 #include "platform.h"
  26 #include "gnunet_regex_lib.h"
  27 #include "regex_internal.h"
  28
  29
  30 /**
  31  * Test if the given regex's canonical regex is the same as this canonical
  32  * regex's canonical regex. Confused? Ok, then: 1. construct a dfa A from the
  33  * given 'regex' 2. get the canonical regex of dfa A 3. construct a dfa B from
  34  * this canonical regex 3. compare the canonical regex of dfa A with the
  35  * canonical regex of dfa B.
  36  *
  37  * @param regex regular expression used for this test (see above).
  38  *
  39  * @return 0 on success, 1 on failure
  40  */
  41 unsigned int
  42 test_proof (const char *regex)
  43 {
  44   unsigned int error;
  45   struct GNUNET_REGEX_Automaton *dfa;
  46   char *c_rx1;
  47   const char *c_rx2;
  48
  49   dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex));
  50   c_rx1 = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (dfa));
  51   GNUNET_REGEX_automaton_destroy (dfa);
  52   dfa = GNUNET_REGEX_construct_dfa (c_rx1, strlen (c_rx1));
  53   c_rx2 = GNUNET_REGEX_get_canonical_regex (dfa);
  54
  55   error = (0 == strcmp (c_rx1, c_rx2)) ? 0 : 1;
  56
  57   if (error > 0)
  58   {
  59     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
  60                 "Comparing canonical regex of\n%s\nfailed:\n%s\nvs.\n%s\n",
  61                 regex, c_rx1, c_rx2);
  62   }
  63
  64   GNUNET_free (c_rx1);
  65   GNUNET_REGEX_automaton_destroy (dfa);
  66
  67   return error;
  68 }
  69
  70 /**
  71  * Use 'test_proof' function to randomly test the canonical regexes of 'count'
  72  * random expressions of length 'rx_length'.
  73  *
  74  * @param count number of random regular expressions to test.
  75  * @param rx_length length of the random regular expressions.
  76  *
  77  * @return 0 on succes, number of failures otherwise.
  78  */
  79 unsigned int
  80 test_proofs_random (unsigned int count, size_t rx_length)
  81 {
  82   unsigned int i;
  83   char *rand_rx;
  84   unsigned int failures;
  85
  86   failures = 0;
  87
  88   for (i = 0; i < count; i++)
  89   {
  90     rand_rx = GNUNET_REGEX_generate_random_regex (rx_length, NULL);
  91     failures += test_proof (rand_rx);
  92     GNUNET_free (rand_rx);
  93   }
  94
  95   return failures;
  96 }
  97
  98 /**
  99  * Test a number of known examples of regexes for proper canonicalization.
 100  *
 101  * @return 0 on success, number of failures otherwise.
 102  */
 103 unsigned int
 104 test_proofs_static (void)
 105 {
 106   unsigned int i;
 107   unsigned int error;
 108
 109   const char *regex[6] = {
 110     "a|aa*a",
 111     "a+",
 112     "a*",
 113     "a*a*",
 114     "(F*C|WfPf|y+F*C)",
 115     "y*F*C|WfPf",
 116     /* "2?jA?e?D*K", */
 117     /* "((j|2j)K|(j|2j)AK|(j|2j)(D|e|(j|2j)A(D|e))D*K)", */
 118     /* "((j|2j)K|(j|2j)(D|e|((j|2j)j|(j|2j)2j)A(D|e))D*K|(j|2j)AK)", */
 119   };
 120
 121   const char *canon_rx1;
 122   const char *canon_rx2;
 123   struct GNUNET_REGEX_Automaton *dfa1;
 124   struct GNUNET_REGEX_Automaton *dfa2;
 125
 126   error = 0;
 127
 128   for (i = 0; i < 6; i += 2)
 129   {
 130     dfa1 = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]));
 131     dfa2 = GNUNET_REGEX_construct_dfa (regex[i + 1], strlen (regex[i + 1]));
 132
 133     canon_rx1 = GNUNET_REGEX_get_canonical_regex (dfa1);
 134     canon_rx2 = GNUNET_REGEX_get_canonical_regex (dfa2);
 135
 136     error += (0 == strcmp (canon_rx1, canon_rx2)) ? 0 : 1;
 137
 138     if (error > 0)
 139     {
 140       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 141                   "Comparing canonical regex failed:\nrx1: %s\ncrx1: %s\nrx2: %s\ncrx2: %s\n",
 142                   regex[i], canon_rx1, regex[i + 1], canon_rx2);
 143
 144       /* Save the graphs of the two conflicting DFAs */
 145       /* GNUNET_REGEX_automaton_save_graph (dfa1, "proofs_fail_dfa1.dot"); */
 146       /* GNUNET_REGEX_automaton_save_graph (dfa2, "proofs_fail_dfa2.dot"); */
 147     }
 148
 149     GNUNET_REGEX_automaton_destroy (dfa1);
 150     GNUNET_REGEX_automaton_destroy (dfa2);
 151   }
 152
 153   return error;
 154 }
 155
 156
 157 int
 158 main (int argc, char *argv[])
 159 {
 160   GNUNET_log_setup ("test-regex",
 161 #if VERBOSE
 162                     "DEBUG",
 163 #else
 164                     "WARNING",
 165 #endif
 166                     NULL);
 167
 168   int error;
 169
 170   error = 0;
 171
 172   error += test_proofs_static ();
 173   /* error += test_proofs_random (10000, 10); */
 174
 175   return error;
 176 }