--- /dev/null
+/*
+ * Generate random C declarations for testing.
+ * Copyright © 2011 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 <http://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+#include <stdbool.h>
+#include <gsl/gsl_rng.h>
+
+#include "declgen.h"
+#include "cdecl.h"
+#include "test.h"
+
+struct gen_rng {
+ gsl_rng *rng;
+};
+
+/*
+ * 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 gen_rng *rng)
+{
+ static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
+ char *str;
+ size_t n;
+
+ n = gsl_rng_uniform_int(rng->rng, 10)+1;
+ str = malloc_nofail(n+1);
+
+ /* Exclude 10 digits from the first character. */
+ str[0] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid - 10)];
+ for (size_t i = 1; i < n; i++)
+ str[i] = valid[gsl_rng_uniform_int(rng->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 gen_rng *rng, bool restrictqual)
+{
+ struct cdecl_declspec *s = NULL, *p;
+
+ while (gsl_rng_uniform(rng->rng) < 0.5) {
+ p = s;
+ s = malloc_nofail(sizeof *s);
+ *s = (struct cdecl_declspec) {
+ .next = p,
+ };
+
+ switch (gsl_rng_uniform_int(rng->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 gen_rng *rng)
+{
+ struct cdecl_declspec *s = NULL, *p;
+
+ while (gsl_rng_uniform(rng->rng) < 0.5) {
+ p = s;
+ s = malloc_nofail(sizeof *s);
+
+ *s = (struct cdecl_declspec) {
+ .type = CDECL_FUNC_INLINE,
+ .next = p,
+ };
+ }
+
+ 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 gen_rng *rng, bool registeronly)
+{
+ struct cdecl_declspec *s;
+
+ if (gsl_rng_uniform(rng->rng) < 0.5)
+ return NULL;
+
+ s = malloc_nofail(sizeof *s);
+ *s = (struct cdecl_declspec) {
+ .type = CDECL_STOR_REGISTER,
+ };
+
+ if (registeronly)
+ return s;
+
+ switch (gsl_rng_uniform_int(rng->rng, 5)) {
+ case 0: s->type = CDECL_STOR_TYPEDEF; break;
+ case 1: s->type = CDECL_STOR_REGISTER; 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.
+ */
+static const unsigned long total_types;
+static struct cdecl_declspec *gen_raw_typespecs(struct gen_rng *rng)
+{
+ switch (gsl_rng_uniform_int(rng->rng, total_types)) {
+# include "typegen.h"
+ }
+}
+static const unsigned long total_types = TOTAL_TYPES;
+
+struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype)
+{
+ struct cdecl_declspec *specs;
+
+retry:
+ specs = gen_raw_typespecs(rng);
+
+ switch (specs->type) {
+ /* void is not always valid, so we might need to pick again. */
+ case CDECL_TYPE_VOID:
+ if (!voidtype)
+ 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);
+ }
+
+ return specs;
+}
+
+struct cdecl_declspec *
+gen_randomize_specs(struct gen_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 = gsl_rng_uniform_int(rng->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 gen_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);
+}
+
+/*
+ * Generate a random array declarator, selecting one of four possibilities
+ * uniformly at random.
+ */
+static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
+{
+ d->type = CDECL_DECL_ARRAY;
+ d->u.array = (struct cdecl_array){0};
+
+ switch (gsl_rng_uniform_int(rng->rng, 4)) {
+ case '0':
+ d->u.array.vla = malloc_nofail(1);
+ d->u.array.vla[0] = 0;
+ break;
+ case '1':
+ d->u.array.vla = gen_identifier(rng);
+ break;
+ case '2':
+ d->u.array.length = 0;
+ break;
+ case '3':
+ d->u.array.length = gsl_rng_uniform_int(rng->rng, -1);
+ break;
+ }
+}
+
+/* Generate a function declarator. */
+static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
+{
+ d->type = CDECL_DECL_FUNCTION;
+ d->u.function.parameters = NULL;
+
+ while (gsl_rng_uniform(rng->rng) < 0.5) {
+ unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
+ struct cdecl *param;
+
+ param = malloc_nofail(sizeof *param);
+ *param = (struct cdecl) {
+ .next = d->u.function.parameters,
+ .declarators = gen_declarators(rng),
+ };
+
+ if (param->declarators->type == CDECL_DECL_ARRAY
+ || param->declarators->type == CDECL_DECL_IDENT)
+ flags |= GEN_NO_VOID;
+
+ param->specifiers = gen_declspecs(rng, flags);
+ d->u.function.parameters = param;
+ }
+
+ if (d->u.function.parameters) {
+ d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
+ }
+}
+
+/*
+ * 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 gen_rng *rng)
+{
+ struct cdecl_declarator *d, *p;
+ unsigned limit = 3;
+
+ d = malloc_nofail(sizeof *d);
+ if (gsl_rng_uniform(rng->rng) < 0.5) {
+ *d = (struct cdecl_declarator) {
+ .type = CDECL_DECL_NULL,
+ };
+ } else {
+ *d = (struct cdecl_declarator) {
+ .type = CDECL_DECL_IDENT,
+ .u.ident = gen_identifier(rng),
+ };
+ }
+
+ while (gsl_rng_uniform(rng->rng) < 0.5) {
+ p = d;
+ d = malloc_nofail(sizeof *d);
+ *d = (struct cdecl_declarator) {
+ .child = p,
+ };
+
+ switch (gsl_rng_uniform_int(rng->rng, limit)) {
+ case 0:
+ d->type = CDECL_DECL_POINTER;
+ d->u.pointer = (struct cdecl_pointer) {
+ .qualifiers = gen_qualifiers(rng, true),
+ };
+ limit = 3;
+ break;
+ case 1:
+ gen_array(rng, d);
+ limit = 2;
+ break;
+ case 2:
+ gen_function(rng, d);
+ limit = 1;
+ break;
+ default:
+ assert(0);
+ }
+ }
+
+ return d;
+}
+
+struct gen_rng *gen_alloc_rng(const char *seed_str)
+{
+ unsigned long seed;
+ struct gen_rng *rng;
+ char *end;
+
+ errno = 0;
+ seed = strtoul(seed_str, &end, 0);
+ if (*end != 0) {
+ fprintf(stderr, "%s: invalid seed\n", seed_str);
+ return NULL;
+ } else if (errno != 0) {
+ fprintf(stderr, "%s: invalid seed: %s\n",
+ seed_str, strerror(errno));
+ return NULL;
+ }
+
+ rng = malloc(sizeof *rng);
+ if (rng) {
+ rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
+ gsl_rng_set(rng->rng, seed);
+ }
+
+ return rng;
+}
projects / cdecl99.git / blobdiff