1 /* expr -- evaluate expressions.
2 Copyright (C) 86, 1991-1997, 1999-2009 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
);
315 /* The above handles --help and --version.
316 Since there is no other invocation of getopt, handle `--' here. */
317 if (argc
> 1 && STREQ (argv
[1], "--"))
325 error (0, 0, _("missing operand"));
326 usage (EXPR_INVALID
);
339 /* Return a VALUE for I. */
342 int_value (unsigned long int i
)
344 VALUE
*v
= xmalloc (sizeof *v
);
346 mpz_init_set_ui (v
->u
.i
, i
);
350 /* Return a VALUE for S. */
353 str_value (char const *s
)
355 VALUE
*v
= xmalloc (sizeof *v
);
357 v
->u
.s
= xstrdup (s
);
361 /* Free VALUE V, including structure components. */
366 if (v
->type
== string
)
381 mpz_out_str (stdout
, 10, v
->u
.i
);
392 /* Return true if V is a null-string or zero-number. */
400 return mpz_sgn (v
->u
.i
) == 0;
403 char const *cp
= v
->u
.s
;
423 /* Return true if CP takes the form of an integer. */
426 looks_like_integer (char const *cp
)
438 /* Coerce V to a string value (can't fail). */
447 char *s
= mpz_get_str (NULL
, 10, v
->u
.i
);
460 /* Coerce V to an integer value. Return true on success, false on failure. */
473 if (! looks_like_integer (s
))
475 if (mpz_init_set_str (v
->u
.i
, s
, 10) != 0 && !HAVE_GMP
)
476 error (EXPR_FAILURE
, ERANGE
, "%s", s
);
486 /* Extract a size_t value from a integer value I.
487 If the value is negative, return SIZE_MAX.
488 If the value is too large, return SIZE_MAX - 1. */
494 if (mpz_fits_ulong_p (i
))
496 unsigned long int ul
= mpz_get_ui (i
);
503 /* Return true and advance if the next token matches STR exactly.
504 STR must not be NULL. */
507 nextarg (char const *str
)
513 bool r
= STREQ (*args
, str
);
519 /* Return true if there no more tokens. */
528 /* Print evaluation trace and args remaining. */
537 for (a
= args
; *a
; a
++)
543 /* Do the : operator.
544 SV is the VALUE for the lhs (the string),
545 PV is the VALUE for the rhs (the pattern). */
548 docolon (VALUE
*sv
, VALUE
*pv
)
550 VALUE
*v
IF_LINT (= NULL
);
552 struct re_pattern_buffer re_buffer
;
553 char fastmap
[UCHAR_MAX
+ 1];
554 struct re_registers re_regs
;
560 re_regs
.num_regs
= 0;
561 re_regs
.start
= NULL
;
564 re_buffer
.buffer
= NULL
;
565 re_buffer
.allocated
= 0;
566 re_buffer
.fastmap
= fastmap
;
567 re_buffer
.translate
= NULL
;
569 RE_SYNTAX_POSIX_BASIC
& ~RE_CONTEXT_INVALID_DUP
& ~RE_NO_EMPTY_RANGES
;
570 errmsg
= re_compile_pattern (pv
->u
.s
, strlen (pv
->u
.s
), &re_buffer
);
572 error (EXPR_INVALID
, 0, "%s", errmsg
);
573 re_buffer
.newline_anchor
= 0;
575 matchlen
= re_match (&re_buffer
, sv
->u
.s
, strlen (sv
->u
.s
), 0, &re_regs
);
578 /* Were \(...\) used? */
579 if (re_buffer
.re_nsub
> 0)
581 sv
->u
.s
[re_regs
.end
[1]] = '\0';
582 v
= str_value (sv
->u
.s
+ re_regs
.start
[1]);
585 v
= int_value (matchlen
);
587 else if (matchlen
== -1)
589 /* Match failed -- return the right kind of null. */
590 if (re_buffer
.re_nsub
> 0)
597 (matchlen
== -2 ? errno
: EOVERFLOW
),
598 _("error in regular expression matcher"));
600 if (0 < re_regs
.num_regs
)
602 free (re_regs
.start
);
605 re_buffer
.fastmap
= NULL
;
606 regfree (&re_buffer
);
610 /* Handle bare operands and ( expr ) syntax. */
613 eval7 (bool evaluate
)
634 return str_value (*args
++);
637 /* Handle match, substr, index, and length keywords, and quoting "+". */
640 eval6 (bool evaluate
)
655 return str_value (*args
++);
657 else if (nextarg ("length"))
659 r
= eval6 (evaluate
);
661 v
= int_value (strlen (r
->u
.s
));
665 else if (nextarg ("match"))
667 l
= eval6 (evaluate
);
668 r
= eval6 (evaluate
);
679 else if (nextarg ("index"))
683 l
= eval6 (evaluate
);
684 r
= eval6 (evaluate
);
687 pos
= strcspn (l
->u
.s
, r
->u
.s
);
688 v
= int_value (l
->u
.s
[pos
] ? pos
+ 1 : 0);
693 else if (nextarg ("substr"))
696 l
= eval6 (evaluate
);
697 i1
= eval6 (evaluate
);
698 i2
= eval6 (evaluate
);
700 llen
= strlen (l
->u
.s
);
702 if (!toarith (i1
) || !toarith (i2
))
706 size_t pos
= getsize (i1
->u
.i
);
707 size_t len
= getsize (i2
->u
.i
);
709 if (llen
< pos
|| pos
== 0 || len
== 0 || len
== SIZE_MAX
)
713 size_t vlen
= MIN (len
, llen
- pos
+ 1);
715 v
= xmalloc (sizeof *v
);
717 v
->u
.s
= xmalloc (vlen
+ 1);
718 vlim
= mempcpy (v
->u
.s
, l
->u
.s
+ pos
- 1, vlen
);
728 return eval7 (evaluate
);
731 /* Handle : operator (pattern matching).
732 Calls docolon to do the real work. */
735 eval5 (bool evaluate
)
744 l
= eval6 (evaluate
);
749 r
= eval6 (evaluate
);
763 /* Handle *, /, % operators. */
766 eval4 (bool evaluate
)
770 enum { multiply
, divide
, mod
} fxn
;
775 l
= eval5 (evaluate
);
780 else if (nextarg ("/"))
782 else if (nextarg ("%"))
786 r
= eval5 (evaluate
);
789 if (!toarith (l
) || !toarith (r
))
790 error (EXPR_INVALID
, 0, _("non-numeric argument"));
791 if (fxn
!= multiply
&& mpz_sgn (r
->u
.i
) == 0)
792 error (EXPR_INVALID
, 0, _("division by zero"));
793 ((fxn
== multiply
? mpz_mul
794 : fxn
== divide
? mpz_tdiv_q
796 (l
->u
.i
, l
->u
.i
, r
->u
.i
));
802 /* Handle +, - operators. */
805 eval3 (bool evaluate
)
809 enum { plus
, minus
} fxn
;
814 l
= eval4 (evaluate
);
819 else if (nextarg ("-"))
823 r
= eval4 (evaluate
);
826 if (!toarith (l
) || !toarith (r
))
827 error (EXPR_INVALID
, 0, _("non-numeric argument"));
828 (fxn
== plus
? mpz_add
: mpz_sub
) (l
->u
.i
, l
->u
.i
, r
->u
.i
);
834 /* Handle comparisons. */
837 eval2 (bool evaluate
)
844 l
= eval3 (evaluate
);
850 less_than
, less_equal
, equal
, not_equal
, greater_equal
, greater_than
856 else if (nextarg ("<="))
858 else if (nextarg ("=") || nextarg ("=="))
860 else if (nextarg ("!="))
862 else if (nextarg (">="))
864 else if (nextarg (">"))
868 r
= eval3 (evaluate
);
876 if (looks_like_integer (l
->u
.s
) && looks_like_integer (r
->u
.s
))
877 cmp
= strintcmp (l
->u
.s
, r
->u
.s
);
881 cmp
= strcoll (l
->u
.s
, r
->u
.s
);
885 error (0, errno
, _("string comparison failed"));
886 error (0, 0, _("set LC_ALL='C' to work around the problem"));
887 error (EXPR_INVALID
, 0,
888 _("the strings compared were %s and %s"),
889 quotearg_n_style (0, locale_quoting_style
, l
->u
.s
),
890 quotearg_n_style (1, locale_quoting_style
, r
->u
.s
));
896 case less_than
: val
= (cmp
< 0); break;
897 case less_equal
: val
= (cmp
<= 0); break;
898 case equal
: val
= (cmp
== 0); break;
899 case not_equal
: val
= (cmp
!= 0); break;
900 case greater_equal
: val
= (cmp
>= 0); break;
901 case greater_than
: val
= (cmp
> 0); break;
915 eval1 (bool evaluate
)
923 l
= eval2 (evaluate
);
928 r
= eval2 (evaluate
&& !null (l
));
929 if (null (l
) || null (r
))
954 l
= eval1 (evaluate
);
959 r
= eval1 (evaluate
&& null (l
));