
/*
    Expression.m

    The Expression class is implemented using a grammar generated by the Unix
    program yacc, and a lexical scanner generated by the Unix program lex.
    The only interface between these parsing modules and this class is the
    function _EXPParseExpression, which actually performs the parse.  The
    results of the parse are returned in two data structures: a parse tree
    representing the expression and a hashtable which holds that variables
    found in the expression.

    The parse tree's nodes are Term structs (declared in exprDefs.h).  There
    is a node for each piece of the expression.  For example, when the
    expression "A+5" is parsed, three nodes result.  The top node of the tree
    represents the binary operator "+".  This top node has two subnodes.  The
    first subnode represents the variable "A".  The second represents the
    integer constant "5".  Since variables can appear more than once in an
    expression, their nodes may occur more than once in the parse tree.
    
    A parse tree is evaluated by doing a depth first traversal of the tree,
    bubbling up the results of each sub-tree until the final value rises
    to the top.
*/


#import "Expression.h"
#import "exprDefs.h"
#import <stdlib.h>
#import <math.h>
#import <appkit/nextstd.h>
#import <string.h>

/* declaration of methods static to this class */
@interface Expression(ExpressionPrivate)
- (void)_updateResults;
- (EXPTermPtr)_addVarTerm:(const char *)name;
@end

@implementation Expression

/* function which can be applied to parse tree nodes with applyToTerms() */
typedef void ParseTreeFunc(void *info, Term *term);

static void freeContents(Expression *self);
static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask);
static void updateTerm(void *data, Term *t);
static float evalTerm(Term *t, int element);
static Term *termOfVar(Expression *self, const char *varName);
static NXHashTable *makeBuiltInFuncTable(NXZone *zone);
static NXHashTable *getBuiltInFuncs(void);
static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func);
static void safeFree(void **data);
static EXPTermEvalFunc sinStub, cosStub, tanStub;
static EXPTermEvalFunc asinStub, acosStub, atanStub;
static EXPTermEvalFunc expStub, logStub, log10Stub, sqrtStub;
static char *termName(const Term *t);
static void FunctionFree(const void *info, void *data);
static unsigned	VarTermHash(const void *info, const void *data);
static int VarTermCompare(const void *info, const void *data1, const void *data2);

/*
 * Shared table of built in functions.  All Expressions which haven't had
 * any application functions added to them shared this table, which contains
 * just the built in functions.
 */
static NXHashTable *BuiltInFuncTable = NULL;

/* data for a built in function */
typedef struct _BuiltInFunc {
    const char *name;		/* name of the function */
    EXPTermEvalFunc *func;	/* proc to call for evaluation */
} BuiltInFunc;

/* table of built in functions */
static const BuiltInFunc FuncList[] = {
	{"sin", &sinStub},
	{"cos", &cosStub},
	{"tan", &tanStub},
	{"asin", &asinStub},
	{"acos", &acosStub},
	{"atan", &atanStub},
	{"exp", &expStub},
	{"log", &logStub},
	{"log10", &log10Stub},
	{"sqrt", &sqrtStub}
};

#define NUM_BUILTIN_FUNCS	(sizeof(FuncList)/sizeof(BuiltInFunc))

/* prototype used to create hashtables of variable terms */
static NXHashTablePrototype VarTermProto = {&VarTermHash, &VarTermCompare, (void (*)(const void *info, void *data))&_EXPFreeTerm, 0};

- init
{
    [super init];
    resolution = 1;
    varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, [self zone]);
    return self;
}

- free
{
    freeContents(self);
  /* if we have a function table and its not the shared one */
    if (validFuncs && validFuncs != BuiltInFuncTable)
	NXFreeHashTable(validFuncs);
    return [super free];
}

- (BOOL)parse:(const char *)expressionString
{
    NXZone *zone;

    zone = [self zone];
  /* clear away any results from a previous parse */
    freeContents(self);
    varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, zone);
    resultsValid = NO;
    text = NXCopyStringBufferFromZone(expressionString, zone);
    if (!validFuncs)
	validFuncs = getBuiltInFuncs();
    return _EXPParseExpression(text, validFuncs, &parseTree, varTerms, zone);
}

