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_crypto_lib.h"
  28 #include "gnunet_regex_lib.h"
  29 #include "regex_internal.h"
  30
  31 /**
  32  * Constant for how many bits the initial string regex should have.
  33  */
  34 #define INITIAL_BITS 10
  35
  36 /**
  37  * Context that contains an id counter for states and transitions as well as a
  38  * DLL of automatons used as a stack for NFA construction.
  39  */
  40 struct GNUNET_REGEX_Context
  41 {
  42   /**
  43    * Unique state id.
  44    */
  45   unsigned int state_id;
  46
  47   /**
  48    * Unique transition id.
  49    */
  50   unsigned int transition_id;
  51
  52   /**
  53    * DLL of GNUNET_REGEX_Automaton's used as a stack.
  54    */
  55   struct GNUNET_REGEX_Automaton *stack_head;
  56
  57   /**
  58    * DLL of GNUNET_REGEX_Automaton's used as a stack.
  59    */
  60   struct GNUNET_REGEX_Automaton *stack_tail;
  61 };
  62
  63 /**
  64  * Type of an automaton.
  65  */
  66 enum GNUNET_REGEX_AutomatonType
  67 {
  68   NFA,
  69   DFA
  70 };
  71
  72 /**
  73  * Automaton representation.
  74  */
  75 struct GNUNET_REGEX_Automaton
  76 {
  77   /**
  78    * Linked list of NFAs used for partial NFA creation.
  79    */
  80   struct GNUNET_REGEX_Automaton *prev;
  81
  82   /**
  83    * Linked list of NFAs used for partial NFA creation.
  84    */
  85   struct GNUNET_REGEX_Automaton *next;
  86
  87   /**
  88    * First state of the automaton. This is mainly used for constructing an NFA,
  89    * where each NFA itself consists of one or more NFAs linked together.
  90    */
  91   struct GNUNET_REGEX_State *start;
  92
  93   /**
  94    * End state of the partial NFA. This is undefined for DFAs
  95    */
  96   struct GNUNET_REGEX_State *end;
  97
  98   /**
  99    * Number of states in the automaton.
 100    */
 101   unsigned int state_count;
 102
 103   /**
 104    * DLL of states.
 105    */
 106   struct GNUNET_REGEX_State *states_head;
 107
 108   /**
 109    * DLL of states
 110    */
 111   struct GNUNET_REGEX_State *states_tail;
 112
 113   /**
 114    * Type of the automaton.
 115    */
 116   enum GNUNET_REGEX_AutomatonType type;
 117
 118   /**
 119    * Regex
 120    */
 121   char *regex;
 122
 123   /**
 124    * Canonical regex (result of RX->NFA->DFA->RX)
 125    */
 126   char *canonical_regex;
 127 };
 128
 129 /**
 130  * A state. Can be used in DFA and NFA automatons.
 131  */
 132 struct GNUNET_REGEX_State
 133 {
 134   /**
 135    * This is a linked list.
 136    */
 137   struct GNUNET_REGEX_State *prev;
 138
 139   /**
 140    * This is a linked list.
 141    */
 142   struct GNUNET_REGEX_State *next;
 143
 144   /**
 145    * Unique state id.
 146    */
 147   unsigned int id;
 148
 149   /**
 150    * If this is an accepting state or not.
 151    */
 152   int accepting;
 153
 154   /**
 155    * Marking of the state. This is used for marking all visited states when
 156    * traversing all states of an automaton and for cases where the state id
 157    * cannot be used (dfa minimization).
 158    */
 159   int marked;
 160
 161   /**
 162    * Marking the state as contained. This is used for checking, if the state is
 163    * contained in a set in constant time
 164    */
 165   int contained;
 166
 167   /**
 168    * Marking the state as part of an SCC (Strongly Connected Component).  All
 169    * states with the same scc_id are part of the same SCC. scc_id is 0, if state
 170    * is not a part of any SCC.
 171    */
 172   unsigned int scc_id;
 173
 174   /**
 175    * Used for SCC detection.
 176    */
 177   int index;
 178
 179   /**
 180    * Used for SCC detection.
 181    */
 182   int lowlink;
 183
 184   /**
 185    * Human readable name of the automaton. Used for debugging and graph
 186    * creation.
 187    */
 188   char *name;
 189
 190   /**
 191    * Hash of the state.
 192    */
 193   struct GNUNET_HashCode hash;
 194
 195   /**
 196    * State ID for proof creation.
 197    */
 198   unsigned int proof_id;
 199
 200   /**
 201    * Proof for this state.
 202    */
 203   char *proof;
 204
 205   /**
 206    * Number of transitions from this state to other states.
 207    */
 208   unsigned int transition_count;
 209
 210   /**
 211    * DLL of transitions.
 212    */
 213   struct Transition *transitions_head;
 214
 215   /**
 216    * DLL of transitions.
 217    */
 218   struct Transition *transitions_tail;
 219
 220   /**
 221    * Set of states on which this state is based on. Used when creating a DFA out
 222    * of several NFA states.
 223    */
 224   struct GNUNET_REGEX_StateSet *nfa_set;
 225 };
 226
 227 /**
 228  * Transition between two states. Each state can have 0-n transitions.  If label
 229  * is 0, this is considered to be an epsilon transition.
 230  */
 231 struct Transition
 232 {
 233   /**
 234    * This is a linked list.
 235    */
 236   struct Transition *prev;
 237
 238   /**
 239    * This is a linked list.
 240    */
 241   struct Transition *next;
 242
 243   /**
 244    * Unique id of this transition.
 245    */
 246   unsigned int id;
 247
 248   /**
 249    * Label for this transition. This is basically the edge label for the graph.
 250    */
 251   char label;
 252
 253   /**
 254    * State to which this transition leads.
 255    */
 256   struct GNUNET_REGEX_State *to_state;
 257
 258   /**
 259    * State from which this transition origins.
 260    */
 261   struct GNUNET_REGEX_State *from_state;
 262
 263   /**
 264    * Mark this transition. For example when reversing the automaton.
 265    */
 266   int mark;
 267 };
 268
 269 /**
 270  * Set of states.
 271  */
 272 struct GNUNET_REGEX_StateSet
 273 {
 274   /**
 275    * Array of states.
 276    */
 277   struct GNUNET_REGEX_State **states;
 278
 279   /**
 280    * Length of the 'states' array.
 281    */
 282   unsigned int len;
 283 };
 284
 285 /*
 286  * Debug helper functions
 287  */
 288
 289 /**
 290  * Print all the transitions of state 's'.
 291  *
 292  * @param s state for which to print it's transitions.
 293  */
 294 void
 295 debug_print_transitions (struct GNUNET_REGEX_State *s);
 296
 297 /**
 298  * Print information of the given state 's'.
 299  *
 300  * @param s state for which debug information should be printed.
 301  */
 302 void
 303 debug_print_state (struct GNUNET_REGEX_State *s)
 304 {
 305   char *proof;
 306
 307   if (NULL == s->proof)
 308     proof = "NULL";
 309   else
 310     proof = s->proof;
 311
 312   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 313               "State %i: %s marked: %i accepting: %i scc_id: %i transitions: %i proof: %s\n",
 314               s->id, s->name, s->marked, s->accepting, s->scc_id,
 315               s->transition_count, proof);
 316
 317   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transitions:\n");
 318   debug_print_transitions (s);
 319 }
 320
 321 /**
 322  * Print debug information for all states contained in the automaton 'a'.
 323  *
 324  * @param a automaton for which debug information of it's states should be printed.
 325  */
 326 void
 327 debug_print_states (struct GNUNET_REGEX_Automaton *a)
 328 {
 329   struct GNUNET_REGEX_State *s;
 330
 331   for (s = a->states_head; NULL != s; s = s->next)
 332     debug_print_state (s);
 333 }
 334
 335 /**
 336  * Print debug information for given transition 't'.
 337  *
 338  * @param t transition for which to print debug info.
 339  */
 340 void
 341 debug_print_transition (struct Transition *t)
 342 {
 343   char *to_state;
 344   char *from_state;
 345   char label;
 346
 347   if (NULL == t)
 348     return;
 349
 350   if (0 == t->label)
 351     label = '0';
 352   else
 353     label = t->label;
 354
 355   if (NULL == t->to_state)
 356     to_state = "NULL";
 357   else
 358     to_state = t->to_state->name;
 359
 360   if (NULL == t->from_state)
 361     from_state = "NULL";
 362   else
 363     from_state = t->from_state->name;
 364
 365   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %c to %s\n",
 366               t->id, from_state, label, to_state);
 367 }
 368
 369 void
 370 debug_print_transitions (struct GNUNET_REGEX_State *s)
 371 {
 372   struct Transition *t;
 373
 374   for (t = s->transitions_head; NULL != t; t = t->next)
 375     debug_print_transition (t);
 376 }
 377
 378
 379 /**
 380  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
 381  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
 382  * SCCs inside an automaton.
 383  *
 384  * @param scc_counter counter for numbering the sccs
 385  * @param v start vertex
 386  * @param index current index
 387  * @param stack stack for saving all SCCs
 388  * @param stack_size current size of the stack
 389  */
 390 static void
 391 scc_tarjan_strongconnect (unsigned int *scc_counter,
 392                           struct GNUNET_REGEX_State *v, unsigned int *index,
 393                           struct GNUNET_REGEX_State **stack,
 394                           unsigned int *stack_size)
 395 {
 396   struct GNUNET_REGEX_State *w;
 397   struct Transition *t;
 398
 399   v->index = *index;
 400   v->lowlink = *index;
 401   (*index)++;
 402   stack[(*stack_size)++] = v;
 403   v->contained = 1;
 404
 405   for (t = v->transitions_head; NULL != t; t = t->next)
 406   {
 407     w = t->to_state;
 408     if (NULL != w && w->index < 0)
 409     {
 410       scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
 411       v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
 412     }
 413     else if (0 != w->contained)
 414       v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
 415   }
 416
 417   if (v->lowlink == v->index)
 418   {
 419     w = stack[--(*stack_size)];
 420     w->contained = 0;
 421
 422     if (v != w)
 423     {
 424       (*scc_counter)++;
 425       while (v != w)
 426       {
 427         w->scc_id = *scc_counter;
 428         w = stack[--(*stack_size)];
 429         w->contained = 0;
 430       }
 431       w->scc_id = *scc_counter;
 432     }
 433   }
 434 }
 435
 436
 437 /**
 438  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
 439  * SCCs will be marked using the scc_id on each state.
 440  *
 441  * @param a the automaton for which SCCs should be computed and assigned.
 442  */
 443 static void
 444 scc_tarjan (struct GNUNET_REGEX_Automaton *a)
 445 {
 446   unsigned int index;
 447   unsigned int scc_counter;
 448   struct GNUNET_REGEX_State *v;
 449   struct GNUNET_REGEX_State *stack[a->state_count];
 450   unsigned int stack_size;
 451
 452   for (v = a->states_head; NULL != v; v = v->next)
 453   {
 454     v->contained = 0;
 455     v->index = -1;
 456     v->lowlink = -1;
 457   }
 458
 459   stack_size = 0;
 460   index = 0;
 461   scc_counter = 0;
 462
 463   for (v = a->states_head; NULL != v; v = v->next)
 464   {
 465     if (v->index < 0)
 466       scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
 467   }
 468 }
 469
 470 /**
 471  * Adds a transition from one state to another on 'label'. Does not add
 472  * duplicate states.
 473  *
 474  * @param ctx context
 475  * @param from_state starting state for the transition
 476  * @param label transition label
 477  * @param to_state state to where the transition should point to
 478  */
 479 static void
 480 state_add_transition (struct GNUNET_REGEX_Context *ctx,
 481                       struct GNUNET_REGEX_State *from_state, const char label,
 482                       struct GNUNET_REGEX_State *to_state)
 483 {
 484   int is_dup;
 485   struct Transition *t;
 486   struct Transition *oth;
 487
 488   if (NULL == from_state)
 489   {
 490     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
 491     return;
 492   }
 493
 494   // Do not add duplicate state transitions
 495   is_dup = GNUNET_NO;
 496   for (t = from_state->transitions_head; NULL != t; t = t->next)
 497   {
 498     if (t->to_state == to_state && t->label == label &&
 499         t->from_state == from_state)
 500     {
 501       is_dup = GNUNET_YES;
 502       break;
 503     }
 504   }
 505
 506   if (is_dup)
 507     return;
 508
 509   // sort transitions by label
 510   for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
 511   {
 512     if (oth->label > label)
 513       break;
 514   }
 515
 516   t = GNUNET_malloc (sizeof (struct Transition));
 517   t->id = ctx->transition_id++;
 518   t->label = label;
 519   t->to_state = to_state;
 520   t->from_state = from_state;
 521
 522   // Add outgoing transition to 'from_state'
 523   from_state->transition_count++;
 524   GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head,
 525                                       from_state->transitions_tail, oth, t);
 526 }
 527
 528 /**
 529  * Compare two states. Used for sorting.
 530  *
 531  * @param a first state
 532  * @param b second state
 533  *
 534  * @return an integer less than, equal to, or greater than zero
 535  *         if the first argument is considered to be respectively
 536  *         less than, equal to, or greater than the second.
 537  */
 538 static int
 539 state_compare (const void *a, const void *b)
 540 {
 541   struct GNUNET_REGEX_State **s1;
 542   struct GNUNET_REGEX_State **s2;
 543
 544   s1 = (struct GNUNET_REGEX_State **) a;
 545   s2 = (struct GNUNET_REGEX_State **) b;
 546
 547   return (*s1)->id - (*s2)->id;
 548 }
 549
 550 /**
 551  * Get all edges leaving state 's'.
 552  *
 553  * @param s state.
 554  * @param edges all edges leaving 's'.
 555  *
 556  * @return number of edges.
 557  */
 558 static unsigned int
 559 state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges)
 560 {
 561   struct Transition *t;
 562   unsigned int count;
 563
 564   if (NULL == s)
 565     return 0;
 566
 567   count = 0;
 568
 569   for (t = s->transitions_head; NULL != t; t = t->next)
 570   {
 571     if (NULL != t->to_state)
 572     {
 573       edges[count].label = &t->label;
 574       edges[count].destination = t->to_state->hash;
 575       count++;
 576     }
 577   }
 578   return count;
 579 }
 580
 581 /**
 582  * Compare to state sets by comparing the id's of the states that are contained
 583  * in each set. Both sets are expected to be sorted by id!
 584  *
 585  * @param sset1 first state set
 586  * @param sset2 second state set
 587  *
 588  * @return an integer less than, equal to, or greater than zero
 589  *         if the first argument is considered to be respectively
 590  *         less than, equal to, or greater than the second.
 591  */
 592 static int
 593 state_set_compare (struct GNUNET_REGEX_StateSet *sset1,
 594                    struct GNUNET_REGEX_StateSet *sset2)
 595 {
 596   int result;
 597   int i;
 598
 599   if (NULL == sset1 || NULL == sset2)
 600     return 1;
 601
 602   result = sset1->len - sset2->len;
 603
 604   for (i = 0; i < sset1->len; i++)
 605   {
 606     if (0 != result)
 607       break;
 608
 609     result = state_compare (&sset1->states[i], &sset2->states[i]);
 610   }
 611   return result;
 612 }
 613
 614 /**
 615  * Clears the given StateSet 'set'
 616  *
 617  * @param set set to be cleared
 618  */
 619 static void
 620 state_set_clear (struct GNUNET_REGEX_StateSet *set)
 621 {
 622   if (NULL != set)
 623   {
 624     GNUNET_free_non_null (set->states);
 625     GNUNET_free (set);
 626   }
 627 }
 628
 629 /**
 630  * Clears an automaton fragment. Does not destroy the states inside the
 631  * automaton.
 632  *
 633  * @param a automaton to be cleared
 634  */
 635 static void
 636 automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
 637 {
 638   if (NULL == a)
 639     return;
 640
 641   a->start = NULL;
 642   a->end = NULL;
 643   a->states_head = NULL;
 644   a->states_tail = NULL;
 645   a->state_count = 0;
 646   GNUNET_free (a);
 647 }
 648
 649 /**
 650  * Frees the memory used by State 's'
 651  *
 652  * @param s state that should be destroyed
 653  */
 654 static void
 655 automaton_destroy_state (struct GNUNET_REGEX_State *s)
 656 {
 657   struct Transition *t;
 658   struct Transition *next_t;
 659
 660   if (NULL == s)
 661     return;
 662
 663   GNUNET_free_non_null (s->name);
 664   GNUNET_free_non_null (s->proof);
 665
 666   for (t = s->transitions_head; NULL != t; t = next_t)
 667   {
 668     next_t = t->next;
 669     GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
 670     GNUNET_free (t);
 671   }
 672
 673   state_set_clear (s->nfa_set);
 674
 675   GNUNET_free (s);
 676 }
 677
 678 /**
 679  * Remove a state from the given automaton 'a'. Always use this function when
 680  * altering the states of an automaton. Will also remove all transitions leading
 681  * to this state, before destroying it.
 682  *
 683  * @param a automaton
 684  * @param s state to remove
 685  */
 686 static void
 687 automaton_remove_state (struct GNUNET_REGEX_Automaton *a,
 688                         struct GNUNET_REGEX_State *s)
 689 {
 690   struct GNUNET_REGEX_State *ss;
 691   struct GNUNET_REGEX_State *s_check;
 692   struct Transition *t_check;
 693
 694   if (NULL == a || NULL == s)
 695     return;
 696
 697   // remove state
 698   ss = s;
 699   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
 700   a->state_count--;
 701
 702   // remove all transitions leading to this state
 703   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 704   {
 705     for (t_check = s_check->transitions_head; NULL != t_check;
 706          t_check = t_check->next)
 707     {
 708       if (t_check->to_state == ss)
 709       {
 710         GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
 711                                      s_check->transitions_tail, t_check);
 712         s_check->transition_count--;
 713       }
 714     }
 715   }
 716
 717   automaton_destroy_state (ss);
 718 }
 719
 720 /**
 721  * Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy
 722  * 's2'.
 723  *
 724  * @param ctx context
 725  * @param a automaton
 726  * @param s1 first state
 727  * @param s2 second state, will be destroyed
 728  */
 729 static void
 730 automaton_merge_states (struct GNUNET_REGEX_Context *ctx,
 731                         struct GNUNET_REGEX_Automaton *a,
 732                         struct GNUNET_REGEX_State *s1,
 733                         struct GNUNET_REGEX_State *s2)
 734 {
 735   struct GNUNET_REGEX_State *s_check;
 736   struct Transition *t_check;
 737   char *new_name;
 738
 739   GNUNET_assert (NULL != ctx && NULL != a && NULL != s1 && NULL != s2);
 740
 741   if (s1 == s2)
 742     return;
 743
 744   // 1. Make all transitions pointing to s2 point to s1
 745   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
 746   {
 747     for (t_check = s_check->transitions_head; NULL != t_check;
 748          t_check = t_check->next)
 749     {
 750       if (s2 == t_check->to_state)
 751         t_check->to_state = s1;
 752     }
 753   }
 754
 755   // 2. Add all transitions from s2 to sX to s1
 756   for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
 757   {
 758     if (t_check->to_state != s1)
 759       state_add_transition (ctx, s1, t_check->label, t_check->to_state);
 760   }
 761
 762   // 3. Rename s1 to {s1,s2}
 763   new_name = s1->name;
 764   GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name);
 765   GNUNET_free (new_name);
 766
 767   // remove state
 768   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2);
 769   a->state_count--;
 770   automaton_destroy_state (s2);
 771 }
 772
 773 /**
 774  * Add a state to the automaton 'a', always use this function to alter the
 775  * states DLL of the automaton.
 776  *
 777  * @param a automaton to add the state to
 778  * @param s state that should be added
 779  */
 780 static void
 781 automaton_add_state (struct GNUNET_REGEX_Automaton *a,
 782                      struct GNUNET_REGEX_State *s)
 783 {
 784   GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
 785   a->state_count++;
 786 }
 787
 788 /**
 789  * Function that is called with each state, when traversing an automaton.
 790  *
 791  * @param cls closure.
 792  * @param count current count of the state, from 0 to a->state_count -1.
 793  * @param s state.
 794  */
 795 typedef void (*GNUNET_REGEX_traverse_action) (void *cls, unsigned int count,
 796                                               struct GNUNET_REGEX_State * s);
 797
 798 /**
 799  * Depth-first traversal of all states that are reachable from state 's'. Expects the states to
 800  * be unmarked (s->marked == GNUNET_NO). Performs 'action' on each visited
 801  * state.
 802  *
 803  * @param s start state.
 804  * @param count current count of the state.
 805  * @param action action to be performed on each state.
 806  * @param action_cls closure for action
 807  */
 808 static void
 809 automaton_state_traverse (struct GNUNET_REGEX_State *s, unsigned int *count,
 810                           GNUNET_REGEX_traverse_action action, void *action_cls)
 811 {
 812   struct Transition *t;
 813
 814   if (GNUNET_NO != s->marked)
 815     return;
 816   s->marked = GNUNET_YES;
 817   if (NULL != action)
 818     action (action_cls, *count, s);
 819   (*count)++;
 820   for (t = s->transitions_head; NULL != t; t = t->next)
 821     automaton_state_traverse (t->to_state, count, action, action_cls);
 822 }
 823
 824
 825 /**
 826  * Traverses the given automaton from it's start state, visiting all reachable
 827  * states and calling 'action' on each one of them.
 828  *
 829  * @param a automaton.
 830  * @param action action to be performed on each state.
 831  * @param action_cls closure for action
 832  */
 833 static void
 834 automaton_traverse (struct GNUNET_REGEX_Automaton *a,
 835                     GNUNET_REGEX_traverse_action action, void *action_cls)
 836 {
 837   unsigned int count;
 838   struct GNUNET_REGEX_State *s;
 839
 840   for (s = a->states_head; NULL != s; s = s->next)
 841     s->marked = GNUNET_NO;
 842   count = 0;
 843   automaton_state_traverse (a->start, &count, action, action_cls);
 844 }
 845
 846
 847 /**
 848  * Check if the given string 'str' needs parentheses around it when
 849  * using it to generate a regex.
 850  *
 851  * Currently only tests for first and last characters being '()' respectively.
 852  * FIXME: What about "(ab)|(cd)"?
 853  *
 854  * @param str string
 855  *
 856  * @return GNUNET_YES if parentheses are needed, GNUNET_NO otherwise
 857  */
 858 static int
 859 needs_parentheses (const char *str)
 860 {
 861   size_t slen;
 862   const char *op;
 863   const char *cl;
 864   const char *pos;
 865   unsigned int cnt;
 866
 867   if ((NULL == str) || ((slen = strlen (str)) < 2))
 868     return GNUNET_NO;
 869
 870   if ('(' != str[0])
 871     return GNUNET_YES;
 872   cnt = 1;
 873   pos = &str[1];
 874   while (cnt > 0)
 875   {
 876     cl = strchr (pos, ')');
 877     if (NULL == cl)
 878     {
 879       GNUNET_break (0);
 880       return GNUNET_YES;
 881     }
 882     op = strchr (pos, '(');
 883     if ((NULL != op) && (op < cl))
 884     {
 885       cnt++;
 886       pos = op + 1;
 887       continue;
 888     }
 889     /* got ')' first */
 890     cnt--;
 891     pos = cl + 1;
 892   }
 893   return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
 894 }
 895
 896
 897 /**
 898  * Remove parentheses surrounding string 'str'.
 899  * Example: "(a)" becomes "a".
 900  * You need to GNUNET_free the returned string.
 901  *
 902  * Currently only tests for first and last characters being '()' respectively.
 903  * FIXME: What about "(ab)|(cd)"?
 904  *
 905  * @param str string, free'd or re-used by this function, can be NULL
 906  *
 907  * @return string without surrounding parentheses, string 'str' if no preceding
 908  *         epsilon could be found, NULL if 'str' was NULL
 909  */
 910 static char *
 911 remove_parentheses (char *str)
 912 {
 913   size_t slen;
 914
 915   if ((NULL == str) || ('(' != str[0]) ||
 916       (str[(slen = strlen (str)) - 1] != ')'))
 917     return str;
 918   memmove (str, &str[1], slen - 2);
 919   str[slen - 2] = '\0';
 920   return str;
 921 }
 922
 923
 924 /**
 925  * Check if the string 'str' starts with an epsilon (empty string).
 926  * Example: "(|a)" is starting with an epsilon.
 927  *
 928  * @param str string to test
 929  *
 930  * @return 0 if str has no epsilon, 1 if str starts with '(|' and ends with ')'
 931  */
 932 static int
 933 has_epsilon (const char *str)
 934 {
 935   return (NULL != str) && ('(' == str[0]) && ('|' == str[1]) &&
 936       (')' == str[strlen (str) - 1]);
 937 }
 938
 939
 940 /**
 941  * Remove an epsilon from the string str. Where epsilon is an empty string
 942  * Example: str = "(|a|b|c)", result: "a|b|c"
 943  * The returned string needs to be freed.
 944  *
 945  * @param str string
 946  *
 947  * @return string without preceding epsilon, string 'str' if no preceding epsilon
 948  *         could be found, NULL if 'str' was NULL
 949  */
 950 static char *
 951 remove_epsilon (const char *str)
 952 {
 953   size_t len;
 954
 955   if (NULL == str)
 956     return NULL;
 957   if (('(' == str[0]) && ('|' == str[1]))
 958   {
 959     len = strlen (str);
 960     if (')' == str[len - 1])
 961       return GNUNET_strndup (&str[2], len - 3);
 962   }
 963   return GNUNET_strdup (str);
 964 }
 965
 966 /**
 967  * Compare 'str1', starting from position 'k',  with whole 'str2'
 968  *
 969  * @param str1 first string to compare, starting from position 'k'
 970  * @param str2 second string for comparison
 971  * @param k starting position in 'str1'
 972  *
 973  * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
 974  */
 975 static int
 976 strkcmp (const char *str1, const char *str2, size_t k)
 977 {
 978   if ((NULL == str1) || (NULL == str2) || (strlen (str1) < k))
 979     return -1;
 980   return strcmp (&str1[k], str2);
 981 }
 982
 983
 984 /**
 985  * Compare two strings for equality. If either is NULL (or if both are
 986  * NULL), they are not equal.
 987  *
 988  * @param str1 first string for comparison.
 989  * @param str2 second string for comparison.
 990  *
 991  * @return  0 if the strings are the same, 1 or -1 if not
 992  */
 993 static int
 994 nullstrcmp (const char *str1, const char *str2)
 995 {
 996   if ((NULL == str1) || (NULL == str2))
 997     return -1;
 998   return strcmp (str1, str2);
 999 }
