src/expr.c

   1 /* expr -- evaluate expressions.
   2    Copyright (C) 86, 91, 92, 93, 94, 1995 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Author: Mike Parker.
  19
  20    This program evaluates expressions.  Each token (operator, operand,
  21    parenthesis) of the expression must be a seperate argument.  The
  22    parser used is a reasonably general one, though any incarnation of
  23    it is language-specific.  It is especially nice for expressions.
  24
  25    No parse tree is needed; a new node is evaluated immediately.
  26    One function can handle multiple operators all of equal precedence,
  27    provided they all associate ((x op x) op x).
  28
  29    Define EVAL_TRACE to print an evaluation trace.  */
  30
  31 #include <config.h>
  32 #include <stdio.h>
  33 #include <sys/types.h>
  34 #include <regex.h>
  35
  36 #include "system.h"
  37 #include "version.h"
  38 #include "long-options.h"
  39 #include "error.h"
  40
  41 #define NEW(type) ((type *) xmalloc (sizeof (type)))
  42 #define OLD(x) free ((char *) x)
  43
  44 /* The kinds of value we can have.  */
  45 enum valtype
  46 {
  47   integer,
  48   string
  49 };
  50 typedef enum valtype TYPE;
  51
  52 /* A value is.... */
  53 struct valinfo
  54 {
  55   TYPE type;                    /* Which kind. */
  56   union
  57   {                             /* The value itself. */
  58     int i;
  59     char *s;
  60   } u;
  61 };
  62 typedef struct valinfo VALUE;
  63
  64 /* The arguments given to the program, minus the program name.  */
  65 static char **args;
  66
  67 /* The name this program was run with. */
  68 char *program_name;
  69
  70 char *xstrdup ();
  71 char *strstr ();
  72 char *xmalloc ();
  73
  74 static VALUE *docolon ();
  75 static VALUE *eval ();
  76 static VALUE *int_value ();
  77 static VALUE *str_value ();
  78 static int isstring ();
  79 static int nextarg ();
  80 static int nomoreargs ();
  81 static int null ();
  82 static int toarith ();
  83 static void freev ();
  84 static void printv ();
  85 static void tostring ();
  86
  87 #ifdef EVAL_TRACE
  88 static void trace ();
  89 #endif
  90
  91 static void
  92 usage (status)
  93      int status;
  94 {
  95   if (status != 0)
  96     fprintf (stderr, "Try `%s --help' for more information.\n",
  97              program_name);
  98   else
  99     {
 100       printf ("\
 101 Usage: %s EXPRESSION\n\
 102   or:  %s OPTION\n\
 103 ",
 104               program_name, program_name);
 105       printf ("\
 106 \n\
 107   --help      display this help and exit\n\
 108   --version   output version information and exit\n\
 109 \n\
 110 ");
 111       printf ("\
 112 EXPRESSION value is written on standard output.  A white line\n\
 113 separates increasing precedence groups.  EXPRESSION may be:\n\
 114 \n\
 115   ARG1 | ARG2       ARG1 if it is neither null nor 0, otherwise ARG2\n\
 116 \n\
 117   ARG1 & ARG2       ARG1 if neither argument is null or 0, otherwise 0\n\
 118 \n\
 119   ARG1 < ARG2       ARG1 is less than ARG2\n\
 120   ARG1 <= ARG2      ARG1 is less than or equal to ARG2\n\
 121   ARG1 = ARG2       ARG1 is equal to ARG2\n\
 122   ARG1 != ARG2      ARG1 is unequal to ARG2\n\
 123   ARG1 >= ARG2      ARG1 is greater than or equal to ARG2\n\
 124   ARG1 > ARG2       ARG1 is greater than ARG2\n\
 125 \n\
 126   ARG1 + ARG2       arithmetic sum of ARG1 and ARG2\n\
 127   ARG1 - ARG2       arithmetic difference of ARG1 and ARG2\n\
 128 \n\
 129   ARG1 * ARG2       arithmetic product of ARG1 and ARG2\n\
 130   ARG1 / ARG2       arithmetic quotient of ARG1 divided by ARG2\n\
 131   ARG1 %% ARG2       arithmetic remainder of ARG1 divided by ARG2\n\
 132 \n\
 133   STRING : REGEXP   anchored pattern match of REGEXP in STRING\n\
 134 \n\
 135   match STRING REGEXP        same as STRING : REGEXP\n\
 136   substr STRING POS LENGTH   substring of STRING, POS counted from 1\n\
 137   index STRING CHARS         index in STRING where any CHARS is found, or 0\n\
 138   length STRING              length of STRING\n\
 139 \n\
 140   ( EXPRESSION )             value of EXPRESSION\n\
 141 ");
 142       printf ("\
 143 \n\
 144 Beware that some operators need to be escaped by backslashes for shells.\n\
 145 Comparisons are arithmetic if both ARGs are numbers, else lexicographical.\n\
 146 Pattern matches return the string matched between \\( and \\) or null; if\n\
 147 \\( and \\) are not used, they return the number of characters matched or 0.\n\
 148 ");
 149     }
 150   exit (status);
 151 }
 152
 153 void
 154 main (argc, argv)
 155      int argc;
 156      char **argv;
 157 {
 158   VALUE *v;
 159
 160   program_name = argv[0];
 161
 162   parse_long_options (argc, argv, "expr", version_string, usage);
 163
 164   if (argc == 1)
 165     {
 166       error (0, 0, "too few arguments");
 167       usage (1);
 168     }
 169
 170   args = argv + 1;
 171
 172   v = eval ();
 173   if (!nomoreargs ())
 174     error (2, 0, "syntax error");
 175   printv (v);
 176
 177   exit (null (v));
 178 }
 179
 180 /* Return a VALUE for I.  */
 181
 182 static VALUE *
 183 int_value (i)
 184      int i;
 185 {
 186   VALUE *v;
 187
 188   v = NEW (VALUE);
 189   v->type = integer;
 190   v->u.i = i;
 191   return v;
 192 }
 193
 194 /* Return a VALUE for S.  */
 195
 196 static VALUE *
 197 str_value (s)
 198      char *s;
 199 {
 200   VALUE *v;
 201
 202   v = NEW (VALUE);
 203   v->type = string;
 204   v->u.s = xstrdup (s);
 205   return v;
 206 }
 207
 208 /* Free VALUE V, including structure components.  */
 209
 210 static void
 211 freev (v)
 212      VALUE *v;
 213 {
 214   if (v->type == string)
 215     free (v->u.s);
 216   OLD (v);
 217 }
 218
 219 /* Print VALUE V.  */
 220
 221 static void
 222 printv (v)
 223      VALUE *v;
 224 {
 225   switch (v->type)
 226     {
 227     case integer:
 228       printf ("%d\n", v->u.i);
 229       break;
 230     case string:
 231       printf ("%s\n", v->u.s);
 232       break;
 233     default:
 234       abort ();
 235     }
 236 }
 237
 238 /* Return nonzero if V is a null-string or zero-number.  */
 239
 240 static int
 241 null (v)
 242      VALUE *v;
 243 {
 244   switch (v->type)
 245     {
 246     case integer:
 247       return v->u.i == 0;
 248     case string:
 249       return v->u.s[0] == '\0' || strcmp(v->u.s, "0") == 0;
 250     default:
 251       abort ();
 252     }
 253 }
 254
 255 /* Return nonzero if V is a string value.  */
 256
 257 static int
 258 isstring (v)
 259      VALUE *v;
 260 {
 261   return v->type == string;
 262 }
 263
 264 /* Coerce V to a string value (can't fail).  */
 265
 266 static void
 267 tostring (v)
 268      VALUE *v;
 269 {
 270   char *temp;
 271
 272   switch (v->type)
 273     {
 274     case integer:
 275       temp = xmalloc (4 * (sizeof (int) / sizeof (char)));
 276       sprintf (temp, "%d", v->u.i);
 277       v->u.s = temp;
 278       v->type = string;
 279       break;
 280     case string:
 281       break;
 282     default:
 283       abort ();
 284     }
 285 }
 286
 287 /* Coerce V to an integer value.  Return 1 on success, 0 on failure.  */
 288
 289 static int
 290 toarith (v)
 291      VALUE *v;
 292 {
 293   int i;
 294   int neg;
 295   char *cp;
 296
 297   switch (v->type)
 298     {
 299     case integer:
 300       return 1;
 301     case string:
 302       i = 0;
 303       cp = v->u.s;
 304       /* Don't interpret the empty string as an integer.  */
 305       if (*cp == 0)
 306         return 0;
 307       neg = (*cp == '-');
 308       if (neg)
 309         cp++;
 310       for (; *cp; cp++)
 311         {
 312           if (ISDIGIT (*cp))
 313             i = i * 10 + *cp - '0';
 314           else
 315             return 0;
 316         }
 317       free (v->u.s);
 318       v->u.i = i * (neg ? -1 : 1);
 319       v->type = integer;
 320       return 1;
 321     default:
 322       abort ();
 323     }
 324 }
 325
 326 /* Return nonzero if the next token matches STR exactly.
 327    STR must not be NULL.  */
 328
 329 static int
 330 nextarg (str)
 331      char *str;
 332 {
 333   if (*args == NULL)
 334     return 0;
 335   return strcmp (*args, str) == 0;
 336 }
 337
 338 /* Return nonzero if there no more tokens.  */
 339
 340 static int
 341 nomoreargs ()
 342 {
 343   return *args == 0;
 344 }
 345
 346 /* The comparison operator handling functions.  */
 347
 348 #define cmpf(name, rel)                         \
 349 static                                          \
 350 int name (l, r) VALUE *l; VALUE *r;             \
 351 {                                               \
 352   if (isstring (l) || isstring (r))             \
 353     {                                           \
 354        tostring (l);                            \
 355        tostring (r);                            \
 356        return strcmp (l->u.s, r->u.s) rel 0;    \
 357     }                                           \
 358  else                                           \
 359    return l->u.i rel r->u.i;                    \
 360 }
 361 cmpf (less_than, <)
 362 cmpf (less_equal, <=)
 363 cmpf (equal, ==)
 364 cmpf (not_equal, !=)
 365 cmpf (greater_equal, >=)
 366 cmpf (greater_than, >)
 367
 368 #undef cmpf
 369
 370 /* The arithmetic operator handling functions.  */
 371
 372 #define arithf(name, op)                        \
 373 static                                          \
 374 int name (l, r) VALUE *l; VALUE *r;             \
 375 {                                               \
 376   if (!toarith (l) || !toarith (r))             \
 377     error (2, 0, "non-numeric argument");       \
 378   return l->u.i op r->u.i;                      \
 379 }
 380
 381 #define arithdivf(name, op)                     \
 382 int name (l, r) VALUE *l; VALUE *r;             \
 383 {                                               \
 384   if (!toarith (l) || !toarith (r))             \
 385     error (2, 0, "non-numeric argument");       \
 386   if (r->u.i == 0)                              \
 387     error (2, 0, "division by zero");           \
 388   return l->u.i op r->u.i;                      \
 389 }
 390
 391 arithf (plus, +)
 392 arithf (minus, -)
 393 arithf (multiply, *)
 394 arithdivf (divide, /)
 395 arithdivf (mod, %)
 396
 397 #undef arithf
 398 #undef arithdivf
 399
 400 #ifdef EVAL_TRACE
 401 /* Print evaluation trace and args remaining.  */
 402
 403 static void
 404 trace (fxn)
 405      char *fxn;
 406 {
 407   char **a;
 408
 409   printf ("%s:", fxn);
 410   for (a = args; *a; a++)
 411     printf (" %s", *a);
 412   putchar ('\n');
 413 }
 414 #endif
 415
 416 /* Do the : operator.
 417    SV is the VALUE for the lhs (the string),
 418    PV is the VALUE for the rhs (the pattern).  */
 419
 420 static VALUE *
 421 docolon (sv, pv)
 422      VALUE *sv;
 423      VALUE *pv;
 424 {
 425   VALUE *v;
 426   const char *errmsg;
 427   struct re_pattern_buffer re_buffer;
 428   struct re_registers re_regs;
 429   int len;
 430
 431   tostring (sv);
 432   tostring (pv);
 433
 434   len = strlen (pv->u.s);
 435   memset (&re_buffer, 0, sizeof (re_buffer));
 436   memset (&re_regs, 0, sizeof (re_regs));
 437   re_buffer.allocated = 2 * len;
 438   re_buffer.buffer = (unsigned char *) xmalloc (re_buffer.allocated);
 439   re_buffer.translate = 0;
 440   errmsg = re_compile_pattern (pv->u.s, len, &re_buffer);
 441   if (errmsg)
 442     error (2, 0, "%s", errmsg);
 443
 444   len = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
 445   if (len >= 0)
 446     {
 447       /* Were \(...\) used? */
 448       if (re_buffer.re_nsub > 0)/* was (re_regs.start[1] >= 0) */
 449         {
 450           sv->u.s[re_regs.end[1]] = '\0';
 451           v = str_value (sv->u.s + re_regs.start[1]);
 452         }
 453       else
 454         v = int_value (len);
 455     }
 456   else
 457     {
 458       /* Match failed -- return the right kind of null.  */
 459       if (strstr (pv->u.s, "\\("))
 460         v = str_value ("");
 461       else
 462         v = int_value (0);
 463     }
 464   free (re_buffer.buffer);
 465   return v;
 466 }
 467
 468 /* Handle bare operands and ( expr ) syntax.  */
 469
 470 static VALUE *
 471 eval7 ()
 472 {
 473   VALUE *v;
 474
 475 #ifdef EVAL_TRACE
 476   trace ("eval7");
 477 #endif
 478   if (nomoreargs ())
 479     error (2, 0, "syntax error");
 480
 481   if (nextarg ("("))
 482     {
 483       args++;
 484       v = eval ();
 485       if (!nextarg (")"))
 486         error (2, 0, "syntax error");
 487       args++;
 488       return v;
 489     }
 490
 491   if (nextarg (")"))
 492     error (2, 0, "syntax error");
 493
 494   return str_value (*args++);
 495 }
 496
 497 /* Handle match, substr, index, and length keywords.  */
 498
 499 static VALUE *
 500 eval6 ()
 501 {
 502   VALUE *l;
 503   VALUE *r;
 504   VALUE *v;
 505   VALUE *i1;
 506   VALUE *i2;
 507
 508 #ifdef EVAL_TRACE
 509   trace ("eval6");
 510 #endif
 511   if (nextarg ("length"))
 512     {
 513       args++;
 514       r = eval6 ();
 515       tostring (r);
 516       v = int_value (strlen (r->u.s));
 517       freev (r);
 518       return v;
 519     }
 520   else if (nextarg ("match"))
 521     {
 522       args++;
 523       l = eval6 ();
 524       r = eval6 ();
 525       v = docolon (l, r);
 526       freev (l);
 527       freev (r);
 528       return v;
 529     }
 530   else if (nextarg ("index"))
 531     {
 532       args++;
 533       l = eval6 ();
 534       r = eval6 ();
 535       tostring (l);
 536       tostring (r);
 537       v = int_value (strcspn (l->u.s, r->u.s) + 1);
 538       if (v->u.i == strlen (l->u.s) + 1)
 539         v->u.i = 0;
 540       freev (l);
 541       freev (r);
 542       return v;
 543     }
 544   else if (nextarg ("substr"))
 545     {
 546       args++;
 547       l = eval6 ();
 548       i1 = eval6 ();
 549       i2 = eval6 ();
 550       tostring (l);
 551       if (!toarith (i1) || !toarith (i2)
 552           || i1->u.i > strlen (l->u.s)
 553           || i1->u.i <= 0 || i2->u.i <= 0)
 554         v = str_value ("");
 555       else
 556         {
 557           v = NEW (VALUE);
 558           v->type = string;
 559           v->u.s = strncpy ((char *) xmalloc (i2->u.i + 1),
 560                             l->u.s + i1->u.i - 1, i2->u.i);
 561           v->u.s[i2->u.i] = 0;
 562         }
 563       freev (l);
 564       freev (i1);
 565       freev (i2);
 566       return v;
 567     }
 568   else
 569     return eval7 ();
 570 }
 571
 572 /* Handle : operator (pattern matching).
 573    Calls docolon to do the real work.  */
 574
 575 static VALUE *
 576 eval5 ()
 577 {
 578   VALUE *l;
 579   VALUE *r;
 580   VALUE *v;
 581
 582 #ifdef EVAL_TRACE
 583   trace ("eval5");
 584 #endif
 585   l = eval6 ();
 586   while (1)
 587     {
 588       if (nextarg (":"))
 589         {
 590           args++;
 591           r = eval6 ();
 592           v = docolon (l, r);
 593           freev (l);
 594           freev (r);
 595           l = v;
 596         }
 597       else
 598         return l;
 599     }
 600 }
 601
 602 /* Handle *, /, % operators.  */
 603
 604 static VALUE *
 605 eval4 ()
 606 {
 607   VALUE *l;
 608   VALUE *r;
 609   int (*fxn) ();
 610   int val;
 611
 612 #ifdef EVAL_TRACE
 613   trace ("eval4");
 614 #endif
 615   l = eval5 ();
 616   while (1)
 617     {
 618       if (nextarg ("*"))
 619         fxn = multiply;
 620       else if (nextarg ("/"))
 621         fxn = divide;
 622       else if (nextarg ("%"))
 623         fxn = mod;
 624       else
 625         return l;
 626       args++;
 627       r = eval5 ();
 628       val = (*fxn) (l, r);
 629       freev (l);
 630       freev (r);
 631       l = int_value (val);
 632     }
 633 }
 634
 635 /* Handle +, - operators.  */
 636
 637 static VALUE *
 638 eval3 ()
 639 {
 640   VALUE *l;
 641   VALUE *r;
 642   int (*fxn) ();
 643   int val;
 644
 645 #ifdef EVAL_TRACE
 646   trace ("eval3");
 647 #endif
 648   l = eval4 ();
 649   while (1)
 650     {
 651       if (nextarg ("+"))
 652         fxn = plus;
 653       else if (nextarg ("-"))
 654         fxn = minus;
 655       else
 656         return l;
 657       args++;
 658       r = eval4 ();
 659       val = (*fxn) (l, r);
 660       freev (l);
 661       freev (r);
 662       l = int_value (val);
 663     }
 664 }
 665
 666 /* Handle comparisons.  */
 667
 668 static VALUE *
 669 eval2 ()
 670 {
 671   VALUE *l;
 672   VALUE *r;
 673   int (*fxn) ();
 674   int val;
 675
 676 #ifdef EVAL_TRACE
 677   trace ("eval2");
 678 #endif
 679   l = eval3 ();
 680   while (1)
 681     {
 682       if (nextarg ("<"))
 683         fxn = less_than;
 684       else if (nextarg ("<="))
 685         fxn = less_equal;
 686       else if (nextarg ("=") || nextarg ("=="))
 687         fxn = equal;
 688       else if (nextarg ("!="))
 689         fxn = not_equal;
 690       else if (nextarg (">="))
 691         fxn = greater_equal;
 692       else if (nextarg (">"))
 693         fxn = greater_than;
 694       else
 695         return l;
 696       args++;
 697       r = eval3 ();
 698       toarith (l);
 699       toarith (r);
 700       val = (*fxn) (l, r);
 701       freev (l);
 702       freev (r);
 703       l = int_value (val);
 704     }
 705 }
 706
 707 /* Handle &.  */
 708
 709 static VALUE *
 710 eval1 ()
 711 {
 712   VALUE *l;
 713   VALUE *r;
 714
 715 #ifdef EVAL_TRACE
 716   trace ("eval1");
 717 #endif
 718   l = eval2 ();
 719   while (1)
 720     {
 721       if (nextarg ("&"))
 722         {
 723           args++;
 724           r = eval2 ();
 725           if (null (l) || null (r))
 726             {
 727               freev (l);
 728               freev (r);
 729               l = int_value (0);
 730             }
 731           else
 732             freev (r);
 733         }
 734       else
 735         return l;
 736     }
 737 }
 738
 739 /* Handle |.  */
 740
 741 static VALUE *
 742 eval ()
 743 {
 744   VALUE *l;
 745   VALUE *r;
 746
 747 #ifdef EVAL_TRACE
 748   trace ("eval");
 749 #endif
 750   l = eval1 ();
 751   while (1)
 752     {
 753       if (nextarg ("|"))
 754         {
 755           args++;
 756           r = eval1 ();
 757           if (null (l))
 758             {
 759               freev (l);
 760               l = r;
 761             }
 762           else
 763             freev (r);
 764         }
 765       else
 766         return l;
 767     }
 768 }