sfx.c

一些常用的数据结构库

/*
 * 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 <[e-mail]>
 *
 * 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_RCSID
static 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;