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