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