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