expr.y revision 223881 
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: head/bin/expr/expr.y 223881 2011-07-09 12:05:53Z se $
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
43struct val *result;
44
45void		assert_to_integer(struct val *);
46int		chk_div(intmax_t, intmax_t);
47int		chk_minus(intmax_t, intmax_t, intmax_t);
48int		chk_plus(intmax_t, intmax_t, intmax_t);
49int		chk_times(intmax_t, intmax_t, intmax_t);
50void		free_value(struct val *);
51int		is_integer(const char *);
52int		isstring(struct val *);
53int		is_zero_or_null(struct val *);
54struct val	*make_integer(intmax_t);
55struct val	*make_str(const char *);
56struct val	*op_and(struct val *, struct val *);
57struct val	*op_colon(struct val *, struct val *);
58struct val	*op_div(struct val *, struct val *);
59struct val	*op_eq(struct val *, struct val *);
60struct val	*op_ge(struct val *, struct val *);
61struct val	*op_gt(struct val *, struct val *);
62struct val	*op_le(struct val *, struct val *);
63struct val	*op_lt(struct val *, struct val *);
64struct val	*op_minus(struct val *, struct val *);
65struct val	*op_ne(struct val *, struct val *);
66struct val	*op_or(struct val *, struct val *);
67struct val	*op_plus(struct val *, struct val *);
68struct val	*op_rem(struct val *, struct val *);
69struct val	*op_times(struct val *, struct val *);
70int		to_integer(struct val *);
71void		to_string(struct val *);
72int		yyerror(const char *);
73int		yylex(void);
74int		yyparse(void);
75
76static int	nonposix;
77char **av;
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%%
119
120struct val *
121make_integer(intmax_t i)
122{
123	struct val *vp;
124
125	vp = (struct val *) malloc (sizeof (*vp));
126	if (vp == NULL) {
127		errx(ERR_EXIT, "malloc() failed");
128	}
129
130	vp->type = integer;
131	vp->u.i  = i;
132	return vp;
133}
134
135struct val *
136make_str(const char *s)
137{
138	struct val *vp;
139
140	vp = (struct val *) malloc (sizeof (*vp));
141	if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) {
142		errx(ERR_EXIT, "malloc() failed");
143	}
144
145	if (is_integer(s))
146		vp->type = numeric_string;
147	else
148		vp->type = string;
149
150	return vp;
151}
152
153
154void
155free_value(struct val *vp)
156{
157	if (vp->type == string || vp->type == numeric_string)
158		free (vp->u.s);
159}
160
161
162int
163to_integer(struct val *vp)
164{
165	intmax_t i;
166
167	/* we can only convert numeric_string to integer, here */
168	if (vp->type == numeric_string) {
169		errno = 0;
170		i  = strtoimax(vp->u.s, (char **)NULL, 10);
171		/* just keep as numeric_string, if the conversion fails */
172		if (errno != ERANGE) {
173			free (vp->u.s);
174			vp->u.i = i;
175			vp->type = integer;
176		}
177	}
178	return (vp->type == integer);
179}
180
181
182void
183assert_to_integer(struct val *vp)
184{
185	if (vp->type == string)
186		errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s);
187	if (!to_integer(vp))
188		errx(ERR_EXIT, "operand too large: '%s'", vp->u.s);
189}
190
191void
192to_string(struct val *vp)
193{
194	char *tmp;
195
196	if (vp->type == string || vp->type == numeric_string)
197		return;
198
199	/*
200	 * log_10(x) ~= 0.3 * log_2(x).  Rounding up gives the number
201	 * of digits; add one each for the sign and terminating null
202	 * character, respectively.
203	 */
204#define	NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1)
205	tmp = malloc(NDIGITS(vp->u.i));
206	if (tmp == NULL)
207		errx(ERR_EXIT, "malloc() failed");
208
209	sprintf(tmp, "%jd", vp->u.i);
210	vp->type = string;
211	vp->u.s  = tmp;
212}
213
214
215int
216is_integer(const char *s)
217{
218	if (nonposix) {
219		if (*s == '\0')
220			return (1);
221		while (isspace((unsigned char)*s))
222			s++;
223	}
224	if (*s == '-' || (nonposix && *s == '+'))
225		s++;
226	if (*s == '\0')
227		return (0);
228	while (isdigit((unsigned char)*s))
229		s++;
230	return (*s == '\0');
231}
232
233
234int
235isstring(struct val *vp)
236{
237	/* only TRUE if this string is not a valid integer */
238	return (vp->type == string);
239}
240
241
242int
243yylex(void)
244{
245	char *p;
246
247	if (*av == NULL)
248		return (0);
249
250	p = *av++;
251
252	if (strlen (p) == 1) {
253		if (strchr ("|&=<>+-*/%:()", *p))
254			return (*p);
255	} else if (strlen (p) == 2 && p[1] == '=') {
256		switch (*p) {
257		case '>': return (GE);
258		case '<': return (LE);
259		case '!': return (NE);
260		}
261	}
262
263	yylval.val = make_str (p);
264	return (TOKEN);
265}
266
267int
268is_zero_or_null(struct val *vp)
269{
270	if (vp->type == integer) {
271		return (vp->u.i == 0);
272	} else {
273		return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0));
274	}
275	/* NOTREACHED */
276}
277
278int
279main(int argc, char *argv[])
280{
281	int c;
282
283	setlocale (LC_ALL, "");
284	if (getenv("EXPR_COMPAT") != NULL
285	    || check_utility_compat("expr")) {
286		av = argv + 1;
287		nonposix = 1;
288	} else {
289		while ((c = getopt(argc, argv, "e")) != -1)
290			switch (c) {
291			case 'e':
292				nonposix = 1;
293				break;
294
295			default:
296				fprintf(stderr,
297				    "usage: expr [-e] expression\n");
298				exit(ERR_EXIT);
299			}
300		av = argv + optind;
301	}
302
303	yyparse();
304
305	if (result->type == integer)
306		printf("%jd\n", result->u.i);
307	else
308		printf("%s\n", result->u.s);
309
310	return (is_zero_or_null(result));
311}
312
313int
314yyerror(const char *s __unused)
315{
316	errx(ERR_EXIT, "syntax error");
317}
318
319
320struct val *
321op_or(struct val *a, struct val *b)
322{
323	if (!is_zero_or_null(a)) {
324		free_value(b);
325		return (a);
326	}
327	free_value(a);
328	if (!is_zero_or_null(b))
329		return (b);
330	free_value(b);
331	return (make_integer((intmax_t)0));
332}
333
334struct val *
335op_and(struct val *a, struct val *b)
336{
337	if (is_zero_or_null (a) || is_zero_or_null (b)) {
338		free_value (a);
339		free_value (b);
340		return (make_integer ((intmax_t)0));
341	} else {
342		free_value (b);
343		return (a);
344	}
345}
346
347struct val *
348op_eq(struct val *a, struct val *b)
349{
350	struct val *r;
351
352	if (isstring (a) || isstring (b)) {
353		to_string (a);
354		to_string (b);
355		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) == 0));
356	} else {
357		assert_to_integer(a);
358		assert_to_integer(b);
359		r = make_integer ((intmax_t)(a->u.i == b->u.i));
360	}
361
362	free_value (a);
363	free_value (b);
364	return r;
365}
366
367struct val *
368op_gt(struct val *a, struct val *b)
369{
370	struct val *r;
371
372	if (isstring (a) || isstring (b)) {
373		to_string (a);
374		to_string (b);
375		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) > 0));
376	} else {
377		assert_to_integer(a);
378		assert_to_integer(b);
379		r = make_integer ((intmax_t)(a->u.i > b->u.i));
380	}
381
382	free_value (a);
383	free_value (b);
384	return r;
385}
386
387struct val *
388op_lt(struct val *a, struct val *b)
389{
390	struct val *r;
391
392	if (isstring (a) || isstring (b)) {
393		to_string (a);
394		to_string (b);
395		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) < 0));
396	} else {
397		assert_to_integer(a);
398		assert_to_integer(b);
399		r = make_integer ((intmax_t)(a->u.i < b->u.i));
400	}
401
402	free_value (a);
403	free_value (b);
404	return r;
405}
406
407struct val *
408op_ge(struct val *a, struct val *b)
409{
410	struct val *r;
411
412	if (isstring (a) || isstring (b)) {
413		to_string (a);
414		to_string (b);
415		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) >= 0));
416	} else {
417		assert_to_integer(a);
418		assert_to_integer(b);
419		r = make_integer ((intmax_t)(a->u.i >= b->u.i));
420	}
421
422	free_value (a);
423	free_value (b);
424	return r;
425}
426
427struct val *
428op_le(struct val *a, struct val *b)
429{
430	struct val *r;
431
432	if (isstring (a) || isstring (b)) {
433		to_string (a);
434		to_string (b);
435		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) <= 0));
436	} else {
437		assert_to_integer(a);
438		assert_to_integer(b);
439		r = make_integer ((intmax_t)(a->u.i <= b->u.i));
440	}
441
442	free_value (a);
443	free_value (b);
444	return r;
445}
446
447struct val *
448op_ne(struct val *a, struct val *b)
449{
450	struct val *r;
451
452	if (isstring (a) || isstring (b)) {
453		to_string (a);
454		to_string (b);
455		r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) != 0));
456	} else {
457		assert_to_integer(a);
458		assert_to_integer(b);
459		r = make_integer ((intmax_t)(a->u.i != b->u.i));
460	}
461
462	free_value (a);
463	free_value (b);
464	return r;
465}
466
467int
468chk_plus(intmax_t a, intmax_t b, intmax_t r)
469{
470
471	/* sum of two positive numbers must be positive */
472	if (a > 0 && b > 0 && r <= 0)
473		return 1;
474	/* sum of two negative numbers must be negative */
475	if (a < 0 && b < 0 && r >= 0)
476		return 1;
477	/* all other cases are OK */
478	return 0;
479}
480
481struct val *
482op_plus(struct val *a, struct val *b)
483{
484	struct val *r;
485
486	assert_to_integer(a);
487	assert_to_integer(b);
488
489	r = make_integer(a->u.i + b->u.i);
490	if (chk_plus(a->u.i, b->u.i, r->u.i)) {
491		errx(ERR_EXIT, "overflow");
492	}
493
494	free_value (a);
495	free_value (b);
496	return r;
497}
498
499int
500chk_minus(intmax_t a, intmax_t b, intmax_t r)
501{
502
503	/* special case subtraction of INTMAX_MIN */
504	if (b == INTMAX_MIN) {
505		if (a >= 0)
506			return 1;
507		else
508			return 0;
509	}
510	/* this is allowed for b != INTMAX_MIN */
511	return chk_plus (a, -b, r);
512}
513
514struct val *
515op_minus(struct val *a, struct val *b)
516{
517	struct val *r;
518
519	assert_to_integer(a);
520	assert_to_integer(b);
521
522	r = make_integer(a->u.i - b->u.i);
523	if (chk_minus(a->u.i, b->u.i, r->u.i)) {
524		errx(ERR_EXIT, "overflow");
525	}
526
527	free_value (a);
528	free_value (b);
529	return r;
530}
531
532int
533chk_times(intmax_t a, intmax_t b, intmax_t r)
534{
535	/* special case: first operand is 0, no overflow possible */
536	if (a == 0)
537		return 0;
538	/* verify that result of division matches second operand */
539	if (r / a != b)
540		return 1;
541	return 0;
542}
543
544struct val *
545op_times(struct val *a, struct val *b)
546{
547	struct val *r;
548
549	assert_to_integer(a);
550	assert_to_integer(b);
551
552	r = make_integer(a->u.i * b->u.i);
553	if (chk_times(a->u.i, b->u.i, r->u.i)) {
554		errx(ERR_EXIT, "overflow");
555	}
556
557	free_value (a);
558	free_value (b);
559	return (r);
560}
561
562int
563chk_div(intmax_t a, intmax_t b)
564{
565	/* div by zero has been taken care of before */
566	/* only INTMAX_MIN / -1 causes overflow */
567	if (a == INTMAX_MIN && b == -1)
568		return 1;
569	/* everything else is OK */
570	return 0;
571}
572
573struct val *
574op_div(struct val *a, struct val *b)
575{
576	struct val *r;
577
578	assert_to_integer(a);
579	assert_to_integer(b);
580
581	if (b->u.i == 0) {
582		errx(ERR_EXIT, "division by zero");
583	}
584	if (chk_div(a->u.i, b->u.i)) {
585		errx(ERR_EXIT, "overflow");
586	}
587	r = make_integer(a->u.i / b->u.i);
588
589	free_value (a);
590	free_value (b);
591	return r;
592}
593
594struct val *
595op_rem(struct val *a, struct val *b)
596{
597	struct val *r;
598
599	assert_to_integer(a);
600	assert_to_integer(b);
601	if (b->u.i == 0) {
602		errx(ERR_EXIT, "division by zero");
603	}
604	r = make_integer(a->u.i % b->u.i);
605
606	free_value (a);
607	free_value (b);
608	return r;
609}
610
611struct val *
612op_colon(struct val *a, struct val *b)
613{
614	regex_t rp;
615	regmatch_t rm[2];
616	char errbuf[256];
617	int eval;
618	struct val *v;
619
620	/* coerce both arguments to strings */
621	to_string(a);
622	to_string(b);
623
624	/* compile regular expression */
625	if ((eval = regcomp (&rp, b->u.s, 0)) != 0) {
626		regerror (eval, &rp, errbuf, sizeof(errbuf));
627		errx(ERR_EXIT, "%s", errbuf);
628	}
629
630	/* compare string against pattern */
631	/* remember that patterns are anchored to the beginning of the line */
632	if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) {
633		if (rm[1].rm_so >= 0) {
634			*(a->u.s + rm[1].rm_eo) = '\0';
635			v = make_str (a->u.s + rm[1].rm_so);
636
637		} else {
638			v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so));
639		}
640	} else {
641		if (rp.re_nsub == 0) {
642			v = make_integer ((intmax_t)0);
643		} else {
644			v = make_str ("");
645		}
646	}
647
648	/* free arguments and pattern buffer */
649	free_value (a);
650	free_value (b);
651	regfree (&rp);
652
653	return v;
654}
655