src/parse-decl.c

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