smatch_type.c

   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
  25 struct symbol *get_real_base_type(struct symbol *sym)
  26 {
  27         struct symbol *ret;
  28
  29         if (!sym)
  30                 return NULL;
  31         ret = get_base_type(sym);
  32         if (ret && ret->type == SYM_RESTRICT)
  33                 return get_real_base_type(ret);
  34         return ret;
  35 }
  36
  37 int type_bits(struct symbol *type)
  38 {
  39         if (!type)
  40                 return 0;
  41         if (type->type == SYM_PTR)  /* Sparse doesn't set this for &pointers */
  42                 return bits_in_pointer;
  43         if (!type->examined)
  44                 examine_symbol_type(type);
  45         return type->bit_size;
  46 }
  47
  48 int type_bytes(struct symbol *type)
  49 {
  50         int bits = type_bits(type);
  51
  52         if (bits < 0)
  53                 return 0;
  54         return bits_to_bytes(bits);
  55 }
  56
  57 int type_positive_bits(struct symbol *type)
  58 {
  59         if (!type)
  60                 return 0;
  61         if (type_unsigned(type))
  62                 return type_bits(type);
  63         return type_bits(type) - 1;
  64 }
  65
  66 static struct symbol *get_binop_type(struct expression *expr)
  67 {
  68         struct symbol *left, *right;
  69
  70         left = get_type(expr->left);
  71         right = get_type(expr->right);
  72
  73         if (!left || !right)
  74                 return NULL;
  75
  76         if (left->type == SYM_PTR || left->type == SYM_ARRAY)
  77                 return left;
  78         if (right->type == SYM_PTR || right->type == SYM_ARRAY)
  79                 return right;
  80
  81         if (expr->op == SPECIAL_LEFTSHIFT ||
  82             expr->op == SPECIAL_RIGHTSHIFT) {
  83                 if (type_positive_bits(left) < 31)
  84                         return &int_ctype;
  85                 return left;
  86         }
  87
  88         if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
  89                 return &int_ctype;
  90
  91         if (type_positive_bits(left) > type_positive_bits(right))
  92                 return left;
  93         return right;
  94 }
  95
  96 static struct symbol *get_type_symbol(struct expression *expr)
  97 {
  98         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
  99                 return NULL;
 100
 101         return get_real_base_type(expr->symbol);
 102 }
 103
 104 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
 105 {
 106         struct symbol *tmp, *sub;
 107
 108         FOR_EACH_PTR(symbol_list, tmp) {
 109                 if (!tmp->ident) {
 110                         sub = get_real_base_type(tmp);
 111                         sub = get_member_symbol(sub->symbol_list, member);
 112                         if (sub)
 113                                 return sub;
 114                         continue;
 115                 }
 116                 if (tmp->ident == member)
 117                         return tmp;
 118         } END_FOR_EACH_PTR(tmp);
 119
 120         return NULL;
 121 }
 122
 123 static struct symbol *get_symbol_from_deref(struct expression *expr)
 124 {
 125         struct ident *member;
 126         struct symbol *sym;
 127
 128         if (!expr || expr->type != EXPR_DEREF)
 129                 return NULL;
 130
 131         member = expr->member;
 132         sym = get_type(expr->deref);
 133         if (!sym) {
 134                 // sm_msg("could not find struct type");
 135                 return NULL;
 136         }
 137         if (sym->type == SYM_PTR)
 138                 sym = get_real_base_type(sym);
 139         sym = get_member_symbol(sym->symbol_list, member);
 140         if (!sym)
 141                 return NULL;
 142         return get_real_base_type(sym);
 143 }
 144
 145 static struct symbol *get_return_type(struct expression *expr)
 146 {
 147         struct symbol *tmp;
 148
 149         tmp = get_type(expr->fn);
 150         if (!tmp)
 151                 return NULL;
 152         return get_real_base_type(tmp);
 153 }
 154
 155 static struct symbol *get_expr_stmt_type(struct statement *stmt)
 156 {
 157         if (stmt->type != STMT_COMPOUND)
 158                 return NULL;
 159         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 160         if (!stmt || 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 || (sym->type != SYM_PTR && sym->type != SYM_ARRAY))
 189                 return NULL;
 190         return get_real_base_type(sym);
 191 }
 192
 193 static struct symbol *fake_pointer_sym(struct expression *expr)
 194 {
 195         struct symbol *sym;
 196         struct symbol *base;
 197
 198         sym = alloc_symbol(expr->pos, SYM_PTR);
 199         expr = expr->unop;
 200         base = get_type(expr);
 201         if (!base)
 202                 return NULL;
 203         sym->ctype.base_type = base;
 204         return sym;
 205 }
 206
 207 struct symbol *get_type(struct expression *expr)
 208 {
 209         if (!expr)
 210                 return NULL;
 211         expr = strip_parens(expr);
 212
 213         switch (expr->type) {
 214         case EXPR_STRING:
 215                 return &string_ctype;
 216         case EXPR_SYMBOL:
 217                 return get_type_symbol(expr);
 218         case EXPR_DEREF:
 219                 return get_symbol_from_deref(expr);
 220         case EXPR_PREOP:
 221         case EXPR_POSTOP:
 222                 if (expr->op == '&')
 223                         return fake_pointer_sym(expr);
 224                 if (expr->op == '*')
 225                         return get_pointer_type(expr->unop);
 226                 return get_type(expr->unop);
 227         case EXPR_ASSIGNMENT:
 228                 return get_type(expr->left);
 229         case EXPR_CAST:
 230         case EXPR_FORCE_CAST:
 231         case EXPR_IMPLIED_CAST:
 232                 return get_real_base_type(expr->cast_type);
 233         case EXPR_COMPARE:
 234         case EXPR_BINOP:
 235                 return get_binop_type(expr);
 236         case EXPR_CALL:
 237                 return get_return_type(expr);
 238         case EXPR_STATEMENT:
 239                 return get_expr_stmt_type(expr->statement);
 240         case EXPR_CONDITIONAL:
 241         case EXPR_SELECT:
 242                 return get_select_type(expr);
 243         case EXPR_SIZEOF:
 244                 return &ulong_ctype;
 245         case EXPR_LOGICAL:
 246                 return &int_ctype;
 247         default:
 248 //              sm_msg("unhandled type %d", expr->type);
 249                 return expr->ctype;
 250         }
 251         return NULL;
 252 }
 253
 254 int type_unsigned(struct symbol *base_type)
 255 {
 256         if (!base_type)
 257                 return 0;
 258         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 259                 return 1;
 260         return 0;
 261 }
 262
 263 int type_signed(struct symbol *base_type)
 264 {
 265         if (!base_type)
 266                 return 0;
 267         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 268                 return 0;
 269         return 1;
 270 }
 271
 272 int expr_unsigned(struct expression *expr)
 273 {
 274         struct symbol *sym;
 275
 276         sym = get_type(expr);
 277         if (!sym)
 278                 return 0;
 279         if (type_unsigned(sym))
 280                 return 1;
 281         return 0;
 282 }
 283
 284 int returns_unsigned(struct symbol *sym)
 285 {
 286         if (!sym)
 287                 return 0;
 288         sym = get_base_type(sym);
 289         if (!sym || sym->type != SYM_FN)
 290                 return 0;
 291         sym = get_base_type(sym);
 292         return type_unsigned(sym);
 293 }
 294
 295 int is_pointer(struct expression *expr)
 296 {
 297         struct symbol *sym;
 298
 299         sym = get_type(expr);
 300         if (!sym)
 301                 return 0;
 302         if (sym == &string_ctype)
 303                 return 0;
 304         if (sym->type == SYM_PTR)
 305                 return 1;
 306         return 0;
 307 }
 308
 309 int returns_pointer(struct symbol *sym)
 310 {
 311         if (!sym)
 312                 return 0;
 313         sym = get_base_type(sym);
 314         if (!sym || sym->type != SYM_FN)
 315                 return 0;
 316         sym = get_base_type(sym);
 317         if (sym->type == SYM_PTR)
 318                 return 1;
 319         return 0;
 320 }
 321
 322 sval_t sval_type_max(struct symbol *base_type)
 323 {
 324         sval_t ret;
 325
 326         ret.value = (~0ULL) >> 1;
 327         ret.type = base_type;
 328
 329         if (!base_type || !type_bits(base_type))
 330                 return ret;
 331
 332         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 333         return ret;
 334 }
 335
 336 sval_t sval_type_min(struct symbol *base_type)
 337 {
 338         sval_t ret;
 339
 340         if (!base_type || !type_bits(base_type))
 341                 base_type = &llong_ctype;
 342         ret.type = base_type;
 343
 344         if (type_unsigned(base_type)) {
 345                 ret.value = 0;
 346                 return ret;
 347         }
 348
 349         ret.value = (~0ULL) << type_positive_bits(base_type);
 350
 351         return ret;
 352 }
 353
 354 int nr_bits(struct expression *expr)
 355 {
 356         struct symbol *type;
 357
 358         type = get_type(expr);
 359         if (!type)
 360                 return 0;
 361         return type_bits(type);
 362 }
 363
 364 int is_void_pointer(struct expression *expr)
 365 {
 366         struct symbol *type;
 367
 368         type = get_type(expr);
 369         if (!type || type->type != SYM_PTR)
 370                 return 0;
 371         type = get_real_base_type(type);
 372         if (type == &void_ctype)
 373                 return 1;
 374         return 0;
 375 }
 376
 377 int is_char_pointer(struct expression *expr)
 378 {
 379         struct symbol *type;
 380
 381         type = get_type(expr);
 382         if (!type || type->type != SYM_PTR)
 383                 return 0;
 384         type = get_real_base_type(type);
 385         if (type == &char_ctype)
 386                 return 1;
 387         return 0;
 388 }
 389
 390 int is_static(struct expression *expr)
 391 {
 392         char *name;
 393         struct symbol *sym;
 394         int ret = 0;
 395
 396         name = expr_to_str_sym(expr, &sym);
 397         if (!name || !sym)
 398                 goto free;
 399
 400         if (sym->ctype.modifiers & MOD_STATIC)
 401                 ret = 1;
 402 free:
 403         free_string(name);
 404         return ret;
 405 }
 406
 407 int types_equiv(struct symbol *one, struct symbol *two)
 408 {
 409         if (!one && !two)
 410                 return 1;
 411         if (!one || !two)
 412                 return 0;
 413         if (one->type != two->type)
 414                 return 0;
 415         if (one->type == SYM_PTR)
 416                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 417         if (type_positive_bits(one) != type_positive_bits(two))
 418                 return 0;
 419         return 1;
 420 }
 421
 422 int fn_static(void)
 423 {
 424         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 425 }
 426
 427 const char *global_static()
 428 {
 429         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 430                 return "static";
 431         else
 432                 return "global";
 433 }
 434
 435 struct symbol *cur_func_return_type(void)
 436 {
 437         struct symbol *sym;
 438
 439         sym = get_real_base_type(cur_func_sym);
 440         if (!sym || sym->type != SYM_FN)
 441                 return NULL;
 442         sym = get_real_base_type(sym);
 443         return sym;
 444 }
 445
 446 struct symbol *get_arg_type(struct expression *fn, int arg)
 447 {
 448         struct symbol *fn_type;
 449         struct symbol *tmp;
 450         struct symbol *arg_type;
 451         int i;
 452
 453         fn_type = get_type(fn);
 454         if (!fn_type)
 455                 return NULL;
 456         if (fn_type->type == SYM_PTR)
 457                 fn_type = get_real_base_type(fn_type);
 458         if (fn_type->type != SYM_FN)
 459                 return NULL;
 460
 461         i = 0;
 462         FOR_EACH_PTR(fn_type->arguments, tmp) {
 463                 arg_type = get_real_base_type(tmp);
 464                 if (i == arg) {
 465                         return arg_type;
 466                 }
 467                 i++;
 468         } END_FOR_EACH_PTR(tmp);
 469
 470         return NULL;
 471 }
 472
 473 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, char *name)
 474 {
 475         struct symbol *tmp, *sub;
 476         int chunk_len;
 477
 478         if (strncmp(name, ".", 1) == 0)
 479                 name += 1;
 480         if (strncmp(name, "->", 2) == 0)
 481                 name += 2;
 482
 483         FOR_EACH_PTR(symbol_list, tmp) {
 484                 if (!tmp->ident) {
 485                         sub = get_real_base_type(tmp);
 486                         sub = get_member_from_string(sub->symbol_list, name);
 487                         if (sub)
 488                                 return sub;
 489                         continue;
 490                 }
 491
 492                 if (strcmp(tmp->ident->name, name) == 0)
 493                         return tmp;
 494
 495                 chunk_len = strlen(tmp->ident->name);
 496                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 497                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 498                         sub = get_real_base_type(tmp);
 499                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 500                 }
 501
 502         } END_FOR_EACH_PTR(tmp);
 503
 504         return NULL;
 505 }
 506
 507 struct symbol *get_member_type_from_key(struct expression *expr, char *key)
 508 {
 509         struct symbol *sym;
 510         char *name;
 511
 512         if (strcmp(key, "$$") == 0)
 513                 return get_type(expr);
 514
 515         if (strcmp(key, "*$$") == 0) {
 516                 sym = get_type(expr);
 517                 if (!sym || sym->type != SYM_PTR)
 518                         return NULL;
 519                 return get_real_base_type(sym);
 520         }
 521
 522         name = expr_to_str_sym(expr, &sym);
 523         free_string(name);
 524         if (!sym)
 525                 return NULL;
 526         sym = get_real_base_type(sym);
 527         if (sym->type == SYM_PTR)
 528                 sym = get_real_base_type(sym);
 529
 530         key = key + 2;
 531         sym = get_member_from_string(sym->symbol_list, key);
 532         if (!sym)
 533                 return NULL;
 534         return get_real_base_type(sym);
 535 }
 536
 537 int is_struct(struct expression *expr)
 538 {
 539         struct symbol *type;
 540
 541         type = get_type(expr);
 542         if (type && type->type == SYM_STRUCT)
 543                 return 1;
 544         return 0;
 545 }