diff options
-rw-r--r-- | src/regex/regex.c | 243 | ||||
-rw-r--r-- | src/regex/test_regex_eval_api.c | 17 | ||||
-rw-r--r-- | src/regex/test_regex_iterate_api.c | 22 |
3 files changed, 227 insertions, 55 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 6a8420ac8..814ae5597 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -205,6 +205,16 @@ struct GNUNET_REGEX_State | |||
205 | struct Transition *transitions_tail; | 205 | struct Transition *transitions_tail; |
206 | 206 | ||
207 | /** | 207 | /** |
208 | * Number of incoming transitions. | ||
209 | */ | ||
210 | unsigned int incoming_transition_count; | ||
211 | |||
212 | /** | ||
213 | * Set of incoming transitions. | ||
214 | */ | ||
215 | struct Transition **incoming_transitions; | ||
216 | |||
217 | /** | ||
208 | * Set of states on which this state is based on. Used when creating a DFA out | 218 | * Set of states on which this state is based on. Used when creating a DFA out |
209 | * of several NFA states. | 219 | * of several NFA states. |
210 | */ | 220 | */ |
@@ -267,10 +277,17 @@ struct GNUNET_REGEX_StateSet | |||
267 | static void | 277 | static void |
268 | debug_print_state (struct GNUNET_REGEX_State *s) | 278 | debug_print_state (struct GNUNET_REGEX_State *s) |
269 | { | 279 | { |
280 | char *proof; | ||
281 | |||
282 | if (NULL == s->proof) | ||
283 | proof = "NULL"; | ||
284 | else | ||
285 | proof = s->proof; | ||
286 | |||
270 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 287 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
271 | "State %i: %s marked: %i accepting: %i scc_id: %i transitions: %i\n", | 288 | "State %i: %s marked: %i accepting: %i scc_id: %i transitions: %i proof: %s\n", |
272 | s->id, s->name, s->marked, s->accepting, s->scc_id, | 289 | s->id, s->name, s->marked, s->accepting, s->scc_id, |
273 | s->transition_count); | 290 | s->transition_count, proof); |
274 | } | 291 | } |
275 | 292 | ||
276 | static void | 293 | static void |
@@ -287,27 +304,41 @@ debug_print_states (struct GNUNET_REGEX_StateSet *sset) | |||
287 | } | 304 | } |
288 | 305 | ||
289 | static void | 306 | static void |
290 | debug_print_transitions (struct GNUNET_REGEX_State *s) | 307 | debug_print_transition (struct Transition *t) |
291 | { | 308 | { |
292 | struct Transition *t; | 309 | char *to_state; |
293 | char *state; | 310 | char *from_state; |
294 | char label; | 311 | char label; |
295 | 312 | ||
296 | for (t = s->transitions_head; NULL != t; t = t->next) | 313 | if (NULL == t) |
297 | { | 314 | return; |
298 | if (0 == t->label) | ||
299 | label = '0'; | ||
300 | else | ||
301 | label = t->label; | ||
302 | 315 | ||
303 | if (NULL == t->to_state) | 316 | if (0 == t->label) |
304 | state = "NULL"; | 317 | label = '0'; |
305 | else | 318 | else |
306 | state = t->to_state->name; | 319 | label = t->label; |
307 | 320 | ||
308 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id, | 321 | if (NULL == t->to_state) |
309 | label, state); | 322 | to_state = "NULL"; |
310 | } | 323 | else |
324 | to_state = t->to_state->name; | ||
325 | |||
326 | if (NULL == t->from_state) | ||
327 | from_state = "NULL"; | ||
328 | else | ||
329 | from_state = t->from_state->name; | ||
330 | |||
331 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %c to %s\n", | ||
332 | t->id, from_state, label, to_state); | ||
333 | } | ||
334 | |||
335 | static void | ||
336 | debug_print_transitions (struct GNUNET_REGEX_State *s) | ||
337 | { | ||
338 | struct Transition *t; | ||
339 | |||
340 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
341 | debug_print_transition (t); | ||
311 | } | 342 | } |
312 | 343 | ||
313 | /** | 344 | /** |
@@ -473,6 +504,73 @@ state_compare (const void *a, const void *b) | |||
473 | } | 504 | } |
474 | 505 | ||
475 | /** | 506 | /** |
507 | * Create a proof for the given state. Intended to be used as a parameter for | ||
508 | * automaton_traverse() function. | ||
509 | * | ||
510 | * @param cls closure | ||
511 | * @param s state | ||
512 | */ | ||
513 | void | ||
514 | state_create_proof (void *cls, struct GNUNET_REGEX_State *s) | ||
515 | { | ||
516 | struct Transition *inc_t; | ||
517 | int i; | ||
518 | char *proof = NULL; | ||
519 | char *stars = NULL; | ||
520 | char *tmp = NULL; | ||
521 | |||
522 | for (i = 0; i < s->incoming_transition_count; i++) | ||
523 | { | ||
524 | inc_t = s->incoming_transitions[i]; | ||
525 | |||
526 | if (NULL == inc_t) | ||
527 | continue; | ||
528 | |||
529 | GNUNET_assert (inc_t->label != 0 && inc_t->from_state != NULL); | ||
530 | |||
531 | if (inc_t->from_state == inc_t->to_state) | ||
532 | GNUNET_asprintf (&stars, "%c*", inc_t->label); | ||
533 | else | ||
534 | { | ||
535 | if (NULL != inc_t->from_state->proof) | ||
536 | GNUNET_asprintf (&tmp, "%s%c", inc_t->from_state->proof, inc_t->label); | ||
537 | else | ||
538 | GNUNET_asprintf (&tmp, "%c", inc_t->label); | ||
539 | } | ||
540 | |||
541 | if (i > 0 && NULL != tmp && NULL != proof) | ||
542 | GNUNET_asprintf (&proof, "%s|%s", proof, tmp); | ||
543 | else if (NULL != tmp) | ||
544 | proof = GNUNET_strdup (tmp); | ||
545 | |||
546 | if (NULL != tmp) | ||
547 | { | ||
548 | GNUNET_free (tmp); | ||
549 | tmp = NULL; | ||
550 | } | ||
551 | } | ||
552 | |||
553 | if (NULL != s->proof) | ||
554 | GNUNET_free (s->proof); | ||
555 | |||
556 | if (s->incoming_transition_count > 1) | ||
557 | { | ||
558 | if (NULL != stars) | ||
559 | { | ||
560 | GNUNET_asprintf (&s->proof, "(%s)%s", proof, stars); | ||
561 | GNUNET_free (stars); | ||
562 | } | ||
563 | else if (NULL != proof) | ||
564 | GNUNET_asprintf (&s->proof, "(%s)", proof); | ||
565 | |||
566 | if (NULL != proof) | ||
567 | GNUNET_free (proof); | ||
568 | } | ||
569 | else | ||
570 | s->proof = proof; | ||
571 | } | ||
572 | |||
573 | /** | ||
476 | * Get all edges leaving state 's'. | 574 | * Get all edges leaving state 's'. |
477 | * | 575 | * |
478 | * @param s state. | 576 | * @param s state. |
@@ -596,6 +694,11 @@ automaton_destroy_state (struct GNUNET_REGEX_State *s) | |||
596 | GNUNET_free (t); | 694 | GNUNET_free (t); |
597 | } | 695 | } |
598 | 696 | ||
697 | if (s->incoming_transition_count > 0 && NULL != s->incoming_transitions) | ||
698 | { | ||
699 | GNUNET_free (s->incoming_transitions); | ||
700 | } | ||
701 | |||
599 | state_set_clear (s->nfa_set); | 702 | state_set_clear (s->nfa_set); |
600 | 703 | ||
601 | GNUNET_free (s); | 704 | GNUNET_free (s); |
@@ -661,9 +764,14 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
661 | struct GNUNET_REGEX_State *s_check; | 764 | struct GNUNET_REGEX_State *s_check; |
662 | struct Transition *t_check; | 765 | struct Transition *t_check; |
663 | char *new_name; | 766 | char *new_name; |
767 | int i; | ||
768 | struct Transition *inc_t; | ||
664 | 769 | ||
665 | GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2); | 770 | GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2); |
666 | 771 | ||
772 | if (s1 == s2) | ||
773 | return; | ||
774 | |||
667 | // 1. Make all transitions pointing to s2 point to s1 | 775 | // 1. Make all transitions pointing to s2 point to s1 |
668 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 776 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
669 | { | 777 | { |
@@ -675,14 +783,28 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
675 | } | 783 | } |
676 | } | 784 | } |
677 | 785 | ||
678 | // 2. Add all transitions from s2 to sX to s1 | 786 | // 2. Remove all transitions coming from s2 |
787 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | ||
788 | { | ||
789 | for (i = 0; i < s_check->incoming_transition_count; i++) | ||
790 | { | ||
791 | inc_t = s_check->incoming_transitions[i]; | ||
792 | |||
793 | if (inc_t != 0 && inc_t->from_state == s2) | ||
794 | { | ||
795 | s_check->incoming_transitions[i] = NULL; | ||
796 | } | ||
797 | } | ||
798 | } | ||
799 | |||
800 | // 3. Add all transitions from s2 to sX to s1 | ||
679 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) | 801 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) |
680 | { | 802 | { |
681 | if (t_check->to_state != s1) | 803 | if (t_check->to_state != s1) |
682 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); | 804 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); |
683 | } | 805 | } |
684 | 806 | ||
685 | // 3. Rename s1 to {s1,s2} | 807 | // 4. Rename s1 to {s1,s2} |
686 | new_name = GNUNET_strdup (s1->name); | 808 | new_name = GNUNET_strdup (s1->name); |
687 | if (NULL != s1->name) | 809 | if (NULL != s1->name) |
688 | { | 810 | { |
@@ -713,18 +835,15 @@ automaton_add_state (struct GNUNET_REGEX_Automaton *a, | |||
713 | a->state_count++; | 835 | a->state_count++; |
714 | } | 836 | } |
715 | 837 | ||
838 | /** | ||
839 | * Function that is called with each state, when traversing an automaton. | ||
840 | * | ||
841 | * @param cls closure | ||
842 | * @param s state | ||
843 | */ | ||
716 | typedef void (*GNUNET_REGEX_traverse_action) (void *cls, | 844 | typedef void (*GNUNET_REGEX_traverse_action) (void *cls, |
717 | struct GNUNET_REGEX_State * s); | 845 | struct GNUNET_REGEX_State * s); |
718 | 846 | ||
719 | static void | ||
720 | automaton_state_traverse_backward (void *cls, struct GNUNET_REGEX_State *s, | ||
721 | GNUNET_REGEX_traverse_action action) | ||
722 | { | ||
723 | |||
724 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Traversing backwards...\n"); | ||
725 | |||
726 | } | ||
727 | |||
728 | /** | 847 | /** |
729 | * Traverses all states that are reachable from state 's'. Expects the states to | 848 | * Traverses all states that are reachable from state 's'. Expects the states to |
730 | * be unmarked (s->marked == GNUNET_NO). Performs 'action' on each visited | 849 | * be unmarked (s->marked == GNUNET_NO). Performs 'action' on each visited |
@@ -739,12 +858,21 @@ automaton_state_traverse (void *cls, struct GNUNET_REGEX_State *s, | |||
739 | GNUNET_REGEX_traverse_action action) | 858 | GNUNET_REGEX_traverse_action action) |
740 | { | 859 | { |
741 | struct Transition *t; | 860 | struct Transition *t; |
861 | int i; | ||
742 | 862 | ||
743 | if (GNUNET_NO == s->marked) | 863 | if (GNUNET_NO == s->marked) |
744 | { | 864 | { |
745 | s->marked = GNUNET_YES; | 865 | s->marked = GNUNET_YES; |
746 | 866 | ||
747 | if (NULL != action) | 867 | // First make sure all incoming states have been traversed |
868 | for (i = 0; i < s->incoming_transition_count; i++) | ||
869 | { | ||
870 | if (NULL != s->incoming_transitions[i]) | ||
871 | automaton_state_traverse (cls, s->incoming_transitions[i]->from_state, | ||
872 | action); | ||
873 | } | ||
874 | |||
875 | if (action > 0) | ||
748 | action (cls, s); | 876 | action (cls, s); |
749 | 877 | ||
750 | for (t = s->transitions_head; NULL != t; t = t->next) | 878 | for (t = s->transitions_head; NULL != t; t = t->next) |
@@ -766,7 +894,7 @@ automaton_traverse (void *cls, struct GNUNET_REGEX_Automaton *a, | |||
766 | { | 894 | { |
767 | struct GNUNET_REGEX_State *s; | 895 | struct GNUNET_REGEX_State *s; |
768 | 896 | ||
769 | for (s = a->start; NULL != s; s = s->next) | 897 | for (s = a->states_head; NULL != s; s = s->next) |
770 | s->marked = GNUNET_NO; | 898 | s->marked = GNUNET_NO; |
771 | 899 | ||
772 | automaton_state_traverse (cls, a->start, action); | 900 | automaton_state_traverse (cls, a->start, action); |
@@ -803,6 +931,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
803 | s->index = -1; | 931 | s->index = -1; |
804 | s->lowlink = -1; | 932 | s->lowlink = -1; |
805 | s->contained = 0; | 933 | s->contained = 0; |
934 | s->proof = NULL; | ||
806 | 935 | ||
807 | if (NULL == nfa_states) | 936 | if (NULL == nfa_states) |
808 | { | 937 | { |
@@ -897,7 +1026,6 @@ dfa_move (struct GNUNET_REGEX_State *s, const char label) | |||
897 | return new_s; | 1026 | return new_s; |
898 | } | 1027 | } |
899 | 1028 | ||
900 | |||
901 | /** | 1029 | /** |
902 | * Remove all unreachable states from DFA 'a'. Unreachable states are those | 1030 | * Remove all unreachable states from DFA 'a'. Unreachable states are those |
903 | * states that are not reachable from the starting state. | 1031 | * states that are not reachable from the starting state. |
@@ -922,10 +1050,7 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
922 | { | 1050 | { |
923 | s_next = s->next; | 1051 | s_next = s->next; |
924 | if (GNUNET_NO == s->marked) | 1052 | if (GNUNET_NO == s->marked) |
925 | { | ||
926 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Removed state %s\n", s->name); | ||
927 | automaton_remove_state (a, s); | 1053 | automaton_remove_state (a, s); |
928 | } | ||
929 | } | 1054 | } |
930 | } | 1055 | } |
931 | 1056 | ||
@@ -983,8 +1108,10 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
983 | struct GNUNET_REGEX_State *s2; | 1108 | struct GNUNET_REGEX_State *s2; |
984 | struct Transition *t1; | 1109 | struct Transition *t1; |
985 | struct Transition *t2; | 1110 | struct Transition *t2; |
1111 | struct GNUNET_REGEX_State *s1_next; | ||
1112 | struct GNUNET_REGEX_State *s2_next; | ||
986 | int change; | 1113 | int change; |
987 | int common_labels; | 1114 | int num_equal_edges; |
988 | 1115 | ||
989 | for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1; | 1116 | for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1; |
990 | i++, s1 = s1->next) | 1117 | i++, s1 = s1->next) |
@@ -995,18 +1122,19 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
995 | // Mark all pairs of accepting/!accepting states | 1122 | // Mark all pairs of accepting/!accepting states |
996 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) | 1123 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) |
997 | { | 1124 | { |
998 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next) | 1125 | for (s2 = a->states_head; NULL != s2; s2 = s2->next) |
999 | { | 1126 | { |
1127 | table[s1->marked][s2->marked] = 0; | ||
1128 | |||
1000 | if ((s1->accepting && !s2->accepting) || | 1129 | if ((s1->accepting && !s2->accepting) || |
1001 | (!s1->accepting && s2->accepting)) | 1130 | (!s1->accepting && s2->accepting)) |
1002 | { | 1131 | { |
1003 | table[s1->marked][s2->marked] = 1; | 1132 | table[s1->marked][s2->marked] = 1; |
1004 | } | 1133 | } |
1005 | else | ||
1006 | table[s1->marked][s2->marked] = 0; | ||
1007 | } | 1134 | } |
1008 | } | 1135 | } |
1009 | 1136 | ||
1137 | // Find all equal states | ||
1010 | change = 1; | 1138 | change = 1; |
1011 | while (0 != change) | 1139 | while (0 != change) |
1012 | { | 1140 | { |
@@ -1018,15 +1146,14 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1018 | if (0 != table[s1->marked][s2->marked]) | 1146 | if (0 != table[s1->marked][s2->marked]) |
1019 | continue; | 1147 | continue; |
1020 | 1148 | ||
1021 | common_labels = GNUNET_NO; | 1149 | num_equal_edges = 0; |
1022 | for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next) | 1150 | for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next) |
1023 | { | 1151 | { |
1024 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) | 1152 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) |
1025 | { | 1153 | { |
1026 | if (t1->label == t2->label) | 1154 | if (t1->label == t2->label) |
1027 | { | 1155 | { |
1028 | common_labels = GNUNET_YES; | 1156 | num_equal_edges++; |
1029 | |||
1030 | if (0 != table[t1->to_state->marked][t2->to_state->marked] || | 1157 | if (0 != table[t1->to_state->marked][t2->to_state->marked] || |
1031 | 0 != table[t2->to_state->marked][t1->to_state->marked]) | 1158 | 0 != table[t2->to_state->marked][t1->to_state->marked]) |
1032 | { | 1159 | { |
@@ -1036,16 +1163,24 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1036 | } | 1163 | } |
1037 | } | 1164 | } |
1038 | } | 1165 | } |
1039 | if (GNUNET_NO == common_labels) | 1166 | if (num_equal_edges == 0) |
1167 | { | ||
1168 | table[s1->marked][s2->marked] = -1; | ||
1169 | } | ||
1170 | else if (num_equal_edges != s1->transition_count || | ||
1171 | num_equal_edges != s2->transition_count) | ||
1172 | { | ||
1173 | // Make sure ALL edges of possible equal states are the same | ||
1040 | table[s1->marked][s2->marked] = -2; | 1174 | table[s1->marked][s2->marked] = -2; |
1175 | } | ||
1041 | } | 1176 | } |
1042 | } | 1177 | } |
1043 | } | 1178 | } |
1044 | 1179 | ||
1045 | struct GNUNET_REGEX_State *s2_next; | 1180 | // Merge states that are equal |
1046 | 1181 | for (s1 = a->states_head; NULL != s1; s1 = s1_next) | |
1047 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) | ||
1048 | { | 1182 | { |
1183 | s1_next = s1->next; | ||
1049 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) | 1184 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) |
1050 | { | 1185 | { |
1051 | s2_next = s2->next; | 1186 | s2_next = s2->next; |
@@ -1599,7 +1734,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1599 | case '*': | 1734 | case '*': |
1600 | if (atomcount == 0) | 1735 | if (atomcount == 0) |
1601 | { | 1736 | { |
1602 | error_msg = "Cannot append '+' to nothing"; | 1737 | error_msg = "Cannot append '*' to nothing"; |
1603 | goto error; | 1738 | goto error; |
1604 | } | 1739 | } |
1605 | nfa_add_star_op (&ctx); | 1740 | nfa_add_star_op (&ctx); |
@@ -1650,7 +1785,6 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1650 | nfa = ctx.stack_tail; | 1785 | nfa = ctx.stack_tail; |
1651 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); | 1786 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); |
1652 | 1787 | ||
1653 | |||
1654 | if (NULL != ctx.stack_head) | 1788 | if (NULL != ctx.stack_head) |
1655 | { | 1789 | { |
1656 | error_msg = "Creating the NFA failed. NFA stack was not empty!"; | 1790 | error_msg = "Creating the NFA failed. NFA stack was not empty!"; |
@@ -1724,6 +1858,9 @@ construct_dfa_states (struct GNUNET_REGEX_Context *ctx, | |||
1724 | ctran->to_state = state_contains; | 1858 | ctran->to_state = state_contains; |
1725 | automaton_destroy_state (new_dfa_state); | 1859 | automaton_destroy_state (new_dfa_state); |
1726 | } | 1860 | } |
1861 | |||
1862 | GNUNET_array_append (ctran->to_state->incoming_transitions, | ||
1863 | ctran->to_state->incoming_transition_count, ctran); | ||
1727 | } | 1864 | } |
1728 | } | 1865 | } |
1729 | 1866 | ||
@@ -1767,9 +1904,16 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len) | |||
1767 | 1904 | ||
1768 | GNUNET_REGEX_automaton_destroy (nfa); | 1905 | GNUNET_REGEX_automaton_destroy (nfa); |
1769 | 1906 | ||
1907 | // Minimize DFA | ||
1770 | dfa_minimize (&ctx, dfa); | 1908 | dfa_minimize (&ctx, dfa); |
1909 | |||
1910 | // Calculate SCCs | ||
1771 | scc_tarjan (&ctx, dfa); | 1911 | scc_tarjan (&ctx, dfa); |
1772 | 1912 | ||
1913 | // Create proofs for all states | ||
1914 | automaton_traverse (NULL, dfa, &state_create_proof); | ||
1915 | |||
1916 | |||
1773 | return dfa; | 1917 | return dfa; |
1774 | } | 1918 | } |
1775 | 1919 | ||
@@ -2068,7 +2212,6 @@ GNUNET_REGEX_check_proof (const char *proof, const GNUNET_HashCode * key) | |||
2068 | return GNUNET_OK; | 2212 | return GNUNET_OK; |
2069 | } | 2213 | } |
2070 | 2214 | ||
2071 | |||
2072 | /** | 2215 | /** |
2073 | * Iterate over all edges helper function starting from state 's', calling | 2216 | * Iterate over all edges helper function starting from state 's', calling |
2074 | * iterator on for each edge. | 2217 | * iterator on for each edge. |
@@ -2091,7 +2234,7 @@ iterate_edge (struct GNUNET_REGEX_State *s, GNUNET_REGEX_KeyIterator iterator, | |||
2091 | 2234 | ||
2092 | num_edges = state_get_edges (s, edges); | 2235 | num_edges = state_get_edges (s, edges); |
2093 | 2236 | ||
2094 | iterator (iterator_cls, &s->hash, NULL, s->accepting, num_edges, edges); | 2237 | iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, edges); |
2095 | 2238 | ||
2096 | for (t = s->transitions_head; NULL != t; t = t->next) | 2239 | for (t = s->transitions_head; NULL != t; t = t->next) |
2097 | iterate_edge (t->to_state, iterator, iterator_cls); | 2240 | iterate_edge (t->to_state, iterator, iterator_cls); |
diff --git a/src/regex/test_regex_eval_api.c b/src/regex/test_regex_eval_api.c index 371d19ec1..c63e97c11 100644 --- a/src/regex/test_regex_eval_api.c +++ b/src/regex/test_regex_eval_api.c | |||
@@ -248,7 +248,7 @@ main (int argc, char *argv[]) | |||
248 | int check_dfa; | 248 | int check_dfa; |
249 | int check_rand; | 249 | int check_rand; |
250 | 250 | ||
251 | struct Regex_String_Pair rxstr[5] = { | 251 | struct Regex_String_Pair rxstr[8] = { |
252 | {"ab?(abcd)?", 5, | 252 | {"ab?(abcd)?", 5, |
253 | {"ababcd", "abab", "aabcd", "a", "abb"}, | 253 | {"ababcd", "abab", "aabcd", "a", "abb"}, |
254 | {match, nomatch, match, match, nomatch}}, | 254 | {match, nomatch, match, match, nomatch}}, |
@@ -260,11 +260,20 @@ main (int argc, char *argv[]) | |||
260 | {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", | 260 | {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", |
261 | "abccccca", "abcdcdcdccdabdabd"}, | 261 | "abccccca", "abcdcdcdccdabdabd"}, |
262 | {nomatch, nomatch, nomatch, nomatch, nomatch}}, | 262 | {nomatch, nomatch, nomatch, nomatch, nomatch}}, |
263 | {"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", 1, | ||
264 | {"kaXycQepRZKyRwY6nhkwVFWBegNVtLPj39XhJJ6bEifRSZRYZg"}, | ||
265 | {nomatch}}, | ||
263 | {"k|a+X*y+c|Q*e|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*g|N+V|t+L|P*j*3*9+X*h*J|J*6|b|E*i*f*R+S|Z|R|Y*Z|g*", 1, | 266 | {"k|a+X*y+c|Q*e|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*g|N+V|t+L|P*j*3*9+X*h*J|J*6|b|E*i*f*R+S|Z|R|Y*Z|g*", 1, |
264 | {"kaXycQepRZKyRwY6nhkwVFWBegNVtLPj39XhJJ6bEifRSZRYZg"}, | 267 | {"kaXycQepRZKyRwY6nhkwVFWBegNVtLPj39XhJJ6bEifRSZRYZg"}, |
265 | {nomatch}}, | 268 | {nomatch}}, |
266 | {"F?W+m+2*6*c*s|P?U?a|B|y*i+t+A|V|6*C*7*e?Z*n*i|J?5+g?W*V?7*j?p?1|r?B?C+E+3+6*i+W*P?K?0|D+7?y*m+3?g?K?", 1, | 269 | {"F?W+m+2*6*c*s|P?U?a|B|y*i+t+A|V|6*C*7*e?Z*n*i|J?5+g?W*V?7*j?p?1|r?B?C+E+3+6*i+W*P?K?0|D+7?y*m+3?g?K?", 1, |
267 | {"osfjsodfonONONOnosndfsdnfsd"}, | 270 | {"osfjsodfonONONOnosndfsdnfsd"}, |
271 | {nomatch}}, | ||
272 | {"V|M*o?x*p*d+h+b|E*m?h?Y*E*O?W*W*P+o?Z+H*M|I*q+C*a+5?5*9|b?z|G*y*k?R|p+u|8*h?B+l*H|e|L*O|1|F?v*0?5|C+", 1, | ||
273 | {"VMoxpdhbEmhYEOWWPoZHMIqCa559bzGykRpu8hBlHeLO1Fv05C"}, | ||
274 | {nomatch}}, | ||
275 | {"ab(c|d)+c*(a(b|c)d)+", 1, | ||
276 | {"abacd"}, | ||
268 | {nomatch}} | 277 | {nomatch}} |
269 | }; | 278 | }; |
270 | 279 | ||
@@ -272,7 +281,7 @@ main (int argc, char *argv[]) | |||
272 | check_dfa = 0; | 281 | check_dfa = 0; |
273 | check_rand = 0; | 282 | check_rand = 0; |
274 | 283 | ||
275 | for (i = 0; i < 5; i++) | 284 | for (i = 0; i < 8; i++) |
276 | { | 285 | { |
277 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) | 286 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) |
278 | { | 287 | { |
@@ -295,8 +304,8 @@ main (int argc, char *argv[]) | |||
295 | } | 304 | } |
296 | 305 | ||
297 | srand (time (NULL)); | 306 | srand (time (NULL)); |
298 | for (i = 0; i < 100; i++) | 307 | for (i = 0; i < 150; i++) |
299 | check_rand += test_random (100, 150, 20); | 308 | check_rand += test_random (150, 200, 25); |
300 | 309 | ||
301 | return check_nfa + check_dfa + check_rand; | 310 | return check_nfa + check_dfa + check_rand; |
302 | } | 311 | } |
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c index 52cd12cb6..7c7324aa5 100644 --- a/src/regex/test_regex_iterate_api.c +++ b/src/regex/test_regex_iterate_api.c | |||
@@ -39,6 +39,9 @@ key_iterator (void *cls, const GNUNET_HashCode * key, const char *proof, | |||
39 | { | 39 | { |
40 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Edge %i: %s\n", i, edges[i].label); | 40 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Edge %i: %s\n", i, edges[i].label); |
41 | } | 41 | } |
42 | |||
43 | if (NULL != proof) | ||
44 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Proof: %s\n", proof); | ||
42 | } | 45 | } |
43 | 46 | ||
44 | int | 47 | int |
@@ -55,14 +58,31 @@ main (int argc, char *argv[]) | |||
55 | int error; | 58 | int error; |
56 | const char *regex; | 59 | const char *regex; |
57 | struct GNUNET_REGEX_Automaton *dfa; | 60 | struct GNUNET_REGEX_Automaton *dfa; |
61 | struct GNUNET_REGEX_Automaton *nfa; | ||
58 | 62 | ||
59 | error = 0; | 63 | error = 0; |
60 | regex = "ab?(abcd)?"; | 64 | /*regex = "ab?|xy|(abcd)?"; */ |
65 | /*regex = "(ab|cd|ef)xy"; */ | ||
66 | /*regex = "(ac|bc)de"; */ | ||
67 | /*regex = "((a|b)c)de"; */ | ||
68 | /*regex = "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*"; */ | ||
69 | regex = "ab(c|d)+c*(a(b|c)d)+"; | ||
70 | /*regex = "ab?(abcd)?"; */ | ||
71 | const char *regex1 = "(ac|bc)de"; | ||
72 | const char *regex2 = "((a|b)c)de"; | ||
61 | 73 | ||
74 | /*nfa = GNUNET_REGEX_construct_nfa (regex, strlen (regex)); */ | ||
75 | /*GNUNET_REGEX_automaton_save_graph (nfa, "nfa.dot"); */ | ||
62 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex)); | 76 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex)); |
63 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa.dot"); | 77 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa.dot"); |
64 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, NULL); | 78 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, NULL); |
65 | GNUNET_REGEX_automaton_destroy (dfa); | 79 | GNUNET_REGEX_automaton_destroy (dfa); |
80 | dfa = GNUNET_REGEX_construct_dfa (regex1, strlen (regex1)); | ||
81 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa1.dot"); | ||
82 | GNUNET_REGEX_automaton_destroy (dfa); | ||
83 | dfa = GNUNET_REGEX_construct_dfa (regex2, strlen (regex2)); | ||
84 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa2.dot"); | ||
85 | GNUNET_REGEX_automaton_destroy (dfa); | ||
66 | 86 | ||
67 | return error; | 87 | return error; |
68 | } | 88 | } |