dissect.c

   1 /*
   2  * sparse/dissect.c
   3  *
   4  * Started by Oleg Nesterov <oleg@redhat.com>
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to deal
   8  * in the Software without restriction, including without limitation the rights
   9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23  */
  24
  25 #include "dissect.h"
  26
  27 #define U_VOID   0x00
  28 #define U_SELF  ((1 << U_SHIFT) - 1)
  29 #define U_MASK  (U_R_VAL | U_W_VAL | U_R_AOF)
  30
  31 #define DO_LIST(l__, p__, expr__)               \
  32         do {                                    \
  33                 typeof(l__->list[0]) p__;       \
  34                 FOR_EACH_PTR(l__, p__)          \
  35                         expr__;                 \
  36                 END_FOR_EACH_PTR(p__);          \
  37         } while (0)
  38
  39 #define DO_2_LIST(l1__,l2__, p1__,p2__, expr__) \
  40         do {                                    \
  41                 typeof(l1__->list[0]) p1__;     \
  42                 typeof(l2__->list[0]) p2__;     \
  43                 PREPARE_PTR_LIST(l1__, p1__);   \
  44                 FOR_EACH_PTR(l2__, p2__)        \
  45                         expr__;                 \
  46                         NEXT_PTR_LIST(p1__);    \
  47                 END_FOR_EACH_PTR(p2__);         \
  48                 FINISH_PTR_LIST(p1__);          \
  49         } while (0)
  50
  51
  52 typedef unsigned usage_t;
  53
  54 struct symbol *dissect_ctx;
  55
  56 static struct reporter *reporter;
  57
  58 static void do_sym_list(struct symbol_list *list);
  59
  60 static struct symbol
  61         *base_type(struct symbol *sym),
  62         *do_initializer(struct symbol *type, struct expression *expr),
  63         *do_expression(usage_t mode, struct expression *expr),
  64         *do_statement(usage_t mode, struct statement *stmt);
  65
  66 static inline int is_ptr(struct symbol *type)
  67 {
  68         return type->type == SYM_PTR || type->type == SYM_ARRAY;
  69 }
  70
  71 static inline usage_t u_rval(usage_t mode)
  72 {
  73         return mode & (U_R_VAL | (U_MASK << U_SHIFT))
  74                 ? U_R_VAL : 0;
  75 }
  76
  77 static inline usage_t u_addr(usage_t mode)
  78 {
  79         return mode = mode & U_MASK
  80                 ? U_R_AOF | (mode & U_W_AOF) : 0;
  81 }
  82
  83 static usage_t u_lval(struct symbol *type)
  84 {
  85         int wptr = is_ptr(type) && !(type->ctype.modifiers & MOD_CONST);
  86         return wptr || type == &bad_ctype
  87                 ? U_W_AOF | U_R_VAL : U_R_VAL;
  88 }
  89
  90 static usage_t fix_mode(struct symbol *type, usage_t mode)
  91 {
  92         mode &= (U_SELF | (U_SELF << U_SHIFT));
  93
  94         switch (type->type) {
  95                 case SYM_BASETYPE:
  96                         if (!type->ctype.base_type)
  97                                 break;
  98                 case SYM_ENUM:
  99                 case SYM_BITFIELD:
 100                         if (mode & U_MASK)
 101                                 mode &= U_SELF;
 102                 default:
 103
 104                 break; case SYM_FN:
 105                         if (mode & U_R_VAL)
 106                                 mode |= U_R_AOF;
 107                         mode &= ~(U_R_VAL | U_W_AOF);
 108
 109                 break; case SYM_ARRAY:
 110                         if (mode & (U_MASK << U_SHIFT))
 111                                 mode >>= U_SHIFT;
 112                         else if (mode != U_W_VAL)
 113                                 mode = u_addr(mode);
 114         }
 115
 116         if (!(mode & U_R_AOF))
 117                 mode &= ~U_W_AOF;
 118
 119         return mode;
 120 }
 121
 122 static struct symbol *report_member(usage_t mode, struct position *pos,
 123                                         struct symbol *type, struct symbol *mem)
 124 {
 125         struct symbol *ret = mem->ctype.base_type;
 126
 127         if (mem->ident || mem->type == SYM_BAD)
 128                 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
 129
 130         return ret;
 131 }
 132
 133 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
 134 {
 135         if (type->type != SYM_STRUCT && type->type != SYM_UNION)
 136                 return;
 137
 138         if (type->ident != NULL)
 139                 reporter->r_member(mode, pos, type, NULL);
 140
 141         DO_LIST(type->symbol_list, mem,
 142                 report_implicit(mode, pos, base_type(mem)));
 143 }
 144
 145 static inline struct symbol *expr_symbol(struct expression *expr)
 146 {
 147         struct symbol *sym = expr->symbol;
 148
 149         if (!sym) {
 150                 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
 151
 152                 if (!sym) {
 153                         sym = alloc_symbol(expr->pos, SYM_BAD);
 154                         bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
 155                         sym->kind = expr->op ?: 'v'; /* see EXPR_CALL */
 156                 }
 157         }
 158
 159         if (!sym->ctype.base_type)
 160                 sym->ctype.base_type = &bad_ctype;
 161
 162         return sym;
 163 }
 164
 165 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
 166 {
 167         struct symbol *sym = expr_symbol(expr);
 168         struct symbol *ret = base_type(sym);
 169
 170         if (0 && ret->type == SYM_ENUM)
 171                 return report_member(mode, &expr->pos, ret, expr->symbol);
 172
 173         reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
 174
 175         return ret;
 176 }
 177
 178 static bool deanon(struct symbol *base, struct ident *node, struct symbol *parent)
 179 {
 180         struct ident *pi = parent ? parent->ident : NULL;
 181         char name[256];
 182
 183         if (!node) {
 184                 base->ident = pi;
 185                 return false;
 186         }
 187
 188         snprintf(name, sizeof(name), "%.*s:%.*s",
 189                 pi ? pi->len : 0, pi ? pi->name : NULL, node->len, node->name);
 190
 191         base->ident = built_in_ident(name);
 192         return true;
 193 }
 194
 195 static void report_memdef(struct symbol *sym, struct symbol *mem)
 196 {
 197         mem->kind = 'm';
 198         if (sym && mem->ident)
 199                 reporter->r_memdef(sym, mem);
 200 }
 201
 202 static void examine_sym_node(struct symbol *node, struct symbol *parent)
 203 {
 204         struct ident *name = node->ident;
 205         struct symbol *base, *dctx;
 206
 207         if (node->examined)
 208                 return;
 209         node->examined = 1;
 210         node->kind = 'v';
 211
 212         while ((base = node->ctype.base_type) != NULL)
 213                 switch (base->type) {
 214                 case SYM_TYPEOF:
 215                         node->ctype.base_type =
 216                                 do_expression(U_VOID, base->initializer);
 217                         break;
 218
 219                 case SYM_ARRAY:
 220                         do_expression(U_R_VAL, base->array_size);
 221                 case SYM_PTR:
 222                         node = base;
 223                         break;
 224
 225                 case SYM_FN:
 226                         node->kind = 'f';
 227                         node = base;
 228                         break;
 229
 230                 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
 231                         if (base->evaluated)
 232                                 return;
 233                         base->evaluated = 1;
 234                         base->kind = 's';
 235
 236                         if (!base->symbol_list)
 237                                 return;
 238
 239                         dctx = dissect_ctx;
 240                         if (toplevel(base->scope))
 241                                 dissect_ctx = NULL;
 242
 243                         if (base->ident || deanon(base, name, parent))
 244                                 reporter->r_symdef(base);
 245
 246                         if (base->ident)
 247                                 parent = base;
 248                         DO_LIST(base->symbol_list, mem,
 249                                 examine_sym_node(mem, parent);
 250                                 report_memdef(parent, mem));
 251                         dissect_ctx = dctx;
 252                 default:
 253                         return;
 254                 }
 255 }
 256
 257 static struct symbol *base_type(struct symbol *sym)
 258 {
 259         if (!sym)
 260                 return &bad_ctype;
 261
 262         if (sym->type == SYM_NODE)
 263                 examine_sym_node(sym, NULL);
 264
 265         return sym->ctype.base_type     // builtin_fn_type
 266                 ?: &bad_ctype;
 267 }
 268
 269 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
 270 {
 271         struct symbol *node;
 272         int addr = 0;
 273
 274         FOR_EACH_PTR(type->symbol_list, node)
 275                 if (!name) {
 276                         if (addr == *p_addr)
 277                                 return node;
 278                 }
 279                 else if (node->ident == NULL) {
 280                         node = __lookup_member(node->ctype.base_type, name, NULL);
 281                         if (node)
 282                                 goto found;
 283                 }
 284                 else if (node->ident == name) {
 285 found:
 286                         if (p_addr)
 287                                 *p_addr = addr;
 288                         return node;
 289                 }
 290                 addr++;
 291         END_FOR_EACH_PTR(node);
 292
 293         return NULL;
 294 }
 295
 296 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
 297 {
 298         struct symbol *mem = __lookup_member(type, name, addr);
 299
 300         if (!mem) {
 301                 static struct symbol bad_member = {
 302                         .type = SYM_BAD,
 303                         .ctype.base_type = &bad_ctype,
 304                         .kind = 'm',
 305                 };
 306
 307                 if (!type->symbol_list)
 308                         type->scope = file_scope;
 309
 310                 mem = &bad_member;
 311                 mem->ident = name;
 312         }
 313
 314         return mem;
 315 }
 316
 317 static struct expression *peek_preop(struct expression *expr, int op)
 318 {
 319         do {
 320                 if (expr->type != EXPR_PREOP)
 321                         break;
 322                 if (expr->op == op)
 323                         return expr->unop;
 324                 if (expr->op == '(')
 325                         expr = expr->unop;
 326                 else
 327                         break;
 328         } while (expr);
 329
 330         return NULL;
 331 }
 332
 333 static struct symbol *do_expression(usage_t mode, struct expression *expr)
 334 {
 335         struct symbol *ret = &int_ctype;
 336
 337 again:
 338         if (expr) switch (expr->type) {
 339         default:
 340                 warning(expr->pos, "bad expr->type: %d", expr->type);
 341
 342         case EXPR_TYPE:         // [struct T]; Why ???
 343         case EXPR_VALUE:
 344         case EXPR_FVALUE:
 345
 346         break; case EXPR_LABEL:
 347                 ret = &label_ctype;
 348
 349         break; case EXPR_STRING:
 350                 ret = &string_ctype;
 351
 352         break; case EXPR_STATEMENT:
 353                 ret = do_statement(mode, expr->statement);
 354
 355         break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
 356                 do_expression(U_VOID, expr->cast_expression);
 357
 358         break; case EXPR_COMMA:
 359                 do_expression(U_VOID, expr->left);
 360                 ret = do_expression(mode, expr->right);
 361
 362         break; case EXPR_CAST: case EXPR_FORCE_CAST: //case EXPR_IMPLIED_CAST:
 363                 ret = base_type(expr->cast_type);
 364                 do_initializer(ret, expr->cast_expression);
 365
 366         break; case EXPR_COMPARE: case EXPR_LOGICAL:
 367                 mode = u_rval(mode);
 368                 do_expression(mode, expr->left);
 369                 do_expression(mode, expr->right);
 370
 371         break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
 372                 do_expression(expr->cond_true
 373                                         ? U_R_VAL : U_R_VAL | mode,
 374                                 expr->conditional);
 375                 ret = do_expression(mode, expr->cond_true);
 376                 ret = do_expression(mode, expr->cond_false);
 377
 378         break; case EXPR_CALL:
 379                 if (expr->fn->type == EXPR_SYMBOL)
 380                         expr->fn->op = 'f'; /* for expr_symbol() */
 381                 ret = do_expression(U_R_PTR, expr->fn);
 382                 if (is_ptr(ret))
 383                         ret = ret->ctype.base_type;
 384                 DO_2_LIST(ret->arguments, expr->args, arg, val,
 385                         do_expression(u_lval(base_type(arg)), val));
 386                 ret = ret->type == SYM_FN ? base_type(ret)
 387                         : &bad_ctype;
 388
 389         break; case EXPR_ASSIGNMENT:
 390                 mode |= U_W_VAL | U_R_VAL;
 391                 if (expr->op == '=')
 392                         mode &= ~U_R_VAL;
 393                 ret = do_expression(mode, expr->left);
 394                 report_implicit(mode, &expr->pos, ret);
 395                 mode = expr->op == '='
 396                         ? u_lval(ret) : U_R_VAL;
 397                 do_expression(mode, expr->right);
 398
 399         break; case EXPR_BINOP: {
 400                 struct symbol *l, *r;
 401                 mode |= u_rval(mode);
 402                 l = do_expression(mode, expr->left);
 403                 r = do_expression(mode, expr->right);
 404                 if (expr->op != '+' && expr->op != '-')
 405                         ;
 406                 else if (!is_ptr_type(r))
 407                         ret = l;
 408                 else if (!is_ptr_type(l))
 409                         ret = r;
 410         }
 411
 412         break; case EXPR_PREOP: case EXPR_POSTOP: {
 413                 struct expression *unop = expr->unop;
 414
 415                 switch (expr->op) {
 416                 case SPECIAL_INCREMENT:
 417                 case SPECIAL_DECREMENT:
 418                         mode |= U_W_VAL | U_R_VAL;
 419                 default:
 420                         mode |= u_rval(mode);
 421                 case '(':
 422                         ret = do_expression(mode, unop);
 423
 424                 break; case '&':
 425                         if ((expr = peek_preop(unop, '*')))
 426                                 goto again;
 427                         ret = alloc_symbol(unop->pos, SYM_PTR);
 428                         ret->ctype.base_type =
 429                                 do_expression(u_addr(mode), unop);
 430
 431                 break; case '*':
 432                         if ((expr = peek_preop(unop, '&')))
 433                                 goto again;
 434                         if (mode & (U_MASK << U_SHIFT))
 435                                 mode |= U_R_VAL;
 436                         mode <<= U_SHIFT;
 437                         if (mode & (U_R_AOF << U_SHIFT))
 438                                 mode |= U_R_VAL;
 439                         if (mode & (U_W_VAL << U_SHIFT))
 440                                 mode |= U_W_AOF;
 441                         ret = do_expression(mode, unop);
 442                         ret = is_ptr(ret) ? base_type(ret)
 443                                 : &bad_ctype;
 444                 }
 445         }
 446
 447         break; case EXPR_DEREF: {
 448                 struct symbol *p_type;
 449                 usage_t p_mode;
 450
 451                 p_mode = mode & U_SELF;
 452                 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
 453                         p_mode = U_R_VAL;
 454                 p_type = do_expression(p_mode, expr->deref);
 455
 456                 ret = report_member(mode, &expr->pos, p_type,
 457                         lookup_member(p_type, expr->member, NULL));
 458         }
 459
 460         break; case EXPR_OFFSETOF: {
 461                 struct symbol *in = base_type(expr->in);
 462
 463                 do {
 464                         if (expr->op == '.') {
 465                                 in = report_member(U_VOID, &expr->pos, in,
 466                                         lookup_member(in, expr->ident, NULL));
 467                         } else {
 468                                 do_expression(U_R_VAL, expr->index);
 469                                 in = in->ctype.base_type;
 470                         }
 471                 } while ((expr = expr->down));
 472         }
 473
 474         break; case EXPR_SYMBOL:
 475                 ret = report_symbol(mode, expr);
 476         }
 477
 478         return ret;
 479 }
 480
 481 static void do_asm_xputs(usage_t mode, struct asm_operand_list *xputs)
 482 {
 483         DO_LIST(xputs, op, do_expression(U_W_AOF | mode, op->expr));
 484 }
 485
 486 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
 487 {
 488         struct symbol *ret = &void_ctype;
 489
 490         if (stmt) switch (stmt->type) {
 491         default:
 492                 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
 493
 494         case STMT_NONE:
 495         case STMT_RANGE:
 496         case STMT_CONTEXT:
 497
 498         break; case STMT_DECLARATION:
 499                 do_sym_list(stmt->declaration);
 500
 501         break; case STMT_EXPRESSION:
 502                 ret = do_expression(mode, stmt->expression);
 503
 504         break; case STMT_RETURN: {
 505                 struct symbol *type = dissect_ctx->ctype.base_type;
 506                 do_expression(u_lval(base_type(type)), stmt->expression);
 507         }
 508
 509         break; case STMT_ASM:
 510                 do_expression(U_R_VAL, stmt->asm_string);
 511                 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
 512                 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
 513
 514         break; case STMT_COMPOUND: {
 515                 int count;
 516
 517                 count = statement_list_size(stmt->stmts);
 518                 DO_LIST(stmt->stmts, st,
 519                         ret = do_statement(--count ? U_VOID : mode, st));
 520         }
 521
 522         break; case STMT_ITERATOR:
 523                 do_sym_list(stmt->iterator_syms);
 524                 do_statement(U_VOID, stmt->iterator_pre_statement);
 525                 do_expression(U_R_VAL, stmt->iterator_pre_condition);
 526                 do_statement(U_VOID, stmt->iterator_post_statement);
 527                 do_statement(U_VOID, stmt->iterator_statement);
 528                 do_expression(U_R_VAL, stmt->iterator_post_condition);
 529
 530         break; case STMT_IF:
 531                 do_expression(U_R_VAL, stmt->if_conditional);
 532                 do_statement(U_VOID, stmt->if_true);
 533                 do_statement(U_VOID, stmt->if_false);
 534
 535         break; case STMT_SWITCH:
 536                 do_expression(U_R_VAL, stmt->switch_expression);
 537                 do_statement(U_VOID, stmt->switch_statement);
 538
 539         break; case STMT_CASE:
 540                 do_expression(U_R_VAL, stmt->case_expression);
 541                 do_expression(U_R_VAL, stmt->case_to);
 542                 do_statement(U_VOID, stmt->case_statement);
 543
 544         break; case STMT_GOTO:
 545                 do_expression(U_R_PTR, stmt->goto_expression);
 546
 547         break; case STMT_LABEL:
 548                 do_statement(mode, stmt->label_statement);
 549
 550         }
 551
 552         return ret;
 553 }
 554
 555 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
 556 {
 557         struct symbol *m_type;
 558         struct expression *m_expr;
 559         int m_addr;
 560
 561         if (expr) switch (expr->type) {
 562         default:
 563                 do_expression(u_lval(type), expr);
 564
 565         break; case EXPR_INDEX:
 566                 do_initializer(base_type(type), expr->idx_expression);
 567
 568         break; case EXPR_INITIALIZER:
 569                 m_addr = 0;
 570                 FOR_EACH_PTR(expr->expr_list, m_expr) {
 571                         if (type->type == SYM_ARRAY) {
 572                                 m_type = base_type(type);
 573                                 if (m_expr->type == EXPR_INDEX)
 574                                         m_expr = m_expr->idx_expression;
 575                         } else {
 576                                 int *m_atop = &m_addr;
 577
 578                                 m_type = type;
 579                                 while (m_expr->type == EXPR_IDENTIFIER) {
 580                                         m_type = report_member(U_W_VAL, &m_expr->pos, m_type,
 581                                                         lookup_member(m_type, m_expr->expr_ident, m_atop));
 582                                         m_expr = m_expr->ident_expression;
 583                                         m_atop = NULL;
 584                                 }
 585
 586                                 if (m_atop) {
 587                                         m_type = report_member(U_W_VAL, &m_expr->pos, m_type,
 588                                                         lookup_member(m_type, NULL, m_atop));
 589                                 }
 590
 591                                 if (m_expr->type != EXPR_INITIALIZER)
 592                                         report_implicit(U_W_VAL, &m_expr->pos, m_type);
 593                         }
 594                         do_initializer(m_type, m_expr);
 595                         m_addr++;
 596                 } END_FOR_EACH_PTR(m_expr);
 597         }
 598
 599         return type;
 600 }
 601
 602 static inline struct symbol *do_symbol(struct symbol *sym)
 603 {
 604         struct symbol *type = base_type(sym);
 605         struct symbol *dctx = dissect_ctx;
 606         struct statement *stmt;
 607
 608         reporter->r_symdef(sym);
 609
 610         switch (type->type) {
 611         default:
 612                 if (!sym->initializer)
 613                         break;
 614                 reporter->r_symbol(U_W_VAL, &sym->pos, sym);
 615                 if (!dctx)
 616                         dissect_ctx = sym;
 617                 do_initializer(type, sym->initializer);
 618                 dissect_ctx = dctx;
 619
 620         break; case SYM_FN:
 621                 stmt = sym->ctype.modifiers & MOD_INLINE
 622                         ? type->inline_stmt : type->stmt;
 623                 if (!stmt)
 624                         break;
 625
 626                 if (dctx)
 627                         sparse_error(dctx->pos, "dissect_ctx change %s -> %s",
 628                                 show_ident(dctx->ident), show_ident(sym->ident));
 629
 630                 dissect_ctx = sym;
 631                 do_sym_list(type->arguments);
 632                 do_statement(U_VOID, stmt);
 633                 dissect_ctx = dctx;
 634         }
 635
 636         return type;
 637 }
 638
 639 static void do_sym_list(struct symbol_list *list)
 640 {
 641         DO_LIST(list, sym, do_symbol(sym));
 642 }
 643
 644 void dissect(struct reporter *rep, struct string_list *filelist)
 645 {
 646         reporter = rep;
 647
 648         DO_LIST(filelist, file, do_sym_list(__sparse(file)));
 649 }