1 /* GNU m4 -- A simple macro processor
2 Copyright (C) 1989, 1990, 1991, 1992, 1993, 1994, 2001, 2006, 2007,
3 2008, 2009 Free Software Foundation, Inc.
5 This file is part of GNU M4.
7 GNU M4 is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 GNU M4 is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
21 /* This file contains the functions to evaluate integer expressions
22 for the "eval" and "evalmp" builtins. It is a little, fairly
23 self-contained module, with its own scanner, and a recursive descent
26 It has been carefully factored for use from the GMP module builtin,
27 mpeval: any actual operation performed on numbers is abstracted by
28 a set of macro definitions. For plain `eval', `number' is some
29 long int type, and `numb_*' manipulate those long ints. When
30 using GMP, `number' is typedef'd to `mpq_t' (the arbritrary
31 precision fractional numbers type of GMP), and `numb_*' are mapped
34 There is only one entry point, `m4_evaluate', a single function for
35 both `eval' and `mpeval', but which is redefined appropriately when
36 this file is #included into its clients. */
38 typedef enum eval_token
43 TIMES
, DIVIDE
, MODULO
, RATIO
,
44 EQ
, NOTEQ
, GT
, GTEQ
, LS
, LSEQ
,
45 LSHIFT
, RSHIFT
, URSHIFT
,
49 QUESTION
, COLON
, COMMA
,
56 typedef enum eval_error
62 /* All errors prior to SYNTAX_ERROR can be ignored in a dead
63 branch of && and ||. All errors after are just more details
64 about a syntax error. */
74 static eval_error
comma_term (m4
*, eval_token
, number
*);
75 static eval_error
condition_term (m4
*, eval_token
, number
*);
76 static eval_error
logical_or_term (m4
*, eval_token
, number
*);
77 static eval_error
logical_and_term (m4
*, eval_token
, number
*);
78 static eval_error
or_term (m4
*, eval_token
, number
*);
79 static eval_error
xor_term (m4
*, eval_token
, number
*);
80 static eval_error
and_term (m4
*, eval_token
, number
*);
81 static eval_error
equality_term (m4
*, eval_token
, number
*);
82 static eval_error
cmp_term (m4
*, eval_token
, number
*);
83 static eval_error
shift_term (m4
*, eval_token
, number
*);
84 static eval_error
add_term (m4
*, eval_token
, number
*);
85 static eval_error
mult_term (m4
*, eval_token
, number
*);
86 static eval_error
exp_term (m4
*, eval_token
, number
*);
87 static eval_error
unary_term (m4
*, eval_token
, number
*);
88 static eval_error
simple_term (m4
*, eval_token
, number
*);
89 static eval_error
numb_pow (number
*, number
*);
93 /* --- LEXICAL FUNCTIONS --- */
95 /* Pointer to next character of input text. */
96 static const char *eval_text
;
98 /* Value of eval_text, from before last call of eval_lex (). This is so we
99 can back up, if we have read too much. */
100 static const char *last_text
;
102 /* Detect when to end parsing. */
103 static const char *end_text
;
105 /* Prime the lexer at the start of TEXT, with length LEN. */
107 eval_init_lex (const char *text
, size_t len
)
110 end_text
= text
+ len
;
117 eval_text
= last_text
;
120 /* VAL is numerical value, if any. Recognize C assignment operators,
121 even though we cannot support them, to issue better error
125 eval_lex (number
*val
)
127 while (eval_text
!= end_text
&& isspace (to_uchar (*eval_text
)))
130 last_text
= eval_text
;
132 if (eval_text
== end_text
)
135 if (isdigit (to_uchar (*eval_text
)))
139 if (*eval_text
== '0')
160 while (isdigit (to_uchar (*eval_text
)) && base
<= 36)
161 base
= 10 * base
+ *eval_text
++ - '0';
162 if (base
== 0 || base
> 36 || *eval_text
!= ':')
174 numb_set_si (val
, 0);
175 for (; *eval_text
; eval_text
++)
177 if (isdigit (to_uchar (*eval_text
)))
178 digit
= *eval_text
- '0';
179 else if (islower (to_uchar (*eval_text
)))
180 digit
= *eval_text
- 'a' + 10;
181 else if (isupper (to_uchar (*eval_text
)))
182 digit
= *eval_text
- 'A' + 10;
190 else if (digit
== 0 && numb_zerop (*val
))
195 else if (digit
>= base
)
202 /* (*val) = (*val) * base; */
204 numb_set_si (&xbase
, base
);
205 numb_times (*val
, xbase
);
207 /* (*val) = (*val) + digit; */
209 numb_set_si (&xdigit
, digit
);
210 numb_plus (*val
, xdigit
);
217 switch (*eval_text
++)
220 if (*eval_text
== '+' || *eval_text
== '=')
224 if (*eval_text
== '-' || *eval_text
== '=')
228 if (*eval_text
== '*')
233 else if (*eval_text
== '=')
237 if (*eval_text
== '=')
241 if (*eval_text
== '=')
247 if (*eval_text
== '=')
254 if (*eval_text
== '=')
261 if (*eval_text
== '=')
266 else if (*eval_text
== '>')
269 if (*eval_text
== '=')
271 else if (*eval_text
== '>')
281 if (*eval_text
== '=')
286 else if (*eval_text
== '<')
288 if (*++eval_text
== '=')
295 if (*eval_text
== '=')
301 if (*eval_text
== '&')
306 else if (*eval_text
== '=')
310 if (*eval_text
== '|')
315 else if (*eval_text
== '=')
333 /* Recursive descent parser. */
335 comma_term (m4
*context
, eval_token et
, number
*v1
)
340 if ((er
= condition_term (context
, et
, v1
)) != NO_ERROR
)
344 while ((et
= eval_lex (&v2
)) == COMMA
)
348 return UNKNOWN_INPUT
;
350 if ((er
= condition_term (context
, et
, &v2
)) != NO_ERROR
)
356 return UNKNOWN_INPUT
;
363 condition_term (m4
*context
, eval_token et
, number
*v1
)
369 if ((er
= logical_or_term (context
, et
, v1
)) != NO_ERROR
)
374 if ((et
= eval_lex (&v2
)) == QUESTION
)
378 return UNKNOWN_INPUT
;
380 /* Implement short-circuiting of valid syntax. */
381 er
= comma_term (context
, et
, &v2
);
383 && !(numb_zerop (*v1
) && er
< SYNTAX_ERROR
))
388 return UNKNOWN_INPUT
;
390 return MISSING_COLON
;
394 return UNKNOWN_INPUT
;
396 er
= condition_term (context
, et
, &v3
);
398 && !(! numb_zerop (*v1
) && er
< SYNTAX_ERROR
))
401 numb_set (*v1
, ! numb_zerop (*v1
) ? v2
: v3
);
406 return UNKNOWN_INPUT
;
413 logical_or_term (m4
*context
, eval_token et
, number
*v1
)
418 if ((er
= logical_and_term (context
, et
, v1
)) != NO_ERROR
)
422 while ((et
= eval_lex (&v2
)) == LOR
)
426 return UNKNOWN_INPUT
;
428 /* Implement short-circuiting of valid syntax. */
429 er
= logical_and_term (context
, et
, &v2
);
432 else if (! numb_zerop (*v1
) && er
< SYNTAX_ERROR
)
433 numb_set (*v1
, numb_ONE
);
439 return UNKNOWN_INPUT
;
446 logical_and_term (m4
*context
, eval_token et
, number
*v1
)
451 if ((er
= or_term (context
, et
, v1
)) != NO_ERROR
)
455 while ((et
= eval_lex (&v2
)) == LAND
)
459 return UNKNOWN_INPUT
;
461 /* Implement short-circuiting of valid syntax. */
462 er
= or_term (context
, et
, &v2
);
465 else if (numb_zerop (*v1
) && er
< SYNTAX_ERROR
)
466 numb_set (*v1
, numb_ZERO
);
472 return UNKNOWN_INPUT
;
479 or_term (m4
*context
, eval_token et
, number
*v1
)
484 if ((er
= xor_term (context
, et
, v1
)) != NO_ERROR
)
488 while ((et
= eval_lex (&v2
)) == OR
)
492 return UNKNOWN_INPUT
;
494 if ((er
= xor_term (context
, et
, &v2
)) != NO_ERROR
)
497 numb_ior (context
, v1
, &v2
);
501 return UNKNOWN_INPUT
;
508 xor_term (m4
*context
, eval_token et
, number
*v1
)
513 if ((er
= and_term (context
, et
, v1
)) != NO_ERROR
)
517 while ((et
= eval_lex (&v2
)) == XOR
)
521 return UNKNOWN_INPUT
;
523 if ((er
= and_term (context
, et
, &v2
)) != NO_ERROR
)
526 numb_eor (context
, v1
, &v2
);
530 return UNKNOWN_INPUT
;
537 and_term (m4
*context
, eval_token et
, number
*v1
)
542 if ((er
= equality_term (context
, et
, v1
)) != NO_ERROR
)
546 while ((et
= eval_lex (&v2
)) == AND
)
550 return UNKNOWN_INPUT
;
552 if ((er
= equality_term (context
, et
, &v2
)) != NO_ERROR
)
555 numb_and (context
, v1
, &v2
);
559 return UNKNOWN_INPUT
;
566 equality_term (m4
*context
, eval_token et
, number
*v1
)
572 if ((er
= cmp_term (context
, et
, v1
)) != NO_ERROR
)
576 while ((op
= eval_lex (&v2
)) == EQ
|| op
== NOTEQ
)
580 return UNKNOWN_INPUT
;
582 if ((er
= cmp_term (context
, et
, &v2
)) != NO_ERROR
)
592 return UNKNOWN_INPUT
;
599 cmp_term (m4
*context
, eval_token et
, number
*v1
)
605 if ((er
= shift_term (context
, et
, v1
)) != NO_ERROR
)
609 while ((op
= eval_lex (&v2
)) == GT
|| op
== GTEQ
610 || op
== LS
|| op
== LSEQ
)
615 return UNKNOWN_INPUT
;
617 if ((er
= shift_term (context
, et
, &v2
)) != NO_ERROR
)
639 assert (!"INTERNAL ERROR: bad comparison operator in cmp_term ()");
645 return UNKNOWN_INPUT
;
652 shift_term (m4
*context
, eval_token et
, number
*v1
)
658 if ((er
= add_term (context
, et
, v1
)) != NO_ERROR
)
662 while ((op
= eval_lex (&v2
)) == LSHIFT
|| op
== RSHIFT
|| op
== URSHIFT
)
667 return UNKNOWN_INPUT
;
669 if ((er
= add_term (context
, et
, &v2
)) != NO_ERROR
)
675 numb_lshift (context
, v1
, &v2
);
679 numb_rshift (context
, v1
, &v2
);
683 numb_urshift (context
, v1
, &v2
);
687 assert (!"INTERNAL ERROR: bad shift operator in shift_term ()");
693 return UNKNOWN_INPUT
;
700 add_term (m4
*context
, eval_token et
, number
*v1
)
706 if ((er
= mult_term (context
, et
, v1
)) != NO_ERROR
)
710 while ((op
= eval_lex (&v2
)) == PLUS
|| op
== MINUS
)
714 return UNKNOWN_INPUT
;
716 if ((er
= mult_term (context
, et
, &v2
)) != NO_ERROR
)
722 numb_minus (*v1
, v2
);
726 return UNKNOWN_INPUT
;
733 mult_term (m4
*context
, eval_token et
, number
*v1
)
739 if ((er
= exp_term (context
, et
, v1
)) != NO_ERROR
)
743 while (op
= eval_lex (&v2
),
751 return UNKNOWN_INPUT
;
753 if ((er
= exp_term (context
, et
, &v2
)) != NO_ERROR
)
759 numb_times (*v1
, v2
);
766 numb_divide(v1
, &v2
);
773 numb_ratio (*v1
, v2
);
780 numb_modulo (context
, v1
, &v2
);
784 assert (!"INTERNAL ERROR: bad operator in mult_term ()");
790 return UNKNOWN_INPUT
;
797 exp_term (m4
*context
, eval_token et
, number
*v1
)
802 if ((er
= unary_term (context
, et
, v1
)) != NO_ERROR
)
806 while ((et
= eval_lex (&v2
)) == EXPONENT
)
810 return UNKNOWN_INPUT
;
812 if ((er
= exp_term (context
, et
, &v2
)) != NO_ERROR
)
815 if ((er
= numb_pow (v1
, &v2
)) != NO_ERROR
)
820 return UNKNOWN_INPUT
;
827 unary_term (m4
*context
, eval_token et
, number
*v1
)
832 if (et
== PLUS
|| et
== MINUS
|| et
== NOT
|| et
== LNOT
)
836 return UNKNOWN_INPUT
;
838 if ((er
= unary_term (context
, et2
, v1
)) != NO_ERROR
)
844 numb_not (context
, v1
);
848 else if ((er
= simple_term (context
, et
, v1
)) != NO_ERROR
)
855 simple_term (m4
*context
, eval_token et
, number
*v1
)
865 return UNKNOWN_INPUT
;
867 if ((er
= comma_term (context
, et
, v1
)) != NO_ERROR
)
872 return UNKNOWN_INPUT
;
875 return MISSING_RIGHT
;
883 return INVALID_OPERATOR
;
891 /* Main entry point, called from "eval" and "mpeval" builtins. */
893 m4_evaluate (m4
*context
, m4_obstack
*obs
, size_t argc
, m4_macro_args
*argv
)
895 const m4_call_info
*me
= m4_arg_info (argv
);
896 const char * str
= M4ARG (1);
901 eval_error err
= NO_ERROR
;
903 if (!m4_arg_empty (argv
, 2)
904 && !m4_numeric_arg (context
, me
, M4ARG (2), M4ARGLEN (2), &radix
))
907 if (radix
< 1 || radix
> 36)
909 m4_warn (context
, 0, me
, _("radix out of range: %d"), radix
);
913 if (argc
>= 4 && !m4_numeric_arg (context
, me
, M4ARG (3), M4ARGLEN (3),
919 m4_warn (context
, 0, me
, _("negative width: %d"), min
);
924 eval_init_lex (str
, M4ARGLEN (1));
927 et
= eval_lex (&val
);
930 m4_warn (context
, 0, me
, _("empty string treated as 0"));
931 numb_set (val
, numb_ZERO
);
934 err
= comma_term (context
, et
, &val
);
936 if (err
== NO_ERROR
&& *eval_text
!= '\0')
938 if (eval_lex (&val
) == BADOP
)
939 err
= INVALID_OPERATOR
;
945 str
= quotearg_style_mem (locale_quoting_style
, str
, M4ARGLEN (1));
949 numb_obstack (obs
, val
, radix
, min
);
953 m4_warn (context
, 0, me
, _("missing right parenthesis: %s"), str
);
957 m4_warn (context
, 0, me
, _("missing colon: %s"), str
);
961 m4_warn (context
, 0, me
, _("bad expression: %s"), str
);
965 m4_warn (context
, 0, me
, _("bad input: %s"), str
);
969 m4_warn (context
, 0, me
, _("excess input: %s"), str
);
972 case INVALID_OPERATOR
:
973 m4_warn (context
, 0, me
, _("invalid operator: %s"), str
);
977 m4_warn (context
, 0, me
, _("divide by zero: %s"), str
);
981 m4_warn (context
, 0, me
, _("modulo by zero: %s"), str
);
984 case NEGATIVE_EXPONENT
:
985 m4_warn (context
, 0, me
, _("negative exponent: %s"), str
);
989 assert (!"INTERNAL ERROR: bad error code in evaluate ()");
997 numb_pow (number
*x
, number
*y
)
999 /* y should be integral */
1004 numb_set_si (&ans
, 1);
1006 if (numb_zerop (*x
) && numb_zerop (*y
))
1012 if (numb_negativep (yy
))
1018 while (numb_positivep (yy
))
1020 numb_times (ans
, *x
);