Home | History | Annotate | Line # | Download | only in m4
expr.c revision 1.18 
      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