expr.c

//SPDX-License-Identifier: GPL-2.0-or-later
/*

   Copyright (C) 2007-2022 Cyril Hrubis <metan@ucw.cz>

 */

#define _GNU_SOURCE

#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#include "expr.h"

#define ERR(err, err_msg, err_pos) do {\
	if ((err) != NULL) {           \
		(err)->err = err_msg;  \
		(err)->pos = err_pos;  \
	}                              \
} while (0)

enum expr_elem_type {
	EXPR_END = 0,
	EXPR_NUM,
	EXPR_NEG,
	EXPR_MUL,
	EXPR_DIV,
	EXPR_ADD,
	EXPR_SUB,
	EXPR_POW,
	EXPR_VAR,
	EXPR_FN1,
	EXPR_FN2,
	EXPR_LPAR,
	EXPR_RPAR,
	EXPR_SEP,
	EXPR_START,
};

struct fn {
	const char *name;
	struct expr_fn fn;
};

static struct fn fn1[] = {
	{"abs",    {.fn1 = fabs}},

	{"exp",    {.fn1 = exp}},
	{"exp2",   {.fn1 = exp2}},
	{"exp10",  {.fn1 = exp10}},
	{"ln",     {.fn1 = log}},
	{"log",    {.fn1 = log10}},
	{"log2",   {.fn1 = log2}},
	{"log10",  {.fn1 = log10}},

	{"sqrt",   {.fn1 = sqrt}},
	{"cbrt",   {.fn1 = cbrt}},

	{"sin",    {.fn1 = sin, .a1_in = 1}},
	{"cos",    {.fn1 = cos, .a1_in = 1}},
	{"tan",    {.fn1 = tan, .a1_in = 1}},
	{"asin",   {.fn1 = asin, .a_out = 1}},
	{"acos",   {.fn1 = acos, .a_out = 1}},
	{"atan",   {.fn1 = atan, .a_out = 1}},

	{"sinh",   {.fn1 = sinh}},
	{"cosh",   {.fn1 = cosh}},
	{"tanh",   {.fn1 = tanh}},
	{"asinh",  {.fn1 = asinh}},
	{"acosh",  {.fn1 = acosh}},
	{"atanh",  {.fn1 = atanh}},

	{"erf",    {.fn1 = erf}},
	{"erfc",   {.fn1 = erf}},
	{"lgamma", {.fn1 = lgamma}},
	{"tgamma", {.fn1 = tgamma}},

	{"ceil",   {.fn1 = ceil}},
	{"floor",  {.fn1 = floor}},
	{"trunc",  {.fn1 = trunc}},
	{"round",  {.fn1 = round}},

	{.name = NULL},
};



static struct fn fn2[] = {
	{"mod",   {.fn2 = fmod}},
	{"rem",   {.fn2 = remainder}},
	{"max",   {.fn2 = fmax}},
	{"min",   {.fn2 = fmin}},

	{"hypot", {.fn2 = hypot}},
	{"pow",   {.fn2 = pow}},

	{"atan2", {.fn2 = atan2, .a_out = 1}},

	{.name = NULL},
};


static const double *var_by_name(const struct expr_var vars[], const char *name)
{
	unsigned int i;

	if (!vars)
		return NULL;

	for (i = 0; vars[i].name; i++) {
		if (!strcmp(vars[i].name, name))
			return &(vars[i].val);
	}

	return NULL;
}

static const char *var_by_ptr(const struct expr_var vars[], const void *ptr)
{
	unsigned int i;

	for (i = 0; vars[i].name; i++) {
		if (ptr == &(vars[i].val))
			return vars[i].name;
	}

	return NULL;
}

static struct expr_fn *fn_by_name(struct fn fns[], const char *name)
{
	unsigned int i;

	for (i = 0; fns[i].name; i++) {
		if (!strcmp(fns[i].name, name))
			return &fns[i].fn;
	}

	return NULL;
}

