1/* vi: set sw=4 ts=4: */
2/*
3 * Mini expr implementation for busybox
4 *
5 * based on GNU expr Mike Parker.
6 * Copyright (C) 86, 1991-1997, 1999 Free Software Foundation, Inc.
7 *
8 * Busybox modifications
9 * Copyright (c) 2000  Edward Betts <edward@debian.org>.
10 * Copyright (C) 2003-2005  Vladimir Oleynik <dzo@simtreas.ru>
11 *  - reduced 464 bytes.
12 *  - 64 math support
13 *
14 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
15 */
16
17/* This program evaluates expressions.  Each token (operator, operand,
18 * parenthesis) of the expression must be a separate argument.  The
19 * parser used is a reasonably general one, though any incarnation of
20 * it is language-specific.  It is especially nice for expressions.
21 *
22 * No parse tree is needed; a new node is evaluated immediately.
23 * One function can handle multiple operators all of equal precedence,
24 * provided they all associate ((x op x) op x). */
25
26/* no getopt needed */
27
28#include "libbb.h"
29#include "xregex.h"
30
31#if ENABLE_EXPR_MATH_SUPPORT_64
32typedef int64_t arith_t;
33
34#define PF_REZ      "ll"
35#define PF_REZ_TYPE (long long)
36#define STRTOL(s, e, b) strtoll(s, e, b)
37#else
38typedef long arith_t;
39
40#define PF_REZ      "l"
41#define PF_REZ_TYPE (long)
42#define STRTOL(s, e, b) strtol(s, e, b)
43#endif
44
45/* TODO: use bb_strtol[l]? It's easier to check for errors... */
46
47/* The kinds of value we can have.  */
48enum {
49	INTEGER,
50	STRING
51};
52
53/* A value is.... */
54struct valinfo {
55	smallint type;                  /* Which kind. */
56	union {                         /* The value itself. */
57		arith_t i;
58		char *s;
59	} u;
60};
61typedef struct valinfo VALUE;
62
63/* The arguments given to the program, minus the program name.  */
64struct globals {
65	char **args;
66} FIX_ALIASING;
67#define G (*(struct globals*)&bb_common_bufsiz1)
68
69/* forward declarations */
70static VALUE *eval(void);
71
72
73/* Return a VALUE for I.  */
74
75static VALUE *int_value(arith_t i)
76{
77	VALUE *v;
78
79	v = xzalloc(sizeof(VALUE));
80	if (INTEGER) /* otherwise xzaaloc did it already */
81		v->type = INTEGER;
82	v->u.i = i;
83	return v;
84}
85
86/* Return a VALUE for S.  */
87
88static VALUE *str_value(const char *s)
89{
90	VALUE *v;
91
92	v = xzalloc(sizeof(VALUE));
93	if (STRING) /* otherwise xzaaloc did it already */
94		v->type = STRING;
95	v->u.s = xstrdup(s);
96	return v;
97}
98
99/* Free VALUE V, including structure components.  */
100
101static void freev(VALUE *v)
102{
103	if (v->type == STRING)
104		free(v->u.s);
105	free(v);
106}
107
108/* Return nonzero if V is a null-string or zero-number.  */
109
110static int null(VALUE *v)
111{
112	if (v->type == INTEGER)
113		return v->u.i == 0;
114	/* STRING: */
115	return v->u.s[0] == '\0' || LONE_CHAR(v->u.s, '0');
116}
117
118/* Coerce V to a STRING value (can't fail).  */
119
120static void tostring(VALUE *v)
121{
122	if (v->type == INTEGER) {
123		v->u.s = xasprintf("%" PF_REZ "d", PF_REZ_TYPE v->u.i);
124		v->type = STRING;
125	}
126}
127
128/* Coerce V to an INTEGER value.  Return 1 on success, 0 on failure.  */
129
130static bool toarith(VALUE *v)
131{
132	if (v->type == STRING) {
133		arith_t i;
134		char *e;
135
136		/* Don't interpret the empty string as an integer.  */
137		/* Currently does not worry about overflow or int/long differences. */
138		i = STRTOL(v->u.s, &e, 10);
139		if ((v->u.s == e) || *e)
140			return 0;
141		free(v->u.s);
142		v->u.i = i;
143		v->type = INTEGER;
144	}
145	return 1;
146}
147
148/* Return str[0]+str[1] if the next token matches STR exactly.
149   STR must not be NULL.  */
150
151static int nextarg(const char *str)
152{
153	if (*G.args == NULL || strcmp(*G.args, str) != 0)
154		return 0;
155	return (unsigned char)str[0] + (unsigned char)str[1];
156}
157
158/* The comparison operator handling functions.  */
159
160static int cmp_common(VALUE *l, VALUE *r, int op)
161{
162	arith_t ll, rr;
163
164	ll = l->u.i;
165	rr = r->u.i;
166	if (l->type == STRING || r->type == STRING) {
167		tostring(l);
168		tostring(r);
169		ll = strcmp(l->u.s, r->u.s);
170		rr = 0;
171	}
172	/* calculating ll - rr and checking the result is prone to overflows.
173	 * We'll do it differently: */
174	if (op == '<')
175		return ll < rr;
176	if (op == ('<' + '='))
177		return ll <= rr;
178	if (op == '=' || (op == '=' + '='))
179		return ll == rr;
180	if (op == '!' + '=')
181		return ll != rr;
182	if (op == '>')
183		return ll > rr;
184	/* >= */
185	return ll >= rr;
186}
187
188/* The arithmetic operator handling functions.  */
189
190static arith_t arithmetic_common(VALUE *l, VALUE *r, int op)
191{
192	arith_t li, ri;
193
194	if (!toarith(l) || !toarith(r))
195		bb_error_msg_and_die("non-numeric argument");
196	li = l->u.i;
197	ri = r->u.i;
198	if (op == '+')
199		return li + ri;
200	if (op == '-')
201		return li - ri;
202	if (op == '*')
203		return li * ri;
204	if (ri == 0)
205		bb_error_msg_and_die("division by zero");
206	if (op == '/')
207		return li / ri;
208	return li % ri;
209}
210
211/* Do the : operator.
212   SV is the VALUE for the lhs (the string),
213   PV is the VALUE for the rhs (the pattern).  */
214
215static VALUE *docolon(VALUE *sv, VALUE *pv)
216{
217	enum { NMATCH = 2 };
218	VALUE *v;
219	regex_t re_buffer;
220	regmatch_t re_regs[NMATCH];
221
222	tostring(sv);
223	tostring(pv);
224
225	if (pv->u.s[0] == '^') {
226		bb_error_msg(
227"warning: '%s': using '^' as the first character\n"
228"of a basic regular expression is not portable; it is ignored", pv->u.s);
229	}
230
231	memset(&re_buffer, 0, sizeof(re_buffer));
232	memset(re_regs, 0, sizeof(re_regs));
233	xregcomp(&re_buffer, pv->u.s, 0);
234
235	/* expr uses an anchored pattern match, so check that there was a
236	 * match and that the match starts at offset 0. */
237	if (regexec(&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH
238	 && re_regs[0].rm_so == 0
239	) {
240		/* Were \(...\) used? */
241		if (re_buffer.re_nsub > 0 && re_regs[1].rm_so >= 0) {
242			sv->u.s[re_regs[1].rm_eo] = '\0';
243			v = str_value(sv->u.s + re_regs[1].rm_so);
244		} else {
245			v = int_value(re_regs[0].rm_eo);
246		}
247	} else {
248		/* Match failed -- return the right kind of null.  */
249		if (re_buffer.re_nsub > 0)
250			v = str_value("");
251		else
252			v = int_value(0);
253	}
254	regfree(&re_buffer);
255	return v;
256}
257
258/* Handle bare operands and ( expr ) syntax.  */
259
260static VALUE *eval7(void)
261{
262	VALUE *v;
263
264	if (!*G.args)
265		bb_error_msg_and_die("syntax error");
266
267	if (nextarg("(")) {
268		G.args++;
269		v = eval();
270		if (!nextarg(")"))
271			bb_error_msg_and_die("syntax error");
272		G.args++;
273		return v;
274	}
275
276	if (nextarg(")"))
277		bb_error_msg_and_die("syntax error");
278
279	return str_value(*G.args++);
280}
281
282/* Handle match, substr, index, length, and quote keywords.  */
283
284static VALUE *eval6(void)
285{
286	static const char keywords[] ALIGN1 =
287		"quote\0""length\0""match\0""index\0""substr\0";
288
289	VALUE *r, *i1, *i2;
290	VALUE *l = l; /* silence gcc */
291	VALUE *v = v; /* silence gcc */
292	int key = *G.args ? index_in_strings(keywords, *G.args) + 1 : 0;
293
294	if (key == 0) /* not a keyword */
295		return eval7();
296	G.args++; /* We have a valid token, so get the next argument.  */
297	if (key == 1) { /* quote */
298		if (!*G.args)
299			bb_error_msg_and_die("syntax error");
300		return str_value(*G.args++);
301	}
302	if (key == 2) { /* length */
303		r = eval6();
304		tostring(r);
305		v = int_value(strlen(r->u.s));
306		freev(r);
307	} else
308		l = eval6();
309
310	if (key == 3) { /* match */
311		r = eval6();
312		v = docolon(l, r);
313		freev(l);
314		freev(r);
315	}
316	if (key == 4) { /* index */
317		r = eval6();
318		tostring(l);
319		tostring(r);
320		v = int_value(strcspn(l->u.s, r->u.s) + 1);
321		if (v->u.i == (arith_t) strlen(l->u.s) + 1)
322			v->u.i = 0;
323		freev(l);
324		freev(r);
325	}
326	if (key == 5) { /* substr */
327		i1 = eval6();
328		i2 = eval6();
329		tostring(l);
330		if (!toarith(i1) || !toarith(i2)
331		 || i1->u.i > (arith_t) strlen(l->u.s)
332		 || i1->u.i <= 0 || i2->u.i <= 0)
333			v = str_value("");
334		else {
335			v = xmalloc(sizeof(VALUE));
336			v->type = STRING;
337			v->u.s = xstrndup(l->u.s + i1->u.i - 1, i2->u.i);
338		}
339		freev(l);
340		freev(i1);
341		freev(i2);
342	}
343	return v;
344
345}
346
347/* Handle : operator (pattern matching).
348   Calls docolon to do the real work.  */
349
350static VALUE *eval5(void)
351{
352	VALUE *l, *r, *v;
353
354	l = eval6();
355	while (nextarg(":")) {
356		G.args++;
357		r = eval6();
358		v = docolon(l, r);
359		freev(l);
360		freev(r);
361		l = v;
362	}
363	return l;
364}
365
366/* Handle *, /, % operators.  */
367
368static VALUE *eval4(void)
369{
370	VALUE *l, *r;
371	int op;
372	arith_t val;
373
374	l = eval5();
375	while (1) {
376		op = nextarg("*");
377		if (!op) { op = nextarg("/");
378		 if (!op) { op = nextarg("%");
379		  if (!op) return l;
380		}}
381		G.args++;
382		r = eval5();
383		val = arithmetic_common(l, r, op);
384		freev(l);
385		freev(r);
386		l = int_value(val);
387	}
388}
389
390/* Handle +, - operators.  */
391
392static VALUE *eval3(void)
393{
394	VALUE *l, *r;
395	int op;
396	arith_t val;
397
398	l = eval4();
399	while (1) {
400		op = nextarg("+");
401		if (!op) {
402			op = nextarg("-");
403			if (!op) return l;
404		}
405		G.args++;
406		r = eval4();
407		val = arithmetic_common(l, r, op);
408		freev(l);
409		freev(r);
410		l = int_value(val);
411	}
412}
413
414/* Handle comparisons.  */
415
416static VALUE *eval2(void)
417{
418	VALUE *l, *r;
419	int op;
420	arith_t val;
421
422	l = eval3();
423	while (1) {
424		op = nextarg("<");
425		if (!op) { op = nextarg("<=");
426		 if (!op) { op = nextarg("=");
427		  if (!op) { op = nextarg("==");
428		   if (!op) { op = nextarg("!=");
429		    if (!op) { op = nextarg(">=");
430		     if (!op) { op = nextarg(">");
431		      if (!op) return l;
432		}}}}}}
433		G.args++;
434		r = eval3();
435		toarith(l);
436		toarith(r);
437		val = cmp_common(l, r, op);
438		freev(l);
439		freev(r);
440		l = int_value(val);
441	}
442}
443
444/* Handle &.  */
445
446static VALUE *eval1(void)
447{
448	VALUE *l, *r;
449
450	l = eval2();
451	while (nextarg("&")) {
452		G.args++;
453		r = eval2();
454		if (null(l) || null(r)) {
455			freev(l);
456			freev(r);
457			l = int_value(0);
458		} else
459			freev(r);
460	}
461	return l;
462}
463
464/* Handle |.  */
465
466static VALUE *eval(void)
467{
468	VALUE *l, *r;
469
470	l = eval1();
471	while (nextarg("|")) {
472		G.args++;
473		r = eval1();
474		if (null(l)) {
475			freev(l);
476			l = r;
477		} else
478			freev(r);
479	}
480	return l;
481}
482
483int expr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
484int expr_main(int argc UNUSED_PARAM, char **argv)
485{
486	VALUE *v;
487
488	xfunc_error_retval = 2; /* coreutils compat */
489	G.args = argv + 1;
490	if (*G.args == NULL) {
491		bb_error_msg_and_die("too few arguments");
492	}
493	v = eval();
494	if (*G.args)
495		bb_error_msg_and_die("syntax error");
496	if (v->type == INTEGER)
497		printf("%" PF_REZ "d\n", PF_REZ_TYPE v->u.i);
498	else
499		puts(v->u.s);
500	fflush_stdout_and_exit(null(v));
501}
502