]>
git.ipfire.org Git - thirdparty/bash.git/blob - expr.c
1 /* expr.c -- arithmetic expression evaluation. */
3 /* Copyright (C) 1990-2010 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
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Bash is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with Bash. If not, see <http://www.gnu.org/licenses/>.
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
141 # define MAX_INT_LEN 32
146 char *tokstr
; /* possibly-rewritten lvalue if not NULL */
147 intmax_t tokval
; /* expression evaluated value */
148 SHELL_VAR
*tokvar
; /* variable described by array or var reference */
149 intmax_t ind
; /* array index if not -1 */
152 /* A structure defining a single expression context. */
155 char *expression
, *tp
, *lasttp
;
162 static char *expression
; /* The current expression */
163 static char *tp
; /* token lexical position */
164 static char *lasttp
; /* pointer to last token position */
165 static int curtok
; /* the current token */
166 static int lasttok
; /* the previous token */
167 static int assigntok
; /* the OP in OP= */
168 static char *tokstr
; /* current token string */
169 static intmax_t tokval
; /* current token value */
170 static int noeval
; /* set to 1 if no assignment to be done */
171 static procenv_t evalbuf
;
173 static struct lvalue curlval
= {0, 0, 0, -1};
174 static struct lvalue lastlval
= {0, 0, 0, -1};
176 static int _is_arithop
__P((int));
177 static void readtok
__P((void)); /* lexical analyzer */
179 static void init_lvalue
__P((struct lvalue
*));
180 static struct lvalue
*alloc_lvalue
__P((void));
181 static void free_lvalue
__P((struct lvalue
*));
183 static intmax_t expr_streval
__P((char *, int, struct lvalue
*));
184 static intmax_t strlong
__P((char *));
185 static void evalerror
__P((const char *));
187 static void pushexp
__P((void));
188 static void popexp
__P((void));
189 static void expr_unwind
__P((void));
190 static void expr_bind_variable
__P((char *, char *));
191 static void expr_bind_array_element
__P((char *, arrayind_t
, char *));
193 static intmax_t subexpr
__P((char *));
195 static intmax_t expcomma
__P((void));
196 static intmax_t expassign
__P((void));
197 static intmax_t expcond
__P((void));
198 static intmax_t explor
__P((void));
199 static intmax_t expland
__P((void));
200 static intmax_t expbor
__P((void));
201 static intmax_t expbxor
__P((void));
202 static intmax_t expband
__P((void));
203 static intmax_t exp5
__P((void));
204 static intmax_t exp4
__P((void));
205 static intmax_t expshift
__P((void));
206 static intmax_t exp3
__P((void));
207 static intmax_t exp2
__P((void));
208 static intmax_t exppower
__P((void));
209 static intmax_t exp1
__P((void));
210 static intmax_t exp0
__P((void));
212 /* Global var which contains the stack of expression contexts. */
213 static EXPR_CONTEXT
**expr_stack
;
214 static int expr_depth
; /* Location in the stack. */
215 static int expr_stack_size
; /* Number of slots already allocated. */
217 extern char *this_command_name
;
218 extern int unbound_vars_is_error
, last_command_exit_value
;
220 #if defined (ARRAY_VARS)
221 extern const char * const bash_badsub_errmsg
;
226 (X)->curtok = curtok; \
227 (X)->lasttok = lasttok; \
229 (X)->lasttp = lasttp; \
230 (X)->tokval = tokval; \
231 (X)->tokstr = tokstr; \
232 (X)->noeval = noeval; \
233 (X)->lval = curlval; \
236 #define RESTORETOK(X) \
238 curtok = (X)->curtok; \
239 lasttok = (X)->lasttok; \
241 lasttp = (X)->lasttp; \
242 tokval = (X)->tokval; \
243 tokstr = (X)->tokstr; \
244 noeval = (X)->noeval; \
245 curlval = (X)->lval; \
248 /* Push and save away the contents of the globals describing the
249 current expression context. */
253 EXPR_CONTEXT
*context
;
255 if (expr_depth
>= MAX_EXPR_RECURSION_LEVEL
)
256 evalerror (_("expression recursion level exceeded"));
258 if (expr_depth
>= expr_stack_size
)
260 expr_stack_size
+= EXPR_STACK_GROW_SIZE
;
261 expr_stack
= (EXPR_CONTEXT
**)xrealloc (expr_stack
, expr_stack_size
* sizeof (EXPR_CONTEXT
*));
264 context
= (EXPR_CONTEXT
*)xmalloc (sizeof (EXPR_CONTEXT
));
266 context
->expression
= expression
;
269 expr_stack
[expr_depth
++] = context
;
272 /* Pop the the contents of the expression context stack into the
273 globals describing the current expression context. */
277 EXPR_CONTEXT
*context
;
280 evalerror (_("recursion stack underflow"));
282 context
= expr_stack
[--expr_depth
];
284 expression
= context
->expression
;
285 RESTORETOK (context
);
293 while (--expr_depth
> 0)
295 if (expr_stack
[expr_depth
]->tokstr
)
296 free (expr_stack
[expr_depth
]->tokstr
);
298 if (expr_stack
[expr_depth
]->expression
)
299 free (expr_stack
[expr_depth
]->expression
);
301 free (expr_stack
[expr_depth
]);
303 free (expr_stack
[expr_depth
]); /* free the allocated EXPR_CONTEXT */
305 noeval
= 0; /* XXX */
309 expr_bind_variable (lhs
, rhs
)
312 (void)bind_int_variable (lhs
, rhs
);
313 stupidly_hack_special_variables (lhs
);
316 /* Rewrite tok, which is of the form vname[expression], to vname[ind], where
317 IND is the already-calculated value of expression. */
319 expr_bind_array_element (tok
, ind
, rhs
)
326 char ibuf
[INT_STRLEN_BOUND (arrayind_t
) + 1], *istr
;
328 istr
= fmtumax (ind
, 10, ibuf
, sizeof (ibuf
), 0);
329 vname
= array_variable_name (tok
, (char **)NULL
, (int *)NULL
);
331 llen
= strlen (vname
) + sizeof (ibuf
) + 3;
332 lhs
= xmalloc (llen
);
334 sprintf (lhs
, "%s[%s]", vname
, istr
); /* XXX */
336 expr_bind_variable (lhs
, rhs
);
337 /*itrace("expr_bind_array_element: %s=%s", lhs, rhs);*/
342 /* Evaluate EXPR, and return the arithmetic result. If VALIDP is
343 non-null, a zero is stored into the location to which it points
344 if the expression is invalid, non-zero otherwise. If a non-zero
345 value is returned in *VALIDP, the return value of evalexp() may
348 The `while' loop after the longjmp is caught relies on the above
349 implementation of pushexp and popexp leaving in expr_stack[0] the
350 values that the variables had when the program started. That is,
351 the first things saved are the initial values of the variables that
352 were assigned at program startup or by the compiler. Therefore, it is
353 safe to let the loop terminate when expr_depth == 0, without freeing up
354 any of the expr_depth[0] stuff. */
356 evalexp (expr
, validp
)
367 FASTCOPY (evalbuf
, oevalbuf
, sizeof (evalbuf
));
369 c
= setjmp (evalbuf
);
375 tokstr
= expression
= (char *)NULL
;
384 val
= subexpr (expr
);
389 FASTCOPY (oevalbuf
, evalbuf
, sizeof (evalbuf
));
401 for (p
= expr
; p
&& *p
&& cr_whitespace (*p
); p
++)
404 if (p
== NULL
|| *p
== '\0')
408 expression
= savestring (expr
);
411 curtok
= lasttok
= 0;
412 tokstr
= (char *)NULL
;
414 init_lvalue (&curlval
);
419 val
= EXP_HIGHEST ();
422 evalerror (_("syntax error in expression"));
435 register intmax_t value
;
437 value
= expassign ();
438 while (curtok
== COMMA
)
441 value
= expassign ();
450 register intmax_t value
;
455 if (curtok
== EQ
|| curtok
== OP_ASSIGN
)
460 special
= curtok
== OP_ASSIGN
;
463 evalerror (_("attempted assignment to non-variable"));
467 op
= assigntok
; /* a OP= b */
471 lhs
= savestring (tokstr
);
472 /* save ind in case rhs is string var and evaluation overwrites it */
475 value
= expassign ();
479 if ((op
== DIV
|| op
== MOD
) && value
== 0)
482 evalerror (_("division by 0"));
521 evalerror (_("bug: bad expassign token"));
531 expr_bind_array_element (lhs
, lind
, rhs
);
533 expr_bind_variable (lhs
, rhs
);
538 tokstr
= (char *)NULL
; /* For freeing on errors. */
543 /* Conditional expression (expr?expr:expr) */
547 intmax_t cval
, val1
, val2
, rval
;
551 rval
= cval
= explor ();
552 if (curtok
== QUES
) /* found conditional expr */
555 if (curtok
== 0 || curtok
== COL
)
556 evalerror (_("expression expected"));
563 val1
= EXP_HIGHEST ();
568 evalerror (_("`:' expected for conditional expression"));
571 evalerror (_("expression expected"));
582 rval
= cval
? val1
: val2
;
592 register intmax_t val1
, val2
;
597 while (curtok
== LOR
)
620 register intmax_t val1
, val2
;
625 while (curtok
== LAND
)
648 register intmax_t val1
, val2
;
652 while (curtok
== BOR
)
666 register intmax_t val1
, val2
;
670 while (curtok
== BXOR
)
684 register intmax_t val1
, val2
;
688 while (curtok
== BAND
)
701 register intmax_t val1
, val2
;
705 while ((curtok
== EQEQ
) || (curtok
== NEQ
))
712 val1
= (val1
== val2
);
714 val1
= (val1
!= val2
);
722 register intmax_t val1
, val2
;
725 while ((curtok
== LEQ
) ||
741 else /* (op == GT) */
747 /* Left and right shifts. */
751 register intmax_t val1
, val2
;
755 while ((curtok
== LSH
) || (curtok
== RSH
))
774 register intmax_t val1
, val2
;
778 while ((curtok
== PLUS
) || (curtok
== MINUS
))
787 else if (op
== MINUS
)
796 register intmax_t val1
, val2
;
800 while ((curtok
== MUL
) ||
810 if (((op
== DIV
) || (op
== MOD
)) && (val2
== 0))
813 evalerror (_("division by 0"));
831 register intmax_t val1
, val2
, c
;
834 while (curtok
== POWER
)
837 val2
= exppower (); /* exponentiation is right-associative */
841 evalerror (_("exponent less than 0"));
842 for (c
= 1; val2
--; c
*= val1
)
852 register intmax_t val
;
859 else if (curtok
== BNOT
)
864 else if (curtok
== MINUS
)
869 else if (curtok
== PLUS
)
883 register intmax_t val
= 0, v2
;
888 /* XXX - might need additional logic here to decide whether or not
889 pre-increment or pre-decrement is legal at this point. */
890 if (curtok
== PREINC
|| curtok
== PREDEC
)
892 stok
= lasttok
= curtok
;
895 /* readtok() catches this */
896 evalerror (_("identifier expected after pre-increment or pre-decrement"));
898 v2
= tokval
+ ((stok
== PREINC
) ? 1 : -1);
902 if (curlval
.ind
!= -1)
903 expr_bind_array_element (curlval
.tokstr
, curlval
.ind
, vincdec
);
905 expr_bind_variable (tokstr
, vincdec
);
910 curtok
= NUM
; /* make sure --x=7 is flagged as an error */
913 else if (curtok
== LPAR
)
916 val
= EXP_HIGHEST ();
918 if (curtok
!= RPAR
) /* ( */
919 evalerror (_("missing `)'"));
921 /* Skip over closing paren. */
924 else if ((curtok
== NUM
) || (curtok
== STR
))
930 tokstr
= (char *)NULL
; /* keep it from being freed */
935 /* post-increment or post-decrement */
936 if (stok
== POSTINC
|| stok
== POSTDEC
)
938 /* restore certain portions of EC */
942 lasttok
= STR
; /* ec.curtok */
944 v2
= val
+ ((stok
== POSTINC
) ? 1 : -1);
948 if (curlval
.ind
!= -1)
949 expr_bind_array_element (curlval
.tokstr
, curlval
.ind
, vincdec
);
951 expr_bind_variable (tokstr
, vincdec
);
954 curtok
= NUM
; /* make sure x++=7 is flagged as an error */
958 if (stok
== STR
) /* free new tokstr before old one is restored */
968 evalerror (_("syntax error: operand expected"));
979 lv
->tokval
= lv
->ind
= -1;
982 static struct lvalue
*
987 lv
= xmalloc (sizeof (struct lvalue
));
996 free (lv
); /* should be inlined */
1000 expr_streval (tok
, e
, lvalue
)
1003 struct lvalue
*lvalue
;
1008 #if defined (ARRAY_VARS)
1012 /*itrace("expr_streval: %s: noeval = %d", tok, noeval);*/
1013 /* If we are suppressing evaluation, just short-circuit here instead of
1014 going through the rest of the evaluator. */
1019 #if defined (ARRAY_VARS)
1020 v
= (e
== ']') ? array_variable_part (tok
, (char **)0, (int *)0) : find_variable (tok
);
1022 v
= find_variable (tok
);
1025 if ((v
== 0 || invisible_p (v
)) && unbound_vars_is_error
)
1027 #if defined (ARRAY_VARS)
1028 value
= (e
== ']') ? array_variable_name (tok
, (char **)0, (int *)0) : tok
;
1033 last_command_exit_value
= EXECUTION_FAILURE
;
1034 err_unboundvar (value
);
1036 #if defined (ARRAY_VARS)
1038 FREE (value
); /* array_variable_name returns new memory */
1041 if (interactive_shell
)
1044 top_level_cleanup ();
1045 jump_to_top_level (DISCARD
);
1048 jump_to_top_level (FORCE_EOF
);
1052 #if defined (ARRAY_VARS)
1053 /* Second argument of 0 to get_array_value means that we don't allow
1054 references like array[@]. In this case, get_array_value is just
1055 like get_variable_value in that it does not return newly-allocated
1056 memory or quote the results. */
1057 value
= (e
== ']') ? get_array_value (tok
, 0, (int *)NULL
, &ind
) : get_variable_value (v
);
1059 value
= get_variable_value (v
);
1062 tval
= (value
&& *value
) ? subexpr (value
) : 0;
1066 lvalue
->tokstr
= tok
; /* XXX */
1067 lvalue
->tokval
= tval
;
1068 lvalue
->tokvar
= v
; /* XXX */
1123 return 1; /* operator tokens */
1127 return 1; /* questionable */
1129 return 0; /* anything else is invalid */
1133 /* Lexical analyzer/token reader for the expression evaluator. Reads the
1134 next token and puts its value into curtok, while advancing past it.
1135 Updates value of tp. May also set tokval (for number) or tokstr (for
1140 register char *cp
, *xp
;
1141 register unsigned char c
, c1
;
1145 /* Skip leading whitespace. */
1148 while (cp
&& (c
= *cp
) && (cr_whitespace (c
)))
1161 lasttp
= tp
= cp
- 1;
1163 if (legal_variable_starter (c
))
1165 /* variable names not preceded with a dollar sign are shell variables. */
1170 while (legal_variable_char (c
))
1175 #if defined (ARRAY_VARS)
1178 e
= skipsubscript (cp
, 0, 0);
1186 evalerror (bash_badsub_errmsg
);
1188 #endif /* ARRAY_VARS */
1191 /* XXX - watch out for pointer aliasing issues here */
1192 if (curlval
.tokstr
&& curlval
.tokstr
== tokstr
)
1193 init_lvalue (&curlval
);
1196 tokstr
= savestring (tp
);
1199 /* XXX - make peektok part of saved token state? */
1201 tokstr
= (char *)NULL
; /* keep it from being freed */
1207 if (peektok
== STR
) /* free new tokstr before old one is restored */
1212 /* The tests for PREINC and PREDEC aren't strictly correct, but they
1213 preserve old behavior if a construct like --x=9 is given. */
1214 if (lasttok
== PREINC
|| lasttok
== PREDEC
|| peektok
!= EQ
)
1217 tokval
= expr_streval (tokstr
, e
, &curlval
);
1227 while (ISALNUM (c
) || c
== '#' || c
== '@' || c
== '_')
1233 tokval
= strlong (tp
);
1241 if ((c
== EQ
) && (c1
== EQ
))
1243 else if ((c
== NOT
) && (c1
== EQ
))
1245 else if ((c
== GT
) && (c1
== EQ
))
1247 else if ((c
== LT
) && (c1
== EQ
))
1249 else if ((c
== LT
) && (c1
== LT
))
1251 if (*cp
== '=') /* a <<= b */
1260 else if ((c
== GT
) && (c1
== GT
))
1264 assigntok
= RSH
; /* a >>= b */
1271 else if ((c
== BAND
) && (c1
== BAND
))
1273 else if ((c
== BOR
) && (c1
== BOR
))
1275 else if ((c
== '*') && (c1
== '*'))
1277 else if ((c
== '-' || c
== '+') && c1
== c
&& curtok
== STR
)
1278 c
= (c
== '-') ? POSTDEC
: POSTINC
;
1279 else if ((c
== '-' || c
== '+') && c1
== c
)
1281 /* Quickly scan forward to see if this is followed by optional
1282 whitespace and an identifier. */
1284 while (xp
&& *xp
&& cr_whitespace (*xp
))
1286 if (legal_variable_starter ((unsigned char)*xp
))
1287 c
= (c
== '-') ? PREDEC
: PREINC
;
1289 cp
--; /* not preinc or predec, so unget the character */
1291 else if (c1
== EQ
&& member (c
, "*/%+-&^|"))
1293 assigntok
= c
; /* a OP= b */
1296 else if (_is_arithop (c
) == 0)
1299 /* use curtok, since it hasn't been copied to lasttok yet */
1300 if (curtok
== 0 || _is_arithop (curtok
) || _is_multiop (curtok
))
1301 evalerror (_("syntax error: operand expected"));
1303 evalerror (_("syntax error: invalid arithmetic operator"));
1306 cp
--; /* `unget' the character */
1308 /* Should check here to make sure that the current character is one
1309 of the recognized operators and flag an error if not. Could create
1310 a character map the first time through and check it on subsequent
1324 name
= this_command_name
;
1325 for (t
= expression
; whitespace (*t
); t
++)
1327 internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1328 name
? name
: "", name
? ": " : "", t
,
1329 msg
, (lasttp
&& *lasttp
) ? lasttp
: "");
1330 longjmp (evalbuf
, 1);
1333 /* Convert a string to an intmax_t integer, with an arbitrary base.
1336 Anything else: [base#]number (this is implemented to match ksh93)
1338 Base may be >=2 and <=64. If base is <= 36, the numbers are drawn
1339 from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1340 interchangably. If base is > 36 and <= 64, the numbers are drawn
1341 from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1342 you get the picture). */
1349 register unsigned char c
;
1350 int base
, foundbase
;
1365 if (*s
== 'x' || *s
== 'X')
1376 for (c
= *s
++; c
; c
= *s
++)
1381 evalerror (_("invalid number"));
1383 /* Illegal base specifications raise an evaluation error. */
1384 if (val
< 2 || val
> 64)
1385 evalerror (_("invalid arithmetic base"));
1391 else if (ISALNUM(c
) || (c
== '_') || (c
== '@'))
1395 else if (c
>= 'a' && c
<= 'z')
1397 else if (c
>= 'A' && c
<= 'Z')
1398 c
-= 'A' - ((base
<= 36) ? 10 : 36);
1405 evalerror (_("value too great for base"));
1407 val
= (val
* base
) + c
;
1416 #if defined (EXPR_TEST)
1421 return (malloc (n
));
1429 return (realloc (s
, n
));
1432 SHELL_VAR
*find_variable () { return 0;}
1433 SHELL_VAR
*bind_variable () { return 0; }
1435 char *get_string_value () { return 0; }
1437 procenv_t top_level
;
1447 if (setjmp (top_level
))
1450 for (i
= 1; i
< argc
; i
++)
1452 v
= evalexp (argv
[i
], &expok
);
1454 fprintf (stderr
, _("%s: expression error\n"), argv
[i
]);
1456 printf ("'%s' -> %ld\n", argv
[i
], v
);
1462 builtin_error (format
, arg1
, arg2
, arg3
, arg4
, arg5
)
1465 fprintf (stderr
, "expr: ");
1466 fprintf (stderr
, format
, arg1
, arg2
, arg3
, arg4
, arg5
);
1467 fprintf (stderr
, "\n");
1478 #endif /* EXPR_TEST */