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;
83 struct GNUNET_REGEX_Nfa
88 unsigned int statecnt;
89 struct State **states;
97 struct Transition *transitions;
108 static unsigned int state_id = 0;
109 static unsigned int transition_id = 0;
111 struct GNUNET_REGEX_Nfa *
112 nfa_create (struct State *start, struct State *end)
114 struct GNUNET_REGEX_Nfa *n;
116 n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Nfa));
118 if (NULL == start && NULL == end)
128 n->states = GNUNET_malloc ((sizeof (struct State *)) * 2);
129 n->states[0] = start;
141 nfa_add_states (struct GNUNET_REGEX_Nfa *n, struct State **states,
148 GNUNET_array_grow (n->states, n->statecnt, n->statecnt + count);
149 for (j = 0; i < n->statecnt && j < count; i++, j++)
151 n->states[i] = states[j];
157 nfa_create_state (int accepting)
161 s = GNUNET_malloc (sizeof (struct State));
163 s->accepting = accepting;
165 s->transitions = NULL;
172 nfa_destroy_state (struct State *s)
175 GNUNET_free (s->transitions);
180 nfa_add_transition (struct State *from_state, const char literal,
181 struct State *to_state)
185 if (NULL == from_state || NULL == to_state)
187 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
191 t.id = transition_id++;
195 if (0 == from_state->tcnt)
196 from_state->transitions = NULL;
198 GNUNET_array_append (from_state->transitions, from_state->tcnt, t);
202 mark_all_states (struct GNUNET_REGEX_Nfa *n, int visited)
206 for (i = 0; i < n->statecnt; i++)
208 n->states[i]->visited = visited;
213 nfa_add_concatenation ()
215 struct GNUNET_REGEX_Nfa *A;
216 struct GNUNET_REGEX_Nfa *B;
217 struct GNUNET_REGEX_Nfa *new;
219 B = pop (&nfa_stack);
220 A = pop (&nfa_stack);
222 if (NULL == A || NULL == B)
224 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
225 "nfa_add_concatenationenation failed, because there were not enough elements on the stack");
229 nfa_add_transition (A->end, 0, B->start);
230 A->end->accepting = 0;
231 B->end->accepting = 1;
233 new = nfa_create (NULL, NULL);
234 nfa_add_states (new, A->states, A->statecnt);
235 nfa_add_states (new, B->states, B->statecnt);
236 new->start = A->start;
238 GNUNET_free (A->states);
240 GNUNET_free (B->states);
243 push (new, &nfa_stack);
249 struct GNUNET_REGEX_Nfa *A;
250 struct GNUNET_REGEX_Nfa *new;
254 A = pop (&nfa_stack);
258 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
259 "nfa_add_star_op failed, because there was no element on the stack");
263 start = nfa_create_state (0);
264 end = nfa_create_state (1);
266 nfa_add_transition (start, 0, A->start);
267 nfa_add_transition (start, 0, end);
268 nfa_add_transition (A->end, 0, A->start);
269 nfa_add_transition (A->end, 0, end);
271 A->end->accepting = 0;
274 new = nfa_create (start, end);
275 nfa_add_states (new, A->states, A->statecnt);
276 GNUNET_free (A->states);
279 push (new, &nfa_stack);
285 struct GNUNET_REGEX_Nfa *A;
287 A = pop (&nfa_stack);
291 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
292 "nfa_add_plus_op failed, because there was no element on the stack");
296 nfa_add_transition (A->end, 0, A->start);
298 push (A, &nfa_stack);
302 nfa_add_alternation ()
304 struct GNUNET_REGEX_Nfa *A;
305 struct GNUNET_REGEX_Nfa *B;
306 struct GNUNET_REGEX_Nfa *new;
310 B = pop (&nfa_stack);
311 A = pop (&nfa_stack);
313 if (NULL == A || NULL == B)
315 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
316 "alternation failed, because there were not enough elements on the stack");
320 start = nfa_create_state (0);
321 end = nfa_create_state (1);
322 nfa_add_transition (start, 0, A->start);
323 nfa_add_transition (start, 0, B->start);
325 nfa_add_transition (A->end, 0, end);
326 nfa_add_transition (B->end, 0, end);
328 A->end->accepting = 0;
329 B->end->accepting = 0;
332 new = nfa_create (start, end);
333 nfa_add_states (new, A->states, A->statecnt);
334 nfa_add_states (new, B->states, B->statecnt);
335 GNUNET_free (A->states);
337 GNUNET_free (B->states);
340 push (new, &nfa_stack);
344 nfa_add_literal (const char lit)
346 struct GNUNET_REGEX_Nfa *n;
350 start = nfa_create_state (0);
351 end = nfa_create_state (1);
352 nfa_add_transition (start, lit, end);
353 n = nfa_create (start, end);
354 push (n, &nfa_stack);
357 struct GNUNET_REGEX_Nfa *
358 GNUNET_REGEX_construct_nfa (const char *regex, size_t len)
360 struct GNUNET_REGEX_Nfa *nfa;
362 unsigned int altcount;
363 unsigned int atomcount;
378 for (count = 0; count < len && *regex; count++, regex++)
387 nfa_add_concatenation ();
389 GNUNET_array_grow (p, pcount, pcount + 1);
390 p[pcount - 1].altcount = altcount;
391 p[pcount - 1].atomcount = atomcount;
398 while (--atomcount > 0)
399 nfa_add_concatenation ();
407 while (--atomcount > 0)
408 nfa_add_concatenation ();
409 for (; altcount > 0; altcount--)
410 nfa_add_alternation ();
412 altcount = p[pcount].altcount;
413 atomcount = p[pcount].atomcount;
426 case 92: /* escape: \ */
433 nfa_add_concatenation ();
435 nfa_add_literal (*regex);
442 while (--atomcount > 0)
443 nfa_add_concatenation ();
444 for (; altcount > 0; altcount--)
445 nfa_add_alternation ();
450 nfa = pop (&nfa_stack);
452 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
453 "Created NFA with %i States and a total of %i Transitions\n",
454 state_id, transition_id);
459 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
461 while (!empty (&nfa_stack))
462 GNUNET_REGEX_destroy_nfa (pop (&nfa_stack));
467 GNUNET_REGEX_destroy_nfa (struct GNUNET_REGEX_Nfa *n)
471 for (i = 0; i < n->statecnt; i++)
473 nfa_destroy_state (n->states[i]);
476 GNUNET_free (n->states);
481 GNUNET_REGEX_save_nfa_graph (struct GNUNET_REGEX_Nfa *n, const char *filename)
493 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
497 mark_all_states (n, 0);
499 states = GNUNET_malloc (sizeof (char));
502 for (i_s = 0; i_s < n->statecnt; i_s++)
504 struct Transition *ctran;
512 GNUNET_asprintf (&s_acc, "s%i [shape=doublecircle];\n", s->id);
514 states = GNUNET_realloc (states, strlen (states) + strlen (s_acc) + 1);
515 strcat (states, s_acc);
519 ctran = s->transitions;
522 for (i_t = 0; i_t < s->tcnt && NULL != s->transitions; i_t++)
526 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "s->transitions was NULL\n");
529 if (NULL == ctran->state)
531 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
532 "Transition from State %i has has no state for transitioning\n",
536 if (ctran->literal == 0)
538 GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"epsilon\"];\n", s->id,
543 GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"%c\"];\n", s->id,
544 ctran->state->id, ctran->literal);
547 states = GNUNET_realloc (states, strlen (states) + strlen (s_tran) + 1);
548 strcat (states, s_tran);
549 GNUNET_free (s_tran);
557 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA");
561 if (NULL == filename || strlen (filename) < 1)
563 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
564 GNUNET_free (states);
568 p = fopen (filename, "w");
571 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
573 GNUNET_free (states);
577 start = "digraph G {\nrankdir=LR\n";
579 fwrite (start, strlen (start), 1, p);
580 fwrite (states, strlen (states), 1, p);
581 fwrite (end, strlen (end), 1, p);
584 GNUNET_free (states);