expr.c

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