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