/*
 * Copyright 1995,96 Thierry Bousch
 * Licensed under the Gnu Public License, Version 2
 *
 * $Id: bytecode.c,v 2.1 1996/09/15 10:20:46 bousch Exp $
 *
 * Execution of byte-code to compute new expressions, either with integers
 * (indices) or algebraic expressions.
 */

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/times.h>
#include <time.h>
#include <sys/wait.h>
#include <unistd.h>
#include "saml.h"
#include "saml-parse.h"
#include "induce.h"

#define FN_PREFIX	"fn_"
#define ARG1	 stack[hstk-1]
#define ARG2	 stack[hstk-2]
#define ARG3	 stack[hstk-3]
#define IARG1	istack[hstk-1]
#define IARG2	istack[hstk-2]
#define IARG3	istack[hstk-3]

static mref_t *stack = NULL;
static int *istack = NULL;
static int stack_size = 0, istack_size = 0;

void reset_interpreter_stack (void)
{
	int i;

	for (i = 0; i < stack_size; i++)
		mref_free(stack[i]);

	free(stack); free(istack);
	stack = NULL; istack = NULL;
	stack_size = 0; istack_size = 0;
}

static void _expand_stack_upto (int position)
{
	int i, old_size = stack_size;
	
	assert(position >= 0);
	stack_size += position + 16;
	stack = realloc(stack, stack_size * sizeof(mref_t));
	assert(stack != NULL);
	for (i = old_size; i < stack_size; i++)
		stack[i] = mref_new();
}

static void _expand_istack_upto (int position)
{
	assert(position >= 0);
	istack_size += position + 16;
	istack = realloc(istack, istack_size * sizeof(int));
	assert(istack != NULL);
}

static inline void verify_stack (int pos)
{
	if (pos >= stack_size)
		_expand_stack_upto(pos);
}

static inline void verify_istack (int pos)
{
	if (pos >= istack_size)
		_expand_istack_upto(pos);
}

static int repeat_subs (mref_t expr, mref_t e1, mref_t e2)
{
	mref_t prev = mref_new();
	int error;

	do {
		mref_copy(prev, expr);
		error = mref_subs(expr, expr, e1, e2);
	}
	while (!error && mref_differ(prev,expr));
	mref_free(prev);
	return error;
}

/* Registration and execution of external functions */

static char **functions = NULL;
static int *fn_arity = NULL;
static int nb_functions = 0, max_functions = 0;

int register_function (char *func, int arity)
{
	int i;

	for (i = 0; i < nb_functions; i++)
		if (!strcmp(func,functions[i]) && fn_arity[i] == arity)
			return i;
	if (nb_functions == max_functions) {
		max_functions = 2*max_functions + 64;
		functions = realloc(functions, max_functions*sizeof(char*));
		fn_arity = realloc(fn_arity, max_functions*sizeof(int));
		assert(functions && fn_arity);
	}
	functions[nb_functions] = func;
	fn_arity[nb_functions] = arity;
	return nb_functions++;
}

static void read_mref_from_fd (mref_t mr, FILE* fd)
{
	mref_t model = mref_new();

	mref_build(model, ST_RATIONAL, "0");
	mref_cast(model, parsed_poly_type);
	saml_init_lexer_fd(fd);
	if (saml_parse(mr, model) < 0)
		fprintf(stderr, "induce: read_mref_from_fd: syntax error\n");
	mref_free(model);
}

static void
execute_ext_func (int *ret, mref_t mr, int fn, int argc, int *e_argv)
{
	char *fname, *command, *p, **argv;
	int i, fd[2], child, c_status;
	struct tms t1, t2;
	FILE *fp;

	fname = functions[fn];
	if (!quiet)
		fprintf(stderr, "External %sfunction %s(%d) ",
		(ret ? "i-" : ""), fname, argc);
	if (pipe(fd) < 0) {
		perror("induce: pipe");
		return;
	}
	if ((child = fork()) < 0) {
		perror("induce: fork");
		return;
	} else if (child == 0) {
		/* This is the child */
		close(fd[0]);
		if (dup2(fd[1],1) < 0)
			perror("induce: dup2");
		command = alloca(strlen(FN_PREFIX)+strlen(fname)+1);
		strcpy(command, FN_PREFIX);
		strcat(command, fname);
		argv = alloca((argc+2)*sizeof(char*));
		argv[0] = command;
		for (i = 0; i < argc; i++) {
			if (ret)
			  sprintf(p=alloca(30), "%d", e_argv[i]);
			else
			  p = strdup(mref_string(e_argv[i]));
			assert(p != NULL);
			argv[i+1] = p;
		}
		argv[argc+1] = NULL;
		execvp(command, argv);
		perror("induce: execvp");
		exit(-1);
	}
	/* This is the parent */
	close(fd[1]);
	if ((fp = fdopen(fd[0], "r")) != NULL) {
		if (ret)
		  fscanf(fp, "%d", ret);	/* integer */
		else
		  read_mref_from_fd(mr, fp);	/* polynomial */
		fclose(fp);
	} else {
		/* Unlikely, but you never know */
		perror("induce: fdopen");
	}
	/* Let's wait for our child to die */
	times(&t1);
	while (waitpid(child,&c_status,0) < 0) {
		if (errno == EINTR)
			continue;
		perror("induce: waitpid");
		return;
	}
	if (!quiet) {
		times(&t2);
		fprintf(stderr, "used %.3fu+%.3fs seconds of CPU time\n",
		  (t2.tms_cutime-t1.tms_cutime)/(double)CLK_TCK,
		  (t2.tms_cstime-t1.tms_cstime)/(double)CLK_TCK);
	}
	/* Abnormal termination? */
	if (WIFSIGNALED(c_status))
		fprintf(stderr, "induce: child killed by signal %d\n",
			WTERMSIG(c_status));
	if (WIFEXITED(c_status) && WEXITSTATUS(c_status))
		fprintf(stderr, "induce: child exited with status %d\n",
			WEXITSTATUS(c_status));
}

