src/parse-decl.c

   1 /*
   2  * Parse and validate C declarations.
   3  * Copyright © 2011-2012, 2020-2021, 2023-2024 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 #include "errmsg.h"
  29
  30 static struct cdecl *fake_function_param(struct cdecl_declarator *);
  31
  32 /*
  33  * Allocate a "parse item", which is a union of several parse tree
  34  * structure types, together with a string buffer.  The s_sz argument
  35  * specifies the size of the string (including its terminator), which
  36  * may be zero.
  37  *
  38  * The union's declarator member is pre-initialized to a valid "identifier"
  39  * declarator, which shares several interesting offsets with the "declspec"
  40  * structure for an "identifier" type specifier.
  41  */
  42 struct parse_item *cdecl__alloc_item(size_t s_sz)
  43 {
  44         struct parse_item *ret;
  45
  46         ret = malloc(offsetof(struct parse_item, s) + s_sz);
  47         if (!ret) {
  48                 cdecl__errmsg(CDECL__ENOMEM);
  49                 return NULL;
  50         }
  51
  52         ret->u.declarator.child   = NULL;
  53         ret->u.declarator.type    = CDECL_DECL_IDENT;
  54         ret->u.declarator.u.ident = ret->s;
  55
  56         return ret;
  57 }
  58
  59 /*
  60  * We can represent type specifiers as a bitmap, which gives us a finite
  61  * list of acceptable bitmap values according to the C standard.  However,
  62  * the "long" specifier is allowed to occur more than once, but only at most
  63  * 2 times.  Treat it as a special case, assigning an unused bit to represent
  64  * the second long.
  65  */
  66 #define MAP_LLONG_BIT 31
  67 #define MAP_LONG_BIT (CDECL_TYPE_LONG-CDECL_SPEC_TYPE)
  68 #define CDECL_TYPE_LLONG (CDECL_SPEC_TYPE+MAP_LLONG_BIT)
  69
  70 #include "typemap.h"
  71
  72 /*
  73  * Convert the declaration specifiers to a bitmap with each bit
  74  * corresponding to one specific type specifier.
  75  */
  76 static int valid_typespec(struct cdecl_declspec *s)
  77 {
  78         struct cdecl_declspec *c;
  79         unsigned long map = 0;
  80
  81         for (c = s; c; c = c->next) {
  82                 unsigned long bit;
  83
  84                 if (cdecl_spec_kind(c) != CDECL_SPEC_TYPE)
  85                         continue;
  86
  87                 bit = c->type - CDECL_SPEC_TYPE;
  88                 assert(bit < MAP_LLONG_BIT);
  89                 bit = 1ul << bit;
  90
  91                 /* "long" special case */
  92                 if ((map & bit) == 1ul << MAP_LONG_BIT)
  93                         bit = 1ul << MAP_LLONG_BIT;
  94
  95                 if (map & bit) {
  96                         if (bit == 1ul << MAP_LLONG_BIT)
  97                                 cdecl__errmsg(CDECL__ETOOLONG);
  98                         else
  99                                 cdecl__errmsg(CDECL__EDUPTYPE);
 100                         return false;
 101                 }
 102                 map |= bit;
 103         }
 104
 105         if (typemap_is_valid(map))
 106                 return true;
 107
 108         if (map == 0)
 109                 cdecl__errmsg(CDECL__ENOTYPE);
 110         else
 111                 cdecl__errmsg(CDECL__EBADTYPE);
 112
 113         return false;
 114 }
 115
 116 /*
 117  * Verify the declaration specifiers of a declaration.  If top is true, treat
 118  * this as a top-level declaration.  Otherwise, treat this as a function
 119  * parameter (which carries additional constraints).
 120  */
 121 static bool valid_declspecs(struct cdecl *decl, bool top)
 122 {
 123         struct cdecl_declspec *c, *specs = decl->specifiers;
 124         struct cdecl_declarator *d   = decl->declarators;
 125         bool abstract = cdecl_is_abstract(d);
 126         unsigned num_storage = 0;
 127
 128         if (!valid_typespec(specs))
 129                 return false;
 130
 131         for (c = specs; c; c = c->next) {
 132                 switch (cdecl_spec_kind(c)) {
 133                 case CDECL_SPEC_TYPE:
 134                         if (c->type == CDECL_TYPE_VOID &&
 135                             (d->type == CDECL_DECL_IDENT
 136                              || d->type == CDECL_DECL_ARRAY)) {
 137                                 cdecl__errmsg(CDECL__EBADVOID);
 138                                 return false;
 139                         }
 140                         continue;
 141                 case CDECL_SPEC_STOR:
 142                         if (top && abstract) {
 143                                 cdecl__errmsg(CDECL__ETYPESTOR);
 144                                 return false;
 145                         }
 146
 147                         if (!top && c->type != CDECL_STOR_REGISTER) {
 148                                 cdecl__errmsg(CDECL__EFUNCSTOR);
 149                                 return false;
 150                         }
 151
 152                         if (++num_storage > 1) {
 153                                 cdecl__errmsg(CDECL__EMANYSTOR);
 154                                 return false;
 155                         }
 156                         break;
 157                 case CDECL_SPEC_QUAL:
 158                         /*
 159                          * Restrict qualifiers are only valid in the
 160                          * pointer qualifier list, which isn't checked here.
 161                          */
 162                         if (c->type == CDECL_QUAL_RESTRICT) {
 163                                 cdecl__errmsg(CDECL__EBADQUAL);
 164                                 return false;
 165                         }
 166                         break;
 167                 case CDECL_SPEC_FUNC:
 168                         if (abstract || !top || d->type != CDECL_DECL_FUNCTION) {
 169                                 cdecl__errmsg(CDECL__ENOTFUNC);
 170                                 return false;
 171                         }
 172
 173                         break;
 174                 default:
 175                         assert(0);
 176                 }
 177         }
 178
 179         return true;
 180 }
 181
 182 /*
 183  * Find the tree pointer which leads to the parameter's leaf node.
 184  *
 185  * Return a null pointer if the traversal locates a syntactic element which
 186  * prevents function reduction.  This occurs if the leaf node declares an
 187  * identifier, or for nontrivial fake function parameters (see below).
 188  */
 189 static struct cdecl_declarator **leaf_pointer(struct cdecl *param)
 190 {
 191         struct cdecl_declarator *d, **p = &param->declarators;
 192
 193         if ((param = fake_function_param(param->declarators))) {
 194                 if (param->declarators->type != CDECL_DECL_NULL)
 195                         return NULL; /* e.g. int (x (*)) */
 196         }
 197
 198         while ((d = *p)->child) {
 199                 p = &d->child;
 200
 201                 if (fake_function_param(d->child))
 202                         return NULL; /* e.g. int (x (*)[][1]) */
 203         }
 204
 205         if (d->type != CDECL_DECL_NULL)
 206                 return NULL; /* e.g. int (x y) */
 207
 208         return p;
 209 }
 210
 211
 212 /*
 213  * The C grammar leaves ambiguous some cases where parentheses represent a
 214  * function declarator or just parentheses.  The language uses additional
 215  * context (whether or not a typedef is in scope, etc.) to resolve these
 216  * ambiguities, but we don't have access to that kind of information.
 217  *
 218  * The cdecl99 parser uses an unambiguous grammar which treats almost
 219  * everything as a function, and thus considers things like 'int (x)' to
 220  * be a function type with a single parameter of type 'x' (a typedef name),
 221  * returning int.  This can result in very complicated types for simple
 222  * declarations.  Ideally, cdecl99 should try and find the "simplest"
 223  * explanation for a given declaration.
 224  *
 225  * Whether or not it achieves the simplest explanation, we apply a simple rule:
 226  * if a declarator could be interpreted as something other than a function,
 227  * do that.
 228  *
 229  * Since cdecl99 supports things like [*] in any context (in C, such constructs
 230  * are only valid in function parameter lists), we don't treat them specially
 231  * here.
 232  */
 233
 234 static struct cdecl_declarator *reduce_function(struct cdecl *param)
 235 {
 236         struct parse_item *spec = (void *)param->specifiers;
 237         struct cdecl_declarator *d, **p;
 238
 239         if (!(p = leaf_pointer(param)))
 240                 return NULL;
 241
 242         /*
 243          * The child and u.ident members of cdecl_declarator are expected
 244          * to be located at identical offsets as, respectively, the next
 245          * and ident members within cdecl_declspec, so the expectation is
 246          * that the compiler can elide both assignments.
 247          */
 248         spec->u.declarator.child = (void *)spec->u.declspec.next;
 249         spec->u.declarator.u.ident = spec->u.declspec.ident;
 250         spec->u.declarator.type = CDECL_DECL_IDENT;
 251         *p = &spec->u.declarator;
 252
 253         d = param->declarators;
 254         free(param);
 255         return d;
 256 }
 257
 258 static bool function_is_reducible(struct cdecl_declarator *d)
 259 {
 260         if (d->type != CDECL_DECL_FUNCTION)
 261                 return false;
 262         if (d->child->type != CDECL_DECL_NULL)
 263                 return false; /* e.g., int (*)(x) */
 264
 265         if (!d->u.function.parameters)
 266                 return false; /* e.g., int f() */
 267         if (d->u.function.parameters->next)
 268                 return false; /* e.g., int (x, y) */
 269         if (d->u.function.variadic)
 270                 return false; /* e.g., int (x, ...) */
 271
 272         if (d->u.function.parameters->specifiers->type != CDECL_TYPE_IDENT)
 273                 return false; /* e.g. int (int) */
 274         if (d->u.function.parameters->specifiers->next)
 275                 return false; /* e.g. int (size_t const) */
 276         if (d->u.function.parameters->declarators->type == CDECL_DECL_POINTER)
 277                 return false; /* e.g. int (x *) */
 278
 279         return true;
 280 }
 281
 282 static int
 283 simplify_functions(struct cdecl_declarator **p, struct cdecl_declarator *d)
 284 {
 285         struct cdecl_declarator *new;
 286
 287         if (!function_is_reducible(d))
 288                 return 0;
 289
 290         new = reduce_function(d->u.function.parameters);
 291         if (!new)
 292                 return 0;
 293         *p = new;
 294         free(d);
 295
 296         return 1;
 297 }
 298
 299 /*
 300  * The main parser's bias towards considering things as functions whenever
 301  * possible makes nested parentheses tricky.  "(x)" is considered to be part
 302  * of a function declarator until simplify_functions converts it.  The problem
 303  * is that "(((x)))" is not valid as part of a function declarator, but it _is_
 304  * valid as either an identifier enclosed thrice in parentheses, or an abstract
 305  * function declarator enclosed twice in parentheses.
 306  *
 307  * To avoid ambiguities, the main parser actually returns a function declarator
 308  * for every pair of parentheses.  The ones we need to look at consist of a
 309  * single parameter with an empty specifier list (noting that every real
 310  * function parameter will have at least one type specifier).
 311  *
 312  * There are two cases:
 313  *
 314  *   - For (), the parser emits a parameter with a lone null declarator.
 315  *     This fake parameter simply gets deleted, leaving us with a normal
 316  *     function declarator with an empty identifier list.
 317  *
 318  *   - Otherwise, the parameter's outermost declarator is not null.  The
 319  *     function itself is deleted, replaced in the parse tree with the
 320  *     fake parameter's declarator.
 321  *
 322  * Repeating until there no fake parameters, this reduction transforms, for
 323  * example, "(((x)))" into "(x)", an abstract function declarator.  The result
 324  * is then subject to the function simplification step, which will turn "(x)"
 325  * into x (declaring an identifier).
 326  *
 327  * The whole process is repeated until no more changes are made to the parse
 328  * tree, or a syntax error is detected.
 329  */
 330 static struct cdecl *fake_function_param(struct cdecl_declarator *d)
 331 {
 332         struct cdecl *param;
 333
 334         if (d->type != CDECL_DECL_FUNCTION)
 335                 return NULL;
 336
 337         param = d->u.function.parameters;
 338         if (!param || param->specifiers)
 339                 return NULL;
 340
 341         assert(!param->next);
 342         return param;
 343 }
 344
 345 static int
 346 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 347 {
 348         struct cdecl *param;
 349
 350         do {
 351                 d = *p;
 352                 while ((param = fake_function_param(d))) {
 353                         struct cdecl_declarator *decl = param->declarators;
 354                         d->u.function.parameters = NULL;
 355
 356                         if (decl->type != CDECL_DECL_NULL) {
 357                                 if (d->child->type != CDECL_DECL_NULL) {
 358                                         /* Fake parameter on real function. */
 359                                         d->u.function.parameters = param;
 360                                         cdecl__errmsg(CDECL__EBADPARAM);
 361                                         return -1;
 362                                 }
 363
 364                                 param->declarators = d;
 365                                 *p = d = decl;
 366                         }
 367
 368                         cdecl__free(param);
 369                 }
 370         } while (simplify_functions(p, d));
 371
 372         return 0;
 373 }
 374
 375 /*
 376  * Returns nonzero iff the given specifier list contains a specifier
 377  * of the indicated type.
 378  */
 379 static int have_specifier(struct cdecl_declspec *s, unsigned type)
 380 {
 381         for (; s; s = s->next)
 382                 if (s->type == type)
 383                         return 1;
 384         return 0;
 385 }
 386
 387 /*
 388  * Check syntax restrictions on a function declarator's child declarator.
 389  * That is, "pointer to function", "array of function" and "function
 390  * returning function".
 391  *
 392  * Returns -1 if the declaration is invalid, or 0 otherwise.
 393  */
 394 static int check_function_child(struct cdecl_declarator *d)
 395 {
 396         struct cdecl_pointer *ptr;
 397
 398         switch (d->type) {
 399         case CDECL_DECL_POINTER:
 400                 ptr = &d->u.pointer;
 401                 if (have_specifier(ptr->qualifiers, CDECL_QUAL_RESTRICT)) {
 402                         /* pointer to function cannot be restrict qualified. */
 403                         cdecl__errmsg(CDECL__ERESTRICTFUNC);
 404                         return -1;
 405                 }
 406                 return 0;
 407         case CDECL_DECL_FUNCTION:
 408                 /* function returning function is never allowed. */
 409                 cdecl__errmsg(CDECL__ERETFUNC);
 410                 return -1;
 411         case CDECL_DECL_ARRAY:
 412                 /* array of function is never allowed. */
 413                 cdecl__errmsg(CDECL__EFUNCARRAY);
 414                 return -1;
 415         }
 416
 417         return 0;
 418 }
 419
 420 /*
 421  * Check a function parameter declaration for validity, which means it has a
 422  * valid combination of declaration specifiers and, if it is a void parameter,
 423  * that it is the one special case where this is allowed.
 424  *
 425  * Returns -1 if the declaration is invalid, or 0 otherwise.
 426  */
 427 static int check_function_param(struct cdecl_function *f, struct cdecl *param)
 428 {
 429         if (!valid_declspecs(param, false))
 430                 return -1;
 431
 432         /* Check for "void" function parameters as a special case. */
 433         if (param->declarators->type == CDECL_DECL_NULL
 434             && have_specifier(param->specifiers, CDECL_TYPE_VOID))
 435         {
 436                 struct cdecl *fp = f->parameters;
 437
 438                 if (f->variadic || fp->next || fp->specifiers->next) {
 439                         cdecl__errmsg(CDECL__EVOIDPARAM);
 440                         return -1;
 441                 }
 442         }
 443
 444         return 0;
 445 }
 446
 447 /*
 448  * Normalize the specifier lists for function parameters, and then check the
 449  * function declarator for validity.
 450  *
 451  * Returns -1 if the declaration is invalid, or 0 otherwise.
 452  */
 453 static int postproc_function(struct cdecl_declarator *d)
 454 {
 455         struct cdecl_function *func = &d->u.function;
 456         struct cdecl *param;
 457         int rc;
 458
 459         for (param = func->parameters; param; param = param->next) {
 460                 param->specifiers = cdecl__normalize_specs(param->specifiers);
 461
 462                 if ((rc = check_function_param(func, param)) < 0)
 463                         return rc;
 464         }
 465
 466         return check_function_child(d->child);
 467 }
 468
 469 static int
 470 postproc_common(struct cdecl_declarator **p, struct cdecl_declarator *d)
 471 {
 472         struct cdecl_pointer *ptr;
 473
 474         switch (d->type) {
 475         case CDECL_DECL_POINTER:
 476                 ptr = &d->u.pointer;
 477                 ptr->qualifiers = cdecl__normalize_specs(ptr->qualifiers);
 478                 return 0;
 479         case CDECL_DECL_FUNCTION:
 480                 return postproc_function(d);
 481         case CDECL_DECL_ARRAY:
 482                 if (d->child && d->child->type == CDECL_DECL_FUNCTION) {
 483                         /* function returning array is never allowed. */
 484                         cdecl__errmsg(CDECL__ERETARRAY);
 485                         return -1;
 486                 }
 487                 return 0;
 488         }
 489
 490         return 0;
 491 }
 492
 493 /*
 494  * Traverse the parse tree, calling a function on every declarator in a
 495  * depth-first preorder traversal.  The function is given a pointer to the
 496  * declarator as well as to the pointer which was used to reach that
 497  * declarator: this can be used to rewrite entire subtrees.
 498  *
 499  * The called function may return a negative value to indicate an error
 500  * which terminates traversal.
 501  *
 502  * Returns 0 on success, or a negative value on failure.
 503  */
 504 static int forall_declarators(struct cdecl *decl,
 505         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 506 {
 507         struct cdecl_declarator *d, **p;
 508
 509         for (p = &decl->declarators; *p; p = &d->child) {
 510                 int rc;
 511
 512                 rc = f(p, *p);
 513                 if (rc < 0)
 514                         return rc;
 515                 d = *p;
 516
 517                 if (d->type == CDECL_DECL_FUNCTION) {
 518                         struct cdecl *i;
 519
 520                         for (i = d->u.function.parameters; i; i = i->next) {
 521                                 rc = forall_declarators(i, f);
 522                                 if (rc < 0)
 523                                         return rc;
 524                         }
 525                 }
 526         }
 527
 528         return 0;
 529 }
 530
 531 static struct cdecl *do_parse(const char *str, int english_mode)
 532 {
 533         struct cdecl *decl = NULL;
 534         YY_BUFFER_STATE state;
 535         yyscan_t scanner;
 536
 537 #if YYDEBUG
 538         extern int cdecl__yydebug;
 539         cdecl__yydebug = 1;
 540 #endif
 541
 542         cdecl__init_i18n();
 543         if (cdecl__yylex_init_extra(english_mode, &scanner) != 0)
 544                 return NULL;
 545
 546         state = cdecl__yy_scan_string(str, scanner);
 547         if (cdecl__yyparse(scanner, &decl) != 0) {
 548                 /*
 549                  * If the input consists of a complete, valid declaration
 550                  * followed by some garbage, that parsed declaration will
 551                  * be output by the parser and we need to free it here.
 552                  */
 553                 cdecl__free(decl);
 554                 decl = NULL;
 555         }
 556         cdecl__yy_delete_buffer(state, scanner);
 557         cdecl__yylex_destroy(scanner);
 558
 559         return decl;
 560 }
 561
 562 static int do_postprocess(struct cdecl *decl, int english_mode)
 563 {
 564         struct cdecl_declspec *norm_specs;
 565         struct cdecl *i;
 566
 567         /*
 568          * For a C declaration with more than one full declarator, the
 569          * specifier list is common to all of them.  Normalize it once,
 570          * then propagate that to all the linked cdecl structures.
 571          *
 572          * In english mode, the cdecl structure list always has exactly
 573          * one entry so we don't need to do anything differently.
 574          */
 575         norm_specs = cdecl__normalize_specs(decl->specifiers);
 576         for (i = decl; i; i = i->next)
 577                 i->specifiers = norm_specs;
 578
 579         for (i = decl; i; i = i->next) {
 580                 if (!english_mode) {
 581                         if (forall_declarators(i, reduce_parentheses) < 0)
 582                                 return 0;
 583                 }
 584
 585                 if (forall_declarators(i, postproc_common) < 0)
 586                         return 0;
 587
 588                 if (!valid_declspecs(i, true))
 589                         return 0;
 590
 591                 if (decl->next && cdecl_is_abstract(i->declarators)) {
 592                         /* Abstract full declarators: there can only be one. */
 593                         cdecl__errmsg(CDECL__EDECLTYPE);
 594                         return 0;
 595                 }
 596         }
 597
 598         return 1;
 599 }
 600
 601 static struct cdecl *parse_common(const char *str, int english_mode)
 602 {
 603         struct cdecl *decl;
 604
 605         if (!(decl = do_parse(str, english_mode)))
 606                 return NULL;
 607
 608         if (!do_postprocess(decl, english_mode)) {
 609                 cdecl__free(decl);
 610                 return NULL;
 611         }
 612
 613         return decl;
 614 }
 615
 616 struct cdecl *cdecl_parse_decl(const char *declstr)
 617 {
 618         return parse_common(declstr, false);
 619 }
 620
 621 struct cdecl *cdecl_parse_english(const char *english)
 622 {
 623         return parse_common(english, true);
 624 }
 625
 626 void cdecl_free(struct cdecl *decl)
 627 {
 628         cdecl__free(decl);
 629 }