1 /*-
2 * Copyright (c) 1993
3 * The Regents of the University of California. All rights reserved.
4 * Copyright (c) 2007
5 * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Kenneth Almquist.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #include <inttypes.h>
36 #include <stdlib.h>
37 #include "arith_yacc.h"
38 #include "expand.h"
39 #include "shell.h"
40 #include "error.h"
41 #include "output.h"
42 #include "var.h"
43
44 #if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ
45 #error Arithmetic tokens are out of order.
46 #endif
47
48 static const char *arith_startbuf;
49
50 const char *arith_buf;
51 union yystype yylval;
52
53 static int last_token;
54
55 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
56
57 static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
58 ARITH_PRECEDENCE(ARITH_MUL, 0),
59 ARITH_PRECEDENCE(ARITH_DIV, 0),
60 ARITH_PRECEDENCE(ARITH_REM, 0),
61 ARITH_PRECEDENCE(ARITH_ADD, 1),
62 ARITH_PRECEDENCE(ARITH_SUB, 1),
63 ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
64 ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
65 ARITH_PRECEDENCE(ARITH_LT, 3),
66 ARITH_PRECEDENCE(ARITH_LE, 3),
67 ARITH_PRECEDENCE(ARITH_GT, 3),
68 ARITH_PRECEDENCE(ARITH_GE, 3),
69 ARITH_PRECEDENCE(ARITH_EQ, 4),
70 ARITH_PRECEDENCE(ARITH_NE, 4),
71 ARITH_PRECEDENCE(ARITH_BAND, 5),
72 ARITH_PRECEDENCE(ARITH_BXOR, 6),
73 ARITH_PRECEDENCE(ARITH_BOR, 7),
74 };
75
76 #define ARITH_MAX_PREC 8
77
78 static void yyerror(const char *s) __attribute__ ((noreturn));
yyerror(const char * s)79 static void yyerror(const char *s)
80 {
81 sh_error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
82 /* NOTREACHED */
83 }
84
arith_prec(int op)85 static inline int arith_prec(int op)
86 {
87 return prec[op - ARITH_BINOP_MIN];
88 }
89
higher_prec(int op1,int op2)90 static inline int higher_prec(int op1, int op2)
91 {
92 return arith_prec(op1) < arith_prec(op2);
93 }
94
do_binop(int op,intmax_t a,intmax_t b)95 static intmax_t do_binop(int op, intmax_t a, intmax_t b)
96 {
97 switch (op) {
98 default:
99 case ARITH_REM:
100 case ARITH_DIV:
101 if (!b)
102 yyerror("division by zero");
103 return op == ARITH_REM ? a % b : a / b;
104 case ARITH_MUL:
105 return a * b;
106 case ARITH_ADD:
107 return a + b;
108 case ARITH_SUB:
109 return a - b;
110 case ARITH_LSHIFT:
111 return a << b;
112 case ARITH_RSHIFT:
113 return a >> b;
114 case ARITH_LT:
115 return a < b;
116 case ARITH_LE:
117 return a <= b;
118 case ARITH_GT:
119 return a > b;
120 case ARITH_GE:
121 return a >= b;
122 case ARITH_EQ:
123 return a == b;
124 case ARITH_NE:
125 return a != b;
126 case ARITH_BAND:
127 return a & b;
128 case ARITH_BXOR:
129 return a ^ b;
130 case ARITH_BOR:
131 return a | b;
132 }
133 }
134
135 static intmax_t assignment(int var, int noeval);
136
primary(int token,union yystype * val,int op,int noeval)137 static intmax_t primary(int token, union yystype *val, int op, int noeval)
138 {
139 intmax_t result;
140
141 again:
142 switch (token) {
143 case ARITH_LPAREN:
144 result = assignment(op, noeval);
145 if (last_token != ARITH_RPAREN)
146 yyerror("expecting ')'");
147 last_token = yylex();
148 return result;
149 case ARITH_NUM:
150 last_token = op;
151 return val->val;
152 case ARITH_VAR:
153 last_token = op;
154 return noeval ? val->val : lookupvarint(val->name);
155 case ARITH_ADD:
156 token = op;
157 *val = yylval;
158 op = yylex();
159 goto again;
160 case ARITH_SUB:
161 *val = yylval;
162 return -primary(op, val, yylex(), noeval);
163 case ARITH_NOT:
164 *val = yylval;
165 return !primary(op, val, yylex(), noeval);
166 case ARITH_BNOT:
167 *val = yylval;
168 return ~primary(op, val, yylex(), noeval);
169 default:
170 yyerror("expecting primary");
171 }
172 }
173
binop2(intmax_t a,int op,int prec,int noeval)174 static intmax_t binop2(intmax_t a, int op, int prec, int noeval)
175 {
176 for (;;) {
177 union yystype val;
178 intmax_t b;
179 int op2;
180 int token;
181
182 token = yylex();
183 val = yylval;
184
185 b = primary(token, &val, yylex(), noeval);
186
187 op2 = last_token;
188 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
189 higher_prec(op2, op)) {
190 b = binop2(b, op2, arith_prec(op), noeval);
191 op2 = last_token;
192 }
193
194 a = noeval ? b : do_binop(op, a, b);
195
196 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX ||
197 arith_prec(op2) >= prec)
198 return a;
199
200 op = op2;
201 }
202 }
203
binop(int token,union yystype * val,int op,int noeval)204 static intmax_t binop(int token, union yystype *val, int op, int noeval)
205 {
206 intmax_t a = primary(token, val, op, noeval);
207
208 op = last_token;
209 if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX)
210 return a;
211
212 return binop2(a, op, ARITH_MAX_PREC, noeval);
213 }
214
and(int token,union yystype * val,int op,int noeval)215 static intmax_t and(int token, union yystype *val, int op, int noeval)
216 {
217 intmax_t a = binop(token, val, op, noeval);
218 intmax_t b;
219
220 op = last_token;
221 if (op != ARITH_AND)
222 return a;
223
224 token = yylex();
225 *val = yylval;
226
227 b = and(token, val, yylex(), noeval | !a);
228
229 return a && b;
230 }
231
or(int token,union yystype * val,int op,int noeval)232 static intmax_t or(int token, union yystype *val, int op, int noeval)
233 {
234 intmax_t a = and(token, val, op, noeval);
235 intmax_t b;
236
237 op = last_token;
238 if (op != ARITH_OR)
239 return a;
240
241 token = yylex();
242 *val = yylval;
243
244 b = or(token, val, yylex(), noeval | !!a);
245
246 return a || b;
247 }
248
cond(int token,union yystype * val,int op,int noeval)249 static intmax_t cond(int token, union yystype *val, int op, int noeval)
250 {
251 intmax_t a = or(token, val, op, noeval);
252 intmax_t b;
253 intmax_t c;
254
255 if (last_token != ARITH_QMARK)
256 return a;
257
258 b = assignment(yylex(), noeval | !a);
259
260 if (last_token != ARITH_COLON)
261 yyerror("expecting ':'");
262
263 token = yylex();
264 *val = yylval;
265
266 c = cond(token, val, yylex(), noeval | !!a);
267
268 return a ? b : c;
269 }
270
assignment(int var,int noeval)271 static intmax_t assignment(int var, int noeval)
272 {
273 union yystype val = yylval;
274 int op = yylex();
275 intmax_t result;
276
277 if (var != ARITH_VAR)
278 return cond(var, &val, op, noeval);
279
280 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX))
281 return cond(var, &val, op, noeval);
282
283 result = assignment(yylex(), noeval);
284 if (noeval)
285 return result;
286
287 return setvarint(val.name,
288 op == ARITH_ASS ? result :
289 do_binop(op - 11, lookupvarint(val.name), result), 0);
290 }
291
arith(const char * s)292 intmax_t arith(const char *s)
293 {
294 intmax_t result;
295
296 arith_buf = arith_startbuf = s;
297
298 result = assignment(yylex(), 0);
299
300 if (last_token)
301 yyerror("expecting EOF");
302
303 return result;
304 }
305