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;
 413   const char *errmsg;
 414   struct re_pattern_buffer re_buffer;
 415   struct re_registers re_regs;
 416   size_t len;
 417   int 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.allocated = 2 * len;
 434   if (re_buffer.allocated < len)
 435     xalloc_die ();
 436   re_buffer.buffer = xmalloc (re_buffer.allocated);
 437   re_buffer.translate = NULL;
 438   re_syntax_options = RE_SYNTAX_POSIX_BASIC;
 439   errmsg = re_compile_pattern (pv->u.s, len, &re_buffer);
 440   if (errmsg)
 441     error (EXPR_FAILURE, 0, "%s", errmsg);
 442
 443   matchlen = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
 444   if (0 <= matchlen)
 445     {
 446       /* Were \(...\) used? */
 447       if (re_buffer.re_nsub > 0)/* was (re_regs.start[1] >= 0) */
 448         {
 449           sv->u.s[re_regs.end[1]] = '\0';
 450           v = str_value (sv->u.s + re_regs.start[1]);
 451         }
 452       else
 453         v = int_value (matchlen);
 454     }
 455   else
 456     {
 457       /* Match failed -- return the right kind of null.  */
 458       if (re_buffer.re_nsub > 0)
 459         v = str_value ("");
 460       else
 461         v = int_value (0);
 462     }
 463   free (re_buffer.buffer);
 464   return v;
 465 }
 466
 467 /* Handle bare operands and ( expr ) syntax.  */
 468
 469 static VALUE *
 470 eval7 (bool evaluate)
 471 {
 472   VALUE *v;
 473
 474 #ifdef EVAL_TRACE
 475   trace ("eval7");
 476 #endif
 477   if (nomoreargs ())
 478     syntax_error ();
 479
 480   if (nextarg ("("))
 481     {
 482       v = eval (evaluate);
 483       if (!nextarg (")"))
 484         syntax_error ();
 485       return v;
 486     }
 487
 488   if (nextarg (")"))
 489     syntax_error ();
 490
 491   return str_value (*args++);
 492 }
 493
 494 /* Handle match, substr, index, and length keywords, and quoting "+".  */
 495
 496 static VALUE *
 497 eval6 (bool evaluate)
 498 {
 499   VALUE *l;
 500   VALUE *r;
 501   VALUE *v;
 502   VALUE *i1;
 503   VALUE *i2;
 504
 505 #ifdef EVAL_TRACE
 506   trace ("eval6");
 507 #endif
 508   if (nextarg ("+"))
 509     {
 510       if (nomoreargs ())
 511         syntax_error ();
 512       return str_value (*args++);
 513     }
 514   else if (nextarg ("length"))
 515     {
 516       r = eval6 (evaluate);
 517       tostring (r);
 518       v = int_value (strlen (r->u.s));
 519       freev (r);
 520       return v;
 521     }
 522   else if (nextarg ("match"))
 523     {
 524       l = eval6 (evaluate);
 525       r = eval6 (evaluate);
 526       if (evaluate)
 527         {
 528           v = docolon (l, r);
 529           freev (l);
 530         }
 531       else
 532         v = l;
 533       freev (r);
 534       return v;
 535     }
 536   else if (nextarg ("index"))
 537     {
 538       l = eval6 (evaluate);
 539       r = eval6 (evaluate);
 540       tostring (l);
 541       tostring (r);
 542       v = int_value (strcspn (l->u.s, r->u.s) + 1);
 543       if (v->u.i == strlen (l->u.s) + 1)
 544         v->u.i = 0;
 545       freev (l);
 546       freev (r);
 547       return v;
 548     }
 549   else if (nextarg ("substr"))
 550     {
 551       l = eval6 (evaluate);
 552       i1 = eval6 (evaluate);
 553       i2 = eval6 (evaluate);
 554       tostring (l);
 555       if (!toarith (i1) || !toarith (i2)
 556           || strlen (l->u.s) < i1->u.i
 557           || i1->u.i <= 0 || i2->u.i <= 0)
 558         v = str_value ("");
 559       else
 560         {
 561           v = xmalloc (sizeof *v);
 562           v->type = string;
 563           v->u.s = strncpy (xmalloc (i2->u.i + 1),
 564                             l->u.s + i1->u.i - 1, i2->u.i);
 565           v->u.s[i2->u.i] = 0;
 566         }
 567       freev (l);
 568       freev (i1);
 569       freev (i2);
 570       return v;
 571     }
 572   else
 573     return eval7 (evaluate);
 574 }
 575
 576 /* Handle : operator (pattern matching).
 577    Calls docolon to do the real work.  */
 578
 579 static VALUE *
 580 eval5 (bool evaluate)
 581 {
 582   VALUE *l;
 583   VALUE *r;
 584   VALUE *v;
 585
 586 #ifdef EVAL_TRACE
 587   trace ("eval5");
 588 #endif
 589   l = eval6 (evaluate);
 590   while (1)
 591     {
 592       if (nextarg (":"))
 593         {
 594           r = eval6 (evaluate);
 595           if (evaluate)
 596             {
 597               v = docolon (l, r);
 598               freev (l);
 599               l = v;
 600             }
 601           freev (r);
 602         }
 603       else
 604         return l;
 605     }
 606 }
 607
 608 /* Handle *, /, % operators.  */
 609
 610 static VALUE *
 611 eval4 (bool evaluate)
 612 {
 613   VALUE *l;
 614   VALUE *r;
 615   enum { multiply, divide, mod } fxn;
 616   intmax_t val = 0;
 617
 618 #ifdef EVAL_TRACE
 619   trace ("eval4");
 620 #endif
 621   l = eval5 (evaluate);
 622   while (1)
 623     {
 624       if (nextarg ("*"))
 625         fxn = multiply;
 626       else if (nextarg ("/"))
 627         fxn = divide;
 628       else if (nextarg ("%"))
 629         fxn = mod;
 630       else
 631         return l;
 632       r = eval5 (evaluate);
 633       if (evaluate)
 634         {
 635           if (!toarith (l) || !toarith (r))
 636             error (EXPR_FAILURE, 0, _("non-numeric argument"));
 637           if (fxn == multiply)
 638             val = l->u.i * r->u.i;
 639           else
 640             {
 641               if (r->u.i == 0)
 642                 error (EXPR_FAILURE, 0, _("division by zero"));
 643               val = fxn == divide ? l->u.i / r->u.i : l->u.i % r->u.i;
 644             }
 645         }
 646       freev (l);
 647       freev (r);
 648       l = int_value (val);
 649     }
 650 }
 651
 652 /* Handle +, - operators.  */
 653
 654 static VALUE *
 655 eval3 (bool evaluate)
 656 {
 657   VALUE *l;
 658   VALUE *r;
 659   enum { plus, minus } fxn;
 660   intmax_t val = 0;
 661
 662 #ifdef EVAL_TRACE
 663   trace ("eval3");
 664 #endif
 665   l = eval4 (evaluate);
 666   while (1)
 667     {
 668       if (nextarg ("+"))
 669         fxn = plus;
 670       else if (nextarg ("-"))
 671         fxn = minus;
 672       else
 673         return l;
 674       r = eval4 (evaluate);
 675       if (evaluate)
 676         {
 677           if (!toarith (l) || !toarith (r))
 678             error (EXPR_FAILURE, 0, _("non-numeric argument"));
 679           val = fxn == plus ? l->u.i + r->u.i : l->u.i - r->u.i;
 680         }
 681       freev (l);
 682       freev (r);
 683       l = int_value (val);
 684     }
 685 }
 686
 687 /* Handle comparisons.  */
 688
 689 static VALUE *
 690 eval2 (bool evaluate)
 691 {
 692   VALUE *l;
 693
 694 #ifdef EVAL_TRACE
 695   trace ("eval2");
 696 #endif
 697   l = eval3 (evaluate);
 698   while (1)
 699     {
 700       VALUE *r;
 701       enum
 702         {
 703           less_than, less_equal, equal, not_equal, greater_equal, greater_than
 704         } fxn;
 705       bool val = false;
 706
 707       if (nextarg ("<"))
 708         fxn = less_than;
 709       else if (nextarg ("<="))
 710         fxn = less_equal;
 711       else if (nextarg ("=") || nextarg ("=="))
 712         fxn = equal;
 713       else if (nextarg ("!="))
 714         fxn = not_equal;
 715       else if (nextarg (">="))
 716         fxn = greater_equal;
 717       else if (nextarg (">"))
 718         fxn = greater_than;
 719       else
 720         return l;
 721       r = eval3 (evaluate);
 722
 723       if (evaluate)
 724         {
 725           int cmp;
 726           tostring (l);
 727           tostring (r);
 728
 729           if (looks_like_integer (l->u.s) && looks_like_integer (r->u.s))
 730             cmp = strintcmp (l->u.s, r->u.s);
 731           else
 732             {
 733               errno = 0;
 734               cmp = strcoll (l->u.s, r->u.s);
 735
 736               if (errno)
 737                 {
 738                   error (0, errno, _("string comparison failed"));
 739                   error (0, 0, _("Set LC_ALL='C' to work around the problem."));
 740                   error (EXPR_FAILURE, 0,
 741                          _("The strings compared were %s and %s."),
 742                          quotearg_n_style (0, locale_quoting_style, l->u.s),
 743                          quotearg_n_style (1, locale_quoting_style, r->u.s));
 744                 }
 745             }
 746
 747           switch (fxn)
 748             {
 749             case less_than:     val = (cmp <  0); break;
 750             case less_equal:    val = (cmp <= 0); break;
 751             case equal:         val = (cmp == 0); break;
 752             case not_equal:     val = (cmp != 0); break;
 753             case greater_equal: val = (cmp >= 0); break;
 754             case greater_than:  val = (cmp >  0); break;
 755             default: abort ();
 756             }
 757         }
 758
 759       freev (l);
 760       freev (r);
 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 }