1 /* expr.c -- arithmetic expression evaluation. */
3 /* Copyright (C) 1990-2004 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 intmax_t 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 "=", "*=", "/=", "%=", "+=", "-=", "<<=", ">>=", "&=", "^=", "|="
47 (Note that most of these operators have special meaning to bash, and an
48 entire expression should be quoted, e.g. "a=$a+1" or "a=a+1" to ensure
49 that it is passed intact to the evaluator when using `let'. When using
50 the $[] or $(( )) forms, the text between the `[' and `]' or `((' and `))'
51 is treated as if in double quotes.)
53 Sub-expressions within parentheses have a precedence level greater than
54 all of the above levels and are evaluated first. Within a single prece-
55 dence group, evaluation is left-to-right, except for the arithmetic
56 assignment operator (`='), which is evaluated right-to-left (as in C).
58 The expression evaluator returns the value of the expression (assignment
59 statements have as a value what is returned by the RHS). The `let'
60 builtin, on the other hand, returns 0 if the last expression evaluates to
61 a non-zero, and 1 otherwise.
63 Implementation is a recursive-descent parser.
74 #if defined (HAVE_UNISTD_H)
76 # include <sys/types.h>
81 #include "chartypes.h"
86 /* Because of the $((...)) construct, expressions may include newlines.
87 Here is a macro which accepts newlines, tabs and spaces as whitespace. */
88 #define cr_whitespace(c) (whitespace(c) || ((c) == '\n'))
90 /* Size be which the expression stack grows when neccessary. */
91 #define EXPR_STACK_GROW_SIZE 10
93 /* Maximum amount of recursion allowed. This prevents a non-integer
94 variable such as "num=num+2" from infinitely adding to itself when
95 "let num=num+2" is given. */
96 #define MAX_EXPR_RECURSION_LEVEL 1024
98 /* The Tokens. Singing "The Lion Sleeps Tonight". */
100 #define EQEQ 1 /* "==" */
101 #define NEQ 2 /* "!=" */
102 #define LEQ 3 /* "<=" */
103 #define GEQ 4 /* ">=" */
104 #define STR 5 /* string */
105 #define NUM 6 /* number */
106 #define LAND 7 /* "&&" Logical AND */
107 #define LOR 8 /* "||" Logical OR */
108 #define LSH 9 /* "<<" Left SHift */
109 #define RSH 10 /* ">>" Right SHift */
110 #define OP_ASSIGN 11 /* op= expassign as in Posix.2 */
111 #define COND 12 /* exp1 ? exp2 : exp3 */
112 #define POWER 13 /* exp1**exp2 */
113 #define PREINC 14 /* ++var */
114 #define PREDEC 15 /* --var */
115 #define POSTINC 16 /* var++ */
116 #define POSTDEC 17 /* var-- */
128 #define BAND '&' /* Bitwise AND */
129 #define BOR '|' /* Bitwise OR. */
130 #define BXOR '^' /* Bitwise eXclusive OR. */
131 #define BNOT '~' /* Bitwise NOT; Two's complement. */
136 /* This should be the function corresponding to the operator with the
137 highest precedence. */
138 #define EXP_HIGHEST expcomma
140 static char *expression; /* The current expression */
141 static char *tp; /* token lexical position */
142 static char *lasttp; /* pointer to last token position */
143 static int curtok; /* the current token */
144 static int lasttok; /* the previous token */
145 static int assigntok; /* the OP in OP= */
146 static char *tokstr; /* current token string */
147 static intmax_t tokval; /* current token value */
148 static int noeval; /* set to 1 if no assignment to be done */
149 static procenv_t evalbuf;
151 static void readtok __P((void)); /* lexical analyzer */
153 static intmax_t expr_streval __P((char *, int));
154 static intmax_t strlong __P((char *));
155 static void evalerror __P((char *));
157 static void pushexp __P((void));
158 static void popexp __P((void));
159 static void expr_unwind __P((void));
160 static void expr_bind_variable __P((char *, char *));
162 static intmax_t subexpr __P((char *));
164 static intmax_t expcomma __P((void));
165 static intmax_t expassign __P((void));
166 static intmax_t expcond __P((void));
167 static intmax_t explor __P((void));
168 static intmax_t expland __P((void));
169 static intmax_t expbor __P((void));
170 static intmax_t expbxor __P((void));
171 static intmax_t expband __P((void));
172 static intmax_t exp5 __P((void));
173 static intmax_t exp4 __P((void));
174 static intmax_t expshift __P((void));
175 static intmax_t exp3 __P((void));
176 static intmax_t exp2 __P((void));
177 static intmax_t exppower __P((void));
178 static intmax_t exp1 __P((void));
179 static intmax_t exp0 __P((void));
181 /* A structure defining a single expression context. */
184 char *expression, *tp, *lasttp;
190 #ifdef INCLUDE_UNUSED
198 /* Global var which contains the stack of expression contexts. */
199 static EXPR_CONTEXT **expr_stack;
200 static int expr_depth; /* Location in the stack. */
201 static int expr_stack_size; /* Number of slots already allocated. */
203 extern char *this_command_name;
204 extern int unbound_vars_is_error;
206 #if defined (ARRAY_VARS)
207 extern char *bash_badsub_errmsg;
212 (X)->curtok = curtok; \
213 (X)->lasttok = lasttok; \
215 (X)->lasttp = lasttp; \
216 (X)->tokval = tokval; \
217 (X)->tokstr = tokstr; \
218 (X)->noeval = noeval; \
221 #define RESTORETOK(X) \
223 curtok = (X)->curtok; \
224 lasttok = (X)->lasttok; \
226 lasttp = (X)->lasttp; \
227 tokval = (X)->tokval; \
228 tokstr = (X)->tokstr; \
229 noeval = (X)->noeval; \
232 /* Push and save away the contents of the globals describing the
233 current expression context. */
237 EXPR_CONTEXT *context;
239 if (expr_depth >= MAX_EXPR_RECURSION_LEVEL)
240 evalerror (_("expression recursion level exceeded"));
242 if (expr_depth >= expr_stack_size)
244 expr_stack_size += EXPR_STACK_GROW_SIZE;
245 expr_stack = (EXPR_CONTEXT **)xrealloc (expr_stack, expr_stack_size * sizeof (EXPR_CONTEXT *));
248 context = (EXPR_CONTEXT *)xmalloc (sizeof (EXPR_CONTEXT));
250 context->expression = expression;
253 expr_stack[expr_depth++] = context;
256 /* Pop the the contents of the expression context stack into the
257 globals describing the current expression context. */
261 EXPR_CONTEXT *context;
264 evalerror (_("recursion stack underflow"));
266 context = expr_stack[--expr_depth];
268 expression = context->expression;
269 RESTORETOK (context);
277 while (--expr_depth > 0)
279 if (expr_stack[expr_depth]->tokstr)
280 free (expr_stack[expr_depth]->tokstr);
282 if (expr_stack[expr_depth]->expression)
283 free (expr_stack[expr_depth]->expression);
285 free (expr_stack[expr_depth]);
287 free (expr_stack[expr_depth]); /* free the allocated EXPR_CONTEXT */
291 expr_bind_variable (lhs, rhs)
294 (void)bind_int_variable (lhs, rhs);
295 stupidly_hack_special_variables (lhs);
298 /* Evaluate EXPR, and return the arithmetic result. If VALIDP is
299 non-null, a zero is stored into the location to which it points
300 if the expression is invalid, non-zero otherwise. If a non-zero
301 value is returned in *VALIDP, the return value of evalexp() may
304 The `while' loop after the longjmp is caught relies on the above
305 implementation of pushexp and popexp leaving in expr_stack[0] the
306 values that the variables had when the program started. That is,
307 the first things saved are the initial values of the variables that
308 were assigned at program startup or by the compiler. Therefore, it is
309 safe to let the loop terminate when expr_depth == 0, without freeing up
310 any of the expr_depth[0] stuff. */
312 evalexp (expr, validp)
322 FASTCOPY (evalbuf, oevalbuf, sizeof (evalbuf));
324 c = setjmp (evalbuf);
330 tokstr = expression = (char *)NULL;
339 val = subexpr (expr);
344 FASTCOPY (oevalbuf, evalbuf, sizeof (evalbuf));
356 for (p = expr; p && *p && cr_whitespace (*p); p++)
359 if (p == NULL || *p == '\0')
363 curtok = lasttok = 0;
364 expression = savestring (expr);
367 tokstr = (char *)NULL;
372 val = EXP_HIGHEST ();
375 evalerror (_("syntax error in expression"));
388 register intmax_t value;
390 value = expassign ();
391 while (curtok == COMMA)
394 value = expassign ();
403 register intmax_t value;
407 if (curtok == EQ || curtok == OP_ASSIGN)
412 special = curtok == OP_ASSIGN;
415 evalerror (_("attempted assignment to non-variable"));
419 op = assigntok; /* a OP= b */
423 lhs = savestring (tokstr);
425 value = expassign ();
436 evalerror (_("division by 0"));
441 evalerror (_("division by 0"));
467 evalerror (_("bug: bad expassign token"));
475 expr_bind_variable (lhs, rhs);
479 tokstr = (char *)NULL; /* For freeing on errors. */
484 /* Conditional expression (expr?expr:expr) */
488 intmax_t cval, val1, val2, rval;
492 rval = cval = explor ();
493 if (curtok == QUES) /* found conditional expr */
496 if (curtok == 0 || curtok == COL)
497 evalerror (_("expression expected"));
504 val1 = EXP_HIGHEST ();
509 evalerror (_("`:' expected for conditional expression"));
512 evalerror (_("expression expected"));
522 rval = cval ? val1 : val2;
532 register intmax_t val1, val2;
537 while (curtok == LOR)
560 register intmax_t val1, val2;
565 while (curtok == LAND)
588 register intmax_t val1, val2;
592 while (curtok == BOR)
606 register intmax_t val1, val2;
610 while (curtok == BXOR)
624 register intmax_t val1, val2;
628 while (curtok == BAND)
641 register intmax_t val1, val2;
645 while ((curtok == EQEQ) || (curtok == NEQ))
652 val1 = (val1 == val2);
654 val1 = (val1 != val2);
662 register intmax_t val1, val2;
665 while ((curtok == LEQ) ||
681 else /* (op == GT) */
687 /* Left and right shifts. */
691 register intmax_t val1, val2;
695 while ((curtok == LSH) || (curtok == RSH))
714 register intmax_t val1, val2;
718 while ((curtok == PLUS) || (curtok == MINUS))
727 else if (op == MINUS)
736 register intmax_t val1, val2;
740 while ((curtok == MUL) ||
750 if (((op == DIV) || (op == MOD)) && (val2 == 0))
751 evalerror (_("division by 0"));
766 register intmax_t val1, val2, c;
769 while (curtok == POWER)
772 val2 = exppower (); /* exponentiation is right-associative */
776 evalerror (_("exponent less than 0"));
777 for (c = 1; val2--; c *= val1)
787 register intmax_t val;
794 else if (curtok == BNOT)
808 register intmax_t val = 0, v2;
813 /* XXX - might need additional logic here to decide whether or not
814 pre-increment or pre-decrement is legal at this point. */
815 if (curtok == PREINC || curtok == PREDEC)
817 stok = lasttok = curtok;
820 /* readtok() catches this */
821 evalerror (_("identifier expected after pre-increment or pre-decrement"));
823 v2 = tokval + ((stok == PREINC) ? 1 : -1);
826 expr_bind_variable (tokstr, vincdec);
830 curtok = NUM; /* make sure --x=7 is flagged as an error */
833 else if (curtok == MINUS)
838 else if (curtok == PLUS)
843 else if (curtok == LPAR)
846 val = EXP_HIGHEST ();
848 if (curtok != RPAR) /* ( */
849 evalerror (_("missing `)'"));
851 /* Skip over closing paren. */
854 else if ((curtok == NUM) || (curtok == STR))
860 tokstr = (char *)NULL; /* keep it from being freed */
865 /* post-increment or post-decrement */
866 if (stok == POSTINC || stok == POSTDEC)
868 /* restore certain portions of EC */
871 lasttok = STR; /* ec.curtok */
873 v2 = val + ((stok == POSTINC) ? 1 : -1);
876 expr_bind_variable (tokstr, vincdec);
878 curtok = NUM; /* make sure x++=7 is flagged as an error */
882 if (stok == STR) /* free new tokstr before old one is restored */
892 evalerror (_("syntax error: operand expected"));
898 expr_streval (tok, e)
907 #if defined (ARRAY_VARS)
908 v = (e == ']') ? array_variable_part (tok, (char **)0, (int *)0) : find_variable (tok);
910 v = find_variable (tok);
913 if ((v == 0 || invisible_p (v)) && unbound_vars_is_error)
915 #if defined (ARRAY_VARS)
916 value = (e == ']') ? array_variable_name (tok, (char **)0, (int *)0) : tok;
921 err_unboundvar (value);
923 #if defined (ARRAY_VARS)
925 FREE (value); /* array_variable_name returns new memory */
928 if (interactive_shell)
931 jump_to_top_level (DISCARD);
934 jump_to_top_level (FORCE_EOF);
937 #if defined (ARRAY_VARS)
938 /* Second argument of 0 to get_array_value means that we don't allow
939 references like array[@]. In this case, get_array_value is just
940 like get_variable_value in that it does not return newly-allocated
941 memory or quote the results. */
942 value = (e == ']') ? get_array_value (tok, 0, (int *)NULL) : get_variable_value (v);
944 value = get_variable_value (v);
947 tval = (value && *value) ? subexpr (value) : 0;
952 /* Lexical analyzer/token reader for the expression evaluator. Reads the
953 next token and puts its value into curtok, while advancing past it.
954 Updates value of tp. May also set tokval (for number) or tokstr (for
959 register char *cp, *xp;
960 register unsigned char c, c1;
963 /* Skip leading whitespace. */
966 while (cp && (c = *cp) && (cr_whitespace (c)))
972 lasttp = tp = cp - 1;
982 if (legal_variable_starter (c))
984 /* variable names not preceded with a dollar sign are shell variables. */
989 while (legal_variable_char (c))
994 #if defined (ARRAY_VARS)
997 e = skipsubscript (cp, 0);
1005 evalerror (bash_badsub_errmsg);
1007 #endif /* ARRAY_VARS */
1011 tokstr = savestring (tp);
1015 tokstr = (char *)NULL; /* keep it from being freed */
1021 if (peektok == STR) /* free new tokstr before old one is restored */
1026 /* The tests for PREINC and PREDEC aren't strictly correct, but they
1027 preserve old behavior if a construct like --x=9 is given. */
1028 if (lasttok == PREINC || lasttok == PREDEC || peektok != EQ)
1029 tokval = expr_streval (tokstr, e);
1038 while (ISALNUM (c) || c == '#' || c == '@' || c == '_')
1044 tokval = strlong (tp);
1052 if ((c == EQ) && (c1 == EQ))
1054 else if ((c == NOT) && (c1 == EQ))
1056 else if ((c == GT) && (c1 == EQ))
1058 else if ((c == LT) && (c1 == EQ))
1060 else if ((c == LT) && (c1 == LT))
1062 if (*cp == '=') /* a <<= b */
1071 else if ((c == GT) && (c1 == GT))
1075 assigntok = RSH; /* a >>= b */
1082 else if ((c == BAND) && (c1 == BAND))
1084 else if ((c == BOR) && (c1 == BOR))
1086 else if ((c == '*') && (c1 == '*'))
1088 else if ((c == '-' || c == '+') && c1 == c && curtok == STR)
1089 c = (c == '-') ? POSTDEC : POSTINC;
1090 else if ((c == '-' || c == '+') && c1 == c)
1092 /* Quickly scan forward to see if this is followed by optional
1093 whitespace and an identifier. */
1095 while (xp && *xp && cr_whitespace (*xp))
1097 if (legal_variable_starter ((unsigned char)*xp))
1098 c = (c == '-') ? PREDEC : PREINC;
1100 cp--; /* not preinc or predec, so unget the character */
1102 else if (c1 == EQ && member (c, "*/%+-&^|"))
1104 assigntok = c; /* a OP= b */
1108 cp--; /* `unget' the character */
1121 name = this_command_name;
1122 for (t = expression; whitespace (*t); t++)
1124 internal_error ("%s%s%s: %s (error token is \"%s\")",
1125 name ? name : "", name ? ": " : "", t,
1126 msg, (lasttp && *lasttp) ? lasttp : "");
1127 longjmp (evalbuf, 1);
1130 /* Convert a string to an intmax_t integer, with an arbitrary base.
1133 Anything else: [base#]number (this is implemented to match ksh93)
1135 Base may be >=2 and <=64. If base is <= 36, the numbers are drawn
1136 from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1137 interchangably. If base is > 36 and <= 64, the numbers are drawn
1138 from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1139 you get the picture). */
1146 register unsigned char c;
1147 int base, foundbase;
1162 if (*s == 'x' || *s == 'X')
1173 for (c = *s++; c; c = *s++)
1178 evalerror (_("invalid number"));
1180 /* Illegal base specifications raise an evaluation error. */
1181 if (val < 2 || val > 64)
1182 evalerror (_("invalid arithmetic base"));
1188 else if (ISALNUM(c) || (c == '_') || (c == '@'))
1192 else if (c >= 'a' && c <= 'z')
1194 else if (c >= 'A' && c <= 'Z')
1195 c -= 'A' - ((base <= 36) ? 10 : 36);
1202 evalerror (_("value too great for base"));
1204 val = (val * base) + c;
1213 #if defined (EXPR_TEST)
1218 return (malloc (n));
1226 return (realloc (s, n));
1229 SHELL_VAR *find_variable () { return 0;}
1230 SHELL_VAR *bind_variable () { return 0; }
1232 char *get_string_value () { return 0; }
1234 procenv_t top_level;
1244 if (setjmp (top_level))
1247 for (i = 1; i < argc; i++)
1249 v = evalexp (argv[i], &expok);
1251 fprintf (stderr, "%s: expression error\n", argv[i]);
1253 printf ("'%s' -> %ld\n", argv[i], v);
1259 builtin_error (format, arg1, arg2, arg3, arg4, arg5)
1262 fprintf (stderr, "expr: ");
1263 fprintf (stderr, format, arg1, arg2, arg3, arg4, arg5);
1264 fprintf (stderr, "\n");
1275 #endif /* EXPR_TEST */