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 != s1 && 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 ctx context
 664  * @param a DFA automaton
 665  */
 666 static void
 667 dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
 668                                      struct GNUNET_REGEX_Automaton *a)
 669 {
 670   int i;
 671   int table[a->state_count][a->state_count];
 672   struct State *s1;
 673   struct State *s2;
 674   struct Transition *t1;
 675   struct Transition *t2;
 676   int change;
 677
 678   change = 1;
 679   for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1;
 680        i++, s1 = s1->next)
 681     s1->marked = i;
 682
 683   // Mark all pairs of accepting/!accepting states
 684   for (s1 = a->states_head; NULL != s1; s1 = s1->next)
 685   {
 686     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
 687     {
 688       if ((s1->accepting && !s2->accepting) ||
 689           (!s1->accepting && s2->accepting))
 690       {
 691         table[s1->marked][s2->marked] = 1;
 692       }
 693       else
 694         table[s1->marked][s2->marked] = 0;
 695     }
 696   }
 697
 698   while (0 != change)
 699   {
 700     change = 0;
 701     for (s1 = a->states_head; NULL != s1; s1 = s1->next)
 702     {
 703       for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
 704       {
 705         if (0 != table[s1->marked][s2->marked])
 706           continue;
 707
 708         for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
 709         {
 710           for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
 711           {
 712             if (t1->literal == t2->literal && t1->state == t2->state &&
 713                 (0 != table[t1->state->marked][t2->state->marked] ||
 714                  0 != table[t2->state->marked][t1->state->marked]))
 715             {
 716               table[s1->marked][s2->marked] = t1->literal;
 717               change = 1;
 718             }
 719             else if (t1->literal != t2->literal && t1->state != t2->state)
 720             {
 721               table[s1->marked][s2->marked] = -1;
 722               change = 1;
 723             }
 724           }
 725         }
 726       }
 727     }
 728   }
 729
 730   struct State *s2_next;
 731
 732   for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
 733   {
 734     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
 735     {
 736       s2_next = s2->next;
 737       if (s1 != s2 && table[s1->marked][s2->marked] == 0)
 738         automaton_merge_states (ctx, a, s1, s2);
 739     }
 740   }
 741 }
 742
 743 /**
 744  * Minimize the given DFA 'a' by removing all unreachable states,
 745  * removing all dead states and merging all non distinguishable states
 746  *
 747  * @param ctx context
 748  * @param a DFA automaton
 749  */
 750 static void
 751 dfa_minimize (struct GNUNET_REGEX_Context *ctx,
 752               struct GNUNET_REGEX_Automaton *a)
 753 {
 754   if (NULL == a)
 755     return;
 756
 757   GNUNET_assert (DFA == a->type);
 758
 759   // 1. remove unreachable states
 760   dfa_remove_unreachable_states (a);
 761
 762   // 2. remove dead states
 763   dfa_remove_dead_states (a);
 764
 765   // 3. Merge nondistinguishable states
 766   dfa_merge_nondistinguishable_states (ctx, a);
 767 }
 768
 769 /**
 770  * Creates a new NFA fragment. Needs to be cleared using automaton_fragment_clear.
 771  *
 772  * @param start starting state
 773  * @param end end state
 774  *
 775  * @return new NFA fragment
 776  */
 777 static struct GNUNET_REGEX_Automaton *
 778 nfa_fragment_create (struct State *start, struct State *end)
 779 {
 780   struct GNUNET_REGEX_Automaton *n;
 781
 782   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 783
 784   n->type = NFA;
 785   n->start = NULL;
 786   n->end = NULL;
 787
 788   if (NULL == start && NULL == end)
 789     return n;
 790
 791   automaton_add_state (n, end);
 792   automaton_add_state (n, start);
 793
 794   n->start = start;
 795   n->end = end;
 796
 797   return n;
 798 }
 799
 800 /**
 801  * Adds a list of states to the given automaton 'n'.
 802  *
 803  * @param n automaton to which the states should be added
 804  * @param states_head head of the DLL of states
 805  * @param states_tail tail of the DLL of states
 806  */
 807 static void
 808 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct State *states_head,
 809                 struct State *states_tail)
 810 {
 811   struct State *s;
 812
 813   if (NULL == n || NULL == states_head)
 814   {
 815     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
 816     return;
 817   }
 818
 819   if (NULL == n->states_head)
 820   {
 821     n->states_head = states_head;
 822     n->states_tail = states_tail;
 823     return;
 824   }
 825
 826   if (NULL != states_head)
 827   {
 828     n->states_tail->next = states_head;
 829     n->states_tail = states_tail;
 830   }
 831
 832   for (s = states_head; NULL != s; s = s->next)
 833     n->state_count++;
 834 }
 835
 836 /**
 837  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
 838  *
 839  * @param ctx context
 840  * @param accepting is it an accepting state or not
 841  *
 842  * @return new NFA state
 843  */
 844 static struct State *
 845 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
 846 {
 847   struct State *s;
 848
 849   s = GNUNET_malloc (sizeof (struct State));
 850   s->id = ctx->state_id++;
 851   s->accepting = accepting;
 852   s->marked = 0;
 853   s->name = NULL;
 854   GNUNET_asprintf (&s->name, "s%i", s->id);
 855
 856   return s;
 857 }
 858
 859 /**
 860  * Calculates the NFA closure set for the given state
 861  *
 862  * @param s starting point state
 863  * @param literal transitioning literal on which to base the closure on,
 864  *                pass 0 for epsilon transition
 865  *
 866  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 867  */
 868 static struct StateSet *
 869 nfa_closure_create (struct State *s, const char literal)
 870 {
 871   struct StateSet *cls;
 872   struct StateSet *cls_check;
 873   struct State *clsstate;
 874   struct State *currentstate;
 875   struct Transition *ctran;
 876
 877   if (NULL == s)
 878     return NULL;
 879
 880   cls = GNUNET_malloc (sizeof (struct StateSet));
 881   cls_check = GNUNET_malloc (sizeof (struct StateSet));
 882
 883   // Add start state to closure only for epsilon closure
 884   if (0 == literal)
 885     GNUNET_array_append (cls->states, cls->len, s);
 886
 887   GNUNET_array_append (cls_check->states, cls_check->len, s);
 888   while (cls_check->len > 0)
 889   {
 890     currentstate = cls_check->states[cls_check->len - 1];
 891     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
 892
 893     for (ctran = currentstate->transitions_head; NULL != ctran;
 894          ctran = ctran->next)
 895     {
 896       if (NULL != ctran->state && literal == ctran->literal)
 897       {
 898         clsstate = ctran->state;
 899
 900         if (NULL != clsstate &&
 901             GNUNET_YES != state_set_contains (cls, clsstate))
 902         {
 903           GNUNET_array_append (cls->states, cls->len, clsstate);
 904           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
 905         }
 906       }
 907     }
 908   }
 909   GNUNET_assert (0 == cls_check->len);
 910   GNUNET_free (cls_check);
 911
 912   if (cls->len > 1)
 913     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 914
 915   return cls;
 916 }
 917
 918 /**
 919  * Calculates the closure set for the given set of states.
 920  *
 921  * @param states list of states on which to base the closure on
 922  * @param literal transitioning literal for which to base the closure on,
 923  *                pass 0 for epsilon transition
 924  *
 925  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 926  */
 927 static struct StateSet *
 928 nfa_closure_set_create (struct StateSet *states, const char literal)
 929 {
 930   struct State *s;
 931   struct StateSet *sset;
 932   struct StateSet *cls;
 933   int i;
 934   int j;
 935   int k;
 936   int contains;
 937
 938   if (NULL == states)
 939     return NULL;
 940
 941   cls = GNUNET_malloc (sizeof (struct StateSet));
 942
 943   for (i = 0; i < states->len; i++)
 944   {
 945     s = states->states[i];
 946     sset = nfa_closure_create (s, literal);
 947
 948     for (j = 0; j < sset->len; j++)
 949     {
 950       contains = 0;
 951       for (k = 0; k < cls->len; k++)
 952       {
 953         if (sset->states[j]->id == cls->states[k]->id)
 954         {
 955           contains = 1;
 956           break;
 957         }
 958       }
 959       if (!contains)
 960         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 961     }
 962     state_set_clear (sset);
 963   }
 964
 965   if (cls->len > 1)
 966     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 967
 968   return cls;
 969 }
 970
 971 /**
 972  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 973  *
 974  * @param ctx context
 975  */
 976 static void
 977 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 978 {
 979   struct GNUNET_REGEX_Automaton *a;
 980   struct GNUNET_REGEX_Automaton *b;
 981   struct GNUNET_REGEX_Automaton *new;
 982
 983   b = ctx->stack_tail;
 984   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 985   a = ctx->stack_tail;
 986   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 987
 988   add_transition (ctx, a->end, 0, b->start);
 989   a->end->accepting = 0;
 990   b->end->accepting = 1;
 991
 992   new = nfa_fragment_create (NULL, NULL);
 993   nfa_add_states (new, a->states_head, a->states_tail);
 994   nfa_add_states (new, b->states_head, b->states_tail);
 995   new->start = a->start;
 996   new->end = b->end;
 997   automaton_fragment_clear (a);
 998   automaton_fragment_clear (b);
 999
1000   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
1001 }
1002
1003 /**
1004  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
1005  *
1006  * @param ctx context
1007  */
1008 static void
1009 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
1010 {
1011   struct GNUNET_REGEX_Automaton *a;
1012   struct GNUNET_REGEX_Automaton *new;
1013   struct State *start;
1014   struct State *end;
1015
1016   a = ctx->stack_tail;
1017   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1018
1019   if (NULL == a)
1020   {
1021     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1022                 "nfa_add_star_op failed, because there was no element on the stack");
1023     return;
1024   }
1025
1026   start = nfa_state_create (ctx, 0);
1027   end = nfa_state_create (ctx, 1);
1028
1029   add_transition (ctx, start, 0, a->start);
1030   add_transition (ctx, start, 0, end);
1031   add_transition (ctx, a->end, 0, a->start);
1032   add_transition (ctx, a->end, 0, end);
1033
1034   a->end->accepting = 0;
1035   end->accepting = 1;
1036
1037   new = nfa_fragment_create (start, end);
1038   nfa_add_states (new, a->states_head, a->states_tail);
1039   automaton_fragment_clear (a);
1040
1041   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
1042 }
1043
1044 /**
1045  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
1046  *
1047  * @param ctx context
1048  */
1049 static void
1050 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
1051 {
1052   struct GNUNET_REGEX_Automaton *a;
1053
1054   a = ctx->stack_tail;
1055   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1056
1057   add_transition (ctx, a->end, 0, a->start);
1058
1059   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
1060 }
1061
1062 /**
1063  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
1064  * that alternates between a and b (a|b)
1065  *
1066  * @param ctx context
1067  */
1068 static void
1069 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
1070 {
1071   struct GNUNET_REGEX_Automaton *a;
1072   struct GNUNET_REGEX_Automaton *b;
1073   struct GNUNET_REGEX_Automaton *new;
1074   struct State *start;
1075   struct State *end;
1076
1077   b = ctx->stack_tail;
1078   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
1079   a = ctx->stack_tail;
1080   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
1081
1082   start = nfa_state_create (ctx, 0);
1083   end = nfa_state_create (ctx, 1);
1084   add_transition (ctx, start, 0, a->start);
1085   add_transition (ctx, start, 0, b->start);
1086
1087   add_transition (ctx, a->end, 0, end);
1088   add_transition (ctx, b->end, 0, end);
1089
1090   a->end->accepting = 0;
1091   b->end->accepting = 0;
1092   end->accepting = 1;
1093
1094   new = nfa_fragment_create (start, end);
1095   nfa_add_states (new, a->states_head, a->states_tail);
1096   nfa_add_states (new, b->states_head, b->states_tail);
1097   automaton_fragment_clear (a);
1098   automaton_fragment_clear (b);
1099
1100   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
1101 }
1102
1103 /**
1104  * Adds a new nfa fragment to the stack
1105  *
1106  * @param ctx context
1107  * @param lit literal for nfa transition
1108  */
1109 static void
1110 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
1111 {
1112   struct GNUNET_REGEX_Automaton *n;
1113   struct State *start;
1114   struct State *end;
1115
1116   GNUNET_assert (NULL != ctx);
1117
1118   start = nfa_state_create (ctx, 0);
1119   end = nfa_state_create (ctx, 1);
1120   add_transition (ctx, start, lit, end);
1121   n = nfa_fragment_create (start, end);
1122   GNUNET_assert (NULL != n);
1123   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
1124 }
1125
1126 /**
1127  * Construct an NFA by parsing the regex string of length 'len'.
1128  *
1129  * @param regex regular expression string
1130  * @param len length of the string
1131  *
1132  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1133  */
1134 struct GNUNET_REGEX_Automaton *
1135 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
1136 {
1137   struct GNUNET_REGEX_Context ctx;
1138   struct GNUNET_REGEX_Automaton *nfa;
1139   const char *regexp;
1140   char *error_msg;
1141   unsigned int count;
1142   unsigned int altcount;
1143   unsigned int atomcount;
1144   unsigned int pcount;
1145   struct
1146   {
1147     int altcount;
1148     int atomcount;
1149   }     *p;
1150
1151   GNUNET_REGEX_context_init (&ctx);
1152
1153   regexp = regex;
1154   p = NULL;
1155   error_msg = NULL;
1156   altcount = 0;
1157   atomcount = 0;
1158   pcount = 0;
1159
1160   for (count = 0; count < len && *regexp; count++, regexp++)
1161   {
1162     switch (*regexp)
1163     {
1164     case '(':
1165       if (atomcount > 1)
1166       {
1167         --atomcount;
1168         nfa_add_concatenation (&ctx);
1169       }
1170       GNUNET_array_grow (p, pcount, pcount + 1);
1171       p[pcount - 1].altcount = altcount;
1172       p[pcount - 1].atomcount = atomcount;
1173       altcount = 0;
1174       atomcount = 0;
1175       break;
1176     case '|':
1177       if (0 == atomcount)
1178       {
1179         error_msg = "Cannot append '|' to nothing";
1180         goto error;
1181       }
1182       while (--atomcount > 0)
1183         nfa_add_concatenation (&ctx);
1184       altcount++;
1185       break;
1186     case ')':
1187       if (0 == pcount)
1188       {
1189         error_msg = "Missing opening '('";
1190         goto error;
1191       }
1192       if (0 == atomcount)
1193       {
1194         // Ignore this: "()"
1195         pcount--;
1196         altcount = p[pcount].altcount;
1197         atomcount = p[pcount].atomcount;
1198         break;
1199       }
1200       while (--atomcount > 0)
1201         nfa_add_concatenation (&ctx);
1202       for (; altcount > 0; altcount--)
1203         nfa_add_alternation (&ctx);
1204       pcount--;
1205       altcount = p[pcount].altcount;
1206       atomcount = p[pcount].atomcount;
1207       atomcount++;
1208       break;
1209     case '*':
1210       if (atomcount == 0)
1211       {
1212         error_msg = "Cannot append '+' to nothing";
1213         goto error;
1214       }
1215       nfa_add_star_op (&ctx);
1216       break;
1217     case '+':
1218       if (atomcount == 0)
1219       {
1220         error_msg = "Cannot append '+' to nothing";
1221         goto error;
1222       }
1223       nfa_add_plus_op (&ctx);
1224       break;
1225     case 92:                   /* escape: \ */
1226       regexp++;
1227       count++;
1228     default:
1229       if (atomcount > 1)
1230       {
1231         --atomcount;
1232         nfa_add_concatenation (&ctx);
1233       }
1234       nfa_add_literal (&ctx, *regexp);
1235       atomcount++;
1236       break;
1237     }
1238   }
1239   if (0 != pcount)
1240   {
1241     error_msg = "Unbalanced parenthesis";
1242     goto error;
1243   }
1244   while (--atomcount > 0)
1245     nfa_add_concatenation (&ctx);
1246   for (; altcount > 0; altcount--)
1247     nfa_add_alternation (&ctx);
1248
1249   if (NULL != p)
1250     GNUNET_free (p);
1251
1252   nfa = ctx.stack_tail;
1253   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
1254
1255
1256   if (NULL != ctx.stack_head)
1257   {
1258     error_msg = "Creating the NFA failed. NFA stack was not empty!";
1259     goto error;
1260   }
1261
1262   return nfa;
1263
1264 error:
1265   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
1266   if (NULL != error_msg)
1267     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
1268   if (NULL != p)
1269     GNUNET_free (p);
1270   while (NULL != ctx.stack_tail)
1271   {
1272     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
1273     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
1274                                  ctx.stack_tail);
1275   }
1276   return NULL;
1277 }
1278
1279 /**
1280  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
1281  * data structure.
1282  *
1283  * @param a automaton to be destroyed
1284  */
1285 void
1286 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
1287 {
1288   struct State *s;
1289   struct State *next_state;
1290
1291   if (NULL == a)
1292     return;
1293
1294   for (s = a->states_head; NULL != s;)
1295   {
1296     next_state = s->next;
1297     automaton_destroy_state (s);
1298     s = next_state;
1299   }
1300
1301   GNUNET_free (a);
1302 }
1303
1304 /**
1305  * Construct DFA for the given 'regex' of length 'len'
1306  *
1307  * @param regex regular expression string
1308  * @param len length of the regular expression
1309  *
1310  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1311  */
1312 struct GNUNET_REGEX_Automaton *
1313 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
1314 {
1315   struct GNUNET_REGEX_Context ctx;
1316   struct GNUNET_REGEX_Automaton *dfa;
1317   struct GNUNET_REGEX_Automaton *nfa;
1318   struct StateSet *tmp;
1319   struct StateSet *nfa_set;
1320   struct StateSet *dfa_stack;
1321   struct Transition *ctran;
1322   struct State *dfa_state;
1323   struct State *new_dfa_state;
1324   struct State *state_contains;
1325   struct State *state_iter;
1326
1327   GNUNET_REGEX_context_init (&ctx);
1328
1329   // Create NFA
1330   nfa = GNUNET_REGEX_construct_nfa (regex, len);
1331
1332   if (NULL == nfa)
1333   {
1334     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1335                 "Could not create DFA, because NFA creation failed\n");
1336     return NULL;
1337   }
1338
1339   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1340   dfa->type = DFA;
1341
1342   // Create DFA start state from epsilon closure
1343   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
1344   nfa_set = nfa_closure_create (nfa->start, 0);
1345   dfa->start = dfa_state_create (&ctx, nfa_set);
1346   automaton_add_state (dfa, dfa->start);
1347   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
1348
1349   // Create dfa states by combining nfa states
1350   while (dfa_stack->len > 0)
1351   {
1352     dfa_state = dfa_stack->states[dfa_stack->len - 1];
1353     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1354
1355     for (ctran = dfa_state->transitions_head; NULL != ctran;
1356          ctran = ctran->next)
1357     {
1358       if (0 != ctran->literal && NULL == ctran->state)
1359       {
1360         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1361         nfa_set = nfa_closure_set_create (tmp, 0);
1362         state_set_clear (tmp);
1363         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1364         state_contains = NULL;
1365         for (state_iter = dfa->states_head; NULL != state_iter;
1366              state_iter = state_iter->next)
1367         {
1368           if (0 ==
1369               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1370             state_contains = state_iter;
1371         }
1372
1373         if (NULL == state_contains)
1374         {
1375           automaton_add_state (dfa, new_dfa_state);
1376           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1377                                new_dfa_state);
1378           ctran->state = new_dfa_state;
1379         }
1380         else
1381         {
1382           ctran->state = state_contains;
1383           automaton_destroy_state (new_dfa_state);
1384         }
1385       }
1386     }
1387   }
1388
1389   GNUNET_free (dfa_stack);
1390   GNUNET_REGEX_automaton_destroy (nfa);
1391
1392   dfa_minimize (&ctx, dfa);
1393
1394   return dfa;
1395 }
1396
1397 /**
1398  * Save the given automaton as a GraphViz dot file
1399  *
1400  * @param a the automaton to be saved
1401  * @param filename where to save the file
1402  */
1403 void
1404 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1405                                    const char *filename)
1406 {
1407   struct State *s;
1408   struct Transition *ctran;
1409   char *s_acc = NULL;
1410   char *s_tran = NULL;
1411   char *start;
1412   char *end;
1413   FILE *p;
1414
1415   if (NULL == a)
1416   {
1417     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1418     return;
1419   }
1420
1421   if (NULL == filename || strlen (filename) < 1)
1422   {
1423     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1424     return;
1425   }
1426
1427   p = fopen (filename, "w");
1428
1429   if (p == NULL)
1430   {
1431     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1432                 filename);
1433     return;
1434   }
1435
1436   start = "digraph G {\nrankdir=LR\n";
1437   fwrite (start, strlen (start), 1, p);
1438
1439   for (s = a->states_head; NULL != s; s = s->next)
1440   {
1441     if (s->accepting)
1442     {
1443       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1444       fwrite (s_acc, strlen (s_acc), 1, p);
1445       GNUNET_free (s_acc);
1446     }
1447
1448     s->marked = 1;
1449
1450     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1451     {
1452       if (NULL == ctran->state)
1453       {
1454         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1455                     "Transition from State %i has has no state for transitioning\n",
1456                     s->id);
1457         continue;
1458       }
1459
1460       if (ctran->literal == 0)
1461       {
1462         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1463                          s->name, ctran->state->name);
1464       }
1465       else
1466       {
1467         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1468                          s->name, ctran->state->name, ctran->literal);
1469       }
1470
1471       fwrite (s_tran, strlen (s_tran), 1, p);
1472       GNUNET_free (s_tran);
1473     }
1474   }
1475
1476   end = "\n}\n";
1477   fwrite (end, strlen (end), 1, p);
1478   fclose (p);
1479 }
1480
1481 /**
1482  * Evaluates the given string using the given DFA automaton
1483  *
1484  * @param a automaton, type must be DFA
1485  * @param string string that should be evaluated
1486  *
1487  * @return 0 if string matches, non 0 otherwise
1488  */
1489 static int
1490 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1491 {
1492   const char *strp;
1493   struct State *s;
1494
1495   if (DFA != a->type)
1496   {
1497     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1498                 "Tried to evaluate DFA, but NFA automaton given");
1499     return -1;
1500   }
1501
1502   s = a->start;
1503
1504   for (strp = string; NULL != strp && *strp; strp++)
1505   {
1506     s = dfa_move (s, *strp);
1507     if (NULL == s)
1508       break;
1509   }
1510
1511   if (NULL != s && s->accepting)
1512     return 0;
1513
1514   return 1;
1515 }
1516
1517 /**
1518  * Evaluates the given string using the given NFA automaton
1519  *
1520  * @param a automaton, type must be NFA
1521  * @param string string that should be evaluated
1522  *
1523  * @return 0 if string matches, non 0 otherwise
1524  */
1525 static int
1526 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1527 {
1528   const char *strp;
1529   struct State *s;
1530   struct StateSet *sset;
1531   struct StateSet *new_sset;
1532   int i;
1533   int result;
1534
1535   if (NFA != a->type)
1536   {
1537     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1538                 "Tried to evaluate NFA, but DFA automaton given");
1539     return -1;
1540   }
1541
1542   result = 1;
1543   strp = string;
1544   sset = nfa_closure_create (a->start, 0);
1545
1546   for (strp = string; NULL != strp && *strp; strp++)
1547   {
1548     new_sset = nfa_closure_set_create (sset, *strp);
1549     state_set_clear (sset);
1550     sset = nfa_closure_set_create (new_sset, 0);
1551     state_set_clear (new_sset);
1552   }
1553
1554   for (i = 0; i < sset->len; i++)
1555   {
1556     s = sset->states[i];
1557     if (NULL != s && s->accepting)
1558     {
1559       result = 0;
1560       break;
1561     }
1562   }
1563
1564   state_set_clear (sset);
1565   return result;
1566 }
1567
1568 /**
1569  * Evaluates the given 'string' against the given compiled regex
1570  *
1571  * @param a automaton
1572  * @param string string to check
1573  *
1574  * @return 0 if string matches, non 0 otherwise
1575  */
1576 int
1577 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1578 {
1579   int result;
1580
1581   switch (a->type)
1582   {
1583   case DFA:
1584     result = evaluate_dfa (a, string);
1585     break;
1586   case NFA:
1587     result = evaluate_nfa (a, string);
1588     break;
1589   default:
1590     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1591                 "Evaluating regex failed, automaton has no type!\n");
1592     result = GNUNET_SYSERR;
1593     break;
1594   }
1595
1596   return result;
1597 }