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