src/expr.c

   1 /* expr -- evaluate expressions.
   2    Copyright (C) 1986-2019 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 3 of the License, or
   7    (at your option) 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, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Author: Mike Parker.
  18    Modified for arbitrary-precision calculation by James Youngman.
  19
  20    This program evaluates expressions.  Each token (operator, operand,
  21    parenthesis) of the expression must be a separate 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 "die.h"
  38 #include "error.h"
  39 #include "long-options.h"
  40 #include "mbuiter.h"
  41 #include "strnumcmp.h"
  42 #include "xstrtol.h"
  43
  44 /* Various parts of this code assume size_t fits into unsigned long
  45    int, the widest unsigned type that GMP supports.  */
  46 verify (SIZE_MAX <= ULONG_MAX);
  47
  48 #ifndef HAVE_GMP
  49 # define HAVE_GMP 0
  50 #endif
  51
  52 #if HAVE_GMP
  53 # include <gmp.h>
  54 #else
  55 static void integer_overflow (char) ATTRIBUTE_NORETURN;
  56 /* Approximate gmp.h well enough for expr.c's purposes.  */
  57 typedef intmax_t mpz_t[1];
  58 static void mpz_clear (mpz_t z) { (void) z; }
  59 static void mpz_init_set_ui (mpz_t z, unsigned long int i) { z[0] = i; }
  60 static int
  61 mpz_init_set_str (mpz_t z, char *s, int base)
  62 {
  63   return xstrtoimax (s, NULL, base, z, "") == LONGINT_OK ? 0 : -1;
  64 }
  65 static void
  66 mpz_add (mpz_t r, mpz_t a0, mpz_t b0)
  67 {
  68   intmax_t a = a0[0];
  69   intmax_t b = b0[0];
  70   intmax_t val = a + b;
  71   if ((val < a) != (b < 0))
  72     integer_overflow ('+');
  73   r[0] = val;
  74 }
  75 static void
  76 mpz_sub (mpz_t r, mpz_t a0, mpz_t b0)
  77 {
  78   intmax_t a = a0[0];
  79   intmax_t b = b0[0];
  80   intmax_t val = a - b;
  81   if ((a < val) != (b < 0))
  82     integer_overflow ('-');
  83   r[0] = val;
  84 }
  85 static void
  86 mpz_mul (mpz_t r, mpz_t a0, mpz_t b0)
  87 {
  88   intmax_t a = a0[0];
  89   intmax_t b = b0[0];
  90   intmax_t val = a * b;
  91   if (! (a == 0 || b == 0
  92          || ((val < 0) == ((a < 0) ^ (b < 0)) && val / a == b)))
  93     integer_overflow ('*');
  94   r[0] = val;
  95 }
  96 static void
  97 mpz_tdiv_q (mpz_t r, mpz_t a0, mpz_t b0)
  98 {
  99   intmax_t a = a0[0];
 100   intmax_t b = b0[0];
 101
 102   /* Some x86-style hosts raise an exception for INT_MIN / -1.  */
 103   if (a < - INTMAX_MAX && b == -1)
 104     integer_overflow ('/');
 105   r[0] = a / b;
 106 }
 107 static void
 108 mpz_tdiv_r (mpz_t r, mpz_t a0, mpz_t b0)
 109 {
 110   intmax_t a = a0[0];
 111   intmax_t b = b0[0];
 112
 113   /* Some x86-style hosts raise an exception for INT_MIN % -1.  */
 114   r[0] = a < - INTMAX_MAX && b == -1 ? 0 : a % b;
 115 }
 116 static char * _GL_ATTRIBUTE_MALLOC
 117 mpz_get_str (char const *str, int base, mpz_t z)
 118 {
 119   (void) str; (void) base;
 120   char buf[INT_BUFSIZE_BOUND (intmax_t)];
 121   return xstrdup (imaxtostr (z[0], buf));
 122 }
 123 static int
 124 mpz_sgn (mpz_t z)
 125 {
 126   return z[0] < 0 ? -1 : 0 < z[0];
 127 }
 128 static int
 129 mpz_fits_ulong_p (mpz_t z)
 130 {
 131   return 0 <= z[0] && z[0] <= ULONG_MAX;
 132 }
 133 static unsigned long int
 134 mpz_get_ui (mpz_t z)
 135 {
 136   return z[0];
 137 }
 138 static int
 139 mpz_out_str (FILE *stream, int base, mpz_t z)
 140 {
 141   (void) base;
 142   char buf[INT_BUFSIZE_BOUND (intmax_t)];
 143   return fputs (imaxtostr (z[0], buf), stream) != EOF;
 144 }
 145 #endif
 146
 147 /* The official name of this program (e.g., no 'g' prefix).  */
 148 #define PROGRAM_NAME "expr"
 149
 150 #define AUTHORS \
 151   proper_name ("Mike Parker"), \
 152   proper_name ("James Youngman"), \
 153   proper_name ("Paul Eggert")
 154
 155 /* Exit statuses.  */
 156 enum
 157   {
 158     /* Invalid expression: e.g., its form does not conform to the
 159        grammar for expressions.  Our grammar is an extension of the
 160        POSIX grammar.  */
 161     EXPR_INVALID = 2,
 162
 163     /* An internal error occurred, e.g., arithmetic overflow, storage
 164        exhaustion.  */
 165     EXPR_FAILURE
 166   };
 167
 168 /* The kinds of value we can have.  */
 169 enum valtype
 170 {
 171   integer,
 172   string
 173 };
 174 typedef enum valtype TYPE;
 175
 176 /* A value is.... */
 177 struct valinfo
 178 {
 179   TYPE type;                    /* Which kind. */
 180   union
 181   {                             /* The value itself. */
 182     mpz_t i;
 183     char *s;
 184   } u;
 185 };
 186 typedef struct valinfo VALUE;
 187
 188 /* The arguments given to the program, minus the program name.  */
 189 static char **args;
 190
 191 static VALUE *eval (bool);
 192 static bool nomoreargs (void);
 193 static bool null (VALUE *v);
 194 static void printv (VALUE *v);
 195
 196
 197 /*
 198    Find the first occurrence in the character string STRING of any character
 199    in the character string ACCEPT.
 200
 201    Copied from gnulib's mbscspn, with two differences:
 202    1. Returns 1-based position of first found character, or zero if not found.
 203    2. Returned value is the logical character index, NOT byte offset.
 204
 205    Examples:
 206      mbs_logical_cspn ('hello','a')  => 0
 207      mbs_logical_cspn ('hello','h')  => 1
 208      mbs_logical_cspn ('hello','oe') => 1
 209      mbs_logical_cspn ('hello','lo') => 3
 210
 211    In UTF-8 \xCE\xB1 is a single character (greek alpha):
 212      mbs_logical_cspn ('\xCE\xB1bc','\xCE\xB1') => 1
 213      mbs_logical_cspn ('\xCE\xB1bc','c') => 3 */
 214 static size_t
 215 mbs_logical_cspn (const char *s, const char *accept)
 216 {
 217   size_t idx = 0;
 218
 219   if (accept[0] == '\0')
 220     return 0;
 221
 222   /* General case.  */
 223   if (MB_CUR_MAX > 1)
 224     {
 225       mbui_iterator_t iter;
 226
 227       for (mbui_init (iter, s); mbui_avail (iter); mbui_advance (iter))
 228         {
 229           ++idx;
 230           if (mb_len (mbui_cur (iter)) == 1)
 231             {
 232               if (mbschr (accept, *mbui_cur_ptr (iter)))
 233                 return idx;
 234             }
 235           else
 236             {
 237               mbui_iterator_t aiter;
 238
 239               for (mbui_init (aiter, accept);
 240                    mbui_avail (aiter);
 241                    mbui_advance (aiter))
 242                 if (mb_equal (mbui_cur (aiter), mbui_cur (iter)))
 243                   return idx;
 244             }
 245         }
 246
 247       /* not found */
 248       return 0;
 249     }
 250   else
 251     {
 252       /* single-byte locale,
 253          convert returned byte offset to 1-based index or zero if not found. */
 254       size_t i = strcspn (s, accept);
 255       return (s[i] ? i + 1 : 0);
 256     }
 257 }
 258
 259 /* Extract the substring of S, from logical character
 260    position POS and LEN characters.
 261    first character position is 1.
 262    POS and LEN refer to logical characters, not octets.
 263
 264    Upon exit, sets v->s to the new string.
 265    The new string might be empty if POS/LEN are invalid. */
 266 static char *
 267 mbs_logical_substr (const char *s, size_t pos, size_t len)
 268 {
 269   char *v, *vlim;
 270
 271   size_t blen = strlen (s); /* byte length */
 272   size_t llen = (MB_CUR_MAX > 1) ? mbslen (s) : blen; /* logical length */
 273
 274   if (llen < pos || pos == 0 || len == 0 || len == SIZE_MAX)
 275     return xstrdup ("");
 276
 277   /* characters to copy */
 278   size_t vlen = MIN (len, llen - pos + 1);
 279
 280   if (MB_CUR_MAX == 1)
 281     {
 282       /* Single-byte case */
 283       v = xmalloc (vlen + 1);
 284       vlim = mempcpy (v, s + pos - 1, vlen);
 285     }
 286   else
 287     {
 288       /* Multibyte case */
 289
 290       /* FIXME: this is wasteful. Some memory can be saved by counting
 291          how many bytes the matching characters occupy. */
 292       vlim = v = xmalloc (blen + 1);
 293
 294       mbui_iterator_t iter;
 295       size_t idx=1;
 296       for (mbui_init (iter, s);
 297            mbui_avail (iter) && vlen > 0;
 298            mbui_advance (iter), ++idx)
 299         {
 300           /* Skip until we reach the starting position */
 301           if (idx < pos)
 302             continue;
 303
 304           /* Copy one character */
 305           --vlen;
 306           vlim = mempcpy (vlim, mbui_cur_ptr (iter), mb_len (mbui_cur (iter)));
 307         }
 308     }
 309   *vlim = '\0';
 310   return v;
 311 }
 312
 313 /* Return the number of logical characteres (possibly multibyte)
 314    that are in string S in the first OFS octets.
 315
 316    Example in UTF-8:
 317    "\xE2\x9D\xA7" is "U+2767 ROTATED FLORAL HEART BULLET".
 318    In the string below, there are only two characters
 319    up to the first 4 bytes (The U+2767 which occupies 3 bytes and 'x'):
 320       mbs_count_to_offset ("\xE2\x9D\xA7xyz", 4) => 2  */
 321 static size_t
 322 mbs_offset_to_chars (const char *s, size_t ofs)
 323 {
 324   mbui_iterator_t iter;
 325   size_t c = 0;
 326   for (mbui_init (iter, s); mbui_avail (iter); mbui_advance (iter))
 327     {
 328       ptrdiff_t d = mbui_cur_ptr (iter) - s;
 329       if (d >= ofs)
 330         break;
 331       ++c;
 332     }
 333   return c;
 334 }
 335
 336
 337
 338 void
 339 usage (int status)
 340 {
 341   if (status != EXIT_SUCCESS)
 342     emit_try_help ();
 343   else
 344     {
 345       printf (_("\
 346 Usage: %s EXPRESSION\n\
 347   or:  %s OPTION\n\
 348 "),
 349               program_name, program_name);
 350       putchar ('\n');
 351       fputs (HELP_OPTION_DESCRIPTION, stdout);
 352       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 353       fputs (_("\
 354 \n\
 355 Print the value of EXPRESSION to standard output.  A blank line below\n\
 356 separates increasing precedence groups.  EXPRESSION may be:\n\
 357 \n\
 358   ARG1 | ARG2       ARG1 if it is neither null nor 0, otherwise ARG2\n\
 359 \n\
 360   ARG1 & ARG2       ARG1 if neither argument is null or 0, otherwise 0\n\
 361 "), stdout);
 362       fputs (_("\
 363 \n\
 364   ARG1 < ARG2       ARG1 is less than ARG2\n\
 365   ARG1 <= ARG2      ARG1 is less than or equal to ARG2\n\
 366   ARG1 = ARG2       ARG1 is equal to ARG2\n\
 367   ARG1 != ARG2      ARG1 is unequal to ARG2\n\
 368   ARG1 >= ARG2      ARG1 is greater than or equal to ARG2\n\
 369   ARG1 > ARG2       ARG1 is greater than ARG2\n\
 370 "), stdout);
 371       fputs (_("\
 372 \n\
 373   ARG1 + ARG2       arithmetic sum of ARG1 and ARG2\n\
 374   ARG1 - ARG2       arithmetic difference of ARG1 and ARG2\n\
 375 "), stdout);
 376       /* Tell xgettext that the "% A" below is not a printf-style
 377          format string:  xgettext:no-c-format */
 378       fputs (_("\
 379 \n\
 380   ARG1 * ARG2       arithmetic product of ARG1 and ARG2\n\
 381   ARG1 / ARG2       arithmetic quotient of ARG1 divided by ARG2\n\
 382   ARG1 % ARG2       arithmetic remainder of ARG1 divided by ARG2\n\
 383 "), stdout);
 384       fputs (_("\
 385 \n\
 386   STRING : REGEXP   anchored pattern match of REGEXP in STRING\n\
 387 \n\
 388   match STRING REGEXP        same as STRING : REGEXP\n\
 389   substr STRING POS LENGTH   substring of STRING, POS counted from 1\n\
 390   index STRING CHARS         index in STRING where any CHARS is found, or 0\n\
 391   length STRING              length of STRING\n\
 392 "), stdout);
 393       fputs (_("\
 394   + TOKEN                    interpret TOKEN as a string, even if it is a\n\
 395                                keyword like 'match' or an operator like '/'\n\
 396 \n\
 397   ( EXPRESSION )             value of EXPRESSION\n\
 398 "), stdout);
 399       fputs (_("\
 400 \n\
 401 Beware that many operators need to be escaped or quoted for shells.\n\
 402 Comparisons are arithmetic if both ARGs are numbers, else lexicographical.\n\
 403 Pattern matches return the string matched between \\( and \\) or null; if\n\
 404 \\( and \\) are not used, they return the number of characters matched or 0.\n\
 405 "), stdout);
 406       fputs (_("\
 407 \n\
 408 Exit status is 0 if EXPRESSION is neither null nor 0, 1 if EXPRESSION is null\n\
 409 or 0, 2 if EXPRESSION is syntactically invalid, and 3 if an error occurred.\n\
 410 "), stdout);
 411       emit_ancillary_info (PROGRAM_NAME);
 412     }
 413   exit (status);
 414 }
 415
 416
 417 #if ! HAVE_GMP
 418 /* Report an integer overflow for operation OP and exit.  */
 419 static void
 420 integer_overflow (char op)
 421 {
 422   die (EXPR_FAILURE, ERANGE, "%c", op);
 423 }
 424 #endif
 425
 426 int
 427 main (int argc, char **argv)
 428 {
 429   VALUE *v;
 430
 431   initialize_main (&argc, &argv);
 432   set_program_name (argv[0]);
 433   setlocale (LC_ALL, "");
 434   bindtextdomain (PACKAGE, LOCALEDIR);
 435   textdomain (PACKAGE);
 436
 437   initialize_exit_failure (EXPR_FAILURE);
 438   atexit (close_stdout);
 439
 440   parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE_NAME, VERSION,
 441                       usage, AUTHORS, (char const *) NULL);
 442
 443   /* The above handles --help and --version.
 444      Since there is no other invocation of getopt, handle '--' here.  */
 445   unsigned int u_argc = argc;
 446   if (1 < u_argc && STREQ (argv[1], "--"))
 447     {
 448       --u_argc;
 449       ++argv;
 450     }
 451
 452   if (u_argc <= 1)
 453     {
 454       error (0, 0, _("missing operand"));
 455       usage (EXPR_INVALID);
 456     }
 457
 458   args = argv + 1;
 459
 460   v = eval (true);
 461   if (!nomoreargs ())
 462     die (EXPR_INVALID, 0, _("syntax error: unexpected argument %s"),
 463          quotearg_n_style (0, locale_quoting_style, *args));
 464
 465   printv (v);
 466
 467   return null (v);
 468 }
 469
 470 /* Return a VALUE for I.  */
 471
 472 static VALUE *
 473 int_value (unsigned long int i)
 474 {
 475   VALUE *v = xmalloc (sizeof *v);
 476   v->type = integer;
 477   mpz_init_set_ui (v->u.i, i);
 478   return v;
 479 }
 480
 481 /* Return a VALUE for S.  */
 482
 483 static VALUE *
 484 str_value (char const *s)
 485 {
 486   VALUE *v = xmalloc (sizeof *v);
 487   v->type = string;
 488   v->u.s = xstrdup (s);
 489   return v;
 490 }
 491
 492 /* Free VALUE V, including structure components.  */
 493
 494 static void
 495 freev (VALUE *v)
 496 {
 497   if (v->type == string)
 498     free (v->u.s);
 499   else
 500     mpz_clear (v->u.i);
 501   free (v);
 502 }
 503
 504 /* Print VALUE V.  */
 505
 506 static void
 507 printv (VALUE *v)
 508 {
 509   switch (v->type)
 510     {
 511     case integer:
 512       mpz_out_str (stdout, 10, v->u.i);
 513       putchar ('\n');
 514       break;
 515     case string:
 516       puts (v->u.s);
 517       break;
 518     default:
 519       abort ();
 520     }
 521 }
 522
 523 /* Return true if V is a null-string or zero-number.  */
 524
 525 static bool _GL_ATTRIBUTE_PURE
 526 null (VALUE *v)
 527 {
 528   switch (v->type)
 529     {
 530     case integer:
 531       return mpz_sgn (v->u.i) == 0;
 532     case string:
 533       {
 534         char const *cp = v->u.s;
 535         if (*cp == '\0')
 536           return true;
 537
 538         cp += (*cp == '-');
 539
 540         do
 541           {
 542             if (*cp != '0')
 543               return false;
 544           }
 545         while (*++cp);
 546
 547         return true;
 548       }
 549     default:
 550       abort ();
 551     }
 552 }
 553
 554 /* Return true if CP takes the form of an integer.  */
 555
 556 static bool _GL_ATTRIBUTE_PURE
 557 looks_like_integer (char const *cp)
 558 {
 559   cp += (*cp == '-');
 560
 561   do
 562     if (! ISDIGIT (*cp))
 563       return false;
 564   while (*++cp);
 565
 566   return true;
 567 }
 568
 569 /* Coerce V to a string value (can't fail).  */
 570
 571 static void
 572 tostring (VALUE *v)
 573 {
 574   switch (v->type)
 575     {
 576     case integer:
 577       {
 578         char *s = mpz_get_str (NULL, 10, v->u.i);
 579         mpz_clear (v->u.i);
 580         v->u.s = s;
 581         v->type = string;
 582       }
 583       break;
 584     case string:
 585       break;
 586     default:
 587       abort ();
 588     }
 589 }
 590
 591 /* Coerce V to an integer value.  Return true on success, false on failure.  */
 592
 593 static bool
 594 toarith (VALUE *v)
 595 {
 596   switch (v->type)
 597     {
 598     case integer:
 599       return true;
 600     case string:
 601       {
 602         char *s = v->u.s;
 603
 604         if (! looks_like_integer (s))
 605           return false;
 606         if (mpz_init_set_str (v->u.i, s, 10) != 0 && !HAVE_GMP)
 607           die (EXPR_FAILURE, ERANGE, "%s", (s));
 608         free (s);
 609         v->type = integer;
 610         return true;
 611       }
 612     default:
 613       abort ();
 614     }
 615 }
 616
 617 /* Extract a size_t value from an integer value I.
 618    If the value is negative, return SIZE_MAX.
 619    If the value is too large, return SIZE_MAX - 1.  */
 620 static size_t
 621 getsize (mpz_t i)
 622 {
 623   if (mpz_sgn (i) < 0)
 624     return SIZE_MAX;
 625   if (mpz_fits_ulong_p (i))
 626     {
 627       unsigned long int ul = mpz_get_ui (i);
 628       if (ul < SIZE_MAX)
 629         return ul;
 630     }
 631   return SIZE_MAX - 1;
 632 }
 633
 634 /* Return true and advance if the next token matches STR exactly.
 635    STR must not be NULL.  */
 636
 637 static bool
 638 nextarg (char const *str)
 639 {
 640   if (*args == NULL)
 641     return false;
 642   else
 643     {
 644       bool r = STREQ (*args, str);
 645       args += r;
 646       return r;
 647     }
 648 }
 649
 650 /* Return true if there no more tokens.  */
 651
 652 static bool
 653 nomoreargs (void)
 654 {
 655   return *args == 0;
 656 }
 657
 658 /* Report missing operand.
 659    There is an implicit assumption that there was a previous argument,
 660    and (args-1) is valid. */
 661 static void
 662 require_more_args (void)
 663 {
 664   if (nomoreargs ())
 665     die (EXPR_INVALID, 0, _("syntax error: missing argument after %s"),
 666          quotearg_n_style (0, locale_quoting_style, *(args-1)));
 667 }
 668
 669
 670 #ifdef EVAL_TRACE
 671 /* Print evaluation trace and args remaining.  */
 672
 673 static void
 674 trace (fxn)
 675      char *fxn;
 676 {
 677   char **a;
 678
 679   printf ("%s:", fxn);
 680   for (a = args; *a; a++)
 681     printf (" %s", *a);
 682   putchar ('\n');
 683 }
 684 #endif
 685
 686 /* Do the : operator.
 687    SV is the VALUE for the lhs (the string),
 688    PV is the VALUE for the rhs (the pattern).  */
 689
 690 static VALUE *
 691 docolon (VALUE *sv, VALUE *pv)
 692 {
 693   VALUE *v IF_LINT ( = NULL);
 694   const char *errmsg;
 695   struct re_pattern_buffer re_buffer;
 696   char fastmap[UCHAR_MAX + 1];
 697   struct re_registers re_regs;
 698   regoff_t matchlen;
 699
 700   tostring (sv);
 701   tostring (pv);
 702
 703   re_regs.num_regs = 0;
 704   re_regs.start = NULL;
 705   re_regs.end = NULL;
 706
 707   re_buffer.buffer = NULL;
 708   re_buffer.allocated = 0;
 709   re_buffer.fastmap = fastmap;
 710   re_buffer.translate = NULL;
 711   re_syntax_options =
 712     RE_SYNTAX_POSIX_BASIC & ~RE_CONTEXT_INVALID_DUP & ~RE_NO_EMPTY_RANGES;
 713   errmsg = re_compile_pattern (pv->u.s, strlen (pv->u.s), &re_buffer);
 714   if (errmsg)
 715     die (EXPR_INVALID, 0, "%s", (errmsg));
 716   re_buffer.newline_anchor = 0;
 717
 718   matchlen = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
 719   if (0 <= matchlen)
 720     {
 721       /* Were \(...\) used? */
 722       if (re_buffer.re_nsub > 0)
 723         {
 724           sv->u.s[re_regs.end[1]] = '\0';
 725           v = str_value (sv->u.s + re_regs.start[1]);
 726         }
 727       else
 728         {
 729           /* In multibyte locales, convert the matched offset (=number of bytes)
 730              to the number of matched characters. */
 731           size_t i = (MB_CUR_MAX == 1
 732                       ? matchlen
 733                       : mbs_offset_to_chars (sv->u.s, matchlen));
 734           v = int_value (i);
 735         }
 736     }
 737   else if (matchlen == -1)
 738     {
 739       /* Match failed -- return the right kind of null.  */
 740       if (re_buffer.re_nsub > 0)
 741         v = str_value ("");
 742       else
 743         v = int_value (0);
 744     }
 745   else
 746     die (EXPR_FAILURE,
 747          (matchlen == -2 ? errno : EOVERFLOW),
 748          _("error in regular expression matcher"));
 749
 750   if (0 < re_regs.num_regs)
 751     {
 752       free (re_regs.start);
 753       free (re_regs.end);
 754     }
 755   re_buffer.fastmap = NULL;
 756   regfree (&re_buffer);
 757   return v;
 758 }
 759
 760 /* Handle bare operands and ( expr ) syntax.  */
 761
 762 static VALUE *
 763 eval7 (bool evaluate)
 764 {
 765   VALUE *v;
 766
 767 #ifdef EVAL_TRACE
 768   trace ("eval7");
 769 #endif
 770   require_more_args ();
 771
 772   if (nextarg ("("))
 773     {
 774       v = eval (evaluate);
 775       if (nomoreargs ())
 776         die (EXPR_INVALID, 0, _("syntax error: expecting ')' after %s"),
 777              quotearg_n_style (0, locale_quoting_style, *(args-1)));
 778       if (!nextarg (")"))
 779         die (EXPR_INVALID, 0, _("syntax error: expecting ')' instead of %s"),
 780              quotearg_n_style (0, locale_quoting_style, *args));
 781       return v;
 782     }
 783
 784   if (nextarg (")"))
 785     die (EXPR_INVALID, 0, _("syntax error: unexpected ')'"));
 786
 787   return str_value (*args++);
 788 }
 789
 790 /* Handle match, substr, index, and length keywords, and quoting "+".  */
 791
 792 static VALUE *
 793 eval6 (bool evaluate)
 794 {
 795   VALUE *l;
 796   VALUE *r;
 797   VALUE *v;
 798   VALUE *i1;
 799   VALUE *i2;
 800
 801 #ifdef EVAL_TRACE
 802   trace ("eval6");
 803 #endif
 804   if (nextarg ("+"))
 805     {
 806       require_more_args ();
 807       return str_value (*args++);
 808     }
 809   else if (nextarg ("length"))
 810     {
 811       r = eval6 (evaluate);
 812       tostring (r);
 813       v = int_value (mbslen (r->u.s));
 814       freev (r);
 815       return v;
 816     }
 817   else if (nextarg ("match"))
 818     {
 819       l = eval6 (evaluate);
 820       r = eval6 (evaluate);
 821       if (evaluate)
 822         {
 823           v = docolon (l, r);
 824           freev (l);
 825         }
 826       else
 827         v = l;
 828       freev (r);
 829       return v;
 830     }
 831   else if (nextarg ("index"))
 832     {
 833       size_t pos;
 834
 835       l = eval6 (evaluate);
 836       r = eval6 (evaluate);
 837       tostring (l);
 838       tostring (r);
 839       pos = mbs_logical_cspn (l->u.s, r->u.s);
 840       v = int_value (pos);
 841       freev (l);
 842       freev (r);
 843       return v;
 844     }
 845   else if (nextarg ("substr"))
 846     {
 847       l = eval6 (evaluate);
 848       i1 = eval6 (evaluate);
 849       i2 = eval6 (evaluate);
 850       tostring (l);
 851
 852       if (!toarith (i1) || !toarith (i2))
 853         v = str_value ("");
 854       else
 855         {
 856           size_t pos = getsize (i1->u.i);
 857           size_t len = getsize (i2->u.i);
 858
 859           char *s = mbs_logical_substr (l->u.s, pos, len);
 860           v = str_value (s);
 861           free (s);
 862         }
 863       freev (l);
 864       freev (i1);
 865       freev (i2);
 866       return v;
 867     }
 868   else
 869     return eval7 (evaluate);
 870 }
 871
 872 /* Handle : operator (pattern matching).
 873    Calls docolon to do the real work.  */
 874
 875 static VALUE *
 876 eval5 (bool evaluate)
 877 {
 878   VALUE *l;
 879   VALUE *r;
 880   VALUE *v;
 881
 882 #ifdef EVAL_TRACE
 883   trace ("eval5");
 884 #endif
 885   l = eval6 (evaluate);
 886   while (1)
 887     {
 888       if (nextarg (":"))
 889         {
 890           r = eval6 (evaluate);
 891           if (evaluate)
 892             {
 893               v = docolon (l, r);
 894               freev (l);
 895               l = v;
 896             }
 897           freev (r);
 898         }
 899       else
 900         return l;
 901     }
 902 }
 903
 904 /* Handle *, /, % operators.  */
 905
 906 static VALUE *
 907 eval4 (bool evaluate)
 908 {
 909   VALUE *l;
 910   VALUE *r;
 911   enum { multiply, divide, mod } fxn;
 912
 913 #ifdef EVAL_TRACE
 914   trace ("eval4");
 915 #endif
 916   l = eval5 (evaluate);
 917   while (1)
 918     {
 919       if (nextarg ("*"))
 920         fxn = multiply;
 921       else if (nextarg ("/"))
 922         fxn = divide;
 923       else if (nextarg ("%"))
 924         fxn = mod;
 925       else
 926         return l;
 927       r = eval5 (evaluate);
 928       if (evaluate)
 929         {
 930           if (!toarith (l) || !toarith (r))
 931             die (EXPR_INVALID, 0, _("non-integer argument"));
 932           if (fxn != multiply && mpz_sgn (r->u.i) == 0)
 933             die (EXPR_INVALID, 0, _("division by zero"));
 934           ((fxn == multiply ? mpz_mul
 935             : fxn == divide ? mpz_tdiv_q
 936             : mpz_tdiv_r)
 937            (l->u.i, l->u.i, r->u.i));
 938         }
 939       freev (r);
 940     }
 941 }
 942
 943 /* Handle +, - operators.  */
 944
 945 static VALUE *
 946 eval3 (bool evaluate)
 947 {
 948   VALUE *l;
 949   VALUE *r;
 950   enum { plus, minus } fxn;
 951
 952 #ifdef EVAL_TRACE
 953   trace ("eval3");
 954 #endif
 955   l = eval4 (evaluate);
 956   while (1)
 957     {
 958       if (nextarg ("+"))
 959         fxn = plus;
 960       else if (nextarg ("-"))
 961         fxn = minus;
 962       else
 963         return l;
 964       r = eval4 (evaluate);
 965       if (evaluate)
 966         {
 967           if (!toarith (l) || !toarith (r))
 968             die (EXPR_INVALID, 0, _("non-integer argument"));
 969           (fxn == plus ? mpz_add : mpz_sub) (l->u.i, l->u.i, r->u.i);
 970         }
 971       freev (r);
 972     }
 973 }
 974
 975 /* Handle comparisons.  */
 976
 977 static VALUE *
 978 eval2 (bool evaluate)
 979 {
 980   VALUE *l;
 981
 982 #ifdef EVAL_TRACE
 983   trace ("eval2");
 984 #endif
 985   l = eval3 (evaluate);
 986   while (1)
 987     {
 988       VALUE *r;
 989       enum
 990         {
 991           less_than, less_equal, equal, not_equal, greater_equal, greater_than
 992         } fxn;
 993       bool val = false;
 994
 995       if (nextarg ("<"))
 996         fxn = less_than;
 997       else if (nextarg ("<="))
 998         fxn = less_equal;
 999       else if (nextarg ("=") || nextarg ("=="))
1000         fxn = equal;
1001       else if (nextarg ("!="))
1002         fxn = not_equal;
1003       else if (nextarg (">="))
1004         fxn = greater_equal;
1005       else if (nextarg (">"))
1006         fxn = greater_than;
1007       else
1008         return l;
1009       r = eval3 (evaluate);
1010
1011       if (evaluate)
1012         {
1013           int cmp;
1014           tostring (l);
1015           tostring (r);
1016
1017           if (looks_like_integer (l->u.s) && looks_like_integer (r->u.s))
1018             cmp = strintcmp (l->u.s, r->u.s);
1019           else
1020             {
1021               errno = 0;
1022               cmp = strcoll (l->u.s, r->u.s);
1023
1024               if (errno)
1025                 {
1026                   error (0, errno, _("string comparison failed"));
1027                   error (0, 0, _("set LC_ALL='C' to work around the problem"));
1028                   die (EXPR_INVALID, 0,
1029                        _("the strings compared were %s and %s"),
1030                        quotearg_n_style (0, locale_quoting_style, l->u.s),
1031                        quotearg_n_style (1, locale_quoting_style, r->u.s));
1032                 }
1033             }
1034
1035           switch (fxn)
1036             {
1037             case less_than:     val = (cmp <  0); break;
1038             case less_equal:    val = (cmp <= 0); break;
1039             case equal:         val = (cmp == 0); break;
1040             case not_equal:     val = (cmp != 0); break;
1041             case greater_equal: val = (cmp >= 0); break;
1042             case greater_than:  val = (cmp >  0); break;
1043             default: abort ();
1044             }
1045         }
1046
1047       freev (l);
1048       freev (r);
1049       l = int_value (val);
1050     }
1051 }
1052
1053 /* Handle &.  */
1054
1055 static VALUE *
1056 eval1 (bool evaluate)
1057 {
1058   VALUE *l;
1059   VALUE *r;
1060
1061 #ifdef EVAL_TRACE
1062   trace ("eval1");
1063 #endif
1064   l = eval2 (evaluate);
1065   while (1)
1066     {
1067       if (nextarg ("&"))
1068         {
1069           r = eval2 (evaluate && !null (l));
1070           if (null (l) || null (r))
1071             {
1072               freev (l);
1073               freev (r);
1074               l = int_value (0);
1075             }
1076           else
1077             freev (r);
1078         }
1079       else
1080         return l;
1081     }
1082 }
1083
1084 /* Handle |.  */
1085
1086 static VALUE *
1087 eval (bool evaluate)
1088 {
1089   VALUE *l;
1090   VALUE *r;
1091
1092 #ifdef EVAL_TRACE
1093   trace ("eval");
1094 #endif
1095   l = eval1 (evaluate);
1096   while (1)
1097     {
1098       if (nextarg ("|"))
1099         {
1100           r = eval1 (evaluate && null (l));
1101           if (null (l))
1102             {
1103               freev (l);
1104               l = r;
1105               if (null (l))
1106                 {
1107                   freev (l);
1108                   l = int_value (0);
1109                 }
1110             }
1111           else
1112             freev (r);
1113         }
1114       else
1115         return l;
1116     }
1117 }