1 /* expr -- evaluate expressions.
2 Copyright (C) 1986-2013 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 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.
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
);
54 static void integer_overflow (char) ATTRIBUTE_NORETURN
;
55 /* Approximate gmp.h well enough for expr.c's purposes. */
56 typedef intmax_t mpz_t
[1];
57 static void mpz_clear (mpz_t z
) { (void) z
; }
58 static void mpz_init_set_ui (mpz_t z
, unsigned long int i
) { z
[0] = i
; }
60 mpz_init_set_str (mpz_t z
, char *s
, int base
)
62 return xstrtoimax (s
, NULL
, base
, z
, NULL
) == LONGINT_OK
? 0 : -1;
65 mpz_add (mpz_t r
, mpz_t a0
, mpz_t b0
)
70 if ((val
< a
) != (b
< 0))
71 integer_overflow ('+');
75 mpz_sub (mpz_t r
, mpz_t a0
, mpz_t b0
)
80 if ((a
< val
) != (b
< 0))
81 integer_overflow ('-');
85 mpz_mul (mpz_t r
, mpz_t a0
, mpz_t b0
)
90 if (! (a
== 0 || b
== 0
91 || ((val
< 0) == ((a
< 0) ^ (b
< 0)) && val
/ a
== b
)))
92 integer_overflow ('*');
96 mpz_tdiv_q (mpz_t r
, mpz_t a0
, mpz_t b0
)
101 /* Some x86-style hosts raise an exception for INT_MIN / -1. */
102 if (a
< - INTMAX_MAX
&& b
== -1)
103 integer_overflow ('/');
107 mpz_tdiv_r (mpz_t r
, mpz_t a0
, mpz_t b0
)
112 /* Some x86-style hosts raise an exception for INT_MIN % -1. */
113 r
[0] = a
< - INTMAX_MAX
&& b
== -1 ? 0 : a
% b
;
116 mpz_get_str (char const *str
, int base
, mpz_t z
)
118 (void) str
; (void) base
;
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
)
141 char buf
[INT_BUFSIZE_BOUND (intmax_t)];
142 return fputs (imaxtostr (z
[0], buf
), stream
) != EOF
;
146 /* The official name of this program (e.g., no 'g' prefix). */
147 #define PROGRAM_NAME "expr"
150 proper_name ("Mike Parker"), \
151 proper_name ("James Youngman"), \
152 proper_name ("Paul Eggert")
157 /* Invalid expression: e.g., its form does not conform to the
158 grammar for expressions. Our grammar is an extension of the
162 /* An internal error occurred, e.g., arithmetic overflow, storage
167 /* The kinds of value we can have. */
173 typedef enum valtype TYPE
;
178 TYPE type
; /* Which kind. */
180 { /* The value itself. */
185 typedef struct valinfo VALUE
;
187 /* The arguments given to the program, minus the program name. */
190 static VALUE
*eval (bool);
191 static bool nomoreargs (void);
192 static bool null (VALUE
*v
);
193 static void printv (VALUE
*v
);
198 if (status
!= EXIT_SUCCESS
)
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_ancillary_info ();
273 /* Report a syntax error and exit. */
277 error (EXPR_INVALID
, 0, _("syntax error"));
281 /* Report an integer overflow for operation OP and exit. */
283 integer_overflow (char op
)
285 error (EXPR_FAILURE
, ERANGE
, "%c", op
);
286 abort (); /* notreached */
291 main (int argc
, char **argv
)
295 initialize_main (&argc
, &argv
);
296 set_program_name (argv
[0]);
297 setlocale (LC_ALL
, "");
298 bindtextdomain (PACKAGE
, LOCALEDIR
);
299 textdomain (PACKAGE
);
301 initialize_exit_failure (EXPR_FAILURE
);
302 atexit (close_stdout
);
304 parse_long_options (argc
, argv
, PROGRAM_NAME
, PACKAGE_NAME
, VERSION
,
305 usage
, AUTHORS
, (char const *) NULL
);
307 /* The above handles --help and --version.
308 Since there is no other invocation of getopt, handle '--' here. */
309 unsigned int u_argc
= argc
;
310 if (1 < u_argc
&& STREQ (argv
[1], "--"))
318 error (0, 0, _("missing operand"));
319 usage (EXPR_INVALID
);
332 /* Return a VALUE for I. */
335 int_value (unsigned long int i
)
337 VALUE
*v
= xmalloc (sizeof *v
);
339 mpz_init_set_ui (v
->u
.i
, i
);
343 /* Return a VALUE for S. */
346 str_value (char const *s
)
348 VALUE
*v
= xmalloc (sizeof *v
);
350 v
->u
.s
= xstrdup (s
);
354 /* Free VALUE V, including structure components. */
359 if (v
->type
== string
)
374 mpz_out_str (stdout
, 10, v
->u
.i
);
385 /* Return true if V is a null-string or zero-number. */
387 static bool _GL_ATTRIBUTE_PURE
393 return mpz_sgn (v
->u
.i
) == 0;
396 char const *cp
= v
->u
.s
;
416 /* Return true if CP takes the form of an integer. */
418 static bool _GL_ATTRIBUTE_PURE
419 looks_like_integer (char const *cp
)
431 /* Coerce V to a string value (can't fail). */
440 char *s
= mpz_get_str (NULL
, 10, v
->u
.i
);
453 /* Coerce V to an integer value. Return true on success, false on failure. */
466 if (! looks_like_integer (s
))
468 if (mpz_init_set_str (v
->u
.i
, s
, 10) != 0 && !HAVE_GMP
)
469 error (EXPR_FAILURE
, ERANGE
, "%s", s
);
479 /* Extract a size_t value from an integer value I.
480 If the value is negative, return SIZE_MAX.
481 If the value is too large, return SIZE_MAX - 1. */
487 if (mpz_fits_ulong_p (i
))
489 unsigned long int ul
= mpz_get_ui (i
);
496 /* Return true and advance if the next token matches STR exactly.
497 STR must not be NULL. */
500 nextarg (char const *str
)
506 bool r
= STREQ (*args
, str
);
512 /* Return true if there no more tokens. */
521 /* Print evaluation trace and args remaining. */
530 for (a
= args
; *a
; a
++)
536 /* Do the : operator.
537 SV is the VALUE for the lhs (the string),
538 PV is the VALUE for the rhs (the pattern). */
541 docolon (VALUE
*sv
, VALUE
*pv
)
543 VALUE
*v
IF_LINT ( = NULL
);
545 struct re_pattern_buffer re_buffer
;
546 char fastmap
[UCHAR_MAX
+ 1];
547 struct re_registers re_regs
;
553 re_regs
.num_regs
= 0;
554 re_regs
.start
= NULL
;
557 re_buffer
.buffer
= NULL
;
558 re_buffer
.allocated
= 0;
559 re_buffer
.fastmap
= fastmap
;
560 re_buffer
.translate
= NULL
;
562 RE_SYNTAX_POSIX_BASIC
& ~RE_CONTEXT_INVALID_DUP
& ~RE_NO_EMPTY_RANGES
;
563 errmsg
= re_compile_pattern (pv
->u
.s
, strlen (pv
->u
.s
), &re_buffer
);
565 error (EXPR_INVALID
, 0, "%s", errmsg
);
566 re_buffer
.newline_anchor
= 0;
568 matchlen
= re_match (&re_buffer
, sv
->u
.s
, strlen (sv
->u
.s
), 0, &re_regs
);
571 /* Were \(...\) used? */
572 if (re_buffer
.re_nsub
> 0)
574 sv
->u
.s
[re_regs
.end
[1]] = '\0';
575 v
= str_value (sv
->u
.s
+ re_regs
.start
[1]);
578 v
= int_value (matchlen
);
580 else if (matchlen
== -1)
582 /* Match failed -- return the right kind of null. */
583 if (re_buffer
.re_nsub
> 0)
590 (matchlen
== -2 ? errno
: EOVERFLOW
),
591 _("error in regular expression matcher"));
593 if (0 < re_regs
.num_regs
)
595 free (re_regs
.start
);
598 re_buffer
.fastmap
= NULL
;
599 regfree (&re_buffer
);
603 /* Handle bare operands and ( expr ) syntax. */
606 eval7 (bool evaluate
)
627 return str_value (*args
++);
630 /* Handle match, substr, index, and length keywords, and quoting "+". */
633 eval6 (bool evaluate
)
648 return str_value (*args
++);
650 else if (nextarg ("length"))
652 r
= eval6 (evaluate
);
654 v
= int_value (strlen (r
->u
.s
));
658 else if (nextarg ("match"))
660 l
= eval6 (evaluate
);
661 r
= eval6 (evaluate
);
672 else if (nextarg ("index"))
676 l
= eval6 (evaluate
);
677 r
= eval6 (evaluate
);
680 pos
= strcspn (l
->u
.s
, r
->u
.s
);
681 v
= int_value (l
->u
.s
[pos
] ? pos
+ 1 : 0);
686 else if (nextarg ("substr"))
689 l
= eval6 (evaluate
);
690 i1
= eval6 (evaluate
);
691 i2
= eval6 (evaluate
);
693 llen
= strlen (l
->u
.s
);
695 if (!toarith (i1
) || !toarith (i2
))
699 size_t pos
= getsize (i1
->u
.i
);
700 size_t len
= getsize (i2
->u
.i
);
702 if (llen
< pos
|| pos
== 0 || len
== 0 || len
== SIZE_MAX
)
706 size_t vlen
= MIN (len
, llen
- pos
+ 1);
708 v
= xmalloc (sizeof *v
);
710 v
->u
.s
= xmalloc (vlen
+ 1);
711 vlim
= mempcpy (v
->u
.s
, l
->u
.s
+ pos
- 1, vlen
);
721 return eval7 (evaluate
);
724 /* Handle : operator (pattern matching).
725 Calls docolon to do the real work. */
728 eval5 (bool evaluate
)
737 l
= eval6 (evaluate
);
742 r
= eval6 (evaluate
);
756 /* Handle *, /, % operators. */
759 eval4 (bool evaluate
)
763 enum { multiply
, divide
, mod
} fxn
;
768 l
= eval5 (evaluate
);
773 else if (nextarg ("/"))
775 else if (nextarg ("%"))
779 r
= eval5 (evaluate
);
782 if (!toarith (l
) || !toarith (r
))
783 error (EXPR_INVALID
, 0, _("non-integer argument"));
784 if (fxn
!= multiply
&& mpz_sgn (r
->u
.i
) == 0)
785 error (EXPR_INVALID
, 0, _("division by zero"));
786 ((fxn
== multiply
? mpz_mul
787 : fxn
== divide
? mpz_tdiv_q
789 (l
->u
.i
, l
->u
.i
, r
->u
.i
));
795 /* Handle +, - operators. */
798 eval3 (bool evaluate
)
802 enum { plus
, minus
} fxn
;
807 l
= eval4 (evaluate
);
812 else if (nextarg ("-"))
816 r
= eval4 (evaluate
);
819 if (!toarith (l
) || !toarith (r
))
820 error (EXPR_INVALID
, 0, _("non-integer argument"));
821 (fxn
== plus
? mpz_add
: mpz_sub
) (l
->u
.i
, l
->u
.i
, r
->u
.i
);
827 /* Handle comparisons. */
830 eval2 (bool evaluate
)
837 l
= eval3 (evaluate
);
843 less_than
, less_equal
, equal
, not_equal
, greater_equal
, greater_than
849 else if (nextarg ("<="))
851 else if (nextarg ("=") || nextarg ("=="))
853 else if (nextarg ("!="))
855 else if (nextarg (">="))
857 else if (nextarg (">"))
861 r
= eval3 (evaluate
);
869 if (looks_like_integer (l
->u
.s
) && looks_like_integer (r
->u
.s
))
870 cmp
= strintcmp (l
->u
.s
, r
->u
.s
);
874 cmp
= strcoll (l
->u
.s
, r
->u
.s
);
878 error (0, errno
, _("string comparison failed"));
879 error (0, 0, _("set LC_ALL='C' to work around the problem"));
880 error (EXPR_INVALID
, 0,
881 _("the strings compared were %s and %s"),
882 quotearg_n_style (0, locale_quoting_style
, l
->u
.s
),
883 quotearg_n_style (1, locale_quoting_style
, r
->u
.s
));
889 case less_than
: val
= (cmp
< 0); break;
890 case less_equal
: val
= (cmp
<= 0); break;
891 case equal
: val
= (cmp
== 0); break;
892 case not_equal
: val
= (cmp
!= 0); break;
893 case greater_equal
: val
= (cmp
>= 0); break;
894 case greater_than
: val
= (cmp
> 0); break;
908 eval1 (bool evaluate
)
916 l
= eval2 (evaluate
);
921 r
= eval2 (evaluate
&& !null (l
));
922 if (null (l
) || null (r
))
947 l
= eval1 (evaluate
);
952 r
= eval1 (evaluate
&& null (l
));