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