/*
 * exprpars.c - Pcal routines concerned with parsing if{n}def expressions
 *
 * Contents:
 *
 *		do_xxx
 *		lookup_token
 *		next_token
 *		parse_expr
 *
 * Revision history:
 *
 *	4.0	AWR	02/06/91	Author
 *
 */

/*
 * Standard headers:
 */

#include <ctype.h>
#include <string.h>
#include <stdio.h>

/*
 * Pcal-specific definitions:
 */

#include "pcaldefs.h"
#include "pcalglob.h"

/*
 * Macros:
 */

/*
 * token type code definitions:
 */

#define TK_UNKNOWN	 0		/* codes returned by next_token() */
#define TK_IDENT	 1
#define TK_LPAREN	 2
#define TK_RPAREN	 3
#define TK_UNARYOP	 4
#define TK_BINARYOP	 5
#define TK_ENDINPUT	 6
#define TK_STARTINPUT	 7		/* special code for start symbol */

/* bit position for token type codes (cf. where_ok[] below) */
#define ID_OK		(1 << TK_IDENT)
#define LP_OK		(1 << TK_LPAREN)
#define RP_OK		(1 << TK_RPAREN)
#define UO_OK		(1 << TK_UNARYOP)
#define BO_OK		(1 << TK_BINARYOP)
#define ST_OK		(1 << TK_STARTINPUT)
#define NEVER_OK	0

/* is token "curr" legal after "prev"? (cf. where_ok[] below) */
#define IS_LEGAL(curr, prev)	(where_ok[curr] & (1 << (prev)))

/*
 * operator-related definitions:
 */

#define OP_AND		0	/* operator subcodes */
#define OP_OR		1
#define OP_XOR		2
#define OP_NEGATE	3

#define ENDINPUT_PREC	-1	/* arbitrary number < lowest op. prec  */
#define OR_PREC		 1	/* operator precedence levels */
#define XOR_PREC	 2
#define AND_PREC	 3
#define NEGATE_PREC	 4
#define PAREN_PREC	 8	/* arbitrary number > highest op. prec */

/* lower bits of operator stack entry are code; higher are precedence */
#define OPR_BITS	4
#define OPR_MASK	((1 << OPR_BITS) - 1)
#define PREC(op)	((op) >> OPR_BITS)
#define OPCODE(op)	((op) & OPR_MASK)
#define MAKE_OPR(p, o)	(((p) << OPR_BITS) | (o))

#define MAX_OP		20	/* size of operand and operator stacks */

/*
 * Globals:
 */

typedef short OPERAND;		/* types for operand and operator stacks */
typedef short OPERATOR;


typedef struct {
	char	*name;		/* token spelling */
	short	type;		/* token type code */
	short	value;		/* associated value */
	} TOKEN;

/* token table - note that substrings must follow longer strings */

TOKEN token_tbl[] = {
	"&&",	TK_BINARYOP,	OP_AND,		/* synonym for "&" */
	"&",	TK_BINARYOP,	OP_AND,
	"||",	TK_BINARYOP,	OP_OR,		/* synonym for "|" */
	"|",	TK_BINARYOP,	OP_OR,
	"!",	TK_UNARYOP,	OP_NEGATE,
	"^",	TK_BINARYOP,	OP_XOR,
	"(",	TK_LPAREN,	0,
	")",	TK_RPAREN,	0,
	NULL,	TK_UNKNOWN,	0		/* must be last entry */
	};


typedef struct {
	short prec;		/* precedence */
	short type;		/* token type (TK_UNARYOP or TK_BINARYOP) */
#ifdef PROTOS
	OPERAND (*pfcn)(OPERAND *);	/* dispatch function */
#else
	OPERAND (*pfcn)();		/* dispatch function */
#endif
	} OPR;

/* operator table - entries must be in same order as OP_XXX */

#ifdef PROTOS
static OPERAND do_and(OPERAND *);
static OPERAND do_or(OPERAND *);
static OPERAND do_xor(OPERAND *);
static OPERAND do_negate(OPERAND *);
#else
static OPERAND do_and(), do_or(), do_xor(), do_negate();   /* dispatch fcns */
#endif

OPR opr_tbl[] = {
	AND_PREC,	TK_BINARYOP,	do_and,		/* OP_AND	*/
	OR_PREC,	TK_BINARYOP,	do_or,		/* OP_OR	*/
	XOR_PREC,	TK_BINARYOP,	do_xor,		/* OP_XOR	*/
	NEGATE_PREC,	TK_UNARYOP,	do_negate	/* OP_NEGATE	*/
	};


/* set of tokens which each token may legally follow (in TK_XXX order) */

int where_ok[] = {
	NEVER_OK                                      ,	 /* TK_UNKNOWN	*/
	ST_OK         | LP_OK         | UO_OK | BO_OK ,	 /* TK_IDENT	*/
	ST_OK         | LP_OK         | UO_OK | BO_OK ,	 /* TK_LPAREN	*/
	        ID_OK | LP_OK | RP_OK                 ,	 /* TK_RPAREN	*/
	ST_OK         | LP_OK                 | BO_OK ,	 /* TK_UNARYOP	*/
	        ID_OK         | RP_OK                 ,	 /* TK_BINARYOP	*/
	ST_OK | ID_OK         | RP_OK                    /* TK_ENDINPUT	*/
	};


/*
 * do_xxx - dispatch functions for operators
 */

#ifdef PROTOS
static OPERAND do_and(OPERAND *ptop)
#else
static OPERAND do_and(ptop)
	OPERAND *ptop;
#endif
{
	return ptop[0] & ptop[-1];
}


#ifdef PROTOS
static OPERAND do_or(OPERAND *ptop)
#else
static OPERAND do_or(ptop)
	OPERAND *ptop;
