1 %{
2 /*-
3 * Written by Pace Willisson ([email protected])
4 * and placed in the public domain.
5 *
6 * Largely rewritten by J.T. Conklin ([email protected])
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
31 enum valtype {
32 integer, numeric_string, string
33 } ;
34
35 struct val {
36 enum valtype type;
37 union {
38 char *s;
39 intmax_t i;
40 } u;
41 } ;
42
43 char **av;
44 int nonposix;
45 struct val *result;
46
47 void assert_to_integer(struct val *);
48 void assert_div(intmax_t, intmax_t);
49 void assert_minus(intmax_t, intmax_t, intmax_t);
50 void assert_plus(intmax_t, intmax_t, intmax_t);
51 void assert_times(intmax_t, intmax_t, intmax_t);
52 int compare_vals(struct val *, struct val *);
53 void free_value(struct val *);
54 int is_integer(const char *);
55 int is_string(struct val *);
56 int is_zero_or_null(struct val *);
57 struct val *make_integer(intmax_t);
58 struct val *make_str(const char *);
59 struct val *op_and(struct val *, struct val *);
60 struct val *op_colon(struct val *, struct val *);
61 struct val *op_div(struct val *, struct val *);
62 struct val *op_eq(struct val *, struct val *);
63 struct val *op_ge(struct val *, struct val *);
64 struct val *op_gt(struct val *, struct val *);
65 struct val *op_le(struct val *, struct val *);
66 struct val *op_lt(struct val *, struct val *);
67 struct val *op_minus(struct val *, struct val *);
68 struct val *op_ne(struct val *, struct val *);
69 struct val *op_or(struct val *, struct val *);
70 struct val *op_plus(struct val *, struct val *);
71 struct val *op_rem(struct val *, struct val *);
72 struct val *op_times(struct val *, struct val *);
73 int to_integer(struct val *);
74 void to_string(struct val *);
75 int yyerror(const char *);
76 int 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
97 start: expr { result = $$; }
98
99 expr: 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 struct val *
120 make_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
133 struct val *
make_str(const char * s)134 make_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
150 void
free_value(struct val * vp)151 free_value(struct val *vp)
152 {
153 if (vp->type == string || vp->type == numeric_string)
154 free(vp->u.s);
155 }
156
157 int
to_integer(struct val * vp)158 to_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
176 void
assert_to_integer(struct val * vp)177 assert_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
185 void
to_string(struct val * vp)186 to_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
208 int
is_integer(const char * s)209 is_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
226 int
is_string(struct val * vp)227 is_string(struct val *vp)
228 {
229 /* only TRUE if this string is not a valid integer */
230 return (vp->type == string);
231 }
232
233 int
yylex(void)234 yylex(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
258 int
is_zero_or_null(struct val * vp)259 is_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
267 int
main(int argc,char * argv[])268 main(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
301 int
yyerror(const char * s __unused)302 yyerror(const char *s __unused)
303 {
304 errx(ERR_EXIT, "syntax error");
305 }
306
307 struct val *
op_or(struct val * a,struct val * b)308 op_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
321 struct val *
op_and(struct val * a,struct val * b)322 op_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
334 int
compare_vals(struct val * a,struct val * b)335 compare_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
359 struct val *
op_eq(struct val * a,struct val * b)360 op_eq(struct val *a, struct val *b)
361 {
362 return (make_integer((intmax_t)(compare_vals(a, b) == 0)));
363 }
364
365 struct val *
op_gt(struct val * a,struct val * b)366 op_gt(struct val *a, struct val *b)
367 {
368 return (make_integer((intmax_t)(compare_vals(a, b) > 0)));
369 }
370
371 struct val *
op_lt(struct val * a,struct val * b)372 op_lt(struct val *a, struct val *b)
373 {
374 return (make_integer((intmax_t)(compare_vals(a, b) < 0)));
375 }
376
377 struct val *
op_ge(struct val * a,struct val * b)378 op_ge(struct val *a, struct val *b)
379 {
380 return (make_integer((intmax_t)(compare_vals(a, b) >= 0)));
381 }
382
383 struct val *
op_le(struct val * a,struct val * b)384 op_le(struct val *a, struct val *b)
385 {
386 return (make_integer((intmax_t)(compare_vals(a, b) <= 0)));
387 }
388
389 struct val *
op_ne(struct val * a,struct val * b)390 op_ne(struct val *a, struct val *b)
391 {
392 return (make_integer((intmax_t)(compare_vals(a, b) != 0)));
393 }
394
395 void
assert_plus(intmax_t a,intmax_t b,intmax_t r)396 assert_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
407 struct val *
op_plus(struct val * a,struct val * b)408 op_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
422 void
assert_minus(intmax_t a,intmax_t b,intmax_t r)423 assert_minus(intmax_t a, intmax_t b, intmax_t r)
424 {
425 if ((a >= 0 && b < 0 && r <= 0) ||
426 (a < 0 && b > 0 && r >= 0))
427 errx(ERR_EXIT, "overflow");
428 }
429
430 struct val *
op_minus(struct val * a,struct val * b)431 op_minus(struct val *a, struct val *b)
432 {
433 struct val *r;
434
435 assert_to_integer(a);
436 assert_to_integer(b);
437 r = make_integer(a->u.i - b->u.i);
438 assert_minus(a->u.i, b->u.i, r->u.i);
439
440 free_value(a);
441 free_value(b);
442 return (r);
443 }
444
445 /*
446 * We depend on undefined behaviour giving a result (in r).
447 * To test this result, pass it as volatile. This prevents
448 * optimizing away of the test based on the undefined behaviour.
449 */
450 void
assert_times(intmax_t a,intmax_t b,volatile intmax_t r)451 assert_times(intmax_t a, intmax_t b, volatile intmax_t r)
452 {
453 /*
454 * If the first operand is 0, no overflow is possible,
455 * else the result of the division test must match the
456 * second operand.
457 *
458 * Be careful to avoid overflow in the overflow test, as
459 * in assert_div(). Overflow in division would kill us
460 * with a SIGFPE before getting the test wrong. In old
461 * buggy versions, optimization used to give a null test
462 * instead of a SIGFPE.
463 */
464 if ((a == -1 && b == INTMAX_MIN) || (a != 0 && r / a != b))
465 errx(ERR_EXIT, "overflow");
466 }
467
468 struct val *
op_times(struct val * a,struct val * b)469 op_times(struct val *a, struct val *b)
470 {
471 struct val *r;
472
473 assert_to_integer(a);
474 assert_to_integer(b);
475 r = make_integer(a->u.i * b->u.i);
476 assert_times(a->u.i, b->u.i, r->u.i);
477
478 free_value(a);
479 free_value(b);
480 return (r);
481 }
482
483 void
assert_div(intmax_t a,intmax_t b)484 assert_div(intmax_t a, intmax_t b)
485 {
486 if (b == 0)
487 errx(ERR_EXIT, "division by zero");
488 /* only INTMAX_MIN / -1 causes overflow */
489 if (a == INTMAX_MIN && b == -1)
490 errx(ERR_EXIT, "overflow");
491 }
492
493 struct val *
op_div(struct val * a,struct val * b)494 op_div(struct val *a, struct val *b)
495 {
496 struct val *r;
497
498 assert_to_integer(a);
499 assert_to_integer(b);
500 /* assert based on operands only, not on result */
501 assert_div(a->u.i, b->u.i);
502 r = make_integer(a->u.i / b->u.i);
503
504 free_value(a);
505 free_value(b);
506 return (r);
507 }
508
509 struct val *
op_rem(struct val * a,struct val * b)510 op_rem(struct val *a, struct val *b)
511 {
512 struct val *r;
513
514 assert_to_integer(a);
515 assert_to_integer(b);
516 /* pass a=1 to only check for div by zero */
517 assert_div(1, b->u.i);
518 r = make_integer(a->u.i % b->u.i);
519
520 free_value(a);
521 free_value(b);
522 return (r);
523 }
524
525 struct val *
op_colon(struct val * a,struct val * b)526 op_colon(struct val *a, struct val *b)
527 {
528 regex_t rp;
529 regmatch_t rm[2];
530 char errbuf[256];
531 int eval;
532 struct val *v;
533
534 /* coerce both arguments to strings */
535 to_string(a);
536 to_string(b);
537
538 /* compile regular expression */
539 if ((eval = regcomp(&rp, b->u.s, 0)) != 0) {
540 regerror(eval, &rp, errbuf, sizeof(errbuf));
541 errx(ERR_EXIT, "%s", errbuf);
542 }
543
544 /* compare string against pattern */
545 /* remember that patterns are anchored to the beginning of the line */
546 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0)
547 if (rm[1].rm_so >= 0) {
548 *(a->u.s + rm[1].rm_eo) = '\0';
549 v = make_str(a->u.s + rm[1].rm_so);
550
551 } else
552 v = make_integer((intmax_t)(rm[0].rm_eo));
553 else
554 if (rp.re_nsub == 0)
555 v = make_integer((intmax_t)0);
556 else
557 v = make_str("");
558
559 /* free arguments and pattern buffer */
560 free_value(a);
561 free_value(b);
562 regfree(&rp);
563
564 return (v);
565 }
566