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