expr.c

   1 /* expr.c -- arithmetic expression evaluation. */
   2
   3 /* Copyright (C) 1990-2013 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     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       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       lasttok = NUM;
 685     }
 686
 687   return (val1);
 688 }
 689
 690 /* Bitwise XOR. */
 691 static intmax_t
 692 expbxor ()
 693 {
 694   register intmax_t val1, val2;
 695
 696   val1 = expband ();
 697
 698   while (curtok == BXOR)
 699     {
 700       readtok ();
 701       val2 = expband ();
 702       val1 = val1 ^ val2;
 703       lasttok = NUM;
 704     }
 705
 706   return (val1);
 707 }
 708
 709 /* Bitwise AND. */
 710 static intmax_t
 711 expband ()
 712 {
 713   register intmax_t val1, val2;
 714
 715   val1 = exp5 ();
 716
 717   while (curtok == BAND)
 718     {
 719       readtok ();
 720       val2 = exp5 ();
 721       val1 = val1 & val2;
 722       lasttok = NUM;
 723     }
 724
 725   return (val1);
 726 }
 727
 728 static intmax_t
 729 exp5 ()
 730 {
 731   register intmax_t val1, val2;
 732
 733   val1 = exp4 ();
 734
 735   while ((curtok == EQEQ) || (curtok == NEQ))
 736     {
 737       int op = curtok;
 738
 739       readtok ();
 740       val2 = exp4 ();
 741       if (op == EQEQ)
 742         val1 = (val1 == val2);
 743       else if (op == NEQ)
 744         val1 = (val1 != val2);
 745       lasttok = NUM;
 746     }
 747   return (val1);
 748 }
 749
 750 static intmax_t
 751 exp4 ()
 752 {
 753   register intmax_t val1, val2;
 754
 755   val1 = expshift ();
 756   while ((curtok == LEQ) ||
 757          (curtok == GEQ) ||
 758          (curtok == LT) ||
 759          (curtok == GT))
 760     {
 761       int op = curtok;
 762
 763       readtok ();
 764       val2 = expshift ();
 765
 766       if (op == LEQ)
 767         val1 = val1 <= val2;
 768       else if (op == GEQ)
 769         val1 = val1 >= val2;
 770       else if (op == LT)
 771         val1 = val1 < val2;
 772       else                      /* (op == GT) */
 773         val1 = val1 > val2;
 774       lasttok = NUM;
 775     }
 776   return (val1);
 777 }
 778
 779 /* Left and right shifts. */
 780 static intmax_t
 781 expshift ()
 782 {
 783   register intmax_t val1, val2;
 784
 785   val1 = exp3 ();
 786
 787   while ((curtok == LSH) || (curtok == RSH))
 788     {
 789       int op = curtok;
 790
 791       readtok ();
 792       val2 = exp3 ();
 793
 794       if (op == LSH)
 795         val1 = val1 << val2;
 796       else
 797         val1 = val1 >> val2;
 798       lasttok = NUM;
 799     }
 800
 801   return (val1);
 802 }
 803
 804 static intmax_t
 805 exp3 ()
 806 {
 807   register intmax_t val1, val2;
 808
 809   val1 = exp2 ();
 810
 811   while ((curtok == PLUS) || (curtok == MINUS))
 812     {
 813       int op = curtok;
 814
 815       readtok ();
 816       val2 = exp2 ();
 817
 818       if (op == PLUS)
 819         val1 += val2;
 820       else if (op == MINUS)
 821         val1 -= val2;
 822       lasttok = NUM;
 823     }
 824   return (val1);
 825 }
 826
 827 static intmax_t
 828 exp2 ()
 829 {
 830   register intmax_t val1, val2;
 831 #if defined (HAVE_IMAXDIV)
 832   imaxdiv_t idiv;
 833 #endif
 834
 835   val1 = exppower ();
 836
 837   while ((curtok == MUL) ||
 838          (curtok == DIV) ||
 839          (curtok == MOD))
 840     {
 841       int op = curtok;
 842       char *stp, *sltp;
 843
 844       stp = tp;
 845       readtok ();
 846
 847       val2 = exppower ();
 848
 849       /* Handle division by 0 and twos-complement arithmetic overflow */
 850       if (((op == DIV) || (op == MOD)) && (val2 == 0))
 851         {
 852           if (noeval == 0)
 853             {
 854               sltp = lasttp;
 855               lasttp = stp;
 856               while (lasttp && *lasttp && whitespace (*lasttp))
 857                 lasttp++;
 858               evalerror (_("division by 0"));
 859               lasttp = sltp;
 860             }
 861           else
 862             val2 = 1;
 863         }
 864       else if (op == MOD && val1 == INTMAX_MIN && val2 == -1)
 865         {
 866           val1 = 0;
 867           continue;
 868         }
 869       else if (op == DIV && val1 == INTMAX_MIN && val2 == -1)
 870         val2 = 1;
 871
 872       if (op == MUL)
 873         val1 *= val2;
 874       else if (op == DIV || op == MOD)
 875 #if defined (HAVE_IMAXDIV)
 876         {
 877           idiv = imaxdiv (val1, val2);
 878           val1 = (op == DIV) ? idiv.quot : idiv.rem;
 879         }
 880 #else
 881         val1 = (op == DIV) ? val1 / val2 : val1 % val2;
 882 #endif
 883       lasttok = NUM;
 884     }
 885   return (val1);
 886 }
 887
 888 static intmax_t
 889 ipow (base, exp)
 890      intmax_t base, exp;
 891 {
 892   intmax_t result;
 893
 894   result = 1;
 895   while (exp)
 896     {
 897       if (exp & 1)
 898         result *= base;
 899       exp >>= 1;
 900       base *= base;
 901     }
 902   return result;
 903 }
 904
 905 static intmax_t
 906 exppower ()
 907 {
 908   register intmax_t val1, val2, c;
 909
 910   val1 = exp1 ();
 911   while (curtok == POWER)
 912     {
 913       readtok ();
 914       val2 = exppower ();       /* exponentiation is right-associative */
 915       lasttok = NUM;
 916       if (val2 == 0)
 917         return (1);
 918       if (val2 < 0)
 919         evalerror (_("exponent less than 0"));
 920       val1 = ipow (val1, val2);
 921     }
 922   return (val1);
 923 }
 924
 925 static intmax_t
 926 exp1 ()
 927 {
 928   register intmax_t val;
 929
 930   if (curtok == NOT)
 931     {
 932       readtok ();
 933       val = !exp1 ();
 934       lasttok = NUM;
 935     }
 936   else if (curtok == BNOT)
 937     {
 938       readtok ();
 939       val = ~exp1 ();
 940       lasttok = NUM;
 941     }
 942   else if (curtok == MINUS)
 943     {
 944       readtok ();
 945       val = - exp1 ();
 946       lasttok = NUM;
 947     }
 948   else if (curtok == PLUS)
 949     {
 950       readtok ();
 951       val = exp1 ();
 952       lasttok = NUM;
 953     }
 954   else
 955     val = exp0 ();
 956
 957   return (val);
 958 }
 959
 960 static intmax_t
 961 exp0 ()
 962 {
 963   register intmax_t val = 0, v2;
 964   char *vincdec;
 965   int stok;
 966   EXPR_CONTEXT ec;
 967
 968   /* XXX - might need additional logic here to decide whether or not
 969            pre-increment or pre-decrement is legal at this point. */
 970   if (curtok == PREINC || curtok == PREDEC)
 971     {
 972       stok = lasttok = curtok;
 973       readtok ();
 974       if (curtok != STR)
 975         /* readtok() catches this */
 976         evalerror (_("identifier expected after pre-increment or pre-decrement"));
 977
 978       v2 = tokval + ((stok == PREINC) ? 1 : -1);
 979       vincdec = itos (v2);
 980       if (noeval == 0)
 981         {
 982 #if defined (ARRAY_VARS)
 983           if (curlval.ind != -1)
 984             expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
 985           else
 986 #endif
 987             expr_bind_variable (tokstr, vincdec);
 988         }
 989       free (vincdec);
 990       val = v2;
 991
 992       curtok = NUM;     /* make sure --x=7 is flagged as an error */
 993       readtok ();
 994     }
 995   else if (curtok == LPAR)
 996     {
 997       /* XXX - save curlval here?  Or entire expression context? */
 998       readtok ();
 999       val = EXP_HIGHEST ();
1000
1001       if (curtok != RPAR) /* ( */
1002         evalerror (_("missing `)'"));
1003
1004       /* Skip over closing paren. */
1005       readtok ();
1006     }
1007   else if ((curtok == NUM) || (curtok == STR))
1008     {
1009       val = tokval;
1010       if (curtok == STR)
1011         {
1012           SAVETOK (&ec);
1013           tokstr = (char *)NULL;        /* keep it from being freed */
1014           noeval = 1;
1015           readtok ();
1016           stok = curtok;
1017
1018           /* post-increment or post-decrement */
1019           if (stok == POSTINC || stok == POSTDEC)
1020             {
1021               /* restore certain portions of EC */
1022               tokstr = ec.tokstr;
1023               noeval = ec.noeval;
1024               curlval = ec.lval;
1025               lasttok = STR;    /* ec.curtok */
1026
1027               v2 = val + ((stok == POSTINC) ? 1 : -1);
1028               vincdec = itos (v2);
1029               if (noeval == 0)
1030                 {
1031 #if defined (ARRAY_VARS)
1032                   if (curlval.ind != -1)
1033                     expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
1034                   else
1035 #endif
1036                     expr_bind_variable (tokstr, vincdec);
1037                 }
1038               free (vincdec);
1039               curtok = NUM;     /* make sure x++=7 is flagged as an error */
1040             }
1041           else
1042             {
1043               /* XXX - watch out for pointer aliasing issues here */
1044               if (stok == STR)  /* free new tokstr before old one is restored */
1045                 FREE (tokstr);
1046               RESTORETOK (&ec);
1047             }
1048         }
1049
1050       readtok ();
1051     }
1052   else
1053     evalerror (_("syntax error: operand expected"));
1054
1055   return (val);
1056 }
1057
1058 static void
1059 init_lvalue (lv)
1060      struct lvalue *lv;
1061 {
1062   lv->tokstr = 0;
1063   lv->tokvar = 0;
1064   lv->tokval = lv->ind = -1;
1065 }
1066
1067 static struct lvalue *
1068 alloc_lvalue ()
1069 {
1070   struct lvalue *lv;
1071
1072   lv = xmalloc (sizeof (struct lvalue));
1073   init_lvalue (lv);
1074   return (lv);
1075 }
1076
1077 static void
1078 free_lvalue (lv)
1079      struct lvalue *lv;
1080 {
1081   free (lv);            /* should be inlined */
1082 }
1083
1084 static intmax_t
1085 expr_streval (tok, e, lvalue)
1086      char *tok;
1087      int e;
1088      struct lvalue *lvalue;
1089 {
1090   SHELL_VAR *v;
1091   char *value;
1092   intmax_t tval;
1093 #if defined (ARRAY_VARS)
1094   arrayind_t ind;
1095 #endif
1096
1097 /*itrace("expr_streval: %s: noeval = %d", tok, noeval);*/
1098   /* If we are suppressing evaluation, just short-circuit here instead of
1099      going through the rest of the evaluator. */
1100   if (noeval)
1101     return (0);
1102
1103   /* [[[[[ */
1104 #if defined (ARRAY_VARS)
1105   v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
1106 #else
1107   v = find_variable (tok);
1108 #endif
1109
1110   if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
1111     {
1112 #if defined (ARRAY_VARS)
1113       value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
1114 #else
1115       value = tok;
1116 #endif
1117
1118       last_command_exit_value = EXECUTION_FAILURE;
1119       err_unboundvar (value);
1120
1121 #if defined (ARRAY_VARS)
1122       if (e == ']')
1123         FREE (value);   /* array_variable_name returns new memory */
1124 #endif
1125
1126       if (interactive_shell)
1127         {
1128           expr_unwind ();
1129           top_level_cleanup ();
1130           jump_to_top_level (DISCARD);
1131         }
1132       else
1133         jump_to_top_level (FORCE_EOF);
1134     }
1135
1136 #if defined (ARRAY_VARS)
1137   ind = -1;
1138   /* Second argument of 0 to get_array_value means that we don't allow
1139      references like array[@].  In this case, get_array_value is just
1140      like get_variable_value in that it does not return newly-allocated
1141      memory or quote the results. */
1142   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL, &ind) : get_variable_value (v);
1143 #else
1144   value = get_variable_value (v);
1145 #endif
1146
1147   tval = (value && *value) ? subexpr (value) : 0;
1148
1149   if (lvalue)
1150     {
1151       lvalue->tokstr = tok;     /* XXX */
1152       lvalue->tokval = tval;
1153       lvalue->tokvar = v;       /* XXX */
1154 #if defined (ARRAY_VARS)
1155       lvalue->ind = ind;
1156 #else
1157       lvalue->ind = -1;
1158 #endif
1159     }
1160
1161   return (tval);
1162 }
1163
1164 static int
1165 _is_multiop (c)
1166      int c;
1167 {
1168   switch (c)
1169     {
1170     case EQEQ:
1171     case NEQ:
1172     case LEQ:
1173     case GEQ:
1174     case LAND:
1175     case LOR:
1176     case LSH:
1177     case RSH:
1178     case OP_ASSIGN:
1179     case COND:
1180     case POWER:
1181     case PREINC:
1182     case PREDEC:
1183     case POSTINC:
1184     case POSTDEC:
1185       return 1;
1186     default:
1187       return 0;
1188     }
1189 }
1190
1191 static int
1192 _is_arithop (c)
1193      int c;
1194 {
1195   switch (c)
1196     {
1197     case EQ:
1198     case GT:
1199     case LT:
1200     case PLUS:
1201     case MINUS:
1202     case MUL:
1203     case DIV:
1204     case MOD:
1205     case NOT:
1206     case LPAR:
1207     case RPAR:
1208     case BAND:
1209     case BOR:
1210     case BXOR:
1211     case BNOT:
1212       return 1;         /* operator tokens */
1213     case QUES:
1214     case COL:
1215     case COMMA:
1216       return 1;         /* questionable */
1217     default:
1218       return 0;         /* anything else is invalid */
1219     }
1220 }
1221
1222 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1223    next token and puts its value into curtok, while advancing past it.
1224    Updates value of tp.  May also set tokval (for number) or tokstr (for
1225    string). */
1226 static void
1227 readtok ()
1228 {
1229   register char *cp, *xp;
1230   register unsigned char c, c1;
1231   register int e;
1232   struct lvalue lval;
1233
1234   /* Skip leading whitespace. */
1235   cp = tp;
1236   c = e = 0;
1237   while (cp && (c = *cp) && (cr_whitespace (c)))
1238     cp++;
1239
1240   if (c)
1241     cp++;
1242
1243   if (c == '\0')
1244     {
1245       lasttok = curtok;
1246       curtok = 0;
1247       tp = cp;
1248       return;
1249     }
1250   lasttp = tp = cp - 1;
1251
1252   if (legal_variable_starter (c))
1253     {
1254       /* variable names not preceded with a dollar sign are shell variables. */
1255       char *savecp;
1256       EXPR_CONTEXT ec;
1257       int peektok;
1258
1259       while (legal_variable_char (c))
1260         c = *cp++;
1261
1262       c = *--cp;
1263
1264 #if defined (ARRAY_VARS)
1265       if (c == '[')
1266         {
1267           e = skipsubscript (cp, 0, 0);
1268           if (cp[e] == ']')
1269             {
1270               cp += e + 1;
1271               c = *cp;
1272               e = ']';
1273             }
1274           else
1275             evalerror (bash_badsub_errmsg);
1276         }
1277 #endif /* ARRAY_VARS */
1278
1279       *cp = '\0';
1280       /* XXX - watch out for pointer aliasing issues here */
1281       if (curlval.tokstr && curlval.tokstr == tokstr)
1282         init_lvalue (&curlval);
1283
1284       FREE (tokstr);
1285       tokstr = savestring (tp);
1286       *cp = c;
1287
1288       /* XXX - make peektok part of saved token state? */
1289       SAVETOK (&ec);
1290       tokstr = (char *)NULL;    /* keep it from being freed */
1291       tp = savecp = cp;
1292       noeval = 1;
1293       curtok = STR;
1294       readtok ();
1295       peektok = curtok;
1296       if (peektok == STR)       /* free new tokstr before old one is restored */
1297         FREE (tokstr);
1298       RESTORETOK (&ec);
1299       cp = savecp;
1300
1301       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1302          preserve old behavior if a construct like --x=9 is given. */
1303       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1304         {
1305           lastlval = curlval;
1306           tokval = expr_streval (tokstr, e, &curlval);
1307         }
1308       else
1309         tokval = 0;
1310
1311       lasttok = curtok;
1312       curtok = STR;
1313     }
1314   else if (DIGIT(c))
1315     {
1316       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1317         c = *cp++;
1318
1319       c = *--cp;
1320       *cp = '\0';
1321
1322       tokval = strlong (tp);
1323       *cp = c;
1324       lasttok = curtok;
1325       curtok = NUM;
1326     }
1327   else
1328     {
1329       c1 = *cp++;
1330       if ((c == EQ) && (c1 == EQ))
1331         c = EQEQ;
1332       else if ((c == NOT) && (c1 == EQ))
1333         c = NEQ;
1334       else if ((c == GT) && (c1 == EQ))
1335         c = GEQ;
1336       else if ((c == LT) && (c1 == EQ))
1337         c = LEQ;
1338       else if ((c == LT) && (c1 == LT))
1339         {
1340           if (*cp == '=')       /* a <<= b */
1341             {
1342               assigntok = LSH;
1343               c = OP_ASSIGN;
1344               cp++;
1345             }
1346           else
1347             c = LSH;
1348         }
1349       else if ((c == GT) && (c1 == GT))
1350         {
1351           if (*cp == '=')
1352             {
1353               assigntok = RSH;  /* a >>= b */
1354               c = OP_ASSIGN;
1355               cp++;
1356             }
1357           else
1358             c = RSH;
1359         }
1360       else if ((c == BAND) && (c1 == BAND))
1361         c = LAND;
1362       else if ((c == BOR) && (c1 == BOR))
1363         c = LOR;
1364       else if ((c == '*') && (c1 == '*'))
1365         c = POWER;
1366       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1367         c = (c == '-') ? POSTDEC : POSTINC;
1368       else if ((c == '-' || c == '+') && c1 == c)
1369         {
1370           /* Quickly scan forward to see if this is followed by optional
1371              whitespace and an identifier. */
1372           xp = cp;
1373           while (xp && *xp && cr_whitespace (*xp))
1374             xp++;
1375           if (legal_variable_starter ((unsigned char)*xp))
1376             c = (c == '-') ? PREDEC : PREINC;
1377           else
1378             cp--;       /* not preinc or predec, so unget the character */
1379         }
1380       else if (c1 == EQ && member (c, "*/%+-&^|"))
1381         {
1382           assigntok = c;        /* a OP= b */
1383           c = OP_ASSIGN;
1384         }
1385       else if (_is_arithop (c) == 0)
1386         {
1387           cp--;
1388           /* use curtok, since it hasn't been copied to lasttok yet */
1389           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1390             evalerror (_("syntax error: operand expected"));
1391           else
1392             evalerror (_("syntax error: invalid arithmetic operator"));
1393         }
1394       else
1395         cp--;                   /* `unget' the character */
1396
1397       /* Should check here to make sure that the current character is one
1398          of the recognized operators and flag an error if not.  Could create
1399          a character map the first time through and check it on subsequent
1400          calls. */
1401       lasttok = curtok;
1402       curtok = c;
1403     }
1404   tp = cp;
1405 }
1406
1407 static void
1408 evalerror (msg)
1409      const char *msg;
1410 {
1411   char *name, *t;
1412
1413   name = this_command_name;
1414   for (t = expression; whitespace (*t); t++)
1415     ;
1416   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1417                    name ? name : "", name ? ": " : "", t,
1418                    msg, (lasttp && *lasttp) ? lasttp : "");
1419   longjmp (evalbuf, 1);
1420 }
1421
1422 /* Convert a string to an intmax_t integer, with an arbitrary base.
1423    0nnn -> base 8
1424    0[Xx]nn -> base 16
1425    Anything else: [base#]number (this is implemented to match ksh93)
1426
1427    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1428    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1429    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1430    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1431    you get the picture). */
1432
1433 static intmax_t
1434 strlong (num)
1435      char *num;
1436 {
1437   register char *s;
1438   register unsigned char c;
1439   int base, foundbase;
1440   intmax_t val;
1441
1442   s = num;
1443
1444   base = 10;
1445   foundbase = 0;
1446   if (*s == '0')
1447     {
1448       s++;
1449
1450       if (*s == '\0')
1451         return 0;
1452
1453        /* Base 16? */
1454       if (*s == 'x' || *s == 'X')
1455         {
1456           base = 16;
1457           s++;
1458         }
1459       else
1460         base = 8;
1461       foundbase++;
1462     }
1463
1464   val = 0;
1465   for (c = *s++; c; c = *s++)
1466     {
1467       if (c == '#')
1468         {
1469           if (foundbase)
1470             evalerror (_("invalid number"));
1471
1472           /* Illegal base specifications raise an evaluation error. */
1473           if (val < 2 || val > 64)
1474             evalerror (_("invalid arithmetic base"));
1475
1476           base = val;
1477           val = 0;
1478           foundbase++;
1479         }
1480       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1481         {
1482           if (DIGIT(c))
1483             c = TODIGIT(c);
1484           else if (c >= 'a' && c <= 'z')
1485             c -= 'a' - 10;
1486           else if (c >= 'A' && c <= 'Z')
1487             c -= 'A' - ((base <= 36) ? 10 : 36);
1488           else if (c == '@')
1489             c = 62;
1490           else if (c == '_')
1491             c = 63;
1492
1493           if (c >= base)
1494             evalerror (_("value too great for base"));
1495
1496           val = (val * base) + c;
1497         }
1498       else
1499         break;
1500     }
1501
1502   return (val);
1503 }
1504
1505 #if defined (EXPR_TEST)
1506 void *
1507 xmalloc (n)
1508      int n;
1509 {
1510   return (malloc (n));
1511 }
1512
1513 void *
1514 xrealloc (s, n)
1515      char *s;
1516      int n;
1517 {
1518   return (realloc (s, n));
1519 }
1520
1521 SHELL_VAR *find_variable () { return 0;}
1522 SHELL_VAR *bind_variable () { return 0; }
1523
1524 char *get_string_value () { return 0; }
1525
1526 procenv_t top_level;
1527
1528 main (argc, argv)
1529      int argc;
1530      char **argv;
1531 {
1532   register int i;
1533   intmax_t v;
1534   int expok;
1535
1536   if (setjmp (top_level))
1537     exit (0);
1538
1539   for (i = 1; i < argc; i++)
1540     {
1541       v = evalexp (argv[i], &expok);
1542       if (expok == 0)
1543         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1544       else
1545         printf ("'%s' -> %ld\n", argv[i], v);
1546     }
1547   exit (0);
1548 }
1549
1550 int
1551 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1552      char *format;
1553 {
1554   fprintf (stderr, "expr: ");
1555   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1556   fprintf (stderr, "\n");
1557   return 0;
1558 }
1559
1560 char *
1561 itos (n)
1562      intmax_t n;
1563 {
1564   return ("42");
1565 }
1566
1567 #endif /* EXPR_TEST */