src/regex/test_regex_proofs.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2012 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18 /**
  19  * @file regex/test_regex_proofs.c
  20  * @brief test for regex.c
  21  * @author Maximilian Szengel
  22  */
  23 #include "platform.h"
  24 #include "regex_internal_lib.h"
  25 #include "regex_test_lib.h"
  26 #include "regex_internal.h"
  27
  28
  29 /**
  30  * Test if the given regex's canonical regex is the same as this canonical
  31  * regex's canonical regex. Confused? Ok, then: 1. construct a dfa A from the
  32  * given 'regex' 2. get the canonical regex of dfa A 3. construct a dfa B from
  33  * this canonical regex 3. compare the canonical regex of dfa A with the
  34  * canonical regex of dfa B.
  35  *
  36  * @param regex regular expression used for this test (see above).
  37  *
  38  * @return 0 on success, 1 on failure
  39  */
  40 static unsigned int
  41 test_proof (const char *regex)
  42 {
  43   unsigned int error;
  44   struct REGEX_INTERNAL_Automaton *dfa;
  45   char *c_rx1;
  46   const char *c_rx2;
  47
  48   dfa = REGEX_INTERNAL_construct_dfa (regex, strlen (regex), 1);
  49   GNUNET_assert (NULL != dfa);
  50   c_rx1 = GNUNET_strdup (REGEX_INTERNAL_get_canonical_regex (dfa));
  51   REGEX_INTERNAL_automaton_destroy (dfa);
  52   dfa = REGEX_INTERNAL_construct_dfa (c_rx1, strlen (c_rx1), 1);
  53   GNUNET_assert (NULL != dfa);
  54   c_rx2 = REGEX_INTERNAL_get_canonical_regex (dfa);
  55
  56   error = (0 == strcmp (c_rx1, c_rx2)) ? 0 : 1;
  57
  58   if (error > 0)
  59   {
  60     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
  61                 "Comparing canonical regex of\n%s\nfailed:\n%s\nvs.\n%s\n",
  62                 regex, c_rx1, c_rx2);
  63   }
  64
  65   GNUNET_free (c_rx1);
  66   REGEX_INTERNAL_automaton_destroy (dfa);
  67
  68   return error;
  69 }
  70
  71
  72 /**
  73  * Use 'test_proof' function to randomly test the canonical regexes of 'count'
  74  * random expressions of length 'rx_length'.
  75  *
  76  * @param count number of random regular expressions to test.
  77  * @param rx_length length of the random regular expressions.
  78  *
  79  * @return 0 on succes, number of failures otherwise.
  80  */
  81 static unsigned int
  82 test_proofs_random (unsigned int count, size_t rx_length)
  83 {
  84   unsigned int i;
  85   char *rand_rx;
  86   unsigned int failures;
  87
  88   failures = 0;
  89
  90   for (i = 0; i < count; i++)
  91   {
  92     rand_rx = REGEX_TEST_generate_random_regex (rx_length, NULL);
  93     failures += test_proof (rand_rx);
  94     GNUNET_free (rand_rx);
  95   }
  96
  97   return failures;
  98 }
  99
 100
 101 /**
 102  * Test a number of known examples of regexes for proper canonicalization.
 103  *
 104  * @return 0 on success, number of failures otherwise.
 105  */
 106 static unsigned int
 107 test_proofs_static ()
 108 {
 109   unsigned int i;
 110   unsigned int error;
 111
 112   const char *regex[8] = {
 113     "a|aa*a",
 114     "a+",
 115     "a*",
 116     "a*a*",
 117     "(F*C|WfPf|y+F*C)",
 118     "y*F*C|WfPf",
 119     "((a|b)c|(a|b)(d|(a|b)e))",
 120     "((a|b)(c|d)|(a|b)(a|b)e)"
 121   };
 122
 123   const char *canon_rx1;
 124   const char *canon_rx2;
 125   struct REGEX_INTERNAL_Automaton *dfa1;
 126   struct REGEX_INTERNAL_Automaton *dfa2;
 127
 128   error = 0;
 129
 130   for (i = 0; i < 8; i += 2)
 131   {
 132     dfa1 = REGEX_INTERNAL_construct_dfa (regex[i], strlen (regex[i]), 1);
 133     dfa2 = REGEX_INTERNAL_construct_dfa (regex[i + 1], strlen (regex[i + 1]), 1);
 134     GNUNET_assert (NULL != dfa1);
 135     GNUNET_assert (NULL != dfa2);
 136
 137     canon_rx1 = REGEX_INTERNAL_get_canonical_regex (dfa1);
 138     canon_rx2 = REGEX_INTERNAL_get_canonical_regex (dfa2);
 139
 140     error += (0 == strcmp (canon_rx1, canon_rx2)) ? 0 : 1;
 141
 142     if (error > 0)
 143     {
 144       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 145                   "Comparing canonical regex failed:\nrx1:\t%s\ncrx1:\t%s\nrx2:\t%s\ncrx2:\t%s\n",
 146                   regex[i], canon_rx1, regex[i + 1], canon_rx2);
 147     }
 148
 149     REGEX_INTERNAL_automaton_destroy (dfa1);
 150     REGEX_INTERNAL_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", "WARNING", NULL);
 161
 162   int error;
 163
 164   error = 0;
 165
 166   error += test_proofs_static ();
 167   error += test_proofs_random (100, 30);
 168
 169   return error;
 170 }