src/regex/regex_test_lib.c

   1 /*
   2  *  This file is part of GNUnet
   3  *  (C) 2012 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18  *  Boston, MA 02111-1307, 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    * Next node with same prefix but different token.
  39    */
  40   struct RegexCombineCtx *next;
  41
  42   /**
  43    * Prev node with same prefix but different token.
  44    */
  45   struct RegexCombineCtx *prev;
  46
  47   /**
  48    * First child node with same prefix and token.
  49    */
  50   struct RegexCombineCtx *head;
  51
  52   /**
  53    * Last child node.
  54    */
  55   struct RegexCombineCtx *tail;
  56
  57   /**
  58    * Token.
  59    */
  60   char *s;
  61 };
  62
  63 /*
  64 static void
  65 space (int n)
  66 {
  67   int i;
  68   for (i = 0; i < n; i++)
  69     printf ("  ");
  70 }
  71
  72 static void
  73 debugctx (struct RegexCombineCtx *ctx, int level)
  74 {
  75   struct RegexCombineCtx *p;
  76   space (level);
  77   if (NULL != ctx->s)
  78     printf ("'%s'\n", ctx->s);
  79   else
  80     printf ("NULL\n");
  81   for (p = ctx->head; NULL != p; p = p->next)
  82   {
  83     debugctx (p, level + 1);
  84   }
  85 }
  86 */
  87
  88 /**
  89  * Extract a string from all prefix-combined regexes.
  90  *
  91  * @param ctx Context with 0 or more regexes.
  92  *
  93  * @return Regex that matches any of the added regexes.
  94  */
  95 static char *
  96 regex_combine (struct RegexCombineCtx *ctx)
  97 {
  98   struct RegexCombineCtx *p;
  99   size_t len;
 100   char *regex;
 101   char *tmp;
 102   char *s;
 103   int opt;
 104
 105   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "new combine %s\n", ctx->s);
 106   regex = GNUNET_strdup ("");
 107   opt = GNUNET_NO;
 108   for (p = ctx->head; NULL != p; p = p->next)
 109   {
 110     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding '%s' to innner %s\n", p->s, ctx->s);
 111     s = regex_combine (p);
 112     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  total '%s'\n", s);
 113     if (strlen(s) == 0)
 114     {
 115       opt = GNUNET_YES;
 116     }
 117     else
 118     {
 119       GNUNET_asprintf (&tmp, "%s%s|", regex, s);
 120       GNUNET_free_non_null (regex);
 121       regex = tmp;
 122     }
 123     GNUNET_free_non_null (s);
 124     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  so far '%s' for inner %s\n", regex, ctx->s);
 125   }
 126
 127   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "opt: %d, innner: '%s'\n", opt, regex);
 128   len = strlen (regex);
 129   if (0 == len)
 130   {
 131     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "empty, returning ''\n");
 132     GNUNET_free (regex);
 133     return NULL == ctx->s ? NULL : GNUNET_strdup (ctx->s);
 134   }
 135
 136   if ('|' == regex[len - 1])
 137     regex[len - 1] = '\0';
 138
 139   if (NULL != ctx->s)
 140   {
 141     if (opt)
 142       GNUNET_asprintf (&s, "%s(%s)?", ctx->s, regex);
 143     else
 144       GNUNET_asprintf (&s, "%s(%s)", ctx->s, regex);
 145     GNUNET_free (regex);
 146     regex = s;
 147   }
 148
 149   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "partial: %s\n", regex);
 150   return regex;
 151 }
 152
 153
 154 /**
 155  * Get the number of matching characters on the prefix of both strings.
 156  *
 157  * @param s1 String 1.
 158  * @param s2 String 2.
 159  *
 160  * @return Number of characters of matching prefix.
 161  */
 162 static unsigned int
 163 get_prefix_length (const char *s1, const char *s2)
 164 {
 165   unsigned int l1;
 166   unsigned int l2;
 167   unsigned int limit;
 168   unsigned int i;
 169
 170   l1 = strlen (s1);
 171   l2 = strlen (s2);
 172   limit = l1 > l2 ? l2 : l1;
 173
 174   for (i = 1; i <= limit; i++)
 175   {
 176     if (0 != strncmp (s1, s2, i))
 177       return i - 1;
 178   }
 179   return limit;
 180 }
 181
 182
 183 /**
 184  * Return the child context with the longest prefix match with the regex.
 185  * Usually only one child will match, search all just in case.
 186  *
 187  * @param ctx Context whose children to search.
 188  * @param regex String to match.
 189  *
 190  * @return Child with the longest prefix, NULL if no child matches.
 191  */
 192 static struct RegexCombineCtx *
 193 get_longest_prefix (struct RegexCombineCtx *ctx, const char *regex)
 194 {
 195   struct RegexCombineCtx *p;
 196   struct RegexCombineCtx *best;
 197   unsigned int l;
 198   unsigned int best_l;
 199
 200   best_l = 0;
 201   best = NULL;
 202   for (p = ctx->head; NULL != p; p = p->next)
 203   {
 204     l = get_prefix_length (p->s, regex);
 205     if (l > best_l)
 206     {
 207       GNUNET_break (0 == best_l);
 208       best = p;
 209       best_l = l;
 210     }
 211   }
 212   return best;
 213 }
 214
 215
 216 /**
 217  * Add a single regex to a context, combining with exisiting regex by-prefix.
 218  *
 219  * @param ctx Context with 0 or more regexes.
 220  * @param regex Regex to add.
 221  */
 222 static void
 223 regex_add (struct RegexCombineCtx *ctx, const char *regex)
 224 {
 225   struct RegexCombineCtx *p;
 226   struct RegexCombineCtx *newctx;
 227   unsigned int prefix_l;
 228   const char *rest_r;
 229   const char *rest_s;
 230   size_t len;
 231
 232   if (0 == strlen (regex))
 233     return;
 234
 235   p = get_longest_prefix (ctx, regex);
 236   if (NULL != p) /* There is some prefix match, reduce regex and try again */
 237   {
 238     prefix_l = get_prefix_length (p->s, regex);
 239     rest_s = &p->s[prefix_l];
 240     rest_r = &regex[prefix_l];
 241     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "chosen '%s' [%u]\n", p->s, prefix_l);
 242     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "prefix r '%.*s'\n", prefix_l, p->s);
 243     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest r '%s'\n", rest_r);
 244     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "rest s '%s'\n", rest_s);
 245     len = strlen (p->s);
 246     if (prefix_l < len) /* only partial match, split existing state */
 247     {
 248       newctx = GNUNET_new (struct RegexCombineCtx);
 249       newctx->head = p->head;
 250       newctx->tail = p->tail;
 251       newctx->s = GNUNET_malloc(len - prefix_l + 1);
 252       strncpy (newctx->s, rest_s, len - prefix_l + 1);
 253
 254       p->head = newctx;
 255       p->tail = newctx;
 256       p->s[prefix_l] = '\0';
 257     }
 258     regex_add (p, rest_r);
 259     return;
 260   }
 261   /* There is no prefix match, add new */
 262   if (NULL == ctx->head && NULL != ctx->s)
 263   {
 264     /* this was the end before, add empty string */
 265     newctx = GNUNET_new (struct RegexCombineCtx);
 266     newctx->s = GNUNET_strdup ("");
 267     GNUNET_CONTAINER_DLL_insert (ctx->head, ctx->tail, newctx);
 268   }
 269   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " no match\n");
 270   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new state %s\n", regex);
 271   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " under %s\n", ctx->s);
 272   newctx = GNUNET_new (struct RegexCombineCtx);
 273   newctx->s = GNUNET_strdup (regex);
 274   GNUNET_CONTAINER_DLL_insert (ctx->head, ctx->tail, newctx);
 275 }
 276
 277
 278 /**
 279  * Free all resources used by the context node and all its children.
 280  *
 281  * @param ctx Context to free.
 282  */
 283 static void
 284 regex_ctx_destroy (struct RegexCombineCtx *ctx)
 285 {
 286   struct RegexCombineCtx *p;
 287   struct RegexCombineCtx *next;
 288
 289   for (p = ctx->head; NULL != p; p = next)
 290   {
 291     next = p->next;
 292     regex_ctx_destroy (p);
 293   }
 294   GNUNET_free_non_null (ctx->s); /* 's' on root node is null */
 295   GNUNET_free (ctx);
 296 }
 297
 298
 299 /**
 300  * Return a prefix-combine regex that matches the same strings as
 301  * any of the original regexes.
 302  *
 303  * WARNING: only useful for reading specific regexes for specific applications,
 304  *          namely the gnunet-regex-profiler / gnunet-regex-daemon.
 305  *          This function DOES NOT support arbitrary regex combining.
 306  */
 307 char *
 308 REGEX_TEST_combine (char * const regexes[])
 309 {
 310   unsigned int i;
 311   char *combined;
 312   const char *current;
 313   struct RegexCombineCtx *ctx;
 314
 315   ctx = GNUNET_new (struct RegexCombineCtx);
 316   for (i = 0; regexes[i]; i++)
 317   {
 318     current = regexes[i];
 319     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex %u: %s\n", i, current);
 320     regex_add (ctx, current);
 321     /* debugctx (ctx, 0); */
 322   }
 323   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\nCombining...\n");
 324   /* debugctx (ctx, 0); */
 325
 326   combined = regex_combine (ctx);
 327
 328   regex_ctx_destroy (ctx);
 329
 330   return combined;
 331 }
 332
 333
 334 /**
 335  * Read a set of regexes from a file, one per line and return them in an array
 336  * suitable for REGEX_TEST_combine.
 337  * The array must be free'd using REGEX_TEST_free_from_file.
 338  *
 339  * @param filename Name of the file containing the regexes.
 340  *
 341  * @return A newly allocated, NULL terminated array of regexes.
 342  */
 343 char **
 344 REGEX_TEST_read_from_file (const char *filename)
 345 {
 346   struct GNUNET_DISK_FileHandle *f;
 347   unsigned int nr;
 348   unsigned int offset;
 349   off_t size;
 350   size_t len;
 351   char *buffer;
 352   char *regex;
 353   char **regexes;
 354
 355   f = GNUNET_DISK_file_open (filename,
 356                              GNUNET_DISK_OPEN_READ,
 357                              GNUNET_DISK_PERM_NONE);
 358   if (NULL == f)
 359   {
 360     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 361                 "Can't open file %s for reading\n", filename);
 362     return NULL;
 363   }
 364   if (GNUNET_OK != GNUNET_DISK_file_handle_size (f, &size))
 365   {
 366     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 367                 "Can't get size of file %s\n", filename);
 368     GNUNET_DISK_file_close (f);
 369     return NULL;
 370   }
 371   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 372               "using file %s, size %llu\n",
 373               filename, (unsigned long long) size);
 374
 375   buffer = GNUNET_malloc (size + 1);
 376   GNUNET_DISK_file_read (f, buffer, size);
 377   GNUNET_DISK_file_close (f);
 378   regexes = GNUNET_malloc (sizeof (char *));
 379   nr = 1;
 380   offset = 0;
 381   regex = NULL;
 382   do
 383   {
 384     if (NULL == regex)
 385       regex = GNUNET_malloc (size + 1);
 386     len = (size_t) sscanf (&buffer[offset], "%s", regex);
 387     if (0 == len)
 388       break;
 389     len = strlen (regex);
 390     offset += len + 1;
 391     if (len < 1)
 392       continue;
 393     regex[len] = '\0';
 394     regex = GNUNET_realloc (regex, len + 1);
 395     GNUNET_array_grow (regexes, nr, nr + 1);
 396     GNUNET_assert (NULL == regexes[nr - 2]);
 397     regexes[nr - 2] = regex;
 398     regexes[nr - 1] = NULL;
 399     regex = NULL;
 400   } while (offset < size);
 401   GNUNET_free_non_null (regex);
 402   GNUNET_free (buffer);
 403
 404   return regexes;
 405 }
 406
 407
 408 /**
 409  * Free all memory reserved for a set of regexes created by read_from_file.
 410  *
 411  * @param regexes NULL-terminated array of regexes.
 412  */
 413 void
 414 REGEX_TEST_free_from_file (char **regexes)
 415 {
 416   unsigned int i;
 417
 418   for (i = 0; regexes[i]; i++)
 419     GNUNET_free (regexes[i]);
 420   GNUNET_free (regexes);
 421 }
 422
 423 /* end of regex_test_lib.c */