1 /* expr -- evaluate expressions.
2 Copyright (C) 1986, 1991-1997, 1999-2011 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
) { (void) 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 (void) str
; (void) base
;
120 char buf
[INT_BUFSIZE_BOUND (intmax_t)];
121 return xstrdup (imaxtostr (z
[0], buf
));
126 return z
[0] < 0 ? -1 : 0 < z
[0];
129 mpz_fits_ulong_p (mpz_t z
)
131 return 0 <= z
[0] && z
[0] <= ULONG_MAX
;
133 static unsigned long int
139 mpz_out_str (FILE *stream
, int base
, mpz_t z
)
142 char buf
[INT_BUFSIZE_BOUND (intmax_t)];
143 return fputs (imaxtostr (z
[0], buf
), stream
) != EOF
;
147 /* The official name of this program (e.g., no `g' prefix). */
148 #define PROGRAM_NAME "expr"
151 proper_name ("Mike Parker"), \
152 proper_name ("James Youngman"), \
153 proper_name ("Paul Eggert")
158 /* Invalid expression: e.g., its form does not conform to the
159 grammar for expressions. Our grammar is an extension of the
163 /* An internal error occurred, e.g., arithmetic overflow, storage
168 /* The kinds of value we can have. */
174 typedef enum valtype TYPE
;
179 TYPE type
; /* Which kind. */
181 { /* The value itself. */
186 typedef struct valinfo VALUE
;
188 /* The arguments given to the program, minus the program name. */
191 static VALUE
*eval (bool);
192 static bool nomoreargs (void);
193 static bool null (VALUE
*v
);
194 static void printv (VALUE
*v
);
199 if (status
!= EXIT_SUCCESS
)
200 fprintf (stderr
, _("Try `%s --help' for more information.\n"),
205 Usage: %s EXPRESSION\n\
208 program_name
, program_name
);
210 fputs (HELP_OPTION_DESCRIPTION
, stdout
);
211 fputs (VERSION_OPTION_DESCRIPTION
, stdout
);
214 Print the value of EXPRESSION to standard output. A blank line below\n\
215 separates increasing precedence groups. EXPRESSION may be:\n\
217 ARG1 | ARG2 ARG1 if it is neither null nor 0, otherwise ARG2\n\
219 ARG1 & ARG2 ARG1 if neither argument is null or 0, otherwise 0\n\
223 ARG1 < ARG2 ARG1 is less than ARG2\n\
224 ARG1 <= ARG2 ARG1 is less than or equal to ARG2\n\
225 ARG1 = ARG2 ARG1 is equal to ARG2\n\
226 ARG1 != ARG2 ARG1 is unequal to ARG2\n\
227 ARG1 >= ARG2 ARG1 is greater than or equal to ARG2\n\
228 ARG1 > ARG2 ARG1 is greater than ARG2\n\
232 ARG1 + ARG2 arithmetic sum of ARG1 and ARG2\n\
233 ARG1 - ARG2 arithmetic difference of ARG1 and ARG2\n\
235 /* Tell xgettext that the "% A" below is not a printf-style
236 format string: xgettext:no-c-format */
239 ARG1 * ARG2 arithmetic product of ARG1 and ARG2\n\
240 ARG1 / ARG2 arithmetic quotient of ARG1 divided by ARG2\n\
241 ARG1 % ARG2 arithmetic remainder of ARG1 divided by ARG2\n\
245 STRING : REGEXP anchored pattern match of REGEXP in STRING\n\
247 match STRING REGEXP same as STRING : REGEXP\n\
248 substr STRING POS LENGTH substring of STRING, POS counted from 1\n\
249 index STRING CHARS index in STRING where any CHARS is found, or 0\n\
250 length STRING length of STRING\n\
253 + TOKEN interpret TOKEN as a string, even if it is a\n\
254 keyword like `match' or an operator like `/'\n\
256 ( EXPRESSION ) value of EXPRESSION\n\
260 Beware that many operators need to be escaped or quoted for shells.\n\
261 Comparisons are arithmetic if both ARGs are numbers, else lexicographical.\n\
262 Pattern matches return the string matched between \\( and \\) or null; if\n\
263 \\( and \\) are not used, they return the number of characters matched or 0.\n\
267 Exit status is 0 if EXPRESSION is neither null nor 0, 1 if EXPRESSION is null\n\
268 or 0, 2 if EXPRESSION is syntactically invalid, and 3 if an error occurred.\n\
270 emit_ancillary_info ();
275 /* Report a syntax error and exit. */
279 error (EXPR_INVALID
, 0, _("syntax error"));
282 /* Report an integer overflow for operation OP and exit. */
284 integer_overflow (char op
)
286 error (EXPR_FAILURE
, ERANGE
, "%c", op
);
287 abort (); /* notreached */
290 static void die (int errno_val
, char const *msg
)
293 die (int errno_val
, char const *msg
)
295 error (EXPR_FAILURE
, errno_val
, "%s", msg
);
296 abort (); /* notreached */
300 main (int argc
, char **argv
)
304 initialize_main (&argc
, &argv
);
305 set_program_name (argv
[0]);
306 setlocale (LC_ALL
, "");
307 bindtextdomain (PACKAGE
, LOCALEDIR
);
308 textdomain (PACKAGE
);
310 initialize_exit_failure (EXPR_FAILURE
);
311 atexit (close_stdout
);
313 parse_long_options (argc
, argv
, PROGRAM_NAME
, PACKAGE_NAME
, VERSION
,
314 usage
, AUTHORS
, (char const *) NULL
);
316 /* The above handles --help and --version.
317 Since there is no other invocation of getopt, handle `--' here. */
318 unsigned int u_argc
= argc
;
319 if (1 < u_argc
&& STREQ (argv
[1], "--"))
327 error (0, 0, _("missing operand"));
328 usage (EXPR_INVALID
);
341 /* Return a VALUE for I. */
344 int_value (unsigned long int i
)
346 VALUE
*v
= xmalloc (sizeof *v
);
348 mpz_init_set_ui (v
->u
.i
, i
);
352 /* Return a VALUE for S. */
355 str_value (char const *s
)
357 VALUE
*v
= xmalloc (sizeof *v
);
359 v
->u
.s
= xstrdup (s
);
363 /* Free VALUE V, including structure components. */
368 if (v
->type
== string
)
383 mpz_out_str (stdout
, 10, v
->u
.i
);
394 /* Return true if V is a null-string or zero-number. */
396 static bool _GL_ATTRIBUTE_PURE
402 return mpz_sgn (v
->u
.i
) == 0;
405 char const *cp
= v
->u
.s
;
425 /* Return true if CP takes the form of an integer. */
427 static bool _GL_ATTRIBUTE_PURE
428 looks_like_integer (char const *cp
)
440 /* Coerce V to a string value (can't fail). */
449 char *s
= mpz_get_str (NULL
, 10, v
->u
.i
);
462 /* Coerce V to an integer value. Return true on success, false on failure. */
475 if (! looks_like_integer (s
))
477 if (mpz_init_set_str (v
->u
.i
, s
, 10) != 0 && !HAVE_GMP
)
478 error (EXPR_FAILURE
, ERANGE
, "%s", s
);
488 /* Extract a size_t value from an integer value I.
489 If the value is negative, return SIZE_MAX.
490 If the value is too large, return SIZE_MAX - 1. */
496 if (mpz_fits_ulong_p (i
))
498 unsigned long int ul
= mpz_get_ui (i
);
505 /* Return true and advance if the next token matches STR exactly.
506 STR must not be NULL. */
509 nextarg (char const *str
)
515 bool r
= STREQ (*args
, str
);
521 /* Return true if there no more tokens. */
530 /* Print evaluation trace and args remaining. */
539 for (a
= args
; *a
; a
++)
545 /* Do the : operator.
546 SV is the VALUE for the lhs (the string),
547 PV is the VALUE for the rhs (the pattern). */
550 docolon (VALUE
*sv
, VALUE
*pv
)
552 VALUE
*v
IF_LINT ( = NULL
);
554 struct re_pattern_buffer re_buffer
;
555 char fastmap
[UCHAR_MAX
+ 1];
556 struct re_registers re_regs
;
562 re_regs
.num_regs
= 0;
563 re_regs
.start
= NULL
;
566 re_buffer
.buffer
= NULL
;
567 re_buffer
.allocated
= 0;
568 re_buffer
.fastmap
= fastmap
;
569 re_buffer
.translate
= NULL
;
571 RE_SYNTAX_POSIX_BASIC
& ~RE_CONTEXT_INVALID_DUP
& ~RE_NO_EMPTY_RANGES
;
572 errmsg
= re_compile_pattern (pv
->u
.s
, strlen (pv
->u
.s
), &re_buffer
);
574 error (EXPR_INVALID
, 0, "%s", errmsg
);
575 re_buffer
.newline_anchor
= 0;
577 matchlen
= re_match (&re_buffer
, sv
->u
.s
, strlen (sv
->u
.s
), 0, &re_regs
);
580 /* Were \(...\) used? */
581 if (re_buffer
.re_nsub
> 0)
583 sv
->u
.s
[re_regs
.end
[1]] = '\0';
584 v
= str_value (sv
->u
.s
+ re_regs
.start
[1]);
587 v
= int_value (matchlen
);
589 else if (matchlen
== -1)
591 /* Match failed -- return the right kind of null. */
592 if (re_buffer
.re_nsub
> 0)
599 (matchlen
== -2 ? errno
: EOVERFLOW
),
600 _("error in regular expression matcher"));
602 if (0 < re_regs
.num_regs
)
604 free (re_regs
.start
);
607 re_buffer
.fastmap
= NULL
;
608 regfree (&re_buffer
);
612 /* Handle bare operands and ( expr ) syntax. */
615 eval7 (bool evaluate
)
636 return str_value (*args
++);
639 /* Handle match, substr, index, and length keywords, and quoting "+". */
642 eval6 (bool evaluate
)
657 return str_value (*args
++);
659 else if (nextarg ("length"))
661 r
= eval6 (evaluate
);
663 v
= int_value (strlen (r
->u
.s
));
667 else if (nextarg ("match"))
669 l
= eval6 (evaluate
);
670 r
= eval6 (evaluate
);
681 else if (nextarg ("index"))
685 l
= eval6 (evaluate
);
686 r
= eval6 (evaluate
);
689 pos
= strcspn (l
->u
.s
, r
->u
.s
);
690 v
= int_value (l
->u
.s
[pos
] ? pos
+ 1 : 0);
695 else if (nextarg ("substr"))
698 l
= eval6 (evaluate
);
699 i1
= eval6 (evaluate
);
700 i2
= eval6 (evaluate
);
702 llen
= strlen (l
->u
.s
);
704 if (!toarith (i1
) || !toarith (i2
))
708 size_t pos
= getsize (i1
->u
.i
);
709 size_t len
= getsize (i2
->u
.i
);
711 if (llen
< pos
|| pos
== 0 || len
== 0 || len
== SIZE_MAX
)
715 size_t vlen
= MIN (len
, llen
- pos
+ 1);
717 v
= xmalloc (sizeof *v
);
719 v
->u
.s
= xmalloc (vlen
+ 1);
720 vlim
= mempcpy (v
->u
.s
, l
->u
.s
+ pos
- 1, vlen
);
730 return eval7 (evaluate
);
733 /* Handle : operator (pattern matching).
734 Calls docolon to do the real work. */
737 eval5 (bool evaluate
)
746 l
= eval6 (evaluate
);
751 r
= eval6 (evaluate
);
765 /* Handle *, /, % operators. */
768 eval4 (bool evaluate
)
772 enum { multiply
, divide
, mod
} fxn
;
777 l
= eval5 (evaluate
);
782 else if (nextarg ("/"))
784 else if (nextarg ("%"))
788 r
= eval5 (evaluate
);
791 if (!toarith (l
) || !toarith (r
))
792 error (EXPR_INVALID
, 0, _("non-integer argument"));
793 if (fxn
!= multiply
&& mpz_sgn (r
->u
.i
) == 0)
794 error (EXPR_INVALID
, 0, _("division by zero"));
795 ((fxn
== multiply
? mpz_mul
796 : fxn
== divide
? mpz_tdiv_q
798 (l
->u
.i
, l
->u
.i
, r
->u
.i
));
804 /* Handle +, - operators. */
807 eval3 (bool evaluate
)
811 enum { plus
, minus
} fxn
;
816 l
= eval4 (evaluate
);
821 else if (nextarg ("-"))
825 r
= eval4 (evaluate
);
828 if (!toarith (l
) || !toarith (r
))
829 error (EXPR_INVALID
, 0, _("non-integer argument"));
830 (fxn
== plus
? mpz_add
: mpz_sub
) (l
->u
.i
, l
->u
.i
, r
->u
.i
);
836 /* Handle comparisons. */
839 eval2 (bool evaluate
)
846 l
= eval3 (evaluate
);
852 less_than
, less_equal
, equal
, not_equal
, greater_equal
, greater_than
858 else if (nextarg ("<="))
860 else if (nextarg ("=") || nextarg ("=="))
862 else if (nextarg ("!="))
864 else if (nextarg (">="))
866 else if (nextarg (">"))
870 r
= eval3 (evaluate
);
878 if (looks_like_integer (l
->u
.s
) && looks_like_integer (r
->u
.s
))
879 cmp
= strintcmp (l
->u
.s
, r
->u
.s
);
883 cmp
= strcoll (l
->u
.s
, r
->u
.s
);
887 error (0, errno
, _("string comparison failed"));
888 error (0, 0, _("set LC_ALL='C' to work around the problem"));
889 error (EXPR_INVALID
, 0,
890 _("the strings compared were %s and %s"),
891 quotearg_n_style (0, locale_quoting_style
, l
->u
.s
),
892 quotearg_n_style (1, locale_quoting_style
, r
->u
.s
));
898 case less_than
: val
= (cmp
< 0); break;
899 case less_equal
: val
= (cmp
<= 0); break;
900 case equal
: val
= (cmp
== 0); break;
901 case not_equal
: val
= (cmp
!= 0); break;
902 case greater_equal
: val
= (cmp
>= 0); break;
903 case greater_than
: val
= (cmp
> 0); break;
917 eval1 (bool evaluate
)
925 l
= eval2 (evaluate
);
930 r
= eval2 (evaluate
&& !null (l
));
931 if (null (l
) || null (r
))
956 l
= eval1 (evaluate
);
961 r
= eval1 (evaluate
&& null (l
));