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;
 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       err_unboundvar (value);
 927
 928 #if defined (ARRAY_VARS)
 929       if (e == ']')
 930         FREE (value);   /* array_variable_name returns new memory */
 931 #endif
 932
 933       if (interactive_shell)
 934         {
 935           expr_unwind ();
 936           top_level_cleanup ();
 937           jump_to_top_level (DISCARD);
 938         }
 939       else
 940         jump_to_top_level (FORCE_EOF);
 941     }
 942
 943 #if defined (ARRAY_VARS)
 944   /* Second argument of 0 to get_array_value means that we don't allow
 945      references like array[@].  In this case, get_array_value is just
 946      like get_variable_value in that it does not return newly-allocated
 947      memory or quote the results. */
 948   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL) : get_variable_value (v);
 949 #else
 950   value = get_variable_value (v);
 951 #endif
 952
 953   tval = (value && *value) ? subexpr (value) : 0;
 954
 955   return (tval);
 956 }
 957
 958 static int
 959 _is_multiop (c)
 960      int c;
 961 {
 962   switch (c)
 963     {
 964     case EQEQ:
 965     case NEQ:
 966     case LEQ:
 967     case GEQ:
 968     case LAND:
 969     case LOR:
 970     case LSH:
 971     case RSH:
 972     case OP_ASSIGN:
 973     case COND:
 974     case POWER:
 975     case PREINC:
 976     case PREDEC:
 977     case POSTINC:
 978     case POSTDEC:
 979       return 1;
 980     default:
 981       return 0;
 982     }
 983 }
 984
 985 static int
 986 _is_arithop (c)
 987      int c;
 988 {
 989   switch (c)
 990     {
 991     case EQ:
 992     case GT:
 993     case LT:
 994     case PLUS:
 995     case MINUS:
 996     case MUL:
 997     case DIV:
 998     case MOD:
 999     case NOT:
1000     case LPAR:
1001     case RPAR:
1002     case BAND:
1003     case BOR:
1004     case BXOR:
1005     case BNOT:
1006       return 1;         /* operator tokens */
1007     case QUES:
1008     case COL:
1009     case COMMA:
1010       return 1;         /* questionable */
1011     default:
1012       return 0;         /* anything else is invalid */
1013     }
1014 }
1015
1016 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1017    next token and puts its value into curtok, while advancing past it.
1018    Updates value of tp.  May also set tokval (for number) or tokstr (for
1019    string). */
1020 static void
1021 readtok ()
1022 {
1023   register char *cp, *xp;
1024   register unsigned char c, c1;
1025   register int e;
1026
1027   /* Skip leading whitespace. */
1028   cp = tp;
1029   c = e = 0;
1030   while (cp && (c = *cp) && (cr_whitespace (c)))
1031     cp++;
1032
1033   if (c)
1034     cp++;
1035
1036   if (c == '\0')
1037     {
1038       lasttok = curtok;
1039       curtok = 0;
1040       tp = cp;
1041       return;
1042     }
1043   lasttp = tp = cp - 1;
1044
1045   if (legal_variable_starter (c))
1046     {
1047       /* variable names not preceded with a dollar sign are shell variables. */
1048       char *savecp;
1049       EXPR_CONTEXT ec;
1050       int peektok;
1051
1052       while (legal_variable_char (c))
1053         c = *cp++;
1054
1055       c = *--cp;
1056
1057 #if defined (ARRAY_VARS)
1058       if (c == '[')
1059         {
1060           e = skipsubscript (cp, 0);
1061           if (cp[e] == ']')
1062             {
1063               cp += e + 1;
1064               c = *cp;
1065               e = ']';
1066             }
1067           else
1068             evalerror (bash_badsub_errmsg);
1069         }
1070 #endif /* ARRAY_VARS */
1071
1072       *cp = '\0';
1073       FREE (tokstr);
1074       tokstr = savestring (tp);
1075       *cp = c;
1076
1077       SAVETOK (&ec);
1078       tokstr = (char *)NULL;    /* keep it from being freed */
1079       tp = savecp = cp;
1080       noeval = 1;
1081       curtok = STR;
1082       readtok ();
1083       peektok = curtok;
1084       if (peektok == STR)       /* free new tokstr before old one is restored */
1085         FREE (tokstr);
1086       RESTORETOK (&ec);
1087       cp = savecp;
1088
1089       /* The tests for PREINC and PREDEC aren't strictly correct, but they
1090          preserve old behavior if a construct like --x=9 is given. */
1091       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1092         tokval = expr_streval (tokstr, e);
1093       else
1094         tokval = 0;
1095
1096       lasttok = curtok;
1097       curtok = STR;
1098     }
1099   else if (DIGIT(c))
1100     {
1101       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1102         c = *cp++;
1103
1104       c = *--cp;
1105       *cp = '\0';
1106
1107       tokval = strlong (tp);
1108       *cp = c;
1109       lasttok = curtok;
1110       curtok = NUM;
1111     }
1112   else
1113     {
1114       c1 = *cp++;
1115       if ((c == EQ) && (c1 == EQ))
1116         c = EQEQ;
1117       else if ((c == NOT) && (c1 == EQ))
1118         c = NEQ;
1119       else if ((c == GT) && (c1 == EQ))
1120         c = GEQ;
1121       else if ((c == LT) && (c1 == EQ))
1122         c = LEQ;
1123       else if ((c == LT) && (c1 == LT))
1124         {
1125           if (*cp == '=')       /* a <<= b */
1126             {
1127               assigntok = LSH;
1128               c = OP_ASSIGN;
1129               cp++;
1130             }
1131           else
1132             c = LSH;
1133         }
1134       else if ((c == GT) && (c1 == GT))
1135         {
1136           if (*cp == '=')
1137             {
1138               assigntok = RSH;  /* a >>= b */
1139               c = OP_ASSIGN;
1140               cp++;
1141             }
1142           else
1143             c = RSH;
1144         }
1145       else if ((c == BAND) && (c1 == BAND))
1146         c = LAND;
1147       else if ((c == BOR) && (c1 == BOR))
1148         c = LOR;
1149       else if ((c == '*') && (c1 == '*'))
1150         c = POWER;
1151       else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1152         c = (c == '-') ? POSTDEC : POSTINC;
1153       else if ((c == '-' || c == '+') && c1 == c)
1154         {
1155           /* Quickly scan forward to see if this is followed by optional
1156              whitespace and an identifier. */
1157           xp = cp;
1158           while (xp && *xp && cr_whitespace (*xp))
1159             xp++;
1160           if (legal_variable_starter ((unsigned char)*xp))
1161             c = (c == '-') ? PREDEC : PREINC;
1162           else
1163             cp--;       /* not preinc or predec, so unget the character */
1164         }
1165       else if (c1 == EQ && member (c, "*/%+-&^|"))
1166         {
1167           assigntok = c;        /* a OP= b */
1168           c = OP_ASSIGN;
1169         }
1170       else if (_is_arithop (c) == 0)
1171         {
1172           cp--;
1173           /* use curtok, since it hasn't been copied to lasttok yet */
1174           if (curtok == 0 || _is_arithop (curtok) || _is_multiop (curtok))
1175             evalerror (_("syntax error: operand expected"));
1176           else
1177             evalerror (_("syntax error: invalid arithmetic operator"));
1178         }
1179       else
1180         cp--;                   /* `unget' the character */
1181
1182       /* Should check here to make sure that the current character is one
1183          of the recognized operators and flag an error if not.  Could create
1184          a character map the first time through and check it on subsequent
1185          calls. */
1186       lasttok = curtok;
1187       curtok = c;
1188     }
1189   tp = cp;
1190 }
1191
1192 static void
1193 evalerror (msg)
1194      const char *msg;
1195 {
1196   char *name, *t;
1197
1198   name = this_command_name;
1199   for (t = expression; whitespace (*t); t++)
1200     ;
1201   internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1202                    name ? name : "", name ? ": " : "", t,
1203                    msg, (lasttp && *lasttp) ? lasttp : "");
1204   longjmp (evalbuf, 1);
1205 }
1206
1207 /* Convert a string to an intmax_t integer, with an arbitrary base.
1208    0nnn -> base 8
1209    0[Xx]nn -> base 16
1210    Anything else: [base#]number (this is implemented to match ksh93)
1211
1212    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1213    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1214    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1215    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1216    you get the picture). */
1217
1218 static intmax_t
1219 strlong (num)
1220      char *num;
1221 {
1222   register char *s;
1223   register unsigned char c;
1224   int base, foundbase;
1225   intmax_t val;
1226
1227   s = num;
1228
1229   base = 10;
1230   foundbase = 0;
1231   if (*s == '0')
1232     {
1233       s++;
1234
1235       if (*s == '\0')
1236         return 0;
1237
1238        /* Base 16? */
1239       if (*s == 'x' || *s == 'X')
1240         {
1241           base = 16;
1242           s++;
1243         }
1244       else
1245         base = 8;
1246       foundbase++;
1247     }
1248
1249   val = 0;
1250   for (c = *s++; c; c = *s++)
1251     {
1252       if (c == '#')
1253         {
1254           if (foundbase)
1255             evalerror (_("invalid number"));
1256
1257           /* Illegal base specifications raise an evaluation error. */
1258           if (val < 2 || val > 64)
1259             evalerror (_("invalid arithmetic base"));
1260
1261           base = val;
1262           val = 0;
1263           foundbase++;
1264         }
1265       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1266         {
1267           if (DIGIT(c))
1268             c = TODIGIT(c);
1269           else if (c >= 'a' && c <= 'z')
1270             c -= 'a' - 10;
1271           else if (c >= 'A' && c <= 'Z')
1272             c -= 'A' - ((base <= 36) ? 10 : 36);
1273           else if (c == '@')
1274             c = 62;
1275           else if (c == '_')
1276             c = 63;
1277
1278           if (c >= base)
1279             evalerror (_("value too great for base"));
1280
1281           val = (val * base) + c;
1282         }
1283       else
1284         break;
1285     }
1286
1287   return (val);
1288 }
1289
1290 #if defined (EXPR_TEST)
1291 void *
1292 xmalloc (n)
1293      int n;
1294 {
1295   return (malloc (n));
1296 }
1297
1298 void *
1299 xrealloc (s, n)
1300      char *s;
1301      int n;
1302 {
1303   return (realloc (s, n));
1304 }
1305
1306 SHELL_VAR *find_variable () { return 0;}
1307 SHELL_VAR *bind_variable () { return 0; }
1308
1309 char *get_string_value () { return 0; }
1310
1311 procenv_t top_level;
1312
1313 main (argc, argv)
1314      int argc;
1315      char **argv;
1316 {
1317   register int i;
1318   intmax_t v;
1319   int expok;
1320
1321   if (setjmp (top_level))
1322     exit (0);
1323
1324   for (i = 1; i < argc; i++)
1325     {
1326       v = evalexp (argv[i], &expok);
1327       if (expok == 0)
1328         fprintf (stderr, _("%s: expression error\n"), argv[i]);
1329       else
1330         printf ("'%s' -> %ld\n", argv[i], v);
1331     }
1332   exit (0);
1333 }
1334
1335 int
1336 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1337      char *format;
1338 {
1339   fprintf (stderr, "expr: ");
1340   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1341   fprintf (stderr, "\n");
1342   return 0;
1343 }
1344
1345 char *
1346 itos (n)
1347      intmax_t n;
1348 {
1349   return ("42");
1350 }
1351
1352 #endif /* EXPR_TEST */