dissect.c

   1 /*
   2  * sparse/dissect.c
   3  *
   4  * Started by Oleg Nesterov <oleg@tv-sign.ru>
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  */
   8
   9 #include "dissect.h"
  10
  11 #define U_VOID   0x00
  12 #define U_SELF  ((1 << U_SHIFT) - 1)
  13 #define U_MASK  (U_R_VAL | U_W_VAL | U_R_AOF)
  14
  15 #define DO_LIST(l__, p__, expr__)               \
  16         do {                                    \
  17                 typeof(l__->list[0]) p__;       \
  18                 FOR_EACH_PTR(l__, p__)          \
  19                         expr__;                 \
  20                 END_FOR_EACH_PTR(p__);          \
  21         } while (0)
  22
  23 #define DO_2_LIST(l1__,l2__, p1__,p2__, expr__) \
  24         do {                                    \
  25                 typeof(l1__->list[0]) p1__;     \
  26                 typeof(l2__->list[0]) p2__;     \
  27                 PREPARE_PTR_LIST(l1__, p1__);   \
  28                 FOR_EACH_PTR(l2__, p2__)        \
  29                         expr__;                 \
  30                         NEXT_PTR_LIST(p1__);    \
  31                 END_FOR_EACH_PTR(p2__);         \
  32                 FINISH_PTR_LIST(p1__);          \
  33         } while (0)
  34
  35
  36 typedef unsigned usage_t;
  37
  38 static struct reporter *reporter;
  39 static struct symbol *return_type;
  40
  41 static void do_sym_list(struct symbol_list *list);
  42
  43 static struct symbol
  44         *base_type(struct symbol *sym),
  45         *do_initializer(struct symbol *type, struct expression* expr),
  46         *do_expression(usage_t mode, struct expression *expr),
  47         *do_statement(usage_t mode, struct statement *stmt);
  48
  49 static inline int is_ptr(struct symbol *type)
  50 {
  51         return type->type == SYM_PTR || type->type == SYM_ARRAY;
  52 }
  53
  54 static inline usage_t u_rval(usage_t mode)
  55 {
  56         return mode & (U_R_VAL | (U_MASK << U_SHIFT))
  57                 ? U_R_VAL : 0;
  58 }
  59
  60 static inline usage_t u_addr(usage_t mode)
  61 {
  62         return mode = mode & U_MASK
  63                 ? U_R_AOF | (mode & U_W_AOF) : 0;
  64 }
  65
  66 static usage_t u_lval(struct symbol *type)
  67 {
  68         int wptr = is_ptr(type) && !(type->ctype.modifiers & MOD_CONST);
  69         return wptr || type == &bad_ctype
  70                 ? U_W_AOF | U_R_VAL : U_R_VAL;
  71 }
  72
  73 static usage_t fix_mode(struct symbol *type, usage_t mode)
  74 {
  75         mode &= (U_SELF | (U_SELF << U_SHIFT));
  76
  77         switch (type->type) {
  78                 case SYM_BASETYPE:
  79                         if (!type->ctype.base_type)
  80                                 break;
  81                 case SYM_ENUM:
  82                 case SYM_BITFIELD:
  83                         if (mode & U_MASK)
  84                                 mode &= U_SELF;
  85                 default:
  86
  87                 break; case SYM_FN:
  88                         if (mode & U_R_VAL)
  89                                 mode |= U_R_AOF;
  90                         mode &= ~(U_R_VAL | U_W_AOF);
  91
  92                 break; case SYM_ARRAY:
  93                         if (mode & (U_MASK << U_SHIFT))
  94                                 mode >>= U_SHIFT;
  95                         else if (mode != U_W_VAL)
  96                                 mode = u_addr(mode);
  97         }
  98
  99         if (!(mode & U_R_AOF))
 100                 mode &= ~U_W_AOF;
 101
 102         return mode;
 103 }
 104
 105 static inline struct symbol *no_member(struct ident *name)
 106 {
 107         static struct symbol sym = {
 108                 .type = SYM_BAD,
 109         };
 110
 111         sym.ctype.base_type = &bad_ctype;
 112         sym.ident = name;
 113
 114         return &sym;
 115 }
 116
 117 static struct symbol *report_member(mode_t mode, struct position *pos,
 118                                         struct symbol *type, struct symbol *mem)
 119 {
 120         struct symbol *ret = mem->ctype.base_type;
 121
 122         if (reporter->r_member)
 123                 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
 124
 125         return ret;
 126 }
 127
 128 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
 129 {
 130         if (type->type != SYM_STRUCT && type->type != SYM_UNION)
 131                 return;
 132
 133         if (reporter->r_member) {
 134                 reporter->r_member(mode, pos, type, NULL);
 135
 136                 DO_LIST(type->symbol_list, mem,
 137                         report_implicit(mode, pos, base_type(mem)));
 138         }
 139 }
 140
 141 static inline struct symbol *expr_symbol(struct expression *expr)
 142 {
 143         struct symbol *sym = expr->symbol;
 144
 145         if (!sym) {
 146                 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
 147
 148                 if (!sym) {
 149                         sym = alloc_symbol(expr->pos, SYM_BAD);
 150                         bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
 151                         sym->ctype.modifiers = MOD_EXTERN;
 152                 }
 153         }
 154
 155         if (!sym->ctype.base_type)
 156                 sym->ctype.base_type = &bad_ctype;
 157
 158         return sym;
 159 }
 160
 161 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
 162 {
 163         struct symbol *sym = expr_symbol(expr);
 164         struct symbol *ret = base_type(sym);
 165
 166         if (0 && ret->type == SYM_ENUM)
 167                 return report_member(mode, &expr->pos, ret, expr->symbol);
 168
 169         if (reporter->r_symbol)
 170                 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
 171
 172         return ret;
 173 }
 174
 175 static inline struct ident *mk_name(struct ident *root, struct ident *node)
 176 {
 177         char name[256];
 178
 179         snprintf(name, sizeof(name), "%.*s:%.*s",
 180                         root ? root->len : 0, root->name,
 181                         node ? node->len : 0, node->name);
 182
 183         return built_in_ident(name);
 184 }
 185
 186 static void examine_sym_node(struct symbol *node, struct ident *root)
 187 {
 188         struct symbol *base;
 189         struct ident *name;
 190
 191         if (node->examined)
 192                 return;
 193
 194         node->examined = 1;
 195         name = node->ident;
 196
 197         while ((base = node->ctype.base_type) != NULL)
 198                 switch (base->type) {
 199                 case SYM_TYPEOF:
 200                         node->ctype.base_type =
 201                                 do_expression(U_VOID, base->initializer);
 202                         break;
 203
 204                 case SYM_ARRAY:
 205                         do_expression(U_R_VAL, base->array_size);
 206                 case SYM_PTR: case SYM_FN:
 207                         node = base;
 208                         break;
 209
 210                 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
 211                         if (base->evaluated)
 212                                 return;
 213                         if (!base->ident && name)
 214                                 base->ident = mk_name(root, name);
 215                         if (!base->ident || !base->symbol_list)
 216                                 return;
 217                         if (reporter->r_symdef)
 218                                 reporter->r_symdef(base);
 219                         base->evaluated = 1;
 220                 default:
 221                         return;
 222                 }
 223 }
 224
 225 static struct symbol *base_type(struct symbol *sym)
 226 {
 227         if (!sym)
 228                 return &bad_ctype;
 229
 230         if (sym->type == SYM_NODE)
 231                 examine_sym_node(sym, NULL);
 232
 233         return sym->ctype.base_type     // builtin_fn_type
 234                 ?: &bad_ctype;
 235 }
 236
 237 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
 238 {
 239         struct symbol *node;
 240         int addr = 0;
 241
 242         FOR_EACH_PTR(type->symbol_list, node)
 243                 if (!name) {
 244                         if (addr == *p_addr)
 245                                 return node;
 246                 }
 247                 else if (node->ident == NULL) {
 248                         node = __lookup_member(node->ctype.base_type, name, NULL);
 249                         if (node)
 250                                 goto found;
 251                 }
 252                 else if (node->ident == name) {
 253 found:
 254                         if (p_addr)
 255                                 *p_addr = addr;
 256                         return node;
 257                 }
 258                 addr++;
 259         END_FOR_EACH_PTR(node);
 260
 261         return NULL;
 262 }
 263
 264 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
 265 {
 266         struct symbol *node = __lookup_member(type, name, addr);
 267
 268         if (node != NULL)
 269                 examine_sym_node(node, type->ident);
 270         else
 271                 node = no_member(name);
 272
 273         return node;
 274 }
 275
 276 static struct expression *peek_preop(struct expression *expr, int op)
 277 {
 278         do {
 279                 if (expr->type != EXPR_PREOP)
 280                         break;
 281                 if (expr->op == op)
 282                         return expr->unop;
 283                 if (expr->op == '(')
 284                         expr = expr->unop;
 285                 else
 286                         break;
 287         } while (expr);
 288
 289         return NULL;
 290 }
 291
 292 static struct symbol *do_expression(usage_t mode, struct expression *expr)
 293 {
 294         struct symbol *ret = &int_ctype;
 295
 296 again:
 297         if (expr) switch (expr->type) {
 298         default:
 299                 warning(expr->pos, "bad expr->type: %d", expr->type);
 300
 301         case EXPR_TYPE:         // [struct T]; Why ???
 302         case EXPR_VALUE:
 303         case EXPR_FVALUE:
 304
 305         break; case EXPR_LABEL:
 306                 ret = &label_ctype;
 307
 308         break; case EXPR_STRING:
 309                 ret = &string_ctype;
 310
 311         break; case EXPR_STATEMENT:
 312                 ret = do_statement(mode, expr->statement);
 313
 314         break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
 315                 do_expression(U_VOID, expr->cast_expression);
 316
 317         break; case EXPR_COMMA:
 318                 do_expression(U_VOID, expr->left);
 319                 ret = do_expression(mode, expr->right);
 320
 321         break; case EXPR_CAST: //case EXPR_IMPLIED_CAST:
 322                 ret = base_type(expr->cast_type);
 323                 do_initializer(ret, expr->cast_expression);
 324
 325         break; case EXPR_COMPARE: case EXPR_LOGICAL:
 326                 mode = u_rval(mode);
 327                 do_expression(mode, expr->left);
 328                 do_expression(mode, expr->right);
 329
 330         break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
 331                 do_expression(expr->cond_true
 332                                         ? U_R_VAL : U_R_VAL | mode,
 333                                 expr->conditional);
 334                 ret = do_expression(mode, expr->cond_true);
 335                 ret = do_expression(mode, expr->cond_false);
 336
 337         break; case EXPR_CALL:
 338                 ret = do_expression(U_R_PTR, expr->fn);
 339                 if (is_ptr(ret))
 340                         ret = ret->ctype.base_type;
 341                 DO_2_LIST(ret->arguments, expr->args, arg, val,
 342                         do_expression(u_lval(base_type(arg)), val));
 343                 ret = ret->type == SYM_FN ? base_type(ret)
 344                         : &bad_ctype;
 345
 346         break; case EXPR_ASSIGNMENT:
 347                 mode |= U_W_VAL | U_R_VAL;
 348                 if (expr->op == '=')
 349                         mode &= ~U_R_VAL;
 350                 ret = do_expression(mode, expr->left);
 351                 report_implicit(mode, &expr->pos, ret);
 352                 mode = expr->op == '='
 353                         ? u_lval(ret) : U_R_VAL;
 354                 do_expression(mode, expr->right);
 355
 356         break; case EXPR_BINOP: {
 357                 struct symbol *l, *r;
 358                 mode |= u_rval(mode);
 359                 l = do_expression(mode, expr->left);
 360                 r = do_expression(mode, expr->right);
 361                 if (expr->op != '+' && expr->op != '-')
 362                         ;
 363                 else if (!is_ptr_type(r))
 364                         ret = l;
 365                 else if (!is_ptr_type(l))
 366                         ret = r;
 367         }
 368
 369         break; case EXPR_PREOP: case EXPR_POSTOP: {
 370                 struct expression *unop = expr->unop;
 371
 372                 switch (expr->op) {
 373                 case SPECIAL_INCREMENT:
 374                 case SPECIAL_DECREMENT:
 375                         mode |= U_W_VAL | U_R_VAL;
 376                 default:
 377                         mode |= u_rval(mode);
 378                 case '(':
 379                         ret = do_expression(mode, unop);
 380
 381                 break; case '&':
 382                         if ((expr = peek_preop(unop, '*')))
 383                                 goto again;
 384                         ret = alloc_symbol(unop->pos, SYM_PTR);
 385                         ret->ctype.base_type =
 386                                 do_expression(u_addr(mode), unop);
 387
 388                 break; case '*':
 389                         if ((expr = peek_preop(unop, '&')))
 390                                 goto again;
 391                         if (mode & (U_MASK << U_SHIFT))
 392                                 mode |= U_R_VAL;
 393                         mode <<= U_SHIFT;
 394                         if (mode & (U_R_AOF << U_SHIFT))
 395                                 mode |= U_R_VAL;
 396                         if (mode & (U_W_VAL << U_SHIFT))
 397                                 mode |= U_W_AOF;
 398                         ret = do_expression(mode, unop);
 399                         ret = is_ptr(ret) ? base_type(ret)
 400                                 : &bad_ctype;
 401                 }
 402         }
 403
 404         break; case EXPR_DEREF: {
 405                 struct symbol *p_type;
 406                 usage_t p_mode;
 407
 408                 p_mode = mode & U_SELF;
 409                 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
 410                         p_mode = U_R_VAL;
 411                 p_type = do_expression(p_mode, expr->deref);
 412
 413                 ret = report_member(mode, &expr->pos, p_type,
 414                         lookup_member(p_type, expr->member, NULL));
 415         }
 416
 417         break; case EXPR_SYMBOL:
 418                 ret = report_symbol(mode, expr);
 419         }
 420
 421         return ret;
 422 }
 423
 424 static void do_asm_xputs(usage_t mode, struct expression_list *xputs)
 425 {
 426         int nr = 0;
 427
 428         DO_LIST(xputs, expr,
 429                 if (++nr % 3 == 0)
 430                         do_expression(U_W_AOF | mode, expr));
 431 }
 432
 433 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
 434 {
 435         struct symbol *ret = &void_ctype;
 436
 437         if (stmt) switch (stmt->type) {
 438         default:
 439                 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
 440
 441         case STMT_NONE:
 442         case STMT_RANGE:
 443         case STMT_CONTEXT:
 444
 445         break; case STMT_DECLARATION:
 446                 do_sym_list(stmt->declaration);
 447
 448         break; case STMT_EXPRESSION:
 449                 ret = do_expression(mode, stmt->expression);
 450
 451         break; case STMT_RETURN:
 452                 do_expression(u_lval(return_type), stmt->expression);
 453
 454         break; case STMT_ASM:
 455                 do_expression(U_R_VAL, stmt->asm_string);
 456                 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
 457                 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
 458
 459         break; case STMT_COMPOUND: {
 460                 int count;
 461
 462                 count = statement_list_size(stmt->stmts);
 463                 DO_LIST(stmt->stmts, st,
 464                         ret = do_statement(--count ? U_VOID : mode, st));
 465         }
 466
 467         break; case STMT_ITERATOR:
 468                 do_sym_list(stmt->iterator_syms);
 469                 do_statement(U_VOID, stmt->iterator_pre_statement);
 470                 do_expression(U_R_VAL, stmt->iterator_pre_condition);
 471                 do_statement(U_VOID, stmt->iterator_post_statement);
 472                 do_statement(U_VOID, stmt->iterator_statement);
 473                 do_expression(U_R_VAL, stmt->iterator_post_condition);
 474
 475         break; case STMT_IF:
 476                 do_expression(U_R_VAL, stmt->if_conditional);
 477                 do_statement(U_VOID, stmt->if_true);
 478                 do_statement(U_VOID, stmt->if_false);
 479
 480         break; case STMT_SWITCH:
 481                 do_expression(U_R_VAL, stmt->switch_expression);
 482                 do_statement(U_VOID, stmt->switch_statement);
 483
 484         break; case STMT_CASE:
 485                 do_expression(U_R_VAL, stmt->case_expression);
 486                 do_expression(U_R_VAL, stmt->case_to);
 487                 do_statement(U_VOID, stmt->case_statement);
 488
 489         break; case STMT_GOTO:
 490                 do_expression(U_R_PTR, stmt->goto_expression);
 491
 492         break; case STMT_LABEL:
 493                 do_statement(mode, stmt->label_statement);
 494
 495         }
 496
 497         return ret;
 498 }
 499
 500 static struct symbol *do_initializer(struct symbol *type, struct expression* expr)
 501 {
 502         struct symbol *m_type;
 503         struct expression *m_expr;
 504         int m_addr;
 505
 506         if (expr) switch (expr->type) {
 507         default:
 508                 do_expression(u_lval(type), expr);
 509
 510         break; case EXPR_INITIALIZER:
 511                 m_addr = 0;
 512                 FOR_EACH_PTR(expr->expr_list, m_expr)
 513                         if(type->type == SYM_ARRAY) {
 514                                 m_type = base_type(type);
 515                                 if (m_expr->type == EXPR_INDEX)
 516                                         m_expr = m_expr->idx_expression;
 517                         } else {
 518                                 struct position *pos = &m_expr->pos;
 519                                 struct ident *m_name = NULL;
 520
 521                                 if (m_expr->type == EXPR_IDENTIFIER) {
 522                                         m_name = m_expr->expr_ident;
 523                                         m_expr = m_expr->ident_expression;
 524                                 }
 525
 526                                 m_type = report_member(U_W_VAL, pos, type,
 527                                                 lookup_member(type, m_name, &m_addr));
 528                                 if (m_expr->type != EXPR_INITIALIZER)
 529                                         report_implicit(U_W_VAL, pos, m_type);
 530                         }
 531                         do_initializer(m_type, m_expr);
 532                         m_addr++;
 533                 END_FOR_EACH_PTR(m_expr);
 534         }
 535
 536         return type;
 537 }
 538
 539 static inline struct symbol *do_symbol(struct symbol *sym)
 540 {
 541         struct symbol *type;
 542
 543         type = base_type(sym);
 544
 545         if (reporter->r_symdef)
 546                 reporter->r_symdef(sym);
 547
 548         switch (type->type) {
 549         default:
 550                 if (!sym->initializer)
 551                         break;
 552                 if (reporter->r_symbol)
 553                         reporter->r_symbol(U_W_VAL, &sym->pos, sym);
 554                 do_initializer(type, sym->initializer);
 555
 556         break; case SYM_FN:
 557                 do_sym_list(type->arguments);
 558                 return_type = base_type(type);
 559                 do_statement(U_VOID, sym->ctype.modifiers & MOD_INLINE
 560                                         ? type->inline_stmt
 561                                         : type->stmt);
 562         }
 563
 564         return type;
 565 }
 566
 567 static void do_sym_list(struct symbol_list *list)
 568 {
 569         DO_LIST(list, sym, do_symbol(sym));
 570 }
 571
 572 void dissect(struct symbol_list *list, struct reporter *rep)
 573 {
 574         reporter = rep;
 575         do_sym_list(list);
 576 }