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