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 /*
  28  * Determine if a declarator declares an identifier (other than a function
  29  * parameter).
  30  */
  31 static bool is_abstract(struct cdecl_declarator *d)
  32 {
  33         while (d->child)
  34                 d = d->child;
  35
  36         return d->type != CDECL_DECL_IDENT;
  37 }
  38
  39 /*
  40  * Verify the declaration specifiers of a declaration.  If top is true, treat
  41  * this as a top-level declaration.  Otherwise, treat this as a function
  42  * parameter (which carries additional constraints).
  43  */
  44 static bool valid_declspecs(struct cdecl *decl, bool top)
  45 {
  46         struct cdecl_declspec *specs = decl->specifiers;
  47         struct cdecl_declarator *d   = decl->declarators;
  48         bool abstract = is_abstract(d);
  49         unsigned num_storage = 0;
  50         unsigned long typemap;
  51
  52         typemap = cdecl__build_typemap(specs);
  53         if (typemap == -1)
  54                 return false;
  55
  56         for (struct cdecl_declspec *c = specs; c; c = c->next) {
  57                 switch (cdecl_spec_kind(c)) {
  58                 case CDECL_SPEC_TYPE:
  59                         if (c->type == CDECL_TYPE_VOID &&
  60                             (d->type == CDECL_DECL_IDENT
  61                              || d->type == CDECL_DECL_ARRAY)) {
  62                                 fprintf(stderr, "invalid declaration of type void\n");
  63                                 return false;
  64                         }
  65                         continue;
  66                 case CDECL_SPEC_STOR:
  67                         if (top && abstract) {
  68                                 fprintf(stderr, "type names cannot have storage-class specifiers\n");
  69                                 return false;
  70                         }
  71
  72                         if (!top && c->type != CDECL_STOR_REGISTER) {
  73                                 fprintf(stderr, "function parameters may only have register storage\n");
  74                                 return false;
  75                         }
  76
  77                         if (++num_storage > 1) {
  78                                 fprintf(stderr, "too many storage-class specifiers\n");
  79                                 return false;
  80                         }
  81                         break;
  82                 case CDECL_SPEC_QUAL:
  83                         /*
  84                          * Restrict qualifiers are only valid in the
  85                          * pointer qualifier list, which isn't checked here.
  86                          */
  87                         if (c->type == CDECL_QUAL_RESTRICT) {
  88                                 fprintf(stderr, "only pointer types can be restrict-qualified.\n");
  89                                 return false;
  90                         }
  91                         break;
  92                 case CDECL_SPEC_FUNC:
  93                         if (abstract) {
  94                                 fprintf(stderr, "type names cannot have function specifiers\n");
  95                                 return false;
  96                         }
  97
  98                         if (!top || d->type != CDECL_DECL_FUNCTION) {
  99                                 fprintf(stderr, "only function declarations may have function specifiers.\n");
 100                                 return false;
 101                         }
 102                         break;
 103                 default:
 104                         assert(0);
 105                 }
 106         }
 107
 108         return true;
 109 }
 110
 111 /*
 112  * The C grammar leaves ambiguous some cases where parentheses represent a
 113  * function declarator or just parentheses.  The language uses additional
 114  * context (whether or not a typedef is in scope, etc.) to resolve these
 115  * ambiguities, but we don't have access to that kind of information.
 116  *
 117  * The cdecl99 parser uses an unambiguous grammar which treats almost
 118  * everything as a function, and thus considers things like 'int (x)' to
 119  * be a function type with a single parameter of type 'x' (a typedef name),
 120  * returning int.  This can result in very complicated types for simple
 121  * declarations.  Ideally, cdecl99 should try and find the "simplest"
 122  * explanation for a given declaration.
 123  *
 124  * Whether or not it achieves the simplest explanation, we apply a simple rule:
 125  * if a declarator could be interpreted as something other than a function,
 126  * do that.
 127  *
 128  *   - The function declarator has a null child declarator.
 129  *   - The function declarator has exactly one parameter, and is not variadic.
 130  *   - The function parameter has a type specifier, and it is a typedef name.
 131  *   - The function parameter has no other declaration specifiers.
 132  *   - The function parameter does not declare an identifier.
 133  *
 134  * Since cdecl99 supports things like [*] in any context (in C, such constructs
 135  * are only valid in function parameter lists), we don't treat them specially
 136  * here.
 137  */
 138
 139 static struct cdecl_declarator *reduce_function(struct cdecl *param)
 140 {
 141         struct cdecl_declspec   *spec = param->specifiers;
 142         struct cdecl_declarator *decl = param->declarators;
 143         struct cdecl_declarator *last;
 144
 145         for (last = decl; last && last->type != CDECL_DECL_NULL;)
 146                 last = last->child;
 147
 148         if (!last)
 149                 return NULL;
 150
 151         last->type = CDECL_DECL_IDENT;
 152         last->u.ident = spec->ident;
 153         free(param);
 154         free(spec);
 155
 156         return decl;
 157 }
 158
 159 static bool function_is_reducible(struct cdecl_declarator *d)
 160 {
 161         if (d->type != CDECL_DECL_FUNCTION)
 162                 return false;
 163         if (d->child->type != CDECL_DECL_NULL)
 164                 return false; /* e.g., int (*)(x) */
 165
 166         if (!d->u.function.parameters)
 167                 return false; /* e.g., int f() */
 168         if (d->u.function.parameters->next)
 169                 return false; /* e.g., int (x, y) */
 170         if (d->u.function.variadic)
 171                 return false; /* e.g., int (x, ...) */
 172
 173         if (d->u.function.parameters->specifiers->type != CDECL_TYPE_IDENT)
 174                 return false; /* e.g. int (int) */
 175         if (d->u.function.parameters->specifiers->next)
 176                 return false; /* e.g. int (size_t const) */
 177
 178         return true;
 179 }
 180
 181 static int
 182 simplify_functions(struct cdecl_declarator **p, struct cdecl_declarator *d)
 183 {
 184         struct cdecl_declarator *new;
 185
 186         if (!function_is_reducible(d))
 187                 return 0;
 188
 189         new = reduce_function(d->u.function.parameters);
 190         if (!new)
 191                 return 0; /* e.g. int (foo bar) */
 192         *p = new;
 193         free(d->child);
 194         free(d);
 195
 196         return 1;
 197 }
 198
 199 /*
 200  * The parser's bias towards considering things as functions whenever possible
 201  * makes nested parentheses tricky.  (x) is considered to be part of a function
 202  * declarator until simplify_functions converts it.  The problem is that
 203  * (((x))) is not valid as part of a function declarator, but it *is* valid
 204  * as an identifier enclosed 3 times in parentheses.  This is complicated by
 205  * the fact that things like (((int))) are not valid anywhere.
 206  *
 207  * To avoid ambiguities, the parser actually emits a "function" declarator for
 208  * every pair of parentheses.  The ones that can't reasonably be functions
 209  * consist of a single "parameter" with no declaration specifiers (note that
 210  * every valid function parameter will have at least one type specifier).
 211  *
 212  * This pass is to remove these fake functions from the parse tree.  We take
 213  * care to avoid turning invalid things like ((int)) into valid things like
 214  * (int) by observing that the only valid function declarators that appear
 215  * in these "fake" parentheses are those that have a non-null child declarator
 216  * (for instance, int ((*)(int)) *or* those that will be eliminated by the
 217  * simplify_functions pass.
 218  */
 219
 220 static int
 221 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 222 {
 223         struct cdecl *param;
 224
 225         if (d->type != CDECL_DECL_FUNCTION)
 226                 return 0;
 227
 228         param = d->u.function.parameters;
 229         if (param && param->specifiers == NULL) {
 230                 struct cdecl_declarator *decl;
 231
 232                 assert(!param->next);
 233
 234                 decl = param->declarators;
 235                 if (decl->type == CDECL_DECL_NULL) {
 236                         free(decl);
 237                         free(param);
 238                         d->u.function.parameters = NULL;
 239                         return 0;
 240                 }
 241
 242                 if (d->child->type != CDECL_DECL_NULL) {
 243                         fprintf(stderr, "invalid function parameter\n");
 244                         return -1;
 245                 }
 246
 247                 free(d->child);
 248                 free(param);
 249                 free(d);
 250                 *p = decl;
 251
 252                 /*
 253                  * We may have replaced d with another fake function which
 254                  * also needs to be eliminated.
 255                  */
 256                 if (reduce_parentheses(p, decl) < 0)
 257                         return -1;
 258
 259                 /*
 260                  * If the remaining declarator is a function, make sure it's
 261                  * valid by checking its reducibility.
 262                  */
 263                 decl = *p;
 264                 if (decl->type == CDECL_DECL_FUNCTION
 265                     && decl->child->type == CDECL_DECL_NULL
 266                     && !function_is_reducible(decl)) {
 267                         fprintf(stderr, "too many parentheses in function\n");
 268                         return -1;
 269                 }
 270
 271                 return 1;
 272         }
 273
 274         return 0;
 275 }
 276
 277 /*
 278  * Function parameters and return types have a few restrictions that are
 279  * really easy to check in comparison to the above absurdity.
 280  */
 281 static int
 282 check_parameters(struct cdecl_declarator **p, struct cdecl_declarator *d)
 283 {
 284         struct cdecl_declspec *spec;
 285         struct cdecl *param;
 286         bool has_void = false;
 287
 288         if (d->type != CDECL_DECL_FUNCTION)
 289                 return 0;
 290
 291         for (param = d->u.function.parameters; param; param = param->next) {
 292                 if (!valid_declspecs(param, false))
 293                         return -1;
 294
 295                 for (spec = param->specifiers; spec; spec = spec->next) {
 296                         if (spec->type == CDECL_TYPE_VOID
 297                             && param->declarators->type == CDECL_DECL_NULL)
 298                                 has_void = true;
 299                 }
 300         }
 301
 302         if (has_void && d->u.function.parameters->next) {
 303                 fprintf(stderr, "a void parameter must stand alone\n");
 304                 return -1;
 305         } else if (has_void && d->u.function.variadic) {
 306                 fprintf(stderr, "variadic functions cannot have a void parameter\n");
 307                 return -1;
 308         }
 309
 310         return 0;
 311 }
 312
 313 /*
 314  * Functions cannot return arrays or functions.  Since the parse tree is
 315  * "inside-out", we need to look for functions as the child declarator.
 316  */
 317 static int
 318 check_rettypes(struct cdecl_declarator **p, struct cdecl_declarator *d)
 319 {
 320         if (!d->child || d->child->type != CDECL_DECL_FUNCTION)
 321                 return 0;
 322
 323         switch (d->type) {
 324         case CDECL_DECL_FUNCTION:
 325                 fprintf(stderr, "functions cannot return functions\n");
 326                 return -1;
 327         case CDECL_DECL_ARRAY:
 328                 fprintf(stderr, "functions cannot return arrays\n");
 329                 return -1;
 330         }
 331
 332         return 0;
 333 }
 334
 335 static int
 336 check_arrays(struct cdecl_declarator **p, struct cdecl_declarator *d)
 337 {
 338         if (!d->child || d->child->type != CDECL_DECL_ARRAY)
 339                 return 0;
 340
 341         switch (d->type) {
 342         case CDECL_DECL_FUNCTION:
 343                 fprintf(stderr, "array members cannot be functions\n");
 344                 return -1;
 345         }
 346
 347         return 0;
 348 }
 349
 350 /*
 351  * Traverse the parse tree, calling a function on every declarator in a
 352  * depth-first preorder traversal.  The function is given a pointer to the
 353  * declarator as well as to the pointer which was used to reach that
 354  * declarator: this can be used to rewrite entire subtrees.
 355  */
 356 static bool forall_declarators(struct cdecl *decl,
 357         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 358 {
 359         struct cdecl_declarator *d, **p;
 360
 361         for (p = &decl->declarators, d = *p; d; p = &d->child, d = *p) {
 362                 switch (f(p, d)) {
 363                 case 0:
 364                         break;
 365                 case 1:
 366                         d = *p;
 367                         break;
 368                 case -1:
 369                         return false;
 370                 default:
 371                         assert(0);
 372                 }
 373
 374                 if (d->type == CDECL_DECL_FUNCTION) {
 375                         struct cdecl *i;
 376
 377                         for (i = d->u.function.parameters; i; i = i->next) {
 378                                 if (!forall_declarators(i, f))
 379                                         return false;
 380                         }
 381                 }
 382         }
 383
 384         return true;
 385 }
 386
 387 struct cdecl *cdecl_parse_decl(const char *declstr)
 388 {
 389         YY_BUFFER_STATE state;
 390         yyscan_t scanner;
 391         struct cdecl *decl;
 392         int rc;
 393
 394         rc = yylex_init(&scanner);
 395         if (rc != 0)
 396                 return NULL;
 397
 398         state = yy_scan_string(declstr, scanner);
 399         rc = yyparse(scanner, &decl);
 400         yy_delete_buffer(state, scanner);
 401         yylex_destroy(scanner);
 402
 403         if (rc != 0)
 404                 return NULL;
 405
 406         for (struct cdecl *i = decl; i; i = i->next) {
 407                 if (!forall_declarators(i, reduce_parentheses))
 408                         goto err;
 409                 if (!forall_declarators(i, simplify_functions))
 410                         goto err;
 411                 if (!forall_declarators(i, check_parameters))
 412                         goto err;
 413                 if (!forall_declarators(i, check_rettypes))
 414                         goto err;
 415                 if (!forall_declarators(i, check_arrays))
 416                         goto err;
 417
 418                 if (!valid_declspecs(i, true))
 419                         goto err;
 420
 421                 if (is_abstract(i->declarators) && (i != decl || i->next)) {
 422                         fprintf(stderr, "mixing type names and declarations is not allowed\n");
 423                         goto err;
 424                 }
 425         }
 426
 427         return decl;
 428 err:
 429         cdecl_free(decl);
 430         return NULL;
 431 }
 432
 433 struct cdecl *cdecl_parse_english(const char *english)
 434 {
 435         YY_BUFFER_STATE state;
 436         yyscan_t scanner;
 437         struct cdecl *decl;
 438         int rc;
 439
 440         rc = yylex_init_extra(true, &scanner);
 441         if (rc != 0)
 442                 return NULL;
 443
 444         state = yy_scan_string(english, scanner);
 445         rc = yyparse(scanner, &decl);
 446         yy_delete_buffer(state, scanner);
 447         yylex_destroy(scanner);
 448
 449         if (rc != 0)
 450                 return NULL;
 451
 452         for (struct cdecl *i = decl; i; i = i->next) {
 453                 if (!forall_declarators(i, check_parameters))
 454                         goto err;
 455                 if (!forall_declarators(i, check_rettypes))
 456                         goto err;
 457                 if (!forall_declarators(i, check_arrays))
 458                         goto err;
 459
 460                 if (!valid_declspecs(i, true))
 461                         goto err;
 462         }
 463
 464         return decl;
 465 err:
 466         cdecl_free(decl);
 467         return NULL;
 468 }