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 (void);
  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 ();
 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       return v->u.s[0] == '\0' || strcmp (v->u.s, "0") == 0;
 283     default:
 284       abort ();
 285     }
 286 }
 287
 288 /* Coerce V to a string value (can't fail).  */
 289
 290 static void
 291 tostring (VALUE *v)
 292 {
 293   char buf[INT_STRLEN_BOUND (intmax_t) + 1];
 294
 295   switch (v->type)
 296     {
 297     case integer:
 298       v->u.s = xstrdup (imaxtostr (v->u.i, buf));
 299       v->type = string;
 300       break;
 301     case string:
 302       break;
 303     default:
 304       abort ();
 305     }
 306 }
 307
 308 /* Coerce V to an integer value.  Return true on success, false on failure.  */
 309
 310 static bool
 311 toarith (VALUE *v)
 312 {
 313   intmax_t i;
 314   bool neg;
 315   char *cp;
 316
 317   switch (v->type)
 318     {
 319     case integer:
 320       return true;
 321     case string:
 322       i = 0;
 323       cp = v->u.s;
 324       neg = (*cp == '-');
 325       if (neg)
 326         cp++;
 327
 328       do
 329         {
 330           if (ISDIGIT (*cp))
 331             i = i * 10 + *cp - '0';
 332           else
 333             return false;
 334         }
 335       while (*++cp);
 336
 337       free (v->u.s);
 338       v->u.i = i * (neg ? -1 : 1);
 339       v->type = integer;
 340       return true;
 341     default:
 342       abort ();
 343     }
 344 }
 345
 346 /* Return nonzero and advance if the next token matches STR exactly.
 347    STR must not be NULL.  */
 348
 349 static bool
 350 nextarg (char const *str)
 351 {
 352   if (*args == NULL)
 353     return 0;
 354   else
 355     {
 356       bool r = strcmp (*args, str) == 0;
 357       args += r;
 358       return r;
 359     }
 360 }
 361
 362 /* Return true if there no more tokens.  */
 363
 364 static bool
 365 nomoreargs (void)
 366 {
 367   return *args == 0;
 368 }
 369
 370 #ifdef EVAL_TRACE
 371 /* Print evaluation trace and args remaining.  */
 372
 373 static void
 374 trace (fxn)
 375      char *fxn;
 376 {
 377   char **a;
 378
 379   printf ("%s:", fxn);
 380   for (a = args; *a; a++)
 381     printf (" %s", *a);
 382   putchar ('\n');
 383 }
 384 #endif
 385
 386 /* Do the : operator.
 387    SV is the VALUE for the lhs (the string),
 388    PV is the VALUE for the rhs (the pattern).  */
 389
 390 static VALUE *
 391 docolon (VALUE *sv, VALUE *pv)
 392 {
 393   VALUE *v;
 394   const char *errmsg;
 395   struct re_pattern_buffer re_buffer;
 396   struct re_registers re_regs;
 397   size_t len;
 398   int matchlen;
 399
 400   tostring (sv);
 401   tostring (pv);
 402
 403   if (pv->u.s[0] == '^')
 404     {
 405       error (0, 0, _("\
 406 warning: unportable BRE: `%s': using `^' as the first character\n\
 407 of the basic regular expression is not portable; it is being ignored"),
 408              pv->u.s);
 409     }
 410
 411   len = strlen (pv->u.s);
 412   memset (&re_buffer, 0, sizeof (re_buffer));
 413   memset (&re_regs, 0, sizeof (re_regs));
 414   re_buffer.allocated = 2 * len;
 415   if (re_buffer.allocated < len)
 416     xalloc_die ();
 417   re_buffer.buffer = xmalloc (re_buffer.allocated);
 418   re_buffer.translate = 0;
 419   re_syntax_options = RE_SYNTAX_POSIX_BASIC;
 420   errmsg = re_compile_pattern (pv->u.s, len, &re_buffer);
 421   if (errmsg)
 422     error (EXPR_FAILURE, 0, "%s", errmsg);
 423
 424   matchlen = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
 425   if (0 <= matchlen)
 426     {
 427       /* Were \(...\) used? */
 428       if (re_buffer.re_nsub > 0)/* was (re_regs.start[1] >= 0) */
 429         {
 430           sv->u.s[re_regs.end[1]] = '\0';
 431           v = str_value (sv->u.s + re_regs.start[1]);
 432         }
 433       else
 434         v = int_value (matchlen);
 435     }
 436   else
 437     {
 438       /* Match failed -- return the right kind of null.  */
 439       if (re_buffer.re_nsub > 0)
 440         v = str_value ("");
 441       else
 442         v = int_value (0);
 443     }
 444   free (re_buffer.buffer);
 445   return v;
 446 }
 447
 448 /* Handle bare operands and ( expr ) syntax.  */
 449
 450 static VALUE *
 451 eval7 (void)
 452 {
 453   VALUE *v;
 454
 455 #ifdef EVAL_TRACE
 456   trace ("eval7");
 457 #endif
 458   if (nomoreargs ())
 459     syntax_error ();
 460
 461   if (nextarg ("("))
 462     {
 463       v = eval ();
 464       if (!nextarg (")"))
 465         syntax_error ();
 466       return v;
 467     }
 468
 469   if (nextarg (")"))
 470     syntax_error ();
 471
 472   return str_value (*args++);
 473 }
 474
 475 /* Handle match, substr, index, and length keywords, and quoting "+".  */
 476
 477 static VALUE *
 478 eval6 (void)
 479 {
 480   VALUE *l;
 481   VALUE *r;
 482   VALUE *v;
 483   VALUE *i1;
 484   VALUE *i2;
 485
 486 #ifdef EVAL_TRACE
 487   trace ("eval6");
 488 #endif
 489   if (nextarg ("+"))
 490     {
 491       if (nomoreargs ())
 492         syntax_error ();
 493       return str_value (*args++);
 494     }
 495   else if (nextarg ("length"))
 496     {
 497       r = eval6 ();
 498       tostring (r);
 499       v = int_value (strlen (r->u.s));
 500       freev (r);
 501       return v;
 502     }
 503   else if (nextarg ("match"))
 504     {
 505       l = eval6 ();
 506       r = eval6 ();
 507       v = docolon (l, r);
 508       freev (l);
 509       freev (r);
 510       return v;
 511     }
 512   else if (nextarg ("index"))
 513     {
 514       l = eval6 ();
 515       r = eval6 ();
 516       tostring (l);
 517       tostring (r);
 518       v = int_value (strcspn (l->u.s, r->u.s) + 1);
 519       if (v->u.i == strlen (l->u.s) + 1)
 520         v->u.i = 0;
 521       freev (l);
 522       freev (r);
 523       return v;
 524     }
 525   else if (nextarg ("substr"))
 526     {
 527       l = eval6 ();
 528       i1 = eval6 ();
 529       i2 = eval6 ();
 530       tostring (l);
 531       if (!toarith (i1) || !toarith (i2)
 532           || strlen (l->u.s) < i1->u.i
 533           || i1->u.i <= 0 || i2->u.i <= 0)
 534         v = str_value ("");
 535       else
 536         {
 537           v = NEW (VALUE);
 538           v->type = string;
 539           v->u.s = strncpy (xmalloc (i2->u.i + 1),
 540                             l->u.s + i1->u.i - 1, i2->u.i);
 541           v->u.s[i2->u.i] = 0;
 542         }
 543       freev (l);
 544       freev (i1);
 545       freev (i2);
 546       return v;
 547     }
 548   else
 549     return eval7 ();
 550 }
 551
 552 /* Handle : operator (pattern matching).
 553    Calls docolon to do the real work.  */
 554
 555 static VALUE *
 556 eval5 (void)
 557 {
 558   VALUE *l;
 559   VALUE *r;
 560   VALUE *v;
 561
 562 #ifdef EVAL_TRACE
 563   trace ("eval5");
 564 #endif
 565   l = eval6 ();
 566   while (1)
 567     {
 568       if (nextarg (":"))
 569         {
 570           r = eval6 ();
 571           v = docolon (l, r);
 572           freev (l);
 573           freev (r);
 574           l = v;
 575         }
 576       else
 577         return l;
 578     }
 579 }
 580
 581 /* Handle *, /, % operators.  */
 582
 583 static VALUE *
 584 eval4 (void)
 585 {
 586   VALUE *l;
 587   VALUE *r;
 588   enum { multiply, divide, mod } fxn;
 589   intmax_t val;
 590
 591 #ifdef EVAL_TRACE
 592   trace ("eval4");
 593 #endif
 594   l = eval5 ();
 595   while (1)
 596     {
 597       if (nextarg ("*"))
 598         fxn = multiply;
 599       else if (nextarg ("/"))
 600         fxn = divide;
 601       else if (nextarg ("%"))
 602         fxn = mod;
 603       else
 604         return l;
 605       r = eval5 ();
 606       if (!toarith (l) || !toarith (r))
 607         error (EXPR_FAILURE, 0, _("non-numeric argument"));
 608       if (fxn == multiply)
 609         val = l->u.i * r->u.i;
 610       else
 611         {
 612           if (r->u.i == 0)
 613             error (EXPR_FAILURE, 0, _("division by zero"));
 614           val = fxn == divide ? l->u.i / r->u.i : l->u.i % r->u.i;
 615         }
 616       freev (l);
 617       freev (r);
 618       l = int_value (val);
 619     }
 620 }
 621
 622 /* Handle +, - operators.  */
 623
 624 static VALUE *
 625 eval3 (void)
 626 {
 627   VALUE *l;
 628   VALUE *r;
 629   enum { plus, minus } fxn;
 630   intmax_t val;
 631
 632 #ifdef EVAL_TRACE
 633   trace ("eval3");
 634 #endif
 635   l = eval4 ();
 636   while (1)
 637     {
 638       if (nextarg ("+"))
 639         fxn = plus;
 640       else if (nextarg ("-"))
 641         fxn = minus;
 642       else
 643         return l;
 644       r = eval4 ();
 645       if (!toarith (l) || !toarith (r))
 646         error (EXPR_FAILURE, 0, _("non-numeric argument"));
 647       val = fxn == plus ? l->u.i + r->u.i : l->u.i - r->u.i;
 648       freev (l);
 649       freev (r);
 650       l = int_value (val);
 651     }
 652 }
 653
 654 /* Handle comparisons.  */
 655
 656 static VALUE *
 657 eval2 (void)
 658 {
 659   VALUE *l;
 660   VALUE *r;
 661   enum
 662   {
 663     less_than, less_equal, equal, not_equal, greater_equal, greater_than
 664   } fxn;
 665   bool val;
 666   intmax_t lval;
 667   intmax_t rval;
 668   int collation_errno;
 669   char *collation_arg1;
 670
 671 #ifdef EVAL_TRACE
 672   trace ("eval2");
 673 #endif
 674   l = eval3 ();
 675   while (1)
 676     {
 677       if (nextarg ("<"))
 678         fxn = less_than;
 679       else if (nextarg ("<="))
 680         fxn = less_equal;
 681       else if (nextarg ("=") || nextarg ("=="))
 682         fxn = equal;
 683       else if (nextarg ("!="))
 684         fxn = not_equal;
 685       else if (nextarg (">="))
 686         fxn = greater_equal;
 687       else if (nextarg (">"))
 688         fxn = greater_than;
 689       else
 690         return l;
 691       r = eval3 ();
 692       tostring (l);
 693       tostring (r);
 694
 695       /* Save the first arg to strcoll, in case we need its value for
 696          a diagnostic later.  This is needed because 'toarith' might
 697          free the first arg.  */
 698       collation_arg1 = xstrdup (l->u.s);
 699
 700       errno = 0;
 701       lval = strcoll (collation_arg1, r->u.s);
 702       collation_errno = errno;
 703       rval = 0;
 704       if (toarith (l) && toarith (r))
 705         {
 706           lval = l->u.i;
 707           rval = r->u.i;
 708         }
 709       else if (collation_errno)
 710         {
 711           error (0, collation_errno, _("string comparison failed"));
 712           error (0, 0, _("Set LC_ALL='C' to work around the problem."));
 713           error (EXPR_FAILURE, 0,
 714                  _("The strings compared were %s and %s."),
 715                  quotearg_n_style (0, locale_quoting_style, collation_arg1),
 716                  quotearg_n_style (1, locale_quoting_style, r->u.s));
 717         }
 718
 719       switch (fxn)
 720         {
 721         case less_than:     val = (lval <  rval); break;
 722         case less_equal:    val = (lval <= rval); break;
 723         case equal:         val = (lval == rval); break;
 724         case not_equal:     val = (lval != rval); break;
 725         case greater_equal: val = (lval >= rval); break;
 726         case greater_than:  val = (lval >  rval); break;
 727         default: abort ();
 728         }
 729       freev (l);
 730       freev (r);
 731       free (collation_arg1);
 732       l = int_value (val);
 733     }
 734 }
 735
 736 /* Handle &.  */
 737
 738 static VALUE *
 739 eval1 (void)
 740 {
 741   VALUE *l;
 742   VALUE *r;
 743
 744 #ifdef EVAL_TRACE
 745   trace ("eval1");
 746 #endif
 747   l = eval2 ();
 748   while (1)
 749     {
 750       if (nextarg ("&"))
 751         {
 752           r = eval2 ();
 753           if (null (l) || null (r))
 754             {
 755               freev (l);
 756               freev (r);
 757               l = int_value (0);
 758             }
 759           else
 760             freev (r);
 761         }
 762       else
 763         return l;
 764     }
 765 }
 766
 767 /* Handle |.  */
 768
 769 static VALUE *
 770 eval (void)
 771 {
 772   VALUE *l;
 773   VALUE *r;
 774
 775 #ifdef EVAL_TRACE
 776   trace ("eval");
 777 #endif
 778   l = eval1 ();
 779   while (1)
 780     {
 781       if (nextarg ("|"))
 782         {
 783           r = eval1 ();
 784           if (null (l))
 785             {
 786               freev (l);
 787               l = r;
 788             }
 789           else
 790             freev (r);
 791         }
 792       else
 793         return l;
 794     }
 795 }