usr/dash/arith_yacc.c

/*-
 * Copyright (c) 1993
 *	The Regents of the University of California.  All rights reserved.
 * Copyright (c) 2007
 *	Herbert Xu <herbert@gondor.apana.org.au>.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Kenneth Almquist.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <inttypes.h>
#include <stdint.h>
#include <stdlib.h>
#include "arith_yacc.h"
#include "expand.h"
#include "shell.h"
#include "error.h"
#include "output.h"
#include "var.h"

#if ARITH_BOR + 11 != ARITH_BORASS || ARITH_ASS + 11 != ARITH_EQ
#error Arithmetic tokens are out of order.
#endif

static const char *arith_startbuf;

const char *arith_buf;
union yystype yylval;

static int last_token;

#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec

static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
	ARITH_PRECEDENCE(ARITH_MUL, 0),
	ARITH_PRECEDENCE(ARITH_DIV, 0),
	ARITH_PRECEDENCE(ARITH_REM, 0),
	ARITH_PRECEDENCE(ARITH_ADD, 1),
	ARITH_PRECEDENCE(ARITH_SUB, 1),
	ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
	ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
	ARITH_PRECEDENCE(ARITH_LT, 3),
	ARITH_PRECEDENCE(ARITH_LE, 3),
	ARITH_PRECEDENCE(ARITH_GT, 3),
	ARITH_PRECEDENCE(ARITH_GE, 3),
	ARITH_PRECEDENCE(ARITH_EQ, 4),
	ARITH_PRECEDENCE(ARITH_NE, 4),
	ARITH_PRECEDENCE(ARITH_BAND, 5),
	ARITH_PRECEDENCE(ARITH_BXOR, 6),
	ARITH_PRECEDENCE(ARITH_BOR, 7),
};

#define ARITH_MAX_PREC 8

static void yyerror(const char *s) __attribute__ ((noreturn));
static void yyerror(const char *s)
{
	sh_error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
	/* NOTREACHED */
}

static inline int arith_prec(int op)
{
	return prec[op - ARITH_BINOP_MIN];
}

static inline int higher_prec(int op1, int op2)
{
	return arith_prec(op1) < arith_prec(op2);
}

static intmax_t do_binop(int op, intmax_t a, intmax_t b)
{
#ifdef HAVE_IMAXDIV
	imaxdiv_t div;
#endif

	switch (op) {
	default:
	case ARITH_REM:
	case ARITH_DIV:
		if (!b)
			yyerror("division by zero");
#ifdef HAVE_IMAXDIV
		div = imaxdiv(a, b);
		return op == ARITH_REM ? div.rem : div.quot;
#else
		return op == ARITH_REM ? a % b : a / b;
#endif
	case ARITH_MUL:
		return a * b;
	case ARITH_ADD:
		return a + b;
	case ARITH_SUB:
		return a - b;
	case ARITH_LSHIFT:
		return a << b;
	case ARITH_RSHIFT:
		return a >> b;
	case ARITH_LT:
		return a < b;
	case ARITH_LE:
		return a <= b;
	case ARITH_GT:
		return a > b;
	case ARITH_GE:
		return a >= b;
	case ARITH_EQ:
		return a == b;
	case ARITH_NE:
		return a != b;
	case ARITH_BAND:
		return a & b;
	case ARITH_BXOR:
		return a ^ b;
	case ARITH_BOR:
		return a | b;
	}
}

static intmax_t assignment(int var, int noeval);

static intmax_t primary(int token, union yystype *val, int op, int noeval)
{
	intmax_t result;

again:
	switch (token) {
	case ARITH_LPAREN:
		result = assignment(op, noeval);
		if (last_token != ARITH_RPAREN)
			yyerror("expecting ')'");
		last_token = yylex();
		return result;
	case ARITH_NUM:
		last_token = op;
		return val->val;
	case ARITH_VAR:
		last_token = op;
		return noeval ? val->val : lookupvarint(val->name);
	case ARITH_ADD:
		token = op;
		*val = yylval;
		op = yylex();
		goto again;
	case ARITH_SUB:
		*val = yylval;
		return -primary(op, val, yylex(), noeval);
	case ARITH_NOT:
		*val = yylval;
		return !primary(op, val, yylex(), noeval);
	case ARITH_BNOT:
		*val = yylval;
		return ~primary(op, val, yylex(), noeval);
	default:
		yyerror("expecting primary");
	}
}

static intmax_t binop2(intmax_t a, int op, int prec, int noeval)
{
	for (;;) {
		union yystype val;
		intmax_t b;
		int op2;
		int token;

		token = yylex();
		val = yylval;

		b = primary(token, &val, yylex(), noeval);

		op2 = last_token;
		if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
		    higher_prec(op2, op)) {
			b = binop2(b, op2, arith_prec(op), noeval);
			op2 = last_token;
		}

		a = noeval ? b : do_binop(op, a, b);

		if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX ||
		    arith_prec(op2) >= prec)
			return a;

		op = op2;
	}
}

