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 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 }