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