src/locale/pleval.c

   1 #include <stdlib.h>
   2 #include <ctype.h>
   3 #include "pleval.h"
   4
   5 /*
   6 grammar:
   7
   8 Start = Expr ';'
   9 Expr  = Or | Or '?' Expr ':' Expr
  10 Or    = And | Or '||' And
  11 And   = Eq | And '&&' Eq
  12 Eq    = Rel | Eq '==' Rel | Eq '!=' Rel
  13 Rel   = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
  14 Add   = Mul | Add '+' Mul | Add '-' Mul
  15 Mul   = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
  16 Prim  = '(' Expr ')' | '!' Prim | decimal | 'n'
  17
  18 internals:
  19
  20 recursive descent expression evaluator with stack depth limit.
  21 for binary operators an operator-precedence parser is used.
  22 eval* functions store the result of the parsed subexpression
  23 and return a pointer to the next non-space character.
  24 */
  25
  26 struct st {
  27         unsigned long r;
  28         unsigned long n;
  29         int op;
  30 };
  31
  32 static const char *skipspace(const char *s)
  33 {
  34         while (isspace(*s)) s++;
  35         return s;
  36 }
  37
  38 static const char *evalexpr(struct st *st, const char *s, int d);
  39
  40 static const char *evalprim(struct st *st, const char *s, int d)
  41 {
  42         char *e;
  43         if (--d < 0) return "";
  44         s = skipspace(s);
  45         if (isdigit(*s)) {
  46                 st->r = strtoul(s, &e, 10);
  47                 if (e == s || st->r == -1) return "";
  48                 return skipspace(e);
  49         }
  50         if (*s == 'n') {
  51                 st->r = st->n;
  52                 return skipspace(s+1);
  53         }
  54         if (*s == '(') {
  55                 s = evalexpr(st, s+1, d);
  56                 if (*s != ')') return "";
  57                 return skipspace(s+1);
  58         }
  59         if (*s == '!') {
  60                 s = evalprim(st, s+1, d);
  61                 st->r = !st->r;
  62                 return s;
  63         }
  64         return "";
  65 }
  66
  67 static int binop(struct st *st, int op, unsigned long left)
  68 {
  69         unsigned long a = left, b = st->r;
  70         switch (op) {
  71         case 0: st->r = a||b; return 0;
  72         case 1: st->r = a&&b; return 0;
  73         case 2: st->r = a==b; return 0;
  74         case 3: st->r = a!=b; return 0;
  75         case 4: st->r = a>=b; return 0;
  76         case 5: st->r = a<=b; return 0;
  77         case 6: st->r = a>b; return 0;
  78         case 7: st->r = a<b; return 0;
  79         case 8: st->r = a+b; return 0;
  80         case 9: st->r = a-b; return 0;
  81         case 10: st->r = a*b; return 0;
  82         case 11: if (b) {st->r = a%b; return 0;} return 1;
  83         case 12: if (b) {st->r = a/b; return 0;} return 1;
  84         }
  85         return 1;
  86 }
  87
  88 static const char *parseop(struct st *st, const char *s)
  89 {
  90         static const char opch[11] = "|&=!><+-*%/";
  91         static const char opch2[6] = "|&====";
  92         int i;
  93         for (i=0; i<11; i++)
  94                 if (*s == opch[i]) {
  95                         /* note: >,< are accepted with or without = */
  96                         if (i<6 && s[1] == opch2[i]) {
  97                                 st->op = i;
  98                                 return s+2;
  99                         }
 100                         if (i>=4) {
 101                                 st->op = i+2;
 102                                 return s+1;
 103                         }
 104                         break;
 105                 }
 106         st->op = 13;
 107         return s;
 108 }
 109
 110 static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
 111 {
 112         static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
 113         unsigned long left;
 114         int op;
 115         d--;
 116         s = evalprim(st, s, d);
 117         s = parseop(st, s);
 118         for (;;) {
 119                 /*
 120                 st->r (left hand side value) and st->op are now set,
 121                 get the right hand side or back out if op has low prec,
 122                 if op was missing then prec[op]==0
 123                 */
 124                 op = st->op;
 125                 if (prec[op] <= minprec)
 126                         return s;
 127                 left = st->r;
 128                 s = evalbinop(st, s, prec[op], d);
 129                 if (binop(st, op, left))
 130                         return "";
 131         }
 132 }
 133
 134 static const char *evalexpr(struct st *st, const char *s, int d)
 135 {
 136         unsigned long a, b;
 137         if (--d < 0)
 138                 return "";
 139         s = evalbinop(st, s, 0, d);
 140         if (*s != '?')
 141                 return s;
 142         a = st->r;
 143         s = evalexpr(st, s+1, d);
 144         if (*s != ':')
 145                 return "";
 146         b = st->r;
 147         s = evalexpr(st, s+1, d);
 148         st->r = a ? b : st->r;
 149         return s;
 150 }
 151
 152 unsigned long __pleval(const char *s, unsigned long n)
 153 {
 154         struct st st;
 155         st.n = n;
 156         s = evalexpr(&st, s, 100);
 157         return *s == ';' ? st.r : -1;
 158 }