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