1 %{ 2 /* Written by Pace Willisson (pace@blitz.com) 3 * and placed in the public domain. 4 * 5 * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 6 * 7 * $FreeBSD$ 8 */ 9 10 #include <sys/types.h> 11 12 #include <ctype.h> 13 #include <err.h> 14 #include <errno.h> 15 #include <inttypes.h> 16 #include <limits.h> 17 #include <locale.h> 18 #include <stdio.h> 19 #include <stdlib.h> 20 #include <string.h> 21 #include <regex.h> 22 #include <unistd.h> 23 24 /* 25 * POSIX specifies a specific error code for syntax errors. We exit 26 * with this code for all errors. 27 */ 28 #define ERR_EXIT 2 29 30 enum valtype { 31 integer, numeric_string, string 32 } ; 33 34 struct val { 35 enum valtype type; 36 union { 37 char *s; 38 intmax_t i; 39 } u; 40 } ; 41 42 struct val *result; 43 44 int chk_div(intmax_t, intmax_t); 45 int chk_minus(intmax_t, intmax_t, intmax_t); 46 int chk_plus(intmax_t, intmax_t, intmax_t); 47 int chk_times(intmax_t, intmax_t, intmax_t); 48 void free_value(struct val *); 49 int is_zero_or_null(struct val *); 50 int isstring(struct val *); 51 struct val *make_integer(intmax_t); 52 struct val *make_str(const char *); 53 struct val *op_and(struct val *, struct val *); 54 struct val *op_colon(struct val *, struct val *); 55 struct val *op_div(struct val *, struct val *); 56 struct val *op_eq(struct val *, struct val *); 57 struct val *op_ge(struct val *, struct val *); 58 struct val *op_gt(struct val *, struct val *); 59 struct val *op_le(struct val *, struct val *); 60 struct val *op_lt(struct val *, struct val *); 61 struct val *op_minus(struct val *, struct val *); 62 struct val *op_ne(struct val *, struct val *); 63 struct val *op_or(struct val *, struct val *); 64 struct val *op_plus(struct val *, struct val *); 65 struct val *op_rem(struct val *, struct val *); 66 struct val *op_times(struct val *, struct val *); 67 intmax_t to_integer(struct val *); 68 void to_string(struct val *); 69 int yyerror(const char *); 70 int yylex(void); 71 int yyparse(void); 72 73 char **av; 74 %} 75 76 %union 77 { 78 struct val *val; 79 } 80 81 %left <val> '|' 82 %left <val> '&' 83 %left <val> '=' '>' '<' GE LE NE 84 %left <val> '+' '-' 85 %left <val> '*' '/' '%' 86 %left <val> ':' 87 88 %token <val> TOKEN 89 %type <val> start expr 90 91 %% 92 93 start: expr { result = $$; } 94 95 expr: TOKEN 96 | '(' expr ')' { $$ = $2; } 97 | expr '|' expr { $$ = op_or ($1, $3); } 98 | expr '&' expr { $$ = op_and ($1, $3); } 99 | expr '=' expr { $$ = op_eq ($1, $3); } 100 | expr '>' expr { $$ = op_gt ($1, $3); } 101 | expr '<' expr { $$ = op_lt ($1, $3); } 102 | expr GE expr { $$ = op_ge ($1, $3); } 103 | expr LE expr { $$ = op_le ($1, $3); } 104 | expr NE expr { $$ = op_ne ($1, $3); } 105 | expr '+' expr { $$ = op_plus ($1, $3); } 106 | expr '-' expr { $$ = op_minus ($1, $3); } 107 | expr '*' expr { $$ = op_times ($1, $3); } 108 | expr '/' expr { $$ = op_div ($1, $3); } 109 | expr '%' expr { $$ = op_rem ($1, $3); } 110 | expr ':' expr { $$ = op_colon ($1, $3); } 111 ; 112 113 114 %% 115 116 struct val * 117 make_integer(intmax_t i) 118 { 119 struct val *vp; 120 121 vp = (struct val *) malloc (sizeof (*vp)); 122 if (vp == NULL) { 123 errx(ERR_EXIT, "malloc() failed"); 124 } 125 126 vp->type = integer; 127 vp->u.i = i; 128 return vp; 129 } 130 131 struct val * 132 make_str(const char *s) 133 { 134 struct val *vp; 135 char *ep; 136 137 vp = (struct val *) malloc (sizeof (*vp)); 138 if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) { 139 errx(ERR_EXIT, "malloc() failed"); 140 } 141 142 /* 143 * Previously we tried to scan the string to see if it ``looked like'' 144 * an integer (erroneously, as it happened). Let strtoimax() do the 145 * dirty work. We could cache the value, except that we are using 146 * a union and need to preserve the original string form until we 147 * are certain that it is not needed. 148 * 149 * IEEE Std.1003.1-2001 says: 150 * /integer/ An argument consisting only of an (optional) unary minus 151 * followed by digits. 152 * 153 * This means that arguments which consist of digits followed by 154 * non-digits MUST NOT be considered integers. strtoimax() will 155 * figure this out for us. 156 */ 157 (void)strtoimax(s, &ep, 10); 158 159 if (*ep != '\0') 160 vp->type = string; 161 else 162 vp->type = numeric_string; 163 164 return vp; 165 } 166 167 168 void 169 free_value(struct val *vp) 170 { 171 if (vp->type == string || vp->type == numeric_string) 172 free (vp->u.s); 173 } 174 175 176 intmax_t 177 to_integer(struct val *vp) 178 { 179 intmax_t i; 180 181 if (vp->type == integer) 182 return 1; 183 184 if (vp->type == string) 185 return 0; 186 187 /* vp->type == numeric_string, make it numeric */ 188 errno = 0; 189 i = strtoimax(vp->u.s, (char **)NULL, 10); 190 if (errno == ERANGE) 191 err(ERR_EXIT, NULL); 192 193 free (vp->u.s); 194 vp->u.i = i; 195 vp->type = integer; 196 return 1; 197 } 198 199 void 200 to_string(struct val *vp) 201 { 202 char *tmp; 203 204 if (vp->type == string || vp->type == numeric_string) 205 return; 206 207 /* 208 * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 209 * of digits; add one each for the sign and terminating null 210 * character, respectively. 211 */ 212 #define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 213 tmp = malloc(NDIGITS(vp->u.i)); 214 if (tmp == NULL) 215 errx(ERR_EXIT, "malloc() failed"); 216 217 sprintf(tmp, "%jd", vp->u.i); 218 vp->type = string; 219 vp->u.s = tmp; 220 } 221 222 223 int 224 isstring(struct val *vp) 225 { 226 /* only TRUE if this string is not a valid integer */ 227 return (vp->type == string); 228 } 229 230 231 int 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 257 is_zero_or_null(struct val *vp) 258 { 259 if (vp->type == integer) { 260 return (vp->u.i == 0); 261 } else { 262 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0)); 263 } 264 /* NOTREACHED */ 265 } 266 267 int 268 main(int argc, char *argv[]) 269 { 270 int c; 271 272 setlocale (LC_ALL, ""); 273 while ((c = getopt(argc, argv, "")) != -1) 274 switch (c) { 275 default: 276 fprintf(stderr, "usage: expr [--] expression\n"); 277 exit(ERR_EXIT); 278 } 279 280 av = argv + optind; 281 282 yyparse(); 283 284 if (result->type == integer) 285 printf("%jd\n", result->u.i); 286 else 287 printf("%s\n", result->u.s); 288 289 return (is_zero_or_null(result)); 290 } 291 292 int 293 yyerror(const char *s __unused) 294 { 295 errx(ERR_EXIT, "syntax error"); 296 } 297 298 299 struct val * 300 op_or(struct val *a, struct val *b) 301 { 302 if (is_zero_or_null (a)) { 303 free_value (a); 304 return (b); 305 } else { 306 free_value (b); 307 return (a); 308 } 309 } 310 311 struct val * 312 op_and(struct val *a, struct val *b) 313 { 314 if (is_zero_or_null (a) || is_zero_or_null (b)) { 315 free_value (a); 316 free_value (b); 317 return (make_integer ((intmax_t)0)); 318 } else { 319 free_value (b); 320 return (a); 321 } 322 } 323 324 struct val * 325 op_eq(struct val *a, struct val *b) 326 { 327 struct val *r; 328 329 if (isstring (a) || isstring (b)) { 330 to_string (a); 331 to_string (b); 332 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) == 0)); 333 } else { 334 (void)to_integer(a); 335 (void)to_integer(b); 336 r = make_integer ((intmax_t)(a->u.i == b->u.i)); 337 } 338 339 free_value (a); 340 free_value (b); 341 return r; 342 } 343 344 struct val * 345 op_gt(struct val *a, struct val *b) 346 { 347 struct val *r; 348 349 if (isstring (a) || isstring (b)) { 350 to_string (a); 351 to_string (b); 352 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) > 0)); 353 } else { 354 (void)to_integer(a); 355 (void)to_integer(b); 356 r = make_integer ((intmax_t)(a->u.i > b->u.i)); 357 } 358 359 free_value (a); 360 free_value (b); 361 return r; 362 } 363 364 struct val * 365 op_lt(struct val *a, struct val *b) 366 { 367 struct val *r; 368 369 if (isstring (a) || isstring (b)) { 370 to_string (a); 371 to_string (b); 372 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) < 0)); 373 } else { 374 (void)to_integer(a); 375 (void)to_integer(b); 376 r = make_integer ((intmax_t)(a->u.i < b->u.i)); 377 } 378 379 free_value (a); 380 free_value (b); 381 return r; 382 } 383 384 struct val * 385 op_ge(struct val *a, struct val *b) 386 { 387 struct val *r; 388 389 if (isstring (a) || isstring (b)) { 390 to_string (a); 391 to_string (b); 392 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) >= 0)); 393 } else { 394 (void)to_integer(a); 395 (void)to_integer(b); 396 r = make_integer ((intmax_t)(a->u.i >= b->u.i)); 397 } 398 399 free_value (a); 400 free_value (b); 401 return r; 402 } 403 404 struct val * 405 op_le(struct val *a, struct val *b) 406 { 407 struct val *r; 408 409 if (isstring (a) || isstring (b)) { 410 to_string (a); 411 to_string (b); 412 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) <= 0)); 413 } else { 414 (void)to_integer(a); 415 (void)to_integer(b); 416 r = make_integer ((intmax_t)(a->u.i <= b->u.i)); 417 } 418 419 free_value (a); 420 free_value (b); 421 return r; 422 } 423 424 struct val * 425 op_ne(struct val *a, struct val *b) 426 { 427 struct val *r; 428 429 if (isstring (a) || isstring (b)) { 430 to_string (a); 431 to_string (b); 432 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) != 0)); 433 } else { 434 (void)to_integer(a); 435 (void)to_integer(b); 436 r = make_integer ((intmax_t)(a->u.i != b->u.i)); 437 } 438 439 free_value (a); 440 free_value (b); 441 return r; 442 } 443 444 int 445 chk_plus(intmax_t a, intmax_t b, intmax_t r) 446 { 447 /* sum of two positive numbers must be positive */ 448 if (a > 0 && b > 0 && r <= 0) 449 return 1; 450 /* sum of two negative numbers must be negative */ 451 if (a < 0 && b < 0 && r >= 0) 452 return 1; 453 /* all other cases are OK */ 454 return 0; 455 } 456 457 struct val * 458 op_plus(struct val *a, struct val *b) 459 { 460 struct val *r; 461 462 if (!to_integer (a) || !to_integer (b)) { 463 errx(ERR_EXIT, "non-numeric argument"); 464 } 465 466 r = make_integer (/*(intmax_t)*/(a->u.i + b->u.i)); 467 if (chk_plus (a->u.i, b->u.i, r->u.i)) { 468 errx(ERR_EXIT, "overflow"); 469 } 470 free_value (a); 471 free_value (b); 472 return r; 473 } 474 475 int 476 chk_minus(intmax_t a, intmax_t b, intmax_t r) 477 { 478 /* special case subtraction of INTMAX_MIN */ 479 if (b == INTMAX_MIN) { 480 if (a >= 0) 481 return 1; 482 else 483 return 0; 484 } 485 /* this is allowed for b != INTMAX_MIN */ 486 return chk_plus (a, -b, r); 487 } 488 489 struct val * 490 op_minus(struct val *a, struct val *b) 491 { 492 struct val *r; 493 494 if (!to_integer (a) || !to_integer (b)) { 495 errx(ERR_EXIT, "non-numeric argument"); 496 } 497 498 r = make_integer (/*(intmax_t)*/(a->u.i - b->u.i)); 499 if (chk_minus (a->u.i, b->u.i, r->u.i)) { 500 errx(ERR_EXIT, "overflow"); 501 } 502 free_value (a); 503 free_value (b); 504 return r; 505 } 506 507 int 508 chk_times(intmax_t a, intmax_t b, intmax_t r) 509 { 510 /* special case: first operand is 0, no overflow possible */ 511 if (a == 0) 512 return 0; 513 /* cerify that result of division matches second operand */ 514 if (r / a != b) 515 return 1; 516 return 0; 517 } 518 519 struct val * 520 op_times(struct val *a, struct val *b) 521 { 522 struct val *r; 523 524 if (!to_integer (a) || !to_integer (b)) { 525 errx(ERR_EXIT, "non-numeric argument"); 526 } 527 528 r = make_integer (/*(intmax_t)*/(a->u.i * b->u.i)); 529 if (chk_times (a->u.i, b->u.i, r->u.i)) { 530 errx(ERR_EXIT, "overflow"); 531 } 532 free_value (a); 533 free_value (b); 534 return (r); 535 } 536 537 int 538 chk_div(intmax_t a, intmax_t b) 539 { 540 /* div by zero has been taken care of before */ 541 /* only INTMAX_MIN / -1 causes overflow */ 542 if (a == INTMAX_MIN && b == -1) 543 return 1; 544 /* everything else is OK */ 545 return 0; 546 } 547 548 struct val * 549 op_div(struct val *a, struct val *b) 550 { 551 struct val *r; 552 553 if (!to_integer (a) || !to_integer (b)) { 554 errx(ERR_EXIT, "non-numeric argument"); 555 } 556 557 if (b->u.i == 0) { 558 errx(ERR_EXIT, "division by zero"); 559 } 560 561 r = make_integer (/*(intmax_t)*/(a->u.i / b->u.i)); 562 if (chk_div (a->u.i, b->u.i)) { 563 errx(ERR_EXIT, "overflow"); 564 } 565 free_value (a); 566 free_value (b); 567 return r; 568 } 569 570 struct val * 571 op_rem(struct val *a, struct val *b) 572 { 573 struct val *r; 574 575 if (!to_integer (a) || !to_integer (b)) { 576 errx(ERR_EXIT, "non-numeric argument"); 577 } 578 579 if (b->u.i == 0) { 580 errx(ERR_EXIT, "division by zero"); 581 } 582 583 r = make_integer (/*(intmax_t)*/(a->u.i % b->u.i)); 584 /* chk_rem necessary ??? */ 585 free_value (a); 586 free_value (b); 587 return r; 588 } 589 590 struct val * 591 op_colon(struct val *a, struct val *b) 592 { 593 regex_t rp; 594 regmatch_t rm[2]; 595 char errbuf[256]; 596 int eval; 597 struct val *v; 598 599 /* coerce to both arguments to strings */ 600 to_string(a); 601 to_string(b); 602 603 /* compile regular expression */ 604 if ((eval = regcomp (&rp, b->u.s, 0)) != 0) { 605 regerror (eval, &rp, errbuf, sizeof(errbuf)); 606 errx(ERR_EXIT, "%s", errbuf); 607 } 608 609 /* compare string against pattern */ 610 /* remember that patterns are anchored to the beginning of the line */ 611 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) { 612 if (rm[1].rm_so >= 0) { 613 *(a->u.s + rm[1].rm_eo) = '\0'; 614 v = make_str (a->u.s + rm[1].rm_so); 615 616 } else { 617 v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 618 } 619 } else { 620 if (rp.re_nsub == 0) { 621 v = make_integer ((intmax_t)0); 622 } else { 623 v = make_str (""); 624 } 625 } 626 627 /* free arguments and pattern buffer */ 628 free_value (a); 629 free_value (b); 630 regfree (&rp); 631 632 return v; 633 } 634