mref_t exec_bytecode (int argc, mref_t *argv, const char *cmd)
{
	int counter=0, hstk=0, ar;
	char c;

	assert(argc >= 0 && cmd != NULL);
	while ((c = *cmd++) != '\0') {
	  switch(c) {
	    case '0': case '1': case '2': case '3': case '4':
	    case '5': case '6': case '7': case '8': case '9':
	    	/* Shift the digit into the counter */
	    	counter = 10*counter + (c - '0');
	    	break;
	    case 'p':
	    	/* Push the argument specified by the counter */
	    	assert(counter < argc && argv != NULL);
	    	verify_stack(hstk);
	    	mref_copy(stack[hstk++], argv[counter]);
	    	counter = 0;
	    	break;
	    case 'n':
	    	/* Negate topmost expression */
	    	assert(hstk >= 1);
	    	mref_negate(ARG1, ARG1);
	    	break;
	    case '!':
	    	/* Dirac function */
	    	assert(hstk >= 1);
	    	if (mref_notzero(ARG1))
	    	  mref_zero(ARG1, ARG1);
	    	else
		  mref_one(ARG1, ARG1);
	    	break;
	    case 'i':
	    	/* Invert topmost expression */
	    	assert(hstk >= 1);
	    	mref_invert(ARG1, ARG1);
	    	break;
	    case '+':
	    	/* Add the two topmost expressions */
	    	assert(hstk >= 2);
	    	mref_add(ARG2, ARG2, ARG1);
	    	--hstk;
	    	break;
	    case '-':
	    	/* Substract them */
	    	assert(hstk >= 2);
	    	mref_sub(ARG2, ARG2, ARG1);
	    	--hstk;
	    	break;
	    case '*':
		/* Multiply them */
		assert(hstk >= 2);
		mref_mul(ARG2, ARG2, ARG1);
		--hstk;
		break;
	    case '/':
	    	/* Divide them */
	    	assert(hstk >= 2);
	    	mref_div(ARG2, ARG2, ARG1);
	    	--hstk;
	    	break;
	    case '^':
	    	/* Raise to the exponent specified by the counter */
		assert(hstk >= 1);
		mref_power(ARG1, ARG1, counter);
		counter = 0;
		break;
	    case 's':
	    	/* Normal substitution */
	    	assert(hstk >= 3);
	    	mref_subs(ARG3, ARG3, ARG2, ARG1);
	    	hstk -= 2;
	    	break;
	    case 'S':
	    	/* Repeated substitution */
	    	assert(hstk >= 3);
	    	repeat_subs(ARG3, ARG2, ARG1);
	    	hstk -= 2;
	    	break;
	    case 'd':
	    	/* Differentiate */
	    	assert(hstk >= 2);
	    	mref_diff(ARG2, ARG2, ARG1);
	    	--hstk;
	    	break;
	    case 'r':
	    	/* Resultant */
	    	assert(hstk >= 3);
	    	mref_elim(ARG3, ARG3, ARG2, ARG1);
	    	hstk -= 2;
	    	break;
	    case 'f':
	    	/* Execute an external function */
	    	ar = fn_arity[counter];
	    	assert(ar <= hstk);
	    	verify_stack(hstk-ar);
	    	execute_ext_func(NULL, stack[hstk-ar], counter,
			ar, &stack[hstk-ar]);
	    	counter = 0;
		hstk -= (ar-1);
		break;
	    default:
		/* This point should never be reached */
	    	fprintf(stderr, "Unrecognized character `%c'. Abort.\n", c);
	    	abort();
	  }
	}
	/* The result should be on the stack now */
	assert(counter == 0);
	assert(hstk == 1);
	return ARG1;
}

