src/expr.c

   1 /* expr -- evaluate expressions.
   2    Copyright (C) 86, 1991-1997, 1999-2006 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: e.g., 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     /* An internal error occurred, e.g., arithmetic overflow, storage
  59        exhaustion.  */
  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       fputs (_("\
 162 \n\
 163 Exit status is 0 if EXPRESSION is neither null nor 0, 1 if EXPRESSION is null\n\
 164 or 0, 2 if EXPRESSION is syntactically invalid, and 3 if an error occurred.\n\
 165 "), stdout);
 166       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 167     }
 168   exit (status);
 169 }
 170
 171 /* Report a syntax error and exit.  */
 172 static void
 173 syntax_error (void)
 174 {
 175   error (EXPR_INVALID, 0, _("syntax error"));
 176 }
 177
 178 int
 179 main (int argc, char **argv)
 180 {
 181   VALUE *v;
 182
 183   initialize_main (&argc, &argv);
 184   program_name = argv[0];
 185   setlocale (LC_ALL, "");
 186   bindtextdomain (PACKAGE, LOCALEDIR);
 187   textdomain (PACKAGE);
 188
 189   initialize_exit_failure (EXPR_FAILURE);
 190   atexit (close_stdout);
 191
 192   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 193                       usage, AUTHORS, (char const *) NULL);
 194   /* The above handles --help and --version.
 195      Since there is no other invocation of getopt, handle `--' here.  */
 196   if (argc > 1 && STREQ (argv[1], "--"))
 197     {
 198       --argc;
 199       ++argv;
 200     }
 201
 202   if (argc <= 1)
 203     {
 204       error (0, 0, _("missing operand"));
 205       usage (EXPR_INVALID);
 206     }
 207
 208   args = argv + 1;
 209
 210   v = eval (true);
 211   if (!nomoreargs ())
 212     syntax_error ();
 213   printv (v);
 214
 215   exit (null (v));
 216 }
 217
 218 /* Return a VALUE for I.  */
 219
 220 static VALUE *
 221 int_value (intmax_t i)
 222 {
 223   VALUE *v = xmalloc (sizeof *v);
 224   v->type = integer;
 225   v->u.i = i;
 226   return v;
 227 }
 228
 229 /* Return a VALUE for S.  */
 230
 231 static VALUE *
 232 str_value (char *s)
 233 {
 234   VALUE *v = xmalloc (sizeof *v);
 235   v->type = string;
 236   v->u.s = xstrdup (s);
 237   return v;
 238 }
 239
 240 /* Free VALUE V, including structure components.  */
 241
 242 static void
 243 freev (VALUE *v)
 244 {
 245   if (v->type == string)
 246     free (v->u.s);
 247   free (v);
 248 }
 249
 250 /* Print VALUE V.  */
 251
 252 static void
 253 printv (VALUE *v)
 254 {
 255   char *p;
 256   char buf[INT_BUFSIZE_BOUND (intmax_t)];
 257
 258   switch (v->type)
 259     {
 260     case integer:
 261       p = imaxtostr (v->u.i, buf);
 262       break;
 263     case string:
 264       p = v->u.s;
 265       break;
 266     default:
 267       abort ();
 268     }
 269
 270   puts (p);
 271 }
 272
 273 /* Return true if V is a null-string or zero-number.  */
 274
 275 static bool
 276 null (VALUE *v)
 277 {
 278   switch (v->type)
 279     {
 280     case integer:
 281       return v->u.i == 0;
 282     case string:
 283       {
 284         char const *cp = v->u.s;
 285         if (*cp == '\0')
 286           return true;
 287
 288         cp += (*cp == '-');
 289
 290         do
 291           {
 292             if (*cp != '0')
 293               return false;
 294           }
 295         while (*++cp);
 296
 297         return true;
 298       }
 299     default:
 300       abort ();
 301     }
 302 }
 303
 304 /* Return true if CP takes the form of an integer.  */
 305
 306 static bool
 307 looks_like_integer (char const *cp)
 308 {
 309   cp += (*cp == '-');
 310
 311   do
 312     if (! ISDIGIT (*cp))
 313       return false;
 314   while (*++cp);
 315
 316   return true;
 317 }
 318
 319 /* Coerce V to a string value (can't fail).  */
 320
 321 static void
 322 tostring (VALUE *v)
 323 {
 324   char buf[INT_BUFSIZE_BOUND (intmax_t)];
 325
 326   switch (v->type)
 327     {
 328     case integer:
 329       v->u.s = xstrdup (imaxtostr (v->u.i, buf));
 330       v->type = string;
 331       break;
 332     case string:
 333       break;
 334     default:
 335       abort ();
 336     }
 337 }
 338
 339 /* Coerce V to an integer value.  Return true on success, false on failure.  */
 340
 341 static bool
 342 toarith (VALUE *v)
 343 {
 344   switch (v->type)
 345     {
 346     case integer:
 347       return true;
 348     case string:
 349       {
 350         intmax_t value;
 351
 352         if (! looks_like_integer (v->u.s))
 353           return false;
 354         if (xstrtoimax (v->u.s, NULL, 10, &value, NULL) != LONGINT_OK)
 355           error (EXPR_FAILURE, ERANGE, "%s", v->u.s);
 356         free (v->u.s);
 357         v->u.i = value;
 358         v->type = integer;
 359         return true;
 360       }
 361     default:
 362       abort ();
 363     }
 364 }
 365
 366 /* Return true and advance if the next token matches STR exactly.
 367    STR must not be NULL.  */
 368
 369 static bool
 370 nextarg (char const *str)
 371 {
 372   if (*args == NULL)
 373     return false;
 374   else
 375     {
 376       bool r = STREQ (*args, str);
 377       args += r;
 378       return r;
 379     }
 380 }
 381
 382 /* Return true if there no more tokens.  */
 383
 384 static bool
 385 nomoreargs (void)
 386 {
 387   return *args == 0;
 388 }
 389
 390 #ifdef EVAL_TRACE
 391 /* Print evaluation trace and args remaining.  */
 392
 393 static void
 394 trace (fxn)
 395      char *fxn;
 396 {
 397   char **a;
 398
 399   printf ("%s:", fxn);
 400   for (a = args; *a; a++)
 401     printf (" %s", *a);
 402   putchar ('\n');
 403 }
 404 #endif
 405
 406 /* Do the : operator.
 407    SV is the VALUE for the lhs (the string),
 408    PV is the VALUE for the rhs (the pattern).  */
 409
 410 static VALUE *
 411 docolon (VALUE *sv, VALUE *pv)
 412 {
 413   VALUE *v IF_LINT (= NULL);
 414   const char *errmsg;
 415   struct re_pattern_buffer re_buffer;
 416   char fastmap[UCHAR_MAX + 1];
 417   struct re_registers re_regs;
 418   regoff_t matchlen;
 419
 420   tostring (sv);
 421   tostring (pv);
 422
 423   re_buffer.buffer = NULL;
 424   re_buffer.allocated = 0;
 425   re_buffer.fastmap = fastmap;
 426   re_buffer.translate = NULL;
 427   re_syntax_options =
 428     RE_SYNTAX_POSIX_BASIC & ~RE_CONTEXT_INVALID_DUP & ~RE_NO_EMPTY_RANGES;
 429   errmsg = re_compile_pattern (pv->u.s, strlen (pv->u.s), &re_buffer);
 430   if (errmsg)
 431     error (EXPR_INVALID, 0, "%s", errmsg);
 432   re_buffer.newline_anchor = 0;
 433
 434   matchlen = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
 435   if (0 <= matchlen)
 436     {
 437       /* Were \(...\) used? */
 438       if (re_buffer.re_nsub > 0)
 439         {
 440           sv->u.s[re_regs.end[1]] = '\0';
 441           v = str_value (sv->u.s + re_regs.start[1]);
 442         }
 443       else
 444         v = int_value (matchlen);
 445     }
 446   else if (matchlen == -1)
 447     {
 448       /* Match failed -- return the right kind of null.  */
 449       if (re_buffer.re_nsub > 0)
 450         v = str_value ("");
 451       else
 452         v = int_value (0);
 453     }
 454   else
 455     error (EXPR_FAILURE,
 456            (matchlen == -2 ? errno : EOVERFLOW),
 457            _("error in regular expression matcher"));
 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 = xmalloc (sizeof *v);
 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_INVALID, 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_INVALID, 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_INVALID, 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
 690 #ifdef EVAL_TRACE
 691   trace ("eval2");
 692 #endif
 693   l = eval3 (evaluate);
 694   while (1)
 695     {
 696       VALUE *r;
 697       enum
 698         {
 699           less_than, less_equal, equal, not_equal, greater_equal, greater_than
 700         } fxn;
 701       bool val = false;
 702
 703       if (nextarg ("<"))
 704         fxn = less_than;
 705       else if (nextarg ("<="))
 706         fxn = less_equal;
 707       else if (nextarg ("=") || nextarg ("=="))
 708         fxn = equal;
 709       else if (nextarg ("!="))
 710         fxn = not_equal;
 711       else if (nextarg (">="))
 712         fxn = greater_equal;
 713       else if (nextarg (">"))
 714         fxn = greater_than;
 715       else
 716         return l;
 717       r = eval3 (evaluate);
 718
 719       if (evaluate)
 720         {
 721           int cmp;
 722           tostring (l);
 723           tostring (r);
 724
 725           if (looks_like_integer (l->u.s) && looks_like_integer (r->u.s))
 726             cmp = strintcmp (l->u.s, r->u.s);
 727           else
 728             {
 729               errno = 0;
 730               cmp = strcoll (l->u.s, r->u.s);
 731
 732               if (errno)
 733                 {
 734                   error (0, errno, _("string comparison failed"));
 735                   error (0, 0, _("Set LC_ALL='C' to work around the problem."));
 736                   error (EXPR_INVALID, 0,
 737                          _("The strings compared were %s and %s."),
 738                          quotearg_n_style (0, locale_quoting_style, l->u.s),
 739                          quotearg_n_style (1, locale_quoting_style, r->u.s));
 740                 }
 741             }
 742
 743           switch (fxn)
 744             {
 745             case less_than:     val = (cmp <  0); break;
 746             case less_equal:    val = (cmp <= 0); break;
 747             case equal:         val = (cmp == 0); break;
 748             case not_equal:     val = (cmp != 0); break;
 749             case greater_equal: val = (cmp >= 0); break;
 750             case greater_than:  val = (cmp >  0); break;
 751             default: abort ();
 752             }
 753         }
 754
 755       freev (l);
 756       freev (r);
 757       l = int_value (val);
 758     }
 759 }
 760
 761 /* Handle &.  */
 762
 763 static VALUE *
 764 eval1 (bool evaluate)
 765 {
 766   VALUE *l;
 767   VALUE *r;
 768
 769 #ifdef EVAL_TRACE
 770   trace ("eval1");
 771 #endif
 772   l = eval2 (evaluate);
 773   while (1)
 774     {
 775       if (nextarg ("&"))
 776         {
 777           r = eval2 (evaluate & ~ null (l));
 778           if (null (l) || null (r))
 779             {
 780               freev (l);
 781               freev (r);
 782               l = int_value (0);
 783             }
 784           else
 785             freev (r);
 786         }
 787       else
 788         return l;
 789     }
 790 }
 791
 792 /* Handle |.  */
 793
 794 static VALUE *
 795 eval (bool evaluate)
 796 {
 797   VALUE *l;
 798   VALUE *r;
 799
 800 #ifdef EVAL_TRACE
 801   trace ("eval");
 802 #endif
 803   l = eval1 (evaluate);
 804   while (1)
 805     {
 806       if (nextarg ("|"))
 807         {
 808           r = eval1 (evaluate & null (l));
 809           if (null (l))
 810             {
 811               freev (l);
 812               l = r;
 813               if (null (l))
 814                 {
 815                   freev (l);
 816                   l = int_value (0);
 817                 }
 818             }
 819           else
 820             freev (r);
 821         }
 822       else
 823         return l;
 824     }
 825 }