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