expr.c

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