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