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