//============================================================================
//
//  SExpEval.cpp - Simple Expression Evaluator
//
//  Copyright (c) 2002 Epson Research and Development, Inc. 
//  All rights reserved.
//
//	The tabs in the file is formatted at 4.
//
//============================================================================

#ifdef _WIN32
#pragma warning( disable : 4100 )	// Disable "unreferenced formal parameter" warning.
#pragma warning( disable : 4514 )	// Disable "unreferenced inline function has been removed" warning (math.h generates these).
#endif


#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "SExpEval.h"
#include "helper.h"




//
// MODULE FUNCTIONS
//

static bool LookupSVar(	in const char* Name, in UInt32 NameLen, in const char* NameSpace, out UInt32& ListIndex );

static int EvalNumIf(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLogAnd(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLogOr(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLogXOr(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalBitAnd(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalBitOr(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalBitXOr(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsEqual(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsNotEqual(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsLT(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsGT(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsLTE(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalIsGTE(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLeftShift(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalRightShift(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLeftRotate(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalRightRotate(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalAdd(				in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalSubtract(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalMultiply(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalDivide(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalModulus(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalLogNot(			in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalBitComplement(	in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
static int EvalExponential(		in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );

#define	   strnewcpy(des,src)	des=new char[strlen(src)+1], strcpy(des,src)
#define    DOEXPRESSION(nth)	{ int ee = EvaluateSExpression(Expr+ExprStart[nth],ExprEnd[nth]-ExprStart[nth],&e[nth],NameSpace,ErrorMsg); if (ee) return ExprStart[nth]+ee; }
#define    ISEXPRTRUE(nth)		( e[nth].IsString ? (e[nth].StrValue[0]!='\0') : (!!e[nth].NumValue) )




//
// EXPRESSION EVALUATOR DATA
//

static ExternalVarFunc	g_cbVar = NULL;
static UInt32			g_DefaultRadix = 16;
#define					EXPR_TOKEN_LETTER	'e'
#define					MaxExprsPerTemplate	3

typedef int (*SExprFunc)( in const char* Expr, in UInt32* ExprStart, in UInt32* ExprEnd, in UInt32 nExprs, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg );
			// Returns 0 if successful, else index into Expr to show where the error occurred.

typedef struct SExprDef
{
	char		Template[10];
	SExprFunc	EvalExpr;
} SExprDef;

static SExprDef	SExpr[] =
{
	// Characters in {braces} are NOT to be matched.
	{ "e?e:e",		EvalNumIf },
	{ "e xor e",	EvalLogXOr },
	{ "e or e",		EvalLogOr },
	{ "e and e",	EvalLogAnd },
	{ "not e",		EvalLogNot },
	{ "e||e",		EvalLogOr },
	{ "e&&e",		EvalLogAnd },
	{ "e^e",		EvalBitXOr },
	{ "e|e",		EvalBitOr },
	{ "e&e",		EvalBitAnd },
	{ "e!=e",		EvalIsNotEqual },
	{ "e==e",		EvalIsEqual },
	{ "e>{=>}e",	EvalIsGT },
	{ "e<{=<}e",	EvalIsLT },
	{ "e>=e",		EvalIsGTE },
	{ "e<=e",		EvalIsLTE },
	{ "e>>{>}e",	EvalRightShift },
	{ "e<<{<}e",	EvalLeftShift },
	{ "e>>>e",		EvalRightRotate },
	{ "e<<<e",		EvalLeftRotate },
	{ "e-e",		EvalSubtract },
	{ "e+e",		EvalAdd },
	{ "e%e",		EvalModulus },
	{ "e/e",		EvalDivide },
	{ "e*{*}e",		EvalMultiply },
	{ "~e",			EvalBitComplement },
	{ "!e",			EvalLogNot },
	{ "e**e",		EvalExponential }
};
const int nSExprs = sizeof(SExpr)/sizeof(SExpr[0]);

//
// USER-DEFINED VARIABLE DATA
//

typedef struct SVarDef
{
	char*	Name;
	bool	IsString;
	UInt32	NumValue;
	char*	StrValue;
	char*	NameSpace;
} SVarDef;

#define		MaxSVars	100
UInt32		NumSVars = 0;
SVarDef		SVars[MaxSVars];




//
// MODULE CODE
//


int EvaluateSExpression( in const char* Expr, in UInt32 ExprLen, inout SValueDef* EndResult, in const char* NameSpace, out const char* *ErrorMsg )
{
	int		ExprError = 0;
	UInt32	i, iT, iE, Radix;
	UInt32	nCharsIgnored = 0;
	UInt32	TemplateLen;
	int		Depth;
	bool	WithinQuotes = false;
	bool	OuterParen;

	UInt32	TokenLen;
	bool	ToString = false;
	UInt32	ToRadix = 0;
	UInt32	ToWidth = 0;

	//
	// PREPARE EXPRESSION FOR PARSING
	//

	// Strip pre/post spacing
	for ( ; (Expr[0]==' '||Expr[0]=='\t'); Expr++,ExprLen-- );
	for ( ; (Expr[ExprLen-1]==' '||Expr[ExprLen-1]=='\t'); ExprLen-- );

	// Verify balance of parenthesis, and strip off outer parenthesis, ie. only (a+b) or (a+(b+c)), but not (a+b)+(c+d).
	OuterParen = ( Expr[0] == '(' );
	for ( iE=Depth=0; iE<ExprLen; iE++ )
	{
		switch ( Expr[iE] )
		{
			case '\"':	if (!iE||Expr[iE-1]!='\\') WithinQuotes=!WithinQuotes;	break;
			case '(':	if (!WithinQuotes) Depth++;								break;
			case ')':	if (!WithinQuotes) Depth--;								break;
		}
		if ( Depth==0 && iE!=ExprLen-1 )
			OuterParen = false;
	}
	if ( Depth != 0 )
	{
		if ( ErrorMsg )
			*ErrorMsg = "Parenthesis mismatch.";
		return 1;
	}
	if ( OuterParen )
	{
		// Made it through without encountering an area not enclosed in the outer paren, so exclude it from here.
		Expr++;
		nCharsIgnored = 1;
		ExprLen -= 2;

		// Re-Strip pre/post spacing
		for ( ; (Expr[0]==' '||Expr[0]=='\t'); Expr++,ExprLen-- );
		for ( ; (Expr[ExprLen-1]==' '||Expr[ExprLen-1]=='\t'); ExprLen-- );

	}

	//
	// ENUMERATE THRU ALL TEMPLATE EXPRESSIONS
	//

	for ( i=0; i<nSExprs; i++ )
	{
		UInt32	eStart[MaxExprsPerTemplate];
		UInt32	eEnd[MaxExprsPerTemplate];
		UInt32	nExprsFound = 0;
		bool	MatchSoFar = true;

		TemplateLen = strlen( SExpr[i].Template );

		// Is this template expression anywhere in Expr?
		iT = iE = 0;
		while ( MatchSoFar && iT<TemplateLen && iE<ExprLen )
		{
			bool   ExprExpected = false;
			UInt32 iOpEnd;

			// Does an expression preceed the next operator?
			if ( SExpr[i].Template[iT] == EXPR_TOKEN_LETTER )
			{
				ExprExpected = true;
				eStart[nExprsFound] = iE;
				iT++;
			}

			// Determine all operator characters to match.
			for ( iOpEnd=iT; iOpEnd<TemplateLen; iOpEnd++ )
				if ( SExpr[i].Template[iOpEnd] == EXPR_TOKEN_LETTER )
					break;

			if ( iOpEnd == iT )
			{
				// There are no more operators to match.
				iE = eEnd[nExprsFound] = ExprLen;
			}
			else
			{
				// An operator match is required, so find it.
				bool InQuote = false;
				int	 ScopeDepth = 0;
				MatchSoFar = false;
				for ( eEnd[nExprsFound]=iE; eEnd[nExprsFound]<ExprLen && !MatchSoFar; eEnd[nExprsFound]++ )
				{
					switch ( Expr[eEnd[nExprsFound]] )
					{
					  case '\"':
						if ( Expr[eEnd[nExprsFound]-1] != '\\' )
							InQuote = !InQuote;
						break;
					  case '(':
					  case '[':
						if ( !InQuote )
							ScopeDepth++;
						break;
					  case ')':
					  case ']':
						if ( !InQuote )
							ScopeDepth--;
						break;
					  default:
						if ( !InQuote && !ScopeDepth )
						{
							// Check to see if the next one or few characters match the operators in the template.
							const char* Operators	= SExpr[i].Template + iT;
							int			iOperators	= 0;
							int			nOperators	= iOpEnd - iT;
							const char* StrToMatch	= Expr + eEnd[nExprsFound];
							int			iStrToMatch	= 0;

							MatchSoFar = true;
							while ( MatchSoFar && iOperators<nOperators )
							{
								if ( Operators[iOperators] == '{' )
								{
									// Do NOT match with these characters.
									while ( Operators[++iOperators] != '}' )
									{
										if ( tolower(StrToMatch[iStrToMatch]) == Operators[iOperators] )
										{
											// Found an illegal match, so skip this group entirely.
											eEnd[nExprsFound] = ExprLen;
											MatchSoFar = false;
											break;
										}
									}
								}
								else if ( tolower(StrToMatch[iStrToMatch]) == Operators[iOperators] )
									iStrToMatch++;
								else
									MatchSoFar = false;
								iOperators++;
							}
							if ( MatchSoFar )
							{
								iE = eEnd[nExprsFound] + iStrToMatch;
								iT += nOperators;
								eEnd[nExprsFound]--;
							}
						}
						break;
					}
				}
			}

			if ( ExprExpected && MatchSoFar )
			{
				if ( eStart[nExprsFound] == eEnd[nExprsFound] )
				{
					if ( ErrorMsg )
						*ErrorMsg = "Expected an expression here.";
					return eStart[nExprsFound] + nCharsIgnored + 1;
				}
				nExprsFound++;
			}
		}

		if ( MatchSoFar )
		{
			// Apply the template.
			ExprError = SExpr[i].EvalExpr( Expr, eStart, eEnd, nExprsFound, EndResult, NameSpace, ErrorMsg );
			return ExprError ? ExprError+nCharsIgnored : 0;
		}
	}

	//
	// MUST BE A TOKEN
	//

	// Skip leading and post-fixed spaces.
	while ( Expr[0]==' ' || Expr[0]=='\t' ) Expr++, nCharsIgnored++, ExprLen--;
	while ( (Expr[ExprLen-1]==' ' || Expr[ExprLen-1]=='\t') && ExprLen>0 ) ExprLen--;

	// Is there a format conversion suffix? (token.nh10, etc)
	for ( TokenLen=Depth=0; TokenLen<ExprLen; TokenLen++ )
	{
		if ( Expr[TokenLen] == '\"' )
			Depth = 1 - Depth;
		else if ( !Depth && Expr[TokenLen]=='.' )
			break;
	}
	if ( TokenLen < ExprLen )
	{
		i = TokenLen + 1;
		switch ( Expr[i] )
		{
			case 's':  case 'S':  ToString=true;										break;
			case 'n':  case 'N':  ToString=false;										break;
			default:   if (ErrorMsg) *ErrorMsg="Unknown format specifier.";	return i+1;
		}
		if ( Expr[++i] )
		{
			switch ( Expr[i] )
			{
				case 'h':  case 'H':  ToRadix=16;  i++;  break;
				case 't':  case 'T':  ToRadix=10;  i++;  break;
				case 'o':  case 'O':  ToRadix=8;   i++;  break;
				case 'i':  case 'I':  ToRadix=2;   i++;  break;
			}
			if ( Expr[i]>='0' && Expr[i]<='9' )
				ToWidth = atoi32( Expr+i, 10 );
		}
	}

	// Since all expression failed to match, then this must be a value.
	if ( Expr[0] == '\"' )
	{
		// STRING VALUE
		EndResult->IsString = true;
		if ( Expr[TokenLen-1] != '\"' )
		{
			if ( ErrorMsg )
				*ErrorMsg = "Invalid string value.";
			return nCharsIgnored + 1;
		}
		UInt32 StrLen = min( TokenLen-2, MaxStringValueSize-1 );
		strncpy( EndResult->StrValue, Expr+1, StrLen );
		EndResult->StrValue[StrLen] = '\0';
	}
	else if ( isnumber(Expr,TokenLen,g_DefaultRadix,&Radix) )
	{
		// NUMERICAL VALUE
		EndResult->IsString = false;
		EndResult->NumValue = atoi32( Expr, Radix );
	}
	else if ( Expr[0] == '$' )
	{
		// USER VARIABLES
		if ( !GetSVar(Expr,TokenLen,EndResult,NameSpace) )
		{
			if ( ErrorMsg )
				*ErrorMsg = "Unknown token or expression.";
			return nCharsIgnored + 1;
		}
	}
	else
	{
		// VARIABLES OR ARRAYS
		if ( g_cbVar )
		{
			EndResult->IsString = ( ToString && !ToRadix );
			ExprError = g_cbVar( Expr, TokenLen, EndResult, ErrorMsg );
			if ( ExprError )
				return ExprError + nCharsIgnored;
		}
		else
		{
			if ( ErrorMsg )
				*ErrorMsg = "Unknown token or expression.";
			return nCharsIgnored + 1;
		}
	}

	if ( TokenLen < ExprLen )
	{
		if ( !EndResult->IsString && !ToString )
		{
			if ( ErrorMsg )
				*ErrorMsg = "Cannot convert a numerical value to a numerical value.";
			return TokenLen + 2;
		}
		if ( ToRadix == 0 )
			ToRadix = g_DefaultRadix;
		if ( EndResult->IsString && ToString )
		{
			if ( ToWidth == 0 )
				return 0;
			EndResult->StrValue[ToWidth] = '\0';
			for ( i=strlen(EndResult->StrValue); i<ToWidth; i++ )
				EndResult->StrValue[i] = ' ';
		}
		else if ( ToString )
			strcpynum( EndResult->StrValue, EndResult->NumValue, ToRadix, ToWidth );
		else
			EndResult->NumValue = aton32( EndResult->StrValue, ToWidth, ToRadix );
		EndResult->IsString = ToString;
	}

	return 0;
}




void SetSExpressionDefaultRadix( in UInt32 DefaultRadix )
{
	g_DefaultRadix = DefaultRadix;
}




bool SetSVar( in const char* Name, in UInt32 NameLen, in SValueDef* Value, in const char* NameSpace )
{
	UInt32 i;

	// Look up to see if variable already exists.
	if ( LookupSVar(Name,NameLen,NameSpace,i) )
	{
		// Existing variable found.
		if ( SVars[i].StrValue )
			delete [] SVars[i].StrValue;
		SVars[i].StrValue = NULL;
	}
	else
	{
		// Doesn't currently exist, create a new one.
		if ( NumSVars+1 > MaxSVars )
			return false; // No room!
		strnewcpy( SVars[i].Name, Name );
		SVars[i].Name[NameLen] = '\0';
		NumSVars++;
	}
	SVars[i].IsString = Value->IsString;
	SVars[i].NumValue = Value->NumValue;
	if ( Value->IsString )
		strnewcpy( SVars[i].StrValue, Value->StrValue );
	if ( NameSpace )