expression.c

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