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