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