#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "pl.h"

/*
grammar:

Start = Expr ';'
Expr  = Or | Or '?' Expr ':' Expr
Or    = And | Or '||' And
And   = Rel | And '&&' Rel
Rel   = Add | Add '==' Add | Add '!=' Add | Add '<=' Add | Add '>=' Add | Add '<' Add | Add '>' Add
Add   = Mul | Add '+' Mul | Add '-' Mul
Mul   = Term | Mul '*' Term | Mul '/' decimal | Mul '%' decimal
Term  = '(' Expr ')' | '!' Term | decimal | 'n'

compared to gnu gettext:
	right side of / and % must be const (and non-zero),
	chained relational/eq operators are not allowed,
	decimal is at most 255

internals:

parser is recursive descent, terminals are pushed on a stack
that grows down, a binary op "Left op Right" is parsed into
"op length-of-Right Right Left" so eval is easy to implement.

op chars on the stack
	n c ! | & = < > + - * / % ?
are
	var, const, neg, or, and, eq, less, greater, add, sub, mul, div, mod, cond

parse* functions push the parsed rule on the stack and return
a pointer to the next non-space char
*/

#include <stdio.h>

struct st {
	unsigned char *p;
	unsigned char *e;
};

static int ok(struct st *st)
{
	return st->p != st->e;
}

static void fail(struct st *st)
{
	st->p = st->e;
}

static void push(struct st *st, int c)
{
	if (ok(st))
		*--st->p = c;
}

static const char *skipspace(const char *s)
{
	while (isspace(*s)) s++;
	return s;
}

static const char *parseconst(struct st *st, const char *s)
{
	char *e;
	unsigned long n;
	n = strtoul(s, &e, 10);
	if (!isdigit(*s) || e == s || n > 255)
		fail(st);
	push(st, n);
	push(st, 'c');
	return skipspace(e);
}

static const char *parseexpr(struct st *st, const char *s, int d);

static const char *parseterm(struct st *st, const char *s, int d)
{
	if (d <= 0) {
		fail(st);
		return s;
	}
	s = skipspace(s);
	if (*s == '!') {
		s = parseterm(st, s+1, d-1);
		push(st, '!');
		return s;
	}
	if (*s == '(') {
		s = parseexpr(st, s+1, d-1);
		if (*s != ')') {
			fail(st);
			return s;
		}
		return skipspace(s+1);
	}
	if (*s == 'n') {
		push(st, 'n');
		return skipspace(s+1);
	}
	return parseconst(st, s);
}

static const char *parsemul(struct st *st, const char *s, int d)
{
	unsigned char *p;
	int op;
	s = parseterm(st, s, d-1);
	for (;;) {
		op = *s;
		p = st->p;
		if (op == '*') {
			s = parseterm(st, s+1, d-1);
		} else  if (op == '/' || op == '%') {
			s = skipspace(s+1);
			if (*s == '0') {
				fail(st);
				return s;
			}
			s = parseconst(st, s);
		} else
			return s;
		push(st, p - st->p);
		push(st, op);
	}
}

static const char *parseadd(struct st *st, const char *s, int d)
{
	unsigned char *p;
	int op;
	s = parsemul(st, s, d-1);
	for (;;) {
		op = *s;
		if (op != '+' && op != '-')
			return s;
		p = st->p;
		s = parsemul(st, s+1, d-1);
		push(st, p - st->p);
		push(st, op);
	}
}

static const char *parserel(struct st *st, const char *s, int d)
{
	unsigned char *p;
	int neg = 0, op;
	s = parseadd(st, s, d-1);
	if (s[0] == '=' && s[1] == '=') {
		op = '=';
		s++;
	} else if (s[0] == '!' && s[1] == '=') {
		op = '=';
		neg = 1;
		s++;
	} else if (s[0] == '<' && s[1] == '=') {
		op = '>';
		neg = 1;
		s++;
	} else if (s[0] == '<') {
		op = '<';
	} else if (s[0] == '>' && s[1] == '=') {
		op = '<';
		neg = 1;
		s++;
	} else if (s[0] == '>') {
		op = '>';
	} else
		return s;
	p = st->p;
	s = parseadd(st, s+1, d-1);
	push(st, p - st->p);
	push(st, op);
	if (neg)
		push(st, '!');
	return s;
}

static const char *parseand(struct st *st, const char *s, int d)
{
	unsigned char *p;
	s = parserel(st, s, d-1);
	for (;;) {
		if (s[0] != '&' || s[1] != '&')
			return s;
		p = st->p;
		s = parserel(st, s+2, d-1);
		push(st, p - st->p);
		push(st, '&');
	}
}

static const char *parseor(struct st *st, const char *s, int d)
{
	unsigned char *p;
	s = parseand(st, s, d-1);
	for (;;) {
		if (s[0] != '|' || s[1] != '|')
			return s;
		p = st->p;
		s = parseand(st, s+2, --d);
		push(st, p - st->p);
		push(st, '|');
	}
}

static const char *parseexpr(struct st *st, const char *s, int d)
{
	unsigned char *p1, *p2;
	if (d <= 0) {
		fail(st);
		return s;
	}
	s = parseor(st, s, d-1);
	if (*s == '?') {
		p1 = st->p;
		s = parseexpr(st, s+1, d-1);
		p2 = st->p;
		if (*s != ':')
			fail(st);
		else
			s = parseexpr(st, s+1, d-1);
		push(st, p2 - st->p);
		push(st, p1 - st->p);
		push(st, '?');
	}
	return s;
}

int parse(unsigned char *expr, size_t elen, const char *s, size_t slen)
{
	const char *e = s + slen - 1;
	unsigned char *p;
	struct st st;

	if (*e != ';')
		return -1;
	if (elen > 200)
		elen = 200;
	st.e = expr;
	p = st.p = expr + elen;
	s = parseexpr(&st, s, 100);
	if (!ok(&st) || s != e)
		return -1;
	memmove(expr, st.p, p - st.p);
	return 0;
}

static unsigned long evalcond(const unsigned char *e, unsigned long n)
{
	int offcond = *e++;
	unsigned long c = eval(e+offcond, n);
	int offtrue = *e++;
	return eval(c ? e+offtrue : e, n);
}

static unsigned long evalbin(int op, const unsigned char *e, unsigned long n)
{
	int offleft = *e++;
	unsigned long right = eval(e, n);
	unsigned long left = eval(e+offleft, n);
	switch (op) {
	case '|': return left || right;
	case '&': return left && right;
	case '=': return left == right;
	case '<': return left < right;
	case '>': return left > right;
	case '+': return left + right;
	case '-': return left - right;
	case '*': return left * right;
	case '/': return left / right;
	case '%': return left % right;
	}
	return -1;
}

unsigned long eval(const unsigned char *e, unsigned long n)
{
	int op = *e++;
	switch (op) {
	case 'n': return n;
	case 'c': return *e;
	case '!': return !eval(e, n);
	case '?': return evalcond(e, n);
	}
	return evalbin(op, e, n);
}