Added expression handler for EMMA

1 files changed, 728 insertions, 0 deletions

diff --git a/expr.c b/expr.c
new file mode 100644
index 0000000..9369e1d
--- /dev/null
+++ b/expr.c
@@ -0,0 +1,728 @@
+/*
+    expr - Simple, expression evaluator
+
+    Copyright (C) 2003  Ian Cowburn (ianc@noddybox.demon.co.uk)
+
+    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 2 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.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+    -------------------------------------------------------------------------
+
+    Expands an expression.
+
+*/
+static const char id[]="$Id$";
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+/* ---------------------------------------- MACROS
+*/
+#define TRUE		1
+#define FALSE		0
+
+#define TYPE_OPERAND	0
+#define TYPE_VARIABLE	1
+#define TYPE_OPERATOR	2	/* This acts as a base for operator tokens */
+#define TYPE_LPAREN	3
+#define TYPE_RPAREN	4
+#define TYPE_DIVIDE	5
+#define TYPE_MULTIPLY	6
+#define TYPE_ADD	7
+#define TYPE_SUBTRACT	8
+#define TYPE_NOT	9
+#define TYPE_AND	10
+#define TYPE_OR		11
+#define TYPE_XOR	12
+#define TYPE_UNARY_PLUS	13
+#define TYPE_UNARY_NEG	14
+#define TYPE_SHIFTL	15
+#define TYPE_SHIFTR	16
+#define TYPE_EQUALITY	17
+#define TYPE_BOOL_AND	18
+#define TYPE_BOOL_OR	19
+#define TYPE_MODULUS	20
+#define TYPE_LT		21
+#define TYPE_GT		22
+#define TYPE_LTEQ	23
+#define TYPE_GTEQ	24
+#define TYPE_NOTEQUAL	25
+
+#define SYM_LPAREN	"("
+#define SYM_RPAREN	")"
+#define SYM_DIVIDE	"/"
+#define SYM_MULTIPLY	"*"
+#define SYM_ADD		"+"
+#define SYM_SUBTRACT	"-"
+#define SYM_NOT		"~"
+#define SYM_AND		"&"
+#define SYM_OR		"|"
+#define SYM_XOR		"^"
+#define SYM_UNARY_PLUS	"+"
+#define SYM_UNARY_NEG	"-"
+#define SYM_SHIFTL	"<<"
+#define SYM_SHIFTR	">>"
+#define SYM_EQUALITY	"=="
+#define SYM_BOOL_AND	"&&"
+#define SYM_BOOL_OR	"||"
+#define SYM_MODULUS	"%"
+#define SYM_LT		"<"
+#define SYM_GT		">"
+#define SYM_LTEQ	"<="
+#define SYM_GTEQ	">="
+#define SYM_NOTEQUAL	"!="
+
+#define OPERATOR_CHARS	"()/*+-~&|^<>!=%"
+
+#define IS_OPERATOR_TYPE(a)	((a)>=TYPE_OPERATOR)
+
+#define IS_PAREN(c)		((c)==SYM_LPAREN[0] || (c)==SYM_RPAREN[0])
+
+#define IS_OPERATOR(c)		(strchr(OPERATOR_CHARS,(c)))
+
+#define IS_OPERAND_END(c)	((c)==' ' || (c)=='\t' || IS_OPERATOR(c))
+
+/* ---------------------------------------- TYPES
+*/
+
+typedef struct stk
+    {
+    int		token;
+    int		priority;
+    int		is_unary;
+    char	*text;
+    struct stk	*next;
+    } Stack;
+
+
+typedef enum {OpBinary, OpPretendUnary, OpUnary} OpType;
+
+typedef struct
+    {
+    const char	*symbol;
+    int		priority;
+    int		token;
+    OpType	type;
+    int		allow_unary;
+    } Operator;
+
+
+typedef enum {OpOk, OpSyntaxError, OpUnknown} OpError;
+
+
+/* ---------------------------------------- GLOBALS
+*/
+static char		error[1024];
+
+static int		(*expand)(void *client_data,
+				  const char *p,
+				  long *value);
+
+static void		*client=NULL;
+
+static const Operator	op_info[]=
+    {
+	/* Unary ops - must be first in list.  Note that LPAREN is treated
+	   as a unary as it must be preceeded by another operator, rather
+	   than an operand.
+	*/
+    	{SYM_NOT,	9,	TYPE_NOT,	OpUnary,	TRUE},
+    	{SYM_UNARY_PLUS,9,	TYPE_UNARY_PLUS,OpUnary,	TRUE},
+    	{SYM_UNARY_NEG,	9,	TYPE_UNARY_NEG,	OpUnary,	TRUE},
+    	{SYM_LPAREN,	99,	TYPE_LPAREN,	OpPretendUnary,	TRUE},
+
+	/* Binary ops and don't care ops
+	*/
+    	{SYM_RPAREN,	99,	TYPE_RPAREN,	OpBinary,	FALSE},
+    	{SYM_SHIFTL,	6,	TYPE_SHIFTL,	OpBinary,	TRUE},
+    	{SYM_SHIFTR,	6,	TYPE_SHIFTR,	OpBinary,	TRUE},
+    	{SYM_MULTIPLY,	5,	TYPE_MULTIPLY,	OpBinary,	TRUE},
+    	{SYM_DIVIDE,	5,	TYPE_DIVIDE,	OpBinary,	TRUE},
+    	{SYM_MODULUS,	5,	TYPE_MODULUS,	OpBinary,	TRUE},
+    	{SYM_ADD,	4,	TYPE_ADD,	OpBinary,	TRUE},
+    	{SYM_SUBTRACT,	4,	TYPE_SUBTRACT,	OpBinary,	TRUE},
+    	{SYM_EQUALITY,	1,	TYPE_EQUALITY,	OpBinary,	TRUE},
+    	{SYM_NOTEQUAL,	1,	TYPE_NOTEQUAL,	OpBinary,	TRUE},
+    	{SYM_LTEQ,	1,	TYPE_LTEQ,	OpBinary,	TRUE},
+    	{SYM_GTEQ,	1,	TYPE_GTEQ,	OpBinary,	TRUE},
+    	{SYM_LT,	1,	TYPE_LT,	OpBinary,	TRUE},
+    	{SYM_GT,	1,	TYPE_GT,	OpBinary,	TRUE},
+    	{SYM_BOOL_AND,	0,	TYPE_BOOL_AND,	OpBinary,	TRUE},
+    	{SYM_AND,	0,	TYPE_AND,	OpBinary,	TRUE},
+    	{SYM_BOOL_OR,	0,	TYPE_BOOL_OR,	OpBinary,	TRUE},
+    	{SYM_OR,	0,	TYPE_OR,	OpBinary,	TRUE},
+    	{SYM_XOR,	0,	TYPE_XOR,	OpBinary,	TRUE},
+
+	{0,0,0}
+    };
+
+
+/* ---------------------------------------- PRIVATE FUNCTIONS
+*/
+
+/* malloc wrapper
+*/
+static void *Malloc(size_t size)
+{
+    void *p=malloc(size);
+
+    if (!p)
+    {
+    	fprintf(stderr,"malloc failed\n");
+	exit(EXIT_FAILURE);
+    }
+
+    return p;
+}
+
+
+/* Copy a string
+*/
+static char *CopyStr(const char *p)
+{
+    char *new=Malloc(strlen(p)+1);
+
+    return strcpy(new,p);
+}
+
+
+/* Empty a stack
+*/
+static Stack *ClearStack(Stack *stack)
+{
+    while(stack)
+    {
+    	Stack *tmp=stack;
+
+	stack=stack->next;
+	free(tmp->text);
+	free(tmp);
+    }
+
+    return stack;
+}
+
+
+/* Push onto the stack
+*/
+static Stack *Push(Stack *stack, int token, int priority, 
+		   int is_unary, const char *text)
+{
+    Stack *e=Malloc(sizeof *e);
+
+    e->text=CopyStr(text);
+    e->priority=priority;
+    e->token=token;
+    e->is_unary=is_unary;
+    e->next=stack;
+    stack=e;
+
+    return stack;
+}
+
+
+/* Destroy the top element on the stack
+*/
+static Stack *Pop(Stack *stack)
+{
+    if (stack)
+    {
+	Stack *tmp=stack;
+
+	stack=stack->next;
+
+    	free(tmp->text);
+	free(tmp);
+    }
+
+    return stack;
+}
+
+
+/* Debug to dump a stack non-destructively
+static void Dump(const char *name, Stack *stack)
+{
+    while (stack)
+    {
+    	printf("%-10s: Type: %-2d  is_unary: %d  text: %s\n",
+			name,stack->token,stack->is_unary,stack->text);
+
+	stack=stack->next;
+    }
+}
+*/
+
+
+/* Find the symbol for an operator
+*/
+static const char *ToString(int token)
+{
+    static char buff[32];
+    int f;
+
+    strcpy(buff,"UNKNOWN");
+
+    for(f=0;op_info[f].symbol;f++)
+    {
+    	if (op_info[f].token==token)
+	{
+	    strcpy(buff,op_info[f].symbol);
+	    return buff;
+	}
+    }
+
+    return "UNKNOWN";
+}
+
+
+/* Search the operator info
+*/
+static OpError FindOp(const char *p, int prev_was_op, const Operator **op)
+{
+    int f;
+    int found=FALSE;
+
+    *op=NULL;
+
+    for(f=0;op_info[f].symbol;f++)
+    {
+    	if (strncmp(op_info[f].symbol,p,strlen(op_info[f].symbol))==0)
+	{
+	    found=TRUE;
+
+	    if ((prev_was_op && op_info[f].type!=OpBinary) ||
+		(!prev_was_op && op_info[f].type==OpBinary))
+	    	
+	    {
+		*op=op_info+f;
+		return OpOk;
+	    }
+	}
+    }
+
+    if (found)
+    	return OpSyntaxError;
+    else
+    	return OpUnknown;
+}
+
+
+static Stack *ToPostfix(const char *expr)
+{
+    Stack *stack=NULL;
+    Stack *output=NULL;
+    char buff[1024];
+    char *p;
+    int prev_was_op=TRUE;
+
+    /* Parse the infix expression into postfix
+    */
+    while(*expr)
+    {
+    	if (IS_OPERATOR(*expr))
+	{
+	    /* Found an operator - parse it
+	    */
+	    const Operator *op;
+	    OpError op_err;
+	    
+	    op_err=FindOp(expr,prev_was_op,&op);
+
+	    /* Unknown operator in expression
+	    */
+	    if (!op)
+	    {
+		if (op_err==OpSyntaxError)
+		    sprintf(error,"Syntax error with operator %c",*expr);
+		else
+		    sprintf(error,"Unknown operator %c",*expr);
+
+	    	stack=ClearStack(stack);
+	    	output=ClearStack(output);
+
+		return NULL;
+	    }
+
+	    /* Special handling for closing parenthesis
+	    */
+	    if (op->token==TYPE_RPAREN)
+	    {
+	    	while(stack && stack->token!=TYPE_LPAREN)
+		{
+		    output=Push(output,
+		    		stack->token,
+				stack->priority,
+				stack->is_unary,
+				stack->text);
+		    stack=Pop(stack);
+		}
+
+		/* Syntax error in expression
+		*/
+		if (!stack)
+		{
+		    sprintf(error,"Missing %s",SYM_LPAREN);
+
+		    stack=ClearStack(stack);
+		    output=ClearStack(output);
+
+		    return NULL;
+		}
+
+		/* Remove the opening bracket and continue
+		*/
+		stack=Pop(stack);
+	    }
+	    else
+	    {
+	    	/* Output the stack until an operator of lower precedence is
+		   found
+		*/
+		if (op->type==OpUnary)
+		{
+		    while(stack && !IS_PAREN(stack->text[0]) &&
+			    !stack->is_unary &&
+				(stack->priority >= op->priority))
+		    {
+			output=Push(output,
+				    stack->token,
+				    stack->priority,
+				    stack->is_unary,
+				    stack->text);
+
+			stack=Pop(stack);
+		    }
+		}
+		else
+		{
+		    while(stack && !IS_PAREN(stack->text[0]) &&
+				(stack->priority >= op->priority))
+		    {
+			output=Push(output,
+				    stack->token,
+				    stack->priority,
+				    stack->is_unary,
+				    stack->text);
+
+			stack=Pop(stack);
+		    }
+		}
+
+		stack=Push(stack,
+			   op->token,
+			   op->priority,
+			   op->type==OpUnary,
+			   op->symbol);
+	    }
+
+	    /* Move past token
+	    */
+	    expr+=strlen(op->symbol);
+
+	    prev_was_op=op->allow_unary;
+	}
+	else
+	{
+	    /* Found an operand - parse and store the operand
+	    */
+	    p=buff;
+
+	    while(*expr && !IS_OPERAND_END(*expr))
+	    {
+	    	*p++=*expr++;
+	    }
+
+	    *p=0;
+
+	    /* Note that operands are marked as unary just to chose one over
+	       the other branch in EvalPostfix() - no other reason
+	    */
+	    output=Push(output,TYPE_OPERAND,0,TRUE,buff);
+
+	    prev_was_op=FALSE;
+	}
+    }
+
+    while(stack)
+    {
+	output=Push(output,
+		    stack->token,
+		    stack->priority,
+		    stack->is_unary,
+		    stack->text);
+
+	stack=Pop(stack);
+    }
+
+    /* Return the stack
+    */
+    return output;
+}
+
+
+static int EvalPostfix(Stack **stack, long *result)
+{
+    Stack *expr;
+    int token;
+
+    expr=*stack;
+
+    if (!expr)
+    {
+	sprintf(error,"Called with empty postfix stack");
+	return FALSE;
+    }
+
+    token=expr->token;
+
+    if (expr->is_unary)
+    {
+    	if (token==TYPE_OPERAND)
+	{
+	    char *endp;
+
+	    *result=strtol(expr->text,&endp,0);
+
+	    if (!(expr->text[0] && *endp==0))
+	    {
+		int ok=FALSE;
+
+		if (expand)
+		    ok=expand(client,expr->text,result);
+
+		if (!ok)
+		{
+		    sprintf(error,"Undefined variable '%s'",expr->text);
+		    return FALSE;
+		}
+	    }
+
+	    expr=Pop(expr);
+	}
+	else if (token==TYPE_VARIABLE)
+	{
+	    int ok=FALSE;
+
+	    if (expand)
+	    	ok=expand(client,expr->text,result);
+
+	    if (!ok)
+	    {
+	    	sprintf(error,"Undefined variable '%s'",expr->text);
+		return FALSE;
+	    }
+
+	    expr=Pop(expr);
+	}
+	else
+	{
+	    long val;
+
+	    expr=Pop(expr);
+
+	    if (!expr || !EvalPostfix(&expr,&val))
+	    {
+		sprintf(error,"Operator '%s' expects an argument",
+				ToString(token));
+		*stack=expr;
+		return FALSE;
+	    }
+
+	    switch(token)
+	    {
+		case TYPE_NOT:
+		    *result=~val;
+		    break;
+
+		case TYPE_UNARY_PLUS:
+		    *result=+val;
+		    break;
+
+		case TYPE_UNARY_NEG:
+		    *result=-val;
+		    break;
+
+		default:
+		    sprintf(error,"Execpected unary token '%s' processed",
+		    			ToString(token));
+		    *stack=expr;
+		    return FALSE;
+		    break;
+	    }
+	}
+    }
+    else
+    {
+	long left,right;
+
+	expr=Pop(expr);
+
+	if (!expr || !EvalPostfix(&expr,&right))
+	{
+	    sprintf(error,"Operator '%s' expects two arguments",
+	    			ToString(token));
+	    *stack=expr;
+	    return FALSE;
+	}
+
+	if (!expr || !EvalPostfix(&expr,&left))
+	{
+	    sprintf(error,"Operator '%s' expects two arguments",
+	    			ToString(token));
+	    *stack=expr;
+	    return FALSE;
+	}
+
+	switch(token)
+	{
+	    case TYPE_DIVIDE:
+		*result=left/right;
+		break;
+
+	    case TYPE_MULTIPLY:
+		*result=left*right;
+		break;
+
+	    case TYPE_MODULUS:
+		*result=left%right;
+		break;
+
+	    case TYPE_ADD:
+		*result=left+right;
+		break;
+
+	    case TYPE_SUBTRACT:
+		*result=left-right;
+		break;
+
+	    case TYPE_AND:
+		*result=left&right;
+		break;
+
+	    case TYPE_OR:
+		*result=left|right;
+		break;
+
+	    case TYPE_BOOL_AND:
+		*result=left&&right;
+		break;
+
+	    case TYPE_BOOL_OR:
+		*result=left||right;
+		break;
+
+	    case TYPE_XOR:
+		*result=left^right;
+		break;
+
+	    case TYPE_SHIFTL:
+		if (right<0)
+		{
+		    sprintf(error,"Cannot shift left by a "
+		    			"negative number (%ld)",right);
+		    *stack=expr;
+		    return FALSE;
+		}
+
+		*result=left<<right;
+		break;
+
+	    case TYPE_SHIFTR:
+		if (right<0)
+		{
+		    sprintf(error,"Cannot shift right by a "
+		    			"negative number (%ld)",right);
+		    *stack=expr;
+		    return FALSE;
+		}
+
+		*result=left>>right;
+		break;
+
+	    case TYPE_EQUALITY:
+		*result=left==right;
+		break;
+
+	    case TYPE_NOTEQUAL:
+		*result=left!=right;
+		break;
+
+	    case TYPE_LT:
+		*result=left<right;
+		break;
+
+	    case TYPE_GT:
+		*result=left>right;
+		break;
+
+	    case TYPE_LTEQ:
+		*result=left<=right;
+		break;
+
+	    case TYPE_GTEQ:
+		*result=left>=right;
+		break;
+
+	    default:
+		sprintf(error,"Unexpected binary token '%s' processed",
+				ToString(token));
+		*stack=expr;
+		return FALSE;
+		break;
+	}
+    }
+
+    *stack=expr;
+
+    return TRUE;
+}
+
+
+/* ---------------------------------------- INTERFACES
+*/
+
+int ExprEval(const char *expr, long *result,
+	     int (*expand_var)(void *client_data, const char *p, long *value),
+	     void *client_data)
+{
+    Stack *output;
+    int ret;
+
+    expand=expand_var;
+    client=client_data;
+
+    output=ToPostfix(expr);
+
+    if (!output)
+	return FALSE;
+
+    ret=EvalPostfix(&output,result);
+
+    ClearStack(output);
+
+    return ret;
+}
+
+
+/* Gets a readable reason for an error from ExprEval() or ExprParse.
+*/
+const char *ExprError(void)
+{
+    return error;
+}
+
+
+/* END OF FILE */