gcc/cppexp.c

   1 /* Parse C expressions for cpplib.
   2    Copyright (C) 1987, 1992, 1994, 1995, 1997, 1998, 1999, 2000, 2001
   3    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 /* Parse a C expression from text in a string  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "cpplib.h"
  26 #include "cpphash.h"
  27
  28 #ifndef MAX_CHAR_TYPE_SIZE
  29 #define MAX_CHAR_TYPE_SIZE CHAR_TYPE_SIZE
  30 #endif
  31
  32 #ifndef MAX_INT_TYPE_SIZE
  33 #define MAX_INT_TYPE_SIZE INT_TYPE_SIZE
  34 #endif
  35
  36 #ifndef MAX_LONG_TYPE_SIZE
  37 #define MAX_LONG_TYPE_SIZE LONG_TYPE_SIZE
  38 #endif
  39
  40 #ifndef MAX_WCHAR_TYPE_SIZE
  41 #define MAX_WCHAR_TYPE_SIZE WCHAR_TYPE_SIZE
  42 #endif
  43
  44 #define MAX_CHAR_TYPE_MASK (MAX_CHAR_TYPE_SIZE < HOST_BITS_PER_WIDEST_INT \
  45                     ? (~(~(HOST_WIDEST_INT) 0 << MAX_CHAR_TYPE_SIZE)) \
  46                     : ~ (HOST_WIDEST_INT) 0)
  47
  48 #define MAX_WCHAR_TYPE_MASK (MAX_WCHAR_TYPE_SIZE < HOST_BITS_PER_WIDEST_INT \
  49                              ? ~(~(HOST_WIDEST_INT) 0 << MAX_WCHAR_TYPE_SIZE) \
  50                              : ~ (HOST_WIDEST_INT) 0)
  51
  52 /* Yield nonzero if adding two numbers with A's and B's signs can yield a
  53    number with SUM's sign, where A, B, and SUM are all C integers.  */
  54 #define possible_sum_sign(a, b, sum) ((((a) ^ (b)) | ~ ((a) ^ (sum))) < 0)
  55
  56 static void integer_overflow PARAMS ((cpp_reader *));
  57 static HOST_WIDEST_INT left_shift PARAMS ((cpp_reader *, HOST_WIDEST_INT,
  58                                            unsigned int,
  59                                            unsigned HOST_WIDEST_INT));
  60 static HOST_WIDEST_INT right_shift PARAMS ((cpp_reader *, HOST_WIDEST_INT,
  61                                             unsigned int,
  62                                             unsigned HOST_WIDEST_INT));
  63 static struct op parse_number PARAMS ((cpp_reader *, const cpp_token *));
  64 static struct op parse_charconst PARAMS ((cpp_reader *, const cpp_token *));
  65 static struct op parse_defined PARAMS ((cpp_reader *));
  66 static HOST_WIDEST_INT parse_escape PARAMS ((cpp_reader *, const U_CHAR **,
  67                                              const U_CHAR *, HOST_WIDEST_INT));
  68 static struct op lex PARAMS ((cpp_reader *, int, cpp_token *));
  69 static const unsigned char *op_as_text PARAMS ((cpp_reader *, enum cpp_ttype));
  70
  71 struct op
  72 {
  73   enum cpp_ttype op;
  74   U_CHAR prio;         /* Priority of op.  */
  75   U_CHAR flags;
  76   U_CHAR unsignedp;    /* True if value should be treated as unsigned.  */
  77   HOST_WIDEST_INT value; /* The value logically "right" of op.  */
  78 };
  79
  80 /* There is no "error" token, but we can't get comments in #if, so we can
  81    abuse that token type.  */
  82 #define CPP_ERROR CPP_COMMENT
  83
  84 /* With -O2, gcc appears to produce nice code, moving the error
  85    message load and subsequent jump completely out of the main path.  */
  86 #define CPP_ICE(msgid) \
  87   do { cpp_ice (pfile, msgid); goto syntax_error; } while(0)
  88 #define SYNTAX_ERROR(msgid) \
  89   do { cpp_error (pfile, msgid); goto syntax_error; } while(0)
  90 #define SYNTAX_ERROR2(msgid, arg) \
  91   do { cpp_error (pfile, msgid, arg); goto syntax_error; } while(0)
  92
  93 /* Parse and convert an integer for #if.  Accepts decimal, hex, or octal
  94    with or without size suffixes.  */
  95 struct suffix
  96 {
  97   unsigned char s[4];
  98   unsigned char u;
  99   unsigned char l;
 100 };
 101
 102 const struct suffix vsuf_1[] = {
 103   { "u", 1, 0 }, { "U", 1, 0 },
 104   { "l", 0, 1 }, { "L", 0, 1 }
 105 };
 106
 107 const struct suffix vsuf_2[] = {
 108   { "ul", 1, 1 }, { "UL", 1, 1 }, { "uL", 1, 1 }, { "Ul", 1, 1 },
 109   { "lu", 1, 1 }, { "LU", 1, 1 }, { "Lu", 1, 1 }, { "lU", 1, 1 },
 110   { "ll", 0, 2 }, { "LL", 0, 2 }
 111 };
 112
 113 const struct suffix vsuf_3[] = {
 114   { "ull", 1, 2 }, { "ULL", 1, 2 }, { "uLL", 1, 2 }, { "Ull", 1, 2 },
 115   { "llu", 1, 2 }, { "LLU", 1, 2 }, { "LLu", 1, 2 }, { "llU", 1, 2 }
 116 };
 117 #define Nsuff(tab) (sizeof tab / sizeof (struct suffix))
 118
 119 static struct op
 120 parse_number (pfile, tok)
 121      cpp_reader *pfile;
 122      const cpp_token *tok;
 123 {
 124   struct op op;
 125   const U_CHAR *start = tok->val.str.text;
 126   const U_CHAR *end = start + tok->val.str.len;
 127   const U_CHAR *p = start;
 128   int c = 0, i, nsuff;
 129   unsigned HOST_WIDEST_INT n = 0, nd, MAX_over_base;
 130   int base = 10;
 131   int overflow = 0;
 132   int digit, largest_digit = 0;
 133   const struct suffix *sufftab;
 134
 135   op.unsignedp = 0;
 136
 137   if (p[0] == '0')
 138     {
 139       if (end - start >= 3 && (p[1] == 'x' || p[1] == 'X'))
 140         {
 141           p += 2;
 142           base = 16;
 143         }
 144       else
 145         {
 146           p += 1;
 147           base = 8;
 148         }
 149     }
 150
 151   /* Some buggy compilers (e.g. MPW C) seem to need both casts.  */
 152   MAX_over_base = (((unsigned HOST_WIDEST_INT) -1)
 153                    / ((unsigned HOST_WIDEST_INT) base));
 154
 155   for(; p < end; p++)
 156     {
 157       c = *p;
 158
 159       if (c >= '0' && c <= '9')
 160         digit = c - '0';
 161       /* We believe that in all live character sets, a-f are
 162          consecutive, and so are A-F.  */
 163       else if (base == 16 && c >= 'a' && c <= 'f')
 164         digit = c - 'a' + 10;
 165       else if (base == 16 && c >= 'A' && c <= 'F')
 166         digit = c - 'A' + 10;
 167       else
 168         break;
 169
 170       if (largest_digit < digit)
 171         largest_digit = digit;
 172       nd = n * base + digit;
 173       overflow |= MAX_over_base < n || nd < n;
 174       n = nd;
 175     }
 176
 177   if (p < end)
 178     {
 179       /* Check for a floating point constant.  Note that float constants
 180          with an exponent or suffix but no decimal point are technically
 181          invalid (C99 6.4.4.2) but accepted elsewhere.  */
 182       if ((c == '.' || c == 'F' || c == 'f')
 183           || (base == 10 && (c == 'E' || c == 'e')
 184               && p+1 < end && (p[1] == '+' || p[1] == '-'))
 185           || (base == 16 && (c == 'P' || c == 'p')
 186               && p+1 < end && (p[1] == '+' || p[1] == '-')))
 187         SYNTAX_ERROR ("floating point numbers are not valid in #if");
 188
 189       /* Determine the suffix. l means long, and u means unsigned.
 190          See the suffix tables, above.  */
 191       switch (end - p)
 192         {
 193         case 1: sufftab = vsuf_1; nsuff = Nsuff(vsuf_1); break;
 194         case 2: sufftab = vsuf_2; nsuff = Nsuff(vsuf_2); break;
 195         case 3: sufftab = vsuf_3; nsuff = Nsuff(vsuf_3); break;
 196         default: goto invalid_suffix;
 197         }
 198
 199       for (i = 0; i < nsuff; i++)
 200         if (memcmp (p, sufftab[i].s, end - p) == 0)
 201           break;
 202       if (i == nsuff)
 203         goto invalid_suffix;
 204       op.unsignedp = sufftab[i].u;
 205
 206       if (CPP_WTRADITIONAL (pfile)
 207           && sufftab[i].u
 208           && ! cpp_sys_objmacro_p (pfile))
 209         cpp_warning (pfile, "traditional C rejects the `U' suffix");
 210       if (sufftab[i].l == 2 && CPP_OPTION (pfile, pedantic)
 211           && ! CPP_OPTION (pfile, c99))
 212         cpp_pedwarn (pfile, "too many 'l' suffixes in integer constant");
 213     }
 214
 215   if (base <= largest_digit)
 216     cpp_pedwarn (pfile, "integer constant contains digits beyond the radix");
 217
 218   if (overflow)
 219     cpp_pedwarn (pfile, "integer constant out of range");
 220
 221   /* If too big to be signed, consider it unsigned.  */
 222   else if ((HOST_WIDEST_INT) n < 0 && ! op.unsignedp)
 223     {
 224       if (base == 10)
 225         cpp_warning (pfile, "integer constant is so large that it is unsigned");
 226       op.unsignedp = 1;
 227     }
 228
 229   op.value = n;
 230   op.op = CPP_INT;
 231   return op;
 232
 233  invalid_suffix:
 234   cpp_error (pfile, "invalid suffix '%.*s' on integer constant",
 235              (int) (end - p), p);
 236  syntax_error:
 237   op.op = CPP_ERROR;
 238   return op;
 239 }
 240
 241 /* Parse and convert a character constant for #if.  Understands backslash
 242    escapes (\n, \031) and multibyte characters (if so configured).  */
 243 static struct op
 244 parse_charconst (pfile, tok)
 245      cpp_reader *pfile;
 246      const cpp_token *tok;
 247 {
 248   struct op op;
 249   HOST_WIDEST_INT result = 0;
 250   int num_chars = 0;
 251   int num_bits;
 252   unsigned int width = MAX_CHAR_TYPE_SIZE;
 253   HOST_WIDEST_INT mask = MAX_CHAR_TYPE_MASK;
 254   int max_chars;
 255   const U_CHAR *ptr = tok->val.str.text;
 256   const U_CHAR *end = ptr + tok->val.str.len;
 257
 258   int c = -1;
 259
 260   if (tok->type == CPP_WCHAR)
 261     width = MAX_WCHAR_TYPE_SIZE, mask = MAX_WCHAR_TYPE_MASK;
 262   max_chars = MAX_LONG_TYPE_SIZE / width;
 263
 264   while (ptr < end)
 265     {
 266       c = *ptr++;
 267       if (c == '\'')
 268         CPP_ICE ("unescaped ' in character constant");
 269       else if (c == '\\')
 270         {
 271           c = parse_escape (pfile, &ptr, end, mask);
 272           if (width < HOST_BITS_PER_INT
 273               && (unsigned int) c >= (unsigned int)(1 << width))
 274             cpp_pedwarn (pfile,
 275                          "escape sequence out of range for character");
 276         }
 277
 278       /* Merge character into result; ignore excess chars.  */
 279       if (++num_chars <= max_chars)
 280         {
 281           if (width < HOST_BITS_PER_INT)
 282             result = (result << width) | (c & ((1 << width) - 1));
 283           else
 284             result = c;
 285         }
 286     }
 287
 288   if (num_chars == 0)
 289     SYNTAX_ERROR ("empty character constant");
 290   else if (num_chars > max_chars)
 291     SYNTAX_ERROR ("character constant too long");
 292   else if (num_chars != 1)
 293     cpp_warning (pfile, "multi-character character constant");
 294
 295   /* If char type is signed, sign-extend the constant.  */
 296   num_bits = num_chars * width;
 297
 298   if (pfile->spec_nodes.n__CHAR_UNSIGNED__->type == NT_MACRO
 299       || ((result >> (num_bits - 1)) & 1) == 0)
 300     op.value = result & ((unsigned HOST_WIDEST_INT) ~0
 301                          >> (HOST_BITS_PER_WIDEST_INT - num_bits));
 302   else
 303     op.value = result | ~((unsigned HOST_WIDEST_INT) ~0
 304                           >> (HOST_BITS_PER_WIDEST_INT - num_bits));
 305
 306   /* This is always a signed type.  */
 307   op.unsignedp = 0;
 308   op.op = CPP_INT;
 309   return op;
 310
 311  syntax_error:
 312   op.op = CPP_ERROR;
 313   return op;
 314 }
 315
 316 static struct op
 317 parse_defined (pfile)
 318      cpp_reader *pfile;
 319 {
 320   int paren = 0;
 321   cpp_hashnode *node = 0;
 322   cpp_token token;
 323   struct op op;
 324
 325   /* Don't expand macros.  */
 326   pfile->state.prevent_expansion++;
 327
 328   cpp_get_token (pfile, &token);
 329   if (token.type == CPP_OPEN_PAREN)
 330     {
 331       paren = 1;
 332       cpp_get_token (pfile, &token);
 333     }
 334
 335   if (token.type == CPP_NAME)
 336     {
 337       node = token.val.node;
 338       if (paren)
 339         {
 340           cpp_get_token (pfile, &token);
 341           if (token.type != CPP_CLOSE_PAREN)
 342             {
 343               cpp_error (pfile, "missing ')' after \"defined\"");
 344               node = 0;
 345             }
 346         }
 347     }
 348   else
 349     {
 350       cpp_error (pfile, "operator \"defined\" requires an identifier");
 351       if (token.flags & NAMED_OP)
 352         {
 353           cpp_token op;
 354
 355           op.flags = 0;
 356           op.type = token.type;
 357           cpp_error (pfile,
 358                      "(\"%s\" is an alternative token for \"%s\" in C++)",
 359                      cpp_token_as_text (pfile, &token),
 360                      cpp_token_as_text (pfile, &op));
 361         }
 362     }
 363
 364   if (!node)
 365     op.op = CPP_ERROR;
 366   else
 367     {
 368       op.value = node->type == NT_MACRO;
 369       op.unsignedp = 0;
 370       op.op = CPP_INT;
 371
 372       /* No macros?  At top of file?  */
 373       if (pfile->mi_state == MI_OUTSIDE && pfile->mi_cmacro == 0
 374           && pfile->mi_if_not_defined == MI_IND_NOT && pfile->mi_lexed == 1)
 375         {
 376           cpp_start_lookahead (pfile);
 377           cpp_get_token (pfile, &token);
 378           if (token.type == CPP_EOF)
 379             pfile->mi_ind_cmacro = node;
 380           cpp_stop_lookahead (pfile, 0);
 381         }
 382     }
 383
 384   pfile->state.prevent_expansion--;
 385   return op;
 386 }
 387
 388 /* Read one token.  */
 389
 390 static struct op
 391 lex (pfile, skip_evaluation, token)
 392      cpp_reader *pfile;
 393      int skip_evaluation;
 394      cpp_token *token;
 395 {
 396   struct op op;
 397
 398   cpp_get_token (pfile, token);
 399
 400   switch (token->type)
 401     {
 402     case CPP_INT:
 403     case CPP_NUMBER:
 404       return parse_number (pfile, token);
 405
 406     case CPP_CHAR:
 407     case CPP_WCHAR:
 408       return parse_charconst (pfile, token);
 409
 410     case CPP_STRING:
 411     case CPP_WSTRING:
 412       SYNTAX_ERROR ("string constants are not valid in #if");
 413
 414     case CPP_FLOAT:
 415       SYNTAX_ERROR ("floating point numbers are not valid in #if");
 416
 417     case CPP_OTHER:
 418       if (ISGRAPH (token->val.c))
 419         SYNTAX_ERROR2 ("invalid character '%c' in #if", token->val.c);
 420       else
 421         SYNTAX_ERROR2 ("invalid character '\\%03o' in #if", token->val.c);
 422
 423     case CPP_NAME:
 424       if (token->val.node == pfile->spec_nodes.n_defined)
 425         {
 426           if (pfile->context->prev && CPP_PEDANTIC (pfile))
 427             cpp_pedwarn (pfile, "\"defined\" operator appears during macro expansion");
 428
 429           return parse_defined (pfile);
 430         }
 431       else if (CPP_OPTION (pfile, cplusplus)
 432                && (token->val.node == pfile->spec_nodes.n_true
 433                    || token->val.node == pfile->spec_nodes.n_false))
 434         {
 435           op.op = CPP_INT;
 436           op.unsignedp = 0;
 437           op.value = (token->val.node == pfile->spec_nodes.n_true);
 438
 439           /* Warn about use of true or false in #if when pedantic
 440              and stdbool.h has not been included.  */
 441           if (CPP_PEDANTIC (pfile)
 442               && ! cpp_defined (pfile, DSC("__bool_true_false_are_defined")))
 443             cpp_pedwarn (pfile, "ISO C++ does not permit \"%s\" in #if",
 444                          token->val.node->name);
 445           return op;
 446         }
 447       else
 448         {
 449           /* Controlling #if expressions cannot contain identifiers (they
 450              could become macros in the future).  */
 451           pfile->mi_state = MI_FAILED;
 452
 453           op.op = CPP_INT;
 454           op.unsignedp = 0;
 455           op.value = 0;
 456
 457           if (CPP_OPTION (pfile, warn_undef) && !skip_evaluation)
 458             cpp_warning (pfile, "\"%s\" is not defined", token->val.node->name);
 459           return op;
 460         }
 461
 462     case CPP_HASH:
 463       {
 464         int temp;
 465
 466         op.op = CPP_INT;
 467         if (_cpp_test_assertion (pfile, &temp))
 468           op.op = CPP_ERROR;
 469         op.unsignedp = 0;
 470         op.value = temp;
 471         return op;
 472       }
 473
 474     case CPP_NOT:
 475       /* We don't worry about its position here.  */
 476       pfile->mi_if_not_defined = MI_IND_NOT;
 477       /* Fall through.  */
 478
 479     default:
 480       if (((int) token->type > (int) CPP_EQ
 481            && (int) token->type < (int) CPP_PLUS_EQ)
 482           || token->type == CPP_EOF)
 483         {
 484           op.op = token->type;
 485           return op;
 486         }
 487
 488       SYNTAX_ERROR2 ("\"%s\" is not valid in #if expressions",
 489                      cpp_token_as_text (pfile, token));
 490     }
 491
 492  syntax_error:
 493   op.op = CPP_ERROR;
 494   return op;
 495 }
 496
 497 /* Parse a C escape sequence.  STRING_PTR points to a variable
 498    containing a pointer to the string to parse.  That pointer
 499    is updated past the characters we use.  The value of the
 500    escape sequence is returned.
 501
 502    If \ is followed by 000, we return 0 and leave the string pointer
 503    after the zeros.  A value of 0 does not mean end of string.  */
 504
 505 static HOST_WIDEST_INT
 506 parse_escape (pfile, string_ptr, limit, result_mask)
 507      cpp_reader *pfile;
 508      const U_CHAR **string_ptr;
 509      const U_CHAR *limit;
 510      HOST_WIDEST_INT result_mask;
 511 {
 512   const U_CHAR *ptr = *string_ptr;
 513   /* We know we have at least one following character.  */
 514   int c = *ptr++;
 515   switch (c)
 516     {
 517     case 'a': c = TARGET_BELL;    break;
 518     case 'b': c = TARGET_BS;      break;
 519     case 'f': c = TARGET_FF;      break;
 520     case 'n': c = TARGET_NEWLINE; break;
 521     case 'r': c = TARGET_CR;      break;
 522     case 't': c = TARGET_TAB;     break;
 523     case 'v': c = TARGET_VT;      break;
 524
 525     case 'e': case 'E':
 526       if (CPP_PEDANTIC (pfile))
 527         cpp_pedwarn (pfile, "non-ISO-standard escape sequence, '\\%c'", c);
 528       c = TARGET_ESC;
 529       break;
 530
 531     case '0': case '1': case '2': case '3':
 532     case '4': case '5': case '6': case '7':
 533       {
 534         unsigned int i = c - '0';
 535         int count = 0;
 536         while (++count < 3)
 537           {
 538             if (ptr >= limit)
 539               break;
 540
 541             c = *ptr;
 542             if (c < '0' || c > '7')
 543               break;
 544             ptr++;
 545             i = (i << 3) + c - '0';
 546           }
 547         if (i != (i & result_mask))
 548           {
 549             i &= result_mask;
 550             cpp_pedwarn (pfile, "octal escape sequence out of range");
 551           }
 552         c = i;
 553         break;
 554       }
 555
 556     case 'x':
 557       {
 558         unsigned int i = 0, overflow = 0;
 559         int digits_found = 0, digit;
 560         for (;;)
 561           {
 562             if (ptr >= limit)
 563               break;
 564             c = *ptr;
 565             if (c >= '0' && c <= '9')
 566               digit = c - '0';
 567             else if (c >= 'a' && c <= 'f')
 568               digit = c - 'a' + 10;
 569             else if (c >= 'A' && c <= 'F')
 570               digit = c - 'A' + 10;
 571             else
 572               break;
 573             ptr++;
 574             overflow |= i ^ (i << 4 >> 4);
 575             i = (i << 4) + digit;
 576             digits_found = 1;
 577           }
 578         if (!digits_found)
 579           cpp_error (pfile, "\\x used with no following hex digits");
 580         if (overflow | (i != (i & result_mask)))
 581           {
 582             i &= result_mask;
 583             cpp_pedwarn (pfile, "hex escape sequence out of range");
 584           }
 585         c = i;
 586         break;
 587       }
 588     }
 589   *string_ptr = ptr;
 590   return c;
 591 }
 592
 593 static void
 594 integer_overflow (pfile)
 595      cpp_reader *pfile;
 596 {
 597   if (CPP_PEDANTIC (pfile))
 598     cpp_pedwarn (pfile, "integer overflow in preprocessor expression");
 599 }
 600
 601 static HOST_WIDEST_INT
 602 left_shift (pfile, a, unsignedp, b)
 603      cpp_reader *pfile;
 604      HOST_WIDEST_INT a;
 605      unsigned int unsignedp;
 606      unsigned HOST_WIDEST_INT b;
 607 {
 608   if (b >= HOST_BITS_PER_WIDEST_INT)
 609     {
 610       if (! unsignedp && a != 0)
 611         integer_overflow (pfile);
 612       return 0;
 613     }
 614   else if (unsignedp)
 615     return (unsigned HOST_WIDEST_INT) a << b;
 616   else
 617     {
 618       HOST_WIDEST_INT l = a << b;
 619       if (l >> b != a)
 620         integer_overflow (pfile);
 621       return l;
 622     }
 623 }
 624
 625 static HOST_WIDEST_INT
 626 right_shift (pfile, a, unsignedp, b)
 627      cpp_reader *pfile ATTRIBUTE_UNUSED;
 628      HOST_WIDEST_INT a;
 629      unsigned int unsignedp;
 630      unsigned HOST_WIDEST_INT b;
 631 {
 632   if (b >= HOST_BITS_PER_WIDEST_INT)
 633     return unsignedp ? 0 : a >> (HOST_BITS_PER_WIDEST_INT - 1);
 634   else if (unsignedp)
 635     return (unsigned HOST_WIDEST_INT) a >> b;
 636   else
 637     return a >> b;
 638 }
 639 \f
 640 /* Operator precedence and flags table.
 641
 642 After an operator is returned from the lexer, if it has priority less
 643 than or equal to the operator on the top of the stack, we reduce the
 644 stack by one operator and repeat the test.  Since equal priorities
 645 reduce, this is naturally left-associative.
 646
 647 We handle right-associative operators by clearing the lower bit of all
 648 left-associative operators, and setting it for right-associative ones.
 649 After the reduction phase of a new operator, just before it is pushed
 650 onto the stack, its RIGHT_ASSOC bit is cleared.  The effect is that
 651 during the reduction phase, the current right-associative operator has
 652 a priority one greater than any other operator of otherwise equal
 653 precedence that has been pushed on the top of the stack.  This avoids
 654 a reduction pass, and effectively makes the logic right-associative.
 655
 656 The remaining cases are '(' and ')'.  We handle '(' by skipping the
 657 reduction phase completely.  ')' is given lower priority than
 658 everything else, including '(', effectively forcing a reduction of the
 659 parenthesised expression.  If there is no matching '(', the stack will
 660 be reduced all the way to the beginning, exiting the parser in the
 661 same way as the ultra-low priority end-of-expression dummy operator.
 662 The exit code checks to see if the operator that caused it is ')', and
 663 if so outputs an appropriate error message.
 664
 665 The parser assumes all shifted operators require a right operand
 666 unless the flag NO_R_OPERAND is set, and similarly for NO_L_OPERAND.
 667 These semantics are automatically checked, any extra semantics need to
 668 be handled with operator-specific code.  */
 669
 670 #define FLAG_BITS  8
 671 #define FLAG_MASK ((1 << FLAG_BITS) - 1)
 672 #define PRIO_SHIFT (FLAG_BITS + 1)
 673 #define EXTRACT_PRIO(cnst) (cnst >> FLAG_BITS)
 674 #define EXTRACT_FLAGS(cnst) (cnst & FLAG_MASK)
 675
 676 /* Flags.  */
 677 #define HAVE_VALUE     (1 << 0)
 678 #define NO_L_OPERAND   (1 << 1)
 679 #define NO_R_OPERAND   (1 << 2)
 680 #define SHORT_CIRCUIT  (1 << 3)
 681
 682 /* Priority and flag combinations.  */
 683 #define RIGHT_ASSOC         (1 << FLAG_BITS)
 684 #define FORCE_REDUCE_PRIO   (0 << PRIO_SHIFT)
 685 #define CLOSE_PAREN_PRIO    (1 << PRIO_SHIFT)
 686 #define OPEN_PAREN_PRIO    ((2 << PRIO_SHIFT) | NO_L_OPERAND)
 687 #define COMMA_PRIO          (3 << PRIO_SHIFT)
 688 #define COND_PRIO          ((4 << PRIO_SHIFT) | RIGHT_ASSOC | SHORT_CIRCUIT)
 689 #define COLON_PRIO         ((5 << PRIO_SHIFT) | SHORT_CIRCUIT)
 690 #define OROR_PRIO          ((6 << PRIO_SHIFT) | SHORT_CIRCUIT)
 691 #define ANDAND_PRIO        ((7 << PRIO_SHIFT) | SHORT_CIRCUIT)
 692 #define OR_PRIO             (8 << PRIO_SHIFT)
 693 #define XOR_PRIO            (9 << PRIO_SHIFT)
 694 #define AND_PRIO           (10 << PRIO_SHIFT)
 695 #define MINMAX_PRIO        (11 << PRIO_SHIFT)
 696 #define EQUAL_PRIO         (12 << PRIO_SHIFT)
 697 #define LESS_PRIO          (13 << PRIO_SHIFT)
 698 #define SHIFT_PRIO         (14 << PRIO_SHIFT)
 699 #define PLUS_PRIO          (15 << PRIO_SHIFT)
 700 #define MUL_PRIO           (16 << PRIO_SHIFT)
 701 #define UNARY_PRIO        ((17 << PRIO_SHIFT) | RIGHT_ASSOC | NO_L_OPERAND)
 702
 703 /* Operator to priority map.  Must be in the same order as the first
 704    N entries of enum cpp_ttype.  */
 705 static const short
 706 op_to_prio[] =
 707 {
 708   /* EQ */              0,              /* dummy entry - can't happen */
 709   /* NOT */             UNARY_PRIO,
 710   /* GREATER */         LESS_PRIO,
 711   /* LESS */            LESS_PRIO,
 712   /* PLUS */            UNARY_PRIO,     /* note these two can be unary */
 713   /* MINUS */           UNARY_PRIO,     /* or binary */
 714   /* MULT */            MUL_PRIO,
 715   /* DIV */             MUL_PRIO,
 716   /* MOD */             MUL_PRIO,
 717   /* AND */             AND_PRIO,
 718   /* OR */              OR_PRIO,
 719   /* XOR */             XOR_PRIO,
 720   /* RSHIFT */          SHIFT_PRIO,
 721   /* LSHIFT */          SHIFT_PRIO,
 722   /* MIN */             MINMAX_PRIO,    /* C++ specific */
 723   /* MAX */             MINMAX_PRIO,    /* extensions */
 724
 725   /* COMPL */           UNARY_PRIO,
 726   /* AND_AND */         ANDAND_PRIO,
 727   /* OR_OR */           OROR_PRIO,
 728   /* QUERY */           COND_PRIO,
 729   /* COLON */           COLON_PRIO,
 730   /* COMMA */           COMMA_PRIO,
 731   /* OPEN_PAREN */      OPEN_PAREN_PRIO,
 732   /* CLOSE_PAREN */     CLOSE_PAREN_PRIO,
 733   /* EQ_EQ */           EQUAL_PRIO,
 734   /* NOT_EQ */          EQUAL_PRIO,
 735   /* GREATER_EQ */      LESS_PRIO,
 736   /* LESS_EQ */         LESS_PRIO
 737 };
 738
 739 #define COMPARE(OP) \
 740   top->unsignedp = 0; \
 741   top->value = (unsigned1 | unsigned2) \
 742   ? (unsigned HOST_WIDEST_INT) v1 OP (unsigned HOST_WIDEST_INT) v2 \
 743   : (v1 OP v2)
 744 #define EQUALITY(OP) \
 745   top->value = v1 OP v2; \
 746   top->unsignedp = 0;
 747 #define BITWISE(OP) \
 748   top->value = v1 OP v2; \
 749   top->unsignedp = unsigned1 | unsigned2;
 750 #define MINMAX(OP) \
 751   top->value = (v1 OP v2) ? v1 : v2; \
 752   top->unsignedp = unsigned1 | unsigned2;
 753 #define UNARY(OP) \
 754   top->value = OP v2; \
 755   top->unsignedp = unsigned2; \
 756   top->flags |= HAVE_VALUE;
 757 #define SHIFT(PSH, MSH) \
 758   if (skip_evaluation)  \
 759     break;              \
 760   top->unsignedp = unsigned1; \
 761   if (v2 < 0 && ! unsigned2)  \
 762     top->value = MSH (pfile, v1, unsigned1, -v2); \
 763   else \
 764     top->value = PSH (pfile, v1, unsigned1, v2);
 765
 766 /* Parse and evaluate a C expression, reading from PFILE.
 767    Returns the truth value of the expression.  */
 768
 769 int
 770 _cpp_parse_expr (pfile)
 771      cpp_reader *pfile;
 772 {
 773   /* The implementation is an operator precedence parser, i.e. a
 774      bottom-up parser, using a stack for not-yet-reduced tokens.
 775
 776      The stack base is 'stack', and the current stack pointer is 'top'.
 777      There is a stack element for each operator (only),
 778      and the most recently pushed operator is 'top->op'.
 779      An operand (value) is stored in the 'value' field of the stack
 780      element of the operator that precedes it.
 781      In that case the 'flags' field has the HAVE_VALUE flag set.  */
 782
 783 #define INIT_STACK_SIZE 20
 784   struct op init_stack[INIT_STACK_SIZE];
 785   struct op *stack = init_stack;
 786   struct op *limit = stack + INIT_STACK_SIZE;
 787   cpp_token token;
 788   register struct op *top = stack + 1;
 789   int skip_evaluation = 0;
 790   int result;
 791
 792   /* Set up detection of #if ! defined().  */
 793   pfile->mi_lexed = 0;
 794   pfile->mi_if_not_defined = MI_IND_NONE;
 795
 796   /* We've finished when we try to reduce this.  */
 797   top->op = CPP_EOF;
 798   /* Nifty way to catch missing '('.  */
 799   top->prio = EXTRACT_PRIO(CLOSE_PAREN_PRIO);
 800   /* Avoid missing right operand checks.  */
 801   top->flags = NO_R_OPERAND;
 802
 803   for (;;)
 804     {
 805       unsigned int prio;
 806       unsigned int flags;
 807       struct op op;
 808
 809       /* Read a token */
 810       op = lex (pfile, skip_evaluation, &token);
 811       pfile->mi_lexed++;
 812
 813       /* If the token is an operand, push its value and get next
 814          token.  If it is an operator, get its priority and flags, and
 815          try to reduce the expression on the stack.  */
 816       switch (op.op)
 817         {
 818         case CPP_ERROR:
 819           goto syntax_error;
 820         push_immediate:
 821         case CPP_INT:
 822           /* Push a value onto the stack.  */
 823           if (top->flags & HAVE_VALUE)
 824             SYNTAX_ERROR ("missing binary operator");
 825           top->value = op.value;
 826           top->unsignedp = op.unsignedp;
 827           top->flags |= HAVE_VALUE;
 828           continue;
 829
 830         case CPP_EOF:   prio = FORCE_REDUCE_PRIO;       break;
 831         case CPP_PLUS:
 832         case CPP_MINUS: prio = PLUS_PRIO;  if (top->flags & HAVE_VALUE) break;
 833           /* else unary; fall through */
 834         default:        prio = op_to_prio[op.op];       break;
 835         }
 836
 837       /* Separate the operator's code into priority and flags.  */
 838       flags = EXTRACT_FLAGS(prio);
 839       prio = EXTRACT_PRIO(prio);
 840       if (prio == EXTRACT_PRIO(OPEN_PAREN_PRIO))
 841         goto skip_reduction;
 842
 843       /* Check for reductions.  Then push the operator.  */
 844       while (prio <= top->prio)
 845         {
 846           HOST_WIDEST_INT v1, v2;
 847           unsigned int unsigned1, unsigned2;
 848
 849           /* Most operators that can appear on the stack require a
 850              right operand.  Check this before trying to reduce.  */
 851           if ((top->flags & (HAVE_VALUE | NO_R_OPERAND)) == 0)
 852             {
 853               if (top->op == CPP_OPEN_PAREN)
 854                 SYNTAX_ERROR ("void expression between '(' and ')'");
 855               else
 856                 SYNTAX_ERROR2 ("operator '%s' has no right operand",
 857                                op_as_text (pfile, top->op));
 858             }
 859
 860           unsigned2 = top->unsignedp, v2 = top->value;
 861           top--;
 862           unsigned1 = top->unsignedp, v1 = top->value;
 863
 864           /* Now set top->value = (top[1].op)(v1, v2); */
 865           switch (top[1].op)
 866             {
 867             default:
 868               cpp_ice (pfile, "impossible operator '%s'",
 869                                op_as_text (pfile, top[1].op));
 870               goto syntax_error;
 871
 872             case CPP_NOT:        UNARY(!);      break;
 873             case CPP_COMPL:      UNARY(~);      break;
 874             case CPP_LESS:       COMPARE(<);    break;
 875             case CPP_GREATER:    COMPARE(>);    break;
 876             case CPP_LESS_EQ:    COMPARE(<=);   break;
 877             case CPP_GREATER_EQ: COMPARE(>=);   break;
 878             case CPP_EQ_EQ:      EQUALITY(==);  break;
 879             case CPP_NOT_EQ:     EQUALITY(!=);  break;
 880             case CPP_AND:        BITWISE(&);    break;
 881             case CPP_XOR:        BITWISE(^);    break;
 882             case CPP_OR:         BITWISE(|);    break;
 883             case CPP_LSHIFT:     SHIFT(left_shift, right_shift); break;
 884             case CPP_RSHIFT:     SHIFT(right_shift, left_shift); break;
 885             case CPP_MIN:        MINMAX(<);     break;
 886             case CPP_MAX:        MINMAX(>);     break;
 887
 888             case CPP_PLUS:
 889               if (!(top->flags & HAVE_VALUE))
 890                 {
 891                   /* Can't use UNARY(+) because K+R C did not have unary
 892                      plus.  Can't use UNARY() because some compilers object
 893                      to the empty argument.  */
 894                   top->value = v2;
 895                   top->unsignedp = unsigned2;
 896                   top->flags |= HAVE_VALUE;
 897
 898                   if (CPP_WTRADITIONAL (pfile))
 899                     cpp_warning (pfile,
 900                         "traditional C rejects the unary plus operator");
 901                 }
 902               else
 903                 {
 904                   top->value = v1 + v2;
 905                   top->unsignedp = unsigned1 | unsigned2;
 906                   if (! top->unsignedp && ! skip_evaluation
 907                       && ! possible_sum_sign (v1, v2, top->value))
 908                     integer_overflow (pfile);
 909                 }
 910               break;
 911             case CPP_MINUS:
 912               if (!(top->flags & HAVE_VALUE))
 913                 {
 914                   UNARY(-);
 915                   if (!skip_evaluation && (top->value & v2) < 0 && !unsigned2)
 916                     integer_overflow (pfile);
 917                 }
 918               else
 919                 { /* Binary '-' */
 920                   top->value = v1 - v2;
 921                   top->unsignedp = unsigned1 | unsigned2;
 922                   if (! top->unsignedp && ! skip_evaluation
 923                       && ! possible_sum_sign (top->value, v2, v1))
 924                     integer_overflow (pfile);
 925                 }
 926               break;
 927             case CPP_MULT:
 928               top->unsignedp = unsigned1 | unsigned2;
 929               if (top->unsignedp)
 930                 top->value = (unsigned HOST_WIDEST_INT) v1 * v2;
 931               else if (!skip_evaluation)
 932                 {
 933                   top->value = v1 * v2;
 934                   if (v1 && (top->value / v1 != v2
 935                              || (top->value & v1 & v2) < 0))
 936                     integer_overflow (pfile);
 937                 }
 938               break;
 939             case CPP_DIV:
 940             case CPP_MOD:
 941               if (skip_evaluation)
 942                 break;
 943               if (v2 == 0)
 944                 SYNTAX_ERROR ("division by zero in #if");
 945               top->unsignedp = unsigned1 | unsigned2;
 946               if (top[1].op == CPP_DIV)
 947                 {
 948                   if (top->unsignedp)
 949                     top->value = (unsigned HOST_WIDEST_INT) v1 / v2;
 950                   else
 951                     {
 952                       top->value = v1 / v2;
 953                       if ((top->value & v1 & v2) < 0)
 954                         integer_overflow (pfile);
 955                     }
 956                 }
 957               else
 958                 {
 959                   if (top->unsignedp)
 960                     top->value = (unsigned HOST_WIDEST_INT) v1 % v2;
 961                   else
 962                     top->value = v1 % v2;
 963                 }
 964               break;
 965
 966             case CPP_OR_OR:
 967               top->value = v1 || v2;
 968               top->unsignedp = 0;
 969               if (v1) skip_evaluation--;
 970               break;
 971             case CPP_AND_AND:
 972               top->value = v1 && v2;
 973               top->unsignedp = 0;
 974               if (!v1) skip_evaluation--;
 975               break;
 976             case CPP_COMMA:
 977               if (CPP_PEDANTIC (pfile))
 978                 cpp_pedwarn (pfile, "comma operator in operand of #if");
 979               top->value = v2;
 980               top->unsignedp = unsigned2;
 981               break;
 982             case CPP_QUERY:
 983               SYNTAX_ERROR ("syntax error '?' without following ':'");
 984             case CPP_COLON:
 985               if (top[0].op != CPP_QUERY)
 986                 SYNTAX_ERROR ("syntax error ':' without preceding '?'");
 987               top--;
 988               if (top->value) skip_evaluation--;
 989               top->value = top->value ? v1 : v2;
 990               top->unsignedp = unsigned1 | unsigned2;
 991               break;
 992             case CPP_OPEN_PAREN:
 993               if (op.op != CPP_CLOSE_PAREN)
 994                 SYNTAX_ERROR ("missing ')' in expression");
 995               op.value = v2;
 996               op.unsignedp = unsigned2;
 997               goto push_immediate;
 998             case CPP_EOF:
 999               /* Reducing this dummy operator indicates we've finished.  */
1000               if (op.op == CPP_CLOSE_PAREN)
1001                 SYNTAX_ERROR ("missing '(' in expression");
1002               goto done;
1003             }
1004         }
1005
1006       /* Handle short-circuit evaluations.  */
1007       if (flags & SHORT_CIRCUIT)
1008         switch (op.op)
1009           {
1010           case CPP_OR_OR:    if (top->value) skip_evaluation++; break;
1011           case CPP_AND_AND:
1012           case CPP_QUERY:    if (!top->value) skip_evaluation++; break;
1013           case CPP_COLON:
1014             if (top[-1].value) /* Was '?' condition true?  */
1015               skip_evaluation++;
1016             else
1017               skip_evaluation--;
1018           default:
1019             break;
1020           }
1021
1022     skip_reduction:
1023       /* Check we have a left operand iff we need one.  */
1024       if (flags & NO_L_OPERAND)
1025         {
1026           if (top->flags & HAVE_VALUE)
1027             SYNTAX_ERROR2 ("missing binary operator before '%s'",
1028                            op_as_text (pfile, top->op));
1029         }
1030       else
1031         {
1032           if (!(top->flags & HAVE_VALUE))
1033             SYNTAX_ERROR2 ("operator '%s' has no left operand",
1034                            op_as_text (pfile, top->op));
1035         }
1036
1037       /* Check for and handle stack overflow.  */
1038       top++;
1039       if (top == limit)
1040         {
1041           struct op *new_stack;
1042           int old_size = (char *) limit - (char *) stack;
1043           int new_size = 2 * old_size;
1044           if (stack != init_stack)
1045             new_stack = (struct op *) xrealloc (stack, new_size);
1046           else
1047             {
1048               new_stack = (struct op *) xmalloc (new_size);
1049               memcpy (new_stack, stack, old_size);
1050             }
1051           stack = new_stack;
1052           top = (struct op *) ((char *) new_stack + old_size);
1053           limit = (struct op *) ((char *) new_stack + new_size);
1054         }
1055
1056       top->flags = flags;
1057       top->prio = prio & ~EXTRACT_PRIO(RIGHT_ASSOC);
1058       top->op = op.op;
1059     }
1060
1061  done:
1062   result = (top[1].value != 0);
1063   if (top != stack)
1064     CPP_ICE ("unbalanced stack in #if");
1065   else if (!(top[1].flags & HAVE_VALUE))
1066     {
1067       SYNTAX_ERROR ("#if with no expression");
1068     syntax_error:
1069       result = 0;  /* Return 0 on syntax error.  */
1070     }
1071
1072   /* Free dynamic stack if we allocated one.  */
1073   if (stack != init_stack)
1074     free (stack);
1075   return result;
1076 }
1077
1078 static const unsigned char *
1079 op_as_text (pfile, op)
1080      cpp_reader *pfile;
1081      enum cpp_ttype op;
1082 {
1083   cpp_token token;
1084
1085   token.type = op;
1086   token.flags = 0;
1087   return cpp_token_as_text (pfile, &token);
1088 }