src/parse-decl.c

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