From 31ac11cc668bb8ecc1317fd2e8bd79b7925bceeb Mon Sep 17 00:00:00 2001 From: Nick Bowler Date: Sun, 20 Nov 2011 11:37:00 -0500 Subject: [PATCH] Separate specifier handling from the output routines. This moves all the code to handle redundant specifiers and multiple orderings to the parser, so that the output routines just have to print them out in order. This will allow the output routines to be used by test generators. --- Makefile.am | 20 ++++--- src/.gitignore | 2 +- src/declare.c | 2 +- src/explain.c | 2 +- src/normalize.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++ src/normalize.h | 7 +++ src/ordspecs.sed | 24 ++++++++ src/output.c | 130 ++++++++++++++++++++--------------------- src/output.h | 3 +- src/parse-decl.c | 38 ++++++++++++ src/specs.lst | 26 +++++++++ src/typemap.c | 10 ---- src/typemap.h | 1 - src/typenames.sed | 15 ----- 14 files changed, 316 insertions(+), 107 deletions(-) create mode 100644 src/normalize.c create mode 100644 src/normalize.h create mode 100644 src/ordspecs.sed create mode 100644 src/specs.lst delete mode 100644 src/typenames.sed diff --git a/Makefile.am b/Makefile.am index 5680a6e..a6782d7 100644 --- a/Makefile.am +++ b/Makefile.am @@ -20,10 +20,10 @@ AM_CPPFLAGS = -I$(top_builddir)/src -I$(top_srcdir)/src \ MAINTAINERCLEANFILES = src/scan.c src/scan.h src/scan.stamp \ src/parse.c src/parse.h src/parse.stamp -CLEANFILES = src/typenames.h src/validtypes.h src/errtab.h +CLEANFILES = src/validtypes.h src/errtab.h -EXTRA_DIST = m4/gnulib-cache.m4 src/types.lst src/typenames.sed \ - src/validtypes.sed src/errors.lst src/strtab.sed \ +EXTRA_DIST = m4/gnulib-cache.m4 src/types.lst src/validtypes.sed \ + src/errors.lst src/strtab.sed \ src/parse.stamp src/scan.stamp \ COPYING.WTFPL2 @@ -39,7 +39,8 @@ lib_LTLIBRARIES = libcdecl.la libcdecl_la_LDFLAGS = -no-undefined \ -export-symbols-regex '^cdecl_[[:lower:]]' libcdecl_la_SOURCES = src/scan.c src/parse.c src/parse-decl.c src/typemap.c \ - src/output.c src/explain.c src/declare.c src/i18n.c src/error.c + src/output.c src/explain.c src/declare.c src/i18n.c src/error.c \ + src/normalize.c libcdecl_la_LIBADD = libgnu.la $(LTLIBINTL) $(LTLIBTHREAD) $(libcdecl_la_OBJECTS): $(gnulib_headers) @@ -51,18 +52,19 @@ $(cdecl99_OBJECTS): $(gnulib_headers) src/parse.lo: src/scan.h src/scan.lo: src/parse.h src/parse-decl.lo: src/scan.h src/parse.h -src/typemap.lo: src/validtypes.h src/typenames.h +src/typemap.lo: src/validtypes.h src/error.lo: src/errtab.h +src/normalize.lo: src/ordspecs.h src/validtypes.h: $(srcdir)/src/types.lst $(srcdir)/src/validtypes.sed $(AM_V_GEN)sed -f $(srcdir)/src/validtypes.sed \ < $(srcdir)/src/types.lst > $@.tmp $(AM_V_at)mv -f $@.tmp $@ -src/typenames.h: $(srcdir)/src/types.lst $(srcdir)/src/typenames.sed - $(AM_V_GEN)sed -f $(srcdir)/src/typenames.sed \ - < $(srcdir)/src/types.lst > $@.tmp - $(AM_V_at)mv -f $@.tmp $@ +src/ordspecs.h: $(srcdir)/src/specs.lst $(srcdir)/src/ordspecs.sed + $(AM_V_GEN) sed -f $(srcdir)/src/ordspecs.sed \ + < $(srcdir)/src/specs.lst > $@.tmp + $(AM_V_at) mv -f $@.tmp $@ src/errtab.h: $(srcdir)/src/errors.lst $(srcdir)/src/strtab.sed $(AM_V_GEN)sed -f $(srcdir)/src/strtab.sed \ diff --git a/src/.gitignore b/src/.gitignore index 8d792bc..50d03eb 100644 --- a/src/.gitignore +++ b/src/.gitignore @@ -3,5 +3,5 @@ parse.[ch] scan.stamp scan.[ch] validtypes.h -typenames.h +ordspecs.h errtab.h diff --git a/src/declare.c b/src/declare.c index 87efc3b..bae96f3 100644 --- a/src/declare.c +++ b/src/declare.c @@ -83,7 +83,7 @@ static size_t declare_pointer(char *buf, size_t n, struct cdecl_pointer *p) else ret += cdecl__advance_(&buf, &n, rc); - rc = cdecl__explain_qualifiers(buf, n, p->qualifiers); + rc = cdecl__explain_specs(buf, n, p->qualifiers, CDECL_SPEC_QUAL); return ret + cdecl__advance(&buf, &n, rc); } diff --git a/src/explain.c b/src/explain.c index 902784c..1b46d20 100644 --- a/src/explain.c +++ b/src/explain.c @@ -58,7 +58,7 @@ explain_pointer(char *buf, size_t n, struct cdecl_pointer *p) { size_t ret = 0, rc; - rc = cdecl__explain_qualifiers(buf, n, p->qualifiers); + rc = cdecl__explain_specs(buf, n, p->qualifiers, CDECL_SPEC_QUAL); ret += cdecl__advance(&buf, &n, rc); return ret + snprintf(buf, n, "pointer to"); diff --git a/src/normalize.c b/src/normalize.c new file mode 100644 index 0000000..704d575 --- /dev/null +++ b/src/normalize.c @@ -0,0 +1,143 @@ +/* + * Normalize C declaration specifier lists. + * 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 . + */ +#include +#include +#include + +#include "cdecl.h" +#include "normalize.h" + +/* + * Totally order the declaration specifier types by defining an injection into + * the natural numbers. + */ +static unsigned order_spec(struct cdecl_declspec *spec) +{ + switch (spec->type) { +# include "ordspecs.h" + default: + assert(0); + } +} + +static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b) +{ + return order_spec(a) - order_spec(b); +} + +/* + * Merge two sorted specifier lists. Each list must have at least one element. + */ +static struct cdecl_declspec * +merge_specs(struct cdecl_declspec *l1, size_t n1, + struct cdecl_declspec *l2, size_t n2) +{ + struct cdecl_declspec *top = l1, **p = ⊤ + + assert(n1 > 0 && n2 > 0); + + for (size_t i = 0, j = 0; i < n1 && j < n2;) { + int ord = compare_specs(l1, l2); + struct cdecl_declspec *tmp; + + if (ord <= 0) { + p = &l1->next; + l1 = l1->next; + i++; + } else if (ord > 0) { + tmp = l2->next; + l2->next = l1; + *p = l2; + p = &l2->next; + l2 = tmp; + + j++; + } + + if (!l1) + *p = l2; + } + + return top; +} + + +/* + * A simple merge sort. Set n to the number of elements in the list, or 0 + * to have the sort function count them. + */ +static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n) +{ + struct cdecl_declspec *l2, *c; + size_t i; + + /* Find the midpoint of the list. */ + if (n > 1) { + for (i = 0, l2 = l1; i < (n+1)/2; i++) + l2 = l2->next; + } else if (n == 0) { + for (i = 0, c = l2 = l1; c; i++, c = c->next) { + if (i % 2 == 0) + l2 = l2->next; + } + + n = i; + } + + assert(n != 0); + if (n == 1) { + l1->next = NULL; + return l1; + } + + /* l1 always has the longer "half". */ + l1 = sort_specs(l1, (n+1)/2); + l2 = sort_specs(l2, n/2); + + return merge_specs(l1, (n+1)/2, l2, n/2); +} + +/* + * C allows declaration specifiers to appear in any order, and allows arbitrary + * repetition of some kinds of specifiers. Normalize the specifier lists by + * sorting the specifiers and removing repeated function specifiers and type + * qualifiers. + */ +struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs) +{ + struct cdecl_declspec *c, *l; + + if (!specs) + return NULL; + + specs = sort_specs(specs, 0); + + for (c = specs, l = NULL; c; l = c, c = c->next) { + switch (cdecl_spec_kind(c)) { + case CDECL_SPEC_QUAL: + case CDECL_SPEC_FUNC: + if (l && l->type == c->type) { + l->next = c->next; + free(c); + c = l; + } + } + } + + return specs; +} diff --git a/src/normalize.h b/src/normalize.h new file mode 100644 index 0000000..3785df5 --- /dev/null +++ b/src/normalize.h @@ -0,0 +1,7 @@ +#ifndef CDECL_NORMALIZE_H_ +#define CDECL_NORMALIZE_H_ + +struct cdecl_declspec; +struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs); + +#endif diff --git a/src/ordspecs.sed b/src/ordspecs.sed new file mode 100644 index 0000000..7eb559c --- /dev/null +++ b/src/ordspecs.sed @@ -0,0 +1,24 @@ +1i\ +/*\ + * Copyright © 2011 Nick Bowler\ + *\ + * License WTFPL2: Do What The Fuck You Want To Public License, version 2.\ + * This is free software: you are free to do what the fuck you want to.\ + * There is NO WARRANTY, to the extent permitted by law.\ + */ +1i\ +/*\ + * This file is automatically generated by ordspecs.sed.\ + */ +/[^_[:alpha:][:space:]]/b +s/[[:space:]][[:space:]]*/ /g +s/_//g +y/abcdefghijklmnopqrstuvwxyz/ABCDEFGHIJKLMNOPQRSTUVWXYZ/ +s/\([[:upper:]]*\) \([[:upper:]]*\)/case CDECL_\1_\2:/ +p +i\ + return += +a\ + ; +d diff --git a/src/output.c b/src/output.c index cb2a568..3b4fa9f 100644 --- a/src/output.c +++ b/src/output.c @@ -48,9 +48,13 @@ size_t cdecl__advance(char **buf, size_t *n, size_t amount) return ret + cdecl__advance_(buf, n, rc); } -static size_t explain_storage(char *buf, size_t n, unsigned spec) +static size_t explain_spec(char *buf, size_t n, struct cdecl_declspec *s) { - switch (spec) { + switch (s->type) { + /* Function specifiers */ + case CDECL_FUNC_INLINE: + return snprintf(buf, n, "inline"); + /* Storage-class specifiers */ case CDECL_STOR_TYPEDEF: return snprintf(buf, n, "typedef"); case CDECL_STOR_EXTERN: @@ -61,93 +65,83 @@ static size_t explain_storage(char *buf, size_t n, unsigned spec) return snprintf(buf, n, "auto"); case CDECL_STOR_REGISTER: return snprintf(buf, n, "register"); + /* Type qualifiers */ + case CDECL_QUAL_RESTRICT: + return snprintf(buf, n, "restrict"); + case CDECL_QUAL_VOLATILE: + return snprintf(buf, n, "volatile"); + case CDECL_QUAL_CONST: + return snprintf(buf, n, "const"); + /* Type specifiers */ + case CDECL_TYPE_VOID: + return snprintf(buf, n, "void"); + case CDECL_TYPE_CHAR: + return snprintf(buf, n, "char"); + case CDECL_TYPE_SHORT: + return snprintf(buf, n, "short"); + case CDECL_TYPE_INT: + return snprintf(buf, n, "int"); + case CDECL_TYPE_LONG: + return snprintf(buf, n, "long"); + case CDECL_TYPE_FLOAT: + return snprintf(buf, n, "float"); + case CDECL_TYPE_DOUBLE: + return snprintf(buf, n, "double"); + case CDECL_TYPE_SIGNED: + return snprintf(buf, n, "signed"); + case CDECL_TYPE_UNSIGNED: + return snprintf(buf, n, "unsigned"); + case CDECL_TYPE_BOOL: + return snprintf(buf, n, "_Bool"); + case CDECL_TYPE_COMPLEX: + return snprintf(buf, n, "_Complex"); + case CDECL_TYPE_IMAGINARY: + return snprintf(buf, n, "_Imaginary"); + case CDECL_TYPE_STRUCT: + return snprintf(buf, n, "struct %s", s->ident); + case CDECL_TYPE_UNION: + return snprintf(buf, n, "union %s", s->ident); + case CDECL_TYPE_ENUM: + return snprintf(buf, n, "enum %s", s->ident); + case CDECL_TYPE_IDENT: + return snprintf(buf, n, "%s", s->ident); default: assert(0); } } -/* Renders the storage-class and function specifiers in canonical form. */ -size_t cdecl__explain_pre_specs(char *buf, size_t n, struct cdecl_declspec *s) +/* + * Render a list of declaration specifiers. Only the declaration specifiers + * listed in mask, which is the bitwise OR of the desired specifier kinds, are + * printed. + */ +size_t cdecl__explain_specs(char *buf, size_t n, struct cdecl_declspec *s, + unsigned mask) { - unsigned long funcmap = 0; size_t ret = 0, rc = 0; for (struct cdecl_declspec *c = s; c; c = c->next) { - switch (cdecl_spec_kind(c)) { + switch (cdecl_spec_kind(c) & mask) { case CDECL_SPEC_FUNC: - funcmap |= 1ul << (c->type & 0xff); - break; case CDECL_SPEC_STOR: - /* Valid C declarations have at most one - * storage-class specifier. */ - rc = explain_storage(buf, n, c->type); - break; + case CDECL_SPEC_QUAL: + case CDECL_SPEC_TYPE: + ret += cdecl__advance(&buf, &n, rc); + rc = explain_spec(buf, n, c); } } - if (funcmap & (1ul << (CDECL_FUNC_INLINE & 0xff))) { - ret += cdecl__advance(&buf, &n, rc); - rc = snprintf(buf, n, "inline"); - } - return ret + rc; } -size_t cdecl__explain_qualifiers(char *buf, size_t n, struct cdecl_declspec *s) +/* Renders the storage-class and function specifiers in canonical form. */ +size_t cdecl__explain_pre_specs(char *buf, size_t n, struct cdecl_declspec *s) { - unsigned long qualmap = 0; - size_t ret = 0, rc = 0; - - for (struct cdecl_declspec *c = s; c; c = c->next) { - if (cdecl_spec_kind(c) != CDECL_SPEC_QUAL) - continue; - qualmap |= 1ul << (c->type & 0xff); - } - - if (qualmap & (1ul << (CDECL_QUAL_RESTRICT & 0xff))) { - ret += cdecl__advance(&buf, &n, rc); - rc = snprintf(buf, n, "restrict"); - } - if (qualmap & (1ul << (CDECL_QUAL_VOLATILE & 0xff))) { - ret += cdecl__advance(&buf, &n, rc); - rc = snprintf(buf, n, "volatile"); - } - if (qualmap & (1ul << (CDECL_QUAL_CONST & 0xff))) { - ret += cdecl__advance(&buf, &n, rc); - rc = snprintf(buf, n, "const"); - } - - return ret + rc; + return cdecl__explain_specs(buf, n, s, CDECL_SPEC_FUNC|CDECL_SPEC_STOR); } /* Renders the type qualifiers and type specifiers in canonical form. */ size_t cdecl__explain_post_specs(char *buf, size_t n, struct cdecl_declspec *s) { - const char *tag = NULL; - unsigned long typemap; - size_t ret = 0, rc; - - typemap = cdecl__build_typemap(s); - if (typemap == -1) - return 0; - - for (struct cdecl_declspec *c = s; c; c = c->next) { - if (cdecl_spec_kind(c) != CDECL_SPEC_TYPE) - continue; - - /* Valid C types have at most one identifier. */ - if (c->ident) - tag = c->ident; - } - - rc = cdecl__explain_qualifiers(buf, n, s); - ret += cdecl__advance(&buf, &n, rc); - - rc = snprintf(buf, n, "%s", cdecl__explain_typemap(typemap)); - if (tag) { - ret += cdecl__advance(&buf, &n, rc); - rc = snprintf(buf, n, "%s", tag); - } - - return ret + rc; + return cdecl__explain_specs(buf, n, s, CDECL_SPEC_QUAL|CDECL_SPEC_TYPE); } diff --git a/src/output.h b/src/output.h index ecb9a75..28a13de 100644 --- a/src/output.h +++ b/src/output.h @@ -6,8 +6,9 @@ size_t cdecl__advance_(char **buf, size_t *n, size_t amount); size_t cdecl__advance(char **buf, size_t *n, size_t amount); +size_t cdecl__explain_specs(char *buf, size_t n, struct cdecl_declspec *s, + unsigned mask); size_t cdecl__explain_pre_specs(char *buf, size_t n, struct cdecl_declspec *s); -size_t cdecl__explain_qualifiers(char *buf, size_t n, struct cdecl_declspec *s); size_t cdecl__explain_post_specs(char *buf, size_t n, struct cdecl_declspec *s); #endif diff --git a/src/parse-decl.c b/src/parse-decl.c index e5395b4..42931a3 100644 --- a/src/parse-decl.c +++ b/src/parse-decl.c @@ -25,6 +25,7 @@ #include "parse.h" #include "scan.h" #include "i18n.h" +#include "normalize.h" /* * Determine if a declarator declares an identifier (other than a function @@ -349,6 +350,27 @@ check_arrays(struct cdecl_declarator **p, struct cdecl_declarator *d) return 0; } +static int +normalize_specs(struct cdecl_declarator **p, struct cdecl_declarator *d) +{ + struct cdecl_function *func; + struct cdecl_pointer *ptr; + + switch (d->type) { + case CDECL_DECL_POINTER: + ptr = &d->u.pointer; + ptr->qualifiers = cdecl__normalize_specs(ptr->qualifiers); + break; + case CDECL_DECL_FUNCTION: + func = &d->u.function; + for (struct cdecl *i = func->parameters; i; i = i->next) + i->specifiers = cdecl__normalize_specs(i->specifiers); + break; + } + + return 0; +} + /* * Traverse the parse tree, calling a function on every declarator in a * depth-first preorder traversal. The function is given a pointer to the @@ -388,6 +410,7 @@ static bool forall_declarators(struct cdecl *decl, struct cdecl *cdecl_parse_decl(const char *declstr) { + struct cdecl_declspec *norm_specs; YY_BUFFER_STATE state; yyscan_t scanner; struct cdecl *decl; @@ -407,7 +430,16 @@ struct cdecl *cdecl_parse_decl(const char *declstr) if (rc != 0) return NULL; + /* + * Since the top-level specifiers are shared between each top-level + * declarator, we need to normalize them once and then propagate the + * new specifier list. + */ + norm_specs = cdecl__normalize_specs(decl->specifiers); + for (struct cdecl *i = decl; i; i = i->next) { + i->specifiers = norm_specs; + if (!forall_declarators(i, reduce_parentheses)) goto err; if (!forall_declarators(i, simplify_functions)) @@ -418,6 +450,8 @@ struct cdecl *cdecl_parse_decl(const char *declstr) goto err; if (!forall_declarators(i, check_arrays)) goto err; + if (!forall_declarators(i, normalize_specs)) + goto err; if (!valid_declspecs(i, true)) goto err; @@ -456,12 +490,16 @@ struct cdecl *cdecl_parse_english(const char *english) return NULL; for (struct cdecl *i = decl; i; i = i->next) { + i->specifiers = cdecl__normalize_specs(i->specifiers); + if (!forall_declarators(i, check_parameters)) goto err; if (!forall_declarators(i, check_rettypes)) goto err; if (!forall_declarators(i, check_arrays)) goto err; + if (!forall_declarators(i, normalize_specs)) + goto err; if (!valid_declspecs(i, true)) goto err; diff --git a/src/specs.lst b/src/specs.lst new file mode 100644 index 0000000..d44c4d4 --- /dev/null +++ b/src/specs.lst @@ -0,0 +1,26 @@ +/* The complete list of declaration specifiers, in desired output order. */ +stor typedef +stor extern +stor static +stor auto +stor register +func inline +qual restrict +qual volatile +qual const +type void +type signed +type unsigned +type char +type short +type long +type int +type float +type double +type _Complex +type _Imaginary +type _Bool +type struct +type union +type enum +type ident diff --git a/src/typemap.c b/src/typemap.c index 1104868..a280be2 100644 --- a/src/typemap.c +++ b/src/typemap.c @@ -81,13 +81,3 @@ unsigned long cdecl__build_typemap(struct cdecl_declspec *s) return -1; } } - -const char *cdecl__explain_typemap(unsigned long map) -{ - switch (map) { -# include "typenames.h" - default: - fprintf(stderr, "invalid type specifiers\n"); - return NULL; - } -} diff --git a/src/typemap.h b/src/typemap.h index 10eeec3..d43afa7 100644 --- a/src/typemap.h +++ b/src/typemap.h @@ -4,6 +4,5 @@ #include "cdecl.h" unsigned long cdecl__build_typemap(struct cdecl_declspec *s); -const char *cdecl__explain_typemap(unsigned long map); #endif diff --git a/src/typenames.sed b/src/typenames.sed deleted file mode 100644 index d487a48..0000000 --- a/src/typenames.sed +++ /dev/null @@ -1,15 +0,0 @@ -1i\ -/* This file is automatically generated by typenames.sed */ -/[^_[:alpha:][:space:]]/b -s/[[:space:]][[:space:]]*/ /g -h -s/_//g -y/abcdefghijklmnopqrstuvwxyz/ABCDEFGHIJKLMNOPQRSTUVWXYZ/ -s/LONG LONG/LLONG LONG/ -s/[[:upper:]][[:upper:]]*/(1ul<<(CDECL_TYPE_&-CDECL_SPEC_TYPE))/g -s/ /|/g -s/.*/case &:/ -p -x -s/ident// -s/.*/ return "&";/ -- 2.43.2