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       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 (no_longjmp_on_fatal_error && interactive_shell)
1127         sh_longjmp (evalbuf, 1);
1128
1129       if (interactive_shell)
1130         {
1131           expr_unwind ();
1132           top_level_cleanup ();
1133           jump_to_top_level (DISCARD);
1134         }
1135       else
1136         jump_to_top_level (FORCE_EOF);
1137     }
1138
1139 #if defined (ARRAY_VARS)
1140   ind = -1;
1141   /* Second argument of 0 to get_array_value means that we don't allow
1142      references like array[@].  In this case, get_array_value is just
1143      like get_variable_value in that it does not return newly-allocated
1144      memory or quote the results. */
1145   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL, &ind) : get_variable_value (v);
1146 #else
1147   value = get_variable_value (v);
1148 #endif
1149
1150   tval = (value && *value) ? subexpr (value) : 0;
1151
1152   if (lvalue)
1153     {
1154       lvalue->tokstr = tok;     /* XXX */
1155       lvalue->tokval = tval;
1156       lvalue->tokvar = v;       /* XXX */
1157 #if defined (ARRAY_VARS)
1158       lvalue->ind = ind;
1159 #else
1160       lvalue->ind = -1;
1161 #endif
1162     }
1163
1164   return (tval);
1165 }
1166
1167 static int
1168 _is_multiop (c)
1169      int c;
1170 {
1171   switch (c)
1172     {
1173     case EQEQ:
1174     case NEQ:
1175     case LEQ:
1176     case GEQ:
1177     case LAND:
1178     case LOR:
1179     case LSH:
1180     case RSH:
1181     case OP_ASSIGN:
1182     case COND:
1183     case POWER:
1184     case PREINC:
1185     case PREDEC:
1186     case POSTINC:
1187     case POSTDEC:
1188       return 1;
1189     default:
1190       return 0;
1191     }
1192 }
1193
1194 static int
1195 _is_arithop (c)
1196      int c;
1197 {
1198   switch (c)
1199     {
1200     case EQ:
1201     case GT:
1202     case LT:
1203     case PLUS:
1204     case MINUS:
1205     case MUL:
1206     case DIV:
1207     case MOD:
1208     case NOT:
1209     case LPAR:
1210     case RPAR:
1211     case BAND:
1212     case BOR:
1213     case BXOR:
1214     case BNOT:
1215       return 1;         /* operator tokens */
1216     case QUES:
1217     case COL:
1218     case COMMA:
1219       return 1;         /* questionable */
1220     default:
1221       return 0;         /* anything else is invalid */
1222     }
1223 }
1224
1225 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1226    next token and puts its value into curtok, while advancing past it.
1227    Updates value of tp.  May also set tokval (for number) or tokstr (for
1228    string). */
1229 static void
1230 readtok ()
1231 {
1232   register char *cp, *xp;
1233   register unsigned char c, c1;
1234   register int e;
1235   struct lvalue lval;
1236
1237   /* Skip leading whitespace. */
1238   cp = tp;
1239   c = e = 0;
1240   while (cp && (c = *cp) && (cr_whitespace (c)))
1241     cp++;
1242
1243   if (c)
1244     cp++;
1245
1246   if (c == '\0')
1247     {
1248       lasttok = curtok;
1249       curtok = 0;
1250       tp = cp;
1251       return;
1252     }
1253   lasttp = tp = cp - 1;
1254
1255   if (legal_variable_starter (c))
1256     {
1257       /* variable names not preceded with a dollar sign are shell variables. */
1258       char *savecp;
1259       EXPR_CONTEXT ec;
1260       int peektok;
1261
1262       while (legal_variable_char (c))
1263         c = *cp++;
1264
1265       c = *--cp;
1266
1267 #if defined (ARRAY_VARS)
1268       if (c == '[')
1269         {
1270           e = skipsubscript (cp, 0, 0);
1271           if (cp[e] == ']')
1272             {
1273               cp += e + 1;
1274               c = *cp;
1275               e = ']';
1276             }
1277           else
1278             evalerror (bash_badsub_errmsg);
1279         }
1280 #endif /* ARRAY_VARS */
1281
1282       *cp = '\0';
1283       /* XXX - watch out for pointer aliasing issues here */
1284       if (curlval.tokstr && curlval.tokstr == tokstr)
1285         init_lvalue (&curlval);
1286
1287       FREE (tokstr);
1288       tokstr = savestring (tp);
1289       *cp = c;
1290
1291       /* XXX - make peektok part of saved token state? */
1292       SAVETOK (&ec);
1293       tokstr = (char *)NULL;    /* keep it from being freed */
1294       tp = savecp = cp;
1295       noeval = 1;
1296       curtok = STR;
1297       readtok ();
1298       peektok = curtok;
1299       if (peektok == STR)       /* free new tokstr before old one is restored */
1300         FREE (tokstr);
1301       RESTORETOK (&ec);
1302       cp = savecp;
1303
1304       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1305          preserve old behavior if a construct like --x=9 is given. */
1306       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1307         {
1308           lastlval = curlval;
1309           tokval = expr_streval (tokstr, e, &curlval);
1310         }
1311       else
1312         tokval = 0;
1313
1314       lasttok = curtok;
1315       curtok = STR;
1316     }
1317   else if (DIGIT(c))
1318     {
1319       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1320         c = *cp++;
1321
1322       c = *--cp;
1323       *cp = '\0';
1324
1325       tokval = strlong (tp);
1326       *cp = c;
1327       lasttok = curtok;
1328       curtok = NUM;
1329     }
1330   else
1331     {
1332       c1 = *cp++;
1333       if ((c == EQ) && (c1 == EQ))
1334         c = EQEQ;
1335       else if ((c == NOT) && (c1 == EQ))
1336         c = NEQ;
1337       else if ((c == GT) && (c1 == EQ))
1338         c = GEQ;
1339       else if ((c == LT) && (c1 == EQ))
1340         c = LEQ;
1341       else if ((c == LT) && (c1 == LT))
1342         {
1343           if (*cp == '=')       /* a <<= b */
1344             {
1345               assigntok = LSH;
1346               c = OP_ASSIGN;
1347               cp++;
1348             }
1349           else
1350             c = LSH;
1351         }
1352       else if ((c == GT) && (c1 == GT))
1353         {
1354           if (*cp == '=')
1355             {
1356               assigntok = RSH;  /* a >>= b */
1357               c = OP_ASSIGN;
1358               cp++;
1359             }
1360           else
1361             c = RSH;
1362         }
1363       else if ((c == BAND) && (c1 == BAND))
1364         c = LAND;
1365       else if ((c == BOR) && (c1 == BOR))
1366         c = LOR;
1367       else if ((c == '*') && (c1 == '*'))
1368         c = POWER;
1369       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1370         c = (c == '-') ? POSTDEC : POSTINC;
1371       else if ((c == '-' || c == '+') && c1 == c)
1372         {
1373           /* Quickly scan forward to see if this is followed by optional
1374              whitespace and an identifier. */
1375           xp = cp;
1376           while (xp && *xp && cr_whitespace (*xp))
1377             xp++;
1378           if (legal_variable_starter ((unsigned char)*xp))
1379             c = (c == '-') ? PREDEC : PREINC;
1380           else
1381             cp--;       /* not preinc or predec, so unget the character */
1382         }
1383       else if (c1 == EQ && member (c, "*/%+-&^|"))
1384         {
1385           assigntok = c;        /* a OP= b */
1386           c = OP_ASSIGN;
1387         }
1388       else if (_is_arithop (c) == 0)
1389         {
1390           cp--;
1391           /* use curtok, since it hasn't been copied to lasttok yet */
1392           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1393             evalerror (_("syntax error: operand expected"));
1394           else
1395             evalerror (_("syntax error: invalid arithmetic operator"));
1396         }
1397       else
1398         cp--;                   /* `unget' the character */
1399
1400       /* Should check here to make sure that the current character is one
1401          of the recognized operators and flag an error if not.  Could create
1402          a character map the first time through and check it on subsequent
1403          calls. */
1404       lasttok = curtok;
1405       curtok = c;
1406     }
1407   tp = cp;
1408 }
1409
1410 static void
1411 evalerror (msg)
1412      const char *msg;
1413 {
1414   char *name, *t;
1415
1416   name = this_command_name;
1417   for (t = expression; whitespace (*t); t++)
1418     ;
1419   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1420                    name ? name : "", name ? ": " : "", t,
1421                    msg, (lasttp && *lasttp) ? lasttp : "");
1422   sh_longjmp (evalbuf, 1);
1423 }
1424
1425 /* Convert a string to an intmax_t integer, with an arbitrary base.
1426    0nnn -> base 8
1427    0[Xx]nn -> base 16
1428    Anything else: [base#]number (this is implemented to match ksh93)
1429
1430    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1431    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1432    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1433    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1434    you get the picture). */
1435
1436 static intmax_t
1437 strlong (num)
1438      char *num;
1439 {
1440   register char *s;
1441   register unsigned char c;
1442   int base, foundbase;
1443   intmax_t val;
1444
1445   s = num;
1446
1447   base = 10;
1448   foundbase = 0;
1449   if (*s == '0')
1450     {
1451       s++;
1452
1453       if (*s == '\0')
1454         return 0;
1455
1456        /* Base 16? */
1457       if (*s == 'x' || *s == 'X')
1458         {
1459           base = 16;
1460           s++;
1461         }
1462       else
1463         base = 8;
1464       foundbase++;
1465     }
1466
1467   val = 0;
1468   for (c = *s++; c; c = *s++)
1469     {
1470       if (c == '#')
1471         {
1472           if (foundbase)
1473             evalerror (_("invalid number"));
1474
1475           /* Illegal base specifications raise an evaluation error. */
1476           if (val < 2 || val > 64)
1477             evalerror (_("invalid arithmetic base"));
1478
1479           base = val;
1480           val = 0;
1481           foundbase++;
1482         }
1483       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1484         {
1485           if (DIGIT(c))
1486             c = TODIGIT(c);
1487           else if (c >= 'a' && c <= 'z')
1488             c -= 'a' - 10;
1489           else if (c >= 'A' && c <= 'Z')
1490             c -= 'A' - ((base <= 36) ? 10 : 36);
1491           else if (c == '@')
1492             c = 62;
1493           else if (c == '_')
1494             c = 63;
1495
1496           if (c >= base)
1497             evalerror (_("value too great for base"));
1498
1499           val = (val * base) + c;
1500         }
1501       else
1502         break;
1503     }
1504
1505   return (val);
1506 }
1507
1508 #if defined (EXPR_TEST)
1509 void *
1510 xmalloc (n)
1511      int n;
1512 {
1513   return (malloc (n));
1514 }
1515
1516 void *
1517 xrealloc (s, n)
1518      char *s;
1519      int n;
1520 {
1521   return (realloc (s, n));
1522 }
1523
1524 SHELL_VAR *find_variable () { return 0;}
1525 SHELL_VAR *bind_variable () { return 0; }
1526
1527 char *get_string_value () { return 0; }
1528
1529 procenv_t top_level;
1530
1531 main (argc, argv)
1532      int argc;
1533      char **argv;
1534 {
1535   register int i;
1536   intmax_t v;
1537   int expok;
1538
1539   if (setjmp (top_level))
1540     exit (0);
1541
1542   for (i = 1; i < argc; i++)
1543     {
1544       v = evalexp (argv[i], &expok);
1545       if (expok == 0)
1546         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1547       else
1548         printf ("'%s' -> %ld\n", argv[i], v);
1549     }
1550   exit (0);
1551 }
1552
1553 int
1554 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1555      char *format;
1556 {
1557   fprintf (stderr, "expr: ");
1558   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1559   fprintf (stderr, "\n");
1560   return 0;
1561 }
1562
1563 char *
1564 itos (n)
1565      intmax_t n;
1566 {
1567   return ("42");
1568 }
1569
1570 #endif /* EXPR_TEST */