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