test/declgen.c

   1 /*
   2  *  Generate random C declarations for testing.
   3  *  Copyright © 2011 Nick Bowler
   4  *
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <config.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <errno.h>
  24 #include <assert.h>
  25 #include <stdbool.h>
  26 #include <gsl/gsl_rng.h>
  27
  28 #include "declgen.h"
  29 #include "cdecl.h"
  30 #include "test.h"
  31
  32 struct gen_rng {
  33         gsl_rng *rng;
  34 };
  35
  36 /*
  37  * Generate a random identifier.  We arbitrarily pick 10 as the largest
  38  * possible.  Avoid generating keywords, including the English ones, by
  39  * excluding the letters t, o, a and n.  Reserved words are OK.
  40  */
  41 char *gen_identifier(struct gen_rng *rng)
  42 {
  43         static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  44         char *str;
  45         size_t n;
  46
  47         n = gsl_rng_uniform_int(rng->rng, 10)+1;
  48         str = malloc_nofail(n+1);
  49
  50         /* Exclude 10 digits from the first character. */
  51         str[0] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid - 10)];
  52         for (size_t i = 1; i < n; i++)
  53                 str[i] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid)];
  54         str[n] = 0;
  55
  56         return str;
  57 }
  58
  59 /*
  60  * Generate random qualifiers.  Qualifiers can appear multiple times, so the
  61  * list is (potentially) unbounded.  We handle the potential unboundedness by
  62  * generating a list of n qualifiers with probability 1/2^(n+1).  Each
  63  * qualifier is chosen uniformly at random from the set of possibilities:
  64  * const, volatile and, if restrictqual is true, restrict.
  65  */
  66 struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual)
  67 {
  68         struct cdecl_declspec *s = NULL, *p;
  69
  70         while (gsl_rng_uniform(rng->rng) < 0.5) {
  71                 p = s;
  72                 s = malloc_nofail(sizeof *s);
  73                 *s = (struct cdecl_declspec) {
  74                         .next = p,
  75                 };
  76
  77                 switch (gsl_rng_uniform_int(rng->rng, 2+restrictqual)) {
  78                 case 0:
  79                         s->type = CDECL_QUAL_CONST;
  80                         break;
  81                 case 1:
  82                         s->type = CDECL_QUAL_VOLATILE;
  83                         break;
  84                 case 2: /* Only if restrictqual is true. */
  85                         s->type = CDECL_QUAL_RESTRICT;
  86                         break;
  87                 default:
  88                         assert(0);
  89                 }
  90         }
  91
  92         return s;
  93 }
  94
  95 /*
  96  * Generate random function specifiers.  Like qualifiers, function specifiers
  97  * can appear multiple times.
  98  */
  99 struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng)
 100 {
 101         struct cdecl_declspec *s = NULL, *p;
 102
 103         while (gsl_rng_uniform(rng->rng) < 0.5) {
 104                 p = s;
 105                 s = malloc_nofail(sizeof *s);
 106
 107                 *s = (struct cdecl_declspec) {
 108                         .type = CDECL_FUNC_INLINE,
 109                         .next = p,
 110                 };
 111         }
 112
 113         return s;
 114 }
 115
 116 /*
 117  * Generate zero or one random storage-class specifier.  If registeronly is
 118  * true, then the only possible storage-class specifier is "register".
 119  * Otherwise, a specifier type will be selected uniformly at random.
 120  */
 121 struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly)
 122 {
 123         struct cdecl_declspec *s;
 124
 125         if (gsl_rng_uniform(rng->rng) < 0.5)
 126                 return NULL;
 127
 128         s = malloc_nofail(sizeof *s);
 129         *s = (struct cdecl_declspec) {
 130                 .type = CDECL_STOR_REGISTER,
 131         };
 132
 133         if (registeronly)
 134                 return s;
 135
 136         switch (gsl_rng_uniform_int(rng->rng, 5)) {
 137         case 0: s->type = CDECL_STOR_TYPEDEF;  break;
 138         case 1: s->type = CDECL_STOR_REGISTER; break;
 139         case 2: s->type = CDECL_STOR_STATIC;   break;
 140         case 3: s->type = CDECL_STOR_AUTO;     break;
 141         case 4: s->type = CDECL_STOR_EXTERN;   break;
 142         default: assert(0);
 143         }
 144
 145         return s;
 146 }
 147
 148 /*
 149  * Generate random type specifiers.  There is a short list of valid
 150  * combinations, from which we can select one uniformly at random.
 151  */
 152 static const unsigned long total_types;
 153 static struct cdecl_declspec *gen_raw_typespecs(struct gen_rng *rng)
 154 {
 155         switch (gsl_rng_uniform_int(rng->rng, total_types)) {
 156 #       include "typegen.h"
 157         }
 158 }
 159 static const unsigned long total_types = TOTAL_TYPES;
 160
 161 struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype)
 162 {
 163         struct cdecl_declspec *specs;
 164
 165 retry:
 166         specs = gen_raw_typespecs(rng);
 167
 168         switch (specs->type) {
 169         /* void is not always valid, so we might need to pick again. */
 170         case CDECL_TYPE_VOID:
 171                 if (!voidtype)
 172                         goto retry;
 173                 break;
 174         /* A few kinds of type specifiers need identifiers to go with them. */
 175         case CDECL_TYPE_STRUCT:
 176         case CDECL_TYPE_UNION:
 177         case CDECL_TYPE_ENUM:
 178         case CDECL_TYPE_IDENT:
 179                 assert(!specs->next);
 180                 specs->ident = gen_identifier(rng);
 181         }
 182
 183         return specs;
 184 }
 185
 186 struct cdecl_declspec *
 187 gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs)
 188 {
 189         struct cdecl_declspec **p;
 190         size_t n = 0;
 191
 192         if (!specs)
 193                 return specs;
 194
 195         for (struct cdecl_declspec *s = specs; s; s = s->next)
 196                 n++;
 197
 198         p = malloc_nofail((n+1) * sizeof *p);
 199
 200         /* Build a temporary array for easy element swapping. */
 201         p[0] = specs;
 202         p[n] = NULL;
 203         for (size_t i = 1; i < n; i++)
 204                 p[i] = p[i-1]->next;
 205
 206         /* Knuth shuffle. */
 207         for (size_t i = 0; i < n; i++) {
 208                 struct cdecl_declspec *tmp;
 209                 size_t r;
 210
 211                 r = gsl_rng_uniform_int(rng->rng, n-i);
 212                 tmp = p[i];
 213                 p[i] = p[r+i];
 214                 p[r+i] = tmp;
 215         }
 216
 217         /* Fix up the pointers. */
 218         for (size_t i = 1; i <= n; i++)
 219                 p[i-1]->next = p[i];
 220         specs = p[0];
 221
 222         free(p);
 223         return specs;
 224 }
 225
 226 /*
 227  * Generate random declaration specifiers.  This consists of random qualifiers
 228  * and type specifiers, as described in the functions above, plus up to one
 229  * storage-class specifier and zero or more function specifiers.
 230  *
 231  * The flags parameter controls what sort of specifiers can be generated in
 232  * order to handle various special cases in the C language.  It is the
 233  * bitwise-or of zero or more values, which have the following meanings:
 234  *
 235  *   GEN_NO_FUNCTION: Do not generate any function specifiers at all.
 236  *   GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
 237  *   GEN_NO_VOID: Do not generate the "void" type specifier.
 238  *   GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
 239  *                      "register".
 240  *
 241  * Notwithstanding any of the above, the "restrict" type qualifier will never
 242  * be generated by this function: use gen_qualifiers directly.
 243  */
 244 struct cdecl_declspec *
 245 gen_declspecs(struct gen_rng *rng, unsigned flags)
 246 {
 247         struct cdecl_declspec *s, *p;
 248
 249         s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
 250         for (p = s; p->next;)
 251                 p = p->next;
 252
 253         if (~flags & GEN_NO_FUNCTION)
 254                 p->next = gen_funcspecs(rng);
 255         for (p = s; p->next;)
 256                 p = p->next;
 257
 258         if (~flags & GEN_NO_STORAGE)
 259                 p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
 260         for (p = s; p->next;)
 261                 p = p->next;
 262
 263         p->next = gen_qualifiers(rng, false);
 264         return gen_randomize_specs(rng, s);
 265 }
 266
 267 /*
 268  * Generate a random array declarator, selecting one of four possibilities
 269  * uniformly at random.
 270  */
 271 static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
 272 {
 273         d->type = CDECL_DECL_ARRAY;
 274         d->u.array = (struct cdecl_array){0};
 275
 276         switch (gsl_rng_uniform_int(rng->rng, 4)) {
 277         case '0':
 278                 d->u.array.vla = malloc_nofail(1);
 279                 d->u.array.vla[0] = 0;
 280                 break;
 281         case '1':
 282                 d->u.array.vla = gen_identifier(rng);
 283                 break;
 284         case '2':
 285                 d->u.array.length = 0;
 286                 break;
 287         case '3':
 288                 d->u.array.length = gsl_rng_uniform_int(rng->rng, -1);
 289                 break;
 290         }
 291 }
 292
 293 /* Generate a function declarator. */
 294 static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
 295 {
 296         d->type = CDECL_DECL_FUNCTION;
 297         d->u.function.parameters = NULL;
 298
 299         while (gsl_rng_uniform(rng->rng) < 0.5) {
 300                 unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
 301                 struct cdecl *param;
 302
 303                 param = malloc_nofail(sizeof *param);
 304                 *param = (struct cdecl) {
 305                         .next = d->u.function.parameters,
 306                         .declarators = gen_declarators(rng),
 307                 };
 308
 309                 if (param->declarators->type != CDECL_DECL_POINTER
 310                     && param->declarators->type != CDECL_DECL_FUNCTION)
 311                         flags |= GEN_NO_VOID;
 312
 313                 param->specifiers = gen_declspecs(rng, flags);
 314                 d->u.function.parameters = param;
 315         }
 316
 317         if (d->u.function.parameters) {
 318                 d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
 319         }
 320 }
 321
 322 /*
 323  * Generate a random chain of declarators.  Like qualifiers above, a chain of
 324  * length N has probability 1/2^(N+1) of occurring.  All declarator chains
 325  * are ultimately terminated by either a null declarator or an identifier,
 326  * selected uniformly at random.
 327  */
 328 struct cdecl_declarator *gen_declarators(struct gen_rng *rng)
 329 {
 330         struct cdecl_declarator *d, *p;
 331         unsigned limit = 3;
 332
 333         d = malloc_nofail(sizeof *d);
 334         if (gsl_rng_uniform(rng->rng) < 0.5) {
 335                 *d = (struct cdecl_declarator) {
 336                         .type = CDECL_DECL_NULL,
 337                 };
 338         } else {
 339                 *d = (struct cdecl_declarator) {
 340                         .type = CDECL_DECL_IDENT,
 341                         .u.ident = gen_identifier(rng),
 342                 };
 343         }
 344
 345         while (gsl_rng_uniform(rng->rng) < 0.5) {
 346                 p = d;
 347                 d = malloc_nofail(sizeof *d);
 348                 *d = (struct cdecl_declarator) {
 349                         .child = p,
 350                 };
 351
 352                 switch (gsl_rng_uniform_int(rng->rng, limit)) {
 353                 case 0:
 354                         d->type = CDECL_DECL_POINTER;
 355                         d->u.pointer = (struct cdecl_pointer) {
 356                                 .qualifiers = gen_qualifiers(rng, true),
 357                         };
 358                         limit = 3;
 359                         break;
 360                 case 1:
 361                         gen_array(rng, d);
 362                         limit = 2;
 363                         break;
 364                 case 2:
 365                         gen_function(rng, d);
 366                         limit = 1;
 367                         break;
 368                 default:
 369                         assert(0);
 370                 }
 371         }
 372
 373         return d;
 374 }
 375
 376 struct gen_rng *gen_alloc_rng(const char *seed_str)
 377 {
 378         unsigned long seed;
 379         struct gen_rng *rng;
 380         char *end;
 381
 382         errno = 0;
 383         seed = strtoul(seed_str, &end, 0);
 384         if (*end != 0) {
 385                 fprintf(stderr, "%s: invalid seed\n", seed_str);
 386                 return NULL;
 387         } else if (errno != 0) {
 388                 fprintf(stderr, "%s: invalid seed: %s\n",
 389                                 seed_str, strerror(errno));
 390                 return NULL;
 391         }
 392
 393         rng = malloc(sizeof *rng);
 394         if (rng) {
 395                 rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
 396                 gsl_rng_set(rng->rng, seed);
 397         }
 398
 399         return rng;
 400 }