src/regex/regex_test_lib.c

   1 /*
   2  *  This file is part of GNUnet
   3  *  Copyright (C) 2012-2017 GNUnet e.V.
   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., 51 Franklin Street, Fifth Floor,
  18  *  Boston, MA 02110-1301, USA.
  19  */
  20 /**
  21  * @file src/regex/regex_test_lib.c
  22  * @brief library to read regexes representing IP networks from a file.
  23  *        and simplyfinying the into one big regex, in order to run
  24  *        tests (regex performance, cadet profiler).
  25  * @author Bartlomiej Polot
  26  */
  27
  28 #include "platform.h"
  29 #include "gnunet_util_lib.h"
  30
  31
  32 /**
  33  * Struct to hold the tree formed by prefix-combining the regexes.
  34  */
  35 struct RegexCombineCtx
  36 {
  37   /**
  38    * Child nodes with same prefix and token.
  39    */
  40   struct RegexCombineCtx **children;
  41
  42   /**
  43    * Alphabet size (how many @a children there are)
  44    */
  45   unsigned int size;
  46
  47   /**
  48    * Token.
  49    */
  50   char *s;
  51 };
  52
  53
  54 /**
  55  * Char 2 int
  56  *
  57  * Convert a character into its int value depending on the base used
  58  *
  59  * @param c Char
  60  * @param size base (2, 8 or 16(hex))
  61  *
  62  * @return Int in range [0, (base-1)]
  63  */
  64 static int
  65 c2i (char c, int size)
  66 {
  67   switch (size)
  68   {
  69     case 2:
  70     case 8:
  71       return c - '0';
  72       break;
  73     case 16:
  74       if (c >= '0' && c <= '9')
  75         return c - '0';
  76       else if (c >= 'A' && c <= 'F')
  77         return c - 'A' + 10;
  78       else if (c >= 'a' && c <= 'f')
  79         return c - 'a' + 10;
  80       else
  81       {
  82         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
  83                     "Cannot convert char %c in base %u\n",
  84                     c, size);
  85         GNUNET_assert (0);
  86       }
  87       break;
  88     default:
  89       GNUNET_assert (0);
  90   }
  91 }
  92
  93
  94 /**
  95  * Printf spaces to indent the regex tree
  96  *
  97  * @param n Indentation level
  98  */
  99 static void
 100 space (int n)
 101 {
 102   for (int i = 0; i < n; i++)
 103     fprintf (stderr, "| ");
 104 }
 105
 106
 107 /**
 108  * Printf the combined regex ctx.
 109  *
 110  * @param ctx The ctx to printf
 111  * @param level Indentation level to start with
 112  */
 113 static void
 114 debugctx (struct RegexCombineCtx *ctx, int level)
 115 {
 116 #if DEBUG_REGEX
 117   if (NULL != ctx->s)
 118   {
 119     space (level - 1);
 120     fprintf (stderr, "%u:'%s'\n", c2i(ctx->s[0], ctx->size), ctx->s);
 121   }
 122   else
 123     fprintf (stderr, "ROOT (base %u)\n", ctx->size);
 124   for (unsigned int i = 0; i < ctx->size; i++)
 125   {
 126     if (NULL != ctx->children[i])
 127     {
 128       space (level);
 129       debugctx (ctx->children[i], level + 1);
 130     }
 131   }
 132   fflush(stderr);
 133 #endif
 134 }
 135
 136
 137 /**
 138  * Add a single regex to a context, combining with exisiting regex by-prefix.
 139  *
 140  * @param ctx Context with 0 or more regexes.
 141  * @param regex Regex to add.
 142  */
 143 static void
 144 regex_add (struct RegexCombineCtx *ctx,
 145            const char *regex);
 146
 147
 148 /**
 149  * Create and initialize a new RegexCombineCtx.
 150  *
 151  * @param alphabet_size Size of the alphabet (and the Trie array)
 152  */
 153 static struct RegexCombineCtx *
 154 new_regex_ctx (unsigned int alphabet_size)
 155 {
 156   struct RegexCombineCtx *ctx;
 157   size_t array_size;
 158
 159   array_size = sizeof(struct RegexCombineCtx *) * alphabet_size;
 160   ctx = GNUNET_new (struct RegexCombineCtx);
 161   ctx->children = GNUNET_malloc (array_size);
 162   ctx->size = alphabet_size;
 163
 164   return ctx;
 165 }
 166
 167
 168 static void
 169 move_children (struct RegexCombineCtx *dst,
 170                const struct RegexCombineCtx *src)
 171 {
 172   size_t array_size;
 173
 174   array_size = sizeof(struct RegexCombineCtx *) * src->size;
 175   GNUNET_memcpy (dst->children,
 176                  src->children,
 177                  array_size);
 178   for (unsigned int i = 0; i < src->size; i++)
 179   {
 180     src->children[i] = NULL;
 181   }
 182 }
 183
 184
 185 /**
 186  * Extract a string from all prefix-combined regexes.
 187  *
 188  * @param ctx Context with 0 or more regexes.
 189  *
 190  * @return Regex that matches any of the added regexes.
 191  */
 192 static char *
 193 regex_combine (struct RegexCombineCtx *ctx)
 194 {
 195   struct RegexCombineCtx *p;
 196   unsigned int i;
 197   size_t len;
 198   char *regex;
 199   char *tmp;
 200   char *s;
 201   int opt;
 202
 203   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "new combine %s\n", ctx->s);
 204   regex = GNUNET_strdup ("");
 205   opt = GNUNET_NO;
 206   for (i = 0; i < ctx->size; i++)
 207   {
 208     p = ctx->children[i];
 209     if (NULL == p)
 210       continue;
 211     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 212                 "adding '%s' to innner %s\n",
 213                 p->s, ctx->s);
 214     s = regex_combine (p);
 215     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  total '%s'\n", s);
 216     if (strlen(s) == 0)
 217     {
 218       opt = GNUNET_YES;
 219     }
 220     else
 221     {
 222       GNUNET_asprintf (&tmp, "%s%s|", regex, s);
 223       GNUNET_free_non_null (regex);
 224       regex = tmp;
 225     }
 226     GNUNET_free_non_null (s);
 227     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  so far '%s' for inner %s\n", regex, ctx->s);
 228   }
 229
 230   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "opt: %d, innner: '%s'\n", opt, regex);
 231   len = strlen (regex);
 232   if (0 == len)
 233   {
 234     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "empty, returning ''\n");
 235     GNUNET_free (regex);
 236     return NULL == ctx->s ? NULL : GNUNET_strdup (ctx->s);
 237   }
 238
 239   if ('|' == regex[len - 1])
 240     regex[len - 1] = '\0';
 241
 242   if (NULL != ctx->s)
 243   {
 244     if (opt)
 245       GNUNET_asprintf (&s, "%s(%s)?", ctx->s, regex);
 246     else
 247       GNUNET_asprintf (&s, "%s(%s)", ctx->s, regex);
 248     GNUNET_free (regex);
 249     regex = s;
 250   }
 251
 252   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "partial: %s\n", regex);
 253   return regex;
 254 }
 255
 256
 257 /**
 258  * Get the number of matching characters on the prefix of both strings.
 259  *
 260  * @param s1 String 1.
 261  * @param s2 String 2.
 262  *
 263  * @return Number of characters of matching prefix.
 264  */
 265 static unsigned int
 266 get_prefix_length (const char *s1, const char *s2)
 267 {
 268   unsigned int l1;
 269   unsigned int l2;
 270   unsigned int limit;
 271   unsigned int i;
 272
 273   l1 = strlen (s1);
 274   l2 = strlen (s2);
 275   limit = l1 > l2 ? l2 : l1;
 276
 277   for (i = 0; i < limit; i++)
 278   {
 279     if (s1[i] != s2[i])
 280       return i;
 281   }
 282   return limit;
 283 }
 284
 285
 286 /**
 287  * Return the child context with the longest prefix match with the regex.
 288  * Usually only one child will match, search all just in case.
 289  *
 290  * @param ctx Context whose children to search.
 291  * @param regex String to match.
 292  *
 293  * @return Child with the longest prefix, NULL if no child matches.
 294  */
 295 static struct RegexCombineCtx *
 296 get_longest_prefix (struct RegexCombineCtx *ctx, const char *regex)
 297 {
 298   struct RegexCombineCtx *p;
 299   struct RegexCombineCtx *best;
 300   unsigned int i;
 301   unsigned int l;
 302   unsigned int best_l;
 303
 304   best_l = 0;
 305   best = NULL;
 306
 307   for (i = 0; i < ctx->size; i++)
 308   {
 309     p = ctx->children[i];
 310     if (NULL == p)
 311       continue;
 312
 313     l = get_prefix_length (p->s, regex);
 314     if (l > best_l)
 315     {
 316       GNUNET_break (0 == best_l);
 317       best = p;
 318       best_l = l;
 319     }
 320   }
 321   return best;
 322 }
 323
 324 static void
 325 regex_add_multiple (struct RegexCombineCtx *ctx,
 326                     const char *regex,
 327                     struct RegexCombineCtx **children)
 328 {
 329   char tmp[2];
 330   long unsigned int i;
 331   size_t l;
 332   struct RegexCombineCtx *newctx;
 333   unsigned int count;
 334
 335   if ('(' != regex[0])
 336   {
 337     GNUNET_assert (0);
 338   }
 339
 340   /* Does the regex cover *all* possible children? Then don't add any,
 341    * as it will be covered by the post-regex "(a-z)*"
 342    */
 343   l = strlen (regex);
 344   count = 0;
 345   for (i = 1UL; i < l; i++)
 346   {
 347     if (regex[i] != '|' && regex[i] != ')')
 348     {
 349       count++;
 350     }
 351   }
 352   if (count == ctx->size)
 353   {
 354     return;
 355   }
 356
 357   /* Add every component as a child node */
 358   tmp[1] = '\0';
 359   for (i = 1UL; i < l; i++)
 360   {
 361     if (regex[i] != '|' && regex[i] != ')')
 362     {
 363       tmp[0] = regex[i];
 364       newctx = new_regex_ctx(ctx->size);
 365       newctx->s = GNUNET_strdup (tmp);
 366       if (children != NULL)
 367         GNUNET_memcpy (newctx->children,
 368                        children,
 369                        sizeof (*children) * ctx->size);
 370       ctx->children[c2i(tmp[0], ctx->size)] = newctx;
 371     }
 372   }
 373 }
 374
 375 /**
 376  * Add a single regex to a context, splitting the exisiting state.
 377  *
 378  * We only had a partial match, split existing state, truncate the current node
 379  * so it only contains the prefix, add suffix(es) as children.
 380  *
 381  * @param ctx Context to split.
 382  * @param len Lenght of ctx->s
 383  * @param prefix_l Lenght of common prefix of the new regex and @a ctx->s
 384  */
 385 static void
 386 regex_split (struct RegexCombineCtx *ctx,
 387              unsigned int len,
 388              unsigned int prefix_l)
 389 {
 390   struct RegexCombineCtx *newctx;
 391   unsigned int idx;
 392   char *suffix;
 393
 394   suffix = GNUNET_malloc (len - prefix_l + 1);
 395   strncpy (suffix, &ctx->s[prefix_l], len - prefix_l + 1);
 396
 397   /* Suffix saved, truncate current node so it only contains the prefix,
 398    * copy any children nodes to put as grandchildren and initialize new empty
 399    * children array.
 400    */
 401   ctx->s[prefix_l] = '\0';
 402
 403   /* If the suffix is an OR expression, add multiple children */
 404   if ('(' == suffix[0])
 405   {
 406     struct RegexCombineCtx **tmp;
 407
 408     tmp = ctx->children;
 409     ctx->children = GNUNET_malloc (sizeof(*tmp) * ctx->size);
 410     regex_add_multiple (ctx, suffix, tmp);
 411     GNUNET_free (suffix);
 412     GNUNET_free (tmp);
 413     return;
 414   }
 415
 416   /* The suffix is a normal string, add as one node */
 417   newctx = new_regex_ctx (ctx->size);
 418   newctx->s = suffix;
 419   move_children (newctx, ctx);
 420   idx = c2i(suffix[0], ctx->size);
 421   ctx->children[idx] = newctx;
 422 }
 423
 424
 425 /**
 426  * Add a single regex to a context, combining with exisiting regex by-prefix.
 427  *
 428  * @param ctx Context with 0 or more regexes.
 429  * @param regex Regex to add.
 430  */
 431 static void
 432 regex_add (struct RegexCombineCtx *ctx, const char *regex)
 433 {
 434   struct RegexCombineCtx *p;
 435   struct RegexCombineCtx *newctx;
 436   long unsigned int l;
 437   unsigned int prefix_l;
 438   const char *rest_r;
 439   const char *rest_s;
 440   size_t len;
 441   int idx;
 442
 443   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 444               "regex_add '%s' into '%s'\n",
 445               regex, ctx->s);
 446   l = strlen (regex);
 447   if (0UL == l)
 448     return;
 449
 450   /* If the regex is in the form of (a|b|c), add every character separately */
 451   if ('(' == regex[0])
 452   {
 453     regex_add_multiple (ctx, regex, NULL);
 454     return;
 455   }
 456
 457   p = get_longest_prefix (ctx, regex);
 458   if (NULL != p)
 459   {
 460     /* There is some prefix match, reduce regex and try again */
 461     prefix_l = get_prefix_length (p->s, regex);
 462     rest_s = &p->s[prefix_l];
 463     rest_r = &regex[prefix_l];
 464     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "chosen '%s' [%u]\n", p->s, prefix_l);
 465     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "prefix r '%.*s'\n", prefix_l, p->s);
 466     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest r '%s'\n", rest_r);
 467     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest s '%s'\n", rest_s);
 468     len = strlen (p->s);
 469     if (prefix_l < len)
 470     {
 471       regex_split (p, len, prefix_l);
 472     }
 473     regex_add (p, rest_r);
 474     return;
 475   }
 476
 477   /* There is no prefix match, add new */
 478   idx = c2i(regex[0], ctx->size);
 479   if (NULL == ctx->children[idx] && NULL != ctx->s)
 480   {
 481     /* this was the end before, add empty string */
 482     newctx = new_regex_ctx (ctx->size);
 483     newctx->s = GNUNET_strdup ("");
 484     ctx->children[idx] = newctx;
 485   }
 486   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " no match\n");
 487   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new state %s\n", regex);
 488   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " under %s\n", ctx->s);
 489   newctx = new_regex_ctx(ctx->size);
 490   newctx->s = GNUNET_strdup (regex);
 491   ctx->children[idx] = newctx;
 492 }
 493
 494
 495 /**
 496  * Free all resources used by the context node and all its children.
 497  *
 498  * @param ctx Context to free.
 499  */
 500 static void
 501 regex_ctx_destroy (struct RegexCombineCtx *ctx)
 502 {
 503   unsigned int i;
 504
 505   if (NULL == ctx)
 506     return;
 507
 508   for (i = 0; i < ctx->size; i++)
 509   {
 510     regex_ctx_destroy (ctx->children[i]);
 511   }
 512   GNUNET_free_non_null (ctx->s); /* 's' on root node is null */
 513   GNUNET_free (ctx->children);
 514   GNUNET_free (ctx);
 515 }
 516
 517
 518 /**
 519  * Combine an array of regexes into a single prefix-shared regex.
 520  * Returns a prefix-combine regex that matches the same strings as
 521  * any of the original regexes.
 522  *
 523  * WARNING: only useful for reading specific regexes for specific applications,
 524  *          namely the gnunet-regex-profiler / gnunet-regex-daemon.
 525  *          This function DOES NOT support arbitrary regex combining.
 526  *
 527  * @param regexes A NULL-terminated array of regexes.
 528  * @param alphabet_size Size of the alphabet the regex uses.
 529  *
 530  * @return A string with a single regex that matches any of the original regexes
 531  */
 532 char *
 533 REGEX_TEST_combine (char * const regexes[], unsigned int alphabet_size)
 534 {
 535   unsigned int i;
 536   char *combined;
 537   const char *current;
 538   struct RegexCombineCtx *ctx;
 539
 540   ctx = new_regex_ctx (alphabet_size);
 541   for (i = 0; regexes[i]; i++)
 542   {
 543     current = regexes[i];
 544     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex %u: %s\n", i, current);
 545     regex_add (ctx, current);
 546     debugctx (ctx, 0);
 547   }
 548   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\nCombining...\n");
 549   debugctx (ctx, 0);
 550
 551   combined = regex_combine (ctx);
 552
 553   regex_ctx_destroy (ctx);
 554
 555   return combined;
 556 }
 557
 558
 559 /**
 560  * Read a set of regexes from a file, one per line and return them in an array
 561  * suitable for REGEX_TEST_combine.
 562  * The array must be free'd using REGEX_TEST_free_from_file.
 563  *
 564  * @param filename Name of the file containing the regexes.
 565  *
 566  * @return A newly allocated, NULL terminated array of regexes.
 567  */
 568 char **
 569 REGEX_TEST_read_from_file (const char *filename)
 570 {
 571   struct GNUNET_DISK_FileHandle *f;
 572   unsigned int nr;
 573   unsigned int offset;
 574   off_t size;
 575   size_t len;
 576   char *buffer;
 577   char *regex;
 578   char **regexes;
 579
 580   f = GNUNET_DISK_file_open (filename,
 581                              GNUNET_DISK_OPEN_READ,
 582                              GNUNET_DISK_PERM_NONE);
 583   if (NULL == f)
 584   {
 585     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 586                 "Can't open file %s for reading\n", filename);
 587     return NULL;
 588   }
 589   if (GNUNET_OK != GNUNET_DISK_file_handle_size (f, &size))
 590   {
 591     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 592                 "Can't get size of file %s\n", filename);
 593     GNUNET_DISK_file_close (f);
 594     return NULL;
 595   }
 596   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 597               "using file %s, size %llu\n",
 598               filename, (unsigned long long) size);
 599
 600   buffer = GNUNET_malloc (size + 1);
 601   GNUNET_DISK_file_read (f, buffer, size);
 602   GNUNET_DISK_file_close (f);
 603   regexes = GNUNET_malloc (sizeof (char *));
 604   nr = 1;
 605   offset = 0;
 606   regex = NULL;
 607   do
 608   {
 609     if (NULL == regex)
 610       regex = GNUNET_malloc (size + 1);
 611     len = (size_t) sscanf (&buffer[offset], "%s", regex);
 612     if (0 == len)
 613       break;
 614     len = strlen (regex);
 615     offset += len + 1;
 616     if (len < 1)
 617       continue;
 618     regex[len] = '\0';
 619     regex = GNUNET_realloc (regex, len + 1);
 620     GNUNET_array_grow (regexes, nr, nr + 1);
 621     GNUNET_assert (NULL == regexes[nr - 2]);
 622     regexes[nr - 2] = regex;
 623     regexes[nr - 1] = NULL;
 624     regex = NULL;
 625   } while (offset < size);
 626   GNUNET_free_non_null (regex);
 627   GNUNET_free (buffer);
 628
 629   return regexes;
 630 }
 631
 632
 633 /**
 634  * Free all memory reserved for a set of regexes created by read_from_file.
 635  *
 636  * @param regexes NULL-terminated array of regexes.
 637  */
 638 void
 639 REGEX_TEST_free_from_file (char **regexes)
 640 {
 641   unsigned int i;
 642
 643   for (i = 0; regexes[i]; i++)
 644     GNUNET_free (regexes[i]);
 645   GNUNET_free (regexes);
 646 }
 647
 648 /* end of regex_test_lib.c */