1 /* 2 * Copyright (C) 2009 Dan Carpenter. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 16 */ 17 18 /* 19 * The idea here is that you have an expression and you 20 * want to know what the type is for that. 21 */ 22 23 #include "smatch.h" 24 #include "smatch_slist.h" 25 26 struct symbol *get_real_base_type(struct symbol *sym) 27 { 28 struct symbol *ret; 29 30 if (!sym) 31 return NULL; 32 if (sym->type == SYM_BASETYPE) 33 return sym; 34 ret = get_base_type(sym); 35 if (!ret) 36 return NULL; 37 if (ret->type == SYM_RESTRICT || ret->type == SYM_NODE) 38 return get_real_base_type(ret); 39 return ret; 40 } 41 42 int type_bytes(struct symbol *type) 43 { 44 int bits; 45 46 if (type && type->type == SYM_ARRAY) 47 return array_bytes(type); 48 49 bits = type_bits(type); 50 if (bits < 0) 51 return 0; 52 return bits_to_bytes(bits); 53 } 54 55 int array_bytes(struct symbol *type) 56 { 57 if (!type || type->type != SYM_ARRAY) 58 return 0; 59 return bits_to_bytes(type->bit_size); 60 } 61 62 static struct symbol *get_binop_type(struct expression *expr) 63 { 64 struct symbol *left, *right; 65 66 left = get_type(expr->left); 67 if (!left) 68 return NULL; 69 70 if (expr->op == SPECIAL_LEFTSHIFT || 71 expr->op == SPECIAL_RIGHTSHIFT) { 72 if (type_positive_bits(left) < 31) 73 return &int_ctype; 74 return left; 75 } 76 right = get_type(expr->right); 77 if (!right) 78 return NULL; 79 80 if (expr->op == '-' && 81 (is_ptr_type(left) && is_ptr_type(right))) 82 return ssize_t_ctype; 83 84 if (left->type == SYM_PTR || left->type == SYM_ARRAY) 85 return left; 86 if (right->type == SYM_PTR || right->type == SYM_ARRAY) 87 return right; 88 89 if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31) 90 return &int_ctype; 91 92 if (type_positive_bits(left) > type_positive_bits(right)) 93 return left; 94 return right; 95 } 96 97 static struct symbol *get_type_symbol(struct expression *expr) 98 { 99 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol) 100 return NULL; 101 102 return get_real_base_type(expr->symbol); 103 } 104 105 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member) 106 { 107 struct symbol *tmp, *sub; 108 109 FOR_EACH_PTR(symbol_list, tmp) { 110 if (!tmp->ident) { 111 sub = get_real_base_type(tmp); 112 sub = get_member_symbol(sub->symbol_list, member); 113 if (sub) 114 return sub; 115 continue; 116 } 117 if (tmp->ident == member) 118 return tmp; 119 } END_FOR_EACH_PTR(tmp); 120 121 return NULL; 122 } 123 124 static struct symbol *get_symbol_from_deref(struct expression *expr) 125 { 126 struct ident *member; 127 struct symbol *sym; 128 129 if (!expr || expr->type != EXPR_DEREF) 130 return NULL; 131 132 member = expr->member; 133 sym = get_type(expr->deref); 134 if (!sym) { 135 // sm_msg("could not find struct type"); 136 return NULL; 137 } 138 if (sym->type == SYM_PTR) 139 sym = get_real_base_type(sym); 140 sym = get_member_symbol(sym->symbol_list, member); 141 if (!sym) 142 return NULL; 143 return get_real_base_type(sym); 144 } 145 146 static struct symbol *get_return_type(struct expression *expr) 147 { 148 struct symbol *tmp; 149 150 tmp = get_type(expr->fn); 151 if (!tmp) 152 return NULL; 153 /* this is to handle __builtin_constant_p() */ 154 if (tmp->type != SYM_FN) 155 tmp = get_base_type(tmp); 156 return get_real_base_type(tmp); 157 } 158 159 static struct symbol *get_expr_stmt_type(struct statement *stmt) 160 { 161 if (stmt->type != STMT_COMPOUND) 162 return NULL; 163 stmt = last_ptr_list((struct ptr_list *)stmt->stmts); 164 if (stmt->type == STMT_LABEL) 165 stmt = stmt->label_statement; 166 if (stmt->type != STMT_EXPRESSION) 167 return NULL; 168 return get_type(stmt->expression); 169 } 170 171 static struct symbol *get_select_type(struct expression *expr) 172 { 173 struct symbol *one, *two; 174 175 one = get_type(expr->cond_true); 176 two = get_type(expr->cond_false); 177 if (!one || !two) 178 return NULL; 179 /* 180 * This is a hack. If the types are not equiv then we 181 * really don't know the type. But I think guessing is 182 * probably Ok here. 183 */ 184 if (type_positive_bits(one) > type_positive_bits(two)) 185 return one; 186 return two; 187 } 188 189 struct symbol *get_pointer_type(struct expression *expr) 190 { 191 struct symbol *sym; 192 193 sym = get_type(expr); 194 if (!sym) 195 return NULL; 196 if (sym->type == SYM_NODE) { 197 sym = get_real_base_type(sym); 198 if (!sym) 199 return NULL; 200 } 201 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY) 202 return NULL; 203 return get_real_base_type(sym); 204 } 205 206 static struct symbol *fake_pointer_sym(struct expression *expr) 207 { 208 struct symbol *sym; 209 struct symbol *base; 210 211 sym = alloc_symbol(expr->pos, SYM_PTR); 212 expr = expr->unop; 213 base = get_type(expr); 214 if (!base) 215 return NULL; 216 sym->ctype.base_type = base; 217 return sym; 218 } 219 220 static struct symbol *get_type_helper(struct expression *expr) 221 { 222 struct symbol *ret; 223 224 expr = strip_parens(expr); 225 if (!expr) 226 return NULL; 227 228 if (expr->ctype) 229 return expr->ctype; 230 231 switch (expr->type) { 232 case EXPR_STRING: 233 ret = &string_ctype; 234 break; 235 case EXPR_SYMBOL: 236 ret = get_type_symbol(expr); 237 break; 238 case EXPR_DEREF: 239 ret = get_symbol_from_deref(expr); 240 break; 241 case EXPR_PREOP: 242 case EXPR_POSTOP: 243 if (expr->op == '&') 244 ret = fake_pointer_sym(expr); 245 else if (expr->op == '*') 246 ret = get_pointer_type(expr->unop); 247 else 248 ret = get_type(expr->unop); 249 break; 250 case EXPR_ASSIGNMENT: 251 ret = get_type(expr->left); 252 break; 253 case EXPR_CAST: 254 case EXPR_FORCE_CAST: 255 case EXPR_IMPLIED_CAST: 256 ret = get_real_base_type(expr->cast_type); 257 break; 258 case EXPR_COMPARE: 259 case EXPR_BINOP: 260 ret = get_binop_type(expr); 261 break; 262 case EXPR_CALL: 263 ret = get_return_type(expr); 264 break; 265 case EXPR_STATEMENT: 266 ret = get_expr_stmt_type(expr->statement); 267 break; 268 case EXPR_CONDITIONAL: 269 case EXPR_SELECT: 270 ret = get_select_type(expr); 271 break; 272 case EXPR_SIZEOF: 273 ret = &ulong_ctype; 274 break; 275 case EXPR_LOGICAL: 276 ret = &int_ctype; 277 break; 278 case EXPR_OFFSETOF: 279 ret = &ulong_ctype; 280 break; 281 default: 282 return NULL; 283 } 284 285 if (ret && ret->type == SYM_TYPEOF) 286 ret = get_type(ret->initializer); 287 288 expr->ctype = ret; 289 return ret; 290 } 291 292 static struct symbol *get_final_type_helper(struct expression *expr) 293 { 294 /* 295 * The problem is that I wrote a bunch of Smatch to think that 296 * you could do get_type() on an expression and it would give 297 * you what the comparison was type promoted to. This is wrong 298 * but fixing it is a big of work... Hence this horrible hack. 299 * 300 */ 301 302 expr = strip_parens(expr); 303 if (!expr) 304 return NULL; 305 306 if (expr->type == EXPR_COMPARE) 307 return &int_ctype; 308 309 return NULL; 310 } 311 312 struct symbol *get_type(struct expression *expr) 313 { 314 return get_type_helper(expr); 315 } 316 317 struct symbol *get_final_type(struct expression *expr) 318 { 319 struct symbol *ret; 320 321 ret = get_final_type_helper(expr); 322 if (ret) 323 return ret; 324 return get_type_helper(expr); 325 } 326 327 struct symbol *get_promoted_type(struct symbol *left, struct symbol *right) 328 { 329 struct symbol *ret = &int_ctype; 330 331 if (type_positive_bits(left) > type_positive_bits(ret)) 332 ret = left; 333 if (type_positive_bits(right) > type_positive_bits(ret)) 334 ret = right; 335 336 if (type_is_ptr(left)) 337 ret = left; 338 if (type_is_ptr(right)) 339 ret = right; 340 341 return ret; 342 } 343 344 int type_signed(struct symbol *base_type) 345 { 346 if (!base_type) 347 return 0; 348 if (base_type->ctype.modifiers & MOD_SIGNED) 349 return 1; 350 return 0; 351 } 352 353 int expr_unsigned(struct expression *expr) 354 { 355 struct symbol *sym; 356 357 sym = get_type(expr); 358 if (!sym) 359 return 0; 360 if (type_unsigned(sym)) 361 return 1; 362 return 0; 363 } 364 365 int expr_signed(struct expression *expr) 366 { 367 struct symbol *sym; 368 369 sym = get_type(expr); 370 if (!sym) 371 return 0; 372 if (type_signed(sym)) 373 return 1; 374 return 0; 375 } 376 377 int returns_unsigned(struct symbol *sym) 378 { 379 if (!sym) 380 return 0; 381 sym = get_base_type(sym); 382 if (!sym || sym->type != SYM_FN) 383 return 0; 384 sym = get_base_type(sym); 385 return type_unsigned(sym); 386 } 387 388 int is_pointer(struct expression *expr) 389 { 390 return type_is_ptr(get_type(expr)); 391 } 392 393 int returns_pointer(struct symbol *sym) 394 { 395 if (!sym) 396 return 0; 397 sym = get_base_type(sym); 398 if (!sym || sym->type != SYM_FN) 399 return 0; 400 sym = get_base_type(sym); 401 if (sym->type == SYM_PTR) 402 return 1; 403 return 0; 404 } 405 406 sval_t sval_type_max(struct symbol *base_type) 407 { 408 sval_t ret; 409 410 if (!base_type || !type_bits(base_type)) 411 base_type = &llong_ctype; 412 ret.type = base_type; 413 414 ret.value = (~0ULL) >> (64 - type_positive_bits(base_type)); 415 return ret; 416 } 417 418 sval_t sval_type_min(struct symbol *base_type) 419 { 420 sval_t ret; 421 422 if (!base_type || !type_bits(base_type)) 423 base_type = &llong_ctype; 424 ret.type = base_type; 425 426 if (type_unsigned(base_type) || is_ptr_type(base_type)) { 427 ret.value = 0; 428 return ret; 429 } 430 431 ret.value = (~0ULL) << type_positive_bits(base_type); 432 433 return ret; 434 } 435 436 int nr_bits(struct expression *expr) 437 { 438 struct symbol *type; 439 440 type = get_type(expr); 441 if (!type) 442 return 0; 443 return type_bits(type); 444 } 445 446 int is_void_pointer(struct expression *expr) 447 { 448 struct symbol *type; 449 450 type = get_type(expr); 451 if (!type || type->type != SYM_PTR) 452 return 0; 453 type = get_real_base_type(type); 454 if (type == &void_ctype) 455 return 1; 456 return 0; 457 } 458 459 int is_char_pointer(struct expression *expr) 460 { 461 struct symbol *type; 462 463 type = get_type(expr); 464 if (!type || type->type != SYM_PTR) 465 return 0; 466 type = get_real_base_type(type); 467 if (type == &char_ctype) 468 return 1; 469 return 0; 470 } 471 472 int is_string(struct expression *expr) 473 { 474 expr = strip_expr(expr); 475 if (!expr || expr->type != EXPR_STRING) 476 return 0; 477 if (expr->string) 478 return 1; 479 return 0; 480 } 481 482 int is_static(struct expression *expr) 483 { 484 char *name; 485 struct symbol *sym; 486 int ret = 0; 487 488 name = expr_to_str_sym(expr, &sym); 489 if (!name || !sym) 490 goto free; 491 492 if (sym->ctype.modifiers & MOD_STATIC) 493 ret = 1; 494 free: 495 free_string(name); 496 return ret; 497 } 498 499 int is_local_variable(struct expression *expr) 500 { 501 struct symbol *sym; 502 char *name; 503 504 name = expr_to_var_sym(expr, &sym); 505 free_string(name); 506 if (!sym || !sym->scope || !sym->scope->token || !cur_func_sym) 507 return 0; 508 if (cmp_pos(sym->scope->token->pos, cur_func_sym->pos) < 0) 509 return 0; 510 if (is_static(expr)) 511 return 0; 512 return 1; 513 } 514 515 int types_equiv(struct symbol *one, struct symbol *two) 516 { 517 if (!one && !two) 518 return 1; 519 if (!one || !two) 520 return 0; 521 if (one->type != two->type) 522 return 0; 523 if (one->type == SYM_PTR) 524 return types_equiv(get_real_base_type(one), get_real_base_type(two)); 525 if (type_positive_bits(one) != type_positive_bits(two)) 526 return 0; 527 return 1; 528 } 529 530 int fn_static(void) 531 { 532 return !!(cur_func_sym->ctype.modifiers & MOD_STATIC); 533 } 534 535 const char *global_static(void) 536 { 537 if (cur_func_sym->ctype.modifiers & MOD_STATIC) 538 return "static"; 539 else 540 return "global"; 541 } 542 543 struct symbol *cur_func_return_type(void) 544 { 545 struct symbol *sym; 546 547 sym = get_real_base_type(cur_func_sym); 548 if (!sym || sym->type != SYM_FN) 549 return NULL; 550 sym = get_real_base_type(sym); 551 return sym; 552 } 553 554 struct symbol *get_arg_type(struct expression *fn, int arg) 555 { 556 struct symbol *fn_type; 557 struct symbol *tmp; 558 struct symbol *arg_type; 559 int i; 560 561 fn_type = get_type(fn); 562 if (!fn_type) 563 return NULL; 564 if (fn_type->type == SYM_PTR) 565 fn_type = get_real_base_type(fn_type); 566 if (fn_type->type != SYM_FN) 567 return NULL; 568 569 i = 0; 570 FOR_EACH_PTR(fn_type->arguments, tmp) { 571 arg_type = get_real_base_type(tmp); 572 if (i == arg) { 573 return arg_type; 574 } 575 i++; 576 } END_FOR_EACH_PTR(tmp); 577 578 return NULL; 579 } 580 581 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name) 582 { 583 struct symbol *tmp, *sub; 584 int chunk_len; 585 586 if (strncmp(name, ".", 1) == 0) 587 name += 1; 588 else if (strncmp(name, "->", 2) == 0) 589 name += 2; 590 591 FOR_EACH_PTR(symbol_list, tmp) { 592 if (!tmp->ident) { 593 sub = get_real_base_type(tmp); 594 sub = get_member_from_string(sub->symbol_list, name); 595 if (sub) 596 return sub; 597 continue; 598 } 599 600 if (strcmp(tmp->ident->name, name) == 0) 601 return tmp; 602 603 chunk_len = tmp->ident->len; 604 if (strncmp(tmp->ident->name, name, chunk_len) == 0 && 605 (name[chunk_len] == '.' || name[chunk_len] == '-')) { 606 sub = get_real_base_type(tmp); 607 if (sub->type == SYM_PTR) 608 sub = get_real_base_type(sub); 609 return get_member_from_string(sub->symbol_list, name + chunk_len); 610 } 611 612 } END_FOR_EACH_PTR(tmp); 613 614 return NULL; 615 } 616 617 struct symbol *get_member_type_from_key(struct expression *expr, const char *key) 618 { 619 struct symbol *sym; 620 621 if (strcmp(key, "$") == 0) 622 return get_type(expr); 623 624 if (strcmp(key, "*$") == 0) { 625 sym = get_type(expr); 626 if (!sym || sym->type != SYM_PTR) 627 return NULL; 628 return get_real_base_type(sym); 629 } 630 631 sym = get_type(expr); 632 if (!sym) 633 return NULL; 634 if (sym->type == SYM_PTR) 635 sym = get_real_base_type(sym); 636 637 key = key + 1; 638 sym = get_member_from_string(sym->symbol_list, key); 639 if (!sym) 640 return NULL; 641 return get_real_base_type(sym); 642 } 643 644 struct symbol *get_arg_type_from_key(struct expression *fn, int param, struct expression *arg, const char *key) 645 { 646 struct symbol *type; 647 648 if (!key) 649 return NULL; 650 if (strcmp(key, "$") == 0) 651 return get_arg_type(fn, param); 652 if (strcmp(key, "*$") == 0) { 653 type = get_arg_type(fn, param); 654 if (!type || type->type != SYM_PTR) 655 return NULL; 656 return get_real_base_type(type); 657 } 658 return get_member_type_from_key(arg, key); 659 } 660 661 int is_struct(struct expression *expr) 662 { 663 struct symbol *type; 664 665 type = get_type(expr); 666 if (type && type->type == SYM_STRUCT) 667 return 1; 668 return 0; 669 } 670 671 static struct { 672 struct symbol *sym; 673 const char *name; 674 } base_types[] = { 675 {&bool_ctype, "bool"}, 676 {&void_ctype, "void"}, 677 {&type_ctype, "type"}, 678 {&char_ctype, "char"}, 679 {&schar_ctype, "schar"}, 680 {&uchar_ctype, "uchar"}, 681 {&short_ctype, "short"}, 682 {&sshort_ctype, "sshort"}, 683 {&ushort_ctype, "ushort"}, 684 {&int_ctype, "int"}, 685 {&sint_ctype, "sint"}, 686 {&uint_ctype, "uint"}, 687 {&long_ctype, "long"}, 688 {&slong_ctype, "slong"}, 689 {&ulong_ctype, "ulong"}, 690 {&llong_ctype, "llong"}, 691 {&sllong_ctype, "sllong"}, 692 {&ullong_ctype, "ullong"}, 693 {&lllong_ctype, "lllong"}, 694 {&slllong_ctype, "slllong"}, 695 {&ulllong_ctype, "ulllong"}, 696 {&float_ctype, "float"}, 697 {&double_ctype, "double"}, 698 {&ldouble_ctype, "ldouble"}, 699 {&string_ctype, "string"}, 700 {&ptr_ctype, "ptr"}, 701 {&lazy_ptr_ctype, "lazy_ptr"}, 702 {&incomplete_ctype, "incomplete"}, 703 {&label_ctype, "label"}, 704 {&bad_ctype, "bad"}, 705 {&null_ctype, "null"}, 706 }; 707 708 static const char *base_type_str(struct symbol *sym) 709 { 710 int i; 711 712 for (i = 0; i < ARRAY_SIZE(base_types); i++) { 713 if (sym == base_types[i].sym) 714 return base_types[i].name; 715 } 716 return "<unknown>"; 717 } 718 719 static int type_str_helper(char *buf, int size, struct symbol *type) 720 { 721 int n; 722 723 if (!type) 724 return snprintf(buf, size, "<unknown>"); 725 726 if (type->type == SYM_BASETYPE) { 727 return snprintf(buf, size, "%s", base_type_str(type)); 728 } else if (type->type == SYM_PTR) { 729 type = get_real_base_type(type); 730 n = type_str_helper(buf, size, type); 731 if (n > size) 732 return n; 733 return n + snprintf(buf + n, size - n, "*"); 734 } else if (type->type == SYM_ARRAY) { 735 type = get_real_base_type(type); 736 n = type_str_helper(buf, size, type); 737 if (n > size) 738 return n; 739 return n + snprintf(buf + n, size - n, "[]"); 740 } else if (type->type == SYM_STRUCT) { 741 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : ""); 742 } else if (type->type == SYM_UNION) { 743 if (type->ident) 744 return snprintf(buf, size, "union %s", type->ident->name); 745 else 746 return snprintf(buf, size, "anonymous union"); 747 } else if (type->type == SYM_FN) { 748 struct symbol *arg, *return_type, *arg_type; 749 int i; 750 751 return_type = get_real_base_type(type); 752 n = type_str_helper(buf, size, return_type); 753 if (n > size) 754 return n; 755 n += snprintf(buf + n, size - n, "(*)("); 756 if (n > size) 757 return n; 758 759 i = 0; 760 FOR_EACH_PTR(type->arguments, arg) { 761 if (i++) 762 n += snprintf(buf + n, size - n, ", "); 763 if (n > size) 764 return n; 765 arg_type = get_real_base_type(arg); 766 n += type_str_helper(buf + n, size - n, arg_type); 767 if (n > size) 768 return n; 769 } END_FOR_EACH_PTR(arg); 770 771 return n + snprintf(buf + n, size - n, ")"); 772 } else if (type->type == SYM_NODE) { 773 n = snprintf(buf, size, "node {"); 774 if (n > size) 775 return n; 776 type = get_real_base_type(type); 777 n += type_str_helper(buf + n, size - n, type); 778 if (n > size) 779 return n; 780 return n + snprintf(buf + n, size - n, "}"); 781 } else if (type->type == SYM_ENUM) { 782 return snprintf(buf, size, "enum %s", type->ident ? type->ident->name : "<unknown>"); 783 } else { 784 return snprintf(buf, size, "<type %d>", type->type); 785 } 786 } 787 788 char *type_to_str(struct symbol *type) 789 { 790 static char buf[256]; 791 792 buf[0] = '\0'; 793 type_str_helper(buf, sizeof(buf), type); 794 return buf; 795 } 796