1 /* GNU m4 -- A simple macro processor
2
3 Copyright (C) 1989-1994, 2006-2007, 2009-2014, 2016-2017, 2020-2021
4 Free Software Foundation, Inc.
5
6 This file is part of GNU M4.
7
8 GNU M4 is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 GNU M4 is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22 /* This file contains the functions to evaluate integer expressions for
23 the "eval" macro. It is a little, fairly self-contained module, with
24 its own scanner, and a recursive descent parser. The only entry point
25 is evaluate (). */
26
27 #include "m4.h"
28
29 /* Evaluates token types. */
30
31 typedef enum eval_token
32 {
33 ERROR, BADOP,
34 PLUS, MINUS,
35 EXPONENT,
36 TIMES, DIVIDE, MODULO,
37 ASSIGN, EQ, NOTEQ, GT, GTEQ, LS, LSEQ,
38 LSHIFT, RSHIFT,
39 LNOT, LAND, LOR,
40 NOT, AND, OR, XOR,
41 LEFTP, RIGHTP,
42 NUMBER, EOTEXT
43 }
44 eval_token;
45
46 /* Error types. */
47
48 typedef enum eval_error
49 {
50 NO_ERROR,
51 DIVIDE_ZERO,
52 MODULO_ZERO,
53 NEGATIVE_EXPONENT,
54 /* All errors prior to SYNTAX_ERROR can be ignored in a dead
55 branch of && and ||. All errors after are just more details
56 about a syntax error. */
57 SYNTAX_ERROR,
58 MISSING_RIGHT,
59 UNKNOWN_INPUT,
60 EXCESS_INPUT,
61 INVALID_OPERATOR
62 }
63 eval_error;
64
65 static eval_error logical_or_term (eval_token, int32_t *);
66 static eval_error logical_and_term (eval_token, int32_t *);
67 static eval_error or_term (eval_token, int32_t *);
68 static eval_error xor_term (eval_token, int32_t *);
69 static eval_error and_term (eval_token, int32_t *);
70 static eval_error equality_term (eval_token, int32_t *);
71 static eval_error cmp_term (eval_token, int32_t *);
72 static eval_error shift_term (eval_token, int32_t *);
73 static eval_error add_term (eval_token, int32_t *);
74 static eval_error mult_term (eval_token, int32_t *);
75 static eval_error exp_term (eval_token, int32_t *);
76 static eval_error unary_term (eval_token, int32_t *);
77 static eval_error simple_term (eval_token, int32_t *);
78
79 /*--------------------.
80 | Lexical functions. |
81 `--------------------*/
82
83 /* Pointer to next character of input text. */
84 static const char *eval_text;
85
86 /* Value of eval_text, from before last call of eval_lex (). This is so we
87 can back up, if we have read too much. */
88 static const char *last_text;
89
90 static void
91 eval_init_lex (const char *text)
92 {
93 eval_text = text;
94 last_text = NULL;
95 }
96
97 static void
98 eval_undo (void)
99 {
100 eval_text = last_text;
101 }
102
103 /* VAL is numerical value, if any. */
104
105 static eval_token
106 eval_lex (int32_t *val)
107 {
108 while (c_isspace (*eval_text))
109 eval_text++;
110
111 last_text = eval_text;
112
113 if (*eval_text == '\0')
114 return EOTEXT;
115
116 if (c_isdigit (*eval_text))
117 {
118 unsigned int base, digit;
119 /* The documentation says that "overflow silently results in wraparound".
120 Therefore use an unsigned integer type to avoid undefined behaviour
121 when parsing '-2147483648'. */
122 uint32_t value;
123
124 if (*eval_text == '0')
125 {
126 eval_text++;
127 switch (*eval_text)
128 {
129 case 'x':
130 case 'X':
131 base = 16;
132 eval_text++;
133 break;
134
135 case 'b':
136 case 'B':
137 base = 2;
138 eval_text++;
139 break;
140
141 case 'r':
142 case 'R':
143 base = 0;
144 eval_text++;
145 while (c_isdigit (*eval_text) && base <= 36)
146 base = 10 * base + *eval_text++ - '0';
147 if (base == 0 || base > 36 || *eval_text != ':')
148 return ERROR;
149 eval_text++;
150 break;
151
152 default:
153 base = 8;
154 }
155 }
156 else
157 base = 10;
158
159 value = 0;
160 for (; *eval_text; eval_text++)
161 {
162 if (c_isdigit (*eval_text))
163 digit = *eval_text - '0';
164 else if (c_islower (*eval_text))
165 digit = *eval_text - 'a' + 10;
166 else if (c_isupper (*eval_text))
167 digit = *eval_text - 'A' + 10;
168 else
169 break;
170
171 if (base == 1)
172 {
173 if (digit == 1)
174 value++;
175 else if (digit == 0 && value == 0)
176 continue;
177 else
178 break;
179 }
180 else if (digit >= base)
181 break;
182 else
183 value = value * base + digit;
184 }
185 *val = value;
186 return NUMBER;
187 }
188
189 switch (*eval_text++)
190 {
191 case '+':
192 if (*eval_text == '+' || *eval_text == '=')
193 return BADOP;
194 return PLUS;
195 case '-':
196 if (*eval_text == '-' || *eval_text == '=')
197 return BADOP;
198 return MINUS;
199 case '*':
200 if (*eval_text == '*')
201 {
202 eval_text++;
203 return EXPONENT;
204 }
205 else if (*eval_text == '=')
206 return BADOP;
207 return TIMES;
208 case '/':
209 if (*eval_text == '=')
210 return BADOP;
211 return DIVIDE;
212 case '%':
213 if (*eval_text == '=')
214 return BADOP;
215 return MODULO;
216 case '=':
217 if (*eval_text == '=')
218 {
219 eval_text++;
220 return EQ;
221 }
222 return ASSIGN;
223 case '!':
224 if (*eval_text == '=')
225 {
226 eval_text++;
227 return NOTEQ;
228 }
229 return LNOT;
230 case '>':
231 if (*eval_text == '=')
232 {
233 eval_text++;
234 return GTEQ;
235 }
236 else if (*eval_text == '>')
237 {
238 if (*++eval_text == '=')
239 return BADOP;
240 return RSHIFT;
241 }
242 return GT;
243 case '<':
244 if (*eval_text == '=')
245 {
246 eval_text++;
247 return LSEQ;
248 }
249 else if (*eval_text == '<')
250 {
251 if (*++eval_text == '=')
252 return BADOP;
253 return LSHIFT;
254 }
255 return LS;
256 case '^':
257 if (*eval_text == '=')
258 return BADOP;
259 return XOR;
260 case '~':
261 return NOT;
262 case '&':
263 if (*eval_text == '&')
264 {
265 eval_text++;
266 return LAND;
267 }
268 else if (*eval_text == '=')
269 return BADOP;
270 return AND;
271 case '|':
272 if (*eval_text == '|')
273 {
274 eval_text++;
275 return LOR;
276 }
277 else if (*eval_text == '=')
278 return BADOP;
279 return OR;
280 case '(':
281 return LEFTP;
282 case ')':
283 return RIGHTP;
284 default:
285 return ERROR;
286 }
287 }
288
289 /*---------------------------------------.
290 | Main entry point, called from "eval". |
291 `---------------------------------------*/
292
293 bool
294 evaluate (const char *expr, int32_t *val)
295 {
296 eval_token et;
297 eval_error err;
298
299 eval_init_lex (expr);
300 et = eval_lex (val);
301 err = logical_or_term (et, val);
302
303 if (err == NO_ERROR && *eval_text != '\0')
304 {
305 if (eval_lex (val) == BADOP)
306 err = INVALID_OPERATOR;
307 else
308 err = EXCESS_INPUT;
309 }
310
311 switch (err)
312 {
313 case NO_ERROR:
314 break;
315
316 case MISSING_RIGHT:
317 M4ERROR ((warning_status, 0,
318 _("bad expression in eval (missing right parenthesis): %s"),
319 expr));
320 break;
321
322 case SYNTAX_ERROR:
323 M4ERROR ((warning_status, 0,
324 _("bad expression in eval: %s"), expr));
325 break;
326
327 case UNKNOWN_INPUT:
328 M4ERROR ((warning_status, 0,
329 _("bad expression in eval (bad input): %s"), expr));
330 break;
331
332 case EXCESS_INPUT:
333 M4ERROR ((warning_status, 0,
334 _("bad expression in eval (excess input): %s"), expr));
335 break;
336
337 case INVALID_OPERATOR:
338 M4ERROR ((warning_status, 0,
339 _("invalid operator in eval: %s"), expr));
340 retcode = EXIT_FAILURE;
341 break;
342
343 case DIVIDE_ZERO:
344 M4ERROR ((warning_status, 0,
345 _("divide by zero in eval: %s"), expr));
346 break;
347
348 case MODULO_ZERO:
349 M4ERROR ((warning_status, 0,
350 _("modulo by zero in eval: %s"), expr));
351 break;
352
353 case NEGATIVE_EXPONENT:
354 M4ERROR ((warning_status, 0,
355 _("negative exponent in eval: %s"), expr));
356 break;
357
358 default:
359 M4ERROR ((warning_status, 0,
360 "INTERNAL ERROR: bad error code in evaluate ()"));
361 abort ();
362 }
363
364 return err != NO_ERROR;
365 }
366
367 /*---------------------------.
368 | Recursive descent parser. |
369 `---------------------------*/
370
371 static eval_error
372 logical_or_term (eval_token et, int32_t *v1)
373 {
374 int32_t v2;
375 eval_error er;
376
377 if ((er = logical_and_term (et, v1)) != NO_ERROR)
378 return er;
379
380 while ((et = eval_lex (&v2)) == LOR)
381 {
382 et = eval_lex (&v2);
383 if (et == ERROR)
384 return UNKNOWN_INPUT;
385
386 /* Implement short-circuiting of valid syntax. */
387 er = logical_and_term (et, &v2);
388 if (er == NO_ERROR)
389 *v1 = *v1 || v2;
390 else if (*v1 != 0 && er < SYNTAX_ERROR)
391 *v1 = 1;
392 else
393 return er;
394 }
395 if (et == ERROR)
396 return UNKNOWN_INPUT;
397
398 eval_undo ();
399 return NO_ERROR;
400 }
401
402 static eval_error
403 logical_and_term (eval_token et, int32_t *v1)
404 {
405 int32_t v2;
406 eval_error er;
407
408 if ((er = or_term (et, v1)) != NO_ERROR)
409 return er;
410
411 while ((et = eval_lex (&v2)) == LAND)
412 {
413 et = eval_lex (&v2);
414 if (et == ERROR)
415 return UNKNOWN_INPUT;
416
417 /* Implement short-circuiting of valid syntax. */
418 er = or_term (et, &v2);
419 if (er == NO_ERROR)
420 *v1 = *v1 && v2;
421 else if (*v1 == 0 && er < SYNTAX_ERROR)
422 ; /* v1 is already 0 */
423 else
424 return er;
425 }
426 if (et == ERROR)
427 return UNKNOWN_INPUT;
428
429 eval_undo ();
430 return NO_ERROR;
431 }
432
433 static eval_error
434 or_term (eval_token et, int32_t *v1)
435 {
436 int32_t v2;
437 eval_error er;
438
439 if ((er = xor_term (et, v1)) != NO_ERROR)
440 return er;
441
442 while ((et = eval_lex (&v2)) == OR)
443 {
444 et = eval_lex (&v2);
445 if (et == ERROR)
446 return UNKNOWN_INPUT;
447
448 if ((er = xor_term (et, &v2)) != NO_ERROR)
449 return er;
450
451 *v1 |= v2;
452 }
453 if (et == ERROR)
454 return UNKNOWN_INPUT;
455
456 eval_undo ();
457 return NO_ERROR;
458 }
459
460 static eval_error
461 xor_term (eval_token et, int32_t *v1)
462 {
463 int32_t v2;
464 eval_error er;
465
466 if ((er = and_term (et, v1)) != NO_ERROR)
467 return er;
468
469 while ((et = eval_lex (&v2)) == XOR)
470 {
471 et = eval_lex (&v2);
472 if (et == ERROR)
473 return UNKNOWN_INPUT;
474
475 if ((er = and_term (et, &v2)) != NO_ERROR)
476 return er;
477
478 *v1 ^= v2;
479 }
480 if (et == ERROR)
481 return UNKNOWN_INPUT;
482
483 eval_undo ();
484 return NO_ERROR;
485 }
486
487 static eval_error
488 and_term (eval_token et, int32_t *v1)
489 {
490 int32_t v2;
491 eval_error er;
492
493 if ((er = equality_term (et, v1)) != NO_ERROR)
494 return er;
495
496 while ((et = eval_lex (&v2)) == AND)
497 {
498 et = eval_lex (&v2);
499 if (et == ERROR)
500 return UNKNOWN_INPUT;
501
502 if ((er = equality_term (et, &v2)) != NO_ERROR)
503 return er;
504
505 *v1 &= v2;
506 }
507 if (et == ERROR)
508 return UNKNOWN_INPUT;
509
510 eval_undo ();
511 return NO_ERROR;
512 }
513
514 static eval_error
515 equality_term (eval_token et, int32_t *v1)
516 {
517 eval_token op;
518 int32_t v2;
519 eval_error er;
520
521 if ((er = cmp_term (et, v1)) != NO_ERROR)
522 return er;
523
524 /* In the 1.4.x series, we maintain the traditional behavior that
525 '=' is a synonym for '=='; however, this is contrary to POSIX and
526 we hope to convert '=' to mean assignment in 2.0. */
527 while ((op = eval_lex (&v2)) == EQ || op == NOTEQ || op == ASSIGN)
528 {
529 et = eval_lex (&v2);
530 if (et == ERROR)
531 return UNKNOWN_INPUT;
532
533 if ((er = cmp_term (et, &v2)) != NO_ERROR)
534 return er;
535
536 if (op == ASSIGN)
537 {
538 M4ERROR ((warning_status, 0, _("\
539 Warning: recommend ==, not =, for equality operator")));
540 op = EQ;
541 }
542 *v1 = (op == EQ) == (*v1 == v2);
543 }
544 if (op == ERROR)
545 return UNKNOWN_INPUT;
546
547 eval_undo ();
548 return NO_ERROR;
549 }
550
551 static eval_error
552 cmp_term (eval_token et, int32_t *v1)
553 {
554 eval_token op;
555 int32_t v2;
556 eval_error er;
557
558 if ((er = shift_term (et, v1)) != NO_ERROR)
559 return er;
560
561 while ((op = eval_lex (&v2)) == GT || op == GTEQ
562 || op == LS || op == LSEQ)
563 {
564
565 et = eval_lex (&v2);
566 if (et == ERROR)
567 return UNKNOWN_INPUT;
568
569 if ((er = shift_term (et, &v2)) != NO_ERROR)
570 return er;
571
572 switch (op)
573 {
574 case GT:
575 *v1 = *v1 > v2;
576 break;
577
578 case GTEQ:
579 *v1 = *v1 >= v2;
580 break;
581
582 case LS:
583 *v1 = *v1 < v2;
584 break;
585
586 case LSEQ:
587 *v1 = *v1 <= v2;
588 break;
589
590 default:
591 M4ERROR ((warning_status, 0,
592 "INTERNAL ERROR: bad comparison operator in cmp_term ()"));
593 abort ();
594 }
595 }
596 if (op == ERROR)
597 return UNKNOWN_INPUT;
598
599 eval_undo ();
600 return NO_ERROR;
601 }
602
603 static eval_error
604 shift_term (eval_token et, int32_t *v1)
605 {
606 eval_token op;
607 int32_t v2;
608 uint32_t u1;
609 eval_error er;
610
611 if ((er = add_term (et, v1)) != NO_ERROR)
612 return er;
613
614 while ((op = eval_lex (&v2)) == LSHIFT || op == RSHIFT)
615 {
616
617 et = eval_lex (&v2);
618 if (et == ERROR)
619 return UNKNOWN_INPUT;
620
621 if ((er = add_term (et, &v2)) != NO_ERROR)
622 return er;
623
624 /* Minimize undefined C behavior (shifting by a negative number,
625 shifting by the width or greater, left shift overflow, or
626 right shift of a negative number). Implement Java 32-bit
627 wrap-around semantics. This code assumes that the
628 implementation-defined overflow when casting unsigned to
629 signed is a silent twos-complement wrap-around. */
630 switch (op)
631 {
632 case LSHIFT:
633 u1 = *v1;
634 u1 <<= (uint32_t) (v2 & 0x1f);
635 *v1 = u1;
636 break;
637
638 case RSHIFT:
639 u1 = *v1 < 0 ? ~*v1 : *v1;
640 u1 >>= (uint32_t) (v2 & 0x1f);
641 *v1 = *v1 < 0 ? ~u1 : u1;
642 break;
643
644 default:
645 M4ERROR ((warning_status, 0,
646 "INTERNAL ERROR: bad shift operator in shift_term ()"));
647 abort ();
648 }
649 }
650 if (op == ERROR)
651 return UNKNOWN_INPUT;
652
653 eval_undo ();
654 return NO_ERROR;
655 }
656
657 static eval_error
658 add_term (eval_token et, int32_t *v1)
659 {
660 eval_token op;
661 int32_t v2;
662 eval_error er;
663
664 if ((er = mult_term (et, v1)) != NO_ERROR)
665 return er;
666
667 while ((op = eval_lex (&v2)) == PLUS || op == MINUS)
668 {
669 et = eval_lex (&v2);
670 if (et == ERROR)
671 return UNKNOWN_INPUT;
672
673 if ((er = mult_term (et, &v2)) != NO_ERROR)
674 return er;
675
676 /* Minimize undefined C behavior on overflow. This code assumes
677 that the implementation-defined overflow when casting
678 unsigned to signed is a silent twos-complement
679 wrap-around. */
680 if (op == PLUS)
681 *v1 = (int32_t) ((uint32_t) *v1 + (uint32_t) v2);
682 else
683 *v1 = (int32_t) ((uint32_t) *v1 - (uint32_t) v2);
684 }
685 if (op == ERROR)
686 return UNKNOWN_INPUT;
687
688 eval_undo ();
689 return NO_ERROR;
690 }
691
692 static eval_error
693 mult_term (eval_token et, int32_t *v1)
694 {
695 eval_token op;
696 int32_t v2;
697 eval_error er;
698
699 if ((er = exp_term (et, v1)) != NO_ERROR)
700 return er;
701
702 while ((op = eval_lex (&v2)) == TIMES || op == DIVIDE || op == MODULO)
703 {
704 et = eval_lex (&v2);
705 if (et == ERROR)
706 return UNKNOWN_INPUT;
707
708 if ((er = exp_term (et, &v2)) != NO_ERROR)
709 return er;
710
711 /* Minimize undefined C behavior on overflow. This code assumes
712 that the implementation-defined overflow when casting
713 unsigned to signed is a silent twos-complement
714 wrap-around. */
715 switch (op)
716 {
717 case TIMES:
718 *v1 = (int32_t) ((uint32_t) *v1 * (uint32_t) v2);
719 break;
720
721 case DIVIDE:
722 if (v2 == 0)
723 return DIVIDE_ZERO;
724 else if (v2 == -1)
725 /* Avoid overflow, and the x86 SIGFPE on INT_MIN / -1. */
726 *v1 = (int32_t) -(uint32_t) *v1;
727 else
728 *v1 /= v2;
729 break;
730
731 case MODULO:
732 if (v2 == 0)
733 return MODULO_ZERO;
734 else if (v2 == -1)
735 /* Avoid the x86 SIGFPE on INT_MIN % -1. */
736 *v1 = 0;
737 else
738 *v1 %= v2;
739 break;
740
741 default:
742 M4ERROR ((warning_status, 0,
743 "INTERNAL ERROR: bad operator in mult_term ()"));
744 abort ();
745 }
746 }
747 if (op == ERROR)
748 return UNKNOWN_INPUT;
749
750 eval_undo ();
751 return NO_ERROR;
752 }
753
754 static eval_error
755 exp_term (eval_token et, int32_t *v1)
756 {
757 uint32_t result;
758 int32_t v2;
759 eval_error er;
760
761 if ((er = unary_term (et, v1)) != NO_ERROR)
762 return er;
763
764 while ((et = eval_lex (&v2)) == EXPONENT)
765 {
766 et = eval_lex (&v2);
767 if (et == ERROR)
768 return UNKNOWN_INPUT;
769
770 if ((er = exp_term (et, &v2)) != NO_ERROR)
771 return er;
772
773 /* Minimize undefined C behavior on overflow. This code assumes
774 that the implementation-defined overflow when casting
775 unsigned to signed is a silent twos-complement
776 wrap-around. */
777 result = 1;
778 if (v2 < 0)
779 return NEGATIVE_EXPONENT;
780 if (*v1 == 0 && v2 == 0)
781 return DIVIDE_ZERO;
782 while (v2-- > 0)
783 result *= (uint32_t) *v1;
784 *v1 = result;
785 }
786 if (et == ERROR)
787 return UNKNOWN_INPUT;
788
789 eval_undo ();
790 return NO_ERROR;
791 }
792
793 static eval_error
794 unary_term (eval_token et, int32_t *v1)
795 {
796 eval_error er;
797
798 if (et == PLUS || et == MINUS || et == NOT || et == LNOT)
799 {
800 eval_token et2 = eval_lex (v1);
801 if (et2 == ERROR)
802 return UNKNOWN_INPUT;
803
804 if ((er = unary_term (et2, v1)) != NO_ERROR)
805 return er;
806
807 /* Minimize undefined C behavior on overflow. This code assumes
808 that the implementation-defined overflow when casting
809 unsigned to signed is a silent twos-complement
810 wrap-around. */
811 if (et == MINUS)
812 *v1 = (int32_t) -(uint32_t) *v1;
813 else if (et == NOT)
814 *v1 = ~*v1;
815 else if (et == LNOT)
816 *v1 = *v1 == 0 ? 1 : 0;
817 }
818 else if ((er = simple_term (et, v1)) != NO_ERROR)
819 return er;
820
821 return NO_ERROR;
822 }
823
824 static eval_error
825 simple_term (eval_token et, int32_t *v1)
826 {
827 int32_t v2;
828 eval_error er;
829
830 switch (et)
831 {
832 case LEFTP:
833 et = eval_lex (v1);
834 if (et == ERROR)
835 return UNKNOWN_INPUT;
836
837 if ((er = logical_or_term (et, v1)) != NO_ERROR)
838 return er;
839
840 et = eval_lex (&v2);
841 if (et == ERROR)
842 return UNKNOWN_INPUT;
843
844 if (et != RIGHTP)
845 return MISSING_RIGHT;
846
847 break;
848
849 case NUMBER:
850 break;
851
852 case BADOP:
853 return INVALID_OPERATOR;
854
855 default:
856 return SYNTAX_ERROR;
857 }
858 return NO_ERROR;
859 }