static const char *fn_by_ptr(struct fn fns[], const void *ptr)
{
	unsigned int i;

	for (i = 0; fns[i].name; i++) {
		if (fns[i].fn.ptr == ptr)
			return fns[i].name;
	}

	return NULL;
}

static int parse_num(const char *in, unsigned int *i, double *res,
                     struct expr_err *err)
{
	char *end;

	errno = 0;

	*res = strtod(in + *i, &end);

	/* no conversion done */
	if (end == in + *i) {
		ERR(err, "Invalid number", *i);
		return 1;
	}

	/* out of range */
	if (errno) {
		ERR(err, "Number out of range", *i);
		return 1;
	}

	*i += end - (in + *i);

	return 0;
}

static int parse_ident(const char *in, unsigned int *i,
                       char res[], unsigned int res_size,
		       struct expr_err *err)
{
	unsigned int j = 0;

	for (;;) {
		switch (in[*i]) {
		case 'a' ... 'z':
		case 'A' ... 'Z':
		case '0' ... '9':
		case '_':
			/* res too small */
			if (j == res_size - 1) {
				ERR(err, "Identifier too long", *i);
				return 1;
			}

			res[j++] = in[(*i)++];
		break;
		default:
			res[j] = 0;
			return 0;
		}
	}
}

/*
 * Right parenthesis.
 */
int stack_rpar(struct expr_elem op_stack[], unsigned int *op_i,
               struct expr_elem out[], unsigned int *out_i,
	       unsigned int i, struct expr_err *err)
{
	for (;;) {
		if (*op_i == 0) {
			ERR(err, "Unmatched parenthesis", i);
			return 1;
		}

		(*op_i)--;

		switch (op_stack[*op_i].type) {
		case EXPR_LPAR:
			if (*op_i > 0) {
				switch (op_stack[*op_i - 1].type) {
				case EXPR_FN1:
				case EXPR_FN2:
					if (op_stack[*op_i].f != op_stack[*op_i - 1].type - EXPR_FN1) {
						ERR(err, "Wrong number of parameters", i);
						return 1;
					}

					out[(*out_i)++] = op_stack[--(*op_i)];
				break;
				default:
				break;
				}
			}
			return 0;
		break;
		default:
			out[(*out_i)++] = op_stack[*op_i];
		}
	}
}

/*
 * Stack comma.
 */
int stack_comma(struct expr_elem op_stack[], unsigned int *op_i,
                struct expr_elem out[], unsigned int *out_i,
		unsigned int i, struct expr_err *err)
{
	for (;;) {
		if (*op_i == 0) {
			ERR(err, "Comma not as parameter separator", i);
			return 1;
		}

		(*op_i)--;

		switch (op_stack[*op_i].type) {
		case EXPR_LPAR:
			op_stack[*op_i].f++;

			if (*op_i == 0 || !(op_stack[*op_i - 1].type == EXPR_FN1 ||
			                    op_stack[*op_i - 1].type == EXPR_FN2)) {
				ERR(err, "Comma not as parameter separator", i);
				return 1;
			}

			(*op_i)++;
			return 0;
		break;
		default:
			out[(*out_i)++] = op_stack[*op_i];
		}
	}
}

/*
 * Operation +, -, *, /
 */
void stack_op(struct expr_elem op_stack[], unsigned int *op_i,
              struct expr_elem out[], unsigned int *out_i,
	      unsigned int op)
{
	while (*op_i > 0) {
		if (op_stack[*op_i - 1].type <= op)
			out[(*out_i)++] = op_stack[--(*op_i)];
		else
			break;
	}

	op_stack[(*op_i)++].type = op;
}

/*
 * Pops rest of the stack at the end.
 */
int op_pop(struct expr_elem op_stack[], unsigned int *op_i,
           struct expr_elem out[], unsigned int *out_i,
	   unsigned int i, struct expr_err *err)
{
	while ((*op_i)-- > 0) {
		switch (op_stack[*op_i].type) {
		case EXPR_LPAR:
		case EXPR_RPAR:
			ERR(err, "Unmatched parenthesis", i);
			return 1;
		break;
		default:
			out[(*out_i)++] = op_stack[*op_i];
		}
	}

	return 0;
}

