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   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       val2 = explor ();
 524       if (set_noeval)
 525         noeval--;
 526       rval = cval ? val1 : val2;
 527       lasttok = COND;
 528     }
 529   return rval;
 530 }
 531
 532 /* Logical OR. */
 533 static intmax_t
 534 explor ()
 535 {
 536   register intmax_t val1, val2;
 537   int set_noeval;
 538
 539   val1 = expland ();
 540
 541   while (curtok == LOR)
 542     {
 543       set_noeval = 0;
 544       if (val1 != 0)
 545         {
 546           noeval++;
 547           set_noeval = 1;
 548         }
 549       readtok ();
 550       val2 = expland ();
 551       if (set_noeval)
 552         noeval--;
 553       val1 = val1 || val2;
 554       lasttok = LOR;
 555     }
 556
 557   return (val1);
 558 }
 559
 560 /* Logical AND. */
 561 static intmax_t
 562 expland ()
 563 {
 564   register intmax_t val1, val2;
 565   int set_noeval;
 566
 567   val1 = expbor ();
 568
 569   while (curtok == LAND)
 570     {
 571       set_noeval = 0;
 572       if (val1 == 0)
 573         {
 574           set_noeval = 1;
 575           noeval++;
 576         }
 577       readtok ();
 578       val2 = expbor ();
 579       if (set_noeval)
 580         noeval--;
 581       val1 = val1 && val2;
 582       lasttok = LAND;
 583     }
 584
 585   return (val1);
 586 }
 587
 588 /* Bitwise OR. */
 589 static intmax_t
 590 expbor ()
 591 {
 592   register intmax_t val1, val2;
 593
 594   val1 = expbxor ();
 595
 596   while (curtok == BOR)
 597     {
 598       readtok ();
 599       val2 = expbxor ();
 600       val1 = val1 | val2;
 601     }
 602
 603   return (val1);
 604 }
 605
 606 /* Bitwise XOR. */
 607 static intmax_t
 608 expbxor ()
 609 {
 610   register intmax_t val1, val2;
 611
 612   val1 = expband ();
 613
 614   while (curtok == BXOR)
 615     {
 616       readtok ();
 617       val2 = expband ();
 618       val1 = val1 ^ val2;
 619     }
 620
 621   return (val1);
 622 }
 623
 624 /* Bitwise AND. */
 625 static intmax_t
 626 expband ()
 627 {
 628   register intmax_t val1, val2;
 629
 630   val1 = exp5 ();
 631
 632   while (curtok == BAND)
 633     {
 634       readtok ();
 635       val2 = exp5 ();
 636       val1 = val1 & val2;
 637     }
 638
 639   return (val1);
 640 }
 641
 642 static intmax_t
 643 exp5 ()
 644 {
 645   register intmax_t val1, val2;
 646
 647   val1 = exp4 ();
 648
 649   while ((curtok == EQEQ) || (curtok == NEQ))
 650     {
 651       int op = curtok;
 652
 653       readtok ();
 654       val2 = exp4 ();
 655       if (op == EQEQ)
 656         val1 = (val1 == val2);
 657       else if (op == NEQ)
 658         val1 = (val1 != val2);
 659     }
 660   return (val1);
 661 }
 662
 663 static intmax_t
 664 exp4 ()
 665 {
 666   register intmax_t val1, val2;
 667
 668   val1 = expshift ();
 669   while ((curtok == LEQ) ||
 670          (curtok == GEQ) ||
 671          (curtok == LT) ||
 672          (curtok == GT))
 673     {
 674       int op = curtok;
 675
 676       readtok ();
 677       val2 = expshift ();
 678
 679       if (op == LEQ)
 680         val1 = val1 <= val2;
 681       else if (op == GEQ)
 682         val1 = val1 >= val2;
 683       else if (op == LT)
 684         val1 = val1 < val2;
 685       else                      /* (op == GT) */
 686         val1 = val1 > val2;
 687     }
 688   return (val1);
 689 }
 690
 691 /* Left and right shifts. */
 692 static intmax_t
 693 expshift ()
 694 {
 695   register intmax_t val1, val2;
 696
 697   val1 = exp3 ();
 698
 699   while ((curtok == LSH) || (curtok == RSH))
 700     {
 701       int op = curtok;
 702
 703       readtok ();
 704       val2 = exp3 ();
 705
 706       if (op == LSH)
 707         val1 = val1 << val2;
 708       else
 709         val1 = val1 >> val2;
 710     }
 711
 712   return (val1);
 713 }
 714
 715 static intmax_t
 716 exp3 ()
 717 {
 718   register intmax_t val1, val2;
 719
 720   val1 = exp2 ();
 721
 722   while ((curtok == PLUS) || (curtok == MINUS))
 723     {
 724       int op = curtok;
 725
 726       readtok ();
 727       val2 = exp2 ();
 728
 729       if (op == PLUS)
 730         val1 += val2;
 731       else if (op == MINUS)
 732         val1 -= val2;
 733     }
 734   return (val1);
 735 }
 736
 737 static intmax_t
 738 exp2 ()
 739 {
 740   register intmax_t val1, val2;
 741
 742   val1 = exppower ();
 743
 744   while ((curtok == MUL) ||
 745          (curtok == DIV) ||
 746          (curtok == MOD))
 747     {
 748       int op = curtok;
 749
 750       readtok ();
 751
 752       val2 = exppower ();
 753
 754       if (((op == DIV) || (op == MOD)) && (val2 == 0))
 755         evalerror (_("division by 0"));
 756
 757       if (op == MUL)
 758         val1 *= val2;
 759       else if (op == DIV)
 760         val1 /= val2;
 761       else if (op == MOD)
 762         val1 %= val2;
 763     }
 764   return (val1);
 765 }
 766
 767 static intmax_t
 768 exppower ()
 769 {
 770   register intmax_t val1, val2, c;
 771
 772   val1 = exp1 ();
 773   while (curtok == POWER)
 774     {
 775       readtok ();
 776       val2 = exppower ();       /* exponentiation is right-associative */
 777       if (val2 == 0)
 778         return (1);
 779       if (val2 < 0)
 780         evalerror (_("exponent less than 0"));
 781       for (c = 1; val2--; c *= val1)
 782         ;
 783       val1 = c;
 784     }
 785   return (val1);
 786 }
 787
 788 static intmax_t
 789 exp1 ()
 790 {
 791   register intmax_t val;
 792
 793   if (curtok == NOT)
 794     {
 795       readtok ();
 796       val = !exp1 ();
 797     }
 798   else if (curtok == BNOT)
 799     {
 800       readtok ();
 801       val = ~exp1 ();
 802     }
 803   else
 804     val = exp0 ();
 805
 806   return (val);
 807 }
 808
 809 static intmax_t
 810 exp0 ()
 811 {
 812   register intmax_t val = 0, v2;
 813   char *vincdec;
 814   int stok;
 815   EXPR_CONTEXT ec;
 816
 817   /* XXX - might need additional logic here to decide whether or not
 818            pre-increment or pre-decrement is legal at this point. */
 819   if (curtok == PREINC || curtok == PREDEC)
 820     {
 821       stok = lasttok = curtok;
 822       readtok ();
 823       if (curtok != STR)
 824         /* readtok() catches this */
 825         evalerror (_("identifier expected after pre-increment or pre-decrement"));
 826
 827       v2 = tokval + ((stok == PREINC) ? 1 : -1);
 828       vincdec = itos (v2);
 829       if (noeval == 0)
 830         expr_bind_variable (tokstr, vincdec);
 831       free (vincdec);
 832       val = v2;
 833
 834       curtok = NUM;     /* make sure --x=7 is flagged as an error */
 835       readtok ();
 836     }
 837   else if (curtok == MINUS)
 838     {
 839       readtok ();
 840       val = - exp0 ();
 841     }
 842   else if (curtok == PLUS)
 843     {
 844       readtok ();
 845       val = exp0 ();
 846     }
 847   else if (curtok == LPAR)
 848     {
 849       readtok ();
 850       val = EXP_HIGHEST ();
 851
 852       if (curtok != RPAR) /* ( */
 853         evalerror (_("missing `)'"));
 854
 855       /* Skip over closing paren. */
 856       readtok ();
 857     }
 858   else if ((curtok == NUM) || (curtok == STR))
 859     {
 860       val = tokval;
 861       if (curtok == STR)
 862         {
 863           SAVETOK (&ec);
 864           tokstr = (char *)NULL;        /* keep it from being freed */
 865           noeval = 1;
 866           readtok ();
 867           stok = curtok;
 868
 869           /* post-increment or post-decrement */
 870           if (stok == POSTINC || stok == POSTDEC)
 871             {
 872               /* restore certain portions of EC */
 873               tokstr = ec.tokstr;
 874               noeval = ec.noeval;
 875               lasttok = STR;    /* ec.curtok */
 876
 877               v2 = val + ((stok == POSTINC) ? 1 : -1);
 878               vincdec = itos (v2);
 879               if (noeval == 0)
 880                 expr_bind_variable (tokstr, vincdec);
 881               free (vincdec);
 882               curtok = NUM;     /* make sure x++=7 is flagged as an error */
 883             }
 884           else
 885             {
 886               if (stok == STR)  /* free new tokstr before old one is restored */
 887                 FREE (tokstr);
 888               RESTORETOK (&ec);
 889             }
 890
 891         }
 892
 893       readtok ();
 894     }
 895   else
 896     evalerror (_("syntax error: operand expected"));
 897
 898   return (val);
 899 }
 900
 901 static intmax_t
 902 expr_streval (tok, e)
 903      char *tok;
 904      int e;
 905 {
 906   SHELL_VAR *v;
 907   char *value;
 908   intmax_t tval;
 909
 910   /* [[[[[ */
 911 #if defined (ARRAY_VARS)
 912   v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
 913 #else
 914   v = find_variable (tok);
 915 #endif
 916
 917   if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
 918     {
 919 #if defined (ARRAY_VARS)
 920       value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
 921 #else
 922       value = tok;
 923 #endif
 924
 925       err_unboundvar (value);
 926
 927 #if defined (ARRAY_VARS)
 928       if (e == ']')
 929         FREE (value);   /* array_variable_name returns new memory */
 930 #endif
 931
 932       if (interactive_shell)
 933         {
 934           expr_unwind ();
 935           top_level_cleanup ();
 936           jump_to_top_level (DISCARD);
 937         }
 938       else
 939         jump_to_top_level (FORCE_EOF);
 940     }
 941
 942 #if defined (ARRAY_VARS)
 943   /* Second argument of 0 to get_array_value means that we don't allow
 944      references like array[@].  In this case, get_array_value is just
 945      like get_variable_value in that it does not return newly-allocated
 946      memory or quote the results. */
 947   value = (e == ']') ? get_array_value (tok, 0, (int *)NULL) : get_variable_value (v);
 948 #else
 949   value = get_variable_value (v);
 950 #endif
 951
 952   tval = (value && *value) ? subexpr (value) : 0;
 953
 954   return (tval);
 955 }
 956
 957 static int
 958 _is_multiop (c)
 959      int c;
 960 {
 961   switch (c)
 962     {
 963     case EQEQ:
 964     case NEQ:
 965     case LEQ:
 966     case GEQ:
 967     case LAND:
 968     case LOR:
 969     case LSH:
 970     case RSH:
 971     case OP_ASSIGN:
 972     case COND:
 973     case POWER:
 974     case PREINC:
 975     case PREDEC:
 976     case POSTINC:
 977     case POSTDEC:
 978       return 1;
 979     default:
 980       return 0;
 981     }
 982 }
 983
 984 static int
 985 _is_arithop (c)
 986      int c;
 987 {
 988   switch (c)
 989     {
 990     case EQ:
 991     case GT:
 992     case LT:
 993     case PLUS:
 994     case MINUS:
 995     case MUL:
 996     case DIV:
 997     case MOD:
 998     case NOT:
 999     case LPAR:
1000     case RPAR:
1001     case BAND:
1002     case BOR:
1003     case BXOR:
1004     case BNOT:
1005       return 1;         /* operator tokens */
1006     case QUES:
1007     case COL:
1008     case COMMA:
1009       return 1;         /* questionable */
1010     default:
1011       return 0;         /* anything else is invalid */
1012     }
1013 }
1014
1015 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
1016    next token and puts its value into curtok, while advancing past it.
1017    Updates value of tp.  May also set tokval (for number) or tokstr (for
1018    string). */
1019 static void
1020 readtok ()
1021 {
1022   register char *cp, *xp;
1023   register unsigned char c, c1;
1024   register int e;
1025
1026   /* Skip leading whitespace. */
1027   cp = tp;
1028   c = e = 0;
1029   while (cp && (c = *cp) && (cr_whitespace (c)))
1030     cp++;
1031
1032   if (c)
1033     cp++;
1034
1035   lasttp = tp = cp - 1;
1036
1037   if (c == '\0')
1038     {
1039       lasttok = curtok;
1040       curtok = 0;
1041       tp = cp;
1042       return;
1043     }
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      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 */