]>
git.ipfire.org Git - thirdparty/bash.git/blob - expr.c
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>
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 int 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 (); /* lexical analyzer */
150 static long subexpr (), expassign (), exp0 (), exp1 (), exp2 (), exp3 (),
151 exp4 (), exp5 (), expshift (), expland (), explor (),
152 expband (), expbor (), expbxor (), expcond (), exppower (),
154 static long strlong ();
155 static void evalerror ();
157 /* A structure defining a single expression context. */
160 char *expression
, *tp
, *lasttp
;
171 /* Global var which contains the stack of expression contexts. */
172 static EXPR_CONTEXT
**expr_stack
;
173 static int expr_depth
; /* Location in the stack. */
174 static int expr_stack_size
; /* Number of slots already allocated. */
176 extern char *this_command_name
;
180 (X)->curtok = curtok; \
181 (X)->lasttok = lasttok; \
183 (X)->lasttp = lasttp; \
184 (X)->tokval = tokval; \
185 (X)->tokstr = tokstr; \
186 (X)->noeval = noeval; \
189 #define RESTORETOK(X) \
191 curtok = (X)->curtok; \
192 lasttok = (X)->lasttok; \
194 lasttp = (X)->lasttp; \
195 tokval = (X)->tokval; \
196 tokstr = (X)->tokstr; \
197 noeval = (X)->noeval; \
200 /* Push and save away the contents of the globals describing the
201 current expression context. */
205 EXPR_CONTEXT
*context
;
207 if (expr_depth
>= MAX_EXPR_RECURSION_LEVEL
)
208 evalerror ("expression recursion level exceeded");
210 if (expr_depth
>= expr_stack_size
)
212 expr_stack
= (EXPR_CONTEXT
**)
213 xrealloc (expr_stack
, (expr_stack_size
+= EXPR_STACK_GROW_SIZE
)
214 * sizeof (EXPR_CONTEXT
*));
217 context
= (EXPR_CONTEXT
*)xmalloc (sizeof (EXPR_CONTEXT
));
219 context
->expression
= expression
;
222 expr_stack
[expr_depth
++] = context
;
225 /* Pop the the contents of the expression context stack into the
226 globals describing the current expression context. */
230 EXPR_CONTEXT
*context
;
233 evalerror ("recursion stack underflow");
235 context
= expr_stack
[--expr_depth
];
237 expression
= context
->expression
;
238 RESTORETOK (context
);
243 /* Evaluate EXPR, and return the arithmetic result. If VALIDP is
244 non-null, a zero is stored into the location to which it points
245 if the expression is invalid, non-zero otherwise. If a non-zero
246 value is returned in *VALIDP, the return value of evalexp() may
249 The `while' loop after the longjmp is caught relies on the above
250 implementation of pushexp and popexp leaving in expr_stack[0] the
251 values that the variables had when the program started. That is,
252 the first things saved are the initial values of the variables that
253 were assigned at program startup or by the compiler. Therefore, it is
254 safe to let the loop terminate when expr_depth == 0, without freeing up
255 any of the expr_depth[0] stuff. */
257 evalexp (expr
, validp
)
263 procenv_t old_evalbuf
;
269 /* Save the value of evalbuf to protect it around possible recursive
270 calls to evalexp (). */
271 COPY_PROCENV (evalbuf
, old_evalbuf
);
274 if (setjmp (evalbuf
))
278 tokstr
= expression
= (char *)NULL
;
280 while (--expr_depth
> 0)
282 if (expr_stack
[expr_depth
]->tokstr
)
283 free (expr_stack
[expr_depth
]->tokstr
);
285 if (expr_stack
[expr_depth
]->expression
)
286 free (expr_stack
[expr_depth
]->expression
);
288 free (expr_stack
[expr_depth
]);
290 free (expr_stack
[expr_depth
]); /* free the allocated EXPR_CONTEXT */
297 val
= subexpr (expr
);
300 /* Restore the value of evalbuf so that any subsequent longjmp calls
301 will have a valid location to jump to. */
302 COPY_PROCENV (old_evalbuf
, evalbuf
);
318 for (p
= expr
; p
&& *p
&& cr_whitespace (*p
); p
++)
321 if (p
== NULL
|| *p
== '\0')
325 curtok
= lasttok
= 0;
326 expression
= savestring (expr
);
329 tokstr
= (char *)NULL
;
334 val
= EXP_HIGHEST ();
337 evalerror ("syntax error in expression");
352 value
= expassign ();
353 while (curtok
== COMMA
)
356 value
= expassign ();
369 if (curtok
== EQ
|| curtok
== OP_ASSIGN
)
374 special
= curtok
== OP_ASSIGN
;
377 evalerror ("attempted assignment to non-variable");
381 op
= assigntok
; /* a OP= b */
385 lhs
= savestring (tokstr
);
387 value
= expassign ();
425 evalerror ("bug: bad expassign token");
433 (void)bind_int_variable (lhs
, rhs
);
437 tokstr
= (char *)NULL
; /* For freeing on errors. */
442 /* Conditional expression (expr?expr:expr) */
446 long cval
, val1
, val2
, rval
;
450 rval
= cval
= explor ();
451 if (curtok
== QUES
) /* found conditional expr */
454 if (curtok
== 0 || curtok
== COL
)
455 evalerror ("expression expected");
464 val1
= EXP_HIGHEST ();
469 evalerror ("`:' expected for conditional expression");
472 evalerror ("expression expected");
482 rval
= cval
? val1
: val2
;
492 register long val1
, val2
;
497 while (curtok
== LOR
)
520 register long val1
, val2
;
525 while (curtok
== LAND
)
548 register long val1
, val2
;
552 while (curtok
== BOR
)
566 register long val1
, val2
;
570 while (curtok
== BXOR
)
584 register long val1
, val2
;
588 while (curtok
== BAND
)
601 register long val1
, val2
;
605 while ((curtok
== EQEQ
) || (curtok
== NEQ
))
612 val1
= (val1
== val2
);
614 val1
= (val1
!= val2
);
622 register long val1
, val2
;
625 while ((curtok
== LEQ
) ||
641 else /* (op == GT) */
647 /* Left and right shifts. */
651 register long val1
, val2
;
655 while ((curtok
== LSH
) || (curtok
== RSH
))
674 register long val1
, val2
;
678 while ((curtok
== PLUS
) || (curtok
== MINUS
))
687 else if (op
== MINUS
)
696 register long val1
, val2
;
700 while ((curtok
== MUL
) ||
710 if (((op
== DIV
) || (op
== MOD
)) && (val2
== 0))
711 evalerror ("division by 0");
726 register long val1
, val2
, c
;
736 evalerror ("exponent less than 0");
737 for (c
= 1; val2
--; c
*= val1
)
754 else if (curtok
== BNOT
)
768 register long val
= 0L, v2
;
772 /* XXX - might need additional logic here to decide whether or not
773 pre-increment or pre-decrement is legal at this point. */
774 if (curtok
== PREINC
|| curtok
== PREDEC
)
776 stok
= lasttok
= curtok
;
779 /* readtok() catches this */
780 evalerror ("identifier expected after pre-increment or pre-decrement");
782 v2
= tokval
+ ((stok
== PREINC
) ? 1 : -1);
785 (void)bind_int_variable (tokstr
, vincdec
);
789 curtok
= NUM
; /* make sure --x=7 is flagged as an error */
792 else if (curtok
== MINUS
)
797 else if (curtok
== PLUS
)
802 else if (curtok
== LPAR
)
805 val
= EXP_HIGHEST ();
808 evalerror ("missing `)'");
810 /* Skip over closing paren. */
813 else if ((curtok
== NUM
) || (curtok
== STR
))
816 if (curtok
== STR
&& (*tp
== '+' || *tp
== '-') && tp
[1] == *tp
&&
817 (tp
[2] == '\0' || (isalnum (tp
[2]) == 0)))
819 /* post-increment or post-decrement */
820 v2
= val
+ ((*tp
== '+') ? 1 : -1);
823 (void)bind_int_variable (tokstr
, vincdec
);
826 curtok
= NUM
; /* make sure x++=7 is flagged as an error */
832 evalerror ("syntax error: operand expected");
837 /* Lexical analyzer/token reader for the expression evaluator. Reads the
838 next token and puts its value into curtok, while advancing past it.
839 Updates value of tp. May also set tokval (for number) or tokstr (for
845 register int c
, c1
, e
;
847 /* Skip leading whitespace. */
850 while (cp
&& (c
= *cp
) && (cr_whitespace (c
)))
856 lasttp
= tp
= cp
- 1;
866 if (legal_variable_starter (c
))
868 /* variable names not preceded with a dollar sign are shell variables. */
869 char *value
, *savecp
;
873 while (legal_variable_char (c
))
878 #if defined (ARRAY_VARS)
881 e
= skipsubscript (cp
, 0);
889 evalerror ("bad array subscript");
891 #endif /* ARRAY_VARS */
895 tokstr
= savestring (tp
);
899 tokstr
= (char *)NULL
; /* keep it from being freed */
904 if (peektok
== STR
) /* free new tokstr before old one is restored */
909 /* The tests for PREINC and PREDEC aren't strictly correct, but they
910 preserve old behavior if a construct like --x=9 is given. */
911 if (lasttok
== PREINC
|| lasttok
== PREDEC
|| peektok
!= EQ
)
913 #if defined (ARRAY_VARS)
914 value
= (e
== ']') ? get_array_value (tokstr
, 0) : get_string_value (tokstr
);
916 value
= get_string_value (tokstr
);
919 tokval
= (value
&& *value
) ? subexpr (value
) : 0;
921 #if defined (ARRAY_VARS)
923 FREE (value
); /* get_array_value returns newly-allocated memory */
934 while (digit (c
) || isletter (c
) || c
== '#' || c
== '@' || c
== '_')
940 tokval
= strlong (tp
);
948 if ((c
== EQ
) && (c1
== EQ
))
950 else if ((c
== NOT
) && (c1
== EQ
))
952 else if ((c
== GT
) && (c1
== EQ
))
954 else if ((c
== LT
) && (c1
== EQ
))
956 else if ((c
== LT
) && (c1
== LT
))
958 if (*cp
== '=') /* a <<= b */
967 else if ((c
== GT
) && (c1
== GT
))
971 assigntok
= RSH
; /* a >>= b */
978 else if ((c
== BAND
) && (c1
== BAND
))
980 else if ((c
== BOR
) && (c1
== BOR
))
982 else if ((c
== '*') && (c1
== '*'))
984 else if ((c
== '-') && (c1
== '-') && legal_variable_starter (*cp
))
986 else if ((c
== '+') && (c1
== '+') && legal_variable_starter (*cp
))
988 else if (c1
== EQ
&& member (c
, "*/%+-&^|"))
990 assigntok
= c
; /* a OP= b */
994 cp
--; /* `unget' the character */
1007 name
= this_command_name
;
1008 for (t
= expression
; whitespace (*t
); t
++)
1010 internal_error ("%s%s%s: %s (error token is \"%s\")",
1011 name
? name
: "", name
? ": " : "", t
,
1012 msg
, (lasttp
&& *lasttp
) ? lasttp
: "");
1013 longjmp (evalbuf
, 1);
1016 /* Convert a string to a long integer, with an arbitrary base.
1019 Anything else: [base#]number (this is implemented to match ksh93)
1021 Base may be >=2 and <=64. If base is <= 36, the numbers are drawn
1022 from [0-9][a-zA-Z], and lowercase and uppercase letters may be used
1023 interchangably. If base is > 36 and <= 64, the numbers are drawn
1024 from [0-9][a-z][A-Z]_@ (a = 10, z = 35, A = 36, Z = 61, _ = 62, @ = 63 --
1025 you get the picture). */
1033 int base
, foundbase
;
1037 if (s
== NULL
|| *s
== '\0')
1046 if (s
== NULL
|| *s
== '\0')
1050 if (*s
== 'x' || *s
== 'X')
1061 for (c
= *s
++; c
; c
= *s
++)
1066 evalerror ("bad number");
1070 /* Illegal base specifications raise an evaluation error. */
1071 if (base
< 2 || base
> 64)
1072 evalerror ("illegal arithmetic base");
1077 else if (isletter(c
) || digit(c
) || (c
== '_') || (c
== '@'))
1081 else if (c
>= 'a' && c
<= 'z')
1083 else if (c
>= 'A' && c
<= 'Z')
1084 c
-= 'A' - ((base
<= 36) ? 10 : 36);
1091 evalerror ("value too great for base");
1093 val
= (val
* base
) + c
;
1101 #if defined (EXPR_TEST)
1106 return (malloc (n
));
1114 return (realloc (s
, n
));
1117 SHELL_VAR
*find_variable () { return 0;}
1118 SHELL_VAR
*bind_variable () { return 0; }
1120 char *get_string_value () { return 0; }
1122 procenv_t top_level
;
1132 if (setjmp (top_level
))
1135 for (i
= 1; i
< argc
; i
++)
1137 v
= evalexp (argv
[i
], &expok
);
1139 fprintf (stderr
, "%s: expression error\n", argv
[i
]);
1141 printf ("'%s' -> %ld\n", argv
[i
], v
);
1147 builtin_error (format
, arg1
, arg2
, arg3
, arg4
, arg5
)
1150 fprintf (stderr
, "expr: ");
1151 fprintf (stderr
, format
, arg1
, arg2
, arg3
, arg4
, arg5
);
1152 fprintf (stderr
, "\n");
1163 #endif /* EXPR_TEST */