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