[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r20902 - gnunet/src/regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r20902 - gnunet/src/regex |
Date: |
Thu, 5 Apr 2012 13:46:24 +0200 |
Author: szengel
Date: 2012-04-05 13:46:24 +0200 (Thu, 05 Apr 2012)
New Revision: 20902
Modified:
gnunet/src/regex/regex.c
gnunet/src/regex/test_regex.c
Log:
Automatic regex generation for testing
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-04-05 10:16:53 UTC (rev 20901)
+++ gnunet/src/regex/regex.c 2012-04-05 11:46:24 UTC (rev 20902)
@@ -416,6 +416,15 @@
return s;
}
+/**
+ * Move from the given state 's' to the next state on
+ * transition 'literal'
+ *
+ * @param s starting state
+ * @param literal edge label to follow
+ *
+ * @return new state or NULL, if transition on literal not possible
+ */
static struct State *
dfa_move (struct State *s, const char literal)
{
@@ -439,6 +448,12 @@
return new_s;
}
+/**
+ * Remove all unreachable states from DFA 'a'. Unreachable states
+ * are those states that are not reachable from the starting state.
+ *
+ * @param a DFA automaton
+ */
static void
dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
{
@@ -472,6 +487,12 @@
*/
}
+/**
+ * Remove all dead states from the DFA 'a'. Dead states are those
+ * states that do not transition to any other state but themselfes.
+ *
+ * @param a DFA automaton
+ */
static void
dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
{
@@ -520,12 +541,23 @@
}
}
+/**
+ * Merge all non distinguishable states in the DFA 'a'
+ *
+ * @param a DFA automaton
+ */
static void
dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Automaton *a)
{
}
+/**
+ * Minimize the given DFA 'a' by removing all unreachable states,
+ * removing all dead states and merging all non distinguishable states
+ *
+ * @param a DFA automaton
+ */
static void
dfa_minimize (struct GNUNET_REGEX_Automaton *a)
{
@@ -1029,10 +1061,6 @@
goto error;
}
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "Created NFA with %i States and a total of %i Transitions\n",
- ctx.state_id, ctx.transition_id);
-
return nfa;
error:
@@ -1156,9 +1184,6 @@
dfa_minimize (dfa);
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
- ctx.state_id);
-
return dfa;
}
Modified: gnunet/src/regex/test_regex.c
===================================================================
--- gnunet/src/regex/test_regex.c 2012-04-05 10:16:53 UTC (rev 20901)
+++ gnunet/src/regex/test_regex.c 2012-04-05 11:46:24 UTC (rev 20902)
@@ -23,7 +23,7 @@
* @author Maximilian Szengel
*/
#include <regex.h>
-
+#include <time.h>
#include "platform.h"
#include "gnunet_regex_lib.h"
@@ -36,44 +36,164 @@
struct Regex_String_Pair
{
char *regex;
- char *string;
- enum Match_Result expected_result;
+ int string_count;
+ char **strings;
+ enum Match_Result *expected_results;
};
-
int
-test_automaton (struct GNUNET_REGEX_Automaton *a, struct Regex_String_Pair
*rxstr)
+test_random (unsigned int rx_length, unsigned int max_str_len, unsigned int
str_count)
{
+ int i;
+ int rx_exp;
+ char rand_rx[rx_length+1];
+ char matching_str[str_count][max_str_len+1];
+ char *rand_rxp;
+ char *matching_strp;
+ int char_op_switch;
+ int last_was_op;
+ char current_char;
+ int eval;
+ int eval_check;
+ struct GNUNET_REGEX_Automaton *dfa;
regex_t rx;
+ regmatch_t matchptr[1];
+ int char_offset;
+ char error[200];
int result;
+
+ // At least one string is needed for matching
+ GNUNET_assert (str_count > 0);
+ // The string should be at least as long as the regex itself
+ GNUNET_assert (max_str_len >= rx_length);
+
+ rand_rxp = rand_rx;
+ matching_strp = matching_str[0];
+
+ // Generate random regex and a string that matches the regex
+ for (i=0; i<rx_length; i++)
+ {
+ char_op_switch = 0 + (int)(1.0 * rand() / (RAND_MAX + 1.0));
+ char_offset = (rand()%2) ? 65 : 97;
+
+ if (0 == char_op_switch
+ && !last_was_op)
+ {
+ last_was_op = 1;
+ rx_exp = rand () % 3;
+
+ switch (rx_exp)
+ {
+ case 0:
+ current_char = '+';
+ break;
+ case 1:
+ current_char = '*';
+ break;
+ case 2:
+ if (i < rx_length -1)
+ current_char = '|';
+ else
+ current_char = (char)(char_offset + (int)( 25.0 * rand() /
(RAND_MAX + 1.0)));
+ break;
+ }
+ }
+ else
+ {
+ current_char = (char)(char_offset + (int)( 25.0 * rand() / (RAND_MAX +
1.0)));
+ last_was_op = 0;
+ }
+
+ if (current_char != '+'
+ && current_char != '*'
+ && current_char != '|')
+ {
+ *matching_strp = current_char;
+ matching_strp++;
+ }
+
+ *rand_rxp = current_char;
+ rand_rxp++;
+ }
+ *rand_rxp = '\0';
+ *matching_strp = '\0';
+
+ result = 0;
+
+ for (i=0; i<str_count; i++)
+ {
+ // Match string using DFA
+ dfa = GNUNET_REGEX_construct_dfa (rand_rx, strlen (rand_rx));
+ if (NULL == dfa)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n");
+ return -1;
+ }
+
+ eval = GNUNET_REGEX_eval (dfa, matching_str[i]);
+ GNUNET_REGEX_automaton_destroy (dfa);
+
+ // Match string using glibc regex
+ if (0 != regcomp (&rx, rand_rx, REG_EXTENDED))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not compile regex using
regcomp\n");
+ return -1;
+ }
+
+ eval_check = regexec (&rx, matching_str[i], 1, matchptr, 0);
+
+ // We only want to match the whole string, because that's what our DFA
does, too.
+ if (eval_check == 0 && (matchptr[0].rm_so != 0 || matchptr[0].rm_eo !=
strlen (matching_str[i])))
+ eval_check = 1;
+
+ // compare result
+ if (eval_check != eval)
+ {
+ regerror (eval_check, &rx, error, sizeof error);
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Unexpected result:\nregex: %s\nstring: %s\ngnunet regex:
%i\nglibc regex: %i\nglibc error: %s\n\n",
+ rand_rx, matching_str, eval, eval_check, error);
+ result += 1;
+ }
+ }
+ return result;
+}
+
+int
+test_automaton (struct GNUNET_REGEX_Automaton *a, regex_t *rx, struct
Regex_String_Pair *rxstr)
+{
+ int result;
int eval;
int eval_check;
+ char error[200];
+ int i;
if (NULL == a)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Automaton was NULL\n");
return 1;
+ }
result = 0;
- eval = GNUNET_REGEX_eval (a, rxstr->string);
- regcomp (&rx, rxstr->regex, REG_EXTENDED);
- eval_check = regexec (&rx, rxstr->string, 0, NULL, 0);
+ for (i=0; i<rxstr->string_count; i++)
+ {
+ eval = GNUNET_REGEX_eval (a, rxstr->strings[i]);
+ eval_check = regexec (rx, rxstr->strings[i], 0, NULL, 0);
- if ((rxstr->expected_result == match
- && (0 != eval || 0 != eval_check))
- ||
- (rxstr->expected_result == nomatch
- && (0 == eval || 0 == eval_check)))
- {
- result = 1;
- char error[200];
- regerror (eval_check, &rx, error, sizeof error);
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Unexpected result:\nregex: %s\nstring: %s\nexpected result:
%i\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n",
- rxstr->regex, rxstr->string, rxstr->expected_result, eval,
eval_check, error);
+ if ((rxstr->expected_results[i] == match
+ && (0 != eval || 0 != eval_check))
+ ||
+ (rxstr->expected_results[i] == nomatch
+ && (0 == eval || 0 == eval_check)))
+ {
+ result = 1;
+ regerror (eval_check, rx, error, sizeof error);
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Unexpected result:\nregex: %s\nstring: %s\nexpected
result: %i\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n",
+ rxstr->regex, rxstr->strings[i],
rxstr->expected_results[i], eval, eval_check, error);
+ }
}
-
- regfree (&rx);
-
return result;
}
@@ -90,34 +210,55 @@
int check_nfa;
int check_dfa;
+ int check_rand;
struct Regex_String_Pair rxstr[3];
struct GNUNET_REGEX_Automaton *a;
+ regex_t rx;
int i;
+ check_nfa = 0;
+ check_dfa = 0;
+ check_rand = 0;
+
rxstr[0].regex = "ab(c|d)+c*(a(b|c)d)+";
- rxstr[0].string = "abcdcdcdcdddddabd";
- rxstr[0].expected_result = match;
+ rxstr[0].string_count = 5;
+ rxstr[0].strings = GNUNET_malloc (sizeof (char *) * rxstr[0].string_count);
+ rxstr[0].strings[0] = "abcdcdcdcdddddabd";
+ rxstr[0].strings[1] = "abcd";
+ rxstr[0].strings[2] = "abcddddddccccccccccccccccccccccccabdacdabd";
+ rxstr[0].strings[3] = "abccccca";
+ rxstr[0].strings[4] = "abcdcdcdccdabdabd";
+ rxstr[0].expected_results = GNUNET_malloc (sizeof (enum Match_Result) *
rxstr[0].string_count);
+ rxstr[0].expected_results[0] = match;
+ rxstr[0].expected_results[1] = nomatch;
+ rxstr[0].expected_results[2] = match;
+ rxstr[0].expected_results[3] = nomatch;
+ rxstr[0].expected_results[4] = match;
- rxstr[1].regex = "a*";
- rxstr[1].string = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
- rxstr[1].expected_result = match;
+ for (i=0; i<1; i++)
+ {
+ if (0 != regcomp (&rx, rxstr->regex, REG_EXTENDED | REG_NOSUB))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not compile regex using
regcomp()\n");
+ return 1;
+ }
- rxstr[2].regex = "a*b*c*d+";
- rxstr[2].string = "a";
- rxstr[2].expected_result = nomatch;
-
- for (i=0; i<3; i++)
- {
// NFA test
a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex));
- check_nfa += test_automaton (a, &rxstr[i]);
+ check_nfa += test_automaton (a, &rx, &rxstr[i]);
GNUNET_REGEX_automaton_destroy (a);
// DFA test
a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
- check_dfa += test_automaton (a, &rxstr[i]);
+ check_dfa += test_automaton (a, &rx, &rxstr[i]);
GNUNET_REGEX_automaton_destroy (a);
+
+ regfree (&rx);
}
- return check_nfa + check_dfa;
+ srand (time(NULL));
+ for (i=0; i< 100; i++)
+ check_rand += test_random (100, 100, 1);
+
+ return check_nfa + check_dfa + check_rand;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r20902 - gnunet/src/regex,
gnunet <=