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, (char**)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 int
 248 main (int argc __unused, char **argv)
 249 {
 250         setlocale (LC_ALL, "");
 251
 252         av = argv + 1;
 253
 254         yyparse ();
 255
 256         if (result->type == integer)
 257                 printf ("%lld\n", (long long)result->u.i);
 258         else
 259                 printf ("%s\n", result->u.s);
 260
 261         return (is_zero_or_null (result));
 262 }
 263
 264 int
 265 yyerror(const char *s __unused)
 266 {
 267         errx (2, "syntax error");
 268 }
 269
 270
 271 struct val *
 272 op_or(struct val *a, struct val *b)
 273 {
 274         if (is_zero_or_null (a)) {
 275                 free_value (a);
 276                 return (b);
 277         } else {
 278                 free_value (b);
 279                 return (a);
 280         }
 281 }
 282
 283 struct val *
 284 op_and(struct val *a, struct val *b)
 285 {
 286         if (is_zero_or_null (a) || is_zero_or_null (b)) {
 287                 free_value (a);
 288                 free_value (b);
 289                 return (make_integer ((quad_t)0));
 290         } else {
 291                 free_value (b);
 292                 return (a);
 293         }
 294 }
 295
 296 struct val *
 297 op_eq(struct val *a, struct val *b)
 298 {
 299         struct val *r;
 300
 301         if (isstring (a) || isstring (b)) {
 302                 to_string (a);
 303                 to_string (b);
 304                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) == 0));
 305         } else {
 306                 to_integer(a);
 307                 to_integer(b);
 308                 r = make_integer ((quad_t)(a->u.i == b->u.i));
 309         }
 310
 311         free_value (a);
 312         free_value (b);
 313         return r;
 314 }
 315
 316 struct val *
 317 op_gt(struct val *a, struct val *b)
 318 {
 319         struct val *r;
 320
 321         if (isstring (a) || isstring (b)) {
 322                 to_string (a);
 323                 to_string (b);
 324                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) > 0));
 325         } else {
 326                 to_integer(a);
 327                 to_integer(b);
 328                 r = make_integer ((quad_t)(a->u.i > b->u.i));
 329         }
 330
 331         free_value (a);
 332         free_value (b);
 333         return r;
 334 }
 335
 336 struct val *
 337 op_lt(struct val *a, struct val *b)
 338 {
 339         struct val *r;
 340
 341         if (isstring (a) || isstring (b)) {
 342                 to_string (a);
 343                 to_string (b);
 344                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) < 0));
 345         } else {
 346                 to_integer(a);
 347                 to_integer(b);
 348                 r = make_integer ((quad_t)(a->u.i < b->u.i));
 349         }
 350
 351         free_value (a);
 352         free_value (b);
 353         return r;
 354 }
 355
 356 struct val *
 357 op_ge(struct val *a, struct val *b)
 358 {
 359         struct val *r;
 360
 361         if (isstring (a) || isstring (b)) {
 362                 to_string (a);
 363                 to_string (b);
 364                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) >= 0));
 365         } else {
 366                 to_integer(a);
 367                 to_integer(b);
 368                 r = make_integer ((quad_t)(a->u.i >= b->u.i));
 369         }
 370
 371         free_value (a);
 372         free_value (b);
 373         return r;
 374 }
 375
 376 struct val *
 377 op_le(struct val *a, struct val *b)
 378 {
 379         struct val *r;
 380
 381         if (isstring (a) || isstring (b)) {
 382                 to_string (a);
 383                 to_string (b);
 384                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) <= 0));
 385         } else {
 386                 to_integer(a);
 387                 to_integer(b);
 388                 r = make_integer ((quad_t)(a->u.i <= b->u.i));
 389         }
 390
 391         free_value (a);
 392         free_value (b);
 393         return r;
 394 }
 395
 396 struct val *
 397 op_ne(struct val *a, struct val *b)
 398 {
 399         struct val *r;
 400
 401         if (isstring (a) || isstring (b)) {
 402                 to_string (a);
 403                 to_string (b);
 404                 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) != 0));
 405         } else {
 406                 to_integer(a);
 407                 to_integer(b);
 408                 r = make_integer ((quad_t)(a->u.i != b->u.i));
 409         }
 410
 411         free_value (a);
 412         free_value (b);
 413         return r;
 414 }
 415
 416 int
 417 chk_plus(quad_t a, quad_t b, quad_t r)
 418 {
 419         /* sum of two positive numbers must be positive */
 420         if (a > 0 && b > 0 && r <= 0)
 421                 return 1;
 422         /* sum of two negative numbers must be negative */
 423         if (a < 0 && b < 0 && r >= 0)
 424                 return 1;
 425         /* all other cases are OK */
 426         return 0;
 427 }
 428
 429 struct val *
 430 op_plus(struct val *a, struct val *b)
 431 {
 432         struct val *r;
 433
 434         if (!to_integer (a) || !to_integer (b)) {
 435                 errx (2, "non-numeric argument");
 436         }
 437
 438         r = make_integer (/*(quad_t)*/(a->u.i + b->u.i));
 439         if (chk_plus (a->u.i, b->u.i, r->u.i)) {
 440                 errx (2, "overflow");
 441         }
 442         free_value (a);
 443         free_value (b);
 444         return r;
 445 }
 446
 447 int
 448 chk_minus(quad_t a, quad_t b, quad_t r)
 449 {
 450         /* special case subtraction of QUAD_MIN */
 451         if (b == QUAD_MIN) {
 452                 if (a >= 0)
 453                         return 1;
 454                 else
 455                         return 0;
 456         }
 457         /* this is allowed for b != QUAD_MIN */
 458         return chk_plus (a, -b, r);
 459 }
 460
 461 struct val *
 462 op_minus(struct val *a, struct val *b)
 463 {
 464         struct val *r;
 465
 466         if (!to_integer (a) || !to_integer (b)) {
 467                 errx (2, "non-numeric argument");
 468         }
 469
 470         r = make_integer (/*(quad_t)*/(a->u.i - b->u.i));
 471         if (chk_minus (a->u.i, b->u.i, r->u.i)) {
 472                 errx (2, "overflow");
 473         }
 474         free_value (a);
 475         free_value (b);
 476         return r;
 477 }
 478
 479 int
 480 chk_times(quad_t a, quad_t b, quad_t r)
 481 {
 482         /* special case: first operand is 0, no overflow possible */
 483         if (a == 0)
 484                 return 0;
 485         /* cerify that result of division matches second operand */
 486         if (r / a != b)
 487                 return 1;
 488         return 0;
 489 }
 490
 491 struct val *
 492 op_times(struct val *a, struct val *b)
 493 {
 494         struct val *r;
 495
 496         if (!to_integer (a) || !to_integer (b)) {
 497                 errx (2, "non-numeric argument");
 498         }
 499
 500         r = make_integer (/*(quad_t)*/(a->u.i * b->u.i));
 501         if (chk_times (a->u.i, b->u.i, r->u.i)) {
 502                 errx (2, "overflow");
 503         }
 504         free_value (a);
 505         free_value (b);
 506         return (r);
 507 }
 508
 509 int
 510 chk_div(quad_t a, quad_t b)
 511 {
 512         /* div by zero has been taken care of before */
 513         /* only QUAD_MIN / -1 causes overflow */
 514         if (a == QUAD_MIN && b == -1)
 515                 return 1;
 516         /* everything else is OK */
 517         return 0;
 518 }
 519
 520 struct val *
 521 op_div(struct val *a, struct val *b)
 522 {
 523         struct val *r;
 524
 525         if (!to_integer (a) || !to_integer (b)) {
 526                 errx (2, "non-numeric argument");
 527         }
 528
 529         if (b->u.i == 0) {
 530                 errx (2, "division by zero");
 531         }
 532
 533         r = make_integer (/*(quad_t)*/(a->u.i / b->u.i));
 534         if (chk_div (a->u.i, b->u.i)) {
 535                 errx (2, "overflow");
 536         }
 537         free_value (a);
 538         free_value (b);
 539         return r;
 540 }
 541
 542 struct val *
 543 op_rem(struct val *a, struct val *b)
 544 {
 545         struct val *r;
 546
 547         if (!to_integer (a) || !to_integer (b)) {
 548                 errx (2, "non-numeric argument");
 549         }
 550
 551         if (b->u.i == 0) {
 552                 errx (2, "division by zero");
 553         }
 554
 555         r = make_integer (/*(quad_t)*/(a->u.i % b->u.i));
 556         /* chk_rem necessary ??? */
 557         free_value (a);
 558         free_value (b);
 559         return r;
 560 }
 561
 562 struct val *
 563 op_colon(struct val *a, struct val *b)
 564 {
 565         regex_t rp;
 566         regmatch_t rm[2];
 567         char errbuf[256];
 568         int eval;
 569         struct val *v;
 570
 571         /* coerce to both arguments to strings */
 572         to_string(a);
 573         to_string(b);
 574
 575         /* compile regular expression */
 576         if ((eval = regcomp (&rp, b->u.s, 0)) != 0) {
 577                 regerror (eval, &rp, errbuf, sizeof(errbuf));
 578                 errx (2, "%s", errbuf);
 579         }
 580
 581         /* compare string against pattern */
 582         /* remember that patterns are anchored to the beginning of the line */
 583         if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) {
 584                 if (rm[1].rm_so >= 0) {
 585                         *(a->u.s + rm[1].rm_eo) = '\0';
 586                         v = make_str (a->u.s + rm[1].rm_so);
 587
 588                 } else {
 589                         v = make_integer ((quad_t)(rm[0].rm_eo - rm[0].rm_so));
 590                 }
 591         } else {
 592                 if (rp.re_nsub == 0) {
 593                         v = make_integer ((quad_t)0);
 594                 } else {
 595                         v = make_str ("");
 596                 }
 597         }
 598
 599         /* free arguments and pattern buffer */
 600         free_value (a);
 601         free_value (b);
 602         regfree (&rp);
 603
 604         return v;
 605 }