expr.c

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