bin/expr/expr.y

   1 %{
   2 /* Written by Pace Willisson (pace@blitz.com)
   3  * and placed in the public domain.
   4  *
   5  * Largely rewritten by J.T. Conklin (jtc@wimsey.com)
   6  *
   7  * $FreeBSD: src/bin/expr/expr.y,v 1.14.2.3 2001/08/01 02:37:46 obrien Exp $
   8  * $DragonFly: src/bin/expr/expr.y,v 1.6 2005/11/06 11:44:02 swildner Exp $
   9  */
  10
  11 #include <sys/types.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include <locale.h>
  16 #include <ctype.h>
  17 #include <err.h>
  18 #include <errno.h>
  19 #include <regex.h>
  20 #include <limits.h>
  21
  22 enum valtype {
  23         integer, numeric_string, string
  24 } ;
  25
  26 struct val {
  27         enum valtype type;
  28         union {
  29                 char *s;
  30                 quad_t i;
  31         } u;
  32 } ;
  33
  34 struct val *result;
  35
  36 int             chk_div (quad_t, quad_t);
  37 int             chk_minus (quad_t, quad_t, quad_t);
  38 int             chk_plus (quad_t, quad_t, quad_t);
  39 int             chk_times (quad_t, quad_t, quad_t);
  40 void            free_value (struct val *);
  41 int             is_zero_or_null (struct val *);
  42 int             isstring (struct val *);
  43 int             main (int, char **);
  44 struct val      *make_integer (quad_t);
  45 struct val      *make_str (const char *);
  46 struct val      *op_and (struct val *, struct val *);
  47 struct val      *op_colon (struct val *, struct val *);
  48 struct val      *op_div (struct val *, struct val *);
  49 struct val      *op_eq (struct val *, struct val *);
  50 struct val      *op_ge (struct val *, struct val *);
  51 struct val      *op_gt (struct val *, struct val *);
  52 struct val      *op_le (struct val *, struct val *);
  53 struct val      *op_lt (struct val *, struct val *);
  54 struct val      *op_minus (struct val *, struct val *);
  55 struct val      *op_ne (struct val *, struct val *);
  56 struct val      *op_or (struct val *, struct val *);
  57 struct val      *op_plus (struct val *, struct val *);
  58 struct val      *op_rem (struct val *, struct val *);
  59 struct val      *op_times (struct val *, struct val *);
  60 quad_t          to_integer (struct val *);
  61 void            to_string (struct val *);
  62 int             yyerror (const char *);
  63 int             yylex (void);
  64 int             yyparse (void);
  65
  66 char **av;
  67 %}
  68
  69 %union
  70 {
  71         struct val *val;
  72 }
  73
  74 %left <val> '|'
  75 %left <val> '&'
  76 %left <val> '=' '>' '<' GE LE NE
  77 %left <val> '+' '-'
  78 %left <val> '*' '/' '%'
  79 %left <val> ':'
  80
  81 %token <val> TOKEN
  82 %type <val> start expr
  83
  84 %%
  85
  86 start: expr { result = $$; }
  87
  88 expr:   TOKEN
  89         | '(' expr ')' { $$ = $2; }
  90         | expr '|' expr { $$ = op_or ($1, $3); }
  91         | expr '&' expr { $$ = op_and ($1, $3); }
  92         | expr '=' expr { $$ = op_eq ($1, $3); }
  93         | expr '>' expr { $$ = op_gt ($1, $3); }
  94         | expr '<' expr { $$ = op_lt ($1, $3); }
  95         | expr GE expr  { $$ = op_ge ($1, $3); }
  96         | expr LE expr  { $$ = op_le ($1, $3); }
  97         | expr NE expr  { $$ = op_ne ($1, $3); }
  98         | expr '+' expr { $$ = op_plus ($1, $3); }
  99         | expr '-' expr { $$ = op_minus ($1, $3); }
 100         | expr '*' expr { $$ = op_times ($1, $3); }
 101         | expr '/' expr { $$ = op_div ($1, $3); }
 102         | expr '%' expr { $$ = op_rem ($1, $3); }
 103         | expr ':' expr { $$ = op_colon ($1, $3); }
 104         ;
 105
 106
 107 %%
 108
 109 struct val *
 110 make_integer(quad_t i)
 111 {
 112         struct val *vp;
 113
 114         vp = (struct val *) malloc (sizeof (*vp));
 115         if (vp == NULL) {
 116                 errx (2, "malloc() failed");
 117         }
 118
 119         vp->type = integer;
 120         vp->u.i  = i;
 121         return vp;
 122 }
 123
 124 struct val *
 125 make_str(const char *s)
 126 {
 127         struct val *vp;
 128         size_t i;
 129         int isint;
 130
 131         vp = (struct val *) malloc (sizeof (*vp));
 132         if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) {
 133                 errx (2, "malloc() failed");
 134         }
 135
 136         for(i = 1, isint = isdigit(s[0]) || s[0] == '-';
 137             isint && i < strlen(s);
 138             i++)
 139         {
 140                 if(!isdigit(s[i]))
 141                          isint = 0;
 142         }
 143
 144         if (isint)
 145                 vp->type = numeric_string;
 146         else
 147                 vp->type = string;
 148
 149         return vp;
 150 }
 151
 152
 153 void
 154 free_value(struct val *vp)
 155 {
 156         if (vp->type == string || vp->type == numeric_string)
 157                 free (vp->u.s);
 158 }
 159
 160
 161 quad_t
 162 to_integer(struct val *vp)
 163 {
 164         quad_t i;
 165
 166         if (vp->type == integer)
 167                 return 1;
 168
 169         if (vp->type == string)
 170                 return 0;
 171
 172         /* vp->type == numeric_string, make it numeric */
 173         errno = 0;
 174         i  = strtoll(vp->u.s, NULL, 10);
 175         if (errno != 0) {
 176                 errx (2, "overflow");
 177         }
 178         free (vp->u.s);
 179         vp->u.i = i;
 180         vp->type = integer;
 181         return 1;
 182 }
 183
 184 void
 185 to_string(struct val *vp)
 186 {
 187         char *tmp;
 188
 189         if (vp->type == string || vp->type == numeric_string)
 190                 return;
 191
 192         tmp = malloc ((size_t)25);
 193         if (tmp == NULL) {
 194                 errx (2, "malloc() failed");
 195         }
 196
 197         sprintf (tmp, "%lld", (long long)vp->u.i);
 198         vp->type = string;
 199         vp->u.s  = tmp;
 200 }
 201
 202
 203 int
 204 isstring(struct val *vp)
 205 {
 206         /* only TRUE if this string is not a valid integer */
 207         return (vp->type == string);
 208 }
 209
 210
 211 int
 212 yylex(void)
 213 {
 214         char *p;
 215
 216         if (*av == NULL)
 217                 return (0);
 218
 219         p = *av++;
 220
 221         if (strlen (p) == 1) {
 222                 if (strchr ("|&=<>+-*/%:()", *p))
 223                         return (*p);
 224         } else if (strlen (p) == 2 && p[1] == '=') {
 225                 switch (*p) {
 226                 case '>': return (GE);
 227                 case '<': return (LE);
 228                 case '!': return (NE);
 229                 }
 230         }
 231
 232         yylval.val = make_str (p);
 233         return (TOKEN);
 234 }
 235
 236 int
 237 is_zero_or_null(struct val *vp)
 238 {
 239         if (vp->type == integer) {
 240                 return (vp->u.i == 0);
 241         } else {
 242                 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0));
 243         }
 244         /* NOTREACHED */
 245 }
 246
 247 static void
 248 usage(void)
 249 {
 250         fprintf(stderr,
 251                 "usage: expr expression\n");
 252         exit(EXIT_FAILURE);
 253 }
 254
 255 int
 256 main (int argc, char **argv)
 257 {
 258         setlocale (LC_ALL, "");
 259
 260         if (argc > 1 && strcmp(argv[1], "--"))
 261                 av = argv + 1;
 262         else if (argc > 2)
 263                 av = argv + 2;
 264         else
 265                 usage();
 266
 267         yyparse ();
 268
 269         if (result->type == integer)
 270                 printf ("%lld\n", (long long)result->u.i);
 271         else
 272                 printf ("%s\n", result->u.s);
 273
 274         return (is_zero_or_null (result));
 275 }
 276
 277 int
 278 yyerror(const char *s __unused)
 279 {
 280         errx (2, "syntax error");
 281 }
 282
 283
 284 struct val *
 285 op_or(struct val *a, struct val *b)
 286 {
 287         if (is_zero_or_null (a)) {
 288                 free_value (a);
 289                 return (b);
 290         } else {
 291                 free_value (b);
 292                 return (a);
 293         }
 294 }
 295
 296 struct val *
 297 op_and(struct val *a, struct val *b)
 298 {
 299         if (is_zero_or_null (a) || is_zero_or_null (b)) {
 300                 free_value (a);
 301                 free_value (b);
 302                 return (make_integer ((quad_t)0));
 303         } else {
 304                 free_value (b);
 305                 return (a);
 306         }
 307 }
 308
 309 struct val *
 310 op_eq(struct val *a, struct val *b)
 311 {
 312         struct val *r;
 313
 314         if (isstring (a) || isstring (b)) {
 315                 to_string (a);
 316                 to_string (b);
 317                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) == 0));
 318         } else {
 319                 to_integer(a);
 320                 to_integer(b);
 321                 r = make_integer ((quad_t)(a->u.i == b->u.i));
 322         }
 323
 324         free_value (a);
 325         free_value (b);
 326         return r;
 327 }
 328
 329 struct val *
 330 op_gt(struct val *a, struct val *b)
 331 {
 332         struct val *r;
 333
 334         if (isstring (a) || isstring (b)) {
 335                 to_string (a);
 336                 to_string (b);
 337                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) > 0));
 338         } else {
 339                 to_integer(a);
 340                 to_integer(b);
 341                 r = make_integer ((quad_t)(a->u.i > b->u.i));
 342         }
 343
 344         free_value (a);
 345         free_value (b);
 346         return r;
 347 }
 348
 349 struct val *
 350 op_lt(struct val *a, struct val *b)
 351 {
 352         struct val *r;
 353
 354         if (isstring (a) || isstring (b)) {
 355                 to_string (a);
 356                 to_string (b);
 357                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) < 0));
 358         } else {
 359                 to_integer(a);
 360                 to_integer(b);
 361                 r = make_integer ((quad_t)(a->u.i < b->u.i));
 362         }
 363
 364         free_value (a);
 365         free_value (b);
 366         return r;
 367 }
 368
 369 struct val *
 370 op_ge(struct val *a, struct val *b)
 371 {
 372         struct val *r;
 373
 374         if (isstring (a) || isstring (b)) {
 375                 to_string (a);
 376                 to_string (b);
 377                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) >= 0));
 378         } else {
 379                 to_integer(a);
 380                 to_integer(b);
 381                 r = make_integer ((quad_t)(a->u.i >= b->u.i));
 382         }
 383
 384         free_value (a);
 385         free_value (b);
 386         return r;
 387 }
 388
 389 struct val *
 390 op_le(struct val *a, struct val *b)
 391 {
 392         struct val *r;
 393
 394         if (isstring (a) || isstring (b)) {
 395                 to_string (a);
 396                 to_string (b);
 397                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) <= 0));
 398         } else {
 399                 to_integer(a);
 400                 to_integer(b);
 401                 r = make_integer ((quad_t)(a->u.i <= b->u.i));
 402         }
 403
 404         free_value (a);
 405         free_value (b);
 406         return r;
 407 }
 408
 409 struct val *
 410 op_ne(struct val *a, struct val *b)
 411 {
 412         struct val *r;
 413
 414         if (isstring (a) || isstring (b)) {
 415                 to_string (a);
 416                 to_string (b);
 417                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) != 0));
 418         } else {
 419                 to_integer(a);
 420                 to_integer(b);
 421                 r = make_integer ((quad_t)(a->u.i != b->u.i));
 422         }
 423
 424         free_value (a);
 425         free_value (b);
 426         return r;
 427 }
 428
 429 int
 430 chk_plus(quad_t a, quad_t b, quad_t r)
 431 {
 432         /* sum of two positive numbers must be positive */
 433         if (a > 0 && b > 0 && r <= 0)
 434                 return 1;
 435         /* sum of two negative numbers must be negative */
 436         if (a < 0 && b < 0 && r >= 0)
 437                 return 1;
 438         /* all other cases are OK */
 439         return 0;
 440 }
 441
 442 struct val *
 443 op_plus(struct val *a, struct val *b)
 444 {
 445         struct val *r;
 446
 447         if (!to_integer (a) || !to_integer (b)) {
 448                 errx (2, "non-numeric argument");
 449         }
 450
 451         r = make_integer (/*(quad_t)*/(a->u.i + b->u.i));
 452         if (chk_plus (a->u.i, b->u.i, r->u.i)) {
 453                 errx (2, "overflow");
 454         }
 455         free_value (a);
 456         free_value (b);
 457         return r;
 458 }
 459
 460 int
 461 chk_minus(quad_t a, quad_t b, quad_t r)
 462 {
 463         /* special case subtraction of QUAD_MIN */
 464         if (b == QUAD_MIN) {
 465                 if (a >= 0)
 466                         return 1;
 467                 else
 468                         return 0;
 469         }
 470         /* this is allowed for b != QUAD_MIN */
 471         return chk_plus (a, -b, r);
 472 }
 473
 474 struct val *
 475 op_minus(struct val *a, struct val *b)
 476 {
 477         struct val *r;
 478
 479         if (!to_integer (a) || !to_integer (b)) {
 480                 errx (2, "non-numeric argument");
 481         }
 482
 483         r = make_integer (/*(quad_t)*/(a->u.i - b->u.i));
 484         if (chk_minus (a->u.i, b->u.i, r->u.i)) {
 485                 errx (2, "overflow");
 486         }
 487         free_value (a);
 488         free_value (b);
 489         return r;
 490 }
 491
 492 int
 493 chk_times(quad_t a, quad_t b, quad_t r)
 494 {
 495         /* special case: first operand is 0, no overflow possible */
 496         if (a == 0)
 497                 return 0;
 498         /* cerify that result of division matches second operand */
 499         if (r / a != b)
 500                 return 1;
 501         return 0;
 502 }
 503
 504 struct val *
 505 op_times(struct val *a, struct val *b)
 506 {
 507         struct val *r;
 508
 509         if (!to_integer (a) || !to_integer (b)) {
 510                 errx (2, "non-numeric argument");
 511         }
 512
 513         r = make_integer (/*(quad_t)*/(a->u.i * b->u.i));
 514         if (chk_times (a->u.i, b->u.i, r->u.i)) {
 515                 errx (2, "overflow");
 516         }
 517         free_value (a);
 518         free_value (b);
 519         return (r);
 520 }
 521
 522 int
 523 chk_div(quad_t a, quad_t b)
 524 {
 525         /* div by zero has been taken care of before */
 526         /* only QUAD_MIN / -1 causes overflow */
 527         if (a == QUAD_MIN && b == -1)
 528                 return 1;
 529         /* everything else is OK */
 530         return 0;
 531 }
 532
 533 struct val *
 534 op_div(struct val *a, struct val *b)
 535 {
 536         struct val *r;
 537
 538         if (!to_integer (a) || !to_integer (b)) {
 539                 errx (2, "non-numeric argument");
 540         }
 541
 542         if (b->u.i == 0) {
 543                 errx (2, "division by zero");
 544         }
 545
 546         r = make_integer (/*(quad_t)*/(a->u.i / b->u.i));
 547         if (chk_div (a->u.i, b->u.i)) {
 548                 errx (2, "overflow");
 549         }
 550         free_value (a);
 551         free_value (b);
 552         return r;
 553 }
 554
 555 struct val *
 556 op_rem(struct val *a, struct val *b)
 557 {
 558         struct val *r;
 559
 560         if (!to_integer (a) || !to_integer (b)) {
 561                 errx (2, "non-numeric argument");
 562         }
 563
 564         if (b->u.i == 0) {
 565                 errx (2, "division by zero");
 566         }
 567
 568         r = make_integer (/*(quad_t)*/(a->u.i % b->u.i));
 569         /* chk_rem necessary ??? */
 570         free_value (a);
 571         free_value (b);
 572         return r;
 573 }
 574
 575 struct val *
 576 op_colon(struct val *a, struct val *b)
 577 {
 578         regex_t rp;
 579         regmatch_t rm[2];
 580         char errbuf[256];
 581         int eval;
 582         struct val *v;
 583
 584         /* coerce to both arguments to strings */
 585         to_string(a);
 586         to_string(b);
 587
 588         /* compile regular expression */
 589         if ((eval = regcomp (&rp, b->u.s, 0)) != 0) {
 590                 regerror (eval, &rp, errbuf, sizeof(errbuf));
 591                 errx (2, "%s", errbuf);
 592         }
 593
 594         /* compare string against pattern */
 595         /* remember that patterns are anchored to the beginning of the line */
 596         if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) {
 597                 if (rm[1].rm_so >= 0) {
 598                         *(a->u.s + rm[1].rm_eo) = '\0';
 599                         v = make_str (a->u.s + rm[1].rm_so);
 600
 601                 } else {
 602                         v = make_integer ((quad_t)(rm[0].rm_eo - rm[0].rm_so));
 603                 }
 604         } else {
 605                 if (rp.re_nsub == 0) {
 606                         v = make_integer ((quad_t)0);
 607                 } else {
 608                         v = make_str ("");
 609                 }
 610         }
 611
 612         /* free arguments and pattern buffer */
 613         free_value (a);
 614         free_value (b);
 615         regfree (&rp);
 616
 617         return v;
 618 }