1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24 * G. S. Fowler
25 * D. G. Korn
26 * AT&T Bell Laboratories
27 *
28 * long integer arithmetic expression evaluator
29 * long constants may be represented as:
30 *
31 * 0ooo octal
32 * 0[xX]hhh hexadecimal
33 * ddd decimal
34 * n#ccc base n, 2 <= b <= 36
35 *
36 * NOTE: all operands are evaluated as both the parse
37 * and evaluation are done on the fly
38 */
39
40 #include <ast.h>
41 #include <ctype.h>
42
43 #define getchr(ex) (*(ex)->nextchr++)
44 #define peekchr(ex) (*(ex)->nextchr)
45 #define ungetchr(ex) ((ex)->nextchr--)
46
47 #define error(ex,msg) return(seterror(ex,msg))
48
49 typedef struct /* expression handle */
50 {
51 char* nextchr; /* next expression char */
52 char* errchr; /* next char after error */
53 char* errmsg; /* error message text */
54 long (*convert)(const char*, char**, void*);
55 void* handle; /* user convert handle */
56 } Expr_t;
57
58 /*
59 * set error message string
60 */
61
62 static long
seterror(register Expr_t * ex,char * msg)63 seterror(register Expr_t* ex, char* msg)
64 {
65 if (!ex->errmsg) ex->errmsg = msg;
66 ex->errchr = ex->nextchr;
67 ex->nextchr = "";
68 return(0);
69 }
70
71 /*
72 * evaluate a subexpression with precedence
73 */
74
75 static long
expr(register Expr_t * ex,register int precedence)76 expr(register Expr_t* ex, register int precedence)
77 {
78 register int c;
79 register long n;
80 register long x;
81 char* pos;
82 int operand = 1;
83
84 while (c = getchr(ex), isspace(c));
85 switch (c)
86 {
87 case 0:
88 ungetchr(ex);
89 if (!precedence) return(0);
90 error(ex, "more tokens expected");
91 case '-':
92 n = -expr(ex, 13);
93 break;
94 case '+':
95 n = expr(ex, 13);
96 break;
97 case '!':
98 n = !expr(ex, 13);
99 break;
100 case '~':
101 n = ~expr(ex, 13);
102 break;
103 default:
104 ungetchr(ex);
105 n = 0;
106 operand = 0;
107 break;
108 }
109 for (;;)
110 {
111 switch (c = getchr(ex))
112 {
113 case 0:
114 goto done;
115 case ')':
116 if (!precedence) error(ex, "too many )'s");
117 goto done;
118 case '(':
119 n = expr(ex, 1);
120 if (getchr(ex) != ')')
121 {
122 ungetchr(ex);
123 error(ex, "closing ) expected");
124 }
125 gotoperand:
126 if (operand) error(ex, "operator expected");
127 operand = 1;
128 continue;
129 case '?':
130 if (precedence > 1) goto done;
131 if (peekchr(ex) == ':')
132 {
133 getchr(ex);
134 x = expr(ex, 2);
135 if (!n) n = x;
136 }
137 else
138 {
139 x = expr(ex, 2);
140 if (getchr(ex) != ':')
141 {
142 ungetchr(ex);
143 error(ex, ": expected for ? operator");
144 }
145 if (n)
146 {
147 n = x;
148 expr(ex, 2);
149 }
150 else n = expr(ex, 2);
151 }
152 break;
153 case ':':
154 goto done;
155 case '|':
156 if (peekchr(ex) == '|')
157 {
158 if (precedence > 2) goto done;
159 getchr(ex);
160 x = expr(ex, 3);
161 n = n || x;
162 }
163 else
164 {
165 if (precedence > 4) goto done;
166 x = expr(ex, 5);
167 n |= x;
168 }
169 break;
170 case '^':
171 if (precedence > 5) goto done;
172 x = expr(ex, 6);
173 n ^= x;
174 break;
175 case '&':
176 if (peekchr(ex) == '&')
177 {
178 if (precedence > 3) goto done;
179 getchr(ex);
180 x = expr(ex, 4);
181 n = n && x;
182 }
183 else
184 {
185 if (precedence > 6) goto done;
186 x = expr(ex, 7);
187 n &= x;
188 }
189 break;
190 case '=':
191 case '!':
192 if (peekchr(ex) != '=') error(ex, "operator syntax error");
193 if (precedence > 7) goto done;
194 getchr(ex);
195 x = expr(ex, 8);
196 if (c == '=') n = n == x;
197 else n = n != x;
198 break;
199 case '<':
200 case '>':
201 if (peekchr(ex) == c)
202 {
203 if (precedence > 9) goto done;
204 getchr(ex);
205 x = expr(ex, 10);
206 if (c == '<') n <<= x;
207 else n >>= x;
208 }
209 else
210 {
211 if (precedence > 8) goto done;
212 if (peekchr(ex) == '=')
213 {
214 getchr(ex);
215 x = expr(ex, 9);
216 if (c == '<') n = n <= x;
217 else n = n >= x;
218 }
219 else
220 {
221 x = expr(ex, 9);
222 if (c == '<') n = n < x;
223 else n = n > x;
224 }
225 }
226 break;
227 case '+':
228 case '-':
229 if (precedence > 10) goto done;
230 x = expr(ex, 11);
231 if (c == '+') n += x;
232 else n -= x;
233 break;
234 case '*':
235 case '/':
236 case '%':
237 if (precedence > 11) goto done;
238 x = expr(ex, 12);
239 if (c == '*') n *= x;
240 else if (x == 0) error(ex, "divide by zero");
241 else if (c == '/') n /= x;
242 else n %= x;
243 break;
244 default:
245 if (isspace(c)) continue;
246 pos = --ex->nextchr;
247 if (isdigit(c)) n = strton(ex->nextchr, &ex->nextchr, NiL, 0);
248 else if (ex->convert) n = (*ex->convert)(ex->nextchr, &ex->nextchr, ex->handle);
249 if (ex->nextchr == pos) error(ex, "syntax error");
250 goto gotoperand;
251 }
252 if (ex->errmsg) return(0);
253 if (!operand) error(ex, "operand expected");
254 }
255 done:
256 ungetchr(ex);
257 if (!operand) error(ex, "operand expected");
258 return(n);
259 }
260
261 /*
262 * evaluate an integer arithmetic expression in s
263 *
264 * (long)(*convert)(const char* string, char** end, void* handle)
265 * is a user supplied conversion routine that is called when unknown
266 * chars are encountered; string points to the part to be
267 * converted and end is adjusted to point to the next non-converted
268 * character; if string is 0 then end points to an error message string
269 *
270 * NOTE: (*convert)() may call strexpr(ex, )
271 */
272
273 long
strexpr(const char * s,char ** end,long (* convert)(const char *,char **,void *),void * handle)274 strexpr(const char* s, char** end, long(*convert)(const char*, char**, void*), void* handle)
275 {
276 long n;
277 Expr_t ex;
278
279 ex.nextchr = (char*)s;
280 ex.errmsg = 0;
281 ex.convert = convert;
282 ex.handle = handle;
283 n = expr(&ex, 0);
284 if (peekchr(&ex) == ':')
285 seterror(&ex, "invalid use of :");
286 if (ex.errmsg)
287 {
288 if (convert) (*convert)(NiL, &ex.errmsg, handle);
289 ex.nextchr = ex.errchr;
290 n = 0;
291 }
292 if (end) *end = ex.nextchr;
293 return(n);
294 }
295