test/declgen.c

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