sh: Remove undefined behaviour due to overflow in +/-/* in arithmetic.
[dragonfly.git] / bin / sh / arith_yacc.c
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  * $FreeBSD: src/bin/sh/arith_yacc.c,v 1.7 2011/11/08 23:54:39 jilles Exp $
35  */
36
37 #include <limits.h>
38 #include <errno.h>
39 #include <inttypes.h>
40 #include <stdlib.h>
41 #include <stdio.h>
42 #include "arith.h"
43 #include "arith_yacc.h"
44 #include "builtins.h"
45 #include "expand.h"
46 #include "shell.h"
47 #include "error.h"
48 #include "memalloc.h"
49 #include "output.h"
50 #include "options.h"
51 #include "var.h"
52
53 #if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ
54 #error Arithmetic tokens are out of order.
55 #endif
56
57 static const char *arith_startbuf;
58
59 const char *arith_buf;
60 union yystype yylval;
61
62 static int last_token;
63
64 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
65
66 static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
67         ARITH_PRECEDENCE(ARITH_MUL, 0),
68         ARITH_PRECEDENCE(ARITH_DIV, 0),
69         ARITH_PRECEDENCE(ARITH_REM, 0),
70         ARITH_PRECEDENCE(ARITH_ADD, 1),
71         ARITH_PRECEDENCE(ARITH_SUB, 1),
72         ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
73         ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
74         ARITH_PRECEDENCE(ARITH_LT, 3),
75         ARITH_PRECEDENCE(ARITH_LE, 3),
76         ARITH_PRECEDENCE(ARITH_GT, 3),
77         ARITH_PRECEDENCE(ARITH_GE, 3),
78         ARITH_PRECEDENCE(ARITH_EQ, 4),
79         ARITH_PRECEDENCE(ARITH_NE, 4),
80         ARITH_PRECEDENCE(ARITH_BAND, 5),
81         ARITH_PRECEDENCE(ARITH_BXOR, 6),
82         ARITH_PRECEDENCE(ARITH_BOR, 7),
83 };
84
85 #define ARITH_MAX_PREC 8
86
87 static __dead2 void
88 yyerror(const char *s)
89 {
90         error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
91         /* NOTREACHED */
92 }
93
94 static arith_t
95 arith_lookupvarint(char *varname)
96 {
97         const char *str;
98         char *p;
99         arith_t result;
100
101         str = lookupvar(varname);
102         if (uflag && str == NULL)
103                 yyerror("variable not set");
104         if (str == NULL || *str == '\0')
105                 str = "0";
106         errno = 0;
107         result = strtoarith_t(str, &p, 0);
108         if (errno != 0 || *p != '\0')
109                 yyerror("variable conversion error");
110         return result;
111 }
112
113 static inline int
114 arith_prec(int op)
115 {
116         return prec[op - ARITH_BINOP_MIN];
117 }
118
119 static inline int
120 higher_prec(int op1, int op2)
121 {
122         return arith_prec(op1) < arith_prec(op2);
123 }
124
125 static arith_t
126 do_binop(int op, arith_t a, arith_t b)
127 {
128
129         switch (op) {
130         default:
131         case ARITH_REM:
132         case ARITH_DIV:
133                 if (!b)
134                         yyerror("division by zero");
135                 if (a == ARITH_MIN && b == -1)
136                         yyerror("divide error");
137                 return op == ARITH_REM ? a % b : a / b;
138         case ARITH_MUL:
139                 return (uintmax_t)a * (uintmax_t)b;
140         case ARITH_ADD:
141                 return (uintmax_t)a + (uintmax_t)b;
142         case ARITH_SUB:
143                 return (uintmax_t)a - (uintmax_t)b;
144         case ARITH_LSHIFT:
145                 return a << b;
146         case ARITH_RSHIFT:
147                 return a >> b;
148         case ARITH_LT:
149                 return a < b;
150         case ARITH_LE:
151                 return a <= b;
152         case ARITH_GT:
153                 return a > b;
154         case ARITH_GE:
155                 return a >= b;
156         case ARITH_EQ:
157                 return a == b;
158         case ARITH_NE:
159                 return a != b;
160         case ARITH_BAND:
161                 return a & b;
162         case ARITH_BXOR:
163                 return a ^ b;
164         case ARITH_BOR:
165                 return a | b;
166         }
167 }
168
169 static arith_t assignment(int var, int noeval);
170
171 static arith_t
172 primary(int token, union yystype *val, int op, int noeval)
173 {
174         arith_t result;
175
176 again:
177         switch (token) {
178         case ARITH_LPAREN:
179                 result = assignment(op, noeval);
180                 if (last_token != ARITH_RPAREN)
181                         yyerror("expecting ')'");
182                 last_token = yylex();
183                 return result;
184         case ARITH_NUM:
185                 last_token = op;
186                 return val->val;
187         case ARITH_VAR:
188                 last_token = op;
189                 return noeval ? val->val : arith_lookupvarint(val->name);
190         case ARITH_ADD:
191                 token = op;
192                 *val = yylval;
193                 op = yylex();
194                 goto again;
195         case ARITH_SUB:
196                 *val = yylval;
197                 return -primary(op, val, yylex(), noeval);
198         case ARITH_NOT:
199                 *val = yylval;
200                 return !primary(op, val, yylex(), noeval);
201         case ARITH_BNOT:
202                 *val = yylval;
203                 return ~primary(op, val, yylex(), noeval);
204         default:
205                 yyerror("expecting primary");
206         }
207 }
208
209 static arith_t
210 binop2(arith_t a, int op, int precedence, int noeval)
211 {
212         for (;;) {
213                 union yystype val;
214                 arith_t b;
215                 int op2;
216                 int token;
217
218                 token = yylex();
219                 val = yylval;
220
221                 b = primary(token, &val, yylex(), noeval);
222
223                 op2 = last_token;
224                 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
225                     higher_prec(op2, op)) {
226                         b = binop2(b, op2, arith_prec(op), noeval);
227                         op2 = last_token;
228                 }
229
230                 a = noeval ? b : do_binop(op, a, b);
231
232                 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX ||
233                     arith_prec(op2) >= precedence)
234                         return a;
235
236                 op = op2;
237         }
238 }
239
240 static arith_t
241 binop(int token, union yystype *val, int op, int noeval)
242 {
243         arith_t a = primary(token, val, op, noeval);
244
245         op = last_token;
246         if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX)
247                 return a;
248
249         return binop2(a, op, ARITH_MAX_PREC, noeval);
250 }
251
252 static arith_t
253 and(int token, union yystype *val, int op, int noeval)
254 {
255         arith_t a = binop(token, val, op, noeval);
256         arith_t b;
257
258         op = last_token;
259         if (op != ARITH_AND)
260                 return a;
261
262         token = yylex();
263         *val = yylval;
264
265         b = and(token, val, yylex(), noeval | !a);
266
267         return a && b;
268 }
269
270 static arith_t
271 or(int token, union yystype *val, int op, int noeval)
272 {
273         arith_t a = and(token, val, op, noeval);
274         arith_t b;
275
276         op = last_token;
277         if (op != ARITH_OR)
278                 return a;
279
280         token = yylex();
281         *val = yylval;
282
283         b = or(token, val, yylex(), noeval | !!a);
284
285         return a || b;
286 }
287
288 static arith_t
289 cond(int token, union yystype *val, int op, int noeval)
290 {
291         arith_t a = or(token, val, op, noeval);
292         arith_t b;
293         arith_t c;
294
295         if (last_token != ARITH_QMARK)
296                 return a;
297
298         b = assignment(yylex(), noeval | !a);
299
300         if (last_token != ARITH_COLON)
301                 yyerror("expecting ':'");
302
303         token = yylex();
304         *val = yylval;
305
306         c = cond(token, val, yylex(), noeval | !!a);
307
308         return a ? b : c;
309 }
310
311 static arith_t
312 assignment(int var, int noeval)
313 {
314         union yystype val = yylval;
315         int op = yylex();
316         arith_t result;
317         char sresult[DIGITS(result) + 1];
318
319         if (var != ARITH_VAR)
320                 return cond(var, &val, op, noeval);
321
322         if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX))
323                 return cond(var, &val, op, noeval);
324
325         result = assignment(yylex(), noeval);
326         if (noeval)
327                 return result;
328
329         if (op != ARITH_ASS)
330                 result = do_binop(op - 11, arith_lookupvarint(val.name), result);
331         snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result);
332         setvar(val.name, sresult, 0);
333         return result;
334 }
335
336 arith_t
337 arith(const char *s)
338 {
339         struct stackmark smark;
340         arith_t result;
341
342         setstackmark(&smark);
343
344         arith_buf = arith_startbuf = s;
345
346         result = assignment(yylex(), 0);
347
348         if (last_token)
349                 yyerror("expecting EOF");
350
351         popstackmark(&smark);
352
353         return result;
354 }
355
356 /*
357  *  The exp(1) builtin.
358  */
359 int
360 letcmd(int argc, char **argv)
361 {
362         const char *p;
363         char *concat;
364         char **ap;
365         arith_t i;
366
367         if (argc > 1) {
368                 p = argv[1];
369                 if (argc > 2) {
370                         /*
371                          * Concatenate arguments.
372                          */
373                         STARTSTACKSTR(concat);
374                         ap = argv + 2;
375                         for (;;) {
376                                 while (*p)
377                                         STPUTC(*p++, concat);
378                                 if ((p = *ap++) == NULL)
379                                         break;
380                                 STPUTC(' ', concat);
381                         }
382                         STPUTC('\0', concat);
383                         p = grabstackstr(concat);
384                 }
385         } else
386                 p = "";
387
388         i = arith(p);
389
390         out1fmt(ARITH_FORMAT_STR "\n", i);
391         return !i;
392 }
393