X-Git-Url: https://git.draconx.ca/gitweb/cdecl99.git/blobdiff_plain/e378d431539e029bdf2fc87f56ccb59d48608b97..HEAD:/src/parse-decl.c diff --git a/src/parse-decl.c b/src/parse-decl.c index b5212ec..3c60dd2 100644 --- a/src/parse-decl.c +++ b/src/parse-decl.c @@ -1,56 +1,156 @@ /* - * Parse and validate C declarations. - * Copyright © 2011 Nick Bowler + * Parse and validate C declarations. + * Copyright © 2011-2012, 2020-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 - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. + * 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 + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . */ + +#include #include #include #include #include "cdecl.h" -#include "typemap.h" +#include "cdecl-internal.h" #include "parse.h" #include "scan.h" +#include "errmsg.h" + +static struct cdecl *fake_function_param(struct cdecl_declarator *); + +/* + * Allocate a "parse item", which is a union of several parse tree + * structure types, together with a string buffer. The s_sz argument + * specifies the size of the string (including its terminator), which + * may be zero. + * + * The union's declarator member is pre-initialized to a valid "identifier" + * declarator, which shares several interesting offsets with the "declspec" + * structure for an "identifier" type specifier. + */ +struct parse_item *cdecl__alloc_item(size_t s_sz) +{ + struct parse_item *ret; + + ret = malloc(offsetof(struct parse_item, s) + s_sz); + if (!ret) { + cdecl__errmsg(CDECL__ENOMEM); + return NULL; + } + + ret->u.declarator.child = NULL; + ret->u.declarator.type = CDECL_DECL_IDENT; + ret->u.declarator.u.ident = ret->s; + + return ret; +} + +/* + * We can represent type specifiers as a bitmap, which gives us a finite + * list of acceptable bitmap values according to the C standard. However, + * the "long" specifier is allowed to occur more than once, but only at most + * 2 times. Treat it as a special case, assigning an unused bit to represent + * the second long. + */ +#define MAP_LLONG_BIT 31 +#define MAP_LONG_BIT (CDECL_TYPE_LONG-CDECL_SPEC_TYPE) +#define CDECL_TYPE_LLONG (CDECL_SPEC_TYPE+MAP_LLONG_BIT) + +#include "typemap.h" + +/* + * Convert the declaration specifiers to a bitmap with each bit + * corresponding to one specific type specifier. + */ +static int valid_typespec(struct cdecl_declspec *s) +{ + struct cdecl_declspec *c; + unsigned long map = 0; + + for (c = s; c; c = c->next) { + unsigned long bit; + + if (cdecl_spec_kind(c) != CDECL_SPEC_TYPE) + continue; + + bit = c->type - CDECL_SPEC_TYPE; + assert(bit < MAP_LLONG_BIT); + bit = 1ul << bit; + + /* "long" special case */ + if ((map & bit) == 1ul << MAP_LONG_BIT) + bit = 1ul << MAP_LLONG_BIT; + + if (map & bit) { + if (bit == 1ul << MAP_LLONG_BIT) + cdecl__errmsg(CDECL__ETOOLONG); + else + cdecl__errmsg(CDECL__EDUPTYPE); + return false; + } + map |= bit; + } + + if (typemap_is_valid(map)) + return true; + + if (map == 0) + cdecl__errmsg(CDECL__ENOTYPE); + else + cdecl__errmsg(CDECL__EBADTYPE); + + return false; +} /* - * Verify the declaration specifiers of a declaration. + * Verify the declaration specifiers of a declaration. If top is true, treat + * this as a top-level declaration. Otherwise, treat this as a function + * parameter (which carries additional constraints). */ -static bool valid_declspecs(struct cdecl *decl) +static bool valid_declspecs(struct cdecl *decl, bool top) { - struct cdecl_declspec *specs = decl->specifiers; + struct cdecl_declspec *c, *specs = decl->specifiers; struct cdecl_declarator *d = decl->declarators; + bool abstract = cdecl_is_abstract(d); unsigned num_storage = 0; - unsigned long typemap; - typemap = cdecl__build_typemap(specs); - if (typemap == -1) - return -1; + if (!valid_typespec(specs)) + return false; - for (struct cdecl_declspec *c = specs; c; c = c->next) { + for (c = specs; c; c = c->next) { switch (cdecl_spec_kind(c)) { case CDECL_SPEC_TYPE: if (c->type == CDECL_TYPE_VOID && (d->type == CDECL_DECL_IDENT || d->type == CDECL_DECL_ARRAY)) { - fprintf(stderr, "invalid declaration of type void\n"); + cdecl__errmsg(CDECL__EBADVOID); return false; } continue; case CDECL_SPEC_STOR: + if (top && abstract) { + cdecl__errmsg(CDECL__ETYPESTOR); + return false; + } + + if (!top && c->type != CDECL_STOR_REGISTER) { + cdecl__errmsg(CDECL__EFUNCSTOR); + return false; + } + if (++num_storage > 1) { - fprintf(stderr, "too many storage-class specifiers\n"); + cdecl__errmsg(CDECL__EMANYSTOR); return false; } break; @@ -60,15 +160,16 @@ static bool valid_declspecs(struct cdecl *decl) * pointer qualifier list, which isn't checked here. */ if (c->type == CDECL_QUAL_RESTRICT) { - fprintf(stderr, "only pointer types can be restrict-qualified.\n"); + cdecl__errmsg(CDECL__EBADQUAL); return false; } break; case CDECL_SPEC_FUNC: - if (d->type != CDECL_DECL_FUNCTION) { - fprintf(stderr, "only function declarations may have function specifiers.\n"); + if (abstract || !top || d->type != CDECL_DECL_FUNCTION) { + cdecl__errmsg(CDECL__ENOTFUNC); return false; } + break; default: assert(0); @@ -78,6 +179,36 @@ static bool valid_declspecs(struct cdecl *decl) return true; } +/* + * Find the tree pointer which leads to the parameter's leaf node. + * + * Return a null pointer if the traversal locates a syntactic element which + * prevents function reduction. This occurs if the leaf node declares an + * identifier, or for nontrivial fake function parameters (see below). + */ +static struct cdecl_declarator **leaf_pointer(struct cdecl *param) +{ + struct cdecl_declarator *d, **p = ¶m->declarators; + + if ((param = fake_function_param(param->declarators))) { + if (param->declarators->type != CDECL_DECL_NULL) + return NULL; /* e.g. int (x (*)) */ + } + + while ((d = *p)->child) { + p = &d->child; + + if (fake_function_param(d->child)) + return NULL; /* e.g. int (x (*)[][1]) */ + } + + if (d->type != CDECL_DECL_NULL) + return NULL; /* e.g. int (x y) */ + + return p; +} + + /* * The C grammar leaves ambiguous some cases where parentheses represent a * function declarator or just parentheses. The language uses additional @@ -95,12 +226,6 @@ static bool valid_declspecs(struct cdecl *decl) * if a declarator could be interpreted as something other than a function, * do that. * - * - The function declarator has a null child declarator. - * - The function declarator has exactly one parameter, and is not variadic. - * - The function parameter has a type specifier, and it is a typedef name. - * - The function parameter has no other declaration specifiers. - * - The function parameter does not declare an identifier. - * * Since cdecl99 supports things like [*] in any context (in C, such constructs * are only valid in function parameter lists), we don't treat them specially * here. @@ -108,22 +233,26 @@ static bool valid_declspecs(struct cdecl *decl) static struct cdecl_declarator *reduce_function(struct cdecl *param) { - struct cdecl_declspec *spec = param->specifiers; - struct cdecl_declarator *decl = param->declarators; - struct cdecl_declarator *last; - - for (last = decl; last && last->type != CDECL_DECL_NULL;) - last = last->child; + struct parse_item *spec = (void *)param->specifiers; + struct cdecl_declarator *d, **p; - if (!last) + if (!(p = leaf_pointer(param))) return NULL; - last->type = CDECL_DECL_IDENT; - last->u.ident = spec->ident; + /* + * The child and u.ident members of cdecl_declarator are expected + * to be located at identical offsets as, respectively, the next + * and ident members within cdecl_declspec, so the expectation is + * that the compiler can elide both assignments. + */ + spec->u.declarator.child = (void *)spec->u.declspec.next; + spec->u.declarator.u.ident = spec->u.declspec.ident; + spec->u.declarator.type = CDECL_DECL_IDENT; + *p = &spec->u.declarator; + + d = param->declarators; free(param); - free(spec); - - return decl; + return d; } static bool function_is_reducible(struct cdecl_declarator *d) @@ -144,6 +273,8 @@ static bool function_is_reducible(struct cdecl_declarator *d) return false; /* e.g. int (int) */ if (d->u.function.parameters->specifiers->next) return false; /* e.g. int (size_t const) */ + if (d->u.function.parameters->declarators->type == CDECL_DECL_POINTER) + return false; /* e.g. int (x *) */ return true; } @@ -158,87 +289,202 @@ simplify_functions(struct cdecl_declarator **p, struct cdecl_declarator *d) new = reduce_function(d->u.function.parameters); if (!new) - return 0; /* e.g. int (foo bar) */ + return 0; *p = new; - free(d->child); free(d); return 1; } /* - * The parser's bias towards considering things as functions whenever possible - * makes nested parentheses tricky. (x) is considered to be part of a function - * declarator until simplify_functions converts it. The problem is that - * (((x))) is not valid as part of a function declarator, but it *is* valid - * as an identifier enclosed 3 times in parentheses. This is complicated by - * the fact that things like (((int))) are not valid anywhere. + * The main parser's bias towards considering things as functions whenever + * possible makes nested parentheses tricky. "(x)" is considered to be part + * of a function declarator until simplify_functions converts it. The problem + * is that "(((x)))" is not valid as part of a function declarator, but it _is_ + * valid as either an identifier enclosed thrice in parentheses, or an abstract + * function declarator enclosed twice in parentheses. + * + * To avoid ambiguities, the main parser actually returns a function declarator + * for every pair of parentheses. The ones we need to look at consist of a + * single parameter with an empty specifier list (noting that every real + * function parameter will have at least one type specifier). * - * To avoid ambiguities, the parser actually emits a "function" declarator for - * every pair of parentheses. The ones that can't reasonably be functions - * consist of a single "parameter" with no declaration specifiers (note that - * every valid function parameter will have at least one type specifier). + * There are two cases: * - * This pass is to remove these fake functions from the parse tree. We take - * care to avoid turning invalid things like ((int)) into valid things like - * (int) by observing that the only valid function declarators that appear - * in these "fake" parentheses are those that have a non-null child declarator - * (for instance, int ((*)(int)) *or* those that will be eliminated by the - * simplify_functions pass. + * - For (), the parser emits a parameter with a lone null declarator. + * This fake parameter simply gets deleted, leaving us with a normal + * function declarator with an empty identifier list. + * + * - Otherwise, the parameter's outermost declarator is not null. The + * function itself is deleted, replaced in the parse tree with the + * fake parameter's declarator. + * + * Repeating until there no fake parameters, this reduction transforms, for + * example, "(((x)))" into "(x)", an abstract function declarator. The result + * is then subject to the function simplification step, which will turn "(x)" + * into x (declaring an identifier). + * + * The whole process is repeated until no more changes are made to the parse + * tree, or a syntax error is detected. */ - -static int -reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d) +static struct cdecl *fake_function_param(struct cdecl_declarator *d) { struct cdecl *param; if (d->type != CDECL_DECL_FUNCTION) - return 0; + return NULL; param = d->u.function.parameters; - if (param && param->specifiers == NULL) { - struct cdecl_declarator *decl; + if (!param || param->specifiers) + return NULL; - assert(!param->next); + assert(!param->next); + return param; +} + +static int +reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d) +{ + struct cdecl *param; - decl = param->declarators; - if (decl->type == CDECL_DECL_NULL) { - free(decl); - free(param); + do { + d = *p; + while ((param = fake_function_param(d))) { + struct cdecl_declarator *decl = param->declarators; d->u.function.parameters = NULL; - return 0; + + if (decl->type != CDECL_DECL_NULL) { + if (d->child->type != CDECL_DECL_NULL) { + /* Fake parameter on real function. */ + d->u.function.parameters = param; + cdecl__errmsg(CDECL__EBADPARAM); + return -1; + } + + param->declarators = d; + *p = d = decl; + } + + cdecl__free(param); } + } while (simplify_functions(p, d)); + + return 0; +} + +/* + * Returns nonzero iff the given specifier list contains a specifier + * of the indicated type. + */ +static int have_specifier(struct cdecl_declspec *s, unsigned type) +{ + for (; s; s = s->next) + if (s->type == type) + return 1; + return 0; +} - if (d->child->type != CDECL_DECL_NULL) { - fprintf(stderr, "invalid function parameter\n"); +/* + * Check syntax restrictions on a function declarator's child declarator. + * That is, "pointer to function", "array of function" and "function + * returning function". + * + * Returns -1 if the declaration is invalid, or 0 otherwise. + */ +static int check_function_child(struct cdecl_declarator *d) +{ + struct cdecl_pointer *ptr; + + switch (d->type) { + case CDECL_DECL_POINTER: + ptr = &d->u.pointer; + if (have_specifier(ptr->qualifiers, CDECL_QUAL_RESTRICT)) { + /* pointer to function cannot be restrict qualified. */ + cdecl__errmsg(CDECL__ERESTRICTFUNC); return -1; } + return 0; + case CDECL_DECL_FUNCTION: + /* function returning function is never allowed. */ + cdecl__errmsg(CDECL__ERETFUNC); + return -1; + case CDECL_DECL_ARRAY: + /* array of function is never allowed. */ + cdecl__errmsg(CDECL__EFUNCARRAY); + return -1; + } - free(d->child); - free(param); - free(d); - *p = decl; + return 0; +} - /* - * We may have replaced d with another fake function which - * also needs to be eliminated. - */ - if (reduce_parentheses(p, decl) < 0) - return -1; +/* + * Check a function parameter declaration for validity, which means it has a + * valid combination of declaration specifiers and, if it is a void parameter, + * that it is the one special case where this is allowed. + * + * Returns -1 if the declaration is invalid, or 0 otherwise. + */ +static int check_function_param(struct cdecl_function *f, struct cdecl *param) +{ + if (!valid_declspecs(param, false)) + return -1; - /* - * If the remaining declarator is a function, make sure it's - * valid by checking its reducibility. - */ - decl = *p; - if (decl->type == CDECL_DECL_FUNCTION - && decl->child->type == CDECL_DECL_NULL - && !function_is_reducible(decl)) { - fprintf(stderr, "too many parentheses in function\n"); + /* Check for "void" function parameters as a special case. */ + if (param->declarators->type == CDECL_DECL_NULL + && have_specifier(param->specifiers, CDECL_TYPE_VOID)) + { + struct cdecl *fp = f->parameters; + + if (f->variadic || fp->next || fp->specifiers->next) { + cdecl__errmsg(CDECL__EVOIDPARAM); return -1; } + } - return 1; + return 0; +} + +/* + * Normalize the specifier lists for function parameters, and then check the + * function declarator for validity. + * + * Returns -1 if the declaration is invalid, or 0 otherwise. + */ +static int postproc_function(struct cdecl_declarator *d) +{ + struct cdecl_function *func = &d->u.function; + struct cdecl *param; + int rc; + + for (param = func->parameters; param; param = param->next) { + param->specifiers = cdecl__normalize_specs(param->specifiers); + + if ((rc = check_function_param(func, param)) < 0) + return rc; + } + + return check_function_child(d->child); +} + +static int +postproc_common(struct cdecl_declarator **p, struct cdecl_declarator *d) +{ + struct cdecl_pointer *ptr; + + switch (d->type) { + case CDECL_DECL_POINTER: + ptr = &d->u.pointer; + ptr->qualifiers = cdecl__normalize_specs(ptr->qualifiers); + return 0; + case CDECL_DECL_FUNCTION: + return postproc_function(d); + case CDECL_DECL_ARRAY: + if (d->child && d->child->type == CDECL_DECL_FUNCTION) { + /* function returning array is never allowed. */ + cdecl__errmsg(CDECL__ERETARRAY); + return -1; + } + return 0; } return 0; @@ -249,63 +495,135 @@ reduce_parentheses(struct cdecl_declarator **p, struct cdecl_declarator *d) * depth-first preorder traversal. The function is given a pointer to the * declarator as well as to the pointer which was used to reach that * declarator: this can be used to rewrite entire subtrees. + * + * The called function may return a negative value to indicate an error + * which terminates traversal. + * + * Returns 0 on success, or a negative value on failure. */ -static bool forall_declarators(struct cdecl *decl, +static int forall_declarators(struct cdecl *decl, int f(struct cdecl_declarator **, struct cdecl_declarator *)) { struct cdecl_declarator *d, **p; - for (p = &decl->declarators, d = *p; d; p = &d->child, d = *p) { - switch (f(p, d)) { - case 0: - break; - case 1: - d = *p; - break; - case -1: - return false; - default: - assert(0); - } + for (p = &decl->declarators; *p; p = &d->child) { + int rc; + + rc = f(p, *p); + if (rc < 0) + return rc; + d = *p; if (d->type == CDECL_DECL_FUNCTION) { struct cdecl *i; for (i = d->u.function.parameters; i; i = i->next) { - if (!forall_declarators(i, f)) - return false; + rc = forall_declarators(i, f); + if (rc < 0) + return rc; } } } - return true; + return 0; } -struct cdecl *cdecl_parse_decl(const char *declstr) +static struct cdecl *do_parse(const char *str, int english_mode) { + struct cdecl *decl = NULL; YY_BUFFER_STATE state; - struct cdecl *decl; - int rc; + yyscan_t scanner; - state = yy_scan_string(declstr); - rc = yyparse(&decl); - yy_delete_buffer(state); +#if YYDEBUG + extern int cdecl__yydebug; + cdecl__yydebug = 1; +#endif - if (rc != 0) + cdecl__init_i18n(); + if (cdecl__yylex_init_extra(english_mode, &scanner) != 0) return NULL; - for (struct cdecl *i = decl; i; i = i->next) { - if (!forall_declarators(i, reduce_parentheses)) - goto err; - if (!forall_declarators(i, simplify_functions)) - goto err; + state = cdecl__yy_scan_string(str, scanner); + if (cdecl__yyparse(scanner, &decl) != 0) { + /* + * If the input consists of a complete, valid declaration + * followed by some garbage, that parsed declaration will + * be output by the parser and we need to free it here. + */ + cdecl__free(decl); + decl = NULL; + } + cdecl__yy_delete_buffer(state, scanner); + cdecl__yylex_destroy(scanner); + + return decl; +} + +static int do_postprocess(struct cdecl *decl, int english_mode) +{ + struct cdecl_declspec *norm_specs; + struct cdecl *i; + + /* + * For a C declaration with more than one full declarator, the + * specifier list is common to all of them. Normalize it once, + * then propagate that to all the linked cdecl structures. + * + * In english mode, the cdecl structure list always has exactly + * one entry so we don't need to do anything differently. + */ + norm_specs = cdecl__normalize_specs(decl->specifiers); + for (i = decl; i; i = i->next) + i->specifiers = norm_specs; + + for (i = decl; i; i = i->next) { + if (!english_mode) { + if (forall_declarators(i, reduce_parentheses) < 0) + return 0; + } + + if (forall_declarators(i, postproc_common) < 0) + return 0; + + if (!valid_declspecs(i, true)) + return 0; - if (!valid_declspecs(i)) - goto err; + if (decl->next && cdecl_is_abstract(i->declarators)) { + /* Abstract full declarators: there can only be one. */ + cdecl__errmsg(CDECL__EDECLTYPE); + return 0; + } + } + + return 1; +} + +static struct cdecl *parse_common(const char *str, int english_mode) +{ + struct cdecl *decl; + + if (!(decl = do_parse(str, english_mode))) + return NULL; + + if (!do_postprocess(decl, english_mode)) { + cdecl__free(decl); + return NULL; } return decl; -err: - cdecl_free(decl); - return NULL; +} + +struct cdecl *cdecl_parse_decl(const char *declstr) +{ + return parse_common(declstr, false); +} + +struct cdecl *cdecl_parse_english(const char *english) +{ + return parse_common(english, true); +} + +void cdecl_free(struct cdecl *decl) +{ + cdecl__free(decl); }