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