t/declgen.c

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