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