static int is_op(unsigned int op)
{
	switch (op) {
	case EXPR_SUB:
	case EXPR_ADD:
	case EXPR_MUL:
	case EXPR_POW:
	case EXPR_DIV:
	case EXPR_START:
		return 1;
	default:
		return 0;
	}
}

static int check_number(unsigned int type)
{
	switch (type) {
	case EXPR_START:
	case EXPR_LPAR:
	case EXPR_SUB:
	case EXPR_ADD:
	case EXPR_MUL:
	case EXPR_POW:
	case EXPR_DIV:
	case EXPR_SEP:
		return 0;
	default:
		return 1;
	}
}

static int is_num(const char c)
{
	switch (c) {
	case '.':
	case '0' ... '9':
		return 1;
	default:
		return 0;
	}
}

static unsigned int max_stack(struct expr *self)
{
	unsigned int stack = 0;
	unsigned int max = 0;
	unsigned int i;

	for (i = 0; self->elems[i].type != EXPR_END; i++) {
		switch (self->elems[i].type) {
		case EXPR_NUM:
		case EXPR_VAR:
			stack++;
		break;
		case EXPR_ADD:
		case EXPR_SUB:
		case EXPR_MUL:
		case EXPR_POW:
		case EXPR_DIV:
		case EXPR_FN2:
			stack--;
		break;
		case EXPR_NEG:
		case EXPR_FN1:
		default:
		break;
		}

		max = max < stack ? stack : max;
	}

	return max;
}

/*
 * Returns one more for every unary plus, but who cares.
 */
static unsigned int count_elems(const char *str, struct expr_err *err)
{
	unsigned int i = 0;
	unsigned int count = 0;
	char buf[42];
	double f;

	for (;;) {
		switch (str[i]) {
		case 'a' ... 'z':
		case 'A' ... 'A':
			if (parse_ident(str, &i, buf, sizeof(buf), err))
				return 0;
			count++;
		break;

		case '.':
		case '0' ... '9':
			if (parse_num(str, &i, &f, err))
				return 0;
			count++;
		break;

		case '+':
		case '-':
		case '/':
		case '*':
		case '^':
			count++;
			i++;
		break;

		case '(':
		case ')':
		case ',':
		case '\t':
		case ' ':
		default:
			i++;
		break;

		case '\0':
			return count;
		}
	}
}

/*
 * Shunting yard + correctness checking.
 */
struct expr *expr_create(const char *str,
                         const struct expr_var vars[],
                         struct expr_err *err)
{
	unsigned int i = 0, s;
	char buf[42];
	const void *ptr;
	double f;

	unsigned int elem_cnt = count_elems(str, err);

	struct expr *eval = malloc(sizeof(struct expr) +
	                           elem_cnt * sizeof(struct expr_elem));

	if (!eval) {
		ERR(err, "Malloc failed", 0);
		return NULL;
	}

	struct expr_elem op_stack[strlen(str)];
	unsigned int op_i = 0;

	unsigned int j = 0;
	unsigned int prev_type = EXPR_START;


	struct expr_elem *elems = eval->elems;

