src/parse-decl.c

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