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   unsigned int state_count;
  64   struct State *states_head;
  65   struct State *states_tail;
  66
  67   enum GNUNET_REGEX_automaton_type type;
  68 };
  69
  70 /**
  71  * A state. Can be used in DFA and NFA automatons.
  72  */
  73 struct State
  74 {
  75   struct State *prev;
  76   struct State *next;
  77
  78   unsigned int id;
  79   int accepting;
  80   int marked;
  81   char *name;
  82
  83   unsigned int transition_count;
  84   struct Transition *transitions_head;
  85   struct Transition *transitions_tail;
  86
  87   struct StateSet *nfa_set;
  88 };
  89
  90 /**
  91  * Transition between two states. Each state can have 0-n transitions.
  92  * If literal is 0, this is considered to be an epsilon transition.
  93  */
  94 struct Transition
  95 {
  96   struct Transition *prev;
  97   struct Transition *next;
  98
  99   unsigned int id;
 100   char literal;
 101   struct State *state;
 102 };
 103
 104 /**
 105  * Set of states
 106  */
 107 struct StateSet
 108 {
 109   /**
 110    * Array of states
 111    */
 112   struct State **states;
 113   unsigned int len;
 114 };
 115
 116 /**
 117  * Initialize a new context
 118  *
 119  * @param ctx context
 120  */
 121 static void
 122 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
 123 {
 124   if (NULL == ctx)
 125   {
 126     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
 127     return;
 128   }
 129   ctx->state_id = 0;
 130   ctx->transition_id = 0;
 131   ctx->stack_head = NULL;
 132   ctx->stack_tail = NULL;
 133 }
 134
 135 static void
 136 debug_print_state (struct State *s)
 137 {
 138   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 139               "State %i: %s marked: %i accepting: %i\n", s->id, s->name,
 140               s->marked, s->accepting);
 141 }
 142
 143 static void
 144 debug_print_states (struct StateSet *sset)
 145 {
 146   struct State *s;
 147   int i;
 148
 149   for (i = 0; i < sset->len; i++)
 150   {
 151     s = sset->states[i];
 152     debug_print_state (s);
 153   }
 154 }
 155
 156 static void
 157 debug_print_transitions (struct State *s)
 158 {
 159   struct Transition *t;
 160   char *state;
 161   char literal;
 162
 163   for (t = s->transitions_head; NULL != t; t = t->next)
 164   {
 165     if (0 == t->literal)
 166       literal = '0';
 167     else
 168       literal = t->literal;
 169
 170     if (NULL == t->state)
 171       state = "NULL";
 172     else
 173       state = t->state->name;
 174
 175     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
 176                 literal, state);
 177   }
 178 }
 179
 180 /**
 181  * Compare two states. Used for sorting.
 182  *
 183  * @param a first state
 184  * @param b second state
 185  *
 186  * @return an integer less than, equal to, or greater than zero
 187  *         if the first argument is considered to be respectively
 188  *         less than, equal to, or greater than the second.
 189  */
 190 static int
 191 state_compare (const void *a, const void *b)
 192 {
 193   struct State **s1;
 194   struct State **s2;
 195
 196   s1 = (struct State **) a;
 197   s2 = (struct State **) b;
 198
 199   return (*s1)->id - (*s2)->id;
 200 }
 201
 202 /**
 203  * Compare to state sets by comparing the id's of the states that are
 204  * contained in each set. Both sets are expected to be sorted by id!
 205  *
 206  * @param sset1 first state set
 207  * @param sset2 second state set
 208  *
 209  * @return 0 if they are equal, non 0 otherwise
 210  */
 211 static int
 212 state_set_compare (struct StateSet *sset1, struct StateSet *sset2)
 213 {
 214   int i;
 215
 216   if (sset1->len != sset2->len)
 217     return 1;
 218
 219   for (i = 0; i < sset1->len; i++)
 220   {
 221     if (sset1->states[i]->id != sset2->states[i]->id)
 222     {
 223       return 1;
 224     }
 225   }
 226   return 0;
 227 }
 228
 229 /**
 230  * Checks if 'elem' is contained in 'set'
 231  *
 232  * @param set set of states
 233  * @param elem state
 234  *
 235  * @return GNUNET_YES if 'set' contains 'elem, GNUNET_NO otherwise
 236  */
 237 static int
 238 state_set_contains (struct StateSet *set, struct State *elem)
 239 {
 240   struct State *s;
 241   int i;
 242
 243   for (i = 0; i < set->len; i++)
 244   {
 245     s = set->states[i];
 246     if (0 == memcmp (s, elem, sizeof (struct State)))
 247       return GNUNET_YES;
 248   }
 249   return GNUNET_NO;
 250 }
 251
 252 /**
 253  * Clears the given StateSet 'set'
 254  *
 255  * @param set set to be cleared
 256  */
 257 static void
 258 state_set_clear (struct StateSet *set)
 259 {
 260   if (NULL != set)
 261   {
 262     if (NULL != set->states)
 263       GNUNET_free (set->states);
 264     GNUNET_free (set);
 265   }
 266 }
 267
 268 /**
 269  * Adds a transition from one state to another on 'literal'
 270  *
 271  * @param ctx context
 272  * @param from_state starting state for the transition
 273  * @param literal transition label
 274  * @param to_state state to where the transition should point to
 275  */
 276 static void
 277 add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state,
 278                 const char literal, struct State *to_state)
 279 {
 280   struct Transition *t;
 281
 282   if (NULL == from_state)
 283   {
 284     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 285     return;
 286   }
 287
 288   t = GNUNET_malloc (sizeof (struct Transition));
 289
 290   t->id = ctx->transition_id++;
 291   t->literal = literal;
 292   t->state = to_state;
 293
 294   GNUNET_CONTAINER_DLL_insert (from_state->transitions_head,
 295                                from_state->transitions_tail, t);
 296 }
 297
 298 /**
 299  * Clears an automaton fragment. Does not destroy the states inside
 300  * the automaton.
 301  *
 302  * @param a automaton to be cleared
 303  */
 304 static void
 305 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
 306 {
 307   a->start = NULL;
 308   a->end = NULL;
 309   a->states_head = NULL;
 310   a->states_tail = NULL;
 311   a->state_count = 0;
 312   GNUNET_free (a);
 313 }
 314
 315 /**
 316  * Frees the memory used by State 's'
 317  *
 318  * @param s state that should be destroyed
 319  */
 320 static void
 321 automaton_destroy_state (struct State *s)
 322 {
 323   struct Transition *t;
 324   struct Transition *next_t;
 325
 326   if (NULL != s->name)
 327     GNUNET_free (s->name);
 328
 329   for (t = s->transitions_head; NULL != t;)
 330   {
 331     next_t = t->next;
 332     GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
 333     GNUNET_free (t);
 334     t = next_t;
 335   }
 336
 337   state_set_clear (s->nfa_set);
 338
 339   GNUNET_free (s);
 340 }
 341
 342 /**
 343  * Remove a state from the given automaton 'a'. Always use this function
 344  * when altering the states of an automaton. Will also remove all transitions
 345  * leading to this state, before destroying it.
 346  *
 347  * @param a automaton
 348  * @param s state to remove
 349  */
 350 static void
 351 automaton_remove_state (struct GNUNET_REGEX_Automaton *a, struct State *s)
 352 {
 353   struct State *ss;
 354   struct State *s_check;
 355   struct Transition *t_check;
 356
 357   // remove state
 358   ss = s;
 359   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
 360   a->state_count--;
 361
 362   // remove all transitions leading to this state
 363   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 364   {
 365     for (t_check = s_check->transitions_head; NULL != t_check;
 366          t_check = t_check->next)
 367     {
 368       if (t_check->state == ss)
 369       {
 370         GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
 371                                      s_check->transitions_tail, t_check);
 372         s_check->transition_count--;
 373       }
 374     }
 375   }
 376
 377   automaton_destroy_state (ss);
 378 }
 379
 380 /**
 381  * Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy 's2'.
 382  *
 383  * @param ctx context
 384  * @param a automaton
 385  * @param s1 first state
 386  * @param s2 second state, will be destroyed
 387  */
 388 static void
 389 automaton_merge_states (struct GNUNET_REGEX_Context *ctx,
 390                         struct GNUNET_REGEX_Automaton *a, struct State *s1,
 391                         struct State *s2)
 392 {
 393   struct State *s_check;
 394   struct Transition *t_check;
 395   struct Transition *t;
 396   char *new_name;
 397
 398   GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2);
 399
 400   // 1. Make all transitions pointing to s2 point to s1
 401   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 402   {
 403     for (t_check = s_check->transitions_head; NULL != t_check;
 404          t_check = t_check->next)
 405     {
 406       if (s_check != s2 && s2 == t_check->state)
 407         t_check->state = s1;
 408     }
 409   }
 410
 411   // 2. Add all transitions from s2 to sX to s1
 412   for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
 413   {
 414     for (t = s1->transitions_head; NULL != t; t = t->next)
 415     {
 416       if (t_check->literal != t->literal && NULL != t_check->state &&
 417           t_check->state != t->state && t_check->state != s2)
 418       {
 419         add_transition (ctx, s1, t_check->literal, t_check->state);
 420       }
 421     }
 422   }
 423
 424   // 3. Rename s1 to {s1,s2}
 425   new_name = GNUNET_malloc (strlen (s1->name) + strlen (s2->name) + 1);
 426   strncat (new_name, s1->name, strlen (s1->name));
 427   strncat (new_name, s2->name, strlen (s2->name));
 428   if (NULL != s1->name)
 429     GNUNET_free (s1->name);
 430   s1->name = new_name;
 431
 432   // remove state
 433   s_check = s2;
 434   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s_check);
 435   a->state_count--;
 436   automaton_destroy_state (s_check);
 437 }
 438
 439 /**
 440  * Add a state to the automaton 'a', always use this function to
 441  * alter the states DLL of the automaton.
 442  *
 443  * @param a automaton to add the state to
 444  * @param s state that should be added
 445  */
 446 static void
 447 automaton_add_state (struct GNUNET_REGEX_Automaton *a, struct State *s)
 448 {
 449   GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
 450   a->state_count++;
 451 }
 452
 453 /**
 454  * Creates a new DFA state based on a set of NFA states. Needs to be freed
 455  * using automaton_destroy_state.
 456  *
 457  * @param ctx context
 458  * @param nfa_states set of NFA states on which the DFA should be based on
 459  *
 460  * @return new DFA state
 461  */
 462 static struct State *
 463 dfa_state_create (struct GNUNET_REGEX_Context *ctx, struct StateSet *nfa_states)
 464 {
 465   struct State *s;
 466   char *name;
 467   int len = 0;
 468   struct State *cstate;
 469   struct Transition *ctran;
 470   int insert = 1;
 471   struct Transition *t;
 472   int i;
 473
 474   s = GNUNET_malloc (sizeof (struct State));
 475   s->id = ctx->state_id++;
 476   s->accepting = 0;
 477   s->marked = 0;
 478   s->name = NULL;
 479
 480   if (NULL == nfa_states)
 481   {
 482     GNUNET_asprintf (&s->name, "s%i", s->id);
 483     return s;
 484   }
 485
 486   s->nfa_set = nfa_states;
 487
 488   if (nfa_states->len < 1)
 489     return s;
 490
 491   // Create a name based on 'sset'
 492   s->name = GNUNET_malloc (sizeof (char) * 2);
 493   strcat (s->name, "{");
 494   name = NULL;
 495
 496   for (i = 0; i < nfa_states->len; i++)
 497   {
 498     cstate = nfa_states->states[i];
 499     GNUNET_asprintf (&name, "%i,", cstate->id);
 500
 501     if (NULL != name)
 502     {
 503       len = strlen (s->name) + strlen (name) + 1;
 504       s->name = GNUNET_realloc (s->name, len);
 505       strcat (s->name, name);
 506       GNUNET_free (name);
 507       name = NULL;
 508     }
 509
 510     // Add a transition for each distinct literal to NULL state
 511     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
 512     {
 513       if (0 != ctran->literal)
 514       {
 515         insert = 1;
 516
 517         for (t = s->transitions_head; NULL != t; t = t->next)
 518         {
 519           if (t->literal == ctran->literal)
 520           {
 521             insert = 0;
 522             break;
 523           }
 524         }
 525
 526         if (insert)
 527           add_transition (ctx, s, ctran->literal, NULL);
 528       }
 529     }
 530
 531     // If the nfa_states contain an accepting state, the new dfa state is also accepting
 532     if (cstate->accepting)
 533       s->accepting = 1;
 534   }
 535
 536   s->name[strlen (s->name) - 1] = '}';
 537
 538   return s;
 539 }
 540
 541 /**
 542  * Move from the given state 's' to the next state on
 543  * transition 'literal'
 544  *
 545  * @param s starting state
 546  * @param literal edge label to follow
 547  *
 548  * @return new state or NULL, if transition on literal not possible
 549  */
 550 static struct State *
 551 dfa_move (struct State *s, const char literal)
 552 {
 553   struct Transition *t;
 554   struct State *new_s;
 555
 556   if (NULL == s)
 557     return NULL;
 558
 559   new_s = NULL;
 560
 561   for (t = s->transitions_head; NULL != t; t = t->next)
 562   {
 563     if (literal == t->literal)
 564     {
 565       new_s = t->state;
 566       break;
 567     }
 568   }
 569
 570   return new_s;
 571 }
 572
 573 /**
 574  * Remove all unreachable states from DFA 'a'. Unreachable states
 575  * are those states that are not reachable from the starting state.
 576  *
 577  * @param a DFA automaton
 578  */
 579 static void
 580 dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
 581 {
 582   struct State *stack[a->state_count];
 583   int stack_len;
 584   struct State *s;
 585   struct Transition *t;
 586
 587   stack_len = 0;
 588
 589   // 1. unmark all states
 590   for (s = a->states_head; NULL != s; s = s->next)
 591   {
 592     s->marked = 0;
 593   }
 594
 595   // 2. traverse dfa from start state and mark all visited states
 596   stack[stack_len] = a->start;
 597   stack_len++;
 598   while (stack_len > 0)
 599   {
 600     s = stack[stack_len - 1];
 601     stack_len--;
 602     s->marked = 1;              // mark s as visited
 603     for (t = s->transitions_head; NULL != t; t = t->next)
 604     {
 605       if (NULL != t->state && 0 == t->state->marked)
 606       {
 607         // add next states to stack
 608         stack[stack_len] = t->state;
 609         stack_len++;
 610       }
 611     }
 612   }
 613
 614   // 3. delete all states that were not visited
 615   for (s = a->states_head; NULL != s; s = s->next)
 616   {
 617     if (0 == s->marked)
 618       automaton_remove_state (a, s);
 619   }
 620 }
 621
 622 /**
 623  * Remove all dead states from the DFA 'a'. Dead states are those
 624  * states that do not transition to any other state but themselfes.
 625  *
 626  * @param a DFA automaton
 627  */
 628 static void
 629 dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
 630 {
 631   struct State *s;
 632   struct Transition *t;
 633   int dead;
 634
 635   GNUNET_assert (DFA == a->type);
 636
 637   for (s = a->states_head; NULL != s; s = s->next)
 638   {
 639     if (s->accepting)
 640       continue;
 641
 642     dead = 1;
 643     for (t = s->transitions_head; NULL != t; t = t->next)
 644     {
 645       if (NULL != t->state && t->state != s)
 646       {
 647         dead = 0;
 648         break;
 649       }
 650     }
 651
 652     if (0 == dead)
 653       continue;
 654
 655     // state s is dead, remove it
 656     automaton_remove_state (a, s);
 657   }
 658 }
 659
 660 /**
 661  * Merge all non distinguishable states in the DFA 'a'
 662  *
 663  * @param a DFA automaton
 664  */
 665 static void
 666 dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
 667                                      struct GNUNET_REGEX_Automaton *a)
 668 {
 669   int i;
 670   int table[a->state_count][a->state_count];
 671   struct State *s1;
 672   struct State *s2;
 673   struct Transition *t1;
 674   struct Transition *t2;
 675   int change;
 676
 677   change = 1;
 678   for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1;
 679        i++, s1 = s1->next)
 680     s1->marked = i;
 681
 682   // Mark all pairs of accepting/!accepting states
 683   for (s1 = a->states_head; NULL != s1; s1 = s1->next)
 684   {
 685     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
 686     {
 687       if ((s1->accepting && !s2->accepting) ||
 688           (!s1->accepting && s2->accepting))
 689       {
 690         table[s1->marked][s2->marked] = 1;
 691       }
 692       else
 693         table[s1->marked][s2->marked] = 0;
 694     }
 695   }
 696
 697   while (0 != change)
 698   {
 699     change = 0;
 700     for (s1 = a->states_head; NULL != s1; s1 = s1->next)
 701     {
 702       for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
 703       {
 704         if (0 != table[s1->marked][s2->marked])
 705           continue;
 706
 707         for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
 708         {
 709           for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
 710           {
 711             if (t1->literal == t2->literal && t1->state == t2->state &&
 712                 (0 != table[t1->state->marked][t2->state->marked] ||
 713                  0 != table[t2->state->marked][t1->state->marked]))
 714             {
 715               table[s1->marked][s2->marked] = t1->literal;
 716               change = 1;
 717             }
 718             else if (t1->literal != t2->literal && t1->state != t2->state)
 719             {
 720               table[s1->marked][s2->marked] = -1;
 721               change = 1;
 722             }
 723           }
 724         }
 725       }
 726     }
 727   }
 728
 729   struct State *s2_next;
 730
 731   for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
 732   {
 733     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
 734     {
 735       s2_next = s2->next;
 736       if (s1 != s2 && table[s1->marked][s2->marked] == 0)
 737         automaton_merge_states (ctx, a, s1, s2);
 738     }
 739   }
 740 }
 741
 742 /**
 743  * Minimize the given DFA 'a' by removing all unreachable states,
 744  * removing all dead states and merging all non distinguishable states
 745  *
 746  * @param a DFA automaton
 747  */
 748 static void
 749 dfa_minimize (struct GNUNET_REGEX_Context *ctx,
 750               struct GNUNET_REGEX_Automaton *a)
 751 {
 752   if (NULL == a)
 753     return;
 754
 755   GNUNET_assert (DFA == a->type);
 756
 757   // 1. remove unreachable states
 758   dfa_remove_unreachable_states (a);
 759
 760   // 2. remove dead states
 761   dfa_remove_dead_states (a);
 762
 763   // 3. Merge nondistinguishable states
 764   dfa_merge_nondistinguishable_states (ctx, a);
 765 }
 766
 767 /**
 768  * Creates a new NFA fragment. Needs to be cleared using automaton_fragment_clear.
 769  *
 770  * @param start starting state
 771  * @param end end state
 772  *
 773  * @return new NFA fragment
 774  */
 775 static struct GNUNET_REGEX_Automaton *
 776 nfa_fragment_create (struct State *start, struct State *end)
 777 {
 778   struct GNUNET_REGEX_Automaton *n;
 779
 780   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 781
 782   n->type = NFA;
 783   n->start = NULL;
 784   n->end = NULL;
 785
 786   if (NULL == start && NULL == end)
 787     return n;
 788
 789   automaton_add_state (n, end);
 790   automaton_add_state (n, start);
 791
 792   n->start = start;
 793   n->end = end;
 794
 795   return n;
 796 }
 797
 798 /**
 799  * Adds a list of states to the given automaton 'n'.
 800  *
 801  * @param n automaton to which the states should be added
 802  * @param states_head head of the DLL of states
 803  * @param states_tail tail of the DLL of states
 804  */
 805 static void
 806 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct State *states_head,
 807                 struct State *states_tail)
 808 {
 809   struct State *s;
 810
 811   if (NULL == n || NULL == states_head)
 812   {
 813     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
 814     return;
 815   }
 816
 817   if (NULL == n->states_head)
 818   {
 819     n->states_head = states_head;
 820     n->states_tail = states_tail;
 821     return;
 822   }
 823
 824   if (NULL != states_head)
 825   {
 826     n->states_tail->next = states_head;
 827     n->states_tail = states_tail;
 828   }
 829
 830   for (s = states_head; NULL != s; s = s->next)
 831     n->state_count++;
 832 }
 833
 834 /**
 835  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
 836  *
 837  * @param ctx context
 838  * @param accepting is it an accepting state or not
 839  *
 840  * @return new NFA state
 841  */
 842 static struct State *
 843 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
 844 {
 845   struct State *s;
 846
 847   s = GNUNET_malloc (sizeof (struct State));
 848   s->id = ctx->state_id++;
 849   s->accepting = accepting;
 850   s->marked = 0;
 851   s->name = NULL;
 852   GNUNET_asprintf (&s->name, "s%i", s->id);
 853
 854   return s;
 855 }
 856
 857 /**
 858  * Calculates the NFA closure set for the given state
 859  *
 860  * @param s starting point state
 861  * @param literal transitioning literal on which to base the closure on,
 862  *                pass 0 for epsilon transition
 863  *
 864  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 865  */
 866 static struct StateSet *
 867 nfa_closure_create (struct State *s, const char literal)
 868 {
 869   struct StateSet *cls;
 870   struct StateSet *cls_check;
 871   struct State *clsstate;
 872   struct State *currentstate;
 873   struct Transition *ctran;
 874
 875   if (NULL == s)
 876     return NULL;
 877
 878   cls = GNUNET_malloc (sizeof (struct StateSet));
 879   cls_check = GNUNET_malloc (sizeof (struct StateSet));
 880
 881   // Add start state to closure only for epsilon closure
 882   if (0 == literal)
 883     GNUNET_array_append (cls->states, cls->len, s);
 884
 885   GNUNET_array_append (cls_check->states, cls_check->len, s);
 886   while (cls_check->len > 0)
 887   {
 888     currentstate = cls_check->states[cls_check->len - 1];
 889     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
 890
 891     for (ctran = currentstate->transitions_head; NULL != ctran;
 892          ctran = ctran->next)
 893     {
 894       if (NULL != ctran->state && literal == ctran->literal)
 895       {
 896         clsstate = ctran->state;
 897
 898         if (NULL != clsstate &&
 899             GNUNET_YES != state_set_contains (cls, clsstate))
 900         {
 901           GNUNET_array_append (cls->states, cls->len, clsstate);
 902           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
 903         }
 904       }
 905     }
 906   }
 907   GNUNET_assert (0 == cls_check->len);
 908   GNUNET_free (cls_check);
 909
 910   if (cls->len > 1)
 911     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 912
 913   return cls;
 914 }
 915
 916 /**
 917  * Calculates the closure set for the given set of states.
 918  *
 919  * @param states list of states on which to base the closure on
 920  * @param literal transitioning literal for which to base the closure on,
 921  *                pass 0 for epsilon transition
 922  *
 923  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 924  */
 925 static struct StateSet *
 926 nfa_closure_set_create (struct StateSet *states, const char literal)
 927 {
 928   struct State *s;
 929   struct StateSet *sset;
 930   struct StateSet *cls;
 931   int i;
 932   int j;
 933   int k;
 934   int contains;
 935
 936   if (NULL == states)
 937     return NULL;
 938
 939   cls = GNUNET_malloc (sizeof (struct StateSet));
 940
 941   for (i = 0; i < states->len; i++)
 942   {
 943     s = states->states[i];
 944     sset = nfa_closure_create (s, literal);
 945
 946     for (j = 0; j < sset->len; j++)
 947     {
 948       contains = 0;
 949       for (k = 0; k < cls->len; k++)
 950       {
 951         if (sset->states[j]->id == cls->states[k]->id)
 952         {
 953           contains = 1;
 954           break;
 955         }
 956       }
 957       if (!contains)
 958         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 959     }
 960     state_set_clear (sset);
 961   }
 962
 963   if (cls->len > 1)
 964     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 965
 966   return cls;
 967 }
 968
 969 /**
 970  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 971  *
 972  * @param ctx context
 973  */
 974 static void
 975 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 976 {
 977   struct GNUNET_REGEX_Automaton *a;
 978   struct GNUNET_REGEX_Automaton *b;
 979   struct GNUNET_REGEX_Automaton *new;
 980
 981   b = ctx->stack_tail;
 982   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 983   a = ctx->stack_tail;
 984   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 985
 986   add_transition (ctx, a->end, 0, b->start);
 987   a->end->accepting = 0;
 988   b->end->accepting = 1;
 989
 990   new = nfa_fragment_create (NULL, NULL);
 991   nfa_add_states (new, a->states_head, a->states_tail);
 992   nfa_add_states (new, b->states_head, b->states_tail);
 993   new->start = a->start;
 994   new->end = b->end;
 995   automaton_fragment_clear (a);
 996   automaton_fragment_clear (b);
 997
 998   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 999 }
