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