2 * Generate random C declarations for testing.
3 * Copyright © 2012, 2021-2024 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/>.
32 * Return a newly-allocated null declarator. The child member is set by the
33 * argument; other members are initialized to zero.
35 static struct cdecl_declarator *new_declarator(struct cdecl_declarator *child)
37 struct cdecl_declarator *d, init = { child, CDECL_DECL_NULL };
39 d = malloc_nofail(sizeof *d);
46 * Return a newly-allocated void specifier. The next member is set by the
47 * argument; other members are initialized to zero.
49 static struct cdecl_declspec *new_specifier(struct cdecl_declspec *next)
51 struct cdecl_declspec *d, init = { next, CDECL_TYPE_VOID };
53 d = malloc_nofail(sizeof *d);
60 * Return a newly-allocated declaration. The next member is set by the
61 * argument; other members are initialized to zero.
63 static struct cdecl *new_cdecl(struct cdecl *next)
65 struct cdecl *d, init = { next };
67 d = malloc_nofail(sizeof *d);
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.
78 static char *gen_identifier(struct test_rng *rng)
80 static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
84 n = test_rng_uniform_int(rng, 10)+1;
85 str = malloc_nofail(n+1);
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)];
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.
103 static struct cdecl_declspec *
104 gen_qualifiers(struct test_rng *rng, int restrictqual)
106 struct cdecl_declspec *s = NULL;
108 while (test_rng_50_50(rng)) {
109 s = new_specifier(s);
111 switch (test_rng_uniform_int(rng, 2+!!restrictqual)) {
113 s->type = CDECL_QUAL_CONST;
116 s->type = CDECL_QUAL_VOLATILE;
118 case 2: /* Only if restrictqual is true. */
119 s->type = CDECL_QUAL_RESTRICT;
130 * Generate random function specifiers. Like qualifiers, function specifiers
131 * can appear multiple times.
133 static struct cdecl_declspec *gen_funcspecs(struct test_rng *rng)
135 struct cdecl_declspec *s = NULL;
137 while (test_rng_50_50(rng)) {
138 s = new_specifier(s);
139 s->type = CDECL_FUNC_INLINE;
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.
150 static struct cdecl_declspec *
151 gen_storspecs(struct test_rng *rng, int registeronly)
153 struct cdecl_declspec *s;
155 if (test_rng_50_50(rng))
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;
172 * Generate random type specifiers. There is a short list of valid
173 * combinations, from which we can select one uniformly at random.
177 static struct cdecl_declspec *
178 gen_typespecs(struct test_rng *rng, int voidtype)
180 struct cdecl_declspec *specs;
183 specs = gen_raw_typespecs(test_rng_uniform_int(rng, GEN_TOTAL_TYPES));
185 switch (specs->type) {
186 /* void is not always valid, so we might need to pick again. */
187 case CDECL_TYPE_VOID:
189 assert(!specs->next);
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);
203 /* Nothing to be done. */
210 static struct cdecl_declspec *
211 gen_randomize_specs(struct test_rng *rng, struct cdecl_declspec *specs)
213 struct cdecl_declspec *s, **p;
219 for (s = specs; s; s = s->next)
222 p = malloc_nofail((n+1) * sizeof *p);
224 /* Build a temporary array for easy element swapping. */
227 for (i = 1; i < n; i++)
231 for (i = 0; i < n; i++) {
232 struct cdecl_declspec *tmp;
235 r = test_rng_uniform_int(rng, n-i);
241 /* Fix up the pointers. */
242 for (i = 1; i <= n; i++)
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.
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:
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
265 * Notwithstanding any of the above, the "restrict" type qualifier will never
266 * be generated by this function: use gen_qualifiers directly.
268 struct cdecl_declspec *
269 gen_declspecs(struct test_rng *rng, unsigned flags)
271 struct cdecl_declspec *s, *p;
273 s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
274 for (p = s; p->next;)
277 if (~flags & GEN_NO_FUNCTION)
278 p->next = gen_funcspecs(rng);
279 for (p = s; p->next;)
282 if (~flags & GEN_NO_STORAGE)
283 p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
284 for (p = s; p->next;)
287 p->next = gen_qualifiers(rng, 0);
288 return gen_randomize_specs(rng, s);
291 static cdecl_uintmax gen_uintmax(struct test_rng *rng)
293 cdecl_uintmax ret = 0;
297 for (i = 0; i < sizeof ret; i++) {
298 tmp = test_rng_uniform_int(rng, UCHAR_MAX+1);
307 * Generate a random array declarator, selecting one of four possibilities
308 * uniformly at random.
310 static void gen_array(struct test_rng *rng, struct cdecl_declarator *d)
312 struct cdecl_array tmp = {0};
314 switch (test_rng_uniform_int(rng, 4)) {
316 tmp.vla = malloc_nofail(1);
320 tmp.vla = gen_identifier(rng);
323 tmp.length = gen_uintmax(rng);
330 d->type = CDECL_DECL_ARRAY;
334 /* Generate a function declarator. */
335 static void gen_function(struct test_rng *rng, struct cdecl_declarator *d)
337 d->type = CDECL_DECL_FUNCTION;
338 d->u.function.parameters = NULL;
340 while (test_rng_50_50(rng)) {
341 unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
344 param = new_cdecl(d->u.function.parameters);
345 param->declarators = gen_declarators(rng);
347 if (param->declarators->type != CDECL_DECL_POINTER
348 && param->declarators->type != CDECL_DECL_FUNCTION)
349 flags |= GEN_NO_VOID;
351 param->specifiers = gen_declspecs(rng, flags);
352 d->u.function.parameters = param;
355 if (d->u.function.parameters) {
356 d->u.function.variadic = test_rng_50_50(rng);
357 } else if (test_rng_50_50(rng)) {
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);
365 d->u.function.parameters = param;
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.
375 struct cdecl_declarator *gen_declarators(struct test_rng *rng)
377 struct cdecl_declarator *d, *p;
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);
386 while (test_rng_50_50(rng)) {
387 d = new_declarator((p = d));
389 switch (test_rng_uniform_int(rng, limit)) {
391 d->type = CDECL_DECL_POINTER;
392 d->u.pointer.qualifiers = gen_qualifiers(rng, 1);
400 gen_function(rng, d);
401 if (p && p->type == CDECL_DECL_POINTER) {
402 struct cdecl_pointer *ptr = &p->u.pointer;
404 gen_free_declspecs(ptr->qualifiers);
405 ptr->qualifiers = gen_qualifiers(rng, 0);
417 static void gen_free_parameters(struct cdecl *x)
424 gen_free_declspecs(x->specifiers);
425 gen_free_declarators(x->declarators);
432 void gen_free_declspecs(struct cdecl_declspec *x)
434 struct cdecl_declspec *p;
444 void gen_free_declarators(struct cdecl_declarator *x)
446 struct cdecl_declarator *p;
452 case CDECL_DECL_NULL:
454 case CDECL_DECL_IDENT:
457 case CDECL_DECL_POINTER:
458 gen_free_declspecs(x->u.pointer.qualifiers);
460 case CDECL_DECL_ARRAY:
461 free(x->u.array.vla);
463 case CDECL_DECL_FUNCTION:
464 gen_free_parameters(x->u.function.parameters);