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 <limits.h>
  24 #include <errno.h>
  25 #include <assert.h>
  26 #include <stdbool.h>
  27 #include <gsl/gsl_rng.h>
  28
  29 #include "declgen.h"
  30 #include "cdecl.h"
  31 #include "test.h"
  32
  33 struct gen_rng {
  34         gsl_rng *rng;
  35 };
  36
  37 /*
  38  * Generate a random identifier.  We arbitrarily pick 10 as the largest
  39  * possible.  Avoid generating keywords, including the English ones, by
  40  * excluding the letters t, o, a and n.  Reserved words are OK.
  41  */
  42 char *gen_identifier(struct gen_rng *rng)
  43 {
  44         static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  45         char *str;
  46         size_t n;
  47
  48         n = gsl_rng_uniform_int(rng->rng, 10)+1;
  49         str = malloc_nofail(n+1);
  50
  51         /* Exclude 10 digits from the first character. */
  52         str[0] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid - 10)];
  53         for (size_t i = 1; i < n; i++)
  54                 str[i] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid)];
  55         str[n] = 0;
  56
  57         return str;
  58 }
  59
  60 /*
  61  * Generate random qualifiers.  Qualifiers can appear multiple times, so the
  62  * list is (potentially) unbounded.  We handle the potential unboundedness by
  63  * generating a list of n qualifiers with probability 1/2^(n+1).  Each
  64  * qualifier is chosen uniformly at random from the set of possibilities:
  65  * const, volatile and, if restrictqual is true, restrict.
  66  */
  67 struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual)
  68 {
  69         struct cdecl_declspec *s = NULL, *p;
  70
  71         while (gsl_rng_uniform(rng->rng) < 0.5) {
  72                 p = s;
  73                 s = malloc_nofail(sizeof *s);
  74                 *s = (struct cdecl_declspec) {
  75                         .next = p,
  76                 };
  77
  78                 switch (gsl_rng_uniform_int(rng->rng, 2+restrictqual)) {
  79                 case 0:
  80                         s->type = CDECL_QUAL_CONST;
  81                         break;
  82                 case 1:
  83                         s->type = CDECL_QUAL_VOLATILE;
  84                         break;
  85                 case 2: /* Only if restrictqual is true. */
  86                         s->type = CDECL_QUAL_RESTRICT;
  87                         break;
  88                 default:
  89                         assert(0);
  90                 }
  91         }
  92
  93         return s;
  94 }
  95
  96 /*
  97  * Generate random function specifiers.  Like qualifiers, function specifiers
  98  * can appear multiple times.
  99  */
 100 struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng)
 101 {
 102         struct cdecl_declspec *s = NULL, *p;
 103
 104         while (gsl_rng_uniform(rng->rng) < 0.5) {
 105                 p = s;
 106                 s = malloc_nofail(sizeof *s);
 107
 108                 *s = (struct cdecl_declspec) {
 109                         .type = CDECL_FUNC_INLINE,
 110                         .next = p,
 111                 };
 112         }
 113
 114         return s;
 115 }
 116
 117 /*
 118  * Generate zero or one random storage-class specifier.  If registeronly is
 119  * true, then the only possible storage-class specifier is "register".
 120  * Otherwise, a specifier type will be selected uniformly at random.
 121  */
 122 struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly)
 123 {
 124         struct cdecl_declspec *s;
 125
 126         if (gsl_rng_uniform(rng->rng) < 0.5)
 127                 return NULL;
 128
 129         s = malloc_nofail(sizeof *s);
 130         *s = (struct cdecl_declspec) {
 131                 .type = CDECL_STOR_REGISTER,
 132         };
 133
 134         if (registeronly)
 135                 return s;
 136
 137         switch (gsl_rng_uniform_int(rng->rng, 5)) {
 138         case 0: s->type = CDECL_STOR_TYPEDEF;  break;
 139         case 1: s->type = CDECL_STOR_REGISTER; break;
 140         case 2: s->type = CDECL_STOR_STATIC;   break;
 141         case 3: s->type = CDECL_STOR_AUTO;     break;
 142         case 4: s->type = CDECL_STOR_EXTERN;   break;
 143         default: assert(0);
 144         }
 145
 146         return s;
 147 }
 148
 149 /*
 150  * Generate random type specifiers.  There is a short list of valid
 151  * combinations, from which we can select one uniformly at random.
 152  */
 153 static const unsigned long total_types;
 154 static struct cdecl_declspec *gen_raw_typespecs(struct gen_rng *rng)
 155 {
 156         switch (gsl_rng_uniform_int(rng->rng, total_types)) {
 157 #       include "typegen.h"
 158         }
 159 }
 160 static const unsigned long total_types = TOTAL_TYPES;
 161
 162 struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype)
 163 {
 164         struct cdecl_declspec *specs;
 165
 166 retry:
 167         specs = gen_raw_typespecs(rng);
 168
 169         switch (specs->type) {
 170         /* void is not always valid, so we might need to pick again. */
 171         case CDECL_TYPE_VOID:
 172                 if (!voidtype)
 173                         goto retry;
 174                 break;
 175         /* A few kinds of type specifiers need identifiers to go with them. */
 176         case CDECL_TYPE_STRUCT:
 177         case CDECL_TYPE_UNION:
 178         case CDECL_TYPE_ENUM:
 179         case CDECL_TYPE_IDENT:
 180                 assert(!specs->next);
 181                 specs->ident = gen_identifier(rng);
 182                 break;
 183         default:
 184                 /* Nothing to be done. */
 185                 ;
 186         }
 187
 188         return specs;
 189 }
 190
 191 struct cdecl_declspec *
 192 gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs)
 193 {
 194         struct cdecl_declspec **p;
 195         size_t n = 0;
 196
 197         if (!specs)
 198                 return specs;
 199
 200         for (struct cdecl_declspec *s = specs; s; s = s->next)
 201                 n++;
 202
 203         p = malloc_nofail((n+1) * sizeof *p);
 204
 205         /* Build a temporary array for easy element swapping. */
 206         p[0] = specs;
 207         p[n] = NULL;
 208         for (size_t i = 1; i < n; i++)
 209                 p[i] = p[i-1]->next;
 210
 211         /* Knuth shuffle. */
 212         for (size_t i = 0; i < n; i++) {
 213                 struct cdecl_declspec *tmp;
 214                 size_t r;
 215
 216                 r = gsl_rng_uniform_int(rng->rng, n-i);
 217                 tmp = p[i];
 218                 p[i] = p[r+i];
 219                 p[r+i] = tmp;
 220         }
 221
 222         /* Fix up the pointers. */
 223         for (size_t i = 1; i <= n; i++)
 224                 p[i-1]->next = p[i];
 225         specs = p[0];
 226
 227         free(p);
 228         return specs;
 229 }
 230
 231 /*
 232  * Generate random declaration specifiers.  This consists of random qualifiers
 233  * and type specifiers, as described in the functions above, plus up to one
 234  * storage-class specifier and zero or more function specifiers.
 235  *
 236  * The flags parameter controls what sort of specifiers can be generated in
 237  * order to handle various special cases in the C language.  It is the
 238  * bitwise-or of zero or more values, which have the following meanings:
 239  *
 240  *   GEN_NO_FUNCTION: Do not generate any function specifiers at all.
 241  *   GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
 242  *   GEN_NO_VOID: Do not generate the "void" type specifier.
 243  *   GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
 244  *                      "register".
 245  *
 246  * Notwithstanding any of the above, the "restrict" type qualifier will never
 247  * be generated by this function: use gen_qualifiers directly.
 248  */
 249 struct cdecl_declspec *
 250 gen_declspecs(struct gen_rng *rng, unsigned flags)
 251 {
 252         struct cdecl_declspec *s, *p;
 253
 254         s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
 255         for (p = s; p->next;)
 256                 p = p->next;
 257
 258         if (~flags & GEN_NO_FUNCTION)
 259                 p->next = gen_funcspecs(rng);
 260         for (p = s; p->next;)
 261                 p = p->next;
 262
 263         if (~flags & GEN_NO_STORAGE)
 264                 p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
 265         for (p = s; p->next;)
 266                 p = p->next;
 267
 268         p->next = gen_qualifiers(rng, false);
 269         return gen_randomize_specs(rng, s);
 270 }
 271
 272 static uintmax_t gen_uintmax(struct gen_rng *rng)
 273 {
 274         unsigned char tmp;
 275         uintmax_t ret = 0;
 276
 277         for (size_t i = 0; i < sizeof ret; i++) {
 278                 tmp = gsl_rng_uniform_int(rng->rng, UCHAR_MAX+1);
 279                 ret <<= CHAR_BIT;
 280                 ret |= tmp;
 281         }
 282
 283         return ret;
 284 }
 285
 286 /*
 287  * Generate a random array declarator, selecting one of four possibilities
 288  * uniformly at random.
 289  */
 290 static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
 291 {
 292         d->type = CDECL_DECL_ARRAY;
 293         d->u.array = (struct cdecl_array){0};
 294
 295         switch (gsl_rng_uniform_int(rng->rng, 4)) {
 296         case 0:
 297                 d->u.array.vla = malloc_nofail(1);
 298                 d->u.array.vla[0] = 0;
 299                 break;
 300         case 1:
 301                 d->u.array.vla = gen_identifier(rng);
 302                 break;
 303         case 2:
 304                 d->u.array.length = 0;
 305                 break;
 306         case 3:
 307                 d->u.array.length = gen_uintmax(rng);
 308                 break;
 309         default:
 310                 assert(0);
 311         }
 312 }
 313
 314 /* Generate a function declarator. */
 315 static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
 316 {
 317         d->type = CDECL_DECL_FUNCTION;
 318         d->u.function.parameters = NULL;
 319
 320         while (gsl_rng_uniform(rng->rng) < 0.5) {
 321                 unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
 322                 struct cdecl *param;
 323
 324                 param = malloc_nofail(sizeof *param);
 325                 *param = (struct cdecl) {
 326                         .next = d->u.function.parameters,
 327                         .declarators = gen_declarators(rng),
 328                 };
 329
 330                 if (param->declarators->type != CDECL_DECL_POINTER
 331                     && param->declarators->type != CDECL_DECL_FUNCTION)
 332                         flags |= GEN_NO_VOID;
 333
 334                 param->specifiers = gen_declspecs(rng, flags);
 335                 d->u.function.parameters = param;
 336         }
 337
 338         if (d->u.function.parameters) {
 339                 d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
 340         } else if (gsl_rng_uniform(rng->rng) < 0.5) {
 341                 struct cdecl *param;
 342
 343                 /* We will never generate (void) above; do it here. */
 344                 param = malloc_nofail(sizeof *param);
 345                 *param = (struct cdecl) { 0 };
 346
 347                 param->declarators = malloc_nofail(sizeof *param->declarators);
 348                 *param->declarators = (struct cdecl_declarator) {
 349                         .type = CDECL_DECL_NULL,
 350                 };
 351
 352                 param->specifiers = malloc_nofail(sizeof *param->specifiers);
 353                 *param->specifiers = (struct cdecl_declspec) {
 354                         .type = CDECL_TYPE_VOID,
 355                 };
 356
 357                 d->u.function.parameters = param;
 358         }
 359 }
 360
 361 /*
 362  * Generate a random chain of declarators.  Like qualifiers above, a chain of
 363  * length N has probability 1/2^(N+1) of occurring.  All declarator chains
 364  * are ultimately terminated by either a null declarator or an identifier,
 365  * selected uniformly at random.
 366  */
 367 struct cdecl_declarator *gen_declarators(struct gen_rng *rng)
 368 {
 369         struct cdecl_declarator *d, *p;
 370         unsigned limit = 3;
 371
 372         d = malloc_nofail(sizeof *d);
 373         if (gsl_rng_uniform(rng->rng) < 0.5) {
 374                 *d = (struct cdecl_declarator) {
 375                         .type = CDECL_DECL_NULL,
 376                 };
 377         } else {
 378                 *d = (struct cdecl_declarator) {
 379                         .type = CDECL_DECL_IDENT,
 380                         .u.ident = gen_identifier(rng),
 381                 };
 382         }
 383
 384         while (gsl_rng_uniform(rng->rng) < 0.5) {
 385                 p = d;
 386                 d = malloc_nofail(sizeof *d);
 387                 *d = (struct cdecl_declarator) {
 388                         .child = p,
 389                 };
 390
 391                 switch (gsl_rng_uniform_int(rng->rng, limit)) {
 392                 case 0:
 393                         d->type = CDECL_DECL_POINTER;
 394                         d->u.pointer = (struct cdecl_pointer) {
 395                                 .qualifiers = gen_qualifiers(rng, true),
 396                         };
 397                         limit = 3;
 398                         break;
 399                 case 1:
 400                         gen_array(rng, d);
 401                         limit = 2;
 402                         break;
 403                 case 2:
 404                         gen_function(rng, d);
 405                         if (p && p->type == CDECL_DECL_POINTER) {
 406                                 struct cdecl_pointer *ptr = &p->u.pointer;
 407
 408                                 gen_free_declspecs(ptr->qualifiers);
 409                                 ptr->qualifiers = gen_qualifiers(rng, false);
 410                         }
 411                         limit = 1;
 412                         break;
 413                 default:
 414                         assert(0);
 415                 }
 416         }
 417
 418         return d;
 419 }
 420
 421 struct gen_rng *gen_alloc_rng(const char *seed_str)
 422 {
 423         unsigned long seed;
 424         struct gen_rng *rng;
 425         char *end;
 426
 427         errno = 0;
 428         seed = strtoul(seed_str, &end, 0);
 429         if (*end != 0) {
 430                 fprintf(stderr, "%s: invalid seed\n", seed_str);
 431                 return NULL;
 432         } else if (errno != 0) {
 433                 fprintf(stderr, "%s: invalid seed: %s\n",
 434                                 seed_str, strerror(errno));
 435                 return NULL;
 436         }
 437
 438         rng = malloc_nofail(sizeof *rng);
 439         rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
 440         gsl_rng_set(rng->rng, seed);
 441
 442         return rng;
 443 }
 444
 445 void gen_free_rng(struct gen_rng *rng)
 446 {
 447         if (rng)
 448                 gsl_rng_free(rng->rng);
 449         free(rng);
 450 }
 451
 452 static void gen_free_parameters(struct cdecl *x)
 453 {
 454         struct cdecl *p;
 455
 456         while (x) {
 457                 p = x->next;
 458
 459                 gen_free_declspecs(x->specifiers);
 460                 gen_free_declarators(x->declarators);
 461                 free(x);
 462
 463                 x = p;
 464         }
 465 }
 466
 467 void gen_free_declspecs(struct cdecl_declspec *x)
 468 {
 469         struct cdecl_declspec *p;
 470
 471         while (x) {
 472                 p = x->next;
 473                 free(x->ident);
 474                 free(x);
 475                 x = p;
 476         }
 477 }
 478
 479 void gen_free_declarators(struct cdecl_declarator *x)
 480 {
 481         struct cdecl_declarator *p;
 482
 483         while (x) {
 484                 p = x->child;
 485
 486                 switch (x->type) {
 487                 case CDECL_DECL_NULL:
 488                         break;
 489                 case CDECL_DECL_IDENT:
 490                         free(x->u.ident);
 491                         break;
 492                 case CDECL_DECL_POINTER:
 493                         gen_free_declspecs(x->u.pointer.qualifiers);
 494                         break;
 495                 case CDECL_DECL_ARRAY:
 496                         free(x->u.array.vla);
 497                         break;
 498                 case CDECL_DECL_FUNCTION:
 499                         gen_free_parameters(x->u.function.parameters);
 500                         break;
 501                 default:
 502                         assert(0);
 503                 }
 504
 505                 free(x);
 506                 x = p;
 507         }
 508 }