int exec_int_bytecode (int argc, int *argv, const char *cmd)
{
	int counter=0, hstk=0, pwtemp, ar;
	char c;

	assert(argc >= 0 && cmd != NULL);
	while ((c = *cmd++) != '\0') {
	  switch(c) {
	    case '0': case '1': case '2': case '3': case '4':
	    case '5': case '6': case '7': case '8': case '9':
	    	/* Shift the digit into the counter */
	    	counter = 10*counter + (c - '0');
	    	break;
	    case 'p':
	    	/* Push the argument specified by the counter */
	    	assert(counter < argc && argv != NULL);
	    	verify_istack(hstk);
	    	istack[hstk++] = argv[counter];
	    	counter = 0;
	    	break;
	    case '.':
	    	/* Push the number in the counter */
	    	verify_istack(hstk);
	    	istack[hstk++] = counter;
	    	counter = 0;
	    	break;
	    case 'n':
	    	/* Negate topmost integer */
	    	assert(hstk >= 1);
	    	IARG1 = -IARG1;
	    	break;
	    case '!':
	    case '=':
	    	/* Dirac function */
	    	assert(hstk >= 1);
	    	IARG1 = !IARG1;
	    	break;
	    case '>':
	    	/* Test if topmost expression is >0 */
	    	assert(hstk >= 1);
	    	IARG1 = (IARG1 > 0);
	    	break;
	    case '<':
	    	/* Test if topmost expression is <0 */
	    	assert(hstk >= 1);
	    	IARG1 = (IARG1 < 0);
	    	break;
	    case '+':
	    	/* Add the two topmost integers */
	    	assert(hstk >= 2);
	    	IARG2 += IARG1;
	    	--hstk;
	    	break;
	    case '-':
	    	/* Substract them */
	    	assert(hstk >= 2);
	    	IARG2 -= IARG1;
	    	--hstk;
	    	break;
	    case '*':
	    	/* Multiply them */
	    	assert(hstk >= 2);
	    	IARG2 *= IARG1;
	    	--hstk;
	    	break;
	    case '/':
	    	/* Divide the first integer by the second one */
	    	assert(hstk >= 2);
	    	if (IARG1 < 0) {
	    		/* Doesn't change the quotient */
	    		IARG1 = -IARG1;
	    		IARG2 = -IARG2;
	    	}
	    	if (IARG1) {
	    		/* Beware, the C division truncates towards 0 */
	    		int x = IARG2 / IARG1;
	    		if (x*IARG1 > IARG2)
	    			--x;
	    		IARG2 = x;
	    	} else {
	    		/* Convention: a/0 == 0 */
	    		IARG2 = 0;
	    	}
	    	--hstk;
	    	break;
	    case '%':
	    	/* Reduce the first integer modulo the second one */
	    	assert(hstk >= 2);
	    	if (IARG1) {
	    		/* The result should have the same sign as IARG1 */
			int x = IARG2 % IARG1;
			if (x*IARG1 < 0)
				x += IARG1;
			IARG2 = x;
	    	}
	    	/* Convention: a%0 == a */
	    	--hstk;
	    	break;
	    case '^':
	    	/* Raise to the exponent specified by the counter */
	    	assert(hstk >= 1);
	    	for (pwtemp = 1; counter; counter--)
	    		pwtemp *= IARG1;
	    	IARG1 = pwtemp;
	    	break;
	    case 'f':
	    	/* Execute an external function */
	    	ar = fn_arity[counter];
	    	assert(ar <= hstk);
	    	verify_istack(hstk-ar);
	    	execute_ext_func(&istack[hstk-ar], 0, counter,
	    		ar, &istack[hstk-ar]);
	    	counter = 0;
	    	hstk -= (ar-1);
	    	break;
	    default:
	    	/* This point should never be reached */
	    	fprintf(stderr, "Unrecognized character `%c'. Abort.\n", c);
	    	abort();
	  }
	}
	/* The result should be on the stack now */
	assert(counter == 0);
	assert(hstk == 1);
	return IARG1;
}

/*
 * It is convenient to use a struct _indexed_variable to hold a list
 * of conditions. The following function checks all of them.
 */

static int check_conditions (int argc, int *argv, idx_var *cond)
{
	int i;

	if (cond == NULL)
		return 1;
	for (i = 0; i < cond->nbind; i++)
		if (!exec_int_bytecode(argc, argv, cond->ibcode[i]))
			return 0;
	/* All tests passed */
	return 1;
}

static eval_rule **rules = NULL;
static int nb_rules = 0, max_rules = 0;

void insert_rule (eval_rule* rule)
{
	if (nb_rules == max_rules) {
		max_rules = 2*max_rules + 64;
		rules = realloc(rules, max_rules*sizeof(eval_rule*));
		assert(rules != NULL);
	}
	rules[nb_rules++] = rule;
}

/* Find the first matching rule */

eval_rule* first_matching_rule (const char *name, int argc, int *argv)
{
	int i;
	eval_rule *cr;

	for (i = 0; i < nb_rules; i++) {
		cr = rules[i];
		if (cr->nbind == argc && !strcmp(cr->rootname,name) &&
			check_conditions(argc,argv,cr->conditions))
				return cr;
	}
	return NULL;
}