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