expr.y revision 235771
1291333Sjkim%{ 2291333Sjkim/*- 3291333Sjkim * Written by Pace Willisson (pace@blitz.com) 4291333Sjkim * and placed in the public domain. 5291333Sjkim * 6291333Sjkim * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 7291333Sjkim * 8298714Sjkim * $FreeBSD: head/bin/expr/expr.y 235771 2012-05-22 03:01:54Z kevlo $ 9291333Sjkim */ 10291333Sjkim 11291333Sjkim#include <sys/types.h> 12291333Sjkim 13291333Sjkim#include <ctype.h> 14291333Sjkim#include <err.h> 15291333Sjkim#include <errno.h> 16291333Sjkim#include <inttypes.h> 17291333Sjkim#include <limits.h> 18291333Sjkim#include <locale.h> 19291333Sjkim#include <stdio.h> 20291333Sjkim#include <stdlib.h> 21291333Sjkim#include <string.h> 22291333Sjkim#include <regex.h> 23291333Sjkim#include <unistd.h> 24291333Sjkim 25291333Sjkim/* 26291333Sjkim * POSIX specifies a specific error code for syntax errors. We exit 27291333Sjkim * with this code for all errors. 28291333Sjkim */ 29291333Sjkim#define ERR_EXIT 2 30291333Sjkim 31291333Sjkimenum valtype { 32291333Sjkim integer, numeric_string, string 33291333Sjkim} ; 34291333Sjkim 35291333Sjkimstruct val { 36291333Sjkim enum valtype type; 37291333Sjkim union { 38291333Sjkim char *s; 39291333Sjkim intmax_t i; 40291333Sjkim } u; 41291333Sjkim} ; 42291333Sjkim 43291333Sjkimchar **av; 44291333Sjkimint nonposix; 45291333Sjkimstruct val *result; 46298714Sjkim 47298714Sjkimvoid assert_to_integer(struct val *); 48291333Sjkimvoid assert_div(intmax_t, intmax_t); 49291333Sjkimvoid assert_minus(intmax_t, intmax_t, intmax_t); 50291333Sjkimvoid assert_plus(intmax_t, intmax_t, intmax_t); 51291333Sjkimvoid assert_times(intmax_t, intmax_t, intmax_t); 52291333Sjkimint compare_vals(struct val *, struct val *); 53291333Sjkimvoid free_value(struct val *); 54291333Sjkimint is_integer(const char *); 55291333Sjkimint is_string(struct val *); 56291333Sjkimint is_zero_or_null(struct val *); 57291333Sjkimstruct val *make_integer(intmax_t); 58291333Sjkimstruct val *make_str(const char *); 59291333Sjkimstruct val *op_and(struct val *, struct val *); 60291333Sjkimstruct val *op_colon(struct val *, struct val *); 61291333Sjkimstruct val *op_div(struct val *, struct val *); 62291333Sjkimstruct val *op_eq(struct val *, struct val *); 63291333Sjkimstruct val *op_ge(struct val *, struct val *); 64291333Sjkimstruct val *op_gt(struct val *, struct val *); 65291333Sjkimstruct val *op_le(struct val *, struct val *); 66291333Sjkimstruct val *op_lt(struct val *, struct val *); 67291333Sjkimstruct val *op_minus(struct val *, struct val *); 68291333Sjkimstruct val *op_ne(struct val *, struct val *); 69291333Sjkimstruct val *op_or(struct val *, struct val *); 70291333Sjkimstruct val *op_plus(struct val *, struct val *); 71291333Sjkimstruct val *op_rem(struct val *, struct val *); 72291333Sjkimstruct val *op_times(struct val *, struct val *); 73291333Sjkimint to_integer(struct val *); 74291333Sjkimvoid to_string(struct val *); 75291333Sjkimint yyerror(const char *); 76291333Sjkimint yylex(void); 77291333Sjkim 78291333Sjkim%} 79291333Sjkim 80291333Sjkim%union 81291333Sjkim{ 82291333Sjkim struct val *val; 83291333Sjkim} 84291333Sjkim 85291333Sjkim%left <val> '|' 86291333Sjkim%left <val> '&' 87291333Sjkim%left <val> '=' '>' '<' GE LE NE 88291333Sjkim%left <val> '+' '-' 89291333Sjkim%left <val> '*' '/' '%' 90291333Sjkim%left <val> ':' 91291333Sjkim 92291333Sjkim%token <val> TOKEN 93291333Sjkim%type <val> start expr 94291333Sjkim 95291333Sjkim%% 96291333Sjkim 97291333Sjkimstart: expr { result = $$; } 98291333Sjkim 99291333Sjkimexpr: TOKEN 100291333Sjkim | '(' expr ')' { $$ = $2; } 101291333Sjkim | expr '|' expr { $$ = op_or($1, $3); } 102291333Sjkim | expr '&' expr { $$ = op_and($1, $3); } 103291333Sjkim | expr '=' expr { $$ = op_eq($1, $3); } 104291333Sjkim | expr '>' expr { $$ = op_gt($1, $3); } 105291333Sjkim | expr '<' expr { $$ = op_lt($1, $3); } 106291333Sjkim | expr GE expr { $$ = op_ge($1, $3); } 107291333Sjkim | expr LE expr { $$ = op_le($1, $3); } 108291333Sjkim | expr NE expr { $$ = op_ne($1, $3); } 109291333Sjkim | expr '+' expr { $$ = op_plus($1, $3); } 110291333Sjkim | expr '-' expr { $$ = op_minus($1, $3); } 111291333Sjkim | expr '*' expr { $$ = op_times($1, $3); } 112291333Sjkim | expr '/' expr { $$ = op_div($1, $3); } 113291333Sjkim | expr '%' expr { $$ = op_rem($1, $3); } 114291333Sjkim | expr ':' expr { $$ = op_colon($1, $3); } 115291333Sjkim ; 116291333Sjkim 117291333Sjkim%% 118291333Sjkim 119291333Sjkimstruct val * 120291333Sjkimmake_integer(intmax_t i) 121291333Sjkim{ 122291333Sjkim struct val *vp; 123291333Sjkim 124291333Sjkim vp = (struct val *)malloc(sizeof(*vp)); 125291333Sjkim if (vp == NULL) 126291333Sjkim errx(ERR_EXIT, "malloc() failed"); 127291333Sjkim 128291333Sjkim vp->type = integer; 129291333Sjkim vp->u.i = i; 130291333Sjkim return (vp); 131291333Sjkim} 132291333Sjkim 133291333Sjkimstruct val * 134291333Sjkimmake_str(const char *s) 135291333Sjkim{ 136291333Sjkim struct val *vp; 137291333Sjkim 138291333Sjkim vp = (struct val *)malloc(sizeof(*vp)); 139291333Sjkim if (vp == NULL || ((vp->u.s = strdup(s)) == NULL)) 140291333Sjkim errx(ERR_EXIT, "malloc() failed"); 141291333Sjkim 142291333Sjkim if (is_integer(s)) 143291333Sjkim vp->type = numeric_string; 144291333Sjkim else 145291333Sjkim vp->type = string; 146291333Sjkim 147291333Sjkim return (vp); 148291333Sjkim} 149291333Sjkim 150291333Sjkimvoid 151291333Sjkimfree_value(struct val *vp) 152291333Sjkim{ 153291333Sjkim if (vp->type == string || vp->type == numeric_string) 154291333Sjkim free(vp->u.s); 155291333Sjkim} 156291333Sjkim 157291333Sjkimint 158291333Sjkimto_integer(struct val *vp) 159291333Sjkim{ 160291333Sjkim intmax_t i; 161291333Sjkim 162291333Sjkim /* we can only convert numeric_string to integer, here */ 163291333Sjkim if (vp->type == numeric_string) { 164291333Sjkim errno = 0; 165291333Sjkim i = strtoimax(vp->u.s, (char **)NULL, 10); 166291333Sjkim /* just keep as numeric_string, if the conversion fails */ 167291333Sjkim if (errno != ERANGE) { 168291333Sjkim free(vp->u.s); 169291333Sjkim vp->u.i = i; 170291333Sjkim vp->type = integer; 171291333Sjkim } 172291333Sjkim } 173291333Sjkim return (vp->type == integer); 174291333Sjkim} 175291333Sjkim 176291333Sjkimvoid 177291333Sjkimassert_to_integer(struct val *vp) 178291333Sjkim{ 179291333Sjkim if (vp->type == string) 180291333Sjkim errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s); 181291333Sjkim if (!to_integer(vp)) 182291333Sjkim errx(ERR_EXIT, "operand too large: '%s'", vp->u.s); 183291333Sjkim} 184291333Sjkim 185291333Sjkimvoid 186291333Sjkimto_string(struct val *vp) 187291333Sjkim{ 188291333Sjkim char *tmp; 189291333Sjkim 190291333Sjkim if (vp->type == string || vp->type == numeric_string) 191291333Sjkim return; 192291333Sjkim 193291333Sjkim /* 194291333Sjkim * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 195291333Sjkim * of digits; add one each for the sign and terminating null 196291333Sjkim * character, respectively. 197291333Sjkim */ 198291333Sjkim#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 199291333Sjkim tmp = malloc(NDIGITS(vp->u.i)); 200291333Sjkim if (tmp == NULL) 201291333Sjkim errx(ERR_EXIT, "malloc() failed"); 202291333Sjkim 203291333Sjkim sprintf(tmp, "%jd", vp->u.i); 204291333Sjkim vp->type = string; 205291333Sjkim vp->u.s = tmp; 206291333Sjkim} 207291333Sjkim 208291333Sjkimint 209291333Sjkimis_integer(const char *s) 210291333Sjkim{ 211291333Sjkim if (nonposix) { 212291333Sjkim if (*s == '\0') 213291333Sjkim return (1); 214291333Sjkim while (isspace((unsigned char)*s)) 215291333Sjkim s++; 216291333Sjkim } 217291333Sjkim if (*s == '-' || (nonposix && *s == '+')) 218291333Sjkim s++; 219291333Sjkim if (*s == '\0') 220291333Sjkim return (0); 221291333Sjkim while (isdigit((unsigned char)*s)) 222291333Sjkim s++; 223291333Sjkim return (*s == '\0'); 224291333Sjkim} 225291333Sjkim 226291333Sjkimint 227291333Sjkimis_string(struct val *vp) 228291333Sjkim{ 229291333Sjkim /* only TRUE if this string is not a valid integer */ 230291333Sjkim return (vp->type == string); 231291333Sjkim} 232291333Sjkim 233291333Sjkimint 234291333Sjkimyylex(void) 235291333Sjkim{ 236291333Sjkim char *p; 237291333Sjkim 238291333Sjkim if (*av == NULL) 239291333Sjkim return (0); 240291333Sjkim 241291333Sjkim p = *av++; 242291333Sjkim 243291333Sjkim if (strlen(p) == 1) { 244291333Sjkim if (strchr("|&=<>+-*/%:()", *p)) 245291333Sjkim return (*p); 246291333Sjkim } else if (strlen(p) == 2 && p[1] == '=') { 247291333Sjkim switch (*p) { 248291333Sjkim case '>': return (GE); 249291333Sjkim case '<': return (LE); 250291333Sjkim case '!': return (NE); 251291333Sjkim } 252291333Sjkim } 253291333Sjkim 254291333Sjkim yylval.val = make_str(p); 255291333Sjkim return (TOKEN); 256291333Sjkim} 257291333Sjkim 258291333Sjkimint 259291333Sjkimis_zero_or_null(struct val *vp) 260291333Sjkim{ 261291333Sjkim if (vp->type == integer) 262291333Sjkim return (vp->u.i == 0); 263291333Sjkim 264291333Sjkim return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0)); 265291333Sjkim} 266291333Sjkim 267291333Sjkimint 268291333Sjkimmain(int argc, char *argv[]) 269291333Sjkim{ 270291333Sjkim int c; 271291333Sjkim 272291333Sjkim setlocale(LC_ALL, ""); 273291333Sjkim if (getenv("EXPR_COMPAT") != NULL 274291333Sjkim || check_utility_compat("expr")) { 275291333Sjkim av = argv + 1; 276291333Sjkim nonposix = 1; 277291333Sjkim } else { 278291333Sjkim while ((c = getopt(argc, argv, "e")) != -1) { 279291333Sjkim switch (c) { 280291333Sjkim case 'e': 281291333Sjkim nonposix = 1; 282291333Sjkim break; 283291333Sjkim default: 284291333Sjkim errx(ERR_EXIT, 285291333Sjkim "usage: expr [-e] expression\n"); 286291333Sjkim } 287291333Sjkim } 288291333Sjkim av = argv + optind; 289291333Sjkim } 290291333Sjkim 291291333Sjkim yyparse(); 292291333Sjkim 293291333Sjkim if (result->type == integer) 294291333Sjkim printf("%jd\n", result->u.i); 295291333Sjkim else 296291333Sjkim printf("%s\n", result->u.s); 297291333Sjkim 298291333Sjkim return (is_zero_or_null(result)); 299291333Sjkim} 300291333Sjkim 301291333Sjkimint 302291333Sjkimyyerror(const char *s __unused) 303291333Sjkim{ 304291333Sjkim errx(ERR_EXIT, "syntax error"); 305291333Sjkim} 306291333Sjkim 307291333Sjkimstruct val * 308291333Sjkimop_or(struct val *a, struct val *b) 309291333Sjkim{ 310291333Sjkim if (!is_zero_or_null(a)) { 311291333Sjkim free_value(b); 312291333Sjkim return (a); 313291333Sjkim } 314291333Sjkim free_value(a); 315291333Sjkim if (!is_zero_or_null(b)) 316291333Sjkim return (b); 317291333Sjkim free_value(b); 318291333Sjkim return (make_integer((intmax_t)0)); 319291333Sjkim} 320291333Sjkim 321291333Sjkimstruct val * 322291333Sjkimop_and(struct val *a, struct val *b) 323291333Sjkim{ 324291333Sjkim if (is_zero_or_null(a) || is_zero_or_null(b)) { 325291333Sjkim free_value(a); 326291333Sjkim free_value(b); 327291333Sjkim return (make_integer((intmax_t)0)); 328291333Sjkim } else { 329291333Sjkim free_value(b); 330291333Sjkim return (a); 331291333Sjkim } 332291333Sjkim} 333291333Sjkim 334291333Sjkimint 335291333Sjkimcompare_vals(struct val *a, struct val *b) 336291333Sjkim{ 337291333Sjkim int r; 338291333Sjkim 339291333Sjkim if (is_string(a) || is_string(b)) { 340291333Sjkim to_string(a); 341291333Sjkim to_string(b); 342291333Sjkim r = strcoll(a->u.s, b->u.s); 343291333Sjkim } else { 344291333Sjkim assert_to_integer(a); 345291333Sjkim assert_to_integer(b); 346291333Sjkim if (a->u.i > b->u.i) 347291333Sjkim r = 1; 348291333Sjkim else if (a->u.i < b->u.i) 349291333Sjkim r = -1; 350291333Sjkim else 351291333Sjkim r = 0; 352291333Sjkim } 353291333Sjkim 354291333Sjkim free_value(a); 355291333Sjkim free_value(b); 356291333Sjkim return (r); 357291333Sjkim} 358291333Sjkim 359291333Sjkimstruct val * 360291333Sjkimop_eq(struct val *a, struct val *b) 361291333Sjkim{ 362291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 363291333Sjkim} 364291333Sjkim 365291333Sjkimstruct val * 366291333Sjkimop_gt(struct val *a, struct val *b) 367291333Sjkim{ 368291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 369291333Sjkim} 370291333Sjkim 371291333Sjkimstruct val * 372291333Sjkimop_lt(struct val *a, struct val *b) 373291333Sjkim{ 374291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 375291333Sjkim} 376291333Sjkim 377291333Sjkimstruct val * 378291333Sjkimop_ge(struct val *a, struct val *b) 379291333Sjkim{ 380291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 381291333Sjkim} 382291333Sjkim 383291333Sjkimstruct val * 384291333Sjkimop_le(struct val *a, struct val *b) 385291333Sjkim{ 386291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 387291333Sjkim} 388291333Sjkim 389291333Sjkimstruct val * 390291333Sjkimop_ne(struct val *a, struct val *b) 391291333Sjkim{ 392291333Sjkim return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 393291333Sjkim} 394291333Sjkim 395291333Sjkimvoid 396291333Sjkimassert_plus(intmax_t a, intmax_t b, intmax_t r) 397291333Sjkim{ 398291333Sjkim /* 399291333Sjkim * sum of two positive numbers must be positive, 400291333Sjkim * sum of two negative numbers must be negative 401291333Sjkim */ 402291333Sjkim if ((a > 0 && b > 0 && r <= 0) || 403291333Sjkim (a < 0 && b < 0 && r >= 0)) 404291333Sjkim errx(ERR_EXIT, "overflow"); 405291333Sjkim} 406291333Sjkim 407291333Sjkimstruct val * 408291333Sjkimop_plus(struct val *a, struct val *b) 409291333Sjkim{ 410291333Sjkim struct val *r; 411291333Sjkim 412291333Sjkim assert_to_integer(a); 413291333Sjkim assert_to_integer(b); 414291333Sjkim r = make_integer(a->u.i + b->u.i); 415291333Sjkim assert_plus(a->u.i, b->u.i, r->u.i); 416291333Sjkim 417291333Sjkim free_value(a); 418291333Sjkim free_value(b); 419291333Sjkim return (r); 420291333Sjkim} 421291333Sjkim 422291333Sjkimvoid 423291333Sjkimassert_minus(intmax_t a, intmax_t b, intmax_t r) 424291333Sjkim{ 425291333Sjkim /* special case subtraction of INTMAX_MIN */ 426291333Sjkim if (b == INTMAX_MIN && a < 0) 427291333Sjkim errx(ERR_EXIT, "overflow"); 428291333Sjkim /* check addition of negative subtrahend */ 429291333Sjkim assert_plus(a, -b, r); 430291333Sjkim} 431291333Sjkim 432291333Sjkimstruct val * 433291333Sjkimop_minus(struct val *a, struct val *b) 434291333Sjkim{ 435291333Sjkim struct val *r; 436291333Sjkim 437291333Sjkim assert_to_integer(a); 438291333Sjkim assert_to_integer(b); 439291333Sjkim r = make_integer(a->u.i - b->u.i); 440291333Sjkim assert_minus(a->u.i, b->u.i, r->u.i); 441291333Sjkim 442291333Sjkim free_value(a); 443291333Sjkim free_value(b); 444291333Sjkim return (r); 445291333Sjkim} 446291333Sjkim 447291333Sjkimvoid 448291333Sjkimassert_times(intmax_t a, intmax_t b, intmax_t r) 449291333Sjkim{ 450291333Sjkim /* 451291333Sjkim * if first operand is 0, no overflow is possible, 452291333Sjkim * else result of division test must match second operand 453291333Sjkim */ 454291333Sjkim if (a != 0 && r / a != b) 455291333Sjkim errx(ERR_EXIT, "overflow"); 456291333Sjkim} 457291333Sjkim 458291333Sjkimstruct val * 459291333Sjkimop_times(struct val *a, struct val *b) 460291333Sjkim{ 461291333Sjkim struct val *r; 462291333Sjkim 463291333Sjkim assert_to_integer(a); 464291333Sjkim assert_to_integer(b); 465291333Sjkim r = make_integer(a->u.i * b->u.i); 466291333Sjkim assert_times(a->u.i, b->u.i, r->u.i); 467291333Sjkim 468291333Sjkim free_value(a); 469291333Sjkim free_value(b); 470291333Sjkim return (r); 471291333Sjkim} 472291333Sjkim 473291333Sjkimvoid 474291333Sjkimassert_div(intmax_t a, intmax_t b) 475291333Sjkim{ 476291333Sjkim if (b == 0) 477291333Sjkim errx(ERR_EXIT, "division by zero"); 478291333Sjkim /* only INTMAX_MIN / -1 causes overflow */ 479291333Sjkim if (a == INTMAX_MIN && b == -1) 480291333Sjkim errx(ERR_EXIT, "overflow"); 481291333Sjkim} 482291333Sjkim 483291333Sjkimstruct val * 484291333Sjkimop_div(struct val *a, struct val *b) 485291333Sjkim{ 486291333Sjkim struct val *r; 487291333Sjkim 488291333Sjkim assert_to_integer(a); 489291333Sjkim assert_to_integer(b); 490291333Sjkim /* assert based on operands only, not on result */ 491291333Sjkim assert_div(a->u.i, b->u.i); 492291333Sjkim r = make_integer(a->u.i / b->u.i); 493291333Sjkim 494291333Sjkim free_value(a); 495291333Sjkim free_value(b); 496291333Sjkim return (r); 497291333Sjkim} 498291333Sjkim 499291333Sjkimstruct val * 500291333Sjkimop_rem(struct val *a, struct val *b) 501291333Sjkim{ 502291333Sjkim struct val *r; 503291333Sjkim 504291333Sjkim assert_to_integer(a); 505291333Sjkim assert_to_integer(b); 506291333Sjkim /* pass a=1 to only check for div by zero */ 507291333Sjkim assert_div(1, b->u.i); 508291333Sjkim r = make_integer(a->u.i % b->u.i); 509291333Sjkim 510291333Sjkim free_value(a); 511291333Sjkim free_value(b); 512291333Sjkim return (r); 513291333Sjkim} 514291333Sjkim 515291333Sjkimstruct val * 516291333Sjkimop_colon(struct val *a, struct val *b) 517291333Sjkim{ 518291333Sjkim regex_t rp; 519291333Sjkim regmatch_t rm[2]; 520291333Sjkim char errbuf[256]; 521291333Sjkim int eval; 522291333Sjkim struct val *v; 523291333Sjkim 524291333Sjkim /* coerce both arguments to strings */ 525291333Sjkim to_string(a); 526291333Sjkim to_string(b); 527291333Sjkim 528291333Sjkim /* compile regular expression */ 529291333Sjkim if ((eval = regcomp(&rp, b->u.s, 0)) != 0) { 530291333Sjkim regerror(eval, &rp, errbuf, sizeof(errbuf)); 531291333Sjkim errx(ERR_EXIT, "%s", errbuf); 532291333Sjkim } 533291333Sjkim 534291333Sjkim /* compare string against pattern */ 535291333Sjkim /* remember that patterns are anchored to the beginning of the line */ 536291333Sjkim if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) 537291333Sjkim if (rm[1].rm_so >= 0) { 538291333Sjkim *(a->u.s + rm[1].rm_eo) = '\0'; 539291333Sjkim v = make_str(a->u.s + rm[1].rm_so); 540291333Sjkim 541291333Sjkim } else 542291333Sjkim v = make_integer((intmax_t)(rm[0].rm_eo)); 543291333Sjkim else 544291333Sjkim if (rp.re_nsub == 0) 545291333Sjkim v = make_integer((intmax_t)0); 546291333Sjkim else 547291333Sjkim v = make_str(""); 548291333Sjkim 549291333Sjkim /* free arguments and pattern buffer */ 550291333Sjkim free_value(a); 551291333Sjkim free_value(b); 552291333Sjkim regfree(&rp); 553291333Sjkim 554291333Sjkim return (v); 555291333Sjkim} 556291333Sjkim