1000
1001 /**
1002  * Helper function used as 'action' in 'automaton_traverse' function to create
1003  * the depth-first numbering of the states.
1004  *
1005  * @param cls states array.
1006  * @param count current state counter.
1007  * @param s current state.
1008  */
1009 static void
1010 number_states (void *cls, unsigned int count, struct GNUNET_REGEX_State *s)
1011 {
1012   struct GNUNET_REGEX_State **states = cls;
1013
1014   s->proof_id = count;
1015   states[count] = s;
1016 }
1017
1018
1019 /**
1020  * create proofs for all states in the given automaton. Implementation of the
1021  * algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and
1022  * Computation 3rd Edition" by Hopcroft, Motwani and Ullman.
1023  *
1024  * @param a automaton.
1025  */
1026 static void
1027 automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
1028 {
1029   unsigned int n = a->state_count;
1030   struct GNUNET_REGEX_State *states[n];
1031   char *R_last[n][n];
1032   char *R_cur[n][n];
1033   struct Transition *t;
1034   char *R_cur_l;
1035   char *R_cur_r;
1036   char *temp_a;
1037   char *temp_b;
1038   char *R_temp_ij;
1039   char *R_temp_ik;
1040   char *R_temp_kj;
1041   char *R_temp_kk;
1042   char *complete_regex;
1043   unsigned int i;
1044   unsigned int j;
1045   unsigned int k;
1046   int cnt;
1047   int eps_check;
1048   int ij_ik_cmp;
1049   int ij_kj_cmp;
1050   int ik_kj_cmp;
1051   int ik_kk_cmp;
1052   int kk_kj_cmp;
1053   int clean_ik_kk_cmp;
1054   int clean_kk_kj_cmp;
1055   int length;
1056   int length_l;
1057   int length_r;
1058
1059   /* create depth-first numbering of the states, initializes 'state' */
1060   automaton_traverse (a, &number_states, states);
1061
1062   /* Compute regular expressions of length "1" between each pair of states */
1063   for (i = 0; i < n; i++)
1064   {
1065     for (j = 0; j < n; j++)
1066     {
1067       R_cur[i][j] = NULL;
1068       R_last[i][j] = NULL;
1069     }
1070     for (t = states[i]->transitions_head; NULL != t; t = t->next)
1071     {
1072       j = t->to_state->proof_id;
1073       if (NULL == R_last[i][j])
1074         GNUNET_asprintf (&R_last[i][j], "%c", t->label);
1075       else
1076       {
1077         temp_a = R_last[i][j];
1078         GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
1079         GNUNET_free (temp_a);
1080       }
1081     }
1082     if (NULL == R_last[i][i])
1083       GNUNET_asprintf (&R_last[i][i], "");
1084     else
1085     {
1086       temp_a = R_last[i][i];
1087       GNUNET_asprintf (&R_last[i][i], "(|%s)", R_last[i][i]);
1088       GNUNET_free (temp_a);
1089     }
1090   }
1091   for (i = 0; i < n; i++)
1092     for (j = 0; j < n; j++)
1093       if (needs_parentheses (R_last[i][j]))
1094       {
1095         temp_a = R_last[i][j];
1096         GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
1097         GNUNET_free (temp_a);
1098       }
1099
1100   // TODO: clean up and fix the induction part
1101
1102   // INDUCTION
1103   for (k = 0; k < n; k++)
1104   {
1105     for (i = 0; i < n; i++)
1106     {
1107       for (j = 0; j < n; j++)
1108       {
1109         /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, */
1110         /* ">>> R_last[i][j] = %s R_last[i][k] = %s " */
1111         /* "R_last[k][k] = %s R_last[k][j] = %s\n", R_last[i][j], */
1112         /* R_last[i][k], R_last[k][k], R_last[k][j]); */
1113
1114         R_cur[i][j] = NULL;
1115         R_cur_r = NULL;
1116         R_cur_l = NULL;
1117
1118         // cache results from strcmp, we might need these many times
1119         ij_kj_cmp = nullstrcmp (R_last[i][j], R_last[k][j]);
1120         ij_ik_cmp = nullstrcmp (R_last[i][j], R_last[i][k]);
1121         ik_kk_cmp = nullstrcmp (R_last[i][k], R_last[k][k]);
1122         ik_kj_cmp = nullstrcmp (R_last[i][k], R_last[k][j]);
1123         kk_kj_cmp = nullstrcmp (R_last[k][k], R_last[k][j]);
1124
1125         // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk})^* R^{(k-1)}_{kj}
1126         // With: R_cur[i][j] = R_cur_l | R_cur_r
1127         // Rij(k) = Rij(k-1), because right side (R_cur_r) is empty set (NULL)
1128         if ((NULL == R_last[i][k] || NULL == R_last[k][j] ||
1129              NULL == R_last[k][k]) && NULL != R_last[i][j])
1130         {
1131           R_cur[i][j] = GNUNET_strdup (R_last[i][j]);
1132         }
1133         // Everything is NULL, so Rij(k) = NULL
1134         else if ((NULL == R_last[i][k] || NULL == R_last[k][j] ||
1135                   NULL == R_last[k][k]) && NULL == R_last[i][j])
1136         {
1137           R_cur[i][j] = NULL;
1138         }
1139         // Right side (R_cur_r) not NULL
1140         else
1141         {
1142           /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, */
1143           /* "R_temp_ij = %s  R_temp_ik = %s  R_temp_kk = %s  R_temp_kj = %s\n", */
1144           /* R_temp_ij, R_temp_ik, R_temp_kk, R_temp_kj); */
1145
1146           // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
1147           // as parentheses, so we can better compare the contents
1148           R_temp_ik = remove_parentheses (remove_epsilon (R_last[i][k]));
1149           R_temp_kk = remove_parentheses (remove_epsilon (R_last[k][k]));
1150           R_temp_kj = remove_parentheses (remove_epsilon (R_last[k][j]));
1151
1152           clean_ik_kk_cmp = nullstrcmp (R_last[i][k], R_temp_kk);
1153           clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last[k][j]);
1154
1155           // construct R_cur_l (and, if necessary R_cur_r)
1156           if (NULL != R_last[i][j])
1157           {
1158             // Assign R_temp_ij to R_last[i][j] and remove epsilon as well
1159             // as parentheses, so we can better compare the contents
1160             R_temp_ij = remove_parentheses (remove_epsilon (R_last[i][j]));
1161
1162             if (0 == strcmp (R_temp_ij, R_temp_ik) &&
1163                 0 == strcmp (R_temp_ik, R_temp_kk) &&
1164                 0 == strcmp (R_temp_kk, R_temp_kj))
1165             {
1166               if (0 == strlen (R_temp_ij))
1167               {
1168                 R_cur_r = GNUNET_strdup ("");
1169               }
1170               // a|(e|a)a*(e|a) = a*
1171               // a|(e|a)(e|a)*(e|a) = a*
1172               // (e|a)|aa*a = a*
1173               // (e|a)|aa*(e|a) = a*
1174               // (e|a)|(e|a)a*a = a*
1175               // (e|a)|(e|a)a*(e|a) = a*
1176               // (e|a)|(e|a)(e|a)*(e|a) = a*
1177               else if ((0 == strncmp (R_last[i][j], "(|", 2)) ||
1178                        (0 == strncmp (R_last[i][k], "(|", 2) &&
1179                         0 == strncmp (R_last[k][j], "(|", 2)))
1180               {
1181                 if (GNUNET_YES == needs_parentheses (R_temp_ij))
1182                   GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij);
1183                 else
1184                   GNUNET_asprintf (&R_cur_r, "%s*", R_temp_ij);
1185               }
1186               // a|aa*a = a+
1187               // a|(e|a)a*a = a+
1188               // a|aa*(e|a) = a+
1189               // a|(e|a)(e|a)*a = a+
1190               // a|a(e|a)*(e|a) = a+
1191               else
1192               {
1193                 if (GNUNET_YES == needs_parentheses (R_temp_ij))
1194                   GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij);
1195                 else
1196                   GNUNET_asprintf (&R_cur_r, "%s+", R_temp_ij);
1197               }
1198             }
1199             // a|ab*b = ab*
1200             else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp &&
1201                      0 != clean_ik_kk_cmp)
1202             {
1203               if (strlen (R_last[k][k]) < 1)
1204                 R_cur_r = GNUNET_strdup (R_last[i][j]);
1205               else if (GNUNET_YES == needs_parentheses (R_temp_kk))
1206                 GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][j], R_temp_kk);
1207               else
1208                 GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][j], R_last[k][k]);
1209
1210               R_cur_l = NULL;
1211             }
1212             // a|bb*a = b*a
1213             else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp &&
1214                      0 != clean_kk_kj_cmp)
1215             {
1216               if (strlen (R_last[k][k]) < 1)
1217                 R_cur_r = GNUNET_strdup (R_last[k][j]);
1218               else if (GNUNET_YES == needs_parentheses (R_temp_kk))
1219                 GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last[k][j]);
1220               else
1221                 GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[k][j]);
1222
1223               R_cur_l = NULL;
1224             }
1225             // a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab*
1226             else if (0 == ij_ik_cmp && 0 == kk_kj_cmp &&
1227                      !has_epsilon (R_last[i][j]) && has_epsilon (R_last[k][k]))
1228             {
1229               if (needs_parentheses (R_temp_kk))
1230                 GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][j], R_temp_kk);
1231               else
1232                 GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][j], R_temp_kk);
1233
1234               R_cur_l = NULL;
1235             }
1236             // a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|...  = b*a
1237             else if (0 == ij_kj_cmp && 0 == ik_kk_cmp &&
1238                      !has_epsilon (R_last[i][j]) && has_epsilon (R_last[k][k]))
1239             {
1240               if (needs_parentheses (R_temp_kk))
1241                 GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last[i][j]);
1242               else
1243                 GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[i][j]);
1244
1245               R_cur_l = NULL;
1246             }
1247             else
1248             {
1249               /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "NO SIMPLIFICATION\n"); */
1250               temp_a =
1251                   (NULL == R_last[i][j]) ? NULL : GNUNET_strdup (R_last[i][j]);
1252               temp_a = remove_parentheses (temp_a);
1253               R_cur_l = temp_a;
1254             }
1255
1256             GNUNET_free_non_null (R_temp_ij);
1257           }
1258           // we have no left side
1259           else
1260           {
1261             R_cur_l = NULL;
1262           }
1263
1264           // construct R_cur_r, if not already constructed
1265           if (NULL == R_cur_r)
1266           {
1267             length = strlen (R_temp_kk) - strlen (R_last[i][k]);
1268
1269             // a(ba)*bx = (ab)+x
1270             if (length > 0 && NULL != R_last[k][k] && 0 < strlen (R_last[k][k])
1271                 && NULL != R_last[k][j] && 0 < strlen (R_last[k][j]) &&
1272                 NULL != R_last[i][k] && 0 < strlen (R_last[i][k]) &&
1273                 0 == strkcmp (R_temp_kk, R_last[i][k], length) &&
1274                 0 == strncmp (R_temp_kk, R_last[k][j], length))
1275             {
1276               temp_a = GNUNET_malloc (length + 1);
1277               temp_b = GNUNET_malloc ((strlen (R_last[k][j]) - length) + 1);
1278
1279               length_l = 0;
1280               length_r = 0;
1281
1282               for (cnt = 0; cnt < strlen (R_last[k][j]); cnt++)
1283               {
1284                 if (cnt < length)
1285                 {
1286                   temp_a[length_l] = R_last[k][j][cnt];
1287                   length_l++;
1288                 }
1289                 else
1290                 {
1291                   temp_b[length_r] = R_last[k][j][cnt];
1292                   length_r++;
1293                 }
1294               }
1295               temp_a[length_l] = '\0';
1296               temp_b[length_r] = '\0';
1297
1298               // e|(ab)+ = (ab)*
1299               if (NULL != R_cur_l && 0 == strlen (R_cur_l) &&
1300                   0 == strlen (temp_b))
1301               {
1302                 GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last[i][k], temp_a);
1303                 GNUNET_free (R_cur_l);
1304                 R_cur_l = NULL;
1305               }
1306               else
1307               {
1308                 GNUNET_asprintf (&R_cur_r, "(%s%s)+%s", R_last[i][k], temp_a,
1309                                  temp_b);
1310               }
1311               GNUNET_free (temp_a);
1312               GNUNET_free (temp_b);
1313             }
1314             else if (0 == strcmp (R_temp_ik, R_temp_kk) &&
1315                      0 == strcmp (R_temp_kk, R_temp_kj))
1316             {
1317               // (e|a)a*(e|a) = a*
1318               // (e|a)(e|a)*(e|a) = a*
1319               if (has_epsilon (R_last[i][k]) && has_epsilon (R_last[k][j]))
1320               {
1321                 if (needs_parentheses (R_temp_kk))
1322                   GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_kk);
1323                 else
1324                   GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk);
1325               }
1326               // aa*a = a+a
1327               else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp &&
1328                        !has_epsilon (R_last[i][k]))
1329               {
1330                 if (needs_parentheses (R_temp_kk))
1331                   GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
1332                 else
1333                   GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
1334               }
1335               // (e|a)a*a = a+
1336               // aa*(e|a) = a+
1337               // a(e|a)*(e|a) = a+
1338               // (e|a)a*a = a+
1339               else
1340               {
1341                 eps_check =
1342                     (has_epsilon (R_last[i][k]) + has_epsilon (R_last[k][k]) +
1343                      has_epsilon (R_last[k][j]));
1344
1345                 if (eps_check == 1)
1346                 {
1347                   if (needs_parentheses (R_temp_kk))
1348                     GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_kk);
1349                   else
1350                     GNUNET_asprintf (&R_cur_r, "%s+", R_temp_kk);
1351                 }
1352               }
1353             }
1354             // aa*b = a+b
1355             // (e|a)(e|a)*b = a*b
1356             else if (0 == strcmp (R_temp_ik, R_temp_kk))
1357             {
1358               if (has_epsilon (R_last[i][k]))
1359               {
1360                 if (needs_parentheses (R_temp_kk))
1361                   GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk,
1362                                    R_last[k][j]);
1363                 else
1364                   GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last[k][j]);
1365               }
1366               else
1367               {
1368                 if (needs_parentheses (R_temp_kk))
1369                   GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk,
1370                                    R_last[k][j]);
1371                 else
1372                   GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last[k][j]);
1373               }
1374             }
1375             // ba*a = ba+
1376             // b(e|a)*(e|a) = ba*
1377             else if (0 == strcmp (R_temp_kk, R_temp_kj))
1378             {
1379               if (has_epsilon (R_last[k][j]))
1380               {
1381                 if (needs_parentheses (R_temp_kk))
1382                   GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last[i][k],
1383                                    R_temp_kk);
1384                 else
1385                   GNUNET_asprintf (&R_cur_r, "%s%s*", R_last[i][k], R_temp_kk);
1386               }
1387               else
1388               {
1389                 if (needs_parentheses (R_temp_kk))
1390                   GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_last[i][k],
1391                                    R_temp_kk);
1392                 else
1393                   GNUNET_asprintf (&R_cur_r, "%s+%s", R_last[i][k], R_temp_kk);
1394               }
1395             }
1396             else
1397             {
1398               if (strlen (R_temp_kk) > 0)
1399               {
1400                 if (needs_parentheses (R_temp_kk))
1401                 {
1402                   GNUNET_asprintf (&R_cur_r, "%s(%s)*%s", R_last[i][k],
1403                                    R_temp_kk, R_last[k][j]);
1404                 }
1405                 else
1406                 {
1407                   GNUNET_asprintf (&R_cur_r, "%s%s*%s", R_last[i][k], R_temp_kk,
1408                                    R_last[k][j]);
1409                 }
1410               }
1411               else
1412               {
1413                 GNUNET_asprintf (&R_cur_r, "%s%s", R_last[i][k], R_last[k][j]);
1414               }
1415             }
1416           }
1417
1418           /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "R_cur_l: %s\n", R_cur_l); */
1419           /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "R_cur_r: %s\n", R_cur_r); */
1420
1421           // putting it all together
1422           if (NULL != R_cur_l && NULL != R_cur_r)
1423           {
1424             // a|a = a
1425             if (0 == strcmp (R_cur_l, R_cur_r))
1426             {
1427               R_cur[i][j] = GNUNET_strdup (R_cur_l);
1428             }
1429             // R_cur_l | R_cur_r
1430             else
1431             {
1432               GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", R_cur_l, R_cur_r);
1433             }
1434           }
1435           else if (NULL != R_cur_l)
1436           {
1437             R_cur[i][j] = GNUNET_strdup (R_cur_l);
1438           }
1439           else if (NULL != R_cur_r)
1440           {
1441             R_cur[i][j] = GNUNET_strdup (R_cur_r);
1442           }
1443           else
1444           {
1445             R_cur[i][j] = NULL;
1446           }
1447
1448           GNUNET_free_non_null (R_cur_l);
1449           GNUNET_free_non_null (R_cur_r);
1450
1451           GNUNET_free_non_null (R_temp_ik);
1452           GNUNET_free_non_null (R_temp_kk);
1453           GNUNET_free_non_null (R_temp_kj);
1454         }
1455       }
1456     }
1457
1458     // set R_last = R_cur
1459     for (i = 0; i < n; i++)
1460     {
1461       for (j = 0; j < n; j++)
1462       {
1463         GNUNET_free_non_null (R_last[i][j]);
1464         R_last[i][j] = R_cur[i][j];
1465         R_cur[i][j] = NULL;
1466       }
1467     }
1468   }
1469
1470   // assign proofs and hashes
1471   for (i = 0; i < n; i++)
1472   {
1473     if (NULL != R_last[a->start->proof_id][i])
1474     {
1475       states[i]->proof = GNUNET_strdup (R_last[a->start->proof_id][i]);
1476       GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof),
1477                           &states[i]->hash);
1478     }
1479   }
1480
1481   // complete regex for whole DFA: union of all pairs (start state/accepting state(s)).
1482   complete_regex = NULL;
1483   for (i = 0; i < n; i++)
1484   {
1485     if (states[i]->accepting)
1486     {
1487       if (NULL == complete_regex && 0 < strlen (R_last[a->start->proof_id][i]))
1488         GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->proof_id][i]);
1489       else if (NULL != R_last[a->start->proof_id][i] &&
1490                0 < strlen (R_last[a->start->proof_id][i]))
1491       {
1492         temp_a = complete_regex;
1493         GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex,
1494                          R_last[a->start->proof_id][i]);
1495         GNUNET_free (temp_a);
1496       }
1497     }
1498   }
1499   a->canonical_regex = complete_regex;
1500
1501   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1502               "---------------------------------------------\n");
1503   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex: %s\n", a->regex);
1504   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Complete Regex: %s\n", complete_regex);
1505   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1506               "---------------------------------------------\n");
1507
1508   // cleanup
1509   for (i = 0; i < n; i++)
1510   {
1511     for (j = 0; j < n; j++)
1512       GNUNET_free_non_null (R_last[i][j]);
1513   }
1514 }
1515
1516 /**
1517  * Creates a new DFA state based on a set of NFA states. Needs to be freed using
1518  * automaton_destroy_state.
1519  *
1520  * @param ctx context
1521  * @param nfa_states set of NFA states on which the DFA should be based on
1522  *
1523  * @return new DFA state
1524  */
1525 static struct GNUNET_REGEX_State *
1526 dfa_state_create (struct GNUNET_REGEX_Context *ctx,
1527                   struct GNUNET_REGEX_StateSet *nfa_states)
1528 {
1529   struct GNUNET_REGEX_State *s;
1530   char *name;
1531   int len = 0;
1532   struct GNUNET_REGEX_State *cstate;
1533   struct Transition *ctran;
1534   int insert = 1;
1535   struct Transition *t;
1536   int i;
1537
1538   s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
1539   s->id = ctx->state_id++;
1540   s->accepting = 0;
1541   s->marked = 0;
1542   s->name = NULL;
1543   s->scc_id = 0;
1544   s->index = -1;
1545   s->lowlink = -1;
1546   s->contained = 0;
1547   s->proof = NULL;
1548
1549   if (NULL == nfa_states)
1550   {
1551     GNUNET_asprintf (&s->name, "s%i", s->id);
1552     return s;
1553   }
1554
1555   s->nfa_set = nfa_states;
1556
1557   if (nfa_states->len < 1)
1558     return s;
1559
1560   // Create a name based on 'sset'
1561   s->name = GNUNET_malloc (sizeof (char) * 2);
1562   strcat (s->name, "{");
1563   name = NULL;
1564
1565   for (i = 0; i < nfa_states->len; i++)
1566   {
1567     cstate = nfa_states->states[i];
1568     GNUNET_asprintf (&name, "%i,", cstate->id);
1569
1570     if (NULL != name)
1571     {
1572       len = strlen (s->name) + strlen (name) + 1;
1573       s->name = GNUNET_realloc (s->name, len);
1574       strcat (s->name, name);
1575       GNUNET_free (name);
1576       name = NULL;
1577     }
1578
1579     // Add a transition for each distinct label to NULL state
1580     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
1581     {
1582       if (0 != ctran->label)
1583       {
1584         insert = 1;
1585
1586         for (t = s->transitions_head; NULL != t; t = t->next)
1587         {
1588           if (t->label == ctran->label)
1589           {
1590             insert = 0;
1591             break;
1592           }
1593         }
1594
1595         if (insert)
1596           state_add_transition (ctx, s, ctran->label, NULL);
1597       }
1598     }
1599
1600     // If the nfa_states contain an accepting state, the new dfa state is also
1601     // accepting
1602     if (cstate->accepting)
1603       s->accepting = 1;
1604   }
1605
1606   s->name[strlen (s->name) - 1] = '}';
1607
1608   return s;
1609 }
1610
1611 /**
1612  * Move from the given state 's' to the next state on transition 'label'
1613  *
1614  * @param s starting state
1615  * @param label edge label to follow
1616  *
1617  * @return new state or NULL, if transition on label not possible
1618  */
1619 static struct GNUNET_REGEX_State *
1620 dfa_move (struct GNUNET_REGEX_State *s, const char label)
1621 {
1622   struct Transition *t;
1623   struct GNUNET_REGEX_State *new_s;
1624
1625   if (NULL == s)
1626     return NULL;
1627
1628   new_s = NULL;
1629
1630   for (t = s->transitions_head; NULL != t; t = t->next)
1631   {
1632     if (label == t->label)
1633     {
1634       new_s = t->to_state;
1635       break;
1636     }
1637   }
1638
1639   return new_s;
1640 }
1641
1642 /**
1643  * Remove all unreachable states from DFA 'a'. Unreachable states are those
1644  * states that are not reachable from the starting state.
1645  *
1646  * @param a DFA automaton
1647  */
1648 static void
1649 dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
1650 {
1651   struct GNUNET_REGEX_State *s;
1652   struct GNUNET_REGEX_State *s_next;
1653
1654   // 1. unmark all states
1655   for (s = a->states_head; NULL != s; s = s->next)
1656     s->marked = GNUNET_NO;
1657
1658   // 2. traverse dfa from start state and mark all visited states
1659   automaton_traverse (a, NULL, NULL);
1660
1661   // 3. delete all states that were not visited
1662   for (s = a->states_head; NULL != s; s = s_next)
1663   {
1664     s_next = s->next;
1665     if (GNUNET_NO == s->marked)
1666       automaton_remove_state (a, s);
1667   }
1668 }
1669
1670 /**
1671  * Remove all dead states from the DFA 'a'. Dead states are those states that do
1672  * not transition to any other state but themselfes.
1673  *
1674  * @param a DFA automaton
1675  */
1676 static void
1677 dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
1678 {
1679   struct GNUNET_REGEX_State *s;
1680   struct Transition *t;
1681   int dead;
1682
1683   GNUNET_assert (DFA == a->type);
1684
1685   for (s = a->states_head; NULL != s; s = s->next)
1686   {
1687     if (s->accepting)
1688       continue;
1689
1690     dead = 1;
1691     for (t = s->transitions_head; NULL != t; t = t->next)
1692     {
1693       if (NULL != t->to_state && t->to_state != s)
1694       {
1695         dead = 0;
1696         break;
1697       }
1698     }
1699
1700     if (0 == dead)
1701       continue;
1702
1703     // state s is dead, remove it
1704     automaton_remove_state (a, s);
1705   }
1706 }
1707
1708 /**
1709  * Merge all non distinguishable states in the DFA 'a'
1710  *
1711  * @param ctx context
1712  * @param a DFA automaton
1713  */
1714 static void
1715 dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
1716                                      struct GNUNET_REGEX_Automaton *a)
1717 {
1718   int i;
1719   int table[a->state_count][a->state_count];
1720   struct GNUNET_REGEX_State *s1;
1721   struct GNUNET_REGEX_State *s2;
1722   struct Transition *t1;
1723   struct Transition *t2;
1724   struct GNUNET_REGEX_State *s1_next;
1725   struct GNUNET_REGEX_State *s2_next;
1726   int change;
1727   int num_equal_edges;
1728
1729   for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1;
1730        i++, s1 = s1->next)
1731   {
1732     s1->marked = i;
1733   }
1734
1735   // Mark all pairs of accepting/!accepting states
1736   for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1737   {
1738     for (s2 = a->states_head; NULL != s2; s2 = s2->next)
1739     {
1740       table[s1->marked][s2->marked] = 0;
1741
1742       if ((s1->accepting && !s2->accepting) ||
1743           (!s1->accepting && s2->accepting))
1744       {
1745         table[s1->marked][s2->marked] = 1;
1746       }
1747     }
1748   }
1749
1750   // Find all equal states
1751   change = 1;
1752   while (0 != change)
1753   {
1754     change = 0;
1755     for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1756     {
1757       for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
1758       {
1759         if (0 != table[s1->marked][s2->marked])
1760           continue;
1761
1762         num_equal_edges = 0;
1763         for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
1764         {
1765           for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
1766           {
1767             if (t1->label == t2->label)
1768             {
1769               num_equal_edges++;
1770               if (0 != table[t1->to_state->marked][t2->to_state->marked] ||
1771                   0 != table[t2->to_state->marked][t1->to_state->marked])
1772               {
1773                 table[s1->marked][s2->marked] = t1->label != 0 ? t1->label : 1;
1774                 change = 1;
1775               }
1776             }
1777           }
1778         }
1779         if (num_equal_edges != s1->transition_count ||
1780             num_equal_edges != s2->transition_count)
1781         {
1782           // Make sure ALL edges of possible equal states are the same
1783           table[s1->marked][s2->marked] = -2;
1784         }
1785       }
1786     }
1787   }
1788
1789   // Merge states that are equal
1790   for (s1 = a->states_head; NULL != s1; s1 = s1_next)
1791   {
1792     s1_next = s1->next;
1793     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
1794     {
1795       s2_next = s2->next;
1796       if (table[s1->marked][s2->marked] == 0)
1797         automaton_merge_states (ctx, a, s1, s2);
1798     }
1799   }
1800 }
1801
1802 /**
1803  * Minimize the given DFA 'a' by removing all unreachable states, removing all
1804  * dead states and merging all non distinguishable states
1805  *
1806  * @param ctx context
1807  * @param a DFA automaton
1808  */
1809 static void
1810 dfa_minimize (struct GNUNET_REGEX_Context *ctx,
1811               struct GNUNET_REGEX_Automaton *a)
1812 {
1813   if (NULL == a)
1814     return;
1815
1816   GNUNET_assert (DFA == a->type);
1817
1818   // 1. remove unreachable states
1819   dfa_remove_unreachable_states (a);
1820
1821   // 2. remove dead states
1822   dfa_remove_dead_states (a);
1823
1824   // 3. Merge nondistinguishable states
1825   dfa_merge_nondistinguishable_states (ctx, a);
1826 }
1827
1828 /**
1829  * Creates a new NFA fragment. Needs to be cleared using
1830  * automaton_fragment_clear.
1831  *
1832  * @param start starting state
1833  * @param end end state
1834  *
1835  * @return new NFA fragment
1836  */
1837 static struct GNUNET_REGEX_Automaton *
1838 nfa_fragment_create (struct GNUNET_REGEX_State *start,
1839                      struct GNUNET_REGEX_State *end)
1840 {
1841   struct GNUNET_REGEX_Automaton *n;
1842
1843   n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
1844
1845   n->type = NFA;
1846   n->start = NULL;
1847   n->end = NULL;
1848
1849   if (NULL == start && NULL == end)
1850     return n;
1851
1852   automaton_add_state (n, end);
1853   automaton_add_state (n, start);
1854
1855   n->start = start;
1856   n->end = end;
1857
1858   return n;
1859 }
1860
1861 /**
1862  * Adds a list of states to the given automaton 'n'.
1863  *
1864  * @param n automaton to which the states should be added
1865  * @param states_head head of the DLL of states
1866  * @param states_tail tail of the DLL of states
1867  */
1868 static void
1869 nfa_add_states (struct GNUNET_REGEX_Automaton *n,
1870                 struct GNUNET_REGEX_State *states_head,
1871                 struct GNUNET_REGEX_State *states_tail)
1872 {
1873   struct GNUNET_REGEX_State *s;
1874
1875   if (NULL == n || NULL == states_head)
1876   {
1877     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
1878     return;
1879   }
1880
1881   if (NULL == n->states_head)
1882   {
1883     n->states_head = states_head;
1884     n->states_tail = states_tail;
1885     return;
1886   }
1887
1888   if (NULL != states_head)
1889   {
1890     n->states_tail->next = states_head;
1891     n->states_tail = states_tail;
1892   }
1893
1894   for (s = states_head; NULL != s; s = s->next)
1895     n->state_count++;
1896 }
1897
1898 /**
1899  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
1900  *
1901  * @param ctx context
1902  * @param accepting is it an accepting state or not
1903  *
1904  * @return new NFA state
1905  */
1906 static struct GNUNET_REGEX_State *
1907 nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
1908 {
1909   struct GNUNET_REGEX_State *s;
1910
1911   s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
1912   s->id = ctx->state_id++;
1913   s->accepting = accepting;
1914   s->marked = 0;
1915   s->contained = 0;
1916   s->index = -1;
1917   s->lowlink = -1;
1918   s->scc_id = 0;
1919   s->name = NULL;
1920   GNUNET_asprintf (&s->name, "s%i", s->id);
1921
1922   return s;
1923 }
1924
1925 /**
1926  * Calculates the NFA closure set for the given state.
1927  *
1928  * @param nfa the NFA containing 's'
1929  * @param s starting point state
1930  * @param label transitioning label on which to base the closure on,
1931  *                pass 0 for epsilon transition
1932  *
1933  * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
1934  */
1935 static struct GNUNET_REGEX_StateSet *
1936 nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa,
1937                     struct GNUNET_REGEX_State *s, const char label)
1938 {
1939   struct GNUNET_REGEX_StateSet *cls;
1940   struct GNUNET_REGEX_StateSet *cls_check;
1941   struct GNUNET_REGEX_State *clsstate;
1942   struct GNUNET_REGEX_State *currentstate;
1943   struct Transition *ctran;
1944
1945   if (NULL == s)
1946     return NULL;
1947
1948   cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
1949   cls_check = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
1950
1951   for (clsstate = nfa->states_head; NULL != clsstate; clsstate = clsstate->next)
1952     clsstate->contained = 0;
1953
1954   // Add start state to closure only for epsilon closure
1955   if (0 == label)
1956     GNUNET_array_append (cls->states, cls->len, s);
1957
1958   GNUNET_array_append (cls_check->states, cls_check->len, s);
1959   while (cls_check->len > 0)
1960   {
1961     currentstate = cls_check->states[cls_check->len - 1];
1962     GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
1963
1964     for (ctran = currentstate->transitions_head; NULL != ctran;
1965          ctran = ctran->next)
1966     {
1967       if (NULL != ctran->to_state && label == ctran->label)
1968       {
1969         clsstate = ctran->to_state;
1970
1971         if (NULL != clsstate && 0 == clsstate->contained)
1972         {
1973           GNUNET_array_append (cls->states, cls->len, clsstate);
1974           GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
1975           clsstate->contained = 1;
1976         }
1977       }
1978     }
1979   }
1980   GNUNET_assert (0 == cls_check->len);
1981   GNUNET_free (cls_check);
1982
1983   // sort the states
1984   if (cls->len > 1)
1985     qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *),
1986            state_compare);
1987
1988   return cls;
1989 }
1990
1991 /**
1992  * Calculates the closure set for the given set of states.
1993  *
1994  * @param nfa the NFA containing 's'
1995  * @param states list of states on which to base the closure on
1996  * @param label transitioning label for which to base the closure on,
1997  *                pass 0 for epsilon transition
1998  *
1999  * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
2000  */
2001 static struct GNUNET_REGEX_StateSet *
2002 nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa,
2003                         struct GNUNET_REGEX_StateSet *states, const char label)
2004 {
2005   struct GNUNET_REGEX_State *s;
2006   struct GNUNET_REGEX_StateSet *sset;
2007   struct GNUNET_REGEX_StateSet *cls;
2008   int i;
2009   int j;
2010   int k;
2011   int contains;
2012
2013   if (NULL == states)
2014     return NULL;
2015
2016   cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
2017
2018   for (i = 0; i < states->len; i++)
2019   {
2020     s = states->states[i];
2021     sset = nfa_closure_create (nfa, s, label);
2022
2023     for (j = 0; j < sset->len; j++)
2024     {
2025       contains = 0;
2026       for (k = 0; k < cls->len; k++)
2027       {
2028         if (sset->states[j]->id == cls->states[k]->id)
2029         {
2030           contains = 1;
2031           break;
2032         }
2033       }
2034       if (!contains)
2035         GNUNET_array_append (cls->states, cls->len, sset->states[j]);
2036     }
2037     state_set_clear (sset);
2038   }
2039
2040   if (cls->len > 1)
2041     qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *),
2042            state_compare);
2043
2044   return cls;
2045 }
2046
2047 /**
2048  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
2049  *
2050  * @param ctx context
2051  */
2052 static void
2053 nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
2054 {
2055   struct GNUNET_REGEX_Automaton *a;
2056   struct GNUNET_REGEX_Automaton *b;
2057   struct GNUNET_REGEX_Automaton *new;
2058
2059   b = ctx->stack_tail;
2060   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
2061   a = ctx->stack_tail;
2062   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2063
2064   state_add_transition (ctx, a->end, 0, b->start);
2065   a->end->accepting = 0;
2066   b->end->accepting = 1;
2067
2068   new = nfa_fragment_create (NULL, NULL);
2069   nfa_add_states (new, a->states_head, a->states_tail);
2070   nfa_add_states (new, b->states_head, b->states_tail);
2071   new->start = a->start;
2072   new->end = b->end;
2073   automaton_fragment_clear (a);
2074   automaton_fragment_clear (b);
2075
2076   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
2077 }
2078
2079 /**
2080  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
2081  *
2082  * @param ctx context
2083  */
2084 static void
2085 nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
2086 {
2087   struct GNUNET_REGEX_Automaton *a;
2088   struct GNUNET_REGEX_Automaton *new;
2089   struct GNUNET_REGEX_State *start;
2090   struct GNUNET_REGEX_State *end;
2091
2092   a = ctx->stack_tail;
2093   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2094
2095   if (NULL == a)
2096   {
2097     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2098                 "nfa_add_star_op failed, because there was no element on the stack");
2099     return;
2100   }
2101
2102   start = nfa_state_create (ctx, 0);
2103   end = nfa_state_create (ctx, 1);
2104
2105   state_add_transition (ctx, start, 0, a->start);
2106   state_add_transition (ctx, start, 0, end);
2107   state_add_transition (ctx, a->end, 0, a->start);
2108   state_add_transition (ctx, a->end, 0, end);
2109
2110   a->end->accepting = 0;
2111   end->accepting = 1;
2112
2113   new = nfa_fragment_create (start, end);
2114   nfa_add_states (new, a->states_head, a->states_tail);
2115   automaton_fragment_clear (a);
2116
2117   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
2118 }
2119
2120 /**
2121  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
2122  *
2123  * @param ctx context
2124  */
2125 static void
2126 nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
2127 {
2128   struct GNUNET_REGEX_Automaton *a;
2129
2130   a = ctx->stack_tail;
2131   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2132
2133   state_add_transition (ctx, a->end, 0, a->start);
2134
2135   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
2136 }
2137
2138 /**
2139  * Pops an NFA fragment (a) from the stack and adds a new fragment (a?)
2140  *
2141  * @param ctx context
2142  */
2143 static void
2144 nfa_add_question_op (struct GNUNET_REGEX_Context *ctx)
2145 {
2146   struct GNUNET_REGEX_Automaton *a;
2147   struct GNUNET_REGEX_Automaton *new;
2148   struct GNUNET_REGEX_State *start;
2149   struct GNUNET_REGEX_State *end;
2150
2151   a = ctx->stack_tail;
2152   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2153
2154   if (NULL == a)
2155   {
2156     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2157                 "nfa_add_question_op failed, because there was no element on the stack");
2158     return;
2159   }
2160
2161   start = nfa_state_create (ctx, 0);
2162   end = nfa_state_create (ctx, 1);
2163
2164   state_add_transition (ctx, start, 0, a->start);
2165   state_add_transition (ctx, start, 0, end);
2166   state_add_transition (ctx, a->end, 0, end);
2167
2168   a->end->accepting = 0;
2169
2170   new = nfa_fragment_create (start, end);
2171   nfa_add_states (new, a->states_head, a->states_tail);
2172   automaton_fragment_clear (a);
2173
2174   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
2175 }
2176
2177 /**
2178  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment that
2179  * alternates between a and b (a|b)
2180  *
2181  * @param ctx context
2182  */
2183 static void
2184 nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
2185 {
2186   struct GNUNET_REGEX_Automaton *a;
2187   struct GNUNET_REGEX_Automaton *b;
2188   struct GNUNET_REGEX_Automaton *new;
2189   struct GNUNET_REGEX_State *start;
2190   struct GNUNET_REGEX_State *end;
2191
2192   b = ctx->stack_tail;
2193   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
2194   a = ctx->stack_tail;
2195   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2196
2197   start = nfa_state_create (ctx, 0);
2198   end = nfa_state_create (ctx, 1);
2199   state_add_transition (ctx, start, 0, a->start);
2200   state_add_transition (ctx, start, 0, b->start);
2201
2202   state_add_transition (ctx, a->end, 0, end);
2203   state_add_transition (ctx, b->end, 0, end);
2204
2205   a->end->accepting = 0;
2206   b->end->accepting = 0;
2207   end->accepting = 1;
2208
2209   new = nfa_fragment_create (start, end);
2210   nfa_add_states (new, a->states_head, a->states_tail);
2211   nfa_add_states (new, b->states_head, b->states_tail);
2212   automaton_fragment_clear (a);
2213   automaton_fragment_clear (b);
2214
2215   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
2216 }
2217
2218 /**
2219  * Adds a new nfa fragment to the stack
2220  *
2221  * @param ctx context
2222  * @param lit label for nfa transition
2223  */
2224 static void
2225 nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit)
2226 {
2227   struct GNUNET_REGEX_Automaton *n;
2228   struct GNUNET_REGEX_State *start;
2229   struct GNUNET_REGEX_State *end;
2230
2231   GNUNET_assert (NULL != ctx);
2232
2233   start = nfa_state_create (ctx, 0);
2234   end = nfa_state_create (ctx, 1);
2235   state_add_transition (ctx, start, lit, end);
2236   n = nfa_fragment_create (start, end);
2237   GNUNET_assert (NULL != n);
2238   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
2239 }
2240
2241 /**
2242  * Initialize a new context
2243  *
2244  * @param ctx context
2245  */
2246 static void
2247 GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
2248 {
2249   if (NULL == ctx)
2250   {
2251     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
2252     return;
2253   }
2254   ctx->state_id = 0;
2255   ctx->transition_id = 0;
2256   ctx->stack_head = NULL;
2257   ctx->stack_tail = NULL;
2258 }
2259
2260 /**
2261  * Construct an NFA by parsing the regex string of length 'len'.
2262  *
2263  * @param regex regular expression string
2264  * @param len length of the string
2265  *
2266  * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton
2267  */
2268 struct GNUNET_REGEX_Automaton *
2269 GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
2270 {
2271   struct GNUNET_REGEX_Context ctx;
2272   struct GNUNET_REGEX_Automaton *nfa;
2273   const char *regexp;
2274   char *error_msg;
2275   unsigned int count;
2276   unsigned int altcount;
2277   unsigned int atomcount;
2278   unsigned int pcount;
2279   struct
2280   {
2281     int altcount;
2282     int atomcount;
2283   }     *p;
2284
2285   GNUNET_REGEX_context_init (&ctx);
2286
2287   regexp = regex;
2288   p = NULL;
2289   error_msg = NULL;
2290   altcount = 0;
2291   atomcount = 0;
2292   pcount = 0;
2293
2294   for (count = 0; count < len && *regexp; count++, regexp++)
2295   {
2296     switch (*regexp)
2297     {
2298     case '(':
2299       if (atomcount > 1)
2300       {
2301         --atomcount;
2302         nfa_add_concatenation (&ctx);
2303       }
2304       GNUNET_array_grow (p, pcount, pcount + 1);
2305       p[pcount - 1].altcount = altcount;
2306       p[pcount - 1].atomcount = atomcount;
2307       altcount = 0;
2308       atomcount = 0;
2309       break;
2310     case '|':
2311       if (0 == atomcount)
2312       {
2313         error_msg = "Cannot append '|' to nothing";
2314         goto error;
2315       }
2316       while (--atomcount > 0)
2317         nfa_add_concatenation (&ctx);
2318       altcount++;
2319       break;
2320     case ')':
2321       if (0 == pcount)
2322       {
2323         error_msg = "Missing opening '('";
2324         goto error;
2325       }
2326       if (0 == atomcount)
2327       {
2328         // Ignore this: "()"
2329         pcount--;
2330         altcount = p[pcount].altcount;
2331         atomcount = p[pcount].atomcount;
2332         break;
2333       }
2334       while (--atomcount > 0)
2335         nfa_add_concatenation (&ctx);
2336       for (; altcount > 0; altcount--)
2337         nfa_add_alternation (&ctx);
2338       pcount--;
2339       altcount = p[pcount].altcount;
2340       atomcount = p[pcount].atomcount;
2341       atomcount++;
2342       break;
2343     case '*':
2344       if (atomcount == 0)
2345       {
2346         error_msg = "Cannot append '*' to nothing";
2347         goto error;
2348       }
2349       nfa_add_star_op (&ctx);
2350       break;
2351     case '+':
2352       if (atomcount == 0)
2353       {
2354         error_msg = "Cannot append '+' to nothing";
2355         goto error;
2356       }
2357       nfa_add_plus_op (&ctx);
2358       break;
2359     case '?':
2360       if (atomcount == 0)
2361       {
2362         error_msg = "Cannot append '?' to nothing";
2363         goto error;
2364       }
2365       nfa_add_question_op (&ctx);
2366       break;
2367     case 92:                   /* escape: \ */
2368       regexp++;
2369       count++;
2370     default:
2371       if (atomcount > 1)
2372       {
2373         --atomcount;
2374         nfa_add_concatenation (&ctx);
2375       }
2376       nfa_add_label (&ctx, *regexp);
2377       atomcount++;
2378       break;
2379     }
2380   }
2381   if (0 != pcount)
2382   {
2383     error_msg = "Unbalanced parenthesis";
2384     goto error;
2385   }
2386   while (--atomcount > 0)
2387     nfa_add_concatenation (&ctx);
2388   for (; altcount > 0; altcount--)
2389     nfa_add_alternation (&ctx);
2390
2391   GNUNET_free_non_null (p);
2392
2393   nfa = ctx.stack_tail;
2394   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2395
2396   if (NULL != ctx.stack_head)
2397   {
2398     error_msg = "Creating the NFA failed. NFA stack was not empty!";
2399     goto error;
2400   }
2401
2402   nfa->regex = GNUNET_strdup (regex);
2403
2404   return nfa;
2405
2406 error:
2407   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: %s\n", regex);
2408   if (NULL != error_msg)
2409     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
2410
2411   GNUNET_free_non_null (p);
2412
2413   while (NULL != (nfa = ctx.stack_head))
2414   {
2415     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2416     GNUNET_REGEX_automaton_destroy (nfa);
2417   }
2418
2419   return NULL;
2420 }
2421
2422 /**
2423  * Create DFA states based on given 'nfa' and starting with 'dfa_state'.
2424  *
2425  * @param ctx context.
2426  * @param nfa NFA automaton.
2427  * @param dfa DFA automaton.
2428  * @param dfa_state current dfa state, pass epsilon closure of first nfa state
2429  *                  for starting.
2430  */
2431 static void
2432 construct_dfa_states (struct GNUNET_REGEX_Context *ctx,
2433                       struct GNUNET_REGEX_Automaton *nfa,
2434                       struct GNUNET_REGEX_Automaton *dfa,
2435                       struct GNUNET_REGEX_State *dfa_state)
2436 {
2437   struct Transition *ctran;
2438   struct GNUNET_REGEX_State *state_iter;
2439   struct GNUNET_REGEX_State *new_dfa_state;
2440   struct GNUNET_REGEX_State *state_contains;
2441   struct GNUNET_REGEX_StateSet *tmp;
2442   struct GNUNET_REGEX_StateSet *nfa_set;
2443
2444   for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
2445   {
2446     if (0 == ctran->label || NULL != ctran->to_state)
2447       continue;
2448
2449     tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label);
2450     nfa_set = nfa_closure_set_create (nfa, tmp, 0);
2451     state_set_clear (tmp);
2452     new_dfa_state = dfa_state_create (ctx, nfa_set);
2453     state_contains = NULL;
2454     for (state_iter = dfa->states_head; NULL != state_iter;
2455          state_iter = state_iter->next)
2456     {
2457       if (0 == state_set_compare (state_iter->nfa_set, new_dfa_state->nfa_set))
2458         state_contains = state_iter;
2459     }
2460
2461     if (NULL == state_contains)
2462     {
2463       automaton_add_state (dfa, new_dfa_state);
2464       ctran->to_state = new_dfa_state;
2465       construct_dfa_states (ctx, nfa, dfa, new_dfa_state);
2466     }
2467     else
2468     {
2469       ctran->to_state = state_contains;
2470       automaton_destroy_state (new_dfa_state);
2471     }
2472   }
2473 }
2474
2475 /**
2476  * Construct DFA for the given 'regex' of length 'len'
2477  *
2478  * @param regex regular expression string
2479  * @param len length of the regular expression
2480  *
2481  * @return DFA, needs to be freed using GNUNET_REGEX_destroy_automaton
2482  */
2483 struct GNUNET_REGEX_Automaton *
2484 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len)
2485 {
2486   struct GNUNET_REGEX_Context ctx;
2487   struct GNUNET_REGEX_Automaton *dfa;
2488   struct GNUNET_REGEX_Automaton *nfa;
2489   struct GNUNET_REGEX_StateSet *nfa_set;
2490
2491   GNUNET_REGEX_context_init (&ctx);
2492
2493   // Create NFA
2494   nfa = GNUNET_REGEX_construct_nfa (regex, len);
2495
2496   if (NULL == nfa)
2497   {
2498     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2499                 "Could not create DFA, because NFA creation failed\n");
2500     return NULL;
2501   }
2502
2503   dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
2504   dfa->type = DFA;
2505   dfa->regex = GNUNET_strdup (regex);
2506
2507   // Create DFA start state from epsilon closure
2508   nfa_set = nfa_closure_create (nfa, nfa->start, 0);
2509   dfa->start = dfa_state_create (&ctx, nfa_set);
2510   automaton_add_state (dfa, dfa->start);
2511
2512   construct_dfa_states (&ctx, nfa, dfa, dfa->start);
2513
2514   GNUNET_REGEX_automaton_destroy (nfa);
2515
2516   // Minimize DFA
2517   dfa_minimize (&ctx, dfa);
2518
2519   // Create proofs for all states
2520   automaton_create_proofs (dfa);
2521
2522   return dfa;
2523 }
2524
2525 /**
2526  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton data
2527  * structure.
2528  *
2529  * @param a automaton to be destroyed
2530  */
2531 void
2532 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
2533 {
2534   struct GNUNET_REGEX_State *s;
2535   struct GNUNET_REGEX_State *next_state;
2536
2537   if (NULL == a)
2538     return;
2539
2540   GNUNET_free_non_null (a->regex);
2541   GNUNET_free_non_null (a->canonical_regex);
2542
2543   for (s = a->states_head; NULL != s;)
2544   {
2545     next_state = s->next;
2546     automaton_destroy_state (s);
2547     s = next_state;
2548   }
2549
2550   GNUNET_free (a);
2551 }
2552
2553 /**
2554  * Save a state to an open file pointer. cls is expected to be a file pointer to
2555  * an open file. Used only in conjunction with
2556  * GNUNET_REGEX_automaton_save_graph.
2557  *
2558  * @param cls file pointer.
2559  * @param count current count of the state, not used.
2560  * @param s state.
2561  */
2562 void
2563 GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count,
2564                                         struct GNUNET_REGEX_State *s)
2565 {
2566   FILE *p;
2567   struct Transition *ctran;
2568   char *s_acc = NULL;
2569   char *s_tran = NULL;
2570
2571   p = cls;
2572
2573   if (s->accepting)
2574   {
2575     GNUNET_asprintf (&s_acc,
2576                      "\"%s(%i)\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
2577                      s->name, s->proof_id, s->scc_id);
2578   }
2579   else
2580   {
2581     GNUNET_asprintf (&s_acc, "\"%s(%i)\" [color=\"0.%i 0.8 0.95\"];\n", s->name,
2582                      s->proof_id, s->scc_id);
2583   }
2584
2585   if (NULL == s_acc)
2586   {
2587     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", s->name);
2588     return;
2589   }
2590   fwrite (s_acc, strlen (s_acc), 1, p);
2591   GNUNET_free (s_acc);
2592   s_acc = NULL;
2593
2594   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
2595   {
2596     if (NULL == ctran->to_state)
2597     {
2598       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2599                   "Transition from State %i has no state for transitioning\n",
2600                   s->id);
2601       continue;
2602     }
2603
2604     if (ctran->label == 0)
2605     {
2606       GNUNET_asprintf (&s_tran,
2607                        "\"%s(%i)\" -> \"%s(%i)\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n",
2608                        s->name, s->proof_id, ctran->to_state->name,
2609                        ctran->to_state->proof_id, s->scc_id);
2610     }
2611     else
2612     {
2613       GNUNET_asprintf (&s_tran,
2614                        "\"%s(%i)\" -> \"%s(%i)\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n",
2615                        s->name, s->proof_id, ctran->to_state->name,
2616                        ctran->to_state->proof_id, ctran->label, s->scc_id);
2617     }
2618
2619     if (NULL == s_tran)
2620     {
2621       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n",
2622                   s->name);
2623       return;
2624     }
2625
2626     fwrite (s_tran, strlen (s_tran), 1, p);
2627     GNUNET_free (s_tran);
2628     s_tran = NULL;
2629   }
2630 }
2631
2632 /**
2633  * Save the given automaton as a GraphViz dot file
2634  *
2635  * @param a the automaton to be saved
2636  * @param filename where to save the file
2637  */
2638 void
2639 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
2640                                    const char *filename)
2641 {
2642   char *start;
2643   char *end;
2644   FILE *p;
2645
2646   if (NULL == a)
2647   {
2648     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
2649     return;
2650   }
2651
2652   if (NULL == filename || strlen (filename) < 1)
2653   {
2654     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
2655     return;
2656   }
2657
2658   p = fopen (filename, "w");
2659
2660   if (NULL == p)
2661   {
2662     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
2663                 filename);
2664     return;
2665   }
2666
2667   /* First add the SCCs to the automaton, so we can color them nicely */
2668   scc_tarjan (a);
2669
2670   start = "digraph G {\nrankdir=LR\n";
2671   fwrite (start, strlen (start), 1, p);
2672
2673   automaton_traverse (a, &GNUNET_REGEX_automaton_save_graph_step, p);
2674
2675   end = "\n}\n";
2676   fwrite (end, strlen (end), 1, p);
2677   fclose (p);
2678 }
2679
2680 /**
2681  * Evaluates the given string using the given DFA automaton
2682  *
2683  * @param a automaton, type must be DFA
2684  * @param string string that should be evaluated
2685  *
2686  * @return 0 if string matches, non 0 otherwise
2687  */
2688 static int
2689 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
2690 {
2691   const char *strp;
2692   struct GNUNET_REGEX_State *s;
2693
2694   if (DFA != a->type)
2695   {
2696     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2697                 "Tried to evaluate DFA, but NFA automaton given");
2698     return -1;
2699   }
2700
2701   s = a->start;
2702
2703   // If the string is empty but the starting state is accepting, we accept.
2704   if ((NULL == string || 0 == strlen (string)) && s->accepting)
2705     return 0;
2706
2707   for (strp = string; NULL != strp && *strp; strp++)
2708   {
2709     s = dfa_move (s, *strp);
2710     if (NULL == s)
2711       break;
2712   }
2713
2714   if (NULL != s && s->accepting)
2715     return 0;
2716
2717   return 1;
2718 }
2719
2720 /**
2721  * Evaluates the given string using the given NFA automaton
2722  *
2723  * @param a automaton, type must be NFA
2724  * @param string string that should be evaluated
2725  *
2726  * @return 0 if string matches, non 0 otherwise
2727  */
2728 static int
2729 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
2730 {
2731   const char *strp;
2732   struct GNUNET_REGEX_State *s;
2733   struct GNUNET_REGEX_StateSet *sset;
2734   struct GNUNET_REGEX_StateSet *new_sset;
2735   int i;
2736   int result;
2737
2738   if (NFA != a->type)
2739   {
2740     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2741                 "Tried to evaluate NFA, but DFA automaton given");
2742     return -1;
2743   }
2744
2745   // If the string is empty but the starting state is accepting, we accept.
2746   if ((NULL == string || 0 == strlen (string)) && a->start->accepting)
2747     return 0;
2748
2749   result = 1;
2750   strp = string;
2751   sset = nfa_closure_create (a, a->start, 0);
2752
2753   for (strp = string; NULL != strp && *strp; strp++)
2754   {
2755     new_sset = nfa_closure_set_create (a, sset, *strp);
2756     state_set_clear (sset);
2757     sset = nfa_closure_set_create (a, new_sset, 0);
2758     state_set_clear (new_sset);
2759   }
2760
2761   for (i = 0; i < sset->len; i++)
2762   {
2763     s = sset->states[i];
2764     if (NULL != s && s->accepting)
2765     {
2766       result = 0;
2767       break;
2768     }
2769   }
2770
2771   state_set_clear (sset);
2772   return result;
2773 }
2774
2775 /**
2776  * Evaluates the given 'string' against the given compiled regex
2777  *
2778  * @param a automaton
2779  * @param string string to check
2780  *
2781  * @return 0 if string matches, non 0 otherwise
2782  */
2783 int
2784 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
2785 {
2786   int result;
2787
2788   switch (a->type)
2789   {
2790   case DFA:
2791     result = evaluate_dfa (a, string);
2792     break;
2793   case NFA:
2794     result = evaluate_nfa (a, string);
2795     break;
2796   default:
2797     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2798                 "Evaluating regex failed, automaton has no type!\n");
2799     result = GNUNET_SYSERR;
2800     break;
2801   }
2802
2803   return result;
2804 }
2805
2806
2807 /**
2808  * Get the canonical regex of the given automaton.
2809  * When constructing the automaton a proof is computed for each state,
2810  * consisting of the regular expression leading to this state. A complete
2811  * regex for the automaton can be computed by combining these proofs.
2812  * As of now this function is only useful for testing.
2813  *
2814  * @param a automaton for which the canonical regex should be returned.
2815  *
2816  * @return
2817  */
2818 const char *
2819 GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a)
2820 {
2821   if (NULL == a)
2822     return NULL;
2823
2824   return a->canonical_regex;
2825 }
2826
2827 /**
2828  * Get the first key for the given 'input_string'. This hashes the first x bits
2829  * of the 'input_strings'.
2830  *
2831  * @param input_string string.
2832  * @param string_len length of the 'input_string'.
2833  * @param key pointer to where to write the hash code.
2834  *
2835  * @return number of bits of 'input_string' that have been consumed
2836  *         to construct the key
2837  */
2838 unsigned int
2839 GNUNET_REGEX_get_first_key (const char *input_string, unsigned int string_len,
2840                             struct GNUNET_HashCode *key)
2841 {
2842   unsigned int size;
2843
2844   size = string_len < INITIAL_BITS ? string_len : INITIAL_BITS;
2845
2846   if (NULL == input_string)
2847   {
2848     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n");
2849     return 0;
2850   }
2851
2852   GNUNET_CRYPTO_hash (input_string, size, key);
2853
2854   return size;
2855 }
2856
2857 /**
2858  * Check if the given 'proof' matches the given 'key'.
2859  *
2860  * @param proof partial regex
2861  * @param key hash
2862  *
2863  * @return GNUNET_OK if the proof is valid for the given key
2864  */
2865 int
2866 GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key)
2867 {
2868   return GNUNET_OK;
2869 }
2870
2871 /**
2872  * Iterate over all edges helper function starting from state 's', calling
2873  * iterator on for each edge.
2874  *
2875  * @param s state.
2876  * @param iterator iterator function called for each edge.
2877  * @param iterator_cls closure.
2878  */
2879 static void
2880 iterate_edge (struct GNUNET_REGEX_State *s, GNUNET_REGEX_KeyIterator iterator,
2881               void *iterator_cls)
2882 {
2883   struct Transition *t;
2884   struct GNUNET_REGEX_Edge edges[s->transition_count];
2885   unsigned int num_edges;
2886
2887   if (GNUNET_YES != s->marked)
2888   {
2889     s->marked = GNUNET_YES;
2890
2891     num_edges = state_get_edges (s, edges);
2892
2893     iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, edges);
2894
2895     for (t = s->transitions_head; NULL != t; t = t->next)
2896       iterate_edge (t->to_state, iterator, iterator_cls);
2897   }
2898 }
2899
2900 /**
2901  * Iterate over all edges starting from start state of automaton 'a'. Calling
2902  * iterator for each edge.
2903  *
2904  * @param a automaton.
2905  * @param iterator iterator called for each edge.
2906  * @param iterator_cls closure.
2907  */
2908 void
2909 GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
2910                                 GNUNET_REGEX_KeyIterator iterator,
2911                                 void *iterator_cls)
2912 {
2913   struct GNUNET_REGEX_State *s;
2914
2915   for (s = a->states_head; NULL != s; s = s->next)
2916     s->marked = GNUNET_NO;
2917
2918   iterate_edge (a->start, iterator, iterator_cls);
2919 }