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
   9 #include <sys/types.h>
  10
  11 #include <ctype.h>
  12 #include <err.h>
  13 #include <errno.h>
  14 #include <inttypes.h>
  15 #include <limits.h>
  16 #include <locale.h>
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <regex.h>
  21 #include <unistd.h>
  22
  23 /*
  24  * POSIX specifies a specific error code for syntax errors.  We exit
  25  * with this code for all errors.
  26  */
  27 #define ERR_EXIT        2
  28
  29 enum valtype {
  30         integer, numeric_string, string
  31 } ;
  32
  33 struct val {
  34         enum valtype type;
  35         union {
  36                 char *s;
  37                 intmax_t i;
  38         } u;
  39 } ;
  40
  41 char            **av;
  42 int             nonposix;
  43 struct val      *result;
  44
  45 void            assert_to_integer(struct val *);
  46 void            assert_div(intmax_t, intmax_t);
  47 void            assert_minus(intmax_t, intmax_t, intmax_t);
  48 void            assert_plus(intmax_t, intmax_t, intmax_t);
  49 void            assert_times(intmax_t, intmax_t, intmax_t);
  50 int             compare_vals(struct val *, struct val *);
  51 void            free_value(struct val *);
  52 int             is_integer(const char *);
  53 int             is_string(struct val *);
  54 int             is_zero_or_null(struct val *);
  55 struct val      *make_integer(intmax_t);
  56 struct val      *make_str(const char *);
  57 struct val      *op_and(struct val *, struct val *);
  58 struct val      *op_colon(struct val *, struct val *);
  59 struct val      *op_div(struct val *, struct val *);
  60 struct val      *op_eq(struct val *, struct val *);
  61 struct val      *op_ge(struct val *, struct val *);
  62 struct val      *op_gt(struct val *, struct val *);
  63 struct val      *op_le(struct val *, struct val *);
  64 struct val      *op_lt(struct val *, struct val *);
  65 struct val      *op_minus(struct val *, struct val *);
  66 struct val      *op_ne(struct val *, struct val *);
  67 struct val      *op_or(struct val *, struct val *);
  68 struct val      *op_plus(struct val *, struct val *);
  69 struct val      *op_rem(struct val *, struct val *);
  70 struct val      *op_times(struct val *, struct val *);
  71 int             to_integer(struct val *);
  72 void            to_string(struct val *);
  73 int             yyerror(const char *);
  74 int             yylex(void);
  75
  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 struct val *
 118 make_integer(intmax_t i)
 119 {
 120         struct val *vp;
 121
 122         vp = (struct val *)malloc(sizeof(*vp));
 123         if (vp == NULL)
 124                 errx(ERR_EXIT, "malloc() failed");
 125
 126         vp->type = integer;
 127         vp->u.i  = i;
 128         return (vp);
 129 }
 130
 131 struct val *
 132 make_str(const char *s)
 133 {
 134         struct val *vp;
 135
 136         vp = (struct val *)malloc(sizeof(*vp));
 137         if (vp == NULL || ((vp->u.s = strdup(s)) == NULL))
 138                 errx(ERR_EXIT, "malloc() failed");
 139
 140         if (is_integer(s))
 141                 vp->type = numeric_string;
 142         else
 143                 vp->type = string;
 144
 145         return (vp);
 146 }
 147
 148 void
 149 free_value(struct val *vp)
 150 {
 151         if (vp->type == string || vp->type == numeric_string)
 152                 free(vp->u.s);
 153 }
 154
 155 int
 156 to_integer(struct val *vp)
 157 {
 158         intmax_t i;
 159
 160         /* we can only convert numeric_string to integer, here */
 161         if (vp->type == numeric_string) {
 162                 errno = 0;
 163                 i  = strtoimax(vp->u.s, (char **)NULL, 10);
 164                 /* just keep as numeric_string, if the conversion fails */
 165                 if (errno != ERANGE) {
 166                         free(vp->u.s);
 167                         vp->u.i = i;
 168                         vp->type = integer;
 169                 }
 170         }
 171         return (vp->type == integer);
 172 }
 173
 174 void
 175 assert_to_integer(struct val *vp)
 176 {
 177         if (vp->type == string)
 178                 errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s);
 179         if (!to_integer(vp))
 180                 errx(ERR_EXIT, "operand too large: '%s'", vp->u.s);
 181 }
 182
 183 void
 184 to_string(struct val *vp)
 185 {
 186         char *tmp;
 187
 188         if (vp->type == string || vp->type == numeric_string)
 189                 return;
 190
 191         /*
 192          * log_10(x) ~= 0.3 * log_2(x).  Rounding up gives the number
 193          * of digits; add one each for the sign and terminating null
 194          * character, respectively.
 195          */
 196 #define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1)
 197         tmp = malloc(NDIGITS(vp->u.i));
 198         if (tmp == NULL)
 199                 errx(ERR_EXIT, "malloc() failed");
 200
 201         sprintf(tmp, "%jd", vp->u.i);
 202         vp->type = string;
 203         vp->u.s  = tmp;
 204 }
 205
 206 int
 207 is_integer(const char *s)
 208 {
 209         if (nonposix) {
 210                 if (*s == '\0')
 211                         return (1);
 212                 while (isspace((unsigned char)*s))
 213                         s++;
 214         }
 215         if (*s == '-' || (nonposix && *s == '+'))
 216                 s++;
 217         if (*s == '\0')
 218                 return (0);
 219         while (isdigit((unsigned char)*s))
 220                 s++;
 221         return (*s == '\0');
 222 }
 223
 224 int
 225 is_string(struct val *vp)
 226 {
 227         /* only TRUE if this string is not a valid integer */
 228         return (vp->type == string);
 229 }
 230
 231 int
 232 yylex(void)
 233 {
 234         char *p;
 235
 236         if (*av == NULL)
 237                 return (0);
 238
 239         p = *av++;
 240
 241         if (strlen(p) == 1) {
 242                 if (strchr("|&=<>+-*/%:()", *p))
 243                         return (*p);
 244         } else if (strlen(p) == 2 && p[1] == '=') {
 245                 switch (*p) {
 246                 case '>': return (GE);
 247                 case '<': return (LE);
 248                 case '!': return (NE);
 249                 }
 250         }
 251
 252         yylval.val = make_str(p);
 253         return (TOKEN);
 254 }
 255
 256 int
 257 is_zero_or_null(struct val *vp)
 258 {
 259         if (vp->type == integer)
 260                 return (vp->u.i == 0);
 261
 262         return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0));
 263 }
 264
 265 int
 266 main(int argc, char *argv[])
 267 {
 268         int c;
 269
 270         setlocale(LC_ALL, "");
 271         if (getenv("EXPR_COMPAT") != NULL
 272             || check_utility_compat("expr")) {
 273                 av = argv + 1;
 274                 nonposix = 1;
 275         } else {
 276                 while ((c = getopt(argc, argv, "e")) != -1) {
 277                         switch (c) {
 278                         case 'e':
 279                                 nonposix = 1;
 280                                 break;
 281                         default:
 282                                 errx(ERR_EXIT,
 283                                     "usage: expr [-e] expression\n");
 284                         }
 285                 }
 286                 av = argv + optind;
 287         }
 288
 289         yyparse();
 290
 291         if (result->type == integer)
 292                 printf("%jd\n", result->u.i);
 293         else
 294                 printf("%s\n", result->u.s);
 295
 296         return (is_zero_or_null(result));
 297 }
 298
 299 int
 300 yyerror(const char *s __unused)
 301 {
 302         errx(ERR_EXIT, "syntax error");
 303 }
 304
 305 struct val *
 306 op_or(struct val *a, struct val *b)
 307 {
 308         if (!is_zero_or_null(a)) {
 309                 free_value(b);
 310                 return (a);
 311         }
 312         free_value(a);
 313         if (!is_zero_or_null(b))
 314                 return (b);
 315         free_value(b);
 316         return (make_integer((intmax_t)0));
 317 }
 318
 319 struct val *
 320 op_and(struct val *a, struct val *b)
 321 {
 322         if (is_zero_or_null(a) || is_zero_or_null(b)) {
 323                 free_value(a);
 324                 free_value(b);
 325                 return (make_integer((intmax_t)0));
 326         } else {
 327                 free_value(b);
 328                 return (a);
 329         }
 330 }
 331
 332 int
 333 compare_vals(struct val *a, struct val *b)
 334 {
 335         int r;
 336
 337         if (is_string(a) || is_string(b)) {
 338                 to_string(a);
 339                 to_string(b);
 340                 r = strcoll(a->u.s, b->u.s);
 341         } else {
 342                 assert_to_integer(a);
 343                 assert_to_integer(b);
 344                 if (a->u.i > b->u.i)
 345                         r = 1;
 346                 else if (a->u.i < b->u.i)
 347                         r = -1;
 348                 else
 349                         r = 0;
 350         }
 351
 352         free_value(a);
 353         free_value(b);
 354         return (r);
 355 }
 356
 357 struct val *
 358 op_eq(struct val *a, struct val *b)
 359 {
 360         return (make_integer((intmax_t)(compare_vals(a, b) == 0)));
 361 }
 362
 363 struct val *
 364 op_gt(struct val *a, struct val *b)
 365 {
 366         return (make_integer((intmax_t)(compare_vals(a, b) > 0)));
 367 }
 368
 369 struct val *
 370 op_lt(struct val *a, struct val *b)
 371 {
 372         return (make_integer((intmax_t)(compare_vals(a, b) < 0)));
 373 }
 374
 375 struct val *
 376 op_ge(struct val *a, struct val *b)
 377 {
 378         return (make_integer((intmax_t)(compare_vals(a, b) >= 0)));
 379 }
 380
 381 struct val *
 382 op_le(struct val *a, struct val *b)
 383 {
 384         return (make_integer((intmax_t)(compare_vals(a, b) <= 0)));
 385 }
 386
 387 struct val *
 388 op_ne(struct val *a, struct val *b)
 389 {
 390         return (make_integer((intmax_t)(compare_vals(a, b) != 0)));
 391 }
 392
 393 void
 394 assert_plus(intmax_t a, intmax_t b, intmax_t r)
 395 {
 396         /*
 397          * sum of two positive numbers must be positive,
 398          * sum of two negative numbers must be negative
 399          */
 400         if ((a > 0 && b > 0 && r <= 0) ||
 401             (a < 0 && b < 0 && r >= 0))
 402                 errx(ERR_EXIT, "overflow");
 403 }
 404
 405 struct val *
 406 op_plus(struct val *a, struct val *b)
 407 {
 408         struct val *r;
 409
 410         assert_to_integer(a);
 411         assert_to_integer(b);
 412         r = make_integer(a->u.i + b->u.i);
 413         assert_plus(a->u.i, b->u.i, r->u.i);
 414
 415         free_value(a);
 416         free_value(b);
 417         return (r);
 418 }
 419
 420 void
 421 assert_minus(intmax_t a, intmax_t b, intmax_t r)
 422 {
 423         if ((a >= 0 && b < 0 && r <= 0) ||
 424             (a < 0 && b > 0 && r >= 0))
 425                 errx(ERR_EXIT, "overflow");
 426 }
 427
 428 struct val *
 429 op_minus(struct val *a, struct val *b)
 430 {
 431         struct val *r;
 432
 433         assert_to_integer(a);
 434         assert_to_integer(b);
 435         r = make_integer(a->u.i - b->u.i);
 436         assert_minus(a->u.i, b->u.i, r->u.i);
 437
 438         free_value(a);
 439         free_value(b);
 440         return (r);
 441 }
 442
 443 /*
 444  * We depend on undefined behaviour giving a result (in r).
 445  * To test this result, pass it as volatile.  This prevents
 446  * optimizing away of the test based on the undefined behaviour.
 447  */
 448 void
 449 assert_times(intmax_t a, intmax_t b, volatile intmax_t r)
 450 {
 451         /*
 452          * If the first operand is 0, no overflow is possible,
 453          * else the result of the division test must match the
 454          * second operand.
 455          *
 456          * Be careful to avoid overflow in the overflow test, as
 457          * in assert_div().  Overflow in division would kill us
 458          * with a SIGFPE before getting the test wrong.  In old
 459          * buggy versions, optimization used to give a null test
 460          * instead of a SIGFPE.
 461          */
 462         if ((a == -1 && b == INTMAX_MIN) || (a != 0 && r / a != b))
 463                 errx(ERR_EXIT, "overflow");
 464 }
 465
 466 struct val *
 467 op_times(struct val *a, struct val *b)
 468 {
 469         struct val *r;
 470
 471         assert_to_integer(a);
 472         assert_to_integer(b);
 473         r = make_integer(a->u.i * b->u.i);
 474         assert_times(a->u.i, b->u.i, r->u.i);
 475
 476         free_value(a);
 477         free_value(b);
 478         return (r);
 479 }
 480
 481 void
 482 assert_div(intmax_t a, intmax_t b)
 483 {
 484         if (b == 0)
 485                 errx(ERR_EXIT, "division by zero");
 486         /* only INTMAX_MIN / -1 causes overflow */
 487         if (a == INTMAX_MIN && b == -1)
 488                 errx(ERR_EXIT, "overflow");
 489 }
 490
 491 struct val *
 492 op_div(struct val *a, struct val *b)
 493 {
 494         struct val *r;
 495
 496         assert_to_integer(a);
 497         assert_to_integer(b);
 498         /* assert based on operands only, not on result */
 499         assert_div(a->u.i, b->u.i);
 500         r = make_integer(a->u.i / b->u.i);
 501
 502         free_value(a);
 503         free_value(b);
 504         return (r);
 505 }
 506
 507 struct val *
 508 op_rem(struct val *a, struct val *b)
 509 {
 510         struct val *r;
 511
 512         assert_to_integer(a);
 513         assert_to_integer(b);
 514         /* pass a=1 to only check for div by zero */
 515         assert_div(1, b->u.i);
 516         r = make_integer(a->u.i % b->u.i);
 517
 518         free_value(a);
 519         free_value(b);
 520         return (r);
 521 }
 522
 523 struct val *
 524 op_colon(struct val *a, struct val *b)
 525 {
 526         regex_t rp;
 527         regmatch_t rm[2];
 528         char errbuf[256];
 529         int eval;
 530         struct val *v;
 531
 532         /* coerce both arguments to strings */
 533         to_string(a);
 534         to_string(b);
 535
 536         /* compile regular expression */
 537         if ((eval = regcomp(&rp, b->u.s, 0)) != 0) {
 538                 regerror(eval, &rp, errbuf, sizeof(errbuf));
 539                 errx(ERR_EXIT, "%s", errbuf);
 540         }
 541
 542         /* compare string against pattern */
 543         /* remember that patterns are anchored to the beginning of the line */
 544         if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0)
 545                 if (rm[1].rm_so >= 0) {
 546                         *(a->u.s + rm[1].rm_eo) = '\0';
 547                         v = make_str(a->u.s + rm[1].rm_so);
 548
 549                 } else
 550                         v = make_integer((intmax_t)(rm[0].rm_eo));
 551         else
 552                 if (rp.re_nsub == 0)
 553                         v = make_integer((intmax_t)0);
 554                 else
 555                         v = make_str("");
 556
 557         /* free arguments and pattern buffer */
 558         free_value(a);
 559         free_value(b);
 560         regfree(&rp);
 561
 562         return (v);
 563 }