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