src/expr.c

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