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.5 2004/11/07 20:54:51 eirikn 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 (i)
 111 quad_t i;
 112 {
 113         struct val *vp;
 114
 115         vp = (struct val *) malloc (sizeof (*vp));
 116         if (vp == NULL) {
 117                 errx (2, "malloc() failed");
 118         }
 119
 120         vp->type = integer;
 121         vp->u.i  = i;
 122         return vp;
 123 }
 124
 125 struct val *
 126 make_str (s)
 127 const char *s;
 128 {
 129         struct val *vp;
 130         size_t i;
 131         int isint;
 132
 133         vp = (struct val *) malloc (sizeof (*vp));
 134         if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) {
 135                 errx (2, "malloc() failed");
 136         }
 137
 138         for(i = 1, isint = isdigit(s[0]) || s[0] == '-';
 139             isint && i < strlen(s);
 140             i++)
 141         {
 142                 if(!isdigit(s[i]))
 143                          isint = 0;
 144         }
 145
 146         if (isint)
 147                 vp->type = numeric_string;
 148         else
 149                 vp->type = string;
 150
 151         return vp;
 152 }
 153
 154
 155 void
 156 free_value (vp)
 157 struct val *vp;
 158 {
 159         if (vp->type == string || vp->type == numeric_string)
 160                 free (vp->u.s);
 161 }
 162
 163
 164 quad_t
 165 to_integer (vp)
 166 struct val *vp;
 167 {
 168         quad_t i;
 169
 170         if (vp->type == integer)
 171                 return 1;
 172
 173         if (vp->type == string)
 174                 return 0;
 175
 176         /* vp->type == numeric_string, make it numeric */
 177         errno = 0;
 178         i  = strtoll(vp->u.s, (char**)NULL, 10);
 179         if (errno != 0) {
 180                 errx (2, "overflow");
 181         }
 182         free (vp->u.s);
 183         vp->u.i = i;
 184         vp->type = integer;
 185         return 1;
 186 }
 187
 188 void
 189 to_string (vp)
 190 struct val *vp;
 191 {
 192         char *tmp;
 193
 194         if (vp->type == string || vp->type == numeric_string)
 195                 return;
 196
 197         tmp = malloc ((size_t)25);
 198         if (tmp == NULL) {
 199                 errx (2, "malloc() failed");
 200         }
 201
 202         sprintf (tmp, "%lld", (long long)vp->u.i);
 203         vp->type = string;
 204         vp->u.s  = tmp;
 205 }
 206
 207
 208 int
 209 isstring (vp)
 210 struct val *vp;
 211 {
 212         /* only TRUE if this string is not a valid integer */
 213         return (vp->type == string);
 214 }
 215
 216
 217 int
 218 yylex ()
 219 {
 220         char *p;
 221
 222         if (*av == NULL)
 223                 return (0);
 224
 225         p = *av++;
 226
 227         if (strlen (p) == 1) {
 228                 if (strchr ("|&=<>+-*/%:()", *p))
 229                         return (*p);
 230         } else if (strlen (p) == 2 && p[1] == '=') {
 231                 switch (*p) {
 232                 case '>': return (GE);
 233                 case '<': return (LE);
 234                 case '!': return (NE);
 235                 }
 236         }
 237
 238         yylval.val = make_str (p);
 239         return (TOKEN);
 240 }
 241
 242 int
 243 is_zero_or_null (vp)
 244 struct val *vp;
 245 {
 246         if (vp->type == integer) {
 247                 return (vp->u.i == 0);
 248         } else {
 249                 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0));
 250         }
 251         /* NOTREACHED */
 252 }
 253
 254 int
 255 main (argc, argv)
 256 int argc __unused;
 257 char **argv;
 258 {
 259         setlocale (LC_ALL, "");
 260
 261         av = argv + 1;
 262
 263         yyparse ();
 264
 265         if (result->type == integer)
 266                 printf ("%lld\n", (long long)result->u.i);
 267         else
 268                 printf ("%s\n", result->u.s);
 269
 270         return (is_zero_or_null (result));
 271 }
 272
 273 int
 274 yyerror (s)
 275 const char *s __unused;
 276 {
 277         errx (2, "syntax error");
 278 }
 279
 280
 281 struct val *
 282 op_or (a, b)
 283 struct val *a, *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 (a, b)
 296 struct val *a, *b;
 297 {
 298         if (is_zero_or_null (a) || is_zero_or_null (b)) {
 299                 free_value (a);
 300                 free_value (b);
 301                 return (make_integer ((quad_t)0));
 302         } else {
 303                 free_value (b);
 304                 return (a);
 305         }
 306 }
 307
 308 struct val *
 309 op_eq (a, b)
 310 struct val *a, *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 (a, b)
 331 struct val *a, *b;
 332 {
 333         struct val *r;
 334
 335         if (isstring (a) || isstring (b)) {
 336                 to_string (a);
 337                 to_string (b);
 338                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) > 0));
 339         } else {
 340                 to_integer(a);
 341                 to_integer(b);
 342                 r = make_integer ((quad_t)(a->u.i > b->u.i));
 343         }
 344
 345         free_value (a);
 346         free_value (b);
 347         return r;
 348 }
 349
 350 struct val *
 351 op_lt (a, b)
 352 struct val *a, *b;
 353 {
 354         struct val *r;
 355
 356         if (isstring (a) || isstring (b)) {
 357                 to_string (a);
 358                 to_string (b);
 359                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) < 0));
 360         } else {
 361                 to_integer(a);
 362                 to_integer(b);
 363                 r = make_integer ((quad_t)(a->u.i < b->u.i));
 364         }
 365
 366         free_value (a);
 367         free_value (b);
 368         return r;
 369 }
 370
 371 struct val *
 372 op_ge (a, b)
 373 struct val *a, *b;
 374 {
 375         struct val *r;
 376
 377         if (isstring (a) || isstring (b)) {
 378                 to_string (a);
 379                 to_string (b);
 380                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) >= 0));
 381         } else {
 382                 to_integer(a);
 383                 to_integer(b);
 384                 r = make_integer ((quad_t)(a->u.i >= b->u.i));
 385         }
 386
 387         free_value (a);
 388         free_value (b);
 389         return r;
 390 }
 391
 392 struct val *
 393 op_le (a, b)
 394 struct val *a, *b;
 395 {
 396         struct val *r;
 397
 398         if (isstring (a) || isstring (b)) {
 399                 to_string (a);
 400                 to_string (b);
 401                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) <= 0));
 402         } else {
 403                 to_integer(a);
 404                 to_integer(b);
 405                 r = make_integer ((quad_t)(a->u.i <= b->u.i));
 406         }
 407
 408         free_value (a);
 409         free_value (b);
 410         return r;
 411 }
 412
 413 struct val *
 414 op_ne (a, b)
 415 struct val *a, *b;
 416 {
 417         struct val *r;
 418
 419         if (isstring (a) || isstring (b)) {
 420                 to_string (a);
 421                 to_string (b);
 422                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) != 0));
 423         } else {
 424                 to_integer(a);
 425                 to_integer(b);
 426                 r = make_integer ((quad_t)(a->u.i != b->u.i));
 427         }
 428
 429         free_value (a);
 430         free_value (b);
 431         return r;
 432 }
 433
 434 int
 435 chk_plus (a, b, r)
 436 quad_t a, b, r;
 437 {
 438         /* sum of two positive numbers must be positive */
 439         if (a > 0 && b > 0 && r <= 0)
 440                 return 1;
 441         /* sum of two negative numbers must be negative */
 442         if (a < 0 && b < 0 && r >= 0)
 443                 return 1;
 444         /* all other cases are OK */
 445         return 0;
 446 }
 447
 448 struct val *
 449 op_plus (a, b)
 450 struct val *a, *b;
 451 {
 452         struct val *r;
 453
 454         if (!to_integer (a) || !to_integer (b)) {
 455                 errx (2, "non-numeric argument");
 456         }
 457
 458         r = make_integer (/*(quad_t)*/(a->u.i + b->u.i));
 459         if (chk_plus (a->u.i, b->u.i, r->u.i)) {
 460                 errx (2, "overflow");
 461         }
 462         free_value (a);
 463         free_value (b);
 464         return r;
 465 }
 466
 467 int
 468 chk_minus (a, b, r)
 469 quad_t a, b, r;
 470 {
 471         /* special case subtraction of QUAD_MIN */
 472         if (b == QUAD_MIN) {
 473                 if (a >= 0)
 474                         return 1;
 475                 else
 476                         return 0;
 477         }
 478         /* this is allowed for b != QUAD_MIN */
 479         return chk_plus (a, -b, r);
 480 }
 481
 482 struct val *
 483 op_minus (a, b)
 484 struct val *a, *b;
 485 {
 486         struct val *r;
 487
 488         if (!to_integer (a) || !to_integer (b)) {
 489                 errx (2, "non-numeric argument");
 490         }
 491
 492         r = make_integer (/*(quad_t)*/(a->u.i - b->u.i));
 493         if (chk_minus (a->u.i, b->u.i, r->u.i)) {
 494                 errx (2, "overflow");
 495         }
 496         free_value (a);
 497         free_value (b);
 498         return r;
 499 }
 500
 501 int
 502 chk_times (a, b, r)
 503 quad_t a, b, r;
 504 {
 505         /* special case: first operand is 0, no overflow possible */
 506         if (a == 0)
 507                 return 0;
 508         /* cerify that result of division matches second operand */
 509         if (r / a != b)
 510                 return 1;
 511         return 0;
 512 }
 513
 514 struct val *
 515 op_times (a, b)
 516 struct val *a, *b;
 517 {
 518         struct val *r;
 519
 520         if (!to_integer (a) || !to_integer (b)) {
 521                 errx (2, "non-numeric argument");
 522         }
 523
 524         r = make_integer (/*(quad_t)*/(a->u.i * b->u.i));
 525         if (chk_times (a->u.i, b->u.i, r->u.i)) {
 526                 errx (2, "overflow");
 527         }
 528         free_value (a);
 529         free_value (b);
 530         return (r);
 531 }
 532
 533 int
 534 chk_div (a, b)
 535 quad_t a, b;
 536 {
 537         /* div by zero has been taken care of before */
 538         /* only QUAD_MIN / -1 causes overflow */
 539         if (a == QUAD_MIN && b == -1)
 540                 return 1;
 541         /* everything else is OK */
 542         return 0;
 543 }
 544
 545 struct val *
 546 op_div (a, b)
 547 struct val *a, *b;
 548 {
 549         struct val *r;
 550
 551         if (!to_integer (a) || !to_integer (b)) {
 552                 errx (2, "non-numeric argument");
 553         }
 554
 555         if (b->u.i == 0) {
 556                 errx (2, "division by zero");
 557         }
 558
 559         r = make_integer (/*(quad_t)*/(a->u.i / b->u.i));
 560         if (chk_div (a->u.i, b->u.i)) {
 561                 errx (2, "overflow");
 562         }
 563         free_value (a);
 564         free_value (b);
 565         return r;
 566 }
 567
 568 struct val *
 569 op_rem (a, b)
 570 struct val *a, *b;
 571 {
 572         struct val *r;
 573
 574         if (!to_integer (a) || !to_integer (b)) {
 575                 errx (2, "non-numeric argument");
 576         }
 577
 578         if (b->u.i == 0) {
 579                 errx (2, "division by zero");
 580         }
 581
 582         r = make_integer (/*(quad_t)*/(a->u.i % b->u.i));
 583         /* chk_rem necessary ??? */
 584         free_value (a);
 585         free_value (b);
 586         return r;
 587 }
 588
 589 struct val *
 590 op_colon (a, b)
 591 struct val *a, *b;
 592 {
 593         regex_t rp;
 594         regmatch_t rm[2];
 595         char errbuf[256];
 596         int eval;
 597         struct val *v;
 598
 599         /* coerce to both arguments to strings */
 600         to_string(a);
 601         to_string(b);
 602
 603         /* compile regular expression */
 604         if ((eval = regcomp (&rp, b->u.s, 0)) != 0) {
 605                 regerror (eval, &rp, errbuf, sizeof(errbuf));
 606                 errx (2, "%s", errbuf);
 607         }
 608
 609         /* compare string against pattern */
 610         /* remember that patterns are anchored to the beginning of the line */
 611         if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) {
 612                 if (rm[1].rm_so >= 0) {
 613                         *(a->u.s + rm[1].rm_eo) = '\0';
 614                         v = make_str (a->u.s + rm[1].rm_so);
 615
 616                 } else {
 617                         v = make_integer ((quad_t)(rm[0].rm_eo - rm[0].rm_so));
 618                 }
 619         } else {
 620                 if (rp.re_nsub == 0) {
 621                         v = make_integer ((quad_t)0);
 622                 } else {
 623                         v = make_str ("");
 624                 }
 625         }
 626
 627         /* free arguments and pattern buffer */
 628         free_value (a);
 629         free_value (b);
 630         regfree (&rp);
 631
 632         return v;
 633 }