1%{
2/*-
3 * Written by Pace Willisson (pace@blitz.com)
4 * and placed in the public domain.
5 *
6 * Largely rewritten by J.T. Conklin (jtc@wimsey.com)
7 *
8 * $FreeBSD$
9 */
10
11#include <sys/types.h>
12
13#include <ctype.h>
14#include <err.h>
15#include <errno.h>
16#include <inttypes.h>
17#include <limits.h>
18#include <locale.h>
19#include <stdio.h>
20#include <stdlib.h>
21#include <string.h>
22#include <regex.h>
23#include <unistd.h>
24
25/*
26 * POSIX specifies a specific error code for syntax errors.  We exit
27 * with this code for all errors.
28 */
29#define	ERR_EXIT	2
30
31enum valtype {
32	integer, numeric_string, string
33} ;
34
35struct val {
36	enum valtype type;
37	union {
38		char *s;
39		intmax_t i;
40	} u;
41} ;
42
43char		**av;
44int		nonposix;
45struct val	*result;
46
47void		assert_to_integer(struct val *);
48void		assert_div(intmax_t, intmax_t);
49void		assert_minus(intmax_t, intmax_t, intmax_t);
50void		assert_plus(intmax_t, intmax_t, intmax_t);
51void		assert_times(intmax_t, intmax_t, intmax_t);
52int		compare_vals(struct val *, struct val *);
53void		free_value(struct val *);
54int		is_integer(const char *);
55int		is_string(struct val *);
56int		is_zero_or_null(struct val *);
57struct val	*make_integer(intmax_t);
58struct val	*make_str(const char *);
59struct val	*op_and(struct val *, struct val *);
60struct val	*op_colon(struct val *, struct val *);
61struct val	*op_div(struct val *, struct val *);
62struct val	*op_eq(struct val *, struct val *);
63struct val	*op_ge(struct val *, struct val *);
64struct val	*op_gt(struct val *, struct val *);
65struct val	*op_le(struct val *, struct val *);
66struct val	*op_lt(struct val *, struct val *);
67struct val	*op_minus(struct val *, struct val *);
68struct val	*op_ne(struct val *, struct val *);
69struct val	*op_or(struct val *, struct val *);
70struct val	*op_plus(struct val *, struct val *);
71struct val	*op_rem(struct val *, struct val *);
72struct val	*op_times(struct val *, struct val *);
73int		to_integer(struct val *);
74void		to_string(struct val *);
75int		yyerror(const char *);
76int		yylex(void);
77
78%}
79
80%union
81{
82	struct val *val;
83}
84
85%left <val> '|'
86%left <val> '&'
87%left <val> '=' '>' '<' GE LE NE
88%left <val> '+' '-'
89%left <val> '*' '/' '%'
90%left <val> ':'
91
92%token <val> TOKEN
93%type <val> start expr
94
95%%
96
97start: expr { result = $$; }
98
99expr:	TOKEN
100	| '(' expr ')' { $$ = $2; }
101	| expr '|' expr { $$ = op_or($1, $3); }
102	| expr '&' expr { $$ = op_and($1, $3); }
103	| expr '=' expr { $$ = op_eq($1, $3); }
104	| expr '>' expr { $$ = op_gt($1, $3); }
105	| expr '<' expr { $$ = op_lt($1, $3); }
106	| expr GE expr  { $$ = op_ge($1, $3); }
107	| expr LE expr  { $$ = op_le($1, $3); }
108	| expr NE expr  { $$ = op_ne($1, $3); }
109	| expr '+' expr { $$ = op_plus($1, $3); }
110	| expr '-' expr { $$ = op_minus($1, $3); }
111	| expr '*' expr { $$ = op_times($1, $3); }
112	| expr '/' expr { $$ = op_div($1, $3); }
113	| expr '%' expr { $$ = op_rem($1, $3); }
114	| expr ':' expr { $$ = op_colon($1, $3); }
115	;
116
117%%
118
119struct val *
120make_integer(intmax_t i)
121{
122	struct val *vp;
123
124	vp = (struct val *)malloc(sizeof(*vp));
125	if (vp == NULL)
126		errx(ERR_EXIT, "malloc() failed");
127
128	vp->type = integer;
129	vp->u.i  = i;
130	return (vp);
131}
132
133struct val *
134make_str(const char *s)
135{
136	struct val *vp;
137
138	vp = (struct val *)malloc(sizeof(*vp));
139	if (vp == NULL || ((vp->u.s = strdup(s)) == NULL))
140		errx(ERR_EXIT, "malloc() failed");
141
142	if (is_integer(s))
143		vp->type = numeric_string;
144	else
145		vp->type = string;
146
147	return (vp);
148}
149
150void
151free_value(struct val *vp)
152{
153	if (vp->type == string || vp->type == numeric_string)
154		free(vp->u.s);
155}
156
157int
158to_integer(struct val *vp)
159{
160	intmax_t i;
161
162	/* we can only convert numeric_string to integer, here */
163	if (vp->type == numeric_string) {
164		errno = 0;
165		i  = strtoimax(vp->u.s, (char **)NULL, 10);
166		/* just keep as numeric_string, if the conversion fails */
167		if (errno != ERANGE) {
168			free(vp->u.s);
169			vp->u.i = i;
170			vp->type = integer;
171		}
172	}
173	return (vp->type == integer);
174}
175
176void
177assert_to_integer(struct val *vp)
178{
179	if (vp->type == string)
180		errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s);
181	if (!to_integer(vp))
182		errx(ERR_EXIT, "operand too large: '%s'", vp->u.s);
183}
184
185void
186to_string(struct val *vp)
187{
188	char *tmp;
189
190	if (vp->type == string || vp->type == numeric_string)
191		return;
192
193	/*
194	 * log_10(x) ~= 0.3 * log_2(x).  Rounding up gives the number
195	 * of digits; add one each for the sign and terminating null
196	 * character, respectively.
197	 */
198#define	NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1)
199	tmp = malloc(NDIGITS(vp->u.i));
200	if (tmp == NULL)
201		errx(ERR_EXIT, "malloc() failed");
202
203	sprintf(tmp, "%jd", vp->u.i);
204	vp->type = string;
205	vp->u.s  = tmp;
206}
207
208int
209is_integer(const char *s)
210{
211	if (nonposix) {
212		if (*s == '\0')
213			return (1);
214		while (isspace((unsigned char)*s))
215			s++;
216	}
217	if (*s == '-' || (nonposix && *s == '+'))
218		s++;
219	if (*s == '\0')
220		return (0);
221	while (isdigit((unsigned char)*s))
222		s++;
223	return (*s == '\0');
224}
225
226int
227is_string(struct val *vp)
228{
229	/* only TRUE if this string is not a valid integer */
230	return (vp->type == string);
231}
232
233int
234yylex(void)
235{
236	char *p;
237
238	if (*av == NULL)
239		return (0);
240
241	p = *av++;
242
243	if (strlen(p) == 1) {
244		if (strchr("|&=<>+-*/%:()", *p))
245			return (*p);
246	} else if (strlen(p) == 2 && p[1] == '=') {
247		switch (*p) {
248		case '>': return (GE);
249		case '<': return (LE);
250		case '!': return (NE);
251		}
252	}
253
254	yylval.val = make_str(p);
255	return (TOKEN);
256}
257
258int
259is_zero_or_null(struct val *vp)
260{
261	if (vp->type == integer)
262		return (vp->u.i == 0);
263
264	return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0));
265}
266
267int
268main(int argc, char *argv[])
269{
270	int c;
271
272	setlocale(LC_ALL, "");
273	if (getenv("EXPR_COMPAT") != NULL
274	    || check_utility_compat("expr")) {
275		av = argv + 1;
276		nonposix = 1;
277	} else {
278		while ((c = getopt(argc, argv, "e")) != -1) {
279			switch (c) {
280			case 'e':
281				nonposix = 1;
282				break;
283			default:
284				errx(ERR_EXIT,
285				    "usage: expr [-e] expression\n");
286			}
287		}
288		av = argv + optind;
289	}
290
291	yyparse();
292
293	if (result->type == integer)
294		printf("%jd\n", result->u.i);
295	else
296		printf("%s\n", result->u.s);
297
298	return (is_zero_or_null(result));
299}
300
301int
302yyerror(const char *s __unused)
303{
304	errx(ERR_EXIT, "syntax error");
305}
306
307struct val *
308op_or(struct val *a, struct val *b)
309{
310	if (!is_zero_or_null(a)) {
311		free_value(b);
312		return (a);
313	}
314	free_value(a);
315	if (!is_zero_or_null(b))
316		return (b);
317	free_value(b);
318	return (make_integer((intmax_t)0));
319}
320
321struct val *
322op_and(struct val *a, struct val *b)
323{
324	if (is_zero_or_null(a) || is_zero_or_null(b)) {
325		free_value(a);
326		free_value(b);
327		return (make_integer((intmax_t)0));
328	} else {
329		free_value(b);
330		return (a);
331	}
332}
333
334int
335compare_vals(struct val *a, struct val *b)
336{
337	int r;
338
339	if (is_string(a) || is_string(b)) {
340		to_string(a);
341		to_string(b);
342		r = strcoll(a->u.s, b->u.s);
343	} else {
344		assert_to_integer(a);
345		assert_to_integer(b);
346		if (a->u.i > b->u.i)
347			r = 1;
348		else if (a->u.i < b->u.i)
349			r = -1;
350		else
351			r = 0;
352	}
353
354	free_value(a);
355	free_value(b);
356	return (r);
357}
358
359struct val *
360op_eq(struct val *a, struct val *b)
361{
362	return (make_integer((intmax_t)(compare_vals(a, b) == 0)));
363}
364
365struct val *
366op_gt(struct val *a, struct val *b)
367{
368	return (make_integer((intmax_t)(compare_vals(a, b) > 0)));
369}
370
371struct val *
372op_lt(struct val *a, struct val *b)
373{
374	return (make_integer((intmax_t)(compare_vals(a, b) < 0)));
375}
376
377struct val *
378op_ge(struct val *a, struct val *b)
379{
380	return (make_integer((intmax_t)(compare_vals(a, b) >= 0)));
381}
382
383struct val *
384op_le(struct val *a, struct val *b)
385{
386	return (make_integer((intmax_t)(compare_vals(a, b) <= 0)));
387}
388
389struct val *
390op_ne(struct val *a, struct val *b)
391{
392	return (make_integer((intmax_t)(compare_vals(a, b) != 0)));
393}
394
395void
396assert_plus(intmax_t a, intmax_t b, intmax_t r)
397{
398	/*
399	 * sum of two positive numbers must be positive,
400	 * sum of two negative numbers must be negative
401	 */
402	if ((a > 0 && b > 0 && r <= 0) ||
403	    (a < 0 && b < 0 && r >= 0))
404		errx(ERR_EXIT, "overflow");
405}
406
407struct val *
408op_plus(struct val *a, struct val *b)
409{
410	struct val *r;
411
412	assert_to_integer(a);
413	assert_to_integer(b);
414	r = make_integer(a->u.i + b->u.i);
415	assert_plus(a->u.i, b->u.i, r->u.i);
416
417	free_value(a);
418	free_value(b);
419	return (r);
420}
421
422void
423assert_minus(intmax_t a, intmax_t b, intmax_t r)
424{
425	/* special case subtraction of INTMAX_MIN */
426	if (b == INTMAX_MIN && a < 0)
427		errx(ERR_EXIT, "overflow");
428	/* check addition of negative subtrahend */
429	assert_plus(a, -b, r);
430}
431
432struct val *
433op_minus(struct val *a, struct val *b)
434{
435	struct val *r;
436
437	assert_to_integer(a);
438	assert_to_integer(b);
439	r = make_integer(a->u.i - b->u.i);
440	assert_minus(a->u.i, b->u.i, r->u.i);
441
442	free_value(a);
443	free_value(b);
444	return (r);
445}
446
447void
448assert_times(intmax_t a, intmax_t b, intmax_t r)
449{
450	/*
451	 * if first operand is 0, no overflow is possible,
452	 * else result of division test must match second operand
453	 */
454	if (a != 0 && r / a != b)
455		errx(ERR_EXIT, "overflow");
456}
457
458struct val *
459op_times(struct val *a, struct val *b)
460{
461	struct val *r;
462
463	assert_to_integer(a);
464	assert_to_integer(b);
465	r = make_integer(a->u.i * b->u.i);
466	assert_times(a->u.i, b->u.i, r->u.i);
467
468	free_value(a);
469	free_value(b);
470	return (r);
471}
472
473void
474assert_div(intmax_t a, intmax_t b)
475{
476	if (b == 0)
477		errx(ERR_EXIT, "division by zero");
478	/* only INTMAX_MIN / -1 causes overflow */
479	if (a == INTMAX_MIN && b == -1)
480		errx(ERR_EXIT, "overflow");
481}
482
483struct val *
484op_div(struct val *a, struct val *b)
485{
486	struct val *r;
487
488	assert_to_integer(a);
489	assert_to_integer(b);
490	/* assert based on operands only, not on result */
491	assert_div(a->u.i, b->u.i);
492	r = make_integer(a->u.i / b->u.i);
493
494	free_value(a);
495	free_value(b);
496	return (r);
497}
498
499struct val *
500op_rem(struct val *a, struct val *b)
501{
502	struct val *r;
503
504	assert_to_integer(a);
505	assert_to_integer(b);
506	/* pass a=1 to only check for div by zero */
507	assert_div(1, b->u.i);
508	r = make_integer(a->u.i % b->u.i);
509
510	free_value(a);
511	free_value(b);
512	return (r);
513}
514
515struct val *
516op_colon(struct val *a, struct val *b)
517{
518	regex_t rp;
519	regmatch_t rm[2];
520	char errbuf[256];
521	int eval;
522	struct val *v;
523
524	/* coerce both arguments to strings */
525	to_string(a);
526	to_string(b);
527
528	/* compile regular expression */
529	if ((eval = regcomp(&rp, b->u.s, 0)) != 0) {
530		regerror(eval, &rp, errbuf, sizeof(errbuf));
531		errx(ERR_EXIT, "%s", errbuf);
532	}
533
534	/* compare string against pattern */
535	/* remember that patterns are anchored to the beginning of the line */
536	if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0)
537		if (rm[1].rm_so >= 0) {
538			*(a->u.s + rm[1].rm_eo) = '\0';
539			v = make_str(a->u.s + rm[1].rm_so);
540
541		} else
542			v = make_integer((intmax_t)(rm[0].rm_eo));
543	else
544		if (rp.re_nsub == 0)
545			v = make_integer((intmax_t)0);
546		else
547			v = make_str("");
548
549	/* free arguments and pattern buffer */
550	free_value(a);
551	free_value(b);
552	regfree(&rp);
553
554	return (v);
555}
556