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