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