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