static intmax_t binop(int token, union yystype *val, int op, int noeval)
{
	intmax_t a = primary(token, val, op, noeval);

	op = last_token;
	if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX)
		return a;

	return binop2(a, op, ARITH_MAX_PREC, noeval);
}

static intmax_t and(int token, union yystype *val, int op, int noeval)
{
	intmax_t a = binop(token, val, op, noeval);
	intmax_t b;

	op = last_token;
	if (op != ARITH_AND)
		return a;

	token = yylex();
	*val = yylval;

	b = and(token, val, yylex(), noeval | !a);

	return a && b;
}

static intmax_t or(int token, union yystype *val, int op, int noeval)
{
	intmax_t a = and(token, val, op, noeval);
	intmax_t b;

	op = last_token;
	if (op != ARITH_OR)
		return a;

	token = yylex();
	*val = yylval;

	b = or(token, val, yylex(), noeval | !!a);

	return a || b;
}

static intmax_t cond(int token, union yystype *val, int op, int noeval)
{
	intmax_t a = or(token, val, op, noeval);
	intmax_t b;
	intmax_t c;

	if (last_token != ARITH_QMARK)
		return a;

	b = assignment(yylex(), noeval | !a);

	if (last_token != ARITH_COLON)
		yyerror("expecting ':'");

	token = yylex();
	*val = yylval;

	c = cond(token, val, yylex(), noeval | !!a);

	return a ? b : c;
}

static intmax_t assignment(int var, int noeval)
{
	union yystype val = yylval;
	int op = yylex();
	intmax_t result;

	if (var != ARITH_VAR)
		return cond(var, &val, op, noeval);

	if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX))
		return cond(var, &val, op, noeval);

	result = assignment(yylex(), noeval);
	if (noeval)
		return result;

	return setvarint(val.name,
			 op == ARITH_ASS ? result :
			 do_binop(op - 11, lookupvarint(val.name), result), 0);
}

