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