expr.c revision 226422 
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
38static char sccsid[] = "@(#)expr.c	8.2 (Berkeley) 4/29/95";
39#else
40#if 0
41static 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: head/usr.bin/m4/expr.c 226422 2011-10-16 08:09:17Z ed $");
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
104static const char *nxtch;		       /* Parser scan pointer */
105static const char *where;
106
107static int query(int mayeval);
108static int lor(int mayeval);
109static int land(int mayeval);
110static int bor(int mayeval);
111static int xor(int mayeval);
112static int band(int mayeval);
113static int eqrel(int mayeval);
114static int nerel(int mayeval);
115static int shift(int mayeval);
116static int primary(int mayeval);
117static int term(int mayeval);
118static int exponent(int mayeval);
119static int unary(int mayeval);
120static int factor(int mayeval);
121static int constant(int mayeval);
122static int num(int mayeval);
123static int skipws(void);
124static void experr(const char *);
125
126/*
127 * For longjmp
128 */
129#include <setjmp.h>
130static 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
140int
141expr(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 */
161static int
162query(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 */
183static int
184lor(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 */
207static int
208land(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 */
231static int
232bor(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 */
252static int
253xor(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 */
269static int
270band(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 */
290static int
291eqrel(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 */
318static int
319nerel(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 */
346static int
347shift(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 */
370static int
371primary(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 */
392static int
393term(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 */
430static int
431exponent(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 */
455static int
456unary(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 */
482static int
483factor(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 */
502static int
503constant(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 */
563static int
564num(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	}
609bad_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 */
621static int
622skipws(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 */
635static void
636experr(const char *msg)
637{
638	printf("m4: %s in expr %s.\n", msg, where);
639	longjmp(expjump, -1);
640}
641