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 GNUNET_REGEX_Nfa
  84 {
  85   struct State *start;
  86   struct State *end;
  87
  88   unsigned int statecnt;
  89   struct State **states;
  90 };
  91
  92 struct State
  93 {
  94   unsigned int id;
  95   int accepting;
  96   unsigned int tcnt;
  97   struct Transition *transitions;
  98   int visited;
  99 };
 100
 101 struct Transition
 102 {
 103   unsigned int id;
 104   char literal;
 105   struct State *state;
 106 };
 107
 108 static unsigned int state_id = 0;
 109 static unsigned int transition_id = 0;
 110
 111 struct GNUNET_REGEX_Nfa *
 112 nfa_create (struct State *start, struct State *end)
 113 {
 114   struct GNUNET_REGEX_Nfa *n;
 115
 116   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Nfa));
 117
 118   if (NULL == start && NULL == end)
 119   {
 120     n->states = NULL;
 121     n->statecnt = 0;
 122     n->start = NULL;
 123     n->end = NULL;
 124
 125     return n;
 126   }
 127
 128   n->states = GNUNET_malloc ((sizeof (struct State *)) * 2);
 129   n->states[0] = start;
 130   n->states[1] = end;
 131   n->statecnt = 2;
 132
 133   n->start = start;
 134   n->end = end;
 135
 136   return n;
 137 }
 138
 139
 140 void
 141 nfa_add_states (struct GNUNET_REGEX_Nfa *n, struct State **states,
 142                 unsigned int count)
 143 {
 144   unsigned int i;
 145   unsigned int j;
 146
 147   i = n->statecnt;
 148   GNUNET_array_grow (n->states, n->statecnt, n->statecnt + count);
 149   for (j = 0; i < n->statecnt && j < count; i++, j++)
 150   {
 151     n->states[i] = states[j];
 152   }
 153 }
 154
 155
 156 struct State *
 157 nfa_create_state (int accepting)
 158 {
 159   struct State *s;
 160
 161   s = GNUNET_malloc (sizeof (struct State));
 162   s->id = state_id++;
 163   s->accepting = accepting;
 164   s->tcnt = 0;
 165   s->transitions = NULL;
 166   s->visited = 0;
 167
 168   return s;
 169 }
 170
 171 void
 172 nfa_destroy_state (struct State *s)
 173 {
 174   if (s->tcnt > 0)
 175     GNUNET_free (s->transitions);
 176   GNUNET_free (s);
 177 }
 178
 179 void
 180 nfa_add_transition (struct State *from_state, const char literal,
 181                     struct State *to_state)
 182 {
 183   struct Transition t;
 184
 185   if (NULL == from_state || NULL == to_state)
 186   {
 187     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 188     return;
 189   }
 190
 191   t.id = transition_id++;
 192   t.literal = literal;
 193   t.state = to_state;
 194
 195   if (0 == from_state->tcnt)
 196     from_state->transitions = NULL;
 197
 198   GNUNET_array_append (from_state->transitions, from_state->tcnt, t);
 199 }
 200
 201 void
 202 mark_all_states (struct GNUNET_REGEX_Nfa *n, int visited)
 203 {
 204   int i;
 205
 206   for (i = 0; i < n->statecnt; i++)
 207   {
 208     n->states[i]->visited = visited;
 209   }
 210 }
 211
 212 void
 213 nfa_add_concatenation ()
 214 {
 215   struct GNUNET_REGEX_Nfa *A;
 216   struct GNUNET_REGEX_Nfa *B;
 217   struct GNUNET_REGEX_Nfa *new;
 218
 219   B = pop (&nfa_stack);
 220   A = pop (&nfa_stack);
 221
 222   if (NULL == A || NULL == B)
 223   {
 224     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 225                 "nfa_add_concatenationenation failed, because there were not enough elements on the stack");
 226     return;
 227   }
 228
 229   nfa_add_transition (A->end, 0, B->start);
 230   A->end->accepting = 0;
 231   B->end->accepting = 1;
 232
 233   new = nfa_create (NULL, NULL);
 234   nfa_add_states (new, A->states, A->statecnt);
 235   nfa_add_states (new, B->states, B->statecnt);
 236   new->start = A->start;
 237   new->end = B->end;
 238   GNUNET_free (A->states);
 239   GNUNET_free (A);
 240   GNUNET_free (B->states);
 241   GNUNET_free (B);
 242
 243   push (new, &nfa_stack);
 244 }
 245
 246 void
 247 nfa_add_star_op ()
 248 {
 249   struct GNUNET_REGEX_Nfa *A;
 250   struct GNUNET_REGEX_Nfa *new;
 251   struct State *start;
 252   struct State *end;
 253
 254   A = pop (&nfa_stack);
 255
 256   if (NULL == A)
 257   {
 258     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 259                 "nfa_add_star_op failed, because there was no element on the stack");
 260     return;
 261   }
 262
 263   start = nfa_create_state (0);
 264   end = nfa_create_state (1);
 265
 266   nfa_add_transition (start, 0, A->start);
 267   nfa_add_transition (start, 0, end);
 268   nfa_add_transition (A->end, 0, A->start);
 269   nfa_add_transition (A->end, 0, end);
 270
 271   A->end->accepting = 0;
 272   end->accepting = 1;
 273
 274   new = nfa_create (start, end);
 275   nfa_add_states (new, A->states, A->statecnt);
 276   GNUNET_free (A->states);
 277   GNUNET_free (A);
 278
 279   push (new, &nfa_stack);
 280 }
 281
 282 void
 283 nfa_add_plus_op ()
 284 {
 285   struct GNUNET_REGEX_Nfa *A;
 286
 287   A = pop (&nfa_stack);
 288
 289   if (NULL == A)
 290   {
 291     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 292                 "nfa_add_plus_op failed, because there was no element on the stack");
 293     return;
 294   }
 295
 296   nfa_add_transition (A->end, 0, A->start);
 297
 298   push (A, &nfa_stack);
 299 }
 300
 301 void
 302 nfa_add_alternation ()
 303 {
 304   struct GNUNET_REGEX_Nfa *A;
 305   struct GNUNET_REGEX_Nfa *B;
 306   struct GNUNET_REGEX_Nfa *new;
 307   struct State *start;
 308   struct State *end;
 309
 310   B = pop (&nfa_stack);
 311   A = pop (&nfa_stack);
 312
 313   if (NULL == A || NULL == B)
 314   {
 315     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 316                 "alternation failed, because there were not enough elements on the stack");
 317     return;
 318   }
 319
 320   start = nfa_create_state (0);
 321   end = nfa_create_state (1);
 322   nfa_add_transition (start, 0, A->start);
 323   nfa_add_transition (start, 0, B->start);
 324
 325   nfa_add_transition (A->end, 0, end);
 326   nfa_add_transition (B->end, 0, end);
 327
 328   A->end->accepting = 0;
 329   B->end->accepting = 0;
 330   end->accepting = 1;
 331
 332   new = nfa_create (start, end);
 333   nfa_add_states (new, A->states, A->statecnt);
 334   nfa_add_states (new, B->states, B->statecnt);
 335   GNUNET_free (A->states);
 336   GNUNET_free (A);
 337   GNUNET_free (B->states);
 338   GNUNET_free (B);
 339
 340   push (new, &nfa_stack);
 341 }
 342
 343 void
 344 nfa_add_literal (const char lit)
 345 {
 346   struct GNUNET_REGEX_Nfa *n;
 347   struct State *start;
 348   struct State *end;
 349
 350   start = nfa_create_state (0);
 351   end = nfa_create_state (1);
 352   nfa_add_transition (start, lit, end);
 353   n = nfa_create (start, end);
 354   push (n, &nfa_stack);
 355 }
 356
 357 struct GNUNET_REGEX_Nfa *
 358 GNUNET_REGEX_construct_nfa (const char *regex, size_t len)
 359 {
 360   struct GNUNET_REGEX_Nfa *nfa;
 361   unsigned int count;
 362   unsigned int altcount;
 363   unsigned int atomcount;
 364   unsigned int pcount;
 365   struct p_stage
 366   {
 367     int altcount;
 368     int atomcount;
 369   };
 370   struct p_stage *p;
 371
 372   p = NULL;
 373
 374   altcount = 0;
 375   atomcount = 0;
 376   pcount = 0;
 377
 378   for (count = 0; count < len && *regex; count++, regex++)
 379   {
 380
 381     switch (*regex)
 382     {
 383     case '(':
 384       if (atomcount > 1)
 385       {
 386         --atomcount;
 387         nfa_add_concatenation ();
 388       }
 389       GNUNET_array_grow (p, pcount, pcount + 1);
 390       p[pcount - 1].altcount = altcount;
 391       p[pcount - 1].atomcount = atomcount;
 392       altcount = 0;
 393       atomcount = 0;
 394       break;
 395     case '|':
 396       if (0 == atomcount)
 397         goto error;
 398       while (--atomcount > 0)
 399         nfa_add_concatenation ();
 400       altcount++;
 401       break;
 402     case ')':
 403       if (0 == pcount)
 404         goto error;
 405       if (atomcount == 0)
 406         goto error;
 407       while (--atomcount > 0)
 408         nfa_add_concatenation ();
 409       for (; altcount > 0; altcount--)
 410         nfa_add_alternation ();
 411       pcount--;
 412       altcount = p[pcount].altcount;
 413       atomcount = p[pcount].atomcount;
 414       atomcount++;
 415       break;
 416     case '*':
 417       if (atomcount == 0)
 418         goto error;
 419       nfa_add_star_op ();
 420       break;
 421     case '+':
 422       if (atomcount == 0)
 423         goto error;
 424       nfa_add_plus_op ();
 425       break;
 426     case 92:                   /* escape: \ */
 427       regex++;
 428       count++;
 429     default:
 430       if (atomcount > 1)
 431       {
 432         --atomcount;
 433         nfa_add_concatenation ();
 434       }
 435       nfa_add_literal (*regex);
 436       atomcount++;
 437       break;
 438     }
 439   }
 440   if (0 != pcount)
 441     goto error;
 442   while (--atomcount > 0)
 443     nfa_add_concatenation ();
 444   for (; altcount > 0; altcount--)
 445     nfa_add_alternation ();
 446
 447   if (NULL != p)
 448     GNUNET_free (p);
 449
 450   nfa = pop (&nfa_stack);
 451
 452   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 453               "Created NFA with %i States and a total of %i Transitions\n",
 454               state_id, transition_id);
 455
 456   return nfa;
 457
 458 error:
 459   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n");
 460   GNUNET_free (p);
 461   while (!empty (&nfa_stack))
 462     GNUNET_REGEX_destroy_nfa (pop (&nfa_stack));
 463   return NULL;
 464 }
 465
 466 void
 467 GNUNET_REGEX_destroy_nfa (struct GNUNET_REGEX_Nfa *n)
 468 {
 469   int i;
 470
 471   for (i = 0; i < n->statecnt; i++)
 472   {
 473     nfa_destroy_state (n->states[i]);
 474   }
 475
 476   GNUNET_free (n->states);
 477   GNUNET_free (n);
 478 }
 479
 480 void
 481 GNUNET_REGEX_save_nfa_graph (struct GNUNET_REGEX_Nfa *n, const char *filename)
 482 {
 483   struct State *s;
 484   char *start;
 485   char *end;
 486   char *states;
 487   FILE *p;
 488   int i_s;
 489   int i_t;
 490
 491   if (NULL == n)
 492   {
 493     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 494     return;
 495   }
 496
 497   mark_all_states (n, 0);
 498
 499   states = GNUNET_malloc (sizeof (char));
 500   *states = '\0';
 501
 502   for (i_s = 0; i_s < n->statecnt; i_s++)
 503   {
 504     struct Transition *ctran;
 505     char *s_acc = NULL;
 506     char *s_tran = NULL;
 507
 508     s = n->states[i_s];
 509
 510     if (s->accepting)
 511     {
 512       GNUNET_asprintf (&s_acc, "s%i [shape=doublecircle];\n", s->id);
 513
 514       states = GNUNET_realloc (states, strlen (states) + strlen (s_acc) + 1);
 515       strcat (states, s_acc);
 516       GNUNET_free (s_acc);
 517     }
 518
 519     ctran = s->transitions;
 520     s->visited = 1;
 521
 522     for (i_t = 0; i_t < s->tcnt && NULL != s->transitions; i_t++)
 523     {
 524       if (NULL == ctran)
 525       {
 526         GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "s->transitions was NULL\n");
 527       }
 528
 529       if (NULL == ctran->state)
 530       {
 531         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 532                     "Transition from State %i has has no state for transitioning\n",
 533                     s->id);
 534       }
 535
 536       if (ctran->literal == 0)
 537       {
 538         GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"epsilon\"];\n", s->id,
 539                          ctran->state->id);
 540       }
 541       else
 542       {
 543         GNUNET_asprintf (&s_tran, "s%i -> s%i [label = \"%c\"];\n", s->id,
 544                          ctran->state->id, ctran->literal);
 545       }
 546
 547       states = GNUNET_realloc (states, strlen (states) + strlen (s_tran) + 1);
 548       strcat (states, s_tran);
 549       GNUNET_free (s_tran);
 550
 551       ctran++;
 552     }
 553   }
 554
 555   if (NULL == states)
 556   {
 557     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA");
 558     return;
 559   }
 560
 561   if (NULL == filename || strlen (filename) < 1)
 562   {
 563     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 564     GNUNET_free (states);
 565     return;
 566   }
 567
 568   p = fopen (filename, "w");
 569   if (p == NULL)
 570   {
 571     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 572                 filename);
 573     GNUNET_free (states);
 574     return;
 575   }
 576
 577   start = "digraph G {\nrankdir=LR\n";
 578   end = "\n}\n";
 579   fwrite (start, strlen (start), 1, p);
 580   fwrite (states, strlen (states), 1, p);
 581   fwrite (end, strlen (end), 1, p);
 582   fclose (p);
 583
 584   GNUNET_free (states);
 585 }