2 This file is part of GNUnet
3 (C) 2012 Christian Grothoff (and other contributing authors)
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.
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.
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.
21 * @file src/regex/regex.c
22 * @brief library to create automatons from regular expressions
23 * @author Maximilian Szengel
26 #include "gnunet_container_lib.h"
27 #include "gnunet_regex_lib.h"
31 stack_push (struct GNUNET_CONTAINER_SList *stack, const void *buf, size_t len)
33 GNUNET_CONTAINER_slist_add (stack, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
38 stack_empty (struct GNUNET_CONTAINER_SList *stack)
40 return 0 == GNUNET_CONTAINER_slist_count (stack);
44 stack_pop (struct GNUNET_CONTAINER_SList *stack, size_t length)
46 struct GNUNET_CONTAINER_SList_Iterator it;
50 it = GNUNET_CONTAINER_slist_begin (stack);
51 val = GNUNET_CONTAINER_slist_get (&it, &len);
52 GNUNET_assert (length == len);
53 GNUNET_CONTAINER_slist_erase (&it);
54 GNUNET_CONTAINER_slist_iter_destroy (&it);
60 stack_top (struct GNUNET_CONTAINER_SList *stack, size_t * len)
62 struct GNUNET_CONTAINER_SList_Iterator it;
64 if (stack_empty (stack))
67 return GNUNET_CONTAINER_slist_get (&it, len);
76 struct GNUNET_CONTAINER_SList *transitions;
77 struct GNUNET_CONTAINER_SList *nfa_set;
80 struct GNUNET_REGEX_Automaton
84 struct GNUNET_CONTAINER_SList *states;
94 struct GNUNET_REGEX_Context
96 unsigned int state_id;
97 unsigned int transition_id;
98 struct GNUNET_CONTAINER_SList *stack;
102 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
106 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
110 ctx->transition_id = 0;
111 ctx->stack = GNUNET_CONTAINER_slist_create ();
115 GNUNET_REGEX_context_destroy (struct GNUNET_REGEX_Context *ctx)
117 if (NULL != ctx->stack)
118 GNUNET_CONTAINER_slist_destroy (ctx->stack);
122 debug_print_state (struct State *s)
124 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
125 "State %i: %s marked: %i accepting: %i\n", s->id, s->name,
126 s->marked, s->accepting);
130 debug_print_states (struct GNUNET_CONTAINER_SList *states)
132 struct GNUNET_CONTAINER_SList_Iterator it;
135 for (it = GNUNET_CONTAINER_slist_begin (states);
136 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
137 GNUNET_CONTAINER_slist_next (&it))
139 s = GNUNET_CONTAINER_slist_get (&it, NULL);
140 debug_print_state (s);
142 GNUNET_CONTAINER_slist_iter_destroy (&it);
146 debug_print_transitions (struct State *s)
148 struct GNUNET_CONTAINER_SList_Iterator it;
149 struct Transition *t;
153 for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
154 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
155 GNUNET_CONTAINER_slist_next (&it))
157 t = GNUNET_CONTAINER_slist_get (&it, NULL);
162 literal = t->literal;
164 if (NULL == t->state)
167 state = t->state->name;
169 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
173 GNUNET_CONTAINER_slist_iter_destroy (&it);
177 set_compare (const void *buf1, const size_t len1, const void *buf2,
182 struct GNUNET_CONTAINER_SList_Iterator it1;
183 struct GNUNET_CONTAINER_SList_Iterator it2;
186 struct GNUNET_CONTAINER_SList *l1;
187 struct GNUNET_CONTAINER_SList *l2;
195 if (len1 != len2 && len1 != sizeof (struct State) &&
196 len2 != sizeof (struct State))
199 s1 = (struct State *) buf1;
200 s2 = (struct State *) buf2;
205 c1 = GNUNET_CONTAINER_slist_count (l1);
206 c2 = GNUNET_CONTAINER_slist_count (l2);
209 return ((c1 > c2) ? 1 : -1);
213 for (it1 = GNUNET_CONTAINER_slist_begin (l1);
214 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it1);
215 GNUNET_CONTAINER_slist_next (&it1))
217 el1 = GNUNET_CONTAINER_slist_get (&it1, &length1);
220 for (it2 = GNUNET_CONTAINER_slist_begin (l2);
221 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it2);
222 GNUNET_CONTAINER_slist_next (&it2))
224 el2 = GNUNET_CONTAINER_slist_get (&it2, &length2);
226 if (length1 != length2)
228 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
229 "Comparing lists failed, element size mismatch\n");
232 if (((struct State *) el1)->id == ((struct State *) el2)->id)
238 GNUNET_CONTAINER_slist_iter_destroy (&it2);
246 GNUNET_CONTAINER_slist_iter_destroy (&it1);
252 transition_literal_compare (const void *buf1, const size_t len1,
253 const void *buf2, const size_t len2)
255 struct Transition *t1;
256 struct Transition *t2;
258 if (len1 != len2 && len1 != sizeof (struct Transition) &&
259 len2 != sizeof (struct Transition))
264 t1 = (struct Transition *) buf1;
265 t2 = (struct Transition *) buf2;
267 if (t1->literal == t2->literal)
269 else if (t1->literal > t2->literal)
276 add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state,
277 const char literal, struct State *to_state)
281 if (NULL == from_state)
283 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
287 t.id = ctx->transition_id++;
291 GNUNET_CONTAINER_slist_add (from_state->transitions,
292 GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT, &t,
297 dfa_create_state (struct GNUNET_REGEX_Context *ctx,
298 struct GNUNET_CONTAINER_SList *states)
302 struct GNUNET_CONTAINER_SList_Iterator stateit;
303 struct GNUNET_CONTAINER_SList_Iterator tranit;
305 struct State *cstate;
306 struct Transition *ctran;
308 s = GNUNET_malloc (sizeof (struct State));
309 s->id = ctx->state_id++;
311 s->transitions = GNUNET_CONTAINER_slist_create ();
320 if (0 == GNUNET_CONTAINER_slist_count (states))
324 // Create a name based on 'sset'
325 s->name = GNUNET_malloc (sizeof (char) * 2);
326 strcat (s->name, "{");
329 for (stateit = GNUNET_CONTAINER_slist_begin (states);
330 GNUNET_NO == GNUNET_CONTAINER_slist_end (&stateit);
331 GNUNET_CONTAINER_slist_next (&stateit))
333 cstate = GNUNET_CONTAINER_slist_get (&stateit, NULL);
334 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
335 GNUNET_asprintf (&name, "%i,", cstate->id);
339 len = strlen (s->name) + strlen (name) + 1;
340 s->name = GNUNET_realloc (s->name, len);
341 strcat (s->name, name);
346 // Add a transition for each distinct literal to NULL state
347 for (tranit = GNUNET_CONTAINER_slist_begin (cstate->transitions);
348 GNUNET_NO == GNUNET_CONTAINER_slist_end (&tranit);
349 GNUNET_CONTAINER_slist_next (&tranit))
351 ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
352 if (0 != ctran->literal &&
353 NULL == GNUNET_CONTAINER_slist_contains2 (s->transitions, ctran,
355 &transition_literal_compare))
357 add_transition (ctx, s, ctran->literal, NULL);
361 if (cstate->accepting)
364 GNUNET_CONTAINER_slist_iter_destroy (&stateit);
366 s->name[strlen (s->name) - 1] = '}';
372 dfa_clear_nfa_set (struct GNUNET_CONTAINER_SList *states)
374 struct GNUNET_CONTAINER_SList_Iterator it;
377 for (it = GNUNET_CONTAINER_slist_begin (states);
378 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
379 GNUNET_CONTAINER_slist_next (&it))
381 s = GNUNET_CONTAINER_slist_get (&it, NULL);
382 if (NULL != s->nfa_set)
384 GNUNET_CONTAINER_slist_destroy (s->nfa_set);
389 GNUNET_CONTAINER_slist_iter_destroy (&it);
392 struct GNUNET_REGEX_Automaton *
393 nfa_create (struct State *start, struct State *end)
395 struct GNUNET_REGEX_Automaton *n;
397 n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
401 n->states = GNUNET_CONTAINER_slist_create ();
403 if (NULL == start && NULL == end)
406 GNUNET_CONTAINER_slist_add (n->states,
407 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, end,
410 GNUNET_CONTAINER_slist_add (n->states,
411 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, start,
421 nfa_add_states (struct GNUNET_REGEX_Automaton *n,
422 struct GNUNET_CONTAINER_SList *states)
424 // This isn't very pretty. Would be better to use GNUNET_CONTAINER_slist_append, but
425 // this function adds to the beginning of dst, which currently breaks "pretty"
426 // printing of the graph...
427 struct GNUNET_CONTAINER_SList_Iterator i;
430 for (i = GNUNET_CONTAINER_slist_begin (states);
431 GNUNET_CONTAINER_slist_end (&i) != GNUNET_YES;
432 GNUNET_CONTAINER_slist_next (&i))
435 s = GNUNET_CONTAINER_slist_get (&i, NULL);
436 GNUNET_CONTAINER_slist_add_end (n->states,
437 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
440 GNUNET_CONTAINER_slist_iter_destroy (&i);
444 nfa_create_state (struct GNUNET_REGEX_Context *ctx, int accepting)
448 s = GNUNET_malloc (sizeof (struct State));
449 s->id = ctx->state_id++;
450 s->accepting = accepting;
451 s->transitions = GNUNET_CONTAINER_slist_create ();
454 GNUNET_asprintf (&s->name, "s%i", s->id);
460 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
462 GNUNET_CONTAINER_slist_destroy (a->states);
469 automaton_destroy_state (struct State *s)
471 if (NULL != s->transitions)
472 GNUNET_CONTAINER_slist_destroy (s->transitions);
474 GNUNET_free (s->name);
475 if (NULL != s->nfa_set)
476 GNUNET_CONTAINER_slist_destroy (s->nfa_set);
481 mark_all_states (struct GNUNET_REGEX_Automaton *n, int marked)
483 struct GNUNET_CONTAINER_SList_Iterator it;
486 for (it = GNUNET_CONTAINER_slist_begin (n->states);
487 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
488 GNUNET_CONTAINER_slist_next (&it))
490 s = GNUNET_CONTAINER_slist_get (&it, NULL);
494 GNUNET_CONTAINER_slist_iter_destroy (&it);
498 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
500 struct GNUNET_REGEX_Automaton *a;
501 struct GNUNET_REGEX_Automaton *b;
502 struct GNUNET_REGEX_Automaton *new;
504 b = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
505 a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
507 add_transition (ctx, a->end, 0, b->start);
508 a->end->accepting = 0;
509 b->end->accepting = 1;
511 new = nfa_create (NULL, NULL);
512 nfa_add_states (new, a->states);
513 nfa_add_states (new, b->states);
514 new->start = a->start;
516 automaton_fragment_clear (a);
517 automaton_fragment_clear (b);
519 stack_push (ctx->stack, new, sizeof *new);
523 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
525 struct GNUNET_REGEX_Automaton *a;
526 struct GNUNET_REGEX_Automaton *new;
530 a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
534 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
535 "nfa_add_star_op failed, because there was no element on the stack");
539 start = nfa_create_state (ctx, 0);
540 end = nfa_create_state (ctx, 1);
542 add_transition (ctx, start, 0, a->start);
543 add_transition (ctx, start, 0, end);
544 add_transition (ctx, a->end, 0, a->start);
545 add_transition (ctx, a->end, 0, end);
547 a->end->accepting = 0;
550 new = nfa_create (start, end);
551 nfa_add_states (new, a->states);
552 automaton_fragment_clear (a);
554 stack_push (ctx->stack, new, sizeof *new);
558 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
560 struct GNUNET_REGEX_Automaton *a;
562 a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
564 add_transition (ctx, a->end, 0, a->start);
566 stack_push (ctx->stack, a, sizeof *a);
570 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
572 struct GNUNET_REGEX_Automaton *a;
573 struct GNUNET_REGEX_Automaton *b;
574 struct GNUNET_REGEX_Automaton *new;
578 b = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
579 a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
581 start = nfa_create_state (ctx, 0);
582 end = nfa_create_state (ctx, 1);
583 add_transition (ctx, start, 0, a->start);
584 add_transition (ctx, start, 0, b->start);
586 add_transition (ctx, a->end, 0, end);
587 add_transition (ctx, b->end, 0, end);
589 a->end->accepting = 0;
590 b->end->accepting = 0;
593 new = nfa_create (start, end);
594 nfa_add_states (new, a->states);
595 nfa_add_states (new, b->states);
596 automaton_fragment_clear (a);
597 automaton_fragment_clear (b);
599 stack_push (ctx->stack, new, sizeof *new);
603 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
605 struct GNUNET_REGEX_Automaton *n;
609 start = nfa_create_state (ctx, 0);
610 end = nfa_create_state (ctx, 1);
611 add_transition (ctx, start, lit, end);
612 n = nfa_create (start, end);
613 stack_push (ctx->stack, n, sizeof *n);
617 * Calculates the closure set for the given set of states.
619 * @param states set of states for which to calculate the closure
620 * @param count number of states in 'states'
621 * @param literal for the transition
623 * @return set of states that can be reached from the given 'states' when
624 * using only 'literal' transitions
626 struct GNUNET_CONTAINER_SList *
627 create_nfa_closure (struct GNUNET_CONTAINER_SList *states, const char literal)
629 struct GNUNET_CONTAINER_SList_Iterator stateit;
630 struct GNUNET_CONTAINER_SList_Iterator tranit;
631 struct GNUNET_CONTAINER_SList *cls;
632 struct GNUNET_CONTAINER_SList *cls_check;
634 struct State *currentstate;
635 struct Transition *currenttransition;
636 struct State *clsstate;
638 cls = GNUNET_CONTAINER_slist_create ();
640 for (stateit = GNUNET_CONTAINER_slist_begin (states);
641 GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
642 GNUNET_CONTAINER_slist_next (&stateit))
644 s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
645 cls_check = GNUNET_CONTAINER_slist_create ();
647 // Add start state to closure only for epsilon closure
650 GNUNET_CONTAINER_slist_add (cls,
651 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, s,
655 stack_push (cls_check, s, sizeof *s);
657 while (!stack_empty (cls_check))
659 currentstate = stack_pop (cls_check, sizeof (struct State));
661 for (tranit = GNUNET_CONTAINER_slist_begin (currentstate->transitions);
662 GNUNET_CONTAINER_slist_end (&tranit) != GNUNET_YES;
663 GNUNET_CONTAINER_slist_next (&tranit))
665 currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
667 if (NULL != currenttransition->state &&
668 literal == currenttransition->literal)
670 clsstate = currenttransition->state;
672 if (NULL == clsstate)
676 GNUNET_CONTAINER_slist_contains (cls, clsstate, sizeof *clsstate))
678 GNUNET_CONTAINER_slist_add (cls,
679 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
680 clsstate, sizeof *clsstate);
681 stack_push (cls_check, clsstate, sizeof *clsstate);
685 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
688 GNUNET_assert (stack_empty (cls_check));
689 GNUNET_CONTAINER_slist_destroy (cls_check);
691 GNUNET_CONTAINER_slist_iter_destroy (&stateit);
696 struct GNUNET_CONTAINER_SList *
697 GNUNET_REGEX_move (struct GNUNET_REGEX_Automaton *a, struct State *s,
700 struct GNUNET_CONTAINER_SList *l;
701 struct GNUNET_CONTAINER_SList_Iterator it;
702 struct Transition *ctran;
704 if (!GNUNET_CONTAINER_slist_contains (a->states, s, sizeof *s))
706 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
707 "State %s is not part of the given automaton", s->name);
711 l = GNUNET_CONTAINER_slist_create ();
713 for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
714 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
715 GNUNET_CONTAINER_slist_next (&it))
717 ctran = GNUNET_CONTAINER_slist_get (&it, NULL);
718 if (literal == ctran->literal)
719 GNUNET_CONTAINER_slist_add (l, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
720 ctran->state, sizeof *(ctran->state));
722 GNUNET_CONTAINER_slist_iter_destroy (&it);
728 * Construct an NFA by parsing the regex string of length 'len'.
730 * @param regex regular expression string
731 * @param len length of the string
733 * @return NFA.Needs to be freed using GNUNET_REGEX_destroy_automaton
735 struct GNUNET_REGEX_Automaton *
736 GNUNET_REGEX_construct_nfa(const char *regex, const size_t len)
738 struct GNUNET_REGEX_Context ctx;
739 struct GNUNET_REGEX_Automaton *nfa;
742 unsigned int altcount;
743 unsigned int atomcount;
751 GNUNET_REGEX_context_init (&ctx);
759 for (count = 0; count < len && *regex; count++, regex++)
767 nfa_add_concatenation (&ctx);
769 GNUNET_array_grow (p, pcount, pcount + 1);
770 p[pcount - 1].altcount = altcount;
771 p[pcount - 1].atomcount = atomcount;
778 error_msg = "Cannot append '|' to nothing";
781 while (--atomcount > 0)
782 nfa_add_concatenation (&ctx);
788 error_msg = "Missing opening '('";
795 altcount = p[pcount].altcount;
796 atomcount = p[pcount].atomcount;
799 while (--atomcount > 0)
800 nfa_add_concatenation (&ctx);
801 for (; altcount > 0; altcount--)
802 nfa_add_alternation (&ctx);
804 altcount = p[pcount].altcount;
805 atomcount = p[pcount].atomcount;
811 error_msg = "Cannot append '+' to nothing";
814 nfa_add_star_op (&ctx);
819 error_msg = "Cannot append '+' to nothing";
822 nfa_add_plus_op (&ctx);
824 case 92: /* escape: \ */
831 nfa_add_concatenation (&ctx);
833 nfa_add_literal (&ctx, *regex);
840 error_msg = "Unbalanced parenthesis";
843 while (--atomcount > 0)
844 nfa_add_concatenation (&ctx);
845 for (; altcount > 0; altcount--)
846 nfa_add_alternation (&ctx);
851 nfa = stack_pop (ctx.stack, sizeof (struct GNUNET_REGEX_Automaton));
853 if (!stack_empty (ctx.stack))
855 error_msg = "Creating the NFA failed. NFA stack was not empty!";
859 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
860 "Created NFA with %i States and a total of %i Transitions\n",
861 GNUNET_CONTAINER_slist_count (nfa->states), ctx.transition_id);
863 GNUNET_REGEX_context_destroy (&ctx);
868 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
869 if (NULL != error_msg)
870 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
872 while (!stack_empty (ctx.stack))
873 GNUNET_REGEX_automaton_destroy (stack_pop (ctx.stack,
874 sizeof (struct GNUNET_REGEX_Automaton)));
875 GNUNET_REGEX_context_destroy (&ctx);
880 * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
883 * @param a automaton to be destroyed
886 GNUNET_REGEX_automaton_destroy(struct GNUNET_REGEX_Automaton *a)
888 struct GNUNET_CONTAINER_SList_Iterator it;
893 for (it = GNUNET_CONTAINER_slist_begin (a->states);
894 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
895 GNUNET_CONTAINER_slist_next (&it))
897 automaton_destroy_state (GNUNET_CONTAINER_slist_get (&it, NULL));
899 GNUNET_CONTAINER_slist_iter_destroy (&it);
900 GNUNET_CONTAINER_slist_destroy (a->states);
905 * Construct DFA for the given 'regex' of lenght 'len'
907 * @param regex regular expression string
908 * @param len length of the regular expression
910 * @return DFA. Needs to be freed using GNUNET_REGEX_destroy_automaton
912 struct GNUNET_REGEX_Automaton *
913 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
915 struct GNUNET_REGEX_Context ctx;
916 struct GNUNET_REGEX_Automaton *dfa;
917 struct GNUNET_REGEX_Automaton *nfa;
918 struct GNUNET_CONTAINER_SList *tmp;
919 struct GNUNET_CONTAINER_SList *nfa_set;
920 struct GNUNET_CONTAINER_SList *sset;
921 struct GNUNET_CONTAINER_SList *dfa_stack;
922 struct GNUNET_CONTAINER_SList_Iterator tranit;
923 struct Transition *currenttransition;
924 struct State *dfa_state;
925 struct State *new_dfa_state;
926 struct State *state_contains;
928 GNUNET_REGEX_context_init (&ctx);
931 nfa = GNUNET_REGEX_construct_nfa (regex, len);
933 dfa_stack = GNUNET_CONTAINER_slist_create ();
935 // Initialize new dfa
936 dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
937 dfa->states = GNUNET_CONTAINER_slist_create ();
939 // Create DFA start state from epsilon closure
940 sset = GNUNET_CONTAINER_slist_create ();
941 GNUNET_CONTAINER_slist_add (sset, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
942 nfa->start, sizeof *(nfa->start));
943 nfa_set = create_nfa_closure (sset, 0);
944 GNUNET_CONTAINER_slist_destroy (sset);
945 dfa->start = dfa_create_state (&ctx, nfa_set);
946 GNUNET_CONTAINER_slist_add (dfa->states,
947 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
948 dfa->start, sizeof *(dfa->start));
949 stack_push (dfa_stack, dfa->start, sizeof *(dfa->start));
951 while (!stack_empty (dfa_stack))
953 dfa_state = stack_pop (dfa_stack, sizeof (struct State));
955 for (tranit = GNUNET_CONTAINER_slist_begin (dfa_state->transitions);
956 GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
957 GNUNET_CONTAINER_slist_next (&tranit))
959 currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
961 if (0 != currenttransition->literal && NULL == currenttransition->state)
963 tmp = create_nfa_closure (dfa_state->nfa_set,
964 currenttransition->literal);
965 nfa_set = create_nfa_closure (tmp, 0);
966 new_dfa_state = dfa_create_state (&ctx, nfa_set);
967 GNUNET_CONTAINER_slist_destroy (tmp);
970 GNUNET_CONTAINER_slist_contains2 (dfa->states, new_dfa_state,
971 sizeof *new_dfa_state,
973 if (NULL == state_contains)
975 GNUNET_CONTAINER_slist_add_end (dfa->states,
976 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
977 new_dfa_state, sizeof *new_dfa_state);
978 stack_push (dfa_stack, new_dfa_state, sizeof *new_dfa_state);
979 currenttransition->state = new_dfa_state;
982 currenttransition->state = state_contains;
986 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
988 GNUNET_CONTAINER_slist_destroy (dfa_stack);
989 GNUNET_REGEX_automaton_destroy (nfa);
990 GNUNET_REGEX_context_destroy (&ctx);
991 dfa_clear_nfa_set (dfa->states);
993 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
994 GNUNET_CONTAINER_slist_count (dfa->states));
1000 * Save the given automaton as a GraphViz dot file
1002 * @param a the automaton to be saved
1003 * @param filename where to save the file
1006 GNUNET_REGEX_automaton_save_graph(struct GNUNET_REGEX_Automaton *a,
1007 const char *filename)
1009 struct GNUNET_CONTAINER_SList_Iterator stateit;
1010 struct GNUNET_CONTAINER_SList_Iterator tranit;
1012 struct Transition *ctran;
1014 char *s_tran = NULL;
1021 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1025 if (NULL == filename || strlen (filename) < 1)
1027 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1031 p = fopen (filename, "w");
1035 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1040 start = "digraph G {\nrankdir=LR\n";
1041 fwrite (start, strlen (start), 1, p);
1043 for (stateit = GNUNET_CONTAINER_slist_begin (a->states);
1044 GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
1045 GNUNET_CONTAINER_slist_next (&stateit))
1048 s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
1052 GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1053 fwrite (s_acc, strlen (s_acc), 1, p);
1054 GNUNET_free (s_acc);
1059 for (tranit = GNUNET_CONTAINER_slist_begin (s->transitions);
1060 GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
1061 GNUNET_CONTAINER_slist_next (&tranit))
1063 ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
1065 if (NULL == ctran->state)
1067 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1068 "Transition from State %i has has no state for transitioning\n",
1073 if (ctran->literal == 0)
1075 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1076 s->name, ctran->state->name);
1080 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1081 s->name, ctran->state->name, ctran->literal);
1084 fwrite (s_tran, strlen (s_tran), 1, p);
1085 GNUNET_free (s_tran);
1087 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
1089 GNUNET_CONTAINER_slist_iter_destroy (&stateit);
1092 fwrite (end, strlen (end), 1, p);