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