expr.c revision 95095 
1/*	$OpenBSD: expr.c,v 1.12 2002/02/16 21:27:48 millert Exp $	*/
2/*	$NetBSD: expr.c,v 1.7 1995/09/28 05:37:31 tls Exp $	*/
3
4/*
5 * Copyright (c) 1989, 1993
6 *	The Regents of the University of California.  All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Ozan Yigit at York University.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in the
18 *    documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 *    must display the following acknowledgement:
21 *	This product includes software developed by the University of
22 *	California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 *    may be used to endorse or promote products derived from this software
25 *    without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 */
39
40#include <sys/cdefs.h>
41__SCCSID("@(#)expr.c      8.2 (Berkeley) 4/29/95");
42__RCSID_SOURCE("$OpenBSD: expr.c,v 1.12 2002/02/16 21:27:48 millert Exp $");
43__FBSDID("$FreeBSD: head/usr.bin/m4/expr.c 95095 2002-04-20 01:49:10Z jmallett $");
44
45#include <sys/types.h>
46#include <ctype.h>
47#include <err.h>
48#include <stddef.h>
49#include <stdio.h>
50#include "mdef.h"
51#include "extern.h"
52
53/*
54 *      expression evaluator: performs a standard recursive
55 *      descent parse to evaluate any expression permissible
56 *      within the following grammar:
57 *
58 *      expr    :       query EOS
59 *      query   :       lor
60 *              |       lor "?" query ":" query
61 *      lor     :       land { "||" land }
62 *      land    :       not { "&&" not }
63 *	not	:	eqrel
64 *		|	'!' not
65 *      eqrel   :       shift { eqrelop shift }
66 *      shift   :       primary { shop primary }
67 *      primary :       term { addop term }
68 *      term    :       exp { mulop exp }
69 *	exp	:	unary { expop unary }
70 *      unary   :       factor
71 *              |       unop unary
72 *      factor  :       constant
73 *              |       "(" query ")"
74 *      constant:       num
75 *              |       "'" CHAR "'"
76 *      num     :       DIGIT
77 *              |       DIGIT num
78 *      shop    :       "<<"
79 *              |       ">>"
80 *      eqrel   :       "="
81 *              |       "=="
82 *              |       "!="
83 *      	|       "<"
84 *              |       ">"
85 *              |       "<="
86 *              |       ">="
87 *
88 *
89 *      This expression evaluator is lifted from a public-domain
90 *      C Pre-Processor included with the DECUS C Compiler distribution.
91 *      It is hacked somewhat to be suitable for m4.
92 *
93 *      Originally by:  Mike Lutz
94 *                      Bob Harper
95 */
96
97#define EQL     0
98#define NEQ     1
99#define LSS     2
100#define LEQ     3
101#define GTR     4
102#define GEQ     5
103#define OCTAL   8
104#define DECIMAL 10
105#define HEX	16
106
107static const char *nxtch;		       /* Parser scan pointer */
108static const char *where;
109
110static int query(void);
111static int lor(void);
112static int land(void);
113static int not(void);
114static int eqrel(void);
115static int shift(void);
116static int primary(void);
117static int term(void);
118static int exp(void);
119static int unary(void);
120static int factor(void);
121static int constant(void);
122static int num(void);
123static int geteqrel(void);
124static int skipws(void);
125static void experr(const char *);
126
127/*
128 * For longjmp
129 */
130#include <setjmp.h>
131static jmp_buf expjump;
132
133/*
134 * macros:
135 *      ungetch - Put back the last character examined.
136 *      getch   - return the next character from expr string.
137 */
138#define ungetch()       nxtch--
139#define getch()         *nxtch++
140
141int
142expr(expbuf)
143	const char *expbuf;
144{
145	int rval;
146
147	nxtch = expbuf;
148	where = expbuf;
149	if (setjmp(expjump) != 0)
150		return FALSE;
151
152	rval = query();
153	if (skipws() == EOS)
154		return rval;
155
156	printf("m4: ill-formed expression.\n");
157	return FALSE;
158}
159
160/*
161 * query : lor | lor '?' query ':' query
162 */
163static int
164query()
165{
166	int bool, true_val, false_val;
167
168	bool = lor();
169	if (skipws() != '?') {
170		ungetch();
171		return bool;
172	}
173
174	true_val = query();
175	if (skipws() != ':')
176		experr("bad query");
177
178	false_val = query();
179	return bool ? true_val : false_val;
180}
181
182/*
183 * lor : land { '||' land }
184 */
185static int
186lor()
187{
188	int c, vl, vr;
189
190	vl = land();
191	while ((c = skipws()) == '|') {
192		if (getch() != '|')
193			ungetch();
194		vr = land();
195		vl = vl || vr;
196	}
197
198	ungetch();
199	return vl;
200}
201
202/*
203 * land : not { '&&' not }
204 */
205static int
206land()
207{
208	int c, vl, vr;
209
210	vl = not();
211	while ((c = skipws()) == '&') {
212		if (getch() != '&')
213			ungetch();
214		vr = not();
215		vl = vl && vr;
216	}
217
218	ungetch();
219	return vl;
220}
221
222/*
223 * not : eqrel | '!' not
224 */
225static int
226not()
227{
228	int val, c;
229
230	if ((c = skipws()) == '!' && getch() != '=') {
231		ungetch();
232		val = not();
233		return !val;
234	}
235
236	if (c == '!')
237		ungetch();
238	ungetch();
239	return eqrel();
240}
241
242/*
243 * eqrel : shift { eqrelop shift }
244 */
245static int
246eqrel()
247{
248	int vl, vr, eqrelval;
249
250	vl = shift();
251	while ((eqrelval = geteqrel()) != -1) {
252		vr = shift();
253
254		switch (eqrelval) {
255		case EQL:
256			vl = (vl == vr);
257			break;
258		case NEQ:
259			vl = (vl != vr);
260			break;
261		case LEQ:
262			vl = (vl <= vr);
263			break;
264		case LSS:
265			vl = (vl < vr);
266			break;
267		case GTR:
268			vl = (vl > vr);
269			break;
270		case GEQ:
271			vl = (vl >= vr);
272			break;
273		}
274	}
275	return vl;
276}
277
278/*
279 * shift : primary { shop primary }
280 */
281static int
282shift()
283{
284	int vl, vr, c;
285
286	vl = primary();
287	while (((c = skipws()) == '<' || c == '>') && getch() == c) {
288		vr = primary();
289
290		if (c == '<')
291			vl <<= vr;
292		else
293			vl >>= vr;
294	}
295
296	if (c == '<' || c == '>')
297		ungetch();
298	ungetch();
299	return vl;
300}
301
302/*
303 * primary : term { addop term }
304 */
305static int
306primary()
307{
308	int c, vl, vr;
309
310	vl = term();
311	while ((c = skipws()) == '+' || c == '-') {
312		vr = term();
313
314		if (c == '+')
315			vl += vr;
316		else
317			vl -= vr;
318	}
319
320	ungetch();
321	return vl;
322}
323
324/*
325 * <term> := <exp> { <mulop> <exp> }
326 */
327static int
328term()
329{
330	int c, vl, vr;
331
332	vl = exp();
333	while ((c = skipws()) == '*' || c == '/' || c == '%') {
334		vr = exp();
335
336		switch (c) {
337		case '*':
338			vl *= vr;
339			break;
340		case '/':
341			if (vr == 0)
342				errx(1, "division by zero in eval.");
343			else
344				vl /= vr;
345			break;
346		case '%':
347			if (vr == 0)
348				errx(1, "modulo zero in eval.");
349			else
350				vl %= vr;
351			break;
352		}
353	}
354	ungetch();
355	return vl;
356}
357
358/*
359 * <term> := <unary> { <expop> <unary> }
360 */
361static int
362exp()
363{
364	int c, vl, vr, n;
365
366	vl = unary();
367	switch (c = skipws()) {
368
369	case '*':
370		if (getch() != '*') {
371			ungetch();
372			break;
373		}
374
375	case '^':
376		vr = exp();
377		n = 1;
378		while (vr-- > 0)
379			n *= vl;
380		return n;
381	}
382
383	ungetch();
384	return vl;
385}
386
387/*
388 * unary : factor | unop unary
389 */
390static int
391unary()
392{
393	int val, c;
394
395	if ((c = skipws()) == '+' || c == '-' || c == '~') {
396		val = unary();
397
398		switch (c) {
399		case '+':
400			return val;
401		case '-':
402			return -val;
403		case '~':
404			return ~val;
405		}
406	}
407
408	ungetch();
409	return factor();
410}
411
412/*
413 * factor : constant | '(' query ')'
414 */
415static int
416factor()
417{
418	int val;
419
420	if (skipws() == '(') {
421		val = query();
422		if (skipws() != ')')
423			experr("bad factor");
424		return val;
425	}
426
427	ungetch();
428	return constant();
429}
430
431/*
432 * constant: num | 'char'
433 * Note: constant() handles multi-byte constants
434 */
435static int
436constant()
437{
438	int i;
439	int value;
440	int c;
441	int v[sizeof(int)];
442
443	if (skipws() != '\'') {
444		ungetch();
445		return num();
446	}
447	for (i = 0; i < (int)sizeof(int); i++) {
448		if ((c = getch()) == '\'') {
449			ungetch();
450			break;
451		}
452		if (c == '\\') {
453			switch (c = getch()) {
454			case '0':
455			case '1':
456			case '2':
457			case '3':
458			case '4':
459			case '5':
460			case '6':
461			case '7':
462				ungetch();
463				c = num();
464				break;
465			case 'n':
466				c = 012;
467				break;
468			case 'r':
469				c = 015;
470				break;
471			case 't':
472				c = 011;
473				break;
474			case 'b':
475				c = 010;
476				break;
477			case 'f':
478				c = 014;
479				break;
480			}
481		}
482		v[i] = c;
483	}
484	if (i == 0 || getch() != '\'')
485		experr("illegal character constant");
486	for (value = 0; --i >= 0;) {
487		value <<= 8;
488		value += v[i];
489	}
490	return value;
491}
492
493/*
494 * num : digit | num digit
495 */
496static int
497num()
498{
499	int rval, c, base;
500	int ndig;
501
502	rval = 0;
503	ndig = 0;
504	c = skipws();
505	if (c == '0') {
506		c = skipws();
507		if (c == 'x' || c == 'X') {
508			base = HEX;
509			c = skipws();
510		} else {
511			base = OCTAL;
512			ndig++;
513		}
514	} else
515		base = DECIMAL;
516	for(;;) {
517		switch(c) {
518			case '8': case '9':
519				if (base == OCTAL)
520					goto bad_digit;
521				/*FALLTHRU*/
522			case '0': case '1': case '2': case '3':
523			case '4': case '5': case '6': case '7':
524				rval *= base;
525				rval += c - '0';
526				break;
527			case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
528				c = tolower(c);
529			case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
530				if (base == HEX) {
531					rval *= base;
532					rval += c - 'a' + 10;
533					break;
534				}
535				/*FALLTHRU*/
536			default:
537				goto bad_digit;
538		}
539		c = getch();
540		ndig++;
541	}
542bad_digit:
543	ungetch();
544
545	if (ndig == 0)
546		experr("bad constant");
547
548	return rval;
549}
550
551/*
552 * eqrel : '=' | '==' | '!=' | '<' | '>' | '<=' | '>='
553 */
554static int
555geteqrel()
556{
557	int c1, c2;
558
559	c1 = skipws();
560	c2 = getch();
561
562	switch (c1) {
563
564	case '=':
565		if (c2 != '=')
566			ungetch();
567		return EQL;
568
569	case '!':
570		if (c2 == '=')
571			return NEQ;
572		ungetch();
573		ungetch();
574		return -1;
575
576	case '<':
577		if (c2 == '=')
578			return LEQ;
579		ungetch();
580		return LSS;
581
582	case '>':
583		if (c2 == '=')
584			return GEQ;
585		ungetch();
586		return GTR;
587
588	default:
589		ungetch();
590		ungetch();
591		return -1;
592	}
593}
594
595/*
596 * Skip over any white space and return terminating char.
597 */
598static int
599skipws()
600{
601	int c;
602
603	while ((c = getch()) <= ' ' && c > EOS)
604		;
605	return c;
606}
607
608/*
609 * resets environment to eval(), prints an error
610 * and forces eval to return FALSE.
611 */
612static void
613experr(msg)
614	const char *msg;
615{
616	printf("m4: %s in expr %s.\n", msg, where);
617	longjmp(expjump, -1);
618}
619