expr.c revision 95060 
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 95060 2002-04-19 17:26:21Z 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, eqrel;
249
250	vl = shift();
251	while ((eqrel = geteqrel()) != -1) {
252		vr = shift();
253
254		switch (eqrel) {
255
256		case EQL:
257			vl = (vl == vr);
258			break;
259		case NEQ:
260			vl = (vl != vr);
261			break;
262
263		case LEQ:
264			vl = (vl <= vr);
265			break;
266		case LSS:
267			vl = (vl < vr);
268			break;
269		case GTR:
270			vl = (vl > vr);
271			break;
272		case GEQ:
273			vl = (vl >= vr);
274			break;
275		}
276	}
277	return vl;
278}
279
280/*
281 * shift : primary { shop primary }
282 */
283static int
284shift()
285{
286	int vl, vr, c;
287
288	vl = primary();
289	while (((c = skipws()) == '<' || c == '>') && getch() == c) {
290		vr = primary();
291
292		if (c == '<')
293			vl <<= vr;
294		else
295			vl >>= vr;
296	}
297
298	if (c == '<' || c == '>')
299		ungetch();
300	ungetch();
301	return vl;
302}
303
304/*
305 * primary : term { addop term }
306 */
307static int
308primary()
309{
310	int c, vl, vr;
311
312	vl = term();
313	while ((c = skipws()) == '+' || c == '-') {
314		vr = term();
315
316		if (c == '+')
317			vl += vr;
318		else
319			vl -= vr;
320	}
321
322	ungetch();
323	return vl;
324}
325
326/*
327 * <term> := <exp> { <mulop> <exp> }
328 */
329static int
330term()
331{
332	int c, vl, vr;
333
334	vl = exp();
335	while ((c = skipws()) == '*' || c == '/' || c == '%') {
336		vr = exp();
337
338		switch (c) {
339		case '*':
340			vl *= vr;
341			break;
342		case '/':
343			if (vr == 0)
344				errx(1, "division by zero in eval.");
345			else
346				vl /= vr;
347			break;
348		case '%':
349			if (vr == 0)
350				errx(1, "modulo zero in eval.");
351			else
352				vl %= vr;
353			break;
354		}
355	}
356	ungetch();
357	return vl;
358}
359
360/*
361 * <term> := <unary> { <expop> <unary> }
362 */
363static int
364exp()
365{
366	int c, vl, vr, n;
367
368	vl = unary();
369	switch (c = skipws()) {
370
371	case '*':
372		if (getch() != '*') {
373			ungetch();
374			break;
375		}
376
377	case '^':
378		vr = exp();
379		n = 1;
380		while (vr-- > 0)
381			n *= vl;
382		return n;
383	}
384
385	ungetch();
386	return vl;
387}
388
389/*
390 * unary : factor | unop unary
391 */
392static int
393unary()
394{
395	int val, c;
396
397	if ((c = skipws()) == '+' || c == '-' || c == '~') {
398		val = unary();
399
400		switch (c) {
401		case '+':
402			return val;
403		case '-':
404			return -val;
405		case '~':
406			return ~val;
407		}
408	}
409
410	ungetch();
411	return factor();
412}
413
414/*
415 * factor : constant | '(' query ')'
416 */
417static int
418factor()
419{
420	int val;
421
422	if (skipws() == '(') {
423		val = query();
424		if (skipws() != ')')
425			experr("bad factor");
426		return val;
427	}
428
429	ungetch();
430	return constant();
431}
432
433/*
434 * constant: num | 'char'
435 * Note: constant() handles multi-byte constants
436 */
437static int
438constant()
439{
440	int i;
441	int value;
442	int c;
443	int v[sizeof(int)];
444
445	if (skipws() != '\'') {
446		ungetch();
447		return num();
448	}
449	for (i = 0; i < sizeof(int); i++) {
450		if ((c = getch()) == '\'') {
451			ungetch();
452			break;
453		}
454		if (c == '\\') {
455			switch (c = getch()) {
456			case '0':
457			case '1':
458			case '2':
459			case '3':
460			case '4':
461			case '5':
462			case '6':
463			case '7':
464				ungetch();
465				c = num();
466				break;
467			case 'n':
468				c = 012;
469				break;
470			case 'r':
471				c = 015;
472				break;
473			case 't':
474				c = 011;
475				break;
476			case 'b':
477				c = 010;
478				break;
479			case 'f':
480				c = 014;
481				break;
482			}
483		}
484		v[i] = c;
485	}
486	if (i == 0 || getch() != '\'')
487		experr("illegal character constant");
488	for (value = 0; --i >= 0;) {
489		value <<= 8;
490		value += v[i];
491	}
492	return value;
493}
494
495/*
496 * num : digit | num digit
497 */
498static int
499num()
500{
501	int rval, c, base;
502	int ndig;
503
504	rval = 0;
505	ndig = 0;
506	c = skipws();
507	if (c == '0') {
508		c = skipws();
509		if (c == 'x' || c == 'X') {
510			base = HEX;
511			c = skipws();
512		} else {
513			base = OCTAL;
514			ndig++;
515		}
516	} else
517		base = DECIMAL;
518	for(;;) {
519		switch(c) {
520			case '8': case '9':
521				if (base == OCTAL)
522					goto bad_digit;
523				/*FALLTHRU*/
524			case '0': case '1': case '2': case '3':
525			case '4': case '5': case '6': case '7':
526				rval *= base;
527				rval += c - '0';
528				break;
529			case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
530				c = tolower(c);
531			case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
532				if (base == HEX) {
533					rval *= base;
534					rval += c - 'a' + 10;
535					break;
536				}
537				/*FALLTHRU*/
538			default:
539				goto bad_digit;
540		}
541		c = getch();
542		ndig++;
543	}
544bad_digit:
545	ungetch();
546
547	if (ndig == 0)
548		experr("bad constant");
549
550	return rval;
551}
552
553/*
554 * eqrel : '=' | '==' | '!=' | '<' | '>' | '<=' | '>='
555 */
556static int
557geteqrel()
558{
559	int c1, c2;
560
561	c1 = skipws();
562	c2 = getch();
563
564	switch (c1) {
565
566	case '=':
567		if (c2 != '=')
568			ungetch();
569		return EQL;
570
571	case '!':
572		if (c2 == '=')
573			return NEQ;
574		ungetch();
575		ungetch();
576		return -1;
577
578	case '<':
579		if (c2 == '=')
580			return LEQ;
581		ungetch();
582		return LSS;
583
584	case '>':
585		if (c2 == '=')
586			return GEQ;
587		ungetch();
588		return GTR;
589
590	default:
591		ungetch();
592		ungetch();
593		return -1;
594	}
595}
596
597/*
598 * Skip over any white space and return terminating char.
599 */
600static int
601skipws()
602{
603	int c;
604
605	while ((c = getch()) <= ' ' && c > EOS)
606		;
607	return c;
608}
609
610/*
611 * resets environment to eval(), prints an error
612 * and forces eval to return FALSE.
613 */
614static void
615experr(msg)
616	const char *msg;
617{
618	printf("m4: %s in expr %s.\n", msg, where);
619	longjmp(expjump, -1);
620}
621