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 2, 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, 59 Temple Place, Suite 330, Boston, MA 02111 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 "id++", "id--" [post-increment and post-decrement]
29 "++id", "--id" [pre-increment and pre-decrement]
30 "-", "+" [(unary operators)]
32 "**" [(exponentiation)]
44 "=", "*=", "/=", "%=", "+=", "-=", "<<=", ">>=", "&=", "^=", "|="
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.)
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).
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.
62 Implementation is a recursive-descent parser.
73 #if defined (HAVE_UNISTD_H)
75 # include <sys/types.h>
80 #include "chartypes.h"
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'))
88 /* Size be which the expression stack grows when neccessary. */
89 #define EXPR_STACK_GROW_SIZE 10
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
96 /* The Tokens. Singing "The Lion Sleeps Tonight". */
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-- */
126 #define BAND '&' /* Bitwise AND */
127 #define BOR '|' /* Bitwise OR. */
128 #define BXOR '^' /* Bitwise eXclusive OR. */
129 #define BNOT '~' /* Bitwise NOT; Two's complement. */
134 /* This should be the function corresponding to the operator with the
135 highest precedence. */
136 #define EXP_HIGHEST expcomma
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;
149 static void readtok __P((void)); /* lexical analyzer */
150 static long strlong __P((char *));
151 static void evalerror __P((char *));
153 static void pushexp __P((void));
154 static void popexp __P((void));
156 static long subexpr __P((char *));
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));
175 /* A structure defining a single expression context. */
178 char *expression, *tp, *lasttp;
184 #ifdef INCLUDE_UNUSED
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. */
197 extern char *this_command_name;
201 (X)->curtok = curtok; \
202 (X)->lasttok = lasttok; \
204 (X)->lasttp = lasttp; \
205 (X)->tokval = tokval; \
206 (X)->tokstr = tokstr; \
207 (X)->noeval = noeval; \
210 #define RESTORETOK(X) \
212 curtok = (X)->curtok; \
213 lasttok = (X)->lasttok; \
215 lasttp = (X)->lasttp; \
216 tokval = (X)->tokval; \
217 tokstr = (X)->tokstr; \
218 noeval = (X)->noeval; \
221 /* Push and save away the contents of the globals describing the
222 current expression context. */
226 EXPR_CONTEXT *context;
228 if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
229 evalerror ("expression recursion level exceeded");
231 if (expr_depth >= expr_stack_size)
233 expr_stack_size += EXPR_STACK_GROW_SIZE;
234 expr_stack = (EXPR_CONTEXT **)xrealloc (expr_stack, expr_stack_size * sizeof (EXPR_CONTEXT *));
237 context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
239 context->expression = expression;
242 expr_stack[expr_depth++] = context;
245 /* Pop the the contents of the expression context stack into the
246 globals describing the current expression context. */
250 EXPR_CONTEXT *context;
253 evalerror ("recursion stack underflow");
255 context = expr_stack[--expr_depth];
257 expression = context->expression;
258 RESTORETOK (context);
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
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. */
277 evalexp (expr, validp)
283 procenv_t old_evalbuf;
289 /* Save the value of evalbuf to protect it around possible recursive
290 calls to evalexp (). */
291 COPY_PROCENV (evalbuf, old_evalbuf);
294 if (setjmp (evalbuf))
298 tokstr = expression = (char *)NULL;
300 while (--expr_depth > 0)
302 if (expr_stack[expr_depth]->tokstr)
303 free (expr_stack[expr_depth]->tokstr);
305 if (expr_stack[expr_depth]->expression)
306 free (expr_stack[expr_depth]->expression);
308 free (expr_stack[expr_depth]);
310 free (expr_stack[expr_depth]); /* free the allocated EXPR_CONTEXT */
317 val = subexpr (expr);
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);
338 for (p = expr; p && *p && cr_whitespace (*p); p++)
341 if (p == NULL || *p == '\0')
345 curtok = lasttok = 0;
346 expression = savestring (expr);
349 tokstr = (char *)NULL;
354 val = EXP_HIGHEST ();
357 evalerror ("syntax error in expression");
372 value = expassign ();
373 while (curtok == COMMA)
376 value = expassign ();
389 if (curtok == EQ || curtok == OP_ASSIGN)
394 special = curtok == OP_ASSIGN;
397 evalerror ("attempted assignment to non-variable");
401 op = assigntok; /* a OP= b */
405 lhs = savestring (tokstr);
407 value = expassign ();
445 evalerror ("bug: bad expassign token");
453 (void)bind_int_variable (lhs, rhs);
457 tokstr = (char *)NULL; /* For freeing on errors. */
462 /* Conditional expression (expr?expr:expr) */
466 long cval, val1, val2, rval;
470 rval = cval = explor ();
471 if (curtok == QUES) /* found conditional expr */
474 if (curtok == 0 || curtok == COL)
475 evalerror ("expression expected");
482 val1 = EXP_HIGHEST ();
487 evalerror ("`:' expected for conditional expression");
490 evalerror ("expression expected");
500 rval = cval ? val1 : val2;
510 register long val1, val2;
515 while (curtok == LOR)
538 register long val1, val2;
543 while (curtok == LAND)
566 register long val1, val2;
570 while (curtok == BOR)
584 register long val1, val2;
588 while (curtok == BXOR)
602 register long val1, val2;
606 while (curtok == BAND)
619 register long val1, val2;
623 while ((curtok == EQEQ) || (curtok == NEQ))
630 val1 = (val1 == val2);
632 val1 = (val1 != val2);
640 register long val1, val2;
643 while ((curtok == LEQ) ||
659 else /* (op == GT) */
665 /* Left and right shifts. */
669 register long val1, val2;
673 while ((curtok == LSH) || (curtok == RSH))
692 register long val1, val2;
696 while ((curtok == PLUS) || (curtok == MINUS))
705 else if (op == MINUS)
714 register long val1, val2;
718 while ((curtok == MUL) ||
728 if (((op == DIV) || (op == MOD)) && (val2 == 0))
729 evalerror ("division by 0");
744 register long val1, val2, c;
754 evalerror ("exponent less than 0");
755 for (c = 1; val2--; c *= val1)
772 else if (curtok == BNOT)
786 register long val = 0, v2;
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)
794 stok = lasttok = curtok;
797 /* readtok() catches this */
798 evalerror ("identifier expected after pre-increment or pre-decrement");
800 v2 = tokval + ((stok == PREINC) ? 1 : -1);
803 (void)bind_int_variable (tokstr, vincdec);
807 curtok = NUM; /* make sure --x=7 is flagged as an error */
810 else if (curtok == MINUS)
815 else if (curtok == PLUS)
820 else if (curtok == LPAR)
823 val = EXP_HIGHEST ();
826 evalerror ("missing `)'");
828 /* Skip over closing paren. */
831 else if ((curtok == NUM) || (curtok == STR))
834 if (curtok == STR && (*tp == '+' || *tp == '-') && tp[1] == *tp &&
835 (tp[2] == '\0' || (ISALNUM ((unsigned char)tp[2]) == 0)))
837 /* post-increment or post-decrement */
838 v2 = val + ((*tp == '+') ? 1 : -1);
841 (void)bind_int_variable (tokstr, vincdec);
844 curtok = NUM; /* make sure x++=7 is flagged as an error */
850 evalerror ("syntax error: operand expected");
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
863 register unsigned char c, c1;
866 /* Skip leading whitespace. */
869 while (cp && (c = *cp) && (cr_whitespace (c)))
875 lasttp = tp = cp - 1;
885 if (legal_variable_starter (c))
887 /* variable names not preceded with a dollar sign are shell variables. */
888 char *value, *savecp;
892 while (legal_variable_char (c))
897 #if defined (ARRAY_VARS)
900 e = skipsubscript (cp, 0);
908 evalerror ("bad array subscript");
910 #endif /* ARRAY_VARS */
914 tokstr = savestring (tp);
918 tokstr = (char *)NULL; /* keep it from being freed */
923 if (peektok == STR) /* free new tokstr before old one is restored */
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)
932 #if defined (ARRAY_VARS)
933 value = (e == ']') ? get_array_value (tokstr, 0) : get_string_value (tokstr);
935 value = get_string_value (tokstr);
938 tokval = (value && *value) ? subexpr (value) : 0;
940 #if defined (ARRAY_VARS)
942 FREE (value); /* get_array_value returns newly-allocated memory */
953 while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
959 tokval = strlong (tp);
967 if ((c == EQ) && (c1 == EQ))
969 else if ((c == NOT) && (c1 == EQ))
971 else if ((c == GT) && (c1 == EQ))
973 else if ((c == LT) && (c1 == EQ))
975 else if ((c == LT) && (c1 == LT))
977 if (*cp == '=') /* a <<= b */
986 else if ((c == GT) && (c1 == GT))
990 assigntok = RSH; /* a >>= b */
997 else if ((c == BAND) && (c1 == BAND))
999 else if ((c == BOR) && (c1 == BOR))
1001 else if ((c == '*') && (c1 == '*'))
1003 else if ((c == '-') && (c1 == '-') && legal_variable_starter ((unsigned char)*cp))
1005 else if ((c == '+') && (c1 == '+') && legal_variable_starter ((unsigned char)*cp))
1007 else if (c1 == EQ && member (c, "*/%+-&^|"))
1009 assigntok = c; /* a OP= b */
1013 cp--; /* `unget' the character */
1026 name = this_command_name;
1027 for (t = expression; whitespace (*t); t++)
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);
1035 /* Convert a string to a long integer, with an arbitrary base.
1038 Anything else: [base#]number (this is implemented to match ksh93)
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). */
1051 register unsigned char c;
1052 int base, foundbase;
1067 if (*s == 'x' || *s == 'X')
1078 for (c = *s++; c; c = *s++)
1083 evalerror ("bad number");
1085 /* Illegal base specifications raise an evaluation error. */
1086 if (val < 2 || val > 64)
1087 evalerror ("illegal arithmetic base");
1093 else if (ISALNUM(c) || (c == '_') || (c == '@'))
1097 else if (c >= 'a' && c <= 'z')
1099 else if (c >= 'A' && c <= 'Z')
1100 c -= 'A' - ((base <= 36) ? 10 : 36);
1107 evalerror ("value too great for base");
1109 val = (val * base) + c;
1117 #if defined (EXPR_TEST)
1122 return (malloc (n));
1130 return (realloc (s, n));
1133 SHELL_VAR *find_variable () { return 0;}
1134 SHELL_VAR *bind_variable () { return 0; }
1136 char *get_string_value () { return 0; }
1138 procenv_t top_level;
1148 if (setjmp (top_level))
1151 for (i = 1; i < argc; i++)
1153 v = evalexp (argv[i], &expok);
1155 fprintf (stderr, "%s: expression error\n", argv[i]);
1157 printf ("'%s' -> %ld\n", argv[i], v);
1163 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1166 fprintf (stderr, "expr: ");
1167 fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1168 fprintf (stderr, "\n");
1179 #endif /* EXPR_TEST */