- (const char *)text
{
    return text;
}

- setResolution:(int)count
{
    if (resolution != count) {
      /*
       * Changing the resolution means we have to recalculate next time
       * we're asked for results
       */
	resultsValid = NO;
	resolution = count;
    }
    return self;
}

- (int)resolution
{
    return resolution;
}

- setVar:(const char *)varName value:(float)val
{
    Term *t;

    resultsValid = NO;		/* must recalc after a var is set */
    t = termOfVar(self, varName);
    if (!t)
	t = [self _addVarTerm:varName];
  /*
   * If the term was previously a vector term, we change it to a variable
   * term (one that has a single value).
   */
    if (t->tag == vectorTerm) {
	t->tag = varTerm;
	safeFree(&(void *)t->data.vector.vals);
	t->data.var.name = t->data.vector.name;
    }
    NX_ASSERT(t->tag == varTerm, "Invalid term type in setVar:value:");
    t->data.var.val = val;
    return self;
}

- (float)varValue:(const char *)varName
{
    Term *t;

    t = termOfVar(self, varName);
    if (t) {
	if(t->tag == varTerm)
	    return t->data.var.val;
	else
	    NX_RAISE(expErrInvalidVarType, self, (void *)varName);
    } else
	NX_RAISE(expErrInvalidVarName, self, (void *)varName);
}

- setVar:(const char *)varName vector:(float *)vals numVals:(int)count
{
    Term *t;

    resultsValid = NO;
    t = termOfVar(self, varName);
    if (!t)
	t = [self _addVarTerm:varName];
  /*
   * If the term was previously a non-vector variable, we change it to a
   * vector variable term.
   */
    if (t->tag == varTerm) {
	t->tag = vectorTerm;
	t->data.vector.name = t->data.var.name;
	t->data.vector.hasRange = NO;
	t->data.vector.vals = NULL;
	t->data.vector.resolution = 0;
    }
    NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:vector:");
    safeFree(&(void *)t->data.vector.vals);
    t->data.vector.resolution = count;
    t->data.vector.vals = vals;
    t->data.vector.changed = YES;
    resolution = count;
    return self;
}

- varVector:(const char *)varName vector:(float **)vals numVals:(int *)count;
{
    Term *t;

    t = termOfVar(self, varName);
    if (t) {
	if(t->tag == vectorTerm) {
	    updateTerm(self, t);
	    *count = t->data.vector.resolution;
	    *vals = t->data.vector.vals;
	} else
	    NX_RAISE(expErrInvalidVarType, self, (void *)varName);
    } else
    	NX_RAISE(expErrInvalidVarName, self, (void *)varName);
    return self;
}

- setVar:(const char *)varName min:(float)minVal max:(float)maxVal
{
    Term *t;

    if (minVal > maxVal)
	NX_RAISE(expErrMinMax, self, NULL);
    resultsValid = NO;
    t = termOfVar(self, varName);
    if (!t)
	t = [self _addVarTerm:varName];
  /*
   * If the term was previously a non-vector variable, we change it to a
   * vector variable term.
   */
    if (t->tag == varTerm) {
	t->tag = vectorTerm;
	t->data.vector.name = t->data.var.name;
	t->data.vector.hasRange = YES;
	t->data.vector.vals = NULL;
	t->data.vector.changed = YES;
    }
    NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:min:max:");

  /*
   * We optimize and do nothing if the passed values are the same as our
   * current values.
   */
    if (t->data.vector.changed || t->data.vector.min != minVal || t->data.vector.max != maxVal) {
	safeFree(&(void *)t->data.vector.vals);
	t->data.vector.resolution = 0;
	t->data.vector.min = minVal;
	t->data.vector.max = maxVal;
	t->data.vector.changed = YES;
    }    
    return self;
}

