missing fi
[oweals/gnunet.git] / 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 "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 }