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