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