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 fail(struct st *st)
  37 {
  38         st->err = 1;
  39         return 0;
  40 }
  41
  42 static unsigned long evalexpr(struct st *st, int d);
  43
  44 static unsigned long evalterm(struct st *st, int d)
  45 {
  46         unsigned long a;
  47         char *e;
  48         if (--d < 0) return fail(st);
  49         st->s = skipspace(st->s);
  50         if (isdigit(*st->s)) {
  51                 a = strtoul(st->s, &e, 10);
  52                 if (e == st->s || a == -1) return fail(st);
  53                 st->s = skipspace(e);
  54                 return a;
  55         }
  56         if (*st->s == 'n') {
  57                 st->s = skipspace(st->s + 1);
  58                 return st->n;
  59         }
  60         if (*st->s == '(') {
  61                 st->s++;
  62                 a = evalexpr(st, d);
  63                 if (*st->s != ')') return fail(st);
  64                 st->s = skipspace(st->s + 1);
  65                 return a;
  66         }
  67         if (*st->s == '!') {
  68                 st->s++;
  69                 return !evalterm(st, d);
  70         }
  71         return fail(st);
  72 }
  73
  74 static unsigned long evalmul(struct st *st, int d)
  75 {
  76         unsigned long b, a = evalterm(st, d);
  77         int op;
  78         for (;;) {
  79                 op = *st->s;
  80                 if (op != '*' && op != '/' && op != '%')
  81                         return a;
  82                 st->s++;
  83                 b = evalterm(st, d);
  84                 if (op == '*') {
  85                         a *= b;
  86                 } else if (!b) {
  87                         return fail(st);
  88                 } else if (op == '%') {
  89                         a %= b;
  90                 } else {
  91                         a /= b;
  92                 }
  93         }
  94 }
  95
  96 static unsigned long evaladd(struct st *st, int d)
  97 {
  98         unsigned long a = 0;
  99         int sub = 0;
 100         for (;;) {
 101                 a += (sub ? -1 : 1) * evalmul(st, d);
 102                 if (*st->s != '+' && *st->s != '-')
 103                         return a;
 104                 sub = *st->s == '-';
 105                 st->s++;
 106         }
 107 }
 108
 109 static unsigned long evalrel(struct st *st, int d)
 110 {
 111         unsigned long b, a = evaladd(st, d);
 112         int less, eq;
 113         for (;;) {
 114                 if (*st->s != '<' && *st->s != '>')
 115                         return a;
 116                 less = st->s[0] == '<';
 117                 eq = st->s[1] == '=';
 118                 st->s += 1 + eq;
 119                 b = evaladd(st, d);
 120                 a = (less ? a < b : a > b) || (eq && a == b);
 121         }
 122 }
 123
 124 static unsigned long evaleq(struct st *st, int d)
 125 {
 126         unsigned long a = evalrel(st, d);
 127         int c;
 128         for (;;) {
 129                 c = st->s[0];
 130                 if ((c != '=' && c != '!') || st->s[1] != '=')
 131                         return a;
 132                 st->s += 2;
 133                 a = (evalrel(st, d) == a) ^ (c == '!');
 134         }
 135 }
 136
 137 static unsigned long evaland(struct st *st, int d)
 138 {
 139         unsigned long a = evaleq(st, d);
 140         for (;;) {
 141                 if (st->s[0] != '&' || st->s[1] != '&')
 142                         return a;
 143                 st->s += 2;
 144                 a = evaleq(st, d) && a;
 145         }
 146 }
 147
 148 static unsigned long evalor(struct st *st, int d)
 149 {
 150         unsigned long a = evaland(st, d);
 151         for (;;) {
 152                 if (st->s[0] != '|' || st->s[1] != '|')
 153                         return a;
 154                 st->s += 2;
 155                 a = evaland(st, d) || a;
 156         }
 157 }
 158
 159 static unsigned long evalexpr(struct st *st, int d)
 160 {
 161         unsigned long a1, a2, a3;
 162         if (--d < 0)
 163                 return fail(st);
 164         a1 = evalor(st, d-6);
 165         if (*st->s != '?')
 166                 return a1;
 167         st->s++;
 168         a2 = evalexpr(st, d);
 169         if (*st->s != ':')
 170                 return fail(st);
 171         st->s++;
 172         a3 = evalexpr(st, d);
 173         return a1 ? a2 : a3;
 174 }
 175
 176 unsigned long __pleval(const char *s, unsigned long n)
 177 {
 178         unsigned long a;
 179         struct st st;
 180         st.s = s;
 181         st.n = n;
 182         st.err = 0;
 183         a = evalexpr(&st, 100);
 184         if (st.err || *st.s != ';')
 185                 return -1;
 186         return a;
 187 }