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 list of states on which to base the closure on
 620  * @param literal transitioning literal for which to base the closure on,
 621  *                pass 0 for epsilon transition
 622  *
 623  * @return nfa closure on literal (epsilon closure if 'literal' == 0)
 624  */
 625 struct GNUNET_CONTAINER_SList *
 626 create_nfa_closure (struct GNUNET_CONTAINER_SList *states, const char literal)
 627 {
 628   struct GNUNET_CONTAINER_SList_Iterator stateit;
 629   struct GNUNET_CONTAINER_SList_Iterator tranit;
 630   struct GNUNET_CONTAINER_SList *cls;
 631   struct GNUNET_CONTAINER_SList *cls_check;
 632   struct State *s;
 633   struct State *currentstate;
 634   struct Transition *currenttransition;
 635   struct State *clsstate;
 636
 637   cls = GNUNET_CONTAINER_slist_create ();
 638
 639   for (stateit = GNUNET_CONTAINER_slist_begin (states);
 640        GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
 641        GNUNET_CONTAINER_slist_next (&stateit))
 642   {
 643     s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
 644     cls_check = GNUNET_CONTAINER_slist_create ();
 645
 646     // Add start state to closure only for epsilon closure
 647     if (0 == literal)
 648     {
 649       GNUNET_CONTAINER_slist_add (cls,
 650                                   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC, s,
 651                                   sizeof *s);
 652     }
 653
 654     stack_push (cls_check, s, sizeof *s);
 655
 656     while (!stack_empty (cls_check))
 657     {
 658       currentstate = stack_pop (cls_check, sizeof (struct State));
 659
 660       for (tranit = GNUNET_CONTAINER_slist_begin (currentstate->transitions);
 661            GNUNET_CONTAINER_slist_end (&tranit) != GNUNET_YES;
 662            GNUNET_CONTAINER_slist_next (&tranit))
 663       {
 664         currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
 665
 666         if (NULL != currenttransition->state &&
 667             literal == currenttransition->literal)
 668         {
 669           clsstate = currenttransition->state;
 670
 671           if (NULL == clsstate)
 672             break;
 673
 674           if (GNUNET_YES !=
 675               GNUNET_CONTAINER_slist_contains (cls, clsstate, sizeof *clsstate))
 676           {
 677             GNUNET_CONTAINER_slist_add (cls,
 678                                         GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 679                                         clsstate, sizeof *clsstate);
 680             stack_push (cls_check, clsstate, sizeof *clsstate);
 681           }
 682         }
 683       }
 684       GNUNET_CONTAINER_slist_iter_destroy (&tranit);
 685     }
 686
 687     GNUNET_assert (stack_empty (cls_check));
 688     GNUNET_CONTAINER_slist_destroy (cls_check);
 689   }
 690   GNUNET_CONTAINER_slist_iter_destroy (&stateit);
 691
 692   return cls;
 693 }
 694
 695 struct GNUNET_CONTAINER_SList *
 696 GNUNET_REGEX_move (struct GNUNET_REGEX_Automaton *a, struct State *s,
 697                    const char literal)
 698 {
 699   struct GNUNET_CONTAINER_SList *l;
 700   struct GNUNET_CONTAINER_SList_Iterator it;
 701   struct Transition *ctran;
 702
 703   if (!GNUNET_CONTAINER_slist_contains (a->states, s, sizeof *s))
 704   {
 705     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 706                 "State %s is not part of the given automaton", s->name);
 707     return NULL;
 708   }
 709
 710   l = GNUNET_CONTAINER_slist_create ();
 711
 712   for (it = GNUNET_CONTAINER_slist_begin (s->transitions);
 713        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 714        GNUNET_CONTAINER_slist_next (&it))
 715   {
 716     ctran = GNUNET_CONTAINER_slist_get (&it, NULL);
 717     if (literal == ctran->literal)
 718       GNUNET_CONTAINER_slist_add (l, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 719                                   ctran->state, sizeof *(ctran->state));
 720   }
 721   GNUNET_CONTAINER_slist_iter_destroy (&it);
 722
 723   return l;
 724 }
 725
 726 /**
 727  * Construct an NFA by parsing the regex string of length 'len'.
 728  *
 729  * @param regex regular expression string
 730  * @param len length of the string
 731  *
 732  * @return NFA.Needs to be freed using GNUNET_REGEX_destroy_automaton
 733  */
 734 struct GNUNET_REGEX_Automaton *
 735 GNUNET_REGEX_construct_nfa(const char *regex, const size_t len)
 736 {
 737   struct GNUNET_REGEX_Context ctx;
 738   struct GNUNET_REGEX_Automaton *nfa;
 739   char *error_msg;
 740   unsigned int count;
 741   unsigned int altcount;
 742   unsigned int atomcount;
 743   unsigned int pcount;
 744   struct
 745   {
 746     int altcount;
 747     int atomcount;
 748   }     *p;
 749
 750   GNUNET_REGEX_context_init (&ctx);
 751
 752   p = NULL;
 753   error_msg = NULL;
 754   altcount = 0;
 755   atomcount = 0;
 756   pcount = 0;
 757
 758   for (count = 0; count < len && *regex; count++, regex++)
 759   {
 760     switch (*regex)
 761     {
 762     case '(':
 763       if (atomcount > 1)
 764       {
 765         --atomcount;
 766         nfa_add_concatenation (&ctx);
 767       }
 768       GNUNET_array_grow (p, pcount, pcount + 1);
 769       p[pcount - 1].altcount = altcount;
 770       p[pcount - 1].atomcount = atomcount;
 771       altcount = 0;
 772       atomcount = 0;
 773       break;
 774     case '|':
 775       if (0 == atomcount)
 776       {
 777         error_msg = "Cannot append '|' to nothing";
 778         goto error;
 779       }
 780       while (--atomcount > 0)
 781         nfa_add_concatenation (&ctx);
 782       altcount++;
 783       break;
 784     case ')':
 785       if (0 == pcount)
 786       {
 787         error_msg = "Missing opening '('";
 788         goto error;
 789       }
 790       if (0 == atomcount)
 791       {
 792         // Ignore this: "()"
 793         pcount--;
 794         altcount = p[pcount].altcount;
 795         atomcount = p[pcount].atomcount;
 796         break;
 797       }
 798       while (--atomcount > 0)
 799         nfa_add_concatenation (&ctx);
 800       for (; altcount > 0; altcount--)
 801         nfa_add_alternation (&ctx);
 802       pcount--;
 803       altcount = p[pcount].altcount;
 804       atomcount = p[pcount].atomcount;
 805       atomcount++;
 806       break;
 807     case '*':
 808       if (atomcount == 0)
 809       {
 810         error_msg = "Cannot append '+' to nothing";
 811         goto error;
 812       }
 813       nfa_add_star_op (&ctx);
 814       break;
 815     case '+':
 816       if (atomcount == 0)
 817       {
 818         error_msg = "Cannot append '+' to nothing";
 819         goto error;
 820       }
 821       nfa_add_plus_op (&ctx);
 822       break;
 823     case 92:                   /* escape: \ */
 824       regex++;
 825       count++;
 826     default:
 827       if (atomcount > 1)
 828       {
 829         --atomcount;
 830         nfa_add_concatenation (&ctx);
 831       }
 832       nfa_add_literal (&ctx, *regex);
 833       atomcount++;
 834       break;
 835     }
 836   }
 837   if (0 != pcount)
 838   {
 839     error_msg = "Unbalanced parenthesis";
 840     goto error;
 841   }
 842   while (--atomcount > 0)
 843     nfa_add_concatenation (&ctx);
 844   for (; altcount > 0; altcount--)
 845     nfa_add_alternation (&ctx);
 846
 847   if (NULL != p)
 848     GNUNET_free (p);
 849
 850   nfa = stack_pop (ctx.stack, sizeof (struct GNUNET_REGEX_Automaton));
 851
 852   if (!stack_empty (ctx.stack))
 853   {
 854     error_msg = "Creating the NFA failed. NFA stack was not empty!";
 855     goto error;
 856   }
 857
 858   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 859               "Created NFA with %i States and a total of %i Transitions\n",
 860               GNUNET_CONTAINER_slist_count (nfa->states), ctx.transition_id);
 861
 862   GNUNET_REGEX_context_destroy (&ctx);
 863
 864   return nfa;
 865
 866 error:
 867   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
 868   if (NULL != error_msg)
 869     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
 870   GNUNET_free (p);
 871   while (!stack_empty (ctx.stack))
 872     GNUNET_REGEX_automaton_destroy (stack_pop (ctx.stack,
 873                                                sizeof (struct GNUNET_REGEX_Automaton)));
 874   GNUNET_REGEX_context_destroy (&ctx);
 875   return NULL;
 876 }
 877
 878 /**
 879  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
 880  * data structure.
 881  *
 882  * @param a automaton to be destroyed
 883  */
 884 void
 885 GNUNET_REGEX_automaton_destroy(struct GNUNET_REGEX_Automaton *a)
 886 {
 887   struct GNUNET_CONTAINER_SList_Iterator it;
 888
 889   if (NULL == a)
 890     return;
 891
 892   for (it = GNUNET_CONTAINER_slist_begin (a->states);
 893        GNUNET_YES != GNUNET_CONTAINER_slist_end (&it);
 894        GNUNET_CONTAINER_slist_next (&it))
 895   {
 896     automaton_destroy_state (GNUNET_CONTAINER_slist_get (&it, NULL));
 897   }
 898   GNUNET_CONTAINER_slist_iter_destroy (&it);
 899   GNUNET_CONTAINER_slist_destroy (a->states);
 900   GNUNET_free (a);
 901 }
 902
 903 /**
 904  * Construct DFA for the given 'regex' of lenght 'len'
 905  *
 906  * @param regex regular expression string
 907  * @param len length of the regular expression
 908  *
 909  * @return DFA. Needs to be freed using GNUNET_REGEX_destroy_automaton
 910  */
 911 struct GNUNET_REGEX_Automaton *
 912 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
 913 {
 914   struct GNUNET_REGEX_Context ctx;
 915   struct GNUNET_REGEX_Automaton *dfa;
 916   struct GNUNET_REGEX_Automaton *nfa;
 917   struct GNUNET_CONTAINER_SList *tmp;
 918   struct GNUNET_CONTAINER_SList *nfa_set;
 919   struct GNUNET_CONTAINER_SList *sset;
 920   struct GNUNET_CONTAINER_SList *dfa_stack;
 921   struct GNUNET_CONTAINER_SList_Iterator tranit;
 922   struct Transition *currenttransition;
 923   struct State *dfa_state;
 924   struct State *new_dfa_state;
 925   struct State *state_contains;
 926
 927   GNUNET_REGEX_context_init (&ctx);
 928
 929   // Create NFA
 930   nfa = GNUNET_REGEX_construct_nfa (regex, len);
 931
 932   dfa_stack = GNUNET_CONTAINER_slist_create ();
 933
 934   // Initialize new dfa
 935   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 936   dfa->states = GNUNET_CONTAINER_slist_create ();
 937
 938   // Create DFA start state from epsilon closure
 939   sset = GNUNET_CONTAINER_slist_create ();
 940   GNUNET_CONTAINER_slist_add (sset, GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 941                               nfa->start, sizeof *(nfa->start));
 942   nfa_set = create_nfa_closure (sset, 0);
 943   GNUNET_CONTAINER_slist_destroy (sset);
 944   dfa->start = dfa_create_state (&ctx, nfa_set);
 945   GNUNET_CONTAINER_slist_add (dfa->states,
 946                               GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 947                               dfa->start, sizeof *(dfa->start));
 948   stack_push (dfa_stack, dfa->start, sizeof *(dfa->start));
 949
 950   while (!stack_empty (dfa_stack))
 951   {
 952     dfa_state = stack_pop (dfa_stack, sizeof (struct State));
 953
 954     for (tranit = GNUNET_CONTAINER_slist_begin (dfa_state->transitions);
 955          GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
 956          GNUNET_CONTAINER_slist_next (&tranit))
 957     {
 958       currenttransition = GNUNET_CONTAINER_slist_get (&tranit, NULL);
 959
 960       if (0 != currenttransition->literal && NULL == currenttransition->state)
 961       {
 962         tmp = create_nfa_closure (dfa_state->nfa_set,
 963                                   currenttransition->literal);
 964         nfa_set = create_nfa_closure (tmp, 0);
 965         new_dfa_state = dfa_create_state (&ctx, nfa_set);
 966         GNUNET_CONTAINER_slist_destroy (tmp);
 967
 968         state_contains =
 969             GNUNET_CONTAINER_slist_contains2 (dfa->states, new_dfa_state,
 970                                               sizeof *new_dfa_state,
 971                                               &set_compare);
 972         if (NULL == state_contains)
 973         {
 974           GNUNET_CONTAINER_slist_add_end (dfa->states,
 975                                           GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC,
 976                                           new_dfa_state, sizeof *new_dfa_state);
 977           stack_push (dfa_stack, new_dfa_state, sizeof *new_dfa_state);
 978           currenttransition->state = new_dfa_state;
 979         }
 980         else
 981           currenttransition->state = state_contains;
 982       }
 983     }
 984
 985     GNUNET_CONTAINER_slist_iter_destroy (&tranit);
 986   }
 987   GNUNET_CONTAINER_slist_destroy (dfa_stack);
 988   GNUNET_REGEX_automaton_destroy (nfa);
 989   GNUNET_REGEX_context_destroy (&ctx);
 990   dfa_clear_nfa_set (dfa->states);
 991
 992   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n",
 993               GNUNET_CONTAINER_slist_count (dfa->states));
 994
 995   return dfa;
 996 }
 997
 998 /**
 999  * Save the given automaton as a GraphViz dot file
1000  *
1001  * @param a the automaton to be saved
1002  * @param filename where to save the file
1003  */
1004 void
1005 GNUNET_REGEX_automaton_save_graph(struct GNUNET_REGEX_Automaton *a,
1006                                   const char *filename)
1007 {
1008   struct GNUNET_CONTAINER_SList_Iterator stateit;
1009   struct GNUNET_CONTAINER_SList_Iterator tranit;
1010   struct State *s;
1011   struct Transition *ctran;
1012   char *s_acc = NULL;
1013   char *s_tran = NULL;
1014   char *start;
1015   char *end;
1016   FILE *p;
1017
1018   if (NULL == a)
1019   {
1020     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1021     return;
1022   }
1023
1024   if (NULL == filename || strlen (filename) < 1)
1025   {
1026     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1027     return;
1028   }
1029
1030   p = fopen (filename, "w");
1031
1032   if (p == NULL)
1033   {
1034     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1035                 filename);
1036     return;
1037   }
1038
1039   start = "digraph G {\nrankdir=LR\n";
1040   fwrite (start, strlen (start), 1, p);
1041
1042   for (stateit = GNUNET_CONTAINER_slist_begin (a->states);
1043        GNUNET_YES != GNUNET_CONTAINER_slist_end (&stateit);
1044        GNUNET_CONTAINER_slist_next (&stateit))
1045   {
1046
1047     s = GNUNET_CONTAINER_slist_get (&stateit, NULL);
1048
1049     if (s->accepting)
1050     {
1051       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1052       fwrite (s_acc, strlen (s_acc), 1, p);
1053       GNUNET_free (s_acc);
1054     }
1055
1056     s->marked = 1;
1057
1058     for (tranit = GNUNET_CONTAINER_slist_begin (s->transitions);
1059          GNUNET_YES != GNUNET_CONTAINER_slist_end (&tranit);
1060          GNUNET_CONTAINER_slist_next (&tranit))
1061     {
1062       ctran = GNUNET_CONTAINER_slist_get (&tranit, NULL);
1063
1064       if (NULL == ctran->state)
1065       {
1066         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1067                     "Transition from State %i has has no state for transitioning\n",
1068                     s->id);
1069         continue;
1070       }
1071
1072       if (ctran->literal == 0)
1073       {
1074         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1075                          s->name, ctran->state->name);
1076       }
1077       else
1078       {
1079         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1080                          s->name, ctran->state->name, ctran->literal);
1081       }
1082
1083       fwrite (s_tran, strlen (s_tran), 1, p);
1084       GNUNET_free (s_tran);
1085     }
1086     GNUNET_CONTAINER_slist_iter_destroy (&tranit);
1087   }
1088   GNUNET_CONTAINER_slist_iter_destroy (&stateit);
1089
1090   end = "\n}\n";
1091   fwrite (end, strlen (end), 1, p);
1092   fclose (p);
1093 }