intmax_t arith(const char *s)
{
	intmax_t result;

	arith_buf = arith_startbuf = s;

	result = assignment(yylex(), 0);

	if (last_token)
		yyerror("expecting EOF");

	return result;
}
1	niro	1122	/*-
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 <stdint.h>
37			#include <stdlib.h>
38			#include "arith_yacc.h"
39			#include "expand.h"
40			#include "shell.h"
41			#include "error.h"
42			#include "output.h"
43			#include "var.h"
44
45			#if ARITH_BOR + 11 != ARITH_BORASS \|\| ARITH_ASS + 11 != ARITH_EQ
46			#error Arithmetic tokens are out of order.
47			#endif
48
49			static const char *arith_startbuf;
50
51			const char *arith_buf;
52			union yystype yylval;
53
54			static int last_token;
55
56			#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
57
58			static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
59			ARITH_PRECEDENCE(ARITH_MUL, 0),
60			ARITH_PRECEDENCE(ARITH_DIV, 0),
61			ARITH_PRECEDENCE(ARITH_REM, 0),
62			ARITH_PRECEDENCE(ARITH_ADD, 1),
63			ARITH_PRECEDENCE(ARITH_SUB, 1),
64			ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
65			ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
66			ARITH_PRECEDENCE(ARITH_LT, 3),
67			ARITH_PRECEDENCE(ARITH_LE, 3),
68			ARITH_PRECEDENCE(ARITH_GT, 3),
69			ARITH_PRECEDENCE(ARITH_GE, 3),
70			ARITH_PRECEDENCE(ARITH_EQ, 4),
71			ARITH_PRECEDENCE(ARITH_NE, 4),
72			ARITH_PRECEDENCE(ARITH_BAND, 5),
73			ARITH_PRECEDENCE(ARITH_BXOR, 6),
74			ARITH_PRECEDENCE(ARITH_BOR, 7),
75			};
76
77			#define ARITH_MAX_PREC 8
78
79			static void yyerror(const char *s) __attribute__ ((noreturn));
80			static void yyerror(const char *s)
81			{
82			sh_error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
83			/* NOTREACHED */
84			}
85
86			static inline int arith_prec(int op)
87			{
88			return prec[op - ARITH_BINOP_MIN];
89			}
90
91			static inline int higher_prec(int op1, int op2)
92			{
93			return arith_prec(op1) < arith_prec(op2);
94			}
95
96			static intmax_t do_binop(int op, intmax_t a, intmax_t b)
97			{
98			#ifdef HAVE_IMAXDIV
99			imaxdiv_t div;
100			#endif
101
102			switch (op) {
103			default:
104			case ARITH_REM:
105			case ARITH_DIV:
106			if (!b)
107			yyerror("division by zero");
108			#ifdef HAVE_IMAXDIV
109			div = imaxdiv(a, b);
110			return op == ARITH_REM ? div.rem : div.quot;
111			#else
112			return op == ARITH_REM ? a % b : a / b;
113			#endif
114			case ARITH_MUL:
115			return a * b;
116			case ARITH_ADD:
117			return a + b;
118			case ARITH_SUB:
119			return a - b;
120			case ARITH_LSHIFT:
121			return a << b;
122			case ARITH_RSHIFT:
123			return a >> b;
124			case ARITH_LT:
125			return a < b;
126			case ARITH_LE:
127			return a <= b;
128			case ARITH_GT:
129			return a > b;
130			case ARITH_GE:
131			return a >= b;
132			case ARITH_EQ:
133			return a == b;
134			case ARITH_NE:
135			return a != b;
136			case ARITH_BAND:
137			return a & b;
138			case ARITH_BXOR:
139			return a ^ b;
140			case ARITH_BOR:
141			return a \| b;
142			}
143			}
144
145			static intmax_t assignment(int var, int noeval);
146
147			static intmax_t primary(int token, union yystype *val, int op, int noeval)
148			{
149			intmax_t result;
150
151			again:
152			switch (token) {
153			case ARITH_LPAREN:
154			result = assignment(op, noeval);
155			if (last_token != ARITH_RPAREN)
156			yyerror("expecting ')'");
157			last_token = yylex();
158			return result;
159			case ARITH_NUM:
160			last_token = op;
161			return val->val;
162			case ARITH_VAR:
163			last_token = op;
164			return noeval ? val->val : lookupvarint(val->name);
165			case ARITH_ADD:
166			token = op;
167			*val = yylval;
168			op = yylex();
169			goto again;
170			case ARITH_SUB:
171			*val = yylval;
172			return -primary(op, val, yylex(), noeval);
173			case ARITH_NOT:
174			*val = yylval;
175			return !primary(op, val, yylex(), noeval);
176			case ARITH_BNOT:
177			*val = yylval;
178			return ~primary(op, val, yylex(), noeval);
179			default:
180			yyerror("expecting primary");
181			}
182			}
183
184			static intmax_t binop2(intmax_t a, int op, int prec, int noeval)
185			{
186			for (;;) {
187			union yystype val;
188			intmax_t b;
189			int op2;
190			int token;
191
192			token = yylex();
193			val = yylval;
194
195			b = primary(token, &val, yylex(), noeval);
196
197			op2 = last_token;
198			if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
199			higher_prec(op2, op)) {
200			b = binop2(b, op2, arith_prec(op), noeval);
201			op2 = last_token;
202			}
203
204			a = noeval ? b : do_binop(op, a, b);
205
206			if (op2 < ARITH_BINOP_MIN \|\| op2 >= ARITH_BINOP_MAX \|\|
207			arith_prec(op2) >= prec)
208			return a;
209
210			op = op2;
211			}
212			}
213
214			static intmax_t binop(int token, union yystype *val, int op, int noeval)
215			{
216			intmax_t a = primary(token, val, op, noeval);
217
218			op = last_token;
219			if (op < ARITH_BINOP_MIN \|\| op >= ARITH_BINOP_MAX)
220			return a;
221
222			return binop2(a, op, ARITH_MAX_PREC, noeval);
223			}
224
225			static intmax_t and(int token, union yystype *val, int op, int noeval)
226			{
227			intmax_t a = binop(token, val, op, noeval);
228			intmax_t b;
229
230			op = last_token;
231			if (op != ARITH_AND)
232			return a;
233
234			token = yylex();
235			*val = yylval;
236
237			b = and(token, val, yylex(), noeval \| !a);
238
239			return a && b;
240			}
241
242			static intmax_t or(int token, union yystype *val, int op, int noeval)
243			{
244			intmax_t a = and(token, val, op, noeval);
245			intmax_t b;
246
247			op = last_token;
248			if (op != ARITH_OR)
249			return a;
250
251			token = yylex();
252			*val = yylval;
253
254			b = or(token, val, yylex(), noeval \| !!a);
255
256			return a \|\| b;
257			}
258
259			static intmax_t cond(int token, union yystype *val, int op, int noeval)
260			{
261			intmax_t a = or(token, val, op, noeval);
262			intmax_t b;
263			intmax_t c;
264
265			if (last_token != ARITH_QMARK)
266			return a;
267
268			b = assignment(yylex(), noeval \| !a);
269
270			if (last_token != ARITH_COLON)
271			yyerror("expecting ':'");
272
273			token = yylex();
274			*val = yylval;
275
276			c = cond(token, val, yylex(), noeval \| !!a);
277
278			return a ? b : c;
279			}
280
281			static intmax_t assignment(int var, int noeval)
282			{
283			union yystype val = yylval;
284			int op = yylex();
285			intmax_t result;
286
287			if (var != ARITH_VAR)
288			return cond(var, &val, op, noeval);
289
290			if (op != ARITH_ASS && (op < ARITH_ASS_MIN \|\| op >= ARITH_ASS_MAX))
291			return cond(var, &val, op, noeval);
292
293			result = assignment(yylex(), noeval);
294			if (noeval)
295			return result;
296
297			return setvarint(val.name,
298			op == ARITH_ASS ? result :
299			do_binop(op - 11, lookupvarint(val.name), result), 0);
300			}
301
302			intmax_t arith(const char *s)
303			{
304			intmax_t result;
305
306			arith_buf = arith_startbuf = s;
307
308			result = assignment(yylex(), 0);
309
310			if (last_token)
311			yyerror("expecting EOF");
312
313			return result;
314			}