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 void
  31 stack_push (struct GNUNET_CONTAINER_SList *stack, const void *buf, size_t len)
  32 {
  33   GNUNET_CONTAINER_slist_add (stack, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
  34                               buf, len);
  35 }
  36
  37 int
  38 stack_empty (struct GNUNET_CONTAINER_SList *stack)
  39 {
  40   return 0 == GNUNET_CONTAINER_slist_count (stack);
  41 }
  42
  43 void *
  44 stack_pop (struct GNUNET_CONTAINER_SList *stack, size_t length)
  45 {
  46   struct GNUNET_CONTAINER_SList_Iterator it;
  47   void *val;
  48   size_t len;
  49
  50   it = GNUNET_CONTAINER_slist_begin (stack);
  51   val = GNUNET_CONTAINER_slist_get (&it, &len);
  52   GNUNET_assert (length == len);
  53   GNUNET_CONTAINER_slist_erase (&it);
  54   GNUNET_CONTAINER_slist_iter_destroy (&it);
  55
  56   return val;
  57 }
  58
  59 void *
  60 stack_top (struct GNUNET_CONTAINER_SList *stack, size_t * len)
  61 {
  62   struct GNUNET_CONTAINER_SList_Iterator it;
  63
  64   if (stack_empty (stack))
  65     return NULL;
  66
  67   return GNUNET_CONTAINER_slist_get (&it, len);
  68 }
  69
  70 struct State
  71 {
  72   unsigned int id;
  73   int accepting;
  74   int marked;
  75   char *name;
  76   struct GNUNET_CONTAINER_SList *transitions;
  77   struct GNUNET_CONTAINER_SList *nfa_set;
  78 };
  79
  80 struct GNUNET_REGEX_Automaton
  81 {
  82   struct State *start;
  83   struct State *end;
  84   struct GNUNET_CONTAINER_SList *states;
  85 };
  86
  87 struct Transition
  88 {
  89   unsigned int id;
  90   char literal;
  91   struct State *state;
  92 };
  93
  94 struct GNUNET_REGEX_Context
  95 {
  96   unsigned int state_id;
  97   unsigned int transition_id;
  98   struct GNUNET_CONTAINER_SList *stack;
  99 };
 100
 101 void
 102 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
 103 {
 104   if (NULL == ctx)
 105   {
 106     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
 107     return;
 108   }
 109   ctx->state_id = 0;
 110   ctx->transition_id = 0;
 111   ctx->stack = GNUNET_CONTAINER_slist_create ();
 112 }
 113
 114 void
 115 GNUNET_REGEX_context_destroy (struct GNUNET_REGEX_Context *ctx)
 116 {
 117   if (NULL != ctx->stack)
 118     GNUNET_CONTAINER_slist_destroy (ctx->stack);
 119 }
 120
 121 void
 122 debug_print_state (struct State *s)
 123 {
 124   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 125               "State %i: %s marked: %i accepting: %i\n", s->id, s->name,
 126               s->marked, s->accepting);
 127 }
 128
 129 void
 130 debug_print_states (struct GNUNET_CONTAINER_SList *states)
 131 {
 132   struct GNUNET_CONTAINER_SList_Iterator it;
 133   struct State *s;
 134
 135   for (it = GNUNET_CONTAINER_slist_begin (states);
 136        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 137        GNUNET_CONTAINER_slist_next (&it))
 138   {
 139     s = GNUNET_CONTAINER_slist_get (&it, NULL);
 140     debug_print_state (s);
 141   }
 142   GNUNET_CONTAINER_slist_iter_destroy (&it);
 143 }
 144
 145 void
 146 debug_print_transitions (struct State *s)
 147 {
 148   struct GNUNET_CONTAINER_SList_Iterator it;
 149   struct Transition *t;
 150   char *state;
 151   char literal;
 152
 153   for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
 154        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 155        GNUNET_CONTAINER_slist_next (&it))
 156   {
 157     t = GNUNET_CONTAINER_slist_get (&it, NULL);
 158
 159     if (0 == t->literal)
 160       literal = '0';
 161     else
 162       literal = t->literal;
 163
 164     if (NULL == t->state)
 165       state = "NULL";
 166     else
 167       state = t->state->name;
 168
 169     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
 170                 literal, state);
 171   }
 172
 173   GNUNET_CONTAINER_slist_iter_destroy (&it);
 174 }
 175
 176 int
 177 set_compare (const void *buf1, const size_t len1, const void *buf2,
 178              const size_t len2)
 179 {
 180   int c1;
 181   int c2;
 182   struct GNUNET_CONTAINER_SList_Iterator it1;
 183   struct GNUNET_CONTAINER_SList_Iterator it2;
 184   struct State *s1;
 185   struct State *s2;
 186   struct GNUNET_CONTAINER_SList *l1;
 187   struct GNUNET_CONTAINER_SList *l2;
 188   const void *el1;
 189   const void *el2;
 190   size_t length1;
 191   size_t length2;
 192   int rslt;
 193   int contains;
 194
 195   if (len1 != len2 && len1 != sizeof (struct State) &&
 196       len2 != sizeof (struct State))
 197     return 1;
 198
 199   s1 = (struct State *) buf1;
 200   s2 = (struct State *) buf2;
 201
 202   l1 = s1->nfa_set;
 203   l2 = s2->nfa_set;
 204
 205   c1 = GNUNET_CONTAINER_slist_count (l1);
 206   c2 = GNUNET_CONTAINER_slist_count (l2);
 207
 208   if (c1 != c2)
 209     return ((c1 > c2) ? 1 : -1);
 210
 211   rslt = 0;
 212
 213   for (it1 = GNUNET_CONTAINER_slist_begin (l1);
 214        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it1);
 215        GNUNET_CONTAINER_slist_next (&it1))
 216   {
 217     el1 = GNUNET_CONTAINER_slist_get (&it1, &length1);
 218     contains = 0;
 219
 220     for (it2 = GNUNET_CONTAINER_slist_begin (l2);
 221          GNUNET_YES != GNUNET_CONTAINER_slist_end (&it2);
 222          GNUNET_CONTAINER_slist_next (&it2))
 223     {
 224       el2 = GNUNET_CONTAINER_slist_get (&it2, &length2);
 225
 226       if (length1 != length2)
 227       {
 228         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 229                     "Comparing lists failed, element size mismatch\n");
 230         break;
 231       }
 232       if (((struct State *) el1)->id == ((struct State *) el2)->id)
 233       {
 234         contains = 1;
 235         break;
 236       }
 237     }
 238     GNUNET_CONTAINER_slist_iter_destroy (&it2);
 239
 240     if (0 == contains)
 241     {
 242       rslt = 1;
 243       break;
 244     }
 245   }
 246   GNUNET_CONTAINER_slist_iter_destroy (&it1);
 247
 248   return rslt;
 249 }
 250
 251 int
 252 transition_literal_compare (const void *buf1, const size_t len1,
 253                             const void *buf2, const size_t len2)
 254 {
 255   struct Transition *t1;
 256   struct Transition *t2;
 257
 258   if (len1 != len2 && len1 != sizeof (struct Transition) &&
 259       len2 != sizeof (struct Transition))
 260   {
 261     return 1;
 262   }
 263
 264   t1 = (struct Transition *) buf1;
 265   t2 = (struct Transition *) buf2;
 266
 267   if (t1->literal == t2->literal)
 268     return 0;
 269   else if (t1->literal > t2->literal)
 270     return 1;
 271   else
 272     return -1;
 273 }
 274
 275 void
 276 add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state,
 277                 const char literal, struct State *to_state)
 278 {
 279   struct Transition t;
 280
 281   if (NULL == from_state)
 282   {
 283     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 284     return;
 285   }
 286
 287   t.id = ctx->transition_id++;
 288   t.literal = literal;
 289   t.state = to_state;
 290
 291   GNUNET_CONTAINER_slist_add (from_state->transitions,
 292                               GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT, &t,
 293                               sizeof t);
 294 }
 295
 296 struct State *
 297 dfa_create_state (struct GNUNET_REGEX_Context *ctx,
 298                   struct GNUNET_CONTAINER_SList *states)
 299 {
 300   struct State *s;
 301   char *name;
 302   struct GNUNET_CONTAINER_SList_Iterator stateit;
 303   struct GNUNET_CONTAINER_SList_Iterator tranit;
 304   int len = 0;
 305   struct State *cstate;
 306   struct Transition *ctran;
 307
 308   s = GNUNET_malloc (sizeof (struct State));
 309   s->id = ctx->state_id++;
 310   s->accepting = 0;
 311   s->transitions = GNUNET_CONTAINER_slist_create ();
 312   s->marked = 0;
 313   s->name = NULL;
 314
 315   if (NULL == states)
 316     return s;
 317
 318   s->nfa_set = states;
 319
 320   if (0 == GNUNET_CONTAINER_slist_count (states))
 321     return s;
 322
 323
 324   // Create a name based on 'sset'
 325   s->name = GNUNET_malloc (sizeof (char) * 2);
 326   strcat (s->name, "{");
 327   name = NULL;
 328
 329   for (stateit = GNUNET_CONTAINER_slist_begin (states);
 330        GNUNET_NO == GNUNET_CONTAINER_slist_end (&stateit);
 331        GNUNET_CONTAINER_slist_next (&stateit))
 332   {
 333     cstate = GNUNET_CONTAINER_slist_get (&stateit, NULL);
 334     GNUNET_CONTAINER_slist_iter_destroy (&tranit);
 335     GNUNET_asprintf (&name, "%i,", cstate->id);
 336
 337     if (NULL != name)
 338     {
 339       len = strlen (s->name) + strlen (name) + 1;
 340       s->name = GNUNET_realloc (s->name, len);
 341       strcat (s->name, name);
 342       GNUNET_free (name);
 343       name = NULL;
 344     }
 345
 346     // Add a transition for each distinct literal to NULL state
 347     for (tranit = GNUNET_CONTAINER_slist_begin (cstate->transitions);
 348          GNUNET_NO == GNUNET_CONTAINER_slist_end (&tranit);
 349          GNUNET_CONTAINER_slist_next (&tranit))
 350     {
 351       ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
 352       if (0 != ctran->literal &&
 353           NULL == GNUNET_CONTAINER_slist_contains2 (s->transitions, ctran,
 354                                                     sizeof *ctran,
 355                                                     &transition_literal_compare))
 356       {
 357         add_transition (ctx, s, ctran->literal, NULL);
 358       }
 359     }
 360
 361     if (cstate->accepting)
 362       s->accepting = 1;
 363   }
 364   GNUNET_CONTAINER_slist_iter_destroy (&stateit);
 365
 366   s->name[strlen (s->name) - 1] = '}';
 367
 368   return s;
 369 }
 370
 371 void
 372 dfa_clear_nfa_set (struct GNUNET_CONTAINER_SList *states)
 373 {
 374   struct GNUNET_CONTAINER_SList_Iterator it;
 375   struct State *s;
 376
 377   for (it = GNUNET_CONTAINER_slist_begin (states);
 378        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 379        GNUNET_CONTAINER_slist_next (&it))
 380   {
 381     s = GNUNET_CONTAINER_slist_get (&it, NULL);
 382     if (NULL != s->nfa_set)
 383     {
 384       GNUNET_CONTAINER_slist_destroy (s->nfa_set);
 385       s->nfa_set = NULL;
 386     }
 387   }
 388
 389   GNUNET_CONTAINER_slist_iter_destroy (&it);
 390 }
 391
 392 struct GNUNET_REGEX_Automaton *
 393 nfa_create (struct State *start, struct State *end)
 394 {
 395   struct GNUNET_REGEX_Automaton *n;
 396
 397   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 398
 399   n->start = NULL;
 400   n->end = NULL;
 401   n->states = GNUNET_CONTAINER_slist_create ();
 402
 403   if (NULL == start && NULL == end)
 404     return n;
 405
 406   GNUNET_CONTAINER_slist_add (n->states,
 407                               GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, end,
 408                               sizeof *end);
 409
 410   GNUNET_CONTAINER_slist_add (n->states,
 411                               GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, start,
 412                               sizeof *start);
 413
 414   n->start = start;
 415   n->end = end;
 416
 417   return n;
 418 }
 419
 420 void
 421 nfa_add_states (struct GNUNET_REGEX_Automaton *n,
 422                 struct GNUNET_CONTAINER_SList *states)
 423 {
 424   // This isn't very pretty. Would be better to use GNUNET_CONTAINER_slist_append, but
 425   // this function adds to the beginning of dst, which currently breaks "pretty"
 426   // printing of the graph...
 427   struct GNUNET_CONTAINER_SList_Iterator i;
 428   struct State *s;
 429
 430   for (i = GNUNET_CONTAINER_slist_begin (states);
 431        GNUNET_CONTAINER_slist_end (&i) != GNUNET_YES;
 432        GNUNET_CONTAINER_slist_next (&i))
 433
 434   {
 435     s = GNUNET_CONTAINER_slist_get (&i, NULL);
 436     GNUNET_CONTAINER_slist_add_end (n->states,
 437                                     GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 438                                     s, sizeof *s);
 439   }
 440   GNUNET_CONTAINER_slist_iter_destroy (&i);
 441 }
 442
 443 struct State *
 444 nfa_create_state (struct GNUNET_REGEX_Context *ctx, int accepting)
 445 {
 446   struct State *s;
 447
 448   s = GNUNET_malloc (sizeof (struct State));
 449   s->id = ctx->state_id++;
 450   s->accepting = accepting;
 451   s->transitions = GNUNET_CONTAINER_slist_create ();
 452   s->marked = 0;
 453   s->name = NULL;
 454   GNUNET_asprintf (&s->name, "s%i", s->id);
 455
 456   return s;
 457 }
 458
 459 void
 460 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
 461 {
 462   GNUNET_CONTAINER_slist_destroy (a->states);
 463   a->start = NULL;
 464   a->end = NULL;
 465   GNUNET_free (a);
 466 }
 467
 468 void
 469 automaton_destroy_state (struct State *s)
 470 {
 471   if (NULL != s->transitions)
 472     GNUNET_CONTAINER_slist_destroy (s->transitions);
 473   if (NULL != s->name)
 474     GNUNET_free (s->name);
 475   if (NULL != s->nfa_set)
 476     GNUNET_CONTAINER_slist_destroy (s->nfa_set);
 477   GNUNET_free (s);
 478 }
 479
 480 void
 481 mark_all_states (struct GNUNET_REGEX_Automaton *n, int marked)
 482 {
 483   struct GNUNET_CONTAINER_SList_Iterator it;
 484   struct State *s;
 485
 486   for (it = GNUNET_CONTAINER_slist_begin (n->states);
 487        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 488        GNUNET_CONTAINER_slist_next (&it))
 489   {
 490     s = GNUNET_CONTAINER_slist_get (&it, NULL);
 491     s->marked = marked;
 492   }
 493
 494   GNUNET_CONTAINER_slist_iter_destroy (&it);
 495 }
 496
 497 void
 498 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 499 {
 500   struct GNUNET_REGEX_Automaton *a;
 501   struct GNUNET_REGEX_Automaton *b;
 502   struct GNUNET_REGEX_Automaton *new;
 503
 504   b = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 505   a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 506
 507   add_transition (ctx, a->end, 0, b->start);
 508   a->end->accepting = 0;
 509   b->end->accepting = 1;
 510
 511   new = nfa_create (NULL, NULL);
 512   nfa_add_states (new, a->states);
 513   nfa_add_states (new, b->states);
 514   new->start = a->start;
 515   new->end = b->end;
 516   automaton_fragment_clear (a);
 517   automaton_fragment_clear (b);
 518
 519   stack_push (ctx->stack, new, sizeof *new);
 520 }
 521
 522 void
 523 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 524 {
 525   struct GNUNET_REGEX_Automaton *a;
 526   struct GNUNET_REGEX_Automaton *new;
 527   struct State *start;
 528   struct State *end;
 529
 530   a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 531
 532   if (NULL == a)
 533   {
 534     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 535                 "nfa_add_star_op failed, because there was no element on the stack");
 536     return;
 537   }
 538
 539   start = nfa_create_state (ctx, 0);
 540   end = nfa_create_state (ctx, 1);
 541
 542   add_transition (ctx, start, 0, a->start);
 543   add_transition (ctx, start, 0, end);
 544   add_transition (ctx, a->end, 0, a->start);
 545   add_transition (ctx, a->end, 0, end);
 546
 547   a->end->accepting = 0;
 548   end->accepting = 1;
 549
 550   new = nfa_create (start, end);
 551   nfa_add_states (new, a->states);
 552   automaton_fragment_clear (a);
 553
 554   stack_push (ctx->stack, new, sizeof *new);
 555 }
 556
 557 void
 558 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 559 {
 560   struct GNUNET_REGEX_Automaton *a;
 561
 562   a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 563
 564   add_transition (ctx, a->end, 0, a->start);
 565
 566   stack_push (ctx->stack, a, sizeof *a);
 567 }
 568
 569 void
 570 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 571 {
 572   struct GNUNET_REGEX_Automaton *a;
 573   struct GNUNET_REGEX_Automaton *b;
 574   struct GNUNET_REGEX_Automaton *new;
 575   struct State *start;
 576   struct State *end;
 577
 578   b = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 579   a = stack_pop (ctx->stack, sizeof (struct GNUNET_REGEX_Automaton));
 580
 581   start = nfa_create_state (ctx, 0);
 582   end = nfa_create_state (ctx, 1);
 583   add_transition (ctx, start, 0, a->start);
 584   add_transition (ctx, start, 0, b->start);
 585
 586   add_transition (ctx, a->end, 0, end);
 587   add_transition (ctx, b->end, 0, end);
 588
 589   a->end->accepting = 0;
 590   b->end->accepting = 0;
 591   end->accepting = 1;
 592
 593   new = nfa_create (start, end);
 594   nfa_add_states (new, a->states);
 595   nfa_add_states (new, b->states);
 596   automaton_fragment_clear (a);
 597   automaton_fragment_clear (b);
 598
 599   stack_push (ctx->stack, new, sizeof *new);
 600 }
 601
 602 void
 603 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 604 {
 605   struct GNUNET_REGEX_Automaton *n;
 606   struct State *start;
 607   struct State *end;
 608
 609   start = nfa_create_state (ctx, 0);
 610   end = nfa_create_state (ctx, 1);
 611   add_transition (ctx, start, lit, end);
 612   n = nfa_create (start, end);
 613   stack_push (ctx->stack, n, sizeof *n);
 614 }
 615
 616 /**
 617  * Calculates the closure set for the given set of states.
 618  *
 619  * @param states set of states for which to calculate the closure
 620  * @param count number of states in 'states'
 621  * @param literal for the transition
 622  *
 623  * @return set of states that can be reached from the given 'states' when
 624  *         using only 'literal' transitions
 625  */
 626 struct GNUNET_CONTAINER_SList *
 627 create_nfa_closure (struct GNUNET_CONTAINER_SList *states, const char literal)
 628 {
 629   struct GNUNET_CONTAINER_SList_Iterator stateit;
 630   struct GNUNET_CONTAINER_SList_Iterator tranit;
 631   struct GNUNET_CONTAINER_SList *cls;
 632   struct GNUNET_CONTAINER_SList *cls_check;
 633   struct State *s;
 634   struct State *currentstate;
 635   struct Transition *currenttransition;
 636   struct State *clsstate;
 637
 638   cls = GNUNET_CONTAINER_slist_create ();
 639
 640   for (stateit = GNUNET_CONTAINER_slist_begin (states);
 641        GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
 642        GNUNET_CONTAINER_slist_next (&stateit))
 643   {
 644     s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
 645     cls_check = GNUNET_CONTAINER_slist_create ();
 646
 647     // Add start state to closure only for epsilon closure
 648     if (0 == literal)
 649     {
 650       GNUNET_CONTAINER_slist_add (cls,
 651                                   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, s,
 652                                   sizeof *s);
 653     }
 654
 655     stack_push (cls_check, s, sizeof *s);
 656
 657     while (!stack_empty (cls_check))
 658     {
 659       currentstate = stack_pop (cls_check, sizeof (struct State));
 660
 661       for (tranit = GNUNET_CONTAINER_slist_begin (currentstate->transitions);
 662            GNUNET_CONTAINER_slist_end (&tranit) != GNUNET_YES;
 663            GNUNET_CONTAINER_slist_next (&tranit))
 664       {
 665         currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
 666
 667         if (NULL != currenttransition->state &&
 668             literal == currenttransition->literal)
 669         {
 670           clsstate = currenttransition->state;
 671
 672           if (NULL == clsstate)
 673             break;
 674
 675           if (GNUNET_YES !=
 676               GNUNET_CONTAINER_slist_contains (cls, clsstate, sizeof *clsstate))
 677           {
 678             GNUNET_CONTAINER_slist_add (cls,
 679                                         GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 680                                         clsstate, sizeof *clsstate);
 681             stack_push (cls_check, clsstate, sizeof *clsstate);
 682           }
 683         }
 684       }
 685       GNUNET_CONTAINER_slist_iter_destroy (&tranit);
 686     }
 687
 688     GNUNET_assert (stack_empty (cls_check));
 689     GNUNET_CONTAINER_slist_destroy (cls_check);
 690   }
 691   GNUNET_CONTAINER_slist_iter_destroy (&stateit);
 692
 693   return cls;
 694 }
 695
 696 struct GNUNET_CONTAINER_SList *
 697 GNUNET_REGEX_move (struct GNUNET_REGEX_Automaton *a, struct State *s,
 698                    const char literal)
 699 {
 700   struct GNUNET_CONTAINER_SList *l;
 701   struct GNUNET_CONTAINER_SList_Iterator it;
 702   struct Transition *ctran;
 703
 704   if (!GNUNET_CONTAINER_slist_contains (a->states, s, sizeof *s))
 705   {
 706     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 707                 "State %s is not part of the given automaton", s->name);
 708     return NULL;
 709   }
 710
 711   l = GNUNET_CONTAINER_slist_create ();
 712
 713   for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
 714        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 715        GNUNET_CONTAINER_slist_next (&it))
 716   {
 717     ctran = GNUNET_CONTAINER_slist_get (&it, NULL);
 718     if (literal == ctran->literal)
 719       GNUNET_CONTAINER_slist_add (l, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 720                                   ctran->state, sizeof *(ctran->state));
 721   }
 722   GNUNET_CONTAINER_slist_iter_destroy (&it);
 723
 724   return l;
 725 }
 726
 727 /**
 728  * Construct an NFA by parsing the regex string of length 'len'.
 729  *
 730  * @param regex regular expression string
 731  * @param len length of the string
 732  *
 733  * @return NFA.Needs to be freed using GNUNET_REGEX_destroy_automaton
 734  */
 735 struct GNUNET_REGEX_Automaton *
 736 GNUNET_REGEX_construct_nfa(const char *regex, const size_t len)
 737 {
 738   struct GNUNET_REGEX_Context ctx;
 739   struct GNUNET_REGEX_Automaton *nfa;
 740   char *error_msg;
 741   unsigned int count;
 742   unsigned int altcount;
 743   unsigned int atomcount;
 744   unsigned int pcount;
 745   struct
 746   {
 747     int altcount;
 748     int atomcount;
 749   }     *p;
 750
 751   GNUNET_REGEX_context_init (&ctx);
 752
 753   p = NULL;
 754   error_msg = NULL;
 755   altcount = 0;
 756   atomcount = 0;
 757   pcount = 0;
 758
 759   for (count = 0; count < len && *regex; count++, regex++)
 760   {
 761     switch (*regex)
 762     {
 763     case '(':
 764       if (atomcount > 1)
 765       {
 766         --atomcount;
 767         nfa_add_concatenation (&ctx);
 768       }
 769       GNUNET_array_grow (p, pcount, pcount + 1);
 770       p[pcount - 1].altcount = altcount;
 771       p[pcount - 1].atomcount = atomcount;
 772       altcount = 0;
 773       atomcount = 0;
 774       break;
 775     case '|':
 776       if (0 == atomcount)
 777       {
 778         error_msg = "Cannot append '|' to nothing";
 779         goto error;
 780       }
 781       while (--atomcount > 0)
 782         nfa_add_concatenation (&ctx);
 783       altcount++;
 784       break;
 785     case ')':
 786       if (0 == pcount)
 787       {
 788         error_msg = "Missing opening '('";
 789         goto error;
 790       }
 791       if (0 == atomcount)
 792       {
 793         // Ignore this: "()"
 794         pcount--;
 795         altcount = p[pcount].altcount;
 796         atomcount = p[pcount].atomcount;
 797         break;
 798       }
 799       while (--atomcount > 0)
 800         nfa_add_concatenation (&ctx);
 801       for (; altcount > 0; altcount--)
 802         nfa_add_alternation (&ctx);
 803       pcount--;
 804       altcount = p[pcount].altcount;
 805       atomcount = p[pcount].atomcount;
 806       atomcount++;
 807       break;
 808     case '*':
 809       if (atomcount == 0)
 810       {
 811         error_msg = "Cannot append '+' to nothing";
 812         goto error;
 813       }
 814       nfa_add_star_op (&ctx);
 815       break;
 816     case '+':
 817       if (atomcount == 0)
 818       {
 819         error_msg = "Cannot append '+' to nothing";
 820         goto error;
 821       }
 822       nfa_add_plus_op (&ctx);
 823       break;
 824     case 92:                   /* escape: \ */
 825       regex++;
 826       count++;
 827     default:
 828       if (atomcount > 1)
 829       {
 830         --atomcount;
 831         nfa_add_concatenation (&ctx);
 832       }
 833       nfa_add_literal (&ctx, *regex);
 834       atomcount++;
 835       break;
 836     }
 837   }
 838   if (0 != pcount)
 839   {
 840     error_msg = "Unbalanced parenthesis";
 841     goto error;
 842   }
 843   while (--atomcount > 0)
 844     nfa_add_concatenation (&ctx);
 845   for (; altcount > 0; altcount--)
 846     nfa_add_alternation (&ctx);
 847
 848   if (NULL != p)
 849     GNUNET_free (p);
 850
 851   nfa = stack_pop (ctx.stack, sizeof (struct GNUNET_REGEX_Automaton));
 852
 853   if (!stack_empty (ctx.stack))
 854   {
 855     error_msg = "Creating the NFA failed. NFA stack was not empty!";
 856     goto error;
 857   }
 858
 859   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 860               "Created NFA with %i States and a total of %i Transitions\n",
 861               GNUNET_CONTAINER_slist_count (nfa->states), ctx.transition_id);
 862
 863   GNUNET_REGEX_context_destroy (&ctx);
 864
 865   return nfa;
 866
 867 error:
 868   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
 869   if (NULL != error_msg)
 870     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
 871   GNUNET_free (p);
 872   while (!stack_empty (ctx.stack))
 873     GNUNET_REGEX_automaton_destroy (stack_pop (ctx.stack,
 874                                                sizeof (struct GNUNET_REGEX_Automaton)));
 875   GNUNET_REGEX_context_destroy (&ctx);
 876   return NULL;
 877 }
 878
 879 /**
 880  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
 881  * data structure.
 882  *
 883  * @param a automaton to be destroyed
 884  */
 885 void
 886 GNUNET_REGEX_automaton_destroy(struct GNUNET_REGEX_Automaton *a)
 887 {
 888   struct GNUNET_CONTAINER_SList_Iterator it;
 889
 890   if (NULL == a)
 891     return;
 892
 893   for (it = GNUNET_CONTAINER_slist_begin (a->states);
 894        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 895        GNUNET_CONTAINER_slist_next (&it))
 896   {
 897     automaton_destroy_state (GNUNET_CONTAINER_slist_get (&it, NULL));
 898   }
 899   GNUNET_CONTAINER_slist_iter_destroy (&it);
 900   GNUNET_CONTAINER_slist_destroy (a->states);
 901   GNUNET_free (a);
 902 }
 903
 904 /**
 905  * Construct DFA for the given 'regex' of lenght 'len'
 906  *
 907  * @param regex regular expression string
 908  * @param len length of the regular expression
 909  *
 910  * @return DFA. Needs to be freed using GNUNET_REGEX_destroy_automaton
 911  */
 912 struct GNUNET_REGEX_Automaton *
 913 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
 914 {
 915   struct GNUNET_REGEX_Context ctx;
 916   struct GNUNET_REGEX_Automaton *dfa;
 917   struct GNUNET_REGEX_Automaton *nfa;
 918   struct GNUNET_CONTAINER_SList *tmp;
 919   struct GNUNET_CONTAINER_SList *nfa_set;
 920   struct GNUNET_CONTAINER_SList *sset;
 921   struct GNUNET_CONTAINER_SList *dfa_stack;
 922   struct GNUNET_CONTAINER_SList_Iterator tranit;
 923   struct Transition *currenttransition;
 924   struct State *dfa_state;
 925   struct State *new_dfa_state;
 926   struct State *state_contains;
 927
 928   GNUNET_REGEX_context_init (&ctx);
 929
 930   // Create NFA
 931   nfa = GNUNET_REGEX_construct_nfa (regex, len);
 932
 933   dfa_stack = GNUNET_CONTAINER_slist_create ();
 934
 935   // Initialize new dfa
 936   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 937   dfa->states = GNUNET_CONTAINER_slist_create ();
 938
 939   // Create DFA start state from epsilon closure
 940   sset = GNUNET_CONTAINER_slist_create ();
 941   GNUNET_CONTAINER_slist_add (sset, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 942                               nfa->start, sizeof *(nfa->start));
 943   nfa_set = create_nfa_closure (sset, 0);
 944   GNUNET_CONTAINER_slist_destroy (sset);
 945   dfa->start = dfa_create_state (&ctx, nfa_set);
 946   GNUNET_CONTAINER_slist_add (dfa->states,
 947                               GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 948                               dfa->start, sizeof *(dfa->start));
 949   stack_push (dfa_stack, dfa->start, sizeof *(dfa->start));
 950
 951   while (!stack_empty (dfa_stack))
 952   {
 953     dfa_state = stack_pop (dfa_stack, sizeof (struct State));
 954
 955     for (tranit = GNUNET_CONTAINER_slist_begin (dfa_state->transitions);
 956          GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
 957          GNUNET_CONTAINER_slist_next (&tranit))
 958     {
 959       currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
 960
 961       if (0 != currenttransition->literal && NULL == currenttransition->state)
 962       {
 963         tmp = create_nfa_closure (dfa_state->nfa_set,
 964                                   currenttransition->literal);
 965         nfa_set = create_nfa_closure (tmp, 0);
 966         new_dfa_state = dfa_create_state (&ctx, nfa_set);
 967         GNUNET_CONTAINER_slist_destroy (tmp);
 968
 969         state_contains =
 970             GNUNET_CONTAINER_slist_contains2 (dfa->states, new_dfa_state,
 971                                               sizeof *new_dfa_state,
 972                                               &set_compare);
 973         if (NULL == state_contains)
 974         {
 975           GNUNET_CONTAINER_slist_add_end (dfa->states,
 976                                           GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 977                                           new_dfa_state, sizeof *new_dfa_state);
 978           stack_push (dfa_stack, new_dfa_state, sizeof *new_dfa_state);
 979           currenttransition->state = new_dfa_state;
 980         }
 981         else
 982           currenttransition->state = state_contains;
 983       }
 984     }
 985
 986     GNUNET_CONTAINER_slist_iter_destroy (&tranit);
 987   }
 988   GNUNET_CONTAINER_slist_destroy (dfa_stack);
 989   GNUNET_REGEX_automaton_destroy (nfa);
 990   GNUNET_REGEX_context_destroy (&ctx);
 991   dfa_clear_nfa_set (dfa->states);
 992
 993   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
 994               GNUNET_CONTAINER_slist_count (dfa->states));
 995
 996   return dfa;
 997 }
 998
 999 /**
1000  * Save the given automaton as a GraphViz dot file
1001  *
1002  * @param a the automaton to be saved
1003  * @param filename where to save the file
1004  */
1005 void
1006 GNUNET_REGEX_automaton_save_graph(struct GNUNET_REGEX_Automaton *a,
1007                                   const char *filename)
1008 {
1009   struct GNUNET_CONTAINER_SList_Iterator stateit;
1010   struct GNUNET_CONTAINER_SList_Iterator tranit;
1011   struct State *s;
1012   struct Transition *ctran;
1013   char *s_acc = NULL;
1014   char *s_tran = NULL;
1015   char *start;
1016   char *end;
1017   FILE *p;
1018
1019   if (NULL == a)
1020   {
1021     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1022     return;
1023   }
1024
1025   if (NULL == filename || strlen (filename) < 1)
1026   {
1027     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1028     return;
1029   }
1030
1031   p = fopen (filename, "w");
1032
1033   if (p == NULL)
1034   {
1035     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1036                 filename);
1037     return;
1038   }
1039
1040   start = "digraph G {\nrankdir=LR\n";
1041   fwrite (start, strlen (start), 1, p);
1042
1043   for (stateit = GNUNET_CONTAINER_slist_begin (a->states);
1044        GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
1045        GNUNET_CONTAINER_slist_next (&stateit))
1046   {
1047
1048     s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
1049
1050     if (s->accepting)
1051     {
1052       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1053       fwrite (s_acc, strlen (s_acc), 1, p);
1054       GNUNET_free (s_acc);
1055     }
1056
1057     s->marked = 1;
1058
1059     for (tranit = GNUNET_CONTAINER_slist_begin (s->transitions);
1060          GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
1061          GNUNET_CONTAINER_slist_next (&tranit))
1062     {
1063       ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
1064
1065       if (NULL == ctran->state)
1066       {
1067         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1068                     "Transition from State %i has has no state for transitioning\n",
1069                     s->id);
1070         continue;
1071       }
1072
1073       if (ctran->literal == 0)
1074       {
1075         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1076                          s->name, ctran->state->name);
1077       }
1078       else
1079       {
1080         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1081                          s->name, ctran->state->name, ctran->literal);
1082       }
1083
1084       fwrite (s_tran, strlen (s_tran), 1, p);
1085       GNUNET_free (s_tran);
1086     }
1087     GNUNET_CONTAINER_slist_iter_destroy (&tranit);
1088   }
1089   GNUNET_CONTAINER_slist_iter_destroy (&stateit);
1090
1091   end = "\n}\n";
1092   fwrite (end, strlen (end), 1, p);
1093   fclose (p);
1094 }