fusl/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;
}