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