src/parse-decl.c

   1 /*
   2  *  Parse and validate C declarations.
   3  *  Copyright © 2011 Nick Bowler
   4  *
   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.
   9  *
  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.
  14  *
  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/>.
  17  */
  18 #include <stdio.h>
  19 #include <assert.h>
  20 #include <stdbool.h>
  21
  22 #include "cdecl.h"
  23 #include "typemap.h"
  24 #include "parse.h"
  25 #include "scan.h"
  26
  27 static int verify_declspecs(struct cdecl_declspec *s)
  28 {
  29         unsigned num_storage = 0;
  30         unsigned long typemap;
  31
  32         typemap = cdecl__build_typemap(s);
  33         if (typemap == -1)
  34                 return -1;
  35
  36         for (struct cdecl_declspec *c = s; c; c = c->next) {
  37                 switch (cdecl_spec_kind(c)) {
  38                 case CDECL_SPEC_TYPE:
  39                         continue;
  40                 case CDECL_SPEC_STOR:
  41                         if (++num_storage > 1) {
  42                                 fprintf(stderr, "too many storage-class specifiers\n");
  43                                 return -1;
  44                         }
  45                         break;
  46                 case CDECL_SPEC_QUAL:
  47                         /*
  48                          * Restrict qualifiers are only valid in the
  49                          * pointer qualifier list, which isn't checked here.
  50                          */
  51                         if (c->type == CDECL_QUAL_RESTRICT) {
  52                                 fprintf(stderr, "only pointer types can be restrict-qualified.\n");
  53                                 return -1;
  54                         }
  55                         break;
  56                 case CDECL_SPEC_FUNC:
  57                         /*
  58                          * We don't support functions yet.
  59                          */
  60                         fprintf(stderr, "only function declarations may have function specifiers.\n");
  61                         return -1;
  62                 default:
  63                         assert(0);
  64                 }
  65         }
  66
  67         return 0;
  68 }
  69
  70 /*
  71  * The C grammar leaves ambiguous some cases where parentheses represent a
  72  * function declarator or just parentheses.  The language uses additional
  73  * context (whether or not a typedef is in scope, etc.) to resolve these
  74  * ambiguities, but we don't have access to that kind of information.
  75  *
  76  * The cdecl99 parser uses an unambiguous grammar which treats almost
  77  * everything as a function, and thus considers things like 'int (x)' to
  78  * be a function type with a single parameter of type 'x' (a typedef name),
  79  * returning int.  This can result in very complicated types for simple
  80  * declarations.  Ideally, cdecl99 should try and find the "simplest"
  81  * explanation for a given declaration.
  82  *
  83  * Whether or not it achieves the simplest explanation, we apply a simple rule:
  84  * if a declarator could be interpreted as something other than a function,
  85  * do that.
  86  *
  87  *   - The function declarator has a null child declarator.
  88  *   - The function declarator has exactly one parameter, and is not variadic.
  89  *   - The function parameter has a type specifier, and it is a typedef name.
  90  *   - The function parameter has no other declaration specifiers.
  91  *   - The function parameter does not declare an identifier.
  92  *
  93  * Since cdecl99 supports things like [*] in any context (in C, such constructs
  94  * are only valid in function parameter lists), we don't treat them specially
  95  * here.
  96  */
  97
  98 static struct cdecl_declarator *reduce_function(struct cdecl *param)
  99 {
 100         struct cdecl_declspec   *spec = param->specifiers;
 101         struct cdecl_declarator *decl = param->declarators;
 102         struct cdecl_declarator *last;
 103
 104         for (last = decl; last && last->type != CDECL_DECL_NULL;)
 105                 last = last->child;
 106
 107         if (!last)
 108                 return NULL;
 109
 110         last->type = CDECL_DECL_IDENT;
 111         last->u.ident = spec->ident;
 112         free(param);
 113         free(spec);
 114
 115         return decl;
 116 }
 117
 118 static bool function_is_reducible(struct cdecl_declarator *d)
 119 {
 120         if (d->type != CDECL_DECL_FUNCTION)
 121                 return false;
 122         if (d->child->type != CDECL_DECL_NULL)
 123                 return false; /* e.g., int (*)(x) */
 124
 125         if (!d->u.function.parameters)
 126                 return false; /* e.g., int f() */
 127         if (d->u.function.parameters->next)
 128                 return false; /* e.g., int (x, y) */
 129         if (d->u.function.variadic)
 130                 return false; /* e.g., int (x, ...) */
 131
 132         if (d->u.function.parameters->specifiers->type != CDECL_TYPE_IDENT)
 133                 return false; /* e.g. int (int) */
 134         if (d->u.function.parameters->specifiers->next)
 135                 return false; /* e.g. int (size_t const) */
 136
 137         return true;
 138 }
 139
 140 static int
 141 simplify_functions(struct cdecl_declarator **p, struct cdecl_declarator *d)
 142 {
 143         struct cdecl_declarator *new;
 144
 145         if (!function_is_reducible(d))
 146                 return 0;
 147
 148         new = reduce_function(d->u.function.parameters);
 149         if (!new)
 150                 return 0; /* e.g. int (foo bar) */
 151         *p = new;
 152         free(d->child);
 153         free(d);
 154
 155         return 1;
 156 }
 157
 158 /*
 159  * The parser's bias towards considering things as functions whenever possible
 160  * makes nested parentheses tricky.  (x) is considered to be part of a function
 161  * declarator until simplify_functions converts it.  The problem is that
 162  * (((x))) is not valid as part of a function declarator, but it *is* valid
 163  * as an identifier enclosed 3 times in parentheses.  This is complicated by
 164  * the fact that things like (((int))) are not valid anywhere.
 165  *
 166  * To avoid ambiguities, the parser actually emits a "function" declarator for
 167  * every pair of parentheses.  The ones that can't reasonably be functions
 168  * consist of a single "parameter" with no declaration specifiers (note that
 169  * every valid function parameter will have at least one type specifier).
 170  *
 171  * This pass is to remove these fake functions from the parse tree.  We take
 172  * care to avoid turning invalid things like ((int)) into valid things like
 173  * (int) by observing that the only valid function declarators that appear
 174  * in these "fake" parentheses are those that have a non-null child declarator
 175  * (for instance, int ((*)(int)) *or* those that will be eliminated by the
 176  * simplify_functions pass.
 177  */
 178
 179 static int
 180 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 181 {
 182         struct cdecl *param;
 183
 184         if (d->type != CDECL_DECL_FUNCTION)
 185                 return 0;
 186
 187         param = d->u.function.parameters;
 188         if (param && param->specifiers == NULL) {
 189                 struct cdecl_declarator *decl;
 190
 191                 assert(!param->next);
 192
 193                 decl = param->declarators;
 194                 if (decl->type == CDECL_DECL_NULL) {
 195                         free(decl);
 196                         free(param);
 197                         d->u.function.parameters = NULL;
 198                         return 0;
 199                 }
 200
 201                 if (d->child->type != CDECL_DECL_NULL) {
 202                         fprintf(stderr, "invalid function parameter\n");
 203                         return -1;
 204                 }
 205
 206                 free(d->child);
 207                 free(param);
 208                 free(d);
 209                 *p = decl;
 210
 211                 /*
 212                  * We may have replaced d with another fake function which
 213                  * also needs to be eliminated.
 214                  */
 215                 if (reduce_parentheses(p, decl) < 0)
 216                         return -1;
 217
 218                 /*
 219                  * If the remaining declarator is a function, make sure it's
 220                  * valid by checking its reducibility.
 221                  */
 222                 decl = *p;
 223                 if (decl->type == CDECL_DECL_FUNCTION
 224                     && decl->child->type == CDECL_DECL_NULL
 225                     && !function_is_reducible(decl)) {
 226                         fprintf(stderr, "too many parentheses in function\n");
 227                         return -1;
 228                 }
 229
 230                 return 1;
 231         }
 232
 233         return 0;
 234 }
 235
 236 /*
 237  * Traverse the parse tree, calling a function on every declarator in a
 238  * depth-first preorder traversal.  The function is given a pointer to the
 239  * declarator as well as to the pointer which was used to reach that
 240  * declarator: this can be used to rewrite entire subtrees.
 241  */
 242 static bool forall_declarators(struct cdecl *decl,
 243         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 244 {
 245         struct cdecl_declarator *d, **p;
 246
 247         for (p = &decl->declarators, d = *p; d; p = &d->child, d = *p) {
 248                 switch (f(p, d)) {
 249                 case 0:
 250                         break;
 251                 case 1:
 252                         d = *p;
 253                         break;
 254                 case -1:
 255                         return false;
 256                 default:
 257                         assert(0);
 258                 }
 259
 260                 if (d->type == CDECL_DECL_FUNCTION) {
 261                         struct cdecl *i;
 262
 263                         for (i = d->u.function.parameters; i; i = i->next) {
 264                                 if (!forall_declarators(i, f))
 265                                         return false;
 266                         }
 267                 }
 268         }
 269
 270         return true;
 271 }
 272
 273 struct cdecl *cdecl_parse_decl(const char *declstr)
 274 {
 275         YY_BUFFER_STATE state;
 276         struct cdecl *decl;
 277         int rc;
 278
 279         state = yy_scan_string(declstr);
 280         rc = yyparse(&decl);
 281         yy_delete_buffer(state);
 282
 283         if (rc != 0)
 284                 return NULL;
 285
 286         if (verify_declspecs(decl->specifiers) != 0)
 287                 goto err;
 288
 289         for (struct cdecl *i = decl; i; i = i->next) {
 290                 if (!forall_declarators(i, reduce_parentheses))
 291                         goto err;
 292                 if (!forall_declarators(i, simplify_functions))
 293                         goto err;
 294         }
 295
 296         return decl;
 297 err:
 298         cdecl_free(decl);
 299         return NULL;
 300 }