expr.c

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