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