2 * Generate random C declarations for testing.
3 * Copyright © 2011 Nick Bowler
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.
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.
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/>.
27 #include <gsl/gsl_rng.h>
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.
42 char *gen_identifier(struct gen_rng *rng)
44 static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
48 n = gsl_rng_uniform_int(rng->rng, 10)+1;
49 str = malloc_nofail(n+1);
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)];
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.
67 struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual)
69 struct cdecl_declspec *s = NULL, *p;
71 while (gsl_rng_uniform(rng->rng) < 0.5) {
73 s = malloc_nofail(sizeof *s);
74 *s = (struct cdecl_declspec) {
78 switch (gsl_rng_uniform_int(rng->rng, 2+restrictqual)) {
80 s->type = CDECL_QUAL_CONST;
83 s->type = CDECL_QUAL_VOLATILE;
85 case 2: /* Only if restrictqual is true. */
86 s->type = CDECL_QUAL_RESTRICT;
97 * Generate random function specifiers. Like qualifiers, function specifiers
98 * can appear multiple times.
100 struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng)
102 struct cdecl_declspec *s = NULL, *p;
104 while (gsl_rng_uniform(rng->rng) < 0.5) {
106 s = malloc_nofail(sizeof *s);
108 *s = (struct cdecl_declspec) {
109 .type = CDECL_FUNC_INLINE,
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.
122 struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly)
124 struct cdecl_declspec *s;
126 if (gsl_rng_uniform(rng->rng) < 0.5)
129 s = malloc_nofail(sizeof *s);
130 *s = (struct cdecl_declspec) {
131 .type = CDECL_STOR_REGISTER,
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;
150 * Generate random type specifiers. There is a short list of valid
151 * combinations, from which we can select one uniformly at random.
153 static const unsigned long total_types;
154 static struct cdecl_declspec *gen_raw_typespecs(struct gen_rng *rng)
156 switch (gsl_rng_uniform_int(rng->rng, total_types)) {
157 # include "typegen.h"
160 static const unsigned long total_types = TOTAL_TYPES;
162 struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype)
164 struct cdecl_declspec *specs;
167 specs = gen_raw_typespecs(rng);
169 switch (specs->type) {
170 /* void is not always valid, so we might need to pick again. */
171 case CDECL_TYPE_VOID:
175 /* A few kinds of type specifiers need identifiers to go with them. */
176 case CDECL_TYPE_STRUCT:
177 case CDECL_TYPE_UNION:
178 case CDECL_TYPE_ENUM:
179 case CDECL_TYPE_IDENT:
180 assert(!specs->next);
181 specs->ident = gen_identifier(rng);
184 /* Nothing to be done. */
191 struct cdecl_declspec *
192 gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs)
194 struct cdecl_declspec **p;
200 for (struct cdecl_declspec *s = specs; s; s = s->next)
203 p = malloc_nofail((n+1) * sizeof *p);
205 /* Build a temporary array for easy element swapping. */
208 for (size_t i = 1; i < n; i++)
212 for (size_t i = 0; i < n; i++) {
213 struct cdecl_declspec *tmp;
216 r = gsl_rng_uniform_int(rng->rng, n-i);
222 /* Fix up the pointers. */
223 for (size_t i = 1; i <= n; i++)
232 * Generate random declaration specifiers. This consists of random qualifiers
233 * and type specifiers, as described in the functions above, plus up to one
234 * storage-class specifier and zero or more function specifiers.
236 * The flags parameter controls what sort of specifiers can be generated in
237 * order to handle various special cases in the C language. It is the
238 * bitwise-or of zero or more values, which have the following meanings:
240 * GEN_NO_FUNCTION: Do not generate any function specifiers at all.
241 * GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
242 * GEN_NO_VOID: Do not generate the "void" type specifier.
243 * GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
246 * Notwithstanding any of the above, the "restrict" type qualifier will never
247 * be generated by this function: use gen_qualifiers directly.
249 struct cdecl_declspec *
250 gen_declspecs(struct gen_rng *rng, unsigned flags)
252 struct cdecl_declspec *s, *p;
254 s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
255 for (p = s; p->next;)
258 if (~flags & GEN_NO_FUNCTION)
259 p->next = gen_funcspecs(rng);
260 for (p = s; p->next;)
263 if (~flags & GEN_NO_STORAGE)
264 p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
265 for (p = s; p->next;)
268 p->next = gen_qualifiers(rng, false);
269 return gen_randomize_specs(rng, s);
272 static uintmax_t gen_uintmax(struct gen_rng *rng)
277 for (size_t i = 0; i < sizeof ret; i++) {
278 tmp = gsl_rng_uniform_int(rng->rng, UCHAR_MAX+1);
287 * Generate a random array declarator, selecting one of four possibilities
288 * uniformly at random.
290 static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
292 d->type = CDECL_DECL_ARRAY;
293 d->u.array = (struct cdecl_array){0};
295 switch (gsl_rng_uniform_int(rng->rng, 4)) {
297 d->u.array.vla = malloc_nofail(1);
298 d->u.array.vla[0] = 0;
301 d->u.array.vla = gen_identifier(rng);
304 d->u.array.length = 0;
307 d->u.array.length = gen_uintmax(rng);
314 /* Generate a function declarator. */
315 static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
317 d->type = CDECL_DECL_FUNCTION;
318 d->u.function.parameters = NULL;
320 while (gsl_rng_uniform(rng->rng) < 0.5) {
321 unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
324 param = malloc_nofail(sizeof *param);
325 *param = (struct cdecl) {
326 .next = d->u.function.parameters,
327 .declarators = gen_declarators(rng),
330 if (param->declarators->type != CDECL_DECL_POINTER
331 && param->declarators->type != CDECL_DECL_FUNCTION)
332 flags |= GEN_NO_VOID;
334 param->specifiers = gen_declspecs(rng, flags);
335 d->u.function.parameters = param;
338 if (d->u.function.parameters) {
339 d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
340 } else if (gsl_rng_uniform(rng->rng) < 0.5) {
343 /* We will never generate (void) above; do it here. */
344 param = malloc_nofail(sizeof *param);
345 *param = (struct cdecl) { 0 };
347 param->declarators = malloc_nofail(sizeof *param->declarators);
348 *param->declarators = (struct cdecl_declarator) {
349 .type = CDECL_DECL_NULL,
352 param->specifiers = malloc_nofail(sizeof *param->specifiers);
353 *param->specifiers = (struct cdecl_declspec) {
354 .type = CDECL_TYPE_VOID,
357 d->u.function.parameters = param;
362 * Generate a random chain of declarators. Like qualifiers above, a chain of
363 * length N has probability 1/2^(N+1) of occurring. All declarator chains
364 * are ultimately terminated by either a null declarator or an identifier,
365 * selected uniformly at random.
367 struct cdecl_declarator *gen_declarators(struct gen_rng *rng)
369 struct cdecl_declarator *d, *p;
372 d = malloc_nofail(sizeof *d);
373 if (gsl_rng_uniform(rng->rng) < 0.5) {
374 *d = (struct cdecl_declarator) {
375 .type = CDECL_DECL_NULL,
378 *d = (struct cdecl_declarator) {
379 .type = CDECL_DECL_IDENT,
380 .u.ident = gen_identifier(rng),
384 while (gsl_rng_uniform(rng->rng) < 0.5) {
386 d = malloc_nofail(sizeof *d);
387 *d = (struct cdecl_declarator) {
391 switch (gsl_rng_uniform_int(rng->rng, limit)) {
393 d->type = CDECL_DECL_POINTER;
394 d->u.pointer = (struct cdecl_pointer) {
395 .qualifiers = gen_qualifiers(rng, true),
404 gen_function(rng, d);
405 if (p && p->type == CDECL_DECL_POINTER) {
406 struct cdecl_pointer *ptr = &p->u.pointer;
408 gen_free_declspecs(ptr->qualifiers);
409 ptr->qualifiers = gen_qualifiers(rng, false);
421 struct gen_rng *gen_alloc_rng(const char *seed_str)
428 seed = strtoul(seed_str, &end, 0);
430 fprintf(stderr, "%s: invalid seed\n", seed_str);
432 } else if (errno != 0) {
433 fprintf(stderr, "%s: invalid seed: %s\n",
434 seed_str, strerror(errno));
438 rng = malloc_nofail(sizeof *rng);
439 rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
440 gsl_rng_set(rng->rng, seed);
445 void gen_free_rng(struct gen_rng *rng)
448 gsl_rng_free(rng->rng);
452 static void gen_free_parameters(struct cdecl *x)
459 gen_free_declspecs(x->specifiers);
460 gen_free_declarators(x->declarators);
467 void gen_free_declspecs(struct cdecl_declspec *x)
469 struct cdecl_declspec *p;
479 void gen_free_declarators(struct cdecl_declarator *x)
481 struct cdecl_declarator *p;
487 case CDECL_DECL_NULL:
489 case CDECL_DECL_IDENT:
492 case CDECL_DECL_POINTER:
493 gen_free_declspecs(x->u.pointer.qualifiers);
495 case CDECL_DECL_ARRAY:
496 free(x->u.array.vla);
498 case CDECL_DECL_FUNCTION:
499 gen_free_parameters(x->u.function.parameters);