src/regex/regex.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file src/regex/regex.c
  22  * @brief library to create automatons from regular expressions
  23  * @author Maximilian Szengel
  24  */
  25 #include "platform.h"
  26 #include "gnunet_container_lib.h"
  27 #include "gnunet_regex_lib.h"
  28 #include "regex.h"
  29
  30 /**
  31  * Context that contains an id counter for states and transitions
  32  * as well as a DLL of automatons used as a stack for NFA construction.
  33  */
  34 struct GNUNET_REGEX_Context
  35 {
  36   unsigned int state_id;
  37   unsigned int transition_id;
  38
  39   /**
  40    * DLL of GNUNET_REGEX_Automaton's used as a stack
  41    */
  42   struct GNUNET_REGEX_Automaton *stack_head;
  43   struct GNUNET_REGEX_Automaton *stack_tail;
  44 };
  45
  46 enum GNUNET_REGEX_automaton_type
  47 {
  48   NFA,
  49   DFA
  50 };
  51
  52 /**
  53  * Automaton representation
  54  */
  55 struct GNUNET_REGEX_Automaton
  56 {
  57   struct GNUNET_REGEX_Automaton *prev;
  58   struct GNUNET_REGEX_Automaton *next;
  59
  60   struct State *start;
  61   struct State *end;
  62
  63   unsigned int state_count;
  64   struct State *states_head;
  65   struct State *states_tail;
  66
  67   enum GNUNET_REGEX_automaton_type type;
  68 };
  69
  70 /**
  71  * A state. Can be used in DFA and NFA automatons.
  72  */
  73 struct State
  74 {
  75   struct State *prev;
  76   struct State *next;
  77
  78   unsigned int id;
  79   int accepting;
  80   int marked;
  81   char *name;
  82
  83   unsigned int transition_count;
  84   struct Transition *transitions_head;
  85   struct Transition *transitions_tail;
  86
  87   struct StateSet *nfa_set;
  88 };
  89
  90 /**
  91  * Transition between two states. Each state can have 0-n transitions.
  92  * If literal is 0, this is considered to be an epsilon transition.
  93  */
  94 struct Transition
  95 {
  96   struct Transition *prev;
  97   struct Transition *next;
  98
  99   unsigned int id;
 100   char literal;
 101   struct State *state;
 102 };
 103
 104 /**
 105  * Set of states
 106  */
 107 struct StateSet
 108 {
 109   /**
 110    * Array of states
 111    */
 112   struct State **states;
 113   unsigned int len;
 114 };
 115
 116 /**
 117  * Initialize a new context
 118  *
 119  * @param ctx context
 120  */
 121 static void
 122 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
 123 {
 124   if (NULL == ctx)
 125   {
 126     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
 127     return;
 128   }
 129   ctx->state_id = 0;
 130   ctx->transition_id = 0;
 131   ctx->stack_head = NULL;
 132   ctx->stack_tail = NULL;
 133 }
 134
 135 static void
 136 debug_print_state (struct State *s)
 137 {
 138   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 139               "State %i: %s marked: %i accepting: %i\n", s->id, s->name,
 140               s->marked, s->accepting);
 141 }
 142
 143 static void
 144 debug_print_states (struct StateSet *sset)
 145 {
 146   struct State *s;
 147   int i;
 148
 149   for (i = 0; i < sset->len; i++)
 150   {
 151     s = sset->states[i];
 152     debug_print_state (s);
 153   }
 154 }
 155
 156 static void
 157 debug_print_transitions (struct State *s)
 158 {
 159   struct Transition *t;
 160   char *state;
 161   char literal;
 162
 163   for (t = s->transitions_head; NULL != t; t = t->next)
 164   {
 165     if (0 == t->literal)
 166       literal = '0';
 167     else
 168       literal = t->literal;
 169
 170     if (NULL == t->state)
 171       state = "NULL";
 172     else
 173       state = t->state->name;
 174
 175     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
 176                 literal, state);
 177   }
 178 }
 179
 180 static int
 181 state_compare (const void *a, const void *b)
 182 {
 183   struct State **s1;
 184   struct State **s2;
 185
 186   s1 = (struct State **) a;
 187   s2 = (struct State **) b;
 188
 189   return (*s1)->id - (*s2)->id;
 190 }
 191
 192 /**
 193  * Compare to state sets by comparing the id's of the states that are
 194  * contained in each set. Both sets are expected to be sorted by id!
 195  *
 196  * @param sset1 first state set
 197  * @param sset2 second state set
 198  *
 199  * @return 0 if they are equal, non 0 otherwise
 200  */
 201 static int
 202 state_set_compare (struct StateSet *sset1, struct StateSet *sset2)
 203 {
 204   int i;
 205
 206   if (sset1->len != sset2->len)
 207     return 1;
 208
 209   for (i = 0; i < sset1->len; i++)
 210   {
 211     if (sset1->states[i]->id != sset2->states[i]->id)
 212     {
 213       return 1;
 214     }
 215   }
 216   return 0;
 217 }
 218
 219 /**
 220  * Checks if 'elem' is contained in 'set'
 221  *
 222  * @param set set of states
 223  * @param elem state
 224  *
 225  * @return GNUNET_YES if 'set' contains 'elem, GNUNET_NO otherwise
 226  */
 227 static int
 228 state_set_contains (struct StateSet *set, struct State *elem)
 229 {
 230   struct State *s;
 231   int i;
 232
 233   for (i = 0; i < set->len; i++)
 234   {
 235     s = set->states[i];
 236     if (0 == memcmp (s, elem, sizeof (struct State)))
 237       return GNUNET_YES;
 238   }
 239   return GNUNET_NO;
 240 }
 241
 242 /**
 243  * Clears the given StateSet 'set'
 244  *
 245  * @param set set to be cleared
 246  */
 247 static void
 248 state_set_clear (struct StateSet *set)
 249 {
 250   if (NULL != set)
 251   {
 252     if (NULL != set->states)
 253       GNUNET_free (set->states);
 254     GNUNET_free (set);
 255   }
 256 }
 257
 258 /**
 259  * Adds a transition from one state to another on 'literal'
 260  *
 261  * @param ctx context
 262  * @param from_state starting state for the transition
 263  * @param literal transition label
 264  * @param to_state state to where the transition should point to
 265  */
 266 static void
 267 add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state,
 268                 const char literal, struct State *to_state)
 269 {
 270   struct Transition *t;
 271
 272   if (NULL == from_state)
 273   {
 274     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 275     return;
 276   }
 277
 278   t = GNUNET_malloc (sizeof (struct Transition));
 279
 280   t->id = ctx->transition_id++;
 281   t->literal = literal;
 282   t->state = to_state;
 283
 284   GNUNET_CONTAINER_DLL_insert (from_state->transitions_head,
 285                                from_state->transitions_tail, t);
 286 }
 287
 288 /**
 289  * Clears an automaton fragment. Does not destroy the states inside
 290  * the automaton.
 291  *
 292  * @param a automaton to be cleared
 293  */
 294 static void
 295 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
 296 {
 297   a->start = NULL;
 298   a->end = NULL;
 299   a->states_head = NULL;
 300   a->states_tail = NULL;
 301   a->state_count = 0;
 302   GNUNET_free (a);
 303 }
 304
 305 /**
 306  * Frees the memory used by State 's'
 307  *
 308  * @param s state that should be destroyed
 309  */
 310 static void
 311 automaton_destroy_state (struct State *s)
 312 {
 313   struct Transition *t;
 314   struct Transition *next_t;
 315
 316   if (NULL != s->name)
 317     GNUNET_free (s->name);
 318
 319   for (t = s->transitions_head; NULL != t;)
 320   {
 321     next_t = t->next;
 322     GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
 323     GNUNET_free (t);
 324     t = next_t;
 325   }
 326
 327   state_set_clear (s->nfa_set);
 328
 329   GNUNET_free (s);
 330 }
 331
 332 static void
 333 automaton_remove_state (struct GNUNET_REGEX_Automaton *a, struct State *s)
 334 {
 335   struct State *ss;
 336   ss = s;
 337   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
 338   a->state_count--;
 339   automaton_destroy_state (ss);
 340 }
 341
 342 static void
 343 automaton_add_state (struct GNUNET_REGEX_Automaton *a, struct State *s)
 344 {
 345   GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
 346   a->state_count++;
 347 }
 348
 349 /**
 350  * Creates a new DFA state based on a set of NFA states. Needs to be freed
 351  * using automaton_destroy_state.
 352  *
 353  * @param ctx context
 354  * @param nfa_states set of NFA states on which the DFA should be based on
 355  *
 356  * @return new DFA state
 357  */
 358 static struct State *
 359 dfa_state_create (struct GNUNET_REGEX_Context *ctx, struct StateSet *nfa_states)
 360 {
 361   struct State *s;
 362   char *name;
 363   int len = 0;
 364   struct State *cstate;
 365   struct Transition *ctran;
 366   int insert = 1;
 367   struct Transition *t;
 368   int i;
 369
 370   s = GNUNET_malloc (sizeof (struct State));
 371   s->id = ctx->state_id++;
 372   s->accepting = 0;
 373   s->marked = 0;
 374   s->name = NULL;
 375
 376   if (NULL == nfa_states)
 377   {
 378     GNUNET_asprintf (&s->name, "s%i", s->id);
 379     return s;
 380   }
 381
 382   s->nfa_set = nfa_states;
 383
 384   if (nfa_states->len < 1)
 385     return s;
 386
 387   // Create a name based on 'sset'
 388   s->name = GNUNET_malloc (sizeof (char) * 2);
 389   strcat (s->name, "{");
 390   name = NULL;
 391
 392   for (i = 0; i < nfa_states->len; i++)
 393   {
 394     cstate = nfa_states->states[i];
 395     GNUNET_asprintf (&name, "%i,", cstate->id);
 396
 397     if (NULL != name)
 398     {
 399       len = strlen (s->name) + strlen (name) + 1;
 400       s->name = GNUNET_realloc (s->name, len);
 401       strcat (s->name, name);
 402       GNUNET_free (name);
 403       name = NULL;
 404     }
 405
 406     // Add a transition for each distinct literal to NULL state
 407     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
 408     {
 409       if (0 != ctran->literal)
 410       {
 411         insert = 1;
 412
 413         for (t = s->transitions_head; NULL != t; t = t->next)
 414         {
 415           if (t->literal == ctran->literal)
 416           {
 417             insert = 0;
 418             break;
 419           }
 420         }
 421
 422         if (insert)
 423           add_transition (ctx, s, ctran->literal, NULL);
 424       }
 425     }
 426
 427     // If the nfa_states contain an accepting state, the new dfa state is also accepting
 428     if (cstate->accepting)
 429       s->accepting = 1;
 430   }
 431
 432   s->name[strlen (s->name) - 1] = '}';
 433
 434   return s;
 435 }
 436
 437 /**
 438  * Move from the given state 's' to the next state on
 439  * transition 'literal'
 440  *
 441  * @param s starting state
 442  * @param literal edge label to follow
 443  *
 444  * @return new state or NULL, if transition on literal not possible
 445  */
 446 static struct State *
 447 dfa_move (struct State *s, const char literal)
 448 {
 449   struct Transition *t;
 450   struct State *new_s;
 451
 452   if (NULL == s)
 453     return NULL;
 454
 455   new_s = NULL;
 456
 457   for (t = s->transitions_head; NULL != t; t = t->next)
 458   {
 459     if (literal == t->literal)
 460     {
 461       new_s = t->state;
 462       break;
 463     }
 464   }
 465
 466   return new_s;
 467 }
 468
 469 /**
 470  * Remove all unreachable states from DFA 'a'. Unreachable states
 471  * are those states that are not reachable from the starting state.
 472  *
 473  * @param a DFA automaton
 474  */
 475 static void
 476 dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
 477 {
 478   struct State *stack[a->state_count];
 479   int stack_len;
 480   struct State *s;
 481   struct Transition *t;
 482
 483   stack_len = 0;
 484
 485   // 1. unmark all states
 486   for (s = a->states_head; NULL != s; s = s->next)
 487   {
 488     s->marked = 0;
 489   }
 490
 491   // 2. traverse dfa from start state and mark all visited states
 492   stack[stack_len] = a->start;
 493   stack_len++;
 494   while (stack_len > 0)
 495   {
 496     s = stack[stack_len-1];
 497     stack_len--;
 498     s->marked = 1; // mark s as visited
 499     for (t = s->transitions_head; NULL != t; t = t->next)
 500     {
 501       if (NULL != t->state && 0 == t->state->marked)
 502       {
 503         // add next states to stack
 504         stack[stack_len] = t->state;
 505         stack_len++;
 506       }
 507     }
 508   }
 509
 510   // 3. delete all states that were not visited
 511   for (s = a->states_head; NULL != s; s = s->next)
 512   {
 513     if (0 == s->marked)
 514       automaton_remove_state (a, s);
 515   }
 516 }
 517
 518 /**
 519  * Remove all dead states from the DFA 'a'. Dead states are those
 520  * states that do not transition to any other state but themselfes.
 521  *
 522  * @param a DFA automaton
 523  */
 524 static void
 525 dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
 526 {
 527   struct State *s;
 528   struct State *s_check;
 529   struct Transition *t;
 530   struct Transition *t_check;
 531   int dead;
 532
 533   GNUNET_assert (DFA == a->type);
 534
 535   for (s = a->states_head; NULL != s; s = s->next)
 536   {
 537     if (s->accepting)
 538       continue;
 539
 540     dead = 1;
 541     for (t = s->transitions_head; NULL != t; t = t->next)
 542     {
 543       if (NULL != t->state && t->state != s)
 544       {
 545         dead = 0;
 546         break;
 547       }
 548     }
 549
 550     if (0 == dead)
 551       continue;
 552
 553     // state s is dead, remove it
 554     // 1. remove all transitions to this state
 555     for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 556     {
 557       for (t_check = s_check->transitions_head; NULL != t_check;
 558            t_check = t_check->next)
 559       {
 560         if (t_check->state == s)
 561         {
 562           GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
 563                                        s_check->transitions_tail, t_check);
 564         }
 565       }
 566     }
 567     // 2. remove state
 568     automaton_remove_state (a, s);
 569   }
 570 }
 571
 572 /**
 573  * Merge all non distinguishable states in the DFA 'a'
 574  *
 575  * @param a DFA automaton
 576  */
 577 static void
 578 dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Automaton *a)
 579 {
 580
 581 }
 582
 583 /**
 584  * Minimize the given DFA 'a' by removing all unreachable states,
 585  * removing all dead states and merging all non distinguishable states
 586  *
 587  * @param a DFA automaton
 588  */
 589 static void
 590 dfa_minimize (struct GNUNET_REGEX_Automaton *a)
 591 {
 592   GNUNET_assert (DFA == a->type);
 593
 594   // 1. remove unreachable states
 595   dfa_remove_unreachable_states (a);
 596
 597   // 2. remove dead states
 598   dfa_remove_dead_states (a);
 599
 600   // 3. Merge nondistinguishable states
 601   dfa_merge_nondistinguishable_states (a);
 602 }
 603
 604 /**
 605  * Creates a new NFA fragment. Needs to be cleared using automaton_fragment_clear.
 606  *
 607  * @param start starting state
 608  * @param end end state
 609  *
 610  * @return new NFA fragment
 611  */
 612 static struct GNUNET_REGEX_Automaton *
 613 nfa_fragment_create (struct State *start, struct State *end)
 614 {
 615   struct GNUNET_REGEX_Automaton *n;
 616
 617   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 618
 619   n->type = NFA;
 620   n->start = NULL;
 621   n->end = NULL;
 622
 623   if (NULL == start && NULL == end)
 624     return n;
 625
 626   automaton_add_state (n, end);
 627   automaton_add_state (n, start);
 628
 629   n->start = start;
 630   n->end = end;
 631
 632   return n;
 633 }
 634
 635 /**
 636  * Adds a list of states to the given automaton 'n'.
 637  *
 638  * @param n automaton to which the states should be added
 639  * @param states_head head of the DLL of states
 640  * @param states_tail tail of the DLL of states
 641  */
 642 static void
 643 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct State *states_head,
 644                 struct State *states_tail)
 645 {
 646   struct State *s;
 647
 648   if (NULL == n || NULL == states_head)
 649   {
 650     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
 651     return;
 652   }
 653
 654   if (NULL == n->states_head)
 655   {
 656     n->states_head = states_head;
 657     n->states_tail = states_tail;
 658     return;
 659   }
 660
 661   if (NULL != states_head)
 662   {
 663     n->states_tail->next = states_head;
 664     n->states_tail = states_tail;
 665   }
 666
 667   for (s = states_head; NULL != s; s = s->next)
 668     n->state_count++;
 669 }
 670
 671 /**
 672  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
 673  *
 674  * @param ctx context
 675  * @param accepting is it an accepting state or not
 676  *
 677  * @return new NFA state
 678  */
 679 static struct State *
 680 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
 681 {
 682   struct State *s;
 683
 684   s = GNUNET_malloc (sizeof (struct State));
 685   s->id = ctx->state_id++;
 686   s->accepting = accepting;
 687   s->marked = 0;
 688   s->name = NULL;
 689   GNUNET_asprintf (&s->name, "s%i", s->id);
 690
 691   return s;
 692 }
 693
 694 /**
 695  * Calculates the NFA closure set for the given state
 696  *
 697  * @param s starting point state
 698  * @param literal transitioning literal on which to base the closure on,
 699  *                pass 0 for epsilon transition
 700  *
 701  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 702  */
 703 static struct StateSet *
 704 nfa_closure_create (struct State *s, const char literal)
 705 {
 706   struct StateSet *cls;
 707   struct StateSet *cls_check;
 708   struct State *clsstate;
 709   struct State *currentstate;
 710   struct Transition *ctran;
 711
 712   if (NULL == s)
 713     return NULL;
 714
 715   cls = GNUNET_malloc (sizeof (struct StateSet));
 716   cls_check = GNUNET_malloc (sizeof (struct StateSet));
 717
 718   // Add start state to closure only for epsilon closure
 719   if (0 == literal)
 720     GNUNET_array_append (cls->states, cls->len, s);
 721
 722   GNUNET_array_append (cls_check->states, cls_check->len, s);
 723   while (cls_check->len > 0)
 724   {
 725     currentstate = cls_check->states[cls_check->len - 1];
 726     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
 727
 728     for (ctran = currentstate->transitions_head; NULL != ctran;
 729          ctran = ctran->next)
 730     {
 731       if (NULL != ctran->state && literal == ctran->literal)
 732       {
 733         clsstate = ctran->state;
 734
 735         if (NULL != clsstate &&
 736             GNUNET_YES != state_set_contains (cls, clsstate))
 737         {
 738           GNUNET_array_append (cls->states, cls->len, clsstate);
 739           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
 740         }
 741       }
 742     }
 743   }
 744   GNUNET_assert (0 == cls_check->len);
 745   GNUNET_free (cls_check);
 746
 747   if (cls->len > 1)
 748     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 749
 750   return cls;
 751 }
 752
 753 /**
 754  * Calculates the closure set for the given set of states.
 755  *
 756  * @param states list of states on which to base the closure on
 757  * @param literal transitioning literal for which to base the closure on,
 758  *                pass 0 for epsilon transition
 759  *
 760  * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0)
 761  */
 762 static struct StateSet *
 763 nfa_closure_set_create (struct StateSet *states, const char literal)
 764 {
 765   struct State *s;
 766   struct StateSet *sset;
 767   struct StateSet *cls;
 768   int i;
 769   int j;
 770   int k;
 771   int contains;
 772
 773   if (NULL == states)
 774     return NULL;
 775
 776   cls = GNUNET_malloc (sizeof (struct StateSet));
 777
 778   for (i = 0; i < states->len; i++)
 779   {
 780     s = states->states[i];
 781     sset = nfa_closure_create (s, literal);
 782
 783     for (j = 0; j < sset->len; j++)
 784     {
 785       contains = 0;
 786       for (k = 0; k < cls->len; k++)
 787       {
 788         if (sset->states[j]->id == cls->states[k]->id)
 789         {
 790           contains = 1;
 791           break;
 792         }
 793       }
 794       if (!contains)
 795         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
 796     }
 797     state_set_clear (sset);
 798   }
 799
 800   if (cls->len > 1)
 801     qsort (cls->states, cls->len, sizeof (struct State *), state_compare);
 802
 803   return cls;
 804 }
 805
 806 /**
 807  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
 808  *
 809  * @param ctx context
 810  */
 811 static void
 812 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 813 {
 814   struct GNUNET_REGEX_Automaton *a;
 815   struct GNUNET_REGEX_Automaton *b;
 816   struct GNUNET_REGEX_Automaton *new;
 817
 818   b = ctx->stack_tail;
 819   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 820   a = ctx->stack_tail;
 821   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 822
 823   add_transition (ctx, a->end, 0, b->start);
 824   a->end->accepting = 0;
 825   b->end->accepting = 1;
 826
 827   new = nfa_fragment_create (NULL, NULL);
 828   nfa_add_states (new, a->states_head, a->states_tail);
 829   nfa_add_states (new, b->states_head, b->states_tail);
 830   new->start = a->start;
 831   new->end = b->end;
 832   automaton_fragment_clear (a);
 833   automaton_fragment_clear (b);
 834
 835   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 836 }
 837
 838 /**
 839  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
 840  *
 841  * @param ctx context
 842  */
 843 static void
 844 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 845 {
 846   struct GNUNET_REGEX_Automaton *a;
 847   struct GNUNET_REGEX_Automaton *new;
 848   struct State *start;
 849   struct State *end;
 850
 851   a = ctx->stack_tail;
 852   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 853
 854   if (NULL == a)
 855   {
 856     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 857                 "nfa_add_star_op failed, because there was no element on the stack");
 858     return;
 859   }
 860
 861   start = nfa_state_create (ctx, 0);
 862   end = nfa_state_create (ctx, 1);
 863
 864   add_transition (ctx, start, 0, a->start);
 865   add_transition (ctx, start, 0, end);
 866   add_transition (ctx, a->end, 0, a->start);
 867   add_transition (ctx, a->end, 0, end);
 868
 869   a->end->accepting = 0;
 870   end->accepting = 1;
 871
 872   new = nfa_fragment_create (start, end);
 873   nfa_add_states (new, a->states_head, a->states_tail);
 874   automaton_fragment_clear (a);
 875
 876   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 877 }
 878
 879 /**
 880  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
 881  *
 882  * @param ctx context
 883  */
 884 static void
 885 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 886 {
 887   struct GNUNET_REGEX_Automaton *a;
 888
 889   a = ctx->stack_tail;
 890   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 891
 892   add_transition (ctx, a->end, 0, a->start);
 893
 894   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
 895 }
 896
 897 /**
 898  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment
 899  * that alternates between a and b (a|b)
 900  *
 901  * @param ctx context
 902  */
 903 static void
 904 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 905 {
 906   struct GNUNET_REGEX_Automaton *a;
 907   struct GNUNET_REGEX_Automaton *b;
 908   struct GNUNET_REGEX_Automaton *new;
 909   struct State *start;
 910   struct State *end;
 911
 912   b = ctx->stack_tail;
 913   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
 914   a = ctx->stack_tail;
 915   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 916
 917   start = nfa_state_create (ctx, 0);
 918   end = nfa_state_create (ctx, 1);
 919   add_transition (ctx, start, 0, a->start);
 920   add_transition (ctx, start, 0, b->start);
 921
 922   add_transition (ctx, a->end, 0, end);
 923   add_transition (ctx, b->end, 0, end);
 924
 925   a->end->accepting = 0;
 926   b->end->accepting = 0;
 927   end->accepting = 1;
 928
 929   new = nfa_fragment_create (start, end);
 930   nfa_add_states (new, a->states_head, a->states_tail);
 931   nfa_add_states (new, b->states_head, b->states_tail);
 932   automaton_fragment_clear (a);
 933   automaton_fragment_clear (b);
 934
 935   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
 936 }
 937
 938 /**
 939  * Adds a new nfa fragment to the stack
 940  *
 941  * @param ctx context
 942  * @param lit literal for nfa transition
 943  */
 944 static void
 945 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 946 {
 947   struct GNUNET_REGEX_Automaton *n;
 948   struct State *start;
 949   struct State *end;
 950
 951   GNUNET_assert (NULL != ctx);
 952
 953   start = nfa_state_create (ctx, 0);
 954   end = nfa_state_create (ctx, 1);
 955   add_transition (ctx, start, lit, end);
 956   n = nfa_fragment_create (start, end);
 957   GNUNET_assert (NULL != n);
 958   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
 959 }
 960
 961 /**
 962  * Construct an NFA by parsing the regex string of length 'len'.
 963  *
 964  * @param regex regular expression string
 965  * @param len length of the string
 966  *
 967  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
 968  */
 969 struct GNUNET_REGEX_Automaton *
 970 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
 971 {
 972   struct GNUNET_REGEX_Context ctx;
 973   struct GNUNET_REGEX_Automaton *nfa;
 974   const char *regexp;
 975   char *error_msg;
 976   unsigned int count;
 977   unsigned int altcount;
 978   unsigned int atomcount;
 979   unsigned int pcount;
 980   struct
 981   {
 982     int altcount;
 983     int atomcount;
 984   }     *p;
 985
 986   GNUNET_REGEX_context_init (&ctx);
 987
 988   regexp = regex;
 989   p = NULL;
 990   error_msg = NULL;
 991   altcount = 0;
 992   atomcount = 0;
 993   pcount = 0;
 994
 995   for (count = 0; count < len && *regexp; count++, regexp++)
 996   {
 997     switch (*regexp)
 998     {
 999     case '(':
1000       if (atomcount > 1)
1001       {
1002         --atomcount;
1003         nfa_add_concatenation (&ctx);
1004       }
1005       GNUNET_array_grow (p, pcount, pcount + 1);
1006       p[pcount - 1].altcount = altcount;
1007       p[pcount - 1].atomcount = atomcount;
1008       altcount = 0;
1009       atomcount = 0;
1010       break;
1011     case '|':
1012       if (0 == atomcount)
1013       {
1014         error_msg = "Cannot append '|' to nothing";
1015         goto error;
1016       }
1017       while (--atomcount > 0)
1018         nfa_add_concatenation (&ctx);
1019       altcount++;
1020       break;
1021     case ')':
1022       if (0 == pcount)
1023       {
1024         error_msg = "Missing opening '('";
1025         goto error;
1026       }
1027       if (0 == atomcount)
1028       {
1029         // Ignore this: "()"
1030         pcount--;
1031         altcount = p[pcount].altcount;
1032         atomcount = p[pcount].atomcount;
1033         break;
1034       }
1035       while (--atomcount > 0)
1036         nfa_add_concatenation (&ctx);
1037       for (; altcount > 0; altcount--)
1038         nfa_add_alternation (&ctx);
1039       pcount--;
1040       altcount = p[pcount].altcount;
1041       atomcount = p[pcount].atomcount;
1042       atomcount++;
1043       break;
1044     case '*':
1045       if (atomcount == 0)
1046       {
1047         error_msg = "Cannot append '+' to nothing";
1048         goto error;
1049       }
1050       nfa_add_star_op (&ctx);
1051       break;
1052     case '+':
1053       if (atomcount == 0)
1054       {
1055         error_msg = "Cannot append '+' to nothing";
1056         goto error;
1057       }
1058       nfa_add_plus_op (&ctx);
1059       break;
1060     case 92:                   /* escape: \ */
1061       regexp++;
1062       count++;
1063     default:
1064       if (atomcount > 1)
1065       {
1066         --atomcount;
1067         nfa_add_concatenation (&ctx);
1068       }
1069       nfa_add_literal (&ctx, *regexp);
1070       atomcount++;
1071       break;
1072     }
1073   }
1074   if (0 != pcount)
1075   {
1076     error_msg = "Unbalanced parenthesis";
1077     goto error;
1078   }
1079   while (--atomcount > 0)
1080     nfa_add_concatenation (&ctx);
1081   for (; altcount > 0; altcount--)
1082     nfa_add_alternation (&ctx);
1083
1084   if (NULL != p)
1085     GNUNET_free (p);
1086
1087   nfa = ctx.stack_tail;
1088   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
1089
1090
1091   if (NULL != ctx.stack_head)
1092   {
1093     error_msg = "Creating the NFA failed. NFA stack was not empty!";
1094     goto error;
1095   }
1096
1097   return nfa;
1098
1099 error:
1100   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
1101   if (NULL != error_msg)
1102     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
1103   GNUNET_free (p);
1104   while (NULL != ctx.stack_tail)
1105   {
1106     GNUNET_REGEX_automaton_destroy (ctx.stack_tail);
1107     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail,
1108                                  ctx.stack_tail);
1109   }
1110   return NULL;
1111 }
1112
1113 /**
1114  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton
1115  * data structure.
1116  *
1117  * @param a automaton to be destroyed
1118  */
1119 void
1120 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
1121 {
1122   struct State *s;
1123   struct State *next_state;
1124
1125   if (NULL == a)
1126     return;
1127
1128   for (s = a->states_head; NULL != s;)
1129   {
1130     next_state = s->next;
1131     automaton_destroy_state (s);
1132     s = next_state;
1133   }
1134
1135   GNUNET_free (a);
1136 }
1137
1138 /**
1139  * Construct DFA for the given 'regex' of length 'len'
1140  *
1141  * @param regex regular expression string
1142  * @param len length of the regular expression
1143  *
1144  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
1145  */
1146 struct GNUNET_REGEX_Automaton *
1147 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
1148 {
1149   struct GNUNET_REGEX_Context ctx;
1150   struct GNUNET_REGEX_Automaton *dfa;
1151   struct GNUNET_REGEX_Automaton *nfa;
1152   struct StateSet *tmp;
1153   struct StateSet *nfa_set;
1154   struct StateSet *dfa_stack;
1155   struct Transition *ctran;
1156   struct State *dfa_state;
1157   struct State *new_dfa_state;
1158   struct State *state_contains;
1159   struct State *state_iter;
1160
1161   GNUNET_REGEX_context_init (&ctx);
1162
1163   // Create NFA
1164   nfa = GNUNET_REGEX_construct_nfa (regex, len);
1165
1166   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1167   dfa->type = DFA;
1168
1169   // Create DFA start state from epsilon closure
1170   dfa_stack = GNUNET_malloc (sizeof (struct StateSet));
1171   nfa_set = nfa_closure_create (nfa->start, 0);
1172   dfa->start = dfa_state_create (&ctx, nfa_set);
1173   automaton_add_state (dfa, dfa->start);
1174   GNUNET_array_append (dfa_stack->states, dfa_stack->len, dfa->start);
1175   while (dfa_stack->len > 0)
1176   {
1177     dfa_state = dfa_stack->states[dfa_stack->len - 1];
1178     GNUNET_array_grow (dfa_stack->states, dfa_stack->len, dfa_stack->len - 1);
1179
1180     for (ctran = dfa_state->transitions_head; NULL != ctran;
1181          ctran = ctran->next)
1182     {
1183       if (0 != ctran->literal && NULL == ctran->state)
1184       {
1185         tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal);
1186         nfa_set = nfa_closure_set_create (tmp, 0);
1187         state_set_clear (tmp);
1188         new_dfa_state = dfa_state_create (&ctx, nfa_set);
1189         state_contains = NULL;
1190         for (state_iter = dfa->states_head; NULL != state_iter;
1191              state_iter = state_iter->next)
1192         {
1193           if (0 ==
1194               state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
1195             state_contains = state_iter;
1196         }
1197
1198         if (NULL == state_contains)
1199         {
1200           automaton_add_state (dfa, new_dfa_state);
1201           GNUNET_array_append (dfa_stack->states, dfa_stack->len,
1202                                new_dfa_state);
1203           ctran->state = new_dfa_state;
1204         }
1205         else
1206         {
1207           ctran->state = state_contains;
1208           automaton_destroy_state (new_dfa_state);
1209         }
1210       }
1211     }
1212   }
1213
1214   GNUNET_free (dfa_stack);
1215   GNUNET_REGEX_automaton_destroy (nfa);
1216
1217   dfa_minimize (dfa);
1218
1219   return dfa;
1220 }
1221
1222 /**
1223  * Save the given automaton as a GraphViz dot file
1224  *
1225  * @param a the automaton to be saved
1226  * @param filename where to save the file
1227  */
1228 void
1229 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
1230                                    const char *filename)
1231 {
1232   struct State *s;
1233   struct Transition *ctran;
1234   char *s_acc = NULL;
1235   char *s_tran = NULL;
1236   char *start;
1237   char *end;
1238   FILE *p;
1239
1240   if (NULL == a)
1241   {
1242     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
1243     return;
1244   }
1245
1246   if (NULL == filename || strlen (filename) < 1)
1247   {
1248     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
1249     return;
1250   }
1251
1252   p = fopen (filename, "w");
1253
1254   if (p == NULL)
1255   {
1256     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
1257                 filename);
1258     return;
1259   }
1260
1261   start = "digraph G {\nrankdir=LR\n";
1262   fwrite (start, strlen (start), 1, p);
1263
1264   for (s = a->states_head; NULL != s; s = s->next)
1265   {
1266     if (s->accepting)
1267     {
1268       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", s->name);
1269       fwrite (s_acc, strlen (s_acc), 1, p);
1270       GNUNET_free (s_acc);
1271     }
1272
1273     s->marked = 1;
1274
1275     for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
1276     {
1277       if (NULL == ctran->state)
1278       {
1279         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1280                     "Transition from State %i has has no state for transitioning\n",
1281                     s->id);
1282         continue;
1283       }
1284
1285       if (ctran->literal == 0)
1286       {
1287         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"epsilon\"];\n",
1288                          s->name, ctran->state->name);
1289       }
1290       else
1291       {
1292         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n",
1293                          s->name, ctran->state->name, ctran->literal);
1294       }
1295
1296       fwrite (s_tran, strlen (s_tran), 1, p);
1297       GNUNET_free (s_tran);
1298     }
1299   }
1300
1301   end = "\n}\n";
1302   fwrite (end, strlen (end), 1, p);
1303   fclose (p);
1304 }
1305
1306 /**
1307  * Evaluates the given string using the given DFA automaton
1308  *
1309  * @param a automaton, type must be DFA
1310  * @param string string that should be evaluated
1311  *
1312  * @return 0 if string matches, non 0 otherwise
1313  */
1314 static int
1315 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1316 {
1317   const char *strp;
1318   struct State *s;
1319
1320   if (DFA != a->type)
1321   {
1322     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1323                 "Tried to evaluate DFA, but NFA automaton given");
1324     return -1;
1325   }
1326
1327   s = a->start;
1328
1329   for (strp = string; NULL != strp && *strp; strp++)
1330   {
1331     s = dfa_move (s, *strp);
1332     if (NULL == s)
1333       break;
1334   }
1335
1336   if (NULL != s && s->accepting)
1337     return 0;
1338
1339   return 1;
1340 }
1341
1342 /**
1343  * Evaluates the given string using the given NFA automaton
1344  *
1345  * @param a automaton, type must be NFA
1346  * @param string string that should be evaluated
1347  *
1348  * @return 0 if string matches, non 0 otherwise
1349  */
1350 static int
1351 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
1352 {
1353   const char *strp;
1354   struct State *s;
1355   struct StateSet *sset;
1356   struct StateSet *new_sset;
1357   int i;
1358   int result;
1359
1360   if (NFA != a->type)
1361   {
1362     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1363                 "Tried to evaluate NFA, but DFA automaton given");
1364     return -1;
1365   }
1366
1367   result = 1;
1368   strp = string;
1369   sset = nfa_closure_create (a->start, 0);
1370
1371   for (strp = string; NULL != strp && *strp; strp++)
1372   {
1373     new_sset = nfa_closure_set_create (sset, *strp);
1374     state_set_clear (sset);
1375     sset = nfa_closure_set_create (new_sset, 0);
1376     state_set_clear (new_sset);
1377   }
1378
1379   for (i = 0; i < sset->len; i++)
1380   {
1381     s = sset->states[i];
1382     if (NULL != s && s->accepting)
1383     {
1384       result = 0;
1385       break;
1386     }
1387   }
1388
1389   state_set_clear (sset);
1390   return result;
1391 }
1392
1393
1394 /**
1395  * Evaluates the given 'string' against the given compiled regex
1396  *
1397  * @param a automaton
1398  * @param string string to check
1399  *
1400  * @return 0 if string matches, non 0 otherwise
1401  */
1402 int
1403 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
1404 {
1405   int result;
1406
1407   switch (a->type)
1408   {
1409   case DFA:
1410     result = evaluate_dfa (a, string);
1411     break;
1412   case NFA:
1413     result = evaluate_nfa (a, string);
1414     break;
1415   default:
1416     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1417                 "Evaluating regex failed, automaton has no type!\n");
1418     result = GNUNET_SYSERR;
1419     break;
1420   }
1421
1422   return result;
1423 }