1 /* expr -- evaluate expressions.
2 Copyright (C) 86, 1991-1997, 1999-2008 Free Software Foundation, Inc.
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.
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.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* Author: Mike Parker.
18 Modified for arbitrary-precision calculation by James Youngman.
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.
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).
29 Define EVAL_TRACE to print an evaluation trace. */
33 #include <sys/types.h>
38 #include "long-options.h"
40 #include "strnumcmp.h"
43 /* Various parts of this code assume size_t fits into unsigned long
44 int, the widest unsigned type that GMP supports. */
45 verify (SIZE_MAX
<= ULONG_MAX
);
47 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
) {}
59 static void mpz_init_set_ui (mpz_t z
, unsigned long int i
) { z
[0] = i
; }
61 mpz_init_set_str (mpz_t z
, char *s
, int base
)
63 return xstrtoimax (s
, NULL
, base
, z
, NULL
) == LONGINT_OK
? 0 : -1;
66 mpz_add (mpz_t r
, mpz_t a0
, mpz_t b0
)
71 if ((val
< a
) != (b
< 0))
72 integer_overflow ('+');
76 mpz_sub (mpz_t r
, mpz_t a0
, mpz_t b0
)
81 if ((a
< val
) != (b
< 0))
82 integer_overflow ('-');
86 mpz_mul (mpz_t r
, mpz_t a0
, mpz_t b0
)
91 if (! (a
== 0 || b
== 0
92 || ((val
< 0) == ((a
< 0) ^ (b
< 0)) && val
/ a
== b
)))
93 integer_overflow ('*');
97 mpz_tdiv_q (mpz_t r
, mpz_t a0
, mpz_t b0
)
102 /* Some x86-style hosts raise an exception for INT_MIN / -1. */
103 if (a
< - INTMAX_MAX
&& b
== -1)
104 integer_overflow ('/');
108 mpz_tdiv_r (mpz_t r
, mpz_t a0
, mpz_t b0
)
113 /* Some x86-style hosts raise an exception for INT_MIN % -1. */
114 r
[0] = a
< - INTMAX_MAX
&& b
== -1 ? 0 : a
% b
;
117 mpz_get_str (char const *str
, int base
, mpz_t z
)
119 char buf
[INT_BUFSIZE_BOUND (intmax_t)];
120 return xstrdup (imaxtostr (z
[0], buf
));
125 return z
[0] < 0 ? -1 : 0 < z
[0];
128 mpz_fits_ulong_p (mpz_t z
)
130 return 0 <= z
[0] && z
[0] <= ULONG_MAX
;
132 static unsigned long int
138 mpz_out_str (FILE *stream
, int base
, mpz_t z
)
140 char buf
[INT_BUFSIZE_BOUND (intmax_t)];
141 return fputs (imaxtostr (z
[0], buf
), stream
) != EOF
;
145 /* The official name of this program (e.g., no `g' prefix). */
146 #define PROGRAM_NAME "expr"
149 proper_name ("Mike Parker"), \
150 proper_name ("James Youngman"), \
151 proper_name ("Paul Eggert")
156 /* Invalid expression: e.g., its form does not conform to the
157 grammar for expressions. Our grammar is an extension of the
161 /* An internal error occurred, e.g., arithmetic overflow, storage
166 /* The kinds of value we can have. */
172 typedef enum valtype TYPE
;
177 TYPE type
; /* Which kind. */
179 { /* The value itself. */
184 typedef struct valinfo VALUE
;
186 /* The arguments given to the program, minus the program name. */
189 static VALUE
*eval (bool);
190 static bool nomoreargs (void);
191 static bool null (VALUE
*v
);
192 static void printv (VALUE
*v
);
197 if (status
!= EXIT_SUCCESS
)
198 fprintf (stderr
, _("Try `%s --help' for more information.\n"),
203 Usage: %s EXPRESSION\n\
206 program_name
, program_name
);
208 fputs (HELP_OPTION_DESCRIPTION
, stdout
);
209 fputs (VERSION_OPTION_DESCRIPTION
, stdout
);
212 Print the value of EXPRESSION to standard output. A blank line below\n\
213 separates increasing precedence groups. EXPRESSION may be:\n\
215 ARG1 | ARG2 ARG1 if it is neither null nor 0, otherwise ARG2\n\
217 ARG1 & ARG2 ARG1 if neither argument is null or 0, otherwise 0\n\
221 ARG1 < ARG2 ARG1 is less than ARG2\n\
222 ARG1 <= ARG2 ARG1 is less than or equal to ARG2\n\
223 ARG1 = ARG2 ARG1 is equal to ARG2\n\
224 ARG1 != ARG2 ARG1 is unequal to ARG2\n\
225 ARG1 >= ARG2 ARG1 is greater than or equal to ARG2\n\
226 ARG1 > ARG2 ARG1 is greater than ARG2\n\
230 ARG1 + ARG2 arithmetic sum of ARG1 and ARG2\n\
231 ARG1 - ARG2 arithmetic difference of ARG1 and ARG2\n\
233 /* Tell xgettext that the "% A" below is not a printf-style
234 format string: xgettext:no-c-format */
237 ARG1 * ARG2 arithmetic product of ARG1 and ARG2\n\
238 ARG1 / ARG2 arithmetic quotient of ARG1 divided by ARG2\n\
239 ARG1 % ARG2 arithmetic remainder of ARG1 divided by ARG2\n\
243 STRING : REGEXP anchored pattern match of REGEXP in STRING\n\
245 match STRING REGEXP same as STRING : REGEXP\n\
246 substr STRING POS LENGTH substring of STRING, POS counted from 1\n\
247 index STRING CHARS index in STRING where any CHARS is found, or 0\n\
248 length STRING length of STRING\n\
251 + TOKEN interpret TOKEN as a string, even if it is a\n\
252 keyword like `match' or an operator like `/'\n\
254 ( EXPRESSION ) value of EXPRESSION\n\
258 Beware that many operators need to be escaped or quoted for shells.\n\
259 Comparisons are arithmetic if both ARGs are numbers, else lexicographical.\n\
260 Pattern matches return the string matched between \\( and \\) or null; if\n\
261 \\( and \\) are not used, they return the number of characters matched or 0.\n\
265 Exit status is 0 if EXPRESSION is neither null nor 0, 1 if EXPRESSION is null\n\
266 or 0, 2 if EXPRESSION is syntactically invalid, and 3 if an error occurred.\n\
268 emit_bug_reporting_address ();
273 /* Report a syntax error and exit. */
277 error (EXPR_INVALID
, 0, _("syntax error"));
280 /* Report an integer overflow for operation OP and exit. */
282 integer_overflow (char op
)
284 error (EXPR_FAILURE
, ERANGE
, "%c", op
);
285 abort (); /* notreached */
288 static void die (int errno_val
, char const *msg
)
291 die (int errno_val
, char const *msg
)
293 error (EXPR_FAILURE
, errno_val
, "%s", msg
);
294 abort (); /* notreached */
298 main (int argc
, char **argv
)
302 initialize_main (&argc
, &argv
);
303 set_program_name (argv
[0]);
304 setlocale (LC_ALL
, "");
305 bindtextdomain (PACKAGE
, LOCALEDIR
);
306 textdomain (PACKAGE
);
308 initialize_exit_failure (EXPR_FAILURE
);
309 atexit (close_stdout
);
311 parse_long_options (argc
, argv
, PROGRAM_NAME
, PACKAGE_NAME
, VERSION
,
312 usage
, AUTHORS
, (char const *) NULL
);
313 /* The above handles --help and --version.
314 Since there is no other invocation of getopt, handle `--' here. */
315 if (argc
> 1 && STREQ (argv
[1], "--"))
323 error (0, 0, _("missing operand"));
324 usage (EXPR_INVALID
);
337 /* Return a VALUE for I. */
340 int_value (unsigned long int i
)
342 VALUE
*v
= xmalloc (sizeof *v
);
344 mpz_init_set_ui (v
->u
.i
, i
);
348 /* Return a VALUE for S. */
351 str_value (char const *s
)
353 VALUE
*v
= xmalloc (sizeof *v
);
355 v
->u
.s
= xstrdup (s
);
359 /* Free VALUE V, including structure components. */
364 if (v
->type
== string
)
379 mpz_out_str (stdout
, 10, v
->u
.i
);
390 /* Return true if V is a null-string or zero-number. */
398 return mpz_sgn (v
->u
.i
) == 0;
401 char const *cp
= v
->u
.s
;
421 /* Return true if CP takes the form of an integer. */
424 looks_like_integer (char const *cp
)
436 /* Coerce V to a string value (can't fail). */
445 char *s
= mpz_get_str (NULL
, 10, v
->u
.i
);
458 /* Coerce V to an integer value. Return true on success, false on failure. */
471 if (! looks_like_integer (s
))
473 if (mpz_init_set_str (v
->u
.i
, s
, 10) != 0 && !HAVE_GMP
)
474 error (EXPR_FAILURE
, ERANGE
, "%s", s
);
484 /* Extract a size_t value from a integer value I.
485 If the value is negative, return SIZE_MAX.
486 If the value is too large, return SIZE_MAX - 1. */
492 if (mpz_fits_ulong_p (i
))
494 unsigned long int ul
= mpz_get_ui (i
);
501 /* Return true and advance if the next token matches STR exactly.
502 STR must not be NULL. */
505 nextarg (char const *str
)
511 bool r
= STREQ (*args
, str
);
517 /* Return true if there no more tokens. */
526 /* Print evaluation trace and args remaining. */
535 for (a
= args
; *a
; a
++)
541 /* Do the : operator.
542 SV is the VALUE for the lhs (the string),
543 PV is the VALUE for the rhs (the pattern). */
546 docolon (VALUE
*sv
, VALUE
*pv
)
548 VALUE
*v
IF_LINT (= NULL
);
550 struct re_pattern_buffer re_buffer
;
551 char fastmap
[UCHAR_MAX
+ 1];
552 struct re_registers re_regs
;
558 re_regs
.num_regs
= 0;
559 re_regs
.start
= NULL
;
562 re_buffer
.buffer
= NULL
;
563 re_buffer
.allocated
= 0;
564 re_buffer
.fastmap
= fastmap
;
565 re_buffer
.translate
= NULL
;
567 RE_SYNTAX_POSIX_BASIC
& ~RE_CONTEXT_INVALID_DUP
& ~RE_NO_EMPTY_RANGES
;
568 errmsg
= re_compile_pattern (pv
->u
.s
, strlen (pv
->u
.s
), &re_buffer
);
570 error (EXPR_INVALID
, 0, "%s", errmsg
);
571 re_buffer
.newline_anchor
= 0;
573 matchlen
= re_match (&re_buffer
, sv
->u
.s
, strlen (sv
->u
.s
), 0, &re_regs
);
576 /* Were \(...\) used? */
577 if (re_buffer
.re_nsub
> 0)
579 sv
->u
.s
[re_regs
.end
[1]] = '\0';
580 v
= str_value (sv
->u
.s
+ re_regs
.start
[1]);
583 v
= int_value (matchlen
);
585 else if (matchlen
== -1)
587 /* Match failed -- return the right kind of null. */
588 if (re_buffer
.re_nsub
> 0)
595 (matchlen
== -2 ? errno
: EOVERFLOW
),
596 _("error in regular expression matcher"));
598 if (0 < re_regs
.num_regs
)
600 free (re_regs
.start
);
603 re_buffer
.fastmap
= NULL
;
604 regfree (&re_buffer
);
608 /* Handle bare operands and ( expr ) syntax. */
611 eval7 (bool evaluate
)
632 return str_value (*args
++);
635 /* Handle match, substr, index, and length keywords, and quoting "+". */
638 eval6 (bool evaluate
)
653 return str_value (*args
++);
655 else if (nextarg ("length"))
657 r
= eval6 (evaluate
);
659 v
= int_value (strlen (r
->u
.s
));
663 else if (nextarg ("match"))
665 l
= eval6 (evaluate
);
666 r
= eval6 (evaluate
);
677 else if (nextarg ("index"))
681 l
= eval6 (evaluate
);
682 r
= eval6 (evaluate
);
685 pos
= strcspn (l
->u
.s
, r
->u
.s
);
686 v
= int_value (l
->u
.s
[pos
] ? pos
+ 1 : 0);
691 else if (nextarg ("substr"))
694 l
= eval6 (evaluate
);
695 i1
= eval6 (evaluate
);
696 i2
= eval6 (evaluate
);
698 llen
= strlen (l
->u
.s
);
700 if (!toarith (i1
) || !toarith (i2
))
704 size_t pos
= getsize (i1
->u
.i
);
705 size_t len
= getsize (i2
->u
.i
);
707 if (llen
< pos
|| pos
== 0 || len
== 0 || len
== SIZE_MAX
)
711 size_t vlen
= MIN (len
, llen
- pos
+ 1);
713 v
= xmalloc (sizeof *v
);
715 v
->u
.s
= xmalloc (vlen
+ 1);
716 vlim
= mempcpy (v
->u
.s
, l
->u
.s
+ pos
- 1, vlen
);
726 return eval7 (evaluate
);
729 /* Handle : operator (pattern matching).
730 Calls docolon to do the real work. */
733 eval5 (bool evaluate
)
742 l
= eval6 (evaluate
);
747 r
= eval6 (evaluate
);
761 /* Handle *, /, % operators. */
764 eval4 (bool evaluate
)
768 enum { multiply
, divide
, mod
} fxn
;
773 l
= eval5 (evaluate
);
778 else if (nextarg ("/"))
780 else if (nextarg ("%"))
784 r
= eval5 (evaluate
);
787 if (!toarith (l
) || !toarith (r
))
788 error (EXPR_INVALID
, 0, _("non-numeric argument"));
789 if (fxn
!= multiply
&& mpz_sgn (r
->u
.i
) == 0)
790 error (EXPR_INVALID
, 0, _("division by zero"));
791 ((fxn
== multiply
? mpz_mul
792 : fxn
== divide
? mpz_tdiv_q
794 (l
->u
.i
, l
->u
.i
, r
->u
.i
));
800 /* Handle +, - operators. */
803 eval3 (bool evaluate
)
807 enum { plus
, minus
} fxn
;
812 l
= eval4 (evaluate
);
817 else if (nextarg ("-"))
821 r
= eval4 (evaluate
);
824 if (!toarith (l
) || !toarith (r
))
825 error (EXPR_INVALID
, 0, _("non-numeric argument"));
826 (fxn
== plus
? mpz_add
: mpz_sub
) (l
->u
.i
, l
->u
.i
, r
->u
.i
);
832 /* Handle comparisons. */
835 eval2 (bool evaluate
)
842 l
= eval3 (evaluate
);
848 less_than
, less_equal
, equal
, not_equal
, greater_equal
, greater_than
854 else if (nextarg ("<="))
856 else if (nextarg ("=") || nextarg ("=="))
858 else if (nextarg ("!="))
860 else if (nextarg (">="))
862 else if (nextarg (">"))
866 r
= eval3 (evaluate
);
874 if (looks_like_integer (l
->u
.s
) && looks_like_integer (r
->u
.s
))
875 cmp
= strintcmp (l
->u
.s
, r
->u
.s
);
879 cmp
= strcoll (l
->u
.s
, r
->u
.s
);
883 error (0, errno
, _("string comparison failed"));
884 error (0, 0, _("set LC_ALL='C' to work around the problem"));
885 error (EXPR_INVALID
, 0,
886 _("the strings compared were %s and %s"),
887 quotearg_n_style (0, locale_quoting_style
, l
->u
.s
),
888 quotearg_n_style (1, locale_quoting_style
, r
->u
.s
));
894 case less_than
: val
= (cmp
< 0); break;
895 case less_equal
: val
= (cmp
<= 0); break;
896 case equal
: val
= (cmp
== 0); break;
897 case not_equal
: val
= (cmp
!= 0); break;
898 case greater_equal
: val
= (cmp
>= 0); break;
899 case greater_than
: val
= (cmp
> 0); break;
913 eval1 (bool evaluate
)
921 l
= eval2 (evaluate
);
926 r
= eval2 (evaluate
& ~ null (l
));
927 if (null (l
) || null (r
))
952 l
= eval1 (evaluate
);
957 r
= eval1 (evaluate
& null (l
));