expr.c

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