- var:(const char *)varName min:(float *)minVal max:(float *)maxVal
{
    Term *t;

    t = termOfVar(self, varName);
    if (t) {
	if(t->tag == vectorTerm) {
	    updateTerm(self, t);
	    *minVal = t->data.vector.min;
	    *maxVal = t->data.vector.max;
	} else
	    NX_RAISE(expErrInvalidVarType, self, (void *)varName);
    } else
    	NX_RAISE(expErrInvalidVarName, self, (void *)varName);
    return self;
}

- (float)resultValue
{
    [self _updateResults];
    return *results;
}

- resultsVector:(float **)vals numVals:(int *)count
{
    [self _updateResults];
    *vals = results;
    *count = resolution;
    return self;
}

- resultsMin:(float *)minVal max:(float *)maxVal
{
    [self _updateResults];
    *minVal = resultsMin;
    *maxVal = resultsMax;
    return self;
}

/*
 * Since the varables are all in a NXHashTable, we just use the NXHashTable
 * functions to enumerate through the names of the variables.
 */

- (EXPEnumState)beginVariableEnumeration
{
    NXHashState *state;

    state = NXZoneMalloc([self zone], sizeof(NXHashState));
    *state = NXInitHashState(varTerms);
    return state;
}

- (const char *)nextVariable:(EXPEnumState)state
{
    const Term *t;

    if (NXNextHashState(varTerms, (NXHashState *)state, &(void *)t))
	return termName(t);
    else
	return NULL;
}

- (void)endVariableEnumeration:(EXPEnumState)state
{
    free(state);
}

- addFuncTerm:(const char *)name minArgs:(int)min maxArgs:(int)max
					evalFunc:(EXPTermEvalFunc *)func
{
    Function *existingType;

  /*
   * If we dont have a function table yet, get one.  If we do have one, but
   * its the shared built in table, get a new one that we can safely modify.
   */
    if (!validFuncs || validFuncs == BuiltInFuncTable)
	validFuncs = makeBuiltInFuncTable([self zone]);
    existingType = addFuncTerm(validFuncs, name, min, max, func);
    if (existingType)
	NX_RAISE(expFuncTypeInUse, self, existingType);
    return self;
}

- removeFuncTerm:(const char *)name
{
    Function *realFunc;
    Function key;

    if (validFuncs) {
      /* look up the func term by name in our table of functions */
	key.name = (char *)name;
	if (realFunc = NXHashGet(validFuncs, &key)) {
	  /*
	   * If we are using the shared table of built ins, get a new table
	   * that we can safely modify (this covers the case of someone
	   * wishing to remove a built in function, possibly to redefine it).
	   */
	    if (validFuncs == BuiltInFuncTable) {
		validFuncs = makeBuiltInFuncTable([self zone]);
		realFunc = NXHashGet(validFuncs, &key);
	    }
	    NXHashRemove(validFuncs, realFunc);
	    free(realFunc);
	    return self;
	}
    }
    return self;
}

/*
 * This is a utililty routine that recursively applies a function to all
 * terms of a parse tree. data is a blind pointer that is simply passed
 * along through the function call.  The function is only called on terms
 * whose type match the given mask.
 */
static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask)
{
    int i;
    Term **tPtr;

    for (i = t->numSubterms, tPtr = t->subterms; i--; tPtr++)
	applyToTerms(*tPtr, func, data, mask);
    if (t->tag & mask)
	(*func)(data, t);
}

/*
 * Empties the contents of the Expression.  Since the variable terms can
 * exist multiple times in the tree, we first run through the tree and
 * free all the nodes except that variable nodes.  Then we free the hash
 * table of variable terms, including the terms themselves. 
 */
static void freeContents(Expression *self)
{
    safeFree(&(void *)self->text);
  /* free the non-variable terms */
    if (self->parseTree)
	applyToTerms(self->parseTree, _EXPFreeTerm, NULL, ~(varTerm|vectorTerm));
  /* free the shared variable terms */
    NXFreeHashTable(self->varTerms);
    safeFree(&(void *)self->results);
}

/*
 * Allocates a new term of the given type, with room for subterms.  The
 * subterms themselves follow as a variable number of arguments.  The are
 * copied into the subterms list of the new term.
 */
