expr.y revision 95278
183098Smp%{ 283098Smp/* Written by Pace Willisson (pace@blitz.com) 359243Sobrien * and placed in the public domain. 483098Smp * 583098Smp * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 659243Sobrien * 759243Sobrien * $FreeBSD: head/bin/expr/expr.y 95278 2002-04-22 21:23:09Z wollman $ 859243Sobrien */ 959243Sobrien 1059243Sobrien#include <sys/types.h> 1159243Sobrien 1259243Sobrien#include <ctype.h> 1359243Sobrien#include <err.h> 1459243Sobrien#include <errno.h> 1559243Sobrien#include <inttypes.h> 1659243Sobrien#include <limits.h> 1759243Sobrien#include <locale.h> 18100616Smp#include <stdio.h> 1959243Sobrien#include <stdlib.h> 2059243Sobrien#include <string.h> 2159243Sobrien#include <regex.h> 2259243Sobrien#include <unistd.h> 2359243Sobrien 2459243Sobrien/* 2559243Sobrien * POSIX specifies a specific error code for syntax errors. We exit 2659243Sobrien * with this code for all errors. 2759243Sobrien */ 2859243Sobrien#define ERR_EXIT 2 2959243Sobrien 3059243Sobrienenum valtype { 3159243Sobrien integer, numeric_string, string 3259243Sobrien} ; 3359243Sobrien 3483098Smpstruct val { 3559243Sobrien enum valtype type; 3659243Sobrien union { 3759243Sobrien char *s; 3859243Sobrien intmax_t i; 3959243Sobrien } u; 4059243Sobrien} ; 4183098Smp 4283098Smpstruct val *result; 4383098Smp 4483098Smpint chk_div(intmax_t, intmax_t); 4583098Smpint chk_minus(intmax_t, intmax_t, intmax_t); 4683098Smpint chk_plus(intmax_t, intmax_t, intmax_t); 47167465Smpint chk_times(intmax_t, intmax_t, intmax_t); 4883098Smpvoid free_value(struct val *); 4983098Smpint is_zero_or_null(struct val *); 5083098Smpint isstring(struct val *); 5183098Smpstruct val *make_integer(intmax_t); 5283098Smpstruct val *make_str(const char *); 5383098Smpstruct val *op_and(struct val *, struct val *); 54167465Smpstruct val *op_colon(struct val *, struct val *); 55167465Smpstruct val *op_div(struct val *, struct val *); 56167465Smpstruct val *op_eq(struct val *, struct val *); 57167465Smpstruct val *op_ge(struct val *, struct val *); 58167465Smpstruct val *op_gt(struct val *, struct val *); 5959243Sobrienstruct val *op_le(struct val *, struct val *); 6059243Sobrienstruct val *op_lt(struct val *, struct val *); 6183098Smpstruct val *op_minus(struct val *, struct val *); 6283098Smpstruct val *op_ne(struct val *, struct val *); 6383098Smpstruct val *op_or(struct val *, struct val *); 6483098Smpstruct val *op_plus(struct val *, struct val *); 6583098Smpstruct val *op_rem(struct val *, struct val *); 6683098Smpstruct val *op_times(struct val *, struct val *); 6783098Smpintmax_t to_integer(struct val *); 6859243Sobrienvoid to_string(struct val *); 6983098Smpint yyerror(const char *); 7083098Smpint yylex(void); 7183098Smpint yyparse(void); 7283098Smp 7359243Sobrienchar **av; 74100616Smp%} 7583098Smp 7683098Smp%union 7783098Smp{ 7883098Smp struct val *val; 7983098Smp} 8083098Smp 8183098Smp%left <val> '|' 8283098Smp%left <val> '&' 83231990Smp%left <val> '=' '>' '<' GE LE NE 84231990Smp%left <val> '+' '-' 8559243Sobrien%left <val> '*' '/' '%' 8683098Smp%left <val> ':' 87100616Smp 8883098Smp%token <val> TOKEN 89167465Smp%type <val> start expr 90167465Smp 91167465Smp%% 92145479Smp 9359243Sobrienstart: expr { result = $$; } 94 95expr: 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 116struct val * 117make_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 131struct val * 132make_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 168void 169free_value(struct val *vp) 170{ 171 if (vp->type == string || vp->type == numeric_string) 172 free (vp->u.s); 173} 174 175 176intmax_t 177to_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 199void 200to_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 223int 224isstring(struct val *vp) 225{ 226 /* only TRUE if this string is not a valid integer */ 227 return (vp->type == string); 228} 229 230 231int 232yylex(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 256int 257is_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 267int 268main(int argc, char *argv[]) 269{ 270 int c; 271 272 setlocale (LC_ALL, ""); 273 if (getenv("EXPR_COMPAT") != NULL) { 274 av = argv + 1; 275 } else { 276 while ((c = getopt(argc, argv, "")) != -1) 277 switch (c) { 278 default: 279 fprintf(stderr,"usage: expr [--] expression\n"); 280 exit(ERR_EXIT); 281 } 282 av = argv + optind; 283 } 284 285 yyparse(); 286 287 if (result->type == integer) 288 printf("%jd\n", result->u.i); 289 else 290 printf("%s\n", result->u.s); 291 292 return (is_zero_or_null(result)); 293} 294 295int 296yyerror(const char *s __unused) 297{ 298 errx(ERR_EXIT, "syntax error"); 299} 300 301 302struct val * 303op_or(struct val *a, struct val *b) 304{ 305 if (is_zero_or_null (a)) { 306 free_value (a); 307 return (b); 308 } else { 309 free_value (b); 310 return (a); 311 } 312} 313 314struct val * 315op_and(struct val *a, struct val *b) 316{ 317 if (is_zero_or_null (a) || is_zero_or_null (b)) { 318 free_value (a); 319 free_value (b); 320 return (make_integer ((intmax_t)0)); 321 } else { 322 free_value (b); 323 return (a); 324 } 325} 326 327struct val * 328op_eq(struct val *a, struct val *b) 329{ 330 struct val *r; 331 332 if (isstring (a) || isstring (b)) { 333 to_string (a); 334 to_string (b); 335 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) == 0)); 336 } else { 337 (void)to_integer(a); 338 (void)to_integer(b); 339 r = make_integer ((intmax_t)(a->u.i == b->u.i)); 340 } 341 342 free_value (a); 343 free_value (b); 344 return r; 345} 346 347struct val * 348op_gt(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 (void)to_integer(a); 358 (void)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_lt(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 (void)to_integer(a); 378 (void)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_ge(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 (void)to_integer(a); 398 (void)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_le(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 (void)to_integer(a); 418 (void)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_ne(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 (void)to_integer(a); 438 (void)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 447int 448chk_plus(intmax_t a, intmax_t b, intmax_t r) 449{ 450 /* sum of two positive numbers must be positive */ 451 if (a > 0 && b > 0 && r <= 0) 452 return 1; 453 /* sum of two negative numbers must be negative */ 454 if (a < 0 && b < 0 && r >= 0) 455 return 1; 456 /* all other cases are OK */ 457 return 0; 458} 459 460struct val * 461op_plus(struct val *a, struct val *b) 462{ 463 struct val *r; 464 465 if (!to_integer (a) || !to_integer (b)) { 466 errx(ERR_EXIT, "non-numeric argument"); 467 } 468 469 r = make_integer (/*(intmax_t)*/(a->u.i + b->u.i)); 470 if (chk_plus (a->u.i, b->u.i, r->u.i)) { 471 errx(ERR_EXIT, "overflow"); 472 } 473 free_value (a); 474 free_value (b); 475 return r; 476} 477 478int 479chk_minus(intmax_t a, intmax_t b, intmax_t r) 480{ 481 /* special case subtraction of INTMAX_MIN */ 482 if (b == INTMAX_MIN) { 483 if (a >= 0) 484 return 1; 485 else 486 return 0; 487 } 488 /* this is allowed for b != INTMAX_MIN */ 489 return chk_plus (a, -b, r); 490} 491 492struct val * 493op_minus(struct val *a, struct val *b) 494{ 495 struct val *r; 496 497 if (!to_integer (a) || !to_integer (b)) { 498 errx(ERR_EXIT, "non-numeric argument"); 499 } 500 501 r = make_integer (/*(intmax_t)*/(a->u.i - b->u.i)); 502 if (chk_minus (a->u.i, b->u.i, r->u.i)) { 503 errx(ERR_EXIT, "overflow"); 504 } 505 free_value (a); 506 free_value (b); 507 return r; 508} 509 510int 511chk_times(intmax_t a, intmax_t b, intmax_t r) 512{ 513 /* special case: first operand is 0, no overflow possible */ 514 if (a == 0) 515 return 0; 516 /* cerify that result of division matches second operand */ 517 if (r / a != b) 518 return 1; 519 return 0; 520} 521 522struct val * 523op_times(struct val *a, struct val *b) 524{ 525 struct val *r; 526 527 if (!to_integer (a) || !to_integer (b)) { 528 errx(ERR_EXIT, "non-numeric argument"); 529 } 530 531 r = make_integer (/*(intmax_t)*/(a->u.i * b->u.i)); 532 if (chk_times (a->u.i, b->u.i, r->u.i)) { 533 errx(ERR_EXIT, "overflow"); 534 } 535 free_value (a); 536 free_value (b); 537 return (r); 538} 539 540int 541chk_div(intmax_t a, intmax_t b) 542{ 543 /* div by zero has been taken care of before */ 544 /* only INTMAX_MIN / -1 causes overflow */ 545 if (a == INTMAX_MIN && b == -1) 546 return 1; 547 /* everything else is OK */ 548 return 0; 549} 550 551struct val * 552op_div(struct val *a, struct val *b) 553{ 554 struct val *r; 555 556 if (!to_integer (a) || !to_integer (b)) { 557 errx(ERR_EXIT, "non-numeric argument"); 558 } 559 560 if (b->u.i == 0) { 561 errx(ERR_EXIT, "division by zero"); 562 } 563 564 r = make_integer (/*(intmax_t)*/(a->u.i / b->u.i)); 565 if (chk_div (a->u.i, b->u.i)) { 566 errx(ERR_EXIT, "overflow"); 567 } 568 free_value (a); 569 free_value (b); 570 return r; 571} 572 573struct val * 574op_rem(struct val *a, struct val *b) 575{ 576 struct val *r; 577 578 if (!to_integer (a) || !to_integer (b)) { 579 errx(ERR_EXIT, "non-numeric argument"); 580 } 581 582 if (b->u.i == 0) { 583 errx(ERR_EXIT, "division by zero"); 584 } 585 586 r = make_integer (/*(intmax_t)*/(a->u.i % b->u.i)); 587 /* chk_rem necessary ??? */ 588 free_value (a); 589 free_value (b); 590 return r; 591} 592 593struct val * 594op_colon(struct val *a, struct val *b) 595{ 596 regex_t rp; 597 regmatch_t rm[2]; 598 char errbuf[256]; 599 int eval; 600 struct val *v; 601 602 /* coerce to both arguments to strings */ 603 to_string(a); 604 to_string(b); 605 606 /* compile regular expression */ 607 if ((eval = regcomp (&rp, b->u.s, 0)) != 0) { 608 regerror (eval, &rp, errbuf, sizeof(errbuf)); 609 errx(ERR_EXIT, "%s", errbuf); 610 } 611 612 /* compare string against pattern */ 613 /* remember that patterns are anchored to the beginning of the line */ 614 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) { 615 if (rm[1].rm_so >= 0) { 616 *(a->u.s + rm[1].rm_eo) = '\0'; 617 v = make_str (a->u.s + rm[1].rm_so); 618 619 } else { 620 v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 621 } 622 } else { 623 if (rp.re_nsub == 0) { 624 v = make_integer ((intmax_t)0); 625 } else { 626 v = make_str (""); 627 } 628 } 629 630 /* free arguments and pattern buffer */ 631 free_value (a); 632 free_value (b); 633 regfree (&rp); 634 635 return v; 636} 637