src/expr.c

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