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