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   /* [[[[[ */
1013 #if defined (ARRAY_VARS)
1014   v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
1015 #else
1016   v = find_variable (tok);
1017 #endif
1018
1019   if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
1020     {
1021 #if defined (ARRAY_VARS)
1022       value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
1023 #else
1024       value = tok;
1025 #endif
1026
1027       last_command_exit_value = EXECUTION_FAILURE;
1028       err_unboundvar (value);
1029
1030 #if defined (ARRAY_VARS)
1031       if (e == ']')
1032         FREE (value);   /* array_variable_name returns new memory */
1033 #endif
1034
1035       if (interactive_shell)
1036         {
1037           expr_unwind ();
1038           top_level_cleanup ();
1039           jump_to_top_level (DISCARD);
1040         }
1041       else
1042         jump_to_top_level (FORCE_EOF);
1043     }
1044
1045   ind = -1;
1046 #if defined (ARRAY_VARS)
1047   /* Second argument of 0 to get_array_value means that we don't allow
1048      references like array[@].  In this case, get_array_value is just
1049      like get_variable_value in that it does not return newly-allocated
1050      memory or quote the results. */
1051   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL, &ind) : get_variable_value (v);
1052 #else
1053   value = get_variable_value (v);
1054 #endif
1055
1056   tval = (value && *value) ? subexpr (value) : 0;
1057
1058   if (lvalue)
1059     {
1060       lvalue->tokstr = tok;     /* XXX */
1061       lvalue->tokval = tval;
1062       lvalue->tokvar = v;       /* XXX */
1063       lvalue->ind = ind;
1064     }
1065
1066   return (tval);
1067 }
1068
1069 static int
1070 _is_multiop (c)
1071      int c;
1072 {
1073   switch (c)
1074     {
1075     case EQEQ:
1076     case NEQ:
1077     case LEQ:
1078     case GEQ:
1079     case LAND:
1080     case LOR:
1081     case LSH:
1082     case RSH:
1083     case OP_ASSIGN:
1084     case COND:
1085     case POWER:
1086     case PREINC:
1087     case PREDEC:
1088     case POSTINC:
1089     case POSTDEC:
1090       return 1;
1091     default:
1092       return 0;
1093     }
1094 }
1095
1096 static int
1097 _is_arithop (c)
1098      int c;
1099 {
1100   switch (c)
1101     {
1102     case EQ:
1103     case GT:
1104     case LT:
1105     case PLUS:
1106     case MINUS:
1107     case MUL:
1108     case DIV:
1109     case MOD:
1110     case NOT:
1111     case LPAR:
1112     case RPAR:
1113     case BAND:
1114     case BOR:
1115     case BXOR:
1116     case BNOT:
1117       return 1;         /* operator tokens */
1118     case QUES:
1119     case COL:
1120     case COMMA:
1121       return 1;         /* questionable */
1122     default:
1123       return 0;         /* anything else is invalid */
1124     }
1125 }
1126
1127 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1128    next token and puts its value into curtok, while advancing past it.
1129    Updates value of tp.  May also set tokval (for number) or tokstr (for
1130    string). */
1131 static void
1132 readtok ()
1133 {
1134   register char *cp, *xp;
1135   register unsigned char c, c1;
1136   register int e;
1137   struct lvalue lval;
1138
1139   /* Skip leading whitespace. */
1140   cp = tp;
1141   c = e = 0;
1142   while (cp && (c = *cp) && (cr_whitespace (c)))
1143     cp++;
1144
1145   if (c)
1146     cp++;
1147
1148   if (c == '\0')
1149     {
1150       lasttok = curtok;
1151       curtok = 0;
1152       tp = cp;
1153       return;
1154     }
1155   lasttp = tp = cp - 1;
1156
1157   if (legal_variable_starter (c))
1158     {
1159       /* variable names not preceded with a dollar sign are shell variables. */
1160       char *savecp;
1161       EXPR_CONTEXT ec;
1162       int peektok;
1163
1164       while (legal_variable_char (c))
1165         c = *cp++;
1166
1167       c = *--cp;
1168
1169 #if defined (ARRAY_VARS)
1170       if (c == '[')
1171         {
1172           e = skipsubscript (cp, 0, 0);
1173           if (cp[e] == ']')
1174             {
1175               cp += e + 1;
1176               c = *cp;
1177               e = ']';
1178             }
1179           else
1180             evalerror (bash_badsub_errmsg);
1181         }
1182 #endif /* ARRAY_VARS */
1183
1184       *cp = '\0';
1185       FREE (tokstr);
1186       tokstr = savestring (tp);
1187       *cp = c;
1188
1189       /* XXX - make peektok part of saved token state? */
1190       SAVETOK (&ec);
1191       tokstr = (char *)NULL;    /* keep it from being freed */
1192       tp = savecp = cp;
1193       noeval = 1;
1194       curtok = STR;
1195       readtok ();
1196       peektok = curtok;
1197       if (peektok == STR)       /* free new tokstr before old one is restored */
1198         FREE (tokstr);
1199       RESTORETOK (&ec);
1200       cp = savecp;
1201
1202       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1203          preserve old behavior if a construct like --x=9 is given. */
1204       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1205         {
1206           lastlval = curlval;
1207           tokval = expr_streval (tokstr, e, &curlval);
1208         }
1209       else
1210         tokval = 0;
1211
1212       lasttok = curtok;
1213       curtok = STR;
1214     }
1215   else if (DIGIT(c))
1216     {
1217       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1218         c = *cp++;
1219
1220       c = *--cp;
1221       *cp = '\0';
1222
1223       tokval = strlong (tp);
1224       *cp = c;
1225       lasttok = curtok;
1226       curtok = NUM;
1227     }
1228   else
1229     {
1230       c1 = *cp++;
1231       if ((c == EQ) && (c1 == EQ))
1232         c = EQEQ;
1233       else if ((c == NOT) && (c1 == EQ))
1234         c = NEQ;
1235       else if ((c == GT) && (c1 == EQ))
1236         c = GEQ;
1237       else if ((c == LT) && (c1 == EQ))
1238         c = LEQ;
1239       else if ((c == LT) && (c1 == LT))
1240         {
1241           if (*cp == '=')       /* a <<= b */
1242             {
1243               assigntok = LSH;
1244               c = OP_ASSIGN;
1245               cp++;
1246             }
1247           else
1248             c = LSH;
1249         }
1250       else if ((c == GT) && (c1 == GT))
1251         {
1252           if (*cp == '=')
1253             {
1254               assigntok = RSH;  /* a >>= b */
1255               c = OP_ASSIGN;
1256               cp++;
1257             }
1258           else
1259             c = RSH;
1260         }
1261       else if ((c == BAND) && (c1 == BAND))
1262         c = LAND;
1263       else if ((c == BOR) && (c1 == BOR))
1264         c = LOR;
1265       else if ((c == '*') && (c1 == '*'))
1266         c = POWER;
1267       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1268         c = (c == '-') ? POSTDEC : POSTINC;
1269       else if ((c == '-' || c == '+') && c1 == c)
1270         {
1271           /* Quickly scan forward to see if this is followed by optional
1272              whitespace and an identifier. */
1273           xp = cp;
1274           while (xp && *xp && cr_whitespace (*xp))
1275             xp++;
1276           if (legal_variable_starter ((unsigned char)*xp))
1277             c = (c == '-') ? PREDEC : PREINC;
1278           else
1279             cp--;       /* not preinc or predec, so unget the character */
1280         }
1281       else if (c1 == EQ && member (c, "*/%+-&^|"))
1282         {
1283           assigntok = c;        /* a OP= b */
1284           c = OP_ASSIGN;
1285         }
1286       else if (_is_arithop (c) == 0)
1287         {
1288           cp--;
1289           /* use curtok, since it hasn't been copied to lasttok yet */
1290           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1291             evalerror (_("syntax error: operand expected"));
1292           else
1293             evalerror (_("syntax error: invalid arithmetic operator"));
1294         }
1295       else
1296         cp--;                   /* `unget' the character */
1297
1298       /* Should check here to make sure that the current character is one
1299          of the recognized operators and flag an error if not.  Could create
1300          a character map the first time through and check it on subsequent
1301          calls. */
1302       lasttok = curtok;
1303       curtok = c;
1304     }
1305   tp = cp;
1306 }
1307
1308 static void
1309 evalerror (msg)
1310      const char *msg;
1311 {
1312   char *name, *t;
1313
1314   name = this_command_name;
1315   for (t = expression; whitespace (*t); t++)
1316     ;
1317   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1318                    name ? name : "", name ? ": " : "", t,
1319                    msg, (lasttp && *lasttp) ? lasttp : "");
1320   longjmp (evalbuf, 1);
1321 }
1322
1323 /* Convert a string to an intmax_t integer, with an arbitrary base.
1324    0nnn -> base 8
1325    0[Xx]nn -> base 16
1326    Anything else: [base#]number (this is implemented to match ksh93)
1327
1328    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1329    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1330    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1331    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1332    you get the picture). */
1333
1334 static intmax_t
1335 strlong (num)
1336      char *num;
1337 {
1338   register char *s;
1339   register unsigned char c;
1340   int base, foundbase;
1341   intmax_t val;
1342
1343   s = num;
1344
1345   base = 10;
1346   foundbase = 0;
1347   if (*s == '0')
1348     {
1349       s++;
1350
1351       if (*s == '\0')
1352         return 0;
1353
1354        /* Base 16? */
1355       if (*s == 'x' || *s == 'X')
1356         {
1357           base = 16;
1358           s++;
1359         }
1360       else
1361         base = 8;
1362       foundbase++;
1363     }
1364
1365   val = 0;
1366   for (c = *s++; c; c = *s++)
1367     {
1368       if (c == '#')
1369         {
1370           if (foundbase)
1371             evalerror (_("invalid number"));
1372
1373           /* Illegal base specifications raise an evaluation error. */
1374           if (val < 2 || val > 64)
1375             evalerror (_("invalid arithmetic base"));
1376
1377           base = val;
1378           val = 0;
1379           foundbase++;
1380         }
1381       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1382         {
1383           if (DIGIT(c))
1384             c = TODIGIT(c);
1385           else if (c >= 'a' && c <= 'z')
1386             c -= 'a' - 10;
1387           else if (c >= 'A' && c <= 'Z')
1388             c -= 'A' - ((base <= 36) ? 10 : 36);
1389           else if (c == '@')
1390             c = 62;
1391           else if (c == '_')
1392             c = 63;
1393
1394           if (c >= base)
1395             evalerror (_("value too great for base"));
1396
1397           val = (val * base) + c;
1398         }
1399       else
1400         break;
1401     }
1402
1403   return (val);
1404 }
1405
1406 #if defined (EXPR_TEST)
1407 void *
1408 xmalloc (n)
1409      int n;
1410 {
1411   return (malloc (n));
1412 }
1413
1414 void *
1415 xrealloc (s, n)
1416      char *s;
1417      int n;
1418 {
1419   return (realloc (s, n));
1420 }
1421
1422 SHELL_VAR *find_variable () { return 0;}
1423 SHELL_VAR *bind_variable () { return 0; }
1424
1425 char *get_string_value () { return 0; }
1426
1427 procenv_t top_level;
1428
1429 main (argc, argv)
1430      int argc;
1431      char **argv;
1432 {
1433   register int i;
1434   intmax_t v;
1435   int expok;
1436
1437   if (setjmp (top_level))
1438     exit (0);
1439
1440   for (i = 1; i < argc; i++)
1441     {
1442       v = evalexp (argv[i], &expok);
1443       if (expok == 0)
1444         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1445       else
1446         printf ("'%s' -> %ld\n", argv[i], v);
1447     }
1448   exit (0);
1449 }
1450
1451 int
1452 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1453      char *format;
1454 {
1455   fprintf (stderr, "expr: ");
1456   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1457   fprintf (stderr, "\n");
1458   return 0;
1459 }
1460
1461 char *
1462 itos (n)
1463      intmax_t n;
1464 {
1465   return ("42");
1466 }
1467
1468 #endif /* EXPR_TEST */