expr.c

   1 /* expr.c -- arithmetic expression evaluation. */
   2
   3 /* Copyright (C) 1990-2015 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 /*
  22  All arithmetic is done as intmax_t integers with no checking for overflow
  23  (though division by 0 is caught and flagged as an error).
  24
  25  The following operators are handled, grouped into a set of levels in
  26  order of decreasing precedence.
  27
  28         "id++", "id--"          [post-increment and post-decrement]
  29         "++id", "--id"          [pre-increment and pre-decrement]
  30         "-", "+"                [(unary operators)]
  31         "!", "~"
  32         "**"                    [(exponentiation)]
  33         "*", "/", "%"
  34         "+", "-"
  35         "<<", ">>"
  36         "<=", ">=", "<", ">"
  37         "==", "!="
  38         "&"
  39         "^"
  40         "|"
  41         "&&"
  42         "||"
  43         "expr ? expr : expr"
  44         "=", "*=", "/=", "%=", "+=", "-=", "<<=", ">>=", "&=", "^=", "|="
  45         ,                       [comma]
  46
  47  (Note that most of these operators have special meaning to bash, and an
  48  entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
  49  that it is passed intact to the evaluator when using `let'.  When using
  50  the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
  51  is treated as if in double quotes.)
  52
  53  Sub-expressions within parentheses have a precedence level greater than
  54  all of the above levels and are evaluated first.  Within a single prece-
  55  dence group, evaluation is left-to-right, except for the arithmetic
  56  assignment operator (`='), which is evaluated right-to-left (as in C).
  57
  58  The expression evaluator returns the value of the expression (assignment
  59  statements have as a value what is returned by the RHS).  The `let'
  60  builtin, on the other hand, returns 0 if the last expression evaluates to
  61  a non-zero, and 1 otherwise.
  62
  63  Implementation is a recursive-descent parser.
  64
  65  Chet Ramey
  66  chet@po.cwru.edu
  67 */
  68
  69 #include "config.h"
  70
  71 #include <stdio.h>
  72 #include "bashansi.h"
  73
  74 #if defined (HAVE_UNISTD_H)
  75 #  ifdef _MINIX
  76 #    include <sys/types.h>
  77 #  endif
  78 #  include <unistd.h>
  79 #endif
  80
  81 #include "chartypes.h"
  82 #include "bashintl.h"
  83
  84 #include "shell.h"
  85 #include "typemax.h"            /* INTMAX_MAX, INTMAX_MIN */
  86
  87 /* Because of the $((...)) construct, expressions may include newlines.
  88    Here is a macro which accepts newlines, tabs and spaces as whitespace. */
  89 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
  90
  91 /* Size be which the expression stack grows when necessary. */
  92 #define EXPR_STACK_GROW_SIZE 10
  93
  94 /* Maximum amount of recursion allowed.  This prevents a non-integer
  95    variable such as "num=num+2" from infinitely adding to itself when
  96    "let num=num+2" is given. */
  97 #define MAX_EXPR_RECURSION_LEVEL 1024
  98
  99 /* The Tokens.  Singing "The Lion Sleeps Tonight". */
 100
 101 #define EQEQ    1       /* "==" */
 102 #define NEQ     2       /* "!=" */
 103 #define LEQ     3       /* "<=" */
 104 #define GEQ     4       /* ">=" */
 105 #define STR     5       /* string */
 106 #define NUM     6       /* number */
 107 #define LAND    7       /* "&&" Logical AND */
 108 #define LOR     8       /* "||" Logical OR */
 109 #define LSH     9       /* "<<" Left SHift */
 110 #define RSH    10       /* ">>" Right SHift */
 111 #define OP_ASSIGN 11    /* op= expassign as in Posix.2 */
 112 #define COND    12      /* exp1 ? exp2 : exp3 */
 113 #define POWER   13      /* exp1**exp2 */
 114 #define PREINC  14      /* ++var */
 115 #define PREDEC  15      /* --var */
 116 #define POSTINC 16      /* var++ */
 117 #define POSTDEC 17      /* var-- */
 118 #define EQ      '='
 119 #define GT      '>'
 120 #define LT      '<'
 121 #define PLUS    '+'
 122 #define MINUS   '-'
 123 #define MUL     '*'
 124 #define DIV     '/'
 125 #define MOD     '%'
 126 #define NOT     '!'
 127 #define LPAR    '('
 128 #define RPAR    ')'
 129 #define BAND    '&'     /* Bitwise AND */
 130 #define BOR     '|'     /* Bitwise OR. */
 131 #define BXOR    '^'     /* Bitwise eXclusive OR. */
 132 #define BNOT    '~'     /* Bitwise NOT; Two's complement. */
 133 #define QUES    '?'
 134 #define COL     ':'
 135 #define COMMA   ','
 136
 137 /* This should be the function corresponding to the operator with the
 138    highest precedence. */
 139 #define EXP_HIGHEST     expcomma
 140
 141 #ifndef MAX_INT_LEN
 142 #  define MAX_INT_LEN 32
 143 #endif
 144
 145 struct lvalue
 146 {
 147   char *tokstr;         /* possibly-rewritten lvalue if not NULL */
 148   intmax_t tokval;      /* expression evaluated value */
 149   SHELL_VAR *tokvar;    /* variable described by array or var reference */
 150   intmax_t ind;         /* array index if not -1 */
 151 };
 152
 153 /* A structure defining a single expression context. */
 154 typedef struct {
 155   int curtok, lasttok;
 156   char *expression, *tp, *lasttp;
 157   intmax_t tokval;
 158   char *tokstr;
 159   int noeval;
 160   struct lvalue lval;
 161 } EXPR_CONTEXT;
 162
 163 static char     *expression;    /* The current expression */
 164 static char     *tp;            /* token lexical position */
 165 static char     *lasttp;        /* pointer to last token position */
 166 static int      curtok;         /* the current token */
 167 static int      lasttok;        /* the previous token */
 168 static int      assigntok;      /* the OP in OP= */
 169 static char     *tokstr;        /* current token string */
 170 static intmax_t tokval;         /* current token value */
 171 static int      noeval;         /* set to 1 if no assignment to be done */
 172 static procenv_t evalbuf;
 173
 174 static struct lvalue curlval = {0, 0, 0, -1};
 175 static struct lvalue lastlval = {0, 0, 0, -1};
 176
 177 static int      _is_arithop __P((int));
 178 static void     readtok __P((void));    /* lexical analyzer */
 179
 180 static void     init_lvalue __P((struct lvalue *));
 181 static struct lvalue *alloc_lvalue __P((void));
 182 static void     free_lvalue __P((struct lvalue *));
 183
 184 static intmax_t expr_streval __P((char *, int, struct lvalue *));
 185 static intmax_t strlong __P((char *));
 186 static void     evalerror __P((const char *));
 187
 188 static void     pushexp __P((void));
 189 static void     popexp __P((void));
 190 static void     expr_unwind __P((void));
 191 static void     expr_bind_variable __P((char *, char *));
 192 #if defined (ARRAY_VARS)
 193 static void     expr_bind_array_element __P((char *, arrayind_t, char *));
 194 #endif
 195
 196 static intmax_t subexpr __P((char *));
 197
 198 static intmax_t expcomma __P((void));
 199 static intmax_t expassign __P((void));
 200 static intmax_t expcond __P((void));
 201 static intmax_t explor __P((void));
 202 static intmax_t expland __P((void));
 203 static intmax_t expbor __P((void));
 204 static intmax_t expbxor __P((void));
 205 static intmax_t expband __P((void));
 206 static intmax_t exp5 __P((void));
 207 static intmax_t exp4 __P((void));
 208 static intmax_t expshift __P((void));
 209 static intmax_t exp3 __P((void));
 210 static intmax_t exp2 __P((void));
 211 static intmax_t exppower __P((void));
 212 static intmax_t exp1 __P((void));
 213 static intmax_t exp0 __P((void));
 214
 215 /* Global var which contains the stack of expression contexts. */
 216 static EXPR_CONTEXT **expr_stack;
 217 static int expr_depth;             /* Location in the stack. */
 218 static int expr_stack_size;        /* Number of slots already allocated. */
 219
 220 extern char *this_command_name;
 221 extern int unbound_vars_is_error, last_command_exit_value;
 222
 223 #if defined (ARRAY_VARS)
 224 extern const char * const bash_badsub_errmsg;
 225 #endif
 226
 227 #define SAVETOK(X) \
 228   do { \
 229     (X)->curtok = curtok; \
 230     (X)->lasttok = lasttok; \
 231     (X)->tp = tp; \
 232     (X)->lasttp = lasttp; \
 233     (X)->tokval = tokval; \
 234     (X)->tokstr = tokstr; \
 235     (X)->noeval = noeval; \
 236     (X)->lval = curlval; \
 237   } while (0)
 238
 239 #define RESTORETOK(X) \
 240   do { \
 241     curtok = (X)->curtok; \
 242     lasttok = (X)->lasttok; \
 243     tp = (X)->tp; \
 244     lasttp = (X)->lasttp; \
 245     tokval = (X)->tokval; \
 246     tokstr = (X)->tokstr; \
 247     noeval = (X)->noeval; \
 248     curlval = (X)->lval; \
 249   } while (0)
 250
 251 /* Push and save away the contents of the globals describing the
 252    current expression context. */
 253 static void
 254 pushexp ()
 255 {
 256   EXPR_CONTEXT *context;
 257
 258   if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
 259     evalerror (_("expression recursion level exceeded"));
 260
 261   if (expr_depth >= expr_stack_size)
 262     {
 263       expr_stack_size += EXPR_STACK_GROW_SIZE;
 264       expr_stack = (EXPR_CONTEXT **)xrealloc (expr_stack, expr_stack_size * sizeof (EXPR_CONTEXT *));
 265     }
 266
 267   context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
 268
 269   context->expression = expression;
 270   SAVETOK(context);
 271
 272   expr_stack[expr_depth++] = context;
 273 }
 274
 275 /* Pop the the contents of the expression context stack into the
 276    globals describing the current expression context. */
 277 static void
 278 popexp ()
 279 {
 280   EXPR_CONTEXT *context;
 281
 282   if (expr_depth == 0)
 283     evalerror (_("recursion stack underflow"));
 284
 285   context = expr_stack[--expr_depth];
 286
 287   expression = context->expression;
 288   RESTORETOK (context);
 289
 290   free (context);
 291 }
 292
 293 static void
 294 expr_unwind ()
 295 {
 296   while (--expr_depth > 0)
 297     {
 298       if (expr_stack[expr_depth]->tokstr)
 299         free (expr_stack[expr_depth]->tokstr);
 300
 301       if (expr_stack[expr_depth]->expression)
 302         free (expr_stack[expr_depth]->expression);
 303
 304       free (expr_stack[expr_depth]);
 305     }
 306   free (expr_stack[expr_depth]);        /* free the allocated EXPR_CONTEXT */
 307
 308   noeval = 0;   /* XXX */
 309 }
 310
 311 static void
 312 expr_bind_variable (lhs, rhs)
 313      char *lhs, *rhs;
 314 {
 315   SHELL_VAR *v;
 316
 317   v = bind_int_variable (lhs, rhs);
 318   if (v && (readonly_p (v) || noassign_p (v)))
 319     sh_longjmp (evalbuf, 1);    /* variable assignment error */
 320   stupidly_hack_special_variables (lhs);
 321 }
 322
 323 #if defined (ARRAY_VARS)
 324 /* Rewrite tok, which is of the form vname[expression], to vname[ind], where
 325    IND is the already-calculated value of expression. */
 326 static void
 327 expr_bind_array_element (tok, ind, rhs)
 328      char *tok;
 329      arrayind_t ind;
 330      char *rhs;
 331 {
 332   char *lhs, *vname;
 333   size_t llen;
 334   char ibuf[INT_STRLEN_BOUND (arrayind_t) + 1], *istr;
 335
 336   istr = fmtumax (ind, 10, ibuf, sizeof (ibuf), 0);
 337   vname = array_variable_name (tok, (char **)NULL, (int *)NULL);
 338
 339   llen = strlen (vname) + sizeof (ibuf) + 3;
 340   lhs = xmalloc (llen);
 341
 342   sprintf (lhs, "%s[%s]", vname, istr);         /* XXX */
 343
 344 /*itrace("expr_bind_array_element: %s=%s", lhs, rhs);*/
 345   expr_bind_variable (lhs, rhs);
 346   free (vname);
 347   free (lhs);
 348 }
 349 #endif /* ARRAY_VARS */
 350
 351 /* Evaluate EXPR, and return the arithmetic result.  If VALIDP is
 352    non-null, a zero is stored into the location to which it points
 353    if the expression is invalid, non-zero otherwise.  If a non-zero
 354    value is returned in *VALIDP, the return value of evalexp() may
 355    be used.
 356
 357    The `while' loop after the longjmp is caught relies on the above
 358    implementation of pushexp and popexp leaving in expr_stack[0] the
 359    values that the variables had when the program started.  That is,
 360    the first things saved are the initial values of the variables that
 361    were assigned at program startup or by the compiler.  Therefore, it is
 362    safe to let the loop terminate when expr_depth == 0, without freeing up
 363    any of the expr_depth[0] stuff. */
 364 intmax_t
 365 evalexp (expr, validp)
 366      char *expr;
 367      int *validp;
 368 {
 369   intmax_t val;
 370   int c;
 371   procenv_t oevalbuf;
 372
 373   val = 0;
 374   noeval = 0;
 375
 376   FASTCOPY (evalbuf, oevalbuf, sizeof (evalbuf));
 377
 378   c = setjmp_nosigs (evalbuf);
 379
 380   if (c)
 381     {
 382       FREE (tokstr);
 383       FREE (expression);
 384       tokstr = expression = (char *)NULL;
 385
 386       expr_unwind ();
 387
 388       if (validp)
 389         *validp = 0;
 390       return (0);
 391     }
 392
 393   val = subexpr (expr);
 394
 395   if (validp)
 396     *validp = 1;
 397
 398   FASTCOPY (oevalbuf, evalbuf, sizeof (evalbuf));
 399
 400   return (val);
 401 }
 402
 403 static intmax_t
 404 subexpr (expr)
 405      char *expr;
 406 {
 407   intmax_t val;
 408   char *p;
 409
 410   for (p = expr; p && *p && cr_whitespace (*p); p++)
 411     ;
 412
 413   if (p == NULL || *p == '\0')
 414     return (0);
 415
 416   pushexp ();
 417   expression = savestring (expr);
 418   tp = expression;
 419
 420   curtok = lasttok = 0;
 421   tokstr = (char *)NULL;
 422   tokval = 0;
 423   init_lvalue (&curlval);
 424   lastlval = curlval;
 425
 426   readtok ();
 427
 428   val = EXP_HIGHEST ();
 429
 430   if (curtok != 0)
 431     evalerror (_("syntax error in expression"));
 432
 433   FREE (tokstr);
 434   FREE (expression);
 435
 436   popexp ();
 437
 438   return val;
 439 }
 440
 441 static intmax_t
 442 expcomma ()
 443 {
 444   register intmax_t value;
 445
 446   value = expassign ();
 447   while (curtok == COMMA)
 448     {
 449       readtok ();
 450       value = expassign ();
 451     }
 452
 453   return value;
 454 }
 455
 456 static intmax_t
 457 expassign ()
 458 {
 459   register intmax_t value;
 460   char *lhs, *rhs;
 461   arrayind_t lind;
 462 #if defined (HAVE_IMAXDIV)
 463   imaxdiv_t idiv;
 464 #endif
 465
 466   value = expcond ();
 467   if (curtok == EQ || curtok == OP_ASSIGN)
 468     {
 469       int special, op;
 470       intmax_t lvalue;
 471
 472       special = curtok == OP_ASSIGN;
 473
 474       if (lasttok != STR)
 475         evalerror (_("attempted assignment to non-variable"));
 476
 477       if (special)
 478         {
 479           op = assigntok;               /* a OP= b */
 480           lvalue = value;
 481         }
 482
 483       /* XXX - watch out for pointer aliasing issues here */
 484       lhs = savestring (tokstr);
 485       /* save ind in case rhs is string var and evaluation overwrites it */
 486       lind = curlval.ind;
 487       readtok ();
 488       value = expassign ();
 489
 490       if (special)
 491         {
 492           if ((op == DIV || op == MOD) && value == 0)
 493             {
 494               if (noeval == 0)
 495                 evalerror (_("division by 0"));
 496               else
 497                 value = 1;
 498             }
 499
 500           switch (op)
 501             {
 502             case MUL:
 503               lvalue *= value;
 504               break;
 505             case DIV:
 506             case MOD:
 507               if (lvalue == INTMAX_MIN && value == -1)
 508                 lvalue = (op == DIV) ? INTMAX_MIN : 0;
 509               else
 510 #if HAVE_IMAXDIV
 511                 {
 512                   idiv = imaxdiv (lvalue, value);
 513                   lvalue = (op == DIV) ? idiv.quot : idiv.rem;
 514                 }
 515 #else
 516                 lvalue = (op == DIV) ? lvalue / value : lvalue % value;
 517 #endif
 518               break;
 519             case PLUS:
 520               lvalue += value;
 521               break;
 522             case MINUS:
 523               lvalue -= value;
 524               break;
 525             case LSH:
 526               lvalue <<= value;
 527               break;
 528             case RSH:
 529               lvalue >>= value;
 530               break;
 531             case BAND:
 532               lvalue &= value;
 533               break;
 534             case BOR:
 535               lvalue |= value;
 536               break;
 537             case BXOR:
 538               lvalue ^= value;
 539               break;
 540             default:
 541               free (lhs);
 542               evalerror (_("bug: bad expassign token"));
 543               break;
 544             }
 545           value = lvalue;
 546         }
 547
 548       rhs = itos (value);
 549       if (noeval == 0)
 550         {
 551 #if defined (ARRAY_VARS)
 552           if (lind != -1)
 553             expr_bind_array_element (lhs, lind, rhs);
 554           else
 555 #endif
 556             expr_bind_variable (lhs, rhs);
 557         }
 558       if (curlval.tokstr && curlval.tokstr == tokstr)
 559         init_lvalue (&curlval);
 560
 561       free (rhs);
 562       free (lhs);
 563       FREE (tokstr);
 564       tokstr = (char *)NULL;            /* For freeing on errors. */
 565     }
 566
 567   return (value);
 568 }
 569
 570 /* Conditional expression (expr?expr:expr) */
 571 static intmax_t
 572 expcond ()
 573 {
 574   intmax_t cval, val1, val2, rval;
 575   int set_noeval;
 576
 577   set_noeval = 0;
 578   rval = cval = explor ();
 579   if (curtok == QUES)           /* found conditional expr */
 580     {
 581       if (cval == 0)
 582         {
 583           set_noeval = 1;
 584           noeval++;
 585         }
 586
 587       readtok ();
 588       if (curtok == 0 || curtok == COL)
 589         evalerror (_("expression expected"));
 590
 591       val1 = EXP_HIGHEST ();
 592
 593       if (set_noeval)
 594         noeval--;
 595       if (curtok != COL)
 596         evalerror (_("`:' expected for conditional expression"));
 597
 598       set_noeval = 0;
 599       if (cval)
 600         {
 601           set_noeval = 1;
 602           noeval++;
 603         }
 604
 605       readtok ();
 606       if (curtok == 0)
 607         evalerror (_("expression expected"));
 608       val2 = expcond ();
 609
 610       if (set_noeval)
 611         noeval--;
 612       rval = cval ? val1 : val2;
 613       lasttok = COND;
 614     }
 615   return rval;
 616 }
 617
 618 /* Logical OR. */
 619 static intmax_t
 620 explor ()
 621 {
 622   register intmax_t val1, val2;
 623   int set_noeval;
 624
 625   val1 = expland ();
 626
 627   while (curtok == LOR)
 628     {
 629       set_noeval = 0;
 630       if (val1 != 0)
 631         {
 632           noeval++;
 633           set_noeval = 1;
 634         }
 635       readtok ();
 636       val2 = expland ();
 637       if (set_noeval)
 638         noeval--;
 639       val1 = val1 || val2;
 640       lasttok = LOR;
 641     }
 642
 643   return (val1);
 644 }
 645
 646 /* Logical AND. */
 647 static intmax_t
 648 expland ()
 649 {
 650   register intmax_t val1, val2;
 651   int set_noeval;
 652
 653   val1 = expbor ();
 654
 655   while (curtok == LAND)
 656     {
 657       set_noeval = 0;
 658       if (val1 == 0)
 659         {
 660           set_noeval = 1;
 661           noeval++;
 662         }
 663       readtok ();
 664       val2 = expbor ();
 665       if (set_noeval)
 666         noeval--;
 667       val1 = val1 && val2;
 668       lasttok = LAND;
 669     }
 670
 671   return (val1);
 672 }
 673
 674 /* Bitwise OR. */
 675 static intmax_t
 676 expbor ()
 677 {
 678   register intmax_t val1, val2;
 679
 680   val1 = expbxor ();
 681
 682   while (curtok == BOR)
 683     {
 684       readtok ();
 685       val2 = expbxor ();
 686       val1 = val1 | val2;
 687       lasttok = NUM;
 688     }
 689
 690   return (val1);
 691 }
 692
 693 /* Bitwise XOR. */
 694 static intmax_t
 695 expbxor ()
 696 {
 697   register intmax_t val1, val2;
 698
 699   val1 = expband ();
 700
 701   while (curtok == BXOR)
 702     {
 703       readtok ();
 704       val2 = expband ();
 705       val1 = val1 ^ val2;
 706       lasttok = NUM;
 707     }
 708
 709   return (val1);
 710 }
 711
 712 /* Bitwise AND. */
 713 static intmax_t
 714 expband ()
 715 {
 716   register intmax_t val1, val2;
 717
 718   val1 = exp5 ();
 719
 720   while (curtok == BAND)
 721     {
 722       readtok ();
 723       val2 = exp5 ();
 724       val1 = val1 & val2;
 725       lasttok = NUM;
 726     }
 727
 728   return (val1);
 729 }
 730
 731 static intmax_t
 732 exp5 ()
 733 {
 734   register intmax_t val1, val2;
 735
 736   val1 = exp4 ();
 737
 738   while ((curtok == EQEQ) || (curtok == NEQ))
 739     {
 740       int op = curtok;
 741
 742       readtok ();
 743       val2 = exp4 ();
 744       if (op == EQEQ)
 745         val1 = (val1 == val2);
 746       else if (op == NEQ)
 747         val1 = (val1 != val2);
 748       lasttok = NUM;
 749     }
 750   return (val1);
 751 }
 752
 753 static intmax_t
 754 exp4 ()
 755 {
 756   register intmax_t val1, val2;
 757
 758   val1 = expshift ();
 759   while ((curtok == LEQ) ||
 760          (curtok == GEQ) ||
 761          (curtok == LT) ||
 762          (curtok == GT))
 763     {
 764       int op = curtok;
 765
 766       readtok ();
 767       val2 = expshift ();
 768
 769       if (op == LEQ)
 770         val1 = val1 <= val2;
 771       else if (op == GEQ)
 772         val1 = val1 >= val2;
 773       else if (op == LT)
 774         val1 = val1 < val2;
 775       else                      /* (op == GT) */
 776         val1 = val1 > val2;
 777       lasttok = NUM;
 778     }
 779   return (val1);
 780 }
 781
 782 /* Left and right shifts. */
 783 static intmax_t
 784 expshift ()
 785 {
 786   register intmax_t val1, val2;
 787
 788   val1 = exp3 ();
 789
 790   while ((curtok == LSH) || (curtok == RSH))
 791     {
 792       int op = curtok;
 793
 794       readtok ();
 795       val2 = exp3 ();
 796
 797       if (op == LSH)
 798         val1 = val1 << val2;
 799       else
 800         val1 = val1 >> val2;
 801       lasttok = NUM;
 802     }
 803
 804   return (val1);
 805 }
 806
 807 static intmax_t
 808 exp3 ()
 809 {
 810   register intmax_t val1, val2;
 811
 812   val1 = exp2 ();
 813
 814   while ((curtok == PLUS) || (curtok == MINUS))
 815     {
 816       int op = curtok;
 817
 818       readtok ();
 819       val2 = exp2 ();
 820
 821       if (op == PLUS)
 822         val1 += val2;
 823       else if (op == MINUS)
 824         val1 -= val2;
 825       lasttok = NUM;
 826     }
 827   return (val1);
 828 }
 829
 830 static intmax_t
 831 exp2 ()
 832 {
 833   register intmax_t val1, val2;
 834 #if defined (HAVE_IMAXDIV)
 835   imaxdiv_t idiv;
 836 #endif
 837
 838   val1 = exppower ();
 839
 840   while ((curtok == MUL) ||
 841          (curtok == DIV) ||
 842          (curtok == MOD))
 843     {
 844       int op = curtok;
 845       char *stp, *sltp;
 846
 847       stp = tp;
 848       readtok ();
 849
 850       val2 = exppower ();
 851
 852       /* Handle division by 0 and twos-complement arithmetic overflow */
 853       if (((op == DIV) || (op == MOD)) && (val2 == 0))
 854         {
 855           if (noeval == 0)
 856             {
 857               sltp = lasttp;
 858               lasttp = stp;
 859               while (lasttp && *lasttp && whitespace (*lasttp))
 860                 lasttp++;
 861               evalerror (_("division by 0"));
 862               lasttp = sltp;
 863             }
 864           else
 865             val2 = 1;
 866         }
 867       else if (op == MOD && val1 == INTMAX_MIN && val2 == -1)
 868         {
 869           val1 = 0;
 870           continue;
 871         }
 872       else if (op == DIV && val1 == INTMAX_MIN && val2 == -1)
 873         val2 = 1;
 874
 875       if (op == MUL)
 876         val1 *= val2;
 877       else if (op == DIV || op == MOD)
 878 #if defined (HAVE_IMAXDIV)
 879         {
 880           idiv = imaxdiv (val1, val2);
 881           val1 = (op == DIV) ? idiv.quot : idiv.rem;
 882         }
 883 #else
 884         val1 = (op == DIV) ? val1 / val2 : val1 % val2;
 885 #endif
 886       lasttok = NUM;
 887     }
 888   return (val1);
 889 }
 890
 891 static intmax_t
 892 ipow (base, exp)
 893      intmax_t base, exp;
 894 {
 895   intmax_t result;
 896
 897   result = 1;
 898   while (exp)
 899     {
 900       if (exp & 1)
 901         result *= base;
 902       exp >>= 1;
 903       base *= base;
 904     }
 905   return result;
 906 }
 907
 908 static intmax_t
 909 exppower ()
 910 {
 911   register intmax_t val1, val2, c;
 912
 913   val1 = exp1 ();
 914   while (curtok == POWER)
 915     {
 916       readtok ();
 917       val2 = exppower ();       /* exponentiation is right-associative */
 918       lasttok = NUM;
 919       if (val2 == 0)
 920         return (1);
 921       if (val2 < 0)
 922         evalerror (_("exponent less than 0"));
 923       val1 = ipow (val1, val2);
 924     }
 925   return (val1);
 926 }
 927
 928 static intmax_t
 929 exp1 ()
 930 {
 931   register intmax_t val;
 932
 933   if (curtok == NOT)
 934     {
 935       readtok ();
 936       val = !exp1 ();
 937       lasttok = NUM;
 938     }
 939   else if (curtok == BNOT)
 940     {
 941       readtok ();
 942       val = ~exp1 ();
 943       lasttok = NUM;
 944     }
 945   else if (curtok == MINUS)
 946     {
 947       readtok ();
 948       val = - exp1 ();
 949       lasttok = NUM;
 950     }
 951   else if (curtok == PLUS)
 952     {
 953       readtok ();
 954       val = exp1 ();
 955       lasttok = NUM;
 956     }
 957   else
 958     val = exp0 ();
 959
 960   return (val);
 961 }
 962
 963 static intmax_t
 964 exp0 ()
 965 {
 966   register intmax_t val = 0, v2;
 967   char *vincdec;
 968   int stok;
 969   EXPR_CONTEXT ec;
 970
 971   /* XXX - might need additional logic here to decide whether or not
 972            pre-increment or pre-decrement is legal at this point. */
 973   if (curtok == PREINC || curtok == PREDEC)
 974     {
 975       stok = lasttok = curtok;
 976       readtok ();
 977       if (curtok != STR)
 978         /* readtok() catches this */
 979         evalerror (_("identifier expected after pre-increment or pre-decrement"));
 980
 981       v2 = tokval + ((stok == PREINC) ? 1 : -1);
 982       vincdec = itos (v2);
 983       if (noeval == 0)
 984         {
 985 #if defined (ARRAY_VARS)
 986           if (curlval.ind != -1)
 987             expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
 988           else
 989 #endif
 990             expr_bind_variable (tokstr, vincdec);
 991         }
 992       free (vincdec);
 993       val = v2;
 994
 995       curtok = NUM;     /* make sure --x=7 is flagged as an error */
 996       readtok ();
 997     }
 998   else if (curtok == LPAR)
 999     {
1000       /* XXX - save curlval here?  Or entire expression context? */
1001       readtok ();
1002       val = EXP_HIGHEST ();
1003
1004       if (curtok != RPAR) /* ( */
1005         evalerror (_("missing `)'"));
1006
1007       /* Skip over closing paren. */
1008       readtok ();
1009     }
1010   else if ((curtok == NUM) || (curtok == STR))
1011     {
1012       val = tokval;
1013       if (curtok == STR)
1014         {
1015           SAVETOK (&ec);
1016           tokstr = (char *)NULL;        /* keep it from being freed */
1017           noeval = 1;
1018           readtok ();
1019           stok = curtok;
1020
1021           /* post-increment or post-decrement */
1022           if (stok == POSTINC || stok == POSTDEC)
1023             {
1024               /* restore certain portions of EC */
1025               tokstr = ec.tokstr;
1026               noeval = ec.noeval;
1027               curlval = ec.lval;
1028               lasttok = STR;    /* ec.curtok */
1029
1030               v2 = val + ((stok == POSTINC) ? 1 : -1);
1031               vincdec = itos (v2);
1032               if (noeval == 0)
1033                 {
1034 #if defined (ARRAY_VARS)
1035                   if (curlval.ind != -1)
1036                     expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
1037                   else
1038 #endif
1039                     expr_bind_variable (tokstr, vincdec);
1040                 }
1041               free (vincdec);
1042               curtok = NUM;     /* make sure x++=7 is flagged as an error */
1043             }
1044           else
1045             {
1046               /* XXX - watch out for pointer aliasing issues here */
1047               if (stok == STR)  /* free new tokstr before old one is restored */
1048                 FREE (tokstr);
1049               RESTORETOK (&ec);
1050             }
1051         }
1052
1053       readtok ();
1054     }
1055   else
1056     evalerror (_("syntax error: operand expected"));
1057
1058   return (val);
1059 }
1060
1061 static void
1062 init_lvalue (lv)
1063      struct lvalue *lv;
1064 {
1065   lv->tokstr = 0;
1066   lv->tokvar = 0;
1067   lv->tokval = lv->ind = -1;
1068 }
1069
1070 static struct lvalue *
1071 alloc_lvalue ()
1072 {
1073   struct lvalue *lv;
1074
1075   lv = xmalloc (sizeof (struct lvalue));
1076   init_lvalue (lv);
1077   return (lv);
1078 }
1079
1080 static void
1081 free_lvalue (lv)
1082      struct lvalue *lv;
1083 {
1084   free (lv);            /* should be inlined */
1085 }
1086
1087 static intmax_t
1088 expr_streval (tok, e, lvalue)
1089      char *tok;
1090      int e;
1091      struct lvalue *lvalue;
1092 {
1093   SHELL_VAR *v;
1094   char *value;
1095   intmax_t tval;
1096 #if defined (ARRAY_VARS)
1097   arrayind_t ind;
1098 #endif
1099
1100 /*itrace("expr_streval: %s: noeval = %d", tok, noeval);*/
1101   /* If we are suppressing evaluation, just short-circuit here instead of
1102      going through the rest of the evaluator. */
1103   if (noeval)
1104     return (0);
1105
1106   /* [[[[[ */
1107 #if defined (ARRAY_VARS)
1108   v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
1109 #else
1110   v = find_variable (tok);
1111 #endif
1112
1113   if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
1114     {
1115 #if defined (ARRAY_VARS)
1116       value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
1117 #else
1118       value = tok;
1119 #endif
1120
1121       last_command_exit_value = EXECUTION_FAILURE;
1122       err_unboundvar (value);
1123
1124 #if defined (ARRAY_VARS)
1125       if (e == ']')
1126         FREE (value);   /* array_variable_name returns new memory */
1127 #endif
1128
1129       if (no_longjmp_on_fatal_error && interactive_shell)
1130         sh_longjmp (evalbuf, 1);
1131
1132       if (interactive_shell)
1133         {
1134           expr_unwind ();
1135           top_level_cleanup ();
1136           jump_to_top_level (DISCARD);
1137         }
1138       else
1139         jump_to_top_level (FORCE_EOF);
1140     }
1141
1142 #if defined (ARRAY_VARS)
1143   ind = -1;
1144   /* Second argument of 0 to get_array_value means that we don't allow
1145      references like array[@].  In this case, get_array_value is just
1146      like get_variable_value in that it does not return newly-allocated
1147      memory or quote the results. */
1148   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL, &ind) : get_variable_value (v);
1149 #else
1150   value = get_variable_value (v);
1151 #endif
1152
1153   tval = (value && *value) ? subexpr (value) : 0;
1154
1155   if (lvalue)
1156     {
1157       lvalue->tokstr = tok;     /* XXX */
1158       lvalue->tokval = tval;
1159       lvalue->tokvar = v;       /* XXX */
1160 #if defined (ARRAY_VARS)
1161       lvalue->ind = ind;
1162 #else
1163       lvalue->ind = -1;
1164 #endif
1165     }
1166
1167   return (tval);
1168 }
1169
1170 static int
1171 _is_multiop (c)
1172      int c;
1173 {
1174   switch (c)
1175     {
1176     case EQEQ:
1177     case NEQ:
1178     case LEQ:
1179     case GEQ:
1180     case LAND:
1181     case LOR:
1182     case LSH:
1183     case RSH:
1184     case OP_ASSIGN:
1185     case COND:
1186     case POWER:
1187     case PREINC:
1188     case PREDEC:
1189     case POSTINC:
1190     case POSTDEC:
1191       return 1;
1192     default:
1193       return 0;
1194     }
1195 }
1196
1197 static int
1198 _is_arithop (c)
1199      int c;
1200 {
1201   switch (c)
1202     {
1203     case EQ:
1204     case GT:
1205     case LT:
1206     case PLUS:
1207     case MINUS:
1208     case MUL:
1209     case DIV:
1210     case MOD:
1211     case NOT:
1212     case LPAR:
1213     case RPAR:
1214     case BAND:
1215     case BOR:
1216     case BXOR:
1217     case BNOT:
1218       return 1;         /* operator tokens */
1219     case QUES:
1220     case COL:
1221     case COMMA:
1222       return 1;         /* questionable */
1223     default:
1224       return 0;         /* anything else is invalid */
1225     }
1226 }
1227
1228 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1229    next token and puts its value into curtok, while advancing past it.
1230    Updates value of tp.  May also set tokval (for number) or tokstr (for
1231    string). */
1232 static void
1233 readtok ()
1234 {
1235   register char *cp, *xp;
1236   register unsigned char c, c1;
1237   register int e;
1238   struct lvalue lval;
1239
1240   /* Skip leading whitespace. */
1241   cp = tp;
1242   c = e = 0;
1243   while (cp && (c = *cp) && (cr_whitespace (c)))
1244     cp++;
1245
1246   if (c)
1247     cp++;
1248
1249   if (c == '\0')
1250     {
1251       lasttok = curtok;
1252       curtok = 0;
1253       tp = cp;
1254       return;
1255     }
1256   lasttp = tp = cp - 1;
1257
1258   if (legal_variable_starter (c))
1259     {
1260       /* variable names not preceded with a dollar sign are shell variables. */
1261       char *savecp;
1262       EXPR_CONTEXT ec;
1263       int peektok;
1264
1265       while (legal_variable_char (c))
1266         c = *cp++;
1267
1268       c = *--cp;
1269
1270 #if defined (ARRAY_VARS)
1271       if (c == '[')
1272         {
1273           e = skipsubscript (cp, 0, 0);
1274           if (cp[e] == ']')
1275             {
1276               cp += e + 1;
1277               c = *cp;
1278               e = ']';
1279             }
1280           else
1281             evalerror (bash_badsub_errmsg);
1282         }
1283 #endif /* ARRAY_VARS */
1284
1285       *cp = '\0';
1286       /* XXX - watch out for pointer aliasing issues here */
1287       if (curlval.tokstr && curlval.tokstr == tokstr)
1288         init_lvalue (&curlval);
1289
1290       FREE (tokstr);
1291       tokstr = savestring (tp);
1292       *cp = c;
1293
1294       /* XXX - make peektok part of saved token state? */
1295       SAVETOK (&ec);
1296       tokstr = (char *)NULL;    /* keep it from being freed */
1297       tp = savecp = cp;
1298       noeval = 1;
1299       curtok = STR;
1300       readtok ();
1301       peektok = curtok;
1302       if (peektok == STR)       /* free new tokstr before old one is restored */
1303         FREE (tokstr);
1304       RESTORETOK (&ec);
1305       cp = savecp;
1306
1307       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1308          preserve old behavior if a construct like --x=9 is given. */
1309       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1310         {
1311           lastlval = curlval;
1312           tokval = expr_streval (tokstr, e, &curlval);
1313         }
1314       else
1315         tokval = 0;
1316
1317       lasttok = curtok;
1318       curtok = STR;
1319     }
1320   else if (DIGIT(c))
1321     {
1322       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1323         c = *cp++;
1324
1325       c = *--cp;
1326       *cp = '\0';
1327
1328       tokval = strlong (tp);
1329       *cp = c;
1330       lasttok = curtok;
1331       curtok = NUM;
1332     }
1333   else
1334     {
1335       c1 = *cp++;
1336       if ((c == EQ) && (c1 == EQ))
1337         c = EQEQ;
1338       else if ((c == NOT) && (c1 == EQ))
1339         c = NEQ;
1340       else if ((c == GT) && (c1 == EQ))
1341         c = GEQ;
1342       else if ((c == LT) && (c1 == EQ))
1343         c = LEQ;
1344       else if ((c == LT) && (c1 == LT))
1345         {
1346           if (*cp == '=')       /* a <<= b */
1347             {
1348               assigntok = LSH;
1349               c = OP_ASSIGN;
1350               cp++;
1351             }
1352           else
1353             c = LSH;
1354         }
1355       else if ((c == GT) && (c1 == GT))
1356         {
1357           if (*cp == '=')
1358             {
1359               assigntok = RSH;  /* a >>= b */
1360               c = OP_ASSIGN;
1361               cp++;
1362             }
1363           else
1364             c = RSH;
1365         }
1366       else if ((c == BAND) && (c1 == BAND))
1367         c = LAND;
1368       else if ((c == BOR) && (c1 == BOR))
1369         c = LOR;
1370       else if ((c == '*') && (c1 == '*'))
1371         c = POWER;
1372       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1373         c = (c == '-') ? POSTDEC : POSTINC;
1374       else if ((c == '-' || c == '+') && c1 == c)
1375         {
1376           /* Quickly scan forward to see if this is followed by optional
1377              whitespace and an identifier. */
1378           xp = cp;
1379           while (xp && *xp && cr_whitespace (*xp))
1380             xp++;
1381           if (legal_variable_starter ((unsigned char)*xp))
1382             c = (c == '-') ? PREDEC : PREINC;
1383           else
1384             cp--;       /* not preinc or predec, so unget the character */
1385         }
1386       else if (c1 == EQ && member (c, "*/%+-&^|"))
1387         {
1388           assigntok = c;        /* a OP= b */
1389           c = OP_ASSIGN;
1390         }
1391       else if (_is_arithop (c) == 0)
1392         {
1393           cp--;
1394           /* use curtok, since it hasn't been copied to lasttok yet */
1395           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1396             evalerror (_("syntax error: operand expected"));
1397           else
1398             evalerror (_("syntax error: invalid arithmetic operator"));
1399         }
1400       else
1401         cp--;                   /* `unget' the character */
1402
1403       /* Should check here to make sure that the current character is one
1404          of the recognized operators and flag an error if not.  Could create
1405          a character map the first time through and check it on subsequent
1406          calls. */
1407       lasttok = curtok;
1408       curtok = c;
1409     }
1410   tp = cp;
1411 }
1412
1413 static void
1414 evalerror (msg)
1415      const char *msg;
1416 {
1417   char *name, *t;
1418
1419   name = this_command_name;
1420   for (t = expression; whitespace (*t); t++)
1421     ;
1422   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1423                    name ? name : "", name ? ": " : "", t,
1424                    msg, (lasttp && *lasttp) ? lasttp : "");
1425   sh_longjmp (evalbuf, 1);
1426 }
1427
1428 /* Convert a string to an intmax_t integer, with an arbitrary base.
1429    0nnn -> base 8
1430    0[Xx]nn -> base 16
1431    Anything else: [base#]number (this is implemented to match ksh93)
1432
1433    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1434    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1435    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1436    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1437    you get the picture). */
1438
1439 static intmax_t
1440 strlong (num)
1441      char *num;
1442 {
1443   register char *s;
1444   register unsigned char c;
1445   int base, foundbase;
1446   intmax_t val;
1447
1448   s = num;
1449
1450   base = 10;
1451   foundbase = 0;
1452   if (*s == '0')
1453     {
1454       s++;
1455
1456       if (*s == '\0')
1457         return 0;
1458
1459        /* Base 16? */
1460       if (*s == 'x' || *s == 'X')
1461         {
1462           base = 16;
1463           s++;
1464         }
1465       else
1466         base = 8;
1467       foundbase++;
1468     }
1469
1470   val = 0;
1471   for (c = *s++; c; c = *s++)
1472     {
1473       if (c == '#')
1474         {
1475           if (foundbase)
1476             evalerror (_("invalid number"));
1477
1478           /* Illegal base specifications raise an evaluation error. */
1479           if (val < 2 || val > 64)
1480             evalerror (_("invalid arithmetic base"));
1481
1482           base = val;
1483           val = 0;
1484           foundbase++;
1485         }
1486       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1487         {
1488           if (DIGIT(c))
1489             c = TODIGIT(c);
1490           else if (c >= 'a' && c <= 'z')
1491             c -= 'a' - 10;
1492           else if (c >= 'A' && c <= 'Z')
1493             c -= 'A' - ((base <= 36) ? 10 : 36);
1494           else if (c == '@')
1495             c = 62;
1496           else if (c == '_')
1497             c = 63;
1498
1499           if (c >= base)
1500             evalerror (_("value too great for base"));
1501
1502           val = (val * base) + c;
1503         }
1504       else
1505         break;
1506     }
1507
1508   return (val);
1509 }
1510
1511 #if defined (EXPR_TEST)
1512 void *
1513 xmalloc (n)
1514      int n;
1515 {
1516   return (malloc (n));
1517 }
1518
1519 void *
1520 xrealloc (s, n)
1521      char *s;
1522      int n;
1523 {
1524   return (realloc (s, n));
1525 }
1526
1527 SHELL_VAR *find_variable () { return 0;}
1528 SHELL_VAR *bind_variable () { return 0; }
1529
1530 char *get_string_value () { return 0; }
1531
1532 procenv_t top_level;
1533
1534 main (argc, argv)
1535      int argc;
1536      char **argv;
1537 {
1538   register int i;
1539   intmax_t v;
1540   int expok;
1541
1542   if (setjmp (top_level))
1543     exit (0);
1544
1545   for (i = 1; i < argc; i++)
1546     {
1547       v = evalexp (argv[i], &expok);
1548       if (expok == 0)
1549         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1550       else
1551         printf ("'%s' -> %ld\n", argv[i], v);
1552     }
1553   exit (0);
1554 }
1555
1556 int
1557 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1558      char *format;
1559 {
1560   fprintf (stderr, "expr: ");
1561   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1562   fprintf (stderr, "\n");
1563   return 0;
1564 }
1565
1566 char *
1567 itos (n)
1568      intmax_t n;
1569 {
1570   return ("42");
1571 }
1572
1573 #endif /* EXPR_TEST */