usr.bin/m4/expr.c

   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 }