1 /* expr.c -- arithmetic expression evaluation. */
3 /* Copyright (C) 1990, 1991 Free Software Foundation, Inc.
5 This file is part of GNU Bash, the Bourne Again SHell.
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 1, or (at your option)
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.
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, 675 Mass Ave, Cambridge, MA 02139, USA. */
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).
25 The following operators are handled, grouped into a set of levels in
26 order of decreasing precedence.
28 "-", "+" [(unary operators)]
42 (Note that most of these operators have special meaning to bash, and an
43 entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
44 that it is passed intact to the evaluator when using `let'. When using
45 the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
46 is treated as if in double quotes.)
48 Sub-expressions within parentheses have a precedence level greater than
49 all of the above levels and are evaluated first. Within a single prece-
50 dence group, evaluation is left-to-right, except for the arithmetic
51 assignment operator (`='), which is evaluated right-to-left (as in C).
53 The expression evaluator returns the value of the expression (assignment
54 statements have as a value what is returned by the RHS). The `let'
55 builtin, on the other hand, returns 0 if the last expression evaluates to
56 a non-zero, and 1 otherwise.
58 Implementation is a recursive-descent parser.
68 #define variable_starter(c) (isletter(c) || (c == '_'))
69 #define variable_character(c) (isletter(c) || (c == '_') || digit(c))
71 /* Because of the $((...)) construct, expressions may include newlines.
72 Here is a macro which accepts newlines, tabs and spaces as whitespace. */
73 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
75 extern char *this_command_name;
77 static char *expression = (char *) NULL; /* The current expression */
78 static char *tp = (char *) NULL; /* token lexical position */
80 static int curtok = 0; /* the current token */
81 static int lasttok = 0; /* the previous token */
82 static int assigntok = 0; /* the OP in OP= */
83 static char *tokstr = (char *) NULL; /* current token string */
84 static int tokval = 0; /* current token value */
85 static jmp_buf evalbuf;
87 static void readtok (); /* lexical analyzer */
88 static long expassign (), exp0 (), exp1 (), exp2 (), exp3 (),
89 exp4 (), exp5 (), expshift (), expland (), explor (),
90 expband (), expbor (), expbxor ();
91 static long strlong ();
92 static void evalerror ();
94 /* A structure defining a single expression context. */
97 char *expression, *tp;
102 /* Global var which contains the stack of expression contexts. */
103 static EXPR_CONTEXT **expr_stack;
104 static int expr_depth = 0; /* Location in the stack. */
105 static int expr_stack_size = 0; /* Number of slots already allocated. */
107 /* Size be which the expression stack grows when neccessary. */
108 #define EXPR_STACK_GROW_SIZE 10
110 /* Maximum amount of recursion allowed. This prevents a non-integer
111 variable such as "num=num+2" from infinitely adding to itself when
112 "let num=num+2" is given. I have to talk to Chet about this hack. */
113 #define MAX_EXPR_RECURSION_LEVEL 1024
115 /* The Tokens. Singing "The Lion Sleeps Tonight". */
117 #define EQEQ 1 /* "==" */
118 #define NEQ 2 /* "!=" */
119 #define LEQ 3 /* "<=" */
120 #define GEQ 4 /* ">=" */
121 #define STR 5 /* string */
122 #define NUM 6 /* number */
123 #define LAND 7 /* "&&" Logical AND */
124 #define LOR 8 /* "||" Logical OR */
125 #define LSH 9 /* "<<" Left SHift */
126 #define RSH 10 /* ">>" Right SHift */
127 #define OP_ASSIGN 11 /* op= expassign as in Posix.2 */
139 #define BAND '&' /* Bitwise AND */
140 #define BOR '|' /* Either Bitwise OR, or what Chet is. */
141 #define BXOR '^' /* Bitwise eXclusive OR. */
142 #define BNOT '~' /* Bitwise NOT; Two's complement. */
144 /* Push and save away the contents of the globals describing the
145 current expression context. */
149 EXPR_CONTEXT *context;
151 context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
153 if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
154 evalerror ("expression recursion level exceeded");
156 if (expr_depth >= expr_stack_size)
158 expr_stack = (EXPR_CONTEXT **)
159 xrealloc (expr_stack, (expr_stack_size += EXPR_STACK_GROW_SIZE)
160 * sizeof (EXPR_CONTEXT *));
163 context->curtok = curtok;
164 context->lasttok = lasttok;
165 context->expression = expression;
167 context->tokval = tokval;
168 context->tokstr = tokstr;
169 expr_stack[expr_depth++] = context;
172 /* Pop the the contents of the expression context stack into the
173 globals describing the current expression context. */
177 EXPR_CONTEXT *context;
180 evalerror ("Recursion stack underflow");
182 context = expr_stack[--expr_depth];
183 curtok = context->curtok;
184 lasttok = context->lasttok;
185 expression = context->expression;
187 tokval = context->tokval;
188 tokstr = context->tokstr;
192 /* Evaluate EXPR, and return the arithmetic result.
194 The `while' loop after the longjmp is caught relies on the above
195 implementation of pushexp and popexp leaving in expr_stack[0] the
196 values that the variables had when the program started. That is,
197 the first things saved are the initial values of the variables that
198 were assigned at program startup or by the compiler. Therefore, it is
199 safe to let the loop terminate when expr_depth == 0, without freeing up
200 any of the expr_depth[0] stuff. */
209 for (p = expr; p && *p && cr_whitespace (*p); p++)
212 if (p == NULL || *p == '\0')
215 /* Save the value of evalbuf to protect it around possible recursive
216 calls to evalexp (). */
217 xbcopy ((char *)evalbuf, (char *)old_evalbuf, sizeof (jmp_buf));
219 if (setjmp (evalbuf))
221 if (tokstr) /* Clean up local allocation. */
229 if (expr_stack[expr_depth]->tokstr)
230 free (expr_stack[expr_depth]->tokstr);
232 if (expr_stack[expr_depth]->expression)
233 free (expr_stack[expr_depth]->expression);
235 longjmp (top_level, DISCARD);
239 curtok = lasttok = 0;
240 expression = savestring (expr);
243 tokstr = (char *)NULL;
251 evalerror ("syntax error in expression");
260 /* Restore the value of evalbuf so that any subsequent longjmp calls
261 will have a valid location to jump to. */
262 xbcopy ((char *)old_evalbuf, (char *)evalbuf, sizeof (jmp_buf));
267 /* Bind/create a shell variable with the name LHS to the RHS.
268 This creates or modifies a variable such that it is an integer.
270 This should really be in variables.c, but it is here so that all of the
271 expression evaluation stuff is localized. Since we don't want any
272 recursive evaluation from bind_variable() (possible without this code,
273 since bind_variable() calls the evaluator for variables with the integer
274 attribute set), we temporarily turn off the integer attribute for each
275 variable we set here, then turn it back on after binding as necessary. */
278 bind_int_variable (lhs, rhs)
281 register SHELL_VAR *v;
284 v = find_variable (lhs);
287 isint = integer_p (v);
288 v->attributes &= ~att_integer;
291 v = bind_variable (lhs, rhs);
293 v->attributes |= att_integer;
303 if (curtok == EQ || curtok == OP_ASSIGN)
305 int special = curtok == OP_ASSIGN;
310 evalerror ("attempted expassign to non-variable");
314 op = assigntok; /* a OP= b */
318 lhs = savestring (tokstr);
320 value = expassign ();
354 evalerror ("bug: bad expassign token %d", assigntok);
361 bind_int_variable (lhs, rhs);
365 tokstr = (char *)NULL; /* For freeing on errors. */
374 register long val1, val2;
378 while (curtok == LOR)
392 register long val1, val2;
396 while (curtok == LAND)
410 register long val1, val2;
414 while (curtok == BOR)
428 register long val1, val2;
432 while (curtok == BXOR)
446 register long val1, val2;
450 while (curtok == BAND)
463 register long val1, val2;
467 while ((curtok == EQEQ) || (curtok == NEQ))
474 val1 = (val1 == val2);
476 val1 = (val1 != val2);
484 register long val1, val2;
487 while ((curtok == LEQ) ||
509 /* Left and right shifts. */
513 register long val1, val2;
517 while ((curtok == LSH) || (curtok == RSH))
536 register long val1, val2;
540 while ((curtok == PLUS) || (curtok == MINUS))
549 else if (op == MINUS)
558 register long val1, val2;
562 while ((curtok == MUL) ||
572 if (((op == DIV) || (op == MOD)) && (val2 == 0))
573 evalerror ("division by 0");
595 else if (curtok == BNOT)
609 register long val = 0L;
616 else if (curtok == PLUS)
621 else if (curtok == LPAR)
627 evalerror ("missing `)'");
629 /* Skip over closing paren. */
632 else if ((curtok == NUM) || (curtok == STR))
638 evalerror ("syntax error in expression");
643 /* Lexical analyzer/token reader for the expression evaluator. Reads the
644 next token and puts its value into curtok, while advancing past it.
645 Updates value of tp. May also set tokval (for number) or tokstr (for
650 register char *cp = tp;
653 /* Skip leading whitespace. */
655 while (cp && (c = *cp) && (cr_whitespace (c)))
661 lasttp = tp = cp - 1;
671 if (variable_starter (c))
673 /* Semi-bogus K*rn shell compatibility feature -- variable
674 names not preceded with a dollar sign are shell variables. */
677 while (variable_character (c))
685 tokstr = savestring (tp);
686 value = get_string_value (tokstr);
689 tokval = evalexp (value);
699 while (digit (c) || isletter (c) || c == '#')
705 tokval = strlong (tp);
713 if ((c == EQ) && (c1 == EQ))
715 else if ((c == NOT) && (c1 == EQ))
717 else if ((c == GT) && (c1 == EQ))
719 else if ((c == LT) && (c1 == EQ))
721 else if ((c == LT) && (c1 == LT))
723 if (*cp == '=') /* a <<= b */
732 else if ((c == GT) && (c1 == GT))
736 assigntok = RSH; /* a >>= b */
743 else if ((c == BAND) && (c1 == BAND))
745 else if ((c == BOR) && (c1 == BOR))
747 else if (c1 == EQ && member(c, "*/%+-&^|"))
749 assigntok = c; /* a OP= b */
753 cp--; /* `unget' the character */
766 name = this_command_name;
768 name = get_name_for_error ();
769 for (t = expression; whitespace (*t); t++)
771 fprintf (stderr, "%s: %s: %s (remainder of expression is \"%s\")\n",
773 msg, (lasttp && *lasttp) ? lasttp : "");
774 longjmp (evalbuf, 1);
777 /* Convert a string to a long integer, with an arbitrary base.
780 Anything else: [base#]number (this is from the ISO Pascal spec). */
785 register char *s = num;
790 if (s == NULL || *s == '\0')
797 if (s == NULL || *s == '\0')
801 if (*s == 'x' || *s == 'X')
810 for (c = *s++; c; c = *s++)
816 /* Illegal base specifications are silently reset to base 10.
817 I don't think that this is a good idea? */
818 if (base < 2 || base > 36)
824 if (isletter(c) || digit(c))
828 else if (c >= 'a' && c <= 'z')
830 else if (c >= 'A' && c <= 'Z')
834 evalerror ("value too great for base");
836 val = (val * base) + c;
844 #if defined (EXPR_TEST)
857 return (realloc (s, n));
860 SHELL_VAR *find_variable () { return 0;}
861 SHELL_VAR *bind_variable () { return 0; }
863 char *get_string_value () { return 0; }
874 if (setjmp (top_level))
877 for (i = 1; i < argc; i++)
879 v = evalexp (argv[i]);
880 printf ("'%s' -> %ld\n", argv[i], v);
886 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
889 fprintf (stderr, "expr: ");
890 fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
891 fprintf (stderr, "\n");
902 #endif /* EXPR_TEST */