third_party/musl/src/locale/pleval.c

#include <stdlib.h>
#include <ctype.h>

/*
grammar:

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

internals:

recursive descent expression evaluator with stack depth limit.
for binary operators an operator-precedence parser is used.
eval* functions store the result of the parsed subexpression
and return a pointer to the next non-space character.
*/

struct st {
	unsigned long r;
	unsigned long n;
	int op;
};

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

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

static const char *evalprim(struct st *st, const char *s, int d)
{
	char *e;
	if (--d < 0) return "";
	s = skipspace(s);
	if (isdigit(*s)) {
		st->r = strtoul(s, &e, 10);
		if (e == s || st->r == -1) return "";
		return skipspace(e);
	}
	if (*s == 'n') {
		st->r = st->n;
		return skipspace(s+1);
	}
	if (*s == '(') {
		s = evalexpr(st, s+1, d);
		if (*s != ')') return "";
		return skipspace(s+1);
	}
	if (*s == '!') {
		s = evalprim(st, s+1, d);
		st->r = !st->r;
		return s;
	}
	return "";
}

static int binop(struct st *st, int op, unsigned long left)
{
	unsigned long a = left, b = st->r;
	switch (op) {
	case 0: st->r = a||b; return 0;
	case 1: st->r = a&&b; return 0;
	case 2: st->r = a==b; return 0;
	case 3: st->r = a!=b; return 0;
	case 4: st->r = a>=b; return 0;
	case 5: st->r = a<=b; return 0;
	case 6: st->r = a>b; return 0;
	case 7: st->r = a<b; return 0;
	case 8: st->r = a+b; return 0;
	case 9: st->r = a-b; return 0;
	case 10: st->r = a*b; return 0;
	case 11: if (b) {st->r = a%b; return 0;} return 1;
	case 12: if (b) {st->r = a/b; return 0;} return 1;
	}
	return 1;
}

static const char *parseop(struct st *st, const char *s)
{
	static const char opch[11] = "|&=!><+-*%/";
	static const char opch2[6] = "|&====";
	int i;
	for (i=0; i<11; i++)
		if (*s == opch[i]) {
			/* note: >,< are accepted with or without = */
			if (i<6 && s[1] == opch2[i]) {
				st->op = i;
				return s+2;
			}
			if (i>=4) {
				st->op = i+2;
				return s+1;
			}
			break;
		}
	st->op = 13;
	return s;
}

static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
{
	static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
	unsigned long left;
	int op;
	d--;
	s = evalprim(st, s, d);
	s = parseop(st, s);
	for (;;) {
		/*
		st->r (left hand side value) and st->op are now set,
		get the right hand side or back out if op has low prec,
		if op was missing then prec[op]==0
		*/
		op = st->op;
		if (prec[op] <= minprec)
			return s;
		left = st->r;
		s = evalbinop(st, s, prec[op], d);
		if (binop(st, op, left))
			return "";
	}
}

static const char *evalexpr(struct st *st, const char *s, int d)
{
	unsigned long a, b;
	if (--d < 0)
		return "";
	s = evalbinop(st, s, 0, d);
	if (*s != '?')
		return s;
	a = st->r;
	s = evalexpr(st, s+1, d);
	if (*s != ':')
		return "";
	b = st->r;
	s = evalexpr(st, s+1, d);
	st->r = a ? b : st->r;
	return s;
}

unsigned long __pleval(const char *s, unsigned long n)
{
	struct st st;
	st.n = n;
	s = evalexpr(&st, s, 100);
	return *s == ';' ? st.r : -1;
}