src/regex/regex.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012 Christian Grothoff (and other contributing authors)
   4
   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.
   9
  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.
  14
  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.
  19 */
  20 /**
  21  * @file src/regex/regex.c
  22  * @brief library to create automatons from regular expressions
  23  * @author Maximilian Szengel
  24  */
  25 #include "platform.h"
  26 #include "gnunet_container_lib.h"
  27 #include "gnunet_regex_lib.h"
  28 #include "regex.h"
  29
  30 /**
  31  * Context that contains an id counter for states and transitions
  32  * as well as a DLL of automatons used as a stack for NFA construction.
  33  */
  34 struct GNUNET_REGEX_Context
  35 {
  36   unsigned int state_id;
  37   unsigned int transition_id;
  38
  39   /**
  40    * DLL of GNUNET_REGEX_Automaton's used as a stack
  41    */
  42   struct GNUNET_REGEX_Automaton *stack_head;
  43   struct GNUNET_REGEX_Automaton *stack_tail;
  44 };
  45
  46 enum GNUNET_REGEX_automaton_type
  47 {
  48   NFA,
  49   DFA
  50 };
  51
  52 /**
  53  * Automaton representation
  54  */
  55 struct GNUNET_REGEX_Automaton
  56 {
  57   struct GNUNET_REGEX_Automaton *prev;
  58   struct GNUNET_REGEX_Automaton *next;
  59
  60   struct State *start;
  61   struct State *end;
  62
  63   struct State *states_head;
  64   struct State *states_tail;
  65
  66   enum GNUNET_REGEX_automaton_type type;
  67 };
  68
  69 /**
  70  * A state. Can be used in DFA and NFA automatons.
  71  */
  72 struct State
  73 {
  74   struct State *prev;
  75   struct State *next;
  76
  77   unsigned int id;
  78   int accepting;
  79   int marked;
  80   char *name;
  81
  82   struct Transition *transitions_head;
  83   struct Transition *transitions_tail;
  84
  85   struct StateSet *nfa_set;
  86 };
  87
  88 /**
  89  * Transition between two states. Each state can have 0-n transitions.
  90  * If literal is 0, this is considered to be an epsilon transition.
  91  */
  92 struct Transition
  93 {
  94   struct Transition *prev;
  95   struct Transition *next;
  96
  97   unsigned int id;
  98   char literal;
  99   struct State *state;
 100 };
 101
 102 /**
 103  * Set of states
 104  */
 105 struct StateSet
 106 {
 107   /**
 108    * Array of states
 109    */
 110   struct State **states;
 111   unsigned int len;
 112 };
 113
 114 /**
 115  * Initialize a new context
 116  *
 117  * @param ctx context
 118  */
 119 void
 120 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
 121 {
 122   if (NULL == ctx)
 123   {
 124     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
 125     return;
 126   }
 127   ctx->state_id = 0;
 128   ctx->transition_id = 0;
 129   ctx->stack_head = NULL;
 130   ctx->stack_tail = NULL;
 131 }
 132
 133 void
 134 debug_print_state (struct State *s)
 135 {
 136   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 137               "State %i: %s marked: %i accepting: %i\n", s->id, s->name,
 138               s->marked, s->accepting);
 139 }
 140
 141 void
 142 debug_print_states (struct StateSet *sset)
 143 {
 144   struct State *s;
 145   int i;
 146
 147   for (i = 0; i < sset->len; i++)
 148   {
 149     s = sset->states[i];
 150     debug_print_state (s);
 151   }
 152 }
 153
 154 void
 155 debug_print_transitions (struct State *s)
 156 {
 157   struct Transition *t;
 158   char *state;
 159   char literal;
 160
 161   for (t = s->transitions_head; NULL != t; t = t->next)
 162   {
 163     if (0 == t->literal)
 164       literal = '0';
 165     else
 166       literal = t->literal;
 167
 168     if (NULL == t->state)
 169       state = "NULL";
 170     else
 171       state = t->state->name;
 172
 173     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
 174                 literal, state);
 175   }
 176 }
 177
 178 /**
 179  * Compare to state sets by comparing the id's of the states that are
 180  * contained in each set.
 181  *
 182  * @param sset1 first state set
 183  * @param sset2 second state set
 184  *
 185  * @return 0 if they are equal, non 0 otherwise
 186  */
 187 int
 188 state_set_compare (struct StateSet *sset1, struct StateSet *sset2)
 189 {
 190   struct State *s1;
 191   struct State *s2;
 192   int i1;
 193   int i2;
 194   int contains;
 195   int rslt;
 196
 197   if (sset1->len < 1 || sset2->len < 1)
 198     return -1;
 199
 200   rslt = 0;
 201
 202   for (i1 = 0; i1 < sset1->len; i1++)
 203   {
 204     s1 = sset1->states[i1];
 205     contains = 0;
 206     for (i2 = 0; i2 < sset2->len; i2++)
 207     {
 208       s2 = sset2->states[i2];
 209       if (s1->id == s2->id)
 210       {
 211         contains = 1;
 212         break;
 213       }
 214     }
 215
 216     if (0 == contains)
 217     {
 218       rslt = 1;
 219       break;
 220     }
 221   }
 222   return rslt;
 223 }
 224
 225 /**
 226  * Checks if 'elem' is contained in 'set'
 227  *
 228  * @param set set of states
 229  * @param elem state
 230  *
 231  * @return GNUNET_YES if 'set' contains 'elem, GNUNET_NO otherwise
 232  */
 233 int
 234 state_set_contains (struct StateSet *set, struct State *elem)
 235 {
 236   struct State *s;
 237   int i;
 238
 239   for (i = 0; i < set->len; i++)
 240   {
 241     s = set->states[i];
 242     if (0 == memcmp (s, elem, sizeof (struct State)))
 243       return GNUNET_YES;
 244   }
 245   return GNUNET_NO;
 246 }
 247
 248 /**
 249  * Clears the given StateSet 'set'
 250  *
 251  * @param set set to be cleared
 252  */
 253 void
 254 state_set_clear (struct StateSet *set)
 255 {
 256   if (NULL != set)
 257   {
 258     if (NULL != set->states)
 259       GNUNET_free (set->states);
 260     GNUNET_free (set);
 261   }
 262 }
 263
 264 /**
 265  * Adds a transition from one state to another on 'literal'
 266  *
 267  * @param ctx context
 268  * @param from_state starting state for the transition
 269  * @param literal transition label
 270  * @param to_state state to where the transition should point to
 271  */
 272 void
 273 add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state,
 274                 const char literal, struct State *to_state)
 275 {
 276   struct Transition *t;
 277
 278   if (NULL == from_state)
 279   {
 280     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 281     return;
 282   }
 283
 284   t = GNUNET_malloc (sizeof (struct Transition));
 285
 286   t->id = ctx->transition_id++;
 287   t->literal = literal;
 288   t->state = to_state;
 289
 290   GNUNET_CONTAINER_DLL_insert (from_state->transitions_head,
 291                                from_state->transitions_tail, t);
 292 }
 293
 294 /**
 295  * Clears an automaton fragment. Does not destroy the states inside
 296  * the automaton.
 297  *
 298  * @param a automaton to be cleared
 299  */
 300 void
 301 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
 302 {
 303   a->start = NULL;
 304   a->end = NULL;
 305   a->states_head = NULL;
 306   a->states_tail = NULL;
 307   GNUNET_free (a);
 308 }
 309
 310 /**
 311  * Frees the memory used by State 's'
 312  *
 313  * @param s state that should be destroyed
 314  */
 315 void
 316 automaton_destroy_state (struct State *s)
 317 {
 318   struct Transition *t;
 319   struct Transition *next_t;
 320
 321   if (NULL != s->name)
 322     GNUNET_free (s->name);
 323
 324   for (t = s->transitions_head; NULL != t;)
 325   {
 326     next_t = t->next;
 327     GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
 328     GNUNET_free (t);
 329     t = next_t;
 330   }
 331
 332   state_set_clear (s->nfa_set);
 333
 334   GNUNET_free (s);
 335 }
 336
 337 /**
 338  * Creates a new DFA state based on a set of NFA states. Needs to be freed
 339  * using automaton_destroy_state.
 340  *
 341  * @param ctx context
 342  * @param nfa_states set of NFA states on which the DFA should be based on
 343  *
 344  * @return new DFA state
 345  */
 346 struct State *
 347 dfa_state_create (struct GNUNET_REGEX_Context *ctx, struct StateSet *nfa_states)
 348 {
 349   struct State *s;
 350   char *name;
 351   int len = 0;
 352   struct State *cstate;
 353   struct Transition *ctran;
 354   int insert = 1;
 355   struct Transition *t;
 356   int i;
 357
 358   s = GNUNET_malloc (sizeof (struct State));
 359   s->id = ctx->state_id++;
 360   s->accepting = 0;
 361   s->marked = 0;
 362   s->name = NULL;
 363
 364   if (NULL == nfa_states)
 365     return s;
 366
 367   s->nfa_set = nfa_states;
 368
 369   if (nfa_states->len < 1)
 370     return s;
 371
 372   // Create a name based on 'sset'
 373   s->name = GNUNET_malloc (sizeof (char) * 2);
 374   strcat (s->name, "{");
 375   name = NULL;
 376
 377   for (i = 0; i < nfa_states->len; i++)
 378   {
 379     cstate = nfa_states->states[i];
 380     GNUNET_asprintf (&name, "%i,", cstate->id);
 381
 382     if (NULL != name)
 383     {
 384       len = strlen (s->name) + strlen (name) + 1;
 385       s->name = GNUNET_realloc (s->name, len);
 386       strcat (s->name, name);
 387       GNUNET_free (name);
 388       name = NULL;
 389     }
 390
 391     // Add a transition for each distinct literal to NULL state
 392     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
 393     {
 394       if (0 != ctran->literal)
 395       {
 396         insert = 1;
 397
 398         for (t = s->transitions_head; NULL != t; t = t->next)
 399         {
 400           if (t->literal == ctran->literal)
 401           {
 402             insert = 0;
 403             break;
 404           }
 405         }
 406
 407         if (insert)
 408           add_transition (ctx, s, ctran->literal, NULL);
 409       }
 410     }
 411
 412     // If the nfa_states contain an accepting state, the new dfa state is also accepting
 413     if (cstate->accepting)
 414       s->accepting = 1;
 415   }
 416
 417   s->name[strlen (s->name) - 1] = '}';
 418
 419   return s;
 420 }
 421
 422 struct State *
 423 dfa_move (struct State *s, const char literal)
 424 {
 425   struct Transition *t;
 426   struct State *new_s;
 427
 428   if (NULL == s)
 429     return NULL;
 430
 431   new_s = NULL;
 432
 433   for (t = s->transitions_head; NULL != t; t = t->next)
 434   {
 435     if (literal == t->literal)
 436     {
 437       new_s = t->state;
 438       break;
 439     }
 440   }
 441
 442   return new_s;
 443 }
 444
 445 /**
 446  * Creates a new NFA fragment. Needs to be cleared using automaton_fragment_clear.
 447  *
 448  * @param start starting state
 449  * @param end end state
 450  *
 451  * @return new NFA fragment
 452  */
 453 struct GNUNET_REGEX_Automaton *
 454 nfa_fragment_create (struct State *start, struct State *end)
 455 {
 456   struct GNUNET_REGEX_Automaton *n;
 457
 458   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 459
 460   n->type = NFA;
 461   n->start = NULL;
 462   n->end = NULL;
 463
 464   if (NULL == start && NULL == end)
 465     return n;
 466
 467   GNUNET_CONTAINER_DLL_insert (n->states_head, n->states_tail, end);
 468   GNUNET_CONTAINER_DLL_insert (n->states_head, n->states_tail, start);
 469
 470   n->start = start;
 471   n->end = end;
 472
 473   return n;
 474 }
 475
 476 /**
 477  * Adds a list of states to the given automaton 'n'.
 478  *
 479  * @param n automaton to which the states should be added
 480  * @param states_head head of the DLL of states
 481  * @param states_tail tail of the DLL of states
 482  */
 483 void
 484 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct State *states_head,
 485                 struct State *states_tail)
 486 {
 487   if (NULL == n || NULL == states_head)
 488   {
 489     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
 490     return;
 491   }
 492
 493   if (NULL == n->states_head)
 494   {
 495     n->states_head = states_head;
 496     n->states_tail = states_tail;
 497     return;
 498   }
 499
 500   if (NULL != states_head)
 501   {
 502     n->states_tail->next = states_head;
 503     n->states_tail = states_tail;
 504   }
 505 }
 506
 507 /**
 508  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
 509  *
 510  * @param ctx context
 511  * @param accepting is it an accepting state or not
 512  *
 513  * @return new NFA state
 514  */
 515 struct State *
 516 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
 517 {
 518   struct State *s;
 519
 520   s = GNUNET_malloc (sizeof (struct State));
 521   s->id = ctx->state_id++;
 522   s->accepting = accepting;
 523   s->marked = 0;
 524   s->name = NULL;
 525   GNUNET_asprintf (&s->name, "s%i", s->id);
 526
 527   return s;
 528 }
 529
 530 /**
 531  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 532  *
 533  * @param ctx context
 534  */
 535 void
 536 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 537 {
 538   struct GNUNET_REGEX_Automaton *a;
 539   struct GNUNET_REGEX_Automaton *b;
 540   struct GNUNET_REGEX_Automaton *new;
 541
 542   b = ctx->stack_tail;
 543   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 544   a = ctx->stack_tail;
 545   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 546
 547   add_transition (ctx, a->end, 0, b->start);
 548   a->end->accepting = 0;
 549   b->end->accepting = 1;
 550
 551   new = nfa_fragment_create (NULL, NULL);
 552   nfa_add_states (new, a->states_head, a->states_tail);
 553   nfa_add_states (new, b->states_head, b->states_tail);
 554   new->start = a->start;
 555   new->end = b->end;
 556   automaton_fragment_clear (a);
 557   automaton_fragment_clear (b);
 558
 559   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 560 }
 561
 562 /**
 563  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
 564  *
 565  * @param ctx context
 566  */
 567 void
 568 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 569 {
 570   struct GNUNET_REGEX_Automaton *a;
 571   struct GNUNET_REGEX_Automaton *new;
 572   struct State *start;
 573   struct State *end;
 574
 575   a = ctx->stack_tail;
 576   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 577
 578   if (NULL == a)
 579   {
 580     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 581                 "nfa_add_star_op failed, because there was no element on the stack");
 582     return;
 583   }
 584
 585   start = nfa_state_create (ctx, 0);
 586   end = nfa_state_create (ctx, 1);
 587
 588   add_transition (ctx, start, 0, a->start);
 589   add_transition (ctx, start, 0, end);
 590   add_transition (ctx, a->end, 0, a->start);
 591   add_transition (ctx, a->end, 0, end);
 592
 593   a->end->accepting = 0;
 594   end->accepting = 1;
 595
 596   new = nfa_fragment_create (start, end);
 597   nfa_add_states (new, a->states_head, a->states_tail);
 598   automaton_fragment_clear (a);
 599
 600   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 601 }
 602
 603 /**
 604  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
 605  *
 606  * @param ctx context
 607  */
 608 void
 609 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 610 {
 611   struct GNUNET_REGEX_Automaton *a;
 612
 613   a = ctx->stack_tail;
 614   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 615
 616   add_transition (ctx, a->end, 0, a->start);
 617
 618   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
 619 }
 620
 621 /**
 622  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
 623  * that alternates between a and b (a|b)
 624  *
 625  * @param ctx context
 626  */
 627 void
 628 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 629 {
 630   struct GNUNET_REGEX_Automaton *a;
 631   struct GNUNET_REGEX_Automaton *b;
 632   struct GNUNET_REGEX_Automaton *new;
 633   struct State *start;
 634   struct State *end;
 635
 636   b = ctx->stack_tail;
 637   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 638   a = ctx->stack_tail;
 639   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 640
 641   start = nfa_state_create (ctx, 0);
 642   end = nfa_state_create (ctx, 1);
 643   add_transition (ctx, start, 0, a->start);
 644   add_transition (ctx, start, 0, b->start);
 645
 646   add_transition (ctx, a->end, 0, end);
 647   add_transition (ctx, b->end, 0, end);
 648
 649   a->end->accepting = 0;
 650   b->end->accepting = 0;
 651   end->accepting = 1;
 652
 653   new = nfa_fragment_create (start, end);
 654   nfa_add_states (new, a->states_head, a->states_tail);
 655   nfa_add_states (new, b->states_head, b->states_tail);
 656   automaton_fragment_clear (a);
 657   automaton_fragment_clear (b);
 658
 659   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 660 }
 661
 662 /**
 663  * Adds a new nfa fragment to the stack
 664  *
 665  * @param ctx context
 666  * @param lit literal for nfa transition
 667  */
 668 void
 669 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 670 {
 671   struct GNUNET_REGEX_Automaton *n;
 672   struct State *start;
 673   struct State *end;
 674
 675   GNUNET_assert (NULL != ctx);
 676
 677   start = nfa_state_create (ctx, 0);
 678   end = nfa_state_create (ctx, 1);
 679   add_transition (ctx, start, lit, end);
 680   n = nfa_fragment_create (start, end);
 681   GNUNET_assert (NULL != n);
 682   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
 683 }
 684
 685 /**
 686  * Calculates the NFA closure set for the given state
 687  *
 688  * @param s starting point state
 689  * @param literal transitioning literal on which to base the closure on,
 690  *                pass 0 for epsilon transition
 691  *
 692  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 693  */
 694 struct StateSet *
 695 nfa_closure_create (struct State *s, const char literal)
 696 {
 697   struct StateSet *cls;
 698   struct StateSet *cls_check;
 699   struct State *clsstate;
 700   struct State *currentstate;
 701   struct Transition *ctran;
 702
 703   if (NULL == s)
 704     return NULL;
 705
 706   cls = GNUNET_malloc (sizeof (struct StateSet));
 707   cls_check = GNUNET_malloc (sizeof (struct StateSet));
 708
 709   // Add start state to closure only for epsilon closure
 710   if (0 == literal)
 711     GNUNET_array_append (cls->states, cls->len, s);
 712
 713   GNUNET_array_append (cls_check->states, cls_check->len, s);
 714   while (cls_check->len > 0)
 715   {
 716     currentstate = cls_check->states[cls_check->len - 1];
 717     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
 718
 719     for (ctran = currentstate->transitions_head; NULL != ctran;
 720          ctran = ctran->next)
 721     {
 722       if (NULL != ctran->state && literal == ctran->literal)
 723       {
 724         clsstate = ctran->state;
 725
 726         if (NULL != clsstate &&
 727             GNUNET_YES != state_set_contains (cls, clsstate))
 728         {
 729           GNUNET_array_append (cls->states, cls->len, clsstate);
 730           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
 731         }
 732       }
 733     }
 734   }
 735   GNUNET_assert (0 == cls_check->len);
 736   GNUNET_free (cls_check);
 737
 738   return cls;
 739 }
 740
 741 /**
 742  * Calculates the closure set for the given set of states.
 743  *
 744  * @param states list of states on which to base the closure on
 745  * @param literal transitioning literal for which to base the closure on,
 746  *                pass 0 for epsilon transition
 747  *
 748  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 749  */
 750 struct StateSet *
 751 nfa_closure_set_create (struct StateSet *states, const char literal)
 752 {
 753   struct State *s;
 754   struct StateSet *sset;
 755   struct StateSet *cls;
 756   int i;
 757   int j;
 758
 759   if (NULL == states)
 760     return NULL;
 761
 762   cls = GNUNET_malloc (sizeof (struct StateSet));
 763
 764   for (i = 0; i < states->len; i++)
 765   {
 766     s = states->states[i];
 767     sset = nfa_closure_create (s, literal);
 768
 769     for (j = 0; j < sset->len; j++)
 770       GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 771
 772     state_set_clear (sset);
 773   }
 774
 775   return cls;
 776 }
 777
 778 /**
 779  * Construct an NFA by parsing the regex string of length 'len'.
 780  *
 781  * @param regex regular expression string
 782  * @param len length of the string
 783  *
 784  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
 785  */
 786 struct GNUNET_REGEX_Automaton *
 787 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
 788 {
 789   struct GNUNET_REGEX_Context ctx;
 790   struct GNUNET_REGEX_Automaton *nfa;
 791   const char *regexp;
 792   char *error_msg;
 793   unsigned int count;
 794   unsigned int altcount;
 795   unsigned int atomcount;
 796   unsigned int pcount;
 797   struct
 798   {
 799     int altcount;
 800     int atomcount;
 801   }     *p;
 802
 803   GNUNET_REGEX_context_init (&ctx);
 804
 805   regexp = regex;
 806   p = NULL;
 807   error_msg = NULL;
 808   altcount = 0;
 809   atomcount = 0;
 810   pcount = 0;
 811
 812   for (count = 0; count < len && *regexp; count++, regexp++)
 813   {
 814     switch (*regexp)
 815     {
 816     case '(':
 817       if (atomcount > 1)
 818       {
 819         --atomcount;
 820         nfa_add_concatenation (&ctx);
 821       }
 822       GNUNET_array_grow (p, pcount, pcount + 1);
 823       p[pcount - 1].altcount = altcount;
 824       p[pcount - 1].atomcount = atomcount;
 825       altcount = 0;
 826       atomcount = 0;
 827       break;
 828     case '|':
 829       if (0 == atomcount)
 830       {
 831         error_msg = "Cannot append '|' to nothing";
 832         goto error;
 833       }
 834       while (--atomcount > 0)
 835         nfa_add_concatenation (&ctx);
 836       altcount++;
 837       break;
 838     case ')':
 839       if (0 == pcount)
 840       {
 841         error_msg = "Missing opening '('";
 842         goto error;
 843       }
 844       if (0 == atomcount)
 845       {
 846         // Ignore this: "()"
 847         pcount--;
 848         altcount = p[pcount].altcount;
 849         atomcount = p[pcount].atomcount;
 850         break;
 851       }
 852       while (--atomcount > 0)
 853         nfa_add_concatenation (&ctx);
 854       for (; altcount > 0; altcount--)
 855         nfa_add_alternation (&ctx);
 856       pcount--;
 857       altcount = p[pcount].altcount;
 858       atomcount = p[pcount].atomcount;
 859       atomcount++;
 860       break;
 861     case '*':
 862       if (atomcount == 0)
 863       {
 864         error_msg = "Cannot append '+' to nothing";
 865         goto error;
 866       }
 867       nfa_add_star_op (&ctx);
 868       break;
 869     case '+':
 870       if (atomcount == 0)
 871       {
 872         error_msg = "Cannot append '+' to nothing";
 873         goto error;
 874       }
 875       nfa_add_plus_op (&ctx);
 876       break;
 877     case 92:                   /* escape: \ */
 878       regexp++;
 879       count++;
 880     default:
 881       if (atomcount > 1)
 882       {
 883         --atomcount;
 884         nfa_add_concatenation (&ctx);
 885       }
 886       nfa_add_literal (&ctx, *regexp);
 887       atomcount++;
 888       break;
 889     }
 890   }
 891   if (0 != pcount)
 892   {
 893     error_msg = "Unbalanced parenthesis";
 894     goto error;
 895   }
 896   while (--atomcount > 0)
 897     nfa_add_concatenation (&ctx);
 898   for (; altcount > 0; altcount--)
 899     nfa_add_alternation (&ctx);
 900
 901   if (NULL != p)
 902     GNUNET_free (p);
 903
 904   nfa = ctx.stack_tail;
 905   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
 906
 907
 908   if (NULL != ctx.stack_head)
 909   {
 910     error_msg = "Creating the NFA failed. NFA stack was not empty!";
 911     goto error;
 912   }
 913
 914   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 915               "Created NFA with %i States and a total of %i Transitions\n",
 916               ctx.state_id, ctx.transition_id);
 917
 918   return nfa;
 919
 920 error:
 921   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
 922   if (NULL != error_msg)
 923     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
 924   GNUNET_free (p);
 925   while (NULL != ctx.stack_tail)
 926   {
 927     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
 928     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
 929                                  ctx.stack_tail);
 930   }
 931   return NULL;
 932 }
 933
 934 /**
 935  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
 936  * data structure.
 937  *
 938  * @param a automaton to be destroyed
 939  */
 940 void
 941 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
 942 {
 943   struct State *s;
 944   struct State *next_state;
 945
 946   if (NULL == a)
 947     return;
 948
 949   for (s = a->states_head; NULL != s;)
 950   {
 951     next_state = s->next;
 952     automaton_destroy_state (s);
 953     s = next_state;
 954   }
 955
 956   GNUNET_free (a);
 957 }
 958
 959 /**
 960  * Construct DFA for the given 'regex' of length 'len'
 961  *
 962  * @param regex regular expression string
 963  * @param len length of the regular expression
 964  *
 965  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
 966  */
 967 struct GNUNET_REGEX_Automaton *
 968 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
 969 {
 970   struct GNUNET_REGEX_Context ctx;
 971   struct GNUNET_REGEX_Automaton *dfa;
 972   struct GNUNET_REGEX_Automaton *nfa;
 973   struct StateSet *tmp;
 974   struct StateSet *nfa_set;
 975   struct StateSet *dfa_stack;
 976   struct Transition *ctran;
 977   struct State *dfa_state;
 978   struct State *new_dfa_state;
 979   struct State *state_contains;
 980   struct State *state_iter;
 981
 982   GNUNET_REGEX_context_init (&ctx);
 983
 984   // Create NFA
 985   nfa = GNUNET_REGEX_construct_nfa (regex, len);
 986
 987   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 988   dfa->type = DFA;
 989
 990   // Create DFA start state from epsilon closure
 991   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
 992   nfa_set = nfa_closure_create (nfa->start, 0);
 993   dfa->start = dfa_state_create (&ctx, nfa_set);
 994   GNUNET_CONTAINER_DLL_insert (dfa->states_head, dfa->states_tail, dfa->start);
 995   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
 996   while (dfa_stack->len > 0)
 997   {
 998     dfa_state = dfa_stack->states[dfa_stack->len - 1];
 999     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1000
1001     for (ctran = dfa_state->transitions_head; NULL != ctran;
1002          ctran = ctran->next)
1003     {
1004       if (0 != ctran->literal && NULL == ctran->state)
1005       {
1006         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1007         nfa_set = nfa_closure_set_create (tmp, 0);
1008         state_set_clear (tmp);
1009         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1010         state_contains = NULL;
1011         for (state_iter = dfa->states_head; NULL != state_iter;
1012              state_iter = state_iter->next)
1013         {
1014           if (0 ==
1015               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1016             state_contains = state_iter;
1017         }
1018
1019         if (NULL == state_contains)
1020         {
1021           GNUNET_CONTAINER_DLL_insert_tail (dfa->states_head, dfa->states_tail,
1022                                             new_dfa_state);
1023           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1024                                new_dfa_state);
1025           ctran->state = new_dfa_state;
1026         }
1027         else
1028         {
1029           ctran->state = state_contains;
1030           automaton_destroy_state (new_dfa_state);
1031         }
1032       }
1033     }
1034   }
1035
1036   GNUNET_free (dfa_stack);
1037   GNUNET_REGEX_automaton_destroy (nfa);
1038
1039   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
1040               ctx.state_id);
1041
1042   return dfa;
1043 }
1044
1045 /**
1046  * Save the given automaton as a GraphViz dot file
1047  *
1048  * @param a the automaton to be saved
1049  * @param filename where to save the file
1050  */
1051 void
1052 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1053                                    const char *filename)
1054 {
1055   struct State *s;
1056   struct Transition *ctran;
1057   char *s_acc = NULL;
1058   char *s_tran = NULL;
1059   char *start;
1060   char *end;
1061   FILE *p;
1062
1063   if (NULL == a)
1064   {
1065     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1066     return;
1067   }
1068
1069   if (NULL == filename || strlen (filename) < 1)
1070   {
1071     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1072     return;
1073   }
1074
1075   p = fopen (filename, "w");
1076
1077   if (p == NULL)
1078   {
1079     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1080                 filename);
1081     return;
1082   }
1083
1084   start = "digraph G {\nrankdir=LR\n";
1085   fwrite (start, strlen (start), 1, p);
1086
1087   for (s = a->states_head; NULL != s; s = s->next)
1088   {
1089     if (s->accepting)
1090     {
1091       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1092       fwrite (s_acc, strlen (s_acc), 1, p);
1093       GNUNET_free (s_acc);
1094     }
1095
1096     s->marked = 1;
1097
1098     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1099     {
1100       if (NULL == ctran->state)
1101       {
1102         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1103                     "Transition from State %i has has no state for transitioning\n",
1104                     s->id);
1105         continue;
1106       }
1107
1108       if (ctran->literal == 0)
1109       {
1110         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1111                          s->name, ctran->state->name);
1112       }
1113       else
1114       {
1115         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1116                          s->name, ctran->state->name, ctran->literal);
1117       }
1118
1119       fwrite (s_tran, strlen (s_tran), 1, p);
1120       GNUNET_free (s_tran);
1121     }
1122   }
1123
1124   end = "\n}\n";
1125   fwrite (end, strlen (end), 1, p);
1126   fclose (p);
1127 }
1128
1129 /**
1130  * Evaluates the given string using the given DFA automaton
1131  *
1132  * @param a automaton, type must be DFA
1133  * @param string string that should be evaluated
1134  *
1135  * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise
1136  */
1137 int
1138 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1139 {
1140   const char *strp;
1141   struct State *s;
1142
1143   if (DFA != a->type)
1144   {
1145     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1146                 "Tried to evaluate NFA, but DFA automaton given");
1147     return GNUNET_SYSERR;
1148   }
1149
1150   s = a->start;
1151
1152   for (strp = string; NULL != strp && *strp; strp++)
1153   {
1154     s = dfa_move (s, *strp);
1155     if (NULL == s)
1156       break;
1157   }
1158
1159   if (NULL != s && s->accepting)
1160     return GNUNET_YES;
1161
1162   return GNUNET_NO;
1163 }
1164
1165 /**
1166  * Evaluates the given string using the given NFA automaton
1167  *
1168  * @param a automaton, type must be NFA
1169  * @param string string that should be evaluated
1170  *
1171  * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise
1172  */
1173 int
1174 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1175 {
1176   const char *strp;
1177   struct State *s;
1178   struct StateSet *sset;
1179   struct StateSet *new_sset;
1180   int i;
1181   int eval;
1182
1183   if (NFA != a->type)
1184   {
1185     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1186                 "Tried to evaluate NFA, but DFA automaton given");
1187     return GNUNET_SYSERR;
1188   }
1189
1190   eval = GNUNET_NO;
1191   strp = string;
1192   sset = GNUNET_malloc (sizeof (struct StateSet));
1193   GNUNET_array_append (sset->states, sset->len, a->start);
1194
1195   for (strp = string; NULL != strp && *strp; strp++)
1196   {
1197     new_sset = nfa_closure_set_create (sset, *strp);
1198     state_set_clear (sset);
1199     sset = nfa_closure_set_create (new_sset, 0);
1200     state_set_clear (new_sset);
1201   }
1202
1203   for (i = 0; i < sset->len; i++)
1204   {
1205     s = sset->states[i];
1206     if (NULL != s && s->accepting)
1207     {
1208       eval = GNUNET_YES;
1209       break;
1210     }
1211   }
1212
1213   state_set_clear (sset);
1214   return eval;
1215 }
1216
1217
1218 /**
1219  * Evaluates the given 'string' against the given compiled regex
1220  *
1221  * @param a automaton
1222  * @param string string to check
1223  *
1224  * @return GNUNET_YES if 'a' matches 'string', GNUNET_NO otherwise
1225  */
1226 int
1227 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1228 {
1229   int eval;
1230
1231   switch (a->type)
1232   {
1233   case DFA:
1234     eval = evaluate_dfa (a, string);
1235     break;
1236   case NFA:
1237     eval = evaluate_nfa (a, string);
1238     break;
1239   default:
1240     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1241                 "Evaluating regex failed, automaton has no type!\n");
1242     eval = GNUNET_SYSERR;
1243     break;
1244   }
1245
1246   return eval;
1247 }