xref: /freebsd/usr.bin/m4/expr.c (revision 10b59a9b4add0320d52c15ce057dd697261e7dfc) 
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    :       exponent { ("*" | "/" | "%") exponent }
75  *      exponent:       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 exponent(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 skipws(void);
124 static void experr(const char *);
125 
126 /*
127  * For longjmp
128  */
129 #include <setjmp.h>
130 static jmp_buf expjump;
131 
132 /*
133  * macros:
134  *      ungetch - Put back the last character examined.
135  *      getch   - return the next character from expr string.
136  */
137 #define ungetch()       nxtch--
138 #define getch()         *nxtch++
139 
140 int
141 expr(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 result, true_val, false_val;
165 
166 	result = lor(mayeval);
167 	if (skipws() != '?') {
168 		ungetch();
169 		return result;
170 	}
171 
172 	true_val = query(result);
173 	if (skipws() != ':')
174 		experr("bad query: missing \":\"");
175 
176 	false_val = query(!result);
177 	return result ? 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 : exponent { ("*" | "/" | "%") exponent }
391  */
392 static int
393 term(int mayeval)
394 {
395 	int c, vl, vr;
396 
397 	vl = exponent(mayeval);
398 	while ((c = skipws()) == '*' || c == '/' || c == '%') {
399 		vr = exponent(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  * exponent : unary { "**" exponent }
429  */
430 static int
431 exponent(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 	int c;
508 	int v[sizeof(int)];
509 
510 	if (skipws() != '\'') {
511 		ungetch();
512 		return num(mayeval);
513 	}
514 	for (i = 0; i < (ssize_t)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 __unused)
565 {
566 	int rval, c, base;
567 	int ndig;
568 
569 	rval = 0;
570 	ndig = 0;
571 	c = skipws();
572 	if (c == '0') {
573 		c = skipws();
574 		if (c == 'x' || c == 'X') {
575 			base = HEX;
576 			c = skipws();
577 		} else {
578 			base = OCTAL;
579 			ndig++;
580 		}
581 	} else
582 		base = DECIMAL;
583 	for(;;) {
584 		switch(c) {
585 			case '8': case '9':
586 				if (base == OCTAL)
587 					goto bad_digit;
588 				/*FALLTHRU*/
589 			case '0': case '1': case '2': case '3':
590 			case '4': case '5': case '6': case '7':
591 				rval *= base;
592 				rval += c - '0';
593 				break;
594 			case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
595 				c = tolower(c);
596 			case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
597 				if (base == HEX) {
598 					rval *= base;
599 					rval += c - 'a' + 10;
600 					break;
601 				}
602 				/*FALLTHRU*/
603 			default:
604 				goto bad_digit;
605 		}
606 		c = getch();
607 		ndig++;
608 	}
609 bad_digit:
610 	ungetch();
611 
612 	if (ndig == 0)
613 		experr("bad constant");
614 
615 	return rval;
616 }
617 
618 /*
619  * Skip over any white space and return terminating char.
620  */
621 static int
622 skipws(void)
623 {
624 	int c;
625 
626 	while ((c = getch()) <= ' ' && c > EOS)
627 		;
628 	return c;
629 }
630 
631 /*
632  * resets environment to eval(), prints an error
633  * and forces eval to return FALSE.
634  */
635 static void
636 experr(const char *msg)
637 {
638 	printf("m4: %s in expr %s.\n", msg, where);
639 	longjmp(expjump, -1);
640 }
641