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