src/expr.c

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