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           switch (op)
 480             {
 481             case MUL:
 482               lvalue *= value;
 483               break;
 484             case DIV:
 485               if (value == 0)
 486                 evalerror (_("division by 0"));
 487               lvalue /= value;
 488               break;
 489             case MOD:
 490               if (value == 0)
 491                 evalerror (_("division by 0"));
 492               lvalue %= value;
 493               break;
 494             case PLUS:
 495               lvalue += value;
 496               break;
 497             case MINUS:
 498               lvalue -= value;
 499               break;
 500             case LSH:
 501               lvalue <<= value;
 502               break;
 503             case RSH:
 504               lvalue >>= value;
 505               break;
 506             case BAND:
 507               lvalue &= value;
 508               break;
 509             case BOR:
 510               lvalue |= value;
 511               break;
 512             case BXOR:
 513               lvalue ^= value;
 514               break;
 515             default:
 516               free (lhs);
 517               evalerror (_("bug: bad expassign token"));
 518               break;
 519             }
 520           value = lvalue;
 521         }
 522
 523       rhs = itos (value);
 524       if (noeval == 0)
 525         {
 526           if (lind != -1)
 527             expr_bind_array_element (lhs, lind, rhs);
 528           else
 529             expr_bind_variable (lhs, rhs);
 530         }
 531       free (rhs);
 532       free (lhs);
 533       FREE (tokstr);
 534       tokstr = (char *)NULL;            /* For freeing on errors. */
 535     }
 536   return (value);
 537 }
 538
 539 /* Conditional expression (expr?expr:expr) */
 540 static intmax_t
 541 expcond ()
 542 {
 543   intmax_t cval, val1, val2, rval;
 544   int set_noeval;
 545
 546   set_noeval = 0;
 547   rval = cval = explor ();
 548   if (curtok == QUES)           /* found conditional expr */
 549     {
 550       readtok ();
 551       if (curtok == 0 || curtok == COL)
 552         evalerror (_("expression expected"));
 553       if (cval == 0)
 554         {
 555           set_noeval = 1;
 556           noeval++;
 557         }
 558
 559       val1 = EXP_HIGHEST ();
 560
 561       if (set_noeval)
 562         noeval--;
 563       if (curtok != COL)
 564         evalerror (_("`:' expected for conditional expression"));
 565       readtok ();
 566       if (curtok == 0)
 567         evalerror (_("expression expected"));
 568       set_noeval = 0;
 569       if (cval)
 570         {
 571           set_noeval = 1;
 572           noeval++;
 573         }
 574
 575       val2 = expcond ();
 576       if (set_noeval)
 577         noeval--;
 578       rval = cval ? val1 : val2;
 579       lasttok = COND;
 580     }
 581   return rval;
 582 }
 583
 584 /* Logical OR. */
 585 static intmax_t
 586 explor ()
 587 {
 588   register intmax_t val1, val2;
 589   int set_noeval;
 590
 591   val1 = expland ();
 592
 593   while (curtok == LOR)
 594     {
 595       set_noeval = 0;
 596       if (val1 != 0)
 597         {
 598           noeval++;
 599           set_noeval = 1;
 600         }
 601       readtok ();
 602       val2 = expland ();
 603       if (set_noeval)
 604         noeval--;
 605       val1 = val1 || val2;
 606       lasttok = LOR;
 607     }
 608
 609   return (val1);
 610 }
 611
 612 /* Logical AND. */
 613 static intmax_t
 614 expland ()
 615 {
 616   register intmax_t val1, val2;
 617   int set_noeval;
 618
 619   val1 = expbor ();
 620
 621   while (curtok == LAND)
 622     {
 623       set_noeval = 0;
 624       if (val1 == 0)
 625         {
 626           set_noeval = 1;
 627           noeval++;
 628         }
 629       readtok ();
 630       val2 = expbor ();
 631       if (set_noeval)
 632         noeval--;
 633       val1 = val1 && val2;
 634       lasttok = LAND;
 635     }
 636
 637   return (val1);
 638 }
 639
 640 /* Bitwise OR. */
 641 static intmax_t
 642 expbor ()
 643 {
 644   register intmax_t val1, val2;
 645
 646   val1 = expbxor ();
 647
 648   while (curtok == BOR)
 649     {
 650       readtok ();
 651       val2 = expbxor ();
 652       val1 = val1 | val2;
 653     }
 654
 655   return (val1);
 656 }
 657
 658 /* Bitwise XOR. */
 659 static intmax_t
 660 expbxor ()
 661 {
 662   register intmax_t val1, val2;
 663
 664   val1 = expband ();
 665
 666   while (curtok == BXOR)
 667     {
 668       readtok ();
 669       val2 = expband ();
 670       val1 = val1 ^ val2;
 671     }
 672
 673   return (val1);
 674 }
 675
 676 /* Bitwise AND. */
 677 static intmax_t
 678 expband ()
 679 {
 680   register intmax_t val1, val2;
 681
 682   val1 = exp5 ();
 683
 684   while (curtok == BAND)
 685     {
 686       readtok ();
 687       val2 = exp5 ();
 688       val1 = val1 & val2;
 689     }
 690
 691   return (val1);
 692 }
 693
 694 static intmax_t
 695 exp5 ()
 696 {
 697   register intmax_t val1, val2;
 698
 699   val1 = exp4 ();
 700
 701   while ((curtok == EQEQ) || (curtok == NEQ))
 702     {
 703       int op = curtok;
 704
 705       readtok ();
 706       val2 = exp4 ();
 707       if (op == EQEQ)
 708         val1 = (val1 == val2);
 709       else if (op == NEQ)
 710         val1 = (val1 != val2);
 711     }
 712   return (val1);
 713 }
 714
 715 static intmax_t
 716 exp4 ()
 717 {
 718   register intmax_t val1, val2;
 719
 720   val1 = expshift ();
 721   while ((curtok == LEQ) ||
 722          (curtok == GEQ) ||
 723          (curtok == LT) ||
 724          (curtok == GT))
 725     {
 726       int op = curtok;
 727
 728       readtok ();
 729       val2 = expshift ();
 730
 731       if (op == LEQ)
 732         val1 = val1 <= val2;
 733       else if (op == GEQ)
 734         val1 = val1 >= val2;
 735       else if (op == LT)
 736         val1 = val1 < val2;
 737       else                      /* (op == GT) */
 738         val1 = val1 > val2;
 739     }
 740   return (val1);
 741 }
 742
 743 /* Left and right shifts. */
 744 static intmax_t
 745 expshift ()
 746 {
 747   register intmax_t val1, val2;
 748
 749   val1 = exp3 ();
 750
 751   while ((curtok == LSH) || (curtok == RSH))
 752     {
 753       int op = curtok;
 754
 755       readtok ();
 756       val2 = exp3 ();
 757
 758       if (op == LSH)
 759         val1 = val1 << val2;
 760       else
 761         val1 = val1 >> val2;
 762     }
 763
 764   return (val1);
 765 }
 766
 767 static intmax_t
 768 exp3 ()
 769 {
 770   register intmax_t val1, val2;
 771
 772   val1 = exp2 ();
 773
 774   while ((curtok == PLUS) || (curtok == MINUS))
 775     {
 776       int op = curtok;
 777
 778       readtok ();
 779       val2 = exp2 ();
 780
 781       if (op == PLUS)
 782         val1 += val2;
 783       else if (op == MINUS)
 784         val1 -= val2;
 785     }
 786   return (val1);
 787 }
 788
 789 static intmax_t
 790 exp2 ()
 791 {
 792   register intmax_t val1, val2;
 793
 794   val1 = exppower ();
 795
 796   while ((curtok == MUL) ||
 797          (curtok == DIV) ||
 798          (curtok == MOD))
 799     {
 800       int op = curtok;
 801
 802       readtok ();
 803
 804       val2 = exppower ();
 805
 806       if (((op == DIV) || (op == MOD)) && (val2 == 0))
 807         evalerror (_("division by 0"));
 808
 809       if (op == MUL)
 810         val1 *= val2;
 811       else if (op == DIV)
 812         val1 /= val2;
 813       else if (op == MOD)
 814         val1 %= val2;
 815     }
 816   return (val1);
 817 }
 818
 819 static intmax_t
 820 exppower ()
 821 {
 822   register intmax_t val1, val2, c;
 823
 824   val1 = exp1 ();
 825   while (curtok == POWER)
 826     {
 827       readtok ();
 828       val2 = exppower ();       /* exponentiation is right-associative */
 829       if (val2 == 0)
 830         return (1);
 831       if (val2 < 0)
 832         evalerror (_("exponent less than 0"));
 833       for (c = 1; val2--; c *= val1)
 834         ;
 835       val1 = c;
 836     }
 837   return (val1);
 838 }
 839
 840 static intmax_t
 841 exp1 ()
 842 {
 843   register intmax_t val;
 844
 845   if (curtok == NOT)
 846     {
 847       readtok ();
 848       val = !exp1 ();
 849     }
 850   else if (curtok == BNOT)
 851     {
 852       readtok ();
 853       val = ~exp1 ();
 854     }
 855   else if (curtok == MINUS)
 856     {
 857       readtok ();
 858       val = - exp1 ();
 859     }
 860   else if (curtok == PLUS)
 861     {
 862       readtok ();
 863       val = exp1 ();
 864     }
 865   else
 866     val = exp0 ();
 867
 868   return (val);
 869 }
 870
 871 static intmax_t
 872 exp0 ()
 873 {
 874   register intmax_t val = 0, v2;
 875   char *vincdec;
 876   int stok;
 877   EXPR_CONTEXT ec;
 878
 879   /* XXX - might need additional logic here to decide whether or not
 880            pre-increment or pre-decrement is legal at this point. */
 881   if (curtok == PREINC || curtok == PREDEC)
 882     {
 883       stok = lasttok = curtok;
 884       readtok ();
 885       if (curtok != STR)
 886         /* readtok() catches this */
 887         evalerror (_("identifier expected after pre-increment or pre-decrement"));
 888
 889       v2 = tokval + ((stok == PREINC) ? 1 : -1);
 890       vincdec = itos (v2);
 891       if (noeval == 0)
 892         {
 893           if (curlval.ind != -1)
 894             expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
 895           else
 896             expr_bind_variable (tokstr, vincdec);
 897         }
 898       free (vincdec);
 899       val = v2;
 900
 901       curtok = NUM;     /* make sure --x=7 is flagged as an error */
 902       readtok ();
 903     }
 904   else if (curtok == LPAR)
 905     {
 906       readtok ();
 907       val = EXP_HIGHEST ();
 908
 909       if (curtok != RPAR) /* ( */
 910         evalerror (_("missing `)'"));
 911
 912       /* Skip over closing paren. */
 913       readtok ();
 914     }
 915   else if ((curtok == NUM) || (curtok == STR))
 916     {
 917       val = tokval;
 918       if (curtok == STR)
 919         {
 920           SAVETOK (&ec);
 921           tokstr = (char *)NULL;        /* keep it from being freed */
 922           noeval = 1;
 923           readtok ();
 924           stok = curtok;
 925
 926           /* post-increment or post-decrement */
 927           if (stok == POSTINC || stok == POSTDEC)
 928             {
 929               /* restore certain portions of EC */
 930               tokstr = ec.tokstr;
 931               noeval = ec.noeval;
 932               curlval = ec.lval;
 933               lasttok = STR;    /* ec.curtok */
 934
 935               v2 = val + ((stok == POSTINC) ? 1 : -1);
 936               vincdec = itos (v2);
 937               if (noeval == 0)
 938                 {
 939                   if (curlval.ind != -1)
 940                     expr_bind_array_element (curlval.tokstr, curlval.ind, vincdec);
 941                   else
 942                     expr_bind_variable (tokstr, vincdec);
 943                 }
 944               free (vincdec);
 945               curtok = NUM;     /* make sure x++=7 is flagged as an error */
 946             }
 947           else
 948             {
 949               if (stok == STR)  /* free new tokstr before old one is restored */
 950                 FREE (tokstr);
 951               RESTORETOK (&ec);
 952             }
 953
 954         }
 955
 956       readtok ();
 957     }
 958   else
 959     evalerror (_("syntax error: operand expected"));
 960
 961   return (val);
 962 }
 963
 964 static void
 965 init_lvalue (lv)
 966      struct lvalue *lv;
 967 {
 968   lv->tokstr = 0;
 969   lv->tokvar = 0;
 970   lv->tokval = lv->ind = -1;
 971 }
 972
 973 static struct lvalue *
 974 alloc_lvalue ()
 975 {
 976   struct lvalue *lv;
 977
 978   lv = xmalloc (sizeof (struct lvalue));
 979   init_lvalue (lv);
 980   return (lv);
 981 }
 982
 983 static void
 984 free_lvalue (lv)
 985      struct lvalue *lv;
 986 {
 987   free (lv);            /* should be inlined */
 988 }
 989
 990 static intmax_t
 991 expr_streval (tok, e, lvalue)
 992      char *tok;
 993      int e;
 994      struct lvalue *lvalue;
 995 {
 996   SHELL_VAR *v;
 997   char *value;
 998   intmax_t tval;
 999 #if defined (ARRAY_VARS)
1000   arrayind_t ind;
1001 #endif
1002
1003   /* [[[[[ */
1004 #if defined (ARRAY_VARS)
1005   v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
1006 #else
1007   v = find_variable (tok);
1008 #endif
1009
1010   if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
1011     {
1012 #if defined (ARRAY_VARS)
1013       value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
1014 #else
1015       value = tok;
1016 #endif
1017
1018       last_command_exit_value = EXECUTION_FAILURE;
1019       err_unboundvar (value);
1020
1021 #if defined (ARRAY_VARS)
1022       if (e == ']')
1023         FREE (value);   /* array_variable_name returns new memory */
1024 #endif
1025
1026       if (interactive_shell)
1027         {
1028           expr_unwind ();
1029           top_level_cleanup ();
1030           jump_to_top_level (DISCARD);
1031         }
1032       else
1033         jump_to_top_level (FORCE_EOF);
1034     }
1035
1036   ind = -1;
1037 #if defined (ARRAY_VARS)
1038   /* Second argument of 0 to get_array_value means that we don't allow
1039      references like array[@].  In this case, get_array_value is just
1040      like get_variable_value in that it does not return newly-allocated
1041      memory or quote the results. */
1042   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL, &ind) : get_variable_value (v);
1043 #else
1044   value = get_variable_value (v);
1045 #endif
1046
1047   tval = (value && *value) ? subexpr (value) : 0;
1048
1049   if (lvalue)
1050     {
1051       lvalue->tokstr = tok;     /* XXX */
1052       lvalue->tokval = tval;
1053       lvalue->tokvar = v;       /* XXX */
1054       lvalue->ind = ind;
1055     }
1056
1057   return (tval);
1058 }
1059
1060 static int
1061 _is_multiop (c)
1062      int c;
1063 {
1064   switch (c)
1065     {
1066     case EQEQ:
1067     case NEQ:
1068     case LEQ:
1069     case GEQ:
1070     case LAND:
1071     case LOR:
1072     case LSH:
1073     case RSH:
1074     case OP_ASSIGN:
1075     case COND:
1076     case POWER:
1077     case PREINC:
1078     case PREDEC:
1079     case POSTINC:
1080     case POSTDEC:
1081       return 1;
1082     default:
1083       return 0;
1084     }
1085 }
1086
1087 static int
1088 _is_arithop (c)
1089      int c;
1090 {
1091   switch (c)
1092     {
1093     case EQ:
1094     case GT:
1095     case LT:
1096     case PLUS:
1097     case MINUS:
1098     case MUL:
1099     case DIV:
1100     case MOD:
1101     case NOT:
1102     case LPAR:
1103     case RPAR:
1104     case BAND:
1105     case BOR:
1106     case BXOR:
1107     case BNOT:
1108       return 1;         /* operator tokens */
1109     case QUES:
1110     case COL:
1111     case COMMA:
1112       return 1;         /* questionable */
1113     default:
1114       return 0;         /* anything else is invalid */
1115     }
1116 }
1117
1118 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1119    next token and puts its value into curtok, while advancing past it.
1120    Updates value of tp.  May also set tokval (for number) or tokstr (for
1121    string). */
1122 static void
1123 readtok ()
1124 {
1125   register char *cp, *xp;
1126   register unsigned char c, c1;
1127   register int e;
1128   struct lvalue lval;
1129
1130   /* Skip leading whitespace. */
1131   cp = tp;
1132   c = e = 0;
1133   while (cp && (c = *cp) && (cr_whitespace (c)))
1134     cp++;
1135
1136   if (c)
1137     cp++;
1138
1139   if (c == '\0')
1140     {
1141       lasttok = curtok;
1142       curtok = 0;
1143       tp = cp;
1144       return;
1145     }
1146   lasttp = tp = cp - 1;
1147
1148   if (legal_variable_starter (c))
1149     {
1150       /* variable names not preceded with a dollar sign are shell variables. */
1151       char *savecp;
1152       EXPR_CONTEXT ec;
1153       int peektok;
1154
1155       while (legal_variable_char (c))
1156         c = *cp++;
1157
1158       c = *--cp;
1159
1160 #if defined (ARRAY_VARS)
1161       if (c == '[')
1162         {
1163           e = skipsubscript (cp, 0, 0);
1164           if (cp[e] == ']')
1165             {
1166               cp += e + 1;
1167               c = *cp;
1168               e = ']';
1169             }
1170           else
1171             evalerror (bash_badsub_errmsg);
1172         }
1173 #endif /* ARRAY_VARS */
1174
1175       *cp = '\0';
1176       FREE (tokstr);
1177       tokstr = savestring (tp);
1178       *cp = c;
1179
1180       /* XXX - make peektok part of saved token state? */
1181       SAVETOK (&ec);
1182       tokstr = (char *)NULL;    /* keep it from being freed */
1183       tp = savecp = cp;
1184       noeval = 1;
1185       curtok = STR;
1186       readtok ();
1187       peektok = curtok;
1188       if (peektok == STR)       /* free new tokstr before old one is restored */
1189         FREE (tokstr);
1190       RESTORETOK (&ec);
1191       cp = savecp;
1192
1193       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1194          preserve old behavior if a construct like --x=9 is given. */
1195       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1196         {
1197           lastlval = curlval;
1198           tokval = expr_streval (tokstr, e, &curlval);
1199         }
1200       else
1201         tokval = 0;
1202
1203       lasttok = curtok;
1204       curtok = STR;
1205     }
1206   else if (DIGIT(c))
1207     {
1208       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1209         c = *cp++;
1210
1211       c = *--cp;
1212       *cp = '\0';
1213
1214       tokval = strlong (tp);
1215       *cp = c;
1216       lasttok = curtok;
1217       curtok = NUM;
1218     }
1219   else
1220     {
1221       c1 = *cp++;
1222       if ((c == EQ) && (c1 == EQ))
1223         c = EQEQ;
1224       else if ((c == NOT) && (c1 == EQ))
1225         c = NEQ;
1226       else if ((c == GT) && (c1 == EQ))
1227         c = GEQ;
1228       else if ((c == LT) && (c1 == EQ))
1229         c = LEQ;
1230       else if ((c == LT) && (c1 == LT))
1231         {
1232           if (*cp == '=')       /* a <<= b */
1233             {
1234               assigntok = LSH;
1235               c = OP_ASSIGN;
1236               cp++;
1237             }
1238           else
1239             c = LSH;
1240         }
1241       else if ((c == GT) && (c1 == GT))
1242         {
1243           if (*cp == '=')
1244             {
1245               assigntok = RSH;  /* a >>= b */
1246               c = OP_ASSIGN;
1247               cp++;
1248             }
1249           else
1250             c = RSH;
1251         }
1252       else if ((c == BAND) && (c1 == BAND))
1253         c = LAND;
1254       else if ((c == BOR) && (c1 == BOR))
1255         c = LOR;
1256       else if ((c == '*') && (c1 == '*'))
1257         c = POWER;
1258       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1259         c = (c == '-') ? POSTDEC : POSTINC;
1260       else if ((c == '-' || c == '+') && c1 == c)
1261         {
1262           /* Quickly scan forward to see if this is followed by optional
1263              whitespace and an identifier. */
1264           xp = cp;
1265           while (xp && *xp && cr_whitespace (*xp))
1266             xp++;
1267           if (legal_variable_starter ((unsigned char)*xp))
1268             c = (c == '-') ? PREDEC : PREINC;
1269           else
1270             cp--;       /* not preinc or predec, so unget the character */
1271         }
1272       else if (c1 == EQ && member (c, "*/%+-&^|"))
1273         {
1274           assigntok = c;        /* a OP= b */
1275           c = OP_ASSIGN;
1276         }
1277       else if (_is_arithop (c) == 0)
1278         {
1279           cp--;
1280           /* use curtok, since it hasn't been copied to lasttok yet */
1281           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1282             evalerror (_("syntax error: operand expected"));
1283           else
1284             evalerror (_("syntax error: invalid arithmetic operator"));
1285         }
1286       else
1287         cp--;                   /* `unget' the character */
1288
1289       /* Should check here to make sure that the current character is one
1290          of the recognized operators and flag an error if not.  Could create
1291          a character map the first time through and check it on subsequent
1292          calls. */
1293       lasttok = curtok;
1294       curtok = c;
1295     }
1296   tp = cp;
1297 }
1298
1299 static void
1300 evalerror (msg)
1301      const char *msg;
1302 {
1303   char *name, *t;
1304
1305   name = this_command_name;
1306   for (t = expression; whitespace (*t); t++)
1307     ;
1308   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1309                    name ? name : "", name ? ": " : "", t,
1310                    msg, (lasttp && *lasttp) ? lasttp : "");
1311   longjmp (evalbuf, 1);
1312 }
1313
1314 /* Convert a string to an intmax_t integer, with an arbitrary base.
1315    0nnn -> base 8
1316    0[Xx]nn -> base 16
1317    Anything else: [base#]number (this is implemented to match ksh93)
1318
1319    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1320    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1321    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1322    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1323    you get the picture). */
1324
1325 static intmax_t
1326 strlong (num)
1327      char *num;
1328 {
1329   register char *s;
1330   register unsigned char c;
1331   int base, foundbase;
1332   intmax_t val;
1333
1334   s = num;
1335
1336   base = 10;
1337   foundbase = 0;
1338   if (*s == '0')
1339     {
1340       s++;
1341
1342       if (*s == '\0')
1343         return 0;
1344
1345        /* Base 16? */
1346       if (*s == 'x' || *s == 'X')
1347         {
1348           base = 16;
1349           s++;
1350         }
1351       else
1352         base = 8;
1353       foundbase++;
1354     }
1355
1356   val = 0;
1357   for (c = *s++; c; c = *s++)
1358     {
1359       if (c == '#')
1360         {
1361           if (foundbase)
1362             evalerror (_("invalid number"));
1363
1364           /* Illegal base specifications raise an evaluation error. */
1365           if (val < 2 || val > 64)
1366             evalerror (_("invalid arithmetic base"));
1367
1368           base = val;
1369           val = 0;
1370           foundbase++;
1371         }
1372       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1373         {
1374           if (DIGIT(c))
1375             c = TODIGIT(c);
1376           else if (c >= 'a' && c <= 'z')
1377             c -= 'a' - 10;
1378           else if (c >= 'A' && c <= 'Z')
1379             c -= 'A' - ((base <= 36) ? 10 : 36);
1380           else if (c == '@')
1381             c = 62;
1382           else if (c == '_')
1383             c = 63;
1384
1385           if (c >= base)
1386             evalerror (_("value too great for base"));
1387
1388           val = (val * base) + c;
1389         }
1390       else
1391         break;
1392     }
1393
1394   return (val);
1395 }
1396
1397 #if defined (EXPR_TEST)
1398 void *
1399 xmalloc (n)
1400      int n;
1401 {
1402   return (malloc (n));
1403 }
1404
1405 void *
1406 xrealloc (s, n)
1407      char *s;
1408      int n;
1409 {
1410   return (realloc (s, n));
1411 }
1412
1413 SHELL_VAR *find_variable () { return 0;}
1414 SHELL_VAR *bind_variable () { return 0; }
1415
1416 char *get_string_value () { return 0; }
1417
1418 procenv_t top_level;
1419
1420 main (argc, argv)
1421      int argc;
1422      char **argv;
1423 {
1424   register int i;
1425   intmax_t v;
1426   int expok;
1427
1428   if (setjmp (top_level))
1429     exit (0);
1430
1431   for (i = 1; i < argc; i++)
1432     {
1433       v = evalexp (argv[i], &expok);
1434       if (expok == 0)
1435         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1436       else
1437         printf ("'%s' -> %ld\n", argv[i], v);
1438     }
1439   exit (0);
1440 }
1441
1442 int
1443 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1444      char *format;
1445 {
1446   fprintf (stderr, "expr: ");
1447   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1448   fprintf (stderr, "\n");
1449   return 0;
1450 }
1451
1452 char *
1453 itos (n)
1454      intmax_t n;
1455 {
1456   return ("42");
1457 }
1458
1459 #endif /* EXPR_TEST */