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                 break;
 182         default:
 183                 /* Nothing to be done. */
 184                 ;
 185         }
 186
 187         return specs;
 188 }
 189
 190 struct cdecl_declspec *
 191 gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs)
 192 {
 193         struct cdecl_declspec **p;
 194         size_t n = 0;
 195
 196         if (!specs)
 197                 return specs;
 198
 199         for (struct cdecl_declspec *s = specs; s; s = s->next)
 200                 n++;
 201
 202         p = malloc_nofail((n+1) * sizeof *p);
 203
 204         /* Build a temporary array for easy element swapping. */
 205         p[0] = specs;
 206         p[n] = NULL;
 207         for (size_t i = 1; i < n; i++)
 208                 p[i] = p[i-1]->next;
 209
 210         /* Knuth shuffle. */
 211         for (size_t i = 0; i < n; i++) {
 212                 struct cdecl_declspec *tmp;
 213                 size_t r;
 214
 215                 r = gsl_rng_uniform_int(rng->rng, n-i);
 216                 tmp = p[i];
 217                 p[i] = p[r+i];
 218                 p[r+i] = tmp;
 219         }
 220
 221         /* Fix up the pointers. */
 222         for (size_t i = 1; i <= n; i++)
 223                 p[i-1]->next = p[i];
 224         specs = p[0];
 225
 226         free(p);
 227         return specs;
 228 }
 229
 230 /*
 231  * Generate random declaration specifiers.  This consists of random qualifiers
 232  * and type specifiers, as described in the functions above, plus up to one
 233  * storage-class specifier and zero or more function specifiers.
 234  *
 235  * The flags parameter controls what sort of specifiers can be generated in
 236  * order to handle various special cases in the C language.  It is the
 237  * bitwise-or of zero or more values, which have the following meanings:
 238  *
 239  *   GEN_NO_FUNCTION: Do not generate any function specifiers at all.
 240  *   GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
 241  *   GEN_NO_VOID: Do not generate the "void" type specifier.
 242  *   GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
 243  *                      "register".
 244  *
 245  * Notwithstanding any of the above, the "restrict" type qualifier will never
 246  * be generated by this function: use gen_qualifiers directly.
 247  */
 248 struct cdecl_declspec *
 249 gen_declspecs(struct gen_rng *rng, unsigned flags)
 250 {
 251         struct cdecl_declspec *s, *p;
 252
 253         s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
 254         for (p = s; p->next;)
 255                 p = p->next;
 256
 257         if (~flags & GEN_NO_FUNCTION)
 258                 p->next = gen_funcspecs(rng);
 259         for (p = s; p->next;)
 260                 p = p->next;
 261
 262         if (~flags & GEN_NO_STORAGE)
 263                 p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
 264         for (p = s; p->next;)
 265                 p = p->next;
 266
 267         p->next = gen_qualifiers(rng, false);
 268         return gen_randomize_specs(rng, s);
 269 }
 270
 271 /*
 272  * Generate a random array declarator, selecting one of four possibilities
 273  * uniformly at random.
 274  */
 275 static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
 276 {
 277         d->type = CDECL_DECL_ARRAY;
 278         d->u.array = (struct cdecl_array){0};
 279
 280         switch (gsl_rng_uniform_int(rng->rng, 4)) {
 281         case 0:
 282                 d->u.array.vla = malloc_nofail(1);
 283                 d->u.array.vla[0] = 0;
 284                 break;
 285         case 1:
 286                 d->u.array.vla = gen_identifier(rng);
 287                 break;
 288         case 2:
 289                 d->u.array.length = 0;
 290                 break;
 291         case 3:
 292                 d->u.array.length = gsl_rng_uniform_int(rng->rng, -1);
 293                 break;
 294         default:
 295                 assert(0);
 296         }
 297 }
 298
 299 /* Generate a function declarator. */
 300 static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
 301 {
 302         d->type = CDECL_DECL_FUNCTION;
 303         d->u.function.parameters = NULL;
 304
 305         while (gsl_rng_uniform(rng->rng) < 0.5) {
 306                 unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
 307                 struct cdecl *param;
 308
 309                 param = malloc_nofail(sizeof *param);
 310                 *param = (struct cdecl) {
 311                         .next = d->u.function.parameters,
 312                         .declarators = gen_declarators(rng),
 313                 };
 314
 315                 if (param->declarators->type != CDECL_DECL_POINTER
 316                     && param->declarators->type != CDECL_DECL_FUNCTION)
 317                         flags |= GEN_NO_VOID;
 318
 319                 param->specifiers = gen_declspecs(rng, flags);
 320                 d->u.function.parameters = param;
 321         }
 322
 323         if (d->u.function.parameters) {
 324                 d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
 325         }
 326 }
 327
 328 /*
 329  * Generate a random chain of declarators.  Like qualifiers above, a chain of
 330  * length N has probability 1/2^(N+1) of occurring.  All declarator chains
 331  * are ultimately terminated by either a null declarator or an identifier,
 332  * selected uniformly at random.
 333  */
 334 struct cdecl_declarator *gen_declarators(struct gen_rng *rng)
 335 {
 336         struct cdecl_declarator *d, *p;
 337         unsigned limit = 3;
 338
 339         d = malloc_nofail(sizeof *d);
 340         if (gsl_rng_uniform(rng->rng) < 0.5) {
 341                 *d = (struct cdecl_declarator) {
 342                         .type = CDECL_DECL_NULL,
 343                 };
 344         } else {
 345                 *d = (struct cdecl_declarator) {
 346                         .type = CDECL_DECL_IDENT,
 347                         .u.ident = gen_identifier(rng),
 348                 };
 349         }
 350
 351         while (gsl_rng_uniform(rng->rng) < 0.5) {
 352                 p = d;
 353                 d = malloc_nofail(sizeof *d);
 354                 *d = (struct cdecl_declarator) {
 355                         .child = p,
 356                 };
 357
 358                 switch (gsl_rng_uniform_int(rng->rng, limit)) {
 359                 case 0:
 360                         d->type = CDECL_DECL_POINTER;
 361                         d->u.pointer = (struct cdecl_pointer) {
 362                                 .qualifiers = gen_qualifiers(rng, true),
 363                         };
 364                         limit = 3;
 365                         break;
 366                 case 1:
 367                         gen_array(rng, d);
 368                         limit = 2;
 369                         break;
 370                 case 2:
 371                         gen_function(rng, d);
 372                         limit = 1;
 373                         break;
 374                 default:
 375                         assert(0);
 376                 }
 377         }
 378
 379         return d;
 380 }
 381
 382 struct gen_rng *gen_alloc_rng(const char *seed_str)
 383 {
 384         unsigned long seed;
 385         struct gen_rng *rng;
 386         char *end;
 387
 388         errno = 0;
 389         seed = strtoul(seed_str, &end, 0);
 390         if (*end != 0) {
 391                 fprintf(stderr, "%s: invalid seed\n", seed_str);
 392                 return NULL;
 393         } else if (errno != 0) {
 394                 fprintf(stderr, "%s: invalid seed: %s\n",
 395                                 seed_str, strerror(errno));
 396                 return NULL;
 397         }
 398
 399         rng = malloc_nofail(sizeof *rng);
 400         rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
 401         gsl_rng_set(rng->rng, seed);
 402
 403         return rng;
 404 }
 405
 406 void gen_free_rng(struct gen_rng *rng)
 407 {
 408         if (rng)
 409                 gsl_rng_free(rng->rng);
 410         free(rng);
 411 }
 412
 413 static void gen_free_parameters(struct cdecl *x)
 414 {
 415         struct cdecl *p;
 416
 417         while (x) {
 418                 p = x->next;
 419
 420                 gen_free_declspecs(x->specifiers);
 421                 gen_free_declarators(x->declarators);
 422                 free(x);
 423
 424                 x = p;
 425         }
 426 }
 427
 428 void gen_free_declspecs(struct cdecl_declspec *x)
 429 {
 430         struct cdecl_declspec *p;
 431
 432         while (x) {
 433                 p = x->next;
 434                 free(x->ident);
 435                 free(x);
 436                 x = p;
 437         }
 438 }
 439
 440 void gen_free_declarators(struct cdecl_declarator *x)
 441 {
 442         struct cdecl_declarator *p;
 443
 444         while (x) {
 445                 p = x->child;
 446
 447                 switch (x->type) {
 448                 case CDECL_DECL_NULL:
 449                         break;
 450                 case CDECL_DECL_IDENT:
 451                         free(x->u.ident);
 452                         break;
 453                 case CDECL_DECL_POINTER:
 454                         gen_free_declspecs(x->u.pointer.qualifiers);
 455                         break;
 456                 case CDECL_DECL_ARRAY:
 457                         free(x->u.array.vla);
 458                         break;
 459                 case CDECL_DECL_FUNCTION:
 460                         gen_free_parameters(x->u.function.parameters);
 461                         break;
 462                 default:
 463                         assert(0);
 464                 }
 465
 466                 free(x);
 467                 x = p;
 468         }
 469 }