/*
* Generate random C declarations for testing.
* Copyright © 2012, 2021-2023 Nick Bowler
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include "declgen.h"
#include "cdecl.h"
#include "test.h"
/*
* Return a newly-allocated null declarator. The child member is set by the
* argument; other members are initialized to zero.
*/
struct cdecl_declarator *new_declarator(struct cdecl_declarator *child)
{
struct cdecl_declarator *d, init = { child, CDECL_DECL_NULL };
d = malloc_nofail(sizeof *d);
*d = init;
return d;
}
/*
* Return a newly-allocated void specifier. The next member is set by the
* argument; other members are initialized to zero.
*/
struct cdecl_declspec *new_specifier(struct cdecl_declspec *next)
{
struct cdecl_declspec *d, init = { next, CDECL_TYPE_VOID };
d = malloc_nofail(sizeof *d);
*d = init;
return d;
}
/*
* Return a newly-allocated declaration. The next member is set by the
* argument; other members are initialized to zero.
*/
struct cdecl *new_cdecl(struct cdecl *next)
{
struct cdecl *d, init = { next };
d = malloc_nofail(sizeof *d);
*d = init;
return d;
}
/*
* Generate a random identifier. We arbitrarily pick 10 as the largest
* possible. Avoid generating keywords, including the English ones, by
* excluding the letters t, o, a and n. Reserved words are OK.
*/
char *gen_identifier(struct test_rng *rng)
{
static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char *str;
size_t n;
n = test_rng_uniform_int(rng, 10)+1;
str = malloc_nofail(n+1);
/* Exclude 10 digits from the first character. */
str[0] = valid[test_rng_uniform_int(rng, sizeof valid - 10)];
for (size_t i = 1; i < n; i++)
str[i] = valid[test_rng_uniform_int(rng, sizeof valid)];
str[n] = 0;
return str;
}
/*
* Generate random qualifiers. Qualifiers can appear multiple times, so the
* list is (potentially) unbounded. We handle the potential unboundedness by
* generating a list of n qualifiers with probability 1/2^(n+1). Each
* qualifier is chosen uniformly at random from the set of possibilities:
* const, volatile and, if restrictqual is true, restrict.
*/
struct cdecl_declspec *gen_qualifiers(struct test_rng *rng, bool restrictqual)
{
struct cdecl_declspec *s = NULL;
while (test_rng_50_50(rng)) {
s = new_specifier(s);
switch (test_rng_uniform_int(rng, 2+restrictqual)) {
case 0:
s->type = CDECL_QUAL_CONST;
break;
case 1:
s->type = CDECL_QUAL_VOLATILE;
break;
case 2: /* Only if restrictqual is true. */
s->type = CDECL_QUAL_RESTRICT;
break;
default:
assert(0);
}
}
return s;
}
/*
* Generate random function specifiers. Like qualifiers, function specifiers
* can appear multiple times.
*/
struct cdecl_declspec *gen_funcspecs(struct test_rng *rng)
{
struct cdecl_declspec *s = NULL;
while (test_rng_50_50(rng)) {
s = new_specifier(s);
s->type = CDECL_FUNC_INLINE;
}
return s;
}
/*
* Generate zero or one random storage-class specifier. If registeronly is
* true, then the only possible storage-class specifier is "register".
* Otherwise, a specifier type will be selected uniformly at random.
*/
struct cdecl_declspec *gen_storspecs(struct test_rng *rng, bool registeronly)
{
struct cdecl_declspec *s;
if (test_rng_50_50(rng))
return NULL;
s = new_specifier(NULL);
switch (test_rng_uniform_int(rng, registeronly ? 1 : 5)) {
case 0: s->type = CDECL_STOR_REGISTER; break;
case 1: s->type = CDECL_STOR_TYPEDEF; break;
case 2: s->type = CDECL_STOR_STATIC; break;
case 3: s->type = CDECL_STOR_AUTO; break;
case 4: s->type = CDECL_STOR_EXTERN; break;
default: assert(0);
}
return s;
}
/*
* Generate random type specifiers. There is a short list of valid
* combinations, from which we can select one uniformly at random.
*/
#include "typegen.h"
struct cdecl_declspec *gen_typespecs(struct test_rng *rng, bool voidtype)
{
struct cdecl_declspec *specs;
retry:
specs = gen_raw_typespecs(test_rng_uniform_int(rng, GEN_TOTAL_TYPES));
switch (specs->type) {
/* void is not always valid, so we might need to pick again. */
case CDECL_TYPE_VOID:
if (!voidtype) {
assert(!specs->next);
free(specs);
goto retry;
}
break;
/* A few kinds of type specifiers need identifiers to go with them. */
case CDECL_TYPE_STRUCT:
case CDECL_TYPE_UNION:
case CDECL_TYPE_ENUM:
case CDECL_TYPE_IDENT:
assert(!specs->next);
specs->ident = gen_identifier(rng);
break;
default:
/* Nothing to be done. */
;
}
return specs;
}
struct cdecl_declspec *
gen_randomize_specs(struct test_rng *rng, struct cdecl_declspec *specs)
{
struct cdecl_declspec **p;
size_t n = 0;
if (!specs)
return specs;
for (struct cdecl_declspec *s = specs; s; s = s->next)
n++;
p = malloc_nofail((n+1) * sizeof *p);
/* Build a temporary array for easy element swapping. */
p[0] = specs;
p[n] = NULL;
for (size_t i = 1; i < n; i++)
p[i] = p[i-1]->next;
/* Knuth shuffle. */
for (size_t i = 0; i < n; i++) {
struct cdecl_declspec *tmp;
size_t r;
r = test_rng_uniform_int(rng, n-i);
tmp = p[i];
p[i] = p[r+i];
p[r+i] = tmp;
}
/* Fix up the pointers. */
for (size_t i = 1; i <= n; i++)
p[i-1]->next = p[i];
specs = p[0];
free(p);
return specs;
}
/*
* Generate random declaration specifiers. This consists of random qualifiers
* and type specifiers, as described in the functions above, plus up to one
* storage-class specifier and zero or more function specifiers.
*
* The flags parameter controls what sort of specifiers can be generated in
* order to handle various special cases in the C language. It is the
* bitwise-or of zero or more values, which have the following meanings:
*
* GEN_NO_FUNCTION: Do not generate any function specifiers at all.
* GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
* GEN_NO_VOID: Do not generate the "void" type specifier.
* GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
* "register".
*
* Notwithstanding any of the above, the "restrict" type qualifier will never
* be generated by this function: use gen_qualifiers directly.
*/
struct cdecl_declspec *
gen_declspecs(struct test_rng *rng, unsigned flags)
{
struct cdecl_declspec *s, *p;
s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
for (p = s; p->next;)
p = p->next;
if (~flags & GEN_NO_FUNCTION)
p->next = gen_funcspecs(rng);
for (p = s; p->next;)
p = p->next;
if (~flags & GEN_NO_STORAGE)
p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
for (p = s; p->next;)
p = p->next;
p->next = gen_qualifiers(rng, false);
return gen_randomize_specs(rng, s);
}
static uintmax_t gen_uintmax(struct test_rng *rng)
{
unsigned char tmp;
uintmax_t ret = 0;
for (size_t i = 0; i < sizeof ret; i++) {
tmp = test_rng_uniform_int(rng, UCHAR_MAX+1);
ret <<= CHAR_BIT;
ret |= tmp;
}
return ret;
}
/*
* Generate a random array declarator, selecting one of four possibilities
* uniformly at random.
*/
static void gen_array(struct test_rng *rng, struct cdecl_declarator *d)
{
struct cdecl_array tmp = {0};
switch (test_rng_uniform_int(rng, 4)) {
case 0:
tmp.vla = malloc_nofail(1);
tmp.vla[0] = 0;
break;
case 1:
tmp.vla = gen_identifier(rng);
break;
case 2:
tmp.length = gen_uintmax(rng);
case 3:
break;
default:
assert(0);
}
d->type = CDECL_DECL_ARRAY;
d->u.array = tmp;
}
/* Generate a function declarator. */
static void gen_function(struct test_rng *rng, struct cdecl_declarator *d)
{
d->type = CDECL_DECL_FUNCTION;
d->u.function.parameters = NULL;
while (test_rng_50_50(rng)) {
unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
struct cdecl *param;
param = new_cdecl(d->u.function.parameters);
param->declarators = gen_declarators(rng);
if (param->declarators->type != CDECL_DECL_POINTER
&& param->declarators->type != CDECL_DECL_FUNCTION)
flags |= GEN_NO_VOID;
param->specifiers = gen_declspecs(rng, flags);
d->u.function.parameters = param;
}
if (d->u.function.parameters) {
d->u.function.variadic = test_rng_50_50(rng);
} else if (test_rng_50_50(rng)) {
struct cdecl *param;
/* We will never generate (void) above; do it here. */
param = new_cdecl(NULL);
param->declarators = new_declarator(NULL);
param->specifiers = new_specifier(NULL);
d->u.function.parameters = param;
}
}
/*
* Generate a random chain of declarators. Like qualifiers above, a chain of
* length N has probability 1/2^(N+1) of occurring. All declarator chains
* are ultimately terminated by either a null declarator or an identifier,
* selected uniformly at random.
*/
struct cdecl_declarator *gen_declarators(struct test_rng *rng)
{
struct cdecl_declarator *d, *p;
unsigned limit = 3;
d = new_declarator(NULL);
if (test_rng_50_50(rng)) {
d->type = CDECL_DECL_IDENT;
d->u.ident = gen_identifier(rng);
}
while (test_rng_50_50(rng)) {
d = new_declarator((p = d));
switch (test_rng_uniform_int(rng, limit)) {
case 0:
d->type = CDECL_DECL_POINTER;
d->u.pointer.qualifiers = gen_qualifiers(rng, true);
limit = 3;
break;
case 1:
gen_array(rng, d);
limit = 2;
break;
case 2:
gen_function(rng, d);
if (p && p->type == CDECL_DECL_POINTER) {
struct cdecl_pointer *ptr = &p->u.pointer;
gen_free_declspecs(ptr->qualifiers);
ptr->qualifiers = gen_qualifiers(rng, false);
}
limit = 1;
break;
default:
assert(0);
}
}
return d;
}
static void gen_free_parameters(struct cdecl *x)
{
struct cdecl *p;
while (x) {
p = x->next;
gen_free_declspecs(x->specifiers);
gen_free_declarators(x->declarators);
free(x);
x = p;
}
}
void gen_free_declspecs(struct cdecl_declspec *x)
{
struct cdecl_declspec *p;
while (x) {
p = x->next;
free(x->ident);
free(x);
x = p;
}
}
void gen_free_declarators(struct cdecl_declarator *x)
{
struct cdecl_declarator *p;
while (x) {
p = x->child;
switch (x->type) {
case CDECL_DECL_NULL:
break;
case CDECL_DECL_IDENT:
free(x->u.ident);
break;
case CDECL_DECL_POINTER:
gen_free_declspecs(x->u.pointer.qualifiers);
break;
case CDECL_DECL_ARRAY:
free(x->u.array.vla);
break;
case CDECL_DECL_FUNCTION:
gen_free_parameters(x->u.function.parameters);
break;
default:
assert(0);
}
free(x);
x = p;
}
}