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: src/bin/expr/expr.y,v 1.28 2011/07/09 12:20:15 se Exp $ 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); 77int 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 98start: expr { result = $$; } 99 100expr: 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 120struct val * 121make_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 134struct val * 135make_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 151void 152free_value(struct val *vp) 153{ 154 if (vp->type == string || vp->type == numeric_string) 155 free(vp->u.s); 156} 157 158int 159to_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 177void 178assert_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 186void 187to_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 209int 210is_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 227int 228is_string(struct val *vp) 229{ 230 /* only TRUE if this string is not a valid integer */ 231 return (vp->type == string); 232} 233 234int 235yylex(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 259int 260is_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 268int 269main(int argc, char *argv[]) 270{ 271#ifndef __APPLE__ 272 int c; 273#endif 274 275 setlocale(LC_ALL, ""); 276#ifdef __APPLE__ 277 av = argv + 1; 278 if (*av && !strcmp(*av, "--")) 279 av++; 280#else 281 if (getenv("EXPR_COMPAT") != NULL 282 || check_utility_compat("expr")) { 283 av = argv + 1; 284 nonposix = 1; 285 } else { 286 while ((c = getopt(argc, argv, "e")) != -1) { 287 switch (c) { 288 case 'e': 289 nonposix = 1; 290 break; 291 default: 292 errx(ERR_EXIT, 293 "usage: expr [-e] expression\n"); 294 } 295 } 296 av = argv + optind; 297 } 298#endif 299 300 yyparse(); 301 302#ifdef __APPLE__ 303 if (to_integer(result)) 304#else 305 if (result->type == integer) 306#endif 307 printf("%jd\n", result->u.i); 308 else 309 printf("%s\n", result->u.s); 310 311 return (is_zero_or_null(result)); 312} 313 314int 315yyerror(const char *s __unused) 316{ 317 errx(ERR_EXIT, "syntax error"); 318} 319 320struct val * 321op_or(struct val *a, struct val *b) 322{ 323 if (!is_zero_or_null(a)) { 324 free_value(b); 325 return (a); 326 } 327 free_value(a); 328 if (!is_zero_or_null(b)) 329 return (b); 330 free_value(b); 331 return (make_integer((intmax_t)0)); 332} 333 334struct val * 335op_and(struct val *a, struct val *b) 336{ 337 if (is_zero_or_null(a) || is_zero_or_null(b)) { 338 free_value(a); 339 free_value(b); 340 return (make_integer((intmax_t)0)); 341 } else { 342 free_value(b); 343 return (a); 344 } 345} 346 347int 348compare_vals(struct val *a, struct val *b) 349{ 350 int r; 351 352 if (is_string(a) || is_string(b)) { 353 to_string(a); 354 to_string(b); 355 r = strcoll(a->u.s, b->u.s); 356 } else { 357 assert_to_integer(a); 358 assert_to_integer(b); 359 if (a->u.i > b->u.i) 360 r = 1; 361 else if (a->u.i < b->u.i) 362 r = -1; 363 else 364 r = 0; 365 } 366 367 free_value(a); 368 free_value(b); 369 return (r); 370} 371 372struct val * 373op_eq(struct val *a, struct val *b) 374{ 375 return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 376} 377 378struct val * 379op_gt(struct val *a, struct val *b) 380{ 381 return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 382} 383 384struct val * 385op_lt(struct val *a, struct val *b) 386{ 387 return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 388} 389 390struct val * 391op_ge(struct val *a, struct val *b) 392{ 393 return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 394} 395 396struct val * 397op_le(struct val *a, struct val *b) 398{ 399 return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 400} 401 402struct val * 403op_ne(struct val *a, struct val *b) 404{ 405 return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 406} 407 408void 409assert_plus(intmax_t a, intmax_t b, intmax_t r) 410{ 411 /* 412 * sum of two positive numbers must be positive, 413 * sum of two negative numbers must be negative 414 */ 415 if ((a > 0 && b > 0 && r <= 0) || 416 (a < 0 && b < 0 && r >= 0)) 417 errx(ERR_EXIT, "overflow"); 418} 419 420struct val * 421op_plus(struct val *a, struct val *b) 422{ 423 struct val *r; 424 425 assert_to_integer(a); 426 assert_to_integer(b); 427 r = make_integer(a->u.i + b->u.i); 428 assert_plus(a->u.i, b->u.i, r->u.i); 429 430 free_value(a); 431 free_value(b); 432 return (r); 433} 434 435void 436assert_minus(intmax_t a, intmax_t b, intmax_t r) 437{ 438 /* special case subtraction of INTMAX_MIN */ 439 if (b == INTMAX_MIN && a < 0) 440 errx(ERR_EXIT, "overflow"); 441 /* check addition of negative subtrahend */ 442 assert_plus(a, -b, r); 443} 444 445struct val * 446op_minus(struct val *a, struct val *b) 447{ 448 struct val *r; 449 450 assert_to_integer(a); 451 assert_to_integer(b); 452 r = make_integer(a->u.i - b->u.i); 453 assert_minus(a->u.i, b->u.i, r->u.i); 454 455 free_value(a); 456 free_value(b); 457 return (r); 458} 459 460void 461assert_times(intmax_t a, intmax_t b, intmax_t r) 462{ 463 /* 464 * if first operand is 0, no overflow is possible, 465 * else result of division test must match second operand 466 */ 467 if (a != 0 && r / a != b) 468 errx(ERR_EXIT, "overflow"); 469} 470 471struct val * 472op_times(struct val *a, struct val *b) 473{ 474 struct val *r; 475 476 assert_to_integer(a); 477 assert_to_integer(b); 478 r = make_integer(a->u.i * b->u.i); 479 assert_times(a->u.i, b->u.i, r->u.i); 480 481 free_value(a); 482 free_value(b); 483 return (r); 484} 485 486void 487assert_div(intmax_t a, intmax_t b) 488{ 489 if (b == 0) 490 errx(ERR_EXIT, "division by zero"); 491 /* only INTMAX_MIN / -1 causes overflow */ 492 if (a == INTMAX_MIN && b == -1) 493 errx(ERR_EXIT, "overflow"); 494} 495 496struct val * 497op_div(struct val *a, struct val *b) 498{ 499 struct val *r; 500 501 assert_to_integer(a); 502 assert_to_integer(b); 503 /* assert based on operands only, not on result */ 504 assert_div(a->u.i, b->u.i); 505 r = make_integer(a->u.i / b->u.i); 506 507 free_value(a); 508 free_value(b); 509 return (r); 510} 511 512struct val * 513op_rem(struct val *a, struct val *b) 514{ 515 struct val *r; 516 517 assert_to_integer(a); 518 assert_to_integer(b); 519 /* pass a=1 to only check for div by zero */ 520 assert_div(1, b->u.i); 521 r = make_integer(a->u.i % b->u.i); 522 523 free_value(a); 524 free_value(b); 525 return (r); 526} 527 528struct val * 529op_colon(struct val *a, struct val *b) 530{ 531 regex_t rp; 532 regmatch_t rm[2]; 533 char errbuf[256]; 534 int eval; 535 struct val *v; 536 537 /* coerce both arguments to strings */ 538 to_string(a); 539 to_string(b); 540 541 /* compile regular expression */ 542 if ((eval = regcomp(&rp, b->u.s, 0)) != 0) { 543 regerror(eval, &rp, errbuf, sizeof(errbuf)); 544 errx(ERR_EXIT, "%s", errbuf); 545 } 546 547 /* compare string against pattern */ 548 /* remember that patterns are anchored to the beginning of the line */ 549 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) 550 if (rm[1].rm_so >= 0) { 551 *(a->u.s + rm[1].rm_eo) = '\0'; 552 v = make_str(a->u.s + rm[1].rm_so); 553#ifdef __APPLE__ 554 v->type = string; /* 8319378 */ 555#endif 556 557 } else 558 v = make_integer((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 559 else 560 if (rp.re_nsub == 0) 561 v = make_integer((intmax_t)0); 562 else 563 v = make_str(""); 564 565 /* free arguments and pattern buffer */ 566 free_value(a); 567 free_value(b); 568 regfree(&rp); 569 570 return (v); 571} 572