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 static struct State *
 420 dfa_move (struct State *s, const char literal)
 421 {
 422   struct Transition *t;
 423   struct State *new_s;
 424
 425   if (NULL == s)
 426     return NULL;
 427
 428   new_s = NULL;
 429
 430   for (t = s->transitions_head; NULL != t; t = t->next)
 431   {
 432     if (literal == t->literal)
 433     {
 434       new_s = t->state;
 435       break;
 436     }
 437   }
 438
 439   return new_s;
 440 }
 441
 442 static void
 443 dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
 444 {
 445   /*
 446    * struct StateSet *unreachable;
 447    * struct State *stack[a->size];
 448    * struct State *s;
 449    *
 450    * unreachable = GNUNET_malloc (sizeof (struct StateSet));
 451    *
 452    * // 1. add all states to unreachable set
 453    * for (s = a->states_head; NULL != s; s = s->next)
 454    * {
 455    * GNUNET_array_append (unreachable->states, unreachable->len; s);
 456    * }
 457    *
 458    * // 2. traverse dfa from start state and remove every visited state from unreachable set
 459    * s = a->start;
 460    * // push a->start
 461    * while (stack->len > 0)
 462    * {
 463    * s = stack->states[stack->len - 1];
 464    * GNUNET_array_grow (stack->states; stack->len; stack->len-1);
 465    * GNUNET_array_
 466    * for (t = s->transitions_head; NULL != t; t = t->next)
 467    * {
 468    *
 469    * }
 470    * }
 471    * // 3. delete all states that are still in the unreachable set
 472    */
 473 }
 474
 475 static void
 476 dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
 477 {
 478   struct State *s;
 479   struct State *s_check;
 480   struct Transition *t;
 481   struct Transition *t_check;
 482   int dead;
 483
 484   GNUNET_assert (DFA == a->type);
 485
 486   for (s = a->states_head; NULL != s; s = s->next)
 487   {
 488     if (s->accepting)
 489       continue;
 490
 491     dead = 1;
 492     for (t = s->transitions_head; NULL != t; t = t->next)
 493     {
 494       if (NULL != t->state && t->state != s)
 495       {
 496         dead = 0;
 497         break;
 498       }
 499     }
 500
 501     if (0 == dead)
 502       continue;
 503
 504     // state s is dead, remove it
 505     // 1. remove all transitions to this state
 506     for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 507     {
 508       for (t_check = s_check->transitions_head; NULL != t_check;
 509            t_check = t_check->next)
 510       {
 511         if (t_check->state == s)
 512         {
 513           GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
 514                                        s_check->transitions_tail, t_check);
 515         }
 516       }
 517     }
 518     // 2. remove state
 519     GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
 520   }
 521 }
 522
 523 static void
 524 dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Automaton *a)
 525 {
 526
 527 }
 528
 529 static void
 530 dfa_minimize (struct GNUNET_REGEX_Automaton *a)
 531 {
 532   GNUNET_assert (DFA == a->type);
 533
 534   // 1. remove unreachable states
 535   dfa_remove_unreachable_states (a);
 536
 537   // 2. remove dead states
 538   dfa_remove_dead_states (a);
 539
 540   // 3. Merge nondistinguishable states
 541   dfa_merge_nondistinguishable_states (a);
 542 }
 543
 544 /**
 545  * Creates a new NFA fragment. Needs to be cleared using automaton_fragment_clear.
 546  *
 547  * @param start starting state
 548  * @param end end state
 549  *
 550  * @return new NFA fragment
 551  */
 552 static struct GNUNET_REGEX_Automaton *
 553 nfa_fragment_create (struct State *start, struct State *end)
 554 {
 555   struct GNUNET_REGEX_Automaton *n;
 556
 557   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 558
 559   n->type = NFA;
 560   n->start = NULL;
 561   n->end = NULL;
 562
 563   if (NULL == start && NULL == end)
 564     return n;
 565
 566   GNUNET_CONTAINER_DLL_insert (n->states_head, n->states_tail, end);
 567   GNUNET_CONTAINER_DLL_insert (n->states_head, n->states_tail, start);
 568
 569   n->start = start;
 570   n->end = end;
 571
 572   return n;
 573 }
 574
 575 /**
 576  * Adds a list of states to the given automaton 'n'.
 577  *
 578  * @param n automaton to which the states should be added
 579  * @param states_head head of the DLL of states
 580  * @param states_tail tail of the DLL of states
 581  */
 582 static void
 583 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct State *states_head,
 584                 struct State *states_tail)
 585 {
 586   if (NULL == n || NULL == states_head)
 587   {
 588     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
 589     return;
 590   }
 591
 592   if (NULL == n->states_head)
 593   {
 594     n->states_head = states_head;
 595     n->states_tail = states_tail;
 596     return;
 597   }
 598
 599   if (NULL != states_head)
 600   {
 601     n->states_tail->next = states_head;
 602     n->states_tail = states_tail;
 603   }
 604 }
 605
 606 /**
 607  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
 608  *
 609  * @param ctx context
 610  * @param accepting is it an accepting state or not
 611  *
 612  * @return new NFA state
 613  */
 614 static struct State *
 615 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
 616 {
 617   struct State *s;
 618
 619   s = GNUNET_malloc (sizeof (struct State));
 620   s->id = ctx->state_id++;
 621   s->accepting = accepting;
 622   s->marked = 0;
 623   s->name = NULL;
 624   GNUNET_asprintf (&s->name, "s%i", s->id);
 625
 626   return s;
 627 }
 628
 629 /**
 630  * Calculates the NFA closure set for the given state
 631  *
 632  * @param s starting point state
 633  * @param literal transitioning literal on which to base the closure on,
 634  *                pass 0 for epsilon transition
 635  *
 636  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 637  */
 638 static struct StateSet *
 639 nfa_closure_create (struct State *s, const char literal)
 640 {
 641   struct StateSet *cls;
 642   struct StateSet *cls_check;
 643   struct State *clsstate;
 644   struct State *currentstate;
 645   struct Transition *ctran;
 646
 647   if (NULL == s)
 648     return NULL;
 649
 650   cls = GNUNET_malloc (sizeof (struct StateSet));
 651   cls_check = GNUNET_malloc (sizeof (struct StateSet));
 652
 653   // Add start state to closure only for epsilon closure
 654   if (0 == literal)
 655     GNUNET_array_append (cls->states, cls->len, s);
 656
 657   GNUNET_array_append (cls_check->states, cls_check->len, s);
 658   while (cls_check->len > 0)
 659   {
 660     currentstate = cls_check->states[cls_check->len - 1];
 661     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
 662
 663     for (ctran = currentstate->transitions_head; NULL != ctran;
 664          ctran = ctran->next)
 665     {
 666       if (NULL != ctran->state && literal == ctran->literal)
 667       {
 668         clsstate = ctran->state;
 669
 670         if (NULL != clsstate &&
 671             GNUNET_YES != state_set_contains (cls, clsstate))
 672         {
 673           GNUNET_array_append (cls->states, cls->len, clsstate);
 674           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
 675         }
 676       }
 677     }
 678   }
 679   GNUNET_assert (0 == cls_check->len);
 680   GNUNET_free (cls_check);
 681
 682   if (cls->len > 1)
 683     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 684
 685   return cls;
 686 }
 687
 688 /**
 689  * Calculates the closure set for the given set of states.
 690  *
 691  * @param states list of states on which to base the closure on
 692  * @param literal transitioning literal for which to base the closure on,
 693  *                pass 0 for epsilon transition
 694  *
 695  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 696  */
 697 static struct StateSet *
 698 nfa_closure_set_create (struct StateSet *states, const char literal)
 699 {
 700   struct State *s;
 701   struct StateSet *sset;
 702   struct StateSet *cls;
 703   int i;
 704   int j;
 705   int k;
 706   int contains;
 707
 708   if (NULL == states)
 709     return NULL;
 710
 711   cls = GNUNET_malloc (sizeof (struct StateSet));
 712
 713   for (i = 0; i < states->len; i++)
 714   {
 715     s = states->states[i];
 716     sset = nfa_closure_create (s, literal);
 717
 718     for (j = 0; j < sset->len; j++)
 719     {
 720       contains = 0;
 721       for (k = 0; k < cls->len; k++)
 722       {
 723         if (sset->states[j]->id == cls->states[k]->id)
 724           contains = 1;
 725       }
 726       if (!contains)
 727         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 728     }
 729     state_set_clear (sset);
 730   }
 731
 732   if (cls->len > 1)
 733     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 734
 735   return cls;
 736 }
 737
 738 /**
 739  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 740  *
 741  * @param ctx context
 742  */
 743 static void
 744 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 745 {
 746   struct GNUNET_REGEX_Automaton *a;
 747   struct GNUNET_REGEX_Automaton *b;
 748   struct GNUNET_REGEX_Automaton *new;
 749
 750   b = ctx->stack_tail;
 751   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 752   a = ctx->stack_tail;
 753   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 754
 755   add_transition (ctx, a->end, 0, b->start);
 756   a->end->accepting = 0;
 757   b->end->accepting = 1;
 758
 759   new = nfa_fragment_create (NULL, NULL);
 760   nfa_add_states (new, a->states_head, a->states_tail);
 761   nfa_add_states (new, b->states_head, b->states_tail);
 762   new->start = a->start;
 763   new->end = b->end;
 764   automaton_fragment_clear (a);
 765   automaton_fragment_clear (b);
 766
 767   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 768 }
 769
 770 /**
 771  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
 772  *
 773  * @param ctx context
 774  */
 775 static void
 776 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 777 {
 778   struct GNUNET_REGEX_Automaton *a;
 779   struct GNUNET_REGEX_Automaton *new;
 780   struct State *start;
 781   struct State *end;
 782
 783   a = ctx->stack_tail;
 784   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 785
 786   if (NULL == a)
 787   {
 788     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 789                 "nfa_add_star_op failed, because there was no element on the stack");
 790     return;
 791   }
 792
 793   start = nfa_state_create (ctx, 0);
 794   end = nfa_state_create (ctx, 1);
 795
 796   add_transition (ctx, start, 0, a->start);
 797   add_transition (ctx, start, 0, end);
 798   add_transition (ctx, a->end, 0, a->start);
 799   add_transition (ctx, a->end, 0, end);
 800
 801   a->end->accepting = 0;
 802   end->accepting = 1;
 803
 804   new = nfa_fragment_create (start, end);
 805   nfa_add_states (new, a->states_head, a->states_tail);
 806   automaton_fragment_clear (a);
 807
 808   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 809 }
 810
 811 /**
 812  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
 813  *
 814  * @param ctx context
 815  */
 816 static void
 817 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 818 {
 819   struct GNUNET_REGEX_Automaton *a;
 820
 821   a = ctx->stack_tail;
 822   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 823
 824   add_transition (ctx, a->end, 0, a->start);
 825
 826   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
 827 }
 828
 829 /**
 830  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
 831  * that alternates between a and b (a|b)
 832  *
 833  * @param ctx context
 834  */
 835 static void
 836 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 837 {
 838   struct GNUNET_REGEX_Automaton *a;
 839   struct GNUNET_REGEX_Automaton *b;
 840   struct GNUNET_REGEX_Automaton *new;
 841   struct State *start;
 842   struct State *end;
 843
 844   b = ctx->stack_tail;
 845   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 846   a = ctx->stack_tail;
 847   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 848
 849   start = nfa_state_create (ctx, 0);
 850   end = nfa_state_create (ctx, 1);
 851   add_transition (ctx, start, 0, a->start);
 852   add_transition (ctx, start, 0, b->start);
 853
 854   add_transition (ctx, a->end, 0, end);
 855   add_transition (ctx, b->end, 0, end);
 856
 857   a->end->accepting = 0;
 858   b->end->accepting = 0;
 859   end->accepting = 1;
 860
 861   new = nfa_fragment_create (start, end);
 862   nfa_add_states (new, a->states_head, a->states_tail);
 863   nfa_add_states (new, b->states_head, b->states_tail);
 864   automaton_fragment_clear (a);
 865   automaton_fragment_clear (b);
 866
 867   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 868 }
 869
 870 /**
 871  * Adds a new nfa fragment to the stack
 872  *
 873  * @param ctx context
 874  * @param lit literal for nfa transition
 875  */
 876 static void
 877 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 878 {
 879   struct GNUNET_REGEX_Automaton *n;
 880   struct State *start;
 881   struct State *end;
 882
 883   GNUNET_assert (NULL != ctx);
 884
 885   start = nfa_state_create (ctx, 0);
 886   end = nfa_state_create (ctx, 1);
 887   add_transition (ctx, start, lit, end);
 888   n = nfa_fragment_create (start, end);
 889   GNUNET_assert (NULL != n);
 890   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
 891 }
 892
 893 /**
 894  * Construct an NFA by parsing the regex string of length 'len'.
 895  *
 896  * @param regex regular expression string
 897  * @param len length of the string
 898  *
 899  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
 900  */
 901 struct GNUNET_REGEX_Automaton *
 902 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
 903 {
 904   struct GNUNET_REGEX_Context ctx;
 905   struct GNUNET_REGEX_Automaton *nfa;
 906   const char *regexp;
 907   char *error_msg;
 908   unsigned int count;
 909   unsigned int altcount;
 910   unsigned int atomcount;
 911   unsigned int pcount;
 912   struct
 913   {
 914     int altcount;
 915     int atomcount;
 916   }     *p;
 917
 918   GNUNET_REGEX_context_init (&ctx);
 919
 920   regexp = regex;
 921   p = NULL;
 922   error_msg = NULL;
 923   altcount = 0;
 924   atomcount = 0;
 925   pcount = 0;
 926
 927   for (count = 0; count < len && *regexp; count++, regexp++)
 928   {
 929     switch (*regexp)
 930     {
 931     case '(':
 932       if (atomcount > 1)
 933       {
 934         --atomcount;
 935         nfa_add_concatenation (&ctx);
 936       }
 937       GNUNET_array_grow (p, pcount, pcount + 1);
 938       p[pcount - 1].altcount = altcount;
 939       p[pcount - 1].atomcount = atomcount;
 940       altcount = 0;
 941       atomcount = 0;
 942       break;
 943     case '|':
 944       if (0 == atomcount)
 945       {
 946         error_msg = "Cannot append '|' to nothing";
 947         goto error;
 948       }
 949       while (--atomcount > 0)
 950         nfa_add_concatenation (&ctx);
 951       altcount++;
 952       break;
 953     case ')':
 954       if (0 == pcount)
 955       {
 956         error_msg = "Missing opening '('";
 957         goto error;
 958       }
 959       if (0 == atomcount)
 960       {
 961         // Ignore this: "()"
 962         pcount--;
 963         altcount = p[pcount].altcount;
 964         atomcount = p[pcount].atomcount;
 965         break;
 966       }
 967       while (--atomcount > 0)
 968         nfa_add_concatenation (&ctx);
 969       for (; altcount > 0; altcount--)
 970         nfa_add_alternation (&ctx);
 971       pcount--;
 972       altcount = p[pcount].altcount;
 973       atomcount = p[pcount].atomcount;
 974       atomcount++;
 975       break;
 976     case '*':
 977       if (atomcount == 0)
 978       {
 979         error_msg = "Cannot append '+' to nothing";
 980         goto error;
 981       }
 982       nfa_add_star_op (&ctx);
 983       break;
 984     case '+':
 985       if (atomcount == 0)
 986       {
 987         error_msg = "Cannot append '+' to nothing";
 988         goto error;
 989       }
 990       nfa_add_plus_op (&ctx);
 991       break;
 992     case 92:                   /* escape: \ */
 993       regexp++;
 994       count++;
 995     default:
 996       if (atomcount > 1)
 997       {
 998         --atomcount;
 999         nfa_add_concatenation (&ctx);
1000       }
1001       nfa_add_literal (&ctx, *regexp);
1002       atomcount++;
1003       break;
1004     }
1005   }
1006   if (0 != pcount)
1007   {
1008     error_msg = "Unbalanced parenthesis";
1009     goto error;
1010   }
1011   while (--atomcount > 0)
1012     nfa_add_concatenation (&ctx);
1013   for (; altcount > 0; altcount--)
1014     nfa_add_alternation (&ctx);
1015
1016   if (NULL != p)
1017     GNUNET_free (p);
1018
1019   nfa = ctx.stack_tail;
1020   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
1021
1022
1023   if (NULL != ctx.stack_head)
1024   {
1025     error_msg = "Creating the NFA failed. NFA stack was not empty!";
1026     goto error;
1027   }
1028
1029   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1030               "Created NFA with %i States and a total of %i Transitions\n",
1031               ctx.state_id, ctx.transition_id);
1032
1033   return nfa;
1034
1035 error:
1036   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
1037   if (NULL != error_msg)
1038     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
1039   GNUNET_free (p);
1040   while (NULL != ctx.stack_tail)
1041   {
1042     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
1043     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
1044                                  ctx.stack_tail);
1045   }
1046   return NULL;
1047 }
1048
1049 /**
1050  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
1051  * data structure.
1052  *
1053  * @param a automaton to be destroyed
1054  */
1055 void
1056 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
1057 {
1058   struct State *s;
1059   struct State *next_state;
1060
1061   if (NULL == a)
1062     return;
1063
1064   for (s = a->states_head; NULL != s;)
1065   {
1066     next_state = s->next;
1067     automaton_destroy_state (s);
1068     s = next_state;
1069   }
1070
1071   GNUNET_free (a);
1072 }
1073
1074 /**
1075  * Construct DFA for the given 'regex' of length 'len'
1076  *
1077  * @param regex regular expression string
1078  * @param len length of the regular expression
1079  *
1080  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1081  */
1082 struct GNUNET_REGEX_Automaton *
1083 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
1084 {
1085   struct GNUNET_REGEX_Context ctx;
1086   struct GNUNET_REGEX_Automaton *dfa;
1087   struct GNUNET_REGEX_Automaton *nfa;
1088   struct StateSet *tmp;
1089   struct StateSet *nfa_set;
1090   struct StateSet *dfa_stack;
1091   struct Transition *ctran;
1092   struct State *dfa_state;
1093   struct State *new_dfa_state;
1094   struct State *state_contains;
1095   struct State *state_iter;
1096
1097   GNUNET_REGEX_context_init (&ctx);
1098
1099   // Create NFA
1100   nfa = GNUNET_REGEX_construct_nfa (regex, len);
1101
1102   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1103   dfa->type = DFA;
1104
1105   // Create DFA start state from epsilon closure
1106   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
1107   nfa_set = nfa_closure_create (nfa->start, 0);
1108   dfa->start = dfa_state_create (&ctx, nfa_set);
1109   GNUNET_CONTAINER_DLL_insert (dfa->states_head, dfa->states_tail, dfa->start);
1110   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
1111   while (dfa_stack->len > 0)
1112   {
1113     dfa_state = dfa_stack->states[dfa_stack->len - 1];
1114     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1115
1116     for (ctran = dfa_state->transitions_head; NULL != ctran;
1117          ctran = ctran->next)
1118     {
1119       if (0 != ctran->literal && NULL == ctran->state)
1120       {
1121         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1122         nfa_set = nfa_closure_set_create (tmp, 0);
1123         state_set_clear (tmp);
1124         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1125         state_contains = NULL;
1126         for (state_iter = dfa->states_head; NULL != state_iter;
1127              state_iter = state_iter->next)
1128         {
1129           if (0 ==
1130               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1131             state_contains = state_iter;
1132         }
1133
1134         if (NULL == state_contains)
1135         {
1136           GNUNET_CONTAINER_DLL_insert_tail (dfa->states_head, dfa->states_tail,
1137                                             new_dfa_state);
1138           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1139                                new_dfa_state);
1140           ctran->state = new_dfa_state;
1141         }
1142         else
1143         {
1144           ctran->state = state_contains;
1145           automaton_destroy_state (new_dfa_state);
1146         }
1147       }
1148     }
1149   }
1150
1151   GNUNET_free (dfa_stack);
1152   GNUNET_REGEX_automaton_destroy (nfa);
1153
1154   dfa_minimize (dfa);
1155
1156   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
1157               ctx.state_id);
1158
1159   return dfa;
1160 }
1161
1162 /**
1163  * Save the given automaton as a GraphViz dot file
1164  *
1165  * @param a the automaton to be saved
1166  * @param filename where to save the file
1167  */
1168 void
1169 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1170                                    const char *filename)
1171 {
1172   struct State *s;
1173   struct Transition *ctran;
1174   char *s_acc = NULL;
1175   char *s_tran = NULL;
1176   char *start;
1177   char *end;
1178   FILE *p;
1179
1180   if (NULL == a)
1181   {
1182     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1183     return;
1184   }
1185
1186   if (NULL == filename || strlen (filename) < 1)
1187   {
1188     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1189     return;
1190   }
1191
1192   p = fopen (filename, "w");
1193
1194   if (p == NULL)
1195   {
1196     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1197                 filename);
1198     return;
1199   }
1200
1201   start = "digraph G {\nrankdir=LR\n";
1202   fwrite (start, strlen (start), 1, p);
1203
1204   for (s = a->states_head; NULL != s; s = s->next)
1205   {
1206     if (s->accepting)
1207     {
1208       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1209       fwrite (s_acc, strlen (s_acc), 1, p);
1210       GNUNET_free (s_acc);
1211     }
1212
1213     s->marked = 1;
1214
1215     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1216     {
1217       if (NULL == ctran->state)
1218       {
1219         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1220                     "Transition from State %i has has no state for transitioning\n",
1221                     s->id);
1222         continue;
1223       }
1224
1225       if (ctran->literal == 0)
1226       {
1227         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1228                          s->name, ctran->state->name);
1229       }
1230       else
1231       {
1232         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1233                          s->name, ctran->state->name, ctran->literal);
1234       }
1235
1236       fwrite (s_tran, strlen (s_tran), 1, p);
1237       GNUNET_free (s_tran);
1238     }
1239   }
1240
1241   end = "\n}\n";
1242   fwrite (end, strlen (end), 1, p);
1243   fclose (p);
1244 }
1245
1246 /**
1247  * Evaluates the given string using the given DFA automaton
1248  *
1249  * @param a automaton, type must be DFA
1250  * @param string string that should be evaluated
1251  *
1252  * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise
1253  */
1254 static int
1255 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1256 {
1257   const char *strp;
1258   struct State *s;
1259
1260   if (DFA != a->type)
1261   {
1262     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1263                 "Tried to evaluate DFA, but NFA automaton given");
1264     return GNUNET_SYSERR;
1265   }
1266
1267   s = a->start;
1268
1269   for (strp = string; NULL != strp && *strp; strp++)
1270   {
1271     s = dfa_move (s, *strp);
1272     if (NULL == s)
1273       break;
1274   }
1275
1276   if (NULL != s && s->accepting)
1277     return GNUNET_YES;
1278
1279   return GNUNET_NO;
1280 }
1281
1282 /**
1283  * Evaluates the given string using the given NFA automaton
1284  *
1285  * @param a automaton, type must be NFA
1286  * @param string string that should be evaluated
1287  *
1288  * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise
1289  */
1290 static int
1291 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1292 {
1293   const char *strp;
1294   struct State *s;
1295   struct StateSet *sset;
1296   struct StateSet *new_sset;
1297   int i;
1298   int result;
1299
1300   if (NFA != a->type)
1301   {
1302     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1303                 "Tried to evaluate NFA, but DFA automaton given");
1304     return GNUNET_SYSERR;
1305   }
1306
1307   result = GNUNET_NO;
1308   strp = string;
1309   sset = GNUNET_malloc (sizeof (struct StateSet));
1310   GNUNET_array_append (sset->states, sset->len, a->start);
1311
1312   for (strp = string; NULL != strp && *strp; strp++)
1313   {
1314     new_sset = nfa_closure_set_create (sset, *strp);
1315     state_set_clear (sset);
1316     sset = nfa_closure_set_create (new_sset, 0);
1317     state_set_clear (new_sset);
1318   }
1319
1320   for (i = 0; i < sset->len; i++)
1321   {
1322     s = sset->states[i];
1323     if (NULL != s && s->accepting)
1324     {
1325       result = GNUNET_YES;
1326       break;
1327     }
1328   }
1329
1330   state_set_clear (sset);
1331   return result;
1332 }
1333
1334
1335 /**
1336  * Evaluates the given 'string' against the given compiled regex
1337  *
1338  * @param a automaton
1339  * @param string string to check
1340  *
1341  * @return GNUNET_YES if 'a' matches 'string', GNUNET_NO otherwise
1342  */
1343 int
1344 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1345 {
1346   int result;
1347
1348   switch (a->type)
1349   {
1350   case DFA:
1351     result = evaluate_dfa (a, string);
1352     break;
1353   case NFA:
1354     result = evaluate_nfa (a, string);
1355     break;
1356   default:
1357     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1358                 "Evaluating regex failed, automaton has no type!\n");
1359     result = GNUNET_SYSERR;
1360     break;
1361   }
1362
1363   return result;
1364 }