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 parser's bias towards considering things as functions whenever possible
 238  * makes nested parentheses tricky.  (x) is considered to be part of a function
 239  * declarator until simplify_functions converts it.  The problem is that
 240  * (((x))) is not valid as part of a function declarator, but it *is* valid
 241  * as an identifier enclosed 3 times in parentheses.  This is complicated by
 242  * the fact that things like (((int))) are not valid anywhere.
 243  *
 244  * To avoid ambiguities, the parser actually emits a "function" declarator for
 245  * every pair of parentheses.  The ones that can't reasonably be functions
 246  * consist of a single "parameter" with no declaration specifiers (note that
 247  * every valid function parameter will have at least one type specifier).
 248  *
 249  * This pass is to remove these fake functions from the parse tree.  We take
 250  * care to avoid turning invalid things like ((int)) into valid things like
 251  * (int) by observing that the only valid function declarators that appear
 252  * in these "fake" parentheses are those that have a non-null child declarator
 253  * (for instance, int ((*)(int)) *or* those that will be eliminated by the
 254  * simplify_functions pass.
 255  */
 256
 257 static int
 258 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 259 {
 260         struct cdecl *param;
 261
 262         if (d->type != CDECL_DECL_FUNCTION)
 263                 return 0;
 264
 265         param = d->u.function.parameters;
 266         if (param && param->specifiers == NULL) {
 267                 struct cdecl_declarator *decl;
 268
 269                 assert(!param->next);
 270
 271                 decl = param->declarators;
 272                 if (decl->type == CDECL_DECL_NULL) {
 273                         free(decl);
 274                         free(param);
 275                         d->u.function.parameters = NULL;
 276                         return 0;
 277                 }
 278
 279                 if (d->child->type != CDECL_DECL_NULL) {
 280                         cdecl__errmsg(CDECL__EBADPARAM);
 281                         return -1;
 282                 }
 283
 284                 free(d->child);
 285                 free(param);
 286                 free(d);
 287                 *p = decl;
 288
 289                 /*
 290                  * We may have replaced d with another fake function which
 291                  * also needs to be eliminated.
 292                  */
 293                 if (reduce_parentheses(p, decl) < 0)
 294                         return -1;
 295
 296                 /*
 297                  * If the remaining declarator is a function, make sure it's
 298                  * valid by checking its reducibility.
 299                  */
 300                 decl = *p;
 301                 if (decl->type == CDECL_DECL_FUNCTION
 302                     && decl->child->type == CDECL_DECL_NULL
 303                     && !function_is_reducible(decl)) {
 304                         cdecl__errmsg(CDECL__EMANYPAREN);
 305                         return -1;
 306                 }
 307
 308                 return 1;
 309         }
 310
 311         return 0;
 312 }
 313
 314 /*
 315  * Function parameters and return types have a few restrictions that are
 316  * really easy to check in comparison to the above absurdity.
 317  */
 318 static int
 319 check_parameters(struct cdecl_declarator **p, struct cdecl_declarator *d)
 320 {
 321         struct cdecl_declspec *spec;
 322         struct cdecl *param;
 323
 324         if (d->type != CDECL_DECL_FUNCTION)
 325                 return 0;
 326
 327         for (param = d->u.function.parameters; param; param = param->next) {
 328                 if (!valid_declspecs(param, false))
 329                         return -1;
 330
 331                 /* Check for "void" function parameters as a special case. */
 332                 for (spec = param->specifiers; spec; spec = spec->next) {
 333                         if (param->declarators->type != CDECL_DECL_NULL)
 334                                 continue;
 335                         if (spec->type != CDECL_TYPE_VOID)
 336                                 continue;
 337
 338                         if (spec != param->specifiers || spec->next != NULL) {
 339                                 cdecl__errmsg(CDECL__EVOIDPARAM);
 340                                 return -1;
 341                         } else if (d->u.function.parameters->next) {
 342                                 cdecl__errmsg(CDECL__EVOIDPARAM);
 343                                 return -1;
 344                         } else if (d->u.function.variadic) {
 345                                 cdecl__errmsg(CDECL__EVOIDPARAM);
 346                                 return -1;
 347                         }
 348                 }
 349         }
 350
 351         return 0;
 352 }
 353
 354 /*
 355  * Functions cannot return arrays or functions.  Since the parse tree is
 356  * "inside-out", we need to look for functions as the child declarator.
 357  */
 358 static int
 359 check_rettypes(struct cdecl_declarator **p, struct cdecl_declarator *d)
 360 {
 361         if (!d->child || d->child->type != CDECL_DECL_FUNCTION)
 362                 return 0;
 363
 364         switch (d->type) {
 365         case CDECL_DECL_FUNCTION:
 366                 cdecl__errmsg(CDECL__ERETFUNC);
 367                 return -1;
 368         case CDECL_DECL_ARRAY:
 369                 cdecl__errmsg(CDECL__ERETARRAY);
 370                 return -1;
 371         }
 372
 373         return 0;
 374 }
 375
 376 static int
 377 check_arrays(struct cdecl_declarator **p, struct cdecl_declarator *d)
 378 {
 379         if (!d->child || d->child->type != CDECL_DECL_ARRAY)
 380                 return 0;
 381
 382         switch (d->type) {
 383         case CDECL_DECL_FUNCTION:
 384                 cdecl__errmsg(CDECL__EFUNCARRAY);
 385                 return -1;
 386         }
 387
 388         return 0;
 389 }
 390
 391 static int
 392 normalize_specs(struct cdecl_declarator **p, struct cdecl_declarator *d)
 393 {
 394         struct cdecl_function *func;
 395         struct cdecl_pointer *ptr;
 396
 397         switch (d->type) {
 398         case CDECL_DECL_POINTER:
 399                 ptr = &d->u.pointer;
 400                 ptr->qualifiers = cdecl__normalize_specs(ptr->qualifiers);
 401                 break;
 402         case CDECL_DECL_FUNCTION:
 403                 func = &d->u.function;
 404                 for (struct cdecl *i = func->parameters; i; i = i->next)
 405                         i->specifiers = cdecl__normalize_specs(i->specifiers);
 406                 break;
 407         }
 408
 409         return 0;
 410 }
 411
 412 static int
 413 check_qualifiers(struct cdecl_declarator **p, struct cdecl_declarator *d)
 414 {
 415         struct cdecl_declspec *spec;
 416         struct cdecl_pointer *ptr;
 417
 418         if (!d->child || d->child->type != CDECL_DECL_POINTER)
 419                 return 0;
 420
 421         ptr = &d->child->u.pointer;
 422         for (spec = ptr->qualifiers; spec; spec = spec->next) {
 423                 if (spec->type == CDECL_QUAL_RESTRICT
 424                     && d->type == CDECL_DECL_FUNCTION) {
 425                         cdecl__errmsg(CDECL__ERESTRICTFUNC);
 426                         return -1;
 427                 }
 428         }
 429
 430         return 0;
 431 }
 432
 433 /*
 434  * Traverse the parse tree, calling a function on every declarator in a
 435  * depth-first preorder traversal.  The function is given a pointer to the
 436  * declarator as well as to the pointer which was used to reach that
 437  * declarator: this can be used to rewrite entire subtrees.
 438  */
 439 static bool forall_declarators(struct cdecl *decl,
 440         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 441 {
 442         struct cdecl_declarator *d, **p;
 443
 444         for (p = &decl->declarators, d = *p; d; p = &d->child, d = *p) {
 445                 switch (f(p, d)) {
 446                 case 0:
 447                         break;
 448                 case 1:
 449                         d = *p;
 450                         break;
 451                 case -1:
 452                         return false;
 453                 default:
 454                         assert(0);
 455                 }
 456
 457                 if (d->type == CDECL_DECL_FUNCTION) {
 458                         struct cdecl *i;
 459
 460                         for (i = d->u.function.parameters; i; i = i->next) {
 461                                 if (!forall_declarators(i, f))
 462                                         return false;
 463                         }
 464                 }
 465         }
 466
 467         return true;
 468 }
 469
 470 static struct cdecl *do_parse(const char *str, int english_mode)
 471 {
 472         YY_BUFFER_STATE state;
 473         yyscan_t scanner;
 474         struct cdecl *decl;
 475
 476 #if YYDEBUG
 477         extern int cdecl__yydebug;
 478         cdecl__yydebug = 1;
 479 #endif
 480
 481         cdecl__init_i18n();
 482         if (cdecl__yylex_init_extra(english_mode, &scanner) != 0)
 483                 return NULL;
 484
 485         state = cdecl__yy_scan_string(str, scanner);
 486         if (cdecl__yyparse(scanner, &decl) != 0)
 487                 decl = NULL;
 488         cdecl__yy_delete_buffer(state, scanner);
 489         cdecl__yylex_destroy(scanner);
 490
 491         return decl;
 492 }
 493
 494 struct cdecl *cdecl_parse_decl(const char *declstr)
 495 {
 496         struct cdecl_declspec *norm_specs;
 497         struct cdecl *decl;
 498
 499         if (!(decl = do_parse(declstr, false)))
 500                 return NULL;
 501
 502         /*
 503          * Since the top-level specifiers are shared between each top-level
 504          * declarator, we need to normalize them once and then propagate the
 505          * new specifier list.
 506          */
 507         norm_specs = cdecl__normalize_specs(decl->specifiers);
 508         for (struct cdecl *i = decl; i; i = i->next) {
 509                 i->specifiers = norm_specs;
 510         }
 511
 512         /* Now perform checks and simplifications on each declarator. */
 513         for (struct cdecl *i = decl; i; i = i->next) {
 514                 if (!forall_declarators(i, reduce_parentheses))
 515                         goto err;
 516                 if (!forall_declarators(i, simplify_functions))
 517                         goto err;
 518                 if (!forall_declarators(i, check_parameters))
 519                         goto err;
 520                 if (!forall_declarators(i, check_rettypes))
 521                         goto err;
 522                 if (!forall_declarators(i, check_arrays))
 523                         goto err;
 524                 if (!forall_declarators(i, normalize_specs))
 525                         goto err;
 526                 if (!forall_declarators(i, check_qualifiers))
 527                         goto err;
 528
 529                 if (!valid_declspecs(i, true))
 530                         goto err;
 531
 532                 if (cdecl_is_abstract(i->declarators)
 533                     && (i != decl || i->next)) {
 534                         cdecl__errmsg(CDECL__EDECLTYPE);
 535                         goto err;
 536                 }
 537         }
 538
 539         return decl;
 540 err:
 541         cdecl__free(decl);
 542         return NULL;
 543 }
 544
 545 struct cdecl *cdecl_parse_english(const char *english)
 546 {
 547         struct cdecl *decl;
 548
 549         if (!(decl = do_parse(english, true)))
 550                 return NULL;
 551
 552         for (struct cdecl *i = decl; i; i = i->next) {
 553                 i->specifiers = cdecl__normalize_specs(i->specifiers);
 554
 555                 if (!forall_declarators(i, check_parameters))
 556                         goto err;
 557                 if (!forall_declarators(i, check_rettypes))
 558                         goto err;
 559                 if (!forall_declarators(i, check_arrays))
 560                         goto err;
 561                 if (!forall_declarators(i, normalize_specs))
 562                         goto err;
 563                 if (!forall_declarators(i, check_qualifiers))
 564                         goto err;
 565
 566                 if (!valid_declspecs(i, true))
 567                         goto err;
 568         }
 569
 570         return decl;
 571 err:
 572         cdecl__free(decl);
 573         return NULL;
 574 }
 575
 576 void cdecl_free(struct cdecl *decl)
 577 {
 578         cdecl__free(decl);
 579 }