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_int_value(struct expression *expr, struct token *token)
  92 {
  93         const char *str = token->integer;
  94         unsigned long long value = 0;
  95         unsigned int base = 10, digit, bits;
  96         unsigned long modifiers, extramod;
  97
  98         switch (str[0]) {
  99         case 'x':
 100                 base = 18;      // the -= 2 for the octal case will
 101                 str++;          // skip the 'x'
 102         /* fallthrough */
 103         case 'o':
 104                 str++;          // skip the 'o' or 'x/X'
 105                 base -= 2;      // the fall-through will make this 8
 106         }
 107         while ((digit = hexval(*str)) < base) {
 108                 value = value * base + digit;
 109                 str++;
 110         }
 111         modifiers = 0;
 112         for (;;) {
 113                 char c = *str++;
 114                 if (c == 'u' || c == 'U') {
 115                         modifiers |= MOD_UNSIGNED;
 116                         continue;
 117                 }
 118                 if (c == 'l' || c == 'L') {
 119                         if (modifiers & MOD_LONG)
 120                                 modifiers |= MOD_LONGLONG;
 121                         modifiers |= MOD_LONG;
 122                         continue;
 123                 }
 124                 break;
 125         }
 126
 127         bits = bits_in_longlong;
 128         extramod = 0;
 129         if (!(modifiers & MOD_LONGLONG)) {
 130                 if (value & (~1ULL << (bits_in_long-1))) {
 131                         extramod = MOD_LONGLONG | MOD_LONG;
 132                 } else {
 133                         bits = bits_in_long;
 134                         if (!(modifiers & MOD_LONG)) {
 135                                 if (value & (~1ULL << (bits_in_int-1))) {
 136                                         extramod = MOD_LONG;
 137                                 } else
 138                                         bits = bits_in_int;
 139                         }
 140                 }
 141         }
 142         if (!(modifiers & MOD_UNSIGNED)) {
 143                 if (value & (1ULL << (bits-1))) {
 144                         extramod |= MOD_UNSIGNED;
 145                 }
 146         }
 147         if (extramod) {
 148                 /*
 149                  * Special case: "int" gets promoted directly to "long"
 150                  * for normal decimal numbers..
 151                  */
 152                 modifiers |= extramod;
 153                 if (base == 10 && modifiers == MOD_UNSIGNED) {
 154                         modifiers = MOD_LONG;
 155                         if (bits_in_long == bits_in_int)
 156                                 modifiers = MOD_LONG | MOD_UNSIGNED;
 157                 }
 158
 159                 /* Hex or octal constants don't complain about missing signedness */
 160                 if (base == 10 || extramod != MOD_UNSIGNED)
 161                         warn(expr->pos, "constant %s is so big it is%s%s%s",
 162                                 show_token(token),
 163                                 (modifiers & MOD_UNSIGNED) ? " unsigned":"",
 164                                 (modifiers & MOD_LONG) ? " long":"",
 165                                 (modifiers & MOD_LONGLONG) ? " long":"");
 166         }
 167
 168         expr->type = EXPR_VALUE;
 169         expr->ctype = ctype_integer(modifiers);
 170         expr->value = value;
 171 }
 172
 173 struct token *primary_expression(struct token *token, struct expression **tree)
 174 {
 175         struct expression *expr = NULL;
 176
 177         switch (token_type(token)) {
 178         static int fp_warned;
 179         case TOKEN_FP:
 180                 expr = alloc_expression(token->pos, EXPR_VALUE);
 181                 expr->ctype = &double_ctype;
 182                 expr->value = 0;
 183                 if (!fp_warned) {
 184                         warn(token->pos, "FP values not yet implemented");
 185                         fp_warned = 1;
 186                 }
 187                 token = token->next;
 188                 break;
 189
 190         case TOKEN_CHAR:
 191                 expr = alloc_expression(token->pos, EXPR_VALUE);
 192                 expr->ctype = &int_ctype;
 193                 expr->value = (unsigned char) token->character;
 194                 token = token->next;
 195                 break;
 196
 197         case TOKEN_INTEGER:
 198                 expr = alloc_expression(token->pos, EXPR_VALUE);
 199                 get_int_value(expr, token);
 200                 token = token->next;
 201                 break;
 202
 203         case TOKEN_IDENT: {
 204                 struct symbol *sym = lookup_symbol(token->ident, NS_SYMBOL | NS_TYPEDEF);
 205                 struct token *next = token->next;
 206
 207                 expr = alloc_expression(token->pos, EXPR_SYMBOL);
 208
 209                 /*
 210                  * We support types as real first-class citizens, with type
 211                  * comparisons etc:
 212                  *
 213                  *      if (typeof(a) == int) ..
 214                  */
 215                 if (sym && sym->namespace == NS_TYPEDEF) {
 216                         warn(token->pos, "typename in expression");
 217                         sym = NULL;
 218                 }
 219                 expr->symbol_name = token->ident;
 220                 expr->symbol = sym;
 221                 token = next;
 222                 break;
 223         }
 224
 225         case TOKEN_STRING: {
 226                 expr = alloc_expression(token->pos, EXPR_STRING);
 227                 token = string_expression(token, expr);
 228                 break;
 229         }
 230
 231         case TOKEN_SPECIAL:
 232                 if (token->special == '(') {
 233                         expr = alloc_expression(token->pos, EXPR_PREOP);
 234                         expr->op = '(';
 235                         token = parens_expression(token, &expr->unop, "in expression");
 236                         break;
 237                 }
 238                 if (token->special == '[' && lookup_type(token->next)) {
 239                         expr = alloc_expression(token->pos, EXPR_TYPE);
 240                         token = typename(token->next, &expr->symbol);
 241                         token = expect(token, ']', "in type expression");
 242                         break;
 243                 }
 244
 245         default:
 246                 ;
 247         }
 248         *tree = expr;
 249         return token;
 250 }
 251
 252 static struct token *expression_list(struct token *token, struct expression_list **list)
 253 {
 254         while (!match_op(token, ')')) {
 255                 struct expression *expr = NULL;
 256                 token = assignment_expression(token, &expr);
 257                 if (!expr)
 258                         break;
 259                 add_expression(list, expr);
 260                 if (!match_op(token, ','))
 261                         break;
 262                 token = token->next;
 263         }
 264         return token;
 265 }
 266
 267 /*
 268  * extend to deal with the ambiguous C grammar for parsing
 269  * a cast expressions followed by an initializer.
 270  */
 271 static struct token *postfix_expression(struct token *token, struct expression **tree, struct expression *cast_init_expr)
 272 {
 273         struct expression *expr = cast_init_expr;
 274
 275         if (!expr)
 276                 token = primary_expression(token, &expr);
 277
 278         while (expr && token_type(token) == TOKEN_SPECIAL) {
 279                 switch (token->special) {
 280                 case '[': {                     /* Array dereference */
 281                         struct expression *deref = alloc_expression(token->pos, EXPR_PREOP);
 282                         struct expression *add = alloc_expression(token->pos, EXPR_BINOP);
 283
 284                         deref->op = '*';
 285                         deref->unop = add;
 286
 287                         add->op = '+';
 288                         add->left = expr;
 289                         token = parse_expression(token->next, &add->right);
 290                         token = expect(token, ']', "at end of array dereference");
 291                         expr = deref;
 292                         continue;
 293                 }
 294                 case SPECIAL_INCREMENT:         /* Post-increment */
 295                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 296                         struct expression *post = alloc_expression(token->pos, EXPR_POSTOP);
 297                         post->op = token->special;
 298                         post->unop = expr;
 299                         expr = post;
 300                         token = token->next;
 301                         continue;
 302                 }
 303                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 304                         /* "x->y" is just shorthand for "(*x).y" */
 305                         struct expression *inner = alloc_expression(token->pos, EXPR_PREOP);
 306                         inner->op = '*';
 307                         inner->unop = expr;
 308                         expr = inner;
 309                 }
 310                 /* Fallthrough!! */
 311                 case '.': {                     /* Structure member dereference */
 312                         struct expression *deref = alloc_expression(token->pos, EXPR_DEREF);
 313                         deref->op = '.';
 314                         deref->deref = expr;
 315                         token = token->next;
 316                         if (token_type(token) != TOKEN_IDENT) {
 317                                 warn(token->pos, "Expected member name");
 318                                 break;
 319                         }
 320                         deref->member = token->ident;
 321                         token = token->next;
 322                         expr = deref;
 323                         continue;
 324                 }
 325
 326                 case '(': {                     /* Function call */
 327                         struct expression *call = alloc_expression(token->pos, EXPR_CALL);
 328                         call->op = '(';
 329                         call->fn = expr;
 330                         token = expression_list(token->next, &call->args);
 331                         token = expect(token, ')', "in function call");
 332                         expr = call;
 333                         continue;
 334                 }
 335
 336                 default:
 337                         break;
 338                 }
 339                 break;
 340         }
 341         *tree = expr;
 342         return token;
 343 }
 344
 345 static struct token *cast_expression(struct token *token, struct expression **tree);
 346 static struct token *unary_expression(struct token *token, struct expression **tree)
 347 {
 348         if (token_type(token) == TOKEN_IDENT &&
 349             (token->ident == &sizeof_ident ||
 350              token->ident == &__alignof___ident)) {
 351                 struct expression *sizeof_ex = alloc_expression(token->pos, EXPR_SIZEOF);
 352                 *tree = sizeof_ex;
 353                 tree = &sizeof_ex->unop;
 354                 token = token->next;
 355                 if (!match_op(token, '(') || !lookup_type(token->next))
 356                         return unary_expression(token, &sizeof_ex->cast_expression);
 357                 token = typename(token->next, &sizeof_ex->cast_type);
 358                 return expect(token, ')', "at end of sizeof type-name");
 359         }
 360
 361         if (token_type(token) == TOKEN_SPECIAL) {
 362                 if (match_oplist(token->special,
 363                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 364                     '&', '*', '+', '-', '~', '!', 0)) {
 365                         struct expression *unary = alloc_expression(token->pos, EXPR_PREOP);
 366                         unary->op = token->special;
 367                         *tree = unary;
 368                         return cast_expression(token->next, &unary->unop);
 369                 }
 370
 371                 /* Gcc extension: &&label gives the address of a label */
 372                 if (match_op(token, SPECIAL_LOGICAL_AND) &&
 373                     token_type(token->next) == TOKEN_IDENT) {
 374                         struct expression *label = alloc_expression(token->pos, EXPR_LABEL);
 375                         label->label_symbol = label_symbol(token->next);
 376                         *tree = label;
 377                         return token->next->next;
 378                 }
 379
 380         }
 381
 382         return postfix_expression(token, tree, NULL);
 383 }
 384
 385 /*
 386  * Ambiguity: a '(' can be either a cast-expression or
 387  * a primary-expression depending on whether it is followed
 388  * by a type or not.
 389  *
 390  * additional ambiguity: a "cast expression" followed by
 391  * an initializer is really a postfix-expression.
 392  */
 393 static struct token *cast_expression(struct token *token, struct expression **tree)
 394 {
 395         if (match_op(token, '(')) {
 396                 struct token *next = token->next;
 397                 if (lookup_type(next)) {
 398                         struct expression *cast = alloc_expression(next->pos, EXPR_CAST);
 399                         struct symbol *sym;
 400
 401                         token = typename(next, &sym);
 402                         cast->cast_type = sym->ctype.base_type;
 403                         token = expect(token, ')', "at end of cast operator");
 404                         if (match_op(token, '{')) {
 405                                 token = initializer(&cast->cast_expression, token);
 406                                 return postfix_expression(token, tree, cast);
 407                         }
 408                         *tree = cast;
 409                         token = cast_expression(token, &cast->cast_expression);
 410                         return token;
 411                 }
 412         }
 413         return unary_expression(token, tree);
 414 }
 415
 416 /* Generic left-to-right binop parsing */
 417 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 418         enum expression_type type, struct token *(*inner)(struct token *, struct expression **), ...)
 419 {
 420         struct expression *left = NULL;
 421         struct token * next = inner(token, &left);
 422
 423         if (left) {
 424                 while (token_type(next) == TOKEN_SPECIAL) {
 425                         struct expression *top, *right = NULL;
 426                         int op = next->special;
 427                         va_list args;
 428
 429                         va_start(args, inner);
 430                         for (;;) {
 431                                 int nextop = va_arg(args, int);
 432                                 if (!nextop)
 433                                         goto out;
 434                                 if (op == nextop)
 435                                         break;
 436                         }
 437                         va_end(args);
 438                         top = alloc_expression(next->pos, type);
 439                         next = inner(next->next, &right);
 440                         if (!right) {
 441                                 warn(next->pos, "No right hand side of '%s'-expression", show_special(op));
 442                                 break;
 443                         }
 444                         top->op = op;
 445                         top->left = left;
 446                         top->right = right;
 447                         left = top;
 448                 }
 449         }
 450 out:
 451         *tree = left;
 452         return next;
 453 }
 454
 455 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 456 {
 457         return lr_binop_expression(token, tree, EXPR_BINOP, cast_expression, '*', '/', '%', 0);
 458 }
 459
 460 static struct token *additive_expression(struct token *token, struct expression **tree)
 461 {
 462         return lr_binop_expression(token, tree, EXPR_BINOP, multiplicative_expression, '+', '-', 0);
 463 }
 464
 465 static struct token *shift_expression(struct token *token, struct expression **tree)
 466 {
 467         return lr_binop_expression(token, tree, EXPR_BINOP, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 468 }
 469
 470 static struct token *relational_expression(struct token *token, struct expression **tree)
 471 {
 472         return lr_binop_expression(token, tree, EXPR_COMPARE, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 473 }
 474
 475 static struct token *equality_expression(struct token *token, struct expression **tree)
 476 {
 477         return lr_binop_expression(token, tree, EXPR_COMPARE, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 478 }
 479
 480 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 481 {
 482         return lr_binop_expression(token, tree, EXPR_BINOP, equality_expression, '&', 0);
 483 }
 484
 485 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 486 {
 487         return lr_binop_expression(token, tree, EXPR_BINOP, bitwise_and_expression, '^', 0);
 488 }
 489
 490 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 491 {
 492         return lr_binop_expression(token, tree, EXPR_BINOP, bitwise_xor_expression, '|', 0);
 493 }
 494
 495 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 496 {
 497         return lr_binop_expression(token, tree, EXPR_LOGICAL, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 498 }
 499
 500 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 501 {
 502         return lr_binop_expression(token, tree, EXPR_LOGICAL, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 503 }
 504
 505 struct token *conditional_expression(struct token *token, struct expression **tree)
 506 {
 507         token = logical_or_expression(token, tree);
 508         if (match_op(token, '?')) {
 509                 struct expression *expr = alloc_expression(token->pos, EXPR_CONDITIONAL);
 510                 expr->op = token->special;
 511                 expr->left = *tree;
 512                 *tree = expr;
 513                 token = parse_expression(token->next, &expr->cond_true);
 514                 token = expect(token, ':', "in conditional expression");
 515                 token = conditional_expression(token, &expr->cond_false);
 516         }
 517         return token;
 518 }
 519
 520 struct token *assignment_expression(struct token *token, struct expression **tree)
 521 {
 522         token = conditional_expression(token, tree);
 523         if (token_type(token) == TOKEN_SPECIAL) {
 524                 static const int assignments[] = {
 525                         '=',
 526                         SPECIAL_ADD_ASSIGN, SPECIAL_SUB_ASSIGN,
 527                         SPECIAL_MUL_ASSIGN, SPECIAL_DIV_ASSIGN,
 528                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 529                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 530                         SPECIAL_OR_ASSIGN,  SPECIAL_XOR_ASSIGN };
 531                 int i, op = token->special;
 532                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 533                         if (assignments[i] == op) {
 534                                 struct expression * expr = alloc_expression(token->pos, EXPR_ASSIGNMENT);
 535                                 expr->left = *tree;
 536                                 expr->op = op;
 537                                 *tree = expr;
 538                                 return assignment_expression(token->next, &expr->right);
 539                         }
 540         }
 541         return token;
 542 }
 543
 544 static struct token *comma_expression(struct token *token, struct expression **tree)
 545 {
 546         return lr_binop_expression(token, tree, EXPR_COMMA, assignment_expression, ',', 0);
 547 }
 548
 549 struct token *parse_expression(struct token *token, struct expression **tree)
 550 {
 551         return comma_expression(token,tree);
 552 }
 553
 554