	for (;;) {
		switch (str[i]) {

		/* parse identifiers */
		case 'a' ... 'z':
		case 'A' ... 'Z':
			s = i;

			if (parse_ident(str, &i, buf, sizeof(buf), err))
				return NULL;

			if (str[i] == '(' && (ptr = fn_by_name(fn1, buf))) {
				//printf("function(1): '%s'\n", buf);
				op_stack[op_i].type = EXPR_FN1;
				op_stack[op_i].fn = ptr;
				op_i++;

				prev_type = EXPR_FN1;

				continue;
			}

			if (str[i] == '(' && (ptr = fn_by_name(fn2, buf))) {
				//printf("function(2): '%s'\n", buf);
				op_stack[op_i].type = EXPR_FN2;
				op_stack[op_i].fn = ptr;
				op_i++;

				prev_type = EXPR_FN2;

				continue;
			}

			if ((ptr = var_by_name(vars, buf))) {
				elems[j].type = EXPR_VAR;
				elems[j].var = ptr;
				j++;

				if (check_number(prev_type)) {
					ERR(err, "Operator expected", s);
					goto err;
				}

				prev_type = EXPR_VAR;

				continue;
			}

			ERR(err, "Invalid identifier", s);
			goto err;
		break;

		/* parse numbers */
		case '.':
		case '0' ... '9':
		number:
			if (parse_num(str, &i, &f, err))
				goto err;

			//printf("number: %f\n", f);

			if (check_number(prev_type)) {
				ERR(err, "Operator expected", i);
				goto err;
			}

			elems[j].type  = EXPR_NUM;
			elems[j].f = f;
			j++;

			prev_type = EXPR_VAR;
		break;
		/* parse operators */
		case '+':
			if (!check_number(prev_type)) {
				if (is_num(str[i+1]))
					goto number;
				else {
					i++;
					continue;
				}
			}

			if (is_op(prev_type)) {
				ERR(err, "Unxpected opeartor", i);
				goto err;
			}

			stack_op(op_stack, &op_i, elems, &j, EXPR_ADD);

			i++;

			prev_type = EXPR_ADD;
		break;
		case '-':
			if (!check_number(prev_type)) {
				if (is_num(str[i+1]))
					goto number;
				else {
					stack_op(op_stack, &op_i, elems, &j, EXPR_NEG);
					i++;
					continue;
				}
			}

			if (is_op(prev_type)) {
				ERR(err, "Unxpected opeartor", i);
				goto err;
			}

			stack_op(op_stack, &op_i, elems, &j, EXPR_SUB);

			i++;

			prev_type = EXPR_SUB;
		break;
		case '/':
			if (is_op(prev_type)) {
				ERR(err, "Unxpected opeartor", i);
				goto err;
			}

			stack_op(op_stack, &op_i, elems, &j, EXPR_DIV);

			i++;

			prev_type = EXPR_DIV;
		break;
		case '*':
			if (is_op(prev_type)) {
				ERR(err, "Unxpected opeartor", i);
				goto err;
			}

			stack_op(op_stack, &op_i, elems, &j, EXPR_MUL);

			i++;

			prev_type = EXPR_MUL;
		break;
		case '^':
			if (is_op(prev_type)) {
				ERR(err, "Unxpected opeartor", i);
				goto err;
			}

			stack_op(op_stack, &op_i, elems, &j, EXPR_POW);

			i++;

			prev_type = EXPR_POW;
		break;
		case '(':
			if (prev_type == EXPR_NUM || prev_type == EXPR_VAR) {
				ERR(err, "Expected operator or function", i);
				goto err;
			}

			op_stack[op_i].type  = EXPR_LPAR;
			op_stack[op_i].f = 0;
			op_i++;

			i++;

			prev_type = EXPR_LPAR;
		break;
		case ')':
			if (is_op(prev_type)) {
				ERR(err, "Expected number, variable or left parenthesis", i);
				goto err;
			}

			if (prev_type == EXPR_LPAR) {
				ERR(err, "Empty parenthesis", i);
				goto err;
			}

			if (prev_type == EXPR_SEP) {
				ERR(err, "Empty parenthesis", i);
				goto err;
			}

			if (stack_rpar(op_stack, &op_i, elems, &j, i, err))
				goto err;

			i++;

			prev_type = EXPR_RPAR;
		break;
		/* argument separator */
		case ',':
			//printf("sep: ,\n");

			if (stack_comma(op_stack, &op_i, elems, &j, i, err))
				goto err;

			i++;

			prev_type = EXPR_SEP;
		break;

		/* ignore whitespaces */
		case '\t':
		case ' ':
			i++;
		break;

		case '\0':
			switch (prev_type) {
			case EXPR_RPAR:
			case EXPR_NUM:
			case EXPR_VAR:
			break;
			default:
				ERR(err, "Unexpected end", i);
				goto err;
			}

			if (op_pop(op_stack, &op_i, elems, &j, i, err))
				goto err;

			elems[j].type = EXPR_END;
			eval->vars = vars;
			eval->stack = max_stack(eval);
			return eval;

		default:
			ERR(err, "Unexpected character", i);
				goto err;
		}
	}

err:
	free(eval);
	return NULL;
}

