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