xref: /dragonfly/usr.bin/m4/expr.c (revision 606a6e92) 
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  * @(#)expr.c	8.2 (Berkeley) 4/29/95
40  * $OpenBSD: expr.c,v 1.14 2002/04/26 16:15:16 espie Exp $
41  * $FreeBSD: src/usr.bin/m4/expr.c,v 1.3.12.1 2002/07/15 02:06:15 jmallett Exp $
42  * $DragonFly: src/usr.bin/m4/expr.c,v 1.3 2004/07/27 21:03:51 dillon Exp $
43  */
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 
107 static const char *nxtch;		       /* Parser scan pointer */
108 static const char *where;
109 
110 static int query(void);
111 static int lor(void);
112 static int land(void);
113 static int not(void);
114 static int eqrel(void);
115 static int shift(void);
116 static int primary(void);
117 static int term(void);
118 static int expx(void);
119 static int unary(void);
120 static int factor(void);
121 static int constant(void);
122 static int num(void);
123 static int geteqrel(void);
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();
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(void)
164 {
165 	int result, true_val, false_val;
166 
167 	result = lor();
168 	if (skipws() != '?') {
169 		ungetch();
170 		return result;
171 	}
172 
173 	true_val = query();
174 	if (skipws() != ':')
175 		experr("bad query");
176 
177 	false_val = query();
178 	return result ? true_val : false_val;
179 }
180 
181 /*
182  * lor : land { '||' land }
183  */
184 static int
185 lor(void)
186 {
187 	int c, vl, vr;
188 
189 	vl = land();
190 	while ((c = skipws()) == '|') {
191 		if (getch() != '|')
192 			ungetch();
193 		vr = land();
194 		vl = vl || vr;
195 	}
196 
197 	ungetch();
198 	return vl;
199 }
200 
201 /*
202  * land : not { '&&' not }
203  */
204 static int
205 land(void)
206 {
207 	int c, vl, vr;
208 
209 	vl = not();
210 	while ((c = skipws()) == '&') {
211 		if (getch() != '&')
212 			ungetch();
213 		vr = not();
214 		vl = vl && vr;
215 	}
216 
217 	ungetch();
218 	return vl;
219 }
220 
221 /*
222  * not : eqrel | '!' not
223  */
224 static int
225 not(void)
226 {
227 	int val, c;
228 
229 	if ((c = skipws()) == '!' && getch() != '=') {
230 		ungetch();
231 		val = not();
232 		return !val;
233 	}
234 
235 	if (c == '!')
236 		ungetch();
237 	ungetch();
238 	return eqrel();
239 }
240 
241 /*
242  * eqrel : shift { eqrelop shift }
243  */
244 static int
245 eqrel(void)
246 {
247 	int vl, vr, op;
248 
249 	vl = shift();
250 	while ((op = geteqrel()) != -1) {
251 		vr = shift();
252 
253 		switch (op) {
254 
255 		case EQL:
256 			vl = (vl == vr);
257 			break;
258 		case NEQ:
259 			vl = (vl != vr);
260 			break;
261 
262 		case LEQ:
263 			vl = (vl <= vr);
264 			break;
265 		case LSS:
266 			vl = (vl < vr);
267 			break;
268 		case GTR:
269 			vl = (vl > vr);
270 			break;
271 		case GEQ:
272 			vl = (vl >= vr);
273 			break;
274 		}
275 	}
276 	return vl;
277 }
278 
279 /*
280  * shift : primary { shop primary }
281  */
282 static int
283 shift(void)
284 {
285 	int vl, vr, c;
286 
287 	vl = primary();
288 	while (((c = skipws()) == '<' || c == '>') && getch() == c) {
289 		vr = primary();
290 
291 		if (c == '<')
292 			vl <<= vr;
293 		else
294 			vl >>= vr;
295 	}
296 
297 	if (c == '<' || c == '>')
298 		ungetch();
299 	ungetch();
300 	return vl;
301 }
302 
303 /*
304  * primary : term { addop term }
305  */
306 static int
307 primary(void)
308 {
309 	int c, vl, vr;
310 
311 	vl = term();
312 	while ((c = skipws()) == '+' || c == '-') {
313 		vr = term();
314 
315 		if (c == '+')
316 			vl += vr;
317 		else
318 			vl -= vr;
319 	}
320 
321 	ungetch();
322 	return vl;
323 }
324 
325 /*
326  * <term> := <exp> { <mulop> <exp> }
327  */
328 static int
329 term(void)
330 {
331 	int c, vl, vr;
332 
333 	vl = expx();
334 	while ((c = skipws()) == '*' || c == '/' || c == '%') {
335 		vr = expx();
336 
337 		switch (c) {
338 		case '*':
339 			vl *= vr;
340 			break;
341 		case '/':
342 			if (vr == 0)
343 				errx(1, "division by zero in eval.");
344 			else
345 				vl /= vr;
346 			break;
347 		case '%':
348 			if (vr == 0)
349 				errx(1, "modulo zero in eval.");
350 			else
351 				vl %= vr;
352 			break;
353 		}
354 	}
355 	ungetch();
356 	return vl;
357 }
358 
359 /*
360  * <term> := <unary> { <expop> <unary> }
361  */
362 static int
363 expx(void)
364 {
365 	int c, vl, vr, n;
366 
367 	vl = unary();
368 	switch (c = skipws()) {
369 
370 	case '*':
371 		if (getch() != '*') {
372 			ungetch();
373 			break;
374 		}
375 
376 	case '^':
377 		vr = expx();
378 		n = 1;
379 		while (vr-- > 0)
380 			n *= vl;
381 		return n;
382 	}
383 
384 	ungetch();
385 	return vl;
386 }
387 
388 /*
389  * unary : factor | unop unary
390  */
391 static int
392 unary(void)
393 {
394 	int val, c;
395 
396 	if ((c = skipws()) == '+' || c == '-' || c == '~') {
397 		val = unary();
398 
399 		switch (c) {
400 		case '+':
401 			return val;
402 		case '-':
403 			return -val;
404 		case '~':
405 			return ~val;
406 		}
407 	}
408 
409 	ungetch();
410 	return factor();
411 }
412 
413 /*
414  * factor : constant | '(' query ')'
415  */
416 static int
417 factor(void)
418 {
419 	int val;
420 
421 	if (skipws() == '(') {
422 		val = query();
423 		if (skipws() != ')')
424 			experr("bad factor");
425 		return val;
426 	}
427 
428 	ungetch();
429 	return constant();
430 }
431 
432 /*
433  * constant: num | 'char'
434  * Note: constant() handles multi-byte constants
435  */
436 static int
437 constant(void)
438 {
439 	int i;
440 	int value;
441 	int c;
442 	int v[sizeof(int)];
443 
444 	if (skipws() != '\'') {
445 		ungetch();
446 		return num();
447 	}
448 	for (i = 0; i < (int)sizeof(int); i++) {
449 		if ((c = getch()) == '\'') {
450 			ungetch();
451 			break;
452 		}
453 		if (c == '\\') {
454 			switch (c = getch()) {
455 			case '0':
456 			case '1':
457 			case '2':
458 			case '3':
459 			case '4':
460 			case '5':
461 			case '6':
462 			case '7':
463 				ungetch();
464 				c = num();
465 				break;
466 			case 'n':
467 				c = 012;
468 				break;
469 			case 'r':
470 				c = 015;
471 				break;
472 			case 't':
473 				c = 011;
474 				break;
475 			case 'b':
476 				c = 010;
477 				break;
478 			case 'f':
479 				c = 014;
480 				break;
481 			}
482 		}
483 		v[i] = c;
484 	}
485 	if (i == 0 || getch() != '\'')
486 		experr("illegal character constant");
487 	for (value = 0; --i >= 0;) {
488 		value <<= 8;
489 		value += v[i];
490 	}
491 	return value;
492 }
493 
494 /*
495  * num : digit | num digit
496  */
497 static int
498 num(void)
499 {
500 	int rval, c, base;
501 	int ndig;
502 
503 	rval = 0;
504 	ndig = 0;
505 	c = skipws();
506 	if (c == '0') {
507 		c = skipws();
508 		if (c == 'x' || c == 'X') {
509 			base = HEX;
510 			c = skipws();
511 		} else {
512 			base = OCTAL;
513 			ndig++;
514 		}
515 	} else
516 		base = DECIMAL;
517 	for(;;) {
518 		switch(c) {
519 			case '8': case '9':
520 				if (base == OCTAL)
521 					goto bad_digit;
522 				/*FALLTHRU*/
523 			case '0': case '1': case '2': case '3':
524 			case '4': case '5': case '6': case '7':
525 				rval *= base;
526 				rval += c - '0';
527 				break;
528 			case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
529 				c = tolower(c);
530 			case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
531 				if (base == HEX) {
532 					rval *= base;
533 					rval += c - 'a' + 10;
534 					break;
535 				}
536 				/*FALLTHRU*/
537 			default:
538 				goto bad_digit;
539 		}
540 		c = getch();
541 		ndig++;
542 	}
543 bad_digit:
544 	ungetch();
545 
546 	if (ndig == 0)
547 		experr("bad constant");
548 
549 	return rval;
550 }
551 
552 /*
553  * eqrel : '=' | '==' | '!=' | '<' | '>' | '<=' | '>='
554  */
555 static int
556 geteqrel(void)
557 {
558 	int c1, c2;
559 
560 	c1 = skipws();
561 	c2 = getch();
562 
563 	switch (c1) {
564 
565 	case '=':
566 		if (c2 != '=')
567 			ungetch();
568 		return EQL;
569 
570 	case '!':
571 		if (c2 == '=')
572 			return NEQ;
573 		ungetch();
574 		ungetch();
575 		return -1;
576 
577 	case '<':
578 		if (c2 == '=')
579 			return LEQ;
580 		ungetch();
581 		return LSS;
582 
583 	case '>':
584 		if (c2 == '=')
585 			return GEQ;
586 		ungetch();
587 		return GTR;
588 
589 	default:
590 		ungetch();
591 		ungetch();
592 		return -1;
593 	}
594 }
595 
596 /*
597  * Skip over any white space and return terminating char.
598  */
599 static int
600 skipws(void)
601 {
602 	int c;
603 
604 	while ((c = getch()) <= ' ' && c > EOS)
605 		;
606 	return c;
607 }
608 
609 /*
610  * resets environment to eval(), prints an error
611  * and forces eval to return FALSE.
612  */
613 static void
614 experr(const char *msg)
615 {
616 	printf("m4: %s in expr %s.\n", msg, where);
617 	longjmp(expjump, -1);
618 }
619