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                 return;
 135
 136         if (type->ident != NULL)
 137                 reporter->r_member(mode, pos, type, NULL);
 138
 139         DO_LIST(type->symbol_list, mem,
 140                 report_implicit(mode, pos, base_type(mem)));
 141 }
 142
 143 static inline struct symbol *expr_symbol(struct expression *expr)
 144 {
 145         struct symbol *sym = expr->symbol;
 146
 147         if (!sym) {
 148                 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
 149
 150                 if (!sym) {
 151                         sym = alloc_symbol(expr->pos, SYM_BAD);
 152                         bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
 153                         sym->ctype.modifiers = MOD_EXTERN;
 154                 }
 155         }
 156
 157         if (!sym->ctype.base_type)
 158                 sym->ctype.base_type = &bad_ctype;
 159
 160         return sym;
 161 }
 162
 163 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
 164 {
 165         struct symbol *sym = expr_symbol(expr);
 166         struct symbol *ret = base_type(sym);
 167
 168         if (0 && ret->type == SYM_ENUM)
 169                 return report_member(mode, &expr->pos, ret, expr->symbol);
 170
 171         if (reporter->r_symbol)
 172                 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
 173
 174         return ret;
 175 }
 176
 177 static inline struct ident *mk_name(struct ident *root, struct ident *node)
 178 {
 179         char name[256];
 180
 181         snprintf(name, sizeof(name), "%.*s:%.*s",
 182                         root ? root->len : 0, root->name,
 183                         node ? node->len : 0, node->name);
 184
 185         return built_in_ident(name);
 186 }
 187
 188 static void examine_sym_node(struct symbol *node, struct ident *root)
 189 {
 190         struct symbol *base;
 191         struct ident *name;
 192
 193         if (node->examined)
 194                 return;
 195
 196         node->examined = 1;
 197         name = node->ident;
 198
 199         while ((base = node->ctype.base_type) != NULL)
 200                 switch (base->type) {
 201                 case SYM_TYPEOF:
 202                         node->ctype.base_type =
 203                                 do_expression(U_VOID, base->initializer);
 204                         break;
 205
 206                 case SYM_ARRAY:
 207                         do_expression(U_R_VAL, base->array_size);
 208                 case SYM_PTR: case SYM_FN:
 209                         node = base;
 210                         break;
 211
 212                 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
 213                         if (base->evaluated)
 214                                 return;
 215                         if (!base->ident && name)
 216                                 base->ident = mk_name(root, name);
 217                         if (!base->ident || !base->symbol_list)
 218                                 return;
 219                         if (reporter->r_symdef)
 220                                 reporter->r_symdef(base);
 221                         base->evaluated = 1;
 222                 default:
 223                         return;
 224                 }
 225 }
 226
 227 static struct symbol *base_type(struct symbol *sym)
 228 {
 229         if (!sym)
 230                 return &bad_ctype;
 231
 232         if (sym->type == SYM_NODE)
 233                 examine_sym_node(sym, NULL);
 234
 235         return sym->ctype.base_type     // builtin_fn_type
 236                 ?: &bad_ctype;
 237 }
 238
 239 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
 240 {
 241         struct symbol *node;
 242         int addr = 0;
 243
 244         FOR_EACH_PTR(type->symbol_list, node)
 245                 if (!name) {
 246                         if (addr == *p_addr)
 247                                 return node;
 248                 }
 249                 else if (node->ident == NULL) {
 250                         node = __lookup_member(node->ctype.base_type, name, NULL);
 251                         if (node)
 252                                 goto found;
 253                 }
 254                 else if (node->ident == name) {
 255 found:
 256                         if (p_addr)
 257                                 *p_addr = addr;
 258                         return node;
 259                 }
 260                 addr++;
 261         END_FOR_EACH_PTR(node);
 262
 263         return NULL;
 264 }
 265
 266 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
 267 {
 268         struct symbol *node = __lookup_member(type, name, addr);
 269
 270         if (node != NULL)
 271                 examine_sym_node(node, type->ident);
 272         else
 273                 node = no_member(name);
 274
 275         return node;
 276 }
 277
 278 static struct expression *peek_preop(struct expression *expr, int op)
 279 {
 280         do {
 281                 if (expr->type != EXPR_PREOP)
 282                         break;
 283                 if (expr->op == op)
 284                         return expr->unop;
 285                 if (expr->op == '(')
 286                         expr = expr->unop;
 287                 else
 288                         break;
 289         } while (expr);
 290
 291         return NULL;
 292 }
 293
 294 static struct symbol *do_expression(usage_t mode, struct expression *expr)
 295 {
 296         struct symbol *ret = &int_ctype;
 297
 298 again:
 299         if (expr) switch (expr->type) {
 300         default:
 301                 warning(expr->pos, "bad expr->type: %d", expr->type);
 302
 303         case EXPR_TYPE:         // [struct T]; Why ???
 304         case EXPR_VALUE:
 305         case EXPR_FVALUE:
 306
 307         break; case EXPR_LABEL:
 308                 ret = &label_ctype;
 309
 310         break; case EXPR_STRING:
 311                 ret = &string_ctype;
 312
 313         break; case EXPR_STATEMENT:
 314                 ret = do_statement(mode, expr->statement);
 315
 316         break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
 317                 do_expression(U_VOID, expr->cast_expression);
 318
 319         break; case EXPR_COMMA:
 320                 do_expression(U_VOID, expr->left);
 321                 ret = do_expression(mode, expr->right);
 322
 323         break; case EXPR_CAST: //case EXPR_IMPLIED_CAST:
 324                 ret = base_type(expr->cast_type);
 325                 do_initializer(ret, expr->cast_expression);
 326
 327         break; case EXPR_COMPARE: case EXPR_LOGICAL:
 328                 mode = u_rval(mode);
 329                 do_expression(mode, expr->left);
 330                 do_expression(mode, expr->right);
 331
 332         break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
 333                 do_expression(expr->cond_true
 334                                         ? U_R_VAL : U_R_VAL | mode,
 335                                 expr->conditional);
 336                 ret = do_expression(mode, expr->cond_true);
 337                 ret = do_expression(mode, expr->cond_false);
 338
 339         break; case EXPR_CALL:
 340                 ret = do_expression(U_R_PTR, expr->fn);
 341                 if (is_ptr(ret))
 342                         ret = ret->ctype.base_type;
 343                 DO_2_LIST(ret->arguments, expr->args, arg, val,
 344                         do_expression(u_lval(base_type(arg)), val));
 345                 ret = ret->type == SYM_FN ? base_type(ret)
 346                         : &bad_ctype;
 347
 348         break; case EXPR_ASSIGNMENT:
 349                 mode |= U_W_VAL | U_R_VAL;
 350                 if (expr->op == '=')
 351                         mode &= ~U_R_VAL;
 352                 ret = do_expression(mode, expr->left);
 353                 report_implicit(mode, &expr->pos, ret);
 354                 mode = expr->op == '='
 355                         ? u_lval(ret) : U_R_VAL;
 356                 do_expression(mode, expr->right);
 357
 358         break; case EXPR_BINOP: {
 359                 struct symbol *l, *r;
 360                 mode |= u_rval(mode);
 361                 l = do_expression(mode, expr->left);
 362                 r = do_expression(mode, expr->right);
 363                 if (expr->op != '+' && expr->op != '-')
 364                         ;
 365                 else if (!is_ptr_type(r))
 366                         ret = l;
 367                 else if (!is_ptr_type(l))
 368                         ret = r;
 369         }
 370
 371         break; case EXPR_PREOP: case EXPR_POSTOP: {
 372                 struct expression *unop = expr->unop;
 373
 374                 switch (expr->op) {
 375                 case SPECIAL_INCREMENT:
 376                 case SPECIAL_DECREMENT:
 377                         mode |= U_W_VAL | U_R_VAL;
 378                 default:
 379                         mode |= u_rval(mode);
 380                 case '(':
 381                         ret = do_expression(mode, unop);
 382
 383                 break; case '&':
 384                         if ((expr = peek_preop(unop, '*')))
 385                                 goto again;
 386                         ret = alloc_symbol(unop->pos, SYM_PTR);
 387                         ret->ctype.base_type =
 388                                 do_expression(u_addr(mode), unop);
 389
 390                 break; case '*':
 391                         if ((expr = peek_preop(unop, '&')))
 392                                 goto again;
 393                         if (mode & (U_MASK << U_SHIFT))
 394                                 mode |= U_R_VAL;
 395                         mode <<= U_SHIFT;
 396                         if (mode & (U_R_AOF << U_SHIFT))
 397                                 mode |= U_R_VAL;
 398                         if (mode & (U_W_VAL << U_SHIFT))
 399                                 mode |= U_W_AOF;
 400                         ret = do_expression(mode, unop);
 401                         ret = is_ptr(ret) ? base_type(ret)
 402                                 : &bad_ctype;
 403                 }
 404         }
 405
 406         break; case EXPR_DEREF: {
 407                 struct symbol *p_type;
 408                 usage_t p_mode;
 409
 410                 p_mode = mode & U_SELF;
 411                 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
 412                         p_mode = U_R_VAL;
 413                 p_type = do_expression(p_mode, expr->deref);
 414
 415                 ret = report_member(mode, &expr->pos, p_type,
 416                         lookup_member(p_type, expr->member, NULL));
 417         }
 418
 419         break; case EXPR_SYMBOL:
 420                 ret = report_symbol(mode, expr);
 421         }
 422
 423         return ret;
 424 }
 425
 426 static void do_asm_xputs(usage_t mode, struct expression_list *xputs)
 427 {
 428         int nr = 0;
 429
 430         DO_LIST(xputs, expr,
 431                 if (++nr % 3 == 0)
 432                         do_expression(U_W_AOF | mode, expr));
 433 }
 434
 435 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
 436 {
 437         struct symbol *ret = &void_ctype;
 438
 439         if (stmt) switch (stmt->type) {
 440         default:
 441                 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
 442
 443         case STMT_NONE:
 444         case STMT_RANGE:
 445         case STMT_CONTEXT:
 446
 447         break; case STMT_DECLARATION:
 448                 do_sym_list(stmt->declaration);
 449
 450         break; case STMT_EXPRESSION:
 451                 ret = do_expression(mode, stmt->expression);
 452
 453         break; case STMT_RETURN:
 454                 do_expression(u_lval(return_type), stmt->expression);
 455
 456         break; case STMT_ASM:
 457                 do_expression(U_R_VAL, stmt->asm_string);
 458                 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
 459                 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
 460
 461         break; case STMT_COMPOUND: {
 462                 int count;
 463
 464                 count = statement_list_size(stmt->stmts);
 465                 DO_LIST(stmt->stmts, st,
 466                         ret = do_statement(--count ? U_VOID : mode, st));
 467         }
 468
 469         break; case STMT_ITERATOR:
 470                 do_sym_list(stmt->iterator_syms);
 471                 do_statement(U_VOID, stmt->iterator_pre_statement);
 472                 do_expression(U_R_VAL, stmt->iterator_pre_condition);
 473                 do_statement(U_VOID, stmt->iterator_post_statement);
 474                 do_statement(U_VOID, stmt->iterator_statement);
 475                 do_expression(U_R_VAL, stmt->iterator_post_condition);
 476
 477         break; case STMT_IF:
 478                 do_expression(U_R_VAL, stmt->if_conditional);
 479                 do_statement(U_VOID, stmt->if_true);
 480                 do_statement(U_VOID, stmt->if_false);
 481
 482         break; case STMT_SWITCH:
 483                 do_expression(U_R_VAL, stmt->switch_expression);
 484                 do_statement(U_VOID, stmt->switch_statement);
 485
 486         break; case STMT_CASE:
 487                 do_expression(U_R_VAL, stmt->case_expression);
 488                 do_expression(U_R_VAL, stmt->case_to);
 489                 do_statement(U_VOID, stmt->case_statement);
 490
 491         break; case STMT_GOTO:
 492                 do_expression(U_R_PTR, stmt->goto_expression);
 493
 494         break; case STMT_LABEL:
 495                 do_statement(mode, stmt->label_statement);
 496
 497         }
 498
 499         return ret;
 500 }
 501
 502 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
 503 {
 504         struct symbol *m_type;
 505         struct expression *m_expr;
 506         int m_addr;
 507
 508         if (expr) switch (expr->type) {
 509         default:
 510                 do_expression(u_lval(type), expr);
 511
 512         break; case EXPR_INDEX:
 513                 do_initializer(base_type(type), expr->idx_expression);
 514
 515         break; case EXPR_INITIALIZER:
 516                 m_addr = 0;
 517                 FOR_EACH_PTR(expr->expr_list, m_expr)
 518                         if (type->type == SYM_ARRAY) {
 519                                 m_type = base_type(type);
 520                                 if (m_expr->type == EXPR_INDEX)
 521                                         m_expr = m_expr->idx_expression;
 522                         } else {
 523                                 struct position *pos = &m_expr->pos;
 524                                 struct ident *m_name = NULL;
 525
 526                                 if (m_expr->type == EXPR_IDENTIFIER) {
 527                                         m_name = m_expr->expr_ident;
 528                                         m_expr = m_expr->ident_expression;
 529                                 }
 530
 531                                 m_type = report_member(U_W_VAL, pos, type,
 532                                                 lookup_member(type, m_name, &m_addr));
 533                                 if (m_expr->type != EXPR_INITIALIZER)
 534                                         report_implicit(U_W_VAL, pos, m_type);
 535                         }
 536                         do_initializer(m_type, m_expr);
 537                         m_addr++;
 538                 END_FOR_EACH_PTR(m_expr);
 539         }
 540
 541         return type;
 542 }
 543
 544 static inline struct symbol *do_symbol(struct symbol *sym)
 545 {
 546         struct symbol *type;
 547
 548         type = base_type(sym);
 549
 550         if (reporter->r_symdef)
 551                 reporter->r_symdef(sym);
 552
 553         switch (type->type) {
 554         default:
 555                 if (!sym->initializer)
 556                         break;
 557                 if (reporter->r_symbol)
 558                         reporter->r_symbol(U_W_VAL, &sym->pos, sym);
 559                 do_initializer(type, sym->initializer);
 560
 561         break; case SYM_FN:
 562                 do_sym_list(type->arguments);
 563                 return_type = base_type(type);
 564                 do_statement(U_VOID, sym->ctype.modifiers & MOD_INLINE
 565                                         ? type->inline_stmt
 566                                         : type->stmt);
 567         }
 568
 569         return type;
 570 }
 571
 572 static void do_sym_list(struct symbol_list *list)
 573 {
 574         DO_LIST(list, sym, do_symbol(sym));
 575 }
 576
 577 void dissect(struct symbol_list *list, struct reporter *rep)
 578 {
 579         reporter = rep;
 580         do_sym_list(list);
 581 }