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_regex_lib.h"
35 static struct Stack *nfa_stack = NULL;
38 push (void *val, struct Stack **stack)
40 struct Stack *new = GNUNET_malloc (sizeof (struct Stack *));
44 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not push to stack\n");
53 empty (struct Stack **stack)
55 return (NULL == *stack || NULL == stack);
59 pop (struct Stack **stack)
75 top (struct Stack **stack)
80 return (*stack)->data;
88 struct Transition *transitions;
95 struct State **states;
99 struct GNUNET_REGEX_Automaton
104 struct StateSet sset;
114 struct GNUNET_REGEX_Context
116 unsigned int state_id;
117 unsigned int transition_id;
121 dfa_create_state (struct GNUNET_REGEX_Context *ctx, struct StateSet *sset, int accepting)
127 s = GNUNET_malloc (sizeof (struct State));
128 s->id = ctx->state_id++;
129 s->accepting = accepting;
131 s->transitions = NULL;
135 if (0 == sset->count)
138 s->name = GNUNET_malloc ( strlen ("{"));
139 strcat (s->name, "{");
141 for (i=0; i<sset->count; i++)
143 name = GNUNET_malloc (sizeof (char));
144 GNUNET_asprintf (&name, "%i,", sset->states[i]->id);
145 s->name = GNUNET_realloc (s->name, strlen (s->name) + strlen (name) + 1);
146 strcat (s->name, name);
149 s->name[strlen (s->name)-1] = '}';
151 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA state with name: %s\n", s->name);
156 struct GNUNET_REGEX_Automaton *
157 nfa_create (struct State *start, struct State *end)
159 struct GNUNET_REGEX_Automaton *n;
160 struct StateSet sset;
162 n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
164 if (NULL == start && NULL == end)
175 sset.states = GNUNET_malloc ((sizeof (struct State *)) * 2);
176 sset.states[0] = start;
177 sset.states[1] = end;
189 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct StateSet *sset)
195 GNUNET_array_grow (n->sset.states, n->sset.count, n->sset.count + sset->count);
196 for (j = 0; i < n->sset.count && j < sset->count; i++, j++)
198 n->sset.states[i] = sset->states[j];
204 nfa_create_state (struct GNUNET_REGEX_Context *ctx, int accepting)
208 s = GNUNET_malloc (sizeof (struct State));
209 s->id = ctx->state_id++;
210 s->accepting = accepting;
212 s->transitions = NULL;
215 GNUNET_asprintf (&s->name, "s%i", s->id);
221 automaton_destroy_state (struct State *s)
224 GNUNET_free (s->transitions);
226 GNUNET_free (s->name);
231 nfa_add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state, const char literal,
232 struct State *to_state)
236 if (NULL == from_state || NULL == to_state)
238 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
242 t.id = ctx->transition_id++;
246 if (0 == from_state->tcnt)
247 from_state->transitions = NULL;
249 GNUNET_array_append (from_state->transitions, from_state->tcnt, t);
253 mark_all_states (struct GNUNET_REGEX_Automaton *n, int marked)
257 for (i = 0; i < n->sset.count; i++)
259 n->sset.states[i]->marked = marked;
264 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
266 struct GNUNET_REGEX_Automaton *A;
267 struct GNUNET_REGEX_Automaton *B;
268 struct GNUNET_REGEX_Automaton *new;
270 B = pop (&nfa_stack);
271 A = pop (&nfa_stack);
273 if (NULL == A || NULL == B)
275 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
276 "nfa_add_concatenationenation failed, because there were not enough elements on the stack");
280 nfa_add_transition (ctx, A->end, 0, B->start);
281 A->end->accepting = 0;
282 B->end->accepting = 1;
284 new = nfa_create (NULL, NULL);
285 nfa_add_states (new, &A->sset);
286 nfa_add_states (new, &B->sset);
287 new->start = A->start;
292 push (new, &nfa_stack);
296 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
298 struct GNUNET_REGEX_Automaton *A;
299 struct GNUNET_REGEX_Automaton *new;
303 A = pop (&nfa_stack);
307 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
308 "nfa_add_star_op failed, because there was no element on the stack");
312 start = nfa_create_state (ctx, 0);
313 end = nfa_create_state (ctx, 1);
315 nfa_add_transition (ctx, start, 0, A->start);
316 nfa_add_transition (ctx, start, 0, end);
317 nfa_add_transition (ctx, A->end, 0, A->start);
318 nfa_add_transition (ctx, A->end, 0, end);
320 A->end->accepting = 0;
323 new = nfa_create (start, end);
324 nfa_add_states (new, &A->sset);
327 push (new, &nfa_stack);
331 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
333 struct GNUNET_REGEX_Automaton *A;
335 A = pop (&nfa_stack);
339 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
340 "nfa_add_plus_op failed, because there was no element on the stack");
344 nfa_add_transition (ctx, A->end, 0, A->start);
346 push (A, &nfa_stack);
350 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
352 struct GNUNET_REGEX_Automaton *A;
353 struct GNUNET_REGEX_Automaton *B;
354 struct GNUNET_REGEX_Automaton *new;
358 B = pop (&nfa_stack);
359 A = pop (&nfa_stack);
361 if (NULL == A || NULL == B)
363 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
364 "alternation failed, because there were not enough elements on the stack");
368 start = nfa_create_state (ctx, 0);
369 end = nfa_create_state (ctx, 1);
370 nfa_add_transition (ctx, start, 0, A->start);
371 nfa_add_transition (ctx, start, 0, B->start);
373 nfa_add_transition (ctx, A->end, 0, end);
374 nfa_add_transition (ctx, B->end, 0, end);
376 A->end->accepting = 0;
377 B->end->accepting = 0;
380 new = nfa_create (start, end);
381 nfa_add_states (new, &A->sset);
382 nfa_add_states (new, &B->sset);
386 push (new, &nfa_stack);
390 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
392 struct GNUNET_REGEX_Automaton *n;
396 start = nfa_create_state (ctx, 0);
397 end = nfa_create_state (ctx, 1);
398 nfa_add_transition (ctx, start, lit, end);
399 n = nfa_create (start, end);
400 push (n, &nfa_stack);
404 * Calculates the closure set for the given set of states.
406 * @param states set of states for which to calculate the closure
407 * @param count number of states in 'states'
408 * @param literal for the transition
410 * @return set of states that can be reached from the given 'states' when
411 * using only 'literal' transitions
414 nfa_closure (struct State **states, unsigned int count, const char literal)
416 struct Stack *cls_check;
421 struct State *currentstate;
422 struct State *clsstate;
425 for (scnt=0; scnt < count; scnt++)
432 // Add start state to closure
433 GNUNET_array_append (cls.states, cls.count, s);
434 push (s, &cls_check);
436 while (!empty(&cls_check))
438 currentstate = pop(&cls_check);
440 for (tcnt=0; tcnt<currentstate->tcnt; tcnt++)
442 if (NULL != currentstate->transitions[tcnt].state
443 && literal == currentstate->transitions[tcnt].literal)
445 clsstate = currentstate->transitions[tcnt].state;
447 if (NULL == clsstate)
450 GNUNET_array_append (cls.states, cls.count, clsstate);
451 push (clsstate, &cls_check);
460 struct GNUNET_REGEX_Automaton *
461 GNUNET_REGEX_construct_nfa (const char *regex, size_t len)
463 struct GNUNET_REGEX_Context ctx;
464 struct GNUNET_REGEX_Automaton *nfa;
467 unsigned int altcount;
468 unsigned int atomcount;
482 ctx.transition_id = 0;
484 for (count = 0; count < len && *regex; count++, regex++)
492 nfa_add_concatenation (&ctx);
494 GNUNET_array_grow (p, pcount, pcount + 1);
495 p[pcount - 1].altcount = altcount;
496 p[pcount - 1].atomcount = atomcount;
503 error_msg = "Cannot append '|' to nothing";
506 while (--atomcount > 0)
507 nfa_add_concatenation (&ctx);
513 error_msg = "Missing opening '('";
520 altcount = p[pcount].altcount;
521 atomcount = p[pcount].atomcount;
524 while (--atomcount > 0)
525 nfa_add_concatenation (&ctx);
526 for (; altcount > 0; altcount--)
527 nfa_add_alternation (&ctx);
529 altcount = p[pcount].altcount;
530 atomcount = p[pcount].atomcount;
536 error_msg = "Cannot append '+' to nothing";
539 nfa_add_star_op (&ctx);
544 error_msg = "Cannot append '+' to nothing";
547 nfa_add_plus_op (&ctx);
549 case 92: /* escape: \ */
556 nfa_add_concatenation (&ctx);
558 nfa_add_literal (&ctx, *regex);
565 error_msg = "Unbalanced parenthesis";
568 while (--atomcount > 0)
569 nfa_add_concatenation (&ctx);
570 for (; altcount > 0; altcount--)
571 nfa_add_alternation (&ctx);
576 nfa = pop (&nfa_stack);
578 if (!empty (&nfa_stack))
580 error_msg = "Creating the NFA failed. NFA stack was not empty!";
584 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
585 "Created NFA with %i States and a total of %i Transitions\n",
586 ctx.state_id, ctx.transition_id);
591 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
592 if (NULL != error_msg)
593 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
595 while (!empty (&nfa_stack))
596 GNUNET_REGEX_destroy_automaton (pop (&nfa_stack));
601 GNUNET_REGEX_destroy_automaton (struct GNUNET_REGEX_Automaton *a)
608 for (i = 0; i < a->sset.count; i++)
610 automaton_destroy_state (a->sset.states[i]);
613 if (NULL != a->sset.states)
614 GNUNET_free (a->sset.states);
619 GNUNET_REGEX_save_nfa_graph (struct GNUNET_REGEX_Automaton *n, const char *filename)
630 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
634 if (NULL == filename || strlen (filename) < 1)
636 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
640 p = fopen (filename, "w");
644 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
649 start = "digraph G {\nrankdir=LR\n";
650 fwrite (start, strlen (start), 1, p);
652 for (scnt = 0; scnt < n->sset.count; scnt++)
654 struct Transition *ctran;
658 s = n->sset.states[scnt];
662 GNUNET_asprintf (&s_acc, "s%i [shape=doublecircle];\n", s->id);
663 fwrite (s_acc, strlen (s_acc), 1, p);
667 ctran = s->transitions;
670 for (tcnt = 0; tcnt < s->tcnt && NULL != ctran; tcnt++)
672 if (NULL == ctran->state)
674 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
675 "Transition from State %i has has no state for transitioning\n",
679 if (ctran->literal == 0)
681 GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"epsilon\"];\n", s->id,
686 GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"%c\"];\n", s->id,
687 ctran->state->id, ctran->literal);
690 fwrite (s_tran, strlen (s_tran), 1, p);
697 fwrite (end, strlen (end), 1, p);
701 struct GNUNET_REGEX_Automaton *
702 GNUNET_REGEX_construct_dfa (const char *regex, size_t len)
704 struct GNUNET_REGEX_Context ctx;
705 struct GNUNET_REGEX_Automaton *dfa;
706 struct GNUNET_REGEX_Automaton *nfa;
707 struct StateSet dfa_start_set;
708 struct State *dfa_start;
711 ctx.transition_id = 0;
714 nfa = GNUNET_REGEX_construct_nfa (regex, len);
716 // Create DFA start state from epsilon closure
717 dfa_start_set = nfa_closure (&nfa->start, 1, 0);
718 dfa_start = dfa_create_state (&ctx, &dfa_start_set, 0);
720 // ecls (move (dfa_start, lit))