gcc/cppexp.c

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