#endif
{
	return ptop[0] | ptop[-1];
}


#ifdef PROTOS
static OPERAND do_xor(OPERAND *ptop)
#else
static OPERAND do_xor(ptop)
	OPERAND *ptop;
#endif
{
	return ptop[0] ^ ptop[-1];
}


#ifdef PROTOS
static OPERAND do_negate(OPERAND *ptop)
#else
static OPERAND do_negate(ptop)
	OPERAND *ptop;
#endif
{
	return ! ptop[0];
}


/*
 * lookup_token - look up token in table; return pointer to table entry
 */
#ifdef PROTOS
static TOKEN *lookup_token(char *p)
#else
static TOKEN *lookup_token(p)
	char *p;
#endif
{
	TOKEN *ptok;

	for (ptok = token_tbl;
	     ptok->name && strncmp(p, ptok->name, strlen(ptok->name));
	     ptok++)
		;

	return ptok;
}


/*
 * next_token - fetch next token from input string; fill in its type and value
 * and return pointer to following character
 */
#ifdef PROTOS
static char *next_token(char *p,
			int *ptype,
			int *pvalue)
#else
static char *next_token(p, ptype, pvalue)
	char *p;
	int *ptype;
	int *pvalue;
#endif
{
	TOKEN *ptok;
	char tokbuf[STRSIZ], *pb;

#define NT_RETURN(p, t, v) \
	if (1) { *ptype = t; *pvalue = v; return p; } else

	while (*p && isspace(*p))	/* skip whitespace */
		p++;

	if (*p == '\0')			/* end of input? */
		NT_RETURN(p, TK_ENDINPUT, 0);

	if (isalpha(*p) || *p == '-') {		/* identifier or flag? */

		pb = tokbuf;		/* make local copy and look up */
		while (*p && (isalpha(*p) || isdigit(*p) || *p == '_' ||
		       (pb == tokbuf && *p == '-')))
			*pb++ = *p++;
		*pb = '\0';

		NT_RETURN(p, TK_IDENT, find_sym(tokbuf));
	}

	ptok = lookup_token(p);		/* other token */
	NT_RETURN(p + (ptok->name ? strlen(ptok->name) : 1), ptok->type,
		ptok->value);
}


/*
 * parse_expr - parses expression consisting of identifiers and logical
 * operators; return TRUE if expression is true (identifier defined => true);
 * FALSE if false; EXPR_ERR if syntax error in expression
 */
#ifdef PROTOS
int parse_expr(char *pbuf)
#else
int parse_expr(pbuf)
	char *pbuf;
#endif
{
	OPERAND opd_stack[MAX_OP];	/* operand stack - TRUE/FALSE values */
	OPERATOR opr_stack[MAX_OP];	/* operator stack - precedence | op */
	int value, token, plevel, prec, result, npop, opr, opd, prev_token, op;

	plevel = 0;			/* paren nesting level */
	opd = opr = -1;			/* indices of stack tops */
	prev_token = TK_STARTINPUT;	/* to detect null expressions */

	if (DEBUG(DEBUG_PP))
		FPR(stderr, "evaluating expression '%s'\n", pbuf);
	do {
		pbuf = next_token(pbuf, &token, &value);

		/* check that the current token may follow the previous one */
		if (! IS_LEGAL(token, prev_token))
			return EXPR_ERR;

		switch(token) {

		case TK_IDENT:		/* identifier => 1 if def, 0 if not */
			opd_stack[++opd] = value != PP_SYM_UNDEF;
			break;

		case TK_LPAREN:		/* left paren - bump nesting level */
			++plevel;
			break;

		case TK_RPAREN:		/* right paren - decrement nesting */
			if (--plevel < 0)
				return EXPR_ERR;
			break;

		case TK_ENDINPUT:	/* end-of-input - treat as operator */
			if (prev_token == TK_STARTINPUT)
				return FALSE;	/* null expr => FALSE */
			/* fall through */

		case TK_UNARYOP:
		case TK_BINARYOP:

			/* get precedence of operator, adjusting for paren
			 * nesting (TK_ENDINPUT has the lowest precedence
			 * of all, to unwind operand/operator stacks at end)
			 */

			prec = token == TK_ENDINPUT ? ENDINPUT_PREC :
				(plevel * PAREN_PREC) + opr_tbl[value].prec;

			/* pop (and perform) any equal- or higher-precedence
			 * operators on operator stack: extract operator,
			 * check for operand stack underflow, execute
			 * operator, adjust operand stack height and place
			 * result of operator on top
			 */

			for ( ;
			     opr >= 0 && PREC(opr_stack[opr]) >= prec;
			     opr--) {
				op = OPCODE(opr_stack[opr]);
				npop = opr_tbl[op].type == TK_UNARYOP ? 0 : 1;
				if (opd < npop)
					return EXPR_ERR;
				result = (*opr_tbl[op].pfcn)(opd_stack + opd);
				opd_stack[opd -= npop] = result;
			}

			/* push operator (if any) onto stack */

			if (token != TK_ENDINPUT)
				opr_stack[++opr] = MAKE_OPR(prec, value);

			break;

		default:		/* should never get here */
			return EXPR_ERR;
			break;

		}

		prev_token = token;

	} while (token != TK_ENDINPUT);

	/* done - check for dangling parens, and leftover operand/operators */

	if (DEBUG(DEBUG_PP))
		FPR(stderr, "evaluated to %s\n", opd_stack[0] ? "TRUE" : "FALSE");
	return plevel != 0 || opd != 0 || opr != -1 ?
		EXPR_ERR :		/* leftover junk - return error */
		opd_stack[0];		/* all OK - return final value */
}