X-Git-Url: https://git.draconx.ca/gitweb/cdecl99.git/blobdiff_plain/7faacc8b3fbc810ec92faa0c38af5270e3bd1b4e..HEAD:/src/parse.y diff --git a/src/parse.y b/src/parse.y index b77cfbb..6f3b304 100644 --- a/src/parse.y +++ b/src/parse.y @@ -1,7 +1,7 @@ %code top { /* * Parser for C declarations. - * Copyright © 2011-2012, 2021, 2023 Nick Bowler + * Copyright © 2011-2012, 2021, 2023-2024 Nick Bowler * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -32,31 +32,88 @@ #include #include "scan.h" -#include "cdecl.h" #include "cdecl-internal.h" #include "errmsg.h" -#define FAIL(msg) do { \ - yyerror(&yylloc, NULL, NULL, msg); \ - YYERROR; \ +/* + * Allocate a parse tree node via cdecl__alloc_item. + * + * - m1 specifies the item's union member to assign to ptr, which selects the + * type of node to allocate. + * + * - m2 specifies the "next" or "child" member, which is initialized to a null + * pointer. The cdecl__alloc_item function sets the declarator.child member + * to null; we explicitly copy this null pointer to the returned union member + * to avoid type punning. It is hoped that compilers will notice that these + * pointers are at the same offset therefore the assignment can be elided. + * + * The resulting pointer can be passed directly to free, as the union is the + * first member of the parse_item structure. + * + * Use the wrapper macros below instead of this one. + */ +#define ALLOC_ITEM(ptr, m1, m2) do { \ + struct parse_item *item; \ + if (!(item = cdecl__alloc_item(0))) \ + YYERROR; \ + item->u.m1.m2 = (void *)item->u.declarator.child; \ + (ptr) = &item->u.m1; \ } while (0) -#define ALLOC(ptr, size) do { \ - (ptr) = malloc(size); \ - if (!(ptr)) { \ - cdecl__errmsg(CDECL__ENOMEM); \ - YYERROR; \ - } \ +/* Wrappers for ALLOC_ITEM to allocate various kinds of parser structures. */ +#define ALLOC_ITEM_DECLARATOR(ptr) ALLOC_ITEM(ptr, declarator, child) +#define ALLOC_ITEM_DECLSPEC(ptr) ALLOC_ITEM(ptr, declspec, next) +#define ALLOC_ITEM_DECL(ptr) ALLOC_ITEM(ptr, decl, next) + +#define ALLOC_FUNCTION_(ptr, parameters_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->type = CDECL_DECL_FUNCTION; \ + (ptr)->u.function.parameters = parameters_; \ +} while (0) + +#define ALLOC_FUNCTION(ptr, parameters_, variadic_) do { \ + ALLOC_FUNCTION_(ptr, parameters_); \ + (ptr)->u.function.variadic = variadic_; \ +} while (0) + +#define ALLOC_ARRAY(ptr, length_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->type = CDECL_DECL_ARRAY; \ + (ptr)->u.array.vla = NULL; \ + (ptr)->u.array.length = length_; \ +} while (0) + +#define ALLOC_POINTER(ptr, qualifiers_, child_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->child = child_; \ + (ptr)->type = CDECL_DECL_POINTER; \ + (ptr)->u.pointer.qualifiers = qualifiers_; \ +} while (0) + +#define ALLOC_DECLSPEC(ptr, type_) do { \ + ALLOC_ITEM_DECLSPEC(ptr); \ + (ptr)->type = type_; \ + (ptr)->ident = NULL; \ } while (0) -#define ALLOC_STRUCT(ptr, type, ...) do { \ - ALLOC(ptr, sizeof (type)); \ - *(ptr) = (type) { __VA_ARGS__ }; \ +#define ALLOC_DECL(ptr, specifiers_, declarators_) do { \ + ALLOC_ITEM_DECL(ptr); \ + (ptr)->specifiers = specifiers_; \ + (ptr)->declarators = declarators_; \ } while (0) + +/* + * With the postprocessing performed by fix-yytname.awk, all the symbol + * name strings can be used directly in error messages and there is no + * need for any string processing. + */ +#define yytnamerr(a, b) ( (a) ? cdecl__strlcpy(a, b, -1) : strlen(b) ) %} %code requires { #include +#include +#include "cdecl.h" } %code provides { @@ -66,16 +123,17 @@ const char *cdecl__token_name(unsigned token); } %union { - uintmax_t uintval; + cdecl_uintmax uintval; unsigned spectype; - _Bool boolval; - char *strval; + bool boolval; struct cdecl_declspec *declspec; struct cdecl_declarator *declarator; struct cdecl *decl; + struct parse_item *item; } %{ +static void yyerror(YYLTYPE *, yyscan_t, struct cdecl **, const char *); static void free_decl(struct cdecl *); static void free_declspec(struct cdecl_declspec *x) @@ -83,7 +141,6 @@ static void free_declspec(struct cdecl_declspec *x) struct cdecl_declspec *p; while (x) { p = x->next; - free(x->ident); free(x); x = p; } @@ -98,16 +155,13 @@ static void free_declarator(struct cdecl_declarator *x) switch (x->type) { case CDECL_DECL_NULL: - break; + x = NULL; case CDECL_DECL_IDENT: - free(x->u.ident); + case CDECL_DECL_ARRAY: break; case CDECL_DECL_POINTER: free_declspec(x->u.pointer.qualifiers); break; - case CDECL_DECL_ARRAY: - free(x->u.array.vla); - break; case CDECL_DECL_FUNCTION: free_decl(x->u.function.parameters); break; @@ -142,27 +196,86 @@ void cdecl__free(struct cdecl *decl) free_decl(decl); } -static void -yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err) +/* + * Join two declaration specifier lists into a single list, with "a" being the + * head of the new list. + * + * The list "a" is assumed to be nonempty. + */ +static void join_specs(struct cdecl_declspec *a, struct cdecl_declspec *b) { - if (strstr(err, "T_LEX_ERROR")) - return; + while (a->next) + a = a->next; + a->next = b; +} - cdecl__err(CDECL_ENOPARSE, "%s", err); +/* + * Join three specifier lists into a single list, and returns the head of + * the new list. + * + * The list "b" is assumed to be a singleton list. + */ +static struct cdecl_declspec *join_specs3(struct cdecl_declspec *a, + struct cdecl_declspec *b, + struct cdecl_declspec *c) +{ + b->next = c; + join_specs(b, a); + return b; } + +/* + * Reverse the order of a "struct cdecl" list, and return the new first + * element of the list (i.e., the last element of the original list). + */ +static struct cdecl *reverse_decls(struct cdecl *decl) +{ + struct cdecl *prev, *next; + + for (prev = NULL; decl; decl = next) { + next = decl->next; + decl->next = prev; + prev = decl; + } + + return prev; +} + +/* + * Alter an abstract declarator (type name) to declare an identifier instead, + * used by the English parser rules to reduce "identifier as type" sequences. + */ +static struct cdecl * +insert_identifier(struct cdecl *decl, struct parse_item *ident) +{ + struct cdecl_declarator *d, **p = &decl->declarators; + + while ((d = *p)->child) + p = &d->child; + + *p = &ident->u.declarator; + return decl; +} + +static struct cdecl_declarator *nulldecl(void) +{ + static const struct cdecl_declarator nulldecl = {0}; + return (void *)&nulldecl; +} +#define NULLDECL (nulldecl()) + %} -%destructor { free($$); } +%destructor { free($$); } %destructor { free_declspec($$); } %destructor { free_declarator($$); } %destructor { free_decl($$); } /* Magic tokens */ -%token T_LEX_ERROR -%token T_ENGLISH +%token T_LEX_ERROR "@@@" -%token T_IDENT "identifier" -%token T_UINT "integer constant" +%token T_IDENT "identifier" +%token T_UINT "integer constant" %token T_SEMICOLON ";" %token T_ASTERISK "*" @@ -216,44 +329,37 @@ yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err) %token T_AS "as" %token T_VLA "variable-length" -%type vla_ident +%type vla_ident +%type array_length %type varargs %type declspec_simple qualifier_simple %type typespec_simple typespec_tagged %type declspec_notype declspec_noid typespec_noid typespec %type qualifier qualifiers -%type declspecs declspecs_noid +%type declspecs declspecs_notype declspecs_noid %type direct_declarator declarator pointer array parens postfix %type direct_declarator_ish declarator_ish parameter_type_list -%type declaration declarators declarator_wrap -%type parameter parameters +%type cdecl declaration declarators declarator_wrap parameter -%type english_vla +%type english_vla %type storage_func_specs post_specs %type type_qual_spec type_qual_specs typedef_name_qual %type english_declarator english_array english_function %type english_parameter_list null_decl -%type english_parameter english_parameters -%type english english_declaration +%type english english_declaration english_parameter -/* - * Harmless shift/reduce conflicts in english_parameter. See comments below - * for more details. - */ -%expect 2 +/* Precedence declaration to avoid conflict in english_parameter; see below. */ +%right T_TYPE +%right T_IDENT %% -input: T_ENGLISH english { - *out = $2; -} | declaration { - *out = $1; -}; +input: cdecl { *out = $1; } +cdecl: english | declaration semi: | T_SEMICOLON - declaration: declspecs declarators semi { - $$ = $2; + $$ = reverse_decls($2); $$->specifiers = $1; }; @@ -273,17 +379,18 @@ declaration: declspecs declarators semi { * unexpected parses; libcdecl applies a simplification step to the resulting * parse tree afterwards. */ -declspecs: declspec_notype declspecs { - $$ = $1; - $$->next = $2; -} | typespec declspecs_noid { - $$ = $1; - $$->next = $2; +declspecs: declspecs_notype typespec declspecs_noid { + $$ = join_specs3($1, $2, $3); } -declspecs_noid: { $$ = NULL; } | declspec_noid declspecs_noid { - $$ = $1; - $$->next = $2; +declspecs_notype: { $$ = NULL; } | declspecs_notype declspec_notype { + $$ = $2; + $$->next = $1; +} + +declspecs_noid: { $$ = NULL; } | declspecs_noid declspec_noid { + $$ = $2; + $$->next = $1; } qualifiers: { $$ = NULL; } | qualifiers qualifier { @@ -291,13 +398,13 @@ qualifiers: { $$ = NULL; } | qualifiers qualifier { $$->next = $1; } -declarators: declarator_wrap | declarator_wrap T_COMMA declarators { - $$ = $1; - $$->next = $3; +declarators: declarator_wrap | declarators T_COMMA declarator_wrap { + $$ = $3; + $$->next = $1; } declarator_wrap: declarator { - ALLOC_STRUCT($$, struct cdecl, .declarators = $1); + ALLOC_DECL($$, NULL, $1); } declspec_simple: T_AUTO @@ -320,104 +427,70 @@ typespec_simple: T_VOID | T_COMPLEX | T_IMAGINARY -typespec_tagged: T_STRUCT | T_UNION | T_ENUM +typespec_tagged: T_STRUCT | T_UNION | T_ENUM | { $$ = CDECL_TYPE_IDENT; } qualifier_simple: T_CONST | T_RESTRICT | T_VOLATILE -declspec_notype: qualifier | declspec_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} - -typespec_noid: typespec_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} - -qualifier: qualifier_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} +declspec_notype: qualifier | declspec_simple { ALLOC_DECLSPEC($$, $1); } +typespec_noid: typespec_simple { ALLOC_DECLSPEC($$, $1); } +qualifier: qualifier_simple { ALLOC_DECLSPEC($$, $1); } typespec: typespec_noid | typespec_tagged T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = $1, - .ident = $2); -} | T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_IDENT, - .ident = $1); + /* Compiler should be able to elide this assignment. */ + $2->u.declspec.ident = $2->u.declarator.u.ident; + + $$ = &$2->u.declspec; + $$->type = $1; } declspec_noid: declspec_notype | typespec_noid vla_ident: T_IDENT | T_ASTERISK { - ALLOC($$, sizeof ""); - strcpy($$, ""); + if (!($$ = cdecl__alloc_item(1))) + YYERROR; + *$$->s = 0; } -array: T_LBRACKET T_UINT T_RBRACKET { - if ($2 == 0) - FAIL(_("array length must be positive")); - - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.length = $2); +array: T_LBRACKET array_length T_RBRACKET { + ALLOC_ARRAY($$, $2); } | T_LBRACKET vla_ident T_RBRACKET { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.vla = $2); -} | T_LBRACKET T_RBRACKET { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY); + $$ = &$2->u.declarator; + $$->type = CDECL_DECL_ARRAY; + $$->u.array.vla = $$->u.ident; + $$->u.array.length = 0; } parameter: declspecs declarator { - ALLOC_STRUCT($$, struct cdecl, - .specifiers = $1, - .declarators = $2); -} - -parameters: parameter | parameters T_COMMA parameter { - $$ = $3; - $$->next = $1; + ALLOC_DECL($$, $1, $2); } varargs: { $$ = false; } | T_COMMA T_ELLIPSIS { $$ = true; } -parameter_type_list: parameters varargs { - struct cdecl *p, *c, *n; - - /* Parameters were accumulated in reverse order. */ - for (p = NULL, c = $1; c; p = c, c = n) { - n = c->next; - c->next = p; - } - - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_FUNCTION, - .u.function.parameters = p, - .u.function.variadic = $2); +parameter_type_list: parameter { + ALLOC_FUNCTION_($$, $1); +} | parameter_type_list T_COMMA parameter { + $$ = $1; + $3->next = $$->u.function.parameters; + $$->u.function.parameters = $3; } -parens: T_LPAREN parameter_type_list T_RPAREN { +parens: T_LPAREN parameter_type_list varargs T_RPAREN { + $2->u.function.parameters = reverse_decls($2->u.function.parameters); + $2->u.function.variadic = $3; $$ = $2; } | T_LPAREN declarator_ish T_RPAREN { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_FUNCTION); - ALLOC_STRUCT($$->u.function.parameters, struct cdecl, - .declarators = $2); + struct cdecl *fake_params; + + ALLOC_DECL(fake_params, NULL, $2); + ALLOC_FUNCTION_($$, fake_params); } pointer: T_ASTERISK qualifiers direct_declarator { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_POINTER, - .u.pointer.qualifiers = $2, - .child = $3); + ALLOC_POINTER($$, $2, $3); } | T_ASTERISK qualifiers pointer { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_POINTER, - .u.pointer.qualifiers = $2, - .child = $3); + ALLOC_POINTER($$, $2, $3); } declarator: direct_declarator | pointer @@ -425,48 +498,42 @@ declarator_ish: direct_declarator_ish | pointer postfix: array | parens direct_declarator_ish: { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_NULL); + $$ = NULLDECL; } | direct_declarator_ish postfix { $$ = $2; $$->child = $1; } direct_declarator: { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_NULL); + $$ = NULLDECL; } | T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_IDENT, - .u.ident = $1); + $$ = &$1->u.declarator; } | direct_declarator postfix { $$ = $2; $$->child = $1; } english: T_DECLARE T_IDENT T_AS english_declaration { - $$ = $4; - for (struct cdecl_declarator *d = $$->declarators; d; d = d->child) { - if (d->type == CDECL_DECL_NULL) { - d->type = CDECL_DECL_IDENT; - d->u.ident = $2; - } - } + $$ = insert_identifier($4, $2); } | T_TYPE english_declaration { $$ = $2; } -storage_func_specs: { $$ = NULL; } | declspec_simple storage_func_specs { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = $1, - .next = $2); +/* + * We use a precedence declaration to prefer shifting an identifier + * over reducing this empty rule; see below. + */ +storage_func_specs: %prec T_TYPE { $$ = NULL; } +storage_func_specs: storage_func_specs declspec_simple { + ALLOC_DECLSPEC($$, $2); + $$->next = $1; } type_qual_spec: typespec_noid | qualifier -type_qual_specs: { $$ = NULL; } | type_qual_spec type_qual_specs { - $$ = $1; - $$->next = $2; +type_qual_specs: { $$ = NULL; } | type_qual_specs type_qual_spec { + $$ = $2; + $$->next = $1; } /* @@ -475,37 +542,18 @@ type_qual_specs: { $$ = NULL; } | type_qual_spec type_qual_specs { * together three different specifiers lists. */ post_specs: qualifiers typespec type_qual_specs { - $$ = $2; - $$->next = $1; - for (struct cdecl_declspec *s = $$; s; s = s->next) { - if (!s->next) { - s->next = $3; - break; - } - } + $$ = join_specs3($1, $2, $3); } english_declaration: storage_func_specs english_declarator post_specs { - ALLOC_STRUCT($$, struct cdecl, - .specifiers = $3, - .declarators = $2); - - for (struct cdecl_declspec *s = $$->specifiers; s; s = s->next) { - if (!s->next) { - s->next = $1; - break; - } - } + join_specs($3, $1); + ALLOC_DECL($$, $3, $2); } english_declarator: { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_NULL); + $$ = NULLDECL; } | english_declarator qualifiers T_POINTER T_TO { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_POINTER, - .child = $1, - .u.pointer.qualifiers = $2); + ALLOC_POINTER($$, $2, $1); } | english_declarator english_array { $$ = $2; $$->child = $1; @@ -515,89 +563,75 @@ english_declarator: { } english_function: T_FUNCTION T_RETURNING { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_FUNCTION, - .u.function.parameters = NULL); -} | T_FUNCTION T_LPAREN english_parameter_list T_RPAREN T_RETURNING { + ALLOC_FUNCTION($$, NULL, false); +} | T_FUNCTION T_LPAREN english_parameter_list varargs T_RPAREN T_RETURNING { + $3->u.function.parameters = reverse_decls($3->u.function.parameters); + $3->u.function.variadic = $4; $$ = $3; } -english_parameter_list: english_parameters varargs { - struct cdecl *p, *c, *n; - - /* Parameters were accumulated in reverse order. */ - for (p = NULL, c = $1; c; p = c, c = n) { - n = c->next; - c->next = p; - } - - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_FUNCTION, - .u.function.parameters = p, - .u.function.variadic = $2); +english_parameter_list: english_parameter { + ALLOC_FUNCTION_($$, $1); +} | english_parameter_list T_COMMA english_parameter { + $$ = $1; + $3->next = $$->u.function.parameters; + $$->u.function.parameters = $3; } -english_parameters: english_parameters T_COMMA english_parameter { - $$ = $3; - $$->next = $1; -} | english_parameter - typedef_name_qual: T_IDENT qualifiers { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_IDENT, - .ident = $1, - .next = $2); + /* Compiler should be able to elide this assignment. */ + $1->u.declspec.ident = $1->u.declarator.u.ident; + + $$ = &$1->u.declspec; + $$->type = CDECL_TYPE_IDENT; + $$->next = $2; } null_decl: { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_NULL); + $$ = NULLDECL; } /* - * There is a small shift/reduce conflict here. An unadorned identifier - * as the first thing in the parameter might be a typedef name deep in the - * first english_declaration (thus empty storage_func_specs and empty - * english_declarator need to be reduced) or it might be the identifier - * before the "as" (thus the identifier should be shifted). + * There is a shift/reduce conflict here when an identifier appears as the + * first token. The conflict is between shifting T_IDENT, or reducing the + * empty production for storage_func_specs (cf. english_declaration). + * + * - In either case, if we reduce, we won't match T_IDENT T_AS since the + * stack now has the extra storage_func_specs nonterminal symbol. + * - And if we shift, we won't match english_declaration since it is + * too late to add storage_func_specs to the stack. * - * The typedef name conflict is the only issue, so treating it as a special - * case makes the shift harmless. + * The only valid input affected by the conflict is a simple type names, + * possibly followed by qualifiers. So the conflict is adequately resolved + * by shifting, so long as we have a special-case reduction to handle this. */ english_parameter: english_declaration | typedef_name_qual null_decl { - ALLOC_STRUCT($$, struct cdecl, - .specifiers = $1, - .declarators = $2); + ALLOC_DECL($$, $1, $2); } | T_IDENT T_AS english_declaration { - $$ = $3; - for (struct cdecl_declarator *d = $$->declarators; d; d = d->child) { - if (d->type == CDECL_DECL_NULL) { - d->type = CDECL_DECL_IDENT; - d->u.ident = $1; - } - } + $$ = insert_identifier($3, $1); } english_array: T_VLA T_ARRAY english_vla T_OF { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.vla = $3); -} | T_ARRAY T_UINT T_OF { - if ($2 == 0) - FAIL(_("array length must be positive")); - - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.length = $2); -} | T_ARRAY T_OF { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.length = 0); + $$ = &$3->u.declarator; + $$->type = CDECL_DECL_ARRAY; + $$->u.array.vla = $$->u.ident; + $$->u.array.length = 0; +} | T_ARRAY array_length T_OF { + ALLOC_ARRAY($$, $2); +} + +array_length: { $$ = 0; } +array_length: T_UINT { + if (!($$ = $1)) { + cdecl__errmsg(CDECL__EZEROARRAY); + YYERROR; + } } english_vla: T_IDENT | { - ALLOC($$, sizeof ""); - strcpy($$, ""); + if (!($$ = cdecl__alloc_item(1))) + YYERROR; + *$$->s = 0; } %% @@ -614,3 +648,17 @@ const char *cdecl__token_name(unsigned token) { return yytname[YYTRANSLATE(token)]; } + +/* + * Current versions of GCC (up to 13) want to inline this function into the + * parser even when optimizing for size and the results are not great, so + * try to prevent such inlining. + */ +CDECL__NOINLINE static void +yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err) +{ + if (strstr(err, yytname[YYTRANSLATE(T_LEX_ERROR)])) + return; + + cdecl__err("%s", err); +}