expr.c

   1 /* expr.c -- arithmetic expression evaluation. */
   2
   3 /* Copyright (C) 1990, 1991 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 long 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
  46  (Note that most of these operators have special meaning to bash, and an
  47  entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
  48  that it is passed intact to the evaluator when using `let'.  When using
  49  the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
  50  is treated as if in double quotes.)
  51
  52  Sub-expressions within parentheses have a precedence level greater than
  53  all of the above levels and are evaluated first.  Within a single prece-
  54  dence group, evaluation is left-to-right, except for the arithmetic
  55  assignment operator (`='), which is evaluated right-to-left (as in C).
  56
  57  The expression evaluator returns the value of the expression (assignment
  58  statements have as a value what is returned by the RHS).  The `let'
  59  builtin, on the other hand, returns 0 if the last expression evaluates to
  60  a non-zero, and 1 otherwise.
  61
  62  Implementation is a recursive-descent parser.
  63
  64  Chet Ramey
  65  chet@ins.CWRU.Edu
  66 */
  67
  68 #include "config.h"
  69
  70 #include <stdio.h>
  71 #include "bashansi.h"
  72
  73 #if defined (HAVE_UNISTD_H)
  74 #  ifdef _MINIX
  75 #    include <sys/types.h>
  76 #  endif
  77 #  include <unistd.h>
  78 #endif
  79
  80 #include "chartypes.h"
  81
  82 #include "shell.h"
  83
  84 /* Because of the $((...)) construct, expressions may include newlines.
  85    Here is a macro which accepts newlines, tabs and spaces as whitespace. */
  86 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
  87
  88 /* Size be which the expression stack grows when neccessary. */
  89 #define EXPR_STACK_GROW_SIZE 10
  90
  91 /* Maximum amount of recursion allowed.  This prevents a non-integer
  92    variable such as "num=num+2" from infinitely adding to itself when
  93    "let num=num+2" is given. */
  94 #define MAX_EXPR_RECURSION_LEVEL 1024
  95
  96 /* The Tokens.  Singing "The Lion Sleeps Tonight". */
  97
  98 #define EQEQ    1       /* "==" */
  99 #define NEQ     2       /* "!=" */
 100 #define LEQ     3       /* "<=" */
 101 #define GEQ     4       /* ">=" */
 102 #define STR     5       /* string */
 103 #define NUM     6       /* number */
 104 #define LAND    7       /* "&&" Logical AND */
 105 #define LOR     8       /* "||" Logical OR */
 106 #define LSH     9       /* "<<" Left SHift */
 107 #define RSH    10       /* ">>" Right SHift */
 108 #define OP_ASSIGN 11    /* op= expassign as in Posix.2 */
 109 #define COND    12      /* exp1 ? exp2 : exp3 */
 110 #define POWER   13      /* exp1**exp2 */
 111 #define PREINC  14      /* ++var */
 112 #define PREDEC  15      /* --var */
 113 #define POSTINC 16      /* var++ */
 114 #define POSTDEC 17      /* var-- */
 115 #define EQ      '='
 116 #define GT      '>'
 117 #define LT      '<'
 118 #define PLUS    '+'
 119 #define MINUS   '-'
 120 #define MUL     '*'
 121 #define DIV     '/'
 122 #define MOD     '%'
 123 #define NOT     '!'
 124 #define LPAR    '('
 125 #define RPAR    ')'
 126 #define BAND    '&'     /* Bitwise AND */
 127 #define BOR     '|'     /* Bitwise OR. */
 128 #define BXOR    '^'     /* Bitwise eXclusive OR. */
 129 #define BNOT    '~'     /* Bitwise NOT; Two's complement. */
 130 #define QUES    '?'
 131 #define COL     ':'
 132 #define COMMA   ','
 133
 134 /* This should be the function corresponding to the operator with the
 135    highest precedence. */
 136 #define EXP_HIGHEST     expcomma
 137
 138 static char     *expression;    /* The current expression */
 139 static char     *tp;            /* token lexical position */
 140 static char     *lasttp;        /* pointer to last token position */
 141 static int      curtok;         /* the current token */
 142 static int      lasttok;        /* the previous token */
 143 static int      assigntok;      /* the OP in OP= */
 144 static char     *tokstr;        /* current token string */
 145 static long     tokval;         /* current token value */
 146 static int      noeval;         /* set to 1 if no assignment to be done */
 147 static procenv_t evalbuf;
 148
 149 static void     readtok __P((void));    /* lexical analyzer */
 150 static long     strlong __P((char *));
 151 static void     evalerror __P((char *));
 152
 153 static void     pushexp __P((void));
 154 static void     popexp __P((void));
 155
 156 static long     subexpr __P((char *));
 157
 158 static long     expcomma __P((void));
 159 static long     expassign __P((void));
 160 static long     expcond __P((void));
 161 static long     explor __P((void));
 162 static long     expland __P((void));
 163 static long     expbor __P((void));
 164 static long     expbxor __P((void));
 165 static long     expband __P((void));
 166 static long     exp5 __P((void));
 167 static long     exp4 __P((void));
 168 static long     expshift __P((void));
 169 static long     exp3 __P((void));
 170 static long     exp2 __P((void));
 171 static long     exppower __P((void));
 172 static long     exp1 __P((void));
 173 static long     exp0 __P((void));
 174
 175 /* A structure defining a single expression context. */
 176 typedef struct {
 177   int curtok, lasttok;
 178   char *expression, *tp, *lasttp;
 179   long tokval;
 180   char *tokstr;
 181   int noeval;
 182 } EXPR_CONTEXT;
 183
 184 #ifdef INCLUDE_UNUSED
 185 /* Not used yet. */
 186 typedef struct {
 187   char *tokstr;
 188   long tokval;
 189 } LVALUE;
 190 #endif
 191
 192 /* Global var which contains the stack of expression contexts. */
 193 static EXPR_CONTEXT **expr_stack;
 194 static int expr_depth;             /* Location in the stack. */
 195 static int expr_stack_size;        /* Number of slots already allocated. */
 196
 197 extern char *this_command_name;
 198
 199 #define SAVETOK(X) \
 200   do { \
 201     (X)->curtok = curtok; \
 202     (X)->lasttok = lasttok; \
 203     (X)->tp = tp; \
 204     (X)->lasttp = lasttp; \
 205     (X)->tokval = tokval; \
 206     (X)->tokstr = tokstr; \
 207     (X)->noeval = noeval; \
 208   } while (0)
 209
 210 #define RESTORETOK(X) \
 211   do { \
 212     curtok = (X)->curtok; \
 213     lasttok = (X)->lasttok; \
 214     tp = (X)->tp; \
 215     lasttp = (X)->lasttp; \
 216     tokval = (X)->tokval; \
 217     tokstr = (X)->tokstr; \
 218     noeval = (X)->noeval; \
 219   } while (0)
 220
 221 /* Push and save away the contents of the globals describing the
 222    current expression context. */
 223 static void
 224 pushexp ()
 225 {
 226   EXPR_CONTEXT *context;
 227
 228   if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
 229     evalerror ("expression recursion level exceeded");
 230
 231   if (expr_depth >= expr_stack_size)
 232     {
 233       expr_stack_size += EXPR_STACK_GROW_SIZE;
 234       expr_stack = (EXPR_CONTEXT **)xrealloc (expr_stack, expr_stack_size * sizeof (EXPR_CONTEXT *));
 235     }
 236
 237   context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
 238
 239   context->expression = expression;
 240   SAVETOK(context);
 241
 242   expr_stack[expr_depth++] = context;
 243 }
 244
 245 /* Pop the the contents of the expression context stack into the
 246    globals describing the current expression context. */
 247 static void
 248 popexp ()
 249 {
 250   EXPR_CONTEXT *context;
 251
 252   if (expr_depth == 0)
 253     evalerror ("recursion stack underflow");
 254
 255   context = expr_stack[--expr_depth];
 256
 257   expression = context->expression;
 258   RESTORETOK (context);
 259
 260   free (context);
 261 }
 262
 263 /* Evaluate EXPR, and return the arithmetic result.  If VALIDP is
 264    non-null, a zero is stored into the location to which it points
 265    if the expression is invalid, non-zero otherwise.  If a non-zero
 266    value is returned in *VALIDP, the return value of evalexp() may
 267    be used.
 268
 269    The `while' loop after the longjmp is caught relies on the above
 270    implementation of pushexp and popexp leaving in expr_stack[0] the
 271    values that the variables had when the program started.  That is,
 272    the first things saved are the initial values of the variables that
 273    were assigned at program startup or by the compiler.  Therefore, it is
 274    safe to let the loop terminate when expr_depth == 0, without freeing up
 275    any of the expr_depth[0] stuff. */
 276 long
 277 evalexp (expr, validp)
 278      char *expr;
 279      int *validp;
 280 {
 281   long val;
 282 #if 0
 283   procenv_t old_evalbuf;
 284 #endif
 285
 286   val = 0;
 287
 288 #if 0
 289   /* Save the value of evalbuf to protect it around possible recursive
 290      calls to evalexp (). */
 291   COPY_PROCENV (evalbuf, old_evalbuf);
 292 #endif
 293
 294   if (setjmp (evalbuf))
 295     {
 296       FREE (tokstr);
 297       FREE (expression);
 298       tokstr = expression = (char *)NULL;
 299
 300       while (--expr_depth > 0)
 301         {
 302           if (expr_stack[expr_depth]->tokstr)
 303             free (expr_stack[expr_depth]->tokstr);
 304
 305           if (expr_stack[expr_depth]->expression)
 306             free (expr_stack[expr_depth]->expression);
 307
 308           free (expr_stack[expr_depth]);
 309         }
 310       free (expr_stack[expr_depth]);    /* free the allocated EXPR_CONTEXT */
 311
 312       if (validp)
 313         *validp = 0;
 314       return (0);
 315     }
 316
 317   val = subexpr (expr);
 318
 319 #if 0
 320   /* Restore the value of evalbuf so that any subsequent longjmp calls
 321      will have a valid location to jump to. */
 322   COPY_PROCENV (old_evalbuf, evalbuf);
 323 #endif
 324
 325   if (validp)
 326     *validp = 1;
 327
 328   return (val);
 329 }
 330
 331 static long
 332 subexpr (expr)
 333      char *expr;
 334 {
 335   long val;
 336   char *p;
 337
 338   for (p = expr; p && *p && cr_whitespace (*p); p++)
 339     ;
 340
 341   if (p == NULL || *p == '\0')
 342     return (0);
 343
 344   pushexp ();
 345   curtok = lasttok = 0;
 346   expression = savestring (expr);
 347   tp = expression;
 348
 349   tokstr = (char *)NULL;
 350   tokval = 0;
 351
 352   readtok ();
 353
 354   val = EXP_HIGHEST ();
 355
 356   if (curtok != 0)
 357     evalerror ("syntax error in expression");
 358
 359   FREE (tokstr);
 360   FREE (expression);
 361
 362   popexp ();
 363
 364   return val;
 365 }
 366
 367 static long
 368 expcomma ()
 369 {
 370   register long value;
 371
 372   value = expassign ();
 373   while (curtok == COMMA)
 374     {
 375       readtok ();
 376       value = expassign ();
 377     }
 378
 379   return value;
 380 }
 381
 382 static long
 383 expassign ()
 384 {
 385   register long value;
 386   char *lhs, *rhs;
 387
 388   value = expcond ();
 389   if (curtok == EQ || curtok == OP_ASSIGN)
 390     {
 391       int special, op;
 392       long lvalue;
 393
 394       special = curtok == OP_ASSIGN;
 395
 396       if (lasttok != STR)
 397         evalerror ("attempted assignment to non-variable");
 398
 399       if (special)
 400         {
 401           op = assigntok;               /* a OP= b */
 402           lvalue = value;
 403         }
 404
 405       lhs = savestring (tokstr);
 406       readtok ();
 407       value = expassign ();
 408
 409       if (special)
 410         {
 411           switch (op)
 412             {
 413             case MUL:
 414               lvalue *= value;
 415               break;
 416             case DIV:
 417               lvalue /= value;
 418               break;
 419             case MOD:
 420               lvalue %= value;
 421               break;
 422             case PLUS:
 423               lvalue += value;
 424               break;
 425             case MINUS:
 426               lvalue -= value;
 427               break;
 428             case LSH:
 429               lvalue <<= value;
 430               break;
 431             case RSH:
 432               lvalue >>= value;
 433               break;
 434             case BAND:
 435               lvalue &= value;
 436               break;
 437             case BOR:
 438               lvalue |= value;
 439               break;
 440             case BXOR:
 441               lvalue ^= value;
 442               break;
 443             default:
 444               free (lhs);
 445               evalerror ("bug: bad expassign token");
 446               break;
 447             }
 448           value = lvalue;
 449         }
 450
 451       rhs = itos (value);
 452       if (noeval == 0)
 453         (void)bind_int_variable (lhs, rhs);
 454       free (rhs);
 455       free (lhs);
 456       FREE (tokstr);
 457       tokstr = (char *)NULL;            /* For freeing on errors. */
 458     }
 459   return (value);
 460 }
 461
 462 /* Conditional expression (expr?expr:expr) */
 463 static long
 464 expcond ()
 465 {
 466   long cval, val1, val2, rval;
 467   int set_noeval;
 468
 469   set_noeval = 0;
 470   rval = cval = explor ();
 471   if (curtok == QUES)           /* found conditional expr */
 472     {
 473       readtok ();
 474       if (curtok == 0 || curtok == COL)
 475         evalerror ("expression expected");
 476       if (cval == 0)
 477         {
 478           set_noeval = 1;
 479           noeval++;
 480         }
 481
 482       val1 = EXP_HIGHEST ();
 483
 484       if (set_noeval)
 485         noeval--;
 486       if (curtok != COL)
 487         evalerror ("`:' expected for conditional expression");
 488       readtok ();
 489       if (curtok == 0)
 490         evalerror ("expression expected");
 491       set_noeval = 0;
 492       if (cval)
 493         {
 494           set_noeval = 1;
 495           noeval++;
 496         }
 497       val2 = explor ();
 498       if (set_noeval)
 499         noeval--;
 500       rval = cval ? val1 : val2;
 501       lasttok = COND;
 502     }
 503   return rval;
 504 }
 505
 506 /* Logical OR. */
 507 static long
 508 explor ()
 509 {
 510   register long val1, val2;
 511   int set_noeval;
 512
 513   val1 = expland ();
 514
 515   while (curtok == LOR)
 516     {
 517       set_noeval = 0;
 518       if (val1 != 0)
 519         {
 520           noeval++;
 521           set_noeval = 1;
 522         }
 523       readtok ();
 524       val2 = expland ();
 525       if (set_noeval)
 526         noeval--;
 527       val1 = val1 || val2;
 528       lasttok = LOR;
 529     }
 530
 531   return (val1);
 532 }
 533
 534 /* Logical AND. */
 535 static long
 536 expland ()
 537 {
 538   register long val1, val2;
 539   int set_noeval;
 540
 541   val1 = expbor ();
 542
 543   while (curtok == LAND)
 544     {
 545       set_noeval = 0;
 546       if (val1 == 0)
 547         {
 548           set_noeval = 1;
 549           noeval++;
 550         }
 551       readtok ();
 552       val2 = expbor ();
 553       if (set_noeval)
 554         noeval--;
 555       val1 = val1 && val2;
 556       lasttok = LAND;
 557     }
 558
 559   return (val1);
 560 }
 561
 562 /* Bitwise OR. */
 563 static long
 564 expbor ()
 565 {
 566   register long val1, val2;
 567
 568   val1 = expbxor ();
 569
 570   while (curtok == BOR)
 571     {
 572       readtok ();
 573       val2 = expbxor ();
 574       val1 = val1 | val2;
 575     }
 576
 577   return (val1);
 578 }
 579
 580 /* Bitwise XOR. */
 581 static long
 582 expbxor ()
 583 {
 584   register long val1, val2;
 585
 586   val1 = expband ();
 587
 588   while (curtok == BXOR)
 589     {
 590       readtok ();
 591       val2 = expband ();
 592       val1 = val1 ^ val2;
 593     }
 594
 595   return (val1);
 596 }
 597
 598 /* Bitwise AND. */
 599 static long
 600 expband ()
 601 {
 602   register long val1, val2;
 603
 604   val1 = exp5 ();
 605
 606   while (curtok == BAND)
 607     {
 608       readtok ();
 609       val2 = exp5 ();
 610       val1 = val1 & val2;
 611     }
 612
 613   return (val1);
 614 }
 615
 616 static long
 617 exp5 ()
 618 {
 619   register long val1, val2;
 620
 621   val1 = exp4 ();
 622
 623   while ((curtok == EQEQ) || (curtok == NEQ))
 624     {
 625       int op = curtok;
 626
 627       readtok ();
 628       val2 = exp4 ();
 629       if (op == EQEQ)
 630         val1 = (val1 == val2);
 631       else if (op == NEQ)
 632         val1 = (val1 != val2);
 633     }
 634   return (val1);
 635 }
 636
 637 static long
 638 exp4 ()
 639 {
 640   register long val1, val2;
 641
 642   val1 = expshift ();
 643   while ((curtok == LEQ) ||
 644          (curtok == GEQ) ||
 645          (curtok == LT) ||
 646          (curtok == GT))
 647     {
 648       int op = curtok;
 649
 650       readtok ();
 651       val2 = expshift ();
 652
 653       if (op == LEQ)
 654         val1 = val1 <= val2;
 655       else if (op == GEQ)
 656         val1 = val1 >= val2;
 657       else if (op == LT)
 658         val1 = val1 < val2;
 659       else                      /* (op == GT) */
 660         val1 = val1 > val2;
 661     }
 662   return (val1);
 663 }
 664
 665 /* Left and right shifts. */
 666 static long
 667 expshift ()
 668 {
 669   register long val1, val2;
 670
 671   val1 = exp3 ();
 672
 673   while ((curtok == LSH) || (curtok == RSH))
 674     {
 675       int op = curtok;
 676
 677       readtok ();
 678       val2 = exp3 ();
 679
 680       if (op == LSH)
 681         val1 = val1 << val2;
 682       else
 683         val1 = val1 >> val2;
 684     }
 685
 686   return (val1);
 687 }
 688
 689 static long
 690 exp3 ()
 691 {
 692   register long val1, val2;
 693
 694   val1 = exp2 ();
 695
 696   while ((curtok == PLUS) || (curtok == MINUS))
 697     {
 698       int op = curtok;
 699
 700       readtok ();
 701       val2 = exp2 ();
 702
 703       if (op == PLUS)
 704         val1 += val2;
 705       else if (op == MINUS)
 706         val1 -= val2;
 707     }
 708   return (val1);
 709 }
 710
 711 static long
 712 exp2 ()
 713 {
 714   register long val1, val2;
 715
 716   val1 = exppower ();
 717
 718   while ((curtok == MUL) ||
 719          (curtok == DIV) ||
 720          (curtok == MOD))
 721     {
 722       int op = curtok;
 723
 724       readtok ();
 725
 726       val2 = exppower ();
 727
 728       if (((op == DIV) || (op == MOD)) && (val2 == 0))
 729         evalerror ("division by 0");
 730
 731       if (op == MUL)
 732         val1 *= val2;
 733       else if (op == DIV)
 734         val1 /= val2;
 735       else if (op == MOD)
 736         val1 %= val2;
 737     }
 738   return (val1);
 739 }
 740
 741 static long
 742 exppower ()
 743 {
 744   register long val1, val2, c;
 745
 746   val1 = exp1 ();
 747   if (curtok == POWER)
 748     {
 749       readtok ();
 750       val2 = exp1 ();
 751       if (val2 == 0)
 752         return (1);
 753       if (val2 < 0)
 754         evalerror ("exponent less than 0");
 755       for (c = 1; val2--; c *= val1)
 756         ;
 757       val1 = c;
 758     }
 759   return (val1);
 760 }
 761
 762 static long
 763 exp1 ()
 764 {
 765   register long val;
 766
 767   if (curtok == NOT)
 768     {
 769       readtok ();
 770       val = !exp1 ();
 771     }
 772   else if (curtok == BNOT)
 773     {
 774       readtok ();
 775       val = ~exp1 ();
 776     }
 777   else
 778     val = exp0 ();
 779
 780   return (val);
 781 }
 782
 783 static long
 784 exp0 ()
 785 {
 786   register long val = 0, v2;
 787   char *vincdec;
 788   int stok;
 789
 790   /* XXX - might need additional logic here to decide whether or not
 791            pre-increment or pre-decrement is legal at this point. */
 792   if (curtok == PREINC || curtok == PREDEC)
 793     {
 794       stok = lasttok = curtok;
 795       readtok ();
 796       if (curtok != STR)
 797         /* readtok() catches this */
 798         evalerror ("identifier expected after pre-increment or pre-decrement");
 799
 800       v2 = tokval + ((stok == PREINC) ? 1 : -1);
 801       vincdec = itos (v2);
 802       if (noeval == 0)
 803         (void)bind_int_variable (tokstr, vincdec);
 804       free (vincdec);
 805       val = v2;
 806
 807       curtok = NUM;     /* make sure --x=7 is flagged as an error */
 808       readtok ();
 809     }
 810   else if (curtok == MINUS)
 811     {
 812       readtok ();
 813       val = - exp0 ();
 814     }
 815   else if (curtok == PLUS)
 816     {
 817       readtok ();
 818       val = exp0 ();
 819     }
 820   else if (curtok == LPAR)
 821     {
 822       readtok ();
 823       val = EXP_HIGHEST ();
 824
 825       if (curtok != RPAR)
 826         evalerror ("missing `)'");
 827
 828       /* Skip over closing paren. */
 829       readtok ();
 830     }
 831   else if ((curtok == NUM) || (curtok == STR))
 832     {
 833       val = tokval;
 834       if (curtok == STR && (*tp == '+' || *tp == '-') && tp[1] == *tp &&
 835                 (tp[2] == '\0' || (ISALNUM ((unsigned char)tp[2]) == 0)))
 836         {
 837           /* post-increment or post-decrement */
 838           v2 = val + ((*tp == '+') ? 1 : -1);
 839           vincdec = itos (v2);
 840           if (noeval == 0)
 841             (void)bind_int_variable (tokstr, vincdec);
 842           free (vincdec);
 843           tp += 2;
 844           curtok = NUM; /* make sure x++=7 is flagged as an error */
 845         }
 846
 847       readtok ();
 848     }
 849   else
 850     evalerror ("syntax error: operand expected");
 851
 852   return (val);
 853 }
 854
 855 /* Lexical analyzer/token reader for the expression evaluator.  Reads the
 856    next token and puts its value into curtok, while advancing past it.
 857    Updates value of tp.  May also set tokval (for number) or tokstr (for
 858    string). */
 859 static void
 860 readtok ()
 861 {
 862   register char *cp;
 863   register unsigned char c, c1;
 864   register int e;
 865
 866   /* Skip leading whitespace. */
 867   cp = tp;
 868   c = e = 0;
 869   while (cp && (c = *cp) && (cr_whitespace (c)))
 870     cp++;
 871
 872   if (c)
 873     cp++;
 874
 875   lasttp = tp = cp - 1;
 876
 877   if (c == '\0')
 878     {
 879       lasttok = curtok;
 880       curtok = 0;
 881       tp = cp;
 882       return;
 883     }
 884
 885   if (legal_variable_starter (c))
 886     {
 887       /* variable names not preceded with a dollar sign are shell variables. */
 888       char *value, *savecp;
 889       EXPR_CONTEXT ec;
 890       int peektok;
 891
 892       while (legal_variable_char (c))
 893         c = *cp++;
 894
 895       c = *--cp;
 896
 897 #if defined (ARRAY_VARS)
 898       if (c == '[')
 899         {
 900           e = skipsubscript (cp, 0);
 901           if (cp[e] == ']')
 902             {
 903               cp += e + 1;
 904               c = *cp;
 905               e = ']';
 906             }
 907           else
 908             evalerror ("bad array subscript");
 909         }
 910 #endif /* ARRAY_VARS */
 911
 912       *cp = '\0';
 913       FREE (tokstr);
 914       tokstr = savestring (tp);
 915       *cp = c;
 916
 917       SAVETOK (&ec);
 918       tokstr = (char *)NULL;    /* keep it from being freed */
 919       tp = savecp = cp;
 920       noeval = 1;
 921       readtok ();
 922       peektok = curtok;
 923       if (peektok == STR)       /* free new tokstr before old one is restored */
 924         FREE (tokstr);
 925       RESTORETOK (&ec);
 926       cp = savecp;
 927
 928       /* The tests for PREINC and PREDEC aren't strictly correct, but they
 929          preserve old behavior if a construct like --x=9 is given. */
 930       if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
 931         {
 932 #if defined (ARRAY_VARS)
 933           value = (e == ']') ? get_array_value (tokstr, 0) : get_string_value (tokstr);
 934 #else
 935           value = get_string_value (tokstr);
 936 #endif
 937
 938           tokval = (value && *value) ? subexpr (value) : 0;
 939
 940 #if defined (ARRAY_VARS)
 941           if (e == ']')
 942             FREE (value);       /* get_array_value returns newly-allocated memory */
 943 #endif
 944         }
 945       else
 946         tokval = 0;
 947
 948       lasttok = curtok;
 949       curtok = STR;
 950     }
 951   else if (DIGIT(c))
 952     {
 953       while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
 954         c = *cp++;
 955
 956       c = *--cp;
 957       *cp = '\0';
 958
 959       tokval = strlong (tp);
 960       *cp = c;
 961       lasttok = curtok;
 962       curtok = NUM;
 963     }
 964   else
 965     {
 966       c1 = *cp++;
 967       if ((c == EQ) && (c1 == EQ))
 968         c = EQEQ;
 969       else if ((c == NOT) && (c1 == EQ))
 970         c = NEQ;
 971       else if ((c == GT) && (c1 == EQ))
 972         c = GEQ;
 973       else if ((c == LT) && (c1 == EQ))
 974         c = LEQ;
 975       else if ((c == LT) && (c1 == LT))
 976         {
 977           if (*cp == '=')       /* a <<= b */
 978             {
 979               assigntok = LSH;
 980               c = OP_ASSIGN;
 981               cp++;
 982             }
 983           else
 984             c = LSH;
 985         }
 986       else if ((c == GT) && (c1 == GT))
 987         {
 988           if (*cp == '=')
 989             {
 990               assigntok = RSH;  /* a >>= b */
 991               c = OP_ASSIGN;
 992               cp++;
 993             }
 994           else
 995             c = RSH;
 996         }
 997       else if ((c == BAND) && (c1 == BAND))
 998         c = LAND;
 999       else if ((c == BOR) && (c1 == BOR))
1000         c = LOR;
1001       else if ((c == '*') && (c1 == '*'))
1002         c = POWER;
1003       else if ((c == '-') && (c1 == '-') && legal_variable_starter ((unsigned char)*cp))
1004         c = PREDEC;
1005       else if ((c == '+') && (c1 == '+') && legal_variable_starter ((unsigned char)*cp))
1006         c = PREINC;
1007       else if (c1 == EQ && member (c, "*/%+-&^|"))
1008         {
1009           assigntok = c;        /* a OP= b */
1010           c = OP_ASSIGN;
1011         }
1012       else
1013         cp--;                   /* `unget' the character */
1014       lasttok = curtok;
1015       curtok = c;
1016     }
1017   tp = cp;
1018 }
1019
1020 static void
1021 evalerror (msg)
1022      char *msg;
1023 {
1024   char *name, *t;
1025
1026   name = this_command_name;
1027   for (t = expression; whitespace (*t); t++)
1028     ;
1029   internal_error ("%s%s%s: %s (error token is \"%s\")",
1030                    name ? name : "", name ? ": " : "", t,
1031                    msg, (lasttp && *lasttp) ? lasttp : "");
1032   longjmp (evalbuf, 1);
1033 }
1034
1035 /* Convert a string to a long integer, with an arbitrary base.
1036    0nnn -> base 8
1037    0[Xx]nn -> base 16
1038    Anything else: [base#]number (this is implemented to match ksh93)
1039
1040    Base may be >=2 and <=64.  If base is <= 36, the numbers are drawn
1041    from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1042    interchangably.  If base is > 36 and <= 64, the numbers are drawn
1043    from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, _ = 62, @ = 63 --
1044    you get the picture). */
1045
1046 static long
1047 strlong (num)
1048      char *num;
1049 {
1050   register char *s;
1051   register unsigned char c;
1052   int base, foundbase;
1053   long val;
1054
1055   s = num;
1056
1057   base = 10;
1058   foundbase = 0;
1059   if (*s == '0')
1060     {
1061       s++;
1062
1063       if (*s == '\0')
1064         return 0;
1065
1066        /* Base 16? */
1067       if (*s == 'x' || *s == 'X')
1068         {
1069           base = 16;
1070           s++;
1071         }
1072       else
1073         base = 8;
1074       foundbase++;
1075     }
1076
1077   val = 0;
1078   for (c = *s++; c; c = *s++)
1079     {
1080       if (c == '#')
1081         {
1082           if (foundbase)
1083             evalerror ("bad number");
1084
1085           /* Illegal base specifications raise an evaluation error. */
1086           if (val < 2 || val > 64)
1087             evalerror ("illegal arithmetic base");
1088
1089           base = val;
1090           val = 0;
1091           foundbase++;
1092         }
1093       else if (ISALNUM(c) || (c == '_') || (c == '@'))
1094         {
1095           if (DIGIT(c))
1096             c = TODIGIT(c);
1097           else if (c >= 'a' && c <= 'z')
1098             c -= 'a' - 10;
1099           else if (c >= 'A' && c <= 'Z')
1100             c -= 'A' - ((base <= 36) ? 10 : 36);
1101           else if (c == '@')
1102             c = 62;
1103           else if (c == '_')
1104             c = 63;
1105
1106           if (c >= base)
1107             evalerror ("value too great for base");
1108
1109           val = (val * base) + c;
1110         }
1111       else
1112         break;
1113     }
1114   return (val);
1115 }
1116
1117 #if defined (EXPR_TEST)
1118 void *
1119 xmalloc (n)
1120      int n;
1121 {
1122   return (malloc (n));
1123 }
1124
1125 void *
1126 xrealloc (s, n)
1127      char *s;
1128      int n;
1129 {
1130   return (realloc (s, n));
1131 }
1132
1133 SHELL_VAR *find_variable () { return 0;}
1134 SHELL_VAR *bind_variable () { return 0; }
1135
1136 char *get_string_value () { return 0; }
1137
1138 procenv_t top_level;
1139
1140 main (argc, argv)
1141      int argc;
1142      char **argv;
1143 {
1144   register int i;
1145   long v;
1146   int expok;
1147
1148   if (setjmp (top_level))
1149     exit (0);
1150
1151   for (i = 1; i < argc; i++)
1152     {
1153       v = evalexp (argv[i], &expok);
1154       if (expok == 0)
1155         fprintf (stderr, "%s: expression error\n", argv[i]);
1156       else
1157         printf ("'%s' -> %ld\n", argv[i], v);
1158     }
1159   exit (0);
1160 }
1161
1162 int
1163 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1164      char *format;
1165 {
1166   fprintf (stderr, "expr: ");
1167   fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1168   fprintf (stderr, "\n");
1169   return 0;
1170 }
1171
1172 char *
1173 itos (n)
1174      long n;
1175 {
1176   return ("42");
1177 }
1178
1179 #endif /* EXPR_TEST */