expression.c

   1 /*
   2  * sparse/expression.c
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  * This is the expression parsing part of parsing C.
   9  */
  10 #include <stdarg.h>
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include <string.h>
  14 #include <ctype.h>
  15 #include <unistd.h>
  16 #include <fcntl.h>
  17
  18 #include "lib.h"
  19 #include "token.h"
  20 #include "parse.h"
  21 #include "symbol.h"
  22 #include "scope.h"
  23 #include "expression.h"
  24 #include "target.h"
  25
  26 static int match_oplist(int op, ...)
  27 {
  28         va_list args;
  29
  30         va_start(args, op);
  31         for (;;) {
  32                 int nextop = va_arg(args, int);
  33                 if (!nextop)
  34                         return 0;
  35                 if (op == nextop)
  36                         return 1;
  37         }
  38 }
  39
  40 static struct token *comma_expression(struct token *, struct expression **);
  41
  42 struct token *parens_expression(struct token *token, struct expression **expr, const char *where)
  43 {
  44         token = expect(token, '(', where);
  45         if (match_op(token, '{')) {
  46                 struct expression *e = alloc_expression(token->pos, EXPR_STATEMENT);
  47                 struct statement *stmt = alloc_statement(token->pos, STMT_COMPOUND);
  48                 *expr = e;
  49                 e->statement = stmt;
  50                 start_symbol_scope();
  51                 token = compound_statement(token->next, stmt);
  52                 end_symbol_scope();
  53                 token = expect(token, '}', "at end of statement expression");
  54         } else
  55                 token = parse_expression(token, expr);
  56         return expect(token, ')', where);
  57 }
  58
  59 static struct token *string_expression(struct token *token, struct expression *expr)
  60 {
  61         struct string *string = token->string;
  62         struct token *next = token->next;
  63
  64         if (token_type(next) == TOKEN_STRING) {
  65                 int totlen = string->length;
  66                 char *data;
  67
  68                 do {
  69                         totlen += next->string->length-1;
  70                         next = next->next;
  71                 } while (token_type(next) == TOKEN_STRING);
  72
  73                 string = __alloc_string(totlen);
  74                 string->length = totlen;
  75                 data = string->data;
  76                 next = token;
  77                 do {
  78                         struct string *s = next->string;
  79                         int len = s->length;
  80
  81                         next = next->next;
  82                         memcpy(data, s->data, len);
  83                         data += len-1;
  84                 } while (token_type(next) == TOKEN_STRING);
  85         }
  86         expr->string = string;
  87         return next;
  88 }
  89
  90 static void get_int_value(struct expression *expr, const char *str)
  91 {
  92         unsigned long long value = 0;
  93         unsigned int base = 10, digit, bits;
  94         unsigned long modifiers, extramod;
  95
  96         switch (str[0]) {
  97         case 'x':
  98                 base = 18;      // the -= 2 for the octal case will
  99                 str++;          // skip the 'x'
 100         /* fallthrough */
 101         case 'o':
 102                 str++;          // skip the 'o' or 'x/X'
 103                 base -= 2;      // the fall-through will make this 8
 104         }
 105         while ((digit = hexval(*str)) < base) {
 106                 value = value * base + digit;
 107                 str++;
 108         }
 109         modifiers = 0;
 110         for (;;) {
 111                 char c = *str++;
 112                 if (c == 'u' || c == 'U') {
 113                         modifiers |= MOD_UNSIGNED;
 114                         continue;
 115                 }
 116                 if (c == 'l' || c == 'L') {
 117                         if (modifiers & MOD_LONG)
 118                                 modifiers |= MOD_LONGLONG;
 119                         modifiers |= MOD_LONG;
 120                         continue;
 121                 }
 122                 break;
 123         }
 124
 125         bits = BITS_IN_LONGLONG;
 126         extramod = 0;
 127         if (!(modifiers & MOD_LONGLONG)) {
 128                 if (value & (~1ULL << (BITS_IN_LONG-1))) {
 129                         extramod = MOD_LONGLONG | MOD_LONG;
 130                 } else {
 131                         bits = BITS_IN_LONG;
 132                         if (!(modifiers & MOD_LONG)) {
 133                                 if (value & (~1ULL << (BITS_IN_INT-1))) {
 134                                         extramod = MOD_LONG;
 135                                 } else
 136                                         bits = BITS_IN_INT;
 137                         }
 138                 }
 139         }
 140         if (!(modifiers & MOD_UNSIGNED)) {
 141                 if (value & (1ULL << (bits-1))) {
 142                         extramod |= MOD_UNSIGNED;
 143                 }
 144         }
 145         if (extramod) {
 146                 /*
 147                  * Special case: "int" gets promoted directly to "long"
 148                  * for normal decimal numbers..
 149                  */
 150                 modifiers |= extramod;
 151                 if (base == 10 && modifiers == MOD_UNSIGNED) {
 152                         modifiers = MOD_LONG;
 153                         if (BITS_IN_LONG == BITS_IN_INT)
 154                                 modifiers = MOD_LONG | MOD_UNSIGNED;
 155                 }
 156
 157                 /* Hex or octal constants don't complain about missing signedness */
 158                 if (base == 10 || extramod != MOD_UNSIGNED)
 159                         warn(expr->pos, "value is so big it is%s%s%s",
 160                                 (modifiers & MOD_UNSIGNED) ? " unsigned":"",
 161                                 (modifiers & MOD_LONG) ? " long":"",
 162                                 (modifiers & MOD_LONGLONG) ? " long":"");
 163         }
 164
 165         expr->type = EXPR_VALUE;
 166         expr->ctype = ctype_integer(modifiers);
 167         expr->value = value;
 168 }
 169
 170 struct token *primary_expression(struct token *token, struct expression **tree)
 171 {
 172         struct expression *expr = NULL;
 173
 174         switch (token_type(token)) {
 175         case TOKEN_FP:
 176                 expr = alloc_expression(token->pos, EXPR_VALUE);
 177                 expr->ctype = &double_ctype;
 178                 expr->value = 0;
 179                 warn(token->pos, "FP values not yet implemented");
 180                 token = token->next;
 181                 break;
 182
 183         case TOKEN_CHAR:
 184                 expr = alloc_expression(token->pos, EXPR_VALUE);
 185                 expr->ctype = &int_ctype;
 186                 expr->value = (unsigned char) token->character;
 187                 token = token->next;
 188                 break;
 189
 190         case TOKEN_INTEGER:
 191                 expr = alloc_expression(token->pos, EXPR_VALUE);
 192                 get_int_value(expr, token->integer);
 193                 token = token->next;
 194                 break;
 195
 196         case TOKEN_IDENT: {
 197                 expr = alloc_expression(token->pos, EXPR_SYMBOL);
 198                 expr->symbol_name = token->ident;
 199                 expr->symbol = lookup_symbol(token->ident, NS_SYMBOL);
 200                 token = token->next;
 201                 break;
 202         }
 203
 204         case TOKEN_STRING: {
 205                 expr = alloc_expression(token->pos, EXPR_STRING);
 206                 token = string_expression(token, expr);
 207                 break;
 208         }
 209
 210         case TOKEN_SPECIAL:
 211                 if (token->special == '(') {
 212                         expr = alloc_expression(token->pos, EXPR_PREOP);
 213                         expr->op = '(';
 214                         token = parens_expression(token, &expr->unop, "in expression");
 215                         break;
 216                 }
 217         default:
 218                 ;
 219         }
 220         *tree = expr;
 221         return token;
 222 }
 223
 224 static struct token *expression_list(struct token *token, struct expression_list **list)
 225 {
 226         while (!match_op(token, ')')) {
 227                 struct expression *expr = NULL;
 228                 token = assignment_expression(token, &expr);
 229                 if (!expr)
 230                         break;
 231                 add_expression(list, expr);
 232                 if (!match_op(token, ','))
 233                         break;
 234                 token = token->next;
 235         }
 236         return token;
 237 }
 238
 239 static struct token *postfix_expression(struct token *token, struct expression **tree)
 240 {
 241         struct expression *expr = NULL;
 242
 243         token = primary_expression(token, &expr);
 244         while (expr && token_type(token) == TOKEN_SPECIAL) {
 245                 switch (token->special) {
 246                 case '[': {                     /* Array dereference */
 247                         struct expression *deref = alloc_expression(token->pos, EXPR_PREOP);
 248                         struct expression *add = alloc_expression(token->pos, EXPR_BINOP);
 249
 250                         deref->op = '*';
 251                         deref->unop = add;
 252
 253                         add->op = '+';
 254                         add->left = expr;
 255                         token = parse_expression(token->next, &add->right);
 256                         token = expect(token, ']', "at end of array dereference");
 257                         expr = deref;
 258                         continue;
 259                 }
 260                 case SPECIAL_INCREMENT:         /* Post-increment */
 261                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 262                         struct expression *post = alloc_expression(token->pos, EXPR_POSTOP);
 263                         post->op = token->special;
 264                         post->unop = expr;
 265                         expr = post;
 266                         token = token->next;
 267                         continue;
 268                 }
 269                 case '.':                       /* Structure member dereference */
 270                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 271                         struct expression *deref = alloc_expression(token->pos, EXPR_DEREF);
 272                         deref->op = token->special;
 273                         deref->deref = expr;
 274                         token = token->next;
 275                         if (token_type(token) != TOKEN_IDENT) {
 276                                 warn(token->pos, "Expected member name");
 277                                 break;
 278                         }
 279                         deref->member = token->ident;
 280                         token = token->next;
 281                         expr = deref;
 282                         continue;
 283                 }
 284
 285                 case '(': {                     /* Function call */
 286                         struct expression *call = alloc_expression(token->pos, EXPR_CALL);
 287                         call->op = '(';
 288                         call->fn = expr;
 289                         token = expression_list(token->next, &call->args);
 290                         token = expect(token, ')', "in function call");
 291                         expr = call;
 292                         continue;
 293                 }
 294
 295                 default:
 296                         break;
 297                 }
 298                 break;
 299         }
 300         *tree = expr;
 301         return token;
 302 }
 303
 304 static struct token *cast_expression(struct token *token, struct expression **tree);
 305 static struct token *unary_expression(struct token *token, struct expression **tree)
 306 {
 307         if (token_type(token) == TOKEN_IDENT &&
 308             (token->ident == &sizeof_ident ||
 309              token->ident == &__alignof___ident)) {
 310                 struct expression *sizeof_ex = alloc_expression(token->pos, EXPR_SIZEOF);
 311                 *tree = sizeof_ex;
 312                 tree = &sizeof_ex->unop;
 313                 token = token->next;
 314                 if (!match_op(token, '(') || !lookup_type(token->next))
 315                         return unary_expression(token, &sizeof_ex->cast_expression);
 316                 token = typename(token->next, &sizeof_ex->cast_type);
 317                 return expect(token, ')', "at end of sizeof type-name");
 318         }
 319
 320         if (token_type(token) == TOKEN_SPECIAL) {
 321                 if (match_oplist(token->special,
 322                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 323                     '&', '*', '+', '-', '~', '!', 0)) {
 324                         struct expression *unary = alloc_expression(token->pos, EXPR_PREOP);
 325                         unary->op = token->special;
 326                         *tree = unary;
 327                         return cast_expression(token->next, &unary->unop);
 328                 }
 329
 330                 /* Gcc extension: &&label gives the address of a label */
 331                 if (match_op(token, SPECIAL_LOGICAL_AND) &&
 332                     token_type(token->next) == TOKEN_IDENT) {
 333                         struct expression *label = alloc_expression(token->pos, EXPR_LABEL);
 334                         label->label_symbol = label_symbol(token->next);
 335                         *tree = label;
 336                         return token->next->next;
 337                 }
 338
 339         }
 340
 341         return postfix_expression(token, tree);
 342 }
 343
 344 /*
 345  * Ambiguity: a '(' can be either a cast-expression or
 346  * a primary-expression depending on whether it is followed
 347  * by a type or not.
 348  */
 349 static struct token *cast_expression(struct token *token, struct expression **tree)
 350 {
 351         if (match_op(token, '(')) {
 352                 struct token *next = token->next;
 353                 if (lookup_type(next)) {
 354                         struct expression *cast = alloc_expression(next->pos, EXPR_CAST);
 355                         struct symbol *sym;
 356
 357                         token = typename(next, &sym);
 358                         cast->cast_type = sym->ctype.base_type;
 359                         token = expect(token, ')', "at end of cast operator");
 360                         *tree = cast;
 361                         if (match_op(token, '{'))
 362                                 return initializer(&cast->cast_expression, token);
 363                         token = cast_expression(token, &cast->cast_expression);
 364                         return token;
 365                 }
 366         }
 367         return unary_expression(token, tree);
 368 }
 369
 370 /* Generic left-to-right binop parsing */
 371 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 372         enum expression_type type, struct token *(*inner)(struct token *, struct expression **), ...)
 373 {
 374         struct expression *left = NULL;
 375         struct token * next = inner(token, &left);
 376
 377         if (left) {
 378                 while (token_type(next) == TOKEN_SPECIAL) {
 379                         struct expression *top, *right = NULL;
 380                         int op = next->special;
 381                         va_list args;
 382
 383                         va_start(args, inner);
 384                         for (;;) {
 385                                 int nextop = va_arg(args, int);
 386                                 if (!nextop)
 387                                         goto out;
 388                                 if (op == nextop)
 389                                         break;
 390                         }
 391                         va_end(args);
 392                         top = alloc_expression(next->pos, type);
 393                         next = inner(next->next, &right);
 394                         if (!right) {
 395                                 warn(next->pos, "No right hand side of '%s'-expression", show_special(op));
 396                                 break;
 397                         }
 398                         top->op = op;
 399                         top->left = left;
 400                         top->right = right;
 401                         left = top;
 402                 }
 403         }
 404 out:
 405         *tree = left;
 406         return next;
 407 }
 408
 409 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 410 {
 411         return lr_binop_expression(token, tree, EXPR_BINOP, cast_expression, '*', '/', '%', 0);
 412 }
 413
 414 static struct token *additive_expression(struct token *token, struct expression **tree)
 415 {
 416         return lr_binop_expression(token, tree, EXPR_BINOP, multiplicative_expression, '+', '-', 0);
 417 }
 418
 419 static struct token *shift_expression(struct token *token, struct expression **tree)
 420 {
 421         return lr_binop_expression(token, tree, EXPR_BINOP, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 422 }
 423
 424 static struct token *relational_expression(struct token *token, struct expression **tree)
 425 {
 426         return lr_binop_expression(token, tree, EXPR_COMPARE, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 427 }
 428
 429 static struct token *equality_expression(struct token *token, struct expression **tree)
 430 {
 431         return lr_binop_expression(token, tree, EXPR_COMPARE, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 432 }
 433
 434 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 435 {
 436         return lr_binop_expression(token, tree, EXPR_BINOP, equality_expression, '&', 0);
 437 }
 438
 439 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 440 {
 441         return lr_binop_expression(token, tree, EXPR_BINOP, bitwise_and_expression, '^', 0);
 442 }
 443
 444 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 445 {
 446         return lr_binop_expression(token, tree, EXPR_BINOP, bitwise_xor_expression, '|', 0);
 447 }
 448
 449 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 450 {
 451         return lr_binop_expression(token, tree, EXPR_LOGICAL, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 452 }
 453
 454 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 455 {
 456         return lr_binop_expression(token, tree, EXPR_LOGICAL, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 457 }
 458
 459 struct token *conditional_expression(struct token *token, struct expression **tree)
 460 {
 461         token = logical_or_expression(token, tree);
 462         if (match_op(token, '?')) {
 463                 struct expression *expr = alloc_expression(token->pos, EXPR_CONDITIONAL);
 464                 expr->op = token->special;
 465                 expr->left = *tree;
 466                 *tree = expr;
 467                 token = parse_expression(token->next, &expr->cond_true);
 468                 token = expect(token, ':', "in conditional expression");
 469                 token = conditional_expression(token, &expr->cond_false);
 470         }
 471         return token;
 472 }
 473
 474 struct token *assignment_expression(struct token *token, struct expression **tree)
 475 {
 476         token = conditional_expression(token, tree);
 477         if (token_type(token) == TOKEN_SPECIAL) {
 478                 static const int assignments[] = {
 479                         '=',
 480                         SPECIAL_ADD_ASSIGN, SPECIAL_SUB_ASSIGN,
 481                         SPECIAL_MUL_ASSIGN, SPECIAL_DIV_ASSIGN,
 482                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 483                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 484                         SPECIAL_OR_ASSIGN,  SPECIAL_XOR_ASSIGN };
 485                 int i, op = token->special;
 486                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 487                         if (assignments[i] == op) {
 488                                 struct expression * expr = alloc_expression(token->pos, EXPR_ASSIGNMENT);
 489                                 expr->left = *tree;
 490                                 expr->op = op;
 491                                 *tree = expr;
 492                                 return assignment_expression(token->next, &expr->right);
 493                         }
 494         }
 495         return token;
 496 }
 497
 498 static struct token *comma_expression(struct token *token, struct expression **tree)
 499 {
 500         return lr_binop_expression(token, tree, EXPR_COMMA, assignment_expression, ',', 0);
 501 }
 502
 503 struct token *parse_expression(struct token *token, struct expression **tree)
 504 {
 505         return comma_expression(token,tree);
 506 }
 507
 508