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  * 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
  38 static char sccsid[] = "@(#)expr.c      8.2 (Berkeley) 4/29/95";
  39 #else
  40 #if 0
  41 static 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$");
  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
 104 static const char *nxtch;                      /* Parser scan pointer */
 105 static const char *where;
 106
 107 static int query(int mayeval);
 108 static int lor(int mayeval);
 109 static int land(int mayeval);
 110 static int bor(int mayeval);
 111 static int xor(int mayeval);
 112 static int band(int mayeval);
 113 static int eqrel(int mayeval);
 114 static int nerel(int mayeval);
 115 static int shift(int mayeval);
 116 static int primary(int mayeval);
 117 static int term(int mayeval);
 118 static int exp(int mayeval);
 119 static int unary(int mayeval);
 120 static int factor(int mayeval);
 121 static int constant(int mayeval);
 122 static int num(int mayeval);
 123 static int geteqrel(int mayeval);
 124 static int skipws(void);
 125 static void experr(const char *);
 126
 127 /*
 128  * For longjmp
 129  */
 130 #include <setjmp.h>
 131 static 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
 141 int
 142 expr(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  */
 162 static int
 163 query(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  */
 184 static int
 185 lor(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  */
 208 static int
 209 land(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  */
 232 static int
 233 bor(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  */
 253 static int
 254 xor(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  */
 270 static int
 271 band(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  */
 291 static int
 292 eqrel(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  */
 319 static int
 320 nerel(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  */
 347 static int
 348 shift(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  */
 371 static int
 372 primary(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  */
 393 static int
 394 term(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  */
 431 static int
 432 exp(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  */
 456 static int
 457 unary(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  */
 483 static int
 484 factor(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  */
 503 static int
 504 constant(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  */
 564 static int
 565 num(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         }
 610 bad_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  */
 622 static int
 623 skipws(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  */
 636 static void
 637 experr(const char *msg)
 638 {
 639         printf("m4: %s in expr %s.\n", msg, where);
 640         longjmp(expjump, -1);
 641 }