[GNUnet-SVN] r20902 - gnunet/src/regex

[gnunet]

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;
 }