arith_yacc.c revision 218626 
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: head/bin/sh/arith_yacc.c 218626 2011-02-12 23:44:05Z jilles $");
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
57static const char *arith_startbuf;
58
59const char *arith_buf;
60union yystype yylval;
61
62static int last_token;
63
64#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
65
66static 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
87static __dead2 void yyerror(const char *s)
88{
89	error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
90	/* NOTREACHED */
91}
92
93static 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
109static inline int arith_prec(int op)
110{
111	return prec[op - ARITH_BINOP_MIN];
112}
113
114static inline int higher_prec(int op1, int op2)
115{
116	return arith_prec(op1) < arith_prec(op2);
117}
118
119static 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
162static arith_t assignment(int var, int noeval);
163
164static arith_t primary(int token, union yystype *val, int op, int noeval)
165{
166	arith_t result;
167
168again:
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
201static arith_t binop2(arith_t a, int op, int prec, 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) >= prec)
225			return a;
226
227		op = op2;
228	}
229}
230
231static 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
242static 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
259static 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
276static 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
298static 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
322arith_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 */
344int
345expcmd(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