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 static const char *skipspace(const char *s)
  32 {
  33         while (isspace(*s)) s++;
  34         return s;
  35 }
  36
  37 static const char *evalexpr(struct st *st, const char *s, int d);
  38
  39 static const char *evalprim(struct st *st, const char *s, int d)
  40 {
  41         char *e;
  42         if (--d < 0) return "";
  43         s = skipspace(s);
  44         if (isdigit(*s)) {
  45                 st->r = strtoul(s, &e, 10);
  46                 if (e == s || st->r == -1) return "";
  47                 return skipspace(e);
  48         }
  49         if (*s == 'n') {
  50                 st->r = st->n;
  51                 return skipspace(s+1);
  52         }
  53         if (*s == '(') {
  54                 s = evalexpr(st, s+1, d);
  55                 if (*s != ')') return "";
  56                 return skipspace(s+1);
  57         }
  58         if (*s == '!') {
  59                 s = evalprim(st, s+1, d);
  60                 st->r = !st->r;
  61                 return s;
  62         }
  63         return "";
  64 }
  65
  66 static int binop(struct st *st, int op, unsigned long left)
  67 {
  68         unsigned long a = left, b = st->r;
  69         switch (op) {
  70         case 0: st->r = a||b; return 0;
  71         case 1: st->r = a&&b; return 0;
  72         case 2: st->r = a==b; return 0;
  73         case 3: st->r = a!=b; return 0;
  74         case 4: st->r = a>=b; return 0;
  75         case 5: st->r = a<=b; return 0;
  76         case 6: st->r = a>b; return 0;
  77         case 7: st->r = a<b; return 0;
  78         case 8: st->r = a+b; return 0;
  79         case 9: st->r = a-b; return 0;
  80         case 10: st->r = a*b; return 0;
  81         case 11: if (b) {st->r = a%b; return 0;} return 1;
  82         case 12: if (b) {st->r = a/b; return 0;} return 1;
  83         }
  84         return 1;
  85 }
  86
  87 static const char *parseop(struct st *st, const char *s)
  88 {
  89         static const char opch[11] = "|&=!><+-*%/";
  90         static const char opch2[6] = "|&====";
  91         int i;
  92         for (i=0; i<11; i++)
  93                 if (*s == opch[i]) {
  94                         /* note: >,< are accepted with or without = */
  95                         if (i<6 && s[1] == opch2[i]) {
  96                                 st->op = i;
  97                                 return s+2;
  98                         }
  99                         if (i>=4) {
 100                                 st->op = i+2;
 101                                 return s+1;
 102                         }
 103                         break;
 104                 }
 105         st->op = 13;
 106         return s;
 107 }
 108
 109 static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
 110 {
 111         static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
 112         unsigned long left;
 113         int op;
 114         d--;
 115         s = evalprim(st, s, d);
 116         s = parseop(st, s);
 117         for (;;) {
 118                 /*
 119                 st->r (left hand side value) and st->op are now set,
 120                 get the right hand side or back out if op has low prec,
 121                 if op was missing then prec[op]==0
 122                 */
 123                 op = st->op;
 124                 if (prec[op] <= minprec)
 125                         return s;
 126                 left = st->r;
 127                 s = evalbinop(st, s, prec[op], d);
 128                 if (binop(st, op, left))
 129                         return "";
 130         }
 131 }
 132
 133 static const char *evalexpr(struct st *st, const char *s, int d)
 134 {
 135         unsigned long a, b;
 136         if (--d < 0)
 137                 return "";
 138         s = evalbinop(st, s, 0, d);
 139         if (*s != '?')
 140                 return s;
 141         a = st->r;
 142         s = evalexpr(st, s+1, d);
 143         if (*s != ':')
 144                 return "";
 145         b = st->r;
 146         s = evalexpr(st, s+1, d);
 147         st->r = a ? b : st->r;
 148         return s;
 149 }
 150
 151 unsigned long __pleval(const char *s, unsigned long n)
 152 {
 153         struct st st;
 154         st.n = n;
 155         s = evalexpr(&st, s, 100);
 156         return *s == ';' ? st.r : -1;
 157 }