third_party/ulib/musl/src/locale/pleval.c

#include <ctype.h>
#include <stdlib.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 == -1ul)
            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;
}