1/*	$NetBSD: arithmetic.c,v 1.5 2018/04/21 23:01:29 kre Exp $	*/
2
3/*-
4 * Copyright (c) 1993
5 *	The Regents of the University of California.  All rights reserved.
6 * Copyright (c) 2007
7 *	Herbert Xu <herbert@gondor.apana.org.au>.  All rights reserved.
8 *
9 * This code is derived from software contributed to Berkeley by
10 * Kenneth Almquist.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 *    notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 *    notice, this list of conditions and the following disclaimer in the
19 *    documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 *    may be used to endorse or promote products derived from this software
22 *    without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * From FreeBSD, who obtained it from dash, modified both times...
37 */
38
39#include <sys/cdefs.h>
40
41#ifndef lint
42__RCSID("$NetBSD: arithmetic.c,v 1.5 2018/04/21 23:01:29 kre Exp $");
43#endif /* not lint */
44
45#include <limits.h>
46#include <errno.h>
47#include <inttypes.h>
48#include <stdlib.h>
49#include <stdio.h>
50#include <string.h>
51
52#include "shell.h"
53#include "arithmetic.h"
54#include "arith_tokens.h"
55#include "expand.h"
56#include "error.h"
57#include "memalloc.h"
58#include "output.h"
59#include "options.h"
60#include "var.h"
61#include "show.h"
62#include "syntax.h"
63
64#if ARITH_BOR + ARITH_ASS_GAP != ARITH_BORASS || \
65	ARITH_ASS + ARITH_ASS_GAP != ARITH_EQ
66#error Arithmetic tokens are out of order.
67#endif
68
69static const char *arith_startbuf;
70
71const char *arith_buf;
72union a_token_val a_t_val;
73
74static int last_token;
75
76int arith_lno, arith_var_lno;
77
78#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
79
80static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = {
81	ARITH_PRECEDENCE(ARITH_MUL, 0),
82	ARITH_PRECEDENCE(ARITH_DIV, 0),
83	ARITH_PRECEDENCE(ARITH_REM, 0),
84	ARITH_PRECEDENCE(ARITH_ADD, 1),
85	ARITH_PRECEDENCE(ARITH_SUB, 1),
86	ARITH_PRECEDENCE(ARITH_LSHIFT, 2),
87	ARITH_PRECEDENCE(ARITH_RSHIFT, 2),
88	ARITH_PRECEDENCE(ARITH_LT, 3),
89	ARITH_PRECEDENCE(ARITH_LE, 3),
90	ARITH_PRECEDENCE(ARITH_GT, 3),
91	ARITH_PRECEDENCE(ARITH_GE, 3),
92	ARITH_PRECEDENCE(ARITH_EQ, 4),
93	ARITH_PRECEDENCE(ARITH_NE, 4),
94	ARITH_PRECEDENCE(ARITH_BAND, 5),
95	ARITH_PRECEDENCE(ARITH_BXOR, 6),
96	ARITH_PRECEDENCE(ARITH_BOR, 7),
97};
98
99#define ARITH_MAX_PREC 8
100
101int expcmd(int, char **);
102
103static void __dead
104arith_err(const char *s)
105{
106	error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
107	/* NOTREACHED */
108}
109
110static intmax_t
111arith_lookupvarint(char *varname)
112{
113	const char *str;
114	char *p;
115	intmax_t result;
116	const int oln = line_number;
117
118	VTRACE(DBG_ARITH, ("Arith var lookup(\"%s\") with lno=%d\n", varname,
119	    arith_var_lno));
120
121	line_number = arith_var_lno;
122	str = lookupvar(varname);
123	line_number = oln;
124
125	if (uflag && str == NULL)
126		arith_err("variable not set");
127	if (str == NULL || *str == '\0')
128		str = "0";
129	errno = 0;
130	result = strtoimax(str, &p, 0);
131	if (errno != 0 || *p != '\0') {
132		if (errno == 0) {
133			while (*p != '\0' && is_space(*p))
134				p++;
135			if (*p == '\0')
136				return result;
137		}
138		arith_err("variable contains non-numeric value");
139	}
140	return result;
141}
142
143static inline int
144arith_prec(int op)
145{
146
147	return prec[op - ARITH_BINOP_MIN];
148}
149
150static inline int
151higher_prec(int op1, int op2)
152{
153
154	return arith_prec(op1) < arith_prec(op2);
155}
156
157static intmax_t
158do_binop(int op, intmax_t a, intmax_t b)
159{
160
161	VTRACE(DBG_ARITH, ("Arith do binop %d (%jd, %jd)\n", op, a, b));
162	switch (op) {
163	default:
164		arith_err("token error");
165	case ARITH_REM:
166	case ARITH_DIV:
167		if (b == 0)
168			arith_err("division by zero");
169		if (a == INTMAX_MIN && b == -1)
170			arith_err("divide error");
171		return op == ARITH_REM ? a % b : a / b;
172	case ARITH_MUL:
173		return (uintmax_t)a * (uintmax_t)b;
174	case ARITH_ADD:
175		return (uintmax_t)a + (uintmax_t)b;
176	case ARITH_SUB:
177		return (uintmax_t)a - (uintmax_t)b;
178	case ARITH_LSHIFT:
179		return (uintmax_t)a << (b & (sizeof(uintmax_t) * CHAR_BIT - 1));
180	case ARITH_RSHIFT:
181		return a >> (b & (sizeof(uintmax_t) * CHAR_BIT - 1));
182	case ARITH_LT:
183		return a < b;
184	case ARITH_LE:
185		return a <= b;
186	case ARITH_GT:
187		return a > b;
188	case ARITH_GE:
189		return a >= b;
190	case ARITH_EQ:
191		return a == b;
192	case ARITH_NE:
193		return a != b;
194	case ARITH_BAND:
195		return a & b;
196	case ARITH_BXOR:
197		return a ^ b;
198	case ARITH_BOR:
199		return a | b;
200	}
201}
202
203static intmax_t assignment(int, int);
204static intmax_t comma_list(int, int);
205
206static intmax_t
207primary(int token, union a_token_val *val, int op, int noeval)
208{
209	intmax_t result;
210	char sresult[DIGITS(result) + 1];
211
212	VTRACE(DBG_ARITH, ("Arith primary: token %d op %d%s\n",
213	    token, op, noeval ? " noeval" : ""));
214
215	switch (token) {
216	case ARITH_LPAREN:
217		result = comma_list(op, noeval);
218		if (last_token != ARITH_RPAREN)
219			arith_err("expecting ')'");
220		last_token = arith_token();
221		return result;
222	case ARITH_NUM:
223		last_token = op;
224		return val->val;
225	case ARITH_VAR:
226		result = noeval ? val->val : arith_lookupvarint(val->name);
227		if (op == ARITH_INCR || op == ARITH_DECR) {
228			last_token = arith_token();
229			if (noeval)
230				return val->val;
231
232			snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR,
233			    result + (op == ARITH_INCR ? 1 : -1));
234			setvar(val->name, sresult, 0);
235		} else
236			last_token = op;
237		return result;
238	case ARITH_ADD:
239		*val = a_t_val;
240		return primary(op, val, arith_token(), noeval);
241	case ARITH_SUB:
242		*val = a_t_val;
243		return -primary(op, val, arith_token(), noeval);
244	case ARITH_NOT:
245		*val = a_t_val;
246		return !primary(op, val, arith_token(), noeval);
247	case ARITH_BNOT:
248		*val = a_t_val;
249		return ~primary(op, val, arith_token(), noeval);
250	case ARITH_INCR:
251	case ARITH_DECR:
252		if (op != ARITH_VAR)
253			arith_err("incr/decr require var name");
254		last_token = arith_token();
255		if (noeval)
256			return val->val;
257		result = arith_lookupvarint(a_t_val.name);
258		snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR,
259			    result += (token == ARITH_INCR ? 1 : -1));
260		setvar(a_t_val.name, sresult, 0);
261		return result;
262	default:
263		arith_err("expecting primary");
264	}
265	return 0;	/* never reached */
266}
267
268static intmax_t
269binop2(intmax_t a, int op, int precedence, int noeval)
270{
271	union a_token_val val;
272	intmax_t b;
273	int op2;
274	int token;
275
276	VTRACE(DBG_ARITH, ("Arith: binop2 %jd op %d (P:%d)%s\n",
277	    a, op, precedence, noeval ? " noeval" : ""));
278
279	for (;;) {
280		token = arith_token();
281		val = a_t_val;
282
283		b = primary(token, &val, arith_token(), noeval);
284
285		op2 = last_token;
286		if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX &&
287		    higher_prec(op2, op)) {
288			b = binop2(b, op2, arith_prec(op), noeval);
289			op2 = last_token;
290		}
291
292		a = noeval ? b : do_binop(op, a, b);
293
294		if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX ||
295		    arith_prec(op2) >= precedence)
296			return a;
297
298		op = op2;
299	}
300}
301
302static intmax_t
303binop(int token, union a_token_val *val, int op, int noeval)
304{
305	intmax_t a = primary(token, val, op, noeval);
306
307	op = last_token;
308	if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX)
309		return a;
310
311	return binop2(a, op, ARITH_MAX_PREC, noeval);
312}
313
314static intmax_t
315and(int token, union a_token_val *val, int op, int noeval)
316{
317	intmax_t a = binop(token, val, op, noeval);
318	intmax_t b;
319
320	op = last_token;
321	if (op != ARITH_AND)
322		return a;
323
324	VTRACE(DBG_ARITH, ("Arith: AND %jd%s\n", a, noeval ? " noeval" : ""));
325
326	token = arith_token();
327	*val = a_t_val;
328
329	b = and(token, val, arith_token(), noeval | !a);
330
331	return a && b;
332}
333
334static intmax_t
335or(int token, union a_token_val *val, int op, int noeval)
336{
337	intmax_t a = and(token, val, op, noeval);
338	intmax_t b;
339
340	op = last_token;
341	if (op != ARITH_OR)
342		return a;
343
344	VTRACE(DBG_ARITH, ("Arith: OR %jd%s\n", a, noeval ? " noeval" : ""));
345
346	token = arith_token();
347	*val = a_t_val;
348
349	b = or(token, val, arith_token(), noeval | !!a);
350
351	return a || b;
352}
353
354static intmax_t
355cond(int token, union a_token_val *val, int op, int noeval)
356{
357	intmax_t a = or(token, val, op, noeval);
358	intmax_t b;
359	intmax_t c;
360
361	if (last_token != ARITH_QMARK)
362		return a;
363
364	VTRACE(DBG_ARITH, ("Arith: ?: %jd%s\n", a, noeval ? " noeval" : ""));
365
366	b = assignment(arith_token(), noeval | !a);
367
368	if (last_token != ARITH_COLON)
369		arith_err("expecting ':'");
370
371	token = arith_token();
372	*val = a_t_val;
373
374	c = cond(token, val, arith_token(), noeval | !!a);
375
376	return a ? b : c;
377}
378
379static intmax_t
380assignment(int var, int noeval)
381{
382	union a_token_val val = a_t_val;
383	int op = arith_token();
384	intmax_t result;
385	char sresult[DIGITS(result) + 1];
386
387
388	if (var != ARITH_VAR)
389		return cond(var, &val, op, noeval);
390
391	if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX))
392		return cond(var, &val, op, noeval);
393
394	VTRACE(DBG_ARITH, ("Arith: %s ASSIGN %d%s\n", val.name, op,
395	    noeval ? " noeval" : ""));
396
397	result = assignment(arith_token(), noeval);
398	if (noeval)
399		return result;
400
401	if (op != ARITH_ASS)
402		result = do_binop(op - ARITH_ASS_GAP,
403		    arith_lookupvarint(val.name), result);
404	snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result);
405	setvar(val.name, sresult, 0);
406	return result;
407}
408
409static intmax_t
410comma_list(int token, int noeval)
411{
412	intmax_t result = assignment(token, noeval);
413
414	while (last_token == ARITH_COMMA) {
415		VTRACE(DBG_ARITH, ("Arith: comma discarding %jd%s\n", result,
416		    noeval ? " noeval" : ""));
417		result = assignment(arith_token(), noeval);
418	}
419
420	return result;
421}
422
423intmax_t
424arith(const char *s, int lno)
425{
426	struct stackmark smark;
427	intmax_t result;
428	const char *p;
429	int nls = 0;
430
431	setstackmark(&smark);
432
433	arith_lno = lno;
434
435	CTRACE(DBG_ARITH, ("Arith(\"%s\", %d) @%d\n", s, lno, arith_lno));
436
437	/* check if it is possible we might reference LINENO */
438	p = s;
439	while ((p = strchr(p, 'L')) != NULL) {
440		if (p[1] == 'I' && p[2] == 'N') {
441			/* if it is possible, we need to correct airth_lno */
442			p = s;
443			while ((p = strchr(p, '\n')) != NULL)
444				nls++, p++;
445			VTRACE(DBG_ARITH, ("Arith found %d newlines\n", nls));
446			arith_lno -= nls;
447			break;
448		}
449		p++;
450	}
451
452	arith_buf = arith_startbuf = s;
453
454	result = comma_list(arith_token(), 0);
455
456	if (last_token)
457		arith_err("expecting end of expression");
458
459	popstackmark(&smark);
460
461	CTRACE(DBG_ARITH, ("Arith result=%jd\n", result));
462
463	return result;
464}
465
466/*
467 *  The let(1)/exp(1) builtin.
468 */
469int
470expcmd(int argc, char **argv)
471{
472	const char *p;
473	char *concat;
474	char **ap;
475	intmax_t i;
476
477	if (argc > 1) {
478		p = argv[1];
479		if (argc > 2) {
480			/*
481			 * Concatenate arguments.
482			 */
483			STARTSTACKSTR(concat);
484			ap = argv + 2;
485			for (;;) {
486				while (*p)
487					STPUTC(*p++, concat);
488				if ((p = *ap++) == NULL)
489					break;
490				STPUTC(' ', concat);
491			}
492			STPUTC('\0', concat);
493			p = grabstackstr(concat);
494		}
495	} else
496		p = "";
497
498	i = arith(p, line_number);
499
500	out1fmt(ARITH_FORMAT_STR "\n", i);
501	return !i;
502}
503