OSDN Git Service

* cppexp.c (interpret_number): Optimize for single-digit
[pf3gnuchains/gcc-fork.git] / gcc / cppexp.c
1 /* Parse C expressions for cpplib.
2    Copyright (C) 1987, 1992, 1994, 1995, 1997, 1998, 1999, 2000, 2001,
3    2002 Free Software Foundation.
4    Contributed by Per Bothner, 1994.
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "cpplib.h"
24 #include "cpphash.h"
25
26 typedef struct cpp_num cpp_num;
27
28 #define PART_PRECISION (sizeof (cpp_num_part) * CHAR_BIT)
29 #define HALF_MASK (~(cpp_num_part) 0 >> (PART_PRECISION / 2))
30 #define LOW_PART(num_part) (num_part & HALF_MASK)
31 #define HIGH_PART(num_part) (num_part >> (PART_PRECISION / 2))
32
33 /* A preprocessing number.  Code assumes that any unused high bits of
34    the double integer are set to zero.  */
35 struct cpp_num
36 {
37   cpp_num_part high;
38   cpp_num_part low;
39   bool unsignedp;  /* True if value should be treated as unsigned.  */
40   bool overflow;   /* True if the most recent calculation overflowed.  */
41 };
42
43 struct op
44 {
45   cpp_num value;                     /* The value logically "right" of op.  */
46   enum cpp_ttype op;
47 };
48
49 /* Some simple utility routines on double integers.  */
50 #define num_zerop(num) ((num.low | num.high) == 0)
51 #define num_eq(num1, num2) (num1.low == num2.low && num1.high == num2.high)
52 static bool num_positive PARAMS ((cpp_num, size_t));
53 static bool num_greater_eq PARAMS ((cpp_num, cpp_num, size_t));
54 static cpp_num num_trim PARAMS ((cpp_num, size_t));
55 static cpp_num num_part_mul PARAMS ((cpp_num_part, cpp_num_part));
56
57 static cpp_num num_unary_op PARAMS ((cpp_reader *, cpp_num, enum cpp_ttype));
58 static cpp_num num_binary_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
59                                       enum cpp_ttype));
60 static cpp_num num_negate PARAMS ((cpp_num, size_t));
61 static cpp_num num_bitwise_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
62                                        enum cpp_ttype));
63 static cpp_num num_inequality_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
64                                           enum cpp_ttype));
65 static cpp_num num_equality_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
66                                         enum cpp_ttype));
67 static cpp_num num_mul PARAMS ((cpp_reader *, cpp_num, cpp_num,
68                                 enum cpp_ttype));
69 static cpp_num num_div_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
70                                    enum cpp_ttype));
71 static cpp_num num_lshift PARAMS ((cpp_num, size_t, size_t));
72 static cpp_num num_rshift PARAMS ((cpp_num, size_t, size_t));
73
74 static cpp_num append_digit PARAMS ((cpp_num, int, int, size_t));
75 static cpp_num interpret_number PARAMS ((cpp_reader *, const cpp_token *));
76 static cpp_num parse_defined PARAMS ((cpp_reader *));
77 static cpp_num eval_token PARAMS ((cpp_reader *, const cpp_token *));
78 static struct op *reduce PARAMS ((cpp_reader *, struct op *, enum cpp_ttype));
79
80 /* Token type abuse.  There is no "error" token, but we can't get
81    comments in #if, so we can abuse that token type.  Similarly,
82    create unary plus and minus operators.  */
83 #define CPP_ERROR CPP_COMMENT
84 #define CPP_UPLUS (CPP_LAST_CPP_OP + 1)
85 #define CPP_UMINUS (CPP_LAST_CPP_OP + 2)
86
87 /* With -O2, gcc appears to produce nice code, moving the error
88    message load and subsequent jump completely out of the main path.  */
89 #define SYNTAX_ERROR(msgid) \
90   do { cpp_error (pfile, DL_ERROR, msgid); goto syntax_error; } while(0)
91 #define SYNTAX_ERROR2(msgid, arg) \
92   do { cpp_error (pfile, DL_ERROR, msgid, arg); goto syntax_error; } while(0)
93
94 struct suffix
95 {
96   const unsigned char s[4];
97   const unsigned char u;
98   const unsigned char l;
99 };
100
101 static const struct suffix vsuf_1[] = {
102   { "u", 1, 0 }, { "U", 1, 0 },
103   { "l", 0, 1 }, { "L", 0, 1 }
104 };
105
106 static const struct suffix vsuf_2[] = {
107   { "ul", 1, 1 }, { "UL", 1, 1 }, { "uL", 1, 1 }, { "Ul", 1, 1 },
108   { "lu", 1, 1 }, { "LU", 1, 1 }, { "Lu", 1, 1 }, { "lU", 1, 1 },
109   { "ll", 0, 2 }, { "LL", 0, 2 }
110 };
111
112 static const struct suffix vsuf_3[] = {
113   { "ull", 1, 2 }, { "ULL", 1, 2 }, { "uLL", 1, 2 }, { "Ull", 1, 2 },
114   { "llu", 1, 2 }, { "LLU", 1, 2 }, { "LLu", 1, 2 }, { "llU", 1, 2 }
115 };
116
117 /* Append DIGIT to NUM, a number of PRECISION bits being read in base
118    BASE.  */
119 static cpp_num
120 append_digit (num, digit, base, precision)
121      cpp_num num;
122      int digit, base;
123      size_t precision;
124 {
125   cpp_num result;
126   unsigned int shift = 3 + (base == 16);
127   bool overflow;
128   cpp_num_part add_high, add_low;
129
130   /* Multiply by 8 or 16.  Catching this overflow here means we don't
131      need to worry about add_high overflowing.  */
132   overflow = num.high >> (PART_PRECISION - shift);
133   result.high = num.high << shift;
134   result.low = num.low << shift;
135   result.high |= num.low >> (PART_PRECISION - shift);
136
137   if (base == 10)
138     {
139       add_low = num.low << 1;
140       add_high = (num.high << 1) + (num.low >> (PART_PRECISION - 1));
141     }
142   else
143     add_high = add_low = 0;
144
145   if (add_low + digit < add_low)
146     add_high++;
147   add_low += digit;
148     
149   if (result.low + add_low < result.low)
150     add_high++;
151   if (result.high + add_high < result.high)
152     overflow = true;
153
154   result.low += add_low;
155   result.high += add_high;
156
157   /* The above code catches overflow of a cpp_num type.  This catches
158      overflow of the (possibly shorter) target precision.  */
159   num.low = result.low;
160   num.high = result.high;
161   result = num_trim (result, precision);
162   if (!num_eq (result, num))
163     overflow = true;
164
165   result.unsignedp = num.unsignedp;
166   result.overflow = overflow;
167   return result;
168 }
169
170 /* Parse and convert what is presumably an integer in TOK.  Accepts
171    decimal, hex, or octal with or without size suffixes.  Returned op
172    is CPP_ERROR on error, otherwise it is a CPP_NUMBER.  */
173 static cpp_num
174 interpret_number (pfile, tok)
175      cpp_reader *pfile;
176      const cpp_token *tok;
177 {
178   cpp_num result;
179   cpp_num_part max;
180   const uchar *p = tok->val.str.text;
181   const uchar *end;
182   const struct suffix *sufftab;
183   size_t precision;
184   unsigned int i, nsuff, base, c;
185   bool overflow, big_digit;
186
187   result.low = 0;
188   result.high = 0;
189   result.unsignedp = 0;
190   result.overflow = 0;
191
192   /* Common case of a single digit.  */
193   end = p + tok->val.str.len;
194   if (tok->val.str.len == 1 && (unsigned int) (p[0] - '0') <= 9)
195     {
196       result.low = p[0] - '0';
197       return result;
198     }
199
200   base = 10;
201   if (p[0] == '0')
202     {
203       if (end - p >= 3 && (p[1] == 'x' || p[1] == 'X'))
204         {
205           p += 2;
206           base = 16;
207         }
208       else
209         {
210           p += 1;
211           base = 8;
212         }
213     }
214
215   c = 0;
216   overflow = big_digit = false;
217   precision = CPP_OPTION (pfile, precision);
218
219   /* We can add a digit to numbers less than this without needing
220      double integers.  9 is the maximum digit for octal and decimal;
221      for hex it is annihilated by the division anyway.  */
222   max = ~(cpp_num_part) 0;
223   if (precision < PART_PRECISION)
224     max >>= PART_PRECISION - precision;
225   max = (max - 9) / base + 1;
226
227   for(; p < end; p++)
228     {
229       c = *p;
230
231       if (ISDIGIT (c) || (base == 16 && ISXDIGIT (c)))
232         c = hex_value (c);
233       else
234         break;
235
236       if (c >= base)
237         big_digit = true;
238
239       /* Strict inequality for when max is set to zero.  */
240       if (result.low < max)
241         result.low = result.low * base + c;
242       else
243         {
244           result = append_digit (result, c, base, precision);
245           overflow |= result.overflow;
246           max = 0;
247         }
248     }
249
250   if (p < end)
251     {
252       /* Check for a floating point constant.  Note that float constants
253          with an exponent or suffix but no decimal point are technically
254          invalid (C99 6.4.4.2) but accepted elsewhere.  */
255       if ((c == '.' || c == 'F' || c == 'f')
256           || (base == 10 && (c == 'E' || c == 'e')
257               && p+1 < end && (p[1] == '+' || p[1] == '-'))
258           || (base == 16 && (c == 'P' || c == 'p')
259               && p+1 < end && (p[1] == '+' || p[1] == '-')))
260         SYNTAX_ERROR ("floating point numbers are not valid in #if");
261
262       /* Determine the suffix. l means long, and u means unsigned.
263          See the suffix tables, above.  */
264       switch (end - p)
265         {
266         case 1: sufftab = vsuf_1; nsuff = ARRAY_SIZE (vsuf_1); break;
267         case 2: sufftab = vsuf_2; nsuff = ARRAY_SIZE (vsuf_2); break;
268         case 3: sufftab = vsuf_3; nsuff = ARRAY_SIZE (vsuf_3); break;
269         default: goto invalid_suffix;
270         }
271
272       for (i = 0; i < nsuff; i++)
273         if (memcmp (p, sufftab[i].s, end - p) == 0)
274           break;
275       if (i == nsuff)
276         goto invalid_suffix;
277       result.unsignedp = sufftab[i].u;
278
279       if (CPP_WTRADITIONAL (pfile)
280           && sufftab[i].u
281           && ! cpp_sys_macro_p (pfile))
282         cpp_error (pfile, DL_WARNING, "traditional C rejects the `U' suffix");
283       if (sufftab[i].l == 2 && CPP_OPTION (pfile, pedantic)
284           && ! CPP_OPTION (pfile, c99))
285         cpp_error (pfile, DL_PEDWARN,
286                    "too many 'l' suffixes in integer constant");
287     }
288
289   if (big_digit)
290     cpp_error (pfile, DL_PEDWARN,
291                "integer constant contains digits beyond the radix");
292
293   if (overflow)
294     cpp_error (pfile, DL_PEDWARN, "integer constant too large for its type");
295   /* If too big to be signed, consider it unsigned.  */
296   else if (!result.unsignedp && !num_positive (result, precision))
297     {
298       if (base == 10)
299         cpp_error (pfile, DL_WARNING,
300                    "integer constant is so large that it is unsigned");
301       result.unsignedp = 1;
302     }
303
304   return result;
305
306  invalid_suffix:
307   cpp_error (pfile, DL_ERROR, "invalid suffix '%.*s' on integer constant",
308              (int) (end - p), p);
309  syntax_error:
310   return result;
311 }
312
313 /* Handle meeting "defined" in a preprocessor expression.  */
314 static cpp_num
315 parse_defined (pfile)
316      cpp_reader *pfile;
317 {
318   cpp_num result;
319   int paren = 0;
320   cpp_hashnode *node = 0;
321   const cpp_token *token;
322   cpp_context *initial_context = pfile->context;
323
324   /* Don't expand macros.  */
325   pfile->state.prevent_expansion++;
326
327   token = cpp_get_token (pfile);
328   if (token->type == CPP_OPEN_PAREN)
329     {
330       paren = 1;
331       token = cpp_get_token (pfile);
332     }
333
334   if (token->type == CPP_NAME)
335     {
336       node = token->val.node;
337       if (paren && cpp_get_token (pfile)->type != CPP_CLOSE_PAREN)
338         {
339           cpp_error (pfile, DL_ERROR, "missing ')' after \"defined\"");
340           node = 0;
341         }
342     }
343   else
344     {
345       cpp_error (pfile, DL_ERROR,
346                  "operator \"defined\" requires an identifier");
347       if (token->flags & NAMED_OP)
348         {
349           cpp_token op;
350
351           op.flags = 0;
352           op.type = token->type;
353           cpp_error (pfile, DL_ERROR,
354                      "(\"%s\" is an alternative token for \"%s\" in C++)",
355                      cpp_token_as_text (pfile, token),
356                      cpp_token_as_text (pfile, &op));
357         }
358     }
359
360   if (node)
361     {
362       if (pfile->context != initial_context)
363         cpp_error (pfile, DL_WARNING,
364                    "this use of \"defined\" may not be portable");
365
366       /* A possible controlling macro of the form #if !defined ().
367          _cpp_parse_expr checks there was no other junk on the line.  */
368       pfile->mi_ind_cmacro = node;
369     }
370
371   pfile->state.prevent_expansion--;
372
373   result.unsignedp = 0;
374   result.high = 0;
375   result.overflow = 0;
376   result.low = node && node->type == NT_MACRO;
377   return result;
378 }
379
380 /* Convert a token into a CPP_NUMBER (an interpreted preprocessing
381    number or character constant, or the result of the "defined" or "#"
382    operators), or CPP_ERROR on error.  */
383 static cpp_num
384 eval_token (pfile, token)
385      cpp_reader *pfile;
386      const cpp_token *token;
387 {
388   cpp_num result;
389   unsigned int temp;
390   int unsignedp = 0;
391
392   switch (token->type)
393     {
394     case CPP_NUMBER:
395       return interpret_number (pfile, token);
396
397     case CPP_WCHAR:
398     case CPP_CHAR:
399       {
400         cppchar_t cc = cpp_interpret_charconst (pfile, token,
401                                                 &temp, &unsignedp);
402
403         result.high = 0;
404         result.low = cc;
405         /* Sign-extend the result if necessary.  */
406         if (!unsignedp && (cppchar_signed_t) cc < 0)
407           {
408             if (PART_PRECISION > BITS_PER_CPPCHAR_T)
409               result.low |= ~(~(cpp_num_part) 0
410                               >> (PART_PRECISION - BITS_PER_CPPCHAR_T));
411             result.high = ~(cpp_num_part) 0;
412             result = num_trim (result, CPP_OPTION (pfile, precision));
413           }
414       }
415       break;
416
417     case CPP_NAME:
418       if (token->val.node == pfile->spec_nodes.n_defined)
419         return parse_defined (pfile);
420       else if (CPP_OPTION (pfile, cplusplus)
421                && (token->val.node == pfile->spec_nodes.n_true
422                    || token->val.node == pfile->spec_nodes.n_false))
423         {
424           result.high = 0;
425           result.low = (token->val.node == pfile->spec_nodes.n_true);
426
427           /* Warn about use of true or false in #if when pedantic
428              and stdbool.h has not been included.  */
429           if (CPP_PEDANTIC (pfile)
430               && ! cpp_defined (pfile, DSC("__bool_true_false_are_defined")))
431             cpp_error (pfile, DL_PEDWARN,
432                        "ISO C++ does not permit \"%s\" in #if",
433                        NODE_NAME (token->val.node));
434         }
435       else
436         {
437           result.high = 0;
438           result.low = 0;
439           if (CPP_OPTION (pfile, warn_undef) && !pfile->state.skip_eval)
440             cpp_error (pfile, DL_WARNING, "\"%s\" is not defined",
441                        NODE_NAME (token->val.node));
442         }
443       break;
444
445     default: /* CPP_HASH */
446       _cpp_test_assertion (pfile, &temp);
447       result.high = 0;
448       result.low = temp;
449     }
450
451   result.unsignedp = unsignedp;
452   result.overflow = 0;
453   return result;
454 }
455 \f
456 /* Operator precedence and flags table.
457
458 After an operator is returned from the lexer, if it has priority less
459 than the operator on the top of the stack, we reduce the stack by one
460 operator and repeat the test.  Since equal priorities do not reduce,
461 this is naturally right-associative.
462
463 We handle left-associative operators by decrementing the priority of
464 just-lexed operators by one, but retaining the priority of operators
465 already on the stack.
466
467 The remaining cases are '(' and ')'.  We handle '(' by skipping the
468 reduction phase completely.  ')' is given lower priority than
469 everything else, including '(', effectively forcing a reduction of the
470 parenthesised expression.  If there is a matching '(', the routine
471 reduce() exits immediately.  If the normal exit route sees a ')', then
472 there cannot have been a matching '(' and an error message is output.
473
474 The parser assumes all shifted operators require a left operand unless
475 the flag NO_L_OPERAND is set.  These semantics are automatic; any
476 extra semantics need to be handled with operator-specific code.  */
477
478 /* Flags.  */
479 #define NO_L_OPERAND    (1 << 0)
480 #define LEFT_ASSOC      (1 << 1)
481
482 /* Arity. */
483 #define UNARY           (1 << 0)
484 #define BINARY          (1 << 1)
485 #define OTHER           (1 << 2)
486
487 typedef cpp_num (*binary_handler) PARAMS ((cpp_reader *, cpp_num, cpp_num,
488                                            enum cpp_ttype));
489 /* Operator to priority map.  Must be in the same order as the first
490    N entries of enum cpp_ttype.  */
491 static const struct operator
492 {
493   uchar prio;
494   uchar flags;
495   uchar arity;
496   binary_handler handler;
497 } optab[] =
498 {
499   /* EQ */              {0, 0, OTHER, NULL},    /* Shouldn't happen.  */
500   /* NOT */             {16, NO_L_OPERAND, UNARY, NULL},
501   /* GREATER */         {12, LEFT_ASSOC, BINARY, num_inequality_op},
502   /* LESS */            {12, LEFT_ASSOC, BINARY, num_inequality_op},
503   /* PLUS */            {14, LEFT_ASSOC, BINARY, num_binary_op},
504   /* MINUS */           {14, LEFT_ASSOC, BINARY, num_binary_op},
505   /* MULT */            {15, LEFT_ASSOC, BINARY, num_mul},
506   /* DIV */             {15, LEFT_ASSOC, BINARY, num_div_op},
507   /* MOD */             {15, LEFT_ASSOC, BINARY, num_div_op},
508   /* AND */             {9, LEFT_ASSOC, BINARY, num_bitwise_op},
509   /* OR */              {7, LEFT_ASSOC, BINARY, num_bitwise_op},
510   /* XOR */             {8, LEFT_ASSOC, BINARY, num_bitwise_op},
511   /* RSHIFT */          {13, LEFT_ASSOC, BINARY, num_binary_op},
512   /* LSHIFT */          {13, LEFT_ASSOC, BINARY, num_binary_op},
513
514   /* MIN */             {10, LEFT_ASSOC, BINARY, num_binary_op},
515   /* MAX */             {10, LEFT_ASSOC, BINARY, num_binary_op},
516
517   /* COMPL */           {16, NO_L_OPERAND, UNARY, NULL},
518   /* AND_AND */         {6, LEFT_ASSOC, OTHER, NULL},
519   /* OR_OR */           {5, LEFT_ASSOC, OTHER, NULL},
520   /* QUERY */           {3, 0, OTHER, NULL},
521   /* COLON */           {4, LEFT_ASSOC, OTHER, NULL},
522   /* COMMA */           {2, LEFT_ASSOC, BINARY, num_binary_op},
523   /* OPEN_PAREN */      {1, NO_L_OPERAND, OTHER, NULL},
524   /* CLOSE_PAREN */     {0, 0, OTHER, NULL},
525   /* EOF */             {0, 0, OTHER, NULL},
526   /* EQ_EQ */           {11, LEFT_ASSOC, BINARY, num_equality_op},
527   /* NOT_EQ */          {11, LEFT_ASSOC, BINARY, num_equality_op},
528   /* GREATER_EQ */      {12, LEFT_ASSOC, BINARY, num_inequality_op},
529   /* LESS_EQ */         {12, LEFT_ASSOC, BINARY, num_inequality_op},
530   /* UPLUS */           {16, NO_L_OPERAND, UNARY, NULL},
531   /* UMINUS */          {16, NO_L_OPERAND, UNARY, NULL}
532 };
533
534 /* Parse and evaluate a C expression, reading from PFILE.
535    Returns the truth value of the expression.
536
537    The implementation is an operator precedence parser, i.e. a
538    bottom-up parser, using a stack for not-yet-reduced tokens.
539
540    The stack base is op_stack, and the current stack pointer is 'top'.
541    There is a stack element for each operator (only), and the most
542    recently pushed operator is 'top->op'.  An operand (value) is
543    stored in the 'value' field of the stack element of the operator
544    that precedes it.  */
545 bool
546 _cpp_parse_expr (pfile)
547      cpp_reader *pfile;
548 {
549   struct op *top = pfile->op_stack;
550   const cpp_token *token = NULL, *prev_token;
551   unsigned int lex_count;
552   bool saw_leading_not, want_value = true;
553
554   pfile->state.skip_eval = 0;
555
556   /* Set up detection of #if ! defined().  */
557   pfile->mi_ind_cmacro = 0;
558   saw_leading_not = false;
559   lex_count = 0;
560
561   /* Lowest priority operator prevents further reductions.  */
562   top->op = CPP_EOF;
563
564   for (;;)
565     {
566       struct op op;
567
568       prev_token = token;
569       token = cpp_get_token (pfile);
570       lex_count++;
571       op.op = token->type;
572
573       switch (op.op)
574         {
575           /* These tokens convert into values.  */
576         case CPP_NUMBER:
577         case CPP_CHAR:
578         case CPP_WCHAR:
579         case CPP_NAME:
580         case CPP_HASH:
581           if (!want_value)
582             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
583                            cpp_token_as_text (pfile, token));
584           want_value = false;
585           top->value = eval_token (pfile, token);
586           continue;
587
588         case CPP_NOT:
589           saw_leading_not = lex_count == 1;
590           break;
591         case CPP_PLUS:
592           if (want_value)
593             op.op = CPP_UPLUS;
594           break;
595         case CPP_MINUS:
596           if (want_value)
597             op.op = CPP_UMINUS;
598           break;
599         case CPP_OTHER:
600           if (ISGRAPH (token->val.c))
601             SYNTAX_ERROR2 ("invalid character '%c' in #if", token->val.c);
602           else
603             SYNTAX_ERROR2 ("invalid character '\\%03o' in #if", token->val.c);
604
605         default:
606           if ((int) op.op <= (int) CPP_EQ || (int) op.op >= (int) CPP_PLUS_EQ)
607             SYNTAX_ERROR2 ("token \"%s\" is not valid in #if expressions",
608                            cpp_token_as_text (pfile, token));
609           break;
610         }
611
612       /* Check we have a value or operator as appropriate.  */
613       if (optab[op.op].flags & NO_L_OPERAND)
614         {
615           if (!want_value)
616             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
617                            cpp_token_as_text (pfile, token));
618         }
619       else if (want_value)
620         {
621           /* Ordering here is subtle and intended to favour the
622              missing parenthesis diagnostics over alternatives.  */
623           if (op.op == CPP_CLOSE_PAREN)
624             {
625               if (top->op == CPP_OPEN_PAREN)
626                 SYNTAX_ERROR ("void expression between '(' and ')'");
627             }
628           else if (top->op == CPP_EOF)
629             SYNTAX_ERROR ("#if with no expression");
630           if (top->op != CPP_EOF && top->op != CPP_OPEN_PAREN)
631             SYNTAX_ERROR2 ("operator '%s' has no right operand",
632                            cpp_token_as_text (pfile, prev_token));
633         }
634
635       top = reduce (pfile, top, op.op);
636       if (!top)
637         goto syntax_error;
638
639       if (op.op == CPP_EOF)
640         break;
641
642       switch (op.op)
643         {
644         case CPP_CLOSE_PAREN:
645           continue;
646         case CPP_OR_OR:
647           if (!num_zerop (top->value))
648             pfile->state.skip_eval++;
649           break;
650         case CPP_AND_AND:
651         case CPP_QUERY:
652           if (num_zerop (top->value))
653             pfile->state.skip_eval++;
654           break;
655         case CPP_COLON:
656           if (top->op != CPP_QUERY)
657             SYNTAX_ERROR (" ':' without preceding '?'");
658           if (!num_zerop (top[-1].value)) /* Was '?' condition true?  */
659             pfile->state.skip_eval++;
660           else
661             pfile->state.skip_eval--;
662         default:
663           break;
664         }
665
666       want_value = true;
667
668       /* Check for and handle stack overflow.  */
669       if (++top == pfile->op_limit)
670         top = _cpp_expand_op_stack (pfile);
671
672       top->op = op.op;
673     }
674
675   /* The controlling macro expression is only valid if we called lex 3
676      times: <!> <defined expression> and <EOF>.  push_conditional ()
677      checks that we are at top-of-file.  */
678   if (pfile->mi_ind_cmacro && !(saw_leading_not && lex_count == 3))
679     pfile->mi_ind_cmacro = 0;
680
681   if (top != pfile->op_stack)
682     {
683       cpp_error (pfile, DL_ICE, "unbalanced stack in #if");
684     syntax_error:
685       return false;  /* Return false on syntax error.  */
686     }
687
688   return !num_zerop (top->value);
689 }
690
691 /* Reduce the operator / value stack if possible, in preparation for
692    pushing operator OP.  Returns NULL on error, otherwise the top of
693    the stack.  */
694 static struct op *
695 reduce (pfile, top, op)
696      cpp_reader *pfile;
697      struct op *top;
698      enum cpp_ttype op;
699 {
700   unsigned int prio;
701
702   if (top->op <= CPP_EQ || top->op > CPP_LAST_CPP_OP + 2)
703     {
704     bad_op:
705       cpp_error (pfile, DL_ICE, "impossible operator '%u'", top->op);
706       return 0;
707     }
708
709   if (op == CPP_OPEN_PAREN)
710     return top;
711
712   /* Decrement the priority of left-associative operators to force a
713      reduction with operators of otherwise equal priority.  */
714   prio = optab[op].prio - ((optab[op].flags & LEFT_ASSOC) != 0);
715   while (prio < optab[top->op].prio)
716     {
717       if (optab[top->op].arity == UNARY)
718         {
719           if (!pfile->state.skip_eval)
720             top[-1].value = num_unary_op (pfile, top->value, top->op);
721           top--;
722         }
723       else if (optab[top->op].arity == BINARY)
724         {
725           if (!pfile->state.skip_eval)
726             top[-1].value = (* (binary_handler) optab[top->op].handler)
727               (pfile, top[-1].value, top->value, top->op);
728           top--;
729         }
730       /* Anything changing skip_eval has to be handled here.  */
731       else switch (top--->op)
732         {
733         case CPP_OR_OR:
734           if (!num_zerop (top->value))
735             pfile->state.skip_eval--;
736           top->value.low = !num_zerop (top->value) || !num_zerop (top[1].value);
737           top->value.high = 0;
738           top->value.unsignedp = false;
739           top->value.overflow = false;
740           break;
741
742         case CPP_AND_AND:
743           if (num_zerop (top->value))
744             pfile->state.skip_eval--;
745           top->value.low = !num_zerop (top->value) && !num_zerop (top[1].value);
746           top->value.high = 0;
747           top->value.unsignedp = false;
748           top->value.overflow = false;
749           break;
750
751         case CPP_OPEN_PAREN:
752           if (op != CPP_CLOSE_PAREN)
753             {
754               cpp_error (pfile, DL_ERROR, "missing ')' in expression");
755               return 0;
756             }
757           top->value = top[1].value;
758           return top;
759
760         case CPP_COLON:
761           top--;
762           if (!num_zerop (top->value))
763             {
764               pfile->state.skip_eval--;
765               top->value = top[1].value;
766             }
767           else
768             top->value = top[2].value;
769           top->value.unsignedp = (top[1].value.unsignedp
770                                   || top[2].value.unsignedp);
771           break;
772
773         case CPP_QUERY:
774           cpp_error (pfile, DL_ERROR, "'?' without following ':'");
775           return 0;
776
777         default:
778           goto bad_op;
779         }
780
781       if (top->value.overflow && !pfile->state.skip_eval)
782         cpp_error (pfile, DL_PEDWARN,
783                    "integer overflow in preprocessor expression");
784     }
785
786   if (op == CPP_CLOSE_PAREN)
787     {
788       cpp_error (pfile, DL_ERROR, "missing '(' in expression");
789       return 0;
790     }
791
792   return top;
793 }
794
795 /* Returns the position of the old top of stack after expansion.  */
796 struct op *
797 _cpp_expand_op_stack (pfile)
798      cpp_reader *pfile;
799 {
800   size_t old_size = (size_t) (pfile->op_limit - pfile->op_stack);
801   size_t new_size = old_size * 2 + 20;
802
803   pfile->op_stack = (struct op *) xrealloc (pfile->op_stack,
804                                             new_size * sizeof (struct op));
805   pfile->op_limit = pfile->op_stack + new_size;
806
807   return pfile->op_stack + old_size;
808 }
809
810 /* Clears the unused high order bits of the number pointed to by PNUM.  */
811 static cpp_num
812 num_trim (num, precision)
813      cpp_num num;
814      size_t precision;
815 {
816   if (precision > PART_PRECISION)
817     {
818       precision -= PART_PRECISION;
819       if (precision < PART_PRECISION)
820         num.high &= ((cpp_num_part) 1 << precision) - 1;
821     }
822   else
823     {
824       if (precision < PART_PRECISION)
825         num.low &= ((cpp_num_part) 1 << precision) - 1;
826       num.high = 0;
827     }
828
829   return num;
830 }
831
832 /* True iff A (presumed signed) >= 0.  */
833 static bool
834 num_positive (num, precision)
835      cpp_num num;
836      size_t precision;
837 {
838   if (precision > PART_PRECISION)
839     {
840       precision -= PART_PRECISION;
841       return (num.high & (cpp_num_part) 1 << (precision - 1)) == 0;
842     }
843
844   return (num.low & (cpp_num_part) 1 << (precision - 1)) == 0;
845 }
846
847 /* Returns the negative of NUM.  */
848 static cpp_num
849 num_negate (num, precision)
850      cpp_num num;
851      size_t precision;
852 {
853   cpp_num copy;
854
855   copy = num;
856   num.high = ~num.high;
857   num.low = ~num.low;
858   if (++num.low == 0)
859     num.high++;
860   num = num_trim (num, precision);
861   num.overflow = (!num.unsignedp && num_eq (num, copy) && !num_zerop (num));
862
863   return num;
864 }
865
866 /* Returns true if A >= B.  */
867 static bool
868 num_greater_eq (pa, pb, precision)
869      cpp_num pa, pb;
870      size_t precision;
871 {
872   bool unsignedp;
873
874   unsignedp = pa.unsignedp || pb.unsignedp;
875
876   if (!unsignedp)
877     {
878       /* Both numbers have signed type.  If they are of different
879        sign, the answer is the sign of A.  */
880       unsignedp = num_positive (pa, precision);
881
882       if (unsignedp != num_positive (pb, precision))
883         return unsignedp;
884
885       /* Otherwise we can do an unsigned comparison.  */
886     }
887
888   return (pa.high > pb.high) || (pa.high == pb.high && pa.low >= pb.low);
889 }
890
891 /* Returns LHS OP RHS, where OP is a bit-wise operation.  */
892 static cpp_num
893 num_bitwise_op (pfile, lhs, rhs, op)
894      cpp_reader *pfile ATTRIBUTE_UNUSED;
895      cpp_num lhs, rhs;
896      enum cpp_ttype op;
897 {
898   lhs.overflow = false;
899   lhs.unsignedp = lhs.unsignedp || rhs.unsignedp;
900
901   /* As excess precision is zeroed, there is no need to num_trim () as
902      these operations cannot introduce a set bit there.  */
903   if (op == CPP_AND)
904     {
905       lhs.low &= rhs.low;
906       lhs.high &= rhs.high;
907     }
908   else if (op == CPP_OR)
909     {
910       lhs.low |= rhs.low;
911       lhs.high |= rhs.high;
912     }
913   else
914     {
915       lhs.low ^= rhs.low;
916       lhs.high ^= rhs.high;
917     }
918
919   return lhs;
920 }
921
922 /* Returns LHS OP RHS, where OP is an inequality.  */
923 static cpp_num
924 num_inequality_op (pfile, lhs, rhs, op)
925      cpp_reader *pfile;
926      cpp_num lhs, rhs;
927      enum cpp_ttype op;
928 {
929   bool gte = num_greater_eq (lhs, rhs, CPP_OPTION (pfile, precision));
930
931   if (op == CPP_GREATER_EQ)
932     lhs.low = gte;
933   else if (op == CPP_LESS)
934     lhs.low = !gte;
935   else if (op == CPP_GREATER)
936     lhs.low = gte && !num_eq (lhs, rhs);
937   else /* CPP_LESS_EQ.  */
938     lhs.low = !gte || num_eq (lhs, rhs);
939
940   lhs.high = 0;
941   lhs.overflow = false;
942   lhs.unsignedp = false;
943   return lhs;
944 }
945
946 /* Returns LHS OP RHS, where OP is == or !=.  */
947 static cpp_num
948 num_equality_op (pfile, lhs, rhs, op)
949      cpp_reader *pfile ATTRIBUTE_UNUSED;
950      cpp_num lhs, rhs;
951      enum cpp_ttype op;
952 {
953   lhs.low = num_eq (lhs, rhs);
954   if (op == CPP_NOT_EQ)
955     lhs.low = !lhs.low;
956   lhs.high = 0;
957   lhs.overflow = false;
958   lhs.unsignedp = false;
959   return lhs;
960 }
961
962 /* Shift NUM, of width PRECISION, right by N bits.  */
963 static cpp_num
964 num_rshift (num, precision, n)
965      cpp_num num;
966      size_t precision, n;
967 {
968   cpp_num_part sign_mask;
969
970   if (num.unsignedp || num_positive (num, precision))
971     sign_mask = 0;
972   else
973     sign_mask = ~(cpp_num_part) 0;
974
975   if (n >= precision)
976     num.high = num.low = sign_mask;
977   else
978     {
979       /* Sign-extend.  */
980       if (precision < PART_PRECISION)
981         num.high = sign_mask, num.low |= sign_mask << precision;
982       else if (precision < 2 * PART_PRECISION)
983         num.high |= sign_mask << (precision - PART_PRECISION);
984
985       if (n >= PART_PRECISION)
986         {
987           n -= PART_PRECISION;
988           num.low = num.high;
989           num.high = sign_mask;
990         }
991
992       if (n)
993         {
994           num.low = (num.low >> n) | (num.high << (PART_PRECISION - n));
995           num.high = (num.high >> n) | (sign_mask << (PART_PRECISION - n));
996         }
997     }
998
999   num = num_trim (num, precision);
1000   num.overflow = false;
1001   return num;
1002 }
1003
1004 /* Shift NUM, of width PRECISION, left by N bits.  */
1005 static cpp_num
1006 num_lshift (num, precision, n)
1007      cpp_num num;
1008      size_t precision, n;
1009 {
1010   if (n >= precision)
1011     {
1012       num.overflow = !num.unsignedp && !num_zerop (num);
1013       num.high = num.low = 0;
1014     }
1015   else
1016     {
1017       cpp_num orig, maybe_orig;
1018       size_t m = n;
1019
1020       orig = num;
1021       if (m >= PART_PRECISION)
1022         {
1023           m -= PART_PRECISION;
1024           num.high = num.low;
1025           num.low = 0;
1026         }
1027       if (m)
1028         {
1029           num.high = (num.high << m) | (num.low >> (PART_PRECISION - m));
1030           num.low <<= m;
1031         }
1032       num = num_trim (num, precision);
1033
1034       if (num.unsignedp)
1035         num.overflow = false;
1036       else
1037         {
1038           maybe_orig = num_rshift (num, precision, n);
1039           num.overflow = !num_eq (orig, maybe_orig);
1040         }
1041     }
1042
1043   return num;
1044 }
1045
1046 /* The four unary operators: +, -, ! and ~.  */
1047 static cpp_num
1048 num_unary_op (pfile, num, op)
1049      cpp_reader *pfile;
1050      cpp_num num;
1051      enum cpp_ttype op;
1052 {
1053   switch (op)
1054     {
1055     case CPP_UPLUS:
1056       if (CPP_WTRADITIONAL (pfile))
1057         cpp_error (pfile, DL_WARNING,
1058                    "traditional C rejects the unary plus operator");
1059       num.overflow = false;
1060       break;
1061
1062     case CPP_UMINUS:
1063       num = num_negate (num, CPP_OPTION (pfile, precision));
1064       break;
1065
1066     case CPP_COMPL:
1067       num.high = ~num.high;
1068       num.low = ~num.low;
1069       num = num_trim (num, CPP_OPTION (pfile, precision));
1070       num.overflow = false;
1071       break;
1072
1073     default: /* case CPP_NOT: */
1074       num.low = num_zerop (num);
1075       num.high = 0;
1076       num.overflow = false;
1077       num.unsignedp = false;
1078       break;
1079     }
1080
1081   return num;
1082 }
1083
1084 /* The various binary operators.  */
1085 static cpp_num
1086 num_binary_op (pfile, lhs, rhs, op)
1087      cpp_reader *pfile;
1088      cpp_num lhs, rhs;
1089      enum cpp_ttype op;
1090 {
1091   cpp_num result;
1092   size_t precision = CPP_OPTION (pfile, precision);
1093   bool gte;
1094   size_t n;
1095
1096   switch (op)
1097     {
1098       /* Shifts.  */
1099     case CPP_LSHIFT:
1100     case CPP_RSHIFT:
1101       if (!rhs.unsignedp && !num_positive (rhs, precision))
1102         {
1103           /* A negative shift is a positive shift the other way.  */
1104           if (op == CPP_LSHIFT)
1105             op = CPP_RSHIFT;
1106           else
1107             op = CPP_LSHIFT;
1108           rhs = num_negate (rhs, precision);
1109         }
1110       if (rhs.high)
1111         n = ~0;                 /* Maximal.  */
1112       else
1113         n = rhs.low;
1114       if (op == CPP_LSHIFT)
1115         lhs = num_lshift (lhs, precision, n);
1116       else
1117         lhs = num_rshift (lhs, precision, n);
1118       break;
1119
1120       /* Min / Max.  */
1121     case CPP_MIN:
1122     case CPP_MAX:
1123       {
1124         bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1125
1126         gte = num_greater_eq (lhs, rhs, precision);
1127         if (op == CPP_MIN)
1128           gte = !gte;
1129         if (!gte)
1130           lhs = rhs;
1131         lhs.unsignedp = unsignedp;
1132       }
1133       break;
1134
1135       /* Arithmetic.  */
1136     case CPP_MINUS:
1137       rhs = num_negate (rhs, precision);
1138     case CPP_PLUS:
1139       result.low = lhs.low + rhs.low;
1140       result.high = lhs.high + rhs.high;
1141       if (result.low < lhs.low)
1142         result.high++;
1143
1144       result = num_trim (result, precision);
1145       result.unsignedp = lhs.unsignedp || rhs.unsignedp;
1146       if (result.unsignedp)
1147         result.overflow = false;
1148       else
1149         {
1150           bool lhsp = num_positive (lhs, precision);
1151           result.overflow = (lhsp == num_positive (rhs, precision)
1152                              && lhsp != num_positive (result, precision));
1153         }
1154       return result;
1155
1156       /* Comma.  */
1157     default: /* case CPP_COMMA: */
1158       if (CPP_PEDANTIC (pfile))
1159         cpp_error (pfile, DL_PEDWARN,
1160                    "comma operator in operand of #if");
1161       lhs = rhs;
1162       break;
1163     }
1164
1165   return lhs;
1166 }
1167
1168 /* Multiplies two unsigned cpp_num_parts to give a cpp_num.  This
1169    cannot overflow.  */
1170 static cpp_num
1171 num_part_mul (lhs, rhs)
1172      cpp_num_part lhs, rhs;
1173 {
1174   cpp_num result;
1175   cpp_num_part middle[2], temp;
1176
1177   result.low = LOW_PART (lhs) * LOW_PART (rhs);
1178   result.high = HIGH_PART (lhs) * HIGH_PART (rhs);
1179
1180   middle[0] = LOW_PART (lhs) * HIGH_PART (rhs);
1181   middle[1] = HIGH_PART (lhs) * LOW_PART (rhs);
1182
1183   temp = result.low;
1184   result.low += LOW_PART (middle[0]) << (PART_PRECISION / 2);
1185   if (result.low < temp)
1186     result.high++;
1187
1188   temp = result.low;
1189   result.low += LOW_PART (middle[1]) << (PART_PRECISION / 2);
1190   if (result.low < temp)
1191     result.high++;
1192
1193   result.high += HIGH_PART (middle[0]);
1194   result.high += HIGH_PART (middle[1]);
1195
1196   return result;
1197 }
1198
1199 /* Multiply two preprocessing numbers.  */
1200 static cpp_num
1201 num_mul (pfile, lhs, rhs, op)
1202      cpp_reader *pfile;
1203      cpp_num lhs, rhs;
1204      enum cpp_ttype op ATTRIBUTE_UNUSED;
1205 {
1206   cpp_num result, temp;
1207   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1208   bool overflow, negate = false;
1209   size_t precision = CPP_OPTION (pfile, precision);
1210
1211   /* Prepare for unsigned multiplication.  */
1212   if (!unsignedp)
1213     {
1214       if (!num_positive (lhs, precision))
1215         negate = !negate, lhs = num_negate (lhs, precision);
1216       if (!num_positive (rhs, precision))
1217         negate = !negate, rhs = num_negate (rhs, precision);
1218     }
1219
1220   overflow = lhs.high && rhs.high;
1221   result = num_part_mul (lhs.low, rhs.low);
1222
1223   temp = num_part_mul (lhs.high, rhs.low);
1224   result.high += temp.low;
1225   if (temp.high)
1226     overflow = true;
1227
1228   temp = num_part_mul (lhs.low, rhs.high);
1229   result.high += temp.low;
1230   if (temp.high)
1231     overflow = true;
1232
1233   temp.low = result.low, temp.high = result.high;
1234   result = num_trim (result, precision);
1235   if (!num_eq (result, temp))
1236     overflow = true;
1237
1238   if (negate)
1239     result = num_negate (result, precision);
1240
1241   if (unsignedp)
1242     result.overflow = false;
1243   else
1244     result.overflow = overflow || (num_positive (result, precision) ^ !negate
1245                                    && !num_zerop (result));
1246   result.unsignedp = unsignedp;
1247
1248   return result;
1249 }
1250
1251 /* Divide two preprocessing numbers, returning the answer or the
1252    remainder depending upon OP.  */
1253 static cpp_num
1254 num_div_op (pfile, lhs, rhs, op)
1255      cpp_reader *pfile;
1256      cpp_num lhs, rhs;
1257      enum cpp_ttype op;
1258 {
1259   cpp_num result, sub;
1260   cpp_num_part mask;
1261   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1262   bool negate = false, lhs_neg = false;
1263   size_t i, precision = CPP_OPTION (pfile, precision);
1264
1265   /* Prepare for unsigned division.  */
1266   if (!unsignedp)
1267     {
1268       if (!num_positive (lhs, precision))
1269         negate = !negate, lhs_neg = true, lhs = num_negate (lhs, precision);
1270       if (!num_positive (rhs, precision))
1271         negate = !negate, rhs = num_negate (rhs, precision);
1272     }
1273
1274   /* Find the high bit.  */
1275   if (rhs.high)
1276     {
1277       i = precision - 1;
1278       mask = (cpp_num_part) 1 << (i - PART_PRECISION);
1279       for (; ; i--, mask >>= 1)
1280         if (rhs.high & mask)
1281           break;
1282     }
1283   else if (rhs.low)
1284     {
1285       if (precision > PART_PRECISION)
1286         i = precision - PART_PRECISION - 1;
1287       else
1288         i = precision - 1;
1289       mask = (cpp_num_part) 1 << i;
1290       for (; ; i--, mask >>= 1)
1291         if (rhs.low & mask)
1292           break;
1293     }
1294   else
1295     {
1296       cpp_error (pfile, DL_ERROR, "division by zero in #if");
1297       return lhs;
1298     }
1299
1300   /* First non-zero bit of RHS is bit I.  Do naive division by
1301      shifting the RHS fully left, and subtracting from LHS if LHS is
1302      at least as big, and then repeating but with one less shift.
1303      This is not very efficient, but is easy to understand.  */
1304
1305   rhs.unsignedp = true;
1306   lhs.unsignedp = true;
1307   i = precision - i - 1;
1308   sub = num_lshift (rhs, precision, i);
1309
1310   result.high = result.low = 0;
1311   for (;;)
1312     {
1313       if (num_greater_eq (lhs, sub, precision))
1314         {
1315           lhs = num_binary_op (pfile, lhs, sub, CPP_MINUS);
1316           if (i >= PART_PRECISION)
1317             result.high |= (cpp_num_part) 1 << (i - PART_PRECISION);
1318           else
1319             result.low |= (cpp_num_part) 1 << i;
1320         }
1321       if (i-- == 0)
1322         break;
1323       sub.low = (sub.low >> 1) | (sub.high << (PART_PRECISION - 1));
1324       sub.high >>= 1;
1325     }
1326
1327   /* We divide so that the remainder has the sign of the LHS.  */
1328   if (op == CPP_DIV)
1329     {
1330       result.unsignedp = unsignedp;
1331       if (unsignedp)
1332         result.overflow = false;
1333       else
1334         {
1335           if (negate)
1336             result = num_negate (result, precision);
1337           result.overflow = num_positive (result, precision) ^ !negate;
1338         }
1339
1340       return result;
1341     }
1342
1343   /* CPP_MOD.  */
1344   lhs.unsignedp = unsignedp;
1345   lhs.overflow = false;
1346   if (lhs_neg)
1347     lhs = num_negate (lhs, precision);
1348
1349   return lhs;
1350 }