smatch_extra.c

   1 /*
   2  * sparse/smatch_extra.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_extra.c is supposed to track the value of every variable.
  12  */
  13
  14 #include <stdlib.h>
  15 #ifndef __USE_ISOC99
  16 #define __USE_ISOC99
  17 #endif
  18 #include <limits.h>
  19 #include "parse.h"
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22 #include "smatch_extra.h"
  23
  24 static int my_id;
  25
  26 static struct symbol *cur_func;
  27
  28 struct data_range whole_range = {
  29         .min = LLONG_MIN,
  30         .max = LLONG_MAX,
  31 };
  32
  33 static struct smatch_state *alloc_extra_state_empty(void)
  34 {
  35         struct smatch_state *state;
  36         struct data_info *dinfo;
  37
  38         dinfo = __alloc_data_info(0);
  39         dinfo->type = DATA_RANGE;
  40         dinfo->value_ranges = NULL;
  41         state = __alloc_smatch_state(0);
  42         state->data = dinfo;
  43         return state;
  44 }
  45
  46 static struct smatch_state *alloc_extra_state_no_name(int val)
  47 {
  48         struct smatch_state *state;
  49
  50         state = __alloc_smatch_state(0);
  51         state->data = (void *)alloc_dinfo_range(val, val);
  52         return state;
  53 }
  54
  55 /* We do this because ->value_ranges is a list */
  56 struct smatch_state *extra_undefined(void)
  57 {
  58         struct data_info *dinfo;
  59         static struct smatch_state *ret;
  60         static struct symbol *prev_func;
  61
  62         if  (prev_func == cur_func)
  63                 return ret;
  64         prev_func = cur_func;
  65
  66         dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
  67         ret = __alloc_smatch_state(0);
  68         ret->name = "unknown";
  69         ret->data = dinfo;
  70         return ret;
  71 }
  72
  73 struct smatch_state *alloc_extra_state(long long val)
  74 {
  75         struct smatch_state *state;
  76
  77         state = alloc_extra_state_no_name(val);
  78         state->name = show_ranges(get_dinfo(state)->value_ranges);
  79         return state;
  80 }
  81
  82 struct smatch_state *alloc_extra_state_range(long long min, long long max)
  83 {
  84         struct smatch_state *state;
  85
  86         if (min == whole_range.min && max == whole_range.max)
  87                 return extra_undefined();
  88         state = __alloc_smatch_state(0);
  89         state->data = (void *)alloc_dinfo_range(min, max);
  90         state->name = show_ranges(get_dinfo(state)->value_ranges);
  91         return state;
  92 }
  93
  94 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
  95 {
  96         struct smatch_state *state;
  97
  98         state = __alloc_smatch_state(0);
  99         state->data = (void *)alloc_dinfo_range_list(rl);
 100         state->name = show_ranges(get_dinfo(state)->value_ranges);
 101         return state;
 102 }
 103
 104 struct data_info *get_dinfo(struct smatch_state *state)
 105 {
 106         if (!state)
 107                 return NULL;
 108         return (struct data_info *)state->data;
 109
 110 }
 111
 112 struct smatch_state *filter_range(struct smatch_state *orig,
 113                                  long long filter_min, long long filter_max)
 114 {
 115         struct smatch_state *ret;
 116         struct data_info *orig_info;
 117         struct data_info *ret_info;
 118
 119         if (!orig)
 120                 orig = extra_undefined();
 121         orig_info = get_dinfo(orig);
 122         ret = alloc_extra_state_empty();
 123         ret_info = get_dinfo(ret);
 124         ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
 125         ret->name = show_ranges(ret_info->value_ranges);
 126         return ret;
 127 }
 128
 129 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
 130 {
 131         return filter_range(orig, num, num);
 132 }
 133
 134 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 135                                        struct smatch_state *s1,
 136                                        struct smatch_state *s2)
 137 {
 138         struct data_info *info1 = get_dinfo(s1);
 139         struct data_info *info2 = get_dinfo(s2);
 140         struct data_info *ret_info;
 141         struct smatch_state *tmp;
 142         struct range_list *value_ranges;
 143
 144         value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
 145         tmp = alloc_extra_state_empty();
 146         ret_info = get_dinfo(tmp);
 147         ret_info->value_ranges = value_ranges;
 148         tmp->name = show_ranges(ret_info->value_ranges);
 149         return tmp;
 150 }
 151
 152 void __extra_handle_canonical_for_loop(struct statement *loop)
 153 {
 154         struct expression *iter_expr;
 155         struct expression *iter_var;
 156         struct expression *condition;
 157         struct sm_state *sm;
 158         long long start;
 159         long long end;
 160
 161         if (!loop->iterator_post_statement)
 162                 return;
 163         if (loop->iterator_post_statement->type != STMT_EXPRESSION)
 164                 return;
 165         iter_expr = loop->iterator_post_statement->expression;
 166         if (!loop->iterator_pre_condition)
 167                 return;
 168         if (loop->iterator_pre_condition->type != EXPR_COMPARE)
 169                 return;
 170         condition = loop->iterator_pre_condition;
 171
 172
 173         if (iter_expr->op != SPECIAL_INCREMENT)
 174                 return;
 175         iter_var = iter_expr->unop;
 176         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 177         if (!sm)
 178                 return;
 179         if (!get_single_value_from_dinfo(get_dinfo(sm->state), &start))
 180                 return;
 181         if (!get_value(condition->right, &end))
 182                 return;
 183         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 184                 return;
 185
 186         switch (condition->op) {
 187         case SPECIAL_NOTEQUAL:
 188                 set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(start, end - 1));
 189                 break;
 190         case '<':
 191                 set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(start, end - 1));
 192                 break;
 193         case SPECIAL_LTE:
 194                 set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(start, end));
 195                 break;
 196         }
 197 }
 198
 199 struct sm_state *__extra_pre_loop_hook_before(struct statement *iterator_pre_statement)
 200 {
 201         struct expression *expr;
 202         char *name;
 203         struct symbol *sym;
 204         struct sm_state *ret = NULL;
 205
 206         if (!iterator_pre_statement)
 207                 return NULL;
 208         if (iterator_pre_statement->type != STMT_EXPRESSION)
 209                 return NULL;
 210         expr = iterator_pre_statement->expression;
 211         if (expr->type != EXPR_ASSIGNMENT)
 212                 return NULL;
 213         name = get_variable_from_expr(expr->left, &sym);
 214         if (!name || !sym)
 215                 goto free;
 216         ret = get_sm_state(my_id, name, sym);
 217 free:
 218         free_string(name);
 219         return ret;
 220 }
 221
 222 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
 223 {
 224         struct expression *iter_expr;
 225         char *name;
 226         struct symbol *sym;
 227         int ret = 0;
 228
 229         if (!iterator)
 230                 return 0;
 231         if (iterator->type != STMT_EXPRESSION)
 232                 return 0;
 233         iter_expr = iterator->expression;
 234         if (iter_expr->op != SPECIAL_INCREMENT && iter_expr->op != SPECIAL_DECREMENT)
 235                 return 0;
 236         name = get_variable_from_expr(iter_expr->unop, &sym);
 237         if (!name || !sym)
 238                 goto free;
 239         if (get_sm_state(my_id, name, sym) == sm)
 240                 ret = 1;
 241 free:
 242         free_string(name);
 243         return ret;
 244 }
 245
 246 void __extra_pre_loop_hook_after(struct sm_state *sm,
 247                                 struct statement *iterator,
 248                                 struct expression *condition)
 249 {
 250         struct expression *iter_expr;
 251         char *name;
 252         struct symbol *sym;
 253         long long value;
 254         int left = 0;
 255         struct smatch_state *state;
 256         struct data_info *dinfo;
 257         long long min, max;
 258
 259         iter_expr = iterator->expression;
 260
 261         if (condition->type != EXPR_COMPARE)
 262                 return;
 263         if (!get_value(condition->left, &value)) {
 264                 if (!get_value(condition->right, &value))
 265                         return;
 266                 left = 1;
 267         }
 268         if (left)
 269                 name = get_variable_from_expr(condition->left, &sym);
 270         else
 271                 name = get_variable_from_expr(condition->right, &sym);
 272         if (!name || !sym)
 273                 goto free;
 274         if (sym != sm->sym || strcmp(name, sm->name))
 275                 goto free;
 276         state = get_state(my_id, name, sym);
 277         dinfo = get_dinfo(state);
 278         min = get_dinfo_min(dinfo);
 279         max = get_dinfo_max(dinfo);
 280         if (iter_expr->op == SPECIAL_INCREMENT && min != whole_range.min && max == whole_range.max) {
 281                 set_state(my_id, name, sym, alloc_extra_state(min));
 282         } else if (min == whole_range.min && max != whole_range.max) {
 283                 set_state(my_id, name, sym, alloc_extra_state(max));
 284         }
 285 free:
 286         free_string(name);
 287         return;
 288 }
 289
 290 static struct smatch_state *unmatched_state(struct sm_state *sm)
 291 {
 292         return extra_undefined();
 293 }
 294
 295 static void match_function_call(struct expression *expr)
 296 {
 297         struct expression *tmp;
 298         struct symbol *sym;
 299         char *name;
 300         int i = 0;
 301
 302         FOR_EACH_PTR(expr->args, tmp) {
 303                 if (tmp->type == EXPR_PREOP && tmp->op == '&') {
 304                         name = get_variable_from_expr(tmp->unop, &sym);
 305                         if (name) {
 306                                 set_state(my_id, name, sym, extra_undefined());
 307                         }
 308                         free_string(name);
 309                 }
 310                 i++;
 311         } END_FOR_EACH_PTR(tmp);
 312 }
 313
 314 static void match_assign(struct expression *expr)
 315 {
 316         struct expression *left;
 317         struct expression *right;
 318         struct symbol *sym;
 319         char *name;
 320         long long value;
 321         int known;
 322         long long min = whole_range.min;
 323         long long max = whole_range.max;
 324         long long tmp;
 325         struct range_list *rl = NULL;
 326
 327         left = strip_expr(expr->left);
 328         name = get_variable_from_expr(left, &sym);
 329         if (!name)
 330                 return;
 331         right = strip_expr(expr->right);
 332         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
 333                 right = strip_expr(right->left);
 334
 335         known = get_implied_range_list(right, &rl);
 336         if (expr->op == '=') {
 337                 if (known)
 338                         set_state(my_id, name, sym, alloc_extra_state_range_list(rl));
 339                 else
 340                         set_state(my_id, name, sym, extra_undefined());
 341                 goto free;
 342         }
 343
 344         known = get_implied_value(right, &value);
 345         if (expr->op == SPECIAL_ADD_ASSIGN) {
 346                 if (get_implied_min(left, &tmp)) {
 347                         if (known)
 348                                 min = tmp + value;
 349                         else
 350                                 min = tmp;
 351                 }
 352
 353         }
 354         if (expr->op == SPECIAL_SUB_ASSIGN) {
 355                 if (get_implied_max(left, &tmp)) {
 356                         if (known)
 357                                 max = tmp - value;
 358                         else
 359                                 max = tmp;
 360                 }
 361
 362         }
 363         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 364 free:
 365         free_string(name);
 366 }
 367
 368 static void unop_expr(struct expression *expr)
 369 {
 370         struct symbol *sym;
 371         char *name;
 372         long long min = whole_range.min;
 373         long long max = whole_range.max;
 374         long long val;
 375
 376         if (expr->op == '*')
 377                 return;
 378         if (expr->op == '(')
 379                 return;
 380         if (expr->op == '!')
 381                 return;
 382
 383         name = get_variable_from_expr(expr->unop, &sym);
 384         if (!name)
 385                 goto free;
 386         if (expr->op == SPECIAL_INCREMENT) {
 387                 if (get_implied_min(expr->unop, &val))
 388                         min = val + 1;
 389         }
 390         if (expr->op == SPECIAL_DECREMENT) {
 391                 if (get_implied_max(expr->unop, &val))
 392                         max = val - 1;
 393         }
 394         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 395 free:
 396         free_string(name);
 397 }
 398
 399 static void match_declarations(struct symbol *sym)
 400 {
 401         const char *name;
 402         long long val;
 403
 404         if (sym->ident) {
 405                 name = sym->ident->name;
 406                 if (sym->initializer) {
 407                         if (get_value(sym->initializer, &val))
 408                                 set_state(my_id, name, sym, alloc_extra_state(val));
 409                         else
 410                                 set_state(my_id, name, sym, extra_undefined());
 411                         scoped_state(my_id, name, sym);
 412                 } else {
 413                         set_state(my_id, name, sym, extra_undefined());
 414                         scoped_state(my_id, name, sym);
 415                 }
 416         }
 417 }
 418
 419 static void match_function_def(struct symbol *sym)
 420 {
 421         struct symbol *arg;
 422
 423         cur_func = sym;
 424         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 425                 if (!arg->ident) {
 426                         continue;
 427                 }
 428                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 429         } END_FOR_EACH_PTR(arg);
 430 }
 431
 432 #define VAL_SINGLE 0
 433 #define VAL_MAX    1
 434 #define VAL_MIN    2
 435
 436 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 437 {
 438         struct smatch_state *state;
 439         struct symbol *sym;
 440         char *name;
 441
 442         if (get_value(expr, val))
 443                 return 1;
 444
 445         name = get_variable_from_expr(expr, &sym);
 446         if (!name)
 447                 return 0;
 448         state = get_state(my_id, name, sym);
 449         free_string(name);
 450         if (!state || !state->data)
 451                 return 0;
 452         if (what == VAL_SINGLE)
 453                 return get_single_value_from_dinfo(get_dinfo(state), val);
 454         if (what == VAL_MAX) {
 455                 *val = get_dinfo_max(get_dinfo(state));
 456                 if (*val == whole_range.max) /* this means just guessing */
 457                         return 0;
 458                 return 1;
 459         }
 460         *val = get_dinfo_min(get_dinfo(state));
 461         if (*val == whole_range.min)
 462                 return 0;
 463         return 1;
 464 }
 465
 466 int get_implied_single_val(struct expression *expr, long long *val)
 467 {
 468         return get_implied_value_helper(expr, val, VAL_SINGLE);
 469 }
 470
 471 int get_implied_max(struct expression *expr, long long *val)
 472 {
 473         return get_implied_value_helper(expr, val, VAL_MAX);
 474 }
 475
 476 int get_implied_min(struct expression *expr, long long *val)
 477 {
 478         return get_implied_value_helper(expr, val, VAL_MIN);
 479 }
 480
 481 int get_implied_single_fuzzy_max(struct expression *expr, long long *max)
 482 {
 483         struct sm_state *sm;
 484         struct sm_state *tmp;
 485
 486         if (get_implied_max(expr, max))
 487                 return 1;
 488
 489         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 490         if (!sm)
 491                 return 0;
 492
 493         *max = whole_range.min;
 494         FOR_EACH_PTR(sm->possible, tmp) {
 495                 long long new_min;
 496
 497                 new_min = get_dinfo_min(get_dinfo(tmp->state));
 498                 if (new_min > *max)
 499                         *max = new_min;
 500         } END_FOR_EACH_PTR(tmp);
 501
 502         if (*max > whole_range.min)
 503                 return 1;
 504         return 0;
 505 }
 506
 507 int get_implied_single_fuzzy_min(struct expression *expr, long long *min)
 508 {
 509         struct sm_state *sm;
 510         struct sm_state *tmp;
 511
 512         if (get_implied_min(expr, min))
 513                 return 1;
 514
 515         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 516         if (!sm)
 517                 return 0;
 518
 519         *min = whole_range.max;
 520         FOR_EACH_PTR(sm->possible, tmp) {
 521                 long long new_max;
 522
 523                 new_max = get_dinfo_max(get_dinfo(tmp->state));
 524                 if (new_max < *min)
 525                         *min = new_max;
 526         } END_FOR_EACH_PTR(tmp);
 527
 528         if (*min < whole_range.max)
 529                 return 1;
 530         return 0;
 531 }
 532
 533 static int last_stmt_val(struct statement *stmt, long long *val)
 534 {
 535         struct expression *expr;
 536
 537         if (!stmt)
 538                 return 0;
 539
 540         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 541         if (stmt->type != STMT_EXPRESSION)
 542                 return 0;
 543         expr = stmt->expression;
 544         return get_value(expr, val);
 545 }
 546
 547 static void match_comparison(struct expression *expr)
 548 {
 549         long long fixed;
 550         char *name = NULL;
 551         struct symbol *sym;
 552         struct smatch_state *one_state;
 553         struct smatch_state *two_state;
 554         struct smatch_state *orig;
 555         int left = 0;
 556         int comparison = expr->op;
 557         struct expression *varies = expr->right;
 558
 559         if (!get_value(expr->left, &fixed)) {
 560                 if (!get_value(expr->right, &fixed))
 561                         return;
 562                 varies = expr->left;
 563                 left = 1;
 564         }
 565         if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
 566                 varies = varies->unop;
 567         if (varies->type == EXPR_CALL) {
 568                 function_comparison(comparison, varies, fixed, left);
 569                 return;
 570         }
 571
 572         name = get_variable_from_expr(varies, &sym);
 573         if (!name || !sym)
 574                 goto free;
 575
 576         orig = get_state(my_id, name, sym);
 577         if (!orig)
 578                 orig = extra_undefined();
 579
 580         switch (comparison) {
 581         case '<':
 582         case SPECIAL_UNSIGNED_LT:
 583                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 584                 two_state = filter_range(orig, fixed, whole_range.max);
 585                 if (left)
 586                         set_true_false_states(my_id, name, sym, two_state, one_state);
 587                 else
 588                         set_true_false_states(my_id, name, sym, one_state, two_state);
 589                 return;
 590         case SPECIAL_UNSIGNED_LTE:
 591         case SPECIAL_LTE:
 592                 one_state = filter_range(orig, whole_range.min, fixed);
 593                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 594                 if (left)
 595                         set_true_false_states(my_id, name, sym, two_state, one_state);
 596                 else
 597                         set_true_false_states(my_id, name, sym, one_state, two_state);
 598                 return;
 599         case SPECIAL_EQUAL:
 600                 // todo.  print a warning here for impossible conditions.
 601                 one_state = alloc_extra_state(fixed);
 602                 two_state = filter_range(orig, fixed, fixed);
 603                 set_true_false_states(my_id, name, sym, one_state, two_state);
 604                 return;
 605         case SPECIAL_UNSIGNED_GTE:
 606         case SPECIAL_GTE:
 607                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 608                 two_state = filter_range(orig, fixed, whole_range.max);
 609                 if (left)
 610                         set_true_false_states(my_id, name, sym, one_state, two_state);
 611                 else
 612                         set_true_false_states(my_id, name, sym, two_state, one_state);
 613                 return;
 614         case '>':
 615         case SPECIAL_UNSIGNED_GT:
 616                 one_state = filter_range(orig, whole_range.min, fixed);
 617                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 618                 if (left)
 619                         set_true_false_states(my_id, name, sym, one_state, two_state);
 620                 else
 621                         set_true_false_states(my_id, name, sym, two_state, one_state);
 622                 return;
 623         case SPECIAL_NOTEQUAL:
 624                 one_state = alloc_extra_state(fixed);
 625                 two_state = filter_range(orig, fixed, fixed);
 626                 set_true_false_states(my_id, name, sym, two_state, one_state);
 627                 return;
 628         default:
 629                 sm_msg("unhandled comparison %d\n", comparison);
 630                 return;
 631         }
 632         return;
 633 free:
 634         free_string(name);
 635 }
 636
 637 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 638 void __extra_match_condition(struct expression *expr)
 639 {
 640         struct symbol *sym;
 641         char *name;
 642         struct smatch_state *pre_state;
 643         struct smatch_state *true_state;
 644         struct smatch_state *false_state;
 645
 646         expr = strip_expr(expr);
 647         switch (expr->type) {
 648         case EXPR_CALL:
 649                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 650                 return;
 651         case EXPR_PREOP:
 652         case EXPR_SYMBOL:
 653         case EXPR_DEREF:
 654                 name = get_variable_from_expr(expr, &sym);
 655                 if (!name)
 656                         return;
 657                 pre_state = get_state(my_id, name, sym);
 658                 true_state = add_filter(pre_state, 0);
 659                 false_state = alloc_extra_state(0);
 660                 set_true_false_states(my_id, name, sym, true_state, false_state);
 661                 free_string(name);
 662                 return;
 663         case EXPR_COMPARE:
 664                 match_comparison(expr);
 665                 return;
 666         case EXPR_ASSIGNMENT:
 667                 __extra_match_condition(expr->left);
 668                 return;
 669         }
 670 }
 671
 672 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
 673 int implied_not_equal(struct expression *expr, long long val)
 674 {
 675         char *name;
 676         struct symbol *sym;
 677         struct smatch_state *state;
 678         int ret = 0;
 679
 680         name = get_variable_from_expr(expr, &sym);
 681         if (!name || !sym)
 682                 goto exit;
 683         state = get_state(my_id, name, sym);
 684         if (!state || !state->data)
 685                 goto exit;
 686         ret = !possibly_false(SPECIAL_NOTEQUAL, get_dinfo(state), val, 1);
 687 exit:
 688         free_string(name);
 689         return ret;
 690 }
 691
 692 int known_condition_true(struct expression *expr)
 693 {
 694         long long tmp;
 695
 696         if (!expr)
 697                 return 0;
 698
 699         if (get_value(expr, &tmp) && tmp)
 700                 return 1;
 701
 702         expr = strip_expr(expr);
 703         switch (expr->type) {
 704         case EXPR_PREOP:
 705                 if (expr->op == '!') {
 706                         if (known_condition_false(expr->unop))
 707                                 return 1;
 708                         break;
 709                 }
 710                 break;
 711         default:
 712                 break;
 713         }
 714         return 0;
 715 }
 716
 717 int known_condition_false(struct expression *expr)
 718 {
 719         if (!expr)
 720                 return 0;
 721
 722         if (is_zero(expr))
 723                 return 1;
 724
 725         switch (expr->type) {
 726         case EXPR_PREOP:
 727                 if (expr->op == '!') {
 728                         if (known_condition_true(expr->unop))
 729                                 return 1;
 730                         break;
 731                 }
 732                 break;
 733         default:
 734                 break;
 735         }
 736         return 0;
 737 }
 738
 739 static int do_comparison_range(struct expression *expr)
 740 {
 741         struct symbol *sym;
 742         char *name;
 743         struct smatch_state *state;
 744         long long value;
 745         int left = 0;
 746         int poss_true, poss_false;
 747
 748         if (!get_value(expr->left, &value)) {
 749                 if (!get_value(expr->right, &value))
 750                         return 3;
 751                 left = 1;
 752         }
 753         if (left)
 754                 name = get_variable_from_expr(expr->left, &sym);
 755         else
 756                 name = get_variable_from_expr(expr->right, &sym);
 757         if (!name || !sym)
 758                 goto free;
 759         state = get_state(SMATCH_EXTRA, name, sym);
 760         if (!state)
 761                 goto free;
 762         poss_true = possibly_true(expr->op, get_dinfo(state), value, left);
 763         poss_false = possibly_false(expr->op, get_dinfo(state), value, left);
 764         if (!poss_true && !poss_false)
 765                 return 0;
 766         if (poss_true && !poss_false)
 767                 return 1;
 768         if (!poss_true && poss_false)
 769                 return 2;
 770         if (poss_true && poss_false)
 771                 return 3;
 772 free:
 773         free_string(name);
 774         return 3;
 775 }
 776
 777 int implied_condition_true(struct expression *expr)
 778 {
 779         struct statement *stmt;
 780         long long tmp;
 781         long long val;
 782
 783         if (!expr)
 784                 return 0;
 785
 786         if (get_value(expr, &tmp) && tmp)
 787                 return 1;
 788
 789         expr = strip_expr(expr);
 790         switch (expr->type) {
 791         case EXPR_COMPARE:
 792                 if (do_comparison_range(expr) == 1)
 793                         return 1;
 794                 break;
 795         case EXPR_PREOP:
 796                 if (expr->op == '!') {
 797                         if (implied_condition_false(expr->unop))
 798                                 return 1;
 799                         break;
 800                 }
 801                 stmt = get_block_thing(expr);
 802                 if (last_stmt_val(stmt, &val) && val == 1)
 803                         return 1;
 804                 break;
 805         default:
 806                 if (implied_not_equal(expr, 0) == 1)
 807                         return 1;
 808                 break;
 809         }
 810         return 0;
 811 }
 812
 813 int implied_condition_false(struct expression *expr)
 814 {
 815         struct statement *stmt;
 816         struct expression *tmp;
 817         long long val;
 818
 819         if (!expr)
 820                 return 0;
 821
 822         if (is_zero(expr))
 823                 return 1;
 824
 825         switch (expr->type) {
 826         case EXPR_COMPARE:
 827                 if (do_comparison_range(expr) == 2)
 828                         return 1;
 829         case EXPR_PREOP:
 830                 if (expr->op == '!') {
 831                         if (implied_condition_true(expr->unop))
 832                                 return 1;
 833                         break;
 834                 }
 835                 stmt = get_block_thing(expr);
 836                 if (last_stmt_val(stmt, &val) && val == 0)
 837                         return 1;
 838                 tmp = strip_expr(expr);
 839                 if (tmp != expr)
 840                         return implied_condition_false(tmp);
 841                 break;
 842         default:
 843                 if (get_implied_value(expr, &val) && val == 0)
 844                         return 1;
 845                 break;
 846         }
 847         return 0;
 848 }
 849
 850 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 851 {
 852         long long val;
 853         struct smatch_state *state;
 854
 855         expr = strip_expr(expr);
 856
 857         state = get_state_expr(my_id, expr);
 858         if (state) {
 859                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
 860                 return 1;
 861         }
 862
 863         if (get_implied_value(expr, &val)) {
 864                 *rl = NULL;
 865                 add_range(rl, val, val);
 866                 return 1;
 867         }
 868
 869         if (expr->type == EXPR_BINOP && expr->op == '%') {
 870                 if (!get_implied_value(expr->right, &val))
 871                         return 0;
 872                 *rl = NULL;
 873                 add_range(rl, 0, val - 1);
 874                 return 1;
 875         }
 876
 877         return 0;
 878 }
 879
 880 void register_smatch_extra(int id)
 881 {
 882         my_id = id;
 883         add_merge_hook(my_id, &merge_func);
 884         add_unmatched_state_hook(my_id, &unmatched_state);
 885         add_hook(&unop_expr, OP_HOOK);
 886         add_hook(&match_function_def, FUNC_DEF_HOOK);
 887         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 888         add_hook(&match_assign, ASSIGNMENT_HOOK);
 889         add_hook(&match_declarations, DECLARATION_HOOK);
 890 }