Term *_EXPAllocTerm(NXZone *zone, TermTag tag, int numSubterms, ...)
{
    Term *t;
    int i;
    va_list args;

    t = NXZoneCalloc(zone, sizeof(Term) + (numSubterms-1) * sizeof(Term *), 1);
    t->tag = tag;
    t->numSubterms = numSubterms;
    va_start(args, numSubterms);
    for (i = 0; i < numSubterms; i++)
	t->subterms[i] = va_arg(args, Term *);
    va_end(args);
    return t;
}

/*
 * Frees a term and any associated data.  This routine can be used as the
 * free function of a NXHashTable prototype, or as a proc passed to
 * applyToTerms().
 */
void _EXPFreeTerm(const void *info, Term *data)
{
    Term *t = (Term *)data;

    if (t->tag == vectorTerm) {
	free(t->data.vector.vals);
	free(t->data.vector.name);
    } else if (t->tag == varTerm)
	free(t->data.var.name);
    free(t);
}

/*
 * Makes sure a term is up to date.  Since terms recalculate any internal
 * state lazily, this must be called before making use of a term's value.
 * We apply this function recursively to all terms before evaluating an
 * Expression, and apply to any term if we are asked to return the values
 * held within the term (for example, from -varVector:vector:numVals:).
 */
static void updateTerm(void *data, Term *t)
{
    Expression *self = data;

    if (t->tag != vectorTerm)
	return;		/* only vector terms require work to stay up to date */

  /* Ensure this term has the same resolution as the rest of the Expression. */ 
    if (self->resolution != t->data.vector.resolution) {
      /*
       * We can change its resolution if we interpolate values for this term
       * within a range.  Else if we were passed a list of values for this
       * term, its an exception if the resolution is no longer in sync.
       */
	if (t->data.vector.hasRange) {
	    safeFree(&(void *)t->data.vector.vals);
	    t->data.vector.vals = NXZoneMalloc([self zone],
					self->resolution * sizeof(float));
	    t->data.vector.resolution = self->resolution;
	    t->data.vector.changed = YES;    /* remember to re-interpolate */
	} else
	    NX_RAISE(expErrResolutionMismatch, self,
					(void *)t->data.vector.name);
    }

    if (t->data.vector.changed) {
	if (t->data.vector.hasRange) {
	  /* interpolate a list of values between min and max */
	    int i;
	    float delta;
	    float *val, *prevVal;

	    i = self->resolution - 1;
	    if (i) {
		delta = (t->data.vector.max - t->data.vector.min) / i;
		prevVal = t->data.vector.vals;
		*prevVal = t->data.vector.min;
		val = prevVal + 1;
		while (i--)
		    *val++ = *prevVal++ + delta;
		*(val-1) = t->data.vector.max;	/* to be sure we hit max */
	    } else
		*t->data.vector.vals = t->data.vector.min;
	} else {
	  /* scan the list of values passed in to find the min and max */
	    int i;
	    float newMin, newMax;
	    float *val;

	    val = t->data.vector.vals;
	    newMin = newMax = *val++;
	    for (i = t->data.vector.resolution; i--; val++) {
		if (*val > newMax)
		    newMax = *val;
		else if (*val < newMin)
		    newMin = *val;
	    }
	    t->data.vector.min = newMin;
	    t->data.vector.max = newMax;
	}
	t->data.vector.changed = NO;	/* we're now up to date */
    }
}

/*
 * Ensures that the results calculated for this Expression are up to date.
 * We first make sure all the terms in the parse tree are up to date by
 * applying updateTerm() to all of them.  We then evaluate the Expression
 * for every n times, depending on the resolution, storing all the results
 * and caclulating their min and max. 
 */
- (void)_updateResults
{
    int i;
    float *f;

    if (!resultsValid) {
	if (parseTree) {
	    applyToTerms(self->parseTree, updateTerm, self, -1);
	    safeFree(&(void *)results);
	    results = NXZoneMalloc([self zone], sizeof(float) * resolution);
	    *results = evalTerm(parseTree, 0);
	    resultsMin = *results;
	    resultsMax = *results;
	    for (i = 1, f = results + 1; i < resolution; i++, f++) {
	      /*
	       * We pass the loop count down through the evaluation recursion
	       * so vector terms can know which element of their vectors they
	       * should use for this evaluation.
	       */
		*f = evalTerm(parseTree, i);
		if (*f > resultsMax)
		    resultsMax = *f;
		else if (*f < resultsMin)
		    resultsMin = *f;
	    }
	} else
	    NX_RAISE(expErrNoText, self, NULL);
	resultsValid = YES;
    }
}

