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