diff options
-rw-r--r-- | src/include/gnunet_regex_lib.h | 2 | ||||
-rw-r--r-- | src/regex/Makefile.am | 2 | ||||
-rw-r--r-- | src/regex/regex.c | 24 | ||||
-rw-r--r-- | src/regex/regex.h | 29 | ||||
-rw-r--r-- | src/regex/test_regex.c | 115 |
5 files changed, 92 insertions, 80 deletions
diff --git a/src/include/gnunet_regex_lib.h b/src/include/gnunet_regex_lib.h index 1138ad4ca..bd458478b 100644 --- a/src/include/gnunet_regex_lib.h +++ b/src/include/gnunet_regex_lib.h | |||
@@ -89,7 +89,7 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
89 | * @param a automaton | 89 | * @param a automaton |
90 | * @param string string to check | 90 | * @param string string to check |
91 | * | 91 | * |
92 | * @return GNUNET_YES if 'a' matches 'string', GNUNET_NO otherwise | 92 | * @return 0 if string matches, non 0 otherwise |
93 | */ | 93 | */ |
94 | int | 94 | int |
95 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, | 95 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, |
diff --git a/src/regex/Makefile.am b/src/regex/Makefile.am index 729773399..7b9d31095 100644 --- a/src/regex/Makefile.am +++ b/src/regex/Makefile.am | |||
@@ -11,7 +11,7 @@ endif | |||
11 | lib_LTLIBRARIES = libgnunetregex.la | 11 | lib_LTLIBRARIES = libgnunetregex.la |
12 | 12 | ||
13 | libgnunetregex_la_SOURCES = \ | 13 | libgnunetregex_la_SOURCES = \ |
14 | regex.c regex.h | 14 | regex.c |
15 | libgnunetregex_la_LIBADD = -lm \ | 15 | libgnunetregex_la_LIBADD = -lm \ |
16 | $(top_builddir)/src/util/libgnunetutil.la | 16 | $(top_builddir)/src/util/libgnunetutil.la |
17 | libgnunetregex_la_LDFLAGS = \ | 17 | libgnunetregex_la_LDFLAGS = \ |
diff --git a/src/regex/regex.c b/src/regex/regex.c index a524ace29..6432075a5 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -721,7 +721,10 @@ nfa_closure_set_create (struct StateSet *states, const char literal) | |||
721 | for (k = 0; k < cls->len; k++) | 721 | for (k = 0; k < cls->len; k++) |
722 | { | 722 | { |
723 | if (sset->states[j]->id == cls->states[k]->id) | 723 | if (sset->states[j]->id == cls->states[k]->id) |
724 | { | ||
724 | contains = 1; | 725 | contains = 1; |
726 | break; | ||
727 | } | ||
725 | } | 728 | } |
726 | if (!contains) | 729 | if (!contains) |
727 | GNUNET_array_append (cls->states, cls->len, sset->states[j]); | 730 | GNUNET_array_append (cls->states, cls->len, sset->states[j]); |
@@ -1249,7 +1252,7 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
1249 | * @param a automaton, type must be DFA | 1252 | * @param a automaton, type must be DFA |
1250 | * @param string string that should be evaluated | 1253 | * @param string string that should be evaluated |
1251 | * | 1254 | * |
1252 | * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise | 1255 | * @return 0 if string matches, non 0 otherwise |
1253 | */ | 1256 | */ |
1254 | static int | 1257 | static int |
1255 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 1258 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
@@ -1261,7 +1264,7 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1261 | { | 1264 | { |
1262 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 1265 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
1263 | "Tried to evaluate DFA, but NFA automaton given"); | 1266 | "Tried to evaluate DFA, but NFA automaton given"); |
1264 | return GNUNET_SYSERR; | 1267 | return -1; |
1265 | } | 1268 | } |
1266 | 1269 | ||
1267 | s = a->start; | 1270 | s = a->start; |
@@ -1274,9 +1277,9 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1274 | } | 1277 | } |
1275 | 1278 | ||
1276 | if (NULL != s && s->accepting) | 1279 | if (NULL != s && s->accepting) |
1277 | return GNUNET_YES; | 1280 | return 0; |
1278 | 1281 | ||
1279 | return GNUNET_NO; | 1282 | return 1; |
1280 | } | 1283 | } |
1281 | 1284 | ||
1282 | /** | 1285 | /** |
@@ -1285,7 +1288,7 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1285 | * @param a automaton, type must be NFA | 1288 | * @param a automaton, type must be NFA |
1286 | * @param string string that should be evaluated | 1289 | * @param string string that should be evaluated |
1287 | * | 1290 | * |
1288 | * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise | 1291 | * @return 0 if string matches, non 0 otherwise |
1289 | */ | 1292 | */ |
1290 | static int | 1293 | static int |
1291 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 1294 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
@@ -1301,13 +1304,12 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1301 | { | 1304 | { |
1302 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 1305 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
1303 | "Tried to evaluate NFA, but DFA automaton given"); | 1306 | "Tried to evaluate NFA, but DFA automaton given"); |
1304 | return GNUNET_SYSERR; | 1307 | return -1; |
1305 | } | 1308 | } |
1306 | 1309 | ||
1307 | result = GNUNET_NO; | 1310 | result = 1; |
1308 | strp = string; | 1311 | strp = string; |
1309 | sset = GNUNET_malloc (sizeof (struct StateSet)); | 1312 | sset = nfa_closure_create (a->start, 0); |
1310 | GNUNET_array_append (sset->states, sset->len, a->start); | ||
1311 | 1313 | ||
1312 | for (strp = string; NULL != strp && *strp; strp++) | 1314 | for (strp = string; NULL != strp && *strp; strp++) |
1313 | { | 1315 | { |
@@ -1322,7 +1324,7 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1322 | s = sset->states[i]; | 1324 | s = sset->states[i]; |
1323 | if (NULL != s && s->accepting) | 1325 | if (NULL != s && s->accepting) |
1324 | { | 1326 | { |
1325 | result = GNUNET_YES; | 1327 | result = 0; |
1326 | break; | 1328 | break; |
1327 | } | 1329 | } |
1328 | } | 1330 | } |
@@ -1338,7 +1340,7 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1338 | * @param a automaton | 1340 | * @param a automaton |
1339 | * @param string string to check | 1341 | * @param string string to check |
1340 | * | 1342 | * |
1341 | * @return GNUNET_YES if 'a' matches 'string', GNUNET_NO otherwise | 1343 | * @return 0 if string matches, non 0 otherwise |
1342 | */ | 1344 | */ |
1343 | int | 1345 | int |
1344 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string) | 1346 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string) |
diff --git a/src/regex/regex.h b/src/regex/regex.h deleted file mode 100644 index 4f8c3853b..000000000 --- a/src/regex/regex.h +++ /dev/null | |||
@@ -1,29 +0,0 @@ | |||
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 src/regex/regex.h | ||
22 | * @brief library to create automatons from regular expressions | ||
23 | * @author Maximilian Szengel | ||
24 | */ | ||
25 | #ifndef REGEX_H | ||
26 | #define REGEX_H | ||
27 | #include "gnunet_regex_lib.h" | ||
28 | |||
29 | #endif | ||
diff --git a/src/regex/test_regex.c b/src/regex/test_regex.c index 6835d1b83..7428c001e 100644 --- a/src/regex/test_regex.c +++ b/src/regex/test_regex.c | |||
@@ -22,10 +22,60 @@ | |||
22 | * @brief test for regex.c | 22 | * @brief test for regex.c |
23 | * @author Maximilian Szengel | 23 | * @author Maximilian Szengel |
24 | */ | 24 | */ |
25 | #include <regex.h> | ||
26 | |||
25 | #include "platform.h" | 27 | #include "platform.h" |
26 | #include "gnunet_regex_lib.h" | 28 | #include "gnunet_regex_lib.h" |
27 | 29 | ||
28 | static int err = 0; | 30 | enum Match_Result |
31 | { | ||
32 | match = 0, | ||
33 | nomatch = 1 | ||
34 | }; | ||
35 | |||
36 | struct Regex_String_Pair | ||
37 | { | ||
38 | char *regex; | ||
39 | char *string; | ||
40 | enum Match_Result expected_result; | ||
41 | }; | ||
42 | |||
43 | |||
44 | int | ||
45 | test_automaton (struct GNUNET_REGEX_Automaton *a, struct Regex_String_Pair *rxstr) | ||
46 | { | ||
47 | regex_t rx; | ||
48 | int result; | ||
49 | int eval; | ||
50 | int eval_check; | ||
51 | |||
52 | if (NULL == a) | ||
53 | return 1; | ||
54 | |||
55 | result = 0; | ||
56 | |||
57 | eval = GNUNET_REGEX_eval (a, rxstr->string); | ||
58 | regcomp (&rx, rxstr->regex, REG_EXTENDED); | ||
59 | eval_check = regexec (&rx, rxstr->string, 0, NULL, 0); | ||
60 | |||
61 | if ((rxstr->expected_result == match | ||
62 | && (0 != eval || 0 != eval_check)) | ||
63 | || | ||
64 | (rxstr->expected_result == nomatch | ||
65 | && (0 == eval || 0 == eval_check))) | ||
66 | { | ||
67 | result = 1; | ||
68 | char error[200]; | ||
69 | regerror (eval_check, &rx, error, sizeof error); | ||
70 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
71 | "Unexpected result:\nregex: %s\nstring: %s\nexpected result: %i\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n", | ||
72 | rxstr->regex, rxstr->string, rxstr->expected_result, eval, eval_check, error); | ||
73 | } | ||
74 | |||
75 | regfree (&rx); | ||
76 | |||
77 | return result; | ||
78 | } | ||
29 | 79 | ||
30 | int | 80 | int |
31 | main (int argc, char *argv[]) | 81 | main (int argc, char *argv[]) |
@@ -38,47 +88,36 @@ main (int argc, char *argv[]) | |||
38 | #endif | 88 | #endif |
39 | NULL); | 89 | NULL); |
40 | 90 | ||
41 | struct GNUNET_REGEX_Automaton *nfa; | 91 | int check_nfa; |
42 | struct GNUNET_REGEX_Automaton *dfa; | 92 | int check_dfa; |
43 | char *regex; | 93 | struct Regex_String_Pair rxstr[3]; |
44 | char *string; | 94 | struct GNUNET_REGEX_Automaton *a; |
45 | int eval; | 95 | int i; |
46 | 96 | ||
47 | nfa = NULL; | 97 | rxstr[0].regex = "ab(c|d)+c*(a(b|c)d)+"; |
48 | dfa = NULL; | 98 | rxstr[0].string = "abcdcdcdcdddddabd"; |
99 | rxstr[0].expected_result = match; | ||
49 | 100 | ||
50 | regex = "a\\*b(c|d)+c*(a(b|c)d)+"; | 101 | rxstr[1].regex = "a*"; |
51 | string = "a*bcdcdcdcdddddabd"; | 102 | rxstr[1].string = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; |
52 | /*regex = "VPN TCP (IPv4|IPv6) Port53"; */ | 103 | rxstr[1].expected_result = match; |
53 | /*string = "VPN TCP IPv4 Port53"; */ | ||
54 | /*regex = "\\*a(a|b)b"; */ | ||
55 | /*regex = "a(a|b)c"; */ | ||
56 | /*regex = "(a|aa)+"; */ | ||
57 | nfa = GNUNET_REGEX_construct_nfa (regex, strlen (regex)); | ||
58 | 104 | ||
59 | if (nfa) | 105 | rxstr[2].regex = "a*b*c*d+"; |
60 | { | 106 | rxstr[2].string = "a"; |
61 | GNUNET_REGEX_automaton_save_graph (nfa, "nfa_graph.dot"); | 107 | rxstr[2].expected_result = nomatch; |
62 | eval = GNUNET_REGEX_eval (nfa, string); | ||
63 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Evaluating %s result: %i\n", string, | ||
64 | eval); | ||
65 | if (GNUNET_YES != eval) | ||
66 | err = 1; | ||
67 | GNUNET_REGEX_automaton_destroy (nfa); | ||
68 | } | ||
69 | else | ||
70 | err = 1; | ||
71 | 108 | ||
72 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex)); | 109 | for (i=0; i<3; i++) |
73 | if (dfa) | ||
74 | { | 110 | { |
75 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa_graph.dot"); | 111 | // NFA test |
76 | eval = GNUNET_REGEX_eval (dfa, string); | 112 | a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex)); |
77 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Evaluating %s result: %i\n", string, | 113 | check_nfa += test_automaton (a, &rxstr[i]); |
78 | eval); | 114 | GNUNET_REGEX_automaton_destroy (a); |
79 | if (GNUNET_YES != eval) | 115 | |
80 | err = 1; | 116 | // DFA test |
81 | GNUNET_REGEX_automaton_destroy (dfa); | 117 | a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex)); |
118 | check_dfa += test_automaton (a, &rxstr[i]); | ||
119 | GNUNET_REGEX_automaton_destroy (a); | ||
82 | } | 120 | } |
83 | return err; | 121 | |
122 | return check_nfa + check_dfa; | ||
84 | } | 123 | } |