bin/expr/expr.y

   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 struct val *result;
  44
  45 int             chk_div(intmax_t, intmax_t);
  46 int             chk_minus(intmax_t, intmax_t, intmax_t);
  47 int             chk_plus(intmax_t, intmax_t, intmax_t);
  48 int             chk_times(intmax_t, intmax_t, intmax_t);
  49 void            free_value(struct val *);
  50 int             is_zero_or_null(struct val *);
  51 int             isstring(struct val *);
  52 struct val      *make_integer(intmax_t);
  53 struct val      *make_str(const char *);
  54 struct val      *op_and(struct val *, struct val *);
  55 struct val      *op_colon(struct val *, struct val *);
  56 struct val      *op_div(struct val *, struct val *);
  57 struct val      *op_eq(struct val *, struct val *);
  58 struct val      *op_ge(struct val *, struct val *);
  59 struct val      *op_gt(struct val *, struct val *);
  60 struct val      *op_le(struct val *, struct val *);
  61 struct val      *op_lt(struct val *, struct val *);
  62 struct val      *op_minus(struct val *, struct val *);
  63 struct val      *op_ne(struct val *, struct val *);
  64 struct val      *op_or(struct val *, struct val *);
  65 struct val      *op_plus(struct val *, struct val *);
  66 struct val      *op_rem(struct val *, struct val *);
  67 struct val      *op_times(struct val *, struct val *);
  68 intmax_t        to_integer(struct val *);
  69 void            to_string(struct val *);
  70 int             yyerror(const char *);
  71 int             yylex(void);
  72 int             yyparse(void);
  73
  74 static int      eflag;
  75 char **av;
  76 %}
  77
  78 %union
  79 {
  80         struct val *val;
  81 }
  82
  83 %left <val> '|'
  84 %left <val> '&'
  85 %left <val> '=' '>' '<' GE LE NE
  86 %left <val> '+' '-'
  87 %left <val> '*' '/' '%'
  88 %left <val> ':'
  89
  90 %token <val> TOKEN
  91 %type <val> start expr
  92
  93 %%
  94
  95 start: expr { result = $$; }
  96
  97 expr:   TOKEN
  98         | '(' expr ')' { $$ = $2; }
  99         | expr '|' expr { $$ = op_or ($1, $3); }
 100         | expr '&' expr { $$ = op_and ($1, $3); }
 101         | expr '=' expr { $$ = op_eq ($1, $3); }
 102         | expr '>' expr { $$ = op_gt ($1, $3); }
 103         | expr '<' expr { $$ = op_lt ($1, $3); }
 104         | expr GE expr  { $$ = op_ge ($1, $3); }
 105         | expr LE expr  { $$ = op_le ($1, $3); }
 106         | expr NE expr  { $$ = op_ne ($1, $3); }
 107         | expr '+' expr { $$ = op_plus ($1, $3); }
 108         | expr '-' expr { $$ = op_minus ($1, $3); }
 109         | expr '*' expr { $$ = op_times ($1, $3); }
 110         | expr '/' expr { $$ = op_div ($1, $3); }
 111         | expr '%' expr { $$ = op_rem ($1, $3); }
 112         | expr ':' expr { $$ = op_colon ($1, $3); }
 113         ;
 114
 115
 116 %%
 117
 118 struct val *
 119 make_integer(intmax_t i)
 120 {
 121         struct val *vp;
 122
 123         vp = (struct val *) malloc (sizeof (*vp));
 124         if (vp == NULL) {
 125                 errx(ERR_EXIT, "malloc() failed");
 126         }
 127
 128         vp->type = integer;
 129         vp->u.i  = i;
 130         return vp;
 131 }
 132
 133 struct val *
 134 make_str(const char *s)
 135 {
 136         struct val *vp;
 137         char *ep;
 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
 144         /*
 145          * Previously we tried to scan the string to see if it ``looked like''
 146          * an integer (erroneously, as it happened).  Let strtoimax() do the
 147          * dirty work.  We could cache the value, except that we are using
 148          * a union and need to preserve the original string form until we
 149          * are certain that it is not needed.
 150          *
 151          * IEEE Std.1003.1-2001 says:
 152          * /integer/ An argument consisting only of an (optional) unary minus
 153          *           followed by digits.
 154          *
 155          * This means that arguments which consist of digits followed by
 156          * non-digits MUST NOT be considered integers.  strtoimax() will
 157          * figure this out for us.
 158          */
 159         if (eflag)
 160                 (void)strtoimax(s, &ep, 10);
 161         else
 162                 (void)strtol(s, &ep, 10);
 163
 164         if (*ep != '\0')
 165                 vp->type = string;
 166         else
 167                 vp->type = numeric_string;
 168
 169         return vp;
 170 }
 171
 172
 173 void
 174 free_value(struct val *vp)
 175 {
 176         if (vp->type == string || vp->type == numeric_string)
 177                 free (vp->u.s);
 178 }
 179
 180
 181 intmax_t
 182 to_integer(struct val *vp)
 183 {
 184         intmax_t i;
 185
 186         if (vp->type == integer)
 187                 return 1;
 188
 189         if (vp->type == string)
 190                 return 0;
 191
 192         /* vp->type == numeric_string, make it numeric */
 193         errno = 0;
 194         if (eflag) {
 195                 i  = strtoimax(vp->u.s, (char **)NULL, 10);
 196                 if (errno == ERANGE)
 197                         err(ERR_EXIT, NULL);
 198         } else {
 199                 i = strtol(vp->u.s, (char **)NULL, 10);
 200         }
 201
 202         free (vp->u.s);
 203         vp->u.i = i;
 204         vp->type = integer;
 205         return 1;
 206 }
 207
 208 void
 209 to_string(struct val *vp)
 210 {
 211         char *tmp;
 212
 213         if (vp->type == string || vp->type == numeric_string)
 214                 return;
 215
 216         /*
 217          * log_10(x) ~= 0.3 * log_2(x).  Rounding up gives the number
 218          * of digits; add one each for the sign and terminating null
 219          * character, respectively.
 220          */
 221 #define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1)
 222         tmp = malloc(NDIGITS(vp->u.i));
 223         if (tmp == NULL)
 224                 errx(ERR_EXIT, "malloc() failed");
 225
 226         sprintf(tmp, "%jd", vp->u.i);
 227         vp->type = string;
 228         vp->u.s  = tmp;
 229 }
 230
 231
 232 int
 233 isstring(struct val *vp)
 234 {
 235         /* only TRUE if this string is not a valid integer */
 236         return (vp->type == string);
 237 }
 238
 239
 240 int
 241 yylex(void)
 242 {
 243         char *p;
 244
 245         if (*av == NULL)
 246                 return (0);
 247
 248         p = *av++;
 249
 250         if (strlen (p) == 1) {
 251                 if (strchr ("|&=<>+-*/%:()", *p))
 252                         return (*p);
 253         } else if (strlen (p) == 2 && p[1] == '=') {
 254                 switch (*p) {
 255                 case '>': return (GE);
 256                 case '<': return (LE);
 257                 case '!': return (NE);
 258                 }
 259         }
 260
 261         yylval.val = make_str (p);
 262         return (TOKEN);
 263 }
 264
 265 int
 266 is_zero_or_null(struct val *vp)
 267 {
 268         if (vp->type == integer) {
 269                 return (vp->u.i == 0);
 270         } else {
 271                 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0));
 272         }
 273         /* NOTREACHED */
 274 }
 275
 276 int
 277 main(int argc, char *argv[])
 278 {
 279         int c;
 280
 281         setlocale (LC_ALL, "");
 282         if (getenv("EXPR_COMPAT") != NULL
 283             || check_utility_compat("expr")) {
 284                 av = argv + 1;
 285                 eflag = 1;
 286         } else {
 287                 while ((c = getopt(argc, argv, "e")) != -1)
 288                         switch (c) {
 289                         case 'e':
 290                                 eflag = 1;
 291                                 break;
 292
 293                         default:
 294                                 fprintf(stderr,
 295                                     "usage: expr [-e] expression\n");
 296                                 exit(ERR_EXIT);
 297                         }
 298                 av = argv + optind;
 299         }
 300
 301         yyparse();
 302
 303         if (result->type == integer)
 304                 printf("%jd\n", result->u.i);
 305         else
 306                 printf("%s\n", result->u.s);
 307
 308         return (is_zero_or_null(result));
 309 }
 310
 311 int
 312 yyerror(const char *s __unused)
 313 {
 314         errx(ERR_EXIT, "syntax error");
 315 }
 316
 317
 318 struct val *
 319 op_or(struct val *a, struct val *b)
 320 {
 321         if (is_zero_or_null (a)) {
 322                 free_value (a);
 323                 return (b);
 324         } else {
 325                 free_value (b);
 326                 return (a);
 327         }
 328 }
 329
 330 struct val *
 331 op_and(struct val *a, struct val *b)
 332 {
 333         if (is_zero_or_null (a) || is_zero_or_null (b)) {
 334                 free_value (a);
 335                 free_value (b);
 336                 return (make_integer ((intmax_t)0));
 337         } else {
 338                 free_value (b);
 339                 return (a);
 340         }
 341 }
 342
 343 struct val *
 344 op_eq(struct val *a, struct val *b)
 345 {
 346         struct val *r;
 347
 348         if (isstring (a) || isstring (b)) {
 349                 to_string (a);
 350                 to_string (b);
 351                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) == 0));
 352         } else {
 353                 (void)to_integer(a);
 354                 (void)to_integer(b);
 355                 r = make_integer ((intmax_t)(a->u.i == b->u.i));
 356         }
 357
 358         free_value (a);
 359         free_value (b);
 360         return r;
 361 }
 362
 363 struct val *
 364 op_gt(struct val *a, struct val *b)
 365 {
 366         struct val *r;
 367
 368         if (isstring (a) || isstring (b)) {
 369                 to_string (a);
 370                 to_string (b);
 371                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) > 0));
 372         } else {
 373                 (void)to_integer(a);
 374                 (void)to_integer(b);
 375                 r = make_integer ((intmax_t)(a->u.i > b->u.i));
 376         }
 377
 378         free_value (a);
 379         free_value (b);
 380         return r;
 381 }
 382
 383 struct val *
 384 op_lt(struct val *a, struct val *b)
 385 {
 386         struct val *r;
 387
 388         if (isstring (a) || isstring (b)) {
 389                 to_string (a);
 390                 to_string (b);
 391                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) < 0));
 392         } else {
 393                 (void)to_integer(a);
 394                 (void)to_integer(b);
 395                 r = make_integer ((intmax_t)(a->u.i < b->u.i));
 396         }
 397
 398         free_value (a);
 399         free_value (b);
 400         return r;
 401 }
 402
 403 struct val *
 404 op_ge(struct val *a, struct val *b)
 405 {
 406         struct val *r;
 407
 408         if (isstring (a) || isstring (b)) {
 409                 to_string (a);
 410                 to_string (b);
 411                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) >= 0));
 412         } else {
 413                 (void)to_integer(a);
 414                 (void)to_integer(b);
 415                 r = make_integer ((intmax_t)(a->u.i >= b->u.i));
 416         }
 417
 418         free_value (a);
 419         free_value (b);
 420         return r;
 421 }
 422
 423 struct val *
 424 op_le(struct val *a, struct val *b)
 425 {
 426         struct val *r;
 427
 428         if (isstring (a) || isstring (b)) {
 429                 to_string (a);
 430                 to_string (b);
 431                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) <= 0));
 432         } else {
 433                 (void)to_integer(a);
 434                 (void)to_integer(b);
 435                 r = make_integer ((intmax_t)(a->u.i <= b->u.i));
 436         }
 437
 438         free_value (a);
 439         free_value (b);
 440         return r;
 441 }
 442
 443 struct val *
 444 op_ne(struct val *a, struct val *b)
 445 {
 446         struct val *r;
 447
 448         if (isstring (a) || isstring (b)) {
 449                 to_string (a);
 450                 to_string (b);
 451                 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) != 0));
 452         } else {
 453                 (void)to_integer(a);
 454                 (void)to_integer(b);
 455                 r = make_integer ((intmax_t)(a->u.i != b->u.i));
 456         }
 457
 458         free_value (a);
 459         free_value (b);
 460         return r;
 461 }
 462
 463 int
 464 chk_plus(intmax_t a, intmax_t b, intmax_t r)
 465 {
 466
 467         /* sum of two positive numbers must be positive */
 468         if (a > 0 && b > 0 && r <= 0)
 469                 return 1;
 470         /* sum of two negative numbers must be negative */
 471         if (a < 0 && b < 0 && r >= 0)
 472                 return 1;
 473         /* all other cases are OK */
 474         return 0;
 475 }
 476
 477 struct val *
 478 op_plus(struct val *a, struct val *b)
 479 {
 480         struct val *r;
 481
 482         if (!to_integer(a) || !to_integer(b)) {
 483                 errx(ERR_EXIT, "non-numeric argument");
 484         }
 485
 486         if (eflag) {
 487                 r = make_integer(a->u.i + b->u.i);
 488                 if (chk_plus(a->u.i, b->u.i, r->u.i)) {
 489                         errx(ERR_EXIT, "overflow");
 490                 }
 491         } else
 492                 r = make_integer((long)a->u.i + (long)b->u.i);
 493
 494         free_value (a);
 495         free_value (b);
 496         return r;
 497 }
 498
 499 int
 500 chk_minus(intmax_t a, intmax_t b, intmax_t r)
 501 {
 502
 503         /* special case subtraction of INTMAX_MIN */
 504         if (b == INTMAX_MIN) {
 505                 if (a >= 0)
 506                         return 1;
 507                 else
 508                         return 0;
 509         }
 510         /* this is allowed for b != INTMAX_MIN */
 511         return chk_plus (a, -b, r);
 512 }
 513
 514 struct val *
 515 op_minus(struct val *a, struct val *b)
 516 {
 517         struct val *r;
 518
 519         if (!to_integer(a) || !to_integer(b)) {
 520                 errx(ERR_EXIT, "non-numeric argument");
 521         }
 522
 523         if (eflag) {
 524                 r = make_integer(a->u.i - b->u.i);
 525                 if (chk_minus(a->u.i, b->u.i, r->u.i)) {
 526                         errx(ERR_EXIT, "overflow");
 527                 }
 528         } else
 529                 r = make_integer((long)a->u.i - (long)b->u.i);
 530
 531         free_value (a);
 532         free_value (b);
 533         return r;
 534 }
 535
 536 int
 537 chk_times(intmax_t a, intmax_t b, intmax_t r)
 538 {
 539         /* special case: first operand is 0, no overflow possible */
 540         if (a == 0)
 541                 return 0;
 542         /* verify that result of division matches second operand */
 543         if (r / a != b)
 544                 return 1;
 545         return 0;
 546 }
 547
 548 struct val *
 549 op_times(struct val *a, struct val *b)
 550 {
 551         struct val *r;
 552
 553         if (!to_integer(a) || !to_integer(b)) {
 554                 errx(ERR_EXIT, "non-numeric argument");
 555         }
 556
 557         if (eflag) {
 558                 r = make_integer(a->u.i * b->u.i);
 559                 if (chk_times(a->u.i, b->u.i, r->u.i)) {
 560                         errx(ERR_EXIT, "overflow");
 561                 }
 562         } else
 563                 r = make_integer((long)a->u.i * (long)b->u.i);
 564
 565         free_value (a);
 566         free_value (b);
 567         return (r);
 568 }
 569
 570 int
 571 chk_div(intmax_t a, intmax_t b)
 572 {
 573         /* div by zero has been taken care of before */
 574         /* only INTMAX_MIN / -1 causes overflow */
 575         if (a == INTMAX_MIN && b == -1)
 576                 return 1;
 577         /* everything else is OK */
 578         return 0;
 579 }
 580
 581 struct val *
 582 op_div(struct val *a, struct val *b)
 583 {
 584         struct val *r;
 585
 586         if (!to_integer(a) || !to_integer(b)) {
 587                 errx(ERR_EXIT, "non-numeric argument");
 588         }
 589
 590         if (b->u.i == 0) {
 591                 errx(ERR_EXIT, "division by zero");
 592         }
 593
 594         if (eflag) {
 595                 r = make_integer(a->u.i / b->u.i);
 596                 if (chk_div(a->u.i, b->u.i)) {
 597                         errx(ERR_EXIT, "overflow");
 598                 }
 599         } else
 600                 r = make_integer((long)a->u.i / (long)b->u.i);
 601
 602         free_value (a);
 603         free_value (b);
 604         return r;
 605 }
 606
 607 struct val *
 608 op_rem(struct val *a, struct val *b)
 609 {
 610         struct val *r;
 611
 612         if (!to_integer(a) || !to_integer(b)) {
 613                 errx(ERR_EXIT, "non-numeric argument");
 614         }
 615
 616         if (b->u.i == 0) {
 617                 errx(ERR_EXIT, "division by zero");
 618         }
 619
 620         if (eflag)
 621                 r = make_integer(a->u.i % b->u.i);
 622                 /* chk_rem necessary ??? */
 623         else
 624                 r = make_integer((long)a->u.i % (long)b->u.i);
 625
 626         free_value (a);
 627         free_value (b);
 628         return r;
 629 }
 630
 631 struct val *
 632 op_colon(struct val *a, struct val *b)
 633 {
 634         regex_t rp;
 635         regmatch_t rm[2];
 636         char errbuf[256];
 637         int eval;
 638         struct val *v;
 639
 640         /* coerce both arguments to strings */
 641         to_string(a);
 642         to_string(b);
 643
 644         /* compile regular expression */
 645         if ((eval = regcomp (&rp, b->u.s, 0)) != 0) {
 646                 regerror (eval, &rp, errbuf, sizeof(errbuf));
 647                 errx(ERR_EXIT, "%s", errbuf);
 648         }
 649
 650         /* compare string against pattern */
 651         /* remember that patterns are anchored to the beginning of the line */
 652         if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) {
 653                 if (rm[1].rm_so >= 0) {
 654                         *(a->u.s + rm[1].rm_eo) = '\0';
 655                         v = make_str (a->u.s + rm[1].rm_so);
 656
 657                 } else {
 658                         v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so));
 659                 }
 660         } else {
 661                 if (rp.re_nsub == 0) {
 662                         v = make_integer ((intmax_t)0);
 663                 } else {
 664                         v = make_str ("");
 665                 }
 666         }
 667
 668         /* free arguments and pattern buffer */
 669         free_value (a);
 670         free_value (b);
 671         regfree (&rp);
 672
 673         return v;
 674 }