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