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