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