#define MAX_ARGS	50

/*
 * Evaluates a particular term.  In order to evaluate itself, any term with
 * subterms must recursively evaluate those first.
 */
static float evalTerm(Term *t, int element)
{
    float result = 0.0;		/* initted to quiet -Wall */
    float base;
    float argsBuffer[MAX_ARGS];
    float *args;
    int i;

    switch (t->tag) {
	case constantTerm:
	    NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
	    result = t->data.constant.val;
	    break;
	case varTerm:
	    NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
	    result = t->data.var.val;
	    break;
	case vectorTerm:
	    NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
	    result = t->data.vector.vals[element];
	    break;
	case binOpTerm:
	    NX_ASSERT(t->numSubterms == 2 ||
			(t->data.binOp.op == '-' && t->numSubterms == 1),
					"Wrong #subterms in evalTerm");
	    switch (t->data.binOp.op) {
		case '+':
		    result = evalTerm(t->subterms[0], element) +
				evalTerm(t->subterms[1], element);
		    break;
		case '-':
		    if (t->numSubterms == 2)
			result = evalTerm(t->subterms[0], element) -
					evalTerm(t->subterms[1], element);
		    else
			result = - evalTerm(t->subterms[0], element);
		    break;
		case '*':
		    result = evalTerm(t->subterms[0], element) *
				evalTerm(t->subterms[1], element);
		    break;
		case '/':
		    result = evalTerm(t->subterms[0], element) /
				evalTerm(t->subterms[1], element);
		    break;
		case '%':
		    result = (int)rint(evalTerm(t->subterms[0], element)) %
				(int)rint(evalTerm(t->subterms[1], element));
		    break;
		case '^':
		  /* optimize for raising to an integral power */
		    if (t->subterms[1]->tag == constantTerm &&
				t->subterms[1]->data.constant.isInt &&
				t->subterms[1]->data.constant.val >= 1) {
			result = base = evalTerm(t->subterms[0], element);
			for (i = t->subterms[1]->data.constant.val; --i; )
			    result *= base;
		    } else
			result = pow(evalTerm(t->subterms[0], element),
					evalTerm(t->subterms[1], element));
		    break;
		default:
		    NX_ASSERT(FALSE, "Unknown binary op type in evalTerm");
	    }
	    break;
	case funcTerm:
	  /*
	   * For functions, we first ensure we have a large enough buffer
	   * for the values of all the arguments.  If there are few enough
	   * arguments, we use a buffer on the stack instead of thrashing
	   * the heap.  We then buffer up all the results of evaluating
	   * the arguments, and then pass this array of argument values
	   * to the proc that we use to evaluate this type of function.
	   */
	    if (t->numSubterms > MAX_ARGS)
		args = NXZoneMalloc(NXDefaultMallocZone(),
					sizeof(float) * t->numSubterms);
	    else
		args = argsBuffer;
	    for (i = 0; i < t->numSubterms; i++)
		args[i] = evalTerm(t->subterms[i], element);
	    result = t->data.func.type->evalFunc(t->numSubterms, args);
    	    if (t->numSubterms > MAX_ARGS)
		NXZoneFree(NXDefaultMallocZone(), args);
	    break;
	default:
	    NX_ASSERT(FALSE, "Invalid term type in evalTerm");
    }
    return result;
}

/* Utility routine to look up a variable by name in the variable hashtable. */
static Term *termOfVar(Expression *self, const char *varName)
{
    Term key;

    if (self->parseTree) {
	key.tag = varTerm;
	key.data.var.name = (char *)varName;
	return NXHashGet(self->varTerms, &key);
    } else
	NX_RAISE(expErrNoText, self, NULL);
}

