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         {
 725           contains = 1;
 726           break;
 727         }
 728       }
 729       if (!contains)
 730         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 731     }
 732     state_set_clear (sset);
 733   }
 734
 735   if (cls->len > 1)
 736     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 737
 738   return cls;
 739 }
 740
 741 /**
 742  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 743  *
 744  * @param ctx context
 745  */
 746 static void
 747 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 748 {
 749   struct GNUNET_REGEX_Automaton *a;
 750   struct GNUNET_REGEX_Automaton *b;
 751   struct GNUNET_REGEX_Automaton *new;
 752
 753   b = ctx->stack_tail;
 754   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 755   a = ctx->stack_tail;
 756   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 757
 758   add_transition (ctx, a->end, 0, b->start);
 759   a->end->accepting = 0;
 760   b->end->accepting = 1;
 761
 762   new = nfa_fragment_create (NULL, NULL);
 763   nfa_add_states (new, a->states_head, a->states_tail);
 764   nfa_add_states (new, b->states_head, b->states_tail);
 765   new->start = a->start;
 766   new->end = b->end;
 767   automaton_fragment_clear (a);
 768   automaton_fragment_clear (b);
 769
 770   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 771 }
 772
 773 /**
 774  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
 775  *
 776  * @param ctx context
 777  */
 778 static void
 779 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 780 {
 781   struct GNUNET_REGEX_Automaton *a;
 782   struct GNUNET_REGEX_Automaton *new;
 783   struct State *start;
 784   struct State *end;
 785
 786   a = ctx->stack_tail;
 787   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 788
 789   if (NULL == a)
 790   {
 791     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 792                 "nfa_add_star_op failed, because there was no element on the stack");
 793     return;
 794   }
 795
 796   start = nfa_state_create (ctx, 0);
 797   end = nfa_state_create (ctx, 1);
 798
 799   add_transition (ctx, start, 0, a->start);
 800   add_transition (ctx, start, 0, end);
 801   add_transition (ctx, a->end, 0, a->start);
 802   add_transition (ctx, a->end, 0, end);
 803
 804   a->end->accepting = 0;
 805   end->accepting = 1;
 806
 807   new = nfa_fragment_create (start, end);
 808   nfa_add_states (new, a->states_head, a->states_tail);
 809   automaton_fragment_clear (a);
 810
 811   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 812 }
 813
 814 /**
 815  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
 816  *
 817  * @param ctx context
 818  */
 819 static void
 820 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 821 {
 822   struct GNUNET_REGEX_Automaton *a;
 823
 824   a = ctx->stack_tail;
 825   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 826
 827   add_transition (ctx, a->end, 0, a->start);
 828
 829   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
 830 }
 831
 832 /**
 833  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
 834  * that alternates between a and b (a|b)
 835  *
 836  * @param ctx context
 837  */
 838 static void
 839 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 840 {
 841   struct GNUNET_REGEX_Automaton *a;
 842   struct GNUNET_REGEX_Automaton *b;
 843   struct GNUNET_REGEX_Automaton *new;
 844   struct State *start;
 845   struct State *end;
 846
 847   b = ctx->stack_tail;
 848   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 849   a = ctx->stack_tail;
 850   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 851
 852   start = nfa_state_create (ctx, 0);
 853   end = nfa_state_create (ctx, 1);
 854   add_transition (ctx, start, 0, a->start);
 855   add_transition (ctx, start, 0, b->start);
 856
 857   add_transition (ctx, a->end, 0, end);
 858   add_transition (ctx, b->end, 0, end);
 859
 860   a->end->accepting = 0;
 861   b->end->accepting = 0;
 862   end->accepting = 1;
 863
 864   new = nfa_fragment_create (start, end);
 865   nfa_add_states (new, a->states_head, a->states_tail);
 866   nfa_add_states (new, b->states_head, b->states_tail);
 867   automaton_fragment_clear (a);
 868   automaton_fragment_clear (b);
 869
 870   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 871 }
 872
 873 /**
 874  * Adds a new nfa fragment to the stack
 875  *
 876  * @param ctx context
 877  * @param lit literal for nfa transition
 878  */
 879 static void
 880 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 881 {
 882   struct GNUNET_REGEX_Automaton *n;
 883   struct State *start;
 884   struct State *end;
 885
 886   GNUNET_assert (NULL != ctx);
 887
 888   start = nfa_state_create (ctx, 0);
 889   end = nfa_state_create (ctx, 1);
 890   add_transition (ctx, start, lit, end);
 891   n = nfa_fragment_create (start, end);
 892   GNUNET_assert (NULL != n);
 893   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
 894 }
 895
 896 /**
 897  * Construct an NFA by parsing the regex string of length 'len'.
 898  *
 899  * @param regex regular expression string
 900  * @param len length of the string
 901  *
 902  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
 903  */
 904 struct GNUNET_REGEX_Automaton *
 905 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
 906 {
 907   struct GNUNET_REGEX_Context ctx;
 908   struct GNUNET_REGEX_Automaton *nfa;
 909   const char *regexp;
 910   char *error_msg;
 911   unsigned int count;
 912   unsigned int altcount;
 913   unsigned int atomcount;
 914   unsigned int pcount;
 915   struct
 916   {
 917     int altcount;
 918     int atomcount;
 919   }     *p;
 920
 921   GNUNET_REGEX_context_init (&ctx);
 922
 923   regexp = regex;
 924   p = NULL;
 925   error_msg = NULL;
 926   altcount = 0;
 927   atomcount = 0;
 928   pcount = 0;
 929
 930   for (count = 0; count < len && *regexp; count++, regexp++)
 931   {
 932     switch (*regexp)
 933     {
 934     case '(':
 935       if (atomcount > 1)
 936       {
 937         --atomcount;
 938         nfa_add_concatenation (&ctx);
 939       }
 940       GNUNET_array_grow (p, pcount, pcount + 1);
 941       p[pcount - 1].altcount = altcount;
 942       p[pcount - 1].atomcount = atomcount;
 943       altcount = 0;
 944       atomcount = 0;
 945       break;
 946     case '|':
 947       if (0 == atomcount)
 948       {
 949         error_msg = "Cannot append '|' to nothing";
 950         goto error;
 951       }
 952       while (--atomcount > 0)
 953         nfa_add_concatenation (&ctx);
 954       altcount++;
 955       break;
 956     case ')':
 957       if (0 == pcount)
 958       {
 959         error_msg = "Missing opening '('";
 960         goto error;
 961       }
 962       if (0 == atomcount)
 963       {
 964         // Ignore this: "()"
 965         pcount--;
 966         altcount = p[pcount].altcount;
 967         atomcount = p[pcount].atomcount;
 968         break;
 969       }
 970       while (--atomcount > 0)
 971         nfa_add_concatenation (&ctx);
 972       for (; altcount > 0; altcount--)
 973         nfa_add_alternation (&ctx);
 974       pcount--;
 975       altcount = p[pcount].altcount;
 976       atomcount = p[pcount].atomcount;
 977       atomcount++;
 978       break;
 979     case '*':
 980       if (atomcount == 0)
 981       {
 982         error_msg = "Cannot append '+' to nothing";
 983         goto error;
 984       }
 985       nfa_add_star_op (&ctx);
 986       break;
 987     case '+':
 988       if (atomcount == 0)
 989       {
 990         error_msg = "Cannot append '+' to nothing";
 991         goto error;
 992       }
 993       nfa_add_plus_op (&ctx);
 994       break;
 995     case 92:                   /* escape: \ */
 996       regexp++;
 997       count++;
 998     default:
 999       if (atomcount > 1)
1000       {
1001         --atomcount;
1002         nfa_add_concatenation (&ctx);
1003       }
1004       nfa_add_literal (&ctx, *regexp);
1005       atomcount++;
1006       break;
1007     }
1008   }
1009   if (0 != pcount)
1010   {
1011     error_msg = "Unbalanced parenthesis";
1012     goto error;
1013   }
1014   while (--atomcount > 0)
1015     nfa_add_concatenation (&ctx);
1016   for (; altcount > 0; altcount--)
1017     nfa_add_alternation (&ctx);
1018
1019   if (NULL != p)
1020     GNUNET_free (p);
1021
1022   nfa = ctx.stack_tail;
1023   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
1024
1025
1026   if (NULL != ctx.stack_head)
1027   {
1028     error_msg = "Creating the NFA failed. NFA stack was not empty!";
1029     goto error;
1030   }
1031
1032   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1033               "Created NFA with %i States and a total of %i Transitions\n",
1034               ctx.state_id, ctx.transition_id);
1035
1036   return nfa;
1037
1038 error:
1039   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
1040   if (NULL != error_msg)
1041     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
1042   GNUNET_free (p);
1043   while (NULL != ctx.stack_tail)
1044   {
1045     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
1046     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
1047                                  ctx.stack_tail);
1048   }
1049   return NULL;
1050 }
1051
1052 /**
1053  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
1054  * data structure.
1055  *
1056  * @param a automaton to be destroyed
1057  */
1058 void
1059 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
1060 {
1061   struct State *s;
1062   struct State *next_state;
1063
1064   if (NULL == a)
1065     return;
1066
1067   for (s = a->states_head; NULL != s;)
1068   {
1069     next_state = s->next;
1070     automaton_destroy_state (s);
1071     s = next_state;
1072   }
1073
1074   GNUNET_free (a);
1075 }
1076
1077 /**
1078  * Construct DFA for the given 'regex' of length 'len'
1079  *
1080  * @param regex regular expression string
1081  * @param len length of the regular expression
1082  *
1083  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1084  */
1085 struct GNUNET_REGEX_Automaton *
1086 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
1087 {
1088   struct GNUNET_REGEX_Context ctx;
1089   struct GNUNET_REGEX_Automaton *dfa;
1090   struct GNUNET_REGEX_Automaton *nfa;
1091   struct StateSet *tmp;
1092   struct StateSet *nfa_set;
1093   struct StateSet *dfa_stack;
1094   struct Transition *ctran;
1095   struct State *dfa_state;
1096   struct State *new_dfa_state;
1097   struct State *state_contains;
1098   struct State *state_iter;
1099
1100   GNUNET_REGEX_context_init (&ctx);
1101
1102   // Create NFA
1103   nfa = GNUNET_REGEX_construct_nfa (regex, len);
1104
1105   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1106   dfa->type = DFA;
1107
1108   // Create DFA start state from epsilon closure
1109   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
1110   nfa_set = nfa_closure_create (nfa->start, 0);
1111   dfa->start = dfa_state_create (&ctx, nfa_set);
1112   GNUNET_CONTAINER_DLL_insert (dfa->states_head, dfa->states_tail, dfa->start);
1113   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
1114   while (dfa_stack->len > 0)
1115   {
1116     dfa_state = dfa_stack->states[dfa_stack->len - 1];
1117     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1118
1119     for (ctran = dfa_state->transitions_head; NULL != ctran;
1120          ctran = ctran->next)
1121     {
1122       if (0 != ctran->literal && NULL == ctran->state)
1123       {
1124         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1125         nfa_set = nfa_closure_set_create (tmp, 0);
1126         state_set_clear (tmp);
1127         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1128         state_contains = NULL;
1129         for (state_iter = dfa->states_head; NULL != state_iter;
1130              state_iter = state_iter->next)
1131         {
1132           if (0 ==
1133               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1134             state_contains = state_iter;
1135         }
1136
1137         if (NULL == state_contains)
1138         {
1139           GNUNET_CONTAINER_DLL_insert_tail (dfa->states_head, dfa->states_tail,
1140                                             new_dfa_state);
1141           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1142                                new_dfa_state);
1143           ctran->state = new_dfa_state;
1144         }
1145         else
1146         {
1147           ctran->state = state_contains;
1148           automaton_destroy_state (new_dfa_state);
1149         }
1150       }
1151     }
1152   }
1153
1154   GNUNET_free (dfa_stack);
1155   GNUNET_REGEX_automaton_destroy (nfa);
1156
1157   dfa_minimize (dfa);
1158
1159   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
1160               ctx.state_id);
1161
1162   return dfa;
1163 }
1164
1165 /**
1166  * Save the given automaton as a GraphViz dot file
1167  *
1168  * @param a the automaton to be saved
1169  * @param filename where to save the file
1170  */
1171 void
1172 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1173                                    const char *filename)
1174 {
1175   struct State *s;
1176   struct Transition *ctran;
1177   char *s_acc = NULL;
1178   char *s_tran = NULL;
1179   char *start;
1180   char *end;
1181   FILE *p;
1182
1183   if (NULL == a)
1184   {
1185     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1186     return;
1187   }
1188
1189   if (NULL == filename || strlen (filename) < 1)
1190   {
1191     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1192     return;
1193   }
1194
1195   p = fopen (filename, "w");
1196
1197   if (p == NULL)
1198   {
1199     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1200                 filename);
1201     return;
1202   }
1203
1204   start = "digraph G {\nrankdir=LR\n";
1205   fwrite (start, strlen (start), 1, p);
1206
1207   for (s = a->states_head; NULL != s; s = s->next)
1208   {
1209     if (s->accepting)
1210     {
1211       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1212       fwrite (s_acc, strlen (s_acc), 1, p);
1213       GNUNET_free (s_acc);
1214     }
1215
1216     s->marked = 1;
1217
1218     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1219     {
1220       if (NULL == ctran->state)
1221       {
1222         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1223                     "Transition from State %i has has no state for transitioning\n",
1224                     s->id);
1225         continue;
1226       }
1227
1228       if (ctran->literal == 0)
1229       {
1230         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1231                          s->name, ctran->state->name);
1232       }
1233       else
1234       {
1235         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1236                          s->name, ctran->state->name, ctran->literal);
1237       }
1238
1239       fwrite (s_tran, strlen (s_tran), 1, p);
1240       GNUNET_free (s_tran);
1241     }
1242   }
1243
1244   end = "\n}\n";
1245   fwrite (end, strlen (end), 1, p);
1246   fclose (p);
1247 }
1248
1249 /**
1250  * Evaluates the given string using the given DFA automaton
1251  *
1252  * @param a automaton, type must be DFA
1253  * @param string string that should be evaluated
1254  *
1255  * @return 0 if string matches, non 0 otherwise
1256  */
1257 static int
1258 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1259 {
1260   const char *strp;
1261   struct State *s;
1262
1263   if (DFA != a->type)
1264   {
1265     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1266                 "Tried to evaluate DFA, but NFA automaton given");
1267     return -1;
1268   }
1269
1270   s = a->start;
1271
1272   for (strp = string; NULL != strp && *strp; strp++)
1273   {
1274     s = dfa_move (s, *strp);
1275     if (NULL == s)
1276       break;
1277   }
1278
1279   if (NULL != s && s->accepting)
1280     return 0;
1281
1282   return 1;
1283 }
1284
1285 /**
1286  * Evaluates the given string using the given NFA automaton
1287  *
1288  * @param a automaton, type must be NFA
1289  * @param string string that should be evaluated
1290  *
1291  * @return 0 if string matches, non 0 otherwise
1292  */
1293 static int
1294 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1295 {
1296   const char *strp;
1297   struct State *s;
1298   struct StateSet *sset;
1299   struct StateSet *new_sset;
1300   int i;
1301   int result;
1302
1303   if (NFA != a->type)
1304   {
1305     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1306                 "Tried to evaluate NFA, but DFA automaton given");
1307     return -1;
1308   }
1309
1310   result = 1;
1311   strp = string;
1312   sset = nfa_closure_create (a->start, 0);
1313
1314   for (strp = string; NULL != strp && *strp; strp++)
1315   {
1316     new_sset = nfa_closure_set_create (sset, *strp);
1317     state_set_clear (sset);
1318     sset = nfa_closure_set_create (new_sset, 0);
1319     state_set_clear (new_sset);
1320   }
1321
1322   for (i = 0; i < sset->len; i++)
1323   {
1324     s = sset->states[i];
1325     if (NULL != s && s->accepting)
1326     {
1327       result = 0;
1328       break;
1329     }
1330   }
1331
1332   state_set_clear (sset);
1333   return result;
1334 }
1335
1336
1337 /**
1338  * Evaluates the given 'string' against the given compiled regex
1339  *
1340  * @param a automaton
1341  * @param string string to check
1342  *
1343  * @return 0 if string matches, non 0 otherwise
1344  */
1345 int
1346 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1347 {
1348   int result;
1349
1350   switch (a->type)
1351   {
1352   case DFA:
1353     result = evaluate_dfa (a, string);
1354     break;
1355   case NFA:
1356     result = evaluate_nfa (a, string);
1357     break;
1358   default:
1359     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1360                 "Evaluating regex failed, automaton has no type!\n");
1361     result = GNUNET_SYSERR;
1362     break;
1363   }
1364
1365   return result;
1366 }