src/parse.y

   1 %code top {
   2 /*
   3  *  Parser for C declarations.
   4  *  Copyright © 2011-2012, 2021, 2023-2024 Nick Bowler
   5  *
   6  *  This program is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19 }
  20
  21 %name-prefix "cdecl__yy"
  22 %parse-param {void *scanner}
  23 %parse-param {struct cdecl **out}
  24 %lex-param {yyscan_t scanner}
  25 %define api.pure
  26 %error-verbose
  27 %locations
  28
  29 %{
  30 #include <config.h>
  31 #include <assert.h>
  32 #include <stdbool.h>
  33
  34 #include "scan.h"
  35 #include "cdecl.h"
  36 #include "cdecl-internal.h"
  37 #include "errmsg.h"
  38
  39 /*
  40  * Allocate a parse tree node via cdecl__alloc_item.
  41  *
  42  * - m1 specifies the item's union member to assign to ptr, which selects the
  43  *   type of node to allocate.
  44  *
  45  * - m2 specifies the "next" or "child" member, which is initialized to a null
  46  *   pointer.  The cdecl__alloc_item function sets the declarator.child member
  47  *   to null; we explicitly copy this null pointer to the returned union member
  48  *   to avoid type punning.  It is hoped that compilers will notice that these
  49  *   pointers are at the same offset therefore the assignment can be elided.
  50  *
  51  * The resulting pointer can be passed directly to free, as the union is the
  52  * first member of the parse_item structure.
  53  *
  54  * Use the wrapper macros below instead of this one.
  55  */
  56 #define ALLOC_ITEM(ptr, m1, m2) do { \
  57         struct parse_item *item; \
  58         if (!(item = cdecl__alloc_item(0))) \
  59                 YYERROR; \
  60         item->u.m1.m2 = (void *)item->u.declarator.child; \
  61         (ptr) = &item->u.m1; \
  62 } while (0)
  63
  64 /* Wrappers for ALLOC_ITEM to allocate various kinds of parser structures. */
  65 #define ALLOC_ITEM_DECLARATOR(ptr) ALLOC_ITEM(ptr, declarator, child)
  66 #define ALLOC_ITEM_DECLSPEC(ptr)   ALLOC_ITEM(ptr, declspec, next)
  67 #define ALLOC_ITEM_DECL(ptr)       ALLOC_ITEM(ptr, decl, next)
  68
  69 #define ALLOC_FUNCTION_(ptr, parameters_) do { \
  70         ALLOC_ITEM_DECLARATOR(ptr); \
  71         (ptr)->type = CDECL_DECL_FUNCTION; \
  72         (ptr)->u.function.parameters = parameters_; \
  73 } while (0)
  74
  75 #define ALLOC_FUNCTION(ptr, parameters_, variadic_) do { \
  76         ALLOC_FUNCTION_(ptr, parameters_); \
  77         (ptr)->u.function.variadic = variadic_; \
  78 } while (0)
  79
  80 #define ALLOC_ARRAY(ptr, length_) do { \
  81         ALLOC_ITEM_DECLARATOR(ptr); \
  82         (ptr)->type = CDECL_DECL_ARRAY; \
  83         (ptr)->u.array.vla = NULL; \
  84         (ptr)->u.array.length = length_; \
  85 } while (0)
  86
  87 #define ALLOC_POINTER(ptr, qualifiers_, child_) do { \
  88         ALLOC_ITEM_DECLARATOR(ptr); \
  89         (ptr)->child = child_; \
  90         (ptr)->type = CDECL_DECL_POINTER; \
  91         (ptr)->u.pointer.qualifiers = qualifiers_; \
  92 } while (0)
  93
  94 #define ALLOC_DECLSPEC(ptr, type_) do { \
  95         ALLOC_ITEM_DECLSPEC(ptr); \
  96         (ptr)->type = type_; \
  97         (ptr)->ident = NULL; \
  98 } while (0)
  99
 100 #define ALLOC_DECL(ptr, specifiers_, declarators_) do { \
 101         ALLOC_ITEM_DECL(ptr); \
 102         (ptr)->specifiers = specifiers_; \
 103         (ptr)->declarators = declarators_; \
 104 } while (0)
 105
 106 /*
 107  * With the postprocessing performed by fix-yytname.awk, all the symbol
 108  * name strings can be used directly in error messages and there is no
 109  * need for any string processing.
 110  */
 111 #define yytnamerr(a, b) ( (a) ? yytnamerr_copy(a, b) \
 112                               : strlen(b) )
 113
 114 static size_t yytnamerr_copy(char *dst, const char *src)
 115 {
 116         return cdecl__strlcpy(dst, src, strlen(src)+1);
 117 }
 118 %}
 119
 120 %code requires {
 121 #include <inttypes.h>
 122 #include <stdbool.h>
 123 }
 124
 125 %code provides {
 126 void cdecl__free(struct cdecl *);
 127 int cdecl__yyparse(void *scanner, struct cdecl **out);
 128 const char *cdecl__token_name(unsigned token);
 129 }
 130
 131 %union {
 132         uintmax_t uintval;
 133         unsigned spectype;
 134         bool boolval;
 135         struct cdecl_declspec *declspec;
 136         struct cdecl_declarator *declarator;
 137         struct cdecl *decl;
 138         struct parse_item *item;
 139 }
 140
 141 %{
 142 static void yyerror(YYLTYPE *, yyscan_t, struct cdecl **, const char *);
 143 static void free_decl(struct cdecl *);
 144
 145 static void free_declspec(struct cdecl_declspec *x)
 146 {
 147         struct cdecl_declspec *p;
 148         while (x) {
 149                 p = x->next;
 150                 free(x);
 151                 x = p;
 152         }
 153 }
 154
 155 static void free_declarator(struct cdecl_declarator *x)
 156 {
 157         struct cdecl_declarator *p;
 158
 159         while (x) {
 160                 p = x->child;
 161
 162                 switch (x->type) {
 163                 case CDECL_DECL_NULL:
 164                         x = NULL;
 165                 case CDECL_DECL_IDENT:
 166                 case CDECL_DECL_ARRAY:
 167                         break;
 168                 case CDECL_DECL_POINTER:
 169                         free_declspec(x->u.pointer.qualifiers);
 170                         break;
 171                 case CDECL_DECL_FUNCTION:
 172                         free_decl(x->u.function.parameters);
 173                         break;
 174                 default:
 175                         assert(0);
 176                 }
 177
 178                 free(x);
 179                 x = p;
 180         }
 181 }
 182
 183 static void free_decl(struct cdecl *x)
 184 {
 185         struct cdecl *p;
 186
 187         while (x) {
 188                 p = x->next;
 189
 190                 /* The specifiers may be shared by an entire chain. */
 191                 if (!p || p->specifiers != x->specifiers)
 192                         free_declspec(x->specifiers);
 193
 194                 free_declarator(x->declarators);
 195                 free(x);
 196                 x = p;
 197         }
 198 }
 199
 200 void cdecl__free(struct cdecl *decl)
 201 {
 202         free_decl(decl);
 203 }
 204
 205 /*
 206  * Join two declaration specifier lists into a single list, with "a" being the
 207  * head of the new list.
 208  *
 209  * The list "a" is assumed to be nonempty.
 210  */
 211 static void join_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
 212 {
 213         while (a->next)
 214                 a = a->next;
 215         a->next = b;
 216 }
 217
 218 /*
 219  * Join three specifier lists into a single list, and returns the head of
 220  * the new list.
 221  *
 222  * The list "b" is assumed to be a singleton list.
 223  */
 224 static struct cdecl_declspec *join_specs3(struct cdecl_declspec *a,
 225                                           struct cdecl_declspec *b,
 226                                           struct cdecl_declspec *c)
 227 {
 228         b->next = c;
 229         join_specs(b, a);
 230         return b;
 231 }
 232
 233 /*
 234  * Reverse the order of a "struct cdecl" list, and return the new first
 235  * element of the list (i.e., the last element of the original list).
 236  */
 237 static struct cdecl *reverse_decls(struct cdecl *decl)
 238 {
 239         struct cdecl *prev, *next;
 240
 241         for (prev = NULL; decl; decl = next) {
 242                 next = decl->next;
 243                 decl->next = prev;
 244                 prev = decl;
 245         }
 246
 247         return prev;
 248 }
 249
 250 /*
 251  * Alter an abstract declarator (type name) to declare an identifier instead,
 252  * used by the English parser rules to reduce "identifier as type" sequences.
 253  */
 254 static struct cdecl *
 255 insert_identifier(struct cdecl *decl, struct parse_item *ident)
 256 {
 257         struct cdecl_declarator *d, **p = &decl->declarators;
 258
 259         while ((d = *p)->child)
 260                 p = &d->child;
 261
 262         *p = &ident->u.declarator;
 263         return decl;
 264 }
 265
 266 static struct cdecl_declarator *nulldecl(void)
 267 {
 268         static const struct cdecl_declarator nulldecl = {0};
 269         return (void *)&nulldecl;
 270 }
 271 #define NULLDECL (nulldecl())
 272
 273 %}
 274
 275 %destructor { free($$); }            <item>
 276 %destructor { free_declspec($$); }   <declspec>
 277 %destructor { free_declarator($$); } <declarator>
 278 %destructor { free_decl($$); }       <decl>
 279
 280 /* Magic tokens */
 281 %token T_LEX_ERROR
 282
 283 %token <item>    T_IDENT "identifier"
 284 %token <uintval> T_UINT  "integer constant"
 285
 286 %token T_SEMICOLON ";"
 287 %token T_ASTERISK  "*"
 288 %token T_LPAREN    "("
 289 %token T_RPAREN    ")"
 290 %token T_LBRACKET  "["
 291 %token T_RBRACKET  "]"
 292 %token T_COMMA     ","
 293 %token T_ELLIPSIS  "..."
 294
 295 %token <spectype> T_TYPEDEF   "typedef"
 296 %token <spectype> T_EXTERN    "extern"
 297 %token <spectype> T_STATIC    "static"
 298 %token <spectype> T_AUTO      "auto"
 299 %token <spectype> T_REGISTER  "register"
 300
 301 %token <spectype> T_INLINE    "inline"
 302
 303 %token <spectype> T_RESTRICT  "restrict"
 304 %token <spectype> T_VOLATILE  "volatile"
 305 %token <spectype> T_CONST     "const"
 306
 307 %token <spectype> T_VOID      "void"
 308 %token <spectype> T_CHAR      "char"
 309 %token <spectype> T_SHORT     "short"
 310 %token <spectype> T_INT       "int"
 311 %token <spectype> T_LONG      "long"
 312 %token <spectype> T_FLOAT     "float"
 313 %token <spectype> T_DOUBLE    "double"
 314 %token <spectype> T_SIGNED    "signed"
 315 %token <spectype> T_UNSIGNED  "unsigned"
 316 %token <spectype> T_BOOL      "_Bool"
 317 %token <spectype> T_COMPLEX   "_Complex"
 318 %token <spectype> T_IMAGINARY "_Imaginary"
 319
 320 %token <spectype> T_STRUCT    "struct"
 321 %token <spectype> T_UNION     "union"
 322 %token <spectype> T_ENUM      "enum"
 323
 324 /*
 325  * English keywords.
 326  */
 327 %token T_TYPE      "type"
 328 %token T_DECLARE   "declare"
 329 %token T_POINTER   "pointer"
 330 %token T_FUNCTION  "function"
 331 %token T_RETURNING "returning"
 332 %token T_ARRAY     "array"
 333 %token T_TO        "to"
 334 %token T_OF        "of"
 335 %token T_AS        "as"
 336 %token T_VLA       "variable-length"
 337
 338 %type <item>       vla_ident
 339 %type <uintval>    array_length
 340 %type <boolval>    varargs
 341 %type <spectype>   declspec_simple qualifier_simple
 342 %type <spectype>   typespec_simple typespec_tagged
 343 %type <declspec>   declspec_notype declspec_noid typespec_noid typespec
 344 %type <declspec>   qualifier qualifiers
 345 %type <declspec>   declspecs declspecs_notype declspecs_noid
 346 %type <declarator> direct_declarator declarator pointer array parens postfix
 347 %type <declarator> direct_declarator_ish declarator_ish parameter_type_list
 348 %type <decl>       cdecl declaration declarators declarator_wrap parameter
 349
 350 %type <item>       english_vla
 351 %type <declspec>   storage_func_specs post_specs
 352 %type <declspec>   type_qual_spec type_qual_specs typedef_name_qual
 353 %type <declarator> english_declarator english_array english_function
 354 %type <declarator> english_parameter_list null_decl
 355 %type <decl>       english english_declaration english_parameter
 356
 357 /* Precedence declaration to avoid conflict in english_parameter; see below. */
 358 %right T_TYPE
 359 %right T_IDENT
 360
 361 %%
 362
 363 input: cdecl { *out = $1; }
 364 cdecl: english | declaration
 365
 366 semi: | T_SEMICOLON
 367 declaration: declspecs declarators semi {
 368         $$ = reverse_decls($2);
 369         $$->specifiers = $1;
 370 };
 371
 372 /*
 373  * We support parsing declarations using arbitrary identifiers as type
 374  * specifiers (a la C typedef).  To avoid confusion with identifiers that
 375  * may also be used as declarators, note the following:
 376  *
 377  *  (a) Every valid C declaration must have at least one type specifier, and
 378  *  (b) Valid declarations with typedef names have exactly one type specifier.
 379  *
 380  * So the rule applied when parsing specifiers is: an identifier is a type
 381  * specifier only if we have not yet seen any type specifiers whatsoever
 382  * (within one declaration specifier list).
 383  *
 384  * Treating identifiers as type specifiers by default can lead to strange and
 385  * unexpected parses; libcdecl applies a simplification step to the resulting
 386  * parse tree afterwards.
 387  */
 388 declspecs: declspecs_notype typespec declspecs_noid {
 389         $$ = join_specs3($1, $2, $3);
 390 }
 391
 392 declspecs_notype: { $$ = NULL; } | declspecs_notype declspec_notype {
 393         $$ = $2;
 394         $$->next = $1;
 395 }
 396
 397 declspecs_noid: { $$ = NULL; } | declspecs_noid declspec_noid {
 398         $$ = $2;
 399         $$->next = $1;
 400 }
 401
 402 qualifiers: { $$ = NULL; } | qualifiers qualifier {
 403         $$ = $2;
 404         $$->next = $1;
 405 }
 406
 407 declarators: declarator_wrap | declarators T_COMMA declarator_wrap {
 408         $$ = $3;
 409         $$->next = $1;
 410 }
 411
 412 declarator_wrap: declarator {
 413         ALLOC_DECL($$, NULL, $1);
 414 }
 415
 416 declspec_simple: T_AUTO
 417         | T_TYPEDEF
 418         | T_EXTERN
 419         | T_STATIC
 420         | T_REGISTER
 421         | T_INLINE
 422
 423 typespec_simple: T_VOID
 424         | T_CHAR
 425         | T_SHORT
 426         | T_INT
 427         | T_LONG
 428         | T_FLOAT
 429         | T_DOUBLE
 430         | T_SIGNED
 431         | T_UNSIGNED
 432         | T_BOOL
 433         | T_COMPLEX
 434         | T_IMAGINARY
 435
 436 typespec_tagged: T_STRUCT | T_UNION | T_ENUM | { $$ = CDECL_TYPE_IDENT; }
 437
 438 qualifier_simple: T_CONST
 439         | T_RESTRICT
 440         | T_VOLATILE
 441
 442 declspec_notype: qualifier | declspec_simple { ALLOC_DECLSPEC($$, $1); }
 443 typespec_noid: typespec_simple { ALLOC_DECLSPEC($$, $1); }
 444 qualifier: qualifier_simple { ALLOC_DECLSPEC($$, $1); }
 445
 446 typespec: typespec_noid | typespec_tagged T_IDENT {
 447         /* Compiler should be able to elide this assignment. */
 448         $2->u.declspec.ident = $2->u.declarator.u.ident;
 449
 450         $$ = &$2->u.declspec;
 451         $$->type = $1;
 452 }
 453
 454 declspec_noid: declspec_notype | typespec_noid
 455
 456 vla_ident: T_IDENT | T_ASTERISK {
 457         if (!($$ = cdecl__alloc_item(1)))
 458                 YYERROR;
 459         *$$->s = 0;
 460 }
 461
 462 array: T_LBRACKET array_length T_RBRACKET {
 463         ALLOC_ARRAY($$, $2);
 464 } | T_LBRACKET vla_ident T_RBRACKET {
 465         $$ = &$2->u.declarator;
 466         $$->type = CDECL_DECL_ARRAY;
 467         $$->u.array.vla = $$->u.ident;
 468         $$->u.array.length = 0;
 469 }
 470
 471 parameter: declspecs declarator {
 472         ALLOC_DECL($$, $1, $2);
 473 }
 474
 475 varargs: { $$ = false; } | T_COMMA T_ELLIPSIS { $$ = true; }
 476
 477 parameter_type_list: parameter {
 478         ALLOC_FUNCTION_($$, $1);
 479 } | parameter_type_list T_COMMA parameter {
 480         $$ = $1;
 481         $3->next = $$->u.function.parameters;
 482         $$->u.function.parameters = $3;
 483 }
 484
 485 parens: T_LPAREN parameter_type_list varargs T_RPAREN {
 486         $2->u.function.parameters = reverse_decls($2->u.function.parameters);
 487         $2->u.function.variadic = $3;
 488         $$ = $2;
 489 } | T_LPAREN declarator_ish T_RPAREN {
 490         struct cdecl *fake_params;
 491
 492         ALLOC_DECL(fake_params, NULL, $2);
 493         ALLOC_FUNCTION_($$, fake_params);
 494 }
 495
 496 pointer: T_ASTERISK qualifiers direct_declarator {
 497         ALLOC_POINTER($$, $2, $3);
 498 } | T_ASTERISK qualifiers pointer {
 499         ALLOC_POINTER($$, $2, $3);
 500 }
 501
 502 declarator: direct_declarator | pointer
 503 declarator_ish: direct_declarator_ish | pointer
 504 postfix: array | parens
 505
 506 direct_declarator_ish: {
 507         $$ = NULLDECL;
 508 } | direct_declarator_ish postfix {
 509         $$ = $2;
 510         $$->child = $1;
 511 }
 512
 513 direct_declarator: {
 514         $$ = NULLDECL;
 515 } | T_IDENT {
 516         $$ = &$1->u.declarator;
 517 } | direct_declarator postfix {
 518         $$ = $2;
 519         $$->child = $1;
 520 }
 521
 522 english: T_DECLARE T_IDENT T_AS english_declaration {
 523         $$ = insert_identifier($4, $2);
 524 } | T_TYPE english_declaration {
 525         $$ = $2;
 526 }
 527
 528 /*
 529  * We use a precedence declaration to prefer shifting an identifier
 530  * over reducing this empty rule; see below.
 531  */
 532 storage_func_specs: %prec T_TYPE { $$ = NULL; }
 533 storage_func_specs: storage_func_specs declspec_simple {
 534         ALLOC_DECLSPEC($$, $2);
 535         $$->next = $1;
 536 }
 537
 538 type_qual_spec: typespec_noid | qualifier
 539
 540 type_qual_specs: { $$ = NULL; } | type_qual_specs type_qual_spec {
 541         $$ = $2;
 542         $$->next = $1;
 543 }
 544
 545 /*
 546  * The "qualifiers" nonterminal needs to be used here to avoid shift/reduce
 547  * conflicts with pointer declarators.  So we end up needing to stitch
 548  * together three different specifiers lists.
 549  */
 550 post_specs: qualifiers typespec type_qual_specs {
 551         $$ = join_specs3($1, $2, $3);
 552 }
 553
 554 english_declaration: storage_func_specs english_declarator post_specs {
 555         join_specs($3, $1);
 556         ALLOC_DECL($$, $3, $2);
 557 }
 558
 559 english_declarator: {
 560         $$ = NULLDECL;
 561 } | english_declarator qualifiers T_POINTER T_TO {
 562         ALLOC_POINTER($$, $2, $1);
 563 } | english_declarator english_array {
 564         $$ = $2;
 565         $$->child = $1;
 566 } | english_declarator english_function {
 567         $$ = $2;
 568         $$->child = $1;
 569 }
 570
 571 english_function: T_FUNCTION T_RETURNING {
 572         ALLOC_FUNCTION($$, NULL, false);
 573 } | T_FUNCTION T_LPAREN english_parameter_list varargs T_RPAREN T_RETURNING {
 574         $3->u.function.parameters = reverse_decls($3->u.function.parameters);
 575         $3->u.function.variadic = $4;
 576         $$ = $3;
 577 }
 578
 579 english_parameter_list: english_parameter {
 580         ALLOC_FUNCTION_($$, $1);
 581 } | english_parameter_list T_COMMA english_parameter {
 582         $$ = $1;
 583         $3->next = $$->u.function.parameters;
 584         $$->u.function.parameters = $3;
 585 }
 586
 587 typedef_name_qual: T_IDENT qualifiers {
 588         /* Compiler should be able to elide this assignment. */
 589         $1->u.declspec.ident = $1->u.declarator.u.ident;
 590
 591         $$ = &$1->u.declspec;
 592         $$->type = CDECL_TYPE_IDENT;
 593         $$->next = $2;
 594 }
 595
 596 null_decl: {
 597         $$ = NULLDECL;
 598 }
 599
 600 /*
 601  * There is a shift/reduce conflict here when an identifier appears as the
 602  * first token.  The conflict is between shifting T_IDENT, or reducing the
 603  * empty production for storage_func_specs (cf. english_declaration).
 604  *
 605  *   - In either case, if we reduce, we won't match T_IDENT T_AS since the
 606  *     stack now has the extra storage_func_specs nonterminal symbol.
 607  *   - And if we shift, we won't match english_declaration since it is
 608  *     too late to add storage_func_specs to the stack.
 609  *
 610  * The only valid input affected by the conflict is a simple type names,
 611  * possibly followed by qualifiers.  So the conflict is adequately resolved
 612  * by shifting, so long as we have a special-case reduction to handle this.
 613  */
 614 english_parameter: english_declaration | typedef_name_qual null_decl {
 615         ALLOC_DECL($$, $1, $2);
 616 } | T_IDENT T_AS english_declaration {
 617         $$ = insert_identifier($3, $1);
 618 }
 619
 620 english_array: T_VLA T_ARRAY english_vla T_OF {
 621         $$ = &$3->u.declarator;
 622         $$->type = CDECL_DECL_ARRAY;
 623         $$->u.array.vla = $$->u.ident;
 624         $$->u.array.length = 0;
 625 } | T_ARRAY array_length T_OF {
 626         ALLOC_ARRAY($$, $2);
 627 }
 628
 629 array_length: { $$ = 0; }
 630 array_length: T_UINT {
 631         if (!($$ = $1)) {
 632                 cdecl__errmsg(CDECL__EZEROARRAY);
 633                 YYERROR;
 634         }
 635 }
 636
 637 english_vla: T_IDENT | {
 638         if (!($$ = cdecl__alloc_item(1)))
 639                 YYERROR;
 640         *$$->s = 0;
 641 }
 642
 643 %%
 644
 645 /*
 646  * Expose the token string table to the rest of the library, in order to
 647  * produce strings that match parser keywords.
 648  *
 649  * In order for this to work properly, the Bison output must be postprocessed
 650  * by fix-yytname.awk to remove pointless quotation marks from the keyword
 651  * strings.
 652  */
 653 const char *cdecl__token_name(unsigned token)
 654 {
 655         return yytname[YYTRANSLATE(token)];
 656 }
 657
 658 /*
 659  * Current versions of GCC (up to 13) want to inline this function into the
 660  * parser even when optimizing for size and the results are not great, so
 661  * try to prevent such inlining.
 662  */
 663 CDECL__NOINLINE static void
 664 yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err)
 665 {
 666         if (strstr(err, yytname[YYTRANSLATE(T_LEX_ERROR)]))
 667                 return;
 668
 669         cdecl__err("%s", err);
 670 }