/* adds a variable term to the Expressions hashtable of them */
- (Term *)_addVarTerm:(const char *)name
{
    Term *newTerm;
    Term *existingTerm;

    newTerm = _EXPAllocTerm([self zone], varTerm, 0);
    newTerm->data.var.name = NXCopyStringBufferFromZone(name, [self zone]);
    existingTerm = NXHashInsertIfAbsent(varTerms, newTerm);
    NX_ASSERT(existingTerm == newTerm, "_addVarTerm: called with existing term");
    return newTerm;
}

/* frees some storage, NULL'ing out the pointer */
static void safeFree(void **data)
{
    free(*data);
    *data = NULL;
}

/* free function used in the NXHashTable prototype for functions */
static void FunctionFree(const void *info, void *data)
{
    free(((Function *)data)->name);
    free(data);
}

/*
 * Adds a func term to a HashTable of them.  Returns any existing entry
 * with the same name, else NULL.
 */
static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func)
{
    Function *newFunc;
    Function *existingType;

    newFunc = NXZoneMalloc(NXZoneFromPtr(table), sizeof(Function));
    newFunc->name = NXCopyStringBufferFromZone(name, NXZoneFromPtr(table));
    newFunc->minArgs = min;
    newFunc->maxArgs = max;
    newFunc->evalFunc = func;
    existingType = NXHashInsertIfAbsent(table, newFunc);
    if (existingType != newFunc)
	return existingType;
    else
	return NULL;
}

/*
 * Returns a global table of all built in functions.  This table is shared
 * by expressions that dont have application functions added to them.
 */
static NXHashTable *getBuiltInFuncs(void)
{
    if (!BuiltInFuncTable)
	BuiltInFuncTable = makeBuiltInFuncTable(NXDefaultMallocZone());
    return BuiltInFuncTable;
}

/* Returns a new hashtable of all built in functions. */
static NXHashTable *makeBuiltInFuncTable(NXZone *zone)
{
    NXHashTable *table;
    NXHashTablePrototype FuncTermProto;
    const BuiltInFunc *bif;
    int i;

    FuncTermProto = NXStrStructKeyPrototype;
    FuncTermProto.free = FunctionFree;
    table = NXCreateHashTableFromZone(FuncTermProto, NUM_BUILTIN_FUNCS,
								NULL, zone);
    for (i = NUM_BUILTIN_FUNCS, bif = FuncList; i--; bif++)
	(void)addFuncTerm(table, bif->name, 1, 1, bif->func);
    return table;
}

/* Returns the name of a term. */
static char *termName(const Term *t)
{
    switch (t->tag) {
	case varTerm:
	    return t->data.var.name;
	case vectorTerm:
	    return t->data.vector.name;
	default:
	    NX_ASSERT(FALSE, "Bogus term type in VarTermHash");
	    return NULL;
    }
}

/* hashing function for variable terms.  Used in hashtable prototypes. */
static unsigned	VarTermHash(const void *info, const void *data)
{
    return NXStrHash(info, termName(data));
}

/* comparison function for variable terms.  Used in hashtable prototypes. */
static int VarTermCompare(const void *info, const void *data1, const void *data2)
{
    return NXStrIsEqual(info, termName(data1), termName(data2));
}

@end

/* These procs implement the built in functions */

static float sinStub(int numArgs, float *arg)	{ return sin(*arg); }
static float cosStub(int numArgs, float *arg)	{ return cos(*arg); }
static float tanStub(int numArgs, float *arg)	{ return tan(*arg); }
static float asinStub(int numArgs, float *arg)	{ return asin(*arg); }
static float acosStub(int numArgs, float *arg)	{ return acos(*arg); }
static float atanStub(int numArgs, float *arg)	{ return atan(*arg); }
static float expStub(int numArgs, float *arg)	{ return exp(*arg); }
static float logStub(int numArgs, float *arg)	{ return log(*arg); }
static float log10Stub(int numArgs, float *arg)	{ return log10(*arg); }
static float sqrtStub(int numArgs, float *arg)	{ return sqrt(*arg); }
