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_regex_lib.h"
  27 #include "regex.h"
  28
  29 struct Stack
  30 {
  31   void *data;
  32   struct Stack *next;
  33 };
  34
  35 static struct Stack *nfa_stack = NULL;
  36
  37 void
  38 push (void *val, struct Stack **stack)
  39 {
  40   struct Stack *new = GNUNET_malloc (sizeof (struct Stack *));
  41
  42   if (NULL == new)
  43   {
  44     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not push to stack\n");
  45     return;
  46   }
  47   new->data = val;
  48   new->next = *stack;
  49   *stack = new;
  50 }
  51
  52 int
  53 empty (struct Stack **stack)
  54 {
  55   return (NULL == *stack || NULL == stack);
  56 }
  57
  58 void *
  59 pop (struct Stack **stack)
  60 {
  61   struct Stack *top;
  62   void *val;
  63
  64   if (empty (stack))
  65     return NULL;
  66
  67   top = *stack;
  68   val = top->data;
  69   *stack = top->next;
  70   GNUNET_free (top);
  71   return val;
  72 }
  73
  74 void *
  75 top (struct Stack **stack)
  76 {
  77   if (empty (stack))
  78     return NULL;
  79
  80   return (*stack)->data;
  81 }
  82
  83 struct State
  84 {
  85   unsigned int id;
  86   int accepting;
  87   unsigned int tcnt;
  88   struct Transition *transitions;
  89   int marked;
  90   char *name;
  91 };
  92
  93 struct StateSet
  94 {
  95   struct State **states;
  96   unsigned int count;
  97 };
  98
  99 struct GNUNET_REGEX_Automaton
 100 {
 101   struct State *start;
 102   struct State *end;
 103
 104   struct StateSet sset;
 105 };
 106
 107 struct Transition
 108 {
 109   unsigned int id;
 110   char literal;
 111   struct State *state;
 112 };
 113
 114 struct GNUNET_REGEX_Context
 115 {
 116   unsigned int state_id;
 117   unsigned int transition_id;
 118 };
 119
 120 struct State *
 121 dfa_create_state (struct GNUNET_REGEX_Context *ctx, struct StateSet *sset, int accepting)
 122 {
 123   int i;
 124   struct State *s;
 125   char *name;
 126
 127   s = GNUNET_malloc (sizeof (struct State));
 128   s->id = ctx->state_id++;
 129   s->accepting = accepting;
 130   s->tcnt = 0;
 131   s->transitions = NULL;
 132   s->marked = 0;
 133   s->name = NULL;
 134
 135   if (0 == sset->count)
 136     return s;
 137
 138   s->name = GNUNET_malloc ( strlen ("{"));
 139   strcat (s->name, "{");
 140
 141   for (i=0; i<sset->count; i++)
 142   {
 143     name = GNUNET_malloc (sizeof (char));
 144     GNUNET_asprintf (&name, "%i,", sset->states[i]->id);
 145     s->name = GNUNET_realloc (s->name, strlen (s->name) + strlen (name) + 1);
 146     strcat (s->name, name);
 147     GNUNET_free (name);
 148   }
 149   s->name[strlen (s->name)-1] = '}';
 150
 151   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA state with name: %s\n", s->name);
 152
 153   return s;
 154 }
 155
 156 struct GNUNET_REGEX_Automaton *
 157 nfa_create (struct State *start, struct State *end)
 158 {
 159   struct GNUNET_REGEX_Automaton *n;
 160   struct StateSet sset;
 161
 162   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
 163
 164   if (NULL == start && NULL == end)
 165   {
 166     sset.states = NULL;
 167     sset.count = 0;
 168     n->sset = sset;
 169     n->start = NULL;
 170     n->end = NULL;
 171
 172     return n;
 173   }
 174
 175   sset.states = GNUNET_malloc ((sizeof (struct State *)) * 2);
 176   sset.states[0] = start;
 177   sset.states[1] = end;
 178   sset.count = 2;
 179   n->sset = sset;
 180
 181   n->start = start;
 182   n->end = end;
 183
 184   return n;
 185 }
 186
 187
 188 void
 189 nfa_add_states (struct GNUNET_REGEX_Automaton *n, struct StateSet *sset)
 190 {
 191   unsigned int i;
 192   unsigned int j;
 193
 194   i = n->sset.count;
 195   GNUNET_array_grow (n->sset.states, n->sset.count, n->sset.count + sset->count);
 196   for (j = 0; i < n->sset.count && j < sset->count; i++, j++)
 197   {
 198     n->sset.states[i] = sset->states[j];
 199   }
 200 }
 201
 202
 203 struct State *
 204 nfa_create_state (struct GNUNET_REGEX_Context *ctx, int accepting)
 205 {
 206   struct State *s;
 207
 208   s = GNUNET_malloc (sizeof (struct State));
 209   s->id = ctx->state_id++;
 210   s->accepting = accepting;
 211   s->tcnt = 0;
 212   s->transitions = NULL;
 213   s->marked = 0;
 214   s->name = NULL;
 215   GNUNET_asprintf (&s->name, "s%i", s->id);
 216
 217   return s;
 218 }
 219
 220 void
 221 automaton_destroy_state (struct State *s)
 222 {
 223   if (s->tcnt > 0)
 224     GNUNET_free (s->transitions);
 225   if (NULL != s->name)
 226     GNUNET_free (s->name);
 227   GNUNET_free (s);
 228 }
 229
 230 void
 231 nfa_add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state, const char literal,
 232                     struct State *to_state)
 233 {
 234   struct Transition t;
 235
 236   if (NULL == from_state || NULL == to_state)
 237   {
 238     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 239     return;
 240   }
 241
 242   t.id = ctx->transition_id++;
 243   t.literal = literal;
 244   t.state = to_state;
 245
 246   if (0 == from_state->tcnt)
 247     from_state->transitions = NULL;
 248
 249   GNUNET_array_append (from_state->transitions, from_state->tcnt, t);
 250 }
 251
 252 void
 253 mark_all_states (struct GNUNET_REGEX_Automaton *n, int marked)
 254 {
 255   int i;
 256
 257   for (i = 0; i < n->sset.count; i++)
 258   {
 259     n->sset.states[i]->marked = marked;
 260   }
 261 }
 262
 263 void
 264 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
 265 {
 266   struct GNUNET_REGEX_Automaton *A;
 267   struct GNUNET_REGEX_Automaton *B;
 268   struct GNUNET_REGEX_Automaton *new;
 269
 270   B = pop (&nfa_stack);
 271   A = pop (&nfa_stack);
 272
 273   if (NULL == A || NULL == B)
 274   {
 275     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 276                 "nfa_add_concatenationenation failed, because there were not enough elements on the stack");
 277     return;
 278   }
 279
 280   nfa_add_transition (ctx, A->end, 0, B->start);
 281   A->end->accepting = 0;
 282   B->end->accepting = 1;
 283
 284   new = nfa_create (NULL, NULL);
 285   nfa_add_states (new, &A->sset);
 286   nfa_add_states (new, &B->sset);
 287   new->start = A->start;
 288   new->end = B->end;
 289   GNUNET_free (A);
 290   GNUNET_free (B);
 291
 292   push (new, &nfa_stack);
 293 }
 294
 295 void
 296 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
 297 {
 298   struct GNUNET_REGEX_Automaton *A;
 299   struct GNUNET_REGEX_Automaton *new;
 300   struct State *start;
 301   struct State *end;
 302
 303   A = pop (&nfa_stack);
 304
 305   if (NULL == A)
 306   {
 307     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 308                 "nfa_add_star_op failed, because there was no element on the stack");
 309     return;
 310   }
 311
 312   start = nfa_create_state (ctx, 0);
 313   end = nfa_create_state (ctx, 1);
 314
 315   nfa_add_transition (ctx, start, 0, A->start);
 316   nfa_add_transition (ctx, start, 0, end);
 317   nfa_add_transition (ctx, A->end, 0, A->start);
 318   nfa_add_transition (ctx, A->end, 0, end);
 319
 320   A->end->accepting = 0;
 321   end->accepting = 1;
 322
 323   new = nfa_create (start, end);
 324   nfa_add_states (new, &A->sset);
 325   GNUNET_free (A);
 326
 327   push (new, &nfa_stack);
 328 }
 329
 330 void
 331 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
 332 {
 333   struct GNUNET_REGEX_Automaton *A;
 334
 335   A = pop (&nfa_stack);
 336
 337   if (NULL == A)
 338   {
 339     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 340                 "nfa_add_plus_op failed, because there was no element on the stack");
 341     return;
 342   }
 343
 344   nfa_add_transition (ctx, A->end, 0, A->start);
 345
 346   push (A, &nfa_stack);
 347 }
 348
 349 void
 350 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
 351 {
 352   struct GNUNET_REGEX_Automaton *A;
 353   struct GNUNET_REGEX_Automaton *B;
 354   struct GNUNET_REGEX_Automaton *new;
 355   struct State *start;
 356   struct State *end;
 357
 358   B = pop (&nfa_stack);
 359   A = pop (&nfa_stack);
 360
 361   if (NULL == A || NULL == B)
 362   {
 363     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 364                 "alternation failed, because there were not enough elements on the stack");
 365     return;
 366   }
 367
 368   start = nfa_create_state (ctx, 0);
 369   end = nfa_create_state (ctx, 1);
 370   nfa_add_transition (ctx, start, 0, A->start);
 371   nfa_add_transition (ctx, start, 0, B->start);
 372
 373   nfa_add_transition (ctx, A->end, 0, end);
 374   nfa_add_transition (ctx, B->end, 0, end);
 375
 376   A->end->accepting = 0;
 377   B->end->accepting = 0;
 378   end->accepting = 1;
 379
 380   new = nfa_create (start, end);
 381   nfa_add_states (new, &A->sset);
 382   nfa_add_states (new, &B->sset);
 383   GNUNET_free (A);
 384   GNUNET_free (B);
 385
 386   push (new, &nfa_stack);
 387 }
 388
 389 void
 390 nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
 391 {
 392   struct GNUNET_REGEX_Automaton *n;
 393   struct State *start;
 394   struct State *end;
 395
 396   start = nfa_create_state (ctx, 0);
 397   end = nfa_create_state (ctx, 1);
 398   nfa_add_transition (ctx, start, lit, end);
 399   n = nfa_create (start, end);
 400   push (n, &nfa_stack);
 401 }
 402
 403 /**
 404  * Calculates the closure set for the given set of states.
 405  *
 406  * @param states set of states for which to calculate the closure
 407  * @param count number of states in 'states'
 408  * @param literal for the transition
 409  *
 410  * @return set of states that can be reached from the given 'states' when
 411  *         using only 'literal' transitions
 412  */
 413 struct StateSet
 414 nfa_closure (struct State **states, unsigned int count, const char literal)
 415 {
 416   struct Stack *cls_check;
 417   unsigned int scnt;
 418   unsigned int tcnt;
 419   struct StateSet cls;
 420   struct State *s;
 421   struct State *currentstate;
 422   struct State *clsstate;
 423
 424
 425   for (scnt=0; scnt < count; scnt++)
 426   {
 427     s = states[scnt];
 428     cls_check = NULL;
 429     cls.states = NULL;
 430     cls.count = 0;
 431
 432     // Add start state to closure
 433     GNUNET_array_append (cls.states, cls.count, s);
 434     push (s, &cls_check);
 435
 436     while (!empty(&cls_check))
 437     {
 438       currentstate = pop(&cls_check);
 439
 440       for (tcnt=0; tcnt<currentstate->tcnt; tcnt++)
 441       {
 442         if (NULL != currentstate->transitions[tcnt].state
 443             && literal == currentstate->transitions[tcnt].literal)
 444         {
 445           clsstate = currentstate->transitions[tcnt].state;
 446
 447           if (NULL == clsstate)
 448             break;
 449
 450           GNUNET_array_append (cls.states, cls.count, clsstate);
 451           push (clsstate, &cls_check);
 452         }
 453       }
 454     }
 455   }
 456
 457   return cls;
 458 }
 459
 460 struct GNUNET_REGEX_Automaton *
 461 GNUNET_REGEX_construct_nfa (const char *regex, size_t len)
 462 {
 463   struct GNUNET_REGEX_Context ctx;
 464   struct GNUNET_REGEX_Automaton *nfa;
 465   char *error_msg;
 466   unsigned int count;
 467   unsigned int altcount;
 468   unsigned int atomcount;
 469   unsigned int pcount;
 470   struct
 471   {
 472     int altcount;
 473     int atomcount;
 474   }*p;
 475
 476   p = NULL;
 477   error_msg = NULL;
 478   altcount = 0;
 479   atomcount = 0;
 480   pcount = 0;
 481   ctx.state_id = 0;
 482   ctx.transition_id = 0;
 483
 484   for (count = 0; count < len && *regex; count++, regex++)
 485   {
 486     switch (*regex)
 487     {
 488     case '(':
 489       if (atomcount > 1)
 490       {
 491         --atomcount;
 492         nfa_add_concatenation (&ctx);
 493       }
 494       GNUNET_array_grow (p, pcount, pcount + 1);
 495       p[pcount - 1].altcount = altcount;
 496       p[pcount - 1].atomcount = atomcount;
 497       altcount = 0;
 498       atomcount = 0;
 499       break;
 500     case '|':
 501       if (0 == atomcount)
 502       {
 503         error_msg = "Cannot append '|' to nothing";
 504         goto error;
 505       }
 506       while (--atomcount > 0)
 507         nfa_add_concatenation (&ctx);
 508       altcount++;
 509       break;
 510     case ')':
 511       if (0 == pcount)
 512       {
 513         error_msg = "Missing opening '('";
 514         goto error;
 515       }
 516       if (0 == atomcount)
 517       {
 518         // Ignore this: "()"
 519         pcount--;
 520         altcount = p[pcount].altcount;
 521         atomcount = p[pcount].atomcount;
 522         break;
 523       }
 524       while (--atomcount > 0)
 525         nfa_add_concatenation (&ctx);
 526       for (; altcount > 0; altcount--)
 527         nfa_add_alternation (&ctx);
 528       pcount--;
 529       altcount = p[pcount].altcount;
 530       atomcount = p[pcount].atomcount;
 531       atomcount++;
 532       break;
 533     case '*':
 534       if (atomcount == 0)
 535       {
 536         error_msg = "Cannot append '+' to nothing";
 537         goto error;
 538       }
 539       nfa_add_star_op (&ctx);
 540       break;
 541     case '+':
 542       if (atomcount == 0)
 543       {
 544         error_msg = "Cannot append '+' to nothing";
 545         goto error;
 546       }
 547       nfa_add_plus_op (&ctx);
 548       break;
 549     case 92:                   /* escape: \ */
 550       regex++;
 551       count++;
 552     default:
 553       if (atomcount > 1)
 554       {
 555         --atomcount;
 556         nfa_add_concatenation (&ctx);
 557       }
 558       nfa_add_literal (&ctx, *regex);
 559       atomcount++;
 560       break;
 561     }
 562   }
 563   if (0 != pcount)
 564   {
 565     error_msg = "Unbalanced parenthesis";
 566     goto error;
 567   }
 568   while (--atomcount > 0)
 569     nfa_add_concatenation (&ctx);
 570   for (; altcount > 0; altcount--)
 571     nfa_add_alternation (&ctx);
 572
 573   if (NULL != p)
 574     GNUNET_free (p);
 575
 576   nfa = pop (&nfa_stack);
 577
 578   if (!empty (&nfa_stack))
 579   {
 580     error_msg = "Creating the NFA failed. NFA stack was not empty!";
 581     goto error;
 582   }
 583
 584   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 585               "Created NFA with %i States and a total of %i Transitions\n",
 586               ctx.state_id, ctx.transition_id);
 587
 588   return nfa;
 589
 590 error:
 591   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
 592   if (NULL != error_msg)
 593     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
 594   GNUNET_free (p);
 595   while (!empty (&nfa_stack))
 596     GNUNET_REGEX_destroy_automaton (pop (&nfa_stack));
 597   return NULL;
 598 }
 599
 600 void
 601 GNUNET_REGEX_destroy_automaton (struct GNUNET_REGEX_Automaton *a)
 602 {
 603   int i;
 604
 605   if (NULL == a)
 606     return;
 607
 608   for (i = 0; i < a->sset.count; i++)
 609   {
 610     automaton_destroy_state (a->sset.states[i]);
 611   }
 612
 613   if (NULL != a->sset.states)
 614     GNUNET_free (a->sset.states);
 615   GNUNET_free (a);
 616 }
 617
 618 void
 619 GNUNET_REGEX_save_nfa_graph (struct GNUNET_REGEX_Automaton *n, const char *filename)
 620 {
 621   struct State *s;
 622   char *start;
 623   char *end;
 624   FILE *p;
 625   int scnt;
 626   int tcnt;
 627
 628   if (NULL == n)
 629   {
 630     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 631     return;
 632   }
 633
 634   if (NULL == filename || strlen (filename) < 1)
 635   {
 636     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 637     return;
 638   }
 639
 640   p = fopen (filename, "w");
 641
 642   if (p == NULL)
 643   {
 644     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 645                 filename);
 646     return;
 647   }
 648
 649   start = "digraph G {\nrankdir=LR\n";
 650   fwrite (start, strlen (start), 1, p);
 651
 652   for (scnt = 0; scnt < n->sset.count; scnt++)
 653   {
 654     struct Transition *ctran;
 655     char *s_acc = NULL;
 656     char *s_tran = NULL;
 657
 658     s = n->sset.states[scnt];
 659
 660     if (s->accepting)
 661     {
 662       GNUNET_asprintf (&s_acc, "s%i [shape=doublecircle];\n", s->id);
 663       fwrite (s_acc, strlen (s_acc), 1, p);
 664       GNUNET_free (s_acc);
 665     }
 666
 667     ctran = s->transitions;
 668     s->marked = 1;
 669
 670     for (tcnt = 0; tcnt < s->tcnt && NULL != ctran; tcnt++)
 671     {
 672       if (NULL == ctran->state)
 673       {
 674         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 675                     "Transition from State %i has has no state for transitioning\n",
 676                     s->id);
 677       }
 678
 679       if (ctran->literal == 0)
 680       {
 681         GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"epsilon\"];\n", s->id,
 682                          ctran->state->id);
 683       }
 684       else
 685       {
 686         GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"%c\"];\n", s->id,
 687                          ctran->state->id, ctran->literal);
 688       }
 689
 690       fwrite (s_tran, strlen (s_tran), 1, p);
 691
 692       ctran++;
 693     }
 694   }
 695
 696   end = "\n}\n";
 697   fwrite (end, strlen (end), 1, p);
 698   fclose (p);
 699 }
 700
 701 struct GNUNET_REGEX_Automaton *
 702 GNUNET_REGEX_construct_dfa (const char *regex, size_t len)
 703 {
 704   struct GNUNET_REGEX_Context ctx;
 705   struct GNUNET_REGEX_Automaton *dfa;
 706   struct GNUNET_REGEX_Automaton *nfa;
 707   struct StateSet dfa_start_set;
 708   struct State *dfa_start;
 709
 710   ctx.state_id = 0;
 711   ctx.transition_id = 0;
 712
 713   // Create NFA
 714   nfa = GNUNET_REGEX_construct_nfa (regex, len);
 715
 716   // Create DFA start state from epsilon closure
 717   dfa_start_set = nfa_closure (&nfa->start, 1, 0);
 718   dfa_start = dfa_create_state (&ctx, &dfa_start_set, 0);
 719
 720   // ecls (move (dfa_start, lit))
 721
 722   return dfa;
 723 }