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