src/expr.c

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