/* * SFX---A utility which tries to determine whether a given C expression * is free of side effects. This can be used for verifying that macros which * expand their arguments more than once are not being accidentally misused. * * Copyright (C) 1999 Kaz Kylheku <kaz@ashi.footprints.net> * * Free Software License: * * All rights are reserved by the author, with the following exceptions: * Permission is granted to freely reproduce and distribute this software, * possibly in exchange for a fee, provided that this copyright notice appears * intact. Permission is also granted to adapt this software to produce * derivative works, as long as the modified versions carry this copyright * notice and additional notices stating that the work has been modified. * This source code may be translated into executable form and incorporated * into proprietary software; there is no requirement for such software to * contain a copyright notice related to this source. * * $Id: sfx.c,v 1.30 1999/11/13 08:41:55 kaz Exp $ * $Name: kazlib_1_20 $ */#include <ctype.h>#include <assert.h>#include <stdio.h>#include <string.h>#include "except.h"#include "sfx.h"#include "hash.h"#ifdef KAZLIB_POSIX_THREADS#include <pthread.h>#endif#ifdef KAZLIB_RCSIDstatic const char rcsid[] = "$Id: sfx.c,v 1.30 1999/11/13 08:41:55 kaz Exp $";#endif/* * Exceptions */#define SFX_EX		0x34DB9C4A#define SFX_SYNERR	1/* * Cache entry */typedef struct {    hnode_t node;    const char *expr;    sfx_rating_t eff;} sfx_entry_t;/* * Parsing context structure */typedef struct {    const unsigned char *start;    const unsigned char *input;    size_t size;    sfx_rating_t eff;} context_t;/* * Declarator type: abstract, concrete or both */typedef enum {    decl_abstract, decl_concrete, decl_both} decl_t;static void init_context(context_t *ctx, const unsigned char *expr){    ctx->input = ctx->start = expr;    ctx->size = strlen((const char *) expr) + 1;    ctx->eff = sfx_none;}static void assign_context(context_t *copy, context_t *orig){    *copy = *orig;}static void set_effect(context_t *ctx, sfx_rating_t eff){    assert (eff == sfx_none || eff == sfx_potential || eff == sfx_certain);    if (eff > ctx->eff)	ctx->eff = eff;}static void reset_effect(context_t *ctx){    ctx->eff = sfx_none;}static sfx_rating_t get_effect(context_t *ctx){    return ctx->eff;}static int skip_ws(context_t *expr){    while (*expr->input != 0 && isspace(*expr->input))	expr->input++;    return (*expr->input == 0);}static int get_next(context_t *expr){    int ret = *expr->input;    if (ret)	expr->input++;    return ret;}static int get_next_skip_ws(context_t *expr){    if (!skip_ws(expr))	return *expr->input++;    return 0;}static const unsigned char *get_ptr(context_t *expr){    return expr->input;}static void skip_n(context_t *ctx, size_t n){    assert ((size_t) (ctx->input - ctx->start) <= ctx->size - n);    ctx->input += n;}static void put_back(context_t *expr, int ch){    if (ch)	expr->input--;}static int peek_next(context_t *expr){    return *expr->input;}static void syntax_error(void){    except_throw(SFX_EX, SFX_SYNERR, "syntax_error");}static void match_hard(context_t *expr, int match){    int ch = get_next(expr);    if (ch != match)	syntax_error();}static void chk_comma(context_t *);static void skip_ident(context_t *expr){    int ch = get_next(expr);    if (!isalpha(ch) && ch != '_')	syntax_error();    do {	ch = get_next(expr);    } while (isalnum(ch) || ch == '_');    put_back(expr, ch);}static void skip_constant(context_t *expr){    int ch = get_next(expr);    assert (isdigit(ch) || ch == '.');    do {	ch = get_next(expr);	if (ch == 'e' || ch == 'E') {	    ch = get_next(expr);	    if (ch == '+' || ch == '-') {		ch = get_next(expr);		if (!isdigit(ch))		    syntax_error();	    }	}    } while (ch != 0 && (isalnum(ch) || ch == '.'));    put_back(expr, ch);}static void skip_strlit(context_t *expr){    int ch = get_next(expr);    assert (ch == '"');    do {	ch = get_next(expr);	if (ch == '\\') {	    get_next(expr);	    continue;	}    } while (ch != 0 && ch != '"');    if (ch != '"')	syntax_error();}static void skip_charlit(context_t *expr){    int ch = get_next(expr);    assert (ch == '\'');    do {	ch = get_next(expr);	if (ch == '\\') {	    get_next(expr);	    continue;	}    } while (ch != 0 && ch != '\'');    if (ch != '\'')	syntax_error();}static void chk_spec_qual_list(context_t *expr){    skip_ws(expr);    skip_ident(expr);    for (;;) {	int ch;	skip_ws(expr);	ch = peek_next(expr);	if (!isalpha(ch) && ch != '_')	    break;	skip_ident(expr);    }}static int speculate(void (*chk_func)(context_t *), context_t *expr, context_t *copy, int nextchar){    static const except_id_t catch[] = { { SFX_EX, XCEPT_CODE_ANY } };    except_t *ex;    volatile int result = 0;    assign_context(copy, expr);    except_try_push(catch, 1, &ex);    if (ex == 0) {	chk_func(copy);	if (nextchar) {	    skip_ws(copy);	    match_hard(copy, nextchar);	}	result = 1;    }     except_try_pop();    return result;}static void chk_pointer_opt(context_t *expr){    for (;;) {	int ch = get_next_skip_ws(expr);	if (ch != '*') {	    put_back(expr, ch);	    break;	}	skip_ws(expr);	ch = peek_next(expr);	if (ch == '*')	    continue;	if (!isalpha(ch) && ch != '_')	    break;	skip_ident(expr);    }}static void chk_decl(context_t *, decl_t);static void chk_parm_decl(context_t *expr){    chk_spec_qual_list(expr);    chk_decl(expr, decl_both);}static void chk_parm_type_list(context_t *expr){    for (;;) {	int ch;	chk_parm_decl(expr);	ch = get_next_skip_ws(expr);	if (ch != ',') {	    put_back(expr, ch);	    break;	}	ch = get_next_skip_ws(expr);	if (ch == '.') {	    match_hard(expr, '.');	    match_hard(expr, '.');	    break;	}	put_back(expr, ch);    }}static void chk_conditional(context_t *);static void chk_direct_decl(context_t *expr, decl_t type){    for (;;) {	int ch = get_next_skip_ws(expr);	if (ch == '(') {	    skip_ws(expr);	    ch = peek_next(expr);	    if (ch == '*' || ch == '(' || ch == '[')		chk_decl(expr, type);	    else if (isalpha(ch) || ch == '_')		chk_parm_type_list(expr);	    match_hard(expr, ')');	} else if (ch == '[') {	    skip_ws(expr);	    ch = peek_next(expr);	    if (ch != ']')		chk_conditional(expr);	    match_hard(expr, ']');			} else if ((type == decl_concrete || type == decl_both) && (isalpha(ch) || ch == '_')) {	    put_back(expr, ch);	    skip_ident(expr);	    break;	} else {	    put_back(expr, ch);	    break;	}    }}static void chk_decl(context_t *expr, decl_t type){    int ch;    chk_pointer_opt(expr);    skip_ws(expr);    ch = peek_next(expr);    if (ch == '[' || ch == '(' || ((type == decl_concrete || type == decl_both) && (isalpha(ch) || ch == '_'))) {	chk_direct_decl(expr, type);    } }static void chk_typename(context_t *expr){    chk_spec_qual_list(expr);    chk_decl(expr, decl_abstract);}static void chk_primary(context_t *expr){    int ch = peek_next(expr);    if (ch == 'L') {	get_next(expr);	ch = peek_next(expr);	if (ch == '\'') {	    skip_charlit(expr);	    return;	}	if (ch == '"') {	    skip_strlit(expr);	    return;	}	put_back(expr, 'L');	ch = 'L';    }    if (isalpha(ch) || ch == '_') {    	skip_ident(expr);	return;    }    if (isdigit(ch) || ch == '.') {	skip_constant(expr);	return;    }    if (ch == '(') {	get_next(expr);	chk_comma(expr);	match_hard(expr, ')');	return;    }    if (ch == '\'') {	skip_charlit(expr);	return;    }    if (ch == '"') {	skip_strlit(expr);	return;    }    syntax_error();}static void chk_postfix(context_t *expr){    chk_primary(expr);    for (;;) {	int ch = get_next_skip_ws(expr);	switch (ch) {	case '[':	    chk_comma(expr);	    skip_ws(expr);	    match_hard(expr, ']');	    continue;	case '(':	    set_effect(expr, sfx_potential);	    ch = get_next_skip_ws(expr);	    if (ch != ')') {		put_back(expr, ch);		/* clever hack: parse non-empty argument list as comma expression */		chk_comma(expr);		ch = get_next_skip_ws(expr);	    }	    if (ch != ')')		syntax_error();	    continue;	case '.':	    skip_ws(expr);	    skip_ident(expr);	    continue;	case '-':	    ch = get_next(expr);	    if (ch != '-' && ch != '>') {		put_back(expr, ch);		put_back(expr, '-');		break;	    }	    if (ch == '>') {		skip_ws(expr);		skip_ident(expr);		continue;	    }	    set_effect(expr, sfx_certain);	    continue;	case '+':	    ch = get_next(expr);	    if (ch != '+') {		put_back(expr, ch);		put_back(expr, '+');		break;	    }	    set_effect(expr, sfx_certain);	    continue;	default:	    put_back(expr, ch);	    break;	}	break;    }}static void chk_cast(context_t *);static void chk_unary(context_t *expr){    for (;;) {	int nscan, ch = get_next_skip_ws(expr);	switch (ch) {	case '+':	    ch = get_next(expr);	    if (ch == '+')		set_effect(expr, sfx_certain);	    else		put_back(expr, ch);	    chk_cast(expr);	    break;	case '-':	    ch = get_next(expr);	    if (ch == '-')		set_effect(expr, sfx_certain);	    else		put_back(expr, ch);	    chk_cast(expr);	    break;	case '&': case '*': case '~': case '!':	    chk_cast(expr);	    break;	case 's':	    put_back(expr, ch);	    nscan = 0;	    sscanf((const char *) get_ptr(expr), "sizeof%*1[^a-z0-9_]%n", &nscan);	    if (nscan == 7 || strcmp((const char *) get_ptr(expr), "sizeof") == 0) {		sfx_rating_t eff = get_effect(expr);	    	skip_n(expr, 6);		ch = get_next_skip_ws(expr);		if (ch == '(') {		    context_t comma, type;		    int iscomma = speculate(chk_comma, expr, &comma, ')');		    int istype = speculate(chk_typename, expr, &type, ')');		    if (!iscomma && !istype)			syntax_error();		    if (iscomma) {			context_t unary;			put_back(expr, ch);			if (speculate(chk_unary, expr, &unary, 0)) {			    assign_context(expr, &unary);			    istype = 0;			}		    }		    if (istype)			assign_context(expr, &type);		} else {		    put_back(expr, ch);		    chk_unary(expr);		}		reset_effect(expr);		set_effect(expr, eff);		break;	    }	    chk_postfix(expr);	    break;	default:	    put_back(expr, ch);	    chk_postfix(expr);	    break;	}	break;    }}static void chk_cast(context_t *expr){    enum {	parexpr,	/* parenthesized expression */	partype,	/* parenthesized type name */	parambig,	/* ambiguity between paren expr and paren type name */	unary,		/* unary expression */	plunary,	/* unary expression with leading plus or minus */	other		/* none of the above, or even end of input */    } curr = partype, old = partype, peek = partype;    /* history for backtracking: two cast expression elements back */    context_t old_expr = { 0 }, cur_expr = { 0 };    for (;;) {	context_t type, comma, unr;