src/regex/regex.c

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