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