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