1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                 Eclipse Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *          http://www.eclipse.org/org/documents/epl-v10.html           *
11 *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
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