nsz Git - musl/blob - src/locale/pleval.c

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