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