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   = Term | Mul '*' Term | Mul '/' Term | Mul '%' Term
  15 Term  = '(' Expr ')' | '!' Term | decimal | 'n'
  16
  17 internals:
  18
  19 recursive descent expression evaluator with stack depth limit.
  20 eval* functions return the value of the subexpression and set
  21 the current string pointer to the next non-space char.
  22 */
  23
  24 struct st {
  25         const char *s;
  26         unsigned long n;
  27         int err;
  28 };
  29
  30 static const char *skipspace(const char *s)
  31 {
  32         while (isspace(*s)) s++;
  33         return s;
  34 }
  35
  36 static unsigned long evalconst(struct st *st)
  37 {
  38         char *e;
  39         unsigned long n;
  40         n = strtoul(st->s, &e, 10);
  41         if (!isdigit(*st->s) || e == st->s || n == -1)
  42                 st->err = 1;
  43         st->s = skipspace(e);
  44         return n;
  45 }
  46
  47 static unsigned long evalexpr(struct st *st, int d);
  48
  49 static unsigned long evalterm(struct st *st, int d)
  50 {
  51         unsigned long a;
  52         if (d <= 0) {
  53                 st->err = 1;
  54                 return 0;
  55         }
  56         st->s = skipspace(st->s);
  57         if (*st->s == '!') {
  58                 st->s++;
  59                 return !evalterm(st, d-1);
  60         }
  61         if (*st->s == '(') {
  62                 st->s++;
  63                 a = evalexpr(st, d-1);
  64                 if (*st->s != ')') {
  65                         st->err = 1;
  66                         return 0;
  67                 }
  68                 st->s = skipspace(st->s + 1);
  69                 return a;
  70         }
  71         if (*st->s == 'n') {
  72                 st->s = skipspace(st->s + 1);
  73                 return st->n;
  74         }
  75         return evalconst(st);
  76 }
  77
  78 static unsigned long evalmul(struct st *st, int d)
  79 {
  80         unsigned long b, a = evalterm(st, d-1);
  81         int op;
  82         for (;;) {
  83                 op = *st->s;
  84                 if (op != '*' && op != '/' && op != '%')
  85                         return a;
  86                 st->s++;
  87                 b = evalterm(st, d-1);
  88                 if (op == '*') {
  89                         a *= b;
  90                 } else if (!b) {
  91                         st->err = 1;
  92                         return 0;
  93                 } else if (op == '%') {
  94                         a %= b;
  95                 } else {
  96                         a /= b;
  97                 }
  98         }
  99 }
 100
 101 static unsigned long evaladd(struct st *st, int d)
 102 {
 103         unsigned long a = 0;
 104         int add = 1;
 105         for (;;) {
 106                 a += (add?1:-1) * evalmul(st, d-1);
 107                 if (*st->s != '+' && *st->s != '-')
 108                         return a;
 109                 add = *st->s == '+';
 110                 st->s++;
 111         }
 112 }
 113
 114 static unsigned long evalrel(struct st *st, int d)
 115 {
 116         unsigned long b, a = evaladd(st, d-1);
 117         int less, eq;
 118         for (;;) {
 119                 if (*st->s != '<' && *st->s != '>')
 120                         return a;
 121                 less = st->s[0] == '<';
 122                 eq = st->s[1] == '=';
 123                 st->s += 1 + eq;
 124                 b = evaladd(st, d-1);
 125                 a = (less ? a < b : a > b) || (eq && a == b);
 126         }
 127 }
 128
 129 static unsigned long evaleq(struct st *st, int d)
 130 {
 131         unsigned long a = evalrel(st, d-1);
 132         int neg;
 133         for (;;) {
 134                 if ((st->s[0] != '=' && st->s[0] != '!') || st->s[1] != '=')
 135                         return a;
 136                 neg = st->s[0] == '!';
 137                 st->s += 2;
 138                 a = evalrel(st, d-1) == a;
 139                 a ^= neg;
 140         }
 141 }
 142
 143 static unsigned long evaland(struct st *st, int d)
 144 {
 145         unsigned long a = evaleq(st, d-1);
 146         for (;;) {
 147                 if (st->s[0] != '&' || st->s[1] != '&')
 148                         return a;
 149                 st->s += 2;
 150                 a = evaleq(st, d-1) && a;
 151         }
 152 }
 153
 154 static unsigned long evalor(struct st *st, int d)
 155 {
 156         unsigned long a = evaland(st, d-1);
 157         for (;;) {
 158                 if (st->s[0] != '|' || st->s[1] != '|')
 159                         return a;
 160                 st->s += 2;
 161                 a = evaland(st, d-1) || a;
 162         }
 163 }
 164
 165 static unsigned long evalexpr(struct st *st, int d)
 166 {
 167         unsigned long a1, a2, a3;
 168         if (d <= 0) {
 169                 st->err = 1;
 170                 return 0;
 171         }
 172         a1 = evalor(st, d-1);
 173         if (*st->s != '?')
 174                 return a1;
 175         st->s++;
 176         a2 = evalexpr(st, d-1);
 177         if (*st->s != ':') {
 178                 st->err = 1;
 179                 return 0;
 180         }
 181         st->s++;
 182         a3 = evalexpr(st, d-1);
 183         return a1 ? a2 : a3;
 184 }
 185
 186 unsigned long __pleval(const char *s, unsigned long n)
 187 {
 188         unsigned long a;
 189         struct st st;
 190         st.s = s;
 191         st.n = n;
 192         st.err = 0;
 193         a = evalexpr(&st, 100);
 194         if (st.err || *st.s != ';')
 195                 return -1;
 196         return a;
 197 }