expr.y revision 223882
1193323Sed%{ 2193323Sed/*- 3193323Sed * Written by Pace Willisson (pace@blitz.com) 4193323Sed * and placed in the public domain. 5193323Sed * 6193323Sed * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 7193323Sed * 8193323Sed * $FreeBSD: head/bin/expr/expr.y 223882 2011-07-09 12:14:57Z se $ 9193323Sed */ 10193323Sed 11193323Sed#include <sys/types.h> 12193323Sed 13193323Sed#include <ctype.h> 14193323Sed#include <err.h> 15193323Sed#include <errno.h> 16193323Sed#include <inttypes.h> 17193323Sed#include <limits.h> 18193323Sed#include <locale.h> 19193323Sed#include <stdio.h> 20193323Sed#include <stdlib.h> 21193323Sed#include <string.h> 22249423Sdim#include <regex.h> 23198090Srdivacky#include <unistd.h> 24198090Srdivacky 25193323Sed/* 26193323Sed * POSIX specifies a specific error code for syntax errors. We exit 27193323Sed * with this code for all errors. 28193323Sed */ 29193323Sed#define ERR_EXIT 2 30193323Sed 31193323Sedenum valtype { 32193323Sed integer, numeric_string, string 33193323Sed} ; 34193323Sed 35193323Sedstruct val { 36202375Srdivacky enum valtype type; 37193323Sed union { 38193323Sed char *s; 39193323Sed intmax_t i; 40193323Sed } u; 41193323Sed} ; 42193323Sed 43193323Sedchar **av; 44193323Sedint nonposix; 45193323Sedstruct val *result; 46202375Srdivacky 47202375Srdivackyvoid assert_to_integer(struct val *); 48193323Sedvoid assert_div(intmax_t, intmax_t); 49198090Srdivackyvoid assert_minus(intmax_t, intmax_t, intmax_t); 50226633Sdimvoid assert_plus(intmax_t, intmax_t, intmax_t); 51193323Sedvoid assert_times(intmax_t, intmax_t, intmax_t); 52193323Sedint compare_vals(struct val *, struct val *); 53218893Sdimvoid free_value(struct val *); 54193323Sedint is_integer(const char *); 55193323Sedint isstring(struct val *); 56193323Sedint is_zero_or_null(struct val *); 57193323Sedstruct val *make_integer(intmax_t); 58193323Sedstruct val *make_str(const char *); 59234353Sdimstruct val *op_and(struct val *, struct val *); 60193323Sedstruct val *op_colon(struct val *, struct val *); 61193323Sedstruct val *op_div(struct val *, struct val *); 62234353Sdimstruct val *op_eq(struct val *, struct val *); 63193323Sedstruct val *op_ge(struct val *, struct val *); 64193323Sedstruct val *op_gt(struct val *, struct val *); 65193323Sedstruct val *op_le(struct val *, struct val *); 66193323Sedstruct val *op_lt(struct val *, struct val *); 67193323Sedstruct val *op_minus(struct val *, struct val *); 68226633Sdimstruct val *op_ne(struct val *, struct val *); 69193323Sedstruct val *op_or(struct val *, struct val *); 70193323Sedstruct val *op_plus(struct val *, struct val *); 71193323Sedstruct val *op_rem(struct val *, struct val *); 72193323Sedstruct val *op_times(struct val *, struct val *); 73193323Sedint to_integer(struct val *); 74193323Sedvoid to_string(struct val *); 75193323Sedint yyerror(const char *); 76193323Sedint yylex(void); 77193323Sedint yyparse(void); 78193323Sed 79193323Sed%} 80223017Sdim 81223017Sdim%union 82223017Sdim{ 83223017Sdim struct val *val; 84223017Sdim} 85223017Sdim 86223017Sdim%left <val> '|' 87223017Sdim%left <val> '&' 88223017Sdim%left <val> '=' '>' '<' GE LE NE 89223017Sdim%left <val> '+' '-' 90226633Sdim%left <val> '*' '/' '%' 91226633Sdim%left <val> ':' 92223017Sdim 93193323Sed%token <val> TOKEN 94193323Sed%type <val> start expr 95193323Sed 96193323Sed%% 97193323Sed 98193323Sedstart: expr { result = $$; } 99193323Sed 100205218Srdivackyexpr: TOKEN 101205218Srdivacky | '(' expr ')' { $$ = $2; } 102193323Sed | expr '|' expr { $$ = op_or ($1, $3); } 103193323Sed | expr '&' expr { $$ = op_and ($1, $3); } 104193323Sed | expr '=' expr { $$ = op_eq ($1, $3); } 105193323Sed | expr '>' expr { $$ = op_gt ($1, $3); } 106193323Sed | expr '<' expr { $$ = op_lt ($1, $3); } 107193323Sed | expr GE expr { $$ = op_ge ($1, $3); } 108193323Sed | expr LE expr { $$ = op_le ($1, $3); } 109193323Sed | expr NE expr { $$ = op_ne ($1, $3); } 110193323Sed | expr '+' expr { $$ = op_plus ($1, $3); } 111193323Sed | expr '-' expr { $$ = op_minus ($1, $3); } 112193323Sed | expr '*' expr { $$ = op_times ($1, $3); } 113193323Sed | expr '/' expr { $$ = op_div ($1, $3); } 114193323Sed | expr '%' expr { $$ = op_rem ($1, $3); } 115193323Sed | expr ':' expr { $$ = op_colon ($1, $3); } 116193323Sed ; 117193323Sed 118193323Sed 119193323Sed%% 120193323Sed 121193323Sedstruct val * 122226633Sdimmake_integer(intmax_t i) 123226633Sdim{ 124226633Sdim struct val *vp; 125193323Sed 126193323Sed vp = (struct val *) malloc (sizeof (*vp)); 127193323Sed if (vp == NULL) { 128193323Sed errx(ERR_EXIT, "malloc() failed"); 129193323Sed } 130193323Sed 131193323Sed vp->type = integer; 132193323Sed vp->u.i = i; 133193323Sed return vp; 134193323Sed} 135193323Sed 136193323Sedstruct val * 137193323Sedmake_str(const char *s) 138193323Sed{ 139193323Sed struct val *vp; 140193323Sed 141193323Sed vp = (struct val *) malloc (sizeof (*vp)); 142193323Sed if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) { 143193323Sed errx(ERR_EXIT, "malloc() failed"); 144193323Sed } 145193323Sed 146193323Sed if (is_integer(s)) 147226633Sdim vp->type = numeric_string; 148226633Sdim else 149226633Sdim vp->type = string; 150226633Sdim 151226633Sdim return vp; 152226633Sdim} 153193323Sed 154193323Sed 155193323Sedvoid 156263508Sdimfree_value(struct val *vp) 157193323Sed{ 158193323Sed if (vp->type == string || vp->type == numeric_string) 159193323Sed free (vp->u.s); 160193323Sed} 161193323Sed 162193323Sed 163263508Sdimint 164193323Sedto_integer(struct val *vp) 165193323Sed{ 166193323Sed intmax_t i; 167226633Sdim 168226633Sdim /* we can only convert numeric_string to integer, here */ 169263508Sdim if (vp->type == numeric_string) { 170226633Sdim errno = 0; 171226633Sdim i = strtoimax(vp->u.s, (char **)NULL, 10); 172226633Sdim /* just keep as numeric_string, if the conversion fails */ 173226633Sdim if (errno != ERANGE) { 174226633Sdim free (vp->u.s); 175226633Sdim vp->u.i = i; 176226633Sdim vp->type = integer; 177226633Sdim } 178226633Sdim } 179226633Sdim return (vp->type == integer); 180193323Sed} 181193323Sed 182263508Sdim 183193323Sedvoid 184193323Sedassert_to_integer(struct val *vp) 185226633Sdim{ 186226633Sdim if (vp->type == string) 187193323Sed errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s); 188193323Sed if (!to_integer(vp)) 189193323Sed errx(ERR_EXIT, "operand too large: '%s'", vp->u.s); 190193323Sed} 191193323Sed 192193323Sedvoid 193193323Sedto_string(struct val *vp) 194193323Sed{ 195193323Sed char *tmp; 196263508Sdim 197193323Sed if (vp->type == string || vp->type == numeric_string) 198226633Sdim return; 199226633Sdim 200193323Sed /* 201193323Sed * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 202193323Sed * of digits; add one each for the sign and terminating null 203193323Sed * character, respectively. 204193323Sed */ 205193323Sed#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 206218893Sdim tmp = malloc(NDIGITS(vp->u.i)); 207193323Sed if (tmp == NULL) 208198090Srdivacky errx(ERR_EXIT, "malloc() failed"); 209198090Srdivacky 210198090Srdivacky sprintf(tmp, "%jd", vp->u.i); 211198090Srdivacky vp->type = string; 212263508Sdim vp->u.s = tmp; 213193323Sed} 214193323Sed 215223017Sdim 216193323Sedint 217223017Sdimis_integer(const char *s) 218234353Sdim{ 219193323Sed if (nonposix) { 220218893Sdim if (*s == '\0') 221193323Sed return (1); 222223017Sdim while (isspace((unsigned char)*s)) 223193323Sed s++; 224193323Sed } 225223017Sdim if (*s == '-' || (nonposix && *s == '+')) 226223017Sdim s++; 227193323Sed if (*s == '\0') 228223017Sdim return (0); 229193323Sed while (isdigit((unsigned char)*s)) 230224145Sdim s++; 231224145Sdim return (*s == '\0'); 232224145Sdim} 233224145Sdim 234223017Sdim 235218893Sdimint 236193323Sedisstring(struct val *vp) 237193323Sed{ 238193323Sed /* only TRUE if this string is not a valid integer */ 239193323Sed return (vp->type == string); 240193323Sed} 241193323Sed 242193323Sed 243193323Sedint 244193323Sedyylex(void) 245193323Sed{ 246207618Srdivacky char *p; 247207618Srdivacky 248193323Sed if (*av == NULL) 249218893Sdim return (0); 250193323Sed 251223017Sdim p = *av++; 252234353Sdim 253234353Sdim if (strlen (p) == 1) { 254234353Sdim if (strchr ("|&=<>+-*/%:()", *p)) 255234353Sdim return (*p); 256234353Sdim } else if (strlen (p) == 2 && p[1] == '=') { 257193323Sed switch (*p) { 258193323Sed case '>': return (GE); 259198090Srdivacky case '<': return (LE); 260198090Srdivacky case '!': return (NE); 261193323Sed } 262193323Sed } 263193323Sed 264193323Sed yylval.val = make_str (p); 265198090Srdivacky return (TOKEN); 266198090Srdivacky} 267263508Sdim 268193323Sedint 269193323Sedis_zero_or_null(struct val *vp) 270193323Sed{ 271193323Sed if (vp->type == integer) { 272193323Sed return (vp->u.i == 0); 273193323Sed } else { 274193323Sed return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0)); 275193323Sed } 276193323Sed /* NOTREACHED */ 277263508Sdim} 278212904Sdim 279212904Sdimint 280212904Sdimmain(int argc, char *argv[]) 281193323Sed{ 282193323Sed int c; 283193323Sed 284198090Srdivacky setlocale (LC_ALL, ""); 285193323Sed if (getenv("EXPR_COMPAT") != NULL 286263508Sdim || check_utility_compat("expr")) { 287193323Sed av = argv + 1; 288193323Sed nonposix = 1; 289193323Sed } else { 290212904Sdim while ((c = getopt(argc, argv, "e")) != -1) 291212904Sdim switch (c) { 292193323Sed case 'e': 293193323Sed nonposix = 1; 294193323Sed break; 295193323Sed 296193323Sed default: 297193323Sed fprintf(stderr, 298193323Sed "usage: expr [-e] expression\n"); 299193323Sed exit(ERR_EXIT); 300193323Sed } 301193323Sed av = argv + optind; 302193323Sed } 303198090Srdivacky 304263508Sdim yyparse(); 305193323Sed 306193323Sed if (result->type == integer) 307193323Sed printf("%jd\n", result->u.i); 308193323Sed else 309193323Sed printf("%s\n", result->u.s); 310193323Sed 311193323Sed return (is_zero_or_null(result)); 312263508Sdim} 313198090Srdivacky 314198090Srdivackyint 315234353Sdimyyerror(const char *s __unused) 316193323Sed{ 317193323Sed errx(ERR_EXIT, "syntax error"); 318193323Sed} 319193323Sed 320193323Sed 321193323Sedstruct val * 322193323Sedop_or(struct val *a, struct val *b) 323193323Sed{ 324193323Sed if (!is_zero_or_null(a)) { 325263508Sdim free_value(b); 326193323Sed return (a); 327193323Sed } 328193323Sed free_value(a); 329193323Sed if (!is_zero_or_null(b)) 330198090Srdivacky return (b); 331198090Srdivacky free_value(b); 332263508Sdim return (make_integer((intmax_t)0)); 333234353Sdim} 334234353Sdim 335234353Sdimstruct val * 336234353Sdimop_and(struct val *a, struct val *b) 337234353Sdim{ 338234353Sdim if (is_zero_or_null (a) || is_zero_or_null (b)) { 339234353Sdim free_value (a); 340234353Sdim free_value (b); 341234353Sdim return (make_integer ((intmax_t)0)); 342193323Sed } else { 343193323Sed free_value (b); 344193323Sed return (a); 345263508Sdim } 346198090Srdivacky} 347198090Srdivacky 348198090Srdivackyint 349193323Sedcompare_vals(struct val *a, struct val *b) 350193323Sed{ 351193323Sed int r; 352198090Srdivacky 353193323Sed if (isstring(a) || isstring(b)) { 354263508Sdim to_string(a); 355193323Sed to_string(b); 356193574Sed r = strcoll(a->u.s, b->u.s); 357193574Sed } else { 358212904Sdim assert_to_integer(a); 359212904Sdim assert_to_integer(b); 360193323Sed if (a->u.i > b->u.i) 361193574Sed r = 1; 362193323Sed else if (a->u.i < b->u.i) 363193323Sed r = -1; 364193323Sed else 365193323Sed r = 0; 366193323Sed } 367193323Sed 368193323Sed free_value(a); 369193323Sed free_value(b); 370193323Sed return (r); 371224145Sdim} 372224145Sdim 373193323Sedstruct val * 374193323Sedop_eq(struct val *a, struct val *b) 375205218Srdivacky{ 376205218Srdivacky return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 377263508Sdim} 378205218Srdivacky 379205218Srdivackystruct val * 380205218Srdivackyop_gt(struct val *a, struct val *b) 381205218Srdivacky{ 382205218Srdivacky return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 383205218Srdivacky} 384205218Srdivacky 385193323Sedstruct val * 386198090Srdivackyop_lt(struct val *a, struct val *b) 387263508Sdim{ 388193323Sed return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 389223017Sdim} 390223017Sdim 391193323Sedstruct val * 392193323Sedop_ge(struct val *a, struct val *b) 393193323Sed{ 394193323Sed return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 395193323Sed} 396193323Sed 397193323Sedstruct val * 398193323Sedop_le(struct val *a, struct val *b) 399193323Sed{ 400193323Sed return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 401193323Sed} 402224145Sdim 403224145Sdimstruct val * 404193323Sedop_ne(struct val *a, struct val *b) 405193323Sed{ 406193323Sed return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 407193323Sed} 408193323Sed 409193323Sedvoid 410193323Sedassert_plus(intmax_t a, intmax_t b, intmax_t r) 411193323Sed{ 412193323Sed /* 413193323Sed * sum of two positive numbers must be positive, 414193323Sed * sum of two negative numbers must be negative 415198090Srdivacky */ 416193323Sed if ((a > 0 && b > 0 && r <= 0) || 417193323Sed (a < 0 && b < 0 && r >= 0)) 418263508Sdim errx(ERR_EXIT, "overflow"); 419218893Sdim} 420263508Sdim 421193323Sedstruct val * 422193323Sedop_plus(struct val *a, struct val *b) 423193323Sed{ 424193323Sed struct val *r; 425193323Sed 426193323Sed assert_to_integer(a); 427193323Sed assert_to_integer(b); 428193323Sed 429193323Sed r = make_integer(a->u.i + b->u.i); 430193323Sed assert_plus(a->u.i, b->u.i, r->u.i); 431198090Srdivacky 432198090Srdivacky free_value (a); 433193323Sed free_value (b); 434263508Sdim return r; 435193323Sed} 436193323Sed 437193323Sedvoid 438193323Sedassert_minus(intmax_t a, intmax_t b, intmax_t r) 439193323Sed{ 440193323Sed 441193323Sed /* special case subtraction of INTMAX_MIN */ 442193323Sed if (b == INTMAX_MIN && a < 0) 443193323Sed errx(ERR_EXIT, "overflow"); 444193323Sed /* check addition of negative subtrahend */ 445193323Sed assert_plus(a, -b, r); 446193323Sed} 447193323Sed 448193323Sedstruct val * 449193323Sedop_minus(struct val *a, struct val *b) 450193323Sed{ 451193323Sed struct val *r; 452198090Srdivacky 453198090Srdivacky assert_to_integer(a); 454263508Sdim assert_to_integer(b); 455193323Sed 456193323Sed r = make_integer(a->u.i - b->u.i); 457193323Sed assert_minus(a->u.i, b->u.i, r->u.i); 458193323Sed 459193323Sed free_value (a); 460193323Sed free_value (b); 461193323Sed return r; 462193323Sed} 463193323Sed 464193323Sedvoid 465193323Sedassert_times(intmax_t a, intmax_t b, intmax_t r) 466193323Sed{ 467193323Sed /* 468193323Sed * if first operand is 0, no overflow is possible, 469193323Sed * else result of division test must match second operand 470193323Sed */ 471193323Sed if (a != 0 && r / a != b) 472193323Sed errx(ERR_EXIT, "overflow"); 473193323Sed} 474193323Sed 475193323Sedstruct val * 476193323Sedop_times(struct val *a, struct val *b) 477263508Sdim{ 478193323Sed struct val *r; 479193323Sed 480193323Sed assert_to_integer(a); 481193323Sed assert_to_integer(b); 482193323Sed 483193323Sed r = make_integer(a->u.i * b->u.i); 484263508Sdim assert_times(a->u.i, b->u.i, r->u.i); 485263508Sdim 486193323Sed free_value (a); 487193323Sed free_value (b); 488226633Sdim return (r); 489234353Sdim} 490234353Sdim 491234353Sdimvoid 492234353Sdimassert_div(intmax_t a, intmax_t b) 493263508Sdim{ 494226633Sdim if (b == 0) 495226633Sdim errx(ERR_EXIT, "division by zero"); 496263508Sdim /* only INTMAX_MIN / -1 causes overflow */ 497226633Sdim if (a == INTMAX_MIN && b == -1) 498226633Sdim errx(ERR_EXIT, "overflow"); 499226633Sdim} 500193323Sed 501193323Sedstruct val * 502193323Sedop_div(struct val *a, struct val *b) 503263508Sdim{ 504193323Sed struct val *r; 505193323Sed 506193323Sed assert_to_integer(a); 507193323Sed assert_to_integer(b); 508193323Sed 509263508Sdim /* assert based on operands only, not on result */ 510226633Sdim assert_div(a->u.i, b->u.i); 511226633Sdim r = make_integer(a->u.i / b->u.i); 512226633Sdim 513226633Sdim free_value (a); 514226633Sdim free_value (b); 515226633Sdim return r; 516249423Sdim} 517226633Sdim 518263508Sdimstruct val * 519226633Sdimop_rem(struct val *a, struct val *b) 520226633Sdim{ 521193323Sed struct val *r; 522263508Sdim 523263508Sdim assert_to_integer(a); 524263508Sdim assert_to_integer(b); 525263508Sdim /* pass a=1 to only check for div by zero */ 526263508Sdim assert_div(1, b->u.i); 527263508Sdim r = make_integer(a->u.i % b->u.i); 528263508Sdim 529263508Sdim free_value (a); 530263508Sdim free_value (b); 531263508Sdim return r; 532263508Sdim} 533193323Sed 534263508Sdimstruct val * 535263508Sdimop_colon(struct val *a, struct val *b) 536193323Sed{ 537226633Sdim regex_t rp; 538193323Sed regmatch_t rm[2]; 539193323Sed char errbuf[256]; 540193323Sed int eval; 541193323Sed struct val *v; 542193323Sed 543249423Sdim /* coerce both arguments to strings */ 544249423Sdim to_string(a); 545249423Sdim to_string(b); 546263508Sdim 547193323Sed /* compile regular expression */ 548193323Sed if ((eval = regcomp (&rp, b->u.s, 0)) != 0) { 549193323Sed regerror (eval, &rp, errbuf, sizeof(errbuf)); 550193323Sed errx(ERR_EXIT, "%s", errbuf); 551263508Sdim } 552193323Sed 553193323Sed /* compare string against pattern */ 554193323Sed /* remember that patterns are anchored to the beginning of the line */ 555193323Sed if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) { 556193323Sed if (rm[1].rm_so >= 0) { 557193323Sed *(a->u.s + rm[1].rm_eo) = '\0'; 558193323Sed v = make_str (a->u.s + rm[1].rm_so); 559193323Sed 560193323Sed } else { 561263508Sdim v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 562249423Sdim } 563193323Sed } else { 564193323Sed if (rp.re_nsub == 0) { 565193323Sed v = make_integer ((intmax_t)0); 566193323Sed } else { 567193323Sed v = make_str (""); 568249423Sdim } 569249423Sdim } 570263508Sdim 571193323Sed /* free arguments and pattern buffer */ 572193323Sed free_value (a); 573193323Sed free_value (b); 574193323Sed regfree (&rp); 575193323Sed 576249423Sdim return v; 577249423Sdim} 578263508Sdim