src/parse-decl.c

   1 /*
   2  *  Parse and validate C declarations.
   3  *  Copyright © 2011 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 <http://www.gnu.org/licenses/>.
  17  */
  18 #include <config.h>
  19 #include <stdio.h>
  20 #include <assert.h>
  21 #include <stdbool.h>
  22
  23 #include "cdecl.h"
  24 #include "typemap.h"
  25 #include "parse.h"
  26 #include "scan.h"
  27 #include "i18n.h"
  28
  29 /*
  30  * Determine if a declarator declares an identifier (other than a function
  31  * parameter).
  32  */
  33 static bool is_abstract(struct cdecl_declarator *d)
  34 {
  35         while (d->child)
  36                 d = d->child;
  37
  38         return d->type != CDECL_DECL_IDENT;
  39 }
  40
  41 /*
  42  * Verify the declaration specifiers of a declaration.  If top is true, treat
  43  * this as a top-level declaration.  Otherwise, treat this as a function
  44  * parameter (which carries additional constraints).
  45  */
  46 static bool valid_declspecs(struct cdecl *decl, bool top)
  47 {
  48         struct cdecl_declspec *specs = decl->specifiers;
  49         struct cdecl_declarator *d   = decl->declarators;
  50         bool abstract = is_abstract(d);
  51         unsigned num_storage = 0;
  52         unsigned long typemap;
  53
  54         typemap = cdecl__build_typemap(specs);
  55         if (typemap == -1)
  56                 return false;
  57
  58         for (struct cdecl_declspec *c = specs; c; c = c->next) {
  59                 switch (cdecl_spec_kind(c)) {
  60                 case CDECL_SPEC_TYPE:
  61                         if (c->type == CDECL_TYPE_VOID &&
  62                             (d->type == CDECL_DECL_IDENT
  63                              || d->type == CDECL_DECL_ARRAY)) {
  64                                 fprintf(stderr, "invalid declaration of type void\n");
  65                                 return false;
  66                         }
  67                         continue;
  68                 case CDECL_SPEC_STOR:
  69                         if (top && abstract) {
  70                                 fprintf(stderr, "type names cannot have storage-class specifiers\n");
  71                                 return false;
  72                         }
  73
  74                         if (!top && c->type != CDECL_STOR_REGISTER) {
  75                                 fprintf(stderr, "function parameters may only have register storage\n");
  76                                 return false;
  77                         }
  78
  79                         if (++num_storage > 1) {
  80                                 fprintf(stderr, "too many storage-class specifiers\n");
  81                                 return false;
  82                         }
  83                         break;
  84                 case CDECL_SPEC_QUAL:
  85                         /*
  86                          * Restrict qualifiers are only valid in the
  87                          * pointer qualifier list, which isn't checked here.
  88                          */
  89                         if (c->type == CDECL_QUAL_RESTRICT) {
  90                                 fprintf(stderr, "only pointer types can be restrict-qualified.\n");
  91                                 return false;
  92                         }
  93                         break;
  94                 case CDECL_SPEC_FUNC:
  95                         if (abstract) {
  96                                 fprintf(stderr, "type names cannot have function specifiers\n");
  97                                 return false;
  98                         }
  99
 100                         if (!top || d->type != CDECL_DECL_FUNCTION) {
 101                                 fprintf(stderr, "only function declarations may have function specifiers.\n");
 102                                 return false;
 103                         }
 104                         break;
 105                 default:
 106                         assert(0);
 107                 }
 108         }
 109
 110         return true;
 111 }
 112
 113 /*
 114  * The C grammar leaves ambiguous some cases where parentheses represent a
 115  * function declarator or just parentheses.  The language uses additional
 116  * context (whether or not a typedef is in scope, etc.) to resolve these
 117  * ambiguities, but we don't have access to that kind of information.
 118  *
 119  * The cdecl99 parser uses an unambiguous grammar which treats almost
 120  * everything as a function, and thus considers things like 'int (x)' to
 121  * be a function type with a single parameter of type 'x' (a typedef name),
 122  * returning int.  This can result in very complicated types for simple
 123  * declarations.  Ideally, cdecl99 should try and find the "simplest"
 124  * explanation for a given declaration.
 125  *
 126  * Whether or not it achieves the simplest explanation, we apply a simple rule:
 127  * if a declarator could be interpreted as something other than a function,
 128  * do that.
 129  *
 130  *   - The function declarator has a null child declarator.
 131  *   - The function declarator has exactly one parameter, and is not variadic.
 132  *   - The function parameter has a type specifier, and it is a typedef name.
 133  *   - The function parameter has no other declaration specifiers.
 134  *   - The function parameter does not declare an identifier.
 135  *
 136  * Since cdecl99 supports things like [*] in any context (in C, such constructs
 137  * are only valid in function parameter lists), we don't treat them specially
 138  * here.
 139  */
 140
 141 static struct cdecl_declarator *reduce_function(struct cdecl *param)
 142 {
 143         struct cdecl_declspec   *spec = param->specifiers;
 144         struct cdecl_declarator *decl = param->declarators;
 145         struct cdecl_declarator *last;
 146
 147         for (last = decl; last && last->type != CDECL_DECL_NULL;)
 148                 last = last->child;
 149
 150         if (!last)
 151                 return NULL;
 152
 153         last->type = CDECL_DECL_IDENT;
 154         last->u.ident = spec->ident;
 155         free(param);
 156         free(spec);
 157
 158         return decl;
 159 }
 160
 161 static bool function_is_reducible(struct cdecl_declarator *d)
 162 {
 163         if (d->type != CDECL_DECL_FUNCTION)
 164                 return false;
 165         if (d->child->type != CDECL_DECL_NULL)
 166                 return false; /* e.g., int (*)(x) */
 167
 168         if (!d->u.function.parameters)
 169                 return false; /* e.g., int f() */
 170         if (d->u.function.parameters->next)
 171                 return false; /* e.g., int (x, y) */
 172         if (d->u.function.variadic)
 173                 return false; /* e.g., int (x, ...) */
 174
 175         if (d->u.function.parameters->specifiers->type != CDECL_TYPE_IDENT)
 176                 return false; /* e.g. int (int) */
 177         if (d->u.function.parameters->specifiers->next)
 178                 return false; /* e.g. int (size_t const) */
 179
 180         return true;
 181 }
 182
 183 static int
 184 simplify_functions(struct cdecl_declarator **p, struct cdecl_declarator *d)
 185 {
 186         struct cdecl_declarator *new;
 187
 188         if (!function_is_reducible(d))
 189                 return 0;
 190
 191         new = reduce_function(d->u.function.parameters);
 192         if (!new)
 193                 return 0; /* e.g. int (foo bar) */
 194         *p = new;
 195         free(d->child);
 196         free(d);
 197
 198         return 1;
 199 }
 200
 201 /*
 202  * The parser's bias towards considering things as functions whenever possible
 203  * makes nested parentheses tricky.  (x) is considered to be part of a function
 204  * declarator until simplify_functions converts it.  The problem is that
 205  * (((x))) is not valid as part of a function declarator, but it *is* valid
 206  * as an identifier enclosed 3 times in parentheses.  This is complicated by
 207  * the fact that things like (((int))) are not valid anywhere.
 208  *
 209  * To avoid ambiguities, the parser actually emits a "function" declarator for
 210  * every pair of parentheses.  The ones that can't reasonably be functions
 211  * consist of a single "parameter" with no declaration specifiers (note that
 212  * every valid function parameter will have at least one type specifier).
 213  *
 214  * This pass is to remove these fake functions from the parse tree.  We take
 215  * care to avoid turning invalid things like ((int)) into valid things like
 216  * (int) by observing that the only valid function declarators that appear
 217  * in these "fake" parentheses are those that have a non-null child declarator
 218  * (for instance, int ((*)(int)) *or* those that will be eliminated by the
 219  * simplify_functions pass.
 220  */
 221
 222 static int
 223 reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d)
 224 {
 225         struct cdecl *param;
 226
 227         if (d->type != CDECL_DECL_FUNCTION)
 228                 return 0;
 229
 230         param = d->u.function.parameters;
 231         if (param && param->specifiers == NULL) {
 232                 struct cdecl_declarator *decl;
 233
 234                 assert(!param->next);
 235
 236                 decl = param->declarators;
 237                 if (decl->type == CDECL_DECL_NULL) {
 238                         free(decl);
 239                         free(param);
 240                         d->u.function.parameters = NULL;
 241                         return 0;
 242                 }
 243
 244                 if (d->child->type != CDECL_DECL_NULL) {
 245                         fprintf(stderr, "invalid function parameter\n");
 246                         return -1;
 247                 }
 248
 249                 free(d->child);
 250                 free(param);
 251                 free(d);
 252                 *p = decl;
 253
 254                 /*
 255                  * We may have replaced d with another fake function which
 256                  * also needs to be eliminated.
 257                  */
 258                 if (reduce_parentheses(p, decl) < 0)
 259                         return -1;
 260
 261                 /*
 262                  * If the remaining declarator is a function, make sure it's
 263                  * valid by checking its reducibility.
 264                  */
 265                 decl = *p;
 266                 if (decl->type == CDECL_DECL_FUNCTION
 267                     && decl->child->type == CDECL_DECL_NULL
 268                     && !function_is_reducible(decl)) {
 269                         fprintf(stderr, "too many parentheses in function\n");
 270                         return -1;
 271                 }
 272
 273                 return 1;
 274         }
 275
 276         return 0;
 277 }
 278
 279 /*
 280  * Function parameters and return types have a few restrictions that are
 281  * really easy to check in comparison to the above absurdity.
 282  */
 283 static int
 284 check_parameters(struct cdecl_declarator **p, struct cdecl_declarator *d)
 285 {
 286         struct cdecl_declspec *spec;
 287         struct cdecl *param;
 288         bool has_void = false;
 289
 290         if (d->type != CDECL_DECL_FUNCTION)
 291                 return 0;
 292
 293         for (param = d->u.function.parameters; param; param = param->next) {
 294                 if (!valid_declspecs(param, false))
 295                         return -1;
 296
 297                 for (spec = param->specifiers; spec; spec = spec->next) {
 298                         if (spec->type == CDECL_TYPE_VOID
 299                             && param->declarators->type == CDECL_DECL_NULL)
 300                                 has_void = true;
 301                 }
 302         }
 303
 304         if (has_void && d->u.function.parameters->next) {
 305                 fprintf(stderr, "a void parameter must stand alone\n");
 306                 return -1;
 307         } else if (has_void && d->u.function.variadic) {
 308                 fprintf(stderr, "variadic functions cannot have a void parameter\n");
 309                 return -1;
 310         }
 311
 312         return 0;
 313 }
 314
 315 /*
 316  * Functions cannot return arrays or functions.  Since the parse tree is
 317  * "inside-out", we need to look for functions as the child declarator.
 318  */
 319 static int
 320 check_rettypes(struct cdecl_declarator **p, struct cdecl_declarator *d)
 321 {
 322         if (!d->child || d->child->type != CDECL_DECL_FUNCTION)
 323                 return 0;
 324
 325         switch (d->type) {
 326         case CDECL_DECL_FUNCTION:
 327                 fprintf(stderr, "functions cannot return functions\n");
 328                 return -1;
 329         case CDECL_DECL_ARRAY:
 330                 fprintf(stderr, "functions cannot return arrays\n");
 331                 return -1;
 332         }
 333
 334         return 0;
 335 }
 336
 337 static int
 338 check_arrays(struct cdecl_declarator **p, struct cdecl_declarator *d)
 339 {
 340         if (!d->child || d->child->type != CDECL_DECL_ARRAY)
 341                 return 0;
 342
 343         switch (d->type) {
 344         case CDECL_DECL_FUNCTION:
 345                 fprintf(stderr, "array members cannot be functions\n");
 346                 return -1;
 347         }
 348
 349         return 0;
 350 }
 351
 352 /*
 353  * Traverse the parse tree, calling a function on every declarator in a
 354  * depth-first preorder traversal.  The function is given a pointer to the
 355  * declarator as well as to the pointer which was used to reach that
 356  * declarator: this can be used to rewrite entire subtrees.
 357  */
 358 static bool forall_declarators(struct cdecl *decl,
 359         int f(struct cdecl_declarator **, struct cdecl_declarator *))
 360 {
 361         struct cdecl_declarator *d, **p;
 362
 363         for (p = &decl->declarators, d = *p; d; p = &d->child, d = *p) {
 364                 switch (f(p, d)) {
 365                 case 0:
 366                         break;
 367                 case 1:
 368                         d = *p;
 369                         break;
 370                 case -1:
 371                         return false;
 372                 default:
 373                         assert(0);
 374                 }
 375
 376                 if (d->type == CDECL_DECL_FUNCTION) {
 377                         struct cdecl *i;
 378
 379                         for (i = d->u.function.parameters; i; i = i->next) {
 380                                 if (!forall_declarators(i, f))
 381                                         return false;
 382                         }
 383                 }
 384         }
 385
 386         return true;
 387 }
 388
 389 struct cdecl *cdecl_parse_decl(const char *declstr)
 390 {
 391         YY_BUFFER_STATE state;
 392         yyscan_t scanner;
 393         struct cdecl *decl;
 394         int rc;
 395
 396         cdecl__init_i18n();
 397
 398         rc = cdecl__yylex_init(&scanner);
 399         if (rc != 0)
 400                 return NULL;
 401
 402         state = cdecl__yy_scan_string(declstr, scanner);
 403         rc = cdecl__yyparse(scanner, &decl);
 404         cdecl__yy_delete_buffer(state, scanner);
 405         cdecl__yylex_destroy(scanner);
 406
 407         if (rc != 0)
 408                 return NULL;
 409
 410         for (struct cdecl *i = decl; i; i = i->next) {
 411                 if (!forall_declarators(i, reduce_parentheses))
 412                         goto err;
 413                 if (!forall_declarators(i, simplify_functions))
 414                         goto err;
 415                 if (!forall_declarators(i, check_parameters))
 416                         goto err;
 417                 if (!forall_declarators(i, check_rettypes))
 418                         goto err;
 419                 if (!forall_declarators(i, check_arrays))
 420                         goto err;
 421
 422                 if (!valid_declspecs(i, true))
 423                         goto err;
 424
 425                 if (is_abstract(i->declarators) && (i != decl || i->next)) {
 426                         fprintf(stderr, "mixing type names and declarations is not allowed\n");
 427                         goto err;
 428                 }
 429         }
 430
 431         return decl;
 432 err:
 433         cdecl__free(decl);
 434         return NULL;
 435 }
 436
 437 struct cdecl *cdecl_parse_english(const char *english)
 438 {
 439         YY_BUFFER_STATE state;
 440         yyscan_t scanner;
 441         struct cdecl *decl;
 442         int rc;
 443
 444         cdecl__init_i18n();
 445
 446         rc = cdecl__yylex_init_extra(true, &scanner);
 447         if (rc != 0)
 448                 return NULL;
 449
 450         state = cdecl__yy_scan_string(english, scanner);
 451         rc = cdecl__yyparse(scanner, &decl);
 452         cdecl__yy_delete_buffer(state, scanner);
 453         cdecl__yylex_destroy(scanner);
 454
 455         if (rc != 0)
 456                 return NULL;
 457
 458         for (struct cdecl *i = decl; i; i = i->next) {
 459                 if (!forall_declarators(i, check_parameters))
 460                         goto err;
 461                 if (!forall_declarators(i, check_rettypes))
 462                         goto err;
 463                 if (!forall_declarators(i, check_arrays))
 464                         goto err;
 465
 466                 if (!valid_declspecs(i, true))
 467                         goto err;
 468         }
 469
 470         return decl;
 471 err:
 472         cdecl__free(decl);
 473         return NULL;
 474 }
 475
 476 void cdecl_free(struct cdecl *decl)
 477 {
 478         cdecl__free(decl);
 479 }