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*                  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
49typedef 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
62static long
63seterror(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
75static long
76expr(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
273long
274strexpr(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