diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-23 16:30:39 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-23 16:30:39 +0000 |
commit | 09f394f4f8fc77de47857adf9b8630136d930005 (patch) | |
tree | a461aacf16a90e371fb41360d2c6e3c2305c856a /src/regex | |
parent | 701f3aaab234871e99915e41a57cae14da9f4b09 (diff) | |
download | gnunet-09f394f4f8fc77de47857adf9b8630136d930005.tar.gz gnunet-09f394f4f8fc77de47857adf9b8630136d930005.zip |
- added check for automaton traversal
- fixed a bug that caused nfa's state_count to be incorrect for certain regexes
- only compute scc's when coloring option is set
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 34 | ||||
-rw-r--r-- | src/regex/regex_graph.c | 5 | ||||
-rw-r--r-- | src/regex/regex_internal.h | 23 | ||||
-rw-r--r-- | src/regex/test_regex_eval_api.c | 4 |
4 files changed, 54 insertions, 12 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 79d94ea03..f8177305e 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -580,12 +580,16 @@ automaton_add_state (struct GNUNET_REGEX_Automaton *a, | |||
580 | * @param marks an array of size a->state_count to remember which state was | 580 | * @param marks an array of size a->state_count to remember which state was |
581 | * already visited. | 581 | * already visited. |
582 | * @param count current count of the state. | 582 | * @param count current count of the state. |
583 | * @param check function that is checked before advancing on each transition | ||
584 | * in the DFS. | ||
585 | * @param check_cls closure for check. | ||
583 | * @param action action to be performed on each state. | 586 | * @param action action to be performed on each state. |
584 | * @param action_cls closure for action. | 587 | * @param action_cls closure for action. |
585 | */ | 588 | */ |
586 | static void | 589 | static void |
587 | automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, | 590 | automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, |
588 | unsigned int *count, | 591 | unsigned int *count, |
592 | GNUNET_REGEX_traverse_check check, void *check_cls, | ||
589 | GNUNET_REGEX_traverse_action action, void *action_cls) | 593 | GNUNET_REGEX_traverse_action action, void *action_cls) |
590 | { | 594 | { |
591 | struct GNUNET_REGEX_Transition *t; | 595 | struct GNUNET_REGEX_Transition *t; |
@@ -602,7 +606,12 @@ automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, | |||
602 | 606 | ||
603 | for (t = s->transitions_head; NULL != t; t = t->next) | 607 | for (t = s->transitions_head; NULL != t; t = t->next) |
604 | { | 608 | { |
605 | automaton_state_traverse (t->to_state, marks, count, action, action_cls); | 609 | if (NULL == check || |
610 | (NULL != check && GNUNET_YES == check (check_cls, s, t))) | ||
611 | { | ||
612 | automaton_state_traverse (t->to_state, marks, count, check, check_cls, | ||
613 | action, action_cls); | ||
614 | } | ||
606 | } | 615 | } |
607 | } | 616 | } |
608 | 617 | ||
@@ -614,12 +623,17 @@ automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, | |||
614 | * | 623 | * |
615 | * @param a automaton to be traversed. | 624 | * @param a automaton to be traversed. |
616 | * @param start start state, pass a->start or NULL to traverse the whole automaton. | 625 | * @param start start state, pass a->start or NULL to traverse the whole automaton. |
626 | * @param check function that is checked before advancing on each transition | ||
627 | * in the DFS. | ||
628 | * @param check_cls closure for check. | ||
617 | * @param action action to be performed on each state. | 629 | * @param action action to be performed on each state. |
618 | * @param action_cls closure for action | 630 | * @param action_cls closure for action |
619 | */ | 631 | */ |
620 | void | 632 | void |
621 | GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, | 633 | GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, |
622 | struct GNUNET_REGEX_State *start, | 634 | struct GNUNET_REGEX_State *start, |
635 | GNUNET_REGEX_traverse_check check, | ||
636 | void *check_cls, | ||
623 | GNUNET_REGEX_traverse_action action, | 637 | GNUNET_REGEX_traverse_action action, |
624 | void *action_cls) | 638 | void *action_cls) |
625 | { | 639 | { |
@@ -644,7 +658,8 @@ GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, | |||
644 | else | 658 | else |
645 | s = start; | 659 | s = start; |
646 | 660 | ||
647 | automaton_state_traverse (s, marks, &count, action, action_cls); | 661 | automaton_state_traverse (s, marks, &count, check, check_cls, action, |
662 | action_cls); | ||
648 | } | 663 | } |
649 | 664 | ||
650 | 665 | ||
@@ -755,8 +770,8 @@ GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx, | |||
755 | struct GNUNET_REGEX_Transition *t; | 770 | struct GNUNET_REGEX_Transition *t; |
756 | struct GNUNET_REGEX_Transition *t_next; | 771 | struct GNUNET_REGEX_Transition *t_next; |
757 | 772 | ||
758 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, &add_multi_strides_to_dfa, | 773 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, |
759 | &ctx); | 774 | &add_multi_strides_to_dfa, &ctx); |
760 | 775 | ||
761 | for (t = ctx.transitions_head; NULL != t; t = t_next) | 776 | for (t = ctx.transitions_head; NULL != t; t = t_next) |
762 | { | 777 | { |
@@ -1329,7 +1344,8 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1329 | } | 1344 | } |
1330 | 1345 | ||
1331 | /* create depth-first numbering of the states, initializes 'state' */ | 1346 | /* create depth-first numbering of the states, initializes 'state' */ |
1332 | GNUNET_REGEX_automaton_traverse (a, a->start, &number_states, states); | 1347 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &number_states, |
1348 | states); | ||
1333 | 1349 | ||
1334 | for (i = 0; i < n; i++) | 1350 | for (i = 0; i < n; i++) |
1335 | GNUNET_assert (NULL != states[i]); | 1351 | GNUNET_assert (NULL != states[i]); |
@@ -1591,7 +1607,7 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
1591 | s->marked = GNUNET_NO; | 1607 | s->marked = GNUNET_NO; |
1592 | 1608 | ||
1593 | // 2. traverse dfa from start state and mark all visited states | 1609 | // 2. traverse dfa from start state and mark all visited states |
1594 | GNUNET_REGEX_automaton_traverse (a, a->start, &mark_states, NULL); | 1610 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL); |
1595 | 1611 | ||
1596 | // 3. delete all states that were not visited | 1612 | // 3. delete all states that were not visited |
1597 | for (s = a->states_head; NULL != s; s = s_next) | 1613 | for (s = a->states_head; NULL != s; s = s_next) |
@@ -1784,6 +1800,7 @@ nfa_fragment_create (struct GNUNET_REGEX_State *start, | |||
1784 | n->type = NFA; | 1800 | n->type = NFA; |
1785 | n->start = NULL; | 1801 | n->start = NULL; |
1786 | n->end = NULL; | 1802 | n->end = NULL; |
1803 | n->state_count = 0; | ||
1787 | 1804 | ||
1788 | if (NULL == start || NULL == end) | 1805 | if (NULL == start || NULL == end) |
1789 | return n; | 1806 | return n; |
@@ -1791,6 +1808,8 @@ nfa_fragment_create (struct GNUNET_REGEX_State *start, | |||
1791 | automaton_add_state (n, end); | 1808 | automaton_add_state (n, end); |
1792 | automaton_add_state (n, start); | 1809 | automaton_add_state (n, start); |
1793 | 1810 | ||
1811 | n->state_count = 2; | ||
1812 | |||
1794 | n->start = start; | 1813 | n->start = start; |
1795 | n->end = end; | 1814 | n->end = end; |
1796 | 1815 | ||
@@ -2016,6 +2035,7 @@ nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx) | |||
2016 | nfa_add_states (new_nfa, b->states_head, b->states_tail); | 2035 | nfa_add_states (new_nfa, b->states_head, b->states_tail); |
2017 | new_nfa->start = a->start; | 2036 | new_nfa->start = a->start; |
2018 | new_nfa->end = b->end; | 2037 | new_nfa->end = b->end; |
2038 | new_nfa->state_count += a->state_count + b->state_count; | ||
2019 | automaton_fragment_clear (a); | 2039 | automaton_fragment_clear (a); |
2020 | automaton_fragment_clear (b); | 2040 | automaton_fragment_clear (b); |
2021 | 2041 | ||
@@ -2363,7 +2383,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2363 | nfa->regex = GNUNET_strdup (regex); | 2383 | nfa->regex = GNUNET_strdup (regex); |
2364 | 2384 | ||
2365 | /* create depth-first numbering of the states for pretty printing */ | 2385 | /* create depth-first numbering of the states for pretty printing */ |
2366 | GNUNET_REGEX_automaton_traverse (nfa, NULL, &number_states, NULL); | 2386 | GNUNET_REGEX_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL); |
2367 | 2387 | ||
2368 | return nfa; | 2388 | return nfa; |
2369 | 2389 | ||
diff --git a/src/regex/regex_graph.c b/src/regex/regex_graph.c index 9223200c8..5db3780d0 100644 --- a/src/regex/regex_graph.c +++ b/src/regex/regex_graph.c | |||
@@ -315,12 +315,13 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
315 | } | 315 | } |
316 | 316 | ||
317 | /* First add the SCCs to the automaton, so we can color them nicely */ | 317 | /* First add the SCCs to the automaton, so we can color them nicely */ |
318 | scc_tarjan (a); | 318 | if (GNUNET_YES == ctx.coloring) |
319 | scc_tarjan (a); | ||
319 | 320 | ||
320 | start = "digraph G {\nrankdir=LR\n"; | 321 | start = "digraph G {\nrankdir=LR\n"; |
321 | fwrite (start, strlen (start), 1, ctx.filep); | 322 | fwrite (start, strlen (start), 1, ctx.filep); |
322 | 323 | ||
323 | GNUNET_REGEX_automaton_traverse (a, a->start, | 324 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, |
324 | &GNUNET_REGEX_automaton_save_graph_step, | 325 | &GNUNET_REGEX_automaton_save_graph_step, |
325 | &ctx); | 326 | &ctx); |
326 | 327 | ||
diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index f96d51fb0..20e81d93c 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h | |||
@@ -257,6 +257,23 @@ struct GNUNET_REGEX_Automaton | |||
257 | 257 | ||
258 | 258 | ||
259 | /** | 259 | /** |
260 | * Function that get's passed to automaton traversal and is called before each | ||
261 | * next traversal from state 's' using transition 't' to check if traversal | ||
262 | * should proceed. Return GNUNET_NO to stop traversal or GNUNET_YES to continue. | ||
263 | * | ||
264 | * @param cls closure for the check. | ||
265 | * @param s current state in the traversal. | ||
266 | * @param t current transition from state 's' that will be used for the next | ||
267 | * step. | ||
268 | * | ||
269 | * @return GNUNET_YES to proceed traversal, GNUNET_NO to stop. | ||
270 | */ | ||
271 | typedef int (*GNUNET_REGEX_traverse_check) (void *cls, | ||
272 | struct GNUNET_REGEX_State * s, | ||
273 | struct GNUNET_REGEX_Transition * t); | ||
274 | |||
275 | |||
276 | /** | ||
260 | * Function that is called with each state, when traversing an automaton. | 277 | * Function that is called with each state, when traversing an automaton. |
261 | * | 278 | * |
262 | * @param cls closure. | 279 | * @param cls closure. |
@@ -275,16 +292,20 @@ typedef void (*GNUNET_REGEX_traverse_action) (void *cls, | |||
275 | * | 292 | * |
276 | * @param a automaton to be traversed. | 293 | * @param a automaton to be traversed. |
277 | * @param start start state, pass a->start or NULL to traverse the whole automaton. | 294 | * @param start start state, pass a->start or NULL to traverse the whole automaton. |
295 | * @param check function that is checked before advancing on each transition | ||
296 | * in the DFS. | ||
297 | * @param check_cls closure for check. | ||
278 | * @param action action to be performed on each state. | 298 | * @param action action to be performed on each state. |
279 | * @param action_cls closure for action | 299 | * @param action_cls closure for action |
280 | */ | 300 | */ |
281 | void | 301 | void |
282 | GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, | 302 | GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, |
283 | struct GNUNET_REGEX_State *start, | 303 | struct GNUNET_REGEX_State *start, |
304 | GNUNET_REGEX_traverse_check check, | ||
305 | void *check_cls, | ||
284 | GNUNET_REGEX_traverse_action action, | 306 | GNUNET_REGEX_traverse_action action, |
285 | void *action_cls); | 307 | void *action_cls); |
286 | 308 | ||
287 | |||
288 | /** | 309 | /** |
289 | * Get the canonical regex of the given automaton. | 310 | * Get the canonical regex of the given automaton. |
290 | * When constructing the automaton a proof is computed for each state, | 311 | * When constructing the automaton a proof is computed for each state, |
diff --git a/src/regex/test_regex_eval_api.c b/src/regex/test_regex_eval_api.c index 2de7d40b2..a4b183127 100644 --- a/src/regex/test_regex_eval_api.c +++ b/src/regex/test_regex_eval_api.c | |||
@@ -348,8 +348,8 @@ main (int argc, char *argv[]) | |||
348 | 348 | ||
349 | /* Random tests */ | 349 | /* Random tests */ |
350 | srand (time (NULL)); | 350 | srand (time (NULL)); |
351 | for (i = 0; i < 50; i++) | 351 | for (i = 0; i < 20; i++) |
352 | check_rand += test_random (50, 60, 30); | 352 | check_rand += test_random (50, 60, 10); |
353 | 353 | ||
354 | return check_nfa + check_dfa + check_rand; | 354 | return check_nfa + check_dfa + check_rand; |
355 | } | 355 | } |