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 list of states on which to base the closure on
620 * @param literal transitioning literal for which to base the closure on,
621 * pass 0 for epsilon transition
623 * @return nfa closure on literal (epsilon closure if 'literal' == 0)
625 struct GNUNET_CONTAINER_SList *
626 create_nfa_closure (struct GNUNET_CONTAINER_SList *states, const char literal)
628 struct GNUNET_CONTAINER_SList_Iterator stateit;
629 struct GNUNET_CONTAINER_SList_Iterator tranit;
630 struct GNUNET_CONTAINER_SList *cls;
631 struct GNUNET_CONTAINER_SList *cls_check;
633 struct State *currentstate;
634 struct Transition *currenttransition;
635 struct State *clsstate;
637 cls = GNUNET_CONTAINER_slist_create ();
639 for (stateit = GNUNET_CONTAINER_slist_begin (states);
640 GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
641 GNUNET_CONTAINER_slist_next (&stateit))
643 s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
644 cls_check = GNUNET_CONTAINER_slist_create ();
646 // Add start state to closure only for epsilon closure
649 GNUNET_CONTAINER_slist_add (cls,
650 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, s,
654 stack_push (cls_check, s, sizeof *s);
656 while (!stack_empty (cls_check))
658 currentstate = stack_pop (cls_check, sizeof (struct State));
660 for (tranit = GNUNET_CONTAINER_slist_begin (currentstate->transitions);
661 GNUNET_CONTAINER_slist_end (&tranit) != GNUNET_YES;
662 GNUNET_CONTAINER_slist_next (&tranit))
664 currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
666 if (NULL != currenttransition->state &&
667 literal == currenttransition->literal)
669 clsstate = currenttransition->state;
671 if (NULL == clsstate)
675 GNUNET_CONTAINER_slist_contains (cls, clsstate, sizeof *clsstate))
677 GNUNET_CONTAINER_slist_add (cls,
678 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
679 clsstate, sizeof *clsstate);
680 stack_push (cls_check, clsstate, sizeof *clsstate);
684 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
687 GNUNET_assert (stack_empty (cls_check));
688 GNUNET_CONTAINER_slist_destroy (cls_check);
690 GNUNET_CONTAINER_slist_iter_destroy (&stateit);
695 struct GNUNET_CONTAINER_SList *
696 GNUNET_REGEX_move (struct GNUNET_REGEX_Automaton *a, struct State *s,
699 struct GNUNET_CONTAINER_SList *l;
700 struct GNUNET_CONTAINER_SList_Iterator it;
701 struct Transition *ctran;
703 if (!GNUNET_CONTAINER_slist_contains (a->states, s, sizeof *s))
705 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
706 "State %s is not part of the given automaton", s->name);
710 l = GNUNET_CONTAINER_slist_create ();
712 for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
713 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
714 GNUNET_CONTAINER_slist_next (&it))
716 ctran = GNUNET_CONTAINER_slist_get (&it, NULL);
717 if (literal == ctran->literal)
718 GNUNET_CONTAINER_slist_add (l, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
719 ctran->state, sizeof *(ctran->state));
721 GNUNET_CONTAINER_slist_iter_destroy (&it);
727 * Construct an NFA by parsing the regex string of length 'len'.
729 * @param regex regular expression string
730 * @param len length of the string
732 * @return NFA.Needs to be freed using GNUNET_REGEX_destroy_automaton
734 struct GNUNET_REGEX_Automaton *
735 GNUNET_REGEX_construct_nfa(const char *regex, const size_t len)
737 struct GNUNET_REGEX_Context ctx;
738 struct GNUNET_REGEX_Automaton *nfa;
741 unsigned int altcount;
742 unsigned int atomcount;
750 GNUNET_REGEX_context_init (&ctx);
758 for (count = 0; count < len && *regex; count++, regex++)
766 nfa_add_concatenation (&ctx);
768 GNUNET_array_grow (p, pcount, pcount + 1);
769 p[pcount - 1].altcount = altcount;
770 p[pcount - 1].atomcount = atomcount;
777 error_msg = "Cannot append '|' to nothing";
780 while (--atomcount > 0)
781 nfa_add_concatenation (&ctx);
787 error_msg = "Missing opening '('";
794 altcount = p[pcount].altcount;
795 atomcount = p[pcount].atomcount;
798 while (--atomcount > 0)
799 nfa_add_concatenation (&ctx);
800 for (; altcount > 0; altcount--)
801 nfa_add_alternation (&ctx);
803 altcount = p[pcount].altcount;
804 atomcount = p[pcount].atomcount;
810 error_msg = "Cannot append '+' to nothing";
813 nfa_add_star_op (&ctx);
818 error_msg = "Cannot append '+' to nothing";
821 nfa_add_plus_op (&ctx);
823 case 92: /* escape: \ */
830 nfa_add_concatenation (&ctx);
832 nfa_add_literal (&ctx, *regex);
839 error_msg = "Unbalanced parenthesis";
842 while (--atomcount > 0)
843 nfa_add_concatenation (&ctx);
844 for (; altcount > 0; altcount--)
845 nfa_add_alternation (&ctx);
850 nfa = stack_pop (ctx.stack, sizeof (struct GNUNET_REGEX_Automaton));
852 if (!stack_empty (ctx.stack))
854 error_msg = "Creating the NFA failed. NFA stack was not empty!";
858 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
859 "Created NFA with %i States and a total of %i Transitions\n",
860 GNUNET_CONTAINER_slist_count (nfa->states), ctx.transition_id);
862 GNUNET_REGEX_context_destroy (&ctx);
867 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
868 if (NULL != error_msg)
869 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
871 while (!stack_empty (ctx.stack))
872 GNUNET_REGEX_automaton_destroy (stack_pop (ctx.stack,
873 sizeof (struct GNUNET_REGEX_Automaton)));
874 GNUNET_REGEX_context_destroy (&ctx);
879 * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
882 * @param a automaton to be destroyed
885 GNUNET_REGEX_automaton_destroy(struct GNUNET_REGEX_Automaton *a)
887 struct GNUNET_CONTAINER_SList_Iterator it;
892 for (it = GNUNET_CONTAINER_slist_begin (a->states);
893 GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
894 GNUNET_CONTAINER_slist_next (&it))
896 automaton_destroy_state (GNUNET_CONTAINER_slist_get (&it, NULL));
898 GNUNET_CONTAINER_slist_iter_destroy (&it);
899 GNUNET_CONTAINER_slist_destroy (a->states);
904 * Construct DFA for the given 'regex' of lenght 'len'
906 * @param regex regular expression string
907 * @param len length of the regular expression
909 * @return DFA. Needs to be freed using GNUNET_REGEX_destroy_automaton
911 struct GNUNET_REGEX_Automaton *
912 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
914 struct GNUNET_REGEX_Context ctx;
915 struct GNUNET_REGEX_Automaton *dfa;
916 struct GNUNET_REGEX_Automaton *nfa;
917 struct GNUNET_CONTAINER_SList *tmp;
918 struct GNUNET_CONTAINER_SList *nfa_set;
919 struct GNUNET_CONTAINER_SList *sset;
920 struct GNUNET_CONTAINER_SList *dfa_stack;
921 struct GNUNET_CONTAINER_SList_Iterator tranit;
922 struct Transition *currenttransition;
923 struct State *dfa_state;
924 struct State *new_dfa_state;
925 struct State *state_contains;
927 GNUNET_REGEX_context_init (&ctx);
930 nfa = GNUNET_REGEX_construct_nfa (regex, len);
932 dfa_stack = GNUNET_CONTAINER_slist_create ();
934 // Initialize new dfa
935 dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
936 dfa->states = GNUNET_CONTAINER_slist_create ();
938 // Create DFA start state from epsilon closure
939 sset = GNUNET_CONTAINER_slist_create ();
940 GNUNET_CONTAINER_slist_add (sset, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
941 nfa->start, sizeof *(nfa->start));
942 nfa_set = create_nfa_closure (sset, 0);
943 GNUNET_CONTAINER_slist_destroy (sset);
944 dfa->start = dfa_create_state (&ctx, nfa_set);
945 GNUNET_CONTAINER_slist_add (dfa->states,
946 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
947 dfa->start, sizeof *(dfa->start));
948 stack_push (dfa_stack, dfa->start, sizeof *(dfa->start));
950 while (!stack_empty (dfa_stack))
952 dfa_state = stack_pop (dfa_stack, sizeof (struct State));
954 for (tranit = GNUNET_CONTAINER_slist_begin (dfa_state->transitions);
955 GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
956 GNUNET_CONTAINER_slist_next (&tranit))
958 currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
960 if (0 != currenttransition->literal && NULL == currenttransition->state)
962 tmp = create_nfa_closure (dfa_state->nfa_set,
963 currenttransition->literal);
964 nfa_set = create_nfa_closure (tmp, 0);
965 new_dfa_state = dfa_create_state (&ctx, nfa_set);
966 GNUNET_CONTAINER_slist_destroy (tmp);
969 GNUNET_CONTAINER_slist_contains2 (dfa->states, new_dfa_state,
970 sizeof *new_dfa_state,
972 if (NULL == state_contains)
974 GNUNET_CONTAINER_slist_add_end (dfa->states,
975 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
976 new_dfa_state, sizeof *new_dfa_state);
977 stack_push (dfa_stack, new_dfa_state, sizeof *new_dfa_state);
978 currenttransition->state = new_dfa_state;
981 currenttransition->state = state_contains;
985 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
987 GNUNET_CONTAINER_slist_destroy (dfa_stack);
988 GNUNET_REGEX_automaton_destroy (nfa);
989 GNUNET_REGEX_context_destroy (&ctx);
990 dfa_clear_nfa_set (dfa->states);
992 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
993 GNUNET_CONTAINER_slist_count (dfa->states));
999 * Save the given automaton as a GraphViz dot file
1001 * @param a the automaton to be saved
1002 * @param filename where to save the file
1005 GNUNET_REGEX_automaton_save_graph(struct GNUNET_REGEX_Automaton *a,
1006 const char *filename)
1008 struct GNUNET_CONTAINER_SList_Iterator stateit;
1009 struct GNUNET_CONTAINER_SList_Iterator tranit;
1011 struct Transition *ctran;
1013 char *s_tran = NULL;
1020 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1024 if (NULL == filename || strlen (filename) < 1)
1026 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1030 p = fopen (filename, "w");
1034 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1039 start = "digraph G {\nrankdir=LR\n";
1040 fwrite (start, strlen (start), 1, p);
1042 for (stateit = GNUNET_CONTAINER_slist_begin (a->states);
1043 GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
1044 GNUNET_CONTAINER_slist_next (&stateit))
1047 s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
1051 GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1052 fwrite (s_acc, strlen (s_acc), 1, p);
1053 GNUNET_free (s_acc);
1058 for (tranit = GNUNET_CONTAINER_slist_begin (s->transitions);
1059 GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
1060 GNUNET_CONTAINER_slist_next (&tranit))
1062 ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
1064 if (NULL == ctran->state)
1066 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1067 "Transition from State %i has has no state for transitioning\n",
1072 if (ctran->literal == 0)
1074 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1075 s->name, ctran->state->name);
1079 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1080 s->name, ctran->state->name, ctran->literal);
1083 fwrite (s_tran, strlen (s_tran), 1, p);
1084 GNUNET_free (s_tran);
1086 GNUNET_CONTAINER_slist_iter_destroy (&tranit);
1088 GNUNET_CONTAINER_slist_iter_destroy (&stateit);
1091 fwrite (end, strlen (end), 1, p);