/*
This file is part of GNUnet
- (C) 2012 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2012 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
/**
* @file regex/test_regex_proofs.c
* @brief test for regex.c
* @author Maximilian Szengel
*/
-#include <regex.h>
-#include <time.h>
#include "platform.h"
-#include "gnunet_regex_lib.h"
+#include "regex_internal_lib.h"
+#include "regex_test_lib.h"
+#include "regex_internal.h"
-int
-main (int argc, char *argv[])
+
+/**
+ * Test if the given regex's canonical regex is the same as this canonical
+ * regex's canonical regex. Confused? Ok, then: 1. construct a dfa A from the
+ * given 'regex' 2. get the canonical regex of dfa A 3. construct a dfa B from
+ * this canonical regex 3. compare the canonical regex of dfa A with the
+ * canonical regex of dfa B.
+ *
+ * @param regex regular expression used for this test (see above).
+ *
+ * @return 0 on success, 1 on failure
+ */
+static unsigned int
+test_proof (const char *regex)
{
- GNUNET_log_setup ("test-regex",
-#if VERBOSE
- "DEBUG",
-#else
- "WARNING",
-#endif
- NULL);
+ unsigned int error;
+ struct REGEX_INTERNAL_Automaton *dfa;
+ char *c_rx1;
+ const char *c_rx2;
- int error;
- int i;
- const char *regex[21] = {
- "ab(c|d)+c*(a(b|c)+d)+(bla)+",
- "(bla)*",
- "b(lab)*la",
- "(ab)*",
- "ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*",
- "z(abc|def)?xyz",
- "1*0(0|1)*",
- "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*",
- "(cd|ab)*",
- "abcd:(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1):(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)",
- "abc(1|0)*def",
- "ab|ac",
- "(ab)(ab)*",
- "ab|cd|ef|gh",
- "a|b|c|d|e|f|g",
- "(ab)|(ac)",
- "a(b|c)",
- "a*a",
- "ab?(abcd)?",
- "(ab|cs|df|sdf)*",
- "a|aa*a"
+ dfa = REGEX_INTERNAL_construct_dfa (regex, strlen (regex), 1);
+ GNUNET_assert (NULL != dfa);
+ c_rx1 = GNUNET_strdup (REGEX_INTERNAL_get_canonical_regex (dfa));
+ REGEX_INTERNAL_automaton_destroy (dfa);
+ dfa = REGEX_INTERNAL_construct_dfa (c_rx1, strlen (c_rx1), 1);
+ GNUNET_assert (NULL != dfa);
+ c_rx2 = REGEX_INTERNAL_get_canonical_regex (dfa);
+
+ error = (0 == strcmp (c_rx1, c_rx2)) ? 0 : 1;
+
+ if (error > 0)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Comparing canonical regex of\n%s\nfailed:\n%s\nvs.\n%s\n",
+ regex, c_rx1, c_rx2);
+ }
+
+ GNUNET_free (c_rx1);
+ REGEX_INTERNAL_automaton_destroy (dfa);
+
+ return error;
+}
+
+
+/**
+ * Use 'test_proof' function to randomly test the canonical regexes of 'count'
+ * random expressions of length 'rx_length'.
+ *
+ * @param count number of random regular expressions to test.
+ * @param rx_length length of the random regular expressions.
+ *
+ * @return 0 on succes, number of failures otherwise.
+ */
+static unsigned int
+test_proofs_random (unsigned int count, size_t rx_length)
+{
+ unsigned int i;
+ char *rand_rx;
+ unsigned int failures;
+
+ failures = 0;
+
+ for (i = 0; i < count; i++)
+ {
+ rand_rx = REGEX_TEST_generate_random_regex (rx_length, NULL);
+ failures += test_proof (rand_rx);
+ GNUNET_free (rand_rx);
+ }
+
+ return failures;
+}
+
+
+/**
+ * Test a number of known examples of regexes for proper canonicalization.
+ *
+ * @return 0 on success, number of failures otherwise.
+ */
+static unsigned int
+test_proofs_static ()
+{
+ unsigned int i;
+ unsigned int error;
+
+ const char *regex[8] = {
+ "a|aa*a",
+ "a+",
+ "a*",
+ "a*a*",
+ "(F*C|WfPf|y+F*C)",
+ "y*F*C|WfPf",
+ "((a|b)c|(a|b)(d|(a|b)e))",
+ "((a|b)(c|d)|(a|b)(a|b)e)"
};
- char *computed_regex;
- struct GNUNET_REGEX_Automaton *dfa;
+
+ const char *canon_rx1;
+ const char *canon_rx2;
+ struct REGEX_INTERNAL_Automaton *dfa1;
+ struct REGEX_INTERNAL_Automaton *dfa2;
error = 0;
- for (i = 0; i < 21; i++)
+ for (i = 0; i < 8; i += 2)
{
- dfa = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]));
- computed_regex = GNUNET_strdup (GNUNET_REGEX_get_computed_regex (dfa));
- GNUNET_REGEX_automaton_destroy (dfa);
-
- dfa = GNUNET_REGEX_construct_dfa (computed_regex, strlen (computed_regex));
- error += (0 == strcmp (computed_regex, GNUNET_REGEX_get_computed_regex (dfa))) ? 0 : 1;
- GNUNET_free (computed_regex);
- GNUNET_REGEX_automaton_destroy (dfa);
+ dfa1 = REGEX_INTERNAL_construct_dfa (regex[i], strlen (regex[i]), 1);
+ dfa2 = REGEX_INTERNAL_construct_dfa (regex[i + 1], strlen (regex[i + 1]), 1);
+ GNUNET_assert (NULL != dfa1);
+ GNUNET_assert (NULL != dfa2);
+
+ canon_rx1 = REGEX_INTERNAL_get_canonical_regex (dfa1);
+ canon_rx2 = REGEX_INTERNAL_get_canonical_regex (dfa2);
+
+ error += (0 == strcmp (canon_rx1, canon_rx2)) ? 0 : 1;
+
+ if (error > 0)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Comparing canonical regex failed:\nrx1:\t%s\ncrx1:\t%s\nrx2:\t%s\ncrx2:\t%s\n",
+ regex[i], canon_rx1, regex[i + 1], canon_rx2);
+ }
+
+ REGEX_INTERNAL_automaton_destroy (dfa1);
+ REGEX_INTERNAL_automaton_destroy (dfa2);
}
-
+
+ return error;
+}
+
+
+int
+main (int argc, char *argv[])
+{
+ GNUNET_log_setup ("test-regex", "WARNING", NULL);
+
+ int error;
+
+ error = 0;
+
+ error += test_proofs_static ();
+ error += test_proofs_random (100, 30);
+
return error;
}