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