void expr_destroy(struct expr *self)
{
	free(self);
}

void expr_dump(struct expr *self)
{
	unsigned int i;

	printf("Variables\n"
	       "---------\n");

	for (i = 0; self->vars[i].name != NULL; i++)
		printf("%s = %f\n", self->vars[i].name, self->vars[i].val);

	printf("\nMax Stack = %u\n", self->stack);

	printf("\nFormule\n"
	       "-------\n");


	for (i = 0; self->elems[i].type != EXPR_END; i++) {
		switch (self->elems[i].type) {
		case EXPR_NUM:
			printf("%f", self->elems[i].f);
		break;
		case EXPR_NEG:
			printf("-(1)");
		break;
		case EXPR_ADD:
			printf("+(2)");
		break;
		case EXPR_SUB:
			printf("-(2)");
		break;
		case EXPR_MUL:
			printf("*(2)");
		break;
		case EXPR_POW:
			printf("^(2)");
		break;
		case EXPR_DIV:
			printf("/(2)");
		break;
		case EXPR_VAR:
			printf("%s", var_by_ptr(self->vars,
			                        self->elems[i].var));
		break;
		case EXPR_FN1:
			printf("%s(1)", fn_by_ptr(fn1, self->elems[i].fn->fn1));
		break;
		case EXPR_FN2:
			printf("%s(2)", fn_by_ptr(fn2, self->elems[i].fn->fn2));
		break;
		default:
			printf("invalid type %i", self->elems[i].type);
		}

		printf(" ");
	}

	printf("\n");
}

static double angle_conv(double angle, struct expr_ctx *ctx)
{
	switch (ctx->angle_unit) {
	case EXPR_DEGREES:
		return angle * M_PI / 180;
	break;
	case EXPR_RADIANS:
		return angle;
	break;
	case EXPR_GRADIANS:
		return angle * M_PI / 200;
	break;
	}

	return 0;
}

static double eval_fn1(struct expr_elem *fn1, double par, struct expr_ctx *ctx)
{
	if (fn1->fn->a1_in)
		par = angle_conv(par, ctx);

	par = fn1->fn->fn1(par);

	if (fn1->fn->a_out)
		par = angle_conv(par, ctx);

	return par;
}

double expr_eval(struct expr *self, struct expr_ctx *ctx)
{
	double buf[self->stack];
	unsigned int i, s = 0;

	for (i = 0; self->elems[i].type != EXPR_END; i++) {
		switch (self->elems[i].type) {
		case EXPR_NUM:
			buf[s++] = self->elems[i].f;
		break;
		case EXPR_NEG:
			buf[s - 1] = -buf[s - 1];
		break;
		case EXPR_ADD:
			buf[s - 2] += buf[s - 1];
			s--;
		break;
		case EXPR_SUB:
			buf[s - 2] -= buf[s - 1];
			s--;
		break;
		case EXPR_MUL:
			buf[s - 2] *= buf[s - 1];
			s--;
		break;
		case EXPR_DIV:
			buf[s - 2] /= buf[s - 1];
			s--;
		break;
		case EXPR_POW:
			buf[s - 2] = pow(buf[s - 2], buf[s - 1]);
			s--;
		break;
		case EXPR_VAR:
			buf[s++] = *(self->elems[i].var);
		break;
		case EXPR_FN1:
			buf[s - 1] = eval_fn1(&self->elems[i], buf[s - 1], ctx);
		break;
		case EXPR_FN2:
			buf[s - 2] = self->elems[i].fn->fn2(buf[s - 2], buf[s - 1]);
			s--;
		break;
		}
	}

	return buf[0];
}