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         free(d);
 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->child);
 266         free(d);
 267
 268         return 1;
 269 }
 270
 271 /*
 272  * The main parser's bias towards considering things as functions whenever
 273  * possible makes nested parentheses tricky.  "(x)" is considered to be part
 274  * of a function declarator until simplify_functions converts it.  The problem
 275  * is that "(((x)))" is not valid as part of a function declarator, but it _is_
 276  * valid as either an identifier enclosed thrice in parentheses, or an abstract
 277  * function declarator enclosed twice in parentheses.
 278  *
 279  * To avoid ambiguities, the main parser actually returns a function declarator
 280  * for every pair of parentheses.  The ones we need to look at consist of a
 281  * single parameter with an empty specifier list (noting that every real
 282  * function parameter will have at least one type specifier).
 283  *
 284  * There are two cases:
 285  *
 286  *   - For (), the parser emits a parameter with a lone null declarator.
 287  *     This fake parameter simply gets deleted, leaving us with a normal
 288  *     function declarator with an empty identifier list.
 289  *
 290  *   - Otherwise, the parameter's outermost declarator is not null.  The
 291  *     function itself is deleted, replaced in the parse tree with the
 292  *     fake parameter's declarator.
 293  *
 294  * Repeating until there no fake parameters, this reduction transforms, for
 295  * example, "(((x)))" into "(x)", an abstract function declarator.  The result
 296  * is then subject to the function simplification step, which will turn "(x)"
 297  * into x (declaring an identifier).
 298  *
 299  * The whole process is repeated until no more changes are made to the parse
 300  * tree, or a syntax error is detected.
 301  */
 302 static struct cdecl *fake_function_param(struct cdecl_declarator *d)
 303 {
 304         struct cdecl *param;
 305
 306         if (d->type != CDECL_DECL_FUNCTION)
 307                 return NULL;
 308
 309         param = d->u.function.parameters;
 310         if (!param || param->specifiers)
 311                 return NULL;
 312
 313         assert(!param->next);
 314         return param;
 315 }
 316
 317 static int
 318 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 319 {
 320         struct cdecl *param;
 321
 322         do {
 323                 d = *p;
 324                 while ((param = fake_function_param(d))) {
 325                         struct cdecl_declarator *decl = param->declarators;
 326                         d->u.function.parameters = NULL;
 327
 328                         if (decl->type != CDECL_DECL_NULL) {
 329                                 if (d->child->type != CDECL_DECL_NULL) {
 330                                         /* Fake parameter on real function. */
 331                                         d->u.function.parameters = param;
 332                                         cdecl__errmsg(CDECL__EBADPARAM);
 333                                         return -1;
 334                                 }
 335
 336                                 param->declarators = d;
 337                                 *p = d = decl;
 338                         }
 339
 340                         cdecl__free(param);
 341                 }
 342         } while (simplify_functions(p, d));
 343
 344         return 0;
 345 }
 346
 347 /*
 348  * Returns nonzero iff the given specifier list contains a specifier
 349  * of the indicated type.
 350  */
 351 static int have_specifier(struct cdecl_declspec *s, unsigned type)
 352 {
 353         for (; s; s = s->next)
 354                 if (s->type == type)
 355                         return 1;
 356         return 0;
 357 }
 358
 359 /*
 360  * Check syntax restrictions on a function declarator's child declarator.
 361  * That is, "pointer to function", "array of function" and "function
 362  * returning function".
 363  *
 364  * Returns -1 if the declaration is invalid, or 0 otherwise.
 365  */
 366 static int check_function_child(struct cdecl_declarator *d)
 367 {
 368         struct cdecl_pointer *ptr;
 369
 370         switch (d->type) {
 371         case CDECL_DECL_POINTER:
 372                 ptr = &d->u.pointer;
 373                 if (have_specifier(ptr->qualifiers, CDECL_QUAL_RESTRICT)) {
 374                         /* pointer to function cannot be restrict qualified. */
 375                         cdecl__errmsg(CDECL__ERESTRICTFUNC);
 376                         return -1;
 377                 }
 378                 return 0;
 379         case CDECL_DECL_FUNCTION:
 380                 /* function returning function is never allowed. */
 381                 cdecl__errmsg(CDECL__ERETFUNC);
 382                 return -1;
 383         case CDECL_DECL_ARRAY:
 384                 /* array of function is never allowed. */
 385                 cdecl__errmsg(CDECL__EFUNCARRAY);
 386                 return -1;
 387         }
 388
 389         return 0;
 390 }
 391
 392 /*
 393  * Check a function parameter declaration for validity, which means it has a
 394  * valid combination of declaration specifiers and, if it is a void parameter,
 395  * that it is the one special case where this is allowed.
 396  *
 397  * Returns -1 if the declaration is invalid, or 0 otherwise.
 398  */
 399 static int check_function_param(struct cdecl_function *f, struct cdecl *param)
 400 {
 401         if (!valid_declspecs(param, false))
 402                 return -1;
 403
 404         /* Check for "void" function parameters as a special case. */
 405         if (param->declarators->type == CDECL_DECL_NULL
 406             && have_specifier(param->specifiers, CDECL_TYPE_VOID))
 407         {
 408                 struct cdecl *fp = f->parameters;
 409
 410                 if (f->variadic || fp->next || fp->specifiers->next) {
 411                         cdecl__errmsg(CDECL__EVOIDPARAM);
 412                         return -1;
 413                 }
 414         }
 415
 416         return 0;
 417 }
 418
 419 /*
 420  * Normalize the specifier lists for function parameters, and then check the
 421  * function declarator for validity.
 422  *
 423  * Returns -1 if the declaration is invalid, or 0 otherwise.
 424  */
 425 static int postproc_function(struct cdecl_declarator *d)
 426 {
 427         struct cdecl_function *func = &d->u.function;
 428         struct cdecl *param;
 429         int rc;
 430
 431         for (param = func->parameters; param; param = param->next) {
 432                 param->specifiers = cdecl__normalize_specs(param->specifiers);
 433
 434                 if ((rc = check_function_param(func, param)) < 0)
 435                         return rc;
 436         }
 437
 438         return check_function_child(d->child);
 439 }
 440
 441 static int
 442 postproc_common(struct cdecl_declarator **p, struct cdecl_declarator *d)
 443 {
 444         struct cdecl_pointer *ptr;
 445
 446         switch (d->type) {
 447         case CDECL_DECL_POINTER:
 448                 ptr = &d->u.pointer;
 449                 ptr->qualifiers = cdecl__normalize_specs(ptr->qualifiers);
 450                 return 0;
 451         case CDECL_DECL_FUNCTION:
 452                 return postproc_function(d);
 453         case CDECL_DECL_ARRAY:
 454                 if (d->child && d->child->type == CDECL_DECL_FUNCTION) {
 455                         /* function returning array is never allowed. */
 456                         cdecl__errmsg(CDECL__ERETARRAY);
 457                         return -1;
 458                 }
 459                 return 0;
 460         }
 461
 462         return 0;
 463 }
 464
 465 /*
 466  * Traverse the parse tree, calling a function on every declarator in a
 467  * depth-first preorder traversal.  The function is given a pointer to the
 468  * declarator as well as to the pointer which was used to reach that
 469  * declarator: this can be used to rewrite entire subtrees.
 470  *
 471  * The called function may return a negative value to indicate an error
 472  * which terminates traversal.
 473  *
 474  * Returns 0 on success, or a negative value on failure.
 475  */
 476 static int forall_declarators(struct cdecl *decl,
 477         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 478 {
 479         struct cdecl_declarator *d, **p;
 480
 481         for (p = &decl->declarators; *p; p = &d->child) {
 482                 int rc;
 483
 484                 rc = f(p, *p);
 485                 if (rc < 0)
 486                         return rc;
 487                 d = *p;
 488
 489                 if (d->type == CDECL_DECL_FUNCTION) {
 490                         struct cdecl *i;
 491
 492                         for (i = d->u.function.parameters; i; i = i->next) {
 493                                 rc = forall_declarators(i, f);
 494                                 if (rc < 0)
 495                                         return rc;
 496                         }
 497                 }
 498         }
 499
 500         return 0;
 501 }
 502
 503 static struct cdecl *do_parse(const char *str, int english_mode)
 504 {
 505         YY_BUFFER_STATE state;
 506         yyscan_t scanner;
 507         struct cdecl *decl;
 508
 509 #if YYDEBUG
 510         extern int cdecl__yydebug;
 511         cdecl__yydebug = 1;
 512 #endif
 513
 514         cdecl__init_i18n();
 515         if (cdecl__yylex_init_extra(english_mode, &scanner) != 0)
 516                 return NULL;
 517
 518         state = cdecl__yy_scan_string(str, scanner);
 519         if (cdecl__yyparse(scanner, &decl) != 0)
 520                 decl = NULL;
 521         cdecl__yy_delete_buffer(state, scanner);
 522         cdecl__yylex_destroy(scanner);
 523
 524         return decl;
 525 }
 526
 527 static int do_postprocess(struct cdecl *decl, int english_mode)
 528 {
 529         struct cdecl_declspec *norm_specs;
 530         struct cdecl *i;
 531
 532         /*
 533          * For a C declaration with more than one full declarator, the
 534          * specifier list is common to all of them.  Normalize it once,
 535          * then propagate that to all the linked cdecl structures.
 536          *
 537          * In english mode, the cdecl structure list always has exactly
 538          * one entry so we don't need to do anything differently.
 539          */
 540         norm_specs = cdecl__normalize_specs(decl->specifiers);
 541         for (i = decl; i; i = i->next)
 542                 i->specifiers = norm_specs;
 543
 544         for (i = decl; i; i = i->next) {
 545                 if (!english_mode) {
 546                         if (forall_declarators(i, reduce_parentheses) < 0)
 547                                 return 0;
 548                 }
 549
 550                 if (forall_declarators(i, postproc_common) < 0)
 551                         return 0;
 552
 553                 if (!valid_declspecs(i, true))
 554                         return 0;
 555
 556                 if (decl->next && cdecl_is_abstract(i->declarators)) {
 557                         /* Abstract full declarators: there can only be one. */
 558                         cdecl__errmsg(CDECL__EDECLTYPE);
 559                         return 0;
 560                 }
 561         }
 562
 563         return 1;
 564 }
 565
 566 static struct cdecl *parse_common(const char *str, int english_mode)
 567 {
 568         struct cdecl *decl;
 569
 570         if (!(decl = do_parse(str, english_mode)))
 571                 return NULL;
 572
 573         if (!do_postprocess(decl, english_mode)) {
 574                 cdecl__free(decl);
 575                 return NULL;
 576         }
 577
 578         return decl;
 579 }
 580
 581 struct cdecl *cdecl_parse_decl(const char *declstr)
 582 {
 583         return parse_common(declstr, false);
 584 }
 585
 586 struct cdecl *cdecl_parse_english(const char *english)
 587 {
 588         return parse_common(english, true);
 589 }
 590
 591 void cdecl_free(struct cdecl *decl)
 592 {
 593         cdecl__free(decl);
 594 }