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