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, mesh 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 // static void
  64 // space (int n)
  65 // {
  66 //   int i;
  67 //   for (i = 0; i < n; i++)
  68 //     printf ("  ");
  69 // }
  70 //
  71 // static void
  72 // debugctx (struct RegexCombineCtx *ctx, int level)
  73 // {
  74 //   struct RegexCombineCtx *p;
  75 //   space (level);
  76 //   if (NULL != ctx->s)
  77 //     printf ("'%s'\n", ctx->s);
  78 //   else
  79 //     printf ("NULL\n");
  80 //   for (p = ctx->head; NULL != p; p = p->next)
  81 //   {
  82 //     debugctx (p, level + 1);
  83 //   }
  84 // }
  85
  86
  87 /**
  88  * Extract a string from all prefix-combined regexes.
  89  *
  90  * @param ctx Context with 0 or more regexes.
  91  *
  92  * @return Regex that matches any of the added regexes.
  93  */
  94 static char *
  95 regex_combine (struct RegexCombineCtx *ctx)
  96 {
  97   struct RegexCombineCtx *p;
  98   size_t len;
  99   char *regex;
 100   char *tmp;
 101   char *s;
 102   int opt;
 103
 104   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "new combine %s\n", ctx->s);
 105   regex = GNUNET_strdup ("");
 106   opt = GNUNET_NO;
 107   for (p = ctx->head; NULL != p; p = p->next)
 108   {
 109     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding '%s' to innner %s\n", p->s, ctx->s);
 110     s = regex_combine (p);
 111     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  total '%s'\n", s);
 112     if (strlen(s) == 0)
 113       opt = GNUNET_YES;
 114     else
 115     {
 116       GNUNET_asprintf (&tmp, "%s%s|", regex, s);
 117       GNUNET_free_non_null (regex);
 118       regex = tmp;
 119     }
 120     GNUNET_free_non_null (s);
 121     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  so far '%s' for inner %s\n", regex, ctx->s);
 122   }
 123
 124   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "opt: %d, innner: '%s'\n", opt, regex);
 125   len = strlen (regex);
 126   if (0 == len)
 127   {
 128     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "empty, returning ''\n");
 129     GNUNET_free (regex);
 130     return GNUNET_strdup (ctx->s);
 131   }
 132
 133   if ('|' == regex[len - 1])
 134     regex[len - 1] = '\0';
 135
 136   if (NULL != ctx->s)
 137   {
 138     if (opt)
 139       GNUNET_asprintf (&s, "%s[%s]", ctx->s, regex);
 140     else
 141       GNUNET_asprintf (&s, "%s(%s)", ctx->s, regex);
 142     GNUNET_free (regex);
 143     regex = s;
 144   }
 145
 146   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "partial: %s\n", regex);
 147   return regex;
 148 }
 149
 150
 151 /**
 152  * Add a single regex to a context, combining with exisiting regex by-prefix.
 153  *
 154  * @param ctx Context with 0 or more regexes.
 155  * @param regex Regex to add.
 156  */
 157 static void
 158 regex_add (struct RegexCombineCtx *ctx, const char *regex)
 159 {
 160   struct RegexCombineCtx *p;
 161   const char *rest;
 162
 163   rest = &regex[1];
 164   for (p = ctx->head; NULL != p; p = p->next)
 165   {
 166     if (p->s[0] == regex[0])
 167     {
 168       if (1 == strlen(p->s))
 169       {
 170         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "common char %s\n", p->s);
 171         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding %s\n", rest);
 172         regex_add (p, rest);
 173       }
 174       else
 175       {
 176         struct RegexCombineCtx *newctx;
 177         newctx = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 178         newctx->s = GNUNET_strdup (&p->s[1]);
 179         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " p has now %s\n", p->s);
 180         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " p will have %.1s\n", p->s);
 181         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " regex is %s\n", regex);
 182         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new has now %s\n", newctx->s);
 183         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " rest is now %s\n", rest);
 184         p->s[1] = '\0'; /* dont realloc */
 185         GNUNET_CONTAINER_DLL_insert (p->head, p->tail, newctx);
 186         regex_add (p, rest);
 187       }
 188       return;
 189     }
 190   }
 191   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " no  match\n");
 192   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " new state %s\n", regex);
 193   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " under %s\n", ctx->s);
 194   p = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 195   p->s = GNUNET_strdup (regex);
 196   GNUNET_CONTAINER_DLL_insert (ctx->head, ctx->tail, p);
 197 }
 198
 199
 200 /**
 201  * Free all resources used by the context node and all its children.
 202  *
 203  * @param ctx Context to free.
 204  */
 205 static void
 206 regex_ctx_destroy (struct RegexCombineCtx *ctx)
 207 {
 208   struct RegexCombineCtx *p;
 209   struct RegexCombineCtx *next;
 210
 211   for (p = ctx->head; NULL != p; p = next)
 212   {
 213     next = p->next;
 214     regex_ctx_destroy (p);
 215   }
 216   GNUNET_free_non_null (ctx->s); /* 's' on root node is null */
 217   GNUNET_free (ctx);
 218 }
 219
 220
 221 /**
 222  * Return a prefix-combine regex that matches the same strings as
 223  * any of the original regexes.
 224  *
 225  * WARNING: only useful for reading specific regexes for specific applications,
 226  *          namely the gnunet-regex-profiler / gnunet-regex-daemon.
 227  *          This function DOES NOT support arbitrary regex combining.
 228  */
 229 char *
 230 GNUNET_REGEX_combine (char * const regexes[])
 231 {
 232   unsigned int i;
 233   char *combined;
 234   const char *current;
 235   struct RegexCombineCtx *ctx;
 236
 237   ctx = GNUNET_malloc (sizeof (struct RegexCombineCtx));
 238   for (i = 0; regexes[i]; i++)
 239   {
 240     current = regexes[i];
 241     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Regex %u: %s\n", i, current);
 242     regex_add (ctx, current);
 243   }
 244   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\nCombining...\n");
 245   //debugctx (ctx, 0);
 246
 247   combined = regex_combine (ctx);
 248
 249   regex_ctx_destroy (ctx);
 250
 251   return combined;
 252 }
 253
 254
 255 /**
 256  * Read a set of regexes from a file, one per line and return them in an array
 257  * suitable for GNUNET_REGEX_combine.
 258  * The array must be free'd using GNUNET_REGEX_free_from_file.
 259  *
 260  * @param filename Name of the file containing the regexes.
 261  *
 262  * @return A newly allocated, NULL terminated array of regexes.
 263  */
 264 char **
 265 GNUNET_REGEX_read_from_file (const char *filename)
 266 {
 267   struct GNUNET_DISK_FileHandle *f;
 268   unsigned int nr;
 269   unsigned int offset;
 270   uint64_t size;
 271   size_t len;
 272   char *buffer;
 273   char *regex;
 274   char **regexes;
 275
 276   f = GNUNET_DISK_file_open (filename,
 277                              GNUNET_DISK_OPEN_READ,
 278                              GNUNET_DISK_PERM_NONE);
 279   if (NULL == f)
 280   {
 281     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 282                 "Can't open file %s for reading\n", filename);
 283     return NULL;
 284   }
 285   if (GNUNET_OK != GNUNET_DISK_file_handle_size (f, &size))
 286   {
 287     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 288                 "Can't get size of file %s\n", filename);
 289     GNUNET_DISK_file_close (f);
 290     return NULL;
 291   }
 292   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 293               "using file %s, size %llu\n",
 294               filename, (unsigned long long) size);
 295
 296   buffer = GNUNET_malloc (size + 1);
 297   GNUNET_DISK_file_read (f, buffer, size);
 298   GNUNET_DISK_file_close (f);
 299   regexes = GNUNET_malloc (sizeof (char *));
 300   nr = 1;
 301   offset = 0;
 302   regex = NULL;
 303   do
 304   {
 305     if (NULL == regex)
 306       regex = GNUNET_malloc (size + 1);
 307     len = (size_t) sscanf (&buffer[offset], "%s", regex);
 308     if (0 == len)
 309       break;
 310     len = strlen (regex);
 311     offset += len + 1;
 312     if (len < 1)
 313       continue;
 314     if (len < 6 || strncmp (&regex[len - 6], "(0|1)*", 6) != 0)
 315     {
 316       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 317                   "%s (line %u) does not end in \"(0|1)*\"\n",
 318                   buffer, nr);
 319     }
 320     else
 321     {
 322       len -= 6;
 323       regex[len] = '\0';
 324     }
 325     regex = GNUNET_realloc (regex, len + 1);
 326     GNUNET_array_grow (regexes, nr, nr + 1);
 327     GNUNET_assert (NULL == regexes[nr - 2]);
 328     regexes[nr - 2] = regex;
 329     regexes[nr - 1] = NULL;
 330     regex = NULL;
 331   } while (offset < size);
 332   GNUNET_free_non_null (regex);
 333   GNUNET_free (buffer);
 334
 335   return regexes;
 336 }
 337
 338
 339 /**
 340  * Free all memory reserved for a set of regexes created by read_from_file.
 341  *
 342  * @param regexes NULL-terminated array of regexes.
 343  */
 344 void
 345 GNUNET_REGEX_free_from_file (char **regexes)
 346 {
 347   unsigned int i;
 348
 349   for (i = 0; regexes[i]; i++)
 350     GNUNET_free (regexes[i]);
 351   GNUNET_free (regexes);
 352 }
 353
 354 /* end of regex_test_lib.c */