src/parse-decl.c

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