]>
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 ();
486 evalerror (_("division by 0"));
491 evalerror (_("division by 0"));
517 evalerror (_("bug: bad expassign token"));
527 expr_bind_array_element (lhs
, lind
, rhs
);
529 expr_bind_variable (lhs
, rhs
);
534 tokstr
= (char *)NULL
; /* For freeing on errors. */
539 /* Conditional expression (expr?expr:expr) */
543 intmax_t cval
, val1
, val2
, rval
;
547 rval
= cval
= explor ();
548 if (curtok
== QUES
) /* found conditional expr */
551 if (curtok
== 0 || curtok
== COL
)
552 evalerror (_("expression expected"));
559 val1
= EXP_HIGHEST ();
564 evalerror (_("`:' expected for conditional expression"));
567 evalerror (_("expression expected"));
578 rval
= cval
? val1
: val2
;
588 register intmax_t val1
, val2
;
593 while (curtok
== LOR
)
616 register intmax_t val1
, val2
;
621 while (curtok
== LAND
)
644 register intmax_t val1
, val2
;
648 while (curtok
== BOR
)
662 register intmax_t val1
, val2
;
666 while (curtok
== BXOR
)
680 register intmax_t val1
, val2
;
684 while (curtok
== BAND
)
697 register intmax_t val1
, val2
;
701 while ((curtok
== EQEQ
) || (curtok
== NEQ
))
708 val1
= (val1
== val2
);
710 val1
= (val1
!= val2
);
718 register intmax_t val1
, val2
;
721 while ((curtok
== LEQ
) ||
737 else /* (op == GT) */
743 /* Left and right shifts. */
747 register intmax_t val1
, val2
;
751 while ((curtok
== LSH
) || (curtok
== RSH
))
770 register intmax_t val1
, val2
;
774 while ((curtok
== PLUS
) || (curtok
== MINUS
))
783 else if (op
== MINUS
)
792 register intmax_t val1
, val2
;
796 while ((curtok
== MUL
) ||
806 if (((op
== DIV
) || (op
== MOD
)) && (val2
== 0))
807 evalerror (_("division by 0"));
822 register intmax_t val1
, val2
, c
;
825 while (curtok
== POWER
)
828 val2
= exppower (); /* exponentiation is right-associative */
832 evalerror (_("exponent less than 0"));
833 for (c
= 1; val2
--; c
*= val1
)
843 register intmax_t val
;
850 else if (curtok
== BNOT
)
855 else if (curtok
== MINUS
)
860 else if (curtok
== PLUS
)
874 register intmax_t val
= 0, v2
;
879 /* XXX - might need additional logic here to decide whether or not
880 pre-increment or pre-decrement is legal at this point. */
881 if (curtok
== PREINC
|| curtok
== PREDEC
)
883 stok
= lasttok
= curtok
;
886 /* readtok() catches this */
887 evalerror (_("identifier expected after pre-increment or pre-decrement"));
889 v2
= tokval
+ ((stok
== PREINC
) ? 1 : -1);
893 if (curlval
.ind
!= -1)
894 expr_bind_array_element (curlval
.tokstr
, curlval
.ind
, vincdec
);
896 expr_bind_variable (tokstr
, vincdec
);
901 curtok
= NUM
; /* make sure --x=7 is flagged as an error */
904 else if (curtok
== LPAR
)
907 val
= EXP_HIGHEST ();
909 if (curtok
!= RPAR
) /* ( */
910 evalerror (_("missing `)'"));
912 /* Skip over closing paren. */
915 else if ((curtok
== NUM
) || (curtok
== STR
))
921 tokstr
= (char *)NULL
; /* keep it from being freed */
926 /* post-increment or post-decrement */
927 if (stok
== POSTINC
|| stok
== POSTDEC
)
929 /* restore certain portions of EC */
933 lasttok
= STR
; /* ec.curtok */
935 v2
= val
+ ((stok
== POSTINC
) ? 1 : -1);
939 if (curlval
.ind
!= -1)
940 expr_bind_array_element (curlval
.tokstr
, curlval
.ind
, vincdec
);
942 expr_bind_variable (tokstr
, vincdec
);
945 curtok
= NUM
; /* make sure x++=7 is flagged as an error */
949 if (stok
== STR
) /* free new tokstr before old one is restored */
959 evalerror (_("syntax error: operand expected"));
970 lv
->tokval
= lv
->ind
= -1;
973 static struct lvalue
*
978 lv
= xmalloc (sizeof (struct lvalue
));
987 free (lv
); /* should be inlined */
991 expr_streval (tok
, e
, lvalue
)
994 struct lvalue
*lvalue
;
999 #if defined (ARRAY_VARS)
1004 #if defined (ARRAY_VARS)
1005 v
= (e
== ']') ? array_variable_part (tok
, (char **)0, (int *)0) : find_variable (tok
);
1007 v
= find_variable (tok
);
1010 if ((v
== 0 || invisible_p (v
)) && unbound_vars_is_error
)
1012 #if defined (ARRAY_VARS)
1013 value
= (e
== ']') ? array_variable_name (tok
, (char **)0, (int *)0) : tok
;
1018 last_command_exit_value
= EXECUTION_FAILURE
;
1019 err_unboundvar (value
);
1021 #if defined (ARRAY_VARS)
1023 FREE (value
); /* array_variable_name returns new memory */
1026 if (interactive_shell
)
1029 top_level_cleanup ();
1030 jump_to_top_level (DISCARD
);
1033 jump_to_top_level (FORCE_EOF
);
1037 #if defined (ARRAY_VARS)
1038 /* Second argument of 0 to get_array_value means that we don't allow
1039 references like array[@]. In this case, get_array_value is just
1040 like get_variable_value in that it does not return newly-allocated
1041 memory or quote the results. */
1042 value
= (e
== ']') ? get_array_value (tok
, 0, (int *)NULL
, &ind
) : get_variable_value (v
);
1044 value
= get_variable_value (v
);
1047 tval
= (value
&& *value
) ? subexpr (value
) : 0;
1051 lvalue
->tokstr
= tok
; /* XXX */
1052 lvalue
->tokval
= tval
;
1053 lvalue
->tokvar
= v
; /* XXX */
1108 return 1; /* operator tokens */
1112 return 1; /* questionable */
1114 return 0; /* anything else is invalid */
1118 /* Lexical analyzer/token reader for the expression evaluator. Reads the
1119 next token and puts its value into curtok, while advancing past it.
1120 Updates value of tp. May also set tokval (for number) or tokstr (for
1125 register char *cp
, *xp
;
1126 register unsigned char c
, c1
;
1130 /* Skip leading whitespace. */
1133 while (cp
&& (c
= *cp
) && (cr_whitespace (c
)))
1146 lasttp
= tp
= cp
- 1;
1148 if (legal_variable_starter (c
))
1150 /* variable names not preceded with a dollar sign are shell variables. */
1155 while (legal_variable_char (c
))
1160 #if defined (ARRAY_VARS)
1163 e
= skipsubscript (cp
, 0, 0);
1171 evalerror (bash_badsub_errmsg
);
1173 #endif /* ARRAY_VARS */
1177 tokstr
= savestring (tp
);
1180 /* XXX - make peektok part of saved token state? */
1182 tokstr
= (char *)NULL
; /* keep it from being freed */
1188 if (peektok
== STR
) /* free new tokstr before old one is restored */
1193 /* The tests for PREINC and PREDEC aren't strictly correct, but they
1194 preserve old behavior if a construct like --x=9 is given. */
1195 if (lasttok
== PREINC
|| lasttok
== PREDEC
|| peektok
!= EQ
)
1198 tokval
= expr_streval (tokstr
, e
, &curlval
);
1208 while (ISALNUM (c
) || c
== '#' || c
== '@' || c
== '_')
1214 tokval
= strlong (tp
);
1222 if ((c
== EQ
) && (c1
== EQ
))
1224 else if ((c
== NOT
) && (c1
== EQ
))
1226 else if ((c
== GT
) && (c1
== EQ
))
1228 else if ((c
== LT
) && (c1
== EQ
))
1230 else if ((c
== LT
) && (c1
== LT
))
1232 if (*cp
== '=') /* a <<= b */
1241 else if ((c
== GT
) && (c1
== GT
))
1245 assigntok
= RSH
; /* a >>= b */
1252 else if ((c
== BAND
) && (c1
== BAND
))
1254 else if ((c
== BOR
) && (c1
== BOR
))
1256 else if ((c
== '*') && (c1
== '*'))
1258 else if ((c
== '-' || c
== '+') && c1
== c
&& curtok
== STR
)
1259 c
= (c
== '-') ? POSTDEC
: POSTINC
;
1260 else if ((c
== '-' || c
== '+') && c1
== c
)
1262 /* Quickly scan forward to see if this is followed by optional
1263 whitespace and an identifier. */
1265 while (xp
&& *xp
&& cr_whitespace (*xp
))
1267 if (legal_variable_starter ((unsigned char)*xp
))
1268 c
= (c
== '-') ? PREDEC
: PREINC
;
1270 cp
--; /* not preinc or predec, so unget the character */
1272 else if (c1
== EQ
&& member (c
, "*/%+-&^|"))
1274 assigntok
= c
; /* a OP= b */
1277 else if (_is_arithop (c
) == 0)
1280 /* use curtok, since it hasn't been copied to lasttok yet */
1281 if (curtok
== 0 || _is_arithop (curtok
) || _is_multiop (curtok
))
1282 evalerror (_("syntax error: operand expected"));
1284 evalerror (_("syntax error: invalid arithmetic operator"));
1287 cp
--; /* `unget' the character */
1289 /* Should check here to make sure that the current character is one
1290 of the recognized operators and flag an error if not. Could create
1291 a character map the first time through and check it on subsequent
1305 name
= this_command_name
;
1306 for (t
= expression
; whitespace (*t
); t
++)
1308 internal_error (_("%s%s%s: %s (error token is \"%s\")"),
1309 name
? name
: "", name
? ": " : "", t
,
1310 msg
, (lasttp
&& *lasttp
) ? lasttp
: "");
1311 longjmp (evalbuf
, 1);
1314 /* Convert a string to an intmax_t integer, with an arbitrary base.
1317 Anything else: [base#]number (this is implemented to match ksh93)
1319 Base may be >=2 and <=64. If base is <= 36, the numbers are drawn
1320 from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1321 interchangably. If base is > 36 and <= 64, the numbers are drawn
1322 from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, @ = 62, _ = 63 --
1323 you get the picture). */
1330 register unsigned char c
;
1331 int base
, foundbase
;
1346 if (*s
== 'x' || *s
== 'X')
1357 for (c
= *s
++; c
; c
= *s
++)
1362 evalerror (_("invalid number"));
1364 /* Illegal base specifications raise an evaluation error. */
1365 if (val
< 2 || val
> 64)
1366 evalerror (_("invalid arithmetic base"));
1372 else if (ISALNUM(c
) || (c
== '_') || (c
== '@'))
1376 else if (c
>= 'a' && c
<= 'z')
1378 else if (c
>= 'A' && c
<= 'Z')
1379 c
-= 'A' - ((base
<= 36) ? 10 : 36);
1386 evalerror (_("value too great for base"));
1388 val
= (val
* base
) + c
;
1397 #if defined (EXPR_TEST)
1402 return (malloc (n
));
1410 return (realloc (s
, n
));
1413 SHELL_VAR
*find_variable () { return 0;}
1414 SHELL_VAR
*bind_variable () { return 0; }
1416 char *get_string_value () { return 0; }
1418 procenv_t top_level
;
1428 if (setjmp (top_level
))
1431 for (i
= 1; i
< argc
; i
++)
1433 v
= evalexp (argv
[i
], &expok
);
1435 fprintf (stderr
, _("%s: expression error\n"), argv
[i
]);
1437 printf ("'%s' -> %ld\n", argv
[i
], v
);
1443 builtin_error (format
, arg1
, arg2
, arg3
, arg4
, arg5
)
1446 fprintf (stderr
, "expr: ");
1447 fprintf (stderr
, format
, arg1
, arg2
, arg3
, arg4
, arg5
);
1448 fprintf (stderr
, "\n");
1459 #endif /* EXPR_TEST */