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