libcpp/expr.c

   1 /* Parse C expressions for cpplib.
   2    Copyright (C) 1987, 1992, 1994, 1995, 1997, 1998, 1999, 2000, 2001,
   3    2002, 2004, 2008 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, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "cpplib.h"
  24 #include "internal.h"
  25
  26 #define PART_PRECISION (sizeof (cpp_num_part) * CHAR_BIT)
  27 #define HALF_MASK (~(cpp_num_part) 0 >> (PART_PRECISION / 2))
  28 #define LOW_PART(num_part) (num_part & HALF_MASK)
  29 #define HIGH_PART(num_part) (num_part >> (PART_PRECISION / 2))
  30
  31 struct op
  32 {
  33   const cpp_token *token;       /* The token forming op (for diagnostics).  */
  34   cpp_num value;                /* The value logically "right" of op.  */
  35   enum cpp_ttype op;
  36 };
  37
  38 /* Some simple utility routines on double integers.  */
  39 #define num_zerop(num) ((num.low | num.high) == 0)
  40 #define num_eq(num1, num2) (num1.low == num2.low && num1.high == num2.high)
  41 static bool num_positive (cpp_num, size_t);
  42 static bool num_greater_eq (cpp_num, cpp_num, size_t);
  43 static cpp_num num_trim (cpp_num, size_t);
  44 static cpp_num num_part_mul (cpp_num_part, cpp_num_part);
  45
  46 static cpp_num num_unary_op (cpp_reader *, cpp_num, enum cpp_ttype);
  47 static cpp_num num_binary_op (cpp_reader *, cpp_num, cpp_num, enum cpp_ttype);
  48 static cpp_num num_negate (cpp_num, size_t);
  49 static cpp_num num_bitwise_op (cpp_reader *, cpp_num, cpp_num, enum cpp_ttype);
  50 static cpp_num num_inequality_op (cpp_reader *, cpp_num, cpp_num,
  51                                   enum cpp_ttype);
  52 static cpp_num num_equality_op (cpp_reader *, cpp_num, cpp_num,
  53                                 enum cpp_ttype);
  54 static cpp_num num_mul (cpp_reader *, cpp_num, cpp_num);
  55 static cpp_num num_div_op (cpp_reader *, cpp_num, cpp_num, enum cpp_ttype);
  56 static cpp_num num_lshift (cpp_num, size_t, size_t);
  57 static cpp_num num_rshift (cpp_num, size_t, size_t);
  58
  59 static cpp_num append_digit (cpp_num, int, int, size_t);
  60 static cpp_num parse_defined (cpp_reader *);
  61 static cpp_num eval_token (cpp_reader *, const cpp_token *);
  62 static struct op *reduce (cpp_reader *, struct op *, enum cpp_ttype);
  63 static unsigned int interpret_float_suffix (const uchar *, size_t);
  64 static unsigned int interpret_int_suffix (const uchar *, size_t);
  65 static void check_promotion (cpp_reader *, const struct op *);
  66
  67 /* Token type abuse to create unary plus and minus operators.  */
  68 #define CPP_UPLUS ((enum cpp_ttype) (CPP_LAST_CPP_OP + 1))
  69 #define CPP_UMINUS ((enum cpp_ttype) (CPP_LAST_CPP_OP + 2))
  70
  71 /* With -O2, gcc appears to produce nice code, moving the error
  72    message load and subsequent jump completely out of the main path.  */
  73 #define SYNTAX_ERROR(msgid) \
  74   do { cpp_error (pfile, CPP_DL_ERROR, msgid); goto syntax_error; } while(0)
  75 #define SYNTAX_ERROR2(msgid, arg) \
  76   do { cpp_error (pfile, CPP_DL_ERROR, msgid, arg); goto syntax_error; } \
  77   while(0)
  78
  79 /* Subroutine of cpp_classify_number.  S points to a float suffix of
  80    length LEN, possibly zero.  Returns 0 for an invalid suffix, or a
  81    flag vector describing the suffix.  */
  82 static unsigned int
  83 interpret_float_suffix (const uchar *s, size_t len)
  84 {
  85   size_t f, l, w, q, i, d;
  86   size_t r, k, u, h;
  87
  88   f = l = w = q = i = d = 0;
  89   r = k = u = h = 0;
  90
  91   while (len--)
  92     switch (s[len])
  93       {
  94       case 'r': case 'R': r++; break;
  95       case 'k': case 'K': k++; break;
  96       case 'u': case 'U': u++; break;
  97       case 'h': case 'H': h++; break;
  98       case 'f': case 'F':
  99         if (d > 0)
 100           return 0;
 101         f++;
 102         break;
 103       case 'l': case 'L':
 104         if (d > 0)
 105           return 0;
 106         l++;
 107         /* If there are two Ls, they must be adjacent and the same case.  */
 108         if (l == 2 && s[len] != s[len + 1])
 109           return 0;
 110         break;
 111       case 'w': case 'W':
 112         if (d > 0)
 113           return 0;
 114         w++;
 115         break;
 116       case 'q': case 'Q':
 117         if (d > 0)
 118           return 0;
 119         q++;
 120         break;
 121       case 'i': case 'I':
 122       case 'j': case 'J': i++; break;
 123       case 'd': case 'D': d++; break;
 124       default:
 125         return 0;
 126       }
 127
 128   if (r + k > 1 || h > 1 || l > 2 || u > 1)
 129     return 0;
 130
 131   if (r == 1)
 132     {
 133       if (f || i || d || w || q)
 134         return 0;
 135
 136       return (CPP_N_FRACT
 137               | (u ? CPP_N_UNSIGNED : 0)
 138               | (h ? CPP_N_SMALL :
 139                  l == 2 ? CPP_N_LARGE :
 140                  l == 1 ? CPP_N_MEDIUM :  0));
 141     }
 142
 143   if (k == 1)
 144     {
 145       if (f || i || d || w || q)
 146         return 0;
 147
 148       return (CPP_N_ACCUM
 149               | (u ? CPP_N_UNSIGNED : 0)
 150               | (h ? CPP_N_SMALL :
 151                  l == 2 ? CPP_N_LARGE :
 152                  l == 1 ? CPP_N_MEDIUM :  0));
 153     }
 154
 155   if (f + l + w + q > 1 || i > 1 || h + u > 0)
 156     return 0;
 157
 158   /* Allow dd, df, dl suffixes for decimal float constants.  */
 159   if (d && ((d + f + l != 2) || i))
 160     return 0;
 161
 162   return ((i ? CPP_N_IMAGINARY : 0)
 163           | (f ? CPP_N_SMALL :
 164              l ? CPP_N_LARGE :
 165              w ? CPP_N_MD_W :
 166              q ? CPP_N_MD_Q : CPP_N_MEDIUM)
 167           | (d ? CPP_N_DFLOAT : 0));
 168 }
 169
 170 /* Subroutine of cpp_classify_number.  S points to an integer suffix
 171    of length LEN, possibly zero. Returns 0 for an invalid suffix, or a
 172    flag vector describing the suffix.  */
 173 static unsigned int
 174 interpret_int_suffix (const uchar *s, size_t len)
 175 {
 176   size_t u, l, i;
 177
 178   u = l = i = 0;
 179
 180   while (len--)
 181     switch (s[len])
 182       {
 183       case 'u': case 'U':       u++; break;
 184       case 'i': case 'I':
 185       case 'j': case 'J':       i++; break;
 186       case 'l': case 'L':       l++;
 187         /* If there are two Ls, they must be adjacent and the same case.  */
 188         if (l == 2 && s[len] != s[len + 1])
 189           return 0;
 190         break;
 191       default:
 192         return 0;
 193       }
 194
 195   if (l > 2 || u > 1 || i > 1)
 196     return 0;
 197
 198   return ((i ? CPP_N_IMAGINARY : 0)
 199           | (u ? CPP_N_UNSIGNED : 0)
 200           | ((l == 0) ? CPP_N_SMALL
 201              : (l == 1) ? CPP_N_MEDIUM : CPP_N_LARGE));
 202 }
 203
 204 /* Categorize numeric constants according to their field (integer,
 205    floating point, or invalid), radix (decimal, octal, hexadecimal),
 206    and type suffixes.  */
 207 unsigned int
 208 cpp_classify_number (cpp_reader *pfile, const cpp_token *token)
 209 {
 210   const uchar *str = token->val.str.text;
 211   const uchar *limit;
 212   unsigned int max_digit, result, radix;
 213   enum {NOT_FLOAT = 0, AFTER_POINT, AFTER_EXPON} float_flag;
 214
 215   /* If the lexer has done its job, length one can only be a single
 216      digit.  Fast-path this very common case.  */
 217   if (token->val.str.len == 1)
 218     return CPP_N_INTEGER | CPP_N_SMALL | CPP_N_DECIMAL;
 219
 220   limit = str + token->val.str.len;
 221   float_flag = NOT_FLOAT;
 222   max_digit = 0;
 223   radix = 10;
 224
 225   /* First, interpret the radix.  */
 226   if (*str == '0')
 227     {
 228       radix = 8;
 229       str++;
 230
 231       /* Require at least one hex digit to classify it as hex.  */
 232       if ((*str == 'x' || *str == 'X')
 233           && (str[1] == '.' || ISXDIGIT (str[1])))
 234         {
 235           radix = 16;
 236           str++;
 237         }
 238       else if ((*str == 'b' || *str == 'B') && (str[1] == '0' || str[1] == '1'))
 239         {
 240           radix = 2;
 241           str++;
 242         }
 243     }
 244
 245   /* Now scan for a well-formed integer or float.  */
 246   for (;;)
 247     {
 248       unsigned int c = *str++;
 249
 250       if (ISDIGIT (c) || (ISXDIGIT (c) && radix == 16))
 251         {
 252           c = hex_value (c);
 253           if (c > max_digit)
 254             max_digit = c;
 255         }
 256       else if (c == '.')
 257         {
 258           if (float_flag == NOT_FLOAT)
 259             float_flag = AFTER_POINT;
 260           else
 261             SYNTAX_ERROR ("too many decimal points in number");
 262         }
 263       else if ((radix <= 10 && (c == 'e' || c == 'E'))
 264                || (radix == 16 && (c == 'p' || c == 'P')))
 265         {
 266           float_flag = AFTER_EXPON;
 267           break;
 268         }
 269       else
 270         {
 271           /* Start of suffix.  */
 272           str--;
 273           break;
 274         }
 275     }
 276
 277   /* The suffix may be for decimal fixed-point constants without exponent.  */
 278   if (radix != 16 && float_flag == NOT_FLOAT)
 279     {
 280       result = interpret_float_suffix (str, limit - str);
 281       if ((result & CPP_N_FRACT) || (result & CPP_N_ACCUM))
 282         {
 283           result |= CPP_N_FLOATING;
 284           /* We need to restore the radix to 10, if the radix is 8.  */
 285           if (radix == 8)
 286             radix = 10;
 287
 288           if (CPP_PEDANTIC (pfile))
 289             cpp_error (pfile, CPP_DL_PEDWARN,
 290                        "fixed-point constants are a GCC extension");
 291           goto syntax_ok;
 292         }
 293       else
 294         result = 0;
 295     }
 296
 297   if (float_flag != NOT_FLOAT && radix == 8)
 298     radix = 10;
 299
 300   if (max_digit >= radix)
 301     {
 302       if (radix == 2)
 303         SYNTAX_ERROR2 ("invalid digit \"%c\" in binary constant", '0' + max_digit);
 304       else
 305         SYNTAX_ERROR2 ("invalid digit \"%c\" in octal constant", '0' + max_digit);
 306     }
 307
 308   if (float_flag != NOT_FLOAT)
 309     {
 310       if (radix == 2)
 311         {
 312           cpp_error (pfile, CPP_DL_ERROR,
 313                      "invalid prefix \"0b\" for floating constant");
 314           return CPP_N_INVALID;
 315         }
 316
 317       if (radix == 16 && CPP_PEDANTIC (pfile) && !CPP_OPTION (pfile, c99))
 318         cpp_error (pfile, CPP_DL_PEDWARN,
 319                    "use of C99 hexadecimal floating constant");
 320
 321       if (float_flag == AFTER_EXPON)
 322         {
 323           if (*str == '+' || *str == '-')
 324             str++;
 325
 326           /* Exponent is decimal, even if string is a hex float.  */
 327           if (!ISDIGIT (*str))
 328             SYNTAX_ERROR ("exponent has no digits");
 329
 330           do
 331             str++;
 332           while (ISDIGIT (*str));
 333         }
 334       else if (radix == 16)
 335         SYNTAX_ERROR ("hexadecimal floating constants require an exponent");
 336
 337       result = interpret_float_suffix (str, limit - str);
 338       if (result == 0)
 339         {
 340           cpp_error (pfile, CPP_DL_ERROR,
 341                      "invalid suffix \"%.*s\" on floating constant",
 342                      (int) (limit - str), str);
 343           return CPP_N_INVALID;
 344         }
 345
 346       /* Traditional C didn't accept any floating suffixes.  */
 347       if (limit != str
 348           && CPP_WTRADITIONAL (pfile)
 349           && ! cpp_sys_macro_p (pfile))
 350         cpp_error (pfile, CPP_DL_WARNING,
 351                    "traditional C rejects the \"%.*s\" suffix",
 352                    (int) (limit - str), str);
 353
 354       /* Radix must be 10 for decimal floats.  */
 355       if ((result & CPP_N_DFLOAT) && radix != 10)
 356         {
 357           cpp_error (pfile, CPP_DL_ERROR,
 358                      "invalid suffix \"%.*s\" with hexadecimal floating constant",
 359                      (int) (limit - str), str);
 360           return CPP_N_INVALID;
 361         }
 362
 363       if ((result & (CPP_N_FRACT | CPP_N_ACCUM)) && CPP_PEDANTIC (pfile))
 364         cpp_error (pfile, CPP_DL_PEDWARN,
 365                    "fixed-point constants are a GCC extension");
 366
 367       if ((result & CPP_N_DFLOAT) && CPP_PEDANTIC (pfile))
 368         cpp_error (pfile, CPP_DL_PEDWARN,
 369                    "decimal float constants are a GCC extension");
 370
 371       result |= CPP_N_FLOATING;
 372     }
 373   else
 374     {
 375       result = interpret_int_suffix (str, limit - str);
 376       if (result == 0)
 377         {
 378           cpp_error (pfile, CPP_DL_ERROR,
 379                      "invalid suffix \"%.*s\" on integer constant",
 380                      (int) (limit - str), str);
 381           return CPP_N_INVALID;
 382         }
 383
 384       /* Traditional C only accepted the 'L' suffix.
 385          Suppress warning about 'LL' with -Wno-long-long.  */
 386       if (CPP_WTRADITIONAL (pfile) && ! cpp_sys_macro_p (pfile))
 387         {
 388           int u_or_i = (result & (CPP_N_UNSIGNED|CPP_N_IMAGINARY));
 389           int large = (result & CPP_N_WIDTH) == CPP_N_LARGE;
 390
 391           if (u_or_i || (large && CPP_OPTION (pfile, warn_long_long)))
 392             cpp_error (pfile, CPP_DL_WARNING,
 393                        "traditional C rejects the \"%.*s\" suffix",
 394                        (int) (limit - str), str);
 395         }
 396
 397       if ((result & CPP_N_WIDTH) == CPP_N_LARGE
 398           && ! CPP_OPTION (pfile, c99)
 399           && CPP_OPTION (pfile, warn_long_long))
 400         cpp_error (pfile, CPP_DL_PEDWARN,
 401                    "use of C99 long long integer constant");
 402
 403       result |= CPP_N_INTEGER;
 404     }
 405
 406  syntax_ok:
 407   if ((result & CPP_N_IMAGINARY) && CPP_PEDANTIC (pfile))
 408     cpp_error (pfile, CPP_DL_PEDWARN,
 409                "imaginary constants are a GCC extension");
 410   if (radix == 2 && CPP_PEDANTIC (pfile))
 411     cpp_error (pfile, CPP_DL_PEDWARN,
 412                "binary constants are a GCC extension");
 413
 414   if (radix == 10)
 415     result |= CPP_N_DECIMAL;
 416   else if (radix == 16)
 417     result |= CPP_N_HEX;
 418   else if (radix == 2)
 419     result |= CPP_N_BINARY;
 420   else
 421     result |= CPP_N_OCTAL;
 422
 423   return result;
 424
 425  syntax_error:
 426   return CPP_N_INVALID;
 427 }
 428
 429 /* cpp_interpret_integer converts an integer constant into a cpp_num,
 430    of precision options->precision.
 431
 432    We do not provide any interface for decimal->float conversion,
 433    because the preprocessor doesn't need it and we don't want to
 434    drag in GCC's floating point emulator.  */
 435 cpp_num
 436 cpp_interpret_integer (cpp_reader *pfile, const cpp_token *token,
 437                        unsigned int type)
 438 {
 439   const uchar *p, *end;
 440   cpp_num result;
 441
 442   result.low = 0;
 443   result.high = 0;
 444   result.unsignedp = !!(type & CPP_N_UNSIGNED);
 445   result.overflow = false;
 446
 447   p = token->val.str.text;
 448   end = p + token->val.str.len;
 449
 450   /* Common case of a single digit.  */
 451   if (token->val.str.len == 1)
 452     result.low = p[0] - '0';
 453   else
 454     {
 455       cpp_num_part max;
 456       size_t precision = CPP_OPTION (pfile, precision);
 457       unsigned int base = 10, c = 0;
 458       bool overflow = false;
 459
 460       if ((type & CPP_N_RADIX) == CPP_N_OCTAL)
 461         {
 462           base = 8;
 463           p++;
 464         }
 465       else if ((type & CPP_N_RADIX) == CPP_N_HEX)
 466         {
 467           base = 16;
 468           p += 2;
 469         }
 470       else if ((type & CPP_N_RADIX) == CPP_N_BINARY)
 471         {
 472           base = 2;
 473           p += 2;
 474         }
 475
 476       /* We can add a digit to numbers strictly less than this without
 477          needing the precision and slowness of double integers.  */
 478       max = ~(cpp_num_part) 0;
 479       if (precision < PART_PRECISION)
 480         max >>= PART_PRECISION - precision;
 481       max = (max - base + 1) / base + 1;
 482
 483       for (; p < end; p++)
 484         {
 485           c = *p;
 486
 487           if (ISDIGIT (c) || (base == 16 && ISXDIGIT (c)))
 488             c = hex_value (c);
 489           else
 490             break;
 491
 492           /* Strict inequality for when max is set to zero.  */
 493           if (result.low < max)
 494             result.low = result.low * base + c;
 495           else
 496             {
 497               result = append_digit (result, c, base, precision);
 498               overflow |= result.overflow;
 499               max = 0;
 500             }
 501         }
 502
 503       if (overflow)
 504         cpp_error (pfile, CPP_DL_PEDWARN,
 505                    "integer constant is too large for its type");
 506       /* If too big to be signed, consider it unsigned.  Only warn for
 507          decimal numbers.  Traditional numbers were always signed (but
 508          we still honor an explicit U suffix); but we only have
 509          traditional semantics in directives.  */
 510       else if (!result.unsignedp
 511                && !(CPP_OPTION (pfile, traditional)
 512                     && pfile->state.in_directive)
 513                && !num_positive (result, precision))
 514         {
 515           if (base == 10)
 516             cpp_error (pfile, CPP_DL_WARNING,
 517                        "integer constant is so large that it is unsigned");
 518           result.unsignedp = true;
 519         }
 520     }
 521
 522   return result;
 523 }
 524
 525 /* Append DIGIT to NUM, a number of PRECISION bits being read in base BASE.  */
 526 static cpp_num
 527 append_digit (cpp_num num, int digit, int base, size_t precision)
 528 {
 529   cpp_num result;
 530   unsigned int shift;
 531   bool overflow;
 532   cpp_num_part add_high, add_low;
 533
 534   /* Multiply by 2, 8 or 16.  Catching this overflow here means we don't
 535      need to worry about add_high overflowing.  */
 536   switch (base)
 537     {
 538     case 2:
 539       shift = 1;
 540       break;
 541
 542     case 16:
 543       shift = 4;
 544       break;
 545
 546     default:
 547       shift = 3;
 548     }
 549   overflow = !!(num.high >> (PART_PRECISION - shift));
 550   result.high = num.high << shift;
 551   result.low = num.low << shift;
 552   result.high |= num.low >> (PART_PRECISION - shift);
 553   result.unsignedp = num.unsignedp;
 554
 555   if (base == 10)
 556     {
 557       add_low = num.low << 1;
 558       add_high = (num.high << 1) + (num.low >> (PART_PRECISION - 1));
 559     }
 560   else
 561     add_high = add_low = 0;
 562
 563   if (add_low + digit < add_low)
 564     add_high++;
 565   add_low += digit;
 566
 567   if (result.low + add_low < result.low)
 568     add_high++;
 569   if (result.high + add_high < result.high)
 570     overflow = true;
 571
 572   result.low += add_low;
 573   result.high += add_high;
 574   result.overflow = overflow;
 575
 576   /* The above code catches overflow of a cpp_num type.  This catches
 577      overflow of the (possibly shorter) target precision.  */
 578   num.low = result.low;
 579   num.high = result.high;
 580   result = num_trim (result, precision);
 581   if (!num_eq (result, num))
 582     result.overflow = true;
 583
 584   return result;
 585 }
 586
 587 /* Handle meeting "defined" in a preprocessor expression.  */
 588 static cpp_num
 589 parse_defined (cpp_reader *pfile)
 590 {
 591   cpp_num result;
 592   int paren = 0;
 593   cpp_hashnode *node = 0;
 594   const cpp_token *token;
 595   cpp_context *initial_context = pfile->context;
 596
 597   /* Don't expand macros.  */
 598   pfile->state.prevent_expansion++;
 599
 600   token = cpp_get_token (pfile);
 601   if (token->type == CPP_OPEN_PAREN)
 602     {
 603       paren = 1;
 604       token = cpp_get_token (pfile);
 605     }
 606
 607   if (token->type == CPP_NAME)
 608     {
 609       node = token->val.node;
 610       if (paren && cpp_get_token (pfile)->type != CPP_CLOSE_PAREN)
 611         {
 612           cpp_error (pfile, CPP_DL_ERROR, "missing ')' after \"defined\"");
 613           node = 0;
 614         }
 615     }
 616   else
 617     {
 618       cpp_error (pfile, CPP_DL_ERROR,
 619                  "operator \"defined\" requires an identifier");
 620       if (token->flags & NAMED_OP)
 621         {
 622           cpp_token op;
 623
 624           op.flags = 0;
 625           op.type = token->type;
 626           cpp_error (pfile, CPP_DL_ERROR,
 627                      "(\"%s\" is an alternative token for \"%s\" in C++)",
 628                      cpp_token_as_text (pfile, token),
 629                      cpp_token_as_text (pfile, &op));
 630         }
 631     }
 632
 633   if (node)
 634     {
 635       if (pfile->context != initial_context && CPP_PEDANTIC (pfile))
 636         cpp_error (pfile, CPP_DL_WARNING,
 637                    "this use of \"defined\" may not be portable");
 638
 639       _cpp_mark_macro_used (node);
 640       if (!(node->flags & NODE_USED))
 641         {
 642           node->flags |= NODE_USED;
 643           if (node->type == NT_MACRO)
 644             {
 645               if (pfile->cb.used_define)
 646                 pfile->cb.used_define (pfile, pfile->directive_line, node);
 647             }
 648           else
 649             {
 650               if (pfile->cb.used_undef)
 651                 pfile->cb.used_undef (pfile, pfile->directive_line, node);
 652             }
 653         }
 654
 655       /* A possible controlling macro of the form #if !defined ().
 656          _cpp_parse_expr checks there was no other junk on the line.  */
 657       pfile->mi_ind_cmacro = node;
 658     }
 659
 660   pfile->state.prevent_expansion--;
 661
 662   result.unsignedp = false;
 663   result.high = 0;
 664   result.overflow = false;
 665   result.low = node && node->type == NT_MACRO;
 666   return result;
 667 }
 668
 669 /* Convert a token into a CPP_NUMBER (an interpreted preprocessing
 670    number or character constant, or the result of the "defined" or "#"
 671    operators).  */
 672 static cpp_num
 673 eval_token (cpp_reader *pfile, const cpp_token *token)
 674 {
 675   cpp_num result;
 676   unsigned int temp;
 677   int unsignedp = 0;
 678
 679   result.unsignedp = false;
 680   result.overflow = false;
 681
 682   switch (token->type)
 683     {
 684     case CPP_NUMBER:
 685       temp = cpp_classify_number (pfile, token);
 686       switch (temp & CPP_N_CATEGORY)
 687         {
 688         case CPP_N_FLOATING:
 689           cpp_error (pfile, CPP_DL_ERROR,
 690                      "floating constant in preprocessor expression");
 691           break;
 692         case CPP_N_INTEGER:
 693           if (!(temp & CPP_N_IMAGINARY))
 694             return cpp_interpret_integer (pfile, token, temp);
 695           cpp_error (pfile, CPP_DL_ERROR,
 696                      "imaginary number in preprocessor expression");
 697           break;
 698
 699         case CPP_N_INVALID:
 700           /* Error already issued.  */
 701           break;
 702         }
 703       result.high = result.low = 0;
 704       break;
 705
 706     case CPP_WCHAR:
 707     case CPP_CHAR:
 708     case CPP_CHAR16:
 709     case CPP_CHAR32:
 710       {
 711         cppchar_t cc = cpp_interpret_charconst (pfile, token,
 712                                                 &temp, &unsignedp);
 713
 714         result.high = 0;
 715         result.low = cc;
 716         /* Sign-extend the result if necessary.  */
 717         if (!unsignedp && (cppchar_signed_t) cc < 0)
 718           {
 719             if (PART_PRECISION > BITS_PER_CPPCHAR_T)
 720               result.low |= ~(~(cpp_num_part) 0
 721                               >> (PART_PRECISION - BITS_PER_CPPCHAR_T));
 722             result.high = ~(cpp_num_part) 0;
 723             result = num_trim (result, CPP_OPTION (pfile, precision));
 724           }
 725       }
 726       break;
 727
 728     case CPP_NAME:
 729       if (token->val.node == pfile->spec_nodes.n_defined)
 730         return parse_defined (pfile);
 731       else if (CPP_OPTION (pfile, cplusplus)
 732                && (token->val.node == pfile->spec_nodes.n_true
 733                    || token->val.node == pfile->spec_nodes.n_false))
 734         {
 735           result.high = 0;
 736           result.low = (token->val.node == pfile->spec_nodes.n_true);
 737         }
 738       else
 739         {
 740           result.high = 0;
 741           result.low = 0;
 742           if (CPP_OPTION (pfile, warn_undef) && !pfile->state.skip_eval)
 743             cpp_error (pfile, CPP_DL_WARNING, "\"%s\" is not defined",
 744                        NODE_NAME (token->val.node));
 745         }
 746       break;
 747
 748     case CPP_HASH:
 749       if (!pfile->state.skipping)
 750         {
 751           /* A pedantic warning takes precedence over a deprecated
 752              warning here.  */
 753           if (CPP_PEDANTIC (pfile))
 754             cpp_error (pfile, CPP_DL_PEDWARN,
 755                        "assertions are a GCC extension");
 756           else if (CPP_OPTION (pfile, warn_deprecated))
 757             cpp_error (pfile, CPP_DL_WARNING,
 758                        "assertions are a deprecated extension");
 759         }
 760       _cpp_test_assertion (pfile, &temp);
 761       result.high = 0;
 762       result.low = temp;
 763       break;
 764
 765     default:
 766       abort ();
 767     }
 768
 769   result.unsignedp = !!unsignedp;
 770   return result;
 771 }
 772 \f
 773 /* Operator precedence and flags table.
 774
 775 After an operator is returned from the lexer, if it has priority less
 776 than the operator on the top of the stack, we reduce the stack by one
 777 operator and repeat the test.  Since equal priorities do not reduce,
 778 this is naturally right-associative.
 779
 780 We handle left-associative operators by decrementing the priority of
 781 just-lexed operators by one, but retaining the priority of operators
 782 already on the stack.
 783
 784 The remaining cases are '(' and ')'.  We handle '(' by skipping the
 785 reduction phase completely.  ')' is given lower priority than
 786 everything else, including '(', effectively forcing a reduction of the
 787 parenthesized expression.  If there is a matching '(', the routine
 788 reduce() exits immediately.  If the normal exit route sees a ')', then
 789 there cannot have been a matching '(' and an error message is output.
 790
 791 The parser assumes all shifted operators require a left operand unless
 792 the flag NO_L_OPERAND is set.  These semantics are automatic; any
 793 extra semantics need to be handled with operator-specific code.  */
 794
 795 /* Flags.  If CHECK_PROMOTION, we warn if the effective sign of an
 796    operand changes because of integer promotions.  */
 797 #define NO_L_OPERAND    (1 << 0)
 798 #define LEFT_ASSOC      (1 << 1)
 799 #define CHECK_PROMOTION (1 << 2)
 800
 801 /* Operator to priority map.  Must be in the same order as the first
 802    N entries of enum cpp_ttype.  */
 803 static const struct cpp_operator
 804 {
 805   uchar prio;
 806   uchar flags;
 807 } optab[] =
 808 {
 809   /* EQ */              {0, 0}, /* Shouldn't happen.  */
 810   /* NOT */             {16, NO_L_OPERAND},
 811   /* GREATER */         {12, LEFT_ASSOC | CHECK_PROMOTION},
 812   /* LESS */            {12, LEFT_ASSOC | CHECK_PROMOTION},
 813   /* PLUS */            {14, LEFT_ASSOC | CHECK_PROMOTION},
 814   /* MINUS */           {14, LEFT_ASSOC | CHECK_PROMOTION},
 815   /* MULT */            {15, LEFT_ASSOC | CHECK_PROMOTION},
 816   /* DIV */             {15, LEFT_ASSOC | CHECK_PROMOTION},
 817   /* MOD */             {15, LEFT_ASSOC | CHECK_PROMOTION},
 818   /* AND */             {9, LEFT_ASSOC | CHECK_PROMOTION},
 819   /* OR */              {7, LEFT_ASSOC | CHECK_PROMOTION},
 820   /* XOR */             {8, LEFT_ASSOC | CHECK_PROMOTION},
 821   /* RSHIFT */          {13, LEFT_ASSOC},
 822   /* LSHIFT */          {13, LEFT_ASSOC},
 823
 824   /* COMPL */           {16, NO_L_OPERAND},
 825   /* AND_AND */         {6, LEFT_ASSOC},
 826   /* OR_OR */           {5, LEFT_ASSOC},
 827   /* Note that QUERY, COLON, and COMMA must have the same precedence.
 828      However, there are some special cases for these in reduce().  */
 829   /* QUERY */           {4, 0},
 830   /* COLON */           {4, LEFT_ASSOC | CHECK_PROMOTION},
 831   /* COMMA */           {4, LEFT_ASSOC},
 832   /* OPEN_PAREN */      {1, NO_L_OPERAND},
 833   /* CLOSE_PAREN */     {0, 0},
 834   /* EOF */             {0, 0},
 835   /* EQ_EQ */           {11, LEFT_ASSOC},
 836   /* NOT_EQ */          {11, LEFT_ASSOC},
 837   /* GREATER_EQ */      {12, LEFT_ASSOC | CHECK_PROMOTION},
 838   /* LESS_EQ */         {12, LEFT_ASSOC | CHECK_PROMOTION},
 839   /* UPLUS */           {16, NO_L_OPERAND},
 840   /* UMINUS */          {16, NO_L_OPERAND}
 841 };
 842
 843 /* Parse and evaluate a C expression, reading from PFILE.
 844    Returns the truth value of the expression.
 845
 846    The implementation is an operator precedence parser, i.e. a
 847    bottom-up parser, using a stack for not-yet-reduced tokens.
 848
 849    The stack base is op_stack, and the current stack pointer is 'top'.
 850    There is a stack element for each operator (only), and the most
 851    recently pushed operator is 'top->op'.  An operand (value) is
 852    stored in the 'value' field of the stack element of the operator
 853    that precedes it.  */
 854 bool
 855 _cpp_parse_expr (cpp_reader *pfile)
 856 {
 857   struct op *top = pfile->op_stack;
 858   unsigned int lex_count;
 859   bool saw_leading_not, want_value = true;
 860
 861   pfile->state.skip_eval = 0;
 862
 863   /* Set up detection of #if ! defined().  */
 864   pfile->mi_ind_cmacro = 0;
 865   saw_leading_not = false;
 866   lex_count = 0;
 867
 868   /* Lowest priority operator prevents further reductions.  */
 869   top->op = CPP_EOF;
 870
 871   for (;;)
 872     {
 873       struct op op;
 874
 875       lex_count++;
 876       op.token = cpp_get_token (pfile);
 877       op.op = op.token->type;
 878
 879       switch (op.op)
 880         {
 881           /* These tokens convert into values.  */
 882         case CPP_NUMBER:
 883         case CPP_CHAR:
 884         case CPP_WCHAR:
 885         case CPP_CHAR16:
 886         case CPP_CHAR32:
 887         case CPP_NAME:
 888         case CPP_HASH:
 889           if (!want_value)
 890             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
 891                            cpp_token_as_text (pfile, op.token));
 892           want_value = false;
 893           top->value = eval_token (pfile, op.token);
 894           continue;
 895
 896         case CPP_NOT:
 897           saw_leading_not = lex_count == 1;
 898           break;
 899         case CPP_PLUS:
 900           if (want_value)
 901             op.op = CPP_UPLUS;
 902           break;
 903         case CPP_MINUS:
 904           if (want_value)
 905             op.op = CPP_UMINUS;
 906           break;
 907
 908         default:
 909           if ((int) op.op <= (int) CPP_EQ || (int) op.op >= (int) CPP_PLUS_EQ)
 910             SYNTAX_ERROR2 ("token \"%s\" is not valid in preprocessor expressions",
 911                            cpp_token_as_text (pfile, op.token));
 912           break;
 913         }
 914
 915       /* Check we have a value or operator as appropriate.  */
 916       if (optab[op.op].flags & NO_L_OPERAND)
 917         {
 918           if (!want_value)
 919             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
 920                            cpp_token_as_text (pfile, op.token));
 921         }
 922       else if (want_value)
 923         {
 924           /* We want a number (or expression) and haven't got one.
 925              Try to emit a specific diagnostic.  */
 926           if (op.op == CPP_CLOSE_PAREN && top->op == CPP_OPEN_PAREN)
 927             SYNTAX_ERROR ("missing expression between '(' and ')'");
 928
 929           if (op.op == CPP_EOF && top->op == CPP_EOF)
 930             SYNTAX_ERROR ("#if with no expression");
 931
 932           if (top->op != CPP_EOF && top->op != CPP_OPEN_PAREN)
 933             SYNTAX_ERROR2 ("operator '%s' has no right operand",
 934                            cpp_token_as_text (pfile, top->token));
 935           else if (op.op == CPP_CLOSE_PAREN || op.op == CPP_EOF)
 936             /* Complain about missing paren during reduction.  */;
 937           else
 938             SYNTAX_ERROR2 ("operator '%s' has no left operand",
 939                            cpp_token_as_text (pfile, op.token));
 940         }
 941
 942       top = reduce (pfile, top, op.op);
 943       if (!top)
 944         goto syntax_error;
 945
 946       if (op.op == CPP_EOF)
 947         break;
 948
 949       switch (op.op)
 950         {
 951         case CPP_CLOSE_PAREN:
 952           continue;
 953         case CPP_OR_OR:
 954           if (!num_zerop (top->value))
 955             pfile->state.skip_eval++;
 956           break;
 957         case CPP_AND_AND:
 958         case CPP_QUERY:
 959           if (num_zerop (top->value))
 960             pfile->state.skip_eval++;
 961           break;
 962         case CPP_COLON:
 963           if (top->op != CPP_QUERY)
 964             SYNTAX_ERROR (" ':' without preceding '?'");
 965           if (!num_zerop (top[-1].value)) /* Was '?' condition true?  */
 966             pfile->state.skip_eval++;
 967           else
 968             pfile->state.skip_eval--;
 969         default:
 970           break;
 971         }
 972
 973       want_value = true;
 974
 975       /* Check for and handle stack overflow.  */
 976       if (++top == pfile->op_limit)
 977         top = _cpp_expand_op_stack (pfile);
 978
 979       top->op = op.op;
 980       top->token = op.token;
 981     }
 982
 983   /* The controlling macro expression is only valid if we called lex 3
 984      times: <!> <defined expression> and <EOF>.  push_conditional ()
 985      checks that we are at top-of-file.  */
 986   if (pfile->mi_ind_cmacro && !(saw_leading_not && lex_count == 3))
 987     pfile->mi_ind_cmacro = 0;
 988
 989   if (top != pfile->op_stack)
 990     {
 991       cpp_error (pfile, CPP_DL_ICE, "unbalanced stack in #if");
 992     syntax_error:
 993       return false;  /* Return false on syntax error.  */
 994     }
 995
 996   return !num_zerop (top->value);
 997 }
 998
 999 /* Reduce the operator / value stack if possible, in preparation for
1000    pushing operator OP.  Returns NULL on error, otherwise the top of
1001    the stack.  */
1002 static struct op *
1003 reduce (cpp_reader *pfile, struct op *top, enum cpp_ttype op)
1004 {
1005   unsigned int prio;
1006
1007   if (top->op <= CPP_EQ || top->op > CPP_LAST_CPP_OP + 2)
1008     {
1009     bad_op:
1010       cpp_error (pfile, CPP_DL_ICE, "impossible operator '%u'", top->op);
1011       return 0;
1012     }
1013
1014   if (op == CPP_OPEN_PAREN)
1015     return top;
1016
1017   /* Decrement the priority of left-associative operators to force a
1018      reduction with operators of otherwise equal priority.  */
1019   prio = optab[op].prio - ((optab[op].flags & LEFT_ASSOC) != 0);
1020   while (prio < optab[top->op].prio)
1021     {
1022       if (CPP_OPTION (pfile, warn_num_sign_change)
1023           && optab[top->op].flags & CHECK_PROMOTION)
1024         check_promotion (pfile, top);
1025
1026       switch (top->op)
1027         {
1028         case CPP_UPLUS:
1029         case CPP_UMINUS:
1030         case CPP_NOT:
1031         case CPP_COMPL:
1032           top[-1].value = num_unary_op (pfile, top->value, top->op);
1033           break;
1034
1035         case CPP_PLUS:
1036         case CPP_MINUS:
1037         case CPP_RSHIFT:
1038         case CPP_LSHIFT:
1039         case CPP_COMMA:
1040           top[-1].value = num_binary_op (pfile, top[-1].value,
1041                                          top->value, top->op);
1042           break;
1043
1044         case CPP_GREATER:
1045         case CPP_LESS:
1046         case CPP_GREATER_EQ:
1047         case CPP_LESS_EQ:
1048           top[-1].value
1049             = num_inequality_op (pfile, top[-1].value, top->value, top->op);
1050           break;
1051
1052         case CPP_EQ_EQ:
1053         case CPP_NOT_EQ:
1054           top[-1].value
1055             = num_equality_op (pfile, top[-1].value, top->value, top->op);
1056           break;
1057
1058         case CPP_AND:
1059         case CPP_OR:
1060         case CPP_XOR:
1061           top[-1].value
1062             = num_bitwise_op (pfile, top[-1].value, top->value, top->op);
1063           break;
1064
1065         case CPP_MULT:
1066           top[-1].value = num_mul (pfile, top[-1].value, top->value);
1067           break;
1068
1069         case CPP_DIV:
1070         case CPP_MOD:
1071           top[-1].value = num_div_op (pfile, top[-1].value,
1072                                       top->value, top->op);
1073           break;
1074
1075         case CPP_OR_OR:
1076           top--;
1077           if (!num_zerop (top->value))
1078             pfile->state.skip_eval--;
1079           top->value.low = (!num_zerop (top->value)
1080                             || !num_zerop (top[1].value));
1081           top->value.high = 0;
1082           top->value.unsignedp = false;
1083           top->value.overflow = false;
1084           continue;
1085
1086         case CPP_AND_AND:
1087           top--;
1088           if (num_zerop (top->value))
1089             pfile->state.skip_eval--;
1090           top->value.low = (!num_zerop (top->value)
1091                             && !num_zerop (top[1].value));
1092           top->value.high = 0;
1093           top->value.unsignedp = false;
1094           top->value.overflow = false;
1095           continue;
1096
1097         case CPP_OPEN_PAREN:
1098           if (op != CPP_CLOSE_PAREN)
1099             {
1100               cpp_error (pfile, CPP_DL_ERROR, "missing ')' in expression");
1101               return 0;
1102             }
1103           top--;
1104           top->value = top[1].value;
1105           return top;
1106
1107         case CPP_COLON:
1108           top -= 2;
1109           if (!num_zerop (top->value))
1110             {
1111               pfile->state.skip_eval--;
1112               top->value = top[1].value;
1113             }
1114           else
1115             top->value = top[2].value;
1116           top->value.unsignedp = (top[1].value.unsignedp
1117                                   || top[2].value.unsignedp);
1118           continue;
1119
1120         case CPP_QUERY:
1121           /* COMMA and COLON should not reduce a QUERY operator.  */
1122           if (op == CPP_COMMA || op == CPP_COLON)
1123             return top;
1124           cpp_error (pfile, CPP_DL_ERROR, "'?' without following ':'");
1125           return 0;
1126
1127         default:
1128           goto bad_op;
1129         }
1130
1131       top--;
1132       if (top->value.overflow && !pfile->state.skip_eval)
1133         cpp_error (pfile, CPP_DL_PEDWARN,
1134                    "integer overflow in preprocessor expression");
1135     }
1136
1137   if (op == CPP_CLOSE_PAREN)
1138     {
1139       cpp_error (pfile, CPP_DL_ERROR, "missing '(' in expression");
1140       return 0;
1141     }
1142
1143   return top;
1144 }
1145
1146 /* Returns the position of the old top of stack after expansion.  */
1147 struct op *
1148 _cpp_expand_op_stack (cpp_reader *pfile)
1149 {
1150   size_t old_size = (size_t) (pfile->op_limit - pfile->op_stack);
1151   size_t new_size = old_size * 2 + 20;
1152
1153   pfile->op_stack = XRESIZEVEC (struct op, pfile->op_stack, new_size);
1154   pfile->op_limit = pfile->op_stack + new_size;
1155
1156   return pfile->op_stack + old_size;
1157 }
1158
1159 /* Emits a warning if the effective sign of either operand of OP
1160    changes because of integer promotions.  */
1161 static void
1162 check_promotion (cpp_reader *pfile, const struct op *op)
1163 {
1164   if (op->value.unsignedp == op[-1].value.unsignedp)
1165     return;
1166
1167   if (op->value.unsignedp)
1168     {
1169       if (!num_positive (op[-1].value, CPP_OPTION (pfile, precision)))
1170         cpp_error (pfile, CPP_DL_WARNING,
1171                    "the left operand of \"%s\" changes sign when promoted",
1172                    cpp_token_as_text (pfile, op->token));
1173     }
1174   else if (!num_positive (op->value, CPP_OPTION (pfile, precision)))
1175     cpp_error (pfile, CPP_DL_WARNING,
1176                "the right operand of \"%s\" changes sign when promoted",
1177                cpp_token_as_text (pfile, op->token));
1178 }
1179
1180 /* Clears the unused high order bits of the number pointed to by PNUM.  */
1181 static cpp_num
1182 num_trim (cpp_num num, size_t precision)
1183 {
1184   if (precision > PART_PRECISION)
1185     {
1186       precision -= PART_PRECISION;
1187       if (precision < PART_PRECISION)
1188         num.high &= ((cpp_num_part) 1 << precision) - 1;
1189     }
1190   else
1191     {
1192       if (precision < PART_PRECISION)
1193         num.low &= ((cpp_num_part) 1 << precision) - 1;
1194       num.high = 0;
1195     }
1196
1197   return num;
1198 }
1199
1200 /* True iff A (presumed signed) >= 0.  */
1201 static bool
1202 num_positive (cpp_num num, size_t precision)
1203 {
1204   if (precision > PART_PRECISION)
1205     {
1206       precision -= PART_PRECISION;
1207       return (num.high & (cpp_num_part) 1 << (precision - 1)) == 0;
1208     }
1209
1210   return (num.low & (cpp_num_part) 1 << (precision - 1)) == 0;
1211 }
1212
1213 /* Sign extend a number, with PRECISION significant bits and all
1214    others assumed clear, to fill out a cpp_num structure.  */
1215 cpp_num
1216 cpp_num_sign_extend (cpp_num num, size_t precision)
1217 {
1218   if (!num.unsignedp)
1219     {
1220       if (precision > PART_PRECISION)
1221         {
1222           precision -= PART_PRECISION;
1223           if (precision < PART_PRECISION
1224               && (num.high & (cpp_num_part) 1 << (precision - 1)))
1225             num.high |= ~(~(cpp_num_part) 0 >> (PART_PRECISION - precision));
1226         }
1227       else if (num.low & (cpp_num_part) 1 << (precision - 1))
1228         {
1229           if (precision < PART_PRECISION)
1230             num.low |= ~(~(cpp_num_part) 0 >> (PART_PRECISION - precision));
1231           num.high = ~(cpp_num_part) 0;
1232         }
1233     }
1234
1235   return num;
1236 }
1237
1238 /* Returns the negative of NUM.  */
1239 static cpp_num
1240 num_negate (cpp_num num, size_t precision)
1241 {
1242   cpp_num copy;
1243
1244   copy = num;
1245   num.high = ~num.high;
1246   num.low = ~num.low;
1247   if (++num.low == 0)
1248     num.high++;
1249   num = num_trim (num, precision);
1250   num.overflow = (!num.unsignedp && num_eq (num, copy) && !num_zerop (num));
1251
1252   return num;
1253 }
1254
1255 /* Returns true if A >= B.  */
1256 static bool
1257 num_greater_eq (cpp_num pa, cpp_num pb, size_t precision)
1258 {
1259   bool unsignedp;
1260
1261   unsignedp = pa.unsignedp || pb.unsignedp;
1262
1263   if (!unsignedp)
1264     {
1265       /* Both numbers have signed type.  If they are of different
1266        sign, the answer is the sign of A.  */
1267       unsignedp = num_positive (pa, precision);
1268
1269       if (unsignedp != num_positive (pb, precision))
1270         return unsignedp;
1271
1272       /* Otherwise we can do an unsigned comparison.  */
1273     }
1274
1275   return (pa.high > pb.high) || (pa.high == pb.high && pa.low >= pb.low);
1276 }
1277
1278 /* Returns LHS OP RHS, where OP is a bit-wise operation.  */
1279 static cpp_num
1280 num_bitwise_op (cpp_reader *pfile ATTRIBUTE_UNUSED,
1281                 cpp_num lhs, cpp_num rhs, enum cpp_ttype op)
1282 {
1283   lhs.overflow = false;
1284   lhs.unsignedp = lhs.unsignedp || rhs.unsignedp;
1285
1286   /* As excess precision is zeroed, there is no need to num_trim () as
1287      these operations cannot introduce a set bit there.  */
1288   if (op == CPP_AND)
1289     {
1290       lhs.low &= rhs.low;
1291       lhs.high &= rhs.high;
1292     }
1293   else if (op == CPP_OR)
1294     {
1295       lhs.low |= rhs.low;
1296       lhs.high |= rhs.high;
1297     }
1298   else
1299     {
1300       lhs.low ^= rhs.low;
1301       lhs.high ^= rhs.high;
1302     }
1303
1304   return lhs;
1305 }
1306
1307 /* Returns LHS OP RHS, where OP is an inequality.  */
1308 static cpp_num
1309 num_inequality_op (cpp_reader *pfile, cpp_num lhs, cpp_num rhs,
1310                    enum cpp_ttype op)
1311 {
1312   bool gte = num_greater_eq (lhs, rhs, CPP_OPTION (pfile, precision));
1313
1314   if (op == CPP_GREATER_EQ)
1315     lhs.low = gte;
1316   else if (op == CPP_LESS)
1317     lhs.low = !gte;
1318   else if (op == CPP_GREATER)
1319     lhs.low = gte && !num_eq (lhs, rhs);
1320   else /* CPP_LESS_EQ.  */
1321     lhs.low = !gte || num_eq (lhs, rhs);
1322
1323   lhs.high = 0;
1324   lhs.overflow = false;
1325   lhs.unsignedp = false;
1326   return lhs;
1327 }
1328
1329 /* Returns LHS OP RHS, where OP is == or !=.  */
1330 static cpp_num
1331 num_equality_op (cpp_reader *pfile ATTRIBUTE_UNUSED,
1332                  cpp_num lhs, cpp_num rhs, enum cpp_ttype op)
1333 {
1334   /* Work around a 3.0.4 bug; see PR 6950.  */
1335   bool eq = num_eq (lhs, rhs);
1336   if (op == CPP_NOT_EQ)
1337     eq = !eq;
1338   lhs.low = eq;
1339   lhs.high = 0;
1340   lhs.overflow = false;
1341   lhs.unsignedp = false;
1342   return lhs;
1343 }
1344
1345 /* Shift NUM, of width PRECISION, right by N bits.  */
1346 static cpp_num
1347 num_rshift (cpp_num num, size_t precision, size_t n)
1348 {
1349   cpp_num_part sign_mask;
1350   bool x = num_positive (num, precision);
1351
1352   if (num.unsignedp || x)
1353     sign_mask = 0;
1354   else
1355     sign_mask = ~(cpp_num_part) 0;
1356
1357   if (n >= precision)
1358     num.high = num.low = sign_mask;
1359   else
1360     {
1361       /* Sign-extend.  */
1362       if (precision < PART_PRECISION)
1363         num.high = sign_mask, num.low |= sign_mask << precision;
1364       else if (precision < 2 * PART_PRECISION)
1365         num.high |= sign_mask << (precision - PART_PRECISION);
1366
1367       if (n >= PART_PRECISION)
1368         {
1369           n -= PART_PRECISION;
1370           num.low = num.high;
1371           num.high = sign_mask;
1372         }
1373
1374       if (n)
1375         {
1376           num.low = (num.low >> n) | (num.high << (PART_PRECISION - n));
1377           num.high = (num.high >> n) | (sign_mask << (PART_PRECISION - n));
1378         }
1379     }
1380
1381   num = num_trim (num, precision);
1382   num.overflow = false;
1383   return num;
1384 }
1385
1386 /* Shift NUM, of width PRECISION, left by N bits.  */
1387 static cpp_num
1388 num_lshift (cpp_num num, size_t precision, size_t n)
1389 {
1390   if (n >= precision)
1391     {
1392       num.overflow = !num.unsignedp && !num_zerop (num);
1393       num.high = num.low = 0;
1394     }
1395   else
1396     {
1397       cpp_num orig, maybe_orig;
1398       size_t m = n;
1399
1400       orig = num;
1401       if (m >= PART_PRECISION)
1402         {
1403           m -= PART_PRECISION;
1404           num.high = num.low;
1405           num.low = 0;
1406         }
1407       if (m)
1408         {
1409           num.high = (num.high << m) | (num.low >> (PART_PRECISION - m));
1410           num.low <<= m;
1411         }
1412       num = num_trim (num, precision);
1413
1414       if (num.unsignedp)
1415         num.overflow = false;
1416       else
1417         {
1418           maybe_orig = num_rshift (num, precision, n);
1419           num.overflow = !num_eq (orig, maybe_orig);
1420         }
1421     }
1422
1423   return num;
1424 }
1425
1426 /* The four unary operators: +, -, ! and ~.  */
1427 static cpp_num
1428 num_unary_op (cpp_reader *pfile, cpp_num num, enum cpp_ttype op)
1429 {
1430   switch (op)
1431     {
1432     case CPP_UPLUS:
1433       if (CPP_WTRADITIONAL (pfile) && !pfile->state.skip_eval)
1434         cpp_error (pfile, CPP_DL_WARNING,
1435                    "traditional C rejects the unary plus operator");
1436       num.overflow = false;
1437       break;
1438
1439     case CPP_UMINUS:
1440       num = num_negate (num, CPP_OPTION (pfile, precision));
1441       break;
1442
1443     case CPP_COMPL:
1444       num.high = ~num.high;
1445       num.low = ~num.low;
1446       num = num_trim (num, CPP_OPTION (pfile, precision));
1447       num.overflow = false;
1448       break;
1449
1450     default: /* case CPP_NOT: */
1451       num.low = num_zerop (num);
1452       num.high = 0;
1453       num.overflow = false;
1454       num.unsignedp = false;
1455       break;
1456     }
1457
1458   return num;
1459 }
1460
1461 /* The various binary operators.  */
1462 static cpp_num
1463 num_binary_op (cpp_reader *pfile, cpp_num lhs, cpp_num rhs, enum cpp_ttype op)
1464 {
1465   cpp_num result;
1466   size_t precision = CPP_OPTION (pfile, precision);
1467   size_t n;
1468
1469   switch (op)
1470     {
1471       /* Shifts.  */
1472     case CPP_LSHIFT:
1473     case CPP_RSHIFT:
1474       if (!rhs.unsignedp && !num_positive (rhs, precision))
1475         {
1476           /* A negative shift is a positive shift the other way.  */
1477           if (op == CPP_LSHIFT)
1478             op = CPP_RSHIFT;
1479           else
1480             op = CPP_LSHIFT;
1481           rhs = num_negate (rhs, precision);
1482         }
1483       if (rhs.high)
1484         n = ~0;                 /* Maximal.  */
1485       else
1486         n = rhs.low;
1487       if (op == CPP_LSHIFT)
1488         lhs = num_lshift (lhs, precision, n);
1489       else
1490         lhs = num_rshift (lhs, precision, n);
1491       break;
1492
1493       /* Arithmetic.  */
1494     case CPP_MINUS:
1495       rhs = num_negate (rhs, precision);
1496     case CPP_PLUS:
1497       result.low = lhs.low + rhs.low;
1498       result.high = lhs.high + rhs.high;
1499       if (result.low < lhs.low)
1500         result.high++;
1501       result.unsignedp = lhs.unsignedp || rhs.unsignedp;
1502       result.overflow = false;
1503
1504       result = num_trim (result, precision);
1505       if (!result.unsignedp)
1506         {
1507           bool lhsp = num_positive (lhs, precision);
1508           result.overflow = (lhsp == num_positive (rhs, precision)
1509                              && lhsp != num_positive (result, precision));
1510         }
1511       return result;
1512
1513       /* Comma.  */
1514     default: /* case CPP_COMMA: */
1515       if (CPP_PEDANTIC (pfile) && (!CPP_OPTION (pfile, c99)
1516                                    || !pfile->state.skip_eval))
1517         cpp_error (pfile, CPP_DL_PEDWARN,
1518                    "comma operator in operand of #if");
1519       lhs = rhs;
1520       break;
1521     }
1522
1523   return lhs;
1524 }
1525
1526 /* Multiplies two unsigned cpp_num_parts to give a cpp_num.  This
1527    cannot overflow.  */
1528 static cpp_num
1529 num_part_mul (cpp_num_part lhs, cpp_num_part rhs)
1530 {
1531   cpp_num result;
1532   cpp_num_part middle[2], temp;
1533
1534   result.low = LOW_PART (lhs) * LOW_PART (rhs);
1535   result.high = HIGH_PART (lhs) * HIGH_PART (rhs);
1536
1537   middle[0] = LOW_PART (lhs) * HIGH_PART (rhs);
1538   middle[1] = HIGH_PART (lhs) * LOW_PART (rhs);
1539
1540   temp = result.low;
1541   result.low += LOW_PART (middle[0]) << (PART_PRECISION / 2);
1542   if (result.low < temp)
1543     result.high++;
1544
1545   temp = result.low;
1546   result.low += LOW_PART (middle[1]) << (PART_PRECISION / 2);
1547   if (result.low < temp)
1548     result.high++;
1549
1550   result.high += HIGH_PART (middle[0]);
1551   result.high += HIGH_PART (middle[1]);
1552   result.unsignedp = true;
1553   result.overflow = false;
1554
1555   return result;
1556 }
1557
1558 /* Multiply two preprocessing numbers.  */
1559 static cpp_num
1560 num_mul (cpp_reader *pfile, cpp_num lhs, cpp_num rhs)
1561 {
1562   cpp_num result, temp;
1563   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1564   bool overflow, negate = false;
1565   size_t precision = CPP_OPTION (pfile, precision);
1566
1567   /* Prepare for unsigned multiplication.  */
1568   if (!unsignedp)
1569     {
1570       if (!num_positive (lhs, precision))
1571         negate = !negate, lhs = num_negate (lhs, precision);
1572       if (!num_positive (rhs, precision))
1573         negate = !negate, rhs = num_negate (rhs, precision);
1574     }
1575
1576   overflow = lhs.high && rhs.high;
1577   result = num_part_mul (lhs.low, rhs.low);
1578
1579   temp = num_part_mul (lhs.high, rhs.low);
1580   result.high += temp.low;
1581   if (temp.high)
1582     overflow = true;
1583
1584   temp = num_part_mul (lhs.low, rhs.high);
1585   result.high += temp.low;
1586   if (temp.high)
1587     overflow = true;
1588
1589   temp.low = result.low, temp.high = result.high;
1590   result = num_trim (result, precision);
1591   if (!num_eq (result, temp))
1592     overflow = true;
1593
1594   if (negate)
1595     result = num_negate (result, precision);
1596
1597   if (unsignedp)
1598     result.overflow = false;
1599   else
1600     result.overflow = overflow || (num_positive (result, precision) ^ !negate
1601                                    && !num_zerop (result));
1602   result.unsignedp = unsignedp;
1603
1604   return result;
1605 }
1606
1607 /* Divide two preprocessing numbers, returning the answer or the
1608    remainder depending upon OP.  */
1609 static cpp_num
1610 num_div_op (cpp_reader *pfile, cpp_num lhs, cpp_num rhs, enum cpp_ttype op)
1611 {
1612   cpp_num result, sub;
1613   cpp_num_part mask;
1614   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1615   bool negate = false, lhs_neg = false;
1616   size_t i, precision = CPP_OPTION (pfile, precision);
1617
1618   /* Prepare for unsigned division.  */
1619   if (!unsignedp)
1620     {
1621       if (!num_positive (lhs, precision))
1622         negate = !negate, lhs_neg = true, lhs = num_negate (lhs, precision);
1623       if (!num_positive (rhs, precision))
1624         negate = !negate, rhs = num_negate (rhs, precision);
1625     }
1626
1627   /* Find the high bit.  */
1628   if (rhs.high)
1629     {
1630       i = precision - 1;
1631       mask = (cpp_num_part) 1 << (i - PART_PRECISION);
1632       for (; ; i--, mask >>= 1)
1633         if (rhs.high & mask)
1634           break;
1635     }
1636   else if (rhs.low)
1637     {
1638       if (precision > PART_PRECISION)
1639         i = precision - PART_PRECISION - 1;
1640       else
1641         i = precision - 1;
1642       mask = (cpp_num_part) 1 << i;
1643       for (; ; i--, mask >>= 1)
1644         if (rhs.low & mask)
1645           break;
1646     }
1647   else
1648     {
1649       if (!pfile->state.skip_eval)
1650         cpp_error (pfile, CPP_DL_ERROR, "division by zero in #if");
1651       return lhs;
1652     }
1653
1654   /* First nonzero bit of RHS is bit I.  Do naive division by
1655      shifting the RHS fully left, and subtracting from LHS if LHS is
1656      at least as big, and then repeating but with one less shift.
1657      This is not very efficient, but is easy to understand.  */
1658
1659   rhs.unsignedp = true;
1660   lhs.unsignedp = true;
1661   i = precision - i - 1;
1662   sub = num_lshift (rhs, precision, i);
1663
1664   result.high = result.low = 0;
1665   for (;;)
1666     {
1667       if (num_greater_eq (lhs, sub, precision))
1668         {
1669           lhs = num_binary_op (pfile, lhs, sub, CPP_MINUS);
1670           if (i >= PART_PRECISION)
1671             result.high |= (cpp_num_part) 1 << (i - PART_PRECISION);
1672           else
1673             result.low |= (cpp_num_part) 1 << i;
1674         }
1675       if (i-- == 0)
1676         break;
1677       sub.low = (sub.low >> 1) | (sub.high << (PART_PRECISION - 1));
1678       sub.high >>= 1;
1679     }
1680
1681   /* We divide so that the remainder has the sign of the LHS.  */
1682   if (op == CPP_DIV)
1683     {
1684       result.unsignedp = unsignedp;
1685       result.overflow = false;
1686       if (!unsignedp)
1687         {
1688           if (negate)
1689             result = num_negate (result, precision);
1690           result.overflow = (num_positive (result, precision) ^ !negate
1691                              && !num_zerop (result));
1692         }
1693
1694       return result;
1695     }
1696
1697   /* CPP_MOD.  */
1698   lhs.unsignedp = unsignedp;
1699   lhs.overflow = false;
1700   if (lhs_neg)
1701     lhs = num_negate (lhs, precision);
1702
1703   return lhs;
1704 }