expression.c

   1 /*
   2  * sparse/expression.c
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003 Linus Torvalds
   6  *
   7  *  Licensed under the Open Software License version 1.1
   8  *
   9  * This is the expression parsing part of parsing C.
  10  */
  11 #include <stdarg.h>
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <ctype.h>
  16 #include <unistd.h>
  17 #include <fcntl.h>
  18 #include <errno.h>
  19 #include <limits.h>
  20
  21 #include "lib.h"
  22 #include "token.h"
  23 #include "parse.h"
  24 #include "symbol.h"
  25 #include "scope.h"
  26 #include "expression.h"
  27 #include "target.h"
  28
  29 static int match_oplist(int op, ...)
  30 {
  31         va_list args;
  32
  33         va_start(args, op);
  34         for (;;) {
  35                 int nextop = va_arg(args, int);
  36                 if (!nextop)
  37                         return 0;
  38                 if (op == nextop)
  39                         return 1;
  40         }
  41 }
  42
  43 static struct token *comma_expression(struct token *, struct expression **);
  44
  45 struct token *parens_expression(struct token *token, struct expression **expr, const char *where)
  46 {
  47         token = expect(token, '(', where);
  48         if (match_op(token, '{')) {
  49                 struct expression *e = alloc_expression(token->pos, EXPR_STATEMENT);
  50                 struct statement *stmt = alloc_statement(token->pos, STMT_COMPOUND);
  51                 *expr = e;
  52                 e->statement = stmt;
  53                 start_symbol_scope();
  54                 token = compound_statement(token->next, stmt);
  55                 end_symbol_scope();
  56                 token = expect(token, '}', "at end of statement expression");
  57         } else
  58                 token = parse_expression(token, expr);
  59         return expect(token, ')', where);
  60 }
  61
  62 static struct token *string_expression(struct token *token, struct expression *expr)
  63 {
  64         struct string *string = token->string;
  65         struct token *next = token->next;
  66
  67         if (token_type(next) == TOKEN_STRING) {
  68                 int totlen = string->length-1;
  69                 char *data;
  70
  71                 do {
  72                         totlen += next->string->length-1;
  73                         next = next->next;
  74                 } while (token_type(next) == TOKEN_STRING);
  75
  76                 if (totlen > MAX_STRING) {
  77                         warn(token->pos, "trying to concatenate %d-character string (%d bytes max)", totlen, MAX_STRING);
  78                         totlen = MAX_STRING;
  79                 }
  80
  81                 string = __alloc_string(totlen+1);
  82                 string->length = totlen+1;
  83                 data = string->data;
  84                 next = token;
  85                 do {
  86                         struct string *s = next->string;
  87                         int len = s->length-1;
  88
  89                         if (len > totlen)
  90                                 len = totlen;
  91                         totlen -= len;
  92
  93                         next = next->next;
  94                         memcpy(data, s->data, len);
  95                         data += len;
  96                 } while (token_type(next) == TOKEN_STRING);
  97                 *data = '\0';
  98         }
  99         expr->string = string;
 100         return next;
 101 }
 102
 103 static void get_fp_value(struct expression *expr, struct token *token)
 104 {
 105         static int fp_warned;
 106
 107         expr->ctype = &double_ctype;
 108         expr->value = 0;
 109         if (!fp_warned) {
 110                 warn(token->pos, "FP values not yet implemented");
 111                 fp_warned = 1;
 112         }
 113 }
 114
 115 #ifndef ULLONG_MAX
 116 #define ULLONG_MAX (~0ULL)
 117 #endif
 118
 119 static void get_number_value(struct expression *expr, struct token *token)
 120 {
 121         const char *str = token->number;
 122         unsigned long long value;
 123         char *end;
 124         unsigned long modifiers = 0;
 125         int overflow = 0, do_warn = 0;
 126         int try_unsigned = 1;
 127         int bits;
 128
 129         errno = 0;
 130         value = strtoull(str, &end, 0);
 131         if (end == str)
 132                 goto Enoint;
 133         if (value == ULLONG_MAX && errno == ERANGE)
 134                 overflow = 1;
 135         while (1) {
 136                 unsigned long added;
 137                 char c = *end++;
 138                 if (!c) {
 139                         break;
 140                 } else if (c == 'u' || c == 'U') {
 141                         added = MOD_UNSIGNED;
 142                 } else if (c == 'l' || c == 'L') {
 143                         added = MOD_LONG;
 144                         if (*end == c) {
 145                                 added |= MOD_LONGLONG;
 146                                 end++;
 147                         }
 148                 } else
 149                         goto Enoint;
 150                 if (modifiers & added)
 151                         goto Enoint;
 152                 modifiers |= added;
 153         }
 154         if (overflow)
 155                 goto Eoverflow;
 156         /* OK, it's a valid integer */
 157         /* decimals can be unsigned only if directly specified as such */
 158         if (str[0] != '0' && !(modifiers & MOD_UNSIGNED))
 159                 try_unsigned = 0;
 160         if (!(modifiers & MOD_LONG)) {
 161                 bits = bits_in_int - 1;
 162                 if (!(value & (~1ULL << bits))) {
 163                         if (!(value & (1ULL << bits))) {
 164                                 goto got_it;
 165                         } else if (try_unsigned) {
 166                                 modifiers |= MOD_UNSIGNED;
 167                                 goto got_it;
 168                         }
 169                 }
 170                 modifiers |= MOD_LONG;
 171                 do_warn = 1;
 172         }
 173         if (!(modifiers & MOD_LONGLONG)) {
 174                 bits = bits_in_long - 1;
 175                 if (!(value & (~1ULL << bits))) {
 176                         if (!(value & (1ULL << bits))) {
 177                                 goto got_it;
 178                         } else if (try_unsigned) {
 179                                 modifiers |= MOD_UNSIGNED;
 180                                 goto got_it;
 181                         }
 182                         do_warn |= 2;
 183                 }
 184                 modifiers |= MOD_LONGLONG;
 185                 do_warn |= 1;
 186         }
 187         bits = bits_in_longlong - 1;
 188         if (value & (~1ULL << bits))
 189                 goto Eoverflow;
 190         if (!(value & (1ULL << bits)))
 191                 goto got_it;
 192         if (!try_unsigned)
 193                 warn(expr->pos, "decimal constant %s is too big for long long",
 194                         show_token(token));
 195         modifiers |= MOD_UNSIGNED;
 196 got_it:
 197         if (do_warn)
 198                 warn(expr->pos, "constant %s is so big it is%s%s%s",
 199                         show_token(token),
 200                         (modifiers & MOD_UNSIGNED) ? " unsigned":"",
 201                         (modifiers & MOD_LONG) ? " long":"",
 202                         (modifiers & MOD_LONGLONG) ? " long":"");
 203         if (do_warn & 2)
 204                 warn(expr->pos,
 205                         "decimal constant %s is between LONG_MAX and ULONG_MAX."
 206                         " For C99 that means long long, C90 compilers are very "
 207                         "likely to produce unsigned long (and a warning) here",
 208                         show_token(token));
 209         expr->type = EXPR_VALUE;
 210         expr->ctype = ctype_integer(modifiers);
 211         expr->value = value;
 212         return;
 213 Eoverflow:
 214         error(expr->pos, "constant %s is too big even for unsigned long long",
 215                         show_token(token));
 216 Enoint:
 217         get_fp_value(expr, token);
 218 }
 219
 220 struct token *primary_expression(struct token *token, struct expression **tree)
 221 {
 222         struct expression *expr = NULL;
 223
 224         switch (token_type(token)) {
 225         case TOKEN_CHAR:
 226                 expr = alloc_expression(token->pos, EXPR_VALUE);
 227                 expr->ctype = &int_ctype;
 228                 expr->value = (unsigned char) token->character;
 229                 token = token->next;
 230                 break;
 231
 232         case TOKEN_NUMBER:
 233                 expr = alloc_expression(token->pos, EXPR_VALUE);
 234                 get_number_value(expr, token);
 235                 token = token->next;
 236                 break;
 237
 238         case TOKEN_IDENT: {
 239                 struct symbol *sym = lookup_symbol(token->ident, NS_SYMBOL | NS_TYPEDEF);
 240                 struct token *next = token->next;
 241
 242                 expr = alloc_expression(token->pos, EXPR_SYMBOL);
 243
 244                 /*
 245                  * We support types as real first-class citizens, with type
 246                  * comparisons etc:
 247                  *
 248                  *      if (typeof(a) == int) ..
 249                  */
 250                 if (sym && sym->namespace == NS_TYPEDEF) {
 251                         warn(token->pos, "typename in expression");
 252                         sym = NULL;
 253                 }
 254                 expr->symbol_name = token->ident;
 255                 expr->symbol = sym;
 256                 token = next;
 257                 break;
 258         }
 259
 260         case TOKEN_STRING: {
 261                 expr = alloc_expression(token->pos, EXPR_STRING);
 262                 token = string_expression(token, expr);
 263                 break;
 264         }
 265
 266         case TOKEN_SPECIAL:
 267                 if (token->special == '(') {
 268                         expr = alloc_expression(token->pos, EXPR_PREOP);
 269                         expr->op = '(';
 270                         token = parens_expression(token, &expr->unop, "in expression");
 271                         break;
 272                 }
 273                 if (token->special == '[' && lookup_type(token->next)) {
 274                         expr = alloc_expression(token->pos, EXPR_TYPE);
 275                         token = typename(token->next, &expr->symbol);
 276                         token = expect(token, ']', "in type expression");
 277                         break;
 278                 }
 279
 280         default:
 281                 ;
 282         }
 283         *tree = expr;
 284         return token;
 285 }
 286
 287 static struct token *expression_list(struct token *token, struct expression_list **list)
 288 {
 289         while (!match_op(token, ')')) {
 290                 struct expression *expr = NULL;
 291                 token = assignment_expression(token, &expr);
 292                 if (!expr)
 293                         break;
 294                 add_expression(list, expr);
 295                 if (!match_op(token, ','))
 296                         break;
 297                 token = token->next;
 298         }
 299         return token;
 300 }
 301
 302 /*
 303  * extend to deal with the ambiguous C grammar for parsing
 304  * a cast expressions followed by an initializer.
 305  */
 306 static struct token *postfix_expression(struct token *token, struct expression **tree, struct expression *cast_init_expr)
 307 {
 308         struct expression *expr = cast_init_expr;
 309
 310         if (!expr)
 311                 token = primary_expression(token, &expr);
 312
 313         while (expr && token_type(token) == TOKEN_SPECIAL) {
 314                 switch (token->special) {
 315                 case '[': {                     /* Array dereference */
 316                         struct expression *deref = alloc_expression(token->pos, EXPR_PREOP);
 317                         struct expression *add = alloc_expression(token->pos, EXPR_BINOP);
 318
 319                         deref->op = '*';
 320                         deref->unop = add;
 321
 322                         add->op = '+';
 323                         add->left = expr;
 324                         token = parse_expression(token->next, &add->right);
 325                         token = expect(token, ']', "at end of array dereference");
 326                         expr = deref;
 327                         continue;
 328                 }
 329                 case SPECIAL_INCREMENT:         /* Post-increment */
 330                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 331                         struct expression *post = alloc_expression(token->pos, EXPR_POSTOP);
 332                         post->op = token->special;
 333                         post->unop = expr;
 334                         expr = post;
 335                         token = token->next;
 336                         continue;
 337                 }
 338                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 339                         /* "x->y" is just shorthand for "(*x).y" */
 340                         struct expression *inner = alloc_expression(token->pos, EXPR_PREOP);
 341                         inner->op = '*';
 342                         inner->unop = expr;
 343                         expr = inner;
 344                 }
 345                 /* Fallthrough!! */
 346                 case '.': {                     /* Structure member dereference */
 347                         struct expression *deref = alloc_expression(token->pos, EXPR_DEREF);
 348                         deref->op = '.';
 349                         deref->deref = expr;
 350                         token = token->next;
 351                         if (token_type(token) != TOKEN_IDENT) {
 352                                 warn(token->pos, "Expected member name");
 353                                 break;
 354                         }
 355                         deref->member = token->ident;
 356                         token = token->next;
 357                         expr = deref;
 358                         continue;
 359                 }
 360
 361                 case '(': {                     /* Function call */
 362                         struct expression *call = alloc_expression(token->pos, EXPR_CALL);
 363                         call->op = '(';
 364                         call->fn = expr;
 365                         token = expression_list(token->next, &call->args);
 366                         token = expect(token, ')', "in function call");
 367                         expr = call;
 368                         continue;
 369                 }
 370
 371                 default:
 372                         break;
 373                 }
 374                 break;
 375         }
 376         *tree = expr;
 377         return token;
 378 }
 379
 380 static struct token *cast_expression(struct token *token, struct expression **tree);
 381 static struct token *unary_expression(struct token *token, struct expression **tree)
 382 {
 383         if (token_type(token) == TOKEN_IDENT) {
 384                 if (token->ident == &sizeof_ident) {
 385                         struct expression *sizeof_ex
 386                                 = alloc_expression(token->pos, EXPR_SIZEOF);
 387                         *tree = sizeof_ex;
 388                         tree = &sizeof_ex->unop;
 389                         token = token->next;
 390                         if (!match_op(token, '(') || !lookup_type(token->next))
 391                                 return unary_expression(token, &sizeof_ex->cast_expression);
 392                         token = typename(token->next, &sizeof_ex->cast_type);
 393                         return expect(token, ')', "at end of sizeof type-name");
 394                 } else if (token->ident == &__alignof___ident) {
 395                         struct expression *alignof_ex
 396                                 = alloc_expression(token->pos, EXPR_ALIGNOF);
 397                         *tree = alignof_ex;
 398                         tree = &alignof_ex->unop;
 399                         token = token->next;
 400                         if (!match_op(token, '(') || !lookup_type(token->next))
 401                                 return unary_expression(token, &alignof_ex->cast_expression);
 402                         token = typename(token->next, &alignof_ex->cast_type);
 403                         return expect(token, ')', "at end of alignof type-name");
 404                 }
 405         }
 406
 407         if (token_type(token) == TOKEN_SPECIAL) {
 408                 if (match_oplist(token->special,
 409                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 410                     '&', '*', '+', '-', '~', '!', 0)) {
 411                         struct expression *unop;
 412                         struct expression *unary;
 413                         struct token *next;
 414
 415                         next = cast_expression(token->next, &unop);
 416                         if (!unop) {
 417                                 warn(token->pos, "Syntax error in unary expression");
 418                                 return next;
 419                         }
 420                         unary = alloc_expression(token->pos, EXPR_PREOP);
 421                         unary->op = token->special;
 422                         unary->unop = unop;
 423                         *tree = unary;
 424                         return next;
 425                 }
 426
 427                 /* Gcc extension: &&label gives the address of a label */
 428                 if (match_op(token, SPECIAL_LOGICAL_AND) &&
 429                     token_type(token->next) == TOKEN_IDENT) {
 430                         struct expression *label = alloc_expression(token->pos, EXPR_LABEL);
 431                         label->label_symbol = label_symbol(token->next);
 432                         *tree = label;
 433                         return token->next->next;
 434                 }
 435
 436         }
 437
 438         return postfix_expression(token, tree, NULL);
 439 }
 440
 441 /*
 442  * Ambiguity: a '(' can be either a cast-expression or
 443  * a primary-expression depending on whether it is followed
 444  * by a type or not.
 445  *
 446  * additional ambiguity: a "cast expression" followed by
 447  * an initializer is really a postfix-expression.
 448  */
 449 static struct token *cast_expression(struct token *token, struct expression **tree)
 450 {
 451         if (match_op(token, '(')) {
 452                 struct token *next = token->next;
 453                 if (lookup_type(next)) {
 454                         struct expression *cast = alloc_expression(next->pos, EXPR_CAST);
 455                         struct symbol *sym;
 456
 457                         token = typename(next, &sym);
 458                         cast->cast_type = sym;
 459                         token = expect(token, ')', "at end of cast operator");
 460                         if (match_op(token, '{')) {
 461                                 token = initializer(&cast->cast_expression, token);
 462                                 return postfix_expression(token, tree, cast);
 463                         }
 464                         *tree = cast;
 465                         token = cast_expression(token, &cast->cast_expression);
 466                         return token;
 467                 }
 468         }
 469         return unary_expression(token, tree);
 470 }
 471
 472 /*
 473  * Generic left-to-right binop parsing
 474  *
 475  * This _really_ needs to be inlined, because that makes the inner
 476  * function call statically deterministic rather than a totally
 477  * unpredictable indirect call. But gcc-3 is so "clever" that it
 478  * doesn't do so by default even when you tell it to inline it.
 479  *
 480  * Making it a macro avoids the inlining problem, and also means
 481  * that we can pass in the op-comparison as an expression rather
 482  * than create a data structure for it.
 483  */
 484
 485 #define LR_BINOP_EXPRESSION(token, tree, type, inner, compare)          \
 486         struct expression *left = NULL;                                 \
 487         struct token * next = inner(token, &left);                      \
 488                                                                         \
 489         if (left) {                                                     \
 490                 while (token_type(next) == TOKEN_SPECIAL) {             \
 491                         struct expression *top, *right = NULL;          \
 492                         int op = next->special;                         \
 493                                                                         \
 494                         if (!(compare))                                 \
 495                                 goto out;                               \
 496                         top = alloc_expression(next->pos, type);        \
 497                         next = inner(next->next, &right);               \
 498                         if (!right) {                                   \
 499                                 warn(next->pos, "No right hand side of '%s'-expression", show_special(op));     \
 500                                 break;                                  \
 501                         }                                               \
 502                         top->op = op;                                   \
 503                         top->left = left;                               \
 504                         top->right = right;                             \
 505                         left = top;                                     \
 506                 }                                                       \
 507         }                                                               \
 508 out:                                                                    \
 509         *tree = left;                                                   \
 510         return next;                                                    \
 511
 512
 513 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 514 {
 515         LR_BINOP_EXPRESSION(
 516                 token, tree, EXPR_BINOP, cast_expression,
 517                 (op == '*') || (op == '/') || (op == '%')
 518         );
 519 }
 520
 521 static struct token *additive_expression(struct token *token, struct expression **tree)
 522 {
 523         LR_BINOP_EXPRESSION(
 524                 token, tree, EXPR_BINOP, multiplicative_expression,
 525                 (op == '+') || (op == '-')
 526         );
 527 }
 528
 529 static struct token *shift_expression(struct token *token, struct expression **tree)
 530 {
 531         LR_BINOP_EXPRESSION(
 532                 token, tree, EXPR_BINOP, additive_expression,
 533                 (op == SPECIAL_LEFTSHIFT) || (op == SPECIAL_RIGHTSHIFT)
 534         );
 535 }
 536
 537 static struct token *relational_expression(struct token *token, struct expression **tree)
 538 {
 539         LR_BINOP_EXPRESSION(
 540                 token, tree, EXPR_COMPARE, shift_expression,
 541                 (op == '<') || (op == '>') ||
 542                 (op == SPECIAL_LTE) || (op == SPECIAL_GTE)
 543         );
 544 }
 545
 546 static struct token *equality_expression(struct token *token, struct expression **tree)
 547 {
 548         LR_BINOP_EXPRESSION(
 549                 token, tree, EXPR_COMPARE, relational_expression,
 550                 (op == SPECIAL_EQUAL) || (op == SPECIAL_NOTEQUAL)
 551         );
 552 }
 553
 554 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 555 {
 556         LR_BINOP_EXPRESSION(
 557                 token, tree, EXPR_BINOP, equality_expression,
 558                 (op == '&')
 559         );
 560 }
 561
 562 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 563 {
 564         LR_BINOP_EXPRESSION(
 565                 token, tree, EXPR_BINOP, bitwise_and_expression,
 566                 (op == '^')
 567         );
 568 }
 569
 570 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 571 {
 572         LR_BINOP_EXPRESSION(
 573                 token, tree, EXPR_BINOP, bitwise_xor_expression,
 574                 (op == '|')
 575         );
 576 }
 577
 578 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 579 {
 580         LR_BINOP_EXPRESSION(
 581                 token, tree, EXPR_LOGICAL, bitwise_or_expression,
 582                 (op == SPECIAL_LOGICAL_AND)
 583         );
 584 }
 585
 586 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 587 {
 588         LR_BINOP_EXPRESSION(
 589                 token, tree, EXPR_LOGICAL, logical_and_expression,
 590                 (op == SPECIAL_LOGICAL_OR)
 591         );
 592 }
 593
 594 struct token *conditional_expression(struct token *token, struct expression **tree)
 595 {
 596         token = logical_or_expression(token, tree);
 597         if (match_op(token, '?')) {
 598                 struct expression *expr = alloc_expression(token->pos, EXPR_CONDITIONAL);
 599                 expr->op = token->special;
 600                 expr->left = *tree;
 601                 *tree = expr;
 602                 token = parse_expression(token->next, &expr->cond_true);
 603                 token = expect(token, ':', "in conditional expression");
 604                 token = conditional_expression(token, &expr->cond_false);
 605         }
 606         return token;
 607 }
 608
 609 struct token *assignment_expression(struct token *token, struct expression **tree)
 610 {
 611         token = conditional_expression(token, tree);
 612         if (token_type(token) == TOKEN_SPECIAL) {
 613                 static const int assignments[] = {
 614                         '=',
 615                         SPECIAL_ADD_ASSIGN, SPECIAL_SUB_ASSIGN,
 616                         SPECIAL_MUL_ASSIGN, SPECIAL_DIV_ASSIGN,
 617                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 618                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 619                         SPECIAL_OR_ASSIGN,  SPECIAL_XOR_ASSIGN };
 620                 int i, op = token->special;
 621                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 622                         if (assignments[i] == op) {
 623                                 struct expression * expr = alloc_expression(token->pos, EXPR_ASSIGNMENT);
 624                                 expr->left = *tree;
 625                                 expr->op = op;
 626                                 *tree = expr;
 627                                 return assignment_expression(token->next, &expr->right);
 628                         }
 629         }
 630         return token;
 631 }
 632
 633 static struct token *comma_expression(struct token *token, struct expression **tree)
 634 {
 635         LR_BINOP_EXPRESSION(
 636                 token, tree, EXPR_COMMA, assignment_expression,
 637                 (op == ',')
 638         );
 639 }
 640
 641 struct token *parse_expression(struct token *token, struct expression **tree)
 642 {
 643         return comma_expression(token,tree);
 644 }
 645
 646