1000
1001 /**
1002  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
1003  *
1004  * @param ctx context
1005  */
1006 static void
1007 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
1008 {
1009   struct GNUNET_REGEX_Automaton *a;
1010   struct GNUNET_REGEX_Automaton *new;
1011   struct State *start;
1012   struct State *end;
1013
1014   a = ctx->stack_tail;
1015   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1016
1017   if (NULL == a)
1018   {
1019     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1020                 "nfa_add_star_op failed, because there was no element on the stack");
1021     return;
1022   }
1023
1024   start = nfa_state_create (ctx, 0);
1025   end = nfa_state_create (ctx, 1);
1026
1027   add_transition (ctx, start, 0, a->start);
1028   add_transition (ctx, start, 0, end);
1029   add_transition (ctx, a->end, 0, a->start);
1030   add_transition (ctx, a->end, 0, end);
1031
1032   a->end->accepting = 0;
1033   end->accepting = 1;
1034
1035   new = nfa_fragment_create (start, end);
1036   nfa_add_states (new, a->states_head, a->states_tail);
1037   automaton_fragment_clear (a);
1038
1039   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
1040 }
1041
1042 /**
1043  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
1044  *
1045  * @param ctx context
1046  */
1047 static void
1048 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
1049 {
1050   struct GNUNET_REGEX_Automaton *a;
1051
1052   a = ctx->stack_tail;
1053   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1054
1055   add_transition (ctx, a->end, 0, a->start);
1056
1057   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
1058 }
1059
1060 /**
1061  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
1062  * that alternates between a and b (a|b)
1063  *
1064  * @param ctx context
1065  */
1066 static void
1067 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
1068 {
1069   struct GNUNET_REGEX_Automaton *a;
1070   struct GNUNET_REGEX_Automaton *b;
1071   struct GNUNET_REGEX_Automaton *new;
1072   struct State *start;
1073   struct State *end;
1074
1075   b = ctx->stack_tail;
1076   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
1077   a = ctx->stack_tail;
1078   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1079
1080   start = nfa_state_create (ctx, 0);
1081   end = nfa_state_create (ctx, 1);
1082   add_transition (ctx, start, 0, a->start);
1083   add_transition (ctx, start, 0, b->start);
1084
1085   add_transition (ctx, a->end, 0, end);
1086   add_transition (ctx, b->end, 0, end);
1087
1088   a->end->accepting = 0;
1089   b->end->accepting = 0;
1090   end->accepting = 1;
1091
1092   new = nfa_fragment_create (start, end);
1093   nfa_add_states (new, a->states_head, a->states_tail);
1094   nfa_add_states (new, b->states_head, b->states_tail);
1095   automaton_fragment_clear (a);
1096   automaton_fragment_clear (b);
1097
1098   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
1099 }
1100
1101 /**
1102  * Adds a new nfa fragment to the stack
1103  *
1104  * @param ctx context
1105  * @param lit literal for nfa transition
1106  */
1107 static void
1108 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
1109 {
1110   struct GNUNET_REGEX_Automaton *n;
1111   struct State *start;
1112   struct State *end;
1113
1114   GNUNET_assert (NULL != ctx);
1115
1116   start = nfa_state_create (ctx, 0);
1117   end = nfa_state_create (ctx, 1);
1118   add_transition (ctx, start, lit, end);
1119   n = nfa_fragment_create (start, end);
1120   GNUNET_assert (NULL != n);
1121   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
1122 }
1123
1124 /**
1125  * Construct an NFA by parsing the regex string of length 'len'.
1126  *
1127  * @param regex regular expression string
1128  * @param len length of the string
1129  *
1130  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1131  */
1132 struct GNUNET_REGEX_Automaton *
1133 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
1134 {
1135   struct GNUNET_REGEX_Context ctx;
1136   struct GNUNET_REGEX_Automaton *nfa;
1137   const char *regexp;
1138   char *error_msg;
1139   unsigned int count;
1140   unsigned int altcount;
1141   unsigned int atomcount;
1142   unsigned int pcount;
1143   struct
1144   {
1145     int altcount;
1146     int atomcount;
1147   }     *p;
1148
1149   GNUNET_REGEX_context_init (&ctx);
1150
1151   regexp = regex;
1152   p = NULL;
1153   error_msg = NULL;
1154   altcount = 0;
1155   atomcount = 0;
1156   pcount = 0;
1157
1158   for (count = 0; count < len && *regexp; count++, regexp++)
1159   {
1160     switch (*regexp)
1161     {
1162     case '(':
1163       if (atomcount > 1)
1164       {
1165         --atomcount;
1166         nfa_add_concatenation (&ctx);
1167       }
1168       GNUNET_array_grow (p, pcount, pcount + 1);
1169       p[pcount - 1].altcount = altcount;
1170       p[pcount - 1].atomcount = atomcount;
1171       altcount = 0;
1172       atomcount = 0;
1173       break;
1174     case '|':
1175       if (0 == atomcount)
1176       {
1177         error_msg = "Cannot append '|' to nothing";
1178         goto error;
1179       }
1180       while (--atomcount > 0)
1181         nfa_add_concatenation (&ctx);
1182       altcount++;
1183       break;
1184     case ')':
1185       if (0 == pcount)
1186       {
1187         error_msg = "Missing opening '('";
1188         goto error;
1189       }
1190       if (0 == atomcount)
1191       {
1192         // Ignore this: "()"
1193         pcount--;
1194         altcount = p[pcount].altcount;
1195         atomcount = p[pcount].atomcount;
1196         break;
1197       }
1198       while (--atomcount > 0)
1199         nfa_add_concatenation (&ctx);
1200       for (; altcount > 0; altcount--)
1201         nfa_add_alternation (&ctx);
1202       pcount--;
1203       altcount = p[pcount].altcount;
1204       atomcount = p[pcount].atomcount;
1205       atomcount++;
1206       break;
1207     case '*':
1208       if (atomcount == 0)
1209       {
1210         error_msg = "Cannot append '+' to nothing";
1211         goto error;
1212       }
1213       nfa_add_star_op (&ctx);
1214       break;
1215     case '+':
1216       if (atomcount == 0)
1217       {
1218         error_msg = "Cannot append '+' to nothing";
1219         goto error;
1220       }
1221       nfa_add_plus_op (&ctx);
1222       break;
1223     case 92:                   /* escape: \ */
1224       regexp++;
1225       count++;
1226     default:
1227       if (atomcount > 1)
1228       {
1229         --atomcount;
1230         nfa_add_concatenation (&ctx);
1231       }
1232       nfa_add_literal (&ctx, *regexp);
1233       atomcount++;
1234       break;
1235     }
1236   }
1237   if (0 != pcount)
1238   {
1239     error_msg = "Unbalanced parenthesis";
1240     goto error;
1241   }
1242   while (--atomcount > 0)
1243     nfa_add_concatenation (&ctx);
1244   for (; altcount > 0; altcount--)
1245     nfa_add_alternation (&ctx);
1246
1247   if (NULL != p)
1248     GNUNET_free (p);
1249
1250   nfa = ctx.stack_tail;
1251   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
1252
1253
1254   if (NULL != ctx.stack_head)
1255   {
1256     error_msg = "Creating the NFA failed. NFA stack was not empty!";
1257     goto error;
1258   }
1259
1260   return nfa;
1261
1262 error:
1263   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
1264   if (NULL != error_msg)
1265     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
1266   if (NULL != p)
1267     GNUNET_free (p);
1268   while (NULL != ctx.stack_tail)
1269   {
1270     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
1271     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
1272                                  ctx.stack_tail);
1273   }
1274   return NULL;
1275 }
1276
1277 /**
1278  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
1279  * data structure.
1280  *
1281  * @param a automaton to be destroyed
1282  */
1283 void
1284 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
1285 {
1286   struct State *s;
1287   struct State *next_state;
1288
1289   if (NULL == a)
1290     return;
1291
1292   for (s = a->states_head; NULL != s;)
1293   {
1294     next_state = s->next;
1295     automaton_destroy_state (s);
1296     s = next_state;
1297   }
1298
1299   GNUNET_free (a);
1300 }
1301
1302 /**
1303  * Construct DFA for the given 'regex' of length 'len'
1304  *
1305  * @param regex regular expression string
1306  * @param len length of the regular expression
1307  *
1308  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1309  */
1310 struct GNUNET_REGEX_Automaton *
1311 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
1312 {
1313   struct GNUNET_REGEX_Context ctx;
1314   struct GNUNET_REGEX_Automaton *dfa;
1315   struct GNUNET_REGEX_Automaton *nfa;
1316   struct StateSet *tmp;
1317   struct StateSet *nfa_set;
1318   struct StateSet *dfa_stack;
1319   struct Transition *ctran;
1320   struct State *dfa_state;
1321   struct State *new_dfa_state;
1322   struct State *state_contains;
1323   struct State *state_iter;
1324
1325   GNUNET_REGEX_context_init (&ctx);
1326
1327   // Create NFA
1328   nfa = GNUNET_REGEX_construct_nfa (regex, len);
1329
1330   if (NULL == nfa)
1331   {
1332     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1333                 "Could not create DFA, because NFA creation failed\n");
1334     return NULL;
1335   }
1336
1337   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1338   dfa->type = DFA;
1339
1340   // Create DFA start state from epsilon closure
1341   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
1342   nfa_set = nfa_closure_create (nfa->start, 0);
1343   dfa->start = dfa_state_create (&ctx, nfa_set);
1344   automaton_add_state (dfa, dfa->start);
1345   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
1346   while (dfa_stack->len > 0)
1347   {
1348     dfa_state = dfa_stack->states[dfa_stack->len - 1];
1349     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1350
1351     for (ctran = dfa_state->transitions_head; NULL != ctran;
1352          ctran = ctran->next)
1353     {
1354       if (0 != ctran->literal && NULL == ctran->state)
1355       {
1356         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1357         nfa_set = nfa_closure_set_create (tmp, 0);
1358         state_set_clear (tmp);
1359         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1360         state_contains = NULL;
1361         for (state_iter = dfa->states_head; NULL != state_iter;
1362              state_iter = state_iter->next)
1363         {
1364           if (0 ==
1365               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1366             state_contains = state_iter;
1367         }
1368
1369         if (NULL == state_contains)
1370         {
1371           automaton_add_state (dfa, new_dfa_state);
1372           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1373                                new_dfa_state);
1374           ctran->state = new_dfa_state;
1375         }
1376         else
1377         {
1378           ctran->state = state_contains;
1379           automaton_destroy_state (new_dfa_state);
1380         }
1381       }
1382     }
1383   }
1384
1385   GNUNET_free (dfa_stack);
1386   GNUNET_REGEX_automaton_destroy (nfa);
1387
1388   /*dfa_minimize (&ctx, dfa);*/
1389
1390   return dfa;
1391 }
1392
1393 /**
1394  * Save the given automaton as a GraphViz dot file
1395  *
1396  * @param a the automaton to be saved
1397  * @param filename where to save the file
1398  */
1399 void
1400 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1401                                    const char *filename)
1402 {
1403   struct State *s;
1404   struct Transition *ctran;
1405   char *s_acc = NULL;
1406   char *s_tran = NULL;
1407   char *start;
1408   char *end;
1409   FILE *p;
1410
1411   if (NULL == a)
1412   {
1413     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1414     return;
1415   }
1416
1417   if (NULL == filename || strlen (filename) < 1)
1418   {
1419     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1420     return;
1421   }
1422
1423   p = fopen (filename, "w");
1424
1425   if (p == NULL)
1426   {
1427     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1428                 filename);
1429     return;
1430   }
1431
1432   start = "digraph G {\nrankdir=LR\n";
1433   fwrite (start, strlen (start), 1, p);
1434
1435   for (s = a->states_head; NULL != s; s = s->next)
1436   {
1437     if (s->accepting)
1438     {
1439       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1440       fwrite (s_acc, strlen (s_acc), 1, p);
1441       GNUNET_free (s_acc);
1442     }
1443
1444     s->marked = 1;
1445
1446     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1447     {
1448       if (NULL == ctran->state)
1449       {
1450         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1451                     "Transition from State %i has has no state for transitioning\n",
1452                     s->id);
1453         continue;
1454       }
1455
1456       if (ctran->literal == 0)
1457       {
1458         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1459                          s->name, ctran->state->name);
1460       }
1461       else
1462       {
1463         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1464                          s->name, ctran->state->name, ctran->literal);
1465       }
1466
1467       fwrite (s_tran, strlen (s_tran), 1, p);
1468       GNUNET_free (s_tran);
1469     }
1470   }
1471
1472   end = "\n}\n";
1473   fwrite (end, strlen (end), 1, p);
1474   fclose (p);
1475 }
1476
1477 /**
1478  * Evaluates the given string using the given DFA automaton
1479  *
1480  * @param a automaton, type must be DFA
1481  * @param string string that should be evaluated
1482  *
1483  * @return 0 if string matches, non 0 otherwise
1484  */
1485 static int
1486 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1487 {
1488   const char *strp;
1489   struct State *s;
1490
1491   if (DFA != a->type)
1492   {
1493     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1494                 "Tried to evaluate DFA, but NFA automaton given");
1495     return -1;
1496   }
1497
1498   s = a->start;
1499
1500   for (strp = string; NULL != strp && *strp; strp++)
1501   {
1502     s = dfa_move (s, *strp);
1503     if (NULL == s)
1504       break;
1505   }
1506
1507   if (NULL != s && s->accepting)
1508     return 0;
1509
1510   return 1;
1511 }
1512
1513 /**
1514  * Evaluates the given string using the given NFA automaton
1515  *
1516  * @param a automaton, type must be NFA
1517  * @param string string that should be evaluated
1518  *
1519  * @return 0 if string matches, non 0 otherwise
1520  */
1521 static int
1522 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1523 {
1524   const char *strp;
1525   struct State *s;
1526   struct StateSet *sset;
1527   struct StateSet *new_sset;
1528   int i;
1529   int result;
1530
1531   if (NFA != a->type)
1532   {
1533     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1534                 "Tried to evaluate NFA, but DFA automaton given");
1535     return -1;
1536   }
1537
1538   result = 1;
1539   strp = string;
1540   sset = nfa_closure_create (a->start, 0);
1541
1542   for (strp = string; NULL != strp && *strp; strp++)
1543   {
1544     new_sset = nfa_closure_set_create (sset, *strp);
1545     state_set_clear (sset);
1546     sset = nfa_closure_set_create (new_sset, 0);
1547     state_set_clear (new_sset);
1548   }
1549
1550   for (i = 0; i < sset->len; i++)
1551   {
1552     s = sset->states[i];
1553     if (NULL != s && s->accepting)
1554     {
1555       result = 0;
1556       break;
1557     }
1558   }
1559
1560   state_set_clear (sset);
1561   return result;
1562 }
1563
1564 /**
1565  * Evaluates the given 'string' against the given compiled regex
1566  *
1567  * @param a automaton
1568  * @param string string to check
1569  *
1570  * @return 0 if string matches, non 0 otherwise
1571  */
1572 int
1573 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1574 {
1575   int result;
1576
1577   switch (a->type)
1578   {
1579   case DFA:
1580     result = evaluate_dfa (a, string);
1581     break;
1582   case NFA:
1583     result = evaluate_nfa (a, string);
1584     break;
1585   default:
1586     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1587                 "Evaluating regex failed, automaton has no type!\n");
1588     result = GNUNET_SYSERR;
1589     break;
1590   }
1591
1592   return result;
1593 }