source: trunk/essentials/sys-devel/m4/src/eval.c

Last change on this file was 3090, checked in by bird, 18 years ago

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